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