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