]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-table.c
2 * BIRD -- Routing Tables
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
12 * Routing tables are probably the most important structures BIRD uses. They
13 * hold all the information about known networks, the associated routes and
16 * There are multiple routing tables (a primary one together with any
17 * number of secondary ones if requested by the configuration). Each table
18 * is basically a FIB containing entries describing the individual
19 * destination networks. For each network (represented by structure &net),
20 * there is a one-way linked list of route entries (&rte), the first entry
21 * on the list being the best one (i.e., the one we currently use
22 * for routing), the order of the other ones is undetermined.
24 * The &rte contains information specific to the route (preference, protocol
25 * metrics, time of last modification etc.) and a pointer to a &rta structure
26 * (see the route attribute module for a precise explanation) holding the
27 * remaining route attributes which are expected to be shared by multiple
28 * routes in order to conserve memory.
33 #include "nest/bird.h"
34 #include "nest/route.h"
35 #include "nest/protocol.h"
37 #include "nest/iface.h"
38 #include "lib/resource.h"
39 #include "lib/event.h"
40 #include "lib/string.h"
41 #include "conf/conf.h"
42 #include "filter/filter.h"
43 #include "lib/string.h"
44 #include "lib/alloca.h"
48 static slab
*rte_slab
;
49 static linpool
*rte_update_pool
;
51 static list routing_tables
;
53 static byte
*rt_format_via(rte
*e
);
54 static void rt_free_hostcache(rtable
*tab
);
55 static void rt_notify_hostcache(rtable
*tab
, net
*net
);
56 static void rt_update_hostcache(rtable
*tab
);
57 static void rt_next_hop_update(rtable
*tab
);
58 static inline int rt_prune_table(rtable
*tab
);
59 static inline void rt_schedule_gc(rtable
*tab
);
60 static inline void rt_schedule_prune(rtable
*tab
);
63 /* Like fib_route(), but skips empty net entries */
65 net_route(rtable
*tab
, ip_addr a
, int len
)
72 a0
= ipa_and(a
, ipa_mkmask(len
));
73 n
= fib_find(&tab
->fib
, &a0
, len
);
74 if (n
&& rte_is_valid(n
->routes
))
82 rte_init(struct fib_node
*N
)
91 * rte_find - find a route
95 * The rte_find() function returns a route for destination @net
96 * which is from route source @src.
99 rte_find(net
*net
, struct rte_src
*src
)
101 rte
*e
= net
->routes
;
103 while (e
&& e
->attrs
->src
!= src
)
109 * rte_get_temp - get a temporary &rte
110 * @a: attributes to assign to the new route (a &rta; in case it's
111 * un-cached, rte_update() will create a cached copy automatically)
113 * Create a temporary &rte and bind it with the attributes @a.
114 * Also set route preference to the default preference set for
120 rte
*e
= sl_alloc(rte_slab
);
124 e
->pref
= a
->src
->proto
->preference
;
131 rte
*e
= sl_alloc(rte_slab
);
133 memcpy(e
, r
, sizeof(rte
));
134 e
->attrs
= rta_clone(r
->attrs
);
140 * rte_cow_rta - get a private writable copy of &rte with writable &rta
141 * @r: a route entry to be copied
142 * @lp: a linpool from which to allocate &rta
144 * rte_cow_rta() takes a &rte and prepares it and associated &rta for
145 * modification. There are three possibilities: First, both &rte and &rta are
146 * private copies, in that case they are returned unchanged. Second, &rte is
147 * private copy, but &rta is cached, in that case &rta is duplicated using
148 * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
149 * both structures are duplicated by rte_do_cow() and rta_do_cow().
151 * Note that in the second case, cached &rta loses one reference, while private
152 * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
153 * nexthops, ...) with it. To work properly, original shared &rta should have
154 * another reference during the life of created private copy.
156 * Result: a pointer to the new writable &rte with writable &rta.
159 rte_cow_rta(rte
*r
, linpool
*lp
)
161 if (!rta_is_cached(r
->attrs
))
165 rta
*a
= rta_do_cow(r
->attrs
, lp
);
171 static int /* Actually better or at least as good as */
172 rte_better(rte
*new, rte
*old
)
174 int (*better
)(rte
*, rte
*);
176 if (!rte_is_valid(old
))
178 if (!rte_is_valid(new))
181 if (new->pref
> old
->pref
)
183 if (new->pref
< old
->pref
)
185 if (new->attrs
->src
->proto
->proto
!= old
->attrs
->src
->proto
->proto
)
188 * If the user has configured protocol preferences, so that two different protocols
189 * have the same preference, try to break the tie by comparing addresses. Not too
190 * useful, but keeps the ordering of routes unambiguous.
192 return new->attrs
->src
->proto
->proto
> old
->attrs
->src
->proto
->proto
;
194 if (better
= new->attrs
->src
->proto
->rte_better
)
195 return better(new, old
);
200 rte_mergable(rte
*pri
, rte
*sec
)
202 int (*mergable
)(rte
*, rte
*);
204 if (!rte_is_valid(pri
) || !rte_is_valid(sec
))
207 if (pri
->pref
!= sec
->pref
)
210 if (pri
->attrs
->src
->proto
->proto
!= sec
->attrs
->src
->proto
->proto
)
213 if (mergable
= pri
->attrs
->src
->proto
->rte_mergable
)
214 return mergable(pri
, sec
);
220 rte_trace(struct proto
*p
, rte
*e
, int dir
, char *msg
)
222 log(L_TRACE
"%s %c %s %I/%d %s", p
->name
, dir
, msg
, e
->net
->n
.prefix
, e
->net
->n
.pxlen
, rt_format_via(e
));
226 rte_trace_in(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
229 rte_trace(p
, e
, '>', msg
);
233 rte_trace_out(uint flag
, struct proto
*p
, rte
*e
, char *msg
)
236 rte_trace(p
, e
, '<', msg
);
240 export_filter_(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, linpool
*pool
, int silent
)
242 struct proto
*p
= ah
->proto
;
243 struct filter
*filter
= ah
->out_filter
;
244 struct proto_stats
*stats
= ah
->stats
;
245 ea_list
*tmpb
= NULL
;
255 *tmpa
= rte_make_tmp_attrs(rt
, pool
);
257 v
= p
->import_control
? p
->import_control(p
, &rt
, tmpa
, pool
) : 0;
263 stats
->exp_updates_rejected
++;
265 rte_trace_out(D_FILTERS
, p
, rt
, "rejected by protocol");
271 rte_trace_out(D_FILTERS
, p
, rt
, "forced accept by protocol");
275 v
= filter
&& ((filter
== FILTER_REJECT
) ||
276 (f_run(filter
, &rt
, tmpa
, pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
));
282 stats
->exp_updates_filtered
++;
283 rte_trace_out(D_FILTERS
, p
, rt
, "filtered out");
293 /* Discard temporary rte */
300 export_filter(struct announce_hook
*ah
, rte
*rt0
, rte
**rt_free
, ea_list
**tmpa
, int silent
)
302 return export_filter_(ah
, rt0
, rt_free
, tmpa
, rte_update_pool
, silent
);
306 do_rt_notify(struct announce_hook
*ah
, net
*net
, rte
*new, rte
*old
, ea_list
*tmpa
, int refeed
)
308 struct proto
*p
= ah
->proto
;
309 struct proto_stats
*stats
= ah
->stats
;
313 * First, apply export limit.
315 * Export route limits has several problems. Because exp_routes
316 * counter is reset before refeed, we don't really know whether
317 * limit is breached and whether the update is new or not. Therefore
318 * the number of really exported routes may exceed the limit
319 * temporarily (routes exported before and new routes in refeed).
321 * Minor advantage is that if the limit is decreased and refeed is
322 * requested, the number of exported routes really decrease.
324 * Second problem is that with export limits, we don't know whether
325 * old was really exported (it might be blocked by limit). When a
326 * withdraw is exported, we announce it even when the previous
327 * update was blocked. This is not a big issue, but the same problem
328 * is in updating exp_routes counter. Therefore, to be consistent in
329 * increases and decreases of exp_routes, we count exported routes
330 * regardless of blocking by limits.
332 * Similar problem is in handling updates - when a new route is
333 * received and blocking is active, the route would be blocked, but
334 * when an update for the route will be received later, the update
335 * would be propagated (as old != NULL). Therefore, we have to block
336 * also non-new updates (contrary to import blocking).
339 struct proto_limit
*l
= ah
->out_limit
;
342 if ((!old
|| refeed
) && (stats
->exp_routes
>= l
->limit
))
343 proto_notify_limit(ah
, l
, PLD_OUT
, stats
->exp_routes
);
345 if (l
->state
== PLS_BLOCKED
)
347 stats
->exp_routes
++; /* see note above */
348 stats
->exp_updates_rejected
++;
349 rte_trace_out(D_FILTERS
, p
, new, "rejected [limit]");
359 stats
->exp_updates_accepted
++;
361 stats
->exp_withdraws_accepted
++;
363 /* Hack: We do not decrease exp_routes during refeed, we instead
364 reset exp_routes at the start of refeed. */
370 if (p
->debug
& D_ROUTES
)
373 rte_trace_out(D_ROUTES
, p
, new, "replaced");
375 rte_trace_out(D_ROUTES
, p
, new, "added");
377 rte_trace_out(D_ROUTES
, p
, old
, "removed");
380 p
->rt_notify(p
, ah
->table
, net
, NULL
, old
, NULL
);
386 t
->next
= new->attrs
->eattrs
;
387 p
->rt_notify(p
, ah
->table
, net
, new, old
, tmpa
);
391 p
->rt_notify(p
, ah
->table
, net
, new, old
, new->attrs
->eattrs
);
395 rt_notify_basic(struct announce_hook
*ah
, net
*net
, rte
*new0
, rte
*old0
, int refeed
)
397 struct proto
*p
= ah
->proto
;
398 struct proto_stats
*stats
= ah
->stats
;
402 rte
*new_free
= NULL
;
403 rte
*old_free
= NULL
;
404 ea_list
*tmpa
= NULL
;
407 stats
->exp_updates_received
++;
409 stats
->exp_withdraws_received
++;
412 * This is a tricky part - we don't know whether route 'old' was
413 * exported to protocol 'p' or was filtered by the export filter.
414 * We try to run the export filter to know this to have a correct
415 * value in 'old' argument of rte_update (and proper filter value)
417 * FIXME - this is broken because 'configure soft' may change
418 * filters but keep routes. Refeed is expected to be called after
419 * change of the filters and with old == new, therefore we do not
420 * even try to run the filter on an old route, This may lead to
421 * 'spurious withdraws' but ensure that there are no 'missing
424 * This is not completely safe as there is a window between
425 * reconfiguration and the end of refeed - if a newly filtered
426 * route disappears during this period, proper withdraw is not
427 * sent (because old would be also filtered) and the route is
428 * not refeeded (because it disappeared before that).
432 new = export_filter(ah
, new, &new_free
, &tmpa
, 0);
435 old
= export_filter(ah
, old
, &old_free
, NULL
, 1);
440 * As mentioned above, 'old' value may be incorrect in some race conditions.
441 * We generally ignore it with the exception of withdraw to pipe protocol.
442 * In that case we rather propagate unfiltered withdraws regardless of
443 * export filters to ensure that when a protocol is flushed, its routes are
444 * removed from all tables. Possible spurious unfiltered withdraws are not
445 * problem here as they are ignored if there is no corresponding route at
446 * the other end of the pipe. We directly call rt_notify() hook instead of
447 * do_rt_notify() to avoid logging and stat counters.
451 if ((p
->proto
== &proto_pipe
) && !new0
&& (p
!= old0
->sender
->proto
))
452 p
->rt_notify(p
, ah
->table
, net
, NULL
, old0
, NULL
);
458 do_rt_notify(ah
, net
, new, old
, tmpa
, refeed
);
460 /* Discard temporary rte's */
468 rt_notify_accepted(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
, rte
*before_old
, int feed
)
470 // struct proto *p = ah->proto;
471 struct proto_stats
*stats
= ah
->stats
;
474 rte
*new_best
= NULL
;
475 rte
*old_best
= NULL
;
476 rte
*new_free
= NULL
;
477 rte
*old_free
= NULL
;
478 ea_list
*tmpa
= NULL
;
480 /* Used to track whether we met old_changed position. If before_old is NULL
481 old_changed was the first and we met it implicitly before current best route. */
482 int old_meet
= old_changed
&& !before_old
;
484 /* Note that before_old is either NULL or valid (not rejected) route.
485 If old_changed is valid, before_old have to be too. If old changed route
486 was not valid, caller must use NULL for both old_changed and before_old. */
489 stats
->exp_updates_received
++;
491 stats
->exp_withdraws_received
++;
493 /* First, find the new_best route - first accepted by filters */
494 for (r
=net
->routes
; rte_is_valid(r
); r
=r
->next
)
496 if (new_best
= export_filter(ah
, r
, &new_free
, &tmpa
, 0))
499 /* Note if we walked around the position of old_changed route */
505 * Second, handle the feed case. That means we do not care for
506 * old_best. It is NULL for feed, and the new_best for refeed.
507 * For refeed, there is a hack similar to one in rt_notify_basic()
508 * to ensure withdraws in case of changed filters
512 if (feed
== 2) /* refeed */
513 old_best
= new_best
? new_best
:
514 (rte_is_valid(net
->routes
) ? net
->routes
: NULL
);
518 if (!new_best
&& !old_best
)
525 * Now, we find the old_best route. Generally, it is the same as the
526 * new_best, unless new_best is the same as new_changed or
527 * old_changed is accepted before new_best.
529 * There are four cases:
531 * - We would find and accept old_changed before new_best, therefore
532 * old_changed is old_best. In remaining cases we suppose this
535 * - We found no new_best, therefore there is also no old_best and
536 * we ignore this withdraw.
538 * - We found new_best different than new_changed, therefore
539 * old_best is the same as new_best and we ignore this update.
541 * - We found new_best the same as new_changed, therefore it cannot
542 * be old_best and we have to continue search for old_best.
547 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
554 /* Third case, we use r instead of new_best, because export_filter() could change it */
555 if (r
!= new_changed
)
563 for (r
=r
->next
; rte_is_valid(r
); r
=r
->next
)
565 if (old_best
= export_filter(ah
, r
, &old_free
, NULL
, 1))
569 if (old_best
= export_filter(ah
, old_changed
, &old_free
, NULL
, 1))
573 /* Implicitly, old_best is NULL and new_best is non-NULL */
576 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, (feed
== 2));
578 /* Discard temporary rte's */
587 mpnh_merge_rta(struct mpnh
*nhs
, rta
*a
, linpool
*pool
, int max
)
589 struct mpnh nh
= { .gw
= a
->gw
, .iface
= a
->iface
};
590 struct mpnh
*nh2
= (a
->dest
== RTD_MULTIPATH
) ? a
->nexthops
: &nh
;
591 return mpnh_merge(nhs
, nh2
, 1, 0, max
, pool
);
595 rt_export_merged(struct announce_hook
*ah
, net
*net
, rte
**rt_free
, ea_list
**tmpa
, linpool
*pool
, int silent
)
597 // struct proto *p = ah->proto;
598 struct mpnh
*nhs
= NULL
;
599 rte
*best0
, *best
, *rt0
, *rt
, *tmp
;
604 if (!rte_is_valid(best0
))
607 best
= export_filter_(ah
, best0
, rt_free
, tmpa
, pool
, silent
);
609 if (!best
|| !rte_is_reachable(best
))
612 for (rt0
= best0
->next
; rt0
; rt0
= rt0
->next
)
614 if (!rte_mergable(best0
, rt0
))
617 rt
= export_filter_(ah
, rt0
, &tmp
, NULL
, pool
, 1);
622 if (rte_is_reachable(rt
))
623 nhs
= mpnh_merge_rta(nhs
, rt
->attrs
, pool
, ah
->proto
->merge_limit
);
631 nhs
= mpnh_merge_rta(nhs
, best
->attrs
, pool
, ah
->proto
->merge_limit
);
635 best
= rte_cow_rta(best
, pool
);
636 best
->attrs
->dest
= RTD_MULTIPATH
;
637 best
->attrs
->nexthops
= nhs
;
649 rt_notify_merged(struct announce_hook
*ah
, net
*net
, rte
*new_changed
, rte
*old_changed
,
650 rte
*new_best
, rte
*old_best
, int refeed
)
652 // struct proto *p = ah->proto;
654 rte
*new_best_free
= NULL
;
655 rte
*old_best_free
= NULL
;
656 rte
*new_changed_free
= NULL
;
657 rte
*old_changed_free
= NULL
;
658 ea_list
*tmpa
= NULL
;
660 /* We assume that all rte arguments are either NULL or rte_is_valid() */
662 /* This check should be done by the caller */
663 if (!new_best
&& !old_best
)
666 /* Check whether the change is relevant to the merged route */
667 if ((new_best
== old_best
) && !refeed
)
669 new_changed
= rte_mergable(new_best
, new_changed
) ?
670 export_filter(ah
, new_changed
, &new_changed_free
, NULL
, 1) : NULL
;
672 old_changed
= rte_mergable(old_best
, old_changed
) ?
673 export_filter(ah
, old_changed
, &old_changed_free
, NULL
, 1) : NULL
;
675 if (!new_changed
&& !old_changed
)
680 ah
->stats
->exp_updates_received
++;
682 ah
->stats
->exp_withdraws_received
++;
684 /* Prepare new merged route */
686 new_best
= rt_export_merged(ah
, net
, &new_best_free
, &tmpa
, rte_update_pool
, 0);
688 /* Prepare old merged route (without proper merged next hops) */
689 /* There are some issues with running filter on old route - see rt_notify_basic() */
690 if (old_best
&& !refeed
)
691 old_best
= export_filter(ah
, old_best
, &old_best_free
, NULL
, 1);
693 if (new_best
|| old_best
)
694 do_rt_notify(ah
, net
, new_best
, old_best
, tmpa
, refeed
);
696 /* Discard temporary rte's */
698 rte_free(new_best_free
);
700 rte_free(old_best_free
);
701 if (new_changed_free
)
702 rte_free(new_changed_free
);
703 if (old_changed_free
)
704 rte_free(old_changed_free
);
709 * rte_announce - announce a routing table change
710 * @tab: table the route has been added to
711 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
712 * @net: network in question
713 * @new: the new route to be announced
714 * @old: the previous route for the same network
715 * @new_best: the new best route for the same network
716 * @old_best: the previous best route for the same network
717 * @before_old: The previous route before @old for the same network.
718 * If @before_old is NULL @old was the first.
720 * This function gets a routing table update and announces it
721 * to all protocols that acccepts given type of route announcement
722 * and are connected to the same table by their announcement hooks.
724 * Route announcement of type %RA_OPTIMAL si generated when optimal
725 * route (in routing table @tab) changes. In that case @old stores the
728 * Route announcement of type %RA_ANY si generated when any route (in
729 * routing table @tab) changes In that case @old stores the old route
730 * from the same protocol.
732 * For each appropriate protocol, we first call its import_control()
733 * hook which performs basic checks on the route (each protocol has a
734 * right to veto or force accept of the route before any filter is
735 * asked) and adds default values of attributes specific to the new
736 * protocol (metrics, tags etc.). Then it consults the protocol's
737 * export filter and if it accepts the route, the rt_notify() hook of
738 * the protocol gets called.
741 rte_announce(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
742 rte
*new_best
, rte
*old_best
, rte
*before_old
)
744 if (!rte_is_valid(new))
747 if (!rte_is_valid(old
))
748 old
= before_old
= NULL
;
750 if (!rte_is_valid(new_best
))
753 if (!rte_is_valid(old_best
))
759 if (type
== RA_OPTIMAL
)
762 new->attrs
->src
->proto
->stats
.pref_routes
++;
764 old
->attrs
->src
->proto
->stats
.pref_routes
--;
767 rt_notify_hostcache(tab
, net
);
770 struct announce_hook
*a
;
771 WALK_LIST(a
, tab
->hooks
)
773 ASSERT(a
->proto
->export_state
!= ES_DOWN
);
774 if (a
->proto
->accept_ra_types
== type
)
775 if (type
== RA_ACCEPTED
)
776 rt_notify_accepted(a
, net
, new, old
, before_old
, 0);
777 else if (type
== RA_MERGED
)
778 rt_notify_merged(a
, net
, new, old
, new_best
, old_best
, 0);
780 rt_notify_basic(a
, net
, new, old
, 0);
790 if ((n
->n
.pxlen
> BITS_PER_IP_ADDRESS
) || !ip_is_prefix(n
->n
.prefix
,n
->n
.pxlen
))
792 log(L_WARN
"Ignoring bogus prefix %I/%d received via %s",
793 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
797 c
= ipa_classify_net(n
->n
.prefix
);
798 if ((c
< 0) || !(c
& IADDR_HOST
) || ((c
& IADDR_SCOPE_MASK
) <= SCOPE_LINK
))
800 log(L_WARN
"Ignoring bogus route %I/%d received via %s",
801 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
805 if ((e
->attrs
->dest
== RTD_MULTIPATH
) && !mpnh_is_sorted(e
->attrs
->nexthops
))
807 log(L_WARN
"Ignoring unsorted multipath route %I/%d received via %s",
808 n
->n
.prefix
, n
->n
.pxlen
, e
->sender
->proto
->name
);
816 * rte_free - delete a &rte
817 * @e: &rte to be deleted
819 * rte_free() deletes the given &rte from the routing table it's linked to.
824 if (rta_is_cached(e
->attrs
))
826 sl_free(rte_slab
, e
);
830 rte_free_quick(rte
*e
)
833 sl_free(rte_slab
, e
);
837 rte_same(rte
*x
, rte
*y
)
840 x
->attrs
== y
->attrs
&&
841 x
->flags
== y
->flags
&&
842 x
->pflags
== y
->pflags
&&
843 x
->pref
== y
->pref
&&
844 (!x
->attrs
->src
->proto
->rte_same
|| x
->attrs
->src
->proto
->rte_same(x
, y
));
847 static inline int rte_is_ok(rte
*e
) { return e
&& !rte_is_filtered(e
); }
850 rte_recalculate(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
852 struct proto
*p
= ah
->proto
;
853 struct rtable
*table
= ah
->table
;
854 struct proto_stats
*stats
= ah
->stats
;
855 static struct tbf rl_pipe
= TBF_DEFAULT_LOG_LIMITS
;
856 rte
*before_old
= NULL
;
857 rte
*old_best
= net
->routes
;
861 k
= &net
->routes
; /* Find and remove original route from the same protocol */
864 if (old
->attrs
->src
== src
)
866 /* If there is the same route in the routing table but from
867 * a different sender, then there are two paths from the
868 * source protocol to this routing table through transparent
869 * pipes, which is not allowed.
871 * We log that and ignore the route. If it is withdraw, we
872 * ignore it completely (there might be 'spurious withdraws',
873 * see FIXME in do_rte_announce())
875 if (old
->sender
->proto
!= p
)
879 log_rl(&rl_pipe
, L_ERR
"Pipe collision detected when sending %I/%d to table %s",
880 net
->n
.prefix
, net
->n
.pxlen
, table
->name
);
886 if (new && rte_same(old
, new))
888 /* No changes, ignore the new route */
890 if (!rte_is_filtered(new))
892 stats
->imp_updates_ignored
++;
893 rte_trace_in(D_ROUTES
, p
, new, "ignored");
911 stats
->imp_withdraws_ignored
++;
915 int new_ok
= rte_is_ok(new);
916 int old_ok
= rte_is_ok(old
);
918 struct proto_limit
*l
= ah
->rx_limit
;
919 if (l
&& !old
&& new)
921 u32 all_routes
= stats
->imp_routes
+ stats
->filt_routes
;
923 if (all_routes
>= l
->limit
)
924 proto_notify_limit(ah
, l
, PLD_RX
, all_routes
);
926 if (l
->state
== PLS_BLOCKED
)
928 /* In receive limit the situation is simple, old is NULL so
929 we just free new and exit like nothing happened */
931 stats
->imp_updates_ignored
++;
932 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
939 if (l
&& !old_ok
&& new_ok
)
941 if (stats
->imp_routes
>= l
->limit
)
942 proto_notify_limit(ah
, l
, PLD_IN
, stats
->imp_routes
);
944 if (l
->state
== PLS_BLOCKED
)
946 /* In import limit the situation is more complicated. We
947 shouldn't just drop the route, we should handle it like
948 it was filtered. We also have to continue the route
949 processing if old or new is non-NULL, but we should exit
950 if both are NULL as this case is probably assumed to be
953 stats
->imp_updates_ignored
++;
954 rte_trace_in(D_FILTERS
, p
, new, "ignored [limit]");
956 if (ah
->in_keep_filtered
)
957 new->flags
|= REF_FILTERED
;
959 { rte_free_quick(new); new = NULL
; }
961 /* Note that old && !new could be possible when
962 ah->in_keep_filtered changed in the recent past. */
973 stats
->imp_updates_accepted
++;
975 stats
->imp_withdraws_accepted
++;
977 stats
->imp_withdraws_ignored
++;
982 rte_is_filtered(new) ? stats
->filt_routes
++ : stats
->imp_routes
++;
984 rte_is_filtered(old
) ? stats
->filt_routes
-- : stats
->imp_routes
--;
986 if (table
->config
->sorted
)
988 /* If routes are sorted, just insert new route to appropriate position */
991 if (before_old
&& !rte_better(new, before_old
))
992 k
= &before_old
->next
;
996 for (; *k
; k
=&(*k
)->next
)
997 if (rte_better(new, *k
))
1006 /* If routes are not sorted, find the best route and move it on
1007 the first position. There are several optimized cases. */
1009 if (src
->proto
->rte_recalculate
&& src
->proto
->rte_recalculate(table
, net
, new, old
, old_best
))
1010 goto do_recalculate
;
1012 if (new && rte_better(new, old_best
))
1014 /* The first case - the new route is cleary optimal,
1015 we link it at the first position */
1017 new->next
= net
->routes
;
1020 else if (old
== old_best
)
1022 /* The second case - the old best route disappeared, we add the
1023 new route (if we have any) to the list (we don't care about
1024 position) and then we elect the new optimal route and relink
1025 that route at the first position and announce it. New optimal
1026 route might be NULL if there is no more routes */
1029 /* Add the new route to the list */
1032 new->next
= net
->routes
;
1036 /* Find a new optimal route (if there is any) */
1039 rte
**bp
= &net
->routes
;
1040 for (k
=&(*bp
)->next
; *k
; k
=&(*k
)->next
)
1041 if (rte_better(*k
, *bp
))
1047 best
->next
= net
->routes
;
1053 /* The third case - the new route is not better than the old
1054 best route (therefore old_best != NULL) and the old best
1055 route was not removed (therefore old_best == net->routes).
1056 We just link the new route after the old best route. */
1058 ASSERT(net
->routes
!= NULL
);
1059 new->next
= net
->routes
->next
;
1060 net
->routes
->next
= new;
1062 /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1068 /* Log the route change */
1069 if (p
->debug
& D_ROUTES
)
1072 rte_trace(p
, new, '>', new == net
->routes
? "added [best]" : "added");
1075 if (old
!= old_best
)
1076 rte_trace(p
, old
, '>', "removed");
1077 else if (rte_is_ok(net
->routes
))
1078 rte_trace(p
, old
, '>', "removed [replaced]");
1080 rte_trace(p
, old
, '>', "removed [sole]");
1084 /* Propagate the route change */
1085 rte_announce(table
, RA_ANY
, net
, new, old
, NULL
, NULL
, NULL
);
1086 if (net
->routes
!= old_best
)
1087 rte_announce(table
, RA_OPTIMAL
, net
, net
->routes
, old_best
, NULL
, NULL
, NULL
);
1088 if (table
->config
->sorted
)
1089 rte_announce(table
, RA_ACCEPTED
, net
, new, old
, NULL
, NULL
, before_old
);
1090 rte_announce(table
, RA_MERGED
, net
, new, old
, net
->routes
, old_best
, NULL
);
1093 (table
->gc_counter
++ >= table
->config
->gc_max_ops
) &&
1094 (table
->gc_time
+ table
->config
->gc_min_time
<= now
))
1095 rt_schedule_gc(table
);
1097 if (old_ok
&& p
->rte_remove
)
1098 p
->rte_remove(net
, old
);
1099 if (new_ok
&& p
->rte_insert
)
1100 p
->rte_insert(net
, new);
1103 rte_free_quick(old
);
1106 static int rte_update_nest_cnt
; /* Nesting counter to allow recursive updates */
1109 rte_update_lock(void)
1111 rte_update_nest_cnt
++;
1115 rte_update_unlock(void)
1117 if (!--rte_update_nest_cnt
)
1118 lp_flush(rte_update_pool
);
1122 rte_hide_dummy_routes(net
*net
, rte
**dummy
)
1124 if (net
->routes
&& net
->routes
->attrs
->source
== RTS_DUMMY
)
1126 *dummy
= net
->routes
;
1127 net
->routes
= (*dummy
)->next
;
1132 rte_unhide_dummy_routes(net
*net
, rte
**dummy
)
1136 (*dummy
)->next
= net
->routes
;
1137 net
->routes
= *dummy
;
1142 * rte_update - enter a new update to a routing table
1143 * @table: table to be updated
1144 * @ah: pointer to table announce hook
1145 * @net: network node
1146 * @p: protocol submitting the update
1147 * @src: protocol originating the update
1148 * @new: a &rte representing the new route or %NULL for route removal.
1150 * This function is called by the routing protocols whenever they discover
1151 * a new route or wish to update/remove an existing route. The right announcement
1152 * sequence is to build route attributes first (either un-cached with @aflags set
1153 * to zero or a cached one using rta_lookup(); in this case please note that
1154 * you need to increase the use count of the attributes yourself by calling
1155 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1156 * the appropriate data and finally submit the new &rte by calling rte_update().
1158 * @src specifies the protocol that originally created the route and the meaning
1159 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1160 * same value as @new->attrs->proto. @p specifies the protocol that called
1161 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1162 * stores @p in @new->sender;
1164 * When rte_update() gets any route, it automatically validates it (checks,
1165 * whether the network and next hop address are valid IP addresses and also
1166 * whether a normal routing protocol doesn't try to smuggle a host or link
1167 * scope route to the table), converts all protocol dependent attributes stored
1168 * in the &rte to temporary extended attributes, consults import filters of the
1169 * protocol to see if the route should be accepted and/or its attributes modified,
1170 * stores the temporary attributes back to the &rte.
1172 * Now, having a "public" version of the route, we
1173 * automatically find any old route defined by the protocol @src
1174 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1175 * recalculate the optimal route for this destination and finally broadcast
1176 * the change (if any) to all routing protocols by calling rte_announce().
1178 * All memory used for attribute lists and other temporary allocations is taken
1179 * from a special linear pool @rte_update_pool and freed when rte_update()
1184 rte_update2(struct announce_hook
*ah
, net
*net
, rte
*new, struct rte_src
*src
)
1186 struct proto
*p
= ah
->proto
;
1187 struct proto_stats
*stats
= ah
->stats
;
1188 struct filter
*filter
= ah
->in_filter
;
1189 ea_list
*tmpa
= NULL
;
1197 stats
->imp_updates_received
++;
1198 if (!rte_validate(new))
1200 rte_trace_in(D_FILTERS
, p
, new, "invalid");
1201 stats
->imp_updates_invalid
++;
1205 if (filter
== FILTER_REJECT
)
1207 stats
->imp_updates_filtered
++;
1208 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1210 if (! ah
->in_keep_filtered
)
1213 /* new is a private copy, i could modify it */
1214 new->flags
|= REF_FILTERED
;
1218 tmpa
= rte_make_tmp_attrs(new, rte_update_pool
);
1219 if (filter
&& (filter
!= FILTER_REJECT
))
1221 ea_list
*old_tmpa
= tmpa
;
1222 int fr
= f_run(filter
, &new, &tmpa
, rte_update_pool
, 0);
1225 stats
->imp_updates_filtered
++;
1226 rte_trace_in(D_FILTERS
, p
, new, "filtered out");
1228 if (! ah
->in_keep_filtered
)
1231 new->flags
|= REF_FILTERED
;
1233 if (tmpa
!= old_tmpa
&& src
->proto
->store_tmp_attrs
)
1234 src
->proto
->store_tmp_attrs(new, tmpa
);
1237 if (!rta_is_cached(new->attrs
)) /* Need to copy attributes */
1238 new->attrs
= rta_lookup(new->attrs
);
1239 new->flags
|= REF_COW
;
1243 stats
->imp_withdraws_received
++;
1247 stats
->imp_withdraws_ignored
++;
1248 rte_update_unlock();
1254 rte_hide_dummy_routes(net
, &dummy
);
1255 rte_recalculate(ah
, net
, new, src
);
1256 rte_unhide_dummy_routes(net
, &dummy
);
1257 rte_update_unlock();
1266 /* Independent call to rte_announce(), used from next hop
1267 recalculation, outside of rte_update(). new must be non-NULL */
1269 rte_announce_i(rtable
*tab
, unsigned type
, net
*net
, rte
*new, rte
*old
,
1270 rte
*new_best
, rte
*old_best
)
1273 rte_announce(tab
, type
, net
, new, old
, new_best
, old_best
, NULL
);
1274 rte_update_unlock();
1278 rte_discard(rte
*old
) /* Non-filtered route deletion, used during garbage collection */
1281 rte_recalculate(old
->sender
, old
->net
, NULL
, old
->attrs
->src
);
1282 rte_update_unlock();
1285 /* Check rtable for best route to given net whether it would be exported do p */
1287 rt_examine(rtable
*t
, ip_addr prefix
, int pxlen
, struct proto
*p
, struct filter
*filter
)
1289 net
*n
= net_find(t
, prefix
, pxlen
);
1290 rte
*rt
= n
? n
->routes
: NULL
;
1292 if (!rte_is_valid(rt
))
1297 /* Rest is stripped down export_filter() */
1298 ea_list
*tmpa
= rte_make_tmp_attrs(rt
, rte_update_pool
);
1299 int v
= p
->import_control
? p
->import_control(p
, &rt
, &tmpa
, rte_update_pool
) : 0;
1300 if (v
== RIC_PROCESS
)
1301 v
= (f_run(filter
, &rt
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
1303 /* Discard temporary rte */
1304 if (rt
!= n
->routes
)
1307 rte_update_unlock();
1314 * rt_refresh_begin - start a refresh cycle
1315 * @t: related routing table
1316 * @ah: related announce hook
1318 * This function starts a refresh cycle for given routing table and announce
1319 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1320 * routes to the routing table (by rte_update()). After that, all protocol
1321 * routes (more precisely routes with @ah as @sender) not sent during the
1322 * refresh cycle but still in the table from the past are pruned. This is
1323 * implemented by marking all related routes as stale by REF_STALE flag in
1324 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1325 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1328 rt_refresh_begin(rtable
*t
, struct announce_hook
*ah
)
1333 FIB_WALK(&t
->fib
, fn
)
1336 for (e
= n
->routes
; e
; e
= e
->next
)
1337 if (e
->sender
== ah
)
1338 e
->flags
|= REF_STALE
;
1344 * rt_refresh_end - end a refresh cycle
1345 * @t: related routing table
1346 * @ah: related announce hook
1348 * This function starts a refresh cycle for given routing table and announce
1349 * hook. See rt_refresh_begin() for description of refresh cycles.
1352 rt_refresh_end(rtable
*t
, struct announce_hook
*ah
)
1358 FIB_WALK(&t
->fib
, fn
)
1361 for (e
= n
->routes
; e
; e
= e
->next
)
1362 if ((e
->sender
== ah
) && (e
->flags
& REF_STALE
))
1364 e
->flags
|= REF_DISCARD
;
1371 rt_schedule_prune(t
);
1376 * rte_dump - dump a route
1377 * @e: &rte to be dumped
1379 * This functions dumps contents of a &rte to debug output.
1385 debug("%-1I/%2d ", n
->n
.prefix
, n
->n
.pxlen
);
1386 debug("KF=%02x PF=%02x pref=%d lm=%d ", n
->n
.flags
, e
->pflags
, e
->pref
, now
-e
->lastmod
);
1388 if (e
->attrs
->src
->proto
->proto
->dump_attrs
)
1389 e
->attrs
->src
->proto
->proto
->dump_attrs(e
);
1394 * rt_dump - dump a routing table
1395 * @t: routing table to be dumped
1397 * This function dumps contents of a given routing table to debug output.
1404 struct announce_hook
*a
;
1406 debug("Dump of routing table <%s>\n", t
->name
);
1410 FIB_WALK(&t
->fib
, fn
)
1413 for(e
=n
->routes
; e
; e
=e
->next
)
1417 WALK_LIST(a
, t
->hooks
)
1418 debug("\tAnnounces routes to protocol %s\n", a
->proto
->name
);
1423 * rt_dump_all - dump all routing tables
1425 * This function dumps contents of all routing tables to debug output.
1432 WALK_LIST(t
, routing_tables
)
1437 rt_schedule_prune(rtable
*tab
)
1439 rt_mark_for_prune(tab
);
1440 ev_schedule(tab
->rt_event
);
1444 rt_schedule_gc(rtable
*tab
)
1446 if (tab
->gc_scheduled
)
1449 tab
->gc_scheduled
= 1;
1450 ev_schedule(tab
->rt_event
);
1454 rt_schedule_hcu(rtable
*tab
)
1456 if (tab
->hcu_scheduled
)
1459 tab
->hcu_scheduled
= 1;
1460 ev_schedule(tab
->rt_event
);
1464 rt_schedule_nhu(rtable
*tab
)
1466 if (tab
->nhu_state
== 0)
1467 ev_schedule(tab
->rt_event
);
1469 /* state change 0->1, 2->3 */
1470 tab
->nhu_state
|= 1;
1475 rt_prune_nets(rtable
*tab
)
1477 struct fib_iterator fit
;
1478 int ncnt
= 0, ndel
= 0;
1481 fib_check(&tab
->fib
);
1484 FIB_ITERATE_INIT(&fit
, &tab
->fib
);
1486 FIB_ITERATE_START(&tab
->fib
, &fit
, f
)
1490 if (!n
->routes
) /* Orphaned FIB entry */
1492 FIB_ITERATE_PUT(&fit
, f
);
1493 fib_delete(&tab
->fib
, f
);
1499 DBG("Pruned %d of %d networks\n", ndel
, ncnt
);
1501 tab
->gc_counter
= 0;
1503 tab
->gc_scheduled
= 0;
1511 if (tab
->hcu_scheduled
)
1512 rt_update_hostcache(tab
);
1515 rt_next_hop_update(tab
);
1517 if (tab
->prune_state
)
1518 if (!rt_prune_table(tab
))
1520 /* Table prune unfinished */
1521 ev_schedule(tab
->rt_event
);
1525 if (tab
->gc_scheduled
)
1528 rt_prune_sources(); // FIXME this should be moved to independent event
1533 rt_setup(pool
*p
, rtable
*t
, char *name
, struct rtable_config
*cf
)
1535 bzero(t
, sizeof(*t
));
1536 fib_init(&t
->fib
, p
, sizeof(net
), 0, rte_init
);
1539 init_list(&t
->hooks
);
1542 t
->rt_event
= ev_new(p
);
1543 t
->rt_event
->hook
= rt_event
;
1544 t
->rt_event
->data
= t
;
1550 * rt_init - initialize routing tables
1552 * This function is called during BIRD startup. It initializes the
1553 * routing table module.
1559 rt_table_pool
= rp_new(&root_pool
, "Routing tables");
1560 rte_update_pool
= lp_new(rt_table_pool
, 4080);
1561 rte_slab
= sl_new(rt_table_pool
, sizeof(rte
));
1562 init_list(&routing_tables
);
1567 rt_prune_step(rtable
*tab
, int *limit
)
1569 struct fib_iterator
*fit
= &tab
->prune_fit
;
1571 DBG("Pruning route table %s\n", tab
->name
);
1573 fib_check(&tab
->fib
);
1576 if (tab
->prune_state
== RPS_NONE
)
1579 if (tab
->prune_state
== RPS_SCHEDULED
)
1581 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1582 tab
->prune_state
= RPS_RUNNING
;
1586 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1588 net
*n
= (net
*) fn
;
1592 for (e
=n
->routes
; e
; e
=e
->next
)
1593 if (e
->sender
->proto
->flushing
|| (e
->flags
& REF_DISCARD
))
1597 FIB_ITERATE_PUT(fit
, fn
);
1606 if (!n
->routes
) /* Orphaned FIB entry */
1608 FIB_ITERATE_PUT(fit
, fn
);
1609 fib_delete(&tab
->fib
, fn
);
1613 FIB_ITERATE_END(fn
);
1616 fib_check(&tab
->fib
);
1619 tab
->prune_state
= RPS_NONE
;
1624 * rt_prune_table - prune a routing table
1625 * @tab: a routing table for pruning
1627 * This function scans the routing table @tab and removes routes belonging to
1628 * flushing protocols, discarded routes and also stale network entries, in a
1629 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1630 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1631 * protocol flushing loop, but it is called from rt_event() for just one routing
1634 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1635 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1638 rt_prune_table(rtable
*tab
)
1641 return rt_prune_step(tab
, &limit
);
1645 * rt_prune_loop - prune routing tables
1647 * The prune loop scans routing tables and removes routes belonging to flushing
1648 * protocols, discarded routes and also stale network entries. Returns 1 when
1649 * all such routes are pruned. It is a part of the protocol flushing loop.
1657 WALK_LIST(t
, routing_tables
)
1658 if (! rt_prune_step(t
, &limit
))
1665 rt_preconfig(struct config
*c
)
1667 struct symbol
*s
= cf_get_symbol("master");
1669 init_list(&c
->tables
);
1670 c
->master_rtc
= rt_new_table(s
);
1675 * Some functions for handing internal next hop updates
1676 * triggered by rt_schedule_nhu().
1680 rta_next_hop_outdated(rta
*a
)
1682 struct hostentry
*he
= a
->hostentry
;
1688 return a
->dest
!= RTD_UNREACHABLE
;
1690 return (a
->iface
!= he
->src
->iface
) || !ipa_equal(a
->gw
, he
->gw
) ||
1691 (a
->dest
!= he
->dest
) || (a
->igp_metric
!= he
->igp_metric
) ||
1692 !mpnh_same(a
->nexthops
, he
->src
->nexthops
);
1696 rta_apply_hostentry(rta
*a
, struct hostentry
*he
)
1699 a
->iface
= he
->src
? he
->src
->iface
: NULL
;
1702 a
->igp_metric
= he
->igp_metric
;
1703 a
->nexthops
= he
->src
? he
->src
->nexthops
: NULL
;
1707 rt_next_hop_update_rte(rtable
*tab UNUSED
, rte
*old
)
1710 memcpy(&a
, old
->attrs
, sizeof(rta
));
1711 rta_apply_hostentry(&a
, old
->attrs
->hostentry
);
1714 rte
*e
= sl_alloc(rte_slab
);
1715 memcpy(e
, old
, sizeof(rte
));
1716 e
->attrs
= rta_lookup(&a
);
1722 rt_next_hop_update_net(rtable
*tab
, net
*n
)
1724 rte
**k
, *e
, *new, *old_best
, **new_best
;
1726 int free_old_best
= 0;
1728 old_best
= n
->routes
;
1732 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1733 if (rta_next_hop_outdated(e
->attrs
))
1735 new = rt_next_hop_update_rte(tab
, e
);
1738 rte_announce_i(tab
, RA_ANY
, n
, new, e
, NULL
, NULL
);
1739 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated");
1741 /* Call a pre-comparison hook */
1742 /* Not really an efficient way to compute this */
1743 if (e
->attrs
->src
->proto
->rte_recalculate
)
1744 e
->attrs
->src
->proto
->rte_recalculate(tab
, n
, new, e
, NULL
);
1748 else /* Freeing of the old best rte is postponed */
1758 /* Find the new best route */
1760 for (k
= &n
->routes
; e
= *k
; k
= &e
->next
)
1762 if (!new_best
|| rte_better(e
, *new_best
))
1766 /* Relink the new best route to the first position */
1768 if (new != n
->routes
)
1770 *new_best
= new->next
;
1771 new->next
= n
->routes
;
1775 /* Announce the new best route */
1776 if (new != old_best
)
1778 rte_announce_i(tab
, RA_OPTIMAL
, n
, new, old_best
, NULL
, NULL
);
1779 rte_trace_in(D_ROUTES
, new->sender
->proto
, new, "updated [best]");
1782 /* FIXME: Better announcement of merged routes */
1783 rte_announce_i(tab
, RA_MERGED
, n
, new, old_best
, new, old_best
);
1786 rte_free_quick(old_best
);
1792 rt_next_hop_update(rtable
*tab
)
1794 struct fib_iterator
*fit
= &tab
->nhu_fit
;
1797 if (tab
->nhu_state
== 0)
1800 if (tab
->nhu_state
== 1)
1802 FIB_ITERATE_INIT(fit
, &tab
->fib
);
1806 FIB_ITERATE_START(&tab
->fib
, fit
, fn
)
1810 FIB_ITERATE_PUT(fit
, fn
);
1811 ev_schedule(tab
->rt_event
);
1814 max_feed
-= rt_next_hop_update_net(tab
, (net
*) fn
);
1816 FIB_ITERATE_END(fn
);
1818 /* state change 2->0, 3->1 */
1819 tab
->nhu_state
&= 1;
1821 if (tab
->nhu_state
> 0)
1822 ev_schedule(tab
->rt_event
);
1826 struct rtable_config
*
1827 rt_new_table(struct symbol
*s
)
1829 /* Hack that allows to 'redefine' the master table */
1830 if ((s
->class == SYM_TABLE
) && (s
->def
== new_config
->master_rtc
))
1833 struct rtable_config
*c
= cfg_allocz(sizeof(struct rtable_config
));
1835 cf_define_symbol(s
, SYM_TABLE
, c
);
1837 add_tail(&new_config
->tables
, &c
->n
);
1838 c
->gc_max_ops
= 1000;
1844 * rt_lock_table - lock a routing table
1845 * @r: routing table to be locked
1847 * Lock a routing table, because it's in use by a protocol,
1848 * preventing it from being freed when it gets undefined in a new
1852 rt_lock_table(rtable
*r
)
1858 * rt_unlock_table - unlock a routing table
1859 * @r: routing table to be unlocked
1861 * Unlock a routing table formerly locked by rt_lock_table(),
1862 * that is decrease its use count and delete it if it's scheduled
1863 * for deletion by configuration changes.
1866 rt_unlock_table(rtable
*r
)
1868 if (!--r
->use_count
&& r
->deleted
)
1870 struct config
*conf
= r
->deleted
;
1871 DBG("Deleting routing table %s\n", r
->name
);
1872 r
->config
->table
= NULL
;
1874 rt_free_hostcache(r
);
1879 config_del_obstacle(conf
);
1884 * rt_commit - commit new routing table configuration
1885 * @new: new configuration
1886 * @old: original configuration or %NULL if it's boot time config
1888 * Scan differences between @old and @new configuration and modify
1889 * the routing tables according to these changes. If @new defines a
1890 * previously unknown table, create it, if it omits a table existing
1891 * in @old, schedule it for deletion (it gets deleted when all protocols
1892 * disconnect from it by calling rt_unlock_table()), if it exists
1893 * in both configurations, leave it unchanged.
1896 rt_commit(struct config
*new, struct config
*old
)
1898 struct rtable_config
*o
, *r
;
1900 DBG("rt_commit:\n");
1903 WALK_LIST(o
, old
->tables
)
1905 rtable
*ot
= o
->table
;
1908 struct symbol
*sym
= cf_find_symbol(new, o
->name
);
1909 if (sym
&& sym
->class == SYM_TABLE
&& !new->shutdown
)
1911 DBG("\t%s: same\n", o
->name
);
1916 if (o
->sorted
!= r
->sorted
)
1917 log(L_WARN
"Reconfiguration of rtable sorted flag not implemented");
1921 DBG("\t%s: deleted\n", o
->name
);
1923 config_add_obstacle(old
);
1925 rt_unlock_table(ot
);
1931 WALK_LIST(r
, new->tables
)
1934 rtable
*t
= mb_alloc(rt_table_pool
, sizeof(struct rtable
));
1935 DBG("\t%s: created\n", r
->name
);
1936 rt_setup(rt_table_pool
, t
, r
->name
, r
);
1937 add_tail(&routing_tables
, &t
->n
);
1944 do_feed_baby(struct proto
*p
, int type
, struct announce_hook
*h
, net
*n
, rte
*e
)
1947 if (type
== RA_ACCEPTED
)
1948 rt_notify_accepted(h
, n
, e
, NULL
, NULL
, p
->refeeding
? 2 : 1);
1949 else if (type
== RA_MERGED
)
1950 rt_notify_merged(h
, n
, NULL
, NULL
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1952 rt_notify_basic(h
, n
, e
, p
->refeeding
? e
: NULL
, p
->refeeding
);
1953 rte_update_unlock();
1957 * rt_feed_baby - advertise routes to a new protocol
1958 * @p: protocol to be fed
1960 * This function performs one pass of advertisement of routes to a newly
1961 * initialized protocol. It's called by the protocol code as long as it
1962 * has something to do. (We avoid transferring all the routes in single
1963 * pass in order not to monopolize CPU time.)
1966 rt_feed_baby(struct proto
*p
)
1968 struct announce_hook
*h
;
1969 struct fib_iterator
*fit
;
1972 if (!p
->feed_ahook
) /* Need to initialize first */
1976 DBG("Announcing routes to new protocol %s\n", p
->name
);
1977 p
->feed_ahook
= p
->ahooks
;
1978 fit
= p
->feed_iterator
= mb_alloc(p
->pool
, sizeof(struct fib_iterator
));
1981 fit
= p
->feed_iterator
;
1985 FIB_ITERATE_START(&h
->table
->fib
, fit
, fn
)
1987 net
*n
= (net
*) fn
;
1991 FIB_ITERATE_PUT(fit
, fn
);
1995 /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1997 if ((p
->accept_ra_types
== RA_OPTIMAL
) ||
1998 (p
->accept_ra_types
== RA_ACCEPTED
) ||
1999 (p
->accept_ra_types
== RA_MERGED
))
2000 if (rte_is_valid(e
))
2002 if (p
->export_state
!= ES_FEEDING
)
2003 return 1; /* In the meantime, the protocol fell down. */
2005 do_feed_baby(p
, p
->accept_ra_types
, h
, n
, e
);
2009 if (p
->accept_ra_types
== RA_ANY
)
2010 for(e
= n
->routes
; e
; e
= e
->next
)
2012 if (p
->export_state
!= ES_FEEDING
)
2013 return 1; /* In the meantime, the protocol fell down. */
2015 if (!rte_is_valid(e
))
2018 do_feed_baby(p
, RA_ANY
, h
, n
, e
);
2022 FIB_ITERATE_END(fn
);
2023 p
->feed_ahook
= h
->next
;
2026 mb_free(p
->feed_iterator
);
2027 p
->feed_iterator
= NULL
;
2033 FIB_ITERATE_INIT(fit
, &h
->table
->fib
);
2038 * rt_feed_baby_abort - abort protocol feeding
2041 * This function is called by the protocol code when the protocol
2042 * stops or ceases to exist before the last iteration of rt_feed_baby()
2046 rt_feed_baby_abort(struct proto
*p
)
2050 /* Unlink the iterator and exit */
2051 fit_get(&p
->feed_ahook
->table
->fib
, p
->feed_iterator
);
2052 p
->feed_ahook
= NULL
;
2057 static inline unsigned
2060 uintptr_t p
= (uintptr_t) ptr
;
2061 return p
^ (p
<< 8) ^ (p
>> 16);
2064 static inline unsigned
2065 hc_hash(ip_addr a
, rtable
*dep
)
2067 return (ipa_hash(a
) ^ ptr_hash(dep
)) & 0xffff;
2071 hc_insert(struct hostcache
*hc
, struct hostentry
*he
)
2073 uint k
= he
->hash_key
>> hc
->hash_shift
;
2074 he
->next
= hc
->hash_table
[k
];
2075 hc
->hash_table
[k
] = he
;
2079 hc_remove(struct hostcache
*hc
, struct hostentry
*he
)
2081 struct hostentry
**hep
;
2082 uint k
= he
->hash_key
>> hc
->hash_shift
;
2084 for (hep
= &hc
->hash_table
[k
]; *hep
!= he
; hep
= &(*hep
)->next
);
2088 #define HC_DEF_ORDER 10
2089 #define HC_HI_MARK *4
2090 #define HC_HI_STEP 2
2091 #define HC_HI_ORDER 16 /* Must be at most 16 */
2092 #define HC_LO_MARK /5
2093 #define HC_LO_STEP 2
2094 #define HC_LO_ORDER 10
2097 hc_alloc_table(struct hostcache
*hc
, unsigned order
)
2099 uint hsize
= 1 << order
;
2100 hc
->hash_order
= order
;
2101 hc
->hash_shift
= 16 - order
;
2102 hc
->hash_max
= (order
>= HC_HI_ORDER
) ? ~0U : (hsize HC_HI_MARK
);
2103 hc
->hash_min
= (order
<= HC_LO_ORDER
) ? 0U : (hsize HC_LO_MARK
);
2105 hc
->hash_table
= mb_allocz(rt_table_pool
, hsize
* sizeof(struct hostentry
*));
2109 hc_resize(struct hostcache
*hc
, unsigned new_order
)
2111 struct hostentry
**old_table
= hc
->hash_table
;
2112 struct hostentry
*he
, *hen
;
2113 uint old_size
= 1 << hc
->hash_order
;
2116 hc_alloc_table(hc
, new_order
);
2117 for (i
= 0; i
< old_size
; i
++)
2118 for (he
= old_table
[i
]; he
!= NULL
; he
=hen
)
2126 static struct hostentry
*
2127 hc_new_hostentry(struct hostcache
*hc
, ip_addr a
, ip_addr ll
, rtable
*dep
, unsigned k
)
2129 struct hostentry
*he
= sl_alloc(hc
->slab
);
2138 add_tail(&hc
->hostentries
, &he
->ln
);
2142 if (hc
->hash_items
> hc
->hash_max
)
2143 hc_resize(hc
, hc
->hash_order
+ HC_HI_STEP
);
2149 hc_delete_hostentry(struct hostcache
*hc
, struct hostentry
*he
)
2155 sl_free(hc
->slab
, he
);
2158 if (hc
->hash_items
< hc
->hash_min
)
2159 hc_resize(hc
, hc
->hash_order
- HC_LO_STEP
);
2163 rt_init_hostcache(rtable
*tab
)
2165 struct hostcache
*hc
= mb_allocz(rt_table_pool
, sizeof(struct hostcache
));
2166 init_list(&hc
->hostentries
);
2169 hc_alloc_table(hc
, HC_DEF_ORDER
);
2170 hc
->slab
= sl_new(rt_table_pool
, sizeof(struct hostentry
));
2172 hc
->lp
= lp_new(rt_table_pool
, 1008);
2173 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2175 tab
->hostcache
= hc
;
2179 rt_free_hostcache(rtable
*tab
)
2181 struct hostcache
*hc
= tab
->hostcache
;
2184 WALK_LIST(n
, hc
->hostentries
)
2186 struct hostentry
*he
= SKIP_BACK(struct hostentry
, ln
, n
);
2190 log(L_ERR
"Hostcache is not empty in table %s", tab
->name
);
2195 mb_free(hc
->hash_table
);
2200 rt_notify_hostcache(rtable
*tab
, net
*net
)
2202 struct hostcache
*hc
= tab
->hostcache
;
2204 if (tab
->hcu_scheduled
)
2207 if (trie_match_prefix(hc
->trie
, net
->n
.prefix
, net
->n
.pxlen
))
2208 rt_schedule_hcu(tab
);
2212 if_local_addr(ip_addr a
, struct iface
*i
)
2216 WALK_LIST(b
, i
->addrs
)
2217 if (ipa_equal(a
, b
->ip
))
2224 rt_get_igp_metric(rte
*rt
)
2226 eattr
*ea
= ea_find(rt
->attrs
->eattrs
, EA_GEN_IGP_METRIC
);
2234 if ((a
->source
== RTS_OSPF
) ||
2235 (a
->source
== RTS_OSPF_IA
) ||
2236 (a
->source
== RTS_OSPF_EXT1
))
2237 return rt
->u
.ospf
.metric1
;
2241 if (a
->source
== RTS_RIP
)
2242 return rt
->u
.rip
.metric
;
2246 if ((a
->dest
!= RTD_ROUTER
) && (a
->dest
!= RTD_MULTIPATH
))
2249 return IGP_METRIC_UNKNOWN
;
2253 rt_update_hostentry(rtable
*tab
, struct hostentry
*he
)
2255 rta
*old_src
= he
->src
;
2258 /* Reset the hostentry */
2261 he
->dest
= RTD_UNREACHABLE
;
2264 net
*n
= net_route(tab
, he
->addr
, MAX_PREFIX_LENGTH
);
2273 /* Recursive route should not depend on another recursive route */
2274 log(L_WARN
"Next hop address %I resolvable through recursive route for %I/%d",
2275 he
->addr
, n
->n
.prefix
, pxlen
);
2279 if (a
->dest
== RTD_DEVICE
)
2281 if (if_local_addr(he
->addr
, a
->iface
))
2283 /* The host address is a local address, this is not valid */
2284 log(L_WARN
"Next hop address %I is a local address of iface %s",
2285 he
->addr
, a
->iface
->name
);
2289 /* The host is directly reachable, use link as a gateway */
2291 he
->dest
= RTD_ROUTER
;
2295 /* The host is reachable through some route entry */
2300 he
->src
= rta_clone(a
);
2301 he
->igp_metric
= rt_get_igp_metric(e
);
2305 /* Add a prefix range to the trie */
2306 trie_add_prefix(tab
->hostcache
->trie
, he
->addr
, MAX_PREFIX_LENGTH
, pxlen
, MAX_PREFIX_LENGTH
);
2309 return old_src
!= he
->src
;
2313 rt_update_hostcache(rtable
*tab
)
2315 struct hostcache
*hc
= tab
->hostcache
;
2316 struct hostentry
*he
;
2319 /* Reset the trie */
2321 hc
->trie
= f_new_trie(hc
->lp
, sizeof(struct f_trie_node
));
2323 WALK_LIST_DELSAFE(n
, x
, hc
->hostentries
)
2325 he
= SKIP_BACK(struct hostentry
, ln
, n
);
2328 hc_delete_hostentry(hc
, he
);
2332 if (rt_update_hostentry(tab
, he
))
2333 rt_schedule_nhu(he
->tab
);
2336 tab
->hcu_scheduled
= 0;
2339 static struct hostentry
*
2340 rt_get_hostentry(rtable
*tab
, ip_addr a
, ip_addr ll
, rtable
*dep
)
2342 struct hostentry
*he
;
2344 if (!tab
->hostcache
)
2345 rt_init_hostcache(tab
);
2347 uint k
= hc_hash(a
, dep
);
2348 struct hostcache
*hc
= tab
->hostcache
;
2349 for (he
= hc
->hash_table
[k
>> hc
->hash_shift
]; he
!= NULL
; he
= he
->next
)
2350 if (ipa_equal(he
->addr
, a
) && (he
->tab
== dep
))
2353 he
= hc_new_hostentry(hc
, a
, ll
, dep
, k
);
2354 rt_update_hostentry(tab
, he
);
2359 rta_set_recursive_next_hop(rtable
*dep
, rta
*a
, rtable
*tab
, ip_addr
*gw
, ip_addr
*ll
)
2361 rta_apply_hostentry(a
, rt_get_hostentry(tab
, *gw
, *ll
, dep
));
2370 rt_format_via(rte
*e
)
2374 /* Max text length w/o IP addr and interface name is 16 */
2375 static byte via
[STD_ADDRESS_P_LENGTH
+sizeof(a
->iface
->name
)+16];
2379 case RTD_ROUTER
: bsprintf(via
, "via %I on %s", a
->gw
, a
->iface
->name
); break;
2380 case RTD_DEVICE
: bsprintf(via
, "dev %s", a
->iface
->name
); break;
2381 case RTD_BLACKHOLE
: bsprintf(via
, "blackhole"); break;
2382 case RTD_UNREACHABLE
: bsprintf(via
, "unreachable"); break;
2383 case RTD_PROHIBIT
: bsprintf(via
, "prohibited"); break;
2384 case RTD_MULTIPATH
: bsprintf(via
, "multipath"); break;
2385 default: bsprintf(via
, "???");
2391 rt_show_rte(struct cli
*c
, byte
*ia
, rte
*e
, struct rt_show_data
*d
, ea_list
*tmpa
)
2393 byte from
[STD_ADDRESS_P_LENGTH
+8];
2394 byte tm
[TM_DATETIME_BUFFER_SIZE
], info
[256];
2396 int primary
= (e
->net
->routes
== e
);
2397 int sync_error
= (e
->net
->n
.flags
& KRF_SYNC_ERROR
);
2398 void (*get_route_info
)(struct rte
*, byte
*buf
, struct ea_list
*attrs
);
2401 tm_format_datetime(tm
, &config
->tf_route
, e
->lastmod
);
2402 if (ipa_nonzero(a
->from
) && !ipa_equal(a
->from
, a
->gw
))
2403 bsprintf(from
, " from %I", a
->from
);
2407 get_route_info
= a
->src
->proto
->proto
->get_route_info
;
2408 if (get_route_info
|| d
->verbose
)
2410 /* Need to normalize the extended attributes */
2412 t
= ea_append(t
, a
->eattrs
);
2413 tmpa
= alloca(ea_scan(t
));
2418 get_route_info(e
, info
, tmpa
);
2420 bsprintf(info
, " (%d)", e
->pref
);
2421 cli_printf(c
, -1007, "%-18s %s [%s %s%s]%s%s", ia
, rt_format_via(e
), a
->src
->proto
->name
,
2422 tm
, from
, primary
? (sync_error
? " !" : " *") : "", info
);
2423 for (nh
= a
->nexthops
; nh
; nh
= nh
->next
)
2424 cli_printf(c
, -1007, "\tvia %I on %s weight %d", nh
->gw
, nh
->iface
->name
, nh
->weight
+ 1);
2426 rta_show(c
, a
, tmpa
);
2430 rt_show_net(struct cli
*c
, net
*n
, struct rt_show_data
*d
)
2433 byte ia
[STD_ADDRESS_P_LENGTH
+8];
2434 struct ea_list
*tmpa
;
2435 struct announce_hook
*a
= NULL
;
2439 bsprintf(ia
, "%I/%d", n
->n
.prefix
, n
->n
.pxlen
);
2443 if (! d
->export_protocol
->rt_notify
)
2446 a
= proto_find_announce_hook(d
->export_protocol
, d
->table
);
2451 for (e
= n
->routes
; e
; e
= e
->next
)
2453 if (rte_is_filtered(e
) != d
->filtered
)
2457 d
->net_counter
+= first
;
2464 rte_update_lock(); /* We use the update buffer for filtering */
2465 tmpa
= rte_make_tmp_attrs(e
, rte_update_pool
);
2467 /* Special case for merged export */
2468 if ((d
->export_mode
== RSEM_EXPORT
) && (d
->export_protocol
->accept_ra_types
== RA_MERGED
))
2471 e
= rt_export_merged(a
, n
, &rt_free
, &tmpa
, rte_update_pool
, 1);
2475 { e
= ee
; goto skip
; }
2477 else if (d
->export_mode
)
2479 struct proto
*ep
= d
->export_protocol
;
2480 int ic
= ep
->import_control
? ep
->import_control(ep
, &e
, &tmpa
, rte_update_pool
) : 0;
2482 if (ep
->accept_ra_types
== RA_OPTIMAL
|| ep
->accept_ra_types
== RA_MERGED
)
2488 if (d
->export_mode
> RSEM_PREEXPORT
)
2491 * FIXME - This shows what should be exported according to current
2492 * filters, but not what was really exported. 'configure soft'
2493 * command may change the export filter and do not update routes.
2495 int do_export
= (ic
> 0) ||
2496 (f_run(a
->out_filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) <= F_ACCEPT
);
2498 if (do_export
!= (d
->export_mode
== RSEM_EXPORT
))
2501 if ((d
->export_mode
== RSEM_EXPORT
) && (ep
->accept_ra_types
== RA_ACCEPTED
))
2506 if (d
->show_protocol
&& (d
->show_protocol
!= e
->attrs
->src
->proto
))
2509 if (f_run(d
->filter
, &e
, &tmpa
, rte_update_pool
, FF_FORCE_TMPATTR
) > F_ACCEPT
)
2514 rt_show_rte(c
, ia
, e
, d
, tmpa
);
2523 rte_update_unlock();
2525 if (d
->primary_only
)
2531 rt_show_cont(struct cli
*c
)
2533 struct rt_show_data
*d
= c
->rover
;
2539 struct fib
*fib
= &d
->table
->fib
;
2540 struct fib_iterator
*it
= &d
->fit
;
2542 FIB_ITERATE_START(fib
, it
, f
)
2545 if (d
->running_on_config
&& d
->running_on_config
!= config
)
2547 cli_printf(c
, 8004, "Stopped due to reconfiguration");
2550 if (d
->export_protocol
&& (d
->export_protocol
->export_state
== ES_DOWN
))
2552 cli_printf(c
, 8005, "Protocol is down");
2557 FIB_ITERATE_PUT(it
, f
);
2560 rt_show_net(c
, n
, d
);
2564 cli_printf(c
, 14, "%d of %d routes for %d networks", d
->show_counter
, d
->rt_counter
, d
->net_counter
);
2566 cli_printf(c
, 0, "");
2568 c
->cont
= c
->cleanup
= NULL
;
2572 rt_show_cleanup(struct cli
*c
)
2574 struct rt_show_data
*d
= c
->rover
;
2576 /* Unlink the iterator */
2577 fit_get(&d
->table
->fib
, &d
->fit
);
2581 rt_show(struct rt_show_data
*d
)
2585 /* Default is either a master table or a table related to a respective protocol */
2586 if (!d
->table
&& d
->export_protocol
) d
->table
= d
->export_protocol
->table
;
2587 if (!d
->table
&& d
->show_protocol
) d
->table
= d
->show_protocol
->table
;
2588 if (!d
->table
) d
->table
= config
->master_rtc
->table
;
2590 /* Filtered routes are neither exported nor have sensible ordering */
2591 if (d
->filtered
&& (d
->export_mode
|| d
->primary_only
))
2594 if (d
->pxlen
== 256)
2596 FIB_ITERATE_INIT(&d
->fit
, &d
->table
->fib
);
2597 this_cli
->cont
= rt_show_cont
;
2598 this_cli
->cleanup
= rt_show_cleanup
;
2599 this_cli
->rover
= d
;
2604 n
= net_route(d
->table
, d
->prefix
, d
->pxlen
);
2606 n
= net_find(d
->table
, d
->prefix
, d
->pxlen
);
2609 rt_show_net(this_cli
, n
, d
);
2614 cli_msg(8001, "Network not in table");
2619 * Documentation for functions declared inline in route.h
2624 * net_find - find a network entry
2625 * @tab: a routing table
2626 * @addr: address of the network
2627 * @len: length of the network prefix
2629 * net_find() looks up the given network in routing table @tab and
2630 * returns a pointer to its &net entry or %NULL if no such network
2633 static inline net
*net_find(rtable
*tab
, ip_addr addr
, unsigned len
)
2637 * net_get - obtain a network entry
2638 * @tab: a routing table
2639 * @addr: address of the network
2640 * @len: length of the network prefix
2642 * net_get() looks up the given network in routing table @tab and
2643 * returns a pointer to its &net entry. If no such entry exists, it's
2646 static inline net
*net_get(rtable
*tab
, ip_addr addr
, unsigned len
)
2650 * rte_cow - copy a route for writing
2651 * @r: a route entry to be copied
2653 * rte_cow() takes a &rte and prepares it for modification. The exact action
2654 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2655 * just returned unchanged, else a new temporary entry with the same contents
2658 * The primary use of this function is inside the filter machinery -- when
2659 * a filter wants to modify &rte contents (to change the preference or to
2660 * attach another set of attributes), it must ensure that the &rte is not
2661 * shared with anyone else (and especially that it isn't stored in any routing
2664 * Result: a pointer to the new writable &rte.
2666 static inline rte
* rte_cow(rte
*r
)