+#ifdef BDB_HIER
+/* Walk up the tree from a child node, looking for an ID that's already
+ * been linked into the cache.
+ */
+int
+hdb_cache_find_parent(
+ Operation *op,
+ DB_TXN *txn,
+ ID id,
+ EntryInfo **res )
+{
+ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
+ EntryInfo ei, eip, *ei2 = NULL, *ein = NULL, *eir = NULL;
+ int rc, add;
+
+ ei.bei_id = id;
+ ei.bei_kids = NULL;
+ ei.bei_ckids = 0;
+
+ for (;;) {
+ rc = hdb_dn2id_parent( op, txn, &ei, &eip.bei_id );
+ if ( rc ) break;
+
+ /* Save the previous node, if any */
+ ei2 = ein;
+
+ /* Create a new node for the current ID */
+ ein = bdb_cache_entryinfo_new( &bdb->bi_cache );
+ ein->bei_id = ei.bei_id;
+ ein->bei_kids = ei.bei_kids;
+ ein->bei_nrdn = ei.bei_nrdn;
+ ein->bei_rdn = ei.bei_rdn;
+ ein->bei_ckids = ei.bei_ckids;
+#ifdef SLAP_ZONE_ALLOC
+ ein->bei_bdb = bdb;
+#endif
+ ei.bei_ckids = 0;
+ add = 1;
+
+ /* This node is not fully connected yet */
+ ein->bei_state |= CACHE_ENTRY_NOT_LINKED;
+
+ /* If this is the first time, save this node
+ * to be returned later.
+ */
+ if ( eir == NULL ) {
+ eir = ein;
+ ein->bei_finders++;
+ }
+
+again:
+ /* Insert this node into the ID tree */
+ ldap_pvt_thread_rdwr_wlock( &bdb->bi_cache.c_rwlock );
+ if ( avl_insert( &bdb->bi_cache.c_idtree, (caddr_t)ein,
+ bdb_id_cmp, bdb_id_dup_err ) ) {
+ EntryInfo *eix = ein->bei_lrunext;
+
+ if ( bdb_cache_entryinfo_trylock( eix )) {
+ ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
+ ldap_pvt_thread_yield();
+ goto again;
+ }
+ ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
+
+ /* Someone else created this node just before us.
+ * Free our new copy and use the existing one.
+ */
+ bdb_cache_entryinfo_free( &bdb->bi_cache, ein );
+
+ /* if it was the node we were looking for, just return it */
+ if ( eir == ein ) {
+ *res = eix;
+ rc = 0;
+ break;
+ }
+
+ ein = ei2;
+ ei2 = eix;
+ add = 0;
+
+ /* otherwise, link up what we have and return */
+ goto gotparent;
+ }
+
+ /* If there was a previous node, link it to this one */
+ if ( ei2 ) ei2->bei_parent = ein;
+
+ /* Look for this node's parent */
+par2:
+ if ( eip.bei_id ) {
+ ei2 = (EntryInfo *) avl_find( bdb->bi_cache.c_idtree,
+ (caddr_t) &eip, bdb_id_cmp );
+ } else {
+ ei2 = &bdb->bi_cache.c_dntree;
+ }
+ if ( ei2 && bdb_cache_entryinfo_trylock( ei2 )) {
+ ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
+ ldap_pvt_thread_yield();
+ ldap_pvt_thread_rdwr_wlock( &bdb->bi_cache.c_rwlock );
+ goto par2;
+ }
+ if ( add )
+ bdb->bi_cache.c_eiused++;
+ if ( ei2 && ( ei2->bei_kids || !ei2->bei_id ))
+ bdb->bi_cache.c_leaves++;
+ ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
+
+gotparent:
+ /* Got the parent, link in and we're done. */
+ if ( ei2 ) {
+ bdb_cache_entryinfo_lock( eir );
+ ein->bei_parent = ei2;
+
+ if ( avl_insert( &ei2->bei_kids, (caddr_t)ein, bdb_rdn_cmp,
+ avl_dup_error) == 0 )
+ ei2->bei_ckids++;
+
+ /* Reset all the state info */
+ for (ein = eir; ein != ei2; ein=ein->bei_parent)
+ ein->bei_state &= ~CACHE_ENTRY_NOT_LINKED;
+
+ bdb_cache_entryinfo_unlock( ei2 );
+ eir->bei_finders--;
+
+ *res = eir;
+ break;
+ }
+ ei.bei_kids = NULL;
+ ei.bei_id = eip.bei_id;
+ ei.bei_ckids = 1;
+ avl_insert( &ei.bei_kids, (caddr_t)ein, bdb_rdn_cmp,
+ avl_dup_error );
+ }
+ return rc;
+}
+
+/* Used by hdb_dn2idl when loading the EntryInfo for all the children
+ * of a given node
+ */
+int hdb_cache_load(
+ struct bdb_info *bdb,
+ EntryInfo *ei,
+ EntryInfo **res )
+{
+ EntryInfo *ei2;
+ int rc;
+
+ /* See if we already have this one */
+ bdb_cache_entryinfo_lock( ei->bei_parent );
+ ei2 = (EntryInfo *)avl_find( ei->bei_parent->bei_kids, ei, bdb_rdn_cmp );
+ bdb_cache_entryinfo_unlock( ei->bei_parent );
+
+ if ( !ei2 ) {
+ /* Not found, add it */
+ struct berval bv;
+
+ /* bei_rdn was not malloc'd before, do it now */
+ ber_dupbv( &bv, &ei->bei_rdn );
+ ei->bei_rdn = bv;
+
+ rc = bdb_entryinfo_add_internal( bdb, ei, res );
+ bdb_cache_entryinfo_unlock( ei->bei_parent );
+ ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
+ } else {
+ /* Found, return it */
+ *res = ei2;
+ return 0;
+ }
+ return rc;
+}
+#endif
+
+/* This is best-effort only. If all entries in the cache are
+ * busy, they will all be kept. This is unlikely to happen
+ * unless the cache is very much smaller than the working set.
+ */
+static void
+bdb_cache_lru_purge( struct bdb_info *bdb )
+{
+ DB_LOCK lock, *lockp;
+ EntryInfo *elru, *elnext = NULL;
+ int islocked;
+ ID eicount, ecount;
+ ID count, efree, eifree = 0;
+#ifdef LDAP_DEBUG
+ int iter;
+#endif
+
+ /* Wait for the mutex; we're the only one trying to purge. */
+ ldap_pvt_thread_mutex_lock( &bdb->bi_cache.c_lru_mutex );
+
+ if ( bdb->bi_cache.c_cursize > bdb->bi_cache.c_maxsize ) {
+ efree = bdb->bi_cache.c_cursize - bdb->bi_cache.c_maxsize;
+ efree += bdb->bi_cache.c_minfree;
+ } else {
+ efree = 0;
+ }
+
+ /* maximum number of EntryInfo leaves to cache. In slapcat
+ * we always free all leaf nodes.
+ */
+
+ if ( slapMode & SLAP_TOOL_READONLY ) {
+ eifree = bdb->bi_cache.c_leaves;
+ } else if ( bdb->bi_cache.c_eimax &&
+ bdb->bi_cache.c_leaves > bdb->bi_cache.c_eimax ) {
+ eifree = bdb->bi_cache.c_minfree * 10;
+ if ( eifree >= bdb->bi_cache.c_leaves )
+ eifree /= 2;
+ }
+
+ if ( !efree && !eifree ) {
+ ldap_pvt_thread_mutex_unlock( &bdb->bi_cache.c_lru_mutex );
+ bdb->bi_cache.c_purging = 0;
+ return;
+ }
+
+ if ( bdb->bi_cache.c_txn ) {
+ lockp = &lock;
+ } else {
+ lockp = NULL;
+ }
+
+ count = 0;
+ eicount = 0;
+ ecount = 0;
+#ifdef LDAP_DEBUG
+ iter = 0;
+#endif
+
+ /* Look for an unused entry to remove */
+ for ( elru = bdb->bi_cache.c_lruhead; elru; elru = elnext ) {
+ elnext = elru->bei_lrunext;
+
+ if ( bdb_cache_entryinfo_trylock( elru ))
+ goto bottom;
+
+ /* This flag implements the clock replacement behavior */
+ if ( elru->bei_state & ( CACHE_ENTRY_REFERENCED )) {
+ elru->bei_state &= ~CACHE_ENTRY_REFERENCED;
+ bdb_cache_entryinfo_unlock( elru );
+ goto bottom;
+ }
+
+ /* If this node is in the process of linking into the cache,
+ * or this node is being deleted, skip it.
+ */
+ if (( elru->bei_state & ( CACHE_ENTRY_NOT_LINKED |
+ CACHE_ENTRY_DELETED | CACHE_ENTRY_LOADING |
+ CACHE_ENTRY_ONELEVEL )) ||
+ elru->bei_finders > 0 ) {
+ bdb_cache_entryinfo_unlock( elru );
+ goto bottom;
+ }
+
+ if ( bdb_cache_entryinfo_trylock( elru->bei_parent )) {
+ bdb_cache_entryinfo_unlock( elru );
+ goto bottom;
+ }
+
+ /* entryinfo is locked */
+ islocked = 1;
+
+ /* If we can successfully writelock it, then
+ * the object is idle.
+ */
+ if ( bdb_cache_entry_db_lock( bdb,
+ bdb->bi_cache.c_txn, elru, 1, 1, lockp ) == 0 ) {
+
+ /* Free entry for this node if it's present */
+ if ( elru->bei_e ) {
+ ecount++;
+
+ /* the cache may have gone over the limit while we
+ * weren't looking, so double check.
+ */
+ if ( !efree && ecount > bdb->bi_cache.c_maxsize )
+ efree = bdb->bi_cache.c_minfree;
+
+ if ( count < efree ) {
+ elru->bei_e->e_private = NULL;
+#ifdef SLAP_ZONE_ALLOC
+ bdb_entry_return( bdb, elru->bei_e, elru->bei_zseq );
+#else
+ bdb_entry_return( elru->bei_e );
+#endif
+ elru->bei_e = NULL;
+ count++;
+ } else {
+ /* Keep this node cached, skip to next */
+ bdb_cache_entry_db_unlock( bdb, lockp );
+ goto next;
+ }
+ }
+ bdb_cache_entry_db_unlock( bdb, lockp );
+
+ /*
+ * If it is a leaf node, and we're over the limit, free it.
+ */
+ if ( elru->bei_kids ) {
+ /* Drop from list, we ignore it... */
+ LRU_DEL( &bdb->bi_cache, elru );
+ } else if ( eicount < eifree ) {
+ /* Too many leaf nodes, free this one */
+ bdb_cache_delete_internal( &bdb->bi_cache, elru, 0 );
+ bdb_cache_delete_cleanup( &bdb->bi_cache, elru );
+ islocked = 0;
+ eicount++;
+ } /* Leave on list until we need to free it */
+ }
+
+next:
+ if ( islocked ) {
+ bdb_cache_entryinfo_unlock( elru );
+ bdb_cache_entryinfo_unlock( elru->bei_parent );
+ }
+
+ if ( count >= efree && eicount >= eifree )
+ break;
+bottom:
+ if ( elnext == bdb->bi_cache.c_lruhead )
+ break;
+#ifdef LDAP_DEBUG
+ iter++;
+#endif
+ }
+
+ if ( count || ecount > bdb->bi_cache.c_cursize ) {
+ ldap_pvt_thread_mutex_lock( &bdb->bi_cache.c_count_mutex );
+ /* HACK: we seem to be losing track, fix up now */
+ if ( ecount > bdb->bi_cache.c_cursize )
+ bdb->bi_cache.c_cursize = ecount;
+ bdb->bi_cache.c_cursize -= count;
+ ldap_pvt_thread_mutex_unlock( &bdb->bi_cache.c_count_mutex );
+ }
+ bdb->bi_cache.c_lruhead = elnext;
+ ldap_pvt_thread_mutex_unlock( &bdb->bi_cache.c_lru_mutex );
+ bdb->bi_cache.c_purging = 0;
+}
+