bpf_jit_machdep.c revision 199603
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 199603 2009-11-20 18:49:20Z 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, size_t *); 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, size_t *size) 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 = malloc((nins + 1) * sizeof(u_int), M_BPFJIT, M_NOWAIT); 115#else 116 stream.refs = malloc((nins + 1) * sizeof(u_int)); 117#endif 118 if (stream.refs == NULL) 119 return (NULL); 120 121 /* Reset the reference table */ 122 for (i = 0; i < nins + 1; i++) 123 stream.refs[i] = 0; 124 125 stream.cur_ip = 0; 126 stream.bpf_pc = 0; 127 128 /* 129 * the first pass will emit the lengths of the instructions 130 * to create the reference table 131 */ 132 emitm = emit_length; 133 134 pass = 0; 135 for (;;) { 136 ins = prog; 137 138 /* create the procedure header */ 139 PUSH(EBP); 140 MOVrd(ESP, EBP); 141 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP); 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 MOVrd(EBP, ECX); 314 MOVid(((int)ins->k - BPF_MEMWORDS) * 315 sizeof(uint32_t), ESI); 316 MOVobd(ECX, ESI, EAX); 317 break; 318 319 case BPF_LDX|BPF_MEM: 320 MOVrd(EBP, ECX); 321 MOVid(((int)ins->k - BPF_MEMWORDS) * 322 sizeof(uint32_t), 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 MOVrd(EBP, ECX); 333 MOVid(((int)ins->k - BPF_MEMWORDS) * 334 sizeof(uint32_t), ESI); 335 MOVomd(EAX, ECX, ESI); 336 break; 337 338 case BPF_STX: 339 MOVrd(EBP, ECX); 340 MOVid(((int)ins->k - BPF_MEMWORDS) * 341 sizeof(uint32_t), ESI); 342 MOVomd(EDX, ECX, ESI); 343 break; 344 345 case BPF_JMP|BPF_JA: 346 JMP(stream.refs[stream.bpf_pc + ins->k] - 347 stream.refs[stream.bpf_pc]); 348 break; 349 350 case BPF_JMP|BPF_JGT|BPF_K: 351 if (ins->jt == 0 && ins->jf == 0) 352 break; 353 CMPid(ins->k, EAX); 354 JCC(JA, JBE); 355 break; 356 357 case BPF_JMP|BPF_JGE|BPF_K: 358 if (ins->jt == 0 && ins->jf == 0) 359 break; 360 CMPid(ins->k, EAX); 361 JCC(JAE, JB); 362 break; 363 364 case BPF_JMP|BPF_JEQ|BPF_K: 365 if (ins->jt == 0 && ins->jf == 0) 366 break; 367 CMPid(ins->k, EAX); 368 JCC(JE, JNE); 369 break; 370 371 case BPF_JMP|BPF_JSET|BPF_K: 372 if (ins->jt == 0 && ins->jf == 0) 373 break; 374 TESTid(ins->k, EAX); 375 JCC(JNE, JE); 376 break; 377 378 case BPF_JMP|BPF_JGT|BPF_X: 379 if (ins->jt == 0 && ins->jf == 0) 380 break; 381 CMPrd(EDX, EAX); 382 JCC(JA, JBE); 383 break; 384 385 case BPF_JMP|BPF_JGE|BPF_X: 386 if (ins->jt == 0 && ins->jf == 0) 387 break; 388 CMPrd(EDX, EAX); 389 JCC(JAE, JB); 390 break; 391 392 case BPF_JMP|BPF_JEQ|BPF_X: 393 if (ins->jt == 0 && ins->jf == 0) 394 break; 395 CMPrd(EDX, EAX); 396 JCC(JE, JNE); 397 break; 398 399 case BPF_JMP|BPF_JSET|BPF_X: 400 if (ins->jt == 0 && ins->jf == 0) 401 break; 402 TESTrd(EDX, EAX); 403 JCC(JNE, JE); 404 break; 405 406 case BPF_ALU|BPF_ADD|BPF_X: 407 ADDrd(EDX, EAX); 408 break; 409 410 case BPF_ALU|BPF_SUB|BPF_X: 411 SUBrd(EDX, EAX); 412 break; 413 414 case BPF_ALU|BPF_MUL|BPF_X: 415 MOVrd(EDX, ECX); 416 MULrd(EDX); 417 MOVrd(ECX, EDX); 418 break; 419 420 case BPF_ALU|BPF_DIV|BPF_X: 421 TESTrd(EDX, EDX); 422 JNEb(7); 423 ZEROrd(EAX); 424 POP(EBX); 425 POP(ESI); 426 POP(EDI); 427 LEAVE_RET(); 428 MOVrd(EDX, ECX); 429 ZEROrd(EDX); 430 DIVrd(ECX); 431 MOVrd(ECX, EDX); 432 break; 433 434 case BPF_ALU|BPF_AND|BPF_X: 435 ANDrd(EDX, EAX); 436 break; 437 438 case BPF_ALU|BPF_OR|BPF_X: 439 ORrd(EDX, EAX); 440 break; 441 442 case BPF_ALU|BPF_LSH|BPF_X: 443 MOVrd(EDX, ECX); 444 SHL_CLrb(EAX); 445 break; 446 447 case BPF_ALU|BPF_RSH|BPF_X: 448 MOVrd(EDX, ECX); 449 SHR_CLrb(EAX); 450 break; 451 452 case BPF_ALU|BPF_ADD|BPF_K: 453 ADD_EAXi(ins->k); 454 break; 455 456 case BPF_ALU|BPF_SUB|BPF_K: 457 SUB_EAXi(ins->k); 458 break; 459 460 case BPF_ALU|BPF_MUL|BPF_K: 461 MOVrd(EDX, ECX); 462 MOVid(ins->k, EDX); 463 MULrd(EDX); 464 MOVrd(ECX, EDX); 465 break; 466 467 case BPF_ALU|BPF_DIV|BPF_K: 468 MOVrd(EDX, ECX); 469 ZEROrd(EDX); 470 MOVid(ins->k, ESI); 471 DIVrd(ESI); 472 MOVrd(ECX, EDX); 473 break; 474 475 case BPF_ALU|BPF_AND|BPF_K: 476 ANDid(ins->k, EAX); 477 break; 478 479 case BPF_ALU|BPF_OR|BPF_K: 480 ORid(ins->k, EAX); 481 break; 482 483 case BPF_ALU|BPF_LSH|BPF_K: 484 SHLib((ins->k) & 0xff, EAX); 485 break; 486 487 case BPF_ALU|BPF_RSH|BPF_K: 488 SHRib((ins->k) & 0xff, EAX); 489 break; 490 491 case BPF_ALU|BPF_NEG: 492 NEGd(EAX); 493 break; 494 495 case BPF_MISC|BPF_TAX: 496 MOVrd(EAX, EDX); 497 break; 498 499 case BPF_MISC|BPF_TXA: 500 MOVrd(EDX, EAX); 501 break; 502 } 503 ins++; 504 } 505 506 pass++; 507 if (pass >= 2) { 508#ifndef _KERNEL 509 if (mprotect(stream.ibuf, stream.cur_ip, 510 PROT_READ | PROT_EXEC) != 0) { 511 munmap(stream.ibuf, stream.cur_ip); 512 stream.ibuf = NULL; 513 } 514#endif 515 *size = stream.cur_ip; 516 break; 517 } 518 519#ifdef _KERNEL 520 stream.ibuf = malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 521 if (stream.ibuf == NULL) 522 break; 523#else 524 stream.ibuf = mmap(NULL, stream.cur_ip, PROT_READ | PROT_WRITE, 525 MAP_ANON, -1, 0); 526 if (stream.ibuf == MAP_FAILED) { 527 stream.ibuf = NULL; 528 break; 529 } 530#endif 531 532 /* 533 * modify the reference table to contain the offsets and 534 * not the lengths of the instructions 535 */ 536 for (i = 1; i < nins + 1; i++) 537 stream.refs[i] += stream.refs[i - 1]; 538 539 /* Reset the counters */ 540 stream.cur_ip = 0; 541 stream.bpf_pc = 0; 542 543 /* the second pass creates the actual code */ 544 emitm = emit_code; 545 } 546 547 /* 548 * the reference table is needed only during compilation, 549 * now we can free it 550 */ 551#ifdef _KERNEL 552 free(stream.refs, M_BPFJIT); 553#else 554 free(stream.refs); 555#endif 556 557 return ((bpf_filter_func)stream.ibuf); 558} 559