fixes #1289 zerotier should have it's own copy of the id hashing code

fixes #1288 id allocation can overallocate
fixes #1126 consider removing lock from idhash

This substantially refactors the id hash code, giving a cleaner API,
and eliminating a extra locking as well as some wasteful allocations.

The ZeroTier code has it's own copy, that is 64-bit friendly, as the
rest of the consumers need only a simpler 32-bit API.

4 files changed, 381 insertions, 34 deletions

diff --git a/src/transport/zerotier/CMakeLists.txt b/src/transport/zerotier/CMakeLists.txt
index 5eca54c3..bc8673c5 100644
--- a/src/transport/zerotier/CMakeLists.txt
+++ b/src/transport/zerotier/CMakeLists.txt
@@ -1,5 +1,5 @@
 #
-# Copyright 2018 Staysail Systems, Inc. <info@staysail.tech>
+# Copyright 2020 Staysail Systems, Inc. <info@staysail.tech>
 # Copyright 2018 Capitar IT Group BV <info@capitar.com>
 #
 # This software is supplied under the terms of the MIT License, a
@@ -26,7 +26,7 @@ if (NNG_TRANSPORT_ZEROTIER)
 
     message(WARNING "
         ************************************************************
-        Linking against zerotiercore changes license terms (GPLv3).
+        Linking against zerotiercore changes license terms.
         Consult a lawyer and the license files for details.
         ************************************************************")
 
@@ -35,7 +35,9 @@ if (NNG_TRANSPORT_ZEROTIER)
     set(_LIBS zerotiercore::zerotiercore)
     set(_DEFS -DNNG_TRANSPORT_ZEROTIER)
 
-    set(_SRCS transport/zerotier/zerotier.c ${PROJECT_SOURCE_DIR}/include/nng/transport/zerotier/zerotier.h)
+    set(_SRCS transport/zerotier/zerotier.c
+            transport/zerotier/zthash.c
+            ${PROJECT_SOURCE_DIR}/include/nng/transport/zerotier/zerotier.h)
 
     set(NNG_DEFS ${NNG_DEFS} ${_DEFS} PARENT_SCOPE)
     set(NNG_LIBS ${NNG_LIBS} ${_LIBS} PARENT_SCOPE)
diff --git a/src/transport/zerotier/zerotier.c b/src/transport/zerotier/zerotier.c
index 32e3ef7d..2667d027 100644
--- a/src/transport/zerotier/zerotier.c
+++ b/src/transport/zerotier/zerotier.c
@@ -14,6 +14,7 @@
 #include <string.h>
 
 #include "core/nng_impl.h"
+#include "zthash.h"
 
 #include "nng/transport/zerotier/zerotier.h"
 
@@ -153,10 +154,10 @@ struct zt_node {
 	nni_plat_udp *  zn_udp6;
 	nni_list        zn_eplist;
 	nni_list        zn_plist;
-	nni_idhash *    zn_ports;
-	nni_idhash *    zn_eps;
-	nni_idhash *    zn_lpipes;
-	nni_idhash *    zn_rpipes;
+	zt_hash *       zn_ports;
+	zt_hash *       zn_eps;
+	zt_hash *       zn_lpipes;
+	zt_hash *       zn_rpipes;
 	nni_aio *       zn_rcv4_aio;
 	uint8_t *       zn_rcv4_buf;
 	nng_sockaddr    zn_rcv4_addr;
@@ -657,8 +658,7 @@ zt_ep_recv_conn_ack(zt_ep *ep, uint64_t raddr, const uint8_t *data, size_t len)
 	// Do we already have a matching pipe?  If so, we can discard
 	// the operation.  This should not happen, since we normally,
 	// deregister the endpoint when we create the pipe.
-	if ((nni_idhash_find(ztn->zn_lpipes, ep->ze_laddr, (void **) &p)) ==
-	    0) {
+	if ((zt_hash_find(ztn->zn_lpipes, ep->ze_laddr, (void **) &p)) == 0) {
 		return;
 	}
 
@@ -672,7 +672,7 @@ zt_ep_recv_conn_ack(zt_ep *ep, uint64_t raddr, const uint8_t *data, size_t len)
 	// Reset the address of the endpoint, so that the next call to
 	// ep_connect will bind a new one -- we are using this one for the
 	// pipe.
-	nni_idhash_remove(ztn->zn_eps, ep->ze_laddr);
+	zt_hash_remove(ztn->zn_eps, ep->ze_laddr);
 	ep->ze_laddr = 0;
 
 	nni_aio_set_output(aio, 0, p);
@@ -699,7 +699,7 @@ zt_ep_recv_conn_req(zt_ep *ep, uint64_t raddr, const uint8_t *data, size_t len)
 
 	// If we already have created a pipe for this connection
 	// then just reply the conn ack.
-	if ((nni_idhash_find(ztn->zn_rpipes, raddr, (void **) &p)) == 0) {
+	if ((zt_hash_find(ztn->zn_rpipes, raddr, (void **) &p)) == 0) {
 		zt_pipe_send_conn_ack(p);
 		return;
 	}
@@ -1083,21 +1083,21 @@ zt_virtual_recv(ZT_Node *node, void *userptr, void *thr, uint64_t nwid,
 	// vs. client pipes separately.
 
 	// If its a local address match on a client pipe, process it.
-	if ((nni_idhash_find(ztn->zn_lpipes, laddr, (void *) &p) == 0) &&
+	if ((zt_hash_find(ztn->zn_lpipes, laddr, (void *) &p) == 0) &&
 	    (p->zp_nwid == nwid) && (p->zp_raddr == raddr)) {
 		zt_pipe_virtual_recv(p, op, data, len);
 		return;
 	}
 
 	// If its a remote address match on a server pipe, process it.
-	if ((nni_idhash_find(ztn->zn_rpipes, raddr, (void *) &p) == 0) &&
+	if ((zt_hash_find(ztn->zn_rpipes, raddr, (void *) &p) == 0) &&
 	    (p->zp_nwid == nwid) && (p->zp_laddr == laddr)) {
 		zt_pipe_virtual_recv(p, op, data, len);
 		return;
 	}
 
 	// No pipe, so look for an endpoint.
-	if ((nni_idhash_find(ztn->zn_eps, laddr, (void **) &ep) == 0) &&
+	if ((zt_hash_find(ztn->zn_eps, laddr, (void **) &ep) == 0) &&
 	    (ep->ze_nwid == nwid)) {
 		// direct this to an endpoint.
 		zt_ep_virtual_recv(ep, op, raddr, data, len);
@@ -1408,9 +1408,9 @@ zt_node_destroy(zt_node *ztn)
 	}
 	nni_aio_free(ztn->zn_rcv4_aio);
 	nni_aio_free(ztn->zn_rcv6_aio);
-	nni_idhash_fini(ztn->zn_eps);
-	nni_idhash_fini(ztn->zn_lpipes);
-	nni_idhash_fini(ztn->zn_rpipes);
+	zt_hash_fini(ztn->zn_eps);
+	zt_hash_fini(ztn->zn_lpipes);
+	zt_hash_fini(ztn->zn_rpipes);
 	nni_cv_fini(&ztn->zn_bgcv);
 	NNI_FREE_STRUCT(ztn);
 }
@@ -1448,10 +1448,10 @@ zt_node_create(zt_node **ztnp, const char *path)
 		zt_node_destroy(ztn);
 		return (NNG_ENOMEM);
 	}
-	if (((rv = nni_idhash_init(&ztn->zn_ports)) != 0) ||
-	    ((rv = nni_idhash_init(&ztn->zn_eps)) != 0) ||
-	    ((rv = nni_idhash_init(&ztn->zn_lpipes)) != 0) ||
-	    ((rv = nni_idhash_init(&ztn->zn_rpipes)) != 0) ||
+	if (((rv = zt_hash_init(&ztn->zn_ports)) != 0) ||
+	    ((rv = zt_hash_init(&ztn->zn_eps)) != 0) ||
+	    ((rv = zt_hash_init(&ztn->zn_lpipes)) != 0) ||
+	    ((rv = zt_hash_init(&ztn->zn_rpipes)) != 0) ||
 	    ((rv = nni_thr_init(&ztn->zn_bgthr, zt_bgthr, ztn)) != 0) ||
 	    ((rv = nni_plat_udp_open(&ztn->zn_udp4, &sa4)) != 0) ||
 	    ((rv = nni_plat_udp_open(&ztn->zn_udp6, &sa6)) != 0)) {
@@ -1480,7 +1480,7 @@ zt_node_create(zt_node **ztnp, const char *path)
 	// higher than the max port, and starting with an
 	// initial random value.  Note that this should give us
 	// about 8 million possible ephemeral ports.
-	nni_idhash_set_limits(ztn->zn_ports, zt_ephemeral, zt_max_port,
+	zt_hash_limits(ztn->zn_ports, zt_ephemeral, zt_max_port,
 	    (nni_random() % (zt_max_port - zt_ephemeral)) + zt_ephemeral);
 
 	nni_strlcpy(ztn->zn_path, path, sizeof(ztn->zn_path));
@@ -1745,9 +1745,9 @@ zt_pipe_fini(void *arg)
 
 	// This tosses the connection details and all state.
 	nni_mtx_lock(&zt_lk);
-	nni_idhash_remove(ztn->zn_ports, p->zp_laddr & zt_port_mask);
-	nni_idhash_remove(ztn->zn_lpipes, p->zp_laddr);
-	nni_idhash_remove(ztn->zn_rpipes, p->zp_raddr);
+	zt_hash_remove(ztn->zn_ports, p->zp_laddr & zt_port_mask);
+	zt_hash_remove(ztn->zn_lpipes, p->zp_laddr);
+	zt_hash_remove(ztn->zn_rpipes, p->zp_raddr);
 	nni_mtx_unlock(&zt_lk);
 
 	for (int i = 0; i < zt_recvq; i++) {
@@ -1798,10 +1798,10 @@ zt_pipe_alloc(
 
 	if (listener) {
 		// listener
-		rv = nni_idhash_insert(ztn->zn_rpipes, raddr, p);
+		rv = zt_hash_insert(ztn->zn_rpipes, raddr, p);
 	} else {
 		// dialer
-		rv = nni_idhash_insert(ztn->zn_lpipes, laddr, p);
+		rv = zt_hash_insert(ztn->zn_lpipes, laddr, p);
 	}
 	if ((rv != 0) ||
 	    ((rv = nni_aio_alloc(&p->zp_ping_aio, zt_pipe_ping_cb, p)) != 0)) {
@@ -2342,8 +2342,8 @@ zt_ep_close(void *arg)
 	// If we're on the ztn node list, pull us off.
 	if (ztn != NULL) {
 		nni_list_node_remove(&ep->ze_link);
-		nni_idhash_remove(ztn->zn_ports, ep->ze_laddr & zt_port_mask);
-		nni_idhash_remove(ztn->zn_eps, ep->ze_laddr);
+		zt_hash_remove(ztn->zn_ports, ep->ze_laddr & zt_port_mask);
+		zt_hash_remove(ztn->zn_eps, ep->ze_laddr);
 	}
 
 	nni_mtx_unlock(&zt_lk);
@@ -2374,7 +2374,7 @@ zt_ep_bind_locked(zt_ep *ep)
 
 	if ((ep->ze_laddr & zt_port_mask) == 0) {
 		// ask for an ephemeral port
-		if ((rv = nni_idhash_alloc(ztn->zn_ports, &port, ep)) != 0) {
+		if ((rv = zt_hash_alloc(ztn->zn_ports, &port, ep)) != 0) {
 			return (rv);
 		}
 		NNI_ASSERT(port & zt_ephemeral);
@@ -2383,10 +2383,10 @@ zt_ep_bind_locked(zt_ep *ep)
 		// make sure port requested is free.
 		port = ep->ze_laddr & zt_port_mask;
 
-		if (nni_idhash_find(ztn->zn_ports, port, &conflict) == 0) {
+		if (zt_hash_find(ztn->zn_ports, port, &conflict) == 0) {
 			return (NNG_EADDRINUSE);
 		}
-		if ((rv = nni_idhash_insert(ztn->zn_ports, port, ep)) != 0) {
+		if ((rv = zt_hash_insert(ztn->zn_ports, port, ep)) != 0) {
 			return (rv);
 		}
 	}
@@ -2398,8 +2398,8 @@ zt_ep_bind_locked(zt_ep *ep)
 	ep->ze_laddr |= port;
 	ep->ze_running = true;
 
-	if ((rv = nni_idhash_insert(ztn->zn_eps, ep->ze_laddr, ep)) != 0) {
-		nni_idhash_remove(ztn->zn_ports, port);
+	if ((rv = zt_hash_insert(ztn->zn_eps, ep->ze_laddr, ep)) != 0) {
+		zt_hash_remove(ztn->zn_ports, port);
 		return (rv);
 	}
 
diff --git a/src/transport/zerotier/zthash.c b/src/transport/zerotier/zthash.c
new file mode 100644
index 00000000..ca46b373
--- /dev/null
+++ b/src/transport/zerotier/zthash.c
@@ -0,0 +1,302 @@
+//
+// Copyright 2020 Staysail Systems, Inc. <info@staysail.tech>
+// Copyright 2018 Capitar IT Group BV <info@capitar.com>
+//
+// This software is supplied under the terms of the MIT License, a
+// copy of which should be located in the distribution where this
+// file was obtained (LICENSE.txt).  A copy of the license may also be
+// found online at https://opensource.org/licenses/MIT.
+//
+
+#include "core/nng_impl.h"
+#include "zthash.h"
+
+struct zt_hash_entry {
+	uint64_t key;
+	void *   val;
+	uint32_t skips;
+};
+
+int
+zt_hash_init(zt_hash **hp)
+{
+	zt_hash *h;
+
+	if ((h = NNI_ALLOC_STRUCT(h)) == NULL) {
+		return (NNG_ENOMEM);
+	}
+	h->ih_entries = NULL;
+	h->ih_count   = 0;
+	h->ih_load    = 0;
+	h->ih_cap     = 0;
+	h->ih_maxload = 0;
+	h->ih_minload = 0; // never shrink below this
+	h->ih_minval  = 0;
+	h->ih_maxval  = 0xffffffff;
+	h->ih_dynval  = 0;
+
+	*hp = h;
+	return (0);
+}
+
+void
+zt_hash_fini(zt_hash *h)
+{
+	if (h != NULL) {
+		if (h->ih_entries != NULL) {
+			NNI_FREE_STRUCTS(h->ih_entries, h->ih_cap);
+			h->ih_entries = NULL;
+			h->ih_cap = h->ih_count = 0;
+			h->ih_load = h->ih_minload = h->ih_maxload = 0;
+		}
+
+		NNI_FREE_STRUCT(h);
+	}
+}
+
+void
+zt_hash_limits(zt_hash *h, uint64_t minval, uint64_t maxval, uint64_t start)
+{
+	if (start < minval) {
+		start = minval;
+	}
+	if (start > maxval) {
+		start = maxval;
+	}
+
+	h->ih_minval = minval;
+	h->ih_maxval = maxval;
+	h->ih_dynval = start;
+	NNI_ASSERT(minval < maxval);
+	NNI_ASSERT(start >= minval);
+	NNI_ASSERT(start <= maxval);
+}
+
+// Inspired by Python dict implementation.  This probe will visit every
+// cell.  We always hash consecutively assigned IDs.
+#define ZT_HASH_NEXT(h, j) ((((j) *5) + 1) & (h->ih_cap - 1))
+#define ZT_HASH_INDEX(h, j) ((j) & (h->ih_cap - 1))
+
+static size_t
+zt_hash_find_index(zt_hash *h, uint64_t id)
+{
+	size_t index;
+	size_t start;
+	if (h->ih_count == 0) {
+		return ((size_t) -1);
+	}
+
+	index = ZT_HASH_INDEX(h, id);
+	start = index;
+	for (;;) {
+		// The value of ihe_key is only valid if ihe_val is not NULL.
+		if ((h->ih_entries[index].key == id) &&
+		    (h->ih_entries[index].val != NULL)) {
+			return (index);
+		}
+		if (h->ih_entries[index].skips == 0) {
+			return ((size_t) -1);
+		}
+		index = ZT_HASH_NEXT(h, index);
+
+		if (index == start) {
+			break;
+		}
+	}
+
+	return ((size_t) -1);
+}
+
+int
+zt_hash_find(zt_hash *h, uint64_t id, void **vp)
+{
+	size_t index;
+	if ((index = zt_hash_find_index(h, id)) == (size_t) -1) {
+		return (NNG_ENOENT);
+	}
+	*vp = h->ih_entries[index].val;
+	return (0);
+}
+
+static int
+zt_hash_resize(zt_hash *h)
+{
+	size_t         newsize;
+	size_t         oldsize;
+	zt_hash_entry *newents;
+	zt_hash_entry *oldents;
+	uint32_t       i;
+
+	if ((h->ih_load < h->ih_maxload) && (h->ih_load >= h->ih_minload)) {
+		// No resize needed.
+		return (0);
+	}
+
+	oldsize = h->ih_cap;
+
+	newsize = 8;
+	while (newsize < (h->ih_count * 2)) {
+		newsize *= 2;
+	}
+	if (newsize == oldsize) {
+		// Same size.
+		return (0);
+	}
+
+	oldents = h->ih_entries;
+	newents = NNI_ALLOC_STRUCTS(newents, newsize);
+	if (newents == NULL) {
+		return (NNG_ENOMEM);
+	}
+
+	h->ih_entries = newents;
+	h->ih_cap     = newsize;
+	h->ih_load    = 0;
+	if (newsize > 8) {
+		h->ih_minload = newsize / 8;
+		h->ih_maxload = newsize * 2 / 3;
+	} else {
+		h->ih_minload = 0;
+		h->ih_maxload = 5;
+	}
+	for (i = 0; i < oldsize; i++) {
+		size_t index;
+		if (oldents[i].val == NULL) {
+			continue;
+		}
+		index = oldents[i].key & (newsize - 1);
+		for (;;) {
+			// Increment the load unconditionally.  It counts
+			// once for every item stored, plus once for each
+			// hashing operation we use to store the item (i.e.
+			// one for the item, plus once for each rehash.)
+			h->ih_load++;
+			if (newents[index].val == NULL) {
+				// As we are hitting this entry for the first
+				// time, it won't have any skips.
+				NNI_ASSERT(newents[index].skips == 0);
+				newents[index].val = oldents[i].val;
+				newents[index].key = oldents[i].key;
+				break;
+			}
+			newents[index].skips++;
+			index = ZT_HASH_NEXT(h, index);
+		}
+	}
+	if (oldsize != 0) {
+		NNI_FREE_STRUCTS(oldents, oldsize);
+	}
+	return (0);
+}
+
+int
+zt_hash_remove(zt_hash *h, uint64_t id)
+{
+	size_t         index;
+	size_t         probe;
+
+	if ((index = zt_hash_find_index(h, id)) == (size_t) -1) {
+		return (NNG_ENOENT);
+	}
+
+	// Now we have found the index where the object exists.  We are going
+	// to restart the search, until the index matches, to decrement the
+	// skips counter.
+	probe = (int) ZT_HASH_INDEX(h, id);
+
+	for (;;) {
+                zt_hash_entry *entry;
+		// The load was increased once each hashing operation we used
+		// to place the the item.  Decrement it accordingly.
+		h->ih_load--;
+		entry = &h->ih_entries[probe];
+		if (probe == index) {
+			entry->val = NULL;
+			entry->key = 0;
+			break;
+		}
+		NNI_ASSERT(entry->skips > 0);
+		entry->skips--;
+		probe = ZT_HASH_NEXT(h, probe);
+	}
+
+	h->ih_count--;
+
+	// Shrink -- but it's ok if we can't.
+	(void) zt_hash_resize(h);
+
+	return (0);
+}
+
+int
+zt_hash_insert(zt_hash *h, uint64_t id, void *val)
+{
+	size_t         index;
+	zt_hash_entry *ent;
+
+	// Try to resize -- if we don't need to, this will be a no-op.
+	if (zt_hash_resize(h) != 0) {
+		return (NNG_ENOMEM);
+	}
+
+	// If it already exists, just overwrite the old value.
+	if ((index = zt_hash_find_index(h, id)) != (size_t) -1) {
+		ent      = &h->ih_entries[index];
+		ent->val = val;
+		return (0);
+	}
+
+	index = ZT_HASH_INDEX(h, id);
+	for (;;) {
+		ent = &h->ih_entries[index];
+
+		// Increment the load count.  We do this each time time we
+		// rehash.  This may over-count items that collide on the
+		// same rehashing, but this should just cause a table to
+		// grow sooner, which is probably a good thing.
+		h->ih_load++;
+		if (ent->val == NULL) {
+			h->ih_count++;
+			ent->key = id;
+			ent->val = val;
+			return (0);
+		}
+		// Record the skip count.  This being non-zero informs
+		// that a rehash will be necessary.  Without this we
+		// would need to scan the entire hash for the match.
+		ent->skips++;
+		index = ZT_HASH_NEXT(h, index);
+	}
+}
+
+int
+zt_hash_alloc(zt_hash *h, uint64_t *idp, void *val)
+{
+	uint64_t id;
+	int      rv;
+
+	NNI_ASSERT(val != NULL);
+
+	if (h->ih_count > (h->ih_maxval - h->ih_minval)) {
+		// Really more like ENOSPC.. the table is filled to max.
+		return (NNG_ENOMEM);
+	}
+
+	for (;;) {
+		id = h->ih_dynval;
+		h->ih_dynval++;
+		if (h->ih_dynval > h->ih_maxval) {
+			h->ih_dynval = h->ih_minval;
+		}
+
+		if (zt_hash_find_index(h, id) == (size_t) -1) {
+			break;
+		}
+	}
+
+	rv = zt_hash_insert(h, id, val);
+	if (rv == 0) {
+		*idp = id;
+	}
+	return (rv);
+}
diff --git a/src/transport/zerotier/zthash.h b/src/transport/zerotier/zthash.h
new file mode 100644
index 00000000..249eabbf
--- /dev/null
+++ b/src/transport/zerotier/zthash.h
@@ -0,0 +1,43 @@
+//
+// Copyright 2020 Staysail Systems, Inc. <info@staysail.tech>
+// Copyright 2018 Capitar IT Group BV <info@capitar.com>
+//
+// This software is supplied under the terms of the MIT License, a
+// copy of which should be located in the distribution where this
+// file was obtained (LICENSE.txt).  A copy of the license may also be
+// found online at https://opensource.org/licenses/MIT.
+//
+
+#ifndef ZT_HASH_H
+#define ZT_HASH_H
+
+#include <stdint.h>
+
+// This code is derived from id hash, but supports 64-bit IDs.
+
+typedef struct zt_hash       zt_hash;
+typedef struct zt_hash_entry zt_hash_entry;
+
+// NB: These details are entirely private to the hash implementation.
+// They are provided here to facilitate inlining in structures.
+struct zt_hash {
+	size_t         ih_cap;
+	size_t         ih_count;
+	size_t         ih_load;
+	size_t         ih_minload; // considers placeholders
+	size_t         ih_maxload;
+	uint64_t       ih_minval;
+	uint64_t       ih_maxval;
+	uint64_t       ih_dynval;
+	zt_hash_entry *ih_entries;
+};
+
+extern int  zt_hash_init(zt_hash **);
+extern void zt_hash_fini(zt_hash *);
+extern void zt_hash_limits(zt_hash *, uint64_t, uint64_t, uint64_t);
+extern int  zt_hash_find(zt_hash *, uint64_t, void **);
+extern int  zt_hash_remove(zt_hash *, uint64_t);
+extern int  zt_hash_insert(zt_hash *, uint64_t, void *);
+extern int  zt_hash_alloc(zt_hash *, uint64_t *, void *);
+
+#endif // CORE_IDHASH_H