route.h 26.1 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/net.h"
15

16
struct ea_list;
17
struct protocol;
18
struct proto;
19
struct rte_src;
20 21 22
struct symbol;
struct filter;
struct cli;
23

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

struct fib_node {
37 38
  struct fib_node *next;		/* Next in hash chain */
  struct fib_iterator *readers;		/* List of readers of this node */
39 40
  byte flags;				/* User-defined, 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
  uint addr_type;			/* Type of address data stored in fib (NET_*) */
61 62
  uint node_size;			/* FIB node size, 0 for nonuniform */
  uint node_offset;			/* Offset of fib_node struct inside of user data */
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
void *fib_find(struct fib *, const net_addr *);	/* Find or return NULL if doesn't exist */
76
void *fib_get_chain(struct fib *f, const net_addr *a); /* Find first node in linked list from hash table */
77
void *fib_get(struct fib *, const net_addr *);	/* Find or create new if nonexistent */
78
void *fib_route(struct fib *, const net_addr *); /* Longest-match routing lookup */
79
void fib_delete(struct fib *, void *);	/* Remove fib entry */
80
void fib_free(struct fib *);		/* Destroy the fib */
81 82 83 84 85
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
86 87
void fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos);

88 89 90 91 92 93 94

#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)
95 96

#define FIB_WALK_END } while (0)
97

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

100 101 102 103 104
#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;						\
105
	for(;;) {						\
106
	  if (!fn_)						\
107
	    {							\
108
	       if (++hpos_ >= count_)				\
109
		 break;						\
110
	       fn_ = (fib)->hash_table[hpos_];			\
111
	       continue;					\
112 113
	    }							\
	  z = fib_node_to_user(fib, fn_);
114

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

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

119
#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
120 121 122 123

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


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

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

146
typedef struct rtable {
147
  node n;				/* Node in list of all tables */
148 149
  struct fib fib;
  char *name;				/* Name of this table */
150
  list channels;			/* List of attached channels (struct channel) */
151
  uint addr_type;			/* Type of address data stored in table (NET_*) */
152
  int pipe_busy;			/* Pipe loop detection */
153
  int use_count;			/* Number of protocols using this table */
154
  u32 rt_count;				/* Number of routes in the table */
155
  struct hostcache *hostcache;
156
  struct rtable_config *config;		/* Configuration of this table */
157 158 159 160
  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.
					 */
161
  struct event *rt_event;		/* Routing table event */
162
  btime gc_time;			/* Time of last GC */
163
  int gc_counter;			/* Number of operations since last GC */
164
  byte prune_state;			/* Table prune state, 1 -> scheduled, 2-> running */
165 166
  byte hcu_scheduled;			/* Hostcache update is scheduled */
  byte nhu_state;			/* Next Hop Update state */
167
  struct fib_iterator prune_fit;	/* Rtable prune FIB iterator */
168
  struct fib_iterator nhu_fit;		/* Next Hop Update FIB iterator */
169 170
} rtable;

171 172 173 174 175
#define NHU_CLEAN	0
#define NHU_SCHEDULED	1
#define NHU_RUNNING	2
#define NHU_DIRTY	3

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

181
struct hostcache {
182 183 184 185 186
  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;
187 188 189
  linpool *lp;				/* Linpool for trie */
  struct f_trie *trie;			/* Trie of prefixes that might affect hostentries */
  list hostentries;			/* List of all hostentries */
190 191 192 193 194
  byte update_hostcache;
};

struct hostentry {
  node ln;
195 196 197
  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
198
  struct rtable *tab;			/* Dependent table, part of key */
199 200
  struct hostentry *next;		/* Next in hash chain */
  unsigned hash_key;			/* Hash key */
201
  unsigned uc;				/* Use count */
202
  struct rta *src;			/* Source rta entry */
203
  byte dest;				/* Chosen route destination type (RTD_...) */
204
  byte nexthop_linkable;		/* Nexthop list is completely non-device */
205
  u32 igp_metric;			/* Chosen route IGP metric */
206 207
};

208 209
typedef struct rte {
  struct rte *next;
210
  net *net;				/* Network this RTE belongs to */
211
  struct channel *sender;		/* Channel used to send the route to the routing table */
212
  struct rta *attrs;			/* Attributes of this route */
213
  byte flags;				/* Flags (REF_...) */
214
  byte pflags;				/* Protocol-specific flags */
215
  word pref;				/* Route preference */
216
  btime lastmod;			/* Last modified */
217 218 219
  union {				/* Protocol-dependent data (metrics etc.) */
#ifdef CONFIG_RIP
    struct {
Ondřej Zajíček's avatar
Ondřej Zajíček committed
220 221
      struct iface *from;		/* Incoming iface */
      u8 metric;			/* RIP metric */
222
      u16 tag;				/* External route tag */
223 224 225 226 227
    } rip;
#endif
#ifdef CONFIG_OSPF
    struct {
      u32 metric1, metric2;		/* OSPF Type 1 and Type 2 metrics */
228
      u32 tag;				/* External route tag */
229
      u32 router_id;			/* Router that originated this route */
230
    } ospf;
231 232 233 234
#endif
#ifdef CONFIG_BGP
    struct {
      u8 suppressed;			/* Used for deterministic MED comparison */
235
      s8 stale;				/* Route is LLGR_STALE, -1 if unknown */
236
    } bgp;
237 238 239
#endif
#ifdef CONFIG_BABEL
    struct {
240
      u16 seqno;			/* Babel seqno */
241 242 243
      u16 metric;			/* Babel metric */
      u64 router_id;			/* Babel router id */
    } babel;
244
#endif
245 246 247 248
    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 seen;				/* Seen during last scan */
249
      u8 best;				/* Best route in network, propagated to core */
250 251
      u32 metric;			/* Kernel metric */
    } krt;
252 253 254
  } u;
} rte;

255
#define REF_COW		1		/* Copy this rte on write */
256
#define REF_FILTERED	2		/* Route is rejected by import filter */
257 258
#define REF_STALE	4		/* Route is stale in a refresh cycle */
#define REF_DISCARD	8		/* Route is scheduled for discard */
259
#define REF_MODIFY	16		/* Route is scheduled for modify */
260 261

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

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

267

268
/* Types of route announcement, also used as flags */
Ondřej Zajíček's avatar
Ondřej Zajíček committed
269
#define RA_UNDEF	0		/* Undefined RA type */
270 271 272
#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 */
273
#define RA_MERGED	4		/* Announcement of optimal route merged with next ones */
274

275
/* Return value of preexport() callback */
276 277 278 279 280
#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 */

Ondřej Zajíček's avatar
Ondřej Zajíček committed
281
extern list routing_tables;
282
struct config;
283 284

void rt_init(void);
285
void rt_preconfig(struct config *);
286 287 288
void rt_commit(struct config *new, struct config *old);
void rt_lock_table(rtable *);
void rt_unlock_table(rtable *);
289
void rt_setup(pool *, rtable *, struct rtable_config *);
290
static inline net *net_find(rtable *tab, const net_addr *addr) { return (net *) fib_find(&tab->fib, addr); }
291 292
static inline net *net_find_valid(rtable *tab, const net_addr *addr)
{ net *n = net_find(tab, addr); return (n && rte_is_valid(n->routes)) ? n : NULL; }
293
static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) fib_get(&tab->fib, addr); }
294 295
void *net_route(rtable *tab, const net_addr *n);
int net_roa_check(rtable *tab, const net_addr *n, u32 asn);
296
rte *rte_find(net *net, struct rte_src *src);
297
rte *rte_get_temp(struct rta *);
298
void rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src);
299
/* rte_update() moved to protocol.h to avoid dependency conflicts */
300
int rt_examine(rtable *t, net_addr *a, struct proto *p, struct filter *filter);
301
rte *rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int silent);
302 303
void rt_refresh_begin(rtable *t, struct channel *c);
void rt_refresh_end(rtable *t, struct channel *c);
304
void rt_modify_stale(rtable *t, struct channel *c);
305
void rt_schedule_prune(rtable *t);
306
void rte_dump(rte *);
307
void rte_free(rte *);
308 309
rte *rte_do_cow(rte *);
static inline rte * rte_cow(rte *r) { return (r->flags & REF_COW) ? rte_do_cow(r) : r; }
310
rte *rte_cow_rta(rte *r, linpool *lp);
311
void rt_dump(rtable *);
312
void rt_dump_all(void);
313 314
int rt_feed_channel(struct channel *c);
void rt_feed_channel_abort(struct channel *c);
315 316 317 318
int rte_update_in(struct channel *c, const net_addr *n, rte *new, struct rte_src *src);
int rt_reload_channel(struct channel *c);
void rt_reload_channel_abort(struct channel *c);
void rt_prune_sync(rtable *t, int all);
319
struct rtable_config *rt_new_table(struct symbol *s, uint addr_type);
320

321

322 323
/* Default limit for ECMP next hops, defined in sysdep code */
extern const int rt_default_ecmp;
324

325 326 327
struct rt_show_data_rtable {
  node n;
  rtable *table;
328
  struct channel *export_channel;
329 330
};

331
struct rt_show_data {
332
  net_addr *addr;
333 334 335 336
  list tables;
  struct rt_show_data_rtable *tab;	/* Iterator over table list */
  struct rt_show_data_rtable *last_table; /* Last table in output */
  struct fib_iterator fit;		/* Iterator over networks in table */
337
  int verbose, tables_defined_by;
338
  struct filter *filter;
339
  struct proto *show_protocol;
340
  struct proto *export_protocol;
341
  struct channel *export_channel;
342
  struct config *running_on_config;
343 344 345
  int export_mode, primary_only, filtered, stats, show_for;

  int table_open;			/* Iteration (fit) is open */
346 347
  int net_counter, rt_counter, show_counter, table_counter;
  int net_counter_last, rt_counter_last, show_counter_last;
348
};
349

350
void rt_show(struct rt_show_data *);
351
struct rt_show_data_rtable * rt_show_add_table(struct rt_show_data *d, rtable *t);
352 353 354 355 356 357 358 359 360

/* Value of table definition mode in struct rt_show_data */
#define RSD_TDB_DEFAULT	  0		/* no table specified */
#define RSD_TDB_INDIRECT  0		/* show route ... protocol P ... */
#define RSD_TDB_ALL	  RSD_TDB_SET			/* show route ... table all ... */
#define RSD_TDB_DIRECT	  RSD_TDB_SET | RSD_TDB_NMN	/* show route ... table X table Y ... */

#define RSD_TDB_SET	  0x1		/* internal: show empty tables */
#define RSD_TDB_NMN	  0x2		/* internal: need matching net */
361

362 363 364 365 366 367
/* 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 */

368 369 370 371 372 373 374 375
/*
 *	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.
 */

376 377
/* Nexthop structure */
struct nexthop {
378 379
  ip_addr gw;				/* Next hop */
  struct iface *iface;			/* Outgoing interface */
380
  struct nexthop *next;
381
  byte flags;
Pavel Tvrdík's avatar
Pavel Tvrdík committed
382
  byte weight;
383 384
  byte labels_orig;			/* Number of labels before hostentry was applied */
  byte labels;				/* Number of all labels */
385
  u32 label[0];
386 387
};

388 389 390
#define RNF_ONLINK		0x1	/* Gateway is onlink regardless of IP ranges */


391 392 393 394 395 396 397 398 399
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 */
};


400
typedef struct rta {
401
  struct rta *next, **pprev;		/* Hash chain */
402 403 404
  u32 uc;				/* Use count */
  u32 hash_key;				/* Hash over important fields */
  struct ea_list *eattrs;		/* Extended Attribute chain */
405
  struct rte_src *src;			/* Route source that created the route */
406 407 408
  struct hostentry *hostentry;		/* Hostentry for recursive next-hops */
  ip_addr from;				/* Advertising router */
  u32 igp_metric;			/* IGP metric to next hop (for iBGP routes) */
409 410 411 412
  u8 source;				/* Route source (RTS_...) */
  u8 scope;				/* Route scope (SCOPE_... -- see ip.h) */
  u8 dest;				/* Route destination type (RTD_...) */
  u8 aflags;
413
  struct nexthop nh;			/* Next hop */
414 415
} rta;

416
#define RTS_DUMMY 0			/* Dummy route to be removed soon */
417 418 419 420 421 422
#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
423
#define RTS_OSPF 7			/* OSPF route */
424
#define RTS_OSPF_IA 8			/* OSPF inter-area route */
Ondřej Filip's avatar
Ondřej Filip committed
425 426 427 428
#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 */
429
#define RTS_BABEL 13			/* Babel route */
430
#define RTS_RPKI 14			/* Route Origin Authorization */
431 432
#define RTS_PERF 15			/* Perf checker */
#define RTS_MAX 16
433 434 435 436 437 438

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

Ondřej Zajíček's avatar
Ondřej Zajíček committed
439 440
#define RTD_NONE 0			/* Undefined next hop */
#define RTD_UNICAST 1			/* Next hop is neighbor router */
441 442 443
#define RTD_BLACKHOLE 2			/* Silently drop packets */
#define RTD_UNREACHABLE 3		/* Reject as unreachable */
#define RTD_PROHIBIT 4			/* Administratively prohibited */
444
#define RTD_MAX 5
445

446 447 448 449
					/* 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 */

450 451
#define RTAF_CACHED 1			/* This is a cached rta */

452 453 454
#define IGP_METRIC_UNKNOWN 0x80000000	/* Default igp_metric used when no other
					   protocol-specific metric is availabe */

455

456 457 458 459 460
const char * rta_dest_names[RTD_MAX];

static inline const char *rta_dest_name(uint n)
{ return (n < RTD_MAX) ? rta_dest_names[n] : "???"; }

461 462
/* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */
static inline int rte_is_reachable(rte *r)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
463
{ return r->attrs->dest == RTD_UNICAST; }
464 465


466 467 468 469 470
/*
 *	Extended Route Attributes
 */

typedef struct eattr {
471
  word id;				/* EA_CODE(PROTOCOL_..., protocol-dependent ID) */
472 473
  byte flags;				/* Protocol-dependent flags */
  byte type;				/* Attribute type and several flags (EAF_...) */
474 475 476 477 478 479
  union {
    u32 data;
    struct adata *ptr;			/* Attribute data elsewhere */
  } u;
} eattr;

Maria Matejka's avatar
Maria Matejka committed
480

481 482
#define EA_CODE(proto,id) (((proto) << 8) | (id))
#define EA_ID(ea) ((ea) & 0xff)
Maria Matejka's avatar
Maria Matejka committed
483 484 485 486 487 488
#define EA_PROTO(ea) ((ea) >> 8)
#define EA_CUSTOM(id) ((id) | EA_CUSTOM_BIT)
#define EA_IS_CUSTOM(ea) ((ea) & EA_CUSTOM_BIT)
#define EA_CUSTOM_ID(ea) ((ea) & ~EA_CUSTOM_BIT)

const char *ea_custom_name(uint ea);
489

490
#define EA_GEN_IGP_METRIC EA_CODE(PROTOCOL_NONE, 0)
491

492
#define EA_CODE_MASK 0xffff
Maria Matejka's avatar
Maria Matejka committed
493
#define EA_CUSTOM_BIT 0x8000
494
#define EA_ALLOW_UNDEF 0x10000		/* ea_find: allow EAF_TYPE_UNDEF */
495
#define EA_BIT(n) ((n) << 24)		/* Used in bitfield accessors */
496

497
#define EAF_TYPE_MASK 0x1f		/* Mask with this to get type */
498
#define EAF_TYPE_INT 0x01		/* 32-bit unsigned integer number */
499
#define EAF_TYPE_OPAQUE 0x02		/* Opaque byte string (not filterable) */
500 501
#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
502
#define EAF_TYPE_AS_PATH 0x06		/* BGP AS path (encoding per RFC 1771:4.3) */
503
#define EAF_TYPE_BITFIELD 0x09		/* 32-bit embedded bitfield */
Martin Mareš's avatar
Martin Mareš committed
504
#define EAF_TYPE_INT_SET 0x0a		/* Set of u32's (e.g., a community list) */
505
#define EAF_TYPE_EC_SET 0x0e		/* Set of pairs of u32's - ext. community list */
506 507
#define EAF_TYPE_LC_SET 0x12		/* Set of triplets of u32's - large community list */
#define EAF_TYPE_UNDEF 0x1f		/* `force undefined' entry */
508
#define EAF_EMBEDDED 0x01		/* Data stored in eattr.u.data (part of type spec) */
509
#define EAF_VAR_LENGTH 0x02		/* Attribute length is variable (part of type spec) */
Ondřej Zajíček's avatar
Ondřej Zajíček committed
510 511
#define EAF_ORIGINATED 0x20		/* The attribute has originated locally */
#define EAF_FRESH 0x40			/* An uncached attribute (e.g. modified in export filter) */
512
#define EAF_TEMP 0x80			/* A temporary attribute (the one stored in the tmp attr list) */
513

Ondřej Zajíček's avatar
Ondřej Zajíček committed
514
typedef struct adata {
Pavel Tvrdík's avatar
Pavel Tvrdík committed
515
  uint length;				/* Length of data */
516
  byte data[0];
Ondřej Zajíček's avatar
Ondřej Zajíček committed
517 518 519 520 521 522 523 524 525
} adata;

static inline struct adata *
lp_alloc_adata(struct linpool *pool, uint len)
{
  struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len);
  ad->length = len;
  return ad;
}
526

527 528 529 530
static inline int adata_same(struct adata *a, struct adata *b)
{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); }


531 532
typedef struct ea_list {
  struct ea_list *next;			/* In case we have an override list */
533
  byte flags;				/* Flags: EALF_... */
534
  byte rfu;
535
  word count;				/* Number of attributes */
536 537 538
  eattr attrs[0];			/* Attribute definitions themselves */
} ea_list;

539 540 541
#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 */
542

543 544 545 546 547 548
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);

549 550 551 552 553
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 */
};
554

555
eattr *ea_find(ea_list *, unsigned ea);
556
eattr *ea_walk(struct ea_walk_state *s, uint id, uint max);
557
int ea_get_int(ea_list *, unsigned ea, int def);
558 559
void ea_dump(ea_list *);
void ea_sort(ea_list *);		/* Sort entries in all sub-lists */
560
unsigned ea_scan(ea_list *);		/* How many bytes do we need for merged ea_list */
561
void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */
562
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
563
uint ea_hash(ea_list *e);	/* Calculate 16-bit hash value */
564
ea_list *ea_append(ea_list *to, ea_list *what);
565
void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max);
566

567 568 569 570 571 572 573 574 575
#define ea_normalize(ea) do { \
  if (ea->next) { \
    ea_list *t = alloca(ea_scan(ea)); \
    ea_merge(ea, t); \
    ea = t; \
  } \
  ea_sort(ea); \
} while(0) \

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
static inline eattr *
ea_set_attr(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, uintptr_t val)
{
  ea_list *a = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
  eattr *e = &a->attrs[0];

  a->flags = EALF_SORTED;
  a->count = 1;
  a->next = *to;
  *to = a;

  e->id = id;
  e->type = type;
  e->flags = flags;

  if (type & EAF_EMBEDDED)
    e->u.data = (u32) val;
  else
    e->u.ptr = (struct adata *) val;

  return e;
}

static inline void
ea_set_attr_u32(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, u32 val)
{ ea_set_attr(to, pool, id, flags, type, (uintptr_t) val); }

static inline void
ea_set_attr_ptr(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, struct adata *val)
{ ea_set_attr(to, pool, id, flags, type, (uintptr_t) val); }

static inline void
ea_set_attr_data(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, void *data, uint len)
{
  struct adata *a = lp_alloc_adata(pool, len);
  memcpy(a->data, data, len);
  ea_set_attr(to, pool, id, flags, type, (uintptr_t) a);
}


616
#define NEXTHOP_MAX_SIZE (sizeof(struct nexthop) + sizeof(u32)*MPLS_MAX_LABEL_STACK)
617 618 619

static inline size_t nexthop_size(const struct nexthop *nh)
{ return sizeof(struct nexthop) + sizeof(u32)*nh->labels; }
620 621 622 623 624
int nexthop__same(struct nexthop *x, struct nexthop *y); /* Compare multipath nexthops */
static inline int nexthop_same(struct nexthop *x, struct nexthop *y)
{ return (x == y) || nexthop__same(x, y); }
struct nexthop *nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp);
static inline void nexthop_link(struct rta *a, struct nexthop *from)
625
{ memcpy(&a->nh, from, nexthop_size(from)); }
Ondřej Zajíček's avatar
Ondřej Zajíček committed
626
void nexthop_insert(struct nexthop **n, struct nexthop *y);
627
int nexthop_is_sorted(struct nexthop *x);
628

629
void rta_init(void);
630
static inline size_t rta_size(const rta *a) { return sizeof(rta) + sizeof(u32)*a->nh.labels; }
631
#define RTA_MAX_SIZE (sizeof(rta) + sizeof(u32)*MPLS_MAX_LABEL_STACK)
632
rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
633
static inline int rta_is_cached(rta *r) { return r->aflags & RTAF_CACHED; }
634
static inline rta *rta_clone(rta *r) { r->uc++; return r; }
635 636
void rta__free(rta *r);
static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); }
637 638
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; }
639 640
void rta_dump(rta *);
void rta_dump_all(void);
641
void rta_show(struct cli *, rta *);
642 643 644 645 646 647 648 649 650

struct hostentry * rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep);
void rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls);

static inline void
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr gw, ip_addr ll, mpls_label_stack *mls)
{
  rta_apply_hostentry(a, rt_get_hostentry(tab, gw, ll, dep), mls);
}
651 652

/*
Ondřej Zajíček's avatar
Ondřej Zajíček committed
653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671
 * 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.
672 673 674 675 676
 */

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--; }

677 678 679 680
/*
 *	Default protocol preferences
 */

681
#define DEF_PREF_DIRECT		240	/* Directly connected */
682
#define DEF_PREF_STATIC		200	/* Static route */
683
#define DEF_PREF_OSPF		150	/* OSPF intra-area, inter-area and type 1 external routes */
684
#define DEF_PREF_BABEL		130	/* Babel */
685 686
#define DEF_PREF_RIP		120	/* RIP */
#define DEF_PREF_BGP		100	/* BGP */
687
#define DEF_PREF_RPKI		100	/* RPKI */
688
#define DEF_PREF_INHERITED	10	/* Routes inherited from other routing daemons */
689

690 691 692 693
/*
 *	Route Origin Authorization
 */

Pavel Tvrdík's avatar
Pavel Tvrdík committed
694 695 696
#define ROA_UNKNOWN	0
#define ROA_VALID	1
#define ROA_INVALID	2
697

Jan Moskyto Matejka's avatar
Jan Moskyto Matejka committed
698
#endif