]>
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
);
811 * rte_free - delete a &rte
812 * @e: &rte to be deleted
814 * rte_free() deletes the given &rte from the routing table it's linked to.
819 if (rta_is_cached(e
->attrs
))
821 sl_free(rte_slab
, e
);
825 rte_free_quick(rte
*e
)
828 sl_free(rte_slab
, e
);
832 rte_same(rte
*x
, rte
*y
)
835 x
->attrs
== y
->attrs
&&
836 x
->flags
== y
->flags
&&
837 x
->pflags
== y
->pflags
&&
838 x
->pref
== y
->pref
&&
839 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
842 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
845 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
847 struct proto
*p
= ah
->proto
;
848 struct rtable
*table
= ah
->table
;
849 struct proto_stats
*stats
= ah
->stats
;
850 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
851 rte
*before_old
= NULL
;
852 rte
*old_best
= net
->routes
;
856 k
= &net
->routes
; /* Find and remove original route from the same protocol */
859 if (old
->attrs
->src
== src
)
861 /* If there is the same route in the routing table but from
862 * a different sender, then there are two paths from the
863 * source protocol to this routing table through transparent
864 * pipes, which is not allowed.
866 * We log that and ignore the route. If it is withdraw, we
867 * ignore it completely (there might be 'spurious withdraws',
868 * see FIXME in do_rte_announce())
870 if (old
->sender
->proto
!= p
)
874 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %I/%d to table %s",
875 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
881 if (new && rte_same(old
, new))
883 /* No changes, ignore the new route */
885 if (!rte_is_filtered(new))
887 stats
->imp_updates_ignored
++;
888 rte_trace_in(D_ROUTES
, p
, new, "ignored");
906 stats
->imp_withdraws_ignored
++;
910 int new_ok
= rte_is_ok(new);
911 int old_ok
= rte_is_ok(old
);
913 struct proto_limit
*l
= ah
->rx_limit
;
914 if (l
&& !old
&& new)
916 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
918 if (all_routes
>= l
->limit
)
919 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
921 if (l
->state
== PLS_BLOCKED
)
923 /* In receive limit the situation is simple, old is NULL so
924 we just free new and exit like nothing happened */
926 stats
->imp_updates_ignored
++;
927 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
934 if (l
&& !old_ok
&& new_ok
)
936 if (stats
->imp_routes
>= l
->limit
)
937 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
939 if (l
->state
== PLS_BLOCKED
)
941 /* In import limit the situation is more complicated. We
942 shouldn't just drop the route, we should handle it like
943 it was filtered. We also have to continue the route
944 processing if old or new is non-NULL, but we should exit
945 if both are NULL as this case is probably assumed to be
948 stats
->imp_updates_ignored
++;
949 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
951 if (ah
->in_keep_filtered
)
952 new->flags
|= REF_FILTERED
;
954 { rte_free_quick(new); new = NULL
; }
956 /* Note that old && !new could be possible when
957 ah->in_keep_filtered changed in the recent past. */
968 stats
->imp_updates_accepted
++;
970 stats
->imp_withdraws_accepted
++;
972 stats
->imp_withdraws_ignored
++;
977 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
979 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
981 if (table
->config
->sorted
)
983 /* If routes are sorted, just insert new route to appropriate position */
986 if (before_old
&& !rte_better(new, before_old
))
987 k
= &before_old
->next
;
991 for (; *k
; k
=&(*k
)->next
)
992 if (rte_better(new, *k
))
1001 /* If routes are not sorted, find the best route and move it on
1002 the first position. There are several optimized cases. */
1004 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
1005 goto do_recalculate
;
1007 if (new && rte_better(new, old_best
))
1009 /* The first case - the new route is cleary optimal,
1010 we link it at the first position */
1012 new->next
= net
->routes
;
1015 else if (old
== old_best
)
1017 /* The second case - the old best route disappeared, we add the
1018 new route (if we have any) to the list (we don't care about
1019 position) and then we elect the new optimal route and relink
1020 that route at the first position and announce it. New optimal
1021 route might be NULL if there is no more routes */
1024 /* Add the new route to the list */
1027 new->next
= net
->routes
;
1031 /* Find a new optimal route (if there is any) */
1034 rte
**bp
= &net
->routes
;
1035 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
1036 if (rte_better(*k
, *bp
))
1042 best
->next
= net
->routes
;
1048 /* The third case - the new route is not better than the old
1049 best route (therefore old_best != NULL) and the old best
1050 route was not removed (therefore old_best == net->routes).
1051 We just link the new route after the old best route. */
1053 ASSERT(net
->routes
!= NULL
);
1054 new->next
= net
->routes
->next
;
1055 net
->routes
->next
= new;
1057 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1063 /* Log the route change */
1064 if (p
->debug
& D_ROUTES
)
1067 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
1070 if (old
!= old_best
)
1071 rte_trace(p
, old
, '>', "removed");
1072 else if (rte_is_ok(net
->routes
))
1073 rte_trace(p
, old
, '>', "removed [replaced]");
1075 rte_trace(p
, old
, '>', "removed [sole]");
1079 /* Propagate the route change */
1080 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, NULL
, NULL
);
1081 if (net
->routes
!= old_best
)
1082 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, NULL
, NULL
);
1083 if (table
->config
->sorted
)
1084 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, NULL
, NULL
, before_old
);
1085 rte_announce(table
, RA_MERGED
, net
, new, old
, net
->routes
, old_best
, NULL
);
1088 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
1089 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
1090 rt_schedule_gc(table
);
1092 if (old_ok
&& p
->rte_remove
)
1093 p
->rte_remove(net
, old
);
1094 if (new_ok
&& p
->rte_insert
)
1095 p
->rte_insert(net
, new);
1098 rte_free_quick(old
);
1101 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
1104 rte_update_lock(void)
1106 rte_update_nest_cnt
++;
1110 rte_update_unlock(void)
1112 if (!--rte_update_nest_cnt
)
1113 lp_flush(rte_update_pool
);
1117 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
1119 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
1121 *dummy
= net
->routes
;
1122 net
->routes
= (*dummy
)->next
;
1127 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
1131 (*dummy
)->next
= net
->routes
;
1132 net
->routes
= *dummy
;
1137 * rte_update - enter a new update to a routing table
1138 * @table: table to be updated
1139 * @ah: pointer to table announce hook
1140 * @net: network node
1141 * @p: protocol submitting the update
1142 * @src: protocol originating the update
1143 * @new: a &rte representing the new route or %NULL for route removal.
1145 * This function is called by the routing protocols whenever they discover
1146 * a new route or wish to update/remove an existing route. The right announcement
1147 * sequence is to build route attributes first (either un-cached with @aflags set
1148 * to zero or a cached one using rta_lookup(); in this case please note that
1149 * you need to increase the use count of the attributes yourself by calling
1150 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1151 * the appropriate data and finally submit the new &rte by calling rte_update().
1153 * @src specifies the protocol that originally created the route and the meaning
1154 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1155 * same value as @new->attrs->proto. @p specifies the protocol that called
1156 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1157 * stores @p in @new->sender;
1159 * When rte_update() gets any route, it automatically validates it (checks,
1160 * whether the network and next hop address are valid IP addresses and also
1161 * whether a normal routing protocol doesn't try to smuggle a host or link
1162 * scope route to the table), converts all protocol dependent attributes stored
1163 * in the &rte to temporary extended attributes, consults import filters of the
1164 * protocol to see if the route should be accepted and/or its attributes modified,
1165 * stores the temporary attributes back to the &rte.
1167 * Now, having a "public" version of the route, we
1168 * automatically find any old route defined by the protocol @src
1169 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1170 * recalculate the optimal route for this destination and finally broadcast
1171 * the change (if any) to all routing protocols by calling rte_announce().
1173 * All memory used for attribute lists and other temporary allocations is taken
1174 * from a special linear pool @rte_update_pool and freed when rte_update()
1179 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
1181 struct proto
*p
= ah
->proto
;
1182 struct proto_stats
*stats
= ah
->stats
;
1183 struct filter
*filter
= ah
->in_filter
;
1184 ea_list
*tmpa
= NULL
;
1192 stats
->imp_updates_received
++;
1193 if (!rte_validate(new))
1195 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1196 stats
->imp_updates_invalid
++;
1200 if (filter
== FILTER_REJECT
)
1202 stats
->imp_updates_filtered
++;
1203 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1205 if (! ah
->in_keep_filtered
)
1208 /* new is a private copy, i could modify it */
1209 new->flags
|= REF_FILTERED
;
1213 tmpa
= make_tmp_attrs(new, rte_update_pool
);
1214 if (filter
&& (filter
!= FILTER_REJECT
))
1216 ea_list
*old_tmpa
= tmpa
;
1217 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
1220 stats
->imp_updates_filtered
++;
1221 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1223 if (! ah
->in_keep_filtered
)
1226 new->flags
|= REF_FILTERED
;
1228 if (tmpa
!= old_tmpa
&& src
->proto
->store_tmp_attrs
)
1229 src
->proto
->store_tmp_attrs(new, tmpa
);
1232 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1233 new->attrs
= rta_lookup(new->attrs
);
1234 new->flags
|= REF_COW
;
1238 stats
->imp_withdraws_received
++;
1242 stats
->imp_withdraws_ignored
++;
1243 rte_update_unlock();
1249 rte_hide_dummy_routes(net
, &dummy
);
1250 rte_recalculate(ah
, net
, new, src
);
1251 rte_unhide_dummy_routes(net
, &dummy
);
1252 rte_update_unlock();
1261 /* Independent call to rte_announce(), used from next hop
1262 recalculation, outside of rte_update(). new must be non-NULL */
1264 rte_announce_i(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
1265 rte
*new_best
, rte
*old_best
)
1268 rte_announce(tab
, type
, net
, new, old
, new_best
, old_best
, NULL
);
1269 rte_update_unlock();
1273 rte_discard(rtable
*t
, rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1276 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1277 rte_update_unlock();
1280 /* Check rtable for best route to given net whether it would be exported do p */
1282 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1284 net
*n
= net_find(t
, prefix
, pxlen
);
1285 rte
*rt
= n
? n
->routes
: NULL
;
1287 if (!rte_is_valid(rt
))
1292 /* Rest is stripped down export_filter() */
1293 ea_list
*tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
1294 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1295 if (v
== RIC_PROCESS
)
1296 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
1298 /* Discard temporary rte */
1299 if (rt
!= n
->routes
)
1302 rte_update_unlock();
1309 * rt_refresh_begin - start a refresh cycle
1310 * @t: related routing table
1311 * @ah: related announce hook
1313 * This function starts a refresh cycle for given routing table and announce
1314 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1315 * routes to the routing table (by rte_update()). After that, all protocol
1316 * routes (more precisely routes with @ah as @sender) not sent during the
1317 * refresh cycle but still in the table from the past are pruned. This is
1318 * implemented by marking all related routes as stale by REF_STALE flag in
1319 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1320 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1323 rt_refresh_begin(rtable
*t
, struct announce_hook
*ah
)
1328 FIB_WALK(&t
->fib
, fn
)
1331 for (e
= n
->routes
; e
; e
= e
->next
)
1332 if (e
->sender
== ah
)
1333 e
->flags
|= REF_STALE
;
1339 * rt_refresh_end - end a refresh cycle
1340 * @t: related routing table
1341 * @ah: related announce hook
1343 * This function starts a refresh cycle for given routing table and announce
1344 * hook. See rt_refresh_begin() for description of refresh cycles.
1347 rt_refresh_end(rtable
*t
, struct announce_hook
*ah
)
1353 FIB_WALK(&t
->fib
, fn
)
1356 for (e
= n
->routes
; e
; e
= e
->next
)
1357 if ((e
->sender
== ah
) && (e
->flags
& REF_STALE
))
1359 e
->flags
|= REF_DISCARD
;
1366 rt_schedule_prune(t
);
1371 * rte_dump - dump a route
1372 * @e: &rte to be dumped
1374 * This functions dumps contents of a &rte to debug output.
1380 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1381 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1383 if (e
->attrs
->src
->proto
->proto
->dump_attrs
)
1384 e
->attrs
->src
->proto
->proto
->dump_attrs(e
);
1389 * rt_dump - dump a routing table
1390 * @t: routing table to be dumped
1392 * This function dumps contents of a given routing table to debug output.
1399 struct announce_hook
*a
;
1401 debug("Dump of routing table <%s>\n", t
->name
);
1405 FIB_WALK(&t
->fib
, fn
)
1408 for(e
=n
->routes
; e
; e
=e
->next
)
1412 WALK_LIST(a
, t
->hooks
)
1413 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1418 * rt_dump_all - dump all routing tables
1420 * This function dumps contents of all routing tables to debug output.
1427 WALK_LIST(t
, routing_tables
)
1432 rt_schedule_prune(rtable
*tab
)
1434 rt_mark_for_prune(tab
);
1435 ev_schedule(tab
->rt_event
);
1439 rt_schedule_gc(rtable
*tab
)
1441 if (tab
->gc_scheduled
)
1444 tab
->gc_scheduled
= 1;
1445 ev_schedule(tab
->rt_event
);
1449 rt_schedule_hcu(rtable
*tab
)
1451 if (tab
->hcu_scheduled
)
1454 tab
->hcu_scheduled
= 1;
1455 ev_schedule(tab
->rt_event
);
1459 rt_schedule_nhu(rtable
*tab
)
1461 if (tab
->nhu_state
== 0)
1462 ev_schedule(tab
->rt_event
);
1464 /* state change 0->1, 2->3 */
1465 tab
->nhu_state
|= 1;
1470 rt_prune_nets(rtable
*tab
)
1472 struct fib_iterator fit
;
1473 int ncnt
= 0, ndel
= 0;
1476 fib_check(&tab
->fib
);
1479 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1481 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1485 if (!n
->routes
) /* Orphaned FIB entry */
1487 FIB_ITERATE_PUT(&fit
, f
);
1488 fib_delete(&tab
->fib
, f
);
1494 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1496 tab
->gc_counter
= 0;
1498 tab
->gc_scheduled
= 0;
1506 if (tab
->hcu_scheduled
)
1507 rt_update_hostcache(tab
);
1510 rt_next_hop_update(tab
);
1512 if (tab
->prune_state
)
1513 if (!rt_prune_table(tab
))
1515 /* Table prune unfinished */
1516 ev_schedule(tab
->rt_event
);
1520 if (tab
->gc_scheduled
)
1523 rt_prune_sources(); // FIXME this should be moved to independent event
1528 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1530 bzero(t
, sizeof(*t
));
1531 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1534 init_list(&t
->hooks
);
1537 t
->rt_event
= ev_new(p
);
1538 t
->rt_event
->hook
= rt_event
;
1539 t
->rt_event
->data
= t
;
1545 * rt_init - initialize routing tables
1547 * This function is called during BIRD startup. It initializes the
1548 * routing table module.
1554 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1555 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1556 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1557 init_list(&routing_tables
);
1562 rt_prune_step(rtable
*tab
, int *limit
)
1564 struct fib_iterator
*fit
= &tab
->prune_fit
;
1566 DBG("Pruning route table %s\n", tab
->name
);
1568 fib_check(&tab
->fib
);
1571 if (tab
->prune_state
== RPS_NONE
)
1574 if (tab
->prune_state
== RPS_SCHEDULED
)
1576 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1577 tab
->prune_state
= RPS_RUNNING
;
1581 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1583 net
*n
= (net
*) fn
;
1587 for (e
=n
->routes
; e
; e
=e
->next
)
1588 if (e
->sender
->proto
->flushing
|| (e
->flags
& REF_DISCARD
))
1592 FIB_ITERATE_PUT(fit
, fn
);
1596 rte_discard(tab
, e
);
1601 if (!n
->routes
) /* Orphaned FIB entry */
1603 FIB_ITERATE_PUT(fit
, fn
);
1604 fib_delete(&tab
->fib
, fn
);
1608 FIB_ITERATE_END(fn
);
1611 fib_check(&tab
->fib
);
1614 tab
->prune_state
= RPS_NONE
;
1619 * rt_prune_table - prune a routing table
1620 * @tab: a routing table for pruning
1622 * This function scans the routing table @tab and removes routes belonging to
1623 * flushing protocols, discarded routes and also stale network entries, in a
1624 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1625 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1626 * protocol flushing loop, but it is called from rt_event() for just one routing
1629 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1630 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1633 rt_prune_table(rtable
*tab
)
1636 return rt_prune_step(tab
, &limit
);
1640 * rt_prune_loop - prune routing tables
1642 * The prune loop scans routing tables and removes routes belonging to flushing
1643 * protocols, discarded routes and also stale network entries. Returns 1 when
1644 * all such routes are pruned. It is a part of the protocol flushing loop.
1652 WALK_LIST(t
, routing_tables
)
1653 if (! rt_prune_step(t
, &limit
))
1660 rt_preconfig(struct config
*c
)
1662 struct symbol
*s
= cf_get_symbol("master");
1664 init_list(&c
->tables
);
1665 c
->master_rtc
= rt_new_table(s
);
1670 * Some functions for handing internal next hop updates
1671 * triggered by rt_schedule_nhu().
1675 rta_next_hop_outdated(rta
*a
)
1677 struct hostentry
*he
= a
->hostentry
;
1683 return a
->dest
!= RTD_UNREACHABLE
;
1685 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1686 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1687 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1691 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1694 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1697 a
->igp_metric
= he
->igp_metric
;
1698 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1702 rt_next_hop_update_rte(rtable
*tab
, rte
*old
)
1705 memcpy(&a
, old
->attrs
, sizeof(rta
));
1706 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1709 rte
*e
= sl_alloc(rte_slab
);
1710 memcpy(e
, old
, sizeof(rte
));
1711 e
->attrs
= rta_lookup(&a
);
1717 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1719 rte
**k
, *e
, *new, *old_best
, **new_best
;
1721 int free_old_best
= 0;
1723 old_best
= n
->routes
;
1727 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1728 if (rta_next_hop_outdated(e
->attrs
))
1730 new = rt_next_hop_update_rte(tab
, e
);
1733 rte_announce_i(tab
, RA_ANY
, n
, new, e
, NULL
, NULL
);
1734 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1736 /* Call a pre-comparison hook */
1737 /* Not really an efficient way to compute this */
1738 if (e
->attrs
->src
->proto
->rte_recalculate
)
1739 e
->attrs
->src
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1743 else /* Freeing of the old best rte is postponed */
1753 /* Find the new best route */
1755 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1757 if (!new_best
|| rte_better(e
, *new_best
))
1761 /* Relink the new best route to the first position */
1763 if (new != n
->routes
)
1765 *new_best
= new->next
;
1766 new->next
= n
->routes
;
1770 /* Announce the new best route */
1771 if (new != old_best
)
1773 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
, NULL
, NULL
);
1774 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1777 /* FIXME: Better announcement of merged routes */
1778 rte_announce_i(tab
, RA_MERGED
, n
, new, old_best
, new, old_best
);
1781 rte_free_quick(old_best
);
1787 rt_next_hop_update(rtable
*tab
)
1789 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1792 if (tab
->nhu_state
== 0)
1795 if (tab
->nhu_state
== 1)
1797 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1801 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1805 FIB_ITERATE_PUT(fit
, fn
);
1806 ev_schedule(tab
->rt_event
);
1809 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1811 FIB_ITERATE_END(fn
);
1813 /* state change 2->0, 3->1 */
1814 tab
->nhu_state
&= 1;
1816 if (tab
->nhu_state
> 0)
1817 ev_schedule(tab
->rt_event
);
1821 struct rtable_config
*
1822 rt_new_table(struct symbol
*s
)
1824 /* Hack that allows to 'redefine' the master table */
1825 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1828 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1830 cf_define_symbol(s
, SYM_TABLE
, c
);
1832 add_tail(&new_config
->tables
, &c
->n
);
1833 c
->gc_max_ops
= 1000;
1839 * rt_lock_table - lock a routing table
1840 * @r: routing table to be locked
1842 * Lock a routing table, because it's in use by a protocol,
1843 * preventing it from being freed when it gets undefined in a new
1847 rt_lock_table(rtable
*r
)
1853 * rt_unlock_table - unlock a routing table
1854 * @r: routing table to be unlocked
1856 * Unlock a routing table formerly locked by rt_lock_table(),
1857 * that is decrease its use count and delete it if it's scheduled
1858 * for deletion by configuration changes.
1861 rt_unlock_table(rtable
*r
)
1863 if (!--r
->use_count
&& r
->deleted
)
1865 struct config
*conf
= r
->deleted
;
1866 DBG("Deleting routing table %s\n", r
->name
);
1867 r
->config
->table
= NULL
;
1869 rt_free_hostcache(r
);
1874 config_del_obstacle(conf
);
1879 * rt_commit - commit new routing table configuration
1880 * @new: new configuration
1881 * @old: original configuration or %NULL if it's boot time config
1883 * Scan differences between @old and @new configuration and modify
1884 * the routing tables according to these changes. If @new defines a
1885 * previously unknown table, create it, if it omits a table existing
1886 * in @old, schedule it for deletion (it gets deleted when all protocols
1887 * disconnect from it by calling rt_unlock_table()), if it exists
1888 * in both configurations, leave it unchanged.
1891 rt_commit(struct config
*new, struct config
*old
)
1893 struct rtable_config
*o
, *r
;
1895 DBG("rt_commit:\n");
1898 WALK_LIST(o
, old
->tables
)
1900 rtable
*ot
= o
->table
;
1903 struct symbol
*sym
= cf_find_symbol(new, o
->name
);
1904 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1906 DBG("\t%s: same\n", o
->name
);
1911 if (o
->sorted
!= r
->sorted
)
1912 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1916 DBG("\t%s: deleted\n", o
->name
);
1918 config_add_obstacle(old
);
1920 rt_unlock_table(ot
);
1926 WALK_LIST(r
, new->tables
)
1929 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1930 DBG("\t%s: created\n", r
->name
);
1931 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1932 add_tail(&routing_tables
, &t
->n
);
1939 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1942 if (type
== RA_ACCEPTED
)
1943 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, p
->refeeding
? 2 : 1);
1944 else if (type
== RA_MERGED
)
1945 rt_notify_merged(h
, n
, NULL
, NULL
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1947 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1948 rte_update_unlock();
1952 * rt_feed_baby - advertise routes to a new protocol
1953 * @p: protocol to be fed
1955 * This function performs one pass of advertisement of routes to a newly
1956 * initialized protocol. It's called by the protocol code as long as it
1957 * has something to do. (We avoid transferring all the routes in single
1958 * pass in order not to monopolize CPU time.)
1961 rt_feed_baby(struct proto
*p
)
1963 struct announce_hook
*h
;
1964 struct fib_iterator
*fit
;
1967 if (!p
->feed_ahook
) /* Need to initialize first */
1971 DBG("Announcing routes to new protocol %s\n", p
->name
);
1972 p
->feed_ahook
= p
->ahooks
;
1973 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1976 fit
= p
->feed_iterator
;
1980 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1982 net
*n
= (net
*) fn
;
1986 FIB_ITERATE_PUT(fit
, fn
);
1990 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1992 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
1993 (p
->accept_ra_types
== RA_ACCEPTED
) ||
1994 (p
->accept_ra_types
== RA_MERGED
))
1995 if (rte_is_valid(e
))
1997 if (p
->export_state
!= ES_FEEDING
)
1998 return 1; /* In the meantime, the protocol fell down. */
2000 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
2004 if (p
->accept_ra_types
== RA_ANY
)
2005 for(e
= n
->routes
; e
; e
= e
->next
)
2007 if (p
->export_state
!= ES_FEEDING
)
2008 return 1; /* In the meantime, the protocol fell down. */
2010 if (!rte_is_valid(e
))
2013 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
2017 FIB_ITERATE_END(fn
);
2018 p
->feed_ahook
= h
->next
;
2021 mb_free(p
->feed_iterator
);
2022 p
->feed_iterator
= NULL
;
2028 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
2033 * rt_feed_baby_abort - abort protocol feeding
2036 * This function is called by the protocol code when the protocol
2037 * stops or ceases to exist before the last iteration of rt_feed_baby()
2041 rt_feed_baby_abort(struct proto
*p
)
2045 /* Unlink the iterator and exit */
2046 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
2047 p
->feed_ahook
= NULL
;
2052 static inline unsigned
2055 uintptr_t p
= (uintptr_t) ptr
;
2056 return p
^ (p
<< 8) ^ (p
>> 16);
2059 static inline unsigned
2060 hc_hash(ip_addr a
, rtable
*dep
)
2062 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
2066 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
2068 uint k
= he
->hash_key
>> hc
->hash_shift
;
2069 he
->next
= hc
->hash_table
[k
];
2070 hc
->hash_table
[k
] = he
;
2074 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
2076 struct hostentry
**hep
;
2077 uint k
= he
->hash_key
>> hc
->hash_shift
;
2079 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
2083 #define HC_DEF_ORDER 10
2084 #define HC_HI_MARK *4
2085 #define HC_HI_STEP 2
2086 #define HC_HI_ORDER 16 /* Must be at most 16 */
2087 #define HC_LO_MARK /5
2088 #define HC_LO_STEP 2
2089 #define HC_LO_ORDER 10
2092 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
2094 unsigned hsize
= 1 << order
;
2095 hc
->hash_order
= order
;
2096 hc
->hash_shift
= 16 - order
;
2097 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0 : (hsize HC_HI_MARK
);
2098 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0 : (hsize HC_LO_MARK
);
2100 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
2104 hc_resize(struct hostcache
*hc
, unsigned new_order
)
2106 unsigned old_size
= 1 << hc
->hash_order
;
2107 struct hostentry
**old_table
= hc
->hash_table
;
2108 struct hostentry
*he
, *hen
;
2111 hc_alloc_table(hc
, new_order
);
2112 for (i
= 0; i
< old_size
; i
++)
2113 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
2121 static struct hostentry
*
2122 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
2124 struct hostentry
*he
= sl_alloc(hc
->slab
);
2133 add_tail(&hc
->hostentries
, &he
->ln
);
2137 if (hc
->hash_items
> hc
->hash_max
)
2138 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
2144 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
2150 sl_free(hc
->slab
, he
);
2153 if (hc
->hash_items
< hc
->hash_min
)
2154 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
2158 rt_init_hostcache(rtable
*tab
)
2160 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
2161 init_list(&hc
->hostentries
);
2164 hc_alloc_table(hc
, HC_DEF_ORDER
);
2165 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
2167 hc
->lp
= lp_new(rt_table_pool
, 1008);
2168 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2170 tab
->hostcache
= hc
;
2174 rt_free_hostcache(rtable
*tab
)
2176 struct hostcache
*hc
= tab
->hostcache
;
2179 WALK_LIST(n
, hc
->hostentries
)
2181 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
2185 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
2190 mb_free(hc
->hash_table
);
2195 rt_notify_hostcache(rtable
*tab
, net
*net
)
2197 struct hostcache
*hc
= tab
->hostcache
;
2199 if (tab
->hcu_scheduled
)
2202 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
2203 rt_schedule_hcu(tab
);
2207 if_local_addr(ip_addr a
, struct iface
*i
)
2211 WALK_LIST(b
, i
->addrs
)
2212 if (ipa_equal(a
, b
->ip
))
2219 rt_get_igp_metric(rte
*rt
)
2221 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
2229 if ((a
->source
== RTS_OSPF
) ||
2230 (a
->source
== RTS_OSPF_IA
) ||
2231 (a
->source
== RTS_OSPF_EXT1
))
2232 return rt
->u
.ospf
.metric1
;
2236 if (a
->source
== RTS_RIP
)
2237 return rt
->u
.rip
.metric
;
2241 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
2244 return IGP_METRIC_UNKNOWN
;
2248 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
2250 rta
*old_src
= he
->src
;
2253 /* Reset the hostentry */
2256 he
->dest
= RTD_UNREACHABLE
;
2259 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
2268 /* Recursive route should not depend on another recursive route */
2269 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
2270 he
->addr
, n
->n
.prefix
, pxlen
);
2274 if (a
->dest
== RTD_DEVICE
)
2276 if (if_local_addr(he
->addr
, a
->iface
))
2278 /* The host address is a local address, this is not valid */
2279 log(L_WARN
"Next hop address %I is a local address of iface %s",
2280 he
->addr
, a
->iface
->name
);
2284 /* The host is directly reachable, use link as a gateway */
2286 he
->dest
= RTD_ROUTER
;
2290 /* The host is reachable through some route entry */
2295 he
->src
= rta_clone(a
);
2296 he
->igp_metric
= rt_get_igp_metric(e
);
2300 /* Add a prefix range to the trie */
2301 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
2304 return old_src
!= he
->src
;
2308 rt_update_hostcache(rtable
*tab
)
2310 struct hostcache
*hc
= tab
->hostcache
;
2311 struct hostentry
*he
;
2314 /* Reset the trie */
2316 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2318 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
2320 he
= SKIP_BACK(struct hostentry
, ln
, n
);
2323 hc_delete_hostentry(hc
, he
);
2327 if (rt_update_hostentry(tab
, he
))
2328 rt_schedule_nhu(he
->tab
);
2331 tab
->hcu_scheduled
= 0;
2334 static struct hostentry
*
2335 rt_get_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2337 struct hostentry
*he
;
2339 if (!tab
->hostcache
)
2340 rt_init_hostcache(tab
);
2342 uint k
= hc_hash(a
, dep
);
2343 struct hostcache
*hc
= tab
->hostcache
;
2344 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2345 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2348 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
2349 rt_update_hostentry(tab
, he
);
2354 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
2356 rta_apply_hostentry(a
, rt_get_hostentry(tab
, *gw
, *ll
, dep
));
2365 rt_format_via(rte
*e
)
2369 /* Max text length w/o IP addr and interface name is 16 */
2370 static byte via
[STD_ADDRESS_P_LENGTH
+sizeof(a
->iface
->name
)+16];
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
, "???");
2386 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2388 byte from
[STD_ADDRESS_P_LENGTH
+8];
2389 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2391 int primary
= (e
->net
->routes
== e
);
2392 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2393 void (*get_route_info
)(struct rte
*, byte
*buf
, struct ea_list
*attrs
);
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
, rt_format_via(e
), 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
)