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