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
  26         int             lei_refcnt;     /* # threads ref'ing this entry */
  27         struct entry    *lei_lrunext;   /* for cache lru list */
  28         struct entry    *lei_lruprev;
  29 };
  30 #define LEI(e)  ((struct ldbm_entry_info *) ((e)->e_private))
  31
  32 static int      cache_delete_entry_internal(struct cache *cache, Entry *e);
  33 #ifdef LDAP_DEBUG
  34 static void     lru_print(struct cache *cache);
  35 #endif
  36
  37 /*
  38  * the cache has three entry points (ways to find things):
  39  *
  40  *      by entry        e.g., if you already have an entry from the cache
  41  *                      and want to delete it. (really by entry ptr)
  42  *      by dn           e.g., when looking for the base object of a search
  43  *      by id           e.g., for search candidates
  44  *
  45  * these correspond to three different avl trees that are maintained.
  46  */
  47
  48 static int
  49 cache_entry_cmp( Entry *e1, Entry *e2 )
  50 {
  51         return( e1 < e2 ? -1 : (e1 > e2 ? 1 : 0) );
  52 }
  53
  54 static int
  55 cache_entrydn_cmp( Entry *e1, Entry *e2 )
  56 {
  57         /* compare their normalized UPPERCASED dn's */
  58         return( strcmp( e1->e_ndn, e2->e_ndn ) );
  59 }
  60
  61 static int
  62 cache_entryid_cmp( Entry *e1, Entry *e2 )
  63 {
  64         return( e1->e_id < e2->e_id ? -1 : (e1->e_id > e2->e_id ? 1 : 0) );
  65 }
  66
  67 void
  68 cache_set_state( struct cache *cache, Entry *e, int state )
  69 {
  70         /* set cache mutex */
  71         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
  72
  73         LEI(e)->lei_state = state;
  74
  75         /* free cache mutex */
  76         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
  77 }
  78
  79 static int
  80 cache_entry_rdwr_lock(Entry *e, int rw)
  81 {
  82         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
  83                 rw ? "w" : "r", e->e_id, 0);
  84
  85         if (rw)
  86                 return ldap_pvt_thread_rdwr_wlock(&LEI(e)->lei_rdwr);
  87         else
  88                 return ldap_pvt_thread_rdwr_rlock(&LEI(e)->lei_rdwr);
  89 }
  90
  91 static int
  92 cache_entry_rdwr_trylock(Entry *e, int rw)
  93 {
  94         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
  95                 rw ? "w" : "r", e->e_id, 0);
  96
  97         if (rw)
  98                 return ldap_pvt_thread_rdwr_wtrylock(&LEI(e)->lei_rdwr);
  99         else
 100                 return ldap_pvt_thread_rdwr_rtrylock(&LEI(e)->lei_rdwr);
 101 }
 102
 103 static int
 104 cache_entry_rdwr_unlock(Entry *e, int rw)
 105 {
 106         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
 107                 rw ? "w" : "r", e->e_id, 0);
 108
 109         if (rw)
 110                 return ldap_pvt_thread_rdwr_wunlock(&LEI(e)->lei_rdwr);
 111         else
 112                 return ldap_pvt_thread_rdwr_runlock(&LEI(e)->lei_rdwr);
 113 }
 114
 115 static int
 116 cache_entry_rdwr_init(Entry *e)
 117 {
 118         return ldap_pvt_thread_rdwr_init( &LEI(e)->lei_rdwr );
 119 }
 120
 121 static int
 122 cache_entry_rdwr_destroy(Entry *e)
 123 {
 124         return ldap_pvt_thread_rdwr_destroy( &LEI(e)->lei_rdwr );
 125 }
 126
 127 static int
 128 cache_entry_private_init( Entry*e )
 129 {
 130         struct ldbm_entry_info *lei;
 131
 132         if( e->e_private != NULL ) {
 133                 return 1;
 134         }
 135
 136         e->e_private = ch_calloc(1, sizeof(struct ldbm_entry_info));
 137
 138         if( cache_entry_rdwr_init( e ) != 0 ) {
 139                 free( LEI(e) );
 140                 return 1;
 141         }
 142
 143         return 0;
 144 }
 145
 146 static int
 147 cache_entry_private_destroy( Entry*e )
 148 {
 149         struct ldbm_entry_info *lei;
 150
 151         if( e->e_private == NULL ) {
 152                 return 1;
 153         }
 154
 155         cache_entry_rdwr_destroy( e );
 156
 157         free( e->e_private );
 158         e->e_private = NULL;
 159         return 0;
 160 }
 161
 162 static void
 163 cache_return_entry_rw( struct cache *cache, Entry *e, int rw )
 164 {
 165         Debug( LDAP_DEBUG_TRACE, "====> cache_return_entry_%s\n",
 166                 rw ? "w" : "r", 0, 0);
 167
 168         /* set cache mutex */
 169         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 170
 171         cache_entry_rdwr_unlock(e, rw);
 172
 173         if ( --LEI(e)->lei_refcnt == 0 &&
 174                 LEI(e)->lei_state == ENTRY_STATE_DELETED )
 175         {
 176                 cache_entry_private_destroy( e );
 177                 entry_free( e );
 178         }
 179
 180         /* free cache mutex */
 181         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 182 }
 183
 184 void
 185 cache_return_entry_r( struct cache *cache, Entry *e )
 186 {
 187         cache_return_entry_rw(cache, e, 0);
 188 }
 189
 190 void
 191 cache_return_entry_w( struct cache *cache, Entry *e )
 192 {
 193         cache_return_entry_rw(cache, e, 1);
 194 }
 195
 196
 197 #define LRU_DELETE( cache, e ) { \
 198         if ( LEI(e)->lei_lruprev != NULL ) { \
 199                 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
 200         } else { \
 201                 cache->c_lruhead = LEI(e)->lei_lrunext; \
 202         } \
 203         if ( LEI(e)->lei_lrunext != NULL ) { \
 204                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
 205         } else { \
 206                 cache->c_lrutail = LEI(e)->lei_lruprev; \
 207         } \
 208 }
 209
 210 #define LRU_ADD( cache, e ) { \
 211         LEI(e)->lei_lrunext = cache->c_lruhead; \
 212         if ( LEI(e)->lei_lrunext != NULL ) { \
 213                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = e; \
 214         } \
 215         cache->c_lruhead = e; \
 216         LEI(e)->lei_lruprev = NULL; \
 217         if ( cache->c_lrutail == NULL ) { \
 218                 cache->c_lrutail = e; \
 219         } \
 220 }
 221
 222 /*
 223  * cache_add_entry_rw - create and lock an entry in the cache
 224  * returns:     0       entry has been created and locked
 225  *              1       entry already existed
 226  *              -1      something bad happened
 227  */
 228 int
 229 cache_add_entry_rw(
 230     struct cache        *cache,
 231     Entry               *e,
 232     int                 state,
 233         int             rw
 234 )
 235 {
 236         int     i, rc;
 237         Entry   *ee;
 238
 239         /* set cache mutex */
 240         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 241
 242         if ( e->e_private != NULL ) {
 243                 Debug( LDAP_DEBUG_ANY,
 244                         "====> cache_add_entry: entry %20s id %lu already cached.\n",
 245                     e->e_dn, e->e_id, 0 );
 246                 return( -1 );
 247         }
 248
 249         if( cache_entry_private_init(e) != 0 ) {
 250                 Debug( LDAP_DEBUG_ANY,
 251                         "====> cache_add_entry: entry %20s id %lu: private init failed!\n",
 252                     e->e_dn, e->e_id, 0 );
 253                 return( -1 );
 254         }
 255
 256         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 257                 cache_entrydn_cmp, avl_dup_error ) != 0 )
 258         {
 259                 Debug( LDAP_DEBUG_TRACE,
 260                         "====> cache_add_entry: entry %20s id %lu already in dn cache\n",
 261                     e->e_dn, e->e_id, 0 );
 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         /* id tree */
 271         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 272                 cache_entryid_cmp, avl_dup_error ) != 0 )
 273         {
 274                 Debug( LDAP_DEBUG_ANY,
 275                         "====> entry %20s id %lu already in id cache\n",
 276                     e->e_dn, e->e_id, 0 );
 277
 278                 /* delete from dn tree inserted above */
 279                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 280                         cache_entrydn_cmp ) == NULL )
 281                 {
 282                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 283                             0, 0, 0 );
 284                 }
 285
 286                 cache_entry_private_destroy(e);
 287
 288                 /* free cache mutex */
 289                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 290                 return( -1 );
 291         }
 292
 293         cache_entry_rdwr_lock( e, rw );
 294
 295         LEI(e)->lei_state = state;
 296         LEI(e)->lei_refcnt = 1;
 297
 298         /* lru */
 299         LRU_ADD( cache, e );
 300         if ( ++cache->c_cursize > cache->c_maxsize ) {
 301                 /*
 302                  * find the lru entry not currently in use and delete it.
 303                  * in case a lot of entries are in use, only look at the
 304                  * first 10 on the tail of the list.
 305                  */
 306                 i = 0;
 307                 while ( cache->c_lrutail != NULL &&
 308                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 309                         i < 10 )
 310                 {
 311                         /* move this in-use entry to the front of the q */
 312                         ee = cache->c_lrutail;
 313                         LRU_DELETE( cache, ee );
 314                         LRU_ADD( cache, ee );
 315                         i++;
 316                 }
 317
 318                 /*
 319                  * found at least one to delete - try to get back under
 320                  * the max cache size.
 321                  */
 322                 while ( cache->c_lrutail != NULL &&
 323                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 324                         cache->c_cursize > cache->c_maxsize )
 325                 {
 326                         e = cache->c_lrutail;
 327
 328                         /* delete from cache and lru q */
 329                         rc = cache_delete_entry_internal( cache, e );
 330
 331                         entry_free( e );
 332                 }
 333         }
 334
 335         /* free cache mutex */
 336         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 337         return( 0 );
 338 }
 339
 340 /*
 341  * cache_update_entry - update a LOCKED entry which has been deleted.
 342  * returns:     0       entry has been created and locked
 343  *              1       entry already existed
 344  *              -1      something bad happened
 345  */
 346 int
 347 cache_update_entry(
 348     struct cache        *cache,
 349     Entry               *e
 350 )
 351 {
 352         int     i, rc;
 353         Entry   *ee;
 354
 355         /* set cache mutex */
 356         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 357
 358         if ( e->e_private == NULL ) {
 359                 Debug( LDAP_DEBUG_ANY,
 360                         "====> cache_update_entry: entry %20s id %lu no private data.\n",
 361                     e->e_dn, e->e_id, 0 );
 362                 return( -1 );
 363         }
 364
 365         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 366                 cache_entrydn_cmp, avl_dup_error ) != 0 )
 367         {
 368                 Debug( LDAP_DEBUG_TRACE,
 369                         "====> cache_add_entry: entry %20s id %lu already in dn cache\n",
 370                     e->e_dn, e->e_id, 0 );
 371
 372                 /* free cache mutex */
 373                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 374                 return( 1 );
 375         }
 376
 377         /* id tree */
 378         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 379                 cache_entryid_cmp, avl_dup_error ) != 0 )
 380         {
 381                 Debug( LDAP_DEBUG_ANY,
 382                         "====> entry %20s id %lu already in id cache\n",
 383                     e->e_dn, e->e_id, 0 );
 384
 385                 /* delete from dn tree inserted above */
 386                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 387                         cache_entrydn_cmp ) == NULL )
 388                 {
 389                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 390                             0, 0, 0 );
 391                 }
 392
 393                 /* free cache mutex */
 394                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 395                 return( -1 );
 396         }
 397
 398         /* lru */
 399         LRU_ADD( cache, e );
 400         if ( ++cache->c_cursize > cache->c_maxsize ) {
 401                 /*
 402                  * find the lru entry not currently in use and delete it.
 403                  * in case a lot of entries are in use, only look at the
 404                  * first 10 on the tail of the list.
 405                  */
 406                 i = 0;
 407                 while ( cache->c_lrutail != NULL &&
 408                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 409                         i < 10 )
 410                 {
 411                         /* move this in-use entry to the front of the q */
 412                         ee = cache->c_lrutail;
 413                         LRU_DELETE( cache, ee );
 414                         LRU_ADD( cache, ee );
 415                         i++;
 416                 }
 417
 418                 /*
 419                  * found at least one to delete - try to get back under
 420                  * the max cache size.
 421                  */
 422                 while ( cache->c_lrutail != NULL &&
 423                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 424                         cache->c_cursize > cache->c_maxsize )
 425                 {
 426                         e = cache->c_lrutail;
 427
 428                         /* delete from cache and lru q */
 429                         rc = cache_delete_entry_internal( cache, e );
 430
 431                         entry_free( e );
 432                 }
 433         }
 434
 435         /* free cache mutex */
 436         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 437         return( 0 );
 438 }
 439
 440 /*
 441  * cache_find_entry_dn2id - find an entry in the cache, given dn
 442  */
 443
 444 ID
 445 cache_find_entry_dn2id(
 446         Backend         *be,
 447     struct cache        *cache,
 448     char                *dn
 449 )
 450 {
 451         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
 452         Entry           e, *ep;
 453         ID                      id;
 454
 455         /* set cache mutex */
 456         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 457
 458         e.e_dn = dn;
 459         e.e_ndn = dn_normalize_case( ch_strdup( dn ) );
 460
 461         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 462                 cache_entrydn_cmp )) != NULL )
 463         {
 464                 /*
 465                  * ep now points to an unlocked entry
 466                  * we do not need to lock the entry if we only
 467                  * check the state, refcnt, LRU, and id.
 468                  */
 469                 free(e.e_ndn);
 470
 471                 Debug(LDAP_DEBUG_TRACE, "====> cache_find_entry_dn2id: found dn: %s\n",
 472                         dn, 0, 0);
 473
 474                 /*
 475                  * entry is deleted or not fully created yet
 476                  */
 477                 if ( LEI(ep)->lei_state == ENTRY_STATE_DELETED ||
 478                         LEI(ep)->lei_state == ENTRY_STATE_CREATING )
 479                 {
 480                         /* free cache mutex */
 481                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 482                         return( NOID );
 483                 }
 484
 485                 /* lru */
 486                 LRU_DELETE( cache, ep );
 487                 LRU_ADD( cache, ep );
 488
 489                 /* save id */
 490                 id = ep->e_id;
 491
 492                 /* free cache mutex */
 493                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 494
 495                 return( id );
 496         }
 497
 498         free(e.e_ndn);
 499
 500         /* free cache mutex */
 501         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 502
 503         return( NOID );
 504 }
 505
 506 /*
 507  * cache_find_entry_id - find an entry in the cache, given id
 508  */
 509
 510 Entry *
 511 cache_find_entry_id(
 512         struct cache    *cache,
 513         ID                              id,
 514         int                             rw
 515 )
 516 {
 517         Entry   e;
 518         Entry   *ep;
 519
 520         e.e_id = id;
 521
 522 try_again:
 523         /* set cache mutex */
 524         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 525
 526         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 527                 cache_entryid_cmp )) != NULL )
 528         {
 529                 Debug(LDAP_DEBUG_TRACE,
 530                         "====> cache_find_entry_dn2id: found id: %ld rw: %d\n",
 531                         id, rw, 0);
 532
 533                 /*
 534                  * entry is deleted or not fully created yet
 535                  */
 536                 if ( LEI(ep)->lei_state == ENTRY_STATE_DELETED ||
 537                         LEI(ep)->lei_state == ENTRY_STATE_CREATING )
 538                 {
 539                         /* free cache mutex */
 540                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 541                         return( NULL );
 542                 }
 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         Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry:\n", 0, 0, 0 );
 595
 596         /* set cache mutex */
 597         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 598
 599         rc = cache_delete_entry_internal( cache, e );
 600
 601         /* free cache mutex */
 602         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 603         return( rc );
 604 }
 605
 606 static int
 607 cache_delete_entry_internal(
 608     struct cache        *cache,
 609     Entry               *e
 610 )
 611 {
 612         int rc = 0;     /* return code */
 613
 614         /* dn tree */
 615         if ( avl_delete( &cache->c_dntree, (caddr_t) e, cache_entrydn_cmp )
 616                 == NULL )
 617         {
 618                 rc = -1;
 619         }
 620
 621         /* id tree */
 622         if ( avl_delete( &cache->c_idtree, (caddr_t) e, cache_entryid_cmp )
 623                 == NULL )
 624         {
 625                 rc = -1;
 626         }
 627
 628         if (rc != 0) {
 629                 return rc;
 630         }
 631
 632         /* lru */
 633         LRU_DELETE( cache, e );
 634         cache->c_cursize--;
 635
 636         /*
 637          * flag entry to be freed later by a call to cache_return_entry()
 638          */
 639         LEI(e)->lei_state = ENTRY_STATE_DELETED;
 640
 641         return( 0 );
 642 }
 643
 644 #ifdef LDAP_DEBUG
 645
 646 static void
 647 lru_print( struct cache *cache )
 648 {
 649         Entry   *e;
 650
 651         fprintf( stderr, "LRU queue (head to tail):\n" );
 652         for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
 653                 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
 654                     e->e_id, LEI(e)->lei_refcnt );
 655         }
 656         fprintf( stderr, "LRU queue (tail to head):\n" );
 657         for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
 658                 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
 659                     e->e_id, LEI(e)->lei_refcnt );
 660         }
 661 }
 662
 663 #endif
 664