1 #ifndef _URCU_RCUJA_INTERNAL_H
2 #define _URCU_RCUJA_INTERNAL_H
5 * rcuja/rcuja-internal.h
7 * Userspace RCU library - RCU Judy Array Internal Header
9 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public
13 * License as published by the Free Software Foundation; either
14 * version 2.1 of the License, or (at your option) any later version.
16 * This library is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Lesser General Public License for more details.
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with this library; if not, write to the Free Software
23 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
31 #include <urcu/rculfhash.h>
34 * Number of least significant pointer bits reserved to represent the
37 #define JA_TYPE_BITS 3
38 #define JA_TYPE_MAX_NR (1UL << JA_TYPE_BITS)
39 #define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1)
40 #define JA_PTR_MASK (~JA_TYPE_MASK)
42 #define JA_ENTRY_PER_NODE 256UL
43 #define JA_LOG2_BITS_PER_BYTE 3U
44 #define JA_BITS_PER_BYTE (1U << JA_LOG2_BITS_PER_BYTE)
46 #define JA_POOL_1D_MASK ((JA_BITS_PER_BYTE - 1) << JA_TYPE_BITS)
47 #define JA_POOL_2D_MASK (JA_POOL_1D_MASK << JA_LOG2_BITS_PER_BYTE)
49 #define JA_MAX_DEPTH 9 /* Maximum depth, including leafs */
52 * Entry for NULL node is at index 8 of the table. It is never encoded
55 #define NODE_INDEX_NULL 8
58 * Number of removals needed on a fallback node before we try to shrink
61 #define JA_FALLBACK_REMOVAL_COUNT 8
63 /* Never declared. Opaque type used to store flagged node pointers. */
64 struct cds_ja_inode_flag
;
68 * Shadow node contains mutex and call_rcu head associated with a node.
70 struct cds_ja_shadow_node
{
71 struct cds_lfht_node ht_node
; /* hash table node */
72 struct cds_ja_inode_flag
*node_flag
; /* reverse mapping and hash table key */
74 * mutual exclusion on all nodes belonging to the same tree
75 * position (e.g. both nodes before and after recompaction
78 pthread_mutex_t
*lock
;
79 unsigned int nr_child
; /* number of children in node */
80 struct rcu_head head
; /* for deferred node and shadow node reclaim */
81 int fallback_removal_count
; /* removals left keeping fallback */
82 int level
; /* level in the tree */
83 struct cds_ja
*ja
; /* toplevel judy array */
87 struct cds_ja_inode_flag
*root
;
88 unsigned int tree_depth
;
91 * We use a hash table to associate node keys to their
92 * respective shadow node. This helps reducing lookup hot path
93 * cache footprint, especially for very small nodes.
96 unsigned long nr_fallback
; /* Number of fallback nodes used */
99 unsigned long node_fallback_count_distribution
[JA_ENTRY_PER_NODE
];
100 unsigned long nr_nodes_allocated
, nr_nodes_freed
;
104 struct cds_ja_inode_flag
*ja_node_flag(struct cds_ja_inode
*node
,
107 assert(type
< (1UL << JA_TYPE_BITS
));
108 return (struct cds_ja_inode_flag
*) (((unsigned long) node
) | type
);
112 struct cds_ja_inode_flag
*ja_node_flag_pool_1d(struct cds_ja_inode
*node
,
113 unsigned long type
, unsigned long bitsel
)
115 assert(type
< (1UL << JA_TYPE_BITS
));
116 assert(bitsel
< JA_BITS_PER_BYTE
);
117 return (struct cds_ja_inode_flag
*) (((unsigned long) node
) | (bitsel
<< JA_TYPE_BITS
) | type
);
121 struct cds_ja_inode_flag
*ja_node_flag_pool_2d(struct cds_ja_inode
*node
,
122 unsigned long type
, unsigned int bitsel
[2])
124 assert(type
< (1UL << JA_TYPE_BITS
));
125 assert(bitsel
[0] < JA_BITS_PER_BYTE
);
126 assert(bitsel
[1] < JA_BITS_PER_BYTE
);
127 return (struct cds_ja_inode_flag
*) (((unsigned long) node
) | (bitsel
[0] << (JA_TYPE_BITS
+ JA_LOG2_BITS_PER_BYTE
)) | (bitsel
[1] << JA_TYPE_BITS
) | type
);
131 unsigned long ja_node_pool_1d_bitsel(struct cds_ja_inode_flag
*node
)
133 return ((unsigned long) node
& JA_POOL_1D_MASK
) >> JA_TYPE_BITS
;
137 void ja_node_pool_2d_bitsel(struct cds_ja_inode_flag
*node
, unsigned long *bits
)
139 bits
[0] = ((unsigned long) node
& JA_POOL_2D_MASK
) >> (JA_TYPE_BITS
+ JA_LOG2_BITS_PER_BYTE
);
140 bits
[1] = ((unsigned long) node
& JA_POOL_1D_MASK
) >> JA_TYPE_BITS
;
143 /* Hardcoded pool indexes for fast path */
144 #define RCU_JA_POOL_IDX_5 5
145 #define RCU_JA_POOL_IDX_6 6
147 struct cds_ja_inode
*ja_node_ptr(struct cds_ja_inode_flag
*node
)
149 unsigned long v
, type_idx
;
152 return NULL
; /* RCU_JA_NULL */
153 v
= (unsigned long) node
;
154 type_idx
= v
& JA_TYPE_MASK
;
157 case RCU_JA_POOL_IDX_5
:
158 v
&= ~(JA_POOL_1D_MASK
| JA_TYPE_MASK
);
160 case RCU_JA_POOL_IDX_6
:
161 v
&= ~(JA_POOL_2D_MASK
| JA_POOL_1D_MASK
| JA_TYPE_MASK
);
164 /* RCU_JA_LINEAR or RCU_JA_PIGEON */
168 return (struct cds_ja_node
*) v
;
171 __attribute__((visibility("protected")))
172 unsigned long ja_node_type(struct cds_ja_inode_flag
*node
);
174 __attribute__((visibility("protected")))
175 void rcuja_free_all_children(struct cds_ja_shadow_node
*shadow_node
,
176 struct cds_ja_inode_flag
*node_flag
,
177 void (*rcu_free_node
)(struct cds_ja_node
*node
));
179 __attribute__((visibility("protected")))
180 struct cds_ja_shadow_node
*rcuja_shadow_lookup_lock(struct cds_lfht
*ht
,
181 struct cds_ja_inode_flag
*node_flag
);
183 __attribute__((visibility("protected")))
184 void rcuja_shadow_unlock(struct cds_ja_shadow_node
*shadow_node
);
186 __attribute__((visibility("protected")))
187 struct cds_ja_shadow_node
*rcuja_shadow_set(struct cds_lfht
*ht
,
188 struct cds_ja_inode_flag
*new_node_flag
,
189 struct cds_ja_shadow_node
*inherit_from
,
190 struct cds_ja
*ja
, int level
);
192 /* rcuja_shadow_clear flags */
194 RCUJA_SHADOW_CLEAR_FREE_NODE
= (1U << 0),
195 RCUJA_SHADOW_CLEAR_FREE_LOCK
= (1U << 1),
198 __attribute__((visibility("protected")))
199 int rcuja_shadow_clear(struct cds_lfht
*ht
,
200 struct cds_ja_inode_flag
*node_flag
,
201 struct cds_ja_shadow_node
*shadow_node
,
204 __attribute__((visibility("protected")))
205 void rcuja_shadow_prune(struct cds_lfht
*ht
,
207 void (*rcu_free_node
)(struct cds_ja_node
*node
));
209 __attribute__((visibility("protected")))
210 struct cds_lfht
*rcuja_create_ht(const struct rcu_flavor_struct
*flavor
);
212 __attribute__((visibility("protected")))
213 int rcuja_delete_ht(struct cds_lfht
*ht
);
215 __attribute__((visibility("protected")))
216 void free_cds_ja_node(struct cds_ja
*ja
, struct cds_ja_inode
*node
);
219 * Iterate through duplicates returned by cds_ja_lookup*()
220 * Receives a struct cds_ja_node * as parameter, which is used as start
221 * of duplicate list and loop cursor.
223 #define cds_ja_for_each_duplicate(pos) \
224 for (; (pos) != NULL; (pos) = (pos)->next)
227 * Iterate through duplicates returned by cds_ja_lookup*()
228 * Safe against removal of entries during traversal.
230 #define cds_ja_for_each_duplicate_safe(_pos, _next) \
231 for (; (_pos) != NULL ? ((_next) = (_pos)->next, 1) : 0; \
240 #if defined(_syscall0)
241 _syscall0(pid_t
, gettid
)
242 #elif defined(__NR_gettid)
243 static inline pid_t
gettid(void)
245 return syscall(__NR_gettid
);
248 #warning "use pid as tid"
249 static inline pid_t
gettid(void)
256 #define dbg_printf(fmt, args...) \
257 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
258 (unsigned long) gettid(), __func__, \
259 __FILE__, __LINE__, ## args)
261 #define dbg_printf(fmt, args...) \
263 /* do nothing but check printf format */ \
265 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
266 (unsigned long) gettid(), __func__, \
267 __FILE__, __LINE__, ## args); \
271 #endif /* _URCU_RCUJA_INTERNAL_H */