lkml.org 
[lkml]   [2009]   [Jan]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [TOMOYO #14 (mmotm 2008-12-30-16-05) 02/10] Singly linked list implementation.
    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 <penguin-kernel@I-love.SAKURA.ne.jp>
    > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
    > ---
    > 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 majordomo@vger.kernel.org
    > More majordomo info at http://vger.kernel.org/majordomo-info.html
    >

    --
    James Morris
    <jmorris@namei.org>


    \
     
     \ /
      Last update: 2009-01-05 10:11    [W:2.326 / U:0.040 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site