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