[thirdparty/bird.git] / filter / data.h

/*
 *	BIRD Internet Routing Daemon -- Dynamic data structures
 *
 *	(c) 1999 Pavel Machek <pavel@ucw.cz>
 *	(c) 2018--2019 Maria Matejka <mq@jmq.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#ifndef _BIRD_FILTER_DATA_H_
#define _BIRD_FILTER_DATA_H_

#include "nest/bird.h"

/* Type numbers must be in 0..0xff range */
#define T_MASK 0xff

/* Internal types */
enum f_type {
/* Nothing. Simply nothing. */
  T_VOID = 0,

/* User visible types, which fit in int */
  T_INT = 0x10,
  T_BOOL = 0x11,
  T_PAIR = 0x12,  /*	Notice that pair is stored as integer: first << 16 | second */
  T_QUAD = 0x13,

/* Put enumerational types in 0x30..0x3f range */
  T_ENUM_LO = 0x30,
  T_ENUM_HI = 0x3f,

  T_ENUM_RTS = 0x30,
  T_ENUM_BGP_ORIGIN = 0x31,
  T_ENUM_SCOPE = 0x32,
  T_ENUM_RTC = 0x33,
  T_ENUM_RTD = 0x34,
  T_ENUM_ROA = 0x35,
  T_ENUM_NETTYPE = 0x36,
  T_ENUM_RA_PREFERENCE = 0x37,
  T_ENUM_AF = 0x38,

/* new enums go here */
  T_ENUM_EMPTY = 0x3f,	/* Special hack for atomic_aggr */

#define T_ENUM T_ENUM_LO ... T_ENUM_HI

/* Bigger ones */
  T_IP = 0x20,
  T_NET = 0x21,
  T_STRING = 0x22,
  T_PATH_MASK = 0x23,	/* mask for BGP path */
  T_PATH = 0x24,		/* BGP path */
  T_CLIST = 0x25,		/* Community list */
  T_EC = 0x26,		/* Extended community value, u64 */
  T_ECLIST = 0x27,		/* Extended community list */
  T_LC = 0x28,		/* Large community value, lcomm */
  T_LCLIST = 0x29,		/* Large community list */
  T_RD = 0x2a,		/* Route distinguisher for VPN addresses */
  T_PATH_MASK_ITEM = 0x2b,	/* Path mask item for path mask constructors */

  T_SET = 0x80,
  T_PREFIX_SET = 0x81,
} PACKED;

/* Filter value; size of this affects filter memory consumption */
struct f_val {
  enum f_type type;	/* T_*  */
  union {
    uint i;
    u64 ec;
    lcomm lc;
    ip_addr ip;
    const net_addr *net;
    char *s;
    const struct f_tree *t;
    const struct f_trie *ti;
    const struct adata *ad;
    const struct f_path_mask *path_mask;
    struct f_path_mask_item pmi;
  } val;
};

/* Dynamic attribute definition (eattrs) */
struct f_dynamic_attr {
  u8 type;		/* EA type (EAF_*) */
  u8 bit;		/* For bitfield accessors */
  enum f_type f_type;	/* Filter type */
  uint ea_code;		/* EA code */
};

enum f_sa_code {
  SA_FROM = 1,
  SA_GW,
  SA_NET,
  SA_PROTO,
  SA_SOURCE,
  SA_SCOPE,
  SA_DEST,
  SA_IFNAME,
  SA_IFINDEX,
} PACKED;

/* Static attribute definition (members of struct rta) */
struct f_static_attr {
  enum f_type f_type;		/* Filter type */
  enum f_sa_code sa_code;	/* Static attribute id */
  int readonly:1;			/* Don't allow writing */
};

/* Filter l-value type */
enum f_lval_type {
  F_LVAL_VARIABLE,
  F_LVAL_PREFERENCE,
  F_LVAL_SA,
  F_LVAL_EA,
};

/* Filter l-value */
struct f_lval {
  enum f_lval_type type;
  union {
    struct symbol *sym;
    struct f_dynamic_attr da;
    struct f_static_attr sa;
  };
};

/* IP prefix range structure */
struct f_prefix {
  net_addr net;		/* The matching prefix must match this net */
  u8 lo, hi;		/* And its length must fit between lo and hi */
};

struct f_tree {
  struct f_tree *left, *right;
  struct f_val from, to;
  void *data;
};

struct f_trie_node
{
  ip_addr addr, mask, accept;
  uint plen;
  struct f_trie_node *c[2];
};

struct f_trie
{
  linpool *lp;
  int zero;
  uint node_size;
  struct f_trie_node root[0];		/* Root trie node follows */
};

struct f_tree *f_new_tree(void);
struct f_tree *build_tree(struct f_tree *);
const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
int same_tree(const struct f_tree *t0, const struct f_tree *t2);
void tree_format(const struct f_tree *t, buffer *buf);

struct f_trie *f_new_trie(linpool *lp, uint node_size);
void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
int trie_match_net(const struct f_trie *t, const net_addr *n);
int trie_same(const struct f_trie *t1, const struct f_trie *t2);
void trie_format(const struct f_trie *t, buffer *buf);

#define F_CMP_ERROR 999

const char *f_type_name(enum f_type t);

int val_same(const struct f_val *v1, const struct f_val *v2);
int val_compare(const struct f_val *v1, const struct f_val *v2);
void val_format(const struct f_val *v, buffer *buf);
char *val_format_str(struct linpool *lp, const struct f_val *v);
const char *val_dump(const struct f_val *v);

static inline int val_is_ip4(const struct f_val *v)
{ return (v->type == T_IP) && ipa_is_ip4(v->val.ip); }
int val_in_range(const struct f_val *v1, const struct f_val *v2);

int clist_set_type(const struct f_tree *set, struct f_val *v);
static inline int eclist_set_type(const struct f_tree *set)
{ return set->from.type == T_EC; }
static inline int lclist_set_type(const struct f_tree *set)
{ return set->from.type == T_LC; }

const struct adata *clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
const struct adata *eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
const struct adata *lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);


/* Special undef value for paths and clists */
static inline int
undef_value(struct f_val v)
{
  return ((v.type == T_PATH) || (v.type == T_CLIST) ||
	  (v.type == T_ECLIST) || (v.type == T_LCLIST)) &&
    (v.val.ad == &null_adata);
}

extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist;

enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres);

#endif
Commit	Line	Data
8bdb05ed	1	/*
4f082dfa	2	* BIRD Internet Routing Daemon -- Dynamic data structures
8bdb05ed MM	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
4f082dfa MM	10	#ifndef _BIRD_FILTER_DATA_H_
4f082dfa MM	11	#define _BIRD_FILTER_DATA_H_
8bdb05ed	12
4f082dfa	13	#include "nest/bird.h"
8bdb05ed MM	14
	15	/* Type numbers must be in 0..0xff range */
	16	#define T_MASK 0xff
	17
	18	/* Internal types */
	19	enum f_type {
96d757c1 JMM	20	/* Nothing. Simply nothing. */
96d757c1 JMM	21	T_VOID = 0,
8bdb05ed MM	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,
0edf0c8c	41	T_ENUM_AF = 0x38,
8bdb05ed MM	42
	43	/* new enums go here */
	44	T_ENUM_EMPTY = 0x3f, /* Special hack for atomic_aggr */
	45
	46	#define T_ENUM T_ENUM_LO ... T_ENUM_HI
	47
	48	/* Bigger ones */
	49	T_IP = 0x20,
	50	T_NET = 0x21,
	51	T_STRING = 0x22,
	52	T_PATH_MASK = 0x23, /* mask for BGP path */
	53	T_PATH = 0x24, /* BGP path */
	54	T_CLIST = 0x25, /* Community list */
	55	T_EC = 0x26, /* Extended community value, u64 */
	56	T_ECLIST = 0x27, /* Extended community list */
	57	T_LC = 0x28, /* Large community value, lcomm */
	58	T_LCLIST = 0x29, /* Large community list */
	59	T_RD = 0x2a, /* Route distinguisher for VPN addresses */
	60	T_PATH_MASK_ITEM = 0x2b, /* Path mask item for path mask constructors */
	61
	62	T_SET = 0x80,
	63	T_PREFIX_SET = 0x81,
	64	} PACKED;
	65
	66	/* Filter value; size of this affects filter memory consumption */
	67	struct f_val {
	68	enum f_type type; /* T_* */
	69	union {
	70	uint i;
	71	u64 ec;
	72	lcomm lc;
	73	ip_addr ip;
	74	const net_addr *net;
	75	char *s;
	76	const struct f_tree *t;
	77	const struct f_trie *ti;
	78	const struct adata *ad;
	79	const struct f_path_mask *path_mask;
	80	struct f_path_mask_item pmi;
	81	} val;
	82	};
	83
8bdb05ed MM	84	/* Dynamic attribute definition (eattrs) */
	85	struct f_dynamic_attr {
	86	u8 type; /* EA type (EAF_) /
	87	u8 bit; /* For bitfield accessors */
	88	enum f_type f_type; /* Filter type */
	89	uint ea_code; /* EA code */
	90	};
	91
	92	enum f_sa_code {
	93	SA_FROM = 1,
	94	SA_GW,
	95	SA_NET,
	96	SA_PROTO,
	97	SA_SOURCE,
	98	SA_SCOPE,
	99	SA_DEST,
	100	SA_IFNAME,
	101	SA_IFINDEX,
	102	} PACKED;
	103
	104	/* Static attribute definition (members of struct rta) */
	105	struct f_static_attr {
	106	enum f_type f_type; /* Filter type */
	107	enum f_sa_code sa_code; /* Static attribute id */
	108	int readonly:1; /* Don't allow writing */
	109	};
	110
4f082dfa MM	111	/* Filter l-value type */
	112	enum f_lval_type {
	113	F_LVAL_VARIABLE,
	114	F_LVAL_PREFERENCE,
	115	F_LVAL_SA,
	116	F_LVAL_EA,
	117	};
	118
	119	/* Filter l-value */
	120	struct f_lval {
	121	enum f_lval_type type;
	122	union {
b40c0f02	123	struct symbol *sym;
4f082dfa MM	124	struct f_dynamic_attr da;
	125	struct f_static_attr sa;
	126	};
	127	};
	128
	129	/* IP prefix range structure */
	130	struct f_prefix {
	131	net_addr net; /* The matching prefix must match this net */
	132	u8 lo, hi; /* And its length must fit between lo and hi */
	133	};
	134
8bdb05ed MM	135	struct f_tree {
	136	struct f_tree left, right;
	137	struct f_val from, to;
	138	void *data;
	139	};
	140
	141	struct f_trie_node
	142	{
	143	ip_addr addr, mask, accept;
	144	uint plen;
	145	struct f_trie_node *c[2];
	146	};
	147
	148	struct f_trie
	149	{
	150	linpool *lp;
	151	int zero;
	152	uint node_size;
	153	struct f_trie_node root[0]; /* Root trie node follows */
	154	};
	155
	156	struct f_tree *f_new_tree(void);
	157	struct f_tree build_tree(struct f_tree );
	158	const struct f_tree find_tree(const struct f_tree t, const struct f_val *val);
	159	int same_tree(const struct f_tree t0, const struct f_tree t2);
	160	void tree_format(const struct f_tree t, buffer buf);
	161
	162	struct f_trie f_new_trie(linpool lp, uint node_size);
	163	void trie_add_prefix(struct f_trie t, const net_addr *n, uint l, uint h);
	164	int trie_match_net(const struct f_trie t, const net_addr n);
	165	int trie_same(const struct f_trie t1, const struct f_trie t2);
	166	void trie_format(const struct f_trie t, buffer buf);
	167
52893045 MM	168	#define F_CMP_ERROR 999
52893045 MM	169
87512e97 OZ	170	const char *f_type_name(enum f_type t);
87512e97 OZ	171
52893045 MM	172	int val_same(const struct f_val v1, const struct f_val v2);
	173	int val_compare(const struct f_val v1, const struct f_val v2);
	174	void val_format(const struct f_val v, buffer buf);
b40c0f02	175	char val_format_str(struct linpool lp, const struct f_val *v);
52893045 MM	176	const char val_dump(const struct f_val v);
	177
	178	static inline int val_is_ip4(const struct f_val *v)
	179	{ return (v->type == T_IP) && ipa_is_ip4(v->val.ip); }
	180	int val_in_range(const struct f_val v1, const struct f_val v2);
	181
	182	int clist_set_type(const struct f_tree set, struct f_val v);
	183	static inline int eclist_set_type(const struct f_tree *set)
	184	{ return set->from.type == T_EC; }
	185	static inline int lclist_set_type(const struct f_tree *set)
	186	{ return set->from.type == T_LC; }
	187
	188	const struct adata clist_filter(struct linpool pool, const struct adata list, const struct f_val set, int pos);
	189	const struct adata eclist_filter(struct linpool pool, const struct adata list, const struct f_val set, int pos);
	190	const struct adata lclist_filter(struct linpool pool, const struct adata list, const struct f_val set, int pos);
	191
	192
	193	/* Special undef value for paths and clists */
	194	static inline int
	195	undef_value(struct f_val v)
	196	{
	197	return ((v.type == T_PATH) \|\| (v.type == T_CLIST) \|\|
	198	(v.type == T_ECLIST) \|\| (v.type == T_LCLIST)) &&
	199	(v.val.ad == &null_adata);
	200	}
	201
8bdb05ed MM	202	extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist;
8bdb05ed MM	203
52893045 MM	204	enum filter_return f_eval(const struct f_line expr, struct linpool tmp_pool, struct f_val *pres);
52893045 MM	205
8bdb05ed	206	#endif