1 | /* |
---|
2 | * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996 |
---|
3 | * The Regents of the University of California. All rights reserved. |
---|
4 | * |
---|
5 | * Redistribution and use in source and binary forms, with or without |
---|
6 | * modification, are permitted provided that: (1) source code distributions |
---|
7 | * retain the above copyright notice and this paragraph in its entirety, (2) |
---|
8 | * distributions including binary code include the above copyright notice and |
---|
9 | * this paragraph in its entirety in the documentation or other materials |
---|
10 | * provided with the distribution, and (3) all advertising materials mentioning |
---|
11 | * features or use of this software display the following acknowledgement: |
---|
12 | * ``This product includes software developed by the University of California, |
---|
13 | * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of |
---|
14 | * the University nor the names of its contributors may be used to endorse |
---|
15 | * or promote products derived from this software without specific prior |
---|
16 | * written permission. |
---|
17 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED |
---|
18 | * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF |
---|
19 | * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. |
---|
20 | */ |
---|
21 | |
---|
22 | /* |
---|
23 | * ATM support: |
---|
24 | * |
---|
25 | * Copyright (c) 1997 Yen Yen Lim and North Dakota State University |
---|
26 | * All rights reserved. |
---|
27 | * |
---|
28 | * Redistribution and use in source and binary forms, with or without |
---|
29 | * modification, are permitted provided that the following conditions |
---|
30 | * are met: |
---|
31 | * 1. Redistributions of source code must retain the above copyright |
---|
32 | * notice, this list of conditions and the following disclaimer. |
---|
33 | * 2. Redistributions in binary form must reproduce the above copyright |
---|
34 | * notice, this list of conditions and the following disclaimer in the |
---|
35 | * documentation and/or other materials provided with the distribution. |
---|
36 | * 3. All advertising materials mentioning features or use of this software |
---|
37 | * must display the following acknowledgement: |
---|
38 | * This product includes software developed by Yen Yen Lim and |
---|
39 | * North Dakota State University |
---|
40 | * 4. The name of the author may not be used to endorse or promote products |
---|
41 | * derived from this software without specific prior written permission. |
---|
42 | * |
---|
43 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
---|
44 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
---|
45 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
---|
46 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, |
---|
47 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
---|
48 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
---|
49 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
---|
50 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
---|
51 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN |
---|
52 | * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
---|
53 | * POSSIBILITY OF SUCH DAMAGE. |
---|
54 | */ |
---|
55 | |
---|
56 | #ifndef HAVE___ATTRIBUTE__ |
---|
57 | #define __attribute__(x) |
---|
58 | #endif /* HAVE___ATTRIBUTE__ */ |
---|
59 | |
---|
60 | /* Address qualifiers. */ |
---|
61 | |
---|
62 | #define Q_HOST 1 |
---|
63 | #define Q_NET 2 |
---|
64 | #define Q_PORT 3 |
---|
65 | #define Q_GATEWAY 4 |
---|
66 | #define Q_PROTO 5 |
---|
67 | #define Q_PROTOCHAIN 6 |
---|
68 | #define Q_PORTRANGE 7 |
---|
69 | |
---|
70 | /* Protocol qualifiers. */ |
---|
71 | |
---|
72 | #define Q_LINK 1 |
---|
73 | #define Q_IP 2 |
---|
74 | #define Q_ARP 3 |
---|
75 | #define Q_RARP 4 |
---|
76 | #define Q_SCTP 5 |
---|
77 | #define Q_TCP 6 |
---|
78 | #define Q_UDP 7 |
---|
79 | #define Q_ICMP 8 |
---|
80 | #define Q_IGMP 9 |
---|
81 | #define Q_IGRP 10 |
---|
82 | |
---|
83 | |
---|
84 | #define Q_ATALK 11 |
---|
85 | #define Q_DECNET 12 |
---|
86 | #define Q_LAT 13 |
---|
87 | #define Q_SCA 14 |
---|
88 | #define Q_MOPRC 15 |
---|
89 | #define Q_MOPDL 16 |
---|
90 | |
---|
91 | |
---|
92 | #define Q_IPV6 17 |
---|
93 | #define Q_ICMPV6 18 |
---|
94 | #define Q_AH 19 |
---|
95 | #define Q_ESP 20 |
---|
96 | |
---|
97 | #define Q_PIM 21 |
---|
98 | #define Q_VRRP 22 |
---|
99 | |
---|
100 | #define Q_AARP 23 |
---|
101 | |
---|
102 | #define Q_ISO 24 |
---|
103 | #define Q_ESIS 25 |
---|
104 | #define Q_ISIS 26 |
---|
105 | #define Q_CLNP 27 |
---|
106 | |
---|
107 | #define Q_STP 28 |
---|
108 | |
---|
109 | #define Q_IPX 29 |
---|
110 | |
---|
111 | #define Q_NETBEUI 30 |
---|
112 | |
---|
113 | /* IS-IS Levels */ |
---|
114 | #define Q_ISIS_L1 31 |
---|
115 | #define Q_ISIS_L2 32 |
---|
116 | /* PDU types */ |
---|
117 | #define Q_ISIS_IIH 33 |
---|
118 | #define Q_ISIS_LAN_IIH 34 |
---|
119 | #define Q_ISIS_PTP_IIH 35 |
---|
120 | #define Q_ISIS_SNP 36 |
---|
121 | #define Q_ISIS_CSNP 37 |
---|
122 | #define Q_ISIS_PSNP 38 |
---|
123 | #define Q_ISIS_LSP 39 |
---|
124 | |
---|
125 | #define Q_RADIO 40 |
---|
126 | |
---|
127 | #define Q_CARP 41 |
---|
128 | |
---|
129 | /* Directional qualifiers. */ |
---|
130 | |
---|
131 | #define Q_SRC 1 |
---|
132 | #define Q_DST 2 |
---|
133 | #define Q_OR 3 |
---|
134 | #define Q_AND 4 |
---|
135 | #define Q_ADDR1 5 |
---|
136 | #define Q_ADDR2 6 |
---|
137 | #define Q_ADDR3 7 |
---|
138 | #define Q_ADDR4 8 |
---|
139 | #define Q_RA 9 |
---|
140 | #define Q_TA 10 |
---|
141 | |
---|
142 | #define Q_DEFAULT 0 |
---|
143 | #define Q_UNDEF 255 |
---|
144 | |
---|
145 | /* ATM types */ |
---|
146 | #define A_METAC 22 /* Meta signalling Circuit */ |
---|
147 | #define A_BCC 23 /* Broadcast Circuit */ |
---|
148 | #define A_OAMF4SC 24 /* Segment OAM F4 Circuit */ |
---|
149 | #define A_OAMF4EC 25 /* End-to-End OAM F4 Circuit */ |
---|
150 | #define A_SC 26 /* Signalling Circuit*/ |
---|
151 | #define A_ILMIC 27 /* ILMI Circuit */ |
---|
152 | #define A_OAM 28 /* OAM cells : F4 only */ |
---|
153 | #define A_OAMF4 29 /* OAM F4 cells: Segment + End-to-end */ |
---|
154 | #define A_LANE 30 /* LANE traffic */ |
---|
155 | #define A_LLC 31 /* LLC-encapsulated traffic */ |
---|
156 | |
---|
157 | /* Based on Q.2931 signalling protocol */ |
---|
158 | #define A_SETUP 41 /* Setup message */ |
---|
159 | #define A_CALLPROCEED 42 /* Call proceeding message */ |
---|
160 | #define A_CONNECT 43 /* Connect message */ |
---|
161 | #define A_CONNECTACK 44 /* Connect Ack message */ |
---|
162 | #define A_RELEASE 45 /* Release message */ |
---|
163 | #define A_RELEASE_DONE 46 /* Release message */ |
---|
164 | |
---|
165 | /* ATM field types */ |
---|
166 | #define A_VPI 51 |
---|
167 | #define A_VCI 52 |
---|
168 | #define A_PROTOTYPE 53 |
---|
169 | #define A_MSGTYPE 54 |
---|
170 | #define A_CALLREFTYPE 55 |
---|
171 | |
---|
172 | #define A_CONNECTMSG 70 /* returns Q.2931 signalling messages for |
---|
173 | establishing and destroying switched |
---|
174 | virtual connection */ |
---|
175 | #define A_METACONNECT 71 /* returns Q.2931 signalling messages for |
---|
176 | establishing and destroying predefined |
---|
177 | virtual circuits, such as broadcast |
---|
178 | circuit, oamf4 segment circuit, oamf4 |
---|
179 | end-to-end circuits, ILMI circuits or |
---|
180 | connection signalling circuit. */ |
---|
181 | |
---|
182 | /* MTP2 types */ |
---|
183 | #define M_FISU 22 /* FISU */ |
---|
184 | #define M_LSSU 23 /* LSSU */ |
---|
185 | #define M_MSU 24 /* MSU */ |
---|
186 | |
---|
187 | /* MTP2 HSL types */ |
---|
188 | #define MH_FISU 25 /* FISU for HSL */ |
---|
189 | #define MH_LSSU 26 /* LSSU */ |
---|
190 | #define MH_MSU 27 /* MSU */ |
---|
191 | |
---|
192 | /* MTP3 field types */ |
---|
193 | #define M_SIO 1 |
---|
194 | #define M_OPC 2 |
---|
195 | #define M_DPC 3 |
---|
196 | #define M_SLS 4 |
---|
197 | |
---|
198 | /* MTP3 field types in case of MTP2 HSL */ |
---|
199 | #define MH_SIO 5 |
---|
200 | #define MH_OPC 6 |
---|
201 | #define MH_DPC 7 |
---|
202 | #define MH_SLS 8 |
---|
203 | |
---|
204 | |
---|
205 | struct slist; |
---|
206 | |
---|
207 | struct stmt { |
---|
208 | int code; |
---|
209 | struct slist *jt; /*only for relative jump in block*/ |
---|
210 | struct slist *jf; /*only for relative jump in block*/ |
---|
211 | bpf_int32 k; |
---|
212 | }; |
---|
213 | |
---|
214 | struct slist { |
---|
215 | struct stmt s; |
---|
216 | struct slist *next; |
---|
217 | }; |
---|
218 | |
---|
219 | /* |
---|
220 | * A bit vector to represent definition sets. We assume TOT_REGISTERS |
---|
221 | * is smaller than 8*sizeof(atomset). |
---|
222 | */ |
---|
223 | typedef bpf_u_int32 atomset; |
---|
224 | #define ATOMMASK(n) (1 << (n)) |
---|
225 | #define ATOMELEM(d, n) (d & ATOMMASK(n)) |
---|
226 | |
---|
227 | /* |
---|
228 | * An unbounded set. |
---|
229 | */ |
---|
230 | typedef bpf_u_int32 *uset; |
---|
231 | |
---|
232 | /* |
---|
233 | * Total number of atomic entities, including accumulator (A) and index (X). |
---|
234 | * We treat all these guys similarly during flow analysis. |
---|
235 | */ |
---|
236 | #define N_ATOMS (BPF_MEMWORDS+2) |
---|
237 | |
---|
238 | struct edge { |
---|
239 | int id; |
---|
240 | int code; |
---|
241 | uset edom; |
---|
242 | struct block *succ; |
---|
243 | struct block *pred; |
---|
244 | struct edge *next; /* link list of incoming edges for a node */ |
---|
245 | }; |
---|
246 | |
---|
247 | struct block { |
---|
248 | int id; |
---|
249 | struct slist *stmts; /* side effect stmts */ |
---|
250 | struct stmt s; /* branch stmt */ |
---|
251 | int mark; |
---|
252 | u_int longjt; /* jt branch requires long jump */ |
---|
253 | u_int longjf; /* jf branch requires long jump */ |
---|
254 | int level; |
---|
255 | int offset; |
---|
256 | int sense; |
---|
257 | struct edge et; |
---|
258 | struct edge ef; |
---|
259 | struct block *head; |
---|
260 | struct block *link; /* link field used by optimizer */ |
---|
261 | uset dom; |
---|
262 | uset closure; |
---|
263 | struct edge *in_edges; |
---|
264 | atomset def, kill; |
---|
265 | atomset in_use; |
---|
266 | atomset out_use; |
---|
267 | int oval; |
---|
268 | int val[N_ATOMS]; |
---|
269 | }; |
---|
270 | |
---|
271 | struct arth { |
---|
272 | struct block *b; /* protocol checks */ |
---|
273 | struct slist *s; /* stmt list */ |
---|
274 | int regno; /* virtual register number of result */ |
---|
275 | }; |
---|
276 | |
---|
277 | struct qual { |
---|
278 | unsigned char addr; |
---|
279 | unsigned char proto; |
---|
280 | unsigned char dir; |
---|
281 | unsigned char pad; |
---|
282 | }; |
---|
283 | |
---|
284 | struct _compiler_state; |
---|
285 | |
---|
286 | typedef struct _compiler_state compiler_state_t; |
---|
287 | |
---|
288 | struct arth *gen_loadi(compiler_state_t *, int); |
---|
289 | struct arth *gen_load(compiler_state_t *, int, struct arth *, int); |
---|
290 | struct arth *gen_loadlen(compiler_state_t *); |
---|
291 | struct arth *gen_neg(compiler_state_t *, struct arth *); |
---|
292 | struct arth *gen_arth(compiler_state_t *, int, struct arth *, struct arth *); |
---|
293 | |
---|
294 | void gen_and(struct block *, struct block *); |
---|
295 | void gen_or(struct block *, struct block *); |
---|
296 | void gen_not(struct block *); |
---|
297 | |
---|
298 | struct block *gen_scode(compiler_state_t *, const char *, struct qual); |
---|
299 | struct block *gen_ecode(compiler_state_t *, const u_char *, struct qual); |
---|
300 | struct block *gen_acode(compiler_state_t *, const u_char *, struct qual); |
---|
301 | struct block *gen_mcode(compiler_state_t *, const char *, const char *, |
---|
302 | unsigned int, struct qual); |
---|
303 | #ifdef INET6 |
---|
304 | struct block *gen_mcode6(compiler_state_t *, const char *, const char *, |
---|
305 | unsigned int, struct qual); |
---|
306 | #endif |
---|
307 | struct block *gen_ncode(compiler_state_t *, const char *, bpf_u_int32, |
---|
308 | struct qual); |
---|
309 | struct block *gen_proto_abbrev(compiler_state_t *, int); |
---|
310 | struct block *gen_relation(compiler_state_t *, int, struct arth *, |
---|
311 | struct arth *, int); |
---|
312 | struct block *gen_less(compiler_state_t *, int); |
---|
313 | struct block *gen_greater(compiler_state_t *, int); |
---|
314 | struct block *gen_byteop(compiler_state_t *, int, int, int); |
---|
315 | struct block *gen_broadcast(compiler_state_t *, int); |
---|
316 | struct block *gen_multicast(compiler_state_t *, int); |
---|
317 | struct block *gen_inbound(compiler_state_t *, int); |
---|
318 | |
---|
319 | struct block *gen_llc(compiler_state_t *); |
---|
320 | struct block *gen_llc_i(compiler_state_t *); |
---|
321 | struct block *gen_llc_s(compiler_state_t *); |
---|
322 | struct block *gen_llc_u(compiler_state_t *); |
---|
323 | struct block *gen_llc_s_subtype(compiler_state_t *, bpf_u_int32); |
---|
324 | struct block *gen_llc_u_subtype(compiler_state_t *, bpf_u_int32); |
---|
325 | |
---|
326 | struct block *gen_vlan(compiler_state_t *, int); |
---|
327 | struct block *gen_mpls(compiler_state_t *, int); |
---|
328 | |
---|
329 | struct block *gen_pppoed(compiler_state_t *); |
---|
330 | struct block *gen_pppoes(compiler_state_t *, int); |
---|
331 | |
---|
332 | struct block *gen_geneve(compiler_state_t *, int); |
---|
333 | |
---|
334 | struct block *gen_atmfield_code(compiler_state_t *, int, bpf_int32, |
---|
335 | bpf_u_int32, int); |
---|
336 | struct block *gen_atmtype_abbrev(compiler_state_t *, int type); |
---|
337 | struct block *gen_atmmulti_abbrev(compiler_state_t *, int type); |
---|
338 | |
---|
339 | struct block *gen_mtp2type_abbrev(compiler_state_t *, int type); |
---|
340 | struct block *gen_mtp3field_code(compiler_state_t *, int, bpf_u_int32, |
---|
341 | bpf_u_int32, int); |
---|
342 | |
---|
343 | struct block *gen_pf_ifname(compiler_state_t *, const char *); |
---|
344 | struct block *gen_pf_rnr(compiler_state_t *, int); |
---|
345 | struct block *gen_pf_srnr(compiler_state_t *, int); |
---|
346 | struct block *gen_pf_ruleset(compiler_state_t *, char *); |
---|
347 | struct block *gen_pf_reason(compiler_state_t *, int); |
---|
348 | struct block *gen_pf_action(compiler_state_t *, int); |
---|
349 | |
---|
350 | struct block *gen_p80211_type(compiler_state_t *, int, int); |
---|
351 | struct block *gen_p80211_fcdir(compiler_state_t *, int); |
---|
352 | |
---|
353 | /* |
---|
354 | * Representation of a program as a tree of blocks, plus current mark. |
---|
355 | * A block is marked if only if its mark equals the current mark. |
---|
356 | * Rather than traverse the code array, marking each item, 'cur_mark' |
---|
357 | * is incremented. This automatically makes each element unmarked. |
---|
358 | */ |
---|
359 | #define isMarked(icp, p) ((p)->mark == (icp)->cur_mark) |
---|
360 | #define unMarkAll(icp) (icp)->cur_mark += 1 |
---|
361 | #define Mark(icp, p) ((p)->mark = (icp)->cur_mark) |
---|
362 | |
---|
363 | struct icode { |
---|
364 | struct block *root; |
---|
365 | int cur_mark; |
---|
366 | }; |
---|
367 | |
---|
368 | void bpf_optimize(compiler_state_t *, struct icode *ic); |
---|
369 | void bpf_syntax_error(compiler_state_t *, const char *); |
---|
370 | void bpf_error(compiler_state_t *, const char *, ...) |
---|
371 | __attribute__((noreturn)) |
---|
372 | #ifdef __ATTRIBUTE___FORMAT_OK |
---|
373 | __attribute__((format (printf, 2, 3))) |
---|
374 | #endif /* __ATTRIBUTE___FORMAT_OK */ |
---|
375 | ; |
---|
376 | |
---|
377 | void finish_parse(compiler_state_t *, struct block *); |
---|
378 | char *sdup(compiler_state_t *, const char *); |
---|
379 | |
---|
380 | struct _opt_state; |
---|
381 | typedef struct _opt_state opt_state_t; |
---|
382 | |
---|
383 | struct bpf_insn *icode_to_fcode(compiler_state_t *, struct icode *, |
---|
384 | struct block *, u_int *); |
---|
385 | void sappend(struct slist *, struct slist *); |
---|
386 | |
---|
387 | /* |
---|
388 | * Older versions of Bison don't put this declaration in |
---|
389 | * grammar.h. |
---|
390 | */ |
---|
391 | int pcap_parse(void *, compiler_state_t *); |
---|
392 | |
---|
393 | /* XXX */ |
---|
394 | #define JT(b) ((b)->et.succ) |
---|
395 | #define JF(b) ((b)->ef.succ) |
---|