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