GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/dvmrpd/rde_srt.c Lines: 0 259 0.0 %
Date: 2017-11-13 Branches: 0 344 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: rde_srt.c,v 1.26 2015/05/22 01:30:27 jsg Exp $ */
2
3
/*
4
 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
5
 * Copyright (c) 2005, 2006 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 <sys/tree.h>
23
#include <netinet/in.h>
24
#include <arpa/inet.h>
25
#include <err.h>
26
#include <stdlib.h>
27
#include <string.h>
28
29
#include "igmp.h"
30
#include "dvmrp.h"
31
#include "dvmrpd.h"
32
#include "log.h"
33
#include "dvmrpe.h"
34
#include "rde.h"
35
36
/* source route tree */
37
38
void	 rt_invalidate(void);
39
void	 rt_expire_timer(int, short, void *);
40
int	 rt_start_expire_timer(struct rt_node *);
41
void	 rt_holddown_timer(int, short, void *);
42
void	 rt_start_holddown_timer(struct rt_node *);
43
44
void	 srt_set_upstream(struct rt_node *, u_int32_t);
45
46
/* Designated forwarder */
47
void	 srt_set_forwarder_self(struct rt_node *, struct iface *);
48
void	 srt_update_ds_forwarders(struct rt_node *, struct iface *,
49
	    u_int32_t);
50
void	 srt_current_forwarder(struct rt_node *, struct iface *,
51
	    u_int32_t, u_int32_t);
52
53
/* Downstream neighbors */
54
void		 srt_add_ds(struct rt_node *, u_int32_t, u_int32_t);
55
void		 srt_delete_ds(struct rt_node *, struct ds_nbr *,
56
		    struct iface *);
57
58
/* Flash updates */
59
void		 flash_update(struct rt_node *);
60
void		 flash_update_ds(struct rt_node *);
61
62
RB_HEAD(rt_tree, rt_node)	 rt;
63
RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
64
RB_GENERATE(rt_tree, rt_node, entry, rt_compare)
65
66
extern struct dvmrpd_conf	*rdeconf;
67
68
/* timers */
69
void
70
rt_expire_timer(int fd, short event, void *arg)
71
{
72
	struct rt_node	*rn = arg;
73
	struct timeval	 tv;
74
75
	log_debug("rt_expire_timer: route %s/%d", inet_ntoa(rn->prefix),
76
	    rn->prefixlen);
77
78
	timerclear(&tv);
79
	rn->old_cost = rn->cost;
80
	rn->cost = INFINITY_METRIC;
81
	tv.tv_sec = ROUTE_HOLD_DOWN;
82
83
	if (evtimer_add(&rn->holddown_timer, &tv) == -1)
84
		fatal("rt_expire_timer");
85
}
86
87
int
88
rt_start_expire_timer(struct rt_node *rn)
89
{
90
	struct timeval	tv;
91
92
	rn->old_cost = 0;
93
94
	if (evtimer_pending(&rn->holddown_timer, NULL))
95
		if (evtimer_del(&rn->holddown_timer) == -1)
96
			fatal("rt_start_expire_timer");
97
98
	timerclear(&tv);
99
	tv.tv_sec = ROUTE_EXPIRATION_TIME;
100
	return (evtimer_add(&rn->expiration_timer, &tv));
101
}
102
103
void
104
rt_holddown_timer(int fd, short event, void *arg)
105
{
106
	struct rt_node	*rn = arg;
107
108
	log_debug("rt_holddown_timer: route %s/%d", inet_ntoa(rn->prefix),
109
	    rn->prefixlen);
110
111
	rt_remove(rn);
112
}
113
114
void
115
rt_start_holddown_timer(struct rt_node *rn)
116
{
117
	struct timeval	tv;
118
119
	timerclear(&tv);
120
	tv.tv_sec = ROUTE_HOLD_DOWN;
121
	if (evtimer_pending(&rn->expiration_timer, NULL)) {
122
		if (evtimer_del(&rn->expiration_timer) == -1)
123
			fatal("rt_start_holddown_timer");
124
		evtimer_add(&rn->holddown_timer, &tv);
125
	}
126
}
127
128
/* route table */
129
void
130
rt_init(void)
131
{
132
	RB_INIT(&rt);
133
}
134
135
int
136
rt_compare(struct rt_node *a, struct rt_node *b)
137
{
138
	/*
139
	 * sort route entries based on prefixlen since generating route
140
	 * reports rely on that.
141
	 */
142
	if (a->prefixlen < b->prefixlen)
143
		return (-1);
144
	if (a->prefixlen > b->prefixlen)
145
		return (1);
146
	if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr))
147
		return (-1);
148
	if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr))
149
		return (1);
150
	return (0);
151
}
152
153
struct rt_node *
154
rt_find(in_addr_t prefix, u_int8_t prefixlen)
155
{
156
	struct rt_node	s;
157
158
	s.prefix.s_addr = prefix;
159
	s.prefixlen = prefixlen;
160
161
	return (RB_FIND(rt_tree, &rt, &s));
162
}
163
164
struct rt_node *
165
rr_new_rt(struct route_report *rr, u_int32_t adj_metric, int connected)
166
{
167
	struct timespec	 now;
168
	struct rt_node  *rn;
169
	int i;
170
171
	clock_gettime(CLOCK_MONOTONIC, &now);
172
173
	if ((rn = calloc(1, sizeof(*rn))) == NULL)
174
		fatal("rr_new_rt");
175
176
	rn->prefix.s_addr = rr->net.s_addr;
177
	rn->prefixlen = mask2prefixlen(rr->mask.s_addr);
178
	rn->nexthop.s_addr = rr->nexthop.s_addr;
179
	rn->cost = adj_metric;
180
	rn->ifindex = rr->ifindex;
181
182
	for (i = 0; i < MAXVIFS; i++) {
183
		rn->ttls[i] = 0;
184
		rn->ds_cnt[i] = 0;
185
		rn->adv_rtr[i].addr.s_addr = 0;
186
		rn->adv_rtr[i].metric = 0;
187
	}
188
189
	LIST_INIT(&rn->ds_list);
190
191
	rn->flags = F_DVMRPD_INSERTED;
192
	rn->connected = connected;
193
	rn->uptime = now.tv_sec;
194
195
	evtimer_set(&rn->expiration_timer, rt_expire_timer, rn);
196
	evtimer_set(&rn->holddown_timer, rt_holddown_timer, rn);
197
198
	return (rn);
199
}
200
201
int
202
rt_insert(struct rt_node *r)
203
{
204
	log_debug("rt_insert: inserting route %s/%d", inet_ntoa(r->prefix),
205
	    r->prefixlen);
206
207
	if (RB_INSERT(rt_tree, &rt, r) != NULL) {
208
		log_warnx("rt_insert failed for %s/%u", inet_ntoa(r->prefix),
209
		    r->prefixlen);
210
		free(r);
211
		return (-1);
212
	}
213
214
	return (0);
215
}
216
217
int
218
rt_remove(struct rt_node *r)
219
{
220
	struct ds_nbr	*ds_nbr;
221
222
	if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
223
		log_warnx("rt_remove failed for %s/%u",
224
		    inet_ntoa(r->prefix), r->prefixlen);
225
		return (-1);
226
	}
227
228
	while ((ds_nbr = LIST_FIRST(&r->ds_list)) != NULL) {
229
		LIST_REMOVE(ds_nbr, entry);
230
		free(ds_nbr);
231
	}
232
233
	free(r);
234
	return (0);
235
}
236
237
void
238
rt_invalidate(void)
239
{
240
	struct rt_node	*r, *nr;
241
242
	for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) {
243
		nr = RB_NEXT(rt_tree, &rt, r);
244
		if (r->invalid)
245
			rt_remove(r);
246
		else
247
			r->invalid = 1;
248
	}
249
}
250
251
void
252
rt_clear(void)
253
{
254
	struct rt_node	*r;
255
256
	while ((r = RB_MIN(rt_tree, &rt)) != NULL)
257
		rt_remove(r);
258
}
259
260
void
261
rt_snap(u_int32_t peerid)
262
{
263
	struct rt_node		*r;
264
	struct route_report	 rr;
265
266
	RB_FOREACH(r, rt_tree, &rt) {
267
		if (r->invalid)
268
			continue;
269
270
		rr.net = r->prefix;
271
		rr.mask.s_addr = ntohl(prefixlen2mask(r->prefixlen));
272
		rr.metric = r->cost;
273
		rr.ifindex = r->ifindex;
274
		rde_imsg_compose_dvmrpe(IMSG_FULL_ROUTE_REPORT, peerid, 0, &rr,
275
		    sizeof(rr));
276
	}
277
}
278
279
void
280
rt_dump(pid_t pid)
281
{
282
	static struct ctl_rt	 rtctl;
283
	struct timespec		 now;
284
	struct timeval		 tv, now2, res;
285
	struct rt_node		*r;
286
287
	clock_gettime(CLOCK_MONOTONIC, &now);
288
289
	RB_FOREACH(r, rt_tree, &rt) {
290
		if (r->invalid)
291
			continue;
292
293
		rtctl.prefix.s_addr = r->prefix.s_addr;
294
		rtctl.nexthop.s_addr = r->nexthop.s_addr;
295
		rtctl.cost = r->cost;
296
		rtctl.flags = r->flags;
297
		rtctl.prefixlen = r->prefixlen;
298
		rtctl.uptime = now.tv_sec - r->uptime;
299
300
		gettimeofday(&now2, NULL);
301
		if (evtimer_pending(&r->expiration_timer, &tv)) {
302
			timersub(&tv, &now2, &res);
303
			rtctl.expire = res.tv_sec;
304
		} else
305
			rtctl.expire = -1;
306
307
		rde_imsg_compose_dvmrpe(IMSG_CTL_SHOW_RIB, 0, pid, &rtctl,
308
		    sizeof(rtctl));
309
	}
310
}
311
312
void
313
rt_update(struct rt_node *rn)
314
{
315
	if (!rn->connected)
316
		rt_start_expire_timer(rn);
317
}
318
319
struct rt_node *
320
rt_match_origin(in_addr_t src)
321
{
322
	struct rt_node	*r;
323
324
	RB_FOREACH(r, rt_tree, &rt) {
325
		if (r->prefix.s_addr == (src &
326
		    htonl(prefixlen2mask(r->prefixlen))))
327
			return (r);
328
	}
329
330
	return (NULL);
331
}
332
333
int
334
srt_check_route(struct route_report *rr, int connected)
335
{
336
	struct rt_node		*rn;
337
	struct iface		*iface;
338
	struct ds_nbr		*ds_nbr;
339
	u_int32_t		 adj_metric;
340
	u_int32_t		 nbr_ip, nbr_report, ifindex;
341
342
	if ((iface = if_find_index(rr->ifindex)) == NULL)
343
		return (-1);
344
345
	ifindex = iface->ifindex;
346
347
	/* Interpret special case 0.0.0.0/8 as 0.0.0.0/0 */
348
	if (rr->net.s_addr == 0)
349
		rr->mask.s_addr = 0;
350
351
	if (connected)
352
		adj_metric = rr->metric;
353
	else
354
		adj_metric = rr->metric + iface->metric;
355
356
	if (adj_metric > INFINITY_METRIC)
357
		adj_metric = INFINITY_METRIC;
358
359
	/* If the route is new and the Adjusted Metric is less than infinity,
360
	   the route should be added. */
361
	rn = rt_find(rr->net.s_addr, mask2prefixlen(rr->mask.s_addr));
362
	if (rn == NULL) {
363
		if (adj_metric < INFINITY_METRIC) {
364
			rn = rr_new_rt(rr, adj_metric, connected);
365
			rt_insert(rn);
366
		}
367
		return (0);
368
	}
369
370
	/* If the route is connected accept only downstream neighbors reports */
371
	if (rn->connected && rr->metric <= INFINITY_METRIC)
372
		return (0);
373
374
	nbr_ip = rn->nexthop.s_addr;
375
	nbr_report = rr->nexthop.s_addr;
376
377
	if (rr->metric < INFINITY_METRIC) {
378
		/* If it is our current nexthop it cannot be a
379
		 * downstream router */
380
		if (nbr_ip != nbr_report)
381
			if ((ds_nbr = srt_find_ds(rn, nbr_report)))
382
				srt_delete_ds(rn, ds_nbr, iface);
383
384
		if (adj_metric > rn->cost) {
385
			if (nbr_ip == nbr_report) {
386
				rn->cost = adj_metric;
387
				flash_update_ds(rn);
388
			}
389
		} else if (adj_metric < rn->cost) {
390
			rn->cost = adj_metric;
391
			if (nbr_ip != nbr_report) {
392
				rn->nexthop.s_addr = nbr_report;
393
				srt_set_upstream(rn, ifindex);
394
				flash_update(rn);
395
			}
396
			/* We have a new best route to source, update the
397
			 * designated forwarders on downstream interfaces to
398
			 * reflect the new metric */
399
			srt_update_ds_forwarders(rn, iface, nbr_report);
400
		} else {
401
			if (nbr_report < nbr_ip) {
402
				rn->nexthop.s_addr = nbr_report;
403
				srt_set_upstream(rn, ifindex);
404
				flash_update(rn);
405
			} else if (nbr_report == nbr_ip &&
406
			    adj_metric == rn->old_cost)
407
				rt_update(rn);
408
				flash_update_ds(rn);
409
		}
410
		/* Update forwarder of current interface if necessary and
411
		 * refresh the route */
412
		srt_current_forwarder(rn, iface, rr->metric, nbr_report);
413
		rt_update(rn);
414
	} else if (rr->metric == INFINITY_METRIC) {
415
		if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr)
416
			srt_set_forwarder_self(rn, iface);
417
infinity:
418
		if (nbr_ip == nbr_report) {
419
			if (rn->cost < INFINITY_METRIC)
420
				rt_start_holddown_timer(rn);
421
		} else
422
			if ((ds_nbr = srt_find_ds(rn, nbr_report)))
423
				srt_delete_ds(rn, ds_nbr, iface);
424
	} else if (INFINITY_METRIC < rr->metric &&
425
	    rr->metric < 2 * INFINITY_METRIC) {
426
		/* Neighbor is reporting his dependency for this source */
427
		if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr)
428
			srt_set_forwarder_self(rn, iface);
429
430
		if (rn->ifindex == ifindex)
431
			goto infinity;
432
		else
433
			if (srt_find_ds(rn, nbr_report) == NULL)
434
				srt_add_ds(rn, nbr_report, ifindex);
435
	}
436
437
	return (0);
438
}
439
440
void
441
srt_current_forwarder(struct rt_node *rn, struct iface *iface,
442
    u_int32_t metric, u_int32_t nbr_report)
443
{
444
	struct adv_rtr *adv = &rn->adv_rtr[iface->ifindex];
445
446
	if (nbr_report == adv->addr.s_addr) {
447
		if (metric > rn->cost || (metric == rn->cost &&
448
		    iface->addr.s_addr < nbr_report))
449
			srt_set_forwarder_self(rn, iface);
450
451
	} else {
452
		if (metric < adv->metric ||
453
		    (metric == adv->metric && nbr_report < adv->addr.s_addr))
454
			if (adv->addr.s_addr == iface->addr.s_addr)
455
				rn->ttls[iface->ifindex] = 0;
456
457
		adv->addr.s_addr = nbr_report;
458
		adv->metric = metric;
459
460
		mfc_update_source(rn);
461
	}
462
463
}
464
465
void
466
srt_update_ds_forwarders(struct rt_node *rn, struct iface *iface,
467
    u_int32_t nbr_report)
468
{
469
	struct iface	*ifa;
470
	int		 i;
471
472
	for (i = 0; i < MAXVIFS; i++) {
473
		if (rn->adv_rtr[i].addr.s_addr &&
474
		    (rn->cost < rn->adv_rtr[i].metric ||
475
		    (rn->cost == rn->adv_rtr[i].metric &&
476
		    iface->addr.s_addr < nbr_report))) {
477
			ifa = if_find_index(i);
478
			srt_set_forwarder_self(rn, ifa);
479
		}
480
	}
481
}
482
483
void
484
srt_set_forwarder_self(struct rt_node *rn, struct iface *iface)
485
{
486
	rn->adv_rtr[iface->ifindex].addr.s_addr = iface->addr.s_addr;
487
	rn->adv_rtr[iface->ifindex].metric = rn->cost;
488
	rn->ttls[iface->ifindex] = 1;
489
490
	mfc_update_source(rn);
491
}
492
493
void
494
srt_set_upstream(struct rt_node *rn, u_int32_t ifindex)
495
{
496
	if (rn->ifindex != ifindex) {
497
		rn->ttls[rn->ifindex] = 1;
498
		rn->ifindex = ifindex;
499
	}
500
501
	mfc_update_source(rn);
502
}
503
504
void
505
srt_add_ds(struct rt_node *rn, u_int32_t nbr_report, u_int32_t ifindex)
506
{
507
	struct ds_nbr	*ds_nbr;
508
509
	log_debug("srt_add_ds: adding downstream router for source %s/%d",
510
	    inet_ntoa(rn->prefix), rn->prefixlen);
511
512
	if ((ds_nbr = malloc(sizeof(struct ds_nbr))) == NULL)
513
		fatal("srt_add_ds");
514
515
	ds_nbr->addr.s_addr = nbr_report;
516
517
	LIST_INSERT_HEAD(&rn->ds_list, ds_nbr, entry);
518
	rn->ds_cnt[ifindex]++;
519
	rn->ttls[ifindex] = 1;
520
521
	mfc_update_source(rn);
522
}
523
524
struct ds_nbr *
525
srt_find_ds(struct rt_node *rn, u_int32_t nbr_report)
526
{
527
	struct ds_nbr	*ds_nbr;
528
529
	LIST_FOREACH(ds_nbr, &rn->ds_list, entry)
530
		if (ds_nbr->addr.s_addr == nbr_report)
531
			return (ds_nbr);
532
533
	return (NULL);
534
}
535
536
void
537
srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface)
538
{
539
	log_debug("srt_delete_ds: deleting downstream router for source %s/%d",
540
	    inet_ntoa(rn->prefix), rn->prefixlen);
541
542
	LIST_REMOVE(ds_nbr, entry);
543
	free(ds_nbr);
544
	rn->ds_cnt[iface->ifindex]--;
545
546
	srt_check_downstream_ifaces(rn, iface);
547
}
548
549
void
550
srt_check_downstream_ifaces(struct rt_node *rn, struct iface *iface)
551
{
552
	/* We are not the designated forwarder for this source on this
553
	   interface. Keep things as they currently are */
554
	if (rn->adv_rtr[iface->ifindex].addr.s_addr != iface->addr.s_addr)
555
		return;
556
557
	/* There are still downstream dependent router for this source
558
	   Keep things as they currently are */
559
	if (rn->ds_cnt[iface->ifindex])
560
		return;
561
562
	/* There are still group members for this source on this iface
563
	   Keep things as they currently are */
564
	if (mfc_check_members(rn, iface))
565
		return;
566
567
	/* Remove interface from the downstream list */
568
	rn->ttls[iface->ifindex] = 0;
569
	mfc_update_source(rn);
570
}
571
572
void
573
srt_expire_nbr(struct in_addr addr, unsigned int ifindex)
574
{
575
	struct ds_nbr		*ds;
576
	struct rt_node		*rn;
577
	struct iface		*iface;
578
579
	iface = if_find_index(ifindex);
580
	if (iface == NULL)
581
		fatal("srt_expire_nbr: interface not found");
582
583
	RB_FOREACH(rn, rt_tree, &rt) {
584
		if (rn->adv_rtr[ifindex].addr.s_addr == addr.s_addr) {
585
			rn->adv_rtr[ifindex].addr.s_addr =
586
			    iface->addr.s_addr;
587
			rn->adv_rtr[ifindex].metric = rn->cost;
588
			/* XXX: delete all routes learned from this nbr */
589
		} else if (rn->adv_rtr[ifindex].addr.s_addr ==
590
		    iface->addr.s_addr) {
591
			ds = srt_find_ds(rn, addr.s_addr);
592
			if (ds) {
593
				srt_delete_ds(rn, ds, iface);
594
				srt_check_downstream_ifaces(rn, iface);
595
			}
596
		}
597
	}
598
}
599
600
void
601
flash_update(struct rt_node *rn) {
602
	struct route_report	rr;
603
604
	rr.net = rn->prefix;
605
	rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen));
606
	rr.metric = rn->cost;
607
	rr.ifindex = rn->ifindex;
608
	rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE, 0, 0, &rr, sizeof(rr));
609
}
610
611
void
612
flash_update_ds(struct rt_node *rn) {
613
	struct route_report	rr;
614
615
	rr.net = rn->prefix;
616
	rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen));
617
	rr.metric = rn->cost;
618
	rr.ifindex = rn->ifindex;
619
	rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE_DS, 0, 0, &rr, sizeof(rr));
620
}