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