Menu
▾
▴
[cadcdev-svn-commits] SF.net SVN: cadcdev: [583] kos
|
From: <ljs...@us...> - 2008-05-19 15:23:47
|
Revision: 583
http://cadcdev.svn.sourceforge.net/cadcdev/?rev=583&view=rev
Author: ljsebald
Date: 2008-05-19 08:23:23 -0700 (Mon, 19 May 2008)
Log Message:
-----------
Adding in a new synchronization primitive: reader/writer semaphores, along with an example program for them.
Modified Paths:
--------------
kos/examples/dreamcast/basic/threading/Makefile
kos/kernel/thread/Makefile
Added Paths:
-----------
kos/examples/dreamcast/basic/threading/rwsem/
kos/examples/dreamcast/basic/threading/rwsem/Makefile
kos/examples/dreamcast/basic/threading/rwsem/rwsem_test.c
kos/include/kos/rwsem.h
kos/kernel/thread/rwsem.c
Modified: kos/examples/dreamcast/basic/threading/Makefile
===================================================================
--- kos/examples/dreamcast/basic/threading/Makefile 2008-05-19 14:49:36 UTC (rev 582)
+++ kos/examples/dreamcast/basic/threading/Makefile 2008-05-19 15:23:23 UTC (rev 583)
@@ -7,11 +7,14 @@
all:
$(KOS_MAKE) -C general
+ $(KOS_MAKE) -C rwsem
clean:
$(KOS_MAKE) -C general clean
+ $(KOS_MAKE) -C rwsem clean
dist:
$(KOS_MAKE) -C general dist
+ $(KOS_MAKE) -C rwsem dist
Added: kos/examples/dreamcast/basic/threading/rwsem/Makefile
===================================================================
--- kos/examples/dreamcast/basic/threading/rwsem/Makefile (rev 0)
+++ kos/examples/dreamcast/basic/threading/rwsem/Makefile 2008-05-19 15:23:23 UTC (rev 583)
@@ -0,0 +1,29 @@
+# KallistiOS ##version##
+#
+# basic/threading/rwsem/Makefile
+# Copyright (C) 2008 Lawrence Sebald
+#
+
+all: rm-elf rwsem_test.elf
+
+include $(KOS_BASE)/Makefile.rules
+
+OBJS = rwsem_test.o
+
+clean: rm-elf
+ -rm -f $(OBJS)
+
+rm-elf:
+ -rm -f rwsem_test.elf
+
+rwsem_test.elf: $(OBJS)
+ $(KOS_CC) $(KOS_CFLAGS) $(KOS_LDFLAGS) -o rwsem_test.elf $(KOS_START) \
+ $(OBJS) $(DATAOBJS) $(OBJEXTRA) $(KOS_LIBS)
+
+
+run: rwsem_test.elf
+ $(KOS_LOADER) rwsem_test.elf
+
+dist:
+ rm -f $(OBJS)
+ $(KOS_STRIP) rwsem_test.elf
\ No newline at end of file
Added: kos/examples/dreamcast/basic/threading/rwsem/rwsem_test.c
===================================================================
--- kos/examples/dreamcast/basic/threading/rwsem/rwsem_test.c (rev 0)
+++ kos/examples/dreamcast/basic/threading/rwsem/rwsem_test.c 2008-05-19 15:23:23 UTC (rev 583)
@@ -0,0 +1,146 @@
+/* KallistiOS ##version##
+
+ rwsem_test.c
+ Copyright (C) 2008 Lawrence Sebald
+
+*/
+
+/* This program is a test of the reader/writer semaphores added in KOS 1.3.0.
+ Basically, what a reader/writer semaphore does is it allows unlimited readers
+ to occupy their critical sections, while guaranteeing exclusive access to
+ writers. This is a concept that I picked up from my undergraduate operating
+ systems class that I figured would probably be useful for KOS. */
+
+#include <stdio.h>
+
+#include <kos/thread.h>
+#include <kos/rwsem.h>
+
+#include <arch/arch.h>
+#include <dc/maple.h>
+#include <dc/maple/controller.h>
+
+#define UNUSED __attribute__((unused))
+
+rw_semaphore_t *s = NULL;
+uint32 number = 0;
+
+void writer0(void *param UNUSED) {
+ int i;
+
+ for(i = 0; i < 20; ++i) {
+ if(rwsem_write_lock(s)) {
+ printf("Writer 0 could not obtain write lock!\n");
+ return;
+ }
+
+ printf("Writer 0 obtained write lock\n");
+ number += 8;
+ rwsem_write_unlock(s);
+
+ thd_sleep(10);
+ }
+
+ printf("Writer 0 done\n");
+}
+
+void writer1(void *param UNUSED) {
+ int i;
+
+ for(i = 0; i < 17; ++i) {
+ if(rwsem_write_lock(s)) {
+ printf("Writer 1 could not obtain write lock!\n");
+ return;
+ }
+
+ printf("Writer 1 obtained write lock\n");
+ number *= 3;
+ rwsem_write_unlock(s);
+
+ thd_sleep(5);
+ }
+
+ printf("Writer 1 done\n");
+}
+
+void reader0(void *param UNUSED) {
+ int i;
+
+ for(i = 0; i < 12; ++i) {
+ if(rwsem_read_lock(s)) {
+ printf("Reader 0 could not obtain read lock!\n");
+ return;
+ }
+
+ printf("Reader 0 obtained read lock\n");
+ printf("Number: %lu\n", number);
+ rwsem_read_unlock(s);
+
+ thd_sleep(20);
+ }
+
+ printf("Reader 0 done\n");
+}
+
+void reader1(void *param UNUSED) {
+ int i;
+
+ for(i = 0; i < 23; ++i) {
+ if(rwsem_read_lock(s)) {
+ printf("Reader 1 could not obtain read lock!\n");
+ return;
+ }
+
+ printf("Reader 1 obtained read lock\n");
+ printf("Number * 2: %lu\n", number * 2);
+ rwsem_read_unlock(s);
+
+ thd_sleep(16);
+ }
+
+ printf("Reader 1 done\n");
+}
+
+KOS_INIT_FLAGS(INIT_DEFAULT);
+int main(int argc, char *argv[]) {
+ kthread_t *w0, *w1, *r0, *r1;
+
+ /* Exit if the user presse all buttons at once. */
+ cont_btn_callback(0, CONT_START | CONT_A | CONT_B | CONT_X | CONT_Y,
+ arch_exit);
+
+ printf("KallistiOS Reader/Writer Semaphore test program\n");
+
+ /* Create the reader/writer semaphore that will be used. */
+ s = rwsem_create();
+
+ if(!s) {
+ printf("Could not create RW semaphore, bailing out!\n");
+ arch_exit();
+ }
+
+ printf("About to create threads\n");
+ w0 = thd_create(writer0, NULL);
+ w1 = thd_create(writer1, NULL);
+ r0 = thd_create(reader0, NULL);
+ r1 = thd_create(reader1, NULL);
+
+ printf("About to sleep\n");
+ thd_wait(w0);
+ thd_wait(w1);
+ thd_wait(r0);
+ thd_wait(r1);
+
+ if(rwsem_read_lock(s)) {
+ printf("Could not obtain final read lock!\n");
+ arch_exit();
+ }
+
+ printf("Final number: %lu\n", number);
+
+ rwsem_read_unlock(s);
+ rwsem_destroy(s);
+
+ printf("Reader/Writer semaphore tests completed successfully!\n");
+ return 0;
+}
Added: kos/include/kos/rwsem.h
===================================================================
--- kos/include/kos/rwsem.h (rev 0)
+++ kos/include/kos/rwsem.h 2008-05-19 15:23:23 UTC (rev 583)
@@ -0,0 +1,86 @@
+/* KallistiOS ##version##
+
+ include/kos/rwsem.h
+ Copyright (C) 2008 Lawrence Sebald
+
+*/
+
+/* This file defines a concept that might be familiar to anyone who's ever
+ hacked around on the Linux kernel a bit: reader/writer semaphores. Basically,
+ reader/writer semaphores allow an unlimitted readers to occupy the critical
+ section at any given time. Since readers, by definition, do not change any
+ data other than their own local variables this should in theory be safe.
+ Writers on the other hand require exclusive access to the critical section.
+ Writers only may proceed into the critical section if the write lock is not
+ held on the semaphore and if there are no readers currently in the critical
+ section. Also, no reader will be allowed into the critical section if the
+ write lock is held. */
+
+#ifndef __KOS_RWSEM_H
+#define __KOS_RWSEM_H
+
+#include <sys/cdefs.h>
+__BEGIN_DECLS
+
+#include <sys/queue.h>
+
+/* Reader/writer semaphore structure */
+typedef struct rw_semaphore {
+ /* List entry for the global list of reader/writer semaphores */
+ LIST_ENTRY(rw_semaphore) list;
+
+ /* How many readers currently hold the semaphore lock? */
+ int read_count;
+
+ /* Does a writer currently hold the lock? */
+ int write_lock;
+} rw_semaphore_t;
+
+LIST_HEAD(rwsemlist, rw_semaphore);
+
+/* Allocate a new reader/writer semaphore. Returns NULL on failure.
+ ENOMEM - Out of memory */
+rw_semaphore_t *rwsem_create();
+
+/* Destroy a reader/writer semaphore */
+void rwsem_destroy(rw_semaphore_t *s);
+
+/* Lock a reader/writer semaphore for reading. Returns -1 on error.
+ EPERM - called inside an interrupt
+ EINTR - was interrupted */
+int rwsem_read_lock(rw_semaphore_t *s);
+
+/* Lock a reader/writer semaphore for writing. Returns -1 on error.
+ EPERM - called inside an interrupt
+ EINTR - was interrupted */
+int rwsem_write_lock(rw_semaphore_t *s);
+
+/* Unlock a reader/writer semaphore from a read lock. Returns -1 on error. */
+int rwsem_read_unlock(rw_semaphore_t *s);
+
+/* Unlock a reader/writer semaphore from a write lock. Returns -1 on error. */
+int rwsem_write_unlock(rw_semaphore_t *s);
+
+/* Attempt to lock a reader/writer semaphore for reading. If the call to
+ rwsem_read_lock() would normally block, return -1 for error.
+ EWOULDBLOCK - would block */
+int rwsem_read_trylock(rw_semaphore_t *s);
+
+/* Attempt to lock a reader/writer semaphore for writing. If the call to
+ rwsem_write_lock() would normally block, return -1 for error.
+ EWOULDBLOCK - would block */
+int rwsem_write_trylock(rw_semaphore_t *s);
+
+/* Return the reader/writer semaphore reader count */
+int rwsem_read_count(rw_semaphore_t *s);
+
+/* Return the reader/writer semaphore write lock status */
+int rwsem_write_locked(rw_semaphore_t *s);
+
+/* Init / shutdown */
+int rwsem_init();
+void rwsem_shutdown();
+
+__END_DECLS
+
+#endif /* __KOS_RWSEM_H */
Modified: kos/kernel/thread/Makefile
===================================================================
--- kos/kernel/thread/Makefile 2008-05-19 14:49:36 UTC (rev 582)
+++ kos/kernel/thread/Makefile 2008-05-19 15:23:23 UTC (rev 583)
@@ -6,7 +6,7 @@
# $Id: Makefile,v 1.4 2003/02/14 08:25:07 bardtx Exp $
OBJS = sem.o cond.o mutex.o genwait.o
-OBJS += thread.o
+OBJS += thread.o rwsem.o
SUBDIRS =
include $(KOS_BASE)/Makefile.prefab
Added: kos/kernel/thread/rwsem.c
===================================================================
--- kos/kernel/thread/rwsem.c (rev 0)
+++ kos/kernel/thread/rwsem.c 2008-05-19 15:23:23 UTC (rev 583)
@@ -0,0 +1,224 @@
+/* KallistiOS ##version##
+
+ rwsem.c
+ Copyright (C) 2008 Lawrence Sebald
+*/
+
+/* Defines reader/writer semaphores */
+
+#include <malloc.h>
+#include <stdio.h>
+#include <assert.h>
+#include <errno.h>
+#include <sys/queue.h>
+
+#include <kos/rwsem.h>
+#include <kos/genwait.h>
+#include <arch/spinlock.h>
+
+/* Reader/writer semaphore list spinlock */
+static spinlock_t mutex;
+
+/* Global list of reader/writer semaphores */
+static struct rwsemlist rwsem_list;
+
+/* Allocate a new reader/writer semaphore */
+rw_semaphore_t *rwsem_create() {
+ rw_semaphore_t *s;
+
+ s = (rw_semaphore_t *)malloc(sizeof(rw_semaphore_t));
+ if(!s) {
+ errno = ENOMEM;
+ return NULL;
+ }
+
+ s->read_count = 0;
+ s->write_lock = 0;
+
+ spinlock_lock(&mutex);
+ LIST_INSERT_HEAD(&rwsem_list, s, list);
+ spinlock_unlock(&mutex);
+
+ return s;
+}
+
+/* Destroy a reader/writer semaphore */
+void rwsem_destroy(rw_semaphore_t *s) {
+ /* XXXX: Should really cause anyone waiting to get an error back on their
+ wait... hmm. */
+ spinlock_lock(&mutex);
+ LIST_REMOVE(s, list);
+ spinlock_unlock(&mutex);
+
+ free(s);
+}
+
+/* Lock a reader/writer semaphore for reading */
+int rwsem_read_lock(rw_semaphore_t *s) {
+ int old, rv = 0;
+
+ if(irq_inside_int()) {
+ dbglog(DBG_WARNING, "rwsem_read_lock: called inside interrupt\n");
+ errno = EPERM;
+ return -1;
+ }
+
+ old = irq_disable();
+
+ /* If the write lock is not held, let the thread proceed */
+ if(!s->write_lock) {
+ ++s->read_count;
+ }
+ else {
+ /* Block until the write lock is not held any more */
+ rv = genwait_wait(s, "rwsem_read_lock", 0, NULL);
+
+ if(rv < 0) {
+ assert(errno == EINTR);
+ rv = -1;
+ }
+ else {
+ ++s->read_count;
+ }
+ }
+
+ irq_restore(old);
+ return rv;
+}
+
+/* Lock a reader/writer semaphore for writing */
+int rwsem_write_lock(rw_semaphore_t *s) {
+ int old, rv = 0;
+
+ if(irq_inside_int()) {
+ dbglog(DBG_WARNING, "rwsem_write_lock: called inside interrupt\n");
+ errno = EPERM;
+ return -1;
+ }
+
+ old = irq_disable();
+
+ /* If the write lock is not held and there are no readers in their critical
+ sections, let the thread proceed. */
+ if(!s->write_lock && !s->read_count) {
+ s->write_lock = 1;
+ }
+ else {
+ /* Block until the write lock is not held and there are no readers
+ inside their critical sections */
+ rv = genwait_wait(&s->write_lock, "rwsem_write_lock", 0, NULL);
+
+ if(rv < 0) {
+ assert(errno == EINTR);
+ rv = -1;
+ }
+ else {
+ s->write_lock = 1;
+ }
+ }
+
+ irq_restore(old);
+ return rv;
+}
+
+/* Unlock a reader/writer semaphore from a read lock. */
+int rwsem_read_unlock(rw_semaphore_t *s) {
+ int old;
+
+ old = irq_disable();
+
+ --s->read_count;
+
+ /* If this was the last reader, attempt to wake any writers waiting. */
+ if(!s->read_count) {
+ genwait_wake_one(&s->write_lock);
+ }
+
+ irq_restore(old);
+
+ return 0;
+}
+
+/* Unlock a reader/writer semaphore from a write lock. */
+int rwsem_write_unlock(rw_semaphore_t *s) {
+ int old, woken;
+
+ old = irq_disable();
+
+ s->write_lock = 0;
+
+ /* Give writers priority, attempt to wake any writers first. */
+ woken = genwait_wake_cnt(&s->write_lock, 1);
+
+ if(!woken) {
+ /* No writers were waiting, wake up any readers. */
+ genwait_wake_all(s);
+ }
+
+ irq_restore(old);
+
+ return 0;
+}
+
+/* Attempt to lock a reader/writer semaphore for reading, but do not block. */
+int rwsem_read_trylock(rw_semaphore_t *s) {
+ int old, rv;
+
+ old = irq_disable();
+
+ /* Is the write lock held? */
+ if(s->write_lock) {
+ rv = -1;
+ errno = EWOULDBLOCK;
+ }
+ else {
+ rv = 0;
+ ++s->read_count;
+ }
+
+ irq_restore(old);
+ return rv;
+}
+
+/* Attempt to lock a reader/writer semaphore for writing, but do not block. */
+int rwsem_write_trylock(rw_semaphore_t *s) {
+ int old, rv;
+
+ old = irq_disable();
+
+ /* Are there any readers in their critical sections, or is the write lock
+ already held, if so we can't do anything about that now. */
+ if(s->read_count || s->write_lock) {
+ rv = -1;
+ errno = EWOULDBLOCK;
+ }
+ else {
+ rv = 0;
+ s->write_lock = 1;
+ }
+
+ irq_restore(old);
+ return rv;
+}
+
+/* Return the current reader count */
+int rwsem_read_count(rw_semaphore_t *s) {
+ return s->read_count;
+}
+
+/* Return the current status of the write lock */
+int rwsem_write_locked(rw_semaphore_t *s) {
+ return s->write_lock;
+}
+
+/* Initialize reader/writer semaphores */
+int rwsem_init() {
+ LIST_INIT(&rwsem_list);
+ spinlock_init(&mutex);
+ return 0;
+}
+
+/* Shut down reader/writer semaphores */
+void rwsem_shutdown() {
+ /* XXXX: Do something useful */
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
