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 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 1998-2005 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20
  21 #include <ac/errno.h>
  22 #include <ac/string.h>
  23 #include <ac/socket.h>
  24
  25 #include "slap.h"
  26
  27 #include "back-ldbm.h"
  28
  29 /* LDBM backend specific entry info -- visible only to the cache */
  30 typedef struct ldbm_entry_info {
  31         /*
  32          * These items are specific to the LDBM backend and should
  33          * be hidden.  Backend cache lock required to access.
  34          */
  35         int             lei_state;      /* for the cache */
  36 #define CACHE_ENTRY_UNDEFINED   0
  37 #define CACHE_ENTRY_CREATING    1
  38 #define CACHE_ENTRY_READY       2
  39 #define CACHE_ENTRY_DELETED     3
  40 #define CACHE_ENTRY_COMMITTED   4
  41
  42         int             lei_refcnt;     /* # threads ref'ing this entry */
  43         Entry   *lei_lrunext;   /* for cache lru list */
  44         Entry   *lei_lruprev;
  45 } EntryInfo;
  46 #undef LEI
  47 #define LEI(e)  ((EntryInfo *) ((e)->e_private))
  48
  49 static int      cache_delete_entry_internal(Cache *cache, Entry *e);
  50 #ifdef LDAP_DEBUG
  51 static void     lru_print(Cache *cache);
  52 #endif
  53
  54 static int
  55 cache_entry_private_init( Entry*e )
  56 {
  57         assert( e->e_private == NULL );
  58
  59         if( e->e_private != NULL ) {
  60                 /* this should never happen */
  61                 return 1;
  62         }
  63
  64         e->e_private = ch_calloc(1, sizeof(struct ldbm_entry_info));
  65
  66         return 0;
  67 }
  68
  69 /*
  70  * marks an entry in CREATING state as committed, so it is really returned
  71  * to the cache. Otherwise an entry in CREATING state is removed.
  72  * Makes e_private be destroyed at the following cache_return_entry_w,
  73  * but lets the entry untouched (owned by someone else)
  74  */
  75 void
  76 cache_entry_commit( Entry *e )
  77 {
  78         assert( e );
  79         assert( e->e_private );
  80         assert( LEI(e)->lei_state == CACHE_ENTRY_CREATING );
  81         /* assert( LEI(e)->lei_refcnt == 1 ); */
  82
  83         LEI(e)->lei_state = CACHE_ENTRY_COMMITTED;
  84 }
  85
  86 static int
  87 cache_entry_private_destroy( Entry*e )
  88 {
  89         assert( e->e_private );
  90
  91         free( e->e_private );
  92         e->e_private = NULL;
  93         return 0;
  94 }
  95
  96 void
  97 cache_return_entry_rw( Cache *cache, Entry *e, int rw )
  98 {
  99         ID id;
 100         int refcnt, freeit = 1;
 101
 102         if ( slapMode != SLAP_SERVER_MODE ) {
 103                 return;
 104         }
 105
 106         /* set cache mutex */
 107         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 108
 109         assert( e->e_private );
 110
 111         id = e->e_id;
 112         refcnt = --LEI(e)->lei_refcnt;
 113
 114         /*
 115          * if the entry is returned when in CREATING state, it is deleted
 116          * but not freed because it may belong to someone else (do_add,
 117          * for instance)
 118          */
 119         if (  LEI(e)->lei_state == CACHE_ENTRY_CREATING ) {
 120                 cache_delete_entry_internal( cache, e );
 121                 freeit = 0;
 122                 /* now the entry is in DELETED state */
 123         }
 124
 125         if ( LEI(e)->lei_state == CACHE_ENTRY_COMMITTED ) {
 126                 LEI(e)->lei_state = CACHE_ENTRY_READY;
 127
 128                 /* free cache mutex */
 129                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 130
 131                 Debug( LDAP_DEBUG_TRACE,
 132                         "====> cache_return_entry_%s( %ld ): created (%d)\n",
 133                         rw ? "w" : "r", id, refcnt );
 134
 135         } else if ( LEI(e)->lei_state == CACHE_ENTRY_DELETED ) {
 136                 if( refcnt > 0 ) {
 137                         /* free cache mutex */
 138                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 139
 140                         Debug( LDAP_DEBUG_TRACE,
 141                                 "====> cache_return_entry_%s( %ld ): delete pending (%d)\n",
 142                                 rw ? "w" : "r", id, refcnt );
 143
 144                 } else {
 145                         cache_entry_private_destroy( e );
 146                         if ( freeit ) {
 147                                 entry_free( e );
 148                         }
 149
 150                         /* free cache mutex */
 151                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 152
 153                         Debug( LDAP_DEBUG_TRACE,
 154                                 "====> cache_return_entry_%s( %ld ): deleted (%d)\n",
 155                                 rw ? "w" : "r", id, refcnt );
 156                 }
 157
 158         } else {
 159                 /* free cache mutex */
 160                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 161
 162                 Debug( LDAP_DEBUG_TRACE,
 163                         "====> cache_return_entry_%s( %ld ): returned (%d)\n",
 164                         rw ? "w" : "r", id, refcnt);
 165         }
 166 }
 167
 168 #define LRU_DELETE( cache, e ) do { \
 169         if ( LEI(e)->lei_lruprev != NULL ) { \
 170                 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
 171         } else { \
 172                 (cache)->c_lruhead = LEI(e)->lei_lrunext; \
 173         } \
 174         if ( LEI(e)->lei_lrunext != NULL ) { \
 175                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
 176         } else { \
 177                 (cache)->c_lrutail = LEI(e)->lei_lruprev; \
 178         } \
 179 } while(0)
 180
 181 #define LRU_ADD( cache, e ) do { \
 182         LEI(e)->lei_lrunext = (cache)->c_lruhead; \
 183         if ( LEI(e)->lei_lrunext != NULL ) { \
 184                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = (e); \
 185         } \
 186         (cache)->c_lruhead = (e); \
 187         LEI(e)->lei_lruprev = NULL; \
 188         if ( (cache)->c_lrutail == NULL ) { \
 189                 (cache)->c_lrutail = (e); \
 190         } \
 191 } while(0)
 192
 193 /*
 194  * cache_add_entry_rw - create and lock an entry in the cache
 195  * returns:     0       entry has been created and locked
 196  *              1       entry already existed
 197  *              -1      something bad happened
 198  */
 199 int
 200 cache_add_entry_rw(
 201     Cache       *cache,
 202     Entry               *e,
 203         int             rw
 204 )
 205 {
 206         int     i, rc;
 207         Entry   *ee;
 208
 209         /* set cache mutex */
 210         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 211
 212         assert( e->e_private == NULL );
 213
 214         if( cache_entry_private_init(e) != 0 ) {
 215                 /* free cache mutex */
 216                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 217
 218                 Debug( LDAP_DEBUG_ANY,
 219                         "====> cache_add_entry( %ld ): \"%s\": private init failed!\n",
 220                     e->e_id, e->e_dn, 0 );
 221
 222                 return( -1 );
 223         }
 224
 225         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 226                          entry_dn_cmp, avl_dup_error ) != 0 )
 227         {
 228                 /* free cache mutex */
 229                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 230
 231                 Debug( LDAP_DEBUG_TRACE,
 232                         "====> cache_add_entry( %ld ): \"%s\": already in dn cache\n",
 233                     e->e_id, e->e_dn, 0 );
 234
 235                 cache_entry_private_destroy(e);
 236
 237                 return( 1 );
 238         }
 239
 240         /* id tree */
 241         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 242                          entry_id_cmp, avl_dup_error ) != 0 )
 243         {
 244                 Debug( LDAP_DEBUG_ANY,
 245                         "====> cache_add_entry( %ld ): \"%s\": already in id cache\n",
 246                     e->e_id, e->e_dn, 0 );
 247
 248                 /* delete from dn tree inserted above */
 249                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 250                                  entry_dn_cmp ) == NULL )
 251                 {
 252                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 253                             0, 0, 0 );
 254                 }
 255
 256                 cache_entry_private_destroy(e);
 257
 258                 /* free cache mutex */
 259                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 260                 return( -1 );
 261         }
 262
 263         /* put the entry into 'CREATING' state */
 264         /* will be marked after when entry is returned */
 265         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
 266         LEI(e)->lei_refcnt = 1;
 267
 268         /* lru */
 269         LRU_ADD( cache, e );
 270         if ( ++cache->c_cursize > cache->c_maxsize ) {
 271                 /*
 272                  * find the lru entry not currently in use and delete it.
 273                  * in case a lot of entries are in use, only look at the
 274                  * first 10 on the tail of the list.
 275                  */
 276                 i = 0;
 277                 while ( cache->c_lrutail != NULL &&
 278                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 279                         i < 10 )
 280                 {
 281                         /* move this in-use entry to the front of the q */
 282                         ee = cache->c_lrutail;
 283                         LRU_DELETE( cache, ee );
 284                         LRU_ADD( cache, ee );
 285                         i++;
 286                 }
 287
 288                 /*
 289                  * found at least one to delete - try to get back under
 290                  * the max cache size.
 291                  */
 292                 while ( cache->c_lrutail != NULL &&
 293                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 294                         cache->c_cursize > cache->c_maxsize )
 295                 {
 296                         e = cache->c_lrutail;
 297
 298                         /* delete from cache and lru q */
 299                         /* XXX do we need rc ? */
 300                         rc = cache_delete_entry_internal( cache, e );
 301                         cache_entry_private_destroy( e );
 302                         entry_free( e );
 303                 }
 304         }
 305
 306         /* free cache mutex */
 307         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 308         return( 0 );
 309 }
 310
 311 /*
 312  * cache_update_entry - update a LOCKED entry which has been deleted.
 313  * returns:     0       entry has been created and locked
 314  *              1       entry already existed
 315  *              -1      something bad happened
 316  */
 317 int
 318 cache_update_entry(
 319     Cache       *cache,
 320     Entry               *e
 321 )
 322 {
 323         int     i, rc;
 324         Entry   *ee;
 325
 326         /* set cache mutex */
 327         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 328
 329         assert( e->e_private );
 330
 331         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 332                          entry_dn_cmp, avl_dup_error ) != 0 )
 333         {
 334                 Debug( LDAP_DEBUG_TRACE,
 335                         "====> cache_update_entry( %ld ): \"%s\": already in dn cache\n",
 336                     e->e_id, e->e_dn, 0 );
 337
 338                 /* free cache mutex */
 339                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 340                 return( 1 );
 341         }
 342
 343         /* id tree */
 344         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 345                          entry_id_cmp, avl_dup_error ) != 0 )
 346         {
 347                 Debug( LDAP_DEBUG_ANY,
 348                         "====> cache_update_entry( %ld ): \"%s\": already in id cache\n",
 349                     e->e_id, e->e_dn, 0 );
 350
 351                 /* delete from dn tree inserted above */
 352                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 353                                  entry_dn_cmp ) == NULL )
 354                 {
 355                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 356                             0, 0, 0 );
 357                 }
 358
 359                 /* free cache mutex */
 360                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 361                 return( -1 );
 362         }
 363
 364         /* put the entry into 'CREATING' state */
 365         /* will be marked after when entry is returned */
 366         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
 367
 368         /* lru */
 369         LRU_ADD( cache, e );
 370         if ( ++cache->c_cursize > cache->c_maxsize ) {
 371                 /*
 372                  * find the lru entry not currently in use and delete it.
 373                  * in case a lot of entries are in use, only look at the
 374                  * first 10 on the tail of the list.
 375                  */
 376                 i = 0;
 377                 while ( cache->c_lrutail != NULL &&
 378                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
 379                         i < 10 )
 380                 {
 381                         /* move this in-use entry to the front of the q */
 382                         ee = cache->c_lrutail;
 383                         LRU_DELETE( cache, ee );
 384                         LRU_ADD( cache, ee );
 385                         i++;
 386                 }
 387
 388                 /*
 389                  * found at least one to delete - try to get back under
 390                  * the max cache size.
 391                  */
 392                 while ( cache->c_lrutail != NULL &&
 393                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
 394                         cache->c_cursize > cache->c_maxsize )
 395                 {
 396                         e = cache->c_lrutail;
 397
 398                         /* delete from cache and lru q */
 399                         /* XXX do we need rc ? */
 400                         rc = cache_delete_entry_internal( cache, e );
 401                         cache_entry_private_destroy( e );
 402                         entry_free( e );
 403                 }
 404         }
 405
 406         /* free cache mutex */
 407         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 408         return( 0 );
 409 }
 410
 411 ID
 412 cache_find_entry_ndn2id(
 413         Backend         *be,
 414     Cache       *cache,
 415     struct berval       *ndn
 416 )
 417 {
 418         Entry           e, *ep;
 419         ID                      id;
 420         int count = 0;
 421
 422         /* this function is always called with normalized DN */
 423         e.e_nname = *ndn;
 424
 425 try_again:
 426         /* set cache mutex */
 427         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 428
 429         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 430                                        entry_dn_cmp )) != NULL )
 431         {
 432                 int state;
 433                 count++;
 434
 435                 /*
 436                  * ep now points to an unlocked entry
 437                  * we do not need to lock the entry if we only
 438                  * check the state, refcnt, LRU, and id.
 439                  */
 440                 assert( ep->e_private );
 441
 442                 /* save id */
 443                 id = ep->e_id;
 444                 state = LEI(ep)->lei_state;
 445
 446                 /*
 447                  * entry is deleted or not fully created yet
 448                  */
 449                 if ( state != CACHE_ENTRY_READY ) {
 450                         assert(state != CACHE_ENTRY_UNDEFINED);
 451
 452                         /* free cache mutex */
 453                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 454
 455                         Debug(LDAP_DEBUG_TRACE,
 456                                 "====> cache_find_entry_ndn2id(\"%s\"): %ld (not ready) %d\n",
 457                                 ndn->bv_val, id, state);
 458
 459                         ldap_pvt_thread_yield();
 460                         goto try_again;
 461                 }
 462
 463                 /* lru */
 464                 LRU_DELETE( cache, ep );
 465                 LRU_ADD( cache, ep );
 466
 467                 /* free cache mutex */
 468                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 469
 470                 Debug(LDAP_DEBUG_TRACE,
 471                         "====> cache_find_entry_ndn2id(\"%s\"): %ld (%d tries)\n",
 472                         ndn->bv_val, id, count);
 473
 474         } else {
 475                 /* free cache mutex */
 476                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 477                 id = NOID;
 478         }
 479
 480         return( id );
 481 }
 482
 483 /*
 484  * cache_find_entry_id - find an entry in the cache, given id
 485  */
 486
 487 Entry *
 488 cache_find_entry_id(
 489         Cache   *cache,
 490         ID                              id,
 491         int                             rw
 492 )
 493 {
 494         Entry   e;
 495         Entry   *ep;
 496         int     count = 0;
 497
 498         e.e_id = id;
 499
 500 try_again:
 501         /* set cache mutex */
 502         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 503
 504         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 505                                        entry_id_cmp )) != NULL )
 506         {
 507                 int state;
 508                 ID      ep_id;
 509
 510                 count++;
 511
 512                 assert( ep->e_private );
 513
 514                 ep_id = ep->e_id;
 515                 state = LEI(ep)->lei_state;
 516
 517                 /*
 518                  * entry is deleted or not fully created yet
 519                  */
 520                 if ( state != CACHE_ENTRY_READY ) {
 521                         assert(state != CACHE_ENTRY_UNDEFINED);
 522
 523                         /* free cache mutex */
 524                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 525
 526                         Debug(LDAP_DEBUG_TRACE,
 527                                 "====> cache_find_entry_id( %ld ): %ld (not ready) %d\n",
 528                                 id, ep_id, state);
 529
 530                         ldap_pvt_thread_yield();
 531                         goto try_again;
 532                 }
 533
 534                 /* lru */
 535                 LRU_DELETE( cache, ep );
 536                 LRU_ADD( cache, ep );
 537
 538                 LEI(ep)->lei_refcnt++;
 539
 540                 /* free cache mutex */
 541                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 542
 543                 Debug(LDAP_DEBUG_TRACE,
 544                         "====> cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
 545                         ep_id, ep->e_dn, count);
 546
 547                 return( ep );
 548         }
 549
 550         /* free cache mutex */
 551         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 552
 553         return( NULL );
 554 }
 555
 556 /*
 557  * cache_delete_entry - delete the entry e from the cache.  the caller
 558  * should have obtained e (increasing its ref count) via a call to one
 559  * of the cache_find_* routines.  the caller should *not* call the
 560  * cache_return_entry() routine prior to calling cache_delete_entry().
 561  * it performs this function.
 562  *
 563  * returns:     0       e was deleted ok
 564  *              1       e was not in the cache
 565  *              -1      something bad happened
 566  */
 567 int
 568 cache_delete_entry(
 569     Cache       *cache,
 570     Entry               *e
 571 )
 572 {
 573         int     rc;
 574
 575         /* set cache mutex */
 576         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 577
 578         assert( e->e_private );
 579
 580         Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry( %ld )\n",
 581                 e->e_id, 0, 0 );
 582
 583         rc = cache_delete_entry_internal( cache, e );
 584
 585         /* free cache mutex */
 586         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 587         return( rc );
 588 }
 589
 590 static int
 591 cache_delete_entry_internal(
 592     Cache       *cache,
 593     Entry               *e
 594 )
 595 {
 596         int rc = 0;     /* return code */
 597
 598         /* dn tree */
 599         if ( avl_delete( &cache->c_dntree, (caddr_t) e, entry_dn_cmp ) == NULL )
 600         {
 601                 rc = -1;
 602         }
 603
 604         /* id tree */
 605         if ( avl_delete( &cache->c_idtree, (caddr_t) e, entry_id_cmp ) == NULL )
 606         {
 607                 rc = -1;
 608         }
 609
 610         if (rc != 0) {
 611                 return rc;
 612         }
 613
 614         /* lru */
 615         LRU_DELETE( cache, e );
 616         cache->c_cursize--;
 617
 618         /*
 619          * flag entry to be freed later by a call to cache_return_entry()
 620          */
 621         LEI(e)->lei_state = CACHE_ENTRY_DELETED;
 622
 623         return( 0 );
 624 }
 625
 626 void
 627 cache_release_all( Cache *cache )
 628 {
 629         Entry *e;
 630         int rc;
 631
 632         /* set cache mutex */
 633         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
 634
 635         Debug( LDAP_DEBUG_TRACE, "====> cache_release_all\n", 0, 0, 0 );
 636
 637
 638         while ( (e = cache->c_lrutail) != NULL && LEI(e)->lei_refcnt == 0 ) {
 639                 /* delete from cache and lru q */
 640                 /* XXX do we need rc ? */
 641                 rc = cache_delete_entry_internal( cache, e );
 642                 cache_entry_private_destroy( e );
 643                 entry_free( e );
 644         }
 645
 646         if ( cache->c_cursize ) {
 647                 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
 648         }
 649
 650         /* free cache mutex */
 651         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
 652 }
 653
 654 #ifdef LDAP_DEBUG
 655 static void
 656 lru_print( Cache *cache )
 657 {
 658         Entry   *e;
 659
 660         fprintf( stderr, "LRU queue (head to tail):\n" );
 661         for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
 662                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 663                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 664         }
 665         fprintf( stderr, "LRU queue (tail to head):\n" );
 666         for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
 667                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
 668                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
 669         }
 670 }
 671 #endif