kern/list: update

This change includes various fixes and additions, and in particular a
subset of lock-less capable variants of the original interface.

8 files changed, 209 insertions, 32 deletions

diff --git a/Makefrag.am b/Makefrag.am
index c52381e2..fca8820a 100644
--- a/Makefrag.am
+++ b/Makefrag.am
@@ -23,6 +23,7 @@ x15_SOURCES +=              \
 	kern/kmem_i.h       \
 	kern/limits.h       \
 	kern/list.h         \
+	kern/list_types.h   \
 	kern/llsync.c       \
 	kern/llsync.h       \
 	kern/llsync_i.h     \
diff --git a/kern/condition_types.h b/kern/condition_types.h
index 9f68bf44..03b22676 100644
--- a/kern/condition_types.h
+++ b/kern/condition_types.h
@@ -21,7 +21,7 @@
 #ifndef _KERN_CONDITION_TYPES_H
 #define _KERN_CONDITION_TYPES_H
 
-#include <kern/list.h>
+#include <kern/list_types.h>
 #include <kern/mutex_types.h>
 #include <kern/spinlock_types.h>
 
diff --git a/kern/evcnt.h b/kern/evcnt.h
index f585fad0..ae014031 100644
--- a/kern/evcnt.h
+++ b/kern/evcnt.h
@@ -21,7 +21,7 @@
 #ifndef _KERN_EVCNT_H
 #define _KERN_EVCNT_H
 
-#include <kern/list.h>
+#include <kern/list_types.h>
 
 /*
  * Size of the buffer storing an event counter name.
diff --git a/kern/list.h b/kern/list.h
index c85e8c15..8cd5a2d7 100644
--- a/kern/list.h
+++ b/kern/list.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009-2014 Richard Braun.
+ * Copyright (c) 2009-2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -21,6 +21,10 @@
 #ifndef _KERN_LIST_H
 #define _KERN_LIST_H
 
+#include <stdbool.h>
+
+#include <kern/list_types.h>
+#include <kern/llsync.h>
 #include <kern/macros.h>
 #include <kern/stddef.h>
 
@@ -34,10 +38,12 @@
  * list of free objects. A declaration like struct list free_node clearly
  * indicates it is used as part of a node in the free list.
  */
-struct list {
-    struct list *prev;
-    struct list *next;
-};
+struct list;
+
+/*
+ * Static list initializer.
+ */
+#define LIST_INITIALIZER(list) { &(list), &(list) }
 
 /*
  * Initialize a list.
@@ -52,7 +58,7 @@ list_init(struct list *list)
 /*
  * Initialize a list node.
  *
- * An entry is in no list when its node members point to NULL.
+ * An entry is in no lists when its node members point to NULL.
  */
 static inline void
 list_node_init(struct list *node)
@@ -62,9 +68,9 @@ list_node_init(struct list *node)
 }
 
 /*
- * Return true if node is in no list.
+ * Return true if node is in no lists.
  */
-static inline int
+static inline bool
 list_node_unlinked(const struct list *node)
 {
     return node->prev == NULL;
@@ -125,9 +131,21 @@ list_prev(const struct list *node)
     list_entry(list_last(list), type, member)
 
 /*
+ * Get the entry next to the given entry.
+ */
+#define list_next_entry(entry, member) \
+    list_entry(list_next(&(entry)->member), typeof(*(entry)), member)
+
+/*
+ * Get the entry previous to the given entry.
+ */
+#define list_prev_entry(entry, member) \
+    list_entry(list_prev(&(entry)->member), typeof(*(entry)), member)
+
+/*
  * Return true if node is after the last or before the first node of the list.
  */
-static inline int
+static inline bool
 list_end(const struct list *list, const struct list *node)
 {
     return list == node;
@@ -136,7 +154,7 @@ list_end(const struct list *list, const struct list *node)
 /*
  * Return true if list is empty.
  */
-static inline int
+static inline bool
 list_empty(const struct list *list)
 {
     return list == list->next;
@@ -145,7 +163,7 @@ list_empty(const struct list *list)
 /*
  * Return true if list contains exactly one node.
  */
-static inline int
+static inline bool
 list_singular(const struct list *list)
 {
     return (list != list->next) && (list->next == list->prev);
@@ -225,6 +243,8 @@ list_set_head(struct list *new_head, const struct list *old_head)
 
 /*
  * Add a node between two nodes.
+ *
+ * This function is private.
  */
 static inline void
 list_add(struct list *prev, struct list *next, struct list *node)
@@ -324,40 +344,168 @@ for (node = list_last(list), tmp = list_prev(node); \
  * The entry node must not be altered during the loop.
  */
 #define list_for_each_entry(list, entry, member)                    \
-for (entry = list_entry(list_first(list), typeof(*entry), member);  \
+for (entry = list_first_entry(list, typeof(*entry), member);        \
      !list_end(list, &entry->member);                               \
-     entry = list_entry(list_next(&entry->member), typeof(*entry),  \
-                        member))
+     entry = list_next_entry(entry, member))
 
 /*
  * Forge a loop to process all entries of a list.
  */
 #define list_for_each_entry_safe(list, entry, tmp, member)          \
-for (entry = list_entry(list_first(list), typeof(*entry), member),  \
-       tmp = list_entry(list_next(&entry->member), typeof(*entry),  \
-                        member);                                    \
+for (entry = list_first_entry(list, typeof(*entry), member),        \
+       tmp = list_next_entry(entry, member);                        \
      !list_end(list, &entry->member);                               \
-     entry = tmp, tmp = list_entry(list_next(&entry->member),       \
-                                   typeof(*entry), member))
+     entry = tmp, tmp = list_next_entry(entry, member))
 
 /*
  * Version of list_for_each_entry() that processes entries backward.
  */
 #define list_for_each_entry_reverse(list, entry, member)            \
-for (entry = list_entry(list_last(list), typeof(*entry), member);   \
+for (entry = list_last_entry(list, typeof(*entry), member);         \
      !list_end(list, &entry->member);                               \
-     entry = list_entry(list_prev(&entry->member), typeof(*entry),  \
-                        member))
+     entry = list_prev_entry(entry, member))
 
 /*
  * Version of list_for_each_entry_safe() that processes entries backward.
  */
 #define list_for_each_entry_reverse_safe(list, entry, tmp, member)  \
-for (entry = list_entry(list_last(list), typeof(*entry), member),   \
-       tmp = list_entry(list_prev(&entry->member), typeof(*entry),  \
-                        member);                                    \
+for (entry = list_last_entry(list, typeof(*entry), member),         \
+       tmp = list_prev_entry(entry, member);                        \
      !list_end(list, &entry->member);                               \
-     entry = tmp, tmp = list_entry(list_prev(&entry->member),       \
-                                   typeof(*entry), member))
+     entry = tmp, tmp = list_prev_entry(entry, member))
+
+/*
+ * Lockless variants
+ *
+ * This is a subset of the main interface that only supports forward traversal.
+ * In addition, list_end() is also allowed in read-side critical sections.
+ */
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define list_llsync_entry(node, type, member) \
+    structof(llsync_read_ptr(node), type, member)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct list *
+list_llsync_first(const struct list *list)
+{
+    return llsync_read_ptr(list->next);
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct list *
+list_llsync_next(const struct list *node)
+{
+    return llsync_read_ptr(node->next);
+}
+
+/*
+ * Get the first entry of a list.
+ *
+ * Unlike list_entry(), this macro may evaluate to NULL, because the node
+ * pointer can only be read once, preventing the combination of lockless
+ * list_empty()/list_first_entry() variants.
+ *
+ * Return NULL if the list is empty.
+ */
+#define list_llsync_first_entry(list, type, member)         \
+MACRO_BEGIN                                                 \
+    struct list *___list = (list);                          \
+    struct list *___first = llsync_read_ptr(___list->next); \
+    list_end(___list, ___first)                             \
+        ? NULL                                              \
+        : list_entry(___first, type, member);               \
+MACRO_END
+
+/*
+ * Add a node between two nodes.
+ *
+ * This function is private.
+ */
+static inline void
+list_llsync_add(struct list *prev, struct list *next, struct list *node)
+{
+    node->next = next;
+    node->prev = prev;
+    llsync_assign_ptr(prev->next, node);
+    next->prev = node;
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+list_llsync_insert_head(struct list *list, struct list *node)
+{
+    list_llsync_add(list, list->next, node);
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+list_llsync_insert_tail(struct list *list, struct list *node)
+{
+    list_llsync_add(list->prev, list, node);
+}
+
+/*
+ * Insert a node before another node.
+ */
+static inline void
+list_llsync_insert_before(struct list *next, struct list *node)
+{
+    list_llsync_add(next->prev, next, node);
+}
+
+/*
+ * Insert a node after another node.
+ */
+static inline void
+list_llsync_insert_after(struct list *prev, struct list *node)
+{
+    list_llsync_add(prev, prev->next, node);
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * After completion, the node is stale.
+ */
+static inline void
+list_llsync_remove(struct list *node)
+{
+    node->next->prev = node->prev;
+    llsync_assign_ptr(node->prev->next, node->next);
+}
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define list_llsync_for_each(list, node)    \
+for (node = list_llsync_first(list);        \
+     !list_end(list, node);                 \
+     node = list_llsync_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define list_llsync_for_each_entry(list, entry, member)     \
+for (entry = list_llsync_entry(list_first(list),            \
+                               typeof(*entry), member);     \
+     !list_end(list, &entry->member);                       \
+     entry = list_llsync_entry(list_next(&entry->member),   \
+                               typeof(*entry), member))
 
 #endif /* _KERN_LIST_H */
diff --git a/kern/list_types.h b/kern/list_types.h
new file mode 100644
index 00000000..d6573cf7
--- /dev/null
+++ b/kern/list_types.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Isolated type definition used to avoid inclusion circular dependencies.
+ */
+
+#ifndef _KERN_LIST_TYPES_H
+#define _KERN_LIST_TYPES_H
+
+struct list {
+    struct list *prev;
+    struct list *next;
+};
+
+#endif /* _KERN_LIST_TYPES_H */
diff --git a/kern/llsync.h b/kern/llsync.h
index f87fbb52..d269f2df 100644
--- a/kern/llsync.h
+++ b/kern/llsync.h
@@ -72,7 +72,6 @@
 
 #include <stdbool.h>
 
-#include <kern/list.h>
 #include <kern/macros.h>
 #include <kern/llsync_i.h>
 #include <kern/thread.h>
diff --git a/kern/mutex_types.h b/kern/mutex_types.h
index 4f99b400..b348fb7b 100644
--- a/kern/mutex_types.h
+++ b/kern/mutex_types.h
@@ -21,7 +21,7 @@
 #ifndef _KERN_MUTEX_TYPES_H
 #define _KERN_MUTEX_TYPES_H
 
-#include <kern/list.h>
+#include <kern/list_types.h>
 #include <kern/spinlock_types.h>
 
 struct mutex {
diff --git a/kern/thread_i.h b/kern/thread_i.h
index 6d9bc501..d004298f 100644
--- a/kern/thread_i.h
+++ b/kern/thread_i.h
@@ -20,7 +20,7 @@
 
 #include <kern/condition_types.h>
 #include <kern/cpumap.h>
-#include <kern/list.h>
+#include <kern/list_types.h>
 #include <kern/macros.h>
 #include <kern/mutex_types.h>
 #include <kern/param.h>