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