bpf_jit_machdep.c revision 181697
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 181697 2008-08-13 19:25:09Z 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 JBEb(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 JBEb(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 JBEb(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 JBEb(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 JBEb(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 JBEb(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 JBEb(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 if (ins->jt == 0 && ins->jf == 0) 318 break; 319 CMPid(ins->k, EAX); 320 JCC(JA, JBE); 321 break; 322 323 case BPF_JMP|BPF_JGE|BPF_K: 324 if (ins->jt == 0 && ins->jf == 0) 325 break; 326 CMPid(ins->k, EAX); 327 JCC(JAE, JB); 328 break; 329 330 case BPF_JMP|BPF_JEQ|BPF_K: 331 if (ins->jt == 0 && ins->jf == 0) 332 break; 333 CMPid(ins->k, EAX); 334 JCC(JE, JNE); 335 break; 336 337 case BPF_JMP|BPF_JSET|BPF_K: 338 if (ins->jt == 0 && ins->jf == 0) 339 break; 340 TESTid(ins->k, EAX); 341 JCC(JNE, JE); 342 break; 343 344 case BPF_JMP|BPF_JGT|BPF_X: 345 if (ins->jt == 0 && ins->jf == 0) 346 break; 347 CMPrd(EDX, EAX); 348 JCC(JA, JBE); 349 break; 350 351 case BPF_JMP|BPF_JGE|BPF_X: 352 if (ins->jt == 0 && ins->jf == 0) 353 break; 354 CMPrd(EDX, EAX); 355 JCC(JAE, JB); 356 break; 357 358 case BPF_JMP|BPF_JEQ|BPF_X: 359 if (ins->jt == 0 && ins->jf == 0) 360 break; 361 CMPrd(EDX, EAX); 362 JCC(JE, JNE); 363 break; 364 365 case BPF_JMP|BPF_JSET|BPF_X: 366 if (ins->jt == 0 && ins->jf == 0) 367 break; 368 TESTrd(EDX, EAX); 369 JCC(JNE, JE); 370 break; 371 372 case BPF_ALU|BPF_ADD|BPF_X: 373 ADDrd(EDX, EAX); 374 break; 375 376 case BPF_ALU|BPF_SUB|BPF_X: 377 SUBrd(EDX, EAX); 378 break; 379 380 case BPF_ALU|BPF_MUL|BPF_X: 381 MOVrd(EDX, ECX); 382 MULrd(EDX); 383 MOVrd(ECX, EDX); 384 break; 385 386 case BPF_ALU|BPF_DIV|BPF_X: 387 TESTrd(EDX, EDX); 388 JNEb(7); 389 ZEROrd(EAX); 390 POP(EBX); 391 POP(ESI); 392 POP(EDI); 393 LEAVE_RET(); 394 MOVrd(EDX, ECX); 395 ZEROrd(EDX); 396 DIVrd(ECX); 397 MOVrd(ECX, EDX); 398 break; 399 400 case BPF_ALU|BPF_AND|BPF_X: 401 ANDrd(EDX, EAX); 402 break; 403 404 case BPF_ALU|BPF_OR|BPF_X: 405 ORrd(EDX, EAX); 406 break; 407 408 case BPF_ALU|BPF_LSH|BPF_X: 409 MOVrd(EDX, ECX); 410 SHL_CLrb(EAX); 411 break; 412 413 case BPF_ALU|BPF_RSH|BPF_X: 414 MOVrd(EDX, ECX); 415 SHR_CLrb(EAX); 416 break; 417 418 case BPF_ALU|BPF_ADD|BPF_K: 419 ADD_EAXi(ins->k); 420 break; 421 422 case BPF_ALU|BPF_SUB|BPF_K: 423 SUB_EAXi(ins->k); 424 break; 425 426 case BPF_ALU|BPF_MUL|BPF_K: 427 MOVrd(EDX, ECX); 428 MOVid(ins->k, EDX); 429 MULrd(EDX); 430 MOVrd(ECX, EDX); 431 break; 432 433 case BPF_ALU|BPF_DIV|BPF_K: 434 MOVrd(EDX, ECX); 435 ZEROrd(EDX); 436 MOVid(ins->k, ESI); 437 DIVrd(ESI); 438 MOVrd(ECX, EDX); 439 break; 440 441 case BPF_ALU|BPF_AND|BPF_K: 442 ANDid(ins->k, EAX); 443 break; 444 445 case BPF_ALU|BPF_OR|BPF_K: 446 ORid(ins->k, EAX); 447 break; 448 449 case BPF_ALU|BPF_LSH|BPF_K: 450 SHLib((ins->k) & 0xff, EAX); 451 break; 452 453 case BPF_ALU|BPF_RSH|BPF_K: 454 SHRib((ins->k) & 0xff, EAX); 455 break; 456 457 case BPF_ALU|BPF_NEG: 458 NEGd(EAX); 459 break; 460 461 case BPF_MISC|BPF_TAX: 462 MOVrd(EAX, EDX); 463 break; 464 465 case BPF_MISC|BPF_TXA: 466 MOVrd(EDX, EAX); 467 break; 468 } 469 ins++; 470 } 471 472 pass++; 473 if (pass == 2) 474 break; 475 476 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 477 if (stream.ibuf == NULL) { 478 free(stream.refs, M_BPFJIT); 479 return (NULL); 480 } 481 482 /* 483 * modify the reference table to contain the offsets and 484 * not the lengths of the instructions 485 */ 486 for (i = 1; i < nins + 1; i++) 487 stream.refs[i] += stream.refs[i - 1]; 488 489 /* Reset the counters */ 490 stream.cur_ip = 0; 491 stream.bpf_pc = 0; 492 493 /* the second pass creates the actual code */ 494 emitm = emit_code; 495 } 496 497 /* 498 * the reference table is needed only during compilation, 499 * now we can free it 500 */ 501 free(stream.refs, M_BPFJIT); 502 503 return ((bpf_filter_func)stream.ibuf); 504} 505