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-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
