1 /* cache.c - routines to maintain an in-core cache of entries */
4 * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
5 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
13 #include <ac/string.h>
14 #include <ac/socket.h>
18 #include "back-ldbm.h"
20 /* LDBM backend specific entry info -- visible only to the cache */
21 typedef struct ldbm_entry_info {
22 ldap_pvt_thread_rdwr_t lei_rdwr; /* reader/writer lock */
25 * remaining fields require backend cache lock to access
26 * These items are specific to the LDBM backend and should
29 int lei_state; /* for the cache */
30 #define CACHE_ENTRY_UNDEFINED 0
31 #define CACHE_ENTRY_CREATING 1
32 #define CACHE_ENTRY_READY 2
33 #define CACHE_ENTRY_DELETED 3
35 int lei_refcnt; /* # threads ref'ing this entry */
36 Entry *lei_lrunext; /* for cache lru list */
39 #define LEI(e) ((EntryInfo *) ((e)->e_private))
41 static int cache_delete_entry_internal(Cache *cache, Entry *e);
43 static void lru_print(Cache *cache);
47 cache_entry_rdwr_lock(Entry *e, int rw)
49 Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
50 rw ? "w" : "r", e->e_id, 0);
53 return ldap_pvt_thread_rdwr_wlock(&LEI(e)->lei_rdwr);
55 return ldap_pvt_thread_rdwr_rlock(&LEI(e)->lei_rdwr);
59 cache_entry_rdwr_trylock(Entry *e, int rw)
61 Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
62 rw ? "w" : "r", e->e_id, 0);
65 return ldap_pvt_thread_rdwr_wtrylock(&LEI(e)->lei_rdwr);
67 return ldap_pvt_thread_rdwr_rtrylock(&LEI(e)->lei_rdwr);
71 cache_entry_rdwr_unlock(Entry *e, int rw)
73 Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
74 rw ? "w" : "r", e->e_id, 0);
77 return ldap_pvt_thread_rdwr_wunlock(&LEI(e)->lei_rdwr);
79 return ldap_pvt_thread_rdwr_runlock(&LEI(e)->lei_rdwr);
83 cache_entry_rdwr_init(Entry *e)
85 return ldap_pvt_thread_rdwr_init( &LEI(e)->lei_rdwr );
89 cache_entry_rdwr_destroy(Entry *e)
91 return ldap_pvt_thread_rdwr_destroy( &LEI(e)->lei_rdwr );
95 cache_entry_private_init( Entry*e )
97 assert( e->e_private == NULL );
99 if( e->e_private != NULL ) {
100 /* this should never happen */
104 e->e_private = ch_calloc(1, sizeof(struct ldbm_entry_info));
106 if( cache_entry_rdwr_init( e ) != 0 ) {
116 cache_entry_private_destroy( Entry*e )
118 assert( e->e_private );
120 cache_entry_rdwr_destroy( e );
122 free( e->e_private );
128 cache_return_entry_rw( Cache *cache, Entry *e, int rw )
133 /* set cache mutex */
134 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
136 assert( e->e_private );
138 cache_entry_rdwr_unlock(e, rw);
141 refcnt = --LEI(e)->lei_refcnt;
143 if ( LEI(e)->lei_state == CACHE_ENTRY_CREATING ) {
144 LEI(e)->lei_state = CACHE_ENTRY_READY;
146 /* free cache mutex */
147 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
149 Debug( LDAP_DEBUG_TRACE,
150 "====> cache_return_entry_%s( %ld ): created (%d)\n",
151 rw ? "w" : "r", id, refcnt );
153 } else if ( LEI(e)->lei_state == CACHE_ENTRY_DELETED ) {
155 /* free cache mutex */
156 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
158 Debug( LDAP_DEBUG_TRACE,
159 "====> cache_return_entry_%s( %ld ): delete pending (%d)\n",
160 rw ? "w" : "r", id, refcnt );
163 cache_entry_private_destroy( e );
166 /* free cache mutex */
167 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
169 Debug( LDAP_DEBUG_TRACE,
170 "====> cache_return_entry_%s( %ld ): deleted (%d)\n",
171 rw ? "w" : "r", id, refcnt );
175 /* free cache mutex */
176 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
178 Debug( LDAP_DEBUG_TRACE,
179 "====> cache_return_entry_%s( %ld ): returned (%d)\n",
180 rw ? "w" : "r", id, refcnt);
184 #define LRU_DELETE( cache, e ) do { \
185 if ( LEI(e)->lei_lruprev != NULL ) { \
186 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
188 (cache)->c_lruhead = LEI(e)->lei_lrunext; \
190 if ( LEI(e)->lei_lrunext != NULL ) { \
191 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
193 (cache)->c_lrutail = LEI(e)->lei_lruprev; \
197 #define LRU_ADD( cache, e ) do { \
198 LEI(e)->lei_lrunext = (cache)->c_lruhead; \
199 if ( LEI(e)->lei_lrunext != NULL ) { \
200 LEI(LEI(e)->lei_lrunext)->lei_lruprev = (e); \
202 (cache)->c_lruhead = (e); \
203 LEI(e)->lei_lruprev = NULL; \
204 if ( (cache)->c_lrutail == NULL ) { \
205 (cache)->c_lrutail = (e); \
210 * cache_add_entry_rw - create and lock an entry in the cache
211 * returns: 0 entry has been created and locked
212 * 1 entry already existed
213 * -1 something bad happened
225 /* set cache mutex */
226 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
228 assert( e->e_private == NULL );
230 if( cache_entry_private_init(e) != 0 ) {
231 /* free cache mutex */
232 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
234 Debug( LDAP_DEBUG_ANY,
235 "====> cache_add_entry( %ld ): \"%s\": private init failed!\n",
236 e->e_id, e->e_dn, 0 );
241 if ( avl_insert( &cache->c_dntree, (caddr_t) e,
242 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
244 /* free cache mutex */
245 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
247 Debug( LDAP_DEBUG_TRACE,
248 "====> cache_add_entry( %ld ): \"%s\": already in dn cache\n",
249 e->e_id, e->e_dn, 0 );
251 cache_entry_private_destroy(e);
257 if ( avl_insert( &cache->c_idtree, (caddr_t) e,
258 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
260 Debug( LDAP_DEBUG_ANY,
261 "====> cache_add_entry( %ld ): \"%s\": already in id cache\n",
262 e->e_id, e->e_dn, 0 );
265 /* delete from dn tree inserted above */
266 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
267 (AVL_CMP) entry_dn_cmp ) == NULL )
269 Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
273 cache_entry_private_destroy(e);
275 /* free cache mutex */
276 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
280 cache_entry_rdwr_lock( e, rw );
282 /* put the entry into 'CREATING' state */
283 /* will be marked after when entry is returned */
284 LEI(e)->lei_state = CACHE_ENTRY_CREATING;
285 LEI(e)->lei_refcnt = 1;
289 if ( ++cache->c_cursize > cache->c_maxsize ) {
291 * find the lru entry not currently in use and delete it.
292 * in case a lot of entries are in use, only look at the
293 * first 10 on the tail of the list.
296 while ( cache->c_lrutail != NULL &&
297 LEI(cache->c_lrutail)->lei_refcnt != 0 &&
300 /* move this in-use entry to the front of the q */
301 ee = cache->c_lrutail;
302 LRU_DELETE( cache, ee );
303 LRU_ADD( cache, ee );
308 * found at least one to delete - try to get back under
309 * the max cache size.
311 while ( cache->c_lrutail != NULL &&
312 LEI(cache->c_lrutail)->lei_refcnt == 0 &&
313 cache->c_cursize > cache->c_maxsize )
315 e = cache->c_lrutail;
317 /* delete from cache and lru q */
318 /* XXX do we need rc ? */
319 rc = cache_delete_entry_internal( cache, e );
320 cache_entry_private_destroy( e );
325 /* free cache mutex */
326 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
331 * cache_update_entry - update a LOCKED entry which has been deleted.
332 * returns: 0 entry has been created and locked
333 * 1 entry already existed
334 * -1 something bad happened
345 /* set cache mutex */
346 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
348 assert( e->e_private );
350 if ( avl_insert( &cache->c_dntree, (caddr_t) e,
351 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
353 Debug( LDAP_DEBUG_TRACE,
354 "====> cache_update_entry( %ld ): \"%s\": already in dn cache\n",
355 e->e_id, e->e_dn, 0 );
357 /* free cache mutex */
358 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
363 if ( avl_insert( &cache->c_idtree, (caddr_t) e,
364 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
366 Debug( LDAP_DEBUG_ANY,
367 "====> cache_update_entry( %ld ): \"%s\": already in id cache\n",
368 e->e_id, e->e_dn, 0 );
370 /* delete from dn tree inserted above */
371 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
372 (AVL_CMP) entry_dn_cmp ) == NULL )
374 Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
378 /* free cache mutex */
379 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
384 /* put the entry into 'CREATING' state */
385 /* will be marked after when entry is returned */
386 LEI(e)->lei_state = CACHE_ENTRY_CREATING;
390 if ( ++cache->c_cursize > cache->c_maxsize ) {
392 * find the lru entry not currently in use and delete it.
393 * in case a lot of entries are in use, only look at the
394 * first 10 on the tail of the list.
397 while ( cache->c_lrutail != NULL &&
398 LEI(cache->c_lrutail)->lei_refcnt != 0 &&
401 /* move this in-use entry to the front of the q */
402 ee = cache->c_lrutail;
403 LRU_DELETE( cache, ee );
404 LRU_ADD( cache, ee );
409 * found at least one to delete - try to get back under
410 * the max cache size.
412 while ( cache->c_lrutail != NULL &&
413 LEI(cache->c_lrutail)->lei_refcnt == 0 &&
414 cache->c_cursize > cache->c_maxsize )
416 e = cache->c_lrutail;
418 /* delete from cache and lru q */
419 /* XXX do we need rc ? */
420 rc = cache_delete_entry_internal( cache, e );
421 cache_entry_private_destroy( e );
426 /* free cache mutex */
427 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
432 * cache_find_entry_dn2id - find an entry in the cache, given dn
436 cache_find_entry_dn2id(
446 e.e_dn = (char *) dn;
447 e.e_ndn = ch_strdup( dn );
448 (void) dn_normalize( e.e_ndn );
451 /* set cache mutex */
452 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
454 if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
455 (AVL_CMP) entry_dn_cmp )) != NULL )
461 * ep now points to an unlocked entry
462 * we do not need to lock the entry if we only
463 * check the state, refcnt, LRU, and id.
466 assert( ep->e_private );
470 state = LEI(ep)->lei_state;
473 * entry is deleted or not fully created yet
475 if ( state != CACHE_ENTRY_READY ) {
476 assert(state != CACHE_ENTRY_UNDEFINED);
478 /* free cache mutex */
479 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
481 Debug(LDAP_DEBUG_TRACE,
482 "====> cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
485 ldap_pvt_thread_yield();
490 LRU_DELETE( cache, ep );
491 LRU_ADD( cache, ep );
493 /* free cache mutex */
494 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
496 Debug(LDAP_DEBUG_TRACE,
497 "====> cache_find_entry_dn2id(\"%s\"): %ld (%d tries)\n",
501 /* free cache mutex */
502 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
513 * cache_find_entry_id - find an entry in the cache, given id
530 /* set cache mutex */
531 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
533 if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
534 (AVL_CMP) entry_id_cmp )) != NULL )
541 assert( ep->e_private );
544 state = LEI(ep)->lei_state;
547 * entry is deleted or not fully created yet
549 if ( state != CACHE_ENTRY_READY ) {
551 assert(state != CACHE_ENTRY_UNDEFINED);
553 /* free cache mutex */
554 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
556 Debug(LDAP_DEBUG_TRACE,
557 "====> cache_find_entry_id( %ld ): %ld (not ready) %d\n",
560 ldap_pvt_thread_yield();
564 /* acquire reader lock */
565 if ( cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
566 /* could not acquire entry lock...
567 * owner cannot free as we have the cache locked.
568 * so, unlock the cache, yield, and try again.
571 /* free cache mutex */
572 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
574 Debug(LDAP_DEBUG_TRACE,
575 "====> cache_find_entry_id( %ld ): %ld (busy) %d\n",
578 ldap_pvt_thread_yield();
583 LRU_DELETE( cache, ep );
584 LRU_ADD( cache, ep );
586 LEI(ep)->lei_refcnt++;
588 /* free cache mutex */
589 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
591 Debug(LDAP_DEBUG_TRACE,
592 "====> cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
593 ep_id, ep->e_dn, count);
598 /* free cache mutex */
599 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
605 * cache_delete_entry - delete the entry e from the cache. the caller
606 * should have obtained e (increasing its ref count) via a call to one
607 * of the cache_find_* routines. the caller should *not* call the
608 * cache_return_entry() routine prior to calling cache_delete_entry().
609 * it performs this function.
611 * returns: 0 e was deleted ok
612 * 1 e was not in the cache
613 * -1 something bad happened
623 /* set cache mutex */
624 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
626 assert( e->e_private );
628 Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry( %ld )\n",
631 rc = cache_delete_entry_internal( cache, e );
633 /* free cache mutex */
634 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
639 cache_delete_entry_internal(
644 int rc = 0; /* return code */
647 if ( avl_delete( &cache->c_dntree, (caddr_t) e, (AVL_CMP) entry_dn_cmp )
654 if ( avl_delete( &cache->c_idtree, (caddr_t) e, (AVL_CMP) entry_id_cmp )
665 LRU_DELETE( cache, e );
669 * flag entry to be freed later by a call to cache_return_entry()
671 LEI(e)->lei_state = CACHE_ENTRY_DELETED;
677 cache_release_all( Cache *cache )
682 /* set cache mutex */
683 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
685 Debug( LDAP_DEBUG_TRACE, "====> cache_release_all\n", 0, 0, 0 );
687 while ( (e = cache->c_lrutail) != NULL && LEI(e)->lei_refcnt == 0 ) {
688 assert(!ldap_pvt_thread_rdwr_active(&LEI(e)->lei_rdwr));
690 /* delete from cache and lru q */
691 /* XXX do we need rc ? */
692 rc = cache_delete_entry_internal( cache, e );
693 cache_entry_private_destroy( e );
697 if ( cache->c_cursize ) {
698 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
701 /* free cache mutex */
702 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
708 lru_print( Cache *cache )
712 fprintf( stderr, "LRU queue (head to tail):\n" );
713 for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
714 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
715 e->e_dn, e->e_id, LEI(e)->lei_refcnt );
717 fprintf( stderr, "LRU queue (tail to head):\n" );
718 for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
719 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
720 e->e_dn, e->e_id, LEI(e)->lei_refcnt );