ofp-msgs: Move most OpenFlow header definitions here.

[cascardo/ovs.git] / lib / cmap.c

diff --git a/lib/cmap.c b/lib/cmap.c
index a7a25f1..7a54ea6 100644 (file)
--- a/lib/cmap.c
+++ b/lib/cmap.c
@@ -16,12 +16,16 @@
 
 #include <config.h>
 #include "cmap.h"
+#include "coverage.h"
 #include "bitmap.h"
 #include "hash.h"
 #include "ovs-rcu.h"
 #include "random.h"
 #include "util.h"
 
+COVERAGE_DEFINE(cmap_expand);
+COVERAGE_DEFINE(cmap_shrink);
+
 /* Optimistic Concurrent Cuckoo Hash
  * =================================
  *
@@ -53,6 +57,10 @@
  * of about 93%.  The current implementation is conservative, expanding the
  * hash table when it is over 85% full.
  *
+ * When the load factor is below 20%, the hash table will be shrinked by half.
+ * This is to reduce the memory utilization of the hash table and to avoid
+ * the hash table occupying the top of heap chunk which prevents the trimming
+ * of heap.
  *
  * Hash Functions
  * ==============
@@ -150,15 +158,21 @@ BUILD_ASSERT_DECL(sizeof(struct cmap_bucket) == CACHE_LINE_SIZE);
  * values waste memory; larger values increase the average insertion time. */
 #define CMAP_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))
 
+/* Default minimum load factor (as a fraction of UINT32_MAX + 1) before
+ * shrinking a cmap.  Currently, the value is chosen to be 20%, this
+ * means cmap will have a 40% load factor after shrink. */
+#define CMAP_MIN_LOAD ((uint32_t) (UINT32_MAX * .20))
+
 /* The implementation of a concurrent hash map. */
 struct cmap_impl {
     unsigned int n;             /* Number of in-use elements. */
     unsigned int max_n;         /* Max elements before enlarging. */
+    unsigned int min_n;         /* Min elements before shrinking. */
     uint32_t mask;              /* Number of 'buckets', minus one. */
     uint32_t basis;             /* Basis for rehashing client's hash values. */
 
     /* Padding to make cmap_impl exactly one cache line long. */
-    uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 4];
+    uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 5];
 
     struct cmap_bucket buckets[];
 };
@@ -199,6 +213,12 @@ calc_max_n(uint32_t mask)
     return ((uint64_t) (mask + 1) * CMAP_K * CMAP_MAX_LOAD) >> 32;
 }
 
+static uint32_t
+calc_min_n(uint32_t mask)
+{
+    return ((uint64_t) (mask + 1) * CMAP_K * CMAP_MIN_LOAD) >> 32;
+}
+
 static struct cmap_impl *
 cmap_impl_create(uint32_t mask)
 {
@@ -210,6 +230,7 @@ cmap_impl_create(uint32_t mask)
                              + (mask + 1) * sizeof *impl->buckets);
     impl->n = 0;
     impl->max_n = calc_max_n(mask);
+    impl->min_n = calc_min_n(mask);
     impl->mask = mask;
     impl->basis = random_uint32();
 
@@ -369,13 +390,13 @@ cmap_find_batch(const struct cmap *cmap, unsigned long map,
     uint32_t c1s[sizeof map * CHAR_BIT];
 
     /* Compute hashes and prefetch 1st buckets. */
-    ULONG_FOR_EACH_1(i, map) {
+    ULLONG_FOR_EACH_1(i, map) {
         h1s[i] = rehash(impl, hashes[i]);
         b1s[i] = &impl->buckets[h1s[i] & impl->mask];
         OVS_PREFETCH(b1s[i]);
     }
     /* Lookups, Round 1. Only look up at the first bucket. */
-    ULONG_FOR_EACH_1(i, map) {
+    ULLONG_FOR_EACH_1(i, map) {
         uint32_t c1;
         const struct cmap_bucket *b1 = b1s[i];
         const struct cmap_node *node;
@@ -393,12 +414,12 @@ cmap_find_batch(const struct cmap *cmap, unsigned long map,
             continue;
         }
         /* Found. */
-        ULONG_SET0(map, i); /* Ignore this on round 2. */
+        ULLONG_SET0(map, i); /* Ignore this on round 2. */
         OVS_PREFETCH(node);
         nodes[i] = node;
     }
     /* Round 2. Look into the 2nd bucket, if needed. */
-    ULONG_FOR_EACH_1(i, map) {
+    ULLONG_FOR_EACH_1(i, map) {
         uint32_t c2;
         const struct cmap_bucket *b2 = b2s[i];
         const struct cmap_node *node;
@@ -424,7 +445,7 @@ cmap_find_batch(const struct cmap *cmap, unsigned long map,
                 }
             }
             /* Not found. */
-            ULONG_SET0(result, i); /* Fix the result. */
+            ULLONG_SET0(result, i); /* Fix the result. */
             continue;
         }
 found:
@@ -758,6 +779,7 @@ cmap_insert(struct cmap *cmap, struct cmap_node *node, uint32_t hash)
     ovsrcu_set_hidden(&node->next, NULL);
 
     if (OVS_UNLIKELY(impl->n >= impl->max_n)) {
+        COVERAGE_INC(cmap_expand);
         impl = cmap_rehash(cmap, (impl->mask << 1) | 1);
     }
 
@@ -825,6 +847,10 @@ cmap_replace(struct cmap *cmap, struct cmap_node *old_node,
 
     if (!new_node) {
         impl->n--;
+        if (OVS_UNLIKELY(impl->n < impl->min_n)) {
+            COVERAGE_INC(cmap_shrink);
+            impl = cmap_rehash(cmap, impl->mask >> 1);
+        }
     }
     return impl->n;
 }