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