1 /* cache.c - routines to maintain an in-core cache of entries */
13 #include "back-ldbm.h"
15 /* LDBM backend specific entry info -- visible only to the cache */
16 struct ldbm_entry_info {
17 ldap_pvt_thread_rdwr_t lei_rdwr; /* reader/writer lock */
20 * remaining fields require backend cache lock to access
21 * These items are specific to the LDBM backend and should
24 int lei_state; /* for the cache */
26 int lei_refcnt; /* # threads ref'ing this entry */
27 struct entry *lei_lrunext; /* for cache lru list */
28 struct entry *lei_lruprev;
30 #define LEI(e) ((struct ldbm_entry_info *) ((e)->e_private))
32 static int cache_delete_entry_internal(struct cache *cache, Entry *e);
34 static void lru_print(struct cache *cache);
38 * the cache has three entry points (ways to find things):
40 * by entry e.g., if you already have an entry from the cache
41 * and want to delete it. (really by entry ptr)
42 * by dn e.g., when looking for the base object of a search
43 * by id e.g., for search candidates
45 * these correspond to three different avl trees that are maintained.
49 cache_entry_cmp( Entry *e1, Entry *e2 )
51 return( e1 < e2 ? -1 : (e1 > e2 ? 1 : 0) );
55 cache_entrydn_cmp( Entry *e1, Entry *e2 )
57 /* compare their normalized UPPERCASED dn's */
58 return( strcmp( e1->e_ndn, e2->e_ndn ) );
62 cache_entryid_cmp( Entry *e1, Entry *e2 )
64 return( e1->e_id < e2->e_id ? -1 : (e1->e_id > e2->e_id ? 1 : 0) );
68 cache_set_state( struct cache *cache, Entry *e, int state )
71 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
73 LEI(e)->lei_state = state;
75 /* free cache mutex */
76 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
80 cache_entry_rdwr_lock(Entry *e, int rw)
82 Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
83 rw ? "w" : "r", e->e_id, 0);
86 return ldap_pvt_thread_rdwr_wlock(&LEI(e)->lei_rdwr);
88 return ldap_pvt_thread_rdwr_rlock(&LEI(e)->lei_rdwr);
92 cache_entry_rdwr_trylock(Entry *e, int rw)
94 Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
95 rw ? "w" : "r", e->e_id, 0);
98 return ldap_pvt_thread_rdwr_wtrylock(&LEI(e)->lei_rdwr);
100 return ldap_pvt_thread_rdwr_rtrylock(&LEI(e)->lei_rdwr);
104 cache_entry_rdwr_unlock(Entry *e, int rw)
106 Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
107 rw ? "w" : "r", e->e_id, 0);
110 return ldap_pvt_thread_rdwr_wunlock(&LEI(e)->lei_rdwr);
112 return ldap_pvt_thread_rdwr_runlock(&LEI(e)->lei_rdwr);
116 cache_entry_rdwr_init(Entry *e)
118 return ldap_pvt_thread_rdwr_init( &LEI(e)->lei_rdwr );
122 cache_entry_rdwr_destroy(Entry *e)
124 return ldap_pvt_thread_rdwr_destroy( &LEI(e)->lei_rdwr );
128 cache_entry_private_init( Entry*e )
130 struct ldbm_entry_info *lei;
132 if( e->e_private != NULL ) {
136 e->e_private = ch_calloc(1, sizeof(struct ldbm_entry_info));
138 if( cache_entry_rdwr_init( e ) != 0 ) {
147 cache_entry_private_destroy( Entry*e )
149 struct ldbm_entry_info *lei;
151 if( e->e_private == NULL ) {
155 cache_entry_rdwr_destroy( e );
157 free( e->e_private );
163 cache_return_entry_rw( struct cache *cache, Entry *e, int rw )
165 Debug( LDAP_DEBUG_TRACE, "====> cache_return_entry_%s\n",
166 rw ? "w" : "r", 0, 0);
168 /* set cache mutex */
169 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
171 cache_entry_rdwr_unlock(e, rw);
173 if ( --LEI(e)->lei_refcnt == 0 &&
174 LEI(e)->lei_state == ENTRY_STATE_DELETED )
176 cache_entry_private_destroy( e );
180 /* free cache mutex */
181 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
185 cache_return_entry_r( struct cache *cache, Entry *e )
187 cache_return_entry_rw(cache, e, 0);
191 cache_return_entry_w( struct cache *cache, Entry *e )
193 cache_return_entry_rw(cache, e, 1);
197 #define LRU_DELETE( cache, e ) { \
198 if ( LEI(e)->lei_lruprev != NULL ) { \
199 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
201 cache->c_lruhead = LEI(e)->lei_lrunext; \
203 if ( LEI(e)->lei_lrunext != NULL ) { \
204 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
206 cache->c_lrutail = LEI(e)->lei_lruprev; \
210 #define LRU_ADD( cache, e ) { \
211 LEI(e)->lei_lrunext = cache->c_lruhead; \
212 if ( LEI(e)->lei_lrunext != NULL ) { \
213 LEI(LEI(e)->lei_lrunext)->lei_lruprev = e; \
215 cache->c_lruhead = e; \
216 LEI(e)->lei_lruprev = NULL; \
217 if ( cache->c_lrutail == NULL ) { \
218 cache->c_lrutail = e; \
223 * cache_add_entry_rw - create and lock an entry in the cache
224 * returns: 0 entry has been created and locked
225 * 1 entry already existed
226 * -1 something bad happened
239 /* set cache mutex */
240 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
242 if ( e->e_private != NULL ) {
243 Debug( LDAP_DEBUG_ANY,
244 "====> cache_add_entry: entry %20s id %lu already cached.\n",
245 e->e_dn, e->e_id, 0 );
249 if( cache_entry_private_init(e) != 0 ) {
250 Debug( LDAP_DEBUG_ANY,
251 "====> cache_add_entry: entry %20s id %lu: private init failed!\n",
252 e->e_dn, e->e_id, 0 );
256 if ( avl_insert( &cache->c_dntree, (caddr_t) e,
257 cache_entrydn_cmp, avl_dup_error ) != 0 )
259 Debug( LDAP_DEBUG_TRACE,
260 "====> cache_add_entry: entry %20s id %lu already in dn cache\n",
261 e->e_dn, e->e_id, 0 );
263 cache_entry_private_destroy(e);
265 /* free cache mutex */
266 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
271 if ( avl_insert( &cache->c_idtree, (caddr_t) e,
272 cache_entryid_cmp, avl_dup_error ) != 0 )
274 Debug( LDAP_DEBUG_ANY,
275 "====> entry %20s id %lu already in id cache\n",
276 e->e_dn, e->e_id, 0 );
278 /* delete from dn tree inserted above */
279 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
280 cache_entrydn_cmp ) == NULL )
282 Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
286 cache_entry_private_destroy(e);
288 /* free cache mutex */
289 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
293 cache_entry_rdwr_lock( e, rw );
295 LEI(e)->lei_state = state;
296 LEI(e)->lei_refcnt = 1;
300 if ( ++cache->c_cursize > cache->c_maxsize ) {
302 * find the lru entry not currently in use and delete it.
303 * in case a lot of entries are in use, only look at the
304 * first 10 on the tail of the list.
307 while ( cache->c_lrutail != NULL &&
308 LEI(cache->c_lrutail)->lei_refcnt != 0 &&
311 /* move this in-use entry to the front of the q */
312 ee = cache->c_lrutail;
313 LRU_DELETE( cache, ee );
314 LRU_ADD( cache, ee );
319 * found at least one to delete - try to get back under
320 * the max cache size.
322 while ( cache->c_lrutail != NULL &&
323 LEI(cache->c_lrutail)->lei_refcnt == 0 &&
324 cache->c_cursize > cache->c_maxsize )
326 e = cache->c_lrutail;
328 /* delete from cache and lru q */
329 rc = cache_delete_entry_internal( cache, e );
335 /* free cache mutex */
336 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
341 * cache_update_entry - update a LOCKED entry which has been deleted.
342 * returns: 0 entry has been created and locked
343 * 1 entry already existed
344 * -1 something bad happened
355 /* set cache mutex */
356 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
358 if ( e->e_private == NULL ) {
359 Debug( LDAP_DEBUG_ANY,
360 "====> cache_update_entry: entry %20s id %lu no private data.\n",
361 e->e_dn, e->e_id, 0 );
365 if ( avl_insert( &cache->c_dntree, (caddr_t) e,
366 cache_entrydn_cmp, avl_dup_error ) != 0 )
368 Debug( LDAP_DEBUG_TRACE,
369 "====> cache_add_entry: entry %20s id %lu already in dn cache\n",
370 e->e_dn, e->e_id, 0 );
372 /* free cache mutex */
373 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
378 if ( avl_insert( &cache->c_idtree, (caddr_t) e,
379 cache_entryid_cmp, avl_dup_error ) != 0 )
381 Debug( LDAP_DEBUG_ANY,
382 "====> entry %20s id %lu already in id cache\n",
383 e->e_dn, e->e_id, 0 );
385 /* delete from dn tree inserted above */
386 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
387 cache_entrydn_cmp ) == NULL )
389 Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
393 /* free cache mutex */
394 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
400 if ( ++cache->c_cursize > cache->c_maxsize ) {
402 * find the lru entry not currently in use and delete it.
403 * in case a lot of entries are in use, only look at the
404 * first 10 on the tail of the list.
407 while ( cache->c_lrutail != NULL &&
408 LEI(cache->c_lrutail)->lei_refcnt != 0 &&
411 /* move this in-use entry to the front of the q */
412 ee = cache->c_lrutail;
413 LRU_DELETE( cache, ee );
414 LRU_ADD( cache, ee );
419 * found at least one to delete - try to get back under
420 * the max cache size.
422 while ( cache->c_lrutail != NULL &&
423 LEI(cache->c_lrutail)->lei_refcnt == 0 &&
424 cache->c_cursize > cache->c_maxsize )
426 e = cache->c_lrutail;
428 /* delete from cache and lru q */
429 rc = cache_delete_entry_internal( cache, e );
435 /* free cache mutex */
436 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
441 * cache_find_entry_dn2id - find an entry in the cache, given dn
445 cache_find_entry_dn2id(
451 struct ldbminfo *li = (struct ldbminfo *) be->be_private;
455 /* set cache mutex */
456 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
459 e.e_ndn = dn_normalize_case( ch_strdup( dn ) );
461 if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
462 cache_entrydn_cmp )) != NULL )
465 * ep now points to an unlocked entry
466 * we do not need to lock the entry if we only
467 * check the state, refcnt, LRU, and id.
471 Debug(LDAP_DEBUG_TRACE, "====> cache_find_entry_dn2id: found dn: %s\n",
475 * entry is deleted or not fully created yet
477 if ( LEI(ep)->lei_state == ENTRY_STATE_DELETED ||
478 LEI(ep)->lei_state == ENTRY_STATE_CREATING )
480 /* free cache mutex */
481 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
486 LRU_DELETE( cache, ep );
487 LRU_ADD( cache, ep );
492 /* free cache mutex */
493 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
500 /* free cache mutex */
501 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
507 * cache_find_entry_id - find an entry in the cache, given id
523 /* set cache mutex */
524 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
526 if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
527 cache_entryid_cmp )) != NULL )
529 Debug(LDAP_DEBUG_TRACE,
530 "====> cache_find_entry_dn2id: found id: %ld rw: %d\n",
534 * entry is deleted or not fully created yet
536 if ( LEI(ep)->lei_state == ENTRY_STATE_DELETED ||
537 LEI(ep)->lei_state == ENTRY_STATE_CREATING )
539 /* free cache mutex */
540 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
544 /* acquire reader lock */
545 if ( cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
546 /* could not acquire entry lock...
547 * owner cannot free as we have the cache locked.
548 * so, unlock the cache, yield, and try again.
551 /* free cache mutex */
552 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
553 ldap_pvt_thread_yield();
558 LRU_DELETE( cache, ep );
559 LRU_ADD( cache, ep );
561 LEI(ep)->lei_refcnt++;
563 /* free cache mutex */
564 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
569 /* free cache mutex */
570 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
576 * cache_delete_entry - delete the entry e from the cache. the caller
577 * should have obtained e (increasing its ref count) via a call to one
578 * of the cache_find_* routines. the caller should *not* call the
579 * cache_return_entry() routine prior to calling cache_delete_entry().
580 * it performs this function.
582 * returns: 0 e was deleted ok
583 * 1 e was not in the cache
584 * -1 something bad happened
594 Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry:\n", 0, 0, 0 );
596 /* set cache mutex */
597 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
599 rc = cache_delete_entry_internal( cache, e );
601 /* free cache mutex */
602 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
607 cache_delete_entry_internal(
612 int rc = 0; /* return code */
615 if ( avl_delete( &cache->c_dntree, (caddr_t) e, cache_entrydn_cmp )
622 if ( avl_delete( &cache->c_idtree, (caddr_t) e, cache_entryid_cmp )
633 LRU_DELETE( cache, e );
637 * flag entry to be freed later by a call to cache_return_entry()
639 LEI(e)->lei_state = ENTRY_STATE_DELETED;
647 lru_print( struct cache *cache )
651 fprintf( stderr, "LRU queue (head to tail):\n" );
652 for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
653 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
654 e->e_id, LEI(e)->lei_refcnt );
656 fprintf( stderr, "LRU queue (tail to head):\n" );
657 for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
658 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
659 e->e_id, LEI(e)->lei_refcnt );