Fix: relayd: don't call lttng_ht_destroy in RCU read-side C.S.
[lttng-tools.git] / src / common / hashtable / rculfhash-internal.h
CommitLineData
cd5376da
DG
1#ifndef URCU_RCULFHASH_INTERNAL_H
2#define URCU_RCULFHASH_INTERNAL_H
bec39940
DG
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
cd5376da
DG
27#include <stdio.h>
28
bec39940
DG
29#include "rculfhash.h"
30
31#ifdef DEBUG
32#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
33#else
cd5376da
DG
34#define dbg_printf(fmt, args...) \
35do { \
36 /* do nothing but check printf format */ \
37 if (0) \
38 printf("[debug rculfhash] " fmt, ## args); \
39} while (0)
bec39940
DG
40#endif
41
42#if (CAA_BITS_PER_LONG == 32)
43#define MAX_TABLE_ORDER 32
44#else
45#define MAX_TABLE_ORDER 64
46#endif
47
48#define MAX_CHUNK_TABLE (1UL << 10)
49
50#ifndef min
51#define min(a, b) ((a) < (b) ? (a) : (b))
52#endif
53
54#ifndef max
55#define max(a, b) ((a) > (b) ? (a) : (b))
56#endif
57
58struct ht_items_count;
59
60/*
61 * cds_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 */
69struct cds_lfht {
70 /* Initial configuration items */
71 unsigned long max_nr_buckets;
72 const struct cds_lfht_mm_type *mm; /* memory management plugin */
73 const struct rcu_flavor_struct *flavor; /* RCU flavor */
74
75 long count; /* global approximate item count */
76
77 /*
78 * We need to put the work threads offline (QSBR) when taking this
79 * mutex, because we use synchronize_rcu within this mutex critical
80 * section, which waits on read-side critical sections, and could
81 * therefore cause grace-period deadlock if we hold off RCU G.P.
82 * completion.
83 */
84 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
85 pthread_attr_t *resize_attr; /* Resize threads attributes */
86 unsigned int in_progress_resize, in_progress_destroy;
87 unsigned long resize_target;
88 int resize_initiated;
89
90 /*
91 * Variables needed for add and remove fast-paths.
92 */
93 int flags;
94 unsigned long min_alloc_buckets_order;
95 unsigned long min_nr_alloc_buckets;
96 struct ht_items_count *split_count; /* split item count */
97
98 /*
99 * Variables needed for the lookup, add and remove fast-paths.
100 */
101 unsigned long size; /* always a power of 2, shared (RCU) */
102 /*
103 * bucket_at pointer is kept here to skip the extra level of
104 * dereference needed to get to "mm" (this is a fast-path).
105 */
106 struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
107 unsigned long index);
108 /*
109 * Dynamic length "tbl_chunk" needs to be at the end of
110 * cds_lfht.
111 */
112 union {
113 /*
114 * Contains the per order-index-level bucket node table.
115 * The size of each bucket node table is half the number
116 * of hashes contained in this order (except for order 0).
117 * The minimum allocation buckets size parameter allows
118 * combining the bucket node arrays of the lowermost
119 * levels to improve cache locality for small index orders.
120 */
121 struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
122
123 /*
124 * Contains the bucket node chunks. The size of each
125 * bucket node chunk is ->min_alloc_size (we avoid to
126 * allocate chunks with different size). Chunks improve
127 * cache locality for small index orders, and are more
128 * friendly with environments where allocation of large
129 * contiguous memory areas is challenging due to memory
130 * fragmentation concerns or inability to use virtual
131 * memory addressing.
132 */
133 struct cds_lfht_node *tbl_chunk[0];
134
135 /*
136 * Memory mapping with room for all possible buckets.
137 * Their memory is allocated when needed.
138 */
139 struct cds_lfht_node *tbl_mmap;
140 };
141 /*
142 * End of variables needed for the lookup, add and remove
143 * fast-paths.
144 */
145};
146
147extern unsigned int cds_lfht_fls_ulong(unsigned long x);
148extern int cds_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
162static inline
163struct cds_lfht *__default_alloc_cds_lfht(
164 const struct cds_lfht_mm_type *mm,
165 unsigned long cds_lfht_size,
166 unsigned long min_nr_alloc_buckets,
167 unsigned long max_nr_buckets)
168{
169 struct cds_lfht *ht;
170
171 ht = calloc(1, cds_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 cds_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 /* _URCU_RCULFHASH_INTERNAL_H */
This page took 0.061594 seconds and 4 git commands to generate.