1 /*-
2  * Copyright (c) 1998 Alex Nash
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  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  * $FreeBSD: src/lib/libpthread/thread/thr_rwlock.c,v 1.14 2004/01/08 15:37:09 deischen Exp $
27  * $DragonFly: src/lib/libthread_xu/thread/thr_rwlock.c,v 1.7 2006/04/06 13:03:09 davidxu Exp $
28  */
29 
30 #include "namespace.h"
31 #include <machine/tls.h>
32 
33 #include <errno.h>
34 #include <limits.h>
35 #include <stdlib.h>
36 #include <pthread.h>
37 #include "un-namespace.h"
38 
39 #include "thr_private.h"
40 
41 /* maximum number of times a read lock may be obtained */
42 #define	MAX_READ_LOCKS		(INT_MAX - 1)
43 
44 umtx_t	_rwlock_static_lock;
45 
46 static int
47 rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr __unused)
48 {
49 	pthread_rwlock_t prwlock;
50 	int ret;
51 
52 	/* allocate rwlock object */
53 	prwlock = (pthread_rwlock_t)malloc(sizeof(struct pthread_rwlock));
54 
55 	if (prwlock == NULL)
56 		return (ENOMEM);
57 
58 	/* initialize the lock */
59 	if ((ret = _pthread_mutex_init(&prwlock->lock, NULL)) != 0)
60 		free(prwlock);
61 	else {
62 		/* initialize the read condition signal */
63 		ret = _pthread_cond_init(&prwlock->read_signal, NULL);
64 
65 		if (ret != 0) {
66 			_pthread_mutex_destroy(&prwlock->lock);
67 			free(prwlock);
68 		} else {
69 			/* initialize the write condition signal */
70 			ret = _pthread_cond_init(&prwlock->write_signal, NULL);
71 
72 			if (ret != 0) {
73 				_pthread_cond_destroy(&prwlock->read_signal);
74 				_pthread_mutex_destroy(&prwlock->lock);
75 				free(prwlock);
76 			} else {
77 				/* success */
78 				prwlock->state = 0;
79 				prwlock->blocked_writers = 0;
80 				*rwlock = prwlock;
81 			}
82 		}
83 	}
84 
85 	return (ret);
86 }
87 
88 int
89 _pthread_rwlock_destroy (pthread_rwlock_t *rwlock)
90 {
91 	int ret;
92 
93 	if (rwlock == NULL)
94 		ret = EINVAL;
95 	else {
96 		pthread_rwlock_t prwlock;
97 
98 		prwlock = *rwlock;
99 
100 		_pthread_mutex_destroy(&prwlock->lock);
101 		_pthread_cond_destroy(&prwlock->read_signal);
102 		_pthread_cond_destroy(&prwlock->write_signal);
103 		free(prwlock);
104 
105 		*rwlock = NULL;
106 
107 		ret = 0;
108 	}
109 	return (ret);
110 }
111 
112 static int
113 init_static(struct pthread *thread, pthread_rwlock_t *rwlock)
114 {
115 	int ret;
116 
117 	THR_LOCK_ACQUIRE(thread, &_rwlock_static_lock);
118 
119 	if (*rwlock == NULL)
120 		ret = rwlock_init(rwlock, NULL);
121 	else
122 		ret = 0;
123 
124 	THR_LOCK_RELEASE(thread, &_rwlock_static_lock);
125 
126 	return (ret);
127 }
128 
129 int
130 _pthread_rwlock_init (pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr)
131 {
132 	*rwlock = NULL;
133 	return (rwlock_init(rwlock, attr));
134 }
135 
136 static int
137 rwlock_rdlock_common (pthread_rwlock_t *rwlock, const struct timespec *abstime)
138 {
139 	struct pthread *curthread = tls_get_curthread();
140 	pthread_rwlock_t prwlock;
141 	int ret;
142 
143 	if (rwlock == NULL)
144 		return (EINVAL);
145 
146 	prwlock = *rwlock;
147 
148 	/* check for static initialization */
149 	if (prwlock == NULL) {
150 		if ((ret = init_static(curthread, rwlock)) != 0)
151 			return (ret);
152 
153 		prwlock = *rwlock;
154 	}
155 
156 	/* grab the monitor lock */
157 	if ((ret = _pthread_mutex_lock(&prwlock->lock)) != 0)
158 		return (ret);
159 
160 	/* check lock count */
161 	if (prwlock->state == MAX_READ_LOCKS) {
162 		_pthread_mutex_unlock(&prwlock->lock);
163 		return (EAGAIN);
164 	}
165 
166 	curthread = tls_get_curthread();
167 	if ((curthread->rdlock_count > 0) && (prwlock->state > 0)) {
168 		/*
169 		 * To avoid having to track all the rdlocks held by
170 		 * a thread or all of the threads that hold a rdlock,
171 		 * we keep a simple count of all the rdlocks held by
172 		 * a thread.  If a thread holds any rdlocks it is
173 		 * possible that it is attempting to take a recursive
174 		 * rdlock.  If there are blocked writers and precedence
175 		 * is given to them, then that would result in the thread
176 		 * deadlocking.  So allowing a thread to take the rdlock
177 		 * when it already has one or more rdlocks avoids the
178 		 * deadlock.  I hope the reader can follow that logic ;-)
179 		 */
180 		;	/* nothing needed */
181 	} else {
182 		/* give writers priority over readers */
183 		while (prwlock->blocked_writers || prwlock->state < 0) {
184 			if (abstime)
185 				ret = _pthread_cond_timedwait
186 				    (&prwlock->read_signal,
187 				    &prwlock->lock, abstime);
188 			else
189 				ret = _pthread_cond_wait(&prwlock->read_signal,
190 			    &prwlock->lock);
191 			if (ret != 0) {
192 				/* can't do a whole lot if this fails */
193 				_pthread_mutex_unlock(&prwlock->lock);
194 				return (ret);
195 			}
196 		}
197 	}
198 
199 	curthread->rdlock_count++;
200 	prwlock->state++; /* indicate we are locked for reading */
201 
202 	/*
203 	 * Something is really wrong if this call fails.  Returning
204 	 * error won't do because we've already obtained the read
205 	 * lock.  Decrementing 'state' is no good because we probably
206 	 * don't have the monitor lock.
207 	 */
208 	_pthread_mutex_unlock(&prwlock->lock);
209 
210 	return (ret);
211 }
212 
213 int
214 _pthread_rwlock_rdlock (pthread_rwlock_t *rwlock)
215 {
216 	return (rwlock_rdlock_common(rwlock, NULL));
217 }
218 
219 int
220 _pthread_rwlock_timedrdlock (pthread_rwlock_t *rwlock,
221 	 const struct timespec *abstime)
222 {
223 	return (rwlock_rdlock_common(rwlock, abstime));
224 }
225 
226 int
227 _pthread_rwlock_tryrdlock (pthread_rwlock_t *rwlock)
228 {
229 	struct pthread *curthread = tls_get_curthread();
230 	pthread_rwlock_t prwlock;
231 	int ret;
232 
233 	if (rwlock == NULL)
234 		return (EINVAL);
235 
236 	prwlock = *rwlock;
237 
238 	/* check for static initialization */
239 	if (prwlock == NULL) {
240 		if ((ret = init_static(curthread, rwlock)) != 0)
241 			return (ret);
242 
243 		prwlock = *rwlock;
244 	}
245 
246 	/* grab the monitor lock */
247 	if ((ret = _pthread_mutex_lock(&prwlock->lock)) != 0)
248 		return (ret);
249 
250 	curthread = tls_get_curthread();
251 	if (prwlock->state == MAX_READ_LOCKS)
252 		ret = EAGAIN;
253 	else if ((curthread->rdlock_count > 0) && (prwlock->state > 0)) {
254 		/* see comment for pthread_rwlock_rdlock() */
255 		curthread->rdlock_count++;
256 		prwlock->state++;
257 	}
258 	/* give writers priority over readers */
259 	else if (prwlock->blocked_writers || prwlock->state < 0)
260 		ret = EBUSY;
261 	else {
262 		curthread->rdlock_count++;
263 		prwlock->state++; /* indicate we are locked for reading */
264 	}
265 
266 	/* see the comment on this in pthread_rwlock_rdlock */
267 	_pthread_mutex_unlock(&prwlock->lock);
268 
269 	return (ret);
270 }
271 
272 int
273 _pthread_rwlock_trywrlock (pthread_rwlock_t *rwlock)
274 {
275 	struct pthread *curthread = tls_get_curthread();
276 	pthread_rwlock_t prwlock;
277 	int ret;
278 
279 	if (rwlock == NULL)
280 		return (EINVAL);
281 
282 	prwlock = *rwlock;
283 
284 	/* check for static initialization */
285 	if (prwlock == NULL) {
286 		if ((ret = init_static(curthread, rwlock)) != 0)
287 			return (ret);
288 
289 		prwlock = *rwlock;
290 	}
291 
292 	/* grab the monitor lock */
293 	if ((ret = _pthread_mutex_lock(&prwlock->lock)) != 0)
294 		return (ret);
295 
296 	if (prwlock->state != 0)
297 		ret = EBUSY;
298 	else
299 		/* indicate we are locked for writing */
300 		prwlock->state = -1;
301 
302 	/* see the comment on this in pthread_rwlock_rdlock */
303 	_pthread_mutex_unlock(&prwlock->lock);
304 
305 	return (ret);
306 }
307 
308 int
309 _pthread_rwlock_unlock (pthread_rwlock_t *rwlock)
310 {
311 	struct pthread *curthread;
312 	pthread_rwlock_t prwlock;
313 	int ret;
314 
315 	if (rwlock == NULL)
316 		return (EINVAL);
317 
318 	prwlock = *rwlock;
319 
320 	if (prwlock == NULL)
321 		return (EINVAL);
322 
323 	/* grab the monitor lock */
324 	if ((ret = _pthread_mutex_lock(&prwlock->lock)) != 0)
325 		return (ret);
326 
327 	curthread = tls_get_curthread();
328 	if (prwlock->state > 0) {
329 		curthread->rdlock_count--;
330 		prwlock->state--;
331 		if (prwlock->state == 0 && prwlock->blocked_writers)
332 			ret = _pthread_cond_signal(&prwlock->write_signal);
333 	} else if (prwlock->state < 0) {
334 		prwlock->state = 0;
335 
336 		if (prwlock->blocked_writers)
337 			ret = _pthread_cond_signal(&prwlock->write_signal);
338 		else
339 			ret = _pthread_cond_broadcast(&prwlock->read_signal);
340 	} else
341 		ret = EINVAL;
342 
343 	/* see the comment on this in pthread_rwlock_rdlock */
344 	_pthread_mutex_unlock(&prwlock->lock);
345 
346 	return (ret);
347 }
348 
349 static int
350 rwlock_wrlock_common (pthread_rwlock_t *rwlock, const struct timespec *abstime)
351 {
352 	struct pthread *curthread = tls_get_curthread();
353 	pthread_rwlock_t prwlock;
354 	int ret;
355 
356 	if (rwlock == NULL)
357 		return (EINVAL);
358 
359 	prwlock = *rwlock;
360 
361 	/* check for static initialization */
362 	if (prwlock == NULL) {
363 		if ((ret = init_static(curthread, rwlock)) != 0)
364 			return (ret);
365 
366 		prwlock = *rwlock;
367 	}
368 
369 	/* grab the monitor lock */
370 	if ((ret = _pthread_mutex_lock(&prwlock->lock)) != 0)
371 		return (ret);
372 
373 	while (prwlock->state != 0) {
374 		prwlock->blocked_writers++;
375 
376 		if (abstime != NULL)
377 			ret = _pthread_cond_timedwait(&prwlock->write_signal,
378 			    &prwlock->lock, abstime);
379 		else
380 			ret = _pthread_cond_wait(&prwlock->write_signal,
381 			    &prwlock->lock);
382 		if (ret != 0) {
383 			prwlock->blocked_writers--;
384 			_pthread_mutex_unlock(&prwlock->lock);
385 			return (ret);
386 		}
387 
388 		prwlock->blocked_writers--;
389 	}
390 
391 	/* indicate we are locked for writing */
392 	prwlock->state = -1;
393 
394 	/* see the comment on this in pthread_rwlock_rdlock */
395 	_pthread_mutex_unlock(&prwlock->lock);
396 
397 	return (ret);
398 }
399 
400 int
401 _pthread_rwlock_wrlock (pthread_rwlock_t *rwlock)
402 {
403 	return (rwlock_wrlock_common (rwlock, NULL));
404 }
405 
406 int
407 _pthread_rwlock_timedwrlock (pthread_rwlock_t *rwlock,
408     const struct timespec *abstime)
409 {
410 	return (rwlock_wrlock_common (rwlock, abstime));
411 }
412 
413 __strong_reference(_pthread_rwlock_destroy, pthread_rwlock_destroy);
414 __strong_reference(_pthread_rwlock_init, pthread_rwlock_init);
415 __strong_reference(_pthread_rwlock_rdlock, pthread_rwlock_rdlock);
416 __strong_reference(_pthread_rwlock_timedrdlock, pthread_rwlock_timedrdlock);
417 __strong_reference(_pthread_rwlock_tryrdlock, pthread_rwlock_tryrdlock);
418 __strong_reference(_pthread_rwlock_trywrlock, pthread_rwlock_trywrlock);
419 __strong_reference(_pthread_rwlock_unlock, pthread_rwlock_unlock);
420 __strong_reference(_pthread_rwlock_wrlock, pthread_rwlock_wrlock);
421 __strong_reference(_pthread_rwlock_timedwrlock, pthread_rwlock_timedwrlock);
422 
423