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