Head

GCC Code Coverage Report

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


/*	$OpenBSD: rde_srt.c,v 1.26 2015/05/22 01:30:27 jsg Exp $ */

/*
 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
 * Copyright (c) 2005, 2006 Esben Norby <norby@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>
#include <sys/socket.h>
#include <sys/tree.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <err.h>
#include <stdlib.h>
#include <string.h>

#include "igmp.h"
#include "dvmrp.h"
#include "dvmrpd.h"
#include "log.h"
#include "dvmrpe.h"
#include "rde.h"

/* source route tree */

void	 rt_invalidate(void);
void	 rt_expire_timer(int, short, void *);
int	 rt_start_expire_timer(struct rt_node *);
void	 rt_holddown_timer(int, short, void *);
void	 rt_start_holddown_timer(struct rt_node *);

void	 srt_set_upstream(struct rt_node *, u_int32_t);

/* Designated forwarder */
void	 srt_set_forwarder_self(struct rt_node *, struct iface *);
void	 srt_update_ds_forwarders(struct rt_node *, struct iface *,
	    u_int32_t);
void	 srt_current_forwarder(struct rt_node *, struct iface *,
	    u_int32_t, u_int32_t);

/* Downstream neighbors */
void		 srt_add_ds(struct rt_node *, u_int32_t, u_int32_t);
void		 srt_delete_ds(struct rt_node *, struct ds_nbr *,
		    struct iface *);

/* Flash updates */
void		 flash_update(struct rt_node *);
void		 flash_update_ds(struct rt_node *);

RB_HEAD(rt_tree, rt_node)	 rt;
RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
RB_GENERATE(rt_tree, rt_node, entry, rt_compare)

extern struct dvmrpd_conf	*rdeconf;

/* timers */
void
rt_expire_timer(int fd, short event, void *arg)
{
	struct rt_node	*rn = arg;
	struct timeval	 tv;

	log_debug("rt_expire_timer: route %s/%d", inet_ntoa(rn->prefix),
	    rn->prefixlen);

	timerclear(&tv);
	rn->old_cost = rn->cost;
	rn->cost = INFINITY_METRIC;
	tv.tv_sec = ROUTE_HOLD_DOWN;

	if (evtimer_add(&rn->holddown_timer, &tv) == -1)
		fatal("rt_expire_timer");
}

int
rt_start_expire_timer(struct rt_node *rn)
{
	struct timeval	tv;

	rn->old_cost = 0;

	if (evtimer_pending(&rn->holddown_timer, NULL))
		if (evtimer_del(&rn->holddown_timer) == -1)
			fatal("rt_start_expire_timer");

	timerclear(&tv);
	tv.tv_sec = ROUTE_EXPIRATION_TIME;
	return (evtimer_add(&rn->expiration_timer, &tv));
}

void
rt_holddown_timer(int fd, short event, void *arg)
{
	struct rt_node	*rn = arg;

	log_debug("rt_holddown_timer: route %s/%d", inet_ntoa(rn->prefix),
	    rn->prefixlen);

	rt_remove(rn);
}

void
rt_start_holddown_timer(struct rt_node *rn)
{
	struct timeval	tv;

	timerclear(&tv);
	tv.tv_sec = ROUTE_HOLD_DOWN;
	if (evtimer_pending(&rn->expiration_timer, NULL)) {
		if (evtimer_del(&rn->expiration_timer) == -1)
			fatal("rt_start_holddown_timer");
		evtimer_add(&rn->holddown_timer, &tv);
	}
}

/* route table */
void
rt_init(void)
{
	RB_INIT(&rt);
}

int
rt_compare(struct rt_node *a, struct rt_node *b)
{
	/*
	 * sort route entries based on prefixlen since generating route
	 * reports rely on that.
	 */
	if (a->prefixlen < b->prefixlen)
		return (-1);
	if (a->prefixlen > b->prefixlen)
		return (1);
	if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr))
		return (-1);
	if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr))
		return (1);
	return (0);
}

struct rt_node *
rt_find(in_addr_t prefix, u_int8_t prefixlen)
{
	struct rt_node	s;

	s.prefix.s_addr = prefix;
	s.prefixlen = prefixlen;

	return (RB_FIND(rt_tree, &rt, &s));
}

struct rt_node *
rr_new_rt(struct route_report *rr, u_int32_t adj_metric, int connected)
{
	struct timespec	 now;
	struct rt_node  *rn;
	int i;

	clock_gettime(CLOCK_MONOTONIC, &now);

	if ((rn = calloc(1, sizeof(*rn))) == NULL)
		fatal("rr_new_rt");

	rn->prefix.s_addr = rr->net.s_addr;
	rn->prefixlen = mask2prefixlen(rr->mask.s_addr);
	rn->nexthop.s_addr = rr->nexthop.s_addr;
	rn->cost = adj_metric;
	rn->ifindex = rr->ifindex;

	for (i = 0; i < MAXVIFS; i++) {
		rn->ttls[i] = 0;
		rn->ds_cnt[i] = 0;
		rn->adv_rtr[i].addr.s_addr = 0;
		rn->adv_rtr[i].metric = 0;
	}

	LIST_INIT(&rn->ds_list);

	rn->flags = F_DVMRPD_INSERTED;
	rn->connected = connected;
	rn->uptime = now.tv_sec;

	evtimer_set(&rn->expiration_timer, rt_expire_timer, rn);
	evtimer_set(&rn->holddown_timer, rt_holddown_timer, rn);

	return (rn);
}

int
rt_insert(struct rt_node *r)
{
	log_debug("rt_insert: inserting route %s/%d", inet_ntoa(r->prefix),
	    r->prefixlen);

	if (RB_INSERT(rt_tree, &rt, r) != NULL) {
		log_warnx("rt_insert failed for %s/%u", inet_ntoa(r->prefix),
		    r->prefixlen);
		free(r);
		return (-1);
	}

	return (0);
}

int
rt_remove(struct rt_node *r)
{
	struct ds_nbr	*ds_nbr;

	if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
		log_warnx("rt_remove failed for %s/%u",
		    inet_ntoa(r->prefix), r->prefixlen);
		return (-1);
	}

	while ((ds_nbr = LIST_FIRST(&r->ds_list)) != NULL) {
		LIST_REMOVE(ds_nbr, entry);
		free(ds_nbr);
	}

	free(r);
	return (0);
}

void
rt_invalidate(void)
{
	struct rt_node	*r, *nr;

	for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) {
		nr = RB_NEXT(rt_tree, &rt, r);
		if (r->invalid)
			rt_remove(r);
		else
			r->invalid = 1;
	}
}

void
rt_clear(void)
{
	struct rt_node	*r;

	while ((r = RB_MIN(rt_tree, &rt)) != NULL)
		rt_remove(r);
}

void
rt_snap(u_int32_t peerid)
{
	struct rt_node		*r;
	struct route_report	 rr;

	RB_FOREACH(r, rt_tree, &rt) {
		if (r->invalid)
			continue;

		rr.net = r->prefix;
		rr.mask.s_addr = ntohl(prefixlen2mask(r->prefixlen));
		rr.metric = r->cost;
		rr.ifindex = r->ifindex;
		rde_imsg_compose_dvmrpe(IMSG_FULL_ROUTE_REPORT, peerid, 0, &rr,
		    sizeof(rr));
	}
}

void
rt_dump(pid_t pid)
{
	static struct ctl_rt	 rtctl;
	struct timespec		 now;
	struct timeval		 tv, now2, res;
	struct rt_node		*r;

	clock_gettime(CLOCK_MONOTONIC, &now);

	RB_FOREACH(r, rt_tree, &rt) {
		if (r->invalid)
			continue;

		rtctl.prefix.s_addr = r->prefix.s_addr;
		rtctl.nexthop.s_addr = r->nexthop.s_addr;
		rtctl.cost = r->cost;
		rtctl.flags = r->flags;
		rtctl.prefixlen = r->prefixlen;
		rtctl.uptime = now.tv_sec - r->uptime;

		gettimeofday(&now2, NULL);
		if (evtimer_pending(&r->expiration_timer, &tv)) {
			timersub(&tv, &now2, &res);
			rtctl.expire = res.tv_sec;
		} else
			rtctl.expire = -1;

		rde_imsg_compose_dvmrpe(IMSG_CTL_SHOW_RIB, 0, pid, &rtctl,
		    sizeof(rtctl));
	}
}

void
rt_update(struct rt_node *rn)
{
	if (!rn->connected)
		rt_start_expire_timer(rn);
}

struct rt_node *
rt_match_origin(in_addr_t src)
{
	struct rt_node	*r;

	RB_FOREACH(r, rt_tree, &rt) {
		if (r->prefix.s_addr == (src &
		    htonl(prefixlen2mask(r->prefixlen))))
			return (r);
	}

	return (NULL);
}

int
srt_check_route(struct route_report *rr, int connected)
{
	struct rt_node		*rn;
	struct iface		*iface;
	struct ds_nbr		*ds_nbr;
	u_int32_t		 adj_metric;
	u_int32_t		 nbr_ip, nbr_report, ifindex;

	if ((iface = if_find_index(rr->ifindex)) == NULL)
		return (-1);

	ifindex = iface->ifindex;

	/* Interpret special case 0.0.0.0/8 as 0.0.0.0/0 */
	if (rr->net.s_addr == 0)
		rr->mask.s_addr = 0;

	if (connected)
		adj_metric = rr->metric;
	else
		adj_metric = rr->metric + iface->metric;

	if (adj_metric > INFINITY_METRIC)
		adj_metric = INFINITY_METRIC;

	/* If the route is new and the Adjusted Metric is less than infinity,
	   the route should be added. */
	rn = rt_find(rr->net.s_addr, mask2prefixlen(rr->mask.s_addr));
	if (rn == NULL) {
		if (adj_metric < INFINITY_METRIC) {
			rn = rr_new_rt(rr, adj_metric, connected);
			rt_insert(rn);
		}
		return (0);
	}

	/* If the route is connected accept only downstream neighbors reports */
	if (rn->connected && rr->metric <= INFINITY_METRIC)
		return (0);

	nbr_ip = rn->nexthop.s_addr;
	nbr_report = rr->nexthop.s_addr;

	if (rr->metric < INFINITY_METRIC) {
		/* If it is our current nexthop it cannot be a
		 * downstream router */
		if (nbr_ip != nbr_report)
			if ((ds_nbr = srt_find_ds(rn, nbr_report)))
				srt_delete_ds(rn, ds_nbr, iface);

		if (adj_metric > rn->cost) {
			if (nbr_ip == nbr_report) {
				rn->cost = adj_metric;
				flash_update_ds(rn);
			}
		} else if (adj_metric < rn->cost) {
			rn->cost = adj_metric;
			if (nbr_ip != nbr_report) {
				rn->nexthop.s_addr = nbr_report;
				srt_set_upstream(rn, ifindex);
				flash_update(rn);
			}
			/* We have a new best route to source, update the
			 * designated forwarders on downstream interfaces to
			 * reflect the new metric */
			srt_update_ds_forwarders(rn, iface, nbr_report);
		} else {
			if (nbr_report < nbr_ip) {
				rn->nexthop.s_addr = nbr_report;
				srt_set_upstream(rn, ifindex);
				flash_update(rn);
			} else if (nbr_report == nbr_ip &&
			    adj_metric == rn->old_cost)
				rt_update(rn);
				flash_update_ds(rn);
		}
		/* Update forwarder of current interface if necessary and
		 * refresh the route */
		srt_current_forwarder(rn, iface, rr->metric, nbr_report);
		rt_update(rn);
	} else if (rr->metric == INFINITY_METRIC) {
		if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr)
			srt_set_forwarder_self(rn, iface);
infinity:
		if (nbr_ip == nbr_report) {
			if (rn->cost < INFINITY_METRIC)
				rt_start_holddown_timer(rn);
		} else
			if ((ds_nbr = srt_find_ds(rn, nbr_report)))
				srt_delete_ds(rn, ds_nbr, iface);
	} else if (INFINITY_METRIC < rr->metric &&
	    rr->metric < 2 * INFINITY_METRIC) {
		/* Neighbor is reporting his dependency for this source */
		if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr)
			srt_set_forwarder_self(rn, iface);

		if (rn->ifindex == ifindex)
			goto infinity;
		else
			if (srt_find_ds(rn, nbr_report) == NULL)
				srt_add_ds(rn, nbr_report, ifindex);
	}

	return (0);
}

void
srt_current_forwarder(struct rt_node *rn, struct iface *iface,
    u_int32_t metric, u_int32_t nbr_report)
{
	struct adv_rtr *adv = &rn->adv_rtr[iface->ifindex];

	if (nbr_report == adv->addr.s_addr) {
		if (metric > rn->cost || (metric == rn->cost &&
		    iface->addr.s_addr < nbr_report))
			srt_set_forwarder_self(rn, iface);

	} else {
		if (metric < adv->metric ||
		    (metric == adv->metric && nbr_report < adv->addr.s_addr))
			if (adv->addr.s_addr == iface->addr.s_addr)
				rn->ttls[iface->ifindex] = 0;

		adv->addr.s_addr = nbr_report;
		adv->metric = metric;

		mfc_update_source(rn);
	}

}

void
srt_update_ds_forwarders(struct rt_node *rn, struct iface *iface,
    u_int32_t nbr_report)
{
	struct iface	*ifa;
	int		 i;

	for (i = 0; i < MAXVIFS; i++) {
		if (rn->adv_rtr[i].addr.s_addr &&
		    (rn->cost < rn->adv_rtr[i].metric ||
		    (rn->cost == rn->adv_rtr[i].metric &&
		    iface->addr.s_addr < nbr_report))) {
			ifa = if_find_index(i);
			srt_set_forwarder_self(rn, ifa);
		}
	}
}

void
srt_set_forwarder_self(struct rt_node *rn, struct iface *iface)
{
	rn->adv_rtr[iface->ifindex].addr.s_addr = iface->addr.s_addr;
	rn->adv_rtr[iface->ifindex].metric = rn->cost;
	rn->ttls[iface->ifindex] = 1;

	mfc_update_source(rn);
}

void
srt_set_upstream(struct rt_node *rn, u_int32_t ifindex)
{
	if (rn->ifindex != ifindex) {
		rn->ttls[rn->ifindex] = 1;
		rn->ifindex = ifindex;
	}

	mfc_update_source(rn);
}

void
srt_add_ds(struct rt_node *rn, u_int32_t nbr_report, u_int32_t ifindex)
{
	struct ds_nbr	*ds_nbr;

	log_debug("srt_add_ds: adding downstream router for source %s/%d",
	    inet_ntoa(rn->prefix), rn->prefixlen);

	if ((ds_nbr = malloc(sizeof(struct ds_nbr))) == NULL)
		fatal("srt_add_ds");

	ds_nbr->addr.s_addr = nbr_report;

	LIST_INSERT_HEAD(&rn->ds_list, ds_nbr, entry);
	rn->ds_cnt[ifindex]++;
	rn->ttls[ifindex] = 1;

	mfc_update_source(rn);
}

struct ds_nbr *
srt_find_ds(struct rt_node *rn, u_int32_t nbr_report)
{
	struct ds_nbr	*ds_nbr;

	LIST_FOREACH(ds_nbr, &rn->ds_list, entry)
		if (ds_nbr->addr.s_addr == nbr_report)
			return (ds_nbr);

	return (NULL);
}

void
srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface)
{
	log_debug("srt_delete_ds: deleting downstream router for source %s/%d",
	    inet_ntoa(rn->prefix), rn->prefixlen);

	LIST_REMOVE(ds_nbr, entry);
	free(ds_nbr);
	rn->ds_cnt[iface->ifindex]--;

	srt_check_downstream_ifaces(rn, iface);
}

void
srt_check_downstream_ifaces(struct rt_node *rn, struct iface *iface)
{
	/* We are not the designated forwarder for this source on this
	   interface. Keep things as they currently are */
	if (rn->adv_rtr[iface->ifindex].addr.s_addr != iface->addr.s_addr)
		return;

	/* There are still downstream dependent router for this source
	   Keep things as they currently are */
	if (rn->ds_cnt[iface->ifindex])
		return;

	/* There are still group members for this source on this iface
	   Keep things as they currently are */
	if (mfc_check_members(rn, iface))
		return;

	/* Remove interface from the downstream list */
	rn->ttls[iface->ifindex] = 0;
	mfc_update_source(rn);
}

void
srt_expire_nbr(struct in_addr addr, unsigned int ifindex)
{
	struct ds_nbr		*ds;
	struct rt_node		*rn;
	struct iface		*iface;

	iface = if_find_index(ifindex);
	if (iface == NULL)
		fatal("srt_expire_nbr: interface not found");

	RB_FOREACH(rn, rt_tree, &rt) {
		if (rn->adv_rtr[ifindex].addr.s_addr == addr.s_addr) {
			rn->adv_rtr[ifindex].addr.s_addr =
			    iface->addr.s_addr;
			rn->adv_rtr[ifindex].metric = rn->cost;
			/* XXX: delete all routes learned from this nbr */
		} else if (rn->adv_rtr[ifindex].addr.s_addr ==
		    iface->addr.s_addr) {
			ds = srt_find_ds(rn, addr.s_addr);
			if (ds) {
				srt_delete_ds(rn, ds, iface);
				srt_check_downstream_ifaces(rn, iface);
			}
		}
	}
}

void
flash_update(struct rt_node *rn) {
	struct route_report	rr;

	rr.net = rn->prefix;
	rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen));
	rr.metric = rn->cost;
	rr.ifindex = rn->ifindex;
	rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE, 0, 0, &rr, sizeof(rr));
}

void
flash_update_ds(struct rt_node *rn) {
	struct route_report	rr;

	rr.net = rn->prefix;
	rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen));
	rr.metric = rn->cost;
	rr.ifindex = rn->ifindex;
	rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE_DS, 0, 0, &rr, sizeof(rr));
}


Generated by: GCOVR (Version 3.3)

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