1 /* $OpenBSD: rde_lsdb.c,v 1.52 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 "ospf.h"
26 #include "ospfd.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_router_check(struct lsa *, u_int16_t);
33 struct vertex *lsa_find_tree(struct lsa_tree *, u_int16_t, u_int32_t,
34 u_int32_t);
35 void lsa_timeout(int, short, void *);
36 void lsa_refresh(struct vertex *);
37 int lsa_equal(struct lsa *, struct lsa *);
38
RB_GENERATE(lsa_tree,vertex,entry,lsa_compare)39 RB_GENERATE(lsa_tree, vertex, entry, lsa_compare)
40
41 void
42 lsa_init(struct lsa_tree *t)
43 {
44 RB_INIT(t);
45 }
46
47 int
lsa_compare(struct vertex * a,struct vertex * b)48 lsa_compare(struct vertex *a, struct vertex *b)
49 {
50 if (a->type < b->type)
51 return (-1);
52 if (a->type > b->type)
53 return (1);
54 if (a->adv_rtr < b->adv_rtr)
55 return (-1);
56 if (a->adv_rtr > b->adv_rtr)
57 return (1);
58 if (a->ls_id < b->ls_id)
59 return (-1);
60 if (a->ls_id > b->ls_id)
61 return (1);
62 return (0);
63 }
64
65
66 struct vertex *
vertex_get(struct lsa * lsa,struct rde_nbr * nbr,struct lsa_tree * tree)67 vertex_get(struct lsa *lsa, struct rde_nbr *nbr, struct lsa_tree *tree)
68 {
69 struct vertex *v;
70 struct timespec tp;
71
72 if ((v = calloc(1, sizeof(struct vertex))) == NULL)
73 fatal(NULL);
74 TAILQ_INIT(&v->nexthop);
75 v->area = nbr->area;
76 v->peerid = nbr->peerid;
77 v->lsa = lsa;
78 clock_gettime(CLOCK_MONOTONIC, &tp);
79 v->changed = v->stamp = tp.tv_sec;
80 v->cost = LS_INFINITY;
81 v->ls_id = ntohl(lsa->hdr.ls_id);
82 v->adv_rtr = ntohl(lsa->hdr.adv_rtr);
83 v->type = lsa->hdr.type;
84 v->lsa_tree = tree;
85
86 if (!nbr->self)
87 v->flooded = 1; /* XXX fix me */
88 v->self = nbr->self;
89
90 evtimer_set(&v->ev, lsa_timeout, v);
91
92 return (v);
93 }
94
95 void
vertex_free(struct vertex * v)96 vertex_free(struct vertex *v)
97 {
98 RB_REMOVE(lsa_tree, v->lsa_tree, v);
99
100 (void)evtimer_del(&v->ev);
101 vertex_nexthop_clear(v);
102 free(v->lsa);
103 free(v);
104 }
105
106 void
vertex_nexthop_clear(struct vertex * v)107 vertex_nexthop_clear(struct vertex *v)
108 {
109 struct v_nexthop *vn;
110
111 while ((vn = TAILQ_FIRST(&v->nexthop))) {
112 TAILQ_REMOVE(&v->nexthop, vn, entry);
113 free(vn);
114 }
115 }
116
117 void
vertex_nexthop_add(struct vertex * dst,struct vertex * parent,u_int32_t nexthop)118 vertex_nexthop_add(struct vertex *dst, struct vertex *parent, u_int32_t nexthop)
119 {
120 struct v_nexthop *vn;
121
122 if ((vn = calloc(1, sizeof(*vn))) == NULL)
123 fatal("vertex_nexthop_add");
124
125 vn->prev = parent;
126 vn->nexthop.s_addr = nexthop;
127
128 TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry);
129 }
130
131 /* returns -1 if a is older, 1 if newer and 0 if equal to b */
132 int
lsa_newer(struct lsa_hdr * a,struct lsa_hdr * b)133 lsa_newer(struct lsa_hdr *a, struct lsa_hdr *b)
134 {
135 int32_t a32, b32;
136 u_int16_t a16, b16;
137 int i;
138
139 if (a == NULL)
140 return (-1);
141 if (b == NULL)
142 return (1);
143
144 /*
145 * The sequence number is defined as signed 32-bit integer,
146 * no idea how IETF came up with such a stupid idea.
147 */
148 a32 = (int32_t)ntohl(a->seq_num);
149 b32 = (int32_t)ntohl(b->seq_num);
150
151 if (a32 > b32)
152 return (1);
153 if (a32 < b32)
154 return (-1);
155
156 a16 = ntohs(a->ls_chksum);
157 b16 = ntohs(b->ls_chksum);
158
159 if (a16 > b16)
160 return (1);
161 if (a16 < b16)
162 return (-1);
163
164 a16 = ntohs(a->age);
165 b16 = ntohs(b->age);
166
167 if (a16 >= MAX_AGE && b16 >= MAX_AGE)
168 return (0);
169 if (b16 >= MAX_AGE)
170 return (-1);
171 if (a16 >= MAX_AGE)
172 return (1);
173
174 i = b16 - a16;
175 if (abs(i) > MAX_AGE_DIFF)
176 return (i > 0 ? 1 : -1);
177
178 return (0);
179 }
180
181 int
lsa_check(struct rde_nbr * nbr,struct lsa * lsa,u_int16_t len)182 lsa_check(struct rde_nbr *nbr, struct lsa *lsa, u_int16_t len)
183 {
184 struct area *area = nbr->area;
185 u_int32_t metric;
186
187 if (len < sizeof(lsa->hdr)) {
188 log_warnx("lsa_check: bad packet size");
189 return (0);
190 }
191 if (ntohs(lsa->hdr.len) != len) {
192 log_warnx("lsa_check: bad packet size");
193 return (0);
194 }
195
196 if (iso_cksum(lsa, len, 0)) {
197 log_warnx("lsa_check: bad packet checksum");
198 return (0);
199 }
200
201 /* invalid ages */
202 if ((ntohs(lsa->hdr.age) < 1 && !nbr->self) ||
203 ntohs(lsa->hdr.age) > MAX_AGE) {
204 log_warnx("lsa_check: bad age");
205 return (0);
206 }
207
208 /* invalid sequence number */
209 if (ntohl(lsa->hdr.seq_num) == RESV_SEQ_NUM) {
210 log_warnx("ls_check: bad seq num");
211 return (0);
212 }
213
214 switch (lsa->hdr.type) {
215 case LSA_TYPE_ROUTER:
216 if (!lsa_router_check(lsa, len))
217 return (0);
218 break;
219 case LSA_TYPE_NETWORK:
220 if ((len % sizeof(u_int32_t)) ||
221 len < sizeof(lsa->hdr) + sizeof(u_int32_t)) {
222 log_warnx("lsa_check: bad LSA network packet");
223 return (0);
224 }
225 break;
226 case LSA_TYPE_SUM_NETWORK:
227 case LSA_TYPE_SUM_ROUTER:
228 if ((len % sizeof(u_int32_t)) ||
229 len < sizeof(lsa->hdr) + sizeof(lsa->data.sum)) {
230 log_warnx("lsa_check: bad LSA summary packet");
231 return (0);
232 }
233 metric = ntohl(lsa->data.sum.metric);
234 if (metric & ~LSA_METRIC_MASK) {
235 log_warnx("lsa_check: bad LSA summary metric");
236 return (0);
237 }
238 break;
239 case LSA_TYPE_EXTERNAL:
240 if ((len % (3 * sizeof(u_int32_t))) ||
241 len < sizeof(lsa->hdr) + sizeof(lsa->data.asext)) {
242 log_warnx("lsa_check: bad LSA as-external packet");
243 return (0);
244 }
245 metric = ntohl(lsa->data.asext.metric);
246 if (metric & ~(LSA_METRIC_MASK | LSA_ASEXT_E_FLAG)) {
247 log_warnx("lsa_check: bad LSA as-external metric");
248 return (0);
249 }
250 /* AS-external-LSA are silently discarded in stub areas */
251 if (area->stub)
252 return (0);
253 break;
254 case LSA_TYPE_LINK_OPAQ:
255 case LSA_TYPE_AREA_OPAQ:
256 case LSA_TYPE_AS_OPAQ:
257 if (len % sizeof(u_int32_t)) {
258 log_warnx("lsa_check: bad opaque LSA packet");
259 return (0);
260 }
261 /* Type-11 Opaque-LSA are silently discarded in stub areas */
262 if (lsa->hdr.type == LSA_TYPE_AS_OPAQ && area->stub)
263 return (0);
264 break;
265 default:
266 log_warnx("lsa_check: unknown type %u", lsa->hdr.type);
267 return (0);
268 }
269
270 /* MaxAge handling */
271 if (lsa->hdr.age == htons(MAX_AGE) && !nbr->self && lsa_find(nbr->iface,
272 lsa->hdr.type, lsa->hdr.ls_id, lsa->hdr.adv_rtr) == NULL &&
273 !rde_nbr_loading(area)) {
274 /*
275 * if no neighbor in state Exchange or Loading
276 * ack LSA but don't add it. Needs to be a direct ack.
277 */
278 rde_imsg_compose_ospfe(IMSG_LS_ACK, nbr->peerid, 0, &lsa->hdr,
279 sizeof(struct lsa_hdr));
280 return (0);
281 }
282
283 return (1);
284 }
285
286 int
lsa_router_check(struct lsa * lsa,u_int16_t len)287 lsa_router_check(struct lsa *lsa, u_int16_t len)
288 {
289 struct lsa_rtr_link *rtr_link;
290 char *buf = (char *)lsa;
291 u_int16_t i, off, nlinks;
292
293 off = sizeof(lsa->hdr) + sizeof(struct lsa_rtr);
294 if (off > len) {
295 log_warnx("lsa_check: invalid LSA router packet");
296 return (0);
297 }
298
299 if (lsa->hdr.ls_id != lsa->hdr.adv_rtr) {
300 log_warnx("lsa_check: invalid LSA router packet, bad adv_rtr");
301 return (0);
302 }
303
304 nlinks = ntohs(lsa->data.rtr.nlinks);
305 if (nlinks == 0) {
306 log_warnx("lsa_check: invalid LSA router packet");
307 return (0);
308 }
309 for (i = 0; i < nlinks; i++) {
310 rtr_link = (struct lsa_rtr_link *)(buf + off);
311 off += sizeof(struct lsa_rtr_link);
312 if (off > len) {
313 log_warnx("lsa_check: invalid LSA router packet");
314 return (0);
315 }
316 off += rtr_link->num_tos * sizeof(u_int32_t);
317 if (off > len) {
318 log_warnx("lsa_check: invalid LSA router packet");
319 return (0);
320 }
321 }
322
323 if (i != nlinks) {
324 log_warnx("lsa_check: invalid LSA router packet");
325 return (0);
326 }
327 return (1);
328 }
329
330 int
lsa_self(struct rde_nbr * nbr,struct lsa * new,struct vertex * v)331 lsa_self(struct rde_nbr *nbr, struct lsa *new, struct vertex *v)
332 {
333 struct iface *iface;
334 struct lsa *dummy;
335
336 if (nbr->self)
337 return (0);
338
339 if (rde_router_id() == new->hdr.adv_rtr)
340 goto self;
341
342 if (new->hdr.type == LSA_TYPE_NETWORK)
343 LIST_FOREACH(iface, &nbr->area->iface_list, entry)
344 if (iface->addr.s_addr == new->hdr.ls_id)
345 goto self;
346
347 return (0);
348
349 self:
350 if (v == NULL) {
351 /*
352 * LSA is no longer announced, remove by premature aging.
353 * The problem is that new may not be altered so a copy
354 * needs to be added to the LSA DB first.
355 */
356 if ((dummy = malloc(ntohs(new->hdr.len))) == NULL)
357 fatal("lsa_self");
358 memcpy(dummy, new, ntohs(new->hdr.len));
359 dummy->hdr.age = htons(MAX_AGE);
360 /*
361 * The clue is that by using the remote nbr as originator
362 * the dummy LSA will be reflooded via the default timeout
363 * handler.
364 */
365 (void)lsa_add(rde_nbr_self(nbr->area), dummy);
366 return (1);
367 }
368
369 /*
370 * LSA is still originated, just reflood it. But we need to create
371 * a new instance by setting the LSA sequence number equal to the
372 * one of new and calling lsa_refresh(). Flooding will be done by the
373 * caller.
374 */
375 v->lsa->hdr.seq_num = new->hdr.seq_num;
376 lsa_refresh(v);
377 return (1);
378 }
379
380 int
lsa_add(struct rde_nbr * nbr,struct lsa * lsa)381 lsa_add(struct rde_nbr *nbr, struct lsa *lsa)
382 {
383 struct lsa_tree *tree;
384 struct vertex *new, *old;
385 struct timeval tv, now, res;
386 int update = 1;
387
388 if (lsa->hdr.type == LSA_TYPE_EXTERNAL ||
389 lsa->hdr.type == LSA_TYPE_AS_OPAQ)
390 tree = &asext_tree;
391 else if (lsa->hdr.type == LSA_TYPE_LINK_OPAQ)
392 tree = &nbr->iface->lsa_tree;
393 else
394 tree = &nbr->area->lsa_tree;
395
396 new = vertex_get(lsa, nbr, tree);
397 old = RB_INSERT(lsa_tree, tree, new);
398
399 if (old != NULL) {
400 if (old->deleted && evtimer_pending(&old->ev, &tv)) {
401 /* new update added before hold time expired */
402 gettimeofday(&now, NULL);
403 timersub(&tv, &now, &res);
404
405 /* remove old LSA and insert new LSA with delay */
406 vertex_free(old);
407 RB_INSERT(lsa_tree, tree, new);
408 new->deleted = 1;
409
410 if (evtimer_add(&new->ev, &res) != 0)
411 fatal("lsa_add");
412 return (1);
413 }
414 if (lsa_equal(new->lsa, old->lsa))
415 update = 0;
416 vertex_free(old);
417 RB_INSERT(lsa_tree, tree, new);
418 }
419
420 if (update) {
421 if (lsa->hdr.type != LSA_TYPE_EXTERNAL &&
422 lsa->hdr.type != LSA_TYPE_AS_OPAQ)
423 nbr->area->dirty = 1;
424 start_spf_timer();
425 }
426
427 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */
428 timerclear(&tv);
429
430 if (nbr->self && ntohs(new->lsa->hdr.age) == DEFAULT_AGE)
431 tv.tv_sec = LS_REFRESH_TIME;
432 else
433 tv.tv_sec = MAX_AGE - ntohs(new->lsa->hdr.age);
434
435 if (evtimer_add(&new->ev, &tv) != 0)
436 fatal("lsa_add");
437 return (0);
438 }
439
440 void
lsa_del(struct rde_nbr * nbr,struct lsa_hdr * lsa)441 lsa_del(struct rde_nbr *nbr, struct lsa_hdr *lsa)
442 {
443 struct vertex *v;
444 struct timeval tv;
445
446 v = lsa_find(nbr->iface, lsa->type, lsa->ls_id, lsa->adv_rtr);
447 if (v == NULL)
448 return;
449
450 v->deleted = 1;
451 /* hold time to make sure that a new lsa is not added premature */
452 timerclear(&tv);
453 tv.tv_sec = MIN_LS_INTERVAL;
454 if (evtimer_add(&v->ev, &tv) == -1)
455 fatal("lsa_del");
456 }
457
458 void
lsa_age(struct vertex * v)459 lsa_age(struct vertex *v)
460 {
461 struct timespec tp;
462 time_t now;
463 int d;
464 u_int16_t age;
465
466 clock_gettime(CLOCK_MONOTONIC, &tp);
467 now = tp.tv_sec;
468
469 d = now - v->stamp;
470 /* set stamp so that at least new calls work */
471 v->stamp = now;
472
473 if (d < 0) {
474 log_warnx("lsa_age: time went backwards");
475 return;
476 }
477
478 age = ntohs(v->lsa->hdr.age);
479 if (age + d > MAX_AGE)
480 age = MAX_AGE;
481 else
482 age += d;
483
484 v->lsa->hdr.age = htons(age);
485 }
486
487 struct vertex *
lsa_find(struct iface * iface,u_int8_t type,u_int32_t ls_id,u_int32_t adv_rtr)488 lsa_find(struct iface *iface, u_int8_t type, u_int32_t ls_id, u_int32_t adv_rtr)
489 {
490 struct lsa_tree *tree;
491
492 if (type == LSA_TYPE_EXTERNAL ||
493 type == LSA_TYPE_AS_OPAQ)
494 tree = &asext_tree;
495 else if (type == LSA_TYPE_LINK_OPAQ)
496 tree = &iface->lsa_tree;
497 else
498 tree = &iface->area->lsa_tree;
499
500 return lsa_find_tree(tree, type, ls_id, adv_rtr);
501 }
502
503 struct vertex *
lsa_find_area(struct area * area,u_int8_t type,u_int32_t ls_id,u_int32_t adv_rtr)504 lsa_find_area(struct area *area, u_int8_t type, u_int32_t ls_id,
505 u_int32_t adv_rtr)
506 {
507 return lsa_find_tree(&area->lsa_tree, type, ls_id, adv_rtr);
508 }
509
510 struct vertex *
lsa_find_tree(struct lsa_tree * tree,u_int16_t type,u_int32_t ls_id,u_int32_t adv_rtr)511 lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id,
512 u_int32_t adv_rtr)
513 {
514 struct vertex key;
515 struct vertex *v;
516
517 key.ls_id = ntohl(ls_id);
518 key.adv_rtr = ntohl(adv_rtr);
519 key.type = type;
520
521 v = RB_FIND(lsa_tree, tree, &key);
522
523 /* LSA that are deleted are not findable */
524 if (v && v->deleted)
525 return (NULL);
526
527 if (v)
528 lsa_age(v);
529
530 return (v);
531 }
532
533 struct vertex *
lsa_find_net(struct area * area,u_int32_t ls_id)534 lsa_find_net(struct area *area, u_int32_t ls_id)
535 {
536 struct lsa_tree *tree = &area->lsa_tree;
537 struct vertex *v;
538
539 /* XXX speed me up */
540 RB_FOREACH(v, lsa_tree, tree) {
541 if (v->lsa->hdr.type == LSA_TYPE_NETWORK &&
542 v->lsa->hdr.ls_id == ls_id) {
543 /* LSA that are deleted are not findable */
544 if (v->deleted)
545 return (NULL);
546 lsa_age(v);
547 return (v);
548 }
549 }
550
551 return (NULL);
552 }
553
554 u_int16_t
lsa_num_links(struct vertex * v)555 lsa_num_links(struct vertex *v)
556 {
557 switch (v->type) {
558 case LSA_TYPE_ROUTER:
559 return (ntohs(v->lsa->data.rtr.nlinks));
560 case LSA_TYPE_NETWORK:
561 return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr)
562 - sizeof(u_int32_t)) / sizeof(struct lsa_net_link));
563 default:
564 fatalx("lsa_num_links: invalid LSA type");
565 }
566 }
567
568 void
lsa_snap(struct rde_nbr * nbr)569 lsa_snap(struct rde_nbr *nbr)
570 {
571 struct lsa_tree *tree = &nbr->area->lsa_tree;
572 struct vertex *v;
573
574 do {
575 RB_FOREACH(v, lsa_tree, tree) {
576 if (v->deleted)
577 continue;
578 switch (v->type) {
579 case LSA_TYPE_LINK_OPAQ:
580 case LSA_TYPE_AREA_OPAQ:
581 case LSA_TYPE_AS_OPAQ:
582 if (nbr->capa_options & OSPF_OPTION_O)
583 break;
584 continue;
585 }
586 lsa_age(v);
587 if (ntohs(v->lsa->hdr.age) >= MAX_AGE)
588 rde_imsg_compose_ospfe(IMSG_LS_SNAP, nbr->peerid,
589 0, &v->lsa->hdr, ntohs(v->lsa->hdr.len));
590 else
591 rde_imsg_compose_ospfe(IMSG_DB_SNAPSHOT,
592 nbr->peerid, 0, &v->lsa->hdr,
593 sizeof(struct lsa_hdr));
594 }
595 if (tree == &asext_tree)
596 break;
597 if (tree == &nbr->area->lsa_tree)
598 tree = &nbr->iface->lsa_tree;
599 else if (nbr->area->stub)
600 break;
601 else
602 tree = &asext_tree;
603 } while (1);
604 }
605
606 void
lsa_dump(struct lsa_tree * tree,int imsg_type,pid_t pid)607 lsa_dump(struct lsa_tree *tree, int imsg_type, pid_t pid)
608 {
609 struct vertex *v;
610
611 RB_FOREACH(v, lsa_tree, tree) {
612 if (v->deleted)
613 continue;
614 lsa_age(v);
615 switch (imsg_type) {
616 case IMSG_CTL_SHOW_DATABASE:
617 break;
618 case IMSG_CTL_SHOW_DB_SELF:
619 if (v->lsa->hdr.adv_rtr == rde_router_id())
620 break;
621 continue;
622 case IMSG_CTL_SHOW_DB_EXT:
623 if (v->type == LSA_TYPE_EXTERNAL)
624 break;
625 continue;
626 case IMSG_CTL_SHOW_DB_NET:
627 if (v->type == LSA_TYPE_NETWORK)
628 break;
629 continue;
630 case IMSG_CTL_SHOW_DB_RTR:
631 if (v->type == LSA_TYPE_ROUTER)
632 break;
633 continue;
634 case IMSG_CTL_SHOW_DB_SUM:
635 if (v->type == LSA_TYPE_SUM_NETWORK)
636 break;
637 continue;
638 case IMSG_CTL_SHOW_DB_ASBR:
639 if (v->type == LSA_TYPE_SUM_ROUTER)
640 break;
641 continue;
642 case IMSG_CTL_SHOW_DB_OPAQ:
643 if (v->type == LSA_TYPE_LINK_OPAQ ||
644 v->type == LSA_TYPE_AREA_OPAQ ||
645 v->type == LSA_TYPE_AS_OPAQ)
646 break;
647 continue;
648 default:
649 log_warnx("lsa_dump: unknown imsg type");
650 return;
651 }
652 rde_imsg_compose_ospfe(imsg_type, 0, pid, &v->lsa->hdr,
653 ntohs(v->lsa->hdr.len));
654 }
655 }
656
657 void
lsa_timeout(int fd,short event,void * bula)658 lsa_timeout(int fd, short event, void *bula)
659 {
660 struct vertex *v = bula;
661 struct timeval tv;
662
663 lsa_age(v);
664
665 if (v->deleted) {
666 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) {
667 vertex_free(v);
668 } else {
669 v->deleted = 0;
670
671 /* schedule recalculation of the RIB */
672 if (v->type != LSA_TYPE_EXTERNAL &&
673 v->type != LSA_TYPE_AS_OPAQ)
674 v->area->dirty = 1;
675 start_spf_timer();
676
677 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
678 v->lsa, ntohs(v->lsa->hdr.len));
679
680 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */
681 timerclear(&tv);
682 if (v->self)
683 tv.tv_sec = LS_REFRESH_TIME;
684 else
685 tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age);
686
687 if (evtimer_add(&v->ev, &tv) != 0)
688 fatal("lsa_timeout");
689 }
690 return;
691 }
692
693 if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE)
694 lsa_refresh(v);
695
696 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
697 v->lsa, ntohs(v->lsa->hdr.len));
698 }
699
700 void
lsa_refresh(struct vertex * v)701 lsa_refresh(struct vertex *v)
702 {
703 struct timeval tv;
704 struct timespec tp;
705 u_int32_t seqnum;
706 u_int16_t len;
707
708 /* refresh LSA by increasing sequence number by one */
709 if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE)
710 /* self originated network that is currently beeing removed */
711 v->lsa->hdr.age = htons(MAX_AGE);
712 else
713 v->lsa->hdr.age = htons(DEFAULT_AGE);
714 seqnum = ntohl(v->lsa->hdr.seq_num);
715 if (seqnum++ == MAX_SEQ_NUM)
716 /* XXX fix me */
717 fatalx("sequence number wrapping");
718 v->lsa->hdr.seq_num = htonl(seqnum);
719
720 /* recalculate checksum */
721 len = ntohs(v->lsa->hdr.len);
722 v->lsa->hdr.ls_chksum = 0;
723 v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET));
724
725 clock_gettime(CLOCK_MONOTONIC, &tp);
726 v->changed = v->stamp = tp.tv_sec;
727
728 timerclear(&tv);
729 tv.tv_sec = LS_REFRESH_TIME;
730 if (evtimer_add(&v->ev, &tv) == -1)
731 fatal("lsa_refresh");
732 }
733
734 void
lsa_merge(struct rde_nbr * nbr,struct lsa * lsa,struct vertex * v)735 lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
736 {
737 struct timeval tv;
738 struct timespec tp;
739 time_t now;
740 u_int16_t len;
741
742 if (v == NULL) {
743 if (lsa_add(nbr, lsa))
744 /* delayed update */
745 return;
746 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0,
747 lsa, ntohs(lsa->hdr.len));
748 return;
749 }
750
751 /* set the seq_num to the current one. lsa_refresh() will do the ++ */
752 lsa->hdr.seq_num = v->lsa->hdr.seq_num;
753 /* recalculate checksum */
754 len = ntohs(lsa->hdr.len);
755 lsa->hdr.ls_chksum = 0;
756 lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET));
757
758 /* compare LSA most header fields are equal so don't check them */
759 if (lsa_equal(lsa, v->lsa)) {
760 free(lsa);
761 return;
762 }
763
764 /* overwrite the lsa all other fields are unaffected */
765 free(v->lsa);
766 v->lsa = lsa;
767 start_spf_timer();
768 if (v->type != LSA_TYPE_EXTERNAL &&
769 v->type != LSA_TYPE_AS_OPAQ)
770 nbr->area->dirty = 1;
771
772 /* set correct timeout for reflooding the LSA */
773 clock_gettime(CLOCK_MONOTONIC, &tp);
774 now = tp.tv_sec;
775 timerclear(&tv);
776 if (v->changed + MIN_LS_INTERVAL >= now)
777 tv.tv_sec = MIN_LS_INTERVAL;
778 if (evtimer_add(&v->ev, &tv) == -1)
779 fatal("lsa_merge");
780 }
781
782 void
lsa_remove_invalid_sums(struct area * area)783 lsa_remove_invalid_sums(struct area *area)
784 {
785 struct lsa_tree *tree = &area->lsa_tree;
786 struct vertex *v, *nv;
787
788 /* XXX speed me up */
789 for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) {
790 nv = RB_NEXT(lsa_tree, tree, v);
791 if ((v->type == LSA_TYPE_SUM_NETWORK ||
792 v->type == LSA_TYPE_SUM_ROUTER) &&
793 v->self && v->cost == LS_INFINITY &&
794 v->deleted == 0) {
795 /*
796 * age the lsa and call lsa_timeout() which will
797 * actually remove it from the database.
798 */
799 v->lsa->hdr.age = htons(MAX_AGE);
800 lsa_timeout(0, 0, v);
801 }
802 }
803 }
804
805 void
lsa_generate_stub_sums(struct area * area)806 lsa_generate_stub_sums(struct area *area)
807 {
808 struct rt_node rn;
809 struct redistribute *r;
810 struct vertex *v;
811 struct lsa *lsa;
812 struct area *back;
813
814 if (!area->stub)
815 return;
816
817 back = rde_backbone_area();
818 if (!back || !back->active)
819 return;
820
821 SIMPLEQ_FOREACH(r, &area->redist_list, entry) {
822 bzero(&rn, sizeof(rn));
823 if (r->type == REDIST_DEFAULT) {
824 /* setup fake rt_node */
825 rn.prefixlen = 0;
826 rn.prefix.s_addr = INADDR_ANY;
827 rn.cost = r->metric & LSA_METRIC_MASK;
828
829 /* update lsa but only if it was changed */
830 v = lsa_find_area(area, LSA_TYPE_SUM_NETWORK,
831 rn.prefix.s_addr, rde_router_id());
832 lsa = orig_sum_lsa(&rn, area, LSA_TYPE_SUM_NETWORK, 0);
833 lsa_merge(rde_nbr_self(area), lsa, v);
834
835 if (v == NULL)
836 v = lsa_find_area(area, LSA_TYPE_SUM_NETWORK,
837 rn.prefix.s_addr, rde_router_id());
838
839 /*
840 * suppressed/deleted routes are not found in the
841 * second lsa_find
842 */
843 if (v)
844 v->cost = rn.cost;
845 return;
846 } else if (r->type == (REDIST_DEFAULT | REDIST_NO))
847 return;
848 }
849 }
850
851 int
lsa_equal(struct lsa * a,struct lsa * b)852 lsa_equal(struct lsa *a, struct lsa *b)
853 {
854 /*
855 * compare LSA that already have same type, adv_rtr and ls_id
856 * so not all header need to be compared
857 */
858 if (a == NULL || b == NULL)
859 return (0);
860 if (a->hdr.len != b->hdr.len)
861 return (0);
862 if (a->hdr.opts != b->hdr.opts)
863 return (0);
864 /* LSAs with age MAX_AGE are never equal */
865 if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE))
866 return (0);
867 if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) -
868 sizeof(struct lsa_hdr)))
869 return (0);
870
871 return (1);
872 }
873