1 /* $NetBSD: rdwr.c,v 1.2 2021/08/14 16:14:56 christos Exp $ */
2
3 /* $OpenLDAP$ */
4 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 *
6 * Copyright 1998-2021 The OpenLDAP Foundation.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted only as authorized by the OpenLDAP
11 * Public License.
12 *
13 * A copy of this license is available in file LICENSE in the
14 * top-level directory of the distribution or, alternatively, at
15 * <http://www.OpenLDAP.org/license.html>.
16 */
17 /* This work was initially developed by Kurt D. Zeilenga for inclusion
18 * in OpenLDAP Software. Additional significant contributors include:
19 * Stuart Lynne
20 */
21
22 /*
23 * This is an improved implementation of Reader/Writer locks does
24 * not protect writers from starvation. That is, if a writer is
25 * currently waiting on a reader, any new reader will get
26 * the lock before the writer.
27 *
28 * Does not support cancellation nor does any status checking.
29 */
30 /* Adapted from publicly available examples for:
31 * "Programming with Posix Threads"
32 * by David R Butenhof, Addison-Wesley
33 * http://cseng.aw.com/bookpage.taf?ISBN=0-201-63392-2
34 */
35
36 #include <sys/cdefs.h>
37 __RCSID("$NetBSD: rdwr.c,v 1.2 2021/08/14 16:14:56 christos Exp $");
38
39 #include "portable.h"
40
41 #include <ac/stdlib.h>
42
43 #include <ac/errno.h>
44 #include <ac/string.h>
45 #include <ac/time.h>
46
47 #include "ldap-int.h"
48
49 #ifdef LDAP_R_COMPILE
50
51 #include "ldap_pvt_thread.h" /* Get the thread interface */
52 #define LDAP_THREAD_RDWR_IMPLEMENTATION
53 #include "ldap_thr_debug.h" /* May rename the symbols defined below */
54
55 /*
56 * implementations that provide their own compatible
57 * reader/writer locks define LDAP_THREAD_HAVE_RDWR
58 * in ldap_pvt_thread.h
59 */
60 #ifndef LDAP_THREAD_HAVE_RDWR
61
62 struct ldap_int_thread_rdwr_s {
63 ldap_pvt_thread_mutex_t ltrw_mutex;
64 ldap_pvt_thread_cond_t ltrw_read; /* wait for read */
65 ldap_pvt_thread_cond_t ltrw_write; /* wait for write */
66 int ltrw_valid;
67 #define LDAP_PVT_THREAD_RDWR_VALID 0x0bad
68 int ltrw_r_active;
69 int ltrw_w_active;
70 int ltrw_r_wait;
71 int ltrw_w_wait;
72 #ifdef LDAP_RDWR_DEBUG
73 /* keep track of who has these locks */
74 #define MAX_READERS 32
75 int ltrw_more_readers; /* Set if ltrw_readers[] is incomplete */
76 ldap_pvt_thread_t ltrw_readers[MAX_READERS];
77 ldap_pvt_thread_t ltrw_writer;
78 #endif
79 };
80
81 int
ldap_pvt_thread_rdwr_init(ldap_pvt_thread_rdwr_t * rwlock)82 ldap_pvt_thread_rdwr_init( ldap_pvt_thread_rdwr_t *rwlock )
83 {
84 struct ldap_int_thread_rdwr_s *rw;
85
86 assert( rwlock != NULL );
87
88 rw = (struct ldap_int_thread_rdwr_s *) LDAP_CALLOC( 1,
89 sizeof( struct ldap_int_thread_rdwr_s ) );
90 if ( !rw )
91 return LDAP_NO_MEMORY;
92
93 /* we should check return results */
94 ldap_pvt_thread_mutex_init( &rw->ltrw_mutex );
95 ldap_pvt_thread_cond_init( &rw->ltrw_read );
96 ldap_pvt_thread_cond_init( &rw->ltrw_write );
97
98 rw->ltrw_valid = LDAP_PVT_THREAD_RDWR_VALID;
99
100 *rwlock = rw;
101 return 0;
102 }
103
104 int
ldap_pvt_thread_rdwr_destroy(ldap_pvt_thread_rdwr_t * rwlock)105 ldap_pvt_thread_rdwr_destroy( ldap_pvt_thread_rdwr_t *rwlock )
106 {
107 struct ldap_int_thread_rdwr_s *rw;
108
109 assert( rwlock != NULL );
110 rw = *rwlock;
111
112 assert( rw != NULL );
113 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
114
115 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
116 return LDAP_PVT_THREAD_EINVAL;
117
118 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
119
120 assert( rw->ltrw_w_active >= 0 );
121 assert( rw->ltrw_w_wait >= 0 );
122 assert( rw->ltrw_r_active >= 0 );
123 assert( rw->ltrw_r_wait >= 0 );
124
125 /* active threads? */
126 if( rw->ltrw_r_active > 0 || rw->ltrw_w_active > 0) {
127 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
128 return LDAP_PVT_THREAD_EBUSY;
129 }
130
131 /* waiting threads? */
132 if( rw->ltrw_r_wait > 0 || rw->ltrw_w_wait > 0) {
133 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
134 return LDAP_PVT_THREAD_EBUSY;
135 }
136
137 rw->ltrw_valid = 0;
138
139 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
140
141 ldap_pvt_thread_mutex_destroy( &rw->ltrw_mutex );
142 ldap_pvt_thread_cond_destroy( &rw->ltrw_read );
143 ldap_pvt_thread_cond_destroy( &rw->ltrw_write );
144
145 LDAP_FREE(rw);
146 *rwlock = NULL;
147 return 0;
148 }
149
ldap_pvt_thread_rdwr_rlock(ldap_pvt_thread_rdwr_t * rwlock)150 int ldap_pvt_thread_rdwr_rlock( ldap_pvt_thread_rdwr_t *rwlock )
151 {
152 struct ldap_int_thread_rdwr_s *rw;
153
154 assert( rwlock != NULL );
155 rw = *rwlock;
156
157 assert( rw != NULL );
158 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
159
160 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
161 return LDAP_PVT_THREAD_EINVAL;
162
163 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
164
165 assert( rw->ltrw_w_active >= 0 );
166 assert( rw->ltrw_w_wait >= 0 );
167 assert( rw->ltrw_r_active >= 0 );
168 assert( rw->ltrw_r_wait >= 0 );
169
170 if( rw->ltrw_w_active > 0 ) {
171 /* writer is active */
172
173 rw->ltrw_r_wait++;
174
175 do {
176 ldap_pvt_thread_cond_wait(
177 &rw->ltrw_read, &rw->ltrw_mutex );
178 } while( rw->ltrw_w_active > 0 );
179
180 rw->ltrw_r_wait--;
181 assert( rw->ltrw_r_wait >= 0 );
182 }
183
184 #ifdef LDAP_RDWR_DEBUG
185 if( rw->ltrw_r_active < MAX_READERS )
186 rw->ltrw_readers[rw->ltrw_r_active] = ldap_pvt_thread_self();
187 else
188 rw->ltrw_more_readers = 1;
189 #endif
190 rw->ltrw_r_active++;
191
192
193 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
194
195 return 0;
196 }
197
ldap_pvt_thread_rdwr_rtrylock(ldap_pvt_thread_rdwr_t * rwlock)198 int ldap_pvt_thread_rdwr_rtrylock( ldap_pvt_thread_rdwr_t *rwlock )
199 {
200 struct ldap_int_thread_rdwr_s *rw;
201
202 assert( rwlock != NULL );
203 rw = *rwlock;
204
205 assert( rw != NULL );
206 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
207
208 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
209 return LDAP_PVT_THREAD_EINVAL;
210
211 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
212
213 assert( rw->ltrw_w_active >= 0 );
214 assert( rw->ltrw_w_wait >= 0 );
215 assert( rw->ltrw_r_active >= 0 );
216 assert( rw->ltrw_r_wait >= 0 );
217
218 if( rw->ltrw_w_active > 0) {
219 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
220 return LDAP_PVT_THREAD_EBUSY;
221 }
222
223 #ifdef LDAP_RDWR_DEBUG
224 if( rw->ltrw_r_active < MAX_READERS )
225 rw->ltrw_readers[rw->ltrw_r_active] = ldap_pvt_thread_self();
226 else
227 rw->ltrw_more_readers = 1;
228 #endif
229 rw->ltrw_r_active++;
230
231 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
232
233 return 0;
234 }
235
ldap_pvt_thread_rdwr_runlock(ldap_pvt_thread_rdwr_t * rwlock)236 int ldap_pvt_thread_rdwr_runlock( ldap_pvt_thread_rdwr_t *rwlock )
237 {
238 struct ldap_int_thread_rdwr_s *rw;
239
240 assert( rwlock != NULL );
241 rw = *rwlock;
242
243 assert( rw != NULL );
244 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
245
246 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
247 return LDAP_PVT_THREAD_EINVAL;
248
249 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
250
251 rw->ltrw_r_active--;
252 #ifdef LDAP_RDWR_DEBUG
253 /* Remove us from the list of readers */
254 {
255 ldap_pvt_thread_t self = ldap_pvt_thread_self();
256 int i, j;
257 for( i = j = rw->ltrw_r_active; i >= 0; i--) {
258 if (rw->ltrw_readers[i] == self) {
259 rw->ltrw_readers[i] = rw->ltrw_readers[j];
260 rw->ltrw_readers[j] = 0;
261 break;
262 }
263 }
264 if( !rw->ltrw_more_readers )
265 assert( i >= 0 );
266 else if( j == 0 )
267 rw->ltrw_more_readers = 0;
268 }
269 #endif
270
271 assert( rw->ltrw_w_active >= 0 );
272 assert( rw->ltrw_w_wait >= 0 );
273 assert( rw->ltrw_r_active >= 0 );
274 assert( rw->ltrw_r_wait >= 0 );
275
276 if (rw->ltrw_r_active == 0 && rw->ltrw_w_wait > 0 ) {
277 ldap_pvt_thread_cond_signal( &rw->ltrw_write );
278 }
279
280 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
281
282 return 0;
283 }
284
ldap_pvt_thread_rdwr_wlock(ldap_pvt_thread_rdwr_t * rwlock)285 int ldap_pvt_thread_rdwr_wlock( ldap_pvt_thread_rdwr_t *rwlock )
286 {
287 struct ldap_int_thread_rdwr_s *rw;
288
289 assert( rwlock != NULL );
290 rw = *rwlock;
291
292 assert( rw != NULL );
293 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
294
295 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
296 return LDAP_PVT_THREAD_EINVAL;
297
298 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
299
300 assert( rw->ltrw_w_active >= 0 );
301 assert( rw->ltrw_w_wait >= 0 );
302 assert( rw->ltrw_r_active >= 0 );
303 assert( rw->ltrw_r_wait >= 0 );
304
305 if ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 ) {
306 rw->ltrw_w_wait++;
307
308 do {
309 ldap_pvt_thread_cond_wait(
310 &rw->ltrw_write, &rw->ltrw_mutex );
311 } while ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 );
312
313 rw->ltrw_w_wait--;
314 assert( rw->ltrw_w_wait >= 0 );
315 }
316
317 #ifdef LDAP_RDWR_DEBUG
318 rw->ltrw_writer = ldap_pvt_thread_self();
319 #endif
320 rw->ltrw_w_active++;
321
322 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
323
324 return 0;
325 }
326
ldap_pvt_thread_rdwr_wtrylock(ldap_pvt_thread_rdwr_t * rwlock)327 int ldap_pvt_thread_rdwr_wtrylock( ldap_pvt_thread_rdwr_t *rwlock )
328 {
329 struct ldap_int_thread_rdwr_s *rw;
330
331 assert( rwlock != NULL );
332 rw = *rwlock;
333
334 assert( rw != NULL );
335 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
336
337 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
338 return LDAP_PVT_THREAD_EINVAL;
339
340 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
341
342 assert( rw->ltrw_w_active >= 0 );
343 assert( rw->ltrw_w_wait >= 0 );
344 assert( rw->ltrw_r_active >= 0 );
345 assert( rw->ltrw_r_wait >= 0 );
346
347 if ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 ) {
348 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
349 return LDAP_PVT_THREAD_EBUSY;
350 }
351
352 #ifdef LDAP_RDWR_DEBUG
353 rw->ltrw_writer = ldap_pvt_thread_self();
354 #endif
355 rw->ltrw_w_active++;
356
357 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
358
359 return 0;
360 }
361
ldap_pvt_thread_rdwr_wunlock(ldap_pvt_thread_rdwr_t * rwlock)362 int ldap_pvt_thread_rdwr_wunlock( ldap_pvt_thread_rdwr_t *rwlock )
363 {
364 struct ldap_int_thread_rdwr_s *rw;
365
366 assert( rwlock != NULL );
367 rw = *rwlock;
368
369 assert( rw != NULL );
370 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
371
372 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
373 return LDAP_PVT_THREAD_EINVAL;
374
375 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
376
377 rw->ltrw_w_active--;
378
379 assert( rw->ltrw_w_active >= 0 );
380 assert( rw->ltrw_w_wait >= 0 );
381 assert( rw->ltrw_r_active >= 0 );
382 assert( rw->ltrw_r_wait >= 0 );
383
384 if (rw->ltrw_r_wait > 0) {
385 ldap_pvt_thread_cond_broadcast( &rw->ltrw_read );
386
387 } else if (rw->ltrw_w_wait > 0) {
388 ldap_pvt_thread_cond_signal( &rw->ltrw_write );
389 }
390
391 #ifdef LDAP_RDWR_DEBUG
392 assert( rw->ltrw_writer == ldap_pvt_thread_self() );
393 rw->ltrw_writer = 0;
394 #endif
395 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
396
397 return 0;
398 }
399
400 #ifdef LDAP_RDWR_DEBUG
401
402 /* just for testing,
403 * return 0 if false, suitable for assert(ldap_pvt_thread_rdwr_Xchk(rdwr))
404 *
405 * Currently they don't check if the calling thread is the one
406 * that has the lock, just that there is a reader or writer.
407 *
408 * Basically sufficient for testing that places that should have
409 * a lock are caught.
410 */
411
ldap_pvt_thread_rdwr_readers(ldap_pvt_thread_rdwr_t * rwlock)412 int ldap_pvt_thread_rdwr_readers(ldap_pvt_thread_rdwr_t *rwlock)
413 {
414 struct ldap_int_thread_rdwr_s *rw;
415
416 assert( rwlock != NULL );
417 rw = *rwlock;
418
419 assert( rw != NULL );
420 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
421 assert( rw->ltrw_w_active >= 0 );
422 assert( rw->ltrw_w_wait >= 0 );
423 assert( rw->ltrw_r_active >= 0 );
424 assert( rw->ltrw_r_wait >= 0 );
425
426 return( rw->ltrw_r_active );
427 }
428
ldap_pvt_thread_rdwr_writers(ldap_pvt_thread_rdwr_t * rwlock)429 int ldap_pvt_thread_rdwr_writers(ldap_pvt_thread_rdwr_t *rwlock)
430 {
431 struct ldap_int_thread_rdwr_s *rw;
432
433 assert( rwlock != NULL );
434 rw = *rwlock;
435
436 assert( rw != NULL );
437 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
438 assert( rw->ltrw_w_active >= 0 );
439 assert( rw->ltrw_w_wait >= 0 );
440 assert( rw->ltrw_r_active >= 0 );
441 assert( rw->ltrw_r_wait >= 0 );
442
443 return( rw->ltrw_w_active );
444 }
445
ldap_pvt_thread_rdwr_active(ldap_pvt_thread_rdwr_t * rwlock)446 int ldap_pvt_thread_rdwr_active(ldap_pvt_thread_rdwr_t *rwlock)
447 {
448 struct ldap_int_thread_rdwr_s *rw;
449
450 assert( rwlock != NULL );
451 rw = *rwlock;
452
453 assert( rw != NULL );
454 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
455 assert( rw->ltrw_w_active >= 0 );
456 assert( rw->ltrw_w_wait >= 0 );
457 assert( rw->ltrw_r_active >= 0 );
458 assert( rw->ltrw_r_wait >= 0 );
459
460 return(ldap_pvt_thread_rdwr_readers(rwlock) +
461 ldap_pvt_thread_rdwr_writers(rwlock));
462 }
463
464 #endif /* LDAP_RDWR_DEBUG */
465
466 #endif /* LDAP_THREAD_HAVE_RDWR */
467
468 #endif /* LDAP_R_COMPILE */
469