Re: [PATCH 1/6] Generic radix trees

[Liu Bo]

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

[Liu Bo]

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

[Kent Overstreet]

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

[Kent Overstreet]

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

[Liu Bo]

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;
> 

Re: [PATCH 1/6] Generic radix trees

[Liu Bo]

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

[Kent Overstreet]

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

[PATCH 1/6] Generic radix trees

[Kent Overstreet]

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