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