filter/filter.h

   1 /*
   2  *      BIRD Internet Routing Daemon -- Filters
   3  *
   4  *      (c) 1999 Pavel Machek <pavel@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #ifndef _BIRD_FILT_H_
  10 #define _BIRD_FILT_H_
  11
  12 #include "lib/resource.h"
  13 #include "lib/ip.h"
  14 #include "nest/route.h"
  15 #include "nest/attrs.h"
  16
  17 /* Filter instruction types */
  18
  19 #define FI__TWOCHAR(a,b)        ((a<<8) | b)
  20 #define FI__LIST \
  21   F(FI_ADD,                       0, '+') \
  22   F(FI_SUBTRACT,                  0, '-') \
  23   F(FI_MULTIPLY,                  0, '*') \
  24   F(FI_DIVIDE,                    0, '/') \
  25   F(FI_AND,                       0, '&') \
  26   F(FI_OR,                        0, '|') \
  27   F(FI_PAIR_CONSTRUCT,          'm', 'p') \
  28   F(FI_EC_CONSTRUCT,            'm', 'c') \
  29   F(FI_LC_CONSTRUCT,            'm', 'l') \
  30   F(FI_PATHMASK_CONSTRUCT,      'm', 'P') \
  31   F(FI_NEQ,                     '!', '=') \
  32   F(FI_EQ,                      '=', '=') \
  33   F(FI_LT,                        0, '<') \
  34   F(FI_LTE,                     '<', '=') \
  35   F(FI_NOT,                       0, '!') \
  36   F(FI_MATCH,                     0, '~') \
  37   F(FI_NOT_MATCH,               '!', '~') \
  38   F(FI_DEFINED,                 'd', 'e') \
  39   F(FI_SET,                       0, 's') \
  40   F(FI_CONSTANT,                  0, 'c') \
  41   F(FI_VARIABLE,                  0, 'V') \
  42   F(FI_CONSTANT_INDIRECT,         0, 'C') \
  43   F(FI_PRINT,                     0, 'p') \
  44   F(FI_CONDITION,                 0, '?') \
  45   F(FI_NOP,                       0, '0') \
  46   F(FI_PRINT_AND_DIE,           'p', ',') \
  47   F(FI_RTA_GET,                   0, 'a') \
  48   F(FI_RTA_SET,                 'a', 'S') \
  49   F(FI_EA_GET,                  'e', 'a') \
  50   F(FI_EA_SET,                  'e', 'S') \
  51   F(FI_PREF_GET,                  0, 'P') \
  52   F(FI_PREF_SET,                'P', 'S') \
  53   F(FI_LENGTH,                    0, 'L') \
  54   F(FI_IP,                      'c', 'p') \
  55   F(FI_AS_PATH_FIRST,           'a', 'f') \
  56   F(FI_AS_PATH_LAST,            'a', 'l') \
  57   F(FI_AS_PATH_LAST_NAG,        'a', 'L') \
  58   F(FI_RETURN,                    0, 'r') \
  59   F(FI_CALL,                    'c', 'a') \
  60   F(FI_CLEAR_LOCAL_VARS,        'c', 'V') \
  61   F(FI_SWITCH,                  'S', 'W') \
  62   F(FI_IP_MASK,                 'i', 'M') \
  63   F(FI_EMPTY,                     0, 'E') \
  64   F(FI_PATH_PREPEND,            'A', 'p') \
  65   F(FI_CLIST_ADD_DEL,           'C', 'a') \
  66   F(FI_ROA_CHECK,               'R', 'C')
  67
  68 enum f_instruction_code {
  69 #define F(c,a,b) \
  70   c = FI__TWOCHAR(a,b),
  71 FI__LIST
  72 #undef F
  73 } PACKED;
  74
  75 struct f_inst {         /* Instruction */
  76   struct f_inst *next;  /* Structure is 16 bytes, anyway */
  77   enum f_instruction_code fi_code;
  78   u16 aux;
  79   union {
  80     int i;
  81     void *p;
  82   } a1;
  83   union {
  84     int i;
  85     void *p;
  86   } a2;
  87   int lineno;
  88 };
  89
  90 #define arg1 a1.p
  91 #define arg2 a2.p
  92
  93 /* Not enough fields in f_inst for three args used by roa_check() */
  94 struct f_inst_roa_check {
  95   struct f_inst i;
  96   struct roa_table_config *rtc;
  97 };
  98
  99 struct f_inst3 {
 100   struct f_inst i;
 101   union {
 102     int i;
 103     void *p;
 104   } a3;
 105 };
 106
 107 #define INST3(x) (((struct f_inst3 *) x)->a3)
 108
 109
 110 struct f_prefix {
 111   ip_addr ip;
 112   int len;
 113 #define LEN_MASK 0xff
 114 #define LEN_PLUS  0x1000000
 115 #define LEN_MINUS 0x2000000
 116 #define LEN_RANGE 0x4000000
 117   /* If range then prefix must be in range (len >> 16 & 0xff, len >> 8 & 0xff) */
 118 };
 119
 120 struct f_val {
 121   int type;
 122   union {
 123     uint i;
 124     u64 ec;
 125     lcomm lc;
 126     /*    ip_addr ip; Folded into prefix */
 127     struct f_prefix px;
 128     char *s;
 129     struct f_tree *t;
 130     struct f_trie *ti;
 131     struct adata *ad;
 132     struct f_path_mask *path_mask;
 133   } val;
 134 };
 135
 136 struct f_dynamic_attr {
 137   int type;
 138   int f_type;
 139   int ea_code;
 140 };
 141
 142 struct f_static_attr {
 143   int f_type;
 144   int sa_code;
 145   int readonly;
 146 };
 147
 148 struct filter {
 149   char *name;
 150   struct f_inst *root;
 151 };
 152
 153 struct f_inst *f_new_inst(enum f_instruction_code fi_code);
 154 struct f_inst *f_new_inst_da(enum f_instruction_code fi_code, struct f_dynamic_attr da);
 155 struct f_inst *f_new_inst_sa(enum f_instruction_code fi_code, struct f_static_attr sa);
 156 static inline struct f_dynamic_attr f_new_dynamic_attr(int type, int f_type, int code) /* Type as core knows it, type as filters know it, and code of dynamic attribute */
 157 { return (struct f_dynamic_attr) { .type = type, .f_type = f_type, .ea_code = code }; }   /* f_type currently unused; will be handy for static type checking */
 158 static inline struct f_static_attr f_new_static_attr(int f_type, int code, int readonly)
 159 { return (struct f_static_attr) { .f_type = f_type, .sa_code = code, .readonly = readonly }; }
 160 struct f_tree *f_new_tree(void);
 161 struct f_inst *f_generate_complex(int operation, int operation_aux, struct f_dynamic_attr da, struct f_inst *argument);
 162 struct f_inst *f_generate_roa_check(struct symbol *sym, struct f_inst *prefix, struct f_inst *asn);
 163
 164
 165 struct f_tree *build_tree(struct f_tree *);
 166 struct f_tree *find_tree(struct f_tree *t, struct f_val val);
 167 int same_tree(struct f_tree *t1, struct f_tree *t2);
 168 void tree_format(struct f_tree *t, buffer *buf);
 169
 170 struct f_trie *f_new_trie(linpool *lp, uint node_size);
 171 void *trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h);
 172 int trie_match_prefix(struct f_trie *t, ip_addr px, int plen);
 173 int trie_same(struct f_trie *t1, struct f_trie *t2);
 174 void trie_format(struct f_trie *t, buffer *buf);
 175
 176 void fprefix_get_bounds(struct f_prefix *px, int *l, int *h);
 177
 178 static inline void
 179 trie_add_fprefix(struct f_trie *t, struct f_prefix *px)
 180 {
 181   int l, h;
 182   fprefix_get_bounds(px, &l, &h);
 183   trie_add_prefix(t, px->ip, px->len & LEN_MASK, l, h);
 184 }
 185
 186 static inline int
 187 trie_match_fprefix(struct f_trie *t, struct f_prefix *px)
 188 {
 189   return trie_match_prefix(t, px->ip, px->len & LEN_MASK);
 190 }
 191
 192
 193 struct ea_list;
 194 struct rte;
 195
 196 int f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags);
 197 struct f_val f_eval_rte(struct f_inst *expr, struct rte **rte, struct linpool *tmp_pool);
 198 struct f_val f_eval(struct f_inst *expr, struct linpool *tmp_pool);
 199 uint f_eval_int(struct f_inst *expr);
 200
 201 char *filter_name(struct filter *filter);
 202 int filter_same(struct filter *new, struct filter *old);
 203
 204 int i_same(struct f_inst *f1, struct f_inst *f2);
 205
 206 int val_compare(struct f_val v1, struct f_val v2);
 207 int val_same(struct f_val v1, struct f_val v2);
 208
 209 void val_format(struct f_val v, buffer *buf);
 210
 211
 212 #define F_NOP 0
 213 #define F_NONL 1
 214 #define F_ACCEPT 2      /* Need to preserve ordering: accepts < rejects! */
 215 #define F_REJECT 3
 216 #define F_ERROR 4
 217 #define F_QUITBIRD 5
 218
 219 #define FILTER_ACCEPT NULL
 220 #define FILTER_REJECT ((void *) 1)
 221
 222 /* Type numbers must be in 0..0xff range */
 223 #define T_MASK 0xff
 224
 225 /* Internal types */
 226 /* Do not use type of zero, that way we'll see errors easier. */
 227 #define T_VOID 1
 228
 229 /* User visible types, which fit in int */
 230 #define T_INT 0x10
 231 #define T_BOOL 0x11
 232 #define T_PAIR 0x12  /* Notice that pair is stored as integer: first << 16 | second */
 233 #define T_QUAD 0x13
 234
 235 /* Put enumerational types in 0x30..0x3f range */
 236 #define T_ENUM_LO 0x30
 237 #define T_ENUM_HI 0x3f
 238
 239 #define T_ENUM_RTS 0x30
 240 #define T_ENUM_BGP_ORIGIN 0x31
 241 #define T_ENUM_SCOPE 0x32
 242 #define T_ENUM_RTC 0x33
 243 #define T_ENUM_RTD 0x34
 244 #define T_ENUM_ROA 0x35
 245 #define T_ENUM_RA_PREFERENCE 0x36
 246 /* new enums go here */
 247 #define T_ENUM_EMPTY 0x3f       /* Special hack for atomic_aggr */
 248
 249 #define T_ENUM T_ENUM_LO ... T_ENUM_HI
 250
 251 /* Bigger ones */
 252 #define T_IP 0x20
 253 #define T_PREFIX 0x21
 254 #define T_STRING 0x22
 255 #define T_PATH_MASK 0x23        /* mask for BGP path */
 256 #define T_PATH 0x24             /* BGP path */
 257 #define T_CLIST 0x25            /* Community list */
 258 #define T_EC 0x26               /* Extended community value, u64 */
 259 #define T_ECLIST 0x27           /* Extended community list */
 260 #define T_LC 0x28               /* Large community value, lcomm */
 261 #define T_LCLIST 0x29           /* Large community list */
 262
 263 #define T_RETURN 0x40
 264 #define T_SET 0x80
 265 #define T_PREFIX_SET 0x81
 266
 267
 268 #define SA_FROM          1
 269 #define SA_GW            2
 270 #define SA_NET           3
 271 #define SA_PROTO         4
 272 #define SA_SOURCE        5
 273 #define SA_SCOPE         6
 274 #define SA_CAST          7
 275 #define SA_DEST          8
 276 #define SA_IFNAME        9
 277 #define SA_IFINDEX      10
 278
 279
 280 struct f_tree {
 281   struct f_tree *left, *right;
 282   struct f_val from, to;
 283   void *data;
 284 };
 285
 286 struct f_trie_node
 287 {
 288   ip_addr addr, mask, accept;
 289   int plen;
 290   struct f_trie_node *c[2];
 291 };
 292
 293 struct f_trie
 294 {
 295   linpool *lp;
 296   int zero;
 297   uint node_size;
 298   struct f_trie_node root[0];           /* Root trie node follows */
 299 };
 300
 301 #define NEW_F_VAL struct f_val * val; val = cfg_alloc(sizeof(struct f_val));
 302
 303 #define FF_FORCE_TMPATTR 1              /* Force all attributes to be temporary */
 304 #define FF_SILENT 2                     /* Silent filter execution */
 305
 306 #endif