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