From 5cfd2f6d974ffa522da0dad462e81204162ae4c5 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Wed, 3 Jan 2007 19:00:07 +0000 Subject: [PATCH] Use Clock algorithm for IDL cache too --- servers/slapd/back-bdb/back-bdb.h | 1 + servers/slapd/back-bdb/idl.c | 60 +++++++++++++++---------------- servers/slapd/back-bdb/init.c | 4 +-- 3 files changed, 31 insertions(+), 34 deletions(-) diff --git a/servers/slapd/back-bdb/back-bdb.h b/servers/slapd/back-bdb/back-bdb.h index 5795e62678..dbc076dcc6 100644 --- a/servers/slapd/back-bdb/back-bdb.h +++ b/servers/slapd/back-bdb/back-bdb.h @@ -70,6 +70,7 @@ typedef struct bdb_idl_cache_entry_s { struct berval kstr; ID *idl; DB *db; + int idl_flags; struct bdb_idl_cache_entry_s* idl_lru_prev; struct bdb_idl_cache_entry_s* idl_lru_next; } bdb_idl_cache_entry_t; diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c index e557c701bf..f25478ba74 100644 --- a/servers/slapd/back-bdb/idl.c +++ b/servers/slapd/back-bdb/idl.c @@ -28,28 +28,10 @@ #define IDL_CMP(x,y) ( x < y ? -1 : ( x > y ? 1 : 0 ) ) #define IDL_LRU_DELETE( bdb, e ) do { \ - if ( e->idl_lru_prev != NULL ) { \ - e->idl_lru_prev->idl_lru_next = e->idl_lru_next; \ - } else { \ - bdb->bi_idl_lru_head = e->idl_lru_next; \ - } \ - if ( e->idl_lru_next != NULL ) { \ - e->idl_lru_next->idl_lru_prev = e->idl_lru_prev; \ - } else { \ - bdb->bi_idl_lru_tail = e->idl_lru_prev; \ - } \ -} while ( 0 ) - -#define IDL_LRU_ADD( bdb, e ) do { \ - e->idl_lru_next = bdb->bi_idl_lru_head; \ - if ( e->idl_lru_next != NULL ) { \ - e->idl_lru_next->idl_lru_prev = (e); \ - } \ - (bdb)->bi_idl_lru_head = (e); \ - e->idl_lru_prev = NULL; \ - if ( (bdb)->bi_idl_lru_tail == NULL ) { \ - (bdb)->bi_idl_lru_tail = (e); \ - } \ + if ( e == bdb->bi_idl_lru_head ) bdb->bi_idl_lru_head = e->idl_lru_next; \ + if ( e == bdb->bi_idl_lru_tail ) bdb->bi_idl_lru_tail = e->idl_lru_prev; \ + e->idl_lru_next->idl_lru_prev = e->idl_lru_prev; \ + e->idl_lru_prev->idl_lru_next = e->idl_lru_next; \ } while ( 0 ) static int @@ -317,10 +299,7 @@ bdb_idl_cache_get( if ( matched_idl_entry != NULL ) { if ( matched_idl_entry->idl && ids ) BDB_IDL_CPY( ids, matched_idl_entry->idl ); - ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock ); - IDL_LRU_DELETE( bdb, matched_idl_entry ); - IDL_LRU_ADD( bdb, matched_idl_entry ); - ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock ); + matched_idl_entry->idl_flags |= CACHE_ENTRY_REFERENCED; if ( matched_idl_entry->idl ) rc = LDAP_SUCCESS; else @@ -340,7 +319,7 @@ bdb_idl_cache_put( int rc ) { bdb_idl_cache_entry_t idl_tmp; - bdb_idl_cache_entry_t *ee; + bdb_idl_cache_entry_t *ee, *eprev; if ( rc == DB_NOTFOUND || BDB_IDL_IS_ZERO( ids )) return; @@ -355,6 +334,7 @@ bdb_idl_cache_put( ee->idl_lru_prev = NULL; ee->idl_lru_next = NULL; + ee->idl_flags = 0; ber_dupbv( &ee->kstr, &idl_tmp.kstr ); ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock ); if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee, @@ -367,11 +347,27 @@ bdb_idl_cache_put( return; } ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock ); - IDL_LRU_ADD( bdb, ee ); + /* LRU_ADD */ + if ( bdb->bi_idl_lru_head ) { + ee->idl_lru_next = bdb->bi_idl_lru_head; + ee->idl_lru_prev = bdb->bi_idl_lru_head->idl_lru_prev; + bdb->bi_idl_lru_head->idl_lru_prev->idl_lru_next = ee; + bdb->bi_idl_lru_head->idl_lru_prev = ee; + } else { + ee->idl_lru_next = ee->idl_lru_prev = ee; + bdb->bi_idl_lru_tail = ee; + } + bdb->bi_idl_lru_head = ee; + if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) { - int i = 0; - while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) { - ee = bdb->bi_idl_lru_tail; + int i; + ee = bdb->bi_idl_lru_tail; + for ( i = 0; i < 10; i++, ee = eprev ) { + eprev = ee->idl_lru_prev; + if ( ee->idl_flags & CACHE_ENTRY_REFERENCED ) { + ee->idl_flags ^= CACHE_ENTRY_REFERENCED; + continue; + } if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee, bdb_idl_entry_cmp ) == NULL ) { Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: " @@ -385,8 +381,8 @@ bdb_idl_cache_put( ch_free( ee->idl ); ch_free( ee ); } + bdb->bi_idl_lru_tail = eprev; } - ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock ); ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock ); } diff --git a/servers/slapd/back-bdb/init.c b/servers/slapd/back-bdb/init.c index d2e6804b02..018a741421 100644 --- a/servers/slapd/back-bdb/init.c +++ b/servers/slapd/back-bdb/init.c @@ -477,14 +477,14 @@ bdb_db_close( BackendDB *be ) avl_free( bdb->bi_idl_tree, NULL ); bdb->bi_idl_tree = NULL; entry = bdb->bi_idl_lru_head; - while ( entry != NULL ) { + do { next_entry = entry->idl_lru_next; if ( entry->idl ) free( entry->idl ); free( entry->kstr.bv_val ); free( entry ); entry = next_entry; - } + } while ( entry != bdb->bi_idl_lru_head ); bdb->bi_idl_lru_head = bdb->bi_idl_lru_tail = NULL; } -- 2.39.5