LCOV - code coverage report
Current view: top level - include/linux - radix-tree.h (source / functions) Hit Total Coverage
Test: landlock.info Lines: 6 39 15.4 %
Date: 2021-04-22 12:43:58 Functions: 0 1 0.0 %

          Line data    Source code
       1             : /* SPDX-License-Identifier: GPL-2.0-or-later */
       2             : /*
       3             :  * Copyright (C) 2001 Momchil Velikov
       4             :  * Portions Copyright (C) 2001 Christoph Hellwig
       5             :  * Copyright (C) 2006 Nick Piggin
       6             :  * Copyright (C) 2012 Konstantin Khlebnikov
       7             :  */
       8             : #ifndef _LINUX_RADIX_TREE_H
       9             : #define _LINUX_RADIX_TREE_H
      10             : 
      11             : #include <linux/bitops.h>
      12             : #include <linux/kernel.h>
      13             : #include <linux/list.h>
      14             : #include <linux/percpu.h>
      15             : #include <linux/preempt.h>
      16             : #include <linux/rcupdate.h>
      17             : #include <linux/spinlock.h>
      18             : #include <linux/types.h>
      19             : #include <linux/xarray.h>
      20             : #include <linux/local_lock.h>
      21             : 
      22             : /* Keep unconverted code working */
      23             : #define radix_tree_root         xarray
      24             : #define radix_tree_node         xa_node
      25             : 
      26             : struct radix_tree_preload {
      27             :         local_lock_t lock;
      28             :         unsigned nr;
      29             :         /* nodes->parent points to next preallocated node */
      30             :         struct radix_tree_node *nodes;
      31             : };
      32             : DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);
      33             : 
      34             : /*
      35             :  * The bottom two bits of the slot determine how the remaining bits in the
      36             :  * slot are interpreted:
      37             :  *
      38             :  * 00 - data pointer
      39             :  * 10 - internal entry
      40             :  * x1 - value entry
      41             :  *
      42             :  * The internal entry may be a pointer to the next level in the tree, a
      43             :  * sibling entry, or an indicator that the entry in this slot has been moved
      44             :  * to another location in the tree and the lookup should be restarted.  While
      45             :  * NULL fits the 'data pointer' pattern, it means that there is no entry in
      46             :  * the tree for this index (no matter what level of the tree it is found at).
      47             :  * This means that storing a NULL entry in the tree is the same as deleting
      48             :  * the entry from the tree.
      49             :  */
      50             : #define RADIX_TREE_ENTRY_MASK           3UL
      51             : #define RADIX_TREE_INTERNAL_NODE        2UL
      52             : 
      53       73953 : static inline bool radix_tree_is_internal_node(void *ptr)
      54             : {
      55       73953 :         return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
      56             :                                 RADIX_TREE_INTERNAL_NODE;
      57             : }
      58             : 
      59             : /*** radix-tree API starts here ***/
      60             : 
      61             : #define RADIX_TREE_MAP_SHIFT    XA_CHUNK_SHIFT
      62             : #define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
      63             : #define RADIX_TREE_MAP_MASK     (RADIX_TREE_MAP_SIZE-1)
      64             : 
      65             : #define RADIX_TREE_MAX_TAGS     XA_MAX_MARKS
      66             : #define RADIX_TREE_TAG_LONGS    XA_MARK_LONGS
      67             : 
      68             : #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
      69             : #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
      70             :                                           RADIX_TREE_MAP_SHIFT))
      71             : 
      72             : /* The IDR tag is stored in the low bits of xa_flags */
      73             : #define ROOT_IS_IDR     ((__force gfp_t)4)
      74             : /* The top bits of xa_flags are used to store the root tags */
      75             : #define ROOT_TAG_SHIFT  (__GFP_BITS_SHIFT)
      76             : 
      77             : #define RADIX_TREE_INIT(name, mask)     XARRAY_INIT(name, mask)
      78             : 
      79             : #define RADIX_TREE(name, mask) \
      80             :         struct radix_tree_root name = RADIX_TREE_INIT(name, mask)
      81             : 
      82             : #define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask)
      83             : 
      84           0 : static inline bool radix_tree_empty(const struct radix_tree_root *root)
      85             : {
      86           0 :         return root->xa_head == NULL;
      87             : }
      88             : 
      89             : /**
      90             :  * struct radix_tree_iter - radix tree iterator state
      91             :  *
      92             :  * @index:      index of current slot
      93             :  * @next_index: one beyond the last index for this chunk
      94             :  * @tags:       bit-mask for tag-iterating
      95             :  * @node:       node that contains current slot
      96             :  *
      97             :  * This radix tree iterator works in terms of "chunks" of slots.  A chunk is a
      98             :  * subinterval of slots contained within one radix tree leaf node.  It is
      99             :  * described by a pointer to its first slot and a struct radix_tree_iter
     100             :  * which holds the chunk's position in the tree and its size.  For tagged
     101             :  * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
     102             :  * radix tree tag.
     103             :  */
     104             : struct radix_tree_iter {
     105             :         unsigned long   index;
     106             :         unsigned long   next_index;
     107             :         unsigned long   tags;
     108             :         struct radix_tree_node *node;
     109             : };
     110             : 
     111             : /**
     112             :  * Radix-tree synchronization
     113             :  *
     114             :  * The radix-tree API requires that users provide all synchronisation (with
     115             :  * specific exceptions, noted below).
     116             :  *
     117             :  * Synchronization of access to the data items being stored in the tree, and
     118             :  * management of their lifetimes must be completely managed by API users.
     119             :  *
     120             :  * For API usage, in general,
     121             :  * - any function _modifying_ the tree or tags (inserting or deleting
     122             :  *   items, setting or clearing tags) must exclude other modifications, and
     123             :  *   exclude any functions reading the tree.
     124             :  * - any function _reading_ the tree or tags (looking up items or tags,
     125             :  *   gang lookups) must exclude modifications to the tree, but may occur
     126             :  *   concurrently with other readers.
     127             :  *
     128             :  * The notable exceptions to this rule are the following functions:
     129             :  * __radix_tree_lookup
     130             :  * radix_tree_lookup
     131             :  * radix_tree_lookup_slot
     132             :  * radix_tree_tag_get
     133             :  * radix_tree_gang_lookup
     134             :  * radix_tree_gang_lookup_tag
     135             :  * radix_tree_gang_lookup_tag_slot
     136             :  * radix_tree_tagged
     137             :  *
     138             :  * The first 7 functions are able to be called locklessly, using RCU. The
     139             :  * caller must ensure calls to these functions are made within rcu_read_lock()
     140             :  * regions. Other readers (lock-free or otherwise) and modifications may be
     141             :  * running concurrently.
     142             :  *
     143             :  * It is still required that the caller manage the synchronization and lifetimes
     144             :  * of the items. So if RCU lock-free lookups are used, typically this would mean
     145             :  * that the items have their own locks, or are amenable to lock-free access; and
     146             :  * that the items are freed by RCU (or only freed after having been deleted from
     147             :  * the radix tree *and* a synchronize_rcu() grace period).
     148             :  *
     149             :  * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
     150             :  * access to data items when inserting into or looking up from the radix tree)
     151             :  *
     152             :  * Note that the value returned by radix_tree_tag_get() may not be relied upon
     153             :  * if only the RCU read lock is held.  Functions to set/clear tags and to
     154             :  * delete nodes running concurrently with it may affect its result such that
     155             :  * two consecutive reads in the same locked section may return different
     156             :  * values.  If reliability is required, modification functions must also be
     157             :  * excluded from concurrency.
     158             :  *
     159             :  * radix_tree_tagged is able to be called without locking or RCU.
     160             :  */
     161             : 
     162             : /**
     163             :  * radix_tree_deref_slot - dereference a slot
     164             :  * @slot: slot pointer, returned by radix_tree_lookup_slot
     165             :  *
     166             :  * For use with radix_tree_lookup_slot().  Caller must hold tree at least read
     167             :  * locked across slot lookup and dereference. Not required if write lock is
     168             :  * held (ie. items cannot be concurrently inserted).
     169             :  *
     170             :  * radix_tree_deref_retry must be used to confirm validity of the pointer if
     171             :  * only the read lock is held.
     172             :  *
     173             :  * Return: entry stored in that slot.
     174             :  */
     175             : static inline void *radix_tree_deref_slot(void __rcu **slot)
     176             : {
     177             :         return rcu_dereference(*slot);
     178             : }
     179             : 
     180             : /**
     181             :  * radix_tree_deref_slot_protected - dereference a slot with tree lock held
     182             :  * @slot: slot pointer, returned by radix_tree_lookup_slot
     183             :  *
     184             :  * Similar to radix_tree_deref_slot.  The caller does not hold the RCU read
     185             :  * lock but it must hold the tree lock to prevent parallel updates.
     186             :  *
     187             :  * Return: entry stored in that slot.
     188             :  */
     189             : static inline void *radix_tree_deref_slot_protected(void __rcu **slot,
     190             :                                                         spinlock_t *treelock)
     191             : {
     192             :         return rcu_dereference_protected(*slot, lockdep_is_held(treelock));
     193             : }
     194             : 
     195             : /**
     196             :  * radix_tree_deref_retry       - check radix_tree_deref_slot
     197             :  * @arg:        pointer returned by radix_tree_deref_slot
     198             :  * Returns:     0 if retry is not required, otherwise retry is required
     199             :  *
     200             :  * radix_tree_deref_retry must be used with radix_tree_deref_slot.
     201             :  */
     202             : static inline int radix_tree_deref_retry(void *arg)
     203             : {
     204             :         return unlikely(radix_tree_is_internal_node(arg));
     205             : }
     206             : 
     207             : /**
     208             :  * radix_tree_exception - radix_tree_deref_slot returned either exception?
     209             :  * @arg:        value returned by radix_tree_deref_slot
     210             :  * Returns:     0 if well-aligned pointer, non-0 if either kind of exception.
     211             :  */
     212             : static inline int radix_tree_exception(void *arg)
     213             : {
     214             :         return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
     215             : }
     216             : 
     217             : int radix_tree_insert(struct radix_tree_root *, unsigned long index,
     218             :                         void *);
     219             : void *__radix_tree_lookup(const struct radix_tree_root *, unsigned long index,
     220             :                           struct radix_tree_node **nodep, void __rcu ***slotp);
     221             : void *radix_tree_lookup(const struct radix_tree_root *, unsigned long);
     222             : void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *,
     223             :                                         unsigned long index);
     224             : void __radix_tree_replace(struct radix_tree_root *, struct radix_tree_node *,
     225             :                           void __rcu **slot, void *entry);
     226             : void radix_tree_iter_replace(struct radix_tree_root *,
     227             :                 const struct radix_tree_iter *, void __rcu **slot, void *entry);
     228             : void radix_tree_replace_slot(struct radix_tree_root *,
     229             :                              void __rcu **slot, void *entry);
     230             : void radix_tree_iter_delete(struct radix_tree_root *,
     231             :                         struct radix_tree_iter *iter, void __rcu **slot);
     232             : void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
     233             : void *radix_tree_delete(struct radix_tree_root *, unsigned long);
     234             : unsigned int radix_tree_gang_lookup(const struct radix_tree_root *,
     235             :                         void **results, unsigned long first_index,
     236             :                         unsigned int max_items);
     237             : int radix_tree_preload(gfp_t gfp_mask);
     238             : int radix_tree_maybe_preload(gfp_t gfp_mask);
     239             : void radix_tree_init(void);
     240             : void *radix_tree_tag_set(struct radix_tree_root *,
     241             :                         unsigned long index, unsigned int tag);
     242             : void *radix_tree_tag_clear(struct radix_tree_root *,
     243             :                         unsigned long index, unsigned int tag);
     244             : int radix_tree_tag_get(const struct radix_tree_root *,
     245             :                         unsigned long index, unsigned int tag);
     246             : void radix_tree_iter_tag_clear(struct radix_tree_root *,
     247             :                 const struct radix_tree_iter *iter, unsigned int tag);
     248             : unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *,
     249             :                 void **results, unsigned long first_index,
     250             :                 unsigned int max_items, unsigned int tag);
     251             : unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *,
     252             :                 void __rcu ***results, unsigned long first_index,
     253             :                 unsigned int max_items, unsigned int tag);
     254             : int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag);
     255             : 
     256           0 : static inline void radix_tree_preload_end(void)
     257             : {
     258           0 :         local_unlock(&radix_tree_preloads.lock);
     259           0 : }
     260             : 
     261             : void __rcu **idr_get_free(struct radix_tree_root *root,
     262             :                               struct radix_tree_iter *iter, gfp_t gfp,
     263             :                               unsigned long max);
     264             : 
     265             : enum {
     266             :         RADIX_TREE_ITER_TAG_MASK = 0x0f,        /* tag index in lower nybble */
     267             :         RADIX_TREE_ITER_TAGGED   = 0x10,        /* lookup tagged slots */
     268             :         RADIX_TREE_ITER_CONTIG   = 0x20,        /* stop at first hole */
     269             : };
     270             : 
     271             : /**
     272             :  * radix_tree_iter_init - initialize radix tree iterator
     273             :  *
     274             :  * @iter:       pointer to iterator state
     275             :  * @start:      iteration starting index
     276             :  * Returns:     NULL
     277             :  */
     278             : static __always_inline void __rcu **
     279       11327 : radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
     280             : {
     281             :         /*
     282             :          * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
     283             :          * in the case of a successful tagged chunk lookup.  If the lookup was
     284             :          * unsuccessful or non-tagged then nobody cares about ->tags.
     285             :          *
     286             :          * Set index to zero to bypass next_index overflow protection.
     287             :          * See the comment in radix_tree_next_chunk() for details.
     288             :          */
     289       11327 :         iter->index = 0;
     290       11327 :         iter->next_index = start;
     291       11327 :         return NULL;
     292             : }
     293             : 
     294             : /**
     295             :  * radix_tree_next_chunk - find next chunk of slots for iteration
     296             :  *
     297             :  * @root:       radix tree root
     298             :  * @iter:       iterator state
     299             :  * @flags:      RADIX_TREE_ITER_* flags and tag index
     300             :  * Returns:     pointer to chunk first slot, or NULL if there no more left
     301             :  *
     302             :  * This function looks up the next chunk in the radix tree starting from
     303             :  * @iter->next_index.  It returns a pointer to the chunk's first slot.
     304             :  * Also it fills @iter with data about chunk: position in the tree (index),
     305             :  * its end (next_index), and constructs a bit mask for tagged iterating (tags).
     306             :  */
     307             : void __rcu **radix_tree_next_chunk(const struct radix_tree_root *,
     308             :                              struct radix_tree_iter *iter, unsigned flags);
     309             : 
     310             : /**
     311             :  * radix_tree_iter_lookup - look up an index in the radix tree
     312             :  * @root: radix tree root
     313             :  * @iter: iterator state
     314             :  * @index: key to look up
     315             :  *
     316             :  * If @index is present in the radix tree, this function returns the slot
     317             :  * containing it and updates @iter to describe the entry.  If @index is not
     318             :  * present, it returns NULL.
     319             :  */
     320             : static inline void __rcu **
     321             : radix_tree_iter_lookup(const struct radix_tree_root *root,
     322             :                         struct radix_tree_iter *iter, unsigned long index)
     323             : {
     324             :         radix_tree_iter_init(iter, index);
     325             :         return radix_tree_next_chunk(root, iter, RADIX_TREE_ITER_CONTIG);
     326             : }
     327             : 
     328             : /**
     329             :  * radix_tree_iter_retry - retry this chunk of the iteration
     330             :  * @iter:       iterator state
     331             :  *
     332             :  * If we iterate over a tree protected only by the RCU lock, a race
     333             :  * against deletion or creation may result in seeing a slot for which
     334             :  * radix_tree_deref_retry() returns true.  If so, call this function
     335             :  * and continue the iteration.
     336             :  */
     337             : static inline __must_check
     338           0 : void __rcu **radix_tree_iter_retry(struct radix_tree_iter *iter)
     339             : {
     340           0 :         iter->next_index = iter->index;
     341           0 :         iter->tags = 0;
     342           0 :         return NULL;
     343             : }
     344             : 
     345             : static inline unsigned long
     346           0 : __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
     347             : {
     348           0 :         return iter->index + slots;
     349             : }
     350             : 
     351             : /**
     352             :  * radix_tree_iter_resume - resume iterating when the chunk may be invalid
     353             :  * @slot: pointer to current slot
     354             :  * @iter: iterator state
     355             :  * Returns: New slot pointer
     356             :  *
     357             :  * If the iterator needs to release then reacquire a lock, the chunk may
     358             :  * have been invalidated by an insertion or deletion.  Call this function
     359             :  * before releasing the lock to continue the iteration from the next index.
     360             :  */
     361             : void __rcu **__must_check radix_tree_iter_resume(void __rcu **slot,
     362             :                                         struct radix_tree_iter *iter);
     363             : 
     364             : /**
     365             :  * radix_tree_chunk_size - get current chunk size
     366             :  *
     367             :  * @iter:       pointer to radix tree iterator
     368             :  * Returns:     current chunk size
     369             :  */
     370             : static __always_inline long
     371           0 : radix_tree_chunk_size(struct radix_tree_iter *iter)
     372             : {
     373           0 :         return iter->next_index - iter->index;
     374             : }
     375             : 
     376             : /**
     377             :  * radix_tree_next_slot - find next slot in chunk
     378             :  *
     379             :  * @slot:       pointer to current slot
     380             :  * @iter:       pointer to iterator state
     381             :  * @flags:      RADIX_TREE_ITER_*, should be constant
     382             :  * Returns:     pointer to next slot, or NULL if there no more left
     383             :  *
     384             :  * This function updates @iter->index in the case of a successful lookup.
     385             :  * For tagged lookup it also eats @iter->tags.
     386             :  *
     387             :  * There are several cases where 'slot' can be passed in as NULL to this
     388             :  * function.  These cases result from the use of radix_tree_iter_resume() or
     389             :  * radix_tree_iter_retry().  In these cases we don't end up dereferencing
     390             :  * 'slot' because either:
     391             :  * a) we are doing tagged iteration and iter->tags has been set to 0, or
     392             :  * b) we are doing non-tagged iteration, and iter->index and iter->next_index
     393             :  *    have been set up so that radix_tree_chunk_size() returns 1 or 0.
     394             :  */
     395           0 : static __always_inline void __rcu **radix_tree_next_slot(void __rcu **slot,
     396             :                                 struct radix_tree_iter *iter, unsigned flags)
     397             : {
     398           0 :         if (flags & RADIX_TREE_ITER_TAGGED) {
     399           0 :                 iter->tags >>= 1;
     400           0 :                 if (unlikely(!iter->tags))
     401             :                         return NULL;
     402           0 :                 if (likely(iter->tags & 1ul)) {
     403           0 :                         iter->index = __radix_tree_iter_add(iter, 1);
     404           0 :                         slot++;
     405           0 :                         goto found;
     406             :                 }
     407           0 :                 if (!(flags & RADIX_TREE_ITER_CONTIG)) {
     408           0 :                         unsigned offset = __ffs(iter->tags);
     409             : 
     410           0 :                         iter->tags >>= offset++;
     411           0 :                         iter->index = __radix_tree_iter_add(iter, offset);
     412           0 :                         slot += offset;
     413           0 :                         goto found;
     414             :                 }
     415             :         } else {
     416           0 :                 long count = radix_tree_chunk_size(iter);
     417             : 
     418           0 :                 while (--count > 0) {
     419           0 :                         slot++;
     420           0 :                         iter->index = __radix_tree_iter_add(iter, 1);
     421             : 
     422           0 :                         if (likely(*slot))
     423           0 :                                 goto found;
     424             :                         if (flags & RADIX_TREE_ITER_CONTIG) {
     425             :                                 /* forbid switching to the next chunk */
     426             :                                 iter->next_index = 0;
     427             :                                 break;
     428             :                         }
     429             :                 }
     430             :         }
     431             :         return NULL;
     432             : 
     433             :  found:
     434             :         return slot;
     435             : }
     436             : 
     437             : /**
     438             :  * radix_tree_for_each_slot - iterate over non-empty slots
     439             :  *
     440             :  * @slot:       the void** variable for pointer to slot
     441             :  * @root:       the struct radix_tree_root pointer
     442             :  * @iter:       the struct radix_tree_iter pointer
     443             :  * @start:      iteration starting index
     444             :  *
     445             :  * @slot points to radix tree slot, @iter->index contains its index.
     446             :  */
     447             : #define radix_tree_for_each_slot(slot, root, iter, start)               \
     448             :         for (slot = radix_tree_iter_init(iter, start) ;                 \
     449             :              slot || (slot = radix_tree_next_chunk(root, iter, 0)) ;    \
     450             :              slot = radix_tree_next_slot(slot, iter, 0))
     451             : 
     452             : /**
     453             :  * radix_tree_for_each_tagged - iterate over tagged slots
     454             :  *
     455             :  * @slot:       the void** variable for pointer to slot
     456             :  * @root:       the struct radix_tree_root pointer
     457             :  * @iter:       the struct radix_tree_iter pointer
     458             :  * @start:      iteration starting index
     459             :  * @tag:        tag index
     460             :  *
     461             :  * @slot points to radix tree slot, @iter->index contains its index.
     462             :  */
     463             : #define radix_tree_for_each_tagged(slot, root, iter, start, tag)        \
     464             :         for (slot = radix_tree_iter_init(iter, start) ;                 \
     465             :              slot || (slot = radix_tree_next_chunk(root, iter,          \
     466             :                               RADIX_TREE_ITER_TAGGED | tag)) ;          \
     467             :              slot = radix_tree_next_slot(slot, iter,                    \
     468             :                                 RADIX_TREE_ITER_TAGGED | tag))
     469             : 
     470             : #endif /* _LINUX_RADIX_TREE_H */

Generated by: LCOV version 1.14