1 /* $OpenBSD: rde_spf.c,v 1.79 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 "ospfd.h"
28 #include "ospf.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 void calc_nexthop(struct vertex *, struct vertex *,
40 struct area *, struct lsa_rtr_link *);
41 void rt_nexthop_clear(struct rt_node *);
42 void rt_nexthop_add(struct rt_node *, struct v_nexthead *, u_int8_t,
43 struct in_addr);
44 void rt_update(struct in_addr, u_int8_t, struct v_nexthead *, u_int8_t,
45 u_int32_t, u_int32_t, struct in_addr, struct in_addr,
46 enum path_type, enum dst_type, u_int8_t, u_int32_t);
47 void rt_invalidate(struct area *);
48 struct lsa_rtr_link *get_rtr_link(struct vertex *, int);
49 struct lsa_net_link *get_net_link(struct vertex *, int);
50 int linked(struct vertex *, struct vertex *);
51
52 void
spf_calc(struct area * area)53 spf_calc(struct area *area)
54 {
55 struct vertex *v, *w;
56 struct lsa_rtr_link *rtr_link = NULL;
57 struct lsa_net_link *net_link;
58 u_int32_t d;
59 int i;
60 struct in_addr addr;
61
62 /* clear SPF tree */
63 spf_tree_clr(area);
64 cand_list_clr();
65
66 /* initialize SPF tree */
67 if ((v = spf_root = lsa_find_area(area, LSA_TYPE_ROUTER,
68 rde_router_id(), rde_router_id())) == NULL) {
69 /* empty area because no interface is active */
70 return;
71 }
72
73 area->transit = 0;
74 spf_root->cost = 0;
75 w = NULL;
76
77 /* make sure the spf root has a nexthop */
78 vertex_nexthop_clear(spf_root);
79 vertex_nexthop_add(spf_root, spf_root, 0);
80
81 /* calculate SPF tree */
82 do {
83 /* loop links */
84 for (i = 0; i < lsa_num_links(v); i++) {
85 switch (v->type) {
86 case LSA_TYPE_ROUTER:
87 rtr_link = get_rtr_link(v, i);
88 switch (rtr_link->type) {
89 case LINK_TYPE_STUB_NET:
90 /* skip */
91 continue;
92 case LINK_TYPE_POINTTOPOINT:
93 case LINK_TYPE_VIRTUAL:
94 /* find router LSA */
95 w = lsa_find_area(area, LSA_TYPE_ROUTER,
96 rtr_link->id, rtr_link->id);
97 break;
98 case LINK_TYPE_TRANSIT_NET:
99 /* find network LSA */
100 w = lsa_find_net(area, rtr_link->id);
101 break;
102 default:
103 fatalx("spf_calc: invalid link type");
104 }
105 break;
106 case LSA_TYPE_NETWORK:
107 net_link = get_net_link(v, i);
108 /* find router LSA */
109 w = lsa_find_area(area, LSA_TYPE_ROUTER,
110 net_link->att_rtr, net_link->att_rtr);
111 break;
112 default:
113 fatalx("spf_calc: invalid LSA type");
114 }
115
116 if (w == NULL)
117 continue;
118
119 if (w->lsa->hdr.age == MAX_AGE)
120 continue;
121
122 if (!linked(w, v)) {
123 addr.s_addr = htonl(w->ls_id);
124 log_debug("spf_calc: w id %s type %d has ",
125 inet_ntoa(addr), w->type);
126 addr.s_addr = htonl(v->ls_id);
127 log_debug(" no link to v id %s type %d",
128 inet_ntoa(addr), v->type);
129 continue;
130 }
131
132 if (v->type == LSA_TYPE_ROUTER)
133 d = v->cost + ntohs(rtr_link->metric);
134 else
135 d = v->cost;
136
137 if (cand_list_present(w)) {
138 if (d > w->cost)
139 continue;
140 if (d < w->cost) {
141 w->cost = d;
142 vertex_nexthop_clear(w);
143 calc_nexthop(w, v, area, rtr_link);
144 /*
145 * need to readd to candidate list
146 * because the list is sorted
147 */
148 TAILQ_REMOVE(&cand_list, w, cand);
149 cand_list_add(w);
150 } else
151 /* equal cost path */
152 calc_nexthop(w, v, area, rtr_link);
153 } else if (w->cost == LS_INFINITY && d < LS_INFINITY) {
154 w->cost = d;
155
156 vertex_nexthop_clear(w);
157 calc_nexthop(w, v, area, rtr_link);
158 cand_list_add(w);
159 }
160 }
161
162 /* get next vertex */
163 v = cand_list_pop();
164 w = NULL;
165 } while (v != NULL);
166
167 /* spf_dump(area); */
168 log_debug("spf_calc: area %s calculated", inet_ntoa(area->id));
169
170 area->num_spf_calc++;
171 start_spf_timer();
172 }
173
174 void
rt_calc(struct vertex * v,struct area * area,struct ospfd_conf * conf)175 rt_calc(struct vertex *v, struct area *area, struct ospfd_conf *conf)
176 {
177 struct vertex *w;
178 struct v_nexthop *vn;
179 struct lsa_rtr_link *rtr_link = NULL;
180 int i;
181 struct in_addr addr, adv_rtr;
182
183 lsa_age(v);
184 if (ntohs(v->lsa->hdr.age) == MAX_AGE)
185 return;
186
187 switch (v->type) {
188 case LSA_TYPE_ROUTER:
189 /* stub networks */
190 if (v->cost >= LS_INFINITY)
191 return;
192
193 for (i = 0; i < lsa_num_links(v); i++) {
194 rtr_link = get_rtr_link(v, i);
195 if (rtr_link->type != LINK_TYPE_STUB_NET)
196 continue;
197
198 addr.s_addr = rtr_link->id & rtr_link->data;
199 adv_rtr.s_addr = htonl(v->adv_rtr);
200
201 rt_update(addr, mask2prefixlen(rtr_link->data),
202 &v->nexthop, v->type,
203 v->cost + ntohs(rtr_link->metric), 0,
204 area->id, adv_rtr, PT_INTRA_AREA, DT_NET,
205 v->lsa->data.rtr.flags, 0);
206 }
207
208 /* router, only add border and as-external routers */
209 if ((v->lsa->data.rtr.flags & (OSPF_RTR_B | OSPF_RTR_E)) == 0)
210 return;
211
212 addr.s_addr = htonl(v->ls_id);
213 adv_rtr.s_addr = htonl(v->adv_rtr);
214
215 rt_update(addr, 32, &v->nexthop, v->type, v->cost, 0, area->id,
216 adv_rtr, PT_INTRA_AREA, DT_RTR, v->lsa->data.rtr.flags, 0);
217 break;
218 case LSA_TYPE_NETWORK:
219 if (v->cost >= LS_INFINITY)
220 return;
221
222 addr.s_addr = htonl(v->ls_id) & v->lsa->data.net.mask;
223 adv_rtr.s_addr = htonl(v->adv_rtr);
224 rt_update(addr, mask2prefixlen(v->lsa->data.net.mask),
225 &v->nexthop, v->type, v->cost, 0, area->id, adv_rtr,
226 PT_INTRA_AREA, DT_NET, 0, 0);
227 break;
228 case LSA_TYPE_SUM_NETWORK:
229 case LSA_TYPE_SUM_ROUTER:
230 /* if ABR only look at area 0.0.0.0 LSA */
231 if (area_border_router(conf) && area->id.s_addr != INADDR_ANY)
232 return;
233
234 /* ignore self-originated stuff */
235 if (v->self)
236 return;
237
238 /* TODO type 3 area address range check */
239
240 if ((w = lsa_find_area(area, LSA_TYPE_ROUTER,
241 htonl(v->adv_rtr),
242 htonl(v->adv_rtr))) == NULL)
243 return;
244
245 /* copy nexthops */
246 vertex_nexthop_clear(v); /* XXX needed ??? */
247 TAILQ_FOREACH(vn, &w->nexthop, entry)
248 vertex_nexthop_add(v, w, vn->nexthop.s_addr);
249
250 v->cost = w->cost +
251 (ntohl(v->lsa->data.sum.metric) & LSA_METRIC_MASK);
252
253 if (v->cost >= LS_INFINITY)
254 return;
255
256 adv_rtr.s_addr = htonl(v->adv_rtr);
257 if (v->type == LSA_TYPE_SUM_NETWORK) {
258 addr.s_addr = htonl(v->ls_id) & v->lsa->data.sum.mask;
259 rt_update(addr, mask2prefixlen(v->lsa->data.sum.mask),
260 &v->nexthop, v->type, v->cost, 0, area->id, adv_rtr,
261 PT_INTER_AREA, DT_NET, 0, 0);
262 } else {
263 addr.s_addr = htonl(v->ls_id);
264 rt_update(addr, 32, &v->nexthop, v->type, v->cost, 0,
265 area->id, adv_rtr, PT_INTER_AREA, DT_RTR,
266 v->lsa->data.rtr.flags, 0);
267 }
268
269 break;
270 case LSA_TYPE_AREA_OPAQ:
271 /* nothing to calculate */
272 break;
273 default:
274 /* as-external LSA are stored in a different tree */
275 fatalx("rt_calc: invalid LSA type");
276 }
277 }
278
279 void
asext_calc(struct vertex * v)280 asext_calc(struct vertex *v)
281 {
282 struct rt_node *r;
283 struct rt_nexthop *rn;
284 u_int32_t cost2;
285 struct in_addr addr, adv_rtr, a;
286 enum path_type type;
287
288 lsa_age(v);
289 if (ntohs(v->lsa->hdr.age) == MAX_AGE ||
290 (ntohl(v->lsa->data.asext.metric) & LSA_METRIC_MASK) >=
291 LS_INFINITY)
292 return;
293
294 switch (v->type) {
295 case LSA_TYPE_EXTERNAL:
296 /* ignore self-originated stuff */
297 if (v->self)
298 return;
299
300 if ((r = rt_lookup(DT_RTR, htonl(v->adv_rtr))) == NULL)
301 return;
302
303 /* XXX RFC1583Compatibility */
304 if (v->lsa->data.asext.fw_addr != 0 &&
305 (r = rt_lookup(DT_NET, v->lsa->data.asext.fw_addr)) == NULL)
306 return;
307
308 if (v->lsa->data.asext.fw_addr != 0 &&
309 r->p_type != PT_INTRA_AREA &&
310 r->p_type != PT_INTER_AREA)
311 return;
312
313 if (ntohl(v->lsa->data.asext.metric) & LSA_ASEXT_E_FLAG) {
314 v->cost = r->cost;
315 cost2 = ntohl(v->lsa->data.asext.metric) &
316 LSA_METRIC_MASK;
317 type = PT_TYPE2_EXT;
318 } else {
319 v->cost = r->cost + (ntohl(v->lsa->data.asext.metric) &
320 LSA_METRIC_MASK);
321 cost2 = 0;
322 type = PT_TYPE1_EXT;
323 }
324
325 a.s_addr = 0;
326 adv_rtr.s_addr = htonl(v->adv_rtr);
327 addr.s_addr = htonl(v->ls_id) & v->lsa->data.asext.mask;
328
329 vertex_nexthop_clear(v);
330 TAILQ_FOREACH(rn, &r->nexthop, entry) {
331 if (rn->invalid)
332 continue;
333
334 /*
335 * if a fw_addr is specified and the nexthop
336 * is directly connected then it is possible to
337 * send traffic directly to fw_addr.
338 */
339 if (v->lsa->data.asext.fw_addr != 0 && rn->connected)
340 vertex_nexthop_add(v, NULL,
341 v->lsa->data.asext.fw_addr);
342 else
343 vertex_nexthop_add(v, NULL, rn->nexthop.s_addr);
344 }
345
346 rt_update(addr, mask2prefixlen(v->lsa->data.asext.mask),
347 &v->nexthop, v->type, v->cost, cost2, a, adv_rtr, type,
348 DT_NET, 0, ntohl(v->lsa->data.asext.ext_tag));
349 break;
350 case LSA_TYPE_AS_OPAQ:
351 /* nothing to calculate */
352 break;
353 default:
354 fatalx("asext_calc: invalid LSA type");
355 }
356 }
357
358 void
spf_tree_clr(struct area * area)359 spf_tree_clr(struct area *area)
360 {
361 struct lsa_tree *tree = &area->lsa_tree;
362 struct vertex *v;
363
364 RB_FOREACH(v, lsa_tree, tree) {
365 v->cost = LS_INFINITY;
366 vertex_nexthop_clear(v);
367 }
368 }
369
370 void
calc_nexthop(struct vertex * dst,struct vertex * parent,struct area * area,struct lsa_rtr_link * rtr_link)371 calc_nexthop(struct vertex *dst, struct vertex *parent,
372 struct area *area, struct lsa_rtr_link *rtr_link)
373 {
374 struct v_nexthop *vn;
375 struct iface *iface;
376 struct rde_nbr *nbr;
377 int i;
378
379 /* case 1 */
380 if (parent == spf_root) {
381 switch (dst->type) {
382 case LSA_TYPE_ROUTER:
383 if (rtr_link->type != LINK_TYPE_POINTTOPOINT)
384 fatalx("inconsistent SPF tree");
385 LIST_FOREACH(iface, &area->iface_list, entry) {
386 if (rtr_link->data != iface->addr.s_addr)
387 continue;
388 LIST_FOREACH(nbr, &area->nbr_list, entry) {
389 if (nbr->ifindex == iface->ifindex) {
390 vertex_nexthop_add(dst, parent,
391 nbr->addr.s_addr);
392 return;
393 }
394 }
395 }
396 fatalx("no interface found for interface");
397 case LSA_TYPE_NETWORK:
398 switch (rtr_link->type) {
399 case LINK_TYPE_POINTTOPOINT:
400 case LINK_TYPE_STUB_NET:
401 /* ignore */
402 break;
403 case LINK_TYPE_TRANSIT_NET:
404 if ((htonl(dst->ls_id) &
405 dst->lsa->data.net.mask) ==
406 (rtr_link->data &
407 dst->lsa->data.net.mask)) {
408 vertex_nexthop_add(dst, parent,
409 rtr_link->data);
410 }
411 break;
412 default:
413 fatalx("calc_nexthop: invalid link "
414 "type");
415 }
416 return;
417 default:
418 fatalx("calc_nexthop: invalid dst type");
419 }
420 return;
421 }
422
423 /* case 2 */
424 if (parent->type == LSA_TYPE_NETWORK && dst->type == LSA_TYPE_ROUTER) {
425 TAILQ_FOREACH(vn, &parent->nexthop, entry) {
426 if (vn->prev == spf_root) {
427 for (i = 0; i < lsa_num_links(dst); i++) {
428 rtr_link = get_rtr_link(dst, i);
429 if ((rtr_link->type ==
430 LINK_TYPE_TRANSIT_NET) &&
431 (rtr_link->data &
432 parent->lsa->data.net.mask) ==
433 (htonl(parent->ls_id) &
434 parent->lsa->data.net.mask))
435 vertex_nexthop_add(dst, parent,
436 rtr_link->data);
437 }
438 } else {
439 vertex_nexthop_add(dst, parent,
440 vn->nexthop.s_addr);
441 }
442 }
443 return;
444 }
445
446 /* case 3 */
447 TAILQ_FOREACH(vn, &parent->nexthop, entry)
448 vertex_nexthop_add(dst, parent, vn->nexthop.s_addr);
449 }
450
451 /* candidate list */
452 void
cand_list_init(void)453 cand_list_init(void)
454 {
455 TAILQ_INIT(&cand_list);
456 }
457
458 void
cand_list_add(struct vertex * v)459 cand_list_add(struct vertex *v)
460 {
461 struct vertex *c = NULL;
462
463 TAILQ_FOREACH(c, &cand_list, cand) {
464 if (c->cost > v->cost) {
465 TAILQ_INSERT_BEFORE(c, v, cand);
466 return;
467 } else if (c->cost == v->cost && c->type == LSA_TYPE_ROUTER &&
468 v->type == LSA_TYPE_NETWORK) {
469 TAILQ_INSERT_BEFORE(c, v, cand);
470 return;
471 }
472 }
473 TAILQ_INSERT_TAIL(&cand_list, v, cand);
474 }
475
476 struct vertex *
cand_list_pop(void)477 cand_list_pop(void)
478 {
479 struct vertex *c;
480
481 if ((c = TAILQ_FIRST(&cand_list)) != NULL) {
482 TAILQ_REMOVE(&cand_list, c, cand);
483 }
484
485 return (c);
486 }
487
488 int
cand_list_present(struct vertex * v)489 cand_list_present(struct vertex *v)
490 {
491 struct vertex *c;
492
493 TAILQ_FOREACH(c, &cand_list, cand) {
494 if (c == v)
495 return (1);
496 }
497
498 return (0);
499 }
500
501 void
cand_list_clr(void)502 cand_list_clr(void)
503 {
504 struct vertex *c;
505
506 while ((c = TAILQ_FIRST(&cand_list)) != NULL) {
507 TAILQ_REMOVE(&cand_list, c, cand);
508 }
509 }
510
511 /* timers */
512 void
spf_timer(int fd,short event,void * arg)513 spf_timer(int fd, short event, void *arg)
514 {
515 struct vertex *v;
516 struct ospfd_conf *conf = arg;
517 struct area *area;
518 struct rt_node *r;
519
520 switch (conf->spf_state) {
521 case SPF_IDLE:
522 fatalx("spf_timer: invalid state IDLE");
523 case SPF_HOLDQUEUE:
524 conf->spf_state = SPF_DELAY;
525 /* FALLTHROUGH */
526 case SPF_DELAY:
527 LIST_FOREACH(area, &conf->area_list, entry) {
528 if (area->dirty) {
529 /* invalidate RIB entries of this area */
530 rt_invalidate(area);
531
532 /* calculate SPF tree */
533 spf_calc(area);
534
535 /* calculate route table */
536 RB_FOREACH(v, lsa_tree, &area->lsa_tree) {
537 rt_calc(v, area, conf);
538 }
539
540 area->dirty = 0;
541 }
542 }
543
544 /* calculate as-external routes, first invalidate them */
545 rt_invalidate(NULL);
546 RB_FOREACH(v, lsa_tree, &asext_tree) {
547 asext_calc(v);
548 }
549
550 RB_FOREACH(r, rt_tree, &rt) {
551 LIST_FOREACH(area, &conf->area_list, entry)
552 rde_summary_update(r, area);
553
554 if (r->d_type != DT_NET)
555 continue;
556
557 if (r->invalid)
558 rde_send_delete_kroute(r);
559 else
560 rde_send_change_kroute(r);
561 }
562
563 LIST_FOREACH(area, &conf->area_list, entry) {
564 lsa_generate_stub_sums(area);
565 lsa_remove_invalid_sums(area);
566 }
567
568 start_spf_holdtimer(conf);
569 break;
570 case SPF_HOLD:
571 conf->spf_state = SPF_IDLE;
572 break;
573 default:
574 fatalx("spf_timer: unknown state");
575 }
576 }
577
578 void
start_spf_timer(void)579 start_spf_timer(void)
580 {
581 struct timeval tv;
582
583 switch (rdeconf->spf_state) {
584 case SPF_IDLE:
585 timerclear(&tv);
586 tv.tv_sec = rdeconf->spf_delay / 1000;
587 tv.tv_usec = (rdeconf->spf_delay % 1000) * 1000;
588 rdeconf->spf_state = SPF_DELAY;
589 if (evtimer_add(&rdeconf->ev, &tv) == -1)
590 fatal("start_spf_timer");
591 break;
592 case SPF_DELAY:
593 /* ignore */
594 break;
595 case SPF_HOLD:
596 rdeconf->spf_state = SPF_HOLDQUEUE;
597 break;
598 case SPF_HOLDQUEUE:
599 /* ignore */
600 break;
601 default:
602 fatalx("start_spf_timer: invalid spf_state");
603 }
604 }
605
606 void
stop_spf_timer(struct ospfd_conf * conf)607 stop_spf_timer(struct ospfd_conf *conf)
608 {
609 if (evtimer_del(&conf->ev) == -1)
610 fatal("stop_spf_timer");
611 }
612
613 void
start_spf_holdtimer(struct ospfd_conf * conf)614 start_spf_holdtimer(struct ospfd_conf *conf)
615 {
616 struct timeval tv;
617
618 switch (conf->spf_state) {
619 case SPF_DELAY:
620 timerclear(&tv);
621 tv.tv_sec = rdeconf->spf_hold_time / 1000;
622 tv.tv_usec = (rdeconf->spf_hold_time % 1000) * 1000;
623 conf->spf_state = SPF_HOLD;
624 if (evtimer_add(&conf->ev, &tv) == -1)
625 fatal("start_spf_holdtimer");
626 break;
627 case SPF_IDLE:
628 case SPF_HOLD:
629 case SPF_HOLDQUEUE:
630 fatalx("start_spf_holdtimer: invalid state");
631 default:
632 fatalx("start_spf_holdtimer: unknown state");
633 }
634 }
635
636 /* route table */
637 void
rt_init(void)638 rt_init(void)
639 {
640 RB_INIT(&rt);
641 }
642
643 int
rt_compare(struct rt_node * a,struct rt_node * b)644 rt_compare(struct rt_node *a, struct rt_node *b)
645 {
646 if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr))
647 return (-1);
648 if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr))
649 return (1);
650 if (a->prefixlen < b->prefixlen)
651 return (-1);
652 if (a->prefixlen > b->prefixlen)
653 return (1);
654 if (a->d_type > b->d_type)
655 return (-1);
656 if (a->d_type < b->d_type)
657 return (1);
658 return (0);
659 }
660
661 struct rt_node *
rt_find(in_addr_t prefix,u_int8_t prefixlen,enum dst_type d_type)662 rt_find(in_addr_t prefix, u_int8_t prefixlen, enum dst_type d_type)
663 {
664 struct rt_node s;
665
666 s.prefix.s_addr = prefix;
667 s.prefixlen = prefixlen;
668 s.d_type = d_type;
669
670 return (RB_FIND(rt_tree, &rt, &s));
671 }
672
673 int
rt_insert(struct rt_node * r)674 rt_insert(struct rt_node *r)
675 {
676 if (RB_INSERT(rt_tree, &rt, r) != NULL) {
677 log_warnx("rt_insert failed for %s/%u",
678 inet_ntoa(r->prefix), r->prefixlen);
679 free(r);
680 return (-1);
681 }
682
683 return (0);
684 }
685
686 int
rt_remove(struct rt_node * r)687 rt_remove(struct rt_node *r)
688 {
689 if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
690 log_warnx("rt_remove failed for %s/%u",
691 inet_ntoa(r->prefix), r->prefixlen);
692 return (-1);
693 }
694
695 rt_nexthop_clear(r);
696 free(r);
697 return (0);
698 }
699
700 void
rt_invalidate(struct area * area)701 rt_invalidate(struct area *area)
702 {
703 struct rt_node *r, *nr;
704 struct rt_nexthop *rn, *nrn;
705
706 for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) {
707 nr = RB_NEXT(rt_tree, &rt, r);
708 if (area == NULL) {
709 /* look only at as_ext routes */
710 if (r->p_type != PT_TYPE1_EXT &&
711 r->p_type != PT_TYPE2_EXT)
712 continue;
713 } else {
714 /* ignore all as_ext routes */
715 if (r->p_type == PT_TYPE1_EXT ||
716 r->p_type == PT_TYPE2_EXT)
717 continue;
718
719 /* look only at routes matching the area */
720 if (r->area.s_addr != area->id.s_addr)
721 continue;
722 }
723 r->invalid = 1;
724 for (rn = TAILQ_FIRST(&r->nexthop); rn != NULL; rn = nrn) {
725 nrn = TAILQ_NEXT(rn, entry);
726 if (rn->invalid) {
727 TAILQ_REMOVE(&r->nexthop, rn, entry);
728 free(rn);
729 } else
730 rn->invalid = 1;
731 }
732 if (TAILQ_EMPTY(&r->nexthop))
733 rt_remove(r);
734 }
735 }
736
737 void
rt_nexthop_clear(struct rt_node * r)738 rt_nexthop_clear(struct rt_node *r)
739 {
740 struct rt_nexthop *rn;
741
742 while ((rn = TAILQ_FIRST(&r->nexthop)) != NULL) {
743 TAILQ_REMOVE(&r->nexthop, rn, entry);
744 free(rn);
745 }
746 }
747
748 void
rt_nexthop_add(struct rt_node * r,struct v_nexthead * vnh,u_int8_t type,struct in_addr adv_rtr)749 rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh, u_int8_t type,
750 struct in_addr adv_rtr)
751 {
752 struct v_nexthop *vn;
753 struct rt_nexthop *rn;
754 struct timespec now;
755
756 TAILQ_FOREACH(vn, vnh, entry) {
757 TAILQ_FOREACH(rn, &r->nexthop, entry) {
758 if (rn->nexthop.s_addr != vn->nexthop.s_addr)
759 continue;
760
761 rn->adv_rtr.s_addr = adv_rtr.s_addr;
762 rn->connected = (type == LSA_TYPE_NETWORK &&
763 vn->prev == spf_root) || (vn->nexthop.s_addr == 0);
764 rn->invalid = 0;
765
766 r->invalid = 0;
767 break;
768 }
769 if (rn)
770 continue;
771
772 if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL)
773 fatal("rt_nexthop_add");
774
775 clock_gettime(CLOCK_MONOTONIC, &now);
776 rn->nexthop.s_addr = vn->nexthop.s_addr;
777 rn->adv_rtr.s_addr = adv_rtr.s_addr;
778 rn->uptime = now.tv_sec;
779 rn->connected = (type == LSA_TYPE_NETWORK &&
780 vn->prev == spf_root) || (vn->nexthop.s_addr == 0);
781 rn->invalid = 0;
782
783 r->invalid = 0;
784 TAILQ_INSERT_TAIL(&r->nexthop, rn, entry);
785 }
786 }
787
788 void
rt_clear(void)789 rt_clear(void)
790 {
791 struct rt_node *r;
792
793 while ((r = RB_MIN(rt_tree, &rt)) != NULL)
794 rt_remove(r);
795 }
796
797 void
rt_dump(struct in_addr area,pid_t pid,u_int8_t r_type)798 rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type)
799 {
800 static struct ctl_rt rtctl;
801 struct timespec now;
802 struct rt_node *r;
803 struct rt_nexthop *rn;
804
805 clock_gettime(CLOCK_MONOTONIC, &now);
806
807 RB_FOREACH(r, rt_tree, &rt) {
808 if (r->invalid)
809 continue;
810
811 if (r->area.s_addr != area.s_addr)
812 continue;
813
814 switch (r_type) {
815 case RIB_RTR:
816 if (r->d_type != DT_RTR)
817 continue;
818 break;
819 case RIB_NET:
820 if (r->d_type != DT_NET)
821 continue;
822 if (r->p_type == PT_TYPE1_EXT ||
823 r->p_type == PT_TYPE2_EXT)
824 continue;
825 break;
826 case RIB_EXT:
827 if (r->p_type != PT_TYPE1_EXT &&
828 r->p_type != PT_TYPE2_EXT)
829 continue;
830 break;
831 default:
832 fatalx("rt_dump: invalid RIB type");
833 }
834
835 bzero(&rtctl, sizeof(rtctl));
836 rtctl.prefix.s_addr = r->prefix.s_addr;
837 rtctl.area.s_addr = r->area.s_addr;
838 rtctl.cost = r->cost;
839 rtctl.cost2 = r->cost2;
840 rtctl.p_type = r->p_type;
841 rtctl.d_type = r->d_type;
842 rtctl.flags = r->flags;
843 rtctl.prefixlen = r->prefixlen;
844
845 TAILQ_FOREACH(rn, &r->nexthop, entry) {
846 if (rn->invalid)
847 continue;
848
849 rtctl.connected = rn->connected;
850 rtctl.nexthop.s_addr = rn->nexthop.s_addr;
851 rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr;
852 rtctl.uptime = now.tv_sec - rn->uptime;
853
854 rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid,
855 &rtctl, sizeof(rtctl));
856 }
857 }
858 }
859
860 void
rt_update(struct in_addr prefix,u_int8_t prefixlen,struct v_nexthead * vnh,u_int8_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)861 rt_update(struct in_addr prefix, u_int8_t prefixlen, struct v_nexthead *vnh,
862 u_int8_t v_type, u_int32_t cost, u_int32_t cost2, struct in_addr area,
863 struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type,
864 u_int8_t flags, u_int32_t tag)
865 {
866 struct rt_node *rte;
867 struct rt_nexthop *rn;
868 int better = 0, equal = 0;
869
870 if ((rte = rt_find(prefix.s_addr, prefixlen, d_type)) == NULL) {
871 if ((rte = calloc(1, sizeof(struct rt_node))) == NULL)
872 fatal("rt_update");
873
874 TAILQ_INIT(&rte->nexthop);
875 rte->prefix.s_addr = prefix.s_addr;
876 rte->prefixlen = prefixlen;
877 rte->cost = cost;
878 rte->cost2 = cost2;
879 rte->area = area;
880 rte->p_type = p_type;
881 rte->d_type = d_type;
882 rte->flags = flags;
883 rte->ext_tag = tag;
884
885 rt_nexthop_add(rte, vnh, v_type, adv_rtr);
886
887 rt_insert(rte);
888 } else {
889 /* order:
890 * 1. intra-area
891 * 2. inter-area
892 * 3. type 1 as ext
893 * 4. type 2 as ext
894 */
895 if (rte->invalid) /* everything is better than invalid */
896 better = 1;
897 else if (p_type < rte->p_type)
898 better = 1;
899 else if (p_type == rte->p_type)
900 switch (p_type) {
901 case PT_INTRA_AREA:
902 case PT_INTER_AREA:
903 if (cost < rte->cost)
904 better = 1;
905 else if (cost == rte->cost &&
906 rte->area.s_addr == area.s_addr)
907 equal = 1;
908 break;
909 case PT_TYPE1_EXT:
910 /* XXX rfc1583 compat */
911 if (cost < rte->cost)
912 better = 1;
913 else if (cost == rte->cost)
914 equal = 1;
915 break;
916 case PT_TYPE2_EXT:
917 if (cost2 < rte->cost2)
918 better = 1;
919 /* XXX rfc1583 compat */
920 else if (cost2 == rte->cost2 &&
921 cost < rte->cost)
922 better = 1;
923 else if (cost2 == rte->cost2 &&
924 cost == rte->cost)
925 equal = 1;
926 break;
927 }
928
929 if (better) {
930 TAILQ_FOREACH(rn, &rte->nexthop, entry)
931 rn->invalid = 1;
932
933 rte->area = area;
934 rte->cost = cost;
935 rte->cost2 = cost2;
936 rte->p_type = p_type;
937 rte->flags = flags;
938 rte->ext_tag = tag;
939 }
940
941 if (equal || better)
942 rt_nexthop_add(rte, vnh, v_type, adv_rtr);
943 }
944 }
945
946 struct rt_node *
rt_lookup(enum dst_type type,in_addr_t addr)947 rt_lookup(enum dst_type type, in_addr_t addr)
948 {
949 struct rt_node *rn;
950 u_int8_t i = 32;
951
952 if (type == DT_RTR) {
953 rn = rt_find(addr, 32, type);
954 if (rn && rn->invalid == 0)
955 return (rn);
956 return (NULL);
957 }
958
959 /* type == DT_NET */
960 do {
961 if ((rn = rt_find(addr & prefixlen2mask(i), i, type)) &&
962 rn->invalid == 0)
963 return (rn);
964 } while (i-- != 0);
965
966 return (NULL);
967 }
968
969 /* router LSA links */
970 struct lsa_rtr_link *
get_rtr_link(struct vertex * v,int idx)971 get_rtr_link(struct vertex *v, int idx)
972 {
973 struct lsa_rtr_link *rtr_link = NULL;
974 char *buf = (char *)v->lsa;
975 u_int16_t i, off, nlinks;
976
977 if (v->type != LSA_TYPE_ROUTER)
978 fatalx("get_rtr_link: invalid LSA type");
979
980 off = sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr);
981
982 /* nlinks validated earlier by lsa_check() */
983 nlinks = lsa_num_links(v);
984 for (i = 0; i < nlinks; i++) {
985 rtr_link = (struct lsa_rtr_link *)(buf + off);
986 if (i == idx)
987 return (rtr_link);
988
989 off += sizeof(struct lsa_rtr_link) +
990 rtr_link->num_tos * sizeof(u_int32_t);
991 }
992
993 fatalx("get_rtr_link: index not found");
994 }
995
996 /* network LSA links */
997 struct lsa_net_link *
get_net_link(struct vertex * v,int idx)998 get_net_link(struct vertex *v, int idx)
999 {
1000 struct lsa_net_link *net_link = NULL;
1001 char *buf = (char *)v->lsa;
1002 u_int16_t i, off, nlinks;
1003
1004 if (v->type != LSA_TYPE_NETWORK)
1005 fatalx("get_net_link: invalid LSA type");
1006
1007 off = sizeof(v->lsa->hdr) + sizeof(u_int32_t);
1008
1009 /* nlinks validated earlier by lsa_check() */
1010 nlinks = lsa_num_links(v);
1011 for (i = 0; i < nlinks; i++) {
1012 net_link = (struct lsa_net_link *)(buf + off);
1013 if (i == idx)
1014 return (net_link);
1015
1016 off += sizeof(struct lsa_net_link);
1017 }
1018
1019 fatalx("get_net_link: index not found");
1020 }
1021
1022 /* misc */
1023 int
linked(struct vertex * w,struct vertex * v)1024 linked(struct vertex *w, struct vertex *v)
1025 {
1026 struct lsa_rtr_link *rtr_link = NULL;
1027 struct lsa_net_link *net_link = NULL;
1028 int i;
1029
1030 switch (w->type) {
1031 case LSA_TYPE_ROUTER:
1032 for (i = 0; i < lsa_num_links(w); i++) {
1033 rtr_link = get_rtr_link(w, i);
1034 switch (v->type) {
1035 case LSA_TYPE_ROUTER:
1036 if (rtr_link->type == LINK_TYPE_POINTTOPOINT &&
1037 rtr_link->id == htonl(v->ls_id))
1038 return (1);
1039 break;
1040 case LSA_TYPE_NETWORK:
1041 if (rtr_link->id == htonl(v->ls_id))
1042 return (1);
1043 break;
1044 default:
1045 fatalx("linked: invalid type");
1046 }
1047 }
1048 return (0);
1049 case LSA_TYPE_NETWORK:
1050 for (i = 0; i < lsa_num_links(w); i++) {
1051 net_link = get_net_link(w, i);
1052 switch (v->type) {
1053 case LSA_TYPE_ROUTER:
1054 if (net_link->att_rtr == htonl(v->ls_id))
1055 return (1);
1056 break;
1057 default:
1058 fatalx("linked: invalid type");
1059 }
1060 }
1061 return (0);
1062 default:
1063 fatalx("linked: invalid LSA type");
1064 }
1065
1066 return (0);
1067 }
1068