]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-table.c
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"
37 #include "nest/iface.h"
38 #include "lib/resource.h"
39 #include "lib/event.h"
40 #include "lib/string.h"
41 #include "conf/conf.h"
42 #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
;
51 static list routing_tables
;
53 static byte
*rt_format_via(rte
*e
);
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
);
58 static inline int rt_prune_table(rtable
*tab
);
59 static inline void rt_schedule_gc(rtable
*tab
);
60 static inline void rt_schedule_prune(rtable
*tab
);
63 /* Like fib_route(), but skips empty net entries */
65 net_route(rtable
*tab
, ip_addr a
, int len
)
72 a0
= ipa_and(a
, ipa_mkmask(len
));
73 n
= fib_find(&tab
->fib
, &a0
, len
);
74 if (n
&& rte_is_valid(n
->routes
))
82 rte_init(struct fib_node
*N
)
91 * rte_find - find a route
95 * The rte_find() function returns a route for destination @net
96 * which is from route source @src.
99 rte_find(net
*net
, struct rte_src
*src
)
101 rte
*e
= net
->routes
;
103 while (e
&& e
->attrs
->src
!= src
)
109 * rte_get_temp - get a temporary &rte
110 * @a: attributes to assign to the new route (a &rta; in case it's
111 * un-cached, rte_update() will create a cached copy automatically)
113 * Create a temporary &rte and bind it with the attributes @a.
114 * Also set route preference to the default preference set for
120 rte
*e
= sl_alloc(rte_slab
);
124 e
->pref
= a
->src
->proto
->preference
;
131 rte
*e
= sl_alloc(rte_slab
);
133 memcpy(e
, r
, sizeof(rte
));
134 e
->attrs
= rta_clone(r
->attrs
);
140 * rte_cow_rta - get a private writable copy of &rte with writable &rta
141 * @r: a route entry to be copied
142 * @lp: a linpool from which to allocate &rta
144 * rte_cow_rta() takes a &rte and prepares it and associated &rta for
145 * modification. There are three possibilities: First, both &rte and &rta are
146 * private copies, in that case they are returned unchanged. Second, &rte is
147 * private copy, but &rta is cached, in that case &rta is duplicated using
148 * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
149 * both structures are duplicated by rte_do_cow() and rta_do_cow().
151 * Note that in the second case, cached &rta loses one reference, while private
152 * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
153 * nexthops, ...) with it. To work properly, original shared &rta should have
154 * another reference during the life of created private copy.
156 * Result: a pointer to the new writable &rte with writable &rta.
159 rte_cow_rta(rte
*r
, linpool
*lp
)
161 if (!rta_is_cached(r
->attrs
))
165 rta
*a
= rta_do_cow(r
->attrs
, lp
);
171 static int /* Actually better or at least as good as */
172 rte_better(rte
*new, rte
*old
)
174 int (*better
)(rte
*, rte
*);
176 if (!rte_is_valid(old
))
178 if (!rte_is_valid(new))
181 if (new->pref
> old
->pref
)
183 if (new->pref
< old
->pref
)
185 if (new->attrs
->src
->proto
->proto
!= old
->attrs
->src
->proto
->proto
)
188 * If the user has configured protocol preferences, so that two different protocols
189 * have the same preference, try to break the tie by comparing addresses. Not too
190 * useful, but keeps the ordering of routes unambiguous.
192 return new->attrs
->src
->proto
->proto
> old
->attrs
->src
->proto
->proto
;
194 if (better
= new->attrs
->src
->proto
->rte_better
)
195 return better(new, old
);
200 rte_mergable(rte
*pri
, rte
*sec
)
202 int (*mergable
)(rte
*, rte
*);
204 if (!rte_is_valid(pri
) || !rte_is_valid(sec
))
207 if (pri
->pref
!= sec
->pref
)
210 if (pri
->attrs
->src
->proto
->proto
!= sec
->attrs
->src
->proto
->proto
)
213 if (mergable
= pri
->attrs
->src
->proto
->rte_mergable
)
214 return mergable(pri
, sec
);
220 rte_trace(struct proto
*p
, rte
*e
, int dir
, char *msg
)
222 log(L_TRACE
"%s %c %s %I/%d %s", p
->name
, dir
, msg
, e
->net
->n
.prefix
, e
->net
->n
.pxlen
, rt_format_via(e
));
226 rte_trace_in(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
229 rte_trace(p
, e
, '>', msg
);
233 rte_trace_out(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
236 rte_trace(p
, e
, '<', msg
);
240 export_filter_(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, linpool
*pool
, int silent
)
242 struct proto
*p
= ah
->proto
;
243 struct filter
*filter
= ah
->out_filter
;
244 struct proto_stats
*stats
= ah
->stats
;
245 ea_list
*tmpb
= NULL
;
255 *tmpa
= rte_make_tmp_attrs(rt
, pool
);
257 v
= p
->import_control
? p
->import_control(p
, &rt
, tmpa
, pool
) : 0;
263 stats
->exp_updates_rejected
++;
265 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
271 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
275 v
= filter
&& ((filter
== FILTER_REJECT
) ||
276 (f_run(filter
, &rt
, tmpa
, pool
,
277 FF_FORCE_TMPATTR
| (silent
? FF_SILENT
: 0)) > F_ACCEPT
));
283 stats
->exp_updates_filtered
++;
284 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
294 /* Discard temporary rte */
301 export_filter(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
303 return export_filter_(ah
, rt0
, rt_free
, tmpa
, rte_update_pool
, silent
);
307 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
309 struct proto
*p
= ah
->proto
;
310 struct proto_stats
*stats
= ah
->stats
;
314 * First, apply export limit.
316 * Export route limits has several problems. Because exp_routes
317 * counter is reset before refeed, we don't really know whether
318 * limit is breached and whether the update is new or not. Therefore
319 * the number of really exported routes may exceed the limit
320 * temporarily (routes exported before and new routes in refeed).
322 * Minor advantage is that if the limit is decreased and refeed is
323 * requested, the number of exported routes really decrease.
325 * Second problem is that with export limits, we don't know whether
326 * old was really exported (it might be blocked by limit). When a
327 * withdraw is exported, we announce it even when the previous
328 * update was blocked. This is not a big issue, but the same problem
329 * is in updating exp_routes counter. Therefore, to be consistent in
330 * increases and decreases of exp_routes, we count exported routes
331 * regardless of blocking by limits.
333 * Similar problem is in handling updates - when a new route is
334 * received and blocking is active, the route would be blocked, but
335 * when an update for the route will be received later, the update
336 * would be propagated (as old != NULL). Therefore, we have to block
337 * also non-new updates (contrary to import blocking).
340 struct proto_limit
*l
= ah
->out_limit
;
343 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
344 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
346 if (l
->state
== PLS_BLOCKED
)
348 stats
->exp_routes
++; /* see note above */
349 stats
->exp_updates_rejected
++;
350 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
360 stats
->exp_updates_accepted
++;
362 stats
->exp_withdraws_accepted
++;
364 /* Hack: We do not decrease exp_routes during refeed, we instead
365 reset exp_routes at the start of refeed. */
371 if (p
->debug
& D_ROUTES
)
374 rte_trace_out(D_ROUTES
, p
, new, "replaced");
376 rte_trace_out(D_ROUTES
, p
, new, "added");
378 rte_trace_out(D_ROUTES
, p
, old
, "removed");
381 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
387 t
->next
= new->attrs
->eattrs
;
388 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
392 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
396 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new0
, rte
*old0
, int refeed
)
398 struct proto
*p
= ah
->proto
;
399 struct proto_stats
*stats
= ah
->stats
;
403 rte
*new_free
= NULL
;
404 rte
*old_free
= NULL
;
405 ea_list
*tmpa
= NULL
;
408 stats
->exp_updates_received
++;
410 stats
->exp_withdraws_received
++;
413 * This is a tricky part - we don't know whether route 'old' was
414 * exported to protocol 'p' or was filtered by the export filter.
415 * We try to run the export filter to know this to have a correct
416 * value in 'old' argument of rte_update (and proper filter value)
418 * FIXME - this is broken because 'configure soft' may change
419 * filters but keep routes. Refeed is expected to be called after
420 * change of the filters and with old == new, therefore we do not
421 * even try to run the filter on an old route, This may lead to
422 * 'spurious withdraws' but ensure that there are no 'missing
425 * This is not completely safe as there is a window between
426 * reconfiguration and the end of refeed - if a newly filtered
427 * route disappears during this period, proper withdraw is not
428 * sent (because old would be also filtered) and the route is
429 * not refeeded (because it disappeared before that).
433 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
436 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
441 * As mentioned above, 'old' value may be incorrect in some race conditions.
442 * We generally ignore it with the exception of withdraw to pipe protocol.
443 * In that case we rather propagate unfiltered withdraws regardless of
444 * export filters to ensure that when a protocol is flushed, its routes are
445 * removed from all tables. Possible spurious unfiltered withdraws are not
446 * problem here as they are ignored if there is no corresponding route at
447 * the other end of the pipe. We directly call rt_notify() hook instead of
448 * do_rt_notify() to avoid logging and stat counters.
452 if ((p
->proto
== &proto_pipe
) && !new0
&& (p
!= old0
->sender
->proto
))
453 p
->rt_notify(p
, ah
->table
, net
, NULL
, old0
, NULL
);
459 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
461 /* Discard temporary rte's */
469 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
, int feed
)
471 // struct proto *p = ah->proto;
472 struct proto_stats
*stats
= ah
->stats
;
475 rte
*new_best
= NULL
;
476 rte
*old_best
= NULL
;
477 rte
*new_free
= NULL
;
478 rte
*old_free
= NULL
;
479 ea_list
*tmpa
= NULL
;
481 /* Used to track whether we met old_changed position. If before_old is NULL
482 old_changed was the first and we met it implicitly before current best route. */
483 int old_meet
= old_changed
&& !before_old
;
485 /* Note that before_old is either NULL or valid (not rejected) route.
486 If old_changed is valid, before_old have to be too. If old changed route
487 was not valid, caller must use NULL for both old_changed and before_old. */
490 stats
->exp_updates_received
++;
492 stats
->exp_withdraws_received
++;
494 /* First, find the new_best route - first accepted by filters */
495 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
497 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
500 /* Note if we walked around the position of old_changed route */
506 * Second, handle the feed case. That means we do not care for
507 * old_best. It is NULL for feed, and the new_best for refeed.
508 * For refeed, there is a hack similar to one in rt_notify_basic()
509 * to ensure withdraws in case of changed filters
513 if (feed
== 2) /* refeed */
514 old_best
= new_best
? new_best
:
515 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
519 if (!new_best
&& !old_best
)
526 * Now, we find the old_best route. Generally, it is the same as the
527 * new_best, unless new_best is the same as new_changed or
528 * old_changed is accepted before new_best.
530 * There are four cases:
532 * - We would find and accept old_changed before new_best, therefore
533 * old_changed is old_best. In remaining cases we suppose this
536 * - We found no new_best, therefore there is also no old_best and
537 * we ignore this withdraw.
539 * - We found new_best different than new_changed, therefore
540 * old_best is the same as new_best and we ignore this update.
542 * - We found new_best the same as new_changed, therefore it cannot
543 * be old_best and we have to continue search for old_best.
548 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
555 /* Third case, we use r instead of new_best, because export_filter() could change it */
556 if (r
!= new_changed
)
564 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
566 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
570 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
574 /* Implicitly, old_best is NULL and new_best is non-NULL */
577 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
579 /* Discard temporary rte's */
588 mpnh_merge_rta(struct mpnh
*nhs
, rta
*a
, linpool
*pool
, int max
)
590 struct mpnh nh
= { .gw
= a
->gw
, .iface
= a
->iface
};
591 struct mpnh
*nh2
= (a
->dest
== RTD_MULTIPATH
) ? a
->nexthops
: &nh
;
592 return mpnh_merge(nhs
, nh2
, 1, 0, max
, pool
);
596 rt_export_merged(struct announce_hook
*ah
, net
*net
, rte
**rt_free
, ea_list
**tmpa
, linpool
*pool
, int silent
)
598 // struct proto *p = ah->proto;
599 struct mpnh
*nhs
= NULL
;
600 rte
*best0
, *best
, *rt0
, *rt
, *tmp
;
605 if (!rte_is_valid(best0
))
608 best
= export_filter_(ah
, best0
, rt_free
, tmpa
, pool
, silent
);
610 if (!best
|| !rte_is_reachable(best
))
613 for (rt0
= best0
->next
; rt0
; rt0
= rt0
->next
)
615 if (!rte_mergable(best0
, rt0
))
618 rt
= export_filter_(ah
, rt0
, &tmp
, NULL
, pool
, 1);
623 if (rte_is_reachable(rt
))
624 nhs
= mpnh_merge_rta(nhs
, rt
->attrs
, pool
, ah
->proto
->merge_limit
);
632 nhs
= mpnh_merge_rta(nhs
, best
->attrs
, pool
, ah
->proto
->merge_limit
);
636 best
= rte_cow_rta(best
, pool
);
637 best
->attrs
->dest
= RTD_MULTIPATH
;
638 best
->attrs
->nexthops
= nhs
;
650 rt_notify_merged(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
,
651 rte
*new_best
, rte
*old_best
, int refeed
)
653 // struct proto *p = ah->proto;
655 rte
*new_best_free
= NULL
;
656 rte
*old_best_free
= NULL
;
657 rte
*new_changed_free
= NULL
;
658 rte
*old_changed_free
= NULL
;
659 ea_list
*tmpa
= NULL
;
661 /* We assume that all rte arguments are either NULL or rte_is_valid() */
663 /* This check should be done by the caller */
664 if (!new_best
&& !old_best
)
667 /* Check whether the change is relevant to the merged route */
668 if ((new_best
== old_best
) && !refeed
)
670 new_changed
= rte_mergable(new_best
, new_changed
) ?
671 export_filter(ah
, new_changed
, &new_changed_free
, NULL
, 1) : NULL
;
673 old_changed
= rte_mergable(old_best
, old_changed
) ?
674 export_filter(ah
, old_changed
, &old_changed_free
, NULL
, 1) : NULL
;
676 if (!new_changed
&& !old_changed
)
681 ah
->stats
->exp_updates_received
++;
683 ah
->stats
->exp_withdraws_received
++;
685 /* Prepare new merged route */
687 new_best
= rt_export_merged(ah
, net
, &new_best_free
, &tmpa
, rte_update_pool
, 0);
689 /* Prepare old merged route (without proper merged next hops) */
690 /* There are some issues with running filter on old route - see rt_notify_basic() */
691 if (old_best
&& !refeed
)
692 old_best
= export_filter(ah
, old_best
, &old_best_free
, NULL
, 1);
694 if (new_best
|| old_best
)
695 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, refeed
);
697 /* Discard temporary rte's */
699 rte_free(new_best_free
);
701 rte_free(old_best_free
);
702 if (new_changed_free
)
703 rte_free(new_changed_free
);
704 if (old_changed_free
)
705 rte_free(old_changed_free
);
710 * rte_announce - announce a routing table change
711 * @tab: table the route has been added to
712 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
713 * @net: network in question
714 * @new: the new route to be announced
715 * @old: the previous route for the same network
716 * @new_best: the new best route for the same network
717 * @old_best: the previous best route for the same network
718 * @before_old: The previous route before @old for the same network.
719 * If @before_old is NULL @old was the first.
721 * This function gets a routing table update and announces it
722 * to all protocols that acccepts given type of route announcement
723 * and are connected to the same table by their announcement hooks.
725 * Route announcement of type %RA_OPTIMAL si generated when optimal
726 * route (in routing table @tab) changes. In that case @old stores the
729 * Route announcement of type %RA_ANY si generated when any route (in
730 * routing table @tab) changes In that case @old stores the old route
731 * from the same protocol.
733 * For each appropriate protocol, we first call its import_control()
734 * hook which performs basic checks on the route (each protocol has a
735 * right to veto or force accept of the route before any filter is
736 * asked) and adds default values of attributes specific to the new
737 * protocol (metrics, tags etc.). Then it consults the protocol's
738 * export filter and if it accepts the route, the rt_notify() hook of
739 * the protocol gets called.
742 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
743 rte
*new_best
, rte
*old_best
, rte
*before_old
)
745 if (!rte_is_valid(new))
748 if (!rte_is_valid(old
))
749 old
= before_old
= NULL
;
751 if (!rte_is_valid(new_best
))
754 if (!rte_is_valid(old_best
))
760 if (type
== RA_OPTIMAL
)
763 new->attrs
->src
->proto
->stats
.pref_routes
++;
765 old
->attrs
->src
->proto
->stats
.pref_routes
--;
768 rt_notify_hostcache(tab
, net
);
771 struct announce_hook
*a
;
772 WALK_LIST(a
, tab
->hooks
)
774 ASSERT(a
->proto
->export_state
!= ES_DOWN
);
775 if (a
->proto
->accept_ra_types
== type
)
776 if (type
== RA_ACCEPTED
)
777 rt_notify_accepted(a
, net
, new, old
, before_old
, 0);
778 else if (type
== RA_MERGED
)
779 rt_notify_merged(a
, net
, new, old
, new_best
, old_best
, 0);
781 rt_notify_basic(a
, net
, new, old
, 0);
791 if ((n
->n
.pxlen
> BITS_PER_IP_ADDRESS
) || !ip_is_prefix(n
->n
.prefix
,n
->n
.pxlen
))
793 log(L_WARN
"Ignoring bogus prefix %I/%d received via %s",
794 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
798 c
= ipa_classify_net(n
->n
.prefix
);
799 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
801 log(L_WARN
"Ignoring bogus route %I/%d received via %s",
802 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
806 if ((e
->attrs
->dest
== RTD_MULTIPATH
) && !mpnh_is_sorted(e
->attrs
->nexthops
))
808 log(L_WARN
"Ignoring unsorted multipath route %I/%d received via %s",
809 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
817 * rte_free - delete a &rte
818 * @e: &rte to be deleted
820 * rte_free() deletes the given &rte from the routing table it's linked to.
825 if (rta_is_cached(e
->attrs
))
827 sl_free(rte_slab
, e
);
831 rte_free_quick(rte
*e
)
834 sl_free(rte_slab
, e
);
838 rte_same(rte
*x
, rte
*y
)
841 x
->attrs
== y
->attrs
&&
842 x
->flags
== y
->flags
&&
843 x
->pflags
== y
->pflags
&&
844 x
->pref
== y
->pref
&&
845 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
848 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
851 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
853 struct proto
*p
= ah
->proto
;
854 struct rtable
*table
= ah
->table
;
855 struct proto_stats
*stats
= ah
->stats
;
856 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
857 rte
*before_old
= NULL
;
858 rte
*old_best
= net
->routes
;
862 k
= &net
->routes
; /* Find and remove original route from the same protocol */
865 if (old
->attrs
->src
== src
)
867 /* If there is the same route in the routing table but from
868 * a different sender, then there are two paths from the
869 * source protocol to this routing table through transparent
870 * pipes, which is not allowed.
872 * We log that and ignore the route. If it is withdraw, we
873 * ignore it completely (there might be 'spurious withdraws',
874 * see FIXME in do_rte_announce())
876 if (old
->sender
->proto
!= p
)
880 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %I/%d to table %s",
881 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
887 if (new && rte_same(old
, new))
889 /* No changes, ignore the new route */
891 if (!rte_is_filtered(new))
893 stats
->imp_updates_ignored
++;
894 rte_trace_in(D_ROUTES
, p
, new, "ignored");
912 stats
->imp_withdraws_ignored
++;
916 int new_ok
= rte_is_ok(new);
917 int old_ok
= rte_is_ok(old
);
919 struct proto_limit
*l
= ah
->rx_limit
;
920 if (l
&& !old
&& new)
922 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
924 if (all_routes
>= l
->limit
)
925 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
927 if (l
->state
== PLS_BLOCKED
)
929 /* In receive limit the situation is simple, old is NULL so
930 we just free new and exit like nothing happened */
932 stats
->imp_updates_ignored
++;
933 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
940 if (l
&& !old_ok
&& new_ok
)
942 if (stats
->imp_routes
>= l
->limit
)
943 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
945 if (l
->state
== PLS_BLOCKED
)
947 /* In import limit the situation is more complicated. We
948 shouldn't just drop the route, we should handle it like
949 it was filtered. We also have to continue the route
950 processing if old or new is non-NULL, but we should exit
951 if both are NULL as this case is probably assumed to be
954 stats
->imp_updates_ignored
++;
955 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
957 if (ah
->in_keep_filtered
)
958 new->flags
|= REF_FILTERED
;
960 { rte_free_quick(new); new = NULL
; }
962 /* Note that old && !new could be possible when
963 ah->in_keep_filtered changed in the recent past. */
974 stats
->imp_updates_accepted
++;
976 stats
->imp_withdraws_accepted
++;
978 stats
->imp_withdraws_ignored
++;
983 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
985 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
987 if (table
->config
->sorted
)
989 /* If routes are sorted, just insert new route to appropriate position */
992 if (before_old
&& !rte_better(new, before_old
))
993 k
= &before_old
->next
;
997 for (; *k
; k
=&(*k
)->next
)
998 if (rte_better(new, *k
))
1007 /* If routes are not sorted, find the best route and move it on
1008 the first position. There are several optimized cases. */
1010 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
1011 goto do_recalculate
;
1013 if (new && rte_better(new, old_best
))
1015 /* The first case - the new route is cleary optimal,
1016 we link it at the first position */
1018 new->next
= net
->routes
;
1021 else if (old
== old_best
)
1023 /* The second case - the old best route disappeared, we add the
1024 new route (if we have any) to the list (we don't care about
1025 position) and then we elect the new optimal route and relink
1026 that route at the first position and announce it. New optimal
1027 route might be NULL if there is no more routes */
1030 /* Add the new route to the list */
1033 new->next
= net
->routes
;
1037 /* Find a new optimal route (if there is any) */
1040 rte
**bp
= &net
->routes
;
1041 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
1042 if (rte_better(*k
, *bp
))
1048 best
->next
= net
->routes
;
1054 /* The third case - the new route is not better than the old
1055 best route (therefore old_best != NULL) and the old best
1056 route was not removed (therefore old_best == net->routes).
1057 We just link the new route after the old best route. */
1059 ASSERT(net
->routes
!= NULL
);
1060 new->next
= net
->routes
->next
;
1061 net
->routes
->next
= new;
1063 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1069 /* Log the route change */
1070 if (p
->debug
& D_ROUTES
)
1073 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
1076 if (old
!= old_best
)
1077 rte_trace(p
, old
, '>', "removed");
1078 else if (rte_is_ok(net
->routes
))
1079 rte_trace(p
, old
, '>', "removed [replaced]");
1081 rte_trace(p
, old
, '>', "removed [sole]");
1085 /* Propagate the route change */
1086 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, NULL
, NULL
);
1087 if (net
->routes
!= old_best
)
1088 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, NULL
, NULL
);
1089 if (table
->config
->sorted
)
1090 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, NULL
, NULL
, before_old
);
1091 rte_announce(table
, RA_MERGED
, net
, new, old
, net
->routes
, old_best
, NULL
);
1094 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
1095 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
1096 rt_schedule_gc(table
);
1098 if (old_ok
&& p
->rte_remove
)
1099 p
->rte_remove(net
, old
);
1100 if (new_ok
&& p
->rte_insert
)
1101 p
->rte_insert(net
, new);
1104 rte_free_quick(old
);
1107 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
1110 rte_update_lock(void)
1112 rte_update_nest_cnt
++;
1116 rte_update_unlock(void)
1118 if (!--rte_update_nest_cnt
)
1119 lp_flush(rte_update_pool
);
1123 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
1125 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
1127 *dummy
= net
->routes
;
1128 net
->routes
= (*dummy
)->next
;
1133 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
1137 (*dummy
)->next
= net
->routes
;
1138 net
->routes
= *dummy
;
1143 * rte_update - enter a new update to a routing table
1144 * @table: table to be updated
1145 * @ah: pointer to table announce hook
1146 * @net: network node
1147 * @p: protocol submitting the update
1148 * @src: protocol originating the update
1149 * @new: a &rte representing the new route or %NULL for route removal.
1151 * This function is called by the routing protocols whenever they discover
1152 * a new route or wish to update/remove an existing route. The right announcement
1153 * sequence is to build route attributes first (either un-cached with @aflags set
1154 * to zero or a cached one using rta_lookup(); in this case please note that
1155 * you need to increase the use count of the attributes yourself by calling
1156 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1157 * the appropriate data and finally submit the new &rte by calling rte_update().
1159 * @src specifies the protocol that originally created the route and the meaning
1160 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1161 * same value as @new->attrs->proto. @p specifies the protocol that called
1162 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1163 * stores @p in @new->sender;
1165 * When rte_update() gets any route, it automatically validates it (checks,
1166 * whether the network and next hop address are valid IP addresses and also
1167 * whether a normal routing protocol doesn't try to smuggle a host or link
1168 * scope route to the table), converts all protocol dependent attributes stored
1169 * in the &rte to temporary extended attributes, consults import filters of the
1170 * protocol to see if the route should be accepted and/or its attributes modified,
1171 * stores the temporary attributes back to the &rte.
1173 * Now, having a "public" version of the route, we
1174 * automatically find any old route defined by the protocol @src
1175 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1176 * recalculate the optimal route for this destination and finally broadcast
1177 * the change (if any) to all routing protocols by calling rte_announce().
1179 * All memory used for attribute lists and other temporary allocations is taken
1180 * from a special linear pool @rte_update_pool and freed when rte_update()
1185 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
1187 struct proto
*p
= ah
->proto
;
1188 struct proto_stats
*stats
= ah
->stats
;
1189 struct filter
*filter
= ah
->in_filter
;
1190 ea_list
*tmpa
= NULL
;
1198 stats
->imp_updates_received
++;
1199 if (!rte_validate(new))
1201 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1202 stats
->imp_updates_invalid
++;
1206 if (filter
== FILTER_REJECT
)
1208 stats
->imp_updates_filtered
++;
1209 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1211 if (! ah
->in_keep_filtered
)
1214 /* new is a private copy, i could modify it */
1215 new->flags
|= REF_FILTERED
;
1219 tmpa
= rte_make_tmp_attrs(new, rte_update_pool
);
1220 if (filter
&& (filter
!= FILTER_REJECT
))
1222 ea_list
*old_tmpa
= tmpa
;
1223 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
1226 stats
->imp_updates_filtered
++;
1227 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1229 if (! ah
->in_keep_filtered
)
1232 new->flags
|= REF_FILTERED
;
1234 if (tmpa
!= old_tmpa
&& src
->proto
->store_tmp_attrs
)
1235 src
->proto
->store_tmp_attrs(new, tmpa
);
1238 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1239 new->attrs
= rta_lookup(new->attrs
);
1240 new->flags
|= REF_COW
;
1244 stats
->imp_withdraws_received
++;
1248 stats
->imp_withdraws_ignored
++;
1249 rte_update_unlock();
1255 rte_hide_dummy_routes(net
, &dummy
);
1256 rte_recalculate(ah
, net
, new, src
);
1257 rte_unhide_dummy_routes(net
, &dummy
);
1258 rte_update_unlock();
1267 /* Independent call to rte_announce(), used from next hop
1268 recalculation, outside of rte_update(). new must be non-NULL */
1270 rte_announce_i(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
1271 rte
*new_best
, rte
*old_best
)
1274 rte_announce(tab
, type
, net
, new, old
, new_best
, old_best
, NULL
);
1275 rte_update_unlock();
1279 rte_discard(rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1282 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1283 rte_update_unlock();
1286 /* Check rtable for best route to given net whether it would be exported do p */
1288 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1290 net
*n
= net_find(t
, prefix
, pxlen
);
1291 rte
*rt
= n
? n
->routes
: NULL
;
1293 if (!rte_is_valid(rt
))
1298 /* Rest is stripped down export_filter() */
1299 ea_list
*tmpa
= rte_make_tmp_attrs(rt
, rte_update_pool
);
1300 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1301 if (v
== RIC_PROCESS
)
1302 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
,
1303 FF_FORCE_TMPATTR
| FF_SILENT
) <= F_ACCEPT
);
1305 /* Discard temporary rte */
1306 if (rt
!= n
->routes
)
1309 rte_update_unlock();
1316 * rt_refresh_begin - start a refresh cycle
1317 * @t: related routing table
1318 * @ah: related announce hook
1320 * This function starts a refresh cycle for given routing table and announce
1321 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1322 * routes to the routing table (by rte_update()). After that, all protocol
1323 * routes (more precisely routes with @ah as @sender) not sent during the
1324 * refresh cycle but still in the table from the past are pruned. This is
1325 * implemented by marking all related routes as stale by REF_STALE flag in
1326 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1327 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1330 rt_refresh_begin(rtable
*t
, struct announce_hook
*ah
)
1335 FIB_WALK(&t
->fib
, fn
)
1338 for (e
= n
->routes
; e
; e
= e
->next
)
1339 if (e
->sender
== ah
)
1340 e
->flags
|= REF_STALE
;
1346 * rt_refresh_end - end a refresh cycle
1347 * @t: related routing table
1348 * @ah: related announce hook
1350 * This function starts a refresh cycle for given routing table and announce
1351 * hook. See rt_refresh_begin() for description of refresh cycles.
1354 rt_refresh_end(rtable
*t
, struct announce_hook
*ah
)
1360 FIB_WALK(&t
->fib
, fn
)
1363 for (e
= n
->routes
; e
; e
= e
->next
)
1364 if ((e
->sender
== ah
) && (e
->flags
& REF_STALE
))
1366 e
->flags
|= REF_DISCARD
;
1373 rt_schedule_prune(t
);
1378 * rte_dump - dump a route
1379 * @e: &rte to be dumped
1381 * This functions dumps contents of a &rte to debug output.
1387 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1388 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1390 if (e
->attrs
->src
->proto
->proto
->dump_attrs
)
1391 e
->attrs
->src
->proto
->proto
->dump_attrs(e
);
1396 * rt_dump - dump a routing table
1397 * @t: routing table to be dumped
1399 * This function dumps contents of a given routing table to debug output.
1406 struct announce_hook
*a
;
1408 debug("Dump of routing table <%s>\n", t
->name
);
1412 FIB_WALK(&t
->fib
, fn
)
1415 for(e
=n
->routes
; e
; e
=e
->next
)
1419 WALK_LIST(a
, t
->hooks
)
1420 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1425 * rt_dump_all - dump all routing tables
1427 * This function dumps contents of all routing tables to debug output.
1434 WALK_LIST(t
, routing_tables
)
1439 rt_schedule_prune(rtable
*tab
)
1441 rt_mark_for_prune(tab
);
1442 ev_schedule(tab
->rt_event
);
1446 rt_schedule_gc(rtable
*tab
)
1448 if (tab
->gc_scheduled
)
1451 tab
->gc_scheduled
= 1;
1452 ev_schedule(tab
->rt_event
);
1456 rt_schedule_hcu(rtable
*tab
)
1458 if (tab
->hcu_scheduled
)
1461 tab
->hcu_scheduled
= 1;
1462 ev_schedule(tab
->rt_event
);
1466 rt_schedule_nhu(rtable
*tab
)
1468 if (tab
->nhu_state
== 0)
1469 ev_schedule(tab
->rt_event
);
1471 /* state change 0->1, 2->3 */
1472 tab
->nhu_state
|= 1;
1477 rt_prune_nets(rtable
*tab
)
1479 struct fib_iterator fit
;
1480 int ncnt
= 0, ndel
= 0;
1483 fib_check(&tab
->fib
);
1486 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1488 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1492 if (!n
->routes
) /* Orphaned FIB entry */
1494 FIB_ITERATE_PUT(&fit
, f
);
1495 fib_delete(&tab
->fib
, f
);
1501 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1503 tab
->gc_counter
= 0;
1505 tab
->gc_scheduled
= 0;
1513 if (tab
->hcu_scheduled
)
1514 rt_update_hostcache(tab
);
1517 rt_next_hop_update(tab
);
1519 if (tab
->prune_state
)
1520 if (!rt_prune_table(tab
))
1522 /* Table prune unfinished */
1523 ev_schedule(tab
->rt_event
);
1527 if (tab
->gc_scheduled
)
1530 rt_prune_sources(); // FIXME this should be moved to independent event
1535 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1537 bzero(t
, sizeof(*t
));
1538 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1541 init_list(&t
->hooks
);
1544 t
->rt_event
= ev_new(p
);
1545 t
->rt_event
->hook
= rt_event
;
1546 t
->rt_event
->data
= t
;
1552 * rt_init - initialize routing tables
1554 * This function is called during BIRD startup. It initializes the
1555 * routing table module.
1561 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1562 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1563 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1564 init_list(&routing_tables
);
1569 rt_prune_step(rtable
*tab
, int *limit
)
1571 struct fib_iterator
*fit
= &tab
->prune_fit
;
1573 DBG("Pruning route table %s\n", tab
->name
);
1575 fib_check(&tab
->fib
);
1578 if (tab
->prune_state
== RPS_NONE
)
1581 if (tab
->prune_state
== RPS_SCHEDULED
)
1583 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1584 tab
->prune_state
= RPS_RUNNING
;
1588 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1590 net
*n
= (net
*) fn
;
1594 for (e
=n
->routes
; e
; e
=e
->next
)
1595 if (e
->sender
->proto
->flushing
|| (e
->flags
& REF_DISCARD
))
1599 FIB_ITERATE_PUT(fit
, fn
);
1608 if (!n
->routes
) /* Orphaned FIB entry */
1610 FIB_ITERATE_PUT(fit
, fn
);
1611 fib_delete(&tab
->fib
, fn
);
1615 FIB_ITERATE_END(fn
);
1618 fib_check(&tab
->fib
);
1621 tab
->prune_state
= RPS_NONE
;
1626 * rt_prune_table - prune a routing table
1627 * @tab: a routing table for pruning
1629 * This function scans the routing table @tab and removes routes belonging to
1630 * flushing protocols, discarded routes and also stale network entries, in a
1631 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1632 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1633 * protocol flushing loop, but it is called from rt_event() for just one routing
1636 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1637 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1640 rt_prune_table(rtable
*tab
)
1643 return rt_prune_step(tab
, &limit
);
1647 * rt_prune_loop - prune routing tables
1649 * The prune loop scans routing tables and removes routes belonging to flushing
1650 * protocols, discarded routes and also stale network entries. Returns 1 when
1651 * all such routes are pruned. It is a part of the protocol flushing loop.
1659 WALK_LIST(t
, routing_tables
)
1660 if (! rt_prune_step(t
, &limit
))
1667 rt_preconfig(struct config
*c
)
1669 struct symbol
*s
= cf_get_symbol("master");
1671 init_list(&c
->tables
);
1672 c
->master_rtc
= rt_new_table(s
);
1677 * Some functions for handing internal next hop updates
1678 * triggered by rt_schedule_nhu().
1682 rta_next_hop_outdated(rta
*a
)
1684 struct hostentry
*he
= a
->hostentry
;
1690 return a
->dest
!= RTD_UNREACHABLE
;
1692 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1693 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1694 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1698 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1701 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1704 a
->igp_metric
= he
->igp_metric
;
1705 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1709 rt_next_hop_update_rte(rtable
*tab UNUSED
, rte
*old
)
1712 memcpy(&a
, old
->attrs
, sizeof(rta
));
1713 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1716 rte
*e
= sl_alloc(rte_slab
);
1717 memcpy(e
, old
, sizeof(rte
));
1718 e
->attrs
= rta_lookup(&a
);
1724 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1726 rte
**k
, *e
, *new, *old_best
, **new_best
;
1728 int free_old_best
= 0;
1730 old_best
= n
->routes
;
1734 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1735 if (rta_next_hop_outdated(e
->attrs
))
1737 new = rt_next_hop_update_rte(tab
, e
);
1740 rte_announce_i(tab
, RA_ANY
, n
, new, e
, NULL
, NULL
);
1741 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1743 /* Call a pre-comparison hook */
1744 /* Not really an efficient way to compute this */
1745 if (e
->attrs
->src
->proto
->rte_recalculate
)
1746 e
->attrs
->src
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1750 else /* Freeing of the old best rte is postponed */
1760 /* Find the new best route */
1762 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1764 if (!new_best
|| rte_better(e
, *new_best
))
1768 /* Relink the new best route to the first position */
1770 if (new != n
->routes
)
1772 *new_best
= new->next
;
1773 new->next
= n
->routes
;
1777 /* Announce the new best route */
1778 if (new != old_best
)
1780 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
, NULL
, NULL
);
1781 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1784 /* FIXME: Better announcement of merged routes */
1785 rte_announce_i(tab
, RA_MERGED
, n
, new, old_best
, new, old_best
);
1788 rte_free_quick(old_best
);
1794 rt_next_hop_update(rtable
*tab
)
1796 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1799 if (tab
->nhu_state
== 0)
1802 if (tab
->nhu_state
== 1)
1804 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1808 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1812 FIB_ITERATE_PUT(fit
, fn
);
1813 ev_schedule(tab
->rt_event
);
1816 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1818 FIB_ITERATE_END(fn
);
1820 /* state change 2->0, 3->1 */
1821 tab
->nhu_state
&= 1;
1823 if (tab
->nhu_state
> 0)
1824 ev_schedule(tab
->rt_event
);
1828 struct rtable_config
*
1829 rt_new_table(struct symbol
*s
)
1831 /* Hack that allows to 'redefine' the master table */
1832 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1835 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1837 cf_define_symbol(s
, SYM_TABLE
, c
);
1839 add_tail(&new_config
->tables
, &c
->n
);
1840 c
->gc_max_ops
= 1000;
1846 * rt_lock_table - lock a routing table
1847 * @r: routing table to be locked
1849 * Lock a routing table, because it's in use by a protocol,
1850 * preventing it from being freed when it gets undefined in a new
1854 rt_lock_table(rtable
*r
)
1860 * rt_unlock_table - unlock a routing table
1861 * @r: routing table to be unlocked
1863 * Unlock a routing table formerly locked by rt_lock_table(),
1864 * that is decrease its use count and delete it if it's scheduled
1865 * for deletion by configuration changes.
1868 rt_unlock_table(rtable
*r
)
1870 if (!--r
->use_count
&& r
->deleted
)
1872 struct config
*conf
= r
->deleted
;
1873 DBG("Deleting routing table %s\n", r
->name
);
1874 r
->config
->table
= NULL
;
1876 rt_free_hostcache(r
);
1881 config_del_obstacle(conf
);
1886 * rt_commit - commit new routing table configuration
1887 * @new: new configuration
1888 * @old: original configuration or %NULL if it's boot time config
1890 * Scan differences between @old and @new configuration and modify
1891 * the routing tables according to these changes. If @new defines a
1892 * previously unknown table, create it, if it omits a table existing
1893 * in @old, schedule it for deletion (it gets deleted when all protocols
1894 * disconnect from it by calling rt_unlock_table()), if it exists
1895 * in both configurations, leave it unchanged.
1898 rt_commit(struct config
*new, struct config
*old
)
1900 struct rtable_config
*o
, *r
;
1902 DBG("rt_commit:\n");
1905 WALK_LIST(o
, old
->tables
)
1907 rtable
*ot
= o
->table
;
1910 struct symbol
*sym
= cf_find_symbol(new, o
->name
);
1911 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1913 DBG("\t%s: same\n", o
->name
);
1918 if (o
->sorted
!= r
->sorted
)
1919 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1923 DBG("\t%s: deleted\n", o
->name
);
1925 config_add_obstacle(old
);
1927 rt_unlock_table(ot
);
1933 WALK_LIST(r
, new->tables
)
1936 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1937 DBG("\t%s: created\n", r
->name
);
1938 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1939 add_tail(&routing_tables
, &t
->n
);
1946 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1949 if (type
== RA_ACCEPTED
)
1950 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, p
->refeeding
? 2 : 1);
1951 else if (type
== RA_MERGED
)
1952 rt_notify_merged(h
, n
, NULL
, NULL
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1954 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1955 rte_update_unlock();
1959 * rt_feed_baby - advertise routes to a new protocol
1960 * @p: protocol to be fed
1962 * This function performs one pass of advertisement of routes to a newly
1963 * initialized protocol. It's called by the protocol code as long as it
1964 * has something to do. (We avoid transferring all the routes in single
1965 * pass in order not to monopolize CPU time.)
1968 rt_feed_baby(struct proto
*p
)
1970 struct announce_hook
*h
;
1971 struct fib_iterator
*fit
;
1974 if (!p
->feed_ahook
) /* Need to initialize first */
1978 DBG("Announcing routes to new protocol %s\n", p
->name
);
1979 p
->feed_ahook
= p
->ahooks
;
1980 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1983 fit
= p
->feed_iterator
;
1987 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1989 net
*n
= (net
*) fn
;
1993 FIB_ITERATE_PUT(fit
, fn
);
1997 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1999 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
2000 (p
->accept_ra_types
== RA_ACCEPTED
) ||
2001 (p
->accept_ra_types
== RA_MERGED
))
2002 if (rte_is_valid(e
))
2004 if (p
->export_state
!= ES_FEEDING
)
2005 return 1; /* In the meantime, the protocol fell down. */
2007 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
2011 if (p
->accept_ra_types
== RA_ANY
)
2012 for(e
= n
->routes
; e
; e
= e
->next
)
2014 if (p
->export_state
!= ES_FEEDING
)
2015 return 1; /* In the meantime, the protocol fell down. */
2017 if (!rte_is_valid(e
))
2020 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
2024 FIB_ITERATE_END(fn
);
2025 p
->feed_ahook
= h
->next
;
2028 mb_free(p
->feed_iterator
);
2029 p
->feed_iterator
= NULL
;
2035 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
2040 * rt_feed_baby_abort - abort protocol feeding
2043 * This function is called by the protocol code when the protocol
2044 * stops or ceases to exist before the last iteration of rt_feed_baby()
2048 rt_feed_baby_abort(struct proto
*p
)
2052 /* Unlink the iterator and exit */
2053 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
2054 p
->feed_ahook
= NULL
;
2059 static inline unsigned
2062 uintptr_t p
= (uintptr_t) ptr
;
2063 return p
^ (p
<< 8) ^ (p
>> 16);
2066 static inline unsigned
2067 hc_hash(ip_addr a
, rtable
*dep
)
2069 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
2073 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
2075 uint k
= he
->hash_key
>> hc
->hash_shift
;
2076 he
->next
= hc
->hash_table
[k
];
2077 hc
->hash_table
[k
] = he
;
2081 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
2083 struct hostentry
**hep
;
2084 uint k
= he
->hash_key
>> hc
->hash_shift
;
2086 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
2090 #define HC_DEF_ORDER 10
2091 #define HC_HI_MARK *4
2092 #define HC_HI_STEP 2
2093 #define HC_HI_ORDER 16 /* Must be at most 16 */
2094 #define HC_LO_MARK /5
2095 #define HC_LO_STEP 2
2096 #define HC_LO_ORDER 10
2099 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
2101 uint hsize
= 1 << order
;
2102 hc
->hash_order
= order
;
2103 hc
->hash_shift
= 16 - order
;
2104 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0U : (hsize HC_HI_MARK
);
2105 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0U : (hsize HC_LO_MARK
);
2107 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
2111 hc_resize(struct hostcache
*hc
, unsigned new_order
)
2113 struct hostentry
**old_table
= hc
->hash_table
;
2114 struct hostentry
*he
, *hen
;
2115 uint old_size
= 1 << hc
->hash_order
;
2118 hc_alloc_table(hc
, new_order
);
2119 for (i
= 0; i
< old_size
; i
++)
2120 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
2128 static struct hostentry
*
2129 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
2131 struct hostentry
*he
= sl_alloc(hc
->slab
);
2140 add_tail(&hc
->hostentries
, &he
->ln
);
2144 if (hc
->hash_items
> hc
->hash_max
)
2145 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
2151 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
2157 sl_free(hc
->slab
, he
);
2160 if (hc
->hash_items
< hc
->hash_min
)
2161 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
2165 rt_init_hostcache(rtable
*tab
)
2167 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
2168 init_list(&hc
->hostentries
);
2171 hc_alloc_table(hc
, HC_DEF_ORDER
);
2172 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
2174 hc
->lp
= lp_new(rt_table_pool
, 1008);
2175 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2177 tab
->hostcache
= hc
;
2181 rt_free_hostcache(rtable
*tab
)
2183 struct hostcache
*hc
= tab
->hostcache
;
2186 WALK_LIST(n
, hc
->hostentries
)
2188 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
2192 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
2197 mb_free(hc
->hash_table
);
2202 rt_notify_hostcache(rtable
*tab
, net
*net
)
2204 struct hostcache
*hc
= tab
->hostcache
;
2206 if (tab
->hcu_scheduled
)
2209 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
2210 rt_schedule_hcu(tab
);
2214 if_local_addr(ip_addr a
, struct iface
*i
)
2218 WALK_LIST(b
, i
->addrs
)
2219 if (ipa_equal(a
, b
->ip
))
2226 rt_get_igp_metric(rte
*rt
)
2228 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
2236 if ((a
->source
== RTS_OSPF
) ||
2237 (a
->source
== RTS_OSPF_IA
) ||
2238 (a
->source
== RTS_OSPF_EXT1
))
2239 return rt
->u
.ospf
.metric1
;
2243 if (a
->source
== RTS_RIP
)
2244 return rt
->u
.rip
.metric
;
2248 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
2251 return IGP_METRIC_UNKNOWN
;
2255 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
2257 rta
*old_src
= he
->src
;
2260 /* Reset the hostentry */
2263 he
->dest
= RTD_UNREACHABLE
;
2266 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
2275 /* Recursive route should not depend on another recursive route */
2276 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
2277 he
->addr
, n
->n
.prefix
, pxlen
);
2281 if (a
->dest
== RTD_DEVICE
)
2283 if (if_local_addr(he
->addr
, a
->iface
))
2285 /* The host address is a local address, this is not valid */
2286 log(L_WARN
"Next hop address %I is a local address of iface %s",
2287 he
->addr
, a
->iface
->name
);
2291 /* The host is directly reachable, use link as a gateway */
2293 he
->dest
= RTD_ROUTER
;
2297 /* The host is reachable through some route entry */
2302 he
->src
= rta_clone(a
);
2303 he
->igp_metric
= rt_get_igp_metric(e
);
2307 /* Add a prefix range to the trie */
2308 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
2311 return old_src
!= he
->src
;
2315 rt_update_hostcache(rtable
*tab
)
2317 struct hostcache
*hc
= tab
->hostcache
;
2318 struct hostentry
*he
;
2321 /* Reset the trie */
2323 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2325 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
2327 he
= SKIP_BACK(struct hostentry
, ln
, n
);
2330 hc_delete_hostentry(hc
, he
);
2334 if (rt_update_hostentry(tab
, he
))
2335 rt_schedule_nhu(he
->tab
);
2338 tab
->hcu_scheduled
= 0;
2341 static struct hostentry
*
2342 rt_get_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2344 struct hostentry
*he
;
2346 if (!tab
->hostcache
)
2347 rt_init_hostcache(tab
);
2349 uint k
= hc_hash(a
, dep
);
2350 struct hostcache
*hc
= tab
->hostcache
;
2351 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2352 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2355 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
2356 rt_update_hostentry(tab
, he
);
2361 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
2363 rta_apply_hostentry(a
, rt_get_hostentry(tab
, *gw
, *ll
, dep
));
2372 rt_format_via(rte
*e
)
2376 /* Max text length w/o IP addr and interface name is 16 */
2377 static byte via
[STD_ADDRESS_P_LENGTH
+sizeof(a
->iface
->name
)+16];
2381 case RTD_ROUTER
: bsprintf(via
, "via %I on %s", a
->gw
, a
->iface
->name
); break;
2382 case RTD_DEVICE
: bsprintf(via
, "dev %s", a
->iface
->name
); break;
2383 case RTD_BLACKHOLE
: bsprintf(via
, "blackhole"); break;
2384 case RTD_UNREACHABLE
: bsprintf(via
, "unreachable"); break;
2385 case RTD_PROHIBIT
: bsprintf(via
, "prohibited"); break;
2386 case RTD_MULTIPATH
: bsprintf(via
, "multipath"); break;
2387 default: bsprintf(via
, "???");
2393 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2395 byte from
[STD_ADDRESS_P_LENGTH
+8];
2396 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2398 int primary
= (e
->net
->routes
== e
);
2399 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2400 void (*get_route_info
)(struct rte
*, byte
*buf
, struct ea_list
*attrs
);
2403 tm_format_datetime(tm
, &config
->tf_route
, e
->lastmod
);
2404 if (ipa_nonzero(a
->from
) && !ipa_equal(a
->from
, a
->gw
))
2405 bsprintf(from
, " from %I", a
->from
);
2409 get_route_info
= a
->src
->proto
->proto
->get_route_info
;
2410 if (get_route_info
|| d
->verbose
)
2412 /* Need to normalize the extended attributes */
2414 t
= ea_append(t
, a
->eattrs
);
2415 tmpa
= alloca(ea_scan(t
));
2420 get_route_info(e
, info
, tmpa
);
2422 bsprintf(info
, " (%d)", e
->pref
);
2423 cli_printf(c
, -1007, "%-18s %s [%s %s%s]%s%s", ia
, rt_format_via(e
), a
->src
->proto
->name
,
2424 tm
, from
, primary
? (sync_error
? " !" : " *") : "", info
);
2425 for (nh
= a
->nexthops
; nh
; nh
= nh
->next
)
2426 cli_printf(c
, -1007, "\tvia %I on %s weight %d", nh
->gw
, nh
->iface
->name
, nh
->weight
+ 1);
2428 rta_show(c
, a
, tmpa
);
2432 rt_show_net(struct cli
*c
, net
*n
, struct rt_show_data
*d
)
2435 byte ia
[STD_ADDRESS_P_LENGTH
+8];
2436 struct ea_list
*tmpa
;
2437 struct announce_hook
*a
= NULL
;
2441 bsprintf(ia
, "%I/%d", n
->n
.prefix
, n
->n
.pxlen
);
2445 if (! d
->export_protocol
->rt_notify
)
2448 a
= proto_find_announce_hook(d
->export_protocol
, d
->table
);
2453 for (e
= n
->routes
; e
; e
= e
->next
)
2455 if (rte_is_filtered(e
) != d
->filtered
)
2459 d
->net_counter
+= first
;
2466 rte_update_lock(); /* We use the update buffer for filtering */
2467 tmpa
= rte_make_tmp_attrs(e
, rte_update_pool
);
2469 /* Special case for merged export */
2470 if ((d
->export_mode
== RSEM_EXPORT
) && (d
->export_protocol
->accept_ra_types
== RA_MERGED
))
2473 e
= rt_export_merged(a
, n
, &rt_free
, &tmpa
, rte_update_pool
, 1);
2477 { e
= ee
; goto skip
; }
2479 else if (d
->export_mode
)
2481 struct proto
*ep
= d
->export_protocol
;
2482 int ic
= ep
->import_control
? ep
->import_control(ep
, &e
, &tmpa
, rte_update_pool
) : 0;
2484 if (ep
->accept_ra_types
== RA_OPTIMAL
|| ep
->accept_ra_types
== RA_MERGED
)
2490 if (d
->export_mode
> RSEM_PREEXPORT
)
2493 * FIXME - This shows what should be exported according to current
2494 * filters, but not what was really exported. 'configure soft'
2495 * command may change the export filter and do not update routes.
2497 int do_export
= (ic
> 0) ||
2498 (f_run(a
->out_filter
, &e
, &tmpa
, rte_update_pool
,
2499 FF_FORCE_TMPATTR
| FF_SILENT
) <= F_ACCEPT
);
2501 if (do_export
!= (d
->export_mode
== RSEM_EXPORT
))
2504 if ((d
->export_mode
== RSEM_EXPORT
) && (ep
->accept_ra_types
== RA_ACCEPTED
))
2509 if (d
->show_protocol
&& (d
->show_protocol
!= e
->attrs
->src
->proto
))
2512 if (f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
)
2517 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2526 rte_update_unlock();
2528 if (d
->primary_only
)
2534 rt_show_cont(struct cli
*c
)
2536 struct rt_show_data
*d
= c
->rover
;
2542 struct fib
*fib
= &d
->table
->fib
;
2543 struct fib_iterator
*it
= &d
->fit
;
2545 FIB_ITERATE_START(fib
, it
, f
)
2548 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2550 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2553 if (d
->export_protocol
&& (d
->export_protocol
->export_state
== ES_DOWN
))
2555 cli_printf(c
, 8005, "Protocol is down");
2560 FIB_ITERATE_PUT(it
, f
);
2563 rt_show_net(c
, n
, d
);
2567 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2569 cli_printf(c
, 0, "");
2571 c
->cont
= c
->cleanup
= NULL
;
2575 rt_show_cleanup(struct cli
*c
)
2577 struct rt_show_data
*d
= c
->rover
;
2579 /* Unlink the iterator */
2580 fit_get(&d
->table
->fib
, &d
->fit
);
2584 rt_show(struct rt_show_data
*d
)
2588 /* Default is either a master table or a table related to a respective protocol */
2589 if (!d
->table
&& d
->export_protocol
) d
->table
= d
->export_protocol
->table
;
2590 if (!d
->table
&& d
->show_protocol
) d
->table
= d
->show_protocol
->table
;
2591 if (!d
->table
) d
->table
= config
->master_rtc
->table
;
2593 /* Filtered routes are neither exported nor have sensible ordering */
2594 if (d
->filtered
&& (d
->export_mode
|| d
->primary_only
))
2597 if (d
->pxlen
== 256)
2599 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2600 this_cli
->cont
= rt_show_cont
;
2601 this_cli
->cleanup
= rt_show_cleanup
;
2602 this_cli
->rover
= d
;
2607 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2609 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2612 rt_show_net(this_cli
, n
, d
);
2617 cli_msg(8001, "Network not in table");
2622 * Documentation for functions declared inline in route.h
2627 * net_find - find a network entry
2628 * @tab: a routing table
2629 * @addr: address of the network
2630 * @len: length of the network prefix
2632 * net_find() looks up the given network in routing table @tab and
2633 * returns a pointer to its &net entry or %NULL if no such network
2636 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2640 * net_get - obtain a network entry
2641 * @tab: a routing table
2642 * @addr: address of the network
2643 * @len: length of the network prefix
2645 * net_get() looks up the given network in routing table @tab and
2646 * returns a pointer to its &net entry. If no such entry exists, it's
2649 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2653 * rte_cow - copy a route for writing
2654 * @r: a route entry to be copied
2656 * rte_cow() takes a &rte and prepares it for modification. The exact action
2657 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2658 * just returned unchanged, else a new temporary entry with the same contents
2661 * The primary use of this function is inside the filter machinery -- when
2662 * a filter wants to modify &rte contents (to change the preference or to
2663 * attach another set of attributes), it must ensure that the &rte is not
2664 * shared with anyone else (and especially that it isn't stored in any routing
2667 * Result: a pointer to the new writable &rte.
2669 static inline rte
* rte_cow(rte
*r
)