]> git.sur5r.net Git - openldap/blob - libraries/libldap_r/rdwr.c
Merge remote branch 'origin/mdb.master'
[openldap] / libraries / libldap_r / rdwr.c
1 /* $OpenLDAP$ */
2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
3  *
4  * Copyright 1998-2012 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 
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 
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
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
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
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
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
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
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
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
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
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 */