[thirdparty/bird.git] / nest / route.h

/*
 *	BIRD Internet Routing Daemon -- Routing Table
 *
 *	(c) 1998 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#ifndef _BIRD_ROUTE_H_
#define _BIRD_ROUTE_H_

#include "lib/resource.h"

struct protocol;

/*
 *	Generic data structure for storing network prefixes. Also used
 *	for the master routing table. Currently implemented as a hash 
 *	table.
 *
 *	Available operations:
 *		- insertion of new entry
 *		- deletion of entry
 *		- searching for entry by network prefix
 */

struct fib_node {
  ip_addr prefix;			/* In host order */
  byte pxlen;
  byte flags;				/* ??? define them ??? */
  byte pad0, pad1;			/* ??? use ??? */
  struct fib_node *next;		/* Next in hash chain */
};

struct fib {
  pool *fib_pool;			/* Pool holding all our data */
  slab *fib_slab;			/* Slab holding all fib nodes */
  struct fib_node **hash_table;		/* Node hash table */
  unsigned int hash_size;		/* Number of hash table entries (a power of two) */
  unsigned int hash_mask;		/* hash_size - 1 */
  unsigned int entries;			/* Number of entries */
  unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */
  void (*init)(struct fib_node *);	/* Constructor */
};

void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *));
void *fib_find(struct fib *, ip_addr *, int);	/* Find or return NULL if doesn't exist */
void *fib_get(struct fib *, ip_addr *, int); 	/* Find or create new if nonexistent */
void fib_delete(struct fib *, void *);	/* Remove fib entry */
void fib_free(struct fib *);		/* Destroy the fib */

#define FIB_WALK(fib, z, op) do {				\
	struct fib_node *z, **ff = (fib)->hash_table;		\
	unsigned int count = (fib)->hash_size;			\
	while (count--)						\
	  for(z = *ff++; z; z=z->next)				\
	    {							\
	      op;						\
	    }							\
	} while (0)

/*
 *	Neighbor Cache. We hold (direct neighbor, protocol) pairs we've seen
 *	along with pointer to protocol-specific data.
 *
 *	The primary goal of this cache is to quickly validate all incoming
 *	packets if their have been sent by our neighbors and to notify
 *	protocols about lost neighbors when an interface goes down.
 */

typedef struct neighbor {
  ip_addr addr;				/* Address of the neighbor */
  struct next *next;			/* Next in hashed chain */
  struct next *sibling;			/* Next in per-device chain */
  struct proto *proto;			/* Protocol this belongs to */
  void *data;				/* Protocol-specific data */
} neighbor;

neighbor *neigh_find(ip_addr *);	/* NULL if not a neighbor */

/*
 *	Master Routing Tables. Generally speaking, each of them is a list
 *	of FIB (one per TOS) with each entry pointing to a list of route entries
 *	representing routes to given network.
 *	Each of the RTE's contains variable data (the preference and protocol-dependent
 *	metrics) and a pointer to a route attribute block common for many routes).
 */

typedef struct rtable {
  struct rtable *sibling;		/* Our sibling for different TOS */
  byte tos;				/* TOS for this table */
  struct fib fib;
  char *name;				/* Name of this table */
  /* FIXME: Data for kernel synchronization */
} rtable;

typedef struct network {
  struct fib_node n;
  struct rte *routes;			/* Available routes for this network */
  struct network *next;			/* Next in Recalc Chain */
} net;

typedef struct rte {
  struct rte *next;
  struct rtattr *attrs;
  byte flags;				/* Flags (REF_...) */
  byte pflags;				/* Protocol-specific flags */
  word pref;				/* Route preference */
  u32 lastmod;				/* Last modified (time) */
  union {				/* Protocol-dependent data (metrics etc.) */
#ifdef CONFIG_STATIC
    struct {
    } stat;
#endif
#ifdef CONFIG_RIP
    struct {
      byte metric;			/* RIP metric */
      u16 tag;				/* External route tag */
    } rip;
#endif
#ifdef CONFIG_OSPF
    struct {
      u32 metric1, metric2;		/* OSPF Type 1 and Type 2 metrics */
      u32 tag;				/* External route tag */
    } ospf;
#endif
#ifdef CONFIG_BGP
    struct {
    } bgp;
#endif
  } u;
} rte;

#define REF_CHOSEN 1			/* Currently chosen route */

extern rtable master_table;

void rt_init(void);
void rt_setup(rtable *, char *);
net *net_find(rtable *tab, unsigned tos, ip_addr mask, unsigned len);
net *net_get(rtable *tab, unsigned tos, ip_addr mask, unsigned len);
rte *rte_find(net *net, struct proto *p);
rte *rte_get_temp(struct rtattr *);
void rte_update(net *net, rte *new);
void rte_dump(rte *);
void rt_dump(rtable *);

/*
 *	Route Attributes
 *
 *	Beware: All standard BGP attributes must be represented here instead
 *	of making them local to the route. This is needed to ensure proper
 *	construction of BGP route attribute lists.
 */

typedef struct rtattr {
  struct rtattr *next, *prev;		/* Hash chain */
  struct rtattr *garbage;		/* Garbage collector chain */
  struct proto *proto;			/* Protocol instance */
  unsigned uc;				/* Use count */
  byte source;				/* Route source (RTS_...) */
  byte scope;				/* Route scope (SCOPE_... -- see ip.h) */
  byte cast;				/* Casting type (RTC_...) */
  byte dest;				/* Route destination type (RTD_...) */
  byte tos;				/* TOS of this route */
  byte flags;				/* Route flags (RTF_...) */
  ip_addr gw;				/* Next hop */
  ip_addr from;				/* Advertising router */
  struct iface *iface;			/* Outgoing interface */
  struct ea_list *attrs;		/* Extended Attribute chain */
  union {				/* Protocol-specific data */
  } u;
} rta;

#define RTS_STATIC 1			/* Normal static route */
#define RTS_INHERIT 2			/* Route inherited from kernel */
#define RTS_DEVICE 3			/* Device route */
#define RTS_STATIC_DEVICE 4		/* Static device route */
#define RTS_REDIRECT 5			/* Learned via redirect */
#define RTS_RIP 6			/* RIP route */
#define RTS_RIP_EXT 7			/* RIP external route */
#define RTS_OSPF 8			/* OSPF route */
#define RTS_OSPF_EXT 9			/* OSPF external route */
#define RTS_OSPF_IA 10			/* OSPF inter-area route */
#define RTS_OSPF_BOUNDARY 11		/* OSPF route to boundary router (???) */
#define RTS_BGP 12			/* BGP route */

#define RTC_UNICAST 0
#define RTC_BROADCAST 1
#define RTC_MULTICAST 2
#define RTC_ANYCAST 3			/* IPv6 Anycast */

#define RTD_ROUTER 0			/* Next hop is neighbor router */
#define RTD_DEVICE 1			/* Points to device */
#define RTD_BLACKHOLE 2			/* Silently drop packets */
#define RTD_UNREACHABLE 3		/* Reject as unreachable */
#define RTD_PROHIBIT 4			/* Administratively prohibited */

#define RTF_EXTERIOR 1			/* Learned via exterior protocol */
#define RTF_TAGGED 2			/* Tagged external route learned via IGP */

/*
 *	Extended Route Attributes
 */

typedef struct eattr {
  byte protocol;			/* Protocol ID (EAP_...) */
  byte flags;				/* Attribute flags (EAF_...) */
  byte id;				/* Protocol-dependent ID */
  byte rfu;				/* ??? */
  union {
    u32 data;
    struct adata *ptr;			/* Attribute data elsewhere */
  } u;
} eattr;

#define EAP_GENERIC 0			/* Generic attributes */
#define EAP_BGP 1			/* BGP attributes */

#define EAF_OPTIONAL 0x80		/* Refer to BGP specs for full meaning */
#define EAF_TRANSITIVE 0x40
#define EAF_PARTIAL 0x20
#define EAF_EXTENDED_LENGTH 0x10	/* Not used by us, internal to BGP */
#define EAF_LONGWORD 0x01		/* Embedded value [Not a BGP flag!] */

struct adata {
  unsigned int length;
  byte data[0];
};

typedef struct ea_list {
  struct ea_list *next;			/* In case we have an override list */
  byte sorted;				/* `Really sorted' flag (???) */
  byte rfu;
  word nattrs;				/* Number of attributes */
  eattr attrs[0];			/* Attribute definitions themselves */
} ea_list;

eattr *ea_find(ea_list *, unsigned protocol, unsigned id);

#define EA_LIST_NEW(p, alloc, n) do {				\
	unsigned cnt = n;				       	\
	p = alloc(sizeof(ea_list) + cnt*sizeof(eattr));		\
	memset(p, 0, sizeof(ea_list));				\
	p->nattrs = cnt;					\
} while(0)

void rta_init(void);
rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
static inline rta *rta_clone(rta *r) { r->uc++; return r; }
void _rta_free(rta *r);
static inline void rta_free(rta *r) { if (r && !--r->uc) _rta_free(r); }
void rta_dump(rta *);
void rta_dump_all(void);

/*
 *	Default protocol preferences
 */

#define DEF_PREF_DIRECT	    	240	/* Directly connected */
#define DEF_PREF_STATIC		200	/* Static route */
#define DEF_PREF_OSPF_INTERNAL	150	/* OSPF intra-area, inter-area and type 1 external routes */
#define DEF_PREF_RIP		120	/* RIP */
#define DEF_PREF_BGP		100	/* BGP */
#define DEF_PREF_OSPF_EXTERNAL	80	/* OSPF external routes */
#define DEF_PREF_RIP_EXTERNAL	70	/* RIP external routes */
#define DEF_PREF_SINK		10	/* Sink route */

#endif
Commit	Line	Data
58ef912c MM	1	/*
	2	* BIRD Internet Routing Daemon -- Routing Table
	3	*
	4	* (c) 1998 Martin Mares <mj@ucw.cz>
	5	*
	6	* Can be freely distributed and used under the terms of the GNU GPL.
	7	*/
	8
	9	#ifndef _BIRD_ROUTE_H_
	10	#define _BIRD_ROUTE_H_
	11
1feea03e	12	#include "lib/resource.h"
58ef912c	13
2326b001 MM	14	struct protocol;
2326b001 MM	15
58ef912c MM	16	/*
58ef912c MM	17	* Generic data structure for storing network prefixes. Also used
62aa008a MM	18	* for the master routing table. Currently implemented as a hash
62aa008a MM	19	* table.
58ef912c MM	20	*
	21	* Available operations:
	22	* - insertion of new entry
	23	* - deletion of entry
62aa008a	24	* - searching for entry by network prefix
58ef912c MM	25	*/
	26
	27	struct fib_node {
	28	ip_addr prefix; /* In host order */
	29	byte pxlen;
	30	byte flags; /* ??? define them ??? */
	31	byte pad0, pad1; /* ??? use ??? */
a8b60382	32	struct fib_node next; / Next in hash chain */
58ef912c MM	33	};
	34
	35	struct fib {
62aa008a MM	36	pool fib_pool; / Pool holding all our data */
	37	slab fib_slab; / Slab holding all fib nodes */
	38	struct fib_node *hash_table; / Node hash table */
a8b60382	39	unsigned int hash_size; /* Number of hash table entries (a power of two) */
62aa008a	40	unsigned int hash_mask; /* hash_size - 1 */
a8b60382 MM	41	unsigned int entries; /* Number of entries */
a8b60382 MM	42	unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */
58ef912c MM	43	void (init)(struct fib_node ); /* Constructor */
	44	};
	45
a8b60382	46	void fib_init(struct fib , pool , unsigned node_size, unsigned hash_size, void (init)(struct fib_node ));
58ef912c	47	void fib_find(struct fib , ip_addr , int); / Find or return NULL if doesn't exist */
58ef912c	48	void fib_get(struct fib , ip_addr , int); / Find or create new if nonexistent */
62aa008a	49	void fib_delete(struct fib , void ); /* Remove fib entry */
a8b60382 MM	50	void fib_free(struct fib ); / Destroy the fib */
a8b60382 MM	51
62aa008a MM	52	#define FIB_WALK(fib, z, op) do { \
62aa008a MM	53	struct fib_node z, *ff = (fib)->hash_table; \
a8b60382 MM	54	unsigned int count = (fib)->hash_size; \
a8b60382 MM	55	while (count--) \
62aa008a	56	for(z = *ff++; z; z=z->next) \
a8b60382	57	{ \
62aa008a	58	op; \
a8b60382	59	} \
62aa008a	60	} while (0)
a8b60382 MM	61
	62	/*
	63	* Neighbor Cache. We hold (direct neighbor, protocol) pairs we've seen
	64	* along with pointer to protocol-specific data.
	65	*
	66	* The primary goal of this cache is to quickly validate all incoming
	67	* packets if their have been sent by our neighbors and to notify
	68	* protocols about lost neighbors when an interface goes down.
	69	*/
	70
	71	typedef struct neighbor {
	72	ip_addr addr; /* Address of the neighbor */
	73	struct next next; / Next in hashed chain */
	74	struct next sibling; / Next in per-device chain */
	75	struct proto proto; / Protocol this belongs to */
	76	void data; / Protocol-specific data */
	77	} neighbor;
	78
	79	neighbor neigh_find(ip_addr ); /* NULL if not a neighbor */
58ef912c MM	80
58ef912c MM	81	/*
62aa008a MM	82	* Master Routing Tables. Generally speaking, each of them is a list
	83	* of FIB (one per TOS) with each entry pointing to a list of route entries
	84	* representing routes to given network.
58ef912c	85	* Each of the RTE's contains variable data (the preference and protocol-dependent
62aa008a	86	* metrics) and a pointer to a route attribute block common for many routes).
58ef912c MM	87	*/
58ef912c MM	88
62aa008a MM	89	typedef struct rtable {
	90	struct rtable sibling; / Our sibling for different TOS */
	91	byte tos; /* TOS for this table */
	92	struct fib fib;
	93	char name; / Name of this table */
	94	/* FIXME: Data for kernel synchronization */
	95	} rtable;
	96
58ef912c MM	97	typedef struct network {
	98	struct fib_node n;
	99	struct rte routes; / Available routes for this network */
	100	struct network next; / Next in Recalc Chain */
	101	} net;
	102
	103	typedef struct rte {
	104	struct rte *next;
	105	struct rtattr *attrs;
	106	byte flags; /* Flags (REF_...) */
481f6985	107	byte pflags; /* Protocol-specific flags */
58ef912c	108	word pref; /* Route preference */
481f6985	109	u32 lastmod; /* Last modified (time) */
58ef912c MM	110	union { /* Protocol-dependent data (metrics etc.) */
	111	#ifdef CONFIG_STATIC
	112	struct {
	113	} stat;
	114	#endif
	115	#ifdef CONFIG_RIP
	116	struct {
	117	byte metric; /* RIP metric */
481f6985	118	u16 tag; /* External route tag */
58ef912c MM	119	} rip;
	120	#endif
	121	#ifdef CONFIG_OSPF
	122	struct {
	123	u32 metric1, metric2; /* OSPF Type 1 and Type 2 metrics */
481f6985	124	u32 tag; /* External route tag */
58ef912c MM	125	} ospf;
	126	#endif
	127	#ifdef CONFIG_BGP
	128	struct {
	129	} bgp;
	130	#endif
	131	} u;
	132	} rte;
	133
	134	#define REF_CHOSEN 1 /* Currently chosen route */
	135
2326b001 MM	136	extern rtable master_table;
	137
	138	void rt_init(void);
	139	void rt_setup(rtable , char );
	140	net net_find(rtable tab, unsigned tos, ip_addr mask, unsigned len);
	141	net net_get(rtable tab, unsigned tos, ip_addr mask, unsigned len);
	142	rte rte_find(net net, struct proto *p);
	143	rte rte_get_temp(struct rtattr );
	144	void rte_update(net net, rte new);
	145	void rte_dump(rte *);
	146	void rt_dump(rtable *);
	147
58ef912c MM	148	/*
	149	* Route Attributes
	150	*
	151	* Beware: All standard BGP attributes must be represented here instead
	152	* of making them local to the route. This is needed to ensure proper
	153	* construction of BGP route attribute lists.
	154	*/
	155
2326b001	156	typedef struct rtattr {
58ef912c MM	157	struct rtattr next, prev; /* Hash chain */
	158	struct rtattr garbage; / Garbage collector chain */
	159	struct proto proto; / Protocol instance */
	160	unsigned uc; /* Use count */
	161	byte source; /* Route source (RTS_...) */
a8b60382	162	byte scope; /* Route scope (SCOPE_... -- see ip.h) */
58ef912c MM	163	byte cast; /* Casting type (RTC_...) */
	164	byte dest; /* Route destination type (RTD_...) */
	165	byte tos; /* TOS of this route */
	166	byte flags; /* Route flags (RTF_...) */
58ef912c	167	ip_addr gw; /* Next hop */
a8b60382	168	ip_addr from; /* Advertising router */
58ef912c MM	169	struct iface iface; / Outgoing interface */
58ef912c MM	170	struct ea_list attrs; / Extended Attribute chain */
a8b60382 MM	171	union { /* Protocol-specific data */
a8b60382 MM	172	} u;
58ef912c MM	173	} rta;
	174
	175	#define RTS_STATIC 1 /* Normal static route */
	176	#define RTS_INHERIT 2 /* Route inherited from kernel */
	177	#define RTS_DEVICE 3 /* Device route */
	178	#define RTS_STATIC_DEVICE 4 /* Static device route */
	179	#define RTS_REDIRECT 5 /* Learned via redirect */
	180	#define RTS_RIP 6 /* RIP route */
	181	#define RTS_RIP_EXT 7 /* RIP external route */
	182	#define RTS_OSPF 8 /* OSPF route */
	183	#define RTS_OSPF_EXT 9 /* OSPF external route */
	184	#define RTS_OSPF_IA 10 /* OSPF inter-area route */
481f6985	185	#define RTS_OSPF_BOUNDARY 11 /* OSPF route to boundary router (???) */
58ef912c MM	186	#define RTS_BGP 12 /* BGP route */
58ef912c MM	187
58ef912c MM	188	#define RTC_UNICAST 0
	189	#define RTC_BROADCAST 1
	190	#define RTC_MULTICAST 2
	191	#define RTC_ANYCAST 3 /* IPv6 Anycast */
	192
	193	#define RTD_ROUTER 0 /* Next hop is neighbor router */
	194	#define RTD_DEVICE 1 /* Points to device */
	195	#define RTD_BLACKHOLE 2 /* Silently drop packets */
	196	#define RTD_UNREACHABLE 3 /* Reject as unreachable */
	197	#define RTD_PROHIBIT 4 /* Administratively prohibited */
	198
481f6985	199	#define RTF_EXTERIOR 1 /* Learned via exterior protocol */
a8b60382	200	#define RTF_TAGGED 2 /* Tagged external route learned via IGP */
481f6985	201
58ef912c MM	202	/*
	203	* Extended Route Attributes
	204	*/
	205
	206	typedef struct eattr {
	207	byte protocol; /* Protocol ID (EAP_...) */
	208	byte flags; /* Attribute flags (EAF_...) */
	209	byte id; /* Protocol-dependent ID */
a8b60382	210	byte rfu; /* ??? */
58ef912c MM	211	union {
	212	u32 data;
	213	struct adata ptr; / Attribute data elsewhere */
	214	} u;
	215	} eattr;
	216
	217	#define EAP_GENERIC 0 /* Generic attributes */
	218	#define EAP_BGP 1 /* BGP attributes */
	219
	220	#define EAF_OPTIONAL 0x80 /* Refer to BGP specs for full meaning */
	221	#define EAF_TRANSITIVE 0x40
	222	#define EAF_PARTIAL 0x20
	223	#define EAF_EXTENDED_LENGTH 0x10 /* Not used by us, internal to BGP */
	224	#define EAF_LONGWORD 0x01 /* Embedded value [Not a BGP flag!] */
	225
	226	struct adata {
	227	unsigned int length;
	228	byte data[0];
	229	};
	230
	231	typedef struct ea_list {
	232	struct ea_list next; / In case we have an override list */
a8b60382	233	byte sorted; /* `Really sorted' flag (???) */
58ef912c MM	234	byte rfu;
	235	word nattrs; /* Number of attributes */
	236	eattr attrs[0]; /* Attribute definitions themselves */
	237	} ea_list;
	238
	239	eattr ea_find(ea_list , unsigned protocol, unsigned id);
	240
	241	#define EA_LIST_NEW(p, alloc, n) do { \
	242	unsigned cnt = n; \
	243	p = alloc(sizeof(ea_list) + cnt*sizeof(eattr)); \
a8b60382	244	memset(p, 0, sizeof(ea_list)); \
58ef912c MM	245	p->nattrs = cnt; \
	246	} while(0)
	247
2326b001 MM	248	void rta_init(void);
	249	rta rta_lookup(rta ); /* Get rta equivalent to this one, uc++ */
	250	static inline rta rta_clone(rta r) { r->uc++; return r; }
	251	void _rta_free(rta *r);
	252	static inline void rta_free(rta *r) { if (r && !--r->uc) _rta_free(r); }
	253	void rta_dump(rta *);
	254	void rta_dump_all(void);
	255
a8b60382 MM	256	/*
	257	* Default protocol preferences
	258	*/
	259
	260	#define DEF_PREF_DIRECT 240 /* Directly connected */
	261	#define DEF_PREF_STATIC 200 /* Static route */
	262	#define DEF_PREF_OSPF_INTERNAL 150 /* OSPF intra-area, inter-area and type 1 external routes */
	263	#define DEF_PREF_RIP 120 /* RIP */
	264	#define DEF_PREF_BGP 100 /* BGP */
	265	#define DEF_PREF_OSPF_EXTERNAL 80 /* OSPF external routes */
	266	#define DEF_PREF_RIP_EXTERNAL 70 /* RIP external routes */
	267	#define DEF_PREF_SINK 10 /* Sink route */
	268
58ef912c	269	#endif