Introduce minimal tracking of announced prefixes. A per peer RB tree tracks

which prefixes were sent out as UPDATE. At withdraw time the RB tree can be
consulted to know if the withdraw actually needs to be sent to the peer.
This replaces the faulty heuristic that was used before and caused either
that unneeded withdraw to be sent or in the worst case failing to send a
necessary withdraw resulting in stuck routes.
OK benno@

3 files changed, 66 insertions, 8 deletions

diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c
index 871e6f822fc..21d40c97614 100644
--- a/usr.sbin/bgpd/rde.c
+++ b/usr.sbin/bgpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.427 2018/09/25 08:08:38 claudio Exp $ */
+/*	$OpenBSD: rde.c,v 1.428 2018/09/29 07:43:36 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -3147,9 +3147,11 @@ rde_softreconfig_out_peer(struct rib_entry *re, struct rde_peer *peer)
 		/* nothing todo */
 	if (oa == ACTION_DENY && na == ACTION_ALLOW) {
 		/* send update */
+		up_rib_add(peer, re);
 		up_generate(peer, &nstate, &addr, pt->prefixlen);
 	} else if (oa == ACTION_ALLOW && na == ACTION_DENY) {
 		/* send withdraw */
+		up_rib_remove(peer, re);
 		up_generate(peer, NULL, &addr, pt->prefixlen);
 	} else if (oa == ACTION_ALLOW && na == ACTION_ALLOW) {
 		/* send update if anything changed */
@@ -3197,6 +3199,7 @@ rde_softreconfig_unload_peer(struct rib_entry *re, void *ptr)
 	    prefix_nhflags(p));
 	if (rde_filter(out_rules_tmp, peer, p, &ostate) != ACTION_DENY) {
 		/* send withdraw */
+		up_rib_remove(peer, re);
 		up_generate(peer, NULL, &addr, pt->prefixlen);
 	}
 	rde_filterstate_clean(&ostate);
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 74417487d6a..83ede7b83e3 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.193 2018/09/20 11:45:59 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.194 2018/09/29 07:43:36 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -55,6 +55,7 @@ LIST_HEAD(aspath_head, rde_aspath);
 TAILQ_HEAD(aspath_queue, rde_aspath);
 RB_HEAD(uptree_prefix, update_prefix);
 RB_HEAD(uptree_attr, update_attr);
+RB_HEAD(uptree_rib, update_rib);
 
 struct rib_desc;
 struct rib;
@@ -70,6 +71,7 @@ struct rde_peer {
 	struct bgpd_addr		 remote_addr;
 	struct bgpd_addr		 local_v4_addr;
 	struct bgpd_addr		 local_v6_addr;
+	struct uptree_rib		 up_rib;
 	struct uptree_prefix		 up_prefix;
 	struct uptree_attr		 up_attrs;
 	struct uplist_attr		 updates[AID_MAX];
@@ -566,6 +568,8 @@ int		 nexthop_compare(struct nexthop *, struct nexthop *);
 /* rde_update.c */
 void		 up_init(struct rde_peer *);
 void		 up_down(struct rde_peer *);
+int		 up_rib_remove(struct rde_peer *, struct rib_entry *);
+void		 up_rib_add(struct rde_peer *, struct rib_entry *);
 int		 up_test_update(struct rde_peer *, struct prefix *);
 int		 up_generate(struct rde_peer *, struct filterstate *,
 		     struct bgpd_addr *, u_int8_t);
diff --git a/usr.sbin/bgpd/rde_update.c b/usr.sbin/bgpd/rde_update.c
index 63f11294208..a42d6f88381 100644
--- a/usr.sbin/bgpd/rde_update.c
+++ b/usr.sbin/bgpd/rde_update.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_update.c,v 1.99 2018/09/18 16:54:01 sthen Exp $ */
+/*	$OpenBSD: rde_update.c,v 1.100 2018/09/29 07:43:36 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -53,9 +53,15 @@ struct update_attr {
 	u_int16_t			 mpattr_len;
 };
 
+struct update_rib {
+	RB_ENTRY(update_rib)		 entry;
+	struct rib_entry		*re;
+};
+
 void	up_clear(struct uplist_attr *, struct uplist_prefix *);
 int	up_prefix_cmp(struct update_prefix *, struct update_prefix *);
 int	up_attr_cmp(struct update_attr *, struct update_attr *);
+int	up_rib_cmp(struct update_rib *, struct update_rib *);
 int	up_add(struct rde_peer *, struct update_prefix *, struct update_attr *);
 
 RB_PROTOTYPE(uptree_prefix, update_prefix, entry, up_prefix_cmp)
@@ -64,6 +70,9 @@ RB_GENERATE(uptree_prefix, update_prefix, entry, up_prefix_cmp)
 RB_PROTOTYPE(uptree_attr, update_attr, entry, up_attr_cmp)
 RB_GENERATE(uptree_attr, update_attr, entry, up_attr_cmp)
 
+RB_PROTOTYPE(uptree_rib, update_rib, entry, up_rib_cmp)
+RB_GENERATE(uptree_rib, update_rib, entry, up_rib_cmp)
+
 SIPHASH_KEY uptree_key;
 
 void
@@ -77,6 +86,7 @@ up_init(struct rde_peer *peer)
 	}
 	RB_INIT(&peer->up_prefix);
 	RB_INIT(&peer->up_attrs);
+	RB_INIT(&peer->up_rib);
 	peer->up_pcnt = 0;
 	peer->up_acnt = 0;
 	peer->up_nlricnt = 0;
@@ -110,13 +120,18 @@ up_clear(struct uplist_attr *updates, struct uplist_prefix *withdraws)
 void
 up_down(struct rde_peer *peer)
 {
-	u_int8_t	i;
+	struct update_rib	*ur, *nur;
+	u_int8_t		i;
 
 	for (i = 0; i < AID_MAX; i++)
 		up_clear(&peer->updates[i], &peer->withdraws[i]);
 
 	RB_INIT(&peer->up_prefix);
 	RB_INIT(&peer->up_attrs);
+	RB_FOREACH_SAFE(ur, uptree_rib, &peer->up_rib, nur) {
+		RB_REMOVE(uptree_rib, &peer->up_rib, ur);
+		free(ur);
+	}
 
 	peer->up_pcnt = 0;
 	peer->up_acnt = 0;
@@ -195,6 +210,42 @@ up_attr_cmp(struct update_attr *a, struct update_attr *b)
 }
 
 int
+up_rib_cmp(struct update_rib *a, struct update_rib *b)
+{
+	if (a->re != b->re)
+		return (a->re > b->re ? 1 : -1);
+	return 0;
+}
+
+int
+up_rib_remove(struct rde_peer *peer, struct rib_entry *re)
+{
+	struct update_rib *ur, u;
+	u.re = re;
+
+	ur = RB_FIND(uptree_rib, &peer->up_rib, &u);
+	if (ur != NULL) {
+		RB_REMOVE(uptree_rib, &peer->up_rib, ur);
+		free(ur);
+		return 1;
+	} else
+		return 0;
+}
+
+void
+up_rib_add(struct rde_peer *peer, struct rib_entry *re)
+{
+	struct update_rib *ur;
+
+	if ((ur = calloc(1, sizeof(*ur))) == NULL)
+		fatal("%s", __func__);
+	ur->re = re;
+
+	if (RB_INSERT(uptree_rib, &peer->up_rib, ur) != NULL)
+		free(ur);
+}
+
+int
 up_add(struct rde_peer *peer, struct update_prefix *p, struct update_attr *a)
 {
 	struct update_attr	*na = NULL;
@@ -409,11 +460,11 @@ withdraw:
 		if (up_test_update(peer, old) != 1)
 			return;
 
-		pt_getaddr(old->re->prefix, &addr);
-		if (rde_filter(rules, peer, old, NULL) == ACTION_DENY)
+		if (!up_rib_remove(peer, old->re))
 			return;
 
 		/* withdraw prefix */
+		pt_getaddr(old->re->prefix, &addr);
 		up_generate(peer, NULL, &addr, old->re->prefix->prefixlen);
 	} else {
 		switch (up_test_update(peer, new)) {
@@ -433,8 +484,8 @@ withdraw:
 		}
 
 		pt_getaddr(new->re->prefix, &addr);
-		up_generate(peer, &state, &addr,
-		    new->re->prefix->prefixlen);
+		up_generate(peer, &state, &addr, new->re->prefix->prefixlen);
+		up_rib_add(peer, new->re);
 
 		rde_filterstate_clean(&state);
 	}