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