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