tools/bpf/bpf_exp.y

0001 /*
0002  * BPF asm code parser
0003  *
0004  * This program is free software; you can distribute it and/or modify
0005  * it under the terms of the GNU General Public License as published
0006  * by the Free Software Foundation; either version 2 of the License,
0007  * or (at your option) any later version.
0008  *
0009  * Syntax kept close to:
0010  *
0011  * Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
0012  * architecture for user-level packet capture. In Proceedings of the
0013  * USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
0014  * Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
0015  * CA, USA, 2-2.
0016  *
0017  * Copyright 2013 Daniel Borkmann <borkmann@redhat.com>
0018  * Licensed under the GNU General Public License, version 2.0 (GPLv2)
0019  */
0020
0021 %{
0022
0023 #include <stdio.h>
0024 #include <string.h>
0025 #include <stdint.h>
0026 #include <stdlib.h>
0027 #include <stdbool.h>
0028 #include <unistd.h>
0029 #include <errno.h>
0030 #include <assert.h>
0031 #include <linux/filter.h>
0032
0033 #include "bpf_exp.yacc.h"
0034
0035 enum jmp_type { JTL, JFL, JKL };
0036
0037 extern FILE *yyin;
0038 extern int yylineno;
0039 extern int yylex(void);
0040 extern void yyerror(const char *str);
0041
0042 extern void bpf_asm_compile(FILE *fp, bool cstyle);
0043 static void bpf_set_curr_instr(uint16_t op, uint8_t jt, uint8_t jf, uint32_t k);
0044 static void bpf_set_curr_label(char *label);
0045 static void bpf_set_jmp_label(char *label, enum jmp_type type);
0046
0047 %}
0048
0049 %union {
0050         char *label;
0051         uint32_t number;
0052 }
0053
0054 %token OP_LDB OP_LDH OP_LD OP_LDX OP_ST OP_STX OP_JMP OP_JEQ OP_JGT OP_JGE
0055 %token OP_JSET OP_ADD OP_SUB OP_MUL OP_DIV OP_AND OP_OR OP_XOR OP_LSH OP_RSH
0056 %token OP_RET OP_TAX OP_TXA OP_LDXB OP_MOD OP_NEG OP_JNEQ OP_JLT OP_JLE OP_LDI
0057 %token OP_LDXI
0058
0059 %token K_PKT_LEN
0060
0061 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
0062
0063 %token extension number label
0064
0065 %type <label> label
0066 %type <number> extension
0067 %type <number> number
0068
0069 %%
0070
0071 prog
0072         : line
0073         | prog line
0074         ;
0075
0076 line
0077         : instr
0078         | labelled_instr
0079         ;
0080
0081 labelled_instr
0082         : labelled instr
0083         ;
0084
0085 instr
0086         : ldb
0087         | ldh
0088         | ld
0089         | ldi
0090         | ldx
0091         | ldxi
0092         | st
0093         | stx
0094         | jmp
0095         | jeq
0096         | jneq
0097         | jlt
0098         | jle
0099         | jgt
0100         | jge
0101         | jset
0102         | add
0103         | sub
0104         | mul
0105         | div
0106         | mod
0107         | neg
0108         | and
0109         | or
0110         | xor
0111         | lsh
0112         | rsh
0113         | ret
0114         | tax
0115         | txa
0116         ;
0117
0118 labelled
0119         : label ':' { bpf_set_curr_label($1); }
0120         ;
0121
0122 ldb
0123         : OP_LDB '[' 'x' '+' number ']' {
0124                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $5); }
0125         | OP_LDB '[' '%' 'x' '+' number ']' {
0126                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $6); }
0127         | OP_LDB '[' number ']' {
0128                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, $3); }
0129         | OP_LDB extension {
0130                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
0131                                    SKF_AD_OFF + $2); }
0132         ;
0133
0134 ldh
0135         : OP_LDH '[' 'x' '+' number ']' {
0136                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $5); }
0137         | OP_LDH '[' '%' 'x' '+' number ']' {
0138                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $6); }
0139         | OP_LDH '[' number ']' {
0140                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, $3); }
0141         | OP_LDH extension {
0142                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
0143                                    SKF_AD_OFF + $2); }
0144         ;
0145
0146 ldi
0147         : OP_LDI '#' number {
0148                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
0149         | OP_LDI number {
0150                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $2); }
0151         ;
0152
0153 ld
0154         : OP_LD '#' number {
0155                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
0156         | OP_LD K_PKT_LEN {
0157                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_LEN, 0, 0, 0); }
0158         | OP_LD extension {
0159                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
0160                                    SKF_AD_OFF + $2); }
0161         | OP_LD 'M' '[' number ']' {
0162                 bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
0163         | OP_LD '[' 'x' '+' number ']' {
0164                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $5); }
0165         | OP_LD '[' '%' 'x' '+' number ']' {
0166                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $6); }
0167         | OP_LD '[' number ']' {
0168                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, $3); }
0169         ;
0170
0171 ldxi
0172         : OP_LDXI '#' number {
0173                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
0174         | OP_LDXI number {
0175                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $2); }
0176         ;
0177
0178 ldx
0179         : OP_LDX '#' number {
0180                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
0181         | OP_LDX K_PKT_LEN {
0182                 bpf_set_curr_instr(BPF_LDX | BPF_W | BPF_LEN, 0, 0, 0); }
0183         | OP_LDX 'M' '[' number ']' {
0184                 bpf_set_curr_instr(BPF_LDX | BPF_MEM, 0, 0, $4); }
0185         | OP_LDXB number '*' '(' '[' number ']' '&' number ')' {
0186                 if ($2 != 4 || $9 != 0xf) {
0187                         fprintf(stderr, "ldxb offset not supported!\n");
0188                         exit(1);
0189                 } else {
0190                         bpf_set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
0191         | OP_LDX number '*' '(' '[' number ']' '&' number ')' {
0192                 if ($2 != 4 || $9 != 0xf) {
0193                         fprintf(stderr, "ldxb offset not supported!\n");
0194                         exit(1);
0195                 } else {
0196                         bpf_set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
0197         ;
0198
0199 st
0200         : OP_ST 'M' '[' number ']' {
0201                 bpf_set_curr_instr(BPF_ST, 0, 0, $4); }
0202         ;
0203
0204 stx
0205         : OP_STX 'M' '[' number ']' {
0206                 bpf_set_curr_instr(BPF_STX, 0, 0, $4); }
0207         ;
0208
0209 jmp
0210         : OP_JMP label {
0211                 bpf_set_jmp_label($2, JKL);
0212                 bpf_set_curr_instr(BPF_JMP | BPF_JA, 0, 0, 0); }
0213         ;
0214
0215 jeq
0216         : OP_JEQ '#' number ',' label ',' label {
0217                 bpf_set_jmp_label($5, JTL);
0218                 bpf_set_jmp_label($7, JFL);
0219                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
0220         | OP_JEQ 'x' ',' label ',' label {
0221                 bpf_set_jmp_label($4, JTL);
0222                 bpf_set_jmp_label($6, JFL);
0223                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
0224         | OP_JEQ '%' 'x' ',' label ',' label {
0225                 bpf_set_jmp_label($5, JTL);
0226                 bpf_set_jmp_label($7, JFL);
0227                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
0228         | OP_JEQ '#' number ',' label {
0229                 bpf_set_jmp_label($5, JTL);
0230                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
0231         | OP_JEQ 'x' ',' label {
0232                 bpf_set_jmp_label($4, JTL);
0233                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
0234         | OP_JEQ '%' 'x' ',' label {
0235                 bpf_set_jmp_label($5, JTL);
0236                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
0237         ;
0238
0239 jneq
0240         : OP_JNEQ '#' number ',' label {
0241                 bpf_set_jmp_label($5, JFL);
0242                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
0243         | OP_JNEQ 'x' ',' label {
0244                 bpf_set_jmp_label($4, JFL);
0245                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
0246         | OP_JNEQ '%' 'x' ',' label {
0247                 bpf_set_jmp_label($5, JFL);
0248                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
0249         ;
0250
0251 jlt
0252         : OP_JLT '#' number ',' label {
0253                 bpf_set_jmp_label($5, JFL);
0254                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
0255         | OP_JLT 'x' ',' label {
0256                 bpf_set_jmp_label($4, JFL);
0257                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
0258         | OP_JLT '%' 'x' ',' label {
0259                 bpf_set_jmp_label($5, JFL);
0260                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
0261         ;
0262
0263 jle
0264         : OP_JLE '#' number ',' label {
0265                 bpf_set_jmp_label($5, JFL);
0266                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
0267         | OP_JLE 'x' ',' label {
0268                 bpf_set_jmp_label($4, JFL);
0269                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
0270         | OP_JLE '%' 'x' ',' label {
0271                 bpf_set_jmp_label($5, JFL);
0272                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
0273         ;
0274
0275 jgt
0276         : OP_JGT '#' number ',' label ',' label {
0277                 bpf_set_jmp_label($5, JTL);
0278                 bpf_set_jmp_label($7, JFL);
0279                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
0280         | OP_JGT 'x' ',' label ',' label {
0281                 bpf_set_jmp_label($4, JTL);
0282                 bpf_set_jmp_label($6, JFL);
0283                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
0284         | OP_JGT '%' 'x' ',' label ',' label {
0285                 bpf_set_jmp_label($5, JTL);
0286                 bpf_set_jmp_label($7, JFL);
0287                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
0288         | OP_JGT '#' number ',' label {
0289                 bpf_set_jmp_label($5, JTL);
0290                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
0291         | OP_JGT 'x' ',' label {
0292                 bpf_set_jmp_label($4, JTL);
0293                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
0294         | OP_JGT '%' 'x' ',' label {
0295                 bpf_set_jmp_label($5, JTL);
0296                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
0297         ;
0298
0299 jge
0300         : OP_JGE '#' number ',' label ',' label {
0301                 bpf_set_jmp_label($5, JTL);
0302                 bpf_set_jmp_label($7, JFL);
0303                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
0304         | OP_JGE 'x' ',' label ',' label {
0305                 bpf_set_jmp_label($4, JTL);
0306                 bpf_set_jmp_label($6, JFL);
0307                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
0308         | OP_JGE '%' 'x' ',' label ',' label {
0309                 bpf_set_jmp_label($5, JTL);
0310                 bpf_set_jmp_label($7, JFL);
0311                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
0312         | OP_JGE '#' number ',' label {
0313                 bpf_set_jmp_label($5, JTL);
0314                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
0315         | OP_JGE 'x' ',' label {
0316                 bpf_set_jmp_label($4, JTL);
0317                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
0318         | OP_JGE '%' 'x' ',' label {
0319                 bpf_set_jmp_label($5, JTL);
0320                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
0321         ;
0322
0323 jset
0324         : OP_JSET '#' number ',' label ',' label {
0325                 bpf_set_jmp_label($5, JTL);
0326                 bpf_set_jmp_label($7, JFL);
0327                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
0328         | OP_JSET 'x' ',' label ',' label {
0329                 bpf_set_jmp_label($4, JTL);
0330                 bpf_set_jmp_label($6, JFL);
0331                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
0332         | OP_JSET '%' 'x' ',' label ',' label {
0333                 bpf_set_jmp_label($5, JTL);
0334                 bpf_set_jmp_label($7, JFL);
0335                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
0336         | OP_JSET '#' number ',' label {
0337                 bpf_set_jmp_label($5, JTL);
0338                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
0339         | OP_JSET 'x' ',' label {
0340                 bpf_set_jmp_label($4, JTL);
0341                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
0342         | OP_JSET '%' 'x' ',' label {
0343                 bpf_set_jmp_label($5, JTL);
0344                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
0345         ;
0346
0347 add
0348         : OP_ADD '#' number {
0349                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_K, 0, 0, $3); }
0350         | OP_ADD 'x' {
0351                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
0352         | OP_ADD '%' 'x' {
0353                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
0354         ;
0355
0356 sub
0357         : OP_SUB '#' number {
0358                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_K, 0, 0, $3); }
0359         | OP_SUB 'x' {
0360                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
0361         | OP_SUB '%' 'x' {
0362                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
0363         ;
0364
0365 mul
0366         : OP_MUL '#' number {
0367                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_K, 0, 0, $3); }
0368         | OP_MUL 'x' {
0369                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
0370         | OP_MUL '%' 'x' {
0371                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
0372         ;
0373
0374 div
0375         : OP_DIV '#' number {
0376                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_K, 0, 0, $3); }
0377         | OP_DIV 'x' {
0378                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
0379         | OP_DIV '%' 'x' {
0380                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
0381         ;
0382
0383 mod
0384         : OP_MOD '#' number {
0385                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_K, 0, 0, $3); }
0386         | OP_MOD 'x' {
0387                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
0388         | OP_MOD '%' 'x' {
0389                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
0390         ;
0391
0392 neg
0393         : OP_NEG {
0394                 bpf_set_curr_instr(BPF_ALU | BPF_NEG, 0, 0, 0); }
0395         ;
0396
0397 and
0398         : OP_AND '#' number {
0399                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_K, 0, 0, $3); }
0400         | OP_AND 'x' {
0401                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
0402         | OP_AND '%' 'x' {
0403                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
0404         ;
0405
0406 or
0407         : OP_OR '#' number {
0408                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_K, 0, 0, $3); }
0409         | OP_OR 'x' {
0410                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
0411         | OP_OR '%' 'x' {
0412                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
0413         ;
0414
0415 xor
0416         : OP_XOR '#' number {
0417                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_K, 0, 0, $3); }
0418         | OP_XOR 'x' {
0419                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
0420         | OP_XOR '%' 'x' {
0421                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
0422         ;
0423
0424 lsh
0425         : OP_LSH '#' number {
0426                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_K, 0, 0, $3); }
0427         | OP_LSH 'x' {
0428                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
0429         | OP_LSH '%' 'x' {
0430                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
0431         ;
0432
0433 rsh
0434         : OP_RSH '#' number {
0435                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_K, 0, 0, $3); }
0436         | OP_RSH 'x' {
0437                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
0438         | OP_RSH '%' 'x' {
0439                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
0440         ;
0441
0442 ret
0443         : OP_RET 'a' {
0444                 bpf_set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
0445         | OP_RET '%' 'a' {
0446                 bpf_set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
0447         | OP_RET 'x' {
0448                 bpf_set_curr_instr(BPF_RET | BPF_X, 0, 0, 0); }
0449         | OP_RET '%' 'x' {
0450                 bpf_set_curr_instr(BPF_RET | BPF_X, 0, 0, 0); }
0451         | OP_RET '#' number {
0452                 bpf_set_curr_instr(BPF_RET | BPF_K, 0, 0, $3); }
0453         ;
0454
0455 tax
0456         : OP_TAX {
0457                 bpf_set_curr_instr(BPF_MISC | BPF_TAX, 0, 0, 0); }
0458         ;
0459
0460 txa
0461         : OP_TXA {
0462                 bpf_set_curr_instr(BPF_MISC | BPF_TXA, 0, 0, 0); }
0463         ;
0464
0465 %%
0466
0467 static int curr_instr = 0;
0468 static struct sock_filter out[BPF_MAXINSNS];
0469 static char **labels, **labels_jt, **labels_jf, **labels_k;
0470
0471 static void bpf_assert_max(void)
0472 {
0473         if (curr_instr >= BPF_MAXINSNS) {
0474                 fprintf(stderr, "only max %u insns allowed!\n", BPF_MAXINSNS);
0475                 exit(1);
0476         }
0477 }
0478
0479 static void bpf_set_curr_instr(uint16_t code, uint8_t jt, uint8_t jf,
0480                                uint32_t k)
0481 {
0482         bpf_assert_max();
0483         out[curr_instr].code = code;
0484         out[curr_instr].jt = jt;
0485         out[curr_instr].jf = jf;
0486         out[curr_instr].k = k;
0487         curr_instr++;
0488 }
0489
0490 static void bpf_set_curr_label(char *label)
0491 {
0492         bpf_assert_max();
0493         labels[curr_instr] = label;
0494 }
0495
0496 static void bpf_set_jmp_label(char *label, enum jmp_type type)
0497 {
0498         bpf_assert_max();
0499         switch (type) {
0500         case JTL:
0501                 labels_jt[curr_instr] = label;
0502                 break;
0503         case JFL:
0504                 labels_jf[curr_instr] = label;
0505                 break;
0506         case JKL:
0507                 labels_k[curr_instr] = label;
0508                 break;
0509         }
0510 }
0511
0512 static int bpf_find_insns_offset(const char *label)
0513 {
0514         int i, max = curr_instr, ret = -ENOENT;
0515
0516         for (i = 0; i < max; i++) {
0517                 if (labels[i] && !strcmp(label, labels[i])) {
0518                         ret = i;
0519                         break;
0520                 }
0521         }
0522
0523         if (ret == -ENOENT) {
0524                 fprintf(stderr, "no such label \'%s\'!\n", label);
0525                 exit(1);
0526         }
0527
0528         return ret;
0529 }
0530
0531 static void bpf_stage_1_insert_insns(void)
0532 {
0533         yyparse();
0534 }
0535
0536 static void bpf_reduce_k_jumps(void)
0537 {
0538         int i;
0539
0540         for (i = 0; i < curr_instr; i++) {
0541                 if (labels_k[i]) {
0542                         int off = bpf_find_insns_offset(labels_k[i]);
0543                         out[i].k = (uint32_t) (off - i - 1);
0544                 }
0545         }
0546 }
0547
0548 static uint8_t bpf_encode_jt_jf_offset(int off, int i)
0549 {
0550         int delta = off - i - 1;
0551
0552         if (delta < 0 || delta > 255) {
0553                 fprintf(stderr, "error: insn #%d jumps to insn #%d, "
0554                                 "which is out of range\n", i, off);
0555                 exit(1);
0556         }
0557         return (uint8_t) delta;
0558 }
0559
0560 static void bpf_reduce_jt_jumps(void)
0561 {
0562         int i;
0563
0564         for (i = 0; i < curr_instr; i++) {
0565                 if (labels_jt[i]) {
0566                         int off = bpf_find_insns_offset(labels_jt[i]);
0567                         out[i].jt = bpf_encode_jt_jf_offset(off, i);
0568                 }
0569         }
0570 }
0571
0572 static void bpf_reduce_jf_jumps(void)
0573 {
0574         int i;
0575
0576         for (i = 0; i < curr_instr; i++) {
0577                 if (labels_jf[i]) {
0578                         int off = bpf_find_insns_offset(labels_jf[i]);
0579                         out[i].jf = bpf_encode_jt_jf_offset(off, i);
0580                 }
0581         }
0582 }
0583
0584 static void bpf_stage_2_reduce_labels(void)
0585 {
0586         bpf_reduce_k_jumps();
0587         bpf_reduce_jt_jumps();
0588         bpf_reduce_jf_jumps();
0589 }
0590
0591 static void bpf_pretty_print_c(void)
0592 {
0593         int i;
0594
0595         for (i = 0; i < curr_instr; i++)
0596                 printf("{ %#04x, %2u, %2u, %#010x },\n", out[i].code,
0597                        out[i].jt, out[i].jf, out[i].k);
0598 }
0599
0600 static void bpf_pretty_print(void)
0601 {
0602         int i;
0603
0604         printf("%u,", curr_instr);
0605         for (i = 0; i < curr_instr; i++)
0606                 printf("%u %u %u %u,", out[i].code,
0607                        out[i].jt, out[i].jf, out[i].k);
0608         printf("\n");
0609 }
0610
0611 static void bpf_init(void)
0612 {
0613         memset(out, 0, sizeof(out));
0614
0615         labels = calloc(BPF_MAXINSNS, sizeof(*labels));
0616         assert(labels);
0617         labels_jt = calloc(BPF_MAXINSNS, sizeof(*labels_jt));
0618         assert(labels_jt);
0619         labels_jf = calloc(BPF_MAXINSNS, sizeof(*labels_jf));
0620         assert(labels_jf);
0621         labels_k = calloc(BPF_MAXINSNS, sizeof(*labels_k));
0622         assert(labels_k);
0623 }
0624
0625 static void bpf_destroy_labels(void)
0626 {
0627         int i;
0628
0629         for (i = 0; i < curr_instr; i++) {
0630                 free(labels_jf[i]);
0631                 free(labels_jt[i]);
0632                 free(labels_k[i]);
0633                 free(labels[i]);
0634         }
0635 }
0636
0637 static void bpf_destroy(void)
0638 {
0639         bpf_destroy_labels();
0640         free(labels_jt);
0641         free(labels_jf);
0642         free(labels_k);
0643         free(labels);
0644 }
0645
0646 void bpf_asm_compile(FILE *fp, bool cstyle)
0647 {
0648         yyin = fp;
0649
0650         bpf_init();
0651         bpf_stage_1_insert_insns();
0652         bpf_stage_2_reduce_labels();
0653         bpf_destroy();
0654
0655         if (cstyle)
0656                 bpf_pretty_print_c();
0657         else
0658                 bpf_pretty_print();
0659
0660         if (fp != stdin)
0661                 fclose(yyin);
0662 }
0663
0664 void yyerror(const char *str)
0665 {
0666         fprintf(stderr, "error: %s at line %d\n", str, yylineno);
0667         exit(1);
0668 }