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-2002 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 /* BDB backend specific entry info -- visible only to the cache */
  21 typedef struct bdb_entry_info {
  22         ldap_pvt_thread_rdwr_t  bei_rdwr;       /* reader/writer lock */
  23
  24         /*
  25          * remaining fields require backend cache lock to access
  26          * These items are specific to the BDB backend and should
  27          * be hidden.
  28          */
  29         int             bei_state;      /* for the cache */
  30 #define CACHE_ENTRY_UNDEFINED   0
  31 #define CACHE_ENTRY_CREATING    1
  32 #define CACHE_ENTRY_READY       2
  33 #define CACHE_ENTRY_DELETED     3
  34 #define CACHE_ENTRY_COMMITTED   4
  35
  36         int             bei_refcnt;     /* # threads ref'ing this entry */
  37         Entry   *bei_lrunext;   /* for cache lru list */
  38         Entry   *bei_lruprev;
  39 } EntryInfo;
  40 #undef BEI
  41 #define BEI(e)  ((EntryInfo *) ((e)->e_private))
  42
  43 static int      bdb_cache_delete_entry_internal(Cache *cache, Entry *e);
  44 #ifdef LDAP_DEBUG
  45 static void     bdb_lru_print(Cache *cache);
  46 #endif
  47
  48 static int
  49 bdb_cache_entry_rdwr_lock(Entry *e, int rw)
  50 {
  51 #ifdef NEW_LOGGING
  52         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
  53                    "bdb_cache_entry_rdwr_lock: %s lock on ID %ld\n",
  54                    rw ? "w" : "r", e->e_id ));
  55 #else
  56         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
  57                 rw ? "w" : "r", e->e_id, 0);
  58 #endif
  59
  60         if (rw)
  61                 return ldap_pvt_thread_rdwr_wlock(&BEI(e)->bei_rdwr);
  62         else
  63                 return ldap_pvt_thread_rdwr_rlock(&BEI(e)->bei_rdwr);
  64 }
  65
  66 static int
  67 bdb_cache_entry_rdwr_trylock(Entry *e, int rw)
  68 {
  69 #ifdef NEW_LOGGING
  70         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
  71                    "bdb_cache_entry_rdwr_trylock: try %s lock on ID: %ld.\n",
  72                    rw ? "w" : "r", e->e_id ));
  73 #else
  74         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
  75                 rw ? "w" : "r", e->e_id, 0);
  76 #endif
  77
  78         if (rw)
  79                 return ldap_pvt_thread_rdwr_wtrylock(&BEI(e)->bei_rdwr);
  80         else
  81                 return ldap_pvt_thread_rdwr_rtrylock(&BEI(e)->bei_rdwr);
  82 }
  83
  84 static int
  85 bdb_cache_entry_rdwr_unlock(Entry *e, int rw)
  86 {
  87 #ifdef NEW_LOGGING
  88         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
  89                    "bdb_cache_entry_rdwr_unlock: remove %s lock on ID %ld.\n",
  90                    rw ? "w" : "r", e->e_id ));
  91 #else
  92         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
  93                 rw ? "w" : "r", e->e_id, 0);
  94 #endif
  95
  96         if (rw)
  97                 return ldap_pvt_thread_rdwr_wunlock(&BEI(e)->bei_rdwr);
  98         else
  99                 return ldap_pvt_thread_rdwr_runlock(&BEI(e)->bei_rdwr);
 100 }
 101
 102 static int
 103 bdb_cache_entry_rdwr_init(Entry *e)
 104 {
 105         return ldap_pvt_thread_rdwr_init( &BEI(e)->bei_rdwr );
 106 }
 107
 108 static int
 109 bdb_cache_entry_rdwr_destroy(Entry *e)
 110 {
 111         return ldap_pvt_thread_rdwr_destroy( &BEI(e)->bei_rdwr );
 112 }
 113
 114 static int
 115 bdb_cache_entry_private_init( Entry *e )
 116 {
 117         assert( e->e_private == NULL );
 118
 119         if( e->e_private != NULL ) {
 120                 /* this should never happen */
 121                 return 1;
 122         }
 123
 124         e->e_private = ch_calloc(1, sizeof(struct bdb_entry_info));
 125
 126         if( bdb_cache_entry_rdwr_init( e ) != 0 ) {
 127                 free( BEI(e) );
 128                 e->e_private = NULL;
 129                 return 1;
 130         }
 131
 132         return 0;
 133 }
 134
 135 /*
 136  * marks an entry in CREATING state as committed, so it is really returned
 137  * to the cache. Otherwise an entry in CREATING state is removed.
 138  * Makes e_private be destroyed at the following cache_return_entry_w,
 139  * but lets the entry untouched (owned by someone else)
 140  */
 141 void
 142 bdb_cache_entry_commit( Entry *e )
 143 {
 144         assert( e );
 145         assert( e->e_private );
 146         assert( BEI(e)->bei_state == CACHE_ENTRY_CREATING );
 147         /* assert( BEI(e)->bei_refcnt == 1 ); */
 148
 149         BEI(e)->bei_state = CACHE_ENTRY_COMMITTED;
 150 }
 151
 152 static int
 153 bdb_cache_entry_private_destroy( Entry *e )
 154 {
 155         assert( e->e_private );
 156
 157         bdb_cache_entry_rdwr_destroy( e );
 158
 159         free( e->e_private );
 160         e->e_private = NULL;
 161         return 0;
 162 }
 163
 164 void
 165 bdb_cache_return_entry_rw( Cache *cache, Entry *e, int rw )
 166 {
 167         ID id;
 168         int refcnt, freeit = 1;
 169
 170         /* set cache write lock */
 171         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 172
 173         assert( e->e_private );
 174
 175         bdb_cache_entry_rdwr_unlock(e, rw);
 176
 177         id = e->e_id;
 178         refcnt = --BEI(e)->bei_refcnt;
 179
 180         /*
 181          * if the entry is returned when in CREATING state, it is deleted
 182          * but not freed because it may belong to someone else (do_add,
 183          * for instance)
 184          */
 185         if (  BEI(e)->bei_state == CACHE_ENTRY_CREATING ) {
 186                 /* set lru mutex */
 187                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 188                 bdb_cache_delete_entry_internal( cache, e );
 189                 /* free lru mutex */
 190                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 191                 freeit = 0;
 192                 /* now the entry is in DELETED state */
 193         }
 194
 195         if ( BEI(e)->bei_state == CACHE_ENTRY_COMMITTED ) {
 196                 BEI(e)->bei_state = CACHE_ENTRY_READY;
 197
 198                 /* free cache write lock */
 199                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 200
 201 #ifdef NEW_LOGGING
 202                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 203                            "bdb_cache_return_entry_rw: return (%ld):%s, refcnt=%d\n",
 204                            id, rw ? "w" : "r", refcnt ));
 205 #else
 206                 Debug( LDAP_DEBUG_TRACE,
 207                         "====> bdb_cache_return_entry_%s( %ld ): created (%d)\n",
 208                         rw ? "w" : "r", id, refcnt );
 209 #endif
 210
 211
 212         } else if ( BEI(e)->bei_state == CACHE_ENTRY_DELETED ) {
 213                 if( refcnt > 0 ) {
 214                         /* free cache write lock */
 215                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 216
 217 #ifdef NEW_LOGGING
 218                         LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 219                                    "bdb_cache_return_entry_rw: %ld, delete pending (%d).\n",
 220                                    id, refcnt ));
 221 #else
 222                         Debug( LDAP_DEBUG_TRACE,
 223                                 "====> bdb_cache_return_entry_%s( %ld ): delete pending (%d)\n",
 224                                 rw ? "w" : "r", id, refcnt );
 225 #endif
 226
 227                 } else {
 228                         bdb_cache_entry_private_destroy( e );
 229                         if ( freeit ) {
 230                                 bdb_entry_return( e );
 231                         }
 232
 233                         /* free cache write lock */
 234                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 235
 236 #ifdef NEW_LOGGING
 237                         LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 238                                    "bdb_cache_return_entry_rw: (%ld): deleted (%d)\n",
 239                                    id, refcnt ));
 240 #else
 241                         Debug( LDAP_DEBUG_TRACE,
 242                                 "====> bdb_cache_return_entry_%s( %ld ): deleted (%d)\n",
 243                                 rw ? "w" : "r", id, refcnt );
 244 #endif
 245                 }
 246
 247         } else {
 248                 /* free cache write lock */
 249                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 250
 251 #ifdef NEW_LOGGING
 252                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 253                            "bdb_cache_return_entry_rw: ID %ld:%s returned (%d)\n",
 254                            id, rw ? "w": "r", refcnt ));
 255 #else
 256                 Debug( LDAP_DEBUG_TRACE,
 257                         "====> bdb_cache_return_entry_%s( %ld ): returned (%d)\n",
 258                         rw ? "w" : "r", id, refcnt);
 259 #endif
 260         }
 261 }
 262
 263 #define LRU_DELETE( cache, e ) do { \
 264         if ( BEI(e)->bei_lruprev != NULL ) { \
 265                 BEI(BEI(e)->bei_lruprev)->bei_lrunext = BEI(e)->bei_lrunext; \
 266         } else { \
 267                 (cache)->c_lruhead = BEI(e)->bei_lrunext; \
 268         } \
 269         if ( BEI(e)->bei_lrunext != NULL ) { \
 270                 BEI(BEI(e)->bei_lrunext)->bei_lruprev = BEI(e)->bei_lruprev; \
 271         } else { \
 272                 (cache)->c_lrutail = BEI(e)->bei_lruprev; \
 273         } \
 274 } while(0)
 275
 276 #define LRU_ADD( cache, e ) do { \
 277         BEI(e)->bei_lrunext = (cache)->c_lruhead; \
 278         if ( BEI(e)->bei_lrunext != NULL ) { \
 279                 BEI(BEI(e)->bei_lrunext)->bei_lruprev = (e); \
 280         } \
 281         (cache)->c_lruhead = (e); \
 282         BEI(e)->bei_lruprev = NULL; \
 283         if ( (cache)->c_lrutail == NULL ) { \
 284                 (cache)->c_lrutail = (e); \
 285         } \
 286 } while(0)
 287
 288 /*
 289  * cache_add_entry_rw - create and lock an entry in the cache
 290  * returns:     0       entry has been created and locked
 291  *              1       entry already existed
 292  *              -1      something bad happened
 293  */
 294 int
 295 bdb_cache_add_entry_rw(
 296     Cache       *cache,
 297     Entry       *e,
 298     int         rw
 299 )
 300 {
 301         int     i, rc;
 302         Entry   *ee;
 303
 304 #ifdef NEW_LOGGING
 305         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
 306                    "bdb_cache_add_entry_rw: add (%s):%s to cache\n",
 307                    e->e_dn, rw ? "w" : "r" ));
 308 #endif
 309         /* set cache write lock */
 310         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 311
 312         assert( e->e_private == NULL );
 313
 314         if( bdb_cache_entry_private_init(e) != 0 ) {
 315                 /* free cache write lock */
 316                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 317
 318 #ifdef NEW_LOGGING
 319                 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
 320                            "bdb_cache_add_entry_rw: add (%s):%ld private init failed!\n",
 321                            e->e_dn, e->e_id ));
 322 #else
 323                 Debug( LDAP_DEBUG_ANY,
 324                         "====> bdb_cache_add_entry( %ld ): \"%s\": private init failed!\n",
 325                     e->e_id, e->e_dn, 0 );
 326 #endif
 327
 328
 329                 return( -1 );
 330         }
 331
 332         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 333                 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
 334         {
 335                 /* free cache write lock */
 336                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 337
 338 #ifdef NEW_LOGGING
 339                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 340                            "bdb_cache_add_entry: (%s):%ld already in cache.\n",
 341                            e->e_dn, e->e_id ));
 342 #else
 343                 Debug( LDAP_DEBUG_TRACE,
 344                         "====> bdb_cache_add_entry( %ld ): \"%s\": already in dn cache\n",
 345                     e->e_id, e->e_dn, 0 );
 346 #endif
 347
 348                 bdb_cache_entry_private_destroy(e);
 349
 350                 return( 1 );
 351         }
 352
 353         /* id tree */
 354         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 355                 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
 356         {
 357 #ifdef NEW_LOGGING
 358                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 359                            "bdb_cache_add_entry: (%s):%ls already in cache.\n",
 360                            e->e_dn, e->e_id ));
 361 #else
 362                 Debug( LDAP_DEBUG_ANY,
 363                         "====> bdb_cache_add_entry( %ld ): \"%s\": already in id cache\n",
 364                     e->e_id, e->e_dn, 0 );
 365 #endif
 366
 367                 /* delete from dn tree inserted above */
 368                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 369                         (AVL_CMP) entry_dn_cmp ) == NULL )
 370                 {
 371 #ifdef NEW_LOGGING
 372                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 373                                    "bdb_cache_add_entry: can't delete (%s) from cache.\n",
 374                                    e->e_dn ));
 375 #else
 376                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 377                             0, 0, 0 );
 378 #endif
 379                 }
 380
 381                 bdb_cache_entry_private_destroy(e);
 382
 383                 /* free cache write lock */
 384                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 385                 return( -1 );
 386         }
 387
 388         bdb_cache_entry_rdwr_lock( e, rw );
 389
 390         /* put the entry into 'CREATING' state */
 391         /* will be marked after when entry is returned */
 392         BEI(e)->bei_state = CACHE_ENTRY_CREATING;
 393         BEI(e)->bei_refcnt = 1;
 394
 395         /* set lru mutex */
 396         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 397         /* lru */
 398         LRU_ADD( cache, e );
 399         if ( ++cache->c_cursize > cache->c_maxsize ) {
 400                 /*
 401                  * find the lru entry not currently in use and delete it.
 402                  * in case a lot of entries are in use, only look at the
 403                  * first 10 on the tail of the list.
 404                  */
 405                 i = 0;
 406                 while ( cache->c_lrutail != NULL &&
 407                         BEI(cache->c_lrutail)->bei_refcnt != 0 &&
 408                         i < 10 )
 409                 {
 410                         /* move this in-use entry to the front of the q */
 411                         ee = cache->c_lrutail;
 412                         LRU_DELETE( cache, ee );
 413                         LRU_ADD( cache, ee );
 414                         i++;
 415                 }
 416
 417                 /*
 418                  * found at least one to delete - try to get back under
 419                  * the max cache size.
 420                  */
 421                 while ( cache->c_lrutail != NULL &&
 422                         BEI(cache->c_lrutail)->bei_refcnt == 0 &&
 423                         cache->c_cursize > cache->c_maxsize )
 424                 {
 425                         e = cache->c_lrutail;
 426
 427                         /* delete from cache and lru q */
 428                         /* XXX do we need rc ? */
 429                         rc = bdb_cache_delete_entry_internal( cache, e );
 430                         bdb_cache_entry_private_destroy( e );
 431                         bdb_entry_return( e );
 432                 }
 433         }
 434
 435         /* free lru mutex */
 436         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 437         /* free cache write lock */
 438         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 439         return( 0 );
 440 }
 441
 442 /*
 443  * cache_update_entry - update a LOCKED entry which has been deleted.
 444  * returns:     0       entry has been created and locked
 445  *              1       entry already existed
 446  *              -1      something bad happened
 447  */
 448 int
 449 bdb_cache_update_entry(
 450     Cache       *cache,
 451     Entry               *e
 452 )
 453 {
 454         int     i, rc;
 455         Entry   *ee;
 456
 457         /* set cache write lock */
 458         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 459
 460         assert( e->e_private );
 461
 462         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 463                 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
 464         {
 465 #ifdef NEW_LOGGING
 466                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 467                            "bdb_cache_update_entry: (%s):%ld already in dn cache\n",
 468                            e->e_dn, e->e_id ));
 469 #else
 470                 Debug( LDAP_DEBUG_TRACE,
 471                         "====> bdb_cache_update_entry( %ld ): \"%s\": already in dn cache\n",
 472                     e->e_id, e->e_dn, 0 );
 473 #endif
 474
 475                 /* free cache write lock */
 476                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 477                 return( 1 );
 478         }
 479
 480         /* id tree */
 481         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 482                 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
 483         {
 484 #ifdef NEW_LOGGING
 485                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 486                            "bdb_cache_update_entry: (%s)%ld already in id cache\n",
 487                            e->e_dn, e->e_id ));
 488 #else
 489                 Debug( LDAP_DEBUG_ANY,
 490                         "====> bdb_cache_update_entry( %ld ): \"%s\": already in id cache\n",
 491                     e->e_id, e->e_dn, 0 );
 492 #endif
 493
 494                 /* delete from dn tree inserted above */
 495                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 496                         (AVL_CMP) entry_dn_cmp ) == NULL )
 497                 {
 498 #ifdef NEW_LOGGING
 499                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 500                                    "bdb_cache_update_entry: can't delete (%s)%ld from dn cache.\n",
 501                                    e->e_dn, e->e_id ));
 502 #else
 503                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 504                             0, 0, 0 );
 505 #endif
 506                 }
 507
 508                 /* free cache write lock */
 509                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 510                 return( -1 );
 511         }
 512
 513
 514         /* put the entry into 'CREATING' state */
 515         /* will be marked after when entry is returned */
 516         BEI(e)->bei_state = CACHE_ENTRY_CREATING;
 517
 518         /* set lru mutex */
 519         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 520         /* lru */
 521         LRU_ADD( cache, e );
 522         if ( ++cache->c_cursize > cache->c_maxsize ) {
 523                 /*
 524                  * find the lru entry not currently in use and delete it.
 525                  * in case a lot of entries are in use, only look at the
 526                  * first 10 on the tail of the list.
 527                  */
 528                 i = 0;
 529                 while ( cache->c_lrutail != NULL &&
 530                         BEI(cache->c_lrutail)->bei_refcnt != 0 &&
 531                         i < 10 )
 532                 {
 533                         /* move this in-use entry to the front of the q */
 534                         ee = cache->c_lrutail;
 535                         LRU_DELETE( cache, ee );
 536                         LRU_ADD( cache, ee );
 537                         i++;
 538                 }
 539
 540                 /*
 541                  * found at least one to delete - try to get back under
 542                  * the max cache size.
 543                  */
 544                 while ( cache->c_lrutail != NULL &&
 545                         BEI(cache->c_lrutail)->bei_refcnt == 0 &&
 546                         cache->c_cursize > cache->c_maxsize )
 547                 {
 548                         e = cache->c_lrutail;
 549
 550                         /* delete from cache and lru q */
 551                         /* XXX do we need rc ? */
 552                         rc = bdb_cache_delete_entry_internal( cache, e );
 553                         bdb_cache_entry_private_destroy( e );
 554                         bdb_entry_return( e );
 555                 }
 556         }
 557
 558         /* free lru mutex */
 559         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 560         /* free cache write lock */
 561         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 562         return( 0 );
 563 }
 564
 565 ID
 566 bdb_cache_find_entry_ndn2id(
 567         Backend         *be,
 568     Cache       *cache,
 569     struct berval       *ndn
 570 )
 571 {
 572         Entry           e, *ep;
 573         ID                      id;
 574         int count = 0;
 575
 576         /* this function is always called with normalized DN */
 577         e.e_nname = *ndn;
 578
 579 try_again:
 580         /* set cache read lock */
 581         ldap_pvt_thread_rdwr_rlock( &cache->c_rwlock );
 582
 583         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 584                 (AVL_CMP) entry_dn_cmp )) != NULL )
 585         {
 586                 int state;
 587                 count++;
 588
 589                 /*
 590                  * ep now points to an unlocked entry
 591                  * we do not need to lock the entry if we only
 592                  * check the state, refcnt, LRU, and id.
 593                  */
 594
 595                 assert( ep->e_private );
 596
 597                 /* save id */
 598                 id = ep->e_id;
 599                 state = BEI(ep)->bei_state;
 600
 601                 /*
 602                  * entry is deleted or not fully created yet
 603                  */
 604                 if ( state != CACHE_ENTRY_READY ) {
 605                         assert(state != CACHE_ENTRY_UNDEFINED);
 606
 607                         /* free cache read lock */
 608                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 609
 610 #ifdef NEW_LOGGING
 611                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 612                                    "bdb_cache_find_entry_dn2id: (%s) %ld not ready: %d\n",
 613                                    ndn->bv_val, id, state ));
 614 #else
 615                         Debug(LDAP_DEBUG_TRACE,
 616                                 "====> bdb_cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
 617                                 ndn->bv_val, id, state);
 618 #endif
 619
 620
 621                         ldap_pvt_thread_yield();
 622                         goto try_again;
 623                 }
 624
 625                 /* free cache read lock */
 626                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 627
 628                 /* set lru mutex */
 629                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 630
 631                 /* lru */
 632                 LRU_DELETE( cache, ep );
 633                 LRU_ADD( cache, ep );
 634
 635                 /* free lru mutex */
 636                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 637
 638 #ifdef NEW_LOGGING
 639                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 640                            "bdb_cache_find_entry_dn2id: (%s): %ld %d tries\n",
 641                            ndn->bv_val, id, count ));
 642 #else
 643                 Debug(LDAP_DEBUG_TRACE,
 644                         "====> bdb_cache_find_entry_dn2id(\"%s\"): %ld (%d tries)\n",
 645                         ndn->bv_val, id, count);
 646 #endif
 647
 648         } else {
 649                 /* free cache read lock */
 650                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 651
 652                 id = NOID;
 653         }
 654
 655         return( id );
 656 }
 657
 658 /*
 659  * cache_find_entry_id - find an entry in the cache, given id
 660  */
 661
 662 Entry *
 663 bdb_cache_find_entry_id(
 664         Cache   *cache,
 665         ID                              id,
 666         int                             rw
 667 )
 668 {
 669         Entry   e;
 670         Entry   *ep;
 671         int     count = 0;
 672
 673         e.e_id = id;
 674
 675 try_again:
 676         /* set cache read lock */
 677         ldap_pvt_thread_rdwr_rlock( &cache->c_rwlock );
 678
 679         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 680                 (AVL_CMP) entry_id_cmp )) != NULL )
 681         {
 682                 int state;
 683                 ID      ep_id;
 684
 685                 count++;
 686
 687                 assert( ep->e_private );
 688
 689                 ep_id = ep->e_id;
 690                 state = BEI(ep)->bei_state;
 691
 692                 /*
 693                  * entry is deleted or not fully created yet
 694                  */
 695                 if ( state != CACHE_ENTRY_READY ) {
 696
 697                         assert(state != CACHE_ENTRY_UNDEFINED);
 698
 699                         /* free cache read lock */
 700                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 701
 702 #ifdef NEW_LOGGING
 703                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 704                                    "bdb_cache_find_entry_id: (%ld)->%ld not ready (%d).\n",
 705                                    id, ep_id, state ));
 706
 707 #else
 708                         Debug(LDAP_DEBUG_TRACE,
 709                                 "====> bdb_cache_find_entry_id( %ld ): %ld (not ready) %d\n",
 710                                 id, ep_id, state);
 711 #endif
 712
 713                         ldap_pvt_thread_yield();
 714                         goto try_again;
 715                 }
 716
 717                 /* acquire reader lock */
 718                 if ( bdb_cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
 719                         /* could not acquire entry lock...
 720                          * owner cannot free as we have the cache locked.
 721                          * so, unlock the cache, yield, and try again.
 722                          */
 723
 724                         /* free cache read lock */
 725                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 726
 727 #ifdef NEW_LOGGING
 728                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 729                                    "bdb_cache_find_entry_id: %ld -> %ld (busy) %d.\n",
 730                                    id, ep_id, state ));
 731 #else
 732                         Debug(LDAP_DEBUG_TRACE,
 733                                 "====> bdb_cache_find_entry_id( %ld ): %ld (busy) %d\n",
 734                                 id, ep_id, state);
 735 #endif
 736
 737                         ldap_pvt_thread_yield();
 738                         goto try_again;
 739                 }
 740
 741                 /* free cache read lock */
 742                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 743                 /* set lru mutex */
 744                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 745                 /* lru */
 746                 LRU_DELETE( cache, ep );
 747                 LRU_ADD( cache, ep );
 748
 749                 BEI(ep)->bei_refcnt++;
 750
 751                 /* free lru mutex */
 752                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 753
 754 #ifdef NEW_LOGGING
 755                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 756                            "bdb_cache_find_entry_id: %ld -> %s  found %d tries.\n",
 757                            ep_id, ep->e_dn, count ));
 758 #else
 759                 Debug(LDAP_DEBUG_TRACE,
 760                         "====> bdb_cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
 761                         ep_id, ep->e_dn, count);
 762 #endif
 763
 764
 765                 return( ep );
 766         }
 767
 768         /* free cache read lock */
 769         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 770
 771         return( NULL );
 772 }
 773
 774 /*
 775  * cache_delete_entry - delete the entry e from the cache.  the caller
 776  * should have obtained e (increasing its ref count) via a call to one
 777  * of the cache_find_* routines.  the caller should *not* call the
 778  * cache_return_entry() routine prior to calling cache_delete_entry().
 779  * it performs this function.
 780  *
 781  * returns:     0       e was deleted ok
 782  *              1       e was not in the cache
 783  *              -1      something bad happened
 784  */
 785 int
 786 bdb_cache_delete_entry(
 787     Cache       *cache,
 788     Entry               *e
 789 )
 790 {
 791         int     rc;
 792
 793         /* set cache write lock */
 794         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 795
 796         assert( e->e_private );
 797
 798 #ifdef NEW_LOGGING
 799         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
 800                    "bdb_cache_delete_entry: delete %ld.\n", e->e_id ));
 801 #else
 802         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_delete_entry( %ld )\n",
 803                 e->e_id, 0, 0 );
 804 #endif
 805
 806         /* set lru mutex */
 807         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 808         rc = bdb_cache_delete_entry_internal( cache, e );
 809         /* free lru mutex */
 810         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 811
 812         /* free cache write lock */
 813         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 814         return( rc );
 815 }
 816
 817 static int
 818 bdb_cache_delete_entry_internal(
 819     Cache       *cache,
 820     Entry               *e
 821 )
 822 {
 823         int rc = 0;     /* return code */
 824
 825         /* dn tree */
 826         if ( avl_delete( &cache->c_dntree, (caddr_t) e, (AVL_CMP) entry_dn_cmp )
 827                 == NULL )
 828         {
 829                 rc = -1;
 830         }
 831
 832         /* id tree */
 833         if ( avl_delete( &cache->c_idtree, (caddr_t) e, (AVL_CMP) entry_id_cmp )
 834                 == NULL )
 835         {
 836                 rc = -1;
 837         }
 838
 839         if (rc != 0) {
 840                 return rc;
 841         }
 842
 843         /* lru */
 844         LRU_DELETE( cache, e );
 845         cache->c_cursize--;
 846
 847         /*
 848          * flag entry to be freed later by a call to cache_return_entry()
 849          */
 850         BEI(e)->bei_state = CACHE_ENTRY_DELETED;
 851
 852         return( 0 );
 853 }
 854
 855 void
 856 bdb_cache_release_all( Cache *cache )
 857 {
 858         Entry *e;
 859         int rc;
 860
 861         /* set cache write lock */
 862         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 863         /* set lru mutex */
 864         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 865
 866 #ifdef NEW_LOGGING
 867         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
 868                    "bdb_cache_release_all: enter\n" ));
 869 #else
 870         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_release_all\n", 0, 0, 0 );
 871 #endif
 872
 873         while ( (e = cache->c_lrutail) != NULL && BEI(e)->bei_refcnt == 0 ) {
 874 #ifdef LDAP_RDWR_DEBUG
 875                 assert(!ldap_pvt_thread_rdwr_active(&BEI(e)->bei_rdwr));
 876 #endif
 877
 878                 /* delete from cache and lru q */
 879                 /* XXX do we need rc ? */
 880                 rc = bdb_cache_delete_entry_internal( cache, e );
 881                 bdb_cache_entry_private_destroy( e );
 882                 bdb_entry_return( e );
 883         }
 884
 885         if ( cache->c_cursize ) {
 886 #ifdef NEW_LOGGING
 887                 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 888                            "bdb_cache_release_all: Entry cache could not be emptied.\n" ));
 889 #else
 890                 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
 891 #endif
 892
 893         }
 894
 895         /* free lru mutex */
 896         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 897         /* free cache write lock */
 898         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 899 }
 900
 901 #ifdef LDAP_DEBUG
 902 static void
 903 bdb_lru_print( Cache *cache )
 904 {
 905         Entry   *e;
 906
 907         fprintf( stderr, "LRU queue (head to tail):\n" );
 908         for ( e = cache->c_lruhead; e != NULL; e = BEI(e)->bei_lrunext ) {
 909                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 910                         e->e_dn, e->e_id, BEI(e)->bei_refcnt );
 911         }
 912         fprintf( stderr, "LRU queue (tail to head):\n" );
 913         for ( e = cache->c_lrutail; e != NULL; e = BEI(e)->bei_lruprev ) {
 914                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 915                         e->e_dn, e->e_id, BEI(e)->bei_refcnt );
 916         }
 917 }
 918 #endif