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