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 /* Do not use type of zero, that way we'll see errors easier. */
  21   T_VOID = 1,
  22
  23 /* User visible types, which fit in int */
  24   T_INT = 0x10,
  25   T_BOOL = 0x11,
  26   T_PAIR = 0x12,  /*    Notice that pair is stored as integer: first << 16 | second */
  27   T_QUAD = 0x13,
  28
  29 /* Put enumerational types in 0x30..0x3f range */
  30   T_ENUM_LO = 0x30,
  31   T_ENUM_HI = 0x3f,
  32
  33   T_ENUM_RTS = 0x30,
  34   T_ENUM_BGP_ORIGIN = 0x31,
  35   T_ENUM_SCOPE = 0x32,
  36   T_ENUM_RTC = 0x33,
  37   T_ENUM_RTD = 0x34,
  38   T_ENUM_ROA = 0x35,
  39   T_ENUM_NETTYPE = 0x36,
  40   T_ENUM_RA_PREFERENCE = 0x37,
  41
  42 /* new enums go here */
  43   T_ENUM_EMPTY = 0x3f,  /* Special hack for atomic_aggr */
  44
  45 #define T_ENUM T_ENUM_LO ... T_ENUM_HI
  46
  47 /* Bigger ones */
  48   T_IP = 0x20,
  49   T_NET = 0x21,
  50   T_STRING = 0x22,
  51   T_PATH_MASK = 0x23,   /* mask for BGP path */
  52   T_PATH = 0x24,                /* BGP path */
  53   T_CLIST = 0x25,               /* Community list */
  54   T_EC = 0x26,          /* Extended community value, u64 */
  55   T_ECLIST = 0x27,              /* Extended community list */
  56   T_LC = 0x28,          /* Large community value, lcomm */
  57   T_LCLIST = 0x29,              /* Large community list */
  58   T_RD = 0x2a,          /* Route distinguisher for VPN addresses */
  59   T_PATH_MASK_ITEM = 0x2b,      /* Path mask item for path mask constructors */
  60
  61   T_SET = 0x80,
  62   T_PREFIX_SET = 0x81,
  63 } PACKED;
  64
  65 /* Filter value; size of this affects filter memory consumption */
  66 struct f_val {
  67   enum f_type type;     /* T_*  */
  68   union {
  69     uint i;
  70     u64 ec;
  71     lcomm lc;
  72     ip_addr ip;
  73     const net_addr *net;
  74     char *s;
  75     const struct f_tree *t;
  76     const struct f_trie *ti;
  77     const struct adata *ad;
  78     const struct f_path_mask *path_mask;
  79     struct f_path_mask_item pmi;
  80   } val;
  81 };
  82
  83 /* Dynamic attribute definition (eattrs) */
  84 struct f_dynamic_attr {
  85   u8 type;              /* EA type (EAF_*) */
  86   u8 bit;               /* For bitfield accessors */
  87   enum f_type f_type;   /* Filter type */
  88   uint ea_code;         /* EA code */
  89 };
  90
  91 enum f_sa_code {
  92   SA_FROM = 1,
  93   SA_GW,
  94   SA_NET,
  95   SA_PROTO,
  96   SA_SOURCE,
  97   SA_SCOPE,
  98   SA_DEST,
  99   SA_IFNAME,
 100   SA_IFINDEX,
 101 } PACKED;
 102
 103 /* Static attribute definition (members of struct rta) */
 104 struct f_static_attr {
 105   enum f_type f_type;           /* Filter type */
 106   enum f_sa_code sa_code;       /* Static attribute id */
 107   int readonly:1;                       /* Don't allow writing */
 108 };
 109
 110 /* Filter l-value type */
 111 enum f_lval_type {
 112   F_LVAL_VARIABLE,
 113   F_LVAL_PREFERENCE,
 114   F_LVAL_SA,
 115   F_LVAL_EA,
 116 };
 117
 118 /* Filter l-value */
 119 struct f_lval {
 120   enum f_lval_type type;
 121   union {
 122     const struct symbol *sym;
 123     struct f_dynamic_attr da;
 124     struct f_static_attr sa;
 125   };
 126 };
 127
 128 /* IP prefix range structure */
 129 struct f_prefix {
 130   net_addr net;         /* The matching prefix must match this net */
 131   u8 lo, hi;            /* And its length must fit between lo and hi */
 132 };
 133
 134 struct f_tree {
 135   struct f_tree *left, *right;
 136   struct f_val from, to;
 137   void *data;
 138 };
 139
 140 struct f_trie_node
 141 {
 142   ip_addr addr, mask, accept;
 143   uint plen;
 144   struct f_trie_node *c[2];
 145 };
 146
 147 struct f_trie
 148 {
 149   linpool *lp;
 150   int zero;
 151   uint node_size;
 152   struct f_trie_node root[0];           /* Root trie node follows */
 153 };
 154
 155 struct f_tree *f_new_tree(void);
 156 struct f_tree *build_tree(struct f_tree *);
 157 const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
 158 int same_tree(const struct f_tree *t0, const struct f_tree *t2);
 159 void tree_format(const struct f_tree *t, buffer *buf);
 160
 161 struct f_trie *f_new_trie(linpool *lp, uint node_size);
 162 void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
 163 int trie_match_net(const struct f_trie *t, const net_addr *n);
 164 int trie_same(const struct f_trie *t1, const struct f_trie *t2);
 165 void trie_format(const struct f_trie *t, buffer *buf);
 166
 167 #define F_CMP_ERROR 999
 168
 169 int val_same(const struct f_val *v1, const struct f_val *v2);
 170 int val_compare(const struct f_val *v1, const struct f_val *v2);
 171 void val_format(const struct f_val *v, buffer *buf);
 172 const char *val_dump(const struct f_val *v);
 173
 174 static inline int val_is_ip4(const struct f_val *v)
 175 { return (v->type == T_IP) && ipa_is_ip4(v->val.ip); }
 176 int val_in_range(const struct f_val *v1, const struct f_val *v2);
 177
 178 int clist_set_type(const struct f_tree *set, struct f_val *v);
 179 static inline int eclist_set_type(const struct f_tree *set)
 180 { return set->from.type == T_EC; }
 181 static inline int lclist_set_type(const struct f_tree *set)
 182 { return set->from.type == T_LC; }
 183
 184 const struct adata *clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 185 const struct adata *eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 186 const struct adata *lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 187
 188
 189 /* Special undef value for paths and clists */
 190 static inline int
 191 undef_value(struct f_val v)
 192 {
 193   return ((v.type == T_PATH) || (v.type == T_CLIST) ||
 194           (v.type == T_ECLIST) || (v.type == T_LCLIST)) &&
 195     (v.val.ad == &null_adata);
 196 }
 197
 198 extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist;
 199
 200 enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres);
 201
 202 #endif