This is the first commit of the hicn projectv19.01

Change-Id: I6f2544ad9b9f8891c88cc4bcce3cf19bd3cc863f
Signed-off-by: Luca Muscariello <lumuscar+fdio@cisco.com>

1 files changed, 1008 insertions, 0 deletions

diff --git a/hicn-plugin/src/hashtb.c b/hicn-plugin/src/hashtb.c
new file mode 100755
index 000000000..332da350d
--- /dev/null
+++ b/hicn-plugin/src/hashtb.c
@@ -0,0 +1,1008 @@
+/*
+ * Copyright (c) 2017-2019 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdlib.h>
+#include <errno.h>
+#include <assert.h>
+#include <inttypes.h>
+
+#include <vlib/vlib.h>
+#include <vppinfra/pool.h>
+
+#include "pcs.h"
+#include "hashtb.h"
+#include "parser.h"
+#include "error.h"
+
+/* return dvd/dvr, rounded up (intended for integer values) */
+#define    CEIL(dvd, dvr)                       \
+  ({                                            \
+    __typeof__ (dvd) _dvd = (dvd);              \
+    __typeof__ (dvr) _dvr = (dvr);              \
+    (_dvd + _dvr - 1)/_dvr;                     \
+  })
+
+#ifndef ALIGN8
+#define ALIGN8(p) (((p) + 0x7) & ~(0x7))
+#endif
+
+#ifndef ALIGNPTR8
+#define ALIGNPTR8(p) ((void *)(((u8 * )(p) + 0x7) & ~(0x7)))
+#endif
+
+#ifndef ALIGN64
+#define ALIGN64(p) (((p) + 0x3f) & ~(0x3f))
+#endif
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+
+/*
+ * Offset to aligned start of additional data (PIT/CS, FIB) embedded in each
+ * node.
+ */
+u32 ht_node_data_offset_aligned;
+
+/* Some support for posix vs vpp mem management */
+#define MEM_ALLOC(x) clib_mem_alloc_aligned((x), 8)
+#define MEM_FREE(p) clib_mem_free((p))
+
+/*
+ * Internal utilities
+ */
+
+/* Allocate an overflow bucket */
+static hicn_hash_bucket_t *
+alloc_overflow_bucket (hicn_hashtb_h h)
+{
+  hicn_hash_bucket_t *newbkt = NULL;
+
+  if (h->ht_overflow_buckets_used < h->ht_overflow_bucket_count)
+    {
+      pool_get_aligned (h->ht_overflow_buckets, newbkt, 8);
+
+      if (newbkt)
+	{
+	  h->ht_overflow_buckets_used++;
+	}
+    }
+  return (newbkt);
+}
+
+/* Free an overflow bucket; clear caller's pointer */
+static void
+free_overflow_bucket (hicn_hashtb_h h, hicn_hash_bucket_t ** pb)
+{
+  hicn_hash_bucket_t *bkt = *pb;
+
+  ASSERT (h->ht_overflow_buckets_used > 0);
+
+  pool_put (h->ht_overflow_buckets, bkt);
+  h->ht_overflow_buckets_used--;
+  *pb = NULL;
+}
+
+/*
+ * Init, allocate a new hashtable
+ */
+int
+hicn_hashtb_alloc (hicn_hashtb_h * ph, u32 max_elems, size_t app_data_size)
+{
+  int ret = HICN_ERROR_NONE;
+  hicn_hashtb_h h = NULL;
+  u32 count;
+  u32 total_buckets;
+  size_t sz;
+  hicn_hash_node_t *nodep;
+  hicn_hash_bucket_t *bucket;
+
+  if (ph == NULL)
+    {
+      ret = HICN_ERROR_HASHTB_INVAL;
+      goto done;
+    }
+  if (max_elems < HICN_HASHTB_MIN_ENTRIES ||
+      max_elems > HICN_HASHTB_MAX_ENTRIES)
+    {
+      goto done;
+    }
+  /* Allocate and init main hashtable struct */
+  h = MEM_ALLOC (sizeof (hicn_hashtb_t));
+  if (h == NULL)
+    {
+      ret = HICN_ERROR_HASHTB_NOMEM;
+      goto done;
+    }
+  memset (h, 0, sizeof (hicn_hashtb_t));
+
+  /* Compute main table bucket (row) count and size, and allocate */
+
+  /* Consider the last entry as used for containing the overflow bucket */
+  total_buckets = CEIL (max_elems, HICN_HASHTB_BUCKET_ENTRIES - 1);
+  count = ALIGN8 (CEIL (total_buckets, HICN_HASHTB_FILL_FACTOR));
+
+  h->ht_bucket_count = count;
+
+  /* We _really_ expect to have buckets aligned on cache lines ... */
+  sz = sizeof (hicn_hash_bucket_t);
+  assert (sz == ALIGN64 (sz));
+
+  h->ht_buckets = MEM_ALLOC (count * sz);
+  if (h->ht_buckets == NULL)
+    {
+      ret = HICN_ERROR_HASHTB_NOMEM;
+      goto done;
+    }
+  memset (h->ht_buckets, 0, count * sz);
+
+  /*
+   * First time through, compute offset to aligned extra data start in
+   * each node struct it's crucial that both the node struct (that the
+   * base hashtable uses) and the extra data area (that's also probably
+   * a struct) are aligned.
+   */
+  if (ht_node_data_offset_aligned == 0)
+    {
+      count = STRUCT_OFFSET_OF (hicn_hash_node_t, hn_data);
+      ht_node_data_offset_aligned = ALIGN8 (count);
+    }
+  //check app struct fits into space provided(HICN_HASH_NODE_APP_DATA_SIZE)
+  u32 ht_node_data_size;
+  ht_node_data_size = sizeof (hicn_hash_node_t) - ht_node_data_offset_aligned;
+  if (app_data_size > ht_node_data_size)
+    {
+      clib_error
+	("hicn hashtable: fatal error: requested app data size(%u) > hashtb node's configured bytes available(%u), sizeof(hicn_shared_t)=%u, sizeof(hicn_pit_entry_t)=%u, sizeof(hicn_cs_entry_t)=%u",
+	 app_data_size, ht_node_data_size, sizeof (hicn_pcs_shared_t),
+	 sizeof (hicn_pit_entry_t), sizeof (hicn_cs_entry_t));
+    }
+  /*
+   * Compute entry node count and size, allocate Allocate/'Hide' the
+   * zero-th node so can use zero as an 'empty' value
+   */
+  pool_alloc_aligned (h->ht_nodes, max_elems, 8);
+  if (h->ht_nodes == NULL)
+    {
+      ret = HICN_ERROR_HASHTB_NOMEM;
+      goto done;
+    }
+  pool_get_aligned (h->ht_nodes, nodep, 8);
+  //alloc node 0
+  nodep = nodep;		/* Silence 'not used' warning */
+
+  h->ht_node_count = max_elems;
+  h->ht_nodes_used = 1;
+
+  /*
+   * Compute overflow bucket count and size, allocate
+   */
+  //count = ALIGN8(CEIL(max_elems, HICN_HASHTB_OVERFLOW_FRACTION));
+  count = ALIGN8 (total_buckets - h->ht_bucket_count);
+
+  pool_alloc_aligned (h->ht_overflow_buckets, count, 8);
+  if (h->ht_overflow_buckets == NULL)
+    {
+      ret = HICN_ERROR_HASHTB_NOMEM;
+      goto done;
+    }
+  /* 'Hide' the zero-th node so we can use zero as an 'empty' value */
+  pool_get_aligned (h->ht_overflow_buckets, bucket, 8);
+  bucket = bucket;		/* Silence 'not used' warning */
+
+  h->ht_overflow_bucket_count = count;
+  h->ht_overflow_buckets_used = 1;
+
+done:
+
+  if (h)
+    {
+      if ((ret == HICN_ERROR_NONE) && ph)
+	{
+	  *ph = h;
+	}
+      else
+	{
+	  hicn_hashtb_free (&h);
+	}
+    }
+  return (ret);
+}
+
+/*
+ * Free, de-allocate a hashtable
+ */
+int
+hicn_hashtb_free (hicn_hashtb_h * ph)
+{
+  int ret = 0;
+
+  if (ph)
+    {
+      if ((*ph)->ht_nodes)
+	{
+	  pool_free ((*ph)->ht_nodes);
+	  (*ph)->ht_nodes = 0;
+	}
+      if ((*ph)->ht_overflow_buckets)
+	{
+	  pool_free ((*ph)->ht_overflow_buckets);
+	  (*ph)->ht_overflow_buckets = 0;
+	}
+      if ((*ph)->ht_buckets)
+	{
+	  MEM_FREE ((*ph)->ht_buckets);
+	  (*ph)->ht_buckets = 0;
+	}
+      MEM_FREE (*ph);
+
+      *ph = NULL;
+    }
+  return (ret);
+}
+
+
+
+/*
+ * Basic api to lookup a specific hash+key tuple. This does the entire lookup
+ * operation, retrieving node structs and comparing keys, so it's not
+ * optimized for prefetching or high performance.
+ *
+ * Returns zero and mails back a node on success, errno otherwise.
+ */
+int
+hicn_hashtb_lookup_node (hicn_hashtb_h h, const u8 * key,
+			 u32 keylen, u64 hashval, u8 is_data,
+			 u32 * node_id, u8 * dpo_ctx_id, u8 * vft_id,
+			 u8 * is_cs, u8 * hash_entry_id, u32 * bucket_id,
+			 u8 * bucket_is_overflow)
+{
+  return (hicn_hashtb_lookup_node_ex
+	  (h, key, keylen, hashval, is_data, FALSE /* deleted nodes */ ,
+	   node_id,
+	   dpo_ctx_id, vft_id, is_cs, hash_entry_id, bucket_id,
+	   bucket_is_overflow));
+}
+
+/*
+ * Extended api to lookup a specific hash+key tuple. The implementation
+ * allows the caller to locate nodes that are marked for deletion, which is
+ * part of some hashtable applications, such as the FIB.
+ *
+ * This does the entire lookup operation, retrieving node structs and comparing
+ * keys, so it's not optimized for prefetching or high performance.
+ *
+ * Returns zero and mails back a node on success, errno otherwise.
+ */
+int
+hicn_hashtb_lookup_node_ex (hicn_hashtb_h h, const u8 * key,
+			    u32 keylen, u64 hashval, u8 is_data,
+			    int include_deleted_p, u32 * node_id,
+			    u8 * dpo_ctx_id, u8 * vft_id, u8 * is_cs,
+			    u8 * hash_entry_id, u32 * bucket_id,
+			    u8 * bucket_is_overflow)
+{
+  int i, ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
+  int found_p = FALSE;
+  u32 bidx;
+  hicn_hash_bucket_t *bucket;
+  u32 current_bucket_id = ~0;
+
+  /*
+   * Use some bits of the low half of the hash to locate a row/bucket
+   * in the table
+   */
+  current_bucket_id = bidx = (hashval & (h->ht_bucket_count - 1));
+
+  bucket = h->ht_buckets + bidx;
+
+  *bucket_is_overflow = 0;
+  /* Check the entries in the bucket for matching hash value */
+
+loop_buckets:
+
+  for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES && !found_p; i++)
+    {
+      /*
+       * If an entry is marked for deletion, ignore it unless the
+       * caller explicitly wants these nodes.
+       */
+      if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
+	{
+	  if (!include_deleted_p)
+	    {
+	      continue;
+	    }
+	}
+      if (bucket->hb_entries[i].he_msb64 == hashval)
+	{
+	  /*
+	   * Found a candidate - must retrieve the actual node
+	   * and check the key.
+	   */
+	  *node_id = bucket->hb_entries[i].he_node;
+	  *dpo_ctx_id = bucket->hb_entries[i].dpo_ctx_id;
+	  *vft_id = bucket->hb_entries[i].vft_id;
+	  *is_cs =
+	    bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_CS_ENTRY;
+	  *hash_entry_id = i;
+	  *bucket_id = current_bucket_id;
+	  /*
+	   * If we are doing lookup for a data, do not take a
+	   * lock in case of a hit with a CS entry
+	   */
+	  if (!(is_data && *is_cs))
+	    {
+	      bucket->hb_entries[i].locks++;
+	    }
+	  found_p = TRUE;
+	  ret = HICN_ERROR_NONE;
+	  goto done;
+	}
+    }
+
+  /*
+   * Be prepared to continue to an overflow bucket if necessary. We
+   * only expect the last entry in a bucket to refer to an overflow
+   * bucket...
+   */
+  i = HICN_HASHTB_BUCKET_ENTRIES - 1;
+  if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
+    {
+      current_bucket_id = bucket->hb_entries[i].he_node;
+      bucket = pool_elt_at_index (h->ht_overflow_buckets,
+				  bucket->hb_entries[i].he_node);
+      *bucket_is_overflow = 1;
+      goto loop_buckets;
+    }
+done:
+
+  return (ret);
+}
+
+/**
+ * This function allows to split the hash verification from the comparison of
+ * the entire key. Useful to exploit prefertching.
+ * return 1 if equals, 0 otherwise
+ */
+int
+hicn_node_compare (const u8 * key, u32 keylen, hicn_hash_node_t * node)
+{
+
+  int ret = 0;
+
+  if (key && keylen == node->hn_keysize)
+    {
+      ret = (memcmp (key, node->hn_key.ks.key, keylen) == 0);
+    }
+  return ret;
+}
+
+/*
+ * Utility to init a new entry in a hashtable bucket/row. We use this to add
+ * new a node+hash, and to clear out an entry during removal.
+ */
+void
+hicn_hashtb_init_entry (hicn_hash_entry_t * entry, u32 nodeidx,
+			u64 hashval, u32 locks)
+{
+  entry->he_msb64 = hashval;
+  entry->he_node = nodeidx;
+
+  /* Clear out some other fields in the entry */
+  entry->he_flags = 0;
+  entry->locks = locks;
+}
+
+/*
+ * Insert a node into the hashtable. We expect the caller has a) computed the
+ * hash value to use, b) initialized the node with the hash and key info, and
+ * c) filled in its app-specific data portion of the node.
+ */
+
+int
+hicn_hashtb_insert (hicn_hashtb_h h, hicn_hash_node_t * node,
+		    hicn_hash_entry_t ** hash_entry, u64 hash,
+		    u32 * node_id,
+		    u8 * dpo_ctx_id, u8 * vft_id, u8 * is_cs,
+		    u8 * hash_entry_id, u32 * bucket_id,
+		    u8 * bucket_is_overflow)
+{
+  int i, ret = HICN_ERROR_HASHTB_INVAL;
+  u32 bidx;
+  hicn_hash_bucket_t *bucket, *newbkt;
+  int use_seven;
+  u32 current_bucket_id = ~0;
+  int is_overflow = 0;
+
+  *hash_entry = NULL;
+
+  if (h == NULL)
+    {
+      goto done;
+    }
+  /*
+   * Use some bits of the low half of the hash to locate a row/bucket
+   * in the table
+   */
+  current_bucket_id = bidx = (hash & (h->ht_bucket_count - 1));
+
+  bucket = h->ht_buckets + bidx;
+
+  use_seven = (h->ht_flags & HICN_HASHTB_FLAG_USE_SEVEN);
+
+  /* Locate a free entry slot in the bucket */
+
+loop_buckets:
+
+  for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++)
+    {
+
+      /*
+       * If an entry is marked for deletion, ignore it
+       */
+      if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
+	{
+	  continue;
+	}
+      /*
+       * Be sure that we are not inserting the same entry twice
+       */
+      if (bucket->hb_entries[i].he_msb64 == hash)
+	{
+	  /*
+	   * We hit an existing pit entry. increase lock.
+	   */
+
+	  *node_id = bucket->hb_entries[i].he_node;
+	  *dpo_ctx_id = bucket->hb_entries[i].dpo_ctx_id;
+	  *vft_id = bucket->hb_entries[i].vft_id;
+	  *is_cs =
+	    bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_CS_ENTRY;
+	  *hash_entry_id = i;
+	  *bucket_id = current_bucket_id;
+	  *hash_entry = &(bucket->hb_entries[i]);
+	  /*
+	   * If we are doing lookup for a data, do not take a
+	   * lock in case of a hit with a CS entry
+	   */
+	  bucket->hb_entries[i].locks++;
+	  *bucket_is_overflow = is_overflow;
+	  ret = HICN_ERROR_HASHTB_EXIST;
+	  goto done;
+	}
+      if ((bucket->hb_entries[i].he_msb64 == 0LL) &&
+	  (bucket->hb_entries[i].he_node == 0))
+	{
+	  /* Found a candidate -- fill it in */
+
+	  /*
+	   * Special case if the application asked not to use
+	   * the last entry in each bucket.
+	   */
+	  if ((i != (HICN_HASHTB_BUCKET_ENTRIES - 1)) || use_seven)
+	    {
+	      hicn_hashtb_init_entry (&(bucket->hb_entries[i]),
+				      NODE_IDX_FROM_NODE (node, h), hash, 0);
+
+	      *hash_entry = &(bucket->hb_entries[i]);
+
+	      node->bucket_id = current_bucket_id;
+	      node->entry_idx = i;
+	      if (is_overflow)
+		node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
+
+	      ret = HICN_ERROR_NONE;
+	      goto done;
+	    }
+	}
+    }
+  /*
+   * Be prepared to continue to an overflow bucket if necessary, or to
+   * add a new overflow bucket. We only expect the last entry in a
+   * bucket to refer to an overflow bucket...
+   */
+  i = HICN_HASHTB_BUCKET_ENTRIES - 1;
+  if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
+    {
+      /* Existing overflow bucket - re-start the search loop */
+      current_bucket_id = bucket->hb_entries[i].he_node;
+      bucket = pool_elt_at_index (h->ht_overflow_buckets, current_bucket_id);
+      is_overflow = 1;
+      goto loop_buckets;
+
+    }
+  else
+    {
+      /*
+       * Overflow - reached the end of a bucket without finding a
+       * free entry slot. Need to allocate an overflow bucket, and
+       * connect it to this bucket.
+       */
+      newbkt = alloc_overflow_bucket (h);
+      if (newbkt == NULL)
+	{
+	  ret = HICN_ERROR_HASHTB_NOMEM;
+	  goto done;
+	}
+      /*
+       * We're touching some more bytes than we absolutely have to
+       * here, but ... that seems ok.
+       */
+      memset (newbkt, 0, sizeof (hicn_hash_bucket_t));
+
+      if (use_seven)
+	{
+	  /*
+	   * Copy existing entry into new bucket - we really
+	   * expect these to be properly aligned so they can be
+	   * treated as int.
+	   */
+	  memcpy (&(newbkt->hb_entries[0]),
+		  &(bucket->hb_entries[i]), sizeof (hicn_hash_entry_t));
+
+	  /* Update bucket id and entry_idx on the hash node */
+	  hicn_hash_node_t *node =
+	    pool_elt_at_index (h->ht_nodes, newbkt->hb_entries[0].he_node);
+	  node->bucket_id = (newbkt - h->ht_overflow_buckets);
+	  node->entry_idx = 0;
+	  node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
+
+	}
+      /*
+       * Connect original bucket to the index of the new overflow
+       * bucket
+       */
+      bucket->hb_entries[i].he_flags |= HICN_HASH_ENTRY_FLAG_OVERFLOW;
+      bucket->hb_entries[i].he_node = (newbkt - h->ht_overflow_buckets);
+
+      /* Add new entry to new overflow bucket */
+      bucket = newbkt;
+
+      /*
+       * Use entry [1] in the new bucket _if_ we just copied into
+       * entry [zero] above.
+       */
+      if (use_seven)
+	{
+
+	  hicn_hashtb_init_entry (&(bucket->hb_entries[1]),
+				  NODE_IDX_FROM_NODE (node, h), hash, 0);
+	  *hash_entry = &(bucket->hb_entries[1]);
+
+	  node->bucket_id = (newbkt - h->ht_overflow_buckets);
+	  node->entry_idx = 1;
+	  node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
+	}
+      else
+	{
+
+	  hicn_hashtb_init_entry (&(bucket->hb_entries[0]),
+				  NODE_IDX_FROM_NODE (node, h), hash, 0);
+	  *hash_entry = &(bucket->hb_entries[0]);
+	  node->bucket_id = (newbkt - h->ht_overflow_buckets);
+	  node->entry_idx = 0;
+	  node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
+	}
+    }
+
+  /* And we're done with the overflow bucket */
+  ret = HICN_ERROR_NONE;
+
+done:
+
+  return (ret);
+}
+
+/*
+ * Delete a node from a hashtable using the node itself, and delete/free the
+ * node. Caller's pointer is cleared on success.
+ */
+void
+hicn_hashtb_delete (hicn_hashtb_h h, hicn_hash_node_t ** pnode, u64 hashval)
+{
+
+  hicn_hashtb_remove_node (h, *pnode, hashval);
+  hicn_hashtb_free_node (h, *pnode);
+  *pnode = NULL;
+
+}
+
+/*
+ * Delete an entry from a hashtable using the node itself. If the node was
+ * stored in an overflow bucket, and the bucket is empty after freeing the
+ * node, the bucket is freed as well.
+ */
+void
+hicn_hashtb_remove_node (hicn_hashtb_h h, hicn_hash_node_t * node,
+			 u64 hashval)
+{
+  int i, count;
+  u32 bidx, overflow_p;
+  hicn_hash_bucket_t *bucket, *parent;
+
+  if ((h == NULL) || (node == NULL))
+    {
+      goto done;
+    }
+  if (node->hn_flags & HICN_HASH_NODE_OVERFLOW_BUCKET)
+    bucket = pool_elt_at_index (h->ht_overflow_buckets, node->bucket_id);
+  else
+    {
+      /*
+       * Use some bits of the low half of the hash to locate a
+       * row/bucket in the table
+       */
+      bidx = (hashval & (h->ht_bucket_count - 1));
+      ASSERT (bidx == node->bucket_id);
+      bucket = h->ht_buckets + node->bucket_id;
+    }
+
+  overflow_p = node->hn_flags & HICN_HASH_NODE_OVERFLOW_BUCKET;
+
+  /* Clear out the entry. */
+  hicn_hashtb_init_entry (&(bucket->hb_entries[node->entry_idx]), 0, 0LL, 0);
+
+  if (!overflow_p)
+    {
+      /*
+       * And we're done, in the easy case where we didn't change an
+       * overflow bucket
+       */
+      goto done;
+    }
+  /*
+   * The special case: if this is the last remaining entry in an
+   * overflow bucket, liberate the bucket. That in turn has a special
+   * case if this bucket is in the middle of a chain of overflow
+   * buckets.
+   *
+   * Note that we're not trying aggressively (yet) to condense buckets at
+   * every possible opportunity.
+   */
+
+  /*
+   * Reset this flag; we'll set it again if this bucket links to
+   * another
+   */
+  overflow_p = FALSE;
+
+  for (i = 0, count = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++)
+    {
+      if (bucket->hb_entries[i].he_node != 0)
+	{
+	  count++;
+	}
+      if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1) &&
+	  (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW))
+	{
+	  count--;		/* Doesn't count as a 'real' entry */
+	  overflow_p = TRUE;
+	}
+    }
+
+  if (count > 0)
+    {
+      /* Still a (real) entry in the row */
+      goto done;
+    }
+  /*
+   * Need to locate the predecessor of 'bucket': start at the beginning
+   * of the chain of buckets and move forward
+   */
+  bidx = (hashval & (h->ht_bucket_count - 1));
+
+  for (parent = h->ht_buckets + bidx; parent != NULL;)
+    {
+
+      if ((parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_flags &
+	   HICN_HASH_ENTRY_FLAG_OVERFLOW) == 0)
+	{
+	  parent = NULL;
+	  break;
+	}
+      bidx = parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node;
+
+      if (pool_elt_at_index (h->ht_overflow_buckets, bidx) == bucket)
+	{
+	  /*
+	   * Found the predecessor of 'bucket'. If 'bucket' has
+	   * a successor, connect 'parent' to it, and take
+	   * 'bucket out of the middle.
+	   */
+	  if (overflow_p)
+	    {
+	      parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node =
+		bucket->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node;
+	    }
+	  else
+	    {
+	      /*
+	       * Just clear the predecessor entry pointing
+	       * at 'bucket'
+	       */
+	      hicn_hashtb_init_entry (&parent->hb_entries
+				      [(HICN_HASHTB_BUCKET_ENTRIES - 1)], 0,
+				      0LL, 0);
+	    }
+
+	  break;
+	}
+      /*
+       * After the first iteration, 'parent' will be an overflow
+       * bucket too
+       */
+      parent = pool_elt_at_index (h->ht_overflow_buckets, bidx);
+    }
+
+  /* We really expect to have found the predecessor */
+  ASSERT (parent != NULL);
+
+  /* And now, finally, we can put 'bucket' back on the free list */
+  free_overflow_bucket (h, &bucket);
+
+done:
+  return;
+}
+
+/*
+ * Prepare a hashtable node, supplying the key, and computed hash info.
+ */
+void
+hicn_hashtb_init_node (hicn_hashtb_h h, hicn_hash_node_t * node,
+		       const u8 * key, u32 keylen)
+{
+  assert (h != NULL);
+  assert (node != NULL);
+  assert (keylen <= HICN_PARAM_HICN_NAME_LEN_MAX);
+
+  /* Init the node struct */
+  node->hn_flags = HICN_HASH_NODE_FLAGS_DEFAULT;
+  node->hn_keysize = 0;
+  node->hn_keysize = keylen;
+  memcpy (node->hn_key.ks.key, key, keylen);
+  node->bucket_id = ~0;
+  node->entry_idx = ~0;
+}
+
+/*
+ * Release a hashtable node back to the free list when an entry is cleared
+ */
+void
+hicn_hashtb_free_node (hicn_hashtb_h h, hicn_hash_node_t * node)
+{
+  ASSERT (h->ht_nodes_used > 0);
+
+  /* Return 'node' to the free list */
+  pool_put (h->ht_nodes, node);
+  h->ht_nodes_used--;
+
+}
+
+/*
+ * Walk a hashtable, iterating through the nodes, keeping context in 'ctx'.
+ */
+int
+hicn_hashtb_next_node (hicn_hashtb_h h, hicn_hash_node_t ** pnode, u64 * ctx)
+{
+  int i, j, ret = HICN_ERROR_HASHTB_INVAL;
+  u32 bidx, entry;
+  hicn_hash_bucket_t *bucket;
+
+  if ((h == NULL) || (pnode == NULL) || (ctx == NULL))
+    {
+      goto done;
+    }
+  /* Special-case for new iteration */
+  if (*ctx == HICN_HASH_WALK_CTX_INITIAL)
+    {
+      bidx = 0;
+      bucket = &h->ht_buckets[0];
+      entry = 0;
+      j = 0;
+      i = 0;
+      goto search_table;
+    }
+  /* Convert context to bucket and entry indices */
+  bidx = *ctx & 0xffffffffLL;
+  entry = *ctx >> 32;
+
+  if (bidx >= h->ht_bucket_count)
+    {
+      ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
+      goto done;
+    }
+  bucket = h->ht_buckets + bidx;
+
+  /* Init total index into entries (includes fixed bucket and overflow) */
+  j = 0;
+
+skip_processed_bucket_chunks:
+  /*
+   * Figure out where to resume the search for the next entry in the
+   * table, by trying to find the last entry returned, from the cookie.
+   * Loop walks one (regular or overflow) bucket chunk, label is used
+   * for walking chain of chunks. Note that if there was a deletion or
+   * an addition that created an overflow, iterator can skip entries or
+   * return duplicate entries, for entries that are present from before
+   * the walk starts until after it ends.
+   */
+
+  for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++, j++)
+    {
+      if (j > entry)
+	{
+	  /*
+	   * Start search for next here, use existing 'bucket'
+	   * and 'i'
+	   */
+	  break;
+	}
+      /*
+       * If an entry is marked for deletion, ignore it
+       */
+      if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
+	{
+	  continue;
+	}
+      /*
+       * Be prepared to continue to an overflow bucket if
+       * necessary. (We only expect the last entry in a bucket to
+       * refer to an overflow bucket...)
+       */
+      if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1))
+	{
+	  if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
+	    {
+	      bucket = pool_elt_at_index (h->ht_overflow_buckets,
+					  bucket->hb_entries[i].he_node);
+
+	      /* Increment overall entry counter 'j' */
+	      j++;
+
+	      goto skip_processed_bucket_chunks;
+	    }
+	  /*
+	   * end of row (end of fixed bucket plus any
+	   * overflows)
+	   */
+	  i = 0;
+	  j = 0;
+
+	  bidx++;
+
+	  /* Special case - we're at the end */
+	  if (bidx >= h->ht_bucket_count)
+	    {
+	      ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
+	      goto done;
+	    }
+	  bucket = h->ht_buckets + bidx;
+	  break;
+	}
+    }
+
+search_table:
+
+  /*
+   * Now we're searching through the table for the next entry that's
+   * set
+   */
+
+  for (; i < HICN_HASHTB_BUCKET_ENTRIES; i++, j++)
+    {
+      /*
+       * If an entry is marked for deletion, ignore it
+       */
+      if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
+	{
+	  continue;
+	}
+      /* Is this entry set? */
+      if (bucket->hb_entries[i].he_node != 0)
+	{
+
+	  /* Retrieve the node struct */
+	  *pnode = pool_elt_at_index (h->ht_nodes,
+				      bucket->hb_entries[i].he_node);
+
+	  /*
+	   * Set 'entry' as we exit, so we can update the
+	   * cookie
+	   */
+	  entry = j;
+	  ret = HICN_ERROR_NONE;
+	  break;
+	}
+      /*
+       * Be prepared to continue to an overflow bucket if
+       * necessary. (We only expect the last entry in a bucket to
+       * refer to an overflow bucket...)
+       */
+      if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1))
+	{
+	  if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
+	    {
+	      bucket = pool_elt_at_index (h->ht_overflow_buckets,
+					  bucket->hb_entries[i].he_node);
+	      /*
+	       * Reset per-bucket index 'i', here (not done
+	       * in iterator)
+	       */
+	      i = 0;
+	      /* Increment overall entry counter 'j' */
+	      j++;
+
+	      goto search_table;
+	    }
+	  else
+	    {
+	      /*
+	       * Move to next bucket, resetting per-bucket
+	       * and overall entry indexes
+	       */
+	      i = 0;
+	      j = 0;
+
+	      bidx++;
+
+	      /* Special case - we're at the end */
+	      if (bidx >= h->ht_bucket_count)
+		{
+		  ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
+		  goto done;
+		}
+	      bucket = h->ht_buckets + bidx;
+	      goto search_table;
+	    }
+	}
+    }
+
+done:
+
+  if (ret == HICN_ERROR_NONE)
+    {
+      /* Update context */
+      *ctx = bidx;
+      *ctx |= ((u64) entry << 32);
+    }
+  return (ret);
+}
+
+int
+hicn_hashtb_key_to_buf (u8 ** vec_res, hicn_hashtb_h h,
+			const hicn_hash_node_t * node)
+{
+  int ret = HICN_ERROR_NONE;
+  u8 *vec = *vec_res;
+
+  if (node->hn_keysize <= HICN_HASH_KEY_BYTES)
+    {
+      vec_add (vec, node->hn_key.ks.key, node->hn_keysize);
+    }
+  *vec_res = vec;
+  return (ret);
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables: eval: (c-set-style "gnu") End:
+ */