]>
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 void rt_format_via(rte
*e
, byte
*via
);
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 byte via
[STD_ADDRESS_P_LENGTH
+32];
232 rt_format_via(e
, via
);
233 log(L_TRACE
"%s %c %s %I/%d %s", p
->name
, dir
, msg
, e
->net
->n
.prefix
, e
->net
->n
.pxlen
, via
);
237 rte_trace_in(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
240 rte_trace(p
, e
, '>', msg
);
244 rte_trace_out(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
247 rte_trace(p
, e
, '<', msg
);
251 export_filter(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
253 struct proto
*p
= ah
->proto
;
254 struct filter
*filter
= ah
->out_filter
;
255 struct proto_stats
*stats
= ah
->stats
;
256 ea_list
*tmpb
= NULL
;
266 *tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
268 v
= p
->import_control
? p
->import_control(p
, &rt
, tmpa
, rte_update_pool
) : 0;
274 stats
->exp_updates_rejected
++;
276 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
282 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
286 v
= filter
&& ((filter
== FILTER_REJECT
) ||
287 (f_run(filter
, &rt
, tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
));
293 stats
->exp_updates_filtered
++;
294 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
304 /* Discard temporary rte */
311 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
313 struct proto
*p
= ah
->proto
;
314 struct proto_stats
*stats
= ah
->stats
;
318 * First, apply export limit.
320 * Export route limits has several problems. Because exp_routes
321 * counter is reset before refeed, we don't really know whether
322 * limit is breached and whether the update is new or not. Therefore
323 * the number of really exported routes may exceed the limit
324 * temporarily (routes exported before and new routes in refeed).
326 * Minor advantage is that if the limit is decreased and refeed is
327 * requested, the number of exported routes really decrease.
329 * Second problem is that with export limits, we don't know whether
330 * old was really exported (it might be blocked by limit). When a
331 * withdraw is exported, we announce it even when the previous
332 * update was blocked. This is not a big issue, but the same problem
333 * is in updating exp_routes counter. Therefore, to be consistent in
334 * increases and decreases of exp_routes, we count exported routes
335 * regardless of blocking by limits.
337 * Similar problem is in handling updates - when a new route is
338 * received and blocking is active, the route would be blocked, but
339 * when an update for the route will be received later, the update
340 * would be propagated (as old != NULL). Therefore, we have to block
341 * also non-new updates (contrary to import blocking).
344 struct proto_limit
*l
= ah
->out_limit
;
347 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
348 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
350 if (l
->state
== PLS_BLOCKED
)
352 stats
->exp_routes
++; /* see note above */
353 stats
->exp_updates_rejected
++;
354 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
364 stats
->exp_updates_accepted
++;
366 stats
->exp_withdraws_accepted
++;
368 /* Hack: We do not decrease exp_routes during refeed, we instead
369 reset exp_routes at the start of refeed. */
375 if (p
->debug
& D_ROUTES
)
378 rte_trace_out(D_ROUTES
, p
, new, "replaced");
380 rte_trace_out(D_ROUTES
, p
, new, "added");
382 rte_trace_out(D_ROUTES
, p
, old
, "removed");
385 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
391 t
->next
= new->attrs
->eattrs
;
392 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
396 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
400 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new0
, rte
*old0
, int refeed
)
402 struct proto
*p
= ah
->proto
;
403 struct proto_stats
*stats
= ah
->stats
;
407 rte
*new_free
= NULL
;
408 rte
*old_free
= NULL
;
409 ea_list
*tmpa
= NULL
;
412 stats
->exp_updates_received
++;
414 stats
->exp_withdraws_received
++;
417 * This is a tricky part - we don't know whether route 'old' was
418 * exported to protocol 'p' or was filtered by the export filter.
419 * We try to run the export filter to know this to have a correct
420 * value in 'old' argument of rte_update (and proper filter value)
422 * FIXME - this is broken because 'configure soft' may change
423 * filters but keep routes. Refeed is expected to be called after
424 * change of the filters and with old == new, therefore we do not
425 * even try to run the filter on an old route, This may lead to
426 * 'spurious withdraws' but ensure that there are no 'missing
429 * This is not completely safe as there is a window between
430 * reconfiguration and the end of refeed - if a newly filtered
431 * route disappears during this period, proper withdraw is not
432 * sent (because old would be also filtered) and the route is
433 * not refeeded (because it disappeared before that).
437 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
440 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
445 * As mentioned above, 'old' value may be incorrect in some race conditions.
446 * We generally ignore it with the exception of withdraw to pipe protocol.
447 * In that case we rather propagate unfiltered withdraws regardless of
448 * export filters to ensure that when a protocol is flushed, its routes are
449 * removed from all tables. Possible spurious unfiltered withdraws are not
450 * problem here as they are ignored if there is no corresponding route at
451 * the other end of the pipe. We directly call rt_notify() hook instead of
452 * do_rt_notify() to avoid logging and stat counters.
456 if ((p
->proto
== &proto_pipe
) && !new0
&& (p
!= old0
->sender
->proto
))
457 p
->rt_notify(p
, ah
->table
, net
, NULL
, old0
, NULL
);
463 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
465 /* Discard temporary rte's */
473 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
, int feed
)
475 // struct proto *p = ah->proto;
476 struct proto_stats
*stats
= ah
->stats
;
479 rte
*new_best
= NULL
;
480 rte
*old_best
= NULL
;
481 rte
*new_free
= NULL
;
482 rte
*old_free
= NULL
;
483 ea_list
*tmpa
= NULL
;
485 /* Used to track whether we met old_changed position. If before_old is NULL
486 old_changed was the first and we met it implicitly before current best route. */
487 int old_meet
= old_changed
&& !before_old
;
489 /* Note that before_old is either NULL or valid (not rejected) route.
490 If old_changed is valid, before_old have to be too. If old changed route
491 was not valid, caller must use NULL for both old_changed and before_old. */
494 stats
->exp_updates_received
++;
496 stats
->exp_withdraws_received
++;
498 /* First, find the new_best route - first accepted by filters */
499 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
501 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
504 /* Note if we walked around the position of old_changed route */
510 * Second, handle the feed case. That means we do not care for
511 * old_best. It is NULL for feed, and the new_best for refeed.
512 * For refeed, there is a hack similar to one in rt_notify_basic()
513 * to ensure withdraws in case of changed filters
517 if (feed
== 2) /* refeed */
518 old_best
= new_best
? new_best
:
519 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
523 if (!new_best
&& !old_best
)
530 * Now, we find the old_best route. Generally, it is the same as the
531 * new_best, unless new_best is the same as new_changed or
532 * old_changed is accepted before new_best.
534 * There are four cases:
536 * - We would find and accept old_changed before new_best, therefore
537 * old_changed is old_best. In remaining cases we suppose this
540 * - We found no new_best, therefore there is also no old_best and
541 * we ignore this withdraw.
543 * - We found new_best different than new_changed, therefore
544 * old_best is the same as new_best and we ignore this update.
546 * - We found new_best the same as new_changed, therefore it cannot
547 * be old_best and we have to continue search for old_best.
552 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
559 /* Third case, we use r instead of new_best, because export_filter() could change it */
560 if (r
!= new_changed
)
568 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
570 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
574 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
578 /* Implicitly, old_best is NULL and new_best is non-NULL */
581 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
583 /* Discard temporary rte's */
592 mpnh_merge_rta(struct mpnh
*nhs
, rta
*a
, int max
)
594 struct mpnh nh
= { .gw
= a
->gw
, .iface
= a
->iface
};
595 struct mpnh
*nh2
= (a
->dest
== RTD_MULTIPATH
) ? a
->nexthops
: &nh
;
596 return mpnh_merge(nhs
, nh2
, 1, 0, max
, rte_update_pool
);
600 rt_export_merged(struct announce_hook
*ah
, net
*net
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
602 // struct proto *p = ah->proto;
603 struct mpnh
*nhs
= NULL
;
604 rte
*best0
, *best
, *rt0
, *rt
, *tmp
;
609 if (!rte_is_valid(best0
))
612 best
= export_filter(ah
, best0
, rt_free
, tmpa
, silent
);
614 if (!best
|| !rte_is_reachable(best
))
617 for (rt0
= best0
->next
; rt0
; rt0
= rt0
->next
)
619 if (!rte_mergable(best0
, rt0
))
622 rt
= export_filter(ah
, rt0
, &tmp
, NULL
, 1);
627 if (rte_is_reachable(rt
))
628 nhs
= mpnh_merge_rta(nhs
, rt
->attrs
, ah
->proto
->merge_limit
);
636 nhs
= mpnh_merge_rta(nhs
, best
->attrs
, ah
->proto
->merge_limit
);
640 best
= rte_cow_rta(best
, rte_update_pool
);
641 best
->attrs
->dest
= RTD_MULTIPATH
;
642 best
->attrs
->nexthops
= nhs
;
654 rt_notify_merged(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
,
655 rte
*new_best
, rte
*old_best
, int refeed
)
657 // struct proto *p = ah->proto;
659 rte
*new_best_free
= NULL
;
660 rte
*old_best_free
= NULL
;
661 rte
*new_changed_free
= NULL
;
662 rte
*old_changed_free
= NULL
;
663 ea_list
*tmpa
= NULL
;
665 /* We assume that all rte arguments are either NULL or rte_is_valid() */
667 /* This check should be done by the caller */
668 if (!new_best
&& !old_best
)
671 /* Check whether the change is relevant to the merged route */
672 if ((new_best
== old_best
) && !refeed
)
674 new_changed
= rte_mergable(new_best
, new_changed
) ?
675 export_filter(ah
, new_changed
, &new_changed_free
, NULL
, 1) : NULL
;
677 old_changed
= rte_mergable(old_best
, old_changed
) ?
678 export_filter(ah
, old_changed
, &old_changed_free
, NULL
, 1) : NULL
;
680 if (!new_changed
&& !old_changed
)
685 ah
->stats
->exp_updates_received
++;
687 ah
->stats
->exp_withdraws_received
++;
689 /* Prepare new merged route */
691 new_best
= rt_export_merged(ah
, net
, &new_best_free
, &tmpa
, 0);
693 /* Prepare old merged route (without proper merged next hops) */
694 /* There are some issues with running filter on old route - see rt_notify_basic() */
695 if (old_best
&& !refeed
)
696 old_best
= export_filter(ah
, old_best
, &old_best_free
, NULL
, 1);
698 if (new_best
|| old_best
)
699 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, refeed
);
701 /* Discard temporary rte's */
703 rte_free(new_best_free
);
705 rte_free(old_best_free
);
706 if (new_changed_free
)
707 rte_free(new_changed_free
);
708 if (old_changed_free
)
709 rte_free(old_changed_free
);
714 * rte_announce - announce a routing table change
715 * @tab: table the route has been added to
716 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
717 * @net: network in question
718 * @new: the new route to be announced
719 * @old: the previous route for the same network
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
);
810 * rte_free - delete a &rte
811 * @e: &rte to be deleted
813 * rte_free() deletes the given &rte from the routing table it's linked to.
818 if (rta_is_cached(e
->attrs
))
820 sl_free(rte_slab
, e
);
824 rte_free_quick(rte
*e
)
827 sl_free(rte_slab
, e
);
831 rte_same(rte
*x
, rte
*y
)
834 x
->attrs
== y
->attrs
&&
835 x
->flags
== y
->flags
&&
836 x
->pflags
== y
->pflags
&&
837 x
->pref
== y
->pref
&&
838 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
841 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
844 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
846 struct proto
*p
= ah
->proto
;
847 struct rtable
*table
= ah
->table
;
848 struct proto_stats
*stats
= ah
->stats
;
849 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
850 rte
*before_old
= NULL
;
851 rte
*old_best
= net
->routes
;
855 k
= &net
->routes
; /* Find and remove original route from the same protocol */
858 if (old
->attrs
->src
== src
)
860 /* If there is the same route in the routing table but from
861 * a different sender, then there are two paths from the
862 * source protocol to this routing table through transparent
863 * pipes, which is not allowed.
865 * We log that and ignore the route. If it is withdraw, we
866 * ignore it completely (there might be 'spurious withdraws',
867 * see FIXME in do_rte_announce())
869 if (old
->sender
->proto
!= p
)
873 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %I/%d to table %s",
874 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
880 if (new && rte_same(old
, new))
882 /* No changes, ignore the new route */
884 if (!rte_is_filtered(new))
886 stats
->imp_updates_ignored
++;
887 rte_trace_in(D_ROUTES
, p
, new, "ignored");
892 /* lastmod is used internally by RIP as the last time
893 when the route was received. */
894 if (src
->proto
->proto
== &proto_rip
)
911 stats
->imp_withdraws_ignored
++;
915 int new_ok
= rte_is_ok(new);
916 int old_ok
= rte_is_ok(old
);
918 struct proto_limit
*l
= ah
->rx_limit
;
919 if (l
&& !old
&& new)
921 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
923 if (all_routes
>= l
->limit
)
924 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
926 if (l
->state
== PLS_BLOCKED
)
928 /* In receive limit the situation is simple, old is NULL so
929 we just free new and exit like nothing happened */
931 stats
->imp_updates_ignored
++;
932 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
939 if (l
&& !old_ok
&& new_ok
)
941 if (stats
->imp_routes
>= l
->limit
)
942 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
944 if (l
->state
== PLS_BLOCKED
)
946 /* In import limit the situation is more complicated. We
947 shouldn't just drop the route, we should handle it like
948 it was filtered. We also have to continue the route
949 processing if old or new is non-NULL, but we should exit
950 if both are NULL as this case is probably assumed to be
953 stats
->imp_updates_ignored
++;
954 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
956 if (ah
->in_keep_filtered
)
957 new->flags
|= REF_FILTERED
;
959 { rte_free_quick(new); new = NULL
; }
961 /* Note that old && !new could be possible when
962 ah->in_keep_filtered changed in the recent past. */
973 stats
->imp_updates_accepted
++;
975 stats
->imp_withdraws_accepted
++;
977 stats
->imp_withdraws_ignored
++;
982 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
984 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
986 if (table
->config
->sorted
)
988 /* If routes are sorted, just insert new route to appropriate position */
991 if (before_old
&& !rte_better(new, before_old
))
992 k
= &before_old
->next
;
996 for (; *k
; k
=&(*k
)->next
)
997 if (rte_better(new, *k
))
1006 /* If routes are not sorted, find the best route and move it on
1007 the first position. There are several optimized cases. */
1009 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
1010 goto do_recalculate
;
1012 if (new && rte_better(new, old_best
))
1014 /* The first case - the new route is cleary optimal,
1015 we link it at the first position */
1017 new->next
= net
->routes
;
1020 else if (old
== old_best
)
1022 /* The second case - the old best route disappeared, we add the
1023 new route (if we have any) to the list (we don't care about
1024 position) and then we elect the new optimal route and relink
1025 that route at the first position and announce it. New optimal
1026 route might be NULL if there is no more routes */
1029 /* Add the new route to the list */
1032 new->next
= net
->routes
;
1036 /* Find a new optimal route (if there is any) */
1039 rte
**bp
= &net
->routes
;
1040 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
1041 if (rte_better(*k
, *bp
))
1047 best
->next
= net
->routes
;
1053 /* The third case - the new route is not better than the old
1054 best route (therefore old_best != NULL) and the old best
1055 route was not removed (therefore old_best == net->routes).
1056 We just link the new route after the old best route. */
1058 ASSERT(net
->routes
!= NULL
);
1059 new->next
= net
->routes
->next
;
1060 net
->routes
->next
= new;
1062 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1068 /* Log the route change */
1069 if (p
->debug
& D_ROUTES
)
1072 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
1075 if (old
!= old_best
)
1076 rte_trace(p
, old
, '>', "removed");
1077 else if (rte_is_ok(net
->routes
))
1078 rte_trace(p
, old
, '>', "removed [replaced]");
1080 rte_trace(p
, old
, '>', "removed [sole]");
1084 /* Propagate the route change */
1085 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, NULL
, NULL
);
1086 if (net
->routes
!= old_best
)
1087 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, NULL
, NULL
);
1088 if (table
->config
->sorted
)
1089 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, NULL
, NULL
, before_old
);
1090 rte_announce(table
, RA_MERGED
, net
, new, old
, net
->routes
, old_best
, NULL
);
1093 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
1094 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
1095 rt_schedule_gc(table
);
1097 if (old_ok
&& p
->rte_remove
)
1098 p
->rte_remove(net
, old
);
1099 if (new_ok
&& p
->rte_insert
)
1100 p
->rte_insert(net
, new);
1103 rte_free_quick(old
);
1106 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
1109 rte_update_lock(void)
1111 rte_update_nest_cnt
++;
1115 rte_update_unlock(void)
1117 if (!--rte_update_nest_cnt
)
1118 lp_flush(rte_update_pool
);
1122 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
1124 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
1126 *dummy
= net
->routes
;
1127 net
->routes
= (*dummy
)->next
;
1132 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
1136 (*dummy
)->next
= net
->routes
;
1137 net
->routes
= *dummy
;
1142 * rte_update - enter a new update to a routing table
1143 * @table: table to be updated
1144 * @ah: pointer to table announce hook
1145 * @net: network node
1146 * @p: protocol submitting the update
1147 * @src: protocol originating the update
1148 * @new: a &rte representing the new route or %NULL for route removal.
1150 * This function is called by the routing protocols whenever they discover
1151 * a new route or wish to update/remove an existing route. The right announcement
1152 * sequence is to build route attributes first (either un-cached with @aflags set
1153 * to zero or a cached one using rta_lookup(); in this case please note that
1154 * you need to increase the use count of the attributes yourself by calling
1155 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1156 * the appropriate data and finally submit the new &rte by calling rte_update().
1158 * @src specifies the protocol that originally created the route and the meaning
1159 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1160 * same value as @new->attrs->proto. @p specifies the protocol that called
1161 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1162 * stores @p in @new->sender;
1164 * When rte_update() gets any route, it automatically validates it (checks,
1165 * whether the network and next hop address are valid IP addresses and also
1166 * whether a normal routing protocol doesn't try to smuggle a host or link
1167 * scope route to the table), converts all protocol dependent attributes stored
1168 * in the &rte to temporary extended attributes, consults import filters of the
1169 * protocol to see if the route should be accepted and/or its attributes modified,
1170 * stores the temporary attributes back to the &rte.
1172 * Now, having a "public" version of the route, we
1173 * automatically find any old route defined by the protocol @src
1174 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1175 * recalculate the optimal route for this destination and finally broadcast
1176 * the change (if any) to all routing protocols by calling rte_announce().
1178 * All memory used for attribute lists and other temporary allocations is taken
1179 * from a special linear pool @rte_update_pool and freed when rte_update()
1184 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
1186 struct proto
*p
= ah
->proto
;
1187 struct proto_stats
*stats
= ah
->stats
;
1188 struct filter
*filter
= ah
->in_filter
;
1189 ea_list
*tmpa
= NULL
;
1197 stats
->imp_updates_received
++;
1198 if (!rte_validate(new))
1200 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1201 stats
->imp_updates_invalid
++;
1205 if (filter
== FILTER_REJECT
)
1207 stats
->imp_updates_filtered
++;
1208 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1210 if (! ah
->in_keep_filtered
)
1213 /* new is a private copy, i could modify it */
1214 new->flags
|= REF_FILTERED
;
1218 tmpa
= make_tmp_attrs(new, rte_update_pool
);
1219 if (filter
&& (filter
!= FILTER_REJECT
))
1221 ea_list
*old_tmpa
= tmpa
;
1222 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
1225 stats
->imp_updates_filtered
++;
1226 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1228 if (! ah
->in_keep_filtered
)
1231 new->flags
|= REF_FILTERED
;
1233 if (tmpa
!= old_tmpa
&& src
->proto
->store_tmp_attrs
)
1234 src
->proto
->store_tmp_attrs(new, tmpa
);
1237 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1238 new->attrs
= rta_lookup(new->attrs
);
1239 new->flags
|= REF_COW
;
1243 stats
->imp_withdraws_received
++;
1247 stats
->imp_withdraws_ignored
++;
1248 rte_update_unlock();
1254 rte_hide_dummy_routes(net
, &dummy
);
1255 rte_recalculate(ah
, net
, new, src
);
1256 rte_unhide_dummy_routes(net
, &dummy
);
1257 rte_update_unlock();
1266 /* Independent call to rte_announce(), used from next hop
1267 recalculation, outside of rte_update(). new must be non-NULL */
1269 rte_announce_i(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
1270 rte
*new_best
, rte
*old_best
)
1273 rte_announce(tab
, type
, net
, new, old
, new_best
, old_best
, NULL
);
1274 rte_update_unlock();
1278 rte_discard(rtable
*t
, rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1281 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1282 rte_update_unlock();
1285 /* Check rtable for best route to given net whether it would be exported do p */
1287 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1289 net
*n
= net_find(t
, prefix
, pxlen
);
1290 rte
*rt
= n
? n
->routes
: NULL
;
1292 if (!rte_is_valid(rt
))
1297 /* Rest is stripped down export_filter() */
1298 ea_list
*tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
1299 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1300 if (v
== RIC_PROCESS
)
1301 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
1303 /* Discard temporary rte */
1304 if (rt
!= n
->routes
)
1307 rte_update_unlock();
1314 * rt_refresh_begin - start a refresh cycle
1315 * @t: related routing table
1316 * @ah: related announce hook
1318 * This function starts a refresh cycle for given routing table and announce
1319 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1320 * routes to the routing table (by rte_update()). After that, all protocol
1321 * routes (more precisely routes with @ah as @sender) not sent during the
1322 * refresh cycle but still in the table from the past are pruned. This is
1323 * implemented by marking all related routes as stale by REF_STALE flag in
1324 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1325 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1328 rt_refresh_begin(rtable
*t
, struct announce_hook
*ah
)
1333 FIB_WALK(&t
->fib
, fn
)
1336 for (e
= n
->routes
; e
; e
= e
->next
)
1337 if (e
->sender
== ah
)
1338 e
->flags
|= REF_STALE
;
1344 * rt_refresh_end - end a refresh cycle
1345 * @t: related routing table
1346 * @ah: related announce hook
1348 * This function starts a refresh cycle for given routing table and announce
1349 * hook. See rt_refresh_begin() for description of refresh cycles.
1352 rt_refresh_end(rtable
*t
, struct announce_hook
*ah
)
1358 FIB_WALK(&t
->fib
, fn
)
1361 for (e
= n
->routes
; e
; e
= e
->next
)
1362 if ((e
->sender
== ah
) && (e
->flags
& REF_STALE
))
1364 e
->flags
|= REF_DISCARD
;
1371 rt_schedule_prune(t
);
1376 * rte_dump - dump a route
1377 * @e: &rte to be dumped
1379 * This functions dumps contents of a &rte to debug output.
1385 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1386 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1388 if (e
->attrs
->src
->proto
->proto
->dump_attrs
)
1389 e
->attrs
->src
->proto
->proto
->dump_attrs(e
);
1394 * rt_dump - dump a routing table
1395 * @t: routing table to be dumped
1397 * This function dumps contents of a given routing table to debug output.
1404 struct announce_hook
*a
;
1406 debug("Dump of routing table <%s>\n", t
->name
);
1410 FIB_WALK(&t
->fib
, fn
)
1413 for(e
=n
->routes
; e
; e
=e
->next
)
1417 WALK_LIST(a
, t
->hooks
)
1418 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1423 * rt_dump_all - dump all routing tables
1425 * This function dumps contents of all routing tables to debug output.
1432 WALK_LIST(t
, routing_tables
)
1437 rt_schedule_prune(rtable
*tab
)
1439 rt_mark_for_prune(tab
);
1440 ev_schedule(tab
->rt_event
);
1444 rt_schedule_gc(rtable
*tab
)
1446 if (tab
->gc_scheduled
)
1449 tab
->gc_scheduled
= 1;
1450 ev_schedule(tab
->rt_event
);
1454 rt_schedule_hcu(rtable
*tab
)
1456 if (tab
->hcu_scheduled
)
1459 tab
->hcu_scheduled
= 1;
1460 ev_schedule(tab
->rt_event
);
1464 rt_schedule_nhu(rtable
*tab
)
1466 if (tab
->nhu_state
== 0)
1467 ev_schedule(tab
->rt_event
);
1469 /* state change 0->1, 2->3 */
1470 tab
->nhu_state
|= 1;
1475 rt_prune_nets(rtable
*tab
)
1477 struct fib_iterator fit
;
1478 int ncnt
= 0, ndel
= 0;
1481 fib_check(&tab
->fib
);
1484 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1486 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1490 if (!n
->routes
) /* Orphaned FIB entry */
1492 FIB_ITERATE_PUT(&fit
, f
);
1493 fib_delete(&tab
->fib
, f
);
1499 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1501 tab
->gc_counter
= 0;
1503 tab
->gc_scheduled
= 0;
1511 if (tab
->hcu_scheduled
)
1512 rt_update_hostcache(tab
);
1515 rt_next_hop_update(tab
);
1517 if (tab
->prune_state
)
1518 if (!rt_prune_table(tab
))
1520 /* Table prune unfinished */
1521 ev_schedule(tab
->rt_event
);
1525 if (tab
->gc_scheduled
)
1528 rt_prune_sources(); // FIXME this should be moved to independent event
1533 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1535 bzero(t
, sizeof(*t
));
1536 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1539 init_list(&t
->hooks
);
1542 t
->rt_event
= ev_new(p
);
1543 t
->rt_event
->hook
= rt_event
;
1544 t
->rt_event
->data
= t
;
1550 * rt_init - initialize routing tables
1552 * This function is called during BIRD startup. It initializes the
1553 * routing table module.
1559 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1560 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1561 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1562 init_list(&routing_tables
);
1567 rt_prune_step(rtable
*tab
, int *limit
)
1569 struct fib_iterator
*fit
= &tab
->prune_fit
;
1571 DBG("Pruning route table %s\n", tab
->name
);
1573 fib_check(&tab
->fib
);
1576 if (tab
->prune_state
== RPS_NONE
)
1579 if (tab
->prune_state
== RPS_SCHEDULED
)
1581 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1582 tab
->prune_state
= RPS_RUNNING
;
1586 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1588 net
*n
= (net
*) fn
;
1592 for (e
=n
->routes
; e
; e
=e
->next
)
1593 if (e
->sender
->proto
->flushing
|| (e
->flags
& REF_DISCARD
))
1597 FIB_ITERATE_PUT(fit
, fn
);
1601 rte_discard(tab
, e
);
1606 if (!n
->routes
) /* Orphaned FIB entry */
1608 FIB_ITERATE_PUT(fit
, fn
);
1609 fib_delete(&tab
->fib
, fn
);
1613 FIB_ITERATE_END(fn
);
1616 fib_check(&tab
->fib
);
1619 tab
->prune_state
= RPS_NONE
;
1624 * rt_prune_table - prune a routing table
1626 * This function scans the routing table @tab and removes routes belonging to
1627 * flushing protocols, discarded routes and also stale network entries, in a
1628 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1629 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1630 * protocol flushing loop, but it is called from rt_event() for just one routing
1633 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1634 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1637 rt_prune_table(rtable
*tab
)
1640 return rt_prune_step(tab
, &limit
);
1644 * rt_prune_loop - prune routing tables
1646 * The prune loop scans routing tables and removes routes belonging to flushing
1647 * protocols, discarded routes and also stale network entries. Returns 1 when
1648 * all such routes are pruned. It is a part of the protocol flushing loop.
1656 WALK_LIST(t
, routing_tables
)
1657 if (! rt_prune_step(t
, &limit
))
1664 rt_preconfig(struct config
*c
)
1666 struct symbol
*s
= cf_find_symbol("master");
1668 init_list(&c
->tables
);
1669 c
->master_rtc
= rt_new_table(s
);
1674 * Some functions for handing internal next hop updates
1675 * triggered by rt_schedule_nhu().
1679 rta_next_hop_outdated(rta
*a
)
1681 struct hostentry
*he
= a
->hostentry
;
1687 return a
->dest
!= RTD_UNREACHABLE
;
1689 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1690 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1691 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1695 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1698 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1701 a
->igp_metric
= he
->igp_metric
;
1702 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1706 rt_next_hop_update_rte(rtable
*tab
, rte
*old
)
1709 memcpy(&a
, old
->attrs
, sizeof(rta
));
1710 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1713 rte
*e
= sl_alloc(rte_slab
);
1714 memcpy(e
, old
, sizeof(rte
));
1715 e
->attrs
= rta_lookup(&a
);
1721 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1723 rte
**k
, *e
, *new, *old_best
, **new_best
;
1725 int free_old_best
= 0;
1727 old_best
= n
->routes
;
1731 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1732 if (rta_next_hop_outdated(e
->attrs
))
1734 new = rt_next_hop_update_rte(tab
, e
);
1737 rte_announce_i(tab
, RA_ANY
, n
, new, e
, NULL
, NULL
);
1738 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1740 /* Call a pre-comparison hook */
1741 /* Not really an efficient way to compute this */
1742 if (e
->attrs
->src
->proto
->rte_recalculate
)
1743 e
->attrs
->src
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1747 else /* Freeing of the old best rte is postponed */
1757 /* Find the new best route */
1759 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1761 if (!new_best
|| rte_better(e
, *new_best
))
1765 /* Relink the new best route to the first position */
1767 if (new != n
->routes
)
1769 *new_best
= new->next
;
1770 new->next
= n
->routes
;
1774 /* Announce the new best route */
1775 if (new != old_best
)
1777 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
, NULL
, NULL
);
1778 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1781 /* FIXME: Better announcement of merged routes */
1782 rte_announce_i(tab
, RA_MERGED
, n
, new, old_best
, new, old_best
);
1785 rte_free_quick(old_best
);
1791 rt_next_hop_update(rtable
*tab
)
1793 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1796 if (tab
->nhu_state
== 0)
1799 if (tab
->nhu_state
== 1)
1801 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1805 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1809 FIB_ITERATE_PUT(fit
, fn
);
1810 ev_schedule(tab
->rt_event
);
1813 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1815 FIB_ITERATE_END(fn
);
1817 /* state change 2->0, 3->1 */
1818 tab
->nhu_state
&= 1;
1820 if (tab
->nhu_state
> 0)
1821 ev_schedule(tab
->rt_event
);
1825 struct rtable_config
*
1826 rt_new_table(struct symbol
*s
)
1828 /* Hack that allows to 'redefine' the master table */
1829 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1832 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1834 cf_define_symbol(s
, SYM_TABLE
, c
);
1836 add_tail(&new_config
->tables
, &c
->n
);
1837 c
->gc_max_ops
= 1000;
1843 * rt_lock_table - lock a routing table
1844 * @r: routing table to be locked
1846 * Lock a routing table, because it's in use by a protocol,
1847 * preventing it from being freed when it gets undefined in a new
1851 rt_lock_table(rtable
*r
)
1857 * rt_unlock_table - unlock a routing table
1858 * @r: routing table to be unlocked
1860 * Unlock a routing table formerly locked by rt_lock_table(),
1861 * that is decrease its use count and delete it if it's scheduled
1862 * for deletion by configuration changes.
1865 rt_unlock_table(rtable
*r
)
1867 if (!--r
->use_count
&& r
->deleted
)
1869 struct config
*conf
= r
->deleted
;
1870 DBG("Deleting routing table %s\n", r
->name
);
1872 rt_free_hostcache(r
);
1877 config_del_obstacle(conf
);
1882 * rt_commit - commit new routing table configuration
1883 * @new: new configuration
1884 * @old: original configuration or %NULL if it's boot time config
1886 * Scan differences between @old and @new configuration and modify
1887 * the routing tables according to these changes. If @new defines a
1888 * previously unknown table, create it, if it omits a table existing
1889 * in @old, schedule it for deletion (it gets deleted when all protocols
1890 * disconnect from it by calling rt_unlock_table()), if it exists
1891 * in both configurations, leave it unchanged.
1894 rt_commit(struct config
*new, struct config
*old
)
1896 struct rtable_config
*o
, *r
;
1898 DBG("rt_commit:\n");
1901 WALK_LIST(o
, old
->tables
)
1903 rtable
*ot
= o
->table
;
1906 struct symbol
*sym
= cf_find_symbol(o
->name
);
1907 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1909 DBG("\t%s: same\n", o
->name
);
1914 if (o
->sorted
!= r
->sorted
)
1915 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1919 DBG("\t%s: deleted\n", o
->name
);
1921 config_add_obstacle(old
);
1923 rt_unlock_table(ot
);
1929 WALK_LIST(r
, new->tables
)
1932 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1933 DBG("\t%s: created\n", r
->name
);
1934 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1935 add_tail(&routing_tables
, &t
->n
);
1942 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1945 if (type
== RA_ACCEPTED
)
1946 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, p
->refeeding
? 2 : 1);
1947 else if (type
== RA_MERGED
)
1948 rt_notify_merged(h
, n
, NULL
, NULL
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1950 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1951 rte_update_unlock();
1955 * rt_feed_baby - advertise routes to a new protocol
1956 * @p: protocol to be fed
1958 * This function performs one pass of advertisement of routes to a newly
1959 * initialized protocol. It's called by the protocol code as long as it
1960 * has something to do. (We avoid transferring all the routes in single
1961 * pass in order not to monopolize CPU time.)
1964 rt_feed_baby(struct proto
*p
)
1966 struct announce_hook
*h
;
1967 struct fib_iterator
*fit
;
1970 if (!p
->feed_ahook
) /* Need to initialize first */
1974 DBG("Announcing routes to new protocol %s\n", p
->name
);
1975 p
->feed_ahook
= p
->ahooks
;
1976 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1979 fit
= p
->feed_iterator
;
1983 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1985 net
*n
= (net
*) fn
;
1989 FIB_ITERATE_PUT(fit
, fn
);
1993 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1995 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
1996 (p
->accept_ra_types
== RA_ACCEPTED
) ||
1997 (p
->accept_ra_types
== RA_MERGED
))
1998 if (rte_is_valid(e
))
2000 if (p
->export_state
!= ES_FEEDING
)
2001 return 1; /* In the meantime, the protocol fell down. */
2003 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
2007 if (p
->accept_ra_types
== RA_ANY
)
2008 for(e
= n
->routes
; e
; e
= e
->next
)
2010 if (p
->export_state
!= ES_FEEDING
)
2011 return 1; /* In the meantime, the protocol fell down. */
2013 if (!rte_is_valid(e
))
2016 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
2020 FIB_ITERATE_END(fn
);
2021 p
->feed_ahook
= h
->next
;
2024 mb_free(p
->feed_iterator
);
2025 p
->feed_iterator
= NULL
;
2031 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
2036 * rt_feed_baby_abort - abort protocol feeding
2039 * This function is called by the protocol code when the protocol
2040 * stops or ceases to exist before the last iteration of rt_feed_baby()
2044 rt_feed_baby_abort(struct proto
*p
)
2048 /* Unlink the iterator and exit */
2049 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
2050 p
->feed_ahook
= NULL
;
2055 static inline unsigned
2058 uintptr_t p
= (uintptr_t) ptr
;
2059 return p
^ (p
<< 8) ^ (p
>> 16);
2062 static inline unsigned
2063 hc_hash(ip_addr a
, rtable
*dep
)
2065 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
2069 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
2071 uint k
= he
->hash_key
>> hc
->hash_shift
;
2072 he
->next
= hc
->hash_table
[k
];
2073 hc
->hash_table
[k
] = he
;
2077 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
2079 struct hostentry
**hep
;
2080 uint k
= he
->hash_key
>> hc
->hash_shift
;
2082 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
2086 #define HC_DEF_ORDER 10
2087 #define HC_HI_MARK *4
2088 #define HC_HI_STEP 2
2089 #define HC_HI_ORDER 16 /* Must be at most 16 */
2090 #define HC_LO_MARK /5
2091 #define HC_LO_STEP 2
2092 #define HC_LO_ORDER 10
2095 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
2097 unsigned hsize
= 1 << order
;
2098 hc
->hash_order
= order
;
2099 hc
->hash_shift
= 16 - order
;
2100 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0 : (hsize HC_HI_MARK
);
2101 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0 : (hsize HC_LO_MARK
);
2103 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
2107 hc_resize(struct hostcache
*hc
, unsigned new_order
)
2109 unsigned old_size
= 1 << hc
->hash_order
;
2110 struct hostentry
**old_table
= hc
->hash_table
;
2111 struct hostentry
*he
, *hen
;
2114 hc_alloc_table(hc
, new_order
);
2115 for (i
= 0; i
< old_size
; i
++)
2116 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
2124 static struct hostentry
*
2125 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
2127 struct hostentry
*he
= sl_alloc(hc
->slab
);
2136 add_tail(&hc
->hostentries
, &he
->ln
);
2140 if (hc
->hash_items
> hc
->hash_max
)
2141 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
2147 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
2153 sl_free(hc
->slab
, he
);
2156 if (hc
->hash_items
< hc
->hash_min
)
2157 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
2161 rt_init_hostcache(rtable
*tab
)
2163 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
2164 init_list(&hc
->hostentries
);
2167 hc_alloc_table(hc
, HC_DEF_ORDER
);
2168 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
2170 hc
->lp
= lp_new(rt_table_pool
, 1008);
2171 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2173 tab
->hostcache
= hc
;
2177 rt_free_hostcache(rtable
*tab
)
2179 struct hostcache
*hc
= tab
->hostcache
;
2182 WALK_LIST(n
, hc
->hostentries
)
2184 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
2188 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
2193 mb_free(hc
->hash_table
);
2198 rt_notify_hostcache(rtable
*tab
, net
*net
)
2200 struct hostcache
*hc
= tab
->hostcache
;
2202 if (tab
->hcu_scheduled
)
2205 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
2206 rt_schedule_hcu(tab
);
2210 if_local_addr(ip_addr a
, struct iface
*i
)
2214 WALK_LIST(b
, i
->addrs
)
2215 if (ipa_equal(a
, b
->ip
))
2222 rt_get_igp_metric(rte
*rt
)
2224 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
2232 if ((a
->source
== RTS_OSPF
) ||
2233 (a
->source
== RTS_OSPF_IA
) ||
2234 (a
->source
== RTS_OSPF_EXT1
))
2235 return rt
->u
.ospf
.metric1
;
2239 if (a
->source
== RTS_RIP
)
2240 return rt
->u
.rip
.metric
;
2244 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
2247 return IGP_METRIC_UNKNOWN
;
2251 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
2253 rta
*old_src
= he
->src
;
2256 /* Reset the hostentry */
2259 he
->dest
= RTD_UNREACHABLE
;
2262 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
2271 /* Recursive route should not depend on another recursive route */
2272 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
2273 he
->addr
, n
->n
.prefix
, pxlen
);
2277 if (a
->dest
== RTD_DEVICE
)
2279 if (if_local_addr(he
->addr
, a
->iface
))
2281 /* The host address is a local address, this is not valid */
2282 log(L_WARN
"Next hop address %I is a local address of iface %s",
2283 he
->addr
, a
->iface
->name
);
2287 /* The host is directly reachable, use link as a gateway */
2289 he
->dest
= RTD_ROUTER
;
2293 /* The host is reachable through some route entry */
2298 he
->src
= rta_clone(a
);
2299 he
->igp_metric
= rt_get_igp_metric(e
);
2303 /* Add a prefix range to the trie */
2304 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
2307 return old_src
!= he
->src
;
2311 rt_update_hostcache(rtable
*tab
)
2313 struct hostcache
*hc
= tab
->hostcache
;
2314 struct hostentry
*he
;
2317 /* Reset the trie */
2319 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2321 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
2323 he
= SKIP_BACK(struct hostentry
, ln
, n
);
2326 hc_delete_hostentry(hc
, he
);
2330 if (rt_update_hostentry(tab
, he
))
2331 rt_schedule_nhu(he
->tab
);
2334 tab
->hcu_scheduled
= 0;
2337 static struct hostentry
*
2338 rt_get_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2340 struct hostentry
*he
;
2342 if (!tab
->hostcache
)
2343 rt_init_hostcache(tab
);
2345 uint k
= hc_hash(a
, dep
);
2346 struct hostcache
*hc
= tab
->hostcache
;
2347 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2348 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2351 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
2352 rt_update_hostentry(tab
, he
);
2357 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
2359 rta_apply_hostentry(a
, rt_get_hostentry(tab
, *gw
, *ll
, dep
));
2368 rt_format_via(rte
*e
, byte
*via
)
2374 case RTD_ROUTER
: bsprintf(via
, "via %I on %s", a
->gw
, a
->iface
->name
); break;
2375 case RTD_DEVICE
: bsprintf(via
, "dev %s", a
->iface
->name
); break;
2376 case RTD_BLACKHOLE
: bsprintf(via
, "blackhole"); break;
2377 case RTD_UNREACHABLE
: bsprintf(via
, "unreachable"); break;
2378 case RTD_PROHIBIT
: bsprintf(via
, "prohibited"); break;
2379 case RTD_MULTIPATH
: bsprintf(via
, "multipath"); break;
2380 default: bsprintf(via
, "???");
2385 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2387 byte via
[STD_ADDRESS_P_LENGTH
+32], from
[STD_ADDRESS_P_LENGTH
+8];
2388 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2390 int primary
= (e
->net
->routes
== e
);
2391 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2392 void (*get_route_info
)(struct rte
*, byte
*buf
, struct ea_list
*attrs
);
2395 rt_format_via(e
, via
);
2396 tm_format_datetime(tm
, &config
->tf_route
, e
->lastmod
);
2397 if (ipa_nonzero(a
->from
) && !ipa_equal(a
->from
, a
->gw
))
2398 bsprintf(from
, " from %I", a
->from
);
2402 get_route_info
= a
->src
->proto
->proto
->get_route_info
;
2403 if (get_route_info
|| d
->verbose
)
2405 /* Need to normalize the extended attributes */
2407 t
= ea_append(t
, a
->eattrs
);
2408 tmpa
= alloca(ea_scan(t
));
2413 get_route_info(e
, info
, tmpa
);
2415 bsprintf(info
, " (%d)", e
->pref
);
2416 cli_printf(c
, -1007, "%-18s %s [%s %s%s]%s%s", ia
, via
, a
->src
->proto
->name
,
2417 tm
, from
, primary
? (sync_error
? " !" : " *") : "", info
);
2418 for (nh
= a
->nexthops
; nh
; nh
= nh
->next
)
2419 cli_printf(c
, -1007, "\tvia %I on %s weight %d", nh
->gw
, nh
->iface
->name
, nh
->weight
+ 1);
2421 rta_show(c
, a
, tmpa
);
2425 rt_show_net(struct cli
*c
, net
*n
, struct rt_show_data
*d
)
2428 byte ia
[STD_ADDRESS_P_LENGTH
+8];
2429 struct ea_list
*tmpa
;
2430 struct announce_hook
*a
= NULL
;
2434 bsprintf(ia
, "%I/%d", n
->n
.prefix
, n
->n
.pxlen
);
2438 if (! d
->export_protocol
->rt_notify
)
2441 a
= proto_find_announce_hook(d
->export_protocol
, d
->table
);
2446 for (e
= n
->routes
; e
; e
= e
->next
)
2448 if (rte_is_filtered(e
) != d
->filtered
)
2452 d
->net_counter
+= first
;
2459 rte_update_lock(); /* We use the update buffer for filtering */
2460 tmpa
= make_tmp_attrs(e
, rte_update_pool
);
2462 /* Special case for merged export */
2463 if ((d
->export_mode
== RSEM_EXPORT
) && (d
->export_protocol
->accept_ra_types
== RA_MERGED
))
2466 e
= rt_export_merged(a
, n
, &rt_free
, &tmpa
, 1);
2470 { e
= ee
; goto skip
; }
2472 else if (d
->export_mode
)
2474 struct proto
*ep
= d
->export_protocol
;
2475 int ic
= ep
->import_control
? ep
->import_control(ep
, &e
, &tmpa
, rte_update_pool
) : 0;
2477 if (ep
->accept_ra_types
== RA_OPTIMAL
|| ep
->accept_ra_types
== RA_MERGED
)
2483 if (d
->export_mode
> RSEM_PREEXPORT
)
2486 * FIXME - This shows what should be exported according to current
2487 * filters, but not what was really exported. 'configure soft'
2488 * command may change the export filter and do not update routes.
2490 int do_export
= (ic
> 0) ||
2491 (f_run(a
->out_filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
2493 if (do_export
!= (d
->export_mode
== RSEM_EXPORT
))
2496 if ((d
->export_mode
== RSEM_EXPORT
) && (ep
->accept_ra_types
== RA_ACCEPTED
))
2501 if (d
->show_protocol
&& (d
->show_protocol
!= e
->attrs
->src
->proto
))
2504 if (f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
)
2509 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2518 rte_update_unlock();
2520 if (d
->primary_only
)
2526 rt_show_cont(struct cli
*c
)
2528 struct rt_show_data
*d
= c
->rover
;
2534 struct fib
*fib
= &d
->table
->fib
;
2535 struct fib_iterator
*it
= &d
->fit
;
2537 FIB_ITERATE_START(fib
, it
, f
)
2540 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2542 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2545 if (d
->export_protocol
&& (d
->export_protocol
->export_state
== ES_DOWN
))
2547 cli_printf(c
, 8005, "Protocol is down");
2552 FIB_ITERATE_PUT(it
, f
);
2555 rt_show_net(c
, n
, d
);
2559 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2561 cli_printf(c
, 0, "");
2563 c
->cont
= c
->cleanup
= NULL
;
2567 rt_show_cleanup(struct cli
*c
)
2569 struct rt_show_data
*d
= c
->rover
;
2571 /* Unlink the iterator */
2572 fit_get(&d
->table
->fib
, &d
->fit
);
2576 rt_show(struct rt_show_data
*d
)
2580 /* Default is either a master table or a table related to a respective protocol */
2581 if (!d
->table
&& d
->export_protocol
) d
->table
= d
->export_protocol
->table
;
2582 if (!d
->table
&& d
->show_protocol
) d
->table
= d
->show_protocol
->table
;
2583 if (!d
->table
) d
->table
= config
->master_rtc
->table
;
2585 /* Filtered routes are neither exported nor have sensible ordering */
2586 if (d
->filtered
&& (d
->export_mode
|| d
->primary_only
))
2589 if (d
->pxlen
== 256)
2591 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2592 this_cli
->cont
= rt_show_cont
;
2593 this_cli
->cleanup
= rt_show_cleanup
;
2594 this_cli
->rover
= d
;
2599 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2601 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2604 rt_show_net(this_cli
, n
, d
);
2609 cli_msg(8001, "Network not in table");
2614 * Documentation for functions declared inline in route.h
2619 * net_find - find a network entry
2620 * @tab: a routing table
2621 * @addr: address of the network
2622 * @len: length of the network prefix
2624 * net_find() looks up the given network in routing table @tab and
2625 * returns a pointer to its &net entry or %NULL if no such network
2628 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2632 * net_get - obtain a network entry
2633 * @tab: a routing table
2634 * @addr: address of the network
2635 * @len: length of the network prefix
2637 * net_get() looks up the given network in routing table @tab and
2638 * returns a pointer to its &net entry. If no such entry exists, it's
2641 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2645 * rte_cow - copy a route for writing
2646 * @r: a route entry to be copied
2648 * rte_cow() takes a &rte and prepares it for modification. The exact action
2649 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2650 * just returned unchanged, else a new temporary entry with the same contents
2653 * The primary use of this function is inside the filter machinery -- when
2654 * a filter wants to modify &rte contents (to change the preference or to
2655 * attach another set of attributes), it must ensure that the &rte is not
2656 * shared with anyone else (and especially that it isn't stored in any routing
2659 * Result: a pointer to the new writable &rte.
2661 static inline rte
* rte_cow(rte
*r
)