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

Line Branch Exec Source
1
/*	$OpenBSD: rde_spf.c,v 1.25 2015/12/05 06:45:19 mmcc Exp $ */
2
3
/*
4
 * Copyright (c) 2005 Esben Norby <norby@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/socket.h>
21
#include <netinet/in.h>
22
#include <arpa/inet.h>
23
#include <err.h>
24
#include <stdlib.h>
25
#include <string.h>
26
27
#include "ospf6d.h"
28
#include "ospf6.h"
29
#include "log.h"
30
#include "rde.h"
31
32
extern struct ospfd_conf	*rdeconf;
33
TAILQ_HEAD(, vertex)		 cand_list;
34
RB_HEAD(rt_tree, rt_node)	 rt;
35
RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
36
RB_GENERATE(rt_tree, rt_node, entry, rt_compare)
37
struct vertex			*spf_root = NULL;
38
39
void		 calc_nexthop_clear(struct vertex *);
40
void		 calc_nexthop_add(struct vertex *, struct vertex *,
41
		     const struct in6_addr *, u_int32_t);
42
struct in6_addr	*calc_nexthop_lladdr(struct vertex *, struct lsa_rtr_link *,
43
		     unsigned int);
44
void		 calc_nexthop_transit_nbr(struct vertex *, struct vertex *,
45
		     unsigned int);
46
void		 calc_nexthop(struct vertex *, struct vertex *,
47
		     struct area *, struct lsa_rtr_link *);
48
void		 rt_nexthop_clear(struct rt_node *);
49
void		 rt_nexthop_add(struct rt_node *, struct v_nexthead *,
50
		     struct in_addr);
51
void		 rt_update(struct in6_addr *, u_int8_t, struct v_nexthead *,
52
		     u_int32_t, u_int32_t, struct in_addr, struct in_addr,
53
		     enum path_type, enum dst_type, u_int8_t, u_int32_t);
54
struct rt_node	*rt_lookup(enum dst_type, struct in6_addr *);
55
void		 rt_invalidate(struct area *);
56
int		 linked(struct vertex *, struct vertex *);
57
58
void
59
spf_calc(struct area *area)
60
{
61
	struct vertex		*v, *w;
62
	struct lsa_rtr_link	*rtr_link = NULL;
63
	struct lsa_net_link	*net_link;
64
	u_int32_t		 d;
65
	unsigned int		 i;
66
67
	/* clear SPF tree */
68
	spf_tree_clr(area);
69
	cand_list_clr();
70
71
	/* initialize SPF tree */
72
	if ((v = spf_root = lsa_find_rtr(area, rde_router_id())) == NULL)
73
		/* empty area because no interface is active */
74
		return;
75
76
	area->transit = 0;
77
	spf_root->cost = 0;
78
	w = NULL;
79
80
	/* calculate SPF tree */
81
	do {
82
		/* loop links */
83
		for (i = 0; i < lsa_num_links(v); i++) {
84
			switch (v->type) {
85
			case LSA_TYPE_ROUTER:
86
				rtr_link = get_rtr_link(v, i);
87
				switch (rtr_link->type) {
88
				case LINK_TYPE_POINTTOPOINT:
89
				case LINK_TYPE_VIRTUAL:
90
					/* find router LSA */
91
					w = lsa_find_rtr(area,
92
					    rtr_link->nbr_rtr_id);
93
					break;
94
				case LINK_TYPE_TRANSIT_NET:
95
					/* find network LSA */
96
					w = lsa_find_tree(&area->lsa_tree,
97
					    htons(LSA_TYPE_NETWORK),
98
					    rtr_link->nbr_iface_id,
99
					    rtr_link->nbr_rtr_id);
100
					break;
101
				default:
102
					fatalx("spf_calc: invalid link type");
103
				}
104
				break;
105
			case LSA_TYPE_NETWORK:
106
				net_link = get_net_link(v, i);
107
				/* find router LSA */
108
				w = lsa_find_rtr(area, net_link->att_rtr);
109
				break;
110
			default:
111
				fatalx("spf_calc: invalid LSA type");
112
			}
113
114
			if (w == NULL)
115
				continue;
116
117
			if (ntohs(w->lsa->hdr.age) == MAX_AGE)
118
				continue;
119
120
			if (lsa_num_links(w) == 0)
121
				continue;
122
123
			if (!linked(w, v)) {
124
				log_debug("spf_calc: w adv_rtr %s ls_id %s "
125
				    "type 0x%x numlinks %hu has no link to "
126
				    "v adv_rtr %s ls_id %s type 0x%x",
127
				    log_rtr_id(htonl(w->adv_rtr)),
128
				    log_rtr_id(htonl(w->ls_id)), w->type,
129
				    lsa_num_links(w),
130
				    log_rtr_id(htonl(v->adv_rtr)),
131
				    log_rtr_id(htonl(v->ls_id)), v->type);
132
				continue;
133
			}
134
135
			if (v->type == LSA_TYPE_ROUTER)
136
				d = v->cost + ntohs(rtr_link->metric);
137
			else
138
				d = v->cost;
139
140
			if (cand_list_present(w)) {
141
				if (d > w->cost)
142
					continue;
143
				if (d < w->cost) {
144
					w->cost = d;
145
					calc_nexthop_clear(w);
146
					calc_nexthop(w, v, area, rtr_link);
147
					/*
148
					 * need to readd to candidate list
149
					 * because the list is sorted
150
					 */
151
					TAILQ_REMOVE(&cand_list, w, cand);
152
					cand_list_add(w);
153
				} else
154
					/* equal cost path */
155
					calc_nexthop(w, v, area, rtr_link);
156
			} else if (w->cost == LS_INFINITY && d < LS_INFINITY) {
157
				w->cost = d;
158
159
				calc_nexthop_clear(w);
160
				calc_nexthop(w, v, area, rtr_link);
161
				cand_list_add(w);
162
			}
163
		}
164
165
		/* get next vertex */
166
		v = cand_list_pop();
167
		w = NULL;
168
	} while (v != NULL);
169
170
	/* spf_dump(area); */
171
	log_debug("spf_calc: area %s calculated", inet_ntoa(area->id));
172
173
	/* Dump SPF tree to log */
174
	RB_FOREACH(v, lsa_tree, &area->lsa_tree) {
175
		struct v_nexthop *vn;
176
		char hops[4096];
177
		struct iface *iface;
178
179
		bzero(hops, sizeof(hops));
180
181
		if (v->type != LSA_TYPE_ROUTER && v->type != LSA_TYPE_NETWORK)
182
			continue;
183
184
		TAILQ_FOREACH(vn, &v->nexthop, entry) {
185
			strlcat(hops, log_in6addr(&vn->nexthop), sizeof(hops));
186
			strlcat(hops, "%", sizeof(hops));
187
			if ((iface = if_find(vn->ifindex)) == NULL)
188
				fatalx("spf_calc: lost iface");
189
			strlcat(hops, iface->name, sizeof(hops));
190
			if (vn != TAILQ_LAST(&v->nexthop, v_nexthead))
191
				strlcat(hops, ", ", sizeof(hops));
192
		}
193
		log_debug("%s(%s, 0x%x, %s) cost %u has nexthops [%s]",
194
		    v == spf_root ? "*" : " ", log_rtr_id(htonl(v->adv_rtr)),
195
		    v->type, log_rtr_id(htonl(v->ls_id)), v->cost, hops);
196
	}
197
198
	area->num_spf_calc++;
199
	start_spf_timer();
200
}
201
202
void
203
rt_calc(struct vertex *v, struct area *area, struct ospfd_conf *conf)
204
{
205
	struct vertex		*w;
206
	struct lsa_intra_prefix	*iap;
207
	struct lsa_prefix	*prefix;
208
	struct in_addr		 adv_rtr;
209
	struct in6_addr		 ia6;
210
	u_int16_t		 i, off;
211
	u_int8_t		 flags;
212
213
	lsa_age(v);
214
	if (ntohs(v->lsa->hdr.age) == MAX_AGE)
215
		return;
216
217
	switch (v->type) {
218
	case LSA_TYPE_ROUTER:
219
		if (v->cost >= LS_INFINITY || TAILQ_EMPTY(&v->nexthop))
220
			return;
221
222
		/* router, only add border and as-external routers */
223
		flags = LSA_24_GETHI(ntohl(v->lsa->data.rtr.opts));
224
		if ((flags & (OSPF_RTR_B | OSPF_RTR_E)) == 0)
225
			return;
226
227
		bzero(&ia6, sizeof(ia6));
228
		adv_rtr.s_addr = htonl(v->adv_rtr);
229
		bcopy(&adv_rtr, &ia6.s6_addr[12], sizeof(adv_rtr));
230
231
		rt_update(&ia6, 128, &v->nexthop, v->cost, 0, area->id,
232
		    adv_rtr, PT_INTER_AREA, DT_RTR, flags, 0);
233
		break;
234
	case LSA_TYPE_INTRA_A_PREFIX:
235
		/* Find referenced LSA */
236
		iap = &v->lsa->data.pref_intra;
237
		switch (ntohs(iap->ref_type)) {
238
		case LSA_TYPE_ROUTER:
239
			w = lsa_find_rtr(area, iap->ref_adv_rtr);
240
			if (w == NULL) {
241
				warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) "
242
				    "references non-existent router %s",
243
				    log_rtr_id(htonl(v->adv_rtr)),
244
				    v->ls_id, log_rtr_id(iap->ref_adv_rtr));
245
				return;
246
			}
247
			flags = LSA_24_GETHI(ntohl(w->lsa->data.rtr.opts));
248
			break;
249
		case LSA_TYPE_NETWORK:
250
			w = lsa_find_tree(&area->lsa_tree, iap->ref_type,
251
			    iap->ref_ls_id, iap->ref_adv_rtr);
252
			if (w == NULL) {
253
				warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) "
254
				    "references non-existent Network LSA (%s, "
255
				    "%u)", log_rtr_id(htonl(v->adv_rtr)),
256
				    v->ls_id, log_rtr_id(iap->ref_adv_rtr),
257
				    ntohl(iap->ref_ls_id));
258
				return;
259
			}
260
			flags = 0;
261
			break;
262
		default:
263
			warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) has "
264
			    "invalid ref_type 0x%hx", log_rtr_id(v->adv_rtr),
265
			    v->ls_id, ntohs(iap->ref_type));
266
			return;
267
		}
268
269
		if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop))
270
			return;
271
272
		/* Add prefixes listed in Intra-Area-Prefix LSA to routing
273
		 * table, using w as destination. */
274
		off = sizeof(v->lsa->hdr) + sizeof(struct lsa_intra_prefix);
275
		for (i = 0; i < ntohs(v->lsa->data.pref_intra.numprefix); i++) {
276
			prefix = (struct lsa_prefix *)((char *)(v->lsa) + off);
277
			if (!(prefix->options & OSPF_PREFIX_NU)) {
278
				bzero(&ia6, sizeof(ia6));
279
				bcopy(prefix + 1, &ia6,
280
				    LSA_PREFIXSIZE(prefix->prefixlen));
281
282
				adv_rtr.s_addr = htonl(w->adv_rtr);
283
284
				rt_update(&ia6, prefix->prefixlen, &w->nexthop,
285
				    w->cost + ntohs(prefix->metric), 0,
286
				    area->id, adv_rtr, PT_INTRA_AREA, DT_NET,
287
				    flags, 0);
288
			}
289
			off += sizeof(struct lsa_prefix)
290
			    + LSA_PREFIXSIZE(prefix->prefixlen);
291
		}
292
		break;
293
	case LSA_TYPE_INTER_A_PREFIX:
294
		/* XXX if ABR only look at area 0.0.0.0 LSA */
295
		/* ignore self-originated stuff */
296
		if (v->self)
297
			return;
298
299
		adv_rtr.s_addr = htonl(v->adv_rtr);
300
		w = lsa_find_rtr(area, adv_rtr.s_addr);
301
		if (w == NULL) {
302
			warnx("rt_calc: Inter-Area-Router LSA (%s, %u) "
303
			    "originated from non-existent router",
304
			    log_rtr_id(htonl(v->adv_rtr)),
305
			    v->ls_id);
306
			return;
307
		}
308
		if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop))
309
			return;
310
311
		/* Add prefix listed in Inter-Area-Prefix LSA to routing
312
		 * table, using w as destination. */
313
		off = sizeof(v->lsa->hdr) + sizeof(struct lsa_prefix_sum);
314
		prefix = (struct lsa_prefix *)((char *)(v->lsa) + off);
315
		if (prefix->options & OSPF_PREFIX_NU)
316
			return;
317
318
		bzero(&ia6, sizeof(ia6));
319
		bcopy(prefix + 1, &ia6, LSA_PREFIXSIZE(prefix->prefixlen));
320
321
		rt_update(&ia6, prefix->prefixlen, &w->nexthop, w->cost +
322
		    (ntohs(v->lsa->data.rtr_sum.metric) & LSA_METRIC_MASK), 0,
323
		    area->id, adv_rtr, PT_INTER_AREA, DT_NET, 0, 0);
324
		break;
325
	case LSA_TYPE_INTER_A_ROUTER:
326
		/* XXX if ABR only look at area 0.0.0.0 LSA */
327
		/* ignore self-originated stuff */
328
		if (v->self)
329
			return;
330
331
		adv_rtr.s_addr = htonl(v->adv_rtr);
332
		w = lsa_find_rtr(area, adv_rtr.s_addr);
333
		if (w == NULL) {
334
			warnx("rt_calc: Inter-Area-Router LSA (%s, %u) "
335
			    "originated from non-existent router",
336
			    log_rtr_id(htonl(v->adv_rtr)),
337
			    v->ls_id);
338
			return;
339
		}
340
		if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop))
341
			return;
342
343
		/* Add router listed in Inter-Area-Router LSA to routing
344
		 * table, using w as destination. */
345
		bzero(&ia6, sizeof(ia6));
346
		bcopy(&v->lsa->data.rtr_sum.dest_rtr_id, &ia6.s6_addr[12],
347
		    4);
348
349
		rt_update(&ia6, 128, &w->nexthop, w->cost +
350
		    (ntohs(v->lsa->data.rtr_sum.metric) & LSA_METRIC_MASK), 0,
351
		    area->id, adv_rtr, PT_INTER_AREA, DT_RTR, 0, 0);
352
		break;
353
	default:
354
		break;
355
	}
356
}
357
358
void
359
asext_calc(struct vertex *v)
360
{
361
	struct in6_addr		 addr, fw_addr;
362
	struct rt_node		*r;
363
	struct rt_nexthop	*rn;
364
	struct lsa_prefix	*prefix;
365
	struct in_addr		 adv_rtr, area;
366
	char			*p;
367
	u_int32_t		 metric, cost2, ext_tag = 0;
368
	enum path_type		 type;
369
370
	lsa_age(v);
371
	if (ntohs(v->lsa->hdr.age) == MAX_AGE ||
372
	    (ntohl(v->lsa->data.asext.metric) & LSA_METRIC_MASK) >=
373
	    LS_INFINITY)
374
		return;
375
376
	switch (v->type) {
377
	case LSA_TYPE_EXTERNAL:
378
		/* ignore self-originated stuff */
379
		if (v->self)
380
			return;
381
382
		adv_rtr.s_addr = htonl(v->adv_rtr);
383
		bzero(&addr, sizeof(addr));
384
		bcopy(&adv_rtr, &addr.s6_addr[12], sizeof(adv_rtr));
385
		if ((r = rt_lookup(DT_RTR, &addr)) == NULL)
386
			return;
387
388
		prefix = &v->lsa->data.asext.prefix;
389
		if (prefix->options & OSPF_PREFIX_NU)
390
			break;
391
		bzero(&addr, sizeof(addr));
392
		bcopy(prefix + 1, &addr,
393
		    LSA_PREFIXSIZE(prefix->prefixlen));
394
395
		p = (char *)(prefix + 1) + LSA_PREFIXSIZE(prefix->prefixlen);
396
		metric = ntohl(v->lsa->data.asext.metric);
397
398
		if (metric & LSA_ASEXT_F_FLAG) {
399
			bcopy(p, &fw_addr, sizeof(fw_addr));
400
			p += sizeof(fw_addr);
401
402
			/* lookup forwarding address */
403
			if ((r = rt_lookup(DT_NET, &fw_addr)) == NULL ||
404
			    (r->p_type != PT_INTRA_AREA &&
405
			    r->p_type != PT_INTER_AREA))
406
				return;
407
		}
408
		if (metric & LSA_ASEXT_T_FLAG) {
409
			bcopy(p, &ext_tag, sizeof(ext_tag));
410
			p += sizeof(ext_tag);
411
		}
412
		if (metric & LSA_ASEXT_E_FLAG) {
413
			v->cost = r->cost;
414
			cost2 = metric & LSA_METRIC_MASK;
415
			type = PT_TYPE2_EXT;
416
		} else {
417
			v->cost = r->cost + (metric & LSA_METRIC_MASK);
418
			cost2 = 0;
419
			type = PT_TYPE1_EXT;
420
		}
421
422
		area.s_addr = 0;
423
		calc_nexthop_clear(v);
424
		TAILQ_FOREACH(rn, &r->nexthop, entry) {
425
			if (rn->invalid)
426
				continue;
427
428
			if (rn->connected && r->d_type == DT_NET) {
429
				if (metric & LSA_ASEXT_F_FLAG)
430
					calc_nexthop_add(v, NULL, &fw_addr,
431
					    rn->ifindex);
432
				else
433
					fatalx("asext_calc: I'm sorry Dave, "
434
					    "I'm afraid I can't do that.");
435
			} else
436
				calc_nexthop_add(v, NULL, &rn->nexthop,
437
				    rn->ifindex);
438
		}
439
440
		rt_update(&addr, prefix->prefixlen,
441
		    &v->nexthop, v->cost, cost2, area, adv_rtr, type,
442
		    DT_NET, 0, ext_tag);
443
		break;
444
	default:
445
		fatalx("asext_calc: invalid LSA type");
446
	}
447
}
448
449
void
450
spf_tree_clr(struct area *area)
451
{
452
	struct lsa_tree	*tree = &area->lsa_tree;
453
	struct vertex	*v;
454
455
	RB_FOREACH(v, lsa_tree, tree) {
456
		v->cost = LS_INFINITY;
457
		calc_nexthop_clear(v);
458
	}
459
}
460
461
void
462
calc_nexthop_clear(struct vertex *v)
463
{
464
	struct v_nexthop	*vn;
465
466
	while ((vn = TAILQ_FIRST(&v->nexthop))) {
467
		TAILQ_REMOVE(&v->nexthop, vn, entry);
468
		free(vn);
469
	}
470
}
471
472
void
473
calc_nexthop_add(struct vertex *dst, struct vertex *parent,
474
	const struct in6_addr *nexthop, u_int32_t ifindex)
475
{
476
	struct v_nexthop	*vn;
477
478
	if ((vn = calloc(1, sizeof(*vn))) == NULL)
479
		fatal("calc_nexthop_add");
480
481
	vn->prev = parent;
482
	if (nexthop)
483
		vn->nexthop = *nexthop;
484
	vn->ifindex = ifindex;
485
486
	TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry);
487
}
488
489
struct in6_addr *
490
calc_nexthop_lladdr(struct vertex *dst, struct lsa_rtr_link *rtr_link,
491
    unsigned int ifindex)
492
{
493
	struct iface		*iface;
494
	struct vertex		*link;
495
	struct rde_nbr		*nbr;
496
497
	/* Find outgoing interface, we need its LSA tree */
498
	LIST_FOREACH(iface, &dst->area->iface_list, entry) {
499
		if (ifindex == iface->ifindex)
500
			break;
501
	}
502
	if (!iface) {
503
		log_warnx("calc_nexthop_lladdr: no interface found for "
504
		    "ifindex %d", ntohl(rtr_link->iface_id));
505
		return (NULL);
506
	}
507
508
	/* Determine neighbor's link-local address.
509
	 * Try to get it from link LSA first. */
510
	link = lsa_find_tree(&iface->lsa_tree,
511
		htons(LSA_TYPE_LINK), rtr_link->iface_id,
512
		htonl(dst->adv_rtr));
513
	if (link)
514
		return &link->lsa->data.link.lladdr;
515
516
	/* Not found, so fall back to source address
517
	 * advertised in hello packet. */
518
	if ((nbr = rde_nbr_find(dst->peerid)) == NULL)
519
		fatalx("next hop is not a neighbor");
520
	return &nbr->addr;
521
}
522
523
void
524
calc_nexthop_transit_nbr(struct vertex *dst, struct vertex *parent,
525
    unsigned int ifindex)
526
{
527
	struct lsa_rtr_link	*rtr_link;
528
	unsigned int		 i;
529
	struct in6_addr		*lladdr;
530
531
	if (dst->type != LSA_TYPE_ROUTER)
532
		fatalx("calc_nexthop_transit_nbr: dst is not a router");
533
	if (parent->type != LSA_TYPE_NETWORK)
534
		fatalx("calc_nexthop_transit_nbr: parent is not a network");
535
536
	/* dst is a neighbor on a directly attached transit network.
537
	 * Figure out dst's link local address and add it as nexthop. */
538
	for (i = 0; i < lsa_num_links(dst); i++) {
539
		rtr_link = get_rtr_link(dst, i);
540
		if (rtr_link->type == LINK_TYPE_TRANSIT_NET &&
541
		    rtr_link->nbr_rtr_id == parent->lsa->hdr.adv_rtr &&
542
		    rtr_link->nbr_iface_id == parent->lsa->hdr.ls_id) {
543
			lladdr = calc_nexthop_lladdr(dst, rtr_link, ifindex);
544
			calc_nexthop_add(dst, parent, lladdr, ifindex);
545
		}
546
	}
547
}
548
549
void
550
calc_nexthop(struct vertex *dst, struct vertex *parent,
551
    struct area *area, struct lsa_rtr_link *rtr_link)
552
{
553
	struct v_nexthop	*vn;
554
	struct in6_addr		*nexthop;
555
556
	/* case 1 */
557
	if (parent == spf_root) {
558
		switch (dst->type) {
559
		case LSA_TYPE_ROUTER:
560
			if (rtr_link->type != LINK_TYPE_POINTTOPOINT)
561
				fatalx("inconsistent SPF tree");
562
			nexthop = calc_nexthop_lladdr(dst, rtr_link,
563
			    ntohl(rtr_link->iface_id));
564
			break;
565
		case LSA_TYPE_NETWORK:
566
			if (rtr_link->type != LINK_TYPE_TRANSIT_NET)
567
				fatalx("inconsistent SPF tree");
568
569
			/* Next hop address cannot be determined yet,
570
			 * we only know the outgoing interface. */
571
			nexthop = NULL;
572
			break;
573
		default:
574
			fatalx("calc_nexthop: invalid dst type");
575
		}
576
577
		calc_nexthop_add(dst, spf_root, nexthop,
578
		    ntohl(rtr_link->iface_id));
579
		return;
580
	}
581
582
	/* case 2 */
583
	if (parent->type == LSA_TYPE_NETWORK && dst->type == LSA_TYPE_ROUTER) {
584
		TAILQ_FOREACH(vn, &parent->nexthop, entry) {
585
			if (vn->prev == spf_root)
586
				calc_nexthop_transit_nbr(dst, parent,
587
				    vn->ifindex);
588
			else
589
				/* dst is more than one transit net away */
590
				calc_nexthop_add(dst, parent, &vn->nexthop,
591
				    vn->ifindex);
592
		}
593
		return;
594
	}
595
596
	/* case 3 */
597
	TAILQ_FOREACH(vn, &parent->nexthop, entry)
598
	    calc_nexthop_add(dst, parent, &vn->nexthop, vn->ifindex);
599
}
600
601
/* candidate list */
602
void
603
cand_list_init(void)
604
{
605
	TAILQ_INIT(&cand_list);
606
}
607
608
void
609
cand_list_add(struct vertex *v)
610
{
611
	struct vertex	*c = NULL;
612
613
	TAILQ_FOREACH(c, &cand_list, cand) {
614
		if (c->cost > v->cost) {
615
			TAILQ_INSERT_BEFORE(c, v, cand);
616
			return;
617
		} else if (c->cost == v->cost && c->type == LSA_TYPE_ROUTER &&
618
		    v->type == LSA_TYPE_NETWORK) {
619
			TAILQ_INSERT_BEFORE(c, v, cand);
620
			return;
621
		}
622
	}
623
	TAILQ_INSERT_TAIL(&cand_list, v, cand);
624
}
625
626
struct vertex *
627
cand_list_pop(void)
628
{
629
	struct vertex	*c;
630
631
	if ((c = TAILQ_FIRST(&cand_list)) != NULL) {
632
		TAILQ_REMOVE(&cand_list, c, cand);
633
	}
634
635
	return (c);
636
}
637
638
int
639
cand_list_present(struct vertex *v)
640
{
641
	struct vertex	*c;
642
643
	TAILQ_FOREACH(c, &cand_list, cand) {
644
		if (c == v)
645
			return (1);
646
	}
647
648
	return (0);
649
}
650
651
void
652
cand_list_clr(void)
653
{
654
	struct vertex *c;
655
656
	while ((c = TAILQ_FIRST(&cand_list)) != NULL) {
657
		TAILQ_REMOVE(&cand_list, c, cand);
658
	}
659
}
660
661
/* timers */
662
/* ARGSUSED */
663
void
664
spf_timer(int fd, short event, void *arg)
665
{
666
	struct vertex		*v;
667
	struct ospfd_conf	*conf = arg;
668
	struct area		*area;
669
	struct rt_node		*r;
670
671
	switch (conf->spf_state) {
672
	case SPF_IDLE:
673
		fatalx("spf_timer: invalid state IDLE");
674
	case SPF_HOLDQUEUE:
675
		conf->spf_state = SPF_DELAY;
676
		/* FALLTHROUGH */
677
	case SPF_DELAY:
678
		LIST_FOREACH(area, &conf->area_list, entry) {
679
			if (area->dirty) {
680
				/* invalidate RIB entries of this area */
681
				rt_invalidate(area);
682
683
				/* calculate SPF tree */
684
				spf_calc(area);
685
686
				/* calculate route table */
687
				RB_FOREACH(v, lsa_tree, &area->lsa_tree) {
688
					rt_calc(v, area, conf);
689
				}
690
691
				area->dirty = 0;
692
			}
693
		}
694
695
		/* calculate as-external routes, first invalidate them */
696
		rt_invalidate(NULL);
697
		RB_FOREACH(v, lsa_tree, &asext_tree) {
698
			asext_calc(v);
699
		}
700
701
		RB_FOREACH(r, rt_tree, &rt) {
702
			LIST_FOREACH(area, &conf->area_list, entry)
703
				rde_summary_update(r, area);
704
705
			if (r->d_type != DT_NET)
706
				continue;
707
708
			if (r->invalid)
709
				rde_send_delete_kroute(r);
710
			else
711
				rde_send_change_kroute(r);
712
		}
713
714
		LIST_FOREACH(area, &conf->area_list, entry)
715
			lsa_remove_invalid_sums(area);
716
717
		start_spf_holdtimer(conf);
718
		break;
719
	case SPF_HOLD:
720
		conf->spf_state = SPF_IDLE;
721
		break;
722
	default:
723
		fatalx("spf_timer: unknown state");
724
	}
725
}
726
727
void
728
start_spf_timer(void)
729
{
730
	struct timeval	tv;
731
732
	switch (rdeconf->spf_state) {
733
	case SPF_IDLE:
734
		timerclear(&tv);
735
		tv.tv_sec = rdeconf->spf_delay;
736
		rdeconf->spf_state = SPF_DELAY;
737
		if (evtimer_add(&rdeconf->ev, &tv) == -1)
738
			fatal("start_spf_timer");
739
		break;
740
	case SPF_DELAY:
741
		/* ignore */
742
		break;
743
	case SPF_HOLD:
744
		rdeconf->spf_state = SPF_HOLDQUEUE;
745
		break;
746
	case SPF_HOLDQUEUE:
747
		/* ignore */
748
		break;
749
	default:
750
		fatalx("start_spf_timer: invalid spf_state");
751
	}
752
}
753
754
void
755
stop_spf_timer(struct ospfd_conf *conf)
756
{
757
	if (evtimer_del(&conf->ev) == -1)
758
		fatal("stop_spf_timer");
759
}
760
761
void
762
start_spf_holdtimer(struct ospfd_conf *conf)
763
{
764
	struct timeval	tv;
765
766
	switch (conf->spf_state) {
767
	case SPF_DELAY:
768
		timerclear(&tv);
769
		tv.tv_sec = conf->spf_hold_time;
770
		conf->spf_state = SPF_HOLD;
771
		if (evtimer_add(&conf->ev, &tv) == -1)
772
			fatal("start_spf_holdtimer");
773
		break;
774
	case SPF_IDLE:
775
	case SPF_HOLD:
776
	case SPF_HOLDQUEUE:
777
		fatalx("start_spf_holdtimer: invalid state");
778
	default:
779
		fatalx("start_spf_holdtimer: unknown state");
780
	}
781
}
782
783
/* route table */
784
void
785
rt_init(void)
786
{
787
	RB_INIT(&rt);
788
}
789
790
int
791
rt_compare(struct rt_node *a, struct rt_node *b)
792
{
793
	int	i;
794
795
	/* XXX maybe a & b need to be switched */
796
	i = memcmp(&a->prefix, &b->prefix, sizeof(a->prefix));
797
	if (i)
798
		return (i);
799
	if (a->prefixlen < b->prefixlen)
800
		return (-1);
801
	if (a->prefixlen > b->prefixlen)
802
		return (1);
803
	if (a->d_type > b->d_type)
804
		return (-1);
805
	if (a->d_type < b->d_type)
806
		return (1);
807
	return (0);
808
}
809
810
struct rt_node *
811
rt_find(struct in6_addr *prefix, u_int8_t prefixlen, enum dst_type d_type)
812
{
813
	struct rt_node	s;
814
815
	s.prefix = *prefix;
816
	s.prefixlen = prefixlen;
817
	s.d_type = d_type;
818
819
	return (RB_FIND(rt_tree, &rt, &s));
820
}
821
822
int
823
rt_insert(struct rt_node *r)
824
{
825
	if (RB_INSERT(rt_tree, &rt, r) != NULL) {
826
		log_warnx("rt_insert failed for %s/%u",
827
		    log_in6addr(&r->prefix), r->prefixlen);
828
		free(r);
829
		return (-1);
830
	}
831
832
	return (0);
833
}
834
835
int
836
rt_remove(struct rt_node *r)
837
{
838
	if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
839
		log_warnx("rt_remove failed for %s/%u",
840
		    log_in6addr(&r->prefix), r->prefixlen);
841
		return (-1);
842
	}
843
844
	rt_nexthop_clear(r);
845
	free(r);
846
	return (0);
847
}
848
849
void
850
rt_invalidate(struct area *area)
851
{
852
	struct rt_node		*r, *nr;
853
	struct rt_nexthop	*rn, *nrn;
854
855
	for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) {
856
		nr = RB_NEXT(rt_tree, &rt, r);
857
		if (area == NULL) {
858
			/* look only at as_ext routes */
859
			if (r->p_type != PT_TYPE1_EXT &&
860
			    r->p_type != PT_TYPE2_EXT)
861
				continue;
862
		} else {
863
			/* ignore all as_ext routes */
864
			if (r->p_type == PT_TYPE1_EXT ||
865
			    r->p_type == PT_TYPE2_EXT)
866
				continue;
867
868
			/* look only at routes matching the area */
869
			if (r->area.s_addr != area->id.s_addr)
870
				continue;
871
		}
872
		r->invalid = 1;
873
		for (rn = TAILQ_FIRST(&r->nexthop); rn != NULL; rn = nrn) {
874
			nrn = TAILQ_NEXT(rn, entry);
875
			if (rn->invalid) {
876
				TAILQ_REMOVE(&r->nexthop, rn, entry);
877
				free(rn);
878
			} else
879
				rn->invalid = 1;
880
		}
881
		if (TAILQ_EMPTY(&r->nexthop))
882
			rt_remove(r);
883
	}
884
}
885
886
void
887
rt_nexthop_clear(struct rt_node *r)
888
{
889
	struct rt_nexthop	*rn;
890
891
	while ((rn = TAILQ_FIRST(&r->nexthop)) != NULL) {
892
		TAILQ_REMOVE(&r->nexthop, rn, entry);
893
		free(rn);
894
	}
895
}
896
897
void
898
rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh,
899
    struct in_addr adv_rtr)
900
{
901
	struct v_nexthop	*vn;
902
	struct rt_nexthop	*rn;
903
	struct timespec		 now;
904
905
	TAILQ_FOREACH(vn, vnh, entry) {
906
		TAILQ_FOREACH(rn, &r->nexthop, entry) {
907
			if (!IN6_ARE_ADDR_EQUAL(&rn->nexthop, &vn->nexthop))
908
				continue;
909
910
			rn->adv_rtr.s_addr = adv_rtr.s_addr;
911
			rn->connected = vn->prev == spf_root;
912
			rn->invalid = 0;
913
914
			r->invalid = 0;
915
			break;
916
		}
917
		if (rn)
918
			continue;
919
920
		if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL)
921
			fatal("rt_nexthop_add");
922
923
		clock_gettime(CLOCK_MONOTONIC, &now);
924
		rn->nexthop = vn->nexthop;
925
		rn->ifindex = vn->ifindex;
926
		rn->adv_rtr.s_addr = adv_rtr.s_addr;
927
		rn->uptime = now.tv_sec;
928
		rn->connected = vn->prev == spf_root;
929
		rn->invalid = 0;
930
931
		r->invalid = 0;
932
		TAILQ_INSERT_TAIL(&r->nexthop, rn, entry);
933
	}
934
}
935
936
void
937
rt_clear(void)
938
{
939
	struct rt_node	*r;
940
941
	while ((r = RB_MIN(rt_tree, &rt)) != NULL)
942
		rt_remove(r);
943
}
944
945
void
946
rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type)
947
{
948
	static struct ctl_rt	 rtctl;
949
	struct timespec		 now;
950
	struct rt_node		*r;
951
	struct rt_nexthop	*rn;
952
953
	clock_gettime(CLOCK_MONOTONIC, &now);
954
955
	RB_FOREACH(r, rt_tree, &rt) {
956
		if (r->invalid)
957
			continue;
958
959
		if (r->area.s_addr != area.s_addr)
960
			continue;
961
962
		switch (r_type) {
963
		case RIB_RTR:
964
			if (r->d_type != DT_RTR)
965
				continue;
966
			break;
967
		case RIB_NET:
968
			if (r->d_type != DT_NET)
969
				continue;
970
			if (r->p_type == PT_TYPE1_EXT ||
971
			    r->p_type == PT_TYPE2_EXT)
972
				continue;
973
			break;
974
		case RIB_EXT:
975
			if (r->p_type != PT_TYPE1_EXT &&
976
			    r->p_type != PT_TYPE2_EXT)
977
				continue;
978
			break;
979
		default:
980
			fatalx("rt_dump: invalid RIB type");
981
		}
982
983
		TAILQ_FOREACH(rn, &r->nexthop, entry) {
984
			if (rn->invalid)
985
				continue;
986
987
			rtctl.prefix = r->prefix;
988
			rtctl.nexthop = rn->nexthop;
989
			rtctl.ifindex = rn->ifindex;
990
			rtctl.area.s_addr = r->area.s_addr;
991
			rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr;
992
			rtctl.cost = r->cost;
993
			rtctl.cost2 = r->cost2;
994
			rtctl.p_type = r->p_type;
995
			rtctl.d_type = r->d_type;
996
			rtctl.flags = r->flags;
997
			rtctl.prefixlen = r->prefixlen;
998
			rtctl.uptime = now.tv_sec - rn->uptime;
999
1000
			rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid,
1001
			    &rtctl, sizeof(rtctl));
1002
		}
1003
	}
1004
}
1005
1006
void
1007
rt_update(struct in6_addr *prefix, u_int8_t prefixlen, struct v_nexthead *vnh,
1008
     u_int32_t cost, u_int32_t cost2, struct in_addr area,
1009
     struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type,
1010
     u_int8_t flags, u_int32_t tag)
1011
{
1012
	struct rt_node		*rte;
1013
	struct rt_nexthop	*rn;
1014
	int			 better = 0, equal = 0;
1015
1016
	if (vnh == NULL || TAILQ_EMPTY(vnh))	/* XXX remove */
1017
		fatalx("rt_update: invalid nexthop");
1018
1019
	if ((rte = rt_find(prefix, prefixlen, d_type)) == NULL) {
1020
		if ((rte = calloc(1, sizeof(struct rt_node))) == NULL)
1021
			fatal("rt_update");
1022
1023
		TAILQ_INIT(&rte->nexthop);
1024
		rte->prefix = *prefix;
1025
		rte->prefixlen = prefixlen;
1026
		rte->cost = cost;
1027
		rte->cost2 = cost2;
1028
		rte->area = area;
1029
		rte->p_type = p_type;
1030
		rte->d_type = d_type;
1031
		rte->flags = flags;
1032
		rte->ext_tag = tag;
1033
1034
		rt_nexthop_add(rte, vnh, adv_rtr);
1035
1036
		rt_insert(rte);
1037
	} else {
1038
		/* order:
1039
		 * 1. intra-area
1040
		 * 2. inter-area
1041
		 * 3. type 1 as ext
1042
		 * 4. type 2 as ext
1043
		 */
1044
		if (rte->invalid)	/* everything is better than invalid */
1045
			better = 1;
1046
		else if (p_type < rte->p_type)
1047
			better = 1;
1048
		else if (p_type == rte->p_type)
1049
			switch (p_type) {
1050
			case PT_INTRA_AREA:
1051
			case PT_INTER_AREA:
1052
				if (cost < rte->cost)
1053
					better = 1;
1054
				else if (cost == rte->cost &&
1055
				    rte->area.s_addr == area.s_addr)
1056
					equal = 1;
1057
				break;
1058
			case PT_TYPE1_EXT:
1059
				if (cost < rte->cost)
1060
					better = 1;
1061
				else if (cost == rte->cost)
1062
					equal = 1;
1063
				break;
1064
			case PT_TYPE2_EXT:
1065
				if (cost2 < rte->cost2)
1066
					better = 1;
1067
				else if (cost2 == rte->cost2 &&
1068
				    cost < rte->cost)
1069
					better = 1;
1070
				else if (cost2 == rte->cost2 &&
1071
				    cost == rte->cost)
1072
					equal = 1;
1073
				break;
1074
			}
1075
1076
		if (better) {
1077
			TAILQ_FOREACH(rn, &rte->nexthop, entry)
1078
				rn->invalid = 1;
1079
1080
			rte->area = area;
1081
			rte->cost = cost;
1082
			rte->cost2 = cost2;
1083
			rte->p_type = p_type;
1084
			rte->flags = flags;
1085
			rte->ext_tag = tag;
1086
		}
1087
1088
		if (equal || better)
1089
			rt_nexthop_add(rte, vnh, adv_rtr);
1090
	}
1091
}
1092
1093
struct rt_node *
1094
rt_lookup(enum dst_type type, struct in6_addr *addr)
1095
{
1096
	struct rt_node	*rn;
1097
	struct in6_addr	 ina;
1098
	u_int8_t	 i = 128;
1099
1100
	if (type == DT_RTR) {
1101
		rn = rt_find(addr, 128, type);
1102
		if (rn && rn->invalid == 0)
1103
			return (rn);
1104
		return (NULL);
1105
	}
1106
1107
	/* type == DT_NET */
1108
	do {
1109
		inet6applymask(&ina, addr, i);
1110
		if ((rn = rt_find(&ina, i, type)) && rn->invalid == 0)
1111
			return (rn);
1112
	} while (i-- != 0);
1113
1114
	return (NULL);
1115
}
1116
1117
/* router LSA links */
1118
struct lsa_rtr_link *
1119
get_rtr_link(struct vertex *v, unsigned int idx)
1120
{
1121
	struct lsa_rtr_link	*rtr_link = NULL;
1122
	unsigned int		 frag = 1;
1123
	unsigned int		 frag_nlinks;
1124
	unsigned int		 nlinks = 0;
1125
	unsigned int		 i;
1126
1127
	if (v->type != LSA_TYPE_ROUTER)
1128
		fatalx("get_rtr_link: invalid LSA type");
1129
1130
	/* Treat multiple Router-LSAs originated by the same router
1131
	 * as an aggregate. */
1132
	do {
1133
		/* number of links validated earlier by lsa_check() */
1134
		rtr_link = (struct lsa_rtr_link *)((char *)v->lsa +
1135
		    sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr));
1136
		frag_nlinks = ((ntohs(v->lsa->hdr.len) -
1137
		    sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) /
1138
		    sizeof(struct lsa_rtr_link));
1139
		if (nlinks + frag_nlinks > idx) {
1140
			for (i = 0; i < frag_nlinks; i++) {
1141
				if (i + nlinks == idx)
1142
					return (rtr_link);
1143
				rtr_link++;
1144
			}
1145
		}
1146
		nlinks += frag_nlinks;
1147
		v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), frag++);
1148
	} while (v);
1149
1150
	return (NULL);
1151
}
1152
1153
/* network LSA links */
1154
struct lsa_net_link *
1155
get_net_link(struct vertex *v, unsigned int idx)
1156
{
1157
	struct lsa_net_link	*net_link = NULL;
1158
	char			*buf = (char *)v->lsa;
1159
	unsigned int		 i;
1160
1161
	if (v->type != LSA_TYPE_NETWORK)
1162
		fatalx("get_net_link: invalid LSA type");
1163
1164
	/* number of links validated earlier by lsa_check() */
1165
	net_link = (struct lsa_net_link *)(buf + sizeof(v->lsa->hdr) +
1166
	    sizeof(struct lsa_net));
1167
	for (i = 0; i < lsa_num_links(v); i++) {
1168
		if (i == idx)
1169
			return (net_link);
1170
		net_link++;
1171
	}
1172
1173
	return (NULL);
1174
}
1175
1176
/* misc */
1177
int
1178
linked(struct vertex *w, struct vertex *v)
1179
{
1180
	struct lsa_rtr_link	*rtr_link = NULL;
1181
	struct lsa_net_link	*net_link = NULL;
1182
	unsigned int		 i;
1183
1184
	switch (w->type) {
1185
	case LSA_TYPE_ROUTER:
1186
		for (i = 0; i < lsa_num_links(w); i++) {
1187
			rtr_link = get_rtr_link(w, i);
1188
			switch (v->type) {
1189
			case LSA_TYPE_ROUTER:
1190
				if (rtr_link->type == LINK_TYPE_POINTTOPOINT &&
1191
				    rtr_link->nbr_rtr_id == htonl(v->adv_rtr))
1192
					return (1);
1193
				break;
1194
			case LSA_TYPE_NETWORK:
1195
				if (rtr_link->type == LINK_TYPE_TRANSIT_NET &&
1196
				    rtr_link->nbr_rtr_id == htonl(v->adv_rtr) &&
1197
				    rtr_link->nbr_iface_id == htonl(v->ls_id))
1198
					return (1);
1199
				break;
1200
			default:
1201
				fatalx("linked: invalid type");
1202
			}
1203
		}
1204
		return (0);
1205
	case LSA_TYPE_NETWORK:
1206
		for (i = 0; i < lsa_num_links(w); i++) {
1207
			net_link = get_net_link(w, i);
1208
			switch (v->type) {
1209
			case LSA_TYPE_ROUTER:
1210
				if (net_link->att_rtr == htonl(v->adv_rtr))
1211
					return (1);
1212
				break;
1213
			default:
1214
				fatalx("linked: invalid type");
1215
			}
1216
		}
1217
		return (0);
1218
	default:
1219
		fatalx("linked: invalid LSA type");
1220
	}
1221
1222
	return (0);
1223
}