bpf_jit_machdep.c revision 181853
1/*- 2 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy) 3 * Copyright (C) 2005-2008 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 181853 2008-08-18 21:17:47Z jkim $"); 34 35#ifdef _KERNEL 36#include "opt_bpf.h" 37#include <sys/param.h> 38#include <sys/systm.h> 39#include <sys/kernel.h> 40#include <sys/socket.h> 41#include <sys/malloc.h> 42#include <net/if.h> 43#else 44#include <stdlib.h> 45#endif 46 47#include <sys/types.h> 48 49#include <net/bpf.h> 50#include <net/bpf_jitter.h> 51 52#include <i386/i386/bpf_jit_machdep.h> 53 54bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, int *); 55 56/* 57 * emit routine to update the jump table 58 */ 59static void 60emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len) 61{ 62 63 (stream->refs)[stream->bpf_pc] += len; 64 stream->cur_ip += len; 65} 66 67/* 68 * emit routine to output the actual binary code 69 */ 70static void 71emit_code(bpf_bin_stream *stream, u_int value, u_int len) 72{ 73 74 switch (len) { 75 case 1: 76 stream->ibuf[stream->cur_ip] = (u_char)value; 77 stream->cur_ip++; 78 break; 79 80 case 2: 81 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 82 stream->cur_ip += 2; 83 break; 84 85 case 4: 86 *((u_int *)(stream->ibuf + stream->cur_ip)) = value; 87 stream->cur_ip += 4; 88 break; 89 } 90 91 return; 92} 93 94/* 95 * Function that does the real stuff 96 */ 97bpf_filter_func 98bpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem) 99{ 100 struct bpf_insn *ins; 101 u_int i, pass; 102 bpf_bin_stream stream; 103 104 /* 105 * NOTE: do not modify the name of this variable, as it's used by 106 * the macros to emit code. 107 */ 108 emit_func emitm; 109 110 /* Do not compile an empty filter. */ 111 if (nins == 0) 112 return (NULL); 113 114 /* Allocate the reference table for the jumps */ 115#ifdef _KERNEL 116 stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int), 117 M_BPFJIT, M_NOWAIT); 118#else 119 stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int)); 120#endif 121 if (stream.refs == NULL) 122 return (NULL); 123 124 /* Reset the reference table */ 125 for (i = 0; i < nins + 1; i++) 126 stream.refs[i] = 0; 127 128 stream.cur_ip = 0; 129 stream.bpf_pc = 0; 130 131 /* 132 * the first pass will emit the lengths of the instructions 133 * to create the reference table 134 */ 135 emitm = emit_length; 136 137 pass = 0; 138 for (;;) { 139 ins = prog; 140 141 /* create the procedure header */ 142 PUSH(EBP); 143 MOVrd(ESP, EBP); 144 PUSH(EDI); 145 PUSH(ESI); 146 PUSH(EBX); 147 MOVodd(8, EBP, EBX); 148 MOVodd(16, EBP, EDI); 149 150 for (i = 0; i < nins; i++) { 151 stream.bpf_pc++; 152 153 switch (ins->code) { 154 default: 155#ifdef _KERNEL 156 return (NULL); 157#else 158 abort(); 159#endif 160 161 case BPF_RET|BPF_K: 162 MOVid(ins->k, EAX); 163 POP(EBX); 164 POP(ESI); 165 POP(EDI); 166 LEAVE_RET(); 167 break; 168 169 case BPF_RET|BPF_A: 170 POP(EBX); 171 POP(ESI); 172 POP(EDI); 173 LEAVE_RET(); 174 break; 175 176 case BPF_LD|BPF_W|BPF_ABS: 177 MOVid(ins->k, ESI); 178 CMPrd(EDI, ESI); 179 JAb(12); 180 MOVrd(EDI, ECX); 181 SUBrd(ESI, ECX); 182 CMPid(sizeof(int32_t), ECX); 183 JAEb(7); 184 ZEROrd(EAX); 185 POP(EBX); 186 POP(ESI); 187 POP(EDI); 188 LEAVE_RET(); 189 MOVobd(EBX, ESI, EAX); 190 BSWAP(EAX); 191 break; 192 193 case BPF_LD|BPF_H|BPF_ABS: 194 ZEROrd(EAX); 195 MOVid(ins->k, ESI); 196 CMPrd(EDI, ESI); 197 JAb(12); 198 MOVrd(EDI, ECX); 199 SUBrd(ESI, ECX); 200 CMPid(sizeof(int16_t), ECX); 201 JAEb(5); 202 POP(EBX); 203 POP(ESI); 204 POP(EDI); 205 LEAVE_RET(); 206 MOVobw(EBX, ESI, AX); 207 SWAP_AX(); 208 break; 209 210 case BPF_LD|BPF_B|BPF_ABS: 211 ZEROrd(EAX); 212 MOVid(ins->k, ESI); 213 CMPrd(EDI, ESI); 214 JBb(5); 215 POP(EBX); 216 POP(ESI); 217 POP(EDI); 218 LEAVE_RET(); 219 MOVobb(EBX, ESI, AL); 220 break; 221 222 case BPF_LD|BPF_W|BPF_LEN: 223 MOVodd(12, EBP, EAX); 224 break; 225 226 case BPF_LDX|BPF_W|BPF_LEN: 227 MOVodd(12, EBP, EDX); 228 break; 229 230 case BPF_LD|BPF_W|BPF_IND: 231 CMPrd(EDI, EDX); 232 JAb(27); 233 MOVid(ins->k, ESI); 234 MOVrd(EDI, ECX); 235 SUBrd(EDX, ECX); 236 CMPrd(ESI, ECX); 237 JBb(14); 238 ADDrd(EDX, ESI); 239 MOVrd(EDI, ECX); 240 SUBrd(ESI, ECX); 241 CMPid(sizeof(int32_t), ECX); 242 JAEb(7); 243 ZEROrd(EAX); 244 POP(EBX); 245 POP(ESI); 246 POP(EDI); 247 LEAVE_RET(); 248 MOVobd(EBX, ESI, EAX); 249 BSWAP(EAX); 250 break; 251 252 case BPF_LD|BPF_H|BPF_IND: 253 ZEROrd(EAX); 254 CMPrd(EDI, EDX); 255 JAb(27); 256 MOVid(ins->k, ESI); 257 MOVrd(EDI, ECX); 258 SUBrd(EDX, ECX); 259 CMPrd(ESI, ECX); 260 JBb(14); 261 ADDrd(EDX, ESI); 262 MOVrd(EDI, ECX); 263 SUBrd(ESI, ECX); 264 CMPid(sizeof(int16_t), ECX); 265 JAEb(5); 266 POP(EBX); 267 POP(ESI); 268 POP(EDI); 269 LEAVE_RET(); 270 MOVobw(EBX, ESI, AX); 271 SWAP_AX(); 272 break; 273 274 case BPF_LD|BPF_B|BPF_IND: 275 ZEROrd(EAX); 276 CMPrd(EDI, EDX); 277 JAEb(13); 278 MOVid(ins->k, ESI); 279 MOVrd(EDI, ECX); 280 SUBrd(EDX, ECX); 281 CMPrd(ESI, ECX); 282 JAb(5); 283 POP(EBX); 284 POP(ESI); 285 POP(EDI); 286 LEAVE_RET(); 287 ADDrd(EDX, ESI); 288 MOVobb(EBX, ESI, AL); 289 break; 290 291 case BPF_LDX|BPF_MSH|BPF_B: 292 MOVid(ins->k, ESI); 293 CMPrd(EDI, ESI); 294 JBb(7); 295 ZEROrd(EAX); 296 POP(EBX); 297 POP(ESI); 298 POP(EDI); 299 LEAVE_RET(); 300 ZEROrd(EDX); 301 MOVobb(EBX, ESI, DL); 302 ANDib(0x0f, DL); 303 SHLib(2, EDX); 304 break; 305 306 case BPF_LD|BPF_IMM: 307 MOVid(ins->k, EAX); 308 break; 309 310 case BPF_LDX|BPF_IMM: 311 MOVid(ins->k, EDX); 312 break; 313 314 case BPF_LD|BPF_MEM: 315 MOVid((uintptr_t)mem, ECX); 316 MOVid(ins->k * 4, ESI); 317 MOVobd(ECX, ESI, EAX); 318 break; 319 320 case BPF_LDX|BPF_MEM: 321 MOVid((uintptr_t)mem, ECX); 322 MOVid(ins->k * 4, ESI); 323 MOVobd(ECX, ESI, EDX); 324 break; 325 326 case BPF_ST: 327 /* 328 * XXX this command and the following could 329 * be optimized if the previous instruction 330 * was already of this type 331 */ 332 MOVid((uintptr_t)mem, ECX); 333 MOVid(ins->k * 4, ESI); 334 MOVomd(EAX, ECX, ESI); 335 break; 336 337 case BPF_STX: 338 MOVid((uintptr_t)mem, ECX); 339 MOVid(ins->k * 4, ESI); 340 MOVomd(EDX, ECX, ESI); 341 break; 342 343 case BPF_JMP|BPF_JA: 344 JMP(stream.refs[stream.bpf_pc + ins->k] - 345 stream.refs[stream.bpf_pc]); 346 break; 347 348 case BPF_JMP|BPF_JGT|BPF_K: 349 if (ins->jt == 0 && ins->jf == 0) 350 break; 351 CMPid(ins->k, EAX); 352 JCC(JA, JBE); 353 break; 354 355 case BPF_JMP|BPF_JGE|BPF_K: 356 if (ins->jt == 0 && ins->jf == 0) 357 break; 358 CMPid(ins->k, EAX); 359 JCC(JAE, JB); 360 break; 361 362 case BPF_JMP|BPF_JEQ|BPF_K: 363 if (ins->jt == 0 && ins->jf == 0) 364 break; 365 CMPid(ins->k, EAX); 366 JCC(JE, JNE); 367 break; 368 369 case BPF_JMP|BPF_JSET|BPF_K: 370 if (ins->jt == 0 && ins->jf == 0) 371 break; 372 TESTid(ins->k, EAX); 373 JCC(JNE, JE); 374 break; 375 376 case BPF_JMP|BPF_JGT|BPF_X: 377 if (ins->jt == 0 && ins->jf == 0) 378 break; 379 CMPrd(EDX, EAX); 380 JCC(JA, JBE); 381 break; 382 383 case BPF_JMP|BPF_JGE|BPF_X: 384 if (ins->jt == 0 && ins->jf == 0) 385 break; 386 CMPrd(EDX, EAX); 387 JCC(JAE, JB); 388 break; 389 390 case BPF_JMP|BPF_JEQ|BPF_X: 391 if (ins->jt == 0 && ins->jf == 0) 392 break; 393 CMPrd(EDX, EAX); 394 JCC(JE, JNE); 395 break; 396 397 case BPF_JMP|BPF_JSET|BPF_X: 398 if (ins->jt == 0 && ins->jf == 0) 399 break; 400 TESTrd(EDX, EAX); 401 JCC(JNE, JE); 402 break; 403 404 case BPF_ALU|BPF_ADD|BPF_X: 405 ADDrd(EDX, EAX); 406 break; 407 408 case BPF_ALU|BPF_SUB|BPF_X: 409 SUBrd(EDX, EAX); 410 break; 411 412 case BPF_ALU|BPF_MUL|BPF_X: 413 MOVrd(EDX, ECX); 414 MULrd(EDX); 415 MOVrd(ECX, EDX); 416 break; 417 418 case BPF_ALU|BPF_DIV|BPF_X: 419 TESTrd(EDX, EDX); 420 JNEb(7); 421 ZEROrd(EAX); 422 POP(EBX); 423 POP(ESI); 424 POP(EDI); 425 LEAVE_RET(); 426 MOVrd(EDX, ECX); 427 ZEROrd(EDX); 428 DIVrd(ECX); 429 MOVrd(ECX, EDX); 430 break; 431 432 case BPF_ALU|BPF_AND|BPF_X: 433 ANDrd(EDX, EAX); 434 break; 435 436 case BPF_ALU|BPF_OR|BPF_X: 437 ORrd(EDX, EAX); 438 break; 439 440 case BPF_ALU|BPF_LSH|BPF_X: 441 MOVrd(EDX, ECX); 442 SHL_CLrb(EAX); 443 break; 444 445 case BPF_ALU|BPF_RSH|BPF_X: 446 MOVrd(EDX, ECX); 447 SHR_CLrb(EAX); 448 break; 449 450 case BPF_ALU|BPF_ADD|BPF_K: 451 ADD_EAXi(ins->k); 452 break; 453 454 case BPF_ALU|BPF_SUB|BPF_K: 455 SUB_EAXi(ins->k); 456 break; 457 458 case BPF_ALU|BPF_MUL|BPF_K: 459 MOVrd(EDX, ECX); 460 MOVid(ins->k, EDX); 461 MULrd(EDX); 462 MOVrd(ECX, EDX); 463 break; 464 465 case BPF_ALU|BPF_DIV|BPF_K: 466 MOVrd(EDX, ECX); 467 ZEROrd(EDX); 468 MOVid(ins->k, ESI); 469 DIVrd(ESI); 470 MOVrd(ECX, EDX); 471 break; 472 473 case BPF_ALU|BPF_AND|BPF_K: 474 ANDid(ins->k, EAX); 475 break; 476 477 case BPF_ALU|BPF_OR|BPF_K: 478 ORid(ins->k, EAX); 479 break; 480 481 case BPF_ALU|BPF_LSH|BPF_K: 482 SHLib((ins->k) & 0xff, EAX); 483 break; 484 485 case BPF_ALU|BPF_RSH|BPF_K: 486 SHRib((ins->k) & 0xff, EAX); 487 break; 488 489 case BPF_ALU|BPF_NEG: 490 NEGd(EAX); 491 break; 492 493 case BPF_MISC|BPF_TAX: 494 MOVrd(EAX, EDX); 495 break; 496 497 case BPF_MISC|BPF_TXA: 498 MOVrd(EDX, EAX); 499 break; 500 } 501 ins++; 502 } 503 504 pass++; 505 if (pass == 2) 506 break; 507 508#ifdef _KERNEL 509 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 510 if (stream.ibuf == NULL) { 511 free(stream.refs, M_BPFJIT); 512 return (NULL); 513 } 514#else 515 stream.ibuf = (char *)malloc(stream.cur_ip); 516 if (stream.ibuf == NULL) { 517 free(stream.refs); 518 return (NULL); 519 } 520#endif 521 522 /* 523 * modify the reference table to contain the offsets and 524 * not the lengths of the instructions 525 */ 526 for (i = 1; i < nins + 1; i++) 527 stream.refs[i] += stream.refs[i - 1]; 528 529 /* Reset the counters */ 530 stream.cur_ip = 0; 531 stream.bpf_pc = 0; 532 533 /* the second pass creates the actual code */ 534 emitm = emit_code; 535 } 536 537 /* 538 * the reference table is needed only during compilation, 539 * now we can free it 540 */ 541#ifdef _KERNEL 542 free(stream.refs, M_BPFJIT); 543#else 544 free(stream.refs); 545#endif 546 547 return ((bpf_filter_func)stream.ibuf); 548} 549