Implement most prefixlen operations as OP_RANGE (prefixlen A - B).

Simplify the RDE logic this way and make it possible to load such ranges
into a much faster lookup trie for prefix-sets.
When printing the config bgpd tries to use the nices way to express the rule:
e.g.    match from any prefix 18.0.0.0/8 prefixlen 8 - 32
becomes match from any prefix 18.0.0.0/8 or-longer
Apart from that there is no user visible change because of this.
OK sthen@

3 files changed, 100 insertions, 121 deletions

diff --git a/usr.sbin/bgpd/parse.y b/usr.sbin/bgpd/parse.y
index 6e21b01ade7..7194e3f16e2 100644
--- a/usr.sbin/bgpd/parse.y
+++ b/usr.sbin/bgpd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.332 2018/09/05 09:49:57 claudio Exp $ */
+/*	$OpenBSD: parse.y,v 1.333 2018/09/05 17:32:43 claudio Exp $ */
 
 /*
  * Copyright (c) 2002, 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -2086,21 +2086,49 @@ filter_elm	: filter_prefix_h	{
 prefixlenop	: /* empty */			{ bzero(&$$, sizeof($$)); }
 		| LONGER				{
 			bzero(&$$, sizeof($$));
-			$$.op = OP_GE;
+			$$.op = OP_RANGE;
 			$$.len_min = -1;
+			$$.len_max = -1;
 		}
 		| PREFIXLEN unaryop NUMBER		{
+			int min, max;
+
 			bzero(&$$, sizeof($$));
 			if ($3 < 0 || $3 > 128) {
 				yyerror("prefixlen must be >= 0 and <= 128");
 				YYERROR;
 			}
-			if ($2 == OP_GT && $3 == 0) {
-				yyerror("prefixlen must be > 0");
-				YYERROR;
+			/*
+			 * convert the unary operation into the equivalent
+			 * range check
+			 */
+			$$.op = OP_RANGE;
+
+			switch ($2) {
+			case OP_EQ:
+			case OP_NE:
+				min = max = $3;
+				$$.op = $2;
+				break;
+			case OP_LT:
+				if ($3 == 0) {
+					yyerror("prefixlen must be > 0");
+					YYERROR;
+				}
+				$3 -= 1;
+			case OP_LE:
+				min = -1;
+				max = $3;
+				break;
+			case OP_GT:
+				$3 += 1;
+			case OP_GE:
+				min = $3;
+				max = -1;
+				break;
 			}
-			$$.op = $2;
-			$$.len_min = $3;
+			$$.len_min = min;
+			$$.len_max = max;
 		}
 		| PREFIXLEN NUMBER binaryop NUMBER	{
 			bzero(&$$, sizeof($$));
@@ -2108,7 +2136,7 @@ prefixlenop	: /* empty */			{ bzero(&$$, sizeof($$)); }
 				yyerror("prefixlen must be < 128");
 				YYERROR;
 			}
-			if ($2 >= $4) {
+			if ($2 > $4) {
 				yyerror("start prefixlen is bigger than end");
 				YYERROR;
 			}
@@ -3696,60 +3724,35 @@ merge_prefixspec(struct filter_prefix_l *p, struct filter_prefixlen *pl)
 		break;
 	}
 
-	switch (pl->op) {
-	case OP_NONE:
+	if (pl->op == OP_NONE) {
+		p->p.len_min = p->p.len_max = p->p.len;
 		return (0);
-	case OP_RANGE:
-	case OP_XRANGE:
-		if (pl->len_min > max_len || pl->len_max > max_len) {
-			yyerror("prefixlen %d too big for AF, limit %d",
-			    pl->len_min > max_len ? pl->len_min : pl->len_max,
-			    max_len);
-			return (-1);
-		}
-		if (pl->len_min < p->p.len) {
-			yyerror("prefixlen %d smaller than prefix, limit %d",
-			    pl->len_min, p->p.len);
-			return (-1);
-		}
-		p->p.len_max = pl->len_max;
-		break;
-	case OP_GE:
-		/* fix up the "or-longer" case */
-		if (pl->len_min == -1)
-			pl->len_min = p->p.len;
-		/* FALLTHROUGH */
-	case OP_EQ:
-	case OP_NE:
-	case OP_LE:
-	case OP_GT:
-		if (pl->len_min > max_len) {
-			yyerror("prefixlen %d too big for AF, limit %d",
-			    pl->len_min, max_len);
-			return (-1);
-		}
-		if (pl->len_min < p->p.len) {
-			yyerror("prefixlen %d smaller than prefix, limit %d",
-			    pl->len_min, p->p.len);
-			return (-1);
-		}
-		break;
-	case OP_LT:
-		if (pl->len_min > max_len - 1) {
-			yyerror("prefixlen %d too big for AF, limit %d",
-			    pl->len_min, max_len - 1);
-			return (-1);
-		}
-		if (pl->len_min < p->p.len + 1) {
-			yyerror("prefixlen %d too small for prefix, limit %d",
-			    pl->len_min, p->p.len + 1);
-			return (-1);
-		}
-		break;
+	}
+
+	if (pl->len_min == -1)
+		pl->len_min = p->p.len;
+	if (pl->len_max == -1)
+		pl->len_max = max_len;
+
+	if (pl->len_max > max_len) {
+		yyerror("prefixlen %d too big, limit %d",
+		    pl->len_max, max_len);
+		return (-1);
+	}
+	if (pl->len_min > pl->len_max) {
+		yyerror("prefixlen %d too big, limit %d",
+		    pl->len_min, pl->len_max);
+		return (-1);
+	}
+	if (pl->len_min < p->p.len) {
+		yyerror("prefixlen %d smaller than prefix, limit %d",
+		    pl->len_min, p->p.len);
+		return (-1);
 	}
 
 	p->p.op = pl->op;
 	p->p.len_min = pl->len_min;
+	p->p.len_max = pl->len_max;
 	return (0);
 }
 
diff --git a/usr.sbin/bgpd/printconf.c b/usr.sbin/bgpd/printconf.c
index 49e93e16954..0690679cac2 100644
--- a/usr.sbin/bgpd/printconf.c
+++ b/usr.sbin/bgpd/printconf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: printconf.c,v 1.110 2018/09/05 09:49:57 claudio Exp $	*/
+/*	$OpenBSD: printconf.c,v 1.111 2018/09/05 17:32:43 claudio Exp $	*/
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -29,7 +29,7 @@
 #include "rde.h"
 #include "log.h"
 
-void		 print_op(enum comp_ops);
+void		 print_prefix(struct filter_prefix *p, const char *);
 void		 print_community(int, int);
 void		 print_largecommunity(int64_t, int64_t, int64_t);
 void		 print_extcommunity(struct filter_extcommunity *);
@@ -55,35 +55,47 @@ void		 print_groups(struct bgpd_config *, struct peer *);
 int		 peer_compare(const void *, const void *);
 
 void
-print_op(enum comp_ops op)
+print_prefix(struct filter_prefix *p, const char *s)
 {
-	switch (op) {
-	case OP_RANGE:
-		printf("-");
+	u_int8_t max_len = 0;
+
+	switch (p->addr.aid) {
+	case AID_INET:
+	case AID_VPN_IPv4:
+		max_len = 32;
 		break;
-	case OP_XRANGE:
-		printf("><");
+	case AID_INET6:
+		max_len = 128;
+		break;
+	case AID_UNSPEC:
+		/* no prefix to print */
+		return;
+	}
+
+	printf("%s%s/%u ", s, log_addr(&p->addr), p->len);
+
+	switch (p->op) {
+	case OP_NONE:
 		break;
 	case OP_EQ:
-		printf("=");
+		printf("prefixlen = %u ", p->len_min);
 		break;
 	case OP_NE:
-		printf("!=");
-		break;
-	case OP_LE:
-		printf("<=");
+		printf("prefixlen != %u ", p->len_min);
 		break;
-	case OP_LT:
-		printf("<");
-		break;
-	case OP_GE:
-		printf(">=");
+	case OP_XRANGE:
+		printf("prefixlen %u >< %u ", p->len_min, p->len_max);
 		break;
-	case OP_GT:
-		printf(">");
+	case OP_RANGE:
+		if (p->len == p->len_min && p->len_max == max_len)
+			printf("or-longer ");
+		else if (p->len_max == max_len)
+			printf("prefixlen >= %u ", p->len_min);
+		else
+			printf("prefixlen %u - %u ", p->len_min, p->len_max);
 		break;
 	default:
-		printf("?");
+		printf("prefixlen %u ??? %u ", p->len_min, p->len_max);
 		break;
 	}
 }
@@ -433,23 +445,8 @@ print_prefixsets(struct prefixset_head *psh)
 
 	SIMPLEQ_FOREACH(ps, psh, entry) {
 		printf("prefix-set \"%s\" { ", ps->name);
-		SIMPLEQ_FOREACH(psi, &ps->psitems, entry) {
-			if (psi->p.addr.aid)
-				printf("%s/%u ", log_addr(&psi->p.addr),
-				    psi->p.len);
-			if (psi->p.op) {
-				if (psi->p.op == OP_RANGE ||
-				    psi->p.op == OP_XRANGE) {
-					printf("prefixlen %u ", psi->p.len_min);
-					print_op(psi->p.op);
-					printf(" %u ", psi->p.len_max);
-				} else {
-					printf("prefixlen ");
-					print_op(psi->p.op);
-					printf(" %u ", psi->p.len_min);
-				}
-			}
-		}
+		SIMPLEQ_FOREACH(psi, &ps->psitems, entry)
+			print_prefix(&psi->p, "");
 		printf(" }\n");
 	}
 }
@@ -676,22 +673,7 @@ print_rule(struct peer *peer_l, struct filter_rule *r)
 	} else
 		printf("any ");
 
-	if (r->match.prefix.addr.aid)
-		printf("prefix %s/%u ", log_addr(&r->match.prefix.addr),
-		    r->match.prefix.len);
-
-	if (r->match.prefix.op) {
-		if (r->match.prefix.op == OP_RANGE ||
-		    r->match.prefix.op == OP_XRANGE) {
-			printf("prefixlen %u ", r->match.prefix.len_min);
-			print_op(r->match.prefix.op);
-			printf(" %u ", r->match.prefix.len_max);
-		} else {
-			printf("prefixlen ");
-			print_op(r->match.prefix.op);
-			printf(" %u ", r->match.prefix.len_min);
-		}
-	}
+	print_prefix(&r->match.prefix, "prefix ");
 
 	if (r->match.prefixset.flags & PREFIXSET_FLAG_FILTER)
 		printf("prefix-set \"%s\" ", r->match.prefixset.name);
diff --git a/usr.sbin/bgpd/rde_filter.c b/usr.sbin/bgpd/rde_filter.c
index ddfa2ac39bb..a314181ff26 100644
--- a/usr.sbin/bgpd/rde_filter.c
+++ b/usr.sbin/bgpd/rde_filter.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_filter.c,v 1.100 2018/09/05 09:49:57 claudio Exp $ */
+/*	$OpenBSD: rde_filter.c,v 1.101 2018/09/05 17:32:43 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -532,16 +532,10 @@ rde_prefix_match(struct filter_prefix *fp, struct prefix *p)
 	case OP_XRANGE:
 		return ((plen < fp->len_min) ||
 		    (plen > fp->len_max));
-	case OP_LE:
-		return (plen <= fp->len_min);
-	case OP_LT:
-		return (plen < fp->len_min);
-	case OP_GE:
-		return (plen >= fp->len_min);
-	case OP_GT:
-		return (plen > fp->len_min);
+	default:
+		log_warnx("%s: unsupported prefix operation", __func__);
+		return (0);
 	}
-	return (0); /* should not be reached */
 }
 
 /* return true when the rule f can never match for this peer */