]>
Commit | Line | Data |
---|---|---|
dfa9a53a | 1 | /* |
1a61882d OF |
2 | * BIRD -- OSPF |
3 | * | |
4 | * (c) 2000--2004 Ondrej Filip <feela@network.cz> | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
dfa9a53a OF |
7 | */ |
8 | ||
9 | #include "ospf.h" | |
5d3f5552 | 10 | |
b49e6f5a OZ |
11 | static void add_cand(list * l, struct top_hash_entry *en, |
12 | struct top_hash_entry *par, u32 dist, | |
57c574d8 | 13 | struct ospf_area *oa, struct ospf_lsa_rt_link *rtl); |
1a61882d OF |
14 | static void rt_sync(struct proto_ospf *po); |
15 | ||
c3226991 | 16 | /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address) |
d82fc18d | 17 | as index, so we need to encapsulate RID to IP address */ |
c3226991 OZ |
18 | #ifdef OSPFv2 |
19 | #define ipa_from_rid(x) _MI(x) | |
20 | #else /* OSPFv3 */ | |
21 | #define ipa_from_rid(x) _MI(0,0,0,x) | |
22 | #endif | |
23 | ||
24 | ||
57c574d8 | 25 | static inline void reset_ri(ort *ort) |
1a61882d | 26 | { |
57c574d8 | 27 | bzero(&ort->n, sizeof(orta)); |
1a61882d | 28 | } |
dfa9a53a | 29 | |
a92847e7 | 30 | void |
1a61882d | 31 | ospf_rt_initort(struct fib_node *fn) |
a92847e7 | 32 | { |
1a61882d | 33 | ort *ri = (ort *) fn; |
57c574d8 OZ |
34 | reset_ri(ri); |
35 | ri->old_rta = NULL; | |
6384c7d7 | 36 | ri->fn.x0 = 0; |
1a61882d | 37 | } |
a92847e7 | 38 | |
57c574d8 OZ |
39 | static inline int |
40 | unresolved_vlink(struct mpnh *nhs) | |
41 | { | |
42 | return nhs && !nhs->iface; | |
43 | } | |
44 | ||
45 | static inline struct mpnh * | |
46 | new_nexthop(struct proto_ospf *po, ip_addr gw, struct iface *iface, unsigned char weight) | |
47 | { | |
48 | struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh)); | |
49 | nh->gw = gw; | |
50 | nh->iface = iface; | |
51 | nh->next = NULL; | |
52 | nh->weight = weight; | |
53 | return nh; | |
54 | } | |
55 | ||
56 | static inline struct mpnh * | |
57 | copy_nexthop(struct proto_ospf *po, struct mpnh *src) | |
58 | { | |
59 | struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh)); | |
60 | nh->gw = src->gw; | |
61 | nh->iface = src->iface; | |
62 | nh->next = NULL; | |
63 | nh->weight = src->weight; | |
64 | return nh; | |
65 | } | |
66 | ||
98ac6176 | 67 | |
3b89a232 | 68 | /* If new is better return 1 */ |
1a61882d | 69 | static int |
3b89a232 | 70 | ri_better(struct proto_ospf *po, orta *new, orta *old) |
1a61882d | 71 | { |
1a61882d OF |
72 | if (old->type == RTS_DUMMY) |
73 | return 1; | |
74 | ||
3b89a232 OZ |
75 | if (new->type < old->type) |
76 | return 1; | |
77 | ||
78 | if (new->type > old->type) | |
79 | return 0; | |
80 | ||
81 | if (new->metric1 < old->metric1) | |
82 | return 1; | |
83 | ||
84 | if (new->metric1 > old->metric1) | |
85 | return 0; | |
86 | ||
87 | return 0; | |
88 | } | |
89 | ||
90 | ||
6384c7d7 OZ |
91 | /* Whether the ASBR or the forward address destination is preferred |
92 | in AS external route selection according to 16.4.1. */ | |
93 | static inline int | |
94 | epath_preferred(orta *ep) | |
95 | { | |
96 | return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0); | |
97 | } | |
98 | ||
3b89a232 OZ |
99 | /* 16.4. (3), return 1 if new is better */ |
100 | static int | |
101 | ri_better_asbr(struct proto_ospf *po, orta *new, orta *old) | |
102 | { | |
6384c7d7 OZ |
103 | if (old->type == RTS_DUMMY) |
104 | return 1; | |
3b89a232 OZ |
105 | |
106 | if (!po->rfc1583) | |
1a61882d | 107 | { |
3b89a232 OZ |
108 | int new_pref = epath_preferred(new); |
109 | int old_pref = epath_preferred(old); | |
110 | ||
111 | if (new_pref > old_pref) | |
112 | return 1; | |
113 | ||
114 | if (new_pref < old_pref) | |
115 | return 0; | |
3b16080c | 116 | } |
98ac6176 | 117 | |
3b89a232 | 118 | if (new->metric1 < old->metric1) |
1a61882d OF |
119 | return 1; |
120 | ||
3b89a232 | 121 | if (new->metric1 > old->metric1) |
98ac6176 | 122 | return 0; |
1a61882d | 123 | |
3b89a232 OZ |
124 | /* Larger area ID is preferred */ |
125 | if (new->oa->areaid > old->oa->areaid) | |
126 | return 1; | |
127 | ||
128 | return 0; | |
129 | } | |
130 | ||
131 | /* 16.4. (6), return 1 if new is better */ | |
132 | static int | |
133 | ri_better_ext(struct proto_ospf *po, orta *new, orta *old) | |
134 | { | |
135 | if (old->type == RTS_DUMMY) | |
136 | return 1; | |
137 | ||
3b89a232 OZ |
138 | /* 16.4. (6a) */ |
139 | if (new->type < old->type) | |
140 | return 1; | |
141 | ||
142 | if (new->type > old->type) | |
143 | return 0; | |
144 | ||
145 | /* 16.4. (6b), same type */ | |
a2d5b405 | 146 | if (new->type == RTS_OSPF_EXT2) |
98ac6176 | 147 | { |
3b89a232 OZ |
148 | if (new->metric2 < old->metric2) |
149 | return 1; | |
150 | ||
151 | if (new->metric2 > old->metric2) | |
152 | return 0; | |
1a61882d | 153 | } |
98ac6176 | 154 | |
3b89a232 OZ |
155 | /* 16.4. (6c) */ |
156 | if (!po->rfc1583) | |
1a61882d | 157 | { |
3b89a232 OZ |
158 | u32 new_pref = new->options & ORTA_PREF; |
159 | u32 old_pref = old->options & ORTA_PREF; | |
98ac6176 | 160 | |
3b89a232 OZ |
161 | if (new_pref > old_pref) |
162 | return 1; | |
1a61882d | 163 | |
3b89a232 OZ |
164 | if (new_pref < old_pref) |
165 | return 0; | |
1a61882d OF |
166 | } |
167 | ||
3b89a232 | 168 | /* 16.4. (6d) */ |
1a61882d OF |
169 | if (new->metric1 < old->metric1) |
170 | return 1; | |
171 | ||
172 | if (new->metric1 > old->metric1) | |
173 | return 0; | |
174 | ||
3b89a232 OZ |
175 | return 0; |
176 | } | |
1a61882d | 177 | |
3b89a232 OZ |
178 | static inline void |
179 | ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new) | |
180 | { | |
181 | ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen); | |
182 | if (ri_better(po, new, &old->n)) | |
183 | memcpy(&old->n, new, sizeof(orta)); | |
a92847e7 OF |
184 | } |
185 | ||
3b89a232 OZ |
186 | static inline void |
187 | ri_install_rt(struct ospf_area *oa, u32 rid, orta *new) | |
aa1e082c | 188 | { |
3b89a232 OZ |
189 | ip_addr addr = ipa_from_rid(rid); |
190 | ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH); | |
191 | if (ri_better(oa->po, new, &old->n)) | |
192 | memcpy(&old->n, new, sizeof(orta)); | |
193 | } | |
1a61882d | 194 | |
3b89a232 | 195 | static inline void |
6384c7d7 | 196 | ri_install_asbr(struct proto_ospf *po, ip_addr *addr, orta *new) |
3b89a232 | 197 | { |
6384c7d7 OZ |
198 | ort *old = (ort *) fib_get(&po->backbone->rtr, addr, MAX_PREFIX_LENGTH); |
199 | if (ri_better_asbr(po, new, &old->n)) | |
3b89a232 OZ |
200 | memcpy(&old->n, new, sizeof(orta)); |
201 | } | |
98ac6176 | 202 | |
3b89a232 | 203 | static inline void |
6384c7d7 | 204 | ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new) |
3b89a232 | 205 | { |
6384c7d7 OZ |
206 | ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen); |
207 | if (ri_better_ext(po, new, &old->n)) | |
208 | memcpy(&old->n, new, sizeof(orta)); | |
aa1e082c OF |
209 | } |
210 | ||
3b89a232 | 211 | |
e60d55be OZ |
212 | #ifdef OSPFv2 |
213 | ||
214 | static struct ospf_iface * | |
215 | find_stub_src(struct ospf_area *oa, ip_addr px, int pxlen) | |
216 | { | |
217 | struct ospf_iface *iff; | |
e60d55be OZ |
218 | |
219 | WALK_LIST(iff, oa->po->iface_list) | |
220 | if ((iff->type != OSPF_IT_VLINK) && | |
221 | (iff->oa == oa) && | |
b8113a5e | 222 | ipa_equal(iff->addr->prefix, px) && |
e60d55be OZ |
223 | (iff->addr->pxlen == pxlen)) |
224 | return iff; | |
225 | ||
226 | return NULL; | |
227 | } | |
228 | ||
229 | #else /* OSPFv3 */ | |
230 | ||
231 | static struct ospf_iface * | |
232 | find_stub_src(struct ospf_area *oa, ip_addr px, int pxlen) | |
233 | { | |
234 | struct ospf_iface *iff; | |
235 | struct ifa *a; | |
236 | ||
237 | WALK_LIST(iff, oa->po->iface_list) | |
238 | if ((iff->type != OSPF_IT_VLINK) && | |
239 | (iff->oa == oa)) | |
240 | WALK_LIST(a, iff->iface->addrs) | |
241 | if (ipa_equal(a->prefix, px) && | |
242 | (a->pxlen == pxlen) && | |
243 | !(a->flags & IA_SECONDARY)) | |
244 | return iff; | |
245 | ||
246 | return NULL; | |
247 | } | |
248 | ||
249 | #endif | |
250 | ||
b49e6f5a OZ |
251 | static void |
252 | add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en) | |
253 | { | |
3b89a232 OZ |
254 | orta nf = { |
255 | .type = RTS_OSPF, | |
256 | .options = 0, | |
257 | .metric1 = metric, | |
258 | .metric2 = LSINFINITY, | |
259 | .tag = 0, | |
260 | .rid = en->lsa.rt, | |
261 | .oa = oa, | |
57c574d8 | 262 | .nhs = en->nhs |
3b89a232 | 263 | }; |
b49e6f5a | 264 | |
e60d55be OZ |
265 | if (en == oa->rt) |
266 | { | |
267 | /* | |
268 | * Local stub networks does not have proper iface in en->nhi | |
269 | * (because they all have common top_hash_entry en). | |
270 | * We have to find iface responsible for that stub network. | |
e0a62ad0 OZ |
271 | * Configured stubnets does not have any iface. They will |
272 | * be removed in rt_sync(). | |
e60d55be OZ |
273 | */ |
274 | ||
57c574d8 OZ |
275 | struct ospf_iface *ifa = find_stub_src(oa, px, pxlen); |
276 | nf.nhs = ifa ? new_nexthop(oa->po, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL; | |
e60d55be OZ |
277 | } |
278 | ||
3b89a232 | 279 | ri_install_net(oa->po, px, pxlen, &nf); |
b49e6f5a OZ |
280 | } |
281 | ||
282 | #ifdef OSPFv3 | |
283 | static void | |
284 | process_prefixes(struct ospf_area *oa) | |
285 | { | |
286 | struct proto_ospf *po = oa->po; | |
ff2857b0 | 287 | // struct proto *p = &po->proto; |
b49e6f5a OZ |
288 | struct top_hash_entry *en, *src; |
289 | struct ospf_lsa_prefix *px; | |
290 | ip_addr pxa; | |
291 | int pxlen; | |
292 | u8 pxopts; | |
293 | u16 metric; | |
294 | u32 *buf; | |
295 | int i; | |
296 | ||
297 | WALK_SLIST(en, po->lsal) | |
298 | { | |
299 | if (en->lsa.type != LSA_T_PREFIX) | |
300 | continue; | |
301 | ||
302 | if (en->domain != oa->areaid) | |
303 | continue; | |
304 | ||
305 | if (en->lsa.age == LSA_MAXAGE) | |
306 | continue; | |
307 | ||
308 | px = en->lsa_body; | |
9f0ba7b1 OZ |
309 | |
310 | /* For router prefix-LSA, we would like to find the first router-LSA */ | |
311 | if (px->ref_type == LSA_T_RT) | |
312 | src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt); | |
313 | else | |
314 | src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type); | |
b49e6f5a OZ |
315 | |
316 | if (!src) | |
317 | continue; | |
318 | ||
3b89a232 OZ |
319 | /* Reachable in SPF */ |
320 | if (src->color != INSPF) | |
321 | continue; | |
322 | ||
b49e6f5a OZ |
323 | if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET)) |
324 | continue; | |
325 | ||
326 | buf = px->rest; | |
327 | for (i = 0; i < px->pxcount; i++) | |
328 | { | |
b66abe8e | 329 | buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric); |
b49e6f5a OZ |
330 | |
331 | if (pxopts & OPT_PX_NU) | |
332 | continue; | |
333 | ||
3b89a232 OZ |
334 | /* Store the first global address to use it later as a vlink endpoint */ |
335 | if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb)) | |
336 | src->lb = pxa; | |
337 | ||
b49e6f5a OZ |
338 | add_network(oa, pxa, pxlen, src->dist + metric, src); |
339 | } | |
340 | } | |
341 | } | |
342 | #endif | |
343 | ||
9f0ba7b1 OZ |
344 | |
345 | static void | |
346 | ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en) | |
347 | { | |
e81b440f | 348 | // struct proto *p = &oa->po->proto; |
9f0ba7b1 | 349 | struct proto_ospf *po = oa->po; |
9f0ba7b1 OZ |
350 | u32 i; |
351 | ||
352 | struct ospf_lsa_rt *rt = en->lsa_body; | |
353 | struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1); | |
354 | ||
355 | for (i = 0; i < lsa_rt_count(&en->lsa); i++) | |
356 | { | |
357 | struct ospf_lsa_rt_link *rtl = rr + i; | |
358 | struct top_hash_entry *tmp = NULL; | |
359 | ||
360 | DBG(" Working on link: %R (type: %u) ", rtl->id, rtl->type); | |
361 | switch (rtl->type) | |
362 | { | |
363 | #ifdef OSPFv2 | |
364 | case LSART_STUB: | |
6d04ef89 OZ |
365 | /* |
366 | * RFC 2328 in 16.1. (2a) says to handle stub networks in an | |
367 | * second phase after the SPF for an area is calculated. We get | |
368 | * the same result by handing them here because add_network() | |
369 | * will keep the best (not the first) found route. | |
370 | */ | |
e60d55be OZ |
371 | add_network(oa, ipa_from_u32(rtl->id), |
372 | ipa_mklen(ipa_from_u32(rtl->data)), | |
373 | act->dist + rtl->metric, act); | |
9f0ba7b1 OZ |
374 | break; |
375 | #endif | |
376 | ||
377 | case LSART_NET: | |
378 | #ifdef OSPFv2 | |
379 | /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */ | |
380 | tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id); | |
381 | #else /* OSPFv3 */ | |
382 | tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET); | |
383 | #endif | |
9f0ba7b1 OZ |
384 | break; |
385 | ||
386 | case LSART_VLNK: | |
387 | case LSART_PTP: | |
388 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); | |
9f0ba7b1 | 389 | break; |
e60d55be | 390 | |
9f0ba7b1 OZ |
391 | default: |
392 | log("Unknown link type in router lsa. (rid = %R)", act->lsa.id); | |
393 | break; | |
394 | } | |
e60d55be | 395 | |
9f0ba7b1 OZ |
396 | if (tmp) |
397 | DBG("Going to add cand, Mydist: %u, Req: %u\n", | |
398 | tmp->dist, act->dist + rtl->metric); | |
57c574d8 | 399 | add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, rtl); |
9f0ba7b1 OZ |
400 | } |
401 | } | |
402 | ||
3b89a232 | 403 | /* RFC 2328 16.1. calculating shortest paths for an area */ |
1a61882d | 404 | static void |
a02c6c18 | 405 | ospf_rt_spfa(struct ospf_area *oa) |
dfa9a53a | 406 | { |
2e10a170 OF |
407 | struct proto *p = &oa->po->proto; |
408 | struct proto_ospf *po = oa->po; | |
9f0ba7b1 | 409 | struct ospf_lsa_rt *rt; |
d345cda5 | 410 | struct ospf_lsa_net *ln; |
98ac6176 | 411 | struct top_hash_entry *act, *tmp; |
9f0ba7b1 | 412 | u32 i, *rts; |
98ac6176 OF |
413 | node *n; |
414 | ||
2e10a170 OF |
415 | if (oa->rt == NULL) |
416 | return; | |
102e3e0e | 417 | |
3aab39f5 | 418 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid); |
1a61882d | 419 | |
c3226991 | 420 | /* 16.1. (1) */ |
dfa9a53a | 421 | init_list(&oa->cand); /* Empty list of candidates */ |
2e10a170 | 422 | oa->trcap = 0; |
dfa9a53a | 423 | |
85195f1a OF |
424 | DBG("LSA db prepared, adding me into candidate list.\n"); |
425 | ||
2e10a170 OF |
426 | oa->rt->dist = 0; |
427 | oa->rt->color = CANDIDATE; | |
85195f1a | 428 | add_head(&oa->cand, &oa->rt->cn); |
3aab39f5 OZ |
429 | DBG("RT LSA: rt: %R, id: %R, type: %u\n", |
430 | oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type); | |
dfa9a53a | 431 | |
2e10a170 | 432 | while (!EMPTY_LIST(oa->cand)) |
dfa9a53a | 433 | { |
2e10a170 OF |
434 | n = HEAD(oa->cand); |
435 | act = SKIP_BACK(struct top_hash_entry, cn, n); | |
dfa9a53a | 436 | rem_node(n); |
dfa9a53a | 437 | |
3aab39f5 OZ |
438 | DBG("Working on LSA: rt: %R, id: %R, type: %u\n", |
439 | act->lsa.rt, act->lsa.id, act->lsa.type); | |
85195f1a | 440 | |
2e10a170 OF |
441 | act->color = INSPF; |
442 | switch (act->lsa.type) | |
dfa9a53a | 443 | { |
2e10a170 OF |
444 | case LSA_T_RT: |
445 | rt = (struct ospf_lsa_rt *) act->lsa_body; | |
c3226991 | 446 | if (rt->options & OPT_RT_V) |
2e10a170 | 447 | oa->trcap = 1; |
b49e6f5a | 448 | |
3b89a232 OZ |
449 | /* |
450 | * In OSPFv3, all routers are added to per-area routing | |
451 | * tables. But we use it just for ASBRs and ABRs. For the | |
452 | * purpose of the last step in SPF - prefix-LSA processing in | |
453 | * process_prefixes(), we use information stored in LSA db. | |
454 | */ | |
6384c7d7 OZ |
455 | if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B)) |
456 | && (act->lsa.rt != po->router_id)) | |
3b89a232 OZ |
457 | { |
458 | orta nf = { | |
459 | .type = RTS_OSPF, | |
460 | .options = rt->options, | |
461 | .metric1 = act->dist, | |
462 | .metric2 = LSINFINITY, | |
463 | .tag = 0, | |
464 | .rid = act->lsa.rt, | |
465 | .oa = oa, | |
57c574d8 | 466 | .nhs = act->nhs |
3b89a232 OZ |
467 | }; |
468 | ri_install_rt(oa, act->lsa.rt, &nf); | |
469 | } | |
b49e6f5a | 470 | |
c3226991 | 471 | #ifdef OSPFv2 |
9f0ba7b1 | 472 | ospf_rt_spfa_rtlinks(oa, act, act); |
c3226991 | 473 | #else /* OSPFv3 */ |
9f0ba7b1 OZ |
474 | for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt); |
475 | tmp; tmp = ospf_hash_find_rt_next(tmp)) | |
476 | ospf_rt_spfa_rtlinks(oa, act, tmp); | |
c3226991 | 477 | #endif |
b49e6f5a | 478 | |
2e10a170 OF |
479 | break; |
480 | case LSA_T_NET: | |
481 | ln = act->lsa_body; | |
b49e6f5a OZ |
482 | |
483 | #ifdef OSPFv2 | |
484 | add_network(oa, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask), | |
485 | ipa_mklen(ln->netmask), act->dist, act); | |
486 | #endif | |
1a61882d | 487 | |
2e10a170 | 488 | rts = (u32 *) (ln + 1); |
c3226991 | 489 | for (i = 0; i < lsa_net_count(&act->lsa); i++) |
2e10a170 | 490 | { |
3aab39f5 | 491 | DBG(" Working on router %R ", rts[i]); |
9f0ba7b1 | 492 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); |
2e10a170 OF |
493 | if (tmp != NULL) |
494 | DBG("Found :-)\n"); | |
495 | else | |
496 | DBG("Not found!\n"); | |
57c574d8 | 497 | add_cand(&oa->cand, tmp, act, act->dist, oa, NULL); |
2e10a170 OF |
498 | } |
499 | break; | |
dfa9a53a | 500 | } |
d345cda5 | 501 | } |
98ac6176 | 502 | |
b49e6f5a OZ |
503 | #ifdef OSPFv3 |
504 | process_prefixes(oa); | |
505 | #endif | |
98ac6176 OF |
506 | } |
507 | ||
508 | static int | |
9807690b | 509 | link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par) |
98ac6176 OF |
510 | { |
511 | u32 i, *rts; | |
512 | struct ospf_lsa_net *ln; | |
513 | struct ospf_lsa_rt *rt; | |
514 | struct ospf_lsa_rt_link *rtl, *rr; | |
9807690b | 515 | struct top_hash_entry *tmp; |
86c84d76 | 516 | struct proto_ospf *po = oa->po; |
98ac6176 | 517 | |
9807690b OZ |
518 | if (!en || !par) return 0; |
519 | ||
3b89a232 OZ |
520 | /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here, |
521 | it is set in process_prefixes() to any global addres in the area */ | |
522 | ||
9807690b | 523 | en->lb = IPA_NONE; |
6e806760 OZ |
524 | #ifdef OSPFv3 |
525 | en->lb_id = 0; | |
526 | #endif | |
9807690b | 527 | switch (en->lsa.type) |
98ac6176 OF |
528 | { |
529 | case LSA_T_RT: | |
9807690b | 530 | rt = (struct ospf_lsa_rt *) en->lsa_body; |
98ac6176 | 531 | rr = (struct ospf_lsa_rt_link *) (rt + 1); |
9807690b | 532 | for (i = 0; i < lsa_rt_count(&en->lsa); i++) |
98ac6176 OF |
533 | { |
534 | rtl = (rr + i); | |
535 | switch (rtl->type) | |
536 | { | |
537 | case LSART_STUB: | |
538 | break; | |
539 | case LSART_NET: | |
9807690b OZ |
540 | #ifdef OSPFv2 |
541 | /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */ | |
542 | tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id); | |
543 | #else /* OSPFv3 */ | |
544 | tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET); | |
545 | #endif | |
546 | if (tmp == par) | |
ba39197c OZ |
547 | { |
548 | #ifdef OSPFv2 | |
cf0858c2 | 549 | en->lb = ipa_from_u32(rtl->data); |
6e806760 OZ |
550 | #else /* OSPFv3 */ |
551 | en->lb_id = rtl->lif; | |
ba39197c OZ |
552 | #endif |
553 | return 1; | |
554 | } | |
9807690b | 555 | |
98ac6176 OF |
556 | break; |
557 | case LSART_VLNK: | |
558 | case LSART_PTP: | |
9807690b OZ |
559 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); |
560 | if (tmp == par) | |
98ac6176 | 561 | return 1; |
9807690b | 562 | |
98ac6176 OF |
563 | break; |
564 | default: | |
9807690b | 565 | log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt); |
98ac6176 OF |
566 | break; |
567 | } | |
568 | } | |
569 | break; | |
570 | case LSA_T_NET: | |
9807690b | 571 | ln = en->lsa_body; |
98ac6176 | 572 | rts = (u32 *) (ln + 1); |
9807690b | 573 | for (i = 0; i < lsa_net_count(&en->lsa); i++) |
98ac6176 | 574 | { |
9807690b OZ |
575 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); |
576 | if (tmp == par) | |
98ac6176 | 577 | return 1; |
98ac6176 OF |
578 | } |
579 | break; | |
580 | default: | |
9807690b | 581 | bug("Unknown lsa type %x.", en->lsa.type); |
98ac6176 OF |
582 | } |
583 | return 0; | |
584 | } | |
585 | ||
3b89a232 OZ |
586 | |
587 | /* RFC 2328 16.2. calculating inter-area routes */ | |
98ac6176 | 588 | static void |
3b89a232 | 589 | ospf_rt_sum(struct ospf_area *oa) |
98ac6176 | 590 | { |
98ac6176 | 591 | struct proto_ospf *po = oa->po; |
3b89a232 | 592 | struct proto *p = &po->proto; |
98ac6176 | 593 | struct top_hash_entry *en; |
3b89a232 OZ |
594 | ip_addr ip = IPA_NONE; |
595 | u32 dst_rid = 0; | |
596 | u32 metric, options; | |
3b89a232 | 597 | ort *abr; |
c3226991 | 598 | int pxlen = -1, type = -1; |
98ac6176 | 599 | |
3b89a232 | 600 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid); |
98ac6176 | 601 | |
86c84d76 | 602 | WALK_SLIST(en, po->lsal) |
98ac6176 | 603 | { |
c3226991 | 604 | if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) |
86c84d76 | 605 | continue; |
c3226991 OZ |
606 | |
607 | if (en->domain != oa->areaid) | |
608 | continue; | |
609 | ||
3b89a232 | 610 | /* 16.2. (1a) */ |
98ac6176 OF |
611 | if (en->lsa.age == LSA_MAXAGE) |
612 | continue; | |
c3226991 | 613 | |
3b89a232 | 614 | /* 16.2. (2) */ |
8a70a13e | 615 | if (en->lsa.rt == po->router_id) |
98ac6176 OF |
616 | continue; |
617 | ||
6384c7d7 | 618 | /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */ |
3b89a232 | 619 | |
98ac6176 OF |
620 | if (en->lsa.type == LSA_T_SUM_NET) |
621 | { | |
c3226991 OZ |
622 | #ifdef OSPFv2 |
623 | struct ospf_lsa_sum *ls = en->lsa_body; | |
624 | pxlen = ipa_mklen(ls->netmask); | |
625 | ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask); | |
626 | #else /* OSPFv3 */ | |
627 | u8 pxopts; | |
b49e6f5a | 628 | u16 rest; |
c3226991 | 629 | struct ospf_lsa_sum_net *ls = en->lsa_body; |
b66abe8e | 630 | lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest); |
b49e6f5a | 631 | |
c3226991 OZ |
632 | if (pxopts & OPT_PX_NU) |
633 | continue; | |
634 | #endif | |
635 | ||
636 | metric = ls->metric & METRIC_MASK; | |
637 | options = 0; | |
98ac6176 | 638 | type = ORT_NET; |
98ac6176 | 639 | } |
3b89a232 | 640 | else /* LSA_T_SUM_RT */ |
98ac6176 | 641 | { |
c3226991 OZ |
642 | #ifdef OSPFv2 |
643 | struct ospf_lsa_sum *ls = en->lsa_body; | |
644 | dst_rid = en->lsa.id; | |
645 | options = 0; | |
646 | #else /* OSPFv3 */ | |
647 | struct ospf_lsa_sum_rt *ls = en->lsa_body; | |
648 | dst_rid = ls->drid; | |
649 | options = ls->options & OPTIONS_MASK; | |
650 | #endif | |
6384c7d7 OZ |
651 | |
652 | /* We don't want local router in ASBR routing table */ | |
653 | if (dst_rid == po->router_id) | |
654 | continue; | |
c3226991 | 655 | |
c3226991 OZ |
656 | metric = ls->metric & METRIC_MASK; |
657 | options |= ORTA_ASBR; | |
98ac6176 | 658 | type = ORT_ROUTER; |
98ac6176 | 659 | } |
c3226991 | 660 | |
3b89a232 OZ |
661 | /* 16.2. (1b) */ |
662 | if (metric == LSINFINITY) | |
663 | continue; | |
99f5fc14 | 664 | |
3b89a232 OZ |
665 | /* 16.2. (4) */ |
666 | ip_addr abrip = ipa_from_rid(en->lsa.rt); | |
667 | abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); | |
668 | if (!abr || !abr->n.type) | |
669 | continue; | |
98ac6176 | 670 | |
3b89a232 OZ |
671 | if (!(abr->n.options & ORTA_ABR)) |
672 | continue; | |
673 | ||
0ea8fb4a OZ |
674 | /* This check is not mentioned in RFC 2328 */ |
675 | if (abr->n.type != RTS_OSPF) | |
676 | continue; | |
677 | ||
3b89a232 OZ |
678 | /* 16.2. (5) */ |
679 | orta nf = { | |
680 | .type = RTS_OSPF_IA, | |
681 | .options = options, | |
682 | .metric1 = abr->n.metric1 + metric, | |
683 | .metric2 = LSINFINITY, | |
684 | .tag = 0, | |
685 | .rid = en->lsa.rt, /* ABR ID */ | |
686 | .oa = oa, | |
57c574d8 | 687 | .nhs = abr->n.nhs |
3b89a232 OZ |
688 | }; |
689 | ||
690 | if (type == ORT_NET) | |
691 | ri_install_net(po, ip, pxlen, &nf); | |
692 | else | |
693 | ri_install_rt(oa, dst_rid, &nf); | |
98ac6176 | 694 | } |
fafe44b6 | 695 | } |
3b89a232 OZ |
696 | |
697 | /* RFC 2328 16.3. examining summary-LSAs in transit areas */ | |
98ac6176 | 698 | static void |
3b89a232 | 699 | ospf_rt_sum_tr(struct ospf_area *oa) |
98ac6176 | 700 | { |
3b89a232 | 701 | // struct proto *p = &oa->po->proto; |
98ac6176 | 702 | struct proto_ospf *po = oa->po; |
3b89a232 | 703 | struct ospf_area *bb = po->backbone; |
6384c7d7 | 704 | ip_addr abrip; |
98ac6176 | 705 | struct top_hash_entry *en; |
6384c7d7 | 706 | u32 dst_rid, metric; |
3b89a232 | 707 | ort *re = NULL, *abr; |
fafe44b6 | 708 | |
3b89a232 OZ |
709 | |
710 | if (!bb) return; | |
b8f17cf1 | 711 | |
86c84d76 | 712 | WALK_SLIST(en, po->lsal) |
98ac6176 | 713 | { |
c3226991 OZ |
714 | if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) |
715 | continue; | |
716 | ||
717 | if (en->domain != oa->areaid) | |
86c84d76 | 718 | continue; |
c3226991 | 719 | |
3b89a232 | 720 | /* 16.3 (1a) */ |
98ac6176 OF |
721 | if (en->lsa.age == LSA_MAXAGE) |
722 | continue; | |
c3226991 | 723 | |
3b89a232 | 724 | /* 16.3 (2) */ |
8a70a13e | 725 | if (en->lsa.rt == po->router_id) |
98ac6176 OF |
726 | continue; |
727 | ||
98ac6176 OF |
728 | if (en->lsa.type == LSA_T_SUM_NET) |
729 | { | |
6384c7d7 OZ |
730 | ip_addr ip; |
731 | int pxlen; | |
c3226991 OZ |
732 | #ifdef OSPFv2 |
733 | struct ospf_lsa_sum *ls = en->lsa_body; | |
734 | pxlen = ipa_mklen(ls->netmask); | |
735 | ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask); | |
736 | #else /* OSPFv3 */ | |
737 | u8 pxopts; | |
b49e6f5a | 738 | u16 rest; |
c3226991 | 739 | struct ospf_lsa_sum_net *ls = en->lsa_body; |
b66abe8e | 740 | lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest); |
b49e6f5a | 741 | |
c3226991 OZ |
742 | if (pxopts & OPT_PX_NU) |
743 | continue; | |
744 | #endif | |
745 | ||
746 | metric = ls->metric & METRIC_MASK; | |
3b89a232 | 747 | re = fib_find(&po->rtf, &ip, pxlen); |
98ac6176 | 748 | } |
3b89a232 | 749 | else // en->lsa.type == LSA_T_SUM_RT |
98ac6176 | 750 | { |
c3226991 OZ |
751 | #ifdef OSPFv2 |
752 | struct ospf_lsa_sum *ls = en->lsa_body; | |
753 | dst_rid = en->lsa.id; | |
c3226991 OZ |
754 | #else /* OSPFv3 */ |
755 | struct ospf_lsa_sum_rt *ls = en->lsa_body; | |
756 | dst_rid = ls->drid; | |
c3226991 OZ |
757 | #endif |
758 | ||
c3226991 | 759 | metric = ls->metric & METRIC_MASK; |
6384c7d7 OZ |
760 | ip_addr ip = ipa_from_rid(dst_rid); |
761 | re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH); | |
98ac6176 | 762 | } |
98ac6176 | 763 | |
3b89a232 OZ |
764 | /* 16.3 (1b) */ |
765 | if (metric == LSINFINITY) | |
766 | continue; | |
1a61882d | 767 | |
3b89a232 OZ |
768 | /* 16.3 (3) */ |
769 | if (!re || !re->n.type) | |
770 | continue; | |
86c84d76 | 771 | |
3b89a232 OZ |
772 | if (re->n.oa->areaid != 0) |
773 | continue; | |
1a61882d | 774 | |
3b89a232 OZ |
775 | if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) |
776 | continue; | |
1a61882d | 777 | |
3b89a232 OZ |
778 | /* 16.3. (4) */ |
779 | abrip = ipa_from_rid(en->lsa.rt); | |
780 | abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); | |
781 | if (!abr || !abr->n.type) | |
782 | continue; | |
1a61882d | 783 | |
3b89a232 | 784 | metric = abr->n.metric1 + metric; /* IAC */ |
98ac6176 | 785 | |
3b89a232 | 786 | /* 16.3. (5) */ |
57c574d8 OZ |
787 | if ((metric < re->n.metric1) || |
788 | ((metric == re->n.metric1) && unresolved_vlink(re->n.nhs))) | |
98ac6176 | 789 | { |
3b89a232 | 790 | /* We want to replace the next-hop even if the metric is equal |
57c574d8 OZ |
791 | to replace a virtual next-hop through vlink with a real one. |
792 | Proper ECMP would merge nexthops here, but we do not do that. | |
793 | We restrict nexthops to fit one area to simplify check | |
794 | 12.4.3 p4 in decide_sum_lsa() */ | |
795 | ||
3b89a232 | 796 | re->n.metric1 = metric; |
57c574d8 OZ |
797 | re->n.voa = oa; |
798 | re->n.nhs = abr->n.nhs; | |
98ac6176 | 799 | } |
98ac6176 | 800 | } |
3b89a232 | 801 | } |
1a61882d | 802 | |
6384c7d7 OZ |
803 | /* Decide about originating or flushing summary LSAs for condended area networks */ |
804 | static int | |
805 | decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa) | |
806 | { | |
807 | if (oa->stub) | |
808 | return 0; | |
809 | ||
810 | if (oa == anet_oa) | |
811 | return 0; | |
812 | ||
813 | /* Do not condense routing info when exporting from backbone to the transit area */ | |
814 | if ((anet_oa == oa->po->backbone) && oa->trcap) | |
815 | return 0; | |
816 | ||
817 | return (anet->active && !anet->hidden); | |
818 | } | |
819 | ||
820 | /* Decide about originating or flushing summary LSAs (12.4.3) */ | |
821 | static int | |
822 | decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest) | |
823 | { | |
824 | /* 12.4.3.1. - do not send summary into stub areas, we send just default route */ | |
825 | if (oa->stub) | |
826 | return 0; | |
827 | ||
828 | /* Invalid field - no route */ | |
829 | if (!nf->n.type) | |
830 | return 0; | |
831 | ||
832 | /* 12.4.3 p2 */ | |
833 | if (nf->n.type > RTS_OSPF_IA) | |
834 | return 0; | |
835 | ||
836 | /* 12.4.3 p3 */ | |
837 | if ((nf->n.oa->areaid == oa->areaid)) | |
838 | return 0; | |
839 | ||
840 | /* 12.4.3 p4 */ | |
57c574d8 | 841 | if (nf->n.voa && (nf->n.voa->areaid == oa->areaid)) |
6384c7d7 OZ |
842 | return 0; |
843 | ||
844 | /* 12.4.3 p5 */ | |
845 | if (nf->n.metric1 >= LSINFINITY) | |
846 | return 0; | |
847 | ||
848 | /* 12.4.3 p6 - AS boundary router */ | |
849 | if (dest == ORT_ROUTER) | |
850 | { | |
851 | /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */ | |
852 | /* 12.4.3 p1 */ | |
853 | return (nf->n.options & ORTA_ASBR); | |
854 | } | |
855 | ||
856 | /* 12.4.3 p7 - inter-area route */ | |
857 | if (nf->n.type == RTS_OSPF_IA) | |
858 | { | |
859 | /* Inter-area routes are not repropagated into the backbone */ | |
860 | return (oa != oa->po->backbone); | |
861 | } | |
862 | ||
863 | /* 12.4.3 p8 - intra-area route */ | |
864 | ||
865 | /* Do not condense routing info when exporting from backbone to the transit area */ | |
866 | if ((nf->n.oa == oa->po->backbone) && oa->trcap) | |
867 | return 1; | |
868 | ||
869 | struct area_net *anet = (struct area_net *) | |
870 | fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen); | |
871 | ||
872 | /* Condensed area network found */ | |
873 | if (anet) | |
874 | return 0; | |
875 | ||
876 | return 1; | |
877 | } | |
878 | ||
879 | /* RFC 2328 16.7. p1 - originate or flush summary LSAs */ | |
880 | static inline void | |
881 | check_sum_net_lsa(struct proto_ospf *po, ort *nf) | |
882 | { | |
883 | struct area_net *anet = NULL; | |
9b061f7e | 884 | struct ospf_area *anet_oa = NULL; |
6384c7d7 OZ |
885 | |
886 | /* RT entry marked as area network */ | |
887 | if (nf->fn.x0) | |
888 | { | |
889 | /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */ | |
890 | if (nf->fn.pxlen == 0) | |
891 | return; | |
892 | ||
893 | /* Find that area network */ | |
894 | WALK_LIST(anet_oa, po->area_list) | |
895 | { | |
896 | anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen); | |
897 | if (anet) | |
898 | break; | |
899 | } | |
900 | } | |
901 | ||
902 | struct ospf_area *oa; | |
903 | WALK_LIST(oa, po->area_list) | |
904 | { | |
905 | if (anet && decide_anet_lsa(oa, anet, anet_oa)) | |
906 | originate_sum_net_lsa(oa, &nf->fn, anet->metric); | |
907 | else if (decide_sum_lsa(oa, nf, ORT_NET)) | |
908 | originate_sum_net_lsa(oa, &nf->fn, nf->n.metric1); | |
909 | else | |
910 | flush_sum_lsa(oa, &nf->fn, ORT_NET); | |
911 | } | |
912 | } | |
913 | ||
914 | static inline void | |
915 | check_sum_rt_lsa(struct proto_ospf *po, ort *nf) | |
916 | { | |
917 | struct ospf_area *oa; | |
918 | WALK_LIST(oa, po->area_list) | |
919 | { | |
920 | if (decide_sum_lsa(oa, nf, ORT_ROUTER)) | |
921 | originate_sum_rt_lsa(oa, &nf->fn, nf->n.metric1, nf->n.options); | |
922 | else | |
923 | flush_sum_lsa(oa, &nf->fn, ORT_ROUTER); | |
924 | } | |
925 | } | |
926 | ||
927 | ||
928 | /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */ | |
3b89a232 | 929 | static void |
6384c7d7 | 930 | ospf_check_vlinks(struct proto_ospf *po) |
3b89a232 | 931 | { |
6384c7d7 OZ |
932 | struct proto *p = &po->proto; |
933 | ||
934 | struct ospf_iface *iface; | |
935 | WALK_LIST(iface, po->iface_list) | |
936 | { | |
937 | if (iface->type == OSPF_IT_VLINK) | |
938 | { | |
939 | struct top_hash_entry *tmp; | |
940 | tmp = ospf_hash_find_rt(po->gr, iface->voa->areaid, iface->vid); | |
941 | ||
57c574d8 | 942 | if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs) |
6384c7d7 | 943 | { |
57c574d8 OZ |
944 | struct ospf_iface *nhi = ospf_iface_find(po, tmp->nhs->iface); |
945 | ||
6384c7d7 | 946 | if ((iface->state != OSPF_IS_PTP) |
57c574d8 | 947 | || (iface->vifa != nhi) |
6384c7d7 OZ |
948 | || !ipa_equal(iface->vip, tmp->lb)) |
949 | { | |
950 | OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id); | |
951 | ospf_iface_sm(iface, ISM_DOWN); | |
57c574d8 OZ |
952 | iface->vifa = nhi; |
953 | iface->iface = nhi->iface; | |
954 | iface->addr = nhi->addr; | |
955 | iface->sk = nhi->sk; | |
6384c7d7 OZ |
956 | iface->cost = tmp->dist; |
957 | iface->vip = tmp->lb; | |
958 | ospf_iface_sm(iface, ISM_UP); | |
959 | } | |
960 | else if ((iface->state == OSPF_IS_PTP) && (iface->cost != tmp->dist)) | |
961 | { | |
962 | iface->cost = tmp->dist; | |
963 | schedule_rt_lsa(po->backbone); | |
964 | } | |
965 | } | |
966 | else | |
967 | { | |
968 | if (iface->state > OSPF_IS_DOWN) | |
969 | { | |
970 | OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid); | |
971 | ospf_iface_sm(iface, ISM_DOWN); | |
972 | } | |
973 | } | |
974 | } | |
975 | } | |
976 | } | |
977 | ||
978 | /* Miscellaneous route processing that needs to be done by ABRs */ | |
979 | static void | |
980 | ospf_rt_abr(struct proto_ospf *po) | |
981 | { | |
982 | struct area_net *anet; | |
983 | ort *nf, *default_nf; | |
984 | ||
3b89a232 | 985 | FIB_WALK(&po->rtf, nftmp) |
98ac6176 | 986 | { |
6384c7d7 OZ |
987 | nf = (ort *) nftmp; |
988 | ||
989 | ||
990 | /* RFC 2328 G.3 - incomplete resolution of virtual next hops */ | |
57c574d8 OZ |
991 | if (nf->n.type && unresolved_vlink(nf->n.nhs)) |
992 | reset_ri(nf); | |
6384c7d7 OZ |
993 | |
994 | ||
995 | /* Compute condensed area networks */ | |
996 | if (nf->n.type == RTS_OSPF) | |
997 | { | |
998 | anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen); | |
999 | if (anet) | |
1000 | { | |
1001 | if (!anet->active) | |
1002 | { | |
1003 | anet->active = 1; | |
1004 | ||
1005 | /* Get a RT entry and mark it to know that it is an area network */ | |
1006 | ort *nfi = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen); | |
1007 | nfi->fn.x0 = 1; /* mark and keep persistent, to have stable UID */ | |
1008 | ||
1009 | /* 16.2. (3) */ | |
1010 | if (nfi->n.type == RTS_OSPF_IA) | |
57c574d8 | 1011 | reset_ri(nfi); |
6384c7d7 OZ |
1012 | } |
1013 | ||
1014 | if (anet->metric < nf->n.metric1) | |
1015 | anet->metric = nf->n.metric1; | |
1016 | } | |
1017 | } | |
1018 | } | |
1019 | FIB_WALK_END; | |
1020 | ||
1021 | ip_addr addr = IPA_NONE; | |
1022 | default_nf = (ort *) fib_get(&po->rtf, &addr, 0); | |
1023 | default_nf->fn.x0 = 1; /* keep persistent */ | |
1024 | ||
1025 | struct ospf_area *oa; | |
1026 | WALK_LIST(oa, po->area_list) | |
1027 | { | |
1028 | ||
1029 | /* 12.4.3.1. - originate or flush default summary LSA for stub areas */ | |
1030 | if (oa->stub) | |
1031 | originate_sum_net_lsa(oa, &default_nf->fn, oa->stub); | |
1032 | else | |
1033 | flush_sum_lsa(oa, &default_nf->fn, ORT_NET); | |
1034 | ||
1035 | ||
1036 | /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */ | |
1037 | FIB_WALK(&oa->rtr, nftmp) | |
1038 | { | |
1039 | nf = (ort *) nftmp; | |
1040 | if (nf->n.options & ORTA_ASBR) | |
1041 | ri_install_asbr(po, &nf->fn.prefix, &nf->n); | |
1042 | } | |
1043 | FIB_WALK_END; | |
1044 | } | |
1045 | ||
1046 | ||
1047 | /* Originate or flush ASBR summary LSAs */ | |
1048 | FIB_WALK(&po->backbone->rtr, nftmp) | |
1049 | { | |
1050 | check_sum_rt_lsa(po, (ort *) nftmp); | |
1a61882d | 1051 | } |
3b89a232 | 1052 | FIB_WALK_END; |
6384c7d7 OZ |
1053 | |
1054 | ||
1055 | /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */ | |
1056 | ospf_check_vlinks(po); | |
b8f17cf1 OF |
1057 | } |
1058 | ||
54818e9b OZ |
1059 | /* Like fib_route(), but ignores dummy rt entries */ |
1060 | static void * | |
1061 | ospf_fib_route(struct fib *f, ip_addr a, int len) | |
1062 | { | |
1063 | ip_addr a0; | |
1064 | ort *nf; | |
1065 | ||
1066 | while (len >= 0) | |
1067 | { | |
1068 | a0 = ipa_and(a, ipa_mkmask(len)); | |
1069 | nf = fib_find(f, &a0, len); | |
1070 | if (nf && nf->n.type) | |
1071 | return nf; | |
1072 | len--; | |
1073 | } | |
1074 | return NULL; | |
1075 | } | |
6384c7d7 OZ |
1076 | |
1077 | /* RFC 2328 16.4. calculating external routes */ | |
b8f17cf1 | 1078 | static void |
86c84d76 | 1079 | ospf_ext_spf(struct proto_ospf *po) |
fafe44b6 | 1080 | { |
3b89a232 | 1081 | ort *nf1, *nf2; |
1a61882d OF |
1082 | orta nfa; |
1083 | struct top_hash_entry *en; | |
2e10a170 | 1084 | struct proto *p = &po->proto; |
aa1e082c | 1085 | struct ospf_lsa_ext *le; |
c3226991 | 1086 | int pxlen, ebit, rt_fwaddr_valid; |
57c574d8 | 1087 | ip_addr ip, rtid, rt_fwaddr; |
c3226991 | 1088 | u32 br_metric, rt_metric, rt_tag; |
98ac6176 | 1089 | struct ospf_area *atmp; |
57c574d8 | 1090 | struct mpnh* nhs = NULL; |
aa1e082c | 1091 | |
1a61882d | 1092 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes"); |
aa1e082c | 1093 | |
86c84d76 | 1094 | WALK_SLIST(en, po->lsal) |
aa1e082c | 1095 | { |
c3226991 | 1096 | /* 16.4. (1) */ |
2e10a170 OF |
1097 | if (en->lsa.type != LSA_T_EXT) |
1098 | continue; | |
3b89a232 | 1099 | |
2e10a170 OF |
1100 | if (en->lsa.age == LSA_MAXAGE) |
1101 | continue; | |
c3226991 OZ |
1102 | |
1103 | /* 16.4. (2) */ | |
8a70a13e | 1104 | if (en->lsa.rt == po->router_id) |
2e10a170 | 1105 | continue; |
aa1e082c | 1106 | |
f9c799a0 OZ |
1107 | DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n", |
1108 | p->name, en->lsa.id, en->lsa.rt, en->lsa.type); | |
273fd2c1 | 1109 | |
c3226991 OZ |
1110 | le = en->lsa_body; |
1111 | ||
1112 | rt_metric = le->metric & METRIC_MASK; | |
1113 | ebit = le->metric & LSA_EXT_EBIT; | |
1114 | ||
1115 | if (rt_metric == LSINFINITY) | |
2e10a170 | 1116 | continue; |
c3226991 OZ |
1117 | |
1118 | #ifdef OSPFv2 | |
2e10a170 | 1119 | ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask); |
c3226991 OZ |
1120 | pxlen = ipa_mklen(le->netmask); |
1121 | rt_fwaddr = le->fwaddr; | |
1122 | rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE); | |
1123 | rt_tag = le->tag; | |
1124 | #else /* OSPFv3 */ | |
1125 | u8 pxopts; | |
b49e6f5a | 1126 | u16 rest; |
c3226991 | 1127 | u32 *buf = le->rest; |
b66abe8e | 1128 | buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest); |
c3226991 OZ |
1129 | |
1130 | if (pxopts & OPT_PX_NU) | |
1131 | continue; | |
1132 | ||
1133 | rt_fwaddr_valid = le->metric & LSA_EXT_FBIT; | |
1134 | if (rt_fwaddr_valid) | |
b66abe8e | 1135 | buf = lsa_get_ipv6_addr(buf, &rt_fwaddr); |
c3226991 OZ |
1136 | else |
1137 | rt_fwaddr = IPA_NONE; | |
1138 | ||
1139 | if (le->metric & LSA_EXT_TBIT) | |
1140 | rt_tag = *buf++; | |
1141 | else | |
1142 | rt_tag = 0; | |
1143 | #endif | |
1144 | ||
1145 | if (pxlen < 0) | |
508c36ab | 1146 | { |
34a877cc OZ |
1147 | log(L_WARN "%s: Invalid mask in LSA (Type: %04x, Id: %R, Rt: %R)", |
1148 | p->name, en->lsa.type, en->lsa.id, en->lsa.rt); | |
4ee21789 | 1149 | continue; |
508c36ab | 1150 | } |
aa1e082c | 1151 | |
c3226991 | 1152 | /* 16.4. (3) */ |
6384c7d7 OZ |
1153 | /* If there are more areas, we already precomputed preferred ASBR entries |
1154 | in ospf_asbr_spf() and stored them in the backbone table */ | |
1155 | atmp = (po->areano > 1) ? po->backbone : HEAD(po->area_list); | |
c3226991 | 1156 | rtid = ipa_from_rid(en->lsa.rt); |
6384c7d7 | 1157 | nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH); |
3b89a232 | 1158 | |
6384c7d7 | 1159 | if (!nf1 || !nf1->n.type) |
1a61882d | 1160 | continue; /* No AS boundary router found */ |
aa1e082c | 1161 | |
c3226991 | 1162 | if (!(nf1->n.options & ORTA_ASBR)) |
1a61882d | 1163 | continue; /* It is not ASBR */ |
508c36ab | 1164 | |
c3226991 | 1165 | if (!rt_fwaddr_valid) |
aa1e082c | 1166 | { |
3b89a232 | 1167 | nf2 = nf1; |
57c574d8 | 1168 | nhs = nf1->n.nhs; |
c3226991 | 1169 | br_metric = nf1->n.metric1; |
508c36ab | 1170 | } |
1a61882d | 1171 | else |
c3226991 | 1172 | { |
54818e9b OZ |
1173 | nf2 = ospf_fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH); |
1174 | if (!nf2) | |
2e10a170 | 1175 | continue; |
98ac6176 | 1176 | |
3b89a232 OZ |
1177 | if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA)) |
1178 | continue; | |
98ac6176 | 1179 | |
e0a62ad0 | 1180 | /* Next-hop is a part of a configured stubnet */ |
57c574d8 | 1181 | if (!nf2->n.nhs) |
e0a62ad0 OZ |
1182 | continue; |
1183 | ||
57c574d8 OZ |
1184 | nhs = nf2->n.nhs; |
1185 | /* If gw is zero, it is a device route */ | |
1186 | if (ipa_zero(nhs->gw)) | |
1187 | nhs = new_nexthop(po, rt_fwaddr, nhs->iface, nhs->weight); | |
c3226991 | 1188 | br_metric = nf2->n.metric1; |
aa1e082c | 1189 | } |
508c36ab | 1190 | |
c3226991 OZ |
1191 | if (ebit) |
1192 | { | |
1193 | nfa.type = RTS_OSPF_EXT2; | |
1194 | nfa.metric1 = br_metric; | |
1195 | nfa.metric2 = rt_metric; | |
1196 | } | |
1197 | else | |
1198 | { | |
1199 | nfa.type = RTS_OSPF_EXT1; | |
1200 | nfa.metric1 = br_metric + rt_metric; | |
1201 | nfa.metric2 = LSINFINITY; | |
1202 | } | |
1203 | ||
0ea8fb4a OZ |
1204 | /* Mark the LSA as reachable */ |
1205 | en->color = INSPF; | |
1206 | ||
3b89a232 OZ |
1207 | /* Whether the route is preferred in route selection according to 16.4.1 */ |
1208 | nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0; | |
1209 | ||
c3226991 | 1210 | nfa.tag = rt_tag; |
c27b2449 | 1211 | nfa.rid = en->lsa.rt; |
3b89a232 | 1212 | nfa.oa = nf1->n.oa; /* undefined in RFC 2328 */ |
57c574d8 OZ |
1213 | nfa.voa = NULL; |
1214 | nfa.nhs = nhs; | |
3b89a232 OZ |
1215 | |
1216 | ri_install_ext(po, ip, pxlen, &nfa); | |
1217 | } | |
1218 | } | |
1219 | ||
57c574d8 | 1220 | /* Cleanup of routing tables and data */ |
6384c7d7 OZ |
1221 | void |
1222 | ospf_rt_reset(struct proto_ospf *po) | |
3b89a232 | 1223 | { |
6384c7d7 OZ |
1224 | struct ospf_area *oa; |
1225 | struct top_hash_entry *en; | |
1226 | struct area_net *anet; | |
1227 | ort *ri; | |
3b89a232 | 1228 | |
6384c7d7 OZ |
1229 | /* Reset old routing table */ |
1230 | FIB_WALK(&po->rtf, nftmp) | |
3b89a232 | 1231 | { |
6384c7d7 | 1232 | ri = (ort *) nftmp; |
6384c7d7 | 1233 | ri->fn.x0 = 0; |
57c574d8 | 1234 | reset_ri(ri); |
6384c7d7 OZ |
1235 | } |
1236 | FIB_WALK_END; | |
1237 | ||
1238 | /* Reset SPF data in LSA db */ | |
1239 | WALK_SLIST(en, po->lsal) | |
1240 | { | |
1241 | en->color = OUTSPF; | |
1242 | en->dist = LSINFINITY; | |
57c574d8 | 1243 | en->nhs = NULL; |
6384c7d7 OZ |
1244 | en->lb = IPA_NONE; |
1245 | } | |
1246 | ||
1247 | WALK_LIST(oa, po->area_list) | |
1248 | { | |
1249 | /* Reset ASBR routing tables */ | |
1250 | FIB_WALK(&oa->rtr, nftmp) | |
3b89a232 | 1251 | { |
6384c7d7 | 1252 | ri = (ort *) nftmp; |
57c574d8 | 1253 | reset_ri(ri); |
6384c7d7 OZ |
1254 | } |
1255 | FIB_WALK_END; | |
3b89a232 | 1256 | |
6384c7d7 OZ |
1257 | /* Reset condensed area networks */ |
1258 | if (po->areano > 1) | |
1259 | { | |
1260 | FIB_WALK(&oa->net_fib, nftmp) | |
3b89a232 | 1261 | { |
6384c7d7 OZ |
1262 | anet = (struct area_net *) nftmp; |
1263 | anet->active = 0; | |
1264 | anet->metric = 0; | |
3b89a232 | 1265 | } |
6384c7d7 | 1266 | FIB_WALK_END; |
3b89a232 OZ |
1267 | } |
1268 | } | |
1269 | } | |
6384c7d7 | 1270 | |
3b89a232 OZ |
1271 | /** |
1272 | * ospf_rt_spf - calculate internal routes | |
1273 | * @po: OSPF protocol | |
1274 | * | |
1275 | * Calculation of internal paths in an area is described in 16.1 of RFC 2328. | |
1276 | * It's based on Dijkstra's shortest path tree algorithms. | |
1277 | * This function is invoked from ospf_disp(). | |
1278 | */ | |
1279 | void | |
1280 | ospf_rt_spf(struct proto_ospf *po) | |
1281 | { | |
1282 | struct proto *p = &po->proto; | |
1283 | struct ospf_area *oa; | |
3b89a232 | 1284 | |
6384c7d7 OZ |
1285 | if (po->areano == 0) |
1286 | return; | |
3b89a232 | 1287 | |
3b89a232 OZ |
1288 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation"); |
1289 | ||
6384c7d7 OZ |
1290 | /* 16. (1) */ |
1291 | ospf_rt_reset(po); | |
3b89a232 | 1292 | |
6384c7d7 | 1293 | /* 16. (2) */ |
3b89a232 | 1294 | WALK_LIST(oa, po->area_list) |
3b89a232 | 1295 | ospf_rt_spfa(oa); |
3b89a232 OZ |
1296 | |
1297 | /* 16. (3) */ | |
6384c7d7 | 1298 | if (po->areano == 1) |
3b89a232 OZ |
1299 | ospf_rt_sum(HEAD(po->area_list)); |
1300 | else | |
1301 | ospf_rt_sum(po->backbone); | |
1302 | ||
1303 | /* 16. (4) */ | |
1304 | WALK_LIST(oa, po->area_list) | |
1305 | if (oa->trcap && (oa->areaid != 0)) | |
1306 | ospf_rt_sum_tr(oa); | |
1307 | ||
6384c7d7 OZ |
1308 | if (po->areano > 1) |
1309 | ospf_rt_abr(po); | |
3b89a232 OZ |
1310 | |
1311 | /* 16. (5) */ | |
1312 | ospf_ext_spf(po); | |
1313 | ||
1314 | rt_sync(po); | |
57c574d8 OZ |
1315 | lp_flush(po->nhpool); |
1316 | ||
3b89a232 | 1317 | po->calcrt = 0; |
dfa9a53a OF |
1318 | } |
1319 | ||
57c574d8 OZ |
1320 | |
1321 | static inline int | |
1322 | match_dr(struct ospf_iface *ifa, struct top_hash_entry *en) | |
1323 | { | |
1324 | #ifdef OSPFv2 | |
1325 | return (ifa->drid == en->lsa.rt) && (ipa_to_u32(ifa->drip) == en->lsa.id); | |
1326 | #else /* OSPFv3 */ | |
1327 | return (ifa->drid == en->lsa.rt) && (ifa->dr_iface_id == en->lsa.id); | |
1328 | #endif | |
1329 | } | |
1330 | ||
1331 | ||
1332 | static inline int | |
1333 | match_rtlink(struct ospf_iface *ifa, struct ospf_lsa_rt_link *rtl) | |
1334 | { | |
1335 | #ifdef OSPFv2 | |
1336 | return (ifa->type == OSPF_IT_PTP) && (ifa->cost == rtl->metric) && | |
1337 | (((ifa->addr->flags & IA_UNNUMBERED) ? ifa->iface->index : | |
1338 | ipa_to_u32(ifa->addr->ip)) == rtl->data); | |
1339 | #else /* OSPFv3 */ | |
1340 | return (ifa->type == OSPF_IT_PTP) && (ifa->cost == rtl->metric) && | |
1341 | (ifa->iface->index == rtl->lif); | |
1342 | #endif | |
1343 | } | |
1344 | ||
1345 | static inline int | |
1346 | inherit_nexthops(struct mpnh *pn) | |
1347 | { | |
1348 | /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */ | |
1349 | return pn && (ipa_nonzero(pn->gw) || !pn->iface); | |
1350 | } | |
1351 | ||
1352 | static struct mpnh * | |
1353 | calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, | |
1354 | struct top_hash_entry *par, struct ospf_lsa_rt_link *rtl) | |
1355 | { | |
1356 | // struct proto *p = &oa->po->proto; | |
1357 | struct proto_ospf *po = oa->po; | |
1358 | struct mpnh *pn = par->nhs; | |
1359 | struct ospf_iface *ifa; | |
1360 | u32 rid = en->lsa.rt; | |
1361 | ||
1362 | /* 16.1.1. The next hop calculation */ | |
1363 | DBG(" Next hop calculating for id: %R rt: %R type: %u\n", | |
1364 | en->lsa.id, en->lsa.rt, en->lsa.type); | |
1365 | ||
1366 | /* Usually, we inherit parent nexthops */ | |
1367 | if (inherit_nexthops(pn)) | |
1368 | return pn; | |
1369 | ||
1370 | /* | |
1371 | * There are three cases: | |
1372 | * 1) en is a local network (and par is root) | |
1373 | * 2) en is a ptp or ptmp neighbor (and par is root) | |
1374 | * 3) en is a bcast or nbma neighbor (and par is local network) | |
1375 | */ | |
1376 | ||
1377 | /* The first case - local network */ | |
1378 | if ((en->lsa.type == LSA_T_NET) && (par == oa->rt)) | |
1379 | { | |
1380 | WALK_LIST(ifa, po->iface_list) | |
1381 | if (match_dr(ifa, en)) | |
1382 | return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight); | |
1383 | ||
1384 | return NULL; | |
1385 | } | |
1386 | ||
1387 | /* The second case - ptp or ptmp neighbor */ | |
1388 | if ((en->lsa.type == LSA_T_RT) && (par == oa->rt)) | |
1389 | { | |
1390 | if (rtl->type == LSART_VLNK) | |
1391 | return new_nexthop(po, IPA_NONE, NULL, 0); | |
1392 | ||
1393 | WALK_LIST(ifa, po->iface_list) | |
1394 | if (match_rtlink(ifa, rtl)) | |
1395 | { | |
1396 | struct ospf_neighbor *m = find_neigh(ifa, rid); | |
1397 | if (m && (m->state == NEIGHBOR_FULL)) | |
1398 | return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight); | |
1399 | } | |
1400 | ||
1401 | return NULL; | |
1402 | } | |
1403 | ||
1404 | /* The third case - bcast or nbma neighbor */ | |
1405 | if ((en->lsa.type == LSA_T_RT) && (par->lsa.type == LSA_T_NET)) | |
1406 | { | |
1407 | /* par->nhi should be defined from parent's calc_next_hop() */ | |
1408 | if (!pn) | |
1409 | goto bad; | |
1410 | ||
1411 | #ifdef OSPFv2 | |
1412 | /* | |
1413 | * In this case, next-hop is the same as link-back, which is | |
1414 | * already computed in link_back(). | |
1415 | */ | |
1416 | if (ipa_zero(en->lb)) | |
1417 | goto bad; | |
1418 | ||
1419 | return new_nexthop(po, en->lb, pn->iface, pn->weight); | |
1420 | ||
1421 | #else /* OSPFv3 */ | |
1422 | /* | |
1423 | * Next-hop is taken from lladdr field of Link-LSA, en->lb_id | |
1424 | * is computed in link_back(). | |
1425 | */ | |
1426 | struct top_hash_entry *lhe; | |
1427 | lhe = ospf_hash_find(po->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK); | |
1428 | ||
1429 | if (!lhe) | |
1430 | return NULL; | |
1431 | ||
1432 | struct ospf_lsa_link *llsa = lhe->lsa_body; | |
1433 | ||
1434 | if (ipa_zero(llsa->lladdr)) | |
1435 | return NULL; | |
1436 | ||
1437 | return new_nexthop(po, llsa->lladdr, pn->iface, pn->weight); | |
1438 | #endif | |
1439 | } | |
1440 | ||
1441 | bad: | |
1442 | /* Probably bug or some race condition, we log it */ | |
1443 | log(L_ERR "Unexpected case in next hop calculation"); | |
1444 | return NULL; | |
1445 | } | |
1446 | ||
1447 | /* Compare nexthops during merge. | |
1448 | We need to maintain nhs sorted to eliminate duplicities */ | |
1449 | static int | |
1450 | cmp_nhs(struct mpnh *s1, struct mpnh *s2) | |
1451 | { | |
1452 | int r; | |
1453 | ||
1454 | if (!s1) | |
1455 | return 1; | |
1456 | ||
1457 | if (!s2) | |
1458 | return -1; | |
1459 | ||
1460 | r = ((int) s2->weight) - ((int) s1->weight); | |
1461 | if (r) | |
1462 | return r; | |
1463 | ||
1464 | r = ipa_compare(s1->gw, s2->gw); | |
1465 | if (r) | |
1466 | return r; | |
1467 | ||
1468 | return ((int) s1->iface->index) - ((int) s2->iface->index); | |
1469 | } | |
1470 | ||
1471 | static void | |
1472 | merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en, | |
1473 | struct top_hash_entry *par, struct mpnh *new) | |
1474 | { | |
1475 | if (en->nhs == new) | |
1476 | return; | |
1477 | ||
1478 | int r1 = en->nhs_reuse; | |
1479 | int r2 = (par->nhs != new); | |
1480 | int count = po->ecmp; | |
1481 | struct mpnh *s1 = en->nhs; | |
1482 | struct mpnh *s2 = new; | |
1483 | struct mpnh **n = &(en->nhs); | |
1484 | ||
1485 | /* | |
1486 | * r1, r2 signalize whether we can reuse nexthops from s1, s2. | |
1487 | * New nexthops (s2, new) can be reused if they are not inherited | |
1488 | * from the parent (i.e. it is allocated in calc_next_hop()). | |
1489 | * Current nexthops (s1, en->nhs) can be reused if they weren't | |
1490 | * inherited in previous steps (that is stored in nhs_reuse, | |
1491 | * i.e. created by merging or allocalted in calc_next_hop()). | |
1492 | * | |
1493 | * Generally, a node first inherits shared nexthops from its | |
1494 | * parent and later possibly gets reusable copy during merging. | |
1495 | */ | |
1496 | ||
1497 | while ((s1 || s2) && count--) | |
1498 | { | |
1499 | int cmp = cmp_nhs(s1, s2); | |
1500 | if (cmp < 0) | |
1501 | { | |
1502 | *n = r1 ? s1 : copy_nexthop(po, s1); | |
1503 | s1 = s1->next; | |
1504 | } | |
1505 | else if (cmp > 0) | |
1506 | { | |
1507 | *n = r2 ? s2 : copy_nexthop(po, s2); | |
1508 | s2 = s2->next; | |
1509 | } | |
1510 | else | |
1511 | { | |
1512 | *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(po, s1)); | |
1513 | s1 = s1->next; | |
1514 | s2 = s2->next; | |
1515 | } | |
1516 | n = &((*n)->next); | |
1517 | } | |
1518 | *n = NULL; | |
1519 | ||
1520 | en->nhs_reuse=1; | |
1521 | } | |
1522 | ||
baa5dd6c | 1523 | /* Add LSA into list of candidates in Dijkstra's algorithm */ |
b8f17cf1 | 1524 | static void |
2e10a170 | 1525 | add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, |
57c574d8 | 1526 | u32 dist, struct ospf_area *oa, struct ospf_lsa_rt_link *rtl) |
dfa9a53a | 1527 | { |
57c574d8 | 1528 | struct proto_ospf *po = oa->po; |
2e10a170 OF |
1529 | node *prev, *n; |
1530 | int added = 0; | |
e80e9d0d | 1531 | struct top_hash_entry *act; |
dfa9a53a | 1532 | |
b49e6f5a | 1533 | /* 16.1. (2b) */ |
2e10a170 OF |
1534 | if (en == NULL) |
1535 | return; | |
1536 | if (en->lsa.age == LSA_MAXAGE) | |
1537 | return; | |
98ac6176 | 1538 | |
b49e6f5a OZ |
1539 | #ifdef OSPFv3 |
1540 | if (en->lsa.type == LSA_T_RT) | |
1541 | { | |
1542 | struct ospf_lsa_rt *rt = en->lsa_body; | |
1543 | if (!(rt->options & OPT_V6) || !(rt->options & OPT_R)) | |
1544 | return; | |
1545 | } | |
1546 | #endif | |
1547 | ||
c3226991 | 1548 | /* 16.1. (2c) */ |
2e10a170 OF |
1549 | if (en->color == INSPF) |
1550 | return; | |
dfa9a53a | 1551 | |
6384c7d7 | 1552 | /* 16.1. (2d), also checks that dist < LSINFINITY */ |
57c574d8 | 1553 | if (dist > en->dist) |
2e10a170 | 1554 | return; |
98ac6176 | 1555 | |
9807690b | 1556 | /* We should check whether there is a reverse link from en to par, */ |
98ac6176 OF |
1557 | if (!link_back(oa, en, par)) |
1558 | return; | |
1559 | ||
57c574d8 OZ |
1560 | struct mpnh *nhs = calc_next_hop(oa, en, par, rtl); |
1561 | if (!nhs) | |
b76aeb82 OZ |
1562 | { |
1563 | log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)", | |
1564 | en->lsa.type, en->lsa.id, en->lsa.rt); | |
1565 | return; | |
1566 | } | |
1567 | ||
57c574d8 OZ |
1568 | if (dist == en->dist) |
1569 | { | |
1570 | /* | |
1571 | * For multipath, we should merge nexthops. We do not mix dummy | |
1572 | * vlink nexthops, device nexthops and gateway nexthops. We merge | |
1573 | * gateway nexthops only. We prefer device nexthops over gateway | |
1574 | * nexthops and gateway nexthops over vlink nexthops. We either | |
1575 | * keep old nexthops, merge old and new, or replace old with new. | |
1576 | * | |
1577 | * We know that en->color == CANDIDATE and en->nhs is defined. | |
1578 | */ | |
1579 | struct mpnh *onhs = en->nhs; | |
1580 | ||
1581 | /* Keep old ones */ | |
1582 | if (!po->ecmp || !nhs->iface || (onhs->iface && ipa_zero(onhs->gw))) | |
1583 | return; | |
1584 | ||
1585 | /* Merge old and new */ | |
1586 | if (ipa_nonzero(nhs->gw) && ipa_nonzero(onhs->gw)) | |
1587 | { | |
1588 | merge_nexthops(po, en, par, nhs); | |
1589 | return; | |
1590 | } | |
1591 | ||
1592 | /* Fallback to replace old ones */ | |
1593 | } | |
1594 | ||
3aab39f5 OZ |
1595 | DBG(" Adding candidate: rt: %R, id: %R, type: %u\n", |
1596 | en->lsa.rt, en->lsa.id, en->lsa.type); | |
2e10a170 | 1597 | |
1a61882d OF |
1598 | if (en->color == CANDIDATE) |
1599 | { /* We found a shorter path */ | |
e80e9d0d | 1600 | rem_node(&en->cn); |
dfa9a53a | 1601 | } |
57c574d8 | 1602 | en->nhs = nhs; |
2e10a170 OF |
1603 | en->dist = dist; |
1604 | en->color = CANDIDATE; | |
57c574d8 | 1605 | en->nhs_reuse = (par->nhs != nhs); |
dfa9a53a | 1606 | |
2e10a170 | 1607 | prev = NULL; |
dfa9a53a | 1608 | |
2e10a170 | 1609 | if (EMPTY_LIST(*l)) |
e80e9d0d | 1610 | { |
2e10a170 | 1611 | add_head(l, &en->cn); |
85195f1a OF |
1612 | } |
1613 | else | |
1614 | { | |
2e10a170 | 1615 | WALK_LIST(n, *l) |
dfa9a53a | 1616 | { |
2e10a170 OF |
1617 | act = SKIP_BACK(struct top_hash_entry, cn, n); |
1618 | if ((act->dist > dist) || | |
57c574d8 | 1619 | ((act->dist == dist) && (act->lsa.type == LSA_T_RT))) |
85195f1a | 1620 | { |
2e10a170 OF |
1621 | if (prev == NULL) |
1622 | add_head(l, &en->cn); | |
1623 | else | |
1624 | insert_node(&en->cn, prev); | |
1625 | added = 1; | |
1626 | break; | |
85195f1a | 1627 | } |
2e10a170 | 1628 | prev = n; |
85195f1a OF |
1629 | } |
1630 | ||
2e10a170 | 1631 | if (!added) |
85195f1a | 1632 | { |
2e10a170 | 1633 | add_tail(l, &en->cn); |
dfa9a53a OF |
1634 | } |
1635 | } | |
1636 | } | |
468f2347 | 1637 | |
b49e6f5a | 1638 | static inline int |
57c574d8 | 1639 | ort_changed(ort *nf, rta *nr) |
b49e6f5a | 1640 | { |
57c574d8 OZ |
1641 | rta *or = nf->old_rta; |
1642 | return !or || | |
1643 | (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) || | |
1644 | (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) || | |
1645 | (nr->source != or->source) || (nr->dest != or->dest) || | |
1646 | (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) || | |
1647 | !mpnh_same(nr->nexthops, or->nexthops); | |
a92847e7 | 1648 | } |
1a61882d OF |
1649 | |
1650 | static void | |
1651 | rt_sync(struct proto_ospf *po) | |
1652 | { | |
1653 | struct proto *p = &po->proto; | |
1654 | struct fib_iterator fit; | |
98ac6176 | 1655 | struct fib *fib = &po->rtf; |
1a61882d | 1656 | ort *nf; |
6384c7d7 | 1657 | struct ospf_area *oa; |
98ac6176 | 1658 | |
f7574707 OZ |
1659 | /* This is used for forced reload of routes */ |
1660 | int reload = (po->calcrt == 2); | |
1661 | ||
98ac6176 | 1662 | OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation"); |
1a61882d OF |
1663 | |
1664 | DBG("Now syncing my rt table with nest's\n"); | |
1665 | FIB_ITERATE_INIT(&fit, fib); | |
98ac6176 | 1666 | again1: |
1a61882d OF |
1667 | FIB_ITERATE_START(fib, &fit, nftmp) |
1668 | { | |
1669 | nf = (ort *) nftmp; | |
3b89a232 | 1670 | |
57c574d8 OZ |
1671 | /* Sanity check of next-hop addresses, failure should not happen */ |
1672 | if (nf->n.type) | |
6384c7d7 | 1673 | { |
57c574d8 OZ |
1674 | struct mpnh *nh; |
1675 | for (nh = nf->n.nhs; nh; nh = nh->next) | |
1676 | if (ipa_nonzero(nh->gw)) | |
1677 | { | |
1678 | neighbor *ng = neigh_find2(p, &nh->gw, nh->iface, 0); | |
1679 | if (!ng || (ng->scope == SCOPE_HOST)) | |
1680 | { reset_ri(nf); break; } | |
1681 | } | |
6384c7d7 | 1682 | } |
27a1e3ac | 1683 | |
6384c7d7 OZ |
1684 | if (po->areano > 1) |
1685 | check_sum_net_lsa(po, nf); | |
7de7470a | 1686 | |
e0a62ad0 | 1687 | /* Remove configured stubnets */ |
57c574d8 OZ |
1688 | if (!nf->n.nhs) |
1689 | reset_ri(nf); | |
e0a62ad0 | 1690 | |
57c574d8 | 1691 | if (nf->n.type) /* Add the route */ |
6384c7d7 | 1692 | { |
57c574d8 OZ |
1693 | rta a0 = { |
1694 | .proto = p, | |
1695 | .source = nf->n.type, | |
1696 | .scope = SCOPE_UNIVERSE, | |
1697 | .cast = RTC_UNICAST, | |
1698 | }; | |
1699 | ||
1700 | if (nf->n.nhs->next) | |
98ac6176 | 1701 | { |
57c574d8 OZ |
1702 | a0.dest = RTD_MULTIPATH; |
1703 | a0.nexthops = nf->n.nhs; | |
1704 | } | |
1705 | else if (ipa_nonzero(nf->n.nhs->gw)) | |
1706 | { | |
1707 | a0.dest = RTD_ROUTER; | |
1708 | a0.iface = nf->n.nhs->iface; | |
1709 | a0.gw = nf->n.nhs->gw; | |
1710 | } | |
1711 | else | |
1712 | { | |
1713 | a0.dest = RTD_DEVICE; | |
1714 | a0.iface = nf->n.nhs->iface; | |
1715 | } | |
6384c7d7 | 1716 | |
57c574d8 OZ |
1717 | if (reload || ort_changed(nf, &a0)) |
1718 | { | |
1719 | net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); | |
1720 | rta *a = rta_lookup(&a0); | |
1721 | rte *e = rte_get_temp(a); | |
1722 | ||
1723 | rta_free(nf->old_rta); | |
1724 | nf->old_rta = rta_clone(a); | |
1725 | e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1; | |
1726 | e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2; | |
1727 | e->u.ospf.tag = nf->old_tag = nf->n.tag; | |
1728 | e->u.ospf.router_id = nf->old_rid = nf->n.rid; | |
6384c7d7 OZ |
1729 | e->pflags = 0; |
1730 | e->net = ne; | |
1731 | e->pref = p->preference; | |
57c574d8 OZ |
1732 | |
1733 | ||
1734 | ||
6384c7d7 OZ |
1735 | DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n", |
1736 | a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1); | |
1737 | rte_update(p->table, ne, p, p, e); | |
98ac6176 | 1738 | } |
57c574d8 OZ |
1739 | } |
1740 | else if (nf->old_rta) | |
1741 | { | |
1742 | /* Remove the route */ | |
1743 | rta_free(nf->old_rta); | |
1744 | nf->old_rta = NULL; | |
1745 | ||
1746 | net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); | |
1747 | rte_update(p->table, ne, p, p, NULL); | |
6384c7d7 OZ |
1748 | } |
1749 | ||
1750 | /* Remove unused rt entry. Entries with fn.x0 == 1 are persistent. */ | |
1751 | if (!nf->n.type && !nf->fn.x0) | |
1752 | { | |
3b89a232 OZ |
1753 | FIB_ITERATE_PUT(&fit, nftmp); |
1754 | fib_delete(fib, nftmp); | |
1755 | goto again1; | |
1a61882d OF |
1756 | } |
1757 | } | |
1758 | FIB_ITERATE_END(nftmp); | |
98ac6176 | 1759 | |
3b89a232 | 1760 | |
98ac6176 OF |
1761 | WALK_LIST(oa, po->area_list) |
1762 | { | |
6384c7d7 | 1763 | /* Cleanup ASBR hash tables */ |
98ac6176 OF |
1764 | FIB_ITERATE_INIT(&fit, &oa->rtr); |
1765 | again2: | |
1766 | FIB_ITERATE_START(&oa->rtr, &fit, nftmp) | |
1767 | { | |
1768 | nf = (ort *) nftmp; | |
98ac6176 | 1769 | |
6384c7d7 | 1770 | if (!nf->n.type) |
3b16080c | 1771 | { |
6384c7d7 OZ |
1772 | FIB_ITERATE_PUT(&fit, nftmp); |
1773 | fib_delete(&oa->rtr, nftmp); | |
1774 | goto again2; | |
3b16080c | 1775 | } |
98ac6176 | 1776 | } |
6384c7d7 | 1777 | FIB_ITERATE_END(nftmp); |
98ac6176 | 1778 | } |
1a61882d | 1779 | } |