include/linux/generic-radix-tree.h

0001 #ifndef _LINUX_GENERIC_RADIX_TREE_H
0002 #define _LINUX_GENERIC_RADIX_TREE_H
0003
0004 /**
0005  * DOC: Generic radix trees/sparse arrays
0006  *
0007  * Very simple and minimalistic, supporting arbitrary size entries up to
0008  * PAGE_SIZE.
0009  *
0010  * A genradix is defined with the type it will store, like so:
0011  *
0012  * static GENRADIX(struct foo) foo_genradix;
0013  *
0014  * The main operations are:
0015  *
0016  * - genradix_init(radix) - initialize an empty genradix
0017  *
0018  * - genradix_free(radix) - free all memory owned by the genradix and
0019  *   reinitialize it
0020  *
0021  * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning
0022  *   NULL if that entry does not exist
0023  *
0024  * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry,
0025  *   allocating it if necessary
0026  *
0027  * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix
0028  *
0029  * The radix tree allocates one page of entries at a time, so entries may exist
0030  * that were never explicitly allocated - they will be initialized to all
0031  * zeroes.
0032  *
0033  * Internally, a genradix is just a radix tree of pages, and indexing works in
0034  * terms of byte offsets. The wrappers in this header file use sizeof on the
0035  * type the radix contains to calculate a byte offset from the index - see
0036  * __idx_to_offset.
0037  */
0038
0039 #include <asm/page.h>
0040 #include <linux/bug.h>
0041 #include <linux/log2.h>
0042 #include <linux/math.h>
0043 #include <linux/types.h>
0044
0045 struct genradix_root;
0046
0047 struct __genradix {
0048     struct genradix_root        *root;
0049 };
0050
0051 /*
0052  * NOTE: currently, sizeof(_type) must not be larger than PAGE_SIZE:
0053  */
0054
0055 #define __GENRADIX_INITIALIZER                  \
0056     {                           \
0057         .tree = {                   \
0058             .root = NULL,               \
0059         }                       \
0060     }
0061
0062 /*
0063  * We use a 0 size array to stash the type we're storing without taking any
0064  * space at runtime - then the various accessor macros can use typeof() to get
0065  * to it for casts/sizeof - we also force the alignment so that storing a type
0066  * with a ridiculous alignment doesn't blow up the alignment or size of the
0067  * genradix.
0068  */
0069
0070 #define GENRADIX(_type)                     \
0071 struct {                            \
0072     struct __genradix   tree;               \
0073     _type           type[0] __aligned(1);       \
0074 }
0075
0076 #define DEFINE_GENRADIX(_name, _type)               \
0077     GENRADIX(_type) _name = __GENRADIX_INITIALIZER
0078
0079 /**
0080  * genradix_init - initialize a genradix
0081  * @_radix: genradix to initialize
0082  *
0083  * Does not fail
0084  */
0085 #define genradix_init(_radix)                   \
0086 do {                                \
0087     *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER;   \
0088 } while (0)
0089
0090 void __genradix_free(struct __genradix *);
0091
0092 /**
0093  * genradix_free: free all memory owned by a genradix
0094  * @_radix: the genradix to free
0095  *
0096  * After freeing, @_radix will be reinitialized and empty
0097  */
0098 #define genradix_free(_radix)   __genradix_free(&(_radix)->tree)
0099
0100 static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
0101 {
0102     if (__builtin_constant_p(obj_size))
0103         BUILD_BUG_ON(obj_size > PAGE_SIZE);
0104     else
0105         BUG_ON(obj_size > PAGE_SIZE);
0106
0107     if (!is_power_of_2(obj_size)) {
0108         size_t objs_per_page = PAGE_SIZE / obj_size;
0109
0110         return (idx / objs_per_page) * PAGE_SIZE +
0111             (idx % objs_per_page) * obj_size;
0112     } else {
0113         return idx * obj_size;
0114     }
0115 }
0116
0117 #define __genradix_cast(_radix)     (typeof((_radix)->type[0]) *)
0118 #define __genradix_obj_size(_radix) sizeof((_radix)->type[0])
0119 #define __genradix_idx_to_offset(_radix, _idx)          \
0120     __idx_to_offset(_idx, __genradix_obj_size(_radix))
0121
0122 void *__genradix_ptr(struct __genradix *, size_t);
0123
0124 /**
0125  * genradix_ptr - get a pointer to a genradix entry
0126  * @_radix: genradix to access
0127  * @_idx:   index to fetch
0128  *
0129  * Returns a pointer to entry at @_idx, or NULL if that entry does not exist.
0130  */
0131 #define genradix_ptr(_radix, _idx)              \
0132     (__genradix_cast(_radix)                \
0133      __genradix_ptr(&(_radix)->tree,            \
0134             __genradix_idx_to_offset(_radix, _idx)))
0135
0136 void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
0137
0138 /**
0139  * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
0140  *          if necessary
0141  * @_radix: genradix to access
0142  * @_idx:   index to fetch
0143  * @_gfp:   gfp mask
0144  *
0145  * Returns a pointer to entry at @_idx, or NULL on allocation failure
0146  */
0147 #define genradix_ptr_alloc(_radix, _idx, _gfp)          \
0148     (__genradix_cast(_radix)                \
0149      __genradix_ptr_alloc(&(_radix)->tree,          \
0150             __genradix_idx_to_offset(_radix, _idx), \
0151             _gfp))
0152
0153 struct genradix_iter {
0154     size_t          offset;
0155     size_t          pos;
0156 };
0157
0158 /**
0159  * genradix_iter_init - initialize a genradix_iter
0160  * @_radix: genradix that will be iterated over
0161  * @_idx:   index to start iterating from
0162  */
0163 #define genradix_iter_init(_radix, _idx)            \
0164     ((struct genradix_iter) {               \
0165         .pos    = (_idx),               \
0166         .offset = __genradix_idx_to_offset((_radix), (_idx)),\
0167     })
0168
0169 void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
0170
0171 /**
0172  * genradix_iter_peek - get first entry at or above iterator's current
0173  *          position
0174  * @_iter:  a genradix_iter
0175  * @_radix: genradix being iterated over
0176  *
0177  * If no more entries exist at or above @_iter's current position, returns NULL
0178  */
0179 #define genradix_iter_peek(_iter, _radix)           \
0180     (__genradix_cast(_radix)                \
0181      __genradix_iter_peek(_iter, &(_radix)->tree,       \
0182                   PAGE_SIZE / __genradix_obj_size(_radix)))
0183
0184 static inline void __genradix_iter_advance(struct genradix_iter *iter,
0185                        size_t obj_size)
0186 {
0187     iter->offset += obj_size;
0188
0189     if (!is_power_of_2(obj_size) &&
0190         (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
0191         iter->offset = round_up(iter->offset, PAGE_SIZE);
0192
0193     iter->pos++;
0194 }
0195
0196 #define genradix_iter_advance(_iter, _radix)            \
0197     __genradix_iter_advance(_iter, __genradix_obj_size(_radix))
0198
0199 #define genradix_for_each_from(_radix, _iter, _p, _start)   \
0200     for (_iter = genradix_iter_init(_radix, _start);    \
0201          (_p = genradix_iter_peek(&_iter, _radix)) != NULL; \
0202          genradix_iter_advance(&_iter, _radix))
0203
0204 /**
0205  * genradix_for_each - iterate over entry in a genradix
0206  * @_radix: genradix to iterate over
0207  * @_iter:  a genradix_iter to track current position
0208  * @_p:     pointer to genradix entry type
0209  *
0210  * On every iteration, @_p will point to the current entry, and @_iter.pos
0211  * will be the current entry's index.
0212  */
0213 #define genradix_for_each(_radix, _iter, _p)            \
0214     genradix_for_each_from(_radix, _iter, _p, 0)
0215
0216 int __genradix_prealloc(struct __genradix *, size_t, gfp_t);
0217
0218 /**
0219  * genradix_prealloc - preallocate entries in a generic radix tree
0220  * @_radix: genradix to preallocate
0221  * @_nr:    number of entries to preallocate
0222  * @_gfp:   gfp mask
0223  *
0224  * Returns 0 on success, -ENOMEM on failure
0225  */
0226 #define genradix_prealloc(_radix, _nr, _gfp)            \
0227      __genradix_prealloc(&(_radix)->tree,           \
0228             __genradix_idx_to_offset(_radix, _nr + 1),\
0229             _gfp)
0230
0231
0232 #endif /* _LINUX_GENERIC_RADIX_TREE_H */