]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-table.c
ae4bb74d1b536c20daabaadc2cc047192add65d8
2 * BIRD -- Routing Tables
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
12 * Routing tables are probably the most important structures BIRD uses. They
13 * hold all the information about known networks, the associated routes and
16 * There are multiple routing tables (a primary one together with any
17 * number of secondary ones if requested by the configuration). Each table
18 * is basically a FIB containing entries describing the individual
19 * destination networks. For each network (represented by structure &net),
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
22 * for routing), the order of the other ones is undetermined.
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.
33 #include "nest/bird.h"
34 #include "nest/route.h"
35 #include "nest/protocol.h"
36 #include "nest/iface.h"
37 #include "lib/resource.h"
38 #include "lib/event.h"
39 #include "lib/string.h"
40 #include "conf/conf.h"
41 #include "filter/filter.h"
43 #include "lib/string.h"
44 #include "lib/alloca.h"
48 static slab
*rte_slab
;
49 static linpool
*rte_update_pool
;
53 static void rt_free_hostcache(rtable
*tab
);
54 static void rt_notify_hostcache(rtable
*tab
, net
*net
);
55 static void rt_update_hostcache(rtable
*tab
);
56 static void rt_next_hop_update(rtable
*tab
);
57 static inline void rt_prune_table(rtable
*tab
);
60 /* Like fib_route(), but skips empty net entries */
62 net_route_ip4(rtable
*t
, net_addr_ip4
*n
)
66 while (r
= net_find_valid(t
, (net_addr
*) n
), (!r
) && (n
->pxlen
> 0))
69 ip4_clrbit(&n
->prefix
, n
->pxlen
);
76 net_route_ip6(rtable
*t
, net_addr_ip6
*n
)
80 while (r
= net_find_valid(t
, (net_addr
*) n
), (!r
) && (n
->pxlen
> 0))
83 ip6_clrbit(&n
->prefix
, n
->pxlen
);
90 net_route_ip6_sadr(rtable
*t
, net_addr_ip6_sadr
*n
)
99 /* We need to do dst first matching. Since sadr addresses are hashed on dst
100 prefix only, find the hash table chain and go through it to find the
101 match with the smallest matching src prefix. */
102 for (fn
= fib_get_chain(&t
->fib
, (net_addr
*) n
); fn
; fn
= fn
->next
)
104 net_addr_ip6_sadr
*a
= (void *) fn
->addr
;
106 if (net_equal_dst_ip6_sadr(n
, a
) &&
107 net_in_net_src_ip6_sadr(n
, a
) &&
108 (a
->src_pxlen
>= best_pxlen
))
110 best
= fib_node_to_user(&t
->fib
, fn
);
111 best_pxlen
= a
->src_pxlen
;
122 ip6_clrbit(&n
->dst_prefix
, n
->dst_pxlen
);
129 net_route(rtable
*tab
, const net_addr
*n
)
131 ASSERT(tab
->addr_type
== n
->type
);
133 net_addr
*n0
= alloca(n
->length
);
141 return net_route_ip4(tab
, (net_addr_ip4
*) n0
);
146 return net_route_ip6(tab
, (net_addr_ip6
*) n0
);
149 return net_route_ip6_sadr(tab
, (net_addr_ip6_sadr
*) n0
);
158 net_roa_check_ip4(rtable
*tab
, const net_addr_ip4
*px
, u32 asn
)
160 struct net_addr_roa4 n
= NET_ADDR_ROA4(px
->prefix
, px
->pxlen
, 0, 0);
166 for (fn
= fib_get_chain(&tab
->fib
, (net_addr
*) &n
); fn
; fn
= fn
->next
)
168 net_addr_roa4
*roa
= (void *) fn
->addr
;
169 net
*r
= fib_node_to_user(&tab
->fib
, fn
);
171 if (net_equal_prefix_roa4(roa
, &n
) && rte_is_valid(r
->routes
))
174 if (asn
&& (roa
->asn
== asn
) && (roa
->max_pxlen
>= px
->pxlen
))
183 ip4_clrbit(&n
.prefix
, n
.pxlen
);
186 return anything
? ROA_INVALID
: ROA_UNKNOWN
;
190 net_roa_check_ip6(rtable
*tab
, const net_addr_ip6
*px
, u32 asn
)
192 struct net_addr_roa6 n
= NET_ADDR_ROA6(px
->prefix
, px
->pxlen
, 0, 0);
198 for (fn
= fib_get_chain(&tab
->fib
, (net_addr
*) &n
); fn
; fn
= fn
->next
)
200 net_addr_roa6
*roa
= (void *) fn
->addr
;
201 net
*r
= fib_node_to_user(&tab
->fib
, fn
);
203 if (net_equal_prefix_roa6(roa
, &n
) && rte_is_valid(r
->routes
))
206 if (asn
&& (roa
->asn
== asn
) && (roa
->max_pxlen
>= px
->pxlen
))
215 ip6_clrbit(&n
.prefix
, n
.pxlen
);
218 return anything
? ROA_INVALID
: ROA_UNKNOWN
;
222 * roa_check - check validity of route origination in a ROA table
224 * @n: network prefix to check
225 * @asn: AS number of network prefix
227 * Implements RFC 6483 route validation for the given network prefix. The
228 * procedure is to find all candidate ROAs - ROAs whose prefixes cover the given
229 * network prefix. If there is no candidate ROA, return ROA_UNKNOWN. If there is
230 * a candidate ROA with matching ASN and maxlen field greater than or equal to
231 * the given prefix length, return ROA_VALID. Otherwise, return ROA_INVALID. If
232 * caller cannot determine origin AS, 0 could be used (in that case ROA_VALID
233 * cannot happen). Table @tab must have type NET_ROA4 or NET_ROA6, network @n
234 * must have type NET_IP4 or NET_IP6, respectively.
237 net_roa_check(rtable
*tab
, const net_addr
*n
, u32 asn
)
239 if ((tab
->addr_type
== NET_ROA4
) && (n
->type
== NET_IP4
))
240 return net_roa_check_ip4(tab
, (const net_addr_ip4
*) n
, asn
);
241 else if ((tab
->addr_type
== NET_ROA6
) && (n
->type
== NET_IP6
))
242 return net_roa_check_ip6(tab
, (const net_addr_ip6
*) n
, asn
);
244 return ROA_UNKNOWN
; /* Should not happen */
248 * rte_find - find a route
252 * The rte_find() function returns a route for destination @net
253 * which is from route source @src.
256 rte_find(net
*net
, struct rte_src
*src
)
258 rte
*e
= net
->routes
;
260 while (e
&& e
->attrs
->src
!= src
)
266 * rte_get_temp - get a temporary &rte
267 * @a: attributes to assign to the new route (a &rta; in case it's
268 * un-cached, rte_update() will create a cached copy automatically)
270 * Create a temporary &rte and bind it with the attributes @a.
271 * Also set route preference to the default preference set for
277 rte
*e
= sl_alloc(rte_slab
);
288 rte
*e
= sl_alloc(rte_slab
);
290 memcpy(e
, r
, sizeof(rte
));
291 e
->attrs
= rta_clone(r
->attrs
);
297 * rte_cow_rta - get a private writable copy of &rte with writable &rta
298 * @r: a route entry to be copied
299 * @lp: a linpool from which to allocate &rta
301 * rte_cow_rta() takes a &rte and prepares it and associated &rta for
302 * modification. There are three possibilities: First, both &rte and &rta are
303 * private copies, in that case they are returned unchanged. Second, &rte is
304 * private copy, but &rta is cached, in that case &rta is duplicated using
305 * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
306 * both structures are duplicated by rte_do_cow() and rta_do_cow().
308 * Note that in the second case, cached &rta loses one reference, while private
309 * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
310 * nexthops, ...) with it. To work properly, original shared &rta should have
311 * another reference during the life of created private copy.
313 * Result: a pointer to the new writable &rte with writable &rta.
316 rte_cow_rta(rte
*r
, linpool
*lp
)
318 if (!rta_is_cached(r
->attrs
))
322 rta
*a
= rta_do_cow(r
->attrs
, lp
);
328 static int /* Actually better or at least as good as */
329 rte_better(rte
*new, rte
*old
)
331 int (*better
)(rte
*, rte
*);
333 if (!rte_is_valid(old
))
335 if (!rte_is_valid(new))
338 if (new->pref
> old
->pref
)
340 if (new->pref
< old
->pref
)
342 if (new->attrs
->src
->proto
->proto
!= old
->attrs
->src
->proto
->proto
)
345 * If the user has configured protocol preferences, so that two different protocols
346 * have the same preference, try to break the tie by comparing addresses. Not too
347 * useful, but keeps the ordering of routes unambiguous.
349 return new->attrs
->src
->proto
->proto
> old
->attrs
->src
->proto
->proto
;
351 if (better
= new->attrs
->src
->proto
->rte_better
)
352 return better(new, old
);
357 rte_mergable(rte
*pri
, rte
*sec
)
359 int (*mergable
)(rte
*, rte
*);
361 if (!rte_is_valid(pri
) || !rte_is_valid(sec
))
364 if (pri
->pref
!= sec
->pref
)
367 if (pri
->attrs
->src
->proto
->proto
!= sec
->attrs
->src
->proto
->proto
)
370 if (mergable
= pri
->attrs
->src
->proto
->rte_mergable
)
371 return mergable(pri
, sec
);
377 rte_trace(struct proto
*p
, rte
*e
, int dir
, char *msg
)
379 log(L_TRACE
"%s %c %s %N %s", p
->name
, dir
, msg
, e
->net
->n
.addr
, rta_dest_name(e
->attrs
->dest
));
383 rte_trace_in(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
386 rte_trace(p
, e
, '>', msg
);
390 rte_trace_out(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
393 rte_trace(p
, e
, '<', msg
);
397 export_filter_(struct channel
*c
, rte
*rt0
, rte
**rt_free
, linpool
*pool
, int silent
)
399 struct proto
*p
= c
->proto
;
400 struct filter
*filter
= c
->out_filter
;
401 struct proto_stats
*stats
= &c
->stats
;
408 rte_make_tmp_attrs(&rt
, pool
);
410 v
= p
->preexport
? p
->preexport(p
, &rt
, pool
) : 0;
416 stats
->exp_updates_rejected
++;
418 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
424 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
428 v
= filter
&& ((filter
== FILTER_REJECT
) ||
429 (f_run(filter
, &rt
, pool
,
430 (silent
? FF_SILENT
: 0)) > F_ACCEPT
));
436 stats
->exp_updates_filtered
++;
437 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
447 /* Discard temporary rte */
454 export_filter(struct channel
*c
, rte
*rt0
, rte
**rt_free
, int silent
)
456 return export_filter_(c
, rt0
, rt_free
, rte_update_pool
, silent
);
460 do_rt_notify(struct channel
*c
, net
*net
, rte
*new, rte
*old
, int refeed
)
462 struct proto
*p
= c
->proto
;
463 struct proto_stats
*stats
= &c
->stats
;
467 * First, apply export limit.
469 * Export route limits has several problems. Because exp_routes
470 * counter is reset before refeed, we don't really know whether
471 * limit is breached and whether the update is new or not. Therefore
472 * the number of really exported routes may exceed the limit
473 * temporarily (routes exported before and new routes in refeed).
475 * Minor advantage is that if the limit is decreased and refeed is
476 * requested, the number of exported routes really decrease.
478 * Second problem is that with export limits, we don't know whether
479 * old was really exported (it might be blocked by limit). When a
480 * withdraw is exported, we announce it even when the previous
481 * update was blocked. This is not a big issue, but the same problem
482 * is in updating exp_routes counter. Therefore, to be consistent in
483 * increases and decreases of exp_routes, we count exported routes
484 * regardless of blocking by limits.
486 * Similar problem is in handling updates - when a new route is
487 * received and blocking is active, the route would be blocked, but
488 * when an update for the route will be received later, the update
489 * would be propagated (as old != NULL). Therefore, we have to block
490 * also non-new updates (contrary to import blocking).
493 struct channel_limit
*l
= &c
->out_limit
;
494 if (l
->action
&& new)
496 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
497 channel_notify_limit(c
, l
, PLD_OUT
, stats
->exp_routes
);
499 if (l
->state
== PLS_BLOCKED
)
501 stats
->exp_routes
++; /* see note above */
502 stats
->exp_updates_rejected
++;
503 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
513 stats
->exp_updates_accepted
++;
515 stats
->exp_withdraws_accepted
++;
517 /* Hack: We do not decrease exp_routes during refeed, we instead
518 reset exp_routes at the start of refeed. */
524 if (p
->debug
& D_ROUTES
)
527 rte_trace_out(D_ROUTES
, p
, new, "replaced");
529 rte_trace_out(D_ROUTES
, p
, new, "added");
531 rte_trace_out(D_ROUTES
, p
, old
, "removed");
533 p
->rt_notify(p
, c
, net
, new, old
);
537 rt_notify_basic(struct channel
*c
, net
*net
, rte
*new0
, rte
*old0
, int refeed
)
539 struct proto
*p
= c
->proto
;
543 rte
*new_free
= NULL
;
544 rte
*old_free
= NULL
;
547 c
->stats
.exp_updates_received
++;
549 c
->stats
.exp_withdraws_received
++;
552 * This is a tricky part - we don't know whether route 'old' was exported to
553 * protocol 'p' or was filtered by the export filter. We try to run the export
554 * filter to know this to have a correct value in 'old' argument of rte_update
555 * (and proper filter value).
557 * This is broken because 'configure soft' may change filters but keep routes.
558 * Refeed cycle is expected to be called after change of the filters and with
559 * old == new, therefore we do not even try to run the filter on an old route.
560 * This may lead to 'spurious withdraws' but ensure that there are no 'missing
563 * This is not completely safe as there is a window between reconfiguration
564 * and the end of refeed - if a newly filtered route disappears during this
565 * period, proper withdraw is not sent (because old would be also filtered)
566 * and the route is not refeeded (because it disappeared before that).
567 * Therefore, we also do not try to run the filter on old routes that are
568 * older than the last filter change.
572 new = export_filter(c
, new, &new_free
, 0);
574 if (old
&& !(refeed
|| (old
->lastmod
<= c
->last_tx_filter_change
)))
575 old
= export_filter(c
, old
, &old_free
, 1);
580 * As mentioned above, 'old' value may be incorrect in some race conditions.
581 * We generally ignore it with the exception of withdraw to pipe protocol.
582 * In that case we rather propagate unfiltered withdraws regardless of
583 * export filters to ensure that when a protocol is flushed, its routes are
584 * removed from all tables. Possible spurious unfiltered withdraws are not
585 * problem here as they are ignored if there is no corresponding route at
586 * the other end of the pipe. We directly call rt_notify() hook instead of
587 * do_rt_notify() to avoid logging and stat counters.
591 if ((p
->proto
== &proto_pipe
) && !new0
&& (p
!= old0
->sender
->proto
))
592 p
->rt_notify(p
, c
, net
, NULL
, old0
);
598 do_rt_notify(c
, net
, new, old
, refeed
);
600 /* Discard temporary rte's */
608 rt_notify_accepted(struct channel
*c
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
, int feed
)
610 // struct proto *p = c->proto;
613 rte
*new_best
= NULL
;
614 rte
*old_best
= NULL
;
615 rte
*new_free
= NULL
;
616 rte
*old_free
= NULL
;
618 /* Used to track whether we met old_changed position. If before_old is NULL
619 old_changed was the first and we met it implicitly before current best route. */
620 int old_meet
= old_changed
&& !before_old
;
622 /* Note that before_old is either NULL or valid (not rejected) route.
623 If old_changed is valid, before_old have to be too. If old changed route
624 was not valid, caller must use NULL for both old_changed and before_old. */
627 c
->stats
.exp_updates_received
++;
629 c
->stats
.exp_withdraws_received
++;
631 /* First, find the new_best route - first accepted by filters */
632 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
634 if (new_best
= export_filter(c
, r
, &new_free
, 0))
637 /* Note if we walked around the position of old_changed route */
643 * Second, handle the feed case. That means we do not care for
644 * old_best. It is NULL for feed, and the new_best for refeed.
645 * For refeed, there is a hack similar to one in rt_notify_basic()
646 * to ensure withdraws in case of changed filters
650 if (feed
== 2) /* refeed */
651 old_best
= new_best
? new_best
:
652 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
656 if (!new_best
&& !old_best
)
663 * Now, we find the old_best route. Generally, it is the same as the
664 * new_best, unless new_best is the same as new_changed or
665 * old_changed is accepted before new_best.
667 * There are four cases:
669 * - We would find and accept old_changed before new_best, therefore
670 * old_changed is old_best. In remaining cases we suppose this
673 * - We found no new_best, therefore there is also no old_best and
674 * we ignore this withdraw.
676 * - We found new_best different than new_changed, therefore
677 * old_best is the same as new_best and we ignore this update.
679 * - We found new_best the same as new_changed, therefore it cannot
680 * be old_best and we have to continue search for old_best.
682 * There is also a hack to ensure consistency in case of changed filters.
683 * It does not find the proper old_best, just selects a non-NULL route.
686 /* Hack for changed filters */
687 if (old_changed
&& (old_changed
->lastmod
<= c
->last_tx_filter_change
))
689 old_best
= old_changed
;
695 if (old_best
= export_filter(c
, old_changed
, &old_free
, 1))
702 /* Third case, we use r instead of new_best, because export_filter() could change it */
703 if (r
!= new_changed
)
711 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
713 if (old_best
= export_filter(c
, r
, &old_free
, 1))
717 if (old_best
= export_filter(c
, old_changed
, &old_free
, 1))
721 /* Implicitly, old_best is NULL and new_best is non-NULL */
724 do_rt_notify(c
, net
, new_best
, old_best
, (feed
== 2));
726 /* Discard temporary rte's */
734 static struct nexthop
*
735 nexthop_merge_rta(struct nexthop
*nhs
, rta
*a
, linpool
*pool
, int max
)
737 return nexthop_merge(nhs
, &(a
->nh
), 1, 0, max
, pool
);
741 rt_export_merged(struct channel
*c
, net
*net
, rte
**rt_free
, linpool
*pool
, int silent
)
743 // struct proto *p = c->proto;
744 struct nexthop
*nhs
= NULL
;
745 rte
*best0
, *best
, *rt0
, *rt
, *tmp
;
750 if (!rte_is_valid(best0
))
753 best
= export_filter_(c
, best0
, rt_free
, pool
, silent
);
755 if (!best
|| !rte_is_reachable(best
))
758 for (rt0
= best0
->next
; rt0
; rt0
= rt0
->next
)
760 if (!rte_mergable(best0
, rt0
))
763 rt
= export_filter_(c
, rt0
, &tmp
, pool
, 1);
768 if (rte_is_reachable(rt
))
769 nhs
= nexthop_merge_rta(nhs
, rt
->attrs
, pool
, c
->merge_limit
);
777 nhs
= nexthop_merge_rta(nhs
, best
->attrs
, pool
, c
->merge_limit
);
781 best
= rte_cow_rta(best
, pool
);
782 nexthop_link(best
->attrs
, nhs
);
794 rt_notify_merged(struct channel
*c
, net
*net
, rte
*new_changed
, rte
*old_changed
,
795 rte
*new_best
, rte
*old_best
, int refeed
)
797 // struct proto *p = c->proto;
799 rte
*new_best_free
= NULL
;
800 rte
*old_best_free
= NULL
;
801 rte
*new_changed_free
= NULL
;
802 rte
*old_changed_free
= NULL
;
804 /* We assume that all rte arguments are either NULL or rte_is_valid() */
806 /* This check should be done by the caller */
807 if (!new_best
&& !old_best
)
810 /* Check whether the change is relevant to the merged route */
811 if ((new_best
== old_best
) && !refeed
)
813 new_changed
= rte_mergable(new_best
, new_changed
) ?
814 export_filter(c
, new_changed
, &new_changed_free
, 1) : NULL
;
816 old_changed
= rte_mergable(old_best
, old_changed
) ?
817 export_filter(c
, old_changed
, &old_changed_free
, 1) : NULL
;
819 if (!new_changed
&& !old_changed
)
824 c
->stats
.exp_updates_received
++;
826 c
->stats
.exp_withdraws_received
++;
828 /* Prepare new merged route */
830 new_best
= rt_export_merged(c
, net
, &new_best_free
, rte_update_pool
, 0);
832 /* Prepare old merged route (without proper merged next hops) */
833 /* There are some issues with running filter on old route - see rt_notify_basic() */
834 if (old_best
&& !refeed
)
835 old_best
= export_filter(c
, old_best
, &old_best_free
, 1);
837 if (new_best
|| old_best
)
838 do_rt_notify(c
, net
, new_best
, old_best
, refeed
);
840 /* Discard temporary rte's */
842 rte_free(new_best_free
);
844 rte_free(old_best_free
);
845 if (new_changed_free
)
846 rte_free(new_changed_free
);
847 if (old_changed_free
)
848 rte_free(old_changed_free
);
853 * rte_announce - announce a routing table change
854 * @tab: table the route has been added to
855 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
856 * @net: network in question
857 * @new: the new route to be announced
858 * @old: the previous route for the same network
859 * @new_best: the new best route for the same network
860 * @old_best: the previous best route for the same network
861 * @before_old: The previous route before @old for the same network.
862 * If @before_old is NULL @old was the first.
864 * This function gets a routing table update and announces it
865 * to all protocols that acccepts given type of route announcement
866 * and are connected to the same table by their announcement hooks.
868 * Route announcement of type %RA_OPTIMAL si generated when optimal
869 * route (in routing table @tab) changes. In that case @old stores the
872 * Route announcement of type %RA_ANY si generated when any route (in
873 * routing table @tab) changes In that case @old stores the old route
874 * from the same protocol.
876 * For each appropriate protocol, we first call its preexport()
877 * hook which performs basic checks on the route (each protocol has a
878 * right to veto or force accept of the route before any filter is
879 * asked) and adds default values of attributes specific to the new
880 * protocol (metrics, tags etc.). Then it consults the protocol's
881 * export filter and if it accepts the route, the rt_notify() hook of
882 * the protocol gets called.
885 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
886 rte
*new_best
, rte
*old_best
, rte
*before_old
)
888 if (!rte_is_valid(new))
891 if (!rte_is_valid(old
))
892 old
= before_old
= NULL
;
894 if (!rte_is_valid(new_best
))
897 if (!rte_is_valid(old_best
))
903 if ((type
== RA_OPTIMAL
) && tab
->hostcache
)
904 rt_notify_hostcache(tab
, net
);
906 struct channel
*c
; node
*n
;
907 WALK_LIST2(c
, n
, tab
->channels
, table_node
)
909 if (c
->export_state
== ES_DOWN
)
912 if (c
->ra_mode
== type
)
913 if (type
== RA_ACCEPTED
)
914 rt_notify_accepted(c
, net
, new, old
, before_old
, 0);
915 else if (type
== RA_MERGED
)
916 rt_notify_merged(c
, net
, new, old
, new_best
, old_best
, 0);
918 rt_notify_basic(c
, net
, new, old
, 0);
928 if (!net_validate(n
->n
.addr
))
930 log(L_WARN
"Ignoring bogus prefix %N received via %s",
931 n
->n
.addr
, e
->sender
->proto
->name
);
935 /* FIXME: better handling different nettypes */
936 c
= !net_is_flow(n
->n
.addr
) ?
937 net_classify(n
->n
.addr
): (IADDR_HOST
| SCOPE_UNIVERSE
);
938 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
940 log(L_WARN
"Ignoring bogus route %N received via %s",
941 n
->n
.addr
, e
->sender
->proto
->name
);
945 if (net_type_match(n
->n
.addr
, NB_DEST
) == !e
->attrs
->dest
)
947 log(L_WARN
"Ignoring route %N with invalid dest %d received via %s",
948 n
->n
.addr
, e
->attrs
->dest
, e
->sender
->proto
->name
);
952 if ((e
->attrs
->dest
== RTD_UNICAST
) && !nexthop_is_sorted(&(e
->attrs
->nh
)))
954 log(L_WARN
"Ignoring unsorted multipath route %N received via %s",
955 n
->n
.addr
, e
->sender
->proto
->name
);
963 * rte_free - delete a &rte
964 * @e: &rte to be deleted
966 * rte_free() deletes the given &rte from the routing table it's linked to.
971 if (rta_is_cached(e
->attrs
))
973 sl_free(rte_slab
, e
);
977 rte_free_quick(rte
*e
)
980 sl_free(rte_slab
, e
);
984 rte_same(rte
*x
, rte
*y
)
987 x
->attrs
== y
->attrs
&&
988 x
->flags
== y
->flags
&&
989 x
->pflags
== y
->pflags
&&
990 x
->pref
== y
->pref
&&
991 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
994 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
997 rte_recalculate(struct channel
*c
, net
*net
, rte
*new, struct rte_src
*src
)
999 struct proto
*p
= c
->proto
;
1000 struct rtable
*table
= c
->table
;
1001 struct proto_stats
*stats
= &c
->stats
;
1002 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
1003 rte
*before_old
= NULL
;
1004 rte
*old_best
= net
->routes
;
1008 k
= &net
->routes
; /* Find and remove original route from the same protocol */
1011 if (old
->attrs
->src
== src
)
1013 /* If there is the same route in the routing table but from
1014 * a different sender, then there are two paths from the
1015 * source protocol to this routing table through transparent
1016 * pipes, which is not allowed.
1018 * We log that and ignore the route. If it is withdraw, we
1019 * ignore it completely (there might be 'spurious withdraws',
1020 * see FIXME in do_rte_announce())
1022 if (old
->sender
->proto
!= p
)
1026 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %N to table %s",
1027 net
->n
.addr
, table
->name
);
1028 rte_free_quick(new);
1033 if (new && rte_same(old
, new))
1035 /* No changes, ignore the new route */
1037 if (!rte_is_filtered(new))
1039 stats
->imp_updates_ignored
++;
1040 rte_trace_in(D_ROUTES
, p
, new, "ignored");
1043 rte_free_quick(new);
1059 stats
->imp_withdraws_ignored
++;
1063 int new_ok
= rte_is_ok(new);
1064 int old_ok
= rte_is_ok(old
);
1066 struct channel_limit
*l
= &c
->rx_limit
;
1067 if (l
->action
&& !old
&& new && !c
->in_table
)
1069 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
1071 if (all_routes
>= l
->limit
)
1072 channel_notify_limit(c
, l
, PLD_RX
, all_routes
);
1074 if (l
->state
== PLS_BLOCKED
)
1076 /* In receive limit the situation is simple, old is NULL so
1077 we just free new and exit like nothing happened */
1079 stats
->imp_updates_ignored
++;
1080 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
1081 rte_free_quick(new);
1087 if (l
->action
&& !old_ok
&& new_ok
)
1089 if (stats
->imp_routes
>= l
->limit
)
1090 channel_notify_limit(c
, l
, PLD_IN
, stats
->imp_routes
);
1092 if (l
->state
== PLS_BLOCKED
)
1094 /* In import limit the situation is more complicated. We
1095 shouldn't just drop the route, we should handle it like
1096 it was filtered. We also have to continue the route
1097 processing if old or new is non-NULL, but we should exit
1098 if both are NULL as this case is probably assumed to be
1101 stats
->imp_updates_ignored
++;
1102 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
1104 if (c
->in_keep_filtered
)
1105 new->flags
|= REF_FILTERED
;
1107 { rte_free_quick(new); new = NULL
; }
1109 /* Note that old && !new could be possible when
1110 c->in_keep_filtered changed in the recent past. */
1121 stats
->imp_updates_accepted
++;
1123 stats
->imp_withdraws_accepted
++;
1125 stats
->imp_withdraws_ignored
++;
1130 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
1132 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
1134 if (table
->config
->sorted
)
1136 /* If routes are sorted, just insert new route to appropriate position */
1139 if (before_old
&& !rte_better(new, before_old
))
1140 k
= &before_old
->next
;
1144 for (; *k
; k
=&(*k
)->next
)
1145 if (rte_better(new, *k
))
1155 /* If routes are not sorted, find the best route and move it on
1156 the first position. There are several optimized cases. */
1158 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
1159 goto do_recalculate
;
1161 if (new && rte_better(new, old_best
))
1163 /* The first case - the new route is cleary optimal,
1164 we link it at the first position */
1166 new->next
= net
->routes
;
1170 else if (old
== old_best
)
1172 /* The second case - the old best route disappeared, we add the
1173 new route (if we have any) to the list (we don't care about
1174 position) and then we elect the new optimal route and relink
1175 that route at the first position and announce it. New optimal
1176 route might be NULL if there is no more routes */
1179 /* Add the new route to the list */
1182 new->next
= net
->routes
;
1187 /* Find a new optimal route (if there is any) */
1190 rte
**bp
= &net
->routes
;
1191 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
1192 if (rte_better(*k
, *bp
))
1198 best
->next
= net
->routes
;
1204 /* The third case - the new route is not better than the old
1205 best route (therefore old_best != NULL) and the old best
1206 route was not removed (therefore old_best == net->routes).
1207 We just link the new route after the old best route. */
1209 ASSERT(net
->routes
!= NULL
);
1210 new->next
= net
->routes
->next
;
1211 net
->routes
->next
= new;
1214 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1218 new->lastmod
= current_time();
1220 /* Log the route change */
1221 if (p
->debug
& D_ROUTES
)
1224 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
1227 if (old
!= old_best
)
1228 rte_trace(p
, old
, '>', "removed");
1229 else if (rte_is_ok(net
->routes
))
1230 rte_trace(p
, old
, '>', "removed [replaced]");
1232 rte_trace(p
, old
, '>', "removed [sole]");
1236 /* Propagate the route change */
1237 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, NULL
, NULL
);
1238 if (net
->routes
!= old_best
)
1239 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, NULL
, NULL
);
1240 if (table
->config
->sorted
)
1241 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, NULL
, NULL
, before_old
);
1242 rte_announce(table
, RA_MERGED
, net
, new, old
, net
->routes
, old_best
, NULL
);
1245 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
1246 (table
->gc_time
+ table
->config
->gc_min_time
<= current_time()))
1247 rt_schedule_prune(table
);
1249 if (old_ok
&& p
->rte_remove
)
1250 p
->rte_remove(net
, old
);
1251 if (new_ok
&& p
->rte_insert
)
1252 p
->rte_insert(net
, new);
1255 rte_free_quick(old
);
1258 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
1261 rte_update_lock(void)
1263 rte_update_nest_cnt
++;
1267 rte_update_unlock(void)
1269 if (!--rte_update_nest_cnt
)
1270 lp_flush(rte_update_pool
);
1274 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
1276 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
1278 *dummy
= net
->routes
;
1279 net
->routes
= (*dummy
)->next
;
1284 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
1288 (*dummy
)->next
= net
->routes
;
1289 net
->routes
= *dummy
;
1294 * rte_update - enter a new update to a routing table
1295 * @table: table to be updated
1296 * @c: channel doing the update
1297 * @net: network node
1298 * @p: protocol submitting the update
1299 * @src: protocol originating the update
1300 * @new: a &rte representing the new route or %NULL for route removal.
1302 * This function is called by the routing protocols whenever they discover
1303 * a new route or wish to update/remove an existing route. The right announcement
1304 * sequence is to build route attributes first (either un-cached with @aflags set
1305 * to zero or a cached one using rta_lookup(); in this case please note that
1306 * you need to increase the use count of the attributes yourself by calling
1307 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1308 * the appropriate data and finally submit the new &rte by calling rte_update().
1310 * @src specifies the protocol that originally created the route and the meaning
1311 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1312 * same value as @new->attrs->proto. @p specifies the protocol that called
1313 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1314 * stores @p in @new->sender;
1316 * When rte_update() gets any route, it automatically validates it (checks,
1317 * whether the network and next hop address are valid IP addresses and also
1318 * whether a normal routing protocol doesn't try to smuggle a host or link
1319 * scope route to the table), converts all protocol dependent attributes stored
1320 * in the &rte to temporary extended attributes, consults import filters of the
1321 * protocol to see if the route should be accepted and/or its attributes modified,
1322 * stores the temporary attributes back to the &rte.
1324 * Now, having a "public" version of the route, we
1325 * automatically find any old route defined by the protocol @src
1326 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1327 * recalculate the optimal route for this destination and finally broadcast
1328 * the change (if any) to all routing protocols by calling rte_announce().
1330 * All memory used for attribute lists and other temporary allocations is taken
1331 * from a special linear pool @rte_update_pool and freed when rte_update()
1336 rte_update2(struct channel
*c
, const net_addr
*n
, rte
*new, struct rte_src
*src
)
1338 struct proto
*p
= c
->proto
;
1339 struct proto_stats
*stats
= &c
->stats
;
1340 struct filter
*filter
= c
->in_filter
;
1344 ASSERT(c
->channel_state
== CS_UP
);
1349 nn
= net_get(c
->table
, n
);
1355 new->pref
= c
->preference
;
1357 stats
->imp_updates_received
++;
1358 if (!rte_validate(new))
1360 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1361 stats
->imp_updates_invalid
++;
1365 if (filter
== FILTER_REJECT
)
1367 stats
->imp_updates_filtered
++;
1368 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1370 if (! c
->in_keep_filtered
)
1373 /* new is a private copy, i could modify it */
1374 new->flags
|= REF_FILTERED
;
1378 rte_make_tmp_attrs(&new, rte_update_pool
);
1379 if (filter
&& (filter
!= FILTER_REJECT
))
1381 ea_list
*oldea
= new->attrs
->eattrs
;
1382 int fr
= f_run(filter
, &new, rte_update_pool
, 0);
1385 stats
->imp_updates_filtered
++;
1386 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1388 if (! c
->in_keep_filtered
)
1391 new->flags
|= REF_FILTERED
;
1393 if (new->attrs
->eattrs
!= oldea
&& src
->proto
->store_tmp_attrs
)
1394 src
->proto
->store_tmp_attrs(new);
1397 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1398 new->attrs
= rta_lookup(new->attrs
);
1399 new->flags
|= REF_COW
;
1403 stats
->imp_withdraws_received
++;
1405 if (!(nn
= net_find(c
->table
, n
)) || !src
)
1407 stats
->imp_withdraws_ignored
++;
1408 rte_update_unlock();
1414 rte_hide_dummy_routes(nn
, &dummy
);
1415 rte_recalculate(c
, nn
, new, src
);
1416 rte_unhide_dummy_routes(nn
, &dummy
);
1417 rte_update_unlock();
1426 /* Independent call to rte_announce(), used from next hop
1427 recalculation, outside of rte_update(). new must be non-NULL */
1429 rte_announce_i(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
1430 rte
*new_best
, rte
*old_best
)
1433 rte_announce(tab
, type
, net
, new, old
, new_best
, old_best
, NULL
);
1434 rte_update_unlock();
1438 rte_discard(rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1441 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1442 rte_update_unlock();
1445 /* Modify existing route by protocol hook, used for long-lived graceful restart */
1447 rte_modify(rte
*old
)
1451 rte
*new = old
->sender
->proto
->rte_modify(old
, rte_update_pool
);
1456 if (!rta_is_cached(new->attrs
))
1457 new->attrs
= rta_lookup(new->attrs
);
1458 new->flags
= (old
->flags
& ~REF_MODIFY
) | REF_COW
;
1461 rte_recalculate(old
->sender
, old
->net
, new, old
->attrs
->src
);
1464 rte_update_unlock();
1467 /* Check rtable for best route to given net whether it would be exported do p */
1469 rt_examine(rtable
*t
, net_addr
*a
, struct proto
*p
, struct filter
*filter
)
1471 net
*n
= net_find(t
, a
);
1472 rte
*rt
= n
? n
->routes
: NULL
;
1474 if (!rte_is_valid(rt
))
1479 /* Rest is stripped down export_filter() */
1480 rte_make_tmp_attrs(&rt
, rte_update_pool
);
1481 int v
= p
->preexport
? p
->preexport(p
, &rt
, rte_update_pool
) : 0;
1482 if (v
== RIC_PROCESS
)
1483 v
= (f_run(filter
, &rt
, rte_update_pool
, FF_SILENT
) <= F_ACCEPT
);
1485 /* Discard temporary rte */
1486 if (rt
!= n
->routes
)
1489 rte_update_unlock();
1496 * rt_refresh_begin - start a refresh cycle
1497 * @t: related routing table
1498 * @c related channel
1500 * This function starts a refresh cycle for given routing table and announce
1501 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1502 * routes to the routing table (by rte_update()). After that, all protocol
1503 * routes (more precisely routes with @c as @sender) not sent during the
1504 * refresh cycle but still in the table from the past are pruned. This is
1505 * implemented by marking all related routes as stale by REF_STALE flag in
1506 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1507 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1510 rt_refresh_begin(rtable
*t
, struct channel
*c
)
1512 FIB_WALK(&t
->fib
, net
, n
)
1515 for (e
= n
->routes
; e
; e
= e
->next
)
1517 e
->flags
|= REF_STALE
;
1523 * rt_refresh_end - end a refresh cycle
1524 * @t: related routing table
1525 * @c: related channel
1527 * This function ends a refresh cycle for given routing table and announce
1528 * hook. See rt_refresh_begin() for description of refresh cycles.
1531 rt_refresh_end(rtable
*t
, struct channel
*c
)
1535 FIB_WALK(&t
->fib
, net
, n
)
1538 for (e
= n
->routes
; e
; e
= e
->next
)
1539 if ((e
->sender
== c
) && (e
->flags
& REF_STALE
))
1541 e
->flags
|= REF_DISCARD
;
1548 rt_schedule_prune(t
);
1552 rt_modify_stale(rtable
*t
, struct channel
*c
)
1556 FIB_WALK(&t
->fib
, net
, n
)
1559 for (e
= n
->routes
; e
; e
= e
->next
)
1560 if ((e
->sender
== c
) && (e
->flags
& REF_STALE
) && !(e
->flags
& REF_FILTERED
))
1562 e
->flags
|= REF_MODIFY
;
1569 rt_schedule_prune(t
);
1573 * rte_dump - dump a route
1574 * @e: &rte to be dumped
1576 * This functions dumps contents of a &rte to debug output.
1582 debug("%-1N ", n
->n
.addr
);
1583 debug("KF=%02x PF=%02x pref=%d ", n
->n
.flags
, e
->pflags
, e
->pref
);
1585 if (e
->attrs
->src
->proto
->proto
->dump_attrs
)
1586 e
->attrs
->src
->proto
->proto
->dump_attrs(e
);
1591 * rt_dump - dump a routing table
1592 * @t: routing table to be dumped
1594 * This function dumps contents of a given routing table to debug output.
1599 debug("Dump of routing table <%s>\n", t
->name
);
1603 FIB_WALK(&t
->fib
, net
, n
)
1606 for(e
=n
->routes
; e
; e
=e
->next
)
1614 * rt_dump_all - dump all routing tables
1616 * This function dumps contents of all routing tables to debug output.
1623 WALK_LIST(t
, routing_tables
)
1628 rt_schedule_hcu(rtable
*tab
)
1630 if (tab
->hcu_scheduled
)
1633 tab
->hcu_scheduled
= 1;
1634 ev_schedule(tab
->rt_event
);
1638 rt_schedule_nhu(rtable
*tab
)
1640 if (tab
->nhu_state
== NHU_CLEAN
)
1641 ev_schedule(tab
->rt_event
);
1644 * NHU_CLEAN -> NHU_SCHEDULED
1645 * NHU_RUNNING -> NHU_DIRTY
1647 tab
->nhu_state
|= NHU_SCHEDULED
;
1651 rt_schedule_prune(rtable
*tab
)
1653 if (tab
->prune_state
== 0)
1654 ev_schedule(tab
->rt_event
);
1656 /* state change 0->1, 2->3 */
1657 tab
->prune_state
|= 1;
1668 if (tab
->hcu_scheduled
)
1669 rt_update_hostcache(tab
);
1672 rt_next_hop_update(tab
);
1674 if (tab
->prune_state
)
1675 rt_prune_table(tab
);
1677 rt_unlock_table(tab
);
1681 rt_setup(pool
*p
, rtable
*t
, struct rtable_config
*cf
)
1683 bzero(t
, sizeof(*t
));
1686 t
->addr_type
= cf
->addr_type
;
1687 fib_init(&t
->fib
, p
, t
->addr_type
, sizeof(net
), OFFSETOF(net
, n
), 0, NULL
);
1688 init_list(&t
->channels
);
1690 t
->rt_event
= ev_new_init(p
, rt_event
, t
);
1691 t
->gc_time
= current_time();
1695 * rt_init - initialize routing tables
1697 * This function is called during BIRD startup. It initializes the
1698 * routing table module.
1704 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1705 rte_update_pool
= lp_new_default(rt_table_pool
);
1706 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1707 init_list(&routing_tables
);
1712 * rt_prune_table - prune a routing table
1714 * The prune loop scans routing tables and removes routes belonging to flushing
1715 * protocols, discarded routes and also stale network entries. It is called from
1716 * rt_event(). The event is rescheduled if the current iteration do not finish
1717 * the table. The pruning is directed by the prune state (@prune_state),
1718 * specifying whether the prune cycle is scheduled or running, and there
1719 * is also a persistent pruning iterator (@prune_fit).
1721 * The prune loop is used also for channel flushing. For this purpose, the
1722 * channels to flush are marked before the iteration and notified after the
1726 rt_prune_table(rtable
*tab
)
1728 struct fib_iterator
*fit
= &tab
->prune_fit
;
1734 DBG("Pruning route table %s\n", tab
->name
);
1736 fib_check(&tab
->fib
);
1739 if (tab
->prune_state
== 0)
1742 if (tab
->prune_state
== 1)
1744 /* Mark channels to flush */
1745 WALK_LIST2(c
, n
, tab
->channels
, table_node
)
1746 if (c
->channel_state
== CS_FLUSHING
)
1747 c
->flush_active
= 1;
1749 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1750 tab
->prune_state
= 2;
1754 FIB_ITERATE_START(&tab
->fib
, fit
, net
, n
)
1759 for (e
=n
->routes
; e
; e
=e
->next
)
1761 if (e
->sender
->flush_active
|| (e
->flags
& REF_DISCARD
))
1765 FIB_ITERATE_PUT(fit
);
1766 ev_schedule(tab
->rt_event
);
1776 if (e
->flags
& REF_MODIFY
)
1780 FIB_ITERATE_PUT(fit
);
1781 ev_schedule(tab
->rt_event
);
1792 if (!n
->routes
) /* Orphaned FIB entry */
1794 FIB_ITERATE_PUT(fit
);
1795 fib_delete(&tab
->fib
, n
);
1802 fib_check(&tab
->fib
);
1805 tab
->gc_counter
= 0;
1806 tab
->gc_time
= current_time();
1808 /* state change 2->0, 3->1 */
1809 tab
->prune_state
&= 1;
1811 if (tab
->prune_state
> 0)
1812 ev_schedule(tab
->rt_event
);
1814 /* FIXME: This should be handled in a better way */
1817 /* Close flushed channels */
1818 WALK_LIST2_DELSAFE(c
, n
, x
, tab
->channels
, table_node
)
1819 if (c
->flush_active
)
1821 c
->flush_active
= 0;
1822 channel_set_state(c
, CS_DOWN
);
1829 rt_preconfig(struct config
*c
)
1831 init_list(&c
->tables
);
1833 rt_new_table(cf_get_symbol("master4"), NET_IP4
);
1834 rt_new_table(cf_get_symbol("master6"), NET_IP6
);
1839 * Some functions for handing internal next hop updates
1840 * triggered by rt_schedule_nhu().
1844 rta_next_hop_outdated(rta
*a
)
1846 struct hostentry
*he
= a
->hostentry
;
1852 return a
->dest
!= RTD_UNREACHABLE
;
1854 return (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1855 (!he
->nexthop_linkable
) || !nexthop_same(&(a
->nh
), &(he
->src
->nh
));
1859 rta_apply_hostentry(rta
*a
, struct hostentry
*he
, mpls_label_stack
*mls
)
1863 a
->igp_metric
= he
->igp_metric
;
1865 if (a
->dest
!= RTD_UNICAST
)
1869 a
->nh
= (struct nexthop
) {};
1871 { /* Store the label stack for later changes */
1872 a
->nh
.labels_orig
= a
->nh
.labels
= mls
->len
;
1873 memcpy(a
->nh
.label
, mls
->stack
, mls
->len
* sizeof(u32
));
1878 if (((!mls
) || (!mls
->len
)) && he
->nexthop_linkable
)
1879 { /* Just link the nexthop chain, no label append happens. */
1880 memcpy(&(a
->nh
), &(he
->src
->nh
), nexthop_size(&(he
->src
->nh
)));
1884 struct nexthop
*nhp
= NULL
, *nhr
= NULL
;
1885 int skip_nexthop
= 0;
1887 for (struct nexthop
*nh
= &(he
->src
->nh
); nh
; nh
= nh
->next
)
1894 nhp
= (nhp
? (nhp
->next
= lp_allocz(rte_update_pool
, NEXTHOP_MAX_SIZE
)) : &(a
->nh
));
1897 nhp
->iface
= nh
->iface
;
1898 nhp
->weight
= nh
->weight
;
1901 nhp
->labels
= nh
->labels
+ mls
->len
;
1902 nhp
->labels_orig
= mls
->len
;
1903 if (nhp
->labels
<= MPLS_MAX_LABEL_STACK
)
1905 memcpy(nhp
->label
, nh
->label
, nh
->labels
* sizeof(u32
)); /* First the hostentry labels */
1906 memcpy(&(nhp
->label
[nh
->labels
]), mls
->stack
, mls
->len
* sizeof(u32
)); /* Then the bottom labels */
1910 log(L_WARN
"Sum of label stack sizes %d + %d = %d exceedes allowed maximum (%d)",
1911 nh
->labels
, mls
->len
, nhp
->labels
, MPLS_MAX_LABEL_STACK
);
1916 if (ipa_nonzero(nh
->gw
))
1918 nhp
->gw
= nh
->gw
; /* Router nexthop */
1919 nhp
->flags
|= (nh
->flags
& RNF_ONLINK
);
1921 else if (ipa_nonzero(he
->link
))
1922 nhp
->gw
= he
->link
; /* Device nexthop with link-local address known */
1924 nhp
->gw
= he
->addr
; /* Device nexthop with link-local address unknown */
1932 a
->dest
= RTD_UNREACHABLE
;
1933 log(L_WARN
"No valid nexthop remaining, setting route unreachable");
1939 rt_next_hop_update_rte(rtable
*tab UNUSED
, rte
*old
)
1941 rta
*a
= alloca(RTA_MAX_SIZE
);
1942 memcpy(a
, old
->attrs
, rta_size(old
->attrs
));
1944 mpls_label_stack mls
= { .len
= a
->nh
.labels_orig
};
1945 memcpy(mls
.stack
, &a
->nh
.label
[a
->nh
.labels
- mls
.len
], mls
.len
* sizeof(u32
));
1947 rta_apply_hostentry(a
, old
->attrs
->hostentry
, &mls
);
1950 rte
*e
= sl_alloc(rte_slab
);
1951 memcpy(e
, old
, sizeof(rte
));
1952 e
->attrs
= rta_lookup(a
);
1958 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1960 rte
**k
, *e
, *new, *old_best
, **new_best
;
1962 int free_old_best
= 0;
1964 old_best
= n
->routes
;
1968 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1969 if (rta_next_hop_outdated(e
->attrs
))
1971 new = rt_next_hop_update_rte(tab
, e
);
1974 rte_announce_i(tab
, RA_ANY
, n
, new, e
, NULL
, NULL
);
1975 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1977 /* Call a pre-comparison hook */
1978 /* Not really an efficient way to compute this */
1979 if (e
->attrs
->src
->proto
->rte_recalculate
)
1980 e
->attrs
->src
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1984 else /* Freeing of the old best rte is postponed */
1994 /* Find the new best route */
1996 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1998 if (!new_best
|| rte_better(e
, *new_best
))
2002 /* Relink the new best route to the first position */
2004 if (new != n
->routes
)
2006 *new_best
= new->next
;
2007 new->next
= n
->routes
;
2011 /* Announce the new best route */
2012 if (new != old_best
)
2014 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
, NULL
, NULL
);
2015 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
2018 /* FIXME: Better announcement of merged routes */
2019 rte_announce_i(tab
, RA_MERGED
, n
, new, old_best
, new, old_best
);
2022 rte_free_quick(old_best
);
2028 rt_next_hop_update(rtable
*tab
)
2030 struct fib_iterator
*fit
= &tab
->nhu_fit
;
2033 if (tab
->nhu_state
== NHU_CLEAN
)
2036 if (tab
->nhu_state
== NHU_SCHEDULED
)
2038 FIB_ITERATE_INIT(fit
, &tab
->fib
);
2039 tab
->nhu_state
= NHU_RUNNING
;
2042 FIB_ITERATE_START(&tab
->fib
, fit
, net
, n
)
2046 FIB_ITERATE_PUT(fit
);
2047 ev_schedule(tab
->rt_event
);
2050 max_feed
-= rt_next_hop_update_net(tab
, n
);
2055 * NHU_DIRTY -> NHU_SCHEDULED
2056 * NHU_RUNNING -> NHU_CLEAN
2058 tab
->nhu_state
&= 1;
2060 if (tab
->nhu_state
!= NHU_CLEAN
)
2061 ev_schedule(tab
->rt_event
);
2065 struct rtable_config
*
2066 rt_new_table(struct symbol
*s
, uint addr_type
)
2068 /* Hack that allows to 'redefine' the master table */
2069 if ((s
->class == SYM_TABLE
) &&
2070 (s
->def
== new_config
->def_tables
[addr_type
]) &&
2071 ((addr_type
== NET_IP4
) || (addr_type
== NET_IP6
)))
2074 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
2076 cf_define_symbol(s
, SYM_TABLE
, c
);
2078 c
->addr_type
= addr_type
;
2079 c
->gc_max_ops
= 1000;
2082 add_tail(&new_config
->tables
, &c
->n
);
2084 /* First table of each type is kept as default */
2085 if (! new_config
->def_tables
[addr_type
])
2086 new_config
->def_tables
[addr_type
] = c
;
2092 * rt_lock_table - lock a routing table
2093 * @r: routing table to be locked
2095 * Lock a routing table, because it's in use by a protocol,
2096 * preventing it from being freed when it gets undefined in a new
2100 rt_lock_table(rtable
*r
)
2106 * rt_unlock_table - unlock a routing table
2107 * @r: routing table to be unlocked
2109 * Unlock a routing table formerly locked by rt_lock_table(),
2110 * that is decrease its use count and delete it if it's scheduled
2111 * for deletion by configuration changes.
2114 rt_unlock_table(rtable
*r
)
2116 if (!--r
->use_count
&& r
->deleted
)
2118 struct config
*conf
= r
->deleted
;
2119 DBG("Deleting routing table %s\n", r
->name
);
2120 r
->config
->table
= NULL
;
2122 rt_free_hostcache(r
);
2127 config_del_obstacle(conf
);
2131 static struct rtable_config
*
2132 rt_find_table_config(struct config
*cf
, char *name
)
2134 struct symbol
*sym
= cf_find_symbol(cf
, name
);
2135 return (sym
&& (sym
->class == SYM_TABLE
)) ? sym
->def
: NULL
;
2139 * rt_commit - commit new routing table configuration
2140 * @new: new configuration
2141 * @old: original configuration or %NULL if it's boot time config
2143 * Scan differences between @old and @new configuration and modify
2144 * the routing tables according to these changes. If @new defines a
2145 * previously unknown table, create it, if it omits a table existing
2146 * in @old, schedule it for deletion (it gets deleted when all protocols
2147 * disconnect from it by calling rt_unlock_table()), if it exists
2148 * in both configurations, leave it unchanged.
2151 rt_commit(struct config
*new, struct config
*old
)
2153 struct rtable_config
*o
, *r
;
2155 DBG("rt_commit:\n");
2158 WALK_LIST(o
, old
->tables
)
2160 rtable
*ot
= o
->table
;
2163 r
= rt_find_table_config(new, o
->name
);
2164 if (r
&& (r
->addr_type
== o
->addr_type
) && !new->shutdown
)
2166 DBG("\t%s: same\n", o
->name
);
2170 if (o
->sorted
!= r
->sorted
)
2171 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
2175 DBG("\t%s: deleted\n", o
->name
);
2177 config_add_obstacle(old
);
2179 rt_unlock_table(ot
);
2185 WALK_LIST(r
, new->tables
)
2188 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
2189 DBG("\t%s: created\n", r
->name
);
2190 rt_setup(rt_table_pool
, t
, r
);
2191 add_tail(&routing_tables
, &t
->n
);
2198 do_feed_channel(struct channel
*c
, net
*n
, rte
*e
)
2201 if (c
->ra_mode
== RA_ACCEPTED
)
2202 rt_notify_accepted(c
, n
, e
, NULL
, NULL
, c
->refeeding
? 2 : 1);
2203 else if (c
->ra_mode
== RA_MERGED
)
2204 rt_notify_merged(c
, n
, NULL
, NULL
, e
, c
->refeeding
? e
: NULL
, c
->refeeding
);
2206 rt_notify_basic(c
, n
, e
, c
->refeeding
? e
: NULL
, c
->refeeding
);
2207 rte_update_unlock();
2211 * rt_feed_channel - advertise all routes to a channel
2212 * @c: channel to be fed
2214 * This function performs one pass of advertisement of routes to a channel that
2215 * is in the ES_FEEDING state. It is called by the protocol code as long as it
2216 * has something to do. (We avoid transferring all the routes in single pass in
2217 * order not to monopolize CPU time.)
2220 rt_feed_channel(struct channel
*c
)
2222 struct fib_iterator
*fit
= &c
->feed_fit
;
2225 ASSERT(c
->export_state
== ES_FEEDING
);
2227 if (!c
->feed_active
)
2229 FIB_ITERATE_INIT(fit
, &c
->table
->fib
);
2233 FIB_ITERATE_START(&c
->table
->fib
, fit
, net
, n
)
2238 FIB_ITERATE_PUT(fit
);
2242 /* FIXME: perhaps we should change feed for RA_ACCEPTED to not use 'new' */
2244 if ((c
->ra_mode
== RA_OPTIMAL
) ||
2245 (c
->ra_mode
== RA_ACCEPTED
) ||
2246 (c
->ra_mode
== RA_MERGED
))
2247 if (rte_is_valid(e
))
2249 /* In the meantime, the protocol may fell down */
2250 if (c
->export_state
!= ES_FEEDING
)
2253 do_feed_channel(c
, n
, e
);
2257 if (c
->ra_mode
== RA_ANY
)
2258 for(e
= n
->routes
; e
; e
= e
->next
)
2260 /* In the meantime, the protocol may fell down */
2261 if (c
->export_state
!= ES_FEEDING
)
2264 if (!rte_is_valid(e
))
2267 do_feed_channel(c
, n
, e
);
2279 * rt_feed_baby_abort - abort protocol feeding
2282 * This function is called by the protocol code when the protocol stops or
2283 * ceases to exist during the feeding.
2286 rt_feed_channel_abort(struct channel
*c
)
2290 /* Unlink the iterator */
2291 fit_get(&c
->table
->fib
, &c
->feed_fit
);
2298 rte_update_in(struct channel
*c
, const net_addr
*n
, rte
*new, struct rte_src
*src
)
2300 struct rtable
*tab
= c
->in_table
;
2306 net
= net_get(tab
, n
);
2309 new->pref
= c
->preference
;
2311 if (!rta_is_cached(new->attrs
))
2312 new->attrs
= rta_lookup(new->attrs
);
2316 net
= net_find(tab
, n
);
2322 /* Find the old rte */
2323 for (pos
= &net
->routes
; old
= *pos
; pos
= &old
->next
)
2324 if (old
->attrs
->src
== src
)
2326 if (new && rte_same(old
, new))
2329 /* Remove the old rte */
2331 rte_free_quick(old
);
2345 struct channel_limit
*l
= &c
->rx_limit
;
2346 if (l
->action
&& !old
)
2348 if (tab
->rt_count
>= l
->limit
)
2349 channel_notify_limit(c
, l
, PLD_RX
, tab
->rt_count
);
2351 if (l
->state
== PLS_BLOCKED
)
2353 rte_trace_in(D_FILTERS
, c
->proto
, new, "ignored [limit]");
2358 /* Insert the new rte */
2359 rte
*e
= rte_do_cow(new);
2360 e
->flags
|= REF_COW
;
2363 e
->lastmod
= current_time();
2370 c
->stats
.imp_updates_received
++;
2371 c
->stats
.imp_updates_ignored
++;
2376 c
->stats
.imp_withdraws_received
++;
2377 c
->stats
.imp_withdraws_ignored
++;
2382 rt_reload_channel(struct channel
*c
)
2384 struct rtable
*tab
= c
->in_table
;
2385 struct fib_iterator
*fit
= &c
->reload_fit
;
2388 ASSERT(c
->channel_state
== CS_UP
);
2390 if (!c
->reload_active
)
2392 FIB_ITERATE_INIT(fit
, &tab
->fib
);
2393 c
->reload_active
= 1;
2396 FIB_ITERATE_START(&tab
->fib
, fit
, net
, n
)
2400 FIB_ITERATE_PUT(fit
);
2404 for (rte
*e
= n
->routes
; e
; e
= e
->next
)
2406 rte_update2(c
, n
->n
.addr
, rte_do_cow(e
), e
->attrs
->src
);
2412 c
->reload_active
= 0;
2417 rt_reload_channel_abort(struct channel
*c
)
2419 if (c
->reload_active
)
2421 /* Unlink the iterator */
2422 fit_get(&c
->in_table
->fib
, &c
->reload_fit
);
2423 c
->reload_active
= 0;
2428 rt_prune_sync(rtable
*t
, int all
)
2430 FIB_WALK(&t
->fib
, net
, n
)
2432 rte
*e
, **ee
= &n
->routes
;
2435 if (all
|| (e
->flags
& (REF_STALE
| REF_DISCARD
)))
2450 hc_hash(ip_addr a
, rtable
*dep
)
2452 return ipa_hash(a
) ^ ptr_hash(dep
);
2456 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
2458 uint k
= he
->hash_key
>> hc
->hash_shift
;
2459 he
->next
= hc
->hash_table
[k
];
2460 hc
->hash_table
[k
] = he
;
2464 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
2466 struct hostentry
**hep
;
2467 uint k
= he
->hash_key
>> hc
->hash_shift
;
2469 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
2473 #define HC_DEF_ORDER 10
2474 #define HC_HI_MARK *4
2475 #define HC_HI_STEP 2
2476 #define HC_HI_ORDER 16 /* Must be at most 16 */
2477 #define HC_LO_MARK /5
2478 #define HC_LO_STEP 2
2479 #define HC_LO_ORDER 10
2482 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
2484 uint hsize
= 1 << order
;
2485 hc
->hash_order
= order
;
2486 hc
->hash_shift
= 32 - order
;
2487 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0U : (hsize HC_HI_MARK
);
2488 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0U : (hsize HC_LO_MARK
);
2490 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
2494 hc_resize(struct hostcache
*hc
, unsigned new_order
)
2496 struct hostentry
**old_table
= hc
->hash_table
;
2497 struct hostentry
*he
, *hen
;
2498 uint old_size
= 1 << hc
->hash_order
;
2501 hc_alloc_table(hc
, new_order
);
2502 for (i
= 0; i
< old_size
; i
++)
2503 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
2511 static struct hostentry
*
2512 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
2514 struct hostentry
*he
= sl_alloc(hc
->slab
);
2516 *he
= (struct hostentry
) {
2523 add_tail(&hc
->hostentries
, &he
->ln
);
2527 if (hc
->hash_items
> hc
->hash_max
)
2528 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
2534 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
2540 sl_free(hc
->slab
, he
);
2543 if (hc
->hash_items
< hc
->hash_min
)
2544 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
2548 rt_init_hostcache(rtable
*tab
)
2550 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
2551 init_list(&hc
->hostentries
);
2554 hc_alloc_table(hc
, HC_DEF_ORDER
);
2555 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
2557 hc
->lp
= lp_new(rt_table_pool
, LP_GOOD_SIZE(1024));
2558 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2560 tab
->hostcache
= hc
;
2564 rt_free_hostcache(rtable
*tab
)
2566 struct hostcache
*hc
= tab
->hostcache
;
2569 WALK_LIST(n
, hc
->hostentries
)
2571 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
2575 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
2580 mb_free(hc
->hash_table
);
2585 rt_notify_hostcache(rtable
*tab
, net
*net
)
2587 if (tab
->hcu_scheduled
)
2590 if (trie_match_net(tab
->hostcache
->trie
, net
->n
.addr
))
2591 rt_schedule_hcu(tab
);
2595 if_local_addr(ip_addr a
, struct iface
*i
)
2599 WALK_LIST(b
, i
->addrs
)
2600 if (ipa_equal(a
, b
->ip
))
2607 rt_get_igp_metric(rte
*rt
)
2609 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
2617 if ((a
->source
== RTS_OSPF
) ||
2618 (a
->source
== RTS_OSPF_IA
) ||
2619 (a
->source
== RTS_OSPF_EXT1
))
2620 return rt
->u
.ospf
.metric1
;
2624 if (a
->source
== RTS_RIP
)
2625 return rt
->u
.rip
.metric
;
2628 if (a
->source
== RTS_DEVICE
)
2631 return IGP_METRIC_UNKNOWN
;
2635 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
2637 rta
*old_src
= he
->src
;
2641 /* Reset the hostentry */
2643 he
->dest
= RTD_UNREACHABLE
;
2644 he
->nexthop_linkable
= 0;
2648 net_fill_ip_host(&he_addr
, he
->addr
);
2649 net
*n
= net_route(tab
, &he_addr
);
2654 pxlen
= n
->n
.addr
->pxlen
;
2658 /* Recursive route should not depend on another recursive route */
2659 log(L_WARN
"Next hop address %I resolvable through recursive route for %N",
2660 he
->addr
, n
->n
.addr
);
2664 if (a
->dest
== RTD_UNICAST
)
2666 for (struct nexthop
*nh
= &(a
->nh
); nh
; nh
= nh
->next
)
2667 if (ipa_zero(nh
->gw
))
2669 if (if_local_addr(he
->addr
, nh
->iface
))
2671 /* The host address is a local address, this is not valid */
2672 log(L_WARN
"Next hop address %I is a local address of iface %s",
2673 he
->addr
, nh
->iface
->name
);
2681 he
->src
= rta_clone(a
);
2683 he
->nexthop_linkable
= !direct
;
2684 he
->igp_metric
= rt_get_igp_metric(e
);
2688 /* Add a prefix range to the trie */
2689 trie_add_prefix(tab
->hostcache
->trie
, &he_addr
, pxlen
, he_addr
.pxlen
);
2692 return old_src
!= he
->src
;
2696 rt_update_hostcache(rtable
*tab
)
2698 struct hostcache
*hc
= tab
->hostcache
;
2699 struct hostentry
*he
;
2702 /* Reset the trie */
2704 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2706 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
2708 he
= SKIP_BACK(struct hostentry
, ln
, n
);
2711 hc_delete_hostentry(hc
, he
);
2715 if (rt_update_hostentry(tab
, he
))
2716 rt_schedule_nhu(he
->tab
);
2719 tab
->hcu_scheduled
= 0;
2723 rt_get_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2725 struct hostentry
*he
;
2727 if (!tab
->hostcache
)
2728 rt_init_hostcache(tab
);
2730 u32 k
= hc_hash(a
, dep
);
2731 struct hostcache
*hc
= tab
->hostcache
;
2732 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2733 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2736 he
= hc_new_hostentry(hc
, a
, ipa_zero(ll
) ? a
: ll
, dep
, k
);
2737 rt_update_hostentry(tab
, he
);
2743 * Documentation for functions declared inline in route.h
2748 * net_find - find a network entry
2749 * @tab: a routing table
2750 * @addr: address of the network
2752 * net_find() looks up the given network in routing table @tab and
2753 * returns a pointer to its &net entry or %NULL if no such network
2756 static inline net
*net_find(rtable
*tab
, net_addr
*addr
)
2760 * net_get - obtain a network entry
2761 * @tab: a routing table
2762 * @addr: address of the network
2764 * net_get() looks up the given network in routing table @tab and
2765 * returns a pointer to its &net entry. If no such entry exists, it's
2768 static inline net
*net_get(rtable
*tab
, net_addr
*addr
)
2772 * rte_cow - copy a route for writing
2773 * @r: a route entry to be copied
2775 * rte_cow() takes a &rte and prepares it for modification. The exact action
2776 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2777 * just returned unchanged, else a new temporary entry with the same contents
2780 * The primary use of this function is inside the filter machinery -- when
2781 * a filter wants to modify &rte contents (to change the preference or to
2782 * attach another set of attributes), it must ensure that the &rte is not
2783 * shared with anyone else (and especially that it isn't stored in any routing
2786 * Result: a pointer to the new writable &rte.
2788 static inline rte
* rte_cow(rte
*r
)