Add implementation of wait-free unordered list.
authorKevin Klues <klueska@cs.berkeley.edu>
Fri, 22 Aug 2014 18:02:58 +0000 (11:02 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Fri, 22 Aug 2014 18:02:58 +0000 (11:02 -0700)
The list is ever-increasing in size, in that once space is created to
accomodate an item in the list, that space is never freed until the
entire list is destroyed. Items are inserted in the list such that
ordering on removal is not guaranteed.

This structure is useful in situations when you want to maintain a
small pool of objects that are shared amongst a larger set of
objects, but only get used for a short period of time (e.g. futext
element structs, sigdata structs, etc.).

user/parlib/include/waitfreelist.h [new file with mode: 0644]
user/parlib/waitfreelist.c [new file with mode: 0644]

diff --git a/user/parlib/include/waitfreelist.h b/user/parlib/include/waitfreelist.h
new file mode 100644 (file)
index 0000000..926e551
--- /dev/null
@@ -0,0 +1,50 @@
+/* Copyright (c) 2014 The Regents of the University of California
+ * Kevin Klues <klueska@cs.berkeley.edu>
+ * Andrew Waterman <waterman@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * A wait-free unordered list data structure.
+ * 
+ */
+
+#ifndef _PARLIB_WAITFREELIST_H
+#define _PARLIB_WAITFREELIST_H
+
+#include <string.h>
+
+struct wfl_entry {
+  struct wfl_entry *next;
+  void *data;
+};
+
+struct wfl {
+  struct wfl_entry *head;
+  struct wfl_entry first;
+};
+
+#define WFL_INITIALIZER(list) {&(list).first, {0, 0}}
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void wfl_init(struct wfl *list);
+void wfl_destroy(struct wfl *list);
+size_t wfl_capacity(struct wfl *list);
+size_t wfl_size(struct wfl *list);
+void wfl_insert(struct wfl *list, void *data);
+void *wfl_remove(struct wfl *list);
+size_t wfl_remove_all(struct wfl *list, void *data);
+
+/* Iterate over list.  Safe w.r.t. inserts, but not w.r.t. removals. */
+#define wfl_foreach_unsafe(elm, list) \
+  for (struct wfl_entry *_p = (list)->head; \
+       elm = _p == NULL ? NULL : _p->data, _p != NULL; \
+       _p = _p->next) \
+    if (elm)
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/user/parlib/waitfreelist.c b/user/parlib/waitfreelist.c
new file mode 100644 (file)
index 0000000..aa53e25
--- /dev/null
@@ -0,0 +1,131 @@
+/* Copyright (c) 2014 The Regents of the University of California
+ * Kevin Klues <klueska@cs.berkeley.edu>
+ * Andrew Waterman <waterman@cs.berkeley.edu>
+ * See LICENSE for details.
+ */
+
+#include <assert.h>
+#include <stdlib.h>
+#include <arch/atomic.h>
+#include <waitfreelist.h>
+
+void wfl_init(struct wfl *list)
+{
+  list->first.next = NULL;
+  list->first.data = NULL;
+  list->head = &list->first;
+}
+
+void wfl_destroy(struct wfl *list)
+{
+  assert(list->first.data == NULL);
+  struct wfl_entry *p = list->first.next; // don't free the first element
+  while (p != NULL) {
+    assert(p->data == NULL);
+    struct wfl_entry *tmp = p;
+    p = p->next;
+    free(tmp);
+  }
+}
+
+size_t wfl_capacity(struct wfl *list)
+{
+  size_t res = 0;
+  for (struct wfl_entry *p = list->head; p != NULL; p = p->next)
+    res++;
+  return res;
+}
+
+size_t wfl_size(struct wfl *list)
+{
+  size_t res = 0;
+  for (struct wfl_entry *p = list->head; p != NULL; p = p->next)
+    res += p->data != NULL;
+  return res;
+}
+
+#if 0
+void wfl_insert(struct wfl *list, void *data)
+{
+retry:
+  struct wfl_entry *p = list->head; // list head is never null
+  struct wfl_entry *new_entry = NULL;
+  while (1) {
+    if (p->data == NULL) {
+      if (__sync_bool_compare_and_swap(&p->data, NULL, data)) {
+        free(new_entry);
+        return;
+      }
+    }
+
+    if (p->next != NULL) {
+      p = p->next;
+      continue;
+    }
+
+    if (new_entry == NULL) {
+      new_entry = malloc(sizeof(struct wfl_entry));
+      if (new_entry == NULL)
+        abort();
+      new_entry->data = data;
+      new_entry->next = NULL;
+      wmb();
+    }
+    if (__sync_bool_compare_and_swap(&p->next, NULL, new_entry))
+      return;
+    goto retry;
+    p = list->head;
+  }
+}
+#endif
+
+void wfl_insert(struct wfl *list, void *data)
+{
+  struct wfl_entry *p = list->head; // list head is never null
+  while (1) {
+    if (p->data == NULL) {
+      if (__sync_bool_compare_and_swap(&p->data, NULL, data))
+        return;
+    }
+
+    if (p->next == NULL)
+      break;
+
+    p = p->next;
+  }
+
+  struct wfl_entry *new_entry = malloc(sizeof(struct wfl_entry));
+  if (new_entry == NULL)
+    abort();
+  new_entry->data = data;
+  new_entry->next = NULL;
+
+  wmb();
+
+  struct wfl_entry *next;
+  while ((next = __sync_val_compare_and_swap(&p->next, NULL, new_entry)))
+    p = next;
+}
+
+void *wfl_remove(struct wfl *list)
+{
+  for (struct wfl_entry *p = list->head; p != NULL; p = p->next) {
+    if (p->data != NULL) {
+      void *data = atomic_swap_ptr(&p->data, 0);
+      if (data != NULL)
+        return data;
+    }
+  }
+  return NULL;
+}
+
+size_t wfl_remove_all(struct wfl *list, void *data)
+{
+  size_t n = 0;
+  for (struct wfl_entry *p = list->head; p != NULL; p = p->next) {
+    if (p->data == data)
+      n += __sync_bool_compare_and_swap(&p->data, data, NULL);
+  }
+  return n;
+}