GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/ospfd/rde_lsdb.c Lines: 1 409 0.2 %
Date: 2017-11-13 Branches: 1 497 0.2 %

Line Branch Exec Source
1
/*	$OpenBSD: rde_lsdb.c,v 1.50 2015/11/22 13:09:10 claudio 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
39













































96
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
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 *
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
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
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
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
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
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
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
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
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
387
	if (lsa->hdr.type == LSA_TYPE_EXTERNAL ||
388
	    lsa->hdr.type == LSA_TYPE_AS_OPAQ)
389
		tree = &asext_tree;
390
	else if (lsa->hdr.type == LSA_TYPE_LINK_OPAQ)
391
		tree = &nbr->iface->lsa_tree;
392
	else
393
		tree = &nbr->area->lsa_tree;
394
395
	new = vertex_get(lsa, nbr, tree);
396
	old = RB_INSERT(lsa_tree, tree, new);
397
398
	if (old != NULL) {
399
		if (old->deleted && evtimer_pending(&old->ev, &tv)) {
400
			/* new update added before hold time expired */
401
			gettimeofday(&now, NULL);
402
			timersub(&tv, &now, &res);
403
404
			/* remove old LSA and insert new LSA with delay */
405
			vertex_free(old);
406
			RB_INSERT(lsa_tree, tree, new);
407
			new->deleted = 1;
408
409
			if (evtimer_add(&new->ev, &res) != 0)
410
				fatal("lsa_add");
411
			return (1);
412
		}
413
		if (!lsa_equal(new->lsa, old->lsa)) {
414
			if (lsa->hdr.type != LSA_TYPE_EXTERNAL &&
415
			    lsa->hdr.type != LSA_TYPE_AS_OPAQ)
416
				nbr->area->dirty = 1;
417
			start_spf_timer();
418
		}
419
		vertex_free(old);
420
		RB_INSERT(lsa_tree, tree, new);
421
	} else {
422
		if (lsa->hdr.type != LSA_TYPE_EXTERNAL &&
423
		    lsa->hdr.type != LSA_TYPE_AS_OPAQ)
424
			nbr->area->dirty = 1;
425
		start_spf_timer();
426
	}
427
428
	/* timeout handling either MAX_AGE or LS_REFRESH_TIME */
429
	timerclear(&tv);
430
431
	if (nbr->self && ntohs(new->lsa->hdr.age) == DEFAULT_AGE)
432
		tv.tv_sec = LS_REFRESH_TIME;
433
	else
434
		tv.tv_sec = MAX_AGE - ntohs(new->lsa->hdr.age);
435
436
	if (evtimer_add(&new->ev, &tv) != 0)
437
		fatal("lsa_add");
438
	return (0);
439
}
440
441
void
442
lsa_del(struct rde_nbr *nbr, struct lsa_hdr *lsa)
443
{
444
	struct vertex	*v;
445
	struct timeval	 tv;
446
447
	v = lsa_find(nbr->iface, lsa->type, lsa->ls_id, lsa->adv_rtr);
448
	if (v == NULL)
449
		return;
450
451
	v->deleted = 1;
452
	/* hold time to make sure that a new lsa is not added premature */
453
	timerclear(&tv);
454
	tv.tv_sec = MIN_LS_INTERVAL;
455
	if (evtimer_add(&v->ev, &tv) == -1)
456
		fatal("lsa_del");
457
}
458
459
void
460
lsa_age(struct vertex *v)
461
{
462
	struct timespec	tp;
463
	time_t		now;
464
	int		d;
465
	u_int16_t	age;
466
467
	clock_gettime(CLOCK_MONOTONIC, &tp);
468
	now = tp.tv_sec;
469
470
	d = now - v->stamp;
471
	/* set stamp so that at least new calls work */
472
	v->stamp = now;
473
474
	if (d < 0) {
475
		log_warnx("lsa_age: time went backwards");
476
		return;
477
	}
478
479
	age = ntohs(v->lsa->hdr.age);
480
	if (age + d > MAX_AGE)
481
		age = MAX_AGE;
482
	else
483
		age += d;
484
485
	v->lsa->hdr.age = htons(age);
486
}
487
488
struct vertex *
489
lsa_find(struct iface *iface, u_int8_t type, u_int32_t ls_id, u_int32_t adv_rtr)
490
{
491
	struct lsa_tree	*tree;
492
493
	if (type == LSA_TYPE_EXTERNAL ||
494
	    type == LSA_TYPE_AS_OPAQ)
495
		tree = &asext_tree;
496
	else if (type == LSA_TYPE_LINK_OPAQ)
497
		tree = &iface->lsa_tree;
498
	else
499
		tree = &iface->area->lsa_tree;
500
501
	return lsa_find_tree(tree, type, ls_id, adv_rtr);
502
}
503
504
struct vertex *
505
lsa_find_area(struct area *area, u_int8_t type, u_int32_t ls_id,
506
    u_int32_t adv_rtr)
507
{
508
	return lsa_find_tree(&area->lsa_tree, type, ls_id, adv_rtr);
509
}
510
511
struct vertex *
512
lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id,
513
    u_int32_t adv_rtr)
514
{
515
	struct vertex	 key;
516
	struct vertex	*v;
517
518
	key.ls_id = ntohl(ls_id);
519
	key.adv_rtr = ntohl(adv_rtr);
520
	key.type = type;
521
522
	v = RB_FIND(lsa_tree, tree, &key);
523
524
	/* LSA that are deleted are not findable */
525
	if (v && v->deleted)
526
		return (NULL);
527
528
	if (v)
529
		lsa_age(v);
530
531
	return (v);
532
}
533
534
struct vertex *
535
lsa_find_net(struct area *area, u_int32_t ls_id)
536
{
537
	struct lsa_tree	*tree = &area->lsa_tree;
538
	struct vertex	*v;
539
540
	/* XXX speed me up */
541
	RB_FOREACH(v, lsa_tree, tree) {
542
		if (v->lsa->hdr.type == LSA_TYPE_NETWORK &&
543
		    v->lsa->hdr.ls_id == ls_id) {
544
			/* LSA that are deleted are not findable */
545
			if (v->deleted)
546
				return (NULL);
547
			lsa_age(v);
548
			return (v);
549
		}
550
	}
551
552
	return (NULL);
553
}
554
555
u_int16_t
556
lsa_num_links(struct vertex *v)
557
{
558
	switch (v->type) {
559
	case LSA_TYPE_ROUTER:
560
		return (ntohs(v->lsa->data.rtr.nlinks));
561
	case LSA_TYPE_NETWORK:
562
		return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr)
563
		    - sizeof(u_int32_t)) / sizeof(struct lsa_net_link));
564
	default:
565
		fatalx("lsa_num_links: invalid LSA type");
566
	}
567
}
568
569
void
570
lsa_snap(struct rde_nbr *nbr)
571
{
572
	struct lsa_tree	*tree = &nbr->area->lsa_tree;
573
	struct vertex	*v;
574
575
	do {
576
		RB_FOREACH(v, lsa_tree, tree) {
577
			if (v->deleted)
578
				continue;
579
			switch (v->type) {
580
			case LSA_TYPE_LINK_OPAQ:
581
			case LSA_TYPE_AREA_OPAQ:
582
			case LSA_TYPE_AS_OPAQ:
583
				if (nbr->capa_options & OSPF_OPTION_O)
584
					break;
585
				continue;
586
			}
587
			lsa_age(v);
588
			if (ntohs(v->lsa->hdr.age) >= MAX_AGE)
589
				rde_imsg_compose_ospfe(IMSG_LS_SNAP, nbr->peerid,
590
				    0, &v->lsa->hdr, ntohs(v->lsa->hdr.len));
591
			else
592
				rde_imsg_compose_ospfe(IMSG_DB_SNAPSHOT,
593
				    nbr->peerid, 0, &v->lsa->hdr,
594
				    sizeof(struct lsa_hdr));
595
		}
596
		if (tree == &asext_tree)
597
			break;
598
		if (tree == &nbr->area->lsa_tree)
599
			tree = &nbr->iface->lsa_tree;
600
		else if (nbr->area->stub)
601
			break;
602
		else
603
			tree = &asext_tree;
604
	} while (1);
605
}
606
607
void
608
lsa_dump(struct lsa_tree *tree, int imsg_type, pid_t pid)
609
{
610
	struct vertex	*v;
611
612
	RB_FOREACH(v, lsa_tree, tree) {
613
		if (v->deleted)
614
			continue;
615
		lsa_age(v);
616
		switch (imsg_type) {
617
		case IMSG_CTL_SHOW_DATABASE:
618
			break;
619
		case IMSG_CTL_SHOW_DB_SELF:
620
			if (v->lsa->hdr.adv_rtr == rde_router_id())
621
				break;
622
			continue;
623
		case IMSG_CTL_SHOW_DB_EXT:
624
			if (v->type == LSA_TYPE_EXTERNAL)
625
				break;
626
			continue;
627
		case IMSG_CTL_SHOW_DB_NET:
628
			if (v->type == LSA_TYPE_NETWORK)
629
				break;
630
			continue;
631
		case IMSG_CTL_SHOW_DB_RTR:
632
			if (v->type == LSA_TYPE_ROUTER)
633
				break;
634
			continue;
635
		case IMSG_CTL_SHOW_DB_SUM:
636
			if (v->type == LSA_TYPE_SUM_NETWORK)
637
				break;
638
			continue;
639
		case IMSG_CTL_SHOW_DB_ASBR:
640
			if (v->type == LSA_TYPE_SUM_ROUTER)
641
				break;
642
			continue;
643
		case IMSG_CTL_SHOW_DB_OPAQ:
644
			if (v->type == LSA_TYPE_LINK_OPAQ ||
645
			    v->type == LSA_TYPE_AREA_OPAQ ||
646
			    v->type == LSA_TYPE_AS_OPAQ)
647
				break;
648
			continue;
649
		default:
650
			log_warnx("lsa_dump: unknown imsg type");
651
			return;
652
		}
653
		rde_imsg_compose_ospfe(imsg_type, 0, pid, &v->lsa->hdr,
654
		    ntohs(v->lsa->hdr.len));
655
	}
656
}
657
658
/* ARGSUSED */
659
void
660
lsa_timeout(int fd, short event, void *bula)
661
{
662
	struct vertex	*v = bula;
663
	struct timeval	 tv;
664
665
	lsa_age(v);
666
667
	if (v->deleted) {
668
		if (ntohs(v->lsa->hdr.age) >= MAX_AGE) {
669
			vertex_free(v);
670
		} else {
671
			v->deleted = 0;
672
673
			/* schedule recalculation of the RIB */
674
			if (v->type != LSA_TYPE_EXTERNAL &&
675
			    v->type != LSA_TYPE_AS_OPAQ)
676
				v->area->dirty = 1;
677
			start_spf_timer();
678
679
			rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
680
			    v->lsa, ntohs(v->lsa->hdr.len));
681
682
			/* timeout handling either MAX_AGE or LS_REFRESH_TIME */
683
			timerclear(&tv);
684
			if (v->self)
685
				tv.tv_sec = LS_REFRESH_TIME;
686
			else
687
				tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age);
688
689
			if (evtimer_add(&v->ev, &tv) != 0)
690
				fatal("lsa_timeout");
691
		}
692
		return;
693
	}
694
695
	if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE)
696
		lsa_refresh(v);
697
698
	rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0,
699
	    v->lsa, ntohs(v->lsa->hdr.len));
700
}
701
702
void
703
lsa_refresh(struct vertex *v)
704
{
705
	struct timeval	 tv;
706
	struct timespec	 tp;
707
	u_int32_t	 seqnum;
708
	u_int16_t	 len;
709
710
	/* refresh LSA by increasing sequence number by one */
711
	if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE)
712
		/* self originated network that is currently beeing removed */
713
		v->lsa->hdr.age = htons(MAX_AGE);
714
	else
715
		v->lsa->hdr.age = htons(DEFAULT_AGE);
716
	seqnum = ntohl(v->lsa->hdr.seq_num);
717
	if (seqnum++ == MAX_SEQ_NUM)
718
		/* XXX fix me */
719
		fatalx("sequence number wrapping");
720
	v->lsa->hdr.seq_num = htonl(seqnum);
721
722
	/* recalculate checksum */
723
	len = ntohs(v->lsa->hdr.len);
724
	v->lsa->hdr.ls_chksum = 0;
725
	v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET));
726
727
	clock_gettime(CLOCK_MONOTONIC, &tp);
728
	v->changed = v->stamp = tp.tv_sec;
729
730
	timerclear(&tv);
731
	tv.tv_sec = LS_REFRESH_TIME;
732
	if (evtimer_add(&v->ev, &tv) == -1)
733
		fatal("lsa_refresh");
734
}
735
736
void
737
lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v)
738
{
739
	struct timeval	tv;
740
	struct timespec	tp;
741
	time_t		now;
742
	u_int16_t	len;
743
744
	if (v == NULL) {
745
		if (lsa_add(nbr, lsa))
746
			/* delayed update */
747
			return;
748
		rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0,
749
		    lsa, ntohs(lsa->hdr.len));
750
		return;
751
	}
752
753
	/* set the seq_num to the current one. lsa_refresh() will do the ++ */
754
	lsa->hdr.seq_num = v->lsa->hdr.seq_num;
755
	/* recalculate checksum */
756
	len = ntohs(lsa->hdr.len);
757
	lsa->hdr.ls_chksum = 0;
758
	lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET));
759
760
	/* compare LSA most header fields are equal so don't check them */
761
	if (lsa_equal(lsa, v->lsa)) {
762
		free(lsa);
763
		return;
764
	}
765
766
	/* overwrite the lsa all other fields are unaffected */
767
	free(v->lsa);
768
	v->lsa = lsa;
769
	start_spf_timer();
770
	if (v->type != LSA_TYPE_EXTERNAL &&
771
	    v->type != LSA_TYPE_AS_OPAQ)
772
		nbr->area->dirty = 1;
773
774
	/* set correct timeout for reflooding the LSA */
775
	clock_gettime(CLOCK_MONOTONIC, &tp);
776
	now = tp.tv_sec;
777
	timerclear(&tv);
778
	if (v->changed + MIN_LS_INTERVAL >= now)
779
		tv.tv_sec = MIN_LS_INTERVAL;
780
	if (evtimer_add(&v->ev, &tv) == -1)
781
		fatal("lsa_merge");
782
}
783
784
void
785
lsa_remove_invalid_sums(struct area *area)
786
{
787
	struct lsa_tree	*tree = &area->lsa_tree;
788
	struct vertex	*v, *nv;
789
790
	/* XXX speed me up */
791
	for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) {
792
		nv = RB_NEXT(lsa_tree, tree, v);
793
		if ((v->type == LSA_TYPE_SUM_NETWORK ||
794
		    v->type == LSA_TYPE_SUM_ROUTER) &&
795
		    v->self && v->cost == LS_INFINITY &&
796
		    v->deleted == 0) {
797
			/*
798
			 * age the lsa and call lsa_timeout() which will
799
			 * actually remove it from the database.
800
			 */
801
			v->lsa->hdr.age = htons(MAX_AGE);
802
			lsa_timeout(0, 0, v);
803
		}
804
	}
805
}
806
807
void
808
lsa_generate_stub_sums(struct area *area)
809
{
810
	struct rt_node rn;
811
	struct redistribute *r;
812
	struct vertex *v;
813
	struct lsa *lsa;
814
	struct area *back;
815
816
	if (!area->stub)
817
		return;
818
819
	back = rde_backbone_area();
820
	if (!back || !back->active)
821
		return;
822
823
	SIMPLEQ_FOREACH(r, &area->redist_list, entry) {
824
		bzero(&rn, sizeof(rn));
825
		if (r->type == REDIST_DEFAULT) {
826
			/* setup fake rt_node */
827
			rn.prefixlen = 0;
828
			rn.prefix.s_addr = INADDR_ANY;
829
			rn.cost = r->metric & LSA_METRIC_MASK;
830
831
			/* update lsa but only if it was changed */
832
			v = lsa_find_area(area, LSA_TYPE_SUM_NETWORK,
833
			    rn.prefix.s_addr, rde_router_id());
834
			lsa = orig_sum_lsa(&rn, area, LSA_TYPE_SUM_NETWORK, 0);
835
			lsa_merge(rde_nbr_self(area), lsa, v);
836
837
			if (v == NULL)
838
				v = lsa_find_area(area, LSA_TYPE_SUM_NETWORK,
839
				    rn.prefix.s_addr, rde_router_id());
840
841
			/*
842
			 * suppressed/deleted routes are not found in the
843
			 * second lsa_find
844
			 */
845
			if (v)
846
				v->cost = rn.cost;
847
			return;
848
		} else if (r->type == (REDIST_DEFAULT | REDIST_NO))
849
			return;
850
	}
851
}
852
853
int
854
lsa_equal(struct lsa *a, struct lsa *b)
855
{
856
	/*
857
	 * compare LSA that already have same type, adv_rtr and ls_id
858
	 * so not all header need to be compared
859
	 */
860
	if (a == NULL || b == NULL)
861
		return (0);
862
	if (a->hdr.len != b->hdr.len)
863
		return (0);
864
	if (a->hdr.opts != b->hdr.opts)
865
		return (0);
866
	/* LSAs with age MAX_AGE are never equal */
867
	if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE))
868
		return (0);
869
	if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) -
870
	    sizeof(struct lsa_hdr)))
871
		return (0);
872
873
	return (1);
874
}