]>
Commit | Line | Data |
---|---|---|
62aa008a | 1 | /* |
58740ed4 | 2 | * BIRD -- Routing Tables |
62aa008a | 3 | * |
50fe90ed | 4 | * (c) 1998--2000 Martin Mares <mj@ucw.cz> |
62aa008a MM |
5 | * |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
58740ed4 MM |
9 | /** |
10 | * DOC: Routing tables | |
11 | * | |
12 | * Routing tables are probably the most important structures BIRD uses. They | |
13 | * hold all the information about known networks, the associated routes and | |
14 | * their attributes. | |
15 | * | |
725270cb | 16 | * There are multiple routing tables (a primary one together with any |
58740ed4 MM |
17 | * number of secondary ones if requested by the configuration). Each table |
18 | * is basically a FIB containing entries describing the individual | |
58f7d004 | 19 | * destination networks. For each network (represented by structure &net), |
725270cb MM |
20 | * there is a one-way linked list of route entries (&rte), the first entry |
21 | * on the list being the best one (i.e., the one we currently use | |
58740ed4 MM |
22 | * for routing), the order of the other ones is undetermined. |
23 | * | |
24 | * The &rte contains information specific to the route (preference, protocol | |
25 | * metrics, time of last modification etc.) and a pointer to a &rta structure | |
26 | * (see the route attribute module for a precise explanation) holding the | |
27 | * remaining route attributes which are expected to be shared by multiple | |
28 | * routes in order to conserve memory. | |
29 | */ | |
30 | ||
6b9fa320 | 31 | #undef LOCAL_DEBUG |
1a54b1c6 | 32 | |
62aa008a MM |
33 | #include "nest/bird.h" |
34 | #include "nest/route.h" | |
2326b001 | 35 | #include "nest/protocol.h" |
730f2e2c | 36 | #include "nest/iface.h" |
2326b001 | 37 | #include "lib/resource.h" |
5996da6a | 38 | #include "lib/event.h" |
00b85905 | 39 | #include "lib/timer.h" |
730f2e2c | 40 | #include "lib/string.h" |
0e02abfd | 41 | #include "conf/conf.h" |
529c4149 | 42 | #include "filter/filter.h" |
4f082dfa | 43 | #include "filter/data.h" |
586c1800 | 44 | #include "lib/hash.h" |
221135d6 | 45 | #include "lib/string.h" |
10af3676 | 46 | #include "lib/alloca.h" |
7d875e09 | 47 | |
acb60628 OZ |
48 | pool *rt_table_pool; |
49 | ||
2326b001 | 50 | static slab *rte_slab; |
e2dc2f30 | 51 | static linpool *rte_update_pool; |
2326b001 | 52 | |
863ecfc7 | 53 | list routing_tables; |
5996da6a | 54 | |
cfe34a31 OZ |
55 | static void rt_free_hostcache(rtable *tab); |
56 | static void rt_notify_hostcache(rtable *tab, net *net); | |
57 | static void rt_update_hostcache(rtable *tab); | |
58 | static void rt_next_hop_update(rtable *tab); | |
f4a60a9b | 59 | static inline void rt_prune_table(rtable *tab); |
00b85905 | 60 | static inline void rt_schedule_notify(rtable *tab); |
0c791f87 | 61 | |
cfd46ee4 | 62 | |
d1e146f2 | 63 | /* Like fib_route(), but skips empty net entries */ |
04632fd7 | 64 | static inline void * |
7ee07a3c | 65 | net_route_ip4(rtable *t, net_addr_ip4 *n) |
d1e146f2 | 66 | { |
04632fd7 | 67 | net *r; |
d1e146f2 | 68 | |
7ee07a3c | 69 | while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0)) |
04632fd7 OZ |
70 | { |
71 | n->pxlen--; | |
72 | ip4_clrbit(&n->prefix, n->pxlen); | |
73 | } | |
74 | ||
75 | return r; | |
76 | } | |
77 | ||
78 | static inline void * | |
7ee07a3c | 79 | net_route_ip6(rtable *t, net_addr_ip6 *n) |
04632fd7 OZ |
80 | { |
81 | net *r; | |
82 | ||
7ee07a3c | 83 | while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0)) |
04632fd7 OZ |
84 | { |
85 | n->pxlen--; | |
86 | ip6_clrbit(&n->prefix, n->pxlen); | |
87 | } | |
88 | ||
89 | return r; | |
90 | } | |
91 | ||
be17805c OZ |
92 | static inline void * |
93 | net_route_ip6_sadr(rtable *t, net_addr_ip6_sadr *n) | |
94 | { | |
95 | struct fib_node *fn; | |
96 | ||
97 | while (1) | |
98 | { | |
99 | net *best = NULL; | |
100 | int best_pxlen = 0; | |
101 | ||
102 | /* We need to do dst first matching. Since sadr addresses are hashed on dst | |
103 | prefix only, find the hash table chain and go through it to find the | |
104 | match with the smallest matching src prefix. */ | |
105 | for (fn = fib_get_chain(&t->fib, (net_addr *) n); fn; fn = fn->next) | |
106 | { | |
107 | net_addr_ip6_sadr *a = (void *) fn->addr; | |
108 | ||
109 | if (net_equal_dst_ip6_sadr(n, a) && | |
110 | net_in_net_src_ip6_sadr(n, a) && | |
111 | (a->src_pxlen >= best_pxlen)) | |
112 | { | |
113 | best = fib_node_to_user(&t->fib, fn); | |
114 | best_pxlen = a->src_pxlen; | |
115 | } | |
116 | } | |
117 | ||
118 | if (best) | |
119 | return best; | |
120 | ||
121 | if (!n->dst_pxlen) | |
122 | break; | |
123 | ||
124 | n->dst_pxlen--; | |
125 | ip6_clrbit(&n->dst_prefix, n->dst_pxlen); | |
126 | } | |
127 | ||
128 | return NULL; | |
129 | } | |
130 | ||
286e2011 OZ |
131 | void * |
132 | net_route(rtable *tab, const net_addr *n) | |
0264ccf6 | 133 | { |
286e2011 | 134 | ASSERT(tab->addr_type == n->type); |
0264ccf6 | 135 | |
286e2011 OZ |
136 | net_addr *n0 = alloca(n->length); |
137 | net_copy(n0, n); | |
138 | ||
139 | switch (n->type) | |
140 | { | |
141 | case NET_IP4: | |
142 | case NET_VPN4: | |
143 | case NET_ROA4: | |
7ee07a3c | 144 | return net_route_ip4(tab, (net_addr_ip4 *) n0); |
286e2011 OZ |
145 | |
146 | case NET_IP6: | |
147 | case NET_VPN6: | |
148 | case NET_ROA6: | |
7ee07a3c | 149 | return net_route_ip6(tab, (net_addr_ip6 *) n0); |
286e2011 | 150 | |
be17805c OZ |
151 | case NET_IP6_SADR: |
152 | return net_route_ip6_sadr(tab, (net_addr_ip6_sadr *) n0); | |
153 | ||
286e2011 OZ |
154 | default: |
155 | return NULL; | |
156 | } | |
157 | } | |
158 | ||
159 | ||
160 | static int | |
161 | net_roa_check_ip4(rtable *tab, const net_addr_ip4 *px, u32 asn) | |
162 | { | |
163 | struct net_addr_roa4 n = NET_ADDR_ROA4(px->prefix, px->pxlen, 0, 0); | |
0264ccf6 | 164 | struct fib_node *fn; |
286e2011 OZ |
165 | int anything = 0; |
166 | ||
0264ccf6 PT |
167 | while (1) |
168 | { | |
169 | for (fn = fib_get_chain(&tab->fib, (net_addr *) &n); fn; fn = fn->next) | |
170 | { | |
286e2011 | 171 | net_addr_roa4 *roa = (void *) fn->addr; |
0264ccf6 | 172 | net *r = fib_node_to_user(&tab->fib, fn); |
286e2011 OZ |
173 | |
174 | if (net_equal_prefix_roa4(roa, &n) && rte_is_valid(r->routes)) | |
0264ccf6 | 175 | { |
0264ccf6 PT |
176 | anything = 1; |
177 | if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen)) | |
178 | return ROA_VALID; | |
179 | } | |
180 | } | |
181 | ||
182 | if (n.pxlen == 0) | |
183 | break; | |
184 | ||
185 | n.pxlen--; | |
186 | ip4_clrbit(&n.prefix, n.pxlen); | |
187 | } | |
188 | ||
189 | return anything ? ROA_INVALID : ROA_UNKNOWN; | |
190 | } | |
191 | ||
286e2011 OZ |
192 | static int |
193 | net_roa_check_ip6(rtable *tab, const net_addr_ip6 *px, u32 asn) | |
0264ccf6 PT |
194 | { |
195 | struct net_addr_roa6 n = NET_ADDR_ROA6(px->prefix, px->pxlen, 0, 0); | |
0264ccf6 | 196 | struct fib_node *fn; |
286e2011 OZ |
197 | int anything = 0; |
198 | ||
0264ccf6 PT |
199 | while (1) |
200 | { | |
201 | for (fn = fib_get_chain(&tab->fib, (net_addr *) &n); fn; fn = fn->next) | |
202 | { | |
286e2011 | 203 | net_addr_roa6 *roa = (void *) fn->addr; |
0264ccf6 | 204 | net *r = fib_node_to_user(&tab->fib, fn); |
286e2011 OZ |
205 | |
206 | if (net_equal_prefix_roa6(roa, &n) && rte_is_valid(r->routes)) | |
0264ccf6 | 207 | { |
0264ccf6 PT |
208 | anything = 1; |
209 | if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen)) | |
210 | return ROA_VALID; | |
211 | } | |
212 | } | |
213 | ||
214 | if (n.pxlen == 0) | |
215 | break; | |
216 | ||
217 | n.pxlen--; | |
218 | ip6_clrbit(&n.prefix, n.pxlen); | |
219 | } | |
220 | ||
221 | return anything ? ROA_INVALID : ROA_UNKNOWN; | |
222 | } | |
223 | ||
286e2011 OZ |
224 | /** |
225 | * roa_check - check validity of route origination in a ROA table | |
226 | * @tab: ROA table | |
227 | * @n: network prefix to check | |
228 | * @asn: AS number of network prefix | |
229 | * | |
230 | * Implements RFC 6483 route validation for the given network prefix. The | |
231 | * procedure is to find all candidate ROAs - ROAs whose prefixes cover the given | |
232 | * network prefix. If there is no candidate ROA, return ROA_UNKNOWN. If there is | |
233 | * a candidate ROA with matching ASN and maxlen field greater than or equal to | |
234 | * the given prefix length, return ROA_VALID. Otherwise, return ROA_INVALID. If | |
235 | * caller cannot determine origin AS, 0 could be used (in that case ROA_VALID | |
236 | * cannot happen). Table @tab must have type NET_ROA4 or NET_ROA6, network @n | |
237 | * must have type NET_IP4 or NET_IP6, respectively. | |
238 | */ | |
239 | int | |
0264ccf6 PT |
240 | net_roa_check(rtable *tab, const net_addr *n, u32 asn) |
241 | { | |
286e2011 OZ |
242 | if ((tab->addr_type == NET_ROA4) && (n->type == NET_IP4)) |
243 | return net_roa_check_ip4(tab, (const net_addr_ip4 *) n, asn); | |
244 | else if ((tab->addr_type == NET_ROA6) && (n->type == NET_IP6)) | |
245 | return net_roa_check_ip6(tab, (const net_addr_ip6 *) n, asn); | |
0264ccf6 | 246 | else |
286e2011 | 247 | return ROA_UNKNOWN; /* Should not happen */ |
d1e146f2 | 248 | } |
2326b001 | 249 | |
58740ed4 MM |
250 | /** |
251 | * rte_find - find a route | |
252 | * @net: network node | |
094d2bdb | 253 | * @src: route source |
58740ed4 MM |
254 | * |
255 | * The rte_find() function returns a route for destination @net | |
094d2bdb | 256 | * which is from route source @src. |
58740ed4 | 257 | */ |
2326b001 | 258 | rte * |
094d2bdb | 259 | rte_find(net *net, struct rte_src *src) |
2326b001 MM |
260 | { |
261 | rte *e = net->routes; | |
262 | ||
5cff1d5f | 263 | while (e && e->src != src) |
2326b001 MM |
264 | e = e->next; |
265 | return e; | |
266 | } | |
267 | ||
58740ed4 MM |
268 | /** |
269 | * rte_get_temp - get a temporary &rte | |
3ce8c610 | 270 | * @a: attributes to assign to the new route (a &rta; in case it's |
2e9b2421 | 271 | * un-cached, rte_update() will create a cached copy automatically) |
58740ed4 MM |
272 | * |
273 | * Create a temporary &rte and bind it with the attributes @a. | |
274 | * Also set route preference to the default preference set for | |
275 | * the protocol. | |
276 | */ | |
2326b001 | 277 | rte * |
5cff1d5f | 278 | rte_get_temp(rta *a, struct rte_src *src) |
2326b001 MM |
279 | { |
280 | rte *e = sl_alloc(rte_slab); | |
281 | ||
282 | e->attrs = a; | |
5ea39eaa | 283 | e->id = 0; |
0cdbd397 | 284 | e->flags = 0; |
5cff1d5f | 285 | rt_lock_source(e->src = src); |
2326b001 MM |
286 | return e; |
287 | } | |
288 | ||
e2dc2f30 MM |
289 | rte * |
290 | rte_do_cow(rte *r) | |
291 | { | |
292 | rte *e = sl_alloc(rte_slab); | |
293 | ||
294 | memcpy(e, r, sizeof(rte)); | |
5cff1d5f MM |
295 | |
296 | rt_lock_source(e->src); | |
e2dc2f30 MM |
297 | e->attrs = rta_clone(r->attrs); |
298 | e->flags = 0; | |
299 | return e; | |
300 | } | |
301 | ||
8d9eef17 OZ |
302 | /** |
303 | * rte_cow_rta - get a private writable copy of &rte with writable &rta | |
304 | * @r: a route entry to be copied | |
305 | * @lp: a linpool from which to allocate &rta | |
306 | * | |
307 | * rte_cow_rta() takes a &rte and prepares it and associated &rta for | |
308 | * modification. There are three possibilities: First, both &rte and &rta are | |
309 | * private copies, in that case they are returned unchanged. Second, &rte is | |
310 | * private copy, but &rta is cached, in that case &rta is duplicated using | |
311 | * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case | |
312 | * both structures are duplicated by rte_do_cow() and rta_do_cow(). | |
313 | * | |
314 | * Note that in the second case, cached &rta loses one reference, while private | |
315 | * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs, | |
316 | * nexthops, ...) with it. To work properly, original shared &rta should have | |
317 | * another reference during the life of created private copy. | |
318 | * | |
319 | * Result: a pointer to the new writable &rte with writable &rta. | |
320 | */ | |
321 | rte * | |
322 | rte_cow_rta(rte *r, linpool *lp) | |
323 | { | |
324 | if (!rta_is_cached(r->attrs)) | |
325 | return r; | |
326 | ||
13c0be19 | 327 | r = rte_cow(r); |
8d9eef17 | 328 | rta *a = rta_do_cow(r->attrs, lp); |
13c0be19 JMM |
329 | rta_free(r->attrs); |
330 | r->attrs = a; | |
331 | return r; | |
8d9eef17 OZ |
332 | } |
333 | ||
cee0cd14 MM |
334 | /** |
335 | * rte_free - delete a &rte | |
336 | * @e: &rte to be deleted | |
337 | * | |
338 | * rte_free() deletes the given &rte from the routing table it's linked to. | |
339 | */ | |
340 | void | |
341 | rte_free(rte *e) | |
342 | { | |
5cff1d5f | 343 | rt_unlock_source(e->src); |
cee0cd14 MM |
344 | if (rta_is_cached(e->attrs)) |
345 | rta_free(e->attrs); | |
346 | sl_free(rte_slab, e); | |
347 | } | |
348 | ||
349 | static inline void | |
350 | rte_free_quick(rte *e) | |
351 | { | |
5cff1d5f | 352 | rt_unlock_source(e->src); |
cee0cd14 MM |
353 | rta_free(e->attrs); |
354 | sl_free(rte_slab, e); | |
355 | } | |
9aa77fcc | 356 | |
2326b001 MM |
357 | static int /* Actually better or at least as good as */ |
358 | rte_better(rte *new, rte *old) | |
359 | { | |
d9f330c5 MM |
360 | int (*better)(rte *, rte *); |
361 | ||
cf98be7b | 362 | if (!rte_is_valid(old)) |
2326b001 | 363 | return 1; |
cf98be7b OZ |
364 | if (!rte_is_valid(new)) |
365 | return 0; | |
366 | ||
eb937358 | 367 | if (new->attrs->pref > old->attrs->pref) |
2326b001 | 368 | return 1; |
eb937358 | 369 | if (new->attrs->pref < old->attrs->pref) |
2326b001 | 370 | return 0; |
5cff1d5f | 371 | if (new->src->proto->proto != old->src->proto->proto) |
4c1b4e1a MM |
372 | { |
373 | /* | |
374 | * If the user has configured protocol preferences, so that two different protocols | |
375 | * have the same preference, try to break the tie by comparing addresses. Not too | |
376 | * useful, but keeps the ordering of routes unambiguous. | |
377 | */ | |
5cff1d5f | 378 | return new->src->proto->proto > old->src->proto->proto; |
4c1b4e1a | 379 | } |
5cff1d5f | 380 | if (better = new->src->proto->rte_better) |
d9f330c5 MM |
381 | return better(new, old); |
382 | return 0; | |
2326b001 MM |
383 | } |
384 | ||
8d9eef17 OZ |
385 | static int |
386 | rte_mergable(rte *pri, rte *sec) | |
387 | { | |
388 | int (*mergable)(rte *, rte *); | |
389 | ||
390 | if (!rte_is_valid(pri) || !rte_is_valid(sec)) | |
391 | return 0; | |
392 | ||
eb937358 | 393 | if (pri->attrs->pref != sec->attrs->pref) |
8d9eef17 OZ |
394 | return 0; |
395 | ||
5cff1d5f | 396 | if (pri->src->proto->proto != sec->src->proto->proto) |
8d9eef17 OZ |
397 | return 0; |
398 | ||
5cff1d5f | 399 | if (mergable = pri->src->proto->rte_mergable) |
8d9eef17 OZ |
400 | return mergable(pri, sec); |
401 | ||
402 | return 0; | |
403 | } | |
404 | ||
cfd46ee4 | 405 | static void |
61dae32b | 406 | rte_trace(struct channel *c, rte *e, int dir, char *msg) |
cfd46ee4 | 407 | { |
61dae32b OZ |
408 | log(L_TRACE "%s.%s %c %s %N %s", |
409 | c->proto->name, c->name ?: "?", dir, msg, e->net->n.addr, | |
410 | rta_dest_name(e->attrs->dest)); | |
cfd46ee4 MM |
411 | } |
412 | ||
413 | static inline void | |
61dae32b | 414 | rte_trace_in(uint flag, struct channel *c, rte *e, char *msg) |
cfd46ee4 | 415 | { |
61dae32b OZ |
416 | if ((c->debug & flag) || (c->proto->debug & flag)) |
417 | rte_trace(c, e, '>', msg); | |
cfd46ee4 MM |
418 | } |
419 | ||
420 | static inline void | |
61dae32b | 421 | rte_trace_out(uint flag, struct channel *c, rte *e, char *msg) |
cfd46ee4 | 422 | { |
61dae32b OZ |
423 | if ((c->debug & flag) || (c->proto->debug & flag)) |
424 | rte_trace(c, e, '<', msg); | |
cfd46ee4 MM |
425 | } |
426 | ||
00a09f3c | 427 | static rte * |
13c0be19 | 428 | export_filter_(struct channel *c, rte *rt0, rte **rt_free, linpool *pool, int silent) |
529c4149 | 429 | { |
f4a60a9b | 430 | struct proto *p = c->proto; |
0b39b1cb | 431 | const struct filter *filter = c->out_filter; |
f4a60a9b | 432 | struct proto_stats *stats = &c->stats; |
00a09f3c OZ |
433 | rte *rt; |
434 | int v; | |
c0adf7e9 | 435 | |
00a09f3c OZ |
436 | rt = rt0; |
437 | *rt_free = NULL; | |
7de45ba4 | 438 | |
d5a32563 | 439 | v = p->preexport ? p->preexport(p, rt) : 0; |
00a09f3c OZ |
440 | if (v < 0) |
441 | { | |
442 | if (silent) | |
443 | goto reject; | |
11361a10 | 444 | |
00a09f3c | 445 | stats->exp_updates_rejected++; |
36da2857 | 446 | if (v == RIC_REJECT) |
61dae32b | 447 | rte_trace_out(D_FILTERS, c, rt, "rejected by protocol"); |
00a09f3c OZ |
448 | goto reject; |
449 | } | |
450 | if (v > 0) | |
e2dc2f30 | 451 | { |
00a09f3c | 452 | if (!silent) |
61dae32b | 453 | rte_trace_out(D_FILTERS, c, rt, "forced accept by protocol"); |
00a09f3c | 454 | goto accept; |
e2dc2f30 | 455 | } |
925fe2d3 | 456 | |
00a09f3c | 457 | v = filter && ((filter == FILTER_REJECT) || |
13c0be19 JMM |
458 | (f_run(filter, &rt, pool, |
459 | (silent ? FF_SILENT : 0)) > F_ACCEPT)); | |
00a09f3c OZ |
460 | if (v) |
461 | { | |
462 | if (silent) | |
463 | goto reject; | |
464 | ||
465 | stats->exp_updates_filtered++; | |
61dae32b | 466 | rte_trace_out(D_FILTERS, c, rt, "filtered out"); |
00a09f3c | 467 | goto reject; |
e2dc2f30 | 468 | } |
925fe2d3 | 469 | |
00a09f3c OZ |
470 | accept: |
471 | if (rt != rt0) | |
472 | *rt_free = rt; | |
473 | return rt; | |
474 | ||
475 | reject: | |
476 | /* Discard temporary rte */ | |
477 | if (rt != rt0) | |
478 | rte_free(rt); | |
479 | return NULL; | |
480 | } | |
481 | ||
a290da25 | 482 | static inline rte * |
13c0be19 | 483 | export_filter(struct channel *c, rte *rt0, rte **rt_free, int silent) |
a290da25 | 484 | { |
13c0be19 | 485 | return export_filter_(c, rt0, rt_free, rte_update_pool, silent); |
a290da25 PT |
486 | } |
487 | ||
00a09f3c | 488 | static void |
13c0be19 | 489 | do_rt_notify(struct channel *c, net *net, rte *new, rte *old, int refeed) |
00a09f3c | 490 | { |
f4a60a9b OZ |
491 | struct proto *p = c->proto; |
492 | struct proto_stats *stats = &c->stats; | |
925fe2d3 | 493 | |
5ea39eaa OZ |
494 | if (refeed && new) |
495 | c->refeed_count++; | |
925fe2d3 | 496 | |
5ea39eaa | 497 | /* Apply export limit */ |
f4a60a9b | 498 | struct channel_limit *l = &c->out_limit; |
5ea39eaa OZ |
499 | if (l->action && !old && new) |
500 | { | |
501 | if (stats->exp_routes >= l->limit) | |
502 | channel_notify_limit(c, l, PLD_OUT, stats->exp_routes); | |
abced4a9 | 503 | |
5ea39eaa OZ |
504 | if (l->state == PLS_BLOCKED) |
505 | { | |
506 | stats->exp_updates_rejected++; | |
61dae32b | 507 | rte_trace_out(D_FILTERS, c, new, "rejected [limit]"); |
5ea39eaa | 508 | return; |
d9b77cc2 | 509 | } |
5ea39eaa | 510 | } |
d9b77cc2 | 511 | |
5ea39eaa | 512 | /* Apply export table */ |
cee0cd14 MM |
513 | struct rte *old_exported = NULL; |
514 | if (c->out_table) | |
515 | { | |
516 | if (!rte_update_out(c, net->n.addr, new, old, &old_exported, refeed)) | |
517 | return; | |
518 | } | |
519 | else if (c->out_filter == FILTER_ACCEPT) | |
520 | old_exported = old; | |
ab758e4f | 521 | |
925fe2d3 | 522 | if (new) |
9db74169 | 523 | stats->exp_updates_accepted++; |
925fe2d3 | 524 | else |
9db74169 | 525 | stats->exp_withdraws_accepted++; |
925fe2d3 | 526 | |
5ea39eaa OZ |
527 | if (old) |
528 | { | |
529 | bmap_clear(&c->export_map, old->id); | |
530 | stats->exp_routes--; | |
531 | } | |
532 | ||
925fe2d3 | 533 | if (new) |
5ea39eaa OZ |
534 | { |
535 | bmap_set(&c->export_map, new->id); | |
9db74169 | 536 | stats->exp_routes++; |
5ea39eaa | 537 | } |
925fe2d3 | 538 | |
cfd46ee4 | 539 | if (p->debug & D_ROUTES) |
5ea39eaa OZ |
540 | { |
541 | if (new && old) | |
61dae32b | 542 | rte_trace_out(D_ROUTES, c, new, "replaced"); |
5ea39eaa | 543 | else if (new) |
61dae32b | 544 | rte_trace_out(D_ROUTES, c, new, "added"); |
5ea39eaa | 545 | else if (old) |
61dae32b | 546 | rte_trace_out(D_ROUTES, c, old, "removed"); |
5ea39eaa OZ |
547 | } |
548 | ||
13c0be19 | 549 | p->rt_notify(p, c, net, new, old); |
cee0cd14 MM |
550 | |
551 | if (c->out_table && old_exported) | |
552 | rte_free_quick(old_exported); | |
00a09f3c OZ |
553 | } |
554 | ||
00a09f3c | 555 | static void |
5ea39eaa | 556 | rt_notify_basic(struct channel *c, net *net, rte *new, rte *old, int refeed) |
00a09f3c | 557 | { |
5ea39eaa | 558 | // struct proto *p = c->proto; |
00a09f3c | 559 | rte *new_free = NULL; |
00a09f3c OZ |
560 | |
561 | if (new) | |
f4a60a9b | 562 | c->stats.exp_updates_received++; |
00a09f3c | 563 | else |
f4a60a9b | 564 | c->stats.exp_withdraws_received++; |
00a09f3c | 565 | |
00a09f3c | 566 | if (new) |
13c0be19 | 567 | new = export_filter(c, new, &new_free, 0); |
00a09f3c | 568 | |
5ea39eaa OZ |
569 | if (old && !bmap_test(&c->export_map, old->id)) |
570 | old = NULL; | |
00a09f3c | 571 | |
00a09f3c OZ |
572 | if (!new && !old) |
573 | return; | |
574 | ||
13c0be19 | 575 | do_rt_notify(c, net, new, old, refeed); |
00a09f3c | 576 | |
5ea39eaa | 577 | /* Discard temporary rte */ |
00a09f3c OZ |
578 | if (new_free) |
579 | rte_free(new_free); | |
00a09f3c OZ |
580 | } |
581 | ||
582 | static void | |
5ea39eaa | 583 | rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_changed, int refeed) |
00a09f3c | 584 | { |
5ea39eaa | 585 | // struct proto *p = c->proto; |
00a09f3c OZ |
586 | rte *new_best = NULL; |
587 | rte *old_best = NULL; | |
588 | rte *new_free = NULL; | |
5ea39eaa | 589 | int new_first = 0; |
00a09f3c | 590 | |
5ea39eaa OZ |
591 | /* |
592 | * We assume that there are no changes in net route order except (added) | |
593 | * new_changed and (removed) old_changed. Therefore, the function is not | |
594 | * compatible with deterministic_med (where nontrivial reordering can happen | |
595 | * as a result of a route change) and with recomputation of recursive routes | |
596 | * due to next hop update (where many routes can be changed in one step). | |
597 | * | |
598 | * Note that we need this assumption just for optimizations, we could just | |
599 | * run full new_best recomputation otherwise. | |
600 | * | |
601 | * There are three cases: | |
602 | * feed or old_best is old_changed -> we need to recompute new_best | |
603 | * old_best is before new_changed -> new_best is old_best, ignore | |
604 | * old_best is after new_changed -> try new_changed, otherwise old_best | |
605 | */ | |
00a09f3c | 606 | |
5ea39eaa | 607 | if (net->routes) |
f4a60a9b | 608 | c->stats.exp_updates_received++; |
00a09f3c | 609 | else |
f4a60a9b | 610 | c->stats.exp_withdraws_received++; |
00a09f3c | 611 | |
5ea39eaa OZ |
612 | /* Find old_best - either old_changed, or route for net->routes */ |
613 | if (old_changed && bmap_test(&c->export_map, old_changed->id)) | |
614 | old_best = old_changed; | |
615 | else | |
616 | { | |
617 | for (rte *r = net->routes; rte_is_valid(r); r = r->next) | |
00a09f3c | 618 | { |
5ea39eaa OZ |
619 | if (bmap_test(&c->export_map, r->id)) |
620 | { | |
621 | old_best = r; | |
00a09f3c | 622 | break; |
5ea39eaa | 623 | } |
00a09f3c | 624 | |
5ea39eaa OZ |
625 | /* Note if new_changed found before old_best */ |
626 | if (r == new_changed) | |
627 | new_first = 1; | |
092c4930 | 628 | } |
5ea39eaa | 629 | } |
092c4930 | 630 | |
5ea39eaa OZ |
631 | /* Find new_best */ |
632 | if ((new_changed == old_changed) || (old_best == old_changed)) | |
633 | { | |
634 | /* Feed or old_best changed -> find first accepted by filters */ | |
635 | for (rte *r = net->routes; rte_is_valid(r); r = r->next) | |
636 | if (new_best = export_filter(c, r, &new_free, 0)) | |
637 | break; | |
638 | } | |
639 | else | |
640 | { | |
641 | /* Other cases -> either new_changed, or old_best (and nothing changed) */ | |
642 | if (new_first && (new_changed = export_filter(c, new_changed, &new_free, 0))) | |
643 | new_best = new_changed; | |
644 | else | |
00a09f3c | 645 | return; |
5ea39eaa | 646 | } |
00a09f3c | 647 | |
5ea39eaa OZ |
648 | if (!new_best && !old_best) |
649 | return; | |
00a09f3c | 650 | |
5ea39eaa | 651 | do_rt_notify(c, net, new_best, old_best, refeed); |
00a09f3c | 652 | |
5ea39eaa | 653 | /* Discard temporary rte */ |
00a09f3c OZ |
654 | if (new_free) |
655 | rte_free(new_free); | |
529c4149 MM |
656 | } |
657 | ||
8d9eef17 | 658 | |
4e276a89 JMM |
659 | static struct nexthop * |
660 | nexthop_merge_rta(struct nexthop *nhs, rta *a, linpool *pool, int max) | |
8d9eef17 | 661 | { |
4e276a89 | 662 | return nexthop_merge(nhs, &(a->nh), 1, 0, max, pool); |
8d9eef17 OZ |
663 | } |
664 | ||
665 | rte * | |
13c0be19 | 666 | rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int silent) |
8d9eef17 | 667 | { |
f4a60a9b | 668 | // struct proto *p = c->proto; |
4e276a89 | 669 | struct nexthop *nhs = NULL; |
8d9eef17 OZ |
670 | rte *best0, *best, *rt0, *rt, *tmp; |
671 | ||
672 | best0 = net->routes; | |
673 | *rt_free = NULL; | |
674 | ||
675 | if (!rte_is_valid(best0)) | |
676 | return NULL; | |
677 | ||
13c0be19 | 678 | best = export_filter_(c, best0, rt_free, pool, silent); |
8d9eef17 OZ |
679 | |
680 | if (!best || !rte_is_reachable(best)) | |
681 | return best; | |
682 | ||
683 | for (rt0 = best0->next; rt0; rt0 = rt0->next) | |
684 | { | |
685 | if (!rte_mergable(best0, rt0)) | |
686 | continue; | |
687 | ||
13c0be19 | 688 | rt = export_filter_(c, rt0, &tmp, pool, 1); |
8d9eef17 OZ |
689 | |
690 | if (!rt) | |
691 | continue; | |
692 | ||
693 | if (rte_is_reachable(rt)) | |
4e276a89 | 694 | nhs = nexthop_merge_rta(nhs, rt->attrs, pool, c->merge_limit); |
8d9eef17 OZ |
695 | |
696 | if (tmp) | |
697 | rte_free(tmp); | |
698 | } | |
699 | ||
700 | if (nhs) | |
701 | { | |
4e276a89 | 702 | nhs = nexthop_merge_rta(nhs, best->attrs, pool, c->merge_limit); |
8d9eef17 OZ |
703 | |
704 | if (nhs->next) | |
705 | { | |
a290da25 | 706 | best = rte_cow_rta(best, pool); |
4e276a89 | 707 | nexthop_link(best->attrs, nhs); |
8d9eef17 OZ |
708 | } |
709 | } | |
710 | ||
711 | if (best != best0) | |
712 | *rt_free = best; | |
713 | ||
714 | return best; | |
715 | } | |
716 | ||
717 | ||
718 | static void | |
f4a60a9b | 719 | rt_notify_merged(struct channel *c, net *net, rte *new_changed, rte *old_changed, |
5ea39eaa | 720 | rte *new_best, rte *old_best, int refeed) |
8d9eef17 | 721 | { |
f4a60a9b | 722 | // struct proto *p = c->proto; |
5ea39eaa | 723 | rte *new_free = NULL; |
8d9eef17 OZ |
724 | |
725 | /* We assume that all rte arguments are either NULL or rte_is_valid() */ | |
726 | ||
727 | /* This check should be done by the caller */ | |
728 | if (!new_best && !old_best) | |
729 | return; | |
730 | ||
731 | /* Check whether the change is relevant to the merged route */ | |
5ea39eaa OZ |
732 | if ((new_best == old_best) && |
733 | (new_changed != old_changed) && | |
734 | !rte_mergable(new_best, new_changed) && | |
735 | !rte_mergable(old_best, old_changed)) | |
736 | return; | |
8d9eef17 OZ |
737 | |
738 | if (new_best) | |
f4a60a9b | 739 | c->stats.exp_updates_received++; |
8d9eef17 | 740 | else |
f4a60a9b | 741 | c->stats.exp_withdraws_received++; |
8d9eef17 OZ |
742 | |
743 | /* Prepare new merged route */ | |
744 | if (new_best) | |
5ea39eaa OZ |
745 | new_best = rt_export_merged(c, net, &new_free, rte_update_pool, 0); |
746 | ||
747 | /* Check old merged route */ | |
748 | if (old_best && !bmap_test(&c->export_map, old_best->id)) | |
749 | old_best = NULL; | |
8d9eef17 | 750 | |
5ea39eaa OZ |
751 | if (!new_best && !old_best) |
752 | return; | |
8d9eef17 | 753 | |
5ea39eaa | 754 | do_rt_notify(c, net, new_best, old_best, refeed); |
8d9eef17 | 755 | |
5ea39eaa OZ |
756 | /* Discard temporary rte */ |
757 | if (new_free) | |
758 | rte_free(new_free); | |
8d9eef17 OZ |
759 | } |
760 | ||
761 | ||
9a8f20fc MM |
762 | /** |
763 | * rte_announce - announce a routing table change | |
764 | * @tab: table the route has been added to | |
5ea39eaa | 765 | * @type: type of route announcement (RA_UNDEF or RA_ANY) |
9a8f20fc | 766 | * @net: network in question |
5ea39eaa OZ |
767 | * @new: the new or changed route |
768 | * @old: the previous route replaced by the new one | |
8e433d6a PT |
769 | * @new_best: the new best route for the same network |
770 | * @old_best: the previous best route for the same network | |
9a8f20fc | 771 | * |
5ea39eaa OZ |
772 | * This function gets a routing table update and announces it to all protocols |
773 | * that are connected to the same table by their channels. | |
9a8f20fc | 774 | * |
5ea39eaa OZ |
775 | * There are two ways of how routing table changes are announced. First, there |
776 | * is a change of just one route in @net (which may caused a change of the best | |
777 | * route of the network). In this case @new and @old describes the changed route | |
778 | * and @new_best and @old_best describes best routes. Other routes are not | |
779 | * affected, but in sorted table the order of other routes might change. | |
23ac9e9a | 780 | * |
5ea39eaa OZ |
781 | * Second, There is a bulk change of multiple routes in @net, with shared best |
782 | * route selection. In such case separate route changes are described using | |
783 | * @type of %RA_ANY, with @new and @old specifying the changed route, while | |
784 | * @new_best and @old_best are NULL. After that, another notification is done | |
785 | * where @new_best and @old_best are filled (may be the same), but @new and @old | |
786 | * are NULL. | |
f98e2915 | 787 | * |
5ea39eaa OZ |
788 | * The function announces the change to all associated channels. For each |
789 | * channel, an appropriate preprocessing is done according to channel &ra_mode. | |
790 | * For example, %RA_OPTIMAL channels receive just changes of best routes. | |
791 | * | |
792 | * In general, we first call preexport() hook of a protocol, which performs | |
793 | * basic checks on the route (each protocol has a right to veto or force accept | |
794 | * of the route before any filter is asked). Then we consult an export filter | |
795 | * of the channel and verify the old route in an export map of the channel. | |
796 | * Finally, the rt_notify() hook of the protocol gets called. | |
797 | * | |
798 | * Note that there are also calls of rt_notify() hooks due to feed, but that is | |
799 | * done outside of scope of rte_announce(). | |
9a8f20fc | 800 | */ |
e2dc2f30 | 801 | static void |
5ea39eaa OZ |
802 | rte_announce(rtable *tab, uint type, net *net, rte *new, rte *old, |
803 | rte *new_best, rte *old_best) | |
2326b001 | 804 | { |
8d9eef17 OZ |
805 | if (!rte_is_valid(new)) |
806 | new = NULL; | |
807 | ||
cf98be7b | 808 | if (!rte_is_valid(old)) |
5ea39eaa | 809 | old = NULL; |
cf98be7b | 810 | |
8d9eef17 OZ |
811 | if (!rte_is_valid(new_best)) |
812 | new_best = NULL; | |
813 | ||
814 | if (!rte_is_valid(old_best)) | |
815 | old_best = NULL; | |
cf98be7b | 816 | |
5ea39eaa | 817 | if (!new && !old && !new_best && !old_best) |
cf98be7b | 818 | return; |
2326b001 | 819 | |
5ea39eaa | 820 | if (new_best != old_best) |
e1c275d8 | 821 | { |
5ea39eaa OZ |
822 | if (new_best) |
823 | new_best->sender->stats.pref_routes++; | |
824 | if (old_best) | |
825 | old_best->sender->stats.pref_routes--; | |
e1c275d8 OZ |
826 | |
827 | if (tab->hostcache) | |
828 | rt_notify_hostcache(tab, net); | |
829 | } | |
cfe34a31 | 830 | |
00b85905 OZ |
831 | rt_schedule_notify(tab); |
832 | ||
f4a60a9b OZ |
833 | struct channel *c; node *n; |
834 | WALK_LIST2(c, n, tab->channels, table_node) | |
5ea39eaa OZ |
835 | { |
836 | if (c->export_state == ES_DOWN) | |
837 | continue; | |
838 | ||
839 | if (type && (type != c->ra_mode)) | |
840 | continue; | |
841 | ||
842 | switch (c->ra_mode) | |
0a2e9d9f | 843 | { |
5ea39eaa OZ |
844 | case RA_OPTIMAL: |
845 | if (new_best != old_best) | |
846 | rt_notify_basic(c, net, new_best, old_best, 0); | |
847 | break; | |
848 | ||
849 | case RA_ANY: | |
850 | if (new != old) | |
851 | rt_notify_basic(c, net, new, old, 0); | |
852 | break; | |
f4a60a9b | 853 | |
5ea39eaa OZ |
854 | case RA_ACCEPTED: |
855 | rt_notify_accepted(c, net, new, old, 0); | |
856 | break; | |
857 | ||
858 | case RA_MERGED: | |
859 | rt_notify_merged(c, net, new, old, new_best, old_best, 0); | |
860 | break; | |
0a2e9d9f | 861 | } |
5ea39eaa | 862 | } |
2326b001 MM |
863 | } |
864 | ||
421838ff MM |
865 | static inline int |
866 | rte_validate(rte *e) | |
867 | { | |
868 | int c; | |
869 | net *n = e->net; | |
870 | ||
fe9f1a6d OZ |
871 | if (!net_validate(n->n.addr)) |
872 | { | |
873 | log(L_WARN "Ignoring bogus prefix %N received via %s", | |
874 | n->n.addr, e->sender->proto->name); | |
875 | return 0; | |
876 | } | |
ff2857b0 | 877 | |
7fc55925 OZ |
878 | /* FIXME: better handling different nettypes */ |
879 | c = !net_is_flow(n->n.addr) ? | |
880 | net_classify(n->n.addr): (IADDR_HOST | SCOPE_UNIVERSE); | |
ff2857b0 | 881 | if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK)) |
fe9f1a6d OZ |
882 | { |
883 | log(L_WARN "Ignoring bogus route %N received via %s", | |
884 | n->n.addr, e->sender->proto->name); | |
885 | return 0; | |
886 | } | |
ff2857b0 | 887 | |
4278abfe OZ |
888 | if (net_type_match(n->n.addr, NB_DEST) == !e->attrs->dest) |
889 | { | |
890 | log(L_WARN "Ignoring route %N with invalid dest %d received via %s", | |
891 | n->n.addr, e->attrs->dest, e->sender->proto->name); | |
892 | return 0; | |
893 | } | |
894 | ||
4e276a89 | 895 | if ((e->attrs->dest == RTD_UNICAST) && !nexthop_is_sorted(&(e->attrs->nh))) |
4278abfe OZ |
896 | { |
897 | log(L_WARN "Ignoring unsorted multipath route %N received via %s", | |
898 | n->n.addr, e->sender->proto->name); | |
899 | return 0; | |
900 | } | |
84cac51a | 901 | |
421838ff MM |
902 | return 1; |
903 | } | |
904 | ||
67be5b23 MM |
905 | static int |
906 | rte_same(rte *x, rte *y) | |
907 | { | |
93af78d2 | 908 | /* rte.flags are not checked, as they are mostly internal to rtable */ |
67be5b23 MM |
909 | return |
910 | x->attrs == y->attrs && | |
67be5b23 | 911 | x->pflags == y->pflags && |
5cff1d5f | 912 | x->src == y->src && |
93af78d2 | 913 | rte_is_filtered(x) == rte_is_filtered(y); |
67be5b23 MM |
914 | } |
915 | ||
70577529 OZ |
916 | static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); } |
917 | ||
e2dc2f30 | 918 | static void |
f4a60a9b | 919 | rte_recalculate(struct channel *c, net *net, rte *new, struct rte_src *src) |
2326b001 | 920 | { |
f4a60a9b OZ |
921 | struct proto *p = c->proto; |
922 | struct rtable *table = c->table; | |
923 | struct proto_stats *stats = &c->stats; | |
1123e707 | 924 | static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS; |
00a09f3c | 925 | rte *before_old = NULL; |
2326b001 MM |
926 | rte *old_best = net->routes; |
927 | rte *old = NULL; | |
00a09f3c | 928 | rte **k; |
2326b001 MM |
929 | |
930 | k = &net->routes; /* Find and remove original route from the same protocol */ | |
931 | while (old = *k) | |
932 | { | |
5cff1d5f | 933 | if (old->src == src) |
2326b001 | 934 | { |
11787b84 OZ |
935 | /* If there is the same route in the routing table but from |
936 | * a different sender, then there are two paths from the | |
937 | * source protocol to this routing table through transparent | |
938 | * pipes, which is not allowed. | |
939 | * | |
940 | * We log that and ignore the route. If it is withdraw, we | |
941 | * ignore it completely (there might be 'spurious withdraws', | |
942 | * see FIXME in do_rte_announce()) | |
943 | */ | |
c0adf7e9 | 944 | if (old->sender->proto != p) |
11787b84 OZ |
945 | { |
946 | if (new) | |
947 | { | |
fe9f1a6d OZ |
948 | log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %N to table %s", |
949 | net->n.addr, table->name); | |
11787b84 OZ |
950 | rte_free_quick(new); |
951 | } | |
952 | return; | |
953 | } | |
954 | ||
0b761098 | 955 | if (new && rte_same(old, new)) |
67be5b23 | 956 | { |
93af78d2 OZ |
957 | /* No changes, ignore the new route and refresh the old one */ |
958 | ||
959 | old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY); | |
cf98be7b | 960 | |
15550957 | 961 | if (!rte_is_filtered(new)) |
cf98be7b OZ |
962 | { |
963 | stats->imp_updates_ignored++; | |
61dae32b | 964 | rte_trace_in(D_ROUTES, c, new, "ignored"); |
cf98be7b OZ |
965 | } |
966 | ||
67be5b23 | 967 | rte_free_quick(new); |
67be5b23 MM |
968 | return; |
969 | } | |
2326b001 | 970 | *k = old->next; |
67d8665a | 971 | table->rt_count--; |
2326b001 MM |
972 | break; |
973 | } | |
974 | k = &old->next; | |
00a09f3c | 975 | before_old = old; |
2326b001 MM |
976 | } |
977 | ||
c0e1f534 OZ |
978 | /* Save the last accessed position */ |
979 | rte **pos = k; | |
980 | ||
00a09f3c OZ |
981 | if (!old) |
982 | before_old = NULL; | |
983 | ||
925fe2d3 OZ |
984 | if (!old && !new) |
985 | { | |
9db74169 | 986 | stats->imp_withdraws_ignored++; |
925fe2d3 OZ |
987 | return; |
988 | } | |
989 | ||
b662290f OZ |
990 | int new_ok = rte_is_ok(new); |
991 | int old_ok = rte_is_ok(old); | |
992 | ||
f4a60a9b | 993 | struct channel_limit *l = &c->rx_limit; |
67d8665a | 994 | if (l->action && !old && new && !c->in_table) |
ebecb6f6 | 995 | { |
15550957 | 996 | u32 all_routes = stats->imp_routes + stats->filt_routes; |
cf98be7b OZ |
997 | |
998 | if (all_routes >= l->limit) | |
f4a60a9b | 999 | channel_notify_limit(c, l, PLD_RX, all_routes); |
7d0a31de OZ |
1000 | |
1001 | if (l->state == PLS_BLOCKED) | |
1002 | { | |
b662290f OZ |
1003 | /* In receive limit the situation is simple, old is NULL so |
1004 | we just free new and exit like nothing happened */ | |
1005 | ||
7d0a31de | 1006 | stats->imp_updates_ignored++; |
61dae32b | 1007 | rte_trace_in(D_FILTERS, c, new, "ignored [limit]"); |
7d0a31de OZ |
1008 | rte_free_quick(new); |
1009 | return; | |
1010 | } | |
ebecb6f6 OZ |
1011 | } |
1012 | ||
f4a60a9b OZ |
1013 | l = &c->in_limit; |
1014 | if (l->action && !old_ok && new_ok) | |
b662290f OZ |
1015 | { |
1016 | if (stats->imp_routes >= l->limit) | |
f4a60a9b | 1017 | channel_notify_limit(c, l, PLD_IN, stats->imp_routes); |
b662290f OZ |
1018 | |
1019 | if (l->state == PLS_BLOCKED) | |
1020 | { | |
1021 | /* In import limit the situation is more complicated. We | |
1022 | shouldn't just drop the route, we should handle it like | |
1023 | it was filtered. We also have to continue the route | |
1024 | processing if old or new is non-NULL, but we should exit | |
1025 | if both are NULL as this case is probably assumed to be | |
1026 | already handled. */ | |
1027 | ||
1028 | stats->imp_updates_ignored++; | |
61dae32b | 1029 | rte_trace_in(D_FILTERS, c, new, "ignored [limit]"); |
b662290f | 1030 | |
f4a60a9b | 1031 | if (c->in_keep_filtered) |
b662290f OZ |
1032 | new->flags |= REF_FILTERED; |
1033 | else | |
1034 | { rte_free_quick(new); new = NULL; } | |
1035 | ||
1036 | /* Note that old && !new could be possible when | |
f4a60a9b | 1037 | c->in_keep_filtered changed in the recent past. */ |
b662290f OZ |
1038 | |
1039 | if (!old && !new) | |
1040 | return; | |
1041 | ||
1042 | new_ok = 0; | |
1043 | goto skip_stats1; | |
1044 | } | |
1045 | } | |
70577529 OZ |
1046 | |
1047 | if (new_ok) | |
9db74169 | 1048 | stats->imp_updates_accepted++; |
70577529 | 1049 | else if (old_ok) |
9db74169 | 1050 | stats->imp_withdraws_accepted++; |
70577529 OZ |
1051 | else |
1052 | stats->imp_withdraws_ignored++; | |
925fe2d3 | 1053 | |
00b85905 OZ |
1054 | if (old_ok || new_ok) |
1055 | table->last_rt_change = current_time(); | |
1056 | ||
b662290f | 1057 | skip_stats1: |
925fe2d3 OZ |
1058 | |
1059 | if (new) | |
15550957 | 1060 | rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++; |
925fe2d3 | 1061 | if (old) |
15550957 | 1062 | rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--; |
925fe2d3 | 1063 | |
26822d8f | 1064 | if (table->config->sorted) |
2326b001 | 1065 | { |
26822d8f OZ |
1066 | /* If routes are sorted, just insert new route to appropriate position */ |
1067 | if (new) | |
1068 | { | |
1069 | if (before_old && !rte_better(new, before_old)) | |
1070 | k = &before_old->next; | |
1071 | else | |
1072 | k = &net->routes; | |
c0973621 | 1073 | |
26822d8f OZ |
1074 | for (; *k; k=&(*k)->next) |
1075 | if (rte_better(new, *k)) | |
1076 | break; | |
c0973621 | 1077 | |
26822d8f OZ |
1078 | new->next = *k; |
1079 | *k = new; | |
c0e1f534 | 1080 | |
67d8665a | 1081 | table->rt_count++; |
26822d8f | 1082 | } |
2326b001 | 1083 | } |
26822d8f | 1084 | else |
2326b001 | 1085 | { |
26822d8f OZ |
1086 | /* If routes are not sorted, find the best route and move it on |
1087 | the first position. There are several optimized cases. */ | |
1088 | ||
094d2bdb | 1089 | if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best)) |
26822d8f OZ |
1090 | goto do_recalculate; |
1091 | ||
1092 | if (new && rte_better(new, old_best)) | |
2326b001 | 1093 | { |
26822d8f OZ |
1094 | /* The first case - the new route is cleary optimal, |
1095 | we link it at the first position */ | |
1096 | ||
c0973621 OZ |
1097 | new->next = net->routes; |
1098 | net->routes = new; | |
c0e1f534 | 1099 | |
67d8665a | 1100 | table->rt_count++; |
c0973621 | 1101 | } |
26822d8f | 1102 | else if (old == old_best) |
c0973621 | 1103 | { |
26822d8f OZ |
1104 | /* The second case - the old best route disappeared, we add the |
1105 | new route (if we have any) to the list (we don't care about | |
1106 | position) and then we elect the new optimal route and relink | |
1107 | that route at the first position and announce it. New optimal | |
1108 | route might be NULL if there is no more routes */ | |
1109 | ||
1110 | do_recalculate: | |
1111 | /* Add the new route to the list */ | |
1112 | if (new) | |
2326b001 | 1113 | { |
c0e1f534 OZ |
1114 | new->next = *pos; |
1115 | *pos = new; | |
1116 | ||
67d8665a | 1117 | table->rt_count++; |
26822d8f OZ |
1118 | } |
1119 | ||
1120 | /* Find a new optimal route (if there is any) */ | |
1121 | if (net->routes) | |
1122 | { | |
1123 | rte **bp = &net->routes; | |
1124 | for (k=&(*bp)->next; *k; k=&(*k)->next) | |
1125 | if (rte_better(*k, *bp)) | |
1126 | bp = k; | |
1127 | ||
1128 | /* And relink it */ | |
1129 | rte *best = *bp; | |
1130 | *bp = best->next; | |
1131 | best->next = net->routes; | |
1132 | net->routes = best; | |
2326b001 | 1133 | } |
2326b001 | 1134 | } |
26822d8f OZ |
1135 | else if (new) |
1136 | { | |
1137 | /* The third case - the new route is not better than the old | |
1138 | best route (therefore old_best != NULL) and the old best | |
1139 | route was not removed (therefore old_best == net->routes). | |
c0e1f534 OZ |
1140 | We just link the new route to the old/last position. */ |
1141 | ||
1142 | new->next = *pos; | |
1143 | *pos = new; | |
26822d8f | 1144 | |
67d8665a | 1145 | table->rt_count++; |
26822d8f OZ |
1146 | } |
1147 | /* The fourth (empty) case - suboptimal route was removed, nothing to do */ | |
2326b001 | 1148 | } |
c0973621 | 1149 | |
26822d8f | 1150 | if (new) |
5ea39eaa OZ |
1151 | { |
1152 | new->lastmod = current_time(); | |
1153 | ||
1154 | if (!old) | |
1155 | { | |
1156 | new->id = hmap_first_zero(&table->id_map); | |
1157 | hmap_set(&table->id_map, new->id); | |
1158 | } | |
1159 | else | |
1160 | new->id = old->id; | |
1161 | } | |
26822d8f OZ |
1162 | |
1163 | /* Log the route change */ | |
61dae32b | 1164 | if ((c->debug & D_ROUTES) || (p->debug & D_ROUTES)) |
e8b29bdc | 1165 | { |
70577529 | 1166 | if (new_ok) |
61dae32b | 1167 | rte_trace(c, new, '>', new == net->routes ? "added [best]" : "added"); |
70577529 OZ |
1168 | else if (old_ok) |
1169 | { | |
1170 | if (old != old_best) | |
61dae32b | 1171 | rte_trace(c, old, '>', "removed"); |
70577529 | 1172 | else if (rte_is_ok(net->routes)) |
61dae32b | 1173 | rte_trace(c, old, '>', "removed [replaced]"); |
70577529 | 1174 | else |
61dae32b | 1175 | rte_trace(c, old, '>', "removed [sole]"); |
70577529 | 1176 | } |
c0973621 OZ |
1177 | } |
1178 | ||
26822d8f | 1179 | /* Propagate the route change */ |
5ea39eaa | 1180 | rte_announce(table, RA_UNDEF, net, new, old, net->routes, old_best); |
00a09f3c OZ |
1181 | |
1182 | if (!net->routes && | |
1183 | (table->gc_counter++ >= table->config->gc_max_ops) && | |
f047271c | 1184 | (table->gc_time + table->config->gc_min_time <= current_time())) |
f4a60a9b | 1185 | rt_schedule_prune(table); |
00a09f3c | 1186 | |
70577529 OZ |
1187 | if (old_ok && p->rte_remove) |
1188 | p->rte_remove(net, old); | |
1189 | if (new_ok && p->rte_insert) | |
1190 | p->rte_insert(net, new); | |
1191 | ||
2326b001 | 1192 | if (old) |
5ea39eaa OZ |
1193 | { |
1194 | if (!new) | |
1195 | hmap_clear(&table->id_map, old->id); | |
1196 | ||
1197 | rte_free_quick(old); | |
1198 | } | |
5b22683d MM |
1199 | } |
1200 | ||
e2dc2f30 MM |
1201 | static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */ |
1202 | ||
1203 | static inline void | |
1204 | rte_update_lock(void) | |
1205 | { | |
1206 | rte_update_nest_cnt++; | |
1207 | } | |
1208 | ||
1209 | static inline void | |
1210 | rte_update_unlock(void) | |
1211 | { | |
1212 | if (!--rte_update_nest_cnt) | |
1213 | lp_flush(rte_update_pool); | |
1214 | } | |
1215 | ||
58740ed4 MM |
1216 | /** |
1217 | * rte_update - enter a new update to a routing table | |
1218 | * @table: table to be updated | |
f4a60a9b | 1219 | * @c: channel doing the update |
58740ed4 MM |
1220 | * @net: network node |
1221 | * @p: protocol submitting the update | |
f98e2915 | 1222 | * @src: protocol originating the update |
58740ed4 MM |
1223 | * @new: a &rte representing the new route or %NULL for route removal. |
1224 | * | |
1225 | * This function is called by the routing protocols whenever they discover | |
1226 | * a new route or wish to update/remove an existing route. The right announcement | |
2e9b2421 | 1227 | * sequence is to build route attributes first (either un-cached with @aflags set |
58740ed4 MM |
1228 | * to zero or a cached one using rta_lookup(); in this case please note that |
1229 | * you need to increase the use count of the attributes yourself by calling | |
1230 | * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all | |
1231 | * the appropriate data and finally submit the new &rte by calling rte_update(). | |
1232 | * | |
f98e2915 OZ |
1233 | * @src specifies the protocol that originally created the route and the meaning |
1234 | * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the | |
1235 | * same value as @new->attrs->proto. @p specifies the protocol that called | |
1236 | * rte_update(). In most cases it is the same protocol as @src. rte_update() | |
1237 | * stores @p in @new->sender; | |
1238 | * | |
9a8f20fc MM |
1239 | * When rte_update() gets any route, it automatically validates it (checks, |
1240 | * whether the network and next hop address are valid IP addresses and also | |
1241 | * whether a normal routing protocol doesn't try to smuggle a host or link | |
1242 | * scope route to the table), converts all protocol dependent attributes stored | |
1243 | * in the &rte to temporary extended attributes, consults import filters of the | |
1244 | * protocol to see if the route should be accepted and/or its attributes modified, | |
1245 | * stores the temporary attributes back to the &rte. | |
1246 | * | |
1247 | * Now, having a "public" version of the route, we | |
f98e2915 | 1248 | * automatically find any old route defined by the protocol @src |
58740ed4 MM |
1249 | * for network @n, replace it by the new one (or removing it if @new is %NULL), |
1250 | * recalculate the optimal route for this destination and finally broadcast | |
9a8f20fc | 1251 | * the change (if any) to all routing protocols by calling rte_announce(). |
3ce8c610 MM |
1252 | * |
1253 | * All memory used for attribute lists and other temporary allocations is taken | |
1254 | * from a special linear pool @rte_update_pool and freed when rte_update() | |
1255 | * finishes. | |
58740ed4 | 1256 | */ |
23ac9e9a OZ |
1257 | |
1258 | void | |
65d2a88d | 1259 | rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src) |
e2dc2f30 | 1260 | { |
61dae32b | 1261 | // struct proto *p = c->proto; |
f4a60a9b | 1262 | struct proto_stats *stats = &c->stats; |
0b39b1cb | 1263 | const struct filter *filter = c->in_filter; |
2003a184 | 1264 | net *nn; |
e2dc2f30 | 1265 | |
f4a60a9b OZ |
1266 | ASSERT(c->channel_state == CS_UP); |
1267 | ||
e2dc2f30 MM |
1268 | rte_update_lock(); |
1269 | if (new) | |
1270 | { | |
c65a9a05 MM |
1271 | /* Create a temporary table node */ |
1272 | nn = alloca(sizeof(net) + n->length); | |
1273 | memset(nn, 0, sizeof(net) + n->length); | |
1274 | net_copy(nn->n.addr, n); | |
2003a184 JMM |
1275 | |
1276 | new->net = nn; | |
f4a60a9b OZ |
1277 | new->sender = c; |
1278 | ||
9db74169 | 1279 | stats->imp_updates_received++; |
cfd46ee4 MM |
1280 | if (!rte_validate(new)) |
1281 | { | |
61dae32b | 1282 | rte_trace_in(D_FILTERS, c, new, "invalid"); |
9db74169 | 1283 | stats->imp_updates_invalid++; |
cfd46ee4 MM |
1284 | goto drop; |
1285 | } | |
cf98be7b | 1286 | |
40b65f94 | 1287 | if (filter == FILTER_REJECT) |
cfd46ee4 | 1288 | { |
9db74169 | 1289 | stats->imp_updates_filtered++; |
61dae32b | 1290 | rte_trace_in(D_FILTERS, c, new, "filtered out"); |
094d2bdb | 1291 | |
f4a60a9b | 1292 | if (! c->in_keep_filtered) |
cf98be7b OZ |
1293 | goto drop; |
1294 | ||
1295 | /* new is a private copy, i could modify it */ | |
15550957 | 1296 | new->flags |= REF_FILTERED; |
cfd46ee4 | 1297 | } |
875cc073 | 1298 | else if (filter) |
e2dc2f30 | 1299 | { |
875cc073 OZ |
1300 | int fr = f_run(filter, &new, rte_update_pool, 0); |
1301 | if (fr > F_ACCEPT) | |
1302 | { | |
1303 | stats->imp_updates_filtered++; | |
61dae32b | 1304 | rte_trace_in(D_FILTERS, c, new, "filtered out"); |
cf98be7b | 1305 | |
875cc073 | 1306 | if (! c->in_keep_filtered) |
875cc073 | 1307 | goto drop; |
875cc073 OZ |
1308 | |
1309 | new->flags |= REF_FILTERED; | |
1310 | } | |
e2dc2f30 | 1311 | } |
094d2bdb | 1312 | if (!rta_is_cached(new->attrs)) /* Need to copy attributes */ |
e2dc2f30 MM |
1313 | new->attrs = rta_lookup(new->attrs); |
1314 | new->flags |= REF_COW; | |
c65a9a05 MM |
1315 | |
1316 | /* Use the actual struct network, not the dummy one */ | |
1317 | nn = net_get(c->table, n); | |
1318 | new->net = nn; | |
e2dc2f30 | 1319 | } |
925fe2d3 | 1320 | else |
094d2bdb OZ |
1321 | { |
1322 | stats->imp_withdraws_received++; | |
1323 | ||
2003a184 | 1324 | if (!(nn = net_find(c->table, n)) || !src) |
094d2bdb OZ |
1325 | { |
1326 | stats->imp_withdraws_ignored++; | |
1327 | rte_update_unlock(); | |
1328 | return; | |
1329 | } | |
1330 | } | |
925fe2d3 | 1331 | |
fad04c75 | 1332 | recalc: |
c65a9a05 | 1333 | /* And recalculate the best route */ |
2003a184 | 1334 | rte_recalculate(c, nn, new, src); |
c65a9a05 | 1335 | |
e2dc2f30 MM |
1336 | rte_update_unlock(); |
1337 | return; | |
1338 | ||
fad04c75 | 1339 | drop: |
e2dc2f30 | 1340 | rte_free(new); |
fad04c75 | 1341 | new = NULL; |
c65a9a05 MM |
1342 | if (nn = net_find(c->table, n)) |
1343 | goto recalc; | |
1344 | ||
1345 | rte_update_unlock(); | |
e2dc2f30 MM |
1346 | } |
1347 | ||
cfe34a31 OZ |
1348 | /* Independent call to rte_announce(), used from next hop |
1349 | recalculation, outside of rte_update(). new must be non-NULL */ | |
a82f692e | 1350 | static inline void |
5ea39eaa | 1351 | rte_announce_i(rtable *tab, uint type, net *net, rte *new, rte *old, |
8d9eef17 | 1352 | rte *new_best, rte *old_best) |
cfe34a31 | 1353 | { |
cfe34a31 | 1354 | rte_update_lock(); |
5ea39eaa | 1355 | rte_announce(tab, type, net, new, old, new_best, old_best); |
cfe34a31 OZ |
1356 | rte_update_unlock(); |
1357 | } | |
1358 | ||
3e236955 JMM |
1359 | static inline void |
1360 | rte_discard(rte *old) /* Non-filtered route deletion, used during garbage collection */ | |
5b22683d | 1361 | { |
e2dc2f30 | 1362 | rte_update_lock(); |
5cff1d5f | 1363 | rte_recalculate(old->sender, old->net, NULL, old->src); |
e2dc2f30 | 1364 | rte_update_unlock(); |
2326b001 MM |
1365 | } |
1366 | ||
5bd73431 OZ |
1367 | /* Modify existing route by protocol hook, used for long-lived graceful restart */ |
1368 | static inline void | |
1369 | rte_modify(rte *old) | |
1370 | { | |
1371 | rte_update_lock(); | |
1372 | ||
1373 | rte *new = old->sender->proto->rte_modify(old, rte_update_pool); | |
1374 | if (new != old) | |
1375 | { | |
1376 | if (new) | |
1377 | { | |
1378 | if (!rta_is_cached(new->attrs)) | |
1379 | new->attrs = rta_lookup(new->attrs); | |
1380 | new->flags = (old->flags & ~REF_MODIFY) | REF_COW; | |
1381 | } | |
1382 | ||
5cff1d5f | 1383 | rte_recalculate(old->sender, old->net, new, old->src); |
5bd73431 OZ |
1384 | } |
1385 | ||
1386 | rte_update_unlock(); | |
1387 | } | |
1388 | ||
36da2857 OZ |
1389 | /* Check rtable for best route to given net whether it would be exported do p */ |
1390 | int | |
0b39b1cb | 1391 | rt_examine(rtable *t, net_addr *a, struct proto *p, const struct filter *filter) |
36da2857 | 1392 | { |
fe9f1a6d | 1393 | net *n = net_find(t, a); |
36da2857 OZ |
1394 | rte *rt = n ? n->routes : NULL; |
1395 | ||
1396 | if (!rte_is_valid(rt)) | |
1397 | return 0; | |
1398 | ||
1399 | rte_update_lock(); | |
1400 | ||
1401 | /* Rest is stripped down export_filter() */ | |
d5a32563 | 1402 | int v = p->preexport ? p->preexport(p, rt) : 0; |
36da2857 | 1403 | if (v == RIC_PROCESS) |
13c0be19 | 1404 | v = (f_run(filter, &rt, rte_update_pool, FF_SILENT) <= F_ACCEPT); |
36da2857 | 1405 | |
95488885 | 1406 | /* Discard temporary rte */ |
36da2857 OZ |
1407 | if (rt != n->routes) |
1408 | rte_free(rt); | |
1409 | ||
1410 | rte_update_unlock(); | |
1411 | ||
1412 | return v > 0; | |
1413 | } | |
1414 | ||
6eda3f13 OZ |
1415 | |
1416 | /** | |
1417 | * rt_refresh_begin - start a refresh cycle | |
1418 | * @t: related routing table | |
f4a60a9b | 1419 | * @c related channel |
6eda3f13 OZ |
1420 | * |
1421 | * This function starts a refresh cycle for given routing table and announce | |
1422 | * hook. The refresh cycle is a sequence where the protocol sends all its valid | |
1423 | * routes to the routing table (by rte_update()). After that, all protocol | |
f4a60a9b | 1424 | * routes (more precisely routes with @c as @sender) not sent during the |
6eda3f13 OZ |
1425 | * refresh cycle but still in the table from the past are pruned. This is |
1426 | * implemented by marking all related routes as stale by REF_STALE flag in | |
1427 | * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD | |
1428 | * flag in rt_refresh_end() and then removing such routes in the prune loop. | |
1429 | */ | |
0c791f87 | 1430 | void |
f4a60a9b | 1431 | rt_refresh_begin(rtable *t, struct channel *c) |
0c791f87 | 1432 | { |
600998fc | 1433 | FIB_WALK(&t->fib, net, n) |
0c791f87 | 1434 | { |
600998fc | 1435 | rte *e; |
0c791f87 | 1436 | for (e = n->routes; e; e = e->next) |
f4a60a9b | 1437 | if (e->sender == c) |
0c791f87 OZ |
1438 | e->flags |= REF_STALE; |
1439 | } | |
1440 | FIB_WALK_END; | |
1441 | } | |
1442 | ||
6eda3f13 OZ |
1443 | /** |
1444 | * rt_refresh_end - end a refresh cycle | |
1445 | * @t: related routing table | |
f4a60a9b | 1446 | * @c: related channel |
6eda3f13 | 1447 | * |
f4a60a9b | 1448 | * This function ends a refresh cycle for given routing table and announce |
6eda3f13 OZ |
1449 | * hook. See rt_refresh_begin() for description of refresh cycles. |
1450 | */ | |
0c791f87 | 1451 | void |
f4a60a9b | 1452 | rt_refresh_end(rtable *t, struct channel *c) |
0c791f87 OZ |
1453 | { |
1454 | int prune = 0; | |
0c791f87 | 1455 | |
600998fc | 1456 | FIB_WALK(&t->fib, net, n) |
0c791f87 | 1457 | { |
600998fc | 1458 | rte *e; |
0c791f87 | 1459 | for (e = n->routes; e; e = e->next) |
f4a60a9b | 1460 | if ((e->sender == c) && (e->flags & REF_STALE)) |
0c791f87 OZ |
1461 | { |
1462 | e->flags |= REF_DISCARD; | |
1463 | prune = 1; | |
1464 | } | |
1465 | } | |
1466 | FIB_WALK_END; | |
1467 | ||
1468 | if (prune) | |
1469 | rt_schedule_prune(t); | |
1470 | } | |
1471 | ||
5bd73431 OZ |
1472 | void |
1473 | rt_modify_stale(rtable *t, struct channel *c) | |
1474 | { | |
1475 | int prune = 0; | |
1476 | ||
1477 | FIB_WALK(&t->fib, net, n) | |
1478 | { | |
1479 | rte *e; | |
1480 | for (e = n->routes; e; e = e->next) | |
1481 | if ((e->sender == c) && (e->flags & REF_STALE) && !(e->flags & REF_FILTERED)) | |
1482 | { | |
1483 | e->flags |= REF_MODIFY; | |
1484 | prune = 1; | |
1485 | } | |
1486 | } | |
1487 | FIB_WALK_END; | |
1488 | ||
1489 | if (prune) | |
1490 | rt_schedule_prune(t); | |
1491 | } | |
0c791f87 | 1492 | |
58740ed4 MM |
1493 | /** |
1494 | * rte_dump - dump a route | |
1495 | * @e: &rte to be dumped | |
1496 | * | |
1497 | * This functions dumps contents of a &rte to debug output. | |
1498 | */ | |
2326b001 | 1499 | void |
a0762910 | 1500 | rte_dump(rte *e) |
2326b001 | 1501 | { |
a0762910 | 1502 | net *n = e->net; |
fe9f1a6d | 1503 | debug("%-1N ", n->n.addr); |
eb937358 | 1504 | debug("PF=%02x ", e->pflags); |
0cdbd397 | 1505 | rta_dump(e->attrs); |
0cdbd397 | 1506 | debug("\n"); |
2326b001 | 1507 | } |
62aa008a | 1508 | |
58740ed4 MM |
1509 | /** |
1510 | * rt_dump - dump a routing table | |
1511 | * @t: routing table to be dumped | |
1512 | * | |
1513 | * This function dumps contents of a given routing table to debug output. | |
1514 | */ | |
2326b001 MM |
1515 | void |
1516 | rt_dump(rtable *t) | |
1517 | { | |
0cdbd397 | 1518 | debug("Dump of routing table <%s>\n", t->name); |
e440395d | 1519 | #ifdef DEBUGGING |
08e2d625 | 1520 | fib_check(&t->fib); |
e440395d | 1521 | #endif |
600998fc | 1522 | FIB_WALK(&t->fib, net, n) |
08e2d625 | 1523 | { |
600998fc | 1524 | rte *e; |
08e2d625 MM |
1525 | for(e=n->routes; e; e=e->next) |
1526 | rte_dump(e); | |
0cdbd397 | 1527 | } |
08e2d625 | 1528 | FIB_WALK_END; |
0cdbd397 | 1529 | debug("\n"); |
2326b001 | 1530 | } |
62aa008a | 1531 | |
58740ed4 MM |
1532 | /** |
1533 | * rt_dump_all - dump all routing tables | |
1534 | * | |
1535 | * This function dumps contents of all routing tables to debug output. | |
1536 | */ | |
6d45cf21 MM |
1537 | void |
1538 | rt_dump_all(void) | |
1539 | { | |
0e02abfd | 1540 | rtable *t; |
4635314c | 1541 | node *n; |
0e02abfd | 1542 | |
4635314c | 1543 | WALK_LIST2(t, n, routing_tables, n) |
0e02abfd | 1544 | rt_dump(t); |
6d45cf21 MM |
1545 | } |
1546 | ||
cfe34a31 OZ |
1547 | static inline void |
1548 | rt_schedule_hcu(rtable *tab) | |
1549 | { | |
1550 | if (tab->hcu_scheduled) | |
1551 | return; | |
1552 | ||
1553 | tab->hcu_scheduled = 1; | |
1554 | ev_schedule(tab->rt_event); | |
1555 | } | |
1556 | ||
1557 | static inline void | |
1558 | rt_schedule_nhu(rtable *tab) | |
1559 | { | |
93f50ca3 | 1560 | if (tab->nhu_state == NHU_CLEAN) |
cfe34a31 OZ |
1561 | ev_schedule(tab->rt_event); |
1562 | ||
93f50ca3 JMM |
1563 | /* state change: |
1564 | * NHU_CLEAN -> NHU_SCHEDULED | |
1565 | * NHU_RUNNING -> NHU_DIRTY | |
1566 | */ | |
1567 | tab->nhu_state |= NHU_SCHEDULED; | |
cfe34a31 OZ |
1568 | } |
1569 | ||
f4a60a9b OZ |
1570 | void |
1571 | rt_schedule_prune(rtable *tab) | |
fb829de6 | 1572 | { |
f4a60a9b OZ |
1573 | if (tab->prune_state == 0) |
1574 | ev_schedule(tab->rt_event); | |
fb829de6 | 1575 | |
f4a60a9b OZ |
1576 | /* state change 0->1, 2->3 */ |
1577 | tab->prune_state |= 1; | |
fb829de6 OZ |
1578 | } |
1579 | ||
f4a60a9b | 1580 | |
8f6accb5 | 1581 | static void |
cfe34a31 | 1582 | rt_event(void *ptr) |
5996da6a | 1583 | { |
cfe34a31 OZ |
1584 | rtable *tab = ptr; |
1585 | ||
286e2011 OZ |
1586 | rt_lock_table(tab); |
1587 | ||
cfe34a31 OZ |
1588 | if (tab->hcu_scheduled) |
1589 | rt_update_hostcache(tab); | |
0e02abfd | 1590 | |
cfe34a31 OZ |
1591 | if (tab->nhu_state) |
1592 | rt_next_hop_update(tab); | |
1593 | ||
0c791f87 | 1594 | if (tab->prune_state) |
f4a60a9b | 1595 | rt_prune_table(tab); |
286e2011 OZ |
1596 | |
1597 | rt_unlock_table(tab); | |
5996da6a MM |
1598 | } |
1599 | ||
00b85905 OZ |
1600 | |
1601 | static inline btime | |
1602 | rt_settled_time(rtable *tab) | |
1603 | { | |
1604 | ASSUME(tab->base_settle_time != 0); | |
1605 | ||
1606 | return MIN(tab->last_rt_change + tab->config->min_settle_time, | |
1607 | tab->base_settle_time + tab->config->max_settle_time); | |
1608 | } | |
1609 | ||
1610 | static void | |
1611 | rt_settle_timer(timer *t) | |
1612 | { | |
1613 | rtable *tab = t->data; | |
1614 | ||
1615 | if (!tab->base_settle_time) | |
1616 | return; | |
1617 | ||
1618 | btime settled_time = rt_settled_time(tab); | |
1619 | if (current_time() < settled_time) | |
1620 | { | |
1621 | tm_set(tab->settle_timer, settled_time); | |
1622 | return; | |
1623 | } | |
1624 | ||
1625 | /* Settled */ | |
1626 | tab->base_settle_time = 0; | |
1627 | ||
1628 | struct rt_subscription *s; | |
1629 | WALK_LIST(s, tab->subscribers) | |
1630 | s->hook(s); | |
1631 | } | |
1632 | ||
1633 | static void | |
1634 | rt_kick_settle_timer(rtable *tab) | |
1635 | { | |
1636 | tab->base_settle_time = current_time(); | |
1637 | ||
1638 | if (!tab->settle_timer) | |
ff397df7 | 1639 | tab->settle_timer = tm_new_init(tab->rp, rt_settle_timer, tab, 0, 0); |
00b85905 OZ |
1640 | |
1641 | if (!tm_active(tab->settle_timer)) | |
1642 | tm_set(tab->settle_timer, rt_settled_time(tab)); | |
1643 | } | |
1644 | ||
1645 | static inline void | |
1646 | rt_schedule_notify(rtable *tab) | |
1647 | { | |
1648 | if (EMPTY_LIST(tab->subscribers)) | |
1649 | return; | |
1650 | ||
1651 | if (tab->base_settle_time) | |
1652 | return; | |
1653 | ||
1654 | rt_kick_settle_timer(tab); | |
1655 | } | |
1656 | ||
1657 | void | |
1658 | rt_subscribe(rtable *tab, struct rt_subscription *s) | |
1659 | { | |
1660 | s->tab = tab; | |
1661 | rt_lock_table(tab); | |
1662 | add_tail(&tab->subscribers, &s->n); | |
1663 | } | |
1664 | ||
1665 | void | |
1666 | rt_unsubscribe(struct rt_subscription *s) | |
1667 | { | |
1668 | rem_node(&s->n); | |
1669 | rt_unlock_table(s->tab); | |
1670 | } | |
1671 | ||
ff397df7 MM |
1672 | static void |
1673 | rt_free(resource *_r) | |
1674 | { | |
1675 | rtable *r = (rtable *) _r; | |
1676 | ||
1677 | DBG("Deleting routing table %s\n", r->name); | |
1678 | ASSERT_DIE(r->use_count == 0); | |
1679 | ||
3d90241f MM |
1680 | if (r->internal) |
1681 | return; | |
1682 | ||
ff397df7 MM |
1683 | r->config->table = NULL; |
1684 | rem_node(&r->n); | |
1685 | ||
1686 | if (r->hostcache) | |
1687 | rt_free_hostcache(r); | |
1688 | ||
1689 | /* Freed automagically by the resource pool | |
1690 | fib_free(&r->fib); | |
1691 | hmap_free(&r->id_map); | |
1692 | rfree(r->rt_event); | |
1693 | rfree(r->settle_timer); | |
1694 | mb_free(r); | |
1695 | */ | |
1696 | } | |
1697 | ||
1698 | static void | |
1699 | rt_res_dump(resource *_r) | |
1700 | { | |
1701 | rtable *r = (rtable *) _r; | |
1702 | debug("name \"%s\", addr_type=%s, rt_count=%u, use_count=%d\n", | |
1703 | r->name, net_label[r->addr_type], r->rt_count, r->use_count); | |
1704 | } | |
1705 | ||
1706 | static struct resclass rt_class = { | |
1707 | .name = "Routing table", | |
1708 | .size = sizeof(struct rtable), | |
1709 | .free = rt_free, | |
1710 | .dump = rt_res_dump, | |
1711 | .lookup = NULL, | |
1712 | .memsize = NULL, | |
1713 | }; | |
1714 | ||
1715 | rtable * | |
1716 | rt_setup(pool *pp, struct rtable_config *cf) | |
b9626ec6 | 1717 | { |
ff397df7 MM |
1718 | int ns = strlen("Routing table ") + strlen(cf->name) + 1; |
1719 | void *nb = mb_alloc(pp, ns); | |
1720 | ASSERT_DIE(ns - 1 == bsnprintf(nb, ns, "Routing table %s", cf->name)); | |
1721 | ||
1722 | pool *p = rp_new(pp, nb); | |
1723 | mb_move(nb, p); | |
1724 | ||
1725 | rtable *t = ralloc(p, &rt_class); | |
1726 | t->rp = p; | |
1727 | ||
28b3b551 | 1728 | t->name = cf->name; |
b9626ec6 | 1729 | t->config = cf; |
28b3b551 | 1730 | t->addr_type = cf->addr_type; |
ff397df7 | 1731 | |
fe9f1a6d | 1732 | fib_init(&t->fib, p, t->addr_type, sizeof(net), OFFSETOF(net, n), 0, NULL); |
f4a60a9b | 1733 | |
3d90241f | 1734 | if (!(t->internal = cf->internal)) |
ff397df7 MM |
1735 | { |
1736 | init_list(&t->channels); | |
1737 | hmap_init(&t->id_map, p, 1024); | |
1738 | hmap_set(&t->id_map, 0); | |
1739 | ||
1740 | init_list(&t->subscribers); | |
5ea39eaa | 1741 | |
ff397df7 MM |
1742 | t->rt_event = ev_new_init(p, rt_event, t); |
1743 | t->last_rt_change = t->gc_time = current_time(); | |
1744 | } | |
00b85905 | 1745 | |
ff397df7 | 1746 | return t; |
b9626ec6 MM |
1747 | } |
1748 | ||
58740ed4 MM |
1749 | /** |
1750 | * rt_init - initialize routing tables | |
1751 | * | |
1752 | * This function is called during BIRD startup. It initializes the | |
1753 | * routing table module. | |
1754 | */ | |
2326b001 MM |
1755 | void |
1756 | rt_init(void) | |
1757 | { | |
1758 | rta_init(); | |
5996da6a | 1759 | rt_table_pool = rp_new(&root_pool, "Routing tables"); |
05d47bd5 | 1760 | rte_update_pool = lp_new_default(rt_table_pool); |
5996da6a | 1761 | rte_slab = sl_new(rt_table_pool, sizeof(rte)); |
0e02abfd | 1762 | init_list(&routing_tables); |
2326b001 | 1763 | } |
1a54b1c6 | 1764 | |
fb829de6 | 1765 | |
f4a60a9b OZ |
1766 | /** |
1767 | * rt_prune_table - prune a routing table | |
1768 | * | |
1769 | * The prune loop scans routing tables and removes routes belonging to flushing | |
1770 | * protocols, discarded routes and also stale network entries. It is called from | |
1771 | * rt_event(). The event is rescheduled if the current iteration do not finish | |
1772 | * the table. The pruning is directed by the prune state (@prune_state), | |
1773 | * specifying whether the prune cycle is scheduled or running, and there | |
1774 | * is also a persistent pruning iterator (@prune_fit). | |
1775 | * | |
1776 | * The prune loop is used also for channel flushing. For this purpose, the | |
1777 | * channels to flush are marked before the iteration and notified after the | |
1778 | * iteration. | |
1779 | */ | |
1780 | static void | |
1781 | rt_prune_table(rtable *tab) | |
fb829de6 OZ |
1782 | { |
1783 | struct fib_iterator *fit = &tab->prune_fit; | |
f4a60a9b OZ |
1784 | int limit = 512; |
1785 | ||
1786 | struct channel *c; | |
1787 | node *n, *x; | |
1a54b1c6 MM |
1788 | |
1789 | DBG("Pruning route table %s\n", tab->name); | |
0521e4f6 MM |
1790 | #ifdef DEBUGGING |
1791 | fib_check(&tab->fib); | |
1792 | #endif | |
fb829de6 | 1793 | |
f4a60a9b OZ |
1794 | if (tab->prune_state == 0) |
1795 | return; | |
fb829de6 | 1796 | |
f4a60a9b OZ |
1797 | if (tab->prune_state == 1) |
1798 | { | |
1799 | /* Mark channels to flush */ | |
1800 | WALK_LIST2(c, n, tab->channels, table_node) | |
1801 | if (c->channel_state == CS_FLUSHING) | |
1802 | c->flush_active = 1; | |
1803 | ||
1804 | FIB_ITERATE_INIT(fit, &tab->fib); | |
1805 | tab->prune_state = 2; | |
1806 | } | |
fb829de6 | 1807 | |
08e2d625 | 1808 | again: |
600998fc | 1809 | FIB_ITERATE_START(&tab->fib, fit, net, n) |
1a54b1c6 | 1810 | { |
08e2d625 | 1811 | rte *e; |
fb829de6 | 1812 | |
08e2d625 | 1813 | rescan: |
fb829de6 | 1814 | for (e=n->routes; e; e=e->next) |
5bd73431 | 1815 | { |
f4a60a9b | 1816 | if (e->sender->flush_active || (e->flags & REF_DISCARD)) |
08e2d625 | 1817 | { |
f4a60a9b | 1818 | if (limit <= 0) |
fb829de6 | 1819 | { |
600998fc | 1820 | FIB_ITERATE_PUT(fit); |
f4a60a9b OZ |
1821 | ev_schedule(tab->rt_event); |
1822 | return; | |
fb829de6 OZ |
1823 | } |
1824 | ||
3e236955 | 1825 | rte_discard(e); |
f4a60a9b | 1826 | limit--; |
fb829de6 | 1827 | |
08e2d625 MM |
1828 | goto rescan; |
1829 | } | |
f4a60a9b | 1830 | |
5bd73431 OZ |
1831 | if (e->flags & REF_MODIFY) |
1832 | { | |
1833 | if (limit <= 0) | |
1834 | { | |
1835 | FIB_ITERATE_PUT(fit); | |
1836 | ev_schedule(tab->rt_event); | |
1837 | return; | |
1838 | } | |
1839 | ||
1840 | rte_modify(e); | |
1841 | limit--; | |
1842 | ||
1843 | goto rescan; | |
1844 | } | |
1845 | } | |
1846 | ||
fb829de6 | 1847 | if (!n->routes) /* Orphaned FIB entry */ |
1a54b1c6 | 1848 | { |
600998fc OZ |
1849 | FIB_ITERATE_PUT(fit); |
1850 | fib_delete(&tab->fib, n); | |
08e2d625 | 1851 | goto again; |
1a54b1c6 | 1852 | } |
1a54b1c6 | 1853 | } |
600998fc | 1854 | FIB_ITERATE_END; |
fb829de6 | 1855 | |
0521e4f6 MM |
1856 | #ifdef DEBUGGING |
1857 | fib_check(&tab->fib); | |
1858 | #endif | |
fb829de6 | 1859 | |
f4a60a9b | 1860 | tab->gc_counter = 0; |
f047271c | 1861 | tab->gc_time = current_time(); |
0e02abfd | 1862 | |
f4a60a9b OZ |
1863 | /* state change 2->0, 3->1 */ |
1864 | tab->prune_state &= 1; | |
0c791f87 | 1865 | |
f4a60a9b OZ |
1866 | if (tab->prune_state > 0) |
1867 | ev_schedule(tab->rt_event); | |
0e02abfd | 1868 | |
f4a60a9b OZ |
1869 | /* FIXME: This should be handled in a better way */ |
1870 | rt_prune_sources(); | |
fb829de6 | 1871 | |
f4a60a9b OZ |
1872 | /* Close flushed channels */ |
1873 | WALK_LIST2_DELSAFE(c, n, x, tab->channels, table_node) | |
1874 | if (c->flush_active) | |
1875 | { | |
1876 | c->flush_active = 0; | |
286e2011 | 1877 | channel_set_state(c, CS_DOWN); |
f4a60a9b OZ |
1878 | } |
1879 | ||
1880 | return; | |
0e02abfd MM |
1881 | } |
1882 | ||
cfe34a31 OZ |
1883 | void |
1884 | rt_preconfig(struct config *c) | |
1885 | { | |
cfe34a31 | 1886 | init_list(&c->tables); |
f4a60a9b OZ |
1887 | |
1888 | rt_new_table(cf_get_symbol("master4"), NET_IP4); | |
1889 | rt_new_table(cf_get_symbol("master6"), NET_IP6); | |
cfe34a31 OZ |
1890 | } |
1891 | ||
1892 | ||
f4a60a9b | 1893 | /* |
cfe34a31 OZ |
1894 | * Some functions for handing internal next hop updates |
1895 | * triggered by rt_schedule_nhu(). | |
1896 | */ | |
1897 | ||
cfe34a31 OZ |
1898 | static inline int |
1899 | rta_next_hop_outdated(rta *a) | |
1900 | { | |
1901 | struct hostentry *he = a->hostentry; | |
7e95c05d OZ |
1902 | |
1903 | if (!he) | |
1904 | return 0; | |
1905 | ||
1906 | if (!he->src) | |
1907 | return a->dest != RTD_UNREACHABLE; | |
1908 | ||
4e276a89 | 1909 | return (a->dest != he->dest) || (a->igp_metric != he->igp_metric) || |
039a65d0 | 1910 | (!he->nexthop_linkable) || !nexthop_same(&(a->nh), &(he->src->nh)); |
cfe34a31 OZ |
1911 | } |
1912 | ||
1e37e35c | 1913 | void |
3c744164 | 1914 | rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls) |
cfe34a31 OZ |
1915 | { |
1916 | a->hostentry = he; | |
cfe34a31 | 1917 | a->dest = he->dest; |
d1e146f2 | 1918 | a->igp_metric = he->igp_metric; |
d47c3d64 | 1919 | |
3c744164 | 1920 | if (a->dest != RTD_UNICAST) |
d47c3d64 | 1921 | { |
3c744164 JMM |
1922 | /* No nexthop */ |
1923 | no_nexthop: | |
1924 | a->nh = (struct nexthop) {}; | |
1925 | if (mls) | |
1926 | { /* Store the label stack for later changes */ | |
1927 | a->nh.labels_orig = a->nh.labels = mls->len; | |
1928 | memcpy(a->nh.label, mls->stack, mls->len * sizeof(u32)); | |
1929 | } | |
d47c3d64 JMM |
1930 | return; |
1931 | } | |
1932 | ||
3c744164 JMM |
1933 | if (((!mls) || (!mls->len)) && he->nexthop_linkable) |
1934 | { /* Just link the nexthop chain, no label append happens. */ | |
1935 | memcpy(&(a->nh), &(he->src->nh), nexthop_size(&(he->src->nh))); | |
1936 | return; | |
1937 | } | |
1938 | ||
1939 | struct nexthop *nhp = NULL, *nhr = NULL; | |
1940 | int skip_nexthop = 0; | |
1e37e35c | 1941 | |
3c744164 | 1942 | for (struct nexthop *nh = &(he->src->nh); nh; nh = nh->next) |
d47c3d64 | 1943 | { |
3c744164 JMM |
1944 | if (skip_nexthop) |
1945 | skip_nexthop--; | |
1946 | else | |
1947 | { | |
1948 | nhr = nhp; | |
cb2b6e04 | 1949 | nhp = (nhp ? (nhp->next = lp_alloc(rte_update_pool, NEXTHOP_MAX_SIZE)) : &(a->nh)); |
3c744164 | 1950 | } |
039a65d0 | 1951 | |
cb2b6e04 | 1952 | memset(nhp, 0, NEXTHOP_MAX_SIZE); |
3c744164 JMM |
1953 | nhp->iface = nh->iface; |
1954 | nhp->weight = nh->weight; | |
843b10c8 | 1955 | |
3c744164 | 1956 | if (mls) |
d47c3d64 | 1957 | { |
3c744164 JMM |
1958 | nhp->labels = nh->labels + mls->len; |
1959 | nhp->labels_orig = mls->len; | |
039a65d0 JMM |
1960 | if (nhp->labels <= MPLS_MAX_LABEL_STACK) |
1961 | { | |
1962 | memcpy(nhp->label, nh->label, nh->labels * sizeof(u32)); /* First the hostentry labels */ | |
3c744164 | 1963 | memcpy(&(nhp->label[nh->labels]), mls->stack, mls->len * sizeof(u32)); /* Then the bottom labels */ |
039a65d0 JMM |
1964 | } |
1965 | else | |
1966 | { | |
1967 | log(L_WARN "Sum of label stack sizes %d + %d = %d exceedes allowed maximum (%d)", | |
3c744164 JMM |
1968 | nh->labels, mls->len, nhp->labels, MPLS_MAX_LABEL_STACK); |
1969 | skip_nexthop++; | |
039a65d0 JMM |
1970 | continue; |
1971 | } | |
d47c3d64 | 1972 | } |
843b10c8 OZ |
1973 | else if (nh->labels) |
1974 | { | |
1975 | nhp->labels = nh->labels; | |
1976 | nhp->labels_orig = 0; | |
1977 | memcpy(nhp->label, nh->label, nh->labels * sizeof(u32)); | |
1978 | } | |
1979 | ||
3c744164 | 1980 | if (ipa_nonzero(nh->gw)) |
a1f5e514 OZ |
1981 | { |
1982 | nhp->gw = nh->gw; /* Router nexthop */ | |
1983 | nhp->flags |= (nh->flags & RNF_ONLINK); | |
1984 | } | |
9eace843 OZ |
1985 | else if (!(nh->iface->flags & IF_MULTIACCESS) || (nh->iface->flags & IF_LOOPBACK)) |
1986 | nhp->gw = IPA_NONE; /* PtP link - no need for nexthop */ | |
3c744164 JMM |
1987 | else if (ipa_nonzero(he->link)) |
1988 | nhp->gw = he->link; /* Device nexthop with link-local address known */ | |
1989 | else | |
1990 | nhp->gw = he->addr; /* Device nexthop with link-local address unknown */ | |
d47c3d64 | 1991 | } |
039a65d0 | 1992 | |
3c744164 JMM |
1993 | if (skip_nexthop) |
1994 | if (nhr) | |
1995 | nhr->next = NULL; | |
1996 | else | |
1997 | { | |
1998 | a->dest = RTD_UNREACHABLE; | |
1999 | log(L_WARN "No valid nexthop remaining, setting route unreachable"); | |
2000 | goto no_nexthop; | |
2001 | } | |
cfe34a31 OZ |
2002 | } |
2003 | ||
2004 | static inline rte * | |
3e236955 | 2005 | rt_next_hop_update_rte(rtable *tab UNUSED, rte *old) |
cfe34a31 | 2006 | { |
62e64905 OZ |
2007 | rta *a = alloca(RTA_MAX_SIZE); |
2008 | memcpy(a, old->attrs, rta_size(old->attrs)); | |
3c744164 JMM |
2009 | |
2010 | mpls_label_stack mls = { .len = a->nh.labels_orig }; | |
2011 | memcpy(mls.stack, &a->nh.label[a->nh.labels - mls.len], mls.len * sizeof(u32)); | |
2012 | ||
2013 | rta_apply_hostentry(a, old->attrs->hostentry, &mls); | |
eb937358 | 2014 | a->cached = 0; |
cfe34a31 OZ |
2015 | |
2016 | rte *e = sl_alloc(rte_slab); | |
2017 | memcpy(e, old, sizeof(rte)); | |
62e64905 | 2018 | e->attrs = rta_lookup(a); |
5cff1d5f | 2019 | rt_lock_source(e->src); |
cfe34a31 OZ |
2020 | |
2021 | return e; | |
2022 | } | |
2023 | ||
2024 | static inline int | |
2025 | rt_next_hop_update_net(rtable *tab, net *n) | |
2026 | { | |
2027 | rte **k, *e, *new, *old_best, **new_best; | |
2028 | int count = 0; | |
2029 | int free_old_best = 0; | |
2030 | ||
2031 | old_best = n->routes; | |
2032 | if (!old_best) | |
2033 | return 0; | |
2034 | ||
cfe34a31 | 2035 | for (k = &n->routes; e = *k; k = &e->next) |
be4cd99a OZ |
2036 | if (rta_next_hop_outdated(e->attrs)) |
2037 | { | |
2038 | new = rt_next_hop_update_rte(tab, e); | |
2039 | *k = new; | |
cfe34a31 | 2040 | |
61dae32b | 2041 | rte_trace_in(D_ROUTES, new->sender, new, "updated"); |
5ea39eaa | 2042 | rte_announce_i(tab, RA_ANY, n, new, e, NULL, NULL); |
cfe34a31 | 2043 | |
be4cd99a OZ |
2044 | /* Call a pre-comparison hook */ |
2045 | /* Not really an efficient way to compute this */ | |
5cff1d5f MM |
2046 | if (e->src->proto->rte_recalculate) |
2047 | e->src->proto->rte_recalculate(tab, n, new, e, NULL); | |
cfe34a31 | 2048 | |
be4cd99a OZ |
2049 | if (e != old_best) |
2050 | rte_free_quick(e); | |
2051 | else /* Freeing of the old best rte is postponed */ | |
2052 | free_old_best = 1; | |
cfe34a31 | 2053 | |
be4cd99a OZ |
2054 | e = new; |
2055 | count++; | |
2056 | } | |
2057 | ||
2058 | if (!count) | |
2059 | return 0; | |
2060 | ||
2061 | /* Find the new best route */ | |
2062 | new_best = NULL; | |
2063 | for (k = &n->routes; e = *k; k = &e->next) | |
2064 | { | |
cfe34a31 OZ |
2065 | if (!new_best || rte_better(e, *new_best)) |
2066 | new_best = k; | |
2067 | } | |
2068 | ||
2069 | /* Relink the new best route to the first position */ | |
2070 | new = *new_best; | |
2071 | if (new != n->routes) | |
2072 | { | |
2073 | *new_best = new->next; | |
2074 | new->next = n->routes; | |
2075 | n->routes = new; | |
2076 | } | |
2077 | ||
2078 | /* Announce the new best route */ | |
2079 | if (new != old_best) | |
61dae32b | 2080 | rte_trace_in(D_ROUTES, new->sender, new, "updated [best]"); |
cfe34a31 | 2081 | |
5ea39eaa OZ |
2082 | /* Propagate changes */ |
2083 | rte_announce_i(tab, RA_UNDEF, n, NULL, NULL, n->routes, old_best); | |
8d9eef17 | 2084 | |
d107ef78 | 2085 | if (free_old_best) |
cfe34a31 OZ |
2086 | rte_free_quick(old_best); |
2087 | ||
2088 | return count; | |
2089 | } | |
2090 | ||
2091 | static void | |
2092 | rt_next_hop_update(rtable *tab) | |
2093 | { | |
2094 | struct fib_iterator *fit = &tab->nhu_fit; | |
2095 | int max_feed = 32; | |
2096 | ||
93f50ca3 | 2097 | if (tab->nhu_state == NHU_CLEAN) |
cfe34a31 OZ |
2098 | return; |
2099 | ||
93f50ca3 | 2100 | if (tab->nhu_state == NHU_SCHEDULED) |
cfe34a31 OZ |
2101 | { |
2102 | FIB_ITERATE_INIT(fit, &tab->fib); | |
93f50ca3 | 2103 | tab->nhu_state = NHU_RUNNING; |
cfe34a31 OZ |
2104 | } |
2105 | ||
600998fc | 2106 | FIB_ITERATE_START(&tab->fib, fit, net, n) |
cfe34a31 OZ |
2107 | { |
2108 | if (max_feed <= 0) | |
2109 | { | |
600998fc | 2110 | FIB_ITERATE_PUT(fit); |
cfe34a31 OZ |
2111 | ev_schedule(tab->rt_event); |
2112 | return; | |
2113 | } | |
600998fc | 2114 | max_feed -= rt_next_hop_update_net(tab, n); |
cfe34a31 | 2115 | } |
600998fc | 2116 | FIB_ITERATE_END; |
cfe34a31 | 2117 | |
93f50ca3 JMM |
2118 | /* State change: |
2119 | * NHU_DIRTY -> NHU_SCHEDULED | |
2120 | * NHU_RUNNING -> NHU_CLEAN | |
2121 | */ | |
cfe34a31 OZ |
2122 | tab->nhu_state &= 1; |
2123 | ||
93f50ca3 | 2124 | if (tab->nhu_state != NHU_CLEAN) |
cfe34a31 OZ |
2125 | ev_schedule(tab->rt_event); |
2126 | } | |
2127 | ||
2128 | ||
b9626ec6 | 2129 | struct rtable_config * |
fe9f1a6d | 2130 | rt_new_table(struct symbol *s, uint addr_type) |
b9626ec6 | 2131 | { |
36415e4b | 2132 | /* Hack that allows to 'redefine' the master table */ |
f4a60a9b | 2133 | if ((s->class == SYM_TABLE) && |
0b39b1cb | 2134 | (s->table == new_config->def_tables[addr_type]) && |
f4a60a9b | 2135 | ((addr_type == NET_IP4) || (addr_type == NET_IP6))) |
0b39b1cb | 2136 | return s->table; |
36415e4b | 2137 | |
b9626ec6 MM |
2138 | struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config)); |
2139 | ||
0b39b1cb | 2140 | cf_define_symbol(s, SYM_TABLE, table, c); |
b9626ec6 | 2141 | c->name = s->name; |
fe9f1a6d | 2142 | c->addr_type = addr_type; |
2eca3b3a | 2143 | c->gc_max_ops = 1000; |
b9626ec6 | 2144 | c->gc_min_time = 5; |
00b85905 OZ |
2145 | c->min_settle_time = 1 S; |
2146 | c->max_settle_time = 20 S; | |
f4a60a9b OZ |
2147 | |
2148 | add_tail(&new_config->tables, &c->n); | |
2149 | ||
2150 | /* First table of each type is kept as default */ | |
2151 | if (! new_config->def_tables[addr_type]) | |
2152 | new_config->def_tables[addr_type] = c; | |
2153 | ||
b9626ec6 MM |
2154 | return c; |
2155 | } | |
2156 | ||
58740ed4 MM |
2157 | /** |
2158 | * rt_lock_table - lock a routing table | |
2159 | * @r: routing table to be locked | |
2160 | * | |
2161 | * Lock a routing table, because it's in use by a protocol, | |
2162 | * preventing it from being freed when it gets undefined in a new | |
2163 | * configuration. | |
2164 | */ | |
0e02abfd | 2165 | void |
50fe90ed | 2166 | rt_lock_table(rtable *r) |
0e02abfd | 2167 | { |
50fe90ed MM |
2168 | r->use_count++; |
2169 | } | |
2170 | ||
58740ed4 MM |
2171 | /** |
2172 | * rt_unlock_table - unlock a routing table | |
2173 | * @r: routing table to be unlocked | |
2174 | * | |
2175 | * Unlock a routing table formerly locked by rt_lock_table(), | |
2176 | * that is decrease its use count and delete it if it's scheduled | |
2177 | * for deletion by configuration changes. | |
2178 | */ | |
50fe90ed MM |
2179 | void |
2180 | rt_unlock_table(rtable *r) | |
2181 | { | |
2182 | if (!--r->use_count && r->deleted) | |
2183 | { | |
2184 | struct config *conf = r->deleted; | |
ff397df7 MM |
2185 | |
2186 | /* Delete the routing table by freeing its pool */ | |
2187 | rt_shutdown(r); | |
50fe90ed MM |
2188 | config_del_obstacle(conf); |
2189 | } | |
2190 | } | |
2191 | ||
bcb4af81 OZ |
2192 | static struct rtable_config * |
2193 | rt_find_table_config(struct config *cf, char *name) | |
2194 | { | |
2195 | struct symbol *sym = cf_find_symbol(cf, name); | |
0b39b1cb | 2196 | return (sym && (sym->class == SYM_TABLE)) ? sym->table : NULL; |
bcb4af81 OZ |
2197 | } |
2198 | ||
58740ed4 MM |
2199 | /** |
2200 | * rt_commit - commit new routing table configuration | |
2201 | * @new: new configuration | |
2202 | * @old: original configuration or %NULL if it's boot time config | |
2203 | * | |
2204 | * Scan differences between @old and @new configuration and modify | |
2205 | * the routing tables according to these changes. If @new defines a | |
2206 | * previously unknown table, create it, if it omits a table existing | |
2207 | * in @old, schedule it for deletion (it gets deleted when all protocols | |
2208 | * disconnect from it by calling rt_unlock_table()), if it exists | |
2209 | * in both configurations, leave it unchanged. | |
2210 | */ | |
50fe90ed MM |
2211 | void |
2212 | rt_commit(struct config *new, struct config *old) | |
2213 | { | |
2214 | struct rtable_config *o, *r; | |
0e02abfd | 2215 | |
50fe90ed MM |
2216 | DBG("rt_commit:\n"); |
2217 | if (old) | |
0e02abfd | 2218 | { |
50fe90ed MM |
2219 | WALK_LIST(o, old->tables) |
2220 | { | |
2221 | rtable *ot = o->table; | |
2222 | if (!ot->deleted) | |
2223 | { | |
bcb4af81 OZ |
2224 | r = rt_find_table_config(new, o->name); |
2225 | if (r && (r->addr_type == o->addr_type) && !new->shutdown) | |
50fe90ed MM |
2226 | { |
2227 | DBG("\t%s: same\n", o->name); | |
50fe90ed MM |
2228 | r->table = ot; |
2229 | ot->name = r->name; | |
b9626ec6 | 2230 | ot->config = r; |
26822d8f OZ |
2231 | if (o->sorted != r->sorted) |
2232 | log(L_WARN "Reconfiguration of rtable sorted flag not implemented"); | |
50fe90ed MM |
2233 | } |
2234 | else | |
2235 | { | |
bf8558bc | 2236 | DBG("\t%s: deleted\n", o->name); |
50fe90ed MM |
2237 | ot->deleted = old; |
2238 | config_add_obstacle(old); | |
2239 | rt_lock_table(ot); | |
2240 | rt_unlock_table(ot); | |
2241 | } | |
2242 | } | |
2243 | } | |
0e02abfd | 2244 | } |
50fe90ed MM |
2245 | |
2246 | WALK_LIST(r, new->tables) | |
2247 | if (!r->table) | |
2248 | { | |
ff397df7 | 2249 | r->table = rt_setup(rt_table_pool, r); |
50fe90ed | 2250 | DBG("\t%s: created\n", r->name); |
ff397df7 | 2251 | add_tail(&routing_tables, &r->table->n); |
50fe90ed MM |
2252 | } |
2253 | DBG("\tdone\n"); | |
0e02abfd | 2254 | } |
730f2e2c | 2255 | |
23ac9e9a | 2256 | static inline void |
f4a60a9b | 2257 | do_feed_channel(struct channel *c, net *n, rte *e) |
23ac9e9a | 2258 | { |
23ac9e9a | 2259 | rte_update_lock(); |
f4a60a9b | 2260 | if (c->ra_mode == RA_ACCEPTED) |
5ea39eaa | 2261 | rt_notify_accepted(c, n, NULL, NULL, c->refeeding); |
f4a60a9b | 2262 | else if (c->ra_mode == RA_MERGED) |
5ea39eaa | 2263 | rt_notify_merged(c, n, NULL, NULL, e, e, c->refeeding); |
f4a60a9b | 2264 | else /* RA_BASIC */ |
5ea39eaa | 2265 | rt_notify_basic(c, n, e, e, c->refeeding); |
23ac9e9a OZ |
2266 | rte_update_unlock(); |
2267 | } | |
2268 | ||
58740ed4 | 2269 | /** |
f4a60a9b OZ |
2270 | * rt_feed_channel - advertise all routes to a channel |
2271 | * @c: channel to be fed | |
58740ed4 | 2272 | * |
f4a60a9b OZ |
2273 | * This function performs one pass of advertisement of routes to a channel that |
2274 | * is in the ES_FEEDING state. It is called by the protocol code as long as it | |
2275 | * has something to do. (We avoid transferring all the routes in single pass in | |
2276 | * order not to monopolize CPU time.) | |
58740ed4 | 2277 | */ |
ac5d8012 | 2278 | int |
f4a60a9b | 2279 | rt_feed_channel(struct channel *c) |
ac5d8012 | 2280 | { |
f4a60a9b | 2281 | struct fib_iterator *fit = &c->feed_fit; |
76dfda9e | 2282 | int max_feed = 256; |
ac5d8012 | 2283 | |
f4a60a9b OZ |
2284 | ASSERT(c->export_state == ES_FEEDING); |
2285 | ||
2286 | if (!c->feed_active) | |
ac5d8012 | 2287 | { |
f4a60a9b OZ |
2288 | FIB_ITERATE_INIT(fit, &c->table->fib); |
2289 | c->feed_active = 1; | |
ac5d8012 | 2290 | } |
ac5d8012 | 2291 | |
f4a60a9b | 2292 | FIB_ITERATE_START(&c->table->fib, fit, net, n) |
ac5d8012 | 2293 | { |
258d0ad4 | 2294 | rte *e = n->routes; |
76dfda9e MM |
2295 | if (max_feed <= 0) |
2296 | { | |
600998fc | 2297 | FIB_ITERATE_PUT(fit); |
76dfda9e MM |
2298 | return 0; |
2299 | } | |
23ac9e9a | 2300 | |
f4a60a9b OZ |
2301 | if ((c->ra_mode == RA_OPTIMAL) || |
2302 | (c->ra_mode == RA_ACCEPTED) || | |
2303 | (c->ra_mode == RA_MERGED)) | |
cf98be7b | 2304 | if (rte_is_valid(e)) |
23ac9e9a | 2305 | { |
f4a60a9b OZ |
2306 | /* In the meantime, the protocol may fell down */ |
2307 | if (c->export_state != ES_FEEDING) | |
2308 | goto done; | |
ca34698c | 2309 | |
f4a60a9b | 2310 | do_feed_channel(c, n, e); |
23ac9e9a OZ |
2311 | max_feed--; |
2312 | } | |
2313 | ||
f4a60a9b | 2314 | if (c->ra_mode == RA_ANY) |
ca34698c | 2315 | for(e = n->routes; e; e = e->next) |
23ac9e9a | 2316 | { |
f4a60a9b OZ |
2317 | /* In the meantime, the protocol may fell down */ |
2318 | if (c->export_state != ES_FEEDING) | |
2319 | goto done; | |
ca34698c OZ |
2320 | |
2321 | if (!rte_is_valid(e)) | |
2322 | continue; | |
2323 | ||
f4a60a9b | 2324 | do_feed_channel(c, n, e); |
23ac9e9a OZ |
2325 | max_feed--; |
2326 | } | |
ac5d8012 | 2327 | } |
600998fc | 2328 | FIB_ITERATE_END; |
ac5d8012 | 2329 | |
f4a60a9b OZ |
2330 | done: |
2331 | c->feed_active = 0; | |
2332 | return 1; | |
ac5d8012 MM |
2333 | } |
2334 | ||
58740ed4 MM |
2335 | /** |
2336 | * rt_feed_baby_abort - abort protocol feeding | |
f4a60a9b | 2337 | * @c: channel |
58740ed4 | 2338 | * |
f4a60a9b OZ |
2339 | * This function is called by the protocol code when the protocol stops or |
2340 | * ceases to exist during the feeding. | |
58740ed4 | 2341 | */ |
ac5d8012 | 2342 | void |
f4a60a9b | 2343 | rt_feed_channel_abort(struct channel *c) |
ac5d8012 | 2344 | { |
f4a60a9b | 2345 | if (c->feed_active) |
ac5d8012 | 2346 | { |
f4a60a9b OZ |
2347 | /* Unlink the iterator */ |
2348 | fit_get(&c->table->fib, &c->feed_fit); | |
2349 | c->feed_active = 0; | |
ac5d8012 MM |
2350 | } |
2351 | } | |
2352 | ||
682d3f7d | 2353 | |
b7d7599c OZ |
2354 | /* |
2355 | * Import table | |
2356 | */ | |
2357 | ||
682d3f7d OZ |
2358 | int |
2359 | rte_update_in(struct channel *c, const net_addr *n, rte *new, struct rte_src *src) | |
2360 | { | |
67d8665a | 2361 | struct rtable *tab = c->in_table; |
682d3f7d OZ |
2362 | rte *old, **pos; |
2363 | net *net; | |
2364 | ||
2365 | if (new) | |
2366 | { | |
67d8665a | 2367 | net = net_get(tab, n); |
682d3f7d | 2368 | |
682d3f7d OZ |
2369 | if (!rta_is_cached(new->attrs)) |
2370 | new->attrs = rta_lookup(new->attrs); | |
2371 | } | |
2372 | else | |
2373 | { | |
67d8665a | 2374 | net = net_find(tab, n); |
682d3f7d OZ |
2375 | |
2376 | if (!net) | |
67d8665a | 2377 | goto drop_withdraw; |
682d3f7d OZ |
2378 | } |
2379 | ||
2380 | /* Find the old rte */ | |
2381 | for (pos = &net->routes; old = *pos; pos = &old->next) | |
5cff1d5f | 2382 | if (old->src == src) |
682d3f7d OZ |
2383 | { |
2384 | if (new && rte_same(old, new)) | |
93af78d2 OZ |
2385 | { |
2386 | /* Refresh the old rte, continue with update to main rtable */ | |
2387 | if (old->flags & (REF_STALE | REF_DISCARD | REF_MODIFY)) | |
2388 | { | |
2389 | old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY); | |
2390 | return 1; | |
2391 | } | |
2392 | ||
67d8665a | 2393 | goto drop_update; |
93af78d2 | 2394 | } |
682d3f7d | 2395 | |
32a25405 MM |
2396 | /* Move iterator if needed */ |
2397 | if (old == c->reload_next_rte) | |
2398 | c->reload_next_rte = old->next; | |
2399 | ||
682d3f7d OZ |
2400 | /* Remove the old rte */ |
2401 | *pos = old->next; | |
2402 | rte_free_quick(old); | |
67d8665a | 2403 | tab->rt_count--; |
682d3f7d OZ |
2404 | |
2405 | break; | |
2406 | } | |
2407 | ||
2408 | if (!new) | |
67d8665a OZ |
2409 | { |
2410 | if (!old) | |
2411 | goto drop_withdraw; | |
2412 | ||
ff397df7 MM |
2413 | if (!net->routes) |
2414 | fib_delete(&tab->fib, net); | |
2415 | ||
67d8665a OZ |
2416 | return 1; |
2417 | } | |
2418 | ||
2419 | struct channel_limit *l = &c->rx_limit; | |
2420 | if (l->action && !old) | |
2421 | { | |
2422 | if (tab->rt_count >= l->limit) | |
2423 | channel_notify_limit(c, l, PLD_RX, tab->rt_count); | |
2424 | ||
2425 | if (l->state == PLS_BLOCKED) | |
2426 | { | |
b962967e OZ |
2427 | /* Required by rte_trace_in() */ |
2428 | new->net = net; | |
2429 | ||
61dae32b | 2430 | rte_trace_in(D_FILTERS, c, new, "ignored [limit]"); |
67d8665a OZ |
2431 | goto drop_update; |
2432 | } | |
2433 | } | |
682d3f7d OZ |
2434 | |
2435 | /* Insert the new rte */ | |
2436 | rte *e = rte_do_cow(new); | |
2437 | e->flags |= REF_COW; | |
2438 | e->net = net; | |
2439 | e->sender = c; | |
2440 | e->lastmod = current_time(); | |
2441 | e->next = *pos; | |
2442 | *pos = e; | |
67d8665a | 2443 | tab->rt_count++; |
682d3f7d | 2444 | return 1; |
67d8665a OZ |
2445 | |
2446 | drop_update: | |
2447 | c->stats.imp_updates_received++; | |
2448 | c->stats.imp_updates_ignored++; | |
2449 | rte_free(new); | |
ff397df7 MM |
2450 | |
2451 | if (!net->routes) | |
2452 | fib_delete(&tab->fib, net); | |
2453 | ||
67d8665a OZ |
2454 | return 0; |
2455 | ||
2456 | drop_withdraw: | |
2457 | c->stats.imp_withdraws_received++; | |
2458 | c->stats.imp_withdraws_ignored++; | |
2459 | return 0; | |
682d3f7d OZ |
2460 | } |
2461 | ||
2462 | int | |
2463 | rt_reload_channel(struct channel *c) | |
2464 | { | |
2465 | struct rtable *tab = c->in_table; | |
2466 | struct fib_iterator *fit = &c->reload_fit; | |
2467 | int max_feed = 64; | |
2468 | ||
2469 | ASSERT(c->channel_state == CS_UP); | |
2470 | ||
2471 | if (!c->reload_active) | |
2472 | { | |
2473 | FIB_ITERATE_INIT(fit, &tab->fib); | |
2474 | c->reload_active = 1; | |
2475 | } | |
2476 | ||
32a25405 MM |
2477 | do { |
2478 | for (rte *e = c->reload_next_rte; e; e = e->next) | |
682d3f7d | 2479 | { |
32a25405 MM |
2480 | if (max_feed-- <= 0) |
2481 | { | |
2482 | c->reload_next_rte = e; | |
2483 | debug("%s channel reload burst split (max_feed=%d)", c->proto->name, max_feed); | |
2484 | return 0; | |
2485 | } | |
2486 | ||
5cff1d5f | 2487 | rte_update2(c, e->net->n.addr, rte_do_cow(e), e->src); |
682d3f7d OZ |
2488 | } |
2489 | ||
32a25405 MM |
2490 | c->reload_next_rte = NULL; |
2491 | ||
2492 | FIB_ITERATE_START(&tab->fib, fit, net, n) | |
682d3f7d | 2493 | { |
32a25405 MM |
2494 | if (c->reload_next_rte = n->routes) |
2495 | { | |
2496 | FIB_ITERATE_PUT_NEXT(fit, &tab->fib); | |
2497 | break; | |
2498 | } | |
682d3f7d | 2499 | } |
32a25405 | 2500 | FIB_ITERATE_END; |
682d3f7d | 2501 | } |
32a25405 | 2502 | while (c->reload_next_rte); |
682d3f7d OZ |
2503 | |
2504 | c->reload_active = 0; | |
2505 | return 1; | |
2506 | } | |
2507 | ||
2508 | void | |
2509 | rt_reload_channel_abort(struct channel *c) | |
2510 | { | |
2511 | if (c->reload_active) | |
2512 | { | |
2513 | /* Unlink the iterator */ | |
2514 | fit_get(&c->in_table->fib, &c->reload_fit); | |
32a25405 | 2515 | c->reload_next_rte = NULL; |
682d3f7d OZ |
2516 | c->reload_active = 0; |
2517 | } | |
2518 | } | |
2519 | ||
2520 | void | |
2521 | rt_prune_sync(rtable *t, int all) | |
2522 | { | |
ff397df7 MM |
2523 | struct fib_iterator fit; |
2524 | ||
2525 | FIB_ITERATE_INIT(&fit, &t->fib); | |
2526 | ||
2527 | again: | |
2528 | FIB_ITERATE_START(&t->fib, &fit, net, n) | |
682d3f7d OZ |
2529 | { |
2530 | rte *e, **ee = &n->routes; | |
ff397df7 | 2531 | |
682d3f7d OZ |
2532 | while (e = *ee) |
2533 | { | |
2534 | if (all || (e->flags & (REF_STALE | REF_DISCARD))) | |
2535 | { | |
2536 | *ee = e->next; | |
2537 | rte_free_quick(e); | |
67d8665a | 2538 | t->rt_count--; |
682d3f7d OZ |
2539 | } |
2540 | else | |
2541 | ee = &e->next; | |
2542 | } | |
ff397df7 MM |
2543 | |
2544 | if (all || !n->routes) | |
2545 | { | |
2546 | FIB_ITERATE_PUT(&fit); | |
2547 | fib_delete(&t->fib, n); | |
2548 | goto again; | |
2549 | } | |
682d3f7d | 2550 | } |
ff397df7 | 2551 | FIB_ITERATE_END; |
682d3f7d OZ |
2552 | } |
2553 | ||
2554 | ||
b7d7599c OZ |
2555 | /* |
2556 | * Export table | |
2557 | */ | |
2558 | ||
2559 | int | |
cee0cd14 | 2560 | rte_update_out(struct channel *c, const net_addr *n, rte *new, rte *old0, rte **old_exported, int refeed) |
b7d7599c OZ |
2561 | { |
2562 | struct rtable *tab = c->out_table; | |
2563 | struct rte_src *src; | |
2564 | rte *old, **pos; | |
2565 | net *net; | |
2566 | ||
2567 | if (new) | |
2568 | { | |
2569 | net = net_get(tab, n); | |
5cff1d5f | 2570 | src = new->src; |
ca2dacfc | 2571 | |
ca2dacfc OZ |
2572 | if (!rta_is_cached(new->attrs)) |
2573 | new->attrs = rta_lookup(new->attrs); | |
b7d7599c OZ |
2574 | } |
2575 | else | |
2576 | { | |
2577 | net = net_find(tab, n); | |
5cff1d5f | 2578 | src = old0->src; |
b7d7599c OZ |
2579 | |
2580 | if (!net) | |
2581 | goto drop_withdraw; | |
2582 | } | |
2583 | ||
2584 | /* Find the old rte */ | |
2585 | for (pos = &net->routes; old = *pos; pos = &old->next) | |
5cff1d5f | 2586 | if ((c->ra_mode != RA_ANY) || (old->src == src)) |
b7d7599c OZ |
2587 | { |
2588 | if (new && rte_same(old, new)) | |
2589 | { | |
2590 | /* REF_STALE / REF_DISCARD not used in export table */ | |
2591 | /* | |
2592 | if (old->flags & (REF_STALE | REF_DISCARD | REF_MODIFY)) | |
2593 | { | |
2594 | old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY); | |
2595 | return 1; | |
2596 | } | |
2597 | */ | |
2598 | ||
2599 | goto drop_update; | |
2600 | } | |
2601 | ||
2602 | /* Remove the old rte */ | |
2603 | *pos = old->next; | |
cee0cd14 | 2604 | *old_exported = old; |
b7d7599c OZ |
2605 | tab->rt_count--; |
2606 | ||
2607 | break; | |
2608 | } | |
2609 | ||
2610 | if (!new) | |
2611 | { | |
2612 | if (!old) | |
2613 | goto drop_withdraw; | |
2614 | ||
ff397df7 MM |
2615 | if (!net->routes) |
2616 | fib_delete(&tab->fib, net); | |
2617 | ||
b7d7599c OZ |
2618 | return 1; |
2619 | } | |
2620 | ||
2621 | /* Insert the new rte */ | |
2622 | rte *e = rte_do_cow(new); | |
2623 | e->flags |= REF_COW; | |
2624 | e->net = net; | |
2625 | e->sender = c; | |
2626 | e->lastmod = current_time(); | |
2627 | e->next = *pos; | |
2628 | *pos = e; | |
2629 | tab->rt_count++; | |
2630 | return 1; | |
2631 | ||
2632 | drop_update: | |
2633 | return refeed; | |
2634 | ||
2635 | drop_withdraw: | |
2636 | return 0; | |
2637 | } | |
2638 | ||
2639 | ||
2640 | /* | |
2641 | * Hostcache | |
2642 | */ | |
2643 | ||
04632fd7 | 2644 | static inline u32 |
f2b76f2c OZ |
2645 | hc_hash(ip_addr a, rtable *dep) |
2646 | { | |
04632fd7 | 2647 | return ipa_hash(a) ^ ptr_hash(dep); |
f2b76f2c OZ |
2648 | } |
2649 | ||
2650 | static inline void | |
2651 | hc_insert(struct hostcache *hc, struct hostentry *he) | |
2652 | { | |
ae80a2de | 2653 | uint k = he->hash_key >> hc->hash_shift; |
f2b76f2c OZ |
2654 | he->next = hc->hash_table[k]; |
2655 | hc->hash_table[k] = he; | |
2656 | } | |
2657 | ||
2658 | static inline void | |
2659 | hc_remove(struct hostcache *hc, struct hostentry *he) | |
2660 | { | |
2661 | struct hostentry **hep; | |
ae80a2de | 2662 | uint k = he->hash_key >> hc->hash_shift; |
f2b76f2c OZ |
2663 | |
2664 | for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next); | |
2665 | *hep = he->next; | |
2666 | } | |
2667 | ||
2668 | #define HC_DEF_ORDER 10 | |
2669 | #define HC_HI_MARK *4 | |
2670 | #define HC_HI_STEP 2 | |
2671 | #define HC_HI_ORDER 16 /* Must be at most 16 */ | |
2672 | #define HC_LO_MARK /5 | |
2673 | #define HC_LO_STEP 2 | |
2674 | #define HC_LO_ORDER 10 | |
2675 | ||
2676 | static void | |
ff397df7 | 2677 | hc_alloc_table(struct hostcache *hc, pool *p, unsigned order) |
f2b76f2c | 2678 | { |
3e236955 | 2679 | uint hsize = 1 << order; |
f2b76f2c | 2680 | hc->hash_order = order; |
04632fd7 | 2681 | hc->hash_shift = 32 - order; |
3e236955 JMM |
2682 | hc->hash_max = (order >= HC_HI_ORDER) ? ~0U : (hsize HC_HI_MARK); |
2683 | hc->hash_min = (order <= HC_LO_ORDER) ? 0U : (hsize HC_LO_MARK); | |
f2b76f2c | 2684 | |
ff397df7 | 2685 | hc->hash_table = mb_allocz(p, hsize * sizeof(struct hostentry *)); |
f2b76f2c OZ |
2686 | } |
2687 | ||
cfe34a31 | 2688 | static void |
ff397df7 | 2689 | hc_resize(struct hostcache *hc, pool *p, unsigned new_order) |
cfe34a31 | 2690 | { |
f2b76f2c OZ |
2691 | struct hostentry **old_table = hc->hash_table; |
2692 | struct hostentry *he, *hen; | |
3e236955 JMM |
2693 | uint old_size = 1 << hc->hash_order; |
2694 | uint i; | |
f2b76f2c | 2695 | |
ff397df7 | 2696 | hc_alloc_table(hc, p, new_order); |
f2b76f2c OZ |
2697 | for (i = 0; i < old_size; i++) |
2698 | for (he = old_table[i]; he != NULL; he=hen) | |
2699 | { | |
2700 | hen = he->next; | |
2701 | hc_insert(hc, he); | |
2702 | } | |
2703 | mb_free(old_table); | |
2704 | } | |
2705 | ||
2706 | static struct hostentry * | |
ff397df7 | 2707 | hc_new_hostentry(struct hostcache *hc, pool *p, ip_addr a, ip_addr ll, rtable *dep, unsigned k) |
f2b76f2c OZ |
2708 | { |
2709 | struct hostentry *he = sl_alloc(hc->slab); | |
2710 | ||
039a65d0 JMM |
2711 | *he = (struct hostentry) { |
2712 | .addr = a, | |
2713 | .link = ll, | |
2714 | .tab = dep, | |
2715 | .hash_key = k, | |
2716 | }; | |
f2b76f2c OZ |
2717 | |
2718 | add_tail(&hc->hostentries, &he->ln); | |
2719 | hc_insert(hc, he); | |
2720 | ||
2721 | hc->hash_items++; | |
2722 | if (hc->hash_items > hc->hash_max) | |
ff397df7 | 2723 | hc_resize(hc, p, hc->hash_order + HC_HI_STEP); |
f2b76f2c OZ |
2724 | |
2725 | return he; | |
2726 | } | |
2727 | ||
2728 | static void | |
ff397df7 | 2729 | hc_delete_hostentry(struct hostcache *hc, pool *p, struct hostentry *he) |
f2b76f2c | 2730 | { |
7e95c05d OZ |
2731 | rta_free(he->src); |
2732 | ||
f2b76f2c OZ |
2733 | rem_node(&he->ln); |
2734 | hc_remove(hc, he); | |
2735 | sl_free(hc->slab, he); | |
2736 | ||
2737 | hc->hash_items--; | |
2738 | if (hc->hash_items < hc->hash_min) | |
ff397df7 | 2739 | hc_resize(hc, p, hc->hash_order - HC_LO_STEP); |
cfe34a31 OZ |
2740 | } |
2741 | ||
2742 | static void | |
2743 | rt_init_hostcache(rtable *tab) | |
2744 | { | |
ff397df7 | 2745 | struct hostcache *hc = mb_allocz(tab->rp, sizeof(struct hostcache)); |
cfe34a31 | 2746 | init_list(&hc->hostentries); |
f2b76f2c OZ |
2747 | |
2748 | hc->hash_items = 0; | |
ff397df7 MM |
2749 | hc_alloc_table(hc, tab->rp, HC_DEF_ORDER); |
2750 | hc->slab = sl_new(tab->rp, sizeof(struct hostentry)); | |
f2b76f2c | 2751 | |
ff397df7 | 2752 | hc->lp = lp_new(tab->rp, LP_GOOD_SIZE(1024)); |
27550028 | 2753 | hc->trie = f_new_trie(hc->lp, 0); |
c477f489 | 2754 | |
cfe34a31 OZ |
2755 | tab->hostcache = hc; |
2756 | } | |
2757 | ||
2758 | static void | |
2759 | rt_free_hostcache(rtable *tab) | |
2760 | { | |
2761 | struct hostcache *hc = tab->hostcache; | |
2762 | ||
2763 | node *n; | |
2764 | WALK_LIST(n, hc->hostentries) | |
2765 | { | |
2766 | struct hostentry *he = SKIP_BACK(struct hostentry, ln, n); | |
7e95c05d OZ |
2767 | rta_free(he->src); |
2768 | ||
cfe34a31 OZ |
2769 | if (he->uc) |
2770 | log(L_ERR "Hostcache is not empty in table %s", tab->name); | |
2771 | } | |
2772 | ||
ff397df7 | 2773 | /* Freed automagically by the resource pool |
f2b76f2c | 2774 | rfree(hc->slab); |
c477f489 | 2775 | rfree(hc->lp); |
f2b76f2c | 2776 | mb_free(hc->hash_table); |
cfe34a31 | 2777 | mb_free(hc); |
ff397df7 | 2778 | */ |
cfe34a31 OZ |
2779 | } |
2780 | ||
2781 | static void | |
2782 | rt_notify_hostcache(rtable *tab, net *net) | |
2783 | { | |
cfe34a31 OZ |
2784 | if (tab->hcu_scheduled) |
2785 | return; | |
2786 | ||
04632fd7 OZ |
2787 | if (trie_match_net(tab->hostcache->trie, net->n.addr)) |
2788 | rt_schedule_hcu(tab); | |
cfe34a31 OZ |
2789 | } |
2790 | ||
2791 | static int | |
2792 | if_local_addr(ip_addr a, struct iface *i) | |
2793 | { | |
2794 | struct ifa *b; | |
2795 | ||
2796 | WALK_LIST(b, i->addrs) | |
2797 | if (ipa_equal(a, b->ip)) | |
2798 | return 1; | |
2799 | ||
2800 | return 0; | |
2801 | } | |
2802 | ||
09ee846d | 2803 | u32 |
d1e146f2 OZ |
2804 | rt_get_igp_metric(rte *rt) |
2805 | { | |
ba5e5940 OZ |
2806 | eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC); |
2807 | ||
2808 | if (ea) | |
2809 | return ea->u.data; | |
2810 | ||
d471d5fc | 2811 | if (rt->attrs->source == RTS_DEVICE) |
d1e146f2 OZ |
2812 | return 0; |
2813 | ||
d471d5fc MM |
2814 | if (rt->src->proto->rte_igp_metric) |
2815 | return rt->src->proto->rte_igp_metric(rt); | |
2816 | ||
d1e146f2 OZ |
2817 | return IGP_METRIC_UNKNOWN; |
2818 | } | |
2819 | ||
cfe34a31 OZ |
2820 | static int |
2821 | rt_update_hostentry(rtable *tab, struct hostentry *he) | |
2822 | { | |
7e95c05d | 2823 | rta *old_src = he->src; |
85ad5855 | 2824 | int direct = 0; |
c477f489 | 2825 | int pxlen = 0; |
cfe34a31 | 2826 | |
04632fd7 | 2827 | /* Reset the hostentry */ |
7e95c05d | 2828 | he->src = NULL; |
7e95c05d | 2829 | he->dest = RTD_UNREACHABLE; |
85ad5855 | 2830 | he->nexthop_linkable = 0; |
7e95c05d OZ |
2831 | he->igp_metric = 0; |
2832 | ||
04632fd7 OZ |
2833 | net_addr he_addr; |
2834 | net_fill_ip_host(&he_addr, he->addr); | |
2835 | net *n = net_route(tab, &he_addr); | |
d1e146f2 | 2836 | if (n) |
cfe34a31 | 2837 | { |
cf98be7b OZ |
2838 | rte *e = n->routes; |
2839 | rta *a = e->attrs; | |
fe9f1a6d | 2840 | pxlen = n->n.addr->pxlen; |
cfe34a31 | 2841 | |
2c9033af OZ |
2842 | if (a->hostentry) |
2843 | { | |
2844 | /* Recursive route should not depend on another recursive route */ | |
fe9f1a6d OZ |
2845 | log(L_WARN "Next hop address %I resolvable through recursive route for %N", |
2846 | he->addr, n->n.addr); | |
7e95c05d | 2847 | goto done; |
2c9033af | 2848 | } |
7e95c05d | 2849 | |
85ad5855 | 2850 | if (a->dest == RTD_UNICAST) |
3c744164 JMM |
2851 | { |
2852 | for (struct nexthop *nh = &(a->nh); nh; nh = nh->next) | |
2853 | if (ipa_zero(nh->gw)) | |
2854 | { | |
2855 | if (if_local_addr(he->addr, nh->iface)) | |
2856 | { | |
2857 | /* The host address is a local address, this is not valid */ | |
2858 | log(L_WARN "Next hop address %I is a local address of iface %s", | |
2859 | he->addr, nh->iface->name); | |
2860 | goto done; | |
2861 | } | |
2862 | ||
85ad5855 | 2863 | direct++; |
3c744164 JMM |
2864 | } |
2865 | } | |
665be7f6 | 2866 | |
7e95c05d | 2867 | he->src = rta_clone(a); |
85ad5855 OZ |
2868 | he->dest = a->dest; |
2869 | he->nexthop_linkable = !direct; | |
cf98be7b | 2870 | he->igp_metric = rt_get_igp_metric(e); |
cfe34a31 OZ |
2871 | } |
2872 | ||
665be7f6 | 2873 | done: |
c477f489 | 2874 | /* Add a prefix range to the trie */ |
04632fd7 | 2875 | trie_add_prefix(tab->hostcache->trie, &he_addr, pxlen, he_addr.pxlen); |
c477f489 | 2876 | |
7e95c05d OZ |
2877 | rta_free(old_src); |
2878 | return old_src != he->src; | |
cfe34a31 OZ |
2879 | } |
2880 | ||
2881 | static void | |
2882 | rt_update_hostcache(rtable *tab) | |
2883 | { | |
2884 | struct hostcache *hc = tab->hostcache; | |
2885 | struct hostentry *he; | |
2886 | node *n, *x; | |
2887 | ||
c477f489 OZ |
2888 | /* Reset the trie */ |
2889 | lp_flush(hc->lp); | |
27550028 | 2890 | hc->trie = f_new_trie(hc->lp, 0); |
c477f489 | 2891 | |
cfe34a31 OZ |
2892 | WALK_LIST_DELSAFE(n, x, hc->hostentries) |
2893 | { | |
2894 | he = SKIP_BACK(struct hostentry, ln, n); | |
2895 | if (!he->uc) | |
2896 | { | |
ff397df7 | 2897 | hc_delete_hostentry(hc, tab->rp, he); |
cfe34a31 OZ |
2898 | continue; |
2899 | } | |
2900 | ||
2901 | if (rt_update_hostentry(tab, he)) | |
2902 | rt_schedule_nhu(he->tab); | |
2903 | } | |
2904 | ||
2905 | tab->hcu_scheduled = 0; | |
2906 | } | |
2907 | ||
1e37e35c | 2908 | struct hostentry * |
094d2bdb | 2909 | rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep) |
cfe34a31 OZ |
2910 | { |
2911 | struct hostentry *he; | |
2912 | ||
2913 | if (!tab->hostcache) | |
2914 | rt_init_hostcache(tab); | |
2915 | ||
04632fd7 | 2916 | u32 k = hc_hash(a, dep); |
f2b76f2c OZ |
2917 | struct hostcache *hc = tab->hostcache; |
2918 | for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next) | |
2919 | if (ipa_equal(he->addr, a) && (he->tab == dep)) | |
2920 | return he; | |
cfe34a31 | 2921 | |
ff397df7 | 2922 | he = hc_new_hostentry(hc, tab->rp, a, ipa_zero(ll) ? a : ll, dep, k); |
f2b76f2c | 2923 | rt_update_hostentry(tab, he); |
cfe34a31 OZ |
2924 | return he; |
2925 | } | |
2926 | ||
094d2bdb | 2927 | |
3ce8c610 MM |
2928 | /* |
2929 | * Documentation for functions declared inline in route.h | |
2930 | */ | |
2931 | #if 0 | |
2932 | ||
2933 | /** | |
2934 | * net_find - find a network entry | |
2935 | * @tab: a routing table | |
2936 | * @addr: address of the network | |
3ce8c610 MM |
2937 | * |
2938 | * net_find() looks up the given network in routing table @tab and | |
2939 | * returns a pointer to its &net entry or %NULL if no such network | |
2940 | * exists. | |
2941 | */ | |
fe9f1a6d | 2942 | static inline net *net_find(rtable *tab, net_addr *addr) |
3ce8c610 MM |
2943 | { DUMMY; } |
2944 | ||
2945 | /** | |
2946 | * net_get - obtain a network entry | |
2947 | * @tab: a routing table | |
2948 | * @addr: address of the network | |
3ce8c610 MM |
2949 | * |
2950 | * net_get() looks up the given network in routing table @tab and | |
2951 | * returns a pointer to its &net entry. If no such entry exists, it's | |
2952 | * created. | |
2953 | */ | |
fe9f1a6d | 2954 | static inline net *net_get(rtable *tab, net_addr *addr) |
3ce8c610 MM |
2955 | { DUMMY; } |
2956 | ||
2957 | /** | |
2958 | * rte_cow - copy a route for writing | |
2959 | * @r: a route entry to be copied | |
2960 | * | |
2961 | * rte_cow() takes a &rte and prepares it for modification. The exact action | |
2962 | * taken depends on the flags of the &rte -- if it's a temporary entry, it's | |
2963 | * just returned unchanged, else a new temporary entry with the same contents | |
2964 | * is created. | |
2965 | * | |
2966 | * The primary use of this function is inside the filter machinery -- when | |
2967 | * a filter wants to modify &rte contents (to change the preference or to | |
2968 | * attach another set of attributes), it must ensure that the &rte is not | |
2969 | * shared with anyone else (and especially that it isn't stored in any routing | |
2970 | * table). | |
2971 | * | |
2e9b2421 | 2972 | * Result: a pointer to the new writable &rte. |
3ce8c610 MM |
2973 | */ |
2974 | static inline rte * rte_cow(rte *r) | |
2975 | { DUMMY; } | |
2976 | ||
2977 | #endif |