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
   3 #include "portable.h"
   4
   5 #include <stdio.h>
   6
   7 #include <ac/string.h>
   8 #include <ac/socket.h>
   9
  10 #include "slap.h"
  11
  12 #include "back-ldbm.h"
  13
  14 static int      cache_delete_entry_internal(struct cache *cache, Entry *e);
  15 #ifdef LDAP_DEBUG
  16 static void     lru_print(struct cache *cache);
  17 #endif
  18
  19 /*
  20  * the cache has three entry points (ways to find things):
  21  *
  22  *      by entry        e.g., if you already have an entry from the cache
  23  *                      and want to delete it. (really by entry ptr)
  24  *      by dn           e.g., when looking for the base object of a search
  25  *      by id           e.g., for search candidates
  26  *
  27  * these correspond to three different avl trees that are maintained.
  28  */
  29
  30 static int
  31 cache_entry_cmp( Entry *e1, Entry *e2 )
  32 {
  33         return( e1 < e2 ? -1 : (e1 > e2 ? 1 : 0) );
  34 }
  35
  36 static int
  37 cache_entrydn_cmp( Entry *e1, Entry *e2 )
  38 {
  39         /* compare their normalized UPPERCASED dn's */
  40         return( strcmp( e1->e_ndn, e2->e_ndn ) );
  41 }
  42
  43 static int
  44 cache_entryid_cmp( Entry *e1, Entry *e2 )
  45 {
  46         return( e1->e_id < e2->e_id ? -1 : (e1->e_id > e2->e_id ? 1 : 0) );
  47 }
  48
  49 void
  50 cache_set_state( struct cache *cache, Entry *e, int state )
  51 {
  52         /* set cache mutex */
  53         pthread_mutex_lock( &cache->c_mutex );
  54
  55         e->e_state = state;
  56
  57         /* free cache mutex */
  58         pthread_mutex_unlock( &cache->c_mutex );
  59 }
  60
  61 static void
  62 cache_return_entry( struct cache *cache, Entry *e )
  63 {
  64         /* set cache mutex */
  65         pthread_mutex_lock( &cache->c_mutex );
  66
  67         if ( --e->e_refcnt == 0 && e->e_state == ENTRY_STATE_DELETED ) {
  68                 entry_free( e );
  69         }
  70
  71         /* free cache mutex */
  72         pthread_mutex_unlock( &cache->c_mutex );
  73 }
  74
  75 static void
  76 cache_return_entry_rw( struct cache *cache, Entry *e, int rw )
  77 {
  78         Debug( LDAP_DEBUG_TRACE, "====> cache_return_entry_%s\n",
  79                 rw ? "w" : "r", 0, 0);
  80         entry_rdwr_unlock(e, rw);;
  81         cache_return_entry(cache, e);
  82 }
  83
  84 void
  85 cache_return_entry_r( struct cache *cache, Entry *e )
  86 {
  87         cache_return_entry_rw(cache, e, 0);
  88 }
  89
  90 void
  91 cache_return_entry_w( struct cache *cache, Entry *e )
  92 {
  93         cache_return_entry_rw(cache, e, 1);
  94 }
  95
  96
  97 #define LRU_DELETE( cache, e ) { \
  98         if ( e->e_lruprev != NULL ) { \
  99                 e->e_lruprev->e_lrunext = e->e_lrunext; \
 100         } else { \
 101                 cache->c_lruhead = e->e_lrunext; \
 102         } \
 103         if ( e->e_lrunext != NULL ) { \
 104                 e->e_lrunext->e_lruprev = e->e_lruprev; \
 105         } else { \
 106                 cache->c_lrutail = e->e_lruprev; \
 107         } \
 108 }
 109
 110 #define LRU_ADD( cache, e ) { \
 111         e->e_lrunext = cache->c_lruhead; \
 112         if ( e->e_lrunext != NULL ) { \
 113                 e->e_lrunext->e_lruprev = e; \
 114         } \
 115         cache->c_lruhead = e; \
 116         e->e_lruprev = NULL; \
 117         if ( cache->c_lrutail == NULL ) { \
 118                 cache->c_lrutail = e; \
 119         } \
 120 }
 121
 122 /*
 123  * cache_create_entry_lock - create an entry in the cache, and lock it.
 124  * returns:     0       entry has been created and locked
 125  *              1       entry already existed
 126  *              -1      something bad happened
 127  */
 128 int
 129 cache_add_entry_lock(
 130     struct cache        *cache,
 131     Entry               *e,
 132     int                 state
 133 )
 134 {
 135         int     i, rc;
 136         Entry   *ee;
 137
 138         /* set cache mutex */
 139         pthread_mutex_lock( &cache->c_mutex );
 140
 141         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
 142                 cache_entrydn_cmp, avl_dup_error ) != 0 )
 143         {
 144                 Debug( LDAP_DEBUG_TRACE,
 145                         "====> cache_add_entry lock: entry %20s id %lu already in dn cache\n",
 146                     e->e_dn, e->e_id, 0 );
 147
 148                 /* free cache mutex */
 149                 pthread_mutex_unlock( &cache->c_mutex );
 150                 return( 1 );
 151         }
 152
 153         /* id tree */
 154         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
 155                 cache_entryid_cmp, avl_dup_error ) != 0 )
 156         {
 157                 Debug( LDAP_DEBUG_ANY,
 158                         "====> entry %20s id %lu already in id cache\n",
 159                     e->e_dn, e->e_id, 0 );
 160
 161                 /* delete from dn tree inserted above */
 162                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
 163                         cache_entrydn_cmp ) == NULL )
 164                 {
 165                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
 166                             0, 0, 0 );
 167                 }
 168
 169                 /* free cache mutex */
 170                 pthread_mutex_unlock( &cache->c_mutex );
 171                 return( -1 );
 172         }
 173
 174         e->e_state = state;
 175         e->e_refcnt = 1;
 176
 177         /* lru */
 178         LRU_ADD( cache, e );
 179         if ( ++cache->c_cursize > cache->c_maxsize ) {
 180                 /*
 181                  * find the lru entry not currently in use and delete it.
 182                  * in case a lot of entries are in use, only look at the
 183                  * first 10 on the tail of the list.
 184                  */
 185                 i = 0;
 186                 while ( cache->c_lrutail != NULL && cache->c_lrutail->e_refcnt
 187                     != 0 && i < 10 ) {
 188                         /* move this in-use entry to the front of the q */
 189                         ee = cache->c_lrutail;
 190                         LRU_DELETE( cache, ee );
 191                         LRU_ADD( cache, ee );
 192                         i++;
 193                 }
 194
 195                 /*
 196                  * found at least one to delete - try to get back under
 197                  * the max cache size.
 198                  */
 199                 while ( cache->c_lrutail != NULL && cache->c_lrutail->e_refcnt
 200                     == 0 && cache->c_cursize > cache->c_maxsize ) {
 201                         e = cache->c_lrutail;
 202
 203                         /* XXX check for writer lock - should also check no readers pending */
 204 #ifdef LDAP_DEBUG
 205                         assert(!pthread_rdwr_rwchk_np(&e->e_rdwr));
 206 #endif
 207
 208                         /* delete from cache and lru q */
 209                         rc = cache_delete_entry_internal( cache, e );
 210
 211                         entry_free( e );
 212                 }
 213         }
 214
 215         /* free cache mutex */
 216         pthread_mutex_unlock( &cache->c_mutex );
 217         return( 0 );
 218 }
 219
 220 /*
 221  * cache_find_entry_dn2id - find an entry in the cache, given dn
 222  */
 223
 224 ID
 225 cache_find_entry_dn2id(
 226         Backend         *be,
 227     struct cache        *cache,
 228     char                *dn
 229 )
 230 {
 231         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
 232         Entry           e, *ep;
 233         ID                      id;
 234
 235         /* set cache mutex */
 236         pthread_mutex_lock( &cache->c_mutex );
 237
 238         e.e_dn = dn;
 239         e.e_ndn = dn_normalize_case( ch_strdup( dn ) );
 240
 241         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
 242                 cache_entrydn_cmp )) != NULL )
 243         {
 244                 free(e.e_ndn);
 245
 246                 Debug(LDAP_DEBUG_TRACE, "====> cache_find_entry_dn2id: found dn: %s\n",
 247                         dn, 0, 0);
 248
 249                 /*
 250                  * entry is deleted or not fully created yet
 251                  */
 252                 if ( ep->e_state == ENTRY_STATE_DELETED ||
 253                         ep->e_state == ENTRY_STATE_CREATING )
 254                 {
 255                         /* free cache mutex */
 256                         pthread_mutex_unlock( &cache->c_mutex );
 257                         return( NOID );
 258                 }
 259
 260                 /* XXX is this safe without writer lock? */
 261                 ep->e_refcnt++;
 262
 263                 /* lru */
 264                 LRU_DELETE( cache, ep );
 265                 LRU_ADD( cache, ep );
 266
 267                 /* acquire reader lock */
 268                 entry_rdwr_lock(ep, 0);
 269
 270                 /* re-check */
 271                 if ( ep->e_state == ENTRY_STATE_DELETED ||
 272                         ep->e_state == ENTRY_STATE_CREATING )
 273                 {
 274                         /* XXX check that is is required */
 275                         ep->e_refcnt--;
 276
 277                         /* free reader lock */
 278                         entry_rdwr_unlock(ep, 0);
 279                         /* free cache mutex */
 280                         pthread_mutex_unlock( &cache->c_mutex );
 281
 282                         return( NOID );
 283                 }
 284
 285                 /* save id */
 286                 id = ep->e_id;
 287
 288                 /* free reader lock */
 289                 entry_rdwr_unlock(ep, 0);
 290
 291                 /* free cache mutex */
 292                 pthread_mutex_unlock( &cache->c_mutex );
 293
 294                 cache_return_entry( &li->li_cache, ep );
 295
 296                 return( id );
 297         }
 298
 299         free(e.e_ndn);
 300
 301         /* free cache mutex */
 302         pthread_mutex_unlock( &cache->c_mutex );
 303
 304         return( NOID );
 305 }
 306
 307 /*
 308  * cache_find_entry_id - find an entry in the cache, given id
 309  */
 310
 311 Entry *
 312 cache_find_entry_id(
 313         struct cache    *cache,
 314         ID                              id,
 315         int                             rw
 316 )
 317 {
 318         Entry   e;
 319         Entry   *ep;
 320
 321         /* set cache mutex */
 322         pthread_mutex_lock( &cache->c_mutex );
 323
 324         e.e_id = id;
 325
 326         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
 327                 cache_entryid_cmp )) != NULL )
 328         {
 329                 Debug(LDAP_DEBUG_TRACE,
 330                         "====> cache_find_entry_dn2id: found id: %ld rw: %d\n",
 331                         id, rw, 0);
 332
 333                 /*
 334                  * entry is deleted or not fully created yet
 335                  */
 336                 if ( ep->e_state == ENTRY_STATE_DELETED ||
 337                         ep->e_state == ENTRY_STATE_CREATING )
 338                 {
 339                         /* free cache mutex */
 340                         pthread_mutex_unlock( &cache->c_mutex );
 341                         return( NULL );
 342                 }
 343                 /* XXX is this safe without writer lock? */
 344                 ep->e_refcnt++;
 345
 346                 /* lru */
 347                 LRU_DELETE( cache, ep );
 348                 LRU_ADD( cache, ep );
 349
 350                 /* acquire reader lock */
 351                 entry_rdwr_lock(ep, 0);
 352
 353                 /* re-check */
 354                 if ( ep->e_state == ENTRY_STATE_DELETED ||
 355                         ep->e_state == ENTRY_STATE_CREATING ) {
 356
 357                         /* XXX check that is is required */
 358                         ep->e_refcnt--;
 359
 360                         /* free reader lock */
 361                         entry_rdwr_unlock(ep, 0);
 362
 363                         /* free cache mutex */
 364                         pthread_mutex_unlock( &cache->c_mutex );
 365                         return( NULL );
 366                 }
 367
 368                 if ( rw ) {
 369                         entry_rdwr_unlock(ep, 0);
 370                         entry_rdwr_lock(ep, 1);
 371                 }
 372
 373                 /* free cache mutex */
 374                 pthread_mutex_unlock( &cache->c_mutex );
 375
 376                 return( ep );
 377         }
 378
 379         /* free cache mutex */
 380         pthread_mutex_unlock( &cache->c_mutex );
 381
 382         return( NULL );
 383 }
 384
 385 /*
 386  * cache_delete_entry - delete the entry e from the cache.  the caller
 387  * should have obtained e (increasing its ref count) via a call to one
 388  * of the cache_find_* routines.  the caller should *not* call the
 389  * cache_return_entry() routine prior to calling cache_delete_entry().
 390  * it performs this function.
 391  *
 392  * returns:     0       e was deleted ok
 393  *              1       e was not in the cache
 394  *              -1      something bad happened
 395  */
 396 int
 397 cache_delete_entry(
 398     struct cache        *cache,
 399     Entry               *e
 400 )
 401 {
 402         int     rc;
 403
 404         Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry:\n", 0, 0, 0 );
 405
 406         /* XXX check for writer lock - should also check no readers pending */
 407 #ifdef LDAP_DEBUG
 408         assert(pthread_rdwr_wchk_np(&e->e_rdwr));
 409 #endif
 410
 411         /* set cache mutex */
 412         pthread_mutex_lock( &cache->c_mutex );
 413
 414         rc = cache_delete_entry_internal( cache, e );
 415
 416         /* free cache mutex */
 417         pthread_mutex_unlock( &cache->c_mutex );
 418         return( rc );
 419 }
 420
 421 static int
 422 cache_delete_entry_internal(
 423     struct cache        *cache,
 424     Entry               *e
 425 )
 426 {
 427         int rc = 0;     /* return code */
 428
 429         /* dn tree */
 430         if ( avl_delete( &cache->c_dntree, (caddr_t) e, cache_entrydn_cmp )
 431                 == NULL )
 432         {
 433                 rc = -1;
 434         }
 435
 436         /* id tree */
 437         if ( avl_delete( &cache->c_idtree, (caddr_t) e, cache_entryid_cmp )
 438                 == NULL )
 439         {
 440                 rc = -1;
 441         }
 442
 443         if (rc != 0) {
 444                 return rc;
 445         }
 446
 447         /* lru */
 448         LRU_DELETE( cache, e );
 449         cache->c_cursize--;
 450
 451         /*
 452          * flag entry to be freed later by a call to cache_return_entry()
 453          */
 454         e->e_state = ENTRY_STATE_DELETED;
 455
 456         return( 0 );
 457 }
 458
 459 #ifdef LDAP_DEBUG
 460
 461 static void
 462 lru_print( struct cache *cache )
 463 {
 464         Entry   *e;
 465
 466         fprintf( stderr, "LRU queue (head to tail):\n" );
 467         for ( e = cache->c_lruhead; e != NULL; e = e->e_lrunext ) {
 468                 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
 469                     e->e_id, e->e_refcnt );
 470         }
 471         fprintf( stderr, "LRU queue (tail to head):\n" );
 472         for ( e = cache->c_lrutail; e != NULL; e = e->e_lruprev ) {
 473                 fprintf( stderr, "\tdn %20s id %lu refcnt %d\n", e->e_dn,
 474                     e->e_id, e->e_refcnt );
 475         }
 476 }
 477
 478 #endif
 479