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