1 /*-
2 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
3 * Copyright (C) 2005-2008 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 #endif
46
47 #include <sys/types.h>
48
49 #include <net/bpf.h>
50 #include <net/bpf_jitter.h>
51
52 #include <i386/i386/bpf_jit_machdep.h>
53
54 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, int *);
55
56 /*
57 * emit routine to update the jump table
58 */
59 static void
60 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
61 {
62
63 (stream->refs)[stream->bpf_pc] += len;
64 stream->cur_ip += len;
65 }
66
67 /*
68 * emit routine to output the actual binary code
69 */
70 static void
71 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
72 {
73
74 switch (len) {
75 case 1:
76 stream->ibuf[stream->cur_ip] = (u_char)value;
77 stream->cur_ip++;
78 break;
79
80 case 2:
81 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
82 stream->cur_ip += 2;
83 break;
84
85 case 4:
86 *((u_int *)(stream->ibuf + stream->cur_ip)) = value;
87 stream->cur_ip += 4;
88 break;
89 }
90
91 return;
92 }
93
94 /*
95 * Function that does the real stuff
96 */
97 bpf_filter_func
98 bpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem)
99 {
100 struct bpf_insn *ins;
101 u_int i, pass;
102 bpf_bin_stream stream;
103
104 /*
105 * NOTE: do not modify the name of this variable, as it's used by
106 * the macros to emit code.
107 */
108 emit_func emitm;
109
110 /* Allocate the reference table for the jumps */
111 #ifdef _KERNEL
112 stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int),
113 M_BPFJIT, M_NOWAIT);
114 #else
115 stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int));
116 #endif
117 if (stream.refs == NULL)
118 return (NULL);
119
120 /* Reset the reference table */
121 for (i = 0; i < nins + 1; i++)
122 stream.refs[i] = 0;
123
124 stream.cur_ip = 0;
125 stream.bpf_pc = 0;
126
127 /*
128 * the first pass will emit the lengths of the instructions
129 * to create the reference table
130 */
131 emitm = emit_length;
132
133 pass = 0;
134 for (;;) {
135 ins = prog;
136
137 /* create the procedure header */
138 PUSH(EBP);
139 MOVrd(ESP, EBP);
140 PUSH(EDI);
141 PUSH(ESI);
142 PUSH(EBX);
143 MOVodd(8, EBP, EBX);
144 MOVodd(16, EBP, EDI);
145
146 for (i = 0; i < nins; i++) {
147 stream.bpf_pc++;
148
149 switch (ins->code) {
150 default:
151 #ifdef _KERNEL
152 return (NULL);
153 #else
154 abort();
155 #endif
156
157 case BPF_RET|BPF_K:
158 MOVid(ins->k, EAX);
159 POP(EBX);
160 POP(ESI);
161 POP(EDI);
162 LEAVE_RET();
163 break;
164
165 case BPF_RET|BPF_A:
166 POP(EBX);
167 POP(ESI);
168 POP(EDI);
169 LEAVE_RET();
170 break;
171
172 case BPF_LD|BPF_W|BPF_ABS:
173 MOVid(ins->k, ESI);
174 CMPrd(EDI, ESI);
175 JAb(12);
176 MOVrd(EDI, ECX);
177 SUBrd(ESI, ECX);
178 CMPid(sizeof(int32_t), ECX);
179 JAEb(7);
180 ZEROrd(EAX);
181 POP(EBX);
182 POP(ESI);
183 POP(EDI);
184 LEAVE_RET();
185 MOVobd(EBX, ESI, EAX);
186 BSWAP(EAX);
187 break;
188
189 case BPF_LD|BPF_H|BPF_ABS:
190 ZEROrd(EAX);
191 MOVid(ins->k, ESI);
192 CMPrd(EDI, ESI);
193 JAb(12);
194 MOVrd(EDI, ECX);
195 SUBrd(ESI, ECX);
196 CMPid(sizeof(int16_t), ECX);
197 JAEb(5);
198 POP(EBX);
199 POP(ESI);
200 POP(EDI);
201 LEAVE_RET();
202 MOVobw(EBX, ESI, AX);
203 SWAP_AX();
204 break;
205
206 case BPF_LD|BPF_B|BPF_ABS:
207 ZEROrd(EAX);
208 MOVid(ins->k, ESI);
209 CMPrd(EDI, ESI);
210 JBb(5);
211 POP(EBX);
212 POP(ESI);
213 POP(EDI);
214 LEAVE_RET();
215 MOVobb(EBX, ESI, AL);
216 break;
217
218 case BPF_LD|BPF_W|BPF_LEN:
219 MOVodd(12, EBP, EAX);
220 break;
221
222 case BPF_LDX|BPF_W|BPF_LEN:
223 MOVodd(12, EBP, EDX);
224 break;
225
226 case BPF_LD|BPF_W|BPF_IND:
227 CMPrd(EDI, EDX);
228 JAb(27);
229 MOVid(ins->k, ESI);
230 MOVrd(EDI, ECX);
231 SUBrd(EDX, ECX);
232 CMPrd(ESI, ECX);
233 JBb(14);
234 ADDrd(EDX, ESI);
235 MOVrd(EDI, ECX);
236 SUBrd(ESI, ECX);
237 CMPid(sizeof(int32_t), ECX);
238 JAEb(7);
239 ZEROrd(EAX);
240 POP(EBX);
241 POP(ESI);
242 POP(EDI);
243 LEAVE_RET();
244 MOVobd(EBX, ESI, EAX);
245 BSWAP(EAX);
246 break;
247
248 case BPF_LD|BPF_H|BPF_IND:
249 ZEROrd(EAX);
250 CMPrd(EDI, EDX);
251 JAb(27);
252 MOVid(ins->k, ESI);
253 MOVrd(EDI, ECX);
254 SUBrd(EDX, ECX);
255 CMPrd(ESI, ECX);
256 JBb(14);
257 ADDrd(EDX, ESI);
258 MOVrd(EDI, ECX);
259 SUBrd(ESI, ECX);
260 CMPid(sizeof(int16_t), ECX);
261 JAEb(5);
262 POP(EBX);
263 POP(ESI);
264 POP(EDI);
265 LEAVE_RET();
266 MOVobw(EBX, ESI, AX);
267 SWAP_AX();
268 break;
269
270 case BPF_LD|BPF_B|BPF_IND:
271 ZEROrd(EAX);
272 CMPrd(EDI, EDX);
273 JAEb(13);
274 MOVid(ins->k, ESI);
275 MOVrd(EDI, ECX);
276 SUBrd(EDX, ECX);
277 CMPrd(ESI, ECX);
278 JAb(5);
279 POP(EBX);
280 POP(ESI);
281 POP(EDI);
282 LEAVE_RET();
283 ADDrd(EDX, ESI);
284 MOVobb(EBX, ESI, AL);
285 break;
286
287 case BPF_LDX|BPF_MSH|BPF_B:
288 MOVid(ins->k, ESI);
289 CMPrd(EDI, ESI);
290 JBb(7);
291 ZEROrd(EAX);
292 POP(EBX);
293 POP(ESI);
294 POP(EDI);
295 LEAVE_RET();
296 ZEROrd(EDX);
297 MOVobb(EBX, ESI, DL);
298 ANDib(0x0f, DL);
299 SHLib(2, EDX);
300 break;
301
302 case BPF_LD|BPF_IMM:
303 MOVid(ins->k, EAX);
304 break;
305
306 case BPF_LDX|BPF_IMM:
307 MOVid(ins->k, EDX);
308 break;
309
310 case BPF_LD|BPF_MEM:
311 MOVid((uintptr_t)mem, ECX);
312 MOVid(ins->k * 4, ESI);
313 MOVobd(ECX, ESI, EAX);
314 break;
315
316 case BPF_LDX|BPF_MEM:
317 MOVid((uintptr_t)mem, ECX);
318 MOVid(ins->k * 4, ESI);
319 MOVobd(ECX, ESI, EDX);
320 break;
321
322 case BPF_ST:
323 /*
324 * XXX this command and the following could
325 * be optimized if the previous instruction
326 * was already of this type
327 */
328 MOVid((uintptr_t)mem, ECX);
329 MOVid(ins->k * 4, ESI);
330 MOVomd(EAX, ECX, ESI);
331 break;
332
333 case BPF_STX:
334 MOVid((uintptr_t)mem, ECX);
335 MOVid(ins->k * 4, ESI);
336 MOVomd(EDX, ECX, ESI);
337 break;
338
339 case BPF_JMP|BPF_JA:
340 JMP(stream.refs[stream.bpf_pc + ins->k] -
341 stream.refs[stream.bpf_pc]);
342 break;
343
344 case BPF_JMP|BPF_JGT|BPF_K:
345 if (ins->jt == 0 && ins->jf == 0)
346 break;
347 CMPid(ins->k, EAX);
348 JCC(JA, JBE);
349 break;
350
351 case BPF_JMP|BPF_JGE|BPF_K:
352 if (ins->jt == 0 && ins->jf == 0)
353 break;
354 CMPid(ins->k, EAX);
355 JCC(JAE, JB);
356 break;
357
358 case BPF_JMP|BPF_JEQ|BPF_K:
359 if (ins->jt == 0 && ins->jf == 0)
360 break;
361 CMPid(ins->k, EAX);
362 JCC(JE, JNE);
363 break;
364
365 case BPF_JMP|BPF_JSET|BPF_K:
366 if (ins->jt == 0 && ins->jf == 0)
367 break;
368 TESTid(ins->k, EAX);
369 JCC(JNE, JE);
370 break;
371
372 case BPF_JMP|BPF_JGT|BPF_X:
373 if (ins->jt == 0 && ins->jf == 0)
374 break;
375 CMPrd(EDX, EAX);
376 JCC(JA, JBE);
377 break;
378
379 case BPF_JMP|BPF_JGE|BPF_X:
380 if (ins->jt == 0 && ins->jf == 0)
381 break;
382 CMPrd(EDX, EAX);
383 JCC(JAE, JB);
384 break;
385
386 case BPF_JMP|BPF_JEQ|BPF_X:
387 if (ins->jt == 0 && ins->jf == 0)
388 break;
389 CMPrd(EDX, EAX);
390 JCC(JE, JNE);
391 break;
392
393 case BPF_JMP|BPF_JSET|BPF_X:
394 if (ins->jt == 0 && ins->jf == 0)
395 break;
396 TESTrd(EDX, EAX);
397 JCC(JNE, JE);
398 break;
399
400 case BPF_ALU|BPF_ADD|BPF_X:
401 ADDrd(EDX, EAX);
402 break;
403
404 case BPF_ALU|BPF_SUB|BPF_X:
405 SUBrd(EDX, EAX);
406 break;
407
408 case BPF_ALU|BPF_MUL|BPF_X:
409 MOVrd(EDX, ECX);
410 MULrd(EDX);
411 MOVrd(ECX, EDX);
412 break;
413
414 case BPF_ALU|BPF_DIV|BPF_X:
415 TESTrd(EDX, EDX);
416 JNEb(7);
417 ZEROrd(EAX);
418 POP(EBX);
419 POP(ESI);
420 POP(EDI);
421 LEAVE_RET();
422 MOVrd(EDX, ECX);
423 ZEROrd(EDX);
424 DIVrd(ECX);
425 MOVrd(ECX, EDX);
426 break;
427
428 case BPF_ALU|BPF_AND|BPF_X:
429 ANDrd(EDX, EAX);
430 break;
431
432 case BPF_ALU|BPF_OR|BPF_X:
433 ORrd(EDX, EAX);
434 break;
435
436 case BPF_ALU|BPF_LSH|BPF_X:
437 MOVrd(EDX, ECX);
438 SHL_CLrb(EAX);
439 break;
440
441 case BPF_ALU|BPF_RSH|BPF_X:
442 MOVrd(EDX, ECX);
443 SHR_CLrb(EAX);
444 break;
445
446 case BPF_ALU|BPF_ADD|BPF_K:
447 ADD_EAXi(ins->k);
448 break;
449
450 case BPF_ALU|BPF_SUB|BPF_K:
451 SUB_EAXi(ins->k);
452 break;
453
454 case BPF_ALU|BPF_MUL|BPF_K:
455 MOVrd(EDX, ECX);
456 MOVid(ins->k, EDX);
457 MULrd(EDX);
458 MOVrd(ECX, EDX);
459 break;
460
461 case BPF_ALU|BPF_DIV|BPF_K:
462 MOVrd(EDX, ECX);
463 ZEROrd(EDX);
464 MOVid(ins->k, ESI);
465 DIVrd(ESI);
466 MOVrd(ECX, EDX);
467 break;
468
469 case BPF_ALU|BPF_AND|BPF_K:
470 ANDid(ins->k, EAX);
471 break;
472
473 case BPF_ALU|BPF_OR|BPF_K:
474 ORid(ins->k, EAX);
475 break;
476
477 case BPF_ALU|BPF_LSH|BPF_K:
478 SHLib((ins->k) & 0xff, EAX);
479 break;
480
481 case BPF_ALU|BPF_RSH|BPF_K:
482 SHRib((ins->k) & 0xff, EAX);
483 break;
484
485 case BPF_ALU|BPF_NEG:
486 NEGd(EAX);
487 break;
488
489 case BPF_MISC|BPF_TAX:
490 MOVrd(EAX, EDX);
491 break;
492
493 case BPF_MISC|BPF_TXA:
494 MOVrd(EDX, EAX);
495 break;
496 }
497 ins++;
498 }
499
500 pass++;
501 if (pass == 2)
502 break;
503
504 #ifdef _KERNEL
505 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT);
506 if (stream.ibuf == NULL) {
507 free(stream.refs, M_BPFJIT);
508 return (NULL);
509 }
510 #else
511 stream.ibuf = (char *)malloc(stream.cur_ip);
512 if (stream.ibuf == NULL) {
513 free(stream.refs);
514 return (NULL);
515 }
516 #endif
517
518 /*
519 * modify the reference table to contain the offsets and
520 * not the lengths of the instructions
521 */
522 for (i = 1; i < nins + 1; i++)
523 stream.refs[i] += stream.refs[i - 1];
524
525 /* Reset the counters */
526 stream.cur_ip = 0;
527 stream.bpf_pc = 0;
528
529 /* the second pass creates the actual code */
530 emitm = emit_code;
531 }
532
533 /*
534 * the reference table is needed only during compilation,
535 * now we can free it
536 */
537 #ifdef _KERNEL
538 free(stream.refs, M_BPFJIT);
539 #else
540 free(stream.refs);
541 #endif
542
543 return ((bpf_filter_func)stream.ibuf);
544 }
Cache object: 5f87dc0438dcc4e72a50afe525b6360b
|