Initial support for pruning. When every single interface is removed from the

downstream list for a particular source send a prune to the upstream router.

input and ok claudio@

9 files changed, 203 insertions, 23 deletions

diff --git a/usr.sbin/dvmrpd/dvmrp.h b/usr.sbin/dvmrpd/dvmrp.h
index b043e30644e..cae149187da 100644
--- a/usr.sbin/dvmrpd/dvmrp.h
+++ b/usr.sbin/dvmrpd/dvmrp.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dvmrp.h,v 1.2 2009/01/27 08:53:47 michele Exp $ */
+/*	$OpenBSD: dvmrp.h,v 1.3 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2005, 2006 Esben Norby <norby@openbsd.org>
@@ -101,6 +101,7 @@ struct prune_hdr {
 	u_int32_t		lifetime;
 	u_int32_t		src_netmask;
 };
+#define	PRUNE_MIN_LEN			12
 
 /* Graft and Graft Ack header */
 struct graft_hdr {
diff --git a/usr.sbin/dvmrpd/dvmrpd.h b/usr.sbin/dvmrpd/dvmrpd.h
index 9c02a357487..5cfc7e77919 100644
--- a/usr.sbin/dvmrpd/dvmrpd.h
+++ b/usr.sbin/dvmrpd/dvmrpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dvmrpd.h,v 1.15 2009/03/07 12:47:17 michele Exp $ */
+/*	$OpenBSD: dvmrpd.h,v 1.16 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2004, 2005, 2006 Esben Norby <norby@openbsd.org>
@@ -111,6 +111,8 @@ enum imsg_type {
 	IMSG_MFC_DEL,
 	IMSG_GROUP_ADD,
 	IMSG_GROUP_DEL,
+	IMSG_SEND_PRUNE,
+	IMSG_RECV_PRUNE,
 	IMSG_FLASH_UPDATE,
 	IMSG_FLASH_UPDATE_DS
 };
@@ -196,6 +198,15 @@ struct mfc {
 	u_int8_t		 ttls[MAXVIFS];
 };
 
+struct prune {
+	struct in_addr		 origin;
+	struct in_addr		 netmask;
+	struct in_addr		 group;
+	struct in_addr		 nexthop;
+	u_short			 ifindex;
+	u_int32_t		 lifetime;
+};
+
 TAILQ_HEAD(rr_head, rr_entry);
 RB_HEAD(src_head, src_node);
 
diff --git a/usr.sbin/dvmrpd/dvmrpe.c b/usr.sbin/dvmrpd/dvmrpe.c
index 468ed1a69c3..931e5b6c45d 100644
--- a/usr.sbin/dvmrpd/dvmrpe.c
+++ b/usr.sbin/dvmrpd/dvmrpe.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dvmrpe.c,v 1.3 2008/11/21 10:39:32 michele Exp $ */
+/*	$OpenBSD: dvmrpe.c,v 1.4 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -272,6 +272,7 @@ dvmrpe_dispatch_rde(int fd, short event, void *bula)
 	struct imsgbuf		*ibuf = bula;
 	struct imsg		 imsg;
 	struct nbr		*nbr;
+	struct prune		 p;
 	struct iface		*iface;
 	struct route_report	*rr;
 	int			 n;
@@ -349,6 +350,26 @@ dvmrpe_dispatch_rde(int fd, short event, void *bula)
 			nbr = nbr_find_peerid(imsg.hdr.peerid);
 			rr_list_send(&nbr->rr_list, NULL, nbr);
 			break;
+		case IMSG_SEND_PRUNE:
+			if (imsg.hdr.len - IMSG_HEADER_SIZE != sizeof(p))
+				fatalx("invalid size of RDE request");
+
+			memcpy(&p, imsg.data, sizeof(p));
+
+			LIST_FOREACH(iface, &deconf->iface_list, entry)
+				if (p.ifindex == iface->ifindex)
+					break;
+
+			if (iface == NULL)
+				fatalx("invalid interface in mfc");
+
+			nbr = nbr_find_ip(iface, p.nexthop.s_addr);
+			if (nbr == NULL)
+				fatalx("unknown neighbor to send prune");
+
+			send_prune(nbr, &p);
+
+			break;
 		case IMSG_FLASH_UPDATE:
 			if (imsg.hdr.len - IMSG_HEADER_SIZE != sizeof(*rr))
 				fatalx("invalid size of RDE request");
diff --git a/usr.sbin/dvmrpd/dvmrpe.h b/usr.sbin/dvmrpd/dvmrpe.h
index d85833a4148..d5e95d283ca 100644
--- a/usr.sbin/dvmrpd/dvmrpe.h
+++ b/usr.sbin/dvmrpd/dvmrpe.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dvmrpe.h,v 1.2 2006/11/10 11:09:56 michele Exp $ */
+/*	$OpenBSD: dvmrpe.h,v 1.3 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2004, 2005, 2006 Esben Norby <norby@openbsd.org>
@@ -195,7 +195,7 @@ void		 recv_probe(struct iface *, struct in_addr, u_int32_t, u_int8_t,
 		    char *, u_int16_t);
 
 /* prune.c */
-int		 send_prune(struct nbr *, void *, int);
+int		 send_prune(struct nbr *, struct prune *);
 void		 recv_prune(struct nbr *, char *, u_int16_t);
 
 /* report.c */
diff --git a/usr.sbin/dvmrpd/prune.c b/usr.sbin/dvmrpd/prune.c
index 697603432f5..58cf4ac3d1f 100644
--- a/usr.sbin/dvmrpd/prune.c
+++ b/usr.sbin/dvmrpd/prune.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: prune.c,v 1.1 2006/06/01 14:12:20 norby Exp $ */
+/*	$OpenBSD: prune.c,v 1.2 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2005, 2006 Esben Norby <norby@openbsd.org>
@@ -34,11 +34,12 @@
 
 /* DVMRP prune packet handling */
 int
-send_prune(struct nbr *nbr, void *data, int len)
+send_prune(struct nbr *nbr, struct prune *p)
 {
 	struct sockaddr_in	 dst;
 	struct buf		*buf;
 	struct dvmrp_hdr	*dvmrp_hdr;
+	struct prune_hdr	 prune;
 	int			 ret = 0;
 
 	log_debug("send_prune: interface %s nbr %s", nbr->iface->name,
@@ -47,6 +48,12 @@ send_prune(struct nbr *nbr, void *data, int len)
 	if (nbr->iface->passive)
 		return (0);
 
+	bzero(&prune, sizeof(prune));
+
+	dst.sin_family = AF_INET;
+	dst.sin_len = sizeof(struct sockaddr_in);
+	dst.sin_addr = nbr->addr;
+
 	if ((buf = buf_open(nbr->iface->mtu - sizeof(struct ip))) == NULL)
 		fatal("send_prune");
 
@@ -54,9 +61,14 @@ send_prune(struct nbr *nbr, void *data, int len)
 	if (gen_dvmrp_hdr(buf, nbr->iface, DVMRP_CODE_PRUNE))
 		goto fail;
 
-	dst.sin_family = AF_INET;
-	dst.sin_len = sizeof(struct sockaddr_in);
-	dst.sin_addr = nbr->addr;
+	prune.src_host_addr = p->origin.s_addr;
+	prune.group_addr = p->group.s_addr;
+
+	/* XXX */
+	prune.lifetime = htonl(MAX_PRUNE_LIFETIME);
+	prune.src_netmask = p->netmask.s_addr;
+
+	buf_add(buf, &prune, sizeof(prune));
 
 	/* update chksum */
 	dvmrp_hdr = buf_seek(buf, 0, sizeof(dvmrp_hdr));
@@ -64,6 +76,7 @@ send_prune(struct nbr *nbr, void *data, int len)
 
 	ret = send_packet(nbr->iface, buf->buf, buf->wpos, &dst);
 	buf_free(buf);
+
 	return (ret);
 fail:
 	log_warn("send_prune");
@@ -74,7 +87,31 @@ fail:
 void
 recv_prune(struct nbr *nbr, char *buf, u_int16_t len)
 {
+	struct prune		 p;
+	struct prune_hdr	*prune;
+
 	log_debug("recv_prune: neighbor ID %s", inet_ntoa(nbr->id));
 
+	if (len < PRUNE_MIN_LEN) {
+		log_debug("recv_prune: packet malformed from %s",
+		    inet_ntoa(nbr->id));
+		return;
+	}
+
+	bzero(&p, sizeof(p));
+
+	prune = (struct prune_hdr *)buf;
+
+	p.origin.s_addr = prune->src_host_addr;
+	p.group.s_addr = prune->group_addr;
+	p.lifetime = prune->lifetime;
+
+	if (len >= sizeof(*prune))
+		p.netmask.s_addr = prune->src_netmask;
+
+	p.ifindex = nbr->iface->ifindex;
+
+	dvmrpe_imsg_compose_rde(IMSG_RECV_PRUNE, nbr->peerid, 0, &p, sizeof(p));
+
 	return;
 }
diff --git a/usr.sbin/dvmrpd/rde.c b/usr.sbin/dvmrpd/rde.c
index 6098765cacf..97ab615b86e 100644
--- a/usr.sbin/dvmrpd/rde.c
+++ b/usr.sbin/dvmrpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.12 2009/03/07 12:47:17 michele Exp $ */
+/*	$OpenBSD: rde.c,v 1.13 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -187,6 +187,7 @@ void
 rde_dispatch_imsg(int fd, short event, void *bula)
 {
 	struct mfc		 mfc;
+	struct prune		 p;
 	struct imsgbuf		*ibuf = bula;
 	struct imsg		 imsg;
 	struct route_report	 rr;
@@ -294,6 +295,12 @@ rde_dispatch_imsg(int fd, short event, void *bula)
 
 			rde_group_list_remove(iface, mfc.group);
 			break;
+		case IMSG_RECV_PRUNE:
+			if (imsg.hdr.len - IMSG_HEADER_SIZE != sizeof(p))
+				fatalx("invalid size of OE request");
+			memcpy(&p, imsg.data, sizeof(p));
+
+			break;
 		default:
 			log_debug("rde_dispatch_msg: unexpected imsg %d",
 			    imsg.hdr.type);
@@ -360,6 +367,7 @@ void
 rde_group_list_remove(struct iface *iface, struct in_addr group)
 {
 	struct rde_group	*rg;
+	struct rt_node		*rn;
 
 	if (TAILQ_EMPTY(&iface->rde_group_list))
 		fatalx("rde_group_list_remove: group does not exist");
@@ -373,4 +381,10 @@ rde_group_list_remove(struct iface *iface, struct in_addr group)
 			free(rg);
 		}
 	}
+
+	rn = mfc_find_origin(group);
+	if (rn == NULL)
+		return;
+
+	srt_check_downstream_ifaces(rn, iface);
 }
diff --git a/usr.sbin/dvmrpd/rde.h b/usr.sbin/dvmrpd/rde.h
index 4a55e096165..84c3ffee86a 100644
--- a/usr.sbin/dvmrpd/rde.h
+++ b/usr.sbin/dvmrpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.12 2009/03/07 12:47:17 michele Exp $ */
+/*	$OpenBSD: rde.h,v 1.13 2009/03/14 15:32:55 michele Exp $ */
 
 /*
  * Copyright (c) 2005, 2006 Esben Norby <norby@openbsd.org>
@@ -54,6 +54,7 @@ struct rt_node {
 struct mfc_node {
 	RB_ENTRY(mfc_node)	 entry;
 	struct event		 expiration_timer;
+	struct event		 prune_timer;
 	u_int8_t		 ttls[MAXVIFS];	/* outgoing vif(s) */
 	struct in_addr		 origin;
 	struct in_addr		 group;
@@ -86,6 +87,7 @@ void		 mfc_clear(void);
 void		 mfc_dump(pid_t);
 void		 mfc_update(struct mfc *);
 void		 mfc_delete(struct mfc *);
+struct rt_node	*mfc_find_origin(struct in_addr);
 void		 mfc_update_source(struct rt_node *);
 int		 mfc_check_members(struct rt_node *, struct iface *);
 
@@ -100,11 +102,13 @@ int		 rt_remove(struct rt_node *);
 void		 rt_clear(void);
 void		 rt_snap(u_int32_t);
 void		 rt_dump(pid_t);
+struct rt_node	*rt_match_origin(in_addr_t);
 
 int		 srt_check_route(struct route_report *, int);
 int		 src_compare(struct src_node *, struct src_node *);
 
 void		 srt_expire_nbr(struct in_addr, struct iface *);
+void		 srt_check_downstream_ifaces(struct rt_node *, struct iface *);
 
 RB_PROTOTYPE(src_head, src_node, entry, src_compare);
 
diff --git a/usr.sbin/dvmrpd/rde_mfc.c b/usr.sbin/dvmrpd/rde_mfc.c
index 6d3bc508839..9a0f7a0deb4 100644
--- a/usr.sbin/dvmrpd/rde_mfc.c
+++ b/usr.sbin/dvmrpd/rde_mfc.c
@@ -1,6 +1,7 @@
-/*	$OpenBSD: rde_mfc.c,v 1.4 2009/03/06 18:39:13 michele Exp $ */
+/*	$OpenBSD: rde_mfc.c,v 1.5 2009/03/14 15:32:55 michele Exp $ */
 
 /*
+ * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
  * Copyright (c) 2006 Esben Norby <norby@openbsd.org>
  *
  * Permission to use, copy, modify, and distribute this software for any
@@ -23,6 +24,7 @@
 #include <arpa/inet.h>
 #include <err.h>
 #include <stdlib.h>
+#include <string.h>
 
 #include "igmp.h"
 #include "dvmrp.h"
@@ -33,11 +35,15 @@
 
 /* multicast forwarding cache */
 
-void	 mfc_invalidate(void);
 void	 mfc_expire_timer(int, short, void *);
 int	 mfc_start_expire_timer(struct mfc_node *);
 int	 mfc_reset_expire_timer(struct mfc_node *);
+void	 mfc_prune_timer(int, short, void *);
+int	 mfc_start_prune_timer(struct mfc_node *);
+int	 mfc_reset_prune_timer(struct mfc_node *);
+
 int	 mfc_compare(struct mfc_node *, struct mfc_node *);
+void	 mfc_invalidate(void);
 
 RB_HEAD(mfc_tree, mfc_node)	 mfc;
 RB_PROTOTYPE(mfc_tree, mfc_node, entry, mfc_compare)
@@ -85,6 +91,38 @@ mfc_start_expire_timer(struct mfc_node *mn)
 	return (evtimer_add(&mn->expiration_timer, &tv));
 }
 
+void
+mfc_prune_timer(int fd, short event, void *arg)
+{
+	struct mfc_node	*mn = arg;
+
+	log_debug("mfc_prune_timer: group %s", inet_ntoa(mn->group));
+
+	event_del(&mn->prune_timer);
+}
+
+int
+mfc_start_prune_timer(struct mfc_node *mn)
+{
+	struct timeval	tv;
+
+	log_debug("mfc_start_prune_timer: group %s", inet_ntoa(mn->group));
+
+	timerclear(&tv);
+	tv.tv_sec = MAX_PRUNE_LIFETIME;
+	return (evtimer_add(&mn->prune_timer, &tv));
+}
+
+int
+mfc_reset_prune_timer(struct mfc_node *mn)
+{
+	struct timeval	tv;
+
+	timerclear(&tv);
+	tv.tv_sec = MAX_PRUNE_LIFETIME;
+	return (evtimer_add(&mn->prune_timer, &tv));
+}
+
 /* route table */
 void
 mfc_init(void)
@@ -185,19 +223,38 @@ mfc_dump(pid_t pid)
 	}
 }
 
+struct rt_node *
+mfc_find_origin(struct in_addr group)
+{
+	struct mfc_node	*mn;
+
+	RB_FOREACH(mn, mfc_tree, &mfc)
+		if (group.s_addr == mn->group.s_addr)
+			return (rt_match_origin(mn->origin.s_addr));
+
+	return (NULL);
+}
+
 void
 mfc_update_source(struct rt_node *rn)
 {
 	struct mfc_node		*mn;
 	struct mfc		 m;
+	struct prune		 p;
 	int			 i;
+	u_int8_t		 found;
 
 	RB_FOREACH(mn, mfc_tree, &mfc) {
 		if (rn->prefix.s_addr == mn->origin.s_addr) {
 			mn->ifindex = rn->ifindex;
 
-			for (i = 0; i < MAXVIFS; i++)
+			found = 0;
+
+			for (i = 0; i < MAXVIFS; i++) {
 				mn->ttls[i] = rn->ttls[i];
+				if (mn->ttls[i] != 0)
+					found = 1;
+			}
 
 			m.origin.s_addr = mn->origin.s_addr;
 			m.group.s_addr = mn->group.s_addr;
@@ -206,11 +263,27 @@ mfc_update_source(struct rt_node *rn)
 			for (i = 0; i < MAXVIFS; i++)
 				m.ttls[i] = mn->ttls[i];
 
-			if (mn->origin.s_addr != 0)
-				rde_imsg_compose_parent(IMSG_MFC_ADD, 0, &m,
-				    sizeof(m));
+			rde_imsg_compose_parent(IMSG_MFC_ADD, 0, &m, sizeof(m));
 
 			mfc_reset_expire_timer(mn);
+
+			if (!found) {
+				/* We have removed all downstream interfaces,
+				   start the pruning process */
+				bzero(&p, sizeof(p));
+
+				p.origin.s_addr = mn->origin.s_addr;
+				p.netmask.s_addr =
+				    prefixlen2mask(rn->prefixlen);
+				p.group.s_addr = mn->group.s_addr;
+				p.nexthop.s_addr = rn->nexthop.s_addr;
+				p.ifindex = mn->ifindex;
+
+				rde_imsg_compose_dvmrpe(IMSG_SEND_PRUNE, 0, 0,
+				    &p, sizeof(p));
+
+				mfc_start_prune_timer(mn);
+			}
 		}
 	}
 }
@@ -236,12 +309,12 @@ mfc_update(struct mfc *nmfc)
 			mn->ttls[i] = nmfc->ttls[i];
 
 		if (mfc_insert(mn) == 0) {
-			if (nmfc->origin.s_addr != 0)
-				rde_imsg_compose_parent(IMSG_MFC_ADD, 0, nmfc,
-				    sizeof(*nmfc));
+			rde_imsg_compose_parent(IMSG_MFC_ADD, 0, nmfc,
+			    sizeof(*nmfc));
 		}
 
 		evtimer_set(&mn->expiration_timer, mfc_expire_timer, mn);
+		evtimer_set(&mn->prune_timer, mfc_expire_timer, mn);
 		mfc_start_expire_timer(mn);
 	}
 }
diff --git a/usr.sbin/dvmrpd/rde_srt.c b/usr.sbin/dvmrpd/rde_srt.c
index 27fbfbb2234..063dab4536d 100644
--- a/usr.sbin/dvmrpd/rde_srt.c
+++ b/usr.sbin/dvmrpd/rde_srt.c
@@ -1,6 +1,7 @@
-/*	$OpenBSD: rde_srt.c,v 1.18 2009/03/06 18:39:13 michele Exp $ */
+/*	$OpenBSD: rde_srt.c,v 1.19 2009/03/14 15:32:55 michele 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
@@ -313,6 +314,18 @@ rt_update(struct rt_node *rn)
 		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 & prefixlen2mask(r->prefixlen)))
+			return (r);
+
+	return (NULL);
+}
+
 int
 srt_check_route(struct route_report *rr, int connected)
 {
@@ -518,6 +531,12 @@ srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface)
 	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)
@@ -530,7 +549,7 @@ srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface)
 
 	/* There are still group members for this source on this iface
 	   Keep things as they currently are */
-	if (!mfc_check_members(rn, iface))
+	if (mfc_check_members(rn, iface))
 		return;
 
 	/* Remove interface from the downstream list */