1 /*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2006 Nick Piggin
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation; either version 2, or (at
9 * your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; If not, see <http://www.gnu.org/licenses/>.
18 */
19 #ifndef _XEN_RADIX_TREE_H
20 #define _XEN_RADIX_TREE_H
21
22 #include <xen/types.h>
23 #include <xen/lib.h>
24 #include <xen/rcupdate.h>
25
26 /*
27 * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
28 * than a data item) is signalled by the low bit set in the root->rnode
29 * pointer.
30 *
31 * In this case root->height is > 0, but the indirect pointer tests are
32 * needed for RCU lookups (because root->height is unreliable). The only
33 * time callers need worry about this is when doing a lookup_slot under
34 * RCU.
35 *
36 * Indirect pointer in fact is also used to tag the last pointer of a node
37 * when it is shrunk, before we rcu free the node. See shrink code for
38 * details.
39 */
40 #define RADIX_TREE_INDIRECT_PTR 1
41
radix_tree_is_indirect_ptr(void * ptr)42 static inline int radix_tree_is_indirect_ptr(void *ptr)
43 {
44 return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
45 }
46
47 /*
48 *** Radix tree structure definitions.
49 *** These are public to allow users to allocate instances of them.
50 *** However all fields are absolutely private.
51 */
52
53 #define RADIX_TREE_MAP_SHIFT 6
54 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
55 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
56
57 struct radix_tree_node {
58 unsigned int height; /* Height from the bottom */
59 unsigned int count;
60 void __rcu *slots[RADIX_TREE_MAP_SIZE];
61 };
62
63 typedef struct radix_tree_node *radix_tree_alloc_fn_t(void *);
64 typedef void radix_tree_free_fn_t(struct radix_tree_node *, void *);
65
66 struct radix_tree_root {
67 unsigned int height;
68 struct radix_tree_node __rcu *rnode;
69 };
70
71 /*
72 *** radix-tree API starts here **
73 */
74
75 #define RADIX_TREE_INIT() {}
76 #define RADIX_TREE(name) struct radix_tree_root name = RADIX_TREE_INIT()
77
78 void radix_tree_init(struct radix_tree_root *root);
79
80 void radix_tree_destroy(
81 struct radix_tree_root *root,
82 void (*slot_free)(void *));
83
84 /**
85 * Radix-tree synchronization
86 *
87 * The radix-tree API requires that users provide all synchronisation (with
88 * specific exceptions, noted below).
89 *
90 * Synchronization of access to the data items being stored in the tree, and
91 * management of their lifetimes must be completely managed by API users.
92 *
93 * For API usage, in general,
94 * - any function _modifying_ the tree (inserting or deleting items) must
95 * exclude other modifications, and exclude any functions reading the tree.
96 * - any function _reading_ the tree (looking up items) must exclude
97 * modifications to the tree, but may occur concurrently with other readers.
98 *
99 * The notable exceptions to this rule are the following functions:
100 * radix_tree_lookup
101 * radix_tree_lookup_slot
102 * radix_tree_gang_lookup
103 * radix_tree_gang_lookup_slot
104 *
105 * The first 7 functions are able to be called locklessly, using RCU. The
106 * caller must ensure calls to these functions are made within rcu_read_lock()
107 * regions. Other readers (lock-free or otherwise) and modifications may be
108 * running concurrently.
109 *
110 * It is still required that the caller manage the synchronization and lifetimes
111 * of the items. So if RCU lock-free lookups are used, typically this would mean
112 * that the items have their own locks, or are amenable to lock-free access; and
113 * that the items are freed by RCU (or only freed after having been deleted from
114 * the radix tree *and* a synchronize_rcu() grace period).
115 *
116 * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
117 * access to data items when inserting into or looking up from the radix tree)
118 */
119
120 /**
121 * radix_tree_deref_slot - dereference a slot
122 * @pslot: pointer to slot, returned by radix_tree_lookup_slot
123 * Returns: item that was stored in that slot with any direct pointer flag
124 * removed.
125 *
126 * For use with radix_tree_lookup_slot(). Caller must hold tree at least read
127 * locked across slot lookup and dereference. Not required if write lock is
128 * held (ie. items cannot be concurrently inserted).
129 *
130 * radix_tree_deref_retry must be used to confirm validity of the pointer if
131 * only the read lock is held.
132 */
radix_tree_deref_slot(void ** pslot)133 static inline void *radix_tree_deref_slot(void **pslot)
134 {
135 return rcu_dereference(*pslot);
136 }
137
138 /**
139 * radix_tree_deref_retry - check radix_tree_deref_slot
140 * @arg: pointer returned by radix_tree_deref_slot
141 * Returns: 0 if retry is not required, otherwise retry is required
142 *
143 * radix_tree_deref_retry must be used with radix_tree_deref_slot.
144 */
radix_tree_deref_retry(void * arg)145 static inline int radix_tree_deref_retry(void *arg)
146 {
147 return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR);
148 }
149
150 /**
151 * radix_tree_replace_slot - replace item in a slot
152 * @pslot: pointer to slot, returned by radix_tree_lookup_slot
153 * @item: new item to store in the slot.
154 *
155 * For use with radix_tree_lookup_slot(). Caller must hold tree write locked
156 * across slot lookup and replacement.
157 */
radix_tree_replace_slot(void ** pslot,void * item)158 static inline void radix_tree_replace_slot(void **pslot, void *item)
159 {
160 BUG_ON(radix_tree_is_indirect_ptr(item));
161 rcu_assign_pointer(*pslot, item);
162 }
163
164
165 /**
166 * radix_tree_{int_to_ptr,ptr_to_int}:
167 *
168 * Allow storage of signed integers in radix-tree slots. We use an encoding
169 * in which the bottom two bits of the slot pointer are reserved (bit 0 for
170 * the indirect-pointer tag; bit 1 always set to prevent an in-use
171 * integer-valued slot from being NULL and thus mistakenly being reaped).
172 */
radix_tree_int_to_ptr(int val)173 static inline void *radix_tree_int_to_ptr(int val)
174 {
175 long _ptr = ((unsigned long)val << 2) | 2;
176 ASSERT((_ptr >> 2) == val);
177 return (void *)_ptr;
178 }
179
radix_tree_ptr_to_int(void * ptr)180 static inline int radix_tree_ptr_to_int(void *ptr)
181 {
182 ASSERT(((long)ptr & 0x3) == 0x2);
183 return (int)((long)ptr >> 2);
184 }
185
186 /**
187 * radix_tree_{ulong_to_ptr,ptr_to_ulong}:
188 *
189 * Same for unsigned long values. Beware though that only BITS_PER_LONG-2
190 * bits are actually usable for the value.
191 */
radix_tree_ulong_to_ptr(unsigned long val)192 static inline void *radix_tree_ulong_to_ptr(unsigned long val)
193 {
194 unsigned long ptr = (val << 2) | 0x2;
195 ASSERT((ptr >> 2) == val);
196 return (void *)ptr;
197 }
198
radix_tree_ptr_to_ulong(void * ptr)199 static inline unsigned long radix_tree_ptr_to_ulong(void *ptr)
200 {
201 ASSERT(((unsigned long)ptr & 0x3) == 0x2);
202 return (unsigned long)ptr >> 2;
203 }
204
205 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
206 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
207 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
208 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
209 unsigned int
210 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
211 unsigned long first_index, unsigned int max_items);
212 unsigned int
213 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
214 unsigned long first_index, unsigned int max_items);
215 unsigned long radix_tree_next_hole(struct radix_tree_root *root,
216 unsigned long index, unsigned long max_scan);
217 unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
218 unsigned long index, unsigned long max_scan);
219
220 #endif /* _XEN_RADIX_TREE_H */
221