1 /*-
2 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
3 * Copyright (C) 2005-2009 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: releng/9.1/sys/i386/i386/bpf_jit_machdep.c 207081 2010-04-22 23:47:19Z 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 #include <string.h>
46 #include <sys/mman.h>
47 #include <sys/param.h>
48 #endif
49
50 #include <sys/types.h>
51
52 #include <net/bpf.h>
53 #include <net/bpf_jitter.h>
54
55 #include <i386/i386/bpf_jit_machdep.h>
56
57 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *);
58
59 /*
60 * Emit routine to update the jump table.
61 */
62 static void
63 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
64 {
65
66 if (stream->refs != NULL)
67 (stream->refs)[stream->bpf_pc] += len;
68 stream->cur_ip += len;
69 }
70
71 /*
72 * Emit routine to output the actual binary code.
73 */
74 static void
75 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
76 {
77
78 switch (len) {
79 case 1:
80 stream->ibuf[stream->cur_ip] = (u_char)value;
81 stream->cur_ip++;
82 break;
83
84 case 2:
85 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
86 stream->cur_ip += 2;
87 break;
88
89 case 4:
90 *((u_int *)(stream->ibuf + stream->cur_ip)) = value;
91 stream->cur_ip += 4;
92 break;
93 }
94
95 return;
96 }
97
98 /*
99 * Scan the filter program and find possible optimization.
100 */
101 static int
102 bpf_jit_optimize(struct bpf_insn *prog, u_int nins)
103 {
104 int flags;
105 u_int i;
106
107 /* Do we return immediately? */
108 if (BPF_CLASS(prog[0].code) == BPF_RET)
109 return (BPF_JIT_FRET);
110
111 for (flags = 0, i = 0; i < nins; i++) {
112 switch (prog[i].code) {
113 case BPF_LD|BPF_W|BPF_ABS:
114 case BPF_LD|BPF_H|BPF_ABS:
115 case BPF_LD|BPF_B|BPF_ABS:
116 case BPF_LD|BPF_W|BPF_IND:
117 case BPF_LD|BPF_H|BPF_IND:
118 case BPF_LD|BPF_B|BPF_IND:
119 case BPF_LDX|BPF_MSH|BPF_B:
120 flags |= BPF_JIT_FPKT;
121 break;
122 case BPF_LD|BPF_MEM:
123 case BPF_LDX|BPF_MEM:
124 case BPF_ST:
125 case BPF_STX:
126 flags |= BPF_JIT_FMEM;
127 break;
128 case BPF_JMP|BPF_JA:
129 case BPF_JMP|BPF_JGT|BPF_K:
130 case BPF_JMP|BPF_JGE|BPF_K:
131 case BPF_JMP|BPF_JEQ|BPF_K:
132 case BPF_JMP|BPF_JSET|BPF_K:
133 case BPF_JMP|BPF_JGT|BPF_X:
134 case BPF_JMP|BPF_JGE|BPF_X:
135 case BPF_JMP|BPF_JEQ|BPF_X:
136 case BPF_JMP|BPF_JSET|BPF_X:
137 flags |= BPF_JIT_FJMP;
138 break;
139 case BPF_ALU|BPF_DIV|BPF_K:
140 flags |= BPF_JIT_FADK;
141 break;
142 }
143 if (flags == BPF_JIT_FLAG_ALL)
144 break;
145 }
146
147 return (flags);
148 }
149
150 /*
151 * Function that does the real stuff.
152 */
153 bpf_filter_func
154 bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size)
155 {
156 bpf_bin_stream stream;
157 struct bpf_insn *ins;
158 int flags, fret, fpkt, fmem, fjmp, fadk;
159 int save_esp;
160 u_int i, pass;
161
162 /*
163 * NOTE: Do not modify the name of this variable, as it's used by
164 * the macros to emit code.
165 */
166 emit_func emitm;
167
168 flags = bpf_jit_optimize(prog, nins);
169 fret = (flags & BPF_JIT_FRET) != 0;
170 fpkt = (flags & BPF_JIT_FPKT) != 0;
171 fmem = (flags & BPF_JIT_FMEM) != 0;
172 fjmp = (flags & BPF_JIT_FJMP) != 0;
173 fadk = (flags & BPF_JIT_FADK) != 0;
174 save_esp = (fpkt || fmem || fadk); /* Stack is used. */
175
176 if (fret)
177 nins = 1;
178
179 memset(&stream, 0, sizeof(stream));
180
181 /* Allocate the reference table for the jumps. */
182 if (fjmp) {
183 #ifdef _KERNEL
184 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
185 M_NOWAIT | M_ZERO);
186 #else
187 stream.refs = calloc(nins + 1, sizeof(u_int));
188 #endif
189 if (stream.refs == NULL)
190 return (NULL);
191 }
192
193 /*
194 * The first pass will emit the lengths of the instructions
195 * to create the reference table.
196 */
197 emitm = emit_length;
198
199 for (pass = 0; pass < 2; pass++) {
200 ins = prog;
201
202 /* Create the procedure header. */
203 if (save_esp) {
204 PUSH(EBP);
205 MOVrd(ESP, EBP);
206 }
207 if (fmem)
208 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP);
209 if (save_esp)
210 PUSH(ESI);
211 if (fpkt) {
212 PUSH(EDI);
213 PUSH(EBX);
214 MOVodd(8, EBP, EBX);
215 MOVodd(16, EBP, EDI);
216 }
217
218 for (i = 0; i < nins; i++) {
219 stream.bpf_pc++;
220
221 switch (ins->code) {
222 default:
223 #ifdef _KERNEL
224 return (NULL);
225 #else
226 abort();
227 #endif
228
229 case BPF_RET|BPF_K:
230 MOVid(ins->k, EAX);
231 if (save_esp) {
232 if (fpkt) {
233 POP(EBX);
234 POP(EDI);
235 }
236 POP(ESI);
237 LEAVE();
238 }
239 RET();
240 break;
241
242 case BPF_RET|BPF_A:
243 if (save_esp) {
244 if (fpkt) {
245 POP(EBX);
246 POP(EDI);
247 }
248 POP(ESI);
249 LEAVE();
250 }
251 RET();
252 break;
253
254 case BPF_LD|BPF_W|BPF_ABS:
255 MOVid(ins->k, ESI);
256 CMPrd(EDI, ESI);
257 JAb(12);
258 MOVrd(EDI, ECX);
259 SUBrd(ESI, ECX);
260 CMPid(sizeof(int32_t), ECX);
261 JAEb(7);
262 ZEROrd(EAX);
263 POP(EBX);
264 POP(EDI);
265 POP(ESI);
266 LEAVE();
267 RET();
268 MOVobd(EBX, ESI, EAX);
269 BSWAP(EAX);
270 break;
271
272 case BPF_LD|BPF_H|BPF_ABS:
273 ZEROrd(EAX);
274 MOVid(ins->k, ESI);
275 CMPrd(EDI, ESI);
276 JAb(12);
277 MOVrd(EDI, ECX);
278 SUBrd(ESI, ECX);
279 CMPid(sizeof(int16_t), ECX);
280 JAEb(5);
281 POP(EBX);
282 POP(EDI);
283 POP(ESI);
284 LEAVE();
285 RET();
286 MOVobw(EBX, ESI, AX);
287 SWAP_AX();
288 break;
289
290 case BPF_LD|BPF_B|BPF_ABS:
291 ZEROrd(EAX);
292 MOVid(ins->k, ESI);
293 CMPrd(EDI, ESI);
294 JBb(5);
295 POP(EBX);
296 POP(EDI);
297 POP(ESI);
298 LEAVE();
299 RET();
300 MOVobb(EBX, ESI, AL);
301 break;
302
303 case BPF_LD|BPF_W|BPF_LEN:
304 if (save_esp)
305 MOVodd(12, EBP, EAX);
306 else {
307 MOVrd(ESP, ECX);
308 MOVodd(12, ECX, EAX);
309 }
310 break;
311
312 case BPF_LDX|BPF_W|BPF_LEN:
313 if (save_esp)
314 MOVodd(12, EBP, EDX);
315 else {
316 MOVrd(ESP, ECX);
317 MOVodd(12, ECX, EDX);
318 }
319 break;
320
321 case BPF_LD|BPF_W|BPF_IND:
322 CMPrd(EDI, EDX);
323 JAb(27);
324 MOVid(ins->k, ESI);
325 MOVrd(EDI, ECX);
326 SUBrd(EDX, ECX);
327 CMPrd(ESI, ECX);
328 JBb(14);
329 ADDrd(EDX, ESI);
330 MOVrd(EDI, ECX);
331 SUBrd(ESI, ECX);
332 CMPid(sizeof(int32_t), ECX);
333 JAEb(7);
334 ZEROrd(EAX);
335 POP(EBX);
336 POP(EDI);
337 POP(ESI);
338 LEAVE();
339 RET();
340 MOVobd(EBX, ESI, EAX);
341 BSWAP(EAX);
342 break;
343
344 case BPF_LD|BPF_H|BPF_IND:
345 ZEROrd(EAX);
346 CMPrd(EDI, EDX);
347 JAb(27);
348 MOVid(ins->k, ESI);
349 MOVrd(EDI, ECX);
350 SUBrd(EDX, ECX);
351 CMPrd(ESI, ECX);
352 JBb(14);
353 ADDrd(EDX, ESI);
354 MOVrd(EDI, ECX);
355 SUBrd(ESI, ECX);
356 CMPid(sizeof(int16_t), ECX);
357 JAEb(5);
358 POP(EBX);
359 POP(EDI);
360 POP(ESI);
361 LEAVE();
362 RET();
363 MOVobw(EBX, ESI, AX);
364 SWAP_AX();
365 break;
366
367 case BPF_LD|BPF_B|BPF_IND:
368 ZEROrd(EAX);
369 CMPrd(EDI, EDX);
370 JAEb(13);
371 MOVid(ins->k, ESI);
372 MOVrd(EDI, ECX);
373 SUBrd(EDX, ECX);
374 CMPrd(ESI, ECX);
375 JAb(5);
376 POP(EBX);
377 POP(EDI);
378 POP(ESI);
379 LEAVE();
380 RET();
381 ADDrd(EDX, ESI);
382 MOVobb(EBX, ESI, AL);
383 break;
384
385 case BPF_LDX|BPF_MSH|BPF_B:
386 MOVid(ins->k, ESI);
387 CMPrd(EDI, ESI);
388 JBb(7);
389 ZEROrd(EAX);
390 POP(EBX);
391 POP(EDI);
392 POP(ESI);
393 LEAVE();
394 RET();
395 ZEROrd(EDX);
396 MOVobb(EBX, ESI, DL);
397 ANDib(0x0f, DL);
398 SHLib(2, EDX);
399 break;
400
401 case BPF_LD|BPF_IMM:
402 MOVid(ins->k, EAX);
403 break;
404
405 case BPF_LDX|BPF_IMM:
406 MOVid(ins->k, EDX);
407 break;
408
409 case BPF_LD|BPF_MEM:
410 MOVrd(EBP, ECX);
411 MOVid(((int)ins->k - BPF_MEMWORDS) *
412 sizeof(uint32_t), ESI);
413 MOVobd(ECX, ESI, EAX);
414 break;
415
416 case BPF_LDX|BPF_MEM:
417 MOVrd(EBP, ECX);
418 MOVid(((int)ins->k - BPF_MEMWORDS) *
419 sizeof(uint32_t), ESI);
420 MOVobd(ECX, ESI, EDX);
421 break;
422
423 case BPF_ST:
424 /*
425 * XXX this command and the following could
426 * be optimized if the previous instruction
427 * was already of this type
428 */
429 MOVrd(EBP, ECX);
430 MOVid(((int)ins->k - BPF_MEMWORDS) *
431 sizeof(uint32_t), ESI);
432 MOVomd(EAX, ECX, ESI);
433 break;
434
435 case BPF_STX:
436 MOVrd(EBP, ECX);
437 MOVid(((int)ins->k - BPF_MEMWORDS) *
438 sizeof(uint32_t), ESI);
439 MOVomd(EDX, ECX, ESI);
440 break;
441
442 case BPF_JMP|BPF_JA:
443 JUMP(ins->k);
444 break;
445
446 case BPF_JMP|BPF_JGT|BPF_K:
447 if (ins->jt == ins->jf) {
448 JUMP(ins->jt);
449 break;
450 }
451 CMPid(ins->k, EAX);
452 JCC(JA, JBE);
453 break;
454
455 case BPF_JMP|BPF_JGE|BPF_K:
456 if (ins->jt == ins->jf) {
457 JUMP(ins->jt);
458 break;
459 }
460 CMPid(ins->k, EAX);
461 JCC(JAE, JB);
462 break;
463
464 case BPF_JMP|BPF_JEQ|BPF_K:
465 if (ins->jt == ins->jf) {
466 JUMP(ins->jt);
467 break;
468 }
469 CMPid(ins->k, EAX);
470 JCC(JE, JNE);
471 break;
472
473 case BPF_JMP|BPF_JSET|BPF_K:
474 if (ins->jt == ins->jf) {
475 JUMP(ins->jt);
476 break;
477 }
478 TESTid(ins->k, EAX);
479 JCC(JNE, JE);
480 break;
481
482 case BPF_JMP|BPF_JGT|BPF_X:
483 if (ins->jt == ins->jf) {
484 JUMP(ins->jt);
485 break;
486 }
487 CMPrd(EDX, EAX);
488 JCC(JA, JBE);
489 break;
490
491 case BPF_JMP|BPF_JGE|BPF_X:
492 if (ins->jt == ins->jf) {
493 JUMP(ins->jt);
494 break;
495 }
496 CMPrd(EDX, EAX);
497 JCC(JAE, JB);
498 break;
499
500 case BPF_JMP|BPF_JEQ|BPF_X:
501 if (ins->jt == ins->jf) {
502 JUMP(ins->jt);
503 break;
504 }
505 CMPrd(EDX, EAX);
506 JCC(JE, JNE);
507 break;
508
509 case BPF_JMP|BPF_JSET|BPF_X:
510 if (ins->jt == ins->jf) {
511 JUMP(ins->jt);
512 break;
513 }
514 TESTrd(EDX, EAX);
515 JCC(JNE, JE);
516 break;
517
518 case BPF_ALU|BPF_ADD|BPF_X:
519 ADDrd(EDX, EAX);
520 break;
521
522 case BPF_ALU|BPF_SUB|BPF_X:
523 SUBrd(EDX, EAX);
524 break;
525
526 case BPF_ALU|BPF_MUL|BPF_X:
527 MOVrd(EDX, ECX);
528 MULrd(EDX);
529 MOVrd(ECX, EDX);
530 break;
531
532 case BPF_ALU|BPF_DIV|BPF_X:
533 TESTrd(EDX, EDX);
534 if (save_esp) {
535 if (fpkt) {
536 JNEb(7);
537 ZEROrd(EAX);
538 POP(EBX);
539 POP(EDI);
540 } else {
541 JNEb(5);
542 ZEROrd(EAX);
543 }
544 POP(ESI);
545 LEAVE();
546 } else {
547 JNEb(3);
548 ZEROrd(EAX);
549 }
550 RET();
551 MOVrd(EDX, ECX);
552 ZEROrd(EDX);
553 DIVrd(ECX);
554 MOVrd(ECX, EDX);
555 break;
556
557 case BPF_ALU|BPF_AND|BPF_X:
558 ANDrd(EDX, EAX);
559 break;
560
561 case BPF_ALU|BPF_OR|BPF_X:
562 ORrd(EDX, EAX);
563 break;
564
565 case BPF_ALU|BPF_LSH|BPF_X:
566 MOVrd(EDX, ECX);
567 SHL_CLrb(EAX);
568 break;
569
570 case BPF_ALU|BPF_RSH|BPF_X:
571 MOVrd(EDX, ECX);
572 SHR_CLrb(EAX);
573 break;
574
575 case BPF_ALU|BPF_ADD|BPF_K:
576 ADD_EAXi(ins->k);
577 break;
578
579 case BPF_ALU|BPF_SUB|BPF_K:
580 SUB_EAXi(ins->k);
581 break;
582
583 case BPF_ALU|BPF_MUL|BPF_K:
584 MOVrd(EDX, ECX);
585 MOVid(ins->k, EDX);
586 MULrd(EDX);
587 MOVrd(ECX, EDX);
588 break;
589
590 case BPF_ALU|BPF_DIV|BPF_K:
591 MOVrd(EDX, ECX);
592 ZEROrd(EDX);
593 MOVid(ins->k, ESI);
594 DIVrd(ESI);
595 MOVrd(ECX, EDX);
596 break;
597
598 case BPF_ALU|BPF_AND|BPF_K:
599 ANDid(ins->k, EAX);
600 break;
601
602 case BPF_ALU|BPF_OR|BPF_K:
603 ORid(ins->k, EAX);
604 break;
605
606 case BPF_ALU|BPF_LSH|BPF_K:
607 SHLib((ins->k) & 0xff, EAX);
608 break;
609
610 case BPF_ALU|BPF_RSH|BPF_K:
611 SHRib((ins->k) & 0xff, EAX);
612 break;
613
614 case BPF_ALU|BPF_NEG:
615 NEGd(EAX);
616 break;
617
618 case BPF_MISC|BPF_TAX:
619 MOVrd(EAX, EDX);
620 break;
621
622 case BPF_MISC|BPF_TXA:
623 MOVrd(EDX, EAX);
624 break;
625 }
626 ins++;
627 }
628
629 if (pass > 0)
630 continue;
631
632 *size = stream.cur_ip;
633 #ifdef _KERNEL
634 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT);
635 if (stream.ibuf == NULL)
636 break;
637 #else
638 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
639 MAP_ANON, -1, 0);
640 if (stream.ibuf == MAP_FAILED) {
641 stream.ibuf = NULL;
642 break;
643 }
644 #endif
645
646 /*
647 * Modify the reference table to contain the offsets and
648 * not the lengths of the instructions.
649 */
650 if (fjmp)
651 for (i = 1; i < nins + 1; i++)
652 stream.refs[i] += stream.refs[i - 1];
653
654 /* Reset the counters. */
655 stream.cur_ip = 0;
656 stream.bpf_pc = 0;
657
658 /* The second pass creates the actual code. */
659 emitm = emit_code;
660 }
661
662 /*
663 * The reference table is needed only during compilation,
664 * now we can free it.
665 */
666 if (fjmp)
667 #ifdef _KERNEL
668 free(stream.refs, M_BPFJIT);
669 #else
670 free(stream.refs);
671 #endif
672
673 #ifndef _KERNEL
674 if (stream.ibuf != NULL &&
675 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
676 munmap(stream.ibuf, *size);
677 stream.ibuf = NULL;
678 }
679 #endif
680
681 return ((bpf_filter_func)stream.ibuf);
682 }
Cache object: a69c2adf2b25b4bef0b3d290f24eeb78
|