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

   1 /* $OpenLDAP$ */
   2 /*
   3  * Copyright 1998-2002 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 #ifdef NEW_LOGGING
 106         LDAP_LOG (( "cache", LDAP_LEVEL_ENTRY, "ldap_flush_cache\n" ));
 107 #else
 108         Debug( LDAP_DEBUG_TRACE, "ldap_flush_cache\n", 0, 0, 0 );
 109 #endif
 110
 111         if ( ld->ld_cache != NULL ) {
 112                 /* delete all requests in the queue */
 113                 for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
 114                         next = m->lm_next;
 115                         ldap_msgfree( m );
 116                 }
 117                 ld->ld_cache->lc_requests = NULL;
 118
 119                 /* delete all messages in the cache */
 120                 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
 121                         for ( m = ld->ld_cache->lc_buckets[ i ];
 122                             m != NULL; m = next ) {
 123                                 next = m->lm_next;
 124                                 ldap_msgfree( m );
 125                         }
 126                         ld->ld_cache->lc_buckets[ i ] = NULL;
 127                 }
 128                 ld->ld_cache->lc_memused = sizeof( LDAPCache );
 129         }
 130 #endif
 131 }
 132
 133
 134 void
 135 ldap_uncache_request( LDAP *ld, int msgid )
 136 {
 137 #ifndef LDAP_NOCACHE
 138 #ifdef NEW_LOGGING
 139         LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
 140                 "ldap_uncache_request %d ld_cache %lx\n",
 141                 msgid, (long) ld->ld_cache ));
 142 #else
 143         Debug( LDAP_DEBUG_TRACE, "ldap_uncache_request %d ld_cache %lx\n",
 144             msgid, (long) ld->ld_cache, 0 );
 145 #endif
 146
 147         uncache_entry_or_req( ld, NULL, msgid );
 148 #endif
 149 }
 150
 151
 152 void
 153 ldap_uncache_entry( LDAP *ld, LDAP_CONST char *dn )
 154 {
 155 #ifndef LDAP_NOCACHE
 156 #ifdef NEW_LOGGING
 157         LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
 158                 "ldap_uncache_entry %s ld_cache %lx\n",
 159                 dn, (long) ld->ld_cache ));
 160 #else
 161         Debug( LDAP_DEBUG_TRACE, "ldap_uncache_entry %s ld_cache %lx\n",
 162             dn, (long) ld->ld_cache, 0 );
 163 #endif
 164
 165         uncache_entry_or_req( ld, dn, 0 );
 166 #endif
 167 }
 168
 169
 170 #ifndef LDAP_NOCACHE
 171
 172 static void
 173 uncache_entry_or_req( LDAP *ld,
 174         const char *dn,         /* if non-NULL, uncache entry */
 175         ber_int_t msgid )               /* request to uncache (if dn == NULL) */
 176 {
 177         int             i;
 178         LDAPMessage     *m, *prev, *next;
 179
 180 #ifdef NEW_LOGGING
 181         LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
 182                 "uncache_entry_or_req dn %s msgid %ld ld_cache %lx\n",
 183                 dn, (long) msgid, (long) ld->ld_cache ));
 184 #else
 185         Debug( LDAP_DEBUG_TRACE,
 186             "ldap_uncache_entry_or_req  dn %s  msgid %ld  ld_cache %lx\n",
 187             dn, (long) msgid, (long) ld->ld_cache );
 188 #endif
 189
 190         if ( ld->ld_cache == NULL ) {
 191             return;
 192         }
 193
 194         /* first check the request queue */
 195         prev = NULL;
 196         for ( m = ld->ld_cache->lc_requests; m != NULL; m = next ) {
 197                 next = m->lm_next;
 198                 if (( dn != NULL && chain_contains_dn( m, dn )) ||
 199                         ( dn == NULL && m->lm_msgid == msgid )) {
 200                         if ( prev == NULL ) {
 201                                 ld->ld_cache->lc_requests = next;
 202                         } else {
 203                                 prev->lm_next = next;
 204                         }
 205                         ld->ld_cache->lc_memused -= msg_size( m );
 206                         ldap_msgfree( m );
 207                 } else {
 208                         prev = m;
 209                 }
 210         }
 211
 212         /* now check the rest of the cache */
 213         for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
 214                 prev = NULL;
 215                 for ( m = ld->ld_cache->lc_buckets[ i ]; m != NULL;
 216                     m = next ) {
 217                         next = m->lm_next;
 218                         if (( dn != NULL && chain_contains_dn( m, dn )) ||
 219                                 ( dn == NULL && m->lm_msgid == msgid )) {
 220                                 if ( prev == NULL ) {
 221                                         ld->ld_cache->lc_buckets[ i ] = next;
 222                                 } else {
 223                                         prev->lm_next = next;
 224                                 }
 225                                 ld->ld_cache->lc_memused -= msg_size( m );
 226                                 ldap_msgfree( m );
 227                         } else {
 228                                 prev = m;
 229                         }
 230                 }
 231         }
 232 }
 233
 234 #endif
 235
 236 void
 237 ldap_add_request_to_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
 238 {
 239 #ifndef LDAP_NOCACHE
 240         LDAPMessage     *new;
 241         ber_len_t       len;
 242
 243 #ifdef NEW_LOGGING
 244         LDAP_LOG (( "cache", LDAP_LEVEL_ENTRY, "ldap_add_request_to_cache\n" ));
 245 #else
 246         Debug( LDAP_DEBUG_TRACE, "ldap_add_request_to_cache\n", 0, 0, 0 );
 247 #endif
 248
 249         ld->ld_errno = LDAP_SUCCESS;
 250         if ( ld->ld_cache == NULL ||
 251             ( ld->ld_cache->lc_enabled == 0 )) {
 252                 return;
 253         }
 254
 255         if (( new = (LDAPMessage *) LDAP_CALLOC( 1, sizeof(LDAPMessage) ))
 256             != NULL ) {
 257                 if (( new->lm_ber = ldap_alloc_ber_with_options( ld )) == NULL ) {
 258                         LDAP_FREE( (char *)new );
 259                         return;
 260                 }
 261                 len = request->ber_ptr - request->ber_buf;
 262                 if (( new->lm_ber->ber_buf = (char *) ber_memalloc( (size_t)len ))
 263                     == NULL ) {
 264                         ber_free( new->lm_ber, 0 );
 265                         LDAP_FREE( (char *)new );
 266                         ld->ld_errno = LDAP_NO_MEMORY;
 267                         return;
 268                 }
 269                 AC_MEMCPY( new->lm_ber->ber_buf, request->ber_buf,
 270                     (size_t)len );
 271                 new->lm_ber->ber_ptr = new->lm_ber->ber_buf;
 272                 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
 273                 new->lm_msgid = ld->ld_msgid;
 274                 new->lm_msgtype = msgtype;;
 275                 new->lm_next = ld->ld_cache->lc_requests;
 276                 ld->ld_cache->lc_requests = new;
 277         } else {
 278                 ld->ld_errno = LDAP_NO_MEMORY;
 279         }
 280 #endif
 281 }
 282
 283
 284 void
 285 ldap_add_result_to_cache( LDAP *ld, LDAPMessage *result )
 286 {
 287 #ifndef LDAP_NOCACHE
 288         LDAPMessage     *m, **mp, *req, *new, *prev;
 289         int             err, keep;
 290
 291 #ifdef NEW_LOGGING
 292         LDAP_LOG (( "cache", LDAP_LEVEL_ARGS,
 293                 "ldap_add_result_to_cache: id %ld, type %ld\n",
 294                 (long) result->lm_msgid, (long) result->lm_msgtype ));
 295 #else
 296         Debug( LDAP_DEBUG_TRACE, "ldap_add_result_to_cache: id %ld, type %ld\n",
 297                 (long) result->lm_msgid, (long) result->lm_msgtype, 0 );
 298 #endif
 299
 300         if ( ld->ld_cache == NULL ||
 301             ( ld->ld_cache->lc_enabled == 0 )) {
 302 #ifdef NEW_LOGGING
 303                 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 304                 "ldap_add_result_to_cache: cache disabled\n" ));
 305 #else
 306                 Debug( LDAP_DEBUG_TRACE, "artc: cache disabled\n", 0, 0, 0 );
 307 #endif
 308                 return;
 309         }
 310
 311         if ( result->lm_msgtype != LDAP_RES_SEARCH_ENTRY &&
 312             result->lm_msgtype != LDAP_RES_SEARCH_REFERENCE &&
 313             result->lm_msgtype != LDAP_RES_SEARCH_RESULT &&
 314             result->lm_msgtype != LDAP_RES_COMPARE ) {
 315                 /*
 316                  * only cache search and compare operations
 317                  */
 318 #ifdef NEW_LOGGING
 319                 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 320                 "ldap_add_result_to_cache: "
 321                 "only caching search & compare operations\n" ));
 322 #else
 323                 Debug( LDAP_DEBUG_TRACE,
 324                     "artc: only caching search & compare operations\n", 0, 0, 0 );
 325 #endif
 326                 return;
 327         }
 328
 329         /*
 330          * if corresponding request is in the lc_requests list, add this
 331          * result to it.  if this result completes the results for the
 332          * request, add the request/result chain to the cache proper.
 333          */
 334         prev = NULL;
 335         for ( m = ld->ld_cache->lc_requests; m != NULL; m = m->lm_next ) {
 336                 if ( m->lm_msgid == result->lm_msgid ) {
 337                         break;
 338                 }
 339                 prev = m;
 340         }
 341
 342         if ( m != NULL ) {      /* found request; add to end of chain */
 343                 req = m;
 344                 for ( ; m->lm_chain != NULL; m = m->lm_chain )
 345                         ;
 346                 if (( new = msg_dup( result )) != NULL ) {
 347                         new->lm_chain = NULL;
 348                         m->lm_chain = new;
 349 #ifdef NEW_LOGGING
 350                         LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
 351                                 "ldap_add_result_to_cache: "
 352                                 "result added to cache request chain\n" ));
 353 #else
 354                         Debug( LDAP_DEBUG_TRACE,
 355                             "artc: result added to cache request chain\n",
 356                             0, 0, 0 );
 357 #endif
 358                 }
 359                 if ( result->lm_msgtype == LDAP_RES_SEARCH_RESULT ||
 360                     result->lm_msgtype == LDAP_RES_COMPARE ) {
 361                         /*
 362                          * this result completes the chain of results
 363                          * add to cache proper if appropriate
 364                          */
 365                         keep = 0;       /* pessimistic */
 366                         err = ldap_result2error( ld, result, 0 );
 367                         if ( err == LDAP_SUCCESS ||
 368                             ( result->lm_msgtype == LDAP_RES_COMPARE &&
 369                             ( err == LDAP_COMPARE_FALSE ||
 370                             err == LDAP_COMPARE_TRUE ||
 371                             err == LDAP_NO_SUCH_ATTRIBUTE ))) {
 372                                 keep = 1;
 373                         }
 374
 375                         if ( ld->ld_cache->lc_options == 0 ) {
 376                                 if ( err == LDAP_SIZELIMIT_EXCEEDED ) {
 377                                     keep = 1;
 378                                 }
 379                         } else if (( ld->ld_cache->lc_options &
 380                                 LDAP_CACHE_OPT_CACHEALLERRS ) != 0 ) {
 381                                 keep = 1;
 382                         }
 383
 384                         if ( prev == NULL ) {
 385                                 ld->ld_cache->lc_requests = req->lm_next;
 386                         } else {
 387                                 prev->lm_next = req->lm_next;
 388                         }
 389
 390                         if ( !keep ) {
 391 #ifdef NEW_LOGGING
 392                                 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
 393                                         "ldap_add_result_to_cache: "
 394                                         "not caching result with error\n" ));
 395 #else
 396                                 Debug( LDAP_DEBUG_TRACE,
 397                                     "artc: not caching result with error %d\n",
 398                                     err, 0, 0 );
 399 #endif
 400                                 ldap_msgfree( req );
 401                         } else {
 402                                 mp = &ld->ld_cache->lc_buckets[
 403                                     cache_hash( req->lm_ber ) ];
 404                                 req->lm_next = *mp;
 405                                 *mp = req;
 406                                 req->lm_time = (long) time( NULL );
 407                                 ld->ld_cache->lc_memused += msg_size( req );
 408                                 check_cache_memused( ld->ld_cache );
 409 #ifdef NEW_LOGGING
 410                                 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
 411                                         "ldap_add_result_to_cache: "
 412                                         "cached result with error\n" ));
 413 #else
 414                                 Debug( LDAP_DEBUG_TRACE,
 415                                     "artc: cached result with error %d\n",
 416                                     err, 0, 0 );
 417 #endif
 418                         }
 419                 }
 420         } else {
 421 #ifdef NEW_LOGGING
 422                 LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
 423                         "ldap_add_result_to_cache: "
 424                         "msgid not in request list\n" ));
 425 #else
 426                 Debug( LDAP_DEBUG_TRACE, "artc: msgid not in request list\n",
 427                     0, 0, 0 );
 428 #endif
 429         }
 430 #endif
 431 }
 432
 433
 434 /*
 435  * look in the cache for this request
 436  * return 0 if found, -1 if not
 437  * if found, the corresponding result messages are added to the incoming
 438  * queue with the correct (new) msgid so that subsequent ldap_result calls
 439  * will find them.
 440  */
 441 int
 442 ldap_check_cache( LDAP *ld, ber_tag_t msgtype, BerElement *request )
 443 {
 444 #ifndef LDAP_NOCACHE
 445         LDAPMessage     *m, *new, *prev, *next;
 446         BerElement      reqber;
 447         int             first, hash;
 448         time_t  c_time;
 449
 450 #ifdef NEW_LOGGING
 451         LDAP_LOG (( "cache", LDAP_LEVEL_ENTRY, "ldap_check_cache\n" ));
 452 #else
 453         Debug( LDAP_DEBUG_TRACE, "ldap_check_cache\n", 0, 0, 0 );
 454 #endif
 455
 456         if ( ld->ld_cache == NULL ||
 457             ( ld->ld_cache->lc_enabled == 0 )) {
 458                 return( -1 );
 459         }
 460
 461         memset( &reqber, '\0', sizeof(reqber) );
 462         reqber.ber_valid = LBER_VALID_BERELEMENT;
 463         reqber.ber_buf = reqber.ber_ptr = request->ber_buf;
 464         reqber.ber_end = request->ber_ptr;
 465         reqber.ber_debug = ber_int_debug;
 466
 467         c_time = time( NULL );
 468
 469         prev = NULL;
 470         hash = cache_hash( &reqber );
 471         for ( m = ld->ld_cache->lc_buckets[ hash ]; m != NULL; m = next ) {
 472 #ifdef NEW_LOGGING
 473                 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 474                         "ldap_check_cache: examining id %ld, type %ld\n",
 475                         (long) m->lm_msgid, (long) m->lm_msgtype ));
 476 #else
 477                 Debug( LDAP_DEBUG_TRACE,"cc: examining id %ld,type %ld\n",
 478                     (long) m->lm_msgid, (long) m->lm_msgtype, 0 );
 479 #endif
 480                 if ( difftime(c_time, m->lm_time) > ld->ld_cache->lc_timeout ) {
 481                         /* delete expired message */
 482                         next = m->lm_next;
 483                         if ( prev == NULL ) {
 484                                 ld->ld_cache->lc_buckets[ hash ] = next;
 485                         } else {
 486                                 prev->lm_next = next;
 487                         }
 488 #ifdef NEW_LOGGING
 489                         LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 490                                 "ldap_check_cache: expired id %ld\n",
 491                                 (long) m->lm_msgid ));
 492 #else
 493                         Debug( LDAP_DEBUG_TRACE, "cc: expired id %d\n",
 494                             m->lm_msgid, 0, 0 );
 495 #endif
 496                         ld->ld_cache->lc_memused -= msg_size( m );
 497                         ldap_msgfree( m );
 498                 } else {
 499                     if ( m->lm_msgtype == msgtype &&
 500                         request_cmp( m->lm_ber, &reqber ) == 0 ) {
 501                             break;
 502                     }
 503                     next = m->lm_next;
 504                     prev = m;
 505                 }
 506         }
 507
 508         if ( m == NULL ) {
 509                 return( -1 );
 510         }
 511
 512         /*
 513          * add duplicates of responses to incoming queue
 514          */
 515         first = 1;
 516         for ( m = m->lm_chain; m != NULL; m = m->lm_chain ) {
 517                 if (( new = msg_dup( m )) == NULL ) {
 518                         return( -1 );
 519                 }
 520
 521                 new->lm_msgid = ld->ld_msgid;
 522                 new->lm_chain = NULL;
 523                 if ( first ) {
 524                         new->lm_next = ld->ld_responses;
 525                         ld->ld_responses = new;
 526                         first = 0;
 527                 } else {
 528                         prev->lm_chain = new;
 529                 }
 530                 prev = new;
 531 #ifdef NEW_LOGGING
 532                 LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 533                         "ldap_check_cache: added type %ld\n",
 534                         (long) m->lm_msgtype ));
 535 #else
 536                 Debug( LDAP_DEBUG_TRACE, "cc: added type %ld\n",
 537                     (long) new->lm_msgtype, 0, 0 );
 538 #endif
 539         }
 540
 541 #ifdef NEW_LOGGING
 542         LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
 543                 "ldap_check_cache: result returned from cache\n" ));
 544 #else
 545         Debug( LDAP_DEBUG_TRACE, "cc: result returned from cache\n", 0, 0, 0 );
 546 #endif
 547         return( 0 );
 548 #else
 549         return( -1 );
 550 #endif
 551 }
 552
 553 #ifndef LDAP_NOCACHE
 554
 555 static int
 556 cache_hash( BerElement *ber )
 557 {
 558         BerElement      bercpy;
 559         ber_len_t       len;
 560
 561         /*
 562          * just take the length of the packet and mod with # of buckets
 563          */
 564         bercpy = *ber;
 565         if ( ber_skip_tag( &bercpy, &len ) == LBER_ERROR
 566                 || ber_scanf( &bercpy, "x" ) == LBER_ERROR ) {
 567             len = 0;    /* punt: just return zero */
 568         } else {
 569             len = bercpy.ber_end - bercpy.ber_ptr;
 570         }
 571
 572 #ifdef NEW_LOGGING
 573         LDAP_LOG (( "cache", LDAP_LEVEL_RESULTS,
 574                 "cache_hash: len is %ld, returning %ld\n",
 575                  len, len % LDAP_CACHE_BUCKETS ));
 576 #else
 577         Debug( LDAP_DEBUG_TRACE, "cache_hash: len is %ld, returning %ld\n",
 578             len, len % LDAP_CACHE_BUCKETS, 0 );
 579 #endif
 580         return( (int) ( len % LDAP_CACHE_BUCKETS ));
 581 }
 582
 583
 584 static LDAPMessage *
 585 msg_dup( LDAPMessage *msg )
 586 {
 587         LDAPMessage     *new;
 588         ber_len_t       len;
 589
 590         if (( new = (LDAPMessage *)LDAP_MALLOC( sizeof(LDAPMessage))) != NULL ) {
 591                 *new = *msg;    /* struct copy */
 592                 if (( new->lm_ber = ber_dup( msg->lm_ber )) == NULL ) {
 593                         LDAP_FREE( (char *)new );
 594                         return( NULL );
 595                 }
 596                 len = msg->lm_ber->ber_end - msg->lm_ber->ber_buf;
 597                 if (( new->lm_ber->ber_buf = (char *) ber_memalloc(
 598                     (size_t)len )) == NULL ) {
 599                         ber_free( new->lm_ber, 0 );
 600                         LDAP_FREE( (char *)new );
 601                         return( NULL );
 602                 }
 603                 AC_MEMCPY( new->lm_ber->ber_buf, msg->lm_ber->ber_buf,
 604                     (size_t)len );
 605                 new->lm_ber->ber_ptr = new->lm_ber->ber_buf +
 606                         ( msg->lm_ber->ber_ptr - msg->lm_ber->ber_buf );
 607                 new->lm_ber->ber_end = new->lm_ber->ber_buf + len;
 608         }
 609
 610         return( new );
 611 }
 612
 613
 614 static int
 615 request_cmp( BerElement *req1, BerElement *req2 )
 616 {
 617         ber_len_t       len;
 618         BerElement      r1, r2;
 619
 620         r1 = *req1;     /* struct copies */
 621         r2 = *req2;
 622
 623         /*
 624          * skip the enclosing tags (sequence markers) and the msg ids
 625          */
 626         if ( ber_skip_tag( &r1, &len ) == LBER_ERROR || ber_scanf( &r1, "x" )
 627             == LBER_ERROR ) {
 628             return( -1 );
 629         }
 630         if ( ber_skip_tag( &r2, &len ) == LBER_ERROR || ber_scanf( &r2, "x" )
 631             == LBER_ERROR ) {
 632             return( -1 );
 633         }
 634
 635         /*
 636          * check remaining length and bytes if necessary
 637          */
 638         if (( len = r1.ber_end - r1.ber_ptr ) !=
 639                 (ber_len_t) (r2.ber_end - r2.ber_ptr) )
 640         {
 641                 return( -1 );   /* different lengths */
 642         }
 643         return( memcmp( r1.ber_ptr, r2.ber_ptr, (size_t)len ));
 644 }
 645
 646
 647 static int
 648 chain_contains_dn( LDAPMessage *msg, const char *dn )
 649 {
 650         LDAPMessage     *m;
 651         BerElement      ber;
 652         ber_int_t               msgid;
 653         char            *s;
 654         int             rc;
 655
 656
 657         /*
 658          * first check the base or dn of the request
 659          */
 660         ber = *msg->lm_ber;     /* struct copy */
 661         if ( ber_scanf( &ber, "{i{a" /*}}*/, &msgid, &s ) != LBER_ERROR ) {
 662             rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
 663             LDAP_FREE( s );
 664             if ( rc != 0 ) {
 665                 return( rc );
 666             }
 667         }
 668
 669         if ( msg->lm_msgtype == LDAP_REQ_COMPARE ) {
 670                 return( 0 );
 671         }
 672
 673         /*
 674          * now check the dn of each search result
 675          */
 676         rc = 0;
 677         for ( m = msg->lm_chain; m != NULL && rc == 0 ; m = m->lm_chain ) {
 678                 if ( m->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
 679                         continue;
 680                 }
 681                 ber = *m->lm_ber;       /* struct copy */
 682                 if ( ber_scanf( &ber, "{a" /*}*/, &s ) != LBER_ERROR ) {
 683                         rc = ( strcasecmp( dn, s ) == 0 ) ? 1 : 0;
 684                         LDAP_FREE( s );
 685                 }
 686         }
 687
 688         return( rc );
 689 }
 690
 691
 692 static ber_len_t
 693 msg_size( LDAPMessage *msg )
 694 {
 695         LDAPMessage     *m;
 696         ber_len_t       size;
 697
 698         size = 0;
 699         for ( m = msg; m != NULL; m = m->lm_chain ) {
 700                 size += ( sizeof( LDAPMessage ) + m->lm_ber->ber_end -
 701                     m->lm_ber->ber_buf );
 702         }
 703
 704         return( size );
 705 }
 706
 707
 708 #define THRESHOLD_FACTOR        3 / 4
 709 #define SIZE_FACTOR             2 / 3
 710
 711 static void
 712 check_cache_memused( LDAPCache *lc )
 713 {
 714 /*
 715  * this routine is called to check if the cache is too big (lc_maxmem >
 716  * minimum cache size and lc_memused > lc_maxmem).  If too big, it reduces
 717  * the cache size to < SIZE_FACTOR * lc_maxmem. The algorithm is as follows:
 718  *    remove_threshold = lc_timeout seconds;
 719  *    do {
 720  *        remove everything older than remove_threshold seconds;
 721  *        remove_threshold = remove_threshold * THRESHOLD_FACTOR;
 722  *    } while ( cache size is > SIZE_FACTOR * lc_maxmem )
 723  */
 724         int             i;
 725         unsigned long   remove_threshold;
 726         time_t c_time;
 727         LDAPMessage     *m, *prev, *next;
 728
 729 #ifdef NEW_LOGGING
 730         LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 731                 "check_cache_memused: %ld bytes in use (%ld max)\n",
 732                  lc->lc_memused, lc->lc_maxmem ));
 733 #else
 734         Debug( LDAP_DEBUG_TRACE, "check_cache_memused: %ld bytes in use (%ld max)\n",
 735             lc->lc_memused, lc->lc_maxmem, 0 );
 736 #endif
 737
 738         if ( (unsigned) lc->lc_maxmem <= sizeof( LDAPCache )
 739             || lc->lc_memused <= lc->lc_maxmem * SIZE_FACTOR ) {
 740                 return;
 741         }
 742
 743         remove_threshold = lc->lc_timeout;
 744         while ( lc->lc_memused > lc->lc_maxmem * SIZE_FACTOR ) {
 745                 c_time = time( NULL );
 746                 for ( i = 0; i < LDAP_CACHE_BUCKETS; ++i ) {
 747                         prev = NULL;
 748                         for ( m = lc->lc_buckets[ i ]; m != NULL;
 749                             m = next ) {
 750                                 next = m->lm_next;
 751                                 if ( difftime(c_time, m->lm_time) > remove_threshold) {
 752                                         if ( prev == NULL ) {
 753                                                 lc->lc_buckets[ i ] = next;
 754                                         } else {
 755                                                 prev->lm_next = next;
 756                                         }
 757                                         lc->lc_memused -= msg_size( m );
 758 #ifdef NEW_LOGGING
 759                                         LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 760                                                 "check_cache_memused: removed %ld\n",
 761                                                 m->lm_msgid ));
 762 #else
 763                                         Debug( LDAP_DEBUG_TRACE,
 764                                             "ccm: removed %d\n",
 765                                             m->lm_msgid, 0, 0 );
 766 #endif
 767                                         ldap_msgfree( m );
 768                                 } else {
 769                                         prev = m;
 770                                 }
 771                         }
 772                 }
 773                 remove_threshold *= THRESHOLD_FACTOR;
 774         }
 775
 776 #ifdef NEW_LOGGING
 777         LDAP_LOG (( "cache", LDAP_LEVEL_DETAIL1,
 778                 "check_cache_memused: reduced usage to %ld bytes\n",
 779                 lc->lc_memused ));
 780 #else
 781         Debug( LDAP_DEBUG_TRACE, "ccm: reduced usage to %ld bytes\n",
 782             lc->lc_memused, 0, 0 );
 783 #endif
 784 }
 785
 786 #endif /* !NO_CACHE */