You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mynewt.apache.org by GitBox <gi...@apache.org> on 2018/07/02 20:07:50 UTC
[GitHub] ccollins476ad closed pull request #1223: util/rwlock: Readers–writer lock
ccollins476ad closed pull request #1223: util/rwlock: Readers–writer lock
URL: https://github.com/apache/mynewt-core/pull/1223
This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:
As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):
diff --git a/util/rwlock/include/rwlock/rwlock.h b/util/rwlock/include/rwlock/rwlock.h
new file mode 100644
index 0000000000..221a0356e8
--- /dev/null
+++ b/util/rwlock/include/rwlock/rwlock.h
@@ -0,0 +1,105 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#ifndef H_RWLOCK_
+#define H_RWLOCK_
+
+#include "os/mynewt.h"
+
+/**
+ * @brief Readers–writer lock - lock for multiple readers, single writer.
+ *
+ * This lock is write-preferring. That is:
+ * o If there is no active writer and no pending writers, read-acquisitions
+ * do not block.
+ * o If there is an active writer or a pending writer, read-acquisitions
+ * block.
+ * o When the last active reader or the active writer releases the lock, it
+ * is acquired by a pending writer if there is one. If there are no
+ * pending writers, the lock is acquired by all pending readers.
+ *
+ * All struct fields should be considered private.
+ */
+struct rwlock {
+ /** Protects access to rwlock's internal state. */
+ struct os_mutex mtx;
+
+ /** Blocks and wakes up pending readers. */
+ struct os_sem rsem;
+
+ /** Blocks and wakes up pending writers. */
+ struct os_sem wsem;
+
+ /** The number of active readers. */
+ uint8_t num_readers;
+
+ /** Whether there is an active writer. */
+ bool active_writer;
+
+ /** The number of blocked readers. */
+ uint8_t pending_readers;
+
+ /** The number of blocked writers. */
+ uint8_t pending_writers;
+
+ /**
+ * The number of ownership transfers currently in progress. No new
+ * acquisitions are allowed until all handoffs are complete.
+ */
+ uint8_t handoffs;
+};
+
+/**
+ * @brief Acquires the lock for use by a reader.
+ *
+ * @param lock The lock to acquire.
+ */
+void rwlock_acquire_read(struct rwlock *lock);
+
+/**
+ * Releases the lock from a reader.
+ *
+ * @param lock The lock to release.
+ */
+void rwlock_release_read(struct rwlock *lock);
+
+/**
+ * @brief Acquires the lock for use by a writer.
+ *
+ * @param lock The lock to acquire.
+ */
+void rwlock_acquire_write(struct rwlock *lock);
+
+/**
+ * Releases the lock from a writer.
+ *
+ * @param lock The lock to release.
+ */
+void rwlock_release_write(struct rwlock *lock);
+
+/**
+ * Initializes a readers-writer lock.
+ *
+ * @param lock The lock to initialize.
+ *
+ * @return 0 on success; nonzero on failure.
+ */
+int rwlock_init(struct rwlock *lock);
+
+#endif
diff --git a/util/rwlock/pkg.yml b/util/rwlock/pkg.yml
new file mode 100644
index 0000000000..1f5817a610
--- /dev/null
+++ b/util/rwlock/pkg.yml
@@ -0,0 +1,25 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+pkg.name: util/rwlock
+pkg.description: "Reader-writer lock"
+pkg.author: "Apache Mynewt <de...@mynewt.apache.org>"
+pkg.homepage: "http://mynewt.apache.org/"
+pkg.keywords:
+
+pkg.deps:
+ - kernel/os
diff --git a/util/rwlock/src/rwlock.c b/util/rwlock/src/rwlock.c
new file mode 100644
index 0000000000..88de440975
--- /dev/null
+++ b/util/rwlock/src/rwlock.c
@@ -0,0 +1,213 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#include "os/mynewt.h"
+#include "rwlock/rwlock.h"
+
+#if MYNEWT_VAL(RWLOCK_DEBUG)
+#define RWLOCK_DBG_ASSERT(expr) (assert(expr))
+#else
+#define RWLOCK_DBG_ASSERT(expr)
+#endif
+
+/**
+ * Unblocks the next pending user. The caller must lock the mutex prior to
+ * calling this.
+ */
+static void
+rwlock_unblock(struct rwlock *lock)
+{
+ RWLOCK_DBG_ASSERT(lock->mtx.mu_owner == g_current_task);
+ RWLOCK_DBG_ASSERT(lock->handoffs == 0);
+
+ /* Give priority to pending writers. */
+ if (lock->pending_writers > 0) {
+ /* Indicate that ownership is being transfered to a single writer. */
+ lock->handoffs = 1;
+
+ os_sem_release(&lock->wsem);
+ lock->pending_writers--;
+ } else {
+ /* Indicate that ownership is being transfered to a collection of
+ * readers.
+ */
+ lock->handoffs = lock->pending_readers;
+
+ while (lock->pending_readers > 0) {
+ os_sem_release(&lock->rsem);
+ lock->pending_readers--;
+ }
+ }
+}
+
+static void
+rwlock_complete_handoff(struct rwlock *lock)
+{
+ RWLOCK_DBG_ASSERT(lock->mtx.mu_owner == g_current_task);
+ RWLOCK_DBG_ASSERT(lock->handoffs > 0);
+ lock->handoffs--;
+}
+
+/**
+ * Indicates whether a prospective reader must wait for the lock to become
+ * available.
+ */
+static bool
+rwlock_read_must_block(const struct rwlock *lock)
+{
+ RWLOCK_DBG_ASSERT(lock->mtx.mu_owner == g_current_task);
+
+ return lock->active_writer ||
+ lock->pending_writers > 0 ||
+ lock->handoffs > 0;
+}
+
+/**
+ * Indicates whether a prospective writer must wait for the lock to become
+ * available.
+ */
+static bool
+rwlock_write_must_block(const struct rwlock *lock)
+{
+ RWLOCK_DBG_ASSERT(lock->mtx.mu_owner == g_current_task);
+
+ return lock->active_writer ||
+ lock->num_readers > 0 ||
+ lock->handoffs > 0;
+}
+
+void
+rwlock_acquire_read(struct rwlock *lock)
+{
+ bool acquired;
+
+ os_mutex_pend(&lock->mtx, OS_TIMEOUT_NEVER);
+
+ if (rwlock_read_must_block(lock)) {
+ lock->pending_readers++;
+ acquired = false;
+ } else {
+ lock->num_readers++;
+ acquired = true;
+ }
+
+ os_mutex_release(&lock->mtx);
+
+ if (acquired) {
+ /* No contention; lock acquired. */
+ return;
+ }
+
+ /* Wait for the lock to become available. */
+ os_sem_pend(&lock->rsem, OS_TIMEOUT_NEVER);
+
+ /* Record reader ownership. */
+ os_mutex_pend(&lock->mtx, OS_TIMEOUT_NEVER);
+ lock->num_readers++;
+ rwlock_complete_handoff(lock);
+ os_mutex_release(&lock->mtx);
+}
+
+void
+rwlock_release_read(struct rwlock *lock)
+{
+ os_mutex_pend(&lock->mtx, OS_TIMEOUT_NEVER);
+
+ RWLOCK_DBG_ASSERT(lock->num_readers > 0);
+ lock->num_readers--;
+
+ /* If this is the last active reader, unblock a pending writer if there is
+ * one.
+ */
+ if (lock->num_readers == 0) {
+ rwlock_unblock(lock);
+ }
+
+ os_mutex_release(&lock->mtx);
+}
+
+void
+rwlock_acquire_write(struct rwlock *lock)
+{
+ bool acquired;
+
+ os_mutex_pend(&lock->mtx, OS_TIMEOUT_NEVER);
+
+ if (rwlock_write_must_block(lock)) {
+ lock->pending_writers++;
+ acquired = false;
+ } else {
+ lock->active_writer = true;
+ acquired = true;
+ }
+
+ os_mutex_release(&lock->mtx);
+
+ if (acquired) {
+ /* No contention; lock acquired. */
+ return;
+ }
+
+ /* Wait for the lock to become available. */
+ os_sem_pend(&lock->wsem, OS_TIMEOUT_NEVER);
+
+ /* Record writer ownership. */
+ os_mutex_pend(&lock->mtx, OS_TIMEOUT_NEVER);
+ lock->active_writer = true;
+ rwlock_complete_handoff(lock);
+ os_mutex_release(&lock->mtx);
+}
+
+void
+rwlock_release_write(struct rwlock *lock)
+{
+ os_mutex_pend(&lock->mtx, OS_TIMEOUT_NEVER);
+
+ RWLOCK_DBG_ASSERT(lock->active_writer);
+ lock->active_writer = false;
+
+ rwlock_unblock(lock);
+
+ os_mutex_release(&lock->mtx);
+}
+
+int
+rwlock_init(struct rwlock *lock)
+{
+ int rc;
+
+ *lock = (struct rwlock) { 0 };
+
+ rc = os_mutex_init(&lock->mtx);
+ if (rc != 0) {
+ return rc;
+ }
+
+ rc = os_sem_init(&lock->rsem, 0);
+ if (rc != 0) {
+ return rc;
+ }
+
+ rc = os_sem_init(&lock->wsem, 0);
+ if (rc != 0) {
+ return rc;
+ }
+
+ return 0;
+}
diff --git a/util/rwlock/syscfg.yml b/util/rwlock/syscfg.yml
new file mode 100644
index 0000000000..6c7765a984
--- /dev/null
+++ b/util/rwlock/syscfg.yml
@@ -0,0 +1,21 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+syscfg.defs:
+ RWLOCK_DEBUG:
+ description: 'Enable extra assertions in the rwlock code.'
+ value: 0
diff --git a/util/rwlock/test/pkg.yml b/util/rwlock/test/pkg.yml
new file mode 100644
index 0000000000..1431a33bbf
--- /dev/null
+++ b/util/rwlock/test/pkg.yml
@@ -0,0 +1,31 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+pkg.name: util/rwlock/test
+pkg.type: unittest
+pkg.description: "rwlock unit tests."
+pkg.author: "Apache Mynewt <de...@mynewt.apache.org>"
+pkg.homepage: "http://mynewt.apache.org/"
+pkg.keywords:
+
+pkg.deps:
+ - kernel/os
+ - test/testutil
+ - util/rwlock
+
+pkg.deps.SELFTEST:
+ - sys/console/stub
diff --git a/util/rwlock/test/src/rwlock_test.c b/util/rwlock/test/src/rwlock_test.c
new file mode 100644
index 0000000000..afbc09fc07
--- /dev/null
+++ b/util/rwlock/test/src/rwlock_test.c
@@ -0,0 +1,35 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#include "rwlock_test.h"
+
+TEST_SUITE(rwlock_test_suite_basic)
+{
+ rwlock_test_case_basic();
+}
+
+#if MYNEWT_VAL(SELFTEST)
+int
+main(int argc, char **argv)
+{
+ rwlock_test_suite_basic();
+
+ return tu_any_failed;
+}
+#endif
diff --git a/util/rwlock/test/src/rwlock_test.h b/util/rwlock/test/src/rwlock_test.h
new file mode 100644
index 0000000000..c38191c1b3
--- /dev/null
+++ b/util/rwlock/test/src/rwlock_test.h
@@ -0,0 +1,10 @@
+#ifndef H_RWLOCK_TEST_H
+#define H_RWLOCK_TEST_H
+
+#include "os/mynewt.h"
+#include "testutil/testutil.h"
+
+TEST_SUITE_DECL(rwlock_test_suite_basic);
+TEST_CASE_DECL(rwlock_test_case_basic);
+
+#endif
diff --git a/util/rwlock/test/src/testcases/rwlock_test_case_basic.c b/util/rwlock/test/src/testcases/rwlock_test_case_basic.c
new file mode 100644
index 0000000000..26917b7856
--- /dev/null
+++ b/util/rwlock/test/src/testcases/rwlock_test_case_basic.c
@@ -0,0 +1,147 @@
+#include "rwlock/rwlock.h"
+#include "rwlock_test.h"
+
+#define RTCB_READ_TASK_PRIO 10
+#define RTCB_WRITE_TASK_PRIO 11
+
+#define RTCB_STACK_SIZE 1024
+
+static void rtcb_evcb_read(struct os_event *ev);
+static void rtcb_evcb_write(struct os_event *ev);
+
+static int rtcb_num_readers;
+static int rtcb_num_writers;
+
+static struct os_eventq rtcb_evq_read;
+static struct os_eventq rtcb_evq_write;
+
+static struct os_task rtcb_task_read;
+static struct os_task rtcb_task_write;
+
+static os_stack_t rtcb_stack_read[RTCB_STACK_SIZE];
+static os_stack_t rtcb_stack_write[RTCB_STACK_SIZE];
+
+static struct rwlock rtcb_rwlock;
+
+static struct os_event rtcb_ev_read = {
+ .ev_cb = rtcb_evcb_read,
+};
+
+static struct os_event rtcb_ev_write = {
+ .ev_cb = rtcb_evcb_write,
+};
+
+static void
+rtcb_evcb_read(struct os_event *ev)
+{
+ rwlock_acquire_read(&rtcb_rwlock);
+ rtcb_num_readers++;
+}
+
+static void
+rtcb_evcb_write(struct os_event *ev)
+{
+ rwlock_acquire_write(&rtcb_rwlock);
+ rtcb_num_writers++;
+}
+
+static void
+rtcb_enqueue_read(void)
+{
+ os_eventq_put(&rtcb_evq_read, &rtcb_ev_read);
+}
+
+static void
+rtcb_enqueue_write(void)
+{
+ os_eventq_put(&rtcb_evq_write, &rtcb_ev_write);
+}
+
+static void
+rtcb_read_task_handler(void *arg)
+{
+ while (1) {
+ os_eventq_run(&rtcb_evq_read);
+ }
+}
+
+static void
+rtcb_write_task_handler(void *arg)
+{
+ while (1) {
+ os_eventq_run(&rtcb_evq_write);
+ }
+}
+
+TEST_CASE_TASK(rwlock_test_case_basic)
+{
+ int rc;
+
+ os_eventq_init(&rtcb_evq_read);
+ os_eventq_init(&rtcb_evq_write);
+
+ rc = os_task_init(&rtcb_task_read, "read", rtcb_read_task_handler, NULL,
+ RTCB_READ_TASK_PRIO, OS_WAIT_FOREVER, rtcb_stack_read,
+ RTCB_STACK_SIZE);
+ TEST_ASSERT_FATAL(rc == 0);
+
+ rc = os_task_init(&rtcb_task_write, "write", rtcb_write_task_handler, NULL,
+ RTCB_WRITE_TASK_PRIO, OS_WAIT_FOREVER, rtcb_stack_write,
+ RTCB_STACK_SIZE);
+ TEST_ASSERT_FATAL(rc == 0);
+
+ rwlock_init(&rtcb_rwlock);
+
+ /* Enqueue one read; ensure it acquires the lock. */
+ rtcb_enqueue_read();
+ TEST_ASSERT_FATAL(rtcb_num_readers == 1);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 0);
+
+ /* Enqueue one write; ensure it does *not* acquire the lock. */
+ rtcb_enqueue_write();
+ TEST_ASSERT_FATAL(rtcb_num_readers == 1);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 0);
+
+ /* Enqueue two more readers; ensure both do *not* acquire the lock. */
+ rtcb_enqueue_read();
+ rtcb_enqueue_read();
+ TEST_ASSERT_FATAL(rtcb_num_readers == 1);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 0);
+
+ /* Release reader; ensure lock given to writer. */
+ rwlock_release_read(&rtcb_rwlock);
+ TEST_ASSERT_FATAL(rtcb_num_readers == 1);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 1);
+
+ /* Release writer; ensure lock given to both pending readers. */
+ rwlock_release_write(&rtcb_rwlock);
+ TEST_ASSERT_FATAL(rtcb_num_readers == 3);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 1);
+
+ /*** Reset state. */
+ rwlock_init(&rtcb_rwlock);
+ rtcb_num_readers = 0;
+ rtcb_num_writers = 0;
+
+ /* Enqueue two writers; ensure lock given to one writer. */
+ rtcb_enqueue_write();
+ rtcb_enqueue_write();
+ TEST_ASSERT_FATAL(rtcb_num_readers == 0);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 1);
+
+ /* Enqueue two readers; ensure lock not given. */
+ rtcb_enqueue_read();
+ rtcb_enqueue_read();
+ TEST_ASSERT_FATAL(rtcb_num_readers == 0);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 1);
+
+ /* Release writer; ensure lock given to second writer. */
+ rwlock_release_write(&rtcb_rwlock);
+ TEST_ASSERT_FATAL(rtcb_num_readers == 0);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 2);
+
+ /* Release writer; ensure lock given to both readers. */
+ rwlock_release_write(&rtcb_rwlock);
+ TEST_ASSERT_FATAL(rtcb_num_readers == 2);
+ TEST_ASSERT_FATAL(rtcb_num_writers == 2);
+}
diff --git a/util/rwlock/test/syscfg.yml b/util/rwlock/test/syscfg.yml
new file mode 100644
index 0000000000..9df43254a3
--- /dev/null
+++ b/util/rwlock/test/syscfg.yml
@@ -0,0 +1,19 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+syscfg.vals:
+ RWLOCK_DEBUG: 1
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services