]>
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 MM |
36 | #include "nest/cli.h" |
37 | #include "nest/iface.h" | |
2326b001 | 38 | #include "lib/resource.h" |
5996da6a | 39 | #include "lib/event.h" |
730f2e2c | 40 | #include "lib/string.h" |
0e02abfd | 41 | #include "conf/conf.h" |
529c4149 | 42 | #include "filter/filter.h" |
221135d6 | 43 | #include "lib/string.h" |
10af3676 | 44 | #include "lib/alloca.h" |
7d875e09 | 45 | |
acb60628 OZ |
46 | pool *rt_table_pool; |
47 | ||
2326b001 | 48 | static slab *rte_slab; |
e2dc2f30 | 49 | static linpool *rte_update_pool; |
2326b001 | 50 | |
0e02abfd | 51 | static list routing_tables; |
5996da6a | 52 | |
cfd46ee4 | 53 | static void rt_format_via(rte *e, byte *via); |
cfe34a31 OZ |
54 | static void rt_free_hostcache(rtable *tab); |
55 | static void rt_notify_hostcache(rtable *tab, net *net); | |
56 | static void rt_update_hostcache(rtable *tab); | |
57 | static void rt_next_hop_update(rtable *tab); | |
0c791f87 | 58 | static inline int rt_prune_table(rtable *tab); |
cfe34a31 | 59 | static inline void rt_schedule_gc(rtable *tab); |
0c791f87 OZ |
60 | static inline void rt_schedule_prune(rtable *tab); |
61 | ||
cfd46ee4 | 62 | |
094d2bdb OZ |
63 | static inline struct ea_list * |
64 | make_tmp_attrs(struct rte *rt, struct linpool *pool) | |
65 | { | |
66 | struct ea_list *(*mta)(struct rte *rt, struct linpool *pool); | |
67 | mta = rt->attrs->src->proto->make_tmp_attrs; | |
68 | return mta ? mta(rt, rte_update_pool) : NULL; | |
69 | } | |
70 | ||
d1e146f2 OZ |
71 | /* Like fib_route(), but skips empty net entries */ |
72 | static net * | |
73 | net_route(rtable *tab, ip_addr a, int len) | |
74 | { | |
75 | ip_addr a0; | |
76 | net *n; | |
77 | ||
78 | while (len >= 0) | |
79 | { | |
80 | a0 = ipa_and(a, ipa_mkmask(len)); | |
81 | n = fib_find(&tab->fib, &a0, len); | |
cf98be7b | 82 | if (n && rte_is_valid(n->routes)) |
d1e146f2 OZ |
83 | return n; |
84 | len--; | |
85 | } | |
86 | return NULL; | |
87 | } | |
88 | ||
5996da6a | 89 | static void |
2326b001 MM |
90 | rte_init(struct fib_node *N) |
91 | { | |
92 | net *n = (net *) N; | |
93 | ||
4c45595e | 94 | N->flags = 0; |
2326b001 MM |
95 | n->routes = NULL; |
96 | } | |
97 | ||
58740ed4 MM |
98 | /** |
99 | * rte_find - find a route | |
100 | * @net: network node | |
094d2bdb | 101 | * @src: route source |
58740ed4 MM |
102 | * |
103 | * The rte_find() function returns a route for destination @net | |
094d2bdb | 104 | * which is from route source @src. |
58740ed4 | 105 | */ |
2326b001 | 106 | rte * |
094d2bdb | 107 | rte_find(net *net, struct rte_src *src) |
2326b001 MM |
108 | { |
109 | rte *e = net->routes; | |
110 | ||
094d2bdb | 111 | while (e && e->attrs->src != src) |
2326b001 MM |
112 | e = e->next; |
113 | return e; | |
114 | } | |
115 | ||
58740ed4 MM |
116 | /** |
117 | * rte_get_temp - get a temporary &rte | |
3ce8c610 | 118 | * @a: attributes to assign to the new route (a &rta; in case it's |
2e9b2421 | 119 | * un-cached, rte_update() will create a cached copy automatically) |
58740ed4 MM |
120 | * |
121 | * Create a temporary &rte and bind it with the attributes @a. | |
122 | * Also set route preference to the default preference set for | |
123 | * the protocol. | |
124 | */ | |
2326b001 MM |
125 | rte * |
126 | rte_get_temp(rta *a) | |
127 | { | |
128 | rte *e = sl_alloc(rte_slab); | |
129 | ||
130 | e->attrs = a; | |
0cdbd397 | 131 | e->flags = 0; |
094d2bdb | 132 | e->pref = a->src->proto->preference; |
2326b001 MM |
133 | return e; |
134 | } | |
135 | ||
e2dc2f30 MM |
136 | rte * |
137 | rte_do_cow(rte *r) | |
138 | { | |
139 | rte *e = sl_alloc(rte_slab); | |
140 | ||
141 | memcpy(e, r, sizeof(rte)); | |
142 | e->attrs = rta_clone(r->attrs); | |
143 | e->flags = 0; | |
144 | return e; | |
145 | } | |
146 | ||
2326b001 MM |
147 | static int /* Actually better or at least as good as */ |
148 | rte_better(rte *new, rte *old) | |
149 | { | |
d9f330c5 MM |
150 | int (*better)(rte *, rte *); |
151 | ||
cf98be7b | 152 | if (!rte_is_valid(old)) |
2326b001 | 153 | return 1; |
cf98be7b OZ |
154 | if (!rte_is_valid(new)) |
155 | return 0; | |
156 | ||
2326b001 MM |
157 | if (new->pref > old->pref) |
158 | return 1; | |
159 | if (new->pref < old->pref) | |
160 | return 0; | |
094d2bdb | 161 | if (new->attrs->src->proto->proto != old->attrs->src->proto->proto) |
4c1b4e1a MM |
162 | { |
163 | /* | |
164 | * If the user has configured protocol preferences, so that two different protocols | |
165 | * have the same preference, try to break the tie by comparing addresses. Not too | |
166 | * useful, but keeps the ordering of routes unambiguous. | |
167 | */ | |
094d2bdb | 168 | return new->attrs->src->proto->proto > old->attrs->src->proto->proto; |
4c1b4e1a | 169 | } |
094d2bdb | 170 | if (better = new->attrs->src->proto->rte_better) |
d9f330c5 MM |
171 | return better(new, old); |
172 | return 0; | |
2326b001 MM |
173 | } |
174 | ||
cfd46ee4 MM |
175 | static void |
176 | rte_trace(struct proto *p, rte *e, int dir, char *msg) | |
177 | { | |
178 | byte via[STD_ADDRESS_P_LENGTH+32]; | |
179 | ||
180 | rt_format_via(e, via); | |
181 | log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via); | |
182 | } | |
183 | ||
184 | static inline void | |
185 | rte_trace_in(unsigned int flag, struct proto *p, rte *e, char *msg) | |
186 | { | |
187 | if (p->debug & flag) | |
b0a47440 | 188 | rte_trace(p, e, '>', msg); |
cfd46ee4 MM |
189 | } |
190 | ||
191 | static inline void | |
192 | rte_trace_out(unsigned int flag, struct proto *p, rte *e, char *msg) | |
193 | { | |
194 | if (p->debug & flag) | |
b0a47440 | 195 | rte_trace(p, e, '<', msg); |
cfd46ee4 MM |
196 | } |
197 | ||
00a09f3c OZ |
198 | static rte * |
199 | export_filter(struct announce_hook *ah, rte *rt0, rte **rt_free, ea_list **tmpa, int silent) | |
529c4149 | 200 | { |
c0adf7e9 OZ |
201 | struct proto *p = ah->proto; |
202 | struct filter *filter = ah->out_filter; | |
203 | struct proto_stats *stats = ah->stats; | |
00a09f3c OZ |
204 | ea_list *tmpb = NULL; |
205 | rte *rt; | |
206 | int v; | |
c0adf7e9 | 207 | |
00a09f3c OZ |
208 | rt = rt0; |
209 | *rt_free = NULL; | |
7de45ba4 | 210 | |
00a09f3c OZ |
211 | /* If called does not care for eattrs, we prepare one internally */ |
212 | if (!tmpa) | |
529c4149 | 213 | { |
094d2bdb | 214 | tmpb = make_tmp_attrs(rt, rte_update_pool); |
00a09f3c | 215 | tmpa = &tmpb; |
529c4149 | 216 | } |
925fe2d3 | 217 | |
00a09f3c OZ |
218 | v = p->import_control ? p->import_control(p, &rt, tmpa, rte_update_pool) : 0; |
219 | if (v < 0) | |
220 | { | |
221 | if (silent) | |
222 | goto reject; | |
11361a10 | 223 | |
00a09f3c | 224 | stats->exp_updates_rejected++; |
36da2857 OZ |
225 | if (v == RIC_REJECT) |
226 | rte_trace_out(D_FILTERS, p, rt, "rejected by protocol"); | |
00a09f3c OZ |
227 | goto reject; |
228 | } | |
229 | if (v > 0) | |
e2dc2f30 | 230 | { |
00a09f3c OZ |
231 | if (!silent) |
232 | rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol"); | |
233 | goto accept; | |
e2dc2f30 | 234 | } |
925fe2d3 | 235 | |
00a09f3c OZ |
236 | v = filter && ((filter == FILTER_REJECT) || |
237 | (f_run(filter, &rt, tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)); | |
238 | if (v) | |
239 | { | |
240 | if (silent) | |
241 | goto reject; | |
242 | ||
243 | stats->exp_updates_filtered++; | |
244 | rte_trace_out(D_FILTERS, p, rt, "filtered out"); | |
245 | goto reject; | |
e2dc2f30 | 246 | } |
925fe2d3 | 247 | |
00a09f3c OZ |
248 | accept: |
249 | if (rt != rt0) | |
250 | *rt_free = rt; | |
251 | return rt; | |
252 | ||
253 | reject: | |
254 | /* Discard temporary rte */ | |
255 | if (rt != rt0) | |
256 | rte_free(rt); | |
257 | return NULL; | |
258 | } | |
259 | ||
260 | static void | |
261 | do_rt_notify(struct announce_hook *ah, net *net, rte *new, rte *old, ea_list *tmpa, int refeed) | |
262 | { | |
263 | struct proto *p = ah->proto; | |
264 | struct proto_stats *stats = ah->stats; | |
925fe2d3 | 265 | |
abced4a9 | 266 | |
ab758e4f | 267 | /* |
abced4a9 OZ |
268 | * First, apply export limit. |
269 | * | |
ab758e4f OZ |
270 | * Export route limits has several problems. Because exp_routes |
271 | * counter is reset before refeed, we don't really know whether | |
abced4a9 | 272 | * limit is breached and whether the update is new or not. Therefore |
ab758e4f OZ |
273 | * the number of really exported routes may exceed the limit |
274 | * temporarily (routes exported before and new routes in refeed). | |
275 | * | |
276 | * Minor advantage is that if the limit is decreased and refeed is | |
277 | * requested, the number of exported routes really decrease. | |
278 | * | |
279 | * Second problem is that with export limits, we don't know whether | |
280 | * old was really exported (it might be blocked by limit). When a | |
281 | * withdraw is exported, we announce it even when the previous | |
282 | * update was blocked. This is not a big issue, but the same problem | |
283 | * is in updating exp_routes counter. Therefore, to be consistent in | |
284 | * increases and decreases of exp_routes, we count exported routes | |
285 | * regardless of blocking by limits. | |
286 | * | |
287 | * Similar problem is in handling updates - when a new route is | |
288 | * received and blocking is active, the route would be blocked, but | |
289 | * when an update for the route will be received later, the update | |
290 | * would be propagated (as old != NULL). Therefore, we have to block | |
291 | * also non-new updates (contrary to import blocking). | |
292 | */ | |
925fe2d3 | 293 | |
d9b77cc2 | 294 | struct proto_limit *l = ah->out_limit; |
ab758e4f | 295 | if (l && new) |
d9b77cc2 | 296 | { |
ab758e4f | 297 | if ((!old || refeed) && (stats->exp_routes >= l->limit)) |
b662290f | 298 | proto_notify_limit(ah, l, PLD_OUT, stats->exp_routes); |
d9b77cc2 OZ |
299 | |
300 | if (l->state == PLS_BLOCKED) | |
301 | { | |
ab758e4f | 302 | stats->exp_routes++; /* see note above */ |
d9b77cc2 OZ |
303 | stats->exp_updates_rejected++; |
304 | rte_trace_out(D_FILTERS, p, new, "rejected [limit]"); | |
ab758e4f | 305 | new = NULL; |
abced4a9 OZ |
306 | |
307 | if (!old) | |
308 | return; | |
d9b77cc2 OZ |
309 | } |
310 | } | |
311 | ||
ab758e4f | 312 | |
925fe2d3 | 313 | if (new) |
9db74169 | 314 | stats->exp_updates_accepted++; |
925fe2d3 | 315 | else |
9db74169 | 316 | stats->exp_withdraws_accepted++; |
925fe2d3 | 317 | |
8a7fb885 OZ |
318 | /* Hack: We do not decrease exp_routes during refeed, we instead |
319 | reset exp_routes at the start of refeed. */ | |
925fe2d3 | 320 | if (new) |
9db74169 | 321 | stats->exp_routes++; |
8a7fb885 | 322 | if (old && !refeed) |
9db74169 | 323 | stats->exp_routes--; |
925fe2d3 | 324 | |
cfd46ee4 MM |
325 | if (p->debug & D_ROUTES) |
326 | { | |
327 | if (new && old) | |
328 | rte_trace_out(D_ROUTES, p, new, "replaced"); | |
329 | else if (new) | |
330 | rte_trace_out(D_ROUTES, p, new, "added"); | |
349e21bb | 331 | else if (old) |
cfd46ee4 MM |
332 | rte_trace_out(D_ROUTES, p, old, "removed"); |
333 | } | |
08f0290a | 334 | if (!new) |
c0adf7e9 | 335 | p->rt_notify(p, ah->table, net, NULL, old, NULL); |
08f0290a MM |
336 | else if (tmpa) |
337 | { | |
2f711231 MM |
338 | ea_list *t = tmpa; |
339 | while (t->next) | |
340 | t = t->next; | |
341 | t->next = new->attrs->eattrs; | |
c0adf7e9 | 342 | p->rt_notify(p, ah->table, net, new, old, tmpa); |
2f711231 | 343 | t->next = NULL; |
08f0290a MM |
344 | } |
345 | else | |
c0adf7e9 | 346 | p->rt_notify(p, ah->table, net, new, old, new->attrs->eattrs); |
00a09f3c OZ |
347 | } |
348 | ||
00a09f3c | 349 | static void |
86f567e1 | 350 | rt_notify_basic(struct announce_hook *ah, net *net, rte *new0, rte *old0, ea_list *tmpa, int refeed) |
00a09f3c | 351 | { |
86f567e1 | 352 | struct proto *p = ah->proto; |
00a09f3c OZ |
353 | struct proto_stats *stats = ah->stats; |
354 | ||
86f567e1 OZ |
355 | rte *new = new0; |
356 | rte *old = old0; | |
00a09f3c OZ |
357 | rte *new_free = NULL; |
358 | rte *old_free = NULL; | |
359 | ||
360 | if (new) | |
361 | stats->exp_updates_received++; | |
362 | else | |
363 | stats->exp_withdraws_received++; | |
364 | ||
365 | /* | |
366 | * This is a tricky part - we don't know whether route 'old' was | |
367 | * exported to protocol 'p' or was filtered by the export filter. | |
368 | * We try to run the export filter to know this to have a correct | |
369 | * value in 'old' argument of rte_update (and proper filter value) | |
370 | * | |
371 | * FIXME - this is broken because 'configure soft' may change | |
372 | * filters but keep routes. Refeed is expected to be called after | |
373 | * change of the filters and with old == new, therefore we do not | |
86f567e1 | 374 | * even try to run the filter on an old route, This may lead to |
00a09f3c OZ |
375 | * 'spurious withdraws' but ensure that there are no 'missing |
376 | * withdraws'. | |
377 | * | |
378 | * This is not completely safe as there is a window between | |
379 | * reconfiguration and the end of refeed - if a newly filtered | |
380 | * route disappears during this period, proper withdraw is not | |
381 | * sent (because old would be also filtered) and the route is | |
382 | * not refeeded (because it disappeared before that). | |
383 | */ | |
384 | ||
385 | if (new) | |
386 | new = export_filter(ah, new, &new_free, &tmpa, 0); | |
387 | ||
388 | if (old && !refeed) | |
389 | old = export_filter(ah, old, &old_free, NULL, 1); | |
390 | ||
00a09f3c | 391 | if (!new && !old) |
86f567e1 OZ |
392 | { |
393 | /* | |
394 | * As mentioned above, 'old' value may be incorrect in some race conditions. | |
395 | * We generally ignore it with the exception of withdraw to pipe protocol. | |
396 | * In that case we rather propagate unfiltered withdraws regardless of | |
397 | * export filters to ensure that when a protocol is flushed, its routes are | |
398 | * removed from all tables. Possible spurious unfiltered withdraws are not | |
399 | * problem here as they are ignored if there is no corresponding route at | |
400 | * the other end of the pipe. We directly call rt_notify() hook instead of | |
401 | * do_rt_notify() to avoid logging and stat counters. | |
402 | */ | |
403 | ||
404 | #ifdef CONFIG_PIPE | |
405 | if ((p->proto == &proto_pipe) && !new0 && (p != old0->sender->proto)) | |
406 | p->rt_notify(p, ah->table, net, NULL, old0, NULL); | |
407 | #endif | |
408 | ||
00a09f3c | 409 | return; |
86f567e1 | 410 | } |
00a09f3c OZ |
411 | |
412 | do_rt_notify(ah, net, new, old, tmpa, refeed); | |
413 | ||
414 | /* Discard temporary rte's */ | |
415 | if (new_free) | |
416 | rte_free(new_free); | |
417 | if (old_free) | |
418 | rte_free(old_free); | |
419 | } | |
420 | ||
421 | static void | |
422 | rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed, rte *before_old, | |
423 | ea_list *tmpa, int feed) | |
424 | { | |
425 | // struct proto *p = ah->proto; | |
426 | struct proto_stats *stats = ah->stats; | |
427 | ||
428 | rte *new_best = NULL; | |
429 | rte *old_best = NULL; | |
430 | rte *new_free = NULL; | |
431 | rte *old_free = NULL; | |
432 | rte *r; | |
433 | ||
cf98be7b OZ |
434 | /* Used to track whether we met old_changed position. If before_old is NULL |
435 | old_changed was the first and we met it implicitly before current best route. */ | |
436 | int old_meet = old_changed && !before_old; | |
437 | ||
438 | /* Note that before_old is either NULL or valid (not rejected) route. | |
439 | If old_changed is valid, before_old have to be too. If old changed route | |
440 | was not valid, caller must use NULL for both old_changed and before_old. */ | |
00a09f3c OZ |
441 | |
442 | if (new_changed) | |
443 | stats->exp_updates_received++; | |
444 | else | |
445 | stats->exp_withdraws_received++; | |
446 | ||
447 | /* First, find the new_best route - first accepted by filters */ | |
cf98be7b | 448 | for (r=net->routes; rte_is_valid(r); r=r->next) |
00a09f3c OZ |
449 | { |
450 | if (new_best = export_filter(ah, r, &new_free, &tmpa, 0)) | |
451 | break; | |
452 | ||
453 | /* Note if we walked around the position of old_changed route */ | |
454 | if (r == before_old) | |
455 | old_meet = 1; | |
456 | } | |
457 | ||
458 | /* | |
459 | * Second, handle the feed case. That means we do not care for | |
460 | * old_best. It is NULL for feed, and the new_best for refeed. | |
461 | * For refeed, there is a hack similar to one in rt_notify_basic() | |
462 | * to ensure withdraws in case of changed filters | |
463 | */ | |
464 | if (feed) | |
465 | { | |
466 | if (feed == 2) /* refeed */ | |
cf98be7b OZ |
467 | old_best = new_best ? new_best : |
468 | (rte_is_valid(net->routes) ? net->routes : NULL); | |
00a09f3c OZ |
469 | else |
470 | old_best = NULL; | |
471 | ||
472 | if (!new_best && !old_best) | |
473 | return; | |
474 | ||
475 | goto found; | |
476 | } | |
477 | ||
478 | /* | |
479 | * Now, we find the old_best route. Generally, it is the same as the | |
480 | * new_best, unless new_best is the same as new_changed or | |
481 | * old_changed is accepted before new_best. | |
482 | * | |
483 | * There are four cases: | |
484 | * | |
485 | * - We would find and accept old_changed before new_best, therefore | |
486 | * old_changed is old_best. In remaining cases we suppose this | |
487 | * is not true. | |
488 | * | |
489 | * - We found no new_best, therefore there is also no old_best and | |
490 | * we ignore this withdraw. | |
491 | * | |
492 | * - We found new_best different than new_changed, therefore | |
493 | * old_best is the same as new_best and we ignore this update. | |
494 | * | |
495 | * - We found new_best the same as new_changed, therefore it cannot | |
496 | * be old_best and we have to continue search for old_best. | |
497 | */ | |
498 | ||
499 | /* First case */ | |
500 | if (old_meet) | |
501 | if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1)) | |
502 | goto found; | |
503 | ||
504 | /* Second case */ | |
505 | if (!new_best) | |
506 | return; | |
d9b77cc2 | 507 | |
26822d8f | 508 | /* Third case, we use r instead of new_best, because export_filter() could change it */ |
00a09f3c OZ |
509 | if (r != new_changed) |
510 | { | |
511 | if (new_free) | |
512 | rte_free(new_free); | |
513 | return; | |
514 | } | |
515 | ||
516 | /* Fourth case */ | |
cf98be7b | 517 | for (r=r->next; rte_is_valid(r); r=r->next) |
00a09f3c OZ |
518 | { |
519 | if (old_best = export_filter(ah, r, &old_free, NULL, 1)) | |
520 | goto found; | |
521 | ||
522 | if (r == before_old) | |
523 | if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1)) | |
524 | goto found; | |
525 | } | |
526 | ||
527 | /* Implicitly, old_best is NULL and new_best is non-NULL */ | |
528 | ||
529 | found: | |
530 | do_rt_notify(ah, net, new_best, old_best, tmpa, (feed == 2)); | |
531 | ||
532 | /* Discard temporary rte's */ | |
533 | if (new_free) | |
534 | rte_free(new_free); | |
535 | if (old_free) | |
536 | rte_free(old_free); | |
529c4149 MM |
537 | } |
538 | ||
9a8f20fc MM |
539 | /** |
540 | * rte_announce - announce a routing table change | |
541 | * @tab: table the route has been added to | |
23ac9e9a | 542 | * @type: type of route announcement (RA_OPTIMAL or RA_ANY) |
9a8f20fc MM |
543 | * @net: network in question |
544 | * @new: the new route to be announced | |
23ac9e9a | 545 | * @old: the previous route for the same network |
9a8f20fc MM |
546 | * @tmpa: a list of temporary attributes belonging to the new route |
547 | * | |
548 | * This function gets a routing table update and announces it | |
f98e2915 OZ |
549 | * to all protocols that acccepts given type of route announcement |
550 | * and are connected to the same table by their announcement hooks. | |
9a8f20fc | 551 | * |
f98e2915 OZ |
552 | * Route announcement of type RA_OPTIMAL si generated when optimal |
553 | * route (in routing table @tab) changes. In that case @old stores the | |
554 | * old optimal route. | |
23ac9e9a | 555 | * |
f98e2915 OZ |
556 | * Route announcement of type RA_ANY si generated when any route (in |
557 | * routing table @tab) changes In that case @old stores the old route | |
558 | * from the same protocol. | |
559 | * | |
560 | * For each appropriate protocol, we first call its import_control() | |
561 | * hook which performs basic checks on the route (each protocol has a | |
562 | * right to veto or force accept of the route before any filter is | |
563 | * asked) and adds default values of attributes specific to the new | |
564 | * protocol (metrics, tags etc.). Then it consults the protocol's | |
565 | * export filter and if it accepts the route, the rt_notify() hook of | |
566 | * the protocol gets called. | |
9a8f20fc | 567 | */ |
e2dc2f30 | 568 | static void |
00a09f3c | 569 | rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, rte *before_old, ea_list *tmpa) |
2326b001 | 570 | { |
cf98be7b OZ |
571 | if (!rte_is_valid(old)) |
572 | old = before_old = NULL; | |
573 | ||
574 | if (!rte_is_valid(new)) | |
575 | new = NULL; | |
576 | ||
577 | if (!old && !new) | |
578 | return; | |
2326b001 | 579 | |
925fe2d3 OZ |
580 | if (type == RA_OPTIMAL) |
581 | { | |
582 | if (new) | |
094d2bdb | 583 | new->attrs->src->proto->stats.pref_routes++; |
925fe2d3 | 584 | if (old) |
094d2bdb | 585 | old->attrs->src->proto->stats.pref_routes--; |
cfe34a31 OZ |
586 | |
587 | if (tab->hostcache) | |
588 | rt_notify_hostcache(tab, net); | |
925fe2d3 OZ |
589 | } |
590 | ||
cf98be7b | 591 | struct announce_hook *a; |
0e02abfd | 592 | WALK_LIST(a, tab->hooks) |
0a2e9d9f | 593 | { |
0c791f87 | 594 | ASSERT(a->proto->export_state != ES_DOWN); |
23ac9e9a | 595 | if (a->proto->accept_ra_types == type) |
00a09f3c OZ |
596 | if (type == RA_ACCEPTED) |
597 | rt_notify_accepted(a, net, new, old, before_old, tmpa, 0); | |
598 | else | |
599 | rt_notify_basic(a, net, new, old, tmpa, 0); | |
0a2e9d9f | 600 | } |
2326b001 MM |
601 | } |
602 | ||
421838ff MM |
603 | static inline int |
604 | rte_validate(rte *e) | |
605 | { | |
606 | int c; | |
607 | net *n = e->net; | |
608 | ||
852b7062 | 609 | if ((n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen)) |
cfd46ee4 | 610 | { |
ab164971 | 611 | log(L_WARN "Ignoring bogus prefix %I/%d received via %s", |
c0adf7e9 | 612 | n->n.prefix, n->n.pxlen, e->sender->proto->name); |
cfd46ee4 MM |
613 | return 0; |
614 | } | |
ff2857b0 OZ |
615 | |
616 | c = ipa_classify_net(n->n.prefix); | |
617 | if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK)) | |
421838ff | 618 | { |
ff2857b0 | 619 | log(L_WARN "Ignoring bogus route %I/%d received via %s", |
c0adf7e9 | 620 | n->n.prefix, n->n.pxlen, e->sender->proto->name); |
ff2857b0 | 621 | return 0; |
421838ff | 622 | } |
ff2857b0 | 623 | |
421838ff MM |
624 | return 1; |
625 | } | |
626 | ||
58740ed4 MM |
627 | /** |
628 | * rte_free - delete a &rte | |
629 | * @e: &rte to be deleted | |
630 | * | |
631 | * rte_free() deletes the given &rte from the routing table it's linked to. | |
632 | */ | |
04925e90 | 633 | void |
2326b001 | 634 | rte_free(rte *e) |
04925e90 | 635 | { |
094d2bdb | 636 | if (rta_is_cached(e->attrs)) |
04925e90 MM |
637 | rta_free(e->attrs); |
638 | sl_free(rte_slab, e); | |
639 | } | |
640 | ||
641 | static inline void | |
642 | rte_free_quick(rte *e) | |
2326b001 MM |
643 | { |
644 | rta_free(e->attrs); | |
645 | sl_free(rte_slab, e); | |
646 | } | |
647 | ||
67be5b23 MM |
648 | static int |
649 | rte_same(rte *x, rte *y) | |
650 | { | |
651 | return | |
652 | x->attrs == y->attrs && | |
653 | x->flags == y->flags && | |
654 | x->pflags == y->pflags && | |
655 | x->pref == y->pref && | |
094d2bdb | 656 | (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y)); |
67be5b23 MM |
657 | } |
658 | ||
70577529 OZ |
659 | static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); } |
660 | ||
e2dc2f30 | 661 | static void |
094d2bdb | 662 | rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, struct rte_src *src) |
2326b001 | 663 | { |
c0adf7e9 OZ |
664 | struct proto *p = ah->proto; |
665 | struct rtable *table = ah->table; | |
666 | struct proto_stats *stats = ah->stats; | |
1123e707 | 667 | static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS; |
00a09f3c | 668 | rte *before_old = NULL; |
2326b001 MM |
669 | rte *old_best = net->routes; |
670 | rte *old = NULL; | |
00a09f3c | 671 | rte **k; |
2326b001 MM |
672 | |
673 | k = &net->routes; /* Find and remove original route from the same protocol */ | |
674 | while (old = *k) | |
675 | { | |
094d2bdb | 676 | if (old->attrs->src == src) |
2326b001 | 677 | { |
11787b84 OZ |
678 | /* If there is the same route in the routing table but from |
679 | * a different sender, then there are two paths from the | |
680 | * source protocol to this routing table through transparent | |
681 | * pipes, which is not allowed. | |
682 | * | |
683 | * We log that and ignore the route. If it is withdraw, we | |
684 | * ignore it completely (there might be 'spurious withdraws', | |
685 | * see FIXME in do_rte_announce()) | |
686 | */ | |
c0adf7e9 | 687 | if (old->sender->proto != p) |
11787b84 OZ |
688 | { |
689 | if (new) | |
690 | { | |
548c329c | 691 | log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %I/%d to table %s", |
11787b84 OZ |
692 | net->n.prefix, net->n.pxlen, table->name); |
693 | rte_free_quick(new); | |
694 | } | |
695 | return; | |
696 | } | |
697 | ||
0b761098 | 698 | if (new && rte_same(old, new)) |
67be5b23 MM |
699 | { |
700 | /* No changes, ignore the new route */ | |
cf98be7b | 701 | |
15550957 | 702 | if (!rte_is_filtered(new)) |
cf98be7b OZ |
703 | { |
704 | stats->imp_updates_ignored++; | |
705 | rte_trace_in(D_ROUTES, p, new, "ignored"); | |
706 | } | |
707 | ||
67be5b23 | 708 | rte_free_quick(new); |
4d9a0d1f OZ |
709 | #ifdef CONFIG_RIP |
710 | /* lastmod is used internally by RIP as the last time | |
711 | when the route was received. */ | |
094d2bdb | 712 | if (src->proto->proto == &proto_rip) |
4d9a0d1f OZ |
713 | old->lastmod = now; |
714 | #endif | |
67be5b23 MM |
715 | return; |
716 | } | |
2326b001 MM |
717 | *k = old->next; |
718 | break; | |
719 | } | |
720 | k = &old->next; | |
00a09f3c | 721 | before_old = old; |
2326b001 MM |
722 | } |
723 | ||
00a09f3c OZ |
724 | if (!old) |
725 | before_old = NULL; | |
726 | ||
925fe2d3 OZ |
727 | if (!old && !new) |
728 | { | |
9db74169 | 729 | stats->imp_withdraws_ignored++; |
925fe2d3 OZ |
730 | return; |
731 | } | |
732 | ||
b662290f OZ |
733 | int new_ok = rte_is_ok(new); |
734 | int old_ok = rte_is_ok(old); | |
735 | ||
736 | struct proto_limit *l = ah->rx_limit; | |
7d0a31de | 737 | if (l && !old && new) |
ebecb6f6 | 738 | { |
15550957 | 739 | u32 all_routes = stats->imp_routes + stats->filt_routes; |
cf98be7b OZ |
740 | |
741 | if (all_routes >= l->limit) | |
b662290f | 742 | proto_notify_limit(ah, l, PLD_RX, all_routes); |
7d0a31de OZ |
743 | |
744 | if (l->state == PLS_BLOCKED) | |
745 | { | |
b662290f OZ |
746 | /* In receive limit the situation is simple, old is NULL so |
747 | we just free new and exit like nothing happened */ | |
748 | ||
7d0a31de OZ |
749 | stats->imp_updates_ignored++; |
750 | rte_trace_in(D_FILTERS, p, new, "ignored [limit]"); | |
751 | rte_free_quick(new); | |
752 | return; | |
753 | } | |
ebecb6f6 OZ |
754 | } |
755 | ||
b662290f OZ |
756 | l = ah->in_limit; |
757 | if (l && !old_ok && new_ok) | |
758 | { | |
759 | if (stats->imp_routes >= l->limit) | |
760 | proto_notify_limit(ah, l, PLD_IN, stats->imp_routes); | |
761 | ||
762 | if (l->state == PLS_BLOCKED) | |
763 | { | |
764 | /* In import limit the situation is more complicated. We | |
765 | shouldn't just drop the route, we should handle it like | |
766 | it was filtered. We also have to continue the route | |
767 | processing if old or new is non-NULL, but we should exit | |
768 | if both are NULL as this case is probably assumed to be | |
769 | already handled. */ | |
770 | ||
771 | stats->imp_updates_ignored++; | |
772 | rte_trace_in(D_FILTERS, p, new, "ignored [limit]"); | |
773 | ||
774 | if (ah->in_keep_filtered) | |
775 | new->flags |= REF_FILTERED; | |
776 | else | |
777 | { rte_free_quick(new); new = NULL; } | |
778 | ||
779 | /* Note that old && !new could be possible when | |
780 | ah->in_keep_filtered changed in the recent past. */ | |
781 | ||
782 | if (!old && !new) | |
783 | return; | |
784 | ||
785 | new_ok = 0; | |
786 | goto skip_stats1; | |
787 | } | |
788 | } | |
70577529 OZ |
789 | |
790 | if (new_ok) | |
9db74169 | 791 | stats->imp_updates_accepted++; |
70577529 | 792 | else if (old_ok) |
9db74169 | 793 | stats->imp_withdraws_accepted++; |
70577529 OZ |
794 | else |
795 | stats->imp_withdraws_ignored++; | |
925fe2d3 | 796 | |
b662290f | 797 | skip_stats1: |
925fe2d3 OZ |
798 | |
799 | if (new) | |
15550957 | 800 | rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++; |
925fe2d3 | 801 | if (old) |
15550957 | 802 | rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--; |
925fe2d3 | 803 | |
26822d8f | 804 | if (table->config->sorted) |
2326b001 | 805 | { |
26822d8f OZ |
806 | /* If routes are sorted, just insert new route to appropriate position */ |
807 | if (new) | |
808 | { | |
809 | if (before_old && !rte_better(new, before_old)) | |
810 | k = &before_old->next; | |
811 | else | |
812 | k = &net->routes; | |
c0973621 | 813 | |
26822d8f OZ |
814 | for (; *k; k=&(*k)->next) |
815 | if (rte_better(new, *k)) | |
816 | break; | |
c0973621 | 817 | |
26822d8f OZ |
818 | new->next = *k; |
819 | *k = new; | |
820 | } | |
2326b001 | 821 | } |
26822d8f | 822 | else |
2326b001 | 823 | { |
26822d8f OZ |
824 | /* If routes are not sorted, find the best route and move it on |
825 | the first position. There are several optimized cases. */ | |
826 | ||
094d2bdb | 827 | if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best)) |
26822d8f OZ |
828 | goto do_recalculate; |
829 | ||
830 | if (new && rte_better(new, old_best)) | |
2326b001 | 831 | { |
26822d8f OZ |
832 | /* The first case - the new route is cleary optimal, |
833 | we link it at the first position */ | |
834 | ||
c0973621 OZ |
835 | new->next = net->routes; |
836 | net->routes = new; | |
837 | } | |
26822d8f | 838 | else if (old == old_best) |
c0973621 | 839 | { |
26822d8f OZ |
840 | /* The second case - the old best route disappeared, we add the |
841 | new route (if we have any) to the list (we don't care about | |
842 | position) and then we elect the new optimal route and relink | |
843 | that route at the first position and announce it. New optimal | |
844 | route might be NULL if there is no more routes */ | |
845 | ||
846 | do_recalculate: | |
847 | /* Add the new route to the list */ | |
848 | if (new) | |
2326b001 | 849 | { |
26822d8f OZ |
850 | new->next = net->routes; |
851 | net->routes = new; | |
852 | } | |
853 | ||
854 | /* Find a new optimal route (if there is any) */ | |
855 | if (net->routes) | |
856 | { | |
857 | rte **bp = &net->routes; | |
858 | for (k=&(*bp)->next; *k; k=&(*k)->next) | |
859 | if (rte_better(*k, *bp)) | |
860 | bp = k; | |
861 | ||
862 | /* And relink it */ | |
863 | rte *best = *bp; | |
864 | *bp = best->next; | |
865 | best->next = net->routes; | |
866 | net->routes = best; | |
2326b001 | 867 | } |
2326b001 | 868 | } |
26822d8f OZ |
869 | else if (new) |
870 | { | |
871 | /* The third case - the new route is not better than the old | |
872 | best route (therefore old_best != NULL) and the old best | |
873 | route was not removed (therefore old_best == net->routes). | |
874 | We just link the new route after the old best route. */ | |
875 | ||
876 | ASSERT(net->routes != NULL); | |
877 | new->next = net->routes->next; | |
878 | net->routes->next = new; | |
879 | } | |
880 | /* The fourth (empty) case - suboptimal route was removed, nothing to do */ | |
2326b001 | 881 | } |
c0973621 | 882 | |
26822d8f OZ |
883 | if (new) |
884 | new->lastmod = now; | |
885 | ||
886 | /* Log the route change */ | |
70577529 | 887 | if (p->debug & D_ROUTES) |
e8b29bdc | 888 | { |
70577529 OZ |
889 | if (new_ok) |
890 | rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added"); | |
891 | else if (old_ok) | |
892 | { | |
893 | if (old != old_best) | |
894 | rte_trace(p, old, '>', "removed"); | |
895 | else if (rte_is_ok(net->routes)) | |
896 | rte_trace(p, old, '>', "removed [replaced]"); | |
897 | else | |
898 | rte_trace(p, old, '>', "removed [sole]"); | |
899 | } | |
c0973621 OZ |
900 | } |
901 | ||
26822d8f | 902 | /* Propagate the route change */ |
00a09f3c | 903 | rte_announce(table, RA_ANY, net, new, old, NULL, tmpa); |
26822d8f OZ |
904 | if (net->routes != old_best) |
905 | rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, tmpa); | |
906 | if (table->config->sorted) | |
907 | rte_announce(table, RA_ACCEPTED, net, new, old, before_old, tmpa); | |
00a09f3c OZ |
908 | |
909 | if (!net->routes && | |
910 | (table->gc_counter++ >= table->config->gc_max_ops) && | |
911 | (table->gc_time + table->config->gc_min_time <= now)) | |
912 | rt_schedule_gc(table); | |
913 | ||
70577529 OZ |
914 | if (old_ok && p->rte_remove) |
915 | p->rte_remove(net, old); | |
916 | if (new_ok && p->rte_insert) | |
917 | p->rte_insert(net, new); | |
918 | ||
2326b001 | 919 | if (old) |
70577529 | 920 | rte_free_quick(old); |
5b22683d MM |
921 | } |
922 | ||
e2dc2f30 MM |
923 | static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */ |
924 | ||
925 | static inline void | |
926 | rte_update_lock(void) | |
927 | { | |
928 | rte_update_nest_cnt++; | |
929 | } | |
930 | ||
931 | static inline void | |
932 | rte_update_unlock(void) | |
933 | { | |
934 | if (!--rte_update_nest_cnt) | |
935 | lp_flush(rte_update_pool); | |
936 | } | |
937 | ||
fad04c75 OZ |
938 | static inline void |
939 | rte_hide_dummy_routes(net *net, rte **dummy) | |
940 | { | |
941 | if (net->routes && net->routes->attrs->source == RTS_DUMMY) | |
942 | { | |
943 | *dummy = net->routes; | |
944 | net->routes = (*dummy)->next; | |
945 | } | |
946 | } | |
947 | ||
948 | static inline void | |
949 | rte_unhide_dummy_routes(net *net, rte **dummy) | |
950 | { | |
951 | if (*dummy) | |
952 | { | |
953 | (*dummy)->next = net->routes; | |
954 | net->routes = *dummy; | |
955 | } | |
956 | } | |
957 | ||
58740ed4 MM |
958 | /** |
959 | * rte_update - enter a new update to a routing table | |
960 | * @table: table to be updated | |
c0adf7e9 | 961 | * @ah: pointer to table announce hook |
58740ed4 MM |
962 | * @net: network node |
963 | * @p: protocol submitting the update | |
f98e2915 | 964 | * @src: protocol originating the update |
58740ed4 MM |
965 | * @new: a &rte representing the new route or %NULL for route removal. |
966 | * | |
967 | * This function is called by the routing protocols whenever they discover | |
968 | * a new route or wish to update/remove an existing route. The right announcement | |
2e9b2421 | 969 | * sequence is to build route attributes first (either un-cached with @aflags set |
58740ed4 MM |
970 | * to zero or a cached one using rta_lookup(); in this case please note that |
971 | * you need to increase the use count of the attributes yourself by calling | |
972 | * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all | |
973 | * the appropriate data and finally submit the new &rte by calling rte_update(). | |
974 | * | |
f98e2915 OZ |
975 | * @src specifies the protocol that originally created the route and the meaning |
976 | * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the | |
977 | * same value as @new->attrs->proto. @p specifies the protocol that called | |
978 | * rte_update(). In most cases it is the same protocol as @src. rte_update() | |
979 | * stores @p in @new->sender; | |
980 | * | |
9a8f20fc MM |
981 | * When rte_update() gets any route, it automatically validates it (checks, |
982 | * whether the network and next hop address are valid IP addresses and also | |
983 | * whether a normal routing protocol doesn't try to smuggle a host or link | |
984 | * scope route to the table), converts all protocol dependent attributes stored | |
985 | * in the &rte to temporary extended attributes, consults import filters of the | |
986 | * protocol to see if the route should be accepted and/or its attributes modified, | |
987 | * stores the temporary attributes back to the &rte. | |
988 | * | |
989 | * Now, having a "public" version of the route, we | |
f98e2915 | 990 | * automatically find any old route defined by the protocol @src |
58740ed4 MM |
991 | * for network @n, replace it by the new one (or removing it if @new is %NULL), |
992 | * recalculate the optimal route for this destination and finally broadcast | |
9a8f20fc | 993 | * the change (if any) to all routing protocols by calling rte_announce(). |
3ce8c610 MM |
994 | * |
995 | * All memory used for attribute lists and other temporary allocations is taken | |
996 | * from a special linear pool @rte_update_pool and freed when rte_update() | |
997 | * finishes. | |
58740ed4 | 998 | */ |
23ac9e9a OZ |
999 | |
1000 | void | |
094d2bdb | 1001 | rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src) |
e2dc2f30 | 1002 | { |
c0adf7e9 OZ |
1003 | struct proto *p = ah->proto; |
1004 | struct proto_stats *stats = ah->stats; | |
1005 | struct filter *filter = ah->in_filter; | |
e2dc2f30 | 1006 | ea_list *tmpa = NULL; |
fad04c75 | 1007 | rte *dummy = NULL; |
e2dc2f30 MM |
1008 | |
1009 | rte_update_lock(); | |
1010 | if (new) | |
1011 | { | |
c0adf7e9 | 1012 | new->sender = ah; |
40b65f94 | 1013 | |
9db74169 | 1014 | stats->imp_updates_received++; |
cfd46ee4 MM |
1015 | if (!rte_validate(new)) |
1016 | { | |
1017 | rte_trace_in(D_FILTERS, p, new, "invalid"); | |
9db74169 | 1018 | stats->imp_updates_invalid++; |
cfd46ee4 MM |
1019 | goto drop; |
1020 | } | |
cf98be7b | 1021 | |
40b65f94 | 1022 | if (filter == FILTER_REJECT) |
cfd46ee4 | 1023 | { |
9db74169 | 1024 | stats->imp_updates_filtered++; |
cfd46ee4 | 1025 | rte_trace_in(D_FILTERS, p, new, "filtered out"); |
094d2bdb | 1026 | |
15550957 | 1027 | if (! ah->in_keep_filtered) |
cf98be7b OZ |
1028 | goto drop; |
1029 | ||
1030 | /* new is a private copy, i could modify it */ | |
15550957 | 1031 | new->flags |= REF_FILTERED; |
cfd46ee4 | 1032 | } |
cf98be7b | 1033 | else |
e2dc2f30 | 1034 | { |
736e143f | 1035 | tmpa = make_tmp_attrs(new, rte_update_pool); |
cf98be7b | 1036 | if (filter && (filter != FILTER_REJECT)) |
cfd46ee4 | 1037 | { |
cf98be7b OZ |
1038 | ea_list *old_tmpa = tmpa; |
1039 | int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0); | |
1040 | if (fr > F_ACCEPT) | |
1041 | { | |
1042 | stats->imp_updates_filtered++; | |
1043 | rte_trace_in(D_FILTERS, p, new, "filtered out"); | |
1044 | ||
15550957 | 1045 | if (! ah->in_keep_filtered) |
cf98be7b OZ |
1046 | goto drop; |
1047 | ||
15550957 | 1048 | new->flags |= REF_FILTERED; |
cf98be7b | 1049 | } |
736e143f OZ |
1050 | if (tmpa != old_tmpa && src->proto->store_tmp_attrs) |
1051 | src->proto->store_tmp_attrs(new, tmpa); | |
cfd46ee4 | 1052 | } |
e2dc2f30 | 1053 | } |
094d2bdb | 1054 | if (!rta_is_cached(new->attrs)) /* Need to copy attributes */ |
e2dc2f30 MM |
1055 | new->attrs = rta_lookup(new->attrs); |
1056 | new->flags |= REF_COW; | |
1057 | } | |
925fe2d3 | 1058 | else |
094d2bdb OZ |
1059 | { |
1060 | stats->imp_withdraws_received++; | |
1061 | ||
1062 | if (!net || !src) | |
1063 | { | |
1064 | stats->imp_withdraws_ignored++; | |
1065 | rte_update_unlock(); | |
1066 | return; | |
1067 | } | |
1068 | } | |
925fe2d3 | 1069 | |
fad04c75 OZ |
1070 | recalc: |
1071 | rte_hide_dummy_routes(net, &dummy); | |
c0adf7e9 | 1072 | rte_recalculate(ah, net, new, tmpa, src); |
fad04c75 | 1073 | rte_unhide_dummy_routes(net, &dummy); |
e2dc2f30 MM |
1074 | rte_update_unlock(); |
1075 | return; | |
1076 | ||
fad04c75 | 1077 | drop: |
e2dc2f30 | 1078 | rte_free(new); |
fad04c75 OZ |
1079 | new = NULL; |
1080 | tmpa = NULL; | |
1081 | goto recalc; | |
e2dc2f30 MM |
1082 | } |
1083 | ||
cfe34a31 OZ |
1084 | /* Independent call to rte_announce(), used from next hop |
1085 | recalculation, outside of rte_update(). new must be non-NULL */ | |
1086 | static inline void | |
1087 | rte_announce_i(rtable *tab, unsigned type, net *n, rte *new, rte *old) | |
1088 | { | |
cfe34a31 OZ |
1089 | ea_list *tmpa; |
1090 | ||
1091 | rte_update_lock(); | |
094d2bdb | 1092 | tmpa = make_tmp_attrs(new, rte_update_pool); |
00a09f3c | 1093 | rte_announce(tab, type, n, new, old, NULL, tmpa); |
cfe34a31 OZ |
1094 | rte_update_unlock(); |
1095 | } | |
1096 | ||
5b22683d | 1097 | void |
0e02abfd | 1098 | rte_discard(rtable *t, rte *old) /* Non-filtered route deletion, used during garbage collection */ |
5b22683d | 1099 | { |
e2dc2f30 | 1100 | rte_update_lock(); |
094d2bdb | 1101 | rte_recalculate(old->sender, old->net, NULL, NULL, old->attrs->src); |
e2dc2f30 | 1102 | rte_update_unlock(); |
2326b001 MM |
1103 | } |
1104 | ||
36da2857 OZ |
1105 | /* Check rtable for best route to given net whether it would be exported do p */ |
1106 | int | |
1107 | rt_examine(rtable *t, ip_addr prefix, int pxlen, struct proto *p, struct filter *filter) | |
1108 | { | |
1109 | net *n = net_find(t, prefix, pxlen); | |
1110 | rte *rt = n ? n->routes : NULL; | |
1111 | ||
1112 | if (!rte_is_valid(rt)) | |
1113 | return 0; | |
1114 | ||
1115 | rte_update_lock(); | |
1116 | ||
1117 | /* Rest is stripped down export_filter() */ | |
736e143f | 1118 | ea_list *tmpa = make_tmp_attrs(rt, rte_update_pool); |
36da2857 OZ |
1119 | int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0; |
1120 | if (v == RIC_PROCESS) | |
1121 | v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT); | |
1122 | ||
1123 | /* Discard temporary rte */ | |
1124 | if (rt != n->routes) | |
1125 | rte_free(rt); | |
1126 | ||
1127 | rte_update_unlock(); | |
1128 | ||
1129 | return v > 0; | |
1130 | } | |
1131 | ||
6eda3f13 OZ |
1132 | |
1133 | /** | |
1134 | * rt_refresh_begin - start a refresh cycle | |
1135 | * @t: related routing table | |
1136 | * @ah: related announce hook | |
1137 | * | |
1138 | * This function starts a refresh cycle for given routing table and announce | |
1139 | * hook. The refresh cycle is a sequence where the protocol sends all its valid | |
1140 | * routes to the routing table (by rte_update()). After that, all protocol | |
1141 | * routes (more precisely routes with @ah as @sender) not sent during the | |
1142 | * refresh cycle but still in the table from the past are pruned. This is | |
1143 | * implemented by marking all related routes as stale by REF_STALE flag in | |
1144 | * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD | |
1145 | * flag in rt_refresh_end() and then removing such routes in the prune loop. | |
1146 | */ | |
0c791f87 OZ |
1147 | void |
1148 | rt_refresh_begin(rtable *t, struct announce_hook *ah) | |
1149 | { | |
1150 | net *n; | |
1151 | rte *e; | |
1152 | ||
1153 | FIB_WALK(&t->fib, fn) | |
1154 | { | |
1155 | n = (net *) fn; | |
1156 | for (e = n->routes; e; e = e->next) | |
1157 | if (e->sender == ah) | |
1158 | e->flags |= REF_STALE; | |
1159 | } | |
1160 | FIB_WALK_END; | |
1161 | } | |
1162 | ||
6eda3f13 OZ |
1163 | /** |
1164 | * rt_refresh_end - end a refresh cycle | |
1165 | * @t: related routing table | |
1166 | * @ah: related announce hook | |
1167 | * | |
1168 | * This function starts a refresh cycle for given routing table and announce | |
1169 | * hook. See rt_refresh_begin() for description of refresh cycles. | |
1170 | */ | |
0c791f87 OZ |
1171 | void |
1172 | rt_refresh_end(rtable *t, struct announce_hook *ah) | |
1173 | { | |
1174 | int prune = 0; | |
1175 | net *n; | |
1176 | rte *e; | |
1177 | ||
1178 | FIB_WALK(&t->fib, fn) | |
1179 | { | |
1180 | n = (net *) fn; | |
1181 | for (e = n->routes; e; e = e->next) | |
1182 | if ((e->sender == ah) && (e->flags & REF_STALE)) | |
1183 | { | |
1184 | e->flags |= REF_DISCARD; | |
1185 | prune = 1; | |
1186 | } | |
1187 | } | |
1188 | FIB_WALK_END; | |
1189 | ||
1190 | if (prune) | |
1191 | rt_schedule_prune(t); | |
1192 | } | |
1193 | ||
1194 | ||
58740ed4 MM |
1195 | /** |
1196 | * rte_dump - dump a route | |
1197 | * @e: &rte to be dumped | |
1198 | * | |
1199 | * This functions dumps contents of a &rte to debug output. | |
1200 | */ | |
2326b001 | 1201 | void |
a0762910 | 1202 | rte_dump(rte *e) |
2326b001 | 1203 | { |
a0762910 | 1204 | net *n = e->net; |
47c447c4 | 1205 | debug("%-1I/%2d ", n->n.prefix, n->n.pxlen); |
c10421d3 | 1206 | debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod); |
0cdbd397 | 1207 | rta_dump(e->attrs); |
094d2bdb OZ |
1208 | if (e->attrs->src->proto->proto->dump_attrs) |
1209 | e->attrs->src->proto->proto->dump_attrs(e); | |
0cdbd397 | 1210 | debug("\n"); |
2326b001 | 1211 | } |
62aa008a | 1212 | |
58740ed4 MM |
1213 | /** |
1214 | * rt_dump - dump a routing table | |
1215 | * @t: routing table to be dumped | |
1216 | * | |
1217 | * This function dumps contents of a given routing table to debug output. | |
1218 | */ | |
2326b001 MM |
1219 | void |
1220 | rt_dump(rtable *t) | |
1221 | { | |
0cdbd397 MM |
1222 | rte *e; |
1223 | net *n; | |
0e02abfd | 1224 | struct announce_hook *a; |
0cdbd397 MM |
1225 | |
1226 | debug("Dump of routing table <%s>\n", t->name); | |
e440395d | 1227 | #ifdef DEBUGGING |
08e2d625 | 1228 | fib_check(&t->fib); |
e440395d | 1229 | #endif |
08e2d625 MM |
1230 | FIB_WALK(&t->fib, fn) |
1231 | { | |
1232 | n = (net *) fn; | |
1233 | for(e=n->routes; e; e=e->next) | |
1234 | rte_dump(e); | |
0cdbd397 | 1235 | } |
08e2d625 | 1236 | FIB_WALK_END; |
0e02abfd MM |
1237 | WALK_LIST(a, t->hooks) |
1238 | debug("\tAnnounces routes to protocol %s\n", a->proto->name); | |
0cdbd397 | 1239 | debug("\n"); |
2326b001 | 1240 | } |
62aa008a | 1241 | |
58740ed4 MM |
1242 | /** |
1243 | * rt_dump_all - dump all routing tables | |
1244 | * | |
1245 | * This function dumps contents of all routing tables to debug output. | |
1246 | */ | |
6d45cf21 MM |
1247 | void |
1248 | rt_dump_all(void) | |
1249 | { | |
0e02abfd MM |
1250 | rtable *t; |
1251 | ||
1252 | WALK_LIST(t, routing_tables) | |
1253 | rt_dump(t); | |
6d45cf21 MM |
1254 | } |
1255 | ||
0c791f87 OZ |
1256 | static inline void |
1257 | rt_schedule_prune(rtable *tab) | |
1258 | { | |
1259 | rt_mark_for_prune(tab); | |
1260 | ev_schedule(tab->rt_event); | |
1261 | } | |
1262 | ||
cfe34a31 OZ |
1263 | static inline void |
1264 | rt_schedule_gc(rtable *tab) | |
1265 | { | |
1266 | if (tab->gc_scheduled) | |
1267 | return; | |
1268 | ||
1269 | tab->gc_scheduled = 1; | |
1270 | ev_schedule(tab->rt_event); | |
1271 | } | |
1272 | ||
1273 | static inline void | |
1274 | rt_schedule_hcu(rtable *tab) | |
1275 | { | |
1276 | if (tab->hcu_scheduled) | |
1277 | return; | |
1278 | ||
1279 | tab->hcu_scheduled = 1; | |
1280 | ev_schedule(tab->rt_event); | |
1281 | } | |
1282 | ||
1283 | static inline void | |
1284 | rt_schedule_nhu(rtable *tab) | |
1285 | { | |
1286 | if (tab->nhu_state == 0) | |
1287 | ev_schedule(tab->rt_event); | |
1288 | ||
1289 | /* state change 0->1, 2->3 */ | |
1290 | tab->nhu_state |= 1; | |
1291 | } | |
1292 | ||
0c791f87 | 1293 | |
fb829de6 OZ |
1294 | static void |
1295 | rt_prune_nets(rtable *tab) | |
1296 | { | |
1297 | struct fib_iterator fit; | |
1298 | int ncnt = 0, ndel = 0; | |
1299 | ||
1300 | #ifdef DEBUGGING | |
1301 | fib_check(&tab->fib); | |
1302 | #endif | |
1303 | ||
1304 | FIB_ITERATE_INIT(&fit, &tab->fib); | |
1305 | again: | |
1306 | FIB_ITERATE_START(&tab->fib, &fit, f) | |
1307 | { | |
1308 | net *n = (net *) f; | |
1309 | ncnt++; | |
1310 | if (!n->routes) /* Orphaned FIB entry */ | |
1311 | { | |
1312 | FIB_ITERATE_PUT(&fit, f); | |
1313 | fib_delete(&tab->fib, f); | |
1314 | ndel++; | |
1315 | goto again; | |
1316 | } | |
1317 | } | |
1318 | FIB_ITERATE_END(f); | |
1319 | DBG("Pruned %d of %d networks\n", ndel, ncnt); | |
1320 | ||
1321 | tab->gc_counter = 0; | |
1322 | tab->gc_time = now; | |
1323 | tab->gc_scheduled = 0; | |
1324 | } | |
1325 | ||
8f6accb5 | 1326 | static void |
cfe34a31 | 1327 | rt_event(void *ptr) |
5996da6a | 1328 | { |
cfe34a31 OZ |
1329 | rtable *tab = ptr; |
1330 | ||
1331 | if (tab->hcu_scheduled) | |
1332 | rt_update_hostcache(tab); | |
0e02abfd | 1333 | |
cfe34a31 OZ |
1334 | if (tab->nhu_state) |
1335 | rt_next_hop_update(tab); | |
1336 | ||
0c791f87 OZ |
1337 | if (tab->prune_state) |
1338 | if (!rt_prune_table(tab)) | |
1339 | { | |
1340 | /* Table prune unfinished */ | |
1341 | ev_schedule(tab->rt_event); | |
1342 | return; | |
1343 | } | |
1344 | ||
cfe34a31 | 1345 | if (tab->gc_scheduled) |
094d2bdb OZ |
1346 | { |
1347 | rt_prune_nets(tab); | |
1348 | rt_prune_sources(); // FIXME this should be moved to independent event | |
1349 | } | |
5996da6a MM |
1350 | } |
1351 | ||
b9626ec6 MM |
1352 | void |
1353 | rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf) | |
1354 | { | |
1355 | bzero(t, sizeof(*t)); | |
1356 | fib_init(&t->fib, p, sizeof(net), 0, rte_init); | |
1357 | t->name = name; | |
1358 | t->config = cf; | |
1359 | init_list(&t->hooks); | |
1360 | if (cf) | |
1361 | { | |
cfe34a31 OZ |
1362 | t->rt_event = ev_new(p); |
1363 | t->rt_event->hook = rt_event; | |
1364 | t->rt_event->data = t; | |
2eca3b3a | 1365 | t->gc_time = now; |
b9626ec6 MM |
1366 | } |
1367 | } | |
1368 | ||
58740ed4 MM |
1369 | /** |
1370 | * rt_init - initialize routing tables | |
1371 | * | |
1372 | * This function is called during BIRD startup. It initializes the | |
1373 | * routing table module. | |
1374 | */ | |
2326b001 MM |
1375 | void |
1376 | rt_init(void) | |
1377 | { | |
1378 | rta_init(); | |
5996da6a | 1379 | rt_table_pool = rp_new(&root_pool, "Routing tables"); |
e2dc2f30 | 1380 | rte_update_pool = lp_new(rt_table_pool, 4080); |
5996da6a | 1381 | rte_slab = sl_new(rt_table_pool, sizeof(rte)); |
0e02abfd | 1382 | init_list(&routing_tables); |
2326b001 | 1383 | } |
1a54b1c6 | 1384 | |
fb829de6 | 1385 | |
0c791f87 | 1386 | static int |
d0e23d42 | 1387 | rt_prune_step(rtable *tab, int *limit) |
fb829de6 OZ |
1388 | { |
1389 | struct fib_iterator *fit = &tab->prune_fit; | |
1a54b1c6 MM |
1390 | |
1391 | DBG("Pruning route table %s\n", tab->name); | |
0521e4f6 MM |
1392 | #ifdef DEBUGGING |
1393 | fib_check(&tab->fib); | |
1394 | #endif | |
fb829de6 | 1395 | |
0c791f87 | 1396 | if (tab->prune_state == RPS_NONE) |
fb829de6 OZ |
1397 | return 1; |
1398 | ||
0c791f87 | 1399 | if (tab->prune_state == RPS_SCHEDULED) |
fb829de6 OZ |
1400 | { |
1401 | FIB_ITERATE_INIT(fit, &tab->fib); | |
0c791f87 | 1402 | tab->prune_state = RPS_RUNNING; |
fb829de6 OZ |
1403 | } |
1404 | ||
08e2d625 | 1405 | again: |
fb829de6 | 1406 | FIB_ITERATE_START(&tab->fib, fit, fn) |
1a54b1c6 | 1407 | { |
fb829de6 | 1408 | net *n = (net *) fn; |
08e2d625 | 1409 | rte *e; |
fb829de6 | 1410 | |
08e2d625 | 1411 | rescan: |
fb829de6 | 1412 | for (e=n->routes; e; e=e->next) |
d0e23d42 | 1413 | if (e->sender->proto->flushing || (e->flags & REF_DISCARD)) |
08e2d625 | 1414 | { |
0c791f87 | 1415 | if (*limit <= 0) |
fb829de6 OZ |
1416 | { |
1417 | FIB_ITERATE_PUT(fit, fn); | |
1418 | return 0; | |
1419 | } | |
1420 | ||
0e02abfd | 1421 | rte_discard(tab, e); |
0c791f87 | 1422 | (*limit)--; |
fb829de6 | 1423 | |
08e2d625 MM |
1424 | goto rescan; |
1425 | } | |
fb829de6 | 1426 | if (!n->routes) /* Orphaned FIB entry */ |
1a54b1c6 | 1427 | { |
fb829de6 OZ |
1428 | FIB_ITERATE_PUT(fit, fn); |
1429 | fib_delete(&tab->fib, fn); | |
08e2d625 | 1430 | goto again; |
1a54b1c6 | 1431 | } |
1a54b1c6 | 1432 | } |
fb829de6 OZ |
1433 | FIB_ITERATE_END(fn); |
1434 | ||
0521e4f6 MM |
1435 | #ifdef DEBUGGING |
1436 | fib_check(&tab->fib); | |
1437 | #endif | |
fb829de6 | 1438 | |
0c791f87 | 1439 | tab->prune_state = RPS_NONE; |
fb829de6 | 1440 | return 1; |
1a54b1c6 | 1441 | } |
0e02abfd | 1442 | |
6eda3f13 OZ |
1443 | /** |
1444 | * rt_prune_table - prune a routing table | |
1445 | * | |
1446 | * This function scans the routing table @tab and removes routes belonging to | |
1447 | * flushing protocols, discarded routes and also stale network entries, in a | |
1448 | * similar fashion like rt_prune_loop(). Returns 1 when all such routes are | |
1449 | * pruned. Contrary to rt_prune_loop(), this function is not a part of the | |
1450 | * protocol flushing loop, but it is called from rt_event() for just one routing | |
1451 | * table. | |
1452 | * | |
1453 | * Note that rt_prune_table() and rt_prune_loop() share (for each table) the | |
1454 | * prune state (@prune_state) and also the pruning iterator (@prune_fit). | |
1455 | */ | |
0c791f87 OZ |
1456 | static inline int |
1457 | rt_prune_table(rtable *tab) | |
1458 | { | |
1459 | int limit = 512; | |
d0e23d42 | 1460 | return rt_prune_step(tab, &limit); |
0c791f87 OZ |
1461 | } |
1462 | ||
58740ed4 | 1463 | /** |
fb829de6 | 1464 | * rt_prune_loop - prune routing tables |
58740ed4 | 1465 | * |
6eda3f13 OZ |
1466 | * The prune loop scans routing tables and removes routes belonging to flushing |
1467 | * protocols, discarded routes and also stale network entries. Returns 1 when | |
1468 | * all such routes are pruned. It is a part of the protocol flushing loop. | |
58740ed4 | 1469 | */ |
fb829de6 OZ |
1470 | int |
1471 | rt_prune_loop(void) | |
0e02abfd | 1472 | { |
0c791f87 | 1473 | int limit = 512; |
9135c1f0 | 1474 | rtable *t; |
0e02abfd MM |
1475 | |
1476 | WALK_LIST(t, routing_tables) | |
d0e23d42 | 1477 | if (! rt_prune_step(t, &limit)) |
fb829de6 OZ |
1478 | return 0; |
1479 | ||
1480 | return 1; | |
0e02abfd MM |
1481 | } |
1482 | ||
cfe34a31 OZ |
1483 | void |
1484 | rt_preconfig(struct config *c) | |
1485 | { | |
1486 | struct symbol *s = cf_find_symbol("master"); | |
1487 | ||
1488 | init_list(&c->tables); | |
1489 | c->master_rtc = rt_new_table(s); | |
1490 | } | |
1491 | ||
1492 | ||
1493 | /* | |
1494 | * Some functions for handing internal next hop updates | |
1495 | * triggered by rt_schedule_nhu(). | |
1496 | */ | |
1497 | ||
cfe34a31 OZ |
1498 | static inline int |
1499 | rta_next_hop_outdated(rta *a) | |
1500 | { | |
1501 | struct hostentry *he = a->hostentry; | |
7e95c05d OZ |
1502 | |
1503 | if (!he) | |
1504 | return 0; | |
1505 | ||
1506 | if (!he->src) | |
1507 | return a->dest != RTD_UNREACHABLE; | |
1508 | ||
1509 | return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) || | |
1510 | (a->dest != he->dest) || (a->igp_metric != he->igp_metric) || | |
1511 | !mpnh_same(a->nexthops, he->src->nexthops); | |
cfe34a31 OZ |
1512 | } |
1513 | ||
1514 | static inline void | |
1515 | rta_apply_hostentry(rta *a, struct hostentry *he) | |
1516 | { | |
1517 | a->hostentry = he; | |
7e95c05d | 1518 | a->iface = he->src ? he->src->iface : NULL; |
cfe34a31 OZ |
1519 | a->gw = he->gw; |
1520 | a->dest = he->dest; | |
d1e146f2 | 1521 | a->igp_metric = he->igp_metric; |
7e95c05d | 1522 | a->nexthops = he->src ? he->src->nexthops : NULL; |
cfe34a31 OZ |
1523 | } |
1524 | ||
1525 | static inline rte * | |
1526 | rt_next_hop_update_rte(rtable *tab, rte *old) | |
1527 | { | |
1528 | rta a; | |
1529 | memcpy(&a, old->attrs, sizeof(rta)); | |
1530 | rta_apply_hostentry(&a, old->attrs->hostentry); | |
1531 | a.aflags = 0; | |
1532 | ||
1533 | rte *e = sl_alloc(rte_slab); | |
1534 | memcpy(e, old, sizeof(rte)); | |
1535 | e->attrs = rta_lookup(&a); | |
1536 | ||
1537 | return e; | |
1538 | } | |
1539 | ||
1540 | static inline int | |
1541 | rt_next_hop_update_net(rtable *tab, net *n) | |
1542 | { | |
1543 | rte **k, *e, *new, *old_best, **new_best; | |
1544 | int count = 0; | |
1545 | int free_old_best = 0; | |
1546 | ||
1547 | old_best = n->routes; | |
1548 | if (!old_best) | |
1549 | return 0; | |
1550 | ||
cfe34a31 | 1551 | for (k = &n->routes; e = *k; k = &e->next) |
be4cd99a OZ |
1552 | if (rta_next_hop_outdated(e->attrs)) |
1553 | { | |
1554 | new = rt_next_hop_update_rte(tab, e); | |
1555 | *k = new; | |
cfe34a31 | 1556 | |
be4cd99a | 1557 | rte_announce_i(tab, RA_ANY, n, new, e); |
c0adf7e9 | 1558 | rte_trace_in(D_ROUTES, new->sender->proto, new, "updated"); |
cfe34a31 | 1559 | |
be4cd99a OZ |
1560 | /* Call a pre-comparison hook */ |
1561 | /* Not really an efficient way to compute this */ | |
094d2bdb OZ |
1562 | if (e->attrs->src->proto->rte_recalculate) |
1563 | e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL); | |
cfe34a31 | 1564 | |
be4cd99a OZ |
1565 | if (e != old_best) |
1566 | rte_free_quick(e); | |
1567 | else /* Freeing of the old best rte is postponed */ | |
1568 | free_old_best = 1; | |
cfe34a31 | 1569 | |
be4cd99a OZ |
1570 | e = new; |
1571 | count++; | |
1572 | } | |
1573 | ||
1574 | if (!count) | |
1575 | return 0; | |
1576 | ||
1577 | /* Find the new best route */ | |
1578 | new_best = NULL; | |
1579 | for (k = &n->routes; e = *k; k = &e->next) | |
1580 | { | |
cfe34a31 OZ |
1581 | if (!new_best || rte_better(e, *new_best)) |
1582 | new_best = k; | |
1583 | } | |
1584 | ||
1585 | /* Relink the new best route to the first position */ | |
1586 | new = *new_best; | |
1587 | if (new != n->routes) | |
1588 | { | |
1589 | *new_best = new->next; | |
1590 | new->next = n->routes; | |
1591 | n->routes = new; | |
1592 | } | |
1593 | ||
1594 | /* Announce the new best route */ | |
1595 | if (new != old_best) | |
1596 | { | |
1597 | rte_announce_i(tab, RA_OPTIMAL, n, new, old_best); | |
c0adf7e9 | 1598 | rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]"); |
cfe34a31 OZ |
1599 | } |
1600 | ||
1601 | if (free_old_best) | |
1602 | rte_free_quick(old_best); | |
1603 | ||
1604 | return count; | |
1605 | } | |
1606 | ||
1607 | static void | |
1608 | rt_next_hop_update(rtable *tab) | |
1609 | { | |
1610 | struct fib_iterator *fit = &tab->nhu_fit; | |
1611 | int max_feed = 32; | |
1612 | ||
1613 | if (tab->nhu_state == 0) | |
1614 | return; | |
1615 | ||
1616 | if (tab->nhu_state == 1) | |
1617 | { | |
1618 | FIB_ITERATE_INIT(fit, &tab->fib); | |
1619 | tab->nhu_state = 2; | |
1620 | } | |
1621 | ||
1622 | FIB_ITERATE_START(&tab->fib, fit, fn) | |
1623 | { | |
1624 | if (max_feed <= 0) | |
1625 | { | |
1626 | FIB_ITERATE_PUT(fit, fn); | |
1627 | ev_schedule(tab->rt_event); | |
1628 | return; | |
1629 | } | |
1630 | max_feed -= rt_next_hop_update_net(tab, (net *) fn); | |
1631 | } | |
1632 | FIB_ITERATE_END(fn); | |
1633 | ||
1634 | /* state change 2->0, 3->1 */ | |
1635 | tab->nhu_state &= 1; | |
1636 | ||
1637 | if (tab->nhu_state > 0) | |
1638 | ev_schedule(tab->rt_event); | |
1639 | } | |
1640 | ||
1641 | ||
b9626ec6 MM |
1642 | struct rtable_config * |
1643 | rt_new_table(struct symbol *s) | |
1644 | { | |
36415e4b OZ |
1645 | /* Hack that allows to 'redefine' the master table */ |
1646 | if ((s->class == SYM_TABLE) && (s->def == new_config->master_rtc)) | |
1647 | return s->def; | |
1648 | ||
b9626ec6 MM |
1649 | struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config)); |
1650 | ||
1651 | cf_define_symbol(s, SYM_TABLE, c); | |
1652 | c->name = s->name; | |
1653 | add_tail(&new_config->tables, &c->n); | |
2eca3b3a | 1654 | c->gc_max_ops = 1000; |
b9626ec6 MM |
1655 | c->gc_min_time = 5; |
1656 | return c; | |
1657 | } | |
1658 | ||
58740ed4 MM |
1659 | /** |
1660 | * rt_lock_table - lock a routing table | |
1661 | * @r: routing table to be locked | |
1662 | * | |
1663 | * Lock a routing table, because it's in use by a protocol, | |
1664 | * preventing it from being freed when it gets undefined in a new | |
1665 | * configuration. | |
1666 | */ | |
0e02abfd | 1667 | void |
50fe90ed | 1668 | rt_lock_table(rtable *r) |
0e02abfd | 1669 | { |
50fe90ed MM |
1670 | r->use_count++; |
1671 | } | |
1672 | ||
58740ed4 MM |
1673 | /** |
1674 | * rt_unlock_table - unlock a routing table | |
1675 | * @r: routing table to be unlocked | |
1676 | * | |
1677 | * Unlock a routing table formerly locked by rt_lock_table(), | |
1678 | * that is decrease its use count and delete it if it's scheduled | |
1679 | * for deletion by configuration changes. | |
1680 | */ | |
50fe90ed MM |
1681 | void |
1682 | rt_unlock_table(rtable *r) | |
1683 | { | |
1684 | if (!--r->use_count && r->deleted) | |
1685 | { | |
1686 | struct config *conf = r->deleted; | |
1687 | DBG("Deleting routing table %s\n", r->name); | |
cfe34a31 OZ |
1688 | if (r->hostcache) |
1689 | rt_free_hostcache(r); | |
50fe90ed MM |
1690 | rem_node(&r->n); |
1691 | fib_free(&r->fib); | |
cfe34a31 | 1692 | rfree(r->rt_event); |
50fe90ed MM |
1693 | mb_free(r); |
1694 | config_del_obstacle(conf); | |
1695 | } | |
1696 | } | |
1697 | ||
58740ed4 MM |
1698 | /** |
1699 | * rt_commit - commit new routing table configuration | |
1700 | * @new: new configuration | |
1701 | * @old: original configuration or %NULL if it's boot time config | |
1702 | * | |
1703 | * Scan differences between @old and @new configuration and modify | |
1704 | * the routing tables according to these changes. If @new defines a | |
1705 | * previously unknown table, create it, if it omits a table existing | |
1706 | * in @old, schedule it for deletion (it gets deleted when all protocols | |
1707 | * disconnect from it by calling rt_unlock_table()), if it exists | |
1708 | * in both configurations, leave it unchanged. | |
1709 | */ | |
50fe90ed MM |
1710 | void |
1711 | rt_commit(struct config *new, struct config *old) | |
1712 | { | |
1713 | struct rtable_config *o, *r; | |
0e02abfd | 1714 | |
50fe90ed MM |
1715 | DBG("rt_commit:\n"); |
1716 | if (old) | |
0e02abfd | 1717 | { |
50fe90ed MM |
1718 | WALK_LIST(o, old->tables) |
1719 | { | |
1720 | rtable *ot = o->table; | |
1721 | if (!ot->deleted) | |
1722 | { | |
1723 | struct symbol *sym = cf_find_symbol(o->name); | |
bf8558bc | 1724 | if (sym && sym->class == SYM_TABLE && !new->shutdown) |
50fe90ed MM |
1725 | { |
1726 | DBG("\t%s: same\n", o->name); | |
1727 | r = sym->def; | |
1728 | r->table = ot; | |
1729 | ot->name = r->name; | |
b9626ec6 | 1730 | ot->config = r; |
26822d8f OZ |
1731 | if (o->sorted != r->sorted) |
1732 | log(L_WARN "Reconfiguration of rtable sorted flag not implemented"); | |
50fe90ed MM |
1733 | } |
1734 | else | |
1735 | { | |
bf8558bc | 1736 | DBG("\t%s: deleted\n", o->name); |
50fe90ed MM |
1737 | ot->deleted = old; |
1738 | config_add_obstacle(old); | |
1739 | rt_lock_table(ot); | |
1740 | rt_unlock_table(ot); | |
1741 | } | |
1742 | } | |
1743 | } | |
0e02abfd | 1744 | } |
50fe90ed MM |
1745 | |
1746 | WALK_LIST(r, new->tables) | |
1747 | if (!r->table) | |
1748 | { | |
1749 | rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable)); | |
1750 | DBG("\t%s: created\n", r->name); | |
b9626ec6 | 1751 | rt_setup(rt_table_pool, t, r->name, r); |
50fe90ed MM |
1752 | add_tail(&routing_tables, &t->n); |
1753 | r->table = t; | |
1754 | } | |
1755 | DBG("\tdone\n"); | |
0e02abfd | 1756 | } |
730f2e2c | 1757 | |
23ac9e9a OZ |
1758 | static inline void |
1759 | do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e) | |
1760 | { | |
23ac9e9a OZ |
1761 | ea_list *tmpa; |
1762 | ||
1763 | rte_update_lock(); | |
094d2bdb | 1764 | tmpa = make_tmp_attrs(e, rte_update_pool); |
00a09f3c OZ |
1765 | if (type == RA_ACCEPTED) |
1766 | rt_notify_accepted(h, n, e, NULL, NULL, tmpa, p->refeeding ? 2 : 1); | |
1767 | else | |
1768 | rt_notify_basic(h, n, e, p->refeeding ? e : NULL, tmpa, p->refeeding); | |
23ac9e9a OZ |
1769 | rte_update_unlock(); |
1770 | } | |
1771 | ||
58740ed4 MM |
1772 | /** |
1773 | * rt_feed_baby - advertise routes to a new protocol | |
1774 | * @p: protocol to be fed | |
1775 | * | |
1776 | * This function performs one pass of advertisement of routes to a newly | |
1777 | * initialized protocol. It's called by the protocol code as long as it | |
1778 | * has something to do. (We avoid transferring all the routes in single | |
1779 | * pass in order not to monopolize CPU time.) | |
1780 | */ | |
ac5d8012 MM |
1781 | int |
1782 | rt_feed_baby(struct proto *p) | |
1783 | { | |
1784 | struct announce_hook *h; | |
1785 | struct fib_iterator *fit; | |
76dfda9e | 1786 | int max_feed = 256; |
ac5d8012 MM |
1787 | |
1788 | if (!p->feed_ahook) /* Need to initialize first */ | |
1789 | { | |
1790 | if (!p->ahooks) | |
1791 | return 1; | |
1792 | DBG("Announcing routes to new protocol %s\n", p->name); | |
1793 | p->feed_ahook = p->ahooks; | |
1794 | fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator)); | |
1795 | goto next_hook; | |
1796 | } | |
1797 | fit = p->feed_iterator; | |
1798 | ||
1799 | again: | |
1800 | h = p->feed_ahook; | |
1801 | FIB_ITERATE_START(&h->table->fib, fit, fn) | |
1802 | { | |
1803 | net *n = (net *) fn; | |
258d0ad4 | 1804 | rte *e = n->routes; |
76dfda9e MM |
1805 | if (max_feed <= 0) |
1806 | { | |
1807 | FIB_ITERATE_PUT(fit, fn); | |
1808 | return 0; | |
1809 | } | |
23ac9e9a | 1810 | |
cf98be7b OZ |
1811 | /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */ |
1812 | ||
b7f3df79 OZ |
1813 | if ((p->accept_ra_types == RA_OPTIMAL) || |
1814 | (p->accept_ra_types == RA_ACCEPTED)) | |
cf98be7b | 1815 | if (rte_is_valid(e)) |
23ac9e9a | 1816 | { |
0c791f87 | 1817 | if (p->export_state != ES_FEEDING) |
23ac9e9a | 1818 | return 1; /* In the meantime, the protocol fell down. */ |
b7f3df79 | 1819 | do_feed_baby(p, p->accept_ra_types, h, n, e); |
23ac9e9a OZ |
1820 | max_feed--; |
1821 | } | |
1822 | ||
1823 | if (p->accept_ra_types == RA_ANY) | |
cf98be7b | 1824 | for(e = n->routes; rte_is_valid(e); e = e->next) |
23ac9e9a | 1825 | { |
0c791f87 | 1826 | if (p->export_state != ES_FEEDING) |
23ac9e9a OZ |
1827 | return 1; /* In the meantime, the protocol fell down. */ |
1828 | do_feed_baby(p, RA_ANY, h, n, e); | |
1829 | max_feed--; | |
1830 | } | |
ac5d8012 MM |
1831 | } |
1832 | FIB_ITERATE_END(fn); | |
1833 | p->feed_ahook = h->next; | |
1834 | if (!p->feed_ahook) | |
1835 | { | |
1836 | mb_free(p->feed_iterator); | |
1837 | p->feed_iterator = NULL; | |
1838 | return 1; | |
1839 | } | |
1840 | ||
1841 | next_hook: | |
1842 | h = p->feed_ahook; | |
1843 | FIB_ITERATE_INIT(fit, &h->table->fib); | |
1844 | goto again; | |
1845 | } | |
1846 | ||
58740ed4 MM |
1847 | /** |
1848 | * rt_feed_baby_abort - abort protocol feeding | |
1849 | * @p: protocol | |
1850 | * | |
1851 | * This function is called by the protocol code when the protocol | |
1852 | * stops or ceases to exist before the last iteration of rt_feed_baby() | |
1853 | * has finished. | |
1854 | */ | |
ac5d8012 MM |
1855 | void |
1856 | rt_feed_baby_abort(struct proto *p) | |
1857 | { | |
1858 | if (p->feed_ahook) | |
1859 | { | |
1860 | /* Unlink the iterator and exit */ | |
1861 | fit_get(&p->feed_ahook->table->fib, p->feed_iterator); | |
1862 | p->feed_ahook = NULL; | |
1863 | } | |
1864 | } | |
1865 | ||
f2b76f2c OZ |
1866 | |
1867 | static inline unsigned | |
1868 | ptr_hash(void *ptr) | |
1869 | { | |
1870 | uintptr_t p = (uintptr_t) ptr; | |
1871 | return p ^ (p << 8) ^ (p >> 16); | |
1872 | } | |
1873 | ||
1874 | static inline unsigned | |
1875 | hc_hash(ip_addr a, rtable *dep) | |
1876 | { | |
1877 | return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff; | |
1878 | } | |
1879 | ||
1880 | static inline void | |
1881 | hc_insert(struct hostcache *hc, struct hostentry *he) | |
1882 | { | |
1883 | unsigned int k = he->hash_key >> hc->hash_shift; | |
1884 | he->next = hc->hash_table[k]; | |
1885 | hc->hash_table[k] = he; | |
1886 | } | |
1887 | ||
1888 | static inline void | |
1889 | hc_remove(struct hostcache *hc, struct hostentry *he) | |
1890 | { | |
1891 | struct hostentry **hep; | |
1892 | unsigned int k = he->hash_key >> hc->hash_shift; | |
1893 | ||
1894 | for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next); | |
1895 | *hep = he->next; | |
1896 | } | |
1897 | ||
1898 | #define HC_DEF_ORDER 10 | |
1899 | #define HC_HI_MARK *4 | |
1900 | #define HC_HI_STEP 2 | |
1901 | #define HC_HI_ORDER 16 /* Must be at most 16 */ | |
1902 | #define HC_LO_MARK /5 | |
1903 | #define HC_LO_STEP 2 | |
1904 | #define HC_LO_ORDER 10 | |
1905 | ||
1906 | static void | |
1907 | hc_alloc_table(struct hostcache *hc, unsigned order) | |
1908 | { | |
1909 | unsigned hsize = 1 << order; | |
1910 | hc->hash_order = order; | |
1911 | hc->hash_shift = 16 - order; | |
1912 | hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK); | |
1913 | hc->hash_min = (order <= HC_LO_ORDER) ? 0 : (hsize HC_LO_MARK); | |
1914 | ||
1915 | hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *)); | |
1916 | } | |
1917 | ||
cfe34a31 | 1918 | static void |
f2b76f2c | 1919 | hc_resize(struct hostcache *hc, unsigned new_order) |
cfe34a31 | 1920 | { |
f2b76f2c OZ |
1921 | unsigned old_size = 1 << hc->hash_order; |
1922 | struct hostentry **old_table = hc->hash_table; | |
1923 | struct hostentry *he, *hen; | |
1924 | int i; | |
1925 | ||
1926 | hc_alloc_table(hc, new_order); | |
1927 | for (i = 0; i < old_size; i++) | |
1928 | for (he = old_table[i]; he != NULL; he=hen) | |
1929 | { | |
1930 | hen = he->next; | |
1931 | hc_insert(hc, he); | |
1932 | } | |
1933 | mb_free(old_table); | |
1934 | } | |
1935 | ||
1936 | static struct hostentry * | |
1b180121 | 1937 | hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k) |
f2b76f2c OZ |
1938 | { |
1939 | struct hostentry *he = sl_alloc(hc->slab); | |
1940 | ||
1941 | he->addr = a; | |
1b180121 | 1942 | he->link = ll; |
f2b76f2c OZ |
1943 | he->tab = dep; |
1944 | he->hash_key = k; | |
1945 | he->uc = 0; | |
7e95c05d | 1946 | he->src = NULL; |
f2b76f2c OZ |
1947 | |
1948 | add_tail(&hc->hostentries, &he->ln); | |
1949 | hc_insert(hc, he); | |
1950 | ||
1951 | hc->hash_items++; | |
1952 | if (hc->hash_items > hc->hash_max) | |
1953 | hc_resize(hc, hc->hash_order + HC_HI_STEP); | |
1954 | ||
1955 | return he; | |
1956 | } | |
1957 | ||
1958 | static void | |
1959 | hc_delete_hostentry(struct hostcache *hc, struct hostentry *he) | |
1960 | { | |
7e95c05d OZ |
1961 | rta_free(he->src); |
1962 | ||
f2b76f2c OZ |
1963 | rem_node(&he->ln); |
1964 | hc_remove(hc, he); | |
1965 | sl_free(hc->slab, he); | |
1966 | ||
1967 | hc->hash_items--; | |
1968 | if (hc->hash_items < hc->hash_min) | |
1969 | hc_resize(hc, hc->hash_order - HC_LO_STEP); | |
cfe34a31 OZ |
1970 | } |
1971 | ||
1972 | static void | |
1973 | rt_init_hostcache(rtable *tab) | |
1974 | { | |
1975 | struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache)); | |
1976 | init_list(&hc->hostentries); | |
f2b76f2c OZ |
1977 | |
1978 | hc->hash_items = 0; | |
1979 | hc_alloc_table(hc, HC_DEF_ORDER); | |
1980 | hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry)); | |
1981 | ||
c477f489 | 1982 | hc->lp = lp_new(rt_table_pool, 1008); |
51762a45 | 1983 | hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node)); |
c477f489 | 1984 | |
cfe34a31 OZ |
1985 | tab->hostcache = hc; |
1986 | } | |
1987 | ||
1988 | static void | |
1989 | rt_free_hostcache(rtable *tab) | |
1990 | { | |
1991 | struct hostcache *hc = tab->hostcache; | |
1992 | ||
1993 | node *n; | |
1994 | WALK_LIST(n, hc->hostentries) | |
1995 | { | |
1996 | struct hostentry *he = SKIP_BACK(struct hostentry, ln, n); | |
7e95c05d OZ |
1997 | rta_free(he->src); |
1998 | ||
cfe34a31 OZ |
1999 | if (he->uc) |
2000 | log(L_ERR "Hostcache is not empty in table %s", tab->name); | |
2001 | } | |
2002 | ||
f2b76f2c | 2003 | rfree(hc->slab); |
c477f489 | 2004 | rfree(hc->lp); |
f2b76f2c | 2005 | mb_free(hc->hash_table); |
cfe34a31 OZ |
2006 | mb_free(hc); |
2007 | } | |
2008 | ||
2009 | static void | |
2010 | rt_notify_hostcache(rtable *tab, net *net) | |
2011 | { | |
2012 | struct hostcache *hc = tab->hostcache; | |
2013 | ||
2014 | if (tab->hcu_scheduled) | |
2015 | return; | |
2016 | ||
c477f489 OZ |
2017 | if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen)) |
2018 | rt_schedule_hcu(tab); | |
cfe34a31 OZ |
2019 | } |
2020 | ||
2021 | static int | |
2022 | if_local_addr(ip_addr a, struct iface *i) | |
2023 | { | |
2024 | struct ifa *b; | |
2025 | ||
2026 | WALK_LIST(b, i->addrs) | |
2027 | if (ipa_equal(a, b->ip)) | |
2028 | return 1; | |
2029 | ||
2030 | return 0; | |
2031 | } | |
2032 | ||
d1e146f2 OZ |
2033 | static u32 |
2034 | rt_get_igp_metric(rte *rt) | |
2035 | { | |
ba5e5940 OZ |
2036 | eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC); |
2037 | ||
2038 | if (ea) | |
2039 | return ea->u.data; | |
2040 | ||
d1e146f2 | 2041 | rta *a = rt->attrs; |
b7c48981 OF |
2042 | |
2043 | #ifdef CONFIG_OSPF | |
d1e146f2 OZ |
2044 | if ((a->source == RTS_OSPF) || |
2045 | (a->source == RTS_OSPF_IA) || | |
2046 | (a->source == RTS_OSPF_EXT1)) | |
2047 | return rt->u.ospf.metric1; | |
b7c48981 | 2048 | #endif |
d1e146f2 | 2049 | |
b7c48981 | 2050 | #ifdef CONFIG_RIP |
d1e146f2 OZ |
2051 | if (a->source == RTS_RIP) |
2052 | return rt->u.rip.metric; | |
b7c48981 | 2053 | #endif |
d1e146f2 OZ |
2054 | |
2055 | /* Device routes */ | |
7e95c05d | 2056 | if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH)) |
d1e146f2 OZ |
2057 | return 0; |
2058 | ||
2059 | return IGP_METRIC_UNKNOWN; | |
2060 | } | |
2061 | ||
cfe34a31 OZ |
2062 | static int |
2063 | rt_update_hostentry(rtable *tab, struct hostentry *he) | |
2064 | { | |
7e95c05d | 2065 | rta *old_src = he->src; |
c477f489 | 2066 | int pxlen = 0; |
cfe34a31 | 2067 | |
7e95c05d OZ |
2068 | /* Reset the hostentry */ |
2069 | he->src = NULL; | |
2070 | he->gw = IPA_NONE; | |
2071 | he->dest = RTD_UNREACHABLE; | |
2072 | he->igp_metric = 0; | |
2073 | ||
d1e146f2 OZ |
2074 | net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH); |
2075 | if (n) | |
cfe34a31 | 2076 | { |
cf98be7b OZ |
2077 | rte *e = n->routes; |
2078 | rta *a = e->attrs; | |
c477f489 | 2079 | pxlen = n->n.pxlen; |
cfe34a31 | 2080 | |
2c9033af OZ |
2081 | if (a->hostentry) |
2082 | { | |
2083 | /* Recursive route should not depend on another recursive route */ | |
2084 | log(L_WARN "Next hop address %I resolvable through recursive route for %I/%d", | |
7e95c05d OZ |
2085 | he->addr, n->n.prefix, pxlen); |
2086 | goto done; | |
2c9033af | 2087 | } |
7e95c05d OZ |
2088 | |
2089 | if (a->dest == RTD_DEVICE) | |
cfe34a31 | 2090 | { |
f2b76f2c | 2091 | if (if_local_addr(he->addr, a->iface)) |
cfe34a31 OZ |
2092 | { |
2093 | /* The host address is a local address, this is not valid */ | |
2094 | log(L_WARN "Next hop address %I is a local address of iface %s", | |
f2b76f2c | 2095 | he->addr, a->iface->name); |
7e95c05d | 2096 | goto done; |
cfe34a31 | 2097 | } |
7e95c05d OZ |
2098 | |
2099 | /* The host is directly reachable, use link as a gateway */ | |
2100 | he->gw = he->link; | |
2101 | he->dest = RTD_ROUTER; | |
cfe34a31 OZ |
2102 | } |
2103 | else | |
2104 | { | |
2105 | /* The host is reachable through some route entry */ | |
cfe34a31 OZ |
2106 | he->gw = a->gw; |
2107 | he->dest = a->dest; | |
2108 | } | |
d1e146f2 | 2109 | |
7e95c05d | 2110 | he->src = rta_clone(a); |
cf98be7b | 2111 | he->igp_metric = rt_get_igp_metric(e); |
cfe34a31 OZ |
2112 | } |
2113 | ||
7e95c05d | 2114 | done: |
c477f489 OZ |
2115 | /* Add a prefix range to the trie */ |
2116 | trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH); | |
2117 | ||
7e95c05d OZ |
2118 | rta_free(old_src); |
2119 | return old_src != he->src; | |
cfe34a31 OZ |
2120 | } |
2121 | ||
2122 | static void | |
2123 | rt_update_hostcache(rtable *tab) | |
2124 | { | |
2125 | struct hostcache *hc = tab->hostcache; | |
2126 | struct hostentry *he; | |
2127 | node *n, *x; | |
2128 | ||
c477f489 OZ |
2129 | /* Reset the trie */ |
2130 | lp_flush(hc->lp); | |
51762a45 | 2131 | hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node)); |
c477f489 | 2132 | |
cfe34a31 OZ |
2133 | WALK_LIST_DELSAFE(n, x, hc->hostentries) |
2134 | { | |
2135 | he = SKIP_BACK(struct hostentry, ln, n); | |
2136 | if (!he->uc) | |
2137 | { | |
f2b76f2c | 2138 | hc_delete_hostentry(hc, he); |
cfe34a31 OZ |
2139 | continue; |
2140 | } | |
2141 | ||
2142 | if (rt_update_hostentry(tab, he)) | |
2143 | rt_schedule_nhu(he->tab); | |
2144 | } | |
2145 | ||
2146 | tab->hcu_scheduled = 0; | |
2147 | } | |
2148 | ||
2149 | static struct hostentry * | |
094d2bdb | 2150 | rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep) |
cfe34a31 OZ |
2151 | { |
2152 | struct hostentry *he; | |
2153 | ||
2154 | if (!tab->hostcache) | |
2155 | rt_init_hostcache(tab); | |
2156 | ||
f2b76f2c OZ |
2157 | unsigned int k = hc_hash(a, dep); |
2158 | struct hostcache *hc = tab->hostcache; | |
2159 | for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next) | |
2160 | if (ipa_equal(he->addr, a) && (he->tab == dep)) | |
2161 | return he; | |
cfe34a31 | 2162 | |
1b180121 | 2163 | he = hc_new_hostentry(hc, a, ll, dep, k); |
f2b76f2c | 2164 | rt_update_hostentry(tab, he); |
cfe34a31 OZ |
2165 | return he; |
2166 | } | |
2167 | ||
2168 | void | |
1b180121 | 2169 | rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll) |
cfe34a31 | 2170 | { |
094d2bdb | 2171 | rta_apply_hostentry(a, rt_get_hostentry(tab, *gw, *ll, dep)); |
cfe34a31 OZ |
2172 | } |
2173 | ||
094d2bdb | 2174 | |
730f2e2c MM |
2175 | /* |
2176 | * CLI commands | |
2177 | */ | |
2178 | ||
2179 | static void | |
cfd46ee4 | 2180 | rt_format_via(rte *e, byte *via) |
730f2e2c | 2181 | { |
730f2e2c MM |
2182 | rta *a = e->attrs; |
2183 | ||
2184 | switch (a->dest) | |
2185 | { | |
2186 | case RTD_ROUTER: bsprintf(via, "via %I on %s", a->gw, a->iface->name); break; | |
2187 | case RTD_DEVICE: bsprintf(via, "dev %s", a->iface->name); break; | |
2188 | case RTD_BLACKHOLE: bsprintf(via, "blackhole"); break; | |
2189 | case RTD_UNREACHABLE: bsprintf(via, "unreachable"); break; | |
2190 | case RTD_PROHIBIT: bsprintf(via, "prohibited"); break; | |
7e95c05d | 2191 | case RTD_MULTIPATH: bsprintf(via, "multipath"); break; |
730f2e2c MM |
2192 | default: bsprintf(via, "???"); |
2193 | } | |
cfd46ee4 MM |
2194 | } |
2195 | ||
2196 | static void | |
ce1da96e | 2197 | rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa) |
cfd46ee4 | 2198 | { |
4ca93a50 | 2199 | byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8]; |
c37e7851 | 2200 | byte tm[TM_DATETIME_BUFFER_SIZE], info[256]; |
cfd46ee4 | 2201 | rta *a = e->attrs; |
5a56f27c | 2202 | int primary = (e->net->routes == e); |
32f95476 | 2203 | int sync_error = (e->net->n.flags & KRF_SYNC_ERROR); |
094d2bdb | 2204 | void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs); |
7e95c05d | 2205 | struct mpnh *nh; |
cfd46ee4 MM |
2206 | |
2207 | rt_format_via(e, via); | |
c37e7851 | 2208 | tm_format_datetime(tm, &config->tf_route, e->lastmod); |
730f2e2c MM |
2209 | if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw)) |
2210 | bsprintf(from, " from %I", a->from); | |
2211 | else | |
2212 | from[0] = 0; | |
094d2bdb OZ |
2213 | |
2214 | get_route_info = a->src->proto->proto->get_route_info; | |
2215 | if (get_route_info || d->verbose) | |
ce1da96e MM |
2216 | { |
2217 | /* Need to normalize the extended attributes */ | |
2218 | ea_list *t = tmpa; | |
2219 | t = ea_append(t, a->eattrs); | |
2220 | tmpa = alloca(ea_scan(t)); | |
2221 | ea_merge(t, tmpa); | |
2f711231 | 2222 | ea_sort(tmpa); |
ce1da96e | 2223 | } |
094d2bdb OZ |
2224 | if (get_route_info) |
2225 | get_route_info(e, info, tmpa); | |
730f2e2c MM |
2226 | else |
2227 | bsprintf(info, " (%d)", e->pref); | |
094d2bdb | 2228 | cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->src->proto->name, |
32f95476 | 2229 | tm, from, primary ? (sync_error ? " !" : " *") : "", info); |
7e95c05d OZ |
2230 | for (nh = a->nexthops; nh; nh = nh->next) |
2231 | cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1); | |
730f2e2c | 2232 | if (d->verbose) |
ce1da96e | 2233 | rta_show(c, a, tmpa); |
730f2e2c MM |
2234 | } |
2235 | ||
2236 | static void | |
2237 | rt_show_net(struct cli *c, net *n, struct rt_show_data *d) | |
2238 | { | |
2239 | rte *e, *ee; | |
2240 | byte ia[STD_ADDRESS_P_LENGTH+8]; | |
c865cae3 OZ |
2241 | struct ea_list *tmpa; |
2242 | struct announce_hook *a = NULL; | |
2243 | int first = 1; | |
2244 | int pass = 0; | |
730f2e2c MM |
2245 | |
2246 | bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen); | |
cf98be7b | 2247 | |
c865cae3 OZ |
2248 | if (d->export_mode) |
2249 | { | |
7aa80901 OZ |
2250 | if (! d->export_protocol->rt_notify) |
2251 | return; | |
2252 | ||
c865cae3 OZ |
2253 | a = proto_find_announce_hook(d->export_protocol, d->table); |
2254 | if (!a) | |
2255 | return; | |
2256 | } | |
2257 | ||
2258 | for (e = n->routes; e; e = e->next) | |
730f2e2c | 2259 | { |
15550957 | 2260 | if (rte_is_filtered(e) != d->filtered) |
cf98be7b OZ |
2261 | continue; |
2262 | ||
23693958 | 2263 | d->rt_counter++; |
c865cae3 OZ |
2264 | d->net_counter += first; |
2265 | first = 0; | |
2266 | ||
2267 | if (pass) | |
2268 | continue; | |
2269 | ||
730f2e2c MM |
2270 | ee = e; |
2271 | rte_update_lock(); /* We use the update buffer for filtering */ | |
094d2bdb | 2272 | tmpa = make_tmp_attrs(e, rte_update_pool); |
c865cae3 OZ |
2273 | |
2274 | if (d->export_mode) | |
ce1da96e | 2275 | { |
c865cae3 OZ |
2276 | struct proto *ep = d->export_protocol; |
2277 | int ic = ep->import_control ? ep->import_control(ep, &e, &tmpa, rte_update_pool) : 0; | |
2278 | ||
2279 | if (ep->accept_ra_types == RA_OPTIMAL) | |
2280 | pass = 1; | |
2281 | ||
2282 | if (ic < 0) | |
2283 | goto skip; | |
2284 | ||
7aa80901 | 2285 | if (d->export_mode > RSEM_PREEXPORT) |
ce1da96e | 2286 | { |
c865cae3 OZ |
2287 | /* |
2288 | * FIXME - This shows what should be exported according to current | |
2289 | * filters, but not what was really exported. 'configure soft' | |
2290 | * command may change the export filter and do not update routes. | |
2291 | */ | |
7aa80901 OZ |
2292 | int do_export = (ic > 0) || |
2293 | (f_run(a->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT); | |
c865cae3 | 2294 | |
7aa80901 | 2295 | if (do_export != (d->export_mode == RSEM_EXPORT)) |
c865cae3 OZ |
2296 | goto skip; |
2297 | ||
7aa80901 | 2298 | if ((d->export_mode == RSEM_EXPORT) && (ep->accept_ra_types == RA_ACCEPTED)) |
c865cae3 | 2299 | pass = 1; |
ce1da96e MM |
2300 | } |
2301 | } | |
c865cae3 OZ |
2302 | |
2303 | if (d->show_protocol && (d->show_protocol != e->attrs->src->proto)) | |
2304 | goto skip; | |
2305 | ||
2306 | if (f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT) | |
2307 | goto skip; | |
2308 | ||
2309 | d->show_counter++; | |
2310 | if (d->stats < 2) | |
2311 | rt_show_rte(c, ia, e, d, tmpa); | |
2312 | ia[0] = 0; | |
2313 | ||
2314 | skip: | |
730f2e2c | 2315 | if (e != ee) |
5e9bdac2 OZ |
2316 | { |
2317 | rte_free(e); | |
2318 | e = ee; | |
2319 | } | |
730f2e2c | 2320 | rte_update_unlock(); |
c865cae3 | 2321 | |
0117d004 | 2322 | if (d->primary_only) |
ce1da96e | 2323 | break; |
730f2e2c MM |
2324 | } |
2325 | } | |
2326 | ||
2327 | static void | |
2328 | rt_show_cont(struct cli *c) | |
2329 | { | |
2330 | struct rt_show_data *d = c->rover; | |
f098e072 MM |
2331 | #ifdef DEBUGGING |
2332 | unsigned max = 4; | |
2333 | #else | |
2334 | unsigned max = 64; | |
2335 | #endif | |
730f2e2c MM |
2336 | struct fib *fib = &d->table->fib; |
2337 | struct fib_iterator *it = &d->fit; | |
2338 | ||
2339 | FIB_ITERATE_START(fib, it, f) | |
2340 | { | |
2341 | net *n = (net *) f; | |
ce1da96e MM |
2342 | if (d->running_on_config && d->running_on_config != config) |
2343 | { | |
2344 | cli_printf(c, 8004, "Stopped due to reconfiguration"); | |
2345 | goto done; | |
2346 | } | |
0c791f87 | 2347 | if (d->export_protocol && (d->export_protocol->export_state == ES_DOWN)) |
ce1da96e MM |
2348 | { |
2349 | cli_printf(c, 8005, "Protocol is down"); | |
2350 | goto done; | |
2351 | } | |
730f2e2c MM |
2352 | if (!max--) |
2353 | { | |
2354 | FIB_ITERATE_PUT(it, f); | |
2355 | return; | |
2356 | } | |
2357 | rt_show_net(c, n, d); | |
2358 | } | |
2359 | FIB_ITERATE_END(f); | |
23693958 MM |
2360 | if (d->stats) |
2361 | cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter); | |
2362 | else | |
2363 | cli_printf(c, 0, ""); | |
ce1da96e | 2364 | done: |
730f2e2c MM |
2365 | c->cont = c->cleanup = NULL; |
2366 | } | |
2367 | ||
2368 | static void | |
2369 | rt_show_cleanup(struct cli *c) | |
2370 | { | |
2371 | struct rt_show_data *d = c->rover; | |
2372 | ||
2373 | /* Unlink the iterator */ | |
2374 | fit_get(&d->table->fib, &d->fit); | |
2375 | } | |
2376 | ||
2377 | void | |
2378 | rt_show(struct rt_show_data *d) | |
2379 | { | |
730f2e2c MM |
2380 | net *n; |
2381 | ||
e667622a | 2382 | /* Default is either a master table or a table related to a respective protocol */ |
c865cae3 OZ |
2383 | if (!d->table && d->export_protocol) d->table = d->export_protocol->table; |
2384 | if (!d->table && d->show_protocol) d->table = d->show_protocol->table; | |
e667622a OF |
2385 | if (!d->table) d->table = config->master_rtc->table; |
2386 | ||
c865cae3 OZ |
2387 | /* Filtered routes are neither exported nor have sensible ordering */ |
2388 | if (d->filtered && (d->export_mode || d->primary_only)) | |
2389 | cli_msg(0, ""); | |
2390 | ||
730f2e2c MM |
2391 | if (d->pxlen == 256) |
2392 | { | |
2393 | FIB_ITERATE_INIT(&d->fit, &d->table->fib); | |
2394 | this_cli->cont = rt_show_cont; | |
2395 | this_cli->cleanup = rt_show_cleanup; | |
2396 | this_cli->rover = d; | |
2397 | } | |
2398 | else | |
2399 | { | |
9449c91a | 2400 | if (d->show_for) |
d1e146f2 | 2401 | n = net_route(d->table, d->prefix, d->pxlen); |
9449c91a | 2402 | else |
d1e146f2 | 2403 | n = net_find(d->table, d->prefix, d->pxlen); |
0da562a7 | 2404 | |
730f2e2c | 2405 | if (n) |
0da562a7 OZ |
2406 | rt_show_net(this_cli, n, d); |
2407 | ||
2408 | if (d->rt_counter) | |
2409 | cli_msg(0, ""); | |
730f2e2c MM |
2410 | else |
2411 | cli_msg(8001, "Network not in table"); | |
2412 | } | |
2413 | } | |
3ce8c610 MM |
2414 | |
2415 | /* | |
2416 | * Documentation for functions declared inline in route.h | |
2417 | */ | |
2418 | #if 0 | |
2419 | ||
2420 | /** | |
2421 | * net_find - find a network entry | |
2422 | * @tab: a routing table | |
2423 | * @addr: address of the network | |
2424 | * @len: length of the network prefix | |
2425 | * | |
2426 | * net_find() looks up the given network in routing table @tab and | |
2427 | * returns a pointer to its &net entry or %NULL if no such network | |
2428 | * exists. | |
2429 | */ | |
2430 | static inline net *net_find(rtable *tab, ip_addr addr, unsigned len) | |
2431 | { DUMMY; } | |
2432 | ||
2433 | /** | |
2434 | * net_get - obtain a network entry | |
2435 | * @tab: a routing table | |
2436 | * @addr: address of the network | |
2437 | * @len: length of the network prefix | |
2438 | * | |
2439 | * net_get() looks up the given network in routing table @tab and | |
2440 | * returns a pointer to its &net entry. If no such entry exists, it's | |
2441 | * created. | |
2442 | */ | |
2443 | static inline net *net_get(rtable *tab, ip_addr addr, unsigned len) | |
2444 | { DUMMY; } | |
2445 | ||
2446 | /** | |
2447 | * rte_cow - copy a route for writing | |
2448 | * @r: a route entry to be copied | |
2449 | * | |
2450 | * rte_cow() takes a &rte and prepares it for modification. The exact action | |
2451 | * taken depends on the flags of the &rte -- if it's a temporary entry, it's | |
2452 | * just returned unchanged, else a new temporary entry with the same contents | |
2453 | * is created. | |
2454 | * | |
2455 | * The primary use of this function is inside the filter machinery -- when | |
2456 | * a filter wants to modify &rte contents (to change the preference or to | |
2457 | * attach another set of attributes), it must ensure that the &rte is not | |
2458 | * shared with anyone else (and especially that it isn't stored in any routing | |
2459 | * table). | |
2460 | * | |
2e9b2421 | 2461 | * Result: a pointer to the new writable &rte. |
3ce8c610 MM |
2462 | */ |
2463 | static inline rte * rte_cow(rte *r) | |
2464 | { DUMMY; } | |
2465 | ||
2466 | #endif |