Commit | Line | Data |
---|---|---|
acdb82a2 MJ |
1 | // SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> |
2 | // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com> | |
3 | // | |
4 | // SPDX-License-Identifier: LGPL-2.1-or-later | |
5 | ||
0b6aa001 LJ |
6 | #ifndef _URCU_RCULFHASH_INTERNAL_H |
7 | #define _URCU_RCULFHASH_INTERNAL_H | |
8 | ||
9 | /* | |
0b6aa001 | 10 | * Internal header for Lock-Free RCU Hash Table |
0b6aa001 LJ |
11 | */ |
12 | ||
01477510 | 13 | #include <urcu/assert.h> |
0b6aa001 | 14 | #include <urcu/rculfhash.h> |
87fbf522 | 15 | #include <stdio.h> |
6bcce235 | 16 | #include <stdlib.h> |
0b6aa001 | 17 | |
b047e7a7 MD |
18 | #include "workqueue.h" |
19 | ||
0b6aa001 LJ |
20 | #ifdef DEBUG |
21 | #define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args) | |
22 | #else | |
87fbf522 MD |
23 | #define dbg_printf(fmt, args...) \ |
24 | do { \ | |
25 | /* do nothing but check printf format */ \ | |
26 | if (0) \ | |
27 | printf("[debug rculfhash] " fmt, ## args); \ | |
28 | } while (0) | |
0b6aa001 LJ |
29 | #endif |
30 | ||
31 | #if (CAA_BITS_PER_LONG == 32) | |
32 | #define MAX_TABLE_ORDER 32 | |
33 | #else | |
34 | #define MAX_TABLE_ORDER 64 | |
35 | #endif | |
36 | ||
308d1cb3 LJ |
37 | #define MAX_CHUNK_TABLE (1UL << 10) |
38 | ||
0b6aa001 LJ |
39 | #ifndef min |
40 | #define min(a, b) ((a) < (b) ? (a) : (b)) | |
41 | #endif | |
42 | ||
43 | #ifndef max | |
44 | #define max(a, b) ((a) > (b) ? (a) : (b)) | |
45 | #endif | |
46 | ||
47 | struct ht_items_count; | |
48 | ||
49 | /* | |
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 | |
52 | * cookie to users. | |
f45b03e0 MD |
53 | * |
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. | |
0b6aa001 LJ |
57 | */ |
58 | struct cds_lfht { | |
f45b03e0 MD |
59 | /* Initial configuration items */ |
60 | unsigned long max_nr_buckets; | |
61 | const struct cds_lfht_mm_type *mm; /* memory management plugin */ | |
ac735254 | 62 | const struct cds_lfht_alloc *alloc; /* memory allocator for mm */ |
f45b03e0 MD |
63 | const struct rcu_flavor_struct *flavor; /* RCU flavor */ |
64 | ||
65 | long count; /* global approximate item count */ | |
66 | ||
67 | /* | |
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. | |
72 | * completion. | |
73 | */ | |
b047e7a7 MD |
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; | |
d0ec0ed2 | 77 | unsigned int in_progress_destroy; |
f45b03e0 MD |
78 | unsigned long resize_target; |
79 | int resize_initiated; | |
b047e7a7 | 80 | struct urcu_work destroy_work; |
f45b03e0 MD |
81 | |
82 | /* | |
83 | * Variables needed for add and remove fast-paths. | |
84 | */ | |
85 | int flags; | |
86 | unsigned long min_alloc_buckets_order; | |
87 | unsigned long min_nr_alloc_buckets; | |
88 | struct ht_items_count *split_count; /* split item count */ | |
89 | ||
0b6aa001 | 90 | /* |
3fd3f554 | 91 | * Variables needed for the lookup, add and remove fast-paths. |
0b6aa001 | 92 | */ |
3fd3f554 | 93 | unsigned long size; /* always a power of 2, shared (RCU) */ |
f45b03e0 MD |
94 | /* |
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). | |
97 | */ | |
98 | struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, | |
99 | unsigned long index); | |
100 | /* | |
101 | * Dynamic length "tbl_chunk" needs to be at the end of | |
102 | * cds_lfht. | |
103 | */ | |
0b6aa001 LJ |
104 | union { |
105 | /* | |
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. | |
112 | */ | |
113 | struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER]; | |
308d1cb3 LJ |
114 | |
115 | /* | |
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 | |
123 | * memory addressing. | |
124 | */ | |
125 | struct cds_lfht_node *tbl_chunk[0]; | |
b0b55251 LJ |
126 | |
127 | /* | |
128 | * Memory mapping with room for all possible buckets. | |
129 | * Their memory is allocated when needed. | |
130 | */ | |
131 | struct cds_lfht_node *tbl_mmap; | |
0b6aa001 | 132 | }; |
3fd3f554 | 133 | /* |
f45b03e0 MD |
134 | * End of variables needed for the lookup, add and remove |
135 | * fast-paths. | |
3fd3f554 | 136 | */ |
0b6aa001 LJ |
137 | }; |
138 | ||
5bc6b66f MD |
139 | extern unsigned int cds_lfht_fls_ulong(unsigned long x); |
140 | extern int cds_lfht_get_count_order_ulong(unsigned long x); | |
0b6aa001 LJ |
141 | |
142 | #ifdef POISON_FREE | |
ac735254 | 143 | #define poison_free(alloc, ptr) \ |
0b6aa001 LJ |
144 | do { \ |
145 | if (ptr) { \ | |
146 | memset(ptr, 0x42, sizeof(*(ptr))); \ | |
ac735254 | 147 | alloc->free(alloc->state, ptr); \ |
0b6aa001 LJ |
148 | } \ |
149 | } while (0) | |
150 | #else | |
ac735254 | 151 | #define poison_free(alloc, ptr) alloc->free(alloc->state, ptr) |
0b6aa001 LJ |
152 | #endif |
153 | ||
1228af1c LJ |
154 | static inline |
155 | struct cds_lfht *__default_alloc_cds_lfht( | |
156 | const struct cds_lfht_mm_type *mm, | |
ac735254 | 157 | const struct cds_lfht_alloc *alloc, |
1228af1c LJ |
158 | unsigned long cds_lfht_size, |
159 | unsigned long min_nr_alloc_buckets, | |
160 | unsigned long max_nr_buckets) | |
161 | { | |
162 | struct cds_lfht *ht; | |
163 | ||
ac735254 | 164 | ht = alloc->calloc(alloc->state, 1, cds_lfht_size); |
01477510 | 165 | urcu_posix_assert(ht); |
1228af1c LJ |
166 | |
167 | ht->mm = mm; | |
ac735254 | 168 | ht->alloc = alloc; |
1228af1c LJ |
169 | ht->bucket_at = mm->bucket_at; |
170 | ht->min_nr_alloc_buckets = min_nr_alloc_buckets; | |
171 | ht->min_alloc_buckets_order = | |
5bc6b66f | 172 | cds_lfht_get_count_order_ulong(min_nr_alloc_buckets); |
1228af1c LJ |
173 | ht->max_nr_buckets = max_nr_buckets; |
174 | ||
175 | return ht; | |
176 | } | |
177 | ||
0b6aa001 | 178 | #endif /* _URCU_RCULFHASH_INTERNAL_H */ |