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