Re: [ovs-dev] [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
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [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;
>