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