1 /* cache.c - routines to maintain an in-core cache of entries */
13 #include "back-ldbm.h"
15 static int cache_delete_entry_internal(struct cache *cache, Entry *e);
17 static void lru_print(struct cache *cache);
21 * the cache has three entry points (ways to find things):
23 * by entry e.g., if you already have an entry from the cache
24 * and want to delete it. (really by entry ptr)
25 * by dn e.g., when looking for the base object of a search
26 * by id e.g., for search candidates
28 * these correspond to three different avl trees that are maintained.
32 cache_entry_cmp( Entry *e1, Entry *e2 )
34 return( e1 < e2 ? -1 : (e1 > e2 ? 1 : 0) );
38 cache_entrydn_cmp( Entry *e1, Entry *e2 )
40 /* compare their normalized UPPERCASED dn's */
41 return( strcmp( e1->e_ndn, e2->e_ndn ) );
45 cache_entryid_cmp( Entry *e1, Entry *e2 )
47 return( e1->e_id < e2->e_id ? -1 : (e1->e_id > e2->e_id ? 1 : 0) );
51 cache_set_state( struct cache *cache, Entry *e, int state )
54 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
58 /* free cache mutex */
59 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
64 cache_return_entry( struct cache *cache, Entry *e )
67 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
69 if ( --e->e_refcnt == 0 && e->e_state == ENTRY_STATE_DELETED ) {
73 /* free cache mutex */
74 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
79 cache_return_entry_rw( struct cache *cache, Entry *e, int rw )
81 Debug( LDAP_DEBUG_TRACE, "====> cache_return_entry_%s\n",
82 rw ? "w" : "r", 0, 0);
85 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
87 entry_rdwr_unlock(e, rw);
89 if ( --e->e_refcnt == 0 && e->e_state == ENTRY_STATE_DELETED ) {
93 /* free cache mutex */
94 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
98 cache_return_entry_r( struct cache *cache, Entry *e )
100 cache_return_entry_rw(cache, e, 0);
104 cache_return_entry_w( struct cache *cache, Entry *e )
106 cache_return_entry_rw(cache, e, 1);
110 #define LRU_DELETE( cache, e ) { \
111 if ( e->e_lruprev != NULL ) { \
112 e->e_lruprev->e_lrunext = e->e_lrunext; \
114 cache->c_lruhead = e->e_lrunext; \
116 if ( e->e_lrunext != NULL ) { \
117 e->e_lrunext->e_lruprev = e->e_lruprev; \
119 cache->c_lrutail = e->e_lruprev; \
123 #define LRU_ADD( cache, e ) { \
124 e->e_lrunext = cache->c_lruhead; \
125 if ( e->e_lrunext != NULL ) { \
126 e->e_lrunext->e_lruprev = e; \
128 cache->c_lruhead = e; \
129 e->e_lruprev = NULL; \
130 if ( cache->c_lrutail == NULL ) { \
131 cache->c_lrutail = e; \
136 * cache_create_entry_lock - create an entry in the cache, and lock it.
137 * returns: 0 entry has been created and locked
138 * 1 entry already existed
139 * -1 something bad happened
142 cache_add_entry_lock(
151 /* set cache mutex */
152 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
154 if ( avl_insert( &cache->c_dntree, (caddr_t) e,
155 cache_entrydn_cmp, avl_dup_error ) != 0 )
157 Debug( LDAP_DEBUG_TRACE,
158 "====> cache_add_entry lock: entry %20s id %lu already in dn cache\n",
159 e->e_dn, e->e_id, 0 );
161 /* free cache mutex */
162 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
167 if ( avl_insert( &cache->c_idtree, (caddr_t) e,
168 cache_entryid_cmp, avl_dup_error ) != 0 )
170 Debug( LDAP_DEBUG_ANY,
171 "====> entry %20s id %lu already in id cache\n",
172 e->e_dn, e->e_id, 0 );
174 /* delete from dn tree inserted above */
175 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
176 cache_entrydn_cmp ) == NULL )
178 Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
182 /* free cache mutex */
183 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
192 if ( ++cache->c_cursize > cache->c_maxsize ) {
194 * find the lru entry not currently in use and delete it.
195 * in case a lot of entries are in use, only look at the
196 * first 10 on the tail of the list.
199 while ( cache->c_lrutail != NULL && cache->c_lrutail->e_refcnt
201 /* move this in-use entry to the front of the q */
202 ee = cache->c_lrutail;
203 LRU_DELETE( cache, ee );
204 LRU_ADD( cache, ee );
209 * found at least one to delete - try to get back under
210 * the max cache size.
212 while ( cache->c_lrutail != NULL && cache->c_lrutail->e_refcnt
213 == 0 && cache->c_cursize > cache->c_maxsize ) {
214 e = cache->c_lrutail;
216 /* XXX check for writer lock - should also check no readers pending */
218 assert(!ldap_pvt_thread_rdwr_active( &e->e_rdwr ));
221 /* delete from cache and lru q */
222 rc = cache_delete_entry_internal( cache, e );
228 /* free cache mutex */
229 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
234 * cache_find_entry_dn2id - find an entry in the cache, given dn
238 cache_find_entry_dn2id(
244 struct ldbminfo *li = (struct ldbminfo *) be->be_private;
248 /* set cache mutex */
249 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
252 e.e_ndn = dn_normalize_case( ch_strdup( dn ) );
254 if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
255 cache_entrydn_cmp )) != NULL )
258 * ep now points to an unlocked entry
259 * we do not need to lock the entry if we only
260 * check the state, refcnt, LRU, and id.
264 Debug(LDAP_DEBUG_TRACE, "====> cache_find_entry_dn2id: found dn: %s\n",
268 * entry is deleted or not fully created yet
270 if ( ep->e_state == ENTRY_STATE_DELETED ||
271 ep->e_state == ENTRY_STATE_CREATING )
273 /* free cache mutex */
274 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
279 LRU_DELETE( cache, ep );
280 LRU_ADD( cache, ep );
285 /* free cache mutex */
286 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
293 /* free cache mutex */
294 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
300 * cache_find_entry_id - find an entry in the cache, given id
316 /* set cache mutex */
317 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
319 if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
320 cache_entryid_cmp )) != NULL )
322 Debug(LDAP_DEBUG_TRACE,
323 "====> cache_find_entry_dn2id: found id: %ld rw: %d\n",
327 * entry is deleted or not fully created yet
329 if ( ep->e_state == ENTRY_STATE_DELETED ||
330 ep->e_state == ENTRY_STATE_CREATING )
332 /* free cache mutex */
333 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
337 /* acquire reader lock */
338 if ( entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
339 /* could not acquire entry lock...
340 * owner cannot free as we have the cache locked.
341 * so, unlock the cache, yield, and try again.
344 /* free cache mutex */
345 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
346 ldap_pvt_thread_yield();
351 LRU_DELETE( cache, ep );
352 LRU_ADD( cache, ep );
356 /* free cache mutex */
357 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
362 /* free cache mutex */
363 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
369 * cache_delete_entry - delete the entry e from the cache. the caller
370 * should have obtained e (increasing its ref count) via a call to one
371 * of the cache_find_* routines. the caller should *not* call the
372 * cache_return_entry() routine prior to calling cache_delete_entry().
373 * it performs this function.
375 * returns: 0 e was deleted ok
376 * 1 e was not in the cache
377 * -1 something bad happened
387 Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry:\n", 0, 0, 0 );
389 /* XXX check for writer lock - should also check no readers pending */
391 assert(ldap_pvt_thread_rdwr_writers(&e->e_rdwr));
394 /* set cache mutex */
395 ldap_pvt_thread_mutex_lock( &cache->c_mutex );
397 rc = cache_delete_entry_internal( cache, e );
399 /* free cache mutex */
400 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
405 cache_delete_entry_internal(
410 int rc = 0; /* return code */
413 if ( avl_delete( &cache->c_dntree, (caddr_t) e, cache_entrydn_cmp )
420 if ( avl_delete( &cache->c_idtree, (caddr_t) e, cache_entryid_cmp )
431 LRU_DELETE( cache, e );
435 * flag entry to be freed later by a call to cache_return_entry()
437 e->e_state = ENTRY_STATE_DELETED;
445 lru_print( struct cache *cache )
449 fprintf( stderr, "LRU queue (head to tail):\n" );
450 for ( e = cache->c_lruhead; e != NULL; e = e->e_lrunext ) {
451 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
452 e->e_id, e->e_refcnt );
454 fprintf( stderr, "LRU queue (tail to head):\n" );
455 for ( e = cache->c_lrutail; e != NULL; e = e->e_lruprev ) {
456 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
457 e->e_id, e->e_refcnt );