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