Merge tag 'dma-mapping-4.16-3' of git://git.infradead.org/users/hch/dma-mapping
[sfrench/cifs-2.6.git] / tools / bpf / bpf_exp.y
1 /*
2  * BPF asm code parser
3  *
4  * This program is free software; you can distribute it and/or modify
5  * it under the terms of the GNU General Public License as published
6  * by the Free Software Foundation; either version 2 of the License,
7  * or (at your option) any later version.
8  *
9  * Syntax kept close to:
10  *
11  * Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
12  * architecture for user-level packet capture. In Proceedings of the
13  * USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
14  * Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
15  * CA, USA, 2-2.
16  *
17  * Copyright 2013 Daniel Borkmann <borkmann@redhat.com>
18  * Licensed under the GNU General Public License, version 2.0 (GPLv2)
19  */
20
21 %{
22
23 #include <stdio.h>
24 #include <string.h>
25 #include <stdint.h>
26 #include <stdlib.h>
27 #include <stdbool.h>
28 #include <unistd.h>
29 #include <errno.h>
30 #include <assert.h>
31 #include <linux/filter.h>
32
33 #include "bpf_exp.yacc.h"
34
35 enum jmp_type { JTL, JFL, JKL };
36
37 extern FILE *yyin;
38 extern int yylineno;
39 extern int yylex(void);
40 extern void yyerror(const char *str);
41
42 extern void bpf_asm_compile(FILE *fp, bool cstyle);
43 static void bpf_set_curr_instr(uint16_t op, uint8_t jt, uint8_t jf, uint32_t k);
44 static void bpf_set_curr_label(char *label);
45 static void bpf_set_jmp_label(char *label, enum jmp_type type);
46
47 %}
48
49 %union {
50         char *label;
51         uint32_t number;
52 }
53
54 %token OP_LDB OP_LDH OP_LD OP_LDX OP_ST OP_STX OP_JMP OP_JEQ OP_JGT OP_JGE
55 %token OP_JSET OP_ADD OP_SUB OP_MUL OP_DIV OP_AND OP_OR OP_XOR OP_LSH OP_RSH
56 %token OP_RET OP_TAX OP_TXA OP_LDXB OP_MOD OP_NEG OP_JNEQ OP_JLT OP_JLE OP_LDI
57 %token OP_LDXI
58
59 %token K_PKT_LEN
60
61 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
62
63 %token extension number label
64
65 %type <label> label
66 %type <number> extension
67 %type <number> number
68
69 %%
70
71 prog
72         : line
73         | prog line
74         ;
75
76 line
77         : instr
78         | labelled_instr
79         ;
80
81 labelled_instr
82         : labelled instr
83         ;
84
85 instr
86         : ldb
87         | ldh
88         | ld
89         | ldi
90         | ldx
91         | ldxi
92         | st
93         | stx
94         | jmp
95         | jeq
96         | jneq
97         | jlt
98         | jle
99         | jgt
100         | jge
101         | jset
102         | add
103         | sub
104         | mul
105         | div
106         | mod
107         | neg
108         | and
109         | or
110         | xor
111         | lsh
112         | rsh
113         | ret
114         | tax
115         | txa
116         ;
117
118 labelled
119         : label ':' { bpf_set_curr_label($1); }
120         ;
121
122 ldb
123         : OP_LDB '[' 'x' '+' number ']' {
124                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $5); }
125         | OP_LDB '[' '%' 'x' '+' number ']' {
126                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $6); }
127         | OP_LDB '[' number ']' {
128                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, $3); }
129         | OP_LDB extension {
130                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
131                                    SKF_AD_OFF + $2); }
132         ;
133
134 ldh
135         : OP_LDH '[' 'x' '+' number ']' {
136                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $5); }
137         | OP_LDH '[' '%' 'x' '+' number ']' {
138                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $6); }
139         | OP_LDH '[' number ']' {
140                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, $3); }
141         | OP_LDH extension {
142                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
143                                    SKF_AD_OFF + $2); }
144         ;
145
146 ldi
147         : OP_LDI '#' number {
148                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
149         | OP_LDI number {
150                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $2); }
151         ;
152
153 ld
154         : OP_LD '#' number {
155                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
156         | OP_LD K_PKT_LEN {
157                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_LEN, 0, 0, 0); }
158         | OP_LD extension {
159                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
160                                    SKF_AD_OFF + $2); }
161         | OP_LD 'M' '[' number ']' {
162                 bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
163         | OP_LD '[' 'x' '+' number ']' {
164                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $5); }
165         | OP_LD '[' '%' 'x' '+' number ']' {
166                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $6); }
167         | OP_LD '[' number ']' {
168                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, $3); }
169         ;
170
171 ldxi
172         : OP_LDXI '#' number {
173                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
174         | OP_LDXI number {
175                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $2); }
176         ;
177
178 ldx
179         : OP_LDX '#' number {
180                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
181         | OP_LDX K_PKT_LEN {
182                 bpf_set_curr_instr(BPF_LDX | BPF_W | BPF_LEN, 0, 0, 0); }
183         | OP_LDX 'M' '[' number ']' {
184                 bpf_set_curr_instr(BPF_LDX | BPF_MEM, 0, 0, $4); }
185         | OP_LDXB number '*' '(' '[' number ']' '&' number ')' {
186                 if ($2 != 4 || $9 != 0xf) {
187                         fprintf(stderr, "ldxb offset not supported!\n");
188                         exit(0);
189                 } else {
190                         bpf_set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
191         | OP_LDX number '*' '(' '[' number ']' '&' number ')' {
192                 if ($2 != 4 || $9 != 0xf) {
193                         fprintf(stderr, "ldxb offset not supported!\n");
194                         exit(0);
195                 } else {
196                         bpf_set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
197         ;
198
199 st
200         : OP_ST 'M' '[' number ']' {
201                 bpf_set_curr_instr(BPF_ST, 0, 0, $4); }
202         ;
203
204 stx
205         : OP_STX 'M' '[' number ']' {
206                 bpf_set_curr_instr(BPF_STX, 0, 0, $4); }
207         ;
208
209 jmp
210         : OP_JMP label {
211                 bpf_set_jmp_label($2, JKL);
212                 bpf_set_curr_instr(BPF_JMP | BPF_JA, 0, 0, 0); }
213         ;
214
215 jeq
216         : OP_JEQ '#' number ',' label ',' label {
217                 bpf_set_jmp_label($5, JTL);
218                 bpf_set_jmp_label($7, JFL);
219                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
220         | OP_JEQ 'x' ',' label ',' label {
221                 bpf_set_jmp_label($4, JTL);
222                 bpf_set_jmp_label($6, JFL);
223                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
224         | OP_JEQ '%' 'x' ',' label ',' label {
225                 bpf_set_jmp_label($5, JTL);
226                 bpf_set_jmp_label($7, JFL);
227                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
228         | OP_JEQ '#' number ',' label {
229                 bpf_set_jmp_label($5, JTL);
230                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
231         | OP_JEQ 'x' ',' label {
232                 bpf_set_jmp_label($4, JTL);
233                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
234         | OP_JEQ '%' 'x' ',' label {
235                 bpf_set_jmp_label($5, JTL);
236                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
237         ;
238
239 jneq
240         : OP_JNEQ '#' number ',' label {
241                 bpf_set_jmp_label($5, JFL);
242                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
243         | OP_JNEQ 'x' ',' label {
244                 bpf_set_jmp_label($4, JFL);
245                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
246         | OP_JNEQ '%' 'x' ',' label {
247                 bpf_set_jmp_label($5, JFL);
248                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
249         ;
250
251 jlt
252         : OP_JLT '#' number ',' label {
253                 bpf_set_jmp_label($5, JFL);
254                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
255         | OP_JLT 'x' ',' label {
256                 bpf_set_jmp_label($4, JFL);
257                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
258         | OP_JLT '%' 'x' ',' label {
259                 bpf_set_jmp_label($5, JFL);
260                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
261         ;
262
263 jle
264         : OP_JLE '#' number ',' label {
265                 bpf_set_jmp_label($5, JFL);
266                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
267         | OP_JLE 'x' ',' label {
268                 bpf_set_jmp_label($4, JFL);
269                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
270         | OP_JLE '%' 'x' ',' label {
271                 bpf_set_jmp_label($5, JFL);
272                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
273         ;
274
275 jgt
276         : OP_JGT '#' number ',' label ',' label {
277                 bpf_set_jmp_label($5, JTL);
278                 bpf_set_jmp_label($7, JFL);
279                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
280         | OP_JGT 'x' ',' label ',' label {
281                 bpf_set_jmp_label($4, JTL);
282                 bpf_set_jmp_label($6, JFL);
283                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
284         | OP_JGT '%' 'x' ',' label ',' label {
285                 bpf_set_jmp_label($5, JTL);
286                 bpf_set_jmp_label($7, JFL);
287                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
288         | OP_JGT '#' number ',' label {
289                 bpf_set_jmp_label($5, JTL);
290                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
291         | OP_JGT 'x' ',' label {
292                 bpf_set_jmp_label($4, JTL);
293                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
294         | OP_JGT '%' 'x' ',' label {
295                 bpf_set_jmp_label($5, JTL);
296                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
297         ;
298
299 jge
300         : OP_JGE '#' number ',' label ',' label {
301                 bpf_set_jmp_label($5, JTL);
302                 bpf_set_jmp_label($7, JFL);
303                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
304         | OP_JGE 'x' ',' label ',' label {
305                 bpf_set_jmp_label($4, JTL);
306                 bpf_set_jmp_label($6, JFL);
307                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
308         | OP_JGE '%' 'x' ',' label ',' label {
309                 bpf_set_jmp_label($5, JTL);
310                 bpf_set_jmp_label($7, JFL);
311                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
312         | OP_JGE '#' number ',' label {
313                 bpf_set_jmp_label($5, JTL);
314                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
315         | OP_JGE 'x' ',' label {
316                 bpf_set_jmp_label($4, JTL);
317                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
318         | OP_JGE '%' 'x' ',' label {
319                 bpf_set_jmp_label($5, JTL);
320                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
321         ;
322
323 jset
324         : OP_JSET '#' number ',' label ',' label {
325                 bpf_set_jmp_label($5, JTL);
326                 bpf_set_jmp_label($7, JFL);
327                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
328         | OP_JSET 'x' ',' label ',' label {
329                 bpf_set_jmp_label($4, JTL);
330                 bpf_set_jmp_label($6, JFL);
331                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
332         | OP_JSET '%' 'x' ',' label ',' label {
333                 bpf_set_jmp_label($5, JTL);
334                 bpf_set_jmp_label($7, JFL);
335                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
336         | OP_JSET '#' number ',' label {
337                 bpf_set_jmp_label($5, JTL);
338                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
339         | OP_JSET 'x' ',' label {
340                 bpf_set_jmp_label($4, JTL);
341                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
342         | OP_JSET '%' 'x' ',' label {
343                 bpf_set_jmp_label($5, JTL);
344                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
345         ;
346
347 add
348         : OP_ADD '#' number {
349                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_K, 0, 0, $3); }
350         | OP_ADD 'x' {
351                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
352         | OP_ADD '%' 'x' {
353                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
354         ;
355
356 sub
357         : OP_SUB '#' number {
358                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_K, 0, 0, $3); }
359         | OP_SUB 'x' {
360                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
361         | OP_SUB '%' 'x' {
362                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
363         ;
364
365 mul
366         : OP_MUL '#' number {
367                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_K, 0, 0, $3); }
368         | OP_MUL 'x' {
369                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
370         | OP_MUL '%' 'x' {
371                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
372         ;
373
374 div
375         : OP_DIV '#' number {
376                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_K, 0, 0, $3); }
377         | OP_DIV 'x' {
378                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
379         | OP_DIV '%' 'x' {
380                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
381         ;
382
383 mod
384         : OP_MOD '#' number {
385                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_K, 0, 0, $3); }
386         | OP_MOD 'x' {
387                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
388         | OP_MOD '%' 'x' {
389                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
390         ;
391
392 neg
393         : OP_NEG {
394                 bpf_set_curr_instr(BPF_ALU | BPF_NEG, 0, 0, 0); }
395         ;
396
397 and
398         : OP_AND '#' number {
399                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_K, 0, 0, $3); }
400         | OP_AND 'x' {
401                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
402         | OP_AND '%' 'x' {
403                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
404         ;
405
406 or
407         : OP_OR '#' number {
408                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_K, 0, 0, $3); }
409         | OP_OR 'x' {
410                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
411         | OP_OR '%' 'x' {
412                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
413         ;
414
415 xor
416         : OP_XOR '#' number {
417                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_K, 0, 0, $3); }
418         | OP_XOR 'x' {
419                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
420         | OP_XOR '%' 'x' {
421                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
422         ;
423
424 lsh
425         : OP_LSH '#' number {
426                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_K, 0, 0, $3); }
427         | OP_LSH 'x' {
428                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
429         | OP_LSH '%' 'x' {
430                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
431         ;
432
433 rsh
434         : OP_RSH '#' number {
435                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_K, 0, 0, $3); }
436         | OP_RSH 'x' {
437                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
438         | OP_RSH '%' 'x' {
439                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
440         ;
441
442 ret
443         : OP_RET 'a' {
444                 bpf_set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
445         | OP_RET '%' 'a' {
446                 bpf_set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
447         | OP_RET 'x' {
448                 bpf_set_curr_instr(BPF_RET | BPF_X, 0, 0, 0); }
449         | OP_RET '%' 'x' {
450                 bpf_set_curr_instr(BPF_RET | BPF_X, 0, 0, 0); }
451         | OP_RET '#' number {
452                 bpf_set_curr_instr(BPF_RET | BPF_K, 0, 0, $3); }
453         ;
454
455 tax
456         : OP_TAX {
457                 bpf_set_curr_instr(BPF_MISC | BPF_TAX, 0, 0, 0); }
458         ;
459
460 txa
461         : OP_TXA {
462                 bpf_set_curr_instr(BPF_MISC | BPF_TXA, 0, 0, 0); }
463         ;
464
465 %%
466
467 static int curr_instr = 0;
468 static struct sock_filter out[BPF_MAXINSNS];
469 static char **labels, **labels_jt, **labels_jf, **labels_k;
470
471 static void bpf_assert_max(void)
472 {
473         if (curr_instr >= BPF_MAXINSNS) {
474                 fprintf(stderr, "only max %u insns allowed!\n", BPF_MAXINSNS);
475                 exit(0);
476         }
477 }
478
479 static void bpf_set_curr_instr(uint16_t code, uint8_t jt, uint8_t jf,
480                                uint32_t k)
481 {
482         bpf_assert_max();
483         out[curr_instr].code = code;
484         out[curr_instr].jt = jt;
485         out[curr_instr].jf = jf;
486         out[curr_instr].k = k;
487         curr_instr++;
488 }
489
490 static void bpf_set_curr_label(char *label)
491 {
492         bpf_assert_max();
493         labels[curr_instr] = label;
494 }
495
496 static void bpf_set_jmp_label(char *label, enum jmp_type type)
497 {
498         bpf_assert_max();
499         switch (type) {
500         case JTL:
501                 labels_jt[curr_instr] = label;
502                 break;
503         case JFL:
504                 labels_jf[curr_instr] = label;
505                 break;
506         case JKL:
507                 labels_k[curr_instr] = label;
508                 break;
509         }
510 }
511
512 static int bpf_find_insns_offset(const char *label)
513 {
514         int i, max = curr_instr, ret = -ENOENT;
515
516         for (i = 0; i < max; i++) {
517                 if (labels[i] && !strcmp(label, labels[i])) {
518                         ret = i;
519                         break;
520                 }
521         }
522
523         if (ret == -ENOENT) {
524                 fprintf(stderr, "no such label \'%s\'!\n", label);
525                 exit(0);
526         }
527
528         return ret;
529 }
530
531 static void bpf_stage_1_insert_insns(void)
532 {
533         yyparse();
534 }
535
536 static void bpf_reduce_k_jumps(void)
537 {
538         int i;
539
540         for (i = 0; i < curr_instr; i++) {
541                 if (labels_k[i]) {
542                         int off = bpf_find_insns_offset(labels_k[i]);
543                         out[i].k = (uint32_t) (off - i - 1);
544                 }
545         }
546 }
547
548 static void bpf_reduce_jt_jumps(void)
549 {
550         int i;
551
552         for (i = 0; i < curr_instr; i++) {
553                 if (labels_jt[i]) {
554                         int off = bpf_find_insns_offset(labels_jt[i]);
555                         out[i].jt = (uint8_t) (off - i -1);
556                 }
557         }
558 }
559
560 static void bpf_reduce_jf_jumps(void)
561 {
562         int i;
563
564         for (i = 0; i < curr_instr; i++) {
565                 if (labels_jf[i]) {
566                         int off = bpf_find_insns_offset(labels_jf[i]);
567                         out[i].jf = (uint8_t) (off - i - 1);
568                 }
569         }
570 }
571
572 static void bpf_stage_2_reduce_labels(void)
573 {
574         bpf_reduce_k_jumps();
575         bpf_reduce_jt_jumps();
576         bpf_reduce_jf_jumps();
577 }
578
579 static void bpf_pretty_print_c(void)
580 {
581         int i;
582
583         for (i = 0; i < curr_instr; i++)
584                 printf("{ %#04x, %2u, %2u, %#010x },\n", out[i].code,
585                        out[i].jt, out[i].jf, out[i].k);
586 }
587
588 static void bpf_pretty_print(void)
589 {
590         int i;
591
592         printf("%u,", curr_instr);
593         for (i = 0; i < curr_instr; i++)
594                 printf("%u %u %u %u,", out[i].code,
595                        out[i].jt, out[i].jf, out[i].k);
596         printf("\n");
597 }
598
599 static void bpf_init(void)
600 {
601         memset(out, 0, sizeof(out));
602
603         labels = calloc(BPF_MAXINSNS, sizeof(*labels));
604         assert(labels);
605         labels_jt = calloc(BPF_MAXINSNS, sizeof(*labels_jt));
606         assert(labels_jt);
607         labels_jf = calloc(BPF_MAXINSNS, sizeof(*labels_jf));
608         assert(labels_jf);
609         labels_k = calloc(BPF_MAXINSNS, sizeof(*labels_k));
610         assert(labels_k);
611 }
612
613 static void bpf_destroy_labels(void)
614 {
615         int i;
616
617         for (i = 0; i < curr_instr; i++) {
618                 free(labels_jf[i]);
619                 free(labels_jt[i]);
620                 free(labels_k[i]);
621                 free(labels[i]);
622         }
623 }
624
625 static void bpf_destroy(void)
626 {
627         bpf_destroy_labels();
628         free(labels_jt);
629         free(labels_jf);
630         free(labels_k);
631         free(labels);
632 }
633
634 void bpf_asm_compile(FILE *fp, bool cstyle)
635 {
636         yyin = fp;
637
638         bpf_init();
639         bpf_stage_1_insert_insns();
640         bpf_stage_2_reduce_labels();
641         bpf_destroy();
642
643         if (cstyle)
644                 bpf_pretty_print_c();
645         else
646                 bpf_pretty_print();
647
648         if (fp != stdin)
649                 fclose(yyin);
650 }
651
652 void yyerror(const char *str)
653 {
654         fprintf(stderr, "error: %s at line %d\n", str, yylineno);
655         exit(1);
656 }