2 * SPDX-License-Identifier: LGPL-2.1-or-later
4 * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
5 * Copyright 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
7 * Internal header for Lock-Free RCU Hash Table
10 #ifndef _LTTNG_UST_RCULFHASH_INTERNAL_H
11 #define _LTTNG_UST_RCULFHASH_INTERNAL_H
13 #include "rculfhash.h"
20 #define dbg_printf(fmt, args...) printf("[debug lttng-ust rculfhash] " fmt, ## args)
22 #define dbg_printf(fmt, args...) \
24 /* do nothing but check printf format */ \
26 printf("[debug lttng-ust rculfhash] " fmt, ## args); \
30 #if (CAA_BITS_PER_LONG == 32)
31 #define MAX_TABLE_ORDER 32
33 #define MAX_TABLE_ORDER 64
36 #define MAX_CHUNK_TABLE (1UL << 10)
39 #define min(a, b) ((a) < (b) ? (a) : (b))
43 #define max(a, b) ((a) > (b) ? (a) : (b))
47 * lttng_ust_lfht: Top-level data structure representing a lock-free hash
48 * table. Defined in the implementation file to make it be an opaque
51 * The fields used in fast-paths are placed near the end of the
52 * structure, because we need to have a variable-sized union to contain
53 * the mm plugin fields, which are used in the fast path.
55 struct lttng_ust_lfht
{
56 /* Initial configuration items */
57 unsigned long max_nr_buckets
;
58 const struct lttng_ust_lfht_mm_type
*mm
; /* memory management plugin */
59 const struct rcu_flavor_struct
*flavor
; /* RCU flavor */
62 * We need to put the work threads offline (QSBR) when taking this
63 * mutex, because we use synchronize_rcu within this mutex critical
64 * section, which waits on read-side critical sections, and could
65 * therefore cause grace-period deadlock if we hold off RCU G.P.
68 pthread_mutex_t resize_mutex
; /* resize mutex: add/del mutex */
69 unsigned int in_progress_destroy
;
70 unsigned long resize_target
;
74 * Variables needed for add and remove fast-paths.
77 unsigned long min_alloc_buckets_order
;
78 unsigned long min_nr_alloc_buckets
;
81 * Variables needed for the lookup, add and remove fast-paths.
83 unsigned long size
; /* always a power of 2, shared (RCU) */
85 * bucket_at pointer is kept here to skip the extra level of
86 * dereference needed to get to "mm" (this is a fast-path).
88 struct lttng_ust_lfht_node
*(*bucket_at
)(struct lttng_ust_lfht
*ht
,
91 * Dynamic length "tbl_chunk" needs to be at the end of
96 * Contains the per order-index-level bucket node table.
97 * The size of each bucket node table is half the number
98 * of hashes contained in this order (except for order 0).
99 * The minimum allocation buckets size parameter allows
100 * combining the bucket node arrays of the lowermost
101 * levels to improve cache locality for small index orders.
103 struct lttng_ust_lfht_node
*tbl_order
[MAX_TABLE_ORDER
];
106 * Contains the bucket node chunks. The size of each
107 * bucket node chunk is ->min_alloc_size (we avoid to
108 * allocate chunks with different size). Chunks improve
109 * cache locality for small index orders, and are more
110 * friendly with environments where allocation of large
111 * contiguous memory areas is challenging due to memory
112 * fragmentation concerns or inability to use virtual
115 struct lttng_ust_lfht_node
*tbl_chunk
[0];
118 * Memory mapping with room for all possible buckets.
119 * Their memory is allocated when needed.
121 struct lttng_ust_lfht_node
*tbl_mmap
;
124 * End of variables needed for the lookup, add and remove
130 extern unsigned int lttng_ust_lfht_fls_ulong(unsigned long x
);
132 extern int lttng_ust_lfht_get_count_order_u32(uint32_t x
);
134 extern int lttng_ust_lfht_get_count_order_ulong(unsigned long x
);
137 #define poison_free(ptr) \
140 memset(ptr, 0x42, sizeof(*(ptr))); \
145 #define poison_free(ptr) free(ptr)
149 struct lttng_ust_lfht
*__default_alloc_lttng_ust_lfht(
150 const struct lttng_ust_lfht_mm_type
*mm
,
151 unsigned long lttng_ust_lfht_size
,
152 unsigned long min_nr_alloc_buckets
,
153 unsigned long max_nr_buckets
)
155 struct lttng_ust_lfht
*ht
;
157 ht
= calloc(1, lttng_ust_lfht_size
);
161 ht
->bucket_at
= mm
->bucket_at
;
162 ht
->min_nr_alloc_buckets
= min_nr_alloc_buckets
;
163 ht
->min_alloc_buckets_order
=
164 lttng_ust_lfht_get_count_order_ulong(min_nr_alloc_buckets
);
165 ht
->max_nr_buckets
= max_nr_buckets
;
170 #endif /* _LTTNG_UST_RCULFHASH_INTERNAL_H */