Re: [PATCH 1/6] Generic radix trees
On Sat, May 26, 2018 at 1:56 PM, Kent Overstreet wrote: > On Sat, May 26, 2018 at 11:16:42AM +0800, Liu Bo wrote: >> > +/* >> > + * Returns pointer to the specified byte @offset within @radix, >> > allocating it if >> > + * necessary - newly allocated slots are always zeroed out: >> > + */ >> > +void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, >> > + gfp_t gfp_mask) >> > +{ >> > + struct genradix_node **n; >> >> Any reason that " struct genradix_node ** " is used here instead of " >> struct genradix_node * "? >> >> Looks like this function only manipulates *n, am I missing something? > > It stores to *n, when it has to allocate a node (including the root) I see, thanks for the explanation. thanks, liubo
Re: [PATCH 1/6] Generic radix trees
On Sat, May 26, 2018 at 11:16:42AM +0800, Liu Bo wrote: > > +/* > > + * Returns pointer to the specified byte @offset within @radix, allocating > > it if > > + * necessary - newly allocated slots are always zeroed out: > > + */ > > +void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, > > + gfp_t gfp_mask) > > +{ > > + struct genradix_node **n; > > Any reason that " struct genradix_node ** " is used here instead of " > struct genradix_node * "? > > Looks like this function only manipulates *n, am I missing something? It stores to *n, when it has to allocate a node (including the root)
Re: [PATCH 1/6] Generic radix trees
Hi Kent, (Add all ML to cc this time.) On Wed, May 23, 2018 at 9:18 AM, Kent Overstreet wrote: > Very simple radix tree implementation that supports storing arbitrary > size entries, up to PAGE_SIZE - upcoming patches will convert existing > flex_array users to genradixes. The new genradix code has a much simpler > API and implementation, and doesn't have a hard limit on the number of > elements like flex_array does. > > Signed-off-by: Kent Overstreet > --- > include/linux/generic-radix-tree.h | 222 + > lib/Makefile | 3 +- > lib/generic-radix-tree.c | 180 +++ > 3 files changed, 404 insertions(+), 1 deletion(-) > create mode 100644 include/linux/generic-radix-tree.h > create mode 100644 lib/generic-radix-tree.c > > diff --git a/include/linux/generic-radix-tree.h > b/include/linux/generic-radix-tree.h > new file mode 100644 > index 00..3328813322 > --- /dev/null > +++ b/include/linux/generic-radix-tree.h > @@ -0,0 +1,222 @@ > +#ifndef _LINUX_GENERIC_RADIX_TREE_H > +#define _LINUX_GENERIC_RADIX_TREE_H > + > +/* > + * Generic radix trees/sparse arrays: > + * > + * Very simple and minimalistic, supporting arbitrary size entries up to > + * PAGE_SIZE. > + * > + * A genradix is defined with the type it will store, like so: > + * static GENRADIX(struct foo) foo_genradix; > + * > + * The main operations are: > + * - genradix_init(radix) - initialize an empty genradix > + * > + * - genradix_free(radix) - free all memory owned by the genradix and > + * reinitialize it > + * > + * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning > + * NULL if that entry does not exist > + * > + * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry, > + * allocating it if necessary > + * > + * - genradix_for_each(radix, iter, p) - iterate over each entry in a > genradix > + * > + * The radix tree allocates one page of entries at a time, so entries may > exist > + * that were never explicitly allocated - they will be initialized to all > + * zeroes. > + * > + * Internally, a genradix is just a radix tree of pages, and indexing works > in > + * terms of byte offsets. The wrappers in this header file use sizeof on the > + * type the radix contains to calculate a byte offset from the index - see > + * __idx_to_offset. > + */ > + > +#include > +#include > +#include > +#include > + > +struct genradix_node; > + > +struct __genradix { > + struct genradix_node*root; > + size_t depth; > +}; > + > +#define __GENRADIX_INITIALIZER \ > + { \ > + .tree = { \ > + .root = NULL, \ > + .depth = 0, \ > + } \ > + } > + > +/* > + * We use a 0 size array to stash the type we're storing without taking any > + * space at runtime - then the various accessor macros can use typeof() to > get > + * to it for casts/sizeof - we also force the alignment so that storing a > type > + * with a ridiculous alignment doesn't blow up the alignment or size of the > + * genradix. > + */ > + > +#define GENRADIX(_type)\ > +struct { \ > + struct __genradix tree; \ > + _type type[0] __aligned(1); \ > +} > + > +#define DEFINE_GENRADIX(_name, _type) \ > + GENRADIX(_type) _name = __GENRADIX_INITIALIZER > + > +/** > + * genradix_init - initialize a genradix > + * @_radix:genradix to initialize > + * > + * Does not fail > + */ > +#define genradix_init(_radix) \ > +do { \ > + *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \ > +} while (0) > + > +void __genradix_free(struct __genradix *); > + > +/** > + * genradix_free: free all memory owned by a genradix > + * > + * After freeing, @_radix will be reinitialized and empty > + */ > +#define genradix_free(_radix) __genradix_free(&(_radix)->tree) > + > +static inline size_t __idx_to_offset(size_t idx, size_t obj_size) > +{ > + if (__builtin_constant_p(obj_size)) > + BUILD_BUG_ON(obj_size > PAGE_SIZE); > + else > + BUG_ON(obj_size > PAGE_SIZE); > + > + if (!is_power_of_2(obj_size)) { > + size_t objs_per_page = PAGE_SIZE / obj_size; > + > + return (idx / objs_per_page) * PAGE_SIZE + > + (idx % objs_per_page) * obj_size; > + } else { > + return idx * obj_size; > + } > +} > + > +#define __genradix_cast(_radix)
[PATCH 1/6] Generic radix trees
Very simple radix tree implementation that supports storing arbitrary size entries, up to PAGE_SIZE - upcoming patches will convert existing flex_array users to genradixes. The new genradix code has a much simpler API and implementation, and doesn't have a hard limit on the number of elements like flex_array does. Signed-off-by: Kent Overstreet --- include/linux/generic-radix-tree.h | 222 + lib/Makefile | 3 +- lib/generic-radix-tree.c | 180 +++ 3 files changed, 404 insertions(+), 1 deletion(-) create mode 100644 include/linux/generic-radix-tree.h create mode 100644 lib/generic-radix-tree.c diff --git a/include/linux/generic-radix-tree.h b/include/linux/generic-radix-tree.h new file mode 100644 index 00..3328813322 --- /dev/null +++ b/include/linux/generic-radix-tree.h @@ -0,0 +1,222 @@ +#ifndef _LINUX_GENERIC_RADIX_TREE_H +#define _LINUX_GENERIC_RADIX_TREE_H + +/* + * Generic radix trees/sparse arrays: + * + * Very simple and minimalistic, supporting arbitrary size entries up to + * PAGE_SIZE. + * + * A genradix is defined with the type it will store, like so: + * static GENRADIX(struct foo) foo_genradix; + * + * The main operations are: + * - genradix_init(radix) - initialize an empty genradix + * + * - genradix_free(radix) - free all memory owned by the genradix and + * reinitialize it + * + * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning + * NULL if that entry does not exist + * + * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry, + * allocating it if necessary + * + * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix + * + * The radix tree allocates one page of entries at a time, so entries may exist + * that were never explicitly allocated - they will be initialized to all + * zeroes. + * + * Internally, a genradix is just a radix tree of pages, and indexing works in + * terms of byte offsets. The wrappers in this header file use sizeof on the + * type the radix contains to calculate a byte offset from the index - see + * __idx_to_offset. + */ + +#include +#include +#include +#include + +struct genradix_node; + +struct __genradix { + struct genradix_node*root; + size_t depth; +}; + +#define __GENRADIX_INITIALIZER \ + { \ + .tree = { \ + .root = NULL, \ + .depth = 0, \ + } \ + } + +/* + * We use a 0 size array to stash the type we're storing without taking any + * space at runtime - then the various accessor macros can use typeof() to get + * to it for casts/sizeof - we also force the alignment so that storing a type + * with a ridiculous alignment doesn't blow up the alignment or size of the + * genradix. + */ + +#define GENRADIX(_type)\ +struct { \ + struct __genradix tree; \ + _type type[0] __aligned(1); \ +} + +#define DEFINE_GENRADIX(_name, _type) \ + GENRADIX(_type) _name = __GENRADIX_INITIALIZER + +/** + * genradix_init - initialize a genradix + * @_radix:genradix to initialize + * + * Does not fail + */ +#define genradix_init(_radix) \ +do { \ + *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \ +} while (0) + +void __genradix_free(struct __genradix *); + +/** + * genradix_free: free all memory owned by a genradix + * + * After freeing, @_radix will be reinitialized and empty + */ +#define genradix_free(_radix) __genradix_free(&(_radix)->tree) + +static inline size_t __idx_to_offset(size_t idx, size_t obj_size) +{ + if (__builtin_constant_p(obj_size)) + BUILD_BUG_ON(obj_size > PAGE_SIZE); + else + BUG_ON(obj_size > PAGE_SIZE); + + if (!is_power_of_2(obj_size)) { + size_t objs_per_page = PAGE_SIZE / obj_size; + + return (idx / objs_per_page) * PAGE_SIZE + + (idx % objs_per_page) * obj_size; + } else { + return idx * obj_size; + } +} + +#define __genradix_cast(_radix)(typeof((_radix)->type[0]) *) +#define __genradix_obj_size(_radix)sizeof((_radix)->type[0]) +#define __genradix_idx_to_offset(_radix, _idx) \ + __idx_to_offset(_idx, __genradix_obj_size(_radix)) + +void *__genradix_ptr(struct __genradix *, size_t); + +/** + * genradix_ptr - get a pointer to a genradix entry + * @_radix:genradix to