Delivered-To: mlmmj-tyndur-devel
Received: from sv1.famkaufmann.info [176.9.73.67]
	by a9b8c5461646 with IMAP (fetchmail-6.3.26)
	for <mlmmj@localhost> (single-drop); Sat, 17 Apr 2021 22:09:56 +0000 (GMT)
Received: from localhost ([172.29.0.7])
	by sv1.famkaufmann.info with LMTP
	id mhw9L51ce2BiCgAALHnFKQ
	(envelope-from <hanna.reitz@mailbox.org>)
	for <mlmmj-tyndur-devel>; Sat, 17 Apr 2021 22:09:33 +0000
Delivered-To: tyndur-devel@tyndur.org
Received: from mout-p-103.mailbox.org (mout-p-103.mailbox.org [2001:67c:2050::465:103])
	by sv1.famkaufmann.info (OpenSMTPD) with ESMTPS id 56bb27f1 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO)
	for <tyndur-devel@tyndur.org>;
	Sat, 17 Apr 2021 22:09:33 +0000 (UTC)
Received: from smtp1.mailbox.org (smtp1.mailbox.org [IPv6:2001:67c:2050:105:465:1:1:0])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
	 key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256)
	(No client certificate requested)
	by mout-p-103.mailbox.org (Postfix) with ESMTPS id 4FN6gd16lQzQjv5
	for <tyndur-devel@tyndur.org>; Sun, 18 Apr 2021 00:09:33 +0200 (CEST)
Authentication-Results: spamfilter02.heinlein-hosting.de (amavisd-new);
	dkim=pass (2048-bit key) reason="pass (just generated, assumed good)"
	header.d=mailbox.org
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mailbox.org; s=mail20150812;
	t=1618697371;
	h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
	 to:to:cc:cc:mime-version:mime-version:content-type:content-type:
	 content-transfer-encoding:content-transfer-encoding:
	 in-reply-to:in-reply-to:references:references;
	bh=TA/Lm42dfA6yNJUjHmbXMxW0cTCUlLovG16F19cOfmw=;
	b=U47ZekvATWhvNm6rzREiIpxU3qxz4btKjblNx4M37KZu/k8/shBXdPRprynnBjcC0sAI95
	jLKHzKdT2sVirZ/6xJAxS6c2vSVMtvVeri8dMsLmGenXfQVNca+lw75Haqozweat5eYZGc
	AYA6heSG70Dd9fzvqp2bAXyyiR7kgTQ+Ps6ff+1/KcxqtJ3Bm8Kx4+IB+u7Dg5V+SfGysa
	ifls2ZyVlWcdJ4ZIP+KbfnHcgKbB/9OsTxcfnudKSmaXFPNN2MsJbv0dkuc9uFh6eS7tkp
	qG9Q5AwnxQ5AbP78lN0wROehJF2JMVMx9sTHqEblvtQE+D4+ek+b/cYc7UKE3A==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mailbox.org; h=
	content-transfer-encoding:content-type:content-type:mime-version
	:references:in-reply-to:message-id:date:date:subject:subject
	:from:from:received; s=mail20150812; t=1618697370; bh=h9Lm+DfqeA
	kX136+kuU9FSJBd5EJiPofcmUrOM9y7eA=; b=tfGb9DOj8qiZzfeL4aDEiI8Nwy
	tpkusp3vYATCEgRGJDilB16OM5y+DiYlM+tv1VVNCtVc1GDI09nCZZd8K760y+O9
	THar4+8eja4vT/6k4T/gwMU+oFMdcFGlqiXKFErp/JXblM/LhF6vLCLVvtM9t4W4
	/in1ogrPNHWO4Ou1uA6hEPWhWpDcfmTN18Uxi7KlsOb0ETtjtxKIe+9aUIIsnUZ7
	O6Q3LUEZ69AlQH7jJVr6/Vl8TzE2jFD+wFP+BXt7YiuwxcpONDanxGyKEfRlHEc/
	GvX4zBHiZYjXAFtp1KDWNBwtb0FXPdY3Jf6+Cr6VrNSiDVg8+ySP2cDTII6w==
X-Virus-Scanned: amavisd-new at heinlein-support.de
Received: from smtp1.mailbox.org ([80.241.60.240])
	by spamfilter02.heinlein-hosting.de (spamfilter02.heinlein-hosting.de [80.241.56.116]) (amavisd-new, port 10030)
	with ESMTP id k4rfR5uOaXH3; Sun, 18 Apr 2021 00:09:30 +0200 (CEST)
From: Hanna Reitz <hanna.reitz@mailbox.org>
To: tyndur-devel@tyndur.org
Cc: Hanna Reitz <hanna.reitz@mailbox.org>
Subject: [PATCH 2/3] pthread: RW-Locks
Date: Sun, 18 Apr 2021 00:09:01 +0200
Message-Id: <20210417220902.151893-3-hanna.reitz@mailbox.org>
In-Reply-To: <20210417220902.151893-1-hanna.reitz@mailbox.org>
References: <20210417220902.151893-1-hanna.reitz@mailbox.org>
Errors-To: toni@tyndur.org
Precedence: list
Reply-To: tyndur-Patches <tyndur-devel@tyndur.org>
List-Id: tyndur-Patches <tyndur-devel.tyndur.org>
List-Unsubscribe: <mailto:tyndur-devel+unsubscribe@tyndur.org>
List-Post: <mailto:tyndur-devel@tyndur.org>
List-Help: <mailto:tyndur-devel+help@tyndur.org>
List-Subscribe: <mailto:tyndur-devel+subscribe@tyndur.org>
List-Owner: <mailto:toni@tyndur.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-MBO-SPAM-Probability: 
X-Rspamd-Score: -8.85 / 15.00 / 15.00
X-Rspamd-Queue-Id: 451E4183B
X-Rspamd-UID: 3580ed

Wie bei allen Atomic- und Concurrency-Geschichten drücke ich alle
Daumen, dass das so funktioniert.

Signed-off-by: Hanna Reitz <hanna.reitz@mailbox.org>
---
 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

