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, ENTRY,
  53                 "bdb_cache_entry_rdwr_lock: %s lock on ID %ld\n",
  54                 rw ? "w" : "r", e->e_id, 0 );
  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, ENTRY,
  71                 "bdb_cache_entry_rdwr_trylock: try %s lock on ID: %ld.\n",
  72                 rw ? "w" : "r", e->e_id, 0 );
  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, ENTRY,
  89                 "bdb_cache_entry_rdwr_unlock: remove %s lock on ID %ld.\n",
  90                 rw ? "w" : "r", e->e_id, 0 );
  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 int
 136 bdb_cache_entry_db_lock
 137 ( DB_ENV *env, u_int32_t locker, Entry *e, int rw, u_int32_t flags, DB_LOCK *lock )
 138 {
 139         int       rc;
 140         DBT       lockobj;
 141         int       db_rw;
 142
 143         if (rw)
 144                 db_rw = DB_LOCK_WRITE;
 145         else
 146                 db_rw = DB_LOCK_READ;
 147
 148         lockobj.data = e->e_nname.bv_val;
 149         lockobj.size = e->e_nname.bv_len;
 150         rc = LOCK_GET(env, locker, flags | DB_LOCK_NOWAIT,
 151                                         &lockobj, db_rw, lock);
 152         if (rc) {
 153 #ifdef NEW_LOGGING
 154                 LDAP_LOG( CACHE, DETAIL1,
 155                         "bdb_cache_entry_db_lock: entry %s, rw %d, rc %d\n",
 156                         e->e_nname.bv_val, rw, rc );
 157 #else
 158                 Debug( LDAP_DEBUG_TRACE,
 159                         "bdb_cache_entry_db_lock: entry %s, rw %d, rc %d\n",
 160                         e->e_nname.bv_val, rw, rc );
 161 #endif
 162         }
 163         return rc;
 164 }
 165
 166 int
 167 bdb_cache_entry_db_unlock
 168 ( DB_ENV *env, DB_LOCK *lock )
 169 {
 170         int rc;
 171
 172         rc = LOCK_PUT ( env, lock );
 173         return rc;
 174 }
 175
 176 /*
 177  * marks an entry in CREATING state as committed, so it is really returned
 178  * to the cache. Otherwise an entry in CREATING state is removed.
 179  * Makes e_private be destroyed at the following cache_return_entry_w,
 180  * but lets the entry untouched (owned by someone else)
 181  */
 182 void
 183 bdb_cache_entry_commit( Entry *e )
 184 {
 185         assert( e );
 186         assert( e->e_private );
 187         assert( BEI(e)->bei_state == CACHE_ENTRY_CREATING );
 188         /* assert( BEI(e)->bei_refcnt == 1 ); */
 189
 190         BEI(e)->bei_state = CACHE_ENTRY_COMMITTED;
 191 }
 192
 193 static int
 194 bdb_cache_entry_private_destroy( Entry *e )
 195 {
 196         assert( e->e_private );
 197
 198         bdb_cache_entry_rdwr_destroy( e );
 199
 200         free( e->e_private );
 201         e->e_private = NULL;
 202         return 0;
 203 }
 204
 205 void
 206 bdb_unlocked_cache_return_entry_rw( Cache *cache, Entry *e, int rw )
 207 {
 208
 209         ID id;
 210         int refcnt, freeit = 1;
 211
 212         /* set cache write lock */
 213         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 214
 215         assert( e->e_private );
 216
 217 #if 0
 218         bdb_cache_entry_rdwr_unlock(e, rw);
 219 #endif
 220
 221         id = e->e_id;
 222         refcnt = --BEI(e)->bei_refcnt;
 223
 224         /*
 225          * if the entry is returned when in CREATING state, it is deleted
 226          * but not freed because it may belong to someone else (do_add,
 227          * for instance)
 228          */
 229         if (  BEI(e)->bei_state == CACHE_ENTRY_CREATING ) {
 230                 /* set lru mutex */
 231                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 232                 bdb_cache_delete_entry_internal( cache, e );
 233                 /* free lru mutex */
 234                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 235                 freeit = 0;
 236                 /* now the entry is in DELETED state */
 237         }
 238
 239         if ( BEI(e)->bei_state == CACHE_ENTRY_COMMITTED ) {
 240                 BEI(e)->bei_state = CACHE_ENTRY_READY;
 241
 242                 /* free cache write lock */
 243                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 244
 245 #ifdef NEW_LOGGING
 246                 LDAP_LOG( CACHE, DETAIL1,
 247                            "bdb_unlocked_cache_return_entry_rw: return (%ld):%s, refcnt=%d\n",
 248                            id, rw ? "w" : "r", refcnt );
 249 #else
 250                 Debug( LDAP_DEBUG_TRACE,
 251                         "====> bdb_unlocked_cache_return_entry_%s( %ld ): created (%d)\n",
 252                         rw ? "w" : "r", id, refcnt );
 253 #endif
 254
 255
 256         } else if ( BEI(e)->bei_state == CACHE_ENTRY_DELETED ) {
 257                 if( refcnt > 0 ) {
 258                         /* free cache write lock */
 259                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 260
 261 #ifdef NEW_LOGGING
 262                         LDAP_LOG( CACHE, DETAIL1,
 263                                    "bdb_unlocked_cache_return_entry_rw: %ld, delete pending (%d).\n",
 264                                    id, refcnt, 0 );
 265 #else
 266                         Debug( LDAP_DEBUG_TRACE,
 267                                 "====> bdb_unlocked_cache_return_entry_%s( %ld ): delete pending (%d)\n",
 268                                 rw ? "w" : "r", id, refcnt );
 269 #endif
 270
 271                 } else {
 272                         bdb_cache_entry_private_destroy( e );
 273                         if ( freeit ) {
 274                                 bdb_entry_return( e );
 275                         }
 276
 277                         /* free cache write lock */
 278                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 279
 280 #ifdef NEW_LOGGING
 281                         LDAP_LOG( CACHE, DETAIL1,
 282                                    "bdb_unlocked_cache_return_entry_rw: (%ld): deleted (%d)\n",
 283                                    id, refcnt, 0 );
 284 #else
 285                         Debug( LDAP_DEBUG_TRACE,
 286                                 "====> bdb_unlocked_cache_return_entry_%s( %ld ): deleted (%d)\n",
 287                                 rw ? "w" : "r", id, refcnt );
 288 #endif
 289                 }
 290
 291         } else {
 292                 /* free cache write lock */
 293                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 294
 295 #ifdef NEW_LOGGING
 296                 LDAP_LOG( CACHE, DETAIL1,
 297                            "bdb_unlocked_cache_return_entry_rw: ID %ld:%s returned (%d)\n",
 298                            id, rw ? "w": "r", refcnt );
 299 #else
 300                 Debug( LDAP_DEBUG_TRACE,
 301                         "====> bdb_unlocked_cache_return_entry_%s( %ld ): returned (%d)\n",
 302                         rw ? "w" : "r", id, refcnt);
 303 #endif
 304         }
 305 }
 306
 307 void
 308 bdb_cache_return_entry_rw
 309 ( DB_ENV *env, Cache *cache, Entry *e, int rw, DB_LOCK *lock )
 310 {
 311         ID id;
 312         int refcnt, freeit = 1;
 313
 314         /* set cache write lock */
 315         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 316
 317         assert( e->e_private );
 318
 319         bdb_cache_entry_db_unlock( env, lock );
 320 #if 0
 321         bdb_cache_entry_rdwr_unlock(e, rw);
 322 #endif
 323
 324         id = e->e_id;
 325         refcnt = --BEI(e)->bei_refcnt;
 326
 327         /*
 328          * if the entry is returned when in CREATING state, it is deleted
 329          * but not freed because it may belong to someone else (do_add,
 330          * for instance)
 331          */
 332         if (  BEI(e)->bei_state == CACHE_ENTRY_CREATING ) {
 333                 /* set lru mutex */
 334                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 335                 bdb_cache_delete_entry_internal( cache, e );
 336                 /* free lru mutex */
 337                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 338                 freeit = 0;
 339                 /* now the entry is in DELETED state */
 340         }
 341
 342         if ( BEI(e)->bei_state == CACHE_ENTRY_COMMITTED ) {
 343                 BEI(e)->bei_state = CACHE_ENTRY_READY;
 344
 345                 /* free cache write lock */
 346                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 347
 348 #ifdef NEW_LOGGING
 349                 LDAP_LOG( CACHE, DETAIL1,
 350                            "bdb_cache_return_entry_rw: return (%ld):%s, refcnt=%d\n",
 351                            id, rw ? "w" : "r", refcnt );
 352 #else
 353                 Debug( LDAP_DEBUG_TRACE,
 354                         "====> bdb_cache_return_entry_%s( %ld ): created (%d)\n",
 355                         rw ? "w" : "r", id, refcnt );
 356 #endif
 357
 358
 359         } else if ( BEI(e)->bei_state == CACHE_ENTRY_DELETED ) {
 360                 if( refcnt > 0 ) {
 361                         /* free cache write lock */
 362                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 363
 364 #ifdef NEW_LOGGING
 365                         LDAP_LOG( CACHE, DETAIL1,
 366                                    "bdb_cache_return_entry_rw: %ld, delete pending (%d).\n",
 367                                    id, refcnt, 0 );
 368 #else
 369                         Debug( LDAP_DEBUG_TRACE,
 370                                 "====> bdb_cache_return_entry_%s( %ld ): delete pending (%d)\n",
 371                                 rw ? "w" : "r", id, refcnt );
 372 #endif
 373
 374                 } else {
 375                         bdb_cache_entry_private_destroy( e );
 376                         if ( freeit ) {
 377                                 bdb_entry_return( e );
 378                         }
 379
 380                         /* free cache write lock */
 381                         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 382
 383 #ifdef NEW_LOGGING
 384                         LDAP_LOG( CACHE, DETAIL1,
 385                                    "bdb_cache_return_entry_rw: (%ld): deleted (%d)\n",
 386                                    id, refcnt, 0 );
 387 #else
 388                         Debug( LDAP_DEBUG_TRACE,
 389                                 "====> bdb_cache_return_entry_%s( %ld ): deleted (%d)\n",
 390                                 rw ? "w" : "r", id, refcnt );
 391 #endif
 392                 }
 393
 394         } else {
 395                 /* free cache write lock */
 396                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 397
 398 #ifdef NEW_LOGGING
 399                 LDAP_LOG( CACHE, DETAIL1,
 400                            "bdb_cache_return_entry_rw: ID %ld:%s returned (%d)\n",
 401                            id, rw ? "w": "r", refcnt );
 402 #else
 403                 Debug( LDAP_DEBUG_TRACE,
 404                         "====> bdb_cache_return_entry_%s( %ld ): returned (%d)\n",
 405                         rw ? "w" : "r", id, refcnt);
 406 #endif
 407         }
 408 }
 409
 410 #define LRU_DELETE( cache, e ) do { \
 411         if ( BEI(e)->bei_lruprev != NULL ) { \
 412                 BEI(BEI(e)->bei_lruprev)->bei_lrunext = BEI(e)->bei_lrunext; \
 413         } else { \
 414                 (cache)->c_lruhead = BEI(e)->bei_lrunext; \
 415         } \
 416         if ( BEI(e)->bei_lrunext != NULL ) { \
 417                 BEI(BEI(e)->bei_lrunext)->bei_lruprev = BEI(e)->bei_lruprev; \
 418         } else { \
 419                 (cache)->c_lrutail = BEI(e)->bei_lruprev; \
 420         } \
 421 } while(0)
 422
 423 #define LRU_ADD( cache, e ) do { \
 424         BEI(e)->bei_lrunext = (cache)->c_lruhead; \
 425         if ( BEI(e)->bei_lrunext != NULL ) { \
 426                 BEI(BEI(e)->bei_lrunext)->bei_lruprev = (e); \
 427         } \
 428         (cache)->c_lruhead = (e); \
 429         BEI(e)->bei_lruprev = NULL; \
 430         if ( (cache)->c_lrutail == NULL ) { \
 431                 (cache)->c_lrutail = (e); \
 432         } \
 433 } while(0)
 434
 435 /*
 436  * cache_add_entry_rw - create and lock an entry in the cache
 437  * returns:     0       entry has been created and locked
 438  *              1       entry already existed
 439  *              -1      something bad happened
 440  *             other    Berkeley DB locking error code
 441  */
 442 int
 443 bdb_cache_add_entry_rw(
 444     DB_ENV      *env,
 445     Cache       *cache,
 446     Entry       *e,
 447     int         rw,
 448     u_int32_t   locker,
 449     DB_LOCK     *lock
 450 )
 451 {
 452         int     i, rc;
 453         Entry   *ee;
 454
 455 #ifdef NEW_LOGGING
 456         LDAP_LOG( CACHE, ENTRY,
 457                 "bdb_cache_add_entry_rw: add (%s):%s to cache\n",
 458                 e->e_dn, rw ? "w" : "r", 0 );
 459 #endif
 460         /* set cache write lock */
 461         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 462
 463         assert( e->e_private == NULL );
 464
 465         if( bdb_cache_entry_private_init(e) != 0 ) {
 466                 /* free cache write lock */
 467                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 468
 469 #ifdef NEW_LOGGING
 470                 LDAP_LOG( CACHE, ERR,
 471                         "bdb_cache_add_entry_rw: add (%s):%ld private init failed!\n",
 472                         e->e_dn, e->e_id, 0 );
 473 #else
 474                 Debug( LDAP_DEBUG_ANY,
 475                         "====> bdb_cache_add_entry( %ld ): \"%s\": private init failed!\n",
 476                     e->e_id, e->e_dn, 0 );
 477 #endif
 478
 479
 480                 return( -1 );
 481         }
 482
 483         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 484                 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
 485         {
 486                 /* free cache write lock */
 487                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 488
 489 #ifdef NEW_LOGGING
 490                 LDAP_LOG( CACHE, DETAIL1,
 491                         "bdb_cache_add_entry: (%s):%ld already in cache.\n",
 492                         e->e_dn, e->e_id, 0 );
 493 #else
 494                 Debug( LDAP_DEBUG_TRACE,
 495                         "====> bdb_cache_add_entry( %ld ): \"%s\": already in dn cache\n",
 496                     e->e_id, e->e_dn, 0 );
 497 #endif
 498
 499                 bdb_cache_entry_private_destroy(e);
 500
 501                 return( 1 );
 502         }
 503
 504         /* id tree */
 505         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 506                 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
 507         {
 508 #ifdef NEW_LOGGING
 509                 LDAP_LOG( CACHE, DETAIL1,
 510                         "bdb_cache_add_entry: (%s):%ls already in cache.\n",
 511                         e->e_dn, e->e_id, 0 );
 512 #else
 513                 Debug( LDAP_DEBUG_ANY,
 514                         "====> bdb_cache_add_entry( %ld ): \"%s\": already in id cache\n",
 515                     e->e_id, e->e_dn, 0 );
 516 #endif
 517
 518                 /* delete from dn tree inserted above */
 519                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 520                         (AVL_CMP) entry_dn_cmp ) == NULL )
 521                 {
 522 #ifdef NEW_LOGGING
 523                         LDAP_LOG( CACHE, INFO,
 524                                 "bdb_cache_add_entry: can't delete (%s) from cache.\n",
 525                                 e->e_dn, 0, 0 );
 526 #else
 527                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 528                             0, 0, 0 );
 529 #endif
 530                 }
 531
 532                 bdb_cache_entry_private_destroy(e);
 533
 534                 /* free cache write lock */
 535                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 536                 return( -1 );
 537         }
 538
 539         rc = bdb_cache_entry_db_lock( env, locker, e, rw, 0, lock );
 540         switch ( rc ) {
 541         case 0 :
 542                 break;
 543         case DB_LOCK_DEADLOCK :
 544         case DB_LOCK_NOTGRANTED :
 545                 /* undo avl changes immediately */
 546                 if ( avl_delete( &cache->c_idtree, (caddr_t) e,
 547                         (AVL_CMP) entry_id_cmp ) == NULL ) {
 548 #ifdef NEW_LOGGING
 549                         LDAP_LOG( CACHE, INFO,
 550                                 "bdb_cache_add_entry: can't delete (%s) from cache.\n",
 551                                 e->e_dn, 0, 0 );
 552 #else
 553                         Debug( LDAP_DEBUG_ANY, "====> can't delete from id cache\n", 0, 0, 0 );
 554 #endif
 555                 }
 556                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 557                                 (AVL_CMP) entry_dn_cmp ) == NULL ) {
 558 #ifdef NEW_LOGGING
 559                         LDAP_LOG( CACHE, INFO,
 560                                 "bdb_cache_add_entry: can't delete (%s) from cache.\n",
 561                                 e->e_dn, 0, 0 );
 562 #else
 563                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n", 0, 0, 0 );
 564 #endif
 565                 }
 566                 /* fall through */
 567         default :
 568                 bdb_cache_entry_private_destroy(e);
 569                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 570                 return rc;
 571         }
 572
 573         /* put the entry into 'CREATING' state */
 574         /* will be marked after when entry is returned */
 575         BEI(e)->bei_state = CACHE_ENTRY_CREATING;
 576         BEI(e)->bei_refcnt = 1;
 577
 578         /* set lru mutex */
 579         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 580         /* lru */
 581         LRU_ADD( cache, e );
 582         if ( ++cache->c_cursize > cache->c_maxsize ) {
 583                 /*
 584                  * find the lru entry not currently in use and delete it.
 585                  * in case a lot of entries are in use, only look at the
 586                  * first 10 on the tail of the list.
 587                  */
 588                 i = 0;
 589                 while ( cache->c_lrutail != NULL &&
 590                         BEI(cache->c_lrutail)->bei_refcnt != 0 &&
 591                         i < 10 )
 592                 {
 593                         /* move this in-use entry to the front of the q */
 594                         ee = cache->c_lrutail;
 595                         LRU_DELETE( cache, ee );
 596                         LRU_ADD( cache, ee );
 597                         i++;
 598                 }
 599
 600                 /*
 601                  * found at least one to delete - try to get back under
 602                  * the max cache size.
 603                  */
 604                 while ( cache->c_lrutail != NULL &&
 605                         BEI(cache->c_lrutail)->bei_refcnt == 0 &&
 606                         cache->c_cursize > cache->c_maxsize )
 607                 {
 608                         e = cache->c_lrutail;
 609
 610                         /* delete from cache and lru q */
 611                         /* XXX do we need rc ? */
 612                         rc = bdb_cache_delete_entry_internal( cache, e );
 613                         bdb_cache_entry_private_destroy( e );
 614                         bdb_entry_return( e );
 615                 }
 616         }
 617
 618         /* free lru mutex */
 619         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 620         /* free cache write lock */
 621         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 622         return( 0 );
 623 }
 624
 625 /*
 626  * cache_update_entry - update a LOCKED entry which has been deleted.
 627  * returns:     0       entry has been created and locked
 628  *              1       entry already existed
 629  *              -1      something bad happened
 630  */
 631 int
 632 bdb_cache_update_entry(
 633     Cache       *cache,
 634     Entry               *e
 635 )
 636 {
 637         int     i, rc;
 638         Entry   *ee;
 639
 640         /* set cache write lock */
 641         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 642
 643         assert( e->e_private );
 644
 645         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 646                 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
 647         {
 648 #ifdef NEW_LOGGING
 649                 LDAP_LOG( CACHE, DETAIL1,
 650                         "bdb_cache_update_entry: (%s):%ld already in dn cache\n",
 651                         e->e_dn, e->e_id, 0 );
 652 #else
 653                 Debug( LDAP_DEBUG_TRACE,
 654                         "====> bdb_cache_update_entry( %ld ): \"%s\": already in dn cache\n",
 655                     e->e_id, e->e_dn, 0 );
 656 #endif
 657
 658                 /* free cache write lock */
 659                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 660                 return( 1 );
 661         }
 662
 663         /* id tree */
 664         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 665                 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
 666         {
 667 #ifdef NEW_LOGGING
 668                 LDAP_LOG( CACHE, DETAIL1,
 669                         "bdb_cache_update_entry: (%s)%ld already in id cache\n",
 670                         e->e_dn, e->e_id, 0 );
 671 #else
 672                 Debug( LDAP_DEBUG_ANY,
 673                         "====> bdb_cache_update_entry( %ld ): \"%s\": already in id cache\n",
 674                     e->e_id, e->e_dn, 0 );
 675 #endif
 676
 677                 /* delete from dn tree inserted above */
 678                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 679                         (AVL_CMP) entry_dn_cmp ) == NULL )
 680                 {
 681 #ifdef NEW_LOGGING
 682                         LDAP_LOG( CACHE, INFO,
 683                                 "bdb_cache_update_entry: can't delete (%s)%ld from dn cache.\n",
 684                                 e->e_dn, e->e_id, 0 );
 685 #else
 686                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 687                             0, 0, 0 );
 688 #endif
 689                 }
 690
 691                 /* free cache write lock */
 692                 ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 693                 return( -1 );
 694         }
 695
 696
 697         /* put the entry into 'CREATING' state */
 698         /* will be marked after when entry is returned */
 699         BEI(e)->bei_state = CACHE_ENTRY_CREATING;
 700
 701         /* set lru mutex */
 702         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 703         /* lru */
 704         LRU_ADD( cache, e );
 705         if ( ++cache->c_cursize > cache->c_maxsize ) {
 706                 /*
 707                  * find the lru entry not currently in use and delete it.
 708                  * in case a lot of entries are in use, only look at the
 709                  * first 10 on the tail of the list.
 710                  */
 711                 i = 0;
 712                 while ( cache->c_lrutail != NULL &&
 713                         BEI(cache->c_lrutail)->bei_refcnt != 0 &&
 714                         i < 10 )
 715                 {
 716                         /* move this in-use entry to the front of the q */
 717                         ee = cache->c_lrutail;
 718                         LRU_DELETE( cache, ee );
 719                         LRU_ADD( cache, ee );
 720                         i++;
 721                 }
 722
 723                 /*
 724                  * found at least one to delete - try to get back under
 725                  * the max cache size.
 726                  */
 727                 while ( cache->c_lrutail != NULL &&
 728                         BEI(cache->c_lrutail)->bei_refcnt == 0 &&
 729                         cache->c_cursize > cache->c_maxsize )
 730                 {
 731                         e = cache->c_lrutail;
 732
 733                         /* delete from cache and lru q */
 734                         /* XXX do we need rc ? */
 735                         rc = bdb_cache_delete_entry_internal( cache, e );
 736                         bdb_cache_entry_private_destroy( e );
 737                         bdb_entry_return( e );
 738                 }
 739         }
 740
 741         /* free lru mutex */
 742         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 743         /* free cache write lock */
 744         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
 745         return( 0 );
 746 }
 747
 748 ID
 749 bdb_cache_find_entry_ndn2id(
 750         Backend         *be,
 751     Cache       *cache,
 752     struct berval       *ndn
 753 )
 754 {
 755         Entry           e, *ep;
 756         ID                      id;
 757         int count = 0;
 758
 759         /* this function is always called with normalized DN */
 760         e.e_nname = *ndn;
 761
 762 try_again:
 763         /* set cache read lock */
 764         ldap_pvt_thread_rdwr_rlock( &cache->c_rwlock );
 765
 766         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 767                 (AVL_CMP) entry_dn_cmp )) != NULL )
 768         {
 769                 int state;
 770                 count++;
 771
 772                 /*
 773                  * ep now points to an unlocked entry
 774                  * we do not need to lock the entry if we only
 775                  * check the state, refcnt, LRU, and id.
 776                  */
 777
 778                 assert( ep->e_private );
 779
 780                 /* save id */
 781                 id = ep->e_id;
 782                 state = BEI(ep)->bei_state;
 783
 784                 /*
 785                  * entry is deleted or not fully created yet
 786                  */
 787                 if ( state != CACHE_ENTRY_READY ) {
 788                         assert(state != CACHE_ENTRY_UNDEFINED);
 789
 790                         /* free cache read lock */
 791                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 792
 793 #ifdef NEW_LOGGING
 794                         LDAP_LOG( CACHE, INFO,
 795                                 "bdb_cache_find_entry_dn2id: (%s) %ld not ready: %d\n",
 796                                 ndn->bv_val, id, state );
 797 #else
 798                         Debug(LDAP_DEBUG_TRACE,
 799                                 "====> bdb_cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
 800                                 ndn->bv_val, id, state);
 801 #endif
 802
 803
 804                         ldap_pvt_thread_yield();
 805                         goto try_again;
 806                 }
 807
 808                 /* free cache read lock */
 809                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 810
 811                 /* set lru mutex */
 812                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 813
 814                 /* lru */
 815                 LRU_DELETE( cache, ep );
 816                 LRU_ADD( cache, ep );
 817
 818                 /* free lru mutex */
 819                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 820
 821 #ifdef NEW_LOGGING
 822                 LDAP_LOG( CACHE, DETAIL1,
 823                         "bdb_cache_find_entry_dn2id: (%s): %ld %d tries\n",
 824                         ndn->bv_val, id, count );
 825 #else
 826                 Debug(LDAP_DEBUG_TRACE,
 827                         "====> bdb_cache_find_entry_dn2id(\"%s\"): %ld (%d tries)\n",
 828                         ndn->bv_val, id, count);
 829 #endif
 830
 831         } else {
 832                 /* free cache read lock */
 833                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 834
 835                 id = NOID;
 836         }
 837
 838         return( id );
 839 }
 840
 841 /*
 842  * cache_find_entry_id - find an entry in the cache, given id
 843  */
 844
 845 Entry *
 846 bdb_cache_find_entry_id(
 847         DB_ENV  *env,
 848         Cache   *cache,
 849         ID                              id,
 850         int                             rw,
 851         u_int32_t       locker,
 852         DB_LOCK         *lock
 853 )
 854 {
 855         Entry   e;
 856         Entry   *ep;
 857         int     count = 0;
 858         int     rc;
 859
 860         e.e_id = id;
 861
 862 try_again:
 863         /* set cache read lock */
 864         ldap_pvt_thread_rdwr_rlock( &cache->c_rwlock );
 865
 866         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 867                 (AVL_CMP) entry_id_cmp )) != NULL )
 868         {
 869                 int state;
 870                 ID      ep_id;
 871
 872                 count++;
 873
 874                 assert( ep->e_private );
 875
 876                 ep_id = ep->e_id;
 877                 state = BEI(ep)->bei_state;
 878
 879                 /*
 880                  * entry is deleted or not fully created yet
 881                  */
 882                 if ( state != CACHE_ENTRY_READY ) {
 883
 884                         assert(state != CACHE_ENTRY_UNDEFINED);
 885
 886                         /* free cache read lock */
 887                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 888
 889 #ifdef NEW_LOGGING
 890                         LDAP_LOG( CACHE, INFO,
 891                                 "bdb_cache_find_entry_id: (%ld)->%ld not ready (%d).\n",
 892                                 id, ep_id, state );
 893
 894 #else
 895                         Debug(LDAP_DEBUG_TRACE,
 896                                 "====> bdb_cache_find_entry_id( %ld ): %ld (not ready) %d\n",
 897                                 id, ep_id, state);
 898 #endif
 899
 900                         ldap_pvt_thread_yield();
 901                         goto try_again;
 902                 }
 903
 904                 /* acquire reader lock */
 905                 rc = bdb_cache_entry_db_lock ( env, locker, ep, rw, 0, lock );
 906
 907 #if 0
 908                 if ( bdb_cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
 909 #endif
 910
 911                 if ( rc ) { /* will be changed to retry beyond threshold */
 912                         /* could not acquire entry lock...
 913                          * owner cannot free as we have the cache locked.
 914                          * so, unlock the cache, yield, and try again.
 915                          */
 916
 917                         /* free cache read lock */
 918                         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 919
 920 #ifdef NEW_LOGGING
 921                         LDAP_LOG( CACHE, INFO,
 922                                 "bdb_cache_find_entry_id: %ld -> %ld (busy) %d.\n",
 923                                 id, ep_id, state );
 924 #else
 925                         Debug(LDAP_DEBUG_TRACE,
 926                                 "====> bdb_cache_find_entry_id( %ld ): %ld (busy) %d\n",
 927                                 id, ep_id, state);
 928                         Debug(LDAP_DEBUG_TRACE,
 929                                 "locker = %d\n",
 930                                 locker, 0, 0);
 931 #endif
 932
 933                         ldap_pvt_thread_yield();
 934                         goto try_again;
 935                 }
 936
 937                 /* free cache read lock */
 938                 ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 939                 /* set lru mutex */
 940                 ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
 941                 /* lru */
 942                 LRU_DELETE( cache, ep );
 943                 LRU_ADD( cache, ep );
 944
 945                 BEI(ep)->bei_refcnt++;
 946
 947                 /* free lru mutex */
 948                 ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
 949
 950 #ifdef NEW_LOGGING
 951                 LDAP_LOG( CACHE, DETAIL1,
 952                         "bdb_cache_find_entry_id: %ld -> %s  found %d tries.\n",
 953                         ep_id, ep->e_dn, count );
 954 #else
 955                 Debug(LDAP_DEBUG_TRACE,
 956                         "====> bdb_cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
 957                         ep_id, ep->e_dn, count);
 958 #endif
 959
 960
 961                 return( ep );
 962         }
 963
 964         /* free cache read lock */
 965         ldap_pvt_thread_rdwr_runlock( &cache->c_rwlock );
 966
 967         return( NULL );
 968 }
 969
 970 /*
 971  * cache_delete_entry - delete the entry e from the cache.  the caller
 972  * should have obtained e (increasing its ref count) via a call to one
 973  * of the cache_find_* routines.  the caller should *not* call the
 974  * cache_return_entry() routine prior to calling cache_delete_entry().
 975  * it performs this function.
 976  *
 977  * returns:     0       e was deleted ok
 978  *              1       e was not in the cache
 979  *              -1      something bad happened
 980  */
 981 int
 982 bdb_cache_delete_entry(
 983     Cache       *cache,
 984     Entry               *e
 985 )
 986 {
 987         int     rc;
 988
 989         /* set cache write lock */
 990         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
 991
 992         assert( e->e_private );
 993
 994 #ifdef NEW_LOGGING
 995         LDAP_LOG( CACHE, ENTRY,
 996                 "bdb_cache_delete_entry: delete %ld.\n", e->e_id, 0, 0 );
 997 #else
 998         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_delete_entry( %ld )\n",
 999                 e->e_id, 0, 0 );
1000 #endif
1001
1002         /* set lru mutex */
1003         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
1004         rc = bdb_cache_delete_entry_internal( cache, e );
1005         /* free lru mutex */
1006         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
1007
1008         /* free cache write lock */
1009         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
1010         return( rc );
1011 }
1012
1013 static int
1014 bdb_cache_delete_entry_internal(
1015     Cache       *cache,
1016     Entry               *e
1017 )
1018 {
1019         int rc = 0;     /* return code */
1020
1021         /* dn tree */
1022         if ( avl_delete( &cache->c_dntree, (caddr_t) e, (AVL_CMP) entry_dn_cmp )
1023                 == NULL )
1024         {
1025                 rc = -1;
1026         }
1027
1028         /* id tree */
1029         if ( avl_delete( &cache->c_idtree, (caddr_t) e, (AVL_CMP) entry_id_cmp )
1030                 == NULL )
1031         {
1032                 rc = -1;
1033         }
1034
1035         if (rc != 0) {
1036                 return rc;
1037         }
1038
1039         /* lru */
1040         LRU_DELETE( cache, e );
1041         cache->c_cursize--;
1042
1043         /*
1044          * flag entry to be freed later by a call to cache_return_entry()
1045          */
1046         BEI(e)->bei_state = CACHE_ENTRY_DELETED;
1047
1048         return( 0 );
1049 }
1050
1051 void
1052 bdb_cache_release_all( Cache *cache )
1053 {
1054         Entry *e;
1055         int rc;
1056
1057         /* set cache write lock */
1058         ldap_pvt_thread_rdwr_wlock( &cache->c_rwlock );
1059         /* set lru mutex */
1060         ldap_pvt_thread_mutex_lock( &cache->lru_mutex );
1061
1062 #ifdef NEW_LOGGING
1063         LDAP_LOG( CACHE, ENTRY, "bdb_cache_release_all: enter\n", 0, 0, 0 );
1064 #else
1065         Debug( LDAP_DEBUG_TRACE, "====> bdb_cache_release_all\n", 0, 0, 0 );
1066 #endif
1067
1068         while ( (e = cache->c_lrutail) != NULL && BEI(e)->bei_refcnt == 0 ) {
1069 #ifdef LDAP_RDWR_DEBUG
1070                 assert(!ldap_pvt_thread_rdwr_active(&BEI(e)->bei_rdwr));
1071 #endif
1072
1073                 /* delete from cache and lru q */
1074                 /* XXX do we need rc ? */
1075                 rc = bdb_cache_delete_entry_internal( cache, e );
1076                 bdb_cache_entry_private_destroy( e );
1077                 bdb_entry_return( e );
1078         }
1079
1080         if ( cache->c_cursize ) {
1081 #ifdef NEW_LOGGING
1082                 LDAP_LOG( CACHE, INFO,
1083                    "bdb_cache_release_all: Entry cache could not be emptied.\n", 0, 0, 0 );
1084 #else
1085                 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
1086 #endif
1087
1088         }
1089
1090         /* free lru mutex */
1091         ldap_pvt_thread_mutex_unlock( &cache->lru_mutex );
1092         /* free cache write lock */
1093         ldap_pvt_thread_rdwr_wunlock( &cache->c_rwlock );
1094 }
1095
1096 #ifdef LDAP_DEBUG
1097 static void
1098 bdb_lru_print( Cache *cache )
1099 {
1100         Entry   *e;
1101
1102         fprintf( stderr, "LRU queue (head to tail):\n" );
1103         for ( e = cache->c_lruhead; e != NULL; e = BEI(e)->bei_lrunext ) {
1104                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
1105                         e->e_dn, e->e_id, BEI(e)->bei_refcnt );
1106         }
1107         fprintf( stderr, "LRU queue (tail to head):\n" );
1108         for ( e = cache->c_lrutail; e != NULL; e = BEI(e)->bei_lruprev ) {
1109                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
1110                         e->e_dn, e->e_id, BEI(e)->bei_refcnt );
1111         }
1112 }
1113 #endif
1114
1115 #ifdef BDB_REUSE_LOCKERS
1116 void
1117 bdb_locker_id_free( void *key, void *data )
1118 {
1119         DB_ENV *env = key;
1120         int lockid = (int) data;
1121
1122         XLOCK_ID_FREE( env, lockid );
1123 }
1124
1125 int
1126 bdb_locker_id( Operation *op, DB_ENV *env, int *locker )
1127 {
1128         int i, rc, lockid;
1129         void *data;
1130
1131         if ( !env || !op || !locker ) return -1;
1132
1133         /* Shouldn't happen unless we're single-threaded */
1134         if ( !op->o_threadctx ) {
1135                 *locker = 0;
1136                 return 0;
1137         }
1138
1139         if ( ldap_pvt_thread_pool_getkey( op->o_threadctx, env, &data, NULL ) ) {
1140                 for ( i=0, rc=1; rc != 0 && i<4; i++ ) {
1141                         rc = XLOCK_ID( env, &lockid );
1142                         if (rc) ldap_pvt_thread_yield();
1143                 }
1144                 if ( rc != 0) {
1145                         return rc;
1146                 }
1147                 data = (void *)lockid;
1148                 if ( ( rc = ldap_pvt_thread_pool_setkey( op->o_threadctx, env,
1149                         data, bdb_locker_id_free ) ) ) {
1150                         XLOCK_ID_FREE( env, lockid );
1151 #ifdef NEW_LOGGING
1152                         LDAP_LOG( BACK_BDB, ERR, "bdb_locker_id: err %s(%d)\n",
1153                                 db_strerror(rc), rc, 0 );
1154 #else
1155                         Debug( LDAP_DEBUG_ANY, "bdb_locker_id: err %s(%d)\n",
1156                                 db_strerror(rc), rc, 0 );
1157 #endif
1158
1159                         return rc;
1160                 }
1161         } else {
1162                 lockid = (int)data;
1163         }
1164         *locker = lockid;
1165         return 0;
1166 }
1167 #endif