Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
radix-tree.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2001 Momchil Velikov
3  * Portions Copyright (C) 2001 Christoph Hellwig
4  * Copyright (C) 2006 Nick Piggin
5  * Copyright (C) 2012 Konstantin Khlebnikov
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License as
9  * published by the Free Software Foundation; either version 2, or (at
10  * your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful, but
13  * WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20  */
21 #ifndef _LINUX_RADIX_TREE_H
22 #define _LINUX_RADIX_TREE_H
23 
24 #include <linux/preempt.h>
25 #include <linux/types.h>
26 #include <linux/bug.h>
27 #include <linux/kernel.h>
28 #include <linux/rcupdate.h>
29 
30 /*
31  * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
32  * than a data item) is signalled by the low bit set in the root->rnode
33  * pointer.
34  *
35  * In this case root->height is > 0, but the indirect pointer tests are
36  * needed for RCU lookups (because root->height is unreliable). The only
37  * time callers need worry about this is when doing a lookup_slot under
38  * RCU.
39  *
40  * Indirect pointer in fact is also used to tag the last pointer of a node
41  * when it is shrunk, before we rcu free the node. See shrink code for
42  * details.
43  */
44 #define RADIX_TREE_INDIRECT_PTR 1
45 /*
46  * A common use of the radix tree is to store pointers to struct pages;
47  * but shmem/tmpfs needs also to store swap entries in the same tree:
48  * those are marked as exceptional entries to distinguish them.
49  * EXCEPTIONAL_ENTRY tests the bit, EXCEPTIONAL_SHIFT shifts content past it.
50  */
51 #define RADIX_TREE_EXCEPTIONAL_ENTRY 2
52 #define RADIX_TREE_EXCEPTIONAL_SHIFT 2
53 
54 static inline int radix_tree_is_indirect_ptr(void *ptr)
55 {
56  return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
57 }
58 
59 /*** radix-tree API starts here ***/
60 
61 #define RADIX_TREE_MAX_TAGS 3
62 
63 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
65  unsigned int height;
68 };
69 
70 #define RADIX_TREE_INIT(mask) { \
71  .height = 0, \
72  .gfp_mask = (mask), \
73  .rnode = NULL, \
74 }
75 
76 #define RADIX_TREE(name, mask) \
77  struct radix_tree_root name = RADIX_TREE_INIT(mask)
78 
79 #define INIT_RADIX_TREE(root, mask) \
80 do { \
81  (root)->height = 0; \
82  (root)->gfp_mask = (mask); \
83  (root)->rnode = NULL; \
84 } while (0)
85 
150 static inline void *radix_tree_deref_slot(void **pslot)
151 {
152  return rcu_dereference(*pslot);
153 }
154 
165 static inline void *radix_tree_deref_slot_protected(void **pslot,
166  spinlock_t *treelock)
167 {
168  return rcu_dereference_protected(*pslot, lockdep_is_held(treelock));
169 }
170 
178 static inline int radix_tree_deref_retry(void *arg)
179 {
180  return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR);
181 }
182 
188 static inline int radix_tree_exceptional_entry(void *arg)
189 {
190  /* Not unlikely because radix_tree_exception often tested first */
191  return (unsigned long)arg & RADIX_TREE_EXCEPTIONAL_ENTRY;
192 }
193 
199 static inline int radix_tree_exception(void *arg)
200 {
201  return unlikely((unsigned long)arg &
203 }
204 
213 static inline void radix_tree_replace_slot(void **pslot, void *item)
214 {
215  BUG_ON(radix_tree_is_indirect_ptr(item));
216  rcu_assign_pointer(*pslot, item);
217 }
218 
219 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
220 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
221 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
222 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
223 unsigned int
224 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
225  unsigned long first_index, unsigned int max_items);
226 unsigned int radix_tree_gang_lookup_slot(struct radix_tree_root *root,
227  void ***results, unsigned long *indices,
228  unsigned long first_index, unsigned int max_items);
229 unsigned long radix_tree_next_hole(struct radix_tree_root *root,
230  unsigned long index, unsigned long max_scan);
231 unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
232  unsigned long index, unsigned long max_scan);
234 void radix_tree_init(void);
235 void *radix_tree_tag_set(struct radix_tree_root *root,
236  unsigned long index, unsigned int tag);
237 void *radix_tree_tag_clear(struct radix_tree_root *root,
238  unsigned long index, unsigned int tag);
239 int radix_tree_tag_get(struct radix_tree_root *root,
240  unsigned long index, unsigned int tag);
241 unsigned int
242 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
243  unsigned long first_index, unsigned int max_items,
244  unsigned int tag);
245 unsigned int
246 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
247  unsigned long first_index, unsigned int max_items,
248  unsigned int tag);
249 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
250  unsigned long *first_indexp, unsigned long last_index,
251  unsigned long nr_to_tag,
252  unsigned int fromtag, unsigned int totag);
253 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
254 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item);
255 
256 static inline void radix_tree_preload_end(void)
257 {
258  preempt_enable();
259 }
260 
276  unsigned long index;
277  unsigned long next_index;
278  unsigned long tags;
279 };
280 
281 #define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */
282 #define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */
283 #define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */
284 
292 static __always_inline void **
293 radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
294 {
295  /*
296  * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
297  * in the case of a successful tagged chunk lookup. If the lookup was
298  * unsuccessful or non-tagged then nobody cares about ->tags.
299  *
300  * Set index to zero to bypass next_index overflow protection.
301  * See the comment in radix_tree_next_chunk() for details.
302  */
303  iter->index = 0;
304  iter->next_index = start;
305  return NULL;
306 }
307 
321 void **radix_tree_next_chunk(struct radix_tree_root *root,
322  struct radix_tree_iter *iter, unsigned flags);
323 
330 static __always_inline unsigned
331 radix_tree_chunk_size(struct radix_tree_iter *iter)
332 {
333  return iter->next_index - iter->index;
334 }
335 
347 static __always_inline void **
348 radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
349 {
350  if (flags & RADIX_TREE_ITER_TAGGED) {
351  iter->tags >>= 1;
352  if (likely(iter->tags & 1ul)) {
353  iter->index++;
354  return slot + 1;
355  }
356  if (!(flags & RADIX_TREE_ITER_CONTIG) && likely(iter->tags)) {
357  unsigned offset = __ffs(iter->tags);
358 
359  iter->tags >>= offset;
360  iter->index += offset + 1;
361  return slot + offset + 1;
362  }
363  } else {
364  unsigned size = radix_tree_chunk_size(iter) - 1;
365 
366  while (size--) {
367  slot++;
368  iter->index++;
369  if (likely(*slot))
370  return slot;
371  if (flags & RADIX_TREE_ITER_CONTIG) {
372  /* forbid switching to the next chunk */
373  iter->next_index = 0;
374  break;
375  }
376  }
377  }
378  return NULL;
379 }
380 
392 #define radix_tree_for_each_chunk(slot, root, iter, start, flags) \
393  for (slot = radix_tree_iter_init(iter, start) ; \
394  (slot = radix_tree_next_chunk(root, iter, flags)) ;)
395 
406 #define radix_tree_for_each_chunk_slot(slot, iter, flags) \
407  for (; slot ; slot = radix_tree_next_slot(slot, iter, flags))
408 
419 #define radix_tree_for_each_slot(slot, root, iter, start) \
420  for (slot = radix_tree_iter_init(iter, start) ; \
421  slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
422  slot = radix_tree_next_slot(slot, iter, 0))
423 
434 #define radix_tree_for_each_contig(slot, root, iter, start) \
435  for (slot = radix_tree_iter_init(iter, start) ; \
436  slot || (slot = radix_tree_next_chunk(root, iter, \
437  RADIX_TREE_ITER_CONTIG)) ; \
438  slot = radix_tree_next_slot(slot, iter, \
439  RADIX_TREE_ITER_CONTIG))
440 
452 #define radix_tree_for_each_tagged(slot, root, iter, start, tag) \
453  for (slot = radix_tree_iter_init(iter, start) ; \
454  slot || (slot = radix_tree_next_chunk(root, iter, \
455  RADIX_TREE_ITER_TAGGED | tag)) ; \
456  slot = radix_tree_next_slot(slot, iter, \
457  RADIX_TREE_ITER_TAGGED))
458 
459 #endif /* _LINUX_RADIX_TREE_H */