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