Remove tail queues which link peer, aspath and prefix together. These

lists are no longer needed and make it possible to share rde_aspath between
peers & prefixes. Instead of the lists the rde_aspath is now reference counted.
With this struct prefix is now the central place where everything is connected
to making the RIB a bit easier to handle.
With input and OK denis@

4 files changed, 64 insertions, 64 deletions

diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h
index 702d00aa1bf..06cc025f16e 100644
--- a/usr.sbin/bgpd/bgpd.h
+++ b/usr.sbin/bgpd/bgpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.h,v 1.350 2018/10/26 16:53:55 claudio Exp $ */
+/*	$OpenBSD: bgpd.h,v 1.351 2018/10/31 14:50:07 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -1066,6 +1066,7 @@ extern struct rib_names ribnames;
 
 struct rde_memstats {
 	int64_t		path_cnt;
+	int64_t		path_refs;
 	int64_t		prefix_cnt;
 	int64_t		rib_cnt;
 	int64_t		pt_cnt[AID_MAX];
diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c
index 15724e65988..91f8e951b09 100644
--- a/usr.sbin/bgpd/rde.c
+++ b/usr.sbin/bgpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.443 2018/10/29 09:28:31 claudio Exp $ */
+/*	$OpenBSD: rde.c,v 1.444 2018/10/31 14:50:07 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -3283,7 +3283,6 @@ peer_add(u_int32_t id, struct peer_config *p_conf)
 	if (peer == NULL)
 		fatal("peer_add");
 
-	TAILQ_INIT(&peer->path_h);
 	memcpy(&peer->conf, p_conf, sizeof(struct peer_config));
 	peer->remote_bgpid = 0;
 	peer->loc_rib_id = rib_find(peer->conf.rib);
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 4cd13e1fcee..8c551e27f50 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.200 2018/10/29 09:28:31 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.201 2018/10/31 14:50:07 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -76,9 +76,7 @@ struct rib_desc {
 LIST_HEAD(rde_peer_head, rde_peer);
 LIST_HEAD(aspath_list, aspath);
 LIST_HEAD(attr_list, attr);
-TAILQ_HEAD(prefix_queue, prefix);
 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);
@@ -89,7 +87,6 @@ TAILQ_HEAD(uplist_attr, update_attr);
 struct rde_peer {
 	LIST_ENTRY(rde_peer)		 hash_l; /* hash list over all peers */
 	LIST_ENTRY(rde_peer)		 peer_l; /* list of all peers */
-	struct aspath_queue		 path_h; /* list of all as paths */
 	struct peer_config		 conf;
 	struct bgpd_addr		 remote_addr;
 	struct bgpd_addr		 local_v4_addr;
@@ -209,10 +206,7 @@ struct mpattr {
 
 struct rde_aspath {
 	LIST_ENTRY(rde_aspath)		 path_l;
-	TAILQ_ENTRY(rde_aspath)		 peer_l;
-	struct prefix_queue		 prefixes;
 	struct attr			**others;
-	struct rde_peer			*peer;
 	struct aspath			*aspath;
 	u_int64_t			 hash;
 	u_int32_t			 flags;		/* internally used */
@@ -220,6 +214,7 @@ struct rde_aspath {
 	u_int32_t			 med;		/* multi exit disc */
 	u_int32_t			 lpref;		/* local pref */
 	u_int32_t			 weight;	/* low prio lpref */
+	int				 refcnt;
 	u_int16_t			 rtlabelid;	/* route label id */
 	u_int16_t			 pftableid;	/* pf table id */
 	u_int8_t			 origin;
@@ -291,7 +286,6 @@ struct pt_entry_vpn4 {
 
 struct prefix {
 	LIST_ENTRY(prefix)		 rib_l, nexthop_l;
-	TAILQ_ENTRY(prefix)		 path_l;
 	struct rib_entry		*re;
 	struct rde_aspath		*aspath;
 	struct rde_peer			*peer;
@@ -479,7 +473,6 @@ int		 path_update(struct rib *, struct rde_peer *,
 		     struct filterstate *, struct bgpd_addr *, int, u_int8_t);
 int		 path_compare(struct rde_aspath *, struct rde_aspath *);
 u_int32_t	 path_remove_stale(struct rde_aspath *, u_int8_t, time_t);
-void		 path_destroy(struct rde_aspath *);
 int		 path_empty(struct rde_aspath *);
 struct rde_aspath *path_copy(struct rde_aspath *, const struct rde_aspath *);
 struct rde_aspath *path_prep(struct rde_aspath *);
diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c
index b843d2c5b99..959e02e2fe6 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.183 2018/10/31 14:45:36 claudio Exp $ */
+/*	$OpenBSD: rde_rib.c,v 1.184 2018/10/31 14:50:07 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -464,9 +464,10 @@ rib_dump_terminate(u_int16_t id, void *arg,
 
 /* path specific functions */
 
-static struct rde_aspath *path_lookup(struct rde_aspath *, struct rde_peer *);
+static struct rde_aspath *path_lookup(struct rde_aspath *);
 static u_int64_t path_hash(struct rde_aspath *);
-static void path_link(struct rde_aspath *, struct rde_peer *);
+static void path_link(struct rde_aspath *);
+static void path_unlink(struct rde_aspath *);
 
 struct path_table {
 	struct aspath_head	*path_hashtbl;
@@ -475,7 +476,27 @@ struct path_table {
 
 SIPHASH_KEY pathtablekey;
 
-#define PATH_HASH(x)	&pathtable.path_hashtbl[x & pathtable.path_hashmask]
+#define	PATH_HASH(x)	&pathtable.path_hashtbl[x & pathtable.path_hashmask]
+
+#define	path_empty(asp)	((asp)->refcnt <= 0)
+
+static inline void
+path_ref(struct rde_aspath *asp)
+{
+	if ((asp->flags & F_ATTR_LINKED) == 0)
+		fatalx("%s: unlinked object", __func__);
+	asp->refcnt++;
+	rdemem.path_refs++;
+}
+
+static inline void
+path_unref(struct rde_aspath *asp)
+{
+	if ((asp->flags & F_ATTR_LINKED) == 0)
+		fatalx("%s: unlinked object", __func__);
+	asp->refcnt--;
+	rdemem.path_refs--;
+}
 
 void
 path_init(u_int32_t hashsize)
@@ -563,10 +584,10 @@ path_update(struct rib *rib, struct rde_peer *peer, struct filterstate *state,
 	 * In both cases lookup the new aspath to make sure it is not
 	 * already in the RIB.
 	 */
-	if ((asp = path_lookup(nasp, peer)) == NULL) {
+	if ((asp = path_lookup(nasp)) == NULL) {
 		/* Path not available, create and link a new one. */
 		asp = path_copy(path_get(), nasp);
-		path_link(asp, peer);
+		path_link(asp);
 	}
 
 	/* If the prefix was found move it else add it to the aspath. */
@@ -654,7 +675,7 @@ path_hash(struct rde_aspath *asp)
 }
 
 static struct rde_aspath *
-path_lookup(struct rde_aspath *aspath, struct rde_peer *peer)
+path_lookup(struct rde_aspath *aspath)
 {
 	struct aspath_head	*head;
 	struct rde_aspath	*asp;
@@ -664,57 +685,43 @@ path_lookup(struct rde_aspath *aspath, struct rde_peer *peer)
 	head = PATH_HASH(hash);
 
 	LIST_FOREACH(asp, head, path_l) {
-		if (asp->hash == hash && peer == asp->peer &&
-		    path_compare(aspath, asp) == 0)
+		if (asp->hash == hash && path_compare(aspath, asp) == 0)
 			return (asp);
 	}
 	return (NULL);
 }
 
 /*
- * This function can only called when all prefix have been removed first.
- * Normally this happens directly out of the prefix removal functions.
+ * Link this aspath into the global hash table.
+ * The asp had to be alloced with path_get.
  */
-void
-path_destroy(struct rde_aspath *asp)
+static void
+path_link(struct rde_aspath *asp)
 {
-	/* path_destroy can only unlink and free empty rde_aspath */
-	if (!TAILQ_EMPTY(&asp->prefixes))
-		log_warnx("path_destroy: still has prefixes, leaking");
-
-	LIST_REMOVE(asp, path_l);
-	TAILQ_REMOVE(&asp->peer->path_h, asp, peer_l);
-	asp->peer = NULL;
-	asp->flags &= ~F_ATTR_LINKED;
+	struct aspath_head	*head;
 
-	path_put(asp);
-}
+	asp->hash = path_hash(asp);
+	head = PATH_HASH(asp->hash);
 
-int
-path_empty(struct rde_aspath *asp)
-{
-	return TAILQ_EMPTY(&asp->prefixes);
+	LIST_INSERT_HEAD(head, asp, path_l);
+	asp->flags |= F_ATTR_LINKED;
 }
 
 /*
- * the path object is linked into multiple lists for fast access.
- * These are peer_l, path_l and nexthop_l.
- * peer_l: list of all aspaths that belong to that peer
- * path_l: hash list to find paths quickly
+ * This function can only be called when all prefix have been removed first.
+ * Normally this happens directly out of the prefix removal functions.
  */
 static void
-path_link(struct rde_aspath *asp, struct rde_peer *peer)
+path_unlink(struct rde_aspath *asp)
 {
-	struct aspath_head	*head;
+	/* make sure no reference is hold for this rde_aspath */
+	if (!path_empty(asp))
+		fatalx("%s: still has prefixes", __func__);
 
-	asp->peer = peer;
-
-	asp->hash = path_hash(asp);
-	head = PATH_HASH(asp->hash);
+	LIST_REMOVE(asp, path_l);
+	asp->flags &= ~F_ATTR_LINKED;
 
-	LIST_INSERT_HEAD(head, asp, path_l);
-	TAILQ_INSERT_HEAD(&peer->path_h, asp, peer_l);
-	asp->flags |= F_ATTR_LINKED;
+	path_put(asp);
 }
 
 /*
@@ -739,6 +746,8 @@ path_copy(struct rde_aspath *dst, const struct rde_aspath *src)
 	dst->pftableid = pftable_ref(src->pftableid);
 
 	dst->flags = src->flags & ~F_ATTR_LINKED;
+	dst->refcnt = 0;	/* not linked so no refcnt */
+
 	attr_copy(dst, src);
 
 	return (dst);
@@ -749,7 +758,6 @@ struct rde_aspath *
 path_prep(struct rde_aspath *asp)
 {
 	memset(asp, 0, sizeof(*asp));
-	TAILQ_INIT(&asp->prefixes);
 	asp->origin = ORIGIN_INCOMPLETE;
 	asp->lpref = DEFAULT_LPREF;
 
@@ -770,11 +778,12 @@ path_get(void)
 	return (path_prep(asp));
 }
 
+/* clean up an asp after use (frees all references to sub-objects) */
 void
 path_clean(struct rde_aspath *asp)
 {
 	if (asp->flags & F_ATTR_LINKED)
-		fatalx("path_clean: linked object");
+		fatalx("%s: linked object", __func__);
 
 	rtlabel_unref(asp->rtlabelid);
 	pftable_unref(asp->pftableid);
@@ -834,7 +843,7 @@ prefix_add(struct bgpd_addr *prefix, int prefixlen, struct rib *rib,
 	if (re == NULL)
 		re = rib_add(rib, prefix, prefixlen);
 
-	p = prefix_bypeer(re, asp->peer);
+	p = prefix_bypeer(re, peer);
 	if (p == NULL) {
 		p = prefix_alloc();
 		prefix_link(p, re, peer, asp, state, vstate);
@@ -875,8 +884,8 @@ prefix_move(struct prefix *p, struct rde_peer *peer,
 	np->nhflags = state->nhflags;
 	np->validation_state = vstate;
 
-	/* add to new as path */
-	TAILQ_INSERT_HEAD(&asp->prefixes, np, path_l);
+	/* add reference to new as path */
+	path_ref(asp);
 
 	/*
 	 * no need to update the peer prefix count because we are only moving
@@ -896,7 +905,7 @@ prefix_move(struct prefix *p, struct rde_peer *peer,
 
 	/* remove old prefix node */
 	oasp = prefix_aspath(p);
-	TAILQ_REMOVE(&oasp->prefixes, p, path_l);
+	path_unref(oasp);
 	/* as before peer count needs no update because of move */
 
 	/* destroy all references to other objects and free the old prefix */
@@ -910,7 +919,7 @@ prefix_move(struct prefix *p, struct rde_peer *peer,
 
 	/* destroy old path if empty */
 	if (path_empty(oasp))
-		path_destroy(oasp);
+		path_unlink(oasp);
 
 	return (0);
 }
@@ -1091,7 +1100,7 @@ prefix_destroy(struct prefix *p)
 	prefix_free(p);
 
 	if (path_empty(asp))
-		path_destroy(asp);
+		path_unlink(asp);
 }
 
 /*
@@ -1101,7 +1110,7 @@ static void
 prefix_link(struct prefix *pref, struct rib_entry *re, struct rde_peer *peer,
     struct rde_aspath *asp, struct filterstate *state, u_int8_t vstate)
 {
-	TAILQ_INSERT_HEAD(&asp->prefixes, pref, path_l);
+	path_ref(asp);
 
 	pref->aspath = asp;
 	pref->peer = peer;
@@ -1123,15 +1132,13 @@ static void
 prefix_unlink(struct prefix *pref)
 {
 	struct rib_entry	*re = pref->re;
-	struct prefix_queue	*pq;
 
 	/* make route decision */
 	LIST_REMOVE(pref, rib_l);
 	prefix_evaluate(NULL, re);
 
-	pq = &prefix_aspath(pref)->prefixes;
+	path_unref(prefix_aspath(pref));
 
-	TAILQ_REMOVE(pq, pref, path_l);
 	if (rib_empty(re))
 		rib_remove(re);