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