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