radix-tree: move rcu_head into a union with private_list
[muen/linux.git] / include / linux / radix-tree.h
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/bitops.h>
25 #include <linux/preempt.h>
26 #include <linux/types.h>
27 #include <linux/bug.h>
28 #include <linux/kernel.h>
29 #include <linux/rcupdate.h>
30
31 /*
32  * The bottom two bits of the slot determine how the remaining bits in the
33  * slot are interpreted:
34  *
35  * 00 - data pointer
36  * 01 - internal entry
37  * 10 - exceptional entry
38  * 11 - this bit combination is currently unused/reserved
39  *
40  * The internal entry may be a pointer to the next level in the tree, a
41  * sibling entry, or an indicator that the entry in this slot has been moved
42  * to another location in the tree and the lookup should be restarted.  While
43  * NULL fits the 'data pointer' pattern, it means that there is no entry in
44  * the tree for this index (no matter what level of the tree it is found at).
45  * This means that you cannot store NULL in the tree as a value for the index.
46  */
47 #define RADIX_TREE_ENTRY_MASK           3UL
48 #define RADIX_TREE_INTERNAL_NODE        1UL
49
50 /*
51  * Most users of the radix tree store pointers but shmem/tmpfs stores swap
52  * entries in the same tree.  They are marked as exceptional entries to
53  * distinguish them from pointers to struct page.
54  * EXCEPTIONAL_ENTRY tests the bit, EXCEPTIONAL_SHIFT shifts content past it.
55  */
56 #define RADIX_TREE_EXCEPTIONAL_ENTRY    2
57 #define RADIX_TREE_EXCEPTIONAL_SHIFT    2
58
59 static inline bool radix_tree_is_internal_node(void *ptr)
60 {
61         return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
62                                 RADIX_TREE_INTERNAL_NODE;
63 }
64
65 /*** radix-tree API starts here ***/
66
67 #define RADIX_TREE_MAX_TAGS 3
68
69 #ifndef RADIX_TREE_MAP_SHIFT
70 #define RADIX_TREE_MAP_SHIFT    (CONFIG_BASE_SMALL ? 4 : 6)
71 #endif
72
73 #define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
74 #define RADIX_TREE_MAP_MASK     (RADIX_TREE_MAP_SIZE-1)
75
76 #define RADIX_TREE_TAG_LONGS    \
77         ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
78
79 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
80 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
81                                           RADIX_TREE_MAP_SHIFT))
82
83 struct radix_tree_node {
84         unsigned char   shift;          /* Bits remaining in each slot */
85         unsigned char   offset;         /* Slot offset in parent */
86         unsigned char   count;          /* Total entry count */
87         unsigned char   exceptional;    /* Exceptional entry count */
88         struct radix_tree_node *parent;         /* Used when ascending tree */
89         void *private_data;                     /* For tree user */
90         union {
91                 struct list_head private_list;  /* For tree user */
92                 struct rcu_head rcu_head;       /* Used when freeing node */
93         };
94         void __rcu      *slots[RADIX_TREE_MAP_SIZE];
95         unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
96 };
97
98 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
99 struct radix_tree_root {
100         gfp_t                   gfp_mask;
101         struct radix_tree_node  __rcu *rnode;
102 };
103
104 #define RADIX_TREE_INIT(mask)   {                                       \
105         .gfp_mask = (mask),                                             \
106         .rnode = NULL,                                                  \
107 }
108
109 #define RADIX_TREE(name, mask) \
110         struct radix_tree_root name = RADIX_TREE_INIT(mask)
111
112 #define INIT_RADIX_TREE(root, mask)                                     \
113 do {                                                                    \
114         (root)->gfp_mask = (mask);                                      \
115         (root)->rnode = NULL;                                           \
116 } while (0)
117
118 static inline bool radix_tree_empty(struct radix_tree_root *root)
119 {
120         return root->rnode == NULL;
121 }
122
123 /**
124  * Radix-tree synchronization
125  *
126  * The radix-tree API requires that users provide all synchronisation (with
127  * specific exceptions, noted below).
128  *
129  * Synchronization of access to the data items being stored in the tree, and
130  * management of their lifetimes must be completely managed by API users.
131  *
132  * For API usage, in general,
133  * - any function _modifying_ the tree or tags (inserting or deleting
134  *   items, setting or clearing tags) must exclude other modifications, and
135  *   exclude any functions reading the tree.
136  * - any function _reading_ the tree or tags (looking up items or tags,
137  *   gang lookups) must exclude modifications to the tree, but may occur
138  *   concurrently with other readers.
139  *
140  * The notable exceptions to this rule are the following functions:
141  * __radix_tree_lookup
142  * radix_tree_lookup
143  * radix_tree_lookup_slot
144  * radix_tree_tag_get
145  * radix_tree_gang_lookup
146  * radix_tree_gang_lookup_slot
147  * radix_tree_gang_lookup_tag
148  * radix_tree_gang_lookup_tag_slot
149  * radix_tree_tagged
150  *
151  * The first 8 functions are able to be called locklessly, using RCU. The
152  * caller must ensure calls to these functions are made within rcu_read_lock()
153  * regions. Other readers (lock-free or otherwise) and modifications may be
154  * running concurrently.
155  *
156  * It is still required that the caller manage the synchronization and lifetimes
157  * of the items. So if RCU lock-free lookups are used, typically this would mean
158  * that the items have their own locks, or are amenable to lock-free access; and
159  * that the items are freed by RCU (or only freed after having been deleted from
160  * the radix tree *and* a synchronize_rcu() grace period).
161  *
162  * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
163  * access to data items when inserting into or looking up from the radix tree)
164  *
165  * Note that the value returned by radix_tree_tag_get() may not be relied upon
166  * if only the RCU read lock is held.  Functions to set/clear tags and to
167  * delete nodes running concurrently with it may affect its result such that
168  * two consecutive reads in the same locked section may return different
169  * values.  If reliability is required, modification functions must also be
170  * excluded from concurrency.
171  *
172  * radix_tree_tagged is able to be called without locking or RCU.
173  */
174
175 /**
176  * radix_tree_deref_slot        - dereference a slot
177  * @pslot:      pointer to slot, returned by radix_tree_lookup_slot
178  * Returns:     item that was stored in that slot with any direct pointer flag
179  *              removed.
180  *
181  * For use with radix_tree_lookup_slot().  Caller must hold tree at least read
182  * locked across slot lookup and dereference. Not required if write lock is
183  * held (ie. items cannot be concurrently inserted).
184  *
185  * radix_tree_deref_retry must be used to confirm validity of the pointer if
186  * only the read lock is held.
187  */
188 static inline void *radix_tree_deref_slot(void **pslot)
189 {
190         return rcu_dereference(*pslot);
191 }
192
193 /**
194  * radix_tree_deref_slot_protected      - dereference a slot without RCU lock but with tree lock held
195  * @pslot:      pointer to slot, returned by radix_tree_lookup_slot
196  * Returns:     item that was stored in that slot with any direct pointer flag
197  *              removed.
198  *
199  * Similar to radix_tree_deref_slot but only used during migration when a pages
200  * mapping is being moved. The caller does not hold the RCU read lock but it
201  * must hold the tree lock to prevent parallel updates.
202  */
203 static inline void *radix_tree_deref_slot_protected(void **pslot,
204                                                         spinlock_t *treelock)
205 {
206         return rcu_dereference_protected(*pslot, lockdep_is_held(treelock));
207 }
208
209 /**
210  * radix_tree_deref_retry       - check radix_tree_deref_slot
211  * @arg:        pointer returned by radix_tree_deref_slot
212  * Returns:     0 if retry is not required, otherwise retry is required
213  *
214  * radix_tree_deref_retry must be used with radix_tree_deref_slot.
215  */
216 static inline int radix_tree_deref_retry(void *arg)
217 {
218         return unlikely(radix_tree_is_internal_node(arg));
219 }
220
221 /**
222  * radix_tree_exceptional_entry - radix_tree_deref_slot gave exceptional entry?
223  * @arg:        value returned by radix_tree_deref_slot
224  * Returns:     0 if well-aligned pointer, non-0 if exceptional entry.
225  */
226 static inline int radix_tree_exceptional_entry(void *arg)
227 {
228         /* Not unlikely because radix_tree_exception often tested first */
229         return (unsigned long)arg & RADIX_TREE_EXCEPTIONAL_ENTRY;
230 }
231
232 /**
233  * radix_tree_exception - radix_tree_deref_slot returned either exception?
234  * @arg:        value returned by radix_tree_deref_slot
235  * Returns:     0 if well-aligned pointer, non-0 if either kind of exception.
236  */
237 static inline int radix_tree_exception(void *arg)
238 {
239         return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
240 }
241
242 int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
243                         unsigned order, struct radix_tree_node **nodep,
244                         void ***slotp);
245 int __radix_tree_insert(struct radix_tree_root *, unsigned long index,
246                         unsigned order, void *);
247 static inline int radix_tree_insert(struct radix_tree_root *root,
248                         unsigned long index, void *entry)
249 {
250         return __radix_tree_insert(root, index, 0, entry);
251 }
252 void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
253                           struct radix_tree_node **nodep, void ***slotp);
254 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
255 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
256 typedef void (*radix_tree_update_node_t)(struct radix_tree_node *, void *);
257 void __radix_tree_replace(struct radix_tree_root *root,
258                           struct radix_tree_node *node,
259                           void **slot, void *item,
260                           radix_tree_update_node_t update_node, void *private);
261 void radix_tree_replace_slot(struct radix_tree_root *root,
262                              void **slot, void *item);
263 void __radix_tree_delete_node(struct radix_tree_root *root,
264                               struct radix_tree_node *node);
265 void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
266 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
267 void radix_tree_clear_tags(struct radix_tree_root *root,
268                            struct radix_tree_node *node,
269                            void **slot);
270 unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
271                         void **results, unsigned long first_index,
272                         unsigned int max_items);
273 unsigned int radix_tree_gang_lookup_slot(struct radix_tree_root *root,
274                         void ***results, unsigned long *indices,
275                         unsigned long first_index, unsigned int max_items);
276 int radix_tree_preload(gfp_t gfp_mask);
277 int radix_tree_maybe_preload(gfp_t gfp_mask);
278 int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order);
279 void radix_tree_init(void);
280 void *radix_tree_tag_set(struct radix_tree_root *root,
281                         unsigned long index, unsigned int tag);
282 void *radix_tree_tag_clear(struct radix_tree_root *root,
283                         unsigned long index, unsigned int tag);
284 int radix_tree_tag_get(struct radix_tree_root *root,
285                         unsigned long index, unsigned int tag);
286 unsigned int
287 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
288                 unsigned long first_index, unsigned int max_items,
289                 unsigned int tag);
290 unsigned int
291 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
292                 unsigned long first_index, unsigned int max_items,
293                 unsigned int tag);
294 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
295                 unsigned long *first_indexp, unsigned long last_index,
296                 unsigned long nr_to_tag,
297                 unsigned int fromtag, unsigned int totag);
298 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
299 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item);
300
301 static inline void radix_tree_preload_end(void)
302 {
303         preempt_enable();
304 }
305
306 /**
307  * struct radix_tree_iter - radix tree iterator state
308  *
309  * @index:      index of current slot
310  * @next_index: one beyond the last index for this chunk
311  * @tags:       bit-mask for tag-iterating
312  * @shift:      shift for the node that holds our slots
313  *
314  * This radix tree iterator works in terms of "chunks" of slots.  A chunk is a
315  * subinterval of slots contained within one radix tree leaf node.  It is
316  * described by a pointer to its first slot and a struct radix_tree_iter
317  * which holds the chunk's position in the tree and its size.  For tagged
318  * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
319  * radix tree tag.
320  */
321 struct radix_tree_iter {
322         unsigned long   index;
323         unsigned long   next_index;
324         unsigned long   tags;
325 #ifdef CONFIG_RADIX_TREE_MULTIORDER
326         unsigned int    shift;
327 #endif
328 };
329
330 static inline unsigned int iter_shift(struct radix_tree_iter *iter)
331 {
332 #ifdef CONFIG_RADIX_TREE_MULTIORDER
333         return iter->shift;
334 #else
335         return 0;
336 #endif
337 }
338
339 #define RADIX_TREE_ITER_TAG_MASK        0x00FF  /* tag index in lower byte */
340 #define RADIX_TREE_ITER_TAGGED          0x0100  /* lookup tagged slots */
341 #define RADIX_TREE_ITER_CONTIG          0x0200  /* stop at first hole */
342
343 /**
344  * radix_tree_iter_init - initialize radix tree iterator
345  *
346  * @iter:       pointer to iterator state
347  * @start:      iteration starting index
348  * Returns:     NULL
349  */
350 static __always_inline void **
351 radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
352 {
353         /*
354          * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
355          * in the case of a successful tagged chunk lookup.  If the lookup was
356          * unsuccessful or non-tagged then nobody cares about ->tags.
357          *
358          * Set index to zero to bypass next_index overflow protection.
359          * See the comment in radix_tree_next_chunk() for details.
360          */
361         iter->index = 0;
362         iter->next_index = start;
363         return NULL;
364 }
365
366 /**
367  * radix_tree_next_chunk - find next chunk of slots for iteration
368  *
369  * @root:       radix tree root
370  * @iter:       iterator state
371  * @flags:      RADIX_TREE_ITER_* flags and tag index
372  * Returns:     pointer to chunk first slot, or NULL if there no more left
373  *
374  * This function looks up the next chunk in the radix tree starting from
375  * @iter->next_index.  It returns a pointer to the chunk's first slot.
376  * Also it fills @iter with data about chunk: position in the tree (index),
377  * its end (next_index), and constructs a bit mask for tagged iterating (tags).
378  */
379 void **radix_tree_next_chunk(struct radix_tree_root *root,
380                              struct radix_tree_iter *iter, unsigned flags);
381
382 /**
383  * radix_tree_iter_retry - retry this chunk of the iteration
384  * @iter:       iterator state
385  *
386  * If we iterate over a tree protected only by the RCU lock, a race
387  * against deletion or creation may result in seeing a slot for which
388  * radix_tree_deref_retry() returns true.  If so, call this function
389  * and continue the iteration.
390  */
391 static inline __must_check
392 void **radix_tree_iter_retry(struct radix_tree_iter *iter)
393 {
394         iter->next_index = iter->index;
395         iter->tags = 0;
396         return NULL;
397 }
398
399 static inline unsigned long
400 __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
401 {
402         return iter->index + (slots << iter_shift(iter));
403 }
404
405 /**
406  * radix_tree_iter_next - resume iterating when the chunk may be invalid
407  * @iter:       iterator state
408  *
409  * If the iterator needs to release then reacquire a lock, the chunk may
410  * have been invalidated by an insertion or deletion.  Call this function
411  * to continue the iteration from the next index.
412  */
413 static inline __must_check
414 void **radix_tree_iter_next(struct radix_tree_iter *iter)
415 {
416         iter->next_index = __radix_tree_iter_add(iter, 1);
417         iter->tags = 0;
418         return NULL;
419 }
420
421 /**
422  * radix_tree_chunk_size - get current chunk size
423  *
424  * @iter:       pointer to radix tree iterator
425  * Returns:     current chunk size
426  */
427 static __always_inline long
428 radix_tree_chunk_size(struct radix_tree_iter *iter)
429 {
430         return (iter->next_index - iter->index) >> iter_shift(iter);
431 }
432
433 static inline struct radix_tree_node *entry_to_node(void *ptr)
434 {
435         return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
436 }
437
438 /**
439  * radix_tree_next_slot - find next slot in chunk
440  *
441  * @slot:       pointer to current slot
442  * @iter:       pointer to interator state
443  * @flags:      RADIX_TREE_ITER_*, should be constant
444  * Returns:     pointer to next slot, or NULL if there no more left
445  *
446  * This function updates @iter->index in the case of a successful lookup.
447  * For tagged lookup it also eats @iter->tags.
448  *
449  * There are several cases where 'slot' can be passed in as NULL to this
450  * function.  These cases result from the use of radix_tree_iter_next() or
451  * radix_tree_iter_retry().  In these cases we don't end up dereferencing
452  * 'slot' because either:
453  * a) we are doing tagged iteration and iter->tags has been set to 0, or
454  * b) we are doing non-tagged iteration, and iter->index and iter->next_index
455  *    have been set up so that radix_tree_chunk_size() returns 1 or 0.
456  */
457 static __always_inline void **
458 radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
459 {
460         if (flags & RADIX_TREE_ITER_TAGGED) {
461                 void *canon = slot;
462
463                 iter->tags >>= 1;
464                 if (unlikely(!iter->tags))
465                         return NULL;
466                 while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
467                                         radix_tree_is_internal_node(slot[1])) {
468                         if (entry_to_node(slot[1]) == canon) {
469                                 iter->tags >>= 1;
470                                 iter->index = __radix_tree_iter_add(iter, 1);
471                                 slot++;
472                                 continue;
473                         }
474                         iter->next_index = __radix_tree_iter_add(iter, 1);
475                         return NULL;
476                 }
477                 if (likely(iter->tags & 1ul)) {
478                         iter->index = __radix_tree_iter_add(iter, 1);
479                         return slot + 1;
480                 }
481                 if (!(flags & RADIX_TREE_ITER_CONTIG)) {
482                         unsigned offset = __ffs(iter->tags);
483
484                         iter->tags >>= offset;
485                         iter->index = __radix_tree_iter_add(iter, offset + 1);
486                         return slot + offset + 1;
487                 }
488         } else {
489                 long count = radix_tree_chunk_size(iter);
490                 void *canon = slot;
491
492                 while (--count > 0) {
493                         slot++;
494                         iter->index = __radix_tree_iter_add(iter, 1);
495
496                         if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
497                             radix_tree_is_internal_node(*slot)) {
498                                 if (entry_to_node(*slot) == canon)
499                                         continue;
500                                 iter->next_index = iter->index;
501                                 break;
502                         }
503
504                         if (likely(*slot))
505                                 return slot;
506                         if (flags & RADIX_TREE_ITER_CONTIG) {
507                                 /* forbid switching to the next chunk */
508                                 iter->next_index = 0;
509                                 break;
510                         }
511                 }
512         }
513         return NULL;
514 }
515
516 /**
517  * radix_tree_for_each_slot - iterate over non-empty slots
518  *
519  * @slot:       the void** variable for pointer to slot
520  * @root:       the struct radix_tree_root pointer
521  * @iter:       the struct radix_tree_iter pointer
522  * @start:      iteration starting index
523  *
524  * @slot points to radix tree slot, @iter->index contains its index.
525  */
526 #define radix_tree_for_each_slot(slot, root, iter, start)               \
527         for (slot = radix_tree_iter_init(iter, start) ;                 \
528              slot || (slot = radix_tree_next_chunk(root, iter, 0)) ;    \
529              slot = radix_tree_next_slot(slot, iter, 0))
530
531 /**
532  * radix_tree_for_each_contig - iterate over contiguous slots
533  *
534  * @slot:       the void** variable for pointer to slot
535  * @root:       the struct radix_tree_root pointer
536  * @iter:       the struct radix_tree_iter pointer
537  * @start:      iteration starting index
538  *
539  * @slot points to radix tree slot, @iter->index contains its index.
540  */
541 #define radix_tree_for_each_contig(slot, root, iter, start)             \
542         for (slot = radix_tree_iter_init(iter, start) ;                 \
543              slot || (slot = radix_tree_next_chunk(root, iter,          \
544                                 RADIX_TREE_ITER_CONTIG)) ;              \
545              slot = radix_tree_next_slot(slot, iter,                    \
546                                 RADIX_TREE_ITER_CONTIG))
547
548 /**
549  * radix_tree_for_each_tagged - iterate over tagged slots
550  *
551  * @slot:       the void** variable for pointer to slot
552  * @root:       the struct radix_tree_root pointer
553  * @iter:       the struct radix_tree_iter pointer
554  * @start:      iteration starting index
555  * @tag:        tag index
556  *
557  * @slot points to radix tree slot, @iter->index contains its index.
558  */
559 #define radix_tree_for_each_tagged(slot, root, iter, start, tag)        \
560         for (slot = radix_tree_iter_init(iter, start) ;                 \
561              slot || (slot = radix_tree_next_chunk(root, iter,          \
562                               RADIX_TREE_ITER_TAGGED | tag)) ;          \
563              slot = radix_tree_next_slot(slot, iter,                    \
564                                 RADIX_TREE_ITER_TAGGED))
565
566 #endif /* _LINUX_RADIX_TREE_H */