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 publically 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 #include "ldap_pvt_thread.h" /* Get the thread interface */
44 #define LDAP_THREAD_RDWR_IMPLEMENTATION
45 #include "ldap_thr_debug.h" /* May rename the symbols defined below */
46
47 /*
48 * implementations that provide their own compatible
49 * reader/writer locks define LDAP_THREAD_HAVE_RDWR
50 * in ldap_pvt_thread.h
51 */
52 #ifndef LDAP_THREAD_HAVE_RDWR
53
54 struct ldap_int_thread_rdwr_s {
55 ldap_pvt_thread_mutex_t ltrw_mutex;
56 ldap_pvt_thread_cond_t ltrw_read; /* wait for read */
57 ldap_pvt_thread_cond_t ltrw_write; /* wait for write */
58 int ltrw_valid;
59 #define LDAP_PVT_THREAD_RDWR_VALID 0x0bad
60 int ltrw_r_active;
61 int ltrw_w_active;
62 int ltrw_r_wait;
63 int ltrw_w_wait;
64 #ifdef LDAP_RDWR_DEBUG
65 /* keep track of who has these locks */
66 #define MAX_READERS 32
67 int ltrw_more_readers; /* Set if ltrw_readers[] is incomplete */
68 ldap_pvt_thread_t ltrw_readers[MAX_READERS];
69 ldap_pvt_thread_t ltrw_writer;
70 #endif
71 };
72
73 int
ldap_pvt_thread_rdwr_init(ldap_pvt_thread_rdwr_t * rwlock)74 ldap_pvt_thread_rdwr_init( ldap_pvt_thread_rdwr_t *rwlock )
75 {
76 struct ldap_int_thread_rdwr_s *rw;
77
78 assert( rwlock != NULL );
79
80 rw = (struct ldap_int_thread_rdwr_s *) LDAP_CALLOC( 1,
81 sizeof( struct ldap_int_thread_rdwr_s ) );
82 if ( !rw )
83 return LDAP_NO_MEMORY;
84
85 /* we should check return results */
86 ldap_pvt_thread_mutex_init( &rw->ltrw_mutex );
87 ldap_pvt_thread_cond_init( &rw->ltrw_read );
88 ldap_pvt_thread_cond_init( &rw->ltrw_write );
89
90 rw->ltrw_valid = LDAP_PVT_THREAD_RDWR_VALID;
91
92 *rwlock = rw;
93 return 0;
94 }
95
96 int
ldap_pvt_thread_rdwr_destroy(ldap_pvt_thread_rdwr_t * rwlock)97 ldap_pvt_thread_rdwr_destroy( ldap_pvt_thread_rdwr_t *rwlock )
98 {
99 struct ldap_int_thread_rdwr_s *rw;
100
101 assert( rwlock != NULL );
102 rw = *rwlock;
103
104 assert( rw != NULL );
105 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
106
107 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
108 return LDAP_PVT_THREAD_EINVAL;
109
110 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
111
112 assert( rw->ltrw_w_active >= 0 );
113 assert( rw->ltrw_w_wait >= 0 );
114 assert( rw->ltrw_r_active >= 0 );
115 assert( rw->ltrw_r_wait >= 0 );
116
117 /* active threads? */
118 if( rw->ltrw_r_active > 0 || rw->ltrw_w_active > 0) {
119 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
120 return LDAP_PVT_THREAD_EBUSY;
121 }
122
123 /* waiting threads? */
124 if( rw->ltrw_r_wait > 0 || rw->ltrw_w_wait > 0) {
125 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
126 return LDAP_PVT_THREAD_EBUSY;
127 }
128
129 rw->ltrw_valid = 0;
130
131 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
132
133 ldap_pvt_thread_mutex_destroy( &rw->ltrw_mutex );
134 ldap_pvt_thread_cond_destroy( &rw->ltrw_read );
135 ldap_pvt_thread_cond_destroy( &rw->ltrw_write );
136
137 LDAP_FREE(rw);
138 *rwlock = NULL;
139 return 0;
140 }
141
ldap_pvt_thread_rdwr_rlock(ldap_pvt_thread_rdwr_t * rwlock)142 int ldap_pvt_thread_rdwr_rlock( ldap_pvt_thread_rdwr_t *rwlock )
143 {
144 struct ldap_int_thread_rdwr_s *rw;
145
146 assert( rwlock != NULL );
147 rw = *rwlock;
148
149 assert( rw != NULL );
150 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
151
152 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
153 return LDAP_PVT_THREAD_EINVAL;
154
155 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
156
157 assert( rw->ltrw_w_active >= 0 );
158 assert( rw->ltrw_w_wait >= 0 );
159 assert( rw->ltrw_r_active >= 0 );
160 assert( rw->ltrw_r_wait >= 0 );
161
162 if( rw->ltrw_w_active > 0 ) {
163 /* writer is active */
164
165 rw->ltrw_r_wait++;
166
167 do {
168 ldap_pvt_thread_cond_wait(
169 &rw->ltrw_read, &rw->ltrw_mutex );
170 } while( rw->ltrw_w_active > 0 );
171
172 rw->ltrw_r_wait--;
173 assert( rw->ltrw_r_wait >= 0 );
174 }
175
176 #ifdef LDAP_RDWR_DEBUG
177 if( rw->ltrw_r_active < MAX_READERS )
178 rw->ltrw_readers[rw->ltrw_r_active] = ldap_pvt_thread_self();
179 else
180 rw->ltrw_more_readers = 1;
181 #endif
182 rw->ltrw_r_active++;
183
184
185 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
186
187 return 0;
188 }
189
ldap_pvt_thread_rdwr_rtrylock(ldap_pvt_thread_rdwr_t * rwlock)190 int ldap_pvt_thread_rdwr_rtrylock( ldap_pvt_thread_rdwr_t *rwlock )
191 {
192 struct ldap_int_thread_rdwr_s *rw;
193
194 assert( rwlock != NULL );
195 rw = *rwlock;
196
197 assert( rw != NULL );
198 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
199
200 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
201 return LDAP_PVT_THREAD_EINVAL;
202
203 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
204
205 assert( rw->ltrw_w_active >= 0 );
206 assert( rw->ltrw_w_wait >= 0 );
207 assert( rw->ltrw_r_active >= 0 );
208 assert( rw->ltrw_r_wait >= 0 );
209
210 if( rw->ltrw_w_active > 0) {
211 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
212 return LDAP_PVT_THREAD_EBUSY;
213 }
214
215 #ifdef LDAP_RDWR_DEBUG
216 if( rw->ltrw_r_active < MAX_READERS )
217 rw->ltrw_readers[rw->ltrw_r_active] = ldap_pvt_thread_self();
218 else
219 rw->ltrw_more_readers = 1;
220 #endif
221 rw->ltrw_r_active++;
222
223 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
224
225 return 0;
226 }
227
ldap_pvt_thread_rdwr_runlock(ldap_pvt_thread_rdwr_t * rwlock)228 int ldap_pvt_thread_rdwr_runlock( ldap_pvt_thread_rdwr_t *rwlock )
229 {
230 struct ldap_int_thread_rdwr_s *rw;
231
232 assert( rwlock != NULL );
233 rw = *rwlock;
234
235 assert( rw != NULL );
236 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
237
238 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
239 return LDAP_PVT_THREAD_EINVAL;
240
241 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
242
243 rw->ltrw_r_active--;
244 #ifdef LDAP_RDWR_DEBUG
245 /* Remove us from the list of readers */
246 {
247 ldap_pvt_thread_t self = ldap_pvt_thread_self();
248 int i, j;
249 for( i = j = rw->ltrw_r_active; i >= 0; i--) {
250 if (rw->ltrw_readers[i] == self) {
251 rw->ltrw_readers[i] = rw->ltrw_readers[j];
252 rw->ltrw_readers[j] = 0;
253 break;
254 }
255 }
256 if( !rw->ltrw_more_readers )
257 assert( i >= 0 );
258 else if( j == 0 )
259 rw->ltrw_more_readers = 0;
260 }
261 #endif
262
263 assert( rw->ltrw_w_active >= 0 );
264 assert( rw->ltrw_w_wait >= 0 );
265 assert( rw->ltrw_r_active >= 0 );
266 assert( rw->ltrw_r_wait >= 0 );
267
268 if (rw->ltrw_r_active == 0 && rw->ltrw_w_wait > 0 ) {
269 ldap_pvt_thread_cond_signal( &rw->ltrw_write );
270 }
271
272 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
273
274 return 0;
275 }
276
ldap_pvt_thread_rdwr_wlock(ldap_pvt_thread_rdwr_t * rwlock)277 int ldap_pvt_thread_rdwr_wlock( ldap_pvt_thread_rdwr_t *rwlock )
278 {
279 struct ldap_int_thread_rdwr_s *rw;
280
281 assert( rwlock != NULL );
282 rw = *rwlock;
283
284 assert( rw != NULL );
285 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
286
287 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
288 return LDAP_PVT_THREAD_EINVAL;
289
290 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
291
292 assert( rw->ltrw_w_active >= 0 );
293 assert( rw->ltrw_w_wait >= 0 );
294 assert( rw->ltrw_r_active >= 0 );
295 assert( rw->ltrw_r_wait >= 0 );
296
297 if ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 ) {
298 rw->ltrw_w_wait++;
299
300 do {
301 ldap_pvt_thread_cond_wait(
302 &rw->ltrw_write, &rw->ltrw_mutex );
303 } while ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 );
304
305 rw->ltrw_w_wait--;
306 assert( rw->ltrw_w_wait >= 0 );
307 }
308
309 #ifdef LDAP_RDWR_DEBUG
310 rw->ltrw_writer = ldap_pvt_thread_self();
311 #endif
312 rw->ltrw_w_active++;
313
314 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
315
316 return 0;
317 }
318
ldap_pvt_thread_rdwr_wtrylock(ldap_pvt_thread_rdwr_t * rwlock)319 int ldap_pvt_thread_rdwr_wtrylock( ldap_pvt_thread_rdwr_t *rwlock )
320 {
321 struct ldap_int_thread_rdwr_s *rw;
322
323 assert( rwlock != NULL );
324 rw = *rwlock;
325
326 assert( rw != NULL );
327 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
328
329 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
330 return LDAP_PVT_THREAD_EINVAL;
331
332 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
333
334 assert( rw->ltrw_w_active >= 0 );
335 assert( rw->ltrw_w_wait >= 0 );
336 assert( rw->ltrw_r_active >= 0 );
337 assert( rw->ltrw_r_wait >= 0 );
338
339 if ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 ) {
340 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
341 return LDAP_PVT_THREAD_EBUSY;
342 }
343
344 #ifdef LDAP_RDWR_DEBUG
345 rw->ltrw_writer = ldap_pvt_thread_self();
346 #endif
347 rw->ltrw_w_active++;
348
349 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
350
351 return 0;
352 }
353
ldap_pvt_thread_rdwr_wunlock(ldap_pvt_thread_rdwr_t * rwlock)354 int ldap_pvt_thread_rdwr_wunlock( ldap_pvt_thread_rdwr_t *rwlock )
355 {
356 struct ldap_int_thread_rdwr_s *rw;
357
358 assert( rwlock != NULL );
359 rw = *rwlock;
360
361 assert( rw != NULL );
362 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
363
364 if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
365 return LDAP_PVT_THREAD_EINVAL;
366
367 ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
368
369 rw->ltrw_w_active--;
370
371 assert( rw->ltrw_w_active >= 0 );
372 assert( rw->ltrw_w_wait >= 0 );
373 assert( rw->ltrw_r_active >= 0 );
374 assert( rw->ltrw_r_wait >= 0 );
375
376 if (rw->ltrw_r_wait > 0) {
377 ldap_pvt_thread_cond_broadcast( &rw->ltrw_read );
378
379 } else if (rw->ltrw_w_wait > 0) {
380 ldap_pvt_thread_cond_signal( &rw->ltrw_write );
381 }
382
383 #ifdef LDAP_RDWR_DEBUG
384 assert( rw->ltrw_writer == ldap_pvt_thread_self() );
385 rw->ltrw_writer = 0;
386 #endif
387 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
388
389 return 0;
390 }
391
392 #ifdef LDAP_RDWR_DEBUG
393
394 /* just for testing,
395 * return 0 if false, suitable for assert(ldap_pvt_thread_rdwr_Xchk(rdwr))
396 *
397 * Currently they don't check if the calling thread is the one
398 * that has the lock, just that there is a reader or writer.
399 *
400 * Basically sufficent for testing that places that should have
401 * a lock are caught.
402 */
403
ldap_pvt_thread_rdwr_readers(ldap_pvt_thread_rdwr_t * rwlock)404 int ldap_pvt_thread_rdwr_readers(ldap_pvt_thread_rdwr_t *rwlock)
405 {
406 struct ldap_int_thread_rdwr_s *rw;
407
408 assert( rwlock != NULL );
409 rw = *rwlock;
410
411 assert( rw != NULL );
412 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
413 assert( rw->ltrw_w_active >= 0 );
414 assert( rw->ltrw_w_wait >= 0 );
415 assert( rw->ltrw_r_active >= 0 );
416 assert( rw->ltrw_r_wait >= 0 );
417
418 return( rw->ltrw_r_active );
419 }
420
ldap_pvt_thread_rdwr_writers(ldap_pvt_thread_rdwr_t * rwlock)421 int ldap_pvt_thread_rdwr_writers(ldap_pvt_thread_rdwr_t *rwlock)
422 {
423 struct ldap_int_thread_rdwr_s *rw;
424
425 assert( rwlock != NULL );
426 rw = *rwlock;
427
428 assert( rw != NULL );
429 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
430 assert( rw->ltrw_w_active >= 0 );
431 assert( rw->ltrw_w_wait >= 0 );
432 assert( rw->ltrw_r_active >= 0 );
433 assert( rw->ltrw_r_wait >= 0 );
434
435 return( rw->ltrw_w_active );
436 }
437
ldap_pvt_thread_rdwr_active(ldap_pvt_thread_rdwr_t * rwlock)438 int ldap_pvt_thread_rdwr_active(ldap_pvt_thread_rdwr_t *rwlock)
439 {
440 struct ldap_int_thread_rdwr_s *rw;
441
442 assert( rwlock != NULL );
443 rw = *rwlock;
444
445 assert( rw != NULL );
446 assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
447 assert( rw->ltrw_w_active >= 0 );
448 assert( rw->ltrw_w_wait >= 0 );
449 assert( rw->ltrw_r_active >= 0 );
450 assert( rw->ltrw_r_wait >= 0 );
451
452 return(ldap_pvt_thread_rdwr_readers(rwlock) +
453 ldap_pvt_thread_rdwr_writers(rwlock));
454 }
455
456 #endif /* LDAP_RDWR_DEBUG */
457
458 #endif /* LDAP_THREAD_HAVE_RDWR */
459