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