1 #ifndef _LTTNG_UST_RCULFHASH_INTERNAL_H
2 #define _LTTNG_UST_RCULFHASH_INTERNAL_H
5 * liblttng-ust/rculfhash-internal.h
7 * Internal header for Lock-Free RCU Hash Table
9 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
10 * Copyright 2011 - Lai Jiangshan <laijs@cn.fujitsu.com>
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.
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.
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
27 #include "rculfhash.h"
34 #define dbg_printf(fmt, args...) printf("[debug lttng-ust rculfhash] " fmt, ## args)
36 #define dbg_printf(fmt, args...) \
38 /* do nothing but check printf format */ \
40 printf("[debug lttng-ust rculfhash] " fmt, ## args); \
44 #if (CAA_BITS_PER_LONG == 32)
45 #define MAX_TABLE_ORDER 32
47 #define MAX_TABLE_ORDER 64
50 #define MAX_CHUNK_TABLE (1UL << 10)
53 #define min(a, b) ((a) < (b) ? (a) : (b))
57 #define max(a, b) ((a) > (b) ? (a) : (b))
61 * lttng_ust_lfht: Top-level data structure representing a lock-free hash
62 * table. Defined in the implementation file to make it be an opaque
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.
69 struct lttng_ust_lfht
{
70 /* Initial configuration items */
71 unsigned long max_nr_buckets
;
72 const struct lttng_ust_lfht_mm_type
*mm
; /* memory management plugin */
73 const struct rcu_flavor_struct
*flavor
; /* RCU flavor */
76 * We need to put the work threads offline (QSBR) when taking this
77 * mutex, because we use synchronize_rcu within this mutex critical
78 * section, which waits on read-side critical sections, and could
79 * therefore cause grace-period deadlock if we hold off RCU G.P.
82 pthread_mutex_t resize_mutex
; /* resize mutex: add/del mutex */
83 unsigned int in_progress_destroy
;
84 unsigned long resize_target
;
88 * Variables needed for add and remove fast-paths.
91 unsigned long min_alloc_buckets_order
;
92 unsigned long min_nr_alloc_buckets
;
95 * Variables needed for the lookup, add and remove fast-paths.
97 unsigned long size
; /* always a power of 2, shared (RCU) */
99 * bucket_at pointer is kept here to skip the extra level of
100 * dereference needed to get to "mm" (this is a fast-path).
102 struct lttng_ust_lfht_node
*(*bucket_at
)(struct lttng_ust_lfht
*ht
,
103 unsigned long index
);
105 * Dynamic length "tbl_chunk" needs to be at the end of
110 * Contains the per order-index-level bucket node table.
111 * The size of each bucket node table is half the number
112 * of hashes contained in this order (except for order 0).
113 * The minimum allocation buckets size parameter allows
114 * combining the bucket node arrays of the lowermost
115 * levels to improve cache locality for small index orders.
117 struct lttng_ust_lfht_node
*tbl_order
[MAX_TABLE_ORDER
];
120 * Contains the bucket node chunks. The size of each
121 * bucket node chunk is ->min_alloc_size (we avoid to
122 * allocate chunks with different size). Chunks improve
123 * cache locality for small index orders, and are more
124 * friendly with environments where allocation of large
125 * contiguous memory areas is challenging due to memory
126 * fragmentation concerns or inability to use virtual
129 struct lttng_ust_lfht_node
*tbl_chunk
[0];
132 * Memory mapping with room for all possible buckets.
133 * Their memory is allocated when needed.
135 struct lttng_ust_lfht_node
*tbl_mmap
;
138 * End of variables needed for the lookup, add and remove
144 extern unsigned int lttng_ust_lfht_fls_ulong(unsigned long x
);
146 extern int lttng_ust_lfht_get_count_order_u32(uint32_t x
);
148 extern int lttng_ust_lfht_get_count_order_ulong(unsigned long x
);
151 #define poison_free(ptr) \
154 memset(ptr, 0x42, sizeof(*(ptr))); \
159 #define poison_free(ptr) free(ptr)
163 struct lttng_ust_lfht
*__default_alloc_lttng_ust_lfht(
164 const struct lttng_ust_lfht_mm_type
*mm
,
165 unsigned long lttng_ust_lfht_size
,
166 unsigned long min_nr_alloc_buckets
,
167 unsigned long max_nr_buckets
)
169 struct lttng_ust_lfht
*ht
;
171 ht
= calloc(1, lttng_ust_lfht_size
);
175 ht
->bucket_at
= mm
->bucket_at
;
176 ht
->min_nr_alloc_buckets
= min_nr_alloc_buckets
;
177 ht
->min_alloc_buckets_order
=
178 lttng_ust_lfht_get_count_order_ulong(min_nr_alloc_buckets
);
179 ht
->max_nr_buckets
= max_nr_buckets
;
184 #endif /* _LTTNG_UST_RCULFHASH_INTERNAL_H */