src/rculfhash-internal.h

   1 // SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   2 // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
   3 //
   4 // SPDX-License-Identifier: LGPL-2.1-or-later
   5
   6 #ifndef _URCU_RCULFHASH_INTERNAL_H
   7 #define _URCU_RCULFHASH_INTERNAL_H
   8
   9 /*
  10  * Internal header for Lock-Free RCU Hash Table
  11  */
  12
  13 #include <urcu/assert.h>
  14 #include <urcu/rculfhash.h>
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17
  18 #include "workqueue.h"
  19
  20 #ifdef DEBUG
  21 #define dbg_printf(fmt, args...)     printf("[debug rculfhash] " fmt, ## args)
  22 #else
  23 #define dbg_printf(fmt, args...)                                \
  24 do {                                                            \
  25         /* do nothing but check printf format */                \
  26         if (0)                                                  \
  27                 printf("[debug rculfhash] " fmt, ## args);      \
  28 } while (0)
  29 #endif
  30
  31 #if (CAA_BITS_PER_LONG == 32)
  32 #define MAX_TABLE_ORDER                 32
  33 #else
  34 #define MAX_TABLE_ORDER                 64
  35 #endif
  36
  37 #define MAX_CHUNK_TABLE                 (1UL << 10)
  38
  39 #ifndef min
  40 #define min(a, b)       ((a) < (b) ? (a) : (b))
  41 #endif
  42
  43 #ifndef max
  44 #define max(a, b)       ((a) > (b) ? (a) : (b))
  45 #endif
  46
  47 struct ht_items_count;
  48
  49 /*
  50  * cds_lfht: Top-level data structure representing a lock-free hash
  51  * table. Defined in the implementation file to make it be an opaque
  52  * cookie to users.
  53  *
  54  * The fields used in fast-paths are placed near the end of the
  55  * structure, because we need to have a variable-sized union to contain
  56  * the mm plugin fields, which are used in the fast path.
  57  */
  58 struct cds_lfht {
  59         /* Initial configuration items */
  60         unsigned long max_nr_buckets;
  61         const struct cds_lfht_mm_type *mm;      /* memory management plugin */
  62         const struct cds_lfht_alloc *alloc;     /* memory allocator for mm */
  63         const struct rcu_flavor_struct *flavor; /* RCU flavor */
  64
  65         long count;                     /* global approximate item count */
  66
  67         /*
  68          * We need to put the work threads offline (QSBR) when taking this
  69          * mutex, because we use synchronize_rcu within this mutex critical
  70          * section, which waits on read-side critical sections, and could
  71          * therefore cause grace-period deadlock if we hold off RCU G.P.
  72          * completion.
  73          */
  74         pthread_mutex_t resize_mutex;           /* resize mutex: add/del mutex */
  75         pthread_attr_t *caller_resize_attr;     /* resize threads attributes from lfht_new caller */
  76         pthread_attr_t resize_attr;
  77         unsigned int in_progress_destroy;
  78         unsigned long resize_target;
  79         int resize_initiated;
  80         struct urcu_work destroy_work;
  81
  82         /*
  83          * Variables needed for add and remove fast-paths.
  84          */
  85         int flags;
  86         unsigned long min_alloc_buckets_order;
  87         unsigned long min_nr_alloc_buckets;
  88         struct ht_items_count *split_count;     /* split item count */
  89
  90         /*
  91          * Variables needed for the lookup, add and remove fast-paths.
  92          */
  93         unsigned long size;     /* always a power of 2, shared (RCU) */
  94         /*
  95          * bucket_at pointer is kept here to skip the extra level of
  96          * dereference needed to get to "mm" (this is a fast-path).
  97          */
  98         struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
  99                         unsigned long index);
 100         /*
 101          * Dynamic length "tbl_chunk" needs to be at the end of
 102          * cds_lfht.
 103          */
 104         union {
 105                 /*
 106                  * Contains the per order-index-level bucket node table.
 107                  * The size of each bucket node table is half the number
 108                  * of hashes contained in this order (except for order 0).
 109                  * The minimum allocation buckets size parameter allows
 110                  * combining the bucket node arrays of the lowermost
 111                  * levels to improve cache locality for small index orders.
 112                  */
 113                 struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
 114
 115                 /*
 116                  * Contains the bucket node chunks. The size of each
 117                  * bucket node chunk is ->min_alloc_size (we avoid to
 118                  * allocate chunks with different size). Chunks improve
 119                  * cache locality for small index orders, and are more
 120                  * friendly with environments where allocation of large
 121                  * contiguous memory areas is challenging due to memory
 122                  * fragmentation concerns or inability to use virtual
 123                  * memory addressing.
 124                  */
 125                 struct cds_lfht_node *tbl_chunk[0];
 126
 127                 /*
 128                  * Memory mapping with room for all possible buckets.
 129                  * Their memory is allocated when needed.
 130                  */
 131                 struct cds_lfht_node *tbl_mmap;
 132         };
 133         /*
 134          * End of variables needed for the lookup, add and remove
 135          * fast-paths.
 136          */
 137 };
 138
 139 extern unsigned int cds_lfht_fls_ulong(unsigned long x);
 140 extern int cds_lfht_get_count_order_ulong(unsigned long x);
 141
 142 #ifdef POISON_FREE
 143 #define poison_free(alloc, ptr)                                 \
 144         do {                                                    \
 145                 if (ptr) {                                      \
 146                         memset(ptr, 0x42, sizeof(*(ptr)));      \
 147                         alloc->free(alloc->state, ptr);                         \
 148                 }                                               \
 149         } while (0)
 150 #else
 151 #define poison_free(alloc, ptr) alloc->free(alloc->state, ptr)
 152 #endif
 153
 154 static inline
 155 struct cds_lfht *__default_alloc_cds_lfht(
 156                 const struct cds_lfht_mm_type *mm,
 157                 const struct cds_lfht_alloc *alloc,
 158                 unsigned long cds_lfht_size,
 159                 unsigned long min_nr_alloc_buckets,
 160                 unsigned long max_nr_buckets)
 161 {
 162         struct cds_lfht *ht;
 163
 164         ht = alloc->calloc(alloc->state, 1, cds_lfht_size);
 165         urcu_posix_assert(ht);
 166
 167         ht->mm = mm;
 168         ht->alloc = alloc;
 169         ht->bucket_at = mm->bucket_at;
 170         ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
 171         ht->min_alloc_buckets_order =
 172                 cds_lfht_get_count_order_ulong(min_nr_alloc_buckets);
 173         ht->max_nr_buckets = max_nr_buckets;
 174
 175         return ht;
 176 }
 177
 178 #endif /* _URCU_RCULFHASH_INTERNAL_H */