git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb2/cache.c

   1 /* cache.c - routines to maintain an in-core cache of entries */
   2
   3 #include "portable.h"
   4
   5 #include <stdio.h>
   6
   7 #include <ac/errno.h>
   8 #include <ac/string.h>
   9 #include <ac/socket.h>
  10
  11 #include "slap.h"
  12
  13 #include "back-bdb2.h"
  14
  15 /* LDBM backend specific entry info -- visible only to the cache */
  16 struct ldbm_entry_info {
  17         ldap_pvt_thread_rdwr_t  lei_rdwr;       /* reader/writer lock */
  18
  19         /*
  20          * remaining fields require backend cache lock to access
  21          * These items are specific to the LDBM backend and should
  22          * be hidden.
  23          */
  24         int             lei_state;      /* for the cache */
  25 #define CACHE_ENTRY_UNDEFINED   0
  26 #define CACHE_ENTRY_CREATING    1
  27 #define CACHE_ENTRY_READY               2
  28 #define CACHE_ENTRY_DELETED             3
  29
  30         int             lei_refcnt;     /* # threads ref'ing this entry */
  31         struct entry    *lei_lrunext;   /* for cache lru list */
  32         struct entry    *lei_lruprev;
  33 };
  34 #define LEI(e)  ((struct ldbm_entry_info *) ((e)->e_private))
  35
  36 static int      cache_delete_entry_internal(struct cache *cache, Entry *e);
  37 #ifdef LDAP_DEBUG
  38 static void     lru_print(struct cache *cache);
  39 #endif
  40
  41 static int
  42 cache_entry_rdwr_lock(Entry *e, int rw)
  43 {
  44         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
  45                 rw ? "w" : "r", e->e_id, 0);
  46
  47         if (rw)
  48                 return ldap_pvt_thread_rdwr_wlock(&LEI(e)->lei_rdwr);
  49         else
  50                 return ldap_pvt_thread_rdwr_rlock(&LEI(e)->lei_rdwr);
  51 }
  52
  53 static int
  54 cache_entry_rdwr_trylock(Entry *e, int rw)
  55 {
  56         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
  57                 rw ? "w" : "r", e->e_id, 0);
  58
  59         if (rw)
  60                 return ldap_pvt_thread_rdwr_wtrylock(&LEI(e)->lei_rdwr);
  61         else
  62                 return ldap_pvt_thread_rdwr_rtrylock(&LEI(e)->lei_rdwr);
  63 }
  64
  65 static int
  66 cache_entry_rdwr_unlock(Entry *e, int rw)
  67 {
  68         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
  69                 rw ? "w" : "r", e->e_id, 0);
  70
  71         if (rw)
  72                 return ldap_pvt_thread_rdwr_wunlock(&LEI(e)->lei_rdwr);
  73         else
  74                 return ldap_pvt_thread_rdwr_runlock(&LEI(e)->lei_rdwr);
  75 }
  76
  77 static int
  78 cache_entry_rdwr_init(Entry *e)
  79 {
  80         return ldap_pvt_thread_rdwr_init( &LEI(e)->lei_rdwr );
  81 }
  82
  83 static int
  84 cache_entry_rdwr_destroy(Entry *e)
  85 {
  86         return ldap_pvt_thread_rdwr_destroy( &LEI(e)->lei_rdwr );
  87 }
  88
  89 static int
  90 cache_entry_private_init( Entry*e )
  91 {
  92         struct ldbm_entry_info *lei;
  93
  94 #ifdef LDAP_DEBUG
  95         assert( e->e_private == NULL );
  96 #endif
  97
  98         if( e->e_private != NULL ) {
  99                 /* this should never happen */
 100                 return 1;
 101         }
 102
 103         e->e_private = ch_calloc(1, sizeof(struct ldbm_entry_info));
 104
 105         if( cache_entry_rdwr_init( e ) != 0 ) {
 106                 free( LEI(e) );
 107                 e->e_private = NULL;
 108                 return 1;
 109         }
 110
 111         return 0;
 112 }
 113
 114 static int
 115 cache_entry_private_destroy( Entry*e )
 116 {
 117         struct ldbm_entry_info *lei;
 118
 119 #ifdef LDAP_DEBUG
 120         assert( e->e_private );
 121 #endif
 122
 123         cache_entry_rdwr_destroy( e );
 124
 125         free( e->e_private );
 126         e->e_private = NULL;
 127         return 0;
 128 }
 129
 130 void
 131 bdb2i_cache_return_entry_rw( struct cache *cache, Entry *e, int rw )
 132 {
 133         /* set cache mutex */
 134         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 135
 136 #ifdef LDAP_DEBUG
 137         assert( e->e_private );
 138 #endif
 139
 140         cache_entry_rdwr_unlock(e, rw);
 141
 142         LEI(e)->lei_refcnt--;
 143
 144         if ( LEI(e)->lei_state == CACHE_ENTRY_CREATING ) {
 145                 Debug( LDAP_DEBUG_TRACE,
 146                         "====> bdb2i_cache_return_entry_%s( %ld ): created (%d)\n",
 147                         rw ? "w" : "r", e->e_id, LEI(e)->lei_refcnt );
 148
 149                 LEI(e)->lei_state = CACHE_ENTRY_READY;
 150
 151         } else if ( LEI(e)->lei_state == CACHE_ENTRY_DELETED ) {
 152                 if( LEI(e)->lei_refcnt > 0 ) {
 153                         Debug( LDAP_DEBUG_TRACE,
 154                         "====> bdb2i_cache_return_entry_%s( %ld ): delete pending (%d)\n",
 155                                 rw ? "w" : "r", e->e_id, LEI(e)->lei_refcnt );
 156
 157                 } else {
 158                         Debug( LDAP_DEBUG_TRACE,
 159                                 "====> bdb2i_cache_return_entry_%s( %ld ): deleted (%d)\n",
 160                                 rw ? "w" : "r", e->e_id, LEI(e)->lei_refcnt );
 161
 162                         cache_entry_private_destroy( e );
 163                         entry_free( e );
 164                 }
 165
 166         } else {
 167                 Debug( LDAP_DEBUG_TRACE,
 168                         "====> bdb2i_cache_return_entry_%s( %ld ): returned (%d)\n",
 169                         rw ? "w" : "r", e->e_id, LEI(e)->lei_refcnt);
 170         }
 171
 172         /* free cache mutex */
 173         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 174 }
 175
 176 #define LRU_DELETE( cache, e ) { \
 177         if ( LEI(e)->lei_lruprev != NULL ) { \
 178                 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
 179         } else { \
 180                 cache->c_lruhead = LEI(e)->lei_lrunext; \
 181         } \
 182         if ( LEI(e)->lei_lrunext != NULL ) { \
 183                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
 184         } else { \
 185                 cache->c_lrutail = LEI(e)->lei_lruprev; \
 186         } \
 187 }
 188
 189 #define LRU_ADD( cache, e ) { \
 190         LEI(e)->lei_lrunext = cache->c_lruhead; \
 191         if ( LEI(e)->lei_lrunext != NULL ) { \
 192                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = e; \
 193         } \
 194         cache->c_lruhead = e; \
 195         LEI(e)->lei_lruprev = NULL; \
 196         if ( cache->c_lrutail == NULL ) { \
 197                 cache->c_lrutail = e; \
 198         } \
 199 }
 200
 201 /*
 202  * bdb2i_cache_add_entry_rw - create and lock an entry in the cache
 203  * returns:     0       entry has been created and locked
 204  *              1       entry already existed
 205  *              -1      something bad happened
 206  */
 207 int
 208 bdb2i_cache_add_entry_rw(
 209     struct cache        *cache,
 210     Entry               *e,
 211         int             rw
 212 )
 213 {
 214         int     i, rc;
 215         Entry   *ee;
 216
 217         /* set cache mutex */
 218         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 219
 220 #ifdef LDAP_DEBUG
 221         assert( e->e_private == NULL );
 222 #endif
 223
 224         if( cache_entry_private_init(e) != 0 ) {
 225                 Debug( LDAP_DEBUG_ANY,
 226                 "====> bdb2i_cache_add_entry( %ld ): \"%s\": private init failed!\n",
 227                     e->e_id, e->e_dn, 0 );
 228                 return( -1 );
 229         }
 230
 231         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 232                 entry_dn_cmp, avl_dup_error ) != 0 )
 233         {
 234                 Debug( LDAP_DEBUG_TRACE,
 235                 "====> bdb2i_cache_add_entry( %ld ): \"%s\": already in dn cache\n",
 236                     e->e_id, e->e_dn, 0 );
 237
 238                 cache_entry_private_destroy(e);
 239
 240                 /* free cache mutex */
 241                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 242                 return( 1 );
 243         }
 244
 245         /* id tree */
 246         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 247                 entry_id_cmp, avl_dup_error ) != 0 )
 248         {
 249                 Debug( LDAP_DEBUG_ANY,
 250                 "====> bdb2i_cache_add_entry( %ld ): \"%s\": already in id cache\n",
 251                     e->e_id, e->e_dn, 0 );
 252
 253                 /* delete from dn tree inserted above */
 254                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 255                         entry_dn_cmp ) == NULL )
 256                 {
 257                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 258                             0, 0, 0 );
 259                 }
 260
 261                 cache_entry_private_destroy(e);
 262
 263                 /* free cache mutex */
 264                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 265                 return( -1 );
 266         }
 267
 268         cache_entry_rdwr_lock( e, rw );
 269
 270         /* put the entry into 'CREATING' state */
 271         /* will be marked after when entry is returned */
 272         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
 273         LEI(e)->lei_refcnt = 1;
 274
 275         /* lru */
 276         LRU_ADD( cache, e );
 277         if ( ++cache->c_cursize > cache->c_maxsize ) {
 278                 /*
 279                  * find the lru entry not currently in use and delete it.
 280                  * in case a lot of entries are in use, only look at the
 281                  * first 10 on the tail of the list.
 282                  */
 283                 i = 0;
 284                 while ( cache->c_lrutail != NULL &&
 285                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 286                         i < 10 )
 287                 {
 288                         /* move this in-use entry to the front of the q */
 289                         ee = cache->c_lrutail;
 290                         LRU_DELETE( cache, ee );
 291                         LRU_ADD( cache, ee );
 292                         i++;
 293                 }
 294
 295                 /*
 296                  * found at least one to delete - try to get back under
 297                  * the max cache size.
 298                  */
 299                 while ( cache->c_lrutail != NULL &&
 300                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 301                         cache->c_cursize > cache->c_maxsize )
 302                 {
 303                         e = cache->c_lrutail;
 304
 305                         /* delete from cache and lru q */
 306                         /* XXX do we need rc ? */
 307                         rc = cache_delete_entry_internal( cache, e );
 308                         cache_entry_private_destroy( e );
 309                         entry_free( e );
 310                 }
 311         }
 312
 313         /* free cache mutex */
 314         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 315         return( 0 );
 316 }
 317
 318 /*
 319  * cache_update_entry - update a LOCKED entry which has been deleted.
 320  * returns:     0       entry has been created and locked
 321  *              1       entry already existed
 322  *              -1      something bad happened
 323  */
 324 int
 325 bdb2i_cache_update_entry(
 326     struct cache        *cache,
 327     Entry               *e
 328 )
 329 {
 330         int     i, rc;
 331         Entry   *ee;
 332
 333         /* set cache mutex */
 334         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 335
 336 #ifdef LDAP_DEBUG
 337         assert( e->e_private );
 338 #endif
 339
 340         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 341                 entry_dn_cmp, avl_dup_error ) != 0 )
 342         {
 343                 Debug( LDAP_DEBUG_TRACE,
 344                 "====> bdb2i_cache_add_entry( %ld ): \"%s\": already in dn cache\n",
 345                     e->e_id, e->e_dn, 0 );
 346
 347                 /* free cache mutex */
 348                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 349                 return( 1 );
 350         }
 351
 352         /* id tree */
 353         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 354                 entry_id_cmp, avl_dup_error ) != 0 )
 355         {
 356                 Debug( LDAP_DEBUG_ANY,
 357                 "====> bdb2i_cache_update_entry( %ld ): \"%s\": already in id cache\n",
 358                     e->e_id, e->e_dn, 0 );
 359
 360                 /* delete from dn tree inserted above */
 361                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 362                         entry_dn_cmp ) == NULL )
 363                 {
 364                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 365                             0, 0, 0 );
 366                 }
 367
 368                 /* free cache mutex */
 369                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 370                 return( -1 );
 371         }
 372
 373         /* put the entry into 'CREATING' state */
 374         /* will be marked after when entry is returned */
 375         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
 376
 377         /* lru */
 378         LRU_ADD( cache, e );
 379         if ( ++cache->c_cursize > cache->c_maxsize ) {
 380                 /*
 381                  * find the lru entry not currently in use and delete it.
 382                  * in case a lot of entries are in use, only look at the
 383                  * first 10 on the tail of the list.
 384                  */
 385                 i = 0;
 386                 while ( cache->c_lrutail != NULL &&
 387                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 388                         i < 10 )
 389                 {
 390                         /* move this in-use entry to the front of the q */
 391                         ee = cache->c_lrutail;
 392                         LRU_DELETE( cache, ee );
 393                         LRU_ADD( cache, ee );
 394                         i++;
 395                 }
 396
 397                 /*
 398                  * found at least one to delete - try to get back under
 399                  * the max cache size.
 400                  */
 401                 while ( cache->c_lrutail != NULL &&
 402                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 403                         cache->c_cursize > cache->c_maxsize )
 404                 {
 405                         e = cache->c_lrutail;
 406
 407                         /* delete from cache and lru q */
 408                         /* XXX do we need rc ? */
 409                         rc = cache_delete_entry_internal( cache, e );
 410                         cache_entry_private_destroy( e );
 411                         entry_free( e );
 412                 }
 413         }
 414
 415         /* free cache mutex */
 416         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 417         return( 0 );
 418 }
 419
 420 /*
 421  * cache_find_entry_dn2id - find an entry in the cache, given dn
 422  */
 423
 424 ID
 425 bdb2i_cache_find_entry_dn2id(
 426         BackendDB               *be,
 427     struct cache        *cache,
 428     char                *dn
 429 )
 430 {
 431         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
 432         Entry           e, *ep;
 433         ID                      id;
 434
 435         /* set cache mutex */
 436         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 437
 438         e.e_dn = dn;
 439         e.e_ndn = dn_normalize_case( ch_strdup( dn ) );
 440
 441         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 442                 entry_dn_cmp )) != NULL )
 443         {
 444                 /*
 445                  * ep now points to an unlocked entry
 446                  * we do not need to lock the entry if we only
 447                  * check the state, refcnt, LRU, and id.
 448                  */
 449                 free(e.e_ndn);
 450
 451 #ifdef LDAP_DEBUG
 452                 assert( ep->e_private );
 453 #endif
 454
 455                 /*
 456                  * entry is deleted or not fully created yet
 457                  */
 458                 if ( LEI(ep)->lei_state != CACHE_ENTRY_READY ) {
 459 #ifdef LDAP_DEBUG
 460                         assert(LEI(ep)->lei_state != CACHE_ENTRY_UNDEFINED);
 461 #endif
 462                         Debug(LDAP_DEBUG_TRACE,
 463                         "====> bdb2i_cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
 464                                 dn, ep->e_id, LEI(ep)->lei_state);
 465
 466                         /* free cache mutex */
 467                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 468                         return( NOID );
 469                 }
 470
 471                 Debug(LDAP_DEBUG_TRACE,
 472                         "====> bdb2i_cache_find_entry_dn2id(\"%s\"): %ld\n",
 473                         dn, ep->e_id, 0);
 474
 475                 /* lru */
 476                 LRU_DELETE( cache, ep );
 477                 LRU_ADD( cache, ep );
 478
 479                 /* save id */
 480                 id = ep->e_id;
 481
 482                 /* free cache mutex */
 483                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 484
 485                 return( id );
 486         }
 487
 488         free(e.e_ndn);
 489
 490         /* free cache mutex */
 491         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 492
 493         return( NOID );
 494 }
 495
 496 /*
 497  * cache_find_entry_id - find an entry in the cache, given id
 498  */
 499
 500 Entry *
 501 bdb2i_cache_find_entry_id(
 502         struct cache    *cache,
 503         ID                              id,
 504         int                             rw
 505 )
 506 {
 507         Entry   e;
 508         Entry   *ep;
 509
 510         e.e_id = id;
 511
 512 try_again:
 513         /* set cache mutex */
 514         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 515
 516         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 517                 entry_id_cmp )) != NULL )
 518         {
 519 #ifdef LDAP_DEBUG
 520                 assert( ep->e_private );
 521 #endif
 522
 523                 /*
 524                  * entry is deleted or not fully created yet
 525                  */
 526                 if ( LEI(ep)->lei_state != CACHE_ENTRY_READY ) {
 527 #ifdef LDAP_DEBUG
 528                         assert(LEI(ep)->lei_state != CACHE_ENTRY_UNDEFINED);
 529 #endif
 530                         Debug(LDAP_DEBUG_TRACE,
 531                                 "====> bdb2i_cache_find_entry_id( %ld ): %ld (not ready) %d\n",
 532                                 id, ep->e_id, LEI(ep)->lei_state);
 533
 534                         /* free cache mutex */
 535                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 536                         return( NULL );
 537                 }
 538
 539                 Debug(LDAP_DEBUG_TRACE,
 540                         "====> bdb2i_cache_find_entry_id( %ld, %s ) \"%s\" (found)\n",
 541                         id, rw ? "w" : "r", ep->e_dn);
 542
 543                 /* acquire reader lock */
 544                 if ( cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
 545                         /* could not acquire entry lock...
 546                          * owner cannot free as we have the cache locked.
 547                          * so, unlock the cache, yield, and try again.
 548                          */
 549
 550                         /* free cache mutex */
 551                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 552                         ldap_pvt_thread_yield();
 553                         goto try_again;
 554                 }
 555
 556                 /* lru */
 557                 LRU_DELETE( cache, ep );
 558                 LRU_ADD( cache, ep );
 559
 560                 LEI(ep)->lei_refcnt++;
 561
 562                 /* free cache mutex */
 563                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 564
 565                 return( ep );
 566         }
 567
 568         /* free cache mutex */
 569         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 570
 571         return( NULL );
 572 }
 573
 574 /*
 575  * cache_delete_entry - delete the entry e from the cache.  the caller
 576  * should have obtained e (increasing its ref count) via a call to one
 577  * of the cache_find_* routines.  the caller should *not* call the
 578  * cache_return_entry() routine prior to calling cache_delete_entry().
 579  * it performs this function.
 580  *
 581  * returns:     0       e was deleted ok
 582  *              1       e was not in the cache
 583  *              -1      something bad happened
 584  */
 585 int
 586 bdb2i_cache_delete_entry(
 587     struct cache        *cache,
 588     Entry               *e
 589 )
 590 {
 591         int     rc;
 592
 593         /* set cache mutex */
 594         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 595
 596 #ifdef LDAP_DEBUG
 597         assert( e->e_private );
 598 #endif
 599
 600         Debug( LDAP_DEBUG_TRACE, "====> bdb2i_cache_delete_entry( %ld )\n",
 601                 e->e_id, 0, 0 );
 602
 603         rc = cache_delete_entry_internal( cache, e );
 604
 605         /* free cache mutex */
 606         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 607         return( rc );
 608 }
 609
 610 static int
 611 cache_delete_entry_internal(
 612     struct cache        *cache,
 613     Entry               *e
 614 )
 615 {
 616         int rc = 0;     /* return code */
 617
 618         /* dn tree */
 619         if ( avl_delete( &cache->c_dntree, (caddr_t) e, entry_dn_cmp )
 620                 == NULL )
 621         {
 622                 rc = -1;
 623         }
 624
 625         /* id tree */
 626         if ( avl_delete( &cache->c_idtree, (caddr_t) e, entry_id_cmp )
 627                 == NULL )
 628         {
 629                 rc = -1;
 630         }
 631
 632         if (rc != 0) {
 633                 return rc;
 634         }
 635
 636         /* lru */
 637         LRU_DELETE( cache, e );
 638         cache->c_cursize--;
 639
 640         /*
 641          * flag entry to be freed later by a call to cache_return_entry()
 642          */
 643         LEI(e)->lei_state = CACHE_ENTRY_DELETED;
 644
 645         return( 0 );
 646 }
 647
 648 #ifdef LDAP_DEBUG
 649
 650 static void
 651 lru_print( struct cache *cache )
 652 {
 653         Entry   *e;
 654
 655         fprintf( stderr, "LRU queue (head to tail):\n" );
 656         for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
 657                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 658                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 659         }
 660         fprintf( stderr, "LRU queue (tail to head):\n" );
 661         for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
 662                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 663                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 664         }
 665 }
 666
 667 #endif
 668