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

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