1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
/*
* 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_
#include "lib/resource.h"
/*
* Generic data structure for storing network prefixes. Also used
* for the master routing table. Currently implemented as a radix
* trie.
*
* Available operations:
* - insertion of new entry
* - deletion of entry
* - searching of entry by network prefix
* - searching of entry by IP address (longest match)
*/
struct fib_node {
ip_addr prefix; /* In host order */
byte pxlen;
byte flags; /* ??? define them ??? */
byte pad0, pad1; /* ??? use ??? */
struct fib_node *next; /* Next in hash chain */
};
struct fib {
slab fib_slab; /* Slab holding all fib nodes */
struct fib_node *hash_table; /* Node hash table */
unsigned int hash_size; /* Number of hash table entries (a power of two) */
unsigned int entries; /* Number of entries */
unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */
void (*init)(struct fib_node *); /* Constructor */
};
void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *));
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 */
void fib_delete(void *); /* Remove fib entry */
void fib_free(struct fib *); /* Destroy the fib */
#define FIB_WALK(fib, op) { \
struct fib_node *f, **ff = (fib)->hash_table; \
unsigned int count = (fib)->hash_size; \
while (count--) \
for(f = *ff++; f; f=f->next) \
{ \
op \
} \
}
/*
* 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 */
/*
* Master Routing Table. Generally speaking, it's a FIB with each entry
* pointing to a list of route entries representing routes to given network.
* Each of the RTE's contains variable data (the preference and protocol-dependent
* metrics) and a pointer to route attribute block common for many routes).
*/
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_...) */
byte pflags; /* Protocol-specific flags */
word pref; /* Route preference */
u32 lastmod; /* Last modified (time) */
union { /* Protocol-dependent data (metrics etc.) */
#ifdef CONFIG_STATIC
struct {
} stat;
#endif
#ifdef CONFIG_RIP
struct {
byte metric; /* RIP metric */
u16 tag; /* External route tag */
} rip;
#endif
#ifdef CONFIG_OSPF
struct {
u32 metric1, metric2; /* OSPF Type 1 and Type 2 metrics */
u32 tag; /* External route tag */
} ospf;
#endif
#ifdef CONFIG_BGP
struct {
} bgp;
#endif
} u;
} rte;
#define REF_CHOSEN 1 /* Currently chosen route */
typedef struct rte rte;
/*
* 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.
*/
struct rtattr {
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_...) */
byte scope; /* Route scope (SCOPE_... -- see ip.h) */
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 */
ip_addr from; /* Advertising router */
struct iface *iface; /* Outgoing interface */
struct ea_list *attrs; /* Extended Attribute chain */
union { /* Protocol-specific data */
} u;
} 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 */
#define RTS_OSPF_BOUNDARY 11 /* OSPF route to boundary router (???) */
#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 */
#define RTF_EXTERIOR 1 /* Learned via exterior protocol */
#define RTF_TAGGED 2 /* Tagged external route learned via IGP */
/*
* Extended Route Attributes
*/
typedef struct eattr {
byte protocol; /* Protocol ID (EAP_...) */
byte flags; /* Attribute flags (EAF_...) */
byte id; /* Protocol-dependent ID */
byte rfu; /* ??? */
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 */
byte sorted; /* `Really sorted' flag (???) */
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)); \
memset(p, 0, sizeof(ea_list)); \
p->nattrs = cnt; \
} while(0)
/*
* 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 */
#endif
|
