This patch introduces new list structure named "list1".
TOMOYO wants to use "write once read many" list.
Since only two operations
(1) Append an entry to the tail of the list.
(2) Read all entries starting from the head of the list.
are needed for that purpose, this list doesn't have pointer to previous
element.
While "hlist" is defined as
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
I don't use "hlist_node" because I don't need pointer to previous element.
By ommiting pointer to previous element, the reader becomes read lock free,
which is good thing for implementing "write once read many" list.
Signed-off-by: Tetsuo Handa <[email protected]>
Reviewed-by: Paul E. McKenney <[email protected]>
---
include/linux/list1.h | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 81 insertions(+)
--- /dev/null
+++ linux-2.6.28-mm1/include/linux/list1.h
@@ -0,0 +1,81 @@
+#ifndef _LINUX_LIST1_H
+#define _LINUX_LIST1_H
+
+#include <linux/list.h>
+#include <linux/rcupdate.h>
+
+/*
+ * Singly linked list implementation.
+ *
+ * This list supports only two operations.
+ * (1) Append an entry to the tail of the list.
+ * (2) Read all entries starting from the head of the list.
+ *
+ * This list is designed for holding "write once, read many" entries.
+ * This list requires no locks for read operation.
+ * This list doesn't support "remove an entry from the list" operation.
+ */
+
+/* To reduce memory usage, this list doesn't use "->prev" pointer. */
+struct list1_head {
+ struct list1_head *next;
+};
+
+#define LIST1_HEAD_INIT(name) { &(name) }
+#define LIST1_HEAD(name) struct list1_head name = LIST1_HEAD_INIT(name)
+
+static inline void INIT_LIST1_HEAD(struct list1_head *list)
+{
+ list->next = list;
+}
+
+/* Reuse list_entry because it doesn't use "->prev" pointer. */
+#define list1_entry list_entry
+
+/* Reuse list_for_each_rcu because it doesn't use "->prev" pointer. */
+#define list1_for_each list_for_each_rcu
+/* Reuse list_for_each_entry_rcu because it doesn't use "->prev" pointer. */
+#define list1_for_each_entry list_for_each_entry_rcu
+
+/**
+ * list1_for_each_cookie - iterate over a list with cookie.
+ * @pos: the &struct list1_head to use as a loop cursor.
+ * @cookie: the &struct list1_head to use as a cookie.
+ * @head: the head for your list.
+ *
+ * Same with list_for_each_rcu() except that this primitive uses @cookie
+ * so that we can continue iteration.
+ * @cookie must be NULL when iteration starts, and @cookie will become
+ * NULL when iteration finishes.
+ *
+ * Since list elements are never removed, we don't need to get a lock
+ * or a reference count.
+ */
+#define list1_for_each_cookie(pos, cookie, head) \
+ for (({ if (!cookie) \
+ cookie = head; }), \
+ pos = rcu_dereference((cookie)->next); \
+ prefetch(pos->next), pos != (head) || ((cookie) = NULL); \
+ (cookie) = pos, pos = rcu_dereference(pos->next))
+
+/**
+ * list1_add_tail - add a new entry to list1 list.
+ * @new: new entry to be added.
+ * @head: list head to add it before.
+ *
+ * Same with list_add_tail_rcu() without "->prev" pointer.
+ *
+ * Caller must hold a lock for protecting @head.
+ */
+static inline void list1_add_tail(struct list1_head *new,
+ struct list1_head *head)
+{
+ struct list1_head *prev = head;
+
+ new->next = head;
+ while (prev->next != head)
+ prev = prev->next;
+ rcu_assign_pointer(prev->next, new);
+}
+
+#endif
--
On Thu, 1 Jan 2009, Tetsuo Handa wrote:
> This patch introduces new list structure named "list1".
>
> TOMOYO wants to use "write once read many" list.
> Since only two operations
>
> (1) Append an entry to the tail of the list.
> (2) Read all entries starting from the head of the list.
>
> are needed for that purpose, this list doesn't have pointer to previous
> element.
>
> While "hlist" is defined as
>
> struct hlist_head {
> struct hlist_node *first;
> };
>
> struct hlist_node {
> struct hlist_node *next, **pprev;
> };
>
> I don't use "hlist_node" because I don't need pointer to previous element.
>
> By ommiting pointer to previous element, the reader becomes read lock free,
> which is good thing for implementing "write once read many" list.
This has a technical ack from Paul, but what about Linus' long-standing
objection to singly-linked lists in the kernel? I'm sure this has been
discussed re. your patches, but I can't find a reference.
Also, should this be folded into list.h, and is "list1" an appropriate
name? ("slist" might be better).
>
> Signed-off-by: Tetsuo Handa <[email protected]>
> Reviewed-by: Paul E. McKenney <[email protected]>
> ---
> include/linux/list1.h | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 81 insertions(+)
>
> --- /dev/null
> +++ linux-2.6.28-mm1/include/linux/list1.h
> @@ -0,0 +1,81 @@
> +#ifndef _LINUX_LIST1_H
> +#define _LINUX_LIST1_H
> +
> +#include <linux/list.h>
> +#include <linux/rcupdate.h>
> +
> +/*
> + * Singly linked list implementation.
> + *
> + * This list supports only two operations.
> + * (1) Append an entry to the tail of the list.
> + * (2) Read all entries starting from the head of the list.
> + *
> + * This list is designed for holding "write once, read many" entries.
> + * This list requires no locks for read operation.
> + * This list doesn't support "remove an entry from the list" operation.
> + */
> +
> +/* To reduce memory usage, this list doesn't use "->prev" pointer. */
> +struct list1_head {
> + struct list1_head *next;
> +};
> +
> +#define LIST1_HEAD_INIT(name) { &(name) }
> +#define LIST1_HEAD(name) struct list1_head name = LIST1_HEAD_INIT(name)
> +
> +static inline void INIT_LIST1_HEAD(struct list1_head *list)
> +{
> + list->next = list;
> +}
> +
> +/* Reuse list_entry because it doesn't use "->prev" pointer. */
> +#define list1_entry list_entry
> +
> +/* Reuse list_for_each_rcu because it doesn't use "->prev" pointer. */
> +#define list1_for_each list_for_each_rcu
> +/* Reuse list_for_each_entry_rcu because it doesn't use "->prev" pointer. */
> +#define list1_for_each_entry list_for_each_entry_rcu
> +
> +/**
> + * list1_for_each_cookie - iterate over a list with cookie.
> + * @pos: the &struct list1_head to use as a loop cursor.
> + * @cookie: the &struct list1_head to use as a cookie.
> + * @head: the head for your list.
> + *
> + * Same with list_for_each_rcu() except that this primitive uses @cookie
> + * so that we can continue iteration.
> + * @cookie must be NULL when iteration starts, and @cookie will become
> + * NULL when iteration finishes.
> + *
> + * Since list elements are never removed, we don't need to get a lock
> + * or a reference count.
> + */
> +#define list1_for_each_cookie(pos, cookie, head) \
> + for (({ if (!cookie) \
> + cookie = head; }), \
> + pos = rcu_dereference((cookie)->next); \
> + prefetch(pos->next), pos != (head) || ((cookie) = NULL); \
> + (cookie) = pos, pos = rcu_dereference(pos->next))
> +
> +/**
> + * list1_add_tail - add a new entry to list1 list.
> + * @new: new entry to be added.
> + * @head: list head to add it before.
> + *
> + * Same with list_add_tail_rcu() without "->prev" pointer.
> + *
> + * Caller must hold a lock for protecting @head.
> + */
> +static inline void list1_add_tail(struct list1_head *new,
> + struct list1_head *head)
> +{
> + struct list1_head *prev = head;
> +
> + new->next = head;
> + while (prev->next != head)
> + prev = prev->next;
> + rcu_assign_pointer(prev->next, new);
> +}
> +
> +#endif
>
> --
> --
> To unsubscribe from this list: send the line "unsubscribe linux-security-module" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>
--
James Morris
<[email protected]>
James Morris wrote:
> This has a technical ack from Paul, but what about Linus' long-standing
> objection to singly-linked lists in the kernel? I'm sure this has been
> discussed re. your patches, but I can't find a reference.
I couldn't find one neither. (What does "re." mean?)
But optimistically speaking, there are many in-tree users who define "struct"
without "prev" pointer.
# grep -hr 'struct [a-zA-Z0-9_]* \*next;' linux-2.6.28/include/linux/ | wc -l
42
# grep -hr 'struct [a-zA-Z0-9_]* \*prev;' linux-2.6.28/include/linux/ | wc -l
7
Not all structures listed below are used as singly linked list,
but many of them are used as singly linked list.
struct sched_class;
struct acpi_pci_driver;
struct adb_request;
struct atalk_route;
struct core_thread;
struct dma_async_tx_descriptor;
struct erase_info;
struct esp_pio_buffer;
struct fdtable;
struct floppy_raw_cmd;
struct ftrace_ops;
struct hdlc_proto;
struct hwif_s;
struct ippp_buf_queue;
struct irqaction;
struct isdn_net_local_s;
struct kcore_list;
struct mfc6_cache;
struct mfc_cache;
struct nls_table;
struct notifier_block;
struct page_list;
struct pbe;
struct phone_device;
struct pnp_id;
struct r3964_block_header;
struct r3964_client_info;
struct r3964_message;
struct rcu_head;
struct resource_list;
struct sched_group;
struct sdio_func_tuple;
struct tasklet_struct;
struct tty_buffer;
struct xor_block_template;
Thus, I believe it is acceptable that TOMOYO uses singly linked list
unless Linus comes out and yell "No!".
Regards.
On Tue, 6 Jan 2009, Tetsuo Handa wrote:
>
> James Morris wrote:
> > This has a technical ack from Paul, but what about Linus' long-standing
> > objection to singly-linked lists in the kernel? I'm sure this has been
> > discussed re. your patches, but I can't find a reference.
> I couldn't find one neither. (What does "re." mean?)
http://en.wiktionary.org/wiki/re#Etymology_1
> But optimistically speaking, there are many in-tree users who define "struct"
> without "prev" pointer.
>
> # grep -hr 'struct [a-zA-Z0-9_]* \*next;' linux-2.6.28/include/linux/ | wc -l
> 42
> # grep -hr 'struct [a-zA-Z0-9_]* \*prev;' linux-2.6.28/include/linux/ | wc -l
> 7
>
> Not all structures listed below are used as singly linked list,
> but many of them are used as singly linked list.
Can any of these be converted to your singly linked list implementation ?
>
> struct sched_class;
> struct acpi_pci_driver;
> struct adb_request;
> struct atalk_route;
> struct core_thread;
> struct dma_async_tx_descriptor;
> struct erase_info;
> struct esp_pio_buffer;
> struct fdtable;
> struct floppy_raw_cmd;
> struct ftrace_ops;
> struct hdlc_proto;
> struct hwif_s;
> struct ippp_buf_queue;
> struct irqaction;
> struct isdn_net_local_s;
> struct kcore_list;
> struct mfc6_cache;
> struct mfc_cache;
> struct nls_table;
> struct notifier_block;
> struct page_list;
> struct pbe;
> struct phone_device;
> struct pnp_id;
> struct r3964_block_header;
> struct r3964_client_info;
> struct r3964_message;
> struct rcu_head;
> struct resource_list;
> struct sched_group;
> struct sdio_func_tuple;
> struct tasklet_struct;
> struct tty_buffer;
> struct xor_block_template;
>
> Thus, I believe it is acceptable that TOMOYO uses singly linked list
> unless Linus comes out and yell "No!".
He's yelled no in the past, so there needs to be a convincing argument
which he'll accept.
- James
--
James Morris
<[email protected]>
James Morris wrote:
> > Not all structures listed below are used as singly linked list,
> > but many of them are used as singly linked list.
>
> Can any of these be converted to your singly linked list implementation ?
Maybe, but will be few.
Regular singly linked list (which is known as "slist") implementation has
below characteristics.
(1) Supports "add", "read" and "remove" operations.
(2) Caller holds read lock when reading, and holds write lock when adding or
removing.
(3) Iteration method (for_each_*) needn't to call rcu_dereference() because
caller holds locks as needed.
TOMOYO's singly linked list (which is named as "list1") implementation has
below characteristics.
(1) Supports "add" and "read" operations.
(2) Caller holds a lock when adding, but doesn't hold a lock when reading.
(3) Iteration method (for_each_*) needs to call rcu_dereference() because
caller doesn't hold a lock when reading.
I think it is not a good thing to rename "list1" to "slist".
Many of these in-tree singly linked list users need to use regular singly
linked list because they need to remove elements from their lists.
Quoting Tetsuo Handa ([email protected]):
> James Morris wrote:
> > > Not all structures listed below are used as singly linked list,
> > > but many of them are used as singly linked list.
> >
> > Can any of these be converted to your singly linked list implementation ?
>
> Maybe, but will be few.
>
> Regular singly linked list (which is known as "slist") implementation has
> below characteristics.
>
> (1) Supports "add", "read" and "remove" operations.
> (2) Caller holds read lock when reading, and holds write lock when adding or
> removing.
> (3) Iteration method (for_each_*) needn't to call rcu_dereference() because
> caller holds locks as needed.
>
> TOMOYO's singly linked list (which is named as "list1") implementation has
> below characteristics.
>
> (1) Supports "add" and "read" operations.
> (2) Caller holds a lock when adding, but doesn't hold a lock when reading.
> (3) Iteration method (for_each_*) needs to call rcu_dereference() because
> caller doesn't hold a lock when reading.
>
> I think it is not a good thing to rename "list1" to "slist".
How about alist (or aolist) for append-only list?
The problem with list1 is that it *really* doesn't imply the
characteristics you cite.
-serge
Serge E. Hallyn wrote:
> > TOMOYO's singly linked list (which is named as "list1") implementation has
> > below characteristics.
> >
> > (1) Supports "add" and "read" operations.
> > (2) Caller holds a lock when adding, but doesn't hold a lock when reading.
> > (3) Iteration method (for_each_*) needs to call rcu_dereference() because
> > caller doesn't hold a lock when reading.
> >
> > I think it is not a good thing to rename "list1" to "slist".
>
> How about alist (or aolist) for append-only list?
>
> The problem with list1 is that it *really* doesn't imply the
> characteristics you cite.
>
OK.
A developer who reads a code using this list likely wonders
"Why no read_lock() before reading this list?".
Thus, I'd like to rename to "rlfl" (Read-Lock-Free List).
James Morris wrote:
> > By ommiting pointer to previous element, the reader becomes read lock free,
> > which is good thing for implementing "write once read many" list.
>
> This has a technical ack from Paul, but what about Linus' long-standing
> objection to singly-linked lists in the kernel? I'm sure this has been
> discussed re. your patches, but I can't find a reference.
>
OK, for reviewers' ease, I purged list1 for now.
Next posting (#15) will use standard doubly linked list with rw_semaphore.
Thanks.