From 5251061c60ffedf3533ca152280799997f645673 Mon Sep 17 00:00:00 2001 From: Adriaan de Groot Date: Thu, 10 Mar 2022 23:36:12 +0100 Subject: [PATCH 1/2] Add ripple.[hc] from Quick SASL - the ripple-list implementation might be useful in other ARPA2 projects, provide it in a common library. - add SPDX tags. - add include guards. - document that WITHOUT_ settings must be consistent between provider and consumer. --- include/arpa2/CMakeLists.txt | 35 ++--- include/arpa2/util/ripple.h | 160 +++++++++++++++++++++++ src/util/CMakeLists.txt | 8 +- src/util/ripple.c | 244 +++++++++++++++++++++++++++++++++++ 4 files changed, 427 insertions(+), 20 deletions(-) create mode 100644 include/arpa2/util/ripple.h create mode 100644 src/util/ripple.c diff --git a/include/arpa2/CMakeLists.txt b/include/arpa2/CMakeLists.txt index f745419..79fd152 100644 --- a/include/arpa2/CMakeLists.txt +++ b/include/arpa2/CMakeLists.txt @@ -5,27 +5,30 @@ install( FILES # Identity & Access things - identity.h group.h - rules.h rules_db.h - access.h access_comm.h access_document.h access_actor.h - # Operating System Stuff - com_err.h - except.h - socket.h + identity.h + group.h + rules.h + rules_db.h + access.h + access_comm.h + access_document.h + access_actor.h + # Operating System Stuff + com_err.h + except.h + socket.h # Crypto bits - entropy.h + entropy.h digest.h - #NOTYETUSEFUL# cipher.h - DESTINATION - include/arpa2/ + DESTINATION include/arpa2/ ) install( FILES - util/snoprintf.h + util/abspath.h + util/cmdparse.h util/hexdump.h - util/cmdparse.h - util/abspath.h - DESTINATION - include/arpa2/util + util/ripple.h + util/snoprintf.h + DESTINATION include/arpa2/util ) diff --git a/include/arpa2/util/ripple.h b/include/arpa2/util/ripple.h new file mode 100644 index 0000000..560561d --- /dev/null +++ b/include/arpa2/util/ripple.h @@ -0,0 +1,160 @@ +/* Ripple List Management, using spin locks. + * + * These are singly-linked lists with references in + * head and next fields. The references hold an extra + * spin lock which protects the reference and the data + * that is being referenced by it. + * + * The rippling routing locks elements in sequence, + * and can invoke an action when 1 or 2 are locked. + * This can be used to construct semantics such as: + * - at 1: Find and process a single element + * - at 1: Add a new element after a locked one + * - at 2: Remove an element from the list + * + * A newly added element needs no lock; a removed + * element will be unlocked after its removal. + * + * Actions may find NULL in their last reference. + * Action are called with a callback data pointer. + * Each routine returns whether the chase continues. + * + * When the symbol RIPPLE_WITHOUT_SPINLOCKS exists, + * the spinlocks are suppressed in resulting code. + * Note that consumers must use the **same** setting + * for RIPPLE_WITHOUT_SPINLOCKS as the library + * had when it was built, or internal structures + * will be mismatched. + * + */ + +/* + * SPDX-License-Identifier: BSD-2-Clause + * SPDX-FileCopyrightText: Copyright 2020 Rick van Rein + */ +#ifndef ARPA2_UTIL_RIPPLE_H +#define ARPA2_UTIL_RIPPLE_H + +#include + + + +#ifndef RIPPLE_WITHOUT_SPINLOCKS +# include +# define SPINLOCK_FIELD pthread_spinlock_t lock; +#else +# define SPINLOCK_FIELD +#endif + + +/* Ripple references are included as head and next + * fields in a linked list and its starting block. + */ +typedef struct ripple_ref { + struct ripple_ref *ref; + SPINLOCK_FIELD +} ripple_ref; + + +/* Callback functions are used to process spin-locked + * elements, which is at least the provided element + * and possibly the next one, depending on where the + * callback was supplied to ripple_iter(). + */ +typedef bool ripple_cb (ripple_ref *element, void *cbdata); + + +/* Tests are used when finding an element in a ripple list. + * The function should return true when the test succeeded. + * This will cast the victim to a larger structure, so it + * must not be used on the head; set skip1st to be safe. + */ +typedef bool ripple_test (ripple_ref *victim, void *cbdata); + + + +/* Initialise a list head as an empty list. + */ +void ripple_init (ripple_ref *head); + + +/* Cleanup a list head. + */ +void ripple_fini (ripple_ref *head); + + +/* Ripple iterator. Start at the head and pass through + * the list for as long as callbacks return true to + * continue. At the end, return the result from the last + * callback. The head must not be NULL. + * + * The callbacks are cb1 and cb2; the former is used with + * just one element locked and non-NULL, the latter is + * used when the next element is also locked and non-NULL. + * The cbdata is supplied to both types of callback and + * may serve as an accumulator. + * + * When skip1st is true, the head is not passed into the + * cb1 callback. This is necessary when cb1 interprets + * the structure of the head; cb2 is assumed to only be + * interested in the ripple_ref structure of the first. + * + * Callbacks may read and write only what they have been + * given with a lock. The ripple_ref are free to change + * within callbacks, but all prior or later elements must + * remain in the list, in their current positions, to + * allow other processes to ripple through. + */ +bool ripple_iter (ripple_ref *head, bool skip1st, ripple_cb *cb1, ripple_cb *cb2, void *cbdata); + + +/* Insert a new item at the start of a ripple list. + * The new item does not have to be initialised. + * + * This function does not fail. + */ +void ripple_insert (ripple_ref *head, ripple_ref *newbe); + + +/* Append a new item to the end of a ripple list. + * The new item does not have to be initialised. + * + * This function does not fail. + */ +void ripple_append (ripple_ref *head, ripple_ref *newbe); + + +/* Remove an element from a ripple list. + * + * Return whether the element was found and removed. + */ +bool ripple_remove (ripple_ref *head, ripple_ref *goner); + + +/* Find the first element in a ripple list that returns + * true from a test function. The test function may + * expand the ripple_ref to a larger structure to see + * the fields surrounding it if it can be sure that the + * list was filled with such structures. + */ +struct ripple_ref *ripple_find (ripple_ref *head, ripple_test *testfun, void *cbdata); + + +/* Map a function over a ripple list while a condition holds. + * The callback function returns true as its while condition. + * + * The return value is the last value returned. + */ +bool ripple_mapwhile (ripple_ref *head, ripple_test *maptestfun, void *cbdata); + + +/* Drop elements from a ripple list while a condition holds. + * The callback function removes an element and returns + * true as its while condition. Supply NULL as a function + * to drop every element from the list. + * + * The return value is the last value returned. + */ +bool ripple_dropwhile (ripple_ref *head, ripple_test *testfun, void *cbdata); + +#endif diff --git a/src/util/CMakeLists.txt b/src/util/CMakeLists.txt index 74f5b49..af93dde 100644 --- a/src/util/CMakeLists.txt +++ b/src/util/CMakeLists.txt @@ -7,10 +7,10 @@ library_pair( util OUTPUT_NAME common_util SOURCES + cmdparse.c + ripple.c + socket.c + snoprintf.c util.c - socket.c - snoprintf.c - cmdparse.c - #DROPPED# comerrinit.c EXPORT ARPA2Common ) diff --git a/src/util/ripple.c b/src/util/ripple.c new file mode 100644 index 0000000..5dab92c --- /dev/null +++ b/src/util/ripple.c @@ -0,0 +1,244 @@ +/* Ripple List Management, using spin locks. */ + +/* + * SPDX-License-Identifier: BSD-2-Clause + * SPDX-FileCopyrightText: Copyright 2020 Rick van Rein + */ + +#include + +#include +#include + + +#ifndef RIPPLE_WITHOUT_SPINLOCKS +# define SPINLOCK(rr) assert (0 == pthread_spin_lock (&(rr)->lock)) +# define SPUNLOCK(rr) assert (0 == pthread_spin_unlock (&(rr)->lock)) +# define SPIN_INIT(rr) assert (0 == pthread_spin_init (&(rr)->lock, PTHREAD_PROCESS_SHARED)) +# define SPIN_FINI(rr) assert (0 == pthread_spin_destroy (&(rr)->lock)) +#else +# define SPINLOCK(rr) +# define SPUNLOCK(rr) +# define SPIN_INIT(rr) +# define SPIN_FINI(rr) +#endif + + + +/* Initialise a list head as an empty list. + */ +void ripple_init (ripple_ref *head) { + assert (head != NULL); + head->ref = NULL; + SPIN_INIT (head); +} + + +/* Cleanup a list head. + */ +void ripple_fini (ripple_ref *head) { + assert (head != NULL); + SPIN_FINI (head); +} + + +/* Ripple iterator. Start at the head and pass through + * the list for as long as callbacks return true to + * continue. At the end, return the result from the last + * callback. The head must not be NULL. + * + * The callbacks are cb1 and cb2; the former is used with + * just one element locked and non-NULL, the latter is + * used when the next element is also locked and non-NULL. + * The cbdata is supplied to both types of callback and + * may serve as an accumulator. + * + * When skip1st is true, the head is not passed into the + * cb1 callback. This is necessary when cb1 interprets + * the structure of the head; cb2 is assumed to only be + * interested in the ripple_ref structure of the first. + * + * Callbacks may read and write only what they have been + * given with a lock. The ripple_ref are free to change + * within callbacks, but all prior or later elements must + * remain in the list, in their current positions, to + * allow other processes to ripple through. + */ +bool ripple_iter (ripple_ref *head, bool skip1st, ripple_cb *cb1, ripple_cb *cb2, void *cbdata) { + assert (head != NULL); + ripple_cb *cb1a = skip1st ? NULL : cb1; + // head is not NULL + SPINLOCK (head); + // head is locked and not NULL + ripple_ref *next = head->ref; + // head is locked and not NULL + // next may be NULL + bool cont = true; + while (cont) { + // head is locked and not NULL + // next may be NULL + if (cb1a != NULL) { + cont = cb1a (head, cbdata); + } else { + cb1a = cb1; + } + // head is locked and not NULL + // next may be NULL + if (next == NULL) { + break; + } else if (cont) { + // head is locked and not NULL + // next is not NULL + SPINLOCK (next); + // head is locked and not NULL + // next is locked and not NULL + if (cb2 != NULL) { + cont = cb2 (head, cbdata); + } + // head is locked and not NULL + // next is locked and not NULL + SPUNLOCK (head); + // next is locked and not NULL + head = next; + // head is locked and not NULL + next = head->ref; + // head is locked and not NULL + // next may be NULL + } + } + // head is locked and not NULL + SPUNLOCK (head); + // head is not NULL + return cont; +} + + +/* Insert a new item at the start of a ripple list. + * The new item does not have to be list-initialised. + * + * This function does not fail. + */ +void ripple_insert (ripple_ref *head, ripple_ref *newbe) { + SPIN_INIT (newbe); + SPINLOCK (head); + newbe->ref = head->ref; + head->ref = newbe; + SPUNLOCK (head); +} + + +/* Append a new item to the end of a ripple list. + * The new item does not have to be list-initialised. + * + * This function does not fail. + */ +static bool _ripple_cb1_append (ripple_ref *maybe_last, void *cbdata) { + log_debug ("_ripple_cb1_append() attempts %p", maybe_last); + if (maybe_last->ref != NULL) { + return true; + } + ripple_ref *newbe = cbdata; + SPIN_INIT (newbe); + newbe->ref = NULL; + maybe_last->ref = newbe; + log_debug ("_ripple_cb1_append() added %p after %p", newbe, maybe_last); + return false; +} +// +void ripple_append (ripple_ref *head, ripple_ref *newbe) { + ripple_iter (head, false, _ripple_cb1_append, NULL, newbe); +} + + +/* Remove an element from a ripple list. + * + * Return whether the element was found and removed. + */ +static bool _ripple_cb2_remove (ripple_ref *maybe_previous, void *cbdata) { + log_debug ("_ripple_cb2_remove() tries %p->ref for removal of %p (cbdata %p)", maybe_previous, maybe_previous->ref, cbdata); + if (maybe_previous->ref != cbdata) { + return true; + } + log_debug ("_ripple_cb2_remove() replaces ->ref %p with ->ref->ref %p", maybe_previous->ref, maybe_previous->ref->ref); + ripple_ref *goner = cbdata; + maybe_previous->ref = goner->ref; + goner->ref = NULL; + return false; +} +// +bool ripple_remove (ripple_ref *head, ripple_ref *goner) { + if (ripple_iter (head, false, NULL, _ripple_cb2_remove, goner)) { + // Not found, return failure + log_debug ("ripple_remove() did not find the instance"); + return false; + } + // Found and removed, now cleanup the spin lock + //BUGGY// SPIN_FINI (goner); + log_debug ("ripple_remove() got rid of the instance"); + return true; +} + + +/* Find the first element in a ripple list that returns + * true from a test function. The test function may + * expand the ripple_ref to a larger structure to see + * the fields surrounding it if it can be sure that the + * list was filled with such structures. + */ +typedef struct ripple_finder { + ripple_test *testfun; + ripple_ref *findings; + void *cbdata; +} ripple_finder; +// +static bool _ripple_cb1_findit (ripple_ref *maybe, void *cbdata) { + ripple_finder *finder = cbdata; + log_debug ("_ripple_cb1_findit() tests %p", maybe); + if (!finder->testfun (maybe, finder->cbdata)) { + return true; + } + log_debug ("_ripple_cb1_findit() returns %p", maybe); + finder->findings = maybe; + return false; +} +// +struct ripple_ref *ripple_find (ripple_ref *head, ripple_test *testfun, void *cbdata) { + struct ripple_finder finder; + finder.testfun = testfun; + finder.findings = NULL; + finder.cbdata = cbdata; + ripple_iter (head, true, _ripple_cb1_findit, NULL, &finder); + log_debug ("ripple_find() returns %p", finder.findings); + return finder.findings; +} + + +/* Map a function over a ripple list while a condition holds. + * The callback function returns true as its while condition. + * + * The return value is the last value returned. + */ +bool ripple_mapwhile (ripple_ref *head, ripple_test *maptestfun, void *cbdata) { + return ripple_iter (head, true, maptestfun, NULL, cbdata); +} + + +/* Drop elements from a ripple list while a condition holds. + * The callback function removes an element and returns + * true as its while condition. Supply NULL as a function + * to drop every element from the list. + * + * The return value is the last value returned. + */ +static bool _ripple_cb2_drop (ripple_ref *gonerptr, void *cbdata) { + ripple_ref *goner = gonerptr->ref; + gonerptr->ref = goner->ref; + goner->ref = NULL; + return true; +} +// +bool ripple_dropwhile (ripple_ref *head, ripple_test *testfun, void *cbdata) { + return ripple_iter (head, true, testfun, _ripple_cb2_drop, cbdata); + //TODO// did not SPIN_FINI(...dropped...) +} + -- GitLab From e0b59aaac128081c2ab107502cc0ffcf342552db Mon Sep 17 00:00:00 2001 From: Adriaan de Groot Date: Fri, 11 Mar 2022 00:05:17 +0100 Subject: [PATCH 2/2] Changes: prep for release with new file / header --- CHANGES | 5 +++++ CMakeLists.txt | 2 +- 2 files changed, 6 insertions(+), 1 deletion(-) diff --git a/CHANGES b/CHANGES index d109d7d..b177521 100644 --- a/CHANGES +++ b/CHANGES @@ -7,6 +7,11 @@ > Base libraries for ARPA2, including library for ACLs and a common > utility library; see also Quick-MEM for other low-level support libraries. +## v2.2.19 (2022-03-11) + +- Added ripple-lists (spinlock-based consistent singly-linked lists) + from Quick SASL. + ## v2.2.18 (2022-03-09) - Removed arpa2comerr_init() function from ARPA2::util diff --git a/CMakeLists.txt b/CMakeLists.txt index 241039d..d10a07a 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -7,7 +7,7 @@ # SPDX-FileCopyrightText: 2020 Rick van Rein cmake_minimum_required (VERSION 3.18 FATAL_ERROR) -project ("ARPA2 Common Libraries" VERSION 2.2.18 LANGUAGES C) +project ("ARPA2 Common Libraries" VERSION 2.2.19 LANGUAGES C) set (CMAKE_C_STANDARD 11) set (CMAKE_C_STANDARD_REQUIRED ON) -- GitLab