2 * Copyright 1998-1999 The OpenLDAP Foundation, All Rights Reserved.
3 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
6 * Copyright (c) 1993 The Regents of the University of Michigan.
9 * cache.c - local caching support for LDAP
16 #include <ac/stdlib.h>
18 #include <ac/socket.h>
19 #include <ac/string.h>
26 static int cache_hash LDAP_P(( BerElement *ber ));
27 static LDAPMessage *msg_dup LDAP_P(( LDAPMessage *msg ));
28 static int request_cmp LDAP_P(( BerElement *req1, BerElement *req2 ));
29 static int chain_contains_dn LDAP_P(( LDAPMessage *msg, LDAP_CONST char *dn ));
30 static ber_len_t msg_size LDAP_P(( LDAPMessage *msg ));
31 static void check_cache_memused LDAP_P(( LDAPCache *lc ));
32 static void uncache_entry_or_req LDAP_P(( LDAP *ld, LDAP_CONST char *dn, ber_int_t msgid ));
37 ldap_enable_cache( LDAP *ld, long timeout, ber_len_t maxmem )
40 if ( ld->ld_cache == NULL ) {
41 if (( ld->ld_cache = (LDAPCache *)LDAP_MALLOC( sizeof( LDAPCache )))
43 ld->ld_errno = LDAP_NO_MEMORY;
46 (void) memset( ld->ld_cache, 0, sizeof( LDAPCache ));
47 ld->ld_cache->lc_memused = sizeof( LDAPCache );
50 ld->ld_cache->lc_timeout = timeout;
51 ld->ld_cache->lc_maxmem = maxmem;
52 check_cache_memused( ld->ld_cache );
53 ld->ld_cache->lc_enabled = 1;
62 ldap_disable_cache( LDAP *ld )
65 if ( ld->ld_cache != NULL ) {
66 ld->ld_cache->lc_enabled = 0;
74 ldap_set_cache_options( LDAP *ld, unsigned long opts )
77 if ( ld->ld_cache != NULL ) {
78 ld->ld_cache->lc_options = opts;
85 ldap_destroy_cache( LDAP *ld )
88 if ( ld->ld_cache != NULL ) {
89 ldap_flush_cache( ld );
90 LDAP_FREE( (char *)ld->ld_cache );
98 ldap_flush_cache( LDAP *ld )
102 LDAPMessage *m, *next;
104 Debug( LDAP_DEBUG_TRACE, "ldap_flush_cache\n", 0, 0, 0 );
106 if ( ld->ld_cache != NULL ) {
107 /* delete all requests in the queue */
108 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
112 ld->ld_cache->lc_requests = NULL;
114 /* delete all messages in the cache */
115 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
116 for ( m = ld->ld_cache->lc_buckets[ i ];
117 m != NULL; m = next ) {
121 ld->ld_cache->lc_buckets[ i ] = NULL;
123 ld->ld_cache->lc_memused = sizeof( LDAPCache );
130 ldap_uncache_request( LDAP *ld, int msgid )
133 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_request %d ld_cache %lx\n",
134 msgid, (long) ld->ld_cache, 0 );
136 uncache_entry_or_req( ld, NULL, msgid );
142 ldap_uncache_entry( LDAP *ld, LDAP_CONST char *dn )
145 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_entry %s ld_cache %lx\n",
146 dn, (long) ld->ld_cache, 0 );
148 uncache_entry_or_req( ld, dn, 0 );
156 uncache_entry_or_req( LDAP *ld,
157 const char *dn, /* if non-NULL, uncache entry */
158 ber_int_t msgid ) /* request to uncache (if dn == NULL) */
161 LDAPMessage *m, *prev, *next;
163 Debug( LDAP_DEBUG_TRACE,
164 "ldap_uncache_entry_or_req dn %s msgid %ld ld_cache %lx\n",
165 dn, (long) msgid, (long) ld->ld_cache );
167 if ( ld->ld_cache == NULL ) {
171 /* first check the request queue */
173 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
175 if (( dn != NULL && chain_contains_dn( m, dn )) ||
176 ( dn == NULL && m->lm_msgid == msgid )) {
177 if ( prev == NULL ) {
178 ld->ld_cache->lc_requests = next;
180 prev->lm_next = next;
182 ld->ld_cache->lc_memused -= msg_size( m );
189 /* now check the rest of the cache */
190 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
192 for ( m = ld->ld_cache->lc_buckets[ i ]; m != NULL;
195 if (( dn != NULL && chain_contains_dn( m, dn )) ||
196 ( dn == NULL && m->lm_msgid == msgid )) {
197 if ( prev == NULL ) {
198 ld->ld_cache->lc_buckets[ i ] = next;
200 prev->lm_next = next;
202 ld->ld_cache->lc_memused -= msg_size( m );
214 ldap_add_request_to_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
220 Debug( LDAP_DEBUG_TRACE, "ldap_add_request_to_cache\n", 0, 0, 0 );
222 ld->ld_errno = LDAP_SUCCESS;
223 if ( ld->ld_cache == NULL ||
224 ( ld->ld_cache->lc_enabled == 0 )) {
228 if (( new = (LDAPMessage *) LDAP_CALLOC( 1, sizeof(LDAPMessage) ))
230 if (( new->lm_ber = ldap_alloc_ber_with_options( ld )) == NULL ) {
231 LDAP_FREE( (char *)new );
234 len = request->ber_ptr - request->ber_buf;
235 if (( new->lm_ber->ber_buf = (char *) ber_memalloc( (size_t)len ))
237 ber_free( new->lm_ber, 0 );
238 LDAP_FREE( (char *)new );
239 ld->ld_errno = LDAP_NO_MEMORY;
242 SAFEMEMCPY( new->lm_ber->ber_buf, request->ber_buf,
244 new->lm_ber->ber_ptr = new->lm_ber->ber_buf;
245 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
246 new->lm_msgid = ld->ld_msgid;
247 new->lm_msgtype = msgtype;;
248 new->lm_next = ld->ld_cache->lc_requests;
249 ld->ld_cache->lc_requests = new;
251 ld->ld_errno = LDAP_NO_MEMORY;
258 ldap_add_result_to_cache( LDAP *ld, LDAPMessage *result )
261 LDAPMessage *m, **mp, *req, *new, *prev;
264 Debug( LDAP_DEBUG_TRACE, "ldap_add_result_to_cache: id %d, type %d\n",
265 result->lm_msgid, result->lm_msgtype, 0 );
267 if ( ld->ld_cache == NULL ||
268 ( ld->ld_cache->lc_enabled == 0 )) {
269 Debug( LDAP_DEBUG_TRACE, "artc: cache disabled\n", 0, 0, 0 );
273 if ( result->lm_msgtype != LDAP_RES_SEARCH_ENTRY &&
274 result->lm_msgtype != LDAP_RES_SEARCH_REFERENCE &&
275 result->lm_msgtype != LDAP_RES_SEARCH_RESULT &&
276 result->lm_msgtype != LDAP_RES_COMPARE ) {
278 * only cache search and compare operations
280 Debug( LDAP_DEBUG_TRACE,
281 "artc: only caching search & compare operations\n", 0, 0, 0 );
286 * if corresponding request is in the lc_requests list, add this
287 * result to it. if this result completes the results for the
288 * request, add the request/result chain to the cache proper.
291 for ( m = ld->ld_cache->lc_requests; m != NULL; m = m->lm_next ) {
292 if ( m->lm_msgid == result->lm_msgid ) {
298 if ( m != NULL ) { /* found request; add to end of chain */
300 for ( ; m->lm_chain != NULL; m = m->lm_chain )
302 if (( new = msg_dup( result )) != NULL ) {
303 new->lm_chain = NULL;
305 Debug( LDAP_DEBUG_TRACE,
306 "artc: result added to cache request chain\n",
309 if ( result->lm_msgtype == LDAP_RES_SEARCH_RESULT ||
310 result->lm_msgtype == LDAP_RES_COMPARE ) {
312 * this result completes the chain of results
313 * add to cache proper if appropriate
315 keep = 0; /* pessimistic */
316 err = ldap_result2error( ld, result, 0 );
317 if ( err == LDAP_SUCCESS ||
318 ( result->lm_msgtype == LDAP_RES_COMPARE &&
319 ( err == LDAP_COMPARE_FALSE ||
320 err == LDAP_COMPARE_TRUE ||
321 err == LDAP_NO_SUCH_ATTRIBUTE ))) {
325 if ( ld->ld_cache->lc_options == 0 ) {
326 if ( err == LDAP_SIZELIMIT_EXCEEDED ) {
329 } else if (( ld->ld_cache->lc_options &
330 LDAP_CACHE_OPT_CACHEALLERRS ) != 0 ) {
334 if ( prev == NULL ) {
335 ld->ld_cache->lc_requests = req->lm_next;
337 prev->lm_next = req->lm_next;
341 Debug( LDAP_DEBUG_TRACE,
342 "artc: not caching result with error %d\n",
346 mp = &ld->ld_cache->lc_buckets[
347 cache_hash( req->lm_ber ) ];
350 req->lm_time = (long) time( NULL );
351 ld->ld_cache->lc_memused += msg_size( req );
352 check_cache_memused( ld->ld_cache );
353 Debug( LDAP_DEBUG_TRACE,
354 "artc: cached result with error %d\n",
359 Debug( LDAP_DEBUG_TRACE, "artc: msgid not in request list\n",
367 * look in the cache for this request
368 * return 0 if found, -1 if not
369 * if found, the corresponding result messages are added to the incoming
370 * queue with the correct (new) msgid so that subsequent ldap_result calls
374 ldap_check_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
377 LDAPMessage *m, *new, *prev, *next;
382 Debug( LDAP_DEBUG_TRACE, "ldap_check_cache\n", 0, 0, 0 );
384 if ( ld->ld_cache == NULL ||
385 ( ld->ld_cache->lc_enabled == 0 )) {
389 reqber.ber_buf = reqber.ber_ptr = request->ber_buf;
390 reqber.ber_end = request->ber_ptr;
392 c_time = time( NULL );
395 hash = cache_hash( &reqber );
396 for ( m = ld->ld_cache->lc_buckets[ hash ]; m != NULL; m = next ) {
397 Debug( LDAP_DEBUG_TRACE,"cc: examining id %d,type %d\n",
398 m->lm_msgid, m->lm_msgtype, 0 );
399 if ( difftime(c_time, m->lm_time) > ld->ld_cache->lc_timeout ) {
400 /* delete expired message */
402 if ( prev == NULL ) {
403 ld->ld_cache->lc_buckets[ hash ] = next;
405 prev->lm_next = next;
407 Debug( LDAP_DEBUG_TRACE, "cc: expired id %d\n",
409 ld->ld_cache->lc_memused -= msg_size( m );
412 if ( m->lm_msgtype == (int)msgtype &&
413 request_cmp( m->lm_ber, &reqber ) == 0 ) {
426 * add duplicates of responses to incoming queue
429 for ( m = m->lm_chain; m != NULL; m = m->lm_chain ) {
430 if (( new = msg_dup( m )) == NULL ) {
434 new->lm_msgid = ld->ld_msgid;
435 new->lm_chain = NULL;
437 new->lm_next = ld->ld_responses;
438 ld->ld_responses = new;
441 prev->lm_chain = new;
444 Debug( LDAP_DEBUG_TRACE, "cc: added type %d\n",
445 new->lm_msgtype, 0, 0 );
448 Debug( LDAP_DEBUG_TRACE, "cc: result returned from cache\n", 0, 0, 0 );
458 cache_hash( BerElement *ber )
464 * just take the length of the packet and mod with # of buckets
467 if ( ber_skip_tag( &bercpy, &len ) == LBER_ERROR
468 || ber_scanf( &bercpy, "x" ) == LBER_ERROR ) {
469 len = 0; /* punt: just return zero */
471 len = bercpy.ber_end - bercpy.ber_ptr;
474 Debug( LDAP_DEBUG_TRACE, "cache_hash: len is %ld, returning %ld\n",
475 len, len % LDAP_CACHE_BUCKETS, 0 );
476 return( (int) ( len % LDAP_CACHE_BUCKETS ));
481 msg_dup( LDAPMessage *msg )
486 if (( new = (LDAPMessage *)LDAP_MALLOC( sizeof(LDAPMessage))) != NULL ) {
487 *new = *msg; /* struct copy */
488 if (( new->lm_ber = ber_dup( msg->lm_ber )) == NULL ) {
489 LDAP_FREE( (char *)new );
492 len = msg->lm_ber->ber_end - msg->lm_ber->ber_buf;
493 if (( new->lm_ber->ber_buf = (char *) ber_memalloc(
494 (size_t)len )) == NULL ) {
495 ber_free( new->lm_ber, 0 );
496 LDAP_FREE( (char *)new );
499 SAFEMEMCPY( new->lm_ber->ber_buf, msg->lm_ber->ber_buf,
501 new->lm_ber->ber_ptr = new->lm_ber->ber_buf +
502 ( msg->lm_ber->ber_ptr - msg->lm_ber->ber_buf );
503 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
511 request_cmp( BerElement *req1, BerElement *req2 )
516 r1 = *req1; /* struct copies */
520 * skip the enclosing tags (sequence markers) and the msg ids
522 if ( ber_skip_tag( &r1, &len ) == LBER_ERROR || ber_scanf( &r1, "x" )
526 if ( ber_skip_tag( &r2, &len ) == LBER_ERROR || ber_scanf( &r2, "x" )
532 * check remaining length and bytes if necessary
534 if (( len = r1.ber_end - r1.ber_ptr ) !=
535 (ber_len_t) (r2.ber_end - r2.ber_ptr) )
537 return( -1 ); /* different lengths */
539 return( memcmp( r1.ber_ptr, r2.ber_ptr, (size_t)len ));
544 chain_contains_dn( LDAPMessage *msg, const char *dn )
554 * first check the base or dn of the request
556 ber = *msg->lm_ber; /* struct copy */
557 if ( ber_scanf( &ber, "{i{a" /*}}*/, &msgid, &s ) != LBER_ERROR ) {
558 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
565 if ( msg->lm_msgtype == LDAP_REQ_COMPARE ) {
570 * now check the dn of each search result
573 for ( m = msg->lm_chain; m != NULL && rc == 0 ; m = m->lm_chain ) {
574 if ( m->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
577 ber = *m->lm_ber; /* struct copy */
578 if ( ber_scanf( &ber, "{a" /*}*/, &s ) != LBER_ERROR ) {
579 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
589 msg_size( LDAPMessage *msg )
595 for ( m = msg; m != NULL; m = m->lm_chain ) {
596 size += ( sizeof( LDAPMessage ) + m->lm_ber->ber_end -
597 m->lm_ber->ber_buf );
604 #define THRESHOLD_FACTOR 3 / 4
605 #define SIZE_FACTOR 2 / 3
608 check_cache_memused( LDAPCache *lc )
611 * this routine is called to check if the cache is too big (lc_maxmem >
612 * minimum cache size and lc_memused > lc_maxmem). If too big, it reduces
613 * the cache size to < SIZE_FACTOR * lc_maxmem. The algorithm is as follows:
614 * remove_threshold = lc_timeout seconds;
616 * remove everything older than remove_threshold seconds;
617 * remove_threshold = remove_threshold * THRESHOLD_FACTOR;
618 * } while ( cache size is > SIZE_FACTOR * lc_maxmem )
621 unsigned long remove_threshold;
623 LDAPMessage *m, *prev, *next;
625 Debug( LDAP_DEBUG_TRACE, "check_cache_memused: %ld bytes in use (%ld max)\n",
626 lc->lc_memused, lc->lc_maxmem, 0 );
628 if ( (unsigned) lc->lc_maxmem <= sizeof( LDAPCache )
629 || lc->lc_memused <= lc->lc_maxmem * SIZE_FACTOR ) {
633 remove_threshold = lc->lc_timeout;
634 while ( lc->lc_memused > lc->lc_maxmem * SIZE_FACTOR ) {
635 c_time = time( NULL );
636 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
638 for ( m = lc->lc_buckets[ i ]; m != NULL;
641 if ( difftime(c_time, m->lm_time) > remove_threshold) {
642 if ( prev == NULL ) {
643 lc->lc_buckets[ i ] = next;
645 prev->lm_next = next;
647 lc->lc_memused -= msg_size( m );
648 Debug( LDAP_DEBUG_TRACE,
657 remove_threshold *= THRESHOLD_FACTOR;
660 Debug( LDAP_DEBUG_TRACE, "ccm: reduced usage to %ld bytes\n",
661 lc->lc_memused, 0, 0 );
664 #endif /* !NO_CACHE */