Commit | Line | Data |
---|---|---|
0b6aa001 LJ |
1 | #ifndef _URCU_RCULFHASH_INTERNAL_H |
2 | #define _URCU_RCULFHASH_INTERNAL_H | |
3 | ||
4 | /* | |
5 | * urcu/rculfhash-internal.h | |
6 | * | |
7 | * Internal header for Lock-Free RCU Hash Table | |
8 | * | |
9 | * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
10 | * Copyright 2011 - Lai Jiangshan <laijs@cn.fujitsu.com> | |
11 | * | |
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. | |
16 | * | |
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. | |
21 | * | |
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 | |
25 | */ | |
26 | ||
27 | #include <urcu/rculfhash.h> | |
28 | ||
29 | #ifdef DEBUG | |
30 | #define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args) | |
31 | #else | |
32 | #define dbg_printf(fmt, args...) | |
33 | #endif | |
34 | ||
35 | #if (CAA_BITS_PER_LONG == 32) | |
36 | #define MAX_TABLE_ORDER 32 | |
37 | #else | |
38 | #define MAX_TABLE_ORDER 64 | |
39 | #endif | |
40 | ||
308d1cb3 LJ |
41 | #define MAX_CHUNK_TABLE (1UL << 10) |
42 | ||
0b6aa001 LJ |
43 | #ifndef min |
44 | #define min(a, b) ((a) < (b) ? (a) : (b)) | |
45 | #endif | |
46 | ||
47 | #ifndef max | |
48 | #define max(a, b) ((a) > (b) ? (a) : (b)) | |
49 | #endif | |
50 | ||
51 | struct ht_items_count; | |
52 | ||
53 | /* | |
54 | * cds_lfht: Top-level data structure representing a lock-free hash | |
55 | * table. Defined in the implementation file to make it be an opaque | |
56 | * cookie to users. | |
57 | */ | |
58 | struct cds_lfht { | |
0b6aa001 | 59 | /* |
3fd3f554 | 60 | * Variables needed for the lookup, add and remove fast-paths. |
0b6aa001 | 61 | */ |
3fd3f554 | 62 | unsigned long size; /* always a power of 2, shared (RCU) */ |
0b6aa001 LJ |
63 | union { |
64 | /* | |
65 | * Contains the per order-index-level bucket node table. | |
66 | * The size of each bucket node table is half the number | |
67 | * of hashes contained in this order (except for order 0). | |
68 | * The minimum allocation buckets size parameter allows | |
69 | * combining the bucket node arrays of the lowermost | |
70 | * levels to improve cache locality for small index orders. | |
71 | */ | |
72 | struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER]; | |
308d1cb3 LJ |
73 | |
74 | /* | |
75 | * Contains the bucket node chunks. The size of each | |
76 | * bucket node chunk is ->min_alloc_size (we avoid to | |
77 | * allocate chunks with different size). Chunks improve | |
78 | * cache locality for small index orders, and are more | |
79 | * friendly with environments where allocation of large | |
80 | * contiguous memory areas is challenging due to memory | |
81 | * fragmentation concerns or inability to use virtual | |
82 | * memory addressing. | |
83 | */ | |
84 | struct cds_lfht_node *tbl_chunk[0]; | |
b0b55251 LJ |
85 | |
86 | /* | |
87 | * Memory mapping with room for all possible buckets. | |
88 | * Their memory is allocated when needed. | |
89 | */ | |
90 | struct cds_lfht_node *tbl_mmap; | |
0b6aa001 | 91 | }; |
3fd3f554 MD |
92 | /* |
93 | * bucket_at pointer is kept here to skip the extra level of | |
94 | * dereference needed to get to "mm" (this is a fast-path). | |
95 | */ | |
96 | struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, | |
97 | unsigned long index); | |
98 | /* | |
99 | * End of variables needed for lookup fast-path. | |
100 | */ | |
101 | ||
102 | struct ht_items_count *split_count; /* split item count */ | |
103 | /* | |
104 | * End of variables needed for add/remove fast-path. | |
105 | */ | |
106 | ||
107 | /* Initial configuration items */ | |
108 | int flags; | |
109 | unsigned long min_alloc_buckets_order; | |
110 | unsigned long min_nr_alloc_buckets; | |
111 | unsigned long max_nr_buckets; | |
112 | const struct cds_lfht_mm_type *mm; /* memory management plugin */ | |
113 | const struct rcu_flavor_struct *flavor; /* RCU flavor */ | |
114 | ||
115 | long count; /* global approximate item count */ | |
116 | ||
117 | /* | |
118 | * We need to put the work threads offline (QSBR) when taking this | |
119 | * mutex, because we use synchronize_rcu within this mutex critical | |
120 | * section, which waits on read-side critical sections, and could | |
121 | * therefore cause grace-period deadlock if we hold off RCU G.P. | |
122 | * completion. | |
123 | */ | |
124 | pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */ | |
125 | pthread_attr_t *resize_attr; /* Resize threads attributes */ | |
126 | unsigned int in_progress_resize, in_progress_destroy; | |
127 | unsigned long resize_target; | |
128 | int resize_initiated; | |
0b6aa001 LJ |
129 | }; |
130 | ||
131 | extern unsigned int fls_ulong(unsigned long x); | |
132 | extern int get_count_order_ulong(unsigned long x); | |
133 | ||
134 | #ifdef POISON_FREE | |
135 | #define poison_free(ptr) \ | |
136 | do { \ | |
137 | if (ptr) { \ | |
138 | memset(ptr, 0x42, sizeof(*(ptr))); \ | |
139 | free(ptr); \ | |
140 | } \ | |
141 | } while (0) | |
142 | #else | |
143 | #define poison_free(ptr) free(ptr) | |
144 | #endif | |
145 | ||
146 | #endif /* _URCU_RCULFHASH_INTERNAL_H */ |