filter/data.h

   1 /*
   2  *      BIRD Internet Routing Daemon -- Dynamic data structures
   3  *
   4  *      (c) 1999 Pavel Machek <pavel@ucw.cz>
   5  *      (c) 2018--2019 Maria Matejka <mq@jmq.cz>
   6  *
   7  *      Can be freely distributed and used under the terms of the GNU GPL.
   8  */
   9
  10 #ifndef _BIRD_FILTER_DATA_H_
  11 #define _BIRD_FILTER_DATA_H_
  12
  13 #include "nest/bird.h"
  14 #include "nest/route.h"
  15
  16 /* Type numbers must be in 0..0xff range */
  17 #define T_MASK 0xff
  18
  19 /* Internal types */
  20 enum f_type {
  21 /* Nothing. Simply nothing. */
  22   T_VOID = 0,
  23
  24   T_NONE = 1,           /* Special hack to represent missing arguments */
  25
  26 /* User visible types, which fit in int */
  27   T_INT = 0x10,
  28   T_BOOL = 0x11,
  29   T_PAIR = 0x12,  /*    Notice that pair is stored as integer: first << 16 | second */
  30   T_QUAD = 0x13,
  31
  32 /* Put enumerational types in 0x30..0x3f range */
  33   T_ENUM_LO = 0x30,
  34   T_ENUM_HI = 0x3f,
  35
  36   T_ENUM_RTS = 0x30,
  37   T_ENUM_BGP_ORIGIN = 0x31,
  38   T_ENUM_SCOPE = 0x32,
  39   T_ENUM_RTC = 0x33,
  40   T_ENUM_RTD = 0x34,
  41   T_ENUM_ROA = 0x35,
  42   T_ENUM_NETTYPE = 0x36,
  43   T_ENUM_RA_PREFERENCE = 0x37,
  44   T_ENUM_AF = 0x38,
  45   T_ENUM_MPLS_POLICY = 0x39,
  46
  47 /* new enums go here */
  48   T_ENUM_EMPTY = 0x3f,  /* Special hack for atomic_aggr */
  49
  50 #define T_ENUM T_ENUM_LO ... T_ENUM_HI
  51
  52 /* Bigger ones */
  53   T_IP = 0x20,
  54   T_NET = 0x21,
  55   T_STRING = 0x22,
  56   T_PATH_MASK = 0x23,   /* mask for BGP path */
  57   T_PATH = 0x24,                /* BGP path */
  58   T_CLIST = 0x25,               /* Community list */
  59   T_EC = 0x26,          /* Extended community value, u64 */
  60   T_ECLIST = 0x27,              /* Extended community list */
  61   T_LC = 0x28,          /* Large community value, lcomm */
  62   T_LCLIST = 0x29,              /* Large community list */
  63   T_RD = 0x2a,          /* Route distinguisher for VPN addresses */
  64   T_PATH_MASK_ITEM = 0x2b,      /* Path mask item for path mask constructors */
  65   T_BYTESTRING = 0x2c,
  66
  67   T_ROUTE = 0x78,
  68   T_ROUTES_BLOCK = 0x79,
  69   T_SET = 0x80,
  70   T_PREFIX_SET = 0x81,
  71 } PACKED;
  72
  73 struct f_method {
  74   struct symbol *sym;
  75   struct f_inst *(*new_inst)(struct f_inst *obj, struct f_inst *args);
  76   const struct f_method *next;
  77   uint arg_num;
  78   enum f_type args_type[];
  79 };
  80
  81 /* Filter value; size of this affects filter memory consumption */
  82 struct f_val {
  83   enum f_type type;     /* T_*  */
  84   union {
  85     uint i;
  86     u64 ec;
  87     lcomm lc;
  88     ip_addr ip;
  89     const net_addr *net;
  90     const char *s;
  91     const struct adata *bs;
  92     const struct f_tree *t;
  93     const struct f_trie *ti;
  94     const struct adata *ad;
  95     const struct f_path_mask *path_mask;
  96     struct f_path_mask_item pmi;
  97     struct rte *rte;
  98   } val;
  99 };
 100
 101 /* Dynamic attribute definition (eattrs) */
 102 struct f_dynamic_attr {
 103   u8 type;              /* EA type (EAF_*) */
 104   u8 bit;               /* For bitfield accessors */
 105   enum f_type f_type;   /* Filter type */
 106   uint ea_code;         /* EA code */
 107   uint flags;
 108 };
 109
 110 enum f_sa_code {
 111   SA_FROM = 1,
 112   SA_GW,
 113   SA_NET,
 114   SA_PROTO,
 115   SA_SOURCE,
 116   SA_SCOPE,
 117   SA_DEST,
 118   SA_IFNAME,
 119   SA_IFINDEX,
 120   SA_WEIGHT,
 121   SA_PREF,
 122   SA_GW_MPLS,
 123   SA_ONLINK,
 124 } PACKED;
 125
 126 /* Static attribute definition (members of struct rta) */
 127 struct f_static_attr {
 128   enum f_type f_type;           /* Filter type */
 129   enum f_sa_code sa_code;       /* Static attribute id */
 130   int readonly:1;                       /* Don't allow writing */
 131 };
 132
 133 /* Filter l-value type */
 134 enum f_lval_type {
 135   F_LVAL_VARIABLE,
 136   F_LVAL_PREFERENCE,
 137   F_LVAL_SA,
 138   F_LVAL_EA,
 139 };
 140
 141 /* Filter l-value */
 142 struct f_lval {
 143   enum f_lval_type type;
 144   struct f_inst *rte;
 145   union {
 146     struct symbol *sym;
 147     struct f_dynamic_attr da;
 148     struct f_static_attr sa;
 149   };
 150 };
 151
 152 /* IP prefix range structure */
 153 struct f_prefix {
 154   net_addr net;         /* The matching prefix must match this net */
 155   u8 lo, hi;            /* And its length must fit between lo and hi */
 156 };
 157
 158 struct f_tree {
 159   struct f_tree *left, *right;
 160   struct f_val from, to;
 161   void *data;
 162 };
 163
 164 #ifdef ENABLE_COMPACT_TRIES
 165 /* Compact 4-way tries */
 166 #define TRIE_STEP               2
 167 #define TRIE_STACK_LENGTH       65
 168 #else
 169 /* Faster 16-way tries */
 170 #define TRIE_STEP               4
 171 #define TRIE_STACK_LENGTH       33
 172 #endif
 173
 174 struct f_trie_node4
 175 {
 176   ip4_addr addr, mask, accept;
 177   u16 plen;
 178   u16 local;
 179   struct f_trie_node4 *c[1 << TRIE_STEP];
 180 };
 181
 182 struct f_trie_node6
 183 {
 184   ip6_addr addr, mask, accept;
 185   u16 plen;
 186   u16 local;
 187   struct f_trie_node6 *c[1 << TRIE_STEP];
 188 };
 189
 190 struct f_trie_node
 191 {
 192   union {
 193     struct f_trie_node4 v4;
 194     struct f_trie_node6 v6;
 195   };
 196 };
 197
 198 struct f_trie
 199 {
 200   linpool *lp;
 201   u8 zero;
 202   s8 ipv4;                              /* -1 for undefined / empty */
 203   u16 data_size;                        /* Additional data for each trie node */
 204   u32 prefix_count;                     /* Works only for restricted tries (pxlen == l == h) */
 205   struct f_trie_node root;              /* Root trie node */
 206 };
 207
 208 struct f_trie_walk_state
 209 {
 210   u8 ipv4;
 211   u8 accept_length;                     /* Current inter-node prefix position */
 212   u8 start_pos;                         /* Initial prefix position in stack[0] */
 213   u8 local_pos;                         /* Current intra-node prefix position */
 214   u8 stack_pos;                         /* Current node in stack below */
 215   const struct f_trie_node *stack[TRIE_STACK_LENGTH];
 216 };
 217
 218 struct f_tree *f_new_tree(void);
 219 struct f_tree *build_tree(struct f_tree *);
 220 const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
 221 const struct f_tree *find_tree_linear(const struct f_tree *t, const struct f_val *val);
 222 int same_tree(const struct f_tree *t0, const struct f_tree *t2);
 223 int tree_node_count(const struct f_tree *t);
 224 void tree_format(const struct f_tree *t, buffer *buf);
 225 void tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void *), void *data);
 226
 227 struct f_trie *f_new_trie(linpool *lp, uint data_size);
 228 void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
 229 int trie_match_net(const struct f_trie *t, const net_addr *n);
 230 int trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0);
 231 int trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0);
 232 void trie_walk_init(struct f_trie_walk_state *s, const struct f_trie *t, const net_addr *from);
 233 int trie_walk_next(struct f_trie_walk_state *s, net_addr *net);
 234 int trie_same(const struct f_trie *t1, const struct f_trie *t2);
 235 void trie_format(const struct f_trie *t, buffer *buf);
 236
 237 static inline int
 238 trie_match_next_longest_ip4(net_addr_ip4 *n, ip4_addr *found)
 239 {
 240   while (n->pxlen)
 241   {
 242     n->pxlen--;
 243     ip4_clrbit(&n->prefix, n->pxlen);
 244
 245     if (ip4_getbit(*found, n->pxlen))
 246       return 1;
 247   }
 248
 249   return 0;
 250 }
 251
 252 static inline int
 253 trie_match_next_longest_ip6(net_addr_ip6 *n, ip6_addr *found)
 254 {
 255   while (n->pxlen)
 256   {
 257     n->pxlen--;
 258     ip6_clrbit(&n->prefix, n->pxlen);
 259
 260     if (ip6_getbit(*found, n->pxlen))
 261       return 1;
 262   }
 263
 264   return 0;
 265 }
 266
 267
 268 #define TRIE_WALK_TO_ROOT_IP4(trie, net, dst) ({                \
 269   net_addr_ip4 dst;                                             \
 270   ip4_addr _found;                                              \
 271   for (int _n = trie_match_longest_ip4(trie, net, &dst, &_found); \
 272        _n;                                                      \
 273        _n = trie_match_next_longest_ip4(&dst, &_found))
 274
 275 #define TRIE_WALK_TO_ROOT_IP6(trie, net, dst) ({                \
 276   net_addr_ip6 dst;                                             \
 277   ip6_addr _found;                                              \
 278   for (int _n = trie_match_longest_ip6(trie, net, &dst, &_found); \
 279        _n;                                                      \
 280        _n = trie_match_next_longest_ip6(&dst, &_found))
 281
 282 #define TRIE_WALK_TO_ROOT_END })
 283
 284
 285 #define TRIE_WALK(trie, net, from) ({                           \
 286   net_addr net;                                                 \
 287   struct f_trie_walk_state tws_;                                \
 288   trie_walk_init(&tws_, trie, from);                            \
 289   while (trie_walk_next(&tws_, &net))
 290
 291 #define TRIE_WALK_END })
 292
 293
 294 #define F_CMP_ERROR 999
 295
 296 const char *f_type_name(enum f_type t);
 297 enum f_type f_type_element_type(enum f_type t);
 298 struct sym_scope *f_type_method_scope(enum f_type t);
 299
 300 int val_same(const struct f_val *v1, const struct f_val *v2);
 301 int val_compare(const struct f_val *v1, const struct f_val *v2);
 302 void val_format(const struct f_val *v, buffer *buf);
 303 char *val_format_str(struct linpool *lp, const struct f_val *v);
 304 const char *val_dump(const struct f_val *v);
 305
 306 static inline int val_is_ip4(const struct f_val *v)
 307 { return (v->type == T_IP) && ipa_is_ip4(v->val.ip); }
 308 int val_in_range(const struct f_val *v1, const struct f_val *v2);
 309
 310 int clist_set_type(const struct f_tree *set, struct f_val *v);
 311 static inline int eclist_set_type(const struct f_tree *set)
 312 { return !set || set->from.type == T_EC; }
 313 static inline int lclist_set_type(const struct f_tree *set)
 314 { return !set || set->from.type == T_LC; }
 315 static inline int path_set_type(const struct f_tree *set)
 316 { return !set || set->from.type == T_INT; }
 317
 318 int clist_match_set(const struct adata *clist, const struct f_tree *set);
 319 int eclist_match_set(const struct adata *list, const struct f_tree *set);
 320 int lclist_match_set(const struct adata *list, const struct f_tree *set);
 321
 322 const struct adata *clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 323 const struct adata *eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 324 const struct adata *lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 325
 326
 327 /* Special undef value for paths and clists */
 328
 329 static inline int
 330 val_is_undefined(struct f_val v)
 331 {
 332   return ((v.type == T_PATH) || (v.type == T_CLIST) ||
 333           (v.type == T_ECLIST) || (v.type == T_LCLIST)) &&
 334     (v.val.ad == &null_adata);
 335 }
 336
 337 static inline struct f_val
 338 val_empty(enum f_type t)
 339 {
 340   switch (t)
 341   {
 342   case T_PATH:
 343   case T_CLIST:
 344   case T_ECLIST:
 345   case T_LCLIST:
 346     return (struct f_val) { .type = t, .val.ad = &null_adata };
 347
 348   default:
 349     return (struct f_val) { };
 350   }
 351 }
 352
 353
 354 extern const struct f_val f_const_empty_prefix_set;
 355
 356 enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres);
 357
 358 #endif