bpf_jit_machdep.c revision 179978
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/i386/i386/bpf_jit_machdep.c 179978 2008-06-24 20:12:44Z 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 <i386/i386/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(EBP); 135 MOVrd(ESP, EBP); 136 PUSH(EDI); 137 PUSH(ESI); 138 PUSH(EBX); 139 MOVodd(8, EBP, EBX); 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(EBX); 151 POP(ESI); 152 POP(EDI); 153 LEAVE_RET(); 154 break; 155 156 case BPF_RET|BPF_A: 157 POP(EBX); 158 POP(ESI); 159 POP(EDI); 160 LEAVE_RET(); 161 break; 162 163 case BPF_LD|BPF_W|BPF_ABS: 164 MOVid(ins->k, ECX); 165 MOVrd(ECX, ESI); 166 ADDib(sizeof(int), ECX); 167 CMPodd(0x10, EBP, ECX); 168 JLEb(7); 169 ZEROrd(EAX); 170 POP(EBX); 171 POP(ESI); 172 POP(EDI); 173 LEAVE_RET(); 174 MOVobd(EBX, ESI, EAX); 175 BSWAP(EAX); 176 break; 177 178 case BPF_LD|BPF_H|BPF_ABS: 179 ZEROrd(EAX); 180 MOVid(ins->k, ECX); 181 MOVrd(ECX, ESI); 182 ADDib(sizeof(short), ECX); 183 CMPodd(0x10, EBP, ECX); 184 JLEb(5); 185 POP(EBX); 186 POP(ESI); 187 POP(EDI); 188 LEAVE_RET(); 189 MOVobw(EBX, ESI, AX); 190 SWAP_AX(); 191 break; 192 193 case BPF_LD|BPF_B|BPF_ABS: 194 ZEROrd(EAX); 195 MOVid(ins->k, ECX); 196 CMPodd(0x10, EBP, ECX); 197 JLEb(5); 198 POP(EBX); 199 POP(ESI); 200 POP(EDI); 201 LEAVE_RET(); 202 MOVobb(EBX, ECX, AL); 203 break; 204 205 case BPF_LD|BPF_W|BPF_LEN: 206 MOVodd(0xc, EBP, EAX); 207 break; 208 209 case BPF_LDX|BPF_W|BPF_LEN: 210 MOVodd(0xc, EBP, EDX); 211 break; 212 213 case BPF_LD|BPF_W|BPF_IND: 214 MOVid(ins->k, ECX); 215 ADDrd(EDX, ECX); 216 MOVrd(ECX, ESI); 217 ADDib(sizeof(int), ECX); 218 CMPodd(0x10, EBP, ECX); 219 JLEb(7); 220 ZEROrd(EAX); 221 POP(EBX); 222 POP(ESI); 223 POP(EDI); 224 LEAVE_RET(); 225 MOVobd(EBX, ESI, EAX); 226 BSWAP(EAX); 227 break; 228 229 case BPF_LD|BPF_H|BPF_IND: 230 ZEROrd(EAX); 231 MOVid(ins->k, ECX); 232 ADDrd(EDX, ECX); 233 MOVrd(ECX, ESI); 234 ADDib(sizeof(short), ECX); 235 CMPodd(0x10, EBP, ECX); 236 JLEb(5); 237 POP(EBX); 238 POP(ESI); 239 POP(EDI); 240 LEAVE_RET(); 241 MOVobw(EBX, ESI, AX); 242 SWAP_AX(); 243 break; 244 245 case BPF_LD|BPF_B|BPF_IND: 246 ZEROrd(EAX); 247 MOVid(ins->k, ECX); 248 ADDrd(EDX, ECX); 249 CMPodd(0x10, EBP, ECX); 250 JLEb(5); 251 POP(EBX); 252 POP(ESI); 253 POP(EDI); 254 LEAVE_RET(); 255 MOVobb(EBX, ECX, AL); 256 break; 257 258 case BPF_LDX|BPF_MSH|BPF_B: 259 MOVid(ins->k, ECX); 260 CMPodd(0x10, EBP, ECX); 261 JLEb(7); 262 ZEROrd(EAX); 263 POP(EBX); 264 POP(ESI); 265 POP(EDI); 266 LEAVE_RET(); 267 ZEROrd(EDX); 268 MOVobb(EBX, ECX, DL); 269 ANDib(0xf, DL); 270 SHLib(2, EDX); 271 break; 272 273 case BPF_LD|BPF_IMM: 274 MOVid(ins->k, EAX); 275 break; 276 277 case BPF_LDX|BPF_IMM: 278 MOVid(ins->k, EDX); 279 break; 280 281 case BPF_LD|BPF_MEM: 282 MOVid((uintptr_t)mem, ECX); 283 MOVid(ins->k * 4, ESI); 284 MOVobd(ECX, ESI, EAX); 285 break; 286 287 case BPF_LDX|BPF_MEM: 288 MOVid((uintptr_t)mem, ECX); 289 MOVid(ins->k * 4, ESI); 290 MOVobd(ECX, ESI, EDX); 291 break; 292 293 case BPF_ST: 294 /* 295 * XXX this command and the following could 296 * be optimized if the previous instruction 297 * was already of this type 298 */ 299 MOVid((uintptr_t)mem, ECX); 300 MOVid(ins->k * 4, ESI); 301 MOVomd(EAX, ECX, ESI); 302 break; 303 304 case BPF_STX: 305 MOVid((uintptr_t)mem, ECX); 306 MOVid(ins->k * 4, ESI); 307 MOVomd(EDX, ECX, ESI); 308 break; 309 310 case BPF_JMP|BPF_JA: 311 JMP(stream.refs[stream.bpf_pc + ins->k] - 312 stream.refs[stream.bpf_pc]); 313 break; 314 315 case BPF_JMP|BPF_JGT|BPF_K: 316 CMPid(ins->k, EAX); 317 /* 5 is the size of the following JMP */ 318 JG(stream.refs[stream.bpf_pc + ins->jt] - 319 stream.refs[stream.bpf_pc] + 5 ); 320 JMP(stream.refs[stream.bpf_pc + ins->jf] - 321 stream.refs[stream.bpf_pc]); 322 break; 323 324 case BPF_JMP|BPF_JGE|BPF_K: 325 CMPid(ins->k, EAX); 326 JGE(stream.refs[stream.bpf_pc + ins->jt] - 327 stream.refs[stream.bpf_pc] + 5); 328 JMP(stream.refs[stream.bpf_pc + ins->jf] - 329 stream.refs[stream.bpf_pc]); 330 break; 331 332 case BPF_JMP|BPF_JEQ|BPF_K: 333 CMPid(ins->k, EAX); 334 JE(stream.refs[stream.bpf_pc + ins->jt] - 335 stream.refs[stream.bpf_pc] + 5); 336 JMP(stream.refs[stream.bpf_pc + ins->jf] - 337 stream.refs[stream.bpf_pc]); 338 break; 339 340 case BPF_JMP|BPF_JSET|BPF_K: 341 MOVrd(EAX, ECX); 342 ANDid(ins->k, ECX); 343 JE(stream.refs[stream.bpf_pc + ins->jf] - 344 stream.refs[stream.bpf_pc] + 5); 345 JMP(stream.refs[stream.bpf_pc + ins->jt] - 346 stream.refs[stream.bpf_pc]); 347 break; 348 349 case BPF_JMP|BPF_JGT|BPF_X: 350 CMPrd(EDX, EAX); 351 JA(stream.refs[stream.bpf_pc + ins->jt] - 352 stream.refs[stream.bpf_pc] + 5); 353 JMP(stream.refs[stream.bpf_pc + ins->jf] - 354 stream.refs[stream.bpf_pc]); 355 break; 356 357 case BPF_JMP|BPF_JGE|BPF_X: 358 CMPrd(EDX, EAX); 359 JAE(stream.refs[stream.bpf_pc + ins->jt] - 360 stream.refs[stream.bpf_pc] + 5); 361 JMP(stream.refs[stream.bpf_pc + ins->jf] - 362 stream.refs[stream.bpf_pc]); 363 break; 364 365 case BPF_JMP|BPF_JEQ|BPF_X: 366 CMPrd(EDX, EAX); 367 JE(stream.refs[stream.bpf_pc + ins->jt] - 368 stream.refs[stream.bpf_pc] + 5); 369 JMP(stream.refs[stream.bpf_pc + ins->jf] - 370 stream.refs[stream.bpf_pc]); 371 break; 372 373 case BPF_JMP|BPF_JSET|BPF_X: 374 MOVrd(EAX, ECX); 375 ANDrd(EDX, ECX); 376 JE(stream.refs[stream.bpf_pc + ins->jf] - 377 stream.refs[stream.bpf_pc] + 5); 378 JMP(stream.refs[stream.bpf_pc + ins->jt] - 379 stream.refs[stream.bpf_pc]); 380 break; 381 382 case BPF_ALU|BPF_ADD|BPF_X: 383 ADDrd(EDX, EAX); 384 break; 385 386 case BPF_ALU|BPF_SUB|BPF_X: 387 SUBrd(EDX, EAX); 388 break; 389 390 case BPF_ALU|BPF_MUL|BPF_X: 391 MOVrd(EDX, ECX); 392 MULrd(EDX); 393 MOVrd(ECX, EDX); 394 break; 395 396 case BPF_ALU|BPF_DIV|BPF_X: 397 CMPid(0, EDX); 398 JNEb(7); 399 ZEROrd(EAX); 400 POP(EBX); 401 POP(ESI); 402 POP(EDI); 403 LEAVE_RET(); 404 MOVrd(EDX, ECX); 405 ZEROrd(EDX); 406 DIVrd(ECX); 407 MOVrd(ECX, EDX); 408 break; 409 410 case BPF_ALU|BPF_AND|BPF_X: 411 ANDrd(EDX, EAX); 412 break; 413 414 case BPF_ALU|BPF_OR|BPF_X: 415 ORrd(EDX, EAX); 416 break; 417 418 case BPF_ALU|BPF_LSH|BPF_X: 419 MOVrd(EDX, ECX); 420 SHL_CLrb(EAX); 421 break; 422 423 case BPF_ALU|BPF_RSH|BPF_X: 424 MOVrd(EDX, ECX); 425 SHR_CLrb(EAX); 426 break; 427 428 case BPF_ALU|BPF_ADD|BPF_K: 429 ADD_EAXi(ins->k); 430 break; 431 432 case BPF_ALU|BPF_SUB|BPF_K: 433 SUB_EAXi(ins->k); 434 break; 435 436 case BPF_ALU|BPF_MUL|BPF_K: 437 MOVrd(EDX, ECX); 438 MOVid(ins->k, EDX); 439 MULrd(EDX); 440 MOVrd(ECX, EDX); 441 break; 442 443 case BPF_ALU|BPF_DIV|BPF_K: 444 MOVrd(EDX, ECX); 445 ZEROrd(EDX); 446 MOVid(ins->k, ESI); 447 DIVrd(ESI); 448 MOVrd(ECX, EDX); 449 break; 450 451 case BPF_ALU|BPF_AND|BPF_K: 452 ANDid(ins->k, EAX); 453 break; 454 455 case BPF_ALU|BPF_OR|BPF_K: 456 ORid(ins->k, EAX); 457 break; 458 459 case BPF_ALU|BPF_LSH|BPF_K: 460 SHLib((ins->k) & 0xff, EAX); 461 break; 462 463 case BPF_ALU|BPF_RSH|BPF_K: 464 SHRib((ins->k) & 0xff, EAX); 465 break; 466 467 case BPF_ALU|BPF_NEG: 468 NEGd(EAX); 469 break; 470 471 case BPF_MISC|BPF_TAX: 472 MOVrd(EAX, EDX); 473 break; 474 475 case BPF_MISC|BPF_TXA: 476 MOVrd(EDX, EAX); 477 break; 478 } 479 ins++; 480 } 481 482 pass++; 483 if (pass == 2) 484 break; 485 486 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 487 if (stream.ibuf == NULL) { 488 free(stream.refs, M_BPFJIT); 489 return NULL; 490 } 491 492 /* 493 * modify the reference table to contain the offsets and 494 * not the lengths of the instructions 495 */ 496 for (i = 1; i < nins + 1; i++) 497 stream.refs[i] += stream.refs[i - 1]; 498 499 /* Reset the counters */ 500 stream.cur_ip = 0; 501 stream.bpf_pc = 0; 502 503 /* the second pass creates the actual code */ 504 emitm = emit_code; 505 } 506 507 /* 508 * the reference table is needed only during compilation, 509 * now we can free it 510 */ 511 free(stream.refs, M_BPFJIT); 512 513 return (bpf_filter_func)stream.ibuf; 514} 515