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

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