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