rculfhash: reorder cds_lfht for smaller cache footprint in fast-paths

[urcu.git] / rculfhash-internal.h

diff --git a/rculfhash-internal.h b/rculfhash-internal.h
index 820e62c2ba6cda664c72b591b489831e12284353..792e04da0304063041f57621091d6967c430b457 100644 (file)
--- a/rculfhash-internal.h
+++ b/rculfhash-internal.h
@@ -38,6 +38,8 @@
 #define MAX_TABLE_ORDER                        64
 #endif
 
+#define MAX_CHUNK_TABLE                        (1UL << 10)
+
 #ifndef min
 #define min(a, b)      ((a) < (b) ? (a) : (b))
 #endif
@@ -54,8 +56,63 @@ struct ht_items_count;
  * cookie to users.
  */
 struct cds_lfht {
+       /*
+        * Variables needed for the lookup, add and remove fast-paths.
+        */
        unsigned long size;     /* always a power of 2, shared (RCU) */
+       union {
+               /*
+                * Contains the per order-index-level bucket node table.
+                * The size of each bucket node table is half the number
+                * of hashes contained in this order (except for order 0).
+                * The minimum allocation buckets size parameter allows
+                * combining the bucket node arrays of the lowermost
+                * levels to improve cache locality for small index orders.
+                */
+               struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
+
+               /*
+                * Contains the bucket node chunks. The size of each
+                * bucket node chunk is ->min_alloc_size (we avoid to
+                * allocate chunks with different size). Chunks improve
+                * cache locality for small index orders, and are more
+                * friendly with environments where allocation of large
+                * contiguous memory areas is challenging due to memory
+                * fragmentation concerns or inability to use virtual
+                * memory addressing.
+                */
+               struct cds_lfht_node *tbl_chunk[0];
+
+               /*
+                * Memory mapping with room for all possible buckets.
+                * Their memory is allocated when needed.
+                */
+               struct cds_lfht_node *tbl_mmap;
+       };
+       /*
+        * bucket_at pointer is kept here to skip the extra level of
+        * dereference needed to get to "mm" (this is a fast-path).
+        */
+       struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
+                       unsigned long index);
+       /*
+        * End of variables needed for lookup fast-path.
+        */
+
+       struct ht_items_count *split_count;     /* split item count */
+       /*
+        * End of variables needed for add/remove fast-path.
+        */
+
+       /* Initial configuration items */
        int flags;
+       unsigned long min_alloc_buckets_order;
+       unsigned long min_nr_alloc_buckets;
+       unsigned long max_nr_buckets;
+       const struct cds_lfht_mm_type *mm;      /* memory management plugin */
+       const struct rcu_flavor_struct *flavor; /* RCU flavor */
+
+       long count;                     /* global approximate item count */
 
        /*
         * We need to put the work threads offline (QSBR) when taking this
@@ -69,32 +126,6 @@ struct cds_lfht {
        unsigned int in_progress_resize, in_progress_destroy;
        unsigned long resize_target;
        int resize_initiated;
-       const struct rcu_flavor_struct *flavor;
-
-       long count;                     /* global approximate item count */
-       struct ht_items_count *split_count;     /* split item count */
-
-       /* memory management related fields are located at the end */
-       const struct cds_lfht_mm_type *mm;
-
-       unsigned long min_alloc_buckets_order;
-       unsigned long min_nr_alloc_buckets;
-       unsigned long max_nr_buckets;
-
-       struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
-                       unsigned long index);
-
-       union {
-               /*
-                * Contains the per order-index-level bucket node table.
-                * The size of each bucket node table is half the number
-                * of hashes contained in this order (except for order 0).
-                * The minimum allocation buckets size parameter allows
-                * combining the bucket node arrays of the lowermost
-                * levels to improve cache locality for small index orders.
-                */
-               struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
-       };
 };
 
 extern unsigned int fls_ulong(unsigned long x);