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