]>
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 static inline struct ea_list
*
64 make_tmp_attrs(struct rte
*rt
, struct linpool
*pool
)
66 struct ea_list
*(*mta
)(struct rte
*rt
, struct linpool
*pool
);
67 mta
= rt
->attrs
->src
->proto
->make_tmp_attrs
;
68 return mta
? mta(rt
, rte_update_pool
) : NULL
;
71 /* Like fib_route(), but skips empty net entries */
73 net_route(rtable
*tab
, ip_addr a
, int len
)
80 a0
= ipa_and(a
, ipa_mkmask(len
));
81 n
= fib_find(&tab
->fib
, &a0
, len
);
82 if (n
&& rte_is_valid(n
->routes
))
90 rte_init(struct fib_node
*N
)
99 * rte_find - find a route
103 * The rte_find() function returns a route for destination @net
104 * which is from route source @src.
107 rte_find(net
*net
, struct rte_src
*src
)
109 rte
*e
= net
->routes
;
111 while (e
&& e
->attrs
->src
!= src
)
117 * rte_get_temp - get a temporary &rte
118 * @a: attributes to assign to the new route (a &rta; in case it's
119 * un-cached, rte_update() will create a cached copy automatically)
121 * Create a temporary &rte and bind it with the attributes @a.
122 * Also set route preference to the default preference set for
128 rte
*e
= sl_alloc(rte_slab
);
132 e
->pref
= a
->src
->proto
->preference
;
139 rte
*e
= sl_alloc(rte_slab
);
141 memcpy(e
, r
, sizeof(rte
));
142 e
->attrs
= rta_clone(r
->attrs
);
148 * rte_cow_rta - get a private writable copy of &rte with writable &rta
149 * @r: a route entry to be copied
150 * @lp: a linpool from which to allocate &rta
152 * rte_cow_rta() takes a &rte and prepares it and associated &rta for
153 * modification. There are three possibilities: First, both &rte and &rta are
154 * private copies, in that case they are returned unchanged. Second, &rte is
155 * private copy, but &rta is cached, in that case &rta is duplicated using
156 * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
157 * both structures are duplicated by rte_do_cow() and rta_do_cow().
159 * Note that in the second case, cached &rta loses one reference, while private
160 * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
161 * nexthops, ...) with it. To work properly, original shared &rta should have
162 * another reference during the life of created private copy.
164 * Result: a pointer to the new writable &rte with writable &rta.
167 rte_cow_rta(rte
*r
, linpool
*lp
)
169 if (!rta_is_cached(r
->attrs
))
173 rta
*a
= rta_do_cow(r
->attrs
, lp
);
179 static int /* Actually better or at least as good as */
180 rte_better(rte
*new, rte
*old
)
182 int (*better
)(rte
*, rte
*);
184 if (!rte_is_valid(old
))
186 if (!rte_is_valid(new))
189 if (new->pref
> old
->pref
)
191 if (new->pref
< old
->pref
)
193 if (new->attrs
->src
->proto
->proto
!= old
->attrs
->src
->proto
->proto
)
196 * If the user has configured protocol preferences, so that two different protocols
197 * have the same preference, try to break the tie by comparing addresses. Not too
198 * useful, but keeps the ordering of routes unambiguous.
200 return new->attrs
->src
->proto
->proto
> old
->attrs
->src
->proto
->proto
;
202 if (better
= new->attrs
->src
->proto
->rte_better
)
203 return better(new, old
);
208 rte_mergable(rte
*pri
, rte
*sec
)
210 int (*mergable
)(rte
*, rte
*);
212 if (!rte_is_valid(pri
) || !rte_is_valid(sec
))
215 if (pri
->pref
!= sec
->pref
)
218 if (pri
->attrs
->src
->proto
->proto
!= sec
->attrs
->src
->proto
->proto
)
221 if (mergable
= pri
->attrs
->src
->proto
->rte_mergable
)
222 return mergable(pri
, sec
);
228 rte_trace(struct proto
*p
, rte
*e
, int dir
, char *msg
)
230 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
));
234 rte_trace_in(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
237 rte_trace(p
, e
, '>', msg
);
241 rte_trace_out(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
244 rte_trace(p
, e
, '<', msg
);
248 export_filter(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
250 struct proto
*p
= ah
->proto
;
251 struct filter
*filter
= ah
->out_filter
;
252 struct proto_stats
*stats
= ah
->stats
;
253 ea_list
*tmpb
= NULL
;
263 *tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
265 v
= p
->import_control
? p
->import_control(p
, &rt
, tmpa
, rte_update_pool
) : 0;
271 stats
->exp_updates_rejected
++;
273 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
279 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
283 v
= filter
&& ((filter
== FILTER_REJECT
) ||
284 (f_run(filter
, &rt
, tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
));
290 stats
->exp_updates_filtered
++;
291 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
301 /* Discard temporary rte */
308 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
310 struct proto
*p
= ah
->proto
;
311 struct proto_stats
*stats
= ah
->stats
;
315 * First, apply export limit.
317 * Export route limits has several problems. Because exp_routes
318 * counter is reset before refeed, we don't really know whether
319 * limit is breached and whether the update is new or not. Therefore
320 * the number of really exported routes may exceed the limit
321 * temporarily (routes exported before and new routes in refeed).
323 * Minor advantage is that if the limit is decreased and refeed is
324 * requested, the number of exported routes really decrease.
326 * Second problem is that with export limits, we don't know whether
327 * old was really exported (it might be blocked by limit). When a
328 * withdraw is exported, we announce it even when the previous
329 * update was blocked. This is not a big issue, but the same problem
330 * is in updating exp_routes counter. Therefore, to be consistent in
331 * increases and decreases of exp_routes, we count exported routes
332 * regardless of blocking by limits.
334 * Similar problem is in handling updates - when a new route is
335 * received and blocking is active, the route would be blocked, but
336 * when an update for the route will be received later, the update
337 * would be propagated (as old != NULL). Therefore, we have to block
338 * also non-new updates (contrary to import blocking).
341 struct proto_limit
*l
= ah
->out_limit
;
344 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
345 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
347 if (l
->state
== PLS_BLOCKED
)
349 stats
->exp_routes
++; /* see note above */
350 stats
->exp_updates_rejected
++;
351 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
361 stats
->exp_updates_accepted
++;
363 stats
->exp_withdraws_accepted
++;
365 /* Hack: We do not decrease exp_routes during refeed, we instead
366 reset exp_routes at the start of refeed. */
372 if (p
->debug
& D_ROUTES
)
375 rte_trace_out(D_ROUTES
, p
, new, "replaced");
377 rte_trace_out(D_ROUTES
, p
, new, "added");
379 rte_trace_out(D_ROUTES
, p
, old
, "removed");
382 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
388 t
->next
= new->attrs
->eattrs
;
389 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
393 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
397 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new0
, rte
*old0
, int refeed
)
399 struct proto
*p
= ah
->proto
;
400 struct proto_stats
*stats
= ah
->stats
;
404 rte
*new_free
= NULL
;
405 rte
*old_free
= NULL
;
406 ea_list
*tmpa
= NULL
;
409 stats
->exp_updates_received
++;
411 stats
->exp_withdraws_received
++;
414 * This is a tricky part - we don't know whether route 'old' was
415 * exported to protocol 'p' or was filtered by the export filter.
416 * We try to run the export filter to know this to have a correct
417 * value in 'old' argument of rte_update (and proper filter value)
419 * FIXME - this is broken because 'configure soft' may change
420 * filters but keep routes. Refeed is expected to be called after
421 * change of the filters and with old == new, therefore we do not
422 * even try to run the filter on an old route, This may lead to
423 * 'spurious withdraws' but ensure that there are no 'missing
426 * This is not completely safe as there is a window between
427 * reconfiguration and the end of refeed - if a newly filtered
428 * route disappears during this period, proper withdraw is not
429 * sent (because old would be also filtered) and the route is
430 * not refeeded (because it disappeared before that).
434 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
437 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
442 * As mentioned above, 'old' value may be incorrect in some race conditions.
443 * We generally ignore it with the exception of withdraw to pipe protocol.
444 * In that case we rather propagate unfiltered withdraws regardless of
445 * export filters to ensure that when a protocol is flushed, its routes are
446 * removed from all tables. Possible spurious unfiltered withdraws are not
447 * problem here as they are ignored if there is no corresponding route at
448 * the other end of the pipe. We directly call rt_notify() hook instead of
449 * do_rt_notify() to avoid logging and stat counters.
453 if ((p
->proto
== &proto_pipe
) && !new0
&& (p
!= old0
->sender
->proto
))
454 p
->rt_notify(p
, ah
->table
, net
, NULL
, old0
, NULL
);
460 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
462 /* Discard temporary rte's */
470 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
, int feed
)
472 // struct proto *p = ah->proto;
473 struct proto_stats
*stats
= ah
->stats
;
476 rte
*new_best
= NULL
;
477 rte
*old_best
= NULL
;
478 rte
*new_free
= NULL
;
479 rte
*old_free
= NULL
;
480 ea_list
*tmpa
= NULL
;
482 /* Used to track whether we met old_changed position. If before_old is NULL
483 old_changed was the first and we met it implicitly before current best route. */
484 int old_meet
= old_changed
&& !before_old
;
486 /* Note that before_old is either NULL or valid (not rejected) route.
487 If old_changed is valid, before_old have to be too. If old changed route
488 was not valid, caller must use NULL for both old_changed and before_old. */
491 stats
->exp_updates_received
++;
493 stats
->exp_withdraws_received
++;
495 /* First, find the new_best route - first accepted by filters */
496 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
498 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
501 /* Note if we walked around the position of old_changed route */
507 * Second, handle the feed case. That means we do not care for
508 * old_best. It is NULL for feed, and the new_best for refeed.
509 * For refeed, there is a hack similar to one in rt_notify_basic()
510 * to ensure withdraws in case of changed filters
514 if (feed
== 2) /* refeed */
515 old_best
= new_best
? new_best
:
516 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
520 if (!new_best
&& !old_best
)
527 * Now, we find the old_best route. Generally, it is the same as the
528 * new_best, unless new_best is the same as new_changed or
529 * old_changed is accepted before new_best.
531 * There are four cases:
533 * - We would find and accept old_changed before new_best, therefore
534 * old_changed is old_best. In remaining cases we suppose this
537 * - We found no new_best, therefore there is also no old_best and
538 * we ignore this withdraw.
540 * - We found new_best different than new_changed, therefore
541 * old_best is the same as new_best and we ignore this update.
543 * - We found new_best the same as new_changed, therefore it cannot
544 * be old_best and we have to continue search for old_best.
549 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
556 /* Third case, we use r instead of new_best, because export_filter() could change it */
557 if (r
!= new_changed
)
565 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
567 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
571 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
575 /* Implicitly, old_best is NULL and new_best is non-NULL */
578 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
580 /* Discard temporary rte's */
589 mpnh_merge_rta(struct mpnh
*nhs
, rta
*a
, int max
)
591 struct mpnh nh
= { .gw
= a
->gw
, .iface
= a
->iface
};
592 struct mpnh
*nh2
= (a
->dest
== RTD_MULTIPATH
) ? a
->nexthops
: &nh
;
593 return mpnh_merge(nhs
, nh2
, 1, 0, max
, rte_update_pool
);
597 rt_export_merged(struct announce_hook
*ah
, net
*net
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
599 // struct proto *p = ah->proto;
600 struct mpnh
*nhs
= NULL
;
601 rte
*best0
, *best
, *rt0
, *rt
, *tmp
;
606 if (!rte_is_valid(best0
))
609 best
= export_filter(ah
, best0
, rt_free
, tmpa
, silent
);
611 if (!best
|| !rte_is_reachable(best
))
614 for (rt0
= best0
->next
; rt0
; rt0
= rt0
->next
)
616 if (!rte_mergable(best0
, rt0
))
619 rt
= export_filter(ah
, rt0
, &tmp
, NULL
, 1);
624 if (rte_is_reachable(rt
))
625 nhs
= mpnh_merge_rta(nhs
, rt
->attrs
, ah
->proto
->merge_limit
);
633 nhs
= mpnh_merge_rta(nhs
, best
->attrs
, ah
->proto
->merge_limit
);
637 best
= rte_cow_rta(best
, rte_update_pool
);
638 best
->attrs
->dest
= RTD_MULTIPATH
;
639 best
->attrs
->nexthops
= nhs
;
651 rt_notify_merged(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
,
652 rte
*new_best
, rte
*old_best
, int refeed
)
654 // struct proto *p = ah->proto;
656 rte
*new_best_free
= NULL
;
657 rte
*old_best_free
= NULL
;
658 rte
*new_changed_free
= NULL
;
659 rte
*old_changed_free
= NULL
;
660 ea_list
*tmpa
= NULL
;
662 /* We assume that all rte arguments are either NULL or rte_is_valid() */
664 /* This check should be done by the caller */
665 if (!new_best
&& !old_best
)
668 /* Check whether the change is relevant to the merged route */
669 if ((new_best
== old_best
) && !refeed
)
671 new_changed
= rte_mergable(new_best
, new_changed
) ?
672 export_filter(ah
, new_changed
, &new_changed_free
, NULL
, 1) : NULL
;
674 old_changed
= rte_mergable(old_best
, old_changed
) ?
675 export_filter(ah
, old_changed
, &old_changed_free
, NULL
, 1) : NULL
;
677 if (!new_changed
&& !old_changed
)
682 ah
->stats
->exp_updates_received
++;
684 ah
->stats
->exp_withdraws_received
++;
686 /* Prepare new merged route */
688 new_best
= rt_export_merged(ah
, net
, &new_best_free
, &tmpa
, 0);
690 /* Prepare old merged route (without proper merged next hops) */
691 /* There are some issues with running filter on old route - see rt_notify_basic() */
692 if (old_best
&& !refeed
)
693 old_best
= export_filter(ah
, old_best
, &old_best_free
, NULL
, 1);
695 if (new_best
|| old_best
)
696 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, refeed
);
698 /* Discard temporary rte's */
700 rte_free(new_best_free
);
702 rte_free(old_best_free
);
703 if (new_changed_free
)
704 rte_free(new_changed_free
);
705 if (old_changed_free
)
706 rte_free(old_changed_free
);
711 * rte_announce - announce a routing table change
712 * @tab: table the route has been added to
713 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
714 * @net: network in question
715 * @new: the new route to be announced
716 * @old: the previous route for the same network
717 * @new_best: the new best route for the same network
718 * @old_best: the previous best route for the same network
719 * @before_old: The previous route before @old for the same network.
720 * If @before_old is NULL @old was the first.
722 * This function gets a routing table update and announces it
723 * to all protocols that acccepts given type of route announcement
724 * and are connected to the same table by their announcement hooks.
726 * Route announcement of type %RA_OPTIMAL si generated when optimal
727 * route (in routing table @tab) changes. In that case @old stores the
730 * Route announcement of type %RA_ANY si generated when any route (in
731 * routing table @tab) changes In that case @old stores the old route
732 * from the same protocol.
734 * For each appropriate protocol, we first call its import_control()
735 * hook which performs basic checks on the route (each protocol has a
736 * right to veto or force accept of the route before any filter is
737 * asked) and adds default values of attributes specific to the new
738 * protocol (metrics, tags etc.). Then it consults the protocol's
739 * export filter and if it accepts the route, the rt_notify() hook of
740 * the protocol gets called.
743 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
744 rte
*new_best
, rte
*old_best
, rte
*before_old
)
746 if (!rte_is_valid(new))
749 if (!rte_is_valid(old
))
750 old
= before_old
= NULL
;
752 if (!rte_is_valid(new_best
))
755 if (!rte_is_valid(old_best
))
761 if (type
== RA_OPTIMAL
)
764 new->attrs
->src
->proto
->stats
.pref_routes
++;
766 old
->attrs
->src
->proto
->stats
.pref_routes
--;
769 rt_notify_hostcache(tab
, net
);
772 struct announce_hook
*a
;
773 WALK_LIST(a
, tab
->hooks
)
775 ASSERT(a
->proto
->export_state
!= ES_DOWN
);
776 if (a
->proto
->accept_ra_types
== type
)
777 if (type
== RA_ACCEPTED
)
778 rt_notify_accepted(a
, net
, new, old
, before_old
, 0);
779 else if (type
== RA_MERGED
)
780 rt_notify_merged(a
, net
, new, old
, new_best
, old_best
, 0);
782 rt_notify_basic(a
, net
, new, old
, 0);
792 if ((n
->n
.pxlen
> BITS_PER_IP_ADDRESS
) || !ip_is_prefix(n
->n
.prefix
,n
->n
.pxlen
))
794 log(L_WARN
"Ignoring bogus prefix %I/%d received via %s",
795 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
799 c
= ipa_classify_net(n
->n
.prefix
);
800 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
802 log(L_WARN
"Ignoring bogus route %I/%d received via %s",
803 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
807 if ((e
->attrs
->dest
== RTD_MULTIPATH
) && !mpnh_is_sorted(e
->attrs
->nexthops
))
809 log(L_WARN
"Ignoring unsorted multipath route %I/%d received via %s",
810 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
818 * rte_free - delete a &rte
819 * @e: &rte to be deleted
821 * rte_free() deletes the given &rte from the routing table it's linked to.
826 if (rta_is_cached(e
->attrs
))
828 sl_free(rte_slab
, e
);
832 rte_free_quick(rte
*e
)
835 sl_free(rte_slab
, e
);
839 rte_same(rte
*x
, rte
*y
)
842 x
->attrs
== y
->attrs
&&
843 x
->flags
== y
->flags
&&
844 x
->pflags
== y
->pflags
&&
845 x
->pref
== y
->pref
&&
846 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
849 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
852 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
854 struct proto
*p
= ah
->proto
;
855 struct rtable
*table
= ah
->table
;
856 struct proto_stats
*stats
= ah
->stats
;
857 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
858 rte
*before_old
= NULL
;
859 rte
*old_best
= net
->routes
;
863 k
= &net
->routes
; /* Find and remove original route from the same protocol */
866 if (old
->attrs
->src
== src
)
868 /* If there is the same route in the routing table but from
869 * a different sender, then there are two paths from the
870 * source protocol to this routing table through transparent
871 * pipes, which is not allowed.
873 * We log that and ignore the route. If it is withdraw, we
874 * ignore it completely (there might be 'spurious withdraws',
875 * see FIXME in do_rte_announce())
877 if (old
->sender
->proto
!= p
)
881 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %I/%d to table %s",
882 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
888 if (new && rte_same(old
, new))
890 /* No changes, ignore the new route */
892 if (!rte_is_filtered(new))
894 stats
->imp_updates_ignored
++;
895 rte_trace_in(D_ROUTES
, p
, new, "ignored");
913 stats
->imp_withdraws_ignored
++;
917 int new_ok
= rte_is_ok(new);
918 int old_ok
= rte_is_ok(old
);
920 struct proto_limit
*l
= ah
->rx_limit
;
921 if (l
&& !old
&& new)
923 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
925 if (all_routes
>= l
->limit
)
926 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
928 if (l
->state
== PLS_BLOCKED
)
930 /* In receive limit the situation is simple, old is NULL so
931 we just free new and exit like nothing happened */
933 stats
->imp_updates_ignored
++;
934 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
941 if (l
&& !old_ok
&& new_ok
)
943 if (stats
->imp_routes
>= l
->limit
)
944 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
946 if (l
->state
== PLS_BLOCKED
)
948 /* In import limit the situation is more complicated. We
949 shouldn't just drop the route, we should handle it like
950 it was filtered. We also have to continue the route
951 processing if old or new is non-NULL, but we should exit
952 if both are NULL as this case is probably assumed to be
955 stats
->imp_updates_ignored
++;
956 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
958 if (ah
->in_keep_filtered
)
959 new->flags
|= REF_FILTERED
;
961 { rte_free_quick(new); new = NULL
; }
963 /* Note that old && !new could be possible when
964 ah->in_keep_filtered changed in the recent past. */
975 stats
->imp_updates_accepted
++;
977 stats
->imp_withdraws_accepted
++;
979 stats
->imp_withdraws_ignored
++;
984 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
986 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
988 if (table
->config
->sorted
)
990 /* If routes are sorted, just insert new route to appropriate position */
993 if (before_old
&& !rte_better(new, before_old
))
994 k
= &before_old
->next
;
998 for (; *k
; k
=&(*k
)->next
)
999 if (rte_better(new, *k
))
1008 /* If routes are not sorted, find the best route and move it on
1009 the first position. There are several optimized cases. */
1011 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
1012 goto do_recalculate
;
1014 if (new && rte_better(new, old_best
))
1016 /* The first case - the new route is cleary optimal,
1017 we link it at the first position */
1019 new->next
= net
->routes
;
1022 else if (old
== old_best
)
1024 /* The second case - the old best route disappeared, we add the
1025 new route (if we have any) to the list (we don't care about
1026 position) and then we elect the new optimal route and relink
1027 that route at the first position and announce it. New optimal
1028 route might be NULL if there is no more routes */
1031 /* Add the new route to the list */
1034 new->next
= net
->routes
;
1038 /* Find a new optimal route (if there is any) */
1041 rte
**bp
= &net
->routes
;
1042 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
1043 if (rte_better(*k
, *bp
))
1049 best
->next
= net
->routes
;
1055 /* The third case - the new route is not better than the old
1056 best route (therefore old_best != NULL) and the old best
1057 route was not removed (therefore old_best == net->routes).
1058 We just link the new route after the old best route. */
1060 ASSERT(net
->routes
!= NULL
);
1061 new->next
= net
->routes
->next
;
1062 net
->routes
->next
= new;
1064 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1070 /* Log the route change */
1071 if (p
->debug
& D_ROUTES
)
1074 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
1077 if (old
!= old_best
)
1078 rte_trace(p
, old
, '>', "removed");
1079 else if (rte_is_ok(net
->routes
))
1080 rte_trace(p
, old
, '>', "removed [replaced]");
1082 rte_trace(p
, old
, '>', "removed [sole]");
1086 /* Propagate the route change */
1087 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, NULL
, NULL
);
1088 if (net
->routes
!= old_best
)
1089 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, NULL
, NULL
);
1090 if (table
->config
->sorted
)
1091 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, NULL
, NULL
, before_old
);
1092 rte_announce(table
, RA_MERGED
, net
, new, old
, net
->routes
, old_best
, NULL
);
1095 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
1096 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
1097 rt_schedule_gc(table
);
1099 if (old_ok
&& p
->rte_remove
)
1100 p
->rte_remove(net
, old
);
1101 if (new_ok
&& p
->rte_insert
)
1102 p
->rte_insert(net
, new);
1105 rte_free_quick(old
);
1108 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
1111 rte_update_lock(void)
1113 rte_update_nest_cnt
++;
1117 rte_update_unlock(void)
1119 if (!--rte_update_nest_cnt
)
1120 lp_flush(rte_update_pool
);
1124 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
1126 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
1128 *dummy
= net
->routes
;
1129 net
->routes
= (*dummy
)->next
;
1134 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
1138 (*dummy
)->next
= net
->routes
;
1139 net
->routes
= *dummy
;
1144 * rte_update - enter a new update to a routing table
1145 * @table: table to be updated
1146 * @ah: pointer to table announce hook
1147 * @net: network node
1148 * @p: protocol submitting the update
1149 * @src: protocol originating the update
1150 * @new: a &rte representing the new route or %NULL for route removal.
1152 * This function is called by the routing protocols whenever they discover
1153 * a new route or wish to update/remove an existing route. The right announcement
1154 * sequence is to build route attributes first (either un-cached with @aflags set
1155 * to zero or a cached one using rta_lookup(); in this case please note that
1156 * you need to increase the use count of the attributes yourself by calling
1157 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1158 * the appropriate data and finally submit the new &rte by calling rte_update().
1160 * @src specifies the protocol that originally created the route and the meaning
1161 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1162 * same value as @new->attrs->proto. @p specifies the protocol that called
1163 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1164 * stores @p in @new->sender;
1166 * When rte_update() gets any route, it automatically validates it (checks,
1167 * whether the network and next hop address are valid IP addresses and also
1168 * whether a normal routing protocol doesn't try to smuggle a host or link
1169 * scope route to the table), converts all protocol dependent attributes stored
1170 * in the &rte to temporary extended attributes, consults import filters of the
1171 * protocol to see if the route should be accepted and/or its attributes modified,
1172 * stores the temporary attributes back to the &rte.
1174 * Now, having a "public" version of the route, we
1175 * automatically find any old route defined by the protocol @src
1176 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1177 * recalculate the optimal route for this destination and finally broadcast
1178 * the change (if any) to all routing protocols by calling rte_announce().
1180 * All memory used for attribute lists and other temporary allocations is taken
1181 * from a special linear pool @rte_update_pool and freed when rte_update()
1186 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
1188 struct proto
*p
= ah
->proto
;
1189 struct proto_stats
*stats
= ah
->stats
;
1190 struct filter
*filter
= ah
->in_filter
;
1191 ea_list
*tmpa
= NULL
;
1199 stats
->imp_updates_received
++;
1200 if (!rte_validate(new))
1202 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1203 stats
->imp_updates_invalid
++;
1207 if (filter
== FILTER_REJECT
)
1209 stats
->imp_updates_filtered
++;
1210 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1212 if (! ah
->in_keep_filtered
)
1215 /* new is a private copy, i could modify it */
1216 new->flags
|= REF_FILTERED
;
1220 tmpa
= make_tmp_attrs(new, rte_update_pool
);
1221 if (filter
&& (filter
!= FILTER_REJECT
))
1223 ea_list
*old_tmpa
= tmpa
;
1224 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
1227 stats
->imp_updates_filtered
++;
1228 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1230 if (! ah
->in_keep_filtered
)
1233 new->flags
|= REF_FILTERED
;
1235 if (tmpa
!= old_tmpa
&& src
->proto
->store_tmp_attrs
)
1236 src
->proto
->store_tmp_attrs(new, tmpa
);
1239 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1240 new->attrs
= rta_lookup(new->attrs
);
1241 new->flags
|= REF_COW
;
1245 stats
->imp_withdraws_received
++;
1249 stats
->imp_withdraws_ignored
++;
1250 rte_update_unlock();
1256 rte_hide_dummy_routes(net
, &dummy
);
1257 rte_recalculate(ah
, net
, new, src
);
1258 rte_unhide_dummy_routes(net
, &dummy
);
1259 rte_update_unlock();
1268 /* Independent call to rte_announce(), used from next hop
1269 recalculation, outside of rte_update(). new must be non-NULL */
1271 rte_announce_i(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
1272 rte
*new_best
, rte
*old_best
)
1275 rte_announce(tab
, type
, net
, new, old
, new_best
, old_best
, NULL
);
1276 rte_update_unlock();
1280 rte_discard(rtable
*t
, rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1283 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1284 rte_update_unlock();
1287 /* Check rtable for best route to given net whether it would be exported do p */
1289 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1291 net
*n
= net_find(t
, prefix
, pxlen
);
1292 rte
*rt
= n
? n
->routes
: NULL
;
1294 if (!rte_is_valid(rt
))
1299 /* Rest is stripped down export_filter() */
1300 ea_list
*tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
1301 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1302 if (v
== RIC_PROCESS
)
1303 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= 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
);
1603 rte_discard(tab
, e
);
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
, 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 unsigned hsize
= 1 << order
;
2102 hc
->hash_order
= order
;
2103 hc
->hash_shift
= 16 - order
;
2104 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0 : (hsize HC_HI_MARK
);
2105 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0 : (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 unsigned old_size
= 1 << hc
->hash_order
;
2114 struct hostentry
**old_table
= hc
->hash_table
;
2115 struct hostentry
*he
, *hen
;
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
= 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
, 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
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
2500 if (do_export
!= (d
->export_mode
== RSEM_EXPORT
))
2503 if ((d
->export_mode
== RSEM_EXPORT
) && (ep
->accept_ra_types
== RA_ACCEPTED
))
2508 if (d
->show_protocol
&& (d
->show_protocol
!= e
->attrs
->src
->proto
))
2511 if (f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
)
2516 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2525 rte_update_unlock();
2527 if (d
->primary_only
)
2533 rt_show_cont(struct cli
*c
)
2535 struct rt_show_data
*d
= c
->rover
;
2541 struct fib
*fib
= &d
->table
->fib
;
2542 struct fib_iterator
*it
= &d
->fit
;
2544 FIB_ITERATE_START(fib
, it
, f
)
2547 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2549 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2552 if (d
->export_protocol
&& (d
->export_protocol
->export_state
== ES_DOWN
))
2554 cli_printf(c
, 8005, "Protocol is down");
2559 FIB_ITERATE_PUT(it
, f
);
2562 rt_show_net(c
, n
, d
);
2566 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2568 cli_printf(c
, 0, "");
2570 c
->cont
= c
->cleanup
= NULL
;
2574 rt_show_cleanup(struct cli
*c
)
2576 struct rt_show_data
*d
= c
->rover
;
2578 /* Unlink the iterator */
2579 fit_get(&d
->table
->fib
, &d
->fit
);
2583 rt_show(struct rt_show_data
*d
)
2587 /* Default is either a master table or a table related to a respective protocol */
2588 if (!d
->table
&& d
->export_protocol
) d
->table
= d
->export_protocol
->table
;
2589 if (!d
->table
&& d
->show_protocol
) d
->table
= d
->show_protocol
->table
;
2590 if (!d
->table
) d
->table
= config
->master_rtc
->table
;
2592 /* Filtered routes are neither exported nor have sensible ordering */
2593 if (d
->filtered
&& (d
->export_mode
|| d
->primary_only
))
2596 if (d
->pxlen
== 256)
2598 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2599 this_cli
->cont
= rt_show_cont
;
2600 this_cli
->cleanup
= rt_show_cleanup
;
2601 this_cli
->rover
= d
;
2606 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2608 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2611 rt_show_net(this_cli
, n
, d
);
2616 cli_msg(8001, "Network not in table");
2621 * Documentation for functions declared inline in route.h
2626 * net_find - find a network entry
2627 * @tab: a routing table
2628 * @addr: address of the network
2629 * @len: length of the network prefix
2631 * net_find() looks up the given network in routing table @tab and
2632 * returns a pointer to its &net entry or %NULL if no such network
2635 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2639 * net_get - obtain a network entry
2640 * @tab: a routing table
2641 * @addr: address of the network
2642 * @len: length of the network prefix
2644 * net_get() looks up the given network in routing table @tab and
2645 * returns a pointer to its &net entry. If no such entry exists, it's
2648 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2652 * rte_cow - copy a route for writing
2653 * @r: a route entry to be copied
2655 * rte_cow() takes a &rte and prepares it for modification. The exact action
2656 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2657 * just returned unchanged, else a new temporary entry with the same contents
2660 * The primary use of this function is inside the filter machinery -- when
2661 * a filter wants to modify &rte contents (to change the preference or to
2662 * attach another set of attributes), it must ensure that the &rte is not
2663 * shared with anyone else (and especially that it isn't stored in any routing
2666 * Result: a pointer to the new writable &rte.
2668 static inline rte
* rte_cow(rte
*r
)