]>
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
++;
216 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
222 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
226 v
= filter
&& ((filter
== FILTER_REJECT
) ||
227 (f_run(filter
, &rt
, tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
));
233 stats
->exp_updates_filtered
++;
234 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
244 /* Discard temporary rte */
251 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
253 struct proto
*p
= ah
->proto
;
254 struct proto_stats
*stats
= ah
->stats
;
258 * First, apply export limit.
260 * Export route limits has several problems. Because exp_routes
261 * counter is reset before refeed, we don't really know whether
262 * limit is breached and whether the update is new or not. Therefore
263 * the number of really exported routes may exceed the limit
264 * temporarily (routes exported before and new routes in refeed).
266 * Minor advantage is that if the limit is decreased and refeed is
267 * requested, the number of exported routes really decrease.
269 * Second problem is that with export limits, we don't know whether
270 * old was really exported (it might be blocked by limit). When a
271 * withdraw is exported, we announce it even when the previous
272 * update was blocked. This is not a big issue, but the same problem
273 * is in updating exp_routes counter. Therefore, to be consistent in
274 * increases and decreases of exp_routes, we count exported routes
275 * regardless of blocking by limits.
277 * Similar problem is in handling updates - when a new route is
278 * received and blocking is active, the route would be blocked, but
279 * when an update for the route will be received later, the update
280 * would be propagated (as old != NULL). Therefore, we have to block
281 * also non-new updates (contrary to import blocking).
284 struct proto_limit
*l
= ah
->out_limit
;
287 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
288 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
290 if (l
->state
== PLS_BLOCKED
)
292 stats
->exp_routes
++; /* see note above */
293 stats
->exp_updates_rejected
++;
294 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
304 stats
->exp_updates_accepted
++;
306 stats
->exp_withdraws_accepted
++;
308 /* Hack: We do not decrease exp_routes during refeed, we instead
309 reset exp_routes at the start of refeed. */
315 if (p
->debug
& D_ROUTES
)
318 rte_trace_out(D_ROUTES
, p
, new, "replaced");
320 rte_trace_out(D_ROUTES
, p
, new, "added");
322 rte_trace_out(D_ROUTES
, p
, old
, "removed");
325 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
331 t
->next
= new->attrs
->eattrs
;
332 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
336 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
340 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
342 // struct proto *p = ah->proto;
343 struct proto_stats
*stats
= ah
->stats
;
345 rte
*new_free
= NULL
;
346 rte
*old_free
= NULL
;
349 stats
->exp_updates_received
++;
351 stats
->exp_withdraws_received
++;
354 * This is a tricky part - we don't know whether route 'old' was
355 * exported to protocol 'p' or was filtered by the export filter.
356 * We try to run the export filter to know this to have a correct
357 * value in 'old' argument of rte_update (and proper filter value)
359 * FIXME - this is broken because 'configure soft' may change
360 * filters but keep routes. Refeed is expected to be called after
361 * change of the filters and with old == new, therefore we do not
362 * even try to run the filter on an old route, This may lead to
363 * 'spurious withdraws' but ensure that there are no 'missing
366 * This is not completely safe as there is a window between
367 * reconfiguration and the end of refeed - if a newly filtered
368 * route disappears during this period, proper withdraw is not
369 * sent (because old would be also filtered) and the route is
370 * not refeeded (because it disappeared before that).
374 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
377 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
379 /* FIXME - This is broken because of incorrect 'old' value (see above) */
383 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
385 /* Discard temporary rte's */
393 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
,
394 ea_list
*tmpa
, int feed
)
396 // struct proto *p = ah->proto;
397 struct proto_stats
*stats
= ah
->stats
;
399 rte
*new_best
= NULL
;
400 rte
*old_best
= NULL
;
401 rte
*new_free
= NULL
;
402 rte
*old_free
= NULL
;
405 /* Used to track whether we met old_changed position. If before_old is NULL
406 old_changed was the first and we met it implicitly before current best route. */
407 int old_meet
= old_changed
&& !before_old
;
409 /* Note that before_old is either NULL or valid (not rejected) route.
410 If old_changed is valid, before_old have to be too. If old changed route
411 was not valid, caller must use NULL for both old_changed and before_old. */
414 stats
->exp_updates_received
++;
416 stats
->exp_withdraws_received
++;
418 /* First, find the new_best route - first accepted by filters */
419 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
421 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
424 /* Note if we walked around the position of old_changed route */
430 * Second, handle the feed case. That means we do not care for
431 * old_best. It is NULL for feed, and the new_best for refeed.
432 * For refeed, there is a hack similar to one in rt_notify_basic()
433 * to ensure withdraws in case of changed filters
437 if (feed
== 2) /* refeed */
438 old_best
= new_best
? new_best
:
439 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
443 if (!new_best
&& !old_best
)
450 * Now, we find the old_best route. Generally, it is the same as the
451 * new_best, unless new_best is the same as new_changed or
452 * old_changed is accepted before new_best.
454 * There are four cases:
456 * - We would find and accept old_changed before new_best, therefore
457 * old_changed is old_best. In remaining cases we suppose this
460 * - We found no new_best, therefore there is also no old_best and
461 * we ignore this withdraw.
463 * - We found new_best different than new_changed, therefore
464 * old_best is the same as new_best and we ignore this update.
466 * - We found new_best the same as new_changed, therefore it cannot
467 * be old_best and we have to continue search for old_best.
472 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
479 /* Third case, we use r instead of new_best, because export_filter() could change it */
480 if (r
!= new_changed
)
488 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
490 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
494 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
498 /* Implicitly, old_best is NULL and new_best is non-NULL */
501 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
503 /* Discard temporary rte's */
511 * rte_announce - announce a routing table change
512 * @tab: table the route has been added to
513 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
514 * @net: network in question
515 * @new: the new route to be announced
516 * @old: the previous route for the same network
517 * @tmpa: a list of temporary attributes belonging to the new route
519 * This function gets a routing table update and announces it
520 * to all protocols that acccepts given type of route announcement
521 * and are connected to the same table by their announcement hooks.
523 * Route announcement of type RA_OPTIMAL si generated when optimal
524 * route (in routing table @tab) changes. In that case @old stores the
527 * Route announcement of type RA_ANY si generated when any route (in
528 * routing table @tab) changes In that case @old stores the old route
529 * from the same protocol.
531 * For each appropriate protocol, we first call its import_control()
532 * hook which performs basic checks on the route (each protocol has a
533 * right to veto or force accept of the route before any filter is
534 * asked) and adds default values of attributes specific to the new
535 * protocol (metrics, tags etc.). Then it consults the protocol's
536 * export filter and if it accepts the route, the rt_notify() hook of
537 * the protocol gets called.
540 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
, rte
*before_old
, ea_list
*tmpa
)
542 if (!rte_is_valid(old
))
543 old
= before_old
= NULL
;
545 if (!rte_is_valid(new))
551 if (type
== RA_OPTIMAL
)
554 new->attrs
->proto
->stats
.pref_routes
++;
556 old
->attrs
->proto
->stats
.pref_routes
--;
559 rt_notify_hostcache(tab
, net
);
562 struct announce_hook
*a
;
563 WALK_LIST(a
, tab
->hooks
)
565 ASSERT(a
->proto
->core_state
== FS_HAPPY
|| a
->proto
->core_state
== FS_FEEDING
);
566 if (a
->proto
->accept_ra_types
== type
)
567 if (type
== RA_ACCEPTED
)
568 rt_notify_accepted(a
, net
, new, old
, before_old
, tmpa
, 0);
570 rt_notify_basic(a
, net
, new, old
, tmpa
, 0);
580 if ((n
->n
.pxlen
> BITS_PER_IP_ADDRESS
) || !ip_is_prefix(n
->n
.prefix
,n
->n
.pxlen
))
582 log(L_WARN
"Ignoring bogus prefix %I/%d received via %s",
583 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
587 c
= ipa_classify_net(n
->n
.prefix
);
588 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
590 log(L_WARN
"Ignoring bogus route %I/%d received via %s",
591 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
599 * rte_free - delete a &rte
600 * @e: &rte to be deleted
602 * rte_free() deletes the given &rte from the routing table it's linked to.
607 if (e
->attrs
->aflags
& RTAF_CACHED
)
609 sl_free(rte_slab
, e
);
613 rte_free_quick(rte
*e
)
616 sl_free(rte_slab
, e
);
620 rte_same(rte
*x
, rte
*y
)
623 x
->attrs
== y
->attrs
&&
624 x
->flags
== y
->flags
&&
625 x
->pflags
== y
->pflags
&&
626 x
->pref
== y
->pref
&&
627 (!x
->attrs
->proto
->rte_same
|| x
->attrs
->proto
->rte_same(x
, y
));
630 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
633 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, ea_list
*tmpa
, struct proto
*src
)
635 struct proto
*p
= ah
->proto
;
636 struct rtable
*table
= ah
->table
;
637 struct proto_stats
*stats
= ah
->stats
;
638 rte
*before_old
= NULL
;
639 rte
*old_best
= net
->routes
;
643 k
= &net
->routes
; /* Find and remove original route from the same protocol */
646 if (old
->attrs
->proto
== src
)
648 /* If there is the same route in the routing table but from
649 * a different sender, then there are two paths from the
650 * source protocol to this routing table through transparent
651 * pipes, which is not allowed.
653 * We log that and ignore the route. If it is withdraw, we
654 * ignore it completely (there might be 'spurious withdraws',
655 * see FIXME in do_rte_announce())
657 if (old
->sender
->proto
!= p
)
661 log(L_ERR
"Pipe collision detected when sending %I/%d to table %s",
662 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
668 if (new && rte_same(old
, new))
670 /* No changes, ignore the new route */
672 if (!rte_is_filtered(new))
674 stats
->imp_updates_ignored
++;
675 rte_trace_in(D_ROUTES
, p
, new, "ignored");
680 /* lastmod is used internally by RIP as the last time
681 when the route was received. */
682 if (src
->proto
== &proto_rip
)
699 stats
->imp_withdraws_ignored
++;
703 int new_ok
= rte_is_ok(new);
704 int old_ok
= rte_is_ok(old
);
706 struct proto_limit
*l
= ah
->rx_limit
;
707 if (l
&& !old
&& new)
709 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
711 if (all_routes
>= l
->limit
)
712 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
714 if (l
->state
== PLS_BLOCKED
)
716 /* In receive limit the situation is simple, old is NULL so
717 we just free new and exit like nothing happened */
719 stats
->imp_updates_ignored
++;
720 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
727 if (l
&& !old_ok
&& new_ok
)
729 if (stats
->imp_routes
>= l
->limit
)
730 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
732 if (l
->state
== PLS_BLOCKED
)
734 /* In import limit the situation is more complicated. We
735 shouldn't just drop the route, we should handle it like
736 it was filtered. We also have to continue the route
737 processing if old or new is non-NULL, but we should exit
738 if both are NULL as this case is probably assumed to be
741 stats
->imp_updates_ignored
++;
742 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
744 if (ah
->in_keep_filtered
)
745 new->flags
|= REF_FILTERED
;
747 { rte_free_quick(new); new = NULL
; }
749 /* Note that old && !new could be possible when
750 ah->in_keep_filtered changed in the recent past. */
761 stats
->imp_updates_accepted
++;
763 stats
->imp_withdraws_accepted
++;
765 stats
->imp_withdraws_ignored
++;
770 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
772 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
774 if (table
->config
->sorted
)
776 /* If routes are sorted, just insert new route to appropriate position */
779 if (before_old
&& !rte_better(new, before_old
))
780 k
= &before_old
->next
;
784 for (; *k
; k
=&(*k
)->next
)
785 if (rte_better(new, *k
))
794 /* If routes are not sorted, find the best route and move it on
795 the first position. There are several optimized cases. */
797 if (src
->rte_recalculate
&& src
->rte_recalculate(table
, net
, new, old
, old_best
))
800 if (new && rte_better(new, old_best
))
802 /* The first case - the new route is cleary optimal,
803 we link it at the first position */
805 new->next
= net
->routes
;
808 else if (old
== old_best
)
810 /* The second case - the old best route disappeared, we add the
811 new route (if we have any) to the list (we don't care about
812 position) and then we elect the new optimal route and relink
813 that route at the first position and announce it. New optimal
814 route might be NULL if there is no more routes */
817 /* Add the new route to the list */
820 new->next
= net
->routes
;
824 /* Find a new optimal route (if there is any) */
827 rte
**bp
= &net
->routes
;
828 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
829 if (rte_better(*k
, *bp
))
835 best
->next
= net
->routes
;
841 /* The third case - the new route is not better than the old
842 best route (therefore old_best != NULL) and the old best
843 route was not removed (therefore old_best == net->routes).
844 We just link the new route after the old best route. */
846 ASSERT(net
->routes
!= NULL
);
847 new->next
= net
->routes
->next
;
848 net
->routes
->next
= new;
850 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
856 /* Log the route change */
857 if (p
->debug
& D_ROUTES
)
860 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
864 rte_trace(p
, old
, '>', "removed");
865 else if (rte_is_ok(net
->routes
))
866 rte_trace(p
, old
, '>', "removed [replaced]");
868 rte_trace(p
, old
, '>', "removed [sole]");
872 /* Propagate the route change */
873 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, tmpa
);
874 if (net
->routes
!= old_best
)
875 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, tmpa
);
876 if (table
->config
->sorted
)
877 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, before_old
, tmpa
);
880 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
881 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
882 rt_schedule_gc(table
);
884 if (old_ok
&& p
->rte_remove
)
885 p
->rte_remove(net
, old
);
886 if (new_ok
&& p
->rte_insert
)
887 p
->rte_insert(net
, new);
893 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
896 rte_update_lock(void)
898 rte_update_nest_cnt
++;
902 rte_update_unlock(void)
904 if (!--rte_update_nest_cnt
)
905 lp_flush(rte_update_pool
);
909 * rte_update - enter a new update to a routing table
910 * @table: table to be updated
911 * @ah: pointer to table announce hook
913 * @p: protocol submitting the update
914 * @src: protocol originating the update
915 * @new: a &rte representing the new route or %NULL for route removal.
917 * This function is called by the routing protocols whenever they discover
918 * a new route or wish to update/remove an existing route. The right announcement
919 * sequence is to build route attributes first (either un-cached with @aflags set
920 * to zero or a cached one using rta_lookup(); in this case please note that
921 * you need to increase the use count of the attributes yourself by calling
922 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
923 * the appropriate data and finally submit the new &rte by calling rte_update().
925 * @src specifies the protocol that originally created the route and the meaning
926 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
927 * same value as @new->attrs->proto. @p specifies the protocol that called
928 * rte_update(). In most cases it is the same protocol as @src. rte_update()
929 * stores @p in @new->sender;
931 * When rte_update() gets any route, it automatically validates it (checks,
932 * whether the network and next hop address are valid IP addresses and also
933 * whether a normal routing protocol doesn't try to smuggle a host or link
934 * scope route to the table), converts all protocol dependent attributes stored
935 * in the &rte to temporary extended attributes, consults import filters of the
936 * protocol to see if the route should be accepted and/or its attributes modified,
937 * stores the temporary attributes back to the &rte.
939 * Now, having a "public" version of the route, we
940 * automatically find any old route defined by the protocol @src
941 * for network @n, replace it by the new one (or removing it if @new is %NULL),
942 * recalculate the optimal route for this destination and finally broadcast
943 * the change (if any) to all routing protocols by calling rte_announce().
945 * All memory used for attribute lists and other temporary allocations is taken
946 * from a special linear pool @rte_update_pool and freed when rte_update()
951 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct proto
*src
)
953 struct proto
*p
= ah
->proto
;
954 struct proto_stats
*stats
= ah
->stats
;
955 struct filter
*filter
= ah
->in_filter
;
956 ea_list
*tmpa
= NULL
;
963 stats
->imp_updates_received
++;
964 if (!rte_validate(new))
966 rte_trace_in(D_FILTERS
, p
, new, "invalid");
967 stats
->imp_updates_invalid
++;
971 if (filter
== FILTER_REJECT
)
973 stats
->imp_updates_filtered
++;
974 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
976 if (! ah
->in_keep_filtered
)
979 /* new is a private copy, i could modify it */
980 new->flags
|= REF_FILTERED
;
984 if (src
->make_tmp_attrs
)
985 tmpa
= src
->make_tmp_attrs(new, rte_update_pool
);
986 if (filter
&& (filter
!= FILTER_REJECT
))
988 ea_list
*old_tmpa
= tmpa
;
989 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
992 stats
->imp_updates_filtered
++;
993 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
995 if (! ah
->in_keep_filtered
)
998 new->flags
|= REF_FILTERED
;
1000 if (tmpa
!= old_tmpa
&& src
->store_tmp_attrs
)
1001 src
->store_tmp_attrs(new, tmpa
);
1005 if (!(new->attrs
->aflags
& RTAF_CACHED
)) /* Need to copy attributes */
1006 new->attrs
= rta_lookup(new->attrs
);
1007 new->flags
|= REF_COW
;
1010 stats
->imp_withdraws_received
++;
1012 rte_recalculate(ah
, net
, new, tmpa
, src
);
1013 rte_update_unlock();
1018 rte_recalculate(ah
, net
, NULL
, NULL
, src
);
1019 rte_update_unlock();
1022 /* Independent call to rte_announce(), used from next hop
1023 recalculation, outside of rte_update(). new must be non-NULL */
1025 rte_announce_i(rtable
*tab
, unsigned type
, net
*n
, rte
*new, rte
*old
)
1031 src
= new->attrs
->proto
;
1032 tmpa
= src
->make_tmp_attrs
? src
->make_tmp_attrs(new, rte_update_pool
) : NULL
;
1033 rte_announce(tab
, type
, n
, new, old
, NULL
, tmpa
);
1034 rte_update_unlock();
1038 rte_discard(rtable
*t
, rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1041 rte_recalculate(old
->sender
, old
->net
, NULL
, NULL
, old
->attrs
->proto
);
1042 rte_update_unlock();
1046 * rte_dump - dump a route
1047 * @e: &rte to be dumped
1049 * This functions dumps contents of a &rte to debug output.
1055 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1056 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1058 if (e
->attrs
->proto
->proto
->dump_attrs
)
1059 e
->attrs
->proto
->proto
->dump_attrs(e
);
1064 * rt_dump - dump a routing table
1065 * @t: routing table to be dumped
1067 * This function dumps contents of a given routing table to debug output.
1074 struct announce_hook
*a
;
1076 debug("Dump of routing table <%s>\n", t
->name
);
1080 FIB_WALK(&t
->fib
, fn
)
1083 for(e
=n
->routes
; e
; e
=e
->next
)
1087 WALK_LIST(a
, t
->hooks
)
1088 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1093 * rt_dump_all - dump all routing tables
1095 * This function dumps contents of all routing tables to debug output.
1102 WALK_LIST(t
, routing_tables
)
1107 rt_schedule_gc(rtable
*tab
)
1109 if (tab
->gc_scheduled
)
1112 tab
->gc_scheduled
= 1;
1113 ev_schedule(tab
->rt_event
);
1117 rt_schedule_hcu(rtable
*tab
)
1119 if (tab
->hcu_scheduled
)
1122 tab
->hcu_scheduled
= 1;
1123 ev_schedule(tab
->rt_event
);
1127 rt_schedule_nhu(rtable
*tab
)
1129 if (tab
->nhu_state
== 0)
1130 ev_schedule(tab
->rt_event
);
1132 /* state change 0->1, 2->3 */
1133 tab
->nhu_state
|= 1;
1137 rt_prune_nets(rtable
*tab
)
1139 struct fib_iterator fit
;
1140 int ncnt
= 0, ndel
= 0;
1143 fib_check(&tab
->fib
);
1146 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1148 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1152 if (!n
->routes
) /* Orphaned FIB entry */
1154 FIB_ITERATE_PUT(&fit
, f
);
1155 fib_delete(&tab
->fib
, f
);
1161 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1163 tab
->gc_counter
= 0;
1165 tab
->gc_scheduled
= 0;
1173 if (tab
->hcu_scheduled
)
1174 rt_update_hostcache(tab
);
1177 rt_next_hop_update(tab
);
1179 if (tab
->gc_scheduled
)
1184 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1186 bzero(t
, sizeof(*t
));
1187 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1190 init_list(&t
->hooks
);
1193 t
->rt_event
= ev_new(p
);
1194 t
->rt_event
->hook
= rt_event
;
1195 t
->rt_event
->data
= t
;
1201 * rt_init - initialize routing tables
1203 * This function is called during BIRD startup. It initializes the
1204 * routing table module.
1210 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1211 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1212 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1213 init_list(&routing_tables
);
1217 /* Called from proto_schedule_flush_loop() only,
1218 ensuring that all prune states are zero */
1220 rt_schedule_prune_all(void)
1224 WALK_LIST(t
, routing_tables
)
1229 rt_prune_step(rtable
*tab
, int *max_feed
)
1231 struct fib_iterator
*fit
= &tab
->prune_fit
;
1233 DBG("Pruning route table %s\n", tab
->name
);
1235 fib_check(&tab
->fib
);
1238 if (tab
->prune_state
== 0)
1241 if (tab
->prune_state
== 1)
1243 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1244 tab
->prune_state
= 2;
1248 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1250 net
*n
= (net
*) fn
;
1254 for (e
=n
->routes
; e
; e
=e
->next
)
1255 if (e
->sender
->proto
->core_state
!= FS_HAPPY
&&
1256 e
->sender
->proto
->core_state
!= FS_FEEDING
)
1260 FIB_ITERATE_PUT(fit
, fn
);
1264 rte_discard(tab
, e
);
1269 if (!n
->routes
) /* Orphaned FIB entry */
1271 FIB_ITERATE_PUT(fit
, fn
);
1272 fib_delete(&tab
->fib
, fn
);
1276 FIB_ITERATE_END(fn
);
1279 fib_check(&tab
->fib
);
1282 tab
->prune_state
= 0;
1287 * rt_prune_loop - prune routing tables
1288 * @tab: routing table to be pruned
1290 * The prune loop scans routing tables and removes routes belonging to
1291 * inactive protocols and also stale network entries. Returns 1 when
1292 * all such routes are pruned. It is a part of the protocol flushing
1301 WALK_LIST(t
, routing_tables
)
1302 if (! rt_prune_step(t
, &max_feed
))
1309 rt_preconfig(struct config
*c
)
1311 struct symbol
*s
= cf_find_symbol("master");
1313 init_list(&c
->tables
);
1314 c
->master_rtc
= rt_new_table(s
);
1319 * Some functions for handing internal next hop updates
1320 * triggered by rt_schedule_nhu().
1324 rta_next_hop_outdated(rta
*a
)
1326 struct hostentry
*he
= a
->hostentry
;
1332 return a
->dest
!= RTD_UNREACHABLE
;
1334 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1335 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1336 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1340 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1343 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1346 a
->igp_metric
= he
->igp_metric
;
1347 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1351 rt_next_hop_update_rte(rtable
*tab
, rte
*old
)
1354 memcpy(&a
, old
->attrs
, sizeof(rta
));
1355 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1358 rte
*e
= sl_alloc(rte_slab
);
1359 memcpy(e
, old
, sizeof(rte
));
1360 e
->attrs
= rta_lookup(&a
);
1366 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1368 rte
**k
, *e
, *new, *old_best
, **new_best
;
1370 int free_old_best
= 0;
1372 old_best
= n
->routes
;
1376 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1377 if (rta_next_hop_outdated(e
->attrs
))
1379 new = rt_next_hop_update_rte(tab
, e
);
1382 rte_announce_i(tab
, RA_ANY
, n
, new, e
);
1383 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1385 /* Call a pre-comparison hook */
1386 /* Not really an efficient way to compute this */
1387 if (e
->attrs
->proto
->rte_recalculate
)
1388 e
->attrs
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1392 else /* Freeing of the old best rte is postponed */
1402 /* Find the new best route */
1404 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1406 if (!new_best
|| rte_better(e
, *new_best
))
1410 /* Relink the new best route to the first position */
1412 if (new != n
->routes
)
1414 *new_best
= new->next
;
1415 new->next
= n
->routes
;
1419 /* Announce the new best route */
1420 if (new != old_best
)
1422 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
);
1423 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1427 rte_free_quick(old_best
);
1433 rt_next_hop_update(rtable
*tab
)
1435 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1438 if (tab
->nhu_state
== 0)
1441 if (tab
->nhu_state
== 1)
1443 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1447 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1451 FIB_ITERATE_PUT(fit
, fn
);
1452 ev_schedule(tab
->rt_event
);
1455 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1457 FIB_ITERATE_END(fn
);
1459 /* state change 2->0, 3->1 */
1460 tab
->nhu_state
&= 1;
1462 if (tab
->nhu_state
> 0)
1463 ev_schedule(tab
->rt_event
);
1467 struct rtable_config
*
1468 rt_new_table(struct symbol
*s
)
1470 /* Hack that allows to 'redefine' the master table */
1471 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1474 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1476 cf_define_symbol(s
, SYM_TABLE
, c
);
1478 add_tail(&new_config
->tables
, &c
->n
);
1479 c
->gc_max_ops
= 1000;
1485 * rt_lock_table - lock a routing table
1486 * @r: routing table to be locked
1488 * Lock a routing table, because it's in use by a protocol,
1489 * preventing it from being freed when it gets undefined in a new
1493 rt_lock_table(rtable
*r
)
1499 * rt_unlock_table - unlock a routing table
1500 * @r: routing table to be unlocked
1502 * Unlock a routing table formerly locked by rt_lock_table(),
1503 * that is decrease its use count and delete it if it's scheduled
1504 * for deletion by configuration changes.
1507 rt_unlock_table(rtable
*r
)
1509 if (!--r
->use_count
&& r
->deleted
)
1511 struct config
*conf
= r
->deleted
;
1512 DBG("Deleting routing table %s\n", r
->name
);
1514 rt_free_hostcache(r
);
1519 config_del_obstacle(conf
);
1524 * rt_commit - commit new routing table configuration
1525 * @new: new configuration
1526 * @old: original configuration or %NULL if it's boot time config
1528 * Scan differences between @old and @new configuration and modify
1529 * the routing tables according to these changes. If @new defines a
1530 * previously unknown table, create it, if it omits a table existing
1531 * in @old, schedule it for deletion (it gets deleted when all protocols
1532 * disconnect from it by calling rt_unlock_table()), if it exists
1533 * in both configurations, leave it unchanged.
1536 rt_commit(struct config
*new, struct config
*old
)
1538 struct rtable_config
*o
, *r
;
1540 DBG("rt_commit:\n");
1543 WALK_LIST(o
, old
->tables
)
1545 rtable
*ot
= o
->table
;
1548 struct symbol
*sym
= cf_find_symbol(o
->name
);
1549 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1551 DBG("\t%s: same\n", o
->name
);
1556 if (o
->sorted
!= r
->sorted
)
1557 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1561 DBG("\t%s: deleted\n", o
->name
);
1563 config_add_obstacle(old
);
1565 rt_unlock_table(ot
);
1571 WALK_LIST(r
, new->tables
)
1574 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1575 DBG("\t%s: created\n", r
->name
);
1576 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1577 add_tail(&routing_tables
, &t
->n
);
1584 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1586 struct proto
*src
= e
->attrs
->proto
;
1590 tmpa
= src
->make_tmp_attrs
? src
->make_tmp_attrs(e
, rte_update_pool
) : NULL
;
1591 if (type
== RA_ACCEPTED
)
1592 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, tmpa
, p
->refeeding
? 2 : 1);
1594 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, tmpa
, p
->refeeding
);
1595 rte_update_unlock();
1599 * rt_feed_baby - advertise routes to a new protocol
1600 * @p: protocol to be fed
1602 * This function performs one pass of advertisement of routes to a newly
1603 * initialized protocol. It's called by the protocol code as long as it
1604 * has something to do. (We avoid transferring all the routes in single
1605 * pass in order not to monopolize CPU time.)
1608 rt_feed_baby(struct proto
*p
)
1610 struct announce_hook
*h
;
1611 struct fib_iterator
*fit
;
1614 if (!p
->feed_ahook
) /* Need to initialize first */
1618 DBG("Announcing routes to new protocol %s\n", p
->name
);
1619 p
->feed_ahook
= p
->ahooks
;
1620 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1623 fit
= p
->feed_iterator
;
1627 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1629 net
*n
= (net
*) fn
;
1633 FIB_ITERATE_PUT(fit
, fn
);
1637 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1639 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
1640 (p
->accept_ra_types
== RA_ACCEPTED
))
1641 if (rte_is_valid(e
))
1643 if (p
->core_state
!= FS_FEEDING
)
1644 return 1; /* In the meantime, the protocol fell down. */
1645 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
1649 if (p
->accept_ra_types
== RA_ANY
)
1650 for(e
= n
->routes
; rte_is_valid(e
); e
= e
->next
)
1652 if (p
->core_state
!= FS_FEEDING
)
1653 return 1; /* In the meantime, the protocol fell down. */
1654 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
1658 FIB_ITERATE_END(fn
);
1659 p
->feed_ahook
= h
->next
;
1662 mb_free(p
->feed_iterator
);
1663 p
->feed_iterator
= NULL
;
1669 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
1674 * rt_feed_baby_abort - abort protocol feeding
1677 * This function is called by the protocol code when the protocol
1678 * stops or ceases to exist before the last iteration of rt_feed_baby()
1682 rt_feed_baby_abort(struct proto
*p
)
1686 /* Unlink the iterator and exit */
1687 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
1688 p
->feed_ahook
= NULL
;
1693 static inline unsigned
1696 uintptr_t p
= (uintptr_t) ptr
;
1697 return p
^ (p
<< 8) ^ (p
>> 16);
1700 static inline unsigned
1701 hc_hash(ip_addr a
, rtable
*dep
)
1703 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
1707 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
1709 unsigned int k
= he
->hash_key
>> hc
->hash_shift
;
1710 he
->next
= hc
->hash_table
[k
];
1711 hc
->hash_table
[k
] = he
;
1715 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
1717 struct hostentry
**hep
;
1718 unsigned int k
= he
->hash_key
>> hc
->hash_shift
;
1720 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
1724 #define HC_DEF_ORDER 10
1725 #define HC_HI_MARK *4
1726 #define HC_HI_STEP 2
1727 #define HC_HI_ORDER 16 /* Must be at most 16 */
1728 #define HC_LO_MARK /5
1729 #define HC_LO_STEP 2
1730 #define HC_LO_ORDER 10
1733 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
1735 unsigned hsize
= 1 << order
;
1736 hc
->hash_order
= order
;
1737 hc
->hash_shift
= 16 - order
;
1738 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0 : (hsize HC_HI_MARK
);
1739 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0 : (hsize HC_LO_MARK
);
1741 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
1745 hc_resize(struct hostcache
*hc
, unsigned new_order
)
1747 unsigned old_size
= 1 << hc
->hash_order
;
1748 struct hostentry
**old_table
= hc
->hash_table
;
1749 struct hostentry
*he
, *hen
;
1752 hc_alloc_table(hc
, new_order
);
1753 for (i
= 0; i
< old_size
; i
++)
1754 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
1762 static struct hostentry
*
1763 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
1765 struct hostentry
*he
= sl_alloc(hc
->slab
);
1774 add_tail(&hc
->hostentries
, &he
->ln
);
1778 if (hc
->hash_items
> hc
->hash_max
)
1779 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
1785 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
1791 sl_free(hc
->slab
, he
);
1794 if (hc
->hash_items
< hc
->hash_min
)
1795 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
1799 rt_init_hostcache(rtable
*tab
)
1801 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
1802 init_list(&hc
->hostentries
);
1805 hc_alloc_table(hc
, HC_DEF_ORDER
);
1806 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
1808 hc
->lp
= lp_new(rt_table_pool
, 1008);
1809 hc
->trie
= f_new_trie(hc
->lp
);
1811 tab
->hostcache
= hc
;
1815 rt_free_hostcache(rtable
*tab
)
1817 struct hostcache
*hc
= tab
->hostcache
;
1820 WALK_LIST(n
, hc
->hostentries
)
1822 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
1826 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
1831 mb_free(hc
->hash_table
);
1836 rt_notify_hostcache(rtable
*tab
, net
*net
)
1838 struct hostcache
*hc
= tab
->hostcache
;
1840 if (tab
->hcu_scheduled
)
1843 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
1844 rt_schedule_hcu(tab
);
1848 if_local_addr(ip_addr a
, struct iface
*i
)
1852 WALK_LIST(b
, i
->addrs
)
1853 if (ipa_equal(a
, b
->ip
))
1860 rt_get_igp_metric(rte
*rt
)
1862 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
1870 if ((a
->source
== RTS_OSPF
) ||
1871 (a
->source
== RTS_OSPF_IA
) ||
1872 (a
->source
== RTS_OSPF_EXT1
))
1873 return rt
->u
.ospf
.metric1
;
1877 if (a
->source
== RTS_RIP
)
1878 return rt
->u
.rip
.metric
;
1882 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
1885 return IGP_METRIC_UNKNOWN
;
1889 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
1891 rta
*old_src
= he
->src
;
1894 /* Reset the hostentry */
1897 he
->dest
= RTD_UNREACHABLE
;
1900 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
1909 /* Recursive route should not depend on another recursive route */
1910 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
1911 he
->addr
, n
->n
.prefix
, pxlen
);
1915 if (a
->dest
== RTD_DEVICE
)
1917 if (if_local_addr(he
->addr
, a
->iface
))
1919 /* The host address is a local address, this is not valid */
1920 log(L_WARN
"Next hop address %I is a local address of iface %s",
1921 he
->addr
, a
->iface
->name
);
1925 /* The host is directly reachable, use link as a gateway */
1927 he
->dest
= RTD_ROUTER
;
1931 /* The host is reachable through some route entry */
1936 he
->src
= rta_clone(a
);
1937 he
->igp_metric
= rt_get_igp_metric(e
);
1941 /* Add a prefix range to the trie */
1942 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
1945 return old_src
!= he
->src
;
1949 rt_update_hostcache(rtable
*tab
)
1951 struct hostcache
*hc
= tab
->hostcache
;
1952 struct hostentry
*he
;
1955 /* Reset the trie */
1957 hc
->trie
= f_new_trie(hc
->lp
);
1959 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
1961 he
= SKIP_BACK(struct hostentry
, ln
, n
);
1964 hc_delete_hostentry(hc
, he
);
1968 if (rt_update_hostentry(tab
, he
))
1969 rt_schedule_nhu(he
->tab
);
1972 tab
->hcu_scheduled
= 0;
1975 static struct hostentry
*
1976 rt_find_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
1978 struct hostentry
*he
;
1980 if (!tab
->hostcache
)
1981 rt_init_hostcache(tab
);
1983 unsigned int k
= hc_hash(a
, dep
);
1984 struct hostcache
*hc
= tab
->hostcache
;
1985 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
1986 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
1989 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
1990 rt_update_hostentry(tab
, he
);
1995 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
1997 rta_apply_hostentry(a
, rt_find_hostentry(tab
, *gw
, *ll
, dep
));
2005 rt_format_via(rte
*e
, byte
*via
)
2011 case RTD_ROUTER
: bsprintf(via
, "via %I on %s", a
->gw
, a
->iface
->name
); break;
2012 case RTD_DEVICE
: bsprintf(via
, "dev %s", a
->iface
->name
); break;
2013 case RTD_BLACKHOLE
: bsprintf(via
, "blackhole"); break;
2014 case RTD_UNREACHABLE
: bsprintf(via
, "unreachable"); break;
2015 case RTD_PROHIBIT
: bsprintf(via
, "prohibited"); break;
2016 case RTD_MULTIPATH
: bsprintf(via
, "multipath"); break;
2017 default: bsprintf(via
, "???");
2022 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2024 byte via
[STD_ADDRESS_P_LENGTH
+32], from
[STD_ADDRESS_P_LENGTH
+8];
2025 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2027 int primary
= (e
->net
->routes
== e
);
2028 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2031 rt_format_via(e
, via
);
2032 tm_format_datetime(tm
, &config
->tf_route
, e
->lastmod
);
2033 if (ipa_nonzero(a
->from
) && !ipa_equal(a
->from
, a
->gw
))
2034 bsprintf(from
, " from %I", a
->from
);
2037 if (a
->proto
->proto
->get_route_info
|| d
->verbose
)
2039 /* Need to normalize the extended attributes */
2041 t
= ea_append(t
, a
->eattrs
);
2042 tmpa
= alloca(ea_scan(t
));
2046 if (a
->proto
->proto
->get_route_info
)
2047 a
->proto
->proto
->get_route_info(e
, info
, tmpa
);
2049 bsprintf(info
, " (%d)", e
->pref
);
2050 cli_printf(c
, -1007, "%-18s %s [%s %s%s]%s%s", ia
, via
, a
->proto
->name
,
2051 tm
, from
, primary
? (sync_error
? " !" : " *") : "", info
);
2052 for (nh
= a
->nexthops
; nh
; nh
= nh
->next
)
2053 cli_printf(c
, -1007, "\tvia %I on %s weight %d", nh
->gw
, nh
->iface
->name
, nh
->weight
+ 1);
2055 rta_show(c
, a
, tmpa
);
2059 rt_show_net(struct cli
*c
, net
*n
, struct rt_show_data
*d
)
2062 byte ia
[STD_ADDRESS_P_LENGTH
+8];
2063 struct announce_hook
*a
;
2066 bsprintf(ia
, "%I/%d", n
->n
.prefix
, n
->n
.pxlen
);
2068 for(e
=n
->routes
; e
; e
=e
->next
)
2070 if (rte_is_filtered(e
) != d
->filtered
)
2073 struct ea_list
*tmpa
;
2074 struct proto
*p0
= e
->attrs
->proto
;
2075 struct proto
*p1
= d
->export_protocol
;
2076 struct proto
*p2
= d
->show_protocol
;
2082 rte_update_lock(); /* We use the update buffer for filtering */
2083 tmpa
= p0
->make_tmp_attrs
? p0
->make_tmp_attrs(e
, rte_update_pool
) : NULL
;
2084 ok
= (d
->filter
== FILTER_ACCEPT
|| f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
2085 if (p2
&& p2
!= p0
) ok
= 0;
2086 if (ok
&& d
->export_mode
)
2089 if ((ic
= p1
->import_control
? p1
->import_control(p1
, &e
, &tmpa
, rte_update_pool
) : 0) < 0)
2091 else if (!ic
&& d
->export_mode
> 1)
2093 /* FIXME - this shows what should be exported according
2094 to current filters, but not what was really exported.
2095 'configure soft' command may change the export filter
2096 and do not update routes */
2098 if ((a
= proto_find_announce_hook(p1
, d
->table
)) && ((a
->out_filter
== FILTER_REJECT
) ||
2099 (a
->out_filter
&& f_run(a
->out_filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
)))
2107 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2115 rte_update_unlock();
2116 if (d
->primary_only
)
2122 rt_show_cont(struct cli
*c
)
2124 struct rt_show_data
*d
= c
->rover
;
2130 struct fib
*fib
= &d
->table
->fib
;
2131 struct fib_iterator
*it
= &d
->fit
;
2133 FIB_ITERATE_START(fib
, it
, f
)
2136 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2138 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2141 if (d
->export_protocol
&&
2142 d
->export_protocol
->core_state
!= FS_HAPPY
&&
2143 d
->export_protocol
->core_state
!= FS_FEEDING
)
2145 cli_printf(c
, 8005, "Protocol is down");
2150 FIB_ITERATE_PUT(it
, f
);
2153 rt_show_net(c
, n
, d
);
2157 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2159 cli_printf(c
, 0, "");
2161 c
->cont
= c
->cleanup
= NULL
;
2165 rt_show_cleanup(struct cli
*c
)
2167 struct rt_show_data
*d
= c
->rover
;
2169 /* Unlink the iterator */
2170 fit_get(&d
->table
->fib
, &d
->fit
);
2174 rt_show(struct rt_show_data
*d
)
2178 if (d
->pxlen
== 256)
2180 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2181 this_cli
->cont
= rt_show_cont
;
2182 this_cli
->cleanup
= rt_show_cleanup
;
2183 this_cli
->rover
= d
;
2188 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2190 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2193 rt_show_net(this_cli
, n
, d
);
2197 cli_msg(8001, "Network not in table");
2202 * Documentation for functions declared inline in route.h
2207 * net_find - find a network entry
2208 * @tab: a routing table
2209 * @addr: address of the network
2210 * @len: length of the network prefix
2212 * net_find() looks up the given network in routing table @tab and
2213 * returns a pointer to its &net entry or %NULL if no such network
2216 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2220 * net_get - obtain a network entry
2221 * @tab: a routing table
2222 * @addr: address of the network
2223 * @len: length of the network prefix
2225 * net_get() looks up the given network in routing table @tab and
2226 * returns a pointer to its &net entry. If no such entry exists, it's
2229 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2233 * rte_cow - copy a route for writing
2234 * @r: a route entry to be copied
2236 * rte_cow() takes a &rte and prepares it for modification. The exact action
2237 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2238 * just returned unchanged, else a new temporary entry with the same contents
2241 * The primary use of this function is inside the filter machinery -- when
2242 * a filter wants to modify &rte contents (to change the preference or to
2243 * attach another set of attributes), it must ensure that the &rte is not
2244 * shared with anyone else (and especially that it isn't stored in any routing
2247 * Result: a pointer to the new writable &rte.
2249 static inline rte
* rte_cow(rte
*r
)