From 349e05ff4d7799916067e4a503c09f36b1050b89 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Tue, 10 Dec 2002 20:33:49 +0000 Subject: [PATCH] Added config keyword "searchstack" for setting search stack cache depth. Default is still 16. Added IDL caching, modified from ITS#2182. Uses "idlcachesize" config keyword. Code is #ifdef'd, currently defined, with default cache of 0. --- servers/slapd/back-bdb/back-bdb.h | 26 ++++++ servers/slapd/back-bdb/config.c | 22 ++++++ servers/slapd/back-bdb/idl.c | 127 ++++++++++++++++++++++++++++++ servers/slapd/back-bdb/init.c | 26 ++++++ servers/slapd/back-bdb/search.c | 9 +-- 5 files changed, 205 insertions(+), 5 deletions(-) diff --git a/servers/slapd/back-bdb/back-bdb.h b/servers/slapd/back-bdb/back-bdb.h index b41aed3a3e..72da426943 100644 --- a/servers/slapd/back-bdb/back-bdb.h +++ b/servers/slapd/back-bdb/back-bdb.h @@ -60,6 +60,23 @@ LDAP_BEGIN_DECL #define DEFAULT_CACHE_SIZE 1000 +/* The default search IDL stack cache depth */ +#define DEFAULT_SEARCH_STACK_DEPTH 16 + +/* for the IDL cache */ +#define SLAP_IDL_CACHE 1 + +#ifdef SLAP_IDL_CACHE +typedef struct bdb_idl_cache_entry_s { + struct berval kstr; + ldap_pvt_thread_rdwr_t idl_entry_rwlock; + ID *idl; + DB *db; + struct bdb_idl_cache_entry_s* idl_lru_prev; + struct bdb_idl_cache_entry_s* idl_lru_next; +} bdb_idl_cache_entry_t; +#endif + /* for the in-core cache of entries */ typedef struct bdb_cache { int c_maxsize; @@ -100,6 +117,7 @@ struct bdb_info { Cache bi_cache; Avlnode *bi_attrs; void *bi_search_stack; + int bi_search_stack_depth; #ifdef BDB_HIER Avlnode *bi_tree; ldap_pvt_thread_rdwr_t bi_tree_rdwr; @@ -117,6 +135,14 @@ struct bdb_info { #ifdef LDAP_CLIENT_UPDATE LDAP_LIST_HEAD(pl, slap_op) psearch_list; #endif +#ifdef SLAP_IDL_CACHE + int bi_idl_cache_max_size; + int bi_idl_cache_size; + Avlnode *bi_idl_tree; + bdb_idl_cache_entry_t *bi_idl_lru_head; + bdb_idl_cache_entry_t *bi_idl_lru_tail; + ldap_pvt_thread_mutex_t bi_idl_tree_mutex; +#endif }; #define bi_id2entry bi_databases[BDB_ID2ENTRY] diff --git a/servers/slapd/back-bdb/config.c b/servers/slapd/back-bdb/config.c index 90f99672f3..4ce4913aac 100644 --- a/servers/slapd/back-bdb/config.c +++ b/servers/slapd/back-bdb/config.c @@ -135,6 +135,28 @@ bdb_db_config( } bdb->bi_cache.c_maxsize = atoi( argv[1] ); + /* depth of search stack cache in units of (IDL)s */ + } else if ( strcasecmp( argv[0], "searchstack" ) == 0 ) { + if ( argc < 2 ) { + fprintf( stderr, + "%s: line %d: missing depth in \"searchstack \" line\n", + fname, lineno ); + return( 1 ); + } + bdb->bi_search_stack_depth = atoi( argv[1] ); + +#ifdef SLAP_IDL_CACHE + /* size of the IDL cache in entries */ + } else if ( strcasecmp( argv[0], "idlcachesize" ) == 0 ) { + if ( argc < 2 ) { + fprintf( stderr, + "%s: line %d: missing size in \"idlcachesize \" line\n", + fname, lineno ); + return( 1 ); + } + bdb->bi_idl_cache_max_size = atoi( argv[1] ); +#endif + /* anything else */ } else { fprintf( stderr, "%s: line %d: " diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c index e450a7c9c7..58e6bd503c 100644 --- a/servers/slapd/back-bdb/idl.c +++ b/servers/slapd/back-bdb/idl.c @@ -18,6 +18,43 @@ #define IDL_CMP(x,y) ( x < y ? -1 : ( x > y ? 1 : 0 ) ) +#ifdef SLAP_IDL_CACHE +#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); \ + } \ +} while ( 0 ) + +static int +bdb_idl_entry_cmp( bdb_idl_cache_entry_t* idl1, bdb_idl_cache_entry_t* idl2 ) +{ + int rc; + + if ((rc = idl1->db - idl2->db )) return rc; + if ((rc = idl1->kstr.bv_len - idl2->kstr.bv_len )) return rc; + return ( memcmp ( idl1->kstr.bv_val, idl2->kstr.bv_val , idl1->kstr.bv_len ) ); +} +#endif + #if IDL_DEBUG > 0 static void idl_check( ID *ids ) { @@ -262,6 +299,9 @@ bdb_idl_fetch_key( size_t len; int rc2; int flags = bdb->bi_db_opflags | DB_MULTIPLE; +#ifdef SLAP_IDL_CACHE + bdb_idl_cache_entry_t idl_tmp; +#endif /* buf must be large enough to grab the entire IDL in one * get(), otherwise BDB 4 will leak resources on subsequent @@ -287,6 +327,24 @@ bdb_idl_fetch_key( } assert( ids != NULL ); +#ifdef SLAP_IDL_CACHE + if ( bdb->bi_idl_cache_max_size ) { + bdb_idl_cache_entry_t *matched_idl_entry; + DBT2bv( key, &idl_tmp.kstr ); + idl_tmp.db = db; + ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex ); + matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp, (AVL_CMP) bdb_idl_entry_cmp ); + if ( matched_idl_entry != NULL ) { + BDB_IDL_CPY( ids, matched_idl_entry->idl ); + IDL_LRU_DELETE( bdb, matched_idl_entry ); + IDL_LRU_ADD( bdb, matched_idl_entry ); + ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex ); + return LDAP_SUCCESS; + } + ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex ); + } +#endif + DBTzero( &data ); data.data = buf; @@ -400,6 +458,36 @@ bdb_idl_fetch_key( return -1; } +#ifdef SLAP_IDL_CACHE + if ( bdb->bi_idl_cache_max_size ) { + bdb_idl_cache_entry_t *ee; + ee = (bdb_idl_cache_entry_t *) malloc( sizeof( bdb_idl_cache_entry_t ) ); + ee->db = db; + ee->idl = (ID*) malloc ( BDB_IDL_SIZEOF ( ids ) ); + ee->idl_lru_prev = NULL; + ee->idl_lru_next = NULL; + BDB_IDL_CPY( ee->idl, ids ); + ber_dupbv( &ee->kstr, &idl_tmp.kstr ); + ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex ); + avl_insert( &bdb->bi_idl_tree, (caddr_t) ee, (AVL_CMP) bdb_idl_entry_cmp, avl_dup_error ); + IDL_LRU_ADD( bdb, 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; + avl_delete( &bdb->bi_idl_tree, (caddr_t) ee, (AVL_CMP) bdb_idl_entry_cmp ); + IDL_LRU_DELETE( bdb, ee ); + i++; + --bdb->bi_idl_cache_size; + free( ee->kstr.bv_val ); + free( ee->idl ); + free( ee ); + } + } + ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex ); + } +#endif + return rc; } @@ -434,6 +522,25 @@ bdb_idl_insert_key( assert( id != NOID ); +#ifdef SLAP_IDL_CACHE + if ( bdb->bi_idl_cache_size ) { + bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp; + DBT2bv( key, &idl_tmp.kstr ); + idl_tmp.db = db; + ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex ); + matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp, (AVL_CMP) bdb_idl_entry_cmp ); + if ( matched_idl_entry != NULL ) { + avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry, (AVL_CMP) bdb_idl_entry_cmp ); + --bdb->bi_idl_cache_size; + IDL_LRU_DELETE( bdb, matched_idl_entry ); + free( matched_idl_entry->kstr.bv_val ); + free( matched_idl_entry->idl ); + free( matched_idl_entry ); + } + ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex ); + } +#endif + DBTzero( &data ); data.size = sizeof( ID ); data.ulen = data.size; @@ -625,6 +732,25 @@ bdb_idl_delete_key( } assert( id != NOID ); +#ifdef SLAP_IDL_CACHE + if ( bdb->bi_idl_cache_max_size ) { + bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp; + DBT2bv( key, &idl_tmp.kstr ); + idl_tmp.db = db; + ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex ); + matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp, (AVL_CMP) bdb_idl_entry_cmp ); + if ( matched_idl_entry != NULL ) { + avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry, (AVL_CMP) bdb_idl_entry_cmp ); + --bdb->bi_idl_cache_size; + IDL_LRU_DELETE( bdb, matched_idl_entry ); + free( matched_idl_entry->kstr.bv_val ); + free( matched_idl_entry->idl ); + free( matched_idl_entry ); + } + ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex ); + } +#endif + DBTzero( &data ); data.data = &tmp; data.size = sizeof( id ); @@ -1007,3 +1133,4 @@ ID bdb_idl_next( ID *ids, ID *cursor ) return NOID; } + diff --git a/servers/slapd/back-bdb/init.c b/servers/slapd/back-bdb/init.c index 245d165250..5087e0418f 100644 --- a/servers/slapd/back-bdb/init.c +++ b/servers/slapd/back-bdb/init.c @@ -92,6 +92,8 @@ bdb_db_init( BackendDB *be ) bdb->bi_cache.c_maxsize = DEFAULT_CACHE_SIZE; bdb->bi_lock_detect = DB_LOCK_DEFAULT; + bdb->bi_search_stack_depth = DEFAULT_SEARCH_STACK_DEPTH; + bdb->bi_search_stack = NULL; #ifdef LDAP_CLIENT_UPDATE LDAP_LIST_INIT (&bdb->psearch_list); @@ -106,6 +108,7 @@ bdb_db_init( BackendDB *be ) #endif be->be_private = bdb; + return 0; } @@ -184,6 +187,13 @@ bdb_db_open( BackendDB *be ) bdb->bi_dbenv->set_errcall( bdb->bi_dbenv, bdb_errcall ); bdb->bi_dbenv->set_lk_detect( bdb->bi_dbenv, bdb->bi_lock_detect ); +#ifdef SLAP_IDL_CACHE + if ( bdb->bi_idl_cache_max_size ) { + ldap_pvt_thread_mutex_init( &bdb->bi_idl_tree_mutex ); + bdb->bi_idl_cache_size = 0; + } +#endif + #ifdef BDB_SUBDIRS { char dir[MAXPATHLEN]; @@ -402,6 +412,9 @@ bdb_db_close( BackendDB *be ) int rc; struct bdb_info *bdb = (struct bdb_info *) be->be_private; struct bdb_db_info *db; +#ifdef SLAP_IDL_CACHE + bdb_idl_cache_entry_t *entry, *next_entry; +#endif while( bdb->bi_ndatabases-- ) { db = bdb->bi_databases[bdb->bi_ndatabases]; @@ -416,6 +429,19 @@ bdb_db_close( BackendDB *be ) bdb_cache_release_all (&bdb->bi_cache); +#ifdef SLAP_IDL_CACHE + ldap_pvt_thread_mutex_lock ( &bdb->bi_idl_tree_mutex ); + entry = bdb->bi_idl_lru_head; + while ( entry != NULL ) { + next_entry = entry->idl_lru_next; + free( entry->idl ); + free( entry->kstr.bv_val ); + free( entry ); + entry = next_entry; + } + ldap_pvt_thread_mutex_unlock ( &bdb->bi_idl_tree_mutex ); +#endif + return 0; } diff --git a/servers/slapd/back-bdb/search.c b/servers/slapd/back-bdb/search.c index bd9ac9590a..be318c3afe 100644 --- a/servers/slapd/back-bdb/search.c +++ b/servers/slapd/back-bdb/search.c @@ -957,8 +957,6 @@ static int oc_filter( return rc; } -#define SRCH_STACK_SIZE 16 - static void search_stack_free( void *key, void *data) { ch_free(data); @@ -980,7 +978,7 @@ static void *search_stack( } if ( !ret ) { - ret = ch_malloc( SRCH_STACK_SIZE * BDB_IDL_UM_SIZE * sizeof( ID ) ); + ret = ch_malloc( bdb->bi_search_stack_depth * BDB_IDL_UM_SIZE * sizeof( ID ) ); if ( op->o_threadctx ) { ldap_pvt_thread_pool_setkey( op->o_threadctx, search_stack, ret, search_stack_free ); @@ -1000,6 +998,7 @@ static int search_candidates( int deref, ID *ids ) { + struct bdb_info *bdb = (struct bdb_info *) be->be_private; int rc, depth = 1; Filter f, scopef, rf, xf; ID *stack; @@ -1087,7 +1086,7 @@ static int search_candidates( #endif /* Allocate IDL stack, plus 1 more for former tmp */ - if ( depth+1 > SRCH_STACK_SIZE ) { + if ( depth+1 > bdb->bi_search_stack_depth ) { stack = ch_malloc( (depth + 1) * BDB_IDL_UM_SIZE * sizeof( ID ) ); } else { stack = search_stack( be, op ); @@ -1095,7 +1094,7 @@ static int search_candidates( rc = bdb_filter_candidates( be, &f, ids, stack, stack+BDB_IDL_UM_SIZE ); - if ( depth+1 > SRCH_STACK_SIZE ) { + if ( depth+1 > bdb->bi_search_stack_depth ) { ch_free( stack ); } -- 2.39.5