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