]> git.ipfire.org Git - thirdparty/bird.git/blame - nest/route.h
RPKI protocol with one cache server per protocol
[thirdparty/bird.git] / nest / route.h
CommitLineData
58ef912c
MM
1/*
2 * BIRD Internet Routing Daemon -- Routing Table
3 *
50fe90ed 4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
58ef912c
MM
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
0e02abfd 12#include "lib/lists.h"
1feea03e 13#include "lib/resource.h"
7152e5ef 14#include "sysdep/unix/timer.h"
f4a60a9b 15//#include "nest/protocol.h"
58ef912c 16
f4a60a9b 17struct ea_list;
2326b001 18struct protocol;
4cc78c50 19struct proto;
f4a60a9b 20struct rte_src;
730f2e2c
MM
21struct symbol;
22struct filter;
23struct cli;
2326b001 24
58ef912c
MM
25/*
26 * Generic data structure for storing network prefixes. Also used
3ab001b9 27 * for the master routing table. Currently implemented as a hash
62aa008a 28 * table.
58ef912c
MM
29 *
30 * Available operations:
31 * - insertion of new entry
32 * - deletion of entry
62aa008a 33 * - searching for entry by network prefix
3ab001b9 34 * - asynchronous retrieval of fib contents
58ef912c
MM
35 */
36
37struct fib_node {
3ab001b9
MM
38 struct fib_node *next; /* Next in hash chain */
39 struct fib_iterator *readers; /* List of readers of this node */
fe9f1a6d 40 byte flags; /* User-defined, will be removed */
fe9f1a6d 41 net_addr addr[0];
3ab001b9
MM
42};
43
44struct fib_iterator { /* See lib/slists.h for an explanation */
45 struct fib_iterator *prev, *next; /* Must be synced with struct fib_node! */
3ab001b9
MM
46 byte efef; /* 0xff to distinguish between iterator and node */
47 byte pad[3];
0ba8a614 48 struct fib_node *node; /* Or NULL if freshly merged */
ae80a2de 49 uint hash;
58ef912c
MM
50};
51
fe9f1a6d 52typedef void (*fib_init_fn)(void *);
ce4aca09 53
58ef912c 54struct fib {
62aa008a
MM
55 pool *fib_pool; /* Pool holding all our data */
56 slab *fib_slab; /* Slab holding all fib nodes */
57 struct fib_node **hash_table; /* Node hash table */
ae80a2de
PT
58 uint hash_size; /* Number of hash table entries (a power of two) */
59 uint hash_order; /* Binary logarithm of hash_size */
04632fd7 60 uint hash_shift; /* 32 - hash_order */
fe9f1a6d 61 uint addr_type; /* Type of address data stored in fib (NET_*) */
f4a60a9b
OZ
62 uint node_size; /* FIB node size, 0 for nonuniform */
63 uint node_offset; /* Offset of fib_node struct inside of user data */
ae80a2de
PT
64 uint entries; /* Number of entries */
65 uint entries_min, entries_max; /* Entry count limits (else start rehashing) */
fe9f1a6d 66 fib_init_fn init; /* Constructor */
58ef912c
MM
67};
68
600998fc
OZ
69static inline void * fib_node_to_user(struct fib *f, struct fib_node *e)
70{ return e ? (void *) ((char *) e - f->node_offset) : NULL; }
71
72static inline struct fib_node * fib_user_to_node(struct fib *f, void *e)
73{ return e ? (void *) ((char *) e + f->node_offset) : NULL; }
74
fe9f1a6d 75void fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init);
0f7d5b1a 76void *fib_find(struct fib *, const net_addr *); /* Find or return NULL if doesn't exist */
0264ccf6 77void *fib_get_chain(struct fib *f, const net_addr *a); /* Find first node in linked list from hash table */
0f7d5b1a
OZ
78void *fib_get(struct fib *, const net_addr *); /* Find or create new if nonexistent */
79void *fib_route(struct fib *, const net_addr *); /* Longest-match routing lookup */
62aa008a 80void fib_delete(struct fib *, void *); /* Remove fib entry */
a8b60382 81void fib_free(struct fib *); /* Destroy the fib */
3ab001b9
MM
82void fib_check(struct fib *); /* Consistency check for debugging */
83
84void fit_init(struct fib_iterator *, struct fib *); /* Internal functions, don't call */
85struct fib_node *fit_get(struct fib *, struct fib_iterator *);
86void fit_put(struct fib_iterator *, struct fib_node *);
8465dccb
OZ
87void fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos);
88
600998fc
OZ
89
90#define FIB_WALK(fib, type, z) do { \
91 struct fib_node *fn_, **ff_ = (fib)->hash_table; \
92 uint count_ = (fib)->hash_size; \
93 type *z; \
94 while (count_--) \
95 for (fn_ = *ff_++; z = fib_node_to_user(fib, fn_); fn_=fn_->next)
236d4eb8
MM
96
97#define FIB_WALK_END } while (0)
a8b60382 98
3ab001b9
MM
99#define FIB_ITERATE_INIT(it, fib) fit_init(it, fib)
100
600998fc
OZ
101#define FIB_ITERATE_START(fib, it, type, z) do { \
102 struct fib_node *fn_ = fit_get(fib, it); \
103 uint count_ = (fib)->hash_size; \
104 uint hpos_ = (it)->hash; \
105 type *z; \
3ab001b9 106 for(;;) { \
600998fc 107 if (!fn_) \
8abbde02 108 { \
600998fc 109 if (++hpos_ >= count_) \
8abbde02 110 break; \
600998fc 111 fn_ = (fib)->hash_table[hpos_]; \
8abbde02 112 continue; \
600998fc
OZ
113 } \
114 z = fib_node_to_user(fib, fn_);
3ab001b9 115
600998fc 116#define FIB_ITERATE_END fn_ = fn_->next; } } while(0)
3ab001b9 117
600998fc 118#define FIB_ITERATE_PUT(it) fit_put(it, fn_)
3ab001b9 119
600998fc 120#define FIB_ITERATE_PUT_NEXT(it, fib) fit_put_next(fib, it, fn_, hpos_)
8465dccb
OZ
121
122#define FIB_ITERATE_UNLINK(it, fib) fit_get(fib, it)
123
124
58ef912c 125/*
08e2d625
MM
126 * Master Routing Tables. Generally speaking, each of them contains a FIB
127 * with each entry pointing to a list of route entries representing routes
128 * to given network (with the selected one at the head).
129 *
58ef912c 130 * Each of the RTE's contains variable data (the preference and protocol-dependent
62aa008a 131 * metrics) and a pointer to a route attribute block common for many routes).
08e2d625
MM
132 *
133 * It's guaranteed that there is at most one RTE for every (prefix,proto) pair.
58ef912c
MM
134 */
135
0e02abfd
MM
136struct rtable_config {
137 node n;
138 char *name;
139 struct rtable *table;
7de45ba4 140 struct proto_config *krt_attached; /* Kernel syncer attached to this table */
fe9f1a6d 141 uint addr_type; /* Type of address data stored in table (NET_*) */
b9626ec6
MM
142 int gc_max_ops; /* Maximum number of operations before GC is run */
143 int gc_min_time; /* Minimum time between two consecutive GC runs */
26822d8f 144 byte sorted; /* Routes of network are sorted according to rte_better() */
0e02abfd
MM
145};
146
62aa008a 147typedef struct rtable {
0e02abfd 148 node n; /* Node in list of all tables */
62aa008a
MM
149 struct fib fib;
150 char *name; /* Name of this table */
f4a60a9b 151 list channels; /* List of attached channels (struct channel) */
fe9f1a6d 152 uint addr_type; /* Type of address data stored in table (NET_*) */
9c11ec9e 153 int pipe_busy; /* Pipe loop detection */
50fe90ed 154 int use_count; /* Number of protocols using this table */
cfe34a31 155 struct hostcache *hostcache;
b9626ec6 156 struct rtable_config *config; /* Configuration of this table */
50fe90ed
MM
157 struct config *deleted; /* Table doesn't exist in current configuration,
158 * delete as soon as use_count becomes 0 and remove
159 * obstacle from this routing table.
160 */
cfe34a31 161 struct event *rt_event; /* Routing table event */
b9626ec6
MM
162 int gc_counter; /* Number of operations since last GC */
163 bird_clock_t gc_time; /* Time of last GC */
9135c1f0 164 byte prune_state; /* Table prune state, 1 -> scheduled, 2-> running */
cfe34a31
OZ
165 byte hcu_scheduled; /* Hostcache update is scheduled */
166 byte nhu_state; /* Next Hop Update state */
fb829de6 167 struct fib_iterator prune_fit; /* Rtable prune FIB iterator */
cfe34a31 168 struct fib_iterator nhu_fit; /* Next Hop Update FIB iterator */
62aa008a
MM
169} rtable;
170
58ef912c 171typedef struct network {
58ef912c 172 struct rte *routes; /* Available routes for this network */
fe9f1a6d 173 struct fib_node n; /* FIB flags reserved for kernel syncer */
58ef912c
MM
174} net;
175
cfe34a31 176struct hostcache {
f2b76f2c
OZ
177 slab *slab; /* Slab holding all hostentries */
178 struct hostentry **hash_table; /* Hash table for hostentries */
179 unsigned hash_order, hash_shift;
180 unsigned hash_max, hash_min;
181 unsigned hash_items;
c477f489
OZ
182 linpool *lp; /* Linpool for trie */
183 struct f_trie *trie; /* Trie of prefixes that might affect hostentries */
184 list hostentries; /* List of all hostentries */
cfe34a31
OZ
185 byte update_hostcache;
186};
187
188struct hostentry {
cfe34a31 189 node ln;
1b180121
OZ
190 ip_addr addr; /* IP address of host, part of key */
191 ip_addr link; /* (link-local) IP address of host, used as gw
192 if host is directly attached */
acb04cfd 193 struct rtable *tab; /* Dependent table, part of key */
f2b76f2c
OZ
194 struct hostentry *next; /* Next in hash chain */
195 unsigned hash_key; /* Hash key */
cfe34a31 196 unsigned uc; /* Use count */
7e95c05d 197 struct rta *src; /* Source rta entry */
cfe34a31
OZ
198 ip_addr gw; /* Chosen next hop */
199 byte dest; /* Chosen route destination type (RTD_...) */
d1e146f2 200 u32 igp_metric; /* Chosen route IGP metric */
cfe34a31
OZ
201};
202
58ef912c
MM
203typedef struct rte {
204 struct rte *next;
a0762910 205 net *net; /* Network this RTE belongs to */
f4a60a9b 206 struct channel *sender; /* Channel used to send the route to the routing table */
1b769b08 207 struct rta *attrs; /* Attributes of this route */
58ef912c 208 byte flags; /* Flags (REF_...) */
481f6985 209 byte pflags; /* Protocol-specific flags */
58ef912c 210 word pref; /* Route preference */
a2ccbb0b 211 bird_clock_t lastmod; /* Last modified */
58ef912c 212 union { /* Protocol-dependent data (metrics etc.) */
58ef912c
MM
213#ifdef CONFIG_RIP
214 struct {
8465dccb
OZ
215 struct iface *from; /* Incoming iface */
216 u8 metric; /* RIP metric */
481f6985 217 u16 tag; /* External route tag */
58ef912c
MM
218 } rip;
219#endif
220#ifdef CONFIG_OSPF
221 struct {
222 u32 metric1, metric2; /* OSPF Type 1 and Type 2 metrics */
481f6985 223 u32 tag; /* External route tag */
c27b2449 224 u32 router_id; /* Router that originated this route */
58ef912c 225 } ospf;
be4cd99a
OZ
226#endif
227#ifdef CONFIG_BGP
228 struct {
229 u8 suppressed; /* Used for deterministic MED comparison */
230 } bgp;
937e75d8
OZ
231#endif
232#ifdef CONFIG_BABEL
233 struct {
234 u16 metric; /* Babel metric */
235 u64 router_id; /* Babel router id */
236 } babel;
58ef912c 237#endif
c10421d3
MM
238 struct { /* Routes generated by krt sync (both temporary and inherited ones) */
239 s8 src; /* Alleged route source (see krt.h) */
240 u8 proto; /* Kernel source protocol ID */
c10421d3 241 u8 seen; /* Seen during last scan */
e86cfd41 242 u8 best; /* Best route in network, propagated to core */
c10421d3
MM
243 u32 metric; /* Kernel metric */
244 } krt;
58ef912c
MM
245 } u;
246} rte;
247
00a09f3c 248#define REF_COW 1 /* Copy this rte on write */
15550957 249#define REF_FILTERED 2 /* Route is rejected by import filter */
0c791f87
OZ
250#define REF_STALE 4 /* Route is stale in a refresh cycle */
251#define REF_DISCARD 8 /* Route is scheduled for discard */
cf98be7b
OZ
252
253/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */
15550957 254static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); }
cf98be7b 255
15550957
OZ
256/* Route just has REF_FILTERED flag */
257static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED); }
cf98be7b 258
e2dc2f30 259
23ac9e9a 260/* Types of route announcement, also used as flags */
00a09f3c
OZ
261#define RA_OPTIMAL 1 /* Announcement of optimal route change */
262#define RA_ACCEPTED 2 /* Announcement of first accepted route */
263#define RA_ANY 3 /* Announcement of any route change */
8d9eef17 264#define RA_MERGED 4 /* Announcement of optimal route merged with next ones */
23ac9e9a 265
36da2857
OZ
266/* Return value of import_control() callback */
267#define RIC_ACCEPT 1 /* Accepted by protocol */
268#define RIC_PROCESS 0 /* Process it through import filter */
269#define RIC_REJECT -1 /* Rejected by protocol */
270#define RIC_DROP -2 /* Silently dropped by protocol */
271
0e02abfd 272struct config;
2326b001
MM
273
274void rt_init(void);
0e02abfd 275void rt_preconfig(struct config *);
50fe90ed
MM
276void rt_commit(struct config *new, struct config *old);
277void rt_lock_table(rtable *);
278void rt_unlock_table(rtable *);
b9626ec6 279void rt_setup(pool *, rtable *, char *, struct rtable_config *);
0264ccf6
PT
280static inline net *net_find(rtable *tab, const net_addr *addr) { return (net *) fib_find(&tab->fib, addr); }
281static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) fib_get(&tab->fib, addr); }
286e2011
OZ
282void *net_route(rtable *tab, const net_addr *n);
283int net_roa_check(rtable *tab, const net_addr *n, u32 asn);
094d2bdb 284rte *rte_find(net *net, struct rte_src *src);
1b769b08 285rte *rte_get_temp(struct rta *);
65d2a88d 286void rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src);
f4a60a9b 287/* rte_update() moved to protocol.h to avoid dependency conflicts */
0e02abfd 288void rte_discard(rtable *tab, rte *old);
fe9f1a6d 289int rt_examine(rtable *t, net_addr *a, struct proto *p, struct filter *filter);
f4a60a9b
OZ
290rte *rt_export_merged(struct channel *c, net *net, rte **rt_free, struct ea_list **tmpa, int silent);
291void rt_refresh_begin(rtable *t, struct channel *c);
292void rt_refresh_end(rtable *t, struct channel *c);
293void rt_schedule_prune(rtable *t);
a0762910 294void rte_dump(rte *);
04925e90 295void rte_free(rte *);
e2dc2f30
MM
296rte *rte_do_cow(rte *);
297static inline rte * rte_cow(rte *r) { return (r->flags & REF_COW) ? rte_do_cow(r) : r; }
8d9eef17 298rte *rte_cow_rta(rte *r, linpool *lp);
2326b001 299void rt_dump(rtable *);
a2ccbb0b 300void rt_dump_all(void);
f4a60a9b
OZ
301int rt_feed_channel(struct channel *c);
302void rt_feed_channel_abort(struct channel *c);
fe9f1a6d 303struct rtable_config *rt_new_table(struct symbol *s, uint addr_type);
2326b001 304
0c791f87 305
730f2e2c 306struct rt_show_data {
04632fd7 307 net_addr *addr;
730f2e2c
MM
308 rtable *table;
309 struct filter *filter;
310 int verbose;
311 struct fib_iterator fit;
4d176e14 312 struct proto *show_protocol;
ea2ae6dd 313 struct proto *export_protocol;
f4a60a9b 314 struct channel *export_channel;
15550957 315 int export_mode, primary_only, filtered;
ce1da96e 316 struct config *running_on_config;
23693958 317 int net_counter, rt_counter, show_counter;
56d6c530 318 int stats, show_for;
730f2e2c
MM
319};
320void rt_show(struct rt_show_data *);
321
7aa80901
OZ
322/* Value of export_mode in struct rt_show_data */
323#define RSEM_NONE 0 /* Export mode not used */
324#define RSEM_PREEXPORT 1 /* Routes ready for export, before filtering */
325#define RSEM_EXPORT 2 /* Routes accepted by export filter */
326#define RSEM_NOEXPORT 3 /* Routes rejected by export filter */
327
58ef912c
MM
328/*
329 * Route Attributes
330 *
331 * Beware: All standard BGP attributes must be represented here instead
332 * of making them local to the route. This is needed to ensure proper
333 * construction of BGP route attribute lists.
334 */
335
7e95c05d
OZ
336/* Multipath next-hop */
337struct mpnh {
338 ip_addr gw; /* Next hop */
339 struct iface *iface; /* Outgoing interface */
340 struct mpnh *next;
e348ef01 341 byte weight;
7e95c05d
OZ
342};
343
094d2bdb
OZ
344struct rte_src {
345 struct rte_src *next; /* Hash chain */
346 struct proto *proto; /* Protocol the source is based on */
347 u32 private_id; /* Private ID, assigned by the protocol */
348 u32 global_id; /* Globally unique ID of the source */
349 unsigned uc; /* Use count */
350};
351
352
1b769b08 353typedef struct rta {
ee76a92a 354 struct rta *next, **pprev; /* Hash chain */
9a74622c
JMM
355 u32 uc; /* Use count */
356 u32 hash_key; /* Hash over important fields */
357 struct mpnh *nexthops; /* Next-hops for multipath routes */
358 struct ea_list *eattrs; /* Extended Attribute chain */
094d2bdb 359 struct rte_src *src; /* Route source that created the route */
9a74622c
JMM
360 struct hostentry *hostentry; /* Hostentry for recursive next-hops */
361 struct iface *iface; /* Outgoing interface */
362 ip_addr gw; /* Next hop */
363 ip_addr from; /* Advertising router */
364 u32 igp_metric; /* IGP metric to next hop (for iBGP routes) */
58ef912c 365 byte source; /* Route source (RTS_...) */
a8b60382 366 byte scope; /* Route scope (SCOPE_... -- see ip.h) */
58ef912c
MM
367 byte cast; /* Casting type (RTC_...) */
368 byte dest; /* Route destination type (RTD_...) */
c8518ae1 369 byte flags; /* Route flags (RTF_...), now unused */
04925e90 370 byte aflags; /* Attribute cache flags (RTAF_...) */
58ef912c
MM
371} rta;
372
618533af 373#define RTS_DUMMY 0 /* Dummy route to be removed soon */
58ef912c
MM
374#define RTS_STATIC 1 /* Normal static route */
375#define RTS_INHERIT 2 /* Route inherited from kernel */
376#define RTS_DEVICE 3 /* Device route */
377#define RTS_STATIC_DEVICE 4 /* Static device route */
378#define RTS_REDIRECT 5 /* Learned via redirect */
379#define RTS_RIP 6 /* RIP route */
beaf86e1 380#define RTS_OSPF 7 /* OSPF route */
8bf684ec 381#define RTS_OSPF_IA 8 /* OSPF inter-area route */
98ac6176
OF
382#define RTS_OSPF_EXT1 9 /* OSPF external route type 1 */
383#define RTS_OSPF_EXT2 10 /* OSPF external route type 2 */
384#define RTS_BGP 11 /* BGP route */
385#define RTS_PIPE 12 /* Inter-table wormhole */
937e75d8 386#define RTS_BABEL 13 /* Babel route */
65d2a88d
PT
387#define RTS_RPKI 14 /* Route Origin Authorization */
388
58ef912c 389
58ef912c
MM
390#define RTC_UNICAST 0
391#define RTC_BROADCAST 1
392#define RTC_MULTICAST 2
393#define RTC_ANYCAST 3 /* IPv6 Anycast */
394
395#define RTD_ROUTER 0 /* Next hop is neighbor router */
396#define RTD_DEVICE 1 /* Points to device */
397#define RTD_BLACKHOLE 2 /* Silently drop packets */
398#define RTD_UNREACHABLE 3 /* Reject as unreachable */
399#define RTD_PROHIBIT 4 /* Administratively prohibited */
7e95c05d
OZ
400#define RTD_MULTIPATH 5 /* Multipath route (nexthops != NULL) */
401#define RTD_NONE 6 /* Invalid RTD */
58ef912c 402
32f95476
OZ
403 /* Flags for net->n.flags, used by kernel syncer */
404#define KRF_INSTALLED 0x80 /* This route should be installed in the kernel */
405#define KRF_SYNC_ERROR 0x40 /* Error during kernel table synchronization */
406
04925e90
MM
407#define RTAF_CACHED 1 /* This is a cached rta */
408
d1e146f2
OZ
409#define IGP_METRIC_UNKNOWN 0x80000000 /* Default igp_metric used when no other
410 protocol-specific metric is availabe */
411
8d9eef17
OZ
412
413/* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */
414static inline int rte_is_reachable(rte *r)
415{ uint d = r->attrs->dest; return (d == RTD_ROUTER) || (d == RTD_DEVICE) || (d == RTD_MULTIPATH); }
416
417
58ef912c
MM
418/*
419 * Extended Route Attributes
420 */
421
422typedef struct eattr {
b77ae37d
MM
423 word id; /* EA_CODE(EAP_..., protocol-dependent ID) */
424 byte flags; /* Protocol-dependent flags */
425 byte type; /* Attribute type and several flags (EAF_...) */
58ef912c
MM
426 union {
427 u32 data;
428 struct adata *ptr; /* Attribute data elsewhere */
429 } u;
430} eattr;
431
432#define EAP_GENERIC 0 /* Generic attributes */
433#define EAP_BGP 1 /* BGP attributes */
9c9e49ac 434#define EAP_RIP 2 /* RIP */
5919c66e 435#define EAP_OSPF 3 /* OSPF */
71ca7716 436#define EAP_KRT 4 /* Kernel route attributes */
937e75d8
OZ
437#define EAP_BABEL 5 /* Babel attributes */
438#define EAP_MAX 6
58ef912c 439
b77ae37d
MM
440#define EA_CODE(proto,id) (((proto) << 8) | (id))
441#define EA_PROTO(ea) ((ea) >> 8)
442#define EA_ID(ea) ((ea) & 0xff)
443
ba5e5940
OZ
444#define EA_GEN_IGP_METRIC EA_CODE(EAP_GENERIC, 0)
445
8d24b689
MM
446#define EA_CODE_MASK 0xffff
447#define EA_ALLOW_UNDEF 0x10000 /* ea_find: allow EAF_TYPE_UNDEF */
315f23a0 448#define EA_BIT(n) ((n) << 24) /* Used in bitfield accessors */
8d24b689 449
b77ae37d 450#define EAF_TYPE_MASK 0x0f /* Mask with this to get type */
315f23a0 451#define EAF_TYPE_INT 0x01 /* 32-bit unsigned integer number */
b77ae37d 452#define EAF_TYPE_OPAQUE 0x02 /* Opaque byte string (not filterable) */
ca97b489
MM
453#define EAF_TYPE_IP_ADDRESS 0x04 /* IP address */
454#define EAF_TYPE_ROUTER_ID 0x05 /* Router ID (IPv4 address) */
b475c543 455#define EAF_TYPE_AS_PATH 0x06 /* BGP AS path (encoding per RFC 1771:4.3) */
315f23a0 456#define EAF_TYPE_BITFIELD 0x09 /* 32-bit embedded bitfield */
b475c543 457#define EAF_TYPE_INT_SET 0x0a /* Set of u32's (e.g., a community list) */
42a0c054 458#define EAF_TYPE_EC_SET 0x0e /* Set of pairs of u32's - ext. community list */
8d24b689 459#define EAF_TYPE_UNDEF 0x0f /* `force undefined' entry */
b77ae37d 460#define EAF_EMBEDDED 0x01 /* Data stored in eattr.u.data (part of type spec) */
ca97b489 461#define EAF_VAR_LENGTH 0x02 /* Attribute length is variable (part of type spec) */
51a183af 462#define EAF_ORIGINATED 0x40 /* The attribute has originated locally */
9f4929e7 463#define EAF_TEMP 0x80 /* A temporary attribute (the one stored in the tmp attr list) */
58ef912c
MM
464
465struct adata {
ae80a2de 466 uint length; /* Length of data */
58ef912c
MM
467 byte data[0];
468};
469
28a10f84
OZ
470static inline int adata_same(struct adata *a, struct adata *b)
471{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); }
472
473
58ef912c
MM
474typedef struct ea_list {
475 struct ea_list *next; /* In case we have an override list */
b77ae37d 476 byte flags; /* Flags: EALF_... */
58ef912c 477 byte rfu;
b77ae37d 478 word count; /* Number of attributes */
58ef912c
MM
479 eattr attrs[0]; /* Attribute definitions themselves */
480} ea_list;
481
b77ae37d
MM
482#define EALF_SORTED 1 /* Attributes are sorted by code */
483#define EALF_BISECT 2 /* Use interval bisection for searching */
484#define EALF_CACHED 4 /* Attributes belonging to cached rta */
58ef912c 485
094d2bdb
OZ
486struct rte_src *rt_find_source(struct proto *p, u32 id);
487struct rte_src *rt_get_source(struct proto *p, u32 id);
488static inline void rt_lock_source(struct rte_src *src) { src->uc++; }
489static inline void rt_unlock_source(struct rte_src *src) { src->uc--; }
490void rt_prune_sources(void);
491
9fdf9d29
OZ
492struct ea_walk_state {
493 ea_list *eattrs; /* Ccurrent ea_list, initially set by caller */
494 eattr *ea; /* Current eattr, initially NULL */
495 u32 visited[4]; /* Bitfield, limiting max to 128 */
496};
094d2bdb 497
b77ae37d 498eattr *ea_find(ea_list *, unsigned ea);
9fdf9d29 499eattr *ea_walk(struct ea_walk_state *s, uint id, uint max);
c0100454 500int ea_get_int(ea_list *, unsigned ea, int def);
b77ae37d
MM
501void ea_dump(ea_list *);
502void ea_sort(ea_list *); /* Sort entries in all sub-lists */
6f57dcc0 503unsigned ea_scan(ea_list *); /* How many bytes do we need for merged ea_list */
b77ae37d 504void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */
6f57dcc0 505int ea_same(ea_list *x, ea_list *y); /* Test whether two ea_lists are identical */
ae80a2de 506uint ea_hash(ea_list *e); /* Calculate 16-bit hash value */
ce1da96e 507ea_list *ea_append(ea_list *to, ea_list *what);
315f23a0 508void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max);
58ef912c 509
7e95c05d
OZ
510int mpnh__same(struct mpnh *x, struct mpnh *y); /* Compare multipath nexthops */
511static inline int mpnh_same(struct mpnh *x, struct mpnh *y)
512{ return (x == y) || mpnh__same(x, y); }
d217ba51 513struct mpnh *mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp);
7e95c05d 514
2326b001
MM
515void rta_init(void);
516rta *rta_lookup(rta *); /* Get rta equivalent to this one, uc++ */
094d2bdb 517static inline int rta_is_cached(rta *r) { return r->aflags & RTAF_CACHED; }
2326b001 518static inline rta *rta_clone(rta *r) { r->uc++; return r; }
b77ae37d
MM
519void rta__free(rta *r);
520static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); }
8d9eef17
OZ
521rta *rta_do_cow(rta *o, linpool *lp);
522static inline rta * rta_cow(rta *r, linpool *lp) { return rta_is_cached(r) ? rta_do_cow(r, lp) : r; }
2326b001
MM
523void rta_dump(rta *);
524void rta_dump_all(void);
ce1da96e 525void rta_show(struct cli *, rta *, ea_list *);
1b180121 526void rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll);
cfe34a31
OZ
527
528/*
acb04cfd
OZ
529 * rta_set_recursive_next_hop() acquires hostentry from hostcache and fills
530 * rta->hostentry field. New hostentry has zero use count. Cached rta locks its
531 * hostentry (increases its use count), uncached rta does not lock it. Hostentry
532 * with zero use count is removed asynchronously during host cache update,
533 * therefore it is safe to hold such hostentry temorarily. Hostentry holds a
534 * lock for a 'source' rta, mainly to share multipath nexthops.
535 *
536 * There is no need to hold a lock for hostentry->dep table, because that table
537 * contains routes responsible for that hostentry, and therefore is non-empty if
538 * given hostentry has non-zero use count. If the hostentry has zero use count,
539 * the entry is removed before dep is referenced.
540 *
541 * The protocol responsible for routes with recursive next hops should hold a
542 * lock for a 'source' table governing that routes (argument tab to
543 * rta_set_recursive_next_hop()), because its routes reference hostentries
544 * (through rta) related to the governing table. When all such routes are
545 * removed, rtas are immediately removed achieving zero uc. Then the 'source'
546 * table lock could be immediately released, although hostentries may still
547 * exist - they will be freed together with the 'source' table.
cfe34a31
OZ
548 */
549
550static inline void rt_lock_hostentry(struct hostentry *he) { if (he) he->uc++; }
551static inline void rt_unlock_hostentry(struct hostentry *he) { if (he) he->uc--; }
552
2326b001 553
3991d84e
MM
554extern struct protocol *attr_class_to_protocol[EAP_MAX];
555
a8b60382
MM
556/*
557 * Default protocol preferences
558 */
559
560#define DEF_PREF_DIRECT 240 /* Directly connected */
561#define DEF_PREF_STATIC 200 /* Static route */
916c8c0a 562#define DEF_PREF_OSPF 150 /* OSPF intra-area, inter-area and type 1 external routes */
937e75d8 563#define DEF_PREF_BABEL 130 /* Babel */
a8b60382
MM
564#define DEF_PREF_RIP 120 /* RIP */
565#define DEF_PREF_BGP 100 /* BGP */
65d2a88d 566#define DEF_PREF_RPKI 100 /* RPKI */
916c8c0a 567#define DEF_PREF_INHERITED 10 /* Routes inherited from other routing daemons */
a8b60382 568
af582c48
OZ
569/*
570 * Route Origin Authorization
571 */
572
650b4189
PT
573#define ROA_UNKNOWN 0
574#define ROA_VALID 1
575#define ROA_INVALID 2
af582c48 576
9656dce7 577#endif