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