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 behavior 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  RWLOCKATTR_DEFAULT     0
57#define  RWLOCKATTR_SHARED_MASK 0x0010
58
59extern pthread_internal_t* __get_thread(void);
60
61int pthread_rwlockattr_init(pthread_rwlockattr_t *attr)
62{
63    if (!attr)
64        return EINVAL;
65
66    *attr = PTHREAD_PROCESS_PRIVATE;
67    return 0;
68}
69
70int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr)
71{
72    if (!attr)
73        return EINVAL;
74
75    *attr = -1;
76    return 0;
77}
78
79int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int  pshared)
80{
81    if (!attr)
82        return EINVAL;
83
84    switch (pshared) {
85    case PTHREAD_PROCESS_PRIVATE:
86    case PTHREAD_PROCESS_SHARED:
87        *attr = pshared;
88        return 0;
89    default:
90        return EINVAL;
91    }
92}
93
94int pthread_rwlockattr_getpshared(pthread_rwlockattr_t *attr, int *pshared)
95{
96    if (!attr || !pshared)
97        return EINVAL;
98
99    *pshared = *attr;
100    return 0;
101}
102
103int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr)
104{
105    pthread_mutexattr_t*  lock_attr = NULL;
106    pthread_condattr_t*   cond_attr = NULL;
107    pthread_mutexattr_t   lock_attr0;
108    pthread_condattr_t    cond_attr0;
109    int                   ret;
110
111    if (rwlock == NULL)
112        return EINVAL;
113
114    if (attr && *attr == PTHREAD_PROCESS_SHARED) {
115        lock_attr = &lock_attr0;
116        pthread_mutexattr_init(lock_attr);
117        pthread_mutexattr_setpshared(lock_attr, PTHREAD_PROCESS_SHARED);
118
119        cond_attr = &cond_attr0;
120        pthread_condattr_init(cond_attr);
121        pthread_condattr_setpshared(cond_attr, PTHREAD_PROCESS_SHARED);
122    }
123
124    ret = pthread_mutex_init(&rwlock->lock, lock_attr);
125    if (ret != 0)
126        return ret;
127
128    ret = pthread_cond_init(&rwlock->cond, cond_attr);
129    if (ret != 0) {
130        pthread_mutex_destroy(&rwlock->lock);
131        return ret;
132    }
133
134    rwlock->numLocks = 0;
135    rwlock->pendingReaders = 0;
136    rwlock->pendingWriters = 0;
137    rwlock->writerThreadId = 0;
138
139    return 0;
140}
141
142int pthread_rwlock_destroy(pthread_rwlock_t *rwlock)
143{
144    if (rwlock == NULL)
145        return EINVAL;
146
147    if (rwlock->numLocks > 0)
148        return EBUSY;
149
150    pthread_cond_destroy(&rwlock->cond);
151    pthread_mutex_destroy(&rwlock->lock);
152    return 0;
153}
154
155/* Returns TRUE iff we can acquire a read lock. */
156static __inline__ int read_precondition(pthread_rwlock_t* rwlock, int tid)
157{
158    /* We can't have the lock if any writer is waiting for it (writer bias).
159     * This tries to avoid starvation when there are multiple readers racing.
160     */
161    if (rwlock->pendingWriters > 0)
162        return 0;
163
164    /* We can have the lock if there is no writer, or if we write-own it */
165    /* The second test avoids a self-dead lock in case of buggy code. */
166    if (rwlock->writerThreadId == 0 || rwlock->writerThreadId == tid)
167        return 1;
168
169    /* Otherwise, we can't have it */
170    return 0;
171}
172
173/* returns TRUE iff we can acquire a write lock. */
174static __inline__ int write_precondition(pthread_rwlock_t* rwlock, int tid)
175{
176    /* We can get the lock if nobody has it */
177    if (rwlock->numLocks == 0)
178        return 1;
179
180    /* Or if we already own it */
181    if (rwlock->writerThreadId == tid)
182        return 1;
183
184    /* Otherwise, not */
185    return 0;
186}
187
188/* This function is used to waken any waiting thread contending
189 * for the lock. One of them should be able to grab it after
190 * that.
191 */
192static void _pthread_rwlock_pulse(pthread_rwlock_t *rwlock)
193{
194    if (rwlock->pendingReaders > 0 || rwlock->pendingWriters > 0)
195        pthread_cond_broadcast(&rwlock->cond);
196}
197
198
199int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock)
200{
201    return pthread_rwlock_timedrdlock(rwlock, NULL);
202}
203
204int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock)
205{
206    int ret = 0;
207
208    if (rwlock == NULL)
209        return EINVAL;
210
211    pthread_mutex_lock(&rwlock->lock);
212    if (__predict_false(!read_precondition(rwlock, __get_thread()->tid)))
213        ret = EBUSY;
214    else
215        rwlock->numLocks ++;
216    pthread_mutex_unlock(&rwlock->lock);
217
218    return ret;
219}
220
221int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout)
222{
223    int ret = 0;
224
225    if (rwlock == NULL)
226        return EINVAL;
227
228    pthread_mutex_lock(&rwlock->lock);
229    int tid = __get_thread()->tid;
230    if (__predict_false(!read_precondition(rwlock, tid))) {
231        rwlock->pendingReaders += 1;
232        do {
233            ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout);
234        } while (ret == 0 && !read_precondition(rwlock, tid));
235        rwlock->pendingReaders -= 1;
236        if (ret != 0)
237            goto EXIT;
238    }
239    rwlock->numLocks ++;
240EXIT:
241    pthread_mutex_unlock(&rwlock->lock);
242    return ret;
243}
244
245
246int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock)
247{
248    return pthread_rwlock_timedwrlock(rwlock, NULL);
249}
250
251int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock)
252{
253    int ret = 0;
254
255    if (rwlock == NULL)
256        return EINVAL;
257
258    pthread_mutex_lock(&rwlock->lock);
259    int tid = __get_thread()->tid;
260    if (__predict_false(!write_precondition(rwlock, tid))) {
261        ret = EBUSY;
262    } else {
263        rwlock->numLocks ++;
264        rwlock->writerThreadId = tid;
265    }
266    pthread_mutex_unlock(&rwlock->lock);
267    return ret;
268}
269
270int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock, const struct timespec *abs_timeout)
271{
272    int ret = 0;
273
274    if (rwlock == NULL)
275        return EINVAL;
276
277    pthread_mutex_lock(&rwlock->lock);
278    int tid = __get_thread()->tid;
279    if (__predict_false(!write_precondition(rwlock, tid))) {
280        /* If we can't read yet, wait until the rwlock is unlocked
281         * and try again. Increment pendingReaders to get the
282         * cond broadcast when that happens.
283         */
284        rwlock->pendingWriters += 1;
285        do {
286            ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout);
287        } while (ret == 0 && !write_precondition(rwlock, tid));
288        rwlock->pendingWriters -= 1;
289        if (ret != 0)
290            goto EXIT;
291    }
292    rwlock->numLocks ++;
293    rwlock->writerThreadId = tid;
294EXIT:
295    pthread_mutex_unlock(&rwlock->lock);
296    return ret;
297}
298
299
300int pthread_rwlock_unlock(pthread_rwlock_t *rwlock)
301{
302    int  ret = 0;
303
304    if (rwlock == NULL)
305        return EINVAL;
306
307    pthread_mutex_lock(&rwlock->lock);
308
309    /* The lock must be held */
310    if (rwlock->numLocks == 0) {
311        ret = EPERM;
312        goto EXIT;
313    }
314
315    /* If it has only readers, writerThreadId is 0 */
316    if (rwlock->writerThreadId == 0) {
317        if (--rwlock->numLocks == 0)
318            _pthread_rwlock_pulse(rwlock);
319    }
320    /* Otherwise, it has only a single writer, which
321     * must be ourselves.
322     */
323    else {
324        if (rwlock->writerThreadId != __get_thread()->tid) {
325            ret = EPERM;
326            goto EXIT;
327        }
328        if (--rwlock->numLocks == 0) {
329            rwlock->writerThreadId = 0;
330            _pthread_rwlock_pulse(rwlock);
331        }
332    }
333EXIT:
334    pthread_mutex_unlock(&rwlock->lock);
335    return ret;
336}
337