]>
git.ipfire.org Git - thirdparty/bird.git/blob - proto/ospf/rt.c
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.
8 * Can be freely distributed and used under the terms of the GNU GPL.
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
);
17 static inline void reset_ri(ort
*ort
)
19 bzero(&ort
->n
, sizeof(orta
));
23 nh_is_vlink(struct nexthop
*nhs
)
29 unresolved_vlink(ort
*ort
)
31 return ort
->n
.nhs
&& nh_is_vlink(ort
->n
.nhs
);
34 static inline struct nexthop
*
35 new_nexthop(struct ospf_proto
*p
, ip_addr gw
, struct iface
*iface
, byte weight
)
37 struct nexthop
*nh
= lp_allocz(p
->nhpool
, sizeof(struct nexthop
));
44 /* Returns true if there are device nexthops in n */
46 has_device_nexthops(const struct nexthop
*n
)
48 for (; n
; n
= n
->next
)
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
)
59 struct nexthop
*root1
= NULL
;
60 struct nexthop
*root2
= NULL
;
61 struct nexthop
**nn1
= &root1
;
62 struct nexthop
**nn2
= &root2
;
65 return new_nexthop(p
, gw
, n
->iface
, n
->weight
);
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. */
71 for (; n
; n
= n
->next
)
73 struct nexthop
*nn
= new_nexthop(p
, ipa_zero(n
->gw
) ? gw
: n
->gw
, n
->iface
, n
->weight
);
87 return nexthop_merge(root1
, root2
, 1, 1, p
->ecmp
, p
->nhpool
);
91 /* Whether the ASBR or the forward address destination is preferred
92 in AS external route selection according to 16.4.1. */
94 epath_preferred(const orta
*ep
)
96 return (ep
->type
== RTS_OSPF
) && (ep
->oa
->areaid
!= 0);
99 /* Whether the ext route has ASBR/next_hop marked as preferred. */
101 orta_pref(const orta
*nf
)
103 return !!(nf
->options
& ORTA_PREF
);
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 */
109 orta_prio(const orta
*nf
)
111 /* RFC 3101 2.5 (6e) priorities */
112 u32 opts
= nf
->options
& (ORTA_NSSA
| ORTA_PROP
);
114 /* A Type-7 LSA with the P-bit set */
115 if (opts
== (ORTA_NSSA
| ORTA_PROP
))
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 */
128 orta_prefer_lsa(const orta
*new, const orta
*old
)
130 int pn
= orta_prio(new);
131 int po
= orta_prio(old
);
133 return (pn
> po
) || ((pn
== po
) && (new->en
->lsa
.rt
> old
->en
->lsa
.rt
));
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
143 orta_compare(const struct ospf_proto
*p
, const orta
*new, const orta
*old
)
147 if (old
->type
== RTS_DUMMY
)
150 /* Prefer intra-area to inter-area to externals */
151 r
= ((int) old
->type
) - ((int) new->type
);
154 /* Prefer lowest type 1 metric */
155 r
= ((int) old
->metric1
) - ((int) new->metric1
);
159 /* Rest is BIRD-specific */
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;
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. */
172 if (nh_is_vlink(new->nhs
))
174 if (nh_is_vlink(old
->nhs
))
181 /* Prefer routes with higher Router ID, just to be more deterministic */
182 if (new->rid
> old
->rid
)
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.
194 orta_compare_asbr(const struct ospf_proto
*p
, const orta
*new, const orta
*old
)
198 if (old
->type
== RTS_DUMMY
)
203 r
= epath_preferred(new) - epath_preferred(old
);
207 r
= ((int) old
->metric1
) - ((int) new->metric1
);
210 /* Larger area ID is preferred */
211 if (new->oa
->areaid
> old
->oa
->areaid
)
214 /* There is just one ASBR of that RID per area, so tie is not possible */
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.
224 orta_compare_ext(const struct ospf_proto
*p
, const orta
*new, const orta
*old
)
228 if (old
->type
== RTS_DUMMY
)
231 /* 16.4 (6a) - prefer routes with lower type */
232 r
= ((int) old
->type
) - ((int) new->type
);
235 /* 16.4 (6b) - prefer routes with lower type 2 metric */
236 if (new->type
== RTS_OSPF_EXT2
)
238 r
= ((int) old
->metric2
) - ((int) new->metric2
);
242 /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
245 r
= orta_pref(new) - orta_pref(old
);
249 /* 16.4 (6d) - prefer routes with lower type 1 metric */
250 r
= ((int) old
->metric1
) - ((int) new->metric1
);
254 if (p
->ecmp
&& p
->merge_external
)
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.
263 if (orta_prefer_lsa(new, old
))
271 ort_replace(ort
*o
, const orta
*new)
273 memcpy(&o
->n
, new, sizeof(orta
));
277 ort_merge(struct ospf_proto
*p
, ort
*o
, const orta
*new)
281 if (old
->nhs
!= new->nhs
)
283 old
->nhs
= nexthop_merge(old
->nhs
, new->nhs
, old
->nhs_reuse
, new->nhs_reuse
,
288 if (old
->rid
< new->rid
)
293 ort_merge_ext(struct ospf_proto
*p
, ort
*o
, const orta
*new)
297 if (old
->nhs
!= new->nhs
)
299 old
->nhs
= nexthop_merge(old
->nhs
, new->nhs
, old
->nhs_reuse
, new->nhs_reuse
,
304 if (old
->tag
!= new->tag
)
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).
313 if (orta_prefer_lsa(new, old
))
315 old
->options
= new->options
;
325 ri_install_net(struct ospf_proto
*p
, net_addr
*net
, const orta
*new)
327 ort
*old
= fib_get(&p
->rtf
, net
);
328 int cmp
= orta_compare(p
, new, &old
->n
);
331 ort_replace(old
, new);
333 ort_merge(p
, old
, new);
337 ri_install_rt(struct ospf_area
*oa
, u32 rid
, const orta
*new)
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
);
344 ort_replace(old
, new);
346 ort_merge(oa
->po
, old
, new);
350 ri_install_asbr(struct ospf_proto
*p
, u32 rid
, const orta
*new)
352 net_addr_ip4 nrid
= net_from_rid(rid
);
353 ort
*old
= fib_get(&p
->backbone
->rtr
, (net_addr
*) &nrid
);
355 if (orta_compare_asbr(p
, new, &old
->n
) > 0)
356 ort_replace(old
, new);
360 ri_install_ext(struct ospf_proto
*p
, net_addr
*net
, const orta
*new)
362 ort
*old
= fib_get(&p
->rtf
, net
);
363 int cmp
= orta_compare_ext(p
, new, &old
->n
);
366 ort_replace(old
, new);
368 ort_merge_ext(p
, old
, new);
371 static inline struct ospf_iface
*
372 rt_pos_to_ifa(struct ospf_area
*oa
, int pos
)
374 struct ospf_iface
*ifa
;
376 WALK_LIST(ifa
, oa
->po
->iface_list
)
377 if (ifa
->oa
== oa
&& pos
>= ifa
->rt_pos_beg
&& pos
< ifa
->rt_pos_end
)
383 static inline struct ospf_iface
*
384 px_pos_to_ifa(struct ospf_area
*oa
, int pos
)
386 struct ospf_iface
*ifa
;
388 WALK_LIST(ifa
, oa
->po
->iface_list
)
389 if (ifa
->oa
== oa
&& pos
>= ifa
->px_pos_beg
&& pos
< ifa
->px_pos_end
)
395 static inline struct ospf_iface
*
396 rt_find_iface2(struct ospf_area
*oa
, uint data
)
398 /* We should handle it differently for unnumbered PTP links */
399 struct ospf_iface
*ifa
;
400 WALK_LIST(ifa
, oa
->po
->iface_list
)
401 if ((ifa
->oa
== oa
) && ifa
->addr
&& (ospf_iface_get_data(ifa
) == data
))
407 static inline struct ospf_iface
*
408 rt_find_iface3(struct ospf_area
*oa
, uint lif
)
410 struct ospf_iface
*ifa
;
411 WALK_LIST(ifa
, oa
->po
->iface_list
)
412 if ((ifa
->oa
== oa
) && (ifa
->iface_id
== lif
))
418 static struct ospf_iface
*
419 rt_find_iface(struct ospf_area
*oa
, int pos
, uint data
, uint lif
)
422 * We can use both position based lookup (which is more reliable) and data/lif
423 * based lookup (which works even during graceful restart). We will prefer the
424 * first approach, but use the second one for GR-enabled instances.
427 if (oa
->po
->gr_mode
!= OSPF_GR_ABLE
)
428 return rt_pos_to_ifa(oa
, pos
);
430 return ospf_is_v2(oa
->po
) ? rt_find_iface2(oa
, data
) : rt_find_iface3(oa
, lif
);
435 add_network(struct ospf_area
*oa
, net_addr
*net
, int metric
, struct top_hash_entry
*en
, int pos
)
437 struct ospf_proto
*p
= oa
->po
;
448 if (!ospf_valid_prefix(net
))
450 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
451 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
458 * Local stub networks do not have proper iface in en->nhi (because they all
459 * have common top_hash_entry en). We have to find iface responsible for
460 * that stub network. Configured stubnets do not have any iface. They will
461 * be removed in rt_sync().
464 struct ospf_iface
*ifa
;
465 ifa
= ospf_is_v2(p
) ? rt_pos_to_ifa(oa
, pos
) : px_pos_to_ifa(oa
, pos
);
466 nf
.nhs
= ifa
? new_nexthop(p
, IPA_NONE
, ifa
->iface
, ifa
->ecmp_weight
) : NULL
;
469 ri_install_net(p
, net
, &nf
);
475 spfa_process_rt(struct ospf_proto
*p
, struct ospf_area
*oa
, struct top_hash_entry
*act
)
477 struct ospf_lsa_rt
*rt
= act
->lsa_body
;
478 struct ospf_lsa_rt_walk rtl
;
479 struct top_hash_entry
*tmp
;
482 if (rt
->options
& OPT_RT_V
)
486 * In OSPFv3, all routers are added to per-area routing
487 * tables. But we use it just for ASBRs and ABRs. For the
488 * purpose of the last step in SPF - prefix-LSA processing in
489 * spfa_process_prefixes(), we use information stored in LSA db.
491 if (((rt
->options
& OPT_RT_E
) || (rt
->options
& OPT_RT_B
))
492 && (act
->lsa
.rt
!= p
->router_id
))
496 .options
= rt
->options
,
497 .metric1
= act
->dist
,
502 ri_install_rt(oa
, act
->lsa
.rt
, &nf
);
505 /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
506 if (ospf_is_v3(p
) && (act
!= oa
->rt
) && !(rt
->options
& OPT_R
))
509 /* Now process Rt links */
510 for (lsa_walk_rt_init(p
, act
, &rtl
), i
= 0; lsa_walk_rt(&rtl
); i
++)
518 /* Should not happen, LSART_STUB is not defined in OSPFv3 */
523 * RFC 2328 in 16.1. (2a) says to handle stub networks in an
524 * second phase after the SPF for an area is calculated. We get
525 * the same result by handing them here because add_network()
526 * will keep the best (not the first) found route.
529 NET_ADDR_IP4(ip4_from_u32(rtl
.id
& rtl
.data
), u32_masklen(rtl
.data
));
531 add_network(oa
, (net_addr
*) &net
, act
->dist
+ rtl
.metric
, act
, i
);
535 tmp
= ospf_hash_find_net(p
->gr
, oa
->areaid
, rtl
.id
, rtl
.nif
);
540 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, rtl
.id
);
544 add_cand(oa
, tmp
, act
, act
->dist
+ rtl
.metric
, i
, rtl
.data
, rtl
.lif
, rtl
.nif
);
549 spfa_process_net(struct ospf_proto
*p
, struct ospf_area
*oa
, struct top_hash_entry
*act
)
551 struct ospf_lsa_net
*ln
= act
->lsa_body
;
552 struct top_hash_entry
*tmp
;
558 NET_ADDR_IP4(ip4_from_u32(act
->lsa
.id
& ln
->optx
), u32_masklen(ln
->optx
));
560 add_network(oa
, (net_addr
*) &net
, act
->dist
, act
, -1);
563 cnt
= lsa_net_count(&act
->lsa
);
564 for (i
= 0; i
< cnt
; i
++)
566 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, ln
->routers
[i
]);
567 add_cand(oa
, tmp
, act
, act
->dist
, -1, 0, 0, 0);
572 spfa_process_prefixes(struct ospf_proto
*p
, struct ospf_area
*oa
)
574 struct top_hash_entry
*en
, *src
;
575 struct ospf_lsa_prefix
*px
;
579 WALK_SLIST(en
, p
->lsal
)
581 if (en
->lsa_type
!= LSA_T_PREFIX
)
584 if (en
->domain
!= oa
->areaid
)
587 if (en
->lsa
.age
== LSA_MAXAGE
)
592 /* For router prefix-LSA, we would like to find the first router-LSA */
593 if (px
->ref_type
== LSA_T_RT
)
594 src
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, px
->ref_rt
);
596 src
= ospf_hash_find(p
->gr
, oa
->areaid
, px
->ref_id
, px
->ref_rt
, px
->ref_type
);
601 /* Reachable in SPF */
602 if (src
->color
!= INSPF
)
605 if ((src
->lsa_type
!= LSA_T_RT
) && (src
->lsa_type
!= LSA_T_NET
))
609 for (i
= 0; i
< px
->pxcount
; i
++)
615 buf
= ospf3_get_prefix(buf
, ospf_get_af(p
), &net
, &pxopts
, &metric
);
617 if (pxopts
& OPT_PX_NU
)
620 /* Store the first global address to use it later as a vlink endpoint */
621 if ((pxopts
& OPT_PX_LA
) && (net
.type
== NET_IP6
) && ipa_zero(src
->lb
))
622 src
->lb
= ipa_from_ip6(net6_prefix(&net
));
624 add_network(oa
, &net
, src
->dist
+ metric
, src
, i
);
629 /* RFC 2328 16.1. calculating shortest paths for an area */
631 ospf_rt_spfa(struct ospf_area
*oa
)
633 struct ospf_proto
*p
= oa
->po
;
634 struct top_hash_entry
*act
;
639 if (oa
->rt
->lsa
.age
== LSA_MAXAGE
)
642 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation for area %R", oa
->areaid
);
645 init_list(&oa
->cand
); /* Empty list of candidates */
648 DBG("LSA db prepared, adding me into candidate list.\n");
651 oa
->rt
->color
= CANDIDATE
;
652 add_head(&oa
->cand
, &oa
->rt
->cn
);
653 DBG("RT LSA: rt: %R, id: %R, type: %u\n",
654 oa
->rt
->lsa
.rt
, oa
->rt
->lsa
.id
, oa
->rt
->lsa_type
);
656 while (!EMPTY_LIST(oa
->cand
))
659 act
= SKIP_BACK(struct top_hash_entry
, cn
, n
);
662 DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
663 act
->lsa
.rt
, act
->lsa
.id
, act
->lsa_type
);
666 switch (act
->lsa_type
)
669 spfa_process_rt(p
, oa
, act
);
673 spfa_process_net(p
, oa
, act
);
677 log(L_WARN
"%s: Unknown LSA type in SPF: %d", p
->p
.name
, act
->lsa_type
);
682 spfa_process_prefixes(p
, oa
);
686 link_back(struct ospf_area
*oa
, struct top_hash_entry
*en
,
687 struct top_hash_entry
*par
, uint lif
, uint nif
)
689 struct ospf_proto
*p
= oa
->po
;
690 struct ospf_lsa_rt_walk rtl
;
691 struct top_hash_entry
*tmp
;
692 struct ospf_lsa_net
*ln
;
695 if (!en
|| !par
) return 0;
697 /* We should check whether there is a link back from en to par,
698 this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
699 note 23, we don't have to find the same link that is used for par
700 to en, any link is enough. This we do for ptp links. For net-rt
701 links, we have to find the same link to compute proper lb/lb_id,
702 which may be later used as the next hop. */
704 /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
705 it is set in process_prefixes() to any global address in the area */
710 switch (en
->lsa_type
)
713 lsa_walk_rt_init(p
, en
, &rtl
);
714 while (lsa_walk_rt(&rtl
))
722 tmp
= ospf_hash_find_net(p
->gr
, oa
->areaid
, rtl
.id
, rtl
.nif
);
726 * Note that there may be multiple matching Rt-fields if router 'en'
727 * have multiple interfaces to net 'par'. Perhaps we should do ECMP.
730 en
->lb
= ipa_from_u32(rtl
.data
);
741 * For OSPFv2, not necessary the same link, see RFC 2328 [23].
742 * For OSPFv3, we verify that by comparing nif and lif fields.
744 if (ospf_is_v3(p
) && ((rtl
.lif
!= nif
) || (rtl
.nif
!= lif
)))
747 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, rtl
.id
);
757 cnt
= lsa_net_count(&en
->lsa
);
758 for (i
= 0; i
< cnt
; i
++)
760 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, ln
->routers
[i
]);
767 log(L_WARN
"%s: Unknown LSA type in SPF: %d", p
->p
.name
, en
->lsa_type
);
773 /* RFC 2328 16.2. calculating inter-area routes */
775 ospf_rt_sum(struct ospf_area
*oa
)
777 struct ospf_proto
*p
= oa
->po
;
778 struct top_hash_entry
*en
;
780 u32 dst_rid
, metric
, options
;
785 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation for inter-area (area %R)", oa
->areaid
);
787 WALK_SLIST(en
, p
->lsal
)
789 if ((en
->lsa_type
!= LSA_T_SUM_RT
) && (en
->lsa_type
!= LSA_T_SUM_NET
))
792 if (en
->domain
!= oa
->areaid
)
796 if (en
->lsa
.age
== LSA_MAXAGE
)
800 if (en
->lsa
.rt
== p
->router_id
)
803 /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */
805 if (en
->lsa_type
== LSA_T_SUM_NET
)
807 lsa_parse_sum_net(en
, ospf_is_v2(p
), ospf_get_af(p
), &net
, &pxopts
, &metric
);
809 if (!ospf_valid_prefix(&net
))
811 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
812 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
816 if (pxopts
& OPT_PX_NU
)
819 /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
820 if (p
->vpn_pe
&& (pxopts
& OPT_PX_DN
))
826 else /* LSA_T_SUM_RT */
828 lsa_parse_sum_rt(en
, ospf_is_v2(p
), &dst_rid
, &metric
, &options
);
830 /* We don't want local router in ASBR routing table */
831 if (dst_rid
== p
->router_id
)
834 options
|= ORTA_ASBR
;
839 if (metric
== LSINFINITY
)
843 net_addr_ip4 nrid
= net_from_rid(en
->lsa
.rt
);
844 abr
= fib_find(&oa
->rtr
, (net_addr
*) &nrid
);
845 if (!abr
|| !abr
->n
.type
)
848 if (!(abr
->n
.options
& ORTA_ABR
))
851 /* This check is not mentioned in RFC 2328 */
852 if (abr
->n
.type
!= RTS_OSPF
)
859 .metric1
= abr
->n
.metric1
+ metric
,
860 .rid
= en
->lsa
.rt
, /* ABR ID */
866 ri_install_net(p
, &net
, &nf
);
868 ri_install_rt(oa
, dst_rid
, &nf
);
872 /* RFC 2328 16.3. examining summary-LSAs in transit areas */
874 ospf_rt_sum_tr(struct ospf_area
*oa
)
876 struct ospf_proto
*p
= oa
->po
;
877 struct ospf_area
*bb
= p
->backbone
;
878 struct top_hash_entry
*en
;
885 WALK_SLIST(en
, p
->lsal
)
887 if ((en
->lsa_type
!= LSA_T_SUM_RT
) && (en
->lsa_type
!= LSA_T_SUM_NET
))
890 if (en
->domain
!= oa
->areaid
)
894 if (en
->lsa
.age
== LSA_MAXAGE
)
898 if (en
->lsa
.rt
== p
->router_id
)
901 if (en
->lsa_type
== LSA_T_SUM_NET
)
906 lsa_parse_sum_net(en
, ospf_is_v2(p
), ospf_get_af(p
), &net
, &pxopts
, &metric
);
908 if (!ospf_valid_prefix(&net
))
910 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
911 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
915 if (pxopts
& OPT_PX_NU
)
918 /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
919 if (p
->vpn_pe
&& (pxopts
& OPT_PX_DN
))
922 re
= fib_find(&p
->rtf
, &net
);
924 else // en->lsa_type == LSA_T_SUM_RT
926 u32 dst_rid
, options
;
928 lsa_parse_sum_rt(en
, ospf_is_v2(p
), &dst_rid
, &metric
, &options
);
930 net_addr_ip4 nrid
= net_from_rid(dst_rid
);
931 re
= fib_find(&bb
->rtr
, (net_addr
*) &nrid
);
935 if (metric
== LSINFINITY
)
939 if (!re
|| !re
->n
.type
)
942 if (re
->n
.oa
->areaid
!= 0)
945 if ((re
->n
.type
!= RTS_OSPF
) && (re
->n
.type
!= RTS_OSPF_IA
))
949 net_addr_ip4 nrid
= net_from_rid(en
->lsa
.rt
);
950 abr
= fib_find(&oa
->rtr
, (net_addr
*) &nrid
);
951 if (!abr
|| !abr
->n
.type
)
954 metric
= abr
->n
.metric1
+ metric
; /* IAC */
957 if ((metric
< re
->n
.metric1
) ||
958 ((metric
== re
->n
.metric1
) && unresolved_vlink(re
)))
960 /* We want to replace the next-hop even if the metric is equal
961 to replace a virtual next-hop through vlink with a real one.
962 Proper ECMP would merge nexthops here, but we do not do that.
963 We restrict nexthops to fit one area to simplify check
964 12.4.3 p4 in decide_sum_lsa() */
966 re
->n
.metric1
= metric
;
968 re
->n
.nhs
= abr
->n
.nhs
;
973 /* Decide about originating or flushing summary LSAs for condensed area networks */
975 decide_anet_lsa(struct ospf_area
*oa
, struct area_net
*anet
, struct ospf_area
*anet_oa
)
977 /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
978 if (!oa_is_ext(oa
) && !oa
->ac
->summary
)
984 /* Do not condense routing info when exporting from backbone to the transit area */
985 if ((anet_oa
== oa
->po
->backbone
) && oa
->trcap
)
988 return (anet
->active
&& !anet
->hidden
);
991 /* Decide about originating or flushing summary LSAs (12.4.3) */
993 decide_sum_lsa(struct ospf_area
*oa
, ort
*nf
, int dest
)
995 /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
996 if (!oa_is_ext(oa
) && !oa
->ac
->summary
)
999 /* Invalid field - no route */
1004 if (nf
->n
.type
> RTS_OSPF_IA
)
1008 if ((nf
->n
.oa
->areaid
== oa
->areaid
))
1012 if (nf
->n
.voa
&& (nf
->n
.voa
->areaid
== oa
->areaid
))
1016 if (nf
->n
.metric1
>= LSINFINITY
)
1019 /* 12.4.3 p6 - AS boundary router */
1020 if (dest
== ORT_ROUTER
)
1022 /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
1024 return oa_is_ext(oa
) && (nf
->n
.options
& ORTA_ASBR
);
1027 /* 12.4.3 p7 - inter-area route */
1028 if (nf
->n
.type
== RTS_OSPF_IA
)
1030 /* Inter-area routes are not repropagated into the backbone */
1031 return (oa
!= oa
->po
->backbone
);
1034 /* 12.4.3 p8 - intra-area route */
1036 /* Do not condense routing info when exporting from backbone to the transit area */
1037 if ((nf
->n
.oa
== oa
->po
->backbone
) && oa
->trcap
)
1040 struct area_net
*anet
= (struct area_net
*)
1041 fib_route(&nf
->n
.oa
->net_fib
, nf
->fn
.addr
);
1043 /* Condensed area network found */
1050 /* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1052 check_sum_net_lsa(struct ospf_proto
*p
, ort
*nf
)
1054 struct area_net
*anet
= NULL
;
1055 struct ospf_area
*anet_oa
= NULL
;
1059 /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1060 if (nf
->fn
.addr
->pxlen
== 0)
1063 /* Find that area network */
1064 WALK_LIST(anet_oa
, p
->area_list
)
1066 anet
= fib_find(&anet_oa
->net_fib
, nf
->fn
.addr
);
1072 struct ospf_area
*oa
;
1073 WALK_LIST(oa
, p
->area_list
)
1075 if (anet
&& decide_anet_lsa(oa
, anet
, anet_oa
))
1076 ospf_originate_sum_net_lsa(p
, oa
, nf
, anet
->metric
);
1077 else if (decide_sum_lsa(oa
, nf
, ORT_NET
))
1078 ospf_originate_sum_net_lsa(p
, oa
, nf
, nf
->n
.metric1
);
1083 check_sum_rt_lsa(struct ospf_proto
*p
, ort
*nf
)
1085 u32 rid
= rid_from_net(nf
->fn
.addr
);
1087 struct ospf_area
*oa
;
1088 WALK_LIST(oa
, p
->area_list
)
1089 if (decide_sum_lsa(oa
, nf
, ORT_ROUTER
))
1090 ospf_originate_sum_rt_lsa(p
, oa
, rid
, nf
->n
.metric1
, nf
->n
.options
);
1094 decide_nssa_lsa(struct ospf_proto
*p
, ort
*nf
, struct ospf_lsa_ext_local
*rt
)
1096 struct ospf_area
*oa
= nf
->n
.oa
;
1097 struct top_hash_entry
*en
= nf
->n
.en
;
1099 if (!rt_is_nssa(nf
) || !oa
->translate
)
1102 /* Condensed area network found */
1103 if (fib_route(&oa
->enet_fib
, nf
->fn
.addr
))
1106 if (!en
|| (en
->lsa_type
!= LSA_T_NSSA
))
1109 /* We do not store needed data in struct orta, we have to parse the LSA */
1110 lsa_parse_ext(en
, ospf_is_v2(p
), ospf_get_af(p
), rt
);
1112 if (rt
->pxopts
& OPT_PX_NU
)
1115 if (!rt
->propagate
|| ipa_zero(rt
->fwaddr
))
1121 /* RFC 3101 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1123 check_nssa_lsa(struct ospf_proto
*p
, ort
*nf
)
1125 struct area_net
*anet
= NULL
;
1126 struct ospf_area
*oa
= NULL
;
1127 struct ospf_lsa_ext_local rt
;
1129 /* Do not translate LSA if there is already the external LSA from route export */
1130 if (nf
->external_rte
)
1135 /* Find that area network */
1136 WALK_LIST(oa
, p
->area_list
)
1138 anet
= fib_find(&oa
->enet_fib
, nf
->fn
.addr
);
1144 /* RFC 3101 3.2 (3) - originate the aggregated address range */
1145 if (anet
&& anet
->active
&& !anet
->hidden
&& oa
->translate
)
1146 ospf_originate_ext_lsa(p
, NULL
, nf
, LSA_M_RTCALC
, anet
->metric
,
1147 (anet
->metric
& LSA_EXT3_EBIT
), IPA_NONE
, anet
->tag
, 0, 0);
1149 /* RFC 3101 3.2 (2) - originate the same network */
1150 else if (decide_nssa_lsa(p
, nf
, &rt
))
1151 ospf_originate_ext_lsa(p
, NULL
, nf
, LSA_M_RTCALC
, rt
.metric
, rt
.ebit
, rt
.fwaddr
, rt
.tag
, 0, 0);
1154 /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1156 ospf_check_vlinks(struct ospf_proto
*p
)
1158 struct ospf_iface
*ifa
;
1159 WALK_LIST(ifa
, p
->iface_list
)
1161 if (ifa
->type
== OSPF_IT_VLINK
)
1163 struct top_hash_entry
*tmp
;
1164 tmp
= ospf_hash_find_rt(p
->gr
, ifa
->voa
->areaid
, ifa
->vid
);
1166 if (tmp
&& (tmp
->color
== INSPF
) && ipa_nonzero(tmp
->lb
) && tmp
->nhs
)
1168 struct ospf_iface
*nhi
= ospf_iface_find(p
, tmp
->nhs
->iface
);
1170 if ((ifa
->state
!= OSPF_IS_PTP
)
1171 || (ifa
->vifa
!= nhi
)
1172 || !ipa_equal(ifa
->vip
, tmp
->lb
))
1174 OSPF_TRACE(D_EVENTS
, "Vlink peer %R found", ifa
->vid
);
1175 ospf_iface_sm(ifa
, ISM_DOWN
);
1177 ifa
->addr
= nhi
->addr
;
1178 ifa
->cost
= tmp
->dist
;
1180 ospf_iface_sm(ifa
, ISM_UP
);
1182 else if ((ifa
->state
== OSPF_IS_PTP
) && (ifa
->cost
!= tmp
->dist
))
1184 ifa
->cost
= tmp
->dist
;
1186 /* RFC 2328 12.4 Event 8 - vlink state change */
1187 ospf_notify_rt_lsa(ifa
->oa
);
1192 if (ifa
->state
> OSPF_IS_DOWN
)
1194 OSPF_TRACE(D_EVENTS
, "Vlink peer %R lost", ifa
->vid
);
1195 ospf_iface_sm(ifa
, ISM_DOWN
);
1203 /* Miscellaneous route processing that needs to be done by ABRs */
1205 ospf_rt_abr1(struct ospf_proto
*p
)
1207 struct area_net
*anet
;
1209 net_addr default_net
;
1211 /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1212 FIB_WALK(&p
->backbone
->rtr
, ort
, nf
)
1214 if (nf
->n
.type
&& unresolved_vlink(nf
))
1220 FIB_WALK(&p
->rtf
, ort
, nf
)
1222 /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1223 if (nf
->n
.type
&& unresolved_vlink(nf
))
1227 /* Compute condensed area networks */
1228 if (nf
->n
.type
== RTS_OSPF
)
1230 anet
= (struct area_net
*) fib_route(&nf
->n
.oa
->net_fib
, nf
->fn
.addr
);
1237 /* Get a RT entry and mark it to know that it is an area network */
1238 ort
*nfi
= fib_get(&p
->rtf
, anet
->fn
.addr
);
1242 if (nfi
->n
.type
== RTS_OSPF_IA
)
1246 if (anet
->metric
< nf
->n
.metric1
)
1247 anet
->metric
= nf
->n
.metric1
;
1255 net_fill_ip4(&default_net
, IP4_NONE
, 0);
1257 net_fill_ip6(&default_net
, IP6_NONE
, 0);
1259 default_nf
= fib_get(&p
->rtf
, &default_net
);
1260 default_nf
->area_net
= 1;
1262 struct ospf_area
*oa
;
1263 WALK_LIST(oa
, p
->area_list
)
1266 /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
1267 if (oa_is_stub(oa
) || (oa_is_nssa(oa
) && !oa
->ac
->summary
))
1268 ospf_originate_sum_net_lsa(p
, oa
, default_nf
, oa
->ac
->default_cost
);
1271 * Originate type-7 default route for NSSA areas
1273 * Because type-7 default LSAs are originated by ABRs, they do not
1274 * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1275 * for both external route export or external-NSSA translation),
1276 * so we use 0 for the src arg.
1279 if (oa_is_nssa(oa
) && oa
->ac
->default_nssa
)
1280 ospf_originate_ext_lsa(p
, oa
, default_nf
, LSA_M_RTCALC
, oa
->ac
->default_cost
,
1281 (oa
->ac
->default_cost
& LSA_EXT3_EBIT
), IPA_NONE
, 0, 0, 0);
1283 /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1286 FIB_WALK(&oa
->rtr
, ort
, nf
)
1288 if (nf
->n
.options
& ORTA_ASBR
)
1289 ri_install_asbr(p
, rid_from_net(nf
->fn
.addr
), &nf
->n
);
1296 /* Originate or flush ASBR summary LSAs */
1297 FIB_WALK(&p
->backbone
->rtr
, ort
, nf
)
1299 check_sum_rt_lsa(p
, nf
);
1304 /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1305 ospf_check_vlinks(p
);
1310 translator_timer_hook(timer
*timer
)
1312 struct ospf_area
*oa
= timer
->data
;
1314 if (oa
->translate
!= TRANS_WAIT
)
1317 oa
->translate
= TRANS_OFF
;
1318 ospf_schedule_rtcalc(oa
->po
);
1322 ospf_rt_abr2(struct ospf_proto
*p
)
1324 struct ospf_area
*oa
;
1325 struct top_hash_entry
*en
;
1327 /* RFC 3101 3.1 - type-7 translator election */
1328 struct ospf_area
*bb
= p
->backbone
;
1329 WALK_LIST(oa
, p
->area_list
)
1334 if (oa
->ac
->translator
)
1337 FIB_WALK(&oa
->rtr
, ort
, nf
)
1339 if (!nf
->n
.type
|| !(nf
->n
.options
& ORTA_ABR
))
1342 ort
*nf2
= fib_find(&bb
->rtr
, nf
->fn
.addr
);
1343 if (!nf2
|| !nf2
->n
.type
|| !(nf2
->n
.options
& ORTA_ABR
))
1346 en
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, nf
->n
.rid
);
1347 if (!en
|| (en
->color
!= INSPF
))
1350 struct ospf_lsa_rt
*rt
= en
->lsa_body
;
1351 /* There is better candidate - Nt-bit or higher Router ID */
1352 if ((rt
->options
& OPT_RT_NT
) || (p
->router_id
< nf
->n
.rid
))
1361 if (translate
&& (oa
->translate
!= TRANS_ON
))
1363 if (oa
->translate
== TRANS_WAIT
)
1364 tm_stop(oa
->translator_timer
);
1366 oa
->translate
= TRANS_ON
;
1369 if (!translate
&& (oa
->translate
== TRANS_ON
))
1371 if (oa
->translator_timer
== NULL
)
1372 oa
->translator_timer
= tm_new_init(p
->p
.pool
, translator_timer_hook
, oa
, 0, 0);
1374 /* Schedule the end of translation */
1375 tm_start(oa
->translator_timer
, oa
->ac
->transint S
);
1376 oa
->translate
= TRANS_WAIT
;
1381 /* Compute condensed external networks */
1382 FIB_WALK(&p
->rtf
, ort
, nf
)
1384 if (rt_is_nssa(nf
) && (nf
->n
.options
& ORTA_PROP
))
1386 struct area_net
*anet
= fib_route(&nf
->n
.oa
->enet_fib
, nf
->fn
.addr
);
1394 /* Get a RT entry and mark it to know that it is an area network */
1395 ort
*nf2
= fib_get(&p
->rtf
, anet
->fn
.addr
);
1399 u32 metric
= (nf
->n
.type
== RTS_OSPF_EXT1
) ?
1400 nf
->n
.metric1
: ((nf
->n
.metric2
+ 1) | LSA_EXT3_EBIT
);
1402 if (anet
->metric
< metric
)
1403 anet
->metric
= metric
;
1410 FIB_WALK(&p
->rtf
, ort
, nf
)
1412 check_sum_net_lsa(p
, nf
);
1413 check_nssa_lsa(p
, nf
);
1419 /* Like fib_route(), but ignores dummy rt entries */
1421 ospf_fib_route_ip4(struct fib
*f
, ip4_addr a
, int len
)
1423 net_addr_ip4 net
= NET_ADDR_IP4(a
, len
);
1427 nf
= fib_find(f
, (net_addr
*) &net
);
1428 if (nf
&& nf
->n
.type
)
1434 ip4_clrbit(&net
.prefix
, net
.pxlen
);
1442 ospf_fib_route_ip6(struct fib
*f
, ip6_addr a
, int len
)
1444 net_addr_ip6 net
= NET_ADDR_IP6(a
, len
);
1448 nf
= fib_find(f
, (net_addr
*) &net
);
1449 if (nf
&& nf
->n
.type
)
1455 ip6_clrbit(&net
.prefix
, net
.pxlen
);
1463 ospf_fib_route(struct fib
*f
, ip_addr a
)
1465 if (f
->addr_type
== NET_IP4
)
1466 return ospf_fib_route_ip4(f
, ipa_to_ip4(a
), IP4_MAX_PREFIX_LENGTH
);
1468 return ospf_fib_route_ip6(f
, ipa_to_ip6(a
), IP6_MAX_PREFIX_LENGTH
);
1472 /* RFC 2328 16.4. calculating external routes */
1474 ospf_ext_spf(struct ospf_proto
*p
)
1476 struct top_hash_entry
*en
;
1477 struct ospf_lsa_ext_local rt
;
1480 struct ospf_area
*atmp
;
1482 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation for ext routes");
1484 WALK_SLIST(en
, p
->lsal
)
1489 if ((en
->lsa_type
!= LSA_T_EXT
) && (en
->lsa_type
!= LSA_T_NSSA
))
1492 if (en
->lsa
.age
== LSA_MAXAGE
)
1496 if (en
->lsa
.rt
== p
->router_id
)
1499 DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
1500 p
->p
.name
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa_type
);
1502 lsa_parse_ext(en
, ospf_is_v2(p
), ospf_get_af(p
), &rt
);
1504 if (!ospf_valid_prefix(&rt
.net
))
1506 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1507 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
1511 if (rt
.metric
== LSINFINITY
)
1514 if (rt
.pxopts
& OPT_PX_NU
)
1517 /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
1518 if (p
->vpn_pe
&& rt
.downwards
)
1522 /* If there are more areas, we already precomputed preferred ASBR
1523 entries in ospf_rt_abr1() and stored them in the backbone
1524 table. For NSSA, we examine the area to which the LSA is assigned */
1525 if (en
->lsa_type
== LSA_T_EXT
)
1526 atmp
= ospf_main_area(p
);
1528 atmp
= ospf_find_area(p
, en
->domain
);
1531 continue; /* Should not happen */
1533 net_addr_ip4 nrid
= net_from_rid(en
->lsa
.rt
);
1534 nf1
= fib_find(&atmp
->rtr
, (net_addr
*) &nrid
);
1536 if (!nf1
|| !nf1
->n
.type
)
1537 continue; /* No AS boundary router found */
1539 if (!(nf1
->n
.options
& ORTA_ASBR
))
1540 continue; /* It is not ASBR */
1542 /* 16.4. (3) NSSA - special rule for default routes */
1543 /* ABR should use default only if P-bit is set and summaries are active */
1544 if ((en
->lsa_type
== LSA_T_NSSA
) && (rt
.net
.pxlen
== 0) &&
1545 (p
->areano
> 1) && !(rt
.propagate
&& atmp
->ac
->summary
))
1551 nfa
.nhs
= nf1
->n
.nhs
;
1552 br_metric
= nf1
->n
.metric1
;
1556 nf2
= ospf_fib_route(&p
->rtf
, rt
.fwaddr
);
1560 if (en
->lsa_type
== LSA_T_EXT
)
1562 /* For ext routes, we accept intra-area or inter-area routes */
1563 if ((nf2
->n
.type
!= RTS_OSPF
) && (nf2
->n
.type
!= RTS_OSPF_IA
))
1568 /* For NSSA routes, we accept just intra-area in the same area */
1569 if ((nf2
->n
.type
!= RTS_OSPF
) || (nf2
->n
.oa
!= atmp
))
1573 /* Next-hop is a part of a configured stubnet */
1577 nfa
.nhs
= nf2
->n
.nhs
;
1578 br_metric
= nf2
->n
.metric1
;
1580 /* Replace device nexthops with nexthops to forwarding address from LSA */
1581 if (has_device_nexthops(nfa
.nhs
))
1583 nfa
.nhs
= fix_device_nexthops(p
, nfa
.nhs
, rt
.fwaddr
);
1590 nfa
.type
= RTS_OSPF_EXT2
;
1591 nfa
.metric1
= br_metric
;
1592 nfa
.metric2
= rt
.metric
;
1596 nfa
.type
= RTS_OSPF_EXT1
;
1597 nfa
.metric1
= br_metric
+ rt
.metric
;
1601 /* Mark the LSA as reachable */
1604 /* Whether the route is preferred in route selection according to 16.4.1 */
1605 nfa
.options
= epath_preferred(&nf2
->n
) ? ORTA_PREF
: 0;
1606 if (en
->lsa_type
== LSA_T_NSSA
)
1608 nfa
.options
|= ORTA_NSSA
;
1610 nfa
.options
|= ORTA_PROP
;
1614 nfa
.rid
= en
->lsa
.rt
;
1615 nfa
.oa
= atmp
; /* undefined in RFC 2328 */
1616 nfa
.en
= en
; /* store LSA for later (NSSA processing) */
1618 ri_install_ext(p
, &rt
.net
, &nfa
);
1622 /* Cleanup of routing tables and data */
1624 ospf_rt_reset(struct ospf_proto
*p
)
1626 struct ospf_area
*oa
;
1627 struct top_hash_entry
*en
;
1629 /* Reset old routing table */
1630 FIB_WALK(&p
->rtf
, ort
, ri
)
1638 /* Reset SPF data in LSA db */
1639 WALK_SLIST(en
, p
->lsal
)
1642 en
->dist
= LSINFINITY
;
1646 if (en
->mode
== LSA_M_RTCALC
)
1647 en
->mode
= LSA_M_RTCALC_STALE
;
1650 WALK_LIST(oa
, p
->area_list
)
1652 /* Reset ASBR routing tables */
1653 FIB_WALK(&oa
->rtr
, ort
, ri
)
1659 /* Reset condensed area networks */
1662 FIB_WALK(&oa
->net_fib
, struct area_net
, anet
)
1669 FIB_WALK(&oa
->enet_fib
, struct area_net
, anet
)
1680 * ospf_rt_spf - calculate internal routes
1681 * @p: OSPF protocol instance
1683 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1684 * It's based on Dijkstra's shortest path tree algorithms.
1685 * This function is invoked from ospf_disp().
1688 ospf_rt_spf(struct ospf_proto
*p
)
1690 struct ospf_area
*oa
;
1695 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation");
1701 WALK_LIST(oa
, p
->area_list
)
1705 ospf_rt_sum(ospf_main_area(p
));
1708 WALK_LIST(oa
, p
->area_list
)
1709 if (oa
->trcap
&& (oa
->areaid
!= 0))
1722 lp_flush(p
->nhpool
);
1729 inherit_nexthops(struct nexthop
*pn
)
1731 /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1732 return pn
&& (ipa_nonzero(pn
->gw
) || !pn
->iface
);
1735 static inline ip_addr
1736 link_lsa_lladdr(struct ospf_proto
*p
, struct top_hash_entry
*en
)
1738 struct ospf_lsa_link
*link_lsa
= en
->lsa_body
;
1739 ip6_addr ll
= link_lsa
->lladdr
;
1744 return ospf_is_ip4(p
) ? ipa_from_ip4(ospf3_6to4(ll
)) : ipa_from_ip6(ll
);
1747 static struct nexthop
*
1748 calc_next_hop(struct ospf_area
*oa
, struct top_hash_entry
*en
,
1749 struct top_hash_entry
*par
, int pos
, uint data
, uint lif
, uint nif
)
1751 struct ospf_proto
*p
= oa
->po
;
1752 struct nexthop
*pn
= par
->nhs
;
1753 struct top_hash_entry
*link
= NULL
;
1754 struct ospf_iface
*ifa
= NULL
;
1755 ip_addr nh
= IPA_NONE
;
1756 u32 rid
= en
->lsa
.rt
;
1758 /* 16.1.1. The next hop calculation */
1759 DBG(" Next hop calculating for id: %R rt: %R type: %u\n",
1760 en
->lsa
.id
, en
->lsa
.rt
, en
->lsa_type
);
1762 /* Usually, we inherit parent nexthops */
1763 if (inherit_nexthops(pn
))
1767 * There are three cases:
1768 * 1) en is a local network (and par is root)
1769 * 2) en is a ptp or ptmp neighbor (and par is root)
1770 * 3) en is a bcast or nbma neighbor (and par is local network)
1773 /* The first case - local network */
1774 if ((en
->lsa_type
== LSA_T_NET
) && (par
== oa
->rt
))
1776 ifa
= rt_find_iface(oa
, pos
, data
, lif
);
1780 if (ospf_is_v3(p
) && (ifa
->iface_id
!= lif
))
1781 log(L_WARN
"%s: Inconsistent interface ID %u/%u", p
->p
.name
, ifa
->iface_id
, lif
);
1783 return new_nexthop(p
, IPA_NONE
, ifa
->iface
, ifa
->ecmp_weight
);
1786 /* The second case - ptp or ptmp neighbor */
1787 if ((en
->lsa_type
== LSA_T_RT
) && (par
== oa
->rt
))
1789 ifa
= rt_find_iface(oa
, pos
, data
, lif
);
1793 if (ospf_is_v3(p
) && (ifa
->iface_id
!= lif
))
1794 log(L_WARN
"%s: Inconsistent interface ID %u/%u", p
->p
.name
, ifa
->iface_id
, lif
);
1796 if (ifa
->type
== OSPF_IT_VLINK
)
1797 return new_nexthop(p
, IPA_NONE
, NULL
, 0);
1799 /* FIXME: On physical PtP links we may skip next-hop altogether */
1801 if (ospf_is_v2(p
) || ospf_is_ip6(p
))
1804 * In this case, next-hop is a source address from neighbor's packets.
1805 * That is necessary for OSPFv2 and practical for OSPFv3 (as it works even
1806 * if neighbor uses LinkLSASuppression), but does not work with OSPFv3-AF
1807 * on IPv4 topology, where src is IPv6 but next-hop should be IPv4.
1809 struct ospf_neighbor
*m
= find_neigh(ifa
, rid
);
1810 if (!m
|| (m
->state
!= NEIGHBOR_FULL
))
1818 * Next-hop is taken from lladdr field of Link-LSA, based on Neighbor
1819 * Iface ID (nif) field in our Router-LSA, which is just nbr->iface_id.
1821 link
= ospf_hash_find(p
->gr
, ifa
->iface_id
, nif
, rid
, LSA_T_LINK
);
1825 nh
= link_lsa_lladdr(p
, link
);
1830 return new_nexthop(p
, nh
, ifa
->iface
, ifa
->ecmp_weight
);
1833 /* The third case - bcast or nbma neighbor */
1834 if ((en
->lsa_type
== LSA_T_RT
) && (par
->lsa_type
== LSA_T_NET
))
1836 /* par->nhi should be defined from parent's calc_next_hop() */
1843 * In this case, next-hop is the same as link-back, which is
1844 * already computed in link_back().
1846 if (ipa_zero(en
->lb
))
1849 return new_nexthop(p
, en
->lb
, pn
->iface
, pn
->weight
);
1854 * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1855 * is computed in link_back().
1857 link
= ospf_hash_find(p
->gr
, pn
->iface
->index
, en
->lb_id
, rid
, LSA_T_LINK
);
1861 nh
= link_lsa_lladdr(p
, link
);
1865 return new_nexthop(p
, nh
, pn
->iface
, pn
->weight
);
1870 /* Probably bug or some race condition, we log it */
1871 log(L_ERR
"%s: Unexpected case in next hop calculation", p
->p
.name
);
1876 /* Add LSA into list of candidates in Dijkstra's algorithm */
1878 add_cand(struct ospf_area
*oa
, struct top_hash_entry
*en
, struct top_hash_entry
*par
,
1879 u32 dist
, int pos
, uint data
, uint lif
, uint nif
)
1881 struct ospf_proto
*p
= oa
->po
;
1884 struct top_hash_entry
*act
;
1889 if (en
->lsa
.age
== LSA_MAXAGE
)
1892 if (ospf_is_v3(p
) && (oa
->options
& OPT_V6
) && (en
->lsa_type
== LSA_T_RT
))
1894 /* In OSPFv3 IPv6 unicast, check V6 flag */
1895 struct ospf_lsa_rt
*rt
= en
->lsa_body
;
1896 if (!(rt
->options
& OPT_V6
))
1901 if (en
->color
== INSPF
)
1904 /* 16.1. (2d), also checks that dist < LSINFINITY */
1905 if (dist
> en
->dist
)
1908 /* We should check whether there is a reverse link from en to par, */
1909 if (!link_back(oa
, en
, par
, lif
, nif
))
1912 struct nexthop
*nhs
= calc_next_hop(oa
, en
, par
, pos
, data
, lif
, nif
);
1915 log(L_WARN
"%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1916 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
1920 /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
1921 if ((dist
== en
->dist
) && !nh_is_vlink(en
->nhs
))
1924 * For multipath, we should merge nexthops. We merge regular nexthops only.
1925 * Dummy vlink nexthops are less preferred and handled as a special case.
1927 * During merging, new nexthops (nhs) can be reused if they are not
1928 * inherited from the parent (i.e. they are allocated in calc_next_hop()).
1929 * Current nexthops (en->nhs) can be reused if they weren't inherited in
1930 * previous steps (that is stored in nhs_reuse, i.e. created by merging or
1931 * allocated in calc_next_hop()).
1933 * Generally, a node first inherits shared nexthops from its parent and
1934 * later possibly gets reusable (private) copy during merging. This is more
1935 * or less same for both top_hash_entry nodes and orta nodes.
1937 * Note that when a child inherits a private nexthop from its parent, it
1938 * should make the nexthop shared for both parent and child, while we only
1939 * update nhs_reuse for the child node. This makes nhs_reuse field for the
1940 * parent technically incorrect, but it is not a problem as parent's nhs
1941 * will not be modified (and nhs_reuse examined) afterwards.
1945 if (!p
->ecmp
|| nh_is_vlink(nhs
) || (nhs
== en
->nhs
))
1948 /* Merge old and new */
1949 int new_reuse
= (par
->nhs
!= nhs
);
1950 en
->nhs
= nexthop_merge(en
->nhs
, nhs
, en
->nhs_reuse
, new_reuse
, p
->ecmp
, p
->nhpool
);
1955 DBG(" Adding candidate: rt: %R, id: %R, type: %u\n",
1956 en
->lsa
.rt
, en
->lsa
.id
, en
->lsa_type
);
1958 if (en
->color
== CANDIDATE
)
1959 { /* We found a shorter path */
1964 en
->color
= CANDIDATE
;
1965 en
->nhs_reuse
= (par
->nhs
!= nhs
);
1969 if (EMPTY_LIST(oa
->cand
))
1971 add_head(&oa
->cand
, &en
->cn
);
1975 WALK_LIST(n
, oa
->cand
)
1977 act
= SKIP_BACK(struct top_hash_entry
, cn
, n
);
1978 if ((act
->dist
> dist
) ||
1979 ((act
->dist
== dist
) && (act
->lsa_type
== LSA_T_RT
)))
1982 add_head(&oa
->cand
, &en
->cn
);
1984 insert_node(&en
->cn
, prev
);
1993 add_tail(&oa
->cand
, &en
->cn
);
1999 ort_changed(ort
*nf
, rta
*nr
)
2001 rta
*or = nf
->old_rta
;
2003 (nf
->n
.metric1
!= nf
->old_metric1
) || (nf
->n
.metric2
!= nf
->old_metric2
) ||
2004 (nf
->n
.tag
!= nf
->old_tag
) || (nf
->n
.rid
!= nf
->old_rid
) ||
2005 (nr
->source
!= or->source
) || (nr
->dest
!= or->dest
) ||
2006 !nexthop_same(&(nr
->nh
), &(or->nh
));
2010 rt_sync(struct ospf_proto
*p
)
2012 struct top_hash_entry
*en
;
2013 struct fib_iterator fit
;
2014 struct fib
*fib
= &p
->rtf
;
2015 struct ospf_area
*oa
;
2017 /* This is used for forced reload of routes */
2018 int reload
= (p
->calcrt
== 2);
2020 OSPF_TRACE(D_EVENTS
, "Starting routing table synchronization");
2022 DBG("Now syncing my rt table with nest's\n");
2023 FIB_ITERATE_INIT(&fit
, fib
);
2025 FIB_ITERATE_START(fib
, &fit
, ort
, nf
)
2027 /* Sanity check of next-hop addresses, failure should not happen */
2031 for (nh
= nf
->n
.nhs
; nh
; nh
= nh
->next
)
2032 if (ipa_nonzero(nh
->gw
))
2034 neighbor
*ng
= neigh_find(&p
->p
, nh
->gw
, nh
->iface
, 0);
2035 if (!ng
|| (ng
->scope
== SCOPE_HOST
))
2036 { reset_ri(nf
); break; }
2040 /* Remove configured stubnets but keep the entries */
2041 if (nf
->n
.type
&& !nf
->n
.nhs
)
2047 if (nf
->n
.type
) /* Add the route */
2050 .src
= p
->p
.main_source
,
2051 .source
= nf
->n
.type
,
2052 .scope
= SCOPE_UNIVERSE
,
2053 .dest
= RTD_UNICAST
,
2057 if (reload
|| ort_changed(nf
, &a0
))
2059 rta
*a
= rta_lookup(&a0
);
2060 rte
*e
= rte_get_temp(a
);
2062 rta_free(nf
->old_rta
);
2063 nf
->old_rta
= rta_clone(a
);
2064 e
->u
.ospf
.metric1
= nf
->old_metric1
= nf
->n
.metric1
;
2065 e
->u
.ospf
.metric2
= nf
->old_metric2
= nf
->n
.metric2
;
2066 e
->u
.ospf
.tag
= nf
->old_tag
= nf
->n
.tag
;
2067 e
->u
.ospf
.router_id
= nf
->old_rid
= nf
->n
.rid
;
2068 e
->pflags
= EA_ID_FLAG(EA_OSPF_METRIC1
) | EA_ID_FLAG(EA_OSPF_ROUTER_ID
);
2070 if (nf
->n
.type
== RTS_OSPF_EXT2
)
2071 e
->pflags
|= EA_ID_FLAG(EA_OSPF_METRIC2
);
2073 /* Perhaps onfly if tag is non-zero? */
2074 if ((nf
->n
.type
== RTS_OSPF_EXT1
) || (nf
->n
.type
== RTS_OSPF_EXT2
))
2075 e
->pflags
|= EA_ID_FLAG(EA_OSPF_TAG
);
2077 DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
2078 a0
.source
, nf
->fn
.addr
, a0
.gw
, a0
.iface
? a0
.iface
->name
: "(none)", nf
->n
.metric1
);
2079 rte_update(&p
->p
, nf
->fn
.addr
, e
);
2082 else if (nf
->old_rta
)
2084 /* Remove the route */
2085 rta_free(nf
->old_rta
);
2088 rte_update(&p
->p
, nf
->fn
.addr
, NULL
);
2091 /* Remove unused rt entry, some special entries are persistent */
2092 if (!nf
->n
.type
&& !nf
->external_rte
&& !nf
->area_net
&& !nf
->keep
)
2095 idm_free(&p
->idm
, nf
->lsa_id
);
2097 FIB_ITERATE_PUT(&fit
);
2098 fib_delete(fib
, nf
);
2105 WALK_LIST(oa
, p
->area_list
)
2107 /* Cleanup ASBR hash tables */
2108 FIB_ITERATE_INIT(&fit
, &oa
->rtr
);
2110 FIB_ITERATE_START(&oa
->rtr
, &fit
, ort
, nf
)
2114 FIB_ITERATE_PUT(&fit
);
2115 fib_delete(&oa
->rtr
, nf
);
2122 /* Cleanup stale LSAs */
2123 WALK_SLIST(en
, p
->lsal
)
2124 if (en
->mode
== LSA_M_RTCALC_STALE
)
2125 ospf_flush_lsa(p
, en
);
2129 /* RFC 3623 2.2 - checking for graceful restart termination conditions */
2131 ospf_update_gr_recovery(struct ospf_proto
*p
)
2133 struct top_hash_entry
*rt
, *net
, *nbr
;
2134 struct ospf_lsa_rt_walk rtl
;
2135 struct ospf_neighbor
*n
;
2136 struct ospf_iface
*ifa
;
2137 struct ospf_area
*oa
;
2138 const char *err_dsc
= NULL
;
2139 uint i
, j
, missing
= 0, err_val
= 0;
2142 * We check here for three cases:
2143 * RFC 3623 2.2 (1) - success when all adjacencies are established
2144 * RFC 3623 2.2 (2) - failure when inconsistent LSA was received
2145 * RFC 3623 2.2 (3) - grace period timeout
2147 * It is handled by processing pre-restart local router-LSA and adjacent
2148 * network-LSAs, checking neighbor association for referenced routers (1)
2149 * and checking back links from their router-LSAs (2).
2151 * TODO: Use timer for grace period timeout. We avoided that as function
2152 * ospf_stop_gr_recovery() called from ospf_disp() makes ending of graceful
2153 * restart uninterrupted by other events.
2156 #define CONTINUE { missing++; continue; }
2158 if (current_time() > p
->gr_timeout
)
2161 WALK_LIST(oa
, p
->area_list
)
2163 /* Get the router-LSA */
2165 if (!rt
|| (rt
->lsa
.age
== LSA_MAXAGE
))
2168 for (lsa_walk_rt_init(p
, rt
, &rtl
), i
= 0; lsa_walk_rt(&rtl
); i
++)
2170 if (rtl
.type
== LSART_STUB
)
2173 ifa
= rt_find_iface(oa
, i
, rtl
.data
, rtl
.lif
);
2175 DROP("inconsistent interface", ospf_is_v2(p
) ? rtl
.data
: rtl
.lif
);
2180 /* Find the network-LSA */
2181 net
= ospf_hash_find_net(p
->gr
, oa
->areaid
, rtl
.id
, rtl
.nif
);
2185 if (!link_back(oa
, net
, rt
, rtl
.lif
, rtl
.nif
))
2186 DROP("Inconsistent network-LSA", net
->lsa
.id
);
2188 if (ifa
->state
== OSPF_IS_DR
)
2190 /* Find all neighbors from the network-LSA */
2191 struct ospf_lsa_net
*net_body
= net
->lsa_body
;
2192 uint cnt
= lsa_net_count(&net
->lsa
);
2193 for (j
= 0; j
< cnt
; i
++)
2195 n
= find_neigh(ifa
, net_body
->routers
[j
]);
2196 if (!n
|| (n
->state
!= NEIGHBOR_FULL
))
2199 if (!n
->got_my_rt_lsa
)
2200 DROP("not received my router-LSA", n
->rid
);
2202 nbr
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, n
->rid
);
2203 if (!link_back(oa
, nbr
, net
, 0, 0))
2204 DROP("inconsistent router-LSA", n
->rid
);
2209 /* Find the DR (by IP for OSPFv2) */
2211 find_neigh_by_ip(ifa
, ipa_from_u32(rtl
.id
)) :
2212 find_neigh(ifa
, rtl
.id
);
2213 if (!n
|| (n
->state
!= NEIGHBOR_FULL
))
2216 if (!n
->got_my_rt_lsa
)
2217 DROP("not received my router-LSA", n
->rid
);
2223 /* Find the PtP peer */
2224 n
= find_neigh(ifa
, rtl
.id
);
2225 if (!n
|| (n
->state
!= NEIGHBOR_FULL
))
2228 if (!n
->got_my_rt_lsa
)
2229 DROP("not received my router-LSA", n
->rid
);
2231 nbr
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, rtl
.id
);
2232 if (!link_back(oa
, nbr
, rt
, rtl
.lif
, rtl
.nif
))
2233 DROP("inconsistent router-LSA", rtl
.id
);
2243 OSPF_TRACE(D_EVENTS
, "Graceful restart finished");
2244 ospf_stop_gr_recovery(p
);
2248 log(L_INFO
"%s: Graceful restart ended - %s (%R)", p
->p
.name
, err_dsc
, err_val
);
2249 ospf_stop_gr_recovery(p
);
2253 log(L_INFO
"%s: Graceful restart ended - grace period expired", p
->p
.name
);
2254 ospf_stop_gr_recovery(p
);