route.h 11 KB
Newer Older
1 2 3
/*
 *	BIRD Internet Routing Daemon -- Routing Table
 *
4
 *	(c) 1998--1999 Martin Mares <mj@ucw.cz>
5 6 7 8 9 10 11
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#ifndef _BIRD_ROUTE_H_
#define _BIRD_ROUTE_H_

12
#include "lib/lists.h"
13
#include "lib/resource.h"
14
#include "lib/timer.h"
15

16
struct protocol;
17
struct proto;
18

19 20
/*
 *	Generic data structure for storing network prefixes. Also used
21
 *	for the master routing table. Currently implemented as a hash
22
 *	table.
23 24 25 26
 *
 *	Available operations:
 *		- insertion of new entry
 *		- deletion of entry
27
 *		- searching for entry by network prefix
28
 *		- asynchronous retrieval of fib contents
29 30 31
 */

struct fib_node {
32 33
  struct fib_node *next;		/* Next in hash chain */
  struct fib_iterator *readers;		/* List of readers of this node */
34
  byte pxlen;
35
  byte flags;				/* User-defined */
36
  byte x0, x1;				/* User-defined */
37 38 39 40 41 42 43 44 45
  ip_addr prefix;			/* In host order */
};

struct fib_iterator {			/* See lib/slists.h for an explanation */
  struct fib_iterator *prev, *next;	/* Must be synced with struct fib_node! */
  struct fib_node *node;		/* Or NULL if freshly merged */
  byte efef;				/* 0xff to distinguish between iterator and node */
  byte pad[3];
  unsigned int hash;
46 47 48
};

struct fib {
49 50 51
  pool *fib_pool;			/* Pool holding all our data */
  slab *fib_slab;			/* Slab holding all fib nodes */
  struct fib_node **hash_table;		/* Node hash table */
52
  unsigned int hash_size;		/* Number of hash table entries (a power of two) */
53 54
  unsigned int hash_order;		/* Binary logarithm of hash_size */
  unsigned int hash_shift;		/* 16 - hash_log */
55 56
  unsigned int entries;			/* Number of entries */
  unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */
57 58 59
  void (*init)(struct fib_node *);	/* Constructor */
};

60
void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_order, void (*init)(struct fib_node *));
61 62
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 */
63
void fib_delete(struct fib *, void *);	/* Remove fib entry */
64
void fib_free(struct fib *);		/* Destroy the fib */
65 66 67 68 69
void fib_check(struct fib *);		/* Consistency check for debugging */

void fit_init(struct fib_iterator *, struct fib *); /* Internal functions, don't call */
struct fib_node *fit_get(struct fib *, struct fib_iterator *);
void fit_put(struct fib_iterator *, struct fib_node *);
70

71
#define FIB_WALK(fib, z) do {					\
72
	struct fib_node *z, **ff = (fib)->hash_table;		\
73 74
	unsigned int count = (fib)->hash_size;			\
	while (count--)						\
75 76 77
	  for(z = *ff++; z; z=z->next)

#define FIB_WALK_END } while (0)
78

79 80 81 82 83 84 85
#define FIB_ITERATE_INIT(it, fib) fit_init(it, fib)

#define FIB_ITERATE_START(fib, it, z) do {			\
	struct fib_node *z = fit_get(fib, it);			\
	unsigned int count = (fib)->hash_size;			\
	unsigned int hpos = (it)->hash;				\
	for(;;) {						\
86
	fis_again:	if (!z) {				\
87 88 89
			if (++hpos >= count)			\
				break;				\
			z = (fib)->hash_table[hpos];		\
90
			goto fis_again;				\
91 92
		}

93
#define FIB_ITERATE_END(z) z = z->next; } } while(0)
94 95 96

#define FIB_ITERATE_PUT(it, z) fit_put(it, z)

97
/*
98 99 100 101
 *	Master Routing Tables. Generally speaking, each of them contains a FIB
 *	with each entry pointing to a list of route entries representing routes
 *	to given network (with the selected one at the head).
 *
102
 *	Each of the RTE's contains variable data (the preference and protocol-dependent
103
 *	metrics) and a pointer to a route attribute block common for many routes).
104 105
 *
 *	It's guaranteed that there is at most one RTE for every (prefix,proto) pair.
106 107
 */

108 109 110 111 112 113
struct rtable_config {
  node n;
  char *name;
  struct rtable *table;
};

114
typedef struct rtable {
115
  node n;				/* Node in list of all tables */
116 117
  struct fib fib;
  char *name;				/* Name of this table */
118
  list hooks;				/* List of announcement hooks */
119 120
} rtable;

121
typedef struct network {
122
  struct fib_node n;			/* FIB flags reserved for kernel syncer */
123 124 125 126 127
  struct rte *routes;			/* Available routes for this network */
} net;

typedef struct rte {
  struct rte *next;
128
  net *net;				/* Network this RTE belongs to */
129
  struct rta *attrs;			/* Attributes of this route */
130
  byte flags;				/* Flags (REF_...) */
Martin Mareš's avatar
Martin Mareš committed
131
  byte pflags;				/* Protocol-specific flags */
132
  word pref;				/* Route preference */
133
  bird_clock_t lastmod;			/* Last modified */
134 135 136
  union {				/* Protocol-dependent data (metrics etc.) */
#ifdef CONFIG_RIP
    struct {
137
      node garbage;			/* List for garbage collection */
138
      byte metric;			/* RIP metric */
Martin Mareš's avatar
Martin Mareš committed
139
      u16 tag;				/* External route tag */
140 141 142 143 144
    } rip;
#endif
#ifdef CONFIG_OSPF
    struct {
      u32 metric1, metric2;		/* OSPF Type 1 and Type 2 metrics */
Martin Mareš's avatar
Martin Mareš committed
145
      u32 tag;				/* External route tag */
146 147 148 149 150 151
    } ospf;
#endif
#ifdef CONFIG_BGP
    struct {
    } bgp;
#endif
152 153 154 155 156 157 158
    struct {				/* Routes generated by krt sync (both temporary and inherited ones) */
      s8 src;				/* Alleged route source (see krt.h) */
      u8 proto;				/* Kernel source protocol ID */
      u8 type;				/* Kernel route type */
      u8 seen;				/* Seen during last scan */
      u32 metric;			/* Kernel metric */
    } krt;
159 160 161
  } u;
} rte;

162 163
#define REF_COW 1			/* Copy this rte on write */

164
struct config;
165 166

void rt_init(void);
167 168
void rt_preconfig(struct config *);
void rt_commit(struct config *);
169
void rt_setup(pool *, rtable *, char *);
170 171
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len) { return (net *) fib_find(&tab->fib, &addr, len); }
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len) { return (net *) fib_get(&tab->fib, &addr, len); }
172
rte *rte_find(net *net, struct proto *p);
173
rte *rte_get_temp(struct rta *);
174 175
void rte_update(rtable *tab, net *net, struct proto *p, rte *new);
void rte_discard(rtable *tab, rte *old);
176
void rte_dump(rte *);
177
void rte_free(rte *);
178 179
rte *rte_do_cow(rte *);
static inline rte * rte_cow(rte *r) { return (r->flags & REF_COW) ? rte_do_cow(r) : r; }
180
void rt_dump(rtable *);
181
void rt_dump_all(void);
182
void rt_feed_baby(struct proto *p);
183
void rt_prune(rtable *tab);
184
void rt_prune_all(void);
185

186 187 188 189 190 191 192 193
/*
 *	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.
 */

194 195 196
typedef struct rta {
  struct rta *next, *prev;		/* Hash chain */
  struct rta *garbage;			/* Garbage collector chain */
197 198 199
  struct proto *proto;			/* Protocol instance */
  unsigned uc;				/* Use count */
  byte source;				/* Route source (RTS_...) */
200
  byte scope;				/* Route scope (SCOPE_... -- see ip.h) */
201 202 203
  byte cast;				/* Casting type (RTC_...) */
  byte dest;				/* Route destination type (RTD_...) */
  byte flags;				/* Route flags (RTF_...) */
204
  byte aflags;				/* Attribute cache flags (RTAF_...) */
205
  byte rfu, rfu2;			/* Padding */
206
  ip_addr gw;				/* Next hop */
207
  ip_addr from;				/* Advertising router */
208 209 210 211
  struct iface *iface;			/* Outgoing interface */
  struct ea_list *attrs;		/* Extended Attribute chain */
} rta;

212
#define RTS_DUMMY 0			/* Dummy route to be removed soon */
213 214 215 216 217 218 219 220 221 222
#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 */
Martin Mareš's avatar
Martin Mareš committed
223
#define RTS_OSPF_BOUNDARY 11		/* OSPF route to boundary router (???) */
224 225 226 227 228 229 230 231 232 233 234 235 236
#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 */

Martin Mareš's avatar
Martin Mareš committed
237
#define RTF_EXTERIOR 1			/* Learned via exterior protocol */
238
#define RTF_TAGGED 2			/* Tagged external route learned via IGP */
Martin Mareš's avatar
Martin Mareš committed
239

240 241
#define RTAF_CACHED 1			/* This is a cached rta */

242 243 244 245 246
/*
 *	Extended Route Attributes
 */

typedef struct eattr {
247 248 249
  word id;				/* EA_CODE(EAP_..., protocol-dependent ID) */
  byte flags;				/* Protocol-dependent flags */
  byte type;				/* Attribute type and several flags (EAF_...) */
250 251 252 253 254 255
  union {
    u32 data;
    struct adata *ptr;			/* Attribute data elsewhere */
  } u;
} eattr;

256
/* FIXME: Introduce real protocol numbers? */
257 258
#define EAP_GENERIC 0			/* Generic attributes */
#define EAP_BGP 1			/* BGP attributes */
259
#define EAP_RIP 2			/* RIP */
260

261 262 263 264 265 266 267 268 269 270 271 272 273
#define EA_CODE(proto,id) (((proto) << 8) | (id))
#define EA_PROTO(ea) ((ea) >> 8)
#define EA_ID(ea) ((ea) & 0xff)

#define EAF_TYPE_MASK 0x0f		/* Mask with this to get type */
#define EAF_TYPE_INT 0x01		/* 32-bit signed integer number */
#define EAF_TYPE_OPAQUE 0x02		/* Opaque byte string (not filterable) */
#define EAF_TYPE_IP_ADDRESS 0x04	/* IP address [FIXME: embed at least for IPv4?] */
#define EAF_TYPE_AS_PATH 0x06		/* BGP AS path [FIXME: define storage layout] */
#define EAF_TYPE_INT_SET 0x0a		/* Set of integers (e.g., a community list) */
#define EAF_EMBEDDED 0x01		/* Data stored in eattr.u.data (part of type spec) */
#define EAF_VAR_LENGTH 0x02		/* Attribute length is variable */
#define EAF_INLINE 0x80			/* Copy of an attribute inlined in rte (temporary ea_lists only) */
274 275 276 277 278 279 280 281

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

typedef struct ea_list {
  struct ea_list *next;			/* In case we have an override list */
282
  byte flags;				/* Flags: EALF_... */
283
  byte rfu;
284
  word count;				/* Number of attributes */
285 286 287
  eattr attrs[0];			/* Attribute definitions themselves */
} ea_list;

288 289 290
#define EALF_SORTED 1			/* Attributes are sorted by code */
#define EALF_BISECT 2			/* Use interval bisection for searching */
#define EALF_CACHED 4			/* Attributes belonging to cached rta */
291

292 293 294 295 296
eattr *ea_find(ea_list *, unsigned ea);
void ea_dump(ea_list *);
void ea_sort(ea_list *);		/* Sort entries in all sub-lists */
unsigned ea_scan(ea_list *);		/* How many bytes do we need for merged ea_list (0=merge not needed) */
void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */
297

298 299 300
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; }
301 302
void rta__free(rta *r);
static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); }
303 304
void rta_dump(rta *);
void rta_dump_all(void);
305
static inline eattr * rta_find(rta *a, unsigned ea) { return ea_find(a->attrs, ea); }
306

307 308 309 310 311 312 313 314 315 316 317
/*
 *	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 */
318
#define DEF_PREF_UKR		50	/* Unidentified Kernel Route */
319 320
#define DEF_PREF_SINK		10	/* Sink route */

321
#endif