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