Refactor aspath code a bit. Move cached source_as (for origin validation)

into struct aspath and pass that struct to aspath_match().
OK denis@

7 files changed, 175 insertions, 178 deletions

diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h
index 5e2560c210a..51bdedf157a 100644
--- a/usr.sbin/bgpd/bgpd.h
+++ b/usr.sbin/bgpd/bgpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.h,v 1.356 2018/12/06 12:38:00 claudio Exp $ */
+/*	$OpenBSD: bgpd.h,v 1.357 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -1258,7 +1258,6 @@ const char	*log_shutcomm(const char *);
 int		 aspath_snprint(char *, size_t, void *, u_int16_t);
 int		 aspath_asprint(char **, void *, u_int16_t);
 size_t		 aspath_strlen(void *, u_int16_t);
-int		 aspath_match(void *, u_int16_t, struct filter_as *, u_int32_t);
 u_int32_t	 aspath_extract(const void *, int);
 int		 aspath_verify(void *, u_int16_t, int);
 #define		 AS_ERR_LEN	-1
diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c
index f141766f94e..905d19c6d9f 100644
--- a/usr.sbin/bgpd/rde.c
+++ b/usr.sbin/bgpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.451 2018/11/29 15:11:27 claudio Exp $ */
+/*	$OpenBSD: rde.c,v 1.452 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -482,7 +482,6 @@ rde_dispatch_imsg_session(struct imsgbuf *ibuf)
 			asp->origin = csr.origin;
 			asp->flags |= F_PREFIX_ANNOUNCED | F_ANN_DYNAMIC;
 			asp->aspath = aspath_get(asdata, csr.aspath_len);
-			asp->source_as = aspath_origin(asp->aspath);
 			netconf_s.asp = asp;
 			break;
 		case IMSG_NETWORK_ATTR:
@@ -1121,10 +1120,6 @@ rde_update_dispatch(struct imsg *imsg)
 			}
 		}
 
-		if (state.aspath.flags & F_ATTR_ASPATH)
-			state.aspath.source_as =
-			    aspath_origin(state.aspath.aspath);
-
 		rde_reflector(peer, &state.aspath);
 	}
 
@@ -1389,7 +1384,7 @@ rde_update_update(struct rde_peer *peer, struct filterstate *in,
 
 	peer->prefix_rcvd_update++;
 	vstate = rde_roa_validity(&conf->rde_roa, prefix, prefixlen,
-	    in->aspath.source_as);
+	    aspath_origin(in->aspath.aspath));
 
 	/* add original path to the Adj-RIB-In */
 	if (path_update(&ribs[RIB_ADJ_IN].rib, peer, in, prefix, prefixlen,
@@ -2220,8 +2215,8 @@ rde_dump_filter(struct prefix *p, struct ctl_show_rib_request *req)
 	if ((req->flags & F_CTL_INVALID) &&
 	    (asp->flags & F_ATTR_PARSE_ERR) == 0)
 		return;
-	if (req->as.type != AS_UNDEF && !aspath_match(asp->aspath->data,
-	    asp->aspath->len, &req->as, 0))
+	if (req->as.type != AS_UNDEF &&
+	    !aspath_match(asp->aspath, &req->as, 0))
 		return;
 	switch (req->community.type) {
 	case COMMUNITY_TYPE_NONE:
@@ -3085,7 +3080,7 @@ rde_softreconfig_in(struct rib_entry *re, void *bula)
 		if (conf->rde_roa.dirty) {
 			/* ROA validation state update */
 			vstate = rde_roa_validity(&conf->rde_roa,
-			    &prefix, pt->prefixlen, asp->source_as);
+			    &prefix, pt->prefixlen, aspath_origin(asp->aspath));
 			if (vstate != p->validation_state) {
 				force_eval = 1;
 				p->validation_state = vstate;
@@ -3660,7 +3655,6 @@ network_add(struct network_config *nc, int flagstatic)
 		asp = path_get();
 		asp->aspath = aspath_get(NULL, 0);
 		asp->origin = ORIGIN_IGP;
-		asp->source_as = aspath_origin(asp->aspath);
 		asp->flags = F_ATTR_ORIGIN | F_ATTR_ASPATH |
 		    F_ATTR_LOCALPREF | F_PREFIX_ANNOUNCED;
 		/* the nexthop is unset unless a default set overrides it */
@@ -3674,7 +3668,7 @@ network_add(struct network_config *nc, int flagstatic)
 		    peerself);
 
 	vstate = rde_roa_validity(&conf->rde_roa, &nc->prefix,
-	    nc->prefixlen, asp->source_as);
+	    nc->prefixlen, aspath_origin(asp->aspath));
 	if (path_update(&ribs[RIB_ADJ_IN].rib, peerself, &state, &nc->prefix,
 	    nc->prefixlen, vstate) == 1)
 		peerself->prefix_cnt++;
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 0ee5964de04..862e0b477b5 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.203 2018/11/28 08:32:27 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.204 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -125,6 +125,7 @@ struct rde_peer {
 
 struct aspath {
 	LIST_ENTRY(aspath)	entry;
+	u_int32_t		source_as;	/* cached source_as */
 	int			refcnt;	/* reference count */
 	u_int16_t		len;	/* total length of aspath in octets */
 	u_int16_t		ascnt;	/* number of AS hops in data */
@@ -208,7 +209,6 @@ struct rde_aspath {
 	struct aspath			*aspath;
 	u_int64_t			 hash;
 	u_int32_t			 flags;		/* internally used */
-	u_int32_t			 source_as;	/* cached source_as */
 	u_int32_t			 med;		/* multi exit disc */
 	u_int32_t			 lpref;		/* local pref */
 	u_int32_t			 weight;	/* low prio lpref */
@@ -354,11 +354,11 @@ u_char		*aspath_deflate(u_char *, u_int16_t *, int *);
 void		 aspath_merge(struct rde_aspath *, struct attr *);
 u_char		*aspath_dump(struct aspath *);
 u_int16_t	 aspath_length(struct aspath *);
-u_int16_t	 aspath_count(const void *, u_int16_t);
 u_int32_t	 aspath_neighbor(struct aspath *);
 u_int32_t	 aspath_origin(struct aspath *);
 int		 aspath_loopfree(struct aspath *, u_int32_t);
 int		 aspath_compare(struct aspath *, struct aspath *);
+int		 aspath_match(struct aspath *, struct filter_as *, u_int32_t);
 u_char		*aspath_prepend(struct aspath *, u_int32_t, int, u_int16_t *);
 int		 aspath_lenmatch(struct aspath *, enum aslen_spec, u_int);
 
diff --git a/usr.sbin/bgpd/rde_attr.c b/usr.sbin/bgpd/rde_attr.c
index 897c3a370ca..455add62574 100644
--- a/usr.sbin/bgpd/rde_attr.c
+++ b/usr.sbin/bgpd/rde_attr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_attr.c,v 1.113 2018/11/28 08:32:27 claudio Exp $ */
+/*	$OpenBSD: rde_attr.c,v 1.114 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -441,6 +441,8 @@ attr_put(struct attr *a)
 
 /* aspath specific functions */
 
+static u_int16_t aspath_count(const void *, u_int16_t);
+static u_int32_t aspath_extract_origin(const void *, u_int16_t);
 static u_int16_t aspath_countlength(struct aspath *, u_int16_t, int);
 static void	 aspath_countcopy(struct aspath *, u_int16_t, u_int8_t *,
 		     u_int16_t, int);
@@ -530,6 +532,7 @@ aspath_get(void *data, u_int16_t len)
 		aspath->refcnt = 0;
 		aspath->len = len;
 		aspath->ascnt = aspath_count(data, len);
+		aspath->source_as = aspath_extract_origin(data, len);
 		memcpy(aspath->data, data, len);
 
 		/* link */
@@ -667,7 +670,22 @@ aspath_length(struct aspath *aspath)
 	return (aspath->len);
 }
 
-u_int16_t
+u_int32_t
+aspath_neighbor(struct aspath *aspath)
+{
+	/* Empty aspath is OK -- internal AS route. */
+	if (aspath->len == 0)
+		return (rde_local_as());
+	return (aspath_extract(aspath->data, 0));
+}
+
+u_int32_t
+aspath_origin(struct aspath *aspath)
+{
+	return aspath->source_as;
+}
+
+static u_int16_t
 aspath_count(const void *data, u_int16_t len)
 {
 	const u_int8_t	*seg;
@@ -692,6 +710,41 @@ aspath_count(const void *data, u_int16_t len)
 	return (cnt);
 }
 
+/*
+ * The origin AS number derived from a Route as follows:
+ * o  the rightmost AS in the final segment of the AS_PATH attribute
+ *    in the Route if that segment is of type AS_SEQUENCE, or
+ * o  the BGP speaker's own AS number if that segment is of type
+ *    AS_CONFED_SEQUENCE or AS_CONFED_SET or if the AS_PATH is empty,
+ * o  the distinguished value "NONE" if the final segment of the
+ *    AS_PATH attribute is of any other type.
+ */
+static u_int32_t
+aspath_extract_origin(const void *data, u_int16_t len)
+{
+	const u_int8_t	*seg;
+	u_int32_t	 as = AS_NONE;
+	u_int16_t	 seg_size;
+	u_int8_t	 seg_len;
+
+	/* AS_PATH is empty */
+	if (len == 0)
+		return (rde_local_as());
+
+	seg = data;
+	for (; len > 0; len -= seg_size, seg += seg_size) {
+		seg_len = seg[1];
+		seg_size = 2 + sizeof(u_int32_t) * seg_len;
+
+		if (len == seg_size && seg[0] == AS_SEQUENCE) {
+			as = aspath_extract(seg, seg_len - 1);
+		}
+		if (seg_size > len)
+			fatalx("%s: would overflow", __func__);
+	}
+	return (as);
+}
+
 static u_int16_t
 aspath_countlength(struct aspath *aspath, u_int16_t cnt, int headcnt)
 {
@@ -771,50 +824,6 @@ aspath_countcopy(struct aspath *aspath, u_int16_t cnt, u_int8_t *buf,
 	}
 }
 
-u_int32_t
-aspath_neighbor(struct aspath *aspath)
-{
-	/* Empty aspath is OK -- internal AS route. */
-	if (aspath->len == 0)
-		return (rde_local_as());
-	return (aspath_extract(aspath->data, 0));
-}
-
-/*
- * The origin AS number derived from a Route as follows:
- * o  the rightmost AS in the final segment of the AS_PATH attribute
- *    in the Route if that segment is of type AS_SEQUENCE, or
- * o  the BGP speaker's own AS number if that segment is of type
- *    AS_CONFED_SEQUENCE or AS_CONFED_SET or if the AS_PATH is empty,
- * o  the distinguished value "NONE" if the final segment of the
- *   AS_PATH attribute is of any other type.
- */
-u_int32_t
-aspath_origin(struct aspath *aspath)
-{
-	u_int8_t	*seg;
-	u_int32_t	 as = AS_NONE;
-	u_int16_t	 len, seg_size;
-	u_int8_t	 seg_len;
-
-	/* AS_PATH is empty */
-	if (aspath->len == 0)
-		return (rde_local_as());
-
-	seg = aspath->data;
-	for (len = aspath->len; len > 0; len -= seg_size, seg += seg_size) {
-		seg_len = seg[1];
-		seg_size = 2 + sizeof(u_int32_t) * seg_len;
-
-		if (len == seg_size && seg[0] == AS_SEQUENCE) {
-			as = aspath_extract(seg, seg_len - 1);
-		}
-		if (seg_size > len)
-			fatalx("%s: would overflow", __func__);
-	}
-	return (as);
-}
-
 int
 aspath_loopfree(struct aspath *aspath, u_int32_t myAS)
 {
@@ -873,6 +882,110 @@ aspath_lookup(const void *data, u_int16_t len)
 }
 
 
+static int
+as_compare(struct filter_as *f, u_int32_t as, u_int32_t neighas)
+{
+	u_int32_t match;
+
+	if (f->flags & AS_FLAG_AS_SET_NAME)	/* should not happen */
+		return (0);
+	if (f->flags & AS_FLAG_AS_SET)
+		return (as_set_match(f->aset, as));
+
+	if (f->flags & AS_FLAG_NEIGHBORAS)
+		match = neighas;
+	else
+		match = f->as_min;
+
+	switch (f->op) {
+	case OP_NONE:
+	case OP_EQ:
+		if (as == match)
+			return (1);
+		break;
+	case OP_NE:
+		if (as != match)
+			return (1);
+		break;
+	case OP_RANGE:
+		if (as >= f->as_min && as <= f->as_max)
+			return (1);
+		break;
+	case OP_XRANGE:
+		if (as < f->as_min || as > f->as_max)
+			return (1);
+		break;
+	}
+	return (0);
+}
+
+/* we need to be able to search more than one as */
+int
+aspath_match(struct aspath *aspath, struct filter_as *f, u_int32_t neighas)
+{
+	const u_int8_t	*seg;
+	int		 final;
+	u_int16_t	 len, seg_size;
+	u_int8_t	 i, seg_len;
+	u_int32_t	 as = AS_NONE;
+
+	if (f->type == AS_EMPTY) {
+		if (aspath_length(aspath) == 0)
+			return (1);
+		else
+			return (0);
+	}
+
+	/* just check the leftmost AS */
+	if (f->type == AS_PEER) {
+		as = aspath_neighbor(aspath);
+		if (as_compare(f, as, neighas))
+			return (1);
+		else
+			return (0);
+	}
+
+	seg = aspath->data;
+	len = aspath->len;
+	for (; len >= 6; len -= seg_size, seg += seg_size) {
+		seg_len = seg[1];
+		seg_size = 2 + sizeof(u_int32_t) * seg_len;
+
+		final = (len == seg_size);
+
+		if (f->type == AS_SOURCE) {
+			/*
+			 * Just extract the rightmost AS
+			 * but if that segment is an AS_SET then the rightmost
+			 * AS of a previous AS_SEQUENCE segment should be used.
+			 * Because of that just look at AS_SEQUENCE segments.
+			 */
+			if (seg[0] == AS_SEQUENCE)
+				as = aspath_extract(seg, seg_len - 1);
+			/* not yet in the final segment */
+			if (!final)
+				continue;
+			if (as_compare(f, as, neighas))
+				return (1);
+			else
+				return (0);
+		}
+		/* AS_TRANSIT or AS_ALL */
+		for (i = 0; i < seg_len; i++) {
+			/*
+			 * the source (rightmost) AS is excluded from
+			 * AS_TRANSIT matches.
+			 */
+			if (final && i == seg_len - 1 && f->type == AS_TRANSIT)
+				return (0);
+			as = aspath_extract(seg, i);
+			if (as_compare(f, as, neighas))
+				return (1);
+		}
+	}
+	return (0);
+}
+
 /*
  * Returns a new prepended aspath. Old needs to be freed by caller.
  */
diff --git a/usr.sbin/bgpd/rde_filter.c b/usr.sbin/bgpd/rde_filter.c
index d731bed35cc..187ea3c546b 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.114 2018/11/28 08:32:27 claudio Exp $ */
+/*	$OpenBSD: rde_filter.c,v 1.115 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -219,8 +219,8 @@ rde_filter_match(struct filter_rule *f, struct rde_peer *peer,
 	}
 
 	if (asp != NULL && f->match.as.type != AS_UNDEF) {
-		if (aspath_match(asp->aspath->data, asp->aspath->len,
-		    &f->match.as, peer->conf.remote_as) == 0)
+		if (aspath_match(asp->aspath, &f->match.as,
+		    peer->conf.remote_as) == 0)
 			return (0);
 	}
 
@@ -289,7 +289,7 @@ rde_filter_match(struct filter_rule *f, struct rde_peer *peer,
 		pt_getaddr(p->re->prefix, prefix);
 		plen = p->re->prefix->prefixlen;
 		if (trie_roa_check(&f->match.originset.ps->th, prefix, plen,
-		    asp->source_as) != ROA_VALID)
+		    aspath_origin(asp->aspath)) != ROA_VALID)
 			return (0);
 	}
 
diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c
index 41d993c0994..63190a3e639 100644
--- a/usr.sbin/bgpd/rde_rib.c
+++ b/usr.sbin/bgpd/rde_rib.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_rib.c,v 1.186 2018/11/14 12:14:41 claudio Exp $ */
+/*	$OpenBSD: rde_rib.c,v 1.187 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -657,10 +657,6 @@ path_compare(struct rde_aspath *a, struct rde_aspath *b)
 		return (1);
 	if (a->pftableid < b->pftableid)
 		return (-1);
-	if (a->source_as > b->source_as)
-		return (1);
-	if (a->source_as < b->source_as)
-		return (-1);
 
 	r = aspath_compare(a->aspath, b->aspath);
 	if (r > 0)
@@ -761,7 +757,6 @@ path_copy(struct rde_aspath *dst, const struct rde_aspath *src)
 	dst->lpref = src->lpref;
 	dst->weight = src->weight;
 	dst->origin = src->origin;
-	dst->source_as = src->source_as;
 	dst->rtlabelid = rtlabel_ref(src->rtlabelid);
 	dst->pftableid = pftable_ref(src->pftableid);
 
diff --git a/usr.sbin/bgpd/util.c b/usr.sbin/bgpd/util.c
index 503c13031ba..4e70d2a9aac 100644
--- a/usr.sbin/bgpd/util.c
+++ b/usr.sbin/bgpd/util.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: util.c,v 1.40 2018/09/26 14:38:19 claudio Exp $ */
+/*	$OpenBSD: util.c,v 1.41 2018/12/11 09:02:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2006 Claudio Jeker <claudio@openbsd.org>
@@ -312,110 +312,6 @@ aspath_strlen(void *data, u_int16_t len)
 	return (total_size);
 }
 
-static int
-as_compare(struct filter_as *f, u_int32_t as, u_int32_t neighas)
-{
-	u_int32_t match;
-
-	if (f->flags & AS_FLAG_AS_SET_NAME)	/* should not happen */
-		return (0);
-	if (f->flags & AS_FLAG_AS_SET)
-		return (as_set_match(f->aset, as));
-
-	if (f->flags & AS_FLAG_NEIGHBORAS)
-		match = neighas;
-	else
-		match = f->as_min;
-
-	switch (f->op) {
-	case OP_NONE:
-	case OP_EQ:
-		if (as == match)
-			return (1);
-		break;
-	case OP_NE:
-		if (as != match)
-			return (1);
-		break;
-	case OP_RANGE:
-		if (as >= f->as_min && as <= f->as_max)
-			return (1);
-		break;
-	case OP_XRANGE:
-		if (as < f->as_min || as > f->as_max)
-			return (1);
-		break;
-	}
-	return (0);
-}
-
-/* we need to be able to search more than one as */
-int
-aspath_match(void *data, u_int16_t len, struct filter_as *f, u_int32_t neighas)
-{
-	u_int8_t	*seg;
-	int		 final;
-	u_int16_t	 seg_size;
-	u_int8_t	 i, seg_len;
-	u_int32_t	 as = 0;
-
-	if (f->type == AS_EMPTY) {
-		if (len == 0)
-			return (1);
-		else
-			return (0);
-	}
-
-	seg = data;
-
-	/* just check the leftmost AS */
-	if (f->type == AS_PEER && len >= 6) {
-		as = aspath_extract(seg, 0);
-		if (as_compare(f, as, neighas))
-			return (1);
-		else
-			return (0);
-	}
-
-	for (; len >= 6; len -= seg_size, seg += seg_size) {
-		seg_len = seg[1];
-		seg_size = 2 + sizeof(u_int32_t) * seg_len;
-
-		final = (len == seg_size);
-
-		if (f->type == AS_SOURCE) {
-			/*
-			 * Just extract the rightmost AS
-			 * but if that segment is an AS_SET then the rightmost
-			 * AS of a previous AS_SEQUENCE segment should be used.
-			 * Because of that just look at AS_SEQUENCE segments.
-			 */
-			if (seg[0] == AS_SEQUENCE)
-				as = aspath_extract(seg, seg_len - 1);
-			/* not yet in the final segment */
-			if (!final)
-				continue;
-			if (as_compare(f, as, neighas))
-				return (1);
-			else
-				return (0);
-		}
-		/* AS_TRANSIT or AS_ALL */
-		for (i = 0; i < seg_len; i++) {
-			/*
-			 * the source (rightmost) AS is excluded from
-			 * AS_TRANSIT matches.
-			 */
-			if (final && i == seg_len - 1 && f->type == AS_TRANSIT)
-				return (0);
-			as = aspath_extract(seg, i);
-			if (as_compare(f, as, neighas))
-				return (1);
-		}
-	}
-	return (0);
-}
-
 /*
  * Extract the asnum out of the as segment at the specified position.
  * Direct access is not possible because of non-aligned reads.