]>
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
);
59 static inline void rt_schedule_gc(rtable
*tab
);
61 /* Like fib_route(), but skips empty net entries */
63 net_route(rtable
*tab
, ip_addr a
, int len
)
70 a0
= ipa_and(a
, ipa_mkmask(len
));
71 n
= fib_find(&tab
->fib
, &a0
, len
);
72 if (n
&& rte_is_valid(n
->routes
))
80 rte_init(struct fib_node
*N
)
89 * rte_find - find a route
93 * The rte_find() function returns a route for destination @net
94 * which belongs has been defined by protocol @p.
97 rte_find(net
*net
, struct proto
*p
)
101 while (e
&& e
->attrs
->proto
!= p
)
107 * rte_get_temp - get a temporary &rte
108 * @a: attributes to assign to the new route (a &rta; in case it's
109 * un-cached, rte_update() will create a cached copy automatically)
111 * Create a temporary &rte and bind it with the attributes @a.
112 * Also set route preference to the default preference set for
118 rte
*e
= sl_alloc(rte_slab
);
122 e
->pref
= a
->proto
->preference
;
129 rte
*e
= sl_alloc(rte_slab
);
131 memcpy(e
, r
, sizeof(rte
));
132 e
->attrs
= rta_clone(r
->attrs
);
137 static int /* Actually better or at least as good as */
138 rte_better(rte
*new, rte
*old
)
140 int (*better
)(rte
*, rte
*);
142 if (!rte_is_valid(old
))
144 if (!rte_is_valid(new))
147 if (new->pref
> old
->pref
)
149 if (new->pref
< old
->pref
)
151 if (new->attrs
->proto
->proto
!= old
->attrs
->proto
->proto
)
154 * If the user has configured protocol preferences, so that two different protocols
155 * have the same preference, try to break the tie by comparing addresses. Not too
156 * useful, but keeps the ordering of routes unambiguous.
158 return new->attrs
->proto
->proto
> old
->attrs
->proto
->proto
;
160 if (better
= new->attrs
->proto
->rte_better
)
161 return better(new, old
);
166 rte_trace(struct proto
*p
, rte
*e
, int dir
, char *msg
)
168 byte via
[STD_ADDRESS_P_LENGTH
+32];
170 rt_format_via(e
, via
);
171 log(L_TRACE
"%s %c %s %I/%d %s", p
->name
, dir
, msg
, e
->net
->n
.prefix
, e
->net
->n
.pxlen
, via
);
175 rte_trace_in(unsigned int flag
, struct proto
*p
, rte
*e
, char *msg
)
178 rte_trace(p
, e
, '>', msg
);
182 rte_trace_out(unsigned int flag
, struct proto
*p
, rte
*e
, char *msg
)
185 rte_trace(p
, e
, '<', msg
);
189 export_filter(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
191 struct proto
*p
= ah
->proto
;
192 struct filter
*filter
= ah
->out_filter
;
193 struct proto_stats
*stats
= ah
->stats
;
194 ea_list
*tmpb
= NULL
;
201 /* If called does not care for eattrs, we prepare one internally */
204 struct proto
*src
= rt
->attrs
->proto
;
205 tmpb
= src
->make_tmp_attrs
? src
->make_tmp_attrs(rt
, rte_update_pool
) : NULL
;
209 v
= p
->import_control
? p
->import_control(p
, &rt
, tmpa
, rte_update_pool
) : 0;
215 stats
->exp_updates_rejected
++;
217 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
223 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
227 v
= filter
&& ((filter
== FILTER_REJECT
) ||
228 (f_run(filter
, &rt
, tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
));
234 stats
->exp_updates_filtered
++;
235 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
245 /* Discard temporary rte */
252 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
254 struct proto
*p
= ah
->proto
;
255 struct proto_stats
*stats
= ah
->stats
;
259 * First, apply export limit.
261 * Export route limits has several problems. Because exp_routes
262 * counter is reset before refeed, we don't really know whether
263 * limit is breached and whether the update is new or not. Therefore
264 * the number of really exported routes may exceed the limit
265 * temporarily (routes exported before and new routes in refeed).
267 * Minor advantage is that if the limit is decreased and refeed is
268 * requested, the number of exported routes really decrease.
270 * Second problem is that with export limits, we don't know whether
271 * old was really exported (it might be blocked by limit). When a
272 * withdraw is exported, we announce it even when the previous
273 * update was blocked. This is not a big issue, but the same problem
274 * is in updating exp_routes counter. Therefore, to be consistent in
275 * increases and decreases of exp_routes, we count exported routes
276 * regardless of blocking by limits.
278 * Similar problem is in handling updates - when a new route is
279 * received and blocking is active, the route would be blocked, but
280 * when an update for the route will be received later, the update
281 * would be propagated (as old != NULL). Therefore, we have to block
282 * also non-new updates (contrary to import blocking).
285 struct proto_limit
*l
= ah
->out_limit
;
288 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
289 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
291 if (l
->state
== PLS_BLOCKED
)
293 stats
->exp_routes
++; /* see note above */
294 stats
->exp_updates_rejected
++;
295 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
305 stats
->exp_updates_accepted
++;
307 stats
->exp_withdraws_accepted
++;
309 /* Hack: We do not decrease exp_routes during refeed, we instead
310 reset exp_routes at the start of refeed. */
316 if (p
->debug
& D_ROUTES
)
319 rte_trace_out(D_ROUTES
, p
, new, "replaced");
321 rte_trace_out(D_ROUTES
, p
, new, "added");
323 rte_trace_out(D_ROUTES
, p
, old
, "removed");
326 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
332 t
->next
= new->attrs
->eattrs
;
333 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
337 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
341 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
343 // struct proto *p = ah->proto;
344 struct proto_stats
*stats
= ah
->stats
;
346 rte
*new_free
= NULL
;
347 rte
*old_free
= NULL
;
350 stats
->exp_updates_received
++;
352 stats
->exp_withdraws_received
++;
355 * This is a tricky part - we don't know whether route 'old' was
356 * exported to protocol 'p' or was filtered by the export filter.
357 * We try to run the export filter to know this to have a correct
358 * value in 'old' argument of rte_update (and proper filter value)
360 * FIXME - this is broken because 'configure soft' may change
361 * filters but keep routes. Refeed is expected to be called after
362 * change of the filters and with old == new, therefore we do not
363 * even try to run the filter on an old route, This may lead to
364 * 'spurious withdraws' but ensure that there are no 'missing
367 * This is not completely safe as there is a window between
368 * reconfiguration and the end of refeed - if a newly filtered
369 * route disappears during this period, proper withdraw is not
370 * sent (because old would be also filtered) and the route is
371 * not refeeded (because it disappeared before that).
375 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
378 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
380 /* FIXME - This is broken because of incorrect 'old' value (see above) */
384 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
386 /* Discard temporary rte's */
394 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
,
395 ea_list
*tmpa
, int feed
)
397 // struct proto *p = ah->proto;
398 struct proto_stats
*stats
= ah
->stats
;
400 rte
*new_best
= NULL
;
401 rte
*old_best
= NULL
;
402 rte
*new_free
= NULL
;
403 rte
*old_free
= NULL
;
406 /* Used to track whether we met old_changed position. If before_old is NULL
407 old_changed was the first and we met it implicitly before current best route. */
408 int old_meet
= old_changed
&& !before_old
;
410 /* Note that before_old is either NULL or valid (not rejected) route.
411 If old_changed is valid, before_old have to be too. If old changed route
412 was not valid, caller must use NULL for both old_changed and before_old. */
415 stats
->exp_updates_received
++;
417 stats
->exp_withdraws_received
++;
419 /* First, find the new_best route - first accepted by filters */
420 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
422 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
425 /* Note if we walked around the position of old_changed route */
431 * Second, handle the feed case. That means we do not care for
432 * old_best. It is NULL for feed, and the new_best for refeed.
433 * For refeed, there is a hack similar to one in rt_notify_basic()
434 * to ensure withdraws in case of changed filters
438 if (feed
== 2) /* refeed */
439 old_best
= new_best
? new_best
:
440 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
444 if (!new_best
&& !old_best
)
451 * Now, we find the old_best route. Generally, it is the same as the
452 * new_best, unless new_best is the same as new_changed or
453 * old_changed is accepted before new_best.
455 * There are four cases:
457 * - We would find and accept old_changed before new_best, therefore
458 * old_changed is old_best. In remaining cases we suppose this
461 * - We found no new_best, therefore there is also no old_best and
462 * we ignore this withdraw.
464 * - We found new_best different than new_changed, therefore
465 * old_best is the same as new_best and we ignore this update.
467 * - We found new_best the same as new_changed, therefore it cannot
468 * be old_best and we have to continue search for old_best.
473 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
480 /* Third case, we use r instead of new_best, because export_filter() could change it */
481 if (r
!= new_changed
)
489 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
491 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
495 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
499 /* Implicitly, old_best is NULL and new_best is non-NULL */
502 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
504 /* Discard temporary rte's */
512 * rte_announce - announce a routing table change
513 * @tab: table the route has been added to
514 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
515 * @net: network in question
516 * @new: the new route to be announced
517 * @old: the previous route for the same network
518 * @tmpa: a list of temporary attributes belonging to the new route
520 * This function gets a routing table update and announces it
521 * to all protocols that acccepts given type of route announcement
522 * and are connected to the same table by their announcement hooks.
524 * Route announcement of type RA_OPTIMAL si generated when optimal
525 * route (in routing table @tab) changes. In that case @old stores the
528 * Route announcement of type RA_ANY si generated when any route (in
529 * routing table @tab) changes In that case @old stores the old route
530 * from the same protocol.
532 * For each appropriate protocol, we first call its import_control()
533 * hook which performs basic checks on the route (each protocol has a
534 * right to veto or force accept of the route before any filter is
535 * asked) and adds default values of attributes specific to the new
536 * protocol (metrics, tags etc.). Then it consults the protocol's
537 * export filter and if it accepts the route, the rt_notify() hook of
538 * the protocol gets called.
541 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
, rte
*before_old
, ea_list
*tmpa
)
543 if (!rte_is_valid(old
))
544 old
= before_old
= NULL
;
546 if (!rte_is_valid(new))
552 if (type
== RA_OPTIMAL
)
555 new->attrs
->proto
->stats
.pref_routes
++;
557 old
->attrs
->proto
->stats
.pref_routes
--;
560 rt_notify_hostcache(tab
, net
);
563 struct announce_hook
*a
;
564 WALK_LIST(a
, tab
->hooks
)
566 ASSERT(a
->proto
->core_state
== FS_HAPPY
|| a
->proto
->core_state
== FS_FEEDING
);
567 if (a
->proto
->accept_ra_types
== type
)
568 if (type
== RA_ACCEPTED
)
569 rt_notify_accepted(a
, net
, new, old
, before_old
, tmpa
, 0);
571 rt_notify_basic(a
, net
, new, old
, tmpa
, 0);
581 if ((n
->n
.pxlen
> BITS_PER_IP_ADDRESS
) || !ip_is_prefix(n
->n
.prefix
,n
->n
.pxlen
))
583 log(L_WARN
"Ignoring bogus prefix %I/%d received via %s",
584 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
588 c
= ipa_classify_net(n
->n
.prefix
);
589 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
591 log(L_WARN
"Ignoring bogus route %I/%d received via %s",
592 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
600 * rte_free - delete a &rte
601 * @e: &rte to be deleted
603 * rte_free() deletes the given &rte from the routing table it's linked to.
608 if (e
->attrs
->aflags
& RTAF_CACHED
)
610 sl_free(rte_slab
, e
);
614 rte_free_quick(rte
*e
)
617 sl_free(rte_slab
, e
);
621 rte_same(rte
*x
, rte
*y
)
624 x
->attrs
== y
->attrs
&&
625 x
->flags
== y
->flags
&&
626 x
->pflags
== y
->pflags
&&
627 x
->pref
== y
->pref
&&
628 (!x
->attrs
->proto
->rte_same
|| x
->attrs
->proto
->rte_same(x
, y
));
631 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
634 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, ea_list
*tmpa
, struct proto
*src
)
636 struct proto
*p
= ah
->proto
;
637 struct rtable
*table
= ah
->table
;
638 struct proto_stats
*stats
= ah
->stats
;
639 rte
*before_old
= NULL
;
640 rte
*old_best
= net
->routes
;
644 k
= &net
->routes
; /* Find and remove original route from the same protocol */
647 if (old
->attrs
->proto
== src
)
649 /* If there is the same route in the routing table but from
650 * a different sender, then there are two paths from the
651 * source protocol to this routing table through transparent
652 * pipes, which is not allowed.
654 * We log that and ignore the route. If it is withdraw, we
655 * ignore it completely (there might be 'spurious withdraws',
656 * see FIXME in do_rte_announce())
658 if (old
->sender
->proto
!= p
)
662 log(L_ERR
"Pipe collision detected when sending %I/%d to table %s",
663 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
669 if (new && rte_same(old
, new))
671 /* No changes, ignore the new route */
673 if (!rte_is_filtered(new))
675 stats
->imp_updates_ignored
++;
676 rte_trace_in(D_ROUTES
, p
, new, "ignored");
681 /* lastmod is used internally by RIP as the last time
682 when the route was received. */
683 if (src
->proto
== &proto_rip
)
700 stats
->imp_withdraws_ignored
++;
704 int new_ok
= rte_is_ok(new);
705 int old_ok
= rte_is_ok(old
);
707 struct proto_limit
*l
= ah
->rx_limit
;
708 if (l
&& !old
&& new)
710 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
712 if (all_routes
>= l
->limit
)
713 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
715 if (l
->state
== PLS_BLOCKED
)
717 /* In receive limit the situation is simple, old is NULL so
718 we just free new and exit like nothing happened */
720 stats
->imp_updates_ignored
++;
721 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
728 if (l
&& !old_ok
&& new_ok
)
730 if (stats
->imp_routes
>= l
->limit
)
731 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
733 if (l
->state
== PLS_BLOCKED
)
735 /* In import limit the situation is more complicated. We
736 shouldn't just drop the route, we should handle it like
737 it was filtered. We also have to continue the route
738 processing if old or new is non-NULL, but we should exit
739 if both are NULL as this case is probably assumed to be
742 stats
->imp_updates_ignored
++;
743 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
745 if (ah
->in_keep_filtered
)
746 new->flags
|= REF_FILTERED
;
748 { rte_free_quick(new); new = NULL
; }
750 /* Note that old && !new could be possible when
751 ah->in_keep_filtered changed in the recent past. */
762 stats
->imp_updates_accepted
++;
764 stats
->imp_withdraws_accepted
++;
766 stats
->imp_withdraws_ignored
++;
771 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
773 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
775 if (table
->config
->sorted
)
777 /* If routes are sorted, just insert new route to appropriate position */
780 if (before_old
&& !rte_better(new, before_old
))
781 k
= &before_old
->next
;
785 for (; *k
; k
=&(*k
)->next
)
786 if (rte_better(new, *k
))
795 /* If routes are not sorted, find the best route and move it on
796 the first position. There are several optimized cases. */
798 if (src
->rte_recalculate
&& src
->rte_recalculate(table
, net
, new, old
, old_best
))
801 if (new && rte_better(new, old_best
))
803 /* The first case - the new route is cleary optimal,
804 we link it at the first position */
806 new->next
= net
->routes
;
809 else if (old
== old_best
)
811 /* The second case - the old best route disappeared, we add the
812 new route (if we have any) to the list (we don't care about
813 position) and then we elect the new optimal route and relink
814 that route at the first position and announce it. New optimal
815 route might be NULL if there is no more routes */
818 /* Add the new route to the list */
821 new->next
= net
->routes
;
825 /* Find a new optimal route (if there is any) */
828 rte
**bp
= &net
->routes
;
829 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
830 if (rte_better(*k
, *bp
))
836 best
->next
= net
->routes
;
842 /* The third case - the new route is not better than the old
843 best route (therefore old_best != NULL) and the old best
844 route was not removed (therefore old_best == net->routes).
845 We just link the new route after the old best route. */
847 ASSERT(net
->routes
!= NULL
);
848 new->next
= net
->routes
->next
;
849 net
->routes
->next
= new;
851 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
857 /* Log the route change */
858 if (p
->debug
& D_ROUTES
)
861 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
865 rte_trace(p
, old
, '>', "removed");
866 else if (rte_is_ok(net
->routes
))
867 rte_trace(p
, old
, '>', "removed [replaced]");
869 rte_trace(p
, old
, '>', "removed [sole]");
873 /* Propagate the route change */
874 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, tmpa
);
875 if (net
->routes
!= old_best
)
876 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, tmpa
);
877 if (table
->config
->sorted
)
878 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, before_old
, tmpa
);
881 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
882 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
883 rt_schedule_gc(table
);
885 if (old_ok
&& p
->rte_remove
)
886 p
->rte_remove(net
, old
);
887 if (new_ok
&& p
->rte_insert
)
888 p
->rte_insert(net
, new);
894 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
897 rte_update_lock(void)
899 rte_update_nest_cnt
++;
903 rte_update_unlock(void)
905 if (!--rte_update_nest_cnt
)
906 lp_flush(rte_update_pool
);
910 * rte_update - enter a new update to a routing table
911 * @table: table to be updated
912 * @ah: pointer to table announce hook
914 * @p: protocol submitting the update
915 * @src: protocol originating the update
916 * @new: a &rte representing the new route or %NULL for route removal.
918 * This function is called by the routing protocols whenever they discover
919 * a new route or wish to update/remove an existing route. The right announcement
920 * sequence is to build route attributes first (either un-cached with @aflags set
921 * to zero or a cached one using rta_lookup(); in this case please note that
922 * you need to increase the use count of the attributes yourself by calling
923 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
924 * the appropriate data and finally submit the new &rte by calling rte_update().
926 * @src specifies the protocol that originally created the route and the meaning
927 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
928 * same value as @new->attrs->proto. @p specifies the protocol that called
929 * rte_update(). In most cases it is the same protocol as @src. rte_update()
930 * stores @p in @new->sender;
932 * When rte_update() gets any route, it automatically validates it (checks,
933 * whether the network and next hop address are valid IP addresses and also
934 * whether a normal routing protocol doesn't try to smuggle a host or link
935 * scope route to the table), converts all protocol dependent attributes stored
936 * in the &rte to temporary extended attributes, consults import filters of the
937 * protocol to see if the route should be accepted and/or its attributes modified,
938 * stores the temporary attributes back to the &rte.
940 * Now, having a "public" version of the route, we
941 * automatically find any old route defined by the protocol @src
942 * for network @n, replace it by the new one (or removing it if @new is %NULL),
943 * recalculate the optimal route for this destination and finally broadcast
944 * the change (if any) to all routing protocols by calling rte_announce().
946 * All memory used for attribute lists and other temporary allocations is taken
947 * from a special linear pool @rte_update_pool and freed when rte_update()
952 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct proto
*src
)
954 struct proto
*p
= ah
->proto
;
955 struct proto_stats
*stats
= ah
->stats
;
956 struct filter
*filter
= ah
->in_filter
;
957 ea_list
*tmpa
= NULL
;
964 stats
->imp_updates_received
++;
965 if (!rte_validate(new))
967 rte_trace_in(D_FILTERS
, p
, new, "invalid");
968 stats
->imp_updates_invalid
++;
972 if (filter
== FILTER_REJECT
)
974 stats
->imp_updates_filtered
++;
975 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
977 if (! ah
->in_keep_filtered
)
980 /* new is a private copy, i could modify it */
981 new->flags
|= REF_FILTERED
;
985 if (src
->make_tmp_attrs
)
986 tmpa
= src
->make_tmp_attrs(new, rte_update_pool
);
987 if (filter
&& (filter
!= FILTER_REJECT
))
989 ea_list
*old_tmpa
= tmpa
;
990 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
993 stats
->imp_updates_filtered
++;
994 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
996 if (! ah
->in_keep_filtered
)
999 new->flags
|= REF_FILTERED
;
1001 if (tmpa
!= old_tmpa
&& src
->store_tmp_attrs
)
1002 src
->store_tmp_attrs(new, tmpa
);
1006 if (!(new->attrs
->aflags
& RTAF_CACHED
)) /* Need to copy attributes */
1007 new->attrs
= rta_lookup(new->attrs
);
1008 new->flags
|= REF_COW
;
1011 stats
->imp_withdraws_received
++;
1013 rte_recalculate(ah
, net
, new, tmpa
, src
);
1014 rte_update_unlock();
1019 rte_recalculate(ah
, net
, NULL
, NULL
, src
);
1020 rte_update_unlock();
1023 /* Independent call to rte_announce(), used from next hop
1024 recalculation, outside of rte_update(). new must be non-NULL */
1026 rte_announce_i(rtable
*tab
, unsigned type
, net
*n
, rte
*new, rte
*old
)
1032 src
= new->attrs
->proto
;
1033 tmpa
= src
->make_tmp_attrs
? src
->make_tmp_attrs(new, rte_update_pool
) : NULL
;
1034 rte_announce(tab
, type
, n
, new, old
, NULL
, tmpa
);
1035 rte_update_unlock();
1039 rte_discard(rtable
*t
, rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1042 rte_recalculate(old
->sender
, old
->net
, NULL
, NULL
, old
->attrs
->proto
);
1043 rte_update_unlock();
1046 /* Check rtable for best route to given net whether it would be exported do p */
1048 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1050 net
*n
= net_find(t
, prefix
, pxlen
);
1051 rte
*rt
= n
? n
->routes
: NULL
;
1053 if (!rte_is_valid(rt
))
1058 /* Rest is stripped down export_filter() */
1059 struct proto
*src
= rt
->attrs
->proto
;
1060 ea_list
*tmpa
= src
->make_tmp_attrs
? src
->make_tmp_attrs(rt
, rte_update_pool
) : NULL
;
1061 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1062 if (v
== RIC_PROCESS
)
1063 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
1065 /* Discard temporary rte */
1066 if (rt
!= n
->routes
)
1069 rte_update_unlock();
1075 * rte_dump - dump a route
1076 * @e: &rte to be dumped
1078 * This functions dumps contents of a &rte to debug output.
1084 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1085 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1087 if (e
->attrs
->proto
->proto
->dump_attrs
)
1088 e
->attrs
->proto
->proto
->dump_attrs(e
);
1093 * rt_dump - dump a routing table
1094 * @t: routing table to be dumped
1096 * This function dumps contents of a given routing table to debug output.
1103 struct announce_hook
*a
;
1105 debug("Dump of routing table <%s>\n", t
->name
);
1109 FIB_WALK(&t
->fib
, fn
)
1112 for(e
=n
->routes
; e
; e
=e
->next
)
1116 WALK_LIST(a
, t
->hooks
)
1117 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1122 * rt_dump_all - dump all routing tables
1124 * This function dumps contents of all routing tables to debug output.
1131 WALK_LIST(t
, routing_tables
)
1136 rt_schedule_gc(rtable
*tab
)
1138 if (tab
->gc_scheduled
)
1141 tab
->gc_scheduled
= 1;
1142 ev_schedule(tab
->rt_event
);
1146 rt_schedule_hcu(rtable
*tab
)
1148 if (tab
->hcu_scheduled
)
1151 tab
->hcu_scheduled
= 1;
1152 ev_schedule(tab
->rt_event
);
1156 rt_schedule_nhu(rtable
*tab
)
1158 if (tab
->nhu_state
== 0)
1159 ev_schedule(tab
->rt_event
);
1161 /* state change 0->1, 2->3 */
1162 tab
->nhu_state
|= 1;
1166 rt_prune_nets(rtable
*tab
)
1168 struct fib_iterator fit
;
1169 int ncnt
= 0, ndel
= 0;
1172 fib_check(&tab
->fib
);
1175 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1177 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1181 if (!n
->routes
) /* Orphaned FIB entry */
1183 FIB_ITERATE_PUT(&fit
, f
);
1184 fib_delete(&tab
->fib
, f
);
1190 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1192 tab
->gc_counter
= 0;
1194 tab
->gc_scheduled
= 0;
1202 if (tab
->hcu_scheduled
)
1203 rt_update_hostcache(tab
);
1206 rt_next_hop_update(tab
);
1208 if (tab
->gc_scheduled
)
1213 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1215 bzero(t
, sizeof(*t
));
1216 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1219 init_list(&t
->hooks
);
1222 t
->rt_event
= ev_new(p
);
1223 t
->rt_event
->hook
= rt_event
;
1224 t
->rt_event
->data
= t
;
1230 * rt_init - initialize routing tables
1232 * This function is called during BIRD startup. It initializes the
1233 * routing table module.
1239 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1240 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1241 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1242 init_list(&routing_tables
);
1246 /* Called from proto_schedule_flush_loop() only,
1247 ensuring that all prune states are zero */
1249 rt_schedule_prune_all(void)
1253 WALK_LIST(t
, routing_tables
)
1258 rt_prune_step(rtable
*tab
, int *max_feed
)
1260 struct fib_iterator
*fit
= &tab
->prune_fit
;
1262 DBG("Pruning route table %s\n", tab
->name
);
1264 fib_check(&tab
->fib
);
1267 if (tab
->prune_state
== 0)
1270 if (tab
->prune_state
== 1)
1272 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1273 tab
->prune_state
= 2;
1277 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1279 net
*n
= (net
*) fn
;
1283 for (e
=n
->routes
; e
; e
=e
->next
)
1284 if (e
->sender
->proto
->core_state
!= FS_HAPPY
&&
1285 e
->sender
->proto
->core_state
!= FS_FEEDING
)
1289 FIB_ITERATE_PUT(fit
, fn
);
1293 rte_discard(tab
, e
);
1298 if (!n
->routes
) /* Orphaned FIB entry */
1300 FIB_ITERATE_PUT(fit
, fn
);
1301 fib_delete(&tab
->fib
, fn
);
1305 FIB_ITERATE_END(fn
);
1308 fib_check(&tab
->fib
);
1311 tab
->prune_state
= 0;
1316 * rt_prune_loop - prune routing tables
1317 * @tab: routing table to be pruned
1319 * The prune loop scans routing tables and removes routes belonging to
1320 * inactive protocols and also stale network entries. Returns 1 when
1321 * all such routes are pruned. It is a part of the protocol flushing
1330 WALK_LIST(t
, routing_tables
)
1331 if (! rt_prune_step(t
, &max_feed
))
1338 rt_preconfig(struct config
*c
)
1340 struct symbol
*s
= cf_find_symbol("master");
1342 init_list(&c
->tables
);
1343 c
->master_rtc
= rt_new_table(s
);
1348 * Some functions for handing internal next hop updates
1349 * triggered by rt_schedule_nhu().
1353 rta_next_hop_outdated(rta
*a
)
1355 struct hostentry
*he
= a
->hostentry
;
1361 return a
->dest
!= RTD_UNREACHABLE
;
1363 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1364 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1365 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1369 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1372 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1375 a
->igp_metric
= he
->igp_metric
;
1376 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1380 rt_next_hop_update_rte(rtable
*tab
, rte
*old
)
1383 memcpy(&a
, old
->attrs
, sizeof(rta
));
1384 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1387 rte
*e
= sl_alloc(rte_slab
);
1388 memcpy(e
, old
, sizeof(rte
));
1389 e
->attrs
= rta_lookup(&a
);
1395 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1397 rte
**k
, *e
, *new, *old_best
, **new_best
;
1399 int free_old_best
= 0;
1401 old_best
= n
->routes
;
1405 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1406 if (rta_next_hop_outdated(e
->attrs
))
1408 new = rt_next_hop_update_rte(tab
, e
);
1411 rte_announce_i(tab
, RA_ANY
, n
, new, e
);
1412 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1414 /* Call a pre-comparison hook */
1415 /* Not really an efficient way to compute this */
1416 if (e
->attrs
->proto
->rte_recalculate
)
1417 e
->attrs
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1421 else /* Freeing of the old best rte is postponed */
1431 /* Find the new best route */
1433 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1435 if (!new_best
|| rte_better(e
, *new_best
))
1439 /* Relink the new best route to the first position */
1441 if (new != n
->routes
)
1443 *new_best
= new->next
;
1444 new->next
= n
->routes
;
1448 /* Announce the new best route */
1449 if (new != old_best
)
1451 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
);
1452 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1456 rte_free_quick(old_best
);
1462 rt_next_hop_update(rtable
*tab
)
1464 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1467 if (tab
->nhu_state
== 0)
1470 if (tab
->nhu_state
== 1)
1472 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1476 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1480 FIB_ITERATE_PUT(fit
, fn
);
1481 ev_schedule(tab
->rt_event
);
1484 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1486 FIB_ITERATE_END(fn
);
1488 /* state change 2->0, 3->1 */
1489 tab
->nhu_state
&= 1;
1491 if (tab
->nhu_state
> 0)
1492 ev_schedule(tab
->rt_event
);
1496 struct rtable_config
*
1497 rt_new_table(struct symbol
*s
)
1499 /* Hack that allows to 'redefine' the master table */
1500 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1503 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1505 cf_define_symbol(s
, SYM_TABLE
, c
);
1507 add_tail(&new_config
->tables
, &c
->n
);
1508 c
->gc_max_ops
= 1000;
1514 * rt_lock_table - lock a routing table
1515 * @r: routing table to be locked
1517 * Lock a routing table, because it's in use by a protocol,
1518 * preventing it from being freed when it gets undefined in a new
1522 rt_lock_table(rtable
*r
)
1528 * rt_unlock_table - unlock a routing table
1529 * @r: routing table to be unlocked
1531 * Unlock a routing table formerly locked by rt_lock_table(),
1532 * that is decrease its use count and delete it if it's scheduled
1533 * for deletion by configuration changes.
1536 rt_unlock_table(rtable
*r
)
1538 if (!--r
->use_count
&& r
->deleted
)
1540 struct config
*conf
= r
->deleted
;
1541 DBG("Deleting routing table %s\n", r
->name
);
1543 rt_free_hostcache(r
);
1548 config_del_obstacle(conf
);
1553 * rt_commit - commit new routing table configuration
1554 * @new: new configuration
1555 * @old: original configuration or %NULL if it's boot time config
1557 * Scan differences between @old and @new configuration and modify
1558 * the routing tables according to these changes. If @new defines a
1559 * previously unknown table, create it, if it omits a table existing
1560 * in @old, schedule it for deletion (it gets deleted when all protocols
1561 * disconnect from it by calling rt_unlock_table()), if it exists
1562 * in both configurations, leave it unchanged.
1565 rt_commit(struct config
*new, struct config
*old
)
1567 struct rtable_config
*o
, *r
;
1569 DBG("rt_commit:\n");
1572 WALK_LIST(o
, old
->tables
)
1574 rtable
*ot
= o
->table
;
1577 struct symbol
*sym
= cf_find_symbol(o
->name
);
1578 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1580 DBG("\t%s: same\n", o
->name
);
1585 if (o
->sorted
!= r
->sorted
)
1586 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1590 DBG("\t%s: deleted\n", o
->name
);
1592 config_add_obstacle(old
);
1594 rt_unlock_table(ot
);
1600 WALK_LIST(r
, new->tables
)
1603 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1604 DBG("\t%s: created\n", r
->name
);
1605 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1606 add_tail(&routing_tables
, &t
->n
);
1613 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1615 struct proto
*src
= e
->attrs
->proto
;
1619 tmpa
= src
->make_tmp_attrs
? src
->make_tmp_attrs(e
, rte_update_pool
) : NULL
;
1620 if (type
== RA_ACCEPTED
)
1621 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, tmpa
, p
->refeeding
? 2 : 1);
1623 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, tmpa
, p
->refeeding
);
1624 rte_update_unlock();
1628 * rt_feed_baby - advertise routes to a new protocol
1629 * @p: protocol to be fed
1631 * This function performs one pass of advertisement of routes to a newly
1632 * initialized protocol. It's called by the protocol code as long as it
1633 * has something to do. (We avoid transferring all the routes in single
1634 * pass in order not to monopolize CPU time.)
1637 rt_feed_baby(struct proto
*p
)
1639 struct announce_hook
*h
;
1640 struct fib_iterator
*fit
;
1643 if (!p
->feed_ahook
) /* Need to initialize first */
1647 DBG("Announcing routes to new protocol %s\n", p
->name
);
1648 p
->feed_ahook
= p
->ahooks
;
1649 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1652 fit
= p
->feed_iterator
;
1656 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1658 net
*n
= (net
*) fn
;
1662 FIB_ITERATE_PUT(fit
, fn
);
1666 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1668 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
1669 (p
->accept_ra_types
== RA_ACCEPTED
))
1670 if (rte_is_valid(e
))
1672 if (p
->core_state
!= FS_FEEDING
)
1673 return 1; /* In the meantime, the protocol fell down. */
1674 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
1678 if (p
->accept_ra_types
== RA_ANY
)
1679 for(e
= n
->routes
; rte_is_valid(e
); e
= e
->next
)
1681 if (p
->core_state
!= FS_FEEDING
)
1682 return 1; /* In the meantime, the protocol fell down. */
1683 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
1687 FIB_ITERATE_END(fn
);
1688 p
->feed_ahook
= h
->next
;
1691 mb_free(p
->feed_iterator
);
1692 p
->feed_iterator
= NULL
;
1698 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
1703 * rt_feed_baby_abort - abort protocol feeding
1706 * This function is called by the protocol code when the protocol
1707 * stops or ceases to exist before the last iteration of rt_feed_baby()
1711 rt_feed_baby_abort(struct proto
*p
)
1715 /* Unlink the iterator and exit */
1716 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
1717 p
->feed_ahook
= NULL
;
1722 static inline unsigned
1725 uintptr_t p
= (uintptr_t) ptr
;
1726 return p
^ (p
<< 8) ^ (p
>> 16);
1729 static inline unsigned
1730 hc_hash(ip_addr a
, rtable
*dep
)
1732 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
1736 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
1738 unsigned int k
= he
->hash_key
>> hc
->hash_shift
;
1739 he
->next
= hc
->hash_table
[k
];
1740 hc
->hash_table
[k
] = he
;
1744 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
1746 struct hostentry
**hep
;
1747 unsigned int k
= he
->hash_key
>> hc
->hash_shift
;
1749 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
1753 #define HC_DEF_ORDER 10
1754 #define HC_HI_MARK *4
1755 #define HC_HI_STEP 2
1756 #define HC_HI_ORDER 16 /* Must be at most 16 */
1757 #define HC_LO_MARK /5
1758 #define HC_LO_STEP 2
1759 #define HC_LO_ORDER 10
1762 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
1764 unsigned hsize
= 1 << order
;
1765 hc
->hash_order
= order
;
1766 hc
->hash_shift
= 16 - order
;
1767 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0 : (hsize HC_HI_MARK
);
1768 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0 : (hsize HC_LO_MARK
);
1770 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
1774 hc_resize(struct hostcache
*hc
, unsigned new_order
)
1776 unsigned old_size
= 1 << hc
->hash_order
;
1777 struct hostentry
**old_table
= hc
->hash_table
;
1778 struct hostentry
*he
, *hen
;
1781 hc_alloc_table(hc
, new_order
);
1782 for (i
= 0; i
< old_size
; i
++)
1783 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
1791 static struct hostentry
*
1792 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
1794 struct hostentry
*he
= sl_alloc(hc
->slab
);
1803 add_tail(&hc
->hostentries
, &he
->ln
);
1807 if (hc
->hash_items
> hc
->hash_max
)
1808 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
1814 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
1820 sl_free(hc
->slab
, he
);
1823 if (hc
->hash_items
< hc
->hash_min
)
1824 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
1828 rt_init_hostcache(rtable
*tab
)
1830 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
1831 init_list(&hc
->hostentries
);
1834 hc_alloc_table(hc
, HC_DEF_ORDER
);
1835 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
1837 hc
->lp
= lp_new(rt_table_pool
, 1008);
1838 hc
->trie
= f_new_trie(hc
->lp
);
1840 tab
->hostcache
= hc
;
1844 rt_free_hostcache(rtable
*tab
)
1846 struct hostcache
*hc
= tab
->hostcache
;
1849 WALK_LIST(n
, hc
->hostentries
)
1851 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
1855 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
1860 mb_free(hc
->hash_table
);
1865 rt_notify_hostcache(rtable
*tab
, net
*net
)
1867 struct hostcache
*hc
= tab
->hostcache
;
1869 if (tab
->hcu_scheduled
)
1872 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
1873 rt_schedule_hcu(tab
);
1877 if_local_addr(ip_addr a
, struct iface
*i
)
1881 WALK_LIST(b
, i
->addrs
)
1882 if (ipa_equal(a
, b
->ip
))
1889 rt_get_igp_metric(rte
*rt
)
1891 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
1899 if ((a
->source
== RTS_OSPF
) ||
1900 (a
->source
== RTS_OSPF_IA
) ||
1901 (a
->source
== RTS_OSPF_EXT1
))
1902 return rt
->u
.ospf
.metric1
;
1906 if (a
->source
== RTS_RIP
)
1907 return rt
->u
.rip
.metric
;
1911 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
1914 return IGP_METRIC_UNKNOWN
;
1918 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
1920 rta
*old_src
= he
->src
;
1923 /* Reset the hostentry */
1926 he
->dest
= RTD_UNREACHABLE
;
1929 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
1938 /* Recursive route should not depend on another recursive route */
1939 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
1940 he
->addr
, n
->n
.prefix
, pxlen
);
1944 if (a
->dest
== RTD_DEVICE
)
1946 if (if_local_addr(he
->addr
, a
->iface
))
1948 /* The host address is a local address, this is not valid */
1949 log(L_WARN
"Next hop address %I is a local address of iface %s",
1950 he
->addr
, a
->iface
->name
);
1954 /* The host is directly reachable, use link as a gateway */
1956 he
->dest
= RTD_ROUTER
;
1960 /* The host is reachable through some route entry */
1965 he
->src
= rta_clone(a
);
1966 he
->igp_metric
= rt_get_igp_metric(e
);
1970 /* Add a prefix range to the trie */
1971 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
1974 return old_src
!= he
->src
;
1978 rt_update_hostcache(rtable
*tab
)
1980 struct hostcache
*hc
= tab
->hostcache
;
1981 struct hostentry
*he
;
1984 /* Reset the trie */
1986 hc
->trie
= f_new_trie(hc
->lp
);
1988 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
1990 he
= SKIP_BACK(struct hostentry
, ln
, n
);
1993 hc_delete_hostentry(hc
, he
);
1997 if (rt_update_hostentry(tab
, he
))
1998 rt_schedule_nhu(he
->tab
);
2001 tab
->hcu_scheduled
= 0;
2004 static struct hostentry
*
2005 rt_find_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2007 struct hostentry
*he
;
2009 if (!tab
->hostcache
)
2010 rt_init_hostcache(tab
);
2012 unsigned int k
= hc_hash(a
, dep
);
2013 struct hostcache
*hc
= tab
->hostcache
;
2014 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2015 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2018 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
2019 rt_update_hostentry(tab
, he
);
2024 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
2026 rta_apply_hostentry(a
, rt_find_hostentry(tab
, *gw
, *ll
, dep
));
2034 rt_format_via(rte
*e
, byte
*via
)
2040 case RTD_ROUTER
: bsprintf(via
, "via %I on %s", a
->gw
, a
->iface
->name
); break;
2041 case RTD_DEVICE
: bsprintf(via
, "dev %s", a
->iface
->name
); break;
2042 case RTD_BLACKHOLE
: bsprintf(via
, "blackhole"); break;
2043 case RTD_UNREACHABLE
: bsprintf(via
, "unreachable"); break;
2044 case RTD_PROHIBIT
: bsprintf(via
, "prohibited"); break;
2045 case RTD_MULTIPATH
: bsprintf(via
, "multipath"); break;
2046 default: bsprintf(via
, "???");
2051 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2053 byte via
[STD_ADDRESS_P_LENGTH
+32], from
[STD_ADDRESS_P_LENGTH
+8];
2054 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2056 int primary
= (e
->net
->routes
== e
);
2057 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2060 rt_format_via(e
, via
);
2061 tm_format_datetime(tm
, &config
->tf_route
, e
->lastmod
);
2062 if (ipa_nonzero(a
->from
) && !ipa_equal(a
->from
, a
->gw
))
2063 bsprintf(from
, " from %I", a
->from
);
2066 if (a
->proto
->proto
->get_route_info
|| d
->verbose
)
2068 /* Need to normalize the extended attributes */
2070 t
= ea_append(t
, a
->eattrs
);
2071 tmpa
= alloca(ea_scan(t
));
2075 if (a
->proto
->proto
->get_route_info
)
2076 a
->proto
->proto
->get_route_info(e
, info
, tmpa
);
2078 bsprintf(info
, " (%d)", e
->pref
);
2079 cli_printf(c
, -1007, "%-18s %s [%s %s%s]%s%s", ia
, via
, a
->proto
->name
,
2080 tm
, from
, primary
? (sync_error
? " !" : " *") : "", info
);
2081 for (nh
= a
->nexthops
; nh
; nh
= nh
->next
)
2082 cli_printf(c
, -1007, "\tvia %I on %s weight %d", nh
->gw
, nh
->iface
->name
, nh
->weight
+ 1);
2084 rta_show(c
, a
, tmpa
);
2088 rt_show_net(struct cli
*c
, net
*n
, struct rt_show_data
*d
)
2091 byte ia
[STD_ADDRESS_P_LENGTH
+8];
2092 struct announce_hook
*a
;
2095 bsprintf(ia
, "%I/%d", n
->n
.prefix
, n
->n
.pxlen
);
2097 for(e
=n
->routes
; e
; e
=e
->next
)
2099 if (rte_is_filtered(e
) != d
->filtered
)
2102 struct ea_list
*tmpa
;
2103 struct proto
*p0
= e
->attrs
->proto
;
2104 struct proto
*p1
= d
->export_protocol
;
2105 struct proto
*p2
= d
->show_protocol
;
2111 rte_update_lock(); /* We use the update buffer for filtering */
2112 tmpa
= p0
->make_tmp_attrs
? p0
->make_tmp_attrs(e
, rte_update_pool
) : NULL
;
2113 ok
= f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
;
2114 if (p2
&& p2
!= p0
) ok
= 0;
2115 if (ok
&& d
->export_mode
)
2118 if ((ic
= p1
->import_control
? p1
->import_control(p1
, &e
, &tmpa
, rte_update_pool
) : 0) < 0)
2120 else if (!ic
&& d
->export_mode
> 1)
2122 /* FIXME - this shows what should be exported according
2123 to current filters, but not what was really exported.
2124 'configure soft' command may change the export filter
2125 and do not update routes */
2127 if ((a
= proto_find_announce_hook(p1
, d
->table
)) &&
2128 (f_run(a
->out_filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
))
2136 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2144 rte_update_unlock();
2145 if (d
->primary_only
)
2151 rt_show_cont(struct cli
*c
)
2153 struct rt_show_data
*d
= c
->rover
;
2159 struct fib
*fib
= &d
->table
->fib
;
2160 struct fib_iterator
*it
= &d
->fit
;
2162 FIB_ITERATE_START(fib
, it
, f
)
2165 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2167 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2170 if (d
->export_protocol
&&
2171 d
->export_protocol
->core_state
!= FS_HAPPY
&&
2172 d
->export_protocol
->core_state
!= FS_FEEDING
)
2174 cli_printf(c
, 8005, "Protocol is down");
2179 FIB_ITERATE_PUT(it
, f
);
2182 rt_show_net(c
, n
, d
);
2186 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2188 cli_printf(c
, 0, "");
2190 c
->cont
= c
->cleanup
= NULL
;
2194 rt_show_cleanup(struct cli
*c
)
2196 struct rt_show_data
*d
= c
->rover
;
2198 /* Unlink the iterator */
2199 fit_get(&d
->table
->fib
, &d
->fit
);
2203 rt_show(struct rt_show_data
*d
)
2207 if (d
->pxlen
== 256)
2209 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2210 this_cli
->cont
= rt_show_cont
;
2211 this_cli
->cleanup
= rt_show_cleanup
;
2212 this_cli
->rover
= d
;
2217 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2219 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2222 rt_show_net(this_cli
, n
, d
);
2226 cli_msg(8001, "Network not in table");
2231 * Documentation for functions declared inline in route.h
2236 * net_find - find a network entry
2237 * @tab: a routing table
2238 * @addr: address of the network
2239 * @len: length of the network prefix
2241 * net_find() looks up the given network in routing table @tab and
2242 * returns a pointer to its &net entry or %NULL if no such network
2245 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2249 * net_get - obtain a network entry
2250 * @tab: a routing table
2251 * @addr: address of the network
2252 * @len: length of the network prefix
2254 * net_get() looks up the given network in routing table @tab and
2255 * returns a pointer to its &net entry. If no such entry exists, it's
2258 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2262 * rte_cow - copy a route for writing
2263 * @r: a route entry to be copied
2265 * rte_cow() takes a &rte and prepares it for modification. The exact action
2266 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2267 * just returned unchanged, else a new temporary entry with the same contents
2270 * The primary use of this function is inside the filter machinery -- when
2271 * a filter wants to modify &rte contents (to change the preference or to
2272 * attach another set of attributes), it must ensure that the &rte is not
2273 * shared with anyone else (and especially that it isn't stored in any routing
2276 * Result: a pointer to the new writable &rte.
2278 static inline rte
* rte_cow(rte
*r
)