bpf_jit_machdep.c revision 179967
1/*- 2 * Copyright (c) 2002 - 2003 NetGroup, Politecnico di Torino (Italy) 3 * Copyright (c) 2005 Jung-uk Kim <jkim@FreeBSD.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the Politecnico di Torino nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS intERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32#include <sys/cdefs.h> 33__FBSDID("$FreeBSD: head/sys/amd64/amd64/bpf_jit_machdep.c 179967 2008-06-23 23:09:52Z jkim $"); 34 35#include "opt_bpf.h" 36 37#include <sys/param.h> 38#include <sys/systm.h> 39#include <sys/kernel.h> 40#include <sys/types.h> 41#include <sys/socket.h> 42#include <sys/malloc.h> 43 44#include <net/if.h> 45#include <net/bpf.h> 46#include <net/bpf_jitter.h> 47 48#include <amd64/amd64/bpf_jit_machdep.h> 49 50bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, int *); 51 52/* 53 * emit routine to update the jump table 54 */ 55static void 56emit_length(bpf_bin_stream *stream, u_int value, u_int len) 57{ 58 59 (stream->refs)[stream->bpf_pc] += len; 60 stream->cur_ip += len; 61} 62 63/* 64 * emit routine to output the actual binary code 65 */ 66static void 67emit_code(bpf_bin_stream *stream, u_int value, u_int len) 68{ 69 70 switch (len) { 71 case 1: 72 stream->ibuf[stream->cur_ip] = (u_char)value; 73 stream->cur_ip++; 74 break; 75 76 case 2: 77 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 78 stream->cur_ip += 2; 79 break; 80 81 case 4: 82 *((u_int *)(stream->ibuf + stream->cur_ip)) = value; 83 stream->cur_ip += 4; 84 break; 85 } 86 87 return; 88} 89 90/* 91 * Function that does the real stuff 92 */ 93bpf_filter_func 94bpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem) 95{ 96 struct bpf_insn *ins; 97 u_int i, pass; 98 bpf_bin_stream stream; 99 100 /* 101 * NOTE: do not modify the name of this variable, as it's used by 102 * the macros to emit code. 103 */ 104 emit_func emitm; 105 106 /* Do not compile an empty filter. */ 107 if (nins == 0) 108 return NULL; 109 110 /* Allocate the reference table for the jumps */ 111 stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int), 112 M_BPFJIT, M_NOWAIT); 113 if (stream.refs == NULL) 114 return NULL; 115 116 /* Reset the reference table */ 117 for (i = 0; i < nins + 1; i++) 118 stream.refs[i] = 0; 119 120 stream.cur_ip = 0; 121 stream.bpf_pc = 0; 122 123 /* 124 * the first pass will emit the lengths of the instructions 125 * to create the reference table 126 */ 127 emitm = emit_length; 128 129 pass = 0; 130 for (;;) { 131 ins = prog; 132 133 /* create the procedure header */ 134 PUSH(RBP); 135 MOVrq(RSP, RBP); 136 MOVdoq(ESI, -8, RBP); 137 MOVdoq(EDX, -12, RBP); 138 PUSH(RBX); 139 MOVrq(RDI, RBX); 140 141 for (i = 0; i < nins; i++) { 142 stream.bpf_pc++; 143 144 switch (ins->code) { 145 default: 146 return NULL; 147 148 case BPF_RET|BPF_K: 149 MOVid(ins->k, EAX); 150 POP(RBX); 151 LEAVE_RET(); 152 break; 153 154 case BPF_RET|BPF_A: 155 POP(RBX); 156 LEAVE_RET(); 157 break; 158 159 case BPF_LD|BPF_W|BPF_ABS: 160 MOVid(ins->k, ECX); 161 MOVrd(ECX, ESI); 162 ADDib(sizeof(int), ECX); 163 CMPoqd(-12, RBP, ECX); 164 JLEb(5); 165 ZERO_EAX(); 166 POP(RBX); 167 LEAVE_RET(); 168 MOVobd(RBX, RSI, EAX); 169 BSWAP(EAX); 170 break; 171 172 case BPF_LD|BPF_H|BPF_ABS: 173 ZERO_EAX(); 174 MOVid(ins->k, ECX); 175 MOVrd(ECX, ESI); 176 ADDib(sizeof(short), ECX); 177 CMPoqd(-12, RBP, ECX); 178 JLEb(3); 179 POP(RBX); 180 LEAVE_RET(); 181 MOVobw(RBX, RSI, AX); 182 SWAP_AX(); 183 break; 184 185 case BPF_LD|BPF_B|BPF_ABS: 186 ZERO_EAX(); 187 MOVid(ins->k, ECX); 188 CMPoqd(-12, RBP, ECX); 189 JLEb(3); 190 POP(RBX); 191 LEAVE_RET(); 192 MOVobb(RBX, RCX, AL); 193 break; 194 195 case BPF_LD|BPF_W|BPF_LEN: 196 MOVoqd(-8, RBP, EAX); 197 break; 198 199 case BPF_LDX|BPF_W|BPF_LEN: 200 MOVoqd(-8, RBP, EDX); 201 break; 202 203 case BPF_LD|BPF_W|BPF_IND: 204 MOVid(ins->k, ECX); 205 ADDrd(EDX, ECX); 206 MOVrd(ECX, ESI); 207 ADDib(sizeof(int), ECX); 208 CMPoqd(-12, RBP, ECX); 209 JLEb(5); 210 ZERO_EAX(); 211 POP(RBX); 212 LEAVE_RET(); 213 MOVobd(RBX, RSI, EAX); 214 BSWAP(EAX); 215 break; 216 217 case BPF_LD|BPF_H|BPF_IND: 218 ZERO_EAX(); 219 MOVid(ins->k, ECX); 220 ADDrd(EDX, ECX); 221 MOVrd(ECX, ESI); 222 ADDib(sizeof(short), ECX); 223 CMPoqd(-12, RBP, ECX); 224 JLEb(3); 225 POP(RBX); 226 LEAVE_RET(); 227 MOVobw(RBX, RSI, AX); 228 SWAP_AX(); 229 break; 230 231 case BPF_LD|BPF_B|BPF_IND: 232 ZERO_EAX(); 233 MOVid(ins->k, ECX); 234 ADDrd(EDX, ECX); 235 CMPoqd(-12, RBP, ECX); 236 JLEb(3); 237 POP(RBX); 238 LEAVE_RET(); 239 MOVobb(RBX, RCX, AL); 240 break; 241 242 case BPF_LDX|BPF_MSH|BPF_B: 243 MOVid(ins->k, ECX); 244 CMPoqd(-12, RBP, ECX); 245 JLEb(5); 246 ZERO_EAX(); 247 POP(RBX); 248 LEAVE_RET(); 249 ZERO_EDX(); 250 MOVobb(RBX, RCX, DL); 251 ANDib(0xf, DL); 252 SHLib(2, EDX); 253 break; 254 255 case BPF_LD|BPF_IMM: 256 MOVid(ins->k, EAX); 257 break; 258 259 case BPF_LDX|BPF_IMM: 260 MOVid(ins->k, EDX); 261 break; 262 263 case BPF_LD|BPF_MEM: 264 MOViq((uintptr_t)mem, RCX); 265 MOVid(ins->k * 4, ESI); 266 MOVobd(RCX, RSI, EAX); 267 break; 268 269 case BPF_LDX|BPF_MEM: 270 MOViq((uintptr_t)mem, RCX); 271 MOVid(ins->k * 4, ESI); 272 MOVobd(RCX, RSI, EDX); 273 break; 274 275 case BPF_ST: 276 /* 277 * XXX this command and the following could 278 * be optimized if the previous instruction 279 * was already of this type 280 */ 281 MOViq((uintptr_t)mem, RCX); 282 MOVid(ins->k * 4, ESI); 283 MOVomd(EAX, RCX, RSI); 284 break; 285 286 case BPF_STX: 287 MOViq((uintptr_t)mem, RCX); 288 MOVid(ins->k * 4, ESI); 289 MOVomd(EDX, RCX, RSI); 290 break; 291 292 case BPF_JMP|BPF_JA: 293 JMP(stream.refs[stream.bpf_pc + ins->k] - 294 stream.refs[stream.bpf_pc]); 295 break; 296 297 case BPF_JMP|BPF_JGT|BPF_K: 298 CMPid(ins->k, EAX); 299 /* 5 is the size of the following JMP */ 300 JG(stream.refs[stream.bpf_pc + ins->jt] - 301 stream.refs[stream.bpf_pc] + 5 ); 302 JMP(stream.refs[stream.bpf_pc + ins->jf] - 303 stream.refs[stream.bpf_pc]); 304 break; 305 306 case BPF_JMP|BPF_JGE|BPF_K: 307 CMPid(ins->k, EAX); 308 JGE(stream.refs[stream.bpf_pc + ins->jt] - 309 stream.refs[stream.bpf_pc] + 5); 310 JMP(stream.refs[stream.bpf_pc + ins->jf] - 311 stream.refs[stream.bpf_pc]); 312 break; 313 314 case BPF_JMP|BPF_JEQ|BPF_K: 315 CMPid(ins->k, EAX); 316 JE(stream.refs[stream.bpf_pc + ins->jt] - 317 stream.refs[stream.bpf_pc] + 5); 318 JMP(stream.refs[stream.bpf_pc + ins->jf] - 319 stream.refs[stream.bpf_pc]); 320 break; 321 322 case BPF_JMP|BPF_JSET|BPF_K: 323 MOVrd(EAX, ECX); 324 ANDid(ins->k, ECX); 325 JE(stream.refs[stream.bpf_pc + ins->jf] - 326 stream.refs[stream.bpf_pc] + 5); 327 JMP(stream.refs[stream.bpf_pc + ins->jt] - 328 stream.refs[stream.bpf_pc]); 329 break; 330 331 case BPF_JMP|BPF_JGT|BPF_X: 332 CMPrd(EDX, EAX); 333 JA(stream.refs[stream.bpf_pc + ins->jt] - 334 stream.refs[stream.bpf_pc] + 5); 335 JMP(stream.refs[stream.bpf_pc + ins->jf] - 336 stream.refs[stream.bpf_pc]); 337 break; 338 339 case BPF_JMP|BPF_JGE|BPF_X: 340 CMPrd(EDX, EAX); 341 JAE(stream.refs[stream.bpf_pc + ins->jt] - 342 stream.refs[stream.bpf_pc] + 5); 343 JMP(stream.refs[stream.bpf_pc + ins->jf] - 344 stream.refs[stream.bpf_pc]); 345 break; 346 347 case BPF_JMP|BPF_JEQ|BPF_X: 348 CMPrd(EDX, EAX); 349 JE(stream.refs[stream.bpf_pc + ins->jt] - 350 stream.refs[stream.bpf_pc] + 5); 351 JMP(stream.refs[stream.bpf_pc + ins->jf] - 352 stream.refs[stream.bpf_pc]); 353 break; 354 355 case BPF_JMP|BPF_JSET|BPF_X: 356 MOVrd(EAX, ECX); 357 ANDrd(EDX, ECX); 358 JE(stream.refs[stream.bpf_pc + ins->jf] - 359 stream.refs[stream.bpf_pc] + 5); 360 JMP(stream.refs[stream.bpf_pc + ins->jt] - 361 stream.refs[stream.bpf_pc]); 362 break; 363 364 case BPF_ALU|BPF_ADD|BPF_X: 365 ADDrd(EDX, EAX); 366 break; 367 368 case BPF_ALU|BPF_SUB|BPF_X: 369 SUBrd(EDX, EAX); 370 break; 371 372 case BPF_ALU|BPF_MUL|BPF_X: 373 MOVrd(EDX, ECX); 374 MULrd(EDX); 375 MOVrd(ECX, EDX); 376 break; 377 378 case BPF_ALU|BPF_DIV|BPF_X: 379 CMPid(0, EDX); 380 JNEb(5); 381 ZERO_EAX(); 382 POP(RBX); 383 LEAVE_RET(); 384 MOVrd(EDX, ECX); 385 ZERO_EDX(); 386 DIVrd(ECX); 387 MOVrd(ECX, EDX); 388 break; 389 390 case BPF_ALU|BPF_AND|BPF_X: 391 ANDrd(EDX, EAX); 392 break; 393 394 case BPF_ALU|BPF_OR|BPF_X: 395 ORrd(EDX, EAX); 396 break; 397 398 case BPF_ALU|BPF_LSH|BPF_X: 399 MOVrd(EDX, ECX); 400 SHL_CLrb(EAX); 401 break; 402 403 case BPF_ALU|BPF_RSH|BPF_X: 404 MOVrd(EDX, ECX); 405 SHR_CLrb(EAX); 406 break; 407 408 case BPF_ALU|BPF_ADD|BPF_K: 409 ADD_EAXi(ins->k); 410 break; 411 412 case BPF_ALU|BPF_SUB|BPF_K: 413 SUB_EAXi(ins->k); 414 break; 415 416 case BPF_ALU|BPF_MUL|BPF_K: 417 MOVrd(EDX, ECX); 418 MOVid(ins->k, EDX); 419 MULrd(EDX); 420 MOVrd(ECX, EDX); 421 break; 422 423 case BPF_ALU|BPF_DIV|BPF_K: 424 MOVrd(EDX, ECX); 425 ZERO_EDX(); 426 MOVid(ins->k, ESI); 427 DIVrd(ESI); 428 MOVrd(ECX, EDX); 429 break; 430 431 case BPF_ALU|BPF_AND|BPF_K: 432 ANDid(ins->k, EAX); 433 break; 434 435 case BPF_ALU|BPF_OR|BPF_K: 436 ORid(ins->k, EAX); 437 break; 438 439 case BPF_ALU|BPF_LSH|BPF_K: 440 SHLib((ins->k) & 0xff, EAX); 441 break; 442 443 case BPF_ALU|BPF_RSH|BPF_K: 444 SHRib((ins->k) & 0xff, EAX); 445 break; 446 447 case BPF_ALU|BPF_NEG: 448 NEGd(EAX); 449 break; 450 451 case BPF_MISC|BPF_TAX: 452 MOVrd(EAX, EDX); 453 break; 454 455 case BPF_MISC|BPF_TXA: 456 MOVrd(EDX, EAX); 457 break; 458 } 459 ins++; 460 } 461 462 pass++; 463 if (pass == 2) 464 break; 465 466 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 467 if (stream.ibuf == NULL) { 468 free(stream.refs, M_BPFJIT); 469 return NULL; 470 } 471 472 /* 473 * modify the reference table to contain the offsets and 474 * not the lengths of the instructions 475 */ 476 for (i = 1; i < nins + 1; i++) 477 stream.refs[i] += stream.refs[i - 1]; 478 479 /* Reset the counters */ 480 stream.cur_ip = 0; 481 stream.bpf_pc = 0; 482 483 /* the second pass creates the actual code */ 484 emitm = emit_code; 485 } 486 487 /* 488 * the reference table is needed only during compilation, 489 * now we can free it 490 */ 491 free(stream.refs, M_BPFJIT); 492 493 return (bpf_filter_func)stream.ibuf; 494} 495