Branch data     Line data    Source code

       1                 :            : #ifndef _LINUX_GENERIC_RADIX_TREE_H
       2                 :            : #define _LINUX_GENERIC_RADIX_TREE_H
       3                 :            : 
       4                 :            : /**
       5                 :            :  * DOC: Generic radix trees/sparse arrays
       6                 :            :  *
       7                 :            :  * Very simple and minimalistic, supporting arbitrary size entries up to
       8                 :            :  * PAGE_SIZE.
       9                 :            :  *
      10                 :            :  * A genradix is defined with the type it will store, like so:
      11                 :            :  *
      12                 :            :  * static GENRADIX(struct foo) foo_genradix;
      13                 :            :  *
      14                 :            :  * The main operations are:
      15                 :            :  *
      16                 :            :  * - genradix_init(radix) - initialize an empty genradix
      17                 :            :  *
      18                 :            :  * - genradix_free(radix) - free all memory owned by the genradix and
      19                 :            :  *   reinitialize it
      20                 :            :  *
      21                 :            :  * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning
      22                 :            :  *   NULL if that entry does not exist
      23                 :            :  *
      24                 :            :  * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry,
      25                 :            :  *   allocating it if necessary
      26                 :            :  *
      27                 :            :  * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix
      28                 :            :  *
      29                 :            :  * The radix tree allocates one page of entries at a time, so entries may exist
      30                 :            :  * that were never explicitly allocated - they will be initialized to all
      31                 :            :  * zeroes.
      32                 :            :  *
      33                 :            :  * Internally, a genradix is just a radix tree of pages, and indexing works in
      34                 :            :  * terms of byte offsets. The wrappers in this header file use sizeof on the
      35                 :            :  * type the radix contains to calculate a byte offset from the index - see
      36                 :            :  * __idx_to_offset.
      37                 :            :  */
      38                 :            : 
      39                 :            : #include <asm/page.h>
      40                 :            : #include <linux/bug.h>
      41                 :            : #include <linux/kernel.h>
      42                 :            : #include <linux/log2.h>
      43                 :            : 
      44                 :            : struct genradix_root;
      45                 :            : 
      46                 :            : struct __genradix {
      47                 :            :         struct genradix_root __rcu      *root;
      48                 :            : };
      49                 :            : 
      50                 :            : /*
      51                 :            :  * NOTE: currently, sizeof(_type) must not be larger than PAGE_SIZE:
      52                 :            :  */
      53                 :            : 
      54                 :            : #define __GENRADIX_INITIALIZER                                  \
      55                 :            :         {                                                       \
      56                 :            :                 .tree = {                                       \
      57                 :            :                         .root = NULL,                           \
      58                 :            :                 }                                               \
      59                 :            :         }
      60                 :            : 
      61                 :            : /*
      62                 :            :  * We use a 0 size array to stash the type we're storing without taking any
      63                 :            :  * space at runtime - then the various accessor macros can use typeof() to get
      64                 :            :  * to it for casts/sizeof - we also force the alignment so that storing a type
      65                 :            :  * with a ridiculous alignment doesn't blow up the alignment or size of the
      66                 :            :  * genradix.
      67                 :            :  */
      68                 :            : 
      69                 :            : #define GENRADIX(_type)                                         \
      70                 :            : struct {                                                        \
      71                 :            :         struct __genradix       tree;                           \
      72                 :            :         _type                   type[0] __aligned(1);           \
      73                 :            : }
      74                 :            : 
      75                 :            : #define DEFINE_GENRADIX(_name, _type)                           \
      76                 :            :         GENRADIX(_type) _name = __GENRADIX_INITIALIZER
      77                 :            : 
      78                 :            : /**
      79                 :            :  * genradix_init - initialize a genradix
      80                 :            :  * @_radix:     genradix to initialize
      81                 :            :  *
      82                 :            :  * Does not fail
      83                 :            :  */
      84                 :            : #define genradix_init(_radix)                                   \
      85                 :            : do {                                                            \
      86                 :            :         *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER;   \
      87                 :            : } while (0)
      88                 :            : 
      89                 :            : void __genradix_free(struct __genradix *);
      90                 :            : 
      91                 :            : /**
      92                 :            :  * genradix_free: free all memory owned by a genradix
      93                 :            :  * @_radix: the genradix to free
      94                 :            :  *
      95                 :            :  * After freeing, @_radix will be reinitialized and empty
      96                 :            :  */
      97                 :            : #define genradix_free(_radix)   __genradix_free(&(_radix)->tree)
      98                 :            : 
      99                 :          0 : static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
     100                 :            : {
     101                 :          0 :         if (__builtin_constant_p(obj_size))
     102                 :          0 :                 BUILD_BUG_ON(obj_size > PAGE_SIZE);
     103                 :            :         else
     104                 :          0 :                 BUG_ON(obj_size > PAGE_SIZE);
     105                 :            : 
     106                 :          0 :         if (!is_power_of_2(obj_size)) {
     107                 :          0 :                 size_t objs_per_page = PAGE_SIZE / obj_size;
     108                 :            : 
     109                 :          0 :                 return (idx / objs_per_page) * PAGE_SIZE +
     110                 :          0 :                         (idx % objs_per_page) * obj_size;
     111                 :            :         } else {
     112                 :          0 :                 return idx * obj_size;
     113                 :            :         }
     114                 :            : }
     115                 :            : 
     116                 :            : #define __genradix_cast(_radix)         (typeof((_radix)->type[0]) *)
     117                 :            : #define __genradix_obj_size(_radix)     sizeof((_radix)->type[0])
     118                 :            : #define __genradix_idx_to_offset(_radix, _idx)                  \
     119                 :            :         __idx_to_offset(_idx, __genradix_obj_size(_radix))
     120                 :            : 
     121                 :            : void *__genradix_ptr(struct __genradix *, size_t);
     122                 :            : 
     123                 :            : /**
     124                 :            :  * genradix_ptr - get a pointer to a genradix entry
     125                 :            :  * @_radix:     genradix to access
     126                 :            :  * @_idx:       index to fetch
     127                 :            :  *
     128                 :            :  * Returns a pointer to entry at @_idx, or NULL if that entry does not exist.
     129                 :            :  */
     130                 :            : #define genradix_ptr(_radix, _idx)                              \
     131                 :            :         (__genradix_cast(_radix)                                \
     132                 :            :          __genradix_ptr(&(_radix)->tree,                 \
     133                 :            :                         __genradix_idx_to_offset(_radix, _idx)))
     134                 :            : 
     135                 :            : void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
     136                 :            : 
     137                 :            : /**
     138                 :            :  * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
     139                 :            :  *                      if necessary
     140                 :            :  * @_radix:     genradix to access
     141                 :            :  * @_idx:       index to fetch
     142                 :            :  * @_gfp:       gfp mask
     143                 :            :  *
     144                 :            :  * Returns a pointer to entry at @_idx, or NULL on allocation failure
     145                 :            :  */
     146                 :            : #define genradix_ptr_alloc(_radix, _idx, _gfp)                  \
     147                 :            :         (__genradix_cast(_radix)                                \
     148                 :            :          __genradix_ptr_alloc(&(_radix)->tree,                   \
     149                 :            :                         __genradix_idx_to_offset(_radix, _idx), \
     150                 :            :                         _gfp))
     151                 :            : 
     152                 :            : struct genradix_iter {
     153                 :            :         size_t                  offset;
     154                 :            :         size_t                  pos;
     155                 :            : };
     156                 :            : 
     157                 :            : /**
     158                 :            :  * genradix_iter_init - initialize a genradix_iter
     159                 :            :  * @_radix:     genradix that will be iterated over
     160                 :            :  * @_idx:       index to start iterating from
     161                 :            :  */
     162                 :            : #define genradix_iter_init(_radix, _idx)                        \
     163                 :            :         ((struct genradix_iter) {                               \
     164                 :            :                 .pos    = (_idx),                               \
     165                 :            :                 .offset = __genradix_idx_to_offset((_radix), (_idx)),\
     166                 :            :         })
     167                 :            : 
     168                 :            : void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
     169                 :            : 
     170                 :            : /**
     171                 :            :  * genradix_iter_peek - get first entry at or above iterator's current
     172                 :            :  *                      position
     173                 :            :  * @_iter:      a genradix_iter
     174                 :            :  * @_radix:     genradix being iterated over
     175                 :            :  *
     176                 :            :  * If no more entries exist at or above @_iter's current position, returns NULL
     177                 :            :  */
     178                 :            : #define genradix_iter_peek(_iter, _radix)                       \
     179                 :            :         (__genradix_cast(_radix)                                \
     180                 :            :          __genradix_iter_peek(_iter, &(_radix)->tree,            \
     181                 :            :                               PAGE_SIZE / __genradix_obj_size(_radix)))
     182                 :            : 
     183                 :            : static inline void __genradix_iter_advance(struct genradix_iter *iter,
     184                 :            :                                            size_t obj_size)
     185                 :            : {
     186                 :            :         iter->offset += obj_size;
     187                 :            : 
     188                 :            :         if (!is_power_of_2(obj_size) &&
     189                 :            :             (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
     190                 :            :                 iter->offset = round_up(iter->offset, PAGE_SIZE);
     191                 :            : 
     192                 :            :         iter->pos++;
     193                 :            : }
     194                 :            : 
     195                 :            : #define genradix_iter_advance(_iter, _radix)                    \
     196                 :            :         __genradix_iter_advance(_iter, __genradix_obj_size(_radix))
     197                 :            : 
     198                 :            : #define genradix_for_each_from(_radix, _iter, _p, _start)       \
     199                 :            :         for (_iter = genradix_iter_init(_radix, _start);        \
     200                 :            :              (_p = genradix_iter_peek(&_iter, _radix)) != NULL;     \
     201                 :            :              genradix_iter_advance(&_iter, _radix))
     202                 :            : 
     203                 :            : /**
     204                 :            :  * genradix_for_each - iterate over entry in a genradix
     205                 :            :  * @_radix:     genradix to iterate over
     206                 :            :  * @_iter:      a genradix_iter to track current position
     207                 :            :  * @_p:         pointer to genradix entry type
     208                 :            :  *
     209                 :            :  * On every iteration, @_p will point to the current entry, and @_iter.pos
     210                 :            :  * will be the current entry's index.
     211                 :            :  */
     212                 :            : #define genradix_for_each(_radix, _iter, _p)                    \
     213                 :            :         genradix_for_each_from(_radix, _iter, _p, 0)
     214                 :            : 
     215                 :            : int __genradix_prealloc(struct __genradix *, size_t, gfp_t);
     216                 :            : 
     217                 :            : /**
     218                 :            :  * genradix_prealloc - preallocate entries in a generic radix tree
     219                 :            :  * @_radix:     genradix to preallocate
     220                 :            :  * @_nr:        number of entries to preallocate
     221                 :            :  * @_gfp:       gfp mask
     222                 :            :  *
     223                 :            :  * Returns 0 on success, -ENOMEM on failure
     224                 :            :  */
     225                 :            : #define genradix_prealloc(_radix, _nr, _gfp)                    \
     226                 :            :          __genradix_prealloc(&(_radix)->tree,                    \
     227                 :            :                         __genradix_idx_to_offset(_radix, _nr + 1),\
     228                 :            :                         _gfp)
     229                 :            : 
     230                 :            : 
     231                 :            : #endif /* _LINUX_GENERIC_RADIX_TREE_H */