route.h 8.45 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
/*
 *	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_

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

15 16
struct protocol;

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

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

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

47
void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *));
48 49
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 */
50
void fib_delete(struct fib *, void *);	/* Remove fib entry */
51 52
void fib_free(struct fib *);		/* Destroy the fib */

53 54
#define FIB_WALK(fib, z, op) do {				\
	struct fib_node *z, **ff = (fib)->hash_table;		\
55 56
	unsigned int count = (fib)->hash_size;			\
	while (count--)						\
57
	  for(z = *ff++; z; z=z->next)				\
58
	    {							\
59
	      op;						\
60
	    }							\
61
	} while (0)
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

/*
 *	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 */
81 82

/*
83 84 85
 *	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.
86
 *	Each of the RTE's contains variable data (the preference and protocol-dependent
87
 *	metrics) and a pointer to a route attribute block common for many routes).
88 89
 */

90 91 92 93 94 95 96 97
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;

98 99 100 101 102 103 104 105 106 107
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_...) */
Martin Mareš's avatar
Martin Mareš committed
108
  byte pflags;				/* Protocol-specific flags */
109
  word pref;				/* Route preference */
110
  bird_clock_t lastmod;			/* Last modified */
111 112 113 114 115 116 117 118
  union {				/* Protocol-dependent data (metrics etc.) */
#ifdef CONFIG_STATIC
    struct {
    } stat;
#endif
#ifdef CONFIG_RIP
    struct {
      byte metric;			/* RIP metric */
Martin Mareš's avatar
Martin Mareš committed
119
      u16 tag;				/* External route tag */
120 121 122 123 124
    } rip;
#endif
#ifdef CONFIG_OSPF
    struct {
      u32 metric1, metric2;		/* OSPF Type 1 and Type 2 metrics */
Martin Mareš's avatar
Martin Mareš committed
125
      u32 tag;				/* External route tag */
126 127 128 129 130 131 132 133 134 135 136
    } ospf;
#endif
#ifdef CONFIG_BGP
    struct {
    } bgp;
#endif
  } u;
} rte;

#define REF_CHOSEN 1			/* Currently chosen route */

137 138 139 140 141 142 143 144 145 146 147
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 *);
148
void rt_dump_all(void);
149

150 151 152 153 154 155 156 157
/*
 *	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.
 */

158
typedef struct rtattr {
159 160 161 162 163
  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_...) */
164
  byte scope;				/* Route scope (SCOPE_... -- see ip.h) */
165 166 167 168 169
  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 */
170
  ip_addr from;				/* Advertising router */
171 172
  struct iface *iface;			/* Outgoing interface */
  struct ea_list *attrs;		/* Extended Attribute chain */
173 174
  union {				/* Protocol-specific data */
  } u;
175 176 177 178 179 180 181 182 183 184 185 186
} 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 */
Martin Mareš's avatar
Martin Mareš committed
187
#define RTS_OSPF_BOUNDARY 11		/* OSPF route to boundary router (???) */
188 189 190 191 192 193 194 195 196 197 198 199 200
#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
201
#define RTF_EXTERIOR 1			/* Learned via exterior protocol */
202
#define RTF_TAGGED 2			/* Tagged external route learned via IGP */
Martin Mareš's avatar
Martin Mareš committed
203

204 205 206 207 208 209 210 211
/*
 *	Extended Route Attributes
 */

typedef struct eattr {
  byte protocol;			/* Protocol ID (EAP_...) */
  byte flags;				/* Attribute flags (EAF_...) */
  byte id;				/* Protocol-dependent ID */
212
  byte rfu;				/* ??? */
213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
  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 */
235
  byte sorted;				/* `Really sorted' flag (???) */
236 237 238 239 240 241 242 243 244 245
  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));		\
246
	memset(p, 0, sizeof(ea_list));				\
247 248 249
	p->nattrs = cnt;					\
} while(0)

250 251 252 253 254 255 256 257
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);

258 259 260 261 262 263 264 265 266 267 268 269 270
/*
 *	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 */

271
#endif