Commit | Line | Data |
---|---|---|
10544ee8 | 1 | /* |
c0c0989a | 2 | * SPDX-License-Identifier: LGPL-2.1-or-later |
10544ee8 | 3 | * |
c0c0989a MJ |
4 | * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> |
5 | * Copyright 2011 Lai Jiangshan <laijs@cn.fujitsu.com> | |
10544ee8 | 6 | * |
c0c0989a | 7 | * Internal header for Lock-Free RCU Hash Table |
10544ee8 MD |
8 | */ |
9 | ||
c0c0989a MJ |
10 | #ifndef _LTTNG_UST_RCULFHASH_INTERNAL_H |
11 | #define _LTTNG_UST_RCULFHASH_INTERNAL_H | |
12 | ||
10544ee8 MD |
13 | #include "rculfhash.h" |
14 | #include <stdio.h> | |
15 | #include <stdlib.h> | |
16 | #include <assert.h> | |
17 | ||
18 | #ifdef DEBUG | |
19 | #define dbg_printf(fmt, args...) printf("[debug lttng-ust rculfhash] " fmt, ## args) | |
20 | #else | |
21 | #define dbg_printf(fmt, args...) \ | |
22 | do { \ | |
23 | /* do nothing but check printf format */ \ | |
24 | if (0) \ | |
25 | printf("[debug lttng-ust rculfhash] " fmt, ## args); \ | |
26 | } while (0) | |
27 | #endif | |
28 | ||
29 | #if (CAA_BITS_PER_LONG == 32) | |
30 | #define MAX_TABLE_ORDER 32 | |
31 | #else | |
32 | #define MAX_TABLE_ORDER 64 | |
33 | #endif | |
34 | ||
35 | #define MAX_CHUNK_TABLE (1UL << 10) | |
36 | ||
37 | #ifndef min | |
38 | #define min(a, b) ((a) < (b) ? (a) : (b)) | |
39 | #endif | |
40 | ||
41 | #ifndef max | |
42 | #define max(a, b) ((a) > (b) ? (a) : (b)) | |
43 | #endif | |
44 | ||
45 | /* | |
46 | * lttng_ust_lfht: Top-level data structure representing a lock-free hash | |
47 | * table. Defined in the implementation file to make it be an opaque | |
48 | * cookie to users. | |
49 | * | |
50 | * The fields used in fast-paths are placed near the end of the | |
51 | * structure, because we need to have a variable-sized union to contain | |
52 | * the mm plugin fields, which are used in the fast path. | |
53 | */ | |
54 | struct lttng_ust_lfht { | |
55 | /* Initial configuration items */ | |
56 | unsigned long max_nr_buckets; | |
57 | const struct lttng_ust_lfht_mm_type *mm; /* memory management plugin */ | |
58 | const struct rcu_flavor_struct *flavor; /* RCU flavor */ | |
59 | ||
60 | /* | |
61 | * We need to put the work threads offline (QSBR) when taking this | |
62 | * mutex, because we use synchronize_rcu within this mutex critical | |
63 | * section, which waits on read-side critical sections, and could | |
64 | * therefore cause grace-period deadlock if we hold off RCU G.P. | |
65 | * completion. | |
66 | */ | |
67 | pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */ | |
68 | unsigned int in_progress_destroy; | |
69 | unsigned long resize_target; | |
70 | int resize_initiated; | |
71 | ||
72 | /* | |
73 | * Variables needed for add and remove fast-paths. | |
74 | */ | |
75 | int flags; | |
76 | unsigned long min_alloc_buckets_order; | |
77 | unsigned long min_nr_alloc_buckets; | |
78 | ||
79 | /* | |
80 | * Variables needed for the lookup, add and remove fast-paths. | |
81 | */ | |
82 | unsigned long size; /* always a power of 2, shared (RCU) */ | |
83 | /* | |
84 | * bucket_at pointer is kept here to skip the extra level of | |
85 | * dereference needed to get to "mm" (this is a fast-path). | |
86 | */ | |
87 | struct lttng_ust_lfht_node *(*bucket_at)(struct lttng_ust_lfht *ht, | |
88 | unsigned long index); | |
89 | /* | |
90 | * Dynamic length "tbl_chunk" needs to be at the end of | |
91 | * lttng_ust_lfht. | |
92 | */ | |
93 | union { | |
94 | /* | |
95 | * Contains the per order-index-level bucket node table. | |
96 | * The size of each bucket node table is half the number | |
97 | * of hashes contained in this order (except for order 0). | |
98 | * The minimum allocation buckets size parameter allows | |
99 | * combining the bucket node arrays of the lowermost | |
100 | * levels to improve cache locality for small index orders. | |
101 | */ | |
102 | struct lttng_ust_lfht_node *tbl_order[MAX_TABLE_ORDER]; | |
103 | ||
104 | /* | |
105 | * Contains the bucket node chunks. The size of each | |
106 | * bucket node chunk is ->min_alloc_size (we avoid to | |
107 | * allocate chunks with different size). Chunks improve | |
108 | * cache locality for small index orders, and are more | |
109 | * friendly with environments where allocation of large | |
110 | * contiguous memory areas is challenging due to memory | |
111 | * fragmentation concerns or inability to use virtual | |
112 | * memory addressing. | |
113 | */ | |
114 | struct lttng_ust_lfht_node *tbl_chunk[0]; | |
115 | ||
116 | /* | |
117 | * Memory mapping with room for all possible buckets. | |
118 | * Their memory is allocated when needed. | |
119 | */ | |
120 | struct lttng_ust_lfht_node *tbl_mmap; | |
121 | }; | |
122 | /* | |
123 | * End of variables needed for the lookup, add and remove | |
124 | * fast-paths. | |
125 | */ | |
126 | }; | |
127 | ||
1d18d519 MJ |
128 | extern unsigned int lttng_ust_lfht_fls_ulong(unsigned long x) |
129 | __attribute__((visibility("hidden"))); | |
ddabe860 | 130 | |
1d18d519 MJ |
131 | extern int lttng_ust_lfht_get_count_order_u32(uint32_t x) |
132 | __attribute__((visibility("hidden"))); | |
ddabe860 | 133 | |
1d18d519 MJ |
134 | extern int lttng_ust_lfht_get_count_order_ulong(unsigned long x) |
135 | __attribute__((visibility("hidden"))); | |
10544ee8 MD |
136 | |
137 | #ifdef POISON_FREE | |
138 | #define poison_free(ptr) \ | |
139 | do { \ | |
140 | if (ptr) { \ | |
141 | memset(ptr, 0x42, sizeof(*(ptr))); \ | |
142 | free(ptr); \ | |
143 | } \ | |
144 | } while (0) | |
145 | #else | |
146 | #define poison_free(ptr) free(ptr) | |
147 | #endif | |
148 | ||
149 | static inline | |
150 | struct lttng_ust_lfht *__default_alloc_lttng_ust_lfht( | |
151 | const struct lttng_ust_lfht_mm_type *mm, | |
152 | unsigned long lttng_ust_lfht_size, | |
153 | unsigned long min_nr_alloc_buckets, | |
154 | unsigned long max_nr_buckets) | |
155 | { | |
156 | struct lttng_ust_lfht *ht; | |
157 | ||
158 | ht = calloc(1, lttng_ust_lfht_size); | |
159 | assert(ht); | |
160 | ||
161 | ht->mm = mm; | |
162 | ht->bucket_at = mm->bucket_at; | |
163 | ht->min_nr_alloc_buckets = min_nr_alloc_buckets; | |
164 | ht->min_alloc_buckets_order = | |
165 | lttng_ust_lfht_get_count_order_ulong(min_nr_alloc_buckets); | |
166 | ht->max_nr_buckets = max_nr_buckets; | |
167 | ||
168 | return ht; | |
169 | } | |
170 | ||
171 | #endif /* _LTTNG_UST_RCULFHASH_INTERNAL_H */ |