From 8a1d2cf1422e35257c160ac5bb12dd3ee481c433 Mon Sep 17 00:00:00 2001 From: David 'Digit' Turner Date: Tue, 11 May 2010 16:39:22 -0700 Subject: Add pthread_rwlock_t implementation to the C library (DO NOT MERGE) Change-Id: I756d8c26afc37cd7b71117ddbaa02a2cb40fdecb --- libc/Android.mk | 3 + libc/bionic/pthread-rwlocks.c | 347 ++++++++++++++++++++++++++++++++++++++++++ libc/docs/CHANGES.TXT | 7 +- libc/include/pthread.h | 35 +++++ 4 files changed, 391 insertions(+), 1 deletion(-) create mode 100644 libc/bionic/pthread-rwlocks.c diff --git a/libc/Android.mk b/libc/Android.mk index 590afbe..0271f10 100644 --- a/libc/Android.mk +++ b/libc/Android.mk @@ -322,6 +322,7 @@ libc_common_src_files += \ # up any thumb code. libc_common_src_files += \ bionic/pthread.c.arm \ + bionic/pthread-rwlocks.c.arm \ bionic/pthread-timers.c.arm \ bionic/ptrace.c.arm @@ -356,6 +357,7 @@ libc_common_src_files += \ arch-x86/string/strncmp_wrapper.S \ arch-x86/string/strlen.S \ bionic/pthread.c \ + bionic/pthread-rwlocks.c \ bionic/pthread-timers.c \ bionic/ptrace.c @@ -393,6 +395,7 @@ libc_common_src_files += \ string/strlen.c \ bionic/eabi.c \ bionic/pthread.c \ + bionic/pthread-rwlocks.c \ bionic/pthread-timers.c \ bionic/ptrace.c \ unistd/socketcalls.c diff --git a/libc/bionic/pthread-rwlocks.c b/libc/bionic/pthread-rwlocks.c new file mode 100644 index 0000000..ca3e95c --- /dev/null +++ b/libc/bionic/pthread-rwlocks.c @@ -0,0 +1,347 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * 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 OWNER 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 "pthread_internal.h" +#include + +/* Technical note: + * + * Possible states of a read/write lock: + * + * - no readers and no writer (unlocked) + * - one or more readers sharing the lock at the same time (read-locked) + * - one writer holding the lock (write-lock) + * + * Additionally: + * - trying to get the write-lock while there are any readers blocks + * - trying to get the read-lock while there is a writer blocks + * - a single thread can acquire the lock multiple times in the same mode + * + * - Posix states that behaviour is undefined it a thread tries to acquire + * the lock in two distinct modes (e.g. write after read, or read after write). + * + * - This implementation tries to avoid writer starvation by making the readers + * block as soon as there is a waiting writer on the lock. However, it cannot + * completely eliminate it: each time the lock is unlocked, all waiting threads + * are woken and battle for it, which one gets it depends on the kernel scheduler + * and is semi-random. + * + */ + +#define __likely(cond) __builtin_expect(!!(cond), 1) +#define __unlikely(cond) __builtin_expect(!!(cond), 0) + +#define RWLOCKATTR_DEFAULT 0 +#define RWLOCKATTR_SHARED_MASK 0x0010 + +extern pthread_internal_t* __get_thread(void); + +/* Return a global kernel ID for the current thread */ +static int __get_thread_id(void) +{ + return __get_thread()->kernel_id; +} + +int pthread_rwlockattr_init(pthread_rwlockattr_t *attr) +{ + if (!attr) + return EINVAL; + + *attr = PTHREAD_PROCESS_PRIVATE; + return 0; +} + +int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr) +{ + if (!attr) + return EINVAL; + + *attr = -1; + return 0; +} + +int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared) +{ + if (!attr) + return EINVAL; + + switch (pshared) { + case PTHREAD_PROCESS_PRIVATE: + case PTHREAD_PROCESS_SHARED: + *attr = pshared; + return 0; + default: + return EINVAL; + } +} + +int pthread_rwlockattr_getpshared(pthread_rwlockattr_t *attr, int *pshared) +{ + if (!attr || !pshared) + return EINVAL; + + *pshared = *attr; + return 0; +} + +int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr) +{ + pthread_mutexattr_t* lock_attr = NULL; + pthread_condattr_t* cond_attr = NULL; + pthread_mutexattr_t lock_attr0; + pthread_condattr_t cond_attr0; + int ret; + + if (rwlock == NULL) + return EINVAL; + + if (attr && *attr == PTHREAD_PROCESS_SHARED) { + lock_attr = &lock_attr0; + pthread_mutexattr_init(lock_attr); + pthread_mutexattr_setpshared(lock_attr, PTHREAD_PROCESS_SHARED); + + cond_attr = &cond_attr0; + pthread_condattr_init(cond_attr); + pthread_condattr_setpshared(cond_attr, PTHREAD_PROCESS_SHARED); + } + + ret = pthread_mutex_init(&rwlock->lock, lock_attr); + if (ret != 0) + return ret; + + ret = pthread_cond_init(&rwlock->cond, cond_attr); + if (ret != 0) { + pthread_mutex_destroy(&rwlock->lock); + return ret; + } + + rwlock->numLocks = 0; + rwlock->pendingReaders = 0; + rwlock->pendingWriters = 0; + rwlock->writerThreadId = 0; + + return 0; +} + +int pthread_rwlock_destroy(pthread_rwlock_t *rwlock) +{ + int ret; + + if (rwlock == NULL) + return EINVAL; + + if (rwlock->numLocks > 0) + return EBUSY; + + pthread_cond_destroy(&rwlock->cond); + pthread_mutex_destroy(&rwlock->lock); + return 0; +} + +/* Returns TRUE iff we can acquire a read lock. */ +static __inline__ int read_precondition(pthread_rwlock_t *rwlock, int thread_id) +{ + /* We can't have the lock if any writer is waiting for it (writer bias). + * This tries to avoid starvation when there are multiple readers racing. + */ + if (rwlock->pendingWriters > 0) + return 0; + + /* We can have the lock if there is no writer, or if we write-own it */ + /* The second test avoids a self-dead lock in case of buggy code. */ + if (rwlock->writerThreadId == 0 || rwlock->writerThreadId == thread_id) + return 1; + + /* Otherwise, we can't have it */ + return 0; +} + +/* returns TRUE iff we can acquire a write lock. */ +static __inline__ int write_precondition(pthread_rwlock_t *rwlock, int thread_id) +{ + /* We can get the lock if nobody has it */ + if (rwlock->numLocks == 0) + return 1; + + /* Or if we already own it */ + if (rwlock->writerThreadId == thread_id) + return 1; + + /* Otherwise, not */ + return 0; +} + +/* This function is used to waken any waiting thread contending + * for the lock. One of them should be able to grab it after + * that. + */ +static void _pthread_rwlock_pulse(pthread_rwlock_t *rwlock) +{ + if (rwlock->pendingReaders > 0 || rwlock->pendingWriters > 0) + pthread_cond_broadcast(&rwlock->cond); +} + + +int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock) +{ + return pthread_rwlock_timedrdlock(rwlock, NULL); +} + +int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock) +{ + int ret = 0; + + if (rwlock == NULL) + return EINVAL; + + pthread_mutex_lock(&rwlock->lock); + if (__unlikely(!read_precondition(rwlock, __get_thread_id()))) + ret = EBUSY; + else + rwlock->numLocks ++; + pthread_mutex_unlock(&rwlock->lock); + + return ret; +} + +int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout) +{ + int thread_id, ret = 0; + + if (rwlock == NULL) + return EINVAL; + + pthread_mutex_lock(&rwlock->lock); + thread_id = __get_thread_id(); + if (__unlikely(!read_precondition(rwlock, thread_id))) { + rwlock->pendingReaders += 1; + do { + ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout); + } while (ret == 0 && !read_precondition(rwlock, thread_id)); + rwlock->pendingReaders -= 1; + if (ret != 0) + goto EXIT; + } + rwlock->numLocks ++; +EXIT: + pthread_mutex_unlock(&rwlock->lock); + return ret; +} + + +int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock) +{ + return pthread_rwlock_timedwrlock(rwlock, NULL); +} + +int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock) +{ + int thread_id, ret = 0; + + if (rwlock == NULL) + return EINVAL; + + pthread_mutex_lock(&rwlock->lock); + thread_id = __get_thread_id(); + if (__unlikely(!write_precondition(rwlock, thread_id))) { + ret = EBUSY; + } else { + rwlock->numLocks ++; + rwlock->writerThreadId = thread_id; + } + pthread_mutex_unlock(&rwlock->lock); + return ret; +} + +int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout) +{ + int thread_id, ret = 0; + + if (rwlock == NULL) + return EINVAL; + + pthread_mutex_lock(&rwlock->lock); + thread_id = __get_thread_id(); + if (__unlikely(!write_precondition(rwlock, thread_id))) { + /* If we can't read yet, wait until the rwlock is unlocked + * and try again. Increment pendingReaders to get the + * cond broadcast when that happens. + */ + rwlock->pendingWriters += 1; + do { + ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout); + } while (ret == 0 && !write_precondition(rwlock, thread_id)); + rwlock->pendingWriters -= 1; + if (ret != 0) + goto EXIT; + } + rwlock->numLocks ++; + rwlock->writerThreadId = thread_id; +EXIT: + pthread_mutex_unlock(&rwlock->lock); + return ret; +} + + +int pthread_rwlock_unlock(pthread_rwlock_t *rwlock) +{ + int ret = 0; + + if (rwlock == NULL) + return EINVAL; + + pthread_mutex_lock(&rwlock->lock); + + /* The lock must be held */ + if (rwlock->numLocks == 0) { + ret = EPERM; + goto EXIT; + } + + /* If it has only readers, writerThreadId is 0 */ + if (rwlock->writerThreadId == 0) { + if (--rwlock->numLocks == 0) + _pthread_rwlock_pulse(rwlock); + } + /* Otherwise, it has only a single writer, which + * must be ourselves. + */ + else { + if (rwlock->writerThreadId != __get_thread_id()) { + ret = EPERM; + goto EXIT; + } + if (--rwlock->numLocks == 0) { + rwlock->writerThreadId = 0; + _pthread_rwlock_pulse(rwlock); + } + } +EXIT: + pthread_mutex_unlock(&rwlock->lock); + return ret; +} diff --git a/libc/docs/CHANGES.TXT b/libc/docs/CHANGES.TXT index 9080685..a66e737 100644 --- a/libc/docs/CHANGES.TXT +++ b/libc/docs/CHANGES.TXT @@ -1,7 +1,12 @@ Bionic ChangeLog: ----------------- -Differences between current and Android 2.1: +Differences between current and Android 2.2: + +- : Add reader/writer locks implementation. + +------------------------------------------------------------------------------- +Differences between Android 2.2. and Android 2.1: - Add support for SH-4 CPU architecture ! diff --git a/libc/include/pthread.h b/libc/include/pthread.h index eb2d169..33039b9 100644 --- a/libc/include/pthread.h +++ b/libc/include/pthread.h @@ -219,6 +219,41 @@ int pthread_cond_timeout_np(pthread_cond_t *cond, */ int pthread_mutex_lock_timeout_np(pthread_mutex_t *mutex, unsigned msecs); +/* read-write lock support */ + +typedef int pthread_rwlockattr_t; + +typedef struct { + pthread_mutex_t lock; + pthread_cond_t cond; + int numLocks; + int writerThreadId; + int pendingReaders; + int pendingWriters; + void* reserved[4]; /* for future extensibility */ +} pthread_rwlock_t; + +#define PTHREAD_RWLOCK_INITIALIZER { PTHREAD_MUTEX_INITIALIZER, 0, NULL, 0, 0 } + +int pthread_rwlockattr_init(pthread_rwlockattr_t *attr); +int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr); +int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared); +int pthread_rwlockattr_getpshared(pthread_rwlockattr_t *attr, int *pshared); + +int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *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_timedrdlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout); + +int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock); +int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock); +int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout); + +int pthread_rwlock_unlock(pthread_rwlock_t *rwlock); + + int pthread_key_create(pthread_key_t *key, void (*destructor_function)(void *)); int pthread_key_delete (pthread_key_t); int pthread_setspecific(pthread_key_t key, const void *value); -- cgit v1.1