src/bpf_parser.y

   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  */
   8
   9 %{
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <stdbool.h>
  14 #include <signal.h>
  15 #include <stdint.h>
  16 #include <errno.h>
  17 #include <assert.h>
  18
  19 #include "bpf.h"
  20 #include "xmalloc.h"
  21 #include "bpf_parser.tab.h"
  22 #include "compiler.h"
  23 #include "die.h"
  24
  25 #define MAX_INSTRUCTIONS        4096
  26
  27 int compile_filter(char *file, int verbose);
  28
  29 static int curr_instr = 0;
  30
  31 static struct sock_filter out[MAX_INSTRUCTIONS];
  32
  33 static char *labels[MAX_INSTRUCTIONS];
  34
  35 static char *labels_jt[MAX_INSTRUCTIONS];
  36 static char *labels_jf[MAX_INSTRUCTIONS];
  37 static char *labels_k[MAX_INSTRUCTIONS];
  38
  39 #define YYERROR_VERBOSE         0
  40 #define YYDEBUG                 0
  41 #define YYENABLE_NLS            1
  42 #define YYLTYPE_IS_TRIVIAL      1
  43 #define ENABLE_NLS              1
  44
  45 extern FILE *yyin;
  46 extern int yylex(void);
  47 extern void yyerror(const char *);
  48 extern int yylineno;
  49 extern char *yytext;
  50
  51 static inline void set_curr_instr(uint16_t code, uint8_t jt, uint8_t jf, uint32_t k)
  52 {
  53         if (curr_instr >= MAX_INSTRUCTIONS)
  54                 panic("Exceeded maximal number of instructions!\n");
  55         out[curr_instr].code = code;
  56         out[curr_instr].jt = jt;
  57         out[curr_instr].jf = jf;
  58         out[curr_instr].k = k;
  59         curr_instr++;
  60 }
  61
  62 static inline void set_curr_label(char *label)
  63 {
  64         if (curr_instr >= MAX_INSTRUCTIONS)
  65                 panic("Exceeded maximal number of instructions!\n");
  66         labels[curr_instr] = label;
  67 }
  68
  69 #define JTL 1
  70 #define JFL 2
  71 #define JKL 3
  72
  73 static inline void set_jmp_label(char *label, int which)
  74 {
  75         if (curr_instr >= MAX_INSTRUCTIONS)
  76                 panic("Exceeded maximal number of instructions!\n");
  77         assert(which == JTL || which == JFL || which == JKL);
  78         if (which == JTL)
  79                 labels_jt[curr_instr] = label;
  80         else if (which == JFL)
  81                 labels_jf[curr_instr] = label;
  82         else
  83                 labels_k[curr_instr] = label;
  84 }
  85
  86 static int find_intr_offset_or_panic(char *label_to_search)
  87 {
  88         int i, max = curr_instr, ret = -ENOENT;
  89
  90         assert(label_to_search);
  91         for (i = 0; i < max; ++i) {
  92                 if (labels[i] != NULL) {
  93                         /* Both are \0-terminated! */
  94                         if (!strcmp(label_to_search, labels[i])) {
  95                                 ret = i;
  96                                 break;
  97                         }
  98                 }
  99         }
 100         if (ret == -ENOENT)
 101                 panic("No such label!\n");
 102
 103         return ret;
 104 }
 105
 106 %}
 107
 108 %union {
 109         char *label;
 110         long int number;
 111 }
 112
 113 %token OP_LDB OP_LDH OP_LD OP_LDX OP_ST OP_STX OP_JMP OP_JEQ OP_JGT OP_JGE
 114 %token OP_JSET OP_ADD OP_SUB OP_MUL OP_DIV OP_AND OP_OR OP_LSH OP_RSH OP_RET
 115 %token OP_TAX OP_TXA OP_LDXB K_PKT_LEN K_PROTO K_TYPE K_IFIDX K_NLATTR
 116 %token K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE K_RXHASH K_CPU K_COMMENT
 117
 118 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#'
 119
 120 %token number_hex number_dec label comment
 121
 122 %type <number> number_hex number_dec number
 123 %type <label> label
 124
 125 %%
 126
 127 prog
 128         : {}
 129         | prog line { }
 130         ;
 131
 132 line
 133         : instr { }
 134         | labeled_instr { }
 135         ;
 136
 137 labeled_instr
 138         : do_label instr { }
 139         ;
 140
 141 instr
 142         : do_ldb { }
 143         | do_ldh { }
 144         | do_ld { }
 145         | do_ldx { }
 146         | do_st { }
 147         | do_stx { }
 148         | do_jmp { }
 149         | do_jeq { }
 150         | do_jgt { }
 151         | do_jge { }
 152         | do_jset { }
 153         | do_add { }
 154         | do_sub { }
 155         | do_mul { }
 156         | do_div { }
 157         | do_and { }
 158         | do_or { }
 159         | do_lsh { }
 160         | do_rsh { }
 161         | do_ret { }
 162         | do_tax { }
 163         | do_txa { }
 164         | do_comment { }
 165         ;
 166
 167 number
 168         : number_dec { $$ = $1; }
 169         | number_hex { $$ = $1; }
 170         ;
 171
 172 do_comment
 173         : K_COMMENT { }
 174         ;
 175
 176 do_label
 177         : label ':' { set_curr_label($1); }
 178         ;
 179
 180 do_ldb
 181         : OP_LDB '[' 'x' '+' number ']' {
 182                 set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $5); }
 183         | OP_LDB '[' number ']' {
 184                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, $3); }
 185         | OP_LDB '#' K_PROTO {
 186                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 187                                SKF_AD_OFF + SKF_AD_PROTOCOL); }
 188         | OP_LDB '#' K_TYPE {
 189                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 190                                SKF_AD_OFF + SKF_AD_PKTTYPE); }
 191         | OP_LDB '#' K_IFIDX {
 192                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 193                                SKF_AD_OFF + SKF_AD_IFINDEX); }
 194         | OP_LDB '#' K_NLATTR {
 195                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 196                                SKF_AD_OFF + SKF_AD_NLATTR); }
 197         | OP_LDB '#' K_NLATTR_NEST {
 198                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 199                                SKF_AD_OFF + SKF_AD_NLATTR_NEST); }
 200         | OP_LDB '#' K_MARK {
 201                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 202                                SKF_AD_OFF + SKF_AD_MARK); }
 203         | OP_LDB '#' K_QUEUE {
 204                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 205                                SKF_AD_OFF + SKF_AD_QUEUE); }
 206         | OP_LDB '#' K_HATYPE {
 207                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 208                                SKF_AD_OFF + SKF_AD_HATYPE); }
 209         | OP_LDB '#' K_RXHASH {
 210                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 211                                SKF_AD_OFF + SKF_AD_RXHASH); }
 212         | OP_LDB '#' K_CPU {
 213                 set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 214                                SKF_AD_OFF + SKF_AD_CPU); }
 215         ;
 216
 217 do_ldh
 218         : OP_LDH '[' 'x' '+' number ']' {
 219                 set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $5); }
 220         | OP_LDH '[' number ']' {
 221                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, $3); }
 222         | OP_LDH '#' K_PROTO {
 223                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 224                                SKF_AD_OFF + SKF_AD_PROTOCOL); }
 225         | OP_LDH '#' K_TYPE {
 226                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 227                                SKF_AD_OFF + SKF_AD_PKTTYPE); }
 228         | OP_LDH '#' K_IFIDX {
 229                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 230                                SKF_AD_OFF + SKF_AD_IFINDEX); }
 231         | OP_LDH '#' K_NLATTR {
 232                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 233                                SKF_AD_OFF + SKF_AD_NLATTR); }
 234         | OP_LDH '#' K_NLATTR_NEST {
 235                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 236                                SKF_AD_OFF + SKF_AD_NLATTR_NEST); }
 237         | OP_LDH '#' K_MARK {
 238                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 239                                SKF_AD_OFF + SKF_AD_MARK); }
 240         | OP_LDH '#' K_QUEUE {
 241                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 242                                SKF_AD_OFF + SKF_AD_QUEUE); }
 243         | OP_LDH '#' K_HATYPE {
 244                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 245                                SKF_AD_OFF + SKF_AD_HATYPE); }
 246         | OP_LDH '#' K_RXHASH {
 247                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 248                                SKF_AD_OFF + SKF_AD_RXHASH); }
 249         | OP_LDH '#' K_CPU {
 250                 set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 251                                SKF_AD_OFF + SKF_AD_CPU); }
 252         ;
 253
 254 do_ld
 255         : OP_LD '#' number {
 256                 set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
 257         | OP_LD '#' K_PKT_LEN {
 258                 set_curr_instr(BPF_LD | BPF_W | BPF_LEN, 0, 0, 0); }
 259         | OP_LD '#' K_PROTO {
 260                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 261                                SKF_AD_OFF + SKF_AD_PROTOCOL); }
 262         | OP_LD '#' K_TYPE {
 263                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 264                                SKF_AD_OFF + SKF_AD_PKTTYPE); }
 265         | OP_LD '#' K_IFIDX {
 266                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 267                                SKF_AD_OFF + SKF_AD_IFINDEX); }
 268         | OP_LD '#' K_NLATTR {
 269                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 270                                SKF_AD_OFF + SKF_AD_NLATTR); }
 271         | OP_LD '#' K_NLATTR_NEST {
 272                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 273                                SKF_AD_OFF + SKF_AD_NLATTR_NEST); }
 274         | OP_LD '#' K_MARK {
 275                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 276                                SKF_AD_OFF + SKF_AD_MARK); }
 277         | OP_LD '#' K_QUEUE {
 278                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 279                                SKF_AD_OFF + SKF_AD_QUEUE); }
 280         | OP_LD '#' K_HATYPE {
 281                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 282                                SKF_AD_OFF + SKF_AD_HATYPE); }
 283         | OP_LD '#' K_RXHASH {
 284                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 285                                SKF_AD_OFF + SKF_AD_RXHASH); }
 286         | OP_LD '#' K_CPU {
 287                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 288                                SKF_AD_OFF + SKF_AD_CPU); }
 289         | OP_LD 'M' '[' number ']' {
 290                 set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
 291         | OP_LD '[' 'x' '+' number ']' {
 292                 set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $5); }
 293         | OP_LD '[' number ']' {
 294                 set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, $3); }
 295         ;
 296
 297 do_ldx
 298         : OP_LDX '#' number {
 299                 set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
 300         | OP_LDX 'M' '[' number ']' {
 301                 set_curr_instr(BPF_LDX | BPF_MEM, 0, 0, $4); }
 302         | OP_LDXB number '*' '(' '[' number ']' '&' number ')' {
 303                 if ($2 != 4 || $9 != 0xf) {
 304                         panic("ldxb offset not supported!\n");
 305                 } else {
 306                         set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
 307         | OP_LDX number '*' '(' '[' number ']' '&' number ')' {
 308                 if ($2 != 4 || $9 != 0xf) {
 309                         panic("ldxb offset not supported!\n");
 310                 } else {
 311                         set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
 312         ;
 313
 314 do_st
 315         : OP_ST 'M' '[' number ']' {
 316                 set_curr_instr(BPF_ST, 0, 0, $4); }
 317         ;
 318
 319 do_stx
 320         : OP_STX 'M' '[' number ']' {
 321                 set_curr_instr(BPF_STX, 0, 0, $4); }
 322         ;
 323
 324 do_jmp
 325         : OP_JMP label {
 326                 set_jmp_label($2, JKL);
 327                 set_curr_instr(BPF_JMP | BPF_JA, 0, 0, 0); }
 328         ;
 329
 330 do_jeq
 331         : OP_JEQ '#' number ',' label ',' label {
 332                 set_jmp_label($5, JTL);
 333                 set_jmp_label($7, JFL);
 334                 set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
 335         | OP_JEQ 'x' ',' label ',' label {
 336                 set_jmp_label($4, JTL);
 337                 set_jmp_label($6, JFL);
 338                 set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 339         ;
 340
 341 do_jgt
 342         : OP_JGT '#' number ',' label ',' label {
 343                 set_jmp_label($5, JTL);
 344                 set_jmp_label($7, JFL);
 345                 set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
 346         | OP_JGT 'x' ',' label ',' label {
 347                 set_jmp_label($4, JTL);
 348                 set_jmp_label($6, JFL);
 349                 set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 350         ;
 351
 352 do_jge
 353         : OP_JGE '#' number ',' label ',' label {
 354                 set_jmp_label($5, JTL);
 355                 set_jmp_label($7, JFL);
 356                 set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
 357         | OP_JGE 'x' ',' label ',' label {
 358                 set_jmp_label($4, JTL);
 359                 set_jmp_label($6, JFL);
 360                 set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 361         ;
 362
 363 do_jset
 364         : OP_JSET '#' number ',' label ',' label {
 365                 set_jmp_label($5, JTL);
 366                 set_jmp_label($7, JFL);
 367                 set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
 368         | OP_JSET 'x' ',' label ',' label {
 369                 set_jmp_label($4, JTL);
 370                 set_jmp_label($6, JFL);
 371                 set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
 372         ;
 373
 374 do_add
 375         : OP_ADD '#' number {
 376                 set_curr_instr(BPF_ALU | BPF_ADD | BPF_K, 0, 0, $3); }
 377         | OP_ADD 'x' {
 378                 set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
 379         ;
 380
 381 do_sub
 382         : OP_SUB '#' number {
 383                 set_curr_instr(BPF_ALU | BPF_SUB | BPF_K, 0, 0, $3); }
 384         | OP_SUB 'x' {
 385                 set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
 386         ;
 387
 388 do_mul
 389         : OP_MUL '#' number {
 390                 set_curr_instr(BPF_ALU | BPF_MUL | BPF_K, 0, 0, $3); }
 391         | OP_MUL 'x' {
 392                 set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
 393         ;
 394
 395 do_div
 396         : OP_DIV '#' number {
 397                 set_curr_instr(BPF_ALU | BPF_DIV | BPF_K, 0, 0, $3); }
 398         | OP_DIV 'x' {
 399                 set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
 400         ;
 401
 402 do_and
 403         : OP_AND '#' number {
 404                 set_curr_instr(BPF_ALU | BPF_AND | BPF_K, 0, 0, $3); }
 405         | OP_AND 'x' {
 406                 set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
 407         ;
 408
 409 do_or
 410         : OP_OR '#' number {
 411                 set_curr_instr(BPF_ALU | BPF_OR | BPF_K, 0, 0, $3); }
 412         | OP_OR 'x' {
 413                 set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
 414         ;
 415
 416 do_lsh
 417         : OP_LSH '#' number {
 418                 set_curr_instr(BPF_ALU | BPF_LSH | BPF_K, 0, 0, $3); }
 419         | OP_LSH 'x' {
 420                 set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
 421         ;
 422
 423 do_rsh
 424         : OP_RSH '#' number {
 425                 set_curr_instr(BPF_ALU | BPF_RSH | BPF_K, 0, 0, $3); }
 426         | OP_RSH 'x' {
 427                 set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
 428         ;
 429
 430 do_ret
 431         : OP_RET 'a' {
 432                 set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
 433         | OP_RET '#' number {
 434                 set_curr_instr(BPF_RET | BPF_K, 0, 0, $3); }
 435         ;
 436
 437 do_tax
 438         : OP_TAX {
 439                 set_curr_instr(BPF_MISC | BPF_TAX, 0, 0, 0); }
 440         ;
 441
 442 do_txa
 443         : OP_TXA {
 444                 set_curr_instr(BPF_MISC | BPF_TXA, 0, 0, 0); }
 445         ;
 446
 447 %%
 448
 449 static void stage_1_inline(void)
 450 {
 451         yyparse();
 452 }
 453
 454 static void stage_2_label_reduce(void)
 455 {
 456         int i, max = curr_instr, off;
 457
 458         /* 1. reduce k jumps */
 459         for (i = 0; i < max; ++i) {
 460                 if (labels_k[i] != NULL) {
 461                         off = find_intr_offset_or_panic(labels_k[i]);
 462                         out[i].k = (uint32_t) (off - i - 1);
 463                 }
 464         }
 465
 466         /* 1. reduce jt jumps */
 467         for (i = 0; i < max; ++i) {
 468                 if (labels_jt[i] != NULL) {
 469                         off = find_intr_offset_or_panic(labels_jt[i]);
 470                         out[i].jt = (uint8_t) (off - i -1);
 471                 }
 472         }
 473
 474         /* 1. reduce jf jumps */
 475         for (i = 0; i < max; ++i) {
 476                 if (labels_jf[i] != NULL) {
 477                         off = find_intr_offset_or_panic(labels_jf[i]);
 478                         out[i].jf = (uint8_t) (off - i - 1);
 479                 }
 480         }
 481 }
 482
 483 int compile_filter(char *file, int verbose)
 484 {
 485         int i;
 486         struct sock_fprog res;
 487
 488         yyin = fopen(file, "r");
 489         if (!yyin)
 490                 panic("Cannot open file!\n");
 491
 492         memset(out, 0, sizeof(out));
 493         memset(labels, 0, sizeof(labels));
 494         memset(labels_jf, 0, sizeof(labels_jf));
 495         memset(labels_jt, 0, sizeof(labels_jt));
 496         memset(labels_k, 0, sizeof(labels_k));
 497
 498         stage_1_inline();
 499         stage_2_label_reduce();
 500
 501         res.filter = out;
 502         res.len = curr_instr;
 503
 504         if (verbose) {
 505                 printf("*** Generated program:\n");
 506                 bpf_dump_all(&res);
 507         }
 508
 509         if (verbose) {
 510                 printf("*** Validating: ");
 511                 fflush(stdout);
 512         }
 513         if (bpf_validate(&res) == 0) {
 514                 if (verbose)
 515                         whine("semantic error! BPF validation failed!\n");
 516                 else
 517                         panic("Semantic error! BPF validation failed! "
 518                               "Try -V for debugging output!\n");
 519         } else if (verbose)
 520                 printf("is valid!\n");
 521
 522         if (verbose)
 523                 printf("*** Result:\n");
 524         for (i = 0; i < res.len; ++i) {
 525                 printf("{ 0x%x, %u, %u, 0x%08x },\n",
 526                        res.filter[i].code, res.filter[i].jt,
 527                        res.filter[i].jf, res.filter[i].k);
 528                 if (labels[i] != NULL)
 529                         xfree(labels[i]);
 530                 if (labels_jt[i] != NULL)
 531                         xfree(labels_jt[i]);
 532                 if (labels_jf[i] != NULL)
 533                         xfree(labels_jf[i]);
 534                 if (labels_k[i] != NULL)
 535                         xfree(labels_k[i]);
 536         }
 537
 538         return 0;
 539 }
 540
 541 void yyerror(const char *err)
 542 {
 543         panic("Syntax error at line %d: %s! %s!\n",
 544               yylineno, yytext, err);
 545 }
 546