]> git.sur5r.net Git - openldap/blob - servers/slapd/back-ldbm/cache.c
New dn2id format with base/one/subtree indices (ldbm/bdb2)
[openldap] / servers / slapd / back-ldbm / cache.c
1 /* cache.c - routines to maintain an in-core cache of entries */
2 /*
3  * Copyright 1998-1999 The OpenLDAP Foundation, All Rights Reserved.
4  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
5  */
6
7 #include "portable.h"
8
9 #include <stdio.h>
10
11 #include <ac/errno.h>
12 #include <ac/string.h>
13 #include <ac/socket.h>
14
15 #include "slap.h"
16
17 #include "back-ldbm.h"
18
19 /* LDBM backend specific entry info -- visible only to the cache */
20 typedef struct ldbm_entry_info {
21         ldap_pvt_thread_rdwr_t  lei_rdwr;       /* reader/writer lock */
22
23         /*
24          * remaining fields require backend cache lock to access
25          * These items are specific to the LDBM backend and should
26          * be hidden.
27          */
28         int             lei_state;      /* for the cache */
29 #define CACHE_ENTRY_UNDEFINED   0
30 #define CACHE_ENTRY_CREATING    1
31 #define CACHE_ENTRY_READY               2
32 #define CACHE_ENTRY_DELETED             3
33
34         int             lei_refcnt;     /* # threads ref'ing this entry */
35         Entry   *lei_lrunext;   /* for cache lru list */
36         Entry   *lei_lruprev;
37 } EntryInfo;
38 #define LEI(e)  ((EntryInfo *) ((e)->e_private))
39
40 static int      cache_delete_entry_internal(Cache *cache, Entry *e);
41 #ifdef LDAP_DEBUG
42 static void     lru_print(Cache *cache);
43 #endif
44
45 static int
46 cache_entry_rdwr_lock(Entry *e, int rw)
47 {
48         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%slock: ID: %ld\n",
49                 rw ? "w" : "r", e->e_id, 0);
50
51         if (rw)
52                 return ldap_pvt_thread_rdwr_wlock(&LEI(e)->lei_rdwr);
53         else
54                 return ldap_pvt_thread_rdwr_rlock(&LEI(e)->lei_rdwr);
55 }
56
57 static int
58 cache_entry_rdwr_trylock(Entry *e, int rw)
59 {
60         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%strylock: ID: %ld\n",
61                 rw ? "w" : "r", e->e_id, 0);
62
63         if (rw)
64                 return ldap_pvt_thread_rdwr_wtrylock(&LEI(e)->lei_rdwr);
65         else
66                 return ldap_pvt_thread_rdwr_rtrylock(&LEI(e)->lei_rdwr);
67 }
68
69 static int
70 cache_entry_rdwr_unlock(Entry *e, int rw)
71 {
72         Debug( LDAP_DEBUG_ARGS, "entry_rdwr_%sunlock: ID: %ld\n",
73                 rw ? "w" : "r", e->e_id, 0);
74
75         if (rw)
76                 return ldap_pvt_thread_rdwr_wunlock(&LEI(e)->lei_rdwr);
77         else
78                 return ldap_pvt_thread_rdwr_runlock(&LEI(e)->lei_rdwr);
79 }
80
81 static int
82 cache_entry_rdwr_init(Entry *e)
83 {
84         return ldap_pvt_thread_rdwr_init( &LEI(e)->lei_rdwr );
85 }
86
87 static int
88 cache_entry_rdwr_destroy(Entry *e)
89 {
90         return ldap_pvt_thread_rdwr_destroy( &LEI(e)->lei_rdwr );
91 }
92
93 static int
94 cache_entry_private_init( Entry*e )
95 {
96         assert( e->e_private == NULL );
97
98         if( e->e_private != NULL ) {
99                 /* this should never happen */
100                 return 1;
101         }
102
103         e->e_private = ch_calloc(1, sizeof(struct ldbm_entry_info));
104
105         if( cache_entry_rdwr_init( e ) != 0 ) {
106                 free( LEI(e) );
107                 e->e_private = NULL;
108                 return 1;
109         } 
110
111         return 0;
112 }
113
114 static int
115 cache_entry_private_destroy( Entry*e )
116 {
117         assert( e->e_private );
118
119         cache_entry_rdwr_destroy( e );
120
121         free( e->e_private );
122         e->e_private = NULL;
123         return 0;
124 }
125
126 void
127 cache_return_entry_rw( Cache *cache, Entry *e, int rw )
128 {
129         ID id;
130         int refcnt;
131
132         /* set cache mutex */
133         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
134
135         assert( e->e_private );
136
137         cache_entry_rdwr_unlock(e, rw);
138
139         id = e->e_id;
140         refcnt = --LEI(e)->lei_refcnt;
141
142         if ( LEI(e)->lei_state == CACHE_ENTRY_CREATING ) {
143                 LEI(e)->lei_state = CACHE_ENTRY_READY;
144
145                 /* free cache mutex */
146                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
147
148                 Debug( LDAP_DEBUG_TRACE,
149                         "====> cache_return_entry_%s( %ld ): created (%d)\n",
150                         rw ? "w" : "r", id, refcnt );
151
152         } else if ( LEI(e)->lei_state == CACHE_ENTRY_DELETED ) {
153                 if( refcnt > 0 ) {
154                         /* free cache mutex */
155                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
156
157                         Debug( LDAP_DEBUG_TRACE,
158                                 "====> cache_return_entry_%s( %ld ): delete pending (%d)\n",
159                                 rw ? "w" : "r", id, refcnt );
160
161                 } else {
162                         cache_entry_private_destroy( e );
163                         entry_free( e );
164
165                         /* free cache mutex */
166                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
167
168                         Debug( LDAP_DEBUG_TRACE,
169                                 "====> cache_return_entry_%s( %ld ): deleted (%d)\n",
170                                 rw ? "w" : "r", id, refcnt );
171                 }
172
173         } else {
174                 /* free cache mutex */
175                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
176
177                 Debug( LDAP_DEBUG_TRACE,
178                         "====> cache_return_entry_%s( %ld ): returned (%d)\n",
179                         rw ? "w" : "r", id, refcnt);
180         }
181 }
182
183 #define LRU_DELETE( cache, e ) do { \
184         if ( LEI(e)->lei_lruprev != NULL ) { \
185                 LEI(LEI(e)->lei_lruprev)->lei_lrunext = LEI(e)->lei_lrunext; \
186         } else { \
187                 (cache)->c_lruhead = LEI(e)->lei_lrunext; \
188         } \
189         if ( LEI(e)->lei_lrunext != NULL ) { \
190                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = LEI(e)->lei_lruprev; \
191         } else { \
192                 (cache)->c_lrutail = LEI(e)->lei_lruprev; \
193         } \
194 } while(0)
195
196 #define LRU_ADD( cache, e ) do { \
197         LEI(e)->lei_lrunext = (cache)->c_lruhead; \
198         if ( LEI(e)->lei_lrunext != NULL ) { \
199                 LEI(LEI(e)->lei_lrunext)->lei_lruprev = (e); \
200         } \
201         (cache)->c_lruhead = (e); \
202         LEI(e)->lei_lruprev = NULL; \
203         if ( (cache)->c_lrutail == NULL ) { \
204                 (cache)->c_lrutail = (e); \
205         } \
206 } while(0)
207
208 /*
209  * cache_add_entry_rw - create and lock an entry in the cache
210  * returns:     0       entry has been created and locked
211  *              1       entry already existed
212  *              -1      something bad happened
213  */
214 int
215 cache_add_entry_rw(
216     Cache       *cache,
217     Entry               *e,
218         int             rw
219 )
220 {
221         int     i, rc;
222         Entry   *ee;
223
224         /* set cache mutex */
225         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
226
227         assert( e->e_private == NULL );
228
229         if( cache_entry_private_init(e) != 0 ) {
230                 /* free cache mutex */
231                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
232
233                 Debug( LDAP_DEBUG_ANY,
234                         "====> cache_add_entry( %ld ): \"%s\": private init failed!\n",
235                     e->e_id, e->e_dn, 0 );
236
237                 return( -1 );
238         }
239
240         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
241                 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
242         {
243                 /* free cache mutex */
244                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
245
246                 Debug( LDAP_DEBUG_TRACE,
247                         "====> cache_add_entry( %ld ): \"%s\": already in dn cache\n",
248                     e->e_id, e->e_dn, 0 );
249
250                 cache_entry_private_destroy(e);
251
252                 return( 1 );
253         }
254
255         /* id tree */
256         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
257                 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
258         {
259                 Debug( LDAP_DEBUG_ANY,
260                         "====> cache_add_entry( %ld ): \"%s\": already in id cache\n",
261                     e->e_id, e->e_dn, 0 );
262
263
264                 /* delete from dn tree inserted above */
265                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
266                         (AVL_CMP) entry_dn_cmp ) == NULL )
267                 {
268                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
269                             0, 0, 0 );
270                 }
271
272                 cache_entry_private_destroy(e);
273
274                 /* free cache mutex */
275                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
276                 return( -1 );
277         }
278
279         cache_entry_rdwr_lock( e, rw );
280
281         /* put the entry into 'CREATING' state */
282         /* will be marked after when entry is returned */
283         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
284         LEI(e)->lei_refcnt = 1;
285
286         /* lru */
287         LRU_ADD( cache, e );
288         if ( ++cache->c_cursize > cache->c_maxsize ) {
289                 /*
290                  * find the lru entry not currently in use and delete it.
291                  * in case a lot of entries are in use, only look at the
292                  * first 10 on the tail of the list.
293                  */
294                 i = 0;
295                 while ( cache->c_lrutail != NULL &&
296                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
297                         i < 10 )
298                 {
299                         /* move this in-use entry to the front of the q */
300                         ee = cache->c_lrutail;
301                         LRU_DELETE( cache, ee );
302                         LRU_ADD( cache, ee );
303                         i++;
304                 }
305
306                 /*
307                  * found at least one to delete - try to get back under
308                  * the max cache size.
309                  */
310                 while ( cache->c_lrutail != NULL &&
311                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
312                         cache->c_cursize > cache->c_maxsize )
313                 {
314                         e = cache->c_lrutail;
315
316                         /* delete from cache and lru q */
317                         /* XXX do we need rc ? */
318                         rc = cache_delete_entry_internal( cache, e );
319                         cache_entry_private_destroy( e );
320                         entry_free( e );
321                 }
322         }
323
324         /* free cache mutex */
325         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
326         return( 0 );
327 }
328
329 /*
330  * cache_update_entry - update a LOCKED entry which has been deleted.
331  * returns:     0       entry has been created and locked
332  *              1       entry already existed
333  *              -1      something bad happened
334  */
335 int
336 cache_update_entry(
337     Cache       *cache,
338     Entry               *e
339 )
340 {
341         int     i, rc;
342         Entry   *ee;
343
344         /* set cache mutex */
345         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
346
347         assert( e->e_private );
348
349         if ( avl_insert( &cache->c_dntree, (caddr_t) e,
350                 (AVL_CMP) entry_dn_cmp, avl_dup_error ) != 0 )
351         {
352                 Debug( LDAP_DEBUG_TRACE,
353                         "====> cache_update_entry( %ld ): \"%s\": already in dn cache\n",
354                     e->e_id, e->e_dn, 0 );
355
356                 /* free cache mutex */
357                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
358                 return( 1 );
359         }
360
361         /* id tree */
362         if ( avl_insert( &cache->c_idtree, (caddr_t) e,
363                 (AVL_CMP) entry_id_cmp, avl_dup_error ) != 0 )
364         {
365                 Debug( LDAP_DEBUG_ANY,
366                         "====> cache_update_entry( %ld ): \"%s\": already in id cache\n",
367                     e->e_id, e->e_dn, 0 );
368
369                 /* delete from dn tree inserted above */
370                 if ( avl_delete( &cache->c_dntree, (caddr_t) e,
371                         (AVL_CMP) entry_dn_cmp ) == NULL )
372                 {
373                         Debug( LDAP_DEBUG_ANY, "====> can't delete from dn cache\n",
374                             0, 0, 0 );
375                 }
376
377                 /* free cache mutex */
378                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
379                 return( -1 );
380         }
381
382
383         /* put the entry into 'CREATING' state */
384         /* will be marked after when entry is returned */
385         LEI(e)->lei_state = CACHE_ENTRY_CREATING;
386
387         /* lru */
388         LRU_ADD( cache, e );
389         if ( ++cache->c_cursize > cache->c_maxsize ) {
390                 /*
391                  * find the lru entry not currently in use and delete it.
392                  * in case a lot of entries are in use, only look at the
393                  * first 10 on the tail of the list.
394                  */
395                 i = 0;
396                 while ( cache->c_lrutail != NULL &&
397                         LEI(cache->c_lrutail)->lei_refcnt != 0 &&
398                         i < 10 )
399                 {
400                         /* move this in-use entry to the front of the q */
401                         ee = cache->c_lrutail;
402                         LRU_DELETE( cache, ee );
403                         LRU_ADD( cache, ee );
404                         i++;
405                 }
406
407                 /*
408                  * found at least one to delete - try to get back under
409                  * the max cache size.
410                  */
411                 while ( cache->c_lrutail != NULL &&
412                         LEI(cache->c_lrutail)->lei_refcnt == 0 &&
413                         cache->c_cursize > cache->c_maxsize )
414                 {
415                         e = cache->c_lrutail;
416
417                         /* delete from cache and lru q */
418                         /* XXX do we need rc ? */
419                         rc = cache_delete_entry_internal( cache, e );
420                         cache_entry_private_destroy( e );
421                         entry_free( e );
422                 }
423         }
424
425         /* free cache mutex */
426         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
427         return( 0 );
428 }
429
430 /*
431  * cache_find_entry_dn2id - find an entry in the cache, given dn
432  */
433
434 ID
435 cache_find_entry_dn2id(
436         Backend         *be,
437     Cache       *cache,
438     char                *dn
439 )
440 {
441         Entry           e, *ep;
442         ID                      id;
443         int count = 0;
444
445         e.e_dn = dn;
446         e.e_ndn = ch_strdup( dn );
447         (void) dn_normalize_case( e.e_ndn );
448
449 try_again:
450         /* set cache mutex */
451         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
452
453         if ( (ep = (Entry *) avl_find( cache->c_dntree, (caddr_t) &e,
454                 (AVL_CMP) entry_dn_cmp )) != NULL )
455         {
456                 int state;
457                 count++;
458
459                 /*
460                  * ep now points to an unlocked entry
461                  * we do not need to lock the entry if we only
462                  * check the state, refcnt, LRU, and id.
463                  */
464
465                 assert( ep->e_private );
466
467                 /* save id */
468                 id = ep->e_id;
469                 state = LEI(ep)->lei_state;
470
471                 /*
472                  * entry is deleted or not fully created yet
473                  */
474                 if ( state != CACHE_ENTRY_READY ) {
475                         assert(state != CACHE_ENTRY_UNDEFINED);
476
477                         /* free cache mutex */
478                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
479
480                         Debug(LDAP_DEBUG_TRACE,
481                                 "====> cache_find_entry_dn2id(\"%s\"): %ld (not ready) %d\n",
482                                 dn, id, state);
483
484                         ldap_pvt_thread_yield();
485                         goto try_again;
486                 }
487
488                 /* lru */
489                 LRU_DELETE( cache, ep );
490                 LRU_ADD( cache, ep );
491                 
492                 /* free cache mutex */
493                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
494
495                 Debug(LDAP_DEBUG_TRACE,
496                         "====> cache_find_entry_dn2id(\"%s\"): %ld (%d tries)\n",
497                         dn, id, count);
498
499         } else {
500                 /* free cache mutex */
501                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
502
503                 id = NOID;
504         }
505
506         free(e.e_ndn);
507
508         return( id );
509 }
510
511 /*
512  * cache_find_entry_id - find an entry in the cache, given id
513  */
514
515 Entry *
516 cache_find_entry_id(
517         Cache   *cache,
518         ID                              id,
519         int                             rw
520 )
521 {
522         Entry   e;
523         Entry   *ep;
524         int     count = 0;
525
526         e.e_id = id;
527
528 try_again:
529         /* set cache mutex */
530         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
531
532         if ( (ep = (Entry *) avl_find( cache->c_idtree, (caddr_t) &e,
533                 (AVL_CMP) entry_id_cmp )) != NULL )
534         {
535                 int state;
536                 ID      ep_id;
537
538                 count++;
539
540                 assert( ep->e_private );
541
542                 ep_id = ep->e_id; 
543                 state = LEI(ep)->lei_state;
544
545                 /*
546                  * entry is deleted or not fully created yet
547                  */
548                 if ( state != CACHE_ENTRY_READY ) {
549
550                         assert(state != CACHE_ENTRY_UNDEFINED);
551
552                         /* free cache mutex */
553                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
554
555                         Debug(LDAP_DEBUG_TRACE,
556                                 "====> cache_find_entry_id( %ld ): %ld (not ready) %d\n",
557                                 id, ep_id, state);
558
559                         ldap_pvt_thread_yield();
560                         goto try_again;
561                 }
562
563                 /* acquire reader lock */
564                 if ( cache_entry_rdwr_trylock(ep, rw) == LDAP_PVT_THREAD_EBUSY ) {
565                         /* could not acquire entry lock...
566                          * owner cannot free as we have the cache locked.
567                          * so, unlock the cache, yield, and try again.
568                          */
569
570                         /* free cache mutex */
571                         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
572
573                         Debug(LDAP_DEBUG_TRACE,
574                                 "====> cache_find_entry_id( %ld ): %ld (busy) %d\n",
575                                 id, ep_id, state);
576
577                         ldap_pvt_thread_yield();
578                         goto try_again;
579                 }
580
581                 /* lru */
582                 LRU_DELETE( cache, ep );
583                 LRU_ADD( cache, ep );
584                 
585                 LEI(ep)->lei_refcnt++;
586
587                 /* free cache mutex */
588                 ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
589
590                 Debug(LDAP_DEBUG_TRACE,
591                         "====> cache_find_entry_id( %ld ) \"%s\" (found) (%d tries)\n",
592                         ep_id, ep->e_dn, count);
593
594                 return( ep );
595         }
596
597         /* free cache mutex */
598         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
599
600         return( NULL );
601 }
602
603 /*
604  * cache_delete_entry - delete the entry e from the cache.  the caller
605  * should have obtained e (increasing its ref count) via a call to one
606  * of the cache_find_* routines.  the caller should *not* call the
607  * cache_return_entry() routine prior to calling cache_delete_entry().
608  * it performs this function.
609  *
610  * returns:     0       e was deleted ok
611  *              1       e was not in the cache
612  *              -1      something bad happened
613  */
614 int
615 cache_delete_entry(
616     Cache       *cache,
617     Entry               *e
618 )
619 {
620         int     rc;
621
622         /* set cache mutex */
623         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
624
625         assert( e->e_private );
626
627         Debug( LDAP_DEBUG_TRACE, "====> cache_delete_entry( %ld )\n",
628                 e->e_id, 0, 0 );
629
630         rc = cache_delete_entry_internal( cache, e );
631
632         /* free cache mutex */
633         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
634         return( rc );
635 }
636
637 static int
638 cache_delete_entry_internal(
639     Cache       *cache,
640     Entry               *e
641 )
642 {
643         int rc = 0;     /* return code */
644
645         /* dn tree */
646         if ( avl_delete( &cache->c_dntree, (caddr_t) e, (AVL_CMP) entry_dn_cmp )
647                 == NULL )
648         {
649                 rc = -1;
650         }
651
652         /* id tree */
653         if ( avl_delete( &cache->c_idtree, (caddr_t) e, (AVL_CMP) entry_id_cmp )
654                 == NULL )
655         {
656                 rc = -1;
657         }
658
659         if (rc != 0) {
660                 return rc;
661         }
662
663         /* lru */
664         LRU_DELETE( cache, e );
665         cache->c_cursize--;
666
667         /*
668          * flag entry to be freed later by a call to cache_return_entry()
669          */
670         LEI(e)->lei_state = CACHE_ENTRY_DELETED;
671
672         return( 0 );
673 }
674
675 #ifdef SLAP_CLEANUP
676
677 void
678 cache_release_all( Cache *cache )
679 {
680         Entry *e;
681         int rc;
682
683         /* set cache mutex */
684         ldap_pvt_thread_mutex_lock( &cache->c_mutex );
685
686         Debug( LDAP_DEBUG_TRACE, "====> cache_release_all\n", 0, 0, 0 );
687
688         while ( (e = cache->c_lrutail) != NULL && LEI(e)->lei_refcnt == 0 ) {
689                 assert(!ldap_pvt_thread_rdwr_active(&LEI(e)->lei_rdwr));
690
691                 /* delete from cache and lru q */
692                 /* XXX do we need rc ? */
693                 rc = cache_delete_entry_internal( cache, e );
694                 cache_entry_private_destroy( e );
695                 entry_free( e );
696         }
697
698         if ( cache->c_cursize ) {
699                 Debug( LDAP_DEBUG_TRACE, "Entry-cache could not be emptied\n", 0, 0, 0 );
700         }
701
702         /* free cache mutex */
703         ldap_pvt_thread_mutex_unlock( &cache->c_mutex );
704 }
705
706 #endif /* SLAP_CLEANUP */
707
708 #ifdef LDAP_DEBUG
709
710 static void
711 lru_print( Cache *cache )
712 {
713         Entry   *e;
714
715         fprintf( stderr, "LRU queue (head to tail):\n" );
716         for ( e = cache->c_lruhead; e != NULL; e = LEI(e)->lei_lrunext ) {
717                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
718                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
719         }
720         fprintf( stderr, "LRU queue (tail to head):\n" );
721         for ( e = cache->c_lrutail; e != NULL; e = LEI(e)->lei_lruprev ) {
722                 fprintf( stderr, "\tdn \"%20s\" id %ld refcnt %d\n",
723                         e->e_dn, e->e_id, LEI(e)->lei_refcnt );
724         }
725 }
726
727 #endif
728