]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-table.c
2 * BIRD -- Routing Tables
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
12 * Routing tables are probably the most important structures BIRD uses. They
13 * hold all the information about known networks, the associated routes and
16 * There are multiple routing tables (a primary one together with any
17 * number of secondary ones if requested by the configuration). Each table
18 * is basically a FIB containing entries describing the individual
19 * destination networks. For each network (represented by structure &net),
20 * there is a one-way linked list of route entries (&rte), the first entry
21 * on the list being the best one (i.e., the one we currently use
22 * for routing), the order of the other ones is undetermined.
24 * The &rte contains information specific to the route (preference, protocol
25 * metrics, time of last modification etc.) and a pointer to a &rta structure
26 * (see the route attribute module for a precise explanation) holding the
27 * remaining route attributes which are expected to be shared by multiple
28 * routes in order to conserve memory.
33 #include "nest/bird.h"
34 #include "nest/route.h"
35 #include "nest/protocol.h"
37 #include "nest/iface.h"
38 #include "lib/resource.h"
39 #include "lib/event.h"
40 #include "lib/string.h"
41 #include "conf/conf.h"
42 #include "filter/filter.h"
43 #include "lib/string.h"
44 #include "lib/alloca.h"
48 static slab
*rte_slab
;
49 static linpool
*rte_update_pool
;
51 static list routing_tables
;
53 static void rt_format_via(rte
*e
, byte
*via
);
54 static void rt_free_hostcache(rtable
*tab
);
55 static void rt_notify_hostcache(rtable
*tab
, net
*net
);
56 static void rt_update_hostcache(rtable
*tab
);
57 static void rt_next_hop_update(rtable
*tab
);
58 static inline int rt_prune_table(rtable
*tab
);
59 static inline void rt_schedule_gc(rtable
*tab
);
60 static inline void rt_schedule_prune(rtable
*tab
);
63 static inline struct ea_list
*
64 make_tmp_attrs(struct rte
*rt
, struct linpool
*pool
)
66 struct ea_list
*(*mta
)(struct rte
*rt
, struct linpool
*pool
);
67 mta
= rt
->attrs
->src
->proto
->make_tmp_attrs
;
68 return mta
? mta(rt
, rte_update_pool
) : NULL
;
71 /* Like fib_route(), but skips empty net entries */
73 net_route(rtable
*tab
, ip_addr a
, int len
)
80 a0
= ipa_and(a
, ipa_mkmask(len
));
81 n
= fib_find(&tab
->fib
, &a0
, len
);
82 if (n
&& rte_is_valid(n
->routes
))
90 rte_init(struct fib_node
*N
)
99 * rte_find - find a route
103 * The rte_find() function returns a route for destination @net
104 * which is from route source @src.
107 rte_find(net
*net
, struct rte_src
*src
)
109 rte
*e
= net
->routes
;
111 while (e
&& e
->attrs
->src
!= src
)
117 * rte_get_temp - get a temporary &rte
118 * @a: attributes to assign to the new route (a &rta; in case it's
119 * un-cached, rte_update() will create a cached copy automatically)
121 * Create a temporary &rte and bind it with the attributes @a.
122 * Also set route preference to the default preference set for
128 rte
*e
= sl_alloc(rte_slab
);
132 e
->pref
= a
->src
->proto
->preference
;
139 rte
*e
= sl_alloc(rte_slab
);
141 memcpy(e
, r
, sizeof(rte
));
142 e
->attrs
= rta_clone(r
->attrs
);
147 static int /* Actually better or at least as good as */
148 rte_better(rte
*new, rte
*old
)
150 int (*better
)(rte
*, rte
*);
152 if (!rte_is_valid(old
))
154 if (!rte_is_valid(new))
157 if (new->pref
> old
->pref
)
159 if (new->pref
< old
->pref
)
161 if (new->attrs
->src
->proto
->proto
!= old
->attrs
->src
->proto
->proto
)
164 * If the user has configured protocol preferences, so that two different protocols
165 * have the same preference, try to break the tie by comparing addresses. Not too
166 * useful, but keeps the ordering of routes unambiguous.
168 return new->attrs
->src
->proto
->proto
> old
->attrs
->src
->proto
->proto
;
170 if (better
= new->attrs
->src
->proto
->rte_better
)
171 return better(new, old
);
176 rte_trace(struct proto
*p
, rte
*e
, int dir
, char *msg
)
178 byte via
[STD_ADDRESS_P_LENGTH
+32];
180 rt_format_via(e
, via
);
181 log(L_TRACE
"%s %c %s %I/%d %s", p
->name
, dir
, msg
, e
->net
->n
.prefix
, e
->net
->n
.pxlen
, via
);
185 rte_trace_in(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
188 rte_trace(p
, e
, '>', msg
);
192 rte_trace_out(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
195 rte_trace(p
, e
, '<', msg
);
199 export_filter(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
201 struct proto
*p
= ah
->proto
;
202 struct filter
*filter
= ah
->out_filter
;
203 struct proto_stats
*stats
= ah
->stats
;
204 ea_list
*tmpb
= NULL
;
214 *tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
216 v
= p
->import_control
? p
->import_control(p
, &rt
, tmpa
, rte_update_pool
) : 0;
222 stats
->exp_updates_rejected
++;
224 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
230 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
234 v
= filter
&& ((filter
== FILTER_REJECT
) ||
235 (f_run(filter
, &rt
, tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
));
241 stats
->exp_updates_filtered
++;
242 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
252 /* Discard temporary rte */
259 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
261 struct proto
*p
= ah
->proto
;
262 struct proto_stats
*stats
= ah
->stats
;
266 * First, apply export limit.
268 * Export route limits has several problems. Because exp_routes
269 * counter is reset before refeed, we don't really know whether
270 * limit is breached and whether the update is new or not. Therefore
271 * the number of really exported routes may exceed the limit
272 * temporarily (routes exported before and new routes in refeed).
274 * Minor advantage is that if the limit is decreased and refeed is
275 * requested, the number of exported routes really decrease.
277 * Second problem is that with export limits, we don't know whether
278 * old was really exported (it might be blocked by limit). When a
279 * withdraw is exported, we announce it even when the previous
280 * update was blocked. This is not a big issue, but the same problem
281 * is in updating exp_routes counter. Therefore, to be consistent in
282 * increases and decreases of exp_routes, we count exported routes
283 * regardless of blocking by limits.
285 * Similar problem is in handling updates - when a new route is
286 * received and blocking is active, the route would be blocked, but
287 * when an update for the route will be received later, the update
288 * would be propagated (as old != NULL). Therefore, we have to block
289 * also non-new updates (contrary to import blocking).
292 struct proto_limit
*l
= ah
->out_limit
;
295 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
296 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
298 if (l
->state
== PLS_BLOCKED
)
300 stats
->exp_routes
++; /* see note above */
301 stats
->exp_updates_rejected
++;
302 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
312 stats
->exp_updates_accepted
++;
314 stats
->exp_withdraws_accepted
++;
316 /* Hack: We do not decrease exp_routes during refeed, we instead
317 reset exp_routes at the start of refeed. */
323 if (p
->debug
& D_ROUTES
)
326 rte_trace_out(D_ROUTES
, p
, new, "replaced");
328 rte_trace_out(D_ROUTES
, p
, new, "added");
330 rte_trace_out(D_ROUTES
, p
, old
, "removed");
333 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
339 t
->next
= new->attrs
->eattrs
;
340 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
344 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
348 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new0
, rte
*old0
, int refeed
)
350 struct proto
*p
= ah
->proto
;
351 struct proto_stats
*stats
= ah
->stats
;
355 rte
*new_free
= NULL
;
356 rte
*old_free
= NULL
;
357 ea_list
*tmpa
= NULL
;
360 stats
->exp_updates_received
++;
362 stats
->exp_withdraws_received
++;
365 * This is a tricky part - we don't know whether route 'old' was
366 * exported to protocol 'p' or was filtered by the export filter.
367 * We try to run the export filter to know this to have a correct
368 * value in 'old' argument of rte_update (and proper filter value)
370 * FIXME - this is broken because 'configure soft' may change
371 * filters but keep routes. Refeed is expected to be called after
372 * change of the filters and with old == new, therefore we do not
373 * even try to run the filter on an old route, This may lead to
374 * 'spurious withdraws' but ensure that there are no 'missing
377 * This is not completely safe as there is a window between
378 * reconfiguration and the end of refeed - if a newly filtered
379 * route disappears during this period, proper withdraw is not
380 * sent (because old would be also filtered) and the route is
381 * not refeeded (because it disappeared before that).
385 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
388 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
393 * As mentioned above, 'old' value may be incorrect in some race conditions.
394 * We generally ignore it with the exception of withdraw to pipe protocol.
395 * In that case we rather propagate unfiltered withdraws regardless of
396 * export filters to ensure that when a protocol is flushed, its routes are
397 * removed from all tables. Possible spurious unfiltered withdraws are not
398 * problem here as they are ignored if there is no corresponding route at
399 * the other end of the pipe. We directly call rt_notify() hook instead of
400 * do_rt_notify() to avoid logging and stat counters.
404 if ((p
->proto
== &proto_pipe
) && !new0
&& (p
!= old0
->sender
->proto
))
405 p
->rt_notify(p
, ah
->table
, net
, NULL
, old0
, NULL
);
411 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
413 /* Discard temporary rte's */
421 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
, int feed
)
423 // struct proto *p = ah->proto;
424 struct proto_stats
*stats
= ah
->stats
;
427 rte
*new_best
= NULL
;
428 rte
*old_best
= NULL
;
429 rte
*new_free
= NULL
;
430 rte
*old_free
= NULL
;
431 ea_list
*tmpa
= NULL
;
433 /* Used to track whether we met old_changed position. If before_old is NULL
434 old_changed was the first and we met it implicitly before current best route. */
435 int old_meet
= old_changed
&& !before_old
;
437 /* Note that before_old is either NULL or valid (not rejected) route.
438 If old_changed is valid, before_old have to be too. If old changed route
439 was not valid, caller must use NULL for both old_changed and before_old. */
442 stats
->exp_updates_received
++;
444 stats
->exp_withdraws_received
++;
446 /* First, find the new_best route - first accepted by filters */
447 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
449 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
452 /* Note if we walked around the position of old_changed route */
458 * Second, handle the feed case. That means we do not care for
459 * old_best. It is NULL for feed, and the new_best for refeed.
460 * For refeed, there is a hack similar to one in rt_notify_basic()
461 * to ensure withdraws in case of changed filters
465 if (feed
== 2) /* refeed */
466 old_best
= new_best
? new_best
:
467 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
471 if (!new_best
&& !old_best
)
478 * Now, we find the old_best route. Generally, it is the same as the
479 * new_best, unless new_best is the same as new_changed or
480 * old_changed is accepted before new_best.
482 * There are four cases:
484 * - We would find and accept old_changed before new_best, therefore
485 * old_changed is old_best. In remaining cases we suppose this
488 * - We found no new_best, therefore there is also no old_best and
489 * we ignore this withdraw.
491 * - We found new_best different than new_changed, therefore
492 * old_best is the same as new_best and we ignore this update.
494 * - We found new_best the same as new_changed, therefore it cannot
495 * be old_best and we have to continue search for old_best.
500 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
507 /* Third case, we use r instead of new_best, because export_filter() could change it */
508 if (r
!= new_changed
)
516 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
518 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
522 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
526 /* Implicitly, old_best is NULL and new_best is non-NULL */
529 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
531 /* Discard temporary rte's */
539 * rte_announce - announce a routing table change
540 * @tab: table the route has been added to
541 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
542 * @net: network in question
543 * @new: the new route to be announced
544 * @old: the previous route for the same network
546 * This function gets a routing table update and announces it
547 * to all protocols that acccepts given type of route announcement
548 * and are connected to the same table by their announcement hooks.
550 * Route announcement of type RA_OPTIMAL si generated when optimal
551 * route (in routing table @tab) changes. In that case @old stores the
554 * Route announcement of type RA_ANY si generated when any route (in
555 * routing table @tab) changes In that case @old stores the old route
556 * from the same protocol.
558 * For each appropriate protocol, we first call its import_control()
559 * hook which performs basic checks on the route (each protocol has a
560 * right to veto or force accept of the route before any filter is
561 * asked) and adds default values of attributes specific to the new
562 * protocol (metrics, tags etc.). Then it consults the protocol's
563 * export filter and if it accepts the route, the rt_notify() hook of
564 * the protocol gets called.
567 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
, rte
*before_old
)
569 if (!rte_is_valid(old
))
570 old
= before_old
= NULL
;
572 if (!rte_is_valid(new))
578 if (type
== RA_OPTIMAL
)
581 new->attrs
->src
->proto
->stats
.pref_routes
++;
583 old
->attrs
->src
->proto
->stats
.pref_routes
--;
586 rt_notify_hostcache(tab
, net
);
589 struct announce_hook
*a
;
590 WALK_LIST(a
, tab
->hooks
)
592 ASSERT(a
->proto
->export_state
!= ES_DOWN
);
593 if (a
->proto
->accept_ra_types
== type
)
594 if (type
== RA_ACCEPTED
)
595 rt_notify_accepted(a
, net
, new, old
, before_old
, 0);
597 rt_notify_basic(a
, net
, new, old
, 0);
607 if ((n
->n
.pxlen
> BITS_PER_IP_ADDRESS
) || !ip_is_prefix(n
->n
.prefix
,n
->n
.pxlen
))
609 log(L_WARN
"Ignoring bogus prefix %I/%d received via %s",
610 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
614 c
= ipa_classify_net(n
->n
.prefix
);
615 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
617 log(L_WARN
"Ignoring bogus route %I/%d received via %s",
618 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
626 * rte_free - delete a &rte
627 * @e: &rte to be deleted
629 * rte_free() deletes the given &rte from the routing table it's linked to.
634 if (rta_is_cached(e
->attrs
))
636 sl_free(rte_slab
, e
);
640 rte_free_quick(rte
*e
)
643 sl_free(rte_slab
, e
);
647 rte_same(rte
*x
, rte
*y
)
650 x
->attrs
== y
->attrs
&&
651 x
->flags
== y
->flags
&&
652 x
->pflags
== y
->pflags
&&
653 x
->pref
== y
->pref
&&
654 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
657 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
660 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
662 struct proto
*p
= ah
->proto
;
663 struct rtable
*table
= ah
->table
;
664 struct proto_stats
*stats
= ah
->stats
;
665 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
666 rte
*before_old
= NULL
;
667 rte
*old_best
= net
->routes
;
671 k
= &net
->routes
; /* Find and remove original route from the same protocol */
674 if (old
->attrs
->src
== src
)
676 /* If there is the same route in the routing table but from
677 * a different sender, then there are two paths from the
678 * source protocol to this routing table through transparent
679 * pipes, which is not allowed.
681 * We log that and ignore the route. If it is withdraw, we
682 * ignore it completely (there might be 'spurious withdraws',
683 * see FIXME in do_rte_announce())
685 if (old
->sender
->proto
!= p
)
689 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %I/%d to table %s",
690 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
696 if (new && rte_same(old
, new))
698 /* No changes, ignore the new route */
700 if (!rte_is_filtered(new))
702 stats
->imp_updates_ignored
++;
703 rte_trace_in(D_ROUTES
, p
, new, "ignored");
708 /* lastmod is used internally by RIP as the last time
709 when the route was received. */
710 if (src
->proto
->proto
== &proto_rip
)
727 stats
->imp_withdraws_ignored
++;
731 int new_ok
= rte_is_ok(new);
732 int old_ok
= rte_is_ok(old
);
734 struct proto_limit
*l
= ah
->rx_limit
;
735 if (l
&& !old
&& new)
737 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
739 if (all_routes
>= l
->limit
)
740 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
742 if (l
->state
== PLS_BLOCKED
)
744 /* In receive limit the situation is simple, old is NULL so
745 we just free new and exit like nothing happened */
747 stats
->imp_updates_ignored
++;
748 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
755 if (l
&& !old_ok
&& new_ok
)
757 if (stats
->imp_routes
>= l
->limit
)
758 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
760 if (l
->state
== PLS_BLOCKED
)
762 /* In import limit the situation is more complicated. We
763 shouldn't just drop the route, we should handle it like
764 it was filtered. We also have to continue the route
765 processing if old or new is non-NULL, but we should exit
766 if both are NULL as this case is probably assumed to be
769 stats
->imp_updates_ignored
++;
770 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
772 if (ah
->in_keep_filtered
)
773 new->flags
|= REF_FILTERED
;
775 { rte_free_quick(new); new = NULL
; }
777 /* Note that old && !new could be possible when
778 ah->in_keep_filtered changed in the recent past. */
789 stats
->imp_updates_accepted
++;
791 stats
->imp_withdraws_accepted
++;
793 stats
->imp_withdraws_ignored
++;
798 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
800 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
802 if (table
->config
->sorted
)
804 /* If routes are sorted, just insert new route to appropriate position */
807 if (before_old
&& !rte_better(new, before_old
))
808 k
= &before_old
->next
;
812 for (; *k
; k
=&(*k
)->next
)
813 if (rte_better(new, *k
))
822 /* If routes are not sorted, find the best route and move it on
823 the first position. There are several optimized cases. */
825 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
828 if (new && rte_better(new, old_best
))
830 /* The first case - the new route is cleary optimal,
831 we link it at the first position */
833 new->next
= net
->routes
;
836 else if (old
== old_best
)
838 /* The second case - the old best route disappeared, we add the
839 new route (if we have any) to the list (we don't care about
840 position) and then we elect the new optimal route and relink
841 that route at the first position and announce it. New optimal
842 route might be NULL if there is no more routes */
845 /* Add the new route to the list */
848 new->next
= net
->routes
;
852 /* Find a new optimal route (if there is any) */
855 rte
**bp
= &net
->routes
;
856 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
857 if (rte_better(*k
, *bp
))
863 best
->next
= net
->routes
;
869 /* The third case - the new route is not better than the old
870 best route (therefore old_best != NULL) and the old best
871 route was not removed (therefore old_best == net->routes).
872 We just link the new route after the old best route. */
874 ASSERT(net
->routes
!= NULL
);
875 new->next
= net
->routes
->next
;
876 net
->routes
->next
= new;
878 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
884 /* Log the route change */
885 if (p
->debug
& D_ROUTES
)
888 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
892 rte_trace(p
, old
, '>', "removed");
893 else if (rte_is_ok(net
->routes
))
894 rte_trace(p
, old
, '>', "removed [replaced]");
896 rte_trace(p
, old
, '>', "removed [sole]");
900 /* Propagate the route change */
901 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
);
902 if (net
->routes
!= old_best
)
903 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
);
904 if (table
->config
->sorted
)
905 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, before_old
);
908 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
909 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
910 rt_schedule_gc(table
);
912 if (old_ok
&& p
->rte_remove
)
913 p
->rte_remove(net
, old
);
914 if (new_ok
&& p
->rte_insert
)
915 p
->rte_insert(net
, new);
921 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
924 rte_update_lock(void)
926 rte_update_nest_cnt
++;
930 rte_update_unlock(void)
932 if (!--rte_update_nest_cnt
)
933 lp_flush(rte_update_pool
);
937 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
939 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
941 *dummy
= net
->routes
;
942 net
->routes
= (*dummy
)->next
;
947 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
951 (*dummy
)->next
= net
->routes
;
952 net
->routes
= *dummy
;
957 * rte_update - enter a new update to a routing table
958 * @table: table to be updated
959 * @ah: pointer to table announce hook
961 * @p: protocol submitting the update
962 * @src: protocol originating the update
963 * @new: a &rte representing the new route or %NULL for route removal.
965 * This function is called by the routing protocols whenever they discover
966 * a new route or wish to update/remove an existing route. The right announcement
967 * sequence is to build route attributes first (either un-cached with @aflags set
968 * to zero or a cached one using rta_lookup(); in this case please note that
969 * you need to increase the use count of the attributes yourself by calling
970 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
971 * the appropriate data and finally submit the new &rte by calling rte_update().
973 * @src specifies the protocol that originally created the route and the meaning
974 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
975 * same value as @new->attrs->proto. @p specifies the protocol that called
976 * rte_update(). In most cases it is the same protocol as @src. rte_update()
977 * stores @p in @new->sender;
979 * When rte_update() gets any route, it automatically validates it (checks,
980 * whether the network and next hop address are valid IP addresses and also
981 * whether a normal routing protocol doesn't try to smuggle a host or link
982 * scope route to the table), converts all protocol dependent attributes stored
983 * in the &rte to temporary extended attributes, consults import filters of the
984 * protocol to see if the route should be accepted and/or its attributes modified,
985 * stores the temporary attributes back to the &rte.
987 * Now, having a "public" version of the route, we
988 * automatically find any old route defined by the protocol @src
989 * for network @n, replace it by the new one (or removing it if @new is %NULL),
990 * recalculate the optimal route for this destination and finally broadcast
991 * the change (if any) to all routing protocols by calling rte_announce().
993 * All memory used for attribute lists and other temporary allocations is taken
994 * from a special linear pool @rte_update_pool and freed when rte_update()
999 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
1001 struct proto
*p
= ah
->proto
;
1002 struct proto_stats
*stats
= ah
->stats
;
1003 struct filter
*filter
= ah
->in_filter
;
1004 ea_list
*tmpa
= NULL
;
1012 stats
->imp_updates_received
++;
1013 if (!rte_validate(new))
1015 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1016 stats
->imp_updates_invalid
++;
1020 if (filter
== FILTER_REJECT
)
1022 stats
->imp_updates_filtered
++;
1023 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1025 if (! ah
->in_keep_filtered
)
1028 /* new is a private copy, i could modify it */
1029 new->flags
|= REF_FILTERED
;
1033 tmpa
= make_tmp_attrs(new, rte_update_pool
);
1034 if (filter
&& (filter
!= FILTER_REJECT
))
1036 ea_list
*old_tmpa
= tmpa
;
1037 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
1040 stats
->imp_updates_filtered
++;
1041 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1043 if (! ah
->in_keep_filtered
)
1046 new->flags
|= REF_FILTERED
;
1048 if (tmpa
!= old_tmpa
&& src
->proto
->store_tmp_attrs
)
1049 src
->proto
->store_tmp_attrs(new, tmpa
);
1052 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1053 new->attrs
= rta_lookup(new->attrs
);
1054 new->flags
|= REF_COW
;
1058 stats
->imp_withdraws_received
++;
1062 stats
->imp_withdraws_ignored
++;
1063 rte_update_unlock();
1069 rte_hide_dummy_routes(net
, &dummy
);
1070 rte_recalculate(ah
, net
, new, src
);
1071 rte_unhide_dummy_routes(net
, &dummy
);
1072 rte_update_unlock();
1081 /* Independent call to rte_announce(), used from next hop
1082 recalculation, outside of rte_update(). new must be non-NULL */
1084 rte_announce_i(rtable
*tab
, unsigned type
, net
*n
, rte
*new, rte
*old
)
1087 rte_announce(tab
, type
, n
, new, old
, NULL
);
1088 rte_update_unlock();
1092 rte_discard(rtable
*t
, rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1095 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1096 rte_update_unlock();
1099 /* Check rtable for best route to given net whether it would be exported do p */
1101 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1103 net
*n
= net_find(t
, prefix
, pxlen
);
1104 rte
*rt
= n
? n
->routes
: NULL
;
1106 if (!rte_is_valid(rt
))
1111 /* Rest is stripped down export_filter() */
1112 ea_list
*tmpa
= make_tmp_attrs(rt
, rte_update_pool
);
1113 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1114 if (v
== RIC_PROCESS
)
1115 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
1117 /* Discard temporary rte */
1118 if (rt
!= n
->routes
)
1121 rte_update_unlock();
1128 * rt_refresh_begin - start a refresh cycle
1129 * @t: related routing table
1130 * @ah: related announce hook
1132 * This function starts a refresh cycle for given routing table and announce
1133 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1134 * routes to the routing table (by rte_update()). After that, all protocol
1135 * routes (more precisely routes with @ah as @sender) not sent during the
1136 * refresh cycle but still in the table from the past are pruned. This is
1137 * implemented by marking all related routes as stale by REF_STALE flag in
1138 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1139 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1142 rt_refresh_begin(rtable
*t
, struct announce_hook
*ah
)
1147 FIB_WALK(&t
->fib
, fn
)
1150 for (e
= n
->routes
; e
; e
= e
->next
)
1151 if (e
->sender
== ah
)
1152 e
->flags
|= REF_STALE
;
1158 * rt_refresh_end - end a refresh cycle
1159 * @t: related routing table
1160 * @ah: related announce hook
1162 * This function starts a refresh cycle for given routing table and announce
1163 * hook. See rt_refresh_begin() for description of refresh cycles.
1166 rt_refresh_end(rtable
*t
, struct announce_hook
*ah
)
1172 FIB_WALK(&t
->fib
, fn
)
1175 for (e
= n
->routes
; e
; e
= e
->next
)
1176 if ((e
->sender
== ah
) && (e
->flags
& REF_STALE
))
1178 e
->flags
|= REF_DISCARD
;
1185 rt_schedule_prune(t
);
1190 * rte_dump - dump a route
1191 * @e: &rte to be dumped
1193 * This functions dumps contents of a &rte to debug output.
1199 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1200 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1202 if (e
->attrs
->src
->proto
->proto
->dump_attrs
)
1203 e
->attrs
->src
->proto
->proto
->dump_attrs(e
);
1208 * rt_dump - dump a routing table
1209 * @t: routing table to be dumped
1211 * This function dumps contents of a given routing table to debug output.
1218 struct announce_hook
*a
;
1220 debug("Dump of routing table <%s>\n", t
->name
);
1224 FIB_WALK(&t
->fib
, fn
)
1227 for(e
=n
->routes
; e
; e
=e
->next
)
1231 WALK_LIST(a
, t
->hooks
)
1232 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1237 * rt_dump_all - dump all routing tables
1239 * This function dumps contents of all routing tables to debug output.
1246 WALK_LIST(t
, routing_tables
)
1251 rt_schedule_prune(rtable
*tab
)
1253 rt_mark_for_prune(tab
);
1254 ev_schedule(tab
->rt_event
);
1258 rt_schedule_gc(rtable
*tab
)
1260 if (tab
->gc_scheduled
)
1263 tab
->gc_scheduled
= 1;
1264 ev_schedule(tab
->rt_event
);
1268 rt_schedule_hcu(rtable
*tab
)
1270 if (tab
->hcu_scheduled
)
1273 tab
->hcu_scheduled
= 1;
1274 ev_schedule(tab
->rt_event
);
1278 rt_schedule_nhu(rtable
*tab
)
1280 if (tab
->nhu_state
== 0)
1281 ev_schedule(tab
->rt_event
);
1283 /* state change 0->1, 2->3 */
1284 tab
->nhu_state
|= 1;
1289 rt_prune_nets(rtable
*tab
)
1291 struct fib_iterator fit
;
1292 int ncnt
= 0, ndel
= 0;
1295 fib_check(&tab
->fib
);
1298 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1300 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1304 if (!n
->routes
) /* Orphaned FIB entry */
1306 FIB_ITERATE_PUT(&fit
, f
);
1307 fib_delete(&tab
->fib
, f
);
1313 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1315 tab
->gc_counter
= 0;
1317 tab
->gc_scheduled
= 0;
1325 if (tab
->hcu_scheduled
)
1326 rt_update_hostcache(tab
);
1329 rt_next_hop_update(tab
);
1331 if (tab
->prune_state
)
1332 if (!rt_prune_table(tab
))
1334 /* Table prune unfinished */
1335 ev_schedule(tab
->rt_event
);
1339 if (tab
->gc_scheduled
)
1342 rt_prune_sources(); // FIXME this should be moved to independent event
1347 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1349 bzero(t
, sizeof(*t
));
1350 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1353 init_list(&t
->hooks
);
1356 t
->rt_event
= ev_new(p
);
1357 t
->rt_event
->hook
= rt_event
;
1358 t
->rt_event
->data
= t
;
1364 * rt_init - initialize routing tables
1366 * This function is called during BIRD startup. It initializes the
1367 * routing table module.
1373 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1374 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1375 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1376 init_list(&routing_tables
);
1381 rt_prune_step(rtable
*tab
, int *limit
)
1383 struct fib_iterator
*fit
= &tab
->prune_fit
;
1385 DBG("Pruning route table %s\n", tab
->name
);
1387 fib_check(&tab
->fib
);
1390 if (tab
->prune_state
== RPS_NONE
)
1393 if (tab
->prune_state
== RPS_SCHEDULED
)
1395 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1396 tab
->prune_state
= RPS_RUNNING
;
1400 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1402 net
*n
= (net
*) fn
;
1406 for (e
=n
->routes
; e
; e
=e
->next
)
1407 if (e
->sender
->proto
->flushing
|| (e
->flags
& REF_DISCARD
))
1411 FIB_ITERATE_PUT(fit
, fn
);
1415 rte_discard(tab
, e
);
1420 if (!n
->routes
) /* Orphaned FIB entry */
1422 FIB_ITERATE_PUT(fit
, fn
);
1423 fib_delete(&tab
->fib
, fn
);
1427 FIB_ITERATE_END(fn
);
1430 fib_check(&tab
->fib
);
1433 tab
->prune_state
= RPS_NONE
;
1438 * rt_prune_table - prune a routing table
1440 * This function scans the routing table @tab and removes routes belonging to
1441 * flushing protocols, discarded routes and also stale network entries, in a
1442 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1443 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1444 * protocol flushing loop, but it is called from rt_event() for just one routing
1447 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1448 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1451 rt_prune_table(rtable
*tab
)
1454 return rt_prune_step(tab
, &limit
);
1458 * rt_prune_loop - prune routing tables
1460 * The prune loop scans routing tables and removes routes belonging to flushing
1461 * protocols, discarded routes and also stale network entries. Returns 1 when
1462 * all such routes are pruned. It is a part of the protocol flushing loop.
1470 WALK_LIST(t
, routing_tables
)
1471 if (! rt_prune_step(t
, &limit
))
1478 rt_preconfig(struct config
*c
)
1480 struct symbol
*s
= cf_find_symbol("master");
1482 init_list(&c
->tables
);
1483 c
->master_rtc
= rt_new_table(s
);
1488 * Some functions for handing internal next hop updates
1489 * triggered by rt_schedule_nhu().
1493 rta_next_hop_outdated(rta
*a
)
1495 struct hostentry
*he
= a
->hostentry
;
1501 return a
->dest
!= RTD_UNREACHABLE
;
1503 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1504 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1505 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1509 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1512 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1515 a
->igp_metric
= he
->igp_metric
;
1516 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1520 rt_next_hop_update_rte(rtable
*tab
, rte
*old
)
1523 memcpy(&a
, old
->attrs
, sizeof(rta
));
1524 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1527 rte
*e
= sl_alloc(rte_slab
);
1528 memcpy(e
, old
, sizeof(rte
));
1529 e
->attrs
= rta_lookup(&a
);
1535 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1537 rte
**k
, *e
, *new, *old_best
, **new_best
;
1539 int free_old_best
= 0;
1541 old_best
= n
->routes
;
1545 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1546 if (rta_next_hop_outdated(e
->attrs
))
1548 new = rt_next_hop_update_rte(tab
, e
);
1551 rte_announce_i(tab
, RA_ANY
, n
, new, e
);
1552 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1554 /* Call a pre-comparison hook */
1555 /* Not really an efficient way to compute this */
1556 if (e
->attrs
->src
->proto
->rte_recalculate
)
1557 e
->attrs
->src
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1561 else /* Freeing of the old best rte is postponed */
1571 /* Find the new best route */
1573 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1575 if (!new_best
|| rte_better(e
, *new_best
))
1579 /* Relink the new best route to the first position */
1581 if (new != n
->routes
)
1583 *new_best
= new->next
;
1584 new->next
= n
->routes
;
1588 /* Announce the new best route */
1589 if (new != old_best
)
1591 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
);
1592 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1596 rte_free_quick(old_best
);
1602 rt_next_hop_update(rtable
*tab
)
1604 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1607 if (tab
->nhu_state
== 0)
1610 if (tab
->nhu_state
== 1)
1612 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1616 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1620 FIB_ITERATE_PUT(fit
, fn
);
1621 ev_schedule(tab
->rt_event
);
1624 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1626 FIB_ITERATE_END(fn
);
1628 /* state change 2->0, 3->1 */
1629 tab
->nhu_state
&= 1;
1631 if (tab
->nhu_state
> 0)
1632 ev_schedule(tab
->rt_event
);
1636 struct rtable_config
*
1637 rt_new_table(struct symbol
*s
)
1639 /* Hack that allows to 'redefine' the master table */
1640 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1643 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1645 cf_define_symbol(s
, SYM_TABLE
, c
);
1647 add_tail(&new_config
->tables
, &c
->n
);
1648 c
->gc_max_ops
= 1000;
1654 * rt_lock_table - lock a routing table
1655 * @r: routing table to be locked
1657 * Lock a routing table, because it's in use by a protocol,
1658 * preventing it from being freed when it gets undefined in a new
1662 rt_lock_table(rtable
*r
)
1668 * rt_unlock_table - unlock a routing table
1669 * @r: routing table to be unlocked
1671 * Unlock a routing table formerly locked by rt_lock_table(),
1672 * that is decrease its use count and delete it if it's scheduled
1673 * for deletion by configuration changes.
1676 rt_unlock_table(rtable
*r
)
1678 if (!--r
->use_count
&& r
->deleted
)
1680 struct config
*conf
= r
->deleted
;
1681 DBG("Deleting routing table %s\n", r
->name
);
1683 rt_free_hostcache(r
);
1688 config_del_obstacle(conf
);
1693 * rt_commit - commit new routing table configuration
1694 * @new: new configuration
1695 * @old: original configuration or %NULL if it's boot time config
1697 * Scan differences between @old and @new configuration and modify
1698 * the routing tables according to these changes. If @new defines a
1699 * previously unknown table, create it, if it omits a table existing
1700 * in @old, schedule it for deletion (it gets deleted when all protocols
1701 * disconnect from it by calling rt_unlock_table()), if it exists
1702 * in both configurations, leave it unchanged.
1705 rt_commit(struct config
*new, struct config
*old
)
1707 struct rtable_config
*o
, *r
;
1709 DBG("rt_commit:\n");
1712 WALK_LIST(o
, old
->tables
)
1714 rtable
*ot
= o
->table
;
1717 struct symbol
*sym
= cf_find_symbol(o
->name
);
1718 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1720 DBG("\t%s: same\n", o
->name
);
1725 if (o
->sorted
!= r
->sorted
)
1726 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1730 DBG("\t%s: deleted\n", o
->name
);
1732 config_add_obstacle(old
);
1734 rt_unlock_table(ot
);
1740 WALK_LIST(r
, new->tables
)
1743 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1744 DBG("\t%s: created\n", r
->name
);
1745 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1746 add_tail(&routing_tables
, &t
->n
);
1753 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1756 if (type
== RA_ACCEPTED
)
1757 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, p
->refeeding
? 2 : 1);
1759 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1760 rte_update_unlock();
1764 * rt_feed_baby - advertise routes to a new protocol
1765 * @p: protocol to be fed
1767 * This function performs one pass of advertisement of routes to a newly
1768 * initialized protocol. It's called by the protocol code as long as it
1769 * has something to do. (We avoid transferring all the routes in single
1770 * pass in order not to monopolize CPU time.)
1773 rt_feed_baby(struct proto
*p
)
1775 struct announce_hook
*h
;
1776 struct fib_iterator
*fit
;
1779 if (!p
->feed_ahook
) /* Need to initialize first */
1783 DBG("Announcing routes to new protocol %s\n", p
->name
);
1784 p
->feed_ahook
= p
->ahooks
;
1785 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1788 fit
= p
->feed_iterator
;
1792 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1794 net
*n
= (net
*) fn
;
1798 FIB_ITERATE_PUT(fit
, fn
);
1802 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1804 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
1805 (p
->accept_ra_types
== RA_ACCEPTED
))
1806 if (rte_is_valid(e
))
1808 if (p
->export_state
!= ES_FEEDING
)
1809 return 1; /* In the meantime, the protocol fell down. */
1811 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
1815 if (p
->accept_ra_types
== RA_ANY
)
1816 for(e
= n
->routes
; e
; e
= e
->next
)
1818 if (p
->export_state
!= ES_FEEDING
)
1819 return 1; /* In the meantime, the protocol fell down. */
1821 if (!rte_is_valid(e
))
1824 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
1828 FIB_ITERATE_END(fn
);
1829 p
->feed_ahook
= h
->next
;
1832 mb_free(p
->feed_iterator
);
1833 p
->feed_iterator
= NULL
;
1839 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
1844 * rt_feed_baby_abort - abort protocol feeding
1847 * This function is called by the protocol code when the protocol
1848 * stops or ceases to exist before the last iteration of rt_feed_baby()
1852 rt_feed_baby_abort(struct proto
*p
)
1856 /* Unlink the iterator and exit */
1857 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
1858 p
->feed_ahook
= NULL
;
1863 static inline unsigned
1866 uintptr_t p
= (uintptr_t) ptr
;
1867 return p
^ (p
<< 8) ^ (p
>> 16);
1870 static inline unsigned
1871 hc_hash(ip_addr a
, rtable
*dep
)
1873 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
1877 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
1879 uint k
= he
->hash_key
>> hc
->hash_shift
;
1880 he
->next
= hc
->hash_table
[k
];
1881 hc
->hash_table
[k
] = he
;
1885 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
1887 struct hostentry
**hep
;
1888 uint k
= he
->hash_key
>> hc
->hash_shift
;
1890 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
1894 #define HC_DEF_ORDER 10
1895 #define HC_HI_MARK *4
1896 #define HC_HI_STEP 2
1897 #define HC_HI_ORDER 16 /* Must be at most 16 */
1898 #define HC_LO_MARK /5
1899 #define HC_LO_STEP 2
1900 #define HC_LO_ORDER 10
1903 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
1905 unsigned hsize
= 1 << order
;
1906 hc
->hash_order
= order
;
1907 hc
->hash_shift
= 16 - order
;
1908 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0 : (hsize HC_HI_MARK
);
1909 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0 : (hsize HC_LO_MARK
);
1911 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
1915 hc_resize(struct hostcache
*hc
, unsigned new_order
)
1917 unsigned old_size
= 1 << hc
->hash_order
;
1918 struct hostentry
**old_table
= hc
->hash_table
;
1919 struct hostentry
*he
, *hen
;
1922 hc_alloc_table(hc
, new_order
);
1923 for (i
= 0; i
< old_size
; i
++)
1924 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
1932 static struct hostentry
*
1933 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
1935 struct hostentry
*he
= sl_alloc(hc
->slab
);
1944 add_tail(&hc
->hostentries
, &he
->ln
);
1948 if (hc
->hash_items
> hc
->hash_max
)
1949 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
1955 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
1961 sl_free(hc
->slab
, he
);
1964 if (hc
->hash_items
< hc
->hash_min
)
1965 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
1969 rt_init_hostcache(rtable
*tab
)
1971 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
1972 init_list(&hc
->hostentries
);
1975 hc_alloc_table(hc
, HC_DEF_ORDER
);
1976 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
1978 hc
->lp
= lp_new(rt_table_pool
, 1008);
1979 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
1981 tab
->hostcache
= hc
;
1985 rt_free_hostcache(rtable
*tab
)
1987 struct hostcache
*hc
= tab
->hostcache
;
1990 WALK_LIST(n
, hc
->hostentries
)
1992 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
1996 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
2001 mb_free(hc
->hash_table
);
2006 rt_notify_hostcache(rtable
*tab
, net
*net
)
2008 struct hostcache
*hc
= tab
->hostcache
;
2010 if (tab
->hcu_scheduled
)
2013 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
2014 rt_schedule_hcu(tab
);
2018 if_local_addr(ip_addr a
, struct iface
*i
)
2022 WALK_LIST(b
, i
->addrs
)
2023 if (ipa_equal(a
, b
->ip
))
2030 rt_get_igp_metric(rte
*rt
)
2032 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
2040 if ((a
->source
== RTS_OSPF
) ||
2041 (a
->source
== RTS_OSPF_IA
) ||
2042 (a
->source
== RTS_OSPF_EXT1
))
2043 return rt
->u
.ospf
.metric1
;
2047 if (a
->source
== RTS_RIP
)
2048 return rt
->u
.rip
.metric
;
2052 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
2055 return IGP_METRIC_UNKNOWN
;
2059 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
2061 rta
*old_src
= he
->src
;
2064 /* Reset the hostentry */
2067 he
->dest
= RTD_UNREACHABLE
;
2070 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
2079 /* Recursive route should not depend on another recursive route */
2080 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
2081 he
->addr
, n
->n
.prefix
, pxlen
);
2085 if (a
->dest
== RTD_DEVICE
)
2087 if (if_local_addr(he
->addr
, a
->iface
))
2089 /* The host address is a local address, this is not valid */
2090 log(L_WARN
"Next hop address %I is a local address of iface %s",
2091 he
->addr
, a
->iface
->name
);
2095 /* The host is directly reachable, use link as a gateway */
2097 he
->dest
= RTD_ROUTER
;
2101 /* The host is reachable through some route entry */
2106 he
->src
= rta_clone(a
);
2107 he
->igp_metric
= rt_get_igp_metric(e
);
2111 /* Add a prefix range to the trie */
2112 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
2115 return old_src
!= he
->src
;
2119 rt_update_hostcache(rtable
*tab
)
2121 struct hostcache
*hc
= tab
->hostcache
;
2122 struct hostentry
*he
;
2125 /* Reset the trie */
2127 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2129 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
2131 he
= SKIP_BACK(struct hostentry
, ln
, n
);
2134 hc_delete_hostentry(hc
, he
);
2138 if (rt_update_hostentry(tab
, he
))
2139 rt_schedule_nhu(he
->tab
);
2142 tab
->hcu_scheduled
= 0;
2145 static struct hostentry
*
2146 rt_get_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2148 struct hostentry
*he
;
2150 if (!tab
->hostcache
)
2151 rt_init_hostcache(tab
);
2153 uint k
= hc_hash(a
, dep
);
2154 struct hostcache
*hc
= tab
->hostcache
;
2155 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2156 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2159 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
2160 rt_update_hostentry(tab
, he
);
2165 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
2167 rta_apply_hostentry(a
, rt_get_hostentry(tab
, *gw
, *ll
, dep
));
2176 rt_format_via(rte
*e
, byte
*via
)
2182 case RTD_ROUTER
: bsprintf(via
, "via %I on %s", a
->gw
, a
->iface
->name
); break;
2183 case RTD_DEVICE
: bsprintf(via
, "dev %s", a
->iface
->name
); break;
2184 case RTD_BLACKHOLE
: bsprintf(via
, "blackhole"); break;
2185 case RTD_UNREACHABLE
: bsprintf(via
, "unreachable"); break;
2186 case RTD_PROHIBIT
: bsprintf(via
, "prohibited"); break;
2187 case RTD_MULTIPATH
: bsprintf(via
, "multipath"); break;
2188 default: bsprintf(via
, "???");
2193 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2195 byte via
[STD_ADDRESS_P_LENGTH
+32], from
[STD_ADDRESS_P_LENGTH
+8];
2196 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2198 int primary
= (e
->net
->routes
== e
);
2199 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2200 void (*get_route_info
)(struct rte
*, byte
*buf
, struct ea_list
*attrs
);
2203 rt_format_via(e
, via
);
2204 tm_format_datetime(tm
, &config
->tf_route
, e
->lastmod
);
2205 if (ipa_nonzero(a
->from
) && !ipa_equal(a
->from
, a
->gw
))
2206 bsprintf(from
, " from %I", a
->from
);
2210 get_route_info
= a
->src
->proto
->proto
->get_route_info
;
2211 if (get_route_info
|| d
->verbose
)
2213 /* Need to normalize the extended attributes */
2215 t
= ea_append(t
, a
->eattrs
);
2216 tmpa
= alloca(ea_scan(t
));
2221 get_route_info(e
, info
, tmpa
);
2223 bsprintf(info
, " (%d)", e
->pref
);
2224 cli_printf(c
, -1007, "%-18s %s [%s %s%s]%s%s", ia
, via
, a
->src
->proto
->name
,
2225 tm
, from
, primary
? (sync_error
? " !" : " *") : "", info
);
2226 for (nh
= a
->nexthops
; nh
; nh
= nh
->next
)
2227 cli_printf(c
, -1007, "\tvia %I on %s weight %d", nh
->gw
, nh
->iface
->name
, nh
->weight
+ 1);
2229 rta_show(c
, a
, tmpa
);
2233 rt_show_net(struct cli
*c
, net
*n
, struct rt_show_data
*d
)
2236 byte ia
[STD_ADDRESS_P_LENGTH
+8];
2237 struct ea_list
*tmpa
;
2238 struct announce_hook
*a
= NULL
;
2242 bsprintf(ia
, "%I/%d", n
->n
.prefix
, n
->n
.pxlen
);
2246 if (! d
->export_protocol
->rt_notify
)
2249 a
= proto_find_announce_hook(d
->export_protocol
, d
->table
);
2254 for (e
= n
->routes
; e
; e
= e
->next
)
2256 if (rte_is_filtered(e
) != d
->filtered
)
2260 d
->net_counter
+= first
;
2267 rte_update_lock(); /* We use the update buffer for filtering */
2268 tmpa
= make_tmp_attrs(e
, rte_update_pool
);
2272 struct proto
*ep
= d
->export_protocol
;
2273 int ic
= ep
->import_control
? ep
->import_control(ep
, &e
, &tmpa
, rte_update_pool
) : 0;
2275 if (ep
->accept_ra_types
== RA_OPTIMAL
)
2281 if (d
->export_mode
> RSEM_PREEXPORT
)
2284 * FIXME - This shows what should be exported according to current
2285 * filters, but not what was really exported. 'configure soft'
2286 * command may change the export filter and do not update routes.
2288 int do_export
= (ic
> 0) ||
2289 (f_run(a
->out_filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
2291 if (do_export
!= (d
->export_mode
== RSEM_EXPORT
))
2294 if ((d
->export_mode
== RSEM_EXPORT
) && (ep
->accept_ra_types
== RA_ACCEPTED
))
2299 if (d
->show_protocol
&& (d
->show_protocol
!= e
->attrs
->src
->proto
))
2302 if (f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
)
2307 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2316 rte_update_unlock();
2318 if (d
->primary_only
)
2324 rt_show_cont(struct cli
*c
)
2326 struct rt_show_data
*d
= c
->rover
;
2332 struct fib
*fib
= &d
->table
->fib
;
2333 struct fib_iterator
*it
= &d
->fit
;
2335 FIB_ITERATE_START(fib
, it
, f
)
2338 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2340 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2343 if (d
->export_protocol
&& (d
->export_protocol
->export_state
== ES_DOWN
))
2345 cli_printf(c
, 8005, "Protocol is down");
2350 FIB_ITERATE_PUT(it
, f
);
2353 rt_show_net(c
, n
, d
);
2357 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2359 cli_printf(c
, 0, "");
2361 c
->cont
= c
->cleanup
= NULL
;
2365 rt_show_cleanup(struct cli
*c
)
2367 struct rt_show_data
*d
= c
->rover
;
2369 /* Unlink the iterator */
2370 fit_get(&d
->table
->fib
, &d
->fit
);
2374 rt_show(struct rt_show_data
*d
)
2378 /* Default is either a master table or a table related to a respective protocol */
2379 if (!d
->table
&& d
->export_protocol
) d
->table
= d
->export_protocol
->table
;
2380 if (!d
->table
&& d
->show_protocol
) d
->table
= d
->show_protocol
->table
;
2381 if (!d
->table
) d
->table
= config
->master_rtc
->table
;
2383 /* Filtered routes are neither exported nor have sensible ordering */
2384 if (d
->filtered
&& (d
->export_mode
|| d
->primary_only
))
2387 if (d
->pxlen
== 256)
2389 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2390 this_cli
->cont
= rt_show_cont
;
2391 this_cli
->cleanup
= rt_show_cleanup
;
2392 this_cli
->rover
= d
;
2397 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2399 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2402 rt_show_net(this_cli
, n
, d
);
2407 cli_msg(8001, "Network not in table");
2412 * Documentation for functions declared inline in route.h
2417 * net_find - find a network entry
2418 * @tab: a routing table
2419 * @addr: address of the network
2420 * @len: length of the network prefix
2422 * net_find() looks up the given network in routing table @tab and
2423 * returns a pointer to its &net entry or %NULL if no such network
2426 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2430 * net_get - obtain a network entry
2431 * @tab: a routing table
2432 * @addr: address of the network
2433 * @len: length of the network prefix
2435 * net_get() looks up the given network in routing table @tab and
2436 * returns a pointer to its &net entry. If no such entry exists, it's
2439 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2443 * rte_cow - copy a route for writing
2444 * @r: a route entry to be copied
2446 * rte_cow() takes a &rte and prepares it for modification. The exact action
2447 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2448 * just returned unchanged, else a new temporary entry with the same contents
2451 * The primary use of this function is inside the filter machinery -- when
2452 * a filter wants to modify &rte contents (to change the preference or to
2453 * attach another set of attributes), it must ensure that the &rte is not
2454 * shared with anyone else (and especially that it isn't stored in any routing
2457 * Result: a pointer to the new writable &rte.
2459 static inline rte
* rte_cow(rte
*r
)