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