]> CyberLeo.Net >> Repos - FreeBSD/releng/9.2.git/blob - sys/i386/i386/bpf_jit_machdep.c
- Copy stable/9 to releng/9.2 as part of the 9.2-RELEASE cycle.
[FreeBSD/releng/9.2.git] / sys / i386 / i386 / bpf_jit_machdep.c
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$");
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 }