1335640Shselasky/* 2335640Shselasky * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996 3335640Shselasky * The Regents of the University of California. All rights reserved. 4335640Shselasky * 5335640Shselasky * Redistribution and use in source and binary forms, with or without 6335640Shselasky * modification, are permitted provided that: (1) source code distributions 7335640Shselasky * retain the above copyright notice and this paragraph in its entirety, (2) 8335640Shselasky * distributions including binary code include the above copyright notice and 9335640Shselasky * this paragraph in its entirety in the documentation or other materials 10335640Shselasky * provided with the distribution, and (3) all advertising materials mentioning 11335640Shselasky * features or use of this software display the following acknowledgement: 12335640Shselasky * ``This product includes software developed by the University of California, 13335640Shselasky * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of 14335640Shselasky * the University nor the names of its contributors may be used to endorse 15335640Shselasky * or promote products derived from this software without specific prior 16335640Shselasky * written permission. 17335640Shselasky * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 18335640Shselasky * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 19335640Shselasky * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 20335640Shselasky */ 21335640Shselasky 22335640Shselasky#include "pcap/funcattrs.h" 23335640Shselasky 24335640Shselasky/* 25335640Shselasky * ATM support: 26335640Shselasky * 27335640Shselasky * Copyright (c) 1997 Yen Yen Lim and North Dakota State University 28335640Shselasky * All rights reserved. 29335640Shselasky * 30335640Shselasky * Redistribution and use in source and binary forms, with or without 31335640Shselasky * modification, are permitted provided that the following conditions 32335640Shselasky * are met: 33335640Shselasky * 1. Redistributions of source code must retain the above copyright 34335640Shselasky * notice, this list of conditions and the following disclaimer. 35335640Shselasky * 2. Redistributions in binary form must reproduce the above copyright 36335640Shselasky * notice, this list of conditions and the following disclaimer in the 37335640Shselasky * documentation and/or other materials provided with the distribution. 38335640Shselasky * 3. All advertising materials mentioning features or use of this software 39335640Shselasky * must display the following acknowledgement: 40335640Shselasky * This product includes software developed by Yen Yen Lim and 41335640Shselasky * North Dakota State University 42335640Shselasky * 4. The name of the author may not be used to endorse or promote products 43335640Shselasky * derived from this software without specific prior written permission. 44335640Shselasky * 45335640Shselasky * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 46335640Shselasky * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 47335640Shselasky * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 48335640Shselasky * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 49335640Shselasky * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 50335640Shselasky * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 51335640Shselasky * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 52335640Shselasky * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 53335640Shselasky * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 54335640Shselasky * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 55335640Shselasky * POSSIBILITY OF SUCH DAMAGE. 56335640Shselasky */ 57335640Shselasky 58335640Shselasky/* Address qualifiers. */ 59335640Shselasky 60335640Shselasky#define Q_HOST 1 61335640Shselasky#define Q_NET 2 62335640Shselasky#define Q_PORT 3 63335640Shselasky#define Q_GATEWAY 4 64335640Shselasky#define Q_PROTO 5 65335640Shselasky#define Q_PROTOCHAIN 6 66335640Shselasky#define Q_PORTRANGE 7 67335640Shselasky 68335640Shselasky/* Protocol qualifiers. */ 69335640Shselasky 70335640Shselasky#define Q_LINK 1 71335640Shselasky#define Q_IP 2 72335640Shselasky#define Q_ARP 3 73335640Shselasky#define Q_RARP 4 74335640Shselasky#define Q_SCTP 5 75335640Shselasky#define Q_TCP 6 76335640Shselasky#define Q_UDP 7 77335640Shselasky#define Q_ICMP 8 78335640Shselasky#define Q_IGMP 9 79335640Shselasky#define Q_IGRP 10 80335640Shselasky 81335640Shselasky 82335640Shselasky#define Q_ATALK 11 83335640Shselasky#define Q_DECNET 12 84335640Shselasky#define Q_LAT 13 85335640Shselasky#define Q_SCA 14 86335640Shselasky#define Q_MOPRC 15 87335640Shselasky#define Q_MOPDL 16 88335640Shselasky 89335640Shselasky 90335640Shselasky#define Q_IPV6 17 91335640Shselasky#define Q_ICMPV6 18 92335640Shselasky#define Q_AH 19 93335640Shselasky#define Q_ESP 20 94335640Shselasky 95335640Shselasky#define Q_PIM 21 96335640Shselasky#define Q_VRRP 22 97335640Shselasky 98335640Shselasky#define Q_AARP 23 99335640Shselasky 100335640Shselasky#define Q_ISO 24 101335640Shselasky#define Q_ESIS 25 102335640Shselasky#define Q_ISIS 26 103335640Shselasky#define Q_CLNP 27 104335640Shselasky 105335640Shselasky#define Q_STP 28 106335640Shselasky 107335640Shselasky#define Q_IPX 29 108335640Shselasky 109335640Shselasky#define Q_NETBEUI 30 110335640Shselasky 111335640Shselasky/* IS-IS Levels */ 112335640Shselasky#define Q_ISIS_L1 31 113335640Shselasky#define Q_ISIS_L2 32 114335640Shselasky/* PDU types */ 115335640Shselasky#define Q_ISIS_IIH 33 116356341Scy#define Q_ISIS_SNP 34 117356341Scy#define Q_ISIS_CSNP 35 118356341Scy#define Q_ISIS_PSNP 36 119356341Scy#define Q_ISIS_LSP 37 120335640Shselasky 121356341Scy#define Q_RADIO 38 122335640Shselasky 123356341Scy#define Q_CARP 39 124335640Shselasky 125335640Shselasky/* Directional qualifiers. */ 126335640Shselasky 127335640Shselasky#define Q_SRC 1 128335640Shselasky#define Q_DST 2 129335640Shselasky#define Q_OR 3 130335640Shselasky#define Q_AND 4 131335640Shselasky#define Q_ADDR1 5 132335640Shselasky#define Q_ADDR2 6 133335640Shselasky#define Q_ADDR3 7 134335640Shselasky#define Q_ADDR4 8 135335640Shselasky#define Q_RA 9 136335640Shselasky#define Q_TA 10 137335640Shselasky 138335640Shselasky#define Q_DEFAULT 0 139335640Shselasky#define Q_UNDEF 255 140335640Shselasky 141335640Shselasky/* ATM types */ 142335640Shselasky#define A_METAC 22 /* Meta signalling Circuit */ 143335640Shselasky#define A_BCC 23 /* Broadcast Circuit */ 144335640Shselasky#define A_OAMF4SC 24 /* Segment OAM F4 Circuit */ 145335640Shselasky#define A_OAMF4EC 25 /* End-to-End OAM F4 Circuit */ 146335640Shselasky#define A_SC 26 /* Signalling Circuit*/ 147335640Shselasky#define A_ILMIC 27 /* ILMI Circuit */ 148335640Shselasky#define A_OAM 28 /* OAM cells : F4 only */ 149335640Shselasky#define A_OAMF4 29 /* OAM F4 cells: Segment + End-to-end */ 150335640Shselasky#define A_LANE 30 /* LANE traffic */ 151335640Shselasky#define A_LLC 31 /* LLC-encapsulated traffic */ 152335640Shselasky 153335640Shselasky/* Based on Q.2931 signalling protocol */ 154335640Shselasky#define A_SETUP 41 /* Setup message */ 155335640Shselasky#define A_CALLPROCEED 42 /* Call proceeding message */ 156335640Shselasky#define A_CONNECT 43 /* Connect message */ 157335640Shselasky#define A_CONNECTACK 44 /* Connect Ack message */ 158335640Shselasky#define A_RELEASE 45 /* Release message */ 159335640Shselasky#define A_RELEASE_DONE 46 /* Release message */ 160335640Shselasky 161335640Shselasky/* ATM field types */ 162335640Shselasky#define A_VPI 51 163335640Shselasky#define A_VCI 52 164335640Shselasky#define A_PROTOTYPE 53 165335640Shselasky#define A_MSGTYPE 54 166335640Shselasky#define A_CALLREFTYPE 55 167335640Shselasky 168335640Shselasky#define A_CONNECTMSG 70 /* returns Q.2931 signalling messages for 169335640Shselasky establishing and destroying switched 170335640Shselasky virtual connection */ 171335640Shselasky#define A_METACONNECT 71 /* returns Q.2931 signalling messages for 172335640Shselasky establishing and destroying predefined 173335640Shselasky virtual circuits, such as broadcast 174335640Shselasky circuit, oamf4 segment circuit, oamf4 175335640Shselasky end-to-end circuits, ILMI circuits or 176335640Shselasky connection signalling circuit. */ 177335640Shselasky 178335640Shselasky/* MTP2 types */ 179335640Shselasky#define M_FISU 22 /* FISU */ 180335640Shselasky#define M_LSSU 23 /* LSSU */ 181335640Shselasky#define M_MSU 24 /* MSU */ 182335640Shselasky 183335640Shselasky/* MTP2 HSL types */ 184335640Shselasky#define MH_FISU 25 /* FISU for HSL */ 185335640Shselasky#define MH_LSSU 26 /* LSSU */ 186335640Shselasky#define MH_MSU 27 /* MSU */ 187335640Shselasky 188335640Shselasky/* MTP3 field types */ 189335640Shselasky#define M_SIO 1 190335640Shselasky#define M_OPC 2 191335640Shselasky#define M_DPC 3 192335640Shselasky#define M_SLS 4 193335640Shselasky 194335640Shselasky/* MTP3 field types in case of MTP2 HSL */ 195335640Shselasky#define MH_SIO 5 196335640Shselasky#define MH_OPC 6 197335640Shselasky#define MH_DPC 7 198335640Shselasky#define MH_SLS 8 199335640Shselasky 200335640Shselasky 201335640Shselaskystruct slist; 202335640Shselasky 203335640Shselaskystruct stmt { 204335640Shselasky int code; 205335640Shselasky struct slist *jt; /*only for relative jump in block*/ 206335640Shselasky struct slist *jf; /*only for relative jump in block*/ 207335640Shselasky bpf_int32 k; 208335640Shselasky}; 209335640Shselasky 210335640Shselaskystruct slist { 211335640Shselasky struct stmt s; 212335640Shselasky struct slist *next; 213335640Shselasky}; 214335640Shselasky 215335640Shselasky/* 216335640Shselasky * A bit vector to represent definition sets. We assume TOT_REGISTERS 217335640Shselasky * is smaller than 8*sizeof(atomset). 218335640Shselasky */ 219335640Shselaskytypedef bpf_u_int32 atomset; 220335640Shselasky#define ATOMMASK(n) (1 << (n)) 221335640Shselasky#define ATOMELEM(d, n) (d & ATOMMASK(n)) 222335640Shselasky 223335640Shselasky/* 224335640Shselasky * An unbounded set. 225335640Shselasky */ 226335640Shselaskytypedef bpf_u_int32 *uset; 227335640Shselasky 228335640Shselasky/* 229335640Shselasky * Total number of atomic entities, including accumulator (A) and index (X). 230335640Shselasky * We treat all these guys similarly during flow analysis. 231335640Shselasky */ 232335640Shselasky#define N_ATOMS (BPF_MEMWORDS+2) 233335640Shselasky 234335640Shselaskystruct edge { 235335640Shselasky int id; 236335640Shselasky int code; 237335640Shselasky uset edom; 238335640Shselasky struct block *succ; 239335640Shselasky struct block *pred; 240335640Shselasky struct edge *next; /* link list of incoming edges for a node */ 241335640Shselasky}; 242335640Shselasky 243335640Shselaskystruct block { 244335640Shselasky int id; 245335640Shselasky struct slist *stmts; /* side effect stmts */ 246335640Shselasky struct stmt s; /* branch stmt */ 247335640Shselasky int mark; 248335640Shselasky u_int longjt; /* jt branch requires long jump */ 249335640Shselasky u_int longjf; /* jf branch requires long jump */ 250335640Shselasky int level; 251335640Shselasky int offset; 252335640Shselasky int sense; 253335640Shselasky struct edge et; 254335640Shselasky struct edge ef; 255335640Shselasky struct block *head; 256335640Shselasky struct block *link; /* link field used by optimizer */ 257335640Shselasky uset dom; 258335640Shselasky uset closure; 259335640Shselasky struct edge *in_edges; 260335640Shselasky atomset def, kill; 261335640Shselasky atomset in_use; 262335640Shselasky atomset out_use; 263335640Shselasky int oval; 264335640Shselasky int val[N_ATOMS]; 265335640Shselasky}; 266335640Shselasky 267335640Shselasky/* 268335640Shselasky * A value of 0 for val[i] means the value is unknown. 269335640Shselasky */ 270335640Shselasky#define VAL_UNKNOWN 0 271335640Shselasky 272335640Shselaskystruct arth { 273335640Shselasky struct block *b; /* protocol checks */ 274335640Shselasky struct slist *s; /* stmt list */ 275335640Shselasky int regno; /* virtual register number of result */ 276335640Shselasky}; 277335640Shselasky 278335640Shselaskystruct qual { 279335640Shselasky unsigned char addr; 280335640Shselasky unsigned char proto; 281335640Shselasky unsigned char dir; 282335640Shselasky unsigned char pad; 283335640Shselasky}; 284335640Shselasky 285335640Shselaskystruct _compiler_state; 286335640Shselasky 287335640Shselaskytypedef struct _compiler_state compiler_state_t; 288335640Shselasky 289335640Shselaskystruct arth *gen_loadi(compiler_state_t *, int); 290335640Shselaskystruct arth *gen_load(compiler_state_t *, int, struct arth *, int); 291335640Shselaskystruct arth *gen_loadlen(compiler_state_t *); 292335640Shselaskystruct arth *gen_neg(compiler_state_t *, struct arth *); 293335640Shselaskystruct arth *gen_arth(compiler_state_t *, int, struct arth *, struct arth *); 294335640Shselasky 295335640Shselaskyvoid gen_and(struct block *, struct block *); 296335640Shselaskyvoid gen_or(struct block *, struct block *); 297335640Shselaskyvoid gen_not(struct block *); 298335640Shselasky 299335640Shselaskystruct block *gen_scode(compiler_state_t *, const char *, struct qual); 300356341Scystruct block *gen_ecode(compiler_state_t *, const char *, struct qual); 301356341Scystruct block *gen_acode(compiler_state_t *, const char *, struct qual); 302335640Shselaskystruct block *gen_mcode(compiler_state_t *, const char *, const char *, 303335640Shselasky unsigned int, struct qual); 304335640Shselasky#ifdef INET6 305335640Shselaskystruct block *gen_mcode6(compiler_state_t *, const char *, const char *, 306335640Shselasky unsigned int, struct qual); 307335640Shselasky#endif 308335640Shselaskystruct block *gen_ncode(compiler_state_t *, const char *, bpf_u_int32, 309335640Shselasky struct qual); 310335640Shselaskystruct block *gen_proto_abbrev(compiler_state_t *, int); 311335640Shselaskystruct block *gen_relation(compiler_state_t *, int, struct arth *, 312335640Shselasky struct arth *, int); 313335640Shselaskystruct block *gen_less(compiler_state_t *, int); 314335640Shselaskystruct block *gen_greater(compiler_state_t *, int); 315335640Shselaskystruct block *gen_byteop(compiler_state_t *, int, int, int); 316335640Shselaskystruct block *gen_broadcast(compiler_state_t *, int); 317335640Shselaskystruct block *gen_multicast(compiler_state_t *, int); 318335640Shselaskystruct block *gen_inbound(compiler_state_t *, int); 319335640Shselasky 320335640Shselaskystruct block *gen_llc(compiler_state_t *); 321335640Shselaskystruct block *gen_llc_i(compiler_state_t *); 322335640Shselaskystruct block *gen_llc_s(compiler_state_t *); 323335640Shselaskystruct block *gen_llc_u(compiler_state_t *); 324335640Shselaskystruct block *gen_llc_s_subtype(compiler_state_t *, bpf_u_int32); 325335640Shselaskystruct block *gen_llc_u_subtype(compiler_state_t *, bpf_u_int32); 326335640Shselasky 327356341Scystruct block *gen_vlan(compiler_state_t *, bpf_u_int32, int); 328356341Scystruct block *gen_mpls(compiler_state_t *, bpf_u_int32, int); 329335640Shselasky 330335640Shselaskystruct block *gen_pppoed(compiler_state_t *); 331356341Scystruct block *gen_pppoes(compiler_state_t *, bpf_u_int32, int); 332335640Shselasky 333356341Scystruct block *gen_geneve(compiler_state_t *, bpf_u_int32, int); 334335640Shselasky 335335640Shselaskystruct block *gen_atmfield_code(compiler_state_t *, int, bpf_int32, 336335640Shselasky bpf_u_int32, int); 337335640Shselaskystruct block *gen_atmtype_abbrev(compiler_state_t *, int type); 338335640Shselaskystruct block *gen_atmmulti_abbrev(compiler_state_t *, int type); 339335640Shselasky 340335640Shselaskystruct block *gen_mtp2type_abbrev(compiler_state_t *, int type); 341335640Shselaskystruct block *gen_mtp3field_code(compiler_state_t *, int, bpf_u_int32, 342335640Shselasky bpf_u_int32, int); 343335640Shselasky 344335640Shselaskystruct block *gen_pf_ifname(compiler_state_t *, const char *); 345335640Shselaskystruct block *gen_pf_rnr(compiler_state_t *, int); 346335640Shselaskystruct block *gen_pf_srnr(compiler_state_t *, int); 347335640Shselaskystruct block *gen_pf_ruleset(compiler_state_t *, char *); 348335640Shselaskystruct block *gen_pf_reason(compiler_state_t *, int); 349335640Shselaskystruct block *gen_pf_action(compiler_state_t *, int); 350335640Shselasky 351335640Shselaskystruct block *gen_p80211_type(compiler_state_t *, int, int); 352335640Shselaskystruct block *gen_p80211_fcdir(compiler_state_t *, int); 353335640Shselasky 354335640Shselasky/* 355335640Shselasky * Representation of a program as a tree of blocks, plus current mark. 356335640Shselasky * A block is marked if only if its mark equals the current mark. 357335640Shselasky * Rather than traverse the code array, marking each item, 'cur_mark' 358335640Shselasky * is incremented. This automatically makes each element unmarked. 359335640Shselasky */ 360335640Shselasky#define isMarked(icp, p) ((p)->mark == (icp)->cur_mark) 361335640Shselasky#define unMarkAll(icp) (icp)->cur_mark += 1 362335640Shselasky#define Mark(icp, p) ((p)->mark = (icp)->cur_mark) 363335640Shselasky 364335640Shselaskystruct icode { 365335640Shselasky struct block *root; 366335640Shselasky int cur_mark; 367335640Shselasky}; 368335640Shselasky 369356341Scyint bpf_optimize(struct icode *, char *); 370356341Scyvoid bpf_set_error(compiler_state_t *, const char *, ...) 371335640Shselasky PCAP_PRINTFLIKE(2, 3); 372335640Shselasky 373356341Scyint finish_parse(compiler_state_t *, struct block *); 374335640Shselaskychar *sdup(compiler_state_t *, const char *); 375335640Shselasky 376356341Scystruct bpf_insn *icode_to_fcode(struct icode *, struct block *, u_int *, 377356341Scy char *); 378335640Shselaskyvoid sappend(struct slist *, struct slist *); 379335640Shselasky 380335640Shselasky/* 381335640Shselasky * Older versions of Bison don't put this declaration in 382335640Shselasky * grammar.h. 383335640Shselasky */ 384335640Shselaskyint pcap_parse(void *, compiler_state_t *); 385335640Shselasky 386335640Shselasky/* XXX */ 387335640Shselasky#define JT(b) ((b)->et.succ) 388335640Shselasky#define JF(b) ((b)->ef.succ) 389