Annotation of embedaddon/bird2/proto/ospf/rt.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD -- OSPF
! 3: *
! 4: * (c) 2000--2004 Ondrej Filip <feela@network.cz>
! 5: * (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
! 6: * (c) 2009--2014 CZ.NIC z.s.p.o.
! 7: *
! 8: * Can be freely distributed and used under the terms of the GNU GPL.
! 9: */
! 10:
! 11: #include "ospf.h"
! 12:
! 13: static void add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par, u32 dist, int i, uint data, uint lif, uint nif);
! 14: static void rt_sync(struct ospf_proto *p);
! 15:
! 16:
! 17: static inline void reset_ri(ort *ort)
! 18: {
! 19: bzero(&ort->n, sizeof(orta));
! 20: }
! 21:
! 22: static inline int
! 23: nh_is_vlink(struct nexthop *nhs)
! 24: {
! 25: return !nhs->iface;
! 26: }
! 27:
! 28: static inline int
! 29: unresolved_vlink(ort *ort)
! 30: {
! 31: return ort->n.nhs && nh_is_vlink(ort->n.nhs);
! 32: }
! 33:
! 34: static inline struct nexthop *
! 35: new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
! 36: {
! 37: struct nexthop *nh = lp_allocz(p->nhpool, sizeof(struct nexthop));
! 38: nh->gw = gw;
! 39: nh->iface = iface;
! 40: nh->weight = weight;
! 41: return nh;
! 42: }
! 43:
! 44: /* Returns true if there are device nexthops in n */
! 45: static inline int
! 46: has_device_nexthops(const struct nexthop *n)
! 47: {
! 48: for (; n; n = n->next)
! 49: if (ipa_zero(n->gw))
! 50: return 1;
! 51:
! 52: return 0;
! 53: }
! 54:
! 55: /* Replace device nexthops with nexthops to gw */
! 56: static struct nexthop *
! 57: fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
! 58: {
! 59: struct nexthop *root1 = NULL;
! 60: struct nexthop *root2 = NULL;
! 61: struct nexthop **nn1 = &root1;
! 62: struct nexthop **nn2 = &root2;
! 63:
! 64: if (!p->ecmp)
! 65: return new_nexthop(p, gw, n->iface, n->weight);
! 66:
! 67: /* This is a bit tricky. We cannot just copy the list and update n->gw,
! 68: because the list should stay sorted, so we create two lists, one with new
! 69: gateways and one with old ones, and then merge them. */
! 70:
! 71: for (; n; n = n->next)
! 72: {
! 73: struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
! 74:
! 75: if (ipa_zero(n->gw))
! 76: {
! 77: *nn1 = nn;
! 78: nn1 = &(nn->next);
! 79: }
! 80: else
! 81: {
! 82: *nn2 = nn;
! 83: nn2 = &(nn->next);
! 84: }
! 85: }
! 86:
! 87: return nexthop_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
! 88: }
! 89:
! 90:
! 91: /* Whether the ASBR or the forward address destination is preferred
! 92: in AS external route selection according to 16.4.1. */
! 93: static inline int
! 94: epath_preferred(const orta *ep)
! 95: {
! 96: return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
! 97: }
! 98:
! 99: /* Whether the ext route has ASBR/next_hop marked as preferred. */
! 100: static inline int
! 101: orta_pref(const orta *nf)
! 102: {
! 103: return !!(nf->options & ORTA_PREF);
! 104: }
! 105:
! 106: /* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
! 107: Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
! 108: static int
! 109: orta_prio(const orta *nf)
! 110: {
! 111: /* RFC 3101 2.5 (6e) priorities */
! 112: u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
! 113:
! 114: /* A Type-7 LSA with the P-bit set */
! 115: if (opts == (ORTA_NSSA | ORTA_PROP))
! 116: return 2;
! 117:
! 118: /* A Type-5 LSA */
! 119: if (opts == 0)
! 120: return 1;
! 121:
! 122: return 0;
! 123: }
! 124:
! 125: /* Whether the route is better according to RFC 3101 2.5 (6e):
! 126: Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
! 127: static int
! 128: orta_prefer_lsa(const orta *new, const orta *old)
! 129: {
! 130: int pn = orta_prio(new);
! 131: int po = orta_prio(old);
! 132:
! 133: return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
! 134: }
! 135:
! 136: /*
! 137: * Compare an existing routing table entry with a new one. Applicable for
! 138: * intra-area routes, inter-area routes and router entries. Returns integer
! 139: * <, = or > than 0 if the new orta is less, equal or more preferred than
! 140: * the old orta.
! 141: */
! 142: static int
! 143: orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
! 144: {
! 145: int r;
! 146:
! 147: if (old->type == RTS_DUMMY)
! 148: return 1;
! 149:
! 150: /* Prefer intra-area to inter-area to externals */
! 151: r = ((int) old->type) - ((int) new->type);
! 152: if (r) return r;
! 153:
! 154: /* Prefer lowest type 1 metric */
! 155: r = ((int) old->metric1) - ((int) new->metric1);
! 156: if (r) return r;
! 157:
! 158:
! 159: /* Rest is BIRD-specific */
! 160:
! 161: /* Area-wide routes should not mix next-hops from different areas.
! 162: This generally should not happen unless there is some misconfiguration. */
! 163: if (new->oa->areaid != old->oa->areaid)
! 164: return (new->oa->areaid > old->oa->areaid) ? 1 : -1;
! 165:
! 166: /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
! 167: vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
! 168: if (!old->nhs)
! 169: return -1;
! 170: if (!new->nhs)
! 171: return 1;
! 172: if (nh_is_vlink(new->nhs))
! 173: return -1;
! 174: if (nh_is_vlink(old->nhs))
! 175: return 1;
! 176:
! 177:
! 178: if (p->ecmp)
! 179: return 0;
! 180:
! 181: /* Prefer routes with higher Router ID, just to be more deterministic */
! 182: if (new->rid > old->rid)
! 183: return 1;
! 184:
! 185: return -1;
! 186: }
! 187:
! 188: /*
! 189: * Compare ASBR routing table entry with a new one, used for precompute ASBRs
! 190: * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
! 191: * than 0 if the new ASBR is less or more preferred than the old ASBR.
! 192: */
! 193: static int
! 194: orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
! 195: {
! 196: int r;
! 197:
! 198: if (old->type == RTS_DUMMY)
! 199: return 1;
! 200:
! 201: if (!p->rfc1583)
! 202: {
! 203: r = epath_preferred(new) - epath_preferred(old);
! 204: if (r) return r;
! 205: }
! 206:
! 207: r = ((int) old->metric1) - ((int) new->metric1);
! 208: if (r) return r;
! 209:
! 210: /* Larger area ID is preferred */
! 211: if (new->oa->areaid > old->oa->areaid)
! 212: return 1;
! 213:
! 214: /* There is just one ASBR of that RID per area, so tie is not possible */
! 215: return -1;
! 216: }
! 217:
! 218: /*
! 219: * Compare a routing table entry with a new one, for AS external routes
! 220: * (RFC 2328 16.4) and NSSA routes (RFC 3101 2.5), Returns integer <, = or >
! 221: * than 0 if the new orta is less, equal or more preferred than the old orta.
! 222: */
! 223: static int
! 224: orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
! 225: {
! 226: int r;
! 227:
! 228: if (old->type == RTS_DUMMY)
! 229: return 1;
! 230:
! 231: /* 16.4 (6a) - prefer routes with lower type */
! 232: r = ((int) old->type) - ((int) new->type);
! 233: if (r) return r;
! 234:
! 235: /* 16.4 (6b) - prefer routes with lower type 2 metric */
! 236: if (new->type == RTS_OSPF_EXT2)
! 237: {
! 238: r = ((int) old->metric2) - ((int) new->metric2);
! 239: if (r) return r;
! 240: }
! 241:
! 242: /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
! 243: if (!p->rfc1583)
! 244: {
! 245: r = orta_pref(new) - orta_pref(old);
! 246: if (r) return r;
! 247: }
! 248:
! 249: /* 16.4 (6d) - prefer routes with lower type 1 metric */
! 250: r = ((int) old->metric1) - ((int) new->metric1);
! 251: if (r) return r;
! 252:
! 253:
! 254: if (p->ecmp && p->merge_external)
! 255: return 0;
! 256:
! 257: /*
! 258: * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
! 259: * LSA with higher router ID. Although this should apply just to functionally
! 260: * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
! 261: * use it also to disambiguate otherwise equally preferred nexthops.
! 262: */
! 263: if (orta_prefer_lsa(new, old))
! 264: return 1;
! 265:
! 266: return -1;
! 267: }
! 268:
! 269:
! 270: static inline void
! 271: ort_replace(ort *o, const orta *new)
! 272: {
! 273: memcpy(&o->n, new, sizeof(orta));
! 274: }
! 275:
! 276: static void
! 277: ort_merge(struct ospf_proto *p, ort *o, const orta *new)
! 278: {
! 279: orta *old = &o->n;
! 280:
! 281: if (old->nhs != new->nhs)
! 282: {
! 283: old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
! 284: p->ecmp, p->nhpool);
! 285: old->nhs_reuse = 1;
! 286: }
! 287:
! 288: if (old->rid < new->rid)
! 289: old->rid = new->rid;
! 290: }
! 291:
! 292: static void
! 293: ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
! 294: {
! 295: orta *old = &o->n;
! 296:
! 297: if (old->nhs != new->nhs)
! 298: {
! 299: old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
! 300: p->ecmp, p->nhpool);
! 301: old->nhs_reuse = 1;
! 302: }
! 303:
! 304: if (old->tag != new->tag)
! 305: old->tag = 0;
! 306:
! 307: /*
! 308: * Even with multipath, we store only one LSA in orta.en for the purpose of
! 309: * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
! 310: * to all chosen LSAs for given network, not just to functionally equivalent
! 311: * ones (i.e. ones with the same non-zero forwarding address).
! 312: */
! 313: if (orta_prefer_lsa(new, old))
! 314: {
! 315: old->options = new->options;
! 316: old->rid = new->rid;
! 317: old->oa = new->oa;
! 318: old->en = new->en;
! 319: }
! 320: }
! 321:
! 322:
! 323:
! 324: static inline void
! 325: ri_install_net(struct ospf_proto *p, net_addr *net, const orta *new)
! 326: {
! 327: ort *old = fib_get(&p->rtf, net);
! 328: int cmp = orta_compare(p, new, &old->n);
! 329:
! 330: if (cmp > 0)
! 331: ort_replace(old, new);
! 332: else if (cmp == 0)
! 333: ort_merge(p, old, new);
! 334: }
! 335:
! 336: static inline void
! 337: ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
! 338: {
! 339: net_addr_ip4 nrid = net_from_rid(rid);
! 340: ort *old = fib_get(&oa->rtr, (net_addr *) &nrid);
! 341: int cmp = orta_compare(oa->po, new, &old->n);
! 342:
! 343: if (cmp > 0)
! 344: ort_replace(old, new);
! 345: else if (cmp == 0)
! 346: ort_merge(oa->po, old, new);
! 347: }
! 348:
! 349: static inline void
! 350: ri_install_asbr(struct ospf_proto *p, u32 rid, const orta *new)
! 351: {
! 352: net_addr_ip4 nrid = net_from_rid(rid);
! 353: ort *old = fib_get(&p->backbone->rtr, (net_addr *) &nrid);
! 354:
! 355: if (orta_compare_asbr(p, new, &old->n) > 0)
! 356: ort_replace(old, new);
! 357: }
! 358:
! 359: static inline void
! 360: ri_install_ext(struct ospf_proto *p, net_addr *net, const orta *new)
! 361: {
! 362: ort *old = fib_get(&p->rtf, net);
! 363: int cmp = orta_compare_ext(p, new, &old->n);
! 364:
! 365: if (cmp > 0)
! 366: ort_replace(old, new);
! 367: else if (cmp == 0)
! 368: ort_merge_ext(p, old, new);
! 369: }
! 370:
! 371: static inline struct ospf_iface *
! 372: rt_pos_to_ifa(struct ospf_area *oa, int pos)
! 373: {
! 374: struct ospf_iface *ifa;
! 375:
! 376: WALK_LIST(ifa, oa->po->iface_list)
! 377: if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
! 378: return ifa;
! 379:
! 380: return NULL;
! 381: }
! 382:
! 383: static inline struct ospf_iface *
! 384: px_pos_to_ifa(struct ospf_area *oa, int pos)
! 385: {
! 386: struct ospf_iface *ifa;
! 387:
! 388: WALK_LIST(ifa, oa->po->iface_list)
! 389: if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
! 390: return ifa;
! 391:
! 392: return NULL;
! 393: }
! 394:
! 395: static inline struct ospf_iface *
! 396: rt_find_iface2(struct ospf_area *oa, uint data)
! 397: {
! 398: ip_addr addr = ipa_from_u32(data);
! 399:
! 400: /* We should handle it differently for unnumbered PTP links */
! 401: struct ospf_iface *ifa;
! 402: WALK_LIST(ifa, oa->po->iface_list)
! 403: if ((ifa->oa == oa) && ifa->addr && (ipa_equal(ifa->addr->ip, addr)))
! 404: return ifa;
! 405:
! 406: return NULL;
! 407: }
! 408:
! 409: static inline struct ospf_iface *
! 410: rt_find_iface3(struct ospf_area *oa, uint lif)
! 411: {
! 412: struct ospf_iface *ifa;
! 413: WALK_LIST(ifa, oa->po->iface_list)
! 414: if ((ifa->oa == oa) && (ifa->iface_id == lif))
! 415: return ifa;
! 416:
! 417: return NULL;
! 418: }
! 419:
! 420: static struct ospf_iface *
! 421: rt_find_iface(struct ospf_area *oa, int pos, uint data, uint lif)
! 422: {
! 423: if (0)
! 424: return rt_pos_to_ifa(oa, pos);
! 425: else
! 426: return ospf_is_v2(oa->po) ? rt_find_iface2(oa, data) : rt_find_iface3(oa, lif);
! 427: }
! 428:
! 429:
! 430: static void
! 431: add_network(struct ospf_area *oa, net_addr *net, int metric, struct top_hash_entry *en, int pos)
! 432: {
! 433: struct ospf_proto *p = oa->po;
! 434:
! 435: orta nf = {
! 436: .type = RTS_OSPF,
! 437: .options = 0,
! 438: .metric1 = metric,
! 439: .rid = en->lsa.rt,
! 440: .oa = oa,
! 441: .nhs = en->nhs
! 442: };
! 443:
! 444: if (!ospf_valid_prefix(net))
! 445: {
! 446: log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
! 447: p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
! 448: return;
! 449: }
! 450:
! 451: if (en == oa->rt)
! 452: {
! 453: /*
! 454: * Local stub networks do not have proper iface in en->nhi (because they all
! 455: * have common top_hash_entry en). We have to find iface responsible for
! 456: * that stub network. Configured stubnets do not have any iface. They will
! 457: * be removed in rt_sync().
! 458: */
! 459:
! 460: struct ospf_iface *ifa;
! 461: ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
! 462: nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
! 463: }
! 464:
! 465: ri_install_net(p, net, &nf);
! 466: }
! 467:
! 468:
! 469:
! 470: static inline void
! 471: spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
! 472: {
! 473: struct ospf_lsa_rt *rt = act->lsa_body;
! 474: struct ospf_lsa_rt_walk rtl;
! 475: struct top_hash_entry *tmp;
! 476: int i;
! 477:
! 478: if (rt->options & OPT_RT_V)
! 479: oa->trcap = 1;
! 480:
! 481: /*
! 482: * In OSPFv3, all routers are added to per-area routing
! 483: * tables. But we use it just for ASBRs and ABRs. For the
! 484: * purpose of the last step in SPF - prefix-LSA processing in
! 485: * spfa_process_prefixes(), we use information stored in LSA db.
! 486: */
! 487: if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
! 488: && (act->lsa.rt != p->router_id))
! 489: {
! 490: orta nf = {
! 491: .type = RTS_OSPF,
! 492: .options = rt->options,
! 493: .metric1 = act->dist,
! 494: .rid = act->lsa.rt,
! 495: .oa = oa,
! 496: .nhs = act->nhs
! 497: };
! 498: ri_install_rt(oa, act->lsa.rt, &nf);
! 499: }
! 500:
! 501: /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
! 502: if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
! 503: return;
! 504:
! 505: /* Now process Rt links */
! 506: for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
! 507: {
! 508: tmp = NULL;
! 509:
! 510: switch (rtl.type)
! 511: {
! 512: case LSART_STUB:
! 513:
! 514: /* Should not happen, LSART_STUB is not defined in OSPFv3 */
! 515: if (ospf_is_v3(p))
! 516: break;
! 517:
! 518: /*
! 519: * RFC 2328 in 16.1. (2a) says to handle stub networks in an
! 520: * second phase after the SPF for an area is calculated. We get
! 521: * the same result by handing them here because add_network()
! 522: * will keep the best (not the first) found route.
! 523: */
! 524: net_addr_ip4 net =
! 525: NET_ADDR_IP4(ip4_from_u32(rtl.id & rtl.data), u32_masklen(rtl.data));
! 526:
! 527: add_network(oa, (net_addr *) &net, act->dist + rtl.metric, act, i);
! 528: break;
! 529:
! 530: case LSART_NET:
! 531: tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
! 532: break;
! 533:
! 534: case LSART_VLNK:
! 535: case LSART_PTP:
! 536: tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
! 537: break;
! 538: }
! 539:
! 540: add_cand(oa, tmp, act, act->dist + rtl.metric, i, rtl.data, rtl.lif, rtl.nif);
! 541: }
! 542: }
! 543:
! 544: static inline void
! 545: spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
! 546: {
! 547: struct ospf_lsa_net *ln = act->lsa_body;
! 548: struct top_hash_entry *tmp;
! 549: int i, cnt;
! 550:
! 551: if (ospf_is_v2(p))
! 552: {
! 553: net_addr_ip4 net =
! 554: NET_ADDR_IP4(ip4_from_u32(act->lsa.id & ln->optx), u32_masklen(ln->optx));
! 555:
! 556: add_network(oa, (net_addr *) &net, act->dist, act, -1);
! 557: }
! 558:
! 559: cnt = lsa_net_count(&act->lsa);
! 560: for (i = 0; i < cnt; i++)
! 561: {
! 562: tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
! 563: add_cand(oa, tmp, act, act->dist, -1, 0, 0, 0);
! 564: }
! 565: }
! 566:
! 567: static inline void
! 568: spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
! 569: {
! 570: struct top_hash_entry *en, *src;
! 571: struct ospf_lsa_prefix *px;
! 572: u32 *buf;
! 573: int i;
! 574:
! 575: WALK_SLIST(en, p->lsal)
! 576: {
! 577: if (en->lsa_type != LSA_T_PREFIX)
! 578: continue;
! 579:
! 580: if (en->domain != oa->areaid)
! 581: continue;
! 582:
! 583: if (en->lsa.age == LSA_MAXAGE)
! 584: continue;
! 585:
! 586: px = en->lsa_body;
! 587:
! 588: /* For router prefix-LSA, we would like to find the first router-LSA */
! 589: if (px->ref_type == LSA_T_RT)
! 590: src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
! 591: else
! 592: src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
! 593:
! 594: if (!src)
! 595: continue;
! 596:
! 597: /* Reachable in SPF */
! 598: if (src->color != INSPF)
! 599: continue;
! 600:
! 601: if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
! 602: continue;
! 603:
! 604: buf = px->rest;
! 605: for (i = 0; i < px->pxcount; i++)
! 606: {
! 607: net_addr net;
! 608: u8 pxopts;
! 609: u16 metric;
! 610:
! 611: buf = ospf3_get_prefix(buf, ospf_get_af(p), &net, &pxopts, &metric);
! 612:
! 613: if (pxopts & OPT_PX_NU)
! 614: continue;
! 615:
! 616: /* Store the first global address to use it later as a vlink endpoint */
! 617: if ((pxopts & OPT_PX_LA) && (net.type == NET_IP6) && ipa_zero(src->lb))
! 618: src->lb = ipa_from_ip6(net6_prefix(&net));
! 619:
! 620: add_network(oa, &net, src->dist + metric, src, i);
! 621: }
! 622: }
! 623: }
! 624:
! 625: /* RFC 2328 16.1. calculating shortest paths for an area */
! 626: static void
! 627: ospf_rt_spfa(struct ospf_area *oa)
! 628: {
! 629: struct ospf_proto *p = oa->po;
! 630: struct top_hash_entry *act;
! 631: node *n;
! 632:
! 633: if (oa->rt == NULL)
! 634: return;
! 635: if (oa->rt->lsa.age == LSA_MAXAGE)
! 636: return;
! 637:
! 638: OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid);
! 639:
! 640: /* 16.1. (1) */
! 641: init_list(&oa->cand); /* Empty list of candidates */
! 642: oa->trcap = 0;
! 643:
! 644: DBG("LSA db prepared, adding me into candidate list.\n");
! 645:
! 646: oa->rt->dist = 0;
! 647: oa->rt->color = CANDIDATE;
! 648: add_head(&oa->cand, &oa->rt->cn);
! 649: DBG("RT LSA: rt: %R, id: %R, type: %u\n",
! 650: oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
! 651:
! 652: while (!EMPTY_LIST(oa->cand))
! 653: {
! 654: n = HEAD(oa->cand);
! 655: act = SKIP_BACK(struct top_hash_entry, cn, n);
! 656: rem_node(n);
! 657:
! 658: DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
! 659: act->lsa.rt, act->lsa.id, act->lsa_type);
! 660:
! 661: act->color = INSPF;
! 662: switch (act->lsa_type)
! 663: {
! 664: case LSA_T_RT:
! 665: spfa_process_rt(p, oa, act);
! 666: break;
! 667:
! 668: case LSA_T_NET:
! 669: spfa_process_net(p, oa, act);
! 670: break;
! 671:
! 672: default:
! 673: log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
! 674: }
! 675: }
! 676:
! 677: if (ospf_is_v3(p))
! 678: spfa_process_prefixes(p, oa);
! 679: }
! 680:
! 681: static int
! 682: link_back(struct ospf_area *oa, struct top_hash_entry *en,
! 683: struct top_hash_entry *par, uint lif, uint nif)
! 684: {
! 685: struct ospf_proto *p = oa->po;
! 686: struct ospf_lsa_rt_walk rtl;
! 687: struct top_hash_entry *tmp;
! 688: struct ospf_lsa_net *ln;
! 689: u32 i, cnt;
! 690:
! 691: if (!en || !par) return 0;
! 692:
! 693: /* We should check whether there is a link back from en to par,
! 694: this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
! 695: note 23, we don't have to find the same link that is used for par
! 696: to en, any link is enough. This we do for ptp links. For net-rt
! 697: links, we have to find the same link to compute proper lb/lb_id,
! 698: which may be later used as the next hop. */
! 699:
! 700: /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
! 701: it is set in process_prefixes() to any global address in the area */
! 702:
! 703: en->lb = IPA_NONE;
! 704: en->lb_id = 0;
! 705:
! 706: switch (en->lsa_type)
! 707: {
! 708: case LSA_T_RT:
! 709: lsa_walk_rt_init(p, en, &rtl);
! 710: while (lsa_walk_rt(&rtl))
! 711: {
! 712: switch (rtl.type)
! 713: {
! 714: case LSART_STUB:
! 715: break;
! 716:
! 717: case LSART_NET:
! 718: tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
! 719: if (tmp == par)
! 720: {
! 721: /*
! 722: * Note that there may be multiple matching Rt-fields if router 'en'
! 723: * have multiple interfaces to net 'par'. Perhaps we should do ECMP.
! 724: */
! 725: if (ospf_is_v2(p))
! 726: en->lb = ipa_from_u32(rtl.data);
! 727: else
! 728: en->lb_id = rtl.lif;
! 729:
! 730: return 1;
! 731: }
! 732: break;
! 733:
! 734: case LSART_VLNK:
! 735: case LSART_PTP:
! 736: /*
! 737: * For OSPFv2, not necessary the same link, see RFC 2328 [23].
! 738: * For OSPFv3, we verify that by comparing nif and lif fields.
! 739: */
! 740: if (ospf_is_v3(p) && ((rtl.lif != nif) || (rtl.nif != lif)))
! 741: break;
! 742:
! 743: tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
! 744: if (tmp == par)
! 745: return 1;
! 746: break;
! 747: }
! 748: }
! 749: break;
! 750:
! 751: case LSA_T_NET:
! 752: ln = en->lsa_body;
! 753: cnt = lsa_net_count(&en->lsa);
! 754: for (i = 0; i < cnt; i++)
! 755: {
! 756: tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
! 757: if (tmp == par)
! 758: return 1;
! 759: }
! 760: break;
! 761:
! 762: default:
! 763: log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
! 764: }
! 765: return 0;
! 766: }
! 767:
! 768:
! 769: /* RFC 2328 16.2. calculating inter-area routes */
! 770: static void
! 771: ospf_rt_sum(struct ospf_area *oa)
! 772: {
! 773: struct ospf_proto *p = oa->po;
! 774: struct top_hash_entry *en;
! 775: net_addr net;
! 776: u32 dst_rid, metric, options;
! 777: ort *abr;
! 778: int type;
! 779: u8 pxopts;
! 780:
! 781: OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
! 782:
! 783: WALK_SLIST(en, p->lsal)
! 784: {
! 785: if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
! 786: continue;
! 787:
! 788: if (en->domain != oa->areaid)
! 789: continue;
! 790:
! 791: /* 16.2. (1a) */
! 792: if (en->lsa.age == LSA_MAXAGE)
! 793: continue;
! 794:
! 795: /* 16.2. (2) */
! 796: if (en->lsa.rt == p->router_id)
! 797: continue;
! 798:
! 799: /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */
! 800:
! 801: if (en->lsa_type == LSA_T_SUM_NET)
! 802: {
! 803: lsa_parse_sum_net(en, ospf_is_v2(p), ospf_get_af(p), &net, &pxopts, &metric);
! 804:
! 805: if (!ospf_valid_prefix(&net))
! 806: {
! 807: log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
! 808: p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
! 809: continue;
! 810: }
! 811:
! 812: if (pxopts & OPT_PX_NU)
! 813: continue;
! 814:
! 815: /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
! 816: if (p->vpn_pe && (pxopts & OPT_PX_DN))
! 817: continue;
! 818:
! 819: options = 0;
! 820: type = ORT_NET;
! 821: }
! 822: else /* LSA_T_SUM_RT */
! 823: {
! 824: lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
! 825:
! 826: /* We don't want local router in ASBR routing table */
! 827: if (dst_rid == p->router_id)
! 828: continue;
! 829:
! 830: options |= ORTA_ASBR;
! 831: type = ORT_ROUTER;
! 832: }
! 833:
! 834: /* 16.2. (1b) */
! 835: if (metric == LSINFINITY)
! 836: continue;
! 837:
! 838: /* 16.2. (4) */
! 839: net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
! 840: abr = fib_find(&oa->rtr, (net_addr *) &nrid);
! 841: if (!abr || !abr->n.type)
! 842: continue;
! 843:
! 844: if (!(abr->n.options & ORTA_ABR))
! 845: continue;
! 846:
! 847: /* This check is not mentioned in RFC 2328 */
! 848: if (abr->n.type != RTS_OSPF)
! 849: continue;
! 850:
! 851: /* 16.2. (5) */
! 852: orta nf = {
! 853: .type = RTS_OSPF_IA,
! 854: .options = options,
! 855: .metric1 = abr->n.metric1 + metric,
! 856: .rid = en->lsa.rt, /* ABR ID */
! 857: .oa = oa,
! 858: .nhs = abr->n.nhs
! 859: };
! 860:
! 861: if (type == ORT_NET)
! 862: ri_install_net(p, &net, &nf);
! 863: else
! 864: ri_install_rt(oa, dst_rid, &nf);
! 865: }
! 866: }
! 867:
! 868: /* RFC 2328 16.3. examining summary-LSAs in transit areas */
! 869: static void
! 870: ospf_rt_sum_tr(struct ospf_area *oa)
! 871: {
! 872: struct ospf_proto *p = oa->po;
! 873: struct ospf_area *bb = p->backbone;
! 874: struct top_hash_entry *en;
! 875: ort *re, *abr;
! 876: u32 metric;
! 877:
! 878: if (!bb)
! 879: return;
! 880:
! 881: WALK_SLIST(en, p->lsal)
! 882: {
! 883: if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
! 884: continue;
! 885:
! 886: if (en->domain != oa->areaid)
! 887: continue;
! 888:
! 889: /* 16.3 (1a) */
! 890: if (en->lsa.age == LSA_MAXAGE)
! 891: continue;
! 892:
! 893: /* 16.3 (2) */
! 894: if (en->lsa.rt == p->router_id)
! 895: continue;
! 896:
! 897: if (en->lsa_type == LSA_T_SUM_NET)
! 898: {
! 899: net_addr net;
! 900: u8 pxopts;
! 901:
! 902: lsa_parse_sum_net(en, ospf_is_v2(p), ospf_get_af(p), &net, &pxopts, &metric);
! 903:
! 904: if (!ospf_valid_prefix(&net))
! 905: {
! 906: log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
! 907: p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
! 908: continue;
! 909: }
! 910:
! 911: if (pxopts & OPT_PX_NU)
! 912: continue;
! 913:
! 914: /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
! 915: if (p->vpn_pe && (pxopts & OPT_PX_DN))
! 916: continue;
! 917:
! 918: re = fib_find(&p->rtf, &net);
! 919: }
! 920: else // en->lsa_type == LSA_T_SUM_RT
! 921: {
! 922: u32 dst_rid, options;
! 923:
! 924: lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
! 925:
! 926: net_addr_ip4 nrid = net_from_rid(dst_rid);
! 927: re = fib_find(&bb->rtr, (net_addr *) &nrid);
! 928: }
! 929:
! 930: /* 16.3 (1b) */
! 931: if (metric == LSINFINITY)
! 932: continue;
! 933:
! 934: /* 16.3 (3) */
! 935: if (!re || !re->n.type)
! 936: continue;
! 937:
! 938: if (re->n.oa->areaid != 0)
! 939: continue;
! 940:
! 941: if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
! 942: continue;
! 943:
! 944: /* 16.3. (4) */
! 945: net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
! 946: abr = fib_find(&oa->rtr, (net_addr *) &nrid);
! 947: if (!abr || !abr->n.type)
! 948: continue;
! 949:
! 950: metric = abr->n.metric1 + metric; /* IAC */
! 951:
! 952: /* 16.3. (5) */
! 953: if ((metric < re->n.metric1) ||
! 954: ((metric == re->n.metric1) && unresolved_vlink(re)))
! 955: {
! 956: /* We want to replace the next-hop even if the metric is equal
! 957: to replace a virtual next-hop through vlink with a real one.
! 958: Proper ECMP would merge nexthops here, but we do not do that.
! 959: We restrict nexthops to fit one area to simplify check
! 960: 12.4.3 p4 in decide_sum_lsa() */
! 961:
! 962: re->n.metric1 = metric;
! 963: re->n.voa = oa;
! 964: re->n.nhs = abr->n.nhs;
! 965: }
! 966: }
! 967: }
! 968:
! 969: /* Decide about originating or flushing summary LSAs for condensed area networks */
! 970: static int
! 971: decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
! 972: {
! 973: /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
! 974: if (!oa_is_ext(oa) && !oa->ac->summary)
! 975: return 0;
! 976:
! 977: if (oa == anet_oa)
! 978: return 0;
! 979:
! 980: /* Do not condense routing info when exporting from backbone to the transit area */
! 981: if ((anet_oa == oa->po->backbone) && oa->trcap)
! 982: return 0;
! 983:
! 984: return (anet->active && !anet->hidden);
! 985: }
! 986:
! 987: /* Decide about originating or flushing summary LSAs (12.4.3) */
! 988: static int
! 989: decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
! 990: {
! 991: /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
! 992: if (!oa_is_ext(oa) && !oa->ac->summary)
! 993: return 0;
! 994:
! 995: /* Invalid field - no route */
! 996: if (!nf->n.type)
! 997: return 0;
! 998:
! 999: /* 12.4.3 p2 */
! 1000: if (nf->n.type > RTS_OSPF_IA)
! 1001: return 0;
! 1002:
! 1003: /* 12.4.3 p3 */
! 1004: if ((nf->n.oa->areaid == oa->areaid))
! 1005: return 0;
! 1006:
! 1007: /* 12.4.3 p4 */
! 1008: if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
! 1009: return 0;
! 1010:
! 1011: /* 12.4.3 p5 */
! 1012: if (nf->n.metric1 >= LSINFINITY)
! 1013: return 0;
! 1014:
! 1015: /* 12.4.3 p6 - AS boundary router */
! 1016: if (dest == ORT_ROUTER)
! 1017: {
! 1018: /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
! 1019: /* 12.4.3 p1 */
! 1020: return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
! 1021: }
! 1022:
! 1023: /* 12.4.3 p7 - inter-area route */
! 1024: if (nf->n.type == RTS_OSPF_IA)
! 1025: {
! 1026: /* Inter-area routes are not repropagated into the backbone */
! 1027: return (oa != oa->po->backbone);
! 1028: }
! 1029:
! 1030: /* 12.4.3 p8 - intra-area route */
! 1031:
! 1032: /* Do not condense routing info when exporting from backbone to the transit area */
! 1033: if ((nf->n.oa == oa->po->backbone) && oa->trcap)
! 1034: return 1;
! 1035:
! 1036: struct area_net *anet = (struct area_net *)
! 1037: fib_route(&nf->n.oa->net_fib, nf->fn.addr);
! 1038:
! 1039: /* Condensed area network found */
! 1040: if (anet)
! 1041: return 0;
! 1042:
! 1043: return 1;
! 1044: }
! 1045:
! 1046: /* RFC 2328 16.7. p1 - originate or flush summary LSAs */
! 1047: static inline void
! 1048: check_sum_net_lsa(struct ospf_proto *p, ort *nf)
! 1049: {
! 1050: struct area_net *anet = NULL;
! 1051: struct ospf_area *anet_oa = NULL;
! 1052:
! 1053: if (nf->area_net)
! 1054: {
! 1055: /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
! 1056: if (nf->fn.addr->pxlen == 0)
! 1057: return;
! 1058:
! 1059: /* Find that area network */
! 1060: WALK_LIST(anet_oa, p->area_list)
! 1061: {
! 1062: anet = fib_find(&anet_oa->net_fib, nf->fn.addr);
! 1063: if (anet)
! 1064: break;
! 1065: }
! 1066: }
! 1067:
! 1068: struct ospf_area *oa;
! 1069: WALK_LIST(oa, p->area_list)
! 1070: {
! 1071: if (anet && decide_anet_lsa(oa, anet, anet_oa))
! 1072: ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
! 1073: else if (decide_sum_lsa(oa, nf, ORT_NET))
! 1074: ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
! 1075: }
! 1076: }
! 1077:
! 1078: static inline void
! 1079: check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
! 1080: {
! 1081: u32 rid = rid_from_net(nf->fn.addr);
! 1082:
! 1083: struct ospf_area *oa;
! 1084: WALK_LIST(oa, p->area_list)
! 1085: if (decide_sum_lsa(oa, nf, ORT_ROUTER))
! 1086: ospf_originate_sum_rt_lsa(p, oa, rid, nf->n.metric1, nf->n.options);
! 1087: }
! 1088:
! 1089: static inline int
! 1090: decide_nssa_lsa(struct ospf_proto *p, ort *nf, struct ospf_lsa_ext_local *rt)
! 1091: {
! 1092: struct ospf_area *oa = nf->n.oa;
! 1093: struct top_hash_entry *en = nf->n.en;
! 1094:
! 1095: if (!rt_is_nssa(nf) || !oa->translate)
! 1096: return 0;
! 1097:
! 1098: /* Condensed area network found */
! 1099: if (fib_route(&oa->enet_fib, nf->fn.addr))
! 1100: return 0;
! 1101:
! 1102: if (!en || (en->lsa_type != LSA_T_NSSA))
! 1103: return 0;
! 1104:
! 1105: /* We do not store needed data in struct orta, we have to parse the LSA */
! 1106: lsa_parse_ext(en, ospf_is_v2(p), ospf_get_af(p), rt);
! 1107:
! 1108: if (rt->pxopts & OPT_PX_NU)
! 1109: return 0;
! 1110:
! 1111: if (!rt->propagate || ipa_zero(rt->fwaddr))
! 1112: return 0;
! 1113:
! 1114: return 1;
! 1115: }
! 1116:
! 1117: /* RFC 3101 3.2 - translating Type-7 LSAs into Type-5 LSAs */
! 1118: static inline void
! 1119: check_nssa_lsa(struct ospf_proto *p, ort *nf)
! 1120: {
! 1121: struct area_net *anet = NULL;
! 1122: struct ospf_area *oa = NULL;
! 1123: struct ospf_lsa_ext_local rt;
! 1124:
! 1125: /* Do not translate LSA if there is already the external LSA from route export */
! 1126: if (nf->external_rte)
! 1127: return;
! 1128:
! 1129: if (nf->area_net)
! 1130: {
! 1131: /* Find that area network */
! 1132: WALK_LIST(oa, p->area_list)
! 1133: {
! 1134: anet = fib_find(&oa->enet_fib, nf->fn.addr);
! 1135: if (anet)
! 1136: break;
! 1137: }
! 1138: }
! 1139:
! 1140: /* RFC 3101 3.2 (3) - originate the aggregated address range */
! 1141: if (anet && anet->active && !anet->hidden && oa->translate)
! 1142: ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
! 1143: (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0, 0);
! 1144:
! 1145: /* RFC 3101 3.2 (2) - originate the same network */
! 1146: else if (decide_nssa_lsa(p, nf, &rt))
! 1147: ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0, 0);
! 1148: }
! 1149:
! 1150: /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
! 1151: static void
! 1152: ospf_check_vlinks(struct ospf_proto *p)
! 1153: {
! 1154: struct ospf_iface *ifa;
! 1155: WALK_LIST(ifa, p->iface_list)
! 1156: {
! 1157: if (ifa->type == OSPF_IT_VLINK)
! 1158: {
! 1159: struct top_hash_entry *tmp;
! 1160: tmp = ospf_hash_find_rt(p->gr, ifa->voa->areaid, ifa->vid);
! 1161:
! 1162: if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
! 1163: {
! 1164: struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
! 1165:
! 1166: if ((ifa->state != OSPF_IS_PTP)
! 1167: || (ifa->vifa != nhi)
! 1168: || !ipa_equal(ifa->vip, tmp->lb))
! 1169: {
! 1170: OSPF_TRACE(D_EVENTS, "Vlink peer %R found", ifa->vid);
! 1171: ospf_iface_sm(ifa, ISM_DOWN);
! 1172: ifa->vifa = nhi;
! 1173: ifa->addr = nhi->addr;
! 1174: ifa->cost = tmp->dist;
! 1175: ifa->vip = tmp->lb;
! 1176: ospf_iface_sm(ifa, ISM_UP);
! 1177: }
! 1178: else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
! 1179: {
! 1180: ifa->cost = tmp->dist;
! 1181:
! 1182: /* RFC 2328 12.4 Event 8 - vlink state change */
! 1183: ospf_notify_rt_lsa(ifa->oa);
! 1184: }
! 1185: }
! 1186: else
! 1187: {
! 1188: if (ifa->state > OSPF_IS_DOWN)
! 1189: {
! 1190: OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
! 1191: ospf_iface_sm(ifa, ISM_DOWN);
! 1192: }
! 1193: }
! 1194: }
! 1195: }
! 1196: }
! 1197:
! 1198:
! 1199: /* Miscellaneous route processing that needs to be done by ABRs */
! 1200: static void
! 1201: ospf_rt_abr1(struct ospf_proto *p)
! 1202: {
! 1203: struct area_net *anet;
! 1204: ort *default_nf;
! 1205: net_addr default_net;
! 1206:
! 1207: /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
! 1208: FIB_WALK(&p->backbone->rtr, ort, nf)
! 1209: {
! 1210: if (nf->n.type && unresolved_vlink(nf))
! 1211: reset_ri(nf);
! 1212: }
! 1213: FIB_WALK_END;
! 1214:
! 1215:
! 1216: FIB_WALK(&p->rtf, ort, nf)
! 1217: {
! 1218: /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
! 1219: if (nf->n.type && unresolved_vlink(nf))
! 1220: reset_ri(nf);
! 1221:
! 1222:
! 1223: /* Compute condensed area networks */
! 1224: if (nf->n.type == RTS_OSPF)
! 1225: {
! 1226: anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.addr);
! 1227: if (anet)
! 1228: {
! 1229: if (!anet->active)
! 1230: {
! 1231: anet->active = 1;
! 1232:
! 1233: /* Get a RT entry and mark it to know that it is an area network */
! 1234: ort *nfi = fib_get(&p->rtf, anet->fn.addr);
! 1235: nfi->area_net = 1;
! 1236:
! 1237: /* 16.2. (3) */
! 1238: if (nfi->n.type == RTS_OSPF_IA)
! 1239: reset_ri(nfi);
! 1240: }
! 1241:
! 1242: if (anet->metric < nf->n.metric1)
! 1243: anet->metric = nf->n.metric1;
! 1244: }
! 1245: }
! 1246: }
! 1247: FIB_WALK_END;
! 1248:
! 1249:
! 1250: if (ospf_is_v2(p))
! 1251: net_fill_ip4(&default_net, IP4_NONE, 0);
! 1252: else
! 1253: net_fill_ip6(&default_net, IP6_NONE, 0);
! 1254:
! 1255: default_nf = fib_get(&p->rtf, &default_net);
! 1256: default_nf->area_net = 1;
! 1257:
! 1258: struct ospf_area *oa;
! 1259: WALK_LIST(oa, p->area_list)
! 1260: {
! 1261:
! 1262: /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
! 1263: if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
! 1264: ospf_originate_sum_net_lsa(p, oa, default_nf, oa->ac->default_cost);
! 1265:
! 1266: /*
! 1267: * Originate type-7 default route for NSSA areas
! 1268: *
! 1269: * Because type-7 default LSAs are originated by ABRs, they do not
! 1270: * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
! 1271: * for both external route export or external-NSSA translation),
! 1272: * so we use 0 for the src arg.
! 1273: */
! 1274:
! 1275: if (oa_is_nssa(oa) && oa->ac->default_nssa)
! 1276: ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
! 1277: (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0, 0);
! 1278:
! 1279: /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
! 1280: if (oa_is_ext(oa))
! 1281: {
! 1282: FIB_WALK(&oa->rtr, ort, nf)
! 1283: {
! 1284: if (nf->n.options & ORTA_ASBR)
! 1285: ri_install_asbr(p, rid_from_net(nf->fn.addr), &nf->n);
! 1286: }
! 1287: FIB_WALK_END;
! 1288: }
! 1289: }
! 1290:
! 1291:
! 1292: /* Originate or flush ASBR summary LSAs */
! 1293: FIB_WALK(&p->backbone->rtr, ort, nf)
! 1294: {
! 1295: check_sum_rt_lsa(p, nf);
! 1296: }
! 1297: FIB_WALK_END;
! 1298:
! 1299:
! 1300: /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
! 1301: ospf_check_vlinks(p);
! 1302: }
! 1303:
! 1304:
! 1305: static void
! 1306: translator_timer_hook(timer *timer)
! 1307: {
! 1308: struct ospf_area *oa = timer->data;
! 1309:
! 1310: if (oa->translate != TRANS_WAIT)
! 1311: return;
! 1312:
! 1313: oa->translate = TRANS_OFF;
! 1314: ospf_schedule_rtcalc(oa->po);
! 1315: }
! 1316:
! 1317: static void
! 1318: ospf_rt_abr2(struct ospf_proto *p)
! 1319: {
! 1320: struct ospf_area *oa;
! 1321: struct top_hash_entry *en;
! 1322:
! 1323: /* RFC 3101 3.1 - type-7 translator election */
! 1324: struct ospf_area *bb = p->backbone;
! 1325: WALK_LIST(oa, p->area_list)
! 1326: if (oa_is_nssa(oa))
! 1327: {
! 1328: int translate = 1;
! 1329:
! 1330: if (oa->ac->translator)
! 1331: goto decided;
! 1332:
! 1333: FIB_WALK(&oa->rtr, ort, nf)
! 1334: {
! 1335: if (!nf->n.type || !(nf->n.options & ORTA_ABR))
! 1336: continue;
! 1337:
! 1338: ort *nf2 = fib_find(&bb->rtr, nf->fn.addr);
! 1339: if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
! 1340: continue;
! 1341:
! 1342: en = ospf_hash_find_rt(p->gr, oa->areaid, nf->n.rid);
! 1343: if (!en || (en->color != INSPF))
! 1344: continue;
! 1345:
! 1346: struct ospf_lsa_rt *rt = en->lsa_body;
! 1347: /* There is better candidate - Nt-bit or higher Router ID */
! 1348: if ((rt->options & OPT_RT_NT) || (p->router_id < nf->n.rid))
! 1349: {
! 1350: translate = 0;
! 1351: goto decided;
! 1352: }
! 1353: }
! 1354: FIB_WALK_END;
! 1355:
! 1356: decided:
! 1357: if (translate && (oa->translate != TRANS_ON))
! 1358: {
! 1359: if (oa->translate == TRANS_WAIT)
! 1360: tm_stop(oa->translator_timer);
! 1361:
! 1362: oa->translate = TRANS_ON;
! 1363: }
! 1364:
! 1365: if (!translate && (oa->translate == TRANS_ON))
! 1366: {
! 1367: if (oa->translator_timer == NULL)
! 1368: oa->translator_timer = tm_new_init(p->p.pool, translator_timer_hook, oa, 0, 0);
! 1369:
! 1370: /* Schedule the end of translation */
! 1371: tm_start(oa->translator_timer, oa->ac->transint S);
! 1372: oa->translate = TRANS_WAIT;
! 1373: }
! 1374: }
! 1375:
! 1376:
! 1377: /* Compute condensed external networks */
! 1378: FIB_WALK(&p->rtf, ort, nf)
! 1379: {
! 1380: if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
! 1381: {
! 1382: struct area_net *anet = fib_route(&nf->n.oa->enet_fib, nf->fn.addr);
! 1383:
! 1384: if (anet)
! 1385: {
! 1386: if (!anet->active)
! 1387: {
! 1388: anet->active = 1;
! 1389:
! 1390: /* Get a RT entry and mark it to know that it is an area network */
! 1391: ort *nf2 = fib_get(&p->rtf, anet->fn.addr);
! 1392: nf2->area_net = 1;
! 1393: }
! 1394:
! 1395: u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
! 1396: nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);
! 1397:
! 1398: if (anet->metric < metric)
! 1399: anet->metric = metric;
! 1400: }
! 1401: }
! 1402: }
! 1403: FIB_WALK_END;
! 1404:
! 1405:
! 1406: FIB_WALK(&p->rtf, ort, nf)
! 1407: {
! 1408: check_sum_net_lsa(p, nf);
! 1409: check_nssa_lsa(p, nf);
! 1410: }
! 1411: FIB_WALK_END;
! 1412: }
! 1413:
! 1414:
! 1415: /* Like fib_route(), but ignores dummy rt entries */
! 1416: static void *
! 1417: ospf_fib_route_ip4(struct fib *f, ip4_addr a, int len)
! 1418: {
! 1419: net_addr_ip4 net = NET_ADDR_IP4(a, len);
! 1420: ort *nf;
! 1421:
! 1422: loop:
! 1423: nf = fib_find(f, (net_addr *) &net);
! 1424: if (nf && nf->n.type)
! 1425: return nf;
! 1426:
! 1427: if (net.pxlen > 0)
! 1428: {
! 1429: net.pxlen--;
! 1430: ip4_clrbit(&net.prefix, net.pxlen);
! 1431: goto loop;
! 1432: }
! 1433:
! 1434: return NULL;
! 1435: }
! 1436:
! 1437: static void *
! 1438: ospf_fib_route_ip6(struct fib *f, ip6_addr a, int len)
! 1439: {
! 1440: net_addr_ip6 net = NET_ADDR_IP6(a, len);
! 1441: ort *nf;
! 1442:
! 1443: loop:
! 1444: nf = fib_find(f, (net_addr *) &net);
! 1445: if (nf && nf->n.type)
! 1446: return nf;
! 1447:
! 1448: if (net.pxlen > 0)
! 1449: {
! 1450: net.pxlen--;
! 1451: ip6_clrbit(&net.prefix, net.pxlen);
! 1452: goto loop;
! 1453: }
! 1454:
! 1455: return NULL;
! 1456: }
! 1457:
! 1458: static void *
! 1459: ospf_fib_route(struct fib *f, ip_addr a)
! 1460: {
! 1461: if (f->addr_type == NET_IP4)
! 1462: return ospf_fib_route_ip4(f, ipa_to_ip4(a), IP4_MAX_PREFIX_LENGTH);
! 1463: else
! 1464: return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH);
! 1465: }
! 1466:
! 1467:
! 1468: /* RFC 2328 16.4. calculating external routes */
! 1469: static void
! 1470: ospf_ext_spf(struct ospf_proto *p)
! 1471: {
! 1472: struct top_hash_entry *en;
! 1473: struct ospf_lsa_ext_local rt;
! 1474: ort *nf1, *nf2;
! 1475: u32 br_metric;
! 1476: struct ospf_area *atmp;
! 1477:
! 1478: OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
! 1479:
! 1480: WALK_SLIST(en, p->lsal)
! 1481: {
! 1482: orta nfa = {};
! 1483:
! 1484: /* 16.4. (1) */
! 1485: if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
! 1486: continue;
! 1487:
! 1488: if (en->lsa.age == LSA_MAXAGE)
! 1489: continue;
! 1490:
! 1491: /* 16.4. (2) */
! 1492: if (en->lsa.rt == p->router_id)
! 1493: continue;
! 1494:
! 1495: DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
! 1496: p->p.name, en->lsa.id, en->lsa.rt, en->lsa_type);
! 1497:
! 1498: lsa_parse_ext(en, ospf_is_v2(p), ospf_get_af(p), &rt);
! 1499:
! 1500: if (!ospf_valid_prefix(&rt.net))
! 1501: {
! 1502: log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
! 1503: p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
! 1504: continue;
! 1505: }
! 1506:
! 1507: if (rt.metric == LSINFINITY)
! 1508: continue;
! 1509:
! 1510: if (rt.pxopts & OPT_PX_NU)
! 1511: continue;
! 1512:
! 1513: /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
! 1514: if (p->vpn_pe && rt.downwards)
! 1515: continue;
! 1516:
! 1517: /* 16.4. (3) */
! 1518: /* If there are more areas, we already precomputed preferred ASBR
! 1519: entries in ospf_rt_abr1() and stored them in the backbone
! 1520: table. For NSSA, we examine the area to which the LSA is assigned */
! 1521: if (en->lsa_type == LSA_T_EXT)
! 1522: atmp = ospf_main_area(p);
! 1523: else /* NSSA */
! 1524: atmp = ospf_find_area(p, en->domain);
! 1525:
! 1526: if (!atmp)
! 1527: continue; /* Should not happen */
! 1528:
! 1529: net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
! 1530: nf1 = fib_find(&atmp->rtr, (net_addr *) &nrid);
! 1531:
! 1532: if (!nf1 || !nf1->n.type)
! 1533: continue; /* No AS boundary router found */
! 1534:
! 1535: if (!(nf1->n.options & ORTA_ASBR))
! 1536: continue; /* It is not ASBR */
! 1537:
! 1538: /* 16.4. (3) NSSA - special rule for default routes */
! 1539: /* ABR should use default only if P-bit is set and summaries are active */
! 1540: if ((en->lsa_type == LSA_T_NSSA) && (rt.net.pxlen == 0) &&
! 1541: (p->areano > 1) && !(rt.propagate && atmp->ac->summary))
! 1542: continue;
! 1543:
! 1544: if (!rt.fbit)
! 1545: {
! 1546: nf2 = nf1;
! 1547: nfa.nhs = nf1->n.nhs;
! 1548: br_metric = nf1->n.metric1;
! 1549: }
! 1550: else
! 1551: {
! 1552: nf2 = ospf_fib_route(&p->rtf, rt.fwaddr);
! 1553: if (!nf2)
! 1554: continue;
! 1555:
! 1556: if (en->lsa_type == LSA_T_EXT)
! 1557: {
! 1558: /* For ext routes, we accept intra-area or inter-area routes */
! 1559: if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
! 1560: continue;
! 1561: }
! 1562: else /* NSSA */
! 1563: {
! 1564: /* For NSSA routes, we accept just intra-area in the same area */
! 1565: if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
! 1566: continue;
! 1567: }
! 1568:
! 1569: /* Next-hop is a part of a configured stubnet */
! 1570: if (!nf2->n.nhs)
! 1571: continue;
! 1572:
! 1573: nfa.nhs = nf2->n.nhs;
! 1574: br_metric = nf2->n.metric1;
! 1575:
! 1576: /* Replace device nexthops with nexthops to forwarding address from LSA */
! 1577: if (has_device_nexthops(nfa.nhs))
! 1578: {
! 1579: nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
! 1580: nfa.nhs_reuse = 1;
! 1581: }
! 1582: }
! 1583:
! 1584: if (rt.ebit)
! 1585: {
! 1586: nfa.type = RTS_OSPF_EXT2;
! 1587: nfa.metric1 = br_metric;
! 1588: nfa.metric2 = rt.metric;
! 1589: }
! 1590: else
! 1591: {
! 1592: nfa.type = RTS_OSPF_EXT1;
! 1593: nfa.metric1 = br_metric + rt.metric;
! 1594: nfa.metric2 = 0;
! 1595: }
! 1596:
! 1597: /* Mark the LSA as reachable */
! 1598: en->color = INSPF;
! 1599:
! 1600: /* Whether the route is preferred in route selection according to 16.4.1 */
! 1601: nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
! 1602: if (en->lsa_type == LSA_T_NSSA)
! 1603: {
! 1604: nfa.options |= ORTA_NSSA;
! 1605: if (rt.propagate)
! 1606: nfa.options |= ORTA_PROP;
! 1607: }
! 1608:
! 1609: nfa.tag = rt.tag;
! 1610: nfa.rid = en->lsa.rt;
! 1611: nfa.oa = atmp; /* undefined in RFC 2328 */
! 1612: nfa.en = en; /* store LSA for later (NSSA processing) */
! 1613:
! 1614: ri_install_ext(p, &rt.net, &nfa);
! 1615: }
! 1616: }
! 1617:
! 1618: /* Cleanup of routing tables and data */
! 1619: void
! 1620: ospf_rt_reset(struct ospf_proto *p)
! 1621: {
! 1622: struct ospf_area *oa;
! 1623: struct top_hash_entry *en;
! 1624:
! 1625: /* Reset old routing table */
! 1626: FIB_WALK(&p->rtf, ort, ri)
! 1627: {
! 1628: ri->area_net = 0;
! 1629: ri->keep = 0;
! 1630: reset_ri(ri);
! 1631: }
! 1632: FIB_WALK_END;
! 1633:
! 1634: /* Reset SPF data in LSA db */
! 1635: WALK_SLIST(en, p->lsal)
! 1636: {
! 1637: en->color = OUTSPF;
! 1638: en->dist = LSINFINITY;
! 1639: en->nhs = NULL;
! 1640: en->lb = IPA_NONE;
! 1641:
! 1642: if (en->mode == LSA_M_RTCALC)
! 1643: en->mode = LSA_M_RTCALC_STALE;
! 1644: }
! 1645:
! 1646: WALK_LIST(oa, p->area_list)
! 1647: {
! 1648: /* Reset ASBR routing tables */
! 1649: FIB_WALK(&oa->rtr, ort, ri)
! 1650: {
! 1651: reset_ri(ri);
! 1652: }
! 1653: FIB_WALK_END;
! 1654:
! 1655: /* Reset condensed area networks */
! 1656: if (p->areano > 1)
! 1657: {
! 1658: FIB_WALK(&oa->net_fib, struct area_net, anet)
! 1659: {
! 1660: anet->active = 0;
! 1661: anet->metric = 0;
! 1662: }
! 1663: FIB_WALK_END;
! 1664:
! 1665: FIB_WALK(&oa->enet_fib, struct area_net, anet)
! 1666: {
! 1667: anet->active = 0;
! 1668: anet->metric = 0;
! 1669: }
! 1670: FIB_WALK_END;
! 1671: }
! 1672: }
! 1673: }
! 1674:
! 1675: /**
! 1676: * ospf_rt_spf - calculate internal routes
! 1677: * @p: OSPF protocol instance
! 1678: *
! 1679: * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
! 1680: * It's based on Dijkstra's shortest path tree algorithms.
! 1681: * This function is invoked from ospf_disp().
! 1682: */
! 1683: void
! 1684: ospf_rt_spf(struct ospf_proto *p)
! 1685: {
! 1686: struct ospf_area *oa;
! 1687:
! 1688: if (p->areano == 0)
! 1689: return;
! 1690:
! 1691: OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
! 1692:
! 1693: /* 16. (1) */
! 1694: ospf_rt_reset(p);
! 1695:
! 1696: /* 16. (2) */
! 1697: WALK_LIST(oa, p->area_list)
! 1698: ospf_rt_spfa(oa);
! 1699:
! 1700: /* 16. (3) */
! 1701: ospf_rt_sum(ospf_main_area(p));
! 1702:
! 1703: /* 16. (4) */
! 1704: WALK_LIST(oa, p->area_list)
! 1705: if (oa->trcap && (oa->areaid != 0))
! 1706: ospf_rt_sum_tr(oa);
! 1707:
! 1708: if (p->areano > 1)
! 1709: ospf_rt_abr1(p);
! 1710:
! 1711: /* 16. (5) */
! 1712: ospf_ext_spf(p);
! 1713:
! 1714: if (p->areano > 1)
! 1715: ospf_rt_abr2(p);
! 1716:
! 1717: rt_sync(p);
! 1718: lp_flush(p->nhpool);
! 1719:
! 1720: p->calcrt = 0;
! 1721: }
! 1722:
! 1723:
! 1724: static inline int
! 1725: inherit_nexthops(struct nexthop *pn)
! 1726: {
! 1727: /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
! 1728: return pn && (ipa_nonzero(pn->gw) || !pn->iface);
! 1729: }
! 1730:
! 1731: static inline ip_addr
! 1732: link_lsa_lladdr(struct ospf_proto *p, struct top_hash_entry *en)
! 1733: {
! 1734: struct ospf_lsa_link *link_lsa = en->lsa_body;
! 1735: ip6_addr ll = link_lsa->lladdr;
! 1736:
! 1737: if (ip6_zero(ll))
! 1738: return IPA_NONE;
! 1739:
! 1740: return ospf_is_ip4(p) ? ipa_from_ip4(ospf3_6to4(ll)) : ipa_from_ip6(ll);
! 1741: }
! 1742:
! 1743: static struct nexthop *
! 1744: calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
! 1745: struct top_hash_entry *par, int pos, uint data, uint lif, uint nif)
! 1746: {
! 1747: struct ospf_proto *p = oa->po;
! 1748: struct nexthop *pn = par->nhs;
! 1749: struct top_hash_entry *link = NULL;
! 1750: struct ospf_iface *ifa = NULL;
! 1751: ip_addr nh = IPA_NONE;
! 1752: u32 rid = en->lsa.rt;
! 1753:
! 1754: /* 16.1.1. The next hop calculation */
! 1755: DBG(" Next hop calculating for id: %R rt: %R type: %u\n",
! 1756: en->lsa.id, en->lsa.rt, en->lsa_type);
! 1757:
! 1758: /* Usually, we inherit parent nexthops */
! 1759: if (inherit_nexthops(pn))
! 1760: return pn;
! 1761:
! 1762: /*
! 1763: * There are three cases:
! 1764: * 1) en is a local network (and par is root)
! 1765: * 2) en is a ptp or ptmp neighbor (and par is root)
! 1766: * 3) en is a bcast or nbma neighbor (and par is local network)
! 1767: */
! 1768:
! 1769: /* The first case - local network */
! 1770: if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
! 1771: {
! 1772: ifa = rt_find_iface(oa, pos, data, lif);
! 1773: if (!ifa)
! 1774: return NULL;
! 1775:
! 1776: if (ospf_is_v3(p) && (ifa->iface_id != lif))
! 1777: log(L_WARN "%s: Inconsistent interface ID %u/%u", p->p.name, ifa->iface_id, lif);
! 1778:
! 1779: return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
! 1780: }
! 1781:
! 1782: /* The second case - ptp or ptmp neighbor */
! 1783: if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
! 1784: {
! 1785: ifa = rt_find_iface(oa, pos, data, lif);
! 1786: if (!ifa)
! 1787: return NULL;
! 1788:
! 1789: if (ospf_is_v3(p) && (ifa->iface_id != lif))
! 1790: log(L_WARN "%s: Inconsistent interface ID %u/%u", p->p.name, ifa->iface_id, lif);
! 1791:
! 1792: if (ifa->type == OSPF_IT_VLINK)
! 1793: return new_nexthop(p, IPA_NONE, NULL, 0);
! 1794:
! 1795: /* FIXME: On physical PtP links we may skip next-hop altogether */
! 1796:
! 1797: if (ospf_is_v2(p) || ospf_is_ip6(p))
! 1798: {
! 1799: /*
! 1800: * In this case, next-hop is a source address from neighbor's packets.
! 1801: * That is necessary for OSPFv2 and practical for OSPFv3 (as it works even
! 1802: * if neighbor uses LinkLSASuppression), but does not work with OSPFv3-AF
! 1803: * on IPv4 topology, where src is IPv6 but next-hop should be IPv4.
! 1804: */
! 1805: struct ospf_neighbor *m = find_neigh(ifa, rid);
! 1806: if (!m || (m->state != NEIGHBOR_FULL))
! 1807: return NULL;
! 1808:
! 1809: nh = m->ip;
! 1810: }
! 1811: else
! 1812: {
! 1813: /*
! 1814: * Next-hop is taken from lladdr field of Link-LSA, based on Neighbor
! 1815: * Iface ID (nif) field in our Router-LSA, which is just nbr->iface_id.
! 1816: */
! 1817: link = ospf_hash_find(p->gr, ifa->iface_id, nif, rid, LSA_T_LINK);
! 1818: if (!link)
! 1819: return NULL;
! 1820:
! 1821: nh = link_lsa_lladdr(p, link);
! 1822: if (ipa_zero(nh))
! 1823: return NULL;
! 1824: }
! 1825:
! 1826: return new_nexthop(p, nh, ifa->iface, ifa->ecmp_weight);
! 1827: }
! 1828:
! 1829: /* The third case - bcast or nbma neighbor */
! 1830: if ((en->lsa_type == LSA_T_RT) && (par->lsa_type == LSA_T_NET))
! 1831: {
! 1832: /* par->nhi should be defined from parent's calc_next_hop() */
! 1833: if (!pn)
! 1834: goto bad;
! 1835:
! 1836: if (ospf_is_v2(p))
! 1837: {
! 1838: /*
! 1839: * In this case, next-hop is the same as link-back, which is
! 1840: * already computed in link_back().
! 1841: */
! 1842: if (ipa_zero(en->lb))
! 1843: goto bad;
! 1844:
! 1845: return new_nexthop(p, en->lb, pn->iface, pn->weight);
! 1846: }
! 1847: else /* OSPFv3 */
! 1848: {
! 1849: /*
! 1850: * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
! 1851: * is computed in link_back().
! 1852: */
! 1853: link = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
! 1854: if (!link)
! 1855: return NULL;
! 1856:
! 1857: nh = link_lsa_lladdr(p, link);
! 1858: if (ipa_zero(nh))
! 1859: return NULL;
! 1860:
! 1861: return new_nexthop(p, nh, pn->iface, pn->weight);
! 1862: }
! 1863: }
! 1864:
! 1865: bad:
! 1866: /* Probably bug or some race condition, we log it */
! 1867: log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
! 1868: return NULL;
! 1869: }
! 1870:
! 1871:
! 1872: /* Add LSA into list of candidates in Dijkstra's algorithm */
! 1873: static void
! 1874: add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par,
! 1875: u32 dist, int pos, uint data, uint lif, uint nif)
! 1876: {
! 1877: struct ospf_proto *p = oa->po;
! 1878: node *prev, *n;
! 1879: int added = 0;
! 1880: struct top_hash_entry *act;
! 1881:
! 1882: /* 16.1. (2b) */
! 1883: if (en == NULL)
! 1884: return;
! 1885: if (en->lsa.age == LSA_MAXAGE)
! 1886: return;
! 1887:
! 1888: if (ospf_is_v3(p) && (oa->options & OPT_V6) && (en->lsa_type == LSA_T_RT))
! 1889: {
! 1890: /* In OSPFv3 IPv6 unicast, check V6 flag */
! 1891: struct ospf_lsa_rt *rt = en->lsa_body;
! 1892: if (!(rt->options & OPT_V6))
! 1893: return;
! 1894: }
! 1895:
! 1896: /* 16.1. (2c) */
! 1897: if (en->color == INSPF)
! 1898: return;
! 1899:
! 1900: /* 16.1. (2d), also checks that dist < LSINFINITY */
! 1901: if (dist > en->dist)
! 1902: return;
! 1903:
! 1904: /* We should check whether there is a reverse link from en to par, */
! 1905: if (!link_back(oa, en, par, lif, nif))
! 1906: return;
! 1907:
! 1908: struct nexthop *nhs = calc_next_hop(oa, en, par, pos, data, lif, nif);
! 1909: if (!nhs)
! 1910: {
! 1911: log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
! 1912: p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
! 1913: return;
! 1914: }
! 1915:
! 1916: /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
! 1917: if ((dist == en->dist) && !nh_is_vlink(en->nhs))
! 1918: {
! 1919: /*
! 1920: * For multipath, we should merge nexthops. We merge regular nexthops only.
! 1921: * Dummy vlink nexthops are less preferred and handled as a special case.
! 1922: *
! 1923: * During merging, new nexthops (nhs) can be reused if they are not
! 1924: * inherited from the parent (i.e. they are allocated in calc_next_hop()).
! 1925: * Current nexthops (en->nhs) can be reused if they weren't inherited in
! 1926: * previous steps (that is stored in nhs_reuse, i.e. created by merging or
! 1927: * allocated in calc_next_hop()).
! 1928: *
! 1929: * Generally, a node first inherits shared nexthops from its parent and
! 1930: * later possibly gets reusable (private) copy during merging. This is more
! 1931: * or less same for both top_hash_entry nodes and orta nodes.
! 1932: *
! 1933: * Note that when a child inherits a private nexthop from its parent, it
! 1934: * should make the nexthop shared for both parent and child, while we only
! 1935: * update nhs_reuse for the child node. This makes nhs_reuse field for the
! 1936: * parent technically incorrect, but it is not a problem as parent's nhs
! 1937: * will not be modified (and nhs_reuse examined) afterwards.
! 1938: */
! 1939:
! 1940: /* Keep old ones */
! 1941: if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
! 1942: return;
! 1943:
! 1944: /* Merge old and new */
! 1945: int new_reuse = (par->nhs != nhs);
! 1946: en->nhs = nexthop_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
! 1947: en->nhs_reuse = 1;
! 1948: return;
! 1949: }
! 1950:
! 1951: DBG(" Adding candidate: rt: %R, id: %R, type: %u\n",
! 1952: en->lsa.rt, en->lsa.id, en->lsa_type);
! 1953:
! 1954: if (en->color == CANDIDATE)
! 1955: { /* We found a shorter path */
! 1956: rem_node(&en->cn);
! 1957: }
! 1958: en->nhs = nhs;
! 1959: en->dist = dist;
! 1960: en->color = CANDIDATE;
! 1961: en->nhs_reuse = (par->nhs != nhs);
! 1962:
! 1963: prev = NULL;
! 1964:
! 1965: if (EMPTY_LIST(oa->cand))
! 1966: {
! 1967: add_head(&oa->cand, &en->cn);
! 1968: }
! 1969: else
! 1970: {
! 1971: WALK_LIST(n, oa->cand)
! 1972: {
! 1973: act = SKIP_BACK(struct top_hash_entry, cn, n);
! 1974: if ((act->dist > dist) ||
! 1975: ((act->dist == dist) && (act->lsa_type == LSA_T_RT)))
! 1976: {
! 1977: if (prev == NULL)
! 1978: add_head(&oa->cand, &en->cn);
! 1979: else
! 1980: insert_node(&en->cn, prev);
! 1981: added = 1;
! 1982: break;
! 1983: }
! 1984: prev = n;
! 1985: }
! 1986:
! 1987: if (!added)
! 1988: {
! 1989: add_tail(&oa->cand, &en->cn);
! 1990: }
! 1991: }
! 1992: }
! 1993:
! 1994: static inline int
! 1995: ort_changed(ort *nf, rta *nr)
! 1996: {
! 1997: rta *or = nf->old_rta;
! 1998: return !or ||
! 1999: (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
! 2000: (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
! 2001: (nr->source != or->source) || (nr->dest != or->dest) ||
! 2002: !nexthop_same(&(nr->nh), &(or->nh));
! 2003: }
! 2004:
! 2005: static void
! 2006: rt_sync(struct ospf_proto *p)
! 2007: {
! 2008: struct top_hash_entry *en;
! 2009: struct fib_iterator fit;
! 2010: struct fib *fib = &p->rtf;
! 2011: struct ospf_area *oa;
! 2012:
! 2013: /* This is used for forced reload of routes */
! 2014: int reload = (p->calcrt == 2);
! 2015:
! 2016: OSPF_TRACE(D_EVENTS, "Starting routing table synchronization");
! 2017:
! 2018: DBG("Now syncing my rt table with nest's\n");
! 2019: FIB_ITERATE_INIT(&fit, fib);
! 2020: again1:
! 2021: FIB_ITERATE_START(fib, &fit, ort, nf)
! 2022: {
! 2023: /* Sanity check of next-hop addresses, failure should not happen */
! 2024: if (nf->n.type)
! 2025: {
! 2026: struct nexthop *nh;
! 2027: for (nh = nf->n.nhs; nh; nh = nh->next)
! 2028: if (ipa_nonzero(nh->gw))
! 2029: {
! 2030: neighbor *ng = neigh_find(&p->p, nh->gw, nh->iface, 0);
! 2031: if (!ng || (ng->scope == SCOPE_HOST))
! 2032: { reset_ri(nf); break; }
! 2033: }
! 2034: }
! 2035:
! 2036: /* Remove configured stubnets but keep the entries */
! 2037: if (nf->n.type && !nf->n.nhs)
! 2038: {
! 2039: reset_ri(nf);
! 2040: nf->keep = 1;
! 2041: }
! 2042:
! 2043: if (nf->n.type) /* Add the route */
! 2044: {
! 2045: rta a0 = {
! 2046: .src = p->p.main_source,
! 2047: .source = nf->n.type,
! 2048: .scope = SCOPE_UNIVERSE,
! 2049: .dest = RTD_UNICAST,
! 2050: .nh = *(nf->n.nhs),
! 2051: };
! 2052:
! 2053: if (reload || ort_changed(nf, &a0))
! 2054: {
! 2055: rta *a = rta_lookup(&a0);
! 2056: rte *e = rte_get_temp(a);
! 2057:
! 2058: rta_free(nf->old_rta);
! 2059: nf->old_rta = rta_clone(a);
! 2060: e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
! 2061: e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
! 2062: e->u.ospf.tag = nf->old_tag = nf->n.tag;
! 2063: e->u.ospf.router_id = nf->old_rid = nf->n.rid;
! 2064: e->pflags = EA_ID_FLAG(EA_OSPF_METRIC1) | EA_ID_FLAG(EA_OSPF_ROUTER_ID);
! 2065:
! 2066: if (nf->n.type == RTS_OSPF_EXT2)
! 2067: e->pflags |= EA_ID_FLAG(EA_OSPF_METRIC2);
! 2068:
! 2069: /* Perhaps onfly if tag is non-zero? */
! 2070: if ((nf->n.type == RTS_OSPF_EXT1) || (nf->n.type == RTS_OSPF_EXT2))
! 2071: e->pflags |= EA_ID_FLAG(EA_OSPF_TAG);
! 2072:
! 2073: DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
! 2074: a0.source, nf->fn.addr, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
! 2075: rte_update(&p->p, nf->fn.addr, e);
! 2076: }
! 2077: }
! 2078: else if (nf->old_rta)
! 2079: {
! 2080: /* Remove the route */
! 2081: rta_free(nf->old_rta);
! 2082: nf->old_rta = NULL;
! 2083:
! 2084: rte_update(&p->p, nf->fn.addr, NULL);
! 2085: }
! 2086:
! 2087: /* Remove unused rt entry, some special entries are persistent */
! 2088: if (!nf->n.type && !nf->external_rte && !nf->area_net && !nf->keep)
! 2089: {
! 2090: if (nf->lsa_id)
! 2091: idm_free(&p->idm, nf->lsa_id);
! 2092:
! 2093: FIB_ITERATE_PUT(&fit);
! 2094: fib_delete(fib, nf);
! 2095: goto again1;
! 2096: }
! 2097: }
! 2098: FIB_ITERATE_END;
! 2099:
! 2100:
! 2101: WALK_LIST(oa, p->area_list)
! 2102: {
! 2103: /* Cleanup ASBR hash tables */
! 2104: FIB_ITERATE_INIT(&fit, &oa->rtr);
! 2105: again2:
! 2106: FIB_ITERATE_START(&oa->rtr, &fit, ort, nf)
! 2107: {
! 2108: if (!nf->n.type)
! 2109: {
! 2110: FIB_ITERATE_PUT(&fit);
! 2111: fib_delete(&oa->rtr, nf);
! 2112: goto again2;
! 2113: }
! 2114: }
! 2115: FIB_ITERATE_END;
! 2116: }
! 2117:
! 2118: /* Cleanup stale LSAs */
! 2119: WALK_SLIST(en, p->lsal)
! 2120: if (en->mode == LSA_M_RTCALC_STALE)
! 2121: ospf_flush_lsa(p, en);
! 2122: }
! 2123:
! 2124:
! 2125: /* RFC 3623 2.2 - checking for graceful restart termination conditions */
! 2126: void
! 2127: ospf_update_gr_recovery(struct ospf_proto *p)
! 2128: {
! 2129: struct top_hash_entry *rt, *net, *nbr;
! 2130: struct ospf_lsa_rt_walk rtl;
! 2131: struct ospf_neighbor *n;
! 2132: struct ospf_iface *ifa;
! 2133: struct ospf_area *oa;
! 2134: const char *err_dsc = NULL;
! 2135: uint i, j, missing = 0, err_val = 0;
! 2136:
! 2137: /*
! 2138: * We check here for three cases:
! 2139: * RFC 3623 2.2 (1) - success when all adjacencies are established
! 2140: * RFC 3623 2.2 (2) - failure when inconsistent LSA was received
! 2141: * RFC 3623 2.2 (3) - grace period timeout
! 2142: *
! 2143: * It is handled by processing pre-restart local router-LSA and adjacent
! 2144: * network-LSAs, checking neighbor association for referenced routers (1)
! 2145: * and checking back links from their router-LSAs (2).
! 2146: *
! 2147: * TODO: Use timer for grace period timeout. We avoided that as function
! 2148: * ospf_stop_gr_recovery() called from ospf_disp() makes ending of graceful
! 2149: * restart uninterrupted by other events.
! 2150: */
! 2151:
! 2152: #define CONTINUE { missing++; continue; }
! 2153:
! 2154: if (current_time() > p->gr_timeout)
! 2155: goto timeout;
! 2156:
! 2157: WALK_LIST(oa, p->area_list)
! 2158: {
! 2159: /* Get the router-LSA */
! 2160: rt = oa->rt;
! 2161: if (!rt || (rt->lsa.age == LSA_MAXAGE))
! 2162: CONTINUE;
! 2163:
! 2164: for (lsa_walk_rt_init(p, rt, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
! 2165: {
! 2166: if (rtl.type == LSART_STUB)
! 2167: continue;
! 2168:
! 2169: ifa = rt_find_iface(oa, i, rtl.data, rtl.lif);
! 2170: if (!ifa)
! 2171: DROP("inconsistent interface", ospf_is_v2(p) ? rtl.data : rtl.lif);
! 2172:
! 2173: switch (rtl.type)
! 2174: {
! 2175: case LSART_NET:
! 2176: /* Find the network-LSA */
! 2177: net = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
! 2178: if (!net)
! 2179: CONTINUE;
! 2180:
! 2181: if (!link_back(oa, net, rt, rtl.lif, rtl.nif))
! 2182: DROP("Inconsistent network-LSA", net->lsa.id);
! 2183:
! 2184: if (ifa->state == OSPF_IS_DR)
! 2185: {
! 2186: /* Find all neighbors from the network-LSA */
! 2187: struct ospf_lsa_net *net_body = net->lsa_body;
! 2188: uint cnt = lsa_net_count(&net->lsa);
! 2189: for (j = 0; j < cnt; i++)
! 2190: {
! 2191: n = find_neigh(ifa, net_body->routers[j]);
! 2192: if (!n || (n->state != NEIGHBOR_FULL))
! 2193: CONTINUE;
! 2194:
! 2195: if (!n->got_my_rt_lsa)
! 2196: DROP("not received my router-LSA", n->rid);
! 2197:
! 2198: nbr = ospf_hash_find_rt(p->gr, oa->areaid, n->rid);
! 2199: if (!link_back(oa, nbr, net, 0, 0))
! 2200: DROP("inconsistent router-LSA", n->rid);
! 2201: }
! 2202: }
! 2203: else
! 2204: {
! 2205: /* Find the DR (by IP for OSPFv2) */
! 2206: n = ospf_is_v2(p) ?
! 2207: find_neigh_by_ip(ifa, ipa_from_u32(rtl.id)) :
! 2208: find_neigh(ifa, rtl.id);
! 2209: if (!n || (n->state != NEIGHBOR_FULL))
! 2210: CONTINUE;
! 2211:
! 2212: if (!n->got_my_rt_lsa)
! 2213: DROP("not received my router-LSA", n->rid);
! 2214: }
! 2215: break;
! 2216:
! 2217: case LSART_VLNK:
! 2218: case LSART_PTP:
! 2219: /* Find the PtP peer */
! 2220: n = find_neigh(ifa, rtl.id);
! 2221: if (!n || (n->state != NEIGHBOR_FULL))
! 2222: CONTINUE;
! 2223:
! 2224: if (!n->got_my_rt_lsa)
! 2225: DROP("not received my router-LSA", n->rid);
! 2226:
! 2227: nbr = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
! 2228: if (!link_back(oa, nbr, rt, rtl.lif, rtl.nif))
! 2229: DROP("inconsistent router-LSA", rtl.id);
! 2230: }
! 2231: }
! 2232: }
! 2233:
! 2234: #undef CONTINUE
! 2235:
! 2236: if (missing)
! 2237: return;
! 2238:
! 2239: OSPF_TRACE(D_EVENTS, "Graceful restart finished");
! 2240: ospf_stop_gr_recovery(p);
! 2241: return;
! 2242:
! 2243: drop:
! 2244: log(L_INFO "%s: Graceful restart ended - %s (%R)", p->p.name, err_dsc, err_val);
! 2245: ospf_stop_gr_recovery(p);
! 2246: return;
! 2247:
! 2248: timeout:
! 2249: log(L_INFO "%s: Graceful restart ended - grace period expired", p->p.name);
! 2250: ospf_stop_gr_recovery(p);
! 2251: return;
! 2252: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rt.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 / proto / ospf