linux-fsdevel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH vfs 1/2] lib: implement ptrset
@ 2014-11-13 22:09 Tejun Heo
  2014-11-13 22:11 ` [PATCH vfs 2/2] {block|char}_dev: remove inode->i_devices Tejun Heo
                   ` (5 more replies)
  0 siblings, 6 replies; 24+ messages in thread
From: Tejun Heo @ 2014-11-13 22:09 UTC (permalink / raw)
  To: Jens Axboe, Alexander Viro, Christoph Hellwig
  Cc: linux-fsdevel, linux-kernel, Andrew Morton

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@kernel.org>
---
 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);
+	}
+}
+
+static __always_inline bool ptrset_find_slot(void *ptr, struct ptrset *set,
+					     struct rb_node ***slotp,
+					     struct rb_node **parentp)
+{
+	struct rb_node **slot = &set->root.rb_node, *parent = NULL;
+
+	while (*slot) {
+		struct ptrset_elem *elem =
+			container_of(*slot, struct ptrset_elem, node);
+
+		parent = *slot;
+		if (ptr < elem->ptr) {
+			slot = &(*slot)->rb_left;
+		} else if (ptr > elem->ptr) {
+			slot = &(*slot)->rb_right;
+		} else {
+			*slotp = slot;
+			return true;
+		}
+	}
+
+	*slotp = slot;
+	if (parentp)
+		*parentp = parent;
+	return false;
+}
+
+/**
+ * ptrset_add - add a pointer to a ptrset
+ * @ptr: the pointer to add
+ * @set: the target ptrset
+ * @gfp: the allocation mask to use
+ *
+ * Allocate a ptrset_elem using @gfp, init with @ptr and add to @set.
+ * Returns 0 on success, -ENOMEM if allocation failed and -EEXIST if @ptr
+ * already exists in @set.
+ *
+ * The caller is responsible for synchronization.
+ */
+int ptrset_add(void *ptr, struct ptrset *set, gfp_t gfp)
+{
+	struct ptrset_elem *elem;
+	struct rb_node *parent, **slot;
+
+	elem = kmalloc(sizeof(*elem), gfp);
+	if (!elem && !in_interrupt())	/* see ptrset_preload() */
+		elem = this_cpu_xchg(ptrset_preload_elem, NULL);
+	if (!elem)
+		return -ENOMEM;
+	elem->ptr = ptr;
+
+	if (ptrset_find_slot(elem->ptr, set, &slot, &parent)) {
+		kfree(elem);
+		return -EEXIST;
+	}
+
+	rb_link_node(&elem->node, parent, slot);
+	rb_insert_color(&elem->node, &set->root);
+	return 0;
+}
+
+/**
+ * ptrset_del - delete a pointer from a ptrset
+ * @ptr: the pointer to delete
+ * @set: the target ptrset
+ *
+ * Delete @ptr from @set.  Returns 0 on success, -ENOENT if @ptr is not in
+ * @set.
+ *
+ * The caller is responsible for synchronization.
+ */
+int ptrset_del(void *ptr, struct ptrset *set)
+{
+	struct rb_node **slot, *node;
+
+	if (!ptrset_find_slot(ptr, set, &slot, NULL))
+		return -ENOENT;
+
+	node = *slot;
+	rb_erase(node, &set->root);
+	kfree(container_of(node, struct ptrset_elem, node));
+	return 0;
+}

^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2014-12-02 18:15 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-11-13 22:09 [PATCH vfs 1/2] lib: implement ptrset Tejun Heo
2014-11-13 22:11 ` [PATCH vfs 2/2] {block|char}_dev: remove inode->i_devices Tejun Heo
2014-11-18 12:10   ` Boaz Harrosh
2014-11-18 12:30     ` Tejun Heo
2014-11-20 10:42   ` Boaz Harrosh
2014-11-20 11:50     ` Tejun Heo
2014-11-20 12:36       ` Boaz Harrosh
2014-11-20 13:11         ` Tejun Heo
2014-11-20 13:39           ` Tejun Heo
2014-11-20 14:14           ` Boaz Harrosh
2014-11-20 14:19             ` Tejun Heo
2014-11-13 22:23 ` [PATCH vfs 1/2] lib: implement ptrset Andrew Morton
2014-11-13 22:27   ` Tejun Heo
2014-11-13 22:40     ` Andrew Morton
2014-11-14 13:12       ` Tejun Heo
2014-11-18 20:46         ` Andrew Morton
2014-11-18  9:19 ` Lai Jiangshan
2014-11-18 11:55   ` Tejun Heo
2014-11-19  1:41     ` Lai Jiangshan
2014-11-18 15:56 ` Azat Khuzhin
2014-11-18 17:16   ` Tejun Heo
2014-11-18 17:49 ` [PATCH vfs v2 " Tejun Heo
2014-11-25 16:37 ` [PATCH vfs " Jan Kara
2014-12-02 18:15   ` Tejun Heo

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).