1 /* $OpenBSD: rde_lsdb.c,v 1.48 2023/03/08 04:43:14 guenther Exp $ */
2
3 /*
4 * Copyright (c) 2004, 2005 Claudio Jeker <claudio@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/tree.h>
21 #include <stdlib.h>
22 #include <string.h>
23 #include <unistd.h>
24
25 #include "ospf6.h"
26 #include "ospf6d.h"
27 #include "rde.h"
28 #include "log.h"
29
30 struct vertex *vertex_get(struct lsa *, struct rde_nbr *, struct lsa_tree *);
31
32 int lsa_link_check(struct lsa *, u_int16_t);
33 int lsa_intra_a_pref_check(struct lsa *, u_int16_t);
34 int lsa_asext_check(struct lsa *, u_int16_t);
35 void lsa_timeout(int, short, void *);
36 void lsa_refresh(struct vertex *);
37 int lsa_equal(struct lsa *, struct lsa *);
38 int lsa_get_prefix(void *, u_int16_t, struct rt_prefix *);
39
RB_GENERATE(lsa_tree,vertex,entry,lsa_compare)40 RB_GENERATE(lsa_tree, vertex, entry, lsa_compare)
41
42 void
43 lsa_init(struct lsa_tree *t)
44 {
45 RB_INIT(t);
46 }
47
48 int
lsa_compare(struct vertex * a,struct vertex * b)49 lsa_compare(struct vertex *a, struct vertex *b)
50 {
51 if (a->type < b->type)
52 return (-1);
53 if (a->type > b->type)
54 return (1);
55 if (a->adv_rtr < b->adv_rtr)
56 return (-1);
57 if (a->adv_rtr > b->adv_rtr)
58 return (1);
59 if (a->ls_id < b->ls_id)
60 return (-1);
61 if (a->ls_id > b->ls_id)
62 return (1);
63 return (0);
64 }
65
66
67 struct vertex *
vertex_get(struct lsa * lsa,struct rde_nbr * nbr,struct lsa_tree * tree)68 vertex_get(struct lsa *lsa, struct rde_nbr *nbr, struct lsa_tree *tree)
69 {
70 struct vertex *v;
71 struct timespec tp;
72
73 if ((v = calloc(1, sizeof(struct vertex))) == NULL)
74 fatal(NULL);
75 TAILQ_INIT(&v->nexthop);
76 v->area = nbr->area;
77 v->peerid = nbr->peerid;
78 v->lsa = lsa;
79 clock_gettime(CLOCK_MONOTONIC, &tp);
80 v->changed = v->stamp = tp.tv_sec;
81 v->cost = LS_INFINITY;
82 v->ls_id = ntohl(lsa->hdr.ls_id);
83 v->adv_rtr = ntohl(lsa->hdr.adv_rtr);
84 v->type = ntohs(lsa->hdr.type);
85 v->lsa_tree = tree;
86
87 if (!nbr->self)
88 v->flooded = 1; /* XXX fix me */
89 v->self = nbr->self;
90
91 evtimer_set(&v->ev, lsa_timeout, v);
92
93 return (v);
94 }
95
96 void
vertex_free(struct vertex * v)97 vertex_free(struct vertex *v)
98 {
99 RB_REMOVE(lsa_tree, v->lsa_tree, v);
100
101 (void)evtimer_del(&v->ev);
102 vertex_nexthop_clear(v);
103 free(v->lsa);
104 free(v);
105 }
106
107 void
vertex_nexthop_clear(struct vertex * v)108 vertex_nexthop_clear(struct vertex *v)
109 {
110 struct v_nexthop *vn;
111
112 while ((vn = TAILQ_FIRST(&v->nexthop))) {
113 TAILQ_REMOVE(&v->nexthop, vn, entry);
114 free(vn);
115 }
116 }
117
118 void
vertex_nexthop_add(struct vertex * dst,struct vertex * parent,const struct in6_addr * nexthop,u_int32_t ifindex)119 vertex_nexthop_add(struct vertex *dst, struct vertex *parent,
120 const struct in6_addr *nexthop, u_int32_t ifindex)
121 {
122 struct v_nexthop *vn;
123
124 if ((vn = calloc(1, sizeof(*vn))) == NULL)
125 fatal("vertex_nexthop_add");
126
127 vn->prev = parent;
128 if (nexthop)
129 vn->nexthop = *nexthop;
130 vn->ifindex = ifindex;
131
132 TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry);
133 }
134
135 /* returns -1 if a is older, 1 if newer and 0 if equal to b */
136 int
lsa_newer(struct lsa_hdr * a,struct lsa_hdr * b)137 lsa_newer(struct lsa_hdr *a, struct lsa_hdr *b)
138 {
139 int32_t a32, b32;
140 u_int16_t a16, b16;
141 int i;
142
143 if (a == NULL)
144 return (-1);
145 if (b == NULL)
146 return (1);
147
148 /*
149 * The sequence number is defined as signed 32-bit integer,
150 * no idea how IETF came up with such a stupid idea.
151 */
152 a32 = (int32_t)ntohl(a->seq_num);
153 b32 = (int32_t)ntohl(b->seq_num);
154
155 if (a32 > b32)
156 return (1);
157 if (a32 < b32)
158 return (-1);
159
160 a16 = ntohs(a->ls_chksum);
161 b16 = ntohs(b->ls_chksum);
162
163 if (a16 > b16)
164 return (1);
165 if (a16 < b16)
166 return (-1);
167
168 a16 = ntohs(a->age);
169 b16 = ntohs(b->age);
170
171 if (a16 >= MAX_AGE && b16 >= MAX_AGE)
172 return (0);
173 if (b16 >= MAX_AGE)
174 return (-1);
175 if (a16 >= MAX_AGE)
176 return (1);
177
178 i = b16 - a16;
179 if (abs(i) > MAX_AGE_DIFF)
180 return (i > 0 ? 1 : -1);
181
182 return (0);
183 }
184
185 int
lsa_check(struct rde_nbr * nbr,struct lsa * lsa,u_int16_t len)186 lsa_check(struct rde_nbr *nbr, struct lsa *lsa, u_int16_t len)
187 {
188 u_int32_t metric;
189
190 if (len < sizeof(lsa->hdr)) {
191 log_warnx("lsa_check: bad packet size");
192 return (0);
193 }
194 if (ntohs(lsa->hdr.len) != len) {
195 log_warnx("lsa_check: bad packet length");
196 return (0);
197 }
198
199 if (iso_cksum(lsa, len, 0)) {
200 log_warnx("lsa_check: bad packet checksum");
201 return (0);
202 }
203
204 /* invalid ages */
205 if ((ntohs(lsa->hdr.age) < 1 && !nbr->self) ||
206 ntohs(lsa->hdr.age) > MAX_AGE) {
207 log_warnx("lsa_check: bad age");
208 return (0);
209 }
210
211 /* invalid sequence number */
212 if (ntohl(lsa->hdr.seq_num) == RESV_SEQ_NUM) {
213 log_warnx("lsa_check: bad seq num");
214 return (0);
215 }
216
217 switch (ntohs(lsa->hdr.type)) {
218 case LSA_TYPE_LINK:
219 if (!lsa_link_check(lsa, len))
220 return (0);
221 break;
222 case LSA_TYPE_ROUTER:
223 if (len < sizeof(lsa->hdr) + sizeof(struct lsa_rtr)) {
224 log_warnx("lsa_check: bad LSA rtr packet");
225 return (0);
226 }
227 len -= sizeof(lsa->hdr) + sizeof(struct lsa_rtr);
228 if (len % sizeof(struct lsa_rtr_link)) {
229 log_warnx("lsa_check: bad LSA rtr packet");
230 return (0);
231 }
232 break;
233 case LSA_TYPE_NETWORK:
234 if ((len % sizeof(u_int32_t)) ||
235 len < sizeof(lsa->hdr) + sizeof(u_int32_t)) {
236 log_warnx("lsa_check: bad LSA network packet");
237 return (0);
238 }
239 break;
240 case LSA_TYPE_INTER_A_PREFIX:
241 if (len < sizeof(lsa->hdr) + sizeof(lsa->data.pref_sum)) {
242 log_warnx("lsa_check: bad LSA prefix summary packet");
243 return (0);
244 }
245 metric = ntohl(lsa->data.pref_sum.metric);
246 if (metric & ~LSA_METRIC_MASK) {
247 log_warnx("lsa_check: bad LSA prefix summary metric");
248 return (0);
249 }
250 if (lsa_get_prefix(((char *)lsa) + sizeof(lsa->hdr) +
251 sizeof(lsa->data.pref_sum),
252 len - sizeof(lsa->hdr) + sizeof(lsa->data.pref_sum),
253 NULL) == -1) {
254 log_warnx("lsa_check: "
255 "invalid LSA prefix summary packet");
256 return (0);
257 }
258 break;
259 case LSA_TYPE_INTER_A_ROUTER:
260 if (len < sizeof(lsa->hdr) + sizeof(lsa->data.rtr_sum)) {
261 log_warnx("lsa_check: bad LSA router summary packet");
262 return (0);
263 }
264 metric = ntohl(lsa->data.rtr_sum.metric);
265 if (metric & ~LSA_METRIC_MASK) {
266 log_warnx("lsa_check: bad LSA router summary metric");
267 return (0);
268 }
269 break;
270 case LSA_TYPE_INTRA_A_PREFIX:
271 if (!lsa_intra_a_pref_check(lsa, len))
272 return (0);
273 break;
274 case LSA_TYPE_EXTERNAL:
275 /* AS-external-LSA are silently discarded in stub areas */
276 if (nbr->area->stub)
277 return (0);
278 if (!lsa_asext_check(lsa, len))
279 return (0);
280 break;
281 default:
282 log_warnx("lsa_check: unknown type %x", ntohs(lsa->hdr.type));
283 return (0);
284 }
285
286 /* MaxAge handling */
287 if (lsa->hdr.age == htons(MAX_AGE) && !nbr->self && lsa_find(nbr->iface,
288 lsa->hdr.type, lsa->hdr.ls_id, lsa->hdr.adv_rtr) == NULL &&
289 !rde_nbr_loading(nbr->area)) {
290 /*
291 * if no neighbor in state Exchange or Loading
292 * ack LSA but don't add it. Needs to be a direct ack.
293 */
294 rde_imsg_compose_ospfe(IMSG_LS_ACK, nbr->peerid, 0, &lsa->hdr,
295 sizeof(struct lsa_hdr));
296 return (0);
297 }
298
299 return (1);
300 }
301
302 int
lsa_link_check(struct lsa * lsa,u_int16_t len)303 lsa_link_check(struct lsa *lsa, u_int16_t len)
304 {
305 char *buf = (char *)lsa;
306 struct lsa_link *llink;
307 u_int32_t i, off, npref;
308 int rv;
309
310 llink = (struct lsa_link *)(buf + sizeof(lsa->hdr));
311 off = sizeof(lsa->hdr) + sizeof(struct lsa_link);
312 if (off > len) {
313 log_warnx("lsa_link_check: invalid LSA link packet, "
314 "short header");
315 return (0);
316 }
317
318 len -= off;
319 npref = ntohl(llink->numprefix);
320
321 for (i = 0; i < npref; i++) {
322 rv = lsa_get_prefix(buf + off, len, NULL);
323 if (rv == -1) {
324 log_warnx("lsa_link_check: invalid LSA link packet");
325 return (0);
326 }
327 off += rv;
328 len -= rv;
329 }
330
331 return (1);
332 }
333
334 int
lsa_intra_a_pref_check(struct lsa * lsa,u_int16_t len)335 lsa_intra_a_pref_check(struct lsa *lsa, u_int16_t len)
336 {
337 char *buf = (char *)lsa;
338 struct lsa_intra_prefix *iap;
339 u_int32_t i, off, npref;
340 int rv;
341
342 iap = (struct lsa_intra_prefix *)(buf + sizeof(lsa->hdr));
343 off = sizeof(lsa->hdr) + sizeof(struct lsa_intra_prefix);
344 if (off > len) {
345 log_warnx("lsa_intra_a_pref_check: "
346 "invalid LSA intra area prefix packet, short header");
347 return (0);
348 }
349
350 len -= off;
351 npref = ntohs(iap->numprefix);
352
353 for (i = 0; i < npref; i++) {
354 rv = lsa_get_prefix(buf + off, len, NULL);
355 if (rv == -1) {
356 log_warnx("lsa_intra_a_pref_check: "
357 "invalid LSA intra area prefix packet");
358 return (0);
359 }
360 off += rv;
361 len -= rv;
362 }
363
364 return (1);
365 }
366
367 int
lsa_asext_check(struct lsa * lsa,u_int16_t len)368 lsa_asext_check(struct lsa *lsa, u_int16_t len)
369 {
370 char *buf = (char *)lsa;
371 struct lsa_asext *asext;
372 struct in6_addr fw_addr;
373 u_int32_t metric;
374 u_int16_t ref_ls_type;
375 int rv;
376 u_int16_t total_len;
377
378 asext = (struct lsa_asext *)(buf + sizeof(lsa->hdr));
379
380 if ((len % sizeof(u_int32_t)) ||
381 len < sizeof(lsa->hdr) + sizeof(*asext)) {
382 log_warnx("lsa_asext_check: bad LSA as-external packet size");
383 return (0);
384 }
385
386 total_len = sizeof(lsa->hdr) + sizeof(*asext);
387 rv = lsa_get_prefix(&asext->prefix, len, NULL);
388 if (rv == -1) {
389 log_warnx("lsa_asext_check: bad LSA as-external packet");
390 return (0);
391 }
392 total_len += rv - sizeof(struct lsa_prefix);
393
394 metric = ntohl(asext->metric);
395 if (metric & LSA_ASEXT_F_FLAG) {
396 if (total_len + sizeof(fw_addr) < len) {
397 bcopy(buf + total_len, &fw_addr, sizeof(fw_addr));
398 if (IN6_IS_ADDR_UNSPECIFIED(&fw_addr) ||
399 IN6_IS_ADDR_LINKLOCAL(&fw_addr)) {
400 log_warnx("lsa_asext_check: bad LSA "
401 "as-external forwarding address");
402 return (0);
403 }
404 }
405 total_len += sizeof(fw_addr);
406 }
407
408 if (metric & LSA_ASEXT_T_FLAG)
409 total_len += sizeof(u_int32_t);
410
411 ref_ls_type = asext->prefix.metric;
412 if (ref_ls_type != 0)
413 total_len += sizeof(u_int32_t);
414
415 if (len != total_len) {
416 log_warnx("lsa_asext_check: bad LSA as-external length");
417 return (0);
418 }
419
420 return (1);
421 }
422
423 int
lsa_self(struct rde_nbr * nbr,struct lsa * lsa,struct vertex * v)424 lsa_self(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
425 {
426 struct lsa *dummy;
427
428 if (nbr->self)
429 return (0);
430
431 if (rde_router_id() != lsa->hdr.adv_rtr)
432 return (0);
433
434 if (v == NULL) {
435 /* LSA is no longer announced, remove by premature aging.
436 * The LSA may not be altered because the caller may still
437 * use it, so a copy needs to be added to the LSDB.
438 * The copy will be reflooded via the default timeout handler.
439 */
440 if ((dummy = malloc(ntohs(lsa->hdr.len))) == NULL)
441 fatal("lsa_self");
442 memcpy(dummy, lsa, ntohs(lsa->hdr.len));
443 dummy->hdr.age = htons(MAX_AGE);
444 /*
445 * The clue is that by using the remote nbr as originator
446 * the dummy LSA will be reflooded via the default timeout
447 * handler.
448 */
449 (void)lsa_add(rde_nbr_self(nbr->area), dummy);
450 return (1);
451 }
452
453 /*
454 * LSA is still originated, just reflood it. But we need to create
455 * a new instance by setting the LSA sequence number equal to the
456 * one of new and calling lsa_refresh(). Flooding will be done by the
457 * caller.
458 */
459 v->lsa->hdr.seq_num = lsa->hdr.seq_num;
460 lsa_refresh(v);
461 return (1);
462 }
463
464 int
lsa_add(struct rde_nbr * nbr,struct lsa * lsa)465 lsa_add(struct rde_nbr *nbr, struct lsa *lsa)
466 {
467 struct lsa_tree *tree;
468 struct vertex *new, *old;
469 struct timeval tv, now, res;
470 int update = 1;
471
472 if (LSA_IS_SCOPE_AS(ntohs(lsa->hdr.type)))
473 tree = &asext_tree;
474 else if (LSA_IS_SCOPE_AREA(ntohs(lsa->hdr.type)))
475 tree = &nbr->area->lsa_tree;
476 else if (LSA_IS_SCOPE_LLOCAL(ntohs(lsa->hdr.type)))
477 tree = &nbr->iface->lsa_tree;
478 else
479 fatalx("%s: unknown scope type", __func__);
480
481 new = vertex_get(lsa, nbr, tree);
482 old = RB_INSERT(lsa_tree, tree, new);
483
484 if (old != NULL) {
485 if (old->deleted && evtimer_pending(&old->ev, &tv)) {
486 /* new update added before hold time expired */
487 gettimeofday(&now, NULL);
488 timersub(&tv, &now, &res);
489
490 /* remove old LSA and insert new LSA with delay */
491 vertex_free(old);
492 RB_INSERT(lsa_tree, tree, new);
493 new->deleted = 1;
494
495 if (evtimer_add(&new->ev, &res) != 0)
496 fatal("lsa_add");
497 return (1);
498 }
499 if (lsa_equal(new->lsa, old->lsa))
500 update = 0;
501 vertex_free(old);
502 RB_INSERT(lsa_tree, tree, new);
503 }
504
505 if (update) {
506 if (ntohs(lsa->hdr.type) == LSA_TYPE_LINK)
507 orig_intra_area_prefix_lsas(nbr->area);
508 if (ntohs(lsa->hdr.type) != LSA_TYPE_EXTERNAL)
509 nbr->area->dirty = 1;
510 start_spf_timer();
511 }
512
513 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */
514 timerclear(&tv);
515
516 if (nbr->self && ntohs(new->lsa->hdr.age) == DEFAULT_AGE)
517 tv.tv_sec = LS_REFRESH_TIME;
518 else
519 tv.tv_sec = MAX_AGE - ntohs(new->lsa->hdr.age);
520
521 if (evtimer_add(&new->ev, &tv) != 0)
522 fatal("lsa_add: evtimer_add()");
523 return (0);
524 }
525
526 void
lsa_del(struct rde_nbr * nbr,struct lsa_hdr * lsa)527 lsa_del(struct rde_nbr *nbr, struct lsa_hdr *lsa)
528 {
529 struct vertex *v;
530 struct timeval tv;
531
532 v = lsa_find(nbr->iface, lsa->type, lsa->ls_id, lsa->adv_rtr);
533 if (v == NULL)
534 return;
535
536 v->deleted = 1;
537 /* hold time to make sure that a new lsa is not added premature */
538 timerclear(&tv);
539 tv.tv_sec = MIN_LS_INTERVAL;
540 if (evtimer_add(&v->ev, &tv) == -1)
541 fatal("lsa_del");
542 }
543
544 void
lsa_age(struct vertex * v)545 lsa_age(struct vertex *v)
546 {
547 struct timespec tp;
548 time_t now;
549 int d;
550 u_int16_t age;
551
552 clock_gettime(CLOCK_MONOTONIC, &tp);
553 now = tp.tv_sec;
554
555 d = now - v->stamp;
556 /* set stamp so that at least new calls work */
557 v->stamp = now;
558
559 if (d < 0) {
560 log_warnx("lsa_age: time went backwards");
561 return;
562 }
563
564 age = ntohs(v->lsa->hdr.age);
565 if (age + d > MAX_AGE)
566 age = MAX_AGE;
567 else
568 age += d;
569
570 v->lsa->hdr.age = htons(age);
571 }
572
573 struct vertex *
lsa_find(struct iface * iface,u_int16_t type,u_int32_t ls_id,u_int32_t adv_rtr)574 lsa_find(struct iface *iface, u_int16_t type, u_int32_t ls_id,
575 u_int32_t adv_rtr)
576 {
577 struct lsa_tree *tree;
578
579 if (LSA_IS_SCOPE_AS(ntohs(type)))
580 tree = &asext_tree;
581 else if (LSA_IS_SCOPE_AREA(ntohs(type)))
582 tree = &iface->area->lsa_tree;
583 else if (LSA_IS_SCOPE_LLOCAL(ntohs(type)))
584 tree = &iface->lsa_tree;
585 else
586 fatalx("unknown scope type");
587
588 return lsa_find_tree(tree, type, ls_id, adv_rtr);
589
590 }
591
592 struct vertex *
lsa_find_tree(struct lsa_tree * tree,u_int16_t type,u_int32_t ls_id,u_int32_t adv_rtr)593 lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id,
594 u_int32_t adv_rtr)
595 {
596 struct vertex key;
597 struct vertex *v;
598
599 key.ls_id = ntohl(ls_id);
600 key.adv_rtr = ntohl(adv_rtr);
601 key.type = ntohs(type);
602
603 v = RB_FIND(lsa_tree, tree, &key);
604
605 /* LSA that are deleted are not findable */
606 if (v && v->deleted)
607 return (NULL);
608
609 if (v)
610 lsa_age(v);
611
612 return (v);
613 }
614
615 struct vertex *
lsa_find_rtr(struct area * area,u_int32_t rtr_id)616 lsa_find_rtr(struct area *area, u_int32_t rtr_id)
617 {
618 return lsa_find_rtr_frag(area, rtr_id, 0);
619 }
620
621 struct vertex *
lsa_find_rtr_frag(struct area * area,u_int32_t rtr_id,unsigned int n)622 lsa_find_rtr_frag(struct area *area, u_int32_t rtr_id, unsigned int n)
623 {
624 struct vertex *v;
625 struct vertex key;
626 unsigned int i;
627
628 key.ls_id = 0;
629 key.adv_rtr = ntohl(rtr_id);
630 key.type = LSA_TYPE_ROUTER;
631
632 i = 0;
633 v = RB_NFIND(lsa_tree, &area->lsa_tree, &key);
634 while (v) {
635 if (v->type != LSA_TYPE_ROUTER ||
636 v->adv_rtr != ntohl(rtr_id)) {
637 /* no more interesting LSAs */
638 v = NULL;
639 break;
640 }
641 if (!v->deleted) {
642 if (i >= n)
643 break;
644 i++;
645 }
646 v = RB_NEXT(lsa_tree, &area->lsa_tree, v);
647 }
648
649 if (v) {
650 if (i == n)
651 lsa_age(v);
652 else
653 v = NULL;
654 }
655
656 return (v);
657 }
658
659 u_int32_t
lsa_find_lsid(struct lsa_tree * tree,int (* cmp)(struct lsa *,struct lsa *),struct lsa * lsa)660 lsa_find_lsid(struct lsa_tree *tree, int (*cmp)(struct lsa *, struct lsa *),
661 struct lsa *lsa)
662 {
663 #define MIN(x, y) ((x) < (y) ? (x) : (y))
664 struct vertex *v;
665 struct vertex key;
666 u_int32_t min, cur;
667
668 key.ls_id = 0;
669 key.adv_rtr = ntohl(lsa->hdr.adv_rtr);
670 key.type = ntohs(lsa->hdr.type);
671
672 cur = 0;
673 min = 0xffffffffU;
674 v = RB_NFIND(lsa_tree, tree, &key);
675 while (v) {
676 if (v->type != key.type ||
677 v->adv_rtr != key.adv_rtr) {
678 /* no more interesting LSAs */
679 min = MIN(min, cur + 1);
680 return (htonl(min));
681 }
682 if (cmp(lsa, v->lsa) == 0) {
683 /* match, return this ls_id */
684 return (htonl(v->ls_id));
685 }
686 if (v->ls_id > cur + 1)
687 min = cur + 1;
688 cur = v->ls_id;
689 if (cur + 1 < cur)
690 fatalx("King Bula sez: somebody got to many LSA");
691 v = RB_NEXT(lsa_tree, tree, v);
692 }
693 min = MIN(min, cur + 1);
694 return (htonl(min));
695 #undef MIN
696 }
697
698 u_int16_t
lsa_num_links(struct vertex * v)699 lsa_num_links(struct vertex *v)
700 {
701 unsigned int n = 1;
702 u_int16_t nlinks = 0;
703
704 switch (v->type) {
705 case LSA_TYPE_ROUTER:
706 do {
707 nlinks += ((ntohs(v->lsa->hdr.len) -
708 sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) /
709 sizeof(struct lsa_rtr_link));
710 v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), n++);
711 } while (v);
712 return nlinks;
713 case LSA_TYPE_NETWORK:
714 return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) -
715 sizeof(struct lsa_net)) / sizeof(struct lsa_net_link));
716 default:
717 fatalx("lsa_num_links: invalid LSA type");
718 }
719
720 return (0);
721 }
722
723 void
lsa_snap(struct rde_nbr * nbr)724 lsa_snap(struct rde_nbr *nbr)
725 {
726 struct lsa_tree *tree = &nbr->area->lsa_tree;
727 struct vertex *v;
728
729 do {
730 RB_FOREACH(v, lsa_tree, tree) {
731 if (v->deleted)
732 continue;
733 lsa_age(v);
734 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) {
735 rde_imsg_compose_ospfe(IMSG_LS_SNAP,
736 nbr->peerid, 0, &v->lsa->hdr,
737 ntohs(v->lsa->hdr.len));
738 } else {
739 rde_imsg_compose_ospfe(IMSG_DB_SNAPSHOT,
740 nbr->peerid, 0, &v->lsa->hdr,
741 sizeof(struct lsa_hdr));
742 }
743 }
744 if (tree == &asext_tree)
745 break;
746 if (tree == &nbr->area->lsa_tree)
747 tree = &nbr->iface->lsa_tree;
748 else
749 tree = &asext_tree;
750 } while (1);
751 }
752
753 void
lsa_dump(struct lsa_tree * tree,int imsg_type,pid_t pid)754 lsa_dump(struct lsa_tree *tree, int imsg_type, pid_t pid)
755 {
756 struct vertex *v;
757
758 RB_FOREACH(v, lsa_tree, tree) {
759 if (v->deleted)
760 continue;
761 lsa_age(v);
762 switch (imsg_type) {
763 case IMSG_CTL_SHOW_DATABASE:
764 break;
765 case IMSG_CTL_SHOW_DB_SELF:
766 if (v->lsa->hdr.adv_rtr == rde_router_id())
767 break;
768 continue;
769 case IMSG_CTL_SHOW_DB_EXT:
770 if (v->type == LSA_TYPE_EXTERNAL)
771 break;
772 continue;
773 case IMSG_CTL_SHOW_DB_LINK:
774 if (v->type == LSA_TYPE_LINK)
775 break;
776 continue;
777 case IMSG_CTL_SHOW_DB_NET:
778 if (v->type == LSA_TYPE_NETWORK)
779 break;
780 continue;
781 case IMSG_CTL_SHOW_DB_RTR:
782 if (v->type == LSA_TYPE_ROUTER)
783 break;
784 continue;
785 case IMSG_CTL_SHOW_DB_INTRA:
786 if (v->type == LSA_TYPE_INTRA_A_PREFIX)
787 break;
788 continue;
789 case IMSG_CTL_SHOW_DB_SUM:
790 if (v->type == LSA_TYPE_INTER_A_PREFIX)
791 break;
792 continue;
793 case IMSG_CTL_SHOW_DB_ASBR:
794 if (v->type == LSA_TYPE_INTER_A_ROUTER)
795 break;
796 continue;
797 default:
798 log_warnx("lsa_dump: unknown imsg type");
799 return;
800 }
801 rde_imsg_compose_ospfe(imsg_type, 0, pid, &v->lsa->hdr,
802 ntohs(v->lsa->hdr.len));
803 }
804 }
805
806 void
lsa_timeout(int fd,short event,void * bula)807 lsa_timeout(int fd, short event, void *bula)
808 {
809 struct vertex *v = bula;
810 struct timeval tv;
811
812 lsa_age(v);
813
814 if (v->deleted) {
815 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) {
816 vertex_free(v);
817 } else {
818 v->deleted = 0;
819
820 /* schedule recalculation of the RIB */
821 if (ntohs(v->lsa->hdr.type) == LSA_TYPE_LINK)
822 orig_intra_area_prefix_lsas(v->area);
823 if (ntohs(v->lsa->hdr.type) != LSA_TYPE_EXTERNAL)
824 v->area->dirty = 1;
825 start_spf_timer();
826
827 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
828 v->lsa, ntohs(v->lsa->hdr.len));
829
830 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */
831 timerclear(&tv);
832 if (v->self)
833 tv.tv_sec = LS_REFRESH_TIME;
834 else
835 tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age);
836
837 if (evtimer_add(&v->ev, &tv) != 0)
838 fatal("lsa_timeout");
839 }
840 return;
841 }
842
843 if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE)
844 lsa_refresh(v);
845
846 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
847 v->lsa, ntohs(v->lsa->hdr.len));
848 }
849
850 void
lsa_refresh(struct vertex * v)851 lsa_refresh(struct vertex *v)
852 {
853 struct timeval tv;
854 struct timespec tp;
855 u_int32_t seqnum;
856 u_int16_t len;
857
858 /* refresh LSA by increasing sequence number by one */
859 if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE)
860 /* self originated network that is currently beeing removed */
861 v->lsa->hdr.age = htons(MAX_AGE);
862 else
863 v->lsa->hdr.age = htons(DEFAULT_AGE);
864 seqnum = ntohl(v->lsa->hdr.seq_num);
865 if (seqnum++ == MAX_SEQ_NUM)
866 /* XXX fix me */
867 fatalx("sequence number wrapping");
868 v->lsa->hdr.seq_num = htonl(seqnum);
869
870 /* recalculate checksum */
871 len = ntohs(v->lsa->hdr.len);
872 v->lsa->hdr.ls_chksum = 0;
873 v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET));
874
875 clock_gettime(CLOCK_MONOTONIC, &tp);
876 v->changed = v->stamp = tp.tv_sec;
877
878 timerclear(&tv);
879 tv.tv_sec = LS_REFRESH_TIME;
880 if (evtimer_add(&v->ev, &tv) == -1)
881 fatal("lsa_refresh");
882 }
883
884 void
lsa_merge(struct rde_nbr * nbr,struct lsa * lsa,struct vertex * v)885 lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
886 {
887 struct timeval tv;
888 struct timespec tp;
889 time_t now;
890 u_int16_t len;
891
892 if (v == NULL) {
893 if (lsa_add(nbr, lsa))
894 /* delayed update */
895 return;
896 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0,
897 lsa, ntohs(lsa->hdr.len));
898 return;
899 }
900
901 /* set the seq_num to the current one. lsa_refresh() will do the ++ */
902 lsa->hdr.seq_num = v->lsa->hdr.seq_num;
903 /* recalculate checksum */
904 len = ntohs(lsa->hdr.len);
905 lsa->hdr.ls_chksum = 0;
906 lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET));
907
908 /* compare LSA most header fields are equal so don't check them */
909 if (lsa_equal(lsa, v->lsa)) {
910 free(lsa);
911 return;
912 }
913
914 /* overwrite the lsa all other fields are unaffected */
915 free(v->lsa);
916 v->lsa = lsa;
917 if (v->type == LSA_TYPE_LINK)
918 orig_intra_area_prefix_lsas(nbr->area);
919 if (v->type != LSA_TYPE_EXTERNAL)
920 nbr->area->dirty = 1;
921 start_spf_timer();
922
923 /* set correct timeout for reflooding the LSA */
924 clock_gettime(CLOCK_MONOTONIC, &tp);
925 now = tp.tv_sec;
926 timerclear(&tv);
927 if (v->changed + MIN_LS_INTERVAL >= now)
928 tv.tv_sec = MIN_LS_INTERVAL;
929 if (evtimer_add(&v->ev, &tv) == -1)
930 fatal("lsa_merge");
931 }
932
933 void
lsa_remove_invalid_sums(struct area * area)934 lsa_remove_invalid_sums(struct area *area)
935 {
936 struct lsa_tree *tree = &area->lsa_tree;
937 struct vertex *v, *nv;
938
939 /* XXX speed me up */
940 for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) {
941 nv = RB_NEXT(lsa_tree, tree, v);
942 if ((v->type == LSA_TYPE_INTER_A_PREFIX ||
943 v->type == LSA_TYPE_INTER_A_ROUTER) &&
944 v->self && v->cost == LS_INFINITY &&
945 v->deleted == 0) {
946 /*
947 * age the lsa and call lsa_timeout() which will
948 * actually remove it from the database.
949 */
950 v->lsa->hdr.age = htons(MAX_AGE);
951 lsa_timeout(0, 0, v);
952 }
953 }
954 }
955
956 int
lsa_equal(struct lsa * a,struct lsa * b)957 lsa_equal(struct lsa *a, struct lsa *b)
958 {
959 /*
960 * compare LSA that already have same type, adv_rtr and ls_id
961 * so not all header need to be compared
962 */
963 if (a == NULL || b == NULL)
964 return (0);
965 if (a->hdr.len != b->hdr.len)
966 return (0);
967 /* LSAs with age MAX_AGE are never equal */
968 if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE))
969 return (0);
970 if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) -
971 sizeof(struct lsa_hdr)))
972 return (0);
973
974 return (1);
975 }
976
977 int
lsa_get_prefix(void * buf,u_int16_t len,struct rt_prefix * p)978 lsa_get_prefix(void *buf, u_int16_t len, struct rt_prefix *p)
979 {
980 struct lsa_prefix *lp = buf;
981 u_int32_t *buf32, *addr = NULL;
982 u_int8_t prefixlen;
983 u_int16_t consumed;
984
985 if (len < sizeof(*lp))
986 return (-1);
987
988 prefixlen = lp->prefixlen;
989
990 if (p) {
991 bzero(p, sizeof(*p));
992 p->prefixlen = lp->prefixlen;
993 p->options = lp->options;
994 p->metric = ntohs(lp->metric);
995 addr = (u_int32_t *)&p->prefix;
996 }
997
998 buf32 = (u_int32_t *)(lp + 1);
999 consumed = sizeof(*lp);
1000
1001 for (prefixlen = LSA_PREFIXSIZE(prefixlen) / sizeof(u_int32_t);
1002 prefixlen > 0; prefixlen--) {
1003 if (len < consumed + sizeof(u_int32_t))
1004 return (-1);
1005 if (addr)
1006 *addr++ = *buf32++;
1007 consumed += sizeof(u_int32_t);
1008 }
1009
1010 return (consumed);
1011 }
1012