Annotation of embedaddon/bird2/nest/rt-table.c, revision 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