lib: implement ptrset

include/linux/fs.h +1 -1

@@ -426,7 +427,7 @@ struct block_device {
 	struct inode *		bd_inode;	/* will die */
 	struct super_block *	bd_super;
 	struct mutex		bd_mutex;	/* open/close mutex */
-	struct list_head	bd_inodes;
+	struct ptrset		bd_inodes;
 	void *			bd_claiming;
 	void *			bd_holder;
 	int			bd_holders;

Right? well if so than those special inodes do
not hold any data and never do IO of any kind
so all the inode members that are needed for IO
are candidates.

example: i_wb_list; i_lru; i_dio_count i_writecount

i_dquot (when QUOTA is on) i_private and more

Even union with the "cgroup writback support" you
want to add.

inode->i_devices is a list_head used to link device inodes to the corresponding block_device or cdev. This patch makes block_device and cdev usfe ptrset to keep track of the inodes instead of linking inode->i_devices allowing removal of the field and thus reduction of struct inode by two pointers.

The conversion is staright-forward. list_add() is replaced with preloaded ptrset_add(), list_del_init() with ptrset_del(), and list iteration with ptrset_for_each(). The only part which isn't direct one-to-one mapping is the error handling after ptrset_add() failure.

The saved two pointers will be used by cgroup writback support.

Signed-off-by Tejun Heo <[email protected]>

Cc Alexander Viro <[email protected]>

Cc Jens Axboe <[email protected]>

Cc Christoph Hellwig <[email protected]>

---
 fs/block_dev.c       |   39 +++++++++++++++++++++++----------------
 fs/char_dev.c        |   25 +++++++++++++++----------
 fs/inode.c           |    1 -
 include/linux/cdev.h |    4 ++--
 include/linux/fs.h   |    4 ++--
 5 files changed, 42 insertions(+), 31 deletions(-)

fs/block_dev.c +7 -6

@@ -458,7 +458,7 @@ static void init_once(void *foo)
 
 	memset(bdev, 0, sizeof(*bdev));
 	mutex_init(&bdev->bd_mutex);
-	INIT_LIST_HEAD(&bdev->bd_inodes);
+	ptrset_init(&bdev->bd_inodes);
 	INIT_LIST_HEAD(&bdev->bd_list);
 #ifdef CONFIG_SYSFS
 	INIT_LIST_HEAD(&bdev->bd_holder_disks);

@@ -470,7 +470,7 @@ static void init_once(void *foo)
 
 static inline void __bd_forget(struct inode *inode)
 {
-	list_del_init(&inode->i_devices);
+	ptrset_del(inode, &inode->i_bdev->bd_inodes);
 	inode->i_bdev = NULL;
 	inode->i_mapping = &inode->i_data;
 }

@@ -478,14 +478,15 @@ static inline void __bd_forget(struct in
 static void bdev_evict_inode(struct inode *inode)
 {
 	struct block_device *bdev = &BDEV_I(inode)->bdev;
-	struct list_head *p;
+	struct ptrset_iter iter;
+	struct inode *bd_inode;
+
 	truncate_inode_pages_final(&inode->i_data);
 	invalidate_inode_buffers(inode); /* is it needed here? */
 	clear_inode(inode);
 	spin_lock(&bdev_lock);
-	while ( (p = bdev->bd_inodes.next) != &bdev->bd_inodes ) {
-		__bd_forget(list_entry(p, struct inode, i_devices));
-	}
+	ptrset_for_each(bd_inode, &bdev->bd_inodes, &iter)
+		__bd_forget(bd_inode);
 	list_del_init(&bdev->bd_list);
 	spin_unlock(&bdev_lock);
 }

fs/char_dev.c +1 -3

 		spin_lock(&cdev_lock);
 		/* Check i_cdev again in case somebody beat us to it while
 		   we dropped the lock. */
 		p = inode->i_cdev;
 		if (!p) {
-			inode->i_cdev = p = new;
-			list_add(&inode->i_devices, &p->list);
-			new = NULL;
+			ret = ptrset_add(inode, &new->inodes, GFP_NOWAIT);

if I understand correctly the motivation here is that the allocation of the internal element is done GFP_KERNEL at this call

Then the add() below can be under the spin_lock.

So why don't you just return an element here to caller and give it to add below. No Preemption-disable, no percpu variable, simple. Like:

Hello, Boaz.

Quoted 5 lines · Boaz Harrosh

if I understand correctly the motivation here is that the allocation of the internal element is done GFP_KERNEL at this call

Then the add() below can be under the spin_lock.

Quoted 2 lines

So why don't you just return an element here to caller and give it to add below. No Preemption-disable, no percpu variable, simple. Like:

Hmmm... mostly because preloading is more convenient and but also because it provides better separation from internal implementation details. e.g. This may be implemented using a different data structure (e.g. bonsai tree)

which may require differing number of new
elements even on success. With the scheme you're describing, the operation would be constantly allocating and freeing memory areas (which may be multiple) unnecessarily.

One thing which is debatable is how to handle preloading errors. We can have the preload fail and then assume that the later insertion won't fail with -ENOMEM (often through BUG/WARN_ON()); however, it often, but not always, is that those insertion operations may fail with different error codes too and requires error handling anyway,

so
overall it seems better to defer the allocation error to the actual insertion point.

It also makes conceptual sense. The preloading
simply upgrades the allocation mask the insertion operation uses.

Thanks.

Actually with my proposed change to "the code you submitted here" there are *less* unnecessary allocations. In both our imp we have a waste when element already exist in the tree, and your imp already waists an allocation in every pset_preload()

And again you are talking about a future undefined "what if", let us look at the very sound imp you proposed here with rbtree and do the best we can with that one.

Again Theoretical. With your current code the only failing I see from add() is allocation, so with my imp it will never fail. One thing good with embedded list_heads is the void returning add. And so with my proposition: void returning add.

When some new imp will be needed we can cross the bridge then.

For now you have convinced me that an rbtree is good, and I want to solve the preemption-disable, none interrupt ugliness, per-cpu vars, as well as the double alloc in the normal lots-of-free-memory case.

Quoted 3 lines

so
overall it seems better to defer the allocation error to the actual insertion point.

That one I did not understand.

Quoted 2 lines

It also makes conceptual sense. The preloading
simply upgrades the allocation mask the insertion operation uses.

How is "upgrades", better then "always have the best mask"

creating another one-off behavior. If we demote this to something which is shared only between block and char devs, we can go simpler and less versatile. Where should it go tho?

Hello, Boaz.

W/ preloading, one way to do it is,

	if (preload())
		handle -ENOMEM;
	lock;
	error = insert();
	if (error)
		handle error which can't be -ENOMEM;
	unlock;
	preload_end();

Another way is

	preload();	// can't fail
	lock;
	error = insert();
	if (error)
		handle error;'
	unlock;
	preload_end();

Both ways have pros and cons. The latter seems to lead to simpler code in general. Not always, but the overall.

And that's why the pattern usually leads to simpler code - it doesn't create a new failure point.

Quoted 2 lines · Tejun Heo

Hello, Boaz.

<>

Quoted 11 lines

W/ preloading, one way to do it is,

	if (preload())
		handle -ENOMEM;
	lock;
	error = insert();
	if (error)
		handle error which can't be -ENOMEM;
	unlock;
	preload_end();

I like this one, cause of the place I come from. Where in a cluster you want the local fails as early as possible before you start to commit remotely, and need to undo on errors.

And I can see the real flow of things

Quoted 10 lines

Another way is

	preload();	// can't fail
	lock;
	error = insert();
	if (error)
		handle error;'
	unlock;
	preload_end();

Quoted 3 lines

Both ways have pros and cons. The latter seems to lead to simpler code in general. Not always, but the overall.

I still like the over all simplicity of the above pattern to this behind the seen complexity hidden away under the carpet.

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.

include/linux/ptrset.h new file +19 -0

@@ -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;
+};

This seems rather slow and bloaty. Why not

struct tjpointer {
	struct list_head list;
	void *pointer;
};

And then callers do things like

	struct tjpointer *tjp;

	lock();

	for_each_tjpointer(tjp, &my_tjpointer_list) {
		foo(tjp->ptr);
	}

	tjpointer_del(tjp);

	unlock();

That's less storage, vastly less support code, insertion and removal are O(1) and it doesn't need the ghastly preload thing.

Hello, Andrew.

Quoted 21 lines · Andrew Morton

This seems rather slow and bloaty. Why not

struct tjpointer {
	struct list_head list;
	void *pointer;
};

And then callers do things like

	struct tjpointer *tjp;

	lock();

	for_each_tjpointer(tjp, &my_tjpointer_list) {
		foo(tjp->ptr);
	}

	tjpointer_del(tjp);

	unlock();

Quoted 2 lines

That's less storage, vastly less support code, insertion and removal are O(1) and it doesn't need the ghastly preload thing.

The goal is moving the memory necessary for indexing to the indexer instead of the indexees. In the above case, the indexee would have to either embed tjpointer inside it or at least have a pointer pointing at it.

In that case tjpointer_add() would need to do a kmalloc() for each inode which is added to the bdev/cdev, just as ptrset_add() is doing.

That might require a nasty preload thing. But really, for just two known callers it would be better to require the caller to create the storage.

	struct tjpointer *new_tpj;

	new_tpj = kmalloc(...);
	lock();
	tjpointer_add(&my_tjp_list, new_tjp, my_pointer);
	unlock();

Basically what I'm saying is nuke the rbtree and use lists.

Hello, Andrew.

Quoted 15 lines · Andrew Morton

In that case tjpointer_add() would need to do a kmalloc() for each inode which is added to the bdev/cdev, just as ptrset_add() is doing.

That might require a nasty preload thing. But really, for just two known callers it would be better to require the caller to create the storage.

	struct tjpointer *new_tpj;

	new_tpj = kmalloc(...);
	lock();
	tjpointer_add(&my_tjp_list, new_tjp, my_pointer);
	unlock();

Quoted 1 line

Basically what I'm saying is nuke the rbtree and use lists.

Hah? Then, each removal would be O(N) where N is the number of total block devices and there are cases where massive number of block devices exist and many are added / removed back-to-back. I don't think making those operations O(N^2) is a good idea.

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 <[email protected]>

---
 include/linux/ptrset.h |   74 +++++++++++++++++++++++++++
 lib/Makefile           |    2 
 lib/ptrset.c           |  131 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 206 insertions(+), 1 deletion(-)

include/linux/ptrset.h new file +74 -0

@@ -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 */

lib/Makefile +1 -1

@@ -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 \

lib/ptrset.c new file +37 -0

@@ -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)) {

Is it too ugly?

What will be the most important result it achieve?

Hello,

Quoted 1 line · Lai Jiangshan

Is it too ugly?

What is "it"? The whole thing? percpu preloading? I'm just gonna continue assuming that you're talking about preloading. If you think it's ugly, please go ahead and explain why you think it is.

It's almost impossible to respond to your "review". It's not clear what your subject matter or opinion on it is. Might as well just bang on the keyboard randomly. When reviewing (or communicating in general), please try to properly form and elaborate your points. Other people can't know what's going on in your brain and have to speculate what you could have meant.

This implementation of preloading an evolution of a design pattern which, IIRC, first started with the radix tree. The non-failing aspect was introduced while the pattern was being applied to idr. I think it's one of the better ways to implement preloading.

Quoted 1 line

What will be the most important result it achieve?

This is the same as other preloading. It allows pulling allocation out of critical section so that it can be done with more generous allocation mask (ie. GFP_KERNEL instead of GPF_NOWAIT). It's a common pattern found in data structures which may allocate memory internally such as radix tree or idr.

lib/ptrset.c new file +6 -0

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

Quoted 12 lines · Tejun Heo

lib/ptrset.c new file +12 -0

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

lib/ptrset.c line 103

Quoted 4 lines

lib/ptrset.c new file +4 -0

+	if (ptrset_find_slot(elem->ptr, set, &slot, &parent)) {
+		kfree(elem);
+		return -EEXIST;
+	}

Maybe allocation *after* ptrset_find_slot() will be better? This will avoid extra kmalloc/kfree if such ptr already exist (and also will avoid ENOMEM for such cases).

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 <[email protected]>

---
 include/linux/ptrset.h |   74 +++++++++++++++++++++++++++
 lib/Makefile           |    2 
 lib/ptrset.c           |  131 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 206 insertions(+), 1 deletion(-)

include/linux/ptrset.h new file +74 -0

@@ -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 */

lib/Makefile +1 -1

@@ -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 \

lib/ptrset.c new file +131 -1

@@ -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;
+}
--

To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 5 lines · Tejun Heo

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.

Tejun, I've noticed this somewhat late but I guess you haven't noticed my
patch series starting with a patch:
blockdev: Don't use i_devices inode field

We can get rid of i_devices without tricks like this... I just need to improve how char devices are handled.