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_MAX_DEPTH 9 /* Maximum depth, including leafs */
49 * Entry for NULL node is at index 8 of the table. It is never encoded
52 #define NODE_INDEX_NULL 8
55 * Number of removals needed on a fallback node before we try to shrink
58 #define JA_FALLBACK_REMOVAL_COUNT 8
60 /* Never declared. Opaque type used to store flagged node pointers. */
61 struct cds_ja_inode_flag
;
65 * Shadow node contains mutex and call_rcu head associated with a node.
67 struct cds_ja_shadow_node
{
68 struct cds_lfht_node ht_node
; /* hash table node */
69 struct cds_ja_inode_flag
*node_flag
; /* reverse mapping and hash table key */
71 * mutual exclusion on all nodes belonging to the same tree
72 * position (e.g. both nodes before and after recompaction
75 pthread_mutex_t
*lock
;
76 unsigned int nr_child
; /* number of children in node */
77 struct rcu_head head
; /* for deferred node and shadow node reclaim */
78 int fallback_removal_count
; /* removals left keeping fallback */
79 int level
; /* level in the tree */
80 struct cds_ja
*ja
; /* toplevel judy array */
84 struct cds_ja_inode_flag
*root
;
85 unsigned int tree_depth
;
88 * We use a hash table to associate node keys to their
89 * respective shadow node. This helps reducing lookup hot path
90 * cache footprint, especially for very small nodes.
93 unsigned long nr_fallback
; /* Number of fallback nodes used */
97 struct cds_ja_inode_flag
*ja_node_flag(struct cds_ja_inode
*node
,
100 assert(type
< (1UL << JA_TYPE_BITS
));
101 return (struct cds_ja_inode_flag
*) (((unsigned long) node
) | type
);
105 struct cds_ja_inode
*ja_node_ptr(struct cds_ja_inode_flag
*node
)
107 return (struct cds_ja_inode
*) (((unsigned long) node
) & JA_PTR_MASK
);
111 unsigned long ja_node_type(struct cds_ja_inode_flag
*node
)
115 if (ja_node_ptr(node
) == NULL
) {
116 return NODE_INDEX_NULL
;
118 type
= (unsigned int) ((unsigned long) node
& JA_TYPE_MASK
);
119 assert(type
< (1UL << JA_TYPE_BITS
));
123 __attribute__((visibility("protected")))
124 void rcuja_free_all_children(struct cds_ja_shadow_node
*shadow_node
,
125 struct cds_ja_inode_flag
*node_flag
,
126 void (*free_node_cb
)(struct rcu_head
*head
));
128 __attribute__((visibility("protected")))
129 struct cds_ja_shadow_node
*rcuja_shadow_lookup_lock(struct cds_lfht
*ht
,
130 struct cds_ja_inode_flag
*node_flag
);
132 __attribute__((visibility("protected")))
133 void rcuja_shadow_unlock(struct cds_ja_shadow_node
*shadow_node
);
135 __attribute__((visibility("protected")))
136 struct cds_ja_shadow_node
*rcuja_shadow_set(struct cds_lfht
*ht
,
137 struct cds_ja_inode_flag
*new_node_flag
,
138 struct cds_ja_shadow_node
*inherit_from
,
141 /* rcuja_shadow_clear flags */
143 RCUJA_SHADOW_CLEAR_FREE_NODE
= (1U << 0),
144 RCUJA_SHADOW_CLEAR_FREE_LOCK
= (1U << 1),
147 __attribute__((visibility("protected")))
148 int rcuja_shadow_clear(struct cds_lfht
*ht
,
149 struct cds_ja_inode_flag
*node_flag
,
150 struct cds_ja_shadow_node
*shadow_node
,
153 __attribute__((visibility("protected")))
154 void rcuja_shadow_prune(struct cds_lfht
*ht
,
156 void (*free_node_cb
)(struct rcu_head
*head
));
158 __attribute__((visibility("protected")))
159 struct cds_lfht
*rcuja_create_ht(const struct rcu_flavor_struct
*flavor
);
161 __attribute__((visibility("protected")))
162 int rcuja_delete_ht(struct cds_lfht
*ht
);
170 #if defined(_syscall0)
171 _syscall0(pid_t
, gettid
)
172 #elif defined(__NR_gettid)
173 static inline pid_t
gettid(void)
175 return syscall(__NR_gettid
);
178 #warning "use pid as tid"
179 static inline pid_t
gettid(void)
186 #define dbg_printf(fmt, args...) \
187 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
188 (unsigned long) gettid(), __func__, \
189 __FILE__, __LINE__, ## args)
191 #define dbg_printf(fmt, args...) \
193 /* do nothing but check printf format */ \
195 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
196 (unsigned long) gettid(), __func__, \
197 __FILE__, __LINE__, ## args); \
201 #endif /* _URCU_RCUJA_INTERNAL_H */