rculfhash-internal.h

   1 #ifndef _URCU_RCULFHASH_INTERNAL_H
   2 #define _URCU_RCULFHASH_INTERNAL_H
   3
   4 /*
   5  * urcu/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 <urcu/rculfhash.h>
  28
  29 #ifdef DEBUG
  30 #define dbg_printf(fmt, args...)     printf("[debug rculfhash] " fmt, ## args)
  31 #else
  32 #define dbg_printf(fmt, args...)
  33 #endif
  34
  35 #if (CAA_BITS_PER_LONG == 32)
  36 #define MAX_TABLE_ORDER                 32
  37 #else
  38 #define MAX_TABLE_ORDER                 64
  39 #endif
  40
  41 #define MAX_CHUNK_TABLE                 (1UL << 10)
  42
  43 #ifndef min
  44 #define min(a, b)       ((a) < (b) ? (a) : (b))
  45 #endif
  46
  47 #ifndef max
  48 #define max(a, b)       ((a) > (b) ? (a) : (b))
  49 #endif
  50
  51 struct ht_items_count;
  52
  53 /*
  54  * cds_lfht: Top-level data structure representing a lock-free hash
  55  * table. Defined in the implementation file to make it be an opaque
  56  * cookie to users.
  57  */
  58 struct cds_lfht {
  59         /*
  60          * Variables needed for the lookup, add and remove fast-paths.
  61          */
  62         unsigned long size;     /* always a power of 2, shared (RCU) */
  63         union {
  64                 /*
  65                  * Contains the per order-index-level bucket node table.
  66                  * The size of each bucket node table is half the number
  67                  * of hashes contained in this order (except for order 0).
  68                  * The minimum allocation buckets size parameter allows
  69                  * combining the bucket node arrays of the lowermost
  70                  * levels to improve cache locality for small index orders.
  71                  */
  72                 struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
  73
  74                 /*
  75                  * Contains the bucket node chunks. The size of each
  76                  * bucket node chunk is ->min_alloc_size (we avoid to
  77                  * allocate chunks with different size). Chunks improve
  78                  * cache locality for small index orders, and are more
  79                  * friendly with environments where allocation of large
  80                  * contiguous memory areas is challenging due to memory
  81                  * fragmentation concerns or inability to use virtual
  82                  * memory addressing.
  83                  */
  84                 struct cds_lfht_node *tbl_chunk[0];
  85
  86                 /*
  87                  * Memory mapping with room for all possible buckets.
  88                  * Their memory is allocated when needed.
  89                  */
  90                 struct cds_lfht_node *tbl_mmap;
  91         };
  92         /*
  93          * bucket_at pointer is kept here to skip the extra level of
  94          * dereference needed to get to "mm" (this is a fast-path).
  95          */
  96         struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
  97                         unsigned long index);
  98         /*
  99          * End of variables needed for lookup fast-path.
 100          */
 101
 102         struct ht_items_count *split_count;     /* split item count */
 103         /*
 104          * End of variables needed for add/remove fast-path.
 105          */
 106
 107         /* Initial configuration items */
 108         int flags;
 109         unsigned long min_alloc_buckets_order;
 110         unsigned long min_nr_alloc_buckets;
 111         unsigned long max_nr_buckets;
 112         const struct cds_lfht_mm_type *mm;      /* memory management plugin */
 113         const struct rcu_flavor_struct *flavor; /* RCU flavor */
 114
 115         long count;                     /* global approximate item count */
 116
 117         /*
 118          * We need to put the work threads offline (QSBR) when taking this
 119          * mutex, because we use synchronize_rcu within this mutex critical
 120          * section, which waits on read-side critical sections, and could
 121          * therefore cause grace-period deadlock if we hold off RCU G.P.
 122          * completion.
 123          */
 124         pthread_mutex_t resize_mutex;   /* resize mutex: add/del mutex */
 125         pthread_attr_t *resize_attr;    /* Resize threads attributes */
 126         unsigned int in_progress_resize, in_progress_destroy;
 127         unsigned long resize_target;
 128         int resize_initiated;
 129 };
 130
 131 extern unsigned int fls_ulong(unsigned long x);
 132 extern int get_count_order_ulong(unsigned long x);
 133
 134 #ifdef POISON_FREE
 135 #define poison_free(ptr)                                        \
 136         do {                                                    \
 137                 if (ptr) {                                      \
 138                         memset(ptr, 0x42, sizeof(*(ptr)));      \
 139                         free(ptr);                              \
 140                 }                                               \
 141         } while (0)
 142 #else
 143 #define poison_free(ptr)        free(ptr)
 144 #endif
 145
 146 #endif /* _URCU_RCULFHASH_INTERNAL_H */