1 /* $OpenBSD: rde_spf.c,v 1.29 2023/03/08 04:43:14 guenther Exp $ */
2
3 /*
4 * Copyright (c) 2005 Esben Norby <norby@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #include <sys/types.h>
20 #include <sys/socket.h>
21 #include <netinet/in.h>
22 #include <arpa/inet.h>
23 #include <err.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "ospf6d.h"
28 #include "ospf6.h"
29 #include "log.h"
30 #include "rde.h"
31
32 extern struct ospfd_conf *rdeconf;
33 TAILQ_HEAD(, vertex) cand_list;
34 RB_HEAD(rt_tree, rt_node) rt;
35 RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
36 RB_GENERATE(rt_tree, rt_node, entry, rt_compare)
37 struct vertex *spf_root = NULL;
38
39 struct in6_addr *calc_nexthop_lladdr(struct vertex *, struct lsa_rtr_link *,
40 unsigned int);
41 void calc_nexthop_transit_nbr(struct vertex *, struct vertex *,
42 unsigned int);
43 void calc_nexthop(struct vertex *, struct vertex *,
44 struct area *, struct lsa_rtr_link *);
45 void rt_nexthop_clear(struct rt_node *);
46 void rt_nexthop_add(struct rt_node *, struct v_nexthead *,
47 u_int16_t, struct in_addr);
48 void rt_update(struct in6_addr *, u_int8_t, struct v_nexthead *,
49 u_int16_t, u_int32_t, u_int32_t, struct in_addr,
50 struct in_addr, enum path_type, enum dst_type, u_int8_t,
51 u_int32_t);
52 struct rt_node *rt_lookup(enum dst_type, struct in6_addr *);
53 void rt_invalidate(struct area *);
54 int linked(struct vertex *, struct vertex *);
55
56 void
spf_calc(struct area * area)57 spf_calc(struct area *area)
58 {
59 struct vertex *v, *w;
60 struct lsa_rtr_link *rtr_link = NULL;
61 struct lsa_net_link *net_link;
62 u_int32_t d;
63 unsigned int i;
64
65 /* clear SPF tree */
66 spf_tree_clr(area);
67 cand_list_clr();
68
69 /* initialize SPF tree */
70 if ((v = spf_root = lsa_find_rtr(area, rde_router_id())) == NULL)
71 /* empty area because no interface is active */
72 return;
73
74 area->transit = 0;
75 spf_root->cost = 0;
76 w = NULL;
77
78 /* calculate SPF tree */
79 do {
80 /* loop links */
81 for (i = 0; i < lsa_num_links(v); i++) {
82 switch (v->type) {
83 case LSA_TYPE_ROUTER:
84 rtr_link = get_rtr_link(v, i);
85 switch (rtr_link->type) {
86 case LINK_TYPE_POINTTOPOINT:
87 case LINK_TYPE_VIRTUAL:
88 /* find router LSA */
89 w = lsa_find_rtr(area,
90 rtr_link->nbr_rtr_id);
91 break;
92 case LINK_TYPE_TRANSIT_NET:
93 /* find network LSA */
94 w = lsa_find_tree(&area->lsa_tree,
95 htons(LSA_TYPE_NETWORK),
96 rtr_link->nbr_iface_id,
97 rtr_link->nbr_rtr_id);
98 break;
99 default:
100 fatalx("spf_calc: invalid link type");
101 }
102 break;
103 case LSA_TYPE_NETWORK:
104 net_link = get_net_link(v, i);
105 /* find router LSA */
106 w = lsa_find_rtr(area, net_link->att_rtr);
107 break;
108 default:
109 fatalx("spf_calc: invalid LSA type");
110 }
111
112 if (w == NULL)
113 continue;
114
115 if (ntohs(w->lsa->hdr.age) == MAX_AGE)
116 continue;
117
118 if (lsa_num_links(w) == 0)
119 continue;
120
121 if (!linked(w, v)) {
122 log_debug("spf_calc: w adv_rtr %s ls_id %s "
123 "type 0x%x numlinks %hu has no link to "
124 "v adv_rtr %s ls_id %s type 0x%x",
125 log_rtr_id(htonl(w->adv_rtr)),
126 log_rtr_id(htonl(w->ls_id)), w->type,
127 lsa_num_links(w),
128 log_rtr_id(htonl(v->adv_rtr)),
129 log_rtr_id(htonl(v->ls_id)), v->type);
130 continue;
131 }
132
133 if (v->type == LSA_TYPE_ROUTER)
134 d = v->cost + ntohs(rtr_link->metric);
135 else
136 d = v->cost;
137
138 if (cand_list_present(w)) {
139 if (d > w->cost)
140 continue;
141 if (d < w->cost) {
142 w->cost = d;
143 vertex_nexthop_clear(w);
144 calc_nexthop(w, v, area, rtr_link);
145 /*
146 * need to readd to candidate list
147 * because the list is sorted
148 */
149 TAILQ_REMOVE(&cand_list, w, cand);
150 cand_list_add(w);
151 } else
152 /* equal cost path */
153 calc_nexthop(w, v, area, rtr_link);
154 } else if (w->cost == LS_INFINITY && d < LS_INFINITY) {
155 w->cost = d;
156
157 vertex_nexthop_clear(w);
158 calc_nexthop(w, v, area, rtr_link);
159 cand_list_add(w);
160 }
161 }
162
163 /* get next vertex */
164 v = cand_list_pop();
165 w = NULL;
166 } while (v != NULL);
167
168 /* spf_dump(area); */
169 log_debug("spf_calc: area %s calculated", inet_ntoa(area->id));
170
171 /* Dump SPF tree to log */
172 RB_FOREACH(v, lsa_tree, &area->lsa_tree) {
173 struct v_nexthop *vn;
174 char hops[4096];
175 struct iface *iface;
176
177 bzero(hops, sizeof(hops));
178
179 if (v->type != LSA_TYPE_ROUTER && v->type != LSA_TYPE_NETWORK)
180 continue;
181
182 TAILQ_FOREACH(vn, &v->nexthop, entry) {
183 strlcat(hops, log_in6addr(&vn->nexthop), sizeof(hops));
184 strlcat(hops, "%", sizeof(hops));
185 if ((iface = if_find(vn->ifindex)) == NULL)
186 fatalx("spf_calc: lost iface");
187 strlcat(hops, iface->name, sizeof(hops));
188 if (vn != TAILQ_LAST(&v->nexthop, v_nexthead))
189 strlcat(hops, ", ", sizeof(hops));
190 }
191 log_debug("%s(%s, 0x%x, %s) cost %u has nexthops [%s]",
192 v == spf_root ? "*" : " ", log_rtr_id(htonl(v->adv_rtr)),
193 v->type, log_rtr_id(htonl(v->ls_id)), v->cost, hops);
194 }
195
196 area->num_spf_calc++;
197 start_spf_timer();
198 }
199
200 void
rt_calc(struct vertex * v,struct area * area,struct ospfd_conf * conf)201 rt_calc(struct vertex *v, struct area *area, struct ospfd_conf *conf)
202 {
203 struct vertex *w;
204 struct lsa_intra_prefix *iap;
205 struct lsa_prefix *prefix;
206 struct in_addr adv_rtr;
207 struct in6_addr ia6;
208 u_int16_t i, off;
209 u_int8_t flags;
210
211 lsa_age(v);
212 if (ntohs(v->lsa->hdr.age) == MAX_AGE)
213 return;
214
215 switch (v->type) {
216 case LSA_TYPE_ROUTER:
217 if (v->cost >= LS_INFINITY || TAILQ_EMPTY(&v->nexthop))
218 return;
219
220 /* router, only add border and as-external routers */
221 flags = LSA_24_GETHI(ntohl(v->lsa->data.rtr.opts));
222 if ((flags & (OSPF_RTR_B | OSPF_RTR_E)) == 0)
223 return;
224
225 bzero(&ia6, sizeof(ia6));
226 adv_rtr.s_addr = htonl(v->adv_rtr);
227 bcopy(&adv_rtr, &ia6.s6_addr[12], sizeof(adv_rtr));
228
229 rt_update(&ia6, 128, &v->nexthop, v->type, v->cost, 0, area->id,
230 adv_rtr, PT_INTER_AREA, DT_RTR, flags, 0);
231 break;
232 case LSA_TYPE_INTRA_A_PREFIX:
233 /* Find referenced LSA */
234 iap = &v->lsa->data.pref_intra;
235 switch (ntohs(iap->ref_type)) {
236 case LSA_TYPE_ROUTER:
237 w = lsa_find_rtr(area, iap->ref_adv_rtr);
238 if (w == NULL) {
239 warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) "
240 "references non-existent router %s",
241 log_rtr_id(htonl(v->adv_rtr)),
242 v->ls_id, log_rtr_id(iap->ref_adv_rtr));
243 return;
244 }
245 flags = LSA_24_GETHI(ntohl(w->lsa->data.rtr.opts));
246 break;
247 case LSA_TYPE_NETWORK:
248 w = lsa_find_tree(&area->lsa_tree, iap->ref_type,
249 iap->ref_ls_id, iap->ref_adv_rtr);
250 if (w == NULL) {
251 warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) "
252 "references non-existent Network LSA (%s, "
253 "%u)", log_rtr_id(htonl(v->adv_rtr)),
254 v->ls_id, log_rtr_id(iap->ref_adv_rtr),
255 ntohl(iap->ref_ls_id));
256 return;
257 }
258 flags = 0;
259 break;
260 default:
261 warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) has "
262 "invalid ref_type 0x%hx", log_rtr_id(v->adv_rtr),
263 v->ls_id, ntohs(iap->ref_type));
264 return;
265 }
266
267 if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop))
268 return;
269
270 /* Add prefixes listed in Intra-Area-Prefix LSA to routing
271 * table, using w as destination. */
272 off = sizeof(v->lsa->hdr) + sizeof(struct lsa_intra_prefix);
273 for (i = 0; i < ntohs(v->lsa->data.pref_intra.numprefix); i++) {
274 prefix = (struct lsa_prefix *)((char *)(v->lsa) + off);
275 if (!(prefix->options & OSPF_PREFIX_NU)) {
276 bzero(&ia6, sizeof(ia6));
277 bcopy(prefix + 1, &ia6,
278 LSA_PREFIXSIZE(prefix->prefixlen));
279
280 adv_rtr.s_addr = htonl(w->adv_rtr);
281
282 rt_update(&ia6, prefix->prefixlen, &w->nexthop,
283 v->type, w->cost + ntohs(prefix->metric), 0,
284 area->id, adv_rtr, PT_INTRA_AREA, DT_NET,
285 flags, 0);
286 }
287 off += sizeof(struct lsa_prefix)
288 + LSA_PREFIXSIZE(prefix->prefixlen);
289 }
290 break;
291 case LSA_TYPE_INTER_A_PREFIX:
292 /* XXX if ABR only look at area 0.0.0.0 LSA */
293 /* ignore self-originated stuff */
294 if (v->self)
295 return;
296
297 adv_rtr.s_addr = htonl(v->adv_rtr);
298 w = lsa_find_rtr(area, adv_rtr.s_addr);
299 if (w == NULL) {
300 warnx("rt_calc: Inter-Area-Router LSA (%s, %u) "
301 "originated from non-existent router",
302 log_rtr_id(htonl(v->adv_rtr)),
303 v->ls_id);
304 return;
305 }
306 if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop))
307 return;
308
309 /* Add prefix listed in Inter-Area-Prefix LSA to routing
310 * table, using w as destination. */
311 off = sizeof(v->lsa->hdr) + sizeof(struct lsa_prefix_sum);
312 prefix = (struct lsa_prefix *)((char *)(v->lsa) + off);
313 if (prefix->options & OSPF_PREFIX_NU)
314 return;
315
316 bzero(&ia6, sizeof(ia6));
317 bcopy(prefix + 1, &ia6, LSA_PREFIXSIZE(prefix->prefixlen));
318
319 rt_update(&ia6, prefix->prefixlen, &w->nexthop, v->type,
320 w->cost + (ntohs(v->lsa->data.rtr_sum.metric) &
321 LSA_METRIC_MASK), 0, area->id, adv_rtr, PT_INTER_AREA,
322 DT_NET, 0, 0);
323 break;
324 case LSA_TYPE_INTER_A_ROUTER:
325 /* XXX if ABR only look at area 0.0.0.0 LSA */
326 /* ignore self-originated stuff */
327 if (v->self)
328 return;
329
330 adv_rtr.s_addr = htonl(v->adv_rtr);
331 w = lsa_find_rtr(area, adv_rtr.s_addr);
332 if (w == NULL) {
333 warnx("rt_calc: Inter-Area-Router LSA (%s, %u) "
334 "originated from non-existent router",
335 log_rtr_id(htonl(v->adv_rtr)),
336 v->ls_id);
337 return;
338 }
339 if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop))
340 return;
341
342 /* Add router listed in Inter-Area-Router LSA to routing
343 * table, using w as destination. */
344 bzero(&ia6, sizeof(ia6));
345 bcopy(&v->lsa->data.rtr_sum.dest_rtr_id, &ia6.s6_addr[12],
346 4);
347
348 rt_update(&ia6, 128, &w->nexthop, v->type, w->cost +
349 (ntohs(v->lsa->data.rtr_sum.metric) & LSA_METRIC_MASK), 0,
350 area->id, adv_rtr, PT_INTER_AREA, DT_RTR, 0, 0);
351 break;
352 default:
353 break;
354 }
355 }
356
357 void
asext_calc(struct vertex * v)358 asext_calc(struct vertex *v)
359 {
360 struct in6_addr addr, fw_addr;
361 struct rt_node *r;
362 struct rt_nexthop *rn;
363 struct lsa_prefix *prefix;
364 struct in_addr adv_rtr, area;
365 char *p;
366 u_int32_t metric, cost2, ext_tag = 0;
367 enum path_type type;
368
369 lsa_age(v);
370 if (ntohs(v->lsa->hdr.age) == MAX_AGE ||
371 (ntohl(v->lsa->data.asext.metric) & LSA_METRIC_MASK) >=
372 LS_INFINITY)
373 return;
374
375 switch (v->type) {
376 case LSA_TYPE_EXTERNAL:
377 /* ignore self-originated stuff */
378 if (v->self)
379 return;
380
381 adv_rtr.s_addr = htonl(v->adv_rtr);
382 bzero(&addr, sizeof(addr));
383 bcopy(&adv_rtr, &addr.s6_addr[12], sizeof(adv_rtr));
384 if ((r = rt_lookup(DT_RTR, &addr)) == NULL)
385 return;
386
387 prefix = &v->lsa->data.asext.prefix;
388 if (prefix->options & OSPF_PREFIX_NU)
389 break;
390 bzero(&addr, sizeof(addr));
391 bcopy(prefix + 1, &addr,
392 LSA_PREFIXSIZE(prefix->prefixlen));
393
394 p = (char *)(prefix + 1) + LSA_PREFIXSIZE(prefix->prefixlen);
395 metric = ntohl(v->lsa->data.asext.metric);
396
397 if (metric & LSA_ASEXT_F_FLAG) {
398 bcopy(p, &fw_addr, sizeof(fw_addr));
399 p += sizeof(fw_addr);
400
401 /* lookup forwarding address */
402 if ((r = rt_lookup(DT_NET, &fw_addr)) == NULL ||
403 (r->p_type != PT_INTRA_AREA &&
404 r->p_type != PT_INTER_AREA))
405 return;
406 }
407 if (metric & LSA_ASEXT_T_FLAG) {
408 bcopy(p, &ext_tag, sizeof(ext_tag));
409 p += sizeof(ext_tag);
410 }
411 if (metric & LSA_ASEXT_E_FLAG) {
412 v->cost = r->cost;
413 cost2 = metric & LSA_METRIC_MASK;
414 type = PT_TYPE2_EXT;
415 } else {
416 v->cost = r->cost + (metric & LSA_METRIC_MASK);
417 cost2 = 0;
418 type = PT_TYPE1_EXT;
419 }
420
421 area.s_addr = 0;
422 vertex_nexthop_clear(v);
423 TAILQ_FOREACH(rn, &r->nexthop, entry) {
424 if (rn->invalid)
425 continue;
426
427 if (rn->connected && r->d_type == DT_NET) {
428 if (metric & LSA_ASEXT_F_FLAG)
429 vertex_nexthop_add(v, NULL, &fw_addr,
430 rn->ifindex);
431 else
432 fatalx("asext_calc: I'm sorry Dave, "
433 "I'm afraid I can't do that.");
434 } else
435 vertex_nexthop_add(v, NULL, &rn->nexthop,
436 rn->ifindex);
437 }
438
439 rt_update(&addr, prefix->prefixlen, &v->nexthop, v->type,
440 v->cost, cost2, area, adv_rtr, type, DT_NET, 0, ext_tag);
441 break;
442 default:
443 fatalx("asext_calc: invalid LSA type");
444 }
445 }
446
447 void
spf_tree_clr(struct area * area)448 spf_tree_clr(struct area *area)
449 {
450 struct lsa_tree *tree = &area->lsa_tree;
451 struct vertex *v;
452
453 RB_FOREACH(v, lsa_tree, tree) {
454 v->cost = LS_INFINITY;
455 vertex_nexthop_clear(v);
456 }
457 }
458
459 struct in6_addr *
calc_nexthop_lladdr(struct vertex * dst,struct lsa_rtr_link * rtr_link,unsigned int ifindex)460 calc_nexthop_lladdr(struct vertex *dst, struct lsa_rtr_link *rtr_link,
461 unsigned int ifindex)
462 {
463 struct iface *iface;
464 struct vertex *link;
465 struct rde_nbr *nbr;
466
467 /* Find outgoing interface, we need its LSA tree */
468 LIST_FOREACH(iface, &dst->area->iface_list, entry) {
469 if (ifindex == iface->ifindex)
470 break;
471 }
472 if (!iface) {
473 log_warnx("calc_nexthop_lladdr: no interface found for "
474 "ifindex %d", ntohl(rtr_link->iface_id));
475 return (NULL);
476 }
477
478 /* Determine neighbor's link-local address.
479 * Try to get it from link LSA first. */
480 link = lsa_find_tree(&iface->lsa_tree,
481 htons(LSA_TYPE_LINK), rtr_link->iface_id,
482 htonl(dst->adv_rtr));
483 if (link)
484 return &link->lsa->data.link.lladdr;
485
486 /* Not found, so fall back to source address
487 * advertised in hello packet. */
488 if ((nbr = rde_nbr_find(dst->peerid)) == NULL)
489 fatalx("next hop is not a neighbor");
490 return &nbr->addr;
491 }
492
493 void
calc_nexthop_transit_nbr(struct vertex * dst,struct vertex * parent,unsigned int ifindex)494 calc_nexthop_transit_nbr(struct vertex *dst, struct vertex *parent,
495 unsigned int ifindex)
496 {
497 struct lsa_rtr_link *rtr_link;
498 unsigned int i;
499 struct in6_addr *lladdr;
500
501 if (dst->type != LSA_TYPE_ROUTER)
502 fatalx("calc_nexthop_transit_nbr: dst is not a router");
503 if (parent->type != LSA_TYPE_NETWORK)
504 fatalx("calc_nexthop_transit_nbr: parent is not a network");
505
506 /* dst is a neighbor on a directly attached transit network.
507 * Figure out dst's link local address and add it as nexthop. */
508 for (i = 0; i < lsa_num_links(dst); i++) {
509 rtr_link = get_rtr_link(dst, i);
510 if (rtr_link->type == LINK_TYPE_TRANSIT_NET &&
511 rtr_link->nbr_rtr_id == parent->lsa->hdr.adv_rtr &&
512 rtr_link->nbr_iface_id == parent->lsa->hdr.ls_id) {
513 lladdr = calc_nexthop_lladdr(dst, rtr_link, ifindex);
514 vertex_nexthop_add(dst, parent, lladdr, ifindex);
515 }
516 }
517 }
518
519 void
calc_nexthop(struct vertex * dst,struct vertex * parent,struct area * area,struct lsa_rtr_link * rtr_link)520 calc_nexthop(struct vertex *dst, struct vertex *parent,
521 struct area *area, struct lsa_rtr_link *rtr_link)
522 {
523 struct v_nexthop *vn;
524 struct in6_addr *nexthop;
525
526 /* case 1 */
527 if (parent == spf_root) {
528 switch (dst->type) {
529 case LSA_TYPE_ROUTER:
530 if (rtr_link->type != LINK_TYPE_POINTTOPOINT)
531 fatalx("inconsistent SPF tree");
532 nexthop = calc_nexthop_lladdr(dst, rtr_link,
533 ntohl(rtr_link->iface_id));
534 break;
535 case LSA_TYPE_NETWORK:
536 if (rtr_link->type != LINK_TYPE_TRANSIT_NET)
537 fatalx("inconsistent SPF tree");
538
539 /* Next hop address cannot be determined yet,
540 * we only know the outgoing interface. */
541 nexthop = NULL;
542 break;
543 default:
544 fatalx("calc_nexthop: invalid dst type");
545 }
546
547 vertex_nexthop_add(dst, parent, nexthop,
548 ntohl(rtr_link->iface_id));
549 return;
550 }
551
552 /* case 2 */
553 if (parent->type == LSA_TYPE_NETWORK && dst->type == LSA_TYPE_ROUTER) {
554 TAILQ_FOREACH(vn, &parent->nexthop, entry) {
555 if (vn->prev == spf_root)
556 calc_nexthop_transit_nbr(dst, parent,
557 vn->ifindex);
558 else
559 /* dst is more than one transit net away */
560 vertex_nexthop_add(dst, parent, &vn->nexthop,
561 vn->ifindex);
562 }
563 return;
564 }
565
566 /* case 3 */
567 TAILQ_FOREACH(vn, &parent->nexthop, entry)
568 vertex_nexthop_add(dst, parent, &vn->nexthop, vn->ifindex);
569 }
570
571 /* candidate list */
572 void
cand_list_init(void)573 cand_list_init(void)
574 {
575 TAILQ_INIT(&cand_list);
576 }
577
578 void
cand_list_add(struct vertex * v)579 cand_list_add(struct vertex *v)
580 {
581 struct vertex *c = NULL;
582
583 TAILQ_FOREACH(c, &cand_list, cand) {
584 if (c->cost > v->cost) {
585 TAILQ_INSERT_BEFORE(c, v, cand);
586 return;
587 } else if (c->cost == v->cost && c->type == LSA_TYPE_ROUTER &&
588 v->type == LSA_TYPE_NETWORK) {
589 TAILQ_INSERT_BEFORE(c, v, cand);
590 return;
591 }
592 }
593 TAILQ_INSERT_TAIL(&cand_list, v, cand);
594 }
595
596 struct vertex *
cand_list_pop(void)597 cand_list_pop(void)
598 {
599 struct vertex *c;
600
601 if ((c = TAILQ_FIRST(&cand_list)) != NULL) {
602 TAILQ_REMOVE(&cand_list, c, cand);
603 }
604
605 return (c);
606 }
607
608 int
cand_list_present(struct vertex * v)609 cand_list_present(struct vertex *v)
610 {
611 struct vertex *c;
612
613 TAILQ_FOREACH(c, &cand_list, cand) {
614 if (c == v)
615 return (1);
616 }
617
618 return (0);
619 }
620
621 void
cand_list_clr(void)622 cand_list_clr(void)
623 {
624 struct vertex *c;
625
626 while ((c = TAILQ_FIRST(&cand_list)) != NULL) {
627 TAILQ_REMOVE(&cand_list, c, cand);
628 }
629 }
630
631 /* timers */
632 void
spf_timer(int fd,short event,void * arg)633 spf_timer(int fd, short event, void *arg)
634 {
635 struct vertex *v;
636 struct ospfd_conf *conf = arg;
637 struct area *area;
638 struct rt_node *r;
639
640 switch (conf->spf_state) {
641 case SPF_IDLE:
642 fatalx("spf_timer: invalid state IDLE");
643 case SPF_HOLDQUEUE:
644 conf->spf_state = SPF_DELAY;
645 /* FALLTHROUGH */
646 case SPF_DELAY:
647 LIST_FOREACH(area, &conf->area_list, entry) {
648 if (area->dirty) {
649 /* invalidate RIB entries of this area */
650 rt_invalidate(area);
651
652 /* calculate SPF tree */
653 spf_calc(area);
654
655 /* calculate route table */
656 RB_FOREACH(v, lsa_tree, &area->lsa_tree) {
657 rt_calc(v, area, conf);
658 }
659
660 area->dirty = 0;
661 }
662 }
663
664 /* calculate as-external routes, first invalidate them */
665 rt_invalidate(NULL);
666 RB_FOREACH(v, lsa_tree, &asext_tree) {
667 asext_calc(v);
668 }
669
670 RB_FOREACH(r, rt_tree, &rt) {
671 LIST_FOREACH(area, &conf->area_list, entry)
672 rde_summary_update(r, area);
673
674 if (r->d_type != DT_NET)
675 continue;
676
677 if (r->invalid)
678 rde_send_delete_kroute(r);
679 else
680 rde_send_change_kroute(r);
681 }
682
683 LIST_FOREACH(area, &conf->area_list, entry)
684 lsa_remove_invalid_sums(area);
685
686 start_spf_holdtimer(conf);
687 break;
688 case SPF_HOLD:
689 conf->spf_state = SPF_IDLE;
690 break;
691 default:
692 fatalx("spf_timer: unknown state");
693 }
694 }
695
696 void
start_spf_timer(void)697 start_spf_timer(void)
698 {
699 struct timeval tv;
700
701 switch (rdeconf->spf_state) {
702 case SPF_IDLE:
703 timerclear(&tv);
704 tv.tv_sec = rdeconf->spf_delay;
705 rdeconf->spf_state = SPF_DELAY;
706 if (evtimer_add(&rdeconf->ev, &tv) == -1)
707 fatal("start_spf_timer");
708 break;
709 case SPF_DELAY:
710 /* ignore */
711 break;
712 case SPF_HOLD:
713 rdeconf->spf_state = SPF_HOLDQUEUE;
714 break;
715 case SPF_HOLDQUEUE:
716 /* ignore */
717 break;
718 default:
719 fatalx("start_spf_timer: invalid spf_state");
720 }
721 }
722
723 void
stop_spf_timer(struct ospfd_conf * conf)724 stop_spf_timer(struct ospfd_conf *conf)
725 {
726 if (evtimer_del(&conf->ev) == -1)
727 fatal("stop_spf_timer");
728 }
729
730 void
start_spf_holdtimer(struct ospfd_conf * conf)731 start_spf_holdtimer(struct ospfd_conf *conf)
732 {
733 struct timeval tv;
734
735 switch (conf->spf_state) {
736 case SPF_DELAY:
737 timerclear(&tv);
738 tv.tv_sec = conf->spf_hold_time;
739 conf->spf_state = SPF_HOLD;
740 if (evtimer_add(&conf->ev, &tv) == -1)
741 fatal("start_spf_holdtimer");
742 break;
743 case SPF_IDLE:
744 case SPF_HOLD:
745 case SPF_HOLDQUEUE:
746 fatalx("start_spf_holdtimer: invalid state");
747 default:
748 fatalx("start_spf_holdtimer: unknown state");
749 }
750 }
751
752 /* route table */
753 void
rt_init(void)754 rt_init(void)
755 {
756 RB_INIT(&rt);
757 }
758
759 int
rt_compare(struct rt_node * a,struct rt_node * b)760 rt_compare(struct rt_node *a, struct rt_node *b)
761 {
762 int i;
763
764 /* XXX maybe a & b need to be switched */
765 i = memcmp(&a->prefix, &b->prefix, sizeof(a->prefix));
766 if (i)
767 return (i);
768 if (a->prefixlen < b->prefixlen)
769 return (-1);
770 if (a->prefixlen > b->prefixlen)
771 return (1);
772 if (a->d_type > b->d_type)
773 return (-1);
774 if (a->d_type < b->d_type)
775 return (1);
776 return (0);
777 }
778
779 struct rt_node *
rt_find(struct in6_addr * prefix,u_int8_t prefixlen,enum dst_type d_type)780 rt_find(struct in6_addr *prefix, u_int8_t prefixlen, enum dst_type d_type)
781 {
782 struct rt_node s;
783
784 s.prefix = *prefix;
785 s.prefixlen = prefixlen;
786 s.d_type = d_type;
787
788 return (RB_FIND(rt_tree, &rt, &s));
789 }
790
791 int
rt_insert(struct rt_node * r)792 rt_insert(struct rt_node *r)
793 {
794 if (RB_INSERT(rt_tree, &rt, r) != NULL) {
795 log_warnx("rt_insert failed for %s/%u",
796 log_in6addr(&r->prefix), r->prefixlen);
797 free(r);
798 return (-1);
799 }
800
801 return (0);
802 }
803
804 int
rt_remove(struct rt_node * r)805 rt_remove(struct rt_node *r)
806 {
807 if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
808 log_warnx("rt_remove failed for %s/%u",
809 log_in6addr(&r->prefix), r->prefixlen);
810 return (-1);
811 }
812
813 rt_nexthop_clear(r);
814 free(r);
815 return (0);
816 }
817
818 void
rt_invalidate(struct area * area)819 rt_invalidate(struct area *area)
820 {
821 struct rt_node *r, *nr;
822 struct rt_nexthop *rn, *nrn;
823
824 for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) {
825 nr = RB_NEXT(rt_tree, &rt, r);
826 if (area == NULL) {
827 /* look only at as_ext routes */
828 if (r->p_type != PT_TYPE1_EXT &&
829 r->p_type != PT_TYPE2_EXT)
830 continue;
831 } else {
832 /* ignore all as_ext routes */
833 if (r->p_type == PT_TYPE1_EXT ||
834 r->p_type == PT_TYPE2_EXT)
835 continue;
836
837 /* look only at routes matching the area */
838 if (r->area.s_addr != area->id.s_addr)
839 continue;
840 }
841 r->invalid = 1;
842 for (rn = TAILQ_FIRST(&r->nexthop); rn != NULL; rn = nrn) {
843 nrn = TAILQ_NEXT(rn, entry);
844 if (rn->invalid) {
845 TAILQ_REMOVE(&r->nexthop, rn, entry);
846 free(rn);
847 } else
848 rn->invalid = 1;
849 }
850 if (TAILQ_EMPTY(&r->nexthop))
851 rt_remove(r);
852 }
853 }
854
855 void
rt_nexthop_clear(struct rt_node * r)856 rt_nexthop_clear(struct rt_node *r)
857 {
858 struct rt_nexthop *rn;
859
860 while ((rn = TAILQ_FIRST(&r->nexthop)) != NULL) {
861 TAILQ_REMOVE(&r->nexthop, rn, entry);
862 free(rn);
863 }
864 }
865
866 void
rt_nexthop_add(struct rt_node * r,struct v_nexthead * vnh,u_int16_t type,struct in_addr adv_rtr)867 rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh, u_int16_t type,
868 struct in_addr adv_rtr)
869 {
870 struct v_nexthop *vn;
871 struct rt_nexthop *rn;
872 struct timespec now;
873
874 TAILQ_FOREACH(vn, vnh, entry) {
875 TAILQ_FOREACH(rn, &r->nexthop, entry) {
876 if (!IN6_ARE_ADDR_EQUAL(&rn->nexthop, &vn->nexthop))
877 continue;
878
879 rn->adv_rtr.s_addr = adv_rtr.s_addr;
880 rn->connected = (type == LSA_TYPE_NETWORK &&
881 vn->prev == spf_root) ||
882 (IN6_IS_ADDR_UNSPECIFIED(&vn->nexthop));
883 rn->invalid = 0;
884
885 r->invalid = 0;
886 break;
887 }
888 if (rn)
889 continue;
890
891 if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL)
892 fatal("rt_nexthop_add");
893
894 clock_gettime(CLOCK_MONOTONIC, &now);
895 rn->nexthop = vn->nexthop;
896 rn->ifindex = vn->ifindex;
897 rn->adv_rtr.s_addr = adv_rtr.s_addr;
898 rn->uptime = now.tv_sec;
899 rn->connected = (type == LSA_TYPE_NETWORK &&
900 vn->prev == spf_root) ||
901 (IN6_IS_ADDR_UNSPECIFIED(&vn->nexthop));
902 rn->invalid = 0;
903
904 r->invalid = 0;
905 TAILQ_INSERT_TAIL(&r->nexthop, rn, entry);
906 }
907 }
908
909 void
rt_clear(void)910 rt_clear(void)
911 {
912 struct rt_node *r;
913
914 while ((r = RB_MIN(rt_tree, &rt)) != NULL)
915 rt_remove(r);
916 }
917
918 void
rt_dump(struct in_addr area,pid_t pid,u_int8_t r_type)919 rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type)
920 {
921 static struct ctl_rt rtctl;
922 struct timespec now;
923 struct rt_node *r;
924 struct rt_nexthop *rn;
925
926 clock_gettime(CLOCK_MONOTONIC, &now);
927
928 RB_FOREACH(r, rt_tree, &rt) {
929 if (r->invalid)
930 continue;
931
932 if (r->area.s_addr != area.s_addr)
933 continue;
934
935 switch (r_type) {
936 case RIB_RTR:
937 if (r->d_type != DT_RTR)
938 continue;
939 break;
940 case RIB_NET:
941 if (r->d_type != DT_NET)
942 continue;
943 if (r->p_type == PT_TYPE1_EXT ||
944 r->p_type == PT_TYPE2_EXT)
945 continue;
946 break;
947 case RIB_EXT:
948 if (r->p_type != PT_TYPE1_EXT &&
949 r->p_type != PT_TYPE2_EXT)
950 continue;
951 break;
952 default:
953 fatalx("rt_dump: invalid RIB type");
954 }
955
956 memset(&rtctl, 0, sizeof(rtctl));
957 rtctl.prefix = r->prefix;
958 rtctl.area.s_addr = r->area.s_addr;
959 rtctl.cost = r->cost;
960 rtctl.cost2 = r->cost2;
961 rtctl.p_type = r->p_type;
962 rtctl.d_type = r->d_type;
963 rtctl.flags = r->flags;
964 rtctl.prefixlen = r->prefixlen;
965
966 TAILQ_FOREACH(rn, &r->nexthop, entry) {
967 if (rn->invalid)
968 continue;
969
970 rtctl.connected = rn->connected;
971 rtctl.nexthop = rn->nexthop;
972 rtctl.ifindex = rn->ifindex;
973 rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr;
974 rtctl.uptime = now.tv_sec - rn->uptime;
975
976 rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid,
977 &rtctl, sizeof(rtctl));
978 }
979 }
980 }
981
982 void
rt_update(struct in6_addr * prefix,u_int8_t prefixlen,struct v_nexthead * vnh,u_int16_t v_type,u_int32_t cost,u_int32_t cost2,struct in_addr area,struct in_addr adv_rtr,enum path_type p_type,enum dst_type d_type,u_int8_t flags,u_int32_t tag)983 rt_update(struct in6_addr *prefix, u_int8_t prefixlen, struct v_nexthead *vnh,
984 u_int16_t v_type, u_int32_t cost, u_int32_t cost2, struct in_addr area,
985 struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type,
986 u_int8_t flags, u_int32_t tag)
987 {
988 struct rt_node *rte;
989 struct rt_nexthop *rn;
990 int better = 0, equal = 0;
991
992 if (vnh == NULL || TAILQ_EMPTY(vnh)) /* XXX remove */
993 fatalx("rt_update: invalid nexthop");
994
995 if ((rte = rt_find(prefix, prefixlen, d_type)) == NULL) {
996 if ((rte = calloc(1, sizeof(struct rt_node))) == NULL)
997 fatal("rt_update");
998
999 TAILQ_INIT(&rte->nexthop);
1000 rte->prefix = *prefix;
1001 rte->prefixlen = prefixlen;
1002 rte->cost = cost;
1003 rte->cost2 = cost2;
1004 rte->area = area;
1005 rte->p_type = p_type;
1006 rte->d_type = d_type;
1007 rte->flags = flags;
1008 rte->ext_tag = tag;
1009
1010 rt_nexthop_add(rte, vnh, v_type, adv_rtr);
1011
1012 rt_insert(rte);
1013 } else {
1014 /* order:
1015 * 1. intra-area
1016 * 2. inter-area
1017 * 3. type 1 as ext
1018 * 4. type 2 as ext
1019 */
1020 if (rte->invalid) /* everything is better than invalid */
1021 better = 1;
1022 else if (p_type < rte->p_type)
1023 better = 1;
1024 else if (p_type == rte->p_type)
1025 switch (p_type) {
1026 case PT_INTRA_AREA:
1027 case PT_INTER_AREA:
1028 if (cost < rte->cost)
1029 better = 1;
1030 else if (cost == rte->cost &&
1031 rte->area.s_addr == area.s_addr)
1032 equal = 1;
1033 break;
1034 case PT_TYPE1_EXT:
1035 if (cost < rte->cost)
1036 better = 1;
1037 else if (cost == rte->cost)
1038 equal = 1;
1039 break;
1040 case PT_TYPE2_EXT:
1041 if (cost2 < rte->cost2)
1042 better = 1;
1043 else if (cost2 == rte->cost2 &&
1044 cost < rte->cost)
1045 better = 1;
1046 else if (cost2 == rte->cost2 &&
1047 cost == rte->cost)
1048 equal = 1;
1049 break;
1050 }
1051
1052 if (better) {
1053 TAILQ_FOREACH(rn, &rte->nexthop, entry)
1054 rn->invalid = 1;
1055
1056 rte->area = area;
1057 rte->cost = cost;
1058 rte->cost2 = cost2;
1059 rte->p_type = p_type;
1060 rte->flags = flags;
1061 rte->ext_tag = tag;
1062 }
1063
1064 if (equal || better)
1065 rt_nexthop_add(rte, vnh, v_type, adv_rtr);
1066 }
1067 }
1068
1069 struct rt_node *
rt_lookup(enum dst_type type,struct in6_addr * addr)1070 rt_lookup(enum dst_type type, struct in6_addr *addr)
1071 {
1072 struct rt_node *rn;
1073 struct in6_addr ina;
1074 u_int8_t i = 128;
1075
1076 if (type == DT_RTR) {
1077 rn = rt_find(addr, 128, type);
1078 if (rn && rn->invalid == 0)
1079 return (rn);
1080 return (NULL);
1081 }
1082
1083 /* type == DT_NET */
1084 do {
1085 inet6applymask(&ina, addr, i);
1086 if ((rn = rt_find(&ina, i, type)) && rn->invalid == 0)
1087 return (rn);
1088 } while (i-- != 0);
1089
1090 return (NULL);
1091 }
1092
1093 /* router LSA links */
1094 struct lsa_rtr_link *
get_rtr_link(struct vertex * v,unsigned int idx)1095 get_rtr_link(struct vertex *v, unsigned int idx)
1096 {
1097 struct lsa_rtr_link *rtr_link = NULL;
1098 unsigned int frag = 1;
1099 unsigned int frag_nlinks;
1100 unsigned int nlinks = 0;
1101 unsigned int i;
1102
1103 if (v->type != LSA_TYPE_ROUTER)
1104 fatalx("get_rtr_link: invalid LSA type");
1105
1106 /* Treat multiple Router-LSAs originated by the same router
1107 * as an aggregate. */
1108 do {
1109 /* number of links validated earlier by lsa_check() */
1110 rtr_link = (struct lsa_rtr_link *)((char *)v->lsa +
1111 sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr));
1112 frag_nlinks = ((ntohs(v->lsa->hdr.len) -
1113 sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) /
1114 sizeof(struct lsa_rtr_link));
1115 if (nlinks + frag_nlinks > idx) {
1116 for (i = 0; i < frag_nlinks; i++) {
1117 if (i + nlinks == idx)
1118 return (rtr_link);
1119 rtr_link++;
1120 }
1121 }
1122 nlinks += frag_nlinks;
1123 v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), frag++);
1124 } while (v);
1125
1126 fatalx("get_rtr_link: index not found");
1127 }
1128
1129 /* network LSA links */
1130 struct lsa_net_link *
get_net_link(struct vertex * v,unsigned int idx)1131 get_net_link(struct vertex *v, unsigned int idx)
1132 {
1133 struct lsa_net_link *net_link = NULL;
1134 char *buf = (char *)v->lsa;
1135 unsigned int i, nlinks;
1136
1137 if (v->type != LSA_TYPE_NETWORK)
1138 fatalx("get_net_link: invalid LSA type");
1139
1140 net_link = (struct lsa_net_link *)(buf + sizeof(v->lsa->hdr) +
1141 sizeof(struct lsa_net));
1142
1143 /* number of links validated earlier by lsa_check() */
1144 nlinks = lsa_num_links(v);
1145 for (i = 0; i < nlinks; i++) {
1146 if (i == idx)
1147 return (net_link);
1148 net_link++;
1149 }
1150
1151 fatalx("get_net_link: index not found");
1152 }
1153
1154 /* misc */
1155 int
linked(struct vertex * w,struct vertex * v)1156 linked(struct vertex *w, struct vertex *v)
1157 {
1158 struct lsa_rtr_link *rtr_link = NULL;
1159 struct lsa_net_link *net_link = NULL;
1160 unsigned int i;
1161
1162 switch (w->type) {
1163 case LSA_TYPE_ROUTER:
1164 for (i = 0; i < lsa_num_links(w); i++) {
1165 rtr_link = get_rtr_link(w, i);
1166 switch (v->type) {
1167 case LSA_TYPE_ROUTER:
1168 if (rtr_link->type == LINK_TYPE_POINTTOPOINT &&
1169 rtr_link->nbr_rtr_id == htonl(v->adv_rtr))
1170 return (1);
1171 break;
1172 case LSA_TYPE_NETWORK:
1173 if (rtr_link->type == LINK_TYPE_TRANSIT_NET &&
1174 rtr_link->nbr_rtr_id == htonl(v->adv_rtr) &&
1175 rtr_link->nbr_iface_id == htonl(v->ls_id))
1176 return (1);
1177 break;
1178 default:
1179 fatalx("linked: invalid type");
1180 }
1181 }
1182 return (0);
1183 case LSA_TYPE_NETWORK:
1184 for (i = 0; i < lsa_num_links(w); i++) {
1185 net_link = get_net_link(w, i);
1186 switch (v->type) {
1187 case LSA_TYPE_ROUTER:
1188 if (net_link->att_rtr == htonl(v->adv_rtr))
1189 return (1);
1190 break;
1191 default:
1192 fatalx("linked: invalid type");
1193 }
1194 }
1195 return (0);
1196 default:
1197 fatalx("linked: invalid LSA type");
1198 }
1199
1200 return (0);
1201 }
1202