liblttng-ust/rculfhash-internal.h

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