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