2 * Copyright (c) 1993 The Regents of the University of Michigan.
5 * cache.c - local caching support for LDAP
11 static char copyright[] = "@(#) Copyright (c) 1993 The Regents of the University of Michigan.\nAll rights reserved.\n";
21 #if defined( DOS ) || defined( _WIN32 )
31 #include <sys/types.h>
32 #include <sys/socket.h>
40 static int cache_hash( BerElement *ber );
41 static LDAPMessage *msg_dup( LDAPMessage *msg );
42 static int request_cmp( BerElement *req1, BerElement *req2 );
43 static int chain_contains_dn( LDAPMessage *msg, char *dn );
44 static long msg_size( LDAPMessage *msg );
45 static void check_cache_memused( LDAPCache *lc );
46 static void uncache_entry_or_req( LDAP *ld, char *dn, int msgid );
47 #else /* NEEDPROTOS */
48 static int cache_hash();
49 static LDAPMessage *msg_dup();
50 static int request_cmp();
51 static int chain_contains_dn();
52 static long msg_size();
53 static void check_cache_memused();
54 static void uncache_entry_or_req();
55 #endif /* NEEDPROTOS */
59 ldap_enable_cache( LDAP *ld, long timeout, long maxmem )
61 if ( ld->ld_cache == NULLLDCACHE ) {
62 if (( ld->ld_cache = (LDAPCache *)malloc( sizeof( LDAPCache )))
64 ld->ld_errno = LDAP_NO_MEMORY;
67 (void) memset( ld->ld_cache, 0, sizeof( LDAPCache ));
68 ld->ld_cache->lc_memused = sizeof( LDAPCache );
71 ld->ld_cache->lc_timeout = timeout;
72 ld->ld_cache->lc_maxmem = maxmem;
73 check_cache_memused( ld->ld_cache );
74 ld->ld_cache->lc_enabled = 1;
80 ldap_disable_cache( LDAP *ld )
82 if ( ld->ld_cache != NULLLDCACHE ) {
83 ld->ld_cache->lc_enabled = 0;
90 ldap_set_cache_options( LDAP *ld, unsigned long opts )
92 if ( ld->ld_cache != NULLLDCACHE ) {
93 ld->ld_cache->lc_options = opts;
99 ldap_destroy_cache( LDAP *ld )
101 if ( ld->ld_cache != NULLLDCACHE ) {
102 ldap_flush_cache( ld );
103 free( (char *)ld->ld_cache );
104 ld->ld_cache = NULLLDCACHE;
110 ldap_flush_cache( LDAP *ld )
113 LDAPMessage *m, *next;
115 Debug( LDAP_DEBUG_TRACE, "ldap_flush_cache\n", 0, 0, 0 );
117 if ( ld->ld_cache != NULLLDCACHE ) {
118 /* delete all requests in the queue */
119 for ( m = ld->ld_cache->lc_requests; m != NULLMSG; m = next ) {
123 ld->ld_cache->lc_requests = NULLMSG;
125 /* delete all messages in the cache */
126 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
127 for ( m = ld->ld_cache->lc_buckets[ i ];
128 m != NULLMSG; m = next ) {
132 ld->ld_cache->lc_buckets[ i ] = NULLMSG;
134 ld->ld_cache->lc_memused = sizeof( LDAPCache );
140 ldap_uncache_request( LDAP *ld, int msgid )
142 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_request %d ld_cache %x\n",
143 msgid, ld->ld_cache, 0 );
145 uncache_entry_or_req( ld, NULL, msgid );
150 ldap_uncache_entry( LDAP *ld, char *dn )
152 Debug( LDAP_DEBUG_TRACE, "ldap_uncache_entry %s ld_cache %x\n",
153 dn, ld->ld_cache, 0 );
155 uncache_entry_or_req( ld, dn, 0 );
160 uncache_entry_or_req( LDAP *ld,
161 char *dn, /* if non-NULL, uncache entry */
162 int msgid ) /* request to uncache (if dn == NULL) */
165 LDAPMessage *m, *prev, *next;
167 Debug( LDAP_DEBUG_TRACE,
168 "ldap_uncache_entry_or_req dn %s msgid %d ld_cache %x\n",
169 dn, msgid, ld->ld_cache );
171 if ( ld->ld_cache == NULLLDCACHE ) {
175 /* first check the request queue */
177 for ( m = ld->ld_cache->lc_requests; m != NULLMSG; m = next ) {
179 if (( dn != NULL && chain_contains_dn( m, dn )) ||
180 ( dn == NULL && m->lm_msgid == msgid )) {
181 if ( prev == NULLMSG ) {
182 ld->ld_cache->lc_requests = next;
184 prev->lm_next = next;
186 ld->ld_cache->lc_memused -= msg_size( m );
193 /* now check the rest of the cache */
194 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
196 for ( m = ld->ld_cache->lc_buckets[ i ]; m != NULLMSG;
199 if (( dn != NULL && chain_contains_dn( m, dn )) ||
200 ( dn == NULL && m->lm_msgid == msgid )) {
201 if ( prev == NULLMSG ) {
202 ld->ld_cache->lc_buckets[ i ] = next;
204 prev->lm_next = next;
206 ld->ld_cache->lc_memused -= msg_size( m );
217 add_request_to_cache( LDAP *ld, unsigned long msgtype, BerElement *request )
222 Debug( LDAP_DEBUG_TRACE, "add_request_to_cache\n", 0, 0, 0 );
224 ld->ld_errno = LDAP_SUCCESS;
225 if ( ld->ld_cache == NULLLDCACHE ||
226 ( ld->ld_cache->lc_enabled == 0 )) {
230 if (( new = (LDAPMessage *) calloc( 1, sizeof(LDAPMessage) ))
232 if (( new->lm_ber = alloc_ber_with_options( ld )) == NULLBER ) {
236 len = request->ber_ptr - request->ber_buf;
237 if (( new->lm_ber->ber_buf = (char *) malloc( (size_t)len ))
239 ber_free( new->lm_ber, 0 );
241 ld->ld_errno = LDAP_NO_MEMORY;
244 SAFEMEMCPY( new->lm_ber->ber_buf, request->ber_buf,
246 new->lm_ber->ber_ptr = new->lm_ber->ber_buf;
247 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
248 new->lm_msgid = ld->ld_msgid;
249 new->lm_msgtype = msgtype;;
250 new->lm_next = ld->ld_cache->lc_requests;
251 ld->ld_cache->lc_requests = new;
253 ld->ld_errno = LDAP_NO_MEMORY;
259 add_result_to_cache( LDAP *ld, LDAPMessage *result )
261 LDAPMessage *m, **mp, *req, *new, *prev;
264 Debug( LDAP_DEBUG_TRACE, "add_result_to_cache: id %d, type %d\n",
265 result->lm_msgid, result->lm_msgtype, 0 );
267 if ( ld->ld_cache == NULLLDCACHE ||
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_RESULT &&
275 result->lm_msgtype != LDAP_RES_COMPARE ) {
277 * only cache search and compare operations
279 Debug( LDAP_DEBUG_TRACE,
280 "artc: only caching search & compare operations\n", 0, 0, 0 );
285 * if corresponding request is in the lc_requests list, add this
286 * result to it. if this result completes the results for the
287 * request, add the request/result chain to the cache proper.
290 for ( m = ld->ld_cache->lc_requests; m != NULL; m = m->lm_next ) {
291 if ( m->lm_msgid == result->lm_msgid ) {
297 if ( m != NULLMSG ) { /* found request; add to end of chain */
299 for ( ; m->lm_chain != NULLMSG; m = m->lm_chain )
301 if (( new = msg_dup( result )) != NULLMSG ) {
302 new->lm_chain = NULLMSG;
304 Debug( LDAP_DEBUG_TRACE,
305 "artc: result added to cache request chain\n",
308 if ( result->lm_msgtype == LDAP_RES_SEARCH_RESULT ||
309 result->lm_msgtype == LDAP_RES_COMPARE ) {
311 * this result completes the chain of results
312 * add to cache proper if appropriate
314 keep = 0; /* pessimistic */
315 err = ldap_result2error( ld, result, 0 );
316 if ( err == LDAP_SUCCESS ||
317 ( result->lm_msgtype == LDAP_RES_COMPARE &&
318 ( err == LDAP_COMPARE_FALSE ||
319 err == LDAP_COMPARE_TRUE ||
320 err == LDAP_NO_SUCH_ATTRIBUTE ))) {
324 if ( ld->ld_cache->lc_options == 0 ) {
325 if ( err == LDAP_SIZELIMIT_EXCEEDED ) {
328 } else if (( ld->ld_cache->lc_options &
329 LDAP_CACHE_OPT_CACHEALLERRS ) != 0 ) {
333 if ( prev == NULLMSG ) {
334 ld->ld_cache->lc_requests = req->lm_next;
336 prev->lm_next = req->lm_next;
340 Debug( LDAP_DEBUG_TRACE,
341 "artc: not caching result with error %d\n",
345 mp = &ld->ld_cache->lc_buckets[
346 cache_hash( req->lm_ber ) ];
349 req->lm_time = (long) time( NULL );
350 ld->ld_cache->lc_memused += msg_size( req );
351 check_cache_memused( ld->ld_cache );
352 Debug( LDAP_DEBUG_TRACE,
353 "artc: cached result with error %d\n",
358 Debug( LDAP_DEBUG_TRACE, "artc: msgid not in request list\n",
365 * look in the cache for this request
366 * return 0 if found, -1 if not
367 * if found, the corresponding result messages are added to the incoming
368 * queue with the correct (new) msgid so that subsequent ldap_result calls
372 check_cache( LDAP *ld, unsigned long msgtype, BerElement *request )
374 LDAPMessage *m, *new, *prev, *next;
377 unsigned long validtime;
379 Debug( LDAP_DEBUG_TRACE, "check_cache\n", 0, 0, 0 );
381 if ( ld->ld_cache == NULLLDCACHE ||
382 ( ld->ld_cache->lc_enabled == 0 )) {
386 reqber.ber_buf = reqber.ber_ptr = request->ber_buf;
387 reqber.ber_end = request->ber_ptr;
389 validtime = (long)time( NULL ) - ld->ld_cache->lc_timeout;
392 hash = cache_hash( &reqber );
393 for ( m = ld->ld_cache->lc_buckets[ hash ]; m != NULLMSG; m = next ) {
394 Debug( LDAP_DEBUG_TRACE,"cc: examining id %d,type %d\n",
395 m->lm_msgid, m->lm_msgtype, 0 );
396 if ( m->lm_time < validtime ) {
397 /* delete expired message */
399 if ( prev == NULL ) {
400 ld->ld_cache->lc_buckets[ hash ] = next;
402 prev->lm_next = next;
404 Debug( LDAP_DEBUG_TRACE, "cc: expired id %d\n",
406 ld->ld_cache->lc_memused -= msg_size( m );
409 if ( m->lm_msgtype == (int)msgtype &&
410 request_cmp( m->lm_ber, &reqber ) == 0 ) {
418 if ( m == NULLMSG ) {
423 * add duplicates of responses to incoming queue
426 for ( m = m->lm_chain; m != NULLMSG; m = m->lm_chain ) {
427 if (( new = msg_dup( m )) == NULLMSG ) {
431 new->lm_msgid = ld->ld_msgid;
432 new->lm_chain = NULLMSG;
434 new->lm_next = ld->ld_responses;
435 ld->ld_responses = new;
438 prev->lm_chain = new;
441 Debug( LDAP_DEBUG_TRACE, "cc: added type %d\n",
442 new->lm_msgtype, 0, 0 );
445 Debug( LDAP_DEBUG_TRACE, "cc: result returned from cache\n", 0, 0, 0 );
451 cache_hash( BerElement *ber )
457 * just take the length of the packet and mod with # of buckets
460 if ( ber_skip_tag( &bercpy, &len ) == LBER_ERROR
461 || ber_scanf( &bercpy, "x" ) == LBER_ERROR ) {
462 len = 0; /* punt: just return zero */
464 len = bercpy.ber_end - bercpy.ber_ptr;
467 Debug( LDAP_DEBUG_TRACE, "cache_hash: len is %ld, returning %ld\n",
468 len, len % LDAP_CACHE_BUCKETS, 0 );
469 return( (int) ( len % LDAP_CACHE_BUCKETS ));
474 msg_dup( LDAPMessage *msg )
479 if (( new = (LDAPMessage *)malloc( sizeof(LDAPMessage))) != NULL ) {
480 *new = *msg; /* struct copy */
481 if (( new->lm_ber = ber_dup( msg->lm_ber )) == NULLBER ) {
485 len = msg->lm_ber->ber_end - msg->lm_ber->ber_buf;
486 if (( new->lm_ber->ber_buf = (char *) malloc(
487 (size_t)len )) == NULL ) {
488 ber_free( new->lm_ber, 0 );
492 SAFEMEMCPY( new->lm_ber->ber_buf, msg->lm_ber->ber_buf,
494 new->lm_ber->ber_ptr = new->lm_ber->ber_buf +
495 ( msg->lm_ber->ber_ptr - msg->lm_ber->ber_buf );
496 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
504 request_cmp( BerElement *req1, BerElement *req2 )
509 r1 = *req1; /* struct copies */
513 * skip the enclosing tags (sequence markers) and the msg ids
515 if ( ber_skip_tag( &r1, &len ) == LBER_ERROR || ber_scanf( &r1, "x" )
519 if ( ber_skip_tag( &r2, &len ) == LBER_ERROR || ber_scanf( &r2, "x" )
525 * check remaining length and bytes if necessary
527 if (( len = r1.ber_end - r1.ber_ptr ) != r2.ber_end - r2.ber_ptr ) {
528 return( -1 ); /* different lengths */
530 return( memcmp( r1.ber_ptr, r2.ber_ptr, (size_t)len ));
535 chain_contains_dn( LDAPMessage *msg, char *dn )
545 * first check the base or dn of the request
547 ber = *msg->lm_ber; /* struct copy */
548 if ( ber_scanf( &ber, "{i{a", &msgid, &s ) != LBER_ERROR ) {
549 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
556 if ( msg->lm_msgtype == LDAP_REQ_COMPARE ) {
561 * now check the dn of each search result
564 for ( m = msg->lm_chain; m != NULLMSG && rc == 0 ; m = m->lm_chain ) {
565 if ( m->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
568 ber = *m->lm_ber; /* struct copy */
569 if ( ber_scanf( &ber, "{a", &s ) != LBER_ERROR ) {
570 rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
580 msg_size( LDAPMessage *msg )
586 for ( m = msg; m != NULLMSG; m = m->lm_chain ) {
587 size += ( sizeof( LDAPMessage ) + m->lm_ber->ber_end -
588 m->lm_ber->ber_buf );
595 #define THRESHOLD_FACTOR 3 / 4
596 #define SIZE_FACTOR 2 / 3
599 check_cache_memused( LDAPCache *lc )
602 * this routine is called to check if the cache is too big (lc_maxmem >
603 * minimum cache size and lc_memused > lc_maxmem). If too big, it reduces
604 * the cache size to < SIZE_FACTOR * lc_maxmem. The algorithm is as follows:
605 * remove_threshold = lc_timeout seconds;
607 * remove everything older than remove_threshold seconds;
608 * remove_threshold = remove_threshold * THRESHOLD_FACTOR;
609 * } while ( cache size is > SIZE_FACTOR * lc_maxmem )
612 unsigned long remove_threshold, validtime;
613 LDAPMessage *m, *prev, *next;
615 Debug( LDAP_DEBUG_TRACE, "check_cache_memused: %ld bytes in use (%ld max)\n",
616 lc->lc_memused, lc->lc_maxmem, 0 );
618 if ( lc->lc_maxmem <= sizeof( LDAPCache )
619 || lc->lc_memused <= lc->lc_maxmem * SIZE_FACTOR ) {
623 remove_threshold = lc->lc_timeout;
624 while ( lc->lc_memused > lc->lc_maxmem * SIZE_FACTOR ) {
625 validtime = (long)time( NULL ) - remove_threshold;
626 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
628 for ( m = lc->lc_buckets[ i ]; m != NULLMSG;
631 if ( m->lm_time < validtime ) {
632 if ( prev == NULLMSG ) {
633 lc->lc_buckets[ i ] = next;
635 prev->lm_next = next;
637 lc->lc_memused -= msg_size( m );
638 Debug( LDAP_DEBUG_TRACE,
647 remove_threshold *= THRESHOLD_FACTOR;
650 Debug( LDAP_DEBUG_TRACE, "ccm: reduced usage to %ld bytes\n",
651 lc->lc_memused, 0, 0 );
654 #endif /* !NO_CACHE */