3 * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved.
4 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
7 * Copyright (c) 1993 The Regents of the University of Michigan.
10 * cache.c - local caching support for LDAP
17 #include <ac/stdlib.h>
19 #include <ac/socket.h>
20 #include <ac/string.h>
27 static int cache_hash LDAP_P(( BerElement *ber ));
28 static LDAPMessage *msg_dup LDAP_P(( LDAPMessage *msg ));
29 static int request_cmp LDAP_P(( BerElement *req1, BerElement *req2 ));
30 static int chain_contains_dn LDAP_P(( LDAPMessage *msg, LDAP_CONST char *dn ));
31 static ber_len_t msg_size LDAP_P(( LDAPMessage *msg ));
32 static void check_cache_memused LDAP_P(( LDAPCache *lc ));
33 static void uncache_entry_or_req LDAP_P(( LDAP *ld, LDAP_CONST char *dn, ber_int_t msgid ));
38 ldap_enable_cache( LDAP *ld, long timeout, ber_len_t maxmem )
41 if ( ld->ld_cache == NULL ) {
42 if (( ld->ld_cache = (LDAPCache *)LDAP_MALLOC( sizeof( LDAPCache )))
44 ld->ld_errno = LDAP_NO_MEMORY;
47 (void) memset( ld->ld_cache, '\0', sizeof( LDAPCache ));
48 ld->ld_cache->lc_memused = sizeof( LDAPCache );
51 ld->ld_cache->lc_timeout = timeout;
52 ld->ld_cache->lc_maxmem = maxmem;
53 check_cache_memused( ld->ld_cache );
54 ld->ld_cache->lc_enabled = 1;
63 ldap_disable_cache( LDAP *ld )
66 if ( ld->ld_cache != NULL ) {
67 ld->ld_cache->lc_enabled = 0;
75 ldap_set_cache_options( LDAP *ld, unsigned long opts )
78 if ( ld->ld_cache != NULL ) {
79 ld->ld_cache->lc_options = opts;
86 ldap_destroy_cache( LDAP *ld )
89 if ( ld->ld_cache != NULL ) {
90 ldap_flush_cache( ld );
91 LDAP_FREE( (char *)ld->ld_cache );
99 ldap_flush_cache( LDAP *ld )
103 LDAPMessage *m, *next;
106 LDAP_LOG (( "cache", LDAP_LEVEL_ENTRY, "ldap_flush_cache\n" ));
108 Debug( LDAP_DEBUG_TRACE, "ldap_flush_cache\n", 0, 0, 0 );
111 if ( ld->ld_cache != NULL ) {
112 /* delete all requests in the queue */
113 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
117 ld->ld_cache->lc_requests = NULL;
119 /* delete all messages in the cache */
120 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
121 for ( m = ld->ld_cache->lc_buckets[ i ];
122 m != NULL; m = next ) {
126 ld->ld_cache->lc_buckets[ i ] = NULL;
128 ld->ld_cache->lc_memused = sizeof( LDAPCache );
135 ldap_uncache_request( LDAP *ld, int msgid )
139 LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
140 "ldap_uncache_request %d ld_cache %lx\n",
141 msgid, (long) ld->ld_cache ));
143 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_request %d ld_cache %lx\n",
144 msgid, (long) ld->ld_cache, 0 );
147 uncache_entry_or_req( ld, NULL, msgid );
153 ldap_uncache_entry( LDAP *ld, LDAP_CONST char *dn )
157 LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
158 "ldap_uncache_entry %s ld_cache %lx\n",
159 dn, (long) ld->ld_cache ));
161 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_entry %s ld_cache %lx\n",
162 dn, (long) ld->ld_cache, 0 );
165 uncache_entry_or_req( ld, dn, 0 );
173 uncache_entry_or_req( LDAP *ld,
174 const char *dn, /* if non-NULL, uncache entry */
175 ber_int_t msgid ) /* request to uncache (if dn == NULL) */
178 LDAPMessage *m, *prev, *next;
181 LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
182 "uncache_entry_or_req dn %s msgid %ld ld_cache %lx\n",
183 dn, (long) msgid, (long) ld->ld_cache ));
185 Debug( LDAP_DEBUG_TRACE,
186 "ldap_uncache_entry_or_req dn %s msgid %ld ld_cache %lx\n",
187 dn, (long) msgid, (long) ld->ld_cache );
190 if ( ld->ld_cache == NULL ) {
194 /* first check the request queue */
196 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
198 if (( dn != NULL && chain_contains_dn( m, dn )) ||
199 ( dn == NULL && m->lm_msgid == msgid )) {
200 if ( prev == NULL ) {
201 ld->ld_cache->lc_requests = next;
203 prev->lm_next = next;
205 ld->ld_cache->lc_memused -= msg_size( m );
212 /* now check the rest of the cache */
213 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
215 for ( m = ld->ld_cache->lc_buckets[ i ]; m != NULL;
218 if (( dn != NULL && chain_contains_dn( m, dn )) ||
219 ( dn == NULL && m->lm_msgid == msgid )) {
220 if ( prev == NULL ) {
221 ld->ld_cache->lc_buckets[ i ] = next;
223 prev->lm_next = next;
225 ld->ld_cache->lc_memused -= msg_size( m );
237 ldap_add_request_to_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
244 LDAP_LOG (( "cache", LDAP_LEVEL_ENTRY, "ldap_add_request_to_cache\n" ));
246 Debug( LDAP_DEBUG_TRACE, "ldap_add_request_to_cache\n", 0, 0, 0 );
249 ld->ld_errno = LDAP_SUCCESS;
250 if ( ld->ld_cache == NULL ||
251 ( ld->ld_cache->lc_enabled == 0 )) {
255 if (( new = (LDAPMessage *) LDAP_CALLOC( 1, sizeof(LDAPMessage) ))
257 if (( new->lm_ber = ldap_alloc_ber_with_options( ld )) == NULL ) {
258 LDAP_FREE( (char *)new );
261 len = request->ber_ptr - request->ber_buf;
262 if (( new->lm_ber->ber_buf = (char *) ber_memalloc( (size_t)len ))
264 ber_free( new->lm_ber, 0 );
265 LDAP_FREE( (char *)new );
266 ld->ld_errno = LDAP_NO_MEMORY;
269 AC_MEMCPY( new->lm_ber->ber_buf, request->ber_buf,
271 new->lm_ber->ber_ptr = new->lm_ber->ber_buf;
272 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
273 new->lm_msgid = ld->ld_msgid;
274 new->lm_msgtype = msgtype;;
275 new->lm_next = ld->ld_cache->lc_requests;
276 ld->ld_cache->lc_requests = new;
278 ld->ld_errno = LDAP_NO_MEMORY;
285 ldap_add_result_to_cache( LDAP *ld, LDAPMessage *result )
288 LDAPMessage *m, **mp, *req, *new, *prev;
292 LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
293 "ldap_add_result_to_cache: id %ld, type %ld\n",
294 (long) result->lm_msgid, (long) result->lm_msgtype ));
296 Debug( LDAP_DEBUG_TRACE, "ldap_add_result_to_cache: id %ld, type %ld\n",
297 (long) result->lm_msgid, (long) result->lm_msgtype, 0 );
300 if ( ld->ld_cache == NULL ||
301 ( ld->ld_cache->lc_enabled == 0 )) {
303 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
304 "ldap_add_result_to_cache: cache disabled\n" ));
306 Debug( LDAP_DEBUG_TRACE, "artc: cache disabled\n", 0, 0, 0 );
311 if ( result->lm_msgtype != LDAP_RES_SEARCH_ENTRY &&
312 result->lm_msgtype != LDAP_RES_SEARCH_REFERENCE &&
313 result->lm_msgtype != LDAP_RES_SEARCH_RESULT &&
314 result->lm_msgtype != LDAP_RES_COMPARE ) {
316 * only cache search and compare operations
319 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
320 "ldap_add_result_to_cache: "
321 "only caching search & compare operations\n" ));
323 Debug( LDAP_DEBUG_TRACE,
324 "artc: only caching search & compare operations\n", 0, 0, 0 );
330 * if corresponding request is in the lc_requests list, add this
331 * result to it. if this result completes the results for the
332 * request, add the request/result chain to the cache proper.
335 for ( m = ld->ld_cache->lc_requests; m != NULL; m = m->lm_next ) {
336 if ( m->lm_msgid == result->lm_msgid ) {
342 if ( m != NULL ) { /* found request; add to end of chain */
344 for ( ; m->lm_chain != NULL; m = m->lm_chain )
346 if (( new = msg_dup( result )) != NULL ) {
347 new->lm_chain = NULL;
350 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
351 "ldap_add_result_to_cache: "
352 "result added to cache request chain\n" ));
354 Debug( LDAP_DEBUG_TRACE,
355 "artc: result added to cache request chain\n",
359 if ( result->lm_msgtype == LDAP_RES_SEARCH_RESULT ||
360 result->lm_msgtype == LDAP_RES_COMPARE ) {
362 * this result completes the chain of results
363 * add to cache proper if appropriate
365 keep = 0; /* pessimistic */
366 err = ldap_result2error( ld, result, 0 );
367 if ( err == LDAP_SUCCESS ||
368 ( result->lm_msgtype == LDAP_RES_COMPARE &&
369 ( err == LDAP_COMPARE_FALSE ||
370 err == LDAP_COMPARE_TRUE ||
371 err == LDAP_NO_SUCH_ATTRIBUTE ))) {
375 if ( ld->ld_cache->lc_options == 0 ) {
376 if ( err == LDAP_SIZELIMIT_EXCEEDED ) {
379 } else if (( ld->ld_cache->lc_options &
380 LDAP_CACHE_OPT_CACHEALLERRS ) != 0 ) {
384 if ( prev == NULL ) {
385 ld->ld_cache->lc_requests = req->lm_next;
387 prev->lm_next = req->lm_next;
392 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
393 "ldap_add_result_to_cache: "
394 "not caching result with error\n" ));
396 Debug( LDAP_DEBUG_TRACE,
397 "artc: not caching result with error %d\n",
402 mp = &ld->ld_cache->lc_buckets[
403 cache_hash( req->lm_ber ) ];
406 req->lm_time = (long) time( NULL );
407 ld->ld_cache->lc_memused += msg_size( req );
408 check_cache_memused( ld->ld_cache );
410 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
411 "ldap_add_result_to_cache: "
412 "cached result with error\n" ));
414 Debug( LDAP_DEBUG_TRACE,
415 "artc: cached result with error %d\n",
422 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
423 "ldap_add_result_to_cache: "
424 "msgid not in request list\n" ));
426 Debug( LDAP_DEBUG_TRACE, "artc: msgid not in request list\n",
435 * look in the cache for this request
436 * return 0 if found, -1 if not
437 * if found, the corresponding result messages are added to the incoming
438 * queue with the correct (new) msgid so that subsequent ldap_result calls
442 ldap_check_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
445 LDAPMessage *m, *new, *prev, *next;
451 LDAP_LOG (( "cache", LDAP_LEVEL_ENTRY, "ldap_check_cache\n" ));
453 Debug( LDAP_DEBUG_TRACE, "ldap_check_cache\n", 0, 0, 0 );
456 if ( ld->ld_cache == NULL ||
457 ( ld->ld_cache->lc_enabled == 0 )) {
461 memset( &reqber, '\0', sizeof(reqber) );
462 reqber.ber_valid = LBER_VALID_BERELEMENT;
463 reqber.ber_buf = reqber.ber_ptr = request->ber_buf;
464 reqber.ber_end = request->ber_ptr;
465 reqber.ber_debug = ber_int_debug;
467 c_time = time( NULL );
470 hash = cache_hash( &reqber );
471 for ( m = ld->ld_cache->lc_buckets[ hash ]; m != NULL; m = next ) {
473 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
474 "ldap_check_cache: examining id %ld, type %ld\n",
475 (long) m->lm_msgid, (long) m->lm_msgtype ));
477 Debug( LDAP_DEBUG_TRACE,"cc: examining id %ld,type %ld\n",
478 (long) m->lm_msgid, (long) m->lm_msgtype, 0 );
480 if ( difftime(c_time, m->lm_time) > ld->ld_cache->lc_timeout ) {
481 /* delete expired message */
483 if ( prev == NULL ) {
484 ld->ld_cache->lc_buckets[ hash ] = next;
486 prev->lm_next = next;
489 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
490 "ldap_check_cache: expired id %ld\n",
491 (long) m->lm_msgid ));
493 Debug( LDAP_DEBUG_TRACE, "cc: expired id %d\n",
496 ld->ld_cache->lc_memused -= msg_size( m );
499 if ( m->lm_msgtype == (int)msgtype &&
500 request_cmp( m->lm_ber, &reqber ) == 0 ) {
513 * add duplicates of responses to incoming queue
516 for ( m = m->lm_chain; m != NULL; m = m->lm_chain ) {
517 if (( new = msg_dup( m )) == NULL ) {
521 new->lm_msgid = ld->ld_msgid;
522 new->lm_chain = NULL;
524 new->lm_next = ld->ld_responses;
525 ld->ld_responses = new;
528 prev->lm_chain = new;
532 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
533 "ldap_check_cache: added type %ld\n",
534 (long) m->lm_msgtype ));
536 Debug( LDAP_DEBUG_TRACE, "cc: added type %ld\n",
537 (long) new->lm_msgtype, 0, 0 );
542 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
543 "ldap_check_cache: result returned from cache\n" ));
545 Debug( LDAP_DEBUG_TRACE, "cc: result returned from cache\n", 0, 0, 0 );
556 cache_hash( BerElement *ber )
562 * just take the length of the packet and mod with # of buckets
565 if ( ber_skip_tag( &bercpy, &len ) == LBER_ERROR
566 || ber_scanf( &bercpy, "x" ) == LBER_ERROR ) {
567 len = 0; /* punt: just return zero */
569 len = bercpy.ber_end - bercpy.ber_ptr;
573 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
574 "cache_hash: len is %ld, returning %ld\n",
575 len, len % LDAP_CACHE_BUCKETS ));
577 Debug( LDAP_DEBUG_TRACE, "cache_hash: len is %ld, returning %ld\n",
578 len, len % LDAP_CACHE_BUCKETS, 0 );
580 return( (int) ( len % LDAP_CACHE_BUCKETS ));
585 msg_dup( LDAPMessage *msg )
590 if (( new = (LDAPMessage *)LDAP_MALLOC( sizeof(LDAPMessage))) != NULL ) {
591 *new = *msg; /* struct copy */
592 if (( new->lm_ber = ber_dup( msg->lm_ber )) == NULL ) {
593 LDAP_FREE( (char *)new );
596 len = msg->lm_ber->ber_end - msg->lm_ber->ber_buf;
597 if (( new->lm_ber->ber_buf = (char *) ber_memalloc(
598 (size_t)len )) == NULL ) {
599 ber_free( new->lm_ber, 0 );
600 LDAP_FREE( (char *)new );
603 AC_MEMCPY( new->lm_ber->ber_buf, msg->lm_ber->ber_buf,
605 new->lm_ber->ber_ptr = new->lm_ber->ber_buf +
606 ( msg->lm_ber->ber_ptr - msg->lm_ber->ber_buf );
607 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
615 request_cmp( BerElement *req1, BerElement *req2 )
620 r1 = *req1; /* struct copies */
624 * skip the enclosing tags (sequence markers) and the msg ids
626 if ( ber_skip_tag( &r1, &len ) == LBER_ERROR || ber_scanf( &r1, "x" )
630 if ( ber_skip_tag( &r2, &len ) == LBER_ERROR || ber_scanf( &r2, "x" )
636 * check remaining length and bytes if necessary
638 if (( len = r1.ber_end - r1.ber_ptr ) !=
639 (ber_len_t) (r2.ber_end - r2.ber_ptr) )
641 return( -1 ); /* different lengths */
643 return( memcmp( r1.ber_ptr, r2.ber_ptr, (size_t)len ));
648 chain_contains_dn( LDAPMessage *msg, const char *dn )
658 * first check the base or dn of the request
660 ber = *msg->lm_ber; /* struct copy */
661 if ( ber_scanf( &ber, "{i{a" /*}}*/, &msgid, &s ) != LBER_ERROR ) {
662 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
669 if ( msg->lm_msgtype == LDAP_REQ_COMPARE ) {
674 * now check the dn of each search result
677 for ( m = msg->lm_chain; m != NULL && rc == 0 ; m = m->lm_chain ) {
678 if ( m->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
681 ber = *m->lm_ber; /* struct copy */
682 if ( ber_scanf( &ber, "{a" /*}*/, &s ) != LBER_ERROR ) {
683 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
693 msg_size( LDAPMessage *msg )
699 for ( m = msg; m != NULL; m = m->lm_chain ) {
700 size += ( sizeof( LDAPMessage ) + m->lm_ber->ber_end -
701 m->lm_ber->ber_buf );
708 #define THRESHOLD_FACTOR 3 / 4
709 #define SIZE_FACTOR 2 / 3
712 check_cache_memused( LDAPCache *lc )
715 * this routine is called to check if the cache is too big (lc_maxmem >
716 * minimum cache size and lc_memused > lc_maxmem). If too big, it reduces
717 * the cache size to < SIZE_FACTOR * lc_maxmem. The algorithm is as follows:
718 * remove_threshold = lc_timeout seconds;
720 * remove everything older than remove_threshold seconds;
721 * remove_threshold = remove_threshold * THRESHOLD_FACTOR;
722 * } while ( cache size is > SIZE_FACTOR * lc_maxmem )
725 unsigned long remove_threshold;
727 LDAPMessage *m, *prev, *next;
730 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
731 "check_cache_memused: %ld bytes in use (%ld max)\n",
732 lc->lc_memused, lc->lc_maxmem ));
734 Debug( LDAP_DEBUG_TRACE, "check_cache_memused: %ld bytes in use (%ld max)\n",
735 lc->lc_memused, lc->lc_maxmem, 0 );
738 if ( (unsigned) lc->lc_maxmem <= sizeof( LDAPCache )
739 || lc->lc_memused <= lc->lc_maxmem * SIZE_FACTOR ) {
743 remove_threshold = lc->lc_timeout;
744 while ( lc->lc_memused > lc->lc_maxmem * SIZE_FACTOR ) {
745 c_time = time( NULL );
746 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
748 for ( m = lc->lc_buckets[ i ]; m != NULL;
751 if ( difftime(c_time, m->lm_time) > remove_threshold) {
752 if ( prev == NULL ) {
753 lc->lc_buckets[ i ] = next;
755 prev->lm_next = next;
757 lc->lc_memused -= msg_size( m );
759 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
760 "check_cache_memused: removed %ld\n",
763 Debug( LDAP_DEBUG_TRACE,
773 remove_threshold *= THRESHOLD_FACTOR;
777 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
778 "check_cache_memused: reduced usage to %ld bytes\n",
781 Debug( LDAP_DEBUG_TRACE, "ccm: reduced usage to %ld bytes\n",
782 lc->lc_memused, 0, 0 );
786 #endif /* !NO_CACHE */