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