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