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