docs: add todo's from Sibir's repo
[netsniff-ng.git] / src / bpf_parser.y
blob094ed8c916e37d53dcab9cdb111913ea9a2de0b4
1 /*
2 * netsniff-ng - the packet sniffing beast
3 * By Daniel Borkmann <daniel@netsniff-ng.org>
4 * Copyright 2011 Daniel Borkmann <dborkma@tik.ee.ethz.ch>,
5 * Swiss federal institute of technology (ETH Zurich)
6 * Subject to the GPL, version 2.
7 */
9 /* yaac-func-prefix: yy */
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <stdbool.h>
16 #include <signal.h>
17 #include <stdint.h>
18 #include <errno.h>
20 #include "bpf.h"
21 #include "xmalloc.h"
22 #include "bpf_parser.tab.h"
23 #include "built_in.h"
24 #include "die.h"
26 #define MAX_INSTRUCTIONS 4096
28 int compile_filter(char *file, int verbose, int bypass);
30 static int curr_instr = 0;
32 static struct sock_filter out[MAX_INSTRUCTIONS];
34 static char *labels[MAX_INSTRUCTIONS];
36 static char *labels_jt[MAX_INSTRUCTIONS];
37 static char *labels_jf[MAX_INSTRUCTIONS];
38 static char *labels_k[MAX_INSTRUCTIONS];
40 #define YYERROR_VERBOSE 0
41 #define YYDEBUG 0
42 #define YYENABLE_NLS 1
43 #define YYLTYPE_IS_TRIVIAL 1
44 #define ENABLE_NLS 1
46 extern FILE *yyin;
47 extern int yylex(void);
48 extern void yyerror(const char *);
49 extern int yylineno;
50 extern char *yytext;
52 static inline void set_curr_instr(uint16_t code, uint8_t jt, uint8_t jf, uint32_t k)
54 if (curr_instr >= MAX_INSTRUCTIONS)
55 panic("Exceeded maximal number of instructions!\n");
57 out[curr_instr].code = code;
58 out[curr_instr].jt = jt;
59 out[curr_instr].jf = jf;
60 out[curr_instr].k = k;
62 curr_instr++;
65 static inline void set_curr_label(char *label)
67 if (curr_instr >= MAX_INSTRUCTIONS)
68 panic("Exceeded maximal number of instructions!\n");
70 labels[curr_instr] = label;
73 #define JTL 1
74 #define JFL 2
75 #define JKL 3
77 static inline void set_jmp_label(char *label, int which)
79 if (curr_instr >= MAX_INSTRUCTIONS)
80 panic("Exceeded maximal number of instructions!\n");
82 bug_on(which != JTL && which != JFL && which != JKL);
84 if (which == JTL)
85 labels_jt[curr_instr] = label;
86 else if (which == JFL)
87 labels_jf[curr_instr] = label;
88 else
89 labels_k[curr_instr] = label;
92 static int find_intr_offset_or_panic(char *label_to_search)
94 int i, max = curr_instr, ret = -ENOENT;
96 bug_on(!label_to_search);
98 for (i = 0; i < max; ++i) {
99 if (labels[i] != NULL) {
100 /* Both are \0-terminated! */
101 if (!strcmp(label_to_search, labels[i])) {
102 ret = i;
103 break;
108 if (ret == -ENOENT)
109 panic("No such label!\n");
111 return ret;
116 %union {
117 char *label;
118 long int number;
121 %token OP_LDB OP_LDH OP_LD OP_LDX OP_ST OP_STX OP_JMP OP_JEQ OP_JGT OP_JGE
122 %token OP_JSET OP_ADD OP_SUB OP_MUL OP_DIV OP_AND OP_OR OP_XOR OP_LSH OP_RSH
123 %token OP_RET OP_TAX OP_TXA OP_LDXB OP_MOD OP_NEG K_PKT_LEN K_PROTO K_TYPE
124 %token K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE K_RXHASH K_CPU K_IFIDX
126 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#'
128 %token number_hex number_dec number_oct number_bin label
130 %type <number> number_hex number_dec number_oct number_bin number
131 %type <label> label
135 prog
136 : line
137 | prog line
140 line
141 : instr
142 | labeled_instr
145 labeled_instr
146 : do_label instr
149 instr
150 : do_ldb
151 | do_ldh
152 | do_ld
153 | do_ldx
154 | do_st
155 | do_stx
156 | do_jmp
157 | do_jeq
158 | do_jgt
159 | do_jge
160 | do_jset
161 | do_add
162 | do_sub
163 | do_mul
164 | do_div
165 | do_mod
166 | do_neg
167 | do_and
168 | do_or
169 | do_xor
170 | do_lsh
171 | do_rsh
172 | do_ret
173 | do_tax
174 | do_txa
177 number
178 : number_dec { $$ = $1; }
179 | number_hex { $$ = $1; }
180 | number_oct { $$ = $1; }
181 | number_bin { $$ = $1; }
184 do_label
185 : label ':' { set_curr_label($1); }
188 do_ldb
189 : OP_LDB '[' 'x' '+' number ']' {
190 set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $5); }
191 | OP_LDB '[' number ']' {
192 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, $3); }
193 | OP_LDB '#' K_PROTO {
194 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
195 SKF_AD_OFF + SKF_AD_PROTOCOL); }
196 | OP_LDB '#' K_TYPE {
197 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
198 SKF_AD_OFF + SKF_AD_PKTTYPE); }
199 | OP_LDB '#' K_IFIDX {
200 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
201 SKF_AD_OFF + SKF_AD_IFINDEX); }
202 | OP_LDB '#' K_NLATTR {
203 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
204 SKF_AD_OFF + SKF_AD_NLATTR); }
205 | OP_LDB '#' K_NLATTR_NEST {
206 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
207 SKF_AD_OFF + SKF_AD_NLATTR_NEST); }
208 | OP_LDB '#' K_MARK {
209 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
210 SKF_AD_OFF + SKF_AD_MARK); }
211 | OP_LDB '#' K_QUEUE {
212 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
213 SKF_AD_OFF + SKF_AD_QUEUE); }
214 | OP_LDB '#' K_HATYPE {
215 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
216 SKF_AD_OFF + SKF_AD_HATYPE); }
217 | OP_LDB '#' K_RXHASH {
218 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
219 SKF_AD_OFF + SKF_AD_RXHASH); }
220 | OP_LDB '#' K_CPU {
221 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
222 SKF_AD_OFF + SKF_AD_CPU); }
225 do_ldh
226 : OP_LDH '[' 'x' '+' number ']' {
227 set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $5); }
228 | OP_LDH '[' number ']' {
229 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, $3); }
230 | OP_LDH '#' K_PROTO {
231 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
232 SKF_AD_OFF + SKF_AD_PROTOCOL); }
233 | OP_LDH '#' K_TYPE {
234 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
235 SKF_AD_OFF + SKF_AD_PKTTYPE); }
236 | OP_LDH '#' K_IFIDX {
237 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
238 SKF_AD_OFF + SKF_AD_IFINDEX); }
239 | OP_LDH '#' K_NLATTR {
240 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
241 SKF_AD_OFF + SKF_AD_NLATTR); }
242 | OP_LDH '#' K_NLATTR_NEST {
243 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
244 SKF_AD_OFF + SKF_AD_NLATTR_NEST); }
245 | OP_LDH '#' K_MARK {
246 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
247 SKF_AD_OFF + SKF_AD_MARK); }
248 | OP_LDH '#' K_QUEUE {
249 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
250 SKF_AD_OFF + SKF_AD_QUEUE); }
251 | OP_LDH '#' K_HATYPE {
252 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
253 SKF_AD_OFF + SKF_AD_HATYPE); }
254 | OP_LDH '#' K_RXHASH {
255 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
256 SKF_AD_OFF + SKF_AD_RXHASH); }
257 | OP_LDH '#' K_CPU {
258 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
259 SKF_AD_OFF + SKF_AD_CPU); }
262 do_ld
263 : OP_LD '#' number {
264 set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
265 | OP_LD '#' K_PKT_LEN {
266 set_curr_instr(BPF_LD | BPF_W | BPF_LEN, 0, 0, 0); }
267 | OP_LD '#' K_PROTO {
268 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
269 SKF_AD_OFF + SKF_AD_PROTOCOL); }
270 | OP_LD '#' K_TYPE {
271 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
272 SKF_AD_OFF + SKF_AD_PKTTYPE); }
273 | OP_LD '#' K_IFIDX {
274 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
275 SKF_AD_OFF + SKF_AD_IFINDEX); }
276 | OP_LD '#' K_NLATTR {
277 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
278 SKF_AD_OFF + SKF_AD_NLATTR); }
279 | OP_LD '#' K_NLATTR_NEST {
280 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
281 SKF_AD_OFF + SKF_AD_NLATTR_NEST); }
282 | OP_LD '#' K_MARK {
283 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
284 SKF_AD_OFF + SKF_AD_MARK); }
285 | OP_LD '#' K_QUEUE {
286 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
287 SKF_AD_OFF + SKF_AD_QUEUE); }
288 | OP_LD '#' K_HATYPE {
289 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
290 SKF_AD_OFF + SKF_AD_HATYPE); }
291 | OP_LD '#' K_RXHASH {
292 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
293 SKF_AD_OFF + SKF_AD_RXHASH); }
294 | OP_LD '#' K_CPU {
295 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
296 SKF_AD_OFF + SKF_AD_CPU); }
297 | OP_LD 'M' '[' number ']' {
298 set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
299 | OP_LD '[' 'x' '+' number ']' {
300 set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $5); }
301 | OP_LD '[' number ']' {
302 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, $3); }
305 do_ldx
306 : OP_LDX '#' number {
307 set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
308 | OP_LDX 'M' '[' number ']' {
309 set_curr_instr(BPF_LDX | BPF_MEM, 0, 0, $4); }
310 | OP_LDXB number '*' '(' '[' number ']' '&' number ')' {
311 if ($2 != 4 || $9 != 0xf) {
312 panic("ldxb offset not supported!\n");
313 } else {
314 set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
315 | OP_LDX number '*' '(' '[' number ']' '&' number ')' {
316 if ($2 != 4 || $9 != 0xf) {
317 panic("ldxb offset not supported!\n");
318 } else {
319 set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
322 do_st
323 : OP_ST 'M' '[' number ']' {
324 set_curr_instr(BPF_ST, 0, 0, $4); }
327 do_stx
328 : OP_STX 'M' '[' number ']' {
329 set_curr_instr(BPF_STX, 0, 0, $4); }
332 do_jmp
333 : OP_JMP label {
334 set_jmp_label($2, JKL);
335 set_curr_instr(BPF_JMP | BPF_JA, 0, 0, 0); }
338 do_jeq
339 : OP_JEQ '#' number ',' label ',' label {
340 set_jmp_label($5, JTL);
341 set_jmp_label($7, JFL);
342 set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
343 | OP_JEQ 'x' ',' label ',' label {
344 set_jmp_label($4, JTL);
345 set_jmp_label($6, JFL);
346 set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
349 do_jgt
350 : OP_JGT '#' number ',' label ',' label {
351 set_jmp_label($5, JTL);
352 set_jmp_label($7, JFL);
353 set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
354 | OP_JGT 'x' ',' label ',' label {
355 set_jmp_label($4, JTL);
356 set_jmp_label($6, JFL);
357 set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
360 do_jge
361 : OP_JGE '#' number ',' label ',' label {
362 set_jmp_label($5, JTL);
363 set_jmp_label($7, JFL);
364 set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
365 | OP_JGE 'x' ',' label ',' label {
366 set_jmp_label($4, JTL);
367 set_jmp_label($6, JFL);
368 set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
371 do_jset
372 : OP_JSET '#' number ',' label ',' label {
373 set_jmp_label($5, JTL);
374 set_jmp_label($7, JFL);
375 set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
376 | OP_JSET 'x' ',' label ',' label {
377 set_jmp_label($4, JTL);
378 set_jmp_label($6, JFL);
379 set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
382 do_add
383 : OP_ADD '#' number {
384 set_curr_instr(BPF_ALU | BPF_ADD | BPF_K, 0, 0, $3); }
385 | OP_ADD 'x' {
386 set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
389 do_sub
390 : OP_SUB '#' number {
391 set_curr_instr(BPF_ALU | BPF_SUB | BPF_K, 0, 0, $3); }
392 | OP_SUB 'x' {
393 set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
396 do_mul
397 : OP_MUL '#' number {
398 set_curr_instr(BPF_ALU | BPF_MUL | BPF_K, 0, 0, $3); }
399 | OP_MUL 'x' {
400 set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
403 do_div
404 : OP_DIV '#' number {
405 set_curr_instr(BPF_ALU | BPF_DIV | BPF_K, 0, 0, $3); }
406 | OP_DIV 'x' {
407 set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
410 do_mod
411 : OP_MOD '#' number {
412 set_curr_instr(BPF_ALU | BPF_MOD | BPF_K, 0, 0, $3); }
413 | OP_MOD 'x' {
414 set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
417 do_neg
418 : OP_NEG {
419 set_curr_instr(BPF_ALU | BPF_NEG, 0, 0, 0); }
422 do_and
423 : OP_AND '#' number {
424 set_curr_instr(BPF_ALU | BPF_AND | BPF_K, 0, 0, $3); }
425 | OP_AND 'x' {
426 set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
429 do_or
430 : OP_OR '#' number {
431 set_curr_instr(BPF_ALU | BPF_OR | BPF_K, 0, 0, $3); }
432 | OP_OR 'x' {
433 set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
436 do_xor
437 : OP_XOR '#' number {
438 set_curr_instr(BPF_ALU | BPF_XOR | BPF_K, 0, 0, $3); }
439 | OP_XOR 'x' {
440 set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
443 do_lsh
444 : OP_LSH '#' number {
445 set_curr_instr(BPF_ALU | BPF_LSH | BPF_K, 0, 0, $3); }
446 | OP_LSH 'x' {
447 set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
450 do_rsh
451 : OP_RSH '#' number {
452 set_curr_instr(BPF_ALU | BPF_RSH | BPF_K, 0, 0, $3); }
453 | OP_RSH 'x' {
454 set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
457 do_ret
458 : OP_RET 'a' {
459 set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
460 | OP_RET '#' number {
461 set_curr_instr(BPF_RET | BPF_K, 0, 0, $3); }
464 do_tax
465 : OP_TAX {
466 set_curr_instr(BPF_MISC | BPF_TAX, 0, 0, 0); }
469 do_txa
470 : OP_TXA {
471 set_curr_instr(BPF_MISC | BPF_TXA, 0, 0, 0); }
476 static void stage_1_inline(void)
478 yyparse();
481 static void stage_2_label_reduce(void)
483 int i, max = curr_instr, off;
485 /* 1. reduce k jumps */
486 for (i = 0; i < max; ++i) {
487 if (labels_k[i] != NULL) {
488 off = find_intr_offset_or_panic(labels_k[i]);
489 out[i].k = (uint32_t) (off - i - 1);
493 /* 1. reduce jt jumps */
494 for (i = 0; i < max; ++i) {
495 if (labels_jt[i] != NULL) {
496 off = find_intr_offset_or_panic(labels_jt[i]);
497 out[i].jt = (uint8_t) (off - i -1);
501 /* 1. reduce jf jumps */
502 for (i = 0; i < max; ++i) {
503 if (labels_jf[i] != NULL) {
504 off = find_intr_offset_or_panic(labels_jf[i]);
505 out[i].jf = (uint8_t) (off - i - 1);
510 int compile_filter(char *file, int verbose, int bypass)
512 int i;
513 struct sock_fprog res;
515 if (!strncmp("-", file, strlen("-")))
516 yyin = stdin;
517 else
518 yyin = fopen(file, "r");
519 if (!yyin)
520 panic("Cannot open file!\n");
522 memset(out, 0, sizeof(out));
523 memset(labels, 0, sizeof(labels));
524 memset(labels_jf, 0, sizeof(labels_jf));
525 memset(labels_jt, 0, sizeof(labels_jt));
526 memset(labels_k, 0, sizeof(labels_k));
528 stage_1_inline();
529 stage_2_label_reduce();
531 res.filter = out;
532 res.len = curr_instr;
534 if (verbose) {
535 printf("Generated program:\n");
536 bpf_dump_all(&res);
539 if (!bypass) {
540 if (verbose) {
541 printf("Validating: ");
542 fflush(stdout);
545 if (bpf_validate(&res) == 0) {
546 if (verbose)
547 whine("Semantic error! BPF validation "
548 "failed!\n");
549 else
550 panic("Semantic error! BPF validation failed! "
551 "Try -V for debugging output!\n");
552 } else if (verbose) {
553 printf("is runnable!\n");
557 if (verbose)
558 printf("Result:\n");
559 for (i = 0; i < res.len; ++i) {
560 printf("{ 0x%x, %u, %u, 0x%08x },\n",
561 res.filter[i].code, res.filter[i].jt,
562 res.filter[i].jf, res.filter[i].k);
563 if (labels[i] != NULL)
564 xfree(labels[i]);
565 if (labels_jt[i] != NULL)
566 xfree(labels_jt[i]);
567 if (labels_jf[i] != NULL)
568 xfree(labels_jf[i]);
569 if (labels_k[i] != NULL)
570 xfree(labels_k[i]);
573 fclose(yyin);
574 return 0;
577 void yyerror(const char *err)
579 panic("Syntax error at line %d: %s! %s!\n",
580 yylineno, yytext, err);