liblttng-ust/rculfhash-internal.h

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