Re: [PATCH vfs 1/2] lib: implement ptrset

[Lai Jiangshan]

On 11/14/2014 06:09 AM, Tejun Heo wrote:
> Implement set of pointers.  Pointers can be added, deleted and
> iterated.  It's currently implemented as a thin rbtree wrapper making
> addition and removal O(log N).  A drawback is that iteration isn't RCU
> safe, which is okay for now.  This will be used to remove
> inode->i_devices.
> 
> Signed-off-by: Tejun Heo <tj@xxxxxxxxxx>
> ---
>  include/linux/ptrset.h |   74 +++++++++++++++++++++++++++
>  lib/Makefile           |    2 
>  lib/ptrset.c           |  131 +++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 206 insertions(+), 1 deletion(-)
> 
> --- /dev/null
> +++ b/include/linux/ptrset.h
> @@ -0,0 +1,74 @@
> +/*
> + * include/linux/ptrset.h - set of pointers
> + *
> + * Copyright (C) 2014		Tejun Heo, Red Hat Inc.
> + *
> + * A ptrset contains an unordered set of pointers.  Pointers can be added,
> + * deleted and iterated.  Addition and removal complexities are O(log N)
> + * where N is the total number of elements in the ptrset.
> + */
> +
> +#ifndef __PTRSET_H
> +#define __PTRSET_H
> +
> +#include <linux/preempt.h>
> +#include <linux/rbtree.h>
> +
> +struct ptrset {
> +	struct rb_root		root;
> +};
> +
> +struct ptrset_elem {
> +	void			*ptr;
> +	struct rb_node		node;
> +};
> +
> +struct ptrset_iter {
> +	struct ptrset_elem	*pos;
> +	struct ptrset_elem	*next;
> +};
> +
> +#define PTRSET_INITIALIZER	{ .root = RB_ROOT, }
> +#define DEFINE_PTRSET(set)	struct ptrset set = PTRSET_INITIALIZER
> +
> +static inline void ptrset_init(struct ptrset *set)
> +{
> +	*set = (struct ptrset)PTRSET_INITIALIZER;
> +}
> +
> +void ptrset_preload(gfp_t gfp);
> +int __must_check ptrset_add(void *ptr, struct ptrset *set, gfp_t gfp);
> +int ptrset_del(void *ptr, struct ptrset *set);
> +
> +/**
> + * ptrset_preload_end - end preload section started with ptrset_preload()
> + *
> + * Each ptrset_preload() should be matched with an invocation of this
> + * function.  See ptrset_preload() for details.
> + */
> +static inline void ptrset_preload_end(void)
> +{
> +	preempt_enable();
> +}
> +
> +/**
> + * ptrset_for_each - iterate pointers in a ptrset
> + * @ptr_cur: the cursor pointer variable (can be a pointer to any type)
> + * @set: the target ptrset
> + * @iter: pointer to struct ptrset_iter used to store iteration state
> + *
> + * Iterate @ptr_cur over all pointers in @set using @iter as the temp
> + * storage.  The order of iteration is undefined and the iterated pointers
> + * may be deleted during iteration.
> + *
> + * The caller is responsible for synchronization.  This is not RCU safe.
> + */
> +#define ptrset_for_each(ptr_cur, set, iter)				\
> +	rbtree_postorder_for_each_entry_safe((iter)->pos, (iter)->next,	\
> +					     &(set)->root, node)	\
> +		if (({	(ptr_cur) = (iter)->pos->ptr;			\
> +			false; }))					\
> +			;						\
> +		else
> +
> +#endif	/* __PTRSET_H */
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLA
>  endif
>  
>  lib-y := ctype.o string.o vsprintf.o cmdline.o \
> -	 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
> +	 rbtree.o radix-tree.o dump_stack.o timerqueue.o ptrset.o \
>  	 idr.o int_sqrt.o extable.o \
>  	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
>  	 proportions.o flex_proportions.o ratelimit.o show_mem.o \
> --- /dev/null
> +++ b/lib/ptrset.c
> @@ -0,0 +1,131 @@
> +/*
> + * lib/ptrset.c - set of pointers
> + *
> + * Copyright (C) 2014		Tejun Heo, Red Hat Inc.
> + */
> +
> +#include <linux/ptrset.h>
> +#include <linux/slab.h>
> +#include <linux/percpu.h>
> +
> +static DEFINE_PER_CPU(struct ptrset_elem *, ptrset_preload_elem);
> +
> +/**
> + * ptrset_preload - preload for ptrset_add()
> + * @gfp: allocation mask to use for preloading
> + *
> + * Preload per-cpu ptrset_elem buffer for ptrset_add().  Can only be used
> + * from process context and each ptrset_preload() invocation should be
> + * matched with ptrset_preload_end().  Note that preemption is disabled
> + * while preloaded.
> + *
> + * The first ptrset_add() in the preloaded section can be treated as if it
> + * were invoked with @gfp used for preloading.  This allows using more
> + * permissive allocation masks for ptrsets protected by spinlocks.
> + */
> +void ptrset_preload(gfp_t gfp)
> +{
> +	/*
> +	 * Consuming preload buffer from non-process context breaks preload
> +	 * allocation guarantee.  Disallow usage from those contexts.
> +	 */
> +	WARN_ON_ONCE(in_interrupt());
> +	might_sleep_if(gfp & __GFP_WAIT);
> +
> +	preempt_disable();
> +
> +	if (!__this_cpu_read(ptrset_preload_elem)) {
> +		struct ptrset_elem *new;
> +
> +		preempt_enable();
> +		new = kmalloc(sizeof(*new), gfp);
> +		preempt_disable();
> +
> +		new = __this_cpu_xchg(ptrset_preload_elem, new);
> +		kfree(new);
> +	}
> +}

Is it too ugly?
What will be the most important result it achieve?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/