VPP-223 Bounded-index extensible hash documentation

Change-Id: If162252062014dbd8ef44f7f10649d54d9a288b0
Signed-off-by: Dave Barach <dave@barachs.net>

4 files changed, 166 insertions, 2 deletions

diff --git a/vppinfra/vppinfra/bihash_8_8.h b/vppinfra/vppinfra/bihash_8_8.h
index 21cb59ad67c..221e1f25534 100644
--- a/vppinfra/vppinfra/bihash_8_8.h
+++ b/vppinfra/vppinfra/bihash_8_8.h
@@ -25,11 +25,15 @@
 #include <vppinfra/pool.h>
 #include <vppinfra/xxhash.h>
 
+/** 8 octet key, 8 octet key value pair */
 typedef struct {
-  u64 key;
-  u64 value;
+  u64 key;                      /**< the key */
+  u64 value;                    /**< the value */
 } clib_bihash_kv_8_8_t;
 
+/** Decide if a clib_bihash_kv_8_8_t instance is free 
+    @param v- pointer to the (key,value) pair
+*/
 static inline int clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t *v)
 {
   if (v->key == ~0ULL && v->value == ~0ULL)
@@ -37,11 +41,19 @@ static inline int clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t *v)
   return 0;
 }
 
+/** Hash a clib_bihash_kv_8_8_t instance 
+    @param v - pointer to the (key,value) pair, hash the key (only)
+*/
 static inline u64 clib_bihash_hash_8_8  (clib_bihash_kv_8_8_t *v)
 {
   return clib_xxhash (v->key);
 }
 
+/** Format a clib_bihash_kv_8_8_t instance 
+    @param s - u8 * vector under construction
+    @param v (vararg) - the (key,value) pair to format
+    @return s - the u8 * vector under construction
+*/
 static inline u8 * format_bihash_kvp_8_8 (u8 * s, va_list * args)
 {
   clib_bihash_kv_8_8_t * v = va_arg (*args, clib_bihash_kv_8_8_t *);
@@ -50,6 +62,10 @@ static inline u8 * format_bihash_kvp_8_8 (u8 * s, va_list * args)
   return s;
 }
 
+/** Compare two clib_bihash_kv_8_8_t instances 
+    @param a - first key
+    @param b - second key
+*/
 static inline int clib_bihash_key_compare_8_8 (u64 a, u64 b)
 {
   return a == b;
diff --git a/vppinfra/vppinfra/bihash_doc.h b/vppinfra/vppinfra/bihash_doc.h
new file mode 100644
index 00000000000..037e7cc90e6
--- /dev/null
+++ b/vppinfra/vppinfra/bihash_doc.h
@@ -0,0 +1,140 @@
+/*
+ * Copyright (c) 2014 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.
+*/
+
+#error do not #include this file!
+
+/** \file
+
+    Bounded-index extensible hashing. The basic algorithm performs
+    thread-safe constant-time lookups in the face of a rational number
+    of hash collisions. The computed hash code h(k) must have
+    reasonable statistics with respect to the key space. It won't do
+    to have h(k) = 0 or 1, for all values of k.
+
+    Each bucket in the power-of-two bucket array contains the index
+    (in a private vppinfra memory heap) of the "backing store" for the
+    bucket, as well as a size field. The size field (log2_pages)
+    corresponds to 1, 2, 4, ... contiguous "pages" containing the
+    (key,value) pairs in the bucket.
+
+    When a single page fills, we allocate two contiguous pages.  We
+    recompute h(k) for each (key,value) pair, using an additional bit
+    to deal the (key, value) pairs into the "top" and "bottom" pages.
+
+    At lookup time, we compute h(k), using lg(bucket-array-size) to
+    pick the bucket. We read the bucket to find the base of the
+    backing pages.  We use an additional log2_pages' worth of bits
+    from h(k) to compute the offset of the page which will contain the
+    (key,value) pair we're trying to find.
+*/
+
+/** template key/value backing page structure */
+typedef struct clib_bihash_value {
+  union {
+
+    clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */
+    clib_bihash_value * next_free; /**< used when a KVP page (or block thereof) is on a freelist */
+  };
+} clib_bihash_value_t
+
+/** bihash bucket structure */
+typedef struct {
+  union {
+    struct {
+      u32 offset;  /**< backing page offset in the clib memory heap */
+      u8 pad[3];   /**< log2 (size of the packing page block) */
+      u8 log2_pages;
+    };
+    u64 as_u64;
+  };
+} clib_bihash_bucket_t;
+#endif /* __defined_clib_bihash_bucket_t__ */
+
+/** A bounded index extensible hash table */
+typedef struct {
+  clib_bihash_bucket_t * buckets; /**< Hash bucket vector, power-of-two in size */
+  volatile u32 * writer_lock; /**< Writer lock, in its own cache line */
+  BVT(clib_bihash_value) ** working_copies; /**< Working copies (various sizes), to avoid locking against readers */
+  clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */
+  u32 nbuckets;                      /**< Number of hash buckets */
+  u32 log2_nbuckets;                 /**< lg(nbuckets) */
+  u8 * name;                         /**< hash table name */
+  BVT(clib_bihash_value) **freelists; /**< power of two freelist vector */
+  void * mheap; /**< clib memory heap */
+} clib_bihash_t;
+
+/** Get pointer to value page given its clib mheap offset */
+static inline void * 
+clib_bihash_get_value (clib_bihash * h, uword offset);
+
+/** Get clib mheap offset given a pointer */
+static inline uword clib_bihash_get_offset (clib_bihash * h, void * v);
+
+/** initialize a bounded index extensible hash table 
+
+    @param h - the bi-hash table to initialize
+    @param name - name of the hash table
+    @param nbuckets - the number of buckets, will be rounded up to 
+a power of two
+    @param memory_size - clib mheap size, in bytes
+*/
+
+void clib_bihash_init
+(clib_bihash * h, char * name, u32 nbuckets, uword memory_size);
+
+/** Destroy a bounded index extensible hash table
+    @param h - the bi-hash table to free
+*/
+
+void clib_bihash_free (clib_bihash * h);
+
+/** Add or delete a (key,value) pair from a bi-hash table
+
+    @param h - the bi-hash table to search
+    @param add_kv - the (key,value) pair to add
+    @param is_add - add=1, delete=0
+    @returns 0 on success, < 0 on error
+    @note This function will replace an existing (key,value) pair if the
+    new key matches an existing key
+*/
+int clib_bihash_add_del (clib_bihash * h, 
+                         clib_bihash_kv * add_v,
+                         int is_add);
+
+
+/** Search a bi-hash table
+
+    @param h - the bi-hash table to search
+    @param search_v - (key,value) pair containing the search key
+    @param return_v - (key,value) pair which matches search_v.key
+    @returns 0 on success (with return_v set), < 0 on error
+*/
+int clib_bihash_search (clib_bihash * h, 
+                        clib_bihash_kv * search_v,
+                        clib_bihash_kv * return_v);
+
+
+/** Visit active (key,value) pairs in a bi-hash table
+
+    @param h - the bi-hash table to search
+    @param callback - function to call with each active (key,value) pair
+    @param arg - arbitrary second argument passed to the callback function
+    First argument is the (key,value) pair to visit
+    @note Trying to supply a proper function prototype for the
+    callback function appears to be a fool's errand.
+*/
+void clib_bihash_foreach_key_value_pair (clib_bihash) * h,
+    void *callback,
+    void *arg);
diff --git a/vppinfra/vppinfra/bihash_template.c b/vppinfra/vppinfra/bihash_template.c
index 35384a38067..0ee92c07570 100644
--- a/vppinfra/vppinfra/bihash_template.c
+++ b/vppinfra/vppinfra/bihash_template.c
@@ -13,6 +13,8 @@
  * limitations under the License.
  */
 
+/** @if DOCUMENTATION_IS_IN_BIHASH_DOC_H */
+
 void BV(clib_bihash_init) 
      (BVT(clib_bihash) * h, char * name, u32 nbuckets, 
      uword memory_size)
@@ -452,3 +454,5 @@ void BV(clib_bihash_foreach_key_value_pair)
         }
     }
 }
+
+/** @endif */
diff --git a/vppinfra/vppinfra/bihash_template.h b/vppinfra/vppinfra/bihash_template.h
index b7968e75453..5f80e7af044 100644
--- a/vppinfra/vppinfra/bihash_template.h
+++ b/vppinfra/vppinfra/bihash_template.h
@@ -14,6 +14,8 @@
  * limitations under the License.
 */
 
+/** @if DOCUMENTATION_IS_IN_BIHASH_DOC_H */
+
 /* 
  * Note: to instantiate the template multiple times in a single file,
  * #undef __included_bihash_template_h__...
@@ -197,3 +199,5 @@ static inline int BV(clib_bihash_search_inline_2)
 
 
 #endif /* __included_bihash_template_h__ */
+
+/** @endif */