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         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 ID
 567 cache_find_entry_ndn2id(
 568         Backend         *be,
 569     Cache       *cache,
 570     struct berval       *ndn
 571 )
 572 {
 573         Entry           e, *ep;
 574         ID                      id;
 575         int count = 0;
 576
 577         /* this function is always called with normalized DN */
 578         e.e_nname = *ndn;
 579
 580 try_again:
 581         /* set cache mutex */
 582         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 583
 584         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 585                 (AVL_CMP) entry_dn_cmp )) != NULL )
 586         {
 587                 int state;
 588                 count++;
 589
 590                 /*
 591                  * ep now points to an unlocked entry
 592                  * we do not need to lock the entry if we only
 593                  * check the state, refcnt, LRU, and id.
 594                  */
 595
 596                 assert( ep->e_private );
 597
 598                 /* save id */
 599                 id = ep->e_id;
 600                 state = LEI(ep)->lei_state;
 601
 602                 /*
 603                  * entry is deleted or not fully created yet
 604                  */
 605                 if ( state != CACHE_ENTRY_READY ) {
 606                         assert(state != CACHE_ENTRY_UNDEFINED);
 607
 608                         /* free cache mutex */
 609                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 610
 611 #ifdef NEW_LOGGING
 612                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 613                                    "cache_find_entry_dn2id: (%s) %ld not ready: %d\n",
 614                                    ndn->bv_val, id, state ));
 615 #else
 616                         Debug(LDAP_DEBUG_TRACE,
 617                                 "====> cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
 618                                 ndn->bv_val, id, state);
 619 #endif
 620
 621
 622                         ldap_pvt_thread_yield();
 623                         goto try_again;
 624                 }
 625
 626                 /* lru */
 627                 LRU_DELETE( cache, ep );
 628                 LRU_ADD( cache, ep );
 629
 630                 /* free cache mutex */
 631                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 632
 633 #ifdef NEW_LOGGING
 634                 LDAP_LOG(( "cache", LDAP_LEVEL_DETAIL1,
 635                            "cache_find_entry_dn2id: (%s): %ld %d tries\n",
 636                            ndn->bv_val, id, count ));
 637 #else
 638                 Debug(LDAP_DEBUG_TRACE,
 639                         "====> cache_find_entry_dn2id(\"%s\"): %ld (%d tries)\n",
 640                         ndn->bv_val, id, count);
 641 #endif
 642
 643
 644         } else {
 645                 /* free cache mutex */
 646                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 647
 648                 id = NOID;
 649         }
 650
 651         return( id );
 652 }
 653
 654 /*
 655  * cache_find_entry_id - find an entry in the cache, given id
 656  */
 657
 658 Entry *
 659 cache_find_entry_id(
 660         Cache   *cache,
 661         ID                              id,
 662         int                             rw
 663 )
 664 {
 665         Entry   e;
 666         Entry   *ep;
 667         int     count = 0;
 668
 669         e.e_id = id;
 670
 671 try_again:
 672         /* set cache mutex */
 673         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 674
 675         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 676                 (AVL_CMP) entry_id_cmp )) != NULL )
 677         {
 678                 int state;
 679                 ID      ep_id;
 680
 681                 count++;
 682
 683                 assert( ep->e_private );
 684
 685                 ep_id = ep->e_id;
 686                 state = LEI(ep)->lei_state;
 687
 688                 /*
 689                  * entry is deleted or not fully created yet
 690                  */
 691                 if ( state != CACHE_ENTRY_READY ) {
 692
 693                         assert(state != CACHE_ENTRY_UNDEFINED);
 694
 695                         /* free cache mutex */
 696                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 697
 698 #ifdef NEW_LOGGING
 699                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 700                                    "cache_find_entry_id: (%ld)->%ld not ready (%d).\n",
 701                                    id, ep_id, state ));
 702
 703 #else
 704                         Debug(LDAP_DEBUG_TRACE,
 705                                 "====> cache_find_entry_id( %ld ): %ld (not ready) %d\n",
 706                                 id, ep_id, state);
 707 #endif
 708
 709
 710                         ldap_pvt_thread_yield();
 711                         goto try_again;
 712                 }
 713
 714                 /* acquire reader lock */
 715                 if ( cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
 716                         /* could not acquire entry lock...
 717                          * owner cannot free as we have the cache locked.
 718                          * so, unlock the cache, yield, and try again.
 719                          */
 720
 721                         /* free cache mutex */
 722                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 723
 724 #ifdef NEW_LOGGING
 725                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 726                                    "cache_find_entry_id: %ld -> %ld (busy) %d.\n",
 727                                    id, ep_id, state ));
 728 #else
 729                         Debug(LDAP_DEBUG_TRACE,
 730                                 "====> cache_find_entry_id( %ld ): %ld (busy) %d\n",
 731                                 id, ep_id, state);
 732 #endif
 733
 734
 735                         ldap_pvt_thread_yield();
 736                         goto try_again;
 737                 }
 738
 739                 /* lru */
 740                 LRU_DELETE( cache, ep );
 741                 LRU_ADD( cache, ep );
 742
 743                 LEI(ep)->lei_refcnt++;
 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_DETAIL1,
 750                            "cache_find_entry_id: %ld -> %s  found %d tries.\n",
 751                            ep_id, ep->e_dn, count ));
 752 #else
 753                 Debug(LDAP_DEBUG_TRACE,
 754                         "====> cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
 755                         ep_id, ep->e_dn, count);
 756 #endif
 757
 758
 759                 return( ep );
 760         }
 761
 762         /* free cache mutex */
 763         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 764
 765         return( NULL );
 766 }
 767
 768 /*
 769  * cache_delete_entry - delete the entry e from the cache.  the caller
 770  * should have obtained e (increasing its ref count) via a call to one
 771  * of the cache_find_* routines.  the caller should *not* call the
 772  * cache_return_entry() routine prior to calling cache_delete_entry().
 773  * it performs this function.
 774  *
 775  * returns:     0       e was deleted ok
 776  *              1       e was not in the cache
 777  *              -1      something bad happened
 778  */
 779 int
 780 cache_delete_entry(
 781     Cache       *cache,
 782     Entry               *e
 783 )
 784 {
 785         int     rc;
 786
 787         /* set cache mutex */
 788         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 789
 790         assert( e->e_private );
 791
 792 #ifdef NEW_LOGGING
 793         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
 794                    "cache_delete_entry: delete %ld.\n", e->e_id ));
 795 #else
 796         Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry( %ld )\n",
 797                 e->e_id, 0, 0 );
 798 #endif
 799
 800
 801         rc = cache_delete_entry_internal( cache, e );
 802
 803         /* free cache mutex */
 804         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 805         return( rc );
 806 }
 807
 808 static int
 809 cache_delete_entry_internal(
 810     Cache       *cache,
 811     Entry               *e
 812 )
 813 {
 814         int rc = 0;     /* return code */
 815
 816         /* dn tree */
 817         if ( avl_delete( &cache->c_dntree, (caddr_t) e, (AVL_CMP) entry_dn_cmp )
 818                 == NULL )
 819         {
 820                 rc = -1;
 821         }
 822
 823         /* id tree */
 824         if ( avl_delete( &cache->c_idtree, (caddr_t) e, (AVL_CMP) entry_id_cmp )
 825                 == NULL )
 826         {
 827                 rc = -1;
 828         }
 829
 830         if (rc != 0) {
 831                 return rc;
 832         }
 833
 834         /* lru */
 835         LRU_DELETE( cache, e );
 836         cache->c_cursize--;
 837
 838         /*
 839          * flag entry to be freed later by a call to cache_return_entry()
 840          */
 841         LEI(e)->lei_state = CACHE_ENTRY_DELETED;
 842
 843         return( 0 );
 844 }
 845
 846 void
 847 cache_release_all( Cache *cache )
 848 {
 849         Entry *e;
 850         int rc;
 851
 852         /* set cache mutex */
 853         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 854
 855 #ifdef NEW_LOGGING
 856         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
 857                    "cache_release_all: enter\n" ));
 858 #else
 859         Debug( LDAP_DEBUG_TRACE, "====> cache_release_all\n", 0, 0, 0 );
 860 #endif
 861
 862
 863         while ( (e = cache->c_lrutail) != NULL && LEI(e)->lei_refcnt == 0 ) {
 864 #ifdef LDAP_RDWR_DEBUG
 865                 assert(!ldap_pvt_thread_rdwr_active(&LEI(e)->lei_rdwr));
 866 #endif
 867
 868                 /* delete from cache and lru q */
 869                 /* XXX do we need rc ? */
 870                 rc = cache_delete_entry_internal( cache, e );
 871                 cache_entry_private_destroy( e );
 872                 entry_free( e );
 873         }
 874
 875         if ( cache->c_cursize ) {
 876 #ifdef NEW_LOGGING
 877                 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 878                            "cache_release_all: Entry cache could not be emptied.\n" ));
 879 #else
 880                 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
 881 #endif
 882
 883         }
 884
 885         /* free cache mutex */
 886         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 887 }
 888
 889 #ifdef LDAP_DEBUG
 890
 891 static void
 892 lru_print( Cache *cache )
 893 {
 894         Entry   *e;
 895
 896         fprintf( stderr, "LRU queue (head to tail):\n" );
 897         for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
 898                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 899                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 900         }
 901         fprintf( stderr, "LRU queue (tail to head):\n" );
 902         for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
 903                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 904                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 905         }
 906 }
 907
 908 #endif
 909