[email protected], 2005-03-21 11:45:16-08:00, [email protected]
[klist] Add initial implementation of klist helpers.
This klist interface provides a couple of structures that wrap around
struct list_head to provide explicit list "head" (struct klist) and
list "node" (struct klist_node) objects. For struct klist, a spinlock
is included that protects access to the actual list itself. struct
klist_node provides a pointer to the klist that owns it and a kref
reference count that indicates the number of current users of that node
in the list.
The entire point is to provide an interface for iterating over a list
that is safe and allows for modification of the list during the
iteration (e.g. insertion and removal), including modification of the
current node on the list.
It works using a 3rd object type - struct klist_iter - that is declared
and initialized before an iteration. klist_next() is used to acquire the
next element in the list. It returns NULL if there are no more items.
This klist interface provides a couple of structures that wrap around
struct list_head to provide explicit list "head" (struct klist) and
list "node" (struct klist_node) objects. For struct klist, a spinlock
is included that protects access to the actual list itself. struct
klist_node provides a pointer to the klist that owns it and a kref
reference count that indicates the number of current users of that node
in the list.
The entire point is to provide an interface for iterating over a list
that is safe and allows for modification of the list during the
iteration (e.g. insertion and removal), including modification of the
current node on the list.
It works using a 3rd object type - struct klist_iter - that is declared
and initialized before an iteration. klist_next() is used to acquire the
next element in the list. It returns NULL if there are no more items.
Internally, that routine takes the klist's lock, decrements the reference
count of the previous klist_node and increments the count of the next
klist_node. It then drops the lock and returns.
There are primitives for adding and removing nodes to/from a klist.
When deleting, klist_del() will simply decrement the reference count.
Only when the count goes to 0 is the node removed from the list.
klist_remove() will try to delete the node from the list and block
until it is actually removed. This is useful for objects (like devices)
that have been removed from the system and must be freed (but must wait
until all accessors have finished).
Internally, that routine takes the klist's lock, decrements the reference
count of the previous klist_node and increments the count of the next
klist_node. It then drops the lock and returns.
There are primitives for adding and removing nodes to/from a klist.
When deleting, klist_del() will simply decrement the reference count.
Only when the count goes to 0 is the node removed from the list.
klist_remove() will try to delete the node from the list and block
until it is actually removed. This is useful for objects (like devices)
that have been removed from the system and must be freed (but must wait
until all accessors have finished).
Signed-off-by: Patrick Mochel <[email protected]>
diff -Nru a/include/linux/klist.h b/include/linux/klist.h
--- /dev/null Wed Dec 31 16:00:00 196900
+++ b/include/linux/klist.h 2005-03-21 12:30:34 -08:00
@@ -0,0 +1,53 @@
+/*
+ * klist.h - Some generic list helpers, extending struct list_head a bit.
+ *
+ * Implementations are found in lib/klist.c
+ *
+ *
+ * Copyright (C) 2005 Patrick Mochel
+ *
+ * This file is rleased under the GPL v2.
+ */
+
+#include <linux/spinlock.h>
+#include <linux/completion.h>
+#include <linux/kref.h>
+#include <linux/list.h>
+
+
+struct klist {
+ spinlock_t k_lock;
+ struct list_head k_list;
+};
+
+
+extern void klist_init(struct klist * k);
+
+
+struct klist_node {
+ struct klist * n_klist;
+ struct list_head n_node;
+ struct kref n_ref;
+ struct completion n_removed;
+};
+
+extern void klist_add_tail(struct klist * k, struct klist_node * n);
+extern void klist_add_head(struct klist * k, struct klist_node * n);
+
+extern void klist_del(struct klist_node * n);
+extern void klist_remove(struct klist_node * n);
+
+
+struct klist_iter {
+ struct klist * i_klist;
+ struct list_head * i_head;
+ struct klist_node * i_cur;
+};
+
+
+extern void klist_iter_init(struct klist * k, struct klist_iter * i);
+extern void klist_iter_init_node(struct klist * k, struct klist_iter * i,
+ struct klist_node * n);
+extern void klist_iter_exit(struct klist_iter * i);
+extern struct klist_node * klist_next(struct klist_iter * i);
+
diff -Nru a/lib/Makefile b/lib/Makefile
--- a/lib/Makefile 2005-03-21 12:30:34 -08:00
+++ b/lib/Makefile 2005-03-21 12:30:34 -08:00
@@ -4,9 +4,10 @@
lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
- kobject.o kref.o idr.o div64.o int_sqrt.o \
- bitmap.o extable.o kobject_uevent.o prio_tree.o sha1.o \
- halfmd4.o
+ idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \
+ sha1.o halfmd4.o
+
+lib-y += kobject.o kref.o kobject_uevent.o klist.o
obj-y += sort.o parser.o
diff -Nru a/lib/klist.c b/lib/klist.c
--- /dev/null Wed Dec 31 16:00:00 196900
+++ b/lib/klist.c 2005-03-21 12:30:34 -08:00
@@ -0,0 +1,248 @@
+/*
+ * klist.c - Routines for manipulating klists.
+ *
+ *
+ * This klist interface provides a couple of structures that wrap around
+ * struct list_head to provide explicit list "head" (struct klist) and
+ * list "node" (struct klist_node) objects. For struct klist, a spinlock
+ * is included that protects access to the actual list itself. struct
+ * klist_node provides a pointer to the klist that owns it and a kref
+ * reference count that indicates the number of current users of that node
+ * in the list.
+ *
+ * The entire point is to provide an interface for iterating over a list
+ * that is safe and allows for modification of the list during the
+ * iteration (e.g. insertion and removal), including modification of the
+ * current node on the list.
+ *
+ * It works using a 3rd object type - struct klist_iter - that is declared
+ * and initialized before an iteration. klist_next() is used to acquire the
+ * next element in the list. It returns NULL if there are no more items.
+ * Internally, that routine takes the klist's lock, decrements the reference
+ * count of the previous klist_node and increments the count of the next
+ * klist_node. It then drops the lock and returns.
+ *
+ * There are primitives for adding and removing nodes to/from a klist.
+ * When deleting, klist_del() will simply decrement the reference count.
+ * Only when the count goes to 0 is the node removed from the list.
+ * klist_remove() will try to delete the node from the list and block
+ * until it is actually removed. This is useful for objects (like devices)
+ * that have been removed from the system and must be freed (but must wait
+ * until all accessors have finished).
+ *
+ * Copyright (C) 2005 Patrick Mochel
+ *
+ * This file is released under the GPL v2.
+ */
+
+#include <linux/klist.h>
+#include <linux/module.h>
+
+
+/**
+ * klist_init - Initialize a klist structure.
+ * @k: The klist we're initializing.
+ */
+
+void klist_init(struct klist * k)
+{
+ INIT_LIST_HEAD(&k->k_list);
+ spin_lock_init(&k->k_lock);
+}
+
+EXPORT_SYMBOL_GPL(klist_init);
+
+
+static void add_head(struct klist * k, struct klist_node * n)
+{
+ spin_lock(&k->k_lock);
+ list_add(&n->n_node, &k->k_list);
+ spin_unlock(&k->k_lock);
+}
+
+static void add_tail(struct klist * k, struct klist_node * n)
+{
+ spin_lock(&k->k_lock);
+ list_add_tail(&n->n_node, &k->k_list);
+ spin_unlock(&k->k_lock);
+}
+
+
+static void klist_node_init(struct klist * k, struct klist_node * n)
+{
+ INIT_LIST_HEAD(&n->n_node);
+ init_completion(&n->n_removed);
+ kref_init(&n->n_ref);
+ n->n_klist = k;
+}
+
+
+/**
+ * klist_add_head - Initialize a klist_node and add it to front.
+ * @k: klist it's going on.
+ * @n: node we're adding.
+ */
+
+void klist_add_head(struct klist * k, struct klist_node * n)
+{
+ klist_node_init(k, n);
+ add_head(k, n);
+}
+
+EXPORT_SYMBOL_GPL(klist_add_head);
+
+
+/**
+ * klist_add_tail - Initialize a klist_node and add it to back.
+ * @k: klist it's going on.
+ * @n: node we're adding.
+ */
+
+void klist_add_tail(struct klist * k, struct klist_node * n)
+{
+ klist_node_init(k, n);
+ add_tail(k, n);
+}
+
+EXPORT_SYMBOL_GPL(klist_add_tail);
+
+
+static void klist_release(struct kref * kref)
+{
+ struct klist_node * n = container_of(kref, struct klist_node, n_ref);
+ list_del(&n->n_node);
+ complete(&n->n_removed);
+}
+
+static int klist_dec_and_del(struct klist_node * n)
+{
+ return kref_put(&n->n_ref, klist_release);
+}
+
+
+/**
+ * klist_del - Decrement the reference count of node and try to remove.
+ * @n: node we're deleting.
+ */
+
+void klist_del(struct klist_node * n)
+{
+ struct klist * k = n->n_klist;
+
+ spin_lock(&k->k_lock);
+ klist_dec_and_del(n);
+ spin_unlock(&k->k_lock);
+}
+
+EXPORT_SYMBOL_GPL(klist_del);
+
+
+/**
+ * klist_remove - Decrement the refcount of node and wait for it to go away.
+ * @n: node we're removing.
+ */
+
+void klist_remove(struct klist_node * n)
+{
+ spin_lock(&n->n_klist->k_lock);
+ klist_dec_and_del(n);
+ spin_unlock(&n->n_klist->k_lock);
+ wait_for_completion(&n->n_removed);
+}
+
+EXPORT_SYMBOL_GPL(klist_remove);
+
+
+/**
+ * klist_iter_init_node - Initialize a klist_iter structure.
+ * @k: klist we're iterating.
+ * @i: klist_iter we're filling.
+ * @n: node to start with.
+ *
+ * Similar to klist_iter_init(), but starts the action off with @n,
+ * instead of with the list head.
+ */
+
+void klist_iter_init_node(struct klist * k, struct klist_iter * i, struct klist_node * n)
+{
+ i->i_klist = k;
+ i->i_head = &k->k_list;
+ i->i_cur = n;
+}
+
+EXPORT_SYMBOL_GPL(klist_iter_init_node);
+
+
+/**
+ * klist_iter_init - Iniitalize a klist_iter structure.
+ * @k: klist we're iterating.
+ * @i: klist_iter structure we're filling.
+ *
+ * Similar to klist_iter_init_node(), but start with the list head.
+ */
+
+void klist_iter_init(struct klist * k, struct klist_iter * i)
+{
+ klist_iter_init_node(k, i, NULL);
+}
+
+EXPORT_SYMBOL_GPL(klist_iter_init);
+
+
+/**
+ * klist_iter_exit - Finish a list iteration.
+ * @i: Iterator structure.
+ *
+ * Must be called when done iterating over list, as it decrements the
+ * refcount of the current node. Necessary in case iteration exited before
+ * the end of the list was reached, and always good form.
+ */
+
+void klist_iter_exit(struct klist_iter * i)
+{
+ if (i->i_cur) {
+ klist_del(i->i_cur);
+ i->i_cur = NULL;
+ }
+}
+
+EXPORT_SYMBOL_GPL(klist_iter_exit);
+
+
+static struct klist_node * to_klist_node(struct list_head * n)
+{
+ return container_of(n, struct klist_node, n_node);
+}
+
+
+/**
+ * klist_next - Ante up next node in list.
+ * @i: Iterator structure.
+ *
+ * First grab list lock. Decrement the reference count of the previous
+ * node, if there was one. Grab the next node, increment its reference
+ * count, drop the lock, and return that next node.
+ */
+
+struct klist_node * klist_next(struct klist_iter * i)
+{
+ struct list_head * next;
+ struct klist_node * knode = NULL;
+
+ spin_lock(&i->i_klist->k_lock);
+ if (i->i_cur) {
+ next = i->i_cur->n_node.next;
+ klist_dec_and_del(i->i_cur);
+ } else
+ next = i->i_head->next;
+
+ if (next != i->i_head) {
+ knode = to_klist_node(next);
+ kref_get(&knode->n_ref);
+ }
+ i->i_cur = knode;
+ spin_unlock(&i->i_klist->k_lock);
+ return knode;
+}
+
+EXPORT_SYMBOL_GPL(klist_next);
On Mon, Mar 21, 2005 at 12:48:47PM -0800, Patrick Mochel wrote:
>
> [email protected], 2005-03-21 11:45:16-08:00, [email protected]
> [klist] Add initial implementation of klist helpers.
> This klist interface provides a couple of structures that wrap around
> struct list_head to provide explicit list "head" (struct klist) and
> list "node" (struct klist_node) objects. For struct klist, a spinlock
> is included that protects access to the actual list itself.
Not sure this is a good idea. Usually you want a lock protect slightly
more than just list operations, e.g. refcounting of objects in list,
some short-term manipulations, etc.
> struct
> klist_node provides a pointer to the klist that owns it and a kref
> reference count that indicates the number of current users of that node
> in the list.
>
> The entire point is to provide an interface for iterating over a list
> that is safe and allows for modification of the list during the
> iteration (e.g. insertion and removal), including modification of the
> current node on the list.
>
> It works using a 3rd object type - struct klist_iter - that is declared
> and initialized before an iteration. klist_next() is used to acquire the
> next element in the list. It returns NULL if there are no more items.
> This klist interface provides a couple of structures that wrap around
> struct list_head to provide explicit list "head" (struct klist) and
> list "node" (struct klist_node) objects. For struct klist, a spinlock
> is included that protects access to the actual list itself. struct
> klist_node provides a pointer to the klist that owns it and a kref
> reference count that indicates the number of current users of that node
> in the list.
Yikes. It's really not that hard to get traversal of a refcounted list
right, and you're adding lots of obsfucation over that rather easy thing.
The driver model and kfoo stuff already got us lots of layer of obsfucation,
but we should really stop at some point where it makes the underlying
operations much more complicated.
> There are primitives for adding and removing nodes to/from a klist.
> When deleting, klist_del() will simply decrement the reference count.
> Only when the count goes to 0 is the node removed from the list.
This sounds rather odd, and doesn't make much sense to me. In all cases
I've seen you want to disallow lookup imediately (list_del), which is
completly separate from object lifetime rules.
On Tue, 22 Mar 2005, Christoph Hellwig wrote:
> On Mon, Mar 21, 2005 at 12:48:47PM -0800, Patrick Mochel wrote:
> >
> > [email protected], 2005-03-21 11:45:16-08:00, [email protected]
> > [klist] Add initial implementation of klist helpers.
>
> > This klist interface provides a couple of structures that wrap around
> > struct list_head to provide explicit list "head" (struct klist) and
> > list "node" (struct klist_node) objects. For struct klist, a spinlock
> > is included that protects access to the actual list itself.
>
> Not sure this is a good idea. Usually you want a lock protect slightly
> more than just list operations, e.g. refcounting of objects in list,
> some short-term manipulations, etc.
The above statement could be a little more explicit. The klist is the sole
object in question. The spinlock protects the klist object itself,
including manipulation of the klist nodes and refcounting of the nodes on
the list. At some point, more fields could be added to struct klist which
may need protection.
That protection could be provided by the spinlock, but it's possible that
those fields may not need to be synchronized with manipulation of the list
or the refcounts, which may warrant a separate lock.
Note that some people (e.g. ex-PTX people that I've dealt with before)
believed that every field should have a separate lock. I definitely don't
follow that mantra, especially since we have refcounts to provide some of
the protection that their locks would. But, where it makes sense, we need
to localize the use, which is why the klist gets its own lock.
> > struct
> > klist_node provides a pointer to the klist that owns it and a kref
> > reference count that indicates the number of current users of that node
> > in the list.
> >
> > The entire point is to provide an interface for iterating over a list
> > that is safe and allows for modification of the list during the
> > iteration (e.g. insertion and removal), including modification of the
> > current node on the list.
> >
> > It works using a 3rd object type - struct klist_iter - that is declared
> > and initialized before an iteration. klist_next() is used to acquire the
> > next element in the list. It returns NULL if there are no more items.
> > This klist interface provides a couple of structures that wrap around
> > struct list_head to provide explicit list "head" (struct klist) and
> > list "node" (struct klist_node) objects. For struct klist, a spinlock
> > is included that protects access to the actual list itself. struct
> > klist_node provides a pointer to the klist that owns it and a kref
> > reference count that indicates the number of current users of that node
> > in the list.
>
> Yikes. It's really not that hard to get traversal of a refcounted list
> right, and you're adding lots of obsfucation over that rather easy thing.
> The driver model and kfoo stuff already got us lots of layer of obsfucation,
> but we should really stop at some point where it makes the underlying
> operations much more complicated.
There is definitely some unnecessary obfuscation in the kobject, etc code.
I'd like to see a lot of that cleaned up, and this is one step along those
lines, even if may seem to only add more code ATM.
This patch solidifies the notion that list heads and list nodes are
autonomous objects, not just in relation to each other, but also to the
larger objects that contain them. The refcounts added are to mediate
access to the greater object via 1 particular list that it's contained on.
They don't control the lifetime of the (greater) object itself per se, but
rather its visibility to a particular set.
It is possible to add the same functionality without encapsulating them in
these new object types (adding locks for each list head and refcounts for
each list node), but this a) saves many keystrokes, and b) makes the
resulting code a lot simpler by using an iterator.
> > There are primitives for adding and removing nodes to/from a klist.
> > When deleting, klist_del() will simply decrement the reference count.
> > Only when the count goes to 0 is the node removed from the list.
>
> This sounds rather odd, and doesn't make much sense to me. In all cases
> I've seen you want to disallow lookup imediately (list_del), which is
> completly separate from object lifetime rules.
The object in question is the list node, which has its own refcount. It's
lifetime is its existence on the list. Ending its lifetime is removing it
from the list, which one would only want to do when that list node is not
being accessed. In itself, it has nothing to do with the lifetime of the
greater object.
Thanks for the comments. I hope this helps,
Pat
Patrick Mochel <[email protected]> writes:
> +void klist_del(struct klist_node * n)
> +{
> + struct klist * k = n->n_klist;
> +
> + spin_lock(&k->k_lock);
> + klist_dec_and_del(n);
> + spin_unlock(&k->k_lock);
> +}
Can't we use atomic_dec_and_lock()?
[...]
> +void klist_remove(struct klist_node * n)
> +{
> + spin_lock(&n->n_klist->k_lock);
> + klist_dec_and_del(n);
> + spin_unlock(&n->n_klist->k_lock);
> + wait_for_completion(&n->n_removed);
> +}
Why isn't those going into drivers/base/? Personally, klist seems
drivers/base stuff rather than generic stuff...
--
OGAWA Hirofumi <[email protected]>
On Wed, 23 Mar 2005, OGAWA Hirofumi wrote:
> Patrick Mochel <[email protected]> writes:
>
> > +void klist_del(struct klist_node * n)
> > +{
> > + struct klist * k = n->n_klist;
> > +
> > + spin_lock(&k->k_lock);
> > + klist_dec_and_del(n);
> > + spin_unlock(&k->k_lock);
> > +}
>
> Can't we use atomic_dec_and_lock()?
No. It uses the kref_inc() and kref_dec(), which do not have the
equivalent atomic_dec_and_lock() primitives.
> [...]
>
> > +void klist_remove(struct klist_node * n)
> > +{
> > + spin_lock(&n->n_klist->k_lock);
> > + klist_dec_and_del(n);
> > + spin_unlock(&n->n_klist->k_lock);
> > + wait_for_completion(&n->n_removed);
> > +}
>
> Why isn't those going into drivers/base/? Personally, klist seems
> drivers/base stuff rather than generic stuff...
Could be for now. I'd like to convert more of the kobject/kest mess to use
a cleaner, and rwsem-free locking mechanism, which would nearly justify it
in lib/. All in all, that change is purely cosmetic.
Pat