git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/cache.c

   1 /* cache.c - routines to maintain an in-core cache of entries */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11
  12 #include <ac/errno.h>
  13 #include <ac/string.h>
  14 #include <ac/socket.h>
  15
  16 #include "slap.h"
  17
  18 #include "back-bdb.h"
  19
  20 static int      bdb_cache_delete_internal(Cache *cache, EntryInfo *e);
  21 #ifdef LDAP_DEBUG
  22 static void     bdb_lru_print(Cache *cache);
  23 #endif
  24
  25 static EntryInfo *
  26 bdb_cache_entryinfo_new( )
  27 {
  28         EntryInfo *ei;
  29
  30         ei = ch_calloc(1, sizeof(struct bdb_entry_info));
  31         ldap_pvt_thread_mutex_init( &ei->bei_kids_mutex );
  32
  33         return ei;
  34 }
  35
  36 /* Atomically release and reacquire a lock */
  37 #if LDAP_SYNC
  38 int
  39 #else
  40 static int
  41 #endif
  42 bdb_cache_entry_db_relock(
  43         DB_ENV *env,
  44         u_int32_t locker,
  45         EntryInfo *ei,
  46         int rw,
  47         int tryOnly,
  48         DB_LOCK *lock )
  49 {
  50 #ifdef NO_THREADS
  51         return 0;
  52 #else
  53         int     rc;
  54         DBT     lockobj;
  55         DB_LOCKREQ list[2];
  56
  57         if ( !lock ) return 0;
  58
  59         lockobj.data = ei;
  60         lockobj.size = sizeof(ei->bei_parent) + sizeof(ei->bei_id);
  61
  62         list[0].op = DB_LOCK_PUT;
  63         list[0].lock = *lock;
  64         list[1].op = DB_LOCK_GET;
  65         list[1].lock = *lock;
  66         list[1].mode = rw ? DB_LOCK_WRITE : DB_LOCK_READ;
  67         list[1].obj = &lockobj;
  68         rc = env->lock_vec(env, locker, tryOnly ? DB_LOCK_NOWAIT : 0,
  69                 list, 2, NULL );
  70
  71         if (rc) {
  72 #ifdef NEW_LOGGING
  73                 LDAP_LOG( CACHE, DETAIL1,
  74                         "bdb_cache_entry_db_relock: entry %ld, rw %d, rc %d\n",
  75                         ei->bei_id, rw, rc );
  76 #else
  77                 Debug( LDAP_DEBUG_TRACE,
  78                         "bdb_cache_entry_db_relock: entry %ld, rw %d, rc %d\n",
  79                         ei->bei_id, rw, rc );
  80 #endif
  81         } else {
  82                 *lock = list[1].lock;
  83         }
  84         return rc;
  85 #endif
  86 }
  87 static int
  88 bdb_cache_entry_db_lock
  89 ( DB_ENV *env, u_int32_t locker, EntryInfo *ei, int rw, int tryOnly, DB_LOCK *lock )
  90 {
  91 #ifdef NO_THREADS
  92         return 0;
  93 #else
  94         int       rc;
  95         DBT       lockobj;
  96         int       db_rw;
  97
  98         if ( !lock ) return 0;
  99
 100         if (rw)
 101                 db_rw = DB_LOCK_WRITE;
 102         else
 103                 db_rw = DB_LOCK_READ;
 104
 105         lockobj.data = ei;
 106         lockobj.size = sizeof(ei->bei_parent) + sizeof(ei->bei_id);
 107
 108         rc = LOCK_GET(env, locker, tryOnly ? DB_LOCK_NOWAIT : 0,
 109                                         &lockobj, db_rw, lock);
 110         if (rc) {
 111 #ifdef NEW_LOGGING
 112                 LDAP_LOG( CACHE, DETAIL1,
 113                         "bdb_cache_entry_db_lock: entry %ld, rw %d, rc %d\n",
 114                         ei->bei_id, rw, rc );
 115 #else
 116                 Debug( LDAP_DEBUG_TRACE,
 117                         "bdb_cache_entry_db_lock: entry %ld, rw %d, rc %d\n",
 118                         ei->bei_id, rw, rc );
 119 #endif
 120         }
 121         return rc;
 122 #endif /* NO_THREADS */
 123 }
 124
 125 int
 126 bdb_cache_entry_db_unlock
 127 ( DB_ENV *env, DB_LOCK *lock )
 128 {
 129 #ifdef NO_THREADS
 130         return 0;
 131 #else
 132         int rc;
 133
 134         rc = LOCK_PUT ( env, lock );
 135         return rc;
 136 #endif
 137 }
 138
 139 static int
 140 bdb_cache_entryinfo_destroy( EntryInfo *e )
 141 {
 142         ldap_pvt_thread_mutex_destroy( &e->bei_kids_mutex );
 143         free( e->bei_nrdn.bv_val );
 144 #ifdef BDB_HIER
 145         free( e->bei_rdn.bv_val );
 146 #endif
 147         free( e );
 148         return 0;
 149 }
 150
 151 #define LRU_DELETE( cache, ei ) do { \
 152         if ( (ei)->bei_lruprev != NULL ) { \
 153                 (ei)->bei_lruprev->bei_lrunext = (ei)->bei_lrunext; \
 154         } else { \
 155                 (cache)->c_lruhead = (ei)->bei_lrunext; \
 156         } \
 157         if ( (ei)->bei_lrunext != NULL ) { \
 158                 (ei)->bei_lrunext->bei_lruprev = (ei)->bei_lruprev; \
 159         } else { \
 160                 (cache)->c_lrutail = (ei)->bei_lruprev; \
 161         } \
 162 } while(0)
 163
 164 #define LRU_ADD( cache, ei ) do { \
 165         (ei)->bei_lrunext = (cache)->c_lruhead; \
 166         if ( (ei)->bei_lrunext != NULL ) { \
 167                 (ei)->bei_lrunext->bei_lruprev = (ei); \
 168         } \
 169         (cache)->c_lruhead = (ei); \
 170         (ei)->bei_lruprev = NULL; \
 171         if ( (cache)->c_lrutail == NULL ) { \
 172                 (cache)->c_lrutail = (ei); \
 173         } \
 174 } while(0)
 175
 176 /* Do a length-ordered sort on normalized RDNs */
 177 static int
 178 bdb_rdn_cmp( const void *v_e1, const void *v_e2 )
 179 {
 180         const EntryInfo *e1 = v_e1, *e2 = v_e2;
 181         int rc = e1->bei_nrdn.bv_len - e2->bei_nrdn.bv_len;
 182         if (rc == 0) rc = strncmp( e1->bei_nrdn.bv_val, e2->bei_nrdn.bv_val,
 183                 e1->bei_nrdn.bv_len );
 184         return rc;
 185 }
 186
 187 static int
 188 bdb_id_cmp( const void *v_e1, const void *v_e2 )
 189 {
 190         const EntryInfo *e1 = v_e1, *e2 = v_e2;
 191         return e1->bei_id - e2->bei_id;
 192 }
 193
 194 /* Create an entryinfo in the cache. Caller must release the locks later.
 195  */
 196 static int
 197 bdb_entryinfo_add_internal(
 198         struct bdb_info *bdb,
 199         EntryInfo *ei,
 200         EntryInfo **res,
 201         u_int32_t locker
 202 )
 203 {
 204         Cache *cache = &bdb->bi_cache;
 205         DB_ENV *env = bdb->bi_dbenv;
 206         EntryInfo *ei2 = NULL;
 207         int incr = 1;
 208         int addkid = 1;
 209         int rc;
 210         DB_LOCK lock;
 211
 212         *res = NULL;
 213
 214         ldap_pvt_thread_rdwr_wlock( &bdb->bi_cache.c_rwlock );
 215         bdb_cache_entryinfo_lock( ei->bei_parent );
 216
 217         /* if parent was previously considered a leaf node,
 218          * it was on the LRU list. Now it's going to have
 219          * kids, take it off the LRU list.
 220          */
 221         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 222         if ( ei->bei_parent->bei_id && !ei->bei_parent->bei_kids ) {
 223                 LRU_DELETE( cache, ei->bei_parent );
 224                 incr = 0;
 225         }
 226
 227         cache->c_cursize += incr;
 228
 229         /* See if we're above the cache size limit */
 230         if ( cache->c_cursize > cache->c_maxsize ) {
 231                 EntryInfo *elru, *elprev;
 232                 int i = 0;
 233
 234                 /* Look for an unused entry to remove */
 235                 for (elru = cache->c_lrutail; elru; elru = elprev, i++ ) {
 236                         elprev = elru->bei_lruprev;
 237
 238                         /* Too many probes, not enough idle, give up */
 239                         if (i > 10) break;
 240
 241                         /* If we can successfully writelock it, then
 242                          * the object is idle.
 243                          */
 244                         if ( bdb_cache_entry_db_lock( env, locker, elru, 1, 1,
 245                                 &lock ) == 0 ) {
 246                                 if ( !elru->bei_e ) {
 247                                         bdb_cache_entry_db_unlock( env, &lock );
 248                                         continue;
 249                                 }
 250                                 /* Need to lock parent to delete child */
 251                                 if ( ldap_pvt_thread_mutex_trylock(
 252                                         &elru->bei_parent->bei_kids_mutex )) {
 253                                         bdb_cache_entry_db_unlock( env, &lock );
 254                                         continue;
 255                                 }
 256                                 bdb_cache_delete_internal( cache, elru );
 257                                 bdb_cache_entryinfo_unlock( elru->bei_parent );
 258                                 elru->bei_e->e_private = NULL;
 259                                 bdb_entry_return( elru->bei_e );
 260                                 bdb_cache_entry_db_unlock( env, &lock );
 261                                 if (ei2) {
 262                                         bdb_cache_entryinfo_destroy( elru );
 263                                 } else {
 264                                         /* re-use this one */
 265                                         ch_free(elru->bei_nrdn.bv_val);
 266                                         elru->bei_nrdn.bv_val = NULL;
 267                                         elru->bei_e = NULL;
 268                                         elru->bei_kids = NULL;
 269                                         elru->bei_lrunext = NULL;
 270                                         elru->bei_lruprev = NULL;
 271                                         elru->bei_state = 0;
 272 #ifdef BDB_HIER
 273                                         ch_free(elru->bei_rdn.bv_val);
 274                                         elru->bei_rdn.bv_val = NULL;
 275                                         elru->bei_modrdns = 0;
 276 #endif
 277                                         ei2 = elru;
 278                                 }
 279                                 if (cache->c_cursize < cache->c_maxsize)
 280                                         break;
 281                         }
 282                 }
 283         }
 284         if (!ei2) {
 285                 ei2 = bdb_cache_entryinfo_new();
 286         }
 287         ei2->bei_id = ei->bei_id;
 288         ei2->bei_parent = ei->bei_parent;
 289 #ifdef BDB_HIER
 290         ei2->bei_rdn = ei->bei_rdn;
 291 #endif
 292
 293         /* Add to cache ID tree */
 294         if (avl_insert( &cache->c_idtree, ei2, bdb_id_cmp, avl_dup_error )) {
 295                 EntryInfo *eix;
 296                 eix = avl_find( cache->c_idtree, ei2, bdb_id_cmp );
 297                 bdb_cache_entryinfo_destroy( ei2 );
 298                 ei2 = eix;
 299                 addkid = 0;
 300                 cache->c_cursize -= incr;
 301 #ifdef BDB_HIER
 302                 /* It got freed above because its value was
 303                  * assigned to ei2.
 304                  */
 305                 ei->bei_rdn.bv_val = NULL;
 306 #endif
 307         } else {
 308                 LRU_ADD( cache, ei2 );
 309                 ber_dupbv( &ei2->bei_nrdn, &ei->bei_nrdn );
 310         }
 311
 312         if ( addkid ) {
 313                 avl_insert( &ei->bei_parent->bei_kids, ei2, bdb_rdn_cmp,
 314                         avl_dup_error );
 315         }
 316
 317         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 318
 319         *res = ei2;
 320         return 0;
 321 }
 322
 323 /* Find the EntryInfo for the requested DN. If the DN cannot be found, return
 324  * the info for its closest ancestor. *res should be NULL to process a
 325  * complete DN starting from the tree root. Otherwise *res must be the
 326  * immediate parent of the requested DN, and only the RDN will be searched.
 327  * The EntryInfo is locked upon return and must be unlocked by the caller.
 328  */
 329 int
 330 bdb_cache_find_ndn(
 331         Operation       *op,
 332         DB_TXN          *txn,
 333         struct berval   *ndn,
 334         EntryInfo       **res,
 335         u_int32_t       locker
 336 )
 337 {
 338         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 339         EntryInfo       ei, *eip, *ei2;
 340         int rc = 0;
 341         char *ptr;
 342
 343         /* this function is always called with normalized DN */
 344         if ( *res ) {
 345                 /* we're doing a onelevel search for an RDN */
 346                 ei.bei_nrdn.bv_val = ndn->bv_val;
 347                 ei.bei_nrdn.bv_len = dn_rdnlen( op->o_bd, ndn );
 348                 eip = *res;
 349         } else {
 350                 /* we're searching a full DN from the root */
 351                 ptr = ndn->bv_val + ndn->bv_len - op->o_bd->be_nsuffix[0].bv_len;
 352                 ei.bei_nrdn.bv_val = ptr;
 353                 ei.bei_nrdn.bv_len = op->o_bd->be_nsuffix[0].bv_len;
 354                 eip = &bdb->bi_cache.c_dntree;
 355         }
 356
 357         for ( bdb_cache_entryinfo_lock( eip ); eip; ) {
 358                 ei.bei_parent = eip;
 359                 ei2 = (EntryInfo *)avl_find( eip->bei_kids, &ei, bdb_rdn_cmp );
 360                 if ( !ei2 ) {
 361                         int len = ei.bei_nrdn.bv_len;
 362
 363                         ei.bei_nrdn.bv_len = ndn->bv_len - (ei.bei_nrdn.bv_val - ndn->bv_val);
 364                         bdb_cache_entryinfo_unlock( eip );
 365
 366                         rc = bdb_dn2id( op, txn, &ei.bei_nrdn, &ei );
 367                         if (rc) {
 368                                 bdb_cache_entryinfo_lock( eip );
 369                                 *res = eip;
 370                                 return rc;
 371                         }
 372
 373                         /* DN exists but needs to be added to cache */
 374                         ei.bei_nrdn.bv_len = len;
 375                         rc = bdb_entryinfo_add_internal( bdb, &ei, &ei2,
 376                                 locker );
 377                         /* add_internal left eip and c_rwlock locked */
 378                         ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
 379                         if ( rc ) {
 380                                 *res = eip;
 381                                 return rc;
 382                         }
 383                 } else if ( ei2->bei_state & CACHE_ENTRY_DELETED ) {
 384                         /* In the midst of deleting? Give it a chance to
 385                          * complete.
 386                          */
 387                         bdb_cache_entryinfo_unlock( eip );
 388                         ldap_pvt_thread_yield();
 389                         bdb_cache_entryinfo_lock( eip );
 390                         *res = eip;
 391                         return DB_NOTFOUND;
 392                 }
 393                 bdb_cache_entryinfo_unlock( eip );
 394                 bdb_cache_entryinfo_lock( ei2 );
 395
 396                 eip = ei2;
 397
 398                 /* Advance to next lower RDN */
 399                 for (ptr = ei.bei_nrdn.bv_val - 2; ptr > ndn->bv_val
 400                         && !DN_SEPARATOR(*ptr); ptr--);
 401                 if ( ptr >= ndn->bv_val ) {
 402                         if (DN_SEPARATOR(*ptr)) ptr++;
 403                         ei.bei_nrdn.bv_len = ei.bei_nrdn.bv_val - ptr - 1;
 404                         ei.bei_nrdn.bv_val = ptr;
 405                 }
 406                 if ( ptr < ndn->bv_val ) {
 407                         *res = eip;
 408                         break;
 409                 }
 410         }
 411
 412         return rc;
 413 }
 414
 415 #ifdef BDB_HIER
 416 /* Walk up the tree from a child node, looking for an ID that's already
 417  * been linked into the cache.
 418  */
 419 static int
 420 hdb_cache_find_parent(
 421         Operation *op,
 422         DB_TXN *txn,
 423         ID id,
 424         EntryInfo **res
 425 )
 426 {
 427         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 428         EntryInfo ei, eip, *ei2 = NULL, *ein = NULL, *eir = NULL;
 429         ID parent;
 430         int rc;
 431
 432         ei.bei_id = id;
 433         ei.bei_kids = NULL;
 434
 435         for (;;) {
 436                 rc = hdb_dn2id_parent( op, txn, &ei, &eip.bei_id );
 437                 if ( rc ) break;
 438
 439                 /* Save the previous node, if any */
 440                 ei2 = ein;
 441
 442                 /* Create a new node for the current ID */
 443                 ein = bdb_cache_entryinfo_new();
 444                 ein->bei_id = ei.bei_id;
 445                 ein->bei_kids = ei.bei_kids;
 446                 ein->bei_nrdn = ei.bei_nrdn;
 447                 ein->bei_rdn = ei.bei_rdn;
 448
 449                 /* This node is not fully connected yet */
 450                 ein->bei_state = CACHE_ENTRY_NOT_LINKED;
 451
 452                 /* Insert this node into the ID tree */
 453                 ldap_pvt_thread_rdwr_wlock( &bdb->bi_cache.c_rwlock );
 454                 if ( avl_insert( &bdb->bi_cache.c_idtree, (caddr_t)ein,
 455                         bdb_id_cmp, avl_dup_error ) ) {
 456
 457                         /* Hm, can this really happen? */
 458                         bdb_cache_entryinfo_destroy( ein );
 459                         ein = (EntryInfo *)avl_find( bdb->bi_cache.c_idtree,
 460                                 (caddr_t) &ei, bdb_id_cmp );
 461                         if ( ei2 ) {
 462                                 bdb_cache_entryinfo_lock( ein );
 463                                 avl_insert( &ein->bei_kids, (caddr_t)ei2,
 464                                         bdb_rdn_cmp, avl_dup_error );
 465                                 bdb_cache_entryinfo_unlock( ein );
 466                         }
 467                 }
 468
 469                 /* If this is the first time, save this node
 470                  * to be returned later.
 471                  */
 472                 if ( eir == NULL ) eir = ein;
 473
 474                 /* If there was a previous node, link it to this one */
 475                 if ( ei2 ) ei2->bei_parent = ein;
 476
 477                 if ( eip.bei_id ) {
 478                         ei2 = (EntryInfo *) avl_find( bdb->bi_cache.c_idtree,
 479                                         (caddr_t) &eip, bdb_id_cmp );
 480                 } else {
 481                         ei2 = &bdb->bi_cache.c_dntree;
 482                 }
 483
 484                 if ( ei2 ) {
 485                         ein->bei_parent = ei2;
 486                         bdb_cache_entryinfo_lock( ei2 );
 487                         avl_insert( &ei2->bei_kids, (caddr_t)ein, bdb_rdn_cmp,
 488                                 avl_dup_error);
 489                         bdb_cache_entryinfo_unlock( ei2 );
 490                         *res = eir;
 491                         bdb_cache_entryinfo_lock( eir );
 492                 }
 493                 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
 494                 if ( ei2 ) {
 495                         /* Found a link. Reset all the state info */
 496                         for (ein = eir; ein != ei2; ein=ein->bei_parent)
 497                                 ein->bei_state &= ~CACHE_ENTRY_NOT_LINKED;
 498                         break;
 499                 }
 500                 ei.bei_kids = NULL;
 501                 ei.bei_id = eip.bei_id;
 502                 avl_insert( &ei.bei_kids, (caddr_t)ein, bdb_rdn_cmp,
 503                         avl_dup_error );
 504         }
 505         return rc;
 506 }
 507 #endif
 508
 509 /*
 510  * cache_find_id - find an entry in the cache, given id.
 511  * The entry is locked for Read upon return. Call with islocked TRUE if
 512  * the supplied *eip was already locked.
 513  */
 514
 515 int
 516 bdb_cache_find_id(
 517         Operation *op,
 518         DB_TXN  *tid,
 519         ID                              id,
 520         EntryInfo       **eip,
 521         int             islocked,
 522         u_int32_t       locker,
 523         DB_LOCK         *lock
 524 )
 525 {
 526         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 527         Entry   *ep = NULL;
 528         int     rc = 0;
 529         EntryInfo ei;
 530
 531         ei.bei_id = id;
 532
 533         /* If we weren't given any info, see if we have it already cached */
 534         if ( !*eip ) {
 535 again:          ldap_pvt_thread_rdwr_rlock( &bdb->bi_cache.c_rwlock );
 536                 *eip = (EntryInfo *) avl_find( bdb->bi_cache.c_idtree,
 537                                         (caddr_t) &ei, bdb_id_cmp );
 538                 if ( *eip ) {
 539                         if ( ldap_pvt_thread_mutex_trylock(
 540                                         &(*eip)->bei_kids_mutex )) {
 541                                 ldap_pvt_thread_rdwr_runlock( &bdb->bi_cache.c_rwlock );
 542                                 if ( (*eip)->bei_state & CACHE_ENTRY_DELETED ) {
 543                                         return DB_NOTFOUND;
 544                                 }
 545                                 ldap_pvt_thread_yield();
 546                                 goto again;
 547                         }
 548                         islocked = 1;
 549                 }
 550                 ldap_pvt_thread_rdwr_runlock( &bdb->bi_cache.c_rwlock );
 551         }
 552
 553         /* See if the ID exists in the database; add it to the cache if so */
 554         if ( !*eip ) {
 555 #ifndef BDB_HIER
 556                 rc = bdb_id2entry( op->o_bd, tid, id, &ep );
 557                 if ( rc == 0 ) {
 558                         rc = bdb_cache_find_ndn( op, tid,
 559                                 &ep->e_nname, eip, locker );
 560                         if ( *eip )
 561                                 islocked = 1;
 562                         if ( rc ) {
 563                                 bdb_entry_return( ep );
 564                                 ep = NULL;
 565                         }
 566                 }
 567 #else
 568                 rc = hdb_cache_find_parent(op, tid, id, eip );
 569                 if ( rc == 0 && *eip )
 570                         islocked = 1;
 571 #endif
 572         }
 573
 574         /* Ok, we found the info, do we have the entry? */
 575         if ( *eip && rc == 0 ) {
 576                 if ( (*eip)->bei_state & CACHE_ENTRY_DELETED ) {
 577                         rc = DB_NOTFOUND;
 578                 } else {
 579                         bdb_cache_entry_db_lock( bdb->bi_dbenv, locker,
 580                                         *eip, 0, 0, lock );
 581                         if ( !(*eip)->bei_e ) {
 582                                 if (!ep) {
 583                                         rc = bdb_id2entry( op->o_bd, tid, id, &ep );
 584                                 }
 585                                 if ( rc == 0 ) {
 586                                         bdb_cache_entry_db_relock( bdb->bi_dbenv, locker,
 587                                                 *eip, 1, 0, lock );
 588                                         /* Make sure no other modifier beat us to it */
 589                                         if ( (*eip)->bei_e ) {
 590                                                 bdb_entry_return( ep );
 591                                                 ep = NULL;
 592                                         } else {
 593                                                 ep->e_private = *eip;
 594 #ifdef BDB_HIER
 595                                                 bdb_fix_dn( ep, 0 );
 596 #endif
 597                                                 (*eip)->bei_e = ep;
 598                                         }
 599                                         bdb_cache_entry_db_relock( bdb->bi_dbenv, locker,
 600                                                 *eip, 0, 0, lock );
 601                                 }
 602                         }
 603 #ifdef BDB_HIER
 604                         else {
 605                                 rc = bdb_fix_dn( (*eip)->bei_e, 1 );
 606                                 if ( rc ) {
 607                                         bdb_cache_entry_db_relock( bdb->bi_dbenv,
 608                                                 locker, *eip, 1, 0, lock );
 609                                         /* check again in case other modifier did it already */
 610                                         if ( bdb_fix_dn( (*eip)->bei_e, 1 ) )
 611                                                 rc = bdb_fix_dn( (*eip)->bei_e, 2 );
 612                                         bdb_cache_entry_db_relock( bdb->bi_dbenv,
 613                                                 locker, *eip, 0, 0, lock );
 614                                 }
 615                         }
 616 #endif
 617                 }
 618         }
 619         if ( rc == 0 && (*eip)->bei_kids == NULL ) {
 620                 /* set lru mutex */
 621                 ldap_pvt_thread_mutex_lock( &bdb->bi_cache.lru_mutex );
 622                 LRU_DELETE( &bdb->bi_cache, *eip );
 623                 LRU_ADD( &bdb->bi_cache, *eip );
 624                 ldap_pvt_thread_mutex_unlock( &bdb->bi_cache.lru_mutex );
 625         }
 626
 627         if ( islocked ) {
 628                 bdb_cache_entryinfo_unlock( *eip );
 629         }
 630         return rc;
 631 }
 632
 633 int
 634 bdb_cache_children(
 635         Operation *op,
 636         DB_TXN *txn,
 637         Entry *e
 638 )
 639 {
 640         int rc;
 641
 642         if ( BEI(e)->bei_kids ) {
 643                 return 0;
 644         }
 645         if ( BEI(e)->bei_state & CACHE_ENTRY_NO_KIDS ) {
 646                 return DB_NOTFOUND;
 647         }
 648         rc = bdb_dn2id_children( op, txn, e );
 649         if ( rc == DB_NOTFOUND ) {
 650                 BEI(e)->bei_state |= CACHE_ENTRY_NO_KIDS;
 651         }
 652         return rc;
 653 }
 654
 655 /* Update the cache after a successful database Add. */
 656 int
 657 bdb_cache_add(
 658         struct bdb_info *bdb,
 659         EntryInfo *eip,
 660         Entry *e,
 661         struct berval *nrdn,
 662         u_int32_t locker
 663 )
 664 {
 665         EntryInfo *new, ei;
 666         struct berval rdn = e->e_name;
 667         int rc;
 668
 669         ei.bei_id = e->e_id;
 670         ei.bei_parent = eip;
 671         ei.bei_nrdn = *nrdn;
 672 #ifdef BDB_HIER
 673         if ( nrdn->bv_len != e->e_nname.bv_len ) {
 674                 char *ptr = strchr( rdn.bv_val, ',' );
 675                 rdn.bv_len = ptr - rdn.bv_val;
 676         }
 677         ber_dupbv( &ei.bei_rdn, &rdn );
 678 #endif
 679         rc = bdb_entryinfo_add_internal( bdb, &ei, &new, locker );
 680         new->bei_e = e;
 681         e->e_private = new;
 682         new->bei_state = CACHE_ENTRY_NO_KIDS;
 683         eip->bei_state &= ~CACHE_ENTRY_NO_KIDS;
 684         bdb_cache_entryinfo_unlock( eip );
 685         ldap_pvt_thread_rdwr_wunlock( &bdb->bi_cache.c_rwlock );
 686         return rc;
 687 }
 688
 689 int
 690 bdb_cache_modify(
 691         Entry *e,
 692         Attribute *newAttrs,
 693         DB_ENV *env,
 694         u_int32_t locker,
 695         DB_LOCK *lock
 696 )
 697 {
 698         EntryInfo *ei = BEI(e);
 699
 700         /* Get write lock on data */
 701         bdb_cache_entry_db_relock( env, locker, ei, 1, 0, lock );
 702
 703         /* If we've done repeated mods on a cached entry, then e_attrs
 704          * is no longer contiguous with the entry, and must be freed.
 705          */
 706         if ( (void *)e->e_attrs != (void *)(e+1) ) {
 707                 attrs_free( e->e_attrs );
 708         }
 709         e->e_attrs = newAttrs;
 710
 711         return 0;
 712 }
 713
 714 /*
 715  * Change the rdn in the entryinfo. Also move to a new parent if needed.
 716  */
 717 int
 718 bdb_cache_modrdn(
 719         Entry *e,
 720         struct berval *nrdn,
 721         Entry *new,
 722         EntryInfo *ein,
 723         DB_ENV *env,
 724         u_int32_t locker,
 725         DB_LOCK *lock
 726 )
 727 {
 728         EntryInfo *ei = BEI(e), *pei;
 729         struct berval rdn;
 730         int rc = 0;
 731
 732         /* Get write lock on data */
 733         bdb_cache_entry_db_relock( env, locker, ei, 1, 0, lock );
 734
 735         /* If we've done repeated mods on a cached entry, then e_attrs
 736          * is no longer contiguous with the entry, and must be freed.
 737          */
 738         if ( (void *)e->e_attrs != (void *)(e+1) ) {
 739                 attrs_free( e->e_attrs );
 740         }
 741         e->e_attrs = new->e_attrs;
 742         if( e->e_nname.bv_val < e->e_bv.bv_val || e->e_nname.bv_val >
 743                 e->e_bv.bv_val + e->e_bv.bv_len ) {
 744                 ch_free(e->e_name.bv_val);
 745                 ch_free(e->e_nname.bv_val);
 746         }
 747         e->e_name = new->e_name;
 748         e->e_nname = new->e_nname;
 749
 750         /* Lock the parent's kids AVL tree */
 751         pei = ei->bei_parent;
 752         bdb_cache_entryinfo_lock( pei );
 753         avl_delete( &pei->bei_kids, (caddr_t) ei, bdb_rdn_cmp );
 754         free( ei->bei_nrdn.bv_val );
 755         ber_dupbv( &ei->bei_nrdn, nrdn );
 756 #ifdef BDB_HIER
 757         free( ei->bei_rdn.bv_val );
 758
 759         rdn = e->e_name;
 760         if ( nrdn->bv_len != e->e_nname.bv_len ) {
 761                 char *ptr = strchr(rdn.bv_val, ',');
 762                 rdn.bv_len = ptr - rdn.bv_val;
 763         }
 764         ber_dupbv( &ei->bei_rdn, &rdn );
 765 #endif
 766
 767         if (!ein) {
 768                 ein = ei->bei_parent;
 769         } else {
 770                 ei->bei_parent = ein;
 771                 bdb_cache_entryinfo_unlock( pei );
 772                 bdb_cache_entryinfo_lock( ein );
 773         }
 774 #ifdef BDB_HIER
 775         { int max = ei->bei_modrdns;
 776         /* Record the generation number of this change */
 777                 for ( pei = ein; pei->bei_parent; pei = pei->bei_parent ) {
 778                         if ( pei->bei_modrdns > max )
 779                                 max = pei->bei_modrdns;
 780                 }
 781                 ei->bei_modrdns = max + 1;
 782         }
 783 #endif
 784         avl_insert( &ein->bei_kids, ei, bdb_rdn_cmp, avl_dup_error );
 785         bdb_cache_entryinfo_unlock( ein );
 786         return rc;
 787 }
 788 /*
 789  * cache_delete - delete the entry e from the cache.
 790  *
 791  * returns:     0       e was deleted ok
 792  *              1       e was not in the cache
 793  *              -1      something bad happened
 794  */
 795 int
 796 bdb_cache_delete(
 797     Cache       *cache,
 798     Entry               *e,
 799     DB_ENV      *env,
 800     u_int32_t   locker,
 801     DB_LOCK     *lock
 802 )
 803 {
 804         EntryInfo *ei = BEI(e);
 805         int     rc;
 806
 807         assert( e->e_private );
 808
 809         /* Set this early, warn off any queriers */
 810         ei->bei_state |= CACHE_ENTRY_DELETED;
 811
 812         /* Lock the entry's info */
 813         bdb_cache_entryinfo_lock( ei );
 814
 815         /* Get write lock on the data */
 816         bdb_cache_entry_db_relock( env, locker, ei, 1, 0, lock );
 817
 818         /* set cache write lock */
 819         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 820
 821         /* Lock the parent's kids tree */
 822         bdb_cache_entryinfo_lock( ei->bei_parent );
 823
 824 #ifdef NEW_LOGGING
 825         LDAP_LOG( CACHE, ENTRY,
 826                 "bdb_cache_delete: delete %ld.\n", e->e_id, 0, 0 );
 827 #else
 828         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_delete( %ld )\n",
 829                 e->e_id, 0, 0 );
 830 #endif
 831
 832         /* set lru mutex */
 833         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 834         rc = bdb_cache_delete_internal( cache, e->e_private );
 835         /* free lru mutex */
 836         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 837
 838         /* free cache write lock */
 839         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 840         bdb_cache_entryinfo_unlock( ei->bei_parent );
 841
 842         /* Leave entry info locked */
 843
 844         return( rc );
 845 }
 846
 847 void
 848 bdb_cache_delete_cleanup(
 849         Entry *e
 850 )
 851 {
 852         bdb_cache_entryinfo_unlock( BEI(e) );
 853         bdb_cache_entryinfo_destroy( e->e_private );
 854         e->e_private = NULL;
 855         bdb_entry_return( e );
 856 }
 857
 858 static int
 859 bdb_cache_delete_internal(
 860     Cache       *cache,
 861     EntryInfo           *e
 862 )
 863 {
 864         int rc = 0;     /* return code */
 865
 866         /* dn tree */
 867         if ( avl_delete( &e->bei_parent->bei_kids, (caddr_t) e, bdb_rdn_cmp ) == NULL )
 868         {
 869                 rc = -1;
 870         }
 871
 872         /* If parent has no more kids, put in on LRU list */
 873         if ( e->bei_parent->bei_kids == NULL ) {
 874                 LRU_ADD( cache, e->bei_parent );
 875                 cache->c_cursize++;
 876         }
 877
 878         /* id tree */
 879         if ( avl_delete( &cache->c_idtree, (caddr_t) e, bdb_id_cmp ) == NULL )
 880         {
 881                 rc = -1;
 882         }
 883
 884         if (rc != 0) {
 885                 return rc;
 886         }
 887
 888         /* lru */
 889         LRU_DELETE( cache, e );
 890         cache->c_cursize--;
 891
 892         /*
 893          * flag entry to be freed later by a call to cache_return_entry()
 894          */
 895         e->bei_state |= CACHE_ENTRY_DELETED;
 896
 897         return( 0 );
 898 }
 899
 900 static void
 901 bdb_entryinfo_release( void *data )
 902 {
 903         EntryInfo *ei = (EntryInfo *)data;
 904         if ( ei->bei_kids ) {
 905                 avl_free( ei->bei_kids, NULL );
 906         }
 907         if ( ei->bei_e ) {
 908                 ei->bei_e->e_private = NULL;
 909                 bdb_entry_return( ei->bei_e );
 910         }
 911         bdb_cache_entryinfo_destroy( ei );
 912 }
 913
 914 void
 915 bdb_cache_release_all( Cache *cache )
 916 {
 917         /* set cache write lock */
 918         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 919         /* set lru mutex */
 920         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 921
 922 #ifdef NEW_LOGGING
 923         LDAP_LOG( CACHE, ENTRY, "bdb_cache_release_all: enter\n", 0, 0, 0 );
 924 #else
 925         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_release_all\n", 0, 0, 0 );
 926 #endif
 927
 928         avl_free( cache->c_dntree.bei_kids, NULL );
 929         avl_free( cache->c_idtree, bdb_entryinfo_release );
 930         cache->c_lruhead = NULL;
 931         cache->c_lrutail = NULL;
 932
 933         /* free lru mutex */
 934         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 935         /* free cache write lock */
 936         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 937 }
 938
 939 #ifdef LDAP_DEBUG
 940 static void
 941 bdb_lru_print( Cache *cache )
 942 {
 943         EntryInfo       *e;
 944
 945         fprintf( stderr, "LRU queue (head to tail):\n" );
 946         for ( e = cache->c_lruhead; e != NULL; e = e->bei_lrunext ) {
 947                 fprintf( stderr, "\trdn \"%20s\" id %ld\n",
 948                         e->bei_nrdn.bv_val, e->bei_id );
 949         }
 950         fprintf( stderr, "LRU queue (tail to head):\n" );
 951         for ( e = cache->c_lrutail; e != NULL; e = e->bei_lruprev ) {
 952                 fprintf( stderr, "\trdn \"%20s\" id %ld\n",
 953                         e->bei_nrdn.bv_val, e->bei_id );
 954         }
 955 }
 956 #endif
 957
 958 #ifdef BDB_REUSE_LOCKERS
 959 static void
 960 bdb_locker_id_free( void *key, void *data )
 961 {
 962         DB_ENV *env = key;
 963         int lockid = (int) data;
 964         int rc;
 965
 966
 967         rc = XLOCK_ID_FREE( env, lockid );
 968         if ( rc == EINVAL ) {
 969                 DB_LOCKREQ lr;
 970 #ifdef NEW_LOGGING
 971                 LDAP_LOG( BACK_BDB, ERR,
 972                         "bdb_locker_id_free: %d err %s(%d)\n",
 973                         lockid, db_strerror(rc), rc );
 974 #else
 975                 Debug( LDAP_DEBUG_ANY,
 976                         "bdb_locker_id_free: %d err %s(%d)\n",
 977                         lockid, db_strerror(rc), rc );
 978 #endif
 979                 memset( &lr, 0, sizeof(lr) );
 980
 981                 /* release all locks held by this locker. */
 982                 lr.op = DB_LOCK_PUT_ALL;
 983                 env->lock_vec( env, lockid, 0, &lr, 1, NULL );
 984                 XLOCK_ID_FREE( env, lockid );
 985         }
 986 }
 987
 988 int
 989 bdb_locker_id( Operation *op, DB_ENV *env, int *locker )
 990 {
 991         int i, rc, lockid;
 992         void *data;
 993         void *ctx;
 994
 995         if ( !env || !locker ) return -1;
 996
 997         /* If no op was provided, try to find the ctx anyway... */
 998         if ( op ) {
 999                 ctx = op->o_threadctx;
1000         } else {
1001                 ctx = ldap_pvt_thread_pool_context();
1002         }
1003
1004         /* Shouldn't happen unless we're single-threaded */
1005         if ( !ctx ) {
1006                 *locker = 0;
1007                 return 0;
1008         }
1009
1010         if ( ldap_pvt_thread_pool_getkey( ctx, env, &data, NULL ) ) {
1011                 for ( i=0, rc=1; rc != 0 && i<4; i++ ) {
1012                         rc = XLOCK_ID( env, &lockid );
1013                         if (rc) ldap_pvt_thread_yield();
1014                 }
1015                 if ( rc != 0) {
1016                         return rc;
1017                 }
1018                 data = (void *)lockid;
1019                 if ( ( rc = ldap_pvt_thread_pool_setkey( ctx, env,
1020                         data, bdb_locker_id_free ) ) ) {
1021                         XLOCK_ID_FREE( env, lockid );
1022 #ifdef NEW_LOGGING
1023                         LDAP_LOG( BACK_BDB, ERR, "bdb_locker_id: err %s(%d)\n",
1024                                 db_strerror(rc), rc, 0 );
1025 #else
1026                         Debug( LDAP_DEBUG_ANY, "bdb_locker_id: err %s(%d)\n",
1027                                 db_strerror(rc), rc, 0 );
1028 #endif
1029
1030                         return rc;
1031                 }
1032         } else {
1033                 lockid = (int)data;
1034         }
1035         *locker = lockid;
1036         return 0;
1037 }
1038 #endif