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