GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/ospfd/lsupdate.c Lines: 0 274 0.0 %
Date: 2017-11-13 Branches: 0 204 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: lsupdate.c,v 1.45 2016/12/26 17:38:14 jca Exp $ */
2
3
/*
4
 * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
5
 * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
6
 *
7
 * Permission to use, copy, modify, and distribute this software for any
8
 * purpose with or without fee is hereby granted, provided that the above
9
 * copyright notice and this permission notice appear in all copies.
10
 *
11
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18
 */
19
20
#include <sys/types.h>
21
#include <sys/socket.h>
22
#include <netinet/in.h>
23
#include <arpa/inet.h>
24
25
#include <stdlib.h>
26
#include <string.h>
27
#include <siphash.h>
28
29
#include "ospf.h"
30
#include "ospfd.h"
31
#include "log.h"
32
#include "ospfe.h"
33
#include "rde.h"
34
35
extern struct ospfd_conf	*oeconf;
36
extern struct imsgev		*iev_rde;
37
38
struct ibuf *prepare_ls_update(struct iface *);
39
int	add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t,
40
	    u_int16_t);
41
int	send_ls_update(struct ibuf *, struct iface *, struct in_addr, u_int32_t);
42
43
void	ls_retrans_list_insert(struct nbr *, struct lsa_entry *);
44
void	ls_retrans_list_remove(struct nbr *, struct lsa_entry *);
45
46
/* link state update packet handling */
47
int
48
lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
49
    void *data)
50
{
51
	struct nbr		*nbr;
52
	struct lsa_entry	*le = NULL;
53
	int			 queued = 0, dont_ack = 0;
54
	int			 r;
55
56
	LIST_FOREACH(nbr, &iface->nbr_list, entry) {
57
		if (nbr == iface->self)
58
			continue;
59
		if (!(nbr->state & NBR_STA_FLOOD))
60
			continue;
61
62
		if (iface->state & IF_STA_DROTHER && !queued)
63
			while ((le = ls_retrans_list_get(iface->self, lsa_hdr)))
64
			    ls_retrans_list_free(iface->self, le);
65
66
		while ((le = ls_retrans_list_get(nbr, lsa_hdr)))
67
			ls_retrans_list_free(nbr, le);
68
69
		if (!(nbr->state & NBR_STA_FULL) &&
70
		    (le = ls_req_list_get(nbr, lsa_hdr)) != NULL) {
71
			r = lsa_newer(lsa_hdr, le->le_lsa);
72
			if (r > 0) {
73
				/* to flood LSA is newer than requested */
74
				ls_req_list_free(nbr, le);
75
				/* new needs to be flooded */
76
			} else if (r < 0) {
77
				/* to flood LSA is older than requested */
78
				continue;
79
			} else {
80
				/* LSA are equal */
81
				ls_req_list_free(nbr, le);
82
				continue;
83
			}
84
		}
85
86
		if (nbr == originator) {
87
			dont_ack++;
88
			continue;
89
		}
90
91
		/* non DR or BDR router keep all lsa in one retrans list */
92
		if (iface->state & IF_STA_DROTHER) {
93
			if (!queued)
94
				ls_retrans_list_add(iface->self, data,
95
				    iface->rxmt_interval, 0);
96
			queued = 1;
97
		} else {
98
			ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0);
99
			queued = 1;
100
		}
101
	}
102
103
	if (!queued)
104
		return (0);
105
106
	if (iface == originator->iface && iface->self != originator) {
107
		if (iface->dr == originator || iface->bdr == originator)
108
			return (0);
109
		if (iface->state & IF_STA_BACKUP)
110
			return (0);
111
		dont_ack++;
112
	}
113
114
	/*
115
	 * initial flood needs to be queued separately, timeout is zero
116
	 * and oneshot has to be set because the retransimssion queues
117
	 * are already loaded.
118
	 */
119
	switch (iface->type) {
120
	case IF_TYPE_POINTOPOINT:
121
	case IF_TYPE_BROADCAST:
122
		ls_retrans_list_add(iface->self, data, 0, 1);
123
		break;
124
	case IF_TYPE_NBMA:
125
	case IF_TYPE_POINTOMULTIPOINT:
126
	case IF_TYPE_VIRTUALLINK:
127
		LIST_FOREACH(nbr, &iface->nbr_list, entry) {
128
			if (nbr == iface->self)
129
				continue;
130
			if (!(nbr->state & NBR_STA_FLOOD))
131
				continue;
132
			if (!TAILQ_EMPTY(&nbr->ls_retrans_list)) {
133
				le = TAILQ_LAST(&nbr->ls_retrans_list,
134
				    lsa_head);
135
				if (lsa_hdr->type != le->le_lsa->type ||
136
				    lsa_hdr->ls_id != le->le_lsa->ls_id ||
137
				    lsa_hdr->adv_rtr != le->le_lsa->adv_rtr)
138
					continue;
139
			}
140
			ls_retrans_list_add(nbr, data, 0, 1);
141
		}
142
		break;
143
	default:
144
		fatalx("lsa_flood: unknown interface type");
145
	}
146
147
	return (dont_ack == 2);
148
}
149
150
struct ibuf *
151
prepare_ls_update(struct iface *iface)
152
{
153
	struct ibuf		*buf;
154
155
	if ((buf = ibuf_dynamic(iface->mtu - sizeof(struct ip),
156
	    IP_MAXPACKET - sizeof(struct ip))) == NULL)
157
		fatal("prepare_ls_update");
158
159
	/* OSPF header */
160
	if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE))
161
		goto fail;
162
163
	/* reserve space for number of lsa field */
164
	if (ibuf_reserve(buf, sizeof(u_int32_t)) == NULL)
165
		goto fail;
166
167
	return (buf);
168
fail:
169
	log_warn("prepare_ls_update");
170
	ibuf_free(buf);
171
	return (NULL);
172
}
173
174
int
175
add_ls_update(struct ibuf *buf, struct iface *iface, void *data, u_int16_t len,
176
    u_int16_t older)
177
{
178
	void		*lsage;
179
	u_int16_t	 age;
180
181
	if ((size_t)iface->mtu < sizeof(struct ip) + sizeof(struct ospf_hdr) +
182
	    sizeof(u_int32_t) + ibuf_size(buf) + len + MD5_DIGEST_LENGTH) {
183
		/* start new packet unless this is the first LSA to pack */
184
		if (ibuf_size(buf) > sizeof(struct ospf_hdr) +
185
		    sizeof(u_int32_t))
186
			return (0);
187
	}
188
189
	lsage = ibuf_reserve(buf, 0);
190
	if (ibuf_add(buf, data, len)) {
191
		log_warn("add_ls_update");
192
		return (0);
193
	}
194
195
	/* age LSA before sending it out */
196
	memcpy(&age, data, sizeof(age));
197
	age = ntohs(age);
198
	if ((age += older + iface->transmit_delay) >= MAX_AGE)
199
		age = MAX_AGE;
200
	age = htons(age);
201
	memcpy(lsage, &age, sizeof(age));
202
203
	return (1);
204
}
205
206
207
208
int
209
send_ls_update(struct ibuf *buf, struct iface *iface, struct in_addr addr,
210
    u_int32_t nlsa)
211
{
212
	struct sockaddr_in	 dst;
213
	int			 ret;
214
215
	nlsa = htonl(nlsa);
216
	memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)),
217
	    &nlsa, sizeof(nlsa));
218
	/* update authentication and calculate checksum */
219
	if (auth_gen(buf, iface))
220
		goto fail;
221
222
	/* set destination */
223
	dst.sin_family = AF_INET;
224
	dst.sin_len = sizeof(struct sockaddr_in);
225
	dst.sin_addr.s_addr = addr.s_addr;
226
227
	ret = send_packet(iface, buf, &dst);
228
229
	ibuf_free(buf);
230
	return (ret);
231
fail:
232
	log_warn("send_ls_update");
233
	ibuf_free(buf);
234
	return (-1);
235
}
236
237
void
238
recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len)
239
{
240
	struct lsa_hdr		 lsa;
241
	u_int32_t		 nlsa;
242
243
	if (len < sizeof(nlsa)) {
244
		log_warnx("recv_ls_update: bad packet size, neighbor ID %s",
245
		    inet_ntoa(nbr->id));
246
		return;
247
	}
248
	memcpy(&nlsa, buf, sizeof(nlsa));
249
	nlsa = ntohl(nlsa);
250
	buf += sizeof(nlsa);
251
	len -= sizeof(nlsa);
252
253
	switch (nbr->state) {
254
	case NBR_STA_DOWN:
255
	case NBR_STA_ATTEMPT:
256
	case NBR_STA_INIT:
257
	case NBR_STA_2_WAY:
258
	case NBR_STA_XSTRT:
259
	case NBR_STA_SNAP:
260
		log_debug("recv_ls_update: packet ignored in state %s, "
261
		    "neighbor ID %s", nbr_state_name(nbr->state),
262
		    inet_ntoa(nbr->id));
263
		break;
264
	case NBR_STA_XCHNG:
265
	case NBR_STA_LOAD:
266
	case NBR_STA_FULL:
267
		for (; nlsa > 0 && len > 0; nlsa--) {
268
			if (len < sizeof(lsa)) {
269
				log_warnx("recv_ls_update: bad packet size, "
270
				    "neighbor ID %s", inet_ntoa(nbr->id));
271
				return;
272
			}
273
			memcpy(&lsa, buf, sizeof(lsa));
274
			if (len < ntohs(lsa.len)) {
275
				log_warnx("recv_ls_update: bad packet size, "
276
				    "neighbor ID %s", inet_ntoa(nbr->id));
277
				return;
278
			}
279
			imsg_compose_event(iev_rde, IMSG_LS_UPD, nbr->peerid, 0,
280
			    -1, buf, ntohs(lsa.len));
281
			buf += ntohs(lsa.len);
282
			len -= ntohs(lsa.len);
283
		}
284
		if (nlsa > 0 || len > 0) {
285
			log_warnx("recv_ls_update: bad packet size, "
286
			    "neighbor ID %s", inet_ntoa(nbr->id));
287
			return;
288
		}
289
		break;
290
	default:
291
		fatalx("recv_ls_update: unknown neighbor state");
292
	}
293
}
294
295
/* link state retransmit list */
296
void
297
ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa,
298
    unsigned short timeout, unsigned short oneshot)
299
{
300
	struct timeval		 tv;
301
	struct lsa_entry	*le;
302
	struct lsa_ref		*ref;
303
304
	if ((ref = lsa_cache_get(lsa)) == NULL)
305
		fatalx("King Bula sez: somebody forgot to lsa_cache_add");
306
307
	if ((le = calloc(1, sizeof(*le))) == NULL)
308
		fatal("ls_retrans_list_add");
309
310
	le->le_ref = ref;
311
	le->le_when = timeout;
312
	le->le_oneshot = oneshot;
313
314
	ls_retrans_list_insert(nbr, le);
315
316
	if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) {
317
		timerclear(&tv);
318
		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
319
320
		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
321
			fatal("ls_retrans_list_add");
322
	}
323
}
324
325
int
326
ls_retrans_list_del(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
327
{
328
	struct lsa_entry	*le;
329
330
	if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL)
331
		return (-1);
332
	/*
333
	 * Compare LSA with the Ack by comparing not only the seq_num and
334
	 * checksum but also the age field.  Since we only care about MAX_AGE
335
	 * vs. non-MAX_AGE LSA, a simple >= comparison is good enough.  This
336
	 * ensures that a LSA withdrawal is not acked by a previous update.
337
	 */
338
	if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num &&
339
	    lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum &&
340
	    ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) {
341
		ls_retrans_list_free(nbr, le);
342
		return (0);
343
	}
344
345
	return (-1);
346
}
347
348
struct lsa_entry *
349
ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
350
{
351
	struct lsa_entry	*le;
352
353
	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
354
		if ((lsa_hdr->type == le->le_ref->hdr.type) &&
355
		    (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) &&
356
		    (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr))
357
			return (le);
358
	}
359
	return (NULL);
360
}
361
362
void
363
ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new)
364
{
365
	struct lsa_entry	*le;
366
	unsigned short		 when = new->le_when;
367
368
	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
369
		if (when < le->le_when) {
370
			new->le_when = when;
371
			TAILQ_INSERT_BEFORE(le, new, entry);
372
			nbr->ls_ret_cnt++;
373
			return;
374
		}
375
		when -= le->le_when;
376
	}
377
	new->le_when = when;
378
	TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
379
	nbr->ls_ret_cnt++;
380
}
381
382
void
383
ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le)
384
{
385
	struct timeval		 tv;
386
	struct lsa_entry	*next = TAILQ_NEXT(le, entry);
387
	int			 reset = 0;
388
389
	/* adjust timeout of next entry */
390
	if (next)
391
		next->le_when += le->le_when;
392
393
	if (TAILQ_FIRST(&nbr->ls_retrans_list) == le &&
394
	    evtimer_pending(&nbr->ls_retrans_timer, NULL))
395
		reset = 1;
396
397
	TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
398
	nbr->ls_ret_cnt--;
399
400
	if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
401
		if (evtimer_del(&nbr->ls_retrans_timer) == -1)
402
			fatal("ls_retrans_list_remove");
403
404
		timerclear(&tv);
405
		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
406
407
		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
408
			fatal("ls_retrans_list_remove");
409
	}
410
}
411
412
void
413
ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le)
414
{
415
	ls_retrans_list_remove(nbr, le);
416
417
	lsa_cache_put(le->le_ref, nbr);
418
	free(le);
419
}
420
421
void
422
ls_retrans_list_clr(struct nbr *nbr)
423
{
424
	struct lsa_entry	*le;
425
426
	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
427
		ls_retrans_list_free(nbr, le);
428
429
	nbr->ls_ret_cnt = 0;
430
}
431
432
/* ARGSUSED */
433
void
434
ls_retrans_timer(int fd, short event, void *bula)
435
{
436
	struct timeval		 tv;
437
	struct timespec		 tp;
438
	struct in_addr		 addr;
439
	struct nbr		*nbr = bula;
440
	struct lsa_entry	*le;
441
	struct ibuf		*buf;
442
	time_t			 now;
443
	int			 d;
444
	u_int32_t		 nlsa = 0;
445
446
	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
447
		le->le_when = 0;	/* timer fired */
448
	else
449
		return;			/* queue empty, nothing to do */
450
451
	clock_gettime(CLOCK_MONOTONIC, &tp);
452
	now = tp.tv_sec;
453
454
	if (nbr->iface->self == nbr) {
455
		/*
456
		 * oneshot needs to be set for lsa queued for flooding,
457
		 * if oneshot is not set then the lsa needs to be converted
458
		 * because the router switched lately to DR or BDR
459
		 */
460
		if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
461
			inet_aton(AllSPFRouters, &addr);
462
		else if (nbr->iface->state & IF_STA_DRORBDR) {
463
			/*
464
			 * old retransmission needs to be converted into
465
			 * flood by rerunning the lsa_flood.
466
			 */
467
			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
468
			    le->le_ref->data);
469
			ls_retrans_list_free(nbr, le);
470
			/* ls_retrans_list_free retriggers the timer */
471
			return;
472
		} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
473
			memcpy(&addr, &nbr->iface->dst, sizeof(addr));
474
		else
475
			inet_aton(AllDRouters, &addr);
476
	} else
477
		memcpy(&addr, &nbr->addr, sizeof(addr));
478
479
	if ((buf = prepare_ls_update(nbr->iface)) == NULL) {
480
		le->le_when = 1;
481
		goto done;
482
	}
483
484
	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
485
	    le->le_when == 0) {
486
		d = now - le->le_ref->stamp;
487
		if (d < 0)
488
			d = 0;
489
		else if (d > MAX_AGE)
490
			d = MAX_AGE;
491
492
		if (add_ls_update(buf, nbr->iface, le->le_ref->data,
493
		    le->le_ref->len, d) == 0) {
494
			if (nlsa == 0) {
495
				/* something bad happened retry later */
496
				log_warnx("ls_retrans_timer: sending LS update "
497
				    "to neighbor ID %s failed",
498
				    inet_ntoa(nbr->id));
499
				TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
500
				nbr->ls_ret_cnt--;
501
				le->le_when = nbr->iface->rxmt_interval;
502
				ls_retrans_list_insert(nbr, le);
503
			}
504
			break;
505
		}
506
		nlsa++;
507
		if (le->le_oneshot)
508
			ls_retrans_list_free(nbr, le);
509
		else {
510
			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
511
			nbr->ls_ret_cnt--;
512
			le->le_when = nbr->iface->rxmt_interval;
513
			ls_retrans_list_insert(nbr, le);
514
		}
515
	}
516
	if (nlsa)
517
		send_ls_update(buf, nbr->iface, addr, nlsa);
518
	else
519
		ibuf_free(buf);
520
521
done:
522
	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
523
		timerclear(&tv);
524
		tv.tv_sec = le->le_when;
525
526
		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
527
			fatal("ls_retrans_timer");
528
	}
529
}
530
531
LIST_HEAD(lsa_cache_head, lsa_ref);
532
533
struct lsa_cache {
534
	struct lsa_cache_head	*hashtbl;
535
	u_int32_t		 hashmask;
536
} lsacache;
537
538
SIPHASH_KEY lsacachekey;
539
540
struct lsa_ref		*lsa_cache_look(struct lsa_hdr *);
541
542
void
543
lsa_cache_init(u_int32_t hashsize)
544
{
545
	u_int32_t        hs, i;
546
547
	for (hs = 1; hs < hashsize; hs <<= 1)
548
		;
549
	lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
550
	if (lsacache.hashtbl == NULL)
551
		fatal("lsa_cache_init");
552
553
	for (i = 0; i < hs; i++)
554
		LIST_INIT(&lsacache.hashtbl[i]);
555
	arc4random_buf(&lsacachekey, sizeof(lsacachekey));
556
557
	lsacache.hashmask = hs - 1;
558
}
559
560
static uint32_t
561
lsa_hash_hdr(const struct lsa_hdr *hdr)
562
{
563
	return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
564
}
565
566
struct lsa_ref *
567
lsa_cache_add(void *data, u_int16_t len)
568
{
569
	struct lsa_cache_head	*head;
570
	struct lsa_ref		*ref, *old;
571
	struct timespec		 tp;
572
573
	if ((ref = calloc(1, sizeof(*ref))) == NULL)
574
		fatal("lsa_cache_add");
575
	memcpy(&ref->hdr, data, sizeof(ref->hdr));
576
577
	if ((old = lsa_cache_look(&ref->hdr))) {
578
		free(ref);
579
		old->refcnt++;
580
		return (old);
581
	}
582
583
	if ((ref->data = malloc(len)) == NULL)
584
		fatal("lsa_cache_add");
585
	memcpy(ref->data, data, len);
586
587
	clock_gettime(CLOCK_MONOTONIC, &tp);
588
	ref->stamp = tp.tv_sec;
589
	ref->len = len;
590
	ref->refcnt = 1;
591
592
	head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
593
	LIST_INSERT_HEAD(head, ref, entry);
594
	return (ref);
595
}
596
597
struct lsa_ref *
598
lsa_cache_get(struct lsa_hdr *lsa_hdr)
599
{
600
	struct lsa_ref		*ref;
601
602
	ref = lsa_cache_look(lsa_hdr);
603
	if (ref)
604
		ref->refcnt++;
605
606
	return (ref);
607
}
608
609
void
610
lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr)
611
{
612
	if (--ref->refcnt > 0)
613
		return;
614
615
	if (ntohs(ref->hdr.age) >= MAX_AGE)
616
		ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
617
		    ref->data, sizeof(struct lsa_hdr));
618
619
	free(ref->data);
620
	LIST_REMOVE(ref, entry);
621
	free(ref);
622
}
623
624
struct lsa_ref *
625
lsa_cache_look(struct lsa_hdr *lsa_hdr)
626
{
627
	struct lsa_cache_head	*head;
628
	struct lsa_ref		*ref;
629
630
	head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];
631
632
	LIST_FOREACH(ref, head, entry) {
633
		if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
634
			/* found match */
635
			return (ref);
636
	}
637
638
	return (NULL);
639
}