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