]> git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/cache.c
cleanup & more
[openldap] / servers / slapd / back-bdb / cache.c
1 /* cache.c - routines to maintain an in-core cache of entries */
2 /* $OpenLDAP$ */
3 /*
4  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
6  */
7
8 #include "portable.h"
9
10 #include <stdio.h>
11
12 #include <ac/errno.h>
13 #include <ac/string.h>
14 #include <ac/socket.h>
15
16 #include "slap.h"
17
18 #include "back-bdb.h"
19
20 /* BDB backend specific entry info -- visible only to the cache */
21 typedef struct bdb_entry_info {
22 #if 0
23         ldap_pvt_thread_rdwr_t  bei_rdwr;       /* reader/writer lock */
24 #endif
25
26         /*
27          * remaining fields require backend cache lock to access
28          * These items are specific to the BDB backend and should
29          * be hidden.
30          */
31         int             bei_state;      /* for the cache */
32 #define CACHE_ENTRY_UNDEFINED   0
33 #define CACHE_ENTRY_CREATING    1
34 #define CACHE_ENTRY_READY       2
35 #define CACHE_ENTRY_DELETED     3
36 #define CACHE_ENTRY_COMMITTED   4
37         
38         int             bei_refcnt;     /* # threads ref'ing this entry */
39         Entry   *bei_lrunext;   /* for cache lru list */
40         Entry   *bei_lruprev;
41 } EntryInfo;
42 #undef BEI
43 #define BEI(e)  ((EntryInfo *) ((e)->e_private))
44
45 static int      bdb_cache_delete_entry_internal(Cache *cache, Entry *e);
46 #ifdef LDAP_DEBUG
47 static void     bdb_lru_print(Cache *cache);
48 #endif
49
50 #if 0   /* unused */
51 static int
52 bdb_cache_entry_rdwr_lock(Entry *e, int rw)
53 {
54 #ifdef NEW_LOGGING
55         LDAP_LOG( CACHE, ENTRY, 
56                 "bdb_cache_entry_rdwr_lock: %s lock on ID %ld\n",
57                 rw ? "w" : "r", e->e_id, 0 );
58 #else
59         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
60                 rw ? "w" : "r", e->e_id, 0);
61 #endif
62
63         if (rw)
64                 return ldap_pvt_thread_rdwr_wlock(&BEI(e)->bei_rdwr);
65         else
66                 return ldap_pvt_thread_rdwr_rlock(&BEI(e)->bei_rdwr);
67 }
68
69 static int
70 bdb_cache_entry_rdwr_trylock(Entry *e, int rw)
71 {
72 #ifdef NEW_LOGGING
73         LDAP_LOG( CACHE, ENTRY, 
74                 "bdb_cache_entry_rdwr_trylock: try %s lock on ID: %ld.\n",
75                 rw ? "w" : "r", e->e_id, 0 );
76 #else
77         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
78                 rw ? "w" : "r", e->e_id, 0);
79 #endif
80
81         if (rw)
82                 return ldap_pvt_thread_rdwr_wtrylock(&BEI(e)->bei_rdwr);
83         else
84                 return ldap_pvt_thread_rdwr_rtrylock(&BEI(e)->bei_rdwr);
85 }
86
87 static int
88 bdb_cache_entry_rdwr_unlock(Entry *e, int rw)
89 {
90 #ifdef NEW_LOGGING
91         LDAP_LOG( CACHE, ENTRY, 
92                 "bdb_cache_entry_rdwr_unlock: remove %s lock on ID %ld.\n",
93                 rw ? "w" : "r", e->e_id, 0 );
94 #else
95         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
96                 rw ? "w" : "r", e->e_id, 0);
97 #endif
98
99         if (rw)
100                 return ldap_pvt_thread_rdwr_wunlock(&BEI(e)->bei_rdwr);
101         else
102                 return ldap_pvt_thread_rdwr_runlock(&BEI(e)->bei_rdwr);
103 }
104 #endif  /* unused */
105
106 #if 0
107 static int
108 bdb_cache_entry_rdwr_init(Entry *e)
109 {
110         return ldap_pvt_thread_rdwr_init( &BEI(e)->bei_rdwr );
111 }
112
113 static int
114 bdb_cache_entry_rdwr_destroy(Entry *e)
115 {
116         return ldap_pvt_thread_rdwr_destroy( &BEI(e)->bei_rdwr );
117 }
118 #endif
119
120 static int
121 bdb_cache_entry_private_init( Entry *e )
122 {
123         assert( e->e_private == NULL );
124
125         if( e->e_private != NULL ) {
126                 /* this should never happen */
127                 return 1;
128         }
129
130         e->e_private = ch_calloc(1, sizeof(struct bdb_entry_info));
131
132 #if 0
133         if( bdb_cache_entry_rdwr_init( e ) != 0 ) {
134                 free( BEI(e) );
135                 e->e_private = NULL;
136                 return 1;
137         } 
138 #endif
139
140         return 0;
141 }
142
143 int
144 bdb_cache_entry_db_lock
145 ( DB_ENV *env, u_int32_t locker, Entry *e, int rw, u_int32_t flags, DB_LOCK *lock )
146 {
147 #ifdef NO_THREADS
148         return 0;
149 #else
150         int       rc;
151         DBT       lockobj;
152         int       db_rw;
153
154         if (rw)
155                 db_rw = DB_LOCK_WRITE;
156         else
157                 db_rw = DB_LOCK_READ;
158
159         lockobj.data = e->e_nname.bv_val;
160         lockobj.size = e->e_nname.bv_len;
161         rc = LOCK_GET(env, locker, flags | DB_LOCK_NOWAIT,
162                                         &lockobj, db_rw, lock);
163         if (rc) {
164 #ifdef NEW_LOGGING
165                 LDAP_LOG( CACHE, DETAIL1, 
166                         "bdb_cache_entry_db_lock: entry %s, rw %d, rc %d\n",
167                         e->e_nname.bv_val, rw, rc );
168 #else
169                 Debug( LDAP_DEBUG_TRACE,
170                         "bdb_cache_entry_db_lock: entry %s, rw %d, rc %d\n",
171                         e->e_nname.bv_val, rw, rc );
172 #endif
173         }
174         return rc;
175 #endif /* NO_THREADS */
176 }
177
178 int
179 bdb_cache_entry_db_unlock
180 ( DB_ENV *env, DB_LOCK *lock )
181 {
182 #ifdef NO_THREADS
183         return 0;
184 #else
185         int rc;
186
187         rc = LOCK_PUT ( env, lock );
188         return rc;
189 #endif
190 }
191
192 /*
193  * marks an entry in CREATING state as committed, so it is really returned
194  * to the cache. Otherwise an entry in CREATING state is removed.
195  * Makes e_private be destroyed at the following cache_return_entry_w,
196  * but lets the entry untouched (owned by someone else)
197  */
198 void
199 bdb_cache_entry_commit( Entry *e )
200 {
201         assert( e );
202         assert( e->e_private );
203         assert( BEI(e)->bei_state == CACHE_ENTRY_CREATING );
204         /* assert( BEI(e)->bei_refcnt == 1 ); */
205
206         BEI(e)->bei_state = CACHE_ENTRY_COMMITTED;
207 }
208
209 static int
210 bdb_cache_entry_private_destroy( Entry *e )
211 {
212         assert( e->e_private );
213
214 #if 0
215         bdb_cache_entry_rdwr_destroy( e );
216 #endif
217
218         free( e->e_private );
219         e->e_private = NULL;
220         return 0;
221 }
222
223 void
224 bdb_unlocked_cache_return_entry_rw( Cache *cache, Entry *e, int rw )
225 {
226
227         ID id;
228         int refcnt, freeit = 1;
229
230         /* set cache write lock */
231         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
232
233         assert( e->e_private );
234
235 #if 0
236         bdb_cache_entry_rdwr_unlock(e, rw);
237 #endif
238
239         id = e->e_id;
240         refcnt = --BEI(e)->bei_refcnt;
241
242         /*
243          * if the entry is returned when in CREATING state, it is deleted
244          * but not freed because it may belong to someone else (do_add,
245          * for instance)
246          */
247         if (  BEI(e)->bei_state == CACHE_ENTRY_CREATING ) {
248                 /* set lru mutex */
249                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
250                 bdb_cache_delete_entry_internal( cache, e );
251                 /* free lru mutex */
252                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
253                 freeit = 0;
254                 /* now the entry is in DELETED state */
255         }
256
257         if ( BEI(e)->bei_state == CACHE_ENTRY_COMMITTED ) {
258                 BEI(e)->bei_state = CACHE_ENTRY_READY;
259
260                 /* free cache write lock */
261                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
262
263 #ifdef NEW_LOGGING
264                 LDAP_LOG( CACHE, DETAIL1, 
265                            "bdb_unlocked_cache_return_entry_rw: return (%ld):%s, refcnt=%d\n",
266                            id, rw ? "w" : "r", refcnt );
267 #else
268                 Debug( LDAP_DEBUG_TRACE,
269                         "====> bdb_unlocked_cache_return_entry_%s( %ld ): created (%d)\n",
270                         rw ? "w" : "r", id, refcnt );
271 #endif
272
273
274         } else if ( BEI(e)->bei_state == CACHE_ENTRY_DELETED ) {
275                 if( refcnt > 0 ) {
276                         /* free cache write lock */
277                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
278
279 #ifdef NEW_LOGGING
280                         LDAP_LOG( CACHE, DETAIL1, 
281                                    "bdb_unlocked_cache_return_entry_rw: %ld, delete pending (%d).\n",
282                                    id, refcnt, 0 );
283 #else
284                         Debug( LDAP_DEBUG_TRACE,
285                                 "====> bdb_unlocked_cache_return_entry_%s( %ld ): delete pending (%d)\n",
286                                 rw ? "w" : "r", id, refcnt );
287 #endif
288
289                 } else {
290                         bdb_cache_entry_private_destroy( e );
291                         if ( freeit ) {
292                                 bdb_entry_return( e );
293                         }
294
295                         /* free cache write lock */
296                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
297
298 #ifdef NEW_LOGGING
299                         LDAP_LOG( CACHE, DETAIL1, 
300                                    "bdb_unlocked_cache_return_entry_rw: (%ld): deleted (%d)\n",
301                                    id, refcnt, 0 );
302 #else
303                         Debug( LDAP_DEBUG_TRACE,
304                                 "====> bdb_unlocked_cache_return_entry_%s( %ld ): deleted (%d)\n",
305                                 rw ? "w" : "r", id, refcnt );
306 #endif
307                 }
308
309         } else {
310                 /* free cache write lock */
311                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
312
313 #ifdef NEW_LOGGING
314                 LDAP_LOG( CACHE, DETAIL1, 
315                            "bdb_unlocked_cache_return_entry_rw: ID %ld:%s returned (%d)\n",
316                            id, rw ? "w": "r", refcnt );
317 #else
318                 Debug( LDAP_DEBUG_TRACE,
319                         "====> bdb_unlocked_cache_return_entry_%s( %ld ): returned (%d)\n",
320                         rw ? "w" : "r", id, refcnt);
321 #endif
322         }
323 }
324
325 void
326 bdb_cache_return_entry_rw
327 ( DB_ENV *env, Cache *cache, Entry *e, int rw, DB_LOCK *lock )
328 {
329         ID id;
330         int refcnt, freeit = 1;
331
332         /* set cache write lock */
333         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
334
335         assert( e->e_private );
336
337         bdb_cache_entry_db_unlock( env, lock );
338 #if 0
339         bdb_cache_entry_rdwr_unlock(e, rw);
340 #endif
341
342         id = e->e_id;
343         refcnt = --BEI(e)->bei_refcnt;
344
345         /*
346          * if the entry is returned when in CREATING state, it is deleted
347          * but not freed because it may belong to someone else (do_add,
348          * for instance)
349          */
350         if (  BEI(e)->bei_state == CACHE_ENTRY_CREATING ) {
351                 /* set lru mutex */
352                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
353                 bdb_cache_delete_entry_internal( cache, e );
354                 /* free lru mutex */
355                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
356                 freeit = 0;
357                 /* now the entry is in DELETED state */
358         }
359
360         if ( BEI(e)->bei_state == CACHE_ENTRY_COMMITTED ) {
361                 BEI(e)->bei_state = CACHE_ENTRY_READY;
362
363                 /* free cache write lock */
364                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
365
366 #ifdef NEW_LOGGING
367                 LDAP_LOG( CACHE, DETAIL1, 
368                            "bdb_cache_return_entry_rw: return (%ld):%s, refcnt=%d\n",
369                            id, rw ? "w" : "r", refcnt );
370 #else
371                 Debug( LDAP_DEBUG_TRACE,
372                         "====> bdb_cache_return_entry_%s( %ld ): created (%d)\n",
373                         rw ? "w" : "r", id, refcnt );
374 #endif
375
376
377         } else if ( BEI(e)->bei_state == CACHE_ENTRY_DELETED ) {
378                 if( refcnt > 0 ) {
379                         /* free cache write lock */
380                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
381
382 #ifdef NEW_LOGGING
383                         LDAP_LOG( CACHE, DETAIL1, 
384                                    "bdb_cache_return_entry_rw: %ld, delete pending (%d).\n",
385                                    id, refcnt, 0 );
386 #else
387                         Debug( LDAP_DEBUG_TRACE,
388                                 "====> bdb_cache_return_entry_%s( %ld ): delete pending (%d)\n",
389                                 rw ? "w" : "r", id, refcnt );
390 #endif
391
392                 } else {
393                         bdb_cache_entry_private_destroy( e );
394                         if ( freeit ) {
395                                 bdb_entry_return( e );
396                         }
397
398                         /* free cache write lock */
399                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
400
401 #ifdef NEW_LOGGING
402                         LDAP_LOG( CACHE, DETAIL1, 
403                                    "bdb_cache_return_entry_rw: (%ld): deleted (%d)\n",
404                                    id, refcnt, 0 );
405 #else
406                         Debug( LDAP_DEBUG_TRACE,
407                                 "====> bdb_cache_return_entry_%s( %ld ): deleted (%d)\n",
408                                 rw ? "w" : "r", id, refcnt );
409 #endif
410                 }
411
412         } else {
413                 /* free cache write lock */
414                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
415
416 #ifdef NEW_LOGGING
417                 LDAP_LOG( CACHE, DETAIL1, 
418                            "bdb_cache_return_entry_rw: ID %ld:%s returned (%d)\n",
419                            id, rw ? "w": "r", refcnt );
420 #else
421                 Debug( LDAP_DEBUG_TRACE,
422                         "====> bdb_cache_return_entry_%s( %ld ): returned (%d)\n",
423                         rw ? "w" : "r", id, refcnt);
424 #endif
425         }
426 }
427
428 #define LRU_DELETE( cache, e ) do { \
429         if ( BEI(e)->bei_lruprev != NULL ) { \
430                 BEI(BEI(e)->bei_lruprev)->bei_lrunext = BEI(e)->bei_lrunext; \
431         } else { \
432                 (cache)->c_lruhead = BEI(e)->bei_lrunext; \
433         } \
434         if ( BEI(e)->bei_lrunext != NULL ) { \
435                 BEI(BEI(e)->bei_lrunext)->bei_lruprev = BEI(e)->bei_lruprev; \
436         } else { \
437                 (cache)->c_lrutail = BEI(e)->bei_lruprev; \
438         } \
439 } while(0)
440
441 #define LRU_ADD( cache, e ) do { \
442         BEI(e)->bei_lrunext = (cache)->c_lruhead; \
443         if ( BEI(e)->bei_lrunext != NULL ) { \
444                 BEI(BEI(e)->bei_lrunext)->bei_lruprev = (e); \
445         } \
446         (cache)->c_lruhead = (e); \
447         BEI(e)->bei_lruprev = NULL; \
448         if ( (cache)->c_lrutail == NULL ) { \
449                 (cache)->c_lrutail = (e); \
450         } \
451 } while(0)
452
453 /*
454  * cache_add_entry_rw - create and lock an entry in the cache
455  * returns:     0       entry has been created and locked
456  *              1       entry already existed
457  *              -1      something bad happened
458  *             other    Berkeley DB locking error code
459  */
460 int
461 bdb_cache_add_entry_rw(
462     DB_ENV      *env,
463     Cache       *cache,
464     Entry       *e,
465     int         rw,
466     u_int32_t   locker,
467     DB_LOCK     *lock
468 )
469 {
470         int     i, rc;
471         Entry   *ee;
472
473 #ifdef NEW_LOGGING
474         LDAP_LOG( CACHE, ENTRY, 
475                 "bdb_cache_add_entry_rw: add (%s):%s to cache\n",
476                 e->e_dn, rw ? "w" : "r", 0 );
477 #endif
478         /* set cache write lock */
479         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
480
481         assert( e->e_private == NULL );
482
483         if( bdb_cache_entry_private_init(e) != 0 ) {
484                 /* free cache write lock */
485                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
486
487 #ifdef NEW_LOGGING
488                 LDAP_LOG( CACHE, ERR, 
489                         "bdb_cache_add_entry_rw: add (%s):%ld private init failed!\n",
490                         e->e_dn, e->e_id, 0 );
491 #else
492                 Debug( LDAP_DEBUG_ANY,
493                         "====> bdb_cache_add_entry( %ld ): \"%s\": private init failed!\n",
494                     e->e_id, e->e_dn, 0 );
495 #endif
496
497
498                 return( -1 );
499         }
500
501         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
502                          entry_dn_cmp, avl_dup_error ) != 0 )
503         {
504                 /* free cache write lock */
505                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
506
507 #ifdef NEW_LOGGING
508                 LDAP_LOG( CACHE, DETAIL1, 
509                         "bdb_cache_add_entry: (%s):%ld already in cache.\n",
510                         e->e_dn, e->e_id, 0 );
511 #else
512                 Debug( LDAP_DEBUG_TRACE,
513                         "====> bdb_cache_add_entry( %ld ): \"%s\": already in dn cache\n",
514                     e->e_id, e->e_dn, 0 );
515 #endif
516
517                 bdb_cache_entry_private_destroy(e);
518
519                 return( 1 );
520         }
521
522         /* id tree */
523         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
524                          entry_id_cmp, avl_dup_error ) != 0 )
525         {
526 #ifdef NEW_LOGGING
527                 LDAP_LOG( CACHE, DETAIL1, 
528                         "bdb_cache_add_entry: (%s):%ls already in cache.\n",
529                         e->e_dn, e->e_id, 0 );
530 #else
531                 Debug( LDAP_DEBUG_ANY,
532                         "====> bdb_cache_add_entry( %ld ): \"%s\": already in id cache\n",
533                     e->e_id, e->e_dn, 0 );
534 #endif
535
536                 /* delete from dn tree inserted above */
537                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
538                                  entry_dn_cmp ) == NULL )
539                 {
540 #ifdef NEW_LOGGING
541                         LDAP_LOG( CACHE, INFO, 
542                                 "bdb_cache_add_entry: can't delete (%s) from cache.\n", 
543                                 e->e_dn, 0, 0 );
544 #else
545                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
546                             0, 0, 0 );
547 #endif
548                 }
549
550                 bdb_cache_entry_private_destroy(e);
551
552                 /* free cache write lock */
553                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
554                 return( -1 );
555         }
556
557         rc = bdb_cache_entry_db_lock( env, locker, e, rw, 0, lock );
558         switch ( rc ) {
559         case 0 :
560                 break;
561         case DB_LOCK_DEADLOCK :
562         case DB_LOCK_NOTGRANTED :
563                 /* undo avl changes immediately */
564                 if ( avl_delete( &cache->c_idtree, (caddr_t) e,
565                                  entry_id_cmp ) == NULL ) {
566 #ifdef NEW_LOGGING
567                         LDAP_LOG( CACHE, INFO, 
568                                 "bdb_cache_add_entry: can't delete (%s) from cache.\n", 
569                                 e->e_dn, 0, 0 );
570 #else
571                         Debug( LDAP_DEBUG_ANY, "====> can't delete from id cache\n", 0, 0, 0 );
572 #endif
573                 }
574                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
575                                  entry_dn_cmp ) == NULL ) {
576 #ifdef NEW_LOGGING
577                         LDAP_LOG( CACHE, INFO, 
578                                 "bdb_cache_add_entry: can't delete (%s) from cache.\n", 
579                                 e->e_dn, 0, 0 );
580 #else
581                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n", 0, 0, 0 );
582 #endif
583                 }
584                 /* fall through */
585         default :
586                 bdb_cache_entry_private_destroy(e);
587                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
588                 return rc;
589         }
590
591         /* put the entry into 'CREATING' state */
592         /* will be marked after when entry is returned */
593         BEI(e)->bei_state = CACHE_ENTRY_CREATING;
594         BEI(e)->bei_refcnt = 1;
595
596         /* set lru mutex */
597         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
598         /* lru */
599         LRU_ADD( cache, e );
600         if ( ++cache->c_cursize > cache->c_maxsize ) {
601                 /*
602                  * find the lru entry not currently in use and delete it.
603                  * in case a lot of entries are in use, only look at the
604                  * first 10 on the tail of the list.
605                  */
606                 i = 0;
607                 while ( cache->c_lrutail != NULL &&
608                         BEI(cache->c_lrutail)->bei_refcnt != 0 &&
609                         i < 10 )
610                 {
611                         /* move this in-use entry to the front of the q */
612                         ee = cache->c_lrutail;
613                         LRU_DELETE( cache, ee );
614                         LRU_ADD( cache, ee );
615                         i++;
616                 }
617
618                 /*
619                  * found at least one to delete - try to get back under
620                  * the max cache size.
621                  */
622                 while ( cache->c_lrutail != NULL &&
623                         BEI(cache->c_lrutail)->bei_refcnt == 0 &&
624                         cache->c_cursize > cache->c_maxsize )
625                 {
626                         e = cache->c_lrutail;
627
628                         /* delete from cache and lru q */
629                         /* XXX do we need rc ? */
630                         rc = bdb_cache_delete_entry_internal( cache, e );
631                         bdb_cache_entry_private_destroy( e );
632                         bdb_entry_return( e );
633                 }
634         }
635
636         /* free lru mutex */
637         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
638         /* free cache write lock */
639         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
640         return( 0 );
641 }
642
643 /*
644  * cache_update_entry - update a LOCKED entry which has been deleted.
645  * returns:     0       entry has been created and locked
646  *              1       entry already existed
647  *              -1      something bad happened
648  */
649 int
650 bdb_cache_update_entry(
651     Cache       *cache,
652     Entry               *e
653 )
654 {
655         int     i, rc;
656         Entry   *ee;
657
658         /* set cache write lock */
659         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
660
661         assert( e->e_private );
662
663         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
664                          entry_dn_cmp, avl_dup_error ) != 0 )
665         {
666 #ifdef NEW_LOGGING
667                 LDAP_LOG( CACHE, DETAIL1, 
668                         "bdb_cache_update_entry: (%s):%ld already in dn cache\n",
669                         e->e_dn, e->e_id, 0 );
670 #else
671                 Debug( LDAP_DEBUG_TRACE,
672                         "====> bdb_cache_update_entry( %ld ): \"%s\": already in dn cache\n",
673                     e->e_id, e->e_dn, 0 );
674 #endif
675
676                 /* free cache write lock */
677                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
678                 return( 1 );
679         }
680
681         /* id tree */
682         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
683                          entry_id_cmp, avl_dup_error ) != 0 )
684         {
685 #ifdef NEW_LOGGING
686                 LDAP_LOG( CACHE, DETAIL1, 
687                         "bdb_cache_update_entry: (%s)%ld already in id cache\n",
688                         e->e_dn, e->e_id, 0 );
689 #else
690                 Debug( LDAP_DEBUG_ANY,
691                         "====> bdb_cache_update_entry( %ld ): \"%s\": already in id cache\n",
692                     e->e_id, e->e_dn, 0 );
693 #endif
694
695                 /* delete from dn tree inserted above */
696                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
697                                  entry_dn_cmp ) == NULL )
698                 {
699 #ifdef NEW_LOGGING
700                         LDAP_LOG( CACHE, INFO, 
701                                 "bdb_cache_update_entry: can't delete (%s)%ld from dn cache.\n",
702                                 e->e_dn, e->e_id, 0 );
703 #else
704                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
705                             0, 0, 0 );
706 #endif
707                 }
708
709                 /* free cache write lock */
710                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
711                 return( -1 );
712         }
713
714
715         /* put the entry into 'CREATING' state */
716         /* will be marked after when entry is returned */
717         BEI(e)->bei_state = CACHE_ENTRY_CREATING;
718
719         /* set lru mutex */
720         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
721         /* lru */
722         LRU_ADD( cache, e );
723         if ( ++cache->c_cursize > cache->c_maxsize ) {
724                 /*
725                  * find the lru entry not currently in use and delete it.
726                  * in case a lot of entries are in use, only look at the
727                  * first 10 on the tail of the list.
728                  */
729                 i = 0;
730                 while ( cache->c_lrutail != NULL &&
731                         BEI(cache->c_lrutail)->bei_refcnt != 0 &&
732                         i < 10 )
733                 {
734                         /* move this in-use entry to the front of the q */
735                         ee = cache->c_lrutail;
736                         LRU_DELETE( cache, ee );
737                         LRU_ADD( cache, ee );
738                         i++;
739                 }
740
741                 /*
742                  * found at least one to delete - try to get back under
743                  * the max cache size.
744                  */
745                 while ( cache->c_lrutail != NULL &&
746                         BEI(cache->c_lrutail)->bei_refcnt == 0 &&
747                         cache->c_cursize > cache->c_maxsize )
748                 {
749                         e = cache->c_lrutail;
750
751                         /* delete from cache and lru q */
752                         /* XXX do we need rc ? */
753                         rc = bdb_cache_delete_entry_internal( cache, e );
754                         bdb_cache_entry_private_destroy( e );
755                         bdb_entry_return( e );
756                 }
757         }
758
759         /* free lru mutex */
760         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
761         /* free cache write lock */
762         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
763         return( 0 );
764 }
765
766 ID
767 bdb_cache_find_entry_ndn2id(
768         Backend         *be,
769     Cache       *cache,
770     struct berval       *ndn
771 )
772 {
773         Entry           e, *ep;
774         ID                      id;
775         int count = 0;
776
777         /* this function is always called with normalized DN */
778         e.e_nname = *ndn;
779
780 try_again:
781         /* set cache read lock */
782         ldap_pvt_thread_rdwr_rlock( &cache->c_rwlock );
783
784         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
785                                        entry_dn_cmp )) != NULL )
786         {
787                 int state;
788                 count++;
789
790                 /*
791                  * ep now points to an unlocked entry
792                  * we do not need to lock the entry if we only
793                  * check the state, refcnt, LRU, and id.
794                  */
795
796                 assert( ep->e_private );
797
798                 /* save id */
799                 id = ep->e_id;
800                 state = BEI(ep)->bei_state;
801
802                 /*
803                  * entry is deleted or not fully created yet
804                  */
805                 if ( state != CACHE_ENTRY_READY && state != CACHE_ENTRY_COMMITTED ) {
806                         assert(state != CACHE_ENTRY_UNDEFINED);
807
808                         /* free cache read lock */
809                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
810
811 #ifdef NEW_LOGGING
812                         LDAP_LOG( CACHE, INFO, 
813                                 "bdb_cache_find_entry_dn2id: (%s) %ld not ready: %d\n",
814                                 ndn->bv_val, id, state );
815 #else
816                         Debug(LDAP_DEBUG_TRACE,
817                                 "====> bdb_cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
818                                 ndn->bv_val, id, state);
819 #endif
820
821
822                         ldap_pvt_thread_yield();
823                         goto try_again;
824                 }
825
826                 /* free cache read lock */
827                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
828
829                 /* set lru mutex */
830                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
831
832                 /* lru */
833                 LRU_DELETE( cache, ep );
834                 LRU_ADD( cache, ep );
835                 
836                 /* free lru mutex */
837                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
838
839 #ifdef NEW_LOGGING
840                 LDAP_LOG( CACHE, DETAIL1, 
841                         "bdb_cache_find_entry_dn2id: (%s): %ld %d tries\n",
842                         ndn->bv_val, id, count );
843 #else
844                 Debug(LDAP_DEBUG_TRACE,
845                         "====> bdb_cache_find_entry_dn2id(\"%s\"): %ld (%d tries)\n",
846                         ndn->bv_val, id, count);
847 #endif
848
849         } else {
850                 /* free cache read lock */
851                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
852
853                 id = NOID;
854         }
855
856         return( id );
857 }
858
859 /*
860  * cache_find_entry_id - find an entry in the cache, given id
861  */
862
863 Entry *
864 bdb_cache_find_entry_id(
865         DB_ENV  *env,
866         Cache   *cache,
867         ID                              id,
868         int                             rw,
869         u_int32_t       locker,
870         DB_LOCK         *lock
871 )
872 {
873         Entry   e;
874         Entry   *ep;
875         int     count = 0;
876         int     rc;
877
878         e.e_id = id;
879
880 try_again:
881         /* set cache read lock */
882         ldap_pvt_thread_rdwr_rlock( &cache->c_rwlock );
883
884         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
885                                        entry_id_cmp )) != NULL )
886         {
887                 int state;
888                 ID      ep_id;
889
890                 count++;
891
892                 assert( ep->e_private );
893
894                 ep_id = ep->e_id; 
895                 state = BEI(ep)->bei_state;
896
897                 /*
898                  * entry is deleted or not fully created yet
899                  */
900                 if ( state != CACHE_ENTRY_READY && state != CACHE_ENTRY_COMMITTED ) {
901
902                         assert(state != CACHE_ENTRY_UNDEFINED);
903
904                         /* free cache read lock */
905                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
906
907 #ifdef NEW_LOGGING
908                         LDAP_LOG( CACHE, INFO, 
909                                 "bdb_cache_find_entry_id: (%ld)->%ld not ready (%d).\n",
910                                 id, ep_id, state );
911                                    
912 #else
913                         Debug(LDAP_DEBUG_TRACE,
914                                 "====> bdb_cache_find_entry_id( %ld ): %ld (not ready) %d\n",
915                                 id, ep_id, state);
916 #endif
917
918                         ldap_pvt_thread_yield();
919                         goto try_again;
920                 }
921
922                 /* acquire reader lock */
923                 rc = bdb_cache_entry_db_lock ( env, locker, ep, rw, 0, lock );
924
925 #if 0
926                 if ( bdb_cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
927 #endif
928
929                 if ( rc ) { /* will be changed to retry beyond threshold */
930                         /* could not acquire entry lock...
931                          * owner cannot free as we have the cache locked.
932                          * so, unlock the cache, yield, and try again.
933                          */
934
935                         /* free cache read lock */
936                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
937
938 #ifdef NEW_LOGGING
939                         LDAP_LOG( CACHE, INFO, 
940                                 "bdb_cache_find_entry_id: %ld -> %ld (busy) %d.\n",
941                                 id, ep_id, state );
942 #else
943                         Debug(LDAP_DEBUG_TRACE,
944                                 "====> bdb_cache_find_entry_id( %ld ): %ld (busy) %d\n",
945                                 id, ep_id, state);
946                         Debug(LDAP_DEBUG_TRACE,
947                                 "locker = %d\n",
948                                 locker, 0, 0);
949 #endif
950
951                         ldap_pvt_thread_yield();
952                         goto try_again;
953                 }
954
955                 /* free cache read lock */
956                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
957                 /* set lru mutex */
958                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
959                 /* lru */
960                 LRU_DELETE( cache, ep );
961                 LRU_ADD( cache, ep );
962                 
963                 BEI(ep)->bei_refcnt++;
964
965                 /* free lru mutex */
966                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
967
968 #ifdef NEW_LOGGING
969                 LDAP_LOG( CACHE, DETAIL1, 
970                         "bdb_cache_find_entry_id: %ld -> %s  found %d tries.\n",
971                         ep_id, ep->e_dn, count );
972 #else
973                 Debug(LDAP_DEBUG_TRACE,
974                         "====> bdb_cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
975                         ep_id, ep->e_dn, count);
976 #endif
977
978
979                 return( ep );
980         }
981
982         /* free cache read lock */
983         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
984
985         return( NULL );
986 }
987
988 /*
989  * cache_delete_entry - delete the entry e from the cache.  the caller
990  * should have obtained e (increasing its ref count) via a call to one
991  * of the cache_find_* routines.  the caller should *not* call the
992  * cache_return_entry() routine prior to calling cache_delete_entry().
993  * it performs this function.
994  *
995  * returns:     0       e was deleted ok
996  *              1       e was not in the cache
997  *              -1      something bad happened
998  */
999 int
1000 bdb_cache_delete_entry(
1001     Cache       *cache,
1002     Entry               *e
1003 )
1004 {
1005         int     rc;
1006
1007         /* set cache write lock */
1008         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
1009
1010         assert( e->e_private );
1011
1012 #ifdef NEW_LOGGING
1013         LDAP_LOG( CACHE, ENTRY, 
1014                 "bdb_cache_delete_entry: delete %ld.\n", e->e_id, 0, 0 );
1015 #else
1016         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_delete_entry( %ld )\n",
1017                 e->e_id, 0, 0 );
1018 #endif
1019
1020         /* set lru mutex */
1021         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
1022         rc = bdb_cache_delete_entry_internal( cache, e );
1023         /* free lru mutex */
1024         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
1025
1026         /* free cache write lock */
1027         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
1028         return( rc );
1029 }
1030
1031 static int
1032 bdb_cache_delete_entry_internal(
1033     Cache       *cache,
1034     Entry               *e
1035 )
1036 {
1037         int rc = 0;     /* return code */
1038
1039         /* dn tree */
1040         if ( avl_delete( &cache->c_dntree, (caddr_t) e, entry_dn_cmp ) == NULL )
1041         {
1042                 rc = -1;
1043         }
1044
1045         /* id tree */
1046         if ( avl_delete( &cache->c_idtree, (caddr_t) e, entry_id_cmp ) == NULL )
1047         {
1048                 rc = -1;
1049         }
1050
1051         if (rc != 0) {
1052                 return rc;
1053         }
1054
1055         /* lru */
1056         LRU_DELETE( cache, e );
1057         cache->c_cursize--;
1058
1059         /*
1060          * flag entry to be freed later by a call to cache_return_entry()
1061          */
1062         BEI(e)->bei_state = CACHE_ENTRY_DELETED;
1063
1064         return( 0 );
1065 }
1066
1067 void
1068 bdb_cache_release_all( Cache *cache )
1069 {
1070         Entry *e;
1071         int rc;
1072
1073         /* set cache write lock */
1074         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
1075         /* set lru mutex */
1076         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
1077
1078 #ifdef NEW_LOGGING
1079         LDAP_LOG( CACHE, ENTRY, "bdb_cache_release_all: enter\n", 0, 0, 0 );
1080 #else
1081         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_release_all\n", 0, 0, 0 );
1082 #endif
1083
1084         while ( (e = cache->c_lrutail) != NULL && BEI(e)->bei_refcnt == 0 ) {
1085 #ifdef LDAP_RDWR_DEBUG
1086                 assert(!ldap_pvt_thread_rdwr_active(&BEI(e)->bei_rdwr));
1087 #endif
1088
1089                 /* delete from cache and lru q */
1090                 /* XXX do we need rc ? */
1091                 rc = bdb_cache_delete_entry_internal( cache, e );
1092                 bdb_cache_entry_private_destroy( e );
1093                 bdb_entry_return( e );
1094         }
1095
1096         if ( cache->c_cursize ) {
1097 #ifdef NEW_LOGGING
1098                 LDAP_LOG( CACHE, INFO,
1099                    "bdb_cache_release_all: Entry cache could not be emptied.\n", 0, 0, 0 );
1100 #else
1101                 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
1102 #endif
1103
1104         }
1105
1106         /* free lru mutex */
1107         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
1108         /* free cache write lock */
1109         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
1110 }
1111
1112 #ifdef LDAP_DEBUG
1113 static void
1114 bdb_lru_print( Cache *cache )
1115 {
1116         Entry   *e;
1117
1118         fprintf( stderr, "LRU queue (head to tail):\n" );
1119         for ( e = cache->c_lruhead; e != NULL; e = BEI(e)->bei_lrunext ) {
1120                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
1121                         e->e_dn, e->e_id, BEI(e)->bei_refcnt );
1122         }
1123         fprintf( stderr, "LRU queue (tail to head):\n" );
1124         for ( e = cache->c_lrutail; e != NULL; e = BEI(e)->bei_lruprev ) {
1125                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
1126                         e->e_dn, e->e_id, BEI(e)->bei_refcnt );
1127         }
1128 }
1129 #endif
1130
1131 #ifdef BDB_REUSE_LOCKERS
1132 void
1133 bdb_locker_id_free( void *key, void *data )
1134 {
1135         DB_ENV *env = key;
1136         int lockid = (int) data;
1137
1138         XLOCK_ID_FREE( env, lockid );
1139 }
1140
1141 int
1142 bdb_locker_id( Operation *op, DB_ENV *env, int *locker )
1143 {
1144         int i, rc, lockid;
1145         void *data;
1146         void *ctx;
1147
1148         if ( !env || !locker ) return -1;
1149
1150         /* If no op was provided, try to find the ctx anyway... */
1151         if ( op ) {
1152                 ctx = op->o_threadctx;
1153         } else {
1154                 ctx = ldap_pvt_thread_pool_context( &connection_pool );
1155         }
1156
1157         /* Shouldn't happen unless we're single-threaded */
1158         if ( !ctx ) {
1159                 *locker = 0;
1160                 return 0;
1161         }
1162
1163         if ( ldap_pvt_thread_pool_getkey( ctx, env, &data, NULL ) ) {
1164                 for ( i=0, rc=1; rc != 0 && i<4; i++ ) {
1165                         rc = XLOCK_ID( env, &lockid );
1166                         if (rc) ldap_pvt_thread_yield();
1167                 }
1168                 if ( rc != 0) {
1169                         return rc;
1170                 }
1171                 data = (void *)lockid;
1172                 if ( ( rc = ldap_pvt_thread_pool_setkey( ctx, env,
1173                         data, bdb_locker_id_free ) ) ) {
1174                         XLOCK_ID_FREE( env, lockid );
1175 #ifdef NEW_LOGGING
1176                         LDAP_LOG( BACK_BDB, ERR, "bdb_locker_id: err %s(%d)\n",
1177                                 db_strerror(rc), rc, 0 );
1178 #else
1179                         Debug( LDAP_DEBUG_ANY, "bdb_locker_id: err %s(%d)\n",
1180                                 db_strerror(rc), rc, 0 );
1181 #endif
1182
1183                         return rc;
1184                 }
1185         } else {
1186                 lockid = (int)data;
1187         }
1188         *locker = lockid;
1189         return 0;
1190 }
1191 #endif