diff mbox series

[07/27] modpost: import include/linux/list.h

Message ID 20220424190811.1678416-8-masahiroy@kernel.org (mailing list archive)
State New, archived
Headers show
Series kbuild: yet another series of cleanups (modpost and LTO) | expand

Commit Message

Masahiro Yamada April 24, 2022, 7:07 p.m. UTC 
Import include/linux/list.h to use convenient list macros in modpost.

I dropped kernel-space code such as {WRITE,READ}_ONCE etc. and unneeded
macros.

I also imported container_of() from include/linux/container_of.h and
type definitions from include/linux/types.h.

Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
---

 scripts/mod/list.h | 336 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 336 insertions(+)
 create mode 100644 scripts/mod/list.h

Comments

Nick Desaulniers April 25, 2022, 6:42 p.m. UTC | #1 
On Sun, Apr 24, 2022 at 12:09 PM Masahiro Yamada <masahiroy@kernel.org> wrote:
>
> Import include/linux/list.h to use convenient list macros in modpost.
>
> I dropped kernel-space code such as {WRITE,READ}_ONCE etc. and unneeded
> macros.
>
> I also imported container_of() from include/linux/container_of.h and
> type definitions from include/linux/types.h.

Is there a better way to just use the kernel headers? I kind of hate
copy+paste since the in tree duplication will diverge over time.

>
> Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
> ---
>
>  scripts/mod/list.h | 336 +++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 336 insertions(+)
>  create mode 100644 scripts/mod/list.h
>
> diff --git a/scripts/mod/list.h b/scripts/mod/list.h
> new file mode 100644
> index 000000000000..c87583a71714
> --- /dev/null
> +++ b/scripts/mod/list.h
> @@ -0,0 +1,336 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +#ifndef LIST_H
> +#define LIST_H
> +
> +#include <stdbool.h>
> +#include <stddef.h>
> +
> +/* Are two types/vars the same type (ignoring qualifiers)? */
> +#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
> +
> +/**
> + * container_of - cast a member of a structure out to the containing structure
> + * @ptr:       the pointer to the member.
> + * @type:      the type of the container struct this is embedded in.
> + * @member:    the name of the member within the struct.
> + *
> + */
> +#define container_of(ptr, type, member) ({                             \
> +       void *__mptr = (void *)(ptr);                                   \
> +       _Static_assert(__same_type(*(ptr), ((type *)0)->member) ||      \
> +                     __same_type(*(ptr), void),                        \
> +                     "pointer type mismatch in container_of()");       \
> +       ((type *)(__mptr - offsetof(type, member))); })
> +
> +#define LIST_POISON1  ((void *) 0x100)
> +#define LIST_POISON2  ((void *) 0x122)
> +
> +/*
> + * Circular doubly linked list implementation.
> + *
> + * Some of the internal functions ("__xxx") are useful when
> + * manipulating whole lists rather than single entries, as
> + * sometimes we already know the next/prev entries and we can
> + * generate better code by using them directly rather than
> + * using the generic single-entry routines.
> + */
> +
> +struct list_head {
> +       struct list_head *next, *prev;
> +};
> +
> +#define LIST_HEAD_INIT(name) { &(name), &(name) }
> +
> +#define LIST_HEAD(name) \
> +       struct list_head name = LIST_HEAD_INIT(name)
> +
> +/**
> + * INIT_LIST_HEAD - Initialize a list_head structure
> + * @list: list_head structure to be initialized.
> + *
> + * Initializes the list_head to point to itself.  If it is a list header,
> + * the result is an empty list.
> + */
> +static inline void INIT_LIST_HEAD(struct list_head *list)
> +{
> +       list->next = list;
> +       list->prev = list;
> +}
> +
> +/*
> + * Insert a new entry between two known consecutive entries.
> + *
> + * This is only for internal list manipulation where we know
> + * the prev/next entries already!
> + */
> +static inline void __list_add(struct list_head *new,
> +                             struct list_head *prev,
> +                             struct list_head *next)
> +{
> +       next->prev = new;
> +       new->next = next;
> +       new->prev = prev;
> +       prev->next = new;
> +}
> +
> +/**
> + * list_add - add a new entry
> + * @new: new entry to be added
> + * @head: list head to add it after
> + *
> + * Insert a new entry after the specified head.
> + * This is good for implementing stacks.
> + */
> +static inline void list_add(struct list_head *new, struct list_head *head)
> +{
> +       __list_add(new, head, head->next);
> +}
> +
> +/**
> + * list_add_tail - add a new entry
> + * @new: new entry to be added
> + * @head: list head to add it before
> + *
> + * Insert a new entry before the specified head.
> + * This is useful for implementing queues.
> + */
> +static inline void list_add_tail(struct list_head *new, struct list_head *head)
> +{
> +       __list_add(new, head->prev, head);
> +}
> +
> +/*
> + * Delete a list entry by making the prev/next entries
> + * point to each other.
> + *
> + * This is only for internal list manipulation where we know
> + * the prev/next entries already!
> + */
> +static inline void __list_del(struct list_head *prev, struct list_head *next)
> +{
> +       next->prev = prev;
> +       prev->next = next;
> +}
> +
> +static inline void __list_del_entry(struct list_head *entry)
> +{
> +       __list_del(entry->prev, entry->next);
> +}
> +
> +/**
> + * list_del - deletes entry from list.
> + * @entry: the element to delete from the list.
> + * Note: list_empty() on entry does not return true after this, the entry is
> + * in an undefined state.
> + */
> +static inline void list_del(struct list_head *entry)
> +{
> +       __list_del_entry(entry);
> +       entry->next = LIST_POISON1;
> +       entry->prev = LIST_POISON2;
> +}
> +
> +/**
> + * list_is_head - tests whether @list is the list @head
> + * @list: the entry to test
> + * @head: the head of the list
> + */
> +static inline int list_is_head(const struct list_head *list, const struct list_head *head)
> +{
> +       return list == head;
> +}
> +
> +/**
> + * list_empty - tests whether a list is empty
> + * @head: the list to test.
> + */
> +static inline int list_empty(const struct list_head *head)
> +{
> +       return head->next == head;
> +}
> +
> +/**
> + * list_entry - get the struct for this entry
> + * @ptr:       the &struct list_head pointer.
> + * @type:      the type of the struct this is embedded in.
> + * @member:    the name of the list_head within the struct.
> + */
> +#define list_entry(ptr, type, member) \
> +       container_of(ptr, type, member)
> +
> +/**
> + * list_first_entry - get the first element from a list
> + * @ptr:       the list head to take the element from.
> + * @type:      the type of the struct this is embedded in.
> + * @member:    the name of the list_head within the struct.
> + *
> + * Note, that list is expected to be not empty.
> + */
> +#define list_first_entry(ptr, type, member) \
> +       list_entry((ptr)->next, type, member)
> +
> +/**
> + * list_next_entry - get the next element in list
> + * @pos:       the type * to cursor
> + * @member:    the name of the list_head within the struct.
> + */
> +#define list_next_entry(pos, member) \
> +       list_entry((pos)->member.next, typeof(*(pos)), member)
> +
> +/**
> + * list_entry_is_head - test if the entry points to the head of the list
> + * @pos:       the type * to cursor
> + * @head:      the head for your list.
> + * @member:    the name of the list_head within the struct.
> + */
> +#define list_entry_is_head(pos, head, member)                          \
> +       (&pos->member == (head))
> +
> +/**
> + * list_for_each_entry -       iterate over list of given type
> + * @pos:       the type * to use as a loop cursor.
> + * @head:      the head for your list.
> + * @member:    the name of the list_head within the struct.
> + */
> +#define list_for_each_entry(pos, head, member)                         \
> +       for (pos = list_first_entry(head, typeof(*pos), member);        \
> +            !list_entry_is_head(pos, head, member);                    \
> +            pos = list_next_entry(pos, member))
> +
> +/**
> + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
> + * @pos:       the type * to use as a loop cursor.
> + * @n:         another type * to use as temporary storage
> + * @head:      the head for your list.
> + * @member:    the name of the list_head within the struct.
> + */
> +#define list_for_each_entry_safe(pos, n, head, member)                 \
> +       for (pos = list_first_entry(head, typeof(*pos), member),        \
> +               n = list_next_entry(pos, member);                       \
> +            !list_entry_is_head(pos, head, member);                    \
> +            pos = n, n = list_next_entry(n, member))
> +
> +/*
> + * Double linked lists with a single pointer list head.
> + * Mostly useful for hash tables where the two pointer list head is
> + * too wasteful.
> + * You lose the ability to access the tail in O(1).
> + */
> +
> +struct hlist_head {
> +       struct hlist_node *first;
> +};
> +
> +struct hlist_node {
> +       struct hlist_node *next, **pprev;
> +};
> +
> +#define HLIST_HEAD_INIT { .first = NULL }
> +#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
> +#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
> +static inline void INIT_HLIST_NODE(struct hlist_node *h)
> +{
> +       h->next = NULL;
> +       h->pprev = NULL;
> +}
> +
> +/**
> + * hlist_unhashed - Has node been removed from list and reinitialized?
> + * @h: Node to be checked
> + *
> + * Not that not all removal functions will leave a node in unhashed
> + * state.  For example, hlist_nulls_del_init_rcu() does leave the
> + * node in unhashed state, but hlist_nulls_del() does not.
> + */
> +static inline int hlist_unhashed(const struct hlist_node *h)
> +{
> +       return !h->pprev;
> +}
> +
> +static inline void __hlist_del(struct hlist_node *n)
> +{
> +       struct hlist_node *next = n->next;
> +       struct hlist_node **pprev = n->pprev;
> +
> +       *pprev = next;
> +       if (next)
> +               next->pprev = pprev;
> +}
> +
> +/**
> + * hlist_del - Delete the specified hlist_node from its list
> + * @n: Node to delete.
> + *
> + * Note that this function leaves the node in hashed state.  Use
> + * hlist_del_init() or similar instead to unhash @n.
> + */
> +static inline void hlist_del(struct hlist_node *n)
> +{
> +       __hlist_del(n);
> +       n->next = LIST_POISON1;
> +       n->pprev = LIST_POISON2;
> +}
> +
> +/**
> + * hlist_del_init - Delete the specified hlist_node from its list and initialize
> + * @n: Node to delete.
> + *
> + * Note that this function leaves the node in unhashed state.
> + */
> +static inline void hlist_del_init(struct hlist_node *n)
> +{
> +       if (!hlist_unhashed(n)) {
> +               __hlist_del(n);
> +               INIT_HLIST_NODE(n);
> +       }
> +}
> +
> +/**
> + * hlist_add_head - add a new entry at the beginning of the hlist
> + * @n: new entry to be added
> + * @h: hlist head to add it after
> + *
> + * Insert a new entry after the specified head.
> + * This is good for implementing stacks.
> + */
> +static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
> +{
> +       struct hlist_node *first = h->first;
> +       n->next = first;
> +       if (first)
> +               first->pprev = &n->next;
> +       h->first = n;
> +       n->pprev = &h->first;
> +}
> +
> +#define hlist_entry(ptr, type, member) container_of(ptr, type, member)
> +
> +#define hlist_entry_safe(ptr, type, member) \
> +       ({ typeof(ptr) ____ptr = (ptr); \
> +          ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
> +       })
> +
> +/**
> + * hlist_for_each_entry        - iterate over list of given type
> + * @pos:       the type * to use as a loop cursor.
> + * @head:      the head for your list.
> + * @member:    the name of the hlist_node within the struct.
> + */
> +#define hlist_for_each_entry(pos, head, member)                                \
> +       for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
> +            pos;                                                       \
> +            pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
> +
> +/**
> + * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
> + * @pos:       the type * to use as a loop cursor.
> + * @n:         a &struct hlist_node to use as temporary storage
> + * @head:      the head for your list.
> + * @member:    the name of the hlist_node within the struct.
> + */
> +#define hlist_for_each_entry_safe(pos, n, head, member)                        \
> +       for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
> +            pos && ({ n = pos->member.next; 1; });                     \
> +            pos = hlist_entry_safe(n, typeof(*pos), member))
> +
> +#endif /* LIST_H */
> --
> 2.32.0
>
Masahiro Yamada April 26, 2022, 4:05 a.m. UTC | #2 
On Tue, Apr 26, 2022 at 3:42 AM Nick Desaulniers
<ndesaulniers@google.com> wrote:
>
> On Sun, Apr 24, 2022 at 12:09 PM Masahiro Yamada <masahiroy@kernel.org> wrote:
> >
> > Import include/linux/list.h to use convenient list macros in modpost.
> >
> > I dropped kernel-space code such as {WRITE,READ}_ONCE etc. and unneeded
> > macros.
> >
> > I also imported container_of() from include/linux/container_of.h and
> > type definitions from include/linux/types.h.
>
> Is there a better way to just use the kernel headers?

Presumably no.
include/linux/list.h includes more.

Adding so many #ifdef __KERNEL__ stubs
would be really ugly.


> I kind of hate
> copy+paste since the in tree duplication will diverge over time.

I only cherry-picked some macros from include/linux/kernel.h

No need to resync.
Nick Desaulniers April 26, 2022, 4:29 p.m. UTC | #3 
On Sun, Apr 24, 2022 at 12:09 PM Masahiro Yamada <masahiroy@kernel.org> wrote:
>
> Import include/linux/list.h to use convenient list macros in modpost.
>
> I dropped kernel-space code such as {WRITE,READ}_ONCE etc. and unneeded
> macros.
>
> I also imported container_of() from include/linux/container_of.h and
> type definitions from include/linux/types.h.
>
> Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Ok then, just two small nits about two comments, which may have been
just copied over from the sources.
Reviewed-by: Nick Desaulniers <ndesaulniers@google.com>

> ---
>
>  scripts/mod/list.h | 336 +++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 336 insertions(+)
>  create mode 100644 scripts/mod/list.h
>
> diff --git a/scripts/mod/list.h b/scripts/mod/list.h
> new file mode 100644
> index 000000000000..c87583a71714
> --- /dev/null
> +++ b/scripts/mod/list.h
> @@ -0,0 +1,336 @@

<snip>

> +/**
> + * list_for_each_entry -       iterate over list of given type

^ Excessive whitespace after the `-`

> + * @pos:       the type * to use as a loop cursor.
> + * @head:      the head for your list.
> + * @member:    the name of the list_head within the struct.
> + */
> +#define list_for_each_entry(pos, head, member)                         \
> +       for (pos = list_first_entry(head, typeof(*pos), member);        \
> +            !list_entry_is_head(pos, head, member);                    \
> +            pos = list_next_entry(pos, member))
> +
> +/**
> + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

^ This sounds like two sentences and looks like it's missing
punctuation separating them?

"iterate over list of given type. Safe against removal of list entry"
Masahiro Yamada April 30, 2022, 2:21 p.m. UTC | #4 
On Wed, Apr 27, 2022 at 1:30 AM Nick Desaulniers
<ndesaulniers@google.com> wrote:
>
> On Sun, Apr 24, 2022 at 12:09 PM Masahiro Yamada <masahiroy@kernel.org> wrote:
> >
> > Import include/linux/list.h to use convenient list macros in modpost.
> >
> > I dropped kernel-space code such as {WRITE,READ}_ONCE etc. and unneeded
> > macros.
> >
> > I also imported container_of() from include/linux/container_of.h and
> > type definitions from include/linux/types.h.
> >
> > Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
>
> Ok then, just two small nits about two comments, which may have been
> just copied over from the sources.
> Reviewed-by: Nick Desaulniers <ndesaulniers@google.com>
>
> > ---
> >
> >  scripts/mod/list.h | 336 +++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 336 insertions(+)
> >  create mode 100644 scripts/mod/list.h
> >
> > diff --git a/scripts/mod/list.h b/scripts/mod/list.h
> > new file mode 100644
> > index 000000000000..c87583a71714
> > --- /dev/null
> > +++ b/scripts/mod/list.h
> > @@ -0,0 +1,336 @@
>
> <snip>
>
> > +/**
> > + * list_for_each_entry -       iterate over list of given type
>
> ^ Excessive whitespace after the `-`
>
> > + * @pos:       the type * to use as a loop cursor.
> > + * @head:      the head for your list.
> > + * @member:    the name of the list_head within the struct.
> > + */
> > +#define list_for_each_entry(pos, head, member)                         \
> > +       for (pos = list_first_entry(head, typeof(*pos), member);        \
> > +            !list_entry_is_head(pos, head, member);                    \
> > +            pos = list_next_entry(pos, member))
> > +
> > +/**
> > + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
>
> ^ This sounds like two sentences and looks like it's missing
> punctuation separating them?
>
> "iterate over list of given type. Safe against removal of list entry"


OK, I will fold your suggestions.

If you have a chance to fix up include/linux/list.h in the same way,
that would be appreciated.

./scripts/checkpatch.pl  -f  include/linux/list.h

might be useful to find out style issues.
diff mbox series

Patch

diff --git a/scripts/mod/list.h b/scripts/mod/list.h
new file mode 100644
index 000000000000..c87583a71714
--- /dev/null
+++ b/scripts/mod/list.h
@@ -0,0 +1,336 @@ 
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef LIST_H
+#define LIST_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+/* Are two types/vars the same type (ignoring qualifiers)? */
+#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ */
+#define container_of(ptr, type, member) ({				\
+	void *__mptr = (void *)(ptr);					\
+	_Static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
+		      __same_type(*(ptr), void),			\
+		      "pointer type mismatch in container_of()");	\
+	((type *)(__mptr - offsetof(type, member))); })
+
+#define LIST_POISON1  ((void *) 0x100)
+#define LIST_POISON2  ((void *) 0x122)
+
+/*
+ * Circular doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
+
+struct list_head {
+	struct list_head *next, *prev;
+};
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define LIST_HEAD(name) \
+	struct list_head name = LIST_HEAD_INIT(name)
+
+/**
+ * INIT_LIST_HEAD - Initialize a list_head structure
+ * @list: list_head structure to be initialized.
+ *
+ * Initializes the list_head to point to itself.  If it is a list header,
+ * the result is an empty list.
+ */
+static inline void INIT_LIST_HEAD(struct list_head *list)
+{
+	list->next = list;
+	list->prev = list;
+}
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_head *new,
+			      struct list_head *prev,
+			      struct list_head *next)
+{
+	next->prev = new;
+	new->next = next;
+	new->prev = prev;
+	prev->next = new;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void list_add(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head, head->next);
+}
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head->prev, head);
+}
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_head *prev, struct list_head *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+static inline void __list_del_entry(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+static inline void list_del(struct list_head *entry)
+{
+	__list_del_entry(entry);
+	entry->next = LIST_POISON1;
+	entry->prev = LIST_POISON2;
+}
+
+/**
+ * list_is_head - tests whether @list is the list @head
+ * @list: the entry to test
+ * @head: the head of the list
+ */
+static inline int list_is_head(const struct list_head *list, const struct list_head *head)
+{
+	return list == head;
+}
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(const struct list_head *head)
+{
+	return head->next == head;
+}
+
+/**
+ * list_entry - get the struct for this entry
+ * @ptr:	the &struct list_head pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_entry(ptr, type, member) \
+	container_of(ptr, type, member)
+
+/**
+ * list_first_entry - get the first element from a list
+ * @ptr:	the list head to take the element from.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define list_first_entry(ptr, type, member) \
+	list_entry((ptr)->next, type, member)
+
+/**
+ * list_next_entry - get the next element in list
+ * @pos:	the type * to cursor
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_next_entry(pos, member) \
+	list_entry((pos)->member.next, typeof(*(pos)), member)
+
+/**
+ * list_entry_is_head - test if the entry points to the head of the list
+ * @pos:	the type * to cursor
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_entry_is_head(pos, head, member)				\
+	(&pos->member == (head))
+
+/**
+ * list_for_each_entry	-	iterate over list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_for_each_entry(pos, head, member)				\
+	for (pos = list_first_entry(head, typeof(*pos), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = list_next_entry(pos, member))
+
+/**
+ * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = list_first_entry(head, typeof(*pos), member),	\
+		n = list_next_entry(pos, member);			\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = n, n = list_next_entry(n, member))
+
+/*
+ * Double linked lists with a single pointer list head.
+ * Mostly useful for hash tables where the two pointer list head is
+ * too wasteful.
+ * You lose the ability to access the tail in O(1).
+ */
+
+struct hlist_head {
+	struct hlist_node *first;
+};
+
+struct hlist_node {
+	struct hlist_node *next, **pprev;
+};
+
+#define HLIST_HEAD_INIT { .first = NULL }
+#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
+#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
+static inline void INIT_HLIST_NODE(struct hlist_node *h)
+{
+	h->next = NULL;
+	h->pprev = NULL;
+}
+
+/**
+ * hlist_unhashed - Has node been removed from list and reinitialized?
+ * @h: Node to be checked
+ *
+ * Not that not all removal functions will leave a node in unhashed
+ * state.  For example, hlist_nulls_del_init_rcu() does leave the
+ * node in unhashed state, but hlist_nulls_del() does not.
+ */
+static inline int hlist_unhashed(const struct hlist_node *h)
+{
+	return !h->pprev;
+}
+
+static inline void __hlist_del(struct hlist_node *n)
+{
+	struct hlist_node *next = n->next;
+	struct hlist_node **pprev = n->pprev;
+
+	*pprev = next;
+	if (next)
+		next->pprev = pprev;
+}
+
+/**
+ * hlist_del - Delete the specified hlist_node from its list
+ * @n: Node to delete.
+ *
+ * Note that this function leaves the node in hashed state.  Use
+ * hlist_del_init() or similar instead to unhash @n.
+ */
+static inline void hlist_del(struct hlist_node *n)
+{
+	__hlist_del(n);
+	n->next = LIST_POISON1;
+	n->pprev = LIST_POISON2;
+}
+
+/**
+ * hlist_del_init - Delete the specified hlist_node from its list and initialize
+ * @n: Node to delete.
+ *
+ * Note that this function leaves the node in unhashed state.
+ */
+static inline void hlist_del_init(struct hlist_node *n)
+{
+	if (!hlist_unhashed(n)) {
+		__hlist_del(n);
+		INIT_HLIST_NODE(n);
+	}
+}
+
+/**
+ * hlist_add_head - add a new entry at the beginning of the hlist
+ * @n: new entry to be added
+ * @h: hlist head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
+{
+	struct hlist_node *first = h->first;
+	n->next = first;
+	if (first)
+		first->pprev = &n->next;
+	h->first = n;
+	n->pprev = &h->first;
+}
+
+#define hlist_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define hlist_entry_safe(ptr, type, member) \
+	({ typeof(ptr) ____ptr = (ptr); \
+	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
+	})
+
+/**
+ * hlist_for_each_entry	- iterate over list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry(pos, head, member)				\
+	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
+	     pos;							\
+	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
+
+/**
+ * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @n:		a &struct hlist_node to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
+	     pos && ({ n = pos->member.next; 1; });			\
+	     pos = hlist_entry_safe(n, typeof(*pos), member))
+
+#endif /* LIST_H */