GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/mrouted/route.c Lines: 0 423 0.0 %
Date: 2017-11-13 Branches: 0 292 0.0 %

Line Branch Exec Source
1
/*	$NetBSD: route.c,v 1.5 1995/12/10 10:07:12 mycroft Exp $	*/
2
3
/*
4
 * The mrouted program is covered by the license in the accompanying file
5
 * named "LICENSE".  Use of the mrouted program represents acceptance of
6
 * the terms and conditions listed in that file.
7
 *
8
 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
9
 * Leland Stanford Junior University.
10
 */
11
12
13
#include "defs.h"
14
15
16
/*
17
 * This define statement saves a lot of space later
18
 */
19
#define RT_ADDR	(struct rtentry *)&routing_table
20
21
/*
22
 * Exported variables.
23
 */
24
int routes_changed;			/* 1=>some routes have changed */
25
int delay_change_reports;		/* 1=>postpone change reports  */
26
27
28
/*
29
 * The routing table is shared with prune.c , so must not be static.
30
 */
31
struct rtentry *routing_table;		/* pointer to list of route entries */
32
33
/*
34
 * Private variables.
35
 */
36
static struct rtentry *rtp;		/* pointer to a route entry         */
37
static struct rtentry *rt_end;		/* pointer to last route entry      */
38
unsigned int nroutes;			/* current number of route entries  */
39
40
/*
41
 * Private functions.
42
 */
43
static int init_children_and_leaves(struct rtentry *r, vifi_t parent);
44
static int find_route(u_int32_t origin, u_int32_t mask);
45
static void create_route(u_int32_t origin, u_int32_t mask);
46
static void discard_route(struct rtentry *prev_r);
47
static int compare_rts(const void *rt1, const void *rt2);
48
static int report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst);
49
50
/*
51
 * Initialize the routing table and associated variables.
52
 */
53
void
54
init_routes()
55
{
56
    routing_table        = NULL;
57
    rt_end		 = RT_ADDR;
58
    nroutes		 = 0;
59
    routes_changed       = FALSE;
60
    delay_change_reports = FALSE;
61
}
62
63
64
/*
65
 * Initialize the children and leaf bits for route 'r', along with the
66
 * associated dominant, subordinate, and leaf timing data structures.
67
 * Return TRUE if this changes the value of either the children or
68
 * leaf bitmaps for 'r'.
69
 */
70
static int
71
init_children_and_leaves(struct rtentry *r, vifi_t parent)
72
{
73
    vifi_t vifi;
74
    struct uvif *v;
75
    vifbitmap_t old_children, old_leaves;
76
77
    VIFM_COPY(r->rt_children, old_children);
78
    VIFM_COPY(r->rt_leaves,   old_leaves  );
79
80
    VIFM_CLRALL(r->rt_children);
81
    VIFM_CLRALL(r->rt_leaves);
82
    r->rt_flags &= ~RTF_LEAF_TIMING;
83
84
    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
85
	r->rt_dominants   [vifi] = 0;
86
	r->rt_subordinates[vifi] = 0;
87
88
	if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED))) {
89
	    VIFM_SET(vifi, r->rt_children);
90
	    if (v->uv_neighbors == NULL) {
91
		VIFM_SET(vifi, r->rt_leaves);
92
		r->rt_leaf_timers[vifi] = 0;
93
	    }
94
	    else {
95
		r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
96
		r->rt_flags |= RTF_LEAF_TIMING;
97
	    }
98
	}
99
	else {
100
	    r->rt_leaf_timers[vifi] = 0;
101
	}
102
    }
103
104
    return (!VIFM_SAME(r->rt_children, old_children) ||
105
	    !VIFM_SAME(r->rt_leaves,   old_leaves));
106
}
107
108
109
/*
110
 * A new vif has come up -- update the children and leaf bitmaps in all route
111
 * entries to take that into account.
112
 */
113
void
114
add_vif_to_routes(vifi_t vifi)
115
{
116
    struct rtentry *r;
117
    struct uvif *v;
118
119
    v = &uvifs[vifi];
120
    for (r = routing_table; r != NULL; r = r->rt_next) {
121
	if (r->rt_metric != UNREACHABLE &&
122
	    !VIFM_ISSET(vifi, r->rt_children)) {
123
	    VIFM_SET(vifi, r->rt_children);
124
	    r->rt_dominants   [vifi] = 0;
125
	    r->rt_subordinates[vifi] = 0;
126
	    if (v->uv_neighbors == NULL) {
127
		VIFM_SET(vifi, r->rt_leaves);
128
		r->rt_leaf_timers[vifi] = 0;
129
	    }
130
	    else {
131
		VIFM_CLR(vifi, r->rt_leaves);
132
		r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
133
		r->rt_flags |= RTF_LEAF_TIMING;
134
	    }
135
	    update_table_entry(r);
136
	}
137
    }
138
}
139
140
141
/*
142
 * A vif has gone down -- expire all routes that have that vif as parent,
143
 * and update the children bitmaps in all other route entries to take into
144
 * account the failed vif.
145
 */
146
void
147
delete_vif_from_routes(vifi_t vifi)
148
{
149
    struct rtentry *r;
150
151
    for (r = routing_table; r != NULL; r = r->rt_next) {
152
	if (r->rt_metric != UNREACHABLE) {
153
	    if (vifi == r->rt_parent) {
154
		del_table_entry(r, 0, DEL_ALL_ROUTES);
155
		r->rt_timer    = ROUTE_EXPIRE_TIME;
156
		r->rt_metric   = UNREACHABLE;
157
		r->rt_flags   |= RTF_CHANGED;
158
		routes_changed = TRUE;
159
	    }
160
	    else if (VIFM_ISSET(vifi, r->rt_children)) {
161
		VIFM_CLR(vifi, r->rt_children);
162
		VIFM_CLR(vifi, r->rt_leaves);
163
		r->rt_subordinates[vifi] = 0;
164
		r->rt_leaf_timers [vifi] = 0;
165
		update_table_entry(r);
166
	    }
167
	    else {
168
		r->rt_dominants[vifi] = 0;
169
	    }
170
	}
171
    }
172
}
173
174
175
/*
176
 * A neighbor has failed or become unreachable.  If that neighbor was
177
 * considered a dominant or subordinate router in any route entries,
178
 * take appropriate action.
179
 */
180
void
181
delete_neighbor_from_routes(u_int32_t addr, vifi_t vifi)
182
{
183
    struct rtentry *r;
184
    struct uvif *v;
185
186
    v = &uvifs[vifi];
187
    for (r = routing_table; r != NULL; r = r->rt_next) {
188
	if (r->rt_metric != UNREACHABLE) {
189
	    if (r->rt_dominants[vifi] == addr) {
190
		VIFM_SET(vifi, r->rt_children);
191
		r->rt_dominants   [vifi] = 0;
192
		r->rt_subordinates[vifi] = 0;
193
		if (v->uv_neighbors == NULL) {
194
		    VIFM_SET(vifi, r->rt_leaves);
195
		    r->rt_leaf_timers[vifi] = 0;
196
		}
197
		else {
198
		    VIFM_CLR(vifi, r->rt_leaves);
199
		    r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
200
		    r->rt_flags |= RTF_LEAF_TIMING;
201
		}
202
		update_table_entry(r);
203
	    }
204
	    else if (r->rt_subordinates[vifi] == addr) {
205
		r->rt_subordinates[vifi] = 0;
206
		if (v->uv_neighbors == NULL) {
207
		    VIFM_SET(vifi, r->rt_leaves);
208
		    update_table_entry(r);
209
		}
210
		else {
211
		    r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
212
		    r->rt_flags |= RTF_LEAF_TIMING;
213
		}
214
	    }
215
	    else if (v->uv_neighbors == NULL &&
216
		     r->rt_leaf_timers[vifi] != 0) {
217
		VIFM_SET(vifi, r->rt_leaves);
218
		r->rt_leaf_timers[vifi] = 0;
219
		update_table_entry(r);
220
	    }
221
	}
222
    }
223
}
224
225
226
/*
227
 * Prepare for a sequence of ordered route updates by initializing a pointer
228
 * to the start of the routing table.  The pointer is used to remember our
229
 * position in the routing table in order to avoid searching from the
230
 * beginning for each update; this relies on having the route reports in
231
 * a single message be in the same order as the route entries in the routing
232
 * table.
233
 */
234
void
235
start_route_updates(void)
236
{
237
    rtp = RT_ADDR;
238
}
239
240
241
/*
242
 * Starting at the route entry following the one to which 'rtp' points,
243
 * look for a route entry matching the specified origin and mask.  If a
244
 * match is found, return TRUE and leave 'rtp' pointing at the found entry.
245
 * If no match is found, return FALSE and leave 'rtp' pointing to the route
246
 * entry preceding the point at which the new origin should be inserted.
247
 * This code is optimized for the normal case in which the first entry to
248
 * be examined is the matching entry.
249
 */
250
static int
251
find_route(u_int32_t origin, u_int32_t mask)
252
{
253
    struct rtentry *r;
254
255
    r = rtp->rt_next;
256
    while (r != NULL) {
257
	if (origin == r->rt_origin && mask == r->rt_originmask) {
258
	    rtp = r;
259
	    return (TRUE);
260
	}
261
	if (ntohl(mask) < ntohl(r->rt_originmask) ||
262
	    (mask == r->rt_originmask &&
263
	     ntohl(origin) < ntohl(r->rt_origin))) {
264
	    rtp = r;
265
	    r = r->rt_next;
266
	}
267
	else break;
268
    }
269
    return (FALSE);
270
}
271
272
/*
273
 * Create a new routing table entry for the specified origin and link it into
274
 * the routing table.  The shared variable 'rtp' is assumed to point to the
275
 * routing entry after which the new one should be inserted.  It is left
276
 * pointing to the new entry.
277
 *
278
 * Only the origin, originmask, originwidth and flags fields are initialized
279
 * in the new route entry; the caller is responsible for filling in the rest.
280
 */
281
static void
282
create_route(u_int32_t origin, u_int32_t mask)
283
{
284
    struct rtentry *r;
285
286
    if ((r = malloc(sizeof(struct rtentry) +
287
	(2 * numvifs * sizeof(u_int32_t)) +
288
	(numvifs * sizeof(u_int)))) == NULL) {
289
	logit(LOG_ERR, 0, "ran out of memory");	/* fatal */
290
    }
291
    r->rt_origin     = origin;
292
    r->rt_originmask = mask;
293
    if      (((char *)&mask)[3] != 0) r->rt_originwidth = 4;
294
    else if (((char *)&mask)[2] != 0) r->rt_originwidth = 3;
295
    else if (((char *)&mask)[1] != 0) r->rt_originwidth = 2;
296
    else                              r->rt_originwidth = 1;
297
    r->rt_flags        = 0;
298
    r->rt_dominants    = (u_int32_t *)(r + 1);
299
    r->rt_subordinates = (u_int32_t *)(r->rt_dominants + numvifs);
300
    r->rt_leaf_timers  = (u_int *)(r->rt_subordinates + numvifs);
301
    r->rt_groups       = NULL;
302
303
    r->rt_next = rtp->rt_next;
304
    rtp->rt_next = r;
305
    r->rt_prev = rtp;
306
    if (r->rt_next != NULL)
307
      (r->rt_next)->rt_prev = r;
308
    else
309
      rt_end = r;
310
    rtp = r;
311
    ++nroutes;
312
}
313
314
315
/*
316
 * Discard the routing table entry following the one to which 'prev_r' points.
317
 */
318
static void
319
discard_route(struct rtentry *prev_r)
320
{
321
    struct rtentry *r;
322
323
    r = prev_r->rt_next;
324
    prev_r->rt_next = r->rt_next;
325
    if (prev_r->rt_next != NULL)
326
      (prev_r->rt_next)->rt_prev = prev_r;
327
    else
328
      rt_end = prev_r;
329
    free((char *)r);
330
    --nroutes;
331
}
332
333
334
/*
335
 * Process a route report for a single origin, creating or updating the
336
 * corresponding routing table entry if necessary.  'src' is either the
337
 * address of a neighboring router from which the report arrived, or zero
338
 * to indicate a change of status of one of our own interfaces.
339
 */
340
void
341
update_route(u_int32_t origin, u_int32_t mask, u_int metric, u_int32_t src,
342
    vifi_t vifi)
343
{
344
    struct rtentry *r;
345
    u_int adj_metric;
346
347
    /*
348
     * Compute an adjusted metric, taking into account the cost of the
349
     * subnet or tunnel over which the report arrived, and normalizing
350
     * all unreachable/poisoned metrics into a single value.
351
     */
352
    if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
353
	logit(LOG_WARNING, 0,
354
	    "%s reports out-of-range metric %u for origin %s",
355
	    inet_fmt(src, s1), metric, inet_fmts(origin, mask, s2));
356
	return;
357
    }
358
    adj_metric = metric + uvifs[vifi].uv_metric;
359
    if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;
360
361
    /*
362
     * Look up the reported origin in the routing table.
363
     */
364
    if (!find_route(origin, mask)) {
365
	/*
366
	 * Not found.
367
	 * Don't create a new entry if the report says it's unreachable,
368
	 * or if the reported origin and mask are invalid.
369
	 */
370
	if (adj_metric == UNREACHABLE) {
371
	    return;
372
	}
373
	if (src != 0 && !inet_valid_subnet(origin, mask)) {
374
	    logit(LOG_WARNING, 0,
375
		"%s reports an invalid origin (%s) and/or mask (%08x)",
376
		inet_fmt(src, s1), inet_fmt(origin, s2), ntohl(mask));
377
	    return;
378
	}
379
380
	/*
381
	 * OK, create the new routing entry.  'rtp' will be left pointing
382
	 * to the new entry.
383
	 */
384
	create_route(origin, mask);
385
386
	/*
387
	 * Now "steal away" any sources that belong under this route
388
	 * by deleting any cache entries they might have created
389
	 * and allowing the kernel to re-request them.
390
	 */
391
	steal_sources(rtp);
392
393
	rtp->rt_metric = UNREACHABLE;	/* temporary; updated below */
394
    }
395
396
    /*
397
     * We now have a routing entry for the reported origin.  Update it?
398
     */
399
    r = rtp;
400
    if (r->rt_metric == UNREACHABLE) {
401
	/*
402
	 * The routing entry is for a formerly-unreachable or new origin.
403
	 * If the report claims reachability, update the entry to use
404
	 * the reported route.
405
	 */
406
	if (adj_metric == UNREACHABLE)
407
	    return;
408
409
	r->rt_parent   = vifi;
410
	init_children_and_leaves(r, vifi);
411
412
	r->rt_gateway  = src;
413
	r->rt_timer    = 0;
414
	r->rt_metric   = adj_metric;
415
	r->rt_flags   |= RTF_CHANGED;
416
	routes_changed = TRUE;
417
	update_table_entry(r);
418
    }
419
    else if (src == r->rt_gateway) {
420
	/*
421
	 * The report has come either from the interface directly-connected
422
	 * to the origin subnet (src and r->rt_gateway both equal zero) or
423
	 * from the gateway we have chosen as the best first-hop gateway back
424
	 * towards the origin (src and r->rt_gateway not equal zero).  Reset
425
	 * the route timer and, if the reported metric has changed, update
426
	 * our entry accordingly.
427
	 */
428
	r->rt_timer = 0;
429
	if (adj_metric == r->rt_metric)
430
	    return;
431
432
	if (adj_metric == UNREACHABLE) {
433
	    del_table_entry(r, 0, DEL_ALL_ROUTES);
434
	    r->rt_timer = ROUTE_EXPIRE_TIME;
435
	}
436
	else if (adj_metric < r->rt_metric) {
437
	    if (init_children_and_leaves(r, vifi)) {
438
		update_table_entry(r);
439
	    }
440
	}
441
	r->rt_metric   = adj_metric;
442
	r->rt_flags   |= RTF_CHANGED;
443
	routes_changed = TRUE;
444
    }
445
    else if (src == 0 ||
446
	     (r->rt_gateway != 0 &&
447
	      (adj_metric < r->rt_metric ||
448
	       (adj_metric == r->rt_metric &&
449
		(ntohl(src) < ntohl(r->rt_gateway) ||
450
		 r->rt_timer >= ROUTE_SWITCH_TIME))))) {
451
	/*
452
	 * The report is for an origin we consider reachable; the report
453
	 * comes either from one of our own interfaces or from a gateway
454
	 * other than the one we have chosen as the best first-hop gateway
455
	 * back towards the origin.  If the source of the update is one of
456
	 * our own interfaces, or if the origin is not a directly-connected
457
	 * subnet and the reported metric for that origin is better than
458
	 * what our routing entry says, update the entry to use the new
459
	 * gateway and metric.  We also switch gateways if the reported
460
	 * metric is the same as the one in the route entry and the gateway
461
	 * associated with the route entry has not been heard from recently,
462
	 * or if the metric is the same but the reporting gateway has a lower
463
	 * IP address than the gateway associated with the route entry.
464
	 * Did you get all that?
465
	 */
466
	if (r->rt_parent != vifi || adj_metric < r->rt_metric) {
467
	    /*
468
	     * XXX Why do we do this if we are just changing the metric?
469
	     */
470
	    r->rt_parent = vifi;
471
	    if (init_children_and_leaves(r, vifi)) {
472
		update_table_entry(r);
473
	    }
474
	}
475
	r->rt_gateway  = src;
476
	r->rt_timer    = 0;
477
	r->rt_metric   = adj_metric;
478
	r->rt_flags   |= RTF_CHANGED;
479
	routes_changed = TRUE;
480
    }
481
    else if (vifi != r->rt_parent) {
482
	/*
483
	 * The report came from a vif other than the route's parent vif.
484
	 * Update the children and leaf info, if necessary.
485
	 */
486
	if (VIFM_ISSET(vifi, r->rt_children)) {
487
	    /*
488
	     * Vif is a child vif for this route.
489
	     */
490
	    if (metric  < r->rt_metric ||
491
		(metric == r->rt_metric &&
492
		 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
493
		/*
494
		 * Neighbor has lower metric to origin (or has same metric
495
		 * and lower IP address) -- it becomes the dominant router,
496
		 * and vif is no longer a child for me.
497
		 */
498
		VIFM_CLR(vifi, r->rt_children);
499
		VIFM_CLR(vifi, r->rt_leaves);
500
		r->rt_dominants   [vifi] = src;
501
		r->rt_subordinates[vifi] = 0;
502
		r->rt_leaf_timers [vifi] = 0;
503
		update_table_entry(r);
504
	    }
505
	    else if (metric > UNREACHABLE) {	/* "poisoned reverse" */
506
		/*
507
		 * Neighbor considers this vif to be on path to route's
508
		 * origin; if no subordinate recorded, record this neighbor
509
		 * as subordinate and clear the leaf flag.
510
		 */
511
		if (r->rt_subordinates[vifi] == 0) {
512
		    VIFM_CLR(vifi, r->rt_leaves);
513
		    r->rt_subordinates[vifi] = src;
514
		    r->rt_leaf_timers [vifi] = 0;
515
		    update_table_entry(r);
516
		}
517
	    }
518
	    else if (src == r->rt_subordinates[vifi]) {
519
		/*
520
		 * Current subordinate no longer considers this vif to be on
521
		 * path to route's origin; it is no longer a subordinate
522
		 * router, and we set the leaf confirmation timer to give
523
		 * us time to hear from other subordinates.
524
		 */
525
		r->rt_subordinates[vifi] = 0;
526
		if (uvifs[vifi].uv_neighbors == NULL ||
527
		    uvifs[vifi].uv_neighbors->al_next == NULL) {
528
		    VIFM_SET(vifi, r->rt_leaves);
529
		    update_table_entry(r);
530
		}
531
		else {
532
		    r->rt_leaf_timers [vifi] = LEAF_CONFIRMATION_TIME;
533
		    r->rt_flags |= RTF_LEAF_TIMING;
534
		}
535
	    }
536
537
	}
538
	else if (src == r->rt_dominants[vifi] &&
539
		 (metric  > r->rt_metric ||
540
		  (metric == r->rt_metric &&
541
		   ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
542
	    /*
543
	     * Current dominant no longer has a lower metric to origin
544
	     * (or same metric and lower IP address); we adopt the vif
545
	     * as our own child.
546
	     */
547
	    VIFM_SET(vifi, r->rt_children);
548
	    r->rt_dominants  [vifi] = 0;
549
	    if (metric > UNREACHABLE) {
550
		r->rt_subordinates[vifi] = src;
551
	    }
552
	    else if (uvifs[vifi].uv_neighbors == NULL ||
553
		     uvifs[vifi].uv_neighbors->al_next == NULL) {
554
		VIFM_SET(vifi, r->rt_leaves);
555
	    }
556
	    else {
557
		r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
558
		r->rt_flags |= RTF_LEAF_TIMING;
559
	    }
560
	    update_table_entry(r);
561
	}
562
    }
563
}
564
565
566
/*
567
 * On every timer interrupt, advance the timer in each routing entry.
568
 */
569
void
570
age_routes(void)
571
{
572
    struct rtentry *r;
573
    struct rtentry *prev_r;
574
    vifi_t vifi;
575
576
    for (prev_r = RT_ADDR, r = routing_table;
577
	 r != NULL;
578
	 prev_r = r, r = r->rt_next) {
579
580
	if ((r->rt_timer += TIMER_INTERVAL) < ROUTE_EXPIRE_TIME) {
581
	    /*
582
	     * Route is still good; see if any leaf timers need to be
583
	     * advanced.
584
	     */
585
	    if (r->rt_flags & RTF_LEAF_TIMING) {
586
		r->rt_flags &= ~RTF_LEAF_TIMING;
587
		for (vifi = 0; vifi < numvifs; ++vifi) {
588
		    if (r->rt_leaf_timers[vifi] != 0) {
589
			/*
590
			 * Unlike other timers, leaf timers decrement.
591
			 */
592
			if ((r->rt_leaf_timers[vifi] -= TIMER_INTERVAL) == 0){
593
#ifdef NOTYET
594
			    /* If the vif is a physical leaf but has neighbors,
595
			     * it is not a tree leaf.  If I am a leaf, then no
596
			     * interface with neighbors is a tree leaf. */
597
			    if (!(((uvifs[vifi].uv_flags & VIFF_LEAF) ||
598
				   (vifs_with_neighbors == 1)) &&
599
				  (uvifs[vifi].uv_neighbors != NULL))) {
600
#endif
601
				VIFM_SET(vifi, r->rt_leaves);
602
				update_table_entry(r);
603
#ifdef NOTYET
604
			    }
605
#endif
606
			}
607
			else {
608
			    r->rt_flags |= RTF_LEAF_TIMING;
609
			}
610
		    }
611
		}
612
	    }
613
	}
614
	else if (r->rt_timer >= ROUTE_DISCARD_TIME) {
615
	    /*
616
	     * Time to garbage-collect the route entry.
617
	     */
618
	    del_table_entry(r, 0, DEL_ALL_ROUTES);
619
	    discard_route(prev_r);
620
	    r = prev_r;
621
	}
622
	else if (r->rt_metric != UNREACHABLE) {
623
	    /*
624
	     * Time to expire the route entry.  If the gateway is zero,
625
	     * i.e., it is a route to a directly-connected subnet, just
626
	     * set the timer back to zero; such routes expire only when
627
	     * the interface to the subnet goes down.
628
	     */
629
	    if (r->rt_gateway == 0) {
630
		r->rt_timer = 0;
631
	    }
632
	    else {
633
		del_table_entry(r, 0, DEL_ALL_ROUTES);
634
		r->rt_metric   = UNREACHABLE;
635
		r->rt_flags   |= RTF_CHANGED;
636
		routes_changed = TRUE;
637
	    }
638
	}
639
    }
640
}
641
642
643
/*
644
 * Mark all routes as unreachable.  This function is called only from
645
 * hup() in preparation for informing all neighbors that we are going
646
 * off the air.  For consistency, we ought also to delete all reachable
647
 * route entries from the kernel, but since we are about to exit we rely
648
 * on the kernel to do its own cleanup -- no point in making all those
649
 * expensive kernel calls now.
650
 */
651
void
652
expire_all_routes(void)
653
{
654
    struct rtentry *r;
655
656
    for (r = routing_table; r != NULL; r = r->rt_next) {
657
	r->rt_metric   = UNREACHABLE;
658
	r->rt_flags   |= RTF_CHANGED;
659
	routes_changed = TRUE;
660
    }
661
}
662
663
664
/*
665
 * Delete all the routes in the routing table.
666
 */
667
void
668
free_all_routes(void)
669
{
670
    struct rtentry *r;
671
672
    r = RT_ADDR;
673
674
    while (r->rt_next)
675
	discard_route(r);
676
}
677
678
679
/*
680
 * Process an incoming neighbor probe message.
681
 */
682
void
683
accept_probe(u_int32_t src, u_int32_t dst, char *p, int datalen,
684
    u_int32_t level)
685
{
686
    vifi_t vifi;
687
688
    if ((vifi = find_vif(src, dst)) == NO_VIF) {
689
	logit(LOG_INFO, 0,
690
	    "ignoring probe from non-neighbor %s", inet_fmt(src, s1));
691
	return;
692
    }
693
694
    update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
695
}
696
697
struct newrt {
698
	u_int32_t mask;
699
	u_int32_t origin;
700
	int metric;
701
	int pad;
702
};
703
704
static int
705
compare_rts(const void *rt1, const void *rt2)
706
{
707
    struct newrt *r1 = (struct newrt *)rt1;
708
    struct newrt *r2 = (struct newrt *)rt2;
709
    u_int32_t m1 = ntohl(r1->mask);
710
    u_int32_t m2 = ntohl(r2->mask);
711
    u_int32_t o1, o2;
712
713
    if (m1 > m2)
714
	return (-1);
715
    if (m1 < m2)
716
	return (1);
717
718
    /* masks are equal */
719
    o1 = ntohl(r1->origin);
720
    o2 = ntohl(r2->origin);
721
    if (o1 > o2)
722
	return (-1);
723
    if (o1 < o2)
724
	return (1);
725
    return (0);
726
}
727
728
/*
729
 * Process an incoming route report message.
730
 */
731
void
732
accept_report(u_int32_t src, u_int32_t dst, char *p, int datalen,
733
    u_int32_t level)
734
{
735
    vifi_t vifi;
736
    int width, i, nrt = 0;
737
    int metric;
738
    u_int32_t mask;
739
    u_int32_t origin;
740
    struct newrt rt[4096];
741
742
    if ((vifi = find_vif(src, dst)) == NO_VIF) {
743
	logit(LOG_INFO, 0,
744
	    "ignoring route report from non-neighbor %s", inet_fmt(src, s1));
745
	return;
746
    }
747
748
    if (!update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level))
749
	return;
750
751
    if (datalen > 2*4096) {
752
	logit(LOG_INFO, 0,
753
	    "ignoring oversize (%d bytes) route report from %s",
754
	    datalen, inet_fmt(src, s1));
755
	return;
756
    }
757
758
    while (datalen > 0) {	/* Loop through per-mask lists. */
759
760
	if (datalen < 3) {
761
	    logit(LOG_WARNING, 0,
762
		"received truncated route report from %s",
763
		inet_fmt(src, s1));
764
	    return;
765
	}
766
	((u_char *)&mask)[0] = 0xff;            width = 1;
767
	if ((((u_char *)&mask)[1] = *p++) != 0) width = 2;
768
	if ((((u_char *)&mask)[2] = *p++) != 0) width = 3;
769
	if ((((u_char *)&mask)[3] = *p++) != 0) width = 4;
770
	if (!inet_valid_mask(ntohl(mask))) {
771
	    logit(LOG_WARNING, 0,
772
		"%s reports bogus netmask 0x%08x (%s)",
773
		inet_fmt(src, s1), ntohl(mask), inet_fmt(mask, s2));
774
	    return;
775
	}
776
	datalen -= 3;
777
778
	do {			/* Loop through (origin, metric) pairs */
779
	    if (datalen < width + 1) {
780
		logit(LOG_WARNING, 0,
781
		    "received truncated route report from %s",
782
		    inet_fmt(src, s1));
783
		return;
784
	    }
785
	    origin = 0;
786
	    for (i = 0; i < width; ++i)
787
		((char *)&origin)[i] = *p++;
788
	    metric = *p++;
789
	    datalen -= width + 1;
790
	    rt[nrt].mask   = mask;
791
	    rt[nrt].origin = origin;
792
	    rt[nrt].metric = (metric & 0x7f);
793
	    ++nrt;
794
	} while (!(metric & 0x80));
795
    }
796
797
    qsort((char*)rt, nrt, sizeof(rt[0]), compare_rts);
798
    start_route_updates();
799
    /*
800
     * If the last entry is default, change mask from 0xff000000 to 0
801
     */
802
    if (rt[nrt-1].origin == 0)
803
	rt[nrt-1].mask = 0;
804
805
    logit(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt,
806
		inet_fmt(src, s1), inet_fmt(dst, s2));
807
    for (i = 0; i < nrt; ++i) {
808
	if (i != 0 && rt[i].origin == rt[i-1].origin &&
809
		      rt[i].mask == rt[i-1].mask) {
810
	    logit(LOG_WARNING, 0, "%s reports duplicate route for %s",
811
		inet_fmt(src, s1), inet_fmts(rt[i].origin, rt[i].mask, s2));
812
	    continue;
813
	}
814
	update_route(rt[i].origin, rt[i].mask, rt[i].metric,
815
		     src, vifi);
816
    }
817
818
    if (routes_changed && !delay_change_reports)
819
	report_to_all_neighbors(CHANGED_ROUTES);
820
}
821
822
823
/*
824
 * Send a route report message to destination 'dst', via virtual interface
825
 * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
826
 */
827
void
828
report(int which_routes, vifi_t vifi, u_int32_t dst)
829
{
830
    struct rtentry *r;
831
    char *p;
832
    int i;
833
    int datalen = 0;
834
    int width = 0;
835
    u_int32_t mask = 0;
836
    u_int32_t src;
837
    u_int32_t nflags;
838
839
    src = uvifs[vifi].uv_lcl_addr;
840
841
    p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
842
843
#ifdef NOTYET
844
    /* If I'm not a leaf, but the neighbor is a leaf, only advertise default */
845
    if ((vifs_with_neighbors != 1) && (uvifs[vifi].uv_flags & VIFF_LEAF)) {
846
      *p++ = 0;       /* 0xff000000 mask */
847
      *p++ = 0;
848
      *p++ = 0;
849
      *p++ = 0;       /* class A net 0.0.0.0 == default */
850
      *p++ = 0x81;    /*XXX metric 1, is this safe? */
851
      datalen += 5;
852
      send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
853
                htonl(MROUTED_LEVEL), datalen);
854
      return;
855
    }
856
#endif
857
858
    nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS;
859
860
    for (r = rt_end; r != RT_ADDR; r = r->rt_prev) {
861
862
	if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED))
863
	    continue;
864
865
	/*
866
	 * If there is no room for this route in the current message,
867
	 * send the message and start a new one.
868
	 */
869
	if (datalen + ((r->rt_originmask == mask) ?
870
		       (width + 1) :
871
		       (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
872
	    *(p-1) |= 0x80;
873
	    send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
874
		      htonl(MROUTED_LEVEL | nflags), datalen);
875
876
	    p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
877
	    datalen = 0;
878
	    mask = 0;
879
	}
880
881
	if (r->rt_originmask != mask || datalen == 0) {
882
	    mask  = r->rt_originmask;
883
	    width = r->rt_originwidth;
884
	    if (datalen != 0) *(p-1) |= 0x80;
885
	    *p++ = ((char *)&mask)[1];
886
	    *p++ = ((char *)&mask)[2];
887
	    *p++ = ((char *)&mask)[3];
888
	    datalen += 3;
889
	}
890
891
	for (i = 0; i < width; ++i)
892
	    *p++ = ((char *)&(r->rt_origin))[i];
893
894
	*p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ?
895
	    (char)(r->rt_metric + UNREACHABLE) :  /* "poisoned reverse" */
896
		(char)(r->rt_metric);
897
898
	datalen += width + 1;
899
    }
900
901
    if (datalen != 0) {
902
	*(p-1) |= 0x80;
903
	send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
904
		  htonl(MROUTED_LEVEL | nflags), datalen);
905
    }
906
}
907
908
909
/*
910
 * Send a route report message to all neighboring routers.
911
 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
912
 */
913
void
914
report_to_all_neighbors(int which_routes)
915
{
916
    vifi_t vifi;
917
    struct uvif *v;
918
    struct rtentry *r;
919
    int routes_changed_before;
920
921
    /*
922
     * Remember the state of the global routes_changed flag before
923
     * generating the reports, and clear the flag.
924
     */
925
    routes_changed_before = routes_changed;
926
    routes_changed = FALSE;
927
928
929
    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
930
	if (v->uv_neighbors != NULL) {
931
	    report(which_routes, vifi,
932
		   (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr
933
		   : dvmrp_group);
934
	}
935
    }
936
937
    /*
938
     * If there were changed routes before we sent the reports AND
939
     * if no new changes occurred while sending the reports, clear
940
     * the change flags in the individual route entries.  If changes
941
     * did occur while sending the reports, new reports will be
942
     * generated at the next timer interrupt.
943
     */
944
    if (routes_changed_before && !routes_changed) {
945
	for (r = routing_table; r != NULL; r = r->rt_next) {
946
	    r->rt_flags &= ~RTF_CHANGED;
947
	}
948
    }
949
950
    /*
951
     * Set a flag to inhibit further reports of changed routes until the
952
     * next timer interrupt.  This is to alleviate update storms.
953
     */
954
    delay_change_reports = TRUE;
955
}
956
957
/*
958
 * Send a route report message to destination 'dst', via virtual interface
959
 * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
960
 */
961
static int
962
report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst)
963
{
964
    struct rtentry *r;
965
    char *p;
966
    int i;
967
    int nrt = 0;
968
    int datalen = 0;
969
    int width = 0;
970
    u_int32_t mask = 0;
971
    u_int32_t src;
972
    u_int32_t nflags;
973
974
    src = uvifs[vifi].uv_lcl_addr;
975
    p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
976
977
    nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS;
978
979
    for (r = start_rt; r != RT_ADDR; r = r->rt_prev) {
980
981
#ifdef NOTYET
982
	/* Don't send poisoned routes back to parents if I am a leaf */
983
	if ((vifs_with_neighbors == 1) && (r->rt_parent == vifi)
984
		&& (r->rt_metric > 1)) {
985
	    ++nrt;
986
	    continue;
987
	}
988
#endif
989
990
	/*
991
	 * If there is no room for this route in the current message,
992
	 * send it & return how many routes we sent.
993
	 */
994
	if (datalen + ((r->rt_originmask == mask) ?
995
		       (width + 1) :
996
		       (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
997
	    *(p-1) |= 0x80;
998
	    send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
999
		      htonl(MROUTED_LEVEL | nflags), datalen);
1000
	    return (nrt);
1001
	}
1002
	if (r->rt_originmask != mask || datalen == 0) {
1003
	    mask  = r->rt_originmask;
1004
	    width = r->rt_originwidth;
1005
	    if (datalen != 0) *(p-1) |= 0x80;
1006
	    *p++ = ((char *)&mask)[1];
1007
	    *p++ = ((char *)&mask)[2];
1008
	    *p++ = ((char *)&mask)[3];
1009
	    datalen += 3;
1010
	}
1011
	for (i = 0; i < width; ++i)
1012
	    *p++ = ((char *)&(r->rt_origin))[i];
1013
1014
	*p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ?
1015
	    (char)(r->rt_metric + UNREACHABLE) :  /* "poisoned reverse" */
1016
		(char)(r->rt_metric);
1017
	++nrt;
1018
	datalen += width + 1;
1019
    }
1020
    if (datalen != 0) {
1021
	*(p-1) |= 0x80;
1022
	send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
1023
		  htonl(MROUTED_LEVEL | nflags), datalen);
1024
    }
1025
    return (nrt);
1026
}
1027
1028
/*
1029
 * send the next chunk of our routing table to all neighbors.
1030
 * return the length of the smallest chunk we sent out.
1031
 */
1032
int
1033
report_next_chunk(void)
1034
{
1035
    vifi_t vifi;
1036
    struct uvif *v;
1037
    struct rtentry *sr;
1038
    int i, n = 0, min = 20000;
1039
    static int start_rt;
1040
1041
    if (nroutes <= 0)
1042
	return (0);
1043
1044
    /*
1045
     * find this round's starting route.
1046
     */
1047
    for (sr = rt_end, i = start_rt; --i >= 0; ) {
1048
	sr = sr->rt_prev;
1049
	if (sr == RT_ADDR)
1050
	    sr = rt_end;
1051
    }
1052
1053
    /*
1054
     * send one chunk of routes starting at this round's start to
1055
     * all our neighbors.
1056
     */
1057
    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
1058
	if ((v->uv_neighbors != NULL)
1059
#ifdef NOTYET
1060
	&& !(v->uv_flags & VIFF_LEAF)
1061
#endif
1062
		) {
1063
	    n = report_chunk(sr, vifi,
1064
			     (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr
1065
			     : dvmrp_group);
1066
	    if (n < min)
1067
		min = n;
1068
	}
1069
    }
1070
    if (min == 20000)
1071
	min = 0;	/* Neighborless router didn't send any routes */
1072
1073
    n = min;
1074
    logit(LOG_INFO, 0, "update %d starting at %d of %d",
1075
	n, (nroutes - start_rt), nroutes);
1076
1077
    start_rt = (start_rt + n) % nroutes;
1078
    return (n);
1079
}
1080
1081
1082
/*
1083
 * Print the contents of the routing table on file 'fp'.
1084
 */
1085
void
1086
dump_routes(FILE *fp)
1087
{
1088
    struct rtentry *r;
1089
    vifi_t i;
1090
1091
1092
    fprintf(fp,
1093
	    "Multicast Routing Table (%u %s)\n%s\n",
1094
	    nroutes, (nroutes == 1) ? "entry" : "entries",
1095
	    " Origin-Subnet      From-Gateway    Metric Tmr In-Vif  Out-Vifs");
1096
1097
    for (r = routing_table; r != NULL; r = r->rt_next) {
1098
1099
	fprintf(fp, " %-18s %-15s ",
1100
		inet_fmts(r->rt_origin, r->rt_originmask, s1),
1101
		(r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway, s2));
1102
1103
	fprintf(fp, (r->rt_metric == UNREACHABLE) ? "  NR " : "%4u ",
1104
		r->rt_metric);
1105
1106
	fprintf(fp, "  %3u %3u   ", r->rt_timer, r->rt_parent);
1107
1108
	for (i = 0; i < numvifs; ++i) {
1109
	    if (VIFM_ISSET(i, r->rt_children)) {
1110
		fprintf(fp, " %u%c",
1111
			i, VIFM_ISSET(i, r->rt_leaves) ? '*' : ' ');
1112
	    }
1113
	}
1114
	fprintf(fp, "\n");
1115
    }
1116
    fprintf(fp, "\n");
1117
}
1118
1119
struct rtentry *
1120
determine_route(u_int32_t src)
1121
{
1122
    struct rtentry *rt;
1123
1124
    for (rt = routing_table; rt != NULL; rt = rt->rt_next) {
1125
	if (rt->rt_origin == (src & rt->rt_originmask))
1126
	    break;
1127
    }
1128
    return rt;
1129
}