Adding upstream version 9.1.upstream/9.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 339 insertions, 0 deletions

diff --git a/lib/atomlist.c b/lib/atomlist.c
new file mode 100644
index 0000000..5c361d3
--- /dev/null
+++ b/lib/atomlist.c
@@ -0,0 +1,339 @@
+// SPDX-License-Identifier: ISC
+/*
+ * Copyright (c) 2016-2018  David Lamparter, for NetDEF, Inc.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "atomlist.h"
+
+void atomlist_add_head(struct atomlist_head *h, struct atomlist_item *item)
+{
+	atomptr_t prevval;
+	atomptr_t i = atomptr_i(item);
+
+	atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed);
+
+	/* updating ->last is possible here, but makes the code considerably
+	 * more complicated... let's not.
+	 */
+	prevval = ATOMPTR_NULL;
+	item->next = ATOMPTR_NULL;
+
+	/* head-insert atomically
+	 * release barrier: item + item->next writes must be completed
+	 */
+	while (!atomic_compare_exchange_weak_explicit(&h->first, &prevval, i,
+				memory_order_release, memory_order_relaxed))
+		atomic_store_explicit(&item->next, prevval,
+				memory_order_relaxed);
+}
+
+void atomlist_add_tail(struct atomlist_head *h, struct atomlist_item *item)
+{
+	atomptr_t prevval = ATOMPTR_NULL;
+	atomptr_t i = atomptr_i(item);
+	atomptr_t hint;
+	struct atomlist_item *prevptr;
+	_Atomic atomptr_t *prev;
+
+	item->next = ATOMPTR_NULL;
+
+	atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed);
+
+	/* place new item into ->last
+	 * release: item writes completed;  acquire: DD barrier on hint
+	 */
+	hint = atomic_exchange_explicit(&h->last, i, memory_order_acq_rel);
+
+	while (1) {
+		if (atomptr_p(hint) == NULL)
+			prev = &h->first;
+		else
+			prev = &atomlist_itemp(hint)->next;
+
+		do {
+			prevval = atomic_load_explicit(prev,
+					memory_order_consume);
+			prevptr = atomlist_itemp(prevval);
+			if (prevptr == NULL)
+				break;
+
+			prev = &prevptr->next;
+		} while (prevptr);
+
+		/* last item is being deleted - start over */
+		if (atomptr_l(prevval)) {
+			hint = ATOMPTR_NULL;
+			continue;
+		}
+
+		/* no barrier - item->next is NULL and was so in xchg above */
+		if (!atomic_compare_exchange_strong_explicit(prev, &prevval, i,
+					memory_order_consume,
+					memory_order_consume)) {
+			hint = prevval;
+			continue;
+		}
+		break;
+	}
+}
+
+static void atomlist_del_core(struct atomlist_head *h,
+			      struct atomlist_item *item,
+			      _Atomic atomptr_t *hint,
+			      atomptr_t next)
+{
+	_Atomic atomptr_t *prev = hint ? hint : &h->first, *upd;
+	atomptr_t prevval, updval;
+	struct atomlist_item *prevptr;
+
+	/* drop us off "last" if needed.  no r/w to barrier. */
+	prevval = atomptr_i(item);
+	atomic_compare_exchange_strong_explicit(&h->last, &prevval,
+			ATOMPTR_NULL,
+			memory_order_relaxed, memory_order_relaxed);
+
+	atomic_fetch_sub_explicit(&h->count, 1, memory_order_relaxed);
+
+	/* the following code should be identical (except sort<>list) to
+	 * atomsort_del_hint()
+	 */
+	while (1) {
+		upd = NULL;
+		updval = ATOMPTR_LOCK;
+
+		do {
+			prevval = atomic_load_explicit(prev,
+					memory_order_consume);
+
+			/* track the beginning of a chain of deleted items
+			 * this is necessary to make this lock-free; we can
+			 * complete deletions started by other threads.
+			 */
+			if (!atomptr_l(prevval)) {
+				updval = prevval;
+				upd = prev;
+			}
+
+			prevptr = atomlist_itemp(prevval);
+			if (prevptr == item)
+				break;
+
+			prev = &prevptr->next;
+		} while (prevptr);
+
+		if (prevptr != item)
+			/* another thread completed our deletion */
+			return;
+
+		if (!upd || atomptr_l(updval)) {
+			/* failed to find non-deleted predecessor...
+			 * have to try again
+			 */
+			prev = &h->first;
+			continue;
+		}
+
+		if (!atomic_compare_exchange_strong_explicit(upd, &updval,
+					next, memory_order_consume,
+					memory_order_consume)) {
+			/* prev doesn't point to item anymore, something
+			 * was inserted.  continue at same position forward.
+			 */
+			continue;
+		}
+		break;
+	}
+}
+
+void atomlist_del_hint(struct atomlist_head *h, struct atomlist_item *item,
+		_Atomic atomptr_t *hint)
+{
+	atomptr_t next;
+
+	/* mark ourselves in-delete - full barrier */
+	next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
+				memory_order_acquire);
+	assert(!atomptr_l(next));	/* delete race on same item */
+
+	atomlist_del_core(h, item, hint, next);
+}
+
+struct atomlist_item *atomlist_pop(struct atomlist_head *h)
+{
+	struct atomlist_item *item;
+	atomptr_t next;
+
+	/* grab head of the list - and remember it in replval for the
+	 * actual delete below.  No matter what, the head of the list is
+	 * where we start deleting because either it's our item, or it's
+	 * some delete-marked items and then our item.
+	 */
+	next = atomic_load_explicit(&h->first, memory_order_consume);
+
+	do {
+		item = atomlist_itemp(next);
+		if (!item)
+			return NULL;
+
+		/* try to mark deletion */
+		next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
+					memory_order_acquire);
+
+	} while (atomptr_l(next));
+	/* if loop is taken: delete race on same item (another pop or del)
+	 * => proceed to next item
+	 * if loop exited here: we have our item selected and marked
+	 */
+	atomlist_del_core(h, item, &h->first, next);
+	return item;
+}
+
+struct atomsort_item *atomsort_add(struct atomsort_head *h,
+		struct atomsort_item *item, int (*cmpfn)(
+			const struct atomsort_item *,
+			const struct atomsort_item *))
+{
+	_Atomic atomptr_t *prev;
+	atomptr_t prevval;
+	atomptr_t i = atomptr_i(item);
+	struct atomsort_item *previtem;
+	int cmpval;
+
+	do {
+		prev = &h->first;
+
+		do {
+			prevval = atomic_load_explicit(prev,
+					memory_order_acquire);
+			previtem = atomptr_p(prevval);
+
+			if (!previtem || (cmpval = cmpfn(previtem, item)) > 0)
+				break;
+			if (cmpval == 0)
+				return previtem;
+
+			prev = &previtem->next;
+		} while (1);
+
+		if (atomptr_l(prevval))
+			continue;
+
+		item->next = prevval;
+		if (atomic_compare_exchange_strong_explicit(prev, &prevval, i,
+				memory_order_release, memory_order_relaxed))
+			break;
+	} while (1);
+
+	atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed);
+	return NULL;
+}
+
+static void atomsort_del_core(struct atomsort_head *h,
+		struct atomsort_item *item, _Atomic atomptr_t *hint,
+		atomptr_t next)
+{
+	_Atomic atomptr_t *prev = hint ? hint : &h->first, *upd;
+	atomptr_t prevval, updval;
+	struct atomsort_item *prevptr;
+
+	atomic_fetch_sub_explicit(&h->count, 1, memory_order_relaxed);
+
+	/* the following code should be identical (except sort<>list) to
+	 * atomlist_del_core()
+	 */
+	while (1) {
+		upd = NULL;
+		updval = ATOMPTR_LOCK;
+
+		do {
+			prevval = atomic_load_explicit(prev,
+					memory_order_consume);
+
+			/* track the beginning of a chain of deleted items
+			 * this is necessary to make this lock-free; we can
+			 * complete deletions started by other threads.
+			 */
+			if (!atomptr_l(prevval)) {
+				updval = prevval;
+				upd = prev;
+			}
+
+			prevptr = atomsort_itemp(prevval);
+			if (prevptr == item)
+				break;
+
+			prev = &prevptr->next;
+		} while (prevptr);
+
+		if (prevptr != item)
+			/* another thread completed our deletion */
+			return;
+
+		if (!upd || atomptr_l(updval)) {
+			/* failed to find non-deleted predecessor...
+			 * have to try again
+			 */
+			prev = &h->first;
+			continue;
+		}
+
+		if (!atomic_compare_exchange_strong_explicit(upd, &updval,
+					next, memory_order_relaxed,
+					memory_order_relaxed)) {
+			/* prev doesn't point to item anymore, something
+			 * was inserted.  continue at same position forward.
+			 */
+			continue;
+		}
+		break;
+	}
+}
+
+void atomsort_del_hint(struct atomsort_head *h, struct atomsort_item *item,
+		_Atomic atomptr_t *hint)
+{
+	atomptr_t next;
+
+	/* mark ourselves in-delete - full barrier */
+	next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
+				memory_order_seq_cst);
+	assert(!atomptr_l(next));	/* delete race on same item */
+
+	atomsort_del_core(h, item, hint, next);
+}
+
+struct atomsort_item *atomsort_pop(struct atomsort_head *h)
+{
+	struct atomsort_item *item;
+	atomptr_t next;
+
+	/* grab head of the list - and remember it in replval for the
+	 * actual delete below.  No matter what, the head of the list is
+	 * where we start deleting because either it's our item, or it's
+	 * some delete-marked items and then our item.
+	 */
+	next = atomic_load_explicit(&h->first, memory_order_consume);
+
+	do {
+		item = atomsort_itemp(next);
+		if (!item)
+			return NULL;
+
+		/* try to mark deletion */
+		next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
+					memory_order_acquire);
+
+	} while (atomptr_l(next));
+	/* if loop is taken: delete race on same item (another pop or del)
+	 * => proceed to next item
+	 * if loop exited here: we have our item selected and marked
+	 */
+	atomsort_del_core(h, item, &h->first, next);
+	return item;
+}