1/*
2 * Copyright (C) 2010 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *  * Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 *  * Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in
12 *    the documentation and/or other materials provided with the
13 *    distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29#include "pthread_internal.h"
30#include <errno.h>
31
32/* Technical note:
33 *
34 * Possible states of a read/write lock:
35 *
36 *  - no readers and no writer (unlocked)
37 *  - one or more readers sharing the lock at the same time (read-locked)
38 *  - one writer holding the lock (write-lock)
39 *
40 * Additionally:
41 *  - trying to get the write-lock while there are any readers blocks
42 *  - trying to get the read-lock while there is a writer blocks
43 *  - a single thread can acquire the lock multiple times in the same mode
44 *
45 *  - Posix states that behaviour is undefined it a thread tries to acquire
46 *    the lock in two distinct modes (e.g. write after read, or read after write).
47 *
48 *  - This implementation tries to avoid writer starvation by making the readers
49 *    block as soon as there is a waiting writer on the lock. However, it cannot
50 *    completely eliminate it: each time the lock is unlocked, all waiting threads
51 *    are woken and battle for it, which one gets it depends on the kernel scheduler
52 *    and is semi-random.
53 *
54 */
55
56#define  __likely(cond)    __builtin_expect(!!(cond), 1)
57#define  __unlikely(cond)  __builtin_expect(!!(cond), 0)
58
59#define  RWLOCKATTR_DEFAULT     0
60#define  RWLOCKATTR_SHARED_MASK 0x0010
61
62extern pthread_internal_t* __get_thread(void);
63
64/* Return a global kernel ID for the current thread */
65static int __get_thread_id(void)
66{
67    return __get_thread()->kernel_id;
68}
69
70int pthread_rwlockattr_init(pthread_rwlockattr_t *attr)
71{
72    if (!attr)
73        return EINVAL;
74
75    *attr = PTHREAD_PROCESS_PRIVATE;
76    return 0;
77}
78
79int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr)
80{
81    if (!attr)
82        return EINVAL;
83
84    *attr = -1;
85    return 0;
86}
87
88int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int  pshared)
89{
90    if (!attr)
91        return EINVAL;
92
93    switch (pshared) {
94    case PTHREAD_PROCESS_PRIVATE:
95    case PTHREAD_PROCESS_SHARED:
96        *attr = pshared;
97        return 0;
98    default:
99        return EINVAL;
100    }
101}
102
103int pthread_rwlockattr_getpshared(pthread_rwlockattr_t *attr, int *pshared)
104{
105    if (!attr || !pshared)
106        return EINVAL;
107
108    *pshared = *attr;
109    return 0;
110}
111
112int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr)
113{
114    pthread_mutexattr_t*  lock_attr = NULL;
115    pthread_condattr_t*   cond_attr = NULL;
116    pthread_mutexattr_t   lock_attr0;
117    pthread_condattr_t    cond_attr0;
118    int                   ret;
119
120    if (rwlock == NULL)
121        return EINVAL;
122
123    if (attr && *attr == PTHREAD_PROCESS_SHARED) {
124        lock_attr = &lock_attr0;
125        pthread_mutexattr_init(lock_attr);
126        pthread_mutexattr_setpshared(lock_attr, PTHREAD_PROCESS_SHARED);
127
128        cond_attr = &cond_attr0;
129        pthread_condattr_init(cond_attr);
130        pthread_condattr_setpshared(cond_attr, PTHREAD_PROCESS_SHARED);
131    }
132
133    ret = pthread_mutex_init(&rwlock->lock, lock_attr);
134    if (ret != 0)
135        return ret;
136
137    ret = pthread_cond_init(&rwlock->cond, cond_attr);
138    if (ret != 0) {
139        pthread_mutex_destroy(&rwlock->lock);
140        return ret;
141    }
142
143    rwlock->numLocks = 0;
144    rwlock->pendingReaders = 0;
145    rwlock->pendingWriters = 0;
146    rwlock->writerThreadId = 0;
147
148    return 0;
149}
150
151int pthread_rwlock_destroy(pthread_rwlock_t *rwlock)
152{
153    int  ret;
154
155    if (rwlock == NULL)
156        return EINVAL;
157
158    if (rwlock->numLocks > 0)
159        return EBUSY;
160
161    pthread_cond_destroy(&rwlock->cond);
162    pthread_mutex_destroy(&rwlock->lock);
163    return 0;
164}
165
166/* Returns TRUE iff we can acquire a read lock. */
167static __inline__ int read_precondition(pthread_rwlock_t *rwlock, int  thread_id)
168{
169    /* We can't have the lock if any writer is waiting for it (writer bias).
170     * This tries to avoid starvation when there are multiple readers racing.
171     */
172    if (rwlock->pendingWriters > 0)
173        return 0;
174
175    /* We can have the lock if there is no writer, or if we write-own it */
176    /* The second test avoids a self-dead lock in case of buggy code. */
177    if (rwlock->writerThreadId == 0 || rwlock->writerThreadId == thread_id)
178        return 1;
179
180    /* Otherwise, we can't have it */
181    return 0;
182}
183
184/* returns TRUE iff we can acquire a write lock. */
185static __inline__ int write_precondition(pthread_rwlock_t *rwlock, int  thread_id)
186{
187    /* We can get the lock if nobody has it */
188    if (rwlock->numLocks == 0)
189        return 1;
190
191    /* Or if we already own it */
192    if (rwlock->writerThreadId == thread_id)
193        return 1;
194
195    /* Otherwise, not */
196    return 0;
197}
198
199/* This function is used to waken any waiting thread contending
200 * for the lock. One of them should be able to grab it after
201 * that.
202 */
203static void _pthread_rwlock_pulse(pthread_rwlock_t *rwlock)
204{
205    if (rwlock->pendingReaders > 0 || rwlock->pendingWriters > 0)
206        pthread_cond_broadcast(&rwlock->cond);
207}
208
209
210int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock)
211{
212    return pthread_rwlock_timedrdlock(rwlock, NULL);
213}
214
215int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock)
216{
217    int ret = 0;
218
219    if (rwlock == NULL)
220        return EINVAL;
221
222    pthread_mutex_lock(&rwlock->lock);
223    if (__unlikely(!read_precondition(rwlock, __get_thread_id())))
224        ret = EBUSY;
225    else
226        rwlock->numLocks ++;
227    pthread_mutex_unlock(&rwlock->lock);
228
229    return ret;
230}
231
232int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout)
233{
234    int thread_id, ret = 0;
235
236    if (rwlock == NULL)
237        return EINVAL;
238
239    pthread_mutex_lock(&rwlock->lock);
240    thread_id = __get_thread_id();
241    if (__unlikely(!read_precondition(rwlock, thread_id))) {
242        rwlock->pendingReaders += 1;
243        do {
244            ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout);
245        } while (ret == 0 && !read_precondition(rwlock, thread_id));
246        rwlock->pendingReaders -= 1;
247        if (ret != 0)
248            goto EXIT;
249    }
250    rwlock->numLocks ++;
251EXIT:
252    pthread_mutex_unlock(&rwlock->lock);
253    return ret;
254}
255
256
257int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock)
258{
259    return pthread_rwlock_timedwrlock(rwlock, NULL);
260}
261
262int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock)
263{
264    int thread_id, ret = 0;
265
266    if (rwlock == NULL)
267        return EINVAL;
268
269    pthread_mutex_lock(&rwlock->lock);
270    thread_id = __get_thread_id();
271    if (__unlikely(!write_precondition(rwlock, thread_id))) {
272        ret = EBUSY;
273    } else {
274        rwlock->numLocks ++;
275        rwlock->writerThreadId = thread_id;
276    }
277    pthread_mutex_unlock(&rwlock->lock);
278    return ret;
279}
280
281int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout)
282{
283    int thread_id, ret = 0;
284
285    if (rwlock == NULL)
286        return EINVAL;
287
288    pthread_mutex_lock(&rwlock->lock);
289    thread_id = __get_thread_id();
290    if (__unlikely(!write_precondition(rwlock, thread_id))) {
291        /* If we can't read yet, wait until the rwlock is unlocked
292         * and try again. Increment pendingReaders to get the
293         * cond broadcast when that happens.
294         */
295        rwlock->pendingWriters += 1;
296        do {
297            ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout);
298        } while (ret == 0 && !write_precondition(rwlock, thread_id));
299        rwlock->pendingWriters -= 1;
300        if (ret != 0)
301            goto EXIT;
302    }
303    rwlock->numLocks ++;
304    rwlock->writerThreadId = thread_id;
305EXIT:
306    pthread_mutex_unlock(&rwlock->lock);
307    return ret;
308}
309
310
311int pthread_rwlock_unlock(pthread_rwlock_t *rwlock)
312{
313    int  ret = 0;
314
315    if (rwlock == NULL)
316        return EINVAL;
317
318    pthread_mutex_lock(&rwlock->lock);
319
320    /* The lock must be held */
321    if (rwlock->numLocks == 0) {
322        ret = EPERM;
323        goto EXIT;
324    }
325
326    /* If it has only readers, writerThreadId is 0 */
327    if (rwlock->writerThreadId == 0) {
328        if (--rwlock->numLocks == 0)
329            _pthread_rwlock_pulse(rwlock);
330    }
331    /* Otherwise, it has only a single writer, which
332     * must be ourselves.
333     */
334    else {
335        if (rwlock->writerThreadId != __get_thread_id()) {
336            ret = EPERM;
337            goto EXIT;
338        }
339        if (--rwlock->numLocks == 0) {
340            rwlock->writerThreadId = 0;
341            _pthread_rwlock_pulse(rwlock);
342        }
343    }
344EXIT:
345    pthread_mutex_unlock(&rwlock->lock);
346    return ret;
347}
348