1 // SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2 // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
4 // SPDX-License-Identifier: LGPL-2.1-or-later
6 #ifndef _URCU_RCULFHASH_INTERNAL_H
7 #define _URCU_RCULFHASH_INTERNAL_H
10 * Internal header for Lock-Free RCU Hash Table
13 #include <urcu/assert.h>
14 #include <urcu/rculfhash.h>
18 #include "workqueue.h"
21 #define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
23 #define dbg_printf(fmt, args...) \
25 /* do nothing but check printf format */ \
27 printf("[debug rculfhash] " fmt, ## args); \
31 #if (CAA_BITS_PER_LONG == 32)
32 #define MAX_TABLE_ORDER 32
34 #define MAX_TABLE_ORDER 64
37 #define MAX_CHUNK_TABLE (1UL << 10)
40 #define min(a, b) ((a) < (b) ? (a) : (b))
44 #define max(a, b) ((a) > (b) ? (a) : (b))
47 struct ht_items_count
;
50 * cds_lfht: Top-level data structure representing a lock-free hash
51 * table. Defined in the implementation file to make it be an opaque
54 * The fields used in fast-paths are placed near the end of the
55 * structure, because we need to have a variable-sized union to contain
56 * the mm plugin fields, which are used in the fast path.
59 /* Initial configuration items */
60 unsigned long max_nr_buckets
;
61 const struct cds_lfht_mm_type
*mm
; /* memory management plugin */
62 const struct cds_lfht_alloc
*alloc
; /* memory allocator for mm */
63 const struct rcu_flavor_struct
*flavor
; /* RCU flavor */
65 long count
; /* global approximate item count */
68 * We need to put the work threads offline (QSBR) when taking this
69 * mutex, because we use synchronize_rcu within this mutex critical
70 * section, which waits on read-side critical sections, and could
71 * therefore cause grace-period deadlock if we hold off RCU G.P.
74 pthread_mutex_t resize_mutex
; /* resize mutex: add/del mutex */
75 pthread_attr_t
*caller_resize_attr
; /* resize threads attributes from lfht_new caller */
76 pthread_attr_t resize_attr
;
77 unsigned int in_progress_destroy
;
78 unsigned long resize_target
;
80 struct urcu_work destroy_work
;
83 * Variables needed for add and remove fast-paths.
86 unsigned long min_alloc_buckets_order
;
87 unsigned long min_nr_alloc_buckets
;
88 struct ht_items_count
*split_count
; /* split item count */
91 * Variables needed for the lookup, add and remove fast-paths.
93 unsigned long size
; /* always a power of 2, shared (RCU) */
95 * bucket_at pointer is kept here to skip the extra level of
96 * dereference needed to get to "mm" (this is a fast-path).
98 struct cds_lfht_node
*(*bucket_at
)(struct cds_lfht
*ht
,
101 * Dynamic length "tbl_chunk" needs to be at the end of
106 * Contains the per order-index-level bucket node table.
107 * The size of each bucket node table is half the number
108 * of hashes contained in this order (except for order 0).
109 * The minimum allocation buckets size parameter allows
110 * combining the bucket node arrays of the lowermost
111 * levels to improve cache locality for small index orders.
113 struct cds_lfht_node
*tbl_order
[MAX_TABLE_ORDER
];
116 * Contains the bucket node chunks. The size of each
117 * bucket node chunk is ->min_alloc_size (we avoid to
118 * allocate chunks with different size). Chunks improve
119 * cache locality for small index orders, and are more
120 * friendly with environments where allocation of large
121 * contiguous memory areas is challenging due to memory
122 * fragmentation concerns or inability to use virtual
125 struct cds_lfht_node
*tbl_chunk
[0];
128 * Memory mapping with room for all possible buckets.
129 * Their memory is allocated when needed.
131 struct cds_lfht_node
*tbl_mmap
;
134 * End of variables needed for the lookup, add and remove
139 extern unsigned int cds_lfht_fls_ulong(unsigned long x
);
140 extern int cds_lfht_get_count_order_ulong(unsigned long x
);
143 #define poison_free(alloc, ptr) \
146 memset(ptr, 0x42, sizeof(*(ptr))); \
147 alloc->free(alloc->state, ptr); \
151 #define poison_free(alloc, ptr) alloc->free(alloc->state, ptr)
155 struct cds_lfht
*__default_alloc_cds_lfht(
156 const struct cds_lfht_mm_type
*mm
,
157 const struct cds_lfht_alloc
*alloc
,
158 unsigned long cds_lfht_size
,
159 unsigned long min_nr_alloc_buckets
,
160 unsigned long max_nr_buckets
)
164 ht
= alloc
->calloc(alloc
->state
, 1, cds_lfht_size
);
165 urcu_posix_assert(ht
);
169 ht
->bucket_at
= mm
->bucket_at
;
170 ht
->min_nr_alloc_buckets
= min_nr_alloc_buckets
;
171 ht
->min_alloc_buckets_order
=
172 cds_lfht_get_count_order_ulong(min_nr_alloc_buckets
);
173 ht
->max_nr_buckets
= max_nr_buckets
;
178 #endif /* _URCU_RCULFHASH_INTERNAL_H */