Switch prefixset to an RB_TREE instead of a SIMPLEQ. This allows to trigger

on duplicates (which are only reported) but is needed as a preparation step
for roa-sets.
OK benno@ denis@

5 files changed, 90 insertions, 21 deletions

diff --git a/usr.sbin/bgpd/bgpd.c b/usr.sbin/bgpd/bgpd.c
index c06100781c9..239eccebdac 100644
--- a/usr.sbin/bgpd/bgpd.c
+++ b/usr.sbin/bgpd/bgpd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.c,v 1.198 2018/09/09 11:00:51 benno Exp $ */
+/*	$OpenBSD: bgpd.c,v 1.199 2018/09/20 07:46:39 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -437,7 +437,7 @@ reconfigure(char *conffile, struct bgpd_config *conf, struct peer **peer_l)
 	struct rde_rib		*rr;
 	struct rdomain		*rd;
 	struct prefixset	*ps;
-	struct prefixset_item	*psi;
+	struct prefixset_item	*psi, *npsi;
 
 	if (reconfpending) {
 		log_info("previous reload still running");
@@ -510,8 +510,8 @@ reconfigure(char *conffile, struct bgpd_config *conf, struct peer **peer_l)
 		if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIXSET, 0, 0, -1,
 		    ps->name, sizeof(ps->name)) == -1)
 			return (-1);
-		while ((psi = SIMPLEQ_FIRST(&ps->psitems)) != NULL) {
-			SIMPLEQ_REMOVE_HEAD(&ps->psitems, entry);
+		RB_FOREACH_SAFE(psi, prefixset_tree, &ps->psitems, npsi) {
+			RB_REMOVE(prefixset_tree, &ps->psitems, psi);
 			if (imsg_compose(ibuf_rde, IMSG_RECONF_PREFIXSETITEM, 0,
 			    0, -1, psi, sizeof(*psi)) == -1)
 				return (-1);
diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h
index f60372f2aa3..cad8b49714b 100644
--- a/usr.sbin/bgpd/bgpd.h
+++ b/usr.sbin/bgpd/bgpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.h,v 1.341 2018/09/18 15:14:07 claudio Exp $ */
+/*	$OpenBSD: bgpd.h,v 1.342 2018/09/20 07:46:39 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -958,15 +958,15 @@ struct roa_set {
 };
 
 struct prefixset_item {
-	struct filter_prefix		 p;
-	SIMPLEQ_ENTRY(prefixset_item)	 entry;
+	struct filter_prefix		p;
+	RB_ENTRY(prefixset_item)	entry;
 };
-SIMPLEQ_HEAD(prefixset_items_h, prefixset_item);
+RB_HEAD(prefixset_tree, prefixset_item);
 
 struct prefixset {
 	int				 sflags;
 	char				 name[SET_NAME_LEN];
-	struct prefixset_items_h	 psitems;
+	struct prefixset_tree		 psitems;
 	SIMPLEQ_ENTRY(prefixset)	 entry;
 };
 
@@ -1090,6 +1090,8 @@ void	filterlist_free(struct filter_head *);
 int	host(const char *, struct bgpd_addr *, u_int8_t *);
 void	copy_filterset(struct filter_set_head *, struct filter_set_head *);
 void	expand_networks(struct bgpd_config *);
+int	prefixset_cmp(struct prefixset_item *, struct prefixset_item *);
+RB_PROTOTYPE(prefixset_tree, prefixset_item, entry, prefixset_cmp);
 
 /* kroute.c */
 int		 kr_init(void);
diff --git a/usr.sbin/bgpd/config.c b/usr.sbin/bgpd/config.c
index 1c0984facaf..b34d7aaec5e 100644
--- a/usr.sbin/bgpd/config.c
+++ b/usr.sbin/bgpd/config.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: config.c,v 1.73 2018/09/09 11:00:51 benno Exp $ */
+/*	$OpenBSD: config.c,v 1.74 2018/09/20 07:46:39 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004, 2005 Henning Brauer <henning@openbsd.org>
@@ -120,16 +120,15 @@ void
 free_prefixsets(struct prefixset_head *psh)
 {
 	struct prefixset	*ps;
-	struct prefixset_item	*psi;
+	struct prefixset_item	*psi, *npsi;
 
 	if (psh == NULL)
 		return;
 
 	while (!SIMPLEQ_EMPTY(psh)) {
 		ps = SIMPLEQ_FIRST(psh);
-		while (!SIMPLEQ_EMPTY(&ps->psitems)) {
-			psi = SIMPLEQ_FIRST(&ps->psitems);
-			SIMPLEQ_REMOVE_HEAD(&ps->psitems, entry);
+		RB_FOREACH_SAFE(psi, prefixset_tree, &ps->psitems, npsi) {
+			RB_REMOVE(prefixset_tree, &ps->psitems, psi);
 			free(psi);
 		}
 		SIMPLEQ_REMOVE_HEAD(psh, entry);
@@ -529,7 +528,7 @@ expand_networks(struct bgpd_config *c)
 			    == NULL)
 				fatal("%s: prefixset %s not found", __func__,
 				    n->net.psname);
-			SIMPLEQ_FOREACH(psi, &ps->psitems, entry) {
+			RB_FOREACH(psi, prefixset_tree, &ps->psitems) {
 				if ((m = calloc(1, sizeof(struct network)))
 				    == NULL)
 					fatal(NULL);
@@ -546,3 +545,48 @@ expand_networks(struct bgpd_config *c)
 		}
 	}
 }
+
+int
+prefixset_cmp(struct prefixset_item *a, struct prefixset_item *b)
+{
+	int i;
+
+	if (a->p.addr.aid < b->p.addr.aid)
+		return (-1);
+	if (a->p.addr.aid > b->p.addr.aid)
+		return (1);
+
+	switch (a->p.addr.aid) {
+	case AID_INET:
+		if (ntohl(a->p.addr.v4.s_addr) < ntohl(b->p.addr.v4.s_addr))
+			return (-1);
+		if (ntohl(a->p.addr.v4.s_addr) > ntohl(b->p.addr.v4.s_addr))
+			return (1);
+		break;
+	case AID_INET6:
+		i = memcmp(&a->p.addr.v6, &b->p.addr.v6,
+		    sizeof(struct in6_addr));
+		if (i > 0)
+			return (1);
+		if (i < 0)
+			return (-1);
+		break;
+	default:
+		fatalx("%s: unknown af", __func__);
+	}
+	if (a->p.len < b->p.len)
+		return (-1);
+	if (a->p.len > b->p.len)
+		return (1);
+	if (a->p.len_min < b->p.len_min)
+		return (-1);
+	if (a->p.len_min > b->p.len_min)
+		return (1);
+	if (a->p.len_max < b->p.len_max)
+		return (-1);
+	if (a->p.len_max > b->p.len_max)
+		return (1);
+	return (0);
+}
+
+RB_GENERATE(prefixset_tree, prefixset_item, entry, prefixset_cmp);
diff --git a/usr.sbin/bgpd/parse.y b/usr.sbin/bgpd/parse.y
index 4c4fec3ad1a..31266d2dde0 100644
--- a/usr.sbin/bgpd/parse.y
+++ b/usr.sbin/bgpd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.353 2018/09/14 10:22:11 claudio Exp $ */
+/*	$OpenBSD: parse.y,v 1.354 2018/09/20 07:46:39 claudio Exp $ */
 
 /*
  * Copyright (c) 2002, 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -443,14 +443,37 @@ prefixset	: PREFIXSET STRING '{' optnl		{
 		}
 
 prefixset_l	: prefixset_item			{
-			SIMPLEQ_INSERT_TAIL(&curpset->psitems, $1, entry);
+			struct prefixset_item	*psi;
+			psi = RB_INSERT(prefixset_tree, &curpset->psitems, $1);
+			if (psi != NULL) {
+				if (cmd_opts & BGPD_OPT_VERBOSE2)
+					log_warnx("warning: duplicate entry in "
+					    "prefixset \"%s\" for %s/%u",
+					    curpset->name,
+					    log_addr(&$1->p.addr), $1->p.len);
+				free($1);
+			}
 		}
 		| prefixset_l comma prefixset_item	{
-			SIMPLEQ_INSERT_TAIL(&curpset->psitems, $3, entry);
+			struct prefixset_item	*psi;
+			psi = RB_INSERT(prefixset_tree, &curpset->psitems, $3);
+			if (psi != NULL) {
+				if (cmd_opts & BGPD_OPT_VERBOSE2)
+					log_warnx("warning: duplicate entry in "
+					    "prefixset \"%s\" for %s/%u",
+					    curpset->name,
+					    log_addr(&$3->p.addr), $3->p.len);
+				free($3);
+			}
 		}
 		;
 
 prefixset_item	: prefix prefixlenop			{
+			if ($2.op != OP_NONE && $2.op != OP_RANGE) {
+				yyerror("unsupported prefixlen operation in "
+				    "prefix-set");
+				YYERROR;
+			}
 			if (($$ = calloc(1, sizeof(*$$))) == NULL)
 				fatal(NULL);
 			memcpy(&$$->p.addr, &$1.prefix, sizeof($$->p.addr));
@@ -4223,6 +4246,6 @@ new_prefix_set(char *name)
 		    name, sizeof(curpset->name) - 1);
 			return -1;
 	}
-	SIMPLEQ_INIT(&curpset->psitems);
+	RB_INIT(&curpset->psitems);
 	return 0;
 }
diff --git a/usr.sbin/bgpd/printconf.c b/usr.sbin/bgpd/printconf.c
index 48b1404b47b..43d4b31060e 100644
--- a/usr.sbin/bgpd/printconf.c
+++ b/usr.sbin/bgpd/printconf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: printconf.c,v 1.119 2018/09/13 11:25:41 claudio Exp $	*/
+/*	$OpenBSD: printconf.c,v 1.120 2018/09/20 07:46:39 claudio Exp $	*/
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -451,7 +451,7 @@ print_prefixsets(struct prefixset_head *psh)
 	SIMPLEQ_FOREACH(ps, psh, entry) {
 		int count = 0;
 		printf("prefix-set \"%s\" {", ps->name);
-		SIMPLEQ_FOREACH(psi, &ps->psitems, entry) {
+		RB_FOREACH(psi, prefixset_tree, &ps->psitems) {
 			if (count++ % 2 == 0)
 				printf("\n\t");
 			else