route.h 23.7 KB
Newer Older
1 2 3
/*
 *	BIRD Internet Routing Daemon -- Routing Table
 *
4
 *	(c) 1998--2000 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
#include "nest/protocol.h"
16

17
struct protocol;
18
struct proto;
19 20 21
struct symbol;
struct filter;
struct cli;
22

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

struct fib_node {
36 37
  struct fib_node *next;		/* Next in hash chain */
  struct fib_iterator *readers;		/* List of readers of this node */
38 39 40
  byte flags;				/* User-defined, will be removed */
  u32 uid;				/* Unique ID based on hash, will be removed */
  net_addr addr[0];
41 42 43 44 45 46
};

struct fib_iterator {			/* See lib/slists.h for an explanation */
  struct fib_iterator *prev, *next;	/* Must be synced with struct fib_node! */
  byte efef;				/* 0xff to distinguish between iterator and node */
  byte pad[3];
47
  struct fib_node *node;		/* Or NULL if freshly merged */
Pavel Tvrdík's avatar
Pavel Tvrdík committed
48
  uint hash;
49 50
};

51
typedef void (*fib_init_fn)(void *);
Martin Mareš's avatar
Martin Mareš committed
52

53
struct fib {
54 55 56
  pool *fib_pool;			/* Pool holding all our data */
  slab *fib_slab;			/* Slab holding all fib nodes */
  struct fib_node **hash_table;		/* Node hash table */
Pavel Tvrdík's avatar
Pavel Tvrdík committed
57 58
  uint hash_size;			/* Number of hash table entries (a power of two) */
  uint hash_order;			/* Binary logarithm of hash_size */
59
  uint hash_shift;			/* 32 - hash_order */
60 61 62
  uint addr_type;			/* Type of address data stored in fib (NET_*) */
  uint node_size;	/* XXXX */
  uint node_offset;	/* XXXX */
Pavel Tvrdík's avatar
Pavel Tvrdík committed
63 64
  uint entries;				/* Number of entries */
  uint entries_min, entries_max;	/* Entry count limits (else start rehashing) */
65
  fib_init_fn init;			/* Constructor */
66 67
};

68 69 70 71 72 73
static inline void * fib_node_to_user(struct fib *f, struct fib_node *e)
{ return e ? (void *) ((char *) e - f->node_offset) : NULL; }

static inline struct fib_node * fib_user_to_node(struct fib *f, void *e)
{ return e ? (void *) ((char *) e + f->node_offset) : NULL; }

74
void fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init);
75 76 77
void *fib_find(struct fib *, const net_addr *);	/* Find or return NULL if doesn't exist */
void *fib_get(struct fib *, const net_addr *); 	/* Find or create new if nonexistent */
void *fib_route(struct fib *, const net_addr *); /* Longest-match routing lookup */
78
void fib_delete(struct fib *, void *);	/* Remove fib entry */
79
void fib_free(struct fib *);		/* Destroy the fib */
80 81 82 83 84
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 *);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
85 86
void fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos);

87 88 89 90 91 92 93

#define FIB_WALK(fib, type, z) do {				\
	struct fib_node *fn_, **ff_ = (fib)->hash_table;	\
	uint count_ = (fib)->hash_size;				\
	type *z;						\
	while (count_--)					\
	  for (fn_ = *ff_++; z = fib_node_to_user(fib, fn_); fn_=fn_->next)
94 95

#define FIB_WALK_END } while (0)
96

97 98
#define FIB_ITERATE_INIT(it, fib) fit_init(it, fib)

99 100 101 102 103
#define FIB_ITERATE_START(fib, it, type, z) do {		\
	struct fib_node *fn_ = fit_get(fib, it);		\
	uint count_ = (fib)->hash_size;				\
	uint hpos_ = (it)->hash;				\
	type *z;						\
104
	for(;;) {						\
105
	  if (!fn_)						\
106
            {							\
107
	       if (++hpos_ >= count_)				\
108
		 break;						\
109
	       fn_ = (fib)->hash_table[hpos_];			\
110
	       continue;					\
111 112
	    }							\
	  z = fib_node_to_user(fib, fn_);
113

114
#define FIB_ITERATE_END fn_ = fn_->next; } } while(0)
115

116
#define FIB_ITERATE_PUT(it) fit_put(it, fn_)
117

118
#define FIB_ITERATE_PUT_NEXT(it, fib) fit_put_next(fib, it, fn_, hpos_)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
119 120 121 122

#define FIB_ITERATE_UNLINK(it, fib) fit_get(fib, it)


123
/*
124 125 126 127
 *	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).
 *
128
 *	Each of the RTE's contains variable data (the preference and protocol-dependent
129
 *	metrics) and a pointer to a route attribute block common for many routes).
130 131
 *
 *	It's guaranteed that there is at most one RTE for every (prefix,proto) pair.
132 133
 */

134 135 136 137
struct rtable_config {
  node n;
  char *name;
  struct rtable *table;
138
  struct proto_config *krt_attached;	/* Kernel syncer attached to this table */
139
  uint addr_type;			/* Type of address data stored in table (NET_*) */
140 141
  int gc_max_ops;			/* Maximum number of operations before GC is run */
  int gc_min_time;			/* Minimum time between two consecutive GC runs */
142
  byte sorted;				/* Routes of network are sorted according to rte_better() */
143 144
};

145
typedef struct rtable {
146
  node n;				/* Node in list of all tables */
147 148
  struct fib fib;
  char *name;				/* Name of this table */
149
  list hooks;				/* List of announcement hooks */
150
  uint addr_type;			/* Type of address data stored in table (NET_*) */
151
  int pipe_busy;			/* Pipe loop detection */
152
  int use_count;			/* Number of protocols using this table */
153
  struct hostcache *hostcache;
154
  struct rtable_config *config;		/* Configuration of this table */
155 156 157 158
  struct config *deleted;		/* Table doesn't exist in current configuration,
					 * delete as soon as use_count becomes 0 and remove
					 * obstacle from this routing table.
					 */
159
  struct event *rt_event;		/* Routing table event */
160 161
  int gc_counter;			/* Number of operations since last GC */
  bird_clock_t gc_time;			/* Time of last GC */
162
  byte gc_scheduled;			/* GC is scheduled */
163
  byte prune_state;			/* Table prune state, 1 -> scheduled, 2-> running */
164 165
  byte hcu_scheduled;			/* Hostcache update is scheduled */
  byte nhu_state;			/* Next Hop Update state */
166
  struct fib_iterator prune_fit;	/* Rtable prune FIB iterator */
167
  struct fib_iterator nhu_fit;		/* Next Hop Update FIB iterator */
168 169
} rtable;

170 171 172 173
#define RPS_NONE	0
#define RPS_SCHEDULED	1
#define RPS_RUNNING	2

174 175
typedef struct network {
  struct rte *routes;			/* Available routes for this network */
176
  struct fib_node n;			/* FIB flags reserved for kernel syncer */
177 178
} net;

179
struct hostcache {
180 181 182 183 184
  slab *slab;				/* Slab holding all hostentries */
  struct hostentry **hash_table;	/* Hash table for hostentries */
  unsigned hash_order, hash_shift;
  unsigned hash_max, hash_min;
  unsigned hash_items;
185 186 187
  linpool *lp;				/* Linpool for trie */
  struct f_trie *trie;			/* Trie of prefixes that might affect hostentries */
  list hostentries;			/* List of all hostentries */
188 189 190 191 192
  byte update_hostcache;
};

struct hostentry {
  node ln;
193 194 195
  ip_addr addr;				/* IP address of host, part of key */
  ip_addr link;				/* (link-local) IP address of host, used as gw
					   if host is directly attached */
Ondřej Zajíček's avatar
Ondřej Zajíček committed
196
  struct rtable *tab;			/* Dependent table, part of key */
197 198
  struct hostentry *next;		/* Next in hash chain */
  unsigned hash_key;			/* Hash key */
199
  unsigned uc;				/* Use count */
200
  struct rta *src;			/* Source rta entry */
201 202
  ip_addr gw;				/* Chosen next hop */
  byte dest;				/* Chosen route destination type (RTD_...) */
203
  u32 igp_metric;			/* Chosen route IGP metric */
204 205
};

206 207
typedef struct rte {
  struct rte *next;
208
  net *net;				/* Network this RTE belongs to */
209
  struct announce_hook *sender;		/* Announce hook used to send the route to the routing table */
210
  struct rta *attrs;			/* Attributes of this route */
211
  byte flags;				/* Flags (REF_...) */
212
  byte pflags;				/* Protocol-specific flags */
213
  word pref;				/* Route preference */
214
  bird_clock_t lastmod;			/* Last modified */
215 216 217
  union {				/* Protocol-dependent data (metrics etc.) */
#ifdef CONFIG_RIP
    struct {
Ondřej Zajíček's avatar
Ondřej Zajíček committed
218 219
      struct iface *from;		/* Incoming iface */
      u8 metric;			/* RIP metric */
220
      u16 tag;				/* External route tag */
221 222 223 224 225
    } rip;
#endif
#ifdef CONFIG_OSPF
    struct {
      u32 metric1, metric2;		/* OSPF Type 1 and Type 2 metrics */
226
      u32 tag;				/* External route tag */
227
      u32 router_id;			/* Router that originated this route */
228
    } ospf;
229 230 231 232 233
#endif
#ifdef CONFIG_BGP
    struct {
      u8 suppressed;			/* Used for deterministic MED comparison */
    } bgp;
234
#endif
235 236 237 238 239 240 241
    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;
242 243 244
  } u;
} rte;

245
#define REF_COW		1		/* Copy this rte on write */
246
#define REF_FILTERED	2		/* Route is rejected by import filter */
247 248
#define REF_STALE	4		/* Route is stale in a refresh cycle */
#define REF_DISCARD	8		/* Route is scheduled for discard */
249 250

/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */
251
static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); }
252

253 254
/* Route just has REF_FILTERED flag */
static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED); }
255

256

257
/* Types of route announcement, also used as flags */
258 259 260
#define RA_OPTIMAL	1		/* Announcement of optimal route change */
#define RA_ACCEPTED	2		/* Announcement of first accepted route */
#define RA_ANY		3		/* Announcement of any route change */
261
#define RA_MERGED	4		/* Announcement of optimal route merged with next ones */
262

263 264 265 266 267 268
/* Return value of import_control() callback */
#define RIC_ACCEPT	1		/* Accepted by protocol */
#define RIC_PROCESS	0		/* Process it through import filter */
#define RIC_REJECT	-1		/* Rejected by protocol */
#define RIC_DROP	-2		/* Silently dropped by protocol */

269
struct config;
270 271

void rt_init(void);
272
void rt_preconfig(struct config *);
273 274 275
void rt_commit(struct config *new, struct config *old);
void rt_lock_table(rtable *);
void rt_unlock_table(rtable *);
276
void rt_setup(pool *, rtable *, char *, struct rtable_config *);
277 278 279
static inline net *net_find(rtable *tab, net_addr *addr) { return (net *) fib_find(&tab->fib, addr); }
static inline net *net_get(rtable *tab, net_addr *addr) { return (net *) fib_get(&tab->fib, addr); }

280
rte *rte_find(net *net, struct rte_src *src);
281
rte *rte_get_temp(struct rta *);
282 283
void rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src);
static inline void rte_update(struct proto *p, net *net, rte *new) { rte_update2(p->main_ahook, net, new, p->main_source); }
284
void rte_discard(rtable *tab, rte *old);
285
int rt_examine(rtable *t, net_addr *a, struct proto *p, struct filter *filter);
286
rte *rt_export_merged(struct announce_hook *ah, net *net, rte **rt_free, struct ea_list **tmpa, int silent);
287 288
void rt_refresh_begin(rtable *t, struct announce_hook *ah);
void rt_refresh_end(rtable *t, struct announce_hook *ah);
289
void rte_dump(rte *);
290
void rte_free(rte *);
291 292
rte *rte_do_cow(rte *);
static inline rte * rte_cow(rte *r) { return (r->flags & REF_COW) ? rte_do_cow(r) : r; }
293
rte *rte_cow_rta(rte *r, linpool *lp);
294
void rt_dump(rtable *);
295
void rt_dump_all(void);
296 297
int rt_feed_baby(struct proto *p);
void rt_feed_baby_abort(struct proto *p);
298
int rt_prune_loop(void);
299
struct rtable_config *rt_new_table(struct symbol *s, uint addr_type);
300

301 302 303 304 305 306 307 308 309
static inline void
rt_mark_for_prune(rtable *tab)
{
  if (tab->prune_state == RPS_RUNNING)
    fit_get(&tab->fib, &tab->prune_fit);

  tab->prune_state = RPS_SCHEDULED;
}

310
struct rt_show_data {
311
  net_addr *addr;
312 313 314 315
  rtable *table;
  struct filter *filter;
  int verbose;
  struct fib_iterator fit;
316
  struct proto *show_protocol;
317
  struct proto *export_protocol;
318
  int export_mode, primary_only, filtered;
319
  struct config *running_on_config;
320
  int net_counter, rt_counter, show_counter;
321
  int stats, show_for;
322 323 324
};
void rt_show(struct rt_show_data *);

325 326 327 328 329 330
/* Value of export_mode in struct rt_show_data */
#define RSEM_NONE	0		/* Export mode not used */
#define RSEM_PREEXPORT	1		/* Routes ready for export, before filtering */
#define RSEM_EXPORT	2		/* Routes accepted by export filter */
#define RSEM_NOEXPORT	3		/* Routes rejected by export filter */

331 332 333 334 335 336 337 338
/*
 *	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.
 */

339 340 341 342 343
/* Multipath next-hop */
struct mpnh {
  ip_addr gw;				/* Next hop */
  struct iface *iface;			/* Outgoing interface */
  struct mpnh *next;
Pavel Tvrdík's avatar
Pavel Tvrdík committed
344
  byte weight;
345 346
};

347 348 349 350 351 352 353 354 355
struct rte_src {
  struct rte_src *next;			/* Hash chain */
  struct proto *proto;			/* Protocol the source is based on */
  u32 private_id;			/* Private ID, assigned by the protocol */
  u32 global_id;			/* Globally unique ID of the source */
  unsigned uc;				/* Use count */
};


356
typedef struct rta {
357
  struct rta *next, **pprev;		/* Hash chain */
358
  struct rte_src *src;			/* Route source that created the route */
359 360
  unsigned uc;				/* Use count */
  byte source;				/* Route source (RTS_...) */
361
  byte scope;				/* Route scope (SCOPE_... -- see ip.h) */
362 363
  byte cast;				/* Casting type (RTC_...) */
  byte dest;				/* Route destination type (RTD_...) */
364
  byte flags;				/* Route flags (RTF_...), now unused */
365
  byte aflags;				/* Attribute cache flags (RTAF_...) */
366
  u16 hash_key;				/* Hash over important fields */
367
  u32 igp_metric;			/* IGP metric to next hop (for iBGP routes) */
368
  ip_addr gw;				/* Next hop */
369
  ip_addr from;				/* Advertising router */
370
  struct hostentry *hostentry;		/* Hostentry for recursive next-hops */
371
  struct iface *iface;			/* Outgoing interface */
372
  struct mpnh *nexthops;		/* Next-hops for multipath routes */
373
  struct ea_list *eattrs;		/* Extended Attribute chain */
374 375
} rta;

376
#define RTS_DUMMY 0			/* Dummy route to be removed soon */
377 378 379 380 381 382
#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 */
Martin Mareš's avatar
Martin Mareš committed
383
#define RTS_OSPF 7			/* OSPF route */
384
#define RTS_OSPF_IA 8			/* OSPF inter-area route */
Ondřej Filip's avatar
Ondřej Filip committed
385 386 387 388
#define RTS_OSPF_EXT1 9			/* OSPF external route type 1 */
#define RTS_OSPF_EXT2 10		/* OSPF external route type 2 */
#define RTS_BGP 11			/* BGP route */
#define RTS_PIPE 12			/* Inter-table wormhole */
389 390 391 392 393 394 395 396 397 398 399

#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 */
400 401
#define RTD_MULTIPATH 5			/* Multipath route (nexthops != NULL) */
#define RTD_NONE 6			/* Invalid RTD */
402

403 404 405 406
					/* Flags for net->n.flags, used by kernel syncer */
#define KRF_INSTALLED 0x80		/* This route should be installed in the kernel */
#define KRF_SYNC_ERROR 0x40		/* Error during kernel table synchronization */

407 408
#define RTAF_CACHED 1			/* This is a cached rta */

409 410 411
#define IGP_METRIC_UNKNOWN 0x80000000	/* Default igp_metric used when no other
					   protocol-specific metric is availabe */

412 413 414 415 416 417

/* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */
static inline int rte_is_reachable(rte *r)
{ uint d = r->attrs->dest; return (d == RTD_ROUTER) || (d == RTD_DEVICE) || (d == RTD_MULTIPATH); }


418 419 420 421 422
/*
 *	Extended Route Attributes
 */

typedef struct eattr {
423 424 425
  word id;				/* EA_CODE(EAP_..., protocol-dependent ID) */
  byte flags;				/* Protocol-dependent flags */
  byte type;				/* Attribute type and several flags (EAF_...) */
426 427 428 429 430 431 432 433
  union {
    u32 data;
    struct adata *ptr;			/* Attribute data elsewhere */
  } u;
} eattr;

#define EAP_GENERIC 0			/* Generic attributes */
#define EAP_BGP 1			/* BGP attributes */
434
#define EAP_RIP 2			/* RIP */
435
#define EAP_OSPF 3			/* OSPF */
436 437
#define EAP_KRT 4			/* Kernel route attributes */
#define EAP_MAX 5
438

439 440 441 442
#define EA_CODE(proto,id) (((proto) << 8) | (id))
#define EA_PROTO(ea) ((ea) >> 8)
#define EA_ID(ea) ((ea) & 0xff)

443 444
#define EA_GEN_IGP_METRIC EA_CODE(EAP_GENERIC, 0)

445 446
#define EA_CODE_MASK 0xffff
#define EA_ALLOW_UNDEF 0x10000		/* ea_find: allow EAF_TYPE_UNDEF */
447
#define EA_BIT(n) ((n) << 24)		/* Used in bitfield accessors */
448

449
#define EAF_TYPE_MASK 0x0f		/* Mask with this to get type */
450
#define EAF_TYPE_INT 0x01		/* 32-bit unsigned integer number */
451
#define EAF_TYPE_OPAQUE 0x02		/* Opaque byte string (not filterable) */
452 453
#define EAF_TYPE_IP_ADDRESS 0x04	/* IP address */
#define EAF_TYPE_ROUTER_ID 0x05		/* Router ID (IPv4 address) */
Martin Mareš's avatar
Martin Mareš committed
454
#define EAF_TYPE_AS_PATH 0x06		/* BGP AS path (encoding per RFC 1771:4.3) */
455
#define EAF_TYPE_BITFIELD 0x09		/* 32-bit embedded bitfield */
Martin Mareš's avatar
Martin Mareš committed
456
#define EAF_TYPE_INT_SET 0x0a		/* Set of u32's (e.g., a community list) */
457
#define EAF_TYPE_EC_SET 0x0e		/* Set of pairs of u32's - ext. community list */
458
#define EAF_TYPE_UNDEF 0x0f		/* `force undefined' entry */
459
#define EAF_EMBEDDED 0x01		/* Data stored in eattr.u.data (part of type spec) */
460
#define EAF_VAR_LENGTH 0x02		/* Attribute length is variable (part of type spec) */
461
#define EAF_ORIGINATED 0x40		/* The attribute has originated locally */
462
#define EAF_TEMP 0x80			/* A temporary attribute (the one stored in the tmp attr list) */
463 464

struct adata {
Pavel Tvrdík's avatar
Pavel Tvrdík committed
465
  uint length;				/* Length of data */
466 467 468
  byte data[0];
};

469 470 471 472
static inline int adata_same(struct adata *a, struct adata *b)
{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); }


473 474
typedef struct ea_list {
  struct ea_list *next;			/* In case we have an override list */
475
  byte flags;				/* Flags: EALF_... */
476
  byte rfu;
477
  word count;				/* Number of attributes */
478 479 480
  eattr attrs[0];			/* Attribute definitions themselves */
} ea_list;

481 482 483
#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 */
484

485 486 487 488 489 490
struct rte_src *rt_find_source(struct proto *p, u32 id);
struct rte_src *rt_get_source(struct proto *p, u32 id);
static inline void rt_lock_source(struct rte_src *src) { src->uc++; }
static inline void rt_unlock_source(struct rte_src *src) { src->uc--; }
void rt_prune_sources(void);

491 492 493 494 495
struct ea_walk_state {
  ea_list *eattrs;			/* Ccurrent ea_list, initially set by caller */
  eattr *ea;				/* Current eattr, initially NULL */
  u32 visited[4];			/* Bitfield, limiting max to 128 */
};
496

497
eattr *ea_find(ea_list *, unsigned ea);
498
eattr *ea_walk(struct ea_walk_state *s, uint id, uint max);
499
int ea_get_int(ea_list *, unsigned ea, int def);
500 501
void ea_dump(ea_list *);
void ea_sort(ea_list *);		/* Sort entries in all sub-lists */
502
unsigned ea_scan(ea_list *);		/* How many bytes do we need for merged ea_list */
503
void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */
504
int ea_same(ea_list *x, ea_list *y);	/* Test whether two ea_lists are identical */
Pavel Tvrdík's avatar
Pavel Tvrdík committed
505
uint ea_hash(ea_list *e);	/* Calculate 16-bit hash value */
506
ea_list *ea_append(ea_list *to, ea_list *what);
507
void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max);
508

509 510 511
int mpnh__same(struct mpnh *x, struct mpnh *y); /* Compare multipath nexthops */
static inline int mpnh_same(struct mpnh *x, struct mpnh *y)
{ return (x == y) || mpnh__same(x, y); }
512
struct mpnh *mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp);
513

514 515
void rta_init(void);
rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
516
static inline int rta_is_cached(rta *r) { return r->aflags & RTAF_CACHED; }
517
static inline rta *rta_clone(rta *r) { r->uc++; return r; }
518 519
void rta__free(rta *r);
static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); }
520 521
rta *rta_do_cow(rta *o, linpool *lp);
static inline rta * rta_cow(rta *r, linpool *lp) { return rta_is_cached(r) ? rta_do_cow(r, lp) : r; }
522 523
void rta_dump(rta *);
void rta_dump_all(void);
524
void rta_show(struct cli *, rta *, ea_list *);
525
void rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll);
526 527

/*
Ondřej Zajíček's avatar
Ondřej Zajíček committed
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546
 * rta_set_recursive_next_hop() acquires hostentry from hostcache and fills
 * rta->hostentry field.  New hostentry has zero use count. Cached rta locks its
 * hostentry (increases its use count), uncached rta does not lock it. Hostentry
 * with zero use count is removed asynchronously during host cache update,
 * therefore it is safe to hold such hostentry temorarily. Hostentry holds a
 * lock for a 'source' rta, mainly to share multipath nexthops.
 *
 * There is no need to hold a lock for hostentry->dep table, because that table
 * contains routes responsible for that hostentry, and therefore is non-empty if
 * given hostentry has non-zero use count. If the hostentry has zero use count,
 * the entry is removed before dep is referenced.
 *
 * The protocol responsible for routes with recursive next hops should hold a
 * lock for a 'source' table governing that routes (argument tab to
 * rta_set_recursive_next_hop()), because its routes reference hostentries
 * (through rta) related to the governing table. When all such routes are
 * removed, rtas are immediately removed achieving zero uc. Then the 'source'
 * table lock could be immediately released, although hostentries may still
 * exist - they will be freed together with the 'source' table.
547 548 549 550 551
 */

static inline void rt_lock_hostentry(struct hostentry *he) { if (he) he->uc++; }
static inline void rt_unlock_hostentry(struct hostentry *he) { if (he) he->uc--; }

552

553 554
extern struct protocol *attr_class_to_protocol[EAP_MAX];

555 556 557 558 559 560
/*
 *	Default protocol preferences
 */

#define DEF_PREF_DIRECT	    	240	/* Directly connected */
#define DEF_PREF_STATIC		200	/* Static route */
561
#define DEF_PREF_OSPF		150	/* OSPF intra-area, inter-area and type 1 external routes */
562 563
#define DEF_PREF_RIP		120	/* RIP */
#define DEF_PREF_BGP		100	/* BGP */
Martin Mareš's avatar
Martin Mareš committed
564
#define DEF_PREF_PIPE		70	/* Routes piped from other tables */
565
#define DEF_PREF_INHERITED	10	/* Routes inherited from other routing daemons */
566

Jan Moskyto Matejka's avatar
Jan Moskyto Matejka committed
567
#if 0
568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646

/*
 *	Route Origin Authorization
 */

struct roa_item {
  u32 asn;
  byte maxlen;
  byte src;
  struct roa_item *next;
};

struct roa_node {
  struct fib_node n;
  struct roa_item *items;
  // u32 cached_asn;
};

struct roa_table {
  node n;				/* Node in roa_table_list */
  struct fib fib;
  char *name;				/* Name of this ROA table */
  struct roa_table_config *cf;		/* Configuration of this ROA table */
};

struct roa_item_config {
  ip_addr prefix;
  byte pxlen, maxlen;
  u32 asn;
  struct roa_item_config *next;
};

struct roa_table_config {
  node n;				/* Node in config->rpa_tables */
  char *name;				/* Name of this ROA table */
  struct roa_table *table;

  struct roa_item_config *roa_items;	/* Preconfigured ROA items */

  // char *filename;
  // int gc_max_ops;			/* Maximum number of operations before GC is run */
  // int gc_min_time;			/* Minimum time between two consecutive GC runs */
};

struct roa_show_data {
  struct fib_iterator fit;
  struct roa_table *table;
  ip_addr prefix;
  byte pxlen;
  byte mode;				/* ROA_SHOW_* values */
  u32 asn;				/* Filter ASN, 0 -> all */
};

#define ROA_UNKNOWN	0
#define ROA_VALID	1
#define ROA_INVALID	2

#define ROA_SRC_ANY	0
#define ROA_SRC_CONFIG	1
#define ROA_SRC_DYNAMIC	2

#define ROA_SHOW_ALL	0
#define ROA_SHOW_PX	1
#define ROA_SHOW_IN	2
#define ROA_SHOW_FOR	3

extern struct roa_table *roa_table_default;

void roa_add_item(struct roa_table *t, ip_addr prefix, byte pxlen, byte maxlen, u32 asn, byte src);
void roa_delete_item(struct roa_table *t, ip_addr prefix, byte pxlen, byte maxlen, u32 asn, byte src);
void roa_flush(struct roa_table *t, byte src);
byte roa_check(struct roa_table *t, ip_addr prefix, byte pxlen, u32 asn);
struct roa_table_config * roa_new_table_config(struct symbol *s);
void roa_add_item_config(struct roa_table_config *rtc, ip_addr prefix, byte pxlen, byte maxlen, u32 asn);
void roa_init(void);
void roa_preconfig(struct config *c);
void roa_commit(struct config *new, struct config *old);
void roa_show(struct roa_show_data *d);

Jan Moskyto Matejka's avatar
Jan Moskyto Matejka committed
647
#endif
648
#endif