]>
git.ipfire.org Git - thirdparty/bird.git/blob - proto/ospf/rt.c
16453b87043cac97d8b57b1e507f64aae5a76d12
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(list
* l
, struct top_hash_entry
*en
,
14 struct top_hash_entry
*par
, u32 dist
,
15 struct ospf_area
*oa
, int i
);
16 static void rt_sync(struct ospf_proto
*p
);
19 static inline void reset_ri(ort
*ort
)
21 bzero(&ort
->n
, sizeof(orta
));
25 ospf_rt_initort(struct fib_node
*fn
)
34 nh_is_vlink(struct mpnh
*nhs
)
40 unresolved_vlink(ort
*ort
)
42 return ort
->n
.nhs
&& nh_is_vlink(ort
->n
.nhs
);
45 static inline struct mpnh
*
46 new_nexthop(struct ospf_proto
*p
, ip_addr gw
, struct iface
*iface
, unsigned char weight
)
48 struct mpnh
*nh
= lp_alloc(p
->nhpool
, sizeof(struct mpnh
));
56 static inline struct mpnh
*
57 copy_nexthop(struct ospf_proto
*p
, const struct mpnh
*src
)
59 struct mpnh
*nh
= lp_alloc(p
->nhpool
, sizeof(struct mpnh
));
61 nh
->iface
= src
->iface
;
63 nh
->weight
= src
->weight
;
67 /* Compare nexthops during merge.
68 We need to maintain nhs sorted to eliminate duplicities */
70 cmp_nhs(struct mpnh
*s1
, struct mpnh
*s2
)
80 r
= ((int) s2
->weight
) - ((int) s1
->weight
);
84 r
= ipa_compare(s1
->gw
, s2
->gw
);
88 return ((int) s1
->iface
->index
) - ((int) s2
->iface
->index
);
92 merge_nexthops(struct ospf_proto
*p
, struct mpnh
*s1
, struct mpnh
*s2
, int r1
, int r2
)
94 struct mpnh
*root
= NULL
;
95 struct mpnh
**n
= &root
;
99 * r1, r2 signalize whether we can reuse nexthops from s1, s2.
100 * New nexthops (s2, new) can be reused if they are not inherited
101 * from the parent (i.e. it is allocated in calc_next_hop()).
102 * Current nexthops (s1, en->nhs) can be reused if they weren't
103 * inherited in previous steps (that is stored in nhs_reuse,
104 * i.e. created by merging or allocalted in calc_next_hop()).
106 * Generally, a node first inherits shared nexthops from its
107 * parent and later possibly gets reusable copy during merging.
110 while ((s1
|| s2
) && count
--)
112 int cmp
= cmp_nhs(s1
, s2
);
115 *n
= r1
? s1
: copy_nexthop(p
, s1
);
120 *n
= r2
? s2
: copy_nexthop(p
, s2
);
125 *n
= r1
? s1
: (r2
? s2
: copy_nexthop(p
, s1
));
136 /* Returns true if there are device nexthops in n */
138 has_device_nexthops(const struct mpnh
*n
)
140 for (; n
; n
= n
->next
)
147 /* Replace device nexthops with nexthops to gw */
149 fix_device_nexthops(struct ospf_proto
*p
, const struct mpnh
*n
, ip_addr gw
)
151 struct mpnh
*root1
= NULL
;
152 struct mpnh
*root2
= NULL
;
153 struct mpnh
**nn1
= &root1
;
154 struct mpnh
**nn2
= &root2
;
156 /* This is a bit tricky. We cannot just copy the list and update n->gw,
157 because the list should stay sorted, so we create two lists, one with new
158 gateways and one with old ones, and then merge them. */
160 for (; n
; n
= n
->next
)
162 struct mpnh
*nn
= new_nexthop(p
, ipa_zero(n
->gw
) ? gw
: n
->gw
, n
->iface
, n
->weight
);
176 return merge_nexthops(p
, root1
, root2
, 1, 1);
180 /* Whether the ASBR or the forward address destination is preferred
181 in AS external route selection according to 16.4.1. */
183 epath_preferred(const orta
*ep
)
185 return (ep
->type
== RTS_OSPF
) && (ep
->oa
->areaid
!= 0);
188 /* Whether the ext route has ASBR/next_hop marked as preferred. */
190 orta_pref(const orta
*nf
)
192 return !!(nf
->options
& ORTA_PREF
);
195 /* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
196 Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
198 orta_prio(const orta
*nf
)
200 /* RFC 3103 2.5 (6e) priorities */
201 u32 opts
= nf
->options
& (ORTA_NSSA
| ORTA_PROP
);
203 /* A Type-7 LSA with the P-bit set */
204 if (opts
== (ORTA_NSSA
| ORTA_PROP
))
214 /* Whether the route is better according to RFC 3101 2.5 (6e):
215 Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
217 orta_prefer_lsa(const orta
*new, const orta
*old
)
219 int pn
= orta_prio(new);
220 int po
= orta_prio(old
);
222 return (pn
> po
) || ((pn
== po
) && (new->en
->lsa
.rt
> old
->en
->lsa
.rt
));
226 * Compare an existing routing table entry with a new one. Applicable for
227 * intra-area routes, inter-area routes and router entries. Returns integer
228 * <, = or > than 0 if the new orta is less, equal or more preferred than
232 orta_compare(const struct ospf_proto
*p
, const orta
*new, const orta
*old
)
236 if (old
->type
== RTS_DUMMY
)
239 /* Prefer intra-area to inter-area to externals */
240 r
= ((int) old
->type
) - ((int) new->type
);
243 /* Prefer lowest type 1 metric */
244 r
= ((int) old
->metric1
) - ((int) new->metric1
);
248 /* Rest is BIRD-specific */
250 /* Area-wide routes should not mix next-hops from different areas.
251 This generally should not happen unless there is some misconfiguration. */
252 if (new->oa
->areaid
!= old
->oa
->areaid
)
253 return (new->oa
->areaid
> old
->oa
->areaid
) ? 1 : -1;
255 /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
256 vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
261 if (nh_is_vlink(new->nhs
))
263 if (nh_is_vlink(old
->nhs
))
270 /* Prefer routes with higher Router ID, just to be more deterministic */
271 if (new->rid
> old
->rid
)
278 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
279 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
280 * than 0 if the new ASBR is less or more preferred than the old ASBR.
283 orta_compare_asbr(const struct ospf_proto
*p
, const orta
*new, const orta
*old
)
287 if (old
->type
== RTS_DUMMY
)
292 r
= epath_preferred(new) - epath_preferred(old
);
296 r
= ((int) old
->metric1
) - ((int) new->metric1
);
299 /* Larger area ID is preferred */
300 if (new->oa
->areaid
> old
->oa
->areaid
)
303 /* There is just one ASBR of that RID per area, so tie is not possible */
308 * Compare a routing table entry with a new one, for AS external routes
309 * (RFC 2328 16.4) and NSSA routes (RFC 3103 2.5), Returns integer <, = or >
310 * than 0 if the new orta is less, equal or more preferred than the old orta.
313 orta_compare_ext(const struct ospf_proto
*p
, const orta
*new, const orta
*old
)
317 if (old
->type
== RTS_DUMMY
)
320 /* 16.4 (6a) - prefer routes with lower type */
321 r
= ((int) old
->type
) - ((int) new->type
);
324 /* 16.4 (6b) - prefer routes with lower type 2 metric */
325 if (new->type
== RTS_OSPF_EXT2
)
327 r
= ((int) old
->metric2
) - ((int) new->metric2
);
331 /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
334 r
= orta_pref(new) - orta_pref(old
);
338 /* 16.4 (6d) - prefer routes with lower type 1 metric */
339 r
= ((int) old
->metric1
) - ((int) new->metric1
);
343 if (p
->ecmp
&& p
->merge_external
)
347 * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
348 * LSA with higher router ID. Although this should apply just to functionally
349 * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
350 * use it also to disambiguate otherwise equally preferred nexthops.
352 if (orta_prefer_lsa(new, old
))
360 ort_replace(ort
*o
, const orta
*new)
362 memcpy(&o
->n
, new, sizeof(orta
));
366 ort_merge(struct ospf_proto
*p
, ort
*o
, const orta
*new)
370 if (old
->nhs
!= new->nhs
)
372 old
->nhs
= merge_nexthops(p
, old
->nhs
, new->nhs
, old
->nhs_reuse
, new->nhs_reuse
);
376 if (old
->rid
< new->rid
)
381 ort_merge_ext(struct ospf_proto
*p
, ort
*o
, const orta
*new)
385 if (old
->nhs
!= new->nhs
)
387 old
->nhs
= merge_nexthops(p
, old
->nhs
, new->nhs
, old
->nhs_reuse
, new->nhs_reuse
);
391 if (old
->tag
!= new->tag
)
395 * Even with multipath, we store only one LSA in orta.en for the purpose of
396 * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
397 * to all chosen LSAs for given network, not just to functionally equivalent
398 * ones (i.e. ones with the same non-zero forwarding address).
400 if (orta_prefer_lsa(new, old
))
402 old
->options
= new->options
;
412 ri_install_net(struct ospf_proto
*p
, ip_addr prefix
, int pxlen
, const orta
*new)
414 ort
*old
= (ort
*) fib_get(&p
->rtf
, &prefix
, pxlen
);
415 int cmp
= orta_compare(p
, new, &old
->n
);
418 ort_replace(old
, new);
420 ort_merge(p
, old
, new);
424 ri_install_rt(struct ospf_area
*oa
, u32 rid
, const orta
*new)
426 ip_addr addr
= ipa_from_rid(rid
);
427 ort
*old
= (ort
*) fib_get(&oa
->rtr
, &addr
, MAX_PREFIX_LENGTH
);
428 int cmp
= orta_compare(oa
->po
, new, &old
->n
);
431 ort_replace(old
, new);
433 ort_merge(oa
->po
, old
, new);
437 ri_install_asbr(struct ospf_proto
*p
, ip_addr
*addr
, const orta
*new)
439 ort
*old
= (ort
*) fib_get(&p
->backbone
->rtr
, addr
, MAX_PREFIX_LENGTH
);
440 if (orta_compare_asbr(p
, new, &old
->n
) > 0)
441 ort_replace(old
, new);
445 ri_install_ext(struct ospf_proto
*p
, ip_addr prefix
, int pxlen
, const orta
*new)
447 ort
*old
= (ort
*) fib_get(&p
->rtf
, &prefix
, pxlen
);
448 int cmp
= orta_compare_ext(p
, new, &old
->n
);
451 ort_replace(old
, new);
453 ort_merge_ext(p
, old
, new);
456 static inline struct ospf_iface
*
457 rt_pos_to_ifa(struct ospf_area
*oa
, int pos
)
459 struct ospf_iface
*ifa
;
461 WALK_LIST(ifa
, oa
->po
->iface_list
)
462 if (ifa
->oa
== oa
&& pos
>= ifa
->rt_pos_beg
&& pos
< ifa
->rt_pos_end
)
468 static inline struct ospf_iface
*
469 px_pos_to_ifa(struct ospf_area
*oa
, int pos
)
471 struct ospf_iface
*ifa
;
473 WALK_LIST(ifa
, oa
->po
->iface_list
)
474 if (ifa
->oa
== oa
&& pos
>= ifa
->px_pos_beg
&& pos
< ifa
->px_pos_end
)
482 add_network(struct ospf_area
*oa
, ip_addr px
, int pxlen
, int metric
, struct top_hash_entry
*en
, int pos
)
484 struct ospf_proto
*p
= oa
->po
;
490 .metric2
= LSINFINITY
,
497 if (pxlen
< 0 || pxlen
> MAX_PREFIX_LENGTH
)
499 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
500 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
507 * Local stub networks does not have proper iface in en->nhi
508 * (because they all have common top_hash_entry en).
509 * We have to find iface responsible for that stub network.
510 * Configured stubnets does not have any iface. They will
511 * be removed in rt_sync().
514 struct ospf_iface
*ifa
;
515 ifa
= ospf_is_v2(p
) ? rt_pos_to_ifa(oa
, pos
) : px_pos_to_ifa(oa
, pos
);
516 nf
.nhs
= ifa
? new_nexthop(p
, IPA_NONE
, ifa
->iface
, ifa
->ecmp_weight
) : NULL
;
519 ri_install_net(p
, px
, pxlen
, &nf
);
525 spfa_process_rt(struct ospf_proto
*p
, struct ospf_area
*oa
, struct top_hash_entry
*act
)
527 struct ospf_lsa_rt
*rt
= act
->lsa_body
;
528 struct ospf_lsa_rt_walk rtl
;
529 struct top_hash_entry
*tmp
;
533 if (rt
->options
& OPT_RT_V
)
537 * In OSPFv3, all routers are added to per-area routing
538 * tables. But we use it just for ASBRs and ABRs. For the
539 * purpose of the last step in SPF - prefix-LSA processing in
540 * spfa_process_prefixes(), we use information stored in LSA db.
542 if (((rt
->options
& OPT_RT_E
) || (rt
->options
& OPT_RT_B
))
543 && (act
->lsa
.rt
!= p
->router_id
))
547 .options
= rt
->options
,
548 .metric1
= act
->dist
,
549 .metric2
= LSINFINITY
,
555 ri_install_rt(oa
, act
->lsa
.rt
, &nf
);
558 /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
559 if (ospf_is_v3(p
) && (act
!= oa
->rt
) && !(rt
->options
& OPT_R
))
562 /* Now process Rt links */
563 for (lsa_walk_rt_init(p
, act
, &rtl
), i
= 0; lsa_walk_rt(&rtl
); i
++)
571 /* Should not happen, LSART_STUB is not defined in OSPFv3 */
576 * RFC 2328 in 16.1. (2a) says to handle stub networks in an
577 * second phase after the SPF for an area is calculated. We get
578 * the same result by handing them here because add_network()
579 * will keep the best (not the first) found route.
581 prefix
= ipa_from_u32(rtl
.id
& rtl
.data
);
582 pxlen
= u32_masklen(rtl
.data
);
583 add_network(oa
, prefix
, pxlen
, act
->dist
+ rtl
.metric
, act
, i
);
587 tmp
= ospf_hash_find_net(p
->gr
, oa
->areaid
, rtl
.id
, rtl
.nif
);
592 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, rtl
.id
);
596 add_cand(&oa
->cand
, tmp
, act
, act
->dist
+ rtl
.metric
, oa
, i
);
601 spfa_process_net(struct ospf_proto
*p
, struct ospf_area
*oa
, struct top_hash_entry
*act
)
603 struct ospf_lsa_net
*ln
= act
->lsa_body
;
604 struct top_hash_entry
*tmp
;
610 prefix
= ipa_from_u32(act
->lsa
.id
& ln
->optx
);
611 pxlen
= u32_masklen(ln
->optx
);
612 add_network(oa
, prefix
, pxlen
, act
->dist
, act
, -1);
615 cnt
= lsa_net_count(&act
->lsa
);
616 for (i
= 0; i
< cnt
; i
++)
618 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, ln
->routers
[i
]);
619 add_cand(&oa
->cand
, tmp
, act
, act
->dist
, oa
, -1);
624 spfa_process_prefixes(struct ospf_proto
*p
, struct ospf_area
*oa
)
626 struct top_hash_entry
*en
, *src
;
627 struct ospf_lsa_prefix
*px
;
635 WALK_SLIST(en
, p
->lsal
)
637 if (en
->lsa_type
!= LSA_T_PREFIX
)
640 if (en
->domain
!= oa
->areaid
)
643 if (en
->lsa
.age
== LSA_MAXAGE
)
648 /* For router prefix-LSA, we would like to find the first router-LSA */
649 if (px
->ref_type
== LSA_T_RT
)
650 src
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, px
->ref_rt
);
652 src
= ospf_hash_find(p
->gr
, oa
->areaid
, px
->ref_id
, px
->ref_rt
, px
->ref_type
);
657 /* Reachable in SPF */
658 if (src
->color
!= INSPF
)
661 if ((src
->lsa_type
!= LSA_T_RT
) && (src
->lsa_type
!= LSA_T_NET
))
665 for (i
= 0; i
< px
->pxcount
; i
++)
667 buf
= lsa_get_ipv6_prefix(buf
, &pxa
, &pxlen
, &pxopts
, &metric
);
669 if (pxopts
& OPT_PX_NU
)
672 /* Store the first global address to use it later as a vlink endpoint */
673 if ((pxopts
& OPT_PX_LA
) && ipa_zero(src
->lb
))
676 add_network(oa
, pxa
, pxlen
, src
->dist
+ metric
, src
, i
);
681 /* RFC 2328 16.1. calculating shortest paths for an area */
683 ospf_rt_spfa(struct ospf_area
*oa
)
685 struct ospf_proto
*p
= oa
->po
;
686 struct top_hash_entry
*act
;
691 if (oa
->rt
->lsa
.age
== LSA_MAXAGE
)
694 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation for area %R", oa
->areaid
);
697 init_list(&oa
->cand
); /* Empty list of candidates */
700 DBG("LSA db prepared, adding me into candidate list.\n");
703 oa
->rt
->color
= CANDIDATE
;
704 add_head(&oa
->cand
, &oa
->rt
->cn
);
705 DBG("RT LSA: rt: %R, id: %R, type: %u\n",
706 oa
->rt
->lsa
.rt
, oa
->rt
->lsa
.id
, oa
->rt
->lsa_type
);
708 while (!EMPTY_LIST(oa
->cand
))
711 act
= SKIP_BACK(struct top_hash_entry
, cn
, n
);
714 DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
715 act
->lsa
.rt
, act
->lsa
.id
, act
->lsa_type
);
718 switch (act
->lsa_type
)
721 spfa_process_rt(p
, oa
, act
);
725 spfa_process_net(p
, oa
, act
);
729 log(L_WARN
"%s: Unknown LSA type in SPF: %d", p
->p
.name
, act
->lsa_type
);
734 spfa_process_prefixes(p
, oa
);
738 link_back(struct ospf_area
*oa
, struct top_hash_entry
*en
, struct top_hash_entry
*par
)
740 struct ospf_proto
*p
= oa
->po
;
741 struct ospf_lsa_rt_walk rtl
;
742 struct top_hash_entry
*tmp
;
743 struct ospf_lsa_net
*ln
;
746 if (!en
|| !par
) return 0;
748 /* We should check whether there is a link back from en to par,
749 this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
750 note 23, we don't have to find the same link that is used for par
751 to en, any link is enough. This we do for ptp links. For net-rt
752 links, we have to find the same link to compute proper lb/lb_id,
753 which may be later used as the next hop. */
755 /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
756 it is set in process_prefixes() to any global addres in the area */
761 switch (en
->lsa_type
)
764 lsa_walk_rt_init(p
, en
, &rtl
);
765 while (lsa_walk_rt(&rtl
))
773 tmp
= ospf_hash_find_net(p
->gr
, oa
->areaid
, rtl
.id
, rtl
.nif
);
777 en
->lb
= ipa_from_u32(rtl
.data
);
787 /* Not necessary the same link, see RFC 2328 [23] */
788 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, rtl
.id
);
798 cnt
= lsa_net_count(&en
->lsa
);
799 for (i
= 0; i
< cnt
; i
++)
801 tmp
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, ln
->routers
[i
]);
808 log(L_WARN
"%s: Unknown LSA type in SPF: %d", p
->p
.name
, en
->lsa_type
);
814 /* RFC 2328 16.2. calculating inter-area routes */
816 ospf_rt_sum(struct ospf_area
*oa
)
818 struct ospf_proto
*p
= oa
->po
;
819 struct top_hash_entry
*en
;
821 u32 dst_rid
, metric
, options
;
823 int pxlen
= -1, type
= -1;
827 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation for inter-area (area %R)", oa
->areaid
);
829 WALK_SLIST(en
, p
->lsal
)
831 if ((en
->lsa_type
!= LSA_T_SUM_RT
) && (en
->lsa_type
!= LSA_T_SUM_NET
))
834 if (en
->domain
!= oa
->areaid
)
838 if (en
->lsa
.age
== LSA_MAXAGE
)
842 if (en
->lsa
.rt
== p
->router_id
)
845 /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */
847 if (en
->lsa_type
== LSA_T_SUM_NET
)
849 lsa_parse_sum_net(en
, ospf_is_v2(p
), &ip
, &pxlen
, &pxopts
, &metric
);
851 if (pxopts
& OPT_PX_NU
)
854 if (pxlen
< 0 || pxlen
> MAX_PREFIX_LENGTH
)
856 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
857 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
864 else /* LSA_T_SUM_RT */
866 lsa_parse_sum_rt(en
, ospf_is_v2(p
), &dst_rid
, &metric
, &options
);
868 /* We don't want local router in ASBR routing table */
869 if (dst_rid
== p
->router_id
)
872 options
|= ORTA_ASBR
;
877 if (metric
== LSINFINITY
)
881 abrip
= ipa_from_rid(en
->lsa
.rt
);
882 abr
= (ort
*) fib_find(&oa
->rtr
, &abrip
, MAX_PREFIX_LENGTH
);
883 if (!abr
|| !abr
->n
.type
)
886 if (!(abr
->n
.options
& ORTA_ABR
))
889 /* This check is not mentioned in RFC 2328 */
890 if (abr
->n
.type
!= RTS_OSPF
)
897 .metric1
= abr
->n
.metric1
+ metric
,
898 .metric2
= LSINFINITY
,
900 .rid
= en
->lsa
.rt
, /* ABR ID */
906 ri_install_net(p
, ip
, pxlen
, &nf
);
908 ri_install_rt(oa
, dst_rid
, &nf
);
912 /* RFC 2328 16.3. examining summary-LSAs in transit areas */
914 ospf_rt_sum_tr(struct ospf_area
*oa
)
916 struct ospf_proto
*p
= oa
->po
;
917 struct ospf_area
*bb
= p
->backbone
;
918 struct top_hash_entry
*en
;
921 u32 dst_rid
, metric
, options
;
929 WALK_SLIST(en
, p
->lsal
)
931 if ((en
->lsa_type
!= LSA_T_SUM_RT
) && (en
->lsa_type
!= LSA_T_SUM_NET
))
934 if (en
->domain
!= oa
->areaid
)
938 if (en
->lsa
.age
== LSA_MAXAGE
)
942 if (en
->lsa
.rt
== p
->router_id
)
945 if (en
->lsa_type
== LSA_T_SUM_NET
)
947 lsa_parse_sum_net(en
, ospf_is_v2(p
), &ip
, &pxlen
, &pxopts
, &metric
);
949 if (pxopts
& OPT_PX_NU
)
952 if (pxlen
< 0 || pxlen
> MAX_PREFIX_LENGTH
)
954 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
955 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
959 re
= fib_find(&p
->rtf
, &ip
, pxlen
);
961 else // en->lsa_type == LSA_T_SUM_RT
963 lsa_parse_sum_rt(en
, ospf_is_v2(p
), &dst_rid
, &metric
, &options
);
965 ip
= ipa_from_rid(dst_rid
);
966 re
= fib_find(&bb
->rtr
, &ip
, MAX_PREFIX_LENGTH
);
970 if (metric
== LSINFINITY
)
974 if (!re
|| !re
->n
.type
)
977 if (re
->n
.oa
->areaid
!= 0)
980 if ((re
->n
.type
!= RTS_OSPF
) && (re
->n
.type
!= RTS_OSPF_IA
))
984 abrip
= ipa_from_rid(en
->lsa
.rt
);
985 abr
= fib_find(&oa
->rtr
, &abrip
, MAX_PREFIX_LENGTH
);
986 if (!abr
|| !abr
->n
.type
)
989 metric
= abr
->n
.metric1
+ metric
; /* IAC */
992 if ((metric
< re
->n
.metric1
) ||
993 ((metric
== re
->n
.metric1
) && unresolved_vlink(re
)))
995 /* We want to replace the next-hop even if the metric is equal
996 to replace a virtual next-hop through vlink with a real one.
997 Proper ECMP would merge nexthops here, but we do not do that.
998 We restrict nexthops to fit one area to simplify check
999 12.4.3 p4 in decide_sum_lsa() */
1001 re
->n
.metric1
= metric
;
1003 re
->n
.nhs
= abr
->n
.nhs
;
1008 /* Decide about originating or flushing summary LSAs for condended area networks */
1010 decide_anet_lsa(struct ospf_area
*oa
, struct area_net
*anet
, struct ospf_area
*anet_oa
)
1012 /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
1013 if (!oa_is_ext(oa
) && !oa
->ac
->summary
)
1019 /* Do not condense routing info when exporting from backbone to the transit area */
1020 if ((anet_oa
== oa
->po
->backbone
) && oa
->trcap
)
1023 return (anet
->active
&& !anet
->hidden
);
1026 /* Decide about originating or flushing summary LSAs (12.4.3) */
1028 decide_sum_lsa(struct ospf_area
*oa
, ort
*nf
, int dest
)
1030 /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
1031 if (!oa_is_ext(oa
) && !oa
->ac
->summary
)
1034 /* Invalid field - no route */
1039 if (nf
->n
.type
> RTS_OSPF_IA
)
1043 if ((nf
->n
.oa
->areaid
== oa
->areaid
))
1047 if (nf
->n
.voa
&& (nf
->n
.voa
->areaid
== oa
->areaid
))
1051 if (nf
->n
.metric1
>= LSINFINITY
)
1054 /* 12.4.3 p6 - AS boundary router */
1055 if (dest
== ORT_ROUTER
)
1057 /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
1059 return oa_is_ext(oa
) && (nf
->n
.options
& ORTA_ASBR
);
1062 /* 12.4.3 p7 - inter-area route */
1063 if (nf
->n
.type
== RTS_OSPF_IA
)
1065 /* Inter-area routes are not repropagated into the backbone */
1066 return (oa
!= oa
->po
->backbone
);
1069 /* 12.4.3 p8 - intra-area route */
1071 /* Do not condense routing info when exporting from backbone to the transit area */
1072 if ((nf
->n
.oa
== oa
->po
->backbone
) && oa
->trcap
)
1075 struct area_net
*anet
= (struct area_net
*)
1076 fib_route(&nf
->n
.oa
->net_fib
, nf
->fn
.prefix
, nf
->fn
.pxlen
);
1078 /* Condensed area network found */
1085 /* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1087 check_sum_net_lsa(struct ospf_proto
*p
, ort
*nf
)
1089 struct area_net
*anet
= NULL
;
1090 struct ospf_area
*anet_oa
= NULL
;
1094 /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1095 if (nf
->fn
.pxlen
== 0)
1098 /* Find that area network */
1099 WALK_LIST(anet_oa
, p
->area_list
)
1101 anet
= (struct area_net
*) fib_find(&anet_oa
->net_fib
, &nf
->fn
.prefix
, nf
->fn
.pxlen
);
1107 struct ospf_area
*oa
;
1108 WALK_LIST(oa
, p
->area_list
)
1110 if (anet
&& decide_anet_lsa(oa
, anet
, anet_oa
))
1111 ospf_originate_sum_net_lsa(p
, oa
, nf
, anet
->metric
);
1112 else if (decide_sum_lsa(oa
, nf
, ORT_NET
))
1113 ospf_originate_sum_net_lsa(p
, oa
, nf
, nf
->n
.metric1
);
1118 check_sum_rt_lsa(struct ospf_proto
*p
, ort
*nf
)
1120 struct ospf_area
*oa
;
1121 WALK_LIST(oa
, p
->area_list
)
1122 if (decide_sum_lsa(oa
, nf
, ORT_ROUTER
))
1123 ospf_originate_sum_rt_lsa(p
, oa
, nf
, nf
->n
.metric1
, nf
->n
.options
);
1127 decide_nssa_lsa(struct ospf_proto
*p
, ort
*nf
, struct ospf_lsa_ext_local
*rt
)
1129 struct ospf_area
*oa
= nf
->n
.oa
;
1130 struct top_hash_entry
*en
= nf
->n
.en
;
1132 if (!rt_is_nssa(nf
) || !oa
->translate
)
1135 /* Condensed area network found */
1136 if (fib_route(&oa
->enet_fib
, nf
->fn
.prefix
, nf
->fn
.pxlen
))
1139 if (!en
|| (en
->lsa_type
!= LSA_T_NSSA
))
1142 /* We do not store needed data in struct orta, we have to parse the LSA */
1143 lsa_parse_ext(en
, ospf_is_v2(p
), rt
);
1145 if (rt
->pxopts
& OPT_PX_NU
)
1148 if (!rt
->propagate
|| ipa_zero(rt
->fwaddr
))
1154 /* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1156 check_nssa_lsa(struct ospf_proto
*p
, ort
*nf
)
1158 struct area_net
*anet
= NULL
;
1159 struct ospf_area
*oa
= NULL
;
1160 struct ospf_lsa_ext_local rt
;
1162 /* Do not translate LSA if there is already the external LSA from route export */
1163 if (nf
->external_rte
)
1168 /* Find that area network */
1169 WALK_LIST(oa
, p
->area_list
)
1171 anet
= (struct area_net
*) fib_find(&oa
->enet_fib
, &nf
->fn
.prefix
, nf
->fn
.pxlen
);
1177 /* RFC 3103 3.2 (3) - originate the aggregated address range */
1178 if (anet
&& anet
->active
&& !anet
->hidden
&& oa
->translate
)
1179 ospf_originate_ext_lsa(p
, NULL
, nf
, LSA_M_RTCALC
, anet
->metric
,
1180 (anet
->metric
& LSA_EXT3_EBIT
), IPA_NONE
, anet
->tag
, 0);
1182 /* RFC 3103 3.2 (2) - originate the same network */
1183 else if (decide_nssa_lsa(p
, nf
, &rt
))
1184 ospf_originate_ext_lsa(p
, NULL
, nf
, LSA_M_RTCALC
, rt
.metric
, rt
.ebit
, rt
.fwaddr
, rt
.tag
, 0);
1187 /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1189 ospf_check_vlinks(struct ospf_proto
*p
)
1191 struct ospf_iface
*ifa
;
1192 WALK_LIST(ifa
, p
->iface_list
)
1194 if (ifa
->type
== OSPF_IT_VLINK
)
1196 struct top_hash_entry
*tmp
;
1197 tmp
= ospf_hash_find_rt(p
->gr
, ifa
->voa
->areaid
, ifa
->vid
);
1199 if (tmp
&& (tmp
->color
== INSPF
) && ipa_nonzero(tmp
->lb
) && tmp
->nhs
)
1201 struct ospf_iface
*nhi
= ospf_iface_find(p
, tmp
->nhs
->iface
);
1203 if ((ifa
->state
!= OSPF_IS_PTP
)
1204 || (ifa
->vifa
!= nhi
)
1205 || !ipa_equal(ifa
->vip
, tmp
->lb
))
1207 OSPF_TRACE(D_EVENTS
, "Vlink peer %R found", tmp
->lsa
.id
);
1208 ospf_iface_sm(ifa
, ISM_DOWN
);
1210 ifa
->addr
= nhi
->addr
;
1211 ifa
->cost
= tmp
->dist
;
1213 ospf_iface_sm(ifa
, ISM_UP
);
1215 else if ((ifa
->state
== OSPF_IS_PTP
) && (ifa
->cost
!= tmp
->dist
))
1217 ifa
->cost
= tmp
->dist
;
1219 /* RFC 2328 12.4 Event 8 - vlink state change */
1220 ospf_notify_rt_lsa(ifa
->oa
);
1225 if (ifa
->state
> OSPF_IS_DOWN
)
1227 OSPF_TRACE(D_EVENTS
, "Vlink peer %R lost", ifa
->vid
);
1228 ospf_iface_sm(ifa
, ISM_DOWN
);
1236 /* Miscellaneous route processing that needs to be done by ABRs */
1238 ospf_rt_abr1(struct ospf_proto
*p
)
1240 struct area_net
*anet
;
1241 ort
*nf
, *default_nf
;
1243 /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1244 FIB_WALK(&p
->backbone
->rtr
, nftmp
)
1248 if (nf
->n
.type
&& unresolved_vlink(nf
))
1254 FIB_WALK(&p
->rtf
, nftmp
)
1259 /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1260 if (nf
->n
.type
&& unresolved_vlink(nf
))
1264 /* Compute condensed area networks */
1265 if (nf
->n
.type
== RTS_OSPF
)
1267 anet
= (struct area_net
*) fib_route(&nf
->n
.oa
->net_fib
, nf
->fn
.prefix
, nf
->fn
.pxlen
);
1274 /* Get a RT entry and mark it to know that it is an area network */
1275 ort
*nfi
= (ort
*) fib_get(&p
->rtf
, &anet
->fn
.prefix
, anet
->fn
.pxlen
);
1279 if (nfi
->n
.type
== RTS_OSPF_IA
)
1283 if (anet
->metric
< nf
->n
.metric1
)
1284 anet
->metric
= nf
->n
.metric1
;
1290 ip_addr addr
= IPA_NONE
;
1291 default_nf
= (ort
*) fib_get(&p
->rtf
, &addr
, 0);
1292 default_nf
->area_net
= 1;
1294 struct ospf_area
*oa
;
1295 WALK_LIST(oa
, p
->area_list
)
1298 /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
1299 if (oa_is_stub(oa
) || (oa_is_nssa(oa
) && !oa
->ac
->summary
))
1300 ospf_originate_sum_net_lsa(p
, oa
, default_nf
, oa
->ac
->default_cost
);
1303 * Originate type-7 default route for NSSA areas
1305 * Because type-7 default LSAs are originated by ABRs, they do not
1306 * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1307 * for both external route export or external-NSSA translation),
1308 * so we use 0 for the src arg.
1311 if (oa_is_nssa(oa
) && oa
->ac
->default_nssa
)
1312 ospf_originate_ext_lsa(p
, oa
, default_nf
, LSA_M_RTCALC
, oa
->ac
->default_cost
,
1313 (oa
->ac
->default_cost
& LSA_EXT3_EBIT
), IPA_NONE
, 0, 0);
1315 /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1318 FIB_WALK(&oa
->rtr
, nftmp
)
1321 if (nf
->n
.options
& ORTA_ASBR
)
1322 ri_install_asbr(p
, &nf
->fn
.prefix
, &nf
->n
);
1329 /* Originate or flush ASBR summary LSAs */
1330 FIB_WALK(&p
->backbone
->rtr
, nftmp
)
1332 check_sum_rt_lsa(p
, (ort
*) nftmp
);
1337 /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1338 ospf_check_vlinks(p
);
1343 translator_timer_hook(timer
*timer
)
1345 struct ospf_area
*oa
= timer
->data
;
1347 if (oa
->translate
!= TRANS_WAIT
)
1350 oa
->translate
= TRANS_OFF
;
1351 ospf_schedule_rtcalc(oa
->po
);
1355 ospf_rt_abr2(struct ospf_proto
*p
)
1357 struct ospf_area
*oa
;
1358 struct top_hash_entry
*en
;
1362 /* RFC 3103 3.1 - type-7 translator election */
1363 struct ospf_area
*bb
= p
->backbone
;
1364 WALK_LIST(oa
, p
->area_list
)
1369 if (oa
->ac
->translator
)
1372 FIB_WALK(&oa
->rtr
, nftmp
)
1375 if (!nf
->n
.type
|| !(nf
->n
.options
& ORTA_ABR
))
1378 nf2
= fib_find(&bb
->rtr
, &nf
->fn
.prefix
, MAX_PREFIX_LENGTH
);
1379 if (!nf2
|| !nf2
->n
.type
|| !(nf2
->n
.options
& ORTA_ABR
))
1382 en
= ospf_hash_find_rt(p
->gr
, oa
->areaid
, nf
->n
.rid
);
1383 if (!en
|| (en
->color
!= INSPF
))
1386 struct ospf_lsa_rt
*rt
= en
->lsa_body
;
1387 /* There is better candidate - Nt-bit or higher Router ID */
1388 if ((rt
->options
& OPT_RT_NT
) || (p
->router_id
< nf
->n
.rid
))
1397 if (translate
&& (oa
->translate
!= TRANS_ON
))
1399 if (oa
->translate
== TRANS_WAIT
)
1400 tm_stop(oa
->translator_timer
);
1402 oa
->translate
= TRANS_ON
;
1405 if (!translate
&& (oa
->translate
== TRANS_ON
))
1407 if (oa
->translator_timer
== NULL
)
1408 oa
->translator_timer
= tm_new_set(p
->p
.pool
, translator_timer_hook
, oa
, 0, 0);
1410 /* Schedule the end of translation */
1411 tm_start(oa
->translator_timer
, oa
->ac
->transint
);
1412 oa
->translate
= TRANS_WAIT
;
1417 /* Compute condensed external networks */
1418 FIB_WALK(&p
->rtf
, nftmp
)
1421 if (rt_is_nssa(nf
) && (nf
->n
.options
& ORTA_PROP
))
1423 struct area_net
*anet
= (struct area_net
*)
1424 fib_route(&nf
->n
.oa
->enet_fib
, nf
->fn
.prefix
, nf
->fn
.pxlen
);
1432 /* Get a RT entry and mark it to know that it is an area network */
1433 nf2
= (ort
*) fib_get(&p
->rtf
, &anet
->fn
.prefix
, anet
->fn
.pxlen
);
1437 u32 metric
= (nf
->n
.type
== RTS_OSPF_EXT1
) ?
1438 nf
->n
.metric1
: ((nf
->n
.metric2
+ 1) | LSA_EXT3_EBIT
);
1440 if (anet
->metric
< metric
)
1441 anet
->metric
= metric
;
1448 FIB_WALK(&p
->rtf
, nftmp
)
1452 check_sum_net_lsa(p
, nf
);
1453 check_nssa_lsa(p
, nf
);
1459 /* Like fib_route(), but ignores dummy rt entries */
1461 ospf_fib_route(struct fib
*f
, ip_addr a
, int len
)
1468 a0
= ipa_and(a
, ipa_mkmask(len
));
1469 nf
= fib_find(f
, &a0
, len
);
1470 if (nf
&& nf
->n
.type
)
1477 /* RFC 2328 16.4. calculating external routes */
1479 ospf_ext_spf(struct ospf_proto
*p
)
1481 struct top_hash_entry
*en
;
1482 struct ospf_lsa_ext_local rt
;
1487 struct ospf_area
*atmp
;
1489 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation for ext routes");
1491 WALK_SLIST(en
, p
->lsal
)
1494 if ((en
->lsa_type
!= LSA_T_EXT
) && (en
->lsa_type
!= LSA_T_NSSA
))
1497 if (en
->lsa
.age
== LSA_MAXAGE
)
1501 if (en
->lsa
.rt
== p
->router_id
)
1504 DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
1505 p
->p
.name
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa_type
);
1507 lsa_parse_ext(en
, ospf_is_v2(p
), &rt
);
1509 if (rt
.metric
== LSINFINITY
)
1512 if (rt
.pxopts
& OPT_PX_NU
)
1515 if (rt
.pxlen
< 0 || rt
.pxlen
> MAX_PREFIX_LENGTH
)
1517 log(L_WARN
"%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1518 p
->p
.name
, en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
1524 /* If there are more areas, we already precomputed preferred ASBR
1525 entries in ospf_rt_abr1() and stored them in the backbone
1526 table. For NSSA, we examine the area to which the LSA is assigned */
1527 if (en
->lsa_type
== LSA_T_EXT
)
1528 atmp
= ospf_main_area(p
);
1530 atmp
= ospf_find_area(p
, en
->domain
);
1533 continue; /* Should not happen */
1535 rtid
= ipa_from_rid(en
->lsa
.rt
);
1536 nf1
= fib_find(&atmp
->rtr
, &rtid
, MAX_PREFIX_LENGTH
);
1538 if (!nf1
|| !nf1
->n
.type
)
1539 continue; /* No AS boundary router found */
1541 if (!(nf1
->n
.options
& ORTA_ASBR
))
1542 continue; /* It is not ASBR */
1544 /* 16.4. (3) NSSA - special rule for default routes */
1545 /* ABR should use default only if P-bit is set and summaries are active */
1546 if ((en
->lsa_type
== LSA_T_NSSA
) && ipa_zero(rt
.ip
) && (rt
.pxlen
== 0) &&
1547 (p
->areano
> 1) && !(rt
.propagate
&& atmp
->ac
->summary
))
1553 nfa
.nhs
= nf1
->n
.nhs
;
1554 br_metric
= nf1
->n
.metric1
;
1558 nf2
= ospf_fib_route(&p
->rtf
, rt
.fwaddr
, MAX_PREFIX_LENGTH
);
1562 if (en
->lsa_type
== LSA_T_EXT
)
1564 /* For ext routes, we accept intra-area or inter-area routes */
1565 if ((nf2
->n
.type
!= RTS_OSPF
) && (nf2
->n
.type
!= RTS_OSPF_IA
))
1570 /* For NSSA routes, we accept just intra-area in the same area */
1571 if ((nf2
->n
.type
!= RTS_OSPF
) || (nf2
->n
.oa
!= atmp
))
1575 /* Next-hop is a part of a configured stubnet */
1579 nfa
.nhs
= nf2
->n
.nhs
;
1580 br_metric
= nf2
->n
.metric1
;
1582 /* Replace device nexthops with nexthops to forwarding address from LSA */
1583 if (has_device_nexthops(nfa
.nhs
))
1585 nfa
.nhs
= fix_device_nexthops(p
, nfa
.nhs
, rt
.fwaddr
);
1592 nfa
.type
= RTS_OSPF_EXT2
;
1593 nfa
.metric1
= br_metric
;
1594 nfa
.metric2
= rt
.metric
;
1598 nfa
.type
= RTS_OSPF_EXT1
;
1599 nfa
.metric1
= br_metric
+ rt
.metric
;
1600 nfa
.metric2
= LSINFINITY
;
1603 /* Mark the LSA as reachable */
1606 /* Whether the route is preferred in route selection according to 16.4.1 */
1607 nfa
.options
= epath_preferred(&nf2
->n
) ? ORTA_PREF
: 0;
1608 if (en
->lsa_type
== LSA_T_NSSA
)
1610 nfa
.options
|= ORTA_NSSA
;
1612 nfa
.options
|= ORTA_PROP
;
1616 nfa
.rid
= en
->lsa
.rt
;
1617 nfa
.oa
= atmp
; /* undefined in RFC 2328 */
1618 nfa
.en
= en
; /* store LSA for later (NSSA processing) */
1620 ri_install_ext(p
, rt
.ip
, rt
.pxlen
, &nfa
);
1624 /* Cleanup of routing tables and data */
1626 ospf_rt_reset(struct ospf_proto
*p
)
1628 struct ospf_area
*oa
;
1629 struct top_hash_entry
*en
;
1630 struct area_net
*anet
;
1633 /* Reset old routing table */
1634 FIB_WALK(&p
->rtf
, nftmp
)
1642 /* Reset SPF data in LSA db */
1643 WALK_SLIST(en
, p
->lsal
)
1646 en
->dist
= LSINFINITY
;
1650 if (en
->mode
== LSA_M_RTCALC
)
1651 en
->mode
= LSA_M_STALE
;
1654 WALK_LIST(oa
, p
->area_list
)
1656 /* Reset ASBR routing tables */
1657 FIB_WALK(&oa
->rtr
, nftmp
)
1664 /* Reset condensed area networks */
1667 FIB_WALK(&oa
->net_fib
, nftmp
)
1669 anet
= (struct area_net
*) nftmp
;
1675 FIB_WALK(&oa
->enet_fib
, nftmp
)
1677 anet
= (struct area_net
*) nftmp
;
1687 * ospf_rt_spf - calculate internal routes
1688 * @p: OSPF protocol instance
1690 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1691 * It's based on Dijkstra's shortest path tree algorithms.
1692 * This function is invoked from ospf_disp().
1695 ospf_rt_spf(struct ospf_proto
*p
)
1697 struct ospf_area
*oa
;
1702 OSPF_TRACE(D_EVENTS
, "Starting routing table calculation");
1708 WALK_LIST(oa
, p
->area_list
)
1712 ospf_rt_sum(ospf_main_area(p
));
1715 WALK_LIST(oa
, p
->area_list
)
1716 if (oa
->trcap
&& (oa
->areaid
!= 0))
1729 lp_flush(p
->nhpool
);
1736 inherit_nexthops(struct mpnh
*pn
)
1738 /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1739 return pn
&& (ipa_nonzero(pn
->gw
) || !pn
->iface
);
1742 static struct mpnh
*
1743 calc_next_hop(struct ospf_area
*oa
, struct top_hash_entry
*en
,
1744 struct top_hash_entry
*par
, int pos
)
1746 struct ospf_proto
*p
= oa
->po
;
1747 struct mpnh
*pn
= par
->nhs
;
1748 struct ospf_iface
*ifa
;
1749 u32 rid
= en
->lsa
.rt
;
1751 /* 16.1.1. The next hop calculation */
1752 DBG(" Next hop calculating for id: %R rt: %R type: %u\n",
1753 en
->lsa
.id
, en
->lsa
.rt
, en
->lsa_type
);
1755 /* Usually, we inherit parent nexthops */
1756 if (inherit_nexthops(pn
))
1760 * There are three cases:
1761 * 1) en is a local network (and par is root)
1762 * 2) en is a ptp or ptmp neighbor (and par is root)
1763 * 3) en is a bcast or nbma neighbor (and par is local network)
1766 /* The first case - local network */
1767 if ((en
->lsa_type
== LSA_T_NET
) && (par
== oa
->rt
))
1769 ifa
= rt_pos_to_ifa(oa
, pos
);
1773 return new_nexthop(p
, IPA_NONE
, ifa
->iface
, ifa
->ecmp_weight
);
1776 /* The second case - ptp or ptmp neighbor */
1777 if ((en
->lsa_type
== LSA_T_RT
) && (par
== oa
->rt
))
1779 ifa
= rt_pos_to_ifa(oa
, pos
);
1783 if (ifa
->type
== OSPF_IT_VLINK
)
1784 return new_nexthop(p
, IPA_NONE
, NULL
, 0);
1786 struct ospf_neighbor
*m
= find_neigh(ifa
, rid
);
1787 if (!m
|| (m
->state
!= NEIGHBOR_FULL
))
1790 return new_nexthop(p
, m
->ip
, ifa
->iface
, ifa
->ecmp_weight
);
1793 /* The third case - bcast or nbma neighbor */
1794 if ((en
->lsa_type
== LSA_T_RT
) && (par
->lsa_type
== LSA_T_NET
))
1796 /* par->nhi should be defined from parent's calc_next_hop() */
1803 * In this case, next-hop is the same as link-back, which is
1804 * already computed in link_back().
1806 if (ipa_zero(en
->lb
))
1809 return new_nexthop(p
, en
->lb
, pn
->iface
, pn
->weight
);
1814 * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1815 * is computed in link_back().
1817 struct top_hash_entry
*lhe
;
1818 lhe
= ospf_hash_find(p
->gr
, pn
->iface
->index
, en
->lb_id
, rid
, LSA_T_LINK
);
1823 struct ospf_lsa_link
*llsa
= lhe
->lsa_body
;
1825 if (ipa_zero(llsa
->lladdr
))
1828 return new_nexthop(p
, llsa
->lladdr
, pn
->iface
, pn
->weight
);
1833 /* Probably bug or some race condition, we log it */
1834 log(L_ERR
"Unexpected case in next hop calculation");
1839 /* Add LSA into list of candidates in Dijkstra's algorithm */
1841 add_cand(list
* l
, struct top_hash_entry
*en
, struct top_hash_entry
*par
,
1842 u32 dist
, struct ospf_area
*oa
, int pos
)
1844 struct ospf_proto
*p
= oa
->po
;
1847 struct top_hash_entry
*act
;
1852 if (en
->lsa
.age
== LSA_MAXAGE
)
1855 if (ospf_is_v3(p
) && (en
->lsa_type
== LSA_T_RT
))
1857 /* In OSPFv3, check V6 flag */
1858 struct ospf_lsa_rt
*rt
= en
->lsa_body
;
1859 if (!(rt
->options
& OPT_V6
))
1864 if (en
->color
== INSPF
)
1867 /* 16.1. (2d), also checks that dist < LSINFINITY */
1868 if (dist
> en
->dist
)
1871 /* We should check whether there is a reverse link from en to par, */
1872 if (!link_back(oa
, en
, par
))
1875 struct mpnh
*nhs
= calc_next_hop(oa
, en
, par
, pos
);
1878 log(L_WARN
"Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1879 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
1883 /* We know that en->color == CANDIDATE and en->nhs is defined. */
1885 if ((dist
== en
->dist
) && !nh_is_vlink(en
->nhs
))
1888 * For multipath, we should merge nexthops. We merge regular nexthops only.
1889 * Dummy vlink nexthops are less preferred and handled as a special case.
1891 * During merging, new nexthops (nhs) can be reused if they are not
1892 * inherited from the parent (i.e. they are allocated in calc_next_hop()).
1893 * Current nexthops (en->nhs) can be reused if they weren't inherited in
1894 * previous steps (that is stored in nhs_reuse, i.e. created by merging or
1895 * allocated in calc_next_hop()).
1897 * Generally, a node first inherits shared nexthops from its parent and
1898 * later possibly gets reusable copy during merging.
1902 if (!p
->ecmp
|| nh_is_vlink(nhs
) || (nhs
== en
->nhs
))
1905 /* Merge old and new */
1906 int new_reuse
= (par
->nhs
!= nhs
);
1907 en
->nhs
= merge_nexthops(p
, en
->nhs
, nhs
, en
->nhs_reuse
, new_reuse
);
1912 DBG(" Adding candidate: rt: %R, id: %R, type: %u\n",
1913 en
->lsa
.rt
, en
->lsa
.id
, en
->lsa_type
);
1915 if (en
->color
== CANDIDATE
)
1916 { /* We found a shorter path */
1921 en
->color
= CANDIDATE
;
1922 en
->nhs_reuse
= (par
->nhs
!= nhs
);
1928 add_head(l
, &en
->cn
);
1934 act
= SKIP_BACK(struct top_hash_entry
, cn
, n
);
1935 if ((act
->dist
> dist
) ||
1936 ((act
->dist
== dist
) && (act
->lsa_type
== LSA_T_RT
)))
1939 add_head(l
, &en
->cn
);
1941 insert_node(&en
->cn
, prev
);
1950 add_tail(l
, &en
->cn
);
1956 ort_changed(ort
*nf
, rta
*nr
)
1958 rta
*or = nf
->old_rta
;
1960 (nf
->n
.metric1
!= nf
->old_metric1
) || (nf
->n
.metric2
!= nf
->old_metric2
) ||
1961 (nf
->n
.tag
!= nf
->old_tag
) || (nf
->n
.rid
!= nf
->old_rid
) ||
1962 (nr
->source
!= or->source
) || (nr
->dest
!= or->dest
) ||
1963 (nr
->iface
!= or->iface
) || !ipa_equal(nr
->gw
, or->gw
) ||
1964 !mpnh_same(nr
->nexthops
, or->nexthops
);
1968 rt_sync(struct ospf_proto
*p
)
1970 struct top_hash_entry
*en
;
1971 struct fib_iterator fit
;
1972 struct fib
*fib
= &p
->rtf
;
1974 struct ospf_area
*oa
;
1976 /* This is used for forced reload of routes */
1977 int reload
= (p
->calcrt
== 2);
1979 OSPF_TRACE(D_EVENTS
, "Starting routing table synchronisation");
1981 DBG("Now syncing my rt table with nest's\n");
1982 FIB_ITERATE_INIT(&fit
, fib
);
1984 FIB_ITERATE_START(fib
, &fit
, nftmp
)
1988 /* Sanity check of next-hop addresses, failure should not happen */
1992 for (nh
= nf
->n
.nhs
; nh
; nh
= nh
->next
)
1993 if (ipa_nonzero(nh
->gw
))
1995 neighbor
*ng
= neigh_find2(&p
->p
, &nh
->gw
, nh
->iface
, 0);
1996 if (!ng
|| (ng
->scope
== SCOPE_HOST
))
1997 { reset_ri(nf
); break; }
2001 /* Remove configured stubnets */
2005 if (nf
->n
.type
) /* Add the route */
2008 .src
= p
->p
.main_source
,
2009 .source
= nf
->n
.type
,
2010 .scope
= SCOPE_UNIVERSE
,
2014 if (nf
->n
.nhs
->next
)
2016 a0
.dest
= RTD_MULTIPATH
;
2017 a0
.nexthops
= nf
->n
.nhs
;
2019 else if (ipa_nonzero(nf
->n
.nhs
->gw
))
2021 a0
.dest
= RTD_ROUTER
;
2022 a0
.iface
= nf
->n
.nhs
->iface
;
2023 a0
.gw
= nf
->n
.nhs
->gw
;
2027 a0
.dest
= RTD_DEVICE
;
2028 a0
.iface
= nf
->n
.nhs
->iface
;
2031 if (reload
|| ort_changed(nf
, &a0
))
2033 net
*ne
= net_get(p
->p
.table
, nf
->fn
.prefix
, nf
->fn
.pxlen
);
2034 rta
*a
= rta_lookup(&a0
);
2035 rte
*e
= rte_get_temp(a
);
2037 rta_free(nf
->old_rta
);
2038 nf
->old_rta
= rta_clone(a
);
2039 e
->u
.ospf
.metric1
= nf
->old_metric1
= nf
->n
.metric1
;
2040 e
->u
.ospf
.metric2
= nf
->old_metric2
= nf
->n
.metric2
;
2041 e
->u
.ospf
.tag
= nf
->old_tag
= nf
->n
.tag
;
2042 e
->u
.ospf
.router_id
= nf
->old_rid
= nf
->n
.rid
;
2045 e
->pref
= p
->p
.preference
;
2047 DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
2048 a0
.source
, nf
->fn
.prefix
, nf
->fn
.pxlen
, a0
.gw
, a0
.iface
? a0
.iface
->name
: "(none)", nf
->n
.metric1
);
2049 rte_update(&p
->p
, ne
, e
);
2052 else if (nf
->old_rta
)
2054 /* Remove the route */
2055 rta_free(nf
->old_rta
);
2058 net
*ne
= net_get(p
->p
.table
, nf
->fn
.prefix
, nf
->fn
.pxlen
);
2059 rte_update(&p
->p
, ne
, NULL
);
2062 /* Remove unused rt entry, some special entries are persistent */
2063 if (!nf
->n
.type
&& !nf
->external_rte
&& !nf
->area_net
)
2065 FIB_ITERATE_PUT(&fit
, nftmp
);
2066 fib_delete(fib
, nftmp
);
2070 FIB_ITERATE_END(nftmp
);
2073 WALK_LIST(oa
, p
->area_list
)
2075 /* Cleanup ASBR hash tables */
2076 FIB_ITERATE_INIT(&fit
, &oa
->rtr
);
2078 FIB_ITERATE_START(&oa
->rtr
, &fit
, nftmp
)
2084 FIB_ITERATE_PUT(&fit
, nftmp
);
2085 fib_delete(&oa
->rtr
, nftmp
);
2089 FIB_ITERATE_END(nftmp
);
2092 /* Cleanup stale LSAs */
2093 WALK_SLIST(en
, p
->lsal
)
2094 if (en
->mode
== LSA_M_STALE
)
2095 ospf_flush_lsa(p
, en
);