[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 2/3] pthread: RW-Locks
Wie bei allen Atomic- und Concurrency-Geschichten drücke ich alle
Daumen, dass das so funktioniert.
Signed-off-by: Hanna Reitz <hanna.reitz@xxxxxxxxxxx>
---
src/modules/include/pthread.h | 30 +++++
src/modules/lib/posix/pthread/rwlock.c | 162 +++++++++++++++++++++++++
2 files changed, 192 insertions(+)
create mode 100644 src/modules/lib/posix/pthread/rwlock.c
diff --git a/src/modules/include/pthread.h b/src/modules/include/pthread.h
index 45c0acb0..517e01c0 100644
--- a/src/modules/include/pthread.h
+++ b/src/modules/include/pthread.h
@@ -33,10 +33,40 @@
#define PTHREAD_THREADS_MAX 8192
+typedef struct {
+ uint32_t count;
+
+ // Nur wichtig, um beim Entsperren zu wissen, ob es ein unlock_w
+ // oder unlock_r ist (pthread trennt das leider nicht)
+ tid_t writer;
+} pthread_rwlock_t;
+
+#define PTHREAD_RWLOCK_INITIALIZER \
+ ((pthread_rwlock_t) { \
+ .count = 0, \
+ .writer = 0, \
+ })
+
+// Nicht unterstuetzt, aber brauchen wir fuer die Definition von
+// pthread_rwlock_init()
+typedef unsigned int pthread_rwlockattr_t;
+
+
int pthread_create(pthread_t *thread,
__attribute__((unused)) const pthread_attr_t *attr,
void *(*start_routine)(void *), void *arg);
pthread_t pthread_self(void);
+
+int pthread_rwlock_init(pthread_rwlock_t* restrict rwlock,
+ const pthread_rwlockattr_t* restrict attr);
+int pthread_rwlock_destroy(pthread_rwlock_t* rwlock);
+
+int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock);
+int pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock);
+int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock);
+int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock);
+int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);
+
#endif
diff --git a/src/modules/lib/posix/pthread/rwlock.c b/src/modules/lib/posix/pthread/rwlock.c
new file mode 100644
index 00000000..3b0185e6
--- /dev/null
+++ b/src/modules/lib/posix/pthread/rwlock.c
@@ -0,0 +1,162 @@
+/*
+ * Copyright (c) 2021 The tyndur Project. All rights reserved.
+ *
+ * This code is derived from software contributed to the tyndur Project
+ * by Hanna Reitz.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+ * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <errno.h>
+#include <pthread.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <syscall.h>
+#include <unistd.h>
+
+/*
+ * Das hier definierte RW-Lock besteht vor allem aus einem Zaehler
+ * (.counter), der fuer jeden Reader um eins inkrementiert wird.
+ * Es gibt eine Maximalzahl von Readern, die so hoch ist (16M), dass
+ * sie praktisch nie erreicht werden sollte.
+ *
+ * Diese Maximalzahl wird verwendet, um das Write-Lock zu
+ * implementieren: Wenn das Maximum erreicht ist, kann das Lock nicht
+ * genommen werden (trylock gibt einen Fehler zurueck, lock yieldet,
+ * bis es geht). Dementsprechend erhoeht jeder Writer den Zaehler um
+ * diese Maximalzahl, was dazu fuehrt, dass er das Lock erst nehmen
+ * kann, wenn es keine Reader mehr gibt.
+ *
+ * Leider ist es bei pthread so, dass es nur eine unlock-Funktion
+ * gibt, also muessen wir uns irgendwo merken, ob der aktuelle Thread
+ * ein Read- oder ein Write-Lock genommen hat. Das passiert mit
+ * .writer, worin nach dem Nehmen eines Write-Locks die aktuelle
+ * Thread-ID gespeichert wird. Die unlock-Funktion kann dann einfach
+ * prüfen, ob dort die eigene Thread-ID steht, und wenn ja, dann war
+ * es ein Write-Lock.
+ * (Funktioniert, weil es nur einen Writer geben kann, und wenn es
+ * keinen gibt, dann ist .writer 0. Die erste Thread-ID bei tyndur
+ * ist 1.)
+ */
+
+#define MAX_READERS (1u << 24)
+
+int pthread_rwlock_init(pthread_rwlock_t* restrict rwlock,
+ const pthread_rwlockattr_t* restrict attr)
+{
+ (void)attr;
+
+ *rwlock = PTHREAD_RWLOCK_INITIALIZER;
+ return 0;
+}
+
+int pthread_rwlock_destroy(pthread_rwlock_t* rwlock)
+{
+ (void)rwlock;
+ return 0;
+}
+
+static void do_unlock(pthread_rwlock_t* rwl)
+{
+ bool write = rwl->writer == gettid();
+
+ if (write) {
+ rwl->writer = 0;
+ }
+
+ // Release: Ende eines kritischen Abschnitts, keine Operationen
+ // duerfen nachher passieren; ausserdem muss diese
+ // Aenderung fuer andere Threads sichtbar gemacht werden
+ __atomic_fetch_sub(&rwl->count, write ? MAX_READERS : 1, __ATOMIC_RELEASE);
+}
+
+static bool do_trylock(pthread_rwlock_t* rwl, bool write)
+{
+ uint32_t inc = write ? MAX_READERS : 1;
+
+ // Acquire: Synchronisation mit do_unlock()
+ // Das hier ist ein Abkuerzungspfad, damit wir rwl->count nicht so
+ // oft um MAX_READERS erhoehen.
+ if (write &&
+ __atomic_load_4(&rwl->count, __ATOMIC_ACQUIRE) + inc > MAX_READERS)
+ {
+ return false;
+ }
+
+ // Acquire: Beginn eines kritischen Abschnitts, keine Operationen
+ // duerfen vorher passieren; ausserdem Synchronisation
+ // mit do_unlock()
+ // Release: Aenderung fuer andere Threads sichtbar machen
+ if (__atomic_add_fetch(&rwl->count, inc, __ATOMIC_ACQ_REL) > MAX_READERS) {
+ __atomic_fetch_sub(&rwl->count, inc, __ATOMIC_RELEASE);
+ return false;
+ }
+
+ if (write) {
+ rwl->writer = gettid();
+ }
+
+ return true;
+}
+
+static void do_lock(pthread_rwlock_t* rwl, bool write)
+{
+ while (!do_trylock(rwl, write)) {
+ yield();
+ }
+}
+
+int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock)
+{
+ do_lock(rwlock, false);
+ return 0;
+}
+
+int pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock)
+{
+ if (do_trylock(rwlock, false)) {
+ return 0;
+ } else {
+ return EBUSY;
+ }
+}
+
+int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock)
+{
+ do_lock(rwlock, true);
+ return 0;
+}
+
+int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock)
+{
+ if (do_trylock(rwlock, true)) {
+ return 0;
+ } else {
+ return EBUSY;
+ }
+}
+
+int pthread_rwlock_unlock(pthread_rwlock_t *rwlock)
+{
+ do_unlock(rwlock);
+ return 0;
+}
--
2.31.0