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