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 assert( LDAP_VALID( ld ) );
44 if ( ld->ld_cache == NULL ) {
45 if (( ld->ld_cache = (LDAPCache *)LDAP_MALLOC( sizeof( LDAPCache )))
47 ld->ld_errno = LDAP_NO_MEMORY;
50 (void) memset( ld->ld_cache, '\0', sizeof( LDAPCache ));
51 ld->ld_cache->lc_memused = sizeof( LDAPCache );
54 ld->ld_cache->lc_timeout = timeout;
55 ld->ld_cache->lc_maxmem = maxmem;
56 check_cache_memused( ld->ld_cache );
57 ld->ld_cache->lc_enabled = 1;
66 ldap_disable_cache( LDAP *ld )
69 assert( LDAP_VALID( ld ) );
72 if ( ld->ld_cache != NULL ) {
73 ld->ld_cache->lc_enabled = 0;
81 ldap_set_cache_options( LDAP *ld, unsigned long opts )
84 assert( LDAP_VALID( ld ) );
87 if ( ld->ld_cache != NULL ) {
88 ld->ld_cache->lc_options = opts;
95 ldap_destroy_cache( LDAP *ld )
98 assert( LDAP_VALID( ld ) );
101 if ( ld->ld_cache != NULL ) {
102 ldap_flush_cache( ld );
103 LDAP_FREE( (char *)ld->ld_cache );
111 ldap_flush_cache( LDAP *ld )
115 LDAPMessage *m, *next;
117 assert( ld != NULL );
118 assert( LDAP_VALID( ld ) );
121 LDAP_LOG ( CACHE, ENTRY, "ldap_flush_cache\n", 0, 0, 0 );
123 Debug( LDAP_DEBUG_TRACE, "ldap_flush_cache\n", 0, 0, 0 );
126 if ( ld->ld_cache != NULL ) {
127 /* delete all requests in the queue */
128 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
132 ld->ld_cache->lc_requests = NULL;
134 /* delete all messages in the cache */
135 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
136 for ( m = ld->ld_cache->lc_buckets[ i ];
137 m != NULL; m = next ) {
141 ld->ld_cache->lc_buckets[ i ] = NULL;
143 ld->ld_cache->lc_memused = sizeof( LDAPCache );
150 ldap_uncache_request( LDAP *ld, int msgid )
152 assert( ld != NULL );
153 assert( LDAP_VALID( ld ) );
158 LDAP_LOG ( CACHE, ARGS, "ldap_uncache_request %d ld_cache %lx\n",
159 msgid, (long) ld->ld_cache, 0 );
161 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_request %d ld_cache %lx\n",
162 msgid, (long) ld->ld_cache, 0 );
165 uncache_entry_or_req( ld, NULL, msgid );
171 ldap_uncache_entry( LDAP *ld, LDAP_CONST char *dn )
173 assert( ld != NULL );
174 assert( LDAP_VALID( ld ) );
175 assert( dn != NULL );
180 LDAP_LOG ( CACHE, ARGS, "ldap_uncache_entry %s ld_cache %lx\n",
181 dn, (long) ld->ld_cache, 0 );
183 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_entry %s ld_cache %lx\n",
184 dn, (long) ld->ld_cache, 0 );
187 uncache_entry_or_req( ld, dn, 0 );
195 uncache_entry_or_req( LDAP *ld,
196 const char *dn, /* if non-NULL, uncache entry */
197 ber_int_t msgid ) /* request to uncache (if dn == NULL) */
200 LDAPMessage *m, *prev, *next;
204 LDAP_LOG ( CACHE, ARGS,
205 "uncache_entry_or_req dn %s msgid %ld ld_cache %lx\n",
206 dn, (long) msgid, (long) ld->ld_cache );
208 Debug( LDAP_DEBUG_TRACE,
209 "ldap_uncache_entry_or_req dn %s msgid %ld ld_cache %lx\n",
210 dn, (long) msgid, (long) ld->ld_cache );
213 if ( ld->ld_cache == NULL ) {
217 /* first check the request queue */
219 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
221 if (( dn != NULL && chain_contains_dn( m, dn )) ||
222 ( dn == NULL && m->lm_msgid == msgid )) {
223 if ( prev == NULL ) {
224 ld->ld_cache->lc_requests = next;
226 prev->lm_next = next;
228 ld->ld_cache->lc_memused -= msg_size( m );
235 /* now check the rest of the cache */
236 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
238 for ( m = ld->ld_cache->lc_buckets[ i ]; m != NULL;
241 if (( dn != NULL && chain_contains_dn( m, dn )) ||
242 ( dn == NULL && m->lm_msgid == msgid )) {
243 if ( prev == NULL ) {
244 ld->ld_cache->lc_buckets[ i ] = next;
246 prev->lm_next = next;
248 ld->ld_cache->lc_memused -= msg_size( m );
260 ldap_add_request_to_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
266 assert( ld != NULL );
267 assert( LDAP_VALID( ld ) );
270 LDAP_LOG ( CACHE, ENTRY, "ldap_add_request_to_cache\n", 0, 0, 0 );
272 Debug( LDAP_DEBUG_TRACE, "ldap_add_request_to_cache\n", 0, 0, 0 );
275 ld->ld_errno = LDAP_SUCCESS;
276 if ( ld->ld_cache == NULL ||
277 ( ld->ld_cache->lc_enabled == 0 )) {
281 if (( new = (LDAPMessage *) LDAP_CALLOC( 1, sizeof(LDAPMessage) ))
283 if (( new->lm_ber = ldap_alloc_ber_with_options( ld )) == NULL ) {
284 LDAP_FREE( (char *)new );
287 len = request->ber_ptr - request->ber_buf;
288 if (( new->lm_ber->ber_buf = (char *) ber_memalloc( (size_t)len ))
290 ber_free( new->lm_ber, 0 );
291 LDAP_FREE( (char *)new );
292 ld->ld_errno = LDAP_NO_MEMORY;
295 AC_MEMCPY( new->lm_ber->ber_buf, request->ber_buf,
297 new->lm_ber->ber_ptr = new->lm_ber->ber_buf;
298 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
299 new->lm_msgid = ld->ld_msgid;
300 new->lm_msgtype = msgtype;;
301 new->lm_next = ld->ld_cache->lc_requests;
302 ld->ld_cache->lc_requests = new;
304 ld->ld_errno = LDAP_NO_MEMORY;
311 ldap_add_result_to_cache( LDAP *ld, LDAPMessage *result )
314 LDAPMessage *m, **mp, *req, *new, *prev;
317 assert( ld != NULL );
318 assert( LDAP_VALID( ld ) );
319 assert( result != NULL );
323 LDAP_LOG ( CACHE, ARGS,
324 "ldap_add_result_to_cache: id %ld, type %ld\n",
325 (long) result->lm_msgid, (long) result->lm_msgtype, 0 );
327 Debug( LDAP_DEBUG_TRACE, "ldap_add_result_to_cache: id %ld, type %ld\n",
328 (long) result->lm_msgid, (long) result->lm_msgtype, 0 );
331 if ( ld->ld_cache == NULL ||
332 ( ld->ld_cache->lc_enabled == 0 )) {
334 LDAP_LOG ( CACHE, DETAIL1,
335 "ldap_add_result_to_cache: cache disabled\n", 0, 0, 0 );
337 Debug( LDAP_DEBUG_TRACE, "artc: cache disabled\n", 0, 0, 0 );
342 if ( result->lm_msgtype != LDAP_RES_SEARCH_ENTRY &&
343 result->lm_msgtype != LDAP_RES_SEARCH_REFERENCE &&
344 result->lm_msgtype != LDAP_RES_SEARCH_RESULT &&
345 result->lm_msgtype != LDAP_RES_COMPARE ) {
347 * only cache search and compare operations
350 LDAP_LOG ( CACHE, DETAIL1,
351 "ldap_add_result_to_cache: only caching search & "
352 "compare operations\n", 0, 0, 0 );
354 Debug( LDAP_DEBUG_TRACE,
355 "artc: only caching search & compare operations\n", 0, 0, 0 );
361 * if corresponding request is in the lc_requests list, add this
362 * result to it. if this result completes the results for the
363 * request, add the request/result chain to the cache proper.
366 for ( m = ld->ld_cache->lc_requests; m != NULL; m = m->lm_next ) {
367 if ( m->lm_msgid == result->lm_msgid ) {
373 if ( m != NULL ) { /* found request; add to end of chain */
375 for ( ; m->lm_chain != NULL; m = m->lm_chain )
377 if (( new = msg_dup( result )) != NULL ) {
378 new->lm_chain = NULL;
381 LDAP_LOG ( CACHE, RESULTS,
382 "ldap_add_result_to_cache: "
383 "result added to cache request chain\n", 0, 0, 0 );
385 Debug( LDAP_DEBUG_TRACE,
386 "artc: result added to cache request chain\n",
390 if ( result->lm_msgtype == LDAP_RES_SEARCH_RESULT ||
391 result->lm_msgtype == LDAP_RES_COMPARE ) {
393 * this result completes the chain of results
394 * add to cache proper if appropriate
396 keep = 0; /* pessimistic */
397 err = ldap_result2error( ld, result, 0 );
398 if ( err == LDAP_SUCCESS ||
399 ( result->lm_msgtype == LDAP_RES_COMPARE &&
400 ( err == LDAP_COMPARE_FALSE ||
401 err == LDAP_COMPARE_TRUE ||
402 err == LDAP_NO_SUCH_ATTRIBUTE ))) {
406 if ( ld->ld_cache->lc_options == 0 ) {
407 if ( err == LDAP_SIZELIMIT_EXCEEDED ) {
410 } else if (( ld->ld_cache->lc_options &
411 LDAP_CACHE_OPT_CACHEALLERRS ) != 0 ) {
415 if ( prev == NULL ) {
416 ld->ld_cache->lc_requests = req->lm_next;
418 prev->lm_next = req->lm_next;
423 LDAP_LOG ( CACHE, RESULTS,
424 "ldap_add_result_to_cache: "
425 "not caching result with error\n", 0, 0, 0 );
427 Debug( LDAP_DEBUG_TRACE,
428 "artc: not caching result with error %d\n",
433 mp = &ld->ld_cache->lc_buckets[
434 cache_hash( req->lm_ber ) ];
437 req->lm_time = (long) time( NULL );
438 ld->ld_cache->lc_memused += msg_size( req );
439 check_cache_memused( ld->ld_cache );
441 LDAP_LOG ( CACHE, RESULTS,
442 "ldap_add_result_to_cache: "
443 "cached result with error\n", 0, 0, 0 );
445 Debug( LDAP_DEBUG_TRACE,
446 "artc: cached result with error %d\n",
453 LDAP_LOG ( CACHE, RESULTS,
454 "ldap_add_result_to_cache: msgid not in request list\n", 0, 0, 0 );
456 Debug( LDAP_DEBUG_TRACE, "artc: msgid not in request list\n",
465 * look in the cache for this request
466 * return 0 if found, -1 if not
467 * if found, the corresponding result messages are added to the incoming
468 * queue with the correct (new) msgid so that subsequent ldap_result calls
472 ldap_check_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
475 LDAPMessage *m, *new, *prev, *next;
480 assert( ld != NULL );
481 assert( LDAP_VALID( ld ) );
482 assert( request != NULL );
485 LDAP_LOG ( CACHE, ENTRY, "ldap_check_cache\n", 0, 0, 0 );
487 Debug( LDAP_DEBUG_TRACE, "ldap_check_cache\n", 0, 0, 0 );
490 if ( ld->ld_cache == NULL ||
491 ( ld->ld_cache->lc_enabled == 0 )) {
495 memset( &reqber, '\0', sizeof(reqber) );
496 reqber.ber_valid = LBER_VALID_BERELEMENT;
497 reqber.ber_buf = reqber.ber_ptr = request->ber_buf;
498 reqber.ber_end = request->ber_ptr;
499 reqber.ber_debug = ber_int_debug;
501 c_time = time( NULL );
504 hash = cache_hash( &reqber );
505 for ( m = ld->ld_cache->lc_buckets[ hash ]; m != NULL; m = next ) {
507 LDAP_LOG ( CACHE, DETAIL1,
508 "ldap_check_cache: examining id %ld, type %ld\n",
509 (long) m->lm_msgid, (long) m->lm_msgtype, 0 );
511 Debug( LDAP_DEBUG_TRACE,"cc: examining id %ld,type %ld\n",
512 (long) m->lm_msgid, (long) m->lm_msgtype, 0 );
514 if ( difftime(c_time, m->lm_time) > ld->ld_cache->lc_timeout ) {
515 /* delete expired message */
517 if ( prev == NULL ) {
518 ld->ld_cache->lc_buckets[ hash ] = next;
520 prev->lm_next = next;
523 LDAP_LOG ( CACHE, DETAIL1, "ldap_check_cache: expired id %ld\n",
524 (long) m->lm_msgid, 0, 0 );
526 Debug( LDAP_DEBUG_TRACE, "cc: expired id %d\n",
529 ld->ld_cache->lc_memused -= msg_size( m );
532 if ( m->lm_msgtype == msgtype &&
533 request_cmp( m->lm_ber, &reqber ) == 0 ) {
546 * add duplicates of responses to incoming queue
549 for ( m = m->lm_chain; m != NULL; m = m->lm_chain ) {
550 if (( new = msg_dup( m )) == NULL ) {
554 new->lm_msgid = ld->ld_msgid;
555 new->lm_chain = NULL;
557 new->lm_next = ld->ld_responses;
558 ld->ld_responses = new;
561 prev->lm_chain = new;
565 LDAP_LOG ( CACHE, DETAIL1, "ldap_check_cache: added type %ld\n",
566 (long) m->lm_msgtype, 0, 0 );
568 Debug( LDAP_DEBUG_TRACE, "cc: added type %ld\n",
569 (long) new->lm_msgtype, 0, 0 );
574 LDAP_LOG ( CACHE, RESULTS,
575 "ldap_check_cache: result returned from cache\n", 0, 0, 0 );
577 Debug( LDAP_DEBUG_TRACE, "cc: result returned from cache\n", 0, 0, 0 );
588 cache_hash( BerElement *ber )
594 * just take the length of the packet and mod with # of buckets
597 if ( ber_skip_tag( &bercpy, &len ) == LBER_ERROR
598 || ber_scanf( &bercpy, "x" ) == LBER_ERROR ) {
599 len = 0; /* punt: just return zero */
601 len = bercpy.ber_end - bercpy.ber_ptr;
605 LDAP_LOG ( CACHE, RESULTS, "cache_hash: len is %ld, returning %ld\n",
606 len, len % LDAP_CACHE_BUCKETS, 0 );
608 Debug( LDAP_DEBUG_TRACE, "cache_hash: len is %ld, returning %ld\n",
609 len, len % LDAP_CACHE_BUCKETS, 0 );
611 return( (int) ( len % LDAP_CACHE_BUCKETS ));
616 msg_dup( LDAPMessage *msg )
621 if (( new = (LDAPMessage *)LDAP_MALLOC( sizeof(LDAPMessage))) != NULL ) {
622 *new = *msg; /* struct copy */
623 if (( new->lm_ber = ber_dup( msg->lm_ber )) == NULL ) {
624 LDAP_FREE( (char *)new );
627 len = msg->lm_ber->ber_end - msg->lm_ber->ber_buf;
628 if (( new->lm_ber->ber_buf = (char *) ber_memalloc(
629 (size_t)len )) == NULL ) {
630 ber_free( new->lm_ber, 0 );
631 LDAP_FREE( (char *)new );
634 AC_MEMCPY( new->lm_ber->ber_buf, msg->lm_ber->ber_buf,
636 new->lm_ber->ber_ptr = new->lm_ber->ber_buf +
637 ( msg->lm_ber->ber_ptr - msg->lm_ber->ber_buf );
638 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
646 request_cmp( BerElement *req1, BerElement *req2 )
651 r1 = *req1; /* struct copies */
655 * skip the enclosing tags (sequence markers) and the msg ids
657 if ( ber_skip_tag( &r1, &len ) == LBER_ERROR || ber_scanf( &r1, "x" )
661 if ( ber_skip_tag( &r2, &len ) == LBER_ERROR || ber_scanf( &r2, "x" )
667 * check remaining length and bytes if necessary
669 if (( len = r1.ber_end - r1.ber_ptr ) !=
670 (ber_len_t) (r2.ber_end - r2.ber_ptr) )
672 return( -1 ); /* different lengths */
674 return( memcmp( r1.ber_ptr, r2.ber_ptr, (size_t)len ));
679 chain_contains_dn( LDAPMessage *msg, const char *dn )
689 * first check the base or dn of the request
691 ber = *msg->lm_ber; /* struct copy */
692 if ( ber_scanf( &ber, "{i{a" /*}}*/, &msgid, &s ) != LBER_ERROR ) {
693 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
700 if ( msg->lm_msgtype == LDAP_REQ_COMPARE ) {
705 * now check the dn of each search result
708 for ( m = msg->lm_chain; m != NULL && rc == 0 ; m = m->lm_chain ) {
709 if ( m->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
712 ber = *m->lm_ber; /* struct copy */
713 if ( ber_scanf( &ber, "{a" /*}*/, &s ) != LBER_ERROR ) {
714 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
724 msg_size( LDAPMessage *msg )
730 for ( m = msg; m != NULL; m = m->lm_chain ) {
731 size += ( sizeof( LDAPMessage ) + m->lm_ber->ber_end -
732 m->lm_ber->ber_buf );
739 #define THRESHOLD_FACTOR 3 / 4
740 #define SIZE_FACTOR 2 / 3
743 check_cache_memused( LDAPCache *lc )
746 * this routine is called to check if the cache is too big (lc_maxmem >
747 * minimum cache size and lc_memused > lc_maxmem). If too big, it reduces
748 * the cache size to < SIZE_FACTOR * lc_maxmem. The algorithm is as follows:
749 * remove_threshold = lc_timeout seconds;
751 * remove everything older than remove_threshold seconds;
752 * remove_threshold = remove_threshold * THRESHOLD_FACTOR;
753 * } while ( cache size is > SIZE_FACTOR * lc_maxmem )
756 unsigned long remove_threshold;
758 LDAPMessage *m, *prev, *next;
761 LDAP_LOG ( CACHE, DETAIL1,
762 "check_cache_memused: %ld bytes in use (%ld max)\n",
763 lc->lc_memused, lc->lc_maxmem, 0 );
765 Debug( LDAP_DEBUG_TRACE, "check_cache_memused: %ld bytes in use (%ld max)\n",
766 lc->lc_memused, lc->lc_maxmem, 0 );
769 if ( (unsigned) lc->lc_maxmem <= sizeof( LDAPCache )
770 || lc->lc_memused <= lc->lc_maxmem * SIZE_FACTOR ) {
774 remove_threshold = lc->lc_timeout;
775 while ( lc->lc_memused > lc->lc_maxmem * SIZE_FACTOR ) {
776 c_time = time( NULL );
777 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
779 for ( m = lc->lc_buckets[ i ]; m != NULL;
782 if ( difftime(c_time, m->lm_time) > remove_threshold) {
783 if ( prev == NULL ) {
784 lc->lc_buckets[ i ] = next;
786 prev->lm_next = next;
788 lc->lc_memused -= msg_size( m );
790 LDAP_LOG ( CACHE, DETAIL1,
791 "check_cache_memused: removed %ld\n", m->lm_msgid,0,0 );
793 Debug( LDAP_DEBUG_TRACE,
803 remove_threshold *= THRESHOLD_FACTOR;
807 LDAP_LOG ( CACHE, DETAIL1,
808 "check_cache_memused: reduced usage to %ld bytes\n",
809 lc->lc_memused, 0, 0 );
811 Debug( LDAP_DEBUG_TRACE, "ccm: reduced usage to %ld bytes\n",
812 lc->lc_memused, 0, 0 );
816 #endif /* !NO_CACHE */