GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/ospf6d/rde_lsdb.c Lines: 0 463 0.0 %
Date: 2017-11-13 Branches: 0 509 0.0 %

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