RCU lock implementation

Introduce an RCU lock implementation as an alternative locking mechanism
to openssl.  The api is documented in the ossl_rcu.pod
file

Read side implementaiton is comparable to that of RWLOCKS:
ossl_rcu_read_lock(lock);
<
critical section in which data can be accessed via
ossl_derefrence
>
ossl_rcu_read_unlock(lock);

Write side implementation is:
ossl_rcu_write_lock(lock);
<
critical section in which data can be updated via
ossl_assign_pointer
and stale data can optionally be scheduled for removal
via ossl_rcu_call
>
ossl_rcu_write_unlock(lock);
...
ossl_synchronize_rcu(lock);

ossl_rcu_call fixup

Reviewed-by: Hugo Landau <hlandau@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/22729)

1 files changed, 258 insertions, 0 deletions

diff --git a/doc/internal/man3/ossl_rcu_lock_new.pod b/doc/internal/man3/ossl_rcu_lock_new.pod
new file mode 100644
index 0000000000..e92bf29165
--- /dev/null
+++ b/doc/internal/man3/ossl_rcu_lock_new.pod
@@ -0,0 +1,258 @@
+=pod
+
+=head1 NAME
+
+ossl_rcu_lock_new,
+ossl_rcu_lock_free, ossl_rcu_read_lock,
+ossl_rcu_read_unlock, ossl_rcu_write_lock,
+ossl_rcu_write_unlock, ossl_synchronize_rcu,
+ossl_rcu_call, ossl_rcu_deref,
+ossl_rcu_assign_ptr, ossl_rcu_uptr_deref,
+ossl_rcu_assign_uptr
+- perform read-copy-update locking
+
+=head1 SYNOPSIS
+
+ CRYPTO_RCU_LOCK *ossl_rcu_lock_new(int num_writers);
+ void ossl_rcu_read_lock(CRYPTO_RCU_LOCK *lock);
+ void ossl_rcu_write_lock(CRYPTO_RCU_LOCK *lock);
+ void ossl_rcu_write_unlock(CRYPTO_RCU_LOCK *lock);
+ void ossl_rcu_read_unlock(CRYPTO_RCU_LOCK *lock);
+ void ossl_synchronize_rcu(CRYPTO_RCU_LOCK *lock);
+ void ossl_rcu_call(CRYPTO_RCU_LOCK *lock, rcu_cb_fn cb, void *data);
+ void *ossl_rcu_deref(void **p);
+ void ossl_rcu_uptr_deref(void **p);
+ void ossl_rcu_assign_ptr(void **p, void **v);
+ void ossl_rcu_assign_uptr(void **p, void **v);
+ void ossl_rcu_lock_free(CRYPTO_RCU_LOCK *lock);
+
+=head1 DESCRIPTION
+
+OpenSSL can be safely used in multi-threaded applications provided that
+support for the underlying OS threading API is built-in. Currently, OpenSSL
+supports the pthread and Windows APIs. OpenSSL can also be built without
+any multi-threading support, for example on platforms that don't provide
+any threading support or that provide a threading API that is not yet
+supported by OpenSSL.
+
+In addition to more traditional Read/Write locks, OpenSSL provides
+Read-Copy-Update (RCU) locks, which allow for always nonblocking read paths.
+
+The following multi-threading functions are provided:
+
+=over 2
+
+=item *
+
+ossl_rcu_assign_uptr() assigns the value pointed to by v to the
+location pointed to by p.  This function should typically not be used, rely
+instead on the ossl_rcu_assign_ptr() macro.
+
+=item *
+
+ossl_rcu_uptr_deref() returns the value stored at the
+location pointed to by p. This function should typically not be used, rely
+instead on the ossl_rcu_deref() macro.
+
+=item *
+
+ossl_rcu_assign_ptr() assigns the value pointed to by v to
+location pointed to by p.
+
+=item *
+
+ossl_rcu_lock_new() allocates a new RCU lock.  The I<num_writers> param
+indicates the number of write side threads which may execute
+ossl_synchronize_rcu() in parallel.  The value must be at least 1, but may be
+larger to obtain increased write side throughput at the cost of additional
+internal memory usage.  A value of 1 is generally recommended.
+
+=item *
+
+ossl_rcu_read_lock() acquires a read side hold on data protected by
+the lock.
+
+=item *
+
+ossl_rcu_read_unlock() releases a read side hold on data protected by
+the lock.
+
+=item *
+
+ossl_rcu_write_lock() acquires a write side hold on data protected by
+the lock.  Note only one writer per lock is permitted, as with read/write locks.
+
+=item *
+
+ossl_rcu_write_unlock() releases a write side hold on data protected
+by the lock.
+
+=item *
+
+ossl_synchronize_rcu() blocks the calling thread until all read side
+holds on the lock have been released, guaranteeing that any old data updated by
+the write side thread is safe to free.
+
+=item *
+
+ossl_rcu_call() enqueues a callback function to the lock, to be called
+when the next synchronization completes.  Note: It is not guaranteed that the
+thread which enqueued the callback will be the thread which executes the
+callback
+
+=item *
+
+ossl_rcu_deref(p) atomically reads a pointer under an RCU locks
+protection
+
+=item *
+
+ossl_rcu_assign_ptr(p,v) atomically writes to a pointer under an
+RCU locks protection
+
+=item *
+
+ossl_rcu_lock_free() frees an allocated RCU lock
+
+=back
+
+=head1 RETURN VALUES
+
+ossl_rcu_lock_new() returns a pointer to a newly created RCU lock structure.
+
+ossl_rcu_deref() and ossl_rcu_uptr_deref() return the value pointed
+to by the passed in value v.
+
+All other functions return no value.
+
+=head1 EXAMPLES
+
+You can find out if OpenSSL was configured with thread support:
+
+ #include <openssl/opensslconf.h>
+ #if defined(OPENSSL_THREADS)
+     /* thread support enabled */
+ #else
+     /* no thread support */
+ #endif
+
+This example safely initializes and uses a lock.
+
+ #include "internal/rcu.h"
+
+ struct foo {
+    int aval;
+    char *name;
+ };
+
+ static CRYPTO_ONCE once = CRYPTO_ONCE_STATIC_INIT;
+ static CRYPTO_RCU_LOCK *lock;
+ static struct foo *fooptr = NULL;
+
+ static void myinit(void)
+ {
+     lock = ossl_rcu_lock_new(1);
+ }
+
+ static int initlock(void)
+ {
+     if (!RUN_ONCE(&once, myinit) || lock == NULL)
+         return 0;
+     return 1;
+ }
+
+ static void writer_thread()
+ {
+    struct foo *newfoo;
+    struct foo *oldfoo;
+
+    initlock();
+
+    /*
+     * update steps in an rcu model
+     */
+
+    /*
+     * 1) create a new shared object
+     */
+    newfoo = OPENSSL_zalloc(sizeof(struct foo));
+
+    /*
+     * acquire the write side lock
+     */
+    ossl_rcu_write_lock(lock);
+
+    /*
+     * 2) read the old pointer
+     */
+    oldfoo = ossl_rcu_deref(&fooptr);
+
+    /*
+     * 3) Copy the old pointer to the new object, and
+     *    make any needed adjustments
+     */
+    memcpy(newfoo, oldfoo, sizeof(struct foo));
+    newfoo->aval++;
+
+    /*
+     * 4) Update the shared pointer to the new value
+     */
+    ossl_rcu_assign_ptr(&fooptr, &newfoo);
+
+    /*
+     * 5) Release the write side lock
+     */
+    ossl_rcu_write_unlock(lock);
+
+    /*
+     * 6) wait for any read side holds on the old data
+     *    to be released
+     */
+    ossl_synchronize_rcu(lock);
+
+    /*
+     * 7) free the old pointer, now that there are no
+     *    further readers
+     */
+    OPENSSL_free(oldfoo);
+ }
+
+ static void reader_thread()
+ {
+    struct foo *myfoo = NULL;
+    int a;
+    /*
+     * 1) Acquire a read side hold on the shared data
+     */
+    ossl_rcu_read_lock(lock);
+
+    /*
+     * 2) Access the shared data pointer
+     */
+    myfoo = ossl_rcu_deref(&fooptr);
+
+    /*
+     * 3) Read the data from the pointer
+     */
+    a = myfoo->aval;
+
+    /*
+     * 4) Indicate our hold on the shared data is complete
+     */
+    ossl_rcu_read_unlock(lock);
+ }
+
+=head1 SEE ALSO
+
+L<crypto(7)>, L<openssl-threads(7)>.
+
+=head1 COPYRIGHT
+
+Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use
+this file except in compliance with the License.  You can obtain a copy
+in the file LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut