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