]>
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, | |
13 | struct ospf_area *oa); | |
b76aeb82 OZ |
14 | static int calc_next_hop(struct ospf_area *oa, |
15 | struct top_hash_entry *en, | |
16 | struct top_hash_entry *par); | |
86c84d76 | 17 | static void ospf_ext_spf(struct proto_ospf *po); |
1a61882d OF |
18 | static void rt_sync(struct proto_ospf *po); |
19 | ||
c3226991 | 20 | /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address) |
d82fc18d | 21 | as index, so we need to encapsulate RID to IP address */ |
c3226991 OZ |
22 | #ifdef OSPFv2 |
23 | #define ipa_from_rid(x) _MI(x) | |
24 | #else /* OSPFv3 */ | |
25 | #define ipa_from_rid(x) _MI(0,0,0,x) | |
26 | #endif | |
27 | ||
28 | ||
1a61882d OF |
29 | static void |
30 | fill_ri(orta * orta) | |
31 | { | |
32 | orta->type = RTS_DUMMY; | |
c3226991 | 33 | orta->options = 0; |
1a61882d OF |
34 | orta->oa = NULL; |
35 | orta->metric1 = LSINFINITY; | |
36 | orta->metric2 = LSINFINITY; | |
3b16080c | 37 | orta->nh = IPA_NONE; |
1a61882d OF |
38 | orta->ifa = NULL; |
39 | orta->ar = NULL; | |
40 | orta->tag = 0; | |
c27b2449 | 41 | orta->rid = 0; |
1a61882d | 42 | } |
dfa9a53a | 43 | |
a92847e7 | 44 | void |
1a61882d | 45 | ospf_rt_initort(struct fib_node *fn) |
a92847e7 | 46 | { |
1a61882d OF |
47 | ort *ri = (ort *) fn; |
48 | fill_ri(&ri->n); | |
1a61882d | 49 | memcpy(&ri->o, &ri->n, sizeof(orta)); |
98ac6176 | 50 | ri->efn = NULL; |
1a61882d | 51 | } |
a92847e7 | 52 | |
1a61882d | 53 | /* If new is better return 1 */ |
98ac6176 OF |
54 | |
55 | /* | |
56 | * This is hard to understand: | |
57 | * If rfc1583 is set to 1, it work likes normal route_better() | |
a2d5b405 | 58 | * But if it is set to 0, it prunes number of AS boundary |
98ac6176 OF |
59 | * routes before it starts the router decision |
60 | */ | |
1a61882d | 61 | static int |
98ac6176 | 62 | ri_better(struct proto_ospf *po, orta * new, ort *nefn, orta * old, ort *oefn, int rfc1583) |
1a61882d OF |
63 | { |
64 | int newtype = new->type; | |
65 | int oldtype = old->type; | |
66 | ||
67 | if (old->type == RTS_DUMMY) | |
68 | return 1; | |
69 | ||
70 | if (old->metric1 == LSINFINITY) | |
71 | return 1; | |
72 | ||
a2d5b405 | 73 | if (!rfc1583) |
1a61882d | 74 | { |
a2d5b405 | 75 | if ((new->type < RTS_OSPF_EXT1) && (new->oa->areaid == 0)) newtype = RTS_OSPF_IA; |
3034b384 | 76 | if ((old->type < RTS_OSPF_EXT1) && (old->oa->areaid == 0)) oldtype = RTS_OSPF_IA; |
3b16080c | 77 | } |
98ac6176 | 78 | |
a2d5b405 | 79 | if (newtype < oldtype) |
1a61882d OF |
80 | return 1; |
81 | ||
a2d5b405 | 82 | if (newtype > oldtype) |
98ac6176 | 83 | return 0; |
1a61882d | 84 | |
98ac6176 | 85 | /* Same type */ |
a2d5b405 | 86 | if (new->type == RTS_OSPF_EXT2) |
98ac6176 OF |
87 | { |
88 | if (new->metric2 < old->metric2) return 1; | |
89 | if (new->metric2 > old->metric2) return 0; | |
1a61882d | 90 | } |
98ac6176 | 91 | |
a2d5b405 | 92 | if (((new->type == RTS_OSPF_EXT2) || (new->type == RTS_OSPF_EXT1)) && (!po->rfc1583)) |
1a61882d | 93 | { |
a2d5b405 OF |
94 | newtype = nefn->n.type; |
95 | oldtype = oefn->n.type; | |
98ac6176 | 96 | |
a2d5b405 OF |
97 | if (nefn->n.oa->areaid == 0) newtype = RTS_OSPF_IA; |
98 | if (oefn->n.oa->areaid == 0) oldtype = RTS_OSPF_IA; | |
1a61882d | 99 | |
a2d5b405 OF |
100 | if (newtype < oldtype) return 1; |
101 | if (newtype > oldtype) return 0; | |
1a61882d OF |
102 | } |
103 | ||
1a61882d OF |
104 | if (new->metric1 < old->metric1) |
105 | return 1; | |
106 | ||
107 | if (new->metric1 > old->metric1) | |
108 | return 0; | |
109 | ||
1a61882d OF |
110 | if (new->oa->areaid > old->oa->areaid) return 1; /* Larger AREAID is preffered */ |
111 | ||
112 | return 0; /* Old is shorter or same */ | |
a92847e7 OF |
113 | } |
114 | ||
1a61882d OF |
115 | static void |
116 | ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest, | |
98ac6176 | 117 | orta * new, ort * ipath) |
aa1e082c | 118 | { |
98ac6176 OF |
119 | struct ospf_area *oa = new->oa; |
120 | ort *old; | |
1a61882d | 121 | |
98ac6176 | 122 | if (dest == ORT_NET) |
1a61882d | 123 | { |
98ac6176 OF |
124 | struct area_net *anet; |
125 | old = (ort *) fib_get(&po->rtf, &prefix, pxlen); | |
126 | if (ri_better(po, new, ipath, &old->n, old->efn, 1)) | |
127 | { | |
128 | memcpy(&old->n, new, sizeof(orta)); | |
129 | old->efn = ipath; | |
7de7470a OF |
130 | if ((new->type == RTS_OSPF) && (anet = (struct area_net *)fib_route(&oa->net_fib, prefix, pxlen))) |
131 | { | |
132 | anet->active = 1; | |
133 | if (new->metric1 > anet->metric) anet->metric = new->metric1; | |
134 | } | |
60e04f04 | 135 | } |
98ac6176 OF |
136 | } |
137 | else | |
138 | { | |
139 | old = (ort *) fib_get(&oa->rtr, &prefix, pxlen); | |
140 | ||
141 | if (ri_better(po, new, ipath, &old->n, old->efn, 1)) | |
142 | { | |
143 | memcpy(&old->n, new, sizeof(orta)); | |
144 | old->efn = ipath; | |
145 | } | |
1a61882d | 146 | } |
aa1e082c OF |
147 | } |
148 | ||
b49e6f5a OZ |
149 | static void |
150 | add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en) | |
151 | { | |
152 | orta nf; | |
153 | nf.type = RTS_OSPF; | |
154 | nf.options = 0; | |
155 | nf.metric1 = metric; | |
156 | nf.metric2 = LSINFINITY; | |
157 | nf.tag = 0; | |
158 | nf.oa = oa; | |
159 | nf.ar = en; | |
160 | nf.nh = en->nh; | |
161 | nf.ifa = en->nhi; | |
c27b2449 | 162 | nf.rid = en->lsa.rt; |
b49e6f5a OZ |
163 | |
164 | /* FIXME check nf.ifa on stubs */ | |
165 | ri_install(oa->po, px, pxlen, ORT_NET, &nf, NULL); | |
166 | } | |
167 | ||
168 | #ifdef OSPFv3 | |
169 | static void | |
170 | process_prefixes(struct ospf_area *oa) | |
171 | { | |
172 | struct proto_ospf *po = oa->po; | |
173 | struct proto *p = &po->proto; | |
174 | struct top_hash_entry *en, *src; | |
175 | struct ospf_lsa_prefix *px; | |
176 | ip_addr pxa; | |
177 | int pxlen; | |
178 | u8 pxopts; | |
179 | u16 metric; | |
180 | u32 *buf; | |
181 | int i; | |
182 | ||
183 | WALK_SLIST(en, po->lsal) | |
184 | { | |
185 | if (en->lsa.type != LSA_T_PREFIX) | |
186 | continue; | |
187 | ||
188 | if (en->domain != oa->areaid) | |
189 | continue; | |
190 | ||
191 | if (en->lsa.age == LSA_MAXAGE) | |
192 | continue; | |
193 | ||
194 | px = en->lsa_body; | |
9f0ba7b1 OZ |
195 | |
196 | /* For router prefix-LSA, we would like to find the first router-LSA */ | |
197 | if (px->ref_type == LSA_T_RT) | |
198 | src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt); | |
199 | else | |
200 | src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type); | |
b49e6f5a OZ |
201 | |
202 | if (!src) | |
203 | continue; | |
204 | ||
205 | if (src->lsa.age == LSA_MAXAGE) | |
206 | continue; | |
207 | ||
208 | if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET)) | |
209 | continue; | |
210 | ||
211 | buf = px->rest; | |
212 | for (i = 0; i < px->pxcount; i++) | |
213 | { | |
b66abe8e | 214 | buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric); |
b49e6f5a OZ |
215 | |
216 | if (pxopts & OPT_PX_NU) | |
217 | continue; | |
218 | ||
219 | add_network(oa, pxa, pxlen, src->dist + metric, src); | |
220 | } | |
221 | } | |
222 | } | |
223 | #endif | |
224 | ||
9f0ba7b1 OZ |
225 | |
226 | static void | |
227 | ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en) | |
228 | { | |
e81b440f | 229 | // struct proto *p = &oa->po->proto; |
9f0ba7b1 OZ |
230 | struct proto_ospf *po = oa->po; |
231 | orta nf; | |
232 | u32 i; | |
233 | ||
234 | struct ospf_lsa_rt *rt = en->lsa_body; | |
235 | struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1); | |
236 | ||
237 | for (i = 0; i < lsa_rt_count(&en->lsa); i++) | |
238 | { | |
239 | struct ospf_lsa_rt_link *rtl = rr + i; | |
240 | struct top_hash_entry *tmp = NULL; | |
241 | ||
242 | DBG(" Working on link: %R (type: %u) ", rtl->id, rtl->type); | |
243 | switch (rtl->type) | |
244 | { | |
245 | #ifdef OSPFv2 | |
246 | case LSART_STUB: | |
247 | /* | |
248 | * This violates rfc2328! But it is mostly harmless. | |
249 | */ | |
250 | DBG("\n"); | |
251 | ||
252 | nf.type = RTS_OSPF; | |
253 | nf.options = 0; | |
254 | nf.metric1 = act->dist + rtl->metric; | |
255 | nf.metric2 = LSINFINITY; | |
256 | nf.tag = 0; | |
257 | nf.oa = oa; | |
258 | nf.ar = act; | |
259 | nf.nh = act->nh; | |
260 | nf.ifa = act->nhi; | |
c27b2449 | 261 | nf.rid = act->lsa.rt; |
9f0ba7b1 OZ |
262 | |
263 | if (act == oa->rt) | |
264 | { | |
265 | struct ospf_iface *iff; | |
266 | ||
267 | WALK_LIST(iff, po->iface_list) /* Try to find corresponding interface */ | |
268 | { | |
269 | if (iff->iface && (iff->type != OSPF_IT_VLINK) && | |
270 | (rtl->id == (ipa_to_u32(ipa_mkmask(iff->iface->addr->pxlen)) | |
271 | & ipa_to_u32(iff->iface->addr->prefix)))) /* No VLINK and IP must match */ | |
272 | { | |
273 | nf.ifa = iff; | |
274 | break; | |
275 | } | |
276 | } | |
277 | } | |
278 | ||
279 | if (!nf.ifa) | |
280 | continue; | |
281 | ||
282 | ri_install(po, ipa_from_u32(rtl->id), | |
283 | ipa_mklen(ipa_from_u32(rtl->data)), ORT_NET, &nf, NULL); | |
284 | break; | |
285 | #endif | |
286 | ||
287 | case LSART_NET: | |
288 | #ifdef OSPFv2 | |
289 | /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */ | |
290 | tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id); | |
291 | #else /* OSPFv3 */ | |
292 | tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET); | |
293 | #endif | |
294 | if (tmp == NULL) | |
295 | DBG("Not found!\n"); | |
296 | else | |
297 | DBG("Found. :-)\n"); | |
298 | break; | |
299 | ||
300 | case LSART_VLNK: | |
301 | case LSART_PTP: | |
302 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); | |
303 | DBG("PTP found.\n"); | |
304 | break; | |
305 | default: | |
306 | log("Unknown link type in router lsa. (rid = %R)", act->lsa.id); | |
307 | break; | |
308 | } | |
309 | if (tmp) | |
310 | DBG("Going to add cand, Mydist: %u, Req: %u\n", | |
311 | tmp->dist, act->dist + rtl->metric); | |
312 | add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa); | |
313 | } | |
314 | } | |
315 | ||
99f5fc14 | 316 | /* 16.1 calculating shortest paths for an area */ |
1a61882d | 317 | static void |
a02c6c18 | 318 | ospf_rt_spfa(struct ospf_area *oa) |
dfa9a53a | 319 | { |
2e10a170 OF |
320 | struct proto *p = &oa->po->proto; |
321 | struct proto_ospf *po = oa->po; | |
9f0ba7b1 | 322 | struct ospf_lsa_rt *rt; |
d345cda5 | 323 | struct ospf_lsa_net *ln; |
98ac6176 OF |
324 | struct ospf_iface *iface; |
325 | struct top_hash_entry *act, *tmp; | |
9f0ba7b1 OZ |
326 | u32 i, *rts; |
327 | orta nf; | |
98ac6176 OF |
328 | node *n; |
329 | ||
2e10a170 OF |
330 | if (oa->rt == NULL) |
331 | return; | |
102e3e0e | 332 | |
3aab39f5 | 333 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid); |
1a61882d | 334 | |
cd092260 | 335 | if (oa->rt->dist != LSINFINITY) |
3b16080c | 336 | bug("Aging was not processed."); |
cd092260 | 337 | |
c3226991 | 338 | /* 16.1. (1) */ |
dfa9a53a | 339 | init_list(&oa->cand); /* Empty list of candidates */ |
2e10a170 | 340 | oa->trcap = 0; |
dfa9a53a | 341 | |
85195f1a OF |
342 | DBG("LSA db prepared, adding me into candidate list.\n"); |
343 | ||
2e10a170 OF |
344 | oa->rt->dist = 0; |
345 | oa->rt->color = CANDIDATE; | |
85195f1a | 346 | add_head(&oa->cand, &oa->rt->cn); |
3aab39f5 OZ |
347 | DBG("RT LSA: rt: %R, id: %R, type: %u\n", |
348 | oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type); | |
dfa9a53a | 349 | |
2e10a170 | 350 | while (!EMPTY_LIST(oa->cand)) |
dfa9a53a | 351 | { |
2e10a170 OF |
352 | n = HEAD(oa->cand); |
353 | act = SKIP_BACK(struct top_hash_entry, cn, n); | |
dfa9a53a | 354 | rem_node(n); |
dfa9a53a | 355 | |
3aab39f5 OZ |
356 | DBG("Working on LSA: rt: %R, id: %R, type: %u\n", |
357 | act->lsa.rt, act->lsa.id, act->lsa.type); | |
85195f1a | 358 | |
2e10a170 OF |
359 | act->color = INSPF; |
360 | switch (act->lsa.type) | |
dfa9a53a | 361 | { |
2e10a170 OF |
362 | case LSA_T_RT: |
363 | rt = (struct ospf_lsa_rt *) act->lsa_body; | |
c3226991 | 364 | if (rt->options & OPT_RT_V) |
2e10a170 | 365 | oa->trcap = 1; |
b49e6f5a | 366 | |
cbf8b08d OZ |
367 | /* In OSPFv2, just ASBRs and ABRs are needed to add to oa->rtr table */ |
368 | // ((rt->options & OPT_RT_V) || (rt->options & OPT_RT_E)) | |
369 | ||
370 | nf.type = RTS_OSPF; | |
371 | nf.options = rt->options; | |
372 | nf.metric1 = act->dist; | |
373 | nf.metric2 = LSINFINITY; | |
374 | nf.tag = 0; | |
375 | nf.oa = oa; | |
376 | nf.ar = act; | |
377 | nf.nh = act->nh; | |
378 | nf.ifa = act->nhi; | |
c27b2449 | 379 | nf.rid = act->lsa.rt; |
cbf8b08d | 380 | ri_install(po, ipa_from_rid(act->lsa.rt), MAX_PREFIX_LENGTH, ORT_ROUTER, &nf, NULL); |
b49e6f5a | 381 | |
c3226991 | 382 | #ifdef OSPFv2 |
9f0ba7b1 | 383 | ospf_rt_spfa_rtlinks(oa, act, act); |
c3226991 | 384 | #else /* OSPFv3 */ |
9f0ba7b1 OZ |
385 | for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt); |
386 | tmp; tmp = ospf_hash_find_rt_next(tmp)) | |
387 | ospf_rt_spfa_rtlinks(oa, act, tmp); | |
c3226991 | 388 | #endif |
b49e6f5a | 389 | |
2e10a170 OF |
390 | break; |
391 | case LSA_T_NET: | |
392 | ln = act->lsa_body; | |
b49e6f5a OZ |
393 | |
394 | #ifdef OSPFv2 | |
395 | add_network(oa, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask), | |
396 | ipa_mklen(ln->netmask), act->dist, act); | |
397 | #endif | |
1a61882d | 398 | |
2e10a170 | 399 | rts = (u32 *) (ln + 1); |
c3226991 | 400 | for (i = 0; i < lsa_net_count(&act->lsa); i++) |
2e10a170 | 401 | { |
3aab39f5 | 402 | DBG(" Working on router %R ", rts[i]); |
9f0ba7b1 | 403 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); |
2e10a170 OF |
404 | if (tmp != NULL) |
405 | DBG("Found :-)\n"); | |
406 | else | |
407 | DBG("Not found!\n"); | |
5d3f5552 | 408 | add_cand(&oa->cand, tmp, act, act->dist, oa); |
2e10a170 OF |
409 | } |
410 | break; | |
dfa9a53a | 411 | } |
d345cda5 | 412 | } |
98ac6176 | 413 | |
b49e6f5a OZ |
414 | #ifdef OSPFv3 |
415 | process_prefixes(oa); | |
416 | #endif | |
417 | ||
98ac6176 OF |
418 | /* Find new/lost VLINK peers */ |
419 | WALK_LIST(iface, po->iface_list) | |
420 | { | |
421 | if ((iface->type == OSPF_IT_VLINK) && (iface->voa == oa)) | |
422 | { | |
9f0ba7b1 OZ |
423 | if ((tmp = ospf_hash_find_rt(po->gr, oa->areaid, iface->vid)) && |
424 | (!ipa_equal(tmp->lb, IPA_NONE))) | |
98ac6176 | 425 | { |
5d3f5552 | 426 | if ((iface->state != OSPF_IS_PTP) || (iface->iface != tmp->nhi->iface) || (!ipa_equal(iface->vip, tmp->lb))) |
3b16080c | 427 | { |
3aab39f5 | 428 | OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id); |
3b16080c | 429 | ospf_iface_sm(iface, ISM_DOWN); |
5d3f5552 | 430 | iface->iface = tmp->nhi->iface; |
3b16080c OF |
431 | iface->vip = tmp->lb; |
432 | ospf_iface_sm(iface, ISM_UP); | |
433 | } | |
98ac6176 OF |
434 | } |
435 | else | |
436 | { | |
3b16080c OF |
437 | if (iface->state > OSPF_IS_DOWN) |
438 | { | |
3aab39f5 | 439 | OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid); |
3b16080c OF |
440 | ospf_iface_sm(iface, ISM_DOWN); |
441 | } | |
98ac6176 OF |
442 | } |
443 | } | |
444 | } | |
445 | } | |
446 | ||
447 | static int | |
9807690b | 448 | link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par) |
98ac6176 OF |
449 | { |
450 | u32 i, *rts; | |
451 | struct ospf_lsa_net *ln; | |
452 | struct ospf_lsa_rt *rt; | |
453 | struct ospf_lsa_rt_link *rtl, *rr; | |
9807690b | 454 | struct top_hash_entry *tmp; |
86c84d76 | 455 | struct proto_ospf *po = oa->po; |
98ac6176 | 456 | |
9807690b OZ |
457 | if (!en || !par) return 0; |
458 | ||
459 | // FIXME lb should be properly set for vlinks */ | |
460 | en->lb = IPA_NONE; | |
461 | switch (en->lsa.type) | |
98ac6176 OF |
462 | { |
463 | case LSA_T_RT: | |
9807690b | 464 | rt = (struct ospf_lsa_rt *) en->lsa_body; |
98ac6176 | 465 | rr = (struct ospf_lsa_rt_link *) (rt + 1); |
9807690b | 466 | for (i = 0; i < lsa_rt_count(&en->lsa); i++) |
98ac6176 OF |
467 | { |
468 | rtl = (rr + i); | |
469 | switch (rtl->type) | |
470 | { | |
471 | case LSART_STUB: | |
472 | break; | |
473 | case LSART_NET: | |
9807690b OZ |
474 | #ifdef OSPFv2 |
475 | /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */ | |
476 | tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id); | |
477 | #else /* OSPFv3 */ | |
478 | tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET); | |
479 | #endif | |
480 | if (tmp == par) | |
ba39197c OZ |
481 | { |
482 | #ifdef OSPFv2 | |
cf0858c2 | 483 | en->lb = ipa_from_u32(rtl->data); |
ba39197c OZ |
484 | #endif |
485 | return 1; | |
486 | } | |
9807690b | 487 | |
98ac6176 OF |
488 | break; |
489 | case LSART_VLNK: | |
490 | case LSART_PTP: | |
9807690b OZ |
491 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); |
492 | if (tmp == par) | |
98ac6176 | 493 | return 1; |
9807690b | 494 | |
98ac6176 OF |
495 | break; |
496 | default: | |
9807690b | 497 | log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt); |
98ac6176 OF |
498 | break; |
499 | } | |
500 | } | |
501 | break; | |
502 | case LSA_T_NET: | |
9807690b | 503 | ln = en->lsa_body; |
98ac6176 | 504 | rts = (u32 *) (ln + 1); |
9807690b | 505 | for (i = 0; i < lsa_net_count(&en->lsa); i++) |
98ac6176 | 506 | { |
9807690b OZ |
507 | tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); |
508 | if (tmp == par) | |
98ac6176 | 509 | return 1; |
98ac6176 OF |
510 | } |
511 | break; | |
512 | default: | |
9807690b | 513 | bug("Unknown lsa type %x.", en->lsa.type); |
98ac6176 OF |
514 | } |
515 | return 0; | |
516 | } | |
517 | ||
99f5fc14 | 518 | /* 16.3 examining summary-LSAs in transit areas */ |
98ac6176 OF |
519 | static void |
520 | ospf_rt_sum_tr(struct ospf_area *oa) | |
521 | { | |
e81b440f | 522 | // struct proto *p = &oa->po->proto; |
98ac6176 | 523 | struct proto_ospf *po = oa->po; |
3b16080c | 524 | struct ospf_area *bb = po->backbone; |
c3226991 | 525 | ip_addr ip, abrip; |
98ac6176 | 526 | struct top_hash_entry *en; |
c3226991 OZ |
527 | u32 dst_rid, metric, options; |
528 | int pxlen = -1, type = -1; | |
98ac6176 OF |
529 | ort *re = NULL, *abr; |
530 | orta nf; | |
531 | ||
a2d5b405 | 532 | if (!bb) return; |
98ac6176 | 533 | |
86c84d76 | 534 | WALK_SLIST(en, po->lsal) |
98ac6176 | 535 | { |
c3226991 | 536 | if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) |
86c84d76 | 537 | continue; |
c3226991 OZ |
538 | |
539 | if (en->domain != oa->areaid) | |
540 | continue; | |
541 | ||
99f5fc14 | 542 | /* 16.3 (1a) */ |
98ac6176 OF |
543 | if (en->lsa.age == LSA_MAXAGE) |
544 | continue; | |
c3226991 | 545 | |
99f5fc14 OZ |
546 | // if (en->dist == LSINFINITY) |
547 | // continue; | |
98ac6176 | 548 | |
99f5fc14 | 549 | /* 16.3 (2) */ |
8a70a13e | 550 | if (en->lsa.rt == po->router_id) |
98ac6176 OF |
551 | continue; |
552 | ||
98ac6176 OF |
553 | if (en->lsa.type == LSA_T_SUM_NET) |
554 | { | |
c3226991 OZ |
555 | #ifdef OSPFv2 |
556 | struct ospf_lsa_sum *ls = en->lsa_body; | |
557 | pxlen = ipa_mklen(ls->netmask); | |
558 | ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask); | |
559 | #else /* OSPFv3 */ | |
560 | u8 pxopts; | |
b49e6f5a | 561 | u16 rest; |
c3226991 | 562 | struct ospf_lsa_sum_net *ls = en->lsa_body; |
b66abe8e | 563 | lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest); |
b49e6f5a | 564 | |
c3226991 OZ |
565 | if (pxopts & OPT_PX_NU) |
566 | continue; | |
567 | #endif | |
568 | ||
569 | metric = ls->metric & METRIC_MASK; | |
570 | options = 0; | |
98ac6176 | 571 | type = ORT_NET; |
c3226991 | 572 | re = (ort *) fib_find(&po->rtf, &ip, pxlen); |
98ac6176 | 573 | } |
c3226991 | 574 | else if (en->lsa.type == LSA_T_SUM_RT) |
98ac6176 | 575 | { |
c3226991 OZ |
576 | #ifdef OSPFv2 |
577 | struct ospf_lsa_sum *ls = en->lsa_body; | |
578 | dst_rid = en->lsa.id; | |
579 | options = 0; | |
580 | #else /* OSPFv3 */ | |
581 | struct ospf_lsa_sum_rt *ls = en->lsa_body; | |
582 | dst_rid = ls->drid; | |
583 | options = ls->options & OPTIONS_MASK; | |
584 | #endif | |
585 | ||
586 | ip = ipa_from_rid(dst_rid); | |
061ab802 | 587 | pxlen = MAX_PREFIX_LENGTH; |
c3226991 OZ |
588 | metric = ls->metric & METRIC_MASK; |
589 | options |= ORTA_ASBR; | |
98ac6176 | 590 | type = ORT_ROUTER; |
c3226991 | 591 | re = (ort *) fib_find(&bb->rtr, &ip, pxlen); |
98ac6176 | 592 | } |
c3226991 | 593 | |
99f5fc14 OZ |
594 | /* 16.3 (1b) */ |
595 | if (metric == LSINFINITY) | |
596 | continue; | |
597 | ||
598 | /* 16.3 (3) */ | |
a2d5b405 OF |
599 | if (!re) continue; |
600 | if (re->n.oa->areaid != 0) continue; | |
601 | if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue; | |
98ac6176 | 602 | |
99f5fc14 | 603 | /* 16.3. (4) */ |
c3226991 | 604 | abrip = ipa_from_rid(en->lsa.rt); |
061ab802 | 605 | abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); |
a2d5b405 | 606 | if (!abr) continue; |
98ac6176 | 607 | |
98ac6176 | 608 | nf.type = re->n.type; |
c3226991 OZ |
609 | nf.options = options; |
610 | nf.metric1 = abr->n.metric1 + metric; | |
98ac6176 | 611 | nf.metric2 = LSINFINITY; |
3f670371 | 612 | nf.tag = 0; |
98ac6176 OF |
613 | nf.oa = oa; |
614 | nf.ar = abr->n.ar; | |
615 | nf.nh = abr->n.nh; | |
616 | nf.ifa = abr->n.ifa; | |
c27b2449 | 617 | nf.rid = en->lsa.rt; /* ABR ID */ |
c3226991 | 618 | ri_install(po, ip, pxlen, type, &nf, NULL); |
98ac6176 | 619 | } |
fafe44b6 | 620 | } |
98ac6176 | 621 | |
99f5fc14 | 622 | /* 16.2 calculating inter-area routes */ |
98ac6176 OF |
623 | static void |
624 | ospf_rt_sum(struct ospf_area *oa) | |
625 | { | |
626 | struct proto_ospf *po = oa->po; | |
627 | struct proto *p = &po->proto; | |
628 | struct top_hash_entry *en; | |
c3226991 OZ |
629 | ip_addr ip, abrip; /* abrIP is actually ID */ |
630 | u32 dst_rid, metric, options; | |
98ac6176 OF |
631 | struct area_net *anet; |
632 | orta nf; | |
63ca37f3 | 633 | ort *abr; |
c3226991 | 634 | int pxlen = -1, type = -1; |
fafe44b6 | 635 | |
3aab39f5 | 636 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid); |
b8f17cf1 | 637 | |
86c84d76 | 638 | WALK_SLIST(en, po->lsal) |
98ac6176 | 639 | { |
c3226991 OZ |
640 | if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) |
641 | continue; | |
642 | ||
643 | if (en->domain != oa->areaid) | |
86c84d76 | 644 | continue; |
c3226991 | 645 | |
98ac6176 OF |
646 | /* Page 169 (1) */ |
647 | if (en->lsa.age == LSA_MAXAGE) | |
648 | continue; | |
c3226991 | 649 | |
98ac6176 | 650 | /* Page 169 (2) */ |
8a70a13e | 651 | if (en->lsa.rt == po->router_id) |
98ac6176 OF |
652 | continue; |
653 | ||
98ac6176 OF |
654 | |
655 | if (en->lsa.type == LSA_T_SUM_NET) | |
656 | { | |
5d3f5552 OF |
657 | struct ospf_area *oaa; |
658 | int skip = 0; | |
c3226991 OZ |
659 | |
660 | #ifdef OSPFv2 | |
661 | struct ospf_lsa_sum *ls = en->lsa_body; | |
662 | pxlen = ipa_mklen(ls->netmask); | |
663 | ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask); | |
664 | #else /* OSPFv3 */ | |
665 | u8 pxopts; | |
b49e6f5a | 666 | u16 rest; |
c3226991 | 667 | struct ospf_lsa_sum_net *ls = en->lsa_body; |
b66abe8e | 668 | lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest); |
b49e6f5a | 669 | |
c3226991 OZ |
670 | if (pxopts & OPT_PX_NU) |
671 | continue; | |
672 | #endif | |
673 | ||
674 | metric = ls->metric & METRIC_MASK; | |
675 | options = 0; | |
676 | type = ORT_NET; | |
677 | ||
98ac6176 | 678 | /* Page 169 (3) */ |
5d3f5552 OF |
679 | WALK_LIST(oaa, po->area_list) |
680 | { | |
c3226991 | 681 | if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active) |
5d3f5552 OF |
682 | { |
683 | skip = 1; | |
684 | break; | |
685 | } | |
686 | } | |
687 | if (skip) continue; | |
98ac6176 | 688 | } |
3e2bd0f1 | 689 | else |
98ac6176 | 690 | { |
c3226991 OZ |
691 | #ifdef OSPFv2 |
692 | struct ospf_lsa_sum *ls = en->lsa_body; | |
693 | dst_rid = en->lsa.id; | |
694 | options = 0; | |
695 | #else /* OSPFv3 */ | |
696 | struct ospf_lsa_sum_rt *ls = en->lsa_body; | |
697 | dst_rid = ls->drid; | |
698 | options = ls->options & OPTIONS_MASK; | |
699 | #endif | |
700 | ||
701 | ip = ipa_from_rid(dst_rid); | |
061ab802 | 702 | pxlen = MAX_PREFIX_LENGTH; |
c3226991 OZ |
703 | metric = ls->metric & METRIC_MASK; |
704 | options |= ORTA_ASBR; | |
98ac6176 OF |
705 | type = ORT_ROUTER; |
706 | } | |
98ac6176 | 707 | |
c3226991 OZ |
708 | /* Page 169 (1) */ |
709 | if (metric == LSINFINITY) | |
710 | continue; | |
711 | ||
712 | /* Page 169 (4) */ | |
713 | abrip = ipa_from_rid(en->lsa.rt); | |
061ab802 | 714 | if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH))) continue; |
98ac6176 | 715 | if (abr->n.metric1 == LSINFINITY) continue; |
c3226991 | 716 | if (!(abr->n.options & ORTA_ABR)) continue; |
98ac6176 | 717 | |
98ac6176 | 718 | nf.type = RTS_OSPF_IA; |
c3226991 OZ |
719 | nf.options = options; |
720 | nf.metric1 = abr->n.metric1 + metric; | |
98ac6176 | 721 | nf.metric2 = LSINFINITY; |
3f670371 | 722 | nf.tag = 0; |
98ac6176 OF |
723 | nf.oa = oa; |
724 | nf.ar = abr->n.ar; | |
725 | nf.nh = abr->n.nh; | |
726 | nf.ifa = abr->n.ifa; | |
c27b2449 | 727 | nf.rid = en->lsa.rt; /* ABR ID */ |
c3226991 | 728 | ri_install(po, ip, pxlen, type, &nf, NULL); |
98ac6176 OF |
729 | } |
730 | } | |
731 | ||
732 | /** | |
733 | * ospf_rt_spf - calculate internal routes | |
734 | * @po: OSPF protocol | |
735 | * | |
736 | * Calculation of internal paths in an area is described in 16.1 of RFC 2328. | |
737 | * It's based on Dijkstra's shortest path tree algorithms. | |
738 | * This function is invoked from ospf_disp(). | |
739 | */ | |
b8f17cf1 OF |
740 | void |
741 | ospf_rt_spf(struct proto_ospf *po) | |
742 | { | |
1a61882d | 743 | struct proto *p = &po->proto; |
b8f17cf1 | 744 | struct ospf_area *oa; |
1a61882d | 745 | ort *ri; |
98ac6176 OF |
746 | struct area_net *anet; |
747 | ||
748 | if (po->areano == 0) return; | |
1a61882d | 749 | |
86c84d76 OF |
750 | po->cleanup = 1; |
751 | ||
1a61882d OF |
752 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation"); |
753 | ||
c3226991 | 754 | /* 16. (1) - Invalidate old routing table */ |
98ac6176 | 755 | FIB_WALK(&po->rtf, nftmp) |
1a61882d OF |
756 | { |
757 | ri = (ort *) nftmp; | |
758 | memcpy(&ri->o, &ri->n, sizeof(orta)); /* Backup old data */ | |
759 | fill_ri(&ri->n); | |
760 | } | |
761 | FIB_WALK_END; | |
762 | ||
763 | ||
b8f17cf1 OF |
764 | WALK_LIST(oa, po->area_list) |
765 | { | |
98ac6176 OF |
766 | FIB_WALK(&oa->rtr, nftmp) |
767 | { | |
768 | ri = (ort *) nftmp; | |
769 | memcpy(&ri->o, &ri->n, sizeof(orta)); /* Backup old data */ | |
770 | fill_ri(&ri->n); | |
771 | } | |
772 | FIB_WALK_END; | |
773 | ||
98ac6176 OF |
774 | FIB_WALK(&oa->net_fib, nftmp) |
775 | { | |
776 | anet = (struct area_net *) nftmp; | |
777 | anet->active = 0; | |
5506c82c | 778 | anet->metric = 1; |
98ac6176 OF |
779 | } |
780 | FIB_WALK_END; | |
c3226991 OZ |
781 | |
782 | /* 16. (2) */ | |
b8f17cf1 OF |
783 | ospf_rt_spfa(oa); |
784 | } | |
1a61882d | 785 | |
c3226991 | 786 | /* 16. (3) */ |
5d3f5552 | 787 | if ((po->areano == 1) || (!po->backbone)) |
1a61882d | 788 | { |
98ac6176 | 789 | ospf_rt_sum(HEAD(po->area_list)); |
1a61882d OF |
790 | } |
791 | else | |
792 | { | |
5d3f5552 | 793 | ospf_rt_sum(po->backbone); |
98ac6176 | 794 | } |
1a61882d | 795 | |
c3226991 | 796 | /* 16. (4) */ |
98ac6176 OF |
797 | WALK_LIST(oa, po->area_list) |
798 | { | |
799 | if (oa->trcap && (oa->areaid != 0)) | |
1a61882d | 800 | { |
98ac6176 OF |
801 | ospf_rt_sum_tr(oa); |
802 | break; | |
1a61882d OF |
803 | } |
804 | } | |
98ac6176 | 805 | |
c3226991 | 806 | /* 16. (5) */ |
86c84d76 OF |
807 | ospf_ext_spf(po); |
808 | ||
1a61882d | 809 | rt_sync(po); |
86c84d76 OF |
810 | |
811 | po->calcrt = 0; | |
b8f17cf1 OF |
812 | } |
813 | ||
1186369b | 814 | /** |
86c84d76 | 815 | * ospf_ext_spf - calculate external paths |
1186369b OF |
816 | * @po: protocol |
817 | * | |
818 | * After routing table for any area is calculated, calculation of external | |
c3226991 | 819 | * path is invoked. This process is described in 16.4 of RFC 2328. |
1186369b OF |
820 | * Inter- and Intra-area paths are always prefered over externals. |
821 | */ | |
b8f17cf1 | 822 | static void |
86c84d76 | 823 | ospf_ext_spf(struct proto_ospf *po) |
fafe44b6 | 824 | { |
98ac6176 | 825 | ort *nf1, *nf2, *nfh; |
1a61882d OF |
826 | orta nfa; |
827 | struct top_hash_entry *en; | |
2e10a170 | 828 | struct proto *p = &po->proto; |
aa1e082c | 829 | struct ospf_lsa_ext *le; |
c3226991 OZ |
830 | int pxlen, ebit, rt_fwaddr_valid; |
831 | ip_addr ip, nh, rtid, rt_fwaddr; | |
5d3f5552 | 832 | struct ospf_iface *nhi = NULL; |
c3226991 | 833 | u32 br_metric, rt_metric, rt_tag; |
8fb0c2c2 | 834 | neighbor *nn; |
98ac6176 | 835 | struct ospf_area *atmp; |
aa1e082c | 836 | |
1a61882d | 837 | OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes"); |
aa1e082c | 838 | |
86c84d76 | 839 | WALK_SLIST(en, po->lsal) |
aa1e082c | 840 | { |
c3226991 | 841 | /* 16.4. (1) */ |
2e10a170 OF |
842 | if (en->lsa.type != LSA_T_EXT) |
843 | continue; | |
844 | if (en->lsa.age == LSA_MAXAGE) | |
845 | continue; | |
c3226991 OZ |
846 | |
847 | /* 16.4. (2) */ | |
8a70a13e | 848 | if (en->lsa.rt == po->router_id) |
2e10a170 | 849 | continue; |
aa1e082c | 850 | |
f9c799a0 OZ |
851 | DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n", |
852 | p->name, en->lsa.id, en->lsa.rt, en->lsa.type); | |
273fd2c1 | 853 | |
c3226991 OZ |
854 | le = en->lsa_body; |
855 | ||
856 | rt_metric = le->metric & METRIC_MASK; | |
857 | ebit = le->metric & LSA_EXT_EBIT; | |
858 | ||
859 | if (rt_metric == LSINFINITY) | |
2e10a170 | 860 | continue; |
c3226991 OZ |
861 | |
862 | #ifdef OSPFv2 | |
2e10a170 | 863 | ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask); |
c3226991 OZ |
864 | pxlen = ipa_mklen(le->netmask); |
865 | rt_fwaddr = le->fwaddr; | |
866 | rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE); | |
867 | rt_tag = le->tag; | |
868 | #else /* OSPFv3 */ | |
869 | u8 pxopts; | |
b49e6f5a | 870 | u16 rest; |
c3226991 | 871 | u32 *buf = le->rest; |
b66abe8e | 872 | buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest); |
c3226991 OZ |
873 | |
874 | if (pxopts & OPT_PX_NU) | |
875 | continue; | |
876 | ||
877 | rt_fwaddr_valid = le->metric & LSA_EXT_FBIT; | |
878 | if (rt_fwaddr_valid) | |
b66abe8e | 879 | buf = lsa_get_ipv6_addr(buf, &rt_fwaddr); |
c3226991 OZ |
880 | else |
881 | rt_fwaddr = IPA_NONE; | |
882 | ||
883 | if (le->metric & LSA_EXT_TBIT) | |
884 | rt_tag = *buf++; | |
885 | else | |
886 | rt_tag = 0; | |
887 | #endif | |
888 | ||
889 | if (pxlen < 0) | |
508c36ab | 890 | { |
34a877cc OZ |
891 | log(L_WARN "%s: Invalid mask in LSA (Type: %04x, Id: %R, Rt: %R)", |
892 | p->name, en->lsa.type, en->lsa.id, en->lsa.rt); | |
4ee21789 | 893 | continue; |
508c36ab | 894 | } |
1a61882d OF |
895 | nhi = NULL; |
896 | nh = IPA_NONE; | |
aa1e082c | 897 | |
c3226991 OZ |
898 | /* 16.4. (3) */ |
899 | rtid = ipa_from_rid(en->lsa.rt); | |
98ac6176 OF |
900 | nf1 = NULL; |
901 | WALK_LIST(atmp, po->area_list) | |
902 | { | |
061ab802 | 903 | nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH); |
a2d5b405 OF |
904 | if (nfh == NULL) continue; |
905 | if (nf1 == NULL) nf1 = nfh; | |
906 | else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh; | |
98ac6176 OF |
907 | } |
908 | ||
909 | if (!nf1) | |
1a61882d | 910 | continue; /* No AS boundary router found */ |
aa1e082c | 911 | |
1a61882d OF |
912 | if (nf1->n.metric1 == LSINFINITY) |
913 | continue; /* distance is INF */ | |
aa1e082c | 914 | |
c3226991 | 915 | if (!(nf1->n.options & ORTA_ASBR)) |
1a61882d | 916 | continue; /* It is not ASBR */ |
508c36ab | 917 | |
c3226991 | 918 | if (!rt_fwaddr_valid) |
aa1e082c | 919 | { |
1a61882d OF |
920 | nh = nf1->n.nh; |
921 | nhi = nf1->n.ifa; | |
98ac6176 | 922 | nfh = nf1; |
c3226991 | 923 | br_metric = nf1->n.metric1; |
508c36ab | 924 | } |
1a61882d | 925 | else |
c3226991 | 926 | { |
061ab802 | 927 | nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH); |
98ac6176 OF |
928 | |
929 | if (!nf2) | |
273fd2c1 | 930 | { |
c3226991 | 931 | DBG("Cannot find network route (GW=%I)\n", rt_fwaddr); |
2e10a170 | 932 | continue; |
273fd2c1 | 933 | } |
98ac6176 | 934 | |
c3226991 | 935 | if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL) |
8fb0c2c2 | 936 | { |
c3226991 | 937 | nh = rt_fwaddr; |
5d3f5552 | 938 | nhi = ospf_iface_find(po, nn->iface); |
8fb0c2c2 | 939 | } |
28a6e1aa OF |
940 | else |
941 | { | |
1a61882d OF |
942 | nh = nf2->n.nh; |
943 | nhi = nf2->n.ifa; | |
28a6e1aa | 944 | } |
98ac6176 | 945 | |
c3226991 OZ |
946 | br_metric = nf2->n.metric1; |
947 | if (br_metric == LSINFINITY) | |
a2d5b405 | 948 | continue; /* distance is INF */ |
aa1e082c | 949 | } |
508c36ab | 950 | |
c3226991 OZ |
951 | if (ebit) |
952 | { | |
953 | nfa.type = RTS_OSPF_EXT2; | |
954 | nfa.metric1 = br_metric; | |
955 | nfa.metric2 = rt_metric; | |
956 | } | |
957 | else | |
958 | { | |
959 | nfa.type = RTS_OSPF_EXT1; | |
960 | nfa.metric1 = br_metric + rt_metric; | |
961 | nfa.metric2 = LSINFINITY; | |
962 | } | |
963 | ||
964 | nfa.options = 0; | |
965 | nfa.tag = rt_tag; | |
a2d5b405 | 966 | nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone; |
1a61882d OF |
967 | nfa.ar = nf1->n.ar; |
968 | nfa.nh = nh; | |
969 | nfa.ifa = nhi; | |
c27b2449 | 970 | nfa.rid = en->lsa.rt; |
c3226991 | 971 | ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh); |
aa1e082c OF |
972 | } |
973 | ||
dfa9a53a OF |
974 | } |
975 | ||
baa5dd6c | 976 | /* Add LSA into list of candidates in Dijkstra's algorithm */ |
b8f17cf1 | 977 | static void |
2e10a170 | 978 | add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, |
c3226991 | 979 | u32 dist, struct ospf_area *oa) |
dfa9a53a | 980 | { |
2e10a170 OF |
981 | node *prev, *n; |
982 | int added = 0; | |
e80e9d0d | 983 | struct top_hash_entry *act; |
dfa9a53a | 984 | |
b49e6f5a | 985 | /* 16.1. (2b) */ |
2e10a170 OF |
986 | if (en == NULL) |
987 | return; | |
988 | if (en->lsa.age == LSA_MAXAGE) | |
989 | return; | |
98ac6176 | 990 | |
b49e6f5a OZ |
991 | #ifdef OSPFv3 |
992 | if (en->lsa.type == LSA_T_RT) | |
993 | { | |
994 | struct ospf_lsa_rt *rt = en->lsa_body; | |
995 | if (!(rt->options & OPT_V6) || !(rt->options & OPT_R)) | |
996 | return; | |
997 | } | |
998 | #endif | |
999 | ||
c3226991 | 1000 | /* 16.1. (2c) */ |
2e10a170 OF |
1001 | if (en->color == INSPF) |
1002 | return; | |
dfa9a53a | 1003 | |
c3226991 | 1004 | /* 16.1. (2d) */ |
2e10a170 OF |
1005 | if (dist >= en->dist) |
1006 | return; | |
e80e9d0d | 1007 | /* |
98ac6176 | 1008 | * FIXME The line above (=) is not a bug, but we don't support multiple |
1a61882d | 1009 | * next hops. I'll start as soon as nest will |
e80e9d0d | 1010 | */ |
98ac6176 | 1011 | |
9807690b | 1012 | /* We should check whether there is a reverse link from en to par, */ |
98ac6176 OF |
1013 | if (!link_back(oa, en, par)) |
1014 | return; | |
1015 | ||
b76aeb82 OZ |
1016 | if (!calc_next_hop(oa, en, par)) |
1017 | { | |
1018 | log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)", | |
1019 | en->lsa.type, en->lsa.id, en->lsa.rt); | |
1020 | return; | |
1021 | } | |
1022 | ||
3aab39f5 OZ |
1023 | DBG(" Adding candidate: rt: %R, id: %R, type: %u\n", |
1024 | en->lsa.rt, en->lsa.id, en->lsa.type); | |
2e10a170 | 1025 | |
1a61882d OF |
1026 | if (en->color == CANDIDATE) |
1027 | { /* We found a shorter path */ | |
e80e9d0d | 1028 | rem_node(&en->cn); |
dfa9a53a | 1029 | } |
2e10a170 OF |
1030 | en->dist = dist; |
1031 | en->color = CANDIDATE; | |
dfa9a53a | 1032 | |
2e10a170 | 1033 | prev = NULL; |
dfa9a53a | 1034 | |
2e10a170 | 1035 | if (EMPTY_LIST(*l)) |
e80e9d0d | 1036 | { |
2e10a170 | 1037 | add_head(l, &en->cn); |
85195f1a OF |
1038 | } |
1039 | else | |
1040 | { | |
2e10a170 | 1041 | WALK_LIST(n, *l) |
dfa9a53a | 1042 | { |
2e10a170 OF |
1043 | act = SKIP_BACK(struct top_hash_entry, cn, n); |
1044 | if ((act->dist > dist) || | |
1045 | ((act->dist == dist) && (act->lsa.type == LSA_T_NET))) | |
c3226991 | 1046 | /* FIXME - shouldn't be here LSA_T_RT ??? */ |
85195f1a | 1047 | { |
2e10a170 OF |
1048 | if (prev == NULL) |
1049 | add_head(l, &en->cn); | |
1050 | else | |
1051 | insert_node(&en->cn, prev); | |
1052 | added = 1; | |
1053 | break; | |
85195f1a | 1054 | } |
2e10a170 | 1055 | prev = n; |
85195f1a OF |
1056 | } |
1057 | ||
2e10a170 | 1058 | if (!added) |
85195f1a | 1059 | { |
2e10a170 | 1060 | add_tail(l, &en->cn); |
dfa9a53a OF |
1061 | } |
1062 | } | |
1063 | } | |
468f2347 | 1064 | |
b49e6f5a OZ |
1065 | |
1066 | static inline int | |
1067 | match_dr(struct ospf_iface *ifa, struct top_hash_entry *en) | |
1068 | { | |
1069 | #ifdef OSPFv2 | |
f9c799a0 | 1070 | return (ifa->drid == en->lsa.rt) && (ipa_to_u32(ifa->drip) == en->lsa.id); |
b49e6f5a OZ |
1071 | #else /* OSPFv3 */ |
1072 | return (ifa->drid == en->lsa.rt) && (ifa->dr_iface_id == en->lsa.id); | |
1073 | #endif | |
1074 | } | |
1075 | ||
b76aeb82 | 1076 | static int |
b49e6f5a OZ |
1077 | calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, |
1078 | struct top_hash_entry *par) | |
468f2347 | 1079 | { |
e81b440f | 1080 | // struct proto *p = &oa->po->proto; |
c6c56264 | 1081 | struct ospf_neighbor *neigh; |
2e10a170 | 1082 | struct proto_ospf *po = oa->po; |
273fd2c1 | 1083 | struct ospf_iface *ifa; |
b49e6f5a | 1084 | |
c3226991 | 1085 | /* 16.1.1. The next hop calculation */ |
e9d3c3aa | 1086 | DBG(" Next hop called.\n"); |
2e10a170 | 1087 | if (ipa_equal(par->nh, IPA_NONE)) |
468f2347 | 1088 | { |
3aab39f5 OZ |
1089 | DBG(" Next hop calculating for id: %R rt: %R type: %u\n", |
1090 | en->lsa.id, en->lsa.rt, en->lsa.type); | |
972fdb45 | 1091 | |
b76aeb82 OZ |
1092 | /* |
1093 | * There are three cases: | |
1094 | * 1) en is a local network (and par is root) | |
1095 | * 2) en is a ptp or ptmp neighbor (and par is root) | |
1096 | * 3) en is a bcast or nbma neighbor (and par is local network) | |
1097 | */ | |
1098 | ||
1099 | /* The first case - local network */ | |
1100 | if ((en->lsa.type == LSA_T_NET) && (par == oa->rt)) | |
273fd2c1 | 1101 | { |
b76aeb82 OZ |
1102 | WALK_LIST(ifa, po->iface_list) |
1103 | if (match_dr(ifa, en)) | |
2e10a170 | 1104 | { |
b76aeb82 OZ |
1105 | en->nh = IPA_NONE; |
1106 | en->nhi = ifa; | |
1107 | return 1; | |
2e10a170 | 1108 | } |
b76aeb82 | 1109 | return 0; |
972fdb45 | 1110 | } |
c3226991 | 1111 | |
b76aeb82 OZ |
1112 | /* |
1113 | * Remaining cases - local neighbours. | |
1114 | * There are two problems with this code: | |
1115 | * 1) we use IP address from HELLO packet | |
1116 | * and not the one from LSA (router or link). | |
1117 | * This may break NBMA networks | |
1118 | * 2) we use find_neigh_noifa() and does not | |
1119 | * take into account associated iface. | |
1120 | * This breaks neighbors connected by more links. | |
1121 | */ | |
1122 | ||
1123 | if ((en->lsa.type == LSA_T_RT) && | |
1124 | ((par == oa->rt) || (par->lsa.type == LSA_T_NET))) | |
972fdb45 | 1125 | { |
b76aeb82 OZ |
1126 | if ((neigh = find_neigh_noifa(po, en->lsa.rt)) != NULL) |
1127 | { | |
1128 | en->nh = neigh->ip; | |
1129 | en->nhi = neigh->ifa; | |
1130 | return 1; | |
1131 | } | |
1132 | return 0; | |
273fd2c1 | 1133 | } |
b76aeb82 OZ |
1134 | |
1135 | /* Probably bug or some race condition, we log it */ | |
1136 | log(L_ERR "Unexpected case in next hop calculation"); | |
1137 | ||
1138 | return 0; | |
a92847e7 | 1139 | } |
b76aeb82 | 1140 | |
b49e6f5a | 1141 | en->nh = par->nh; |
b76aeb82 OZ |
1142 | en->nhi = par->nhi; |
1143 | return 1; | |
a92847e7 | 1144 | } |
1a61882d OF |
1145 | |
1146 | static void | |
1147 | rt_sync(struct proto_ospf *po) | |
1148 | { | |
1149 | struct proto *p = &po->proto; | |
1150 | struct fib_iterator fit; | |
98ac6176 | 1151 | struct fib *fib = &po->rtf; |
1a61882d | 1152 | ort *nf; |
3b16080c | 1153 | struct ospf_area *oa, *oaa; |
98ac6176 | 1154 | struct area_net *anet; |
3b16080c | 1155 | int flush; |
98ac6176 | 1156 | |
f7574707 OZ |
1157 | /* This is used for forced reload of routes */ |
1158 | int reload = (po->calcrt == 2); | |
1159 | ||
98ac6176 | 1160 | OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation"); |
1a61882d OF |
1161 | |
1162 | DBG("Now syncing my rt table with nest's\n"); | |
1163 | FIB_ITERATE_INIT(&fit, fib); | |
98ac6176 | 1164 | again1: |
1a61882d OF |
1165 | FIB_ITERATE_START(fib, &fit, nftmp) |
1166 | { | |
1167 | nf = (ort *) nftmp; | |
5d3f5552 | 1168 | check_sum_lsa(po, nf, ORT_NET); |
f7574707 | 1169 | if (reload || memcmp(&nf->n, &nf->o, sizeof(orta))) |
1a61882d OF |
1170 | { /* Some difference */ |
1171 | net *ne; | |
1172 | rta a0; | |
1173 | rte *e; | |
1174 | ||
1175 | bzero(&a0, sizeof(a0)); | |
1176 | ||
1177 | a0.proto = p; | |
1178 | a0.source = nf->n.type; | |
1179 | a0.scope = SCOPE_UNIVERSE; | |
1180 | a0.cast = RTC_UNICAST; | |
1181 | a0.dest = RTD_ROUTER; | |
1182 | a0.flags = 0; | |
1183 | a0.aflags = 0; | |
5d3f5552 OF |
1184 | a0.iface = NULL; |
1185 | if (nf->n.ifa) a0.iface = nf->n.ifa->iface; | |
1a61882d | 1186 | a0.gw = nf->n.nh; |
89ba9a18 | 1187 | |
be862406 | 1188 | if (ipa_nonzero(nf->n.nh) && (!neigh_find2(p, &nf->n.nh, nf->n.ifa->iface, 0))) |
3b16080c OF |
1189 | { |
1190 | int found = 0; | |
1191 | struct ospf_iface *ifa; | |
1192 | struct top_hash_entry *en; | |
061ab802 | 1193 | OSPF_TRACE(D_EVENTS, "Trying to find correct next hop %I/%d via %I", nf->fn.prefix, nf->fn.pxlen, nf->n.nh); |
3b16080c OF |
1194 | WALK_LIST(ifa, po->iface_list) |
1195 | { | |
1196 | if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh)) | |
1197 | { | |
9f0ba7b1 OZ |
1198 | if ((en = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->vid)) |
1199 | && (!ipa_equal(en->nh, IPA_NONE))) | |
3b16080c OF |
1200 | { |
1201 | a0.gw = en->nh; | |
1202 | found = 1; | |
1203 | } | |
1204 | break; | |
1205 | } | |
1206 | } | |
1207 | if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */ | |
1208 | } | |
27a1e3ac | 1209 | |
7de7470a OF |
1210 | if (ipa_equal(nf->n.nh, IPA_NONE)) a0.dest = RTD_DEVICE; |
1211 | ||
27a1e3ac OF |
1212 | if (!a0.iface) /* Still no match? Can this really happen? */ |
1213 | nf->n.metric1 = LSINFINITY; | |
1214 | ||
1a61882d | 1215 | ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); |
98ac6176 OF |
1216 | if (nf->n.metric1 < LSINFINITY) |
1217 | { | |
1218 | e = rte_get_temp(&a0); | |
1219 | e->u.ospf.metric1 = nf->n.metric1; | |
1220 | e->u.ospf.metric2 = nf->n.metric2; | |
1221 | e->u.ospf.tag = nf->n.tag; | |
c27b2449 | 1222 | e->u.ospf.router_id = nf->n.rid; |
98ac6176 OF |
1223 | e->pflags = 0; |
1224 | e->net = ne; | |
1225 | e->pref = p->preference; | |
27a1e3ac OF |
1226 | DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n", |
1227 | a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1); | |
f98e2915 | 1228 | rte_update(p->table, ne, p, p, e); |
98ac6176 OF |
1229 | } |
1230 | else | |
1231 | { | |
f98e2915 | 1232 | rte_update(p->table, ne, p, p, NULL); |
98ac6176 OF |
1233 | FIB_ITERATE_PUT(&fit, nftmp); |
1234 | fib_delete(fib, nftmp); | |
1235 | goto again1; | |
1236 | } | |
1a61882d OF |
1237 | } |
1238 | } | |
1239 | FIB_ITERATE_END(nftmp); | |
98ac6176 OF |
1240 | |
1241 | WALK_LIST(oa, po->area_list) | |
1242 | { | |
1243 | FIB_ITERATE_INIT(&fit, &oa->rtr); | |
1244 | again2: | |
1245 | FIB_ITERATE_START(&oa->rtr, &fit, nftmp) | |
1246 | { | |
1247 | nf = (ort *) nftmp; | |
1248 | if (memcmp(&nf->n, &nf->o, sizeof(orta))) | |
1249 | { /* Some difference */ | |
1250 | check_sum_lsa(po, nf, ORT_ROUTER); | |
a2d5b405 | 1251 | if (nf->n.metric1 >= LSINFINITY) |
98ac6176 OF |
1252 | { |
1253 | FIB_ITERATE_PUT(&fit, nftmp); | |
1254 | fib_delete(&oa->rtr, nftmp); | |
1255 | goto again2; | |
1256 | } | |
1257 | } | |
1258 | } | |
1259 | FIB_ITERATE_END(nftmp); | |
1260 | ||
1261 | /* Check condensed summary LSAs */ | |
1262 | FIB_WALK(&oa->net_fib, nftmp) | |
1263 | { | |
3b16080c | 1264 | flush = 1; |
98ac6176 | 1265 | anet = (struct area_net *) nftmp; |
a2d5b405 | 1266 | if ((!anet->hidden) && anet->active) |
3b16080c OF |
1267 | flush = 0; |
1268 | ||
1269 | WALK_LIST(oaa, po->area_list) | |
1270 | { | |
5d3f5552 OF |
1271 | int fl = flush; |
1272 | ||
3b16080c | 1273 | if (oaa == oa) continue; |
5d3f5552 OF |
1274 | |
1275 | if ((oa == po->backbone) && oaa->trcap) fl = 1; | |
1276 | ||
dafaef9b OF |
1277 | if (oaa->stub) fl = 1; |
1278 | ||
a2d5b405 | 1279 | if (fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET); |
c3226991 | 1280 | else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric, 0); |
3b16080c | 1281 | } |
98ac6176 OF |
1282 | } |
1283 | FIB_WALK_END; | |
dafaef9b OF |
1284 | |
1285 | /* Check default summary LSA for stub areas | |
1286 | * just for router connected to backbone */ | |
1287 | if (po->backbone) | |
1288 | { | |
1289 | struct fib_node fnn; | |
1290 | ||
1291 | fnn.prefix = IPA_NONE; | |
1292 | fnn.pxlen = 0; | |
c3226991 | 1293 | if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub, 0); |
dafaef9b OF |
1294 | else flush_sum_lsa(oa, &fnn, ORT_NET); |
1295 | } | |
98ac6176 | 1296 | } |
1a61882d | 1297 | } |