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