git.sur5r.net Git - openldap/blob - libraries/libldap/cache.c

   1 /*
   2  * Copyright 1998-1999 The OpenLDAP Foundation, All Rights Reserved.
   3  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   4  */
   5 /*  Portions
   6  *  Copyright (c) 1993 The Regents of the University of Michigan.
   7  *  All rights reserved.
   8  *
   9  *  cache.c - local caching support for LDAP
  10  */
  11
  12 #include "portable.h"
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16
  17 #include <ac/socket.h>
  18 #include <ac/string.h>
  19 #include <ac/time.h>
  20
  21 #include "ldap-int.h"
  22
  23 #ifndef LDAP_NOCACHE
  24
  25 static int              cache_hash LDAP_P(( BerElement *ber ));
  26 static LDAPMessage      *msg_dup LDAP_P(( LDAPMessage *msg ));
  27 static int              request_cmp LDAP_P(( BerElement *req1, BerElement *req2 ));
  28 static int              chain_contains_dn LDAP_P(( LDAPMessage *msg, LDAP_CONST char *dn ));
  29 static long             msg_size LDAP_P(( LDAPMessage *msg ));
  30 static void             check_cache_memused LDAP_P(( LDAPCache *lc ));
  31 static void             uncache_entry_or_req LDAP_P(( LDAP *ld, LDAP_CONST char *dn, int msgid ));
  32
  33 #endif
  34
  35 int
  36 ldap_enable_cache( LDAP *ld, long timeout, long maxmem )
  37 {
  38 #ifndef LDAP_NOCACHE
  39         if ( ld->ld_cache == NULLLDCACHE ) {
  40                 if (( ld->ld_cache = (LDAPCache *)malloc( sizeof( LDAPCache )))
  41                     == NULLLDCACHE ) {
  42                         ld->ld_errno = LDAP_NO_MEMORY;
  43                         return( -1 );
  44                 }
  45                 (void) memset( ld->ld_cache, 0, sizeof( LDAPCache ));
  46                 ld->ld_cache->lc_memused = sizeof( LDAPCache );
  47         }
  48
  49         ld->ld_cache->lc_timeout = timeout;
  50         ld->ld_cache->lc_maxmem = maxmem;
  51         check_cache_memused( ld->ld_cache );
  52         ld->ld_cache->lc_enabled = 1;
  53         return( 0 );
  54 #else
  55         return( -1 );
  56 #endif
  57 }
  58
  59
  60 void
  61 ldap_disable_cache( LDAP *ld )
  62 {
  63 #ifndef LDAP_NOCACHE
  64         if ( ld->ld_cache != NULLLDCACHE ) {
  65                 ld->ld_cache->lc_enabled = 0;
  66         }
  67 #endif
  68 }
  69
  70
  71
  72 void
  73 ldap_set_cache_options( LDAP *ld, unsigned long opts )
  74 {
  75 #ifndef LDAP_NOCACHE
  76         if ( ld->ld_cache != NULLLDCACHE ) {
  77                 ld->ld_cache->lc_options = opts;
  78         }
  79 #endif
  80 }
  81
  82
  83 void
  84 ldap_destroy_cache( LDAP *ld )
  85 {
  86 #ifndef LDAP_NOCACHE
  87         if ( ld->ld_cache != NULLLDCACHE ) {
  88                 ldap_flush_cache( ld );
  89                 free( (char *)ld->ld_cache );
  90                 ld->ld_cache = NULLLDCACHE;
  91         }
  92 #endif
  93 }
  94
  95
  96 void
  97 ldap_flush_cache( LDAP *ld )
  98 {
  99 #ifndef LDAP_NOCACHE
 100         int             i;
 101         LDAPMessage     *m, *next;
 102
 103         Debug( LDAP_DEBUG_TRACE, "ldap_flush_cache\n", 0, 0, 0 );
 104
 105         if ( ld->ld_cache != NULLLDCACHE ) {
 106                 /* delete all requests in the queue */
 107                 for ( m = ld->ld_cache->lc_requests; m != NULLMSG; m = next ) {
 108                         next = m->lm_next;
 109                         ldap_msgfree( m );
 110                 }
 111                 ld->ld_cache->lc_requests = NULLMSG;
 112
 113                 /* delete all messages in the cache */
 114                 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
 115                         for ( m = ld->ld_cache->lc_buckets[ i ];
 116                             m != NULLMSG; m = next ) {
 117                                 next = m->lm_next;
 118                                 ldap_msgfree( m );
 119                         }
 120                         ld->ld_cache->lc_buckets[ i ] = NULLMSG;
 121                 }
 122                 ld->ld_cache->lc_memused = sizeof( LDAPCache );
 123         }
 124 #endif
 125 }
 126
 127
 128 void
 129 ldap_uncache_request( LDAP *ld, int msgid )
 130 {
 131 #ifndef LDAP_NOCACHE
 132         Debug( LDAP_DEBUG_TRACE, "ldap_uncache_request %d ld_cache %lx\n",
 133             msgid, (long) ld->ld_cache, 0 );
 134
 135         uncache_entry_or_req( ld, NULL, msgid );
 136 #endif
 137 }
 138
 139
 140 void
 141 ldap_uncache_entry( LDAP *ld, LDAP_CONST char *dn )
 142 {
 143 #ifndef LDAP_NOCACHE
 144         Debug( LDAP_DEBUG_TRACE, "ldap_uncache_entry %s ld_cache %lx\n",
 145             dn, (long) ld->ld_cache, 0 );
 146
 147         uncache_entry_or_req( ld, dn, 0 );
 148 #endif
 149 }
 150
 151
 152 #ifndef LDAP_NOCACHE
 153
 154 static void
 155 uncache_entry_or_req( LDAP *ld,
 156         const char *dn,         /* if non-NULL, uncache entry */
 157         int msgid )             /* request to uncache (if dn == NULL) */
 158 {
 159         int             i;
 160         LDAPMessage     *m, *prev, *next;
 161
 162         Debug( LDAP_DEBUG_TRACE,
 163             "ldap_uncache_entry_or_req  dn %s  msgid %d  ld_cache %lx\n",
 164             dn, msgid, (long) ld->ld_cache );
 165
 166         if ( ld->ld_cache == NULLLDCACHE ) {
 167             return;
 168         }
 169
 170         /* first check the request queue */
 171         prev = NULLMSG;
 172         for ( m = ld->ld_cache->lc_requests; m != NULLMSG; m = next ) {
 173                 next = m->lm_next;
 174                 if (( dn != NULL && chain_contains_dn( m, dn )) ||
 175                         ( dn == NULL && m->lm_msgid == msgid )) {
 176                         if ( prev == NULLMSG ) {
 177                                 ld->ld_cache->lc_requests = next;
 178                         } else {
 179                                 prev->lm_next = next;
 180                         }
 181                         ld->ld_cache->lc_memused -= msg_size( m );
 182                         ldap_msgfree( m );
 183                 } else {
 184                         prev = m;
 185                 }
 186         }
 187
 188         /* now check the rest of the cache */
 189         for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
 190                 prev = NULLMSG;
 191                 for ( m = ld->ld_cache->lc_buckets[ i ]; m != NULLMSG;
 192                     m = next ) {
 193                         next = m->lm_next;
 194                         if (( dn != NULL && chain_contains_dn( m, dn )) ||
 195                                 ( dn == NULL && m->lm_msgid == msgid )) {
 196                                 if ( prev == NULLMSG ) {
 197                                         ld->ld_cache->lc_buckets[ i ] = next;
 198                                 } else {
 199                                         prev->lm_next = next;
 200                                 }
 201                                 ld->ld_cache->lc_memused -= msg_size( m );
 202                                 ldap_msgfree( m );
 203                         } else {
 204                                 prev = m;
 205                         }
 206                 }
 207         }
 208 }
 209
 210 #endif
 211
 212 void
 213 ldap_add_request_to_cache( LDAP *ld, unsigned long msgtype, BerElement *request )
 214 {
 215 #ifndef LDAP_NOCACHE
 216         LDAPMessage     *new;
 217         long            len;
 218
 219         Debug( LDAP_DEBUG_TRACE, "ldap_add_request_to_cache\n", 0, 0, 0 );
 220
 221         ld->ld_errno = LDAP_SUCCESS;
 222         if ( ld->ld_cache == NULLLDCACHE ||
 223             ( ld->ld_cache->lc_enabled == 0 )) {
 224                 return;
 225         }
 226
 227         if (( new = (LDAPMessage *) calloc( 1, sizeof(LDAPMessage) ))
 228             != NULL ) {
 229                 if (( new->lm_ber = ldap_alloc_ber_with_options( ld )) == NULLBER ) {
 230                         free( (char *)new );
 231                         return;
 232                 }
 233                 len = request->ber_ptr - request->ber_buf;
 234                 if (( new->lm_ber->ber_buf = (char *) malloc( (size_t)len ))
 235                     == NULL ) {
 236                         ber_free( new->lm_ber, 0 );
 237                         free( (char *)new );
 238                         ld->ld_errno = LDAP_NO_MEMORY;
 239                         return;
 240                 }
 241                 SAFEMEMCPY( new->lm_ber->ber_buf, request->ber_buf,
 242                     (size_t)len );
 243                 new->lm_ber->ber_ptr = new->lm_ber->ber_buf;
 244                 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
 245                 new->lm_msgid = ld->ld_msgid;
 246                 new->lm_msgtype = msgtype;;
 247                 new->lm_next = ld->ld_cache->lc_requests;
 248                 ld->ld_cache->lc_requests = new;
 249         } else {
 250                 ld->ld_errno = LDAP_NO_MEMORY;
 251         }
 252 #endif
 253 }
 254
 255
 256 void
 257 ldap_add_result_to_cache( LDAP *ld, LDAPMessage *result )
 258 {
 259 #ifndef LDAP_NOCACHE
 260         LDAPMessage     *m, **mp, *req, *new, *prev;
 261         int             err, keep;
 262
 263         Debug( LDAP_DEBUG_TRACE, "ldap_add_result_to_cache: id %d, type %d\n",
 264                 result->lm_msgid, result->lm_msgtype, 0 );
 265
 266         if ( ld->ld_cache == NULLLDCACHE ||
 267             ( ld->ld_cache->lc_enabled == 0 )) {
 268                 Debug( LDAP_DEBUG_TRACE, "artc: cache disabled\n", 0, 0, 0 );
 269                 return;
 270         }
 271
 272         if ( result->lm_msgtype != LDAP_RES_SEARCH_ENTRY &&
 273             result->lm_msgtype != LDAP_RES_SEARCH_REFERENCE &&
 274             result->lm_msgtype != LDAP_RES_SEARCH_RESULT &&
 275             result->lm_msgtype != LDAP_RES_COMPARE ) {
 276                 /*
 277                  * only cache search and compare operations
 278                  */
 279                 Debug( LDAP_DEBUG_TRACE,
 280                     "artc: only caching search & compare operations\n", 0, 0, 0 );
 281                 return;
 282         }
 283
 284         /*
 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.
 288          */
 289         prev = NULLMSG;
 290         for ( m = ld->ld_cache->lc_requests; m != NULL; m = m->lm_next ) {
 291                 if ( m->lm_msgid == result->lm_msgid ) {
 292                         break;
 293                 }
 294                 prev = m;
 295         }
 296
 297         if ( m != NULLMSG ) {   /* found request; add to end of chain */
 298                 req = m;
 299                 for ( ; m->lm_chain != NULLMSG; m = m->lm_chain )
 300                         ;
 301                 if (( new = msg_dup( result )) != NULLMSG ) {
 302                         new->lm_chain = NULLMSG;
 303                         m->lm_chain = new;
 304                         Debug( LDAP_DEBUG_TRACE,
 305                             "artc: result added to cache request chain\n",
 306                             0, 0, 0 );
 307                 }
 308                 if ( result->lm_msgtype == LDAP_RES_SEARCH_RESULT ||
 309                     result->lm_msgtype == LDAP_RES_COMPARE ) {
 310                         /*
 311                          * this result completes the chain of results
 312                          * add to cache proper if appropriate
 313                          */
 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 ))) {
 321                                 keep = 1;
 322                         }
 323
 324                         if ( ld->ld_cache->lc_options == 0 ) {
 325                                 if ( err == LDAP_SIZELIMIT_EXCEEDED ) {
 326                                     keep = 1;
 327                                 }
 328                         } else if (( ld->ld_cache->lc_options &
 329                                 LDAP_CACHE_OPT_CACHEALLERRS ) != 0 ) {
 330                                 keep = 1;
 331                         }
 332
 333                         if ( prev == NULLMSG ) {
 334                                 ld->ld_cache->lc_requests = req->lm_next;
 335                         } else {
 336                                 prev->lm_next = req->lm_next;
 337                         }
 338
 339                         if ( !keep ) {
 340                                 Debug( LDAP_DEBUG_TRACE,
 341                                     "artc: not caching result with error %d\n",
 342                                     err, 0, 0 );
 343                                 ldap_msgfree( req );
 344                         } else {
 345                                 mp = &ld->ld_cache->lc_buckets[
 346                                     cache_hash( req->lm_ber ) ];
 347                                 req->lm_next = *mp;
 348                                 *mp = req;
 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",
 354                                     err, 0, 0 );
 355                         }
 356                 }
 357         } else {
 358                 Debug( LDAP_DEBUG_TRACE, "artc: msgid not in request list\n",
 359                     0, 0, 0 );
 360         }
 361 #endif
 362 }
 363
 364
 365 /*
 366  * look in the cache for this request
 367  * return 0 if found, -1 if not
 368  * if found, the corresponding result messages are added to the incoming
 369  * queue with the correct (new) msgid so that subsequent ldap_result calls
 370  * will find them.
 371  */
 372 int
 373 ldap_check_cache( LDAP *ld, unsigned long msgtype, BerElement *request )
 374 {
 375 #ifndef LDAP_NOCACHE
 376         LDAPMessage     *m, *new, *prev, *next;
 377         BerElement      reqber;
 378         int             first, hash;
 379         unsigned long   validtime;
 380
 381         Debug( LDAP_DEBUG_TRACE, "ldap_check_cache\n", 0, 0, 0 );
 382
 383         if ( ld->ld_cache == NULLLDCACHE ||
 384             ( ld->ld_cache->lc_enabled == 0 )) {
 385                 return( -1 );
 386         }
 387
 388         reqber.ber_buf = reqber.ber_ptr = request->ber_buf;
 389         reqber.ber_end = request->ber_ptr;
 390
 391         validtime = (long)time( NULL ) - ld->ld_cache->lc_timeout;
 392
 393         prev = NULLMSG;
 394         hash = cache_hash( &reqber );
 395         for ( m = ld->ld_cache->lc_buckets[ hash ]; m != NULLMSG; m = next ) {
 396                 Debug( LDAP_DEBUG_TRACE,"cc: examining id %d,type %d\n",
 397                     m->lm_msgid, m->lm_msgtype, 0 );
 398                 if ( m->lm_time < validtime ) {
 399                         /* delete expired message */
 400                         next = m->lm_next;
 401                         if ( prev == NULL ) {
 402                                 ld->ld_cache->lc_buckets[ hash ] = next;
 403                         } else {
 404                                 prev->lm_next = next;
 405                         }
 406                         Debug( LDAP_DEBUG_TRACE, "cc: expired id %d\n",
 407                             m->lm_msgid, 0, 0 );
 408                         ld->ld_cache->lc_memused -= msg_size( m );
 409                         ldap_msgfree( m );
 410                 } else {
 411                     if ( m->lm_msgtype == (int)msgtype &&
 412                         request_cmp( m->lm_ber, &reqber ) == 0 ) {
 413                             break;
 414                     }
 415                     next = m->lm_next;
 416                     prev = m;
 417                 }
 418         }
 419
 420         if ( m == NULLMSG ) {
 421                 return( -1 );
 422         }
 423
 424         /*
 425          * add duplicates of responses to incoming queue
 426          */
 427         first = 1;
 428         for ( m = m->lm_chain; m != NULLMSG; m = m->lm_chain ) {
 429                 if (( new = msg_dup( m )) == NULLMSG ) {
 430                         return( -1 );
 431                 }
 432
 433                 new->lm_msgid = ld->ld_msgid;
 434                 new->lm_chain = NULLMSG;
 435                 if ( first ) {
 436                         new->lm_next = ld->ld_responses;
 437                         ld->ld_responses = new;
 438                         first = 0;
 439                 } else {
 440                         prev->lm_chain = new;
 441                 }
 442                 prev = new;
 443                 Debug( LDAP_DEBUG_TRACE, "cc: added type %d\n",
 444                     new->lm_msgtype, 0, 0 );
 445         }
 446
 447         Debug( LDAP_DEBUG_TRACE, "cc: result returned from cache\n", 0, 0, 0 );
 448         return( 0 );
 449 #else
 450         return( -1 );
 451 #endif
 452 }
 453
 454 #ifndef LDAP_NOCACHE
 455
 456 static int
 457 cache_hash( BerElement *ber )
 458 {
 459         BerElement      bercpy;
 460         unsigned long   len;
 461
 462         /*
 463          * just take the length of the packet and mod with # of buckets
 464          */
 465         bercpy = *ber;
 466         if ( ber_skip_tag( &bercpy, &len ) == LBER_ERROR
 467                 || ber_scanf( &bercpy, "x" ) == LBER_ERROR ) {
 468             len = 0;    /* punt: just return zero */
 469         } else {
 470             len = bercpy.ber_end - bercpy.ber_ptr;
 471         }
 472
 473         Debug( LDAP_DEBUG_TRACE, "cache_hash: len is %ld, returning %ld\n",
 474             len, len % LDAP_CACHE_BUCKETS, 0 );
 475         return( (int) ( len % LDAP_CACHE_BUCKETS ));
 476 }
 477
 478
 479 static LDAPMessage *
 480 msg_dup( LDAPMessage *msg )
 481 {
 482         LDAPMessage     *new;
 483         long            len;
 484
 485         if (( new = (LDAPMessage *)malloc( sizeof(LDAPMessage))) != NULL ) {
 486                 *new = *msg;    /* struct copy */
 487                 if (( new->lm_ber = ber_dup( msg->lm_ber )) == NULLBER ) {
 488                         free( (char *)new );
 489                         return( NULLMSG );
 490                 }
 491                 len = msg->lm_ber->ber_end - msg->lm_ber->ber_buf;
 492                 if (( new->lm_ber->ber_buf = (char *) malloc(
 493                     (size_t)len )) == NULL ) {
 494                         ber_free( new->lm_ber, 0 );
 495                         free( (char *)new );
 496                         return( NULLMSG );
 497                 }
 498                 SAFEMEMCPY( new->lm_ber->ber_buf, msg->lm_ber->ber_buf,
 499                     (size_t)len );
 500                 new->lm_ber->ber_ptr = new->lm_ber->ber_buf +
 501                         ( msg->lm_ber->ber_ptr - msg->lm_ber->ber_buf );
 502                 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
 503         }
 504
 505         return( new );
 506 }
 507
 508
 509 static int
 510 request_cmp( BerElement *req1, BerElement *req2 )
 511 {
 512         unsigned long   len;
 513         BerElement      r1, r2;
 514
 515         r1 = *req1;     /* struct copies */
 516         r2 = *req2;
 517
 518         /*
 519          * skip the enclosing tags (sequence markers) and the msg ids
 520          */
 521         if ( ber_skip_tag( &r1, &len ) == LBER_ERROR || ber_scanf( &r1, "x" )
 522             == LBER_ERROR ) {
 523             return( -1 );
 524         }
 525         if ( ber_skip_tag( &r2, &len ) == LBER_ERROR || ber_scanf( &r2, "x" )
 526             == LBER_ERROR ) {
 527             return( -1 );
 528         }
 529
 530         /*
 531          * check remaining length and bytes if necessary
 532          */
 533         if (( len = r1.ber_end - r1.ber_ptr ) !=
 534                 (unsigned long) (r2.ber_end - r2.ber_ptr) )
 535         {
 536                 return( -1 );   /* different lengths */
 537         }
 538         return( memcmp( r1.ber_ptr, r2.ber_ptr, (size_t)len ));
 539 }
 540
 541
 542 static int
 543 chain_contains_dn( LDAPMessage *msg, const char *dn )
 544 {
 545         LDAPMessage     *m;
 546         BerElement      ber;
 547         long            msgid;
 548         char            *s;
 549         int             rc;
 550
 551
 552         /*
 553          * first check the base or dn of the request
 554          */
 555         ber = *msg->lm_ber;     /* struct copy */
 556         if ( ber_scanf( &ber, "{i{a", &msgid, &s ) != LBER_ERROR ) {
 557             rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
 558             free( s );
 559             if ( rc != 0 ) {
 560                 return( rc );
 561             }
 562         }
 563
 564         if ( msg->lm_msgtype == LDAP_REQ_COMPARE ) {
 565                 return( 0 );
 566         }
 567
 568         /*
 569          * now check the dn of each search result
 570          */
 571         rc = 0;
 572         for ( m = msg->lm_chain; m != NULLMSG && rc == 0 ; m = m->lm_chain ) {
 573                 if ( m->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
 574                         continue;
 575                 }
 576                 ber = *m->lm_ber;       /* struct copy */
 577                 if ( ber_scanf( &ber, "{a", &s ) != LBER_ERROR ) {
 578                         rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
 579                         free( s );
 580                 }
 581         }
 582
 583         return( rc );
 584 }
 585
 586
 587 static long
 588 msg_size( LDAPMessage *msg )
 589 {
 590         LDAPMessage     *m;
 591         long            size;
 592
 593         size = 0;
 594         for ( m = msg; m != NULLMSG; m = m->lm_chain ) {
 595                 size += ( sizeof( LDAPMessage ) + m->lm_ber->ber_end -
 596                     m->lm_ber->ber_buf );
 597         }
 598
 599         return( size );
 600 }
 601
 602
 603 #define THRESHOLD_FACTOR        3 / 4
 604 #define SIZE_FACTOR             2 / 3
 605
 606 static void
 607 check_cache_memused( LDAPCache *lc )
 608 {
 609 /*
 610  * this routine is called to check if the cache is too big (lc_maxmem >
 611  * minimum cache size and lc_memused > lc_maxmem).  If too big, it reduces
 612  * the cache size to < SIZE_FACTOR * lc_maxmem. The algorithm is as follows:
 613  *    remove_threshold = lc_timeout seconds;
 614  *    do {
 615  *        remove everything older than remove_threshold seconds;
 616  *        remove_threshold = remove_threshold * THRESHOLD_FACTOR;
 617  *    } while ( cache size is > SIZE_FACTOR * lc_maxmem )
 618  */
 619         int             i;
 620         unsigned long   remove_threshold, validtime;
 621         LDAPMessage     *m, *prev, *next;
 622
 623         Debug( LDAP_DEBUG_TRACE, "check_cache_memused: %ld bytes in use (%ld max)\n",
 624             lc->lc_memused, lc->lc_maxmem, 0 );
 625
 626         if ( (unsigned) lc->lc_maxmem <= sizeof( LDAPCache )
 627             || lc->lc_memused <= lc->lc_maxmem * SIZE_FACTOR ) {
 628                 return;
 629         }
 630
 631         remove_threshold = lc->lc_timeout;
 632         while ( lc->lc_memused > lc->lc_maxmem * SIZE_FACTOR ) {
 633                 validtime = (long)time( NULL ) - remove_threshold;
 634                 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
 635                         prev = NULLMSG;
 636                         for ( m = lc->lc_buckets[ i ]; m != NULLMSG;
 637                             m = next ) {
 638                                 next = m->lm_next;
 639                                 if ( m->lm_time < validtime ) {
 640                                         if ( prev == NULLMSG ) {
 641                                                 lc->lc_buckets[ i ] = next;
 642                                         } else {
 643                                                 prev->lm_next = next;
 644                                         }
 645                                         lc->lc_memused -= msg_size( m );
 646                                         Debug( LDAP_DEBUG_TRACE,
 647                                             "ccm: removed %d\n",
 648                                             m->lm_msgid, 0, 0 );
 649                                         ldap_msgfree( m );
 650                                 } else {
 651                                         prev = m;
 652                                 }
 653                         }
 654                 }
 655                 remove_threshold *= THRESHOLD_FACTOR;
 656         }
 657
 658         Debug( LDAP_DEBUG_TRACE, "ccm: reduced usage to %ld bytes\n",
 659             lc->lc_memused, 0, 0 );
 660 }
 661
 662 #endif /* !NO_CACHE */