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
   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-ldbm.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 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                         "====> 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                                 "====> 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                                 "====> 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                         "====> cache_return_entry_%s( %ld ): returned (%d)\n",
 169                         rw ? "w" : "r", e->e_id, LEI(e)->lei_refcnt);
 170         }
 171
 172
 173         /* free cache mutex */
 174         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 175 }
 176
 177 #define LRU_DELETE( cache, e ) { \
 178         if ( LEI(e)->lei_lruprev != NULL ) { \
 179                 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
 180         } else { \
 181                 cache->c_lruhead = LEI(e)->lei_lrunext; \
 182         } \
 183         if ( LEI(e)->lei_lrunext != NULL ) { \
 184                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
 185         } else { \
 186                 cache->c_lrutail = LEI(e)->lei_lruprev; \
 187         } \
 188 }
 189
 190 #define LRU_ADD( cache, e ) { \
 191         LEI(e)->lei_lrunext = cache->c_lruhead; \
 192         if ( LEI(e)->lei_lrunext != NULL ) { \
 193                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = e; \
 194         } \
 195         cache->c_lruhead = e; \
 196         LEI(e)->lei_lruprev = NULL; \
 197         if ( cache->c_lrutail == NULL ) { \
 198                 cache->c_lrutail = e; \
 199         } \
 200 }
 201
 202 /*
 203  * cache_add_entry_rw - create and lock an entry in the cache
 204  * returns:     0       entry has been created and locked
 205  *              1       entry already existed
 206  *              -1      something bad happened
 207  */
 208 int
 209 cache_add_entry_rw(
 210     struct cache        *cache,
 211     Entry               *e,
 212         int             rw
 213 )
 214 {
 215         int     i, rc;
 216         Entry   *ee;
 217
 218         /* set cache mutex */
 219         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 220
 221 #ifdef LDAP_DEBUG
 222         assert( e->e_private == NULL );
 223 #endif
 224
 225         if( cache_entry_private_init(e) != 0 ) {
 226                 Debug( LDAP_DEBUG_ANY,
 227                         "====> cache_add_entry( %ld ): \"%s\": private init failed!\n",
 228                     e->e_id, e->e_dn, 0 );
 229                 return( -1 );
 230         }
 231
 232         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 233                 entry_dn_cmp, avl_dup_error ) != 0 )
 234         {
 235                 Debug( LDAP_DEBUG_TRACE,
 236                         "====> cache_add_entry( %ld ): \"%s\": already in dn cache\n",
 237                     e->e_id, e->e_dn, 0 );
 238
 239                 cache_entry_private_destroy(e);
 240
 241                 /* free cache mutex */
 242                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 243                 return( 1 );
 244         }
 245
 246         /* id tree */
 247         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 248                 entry_id_cmp, avl_dup_error ) != 0 )
 249         {
 250                 Debug( LDAP_DEBUG_ANY,
 251                         "====> cache_add_entry( %ld ): \"%s\": already in id cache\n",
 252                     e->e_id, e->e_dn, 0 );
 253
 254
 255                 /* delete from dn tree inserted above */
 256                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 257                         entry_dn_cmp ) == NULL )
 258                 {
 259                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 260                             0, 0, 0 );
 261                 }
 262
 263                 cache_entry_private_destroy(e);
 264
 265                 /* free cache mutex */
 266                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 267                 return( -1 );
 268         }
 269
 270         cache_entry_rdwr_lock( e, rw );
 271
 272         /* put the entry into 'CREATING' state */
 273         /* will be marked after when entry is returned */
 274         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
 275         LEI(e)->lei_refcnt = 1;
 276
 277         /* lru */
 278         LRU_ADD( cache, e );
 279         if ( ++cache->c_cursize > cache->c_maxsize ) {
 280                 /*
 281                  * find the lru entry not currently in use and delete it.
 282                  * in case a lot of entries are in use, only look at the
 283                  * first 10 on the tail of the list.
 284                  */
 285                 i = 0;
 286                 while ( cache->c_lrutail != NULL &&
 287                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 288                         i < 10 )
 289                 {
 290                         /* move this in-use entry to the front of the q */
 291                         ee = cache->c_lrutail;
 292                         LRU_DELETE( cache, ee );
 293                         LRU_ADD( cache, ee );
 294                         i++;
 295                 }
 296
 297                 /*
 298                  * found at least one to delete - try to get back under
 299                  * the max cache size.
 300                  */
 301                 while ( cache->c_lrutail != NULL &&
 302                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 303                         cache->c_cursize > cache->c_maxsize )
 304                 {
 305                         e = cache->c_lrutail;
 306
 307                         /* delete from cache and lru q */
 308                         /* XXX do we need rc ? */
 309                         rc = cache_delete_entry_internal( cache, e );
 310                         cache_entry_private_destroy( e );
 311                         entry_free( e );
 312                 }
 313         }
 314
 315         /* free cache mutex */
 316         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 317         return( 0 );
 318 }
 319
 320 /*
 321  * cache_update_entry - update a LOCKED entry which has been deleted.
 322  * returns:     0       entry has been created and locked
 323  *              1       entry already existed
 324  *              -1      something bad happened
 325  */
 326 int
 327 cache_update_entry(
 328     struct cache        *cache,
 329     Entry               *e
 330 )
 331 {
 332         int     i, rc;
 333         Entry   *ee;
 334
 335         /* set cache mutex */
 336         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 337
 338 #ifdef LDAP_DEBUG
 339         assert( e->e_private );
 340 #endif
 341
 342         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 343                 entry_dn_cmp, avl_dup_error ) != 0 )
 344         {
 345                 Debug( LDAP_DEBUG_TRACE,
 346                         "====> cache_update_entry( %ld ): \"%s\": already in dn cache\n",
 347                     e->e_id, e->e_dn, 0 );
 348
 349                 /* free cache mutex */
 350                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 351                 return( 1 );
 352         }
 353
 354         /* id tree */
 355         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 356                 entry_id_cmp, avl_dup_error ) != 0 )
 357         {
 358                 Debug( LDAP_DEBUG_ANY,
 359                         "====> cache_update_entry( %ld ): \"%s\": already in id cache\n",
 360                     e->e_id, e->e_dn, 0 );
 361
 362                 /* delete from dn tree inserted above */
 363                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 364                         entry_dn_cmp ) == NULL )
 365                 {
 366                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 367                             0, 0, 0 );
 368                 }
 369
 370                 /* free cache mutex */
 371                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 372                 return( -1 );
 373         }
 374
 375
 376         /* put the entry into 'CREATING' state */
 377         /* will be marked after when entry is returned */
 378         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
 379
 380         /* lru */
 381         LRU_ADD( cache, e );
 382         if ( ++cache->c_cursize > cache->c_maxsize ) {
 383                 /*
 384                  * find the lru entry not currently in use and delete it.
 385                  * in case a lot of entries are in use, only look at the
 386                  * first 10 on the tail of the list.
 387                  */
 388                 i = 0;
 389                 while ( cache->c_lrutail != NULL &&
 390                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 391                         i < 10 )
 392                 {
 393                         /* move this in-use entry to the front of the q */
 394                         ee = cache->c_lrutail;
 395                         LRU_DELETE( cache, ee );
 396                         LRU_ADD( cache, ee );
 397                         i++;
 398                 }
 399
 400                 /*
 401                  * found at least one to delete - try to get back under
 402                  * the max cache size.
 403                  */
 404                 while ( cache->c_lrutail != NULL &&
 405                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 406                         cache->c_cursize > cache->c_maxsize )
 407                 {
 408                         e = cache->c_lrutail;
 409
 410                         /* delete from cache and lru q */
 411                         /* XXX do we need rc ? */
 412                         rc = cache_delete_entry_internal( cache, e );
 413                         cache_entry_private_destroy( e );
 414                         entry_free( e );
 415                 }
 416         }
 417
 418         /* free cache mutex */
 419         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 420         return( 0 );
 421 }
 422
 423 /*
 424  * cache_find_entry_dn2id - find an entry in the cache, given dn
 425  */
 426
 427 ID
 428 cache_find_entry_dn2id(
 429         Backend         *be,
 430     struct cache        *cache,
 431     char                *dn
 432 )
 433 {
 434         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
 435         Entry           e, *ep;
 436         ID                      id;
 437
 438         /* set cache mutex */
 439         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 440
 441         e.e_dn = dn;
 442         e.e_ndn = dn_normalize_case( ch_strdup( dn ) );
 443
 444         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 445                 entry_dn_cmp )) != NULL )
 446         {
 447                 /*
 448                  * ep now points to an unlocked entry
 449                  * we do not need to lock the entry if we only
 450                  * check the state, refcnt, LRU, and id.
 451                  */
 452                 free(e.e_ndn);
 453
 454 #ifdef LDAP_DEBUG
 455                 assert( ep->e_private );
 456 #endif
 457                 /*
 458                  * entry is deleted or not fully created yet
 459                  */
 460                 if ( LEI(ep)->lei_state != CACHE_ENTRY_READY ) {
 461 #ifdef LDAP_DEBUG
 462                         assert(LEI(ep)->lei_state != CACHE_ENTRY_UNDEFINED);
 463 #endif
 464                         Debug(LDAP_DEBUG_TRACE,
 465                                 "====> cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
 466                                 dn, ep->e_id, LEI(ep)->lei_state);
 467
 468                         /* free cache mutex */
 469                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 470                         return( NOID );
 471                 }
 472
 473                 Debug(LDAP_DEBUG_TRACE,
 474                         "====> cache_find_entry_dn2id(\"%s\"): %ld\n",
 475                         dn, ep->e_id, 0);
 476
 477                 /* lru */
 478                 LRU_DELETE( cache, ep );
 479                 LRU_ADD( cache, ep );
 480
 481                 /* save id */
 482                 id = ep->e_id;
 483
 484                 /* free cache mutex */
 485                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 486
 487                 return( id );
 488         }
 489
 490         free(e.e_ndn);
 491
 492         /* free cache mutex */
 493         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 494
 495         return( NOID );
 496 }
 497
 498 /*
 499  * cache_find_entry_id - find an entry in the cache, given id
 500  */
 501
 502 Entry *
 503 cache_find_entry_id(
 504         struct cache    *cache,
 505         ID                              id,
 506         int                             rw
 507 )
 508 {
 509         Entry   e;
 510         Entry   *ep;
 511
 512         e.e_id = id;
 513
 514 try_again:
 515         /* set cache mutex */
 516         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 517
 518         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 519                 entry_id_cmp )) != NULL )
 520         {
 521 #ifdef LDAP_DEBUG
 522                 assert( ep->e_private );
 523 #endif
 524                 /*
 525                  * entry is deleted or not fully created yet
 526                  */
 527                 if ( LEI(ep)->lei_state != CACHE_ENTRY_READY ) {
 528 #ifdef LDAP_DEBUG
 529                         assert(LEI(ep)->lei_state != CACHE_ENTRY_UNDEFINED);
 530 #endif
 531                         Debug(LDAP_DEBUG_TRACE,
 532                                 "====> cache_find_entry_id( %ld ): %ld (not ready) %d\n",
 533                                 id, ep->e_id, LEI(ep)->lei_state);
 534
 535                         /* free cache mutex */
 536                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 537                         return( NULL );
 538                 }
 539
 540                 Debug(LDAP_DEBUG_TRACE,
 541                         "====> cache_find_entry_id( %ld, %s ) \"%s\" (found)\n",
 542                         id, rw ? "w" : "r", ep->e_dn);
 543
 544                 /* acquire reader lock */
 545                 if ( cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
 546                         /* could not acquire entry lock...
 547                          * owner cannot free as we have the cache locked.
 548                          * so, unlock the cache, yield, and try again.
 549                          */
 550
 551                         /* free cache mutex */
 552                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 553                         ldap_pvt_thread_yield();
 554                         goto try_again;
 555                 }
 556
 557                 /* lru */
 558                 LRU_DELETE( cache, ep );
 559                 LRU_ADD( cache, ep );
 560
 561                 LEI(ep)->lei_refcnt++;
 562
 563                 /* free cache mutex */
 564                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 565
 566                 return( ep );
 567         }
 568
 569         /* free cache mutex */
 570         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 571
 572         return( NULL );
 573 }
 574
 575 /*
 576  * cache_delete_entry - delete the entry e from the cache.  the caller
 577  * should have obtained e (increasing its ref count) via a call to one
 578  * of the cache_find_* routines.  the caller should *not* call the
 579  * cache_return_entry() routine prior to calling cache_delete_entry().
 580  * it performs this function.
 581  *
 582  * returns:     0       e was deleted ok
 583  *              1       e was not in the cache
 584  *              -1      something bad happened
 585  */
 586 int
 587 cache_delete_entry(
 588     struct cache        *cache,
 589     Entry               *e
 590 )
 591 {
 592         int     rc;
 593
 594         /* set cache mutex */
 595         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 596
 597 #ifdef LDAP_DEBUG
 598         assert( e->e_private );
 599 #endif
 600
 601         Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry( %ld )\n",
 602                 e->e_id, 0, 0 );
 603
 604         rc = cache_delete_entry_internal( cache, e );
 605
 606         /* free cache mutex */
 607         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 608         return( rc );
 609 }
 610
 611 static int
 612 cache_delete_entry_internal(
 613     struct cache        *cache,
 614     Entry               *e
 615 )
 616 {
 617         int rc = 0;     /* return code */
 618
 619         /* dn tree */
 620         if ( avl_delete( &cache->c_dntree, (caddr_t) e, entry_dn_cmp )
 621                 == NULL )
 622         {
 623                 rc = -1;
 624         }
 625
 626         /* id tree */
 627         if ( avl_delete( &cache->c_idtree, (caddr_t) e, entry_id_cmp )
 628                 == NULL )
 629         {
 630                 rc = -1;
 631         }
 632
 633         if (rc != 0) {
 634                 return rc;
 635         }
 636
 637         /* lru */
 638         LRU_DELETE( cache, e );
 639         cache->c_cursize--;
 640
 641         /*
 642          * flag entry to be freed later by a call to cache_return_entry()
 643          */
 644         LEI(e)->lei_state = CACHE_ENTRY_DELETED;
 645
 646         return( 0 );
 647 }
 648
 649 #ifdef LDAP_DEBUG
 650
 651 static void
 652 lru_print( struct cache *cache )
 653 {
 654         Entry   *e;
 655
 656         fprintf( stderr, "LRU queue (head to tail):\n" );
 657         for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
 658                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 659                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 660         }
 661         fprintf( stderr, "LRU queue (tail to head):\n" );
 662         for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
 663                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 664                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 665         }
 666 }
 667
 668 #endif
 669