Annotation of embedaddon/bird2/nest/rt-table.c, revision 1.1.1.1
1.1 misho 1: /*
2: * BIRD -- Routing Tables
3: *
4: * (c) 1998--2000 Martin Mares <mj@ucw.cz>
5: *
6: * Can be freely distributed and used under the terms of the GNU GPL.
7: */
8:
9: /**
10: * DOC: Routing tables
11: *
12: * Routing tables are probably the most important structures BIRD uses. They
13: * hold all the information about known networks, the associated routes and
14: * their attributes.
15: *
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.
23: *
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.
29: */
30:
31: #undef LOCAL_DEBUG
32:
33: #include "nest/bird.h"
34: #include "nest/route.h"
35: #include "nest/protocol.h"
36: #include "nest/iface.h"
37: #include "lib/resource.h"
38: #include "lib/event.h"
39: #include "lib/string.h"
40: #include "conf/conf.h"
41: #include "filter/filter.h"
42: #include "filter/data.h"
43: #include "lib/hash.h"
44: #include "lib/string.h"
45: #include "lib/alloca.h"
46:
47: #ifdef CONFIG_BGP
48: #include "proto/bgp/bgp.h"
49: #endif
50:
51: pool *rt_table_pool;
52:
53: static slab *rte_slab;
54: static linpool *rte_update_pool;
55:
56: list routing_tables;
57:
58: static void rt_free_hostcache(rtable *tab);
59: static void rt_notify_hostcache(rtable *tab, net *net);
60: static void rt_update_hostcache(rtable *tab);
61: static void rt_next_hop_update(rtable *tab);
62: static inline void rt_prune_table(rtable *tab);
63:
64:
65: /* Like fib_route(), but skips empty net entries */
66: static inline void *
67: net_route_ip4(rtable *t, net_addr_ip4 *n)
68: {
69: net *r;
70:
71: while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0))
72: {
73: n->pxlen--;
74: ip4_clrbit(&n->prefix, n->pxlen);
75: }
76:
77: return r;
78: }
79:
80: static inline void *
81: net_route_ip6(rtable *t, net_addr_ip6 *n)
82: {
83: net *r;
84:
85: while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0))
86: {
87: n->pxlen--;
88: ip6_clrbit(&n->prefix, n->pxlen);
89: }
90:
91: return r;
92: }
93:
94: static inline void *
95: net_route_ip6_sadr(rtable *t, net_addr_ip6_sadr *n)
96: {
97: struct fib_node *fn;
98:
99: while (1)
100: {
101: net *best = NULL;
102: int best_pxlen = 0;
103:
104: /* We need to do dst first matching. Since sadr addresses are hashed on dst
105: prefix only, find the hash table chain and go through it to find the
106: match with the smallest matching src prefix. */
107: for (fn = fib_get_chain(&t->fib, (net_addr *) n); fn; fn = fn->next)
108: {
109: net_addr_ip6_sadr *a = (void *) fn->addr;
110:
111: if (net_equal_dst_ip6_sadr(n, a) &&
112: net_in_net_src_ip6_sadr(n, a) &&
113: (a->src_pxlen >= best_pxlen))
114: {
115: best = fib_node_to_user(&t->fib, fn);
116: best_pxlen = a->src_pxlen;
117: }
118: }
119:
120: if (best)
121: return best;
122:
123: if (!n->dst_pxlen)
124: break;
125:
126: n->dst_pxlen--;
127: ip6_clrbit(&n->dst_prefix, n->dst_pxlen);
128: }
129:
130: return NULL;
131: }
132:
133: void *
134: net_route(rtable *tab, const net_addr *n)
135: {
136: ASSERT(tab->addr_type == n->type);
137:
138: net_addr *n0 = alloca(n->length);
139: net_copy(n0, n);
140:
141: switch (n->type)
142: {
143: case NET_IP4:
144: case NET_VPN4:
145: case NET_ROA4:
146: return net_route_ip4(tab, (net_addr_ip4 *) n0);
147:
148: case NET_IP6:
149: case NET_VPN6:
150: case NET_ROA6:
151: return net_route_ip6(tab, (net_addr_ip6 *) n0);
152:
153: case NET_IP6_SADR:
154: return net_route_ip6_sadr(tab, (net_addr_ip6_sadr *) n0);
155:
156: default:
157: return NULL;
158: }
159: }
160:
161:
162: static int
163: net_roa_check_ip4(rtable *tab, const net_addr_ip4 *px, u32 asn)
164: {
165: struct net_addr_roa4 n = NET_ADDR_ROA4(px->prefix, px->pxlen, 0, 0);
166: struct fib_node *fn;
167: int anything = 0;
168:
169: while (1)
170: {
171: for (fn = fib_get_chain(&tab->fib, (net_addr *) &n); fn; fn = fn->next)
172: {
173: net_addr_roa4 *roa = (void *) fn->addr;
174: net *r = fib_node_to_user(&tab->fib, fn);
175:
176: if (net_equal_prefix_roa4(roa, &n) && rte_is_valid(r->routes))
177: {
178: anything = 1;
179: if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
180: return ROA_VALID;
181: }
182: }
183:
184: if (n.pxlen == 0)
185: break;
186:
187: n.pxlen--;
188: ip4_clrbit(&n.prefix, n.pxlen);
189: }
190:
191: return anything ? ROA_INVALID : ROA_UNKNOWN;
192: }
193:
194: static int
195: net_roa_check_ip6(rtable *tab, const net_addr_ip6 *px, u32 asn)
196: {
197: struct net_addr_roa6 n = NET_ADDR_ROA6(px->prefix, px->pxlen, 0, 0);
198: struct fib_node *fn;
199: int anything = 0;
200:
201: while (1)
202: {
203: for (fn = fib_get_chain(&tab->fib, (net_addr *) &n); fn; fn = fn->next)
204: {
205: net_addr_roa6 *roa = (void *) fn->addr;
206: net *r = fib_node_to_user(&tab->fib, fn);
207:
208: if (net_equal_prefix_roa6(roa, &n) && rte_is_valid(r->routes))
209: {
210: anything = 1;
211: if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
212: return ROA_VALID;
213: }
214: }
215:
216: if (n.pxlen == 0)
217: break;
218:
219: n.pxlen--;
220: ip6_clrbit(&n.prefix, n.pxlen);
221: }
222:
223: return anything ? ROA_INVALID : ROA_UNKNOWN;
224: }
225:
226: /**
227: * roa_check - check validity of route origination in a ROA table
228: * @tab: ROA table
229: * @n: network prefix to check
230: * @asn: AS number of network prefix
231: *
232: * Implements RFC 6483 route validation for the given network prefix. The
233: * procedure is to find all candidate ROAs - ROAs whose prefixes cover the given
234: * network prefix. If there is no candidate ROA, return ROA_UNKNOWN. If there is
235: * a candidate ROA with matching ASN and maxlen field greater than or equal to
236: * the given prefix length, return ROA_VALID. Otherwise, return ROA_INVALID. If
237: * caller cannot determine origin AS, 0 could be used (in that case ROA_VALID
238: * cannot happen). Table @tab must have type NET_ROA4 or NET_ROA6, network @n
239: * must have type NET_IP4 or NET_IP6, respectively.
240: */
241: int
242: net_roa_check(rtable *tab, const net_addr *n, u32 asn)
243: {
244: if ((tab->addr_type == NET_ROA4) && (n->type == NET_IP4))
245: return net_roa_check_ip4(tab, (const net_addr_ip4 *) n, asn);
246: else if ((tab->addr_type == NET_ROA6) && (n->type == NET_IP6))
247: return net_roa_check_ip6(tab, (const net_addr_ip6 *) n, asn);
248: else
249: return ROA_UNKNOWN; /* Should not happen */
250: }
251:
252: /**
253: * rte_find - find a route
254: * @net: network node
255: * @src: route source
256: *
257: * The rte_find() function returns a route for destination @net
258: * which is from route source @src.
259: */
260: rte *
261: rte_find(net *net, struct rte_src *src)
262: {
263: rte *e = net->routes;
264:
265: while (e && e->attrs->src != src)
266: e = e->next;
267: return e;
268: }
269:
270: /**
271: * rte_get_temp - get a temporary &rte
272: * @a: attributes to assign to the new route (a &rta; in case it's
273: * un-cached, rte_update() will create a cached copy automatically)
274: *
275: * Create a temporary &rte and bind it with the attributes @a.
276: * Also set route preference to the default preference set for
277: * the protocol.
278: */
279: rte *
280: rte_get_temp(rta *a)
281: {
282: rte *e = sl_alloc(rte_slab);
283:
284: e->attrs = a;
285: e->flags = 0;
286: e->pref = 0;
287: return e;
288: }
289:
290: rte *
291: rte_do_cow(rte *r)
292: {
293: rte *e = sl_alloc(rte_slab);
294:
295: memcpy(e, r, sizeof(rte));
296: e->attrs = rta_clone(r->attrs);
297: e->flags = 0;
298: return e;
299: }
300:
301: /**
302: * rte_cow_rta - get a private writable copy of &rte with writable &rta
303: * @r: a route entry to be copied
304: * @lp: a linpool from which to allocate &rta
305: *
306: * rte_cow_rta() takes a &rte and prepares it and associated &rta for
307: * modification. There are three possibilities: First, both &rte and &rta are
308: * private copies, in that case they are returned unchanged. Second, &rte is
309: * private copy, but &rta is cached, in that case &rta is duplicated using
310: * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
311: * both structures are duplicated by rte_do_cow() and rta_do_cow().
312: *
313: * Note that in the second case, cached &rta loses one reference, while private
314: * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
315: * nexthops, ...) with it. To work properly, original shared &rta should have
316: * another reference during the life of created private copy.
317: *
318: * Result: a pointer to the new writable &rte with writable &rta.
319: */
320: rte *
321: rte_cow_rta(rte *r, linpool *lp)
322: {
323: if (!rta_is_cached(r->attrs))
324: return r;
325:
326: r = rte_cow(r);
327: rta *a = rta_do_cow(r->attrs, lp);
328: rta_free(r->attrs);
329: r->attrs = a;
330: return r;
331: }
332:
333:
334: /**
335: * rte_init_tmp_attrs - initialize temporary ea_list for route
336: * @r: route entry to be modified
337: * @lp: linpool from which to allocate attributes
338: * @max: maximum number of added temporary attribus
339: *
340: * This function is supposed to be called from make_tmp_attrs() and
341: * store_tmp_attrs() hooks before rte_make_tmp_attr() / rte_store_tmp_attr()
342: * functions. It allocates &ea_list with length for @max items for temporary
343: * attributes and puts it on top of eattrs stack.
344: */
345: void
346: rte_init_tmp_attrs(rte *r, linpool *lp, uint max)
347: {
348: struct ea_list *e = lp_alloc(lp, sizeof(struct ea_list) + max * sizeof(eattr));
349:
350: e->next = r->attrs->eattrs;
351: e->flags = EALF_SORTED | EALF_TEMP;
352: e->count = 0;
353:
354: r->attrs->eattrs = e;
355: }
356:
357: /**
358: * rte_make_tmp_attr - make temporary eattr from private route fields
359: * @r: route entry to be modified
360: * @id: attribute ID
361: * @type: attribute type
362: * @val: attribute value (u32 or adata ptr)
363: *
364: * This function is supposed to be called from make_tmp_attrs() hook for
365: * each temporary attribute, after temporary &ea_list was initialized by
366: * rte_init_tmp_attrs(). It checks whether temporary attribute is supposed to
367: * be defined (based on route pflags) and if so then it fills &eattr field in
368: * preallocated temporary &ea_list on top of route @r eattrs stack.
369: *
370: * Note that it may require free &eattr in temporary &ea_list, so it must not be
371: * called more times than @max argument of rte_init_tmp_attrs().
372: */
373: void
374: rte_make_tmp_attr(rte *r, uint id, uint type, uintptr_t val)
375: {
376: if (r->pflags & EA_ID_FLAG(id))
377: {
378: ea_list *e = r->attrs->eattrs;
379: eattr *a = &e->attrs[e->count++];
380: a->id = id;
381: a->type = type;
382: a->flags = 0;
383:
384: if (type & EAF_EMBEDDED)
385: a->u.data = (u32) val;
386: else
387: a->u.ptr = (struct adata *) val;
388: }
389: }
390:
391: /**
392: * rte_store_tmp_attr - store temporary eattr to private route fields
393: * @r: route entry to be modified
394: * @id: attribute ID
395: *
396: * This function is supposed to be called from store_tmp_attrs() hook for
397: * each temporary attribute, after temporary &ea_list was initialized by
398: * rte_init_tmp_attrs(). It checks whether temporary attribute is defined in
399: * route @r eattrs stack, updates route pflags accordingly, undefines it by
400: * filling &eattr field in preallocated temporary &ea_list on top of the eattrs
401: * stack, and returns the value. Caller is supposed to store it in the
402: * appropriate private field.
403: *
404: * Note that it may require free &eattr in temporary &ea_list, so it must not be
405: * called more times than @max argument of rte_init_tmp_attrs()
406: */
407: uintptr_t
408: rte_store_tmp_attr(rte *r, uint id)
409: {
410: ea_list *e = r->attrs->eattrs;
411: eattr *a = ea_find(e->next, id);
412:
413: if (a)
414: {
415: e->attrs[e->count++] = (struct eattr) { .id = id, .type = EAF_TYPE_UNDEF };
416: r->pflags |= EA_ID_FLAG(id);
417: return (a->type & EAF_EMBEDDED) ? a->u.data : (uintptr_t) a->u.ptr;
418: }
419: else
420: {
421: r->pflags &= ~EA_ID_FLAG(id);
422: return 0;
423: }
424: }
425:
426: /**
427: * rte_make_tmp_attrs - prepare route by adding all relevant temporary route attributes
428: * @r: route entry to be modified (may be replaced if COW)
429: * @lp: linpool from which to allocate attributes
430: * @old_attrs: temporary ref to old &rta (may be NULL)
431: *
432: * This function expands privately stored protocol-dependent route attributes
433: * to a uniform &eattr / &ea_list representation. It is essentially a wrapper
434: * around protocol make_tmp_attrs() hook, which does some additional work like
435: * ensuring that route @r is writable.
436: *
437: * The route @r may be read-only (with %REF_COW flag), in that case rw copy is
438: * obtained by rte_cow() and @r is replaced. If @rte is originally rw, it may be
439: * directly modified (and it is never copied).
440: *
441: * If the @old_attrs ptr is supplied, the function obtains another reference of
442: * old cached &rta, that is necessary in some cases (see rte_cow_rta() for
443: * details). It is freed by rte_store_tmp_attrs(), or manually by rta_free().
444: *
445: * Generally, if caller ensures that @r is read-only (e.g. in route export) then
446: * it may ignore @old_attrs (and set it to NULL), but must handle replacement of
447: * @r. If caller ensures that @r is writable (e.g. in route import) then it may
448: * ignore replacement of @r, but it must handle @old_attrs.
449: */
450: void
451: rte_make_tmp_attrs(rte **r, linpool *lp, rta **old_attrs)
452: {
453: void (*make_tmp_attrs)(rte *r, linpool *lp);
454: make_tmp_attrs = (*r)->attrs->src->proto->make_tmp_attrs;
455:
456: if (!make_tmp_attrs)
457: return;
458:
459: /* We may need to keep ref to old attributes, will be freed in rte_store_tmp_attrs() */
460: if (old_attrs)
461: *old_attrs = rta_is_cached((*r)->attrs) ? rta_clone((*r)->attrs) : NULL;
462:
463: *r = rte_cow_rta(*r, lp);
464: make_tmp_attrs(*r, lp);
465: }
466:
467: /**
468: * rte_store_tmp_attrs - store temporary route attributes back to private route fields
469: * @r: route entry to be modified
470: * @lp: linpool from which to allocate attributes
471: * @old_attrs: temporary ref to old &rta
472: *
473: * This function stores temporary route attributes that were expanded by
474: * rte_make_tmp_attrs() back to private route fields and also undefines them.
475: * It is essentially a wrapper around protocol store_tmp_attrs() hook, which
476: * does some additional work like shortcut if there is no change and cleanup
477: * of @old_attrs reference obtained by rte_make_tmp_attrs().
478: */
479: static void
480: rte_store_tmp_attrs(rte *r, linpool *lp, rta *old_attrs)
481: {
482: void (*store_tmp_attrs)(rte *rt, linpool *lp);
483: store_tmp_attrs = r->attrs->src->proto->store_tmp_attrs;
484:
485: if (!store_tmp_attrs)
486: return;
487:
488: ASSERT(!rta_is_cached(r->attrs));
489:
490: /* If there is no new ea_list, we just skip the temporary ea_list */
491: ea_list *ea = r->attrs->eattrs;
492: if (ea && (ea->flags & EALF_TEMP))
493: r->attrs->eattrs = ea->next;
494: else
495: store_tmp_attrs(r, lp);
496:
497: /* Free ref we got in rte_make_tmp_attrs(), have to do rta_lookup() first */
498: r->attrs = rta_lookup(r->attrs);
499: rta_free(old_attrs);
500: }
501:
502:
503: static int /* Actually better or at least as good as */
504: rte_better(rte *new, rte *old)
505: {
506: int (*better)(rte *, rte *);
507:
508: if (!rte_is_valid(old))
509: return 1;
510: if (!rte_is_valid(new))
511: return 0;
512:
513: if (new->pref > old->pref)
514: return 1;
515: if (new->pref < old->pref)
516: return 0;
517: if (new->attrs->src->proto->proto != old->attrs->src->proto->proto)
518: {
519: /*
520: * If the user has configured protocol preferences, so that two different protocols
521: * have the same preference, try to break the tie by comparing addresses. Not too
522: * useful, but keeps the ordering of routes unambiguous.
523: */
524: return new->attrs->src->proto->proto > old->attrs->src->proto->proto;
525: }
526: if (better = new->attrs->src->proto->rte_better)
527: return better(new, old);
528: return 0;
529: }
530:
531: static int
532: rte_mergable(rte *pri, rte *sec)
533: {
534: int (*mergable)(rte *, rte *);
535:
536: if (!rte_is_valid(pri) || !rte_is_valid(sec))
537: return 0;
538:
539: if (pri->pref != sec->pref)
540: return 0;
541:
542: if (pri->attrs->src->proto->proto != sec->attrs->src->proto->proto)
543: return 0;
544:
545: if (mergable = pri->attrs->src->proto->rte_mergable)
546: return mergable(pri, sec);
547:
548: return 0;
549: }
550:
551: static void
552: rte_trace(struct proto *p, rte *e, int dir, char *msg)
553: {
554: log(L_TRACE "%s %c %s %N %s", p->name, dir, msg, e->net->n.addr, rta_dest_name(e->attrs->dest));
555: }
556:
557: static inline void
558: rte_trace_in(uint flag, struct proto *p, rte *e, char *msg)
559: {
560: if (p->debug & flag)
561: rte_trace(p, e, '>', msg);
562: }
563:
564: static inline void
565: rte_trace_out(uint flag, struct proto *p, rte *e, char *msg)
566: {
567: if (p->debug & flag)
568: rte_trace(p, e, '<', msg);
569: }
570:
571: static rte *
572: export_filter_(struct channel *c, rte *rt0, rte **rt_free, linpool *pool, int silent)
573: {
574: struct proto *p = c->proto;
575: const struct filter *filter = c->out_filter;
576: struct proto_stats *stats = &c->stats;
577: rte *rt;
578: int v;
579:
580: rt = rt0;
581: *rt_free = NULL;
582:
583: v = p->preexport ? p->preexport(p, &rt, pool) : 0;
584: if (v < 0)
585: {
586: if (silent)
587: goto reject;
588:
589: stats->exp_updates_rejected++;
590: if (v == RIC_REJECT)
591: rte_trace_out(D_FILTERS, p, rt, "rejected by protocol");
592: goto reject;
593: }
594: if (v > 0)
595: {
596: if (!silent)
597: rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol");
598: goto accept;
599: }
600:
601: rte_make_tmp_attrs(&rt, pool, NULL);
602:
603: v = filter && ((filter == FILTER_REJECT) ||
604: (f_run(filter, &rt, pool,
605: (silent ? FF_SILENT : 0)) > F_ACCEPT));
606: if (v)
607: {
608: if (silent)
609: goto reject;
610:
611: stats->exp_updates_filtered++;
612: rte_trace_out(D_FILTERS, p, rt, "filtered out");
613: goto reject;
614: }
615:
616: accept:
617: if (rt != rt0)
618: *rt_free = rt;
619: return rt;
620:
621: reject:
622: /* Discard temporary rte */
623: if (rt != rt0)
624: rte_free(rt);
625: return NULL;
626: }
627:
628: static inline rte *
629: export_filter(struct channel *c, rte *rt0, rte **rt_free, int silent)
630: {
631: return export_filter_(c, rt0, rt_free, rte_update_pool, silent);
632: }
633:
634: static void
635: do_rt_notify(struct channel *c, net *net, rte *new, rte *old, int refeed)
636: {
637: struct proto *p = c->proto;
638: struct proto_stats *stats = &c->stats;
639:
640: /*
641: * First, apply export limit.
642: *
643: * Export route limits has several problems. Because exp_routes
644: * counter is reset before refeed, we don't really know whether
645: * limit is breached and whether the update is new or not. Therefore
646: * the number of really exported routes may exceed the limit
647: * temporarily (routes exported before and new routes in refeed).
648: *
649: * Minor advantage is that if the limit is decreased and refeed is
650: * requested, the number of exported routes really decrease.
651: *
652: * Second problem is that with export limits, we don't know whether
653: * old was really exported (it might be blocked by limit). When a
654: * withdraw is exported, we announce it even when the previous
655: * update was blocked. This is not a big issue, but the same problem
656: * is in updating exp_routes counter. Therefore, to be consistent in
657: * increases and decreases of exp_routes, we count exported routes
658: * regardless of blocking by limits.
659: *
660: * Similar problem is in handling updates - when a new route is
661: * received and blocking is active, the route would be blocked, but
662: * when an update for the route will be received later, the update
663: * would be propagated (as old != NULL). Therefore, we have to block
664: * also non-new updates (contrary to import blocking).
665: */
666:
667: struct channel_limit *l = &c->out_limit;
668: if (l->action && new)
669: {
670: if ((!old || refeed) && (stats->exp_routes >= l->limit))
671: channel_notify_limit(c, l, PLD_OUT, stats->exp_routes);
672:
673: if (l->state == PLS_BLOCKED)
674: {
675: stats->exp_routes++; /* see note above */
676: stats->exp_updates_rejected++;
677: rte_trace_out(D_FILTERS, p, new, "rejected [limit]");
678: new = NULL;
679:
680: if (!old)
681: return;
682: }
683: }
684:
685: if (c->out_table && !rte_update_out(c, net->n.addr, new, old, refeed))
686: return;
687:
688: if (new)
689: stats->exp_updates_accepted++;
690: else
691: stats->exp_withdraws_accepted++;
692:
693: /* Hack: We do not decrease exp_routes during refeed, we instead
694: reset exp_routes at the start of refeed. */
695: if (new)
696: stats->exp_routes++;
697: if (old && !refeed)
698: stats->exp_routes--;
699:
700: if (p->debug & D_ROUTES)
701: {
702: if (new && old)
703: rte_trace_out(D_ROUTES, p, new, "replaced");
704: else if (new)
705: rte_trace_out(D_ROUTES, p, new, "added");
706: else if (old)
707: rte_trace_out(D_ROUTES, p, old, "removed");
708: }
709: p->rt_notify(p, c, net, new, old);
710: }
711:
712: static void
713: rt_notify_basic(struct channel *c, net *net, rte *new0, rte *old0, int refeed)
714: {
715: struct proto *p = c->proto;
716:
717: rte *new = new0;
718: rte *old = old0;
719: rte *new_free = NULL;
720: rte *old_free = NULL;
721:
722: if (new)
723: c->stats.exp_updates_received++;
724: else
725: c->stats.exp_withdraws_received++;
726:
727: /*
728: * This is a tricky part - we don't know whether route 'old' was exported to
729: * protocol 'p' or was filtered by the export filter. We try to run the export
730: * filter to know this to have a correct value in 'old' argument of rte_update
731: * (and proper filter value).
732: *
733: * This is broken because 'configure soft' may change filters but keep routes.
734: * Refeed cycle is expected to be called after change of the filters and with
735: * old == new, therefore we do not even try to run the filter on an old route.
736: * This may lead to 'spurious withdraws' but ensure that there are no 'missing
737: * withdraws'.
738: *
739: * This is not completely safe as there is a window between reconfiguration
740: * and the end of refeed - if a newly filtered route disappears during this
741: * period, proper withdraw is not sent (because old would be also filtered)
742: * and the route is not refeeded (because it disappeared before that).
743: * This is handled below as a special case.
744: */
745:
746: if (new)
747: new = export_filter(c, new, &new_free, 0);
748:
749: if (old && !refeed)
750: old = export_filter(c, old, &old_free, 1);
751:
752: if (!new && !old)
753: {
754: /*
755: * As mentioned above, 'old' value may be incorrect in some race conditions.
756: * We generally ignore it with two exceptions:
757: *
758: * First, withdraw to pipe protocol. In that case we rather propagate
759: * unfiltered withdraws regardless of export filters to ensure that when a
760: * protocol is flushed, its routes are removed from all tables. Possible
761: * spurious unfiltered withdraws are not problem here as they are ignored if
762: * there is no corresponding route at the other end of the pipe.
763: *
764: * Second, recent filter change. If old route is older than filter change,
765: * then it was previously evaluated by a different filter and we do not know
766: * whether it was really propagated. In that case we rather send spurious
767: * withdraw than do nothing and possibly cause phantom routes.
768: *
769: * In both cases wqe directly call rt_notify() hook instead of
770: * do_rt_notify() to avoid logging and stat counters.
771: */
772:
773: int pipe_withdraw = 0, filter_change = 0;
774: #ifdef CONFIG_PIPE
775: pipe_withdraw = (p->proto == &proto_pipe) && !new0;
776: #endif
777: filter_change = old0 && (old0->lastmod <= c->last_tx_filter_change);
778:
779: if ((pipe_withdraw || filter_change) && (p != old0->sender->proto))
780: {
781: c->stats.exp_withdraws_accepted++;
782: p->rt_notify(p, c, net, NULL, old0);
783: }
784:
785: return;
786: }
787:
788: do_rt_notify(c, net, new, old, refeed);
789:
790: /* Discard temporary rte's */
791: if (new_free)
792: rte_free(new_free);
793: if (old_free)
794: rte_free(old_free);
795: }
796:
797: static void
798: rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_changed, rte *before_old, int feed)
799: {
800: struct proto *p = c->proto;
801:
802: rte *r;
803: rte *new_best = NULL;
804: rte *old_best = NULL;
805: rte *new_free = NULL;
806: rte *old_free = NULL;
807:
808: /* Used to track whether we met old_changed position. If before_old is NULL
809: old_changed was the first and we met it implicitly before current best route. */
810: int old_meet = old_changed && !before_old;
811:
812: /* Note that before_old is either NULL or valid (not rejected) route.
813: If old_changed is valid, before_old have to be too. If old changed route
814: was not valid, caller must use NULL for both old_changed and before_old. */
815:
816: if (new_changed)
817: c->stats.exp_updates_received++;
818: else
819: c->stats.exp_withdraws_received++;
820:
821: /* First, find the new_best route - first accepted by filters */
822: for (r=net->routes; rte_is_valid(r); r=r->next)
823: {
824: if (new_best = export_filter(c, r, &new_free, 0))
825: break;
826:
827: /* Note if we walked around the position of old_changed route */
828: if (r == before_old)
829: old_meet = 1;
830: }
831:
832: /*
833: * Second, handle the feed case. That means we do not care for
834: * old_best. It is NULL for feed, and the new_best for refeed.
835: * For refeed, there is a hack similar to one in rt_notify_basic()
836: * to ensure withdraws in case of changed filters
837: */
838: if (feed)
839: {
840: if (feed == 2) /* refeed */
841: old_best = new_best ? new_best :
842: (rte_is_valid(net->routes) ? net->routes : NULL);
843: else
844: old_best = NULL;
845:
846: if (!new_best && !old_best)
847: return;
848:
849: goto found;
850: }
851:
852: /*
853: * Now, we find the old_best route. Generally, it is the same as the
854: * new_best, unless new_best is the same as new_changed or
855: * old_changed is accepted before new_best.
856: *
857: * There are four cases:
858: *
859: * - We would find and accept old_changed before new_best, therefore
860: * old_changed is old_best. In remaining cases we suppose this
861: * is not true.
862: *
863: * - We found no new_best, therefore there is also no old_best and
864: * we ignore this withdraw.
865: *
866: * - We found new_best different than new_changed, therefore
867: * old_best is the same as new_best and we ignore this update.
868: *
869: * - We found new_best the same as new_changed, therefore it cannot
870: * be old_best and we have to continue search for old_best.
871: *
872: * There is also a hack to ensure consistency in case of changed filters.
873: * It does not find the proper old_best, just selects a non-NULL route.
874: */
875:
876: /* Hack for changed filters */
877: if (old_changed &&
878: (p != old_changed->sender->proto) &&
879: (old_changed->lastmod <= c->last_tx_filter_change))
880: {
881: old_best = old_changed;
882: goto found;
883: }
884:
885: /* First case */
886: if (old_meet)
887: if (old_best = export_filter(c, old_changed, &old_free, 1))
888: goto found;
889:
890: /* Second case */
891: if (!new_best)
892: return;
893:
894: /* Third case, we use r instead of new_best, because export_filter() could change it */
895: if (r != new_changed)
896: {
897: if (new_free)
898: rte_free(new_free);
899: return;
900: }
901:
902: /* Fourth case */
903: for (r=r->next; rte_is_valid(r); r=r->next)
904: {
905: if (old_best = export_filter(c, r, &old_free, 1))
906: goto found;
907:
908: if (r == before_old)
909: if (old_best = export_filter(c, old_changed, &old_free, 1))
910: goto found;
911: }
912:
913: /* Implicitly, old_best is NULL and new_best is non-NULL */
914:
915: found:
916: do_rt_notify(c, net, new_best, old_best, (feed == 2));
917:
918: /* Discard temporary rte's */
919: if (new_free)
920: rte_free(new_free);
921: if (old_free)
922: rte_free(old_free);
923: }
924:
925:
926: static struct nexthop *
927: nexthop_merge_rta(struct nexthop *nhs, rta *a, linpool *pool, int max)
928: {
929: return nexthop_merge(nhs, &(a->nh), 1, 0, max, pool);
930: }
931:
932: rte *
933: rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int silent)
934: {
935: // struct proto *p = c->proto;
936: struct nexthop *nhs = NULL;
937: rte *best0, *best, *rt0, *rt, *tmp;
938:
939: best0 = net->routes;
940: *rt_free = NULL;
941:
942: if (!rte_is_valid(best0))
943: return NULL;
944:
945: best = export_filter_(c, best0, rt_free, pool, silent);
946:
947: if (!best || !rte_is_reachable(best))
948: return best;
949:
950: for (rt0 = best0->next; rt0; rt0 = rt0->next)
951: {
952: if (!rte_mergable(best0, rt0))
953: continue;
954:
955: rt = export_filter_(c, rt0, &tmp, pool, 1);
956:
957: if (!rt)
958: continue;
959:
960: if (rte_is_reachable(rt))
961: nhs = nexthop_merge_rta(nhs, rt->attrs, pool, c->merge_limit);
962:
963: if (tmp)
964: rte_free(tmp);
965: }
966:
967: if (nhs)
968: {
969: nhs = nexthop_merge_rta(nhs, best->attrs, pool, c->merge_limit);
970:
971: if (nhs->next)
972: {
973: best = rte_cow_rta(best, pool);
974: nexthop_link(best->attrs, nhs);
975: }
976: }
977:
978: if (best != best0)
979: *rt_free = best;
980:
981: return best;
982: }
983:
984:
985: static void
986: rt_notify_merged(struct channel *c, net *net, rte *new_changed, rte *old_changed,
987: rte *new_best, rte*old_best, int refeed)
988: {
989: // struct proto *p = c->proto;
990:
991: rte *new_best_free = NULL;
992: rte *old_best_free = NULL;
993: rte *new_changed_free = NULL;
994: rte *old_changed_free = NULL;
995:
996: /* We assume that all rte arguments are either NULL or rte_is_valid() */
997:
998: /* This check should be done by the caller */
999: if (!new_best && !old_best)
1000: return;
1001:
1002: /* Check whether the change is relevant to the merged route */
1003: if ((new_best == old_best) && !refeed)
1004: {
1005: new_changed = rte_mergable(new_best, new_changed) ?
1006: export_filter(c, new_changed, &new_changed_free, 1) : NULL;
1007:
1008: old_changed = rte_mergable(old_best, old_changed) ?
1009: export_filter(c, old_changed, &old_changed_free, 1) : NULL;
1010:
1011: if (!new_changed && !old_changed)
1012: return;
1013: }
1014:
1015: if (new_best)
1016: c->stats.exp_updates_received++;
1017: else
1018: c->stats.exp_withdraws_received++;
1019:
1020: /* Prepare new merged route */
1021: if (new_best)
1022: new_best = rt_export_merged(c, net, &new_best_free, rte_update_pool, 0);
1023:
1024: /* Prepare old merged route (without proper merged next hops) */
1025: /* There are some issues with running filter on old route - see rt_notify_basic() */
1026: if (old_best && !refeed)
1027: old_best = export_filter(c, old_best, &old_best_free, 1);
1028:
1029: if (new_best || old_best)
1030: do_rt_notify(c, net, new_best, old_best, refeed);
1031:
1032: /* Discard temporary rte's */
1033: if (new_best_free)
1034: rte_free(new_best_free);
1035: if (old_best_free)
1036: rte_free(old_best_free);
1037: if (new_changed_free)
1038: rte_free(new_changed_free);
1039: if (old_changed_free)
1040: rte_free(old_changed_free);
1041: }
1042:
1043:
1044: /**
1045: * rte_announce - announce a routing table change
1046: * @tab: table the route has been added to
1047: * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
1048: * @net: network in question
1049: * @new: the new route to be announced
1050: * @old: the previous route for the same network
1051: * @new_best: the new best route for the same network
1052: * @old_best: the previous best route for the same network
1053: * @before_old: The previous route before @old for the same network.
1054: * If @before_old is NULL @old was the first.
1055: *
1056: * This function gets a routing table update and announces it
1057: * to all protocols that acccepts given type of route announcement
1058: * and are connected to the same table by their announcement hooks.
1059: *
1060: * Route announcement of type %RA_OPTIMAL si generated when optimal
1061: * route (in routing table @tab) changes. In that case @old stores the
1062: * old optimal route.
1063: *
1064: * Route announcement of type %RA_ANY si generated when any route (in
1065: * routing table @tab) changes In that case @old stores the old route
1066: * from the same protocol.
1067: *
1068: * For each appropriate protocol, we first call its preexport()
1069: * hook which performs basic checks on the route (each protocol has a
1070: * right to veto or force accept of the route before any filter is
1071: * asked) and adds default values of attributes specific to the new
1072: * protocol (metrics, tags etc.). Then it consults the protocol's
1073: * export filter and if it accepts the route, the rt_notify() hook of
1074: * the protocol gets called.
1075: */
1076: static void
1077: rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old,
1078: rte *new_best, rte *old_best, rte *before_old)
1079: {
1080: if (!rte_is_valid(new))
1081: new = NULL;
1082:
1083: if (!rte_is_valid(old))
1084: old = before_old = NULL;
1085:
1086: if (!rte_is_valid(new_best))
1087: new_best = NULL;
1088:
1089: if (!rte_is_valid(old_best))
1090: old_best = NULL;
1091:
1092: if (!old && !new)
1093: return;
1094:
1095: if (type == RA_OPTIMAL)
1096: {
1097: if (new)
1098: new->sender->stats.pref_routes++;
1099: if (old)
1100: old->sender->stats.pref_routes--;
1101:
1102: if (tab->hostcache)
1103: rt_notify_hostcache(tab, net);
1104: }
1105:
1106: struct channel *c; node *n;
1107: WALK_LIST2(c, n, tab->channels, table_node)
1108: {
1109: if (c->export_state == ES_DOWN)
1110: continue;
1111:
1112: if (c->ra_mode == type)
1113: if (type == RA_ACCEPTED)
1114: rt_notify_accepted(c, net, new, old, before_old, 0);
1115: else if (type == RA_MERGED)
1116: rt_notify_merged(c, net, new, old, new_best, old_best, 0);
1117: else
1118: rt_notify_basic(c, net, new, old, 0);
1119: }
1120: }
1121:
1122: static inline int
1123: rte_validate(rte *e)
1124: {
1125: int c;
1126: net *n = e->net;
1127:
1128: if (!net_validate(n->n.addr))
1129: {
1130: log(L_WARN "Ignoring bogus prefix %N received via %s",
1131: n->n.addr, e->sender->proto->name);
1132: return 0;
1133: }
1134:
1135: /* FIXME: better handling different nettypes */
1136: c = !net_is_flow(n->n.addr) ?
1137: net_classify(n->n.addr): (IADDR_HOST | SCOPE_UNIVERSE);
1138: if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
1139: {
1140: log(L_WARN "Ignoring bogus route %N received via %s",
1141: n->n.addr, e->sender->proto->name);
1142: return 0;
1143: }
1144:
1145: if (net_type_match(n->n.addr, NB_DEST) == !e->attrs->dest)
1146: {
1147: log(L_WARN "Ignoring route %N with invalid dest %d received via %s",
1148: n->n.addr, e->attrs->dest, e->sender->proto->name);
1149: return 0;
1150: }
1151:
1152: if ((e->attrs->dest == RTD_UNICAST) && !nexthop_is_sorted(&(e->attrs->nh)))
1153: {
1154: log(L_WARN "Ignoring unsorted multipath route %N received via %s",
1155: n->n.addr, e->sender->proto->name);
1156: return 0;
1157: }
1158:
1159: return 1;
1160: }
1161:
1162: /**
1163: * rte_free - delete a &rte
1164: * @e: &rte to be deleted
1165: *
1166: * rte_free() deletes the given &rte from the routing table it's linked to.
1167: */
1168: void
1169: rte_free(rte *e)
1170: {
1171: if (rta_is_cached(e->attrs))
1172: rta_free(e->attrs);
1173: sl_free(rte_slab, e);
1174: }
1175:
1176: static inline void
1177: rte_free_quick(rte *e)
1178: {
1179: rta_free(e->attrs);
1180: sl_free(rte_slab, e);
1181: }
1182:
1183: static int
1184: rte_same(rte *x, rte *y)
1185: {
1186: /* rte.flags are not checked, as they are mostly internal to rtable */
1187: return
1188: x->attrs == y->attrs &&
1189: x->pflags == y->pflags &&
1190: x->pref == y->pref &&
1191: (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y)) &&
1192: rte_is_filtered(x) == rte_is_filtered(y);
1193: }
1194:
1195: static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); }
1196:
1197: static void
1198: rte_recalculate(struct channel *c, net *net, rte *new, struct rte_src *src)
1199: {
1200: struct proto *p = c->proto;
1201: struct rtable *table = c->table;
1202: struct proto_stats *stats = &c->stats;
1203: static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS;
1204: rte *before_old = NULL;
1205: rte *old_best = net->routes;
1206: rte *old = NULL;
1207: rte **k;
1208:
1209: k = &net->routes; /* Find and remove original route from the same protocol */
1210: while (old = *k)
1211: {
1212: if (old->attrs->src == src)
1213: {
1214: /* If there is the same route in the routing table but from
1215: * a different sender, then there are two paths from the
1216: * source protocol to this routing table through transparent
1217: * pipes, which is not allowed.
1218: *
1219: * We log that and ignore the route. If it is withdraw, we
1220: * ignore it completely (there might be 'spurious withdraws',
1221: * see FIXME in do_rte_announce())
1222: */
1223: if (old->sender->proto != p)
1224: {
1225: if (new)
1226: {
1227: log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %N to table %s",
1228: net->n.addr, table->name);
1229: rte_free_quick(new);
1230: }
1231: return;
1232: }
1233:
1234: if (new && rte_same(old, new))
1235: {
1236: /* No changes, ignore the new route and refresh the old one */
1237:
1238: old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY);
1239:
1240: if (!rte_is_filtered(new))
1241: {
1242: stats->imp_updates_ignored++;
1243: rte_trace_in(D_ROUTES, p, new, "ignored");
1244: }
1245:
1246: rte_free_quick(new);
1247: return;
1248: }
1249: *k = old->next;
1250: table->rt_count--;
1251: break;
1252: }
1253: k = &old->next;
1254: before_old = old;
1255: }
1256:
1257: if (!old)
1258: before_old = NULL;
1259:
1260: if (!old && !new)
1261: {
1262: stats->imp_withdraws_ignored++;
1263: return;
1264: }
1265:
1266: int new_ok = rte_is_ok(new);
1267: int old_ok = rte_is_ok(old);
1268:
1269: struct channel_limit *l = &c->rx_limit;
1270: if (l->action && !old && new && !c->in_table)
1271: {
1272: u32 all_routes = stats->imp_routes + stats->filt_routes;
1273:
1274: if (all_routes >= l->limit)
1275: channel_notify_limit(c, l, PLD_RX, all_routes);
1276:
1277: if (l->state == PLS_BLOCKED)
1278: {
1279: /* In receive limit the situation is simple, old is NULL so
1280: we just free new and exit like nothing happened */
1281:
1282: stats->imp_updates_ignored++;
1283: rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
1284: rte_free_quick(new);
1285: return;
1286: }
1287: }
1288:
1289: l = &c->in_limit;
1290: if (l->action && !old_ok && new_ok)
1291: {
1292: if (stats->imp_routes >= l->limit)
1293: channel_notify_limit(c, l, PLD_IN, stats->imp_routes);
1294:
1295: if (l->state == PLS_BLOCKED)
1296: {
1297: /* In import limit the situation is more complicated. We
1298: shouldn't just drop the route, we should handle it like
1299: it was filtered. We also have to continue the route
1300: processing if old or new is non-NULL, but we should exit
1301: if both are NULL as this case is probably assumed to be
1302: already handled. */
1303:
1304: stats->imp_updates_ignored++;
1305: rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
1306:
1307: if (c->in_keep_filtered)
1308: new->flags |= REF_FILTERED;
1309: else
1310: { rte_free_quick(new); new = NULL; }
1311:
1312: /* Note that old && !new could be possible when
1313: c->in_keep_filtered changed in the recent past. */
1314:
1315: if (!old && !new)
1316: return;
1317:
1318: new_ok = 0;
1319: goto skip_stats1;
1320: }
1321: }
1322:
1323: if (new_ok)
1324: stats->imp_updates_accepted++;
1325: else if (old_ok)
1326: stats->imp_withdraws_accepted++;
1327: else
1328: stats->imp_withdraws_ignored++;
1329:
1330: skip_stats1:
1331:
1332: if (new)
1333: rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++;
1334: if (old)
1335: rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--;
1336:
1337: if (table->config->sorted)
1338: {
1339: /* If routes are sorted, just insert new route to appropriate position */
1340: if (new)
1341: {
1342: if (before_old && !rte_better(new, before_old))
1343: k = &before_old->next;
1344: else
1345: k = &net->routes;
1346:
1347: for (; *k; k=&(*k)->next)
1348: if (rte_better(new, *k))
1349: break;
1350:
1351: new->next = *k;
1352: *k = new;
1353: table->rt_count++;
1354: }
1355: }
1356: else
1357: {
1358: /* If routes are not sorted, find the best route and move it on
1359: the first position. There are several optimized cases. */
1360:
1361: if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
1362: goto do_recalculate;
1363:
1364: if (new && rte_better(new, old_best))
1365: {
1366: /* The first case - the new route is cleary optimal,
1367: we link it at the first position */
1368:
1369: new->next = net->routes;
1370: net->routes = new;
1371: table->rt_count++;
1372: }
1373: else if (old == old_best)
1374: {
1375: /* The second case - the old best route disappeared, we add the
1376: new route (if we have any) to the list (we don't care about
1377: position) and then we elect the new optimal route and relink
1378: that route at the first position and announce it. New optimal
1379: route might be NULL if there is no more routes */
1380:
1381: do_recalculate:
1382: /* Add the new route to the list */
1383: if (new)
1384: {
1385: new->next = net->routes;
1386: net->routes = new;
1387: table->rt_count++;
1388: }
1389:
1390: /* Find a new optimal route (if there is any) */
1391: if (net->routes)
1392: {
1393: rte **bp = &net->routes;
1394: for (k=&(*bp)->next; *k; k=&(*k)->next)
1395: if (rte_better(*k, *bp))
1396: bp = k;
1397:
1398: /* And relink it */
1399: rte *best = *bp;
1400: *bp = best->next;
1401: best->next = net->routes;
1402: net->routes = best;
1403: }
1404: }
1405: else if (new)
1406: {
1407: /* The third case - the new route is not better than the old
1408: best route (therefore old_best != NULL) and the old best
1409: route was not removed (therefore old_best == net->routes).
1410: We just link the new route after the old best route. */
1411:
1412: ASSERT(net->routes != NULL);
1413: new->next = net->routes->next;
1414: net->routes->next = new;
1415: table->rt_count++;
1416: }
1417: /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1418: }
1419:
1420: if (new)
1421: new->lastmod = current_time();
1422:
1423: /* Log the route change */
1424: if (p->debug & D_ROUTES)
1425: {
1426: if (new_ok)
1427: rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added");
1428: else if (old_ok)
1429: {
1430: if (old != old_best)
1431: rte_trace(p, old, '>', "removed");
1432: else if (rte_is_ok(net->routes))
1433: rte_trace(p, old, '>', "removed [replaced]");
1434: else
1435: rte_trace(p, old, '>', "removed [sole]");
1436: }
1437: }
1438:
1439: /* Propagate the route change */
1440: rte_announce(table, RA_ANY, net, new, old, NULL, NULL, NULL);
1441: if (net->routes != old_best)
1442: rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, NULL, NULL);
1443: if (table->config->sorted)
1444: rte_announce(table, RA_ACCEPTED, net, new, old, NULL, NULL, before_old);
1445: rte_announce(table, RA_MERGED, net, new, old, net->routes, old_best, NULL);
1446:
1447: if (!net->routes &&
1448: (table->gc_counter++ >= table->config->gc_max_ops) &&
1449: (table->gc_time + table->config->gc_min_time <= current_time()))
1450: rt_schedule_prune(table);
1451:
1452: if (old_ok && p->rte_remove)
1453: p->rte_remove(net, old);
1454: if (new_ok && p->rte_insert)
1455: p->rte_insert(net, new);
1456:
1457: if (old)
1458: rte_free_quick(old);
1459: }
1460:
1461: static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */
1462:
1463: static inline void
1464: rte_update_lock(void)
1465: {
1466: rte_update_nest_cnt++;
1467: }
1468:
1469: static inline void
1470: rte_update_unlock(void)
1471: {
1472: if (!--rte_update_nest_cnt)
1473: lp_flush(rte_update_pool);
1474: }
1475:
1476: static inline void
1477: rte_hide_dummy_routes(net *net, rte **dummy)
1478: {
1479: if (net->routes && net->routes->attrs->source == RTS_DUMMY)
1480: {
1481: *dummy = net->routes;
1482: net->routes = (*dummy)->next;
1483: }
1484: }
1485:
1486: static inline void
1487: rte_unhide_dummy_routes(net *net, rte **dummy)
1488: {
1489: if (*dummy)
1490: {
1491: (*dummy)->next = net->routes;
1492: net->routes = *dummy;
1493: }
1494: }
1495:
1496: /**
1497: * rte_update - enter a new update to a routing table
1498: * @table: table to be updated
1499: * @c: channel doing the update
1500: * @net: network node
1501: * @p: protocol submitting the update
1502: * @src: protocol originating the update
1503: * @new: a &rte representing the new route or %NULL for route removal.
1504: *
1505: * This function is called by the routing protocols whenever they discover
1506: * a new route or wish to update/remove an existing route. The right announcement
1507: * sequence is to build route attributes first (either un-cached with @aflags set
1508: * to zero or a cached one using rta_lookup(); in this case please note that
1509: * you need to increase the use count of the attributes yourself by calling
1510: * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1511: * the appropriate data and finally submit the new &rte by calling rte_update().
1512: *
1513: * @src specifies the protocol that originally created the route and the meaning
1514: * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1515: * same value as @new->attrs->proto. @p specifies the protocol that called
1516: * rte_update(). In most cases it is the same protocol as @src. rte_update()
1517: * stores @p in @new->sender;
1518: *
1519: * When rte_update() gets any route, it automatically validates it (checks,
1520: * whether the network and next hop address are valid IP addresses and also
1521: * whether a normal routing protocol doesn't try to smuggle a host or link
1522: * scope route to the table), converts all protocol dependent attributes stored
1523: * in the &rte to temporary extended attributes, consults import filters of the
1524: * protocol to see if the route should be accepted and/or its attributes modified,
1525: * stores the temporary attributes back to the &rte.
1526: *
1527: * Now, having a "public" version of the route, we
1528: * automatically find any old route defined by the protocol @src
1529: * for network @n, replace it by the new one (or removing it if @new is %NULL),
1530: * recalculate the optimal route for this destination and finally broadcast
1531: * the change (if any) to all routing protocols by calling rte_announce().
1532: *
1533: * All memory used for attribute lists and other temporary allocations is taken
1534: * from a special linear pool @rte_update_pool and freed when rte_update()
1535: * finishes.
1536: */
1537:
1538: void
1539: rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src)
1540: {
1541: struct proto *p = c->proto;
1542: struct proto_stats *stats = &c->stats;
1543: const struct filter *filter = c->in_filter;
1544: rte *dummy = NULL;
1545: net *nn;
1546:
1547: ASSERT(c->channel_state == CS_UP);
1548:
1549: rte_update_lock();
1550: if (new)
1551: {
1552: /* Create a temporary table node */
1553: nn = alloca(sizeof(net) + n->length);
1554: memset(nn, 0, sizeof(net) + n->length);
1555: net_copy(nn->n.addr, n);
1556:
1557: new->net = nn;
1558: new->sender = c;
1559:
1560: if (!new->pref)
1561: new->pref = c->preference;
1562:
1563: stats->imp_updates_received++;
1564: if (!rte_validate(new))
1565: {
1566: rte_trace_in(D_FILTERS, p, new, "invalid");
1567: stats->imp_updates_invalid++;
1568: goto drop;
1569: }
1570:
1571: if (filter == FILTER_REJECT)
1572: {
1573: stats->imp_updates_filtered++;
1574: rte_trace_in(D_FILTERS, p, new, "filtered out");
1575:
1576: if (! c->in_keep_filtered)
1577: goto drop;
1578:
1579: /* new is a private copy, i could modify it */
1580: new->flags |= REF_FILTERED;
1581: }
1582: else if (filter)
1583: {
1584: rta *old_attrs = NULL;
1585: rte_make_tmp_attrs(&new, rte_update_pool, &old_attrs);
1586:
1587: int fr = f_run(filter, &new, rte_update_pool, 0);
1588: if (fr > F_ACCEPT)
1589: {
1590: stats->imp_updates_filtered++;
1591: rte_trace_in(D_FILTERS, p, new, "filtered out");
1592:
1593: if (! c->in_keep_filtered)
1594: {
1595: rta_free(old_attrs);
1596: goto drop;
1597: }
1598:
1599: new->flags |= REF_FILTERED;
1600: }
1601:
1602: rte_store_tmp_attrs(new, rte_update_pool, old_attrs);
1603: }
1604: if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
1605: new->attrs = rta_lookup(new->attrs);
1606: new->flags |= REF_COW;
1607:
1608: /* Use the actual struct network, not the dummy one */
1609: nn = net_get(c->table, n);
1610: new->net = nn;
1611: }
1612: else
1613: {
1614: stats->imp_withdraws_received++;
1615:
1616: if (!(nn = net_find(c->table, n)) || !src)
1617: {
1618: stats->imp_withdraws_ignored++;
1619: rte_update_unlock();
1620: return;
1621: }
1622: }
1623:
1624: recalc:
1625: /* And recalculate the best route */
1626: rte_hide_dummy_routes(nn, &dummy);
1627: rte_recalculate(c, nn, new, src);
1628: rte_unhide_dummy_routes(nn, &dummy);
1629:
1630: rte_update_unlock();
1631: return;
1632:
1633: drop:
1634: rte_free(new);
1635: new = NULL;
1636: if (nn = net_find(c->table, n))
1637: goto recalc;
1638:
1639: rte_update_unlock();
1640: }
1641:
1642: /* Independent call to rte_announce(), used from next hop
1643: recalculation, outside of rte_update(). new must be non-NULL */
1644: static inline void
1645: rte_announce_i(rtable *tab, unsigned type, net *net, rte *new, rte *old,
1646: rte *new_best, rte *old_best)
1647: {
1648: rte_update_lock();
1649: rte_announce(tab, type, net, new, old, new_best, old_best, NULL);
1650: rte_update_unlock();
1651: }
1652:
1653: static inline void
1654: rte_discard(rte *old) /* Non-filtered route deletion, used during garbage collection */
1655: {
1656: rte_update_lock();
1657: rte_recalculate(old->sender, old->net, NULL, old->attrs->src);
1658: rte_update_unlock();
1659: }
1660:
1661: /* Modify existing route by protocol hook, used for long-lived graceful restart */
1662: static inline void
1663: rte_modify(rte *old)
1664: {
1665: rte_update_lock();
1666:
1667: rte *new = old->sender->proto->rte_modify(old, rte_update_pool);
1668: if (new != old)
1669: {
1670: if (new)
1671: {
1672: if (!rta_is_cached(new->attrs))
1673: new->attrs = rta_lookup(new->attrs);
1674: new->flags = (old->flags & ~REF_MODIFY) | REF_COW;
1675: }
1676:
1677: rte_recalculate(old->sender, old->net, new, old->attrs->src);
1678: }
1679:
1680: rte_update_unlock();
1681: }
1682:
1683: /* Check rtable for best route to given net whether it would be exported do p */
1684: int
1685: rt_examine(rtable *t, net_addr *a, struct proto *p, const struct filter *filter)
1686: {
1687: net *n = net_find(t, a);
1688: rte *rt = n ? n->routes : NULL;
1689:
1690: if (!rte_is_valid(rt))
1691: return 0;
1692:
1693: rte_update_lock();
1694:
1695: /* Rest is stripped down export_filter() */
1696: int v = p->preexport ? p->preexport(p, &rt, rte_update_pool) : 0;
1697: if (v == RIC_PROCESS)
1698: {
1699: rte_make_tmp_attrs(&rt, rte_update_pool, NULL);
1700: v = (f_run(filter, &rt, rte_update_pool, FF_SILENT) <= F_ACCEPT);
1701: }
1702:
1703: /* Discard temporary rte */
1704: if (rt != n->routes)
1705: rte_free(rt);
1706:
1707: rte_update_unlock();
1708:
1709: return v > 0;
1710: }
1711:
1712:
1713: /**
1714: * rt_refresh_begin - start a refresh cycle
1715: * @t: related routing table
1716: * @c related channel
1717: *
1718: * This function starts a refresh cycle for given routing table and announce
1719: * hook. The refresh cycle is a sequence where the protocol sends all its valid
1720: * routes to the routing table (by rte_update()). After that, all protocol
1721: * routes (more precisely routes with @c as @sender) not sent during the
1722: * refresh cycle but still in the table from the past are pruned. This is
1723: * implemented by marking all related routes as stale by REF_STALE flag in
1724: * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1725: * flag in rt_refresh_end() and then removing such routes in the prune loop.
1726: */
1727: void
1728: rt_refresh_begin(rtable *t, struct channel *c)
1729: {
1730: FIB_WALK(&t->fib, net, n)
1731: {
1732: rte *e;
1733: for (e = n->routes; e; e = e->next)
1734: if (e->sender == c)
1735: e->flags |= REF_STALE;
1736: }
1737: FIB_WALK_END;
1738: }
1739:
1740: /**
1741: * rt_refresh_end - end a refresh cycle
1742: * @t: related routing table
1743: * @c: related channel
1744: *
1745: * This function ends a refresh cycle for given routing table and announce
1746: * hook. See rt_refresh_begin() for description of refresh cycles.
1747: */
1748: void
1749: rt_refresh_end(rtable *t, struct channel *c)
1750: {
1751: int prune = 0;
1752:
1753: FIB_WALK(&t->fib, net, n)
1754: {
1755: rte *e;
1756: for (e = n->routes; e; e = e->next)
1757: if ((e->sender == c) && (e->flags & REF_STALE))
1758: {
1759: e->flags |= REF_DISCARD;
1760: prune = 1;
1761: }
1762: }
1763: FIB_WALK_END;
1764:
1765: if (prune)
1766: rt_schedule_prune(t);
1767: }
1768:
1769: void
1770: rt_modify_stale(rtable *t, struct channel *c)
1771: {
1772: int prune = 0;
1773:
1774: FIB_WALK(&t->fib, net, n)
1775: {
1776: rte *e;
1777: for (e = n->routes; e; e = e->next)
1778: if ((e->sender == c) && (e->flags & REF_STALE) && !(e->flags & REF_FILTERED))
1779: {
1780: e->flags |= REF_MODIFY;
1781: prune = 1;
1782: }
1783: }
1784: FIB_WALK_END;
1785:
1786: if (prune)
1787: rt_schedule_prune(t);
1788: }
1789:
1790: /**
1791: * rte_dump - dump a route
1792: * @e: &rte to be dumped
1793: *
1794: * This functions dumps contents of a &rte to debug output.
1795: */
1796: void
1797: rte_dump(rte *e)
1798: {
1799: net *n = e->net;
1800: debug("%-1N ", n->n.addr);
1801: debug("KF=%02x PF=%02x pref=%d ", n->n.flags, e->pflags, e->pref);
1802: rta_dump(e->attrs);
1803: if (e->attrs->src->proto->proto->dump_attrs)
1804: e->attrs->src->proto->proto->dump_attrs(e);
1805: debug("\n");
1806: }
1807:
1808: /**
1809: * rt_dump - dump a routing table
1810: * @t: routing table to be dumped
1811: *
1812: * This function dumps contents of a given routing table to debug output.
1813: */
1814: void
1815: rt_dump(rtable *t)
1816: {
1817: debug("Dump of routing table <%s>\n", t->name);
1818: #ifdef DEBUGGING
1819: fib_check(&t->fib);
1820: #endif
1821: FIB_WALK(&t->fib, net, n)
1822: {
1823: rte *e;
1824: for(e=n->routes; e; e=e->next)
1825: rte_dump(e);
1826: }
1827: FIB_WALK_END;
1828: debug("\n");
1829: }
1830:
1831: /**
1832: * rt_dump_all - dump all routing tables
1833: *
1834: * This function dumps contents of all routing tables to debug output.
1835: */
1836: void
1837: rt_dump_all(void)
1838: {
1839: rtable *t;
1840:
1841: WALK_LIST(t, routing_tables)
1842: rt_dump(t);
1843: }
1844:
1845: static inline void
1846: rt_schedule_hcu(rtable *tab)
1847: {
1848: if (tab->hcu_scheduled)
1849: return;
1850:
1851: tab->hcu_scheduled = 1;
1852: ev_schedule(tab->rt_event);
1853: }
1854:
1855: static inline void
1856: rt_schedule_nhu(rtable *tab)
1857: {
1858: if (tab->nhu_state == NHU_CLEAN)
1859: ev_schedule(tab->rt_event);
1860:
1861: /* state change:
1862: * NHU_CLEAN -> NHU_SCHEDULED
1863: * NHU_RUNNING -> NHU_DIRTY
1864: */
1865: tab->nhu_state |= NHU_SCHEDULED;
1866: }
1867:
1868: void
1869: rt_schedule_prune(rtable *tab)
1870: {
1871: if (tab->prune_state == 0)
1872: ev_schedule(tab->rt_event);
1873:
1874: /* state change 0->1, 2->3 */
1875: tab->prune_state |= 1;
1876: }
1877:
1878:
1879: static void
1880: rt_event(void *ptr)
1881: {
1882: rtable *tab = ptr;
1883:
1884: rt_lock_table(tab);
1885:
1886: if (tab->hcu_scheduled)
1887: rt_update_hostcache(tab);
1888:
1889: if (tab->nhu_state)
1890: rt_next_hop_update(tab);
1891:
1892: if (tab->prune_state)
1893: rt_prune_table(tab);
1894:
1895: rt_unlock_table(tab);
1896: }
1897:
1898: void
1899: rt_setup(pool *p, rtable *t, struct rtable_config *cf)
1900: {
1901: bzero(t, sizeof(*t));
1902: t->name = cf->name;
1903: t->config = cf;
1904: t->addr_type = cf->addr_type;
1905: fib_init(&t->fib, p, t->addr_type, sizeof(net), OFFSETOF(net, n), 0, NULL);
1906: init_list(&t->channels);
1907:
1908: t->rt_event = ev_new_init(p, rt_event, t);
1909: t->gc_time = current_time();
1910: }
1911:
1912: /**
1913: * rt_init - initialize routing tables
1914: *
1915: * This function is called during BIRD startup. It initializes the
1916: * routing table module.
1917: */
1918: void
1919: rt_init(void)
1920: {
1921: rta_init();
1922: rt_table_pool = rp_new(&root_pool, "Routing tables");
1923: rte_update_pool = lp_new_default(rt_table_pool);
1924: rte_slab = sl_new(rt_table_pool, sizeof(rte));
1925: init_list(&routing_tables);
1926: }
1927:
1928:
1929: /**
1930: * rt_prune_table - prune a routing table
1931: *
1932: * The prune loop scans routing tables and removes routes belonging to flushing
1933: * protocols, discarded routes and also stale network entries. It is called from
1934: * rt_event(). The event is rescheduled if the current iteration do not finish
1935: * the table. The pruning is directed by the prune state (@prune_state),
1936: * specifying whether the prune cycle is scheduled or running, and there
1937: * is also a persistent pruning iterator (@prune_fit).
1938: *
1939: * The prune loop is used also for channel flushing. For this purpose, the
1940: * channels to flush are marked before the iteration and notified after the
1941: * iteration.
1942: */
1943: static void
1944: rt_prune_table(rtable *tab)
1945: {
1946: struct fib_iterator *fit = &tab->prune_fit;
1947: int limit = 512;
1948:
1949: struct channel *c;
1950: node *n, *x;
1951:
1952: DBG("Pruning route table %s\n", tab->name);
1953: #ifdef DEBUGGING
1954: fib_check(&tab->fib);
1955: #endif
1956:
1957: if (tab->prune_state == 0)
1958: return;
1959:
1960: if (tab->prune_state == 1)
1961: {
1962: /* Mark channels to flush */
1963: WALK_LIST2(c, n, tab->channels, table_node)
1964: if (c->channel_state == CS_FLUSHING)
1965: c->flush_active = 1;
1966:
1967: FIB_ITERATE_INIT(fit, &tab->fib);
1968: tab->prune_state = 2;
1969: }
1970:
1971: again:
1972: FIB_ITERATE_START(&tab->fib, fit, net, n)
1973: {
1974: rte *e;
1975:
1976: rescan:
1977: for (e=n->routes; e; e=e->next)
1978: {
1979: if (e->sender->flush_active || (e->flags & REF_DISCARD))
1980: {
1981: if (limit <= 0)
1982: {
1983: FIB_ITERATE_PUT(fit);
1984: ev_schedule(tab->rt_event);
1985: return;
1986: }
1987:
1988: rte_discard(e);
1989: limit--;
1990:
1991: goto rescan;
1992: }
1993:
1994: if (e->flags & REF_MODIFY)
1995: {
1996: if (limit <= 0)
1997: {
1998: FIB_ITERATE_PUT(fit);
1999: ev_schedule(tab->rt_event);
2000: return;
2001: }
2002:
2003: rte_modify(e);
2004: limit--;
2005:
2006: goto rescan;
2007: }
2008: }
2009:
2010: if (!n->routes) /* Orphaned FIB entry */
2011: {
2012: FIB_ITERATE_PUT(fit);
2013: fib_delete(&tab->fib, n);
2014: goto again;
2015: }
2016: }
2017: FIB_ITERATE_END;
2018:
2019: #ifdef DEBUGGING
2020: fib_check(&tab->fib);
2021: #endif
2022:
2023: tab->gc_counter = 0;
2024: tab->gc_time = current_time();
2025:
2026: /* state change 2->0, 3->1 */
2027: tab->prune_state &= 1;
2028:
2029: if (tab->prune_state > 0)
2030: ev_schedule(tab->rt_event);
2031:
2032: /* FIXME: This should be handled in a better way */
2033: rt_prune_sources();
2034:
2035: /* Close flushed channels */
2036: WALK_LIST2_DELSAFE(c, n, x, tab->channels, table_node)
2037: if (c->flush_active)
2038: {
2039: c->flush_active = 0;
2040: channel_set_state(c, CS_DOWN);
2041: }
2042:
2043: return;
2044: }
2045:
2046: void
2047: rt_preconfig(struct config *c)
2048: {
2049: init_list(&c->tables);
2050:
2051: rt_new_table(cf_get_symbol("master4"), NET_IP4);
2052: rt_new_table(cf_get_symbol("master6"), NET_IP6);
2053: }
2054:
2055:
2056: /*
2057: * Some functions for handing internal next hop updates
2058: * triggered by rt_schedule_nhu().
2059: */
2060:
2061: static inline int
2062: rta_next_hop_outdated(rta *a)
2063: {
2064: struct hostentry *he = a->hostentry;
2065:
2066: if (!he)
2067: return 0;
2068:
2069: if (!he->src)
2070: return a->dest != RTD_UNREACHABLE;
2071:
2072: return (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
2073: (!he->nexthop_linkable) || !nexthop_same(&(a->nh), &(he->src->nh));
2074: }
2075:
2076: void
2077: rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls)
2078: {
2079: a->hostentry = he;
2080: a->dest = he->dest;
2081: a->igp_metric = he->igp_metric;
2082:
2083: if (a->dest != RTD_UNICAST)
2084: {
2085: /* No nexthop */
2086: no_nexthop:
2087: a->nh = (struct nexthop) {};
2088: if (mls)
2089: { /* Store the label stack for later changes */
2090: a->nh.labels_orig = a->nh.labels = mls->len;
2091: memcpy(a->nh.label, mls->stack, mls->len * sizeof(u32));
2092: }
2093: return;
2094: }
2095:
2096: if (((!mls) || (!mls->len)) && he->nexthop_linkable)
2097: { /* Just link the nexthop chain, no label append happens. */
2098: memcpy(&(a->nh), &(he->src->nh), nexthop_size(&(he->src->nh)));
2099: return;
2100: }
2101:
2102: struct nexthop *nhp = NULL, *nhr = NULL;
2103: int skip_nexthop = 0;
2104:
2105: for (struct nexthop *nh = &(he->src->nh); nh; nh = nh->next)
2106: {
2107: if (skip_nexthop)
2108: skip_nexthop--;
2109: else
2110: {
2111: nhr = nhp;
2112: nhp = (nhp ? (nhp->next = lp_alloc(rte_update_pool, NEXTHOP_MAX_SIZE)) : &(a->nh));
2113: }
2114:
2115: memset(nhp, 0, NEXTHOP_MAX_SIZE);
2116: nhp->iface = nh->iface;
2117: nhp->weight = nh->weight;
2118:
2119: if (mls)
2120: {
2121: nhp->labels = nh->labels + mls->len;
2122: nhp->labels_orig = mls->len;
2123: if (nhp->labels <= MPLS_MAX_LABEL_STACK)
2124: {
2125: memcpy(nhp->label, nh->label, nh->labels * sizeof(u32)); /* First the hostentry labels */
2126: memcpy(&(nhp->label[nh->labels]), mls->stack, mls->len * sizeof(u32)); /* Then the bottom labels */
2127: }
2128: else
2129: {
2130: log(L_WARN "Sum of label stack sizes %d + %d = %d exceedes allowed maximum (%d)",
2131: nh->labels, mls->len, nhp->labels, MPLS_MAX_LABEL_STACK);
2132: skip_nexthop++;
2133: continue;
2134: }
2135: }
2136: else if (nh->labels)
2137: {
2138: nhp->labels = nh->labels;
2139: nhp->labels_orig = 0;
2140: memcpy(nhp->label, nh->label, nh->labels * sizeof(u32));
2141: }
2142:
2143: if (ipa_nonzero(nh->gw))
2144: {
2145: nhp->gw = nh->gw; /* Router nexthop */
2146: nhp->flags |= (nh->flags & RNF_ONLINK);
2147: }
2148: else if (!(nh->iface->flags & IF_MULTIACCESS) || (nh->iface->flags & IF_LOOPBACK))
2149: nhp->gw = IPA_NONE; /* PtP link - no need for nexthop */
2150: else if (ipa_nonzero(he->link))
2151: nhp->gw = he->link; /* Device nexthop with link-local address known */
2152: else
2153: nhp->gw = he->addr; /* Device nexthop with link-local address unknown */
2154: }
2155:
2156: if (skip_nexthop)
2157: if (nhr)
2158: nhr->next = NULL;
2159: else
2160: {
2161: a->dest = RTD_UNREACHABLE;
2162: log(L_WARN "No valid nexthop remaining, setting route unreachable");
2163: goto no_nexthop;
2164: }
2165: }
2166:
2167: static inline rte *
2168: rt_next_hop_update_rte(rtable *tab UNUSED, rte *old)
2169: {
2170: rta *a = alloca(RTA_MAX_SIZE);
2171: memcpy(a, old->attrs, rta_size(old->attrs));
2172:
2173: mpls_label_stack mls = { .len = a->nh.labels_orig };
2174: memcpy(mls.stack, &a->nh.label[a->nh.labels - mls.len], mls.len * sizeof(u32));
2175:
2176: rta_apply_hostentry(a, old->attrs->hostentry, &mls);
2177: a->aflags = 0;
2178:
2179: rte *e = sl_alloc(rte_slab);
2180: memcpy(e, old, sizeof(rte));
2181: e->attrs = rta_lookup(a);
2182:
2183: return e;
2184: }
2185:
2186: static inline int
2187: rt_next_hop_update_net(rtable *tab, net *n)
2188: {
2189: rte **k, *e, *new, *old_best, **new_best;
2190: int count = 0;
2191: int free_old_best = 0;
2192:
2193: old_best = n->routes;
2194: if (!old_best)
2195: return 0;
2196:
2197: for (k = &n->routes; e = *k; k = &e->next)
2198: if (rta_next_hop_outdated(e->attrs))
2199: {
2200: new = rt_next_hop_update_rte(tab, e);
2201: *k = new;
2202:
2203: rte_announce_i(tab, RA_ANY, n, new, e, NULL, NULL);
2204: rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
2205:
2206: /* Call a pre-comparison hook */
2207: /* Not really an efficient way to compute this */
2208: if (e->attrs->src->proto->rte_recalculate)
2209: e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
2210:
2211: if (e != old_best)
2212: rte_free_quick(e);
2213: else /* Freeing of the old best rte is postponed */
2214: free_old_best = 1;
2215:
2216: e = new;
2217: count++;
2218: }
2219:
2220: if (!count)
2221: return 0;
2222:
2223: /* Find the new best route */
2224: new_best = NULL;
2225: for (k = &n->routes; e = *k; k = &e->next)
2226: {
2227: if (!new_best || rte_better(e, *new_best))
2228: new_best = k;
2229: }
2230:
2231: /* Relink the new best route to the first position */
2232: new = *new_best;
2233: if (new != n->routes)
2234: {
2235: *new_best = new->next;
2236: new->next = n->routes;
2237: n->routes = new;
2238: }
2239:
2240: /* Announce the new best route */
2241: if (new != old_best)
2242: {
2243: rte_announce_i(tab, RA_OPTIMAL, n, new, old_best, NULL, NULL);
2244: rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
2245: }
2246:
2247: /* FIXME: Better announcement of merged routes */
2248: rte_announce_i(tab, RA_MERGED, n, new, old_best, new, old_best);
2249:
2250: if (free_old_best)
2251: rte_free_quick(old_best);
2252:
2253: return count;
2254: }
2255:
2256: static void
2257: rt_next_hop_update(rtable *tab)
2258: {
2259: struct fib_iterator *fit = &tab->nhu_fit;
2260: int max_feed = 32;
2261:
2262: if (tab->nhu_state == NHU_CLEAN)
2263: return;
2264:
2265: if (tab->nhu_state == NHU_SCHEDULED)
2266: {
2267: FIB_ITERATE_INIT(fit, &tab->fib);
2268: tab->nhu_state = NHU_RUNNING;
2269: }
2270:
2271: FIB_ITERATE_START(&tab->fib, fit, net, n)
2272: {
2273: if (max_feed <= 0)
2274: {
2275: FIB_ITERATE_PUT(fit);
2276: ev_schedule(tab->rt_event);
2277: return;
2278: }
2279: max_feed -= rt_next_hop_update_net(tab, n);
2280: }
2281: FIB_ITERATE_END;
2282:
2283: /* State change:
2284: * NHU_DIRTY -> NHU_SCHEDULED
2285: * NHU_RUNNING -> NHU_CLEAN
2286: */
2287: tab->nhu_state &= 1;
2288:
2289: if (tab->nhu_state != NHU_CLEAN)
2290: ev_schedule(tab->rt_event);
2291: }
2292:
2293:
2294: struct rtable_config *
2295: rt_new_table(struct symbol *s, uint addr_type)
2296: {
2297: /* Hack that allows to 'redefine' the master table */
2298: if ((s->class == SYM_TABLE) &&
2299: (s->table == new_config->def_tables[addr_type]) &&
2300: ((addr_type == NET_IP4) || (addr_type == NET_IP6)))
2301: return s->table;
2302:
2303: struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
2304:
2305: cf_define_symbol(s, SYM_TABLE, table, c);
2306: c->name = s->name;
2307: c->addr_type = addr_type;
2308: c->gc_max_ops = 1000;
2309: c->gc_min_time = 5;
2310:
2311: add_tail(&new_config->tables, &c->n);
2312:
2313: /* First table of each type is kept as default */
2314: if (! new_config->def_tables[addr_type])
2315: new_config->def_tables[addr_type] = c;
2316:
2317: return c;
2318: }
2319:
2320: /**
2321: * rt_lock_table - lock a routing table
2322: * @r: routing table to be locked
2323: *
2324: * Lock a routing table, because it's in use by a protocol,
2325: * preventing it from being freed when it gets undefined in a new
2326: * configuration.
2327: */
2328: void
2329: rt_lock_table(rtable *r)
2330: {
2331: r->use_count++;
2332: }
2333:
2334: /**
2335: * rt_unlock_table - unlock a routing table
2336: * @r: routing table to be unlocked
2337: *
2338: * Unlock a routing table formerly locked by rt_lock_table(),
2339: * that is decrease its use count and delete it if it's scheduled
2340: * for deletion by configuration changes.
2341: */
2342: void
2343: rt_unlock_table(rtable *r)
2344: {
2345: if (!--r->use_count && r->deleted)
2346: {
2347: struct config *conf = r->deleted;
2348: DBG("Deleting routing table %s\n", r->name);
2349: r->config->table = NULL;
2350: if (r->hostcache)
2351: rt_free_hostcache(r);
2352: rem_node(&r->n);
2353: fib_free(&r->fib);
2354: rfree(r->rt_event);
2355: mb_free(r);
2356: config_del_obstacle(conf);
2357: }
2358: }
2359:
2360: static struct rtable_config *
2361: rt_find_table_config(struct config *cf, char *name)
2362: {
2363: struct symbol *sym = cf_find_symbol(cf, name);
2364: return (sym && (sym->class == SYM_TABLE)) ? sym->table : NULL;
2365: }
2366:
2367: /**
2368: * rt_commit - commit new routing table configuration
2369: * @new: new configuration
2370: * @old: original configuration or %NULL if it's boot time config
2371: *
2372: * Scan differences between @old and @new configuration and modify
2373: * the routing tables according to these changes. If @new defines a
2374: * previously unknown table, create it, if it omits a table existing
2375: * in @old, schedule it for deletion (it gets deleted when all protocols
2376: * disconnect from it by calling rt_unlock_table()), if it exists
2377: * in both configurations, leave it unchanged.
2378: */
2379: void
2380: rt_commit(struct config *new, struct config *old)
2381: {
2382: struct rtable_config *o, *r;
2383:
2384: DBG("rt_commit:\n");
2385: if (old)
2386: {
2387: WALK_LIST(o, old->tables)
2388: {
2389: rtable *ot = o->table;
2390: if (!ot->deleted)
2391: {
2392: r = rt_find_table_config(new, o->name);
2393: if (r && (r->addr_type == o->addr_type) && !new->shutdown)
2394: {
2395: DBG("\t%s: same\n", o->name);
2396: r->table = ot;
2397: ot->name = r->name;
2398: ot->config = r;
2399: if (o->sorted != r->sorted)
2400: log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
2401: }
2402: else
2403: {
2404: DBG("\t%s: deleted\n", o->name);
2405: ot->deleted = old;
2406: config_add_obstacle(old);
2407: rt_lock_table(ot);
2408: rt_unlock_table(ot);
2409: }
2410: }
2411: }
2412: }
2413:
2414: WALK_LIST(r, new->tables)
2415: if (!r->table)
2416: {
2417: rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
2418: DBG("\t%s: created\n", r->name);
2419: rt_setup(rt_table_pool, t, r);
2420: add_tail(&routing_tables, &t->n);
2421: r->table = t;
2422: }
2423: DBG("\tdone\n");
2424: }
2425:
2426: static inline void
2427: do_feed_channel(struct channel *c, net *n, rte *e)
2428: {
2429: rte_update_lock();
2430: if (c->ra_mode == RA_ACCEPTED)
2431: rt_notify_accepted(c, n, e, NULL, NULL, c->refeeding ? 2 : 1);
2432: else if (c->ra_mode == RA_MERGED)
2433: rt_notify_merged(c, n, NULL, NULL, e, c->refeeding ? e : NULL, c->refeeding);
2434: else /* RA_BASIC */
2435: rt_notify_basic(c, n, e, c->refeeding ? e : NULL, c->refeeding);
2436: rte_update_unlock();
2437: }
2438:
2439: /**
2440: * rt_feed_channel - advertise all routes to a channel
2441: * @c: channel to be fed
2442: *
2443: * This function performs one pass of advertisement of routes to a channel that
2444: * is in the ES_FEEDING state. It is called by the protocol code as long as it
2445: * has something to do. (We avoid transferring all the routes in single pass in
2446: * order not to monopolize CPU time.)
2447: */
2448: int
2449: rt_feed_channel(struct channel *c)
2450: {
2451: struct fib_iterator *fit = &c->feed_fit;
2452: int max_feed = 256;
2453:
2454: ASSERT(c->export_state == ES_FEEDING);
2455:
2456: if (!c->feed_active)
2457: {
2458: FIB_ITERATE_INIT(fit, &c->table->fib);
2459: c->feed_active = 1;
2460: }
2461:
2462: FIB_ITERATE_START(&c->table->fib, fit, net, n)
2463: {
2464: rte *e = n->routes;
2465: if (max_feed <= 0)
2466: {
2467: FIB_ITERATE_PUT(fit);
2468: return 0;
2469: }
2470:
2471: /* FIXME: perhaps we should change feed for RA_ACCEPTED to not use 'new' */
2472:
2473: if ((c->ra_mode == RA_OPTIMAL) ||
2474: (c->ra_mode == RA_ACCEPTED) ||
2475: (c->ra_mode == RA_MERGED))
2476: if (rte_is_valid(e))
2477: {
2478: /* In the meantime, the protocol may fell down */
2479: if (c->export_state != ES_FEEDING)
2480: goto done;
2481:
2482: do_feed_channel(c, n, e);
2483: max_feed--;
2484: }
2485:
2486: if (c->ra_mode == RA_ANY)
2487: for(e = n->routes; e; e = e->next)
2488: {
2489: /* In the meantime, the protocol may fell down */
2490: if (c->export_state != ES_FEEDING)
2491: goto done;
2492:
2493: if (!rte_is_valid(e))
2494: continue;
2495:
2496: do_feed_channel(c, n, e);
2497: max_feed--;
2498: }
2499: }
2500: FIB_ITERATE_END;
2501:
2502: done:
2503: c->feed_active = 0;
2504: return 1;
2505: }
2506:
2507: /**
2508: * rt_feed_baby_abort - abort protocol feeding
2509: * @c: channel
2510: *
2511: * This function is called by the protocol code when the protocol stops or
2512: * ceases to exist during the feeding.
2513: */
2514: void
2515: rt_feed_channel_abort(struct channel *c)
2516: {
2517: if (c->feed_active)
2518: {
2519: /* Unlink the iterator */
2520: fit_get(&c->table->fib, &c->feed_fit);
2521: c->feed_active = 0;
2522: }
2523: }
2524:
2525:
2526: /*
2527: * Import table
2528: */
2529:
2530: int
2531: rte_update_in(struct channel *c, const net_addr *n, rte *new, struct rte_src *src)
2532: {
2533: struct rtable *tab = c->in_table;
2534: rte *old, **pos;
2535: net *net;
2536:
2537: if (new)
2538: {
2539: net = net_get(tab, n);
2540:
2541: if (!new->pref)
2542: new->pref = c->preference;
2543:
2544: if (!rta_is_cached(new->attrs))
2545: new->attrs = rta_lookup(new->attrs);
2546: }
2547: else
2548: {
2549: net = net_find(tab, n);
2550:
2551: if (!net)
2552: goto drop_withdraw;
2553: }
2554:
2555: /* Find the old rte */
2556: for (pos = &net->routes; old = *pos; pos = &old->next)
2557: if (old->attrs->src == src)
2558: {
2559: if (new && rte_same(old, new))
2560: {
2561: /* Refresh the old rte, continue with update to main rtable */
2562: if (old->flags & (REF_STALE | REF_DISCARD | REF_MODIFY))
2563: {
2564: old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY);
2565: return 1;
2566: }
2567:
2568: goto drop_update;
2569: }
2570:
2571: /* Move iterator if needed */
2572: if (old == c->reload_next_rte)
2573: c->reload_next_rte = old->next;
2574:
2575: /* Remove the old rte */
2576: *pos = old->next;
2577: rte_free_quick(old);
2578: tab->rt_count--;
2579:
2580: break;
2581: }
2582:
2583: if (!new)
2584: {
2585: if (!old)
2586: goto drop_withdraw;
2587:
2588: return 1;
2589: }
2590:
2591: struct channel_limit *l = &c->rx_limit;
2592: if (l->action && !old)
2593: {
2594: if (tab->rt_count >= l->limit)
2595: channel_notify_limit(c, l, PLD_RX, tab->rt_count);
2596:
2597: if (l->state == PLS_BLOCKED)
2598: {
2599: rte_trace_in(D_FILTERS, c->proto, new, "ignored [limit]");
2600: goto drop_update;
2601: }
2602: }
2603:
2604: /* Insert the new rte */
2605: rte *e = rte_do_cow(new);
2606: e->flags |= REF_COW;
2607: e->net = net;
2608: e->sender = c;
2609: e->lastmod = current_time();
2610: e->next = *pos;
2611: *pos = e;
2612: tab->rt_count++;
2613: return 1;
2614:
2615: drop_update:
2616: c->stats.imp_updates_received++;
2617: c->stats.imp_updates_ignored++;
2618: rte_free(new);
2619: return 0;
2620:
2621: drop_withdraw:
2622: c->stats.imp_withdraws_received++;
2623: c->stats.imp_withdraws_ignored++;
2624: return 0;
2625: }
2626:
2627: int
2628: rt_reload_channel(struct channel *c)
2629: {
2630: struct rtable *tab = c->in_table;
2631: struct fib_iterator *fit = &c->reload_fit;
2632: int max_feed = 64;
2633:
2634: ASSERT(c->channel_state == CS_UP);
2635:
2636: if (!c->reload_active)
2637: {
2638: FIB_ITERATE_INIT(fit, &tab->fib);
2639: c->reload_active = 1;
2640: }
2641:
2642: do {
2643: for (rte *e = c->reload_next_rte; e; e = e->next)
2644: {
2645: if (max_feed-- <= 0)
2646: {
2647: c->reload_next_rte = e;
2648: debug("%s channel reload burst split (max_feed=%d)", c->proto->name, max_feed);
2649: return 0;
2650: }
2651:
2652: rte_update2(c, e->net->n.addr, rte_do_cow(e), e->attrs->src);
2653: }
2654:
2655: c->reload_next_rte = NULL;
2656:
2657: FIB_ITERATE_START(&tab->fib, fit, net, n)
2658: {
2659: if (c->reload_next_rte = n->routes)
2660: {
2661: FIB_ITERATE_PUT_NEXT(fit, &tab->fib);
2662: break;
2663: }
2664: }
2665: FIB_ITERATE_END;
2666: }
2667: while (c->reload_next_rte);
2668:
2669: c->reload_active = 0;
2670: return 1;
2671: }
2672:
2673: void
2674: rt_reload_channel_abort(struct channel *c)
2675: {
2676: if (c->reload_active)
2677: {
2678: /* Unlink the iterator */
2679: fit_get(&c->in_table->fib, &c->reload_fit);
2680: c->reload_next_rte = NULL;
2681: c->reload_active = 0;
2682: }
2683: }
2684:
2685: void
2686: rt_prune_sync(rtable *t, int all)
2687: {
2688: FIB_WALK(&t->fib, net, n)
2689: {
2690: rte *e, **ee = &n->routes;
2691: while (e = *ee)
2692: {
2693: if (all || (e->flags & (REF_STALE | REF_DISCARD)))
2694: {
2695: *ee = e->next;
2696: rte_free_quick(e);
2697: t->rt_count--;
2698: }
2699: else
2700: ee = &e->next;
2701: }
2702: }
2703: FIB_WALK_END;
2704: }
2705:
2706:
2707: /*
2708: * Export table
2709: */
2710:
2711: int
2712: rte_update_out(struct channel *c, const net_addr *n, rte *new, rte *old0, int refeed)
2713: {
2714: struct rtable *tab = c->out_table;
2715: struct rte_src *src;
2716: rte *old, **pos;
2717: net *net;
2718:
2719: if (new)
2720: {
2721: net = net_get(tab, n);
2722: src = new->attrs->src;
2723:
2724: rte_store_tmp_attrs(new, rte_update_pool, NULL);
2725:
2726: if (!rta_is_cached(new->attrs))
2727: new->attrs = rta_lookup(new->attrs);
2728: }
2729: else
2730: {
2731: net = net_find(tab, n);
2732: src = old0->attrs->src;
2733:
2734: if (!net)
2735: goto drop_withdraw;
2736: }
2737:
2738: /* Find the old rte */
2739: for (pos = &net->routes; old = *pos; pos = &old->next)
2740: if (old->attrs->src == src)
2741: {
2742: if (new && rte_same(old, new))
2743: {
2744: /* REF_STALE / REF_DISCARD not used in export table */
2745: /*
2746: if (old->flags & (REF_STALE | REF_DISCARD | REF_MODIFY))
2747: {
2748: old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY);
2749: return 1;
2750: }
2751: */
2752:
2753: goto drop_update;
2754: }
2755:
2756: /* Remove the old rte */
2757: *pos = old->next;
2758: rte_free_quick(old);
2759: tab->rt_count--;
2760:
2761: break;
2762: }
2763:
2764: if (!new)
2765: {
2766: if (!old)
2767: goto drop_withdraw;
2768:
2769: return 1;
2770: }
2771:
2772: /* Insert the new rte */
2773: rte *e = rte_do_cow(new);
2774: e->flags |= REF_COW;
2775: e->net = net;
2776: e->sender = c;
2777: e->lastmod = current_time();
2778: e->next = *pos;
2779: *pos = e;
2780: tab->rt_count++;
2781: return 1;
2782:
2783: drop_update:
2784: return refeed;
2785:
2786: drop_withdraw:
2787: return 0;
2788: }
2789:
2790:
2791: /*
2792: * Hostcache
2793: */
2794:
2795: static inline u32
2796: hc_hash(ip_addr a, rtable *dep)
2797: {
2798: return ipa_hash(a) ^ ptr_hash(dep);
2799: }
2800:
2801: static inline void
2802: hc_insert(struct hostcache *hc, struct hostentry *he)
2803: {
2804: uint k = he->hash_key >> hc->hash_shift;
2805: he->next = hc->hash_table[k];
2806: hc->hash_table[k] = he;
2807: }
2808:
2809: static inline void
2810: hc_remove(struct hostcache *hc, struct hostentry *he)
2811: {
2812: struct hostentry **hep;
2813: uint k = he->hash_key >> hc->hash_shift;
2814:
2815: for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
2816: *hep = he->next;
2817: }
2818:
2819: #define HC_DEF_ORDER 10
2820: #define HC_HI_MARK *4
2821: #define HC_HI_STEP 2
2822: #define HC_HI_ORDER 16 /* Must be at most 16 */
2823: #define HC_LO_MARK /5
2824: #define HC_LO_STEP 2
2825: #define HC_LO_ORDER 10
2826:
2827: static void
2828: hc_alloc_table(struct hostcache *hc, unsigned order)
2829: {
2830: uint hsize = 1 << order;
2831: hc->hash_order = order;
2832: hc->hash_shift = 32 - order;
2833: hc->hash_max = (order >= HC_HI_ORDER) ? ~0U : (hsize HC_HI_MARK);
2834: hc->hash_min = (order <= HC_LO_ORDER) ? 0U : (hsize HC_LO_MARK);
2835:
2836: hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
2837: }
2838:
2839: static void
2840: hc_resize(struct hostcache *hc, unsigned new_order)
2841: {
2842: struct hostentry **old_table = hc->hash_table;
2843: struct hostentry *he, *hen;
2844: uint old_size = 1 << hc->hash_order;
2845: uint i;
2846:
2847: hc_alloc_table(hc, new_order);
2848: for (i = 0; i < old_size; i++)
2849: for (he = old_table[i]; he != NULL; he=hen)
2850: {
2851: hen = he->next;
2852: hc_insert(hc, he);
2853: }
2854: mb_free(old_table);
2855: }
2856:
2857: static struct hostentry *
2858: hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k)
2859: {
2860: struct hostentry *he = sl_alloc(hc->slab);
2861:
2862: *he = (struct hostentry) {
2863: .addr = a,
2864: .link = ll,
2865: .tab = dep,
2866: .hash_key = k,
2867: };
2868:
2869: add_tail(&hc->hostentries, &he->ln);
2870: hc_insert(hc, he);
2871:
2872: hc->hash_items++;
2873: if (hc->hash_items > hc->hash_max)
2874: hc_resize(hc, hc->hash_order + HC_HI_STEP);
2875:
2876: return he;
2877: }
2878:
2879: static void
2880: hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
2881: {
2882: rta_free(he->src);
2883:
2884: rem_node(&he->ln);
2885: hc_remove(hc, he);
2886: sl_free(hc->slab, he);
2887:
2888: hc->hash_items--;
2889: if (hc->hash_items < hc->hash_min)
2890: hc_resize(hc, hc->hash_order - HC_LO_STEP);
2891: }
2892:
2893: static void
2894: rt_init_hostcache(rtable *tab)
2895: {
2896: struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
2897: init_list(&hc->hostentries);
2898:
2899: hc->hash_items = 0;
2900: hc_alloc_table(hc, HC_DEF_ORDER);
2901: hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
2902:
2903: hc->lp = lp_new(rt_table_pool, LP_GOOD_SIZE(1024));
2904: hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2905:
2906: tab->hostcache = hc;
2907: }
2908:
2909: static void
2910: rt_free_hostcache(rtable *tab)
2911: {
2912: struct hostcache *hc = tab->hostcache;
2913:
2914: node *n;
2915: WALK_LIST(n, hc->hostentries)
2916: {
2917: struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
2918: rta_free(he->src);
2919:
2920: if (he->uc)
2921: log(L_ERR "Hostcache is not empty in table %s", tab->name);
2922: }
2923:
2924: rfree(hc->slab);
2925: rfree(hc->lp);
2926: mb_free(hc->hash_table);
2927: mb_free(hc);
2928: }
2929:
2930: static void
2931: rt_notify_hostcache(rtable *tab, net *net)
2932: {
2933: if (tab->hcu_scheduled)
2934: return;
2935:
2936: if (trie_match_net(tab->hostcache->trie, net->n.addr))
2937: rt_schedule_hcu(tab);
2938: }
2939:
2940: static int
2941: if_local_addr(ip_addr a, struct iface *i)
2942: {
2943: struct ifa *b;
2944:
2945: WALK_LIST(b, i->addrs)
2946: if (ipa_equal(a, b->ip))
2947: return 1;
2948:
2949: return 0;
2950: }
2951:
2952: u32
2953: rt_get_igp_metric(rte *rt)
2954: {
2955: eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
2956:
2957: if (ea)
2958: return ea->u.data;
2959:
2960: rta *a = rt->attrs;
2961:
2962: #ifdef CONFIG_OSPF
2963: if ((a->source == RTS_OSPF) ||
2964: (a->source == RTS_OSPF_IA) ||
2965: (a->source == RTS_OSPF_EXT1))
2966: return rt->u.ospf.metric1;
2967: #endif
2968:
2969: #ifdef CONFIG_RIP
2970: if (a->source == RTS_RIP)
2971: return rt->u.rip.metric;
2972: #endif
2973:
2974: #ifdef CONFIG_BGP
2975: if (a->source == RTS_BGP)
2976: {
2977: u64 metric = bgp_total_aigp_metric(rt);
2978: return (u32) MIN(metric, (u64) IGP_METRIC_UNKNOWN);
2979: }
2980: #endif
2981:
2982: if (a->source == RTS_DEVICE)
2983: return 0;
2984:
2985: return IGP_METRIC_UNKNOWN;
2986: }
2987:
2988: static int
2989: rt_update_hostentry(rtable *tab, struct hostentry *he)
2990: {
2991: rta *old_src = he->src;
2992: int direct = 0;
2993: int pxlen = 0;
2994:
2995: /* Reset the hostentry */
2996: he->src = NULL;
2997: he->dest = RTD_UNREACHABLE;
2998: he->nexthop_linkable = 0;
2999: he->igp_metric = 0;
3000:
3001: net_addr he_addr;
3002: net_fill_ip_host(&he_addr, he->addr);
3003: net *n = net_route(tab, &he_addr);
3004: if (n)
3005: {
3006: rte *e = n->routes;
3007: rta *a = e->attrs;
3008: pxlen = n->n.addr->pxlen;
3009:
3010: if (a->hostentry)
3011: {
3012: /* Recursive route should not depend on another recursive route */
3013: log(L_WARN "Next hop address %I resolvable through recursive route for %N",
3014: he->addr, n->n.addr);
3015: goto done;
3016: }
3017:
3018: if (a->dest == RTD_UNICAST)
3019: {
3020: for (struct nexthop *nh = &(a->nh); nh; nh = nh->next)
3021: if (ipa_zero(nh->gw))
3022: {
3023: if (if_local_addr(he->addr, nh->iface))
3024: {
3025: /* The host address is a local address, this is not valid */
3026: log(L_WARN "Next hop address %I is a local address of iface %s",
3027: he->addr, nh->iface->name);
3028: goto done;
3029: }
3030:
3031: direct++;
3032: }
3033: }
3034:
3035: he->src = rta_clone(a);
3036: he->dest = a->dest;
3037: he->nexthop_linkable = !direct;
3038: he->igp_metric = rt_get_igp_metric(e);
3039: }
3040:
3041: done:
3042: /* Add a prefix range to the trie */
3043: trie_add_prefix(tab->hostcache->trie, &he_addr, pxlen, he_addr.pxlen);
3044:
3045: rta_free(old_src);
3046: return old_src != he->src;
3047: }
3048:
3049: static void
3050: rt_update_hostcache(rtable *tab)
3051: {
3052: struct hostcache *hc = tab->hostcache;
3053: struct hostentry *he;
3054: node *n, *x;
3055:
3056: /* Reset the trie */
3057: lp_flush(hc->lp);
3058: hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
3059:
3060: WALK_LIST_DELSAFE(n, x, hc->hostentries)
3061: {
3062: he = SKIP_BACK(struct hostentry, ln, n);
3063: if (!he->uc)
3064: {
3065: hc_delete_hostentry(hc, he);
3066: continue;
3067: }
3068:
3069: if (rt_update_hostentry(tab, he))
3070: rt_schedule_nhu(he->tab);
3071: }
3072:
3073: tab->hcu_scheduled = 0;
3074: }
3075:
3076: struct hostentry *
3077: rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
3078: {
3079: struct hostentry *he;
3080:
3081: if (!tab->hostcache)
3082: rt_init_hostcache(tab);
3083:
3084: u32 k = hc_hash(a, dep);
3085: struct hostcache *hc = tab->hostcache;
3086: for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
3087: if (ipa_equal(he->addr, a) && (he->tab == dep))
3088: return he;
3089:
3090: he = hc_new_hostentry(hc, a, ipa_zero(ll) ? a : ll, dep, k);
3091: rt_update_hostentry(tab, he);
3092: return he;
3093: }
3094:
3095:
3096: /*
3097: * Documentation for functions declared inline in route.h
3098: */
3099: #if 0
3100:
3101: /**
3102: * net_find - find a network entry
3103: * @tab: a routing table
3104: * @addr: address of the network
3105: *
3106: * net_find() looks up the given network in routing table @tab and
3107: * returns a pointer to its &net entry or %NULL if no such network
3108: * exists.
3109: */
3110: static inline net *net_find(rtable *tab, net_addr *addr)
3111: { DUMMY; }
3112:
3113: /**
3114: * net_get - obtain a network entry
3115: * @tab: a routing table
3116: * @addr: address of the network
3117: *
3118: * net_get() looks up the given network in routing table @tab and
3119: * returns a pointer to its &net entry. If no such entry exists, it's
3120: * created.
3121: */
3122: static inline net *net_get(rtable *tab, net_addr *addr)
3123: { DUMMY; }
3124:
3125: /**
3126: * rte_cow - copy a route for writing
3127: * @r: a route entry to be copied
3128: *
3129: * rte_cow() takes a &rte and prepares it for modification. The exact action
3130: * taken depends on the flags of the &rte -- if it's a temporary entry, it's
3131: * just returned unchanged, else a new temporary entry with the same contents
3132: * is created.
3133: *
3134: * The primary use of this function is inside the filter machinery -- when
3135: * a filter wants to modify &rte contents (to change the preference or to
3136: * attach another set of attributes), it must ensure that the &rte is not
3137: * shared with anyone else (and especially that it isn't stored in any routing
3138: * table).
3139: *
3140: * Result: a pointer to the new writable &rte.
3141: */
3142: static inline rte * rte_cow(rte *r)
3143: { DUMMY; }
3144:
3145: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rt-table.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / nest