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 /* Allow to specify custom node alloc/dealloc routines. */
71 radix_tree_alloc_fn_t *node_alloc;
72 radix_tree_free_fn_t *node_free;
73 void *node_alloc_free_arg;
74 };
75
76 /*
77 *** radix-tree API starts here **
78 */
79
80 void radix_tree_init(struct radix_tree_root *root);
81 void radix_tree_set_alloc_callbacks(
82 struct radix_tree_root *root,
83 radix_tree_alloc_fn_t *node_alloc,
84 radix_tree_free_fn_t *node_free,
85 void *node_alloc_free_arg);
86
87 void radix_tree_destroy(
88 struct radix_tree_root *root,
89 void (*slot_free)(void *));
90
91 /**
92 * Radix-tree synchronization
93 *
94 * The radix-tree API requires that users provide all synchronisation (with
95 * specific exceptions, noted below).
96 *
97 * Synchronization of access to the data items being stored in the tree, and
98 * management of their lifetimes must be completely managed by API users.
99 *
100 * For API usage, in general,
101 * - any function _modifying_ the tree (inserting or deleting items) must
102 * exclude other modifications, and exclude any functions reading the tree.
103 * - any function _reading_ the tree (looking up items) must exclude
104 * modifications to the tree, but may occur concurrently with other readers.
105 *
106 * The notable exceptions to this rule are the following functions:
107 * radix_tree_lookup
108 * radix_tree_lookup_slot
109 * radix_tree_gang_lookup
110 * radix_tree_gang_lookup_slot
111 *
112 * The first 7 functions are able to be called locklessly, using RCU. The
113 * caller must ensure calls to these functions are made within rcu_read_lock()
114 * regions. Other readers (lock-free or otherwise) and modifications may be
115 * running concurrently.
116 *
117 * It is still required that the caller manage the synchronization and lifetimes
118 * of the items. So if RCU lock-free lookups are used, typically this would mean
119 * that the items have their own locks, or are amenable to lock-free access; and
120 * that the items are freed by RCU (or only freed after having been deleted from
121 * the radix tree *and* a synchronize_rcu() grace period).
122 *
123 * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
124 * access to data items when inserting into or looking up from the radix tree)
125 */
126
127 /**
128 * radix_tree_deref_slot - dereference a slot
129 * @pslot: pointer to slot, returned by radix_tree_lookup_slot
130 * Returns: item that was stored in that slot with any direct pointer flag
131 * removed.
132 *
133 * For use with radix_tree_lookup_slot(). Caller must hold tree at least read
134 * locked across slot lookup and dereference. Not required if write lock is
135 * held (ie. items cannot be concurrently inserted).
136 *
137 * radix_tree_deref_retry must be used to confirm validity of the pointer if
138 * only the read lock is held.
139 */
radix_tree_deref_slot(void ** pslot)140 static inline void *radix_tree_deref_slot(void **pslot)
141 {
142 return rcu_dereference(*pslot);
143 }
144
145 /**
146 * radix_tree_deref_retry - check radix_tree_deref_slot
147 * @arg: pointer returned by radix_tree_deref_slot
148 * Returns: 0 if retry is not required, otherwise retry is required
149 *
150 * radix_tree_deref_retry must be used with radix_tree_deref_slot.
151 */
radix_tree_deref_retry(void * arg)152 static inline int radix_tree_deref_retry(void *arg)
153 {
154 return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR);
155 }
156
157 /**
158 * radix_tree_replace_slot - replace item in a slot
159 * @pslot: pointer to slot, returned by radix_tree_lookup_slot
160 * @item: new item to store in the slot.
161 *
162 * For use with radix_tree_lookup_slot(). Caller must hold tree write locked
163 * across slot lookup and replacement.
164 */
radix_tree_replace_slot(void ** pslot,void * item)165 static inline void radix_tree_replace_slot(void **pslot, void *item)
166 {
167 BUG_ON(radix_tree_is_indirect_ptr(item));
168 rcu_assign_pointer(*pslot, item);
169 }
170
171
172 /**
173 * radix_tree_{int_to_ptr,ptr_to_int}:
174 *
175 * Allow storage of signed integers in radix-tree slots. We use an encoding
176 * in which the bottom two bits of the slot pointer are reserved (bit 0 for
177 * the indirect-pointer tag; bit 1 always set to prevent an in-use
178 * integer-valued slot from being NULL and thus mistakenly being reaped).
179 */
radix_tree_int_to_ptr(int val)180 static inline void *radix_tree_int_to_ptr(int val)
181 {
182 long _ptr = ((long)val << 2) | 0x2l;
183 ASSERT((_ptr >> 2) == val);
184 return (void *)_ptr;
185 }
186
radix_tree_ptr_to_int(void * ptr)187 static inline int radix_tree_ptr_to_int(void *ptr)
188 {
189 ASSERT(((long)ptr & 0x3) == 0x2);
190 return (int)((long)ptr >> 2);
191 }
192
193 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
194 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
195 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
196 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
197 unsigned int
198 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
199 unsigned long first_index, unsigned int max_items);
200 unsigned int
201 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
202 unsigned long first_index, unsigned int max_items);
203 unsigned long radix_tree_next_hole(struct radix_tree_root *root,
204 unsigned long index, unsigned long max_scan);
205 unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
206 unsigned long index, unsigned long max_scan);
207
208 #endif /* _XEN_RADIX_TREE_H */
209