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