1 /* 2 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 #pragma ident "%Z%%M% %I% %E% SMI" 6 7 /* 8 * The contents of this file are subject to the Netscape Public 9 * License Version 1.1 (the "License"); you may not use this file 10 * except in compliance with the License. You may obtain a copy of 11 * the License at http://www.mozilla.org/NPL/ 12 * 13 * Software distributed under the License is distributed on an "AS 14 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or 15 * implied. See the License for the specific language governing 16 * rights and limitations under the License. 17 * 18 * The Original Code is Mozilla Communicator client code, released 19 * March 31, 1998. 20 * 21 * The Initial Developer of the Original Code is Netscape 22 * Communications Corporation. Portions created by Netscape are 23 * Copyright (C) 1998-1999 Netscape Communications Corporation. All 24 * Rights Reserved. 25 * 26 * Contributor(s): 27 */ 28 /* 29 * 30 * memcache.c - routines that implement an in-memory cache. 31 * 32 * To Do: 1) ber_dup_ext(). 33 * 2) referrals and reference? 34 */ 35 36 #include <assert.h> 37 #include "ldap-int.h" 38 39 /* 40 * Extra size allocated to BerElement. 41 * XXXmcs: must match EXBUFSIZ in liblber/io.c? 42 */ 43 #define EXTRA_SIZE 1024 44 45 /* Mode constants for function memcache_access() */ 46 #define MEMCACHE_ACCESS_ADD 0 47 #define MEMCACHE_ACCESS_APPEND 1 48 #define MEMCACHE_ACCESS_APPEND_LAST 2 49 #define MEMCACHE_ACCESS_FIND 3 50 #define MEMCACHE_ACCESS_DELETE 4 51 #define MEMCACHE_ACCESS_DELETE_ALL 5 52 #define MEMCACHE_ACCESS_UPDATE 6 53 #define MEMCACHE_ACCESS_FLUSH 7 54 #define MEMCACHE_ACCESS_FLUSH_ALL 8 55 #define MEMCACHE_ACCESS_FLUSH_LRU 9 56 57 /* Mode constants for function memcache_adj_size */ 58 #define MEMCACHE_SIZE_DEDUCT 0 59 #define MEMCACHE_SIZE_ADD 1 60 61 #define MEMCACHE_SIZE_ENTRIES 1 62 #define MEMCACHE_SIZE_NON_ENTRIES 2 63 64 /* Size used for calculation if given size of cache is 0 */ 65 #define MEMCACHE_DEF_SIZE 131072 /* 128K bytes */ 66 67 /* Index into different list structure */ 68 #define LIST_TTL 0 69 #define LIST_LRU 1 70 #define LIST_TMP 2 71 #define LIST_TOTAL 3 72 73 74 static char *emptyStr = ""; 75 76 /* Macros to make code more readable */ 77 #define NSLDAPI_VALID_MEMCACHE_POINTER( cp ) ( (cp) != NULL ) 78 #define NSLDAPI_STR_NONNULL( s ) ( (s) ? (s) : emptyStr ) 79 #define NSLDAPI_SAFE_STRLEN( s ) ( (s) ? strlen((s)) + 1 : 1 ) 80 81 /* Macros dealing with mutex */ 82 #define LDAP_MEMCACHE_MUTEX_LOCK( c ) \ 83 if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_lock ) { \ 84 ((c)->ldmemc_lock_fns).ltf_mutex_lock( (c)->ldmemc_lock ); \ 85 } 86 87 #define LDAP_MEMCACHE_MUTEX_UNLOCK( c ) \ 88 if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_unlock ) { \ 89 ((c)->ldmemc_lock_fns).ltf_mutex_unlock( (c)->ldmemc_lock ); \ 90 } 91 92 #define LDAP_MEMCACHE_MUTEX_ALLOC( c ) \ 93 ((c) && ((c)->ldmemc_lock_fns).ltf_mutex_alloc ? \ 94 ((c)->ldmemc_lock_fns).ltf_mutex_alloc() : NULL) 95 96 #define LDAP_MEMCACHE_MUTEX_FREE( c ) \ 97 if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_free ) { \ 98 ((c)->ldmemc_lock_fns).ltf_mutex_free( (c)->ldmemc_lock ); \ 99 } 100 101 /* Macros used for triming unnecessary spaces in a basedn */ 102 #define NSLDAPI_IS_SPACE( c ) \ 103 (((c) == ' ') || ((c) == '\t') || ((c) == '\n')) 104 105 #define NSLDAPI_IS_SEPARATER( c ) \ 106 ((c) == ',') 107 108 /* Hash table callback function pointer definition */ 109 typedef int (*HashFuncPtr)(int table_size, void *key); 110 typedef int (*PutDataPtr)(void **ppTableData, void *key, void *pData); 111 typedef int (*GetDataPtr)(void *pTableData, void *key, void **ppData); 112 typedef int (*RemoveDataPtr)(void **ppTableData, void *key, void **ppData); 113 typedef int (*MiscFuncPtr)(void **ppTableData, void *key, void *pData); 114 typedef void (*ClrTableNodePtr)(void **ppTableData, void *pData); 115 116 /* Structure of a node in a hash table */ 117 typedef struct HashTableNode_struct { 118 void *pData; 119 } HashTableNode; 120 121 /* Structure of a hash table */ 122 typedef struct HashTable_struct { 123 HashTableNode *table; 124 int size; 125 HashFuncPtr hashfunc; 126 PutDataPtr putdata; 127 GetDataPtr getdata; 128 MiscFuncPtr miscfunc; 129 RemoveDataPtr removedata; 130 ClrTableNodePtr clrtablenode; 131 } HashTable; 132 133 /* Structure uniquely identifies a search request */ 134 typedef struct ldapmemcacheReqId_struct { 135 LDAP *ldmemcrid_ld; 136 int ldmemcrid_msgid; 137 } ldapmemcacheReqId; 138 139 /* Structure representing a ldap handle associated to memcache */ 140 typedef struct ldapmemcacheld_struct { 141 LDAP *ldmemcl_ld; 142 struct ldapmemcacheld_struct *ldmemcl_next; 143 } ldapmemcacheld; 144 145 /* Structure representing header of a search result */ 146 typedef struct ldapmemcacheRes_struct { 147 char *ldmemcr_basedn; 148 unsigned long ldmemcr_crc_key; 149 unsigned long ldmemcr_resSize; 150 unsigned long ldmemcr_timestamp; 151 LDAPMessage *ldmemcr_resHead; 152 LDAPMessage *ldmemcr_resTail; 153 ldapmemcacheReqId ldmemcr_req_id; 154 struct ldapmemcacheRes_struct *ldmemcr_next[LIST_TOTAL]; 155 struct ldapmemcacheRes_struct *ldmemcr_prev[LIST_TOTAL]; 156 struct ldapmemcacheRes_struct *ldmemcr_htable_next; 157 } ldapmemcacheRes; 158 159 /* Structure for memcache statistics */ 160 typedef struct ldapmemcacheStats_struct { 161 unsigned long ldmemcstat_tries; 162 unsigned long ldmemcstat_hits; 163 } ldapmemcacheStats; 164 165 /* Structure of a memcache object */ 166 struct ldapmemcache { 167 unsigned long ldmemc_ttl; 168 unsigned long ldmemc_size; 169 unsigned long ldmemc_size_used; 170 unsigned long ldmemc_size_entries; 171 char **ldmemc_basedns; 172 void *ldmemc_lock; 173 ldapmemcacheld *ldmemc_lds; 174 HashTable *ldmemc_resTmp; 175 HashTable *ldmemc_resLookup; 176 ldapmemcacheRes *ldmemc_resHead[LIST_TOTAL]; 177 ldapmemcacheRes *ldmemc_resTail[LIST_TOTAL]; 178 struct ldap_thread_fns ldmemc_lock_fns; 179 ldapmemcacheStats ldmemc_stats; 180 }; 181 182 /* Function prototypes */ 183 static int memcache_exist(LDAP *ld); 184 static int memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg); 185 static int memcache_compare_dn(const char *main_dn, const char *dn, int scope); 186 static int memcache_dup_message(LDAPMessage *res, int msgid, int fromcache, 187 LDAPMessage **ppResCopy, unsigned long *pSize); 188 static BerElement* memcache_ber_dup(BerElement* pBer, unsigned long *pSize); 189 190 static void memcache_trim_basedn_spaces(char *basedn); 191 static int memcache_validate_basedn(LDAPMemCache *cache, const char *basedn); 192 static int memcache_get_ctrls_len(LDAPControl **ctrls); 193 static void memcache_append_ctrls(char *buf, LDAPControl **serverCtrls, 194 LDAPControl **clientCtrls); 195 static int memcache_adj_size(LDAPMemCache *cache, unsigned long size, 196 int usageFlags, int bAdd); 197 static int memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes); 198 static int memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes, 199 unsigned long curTime); 200 static int memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, 201 int index); 202 static int memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg, 203 unsigned long size); 204 static int memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, 205 int index); 206 static int memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes); 207 static int memcache_add(LDAP *ld, unsigned long key, int msgid, 208 const char *basedn); 209 static int memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes); 210 static int memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes); 211 static int memcache_remove(LDAP *ld, int msgid); 212 #if 0 /* function not used */ 213 static int memcache_remove_all(LDAP *ld); 214 #endif /* 0 */ 215 static int memcache_access(LDAPMemCache *cache, int mode, 216 void *pData1, void *pData2, void *pData3); 217 #ifdef LDAP_DEBUG 218 static void memcache_print_list( LDAPMemCache *cache, int index ); 219 static void memcache_report_statistics( LDAPMemCache *cache ); 220 #endif /* LDAP_DEBUG */ 221 222 static int htable_calculate_size(int sizelimit); 223 static int htable_sizeinbytes(HashTable *pTable); 224 static int htable_put(HashTable *pTable, void *key, void *pData); 225 static int htable_get(HashTable *pTable, void *key, void **ppData); 226 static int htable_misc(HashTable *pTable, void *key, void *pData); 227 static int htable_remove(HashTable *pTable, void *key, void **ppData); 228 static int htable_removeall(HashTable *pTable, void *pData); 229 static int htable_create(int size_limit, HashFuncPtr hashf, 230 PutDataPtr putDataf, GetDataPtr getDataf, 231 RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef, 232 MiscFuncPtr miscOpf, HashTable **ppTable); 233 static int htable_free(HashTable *pTable); 234 235 static int msgid_hashf(int table_size, void *key); 236 static int msgid_putdata(void **ppTableData, void *key, void *pData); 237 static int msgid_getdata(void *pTableData, void *key, void **ppData); 238 static int msgid_removedata(void **ppTableData, void *key, void **ppData); 239 static int msgid_clear_ld_items(void **ppTableData, void *key, void *pData); 240 static void msgid_clearnode(void **ppTableData, void *pData); 241 242 static int attrkey_hashf(int table_size, void *key); 243 static int attrkey_putdata(void **ppTableData, void *key, void *pData); 244 static int attrkey_getdata(void *pTableData, void *key, void **ppData); 245 static int attrkey_removedata(void **ppTableData, void *key, void **ppData); 246 static void attrkey_clearnode(void **ppTableData, void *pData); 247 248 static unsigned long crc32_convert(char *buf, int len); 249 250 /* Create a memcache object. */ 251 int 252 LDAP_CALL 253 ldap_memcache_init( unsigned long ttl, unsigned long size, 254 char **baseDNs, struct ldap_thread_fns *thread_fns, 255 LDAPMemCache **cachep ) 256 { 257 unsigned long total_size = 0; 258 259 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init\n", 0, 0, 0 ); 260 261 if ( cachep == NULL ) { 262 return( LDAP_PARAM_ERROR ); 263 } 264 265 if ((*cachep = (LDAPMemCache*)NSLDAPI_CALLOC(1, 266 sizeof(LDAPMemCache))) == NULL) { 267 return ( LDAP_NO_MEMORY ); 268 } 269 270 total_size += sizeof(LDAPMemCache); 271 272 (*cachep)->ldmemc_ttl = ttl; 273 (*cachep)->ldmemc_size = size; 274 (*cachep)->ldmemc_lds = NULL; 275 276 /* Non-zero default size needed for calculating size of hash tables */ 277 size = (size ? size : MEMCACHE_DEF_SIZE); 278 279 if (thread_fns) { 280 memcpy(&((*cachep)->ldmemc_lock_fns), thread_fns, 281 sizeof(struct ldap_thread_fns)); 282 } else { 283 memset(&((*cachep)->ldmemc_lock_fns), 0, 284 sizeof(struct ldap_thread_fns)); 285 } 286 287 (*cachep)->ldmemc_lock = LDAP_MEMCACHE_MUTEX_ALLOC( *cachep ); 288 289 /* Cache basedns */ 290 if (baseDNs != NULL) { 291 292 int i; 293 294 for (i = 0; baseDNs[i]; i++) { 295 ; 296 } 297 298 (*cachep)->ldmemc_basedns = (char**)NSLDAPI_CALLOC(i + 1, 299 sizeof(char*)); 300 301 if ((*cachep)->ldmemc_basedns == NULL) { 302 ldap_memcache_destroy(*cachep); 303 *cachep = NULL; 304 return ( LDAP_NO_MEMORY ); 305 } 306 307 total_size += (i + 1) * sizeof(char*); 308 309 for (i = 0; baseDNs[i]; i++) { 310 (*cachep)->ldmemc_basedns[i] = nsldapi_strdup(baseDNs[i]); 311 if ((*cachep)->ldmemc_basedns[i] == NULL) 312 return ( LDAP_NO_MEMORY ); 313 total_size += strlen(baseDNs[i]) + 1; 314 } 315 316 (*cachep)->ldmemc_basedns[i] = NULL; 317 } 318 319 /* Create hash table for temporary cache */ 320 if (htable_create(size, msgid_hashf, msgid_putdata, msgid_getdata, 321 msgid_removedata, msgid_clearnode, msgid_clear_ld_items, 322 &((*cachep)->ldmemc_resTmp)) != LDAP_SUCCESS) { 323 ldap_memcache_destroy(*cachep); 324 *cachep = NULL; 325 return( LDAP_NO_MEMORY ); 326 } 327 328 total_size += htable_sizeinbytes((*cachep)->ldmemc_resTmp); 329 330 /* Create hash table for primary cache */ 331 if (htable_create(size, attrkey_hashf, attrkey_putdata, 332 attrkey_getdata, attrkey_removedata, attrkey_clearnode, 333 NULL, &((*cachep)->ldmemc_resLookup)) != LDAP_SUCCESS) { 334 ldap_memcache_destroy(*cachep); 335 *cachep = NULL; 336 return( LDAP_NO_MEMORY ); 337 } 338 339 total_size += htable_sizeinbytes((*cachep)->ldmemc_resLookup); 340 341 /* See if there is enough room so far */ 342 if (memcache_adj_size(*cachep, total_size, MEMCACHE_SIZE_NON_ENTRIES, 343 MEMCACHE_SIZE_ADD) != LDAP_SUCCESS) { 344 ldap_memcache_destroy(*cachep); 345 *cachep = NULL; 346 return( LDAP_SIZELIMIT_EXCEEDED ); 347 } 348 349 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init new cache 0x%x\n", 350 *cachep, 0, 0 ); 351 352 return( LDAP_SUCCESS ); 353 } 354 355 /* Associates a ldap handle to a memcache object. */ 356 int 357 LDAP_CALL 358 ldap_memcache_set( LDAP *ld, LDAPMemCache *cache ) 359 { 360 int nRes = LDAP_SUCCESS; 361 362 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_set\n", 0, 0, 0 ); 363 364 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) ) 365 return( LDAP_PARAM_ERROR ); 366 367 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 368 369 if (ld->ld_memcache != cache) { 370 371 LDAPMemCache *c = ld->ld_memcache; 372 ldapmemcacheld *pCur = NULL; 373 ldapmemcacheld *pPrev = NULL; 374 375 /* First dissociate handle from old cache */ 376 377 LDAP_MEMCACHE_MUTEX_LOCK( c ); 378 379 pCur = (c ? c->ldmemc_lds : NULL); 380 for (; pCur; pCur = pCur->ldmemcl_next) { 381 if (pCur->ldmemcl_ld == ld) 382 break; 383 pPrev = pCur; 384 } 385 386 if (pCur) { 387 388 ldapmemcacheReqId reqid; 389 390 reqid.ldmemcrid_ld = ld; 391 reqid.ldmemcrid_msgid = -1; 392 htable_misc(c->ldmemc_resTmp, (void*)&reqid, (void*)c); 393 394 if (pPrev) 395 pPrev->ldmemcl_next = pCur->ldmemcl_next; 396 else 397 c->ldmemc_lds = pCur->ldmemcl_next; 398 NSLDAPI_FREE(pCur); 399 pCur = NULL; 400 401 memcache_adj_size(c, sizeof(ldapmemcacheld), 402 MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT); 403 } 404 405 LDAP_MEMCACHE_MUTEX_UNLOCK( c ); 406 407 ld->ld_memcache = NULL; 408 409 /* Exit if no new cache is specified */ 410 if (cache == NULL) { 411 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 412 return( LDAP_SUCCESS ); 413 } 414 415 /* Then associate handle with new cache */ 416 417 LDAP_MEMCACHE_MUTEX_LOCK( cache ); 418 419 if ((nRes = memcache_adj_size(cache, sizeof(ldapmemcacheld), 420 MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_ADD)) != LDAP_SUCCESS) { 421 LDAP_MEMCACHE_MUTEX_UNLOCK( cache ); 422 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 423 return nRes; 424 } 425 426 pCur = (ldapmemcacheld*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheld)); 427 if (pCur == NULL) { 428 memcache_adj_size(cache, sizeof(ldapmemcacheld), 429 MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT); 430 nRes = LDAP_NO_MEMORY; 431 } else { 432 pCur->ldmemcl_ld = ld; 433 pCur->ldmemcl_next = cache->ldmemc_lds; 434 cache->ldmemc_lds = pCur; 435 ld->ld_memcache = cache; 436 } 437 438 LDAP_MEMCACHE_MUTEX_UNLOCK( cache ); 439 } 440 441 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 442 443 return nRes; 444 } 445 446 /* Retrieves memcache with which the ldap handle has been associated. */ 447 int 448 LDAP_CALL 449 ldap_memcache_get( LDAP *ld, LDAPMemCache **cachep ) 450 { 451 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_get ld: 0x%x\n", ld, 0, 0 ); 452 453 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cachep == NULL ) { 454 return( LDAP_PARAM_ERROR ); 455 } 456 457 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 458 *cachep = ld->ld_memcache; 459 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 460 461 return( LDAP_SUCCESS ); 462 } 463 464 /* 465 * Function that stays inside libldap and proactively expires items from 466 * the given cache. This should be called from a newly created thread since 467 * it will not return until after ldap_memcache_destroy() is called. 468 */ 469 void 470 LDAP_CALL 471 ldap_memcache_update( LDAPMemCache *cache ) 472 { 473 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_update: cache 0x%x\n", 474 cache, 0, 0 ); 475 476 if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) { 477 return; 478 } 479 480 LDAP_MEMCACHE_MUTEX_LOCK( cache ); 481 memcache_access(cache, MEMCACHE_ACCESS_UPDATE, NULL, NULL, NULL); 482 LDAP_MEMCACHE_MUTEX_UNLOCK( cache ); 483 } 484 485 /* Removes specified entries from given memcache. */ 486 void 487 LDAP_CALL 488 ldap_memcache_flush( LDAPMemCache *cache, char *dn, int scope ) 489 { 490 LDAPDebug( LDAP_DEBUG_TRACE, 491 "ldap_memcache_flush( cache: 0x%x, dn: %s, scope: %d)\n", 492 cache, ( dn == NULL ) ? "(null)" : dn, scope ); 493 494 if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) { 495 return; 496 } 497 498 LDAP_MEMCACHE_MUTEX_LOCK( cache ); 499 500 if (!dn) { 501 memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL); 502 } else { 503 memcache_access(cache, MEMCACHE_ACCESS_FLUSH, 504 (void*)dn, (void*)(uintptr_t)scope, NULL); 505 } 506 507 LDAP_MEMCACHE_MUTEX_UNLOCK( cache ); 508 } 509 510 /* Destroys the given memcache. */ 511 void 512 LDAP_CALL 513 ldap_memcache_destroy( LDAPMemCache *cache ) 514 { 515 int i = 0; 516 unsigned long size = sizeof(LDAPMemCache); 517 ldapmemcacheld *pNode = NULL, *pNextNode = NULL; 518 519 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_destroy( 0x%x )\n", 520 cache, 0, 0 ); 521 522 if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) { 523 return; 524 } 525 526 /* Dissociate all ldap handes from this cache. */ 527 LDAP_MEMCACHE_MUTEX_LOCK( cache ); 528 529 for (pNode = cache->ldmemc_lds; pNode; pNode = pNextNode, i++) { 530 LDAP_MUTEX_LOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK ); 531 cache->ldmemc_lds = pNode->ldmemcl_next; 532 pNode->ldmemcl_ld->ld_memcache = NULL; 533 LDAP_MUTEX_UNLOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK ); 534 pNextNode = pNode->ldmemcl_next; 535 NSLDAPI_FREE(pNode); 536 } 537 538 size += i * sizeof(ldapmemcacheld); 539 540 LDAP_MEMCACHE_MUTEX_UNLOCK( cache ); 541 542 /* Free array of basedns */ 543 if (cache->ldmemc_basedns) { 544 for (i = 0; cache->ldmemc_basedns[i]; i++) { 545 size += strlen(cache->ldmemc_basedns[i]) + 1; 546 NSLDAPI_FREE(cache->ldmemc_basedns[i]); 547 } 548 size += (i + 1) * sizeof(char*); 549 NSLDAPI_FREE(cache->ldmemc_basedns); 550 } 551 552 /* Free hash table used for temporary cache */ 553 if (cache->ldmemc_resTmp) { 554 size += htable_sizeinbytes(cache->ldmemc_resTmp); 555 memcache_access(cache, MEMCACHE_ACCESS_DELETE_ALL, NULL, NULL, NULL); 556 htable_free(cache->ldmemc_resTmp); 557 } 558 559 /* Free hash table used for primary cache */ 560 if (cache->ldmemc_resLookup) { 561 size += htable_sizeinbytes(cache->ldmemc_resLookup); 562 memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL); 563 htable_free(cache->ldmemc_resLookup); 564 } 565 566 memcache_adj_size(cache, size, MEMCACHE_SIZE_NON_ENTRIES, 567 MEMCACHE_SIZE_DEDUCT); 568 569 LDAP_MEMCACHE_MUTEX_FREE( cache ); 570 571 NSLDAPI_FREE(cache); 572 } 573 574 /************************* Internal API Functions ****************************/ 575 576 /* Creates an integer key by applying the Cyclic Reduntency Check algorithm on 577 a long string formed by concatenating all the search parameters plus the 578 current bind DN. The key is used in the cache for looking up cached 579 entries. It is assumed that the CRC algorithm will generate 580 different integers from different byte strings. */ 581 int 582 ldap_memcache_createkey(LDAP *ld, const char *base, int scope, 583 const char *filter, char **attrs, 584 int attrsonly, LDAPControl **serverctrls, 585 LDAPControl **clientctrls, unsigned long *keyp) 586 { 587 int nRes, i, j, i_smallest; 588 int len; 589 int defport; 590 char buf[50]; 591 char *tmp, *defhost, *binddn, *keystr, *tmpbase; 592 593 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (keyp == NULL) ) 594 return( LDAP_PARAM_ERROR ); 595 596 *keyp = 0; 597 598 if (!memcache_exist(ld)) 599 return( LDAP_LOCAL_ERROR ); 600 601 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 602 LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache ); 603 nRes = memcache_validate_basedn(ld->ld_memcache, base); 604 LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache ); 605 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 606 607 if (nRes != LDAP_SUCCESS) 608 return nRes; 609 610 defhost = NSLDAPI_STR_NONNULL(ld->ld_defhost); 611 defport = ld->ld_defport; 612 tmpbase = nsldapi_strdup(NSLDAPI_STR_NONNULL(base)); 613 if (tmpbase == NULL) 614 return( LDAP_LOCAL_ERROR ); 615 memcache_trim_basedn_spaces(tmpbase); 616 617 if ((binddn = nsldapi_get_binddn(ld)) == NULL) 618 binddn = ""; 619 620 sprintf(buf, "%i\n%i\n%i\n", defport, scope, (attrsonly ? 1 : 0)); 621 len = NSLDAPI_SAFE_STRLEN(buf) + NSLDAPI_SAFE_STRLEN(tmpbase) + 622 NSLDAPI_SAFE_STRLEN(filter) + NSLDAPI_SAFE_STRLEN(defhost) + 623 NSLDAPI_SAFE_STRLEN(binddn); 624 625 if (attrs) { 626 for (i = 0; attrs[i]; i++) { 627 628 for (i_smallest = j = i; attrs[j]; j++) { 629 if (strcasecmp(attrs[i_smallest], attrs[j]) > 0) 630 i_smallest = j; 631 } 632 633 if (i != i_smallest) { 634 tmp = attrs[i]; 635 attrs[i] = attrs[i_smallest]; 636 attrs[i_smallest] = tmp; 637 } 638 639 len += NSLDAPI_SAFE_STRLEN(attrs[i]); 640 } 641 } else { 642 len += 1; 643 } 644 645 len += memcache_get_ctrls_len(serverctrls) + 646 memcache_get_ctrls_len(clientctrls) + 1; 647 648 if ((keystr = (char*)NSLDAPI_CALLOC(len, sizeof(char))) == NULL) { 649 if (defhost != emptyStr) 650 NSLDAPI_FREE(defhost); 651 NSLDAPI_FREE(tmpbase); 652 return( LDAP_NO_MEMORY ); 653 } 654 655 sprintf(keystr, "%s\n%s\n%s\n%s\n%s\n", binddn, tmpbase, 656 NSLDAPI_STR_NONNULL(defhost), NSLDAPI_STR_NONNULL(filter), 657 NSLDAPI_STR_NONNULL(buf)); 658 659 if (attrs) { 660 for (i = 0; attrs[i]; i++) { 661 strcat(keystr, NSLDAPI_STR_NONNULL(attrs[i])); 662 strcat(keystr, "\n"); 663 } 664 } else { 665 strcat(keystr, "\n"); 666 } 667 668 for (tmp = keystr; *tmp; 669 *tmp += (*tmp >= 'a' && *tmp <= 'z' ? 'A'-'a' : 0), tmp++) { 670 ; 671 } 672 673 memcache_append_ctrls(keystr, serverctrls, clientctrls); 674 675 /* CRC algorithm */ 676 *keyp = crc32_convert(keystr, len); 677 678 NSLDAPI_FREE(keystr); 679 NSLDAPI_FREE(tmpbase); 680 681 return LDAP_SUCCESS; 682 } 683 684 /* Searches the cache for the right cached entries, and if found, attaches 685 them to the given ldap handle. This function relies on locking by the 686 caller. */ 687 int 688 ldap_memcache_result(LDAP *ld, int msgid, unsigned long key) 689 { 690 int nRes; 691 LDAPMessage *pMsg = NULL; 692 693 LDAPDebug( LDAP_DEBUG_TRACE, 694 "ldap_memcache_result( ld: 0x%x, msgid: %d, key: 0x%8.8lx)\n", 695 ld, msgid, key ); 696 697 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) { 698 return( LDAP_PARAM_ERROR ); 699 } 700 701 if (!memcache_exist(ld)) { 702 return( LDAP_LOCAL_ERROR ); 703 } 704 705 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 706 LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache ); 707 708 /* Search the cache and append the results to ld if found */ 709 ++ld->ld_memcache->ldmemc_stats.ldmemcstat_tries; 710 if ((nRes = memcache_search(ld, key, &pMsg)) == LDAP_SUCCESS) { 711 nRes = memcache_add_to_ld(ld, msgid, pMsg); 712 ++ld->ld_memcache->ldmemc_stats.ldmemcstat_hits; 713 LDAPDebug( LDAP_DEBUG_TRACE, 714 "ldap_memcache_result: key 0x%8.8lx found in cache\n", 715 key, 0, 0 ); 716 } else { 717 LDAPDebug( LDAP_DEBUG_TRACE, 718 "ldap_memcache_result: key 0x%8.8lx not found in cache\n", 719 key, 0, 0 ); 720 } 721 722 #ifdef LDAP_DEBUG 723 memcache_print_list( ld->ld_memcache, LIST_LRU ); 724 memcache_report_statistics( ld->ld_memcache ); 725 #endif /* LDAP_DEBUG */ 726 727 LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache ); 728 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 729 730 return nRes; 731 } 732 733 /* Creates a new header in the cache so that entries arriving from the 734 directory server can later be cached under the header. */ 735 int 736 ldap_memcache_new(LDAP *ld, int msgid, unsigned long key, const char *basedn) 737 { 738 int nRes; 739 740 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) ) { 741 return( LDAP_PARAM_ERROR ); 742 } 743 744 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 745 746 if (!memcache_exist(ld)) { 747 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 748 return( LDAP_LOCAL_ERROR ); 749 } 750 751 LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache ); 752 nRes = memcache_add(ld, key, msgid, basedn); 753 LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache ); 754 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 755 756 return nRes; 757 } 758 759 /* Appends a chain of entries to an existing cache header. Parameter "bLast" 760 indicates whether there will be more entries arriving for the search in 761 question. */ 762 int 763 ldap_memcache_append(LDAP *ld, int msgid, int bLast, LDAPMessage *result) 764 { 765 int nRes = LDAP_SUCCESS; 766 767 LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_append( ld: 0x%x, ", ld, 0, 0 ); 768 LDAPDebug( LDAP_DEBUG_TRACE, "msgid %d, bLast: %d, result: 0x%x)\n", 769 msgid, bLast, result ); 770 771 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || !result ) { 772 return( LDAP_PARAM_ERROR ); 773 } 774 775 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 776 777 if (!memcache_exist(ld)) { 778 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 779 return( LDAP_LOCAL_ERROR ); 780 } 781 782 LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache ); 783 784 if (!bLast) 785 nRes = memcache_append(ld, msgid, result); 786 else 787 nRes = memcache_append_last(ld, msgid, result); 788 789 LDAPDebug( LDAP_DEBUG_TRACE, 790 "ldap_memcache_append: %s result for msgid %d\n", 791 ( nRes == LDAP_SUCCESS ) ? "added" : "failed to add", msgid , 0 ); 792 793 LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache ); 794 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 795 796 return nRes; 797 } 798 799 /* Removes partially cached results for a search as a result of calling 800 ldap_abandon() by the client. */ 801 int 802 ldap_memcache_abandon(LDAP *ld, int msgid) 803 { 804 int nRes; 805 806 if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) { 807 return( LDAP_PARAM_ERROR ); 808 } 809 810 LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK ); 811 812 if (!memcache_exist(ld)) { 813 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 814 return( LDAP_LOCAL_ERROR ); 815 } 816 817 LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache ); 818 nRes = memcache_remove(ld, msgid); 819 LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache ); 820 LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK ); 821 822 return nRes; 823 } 824 825 /*************************** helper functions *******************************/ 826 827 /* Removes extraneous spaces in a basedn so that basedns differ by only those 828 spaces will be treated as equal. Extraneous spaces are those that 829 precedes the basedn and those that follow a comma. */ 830 /* 831 * XXXmcs: this is a bit too agressive... we need to deal with the fact that 832 * commas and spaces may be quoted, in which case it is wrong to remove them. 833 */ 834 static void 835 memcache_trim_basedn_spaces(char *basedn) 836 { 837 char *pRead, *pWrite; 838 839 if (!basedn) 840 return; 841 842 for (pWrite = pRead = basedn; *pRead; ) { 843 for (; *pRead && NSLDAPI_IS_SPACE(*pRead); pRead++) { 844 ; 845 } 846 for (; *pRead && !NSLDAPI_IS_SEPARATER(*pRead); 847 *(pWrite++) = *(pRead++)) { 848 ; 849 } 850 *(pWrite++) = (*pRead ? *(pRead++) : *pRead); 851 } 852 } 853 854 /* Verifies whether the results of a search should be cached or not by 855 checking if the search's basedn falls under any of the basedns for which 856 the memcache is responsible. */ 857 static int 858 memcache_validate_basedn(LDAPMemCache *cache, const char *basedn) 859 { 860 int i; 861 862 if ( cache->ldmemc_basedns == NULL ) { 863 return( LDAP_SUCCESS ); 864 } 865 866 #if 1 867 if (basedn == NULL) { 868 basedn = ""; 869 } 870 #else 871 /* XXXmcs: I do not understand this code... */ 872 if (basedn == NULL) 873 return (cache->ldmemc_basedns && cache->ldmemc_basedns[0] ? 874 LDAP_OPERATIONS_ERROR : LDAP_SUCCESS); 875 } 876 #endif 877 878 for (i = 0; cache->ldmemc_basedns[i]; i++) { 879 if (memcache_compare_dn(basedn, cache->ldmemc_basedns[i], 880 LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) { 881 return( LDAP_SUCCESS ); 882 } 883 } 884 885 return( LDAP_OPERATIONS_ERROR ); 886 } 887 888 /* Calculates the length of the buffer needed to concatenate the contents of 889 a ldap control. */ 890 static int 891 memcache_get_ctrls_len(LDAPControl **ctrls) 892 { 893 int len = 0, i; 894 895 if (ctrls) { 896 for (i = 0; ctrls[i]; i++) { 897 len += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) + 898 (ctrls[i]->ldctl_value).bv_len + 4; 899 } 900 } 901 902 return len; 903 } 904 905 /* Contenates the contents of client and server controls to a buffer. */ 906 static void 907 memcache_append_ctrls(char *buf, LDAPControl **serverCtrls, 908 LDAPControl **clientCtrls) 909 { 910 int i, j; 911 char *pCh = buf + strlen(buf); 912 LDAPControl **ctrls; 913 914 for (j = 0; j < 2; j++) { 915 916 if ((ctrls = (j ? clientCtrls : serverCtrls)) == NULL) 917 continue; 918 919 for (i = 0; ctrls[i]; i++) { 920 sprintf(pCh, "%s\n", NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)); 921 pCh += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) + 1; 922 if ((ctrls[i]->ldctl_value).bv_len > 0) { 923 memcpy(pCh, (ctrls[i]->ldctl_value).bv_val, 924 (ctrls[i]->ldctl_value).bv_len); 925 pCh += (ctrls[i]->ldctl_value).bv_len; 926 } 927 sprintf(pCh, "\n%i\n", (ctrls[i]->ldctl_iscritical ? 1 : 0)); 928 pCh += 3; 929 } 930 } 931 } 932 933 /* Increases or decreases the size (in bytes) the given memcache currently 934 uses. If the size goes over the limit, the function returns an error. */ 935 static int 936 memcache_adj_size(LDAPMemCache *cache, unsigned long size, 937 int usageFlags, int bAdd) 938 { 939 LDAPDebug( LDAP_DEBUG_TRACE, 940 "memcache_adj_size: attempting to %s %ld %s bytes...\n", 941 bAdd ? "add" : "remove", size, 942 ( usageFlags & MEMCACHE_SIZE_ENTRIES ) ? "entry" : "non-entry" ); 943 944 if (bAdd) { 945 cache->ldmemc_size_used += size; 946 if ((cache->ldmemc_size > 0) && 947 (cache->ldmemc_size_used > cache->ldmemc_size)) { 948 949 if (size > cache->ldmemc_size_entries) { 950 cache->ldmemc_size_used -= size; 951 LDAPDebug( LDAP_DEBUG_TRACE, 952 "memcache_adj_size: failed (size > size_entries %ld).\n", 953 cache->ldmemc_size_entries, 0, 0 ); 954 return( LDAP_SIZELIMIT_EXCEEDED ); 955 } 956 957 while (cache->ldmemc_size_used > cache->ldmemc_size) { 958 if (memcache_access(cache, MEMCACHE_ACCESS_FLUSH_LRU, 959 NULL, NULL, NULL) != LDAP_SUCCESS) { 960 cache->ldmemc_size_used -= size; 961 LDAPDebug( LDAP_DEBUG_TRACE, 962 "memcache_adj_size: failed (LRU flush failed).\n", 963 0, 0, 0 ); 964 return( LDAP_SIZELIMIT_EXCEEDED ); 965 } 966 } 967 } 968 if (usageFlags & MEMCACHE_SIZE_ENTRIES) 969 cache->ldmemc_size_entries += size; 970 } else { 971 cache->ldmemc_size_used -= size; 972 assert(cache->ldmemc_size_used >= 0); 973 if (usageFlags & MEMCACHE_SIZE_ENTRIES) 974 cache->ldmemc_size_entries -= size; 975 } 976 977 #ifdef LDAP_DEBUG 978 if ( cache->ldmemc_size == 0 ) { /* no size limit */ 979 LDAPDebug( LDAP_DEBUG_TRACE, 980 "memcache_adj_size: succeeded (new size: %ld bytes).\n", 981 cache->ldmemc_size_used, 0, 0 ); 982 } else { 983 LDAPDebug( LDAP_DEBUG_TRACE, 984 "memcache_adj_size: succeeded (new size: %ld bytes, " 985 "free space: %ld bytes).\n", cache->ldmemc_size_used, 986 cache->ldmemc_size - cache->ldmemc_size_used, 0 ); 987 } 988 #endif /* LDAP_DEBUG */ 989 990 return( LDAP_SUCCESS ); 991 } 992 993 /* Searches the cache for results for a particular search identified by 994 parameter "key", which was generated ldap_memcache_createkey(). */ 995 static int 996 memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes) 997 { 998 int nRes; 999 ldapmemcacheRes *pRes; 1000 1001 *ppRes = NULL; 1002 1003 if (!memcache_exist(ld)) 1004 return LDAP_LOCAL_ERROR; 1005 1006 nRes = memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_FIND, 1007 (void*)&key, (void*)(&pRes), NULL); 1008 1009 if (nRes != LDAP_SUCCESS) 1010 return nRes; 1011 1012 *ppRes = pRes->ldmemcr_resHead; 1013 assert((pRes->ldmemcr_req_id).ldmemcrid_msgid == -1); 1014 1015 return( LDAP_SUCCESS ); 1016 } 1017 1018 /* Adds a new header into the cache as a place holder for entries 1019 arriving later. */ 1020 static int 1021 memcache_add(LDAP *ld, unsigned long key, int msgid, 1022 const char *basedn) 1023 { 1024 ldapmemcacheReqId reqid; 1025 1026 if (!memcache_exist(ld)) 1027 return LDAP_LOCAL_ERROR; 1028 1029 reqid.ldmemcrid_msgid = msgid; 1030 reqid.ldmemcrid_ld = ld; 1031 1032 return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_ADD, 1033 (void*)&key, (void*)&reqid, (void*)basedn); 1034 } 1035 1036 /* Appends search entries arriving from the dir server to the cache. */ 1037 static int 1038 memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes) 1039 { 1040 ldapmemcacheReqId reqid; 1041 1042 if (!memcache_exist(ld)) 1043 return LDAP_LOCAL_ERROR; 1044 1045 reqid.ldmemcrid_msgid = msgid; 1046 reqid.ldmemcrid_ld = ld; 1047 1048 return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND, 1049 (void*)&reqid, (void*)pRes, NULL); 1050 } 1051 1052 /* Same as memcache_append(), but the entries being appended are the 1053 last from the dir server. Once all entries for a search have arrived, 1054 the entries are moved from secondary to primary cache, and a time 1055 stamp is given to the entries. */ 1056 static int 1057 memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes) 1058 { 1059 ldapmemcacheReqId reqid; 1060 1061 if (!memcache_exist(ld)) 1062 return LDAP_LOCAL_ERROR; 1063 1064 reqid.ldmemcrid_msgid = msgid; 1065 reqid.ldmemcrid_ld = ld; 1066 1067 return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND_LAST, 1068 (void*)&reqid, (void*)pRes, NULL); 1069 } 1070 1071 /* Removes entries from the temporary cache. */ 1072 static int 1073 memcache_remove(LDAP *ld, int msgid) 1074 { 1075 ldapmemcacheReqId reqid; 1076 1077 if (!memcache_exist(ld)) 1078 return LDAP_LOCAL_ERROR; 1079 1080 reqid.ldmemcrid_msgid = msgid; 1081 reqid.ldmemcrid_ld = ld; 1082 1083 return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE, 1084 (void*)&reqid, NULL, NULL); 1085 } 1086 1087 #if 0 /* this function is not used */ 1088 /* Wipes out everything in the temporary cache directory. */ 1089 static int 1090 memcache_remove_all(LDAP *ld) 1091 { 1092 if (!memcache_exist(ld)) 1093 return LDAP_LOCAL_ERROR; 1094 1095 return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE_ALL, 1096 NULL, NULL, NULL); 1097 } 1098 #endif /* 0 */ 1099 1100 /* Returns TRUE or FALSE */ 1101 static int 1102 memcache_exist(LDAP *ld) 1103 { 1104 return (ld->ld_memcache != NULL); 1105 } 1106 1107 /* Attaches cached entries to an ldap handle. */ 1108 static int 1109 memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg) 1110 { 1111 int nRes = LDAP_SUCCESS; 1112 LDAPMessage **r; 1113 LDAPMessage *pCopy; 1114 1115 nRes = memcache_dup_message(pMsg, msgid, 1, &pCopy, NULL); 1116 if (nRes != LDAP_SUCCESS) 1117 return nRes; 1118 1119 for (r = &(ld->ld_responses); *r; r = &((*r)->lm_next)) 1120 if ((*r)->lm_msgid == msgid) 1121 break; 1122 1123 if (*r) 1124 for (r = &((*r)->lm_chain); *r; r = &((*r)->lm_chain)) { 1125 ; 1126 } 1127 1128 *r = pCopy; 1129 1130 return nRes; 1131 } 1132 1133 /* Check if main_dn is included in {dn, scope} */ 1134 static int 1135 memcache_compare_dn(const char *main_dn, const char *dn, int scope) 1136 { 1137 int nRes; 1138 char **components = NULL; 1139 char **main_components = NULL; 1140 1141 components = ldap_explode_dn(dn, 0); 1142 main_components = ldap_explode_dn(main_dn, 0); 1143 1144 if (!components || !main_components) { 1145 nRes = LDAP_COMPARE_TRUE; 1146 } 1147 else { 1148 1149 int i, main_i; 1150 1151 main_i = ldap_count_values(main_components) - 1; 1152 i = ldap_count_values(components) - 1; 1153 1154 for (; i >= 0 && main_i >= 0; i--, main_i--) { 1155 if (strcasecmp(main_components[main_i], components[i])) 1156 break; 1157 } 1158 1159 if (i >= 0 && main_i >= 0) { 1160 nRes = LDAP_COMPARE_FALSE; 1161 } 1162 else if (i < 0 && main_i < 0) { 1163 if (scope != LDAP_SCOPE_ONELEVEL) 1164 nRes = LDAP_COMPARE_TRUE; 1165 else 1166 nRes = LDAP_COMPARE_FALSE; 1167 } 1168 else if (main_i < 0) { 1169 nRes = LDAP_COMPARE_FALSE; 1170 } 1171 else { 1172 if (scope == LDAP_SCOPE_BASE) 1173 nRes = LDAP_COMPARE_FALSE; 1174 else if (scope == LDAP_SCOPE_SUBTREE) 1175 nRes = LDAP_COMPARE_TRUE; 1176 else if (main_i == 0) 1177 nRes = LDAP_COMPARE_TRUE; 1178 else 1179 nRes = LDAP_COMPARE_FALSE; 1180 } 1181 } 1182 1183 if (components) 1184 ldap_value_free(components); 1185 1186 if (main_components) 1187 ldap_value_free(main_components); 1188 1189 return nRes; 1190 } 1191 1192 /* Dup a complete separate copy of a berelement, including the buffers 1193 the berelement points to. */ 1194 static BerElement* 1195 memcache_ber_dup(BerElement* pBer, unsigned long *pSize) 1196 { 1197 BerElement *p = ber_dup(pBer); 1198 1199 *pSize = 0; 1200 1201 if (p) { 1202 1203 *pSize += sizeof(BerElement) + EXTRA_SIZE; 1204 1205 if (p->ber_len <= EXTRA_SIZE) { 1206 p->ber_flags |= LBER_FLAG_NO_FREE_BUFFER; 1207 p->ber_buf = (char*)p + sizeof(BerElement); 1208 } else { 1209 p->ber_flags &= ~LBER_FLAG_NO_FREE_BUFFER; 1210 p->ber_buf = (char*)NSLDAPI_CALLOC(1, p->ber_len); 1211 *pSize += (p->ber_buf ? p->ber_len : 0); 1212 } 1213 1214 if (p->ber_buf) { 1215 p->ber_ptr = p->ber_buf + (pBer->ber_ptr - pBer->ber_buf); 1216 p->ber_end = p->ber_buf + p->ber_len; 1217 memcpy(p->ber_buf, pBer->ber_buf, p->ber_len); 1218 } else { 1219 ber_free(p, 0); 1220 p = NULL; 1221 *pSize = 0; 1222 } 1223 } 1224 1225 return p; 1226 } 1227 1228 /* Dup a entry or a chain of entries. */ 1229 static int 1230 memcache_dup_message(LDAPMessage *res, int msgid, int fromcache, 1231 LDAPMessage **ppResCopy, unsigned long *pSize) 1232 { 1233 int nRes = LDAP_SUCCESS; 1234 unsigned long ber_size; 1235 LDAPMessage *pCur; 1236 LDAPMessage **ppCurNew; 1237 1238 *ppResCopy = NULL; 1239 1240 if (pSize) 1241 *pSize = 0; 1242 1243 /* Make a copy of res */ 1244 for (pCur = res, ppCurNew = ppResCopy; pCur; 1245 pCur = pCur->lm_chain, ppCurNew = &((*ppCurNew)->lm_chain)) { 1246 1247 if ((*ppCurNew = (LDAPMessage*)NSLDAPI_CALLOC(1, 1248 sizeof(LDAPMessage))) == NULL) { 1249 nRes = LDAP_NO_MEMORY; 1250 break; 1251 } 1252 1253 memcpy(*ppCurNew, pCur, sizeof(LDAPMessage)); 1254 (*ppCurNew)->lm_next = NULL; 1255 (*ppCurNew)->lm_ber = memcache_ber_dup(pCur->lm_ber, &ber_size); 1256 (*ppCurNew)->lm_msgid = msgid; 1257 (*ppCurNew)->lm_fromcache = (fromcache != 0); 1258 1259 if (pSize) 1260 *pSize += sizeof(LDAPMessage) + ber_size; 1261 } 1262 1263 if ((nRes != LDAP_SUCCESS) && (*ppResCopy != NULL)) { 1264 ldap_msgfree(*ppResCopy); 1265 *ppResCopy = NULL; 1266 if (pSize) 1267 *pSize = 0; 1268 } 1269 1270 return nRes; 1271 } 1272 1273 /************************* Cache Functions ***********************/ 1274 1275 /* Frees a cache header. */ 1276 static int 1277 memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes) 1278 { 1279 if (pRes) { 1280 1281 unsigned long size = sizeof(ldapmemcacheRes); 1282 1283 if (pRes->ldmemcr_basedn) { 1284 size += strlen(pRes->ldmemcr_basedn) + 1; 1285 NSLDAPI_FREE(pRes->ldmemcr_basedn); 1286 } 1287 1288 if (pRes->ldmemcr_resHead) { 1289 size += pRes->ldmemcr_resSize; 1290 ldap_msgfree(pRes->ldmemcr_resHead); 1291 } 1292 1293 NSLDAPI_FREE(pRes); 1294 1295 memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES, 1296 MEMCACHE_SIZE_DEDUCT); 1297 } 1298 1299 return( LDAP_SUCCESS ); 1300 } 1301 1302 /* Detaches a cache header from the list of headers. */ 1303 static int 1304 memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index) 1305 { 1306 if (pRes->ldmemcr_prev[index]) 1307 pRes->ldmemcr_prev[index]->ldmemcr_next[index] = 1308 pRes->ldmemcr_next[index]; 1309 1310 if (pRes->ldmemcr_next[index]) 1311 pRes->ldmemcr_next[index]->ldmemcr_prev[index] = 1312 pRes->ldmemcr_prev[index]; 1313 1314 if (cache->ldmemc_resHead[index] == pRes) 1315 cache->ldmemc_resHead[index] = pRes->ldmemcr_next[index]; 1316 1317 if (cache->ldmemc_resTail[index] == pRes) 1318 cache->ldmemc_resTail[index] = pRes->ldmemcr_prev[index]; 1319 1320 pRes->ldmemcr_prev[index] = NULL; 1321 pRes->ldmemcr_next[index] = NULL; 1322 1323 return( LDAP_SUCCESS ); 1324 } 1325 1326 /* Inserts a new cache header to a list of headers. */ 1327 static int 1328 memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index) 1329 { 1330 if (cache->ldmemc_resHead[index]) 1331 cache->ldmemc_resHead[index]->ldmemcr_prev[index] = pRes; 1332 else 1333 cache->ldmemc_resTail[index] = pRes; 1334 1335 pRes->ldmemcr_prev[index] = NULL; 1336 pRes->ldmemcr_next[index] = cache->ldmemc_resHead[index]; 1337 cache->ldmemc_resHead[index] = pRes; 1338 1339 return( LDAP_SUCCESS ); 1340 } 1341 1342 /* Appends a chain of entries to the given cache header. */ 1343 static int 1344 memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg, 1345 unsigned long size) 1346 { 1347 if (pRes->ldmemcr_resTail) 1348 pRes->ldmemcr_resTail->lm_chain = pMsg; 1349 else 1350 pRes->ldmemcr_resHead = pMsg; 1351 1352 for (pRes->ldmemcr_resTail = pMsg; 1353 pRes->ldmemcr_resTail->lm_chain; 1354 pRes->ldmemcr_resTail = pRes->ldmemcr_resTail->lm_chain) { 1355 ; 1356 } 1357 1358 pRes->ldmemcr_resSize += size; 1359 1360 return( LDAP_SUCCESS ); 1361 } 1362 1363 1364 #ifdef LDAP_DEBUG 1365 static void 1366 memcache_print_list( LDAPMemCache *cache, int index ) 1367 { 1368 char *name; 1369 ldapmemcacheRes *restmp; 1370 1371 switch( index ) { 1372 case LIST_TTL: 1373 name = "TTL"; 1374 break; 1375 case LIST_LRU: 1376 name = "LRU"; 1377 break; 1378 case LIST_TMP: 1379 name = "TMP"; 1380 break; 1381 case LIST_TOTAL: 1382 name = "TOTAL"; 1383 break; 1384 default: 1385 name = "unknown"; 1386 } 1387 1388 LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x %s list:\n", 1389 cache, name, 0 ); 1390 for ( restmp = cache->ldmemc_resHead[index]; restmp != NULL; 1391 restmp = restmp->ldmemcr_next[index] ) { 1392 LDAPDebug( LDAP_DEBUG_TRACE, 1393 " key: 0x%8.8lx, ld: 0x%x, msgid: %d\n", 1394 restmp->ldmemcr_crc_key, 1395 restmp->ldmemcr_req_id.ldmemcrid_ld, 1396 restmp->ldmemcr_req_id.ldmemcrid_msgid ); 1397 } 1398 LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x end of %s list.\n", 1399 cache, name, 0 ); 1400 } 1401 #endif /* LDAP_DEBUG */ 1402 1403 /* Tells whether a cached result has expired. */ 1404 static int 1405 memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes, 1406 unsigned long curTime) 1407 { 1408 if (!cache->ldmemc_ttl) 1409 return 0; 1410 1411 return ((unsigned long)difftime( 1412 (time_t)curTime, 1413 (time_t)(pRes->ldmemcr_timestamp)) >= 1414 cache->ldmemc_ttl); 1415 } 1416 1417 /* Operates the cache in a central place. */ 1418 static int 1419 memcache_access(LDAPMemCache *cache, int mode, 1420 void *pData1, void *pData2, void *pData3) 1421 { 1422 int nRes = LDAP_SUCCESS; 1423 unsigned long size = 0; 1424 1425 /* Add a new cache header to the cache. */ 1426 if (mode == MEMCACHE_ACCESS_ADD) { 1427 unsigned long key = *((unsigned long*)pData1); 1428 char *basedn = (char*)pData3; 1429 ldapmemcacheRes *pRes = NULL; 1430 1431 nRes = htable_get(cache->ldmemc_resTmp, pData2, (void**)&pRes); 1432 if (nRes == LDAP_SUCCESS) 1433 return( LDAP_ALREADY_EXISTS ); 1434 1435 pRes = (ldapmemcacheRes*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheRes)); 1436 if (pRes == NULL) 1437 return( LDAP_NO_MEMORY ); 1438 1439 pRes->ldmemcr_crc_key = key; 1440 pRes->ldmemcr_req_id = *((ldapmemcacheReqId*)pData2); 1441 pRes->ldmemcr_basedn = (basedn ? nsldapi_strdup(basedn) : NULL); 1442 1443 size += sizeof(ldapmemcacheRes) + strlen(basedn) + 1; 1444 nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES, 1445 MEMCACHE_SIZE_ADD); 1446 if (nRes == LDAP_SUCCESS) 1447 nRes = htable_put(cache->ldmemc_resTmp, pData2, (void*)pRes); 1448 if (nRes == LDAP_SUCCESS) 1449 memcache_add_to_list(cache, pRes, LIST_TMP); 1450 else 1451 memcache_free_entry(cache, pRes); 1452 } 1453 /* Append entries to an existing cache header. */ 1454 else if ((mode == MEMCACHE_ACCESS_APPEND) || 1455 (mode == MEMCACHE_ACCESS_APPEND_LAST)) { 1456 1457 LDAPMessage *pMsg = (LDAPMessage*)pData2; 1458 LDAPMessage *pCopy = NULL; 1459 ldapmemcacheRes *pRes = NULL; 1460 1461 nRes = htable_get(cache->ldmemc_resTmp, pData1, (void**)&pRes); 1462 if (nRes != LDAP_SUCCESS) 1463 return nRes; 1464 1465 nRes = memcache_dup_message(pMsg, pMsg->lm_msgid, 0, &pCopy, &size); 1466 if (nRes != LDAP_SUCCESS) { 1467 nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL); 1468 assert(nRes == LDAP_SUCCESS); 1469 memcache_free_from_list(cache, pRes, LIST_TMP); 1470 memcache_free_entry(cache, pRes); 1471 return nRes; 1472 } 1473 1474 nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES, 1475 MEMCACHE_SIZE_ADD); 1476 if (nRes != LDAP_SUCCESS) { 1477 ldap_msgfree(pCopy); 1478 nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL); 1479 assert(nRes == LDAP_SUCCESS); 1480 memcache_free_from_list(cache, pRes, LIST_TMP); 1481 memcache_free_entry(cache, pRes); 1482 return nRes; 1483 } 1484 1485 memcache_add_res_to_list(pRes, pCopy, size); 1486 1487 if (mode == MEMCACHE_ACCESS_APPEND) 1488 return( LDAP_SUCCESS ); 1489 1490 nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL); 1491 assert(nRes == LDAP_SUCCESS); 1492 memcache_free_from_list(cache, pRes, LIST_TMP); 1493 (pRes->ldmemcr_req_id).ldmemcrid_ld = NULL; 1494 (pRes->ldmemcr_req_id).ldmemcrid_msgid = -1; 1495 pRes->ldmemcr_timestamp = (unsigned long)time(NULL); 1496 1497 if ((nRes = htable_put(cache->ldmemc_resLookup, 1498 (void*)&(pRes->ldmemcr_crc_key), 1499 (void*)pRes)) == LDAP_SUCCESS) { 1500 memcache_add_to_list(cache, pRes, LIST_TTL); 1501 memcache_add_to_list(cache, pRes, LIST_LRU); 1502 } else { 1503 memcache_free_entry(cache, pRes); 1504 } 1505 } 1506 /* Search for cached entries for a particular search. */ 1507 else if (mode == MEMCACHE_ACCESS_FIND) { 1508 1509 ldapmemcacheRes **ppRes = (ldapmemcacheRes**)pData2; 1510 1511 nRes = htable_get(cache->ldmemc_resLookup, pData1, (void**)ppRes); 1512 if (nRes != LDAP_SUCCESS) 1513 return nRes; 1514 1515 if (!memcache_expired(cache, *ppRes, (unsigned long)time(0))) { 1516 memcache_free_from_list(cache, *ppRes, LIST_LRU); 1517 memcache_add_to_list(cache, *ppRes, LIST_LRU); 1518 return( LDAP_SUCCESS ); 1519 } 1520 1521 nRes = htable_remove(cache->ldmemc_resLookup, pData1, NULL); 1522 assert(nRes == LDAP_SUCCESS); 1523 memcache_free_from_list(cache, *ppRes, LIST_TTL); 1524 memcache_free_from_list(cache, *ppRes, LIST_LRU); 1525 memcache_free_entry(cache, *ppRes); 1526 nRes = LDAP_NO_SUCH_OBJECT; 1527 *ppRes = NULL; 1528 } 1529 /* Remove cached entries in the temporary cache. */ 1530 else if (mode == MEMCACHE_ACCESS_DELETE) { 1531 1532 ldapmemcacheRes *pCurRes = NULL; 1533 1534 if ((nRes = htable_remove(cache->ldmemc_resTmp, pData1, 1535 (void**)&pCurRes)) == LDAP_SUCCESS) { 1536 memcache_free_from_list(cache, pCurRes, LIST_TMP); 1537 memcache_free_entry(cache, pCurRes); 1538 } 1539 } 1540 /* Wipe out the temporary cache. */ 1541 else if (mode == MEMCACHE_ACCESS_DELETE_ALL) { 1542 1543 nRes = htable_removeall(cache->ldmemc_resTmp, (void*)cache); 1544 } 1545 /* Remove expired entries from primary cache. */ 1546 else if (mode == MEMCACHE_ACCESS_UPDATE) { 1547 1548 ldapmemcacheRes *pCurRes = cache->ldmemc_resTail[LIST_TTL]; 1549 unsigned long curTime = (unsigned long)time(NULL); 1550 1551 for (; pCurRes; pCurRes = cache->ldmemc_resTail[LIST_TTL]) { 1552 1553 if (!memcache_expired(cache, pCurRes, curTime)) 1554 break; 1555 1556 nRes = htable_remove(cache->ldmemc_resLookup, 1557 (void*)&(pCurRes->ldmemcr_crc_key), NULL); 1558 assert(nRes == LDAP_SUCCESS); 1559 memcache_free_from_list(cache, pCurRes, LIST_TTL); 1560 memcache_free_from_list(cache, pCurRes, LIST_LRU); 1561 memcache_free_entry(cache, pCurRes); 1562 } 1563 } 1564 /* Wipe out the primary cache. */ 1565 else if (mode == MEMCACHE_ACCESS_FLUSH_ALL) { 1566 1567 ldapmemcacheRes *pCurRes = cache->ldmemc_resHead[LIST_TTL]; 1568 1569 nRes = htable_removeall(cache->ldmemc_resLookup, (void*)cache); 1570 1571 for (; pCurRes; pCurRes = cache->ldmemc_resHead[LIST_TTL]) { 1572 memcache_free_from_list(cache, pCurRes, LIST_LRU); 1573 cache->ldmemc_resHead[LIST_TTL] = 1574 cache->ldmemc_resHead[LIST_TTL]->ldmemcr_next[LIST_TTL]; 1575 memcache_free_entry(cache, pCurRes); 1576 } 1577 cache->ldmemc_resTail[LIST_TTL] = NULL; 1578 } 1579 /* Remove cached entries in both primary and temporary cache. */ 1580 else if (mode == MEMCACHE_ACCESS_FLUSH) { 1581 1582 int i, list_id, bDone; 1583 int scope = (int)(uintptr_t)pData2; 1584 char *dn = (char*)pData1; 1585 char *dnTmp; 1586 BerElement ber; 1587 LDAPMessage *pMsg; 1588 ldapmemcacheRes *pRes; 1589 1590 if (cache->ldmemc_basedns) { 1591 for (i = 0; cache->ldmemc_basedns[i]; i++) { 1592 if ((memcache_compare_dn(cache->ldmemc_basedns[i], dn, 1593 LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) || 1594 (memcache_compare_dn(dn, cache->ldmemc_basedns[i], 1595 LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE)) 1596 break; 1597 } 1598 if (cache->ldmemc_basedns[i] == NULL) 1599 return( LDAP_SUCCESS ); 1600 } 1601 1602 for (i = 0; i < 2; i++) { 1603 1604 list_id = (i == 0 ? LIST_TTL : LIST_TMP); 1605 1606 for (pRes = cache->ldmemc_resHead[list_id]; pRes != NULL; 1607 pRes = pRes->ldmemcr_next[list_id]) { 1608 1609 if ((memcache_compare_dn(pRes->ldmemcr_basedn, dn, 1610 LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE) && 1611 (memcache_compare_dn(dn, pRes->ldmemcr_basedn, 1612 LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE)) 1613 continue; 1614 1615 for (pMsg = pRes->ldmemcr_resHead, bDone = 0; 1616 !bDone && pMsg; pMsg = pMsg->lm_chain) { 1617 1618 if (!NSLDAPI_IS_SEARCH_ENTRY( pMsg->lm_msgtype )) 1619 continue; 1620 1621 ber = *(pMsg->lm_ber); 1622 if (ber_scanf(&ber, "{a", &dnTmp) != LBER_ERROR) { 1623 bDone = (memcache_compare_dn(dnTmp, dn, scope) == 1624 LDAP_COMPARE_TRUE); 1625 ldap_memfree(dnTmp); 1626 } 1627 } 1628 1629 if (!bDone) 1630 continue; 1631 1632 if (list_id == LIST_TTL) { 1633 nRes = htable_remove(cache->ldmemc_resLookup, 1634 (void*)&(pRes->ldmemcr_crc_key), NULL); 1635 assert(nRes == LDAP_SUCCESS); 1636 memcache_free_from_list(cache, pRes, LIST_TTL); 1637 memcache_free_from_list(cache, pRes, LIST_LRU); 1638 } else { 1639 nRes = htable_remove(cache->ldmemc_resTmp, 1640 (void*)&(pRes->ldmemcr_req_id), NULL); 1641 assert(nRes == LDAP_SUCCESS); 1642 memcache_free_from_list(cache, pRes, LIST_TMP); 1643 } 1644 memcache_free_entry(cache, pRes); 1645 } 1646 } 1647 } 1648 /* Flush least recently used entries from cache */ 1649 else if (mode == MEMCACHE_ACCESS_FLUSH_LRU) { 1650 1651 ldapmemcacheRes *pRes = cache->ldmemc_resTail[LIST_LRU]; 1652 1653 if (pRes == NULL) 1654 return LDAP_NO_SUCH_OBJECT; 1655 1656 LDAPDebug( LDAP_DEBUG_TRACE, 1657 "memcache_access FLUSH_LRU: removing key 0x%8.8lx\n", 1658 pRes->ldmemcr_crc_key, 0, 0 ); 1659 nRes = htable_remove(cache->ldmemc_resLookup, 1660 (void*)&(pRes->ldmemcr_crc_key), NULL); 1661 assert(nRes == LDAP_SUCCESS); 1662 memcache_free_from_list(cache, pRes, LIST_TTL); 1663 memcache_free_from_list(cache, pRes, LIST_LRU); 1664 memcache_free_entry(cache, pRes); 1665 } 1666 /* Unknown command */ 1667 else { 1668 nRes = LDAP_PARAM_ERROR; 1669 } 1670 1671 return nRes; 1672 } 1673 1674 1675 #ifdef LDAP_DEBUG 1676 static void 1677 memcache_report_statistics( LDAPMemCache *cache ) 1678 { 1679 unsigned long hitrate; 1680 1681 if ( cache->ldmemc_stats.ldmemcstat_tries == 0 ) { 1682 hitrate = 0; 1683 } else { 1684 hitrate = ( 100L * cache->ldmemc_stats.ldmemcstat_hits ) / 1685 cache->ldmemc_stats.ldmemcstat_tries; 1686 } 1687 LDAPDebug( LDAP_DEBUG_STATS, "memcache 0x%x:\n", cache, 0, 0 ); 1688 LDAPDebug( LDAP_DEBUG_STATS, " tries: %ld hits: %ld hitrate: %ld%%\n", 1689 cache->ldmemc_stats.ldmemcstat_tries, 1690 cache->ldmemc_stats.ldmemcstat_hits, hitrate ); 1691 if ( cache->ldmemc_size <= 0 ) { /* no size limit */ 1692 LDAPDebug( LDAP_DEBUG_STATS, " memory bytes used: %ld\n", 1693 cache->ldmemc_size_used, 0, 0 ); 1694 } else { 1695 LDAPDebug( LDAP_DEBUG_STATS, " memory bytes used: %ld free: %ld\n", 1696 cache->ldmemc_size_used, 1697 cache->ldmemc_size - cache->ldmemc_size_used, 0 ); 1698 } 1699 } 1700 #endif /* LDAP_DEBUG */ 1701 1702 /************************ Hash Table Functions *****************************/ 1703 1704 /* Calculates size (# of entries) of hash table given the size limit for 1705 the cache. */ 1706 static int 1707 htable_calculate_size(int sizelimit) 1708 { 1709 int i, j; 1710 int size = (int)(((double)sizelimit / 1711 (double)(sizeof(BerElement) + EXTRA_SIZE)) / 1.5); 1712 1713 /* Get a prime # */ 1714 size = (size & 0x1 ? size : size + 1); 1715 for (i = 3, j = size / 2; i < j; i++) { 1716 if ((size % i) == 0) { 1717 size += 2; 1718 i = 3; 1719 j = size / 2; 1720 } 1721 } 1722 1723 return size; 1724 } 1725 1726 /* Returns the size in bytes of the given hash table. */ 1727 static int 1728 htable_sizeinbytes(HashTable *pTable) 1729 { 1730 if (!pTable) 1731 return 0; 1732 1733 return (pTable->size * sizeof(HashTableNode)); 1734 } 1735 1736 /* Inserts an item into the hash table. */ 1737 static int 1738 htable_put(HashTable *pTable, void *key, void *pData) 1739 { 1740 int index = pTable->hashfunc(pTable->size, key); 1741 1742 if (index >= 0 && index < pTable->size) 1743 return pTable->putdata(&(pTable->table[index].pData), key, pData); 1744 1745 return( LDAP_OPERATIONS_ERROR ); 1746 } 1747 1748 /* Retrieves an item from the hash table. */ 1749 static int 1750 htable_get(HashTable *pTable, void *key, void **ppData) 1751 { 1752 int index = pTable->hashfunc(pTable->size, key); 1753 1754 *ppData = NULL; 1755 1756 if (index >= 0 && index < pTable->size) 1757 return pTable->getdata(pTable->table[index].pData, key, ppData); 1758 1759 return( LDAP_OPERATIONS_ERROR ); 1760 } 1761 1762 /* Performs a miscellaneous operation on a hash table entry. */ 1763 static int 1764 htable_misc(HashTable *pTable, void *key, void *pData) 1765 { 1766 if (pTable->miscfunc) { 1767 int index = pTable->hashfunc(pTable->size, key); 1768 if (index >= 0 && index < pTable->size) 1769 return pTable->miscfunc(&(pTable->table[index].pData), key, pData); 1770 } 1771 1772 return( LDAP_OPERATIONS_ERROR ); 1773 } 1774 1775 /* Removes an item from the hash table. */ 1776 static int 1777 htable_remove(HashTable *pTable, void *key, void **ppData) 1778 { 1779 int index = pTable->hashfunc(pTable->size, key); 1780 1781 if (ppData) 1782 *ppData = NULL; 1783 1784 if (index >= 0 && index < pTable->size) 1785 return pTable->removedata(&(pTable->table[index].pData), key, ppData); 1786 1787 return( LDAP_OPERATIONS_ERROR ); 1788 } 1789 1790 /* Removes everything in the hash table. */ 1791 static int 1792 htable_removeall(HashTable *pTable, void *pData) 1793 { 1794 int i; 1795 1796 for (i = 0; i < pTable->size; i++) 1797 pTable->clrtablenode(&(pTable->table[i].pData), pData); 1798 1799 return( LDAP_SUCCESS ); 1800 } 1801 1802 /* Creates a new hash table. */ 1803 static int 1804 htable_create(int size_limit, HashFuncPtr hashf, 1805 PutDataPtr putDataf, GetDataPtr getDataf, 1806 RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef, 1807 MiscFuncPtr miscOpf, HashTable **ppTable) 1808 { 1809 size_limit = htable_calculate_size(size_limit); 1810 1811 if ((*ppTable = (HashTable*)NSLDAPI_CALLOC(1, sizeof(HashTable))) == NULL) 1812 return( LDAP_NO_MEMORY ); 1813 1814 (*ppTable)->table = (HashTableNode*)NSLDAPI_CALLOC(size_limit, 1815 sizeof(HashTableNode)); 1816 if ((*ppTable)->table == NULL) { 1817 NSLDAPI_FREE(*ppTable); 1818 *ppTable = NULL; 1819 return( LDAP_NO_MEMORY ); 1820 } 1821 1822 (*ppTable)->size = size_limit; 1823 (*ppTable)->hashfunc = hashf; 1824 (*ppTable)->putdata = putDataf; 1825 (*ppTable)->getdata = getDataf; 1826 (*ppTable)->miscfunc = miscOpf; 1827 (*ppTable)->removedata = removeDataf; 1828 (*ppTable)->clrtablenode = clrNodef; 1829 1830 return( LDAP_SUCCESS ); 1831 } 1832 1833 /* Destroys a hash table. */ 1834 static int 1835 htable_free(HashTable *pTable) 1836 { 1837 NSLDAPI_FREE(pTable->table); 1838 NSLDAPI_FREE(pTable); 1839 return( LDAP_SUCCESS ); 1840 } 1841 1842 /**************** Hash table callbacks for temporary cache ****************/ 1843 1844 /* Hash function */ 1845 static int 1846 msgid_hashf(int table_size, void *key) 1847 { 1848 uint_t code = (uint_t)(uintptr_t)((ldapmemcacheReqId*)key)->ldmemcrid_ld; 1849 return (((code << 20) + (code >> 12)) % table_size); 1850 } 1851 1852 /* Called by hash table to insert an item. */ 1853 static int 1854 msgid_putdata(void **ppTableData, void *key, void *pData) 1855 { 1856 ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key; 1857 ldapmemcacheRes *pRes = (ldapmemcacheRes*)pData; 1858 ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData; 1859 ldapmemcacheRes *pCurRes = *ppHead; 1860 ldapmemcacheRes *pPrev = NULL; 1861 1862 for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) { 1863 if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld) 1864 break; 1865 pPrev = pCurRes; 1866 } 1867 1868 if (pCurRes) { 1869 for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) { 1870 if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid == 1871 pReqId->ldmemcrid_msgid) 1872 return( LDAP_ALREADY_EXISTS ); 1873 pPrev = pCurRes; 1874 } 1875 pPrev->ldmemcr_next[LIST_TTL] = pRes; 1876 pRes->ldmemcr_prev[LIST_TTL] = pPrev; 1877 pRes->ldmemcr_next[LIST_TTL] = NULL; 1878 } else { 1879 if (pPrev) 1880 pPrev->ldmemcr_htable_next = pRes; 1881 else 1882 *ppHead = pRes; 1883 pRes->ldmemcr_htable_next = NULL; 1884 } 1885 1886 return( LDAP_SUCCESS ); 1887 } 1888 1889 /* Called by hash table to retrieve an item. */ 1890 static int 1891 msgid_getdata(void *pTableData, void *key, void **ppData) 1892 { 1893 ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key; 1894 ldapmemcacheRes *pCurRes = (ldapmemcacheRes*)pTableData; 1895 1896 *ppData = NULL; 1897 1898 for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) { 1899 if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld) 1900 break; 1901 } 1902 1903 if (!pCurRes) 1904 return( LDAP_NO_SUCH_OBJECT ); 1905 1906 for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) { 1907 if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid == 1908 pReqId->ldmemcrid_msgid) { 1909 *ppData = (void*)pCurRes; 1910 return( LDAP_SUCCESS ); 1911 } 1912 } 1913 1914 return( LDAP_NO_SUCH_OBJECT ); 1915 } 1916 1917 /* Called by hash table to remove an item. */ 1918 static int 1919 msgid_removedata(void **ppTableData, void *key, void **ppData) 1920 { 1921 ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData); 1922 ldapmemcacheRes *pCurRes = NULL; 1923 ldapmemcacheRes *pPrev = NULL; 1924 ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key; 1925 1926 if (ppData) 1927 *ppData = NULL; 1928 1929 for (; pHead; pHead = pHead->ldmemcr_htable_next) { 1930 if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld) 1931 break; 1932 pPrev = pHead; 1933 } 1934 1935 if (!pHead) 1936 return( LDAP_NO_SUCH_OBJECT ); 1937 1938 for (pCurRes = pHead; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) { 1939 if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid == 1940 pReqId->ldmemcrid_msgid) 1941 break; 1942 } 1943 1944 if (!pCurRes) 1945 return( LDAP_NO_SUCH_OBJECT ); 1946 1947 if (ppData) { 1948 pCurRes->ldmemcr_next[LIST_TTL] = NULL; 1949 pCurRes->ldmemcr_prev[LIST_TTL] = NULL; 1950 pCurRes->ldmemcr_htable_next = NULL; 1951 *ppData = (void*)pCurRes; 1952 } 1953 1954 if (pCurRes != pHead) { 1955 if (pCurRes->ldmemcr_prev[LIST_TTL]) 1956 pCurRes->ldmemcr_prev[LIST_TTL]->ldmemcr_next[LIST_TTL] = 1957 pCurRes->ldmemcr_next[LIST_TTL]; 1958 if (pCurRes->ldmemcr_next[LIST_TTL]) 1959 pCurRes->ldmemcr_next[LIST_TTL]->ldmemcr_prev[LIST_TTL] = 1960 pCurRes->ldmemcr_prev[LIST_TTL]; 1961 return( LDAP_SUCCESS ); 1962 } 1963 1964 if (pPrev) { 1965 if (pHead->ldmemcr_next[LIST_TTL]) { 1966 pPrev->ldmemcr_htable_next = pHead->ldmemcr_next[LIST_TTL]; 1967 pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next = 1968 pHead->ldmemcr_htable_next; 1969 } else { 1970 pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next; 1971 } 1972 } else { 1973 if (pHead->ldmemcr_next[LIST_TTL]) { 1974 *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_next[LIST_TTL]; 1975 pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next = 1976 pHead->ldmemcr_htable_next; 1977 } else { 1978 *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next; 1979 } 1980 } 1981 1982 return( LDAP_SUCCESS ); 1983 } 1984 1985 /* Called by hash table to remove all cached entries associated to searches 1986 being performed using the given ldap handle. */ 1987 static int 1988 msgid_clear_ld_items(void **ppTableData, void *key, void *pData) 1989 { 1990 LDAPMemCache *cache = (LDAPMemCache*)pData; 1991 ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData); 1992 ldapmemcacheRes *pPrev = NULL; 1993 ldapmemcacheRes *pCurRes = NULL; 1994 ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key; 1995 1996 for (; pHead; pHead = pHead->ldmemcr_htable_next) { 1997 if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld) 1998 break; 1999 pPrev = pHead; 2000 } 2001 2002 if (!pHead) 2003 return( LDAP_NO_SUCH_OBJECT ); 2004 2005 if (pPrev) 2006 pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next; 2007 else 2008 *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next; 2009 2010 for (pCurRes = pHead; pHead; pCurRes = pHead) { 2011 pHead = pHead->ldmemcr_next[LIST_TTL]; 2012 memcache_free_from_list(cache, pCurRes, LIST_TMP); 2013 memcache_free_entry(cache, pCurRes); 2014 } 2015 2016 return( LDAP_SUCCESS ); 2017 } 2018 2019 /* Called by hash table for removing all items in the table. */ 2020 static void 2021 msgid_clearnode(void **ppTableData, void *pData) 2022 { 2023 LDAPMemCache *cache = (LDAPMemCache*)pData; 2024 ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData; 2025 ldapmemcacheRes *pSubHead = *ppHead; 2026 ldapmemcacheRes *pCurRes = NULL; 2027 2028 for (; *ppHead; pSubHead = *ppHead) { 2029 ppHead = &((*ppHead)->ldmemcr_htable_next); 2030 for (pCurRes = pSubHead; pSubHead; pCurRes = pSubHead) { 2031 pSubHead = pSubHead->ldmemcr_next[LIST_TTL]; 2032 memcache_free_from_list(cache, pCurRes, LIST_TMP); 2033 memcache_free_entry(cache, pCurRes); 2034 } 2035 } 2036 } 2037 2038 /********************* Hash table for primary cache ************************/ 2039 2040 /* Hash function */ 2041 static int 2042 attrkey_hashf(int table_size, void *key) 2043 { 2044 return ((*((unsigned long*)key)) % table_size); 2045 } 2046 2047 /* Called by hash table to insert an item. */ 2048 static int 2049 attrkey_putdata(void **ppTableData, void *key, void *pData) 2050 { 2051 unsigned long attrkey = *((unsigned long*)key); 2052 ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData; 2053 ldapmemcacheRes *pRes = *ppHead; 2054 2055 for (; pRes; pRes = pRes->ldmemcr_htable_next) { 2056 if (pRes->ldmemcr_crc_key == attrkey) 2057 return( LDAP_ALREADY_EXISTS ); 2058 } 2059 2060 pRes = (ldapmemcacheRes*)pData; 2061 pRes->ldmemcr_htable_next = *ppHead; 2062 *ppHead = pRes; 2063 2064 return( LDAP_SUCCESS ); 2065 } 2066 2067 /* Called by hash table to retrieve an item. */ 2068 static int 2069 attrkey_getdata(void *pTableData, void *key, void **ppData) 2070 { 2071 unsigned long attrkey = *((unsigned long*)key); 2072 ldapmemcacheRes *pRes = (ldapmemcacheRes*)pTableData; 2073 2074 for (; pRes; pRes = pRes->ldmemcr_htable_next) { 2075 if (pRes->ldmemcr_crc_key == attrkey) { 2076 *ppData = (void*)pRes; 2077 return( LDAP_SUCCESS ); 2078 } 2079 } 2080 2081 *ppData = NULL; 2082 2083 return( LDAP_NO_SUCH_OBJECT ); 2084 } 2085 2086 /* Called by hash table to remove an item. */ 2087 static int 2088 attrkey_removedata(void **ppTableData, void *key, void **ppData) 2089 { 2090 unsigned long attrkey = *((unsigned long*)key); 2091 ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData; 2092 ldapmemcacheRes *pRes = *ppHead; 2093 ldapmemcacheRes *pPrev = NULL; 2094 2095 for (; pRes; pRes = pRes->ldmemcr_htable_next) { 2096 if (pRes->ldmemcr_crc_key == attrkey) { 2097 if (ppData) 2098 *ppData = (void*)pRes; 2099 if (pPrev) 2100 pPrev->ldmemcr_htable_next = pRes->ldmemcr_htable_next; 2101 else 2102 *ppHead = pRes->ldmemcr_htable_next; 2103 pRes->ldmemcr_htable_next = NULL; 2104 return( LDAP_SUCCESS ); 2105 } 2106 pPrev = pRes; 2107 } 2108 2109 if (ppData) 2110 *ppData = NULL; 2111 2112 return( LDAP_NO_SUCH_OBJECT ); 2113 } 2114 2115 /* Called by hash table for removing all items in the table. */ 2116 static void 2117 attrkey_clearnode(void **ppTableData, void *pData) 2118 { 2119 ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData; 2120 ldapmemcacheRes *pRes = *ppHead; 2121 2122 (void)pData; 2123 2124 for (; *ppHead; pRes = *ppHead) { 2125 ppHead = &((*ppHead)->ldmemcr_htable_next); 2126 pRes->ldmemcr_htable_next = NULL; 2127 } 2128 } 2129 2130 /***************************** CRC algorithm ********************************/ 2131 2132 /* From http://www.faqs.org/faqs/compression-faq/part1/section-25.html */ 2133 2134 /* 2135 * Build auxiliary table for parallel byte-at-a-time CRC-32. 2136 */ 2137 #define NSLDAPI_CRC32_POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */ 2138 2139 static unsigned long crc32_table[256] = { 2140 0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b, 2141 0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61, 2142 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, 0x4c11db70, 0x48d0c6c7, 2143 0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75, 2144 0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 2145 0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039, 2146 0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58, 0xbaea46ef, 2147 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d, 2148 0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb, 2149 0xceb42022, 0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 2150 0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0, 2151 0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072, 2152 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4, 2153 0x0808d07d, 0x0cc9cdca, 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde, 2154 0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 2155 0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba, 2156 0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc, 2157 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6, 2158 0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050, 2159 0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 2160 0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34, 2161 0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637, 2162 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, 0x4f040d56, 0x4bc510e1, 2163 0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53, 2164 0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 2165 0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff, 2166 0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e, 0xf5ee4bb9, 2167 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b, 2168 0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 2169 0xcda1f604, 0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 2170 0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71, 2171 0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3, 2172 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2, 2173 0x470cdd2b, 0x43cdc09c, 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8, 2174 0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 2175 0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec, 2176 0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a, 2177 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0, 2178 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676, 2179 0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 2180 0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662, 2181 0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668, 2182 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4 }; 2183 2184 /* Initialized first time "crc32()" is called. If you prefer, you can 2185 * statically initialize it at compile time. [Another exercise.] 2186 */ 2187 2188 static unsigned long 2189 crc32_convert(char *buf, int len) 2190 { 2191 char *p; 2192 #ifdef OSF1V4D 2193 unsigned int crc; 2194 #else 2195 unsigned long crc; /* FIXME: this is not 32-bits on all platforms! */ 2196 #endif /* OSF1V4D */ 2197 2198 crc = 0xffffffff; /* preload shift register, per CRC-32 spec */ 2199 for (p = buf; len > 0; ++p, --len) 2200 crc = ((crc << 8) ^ crc32_table[(crc >> 24) ^ *p]) & 0xffffffff; 2201 2202 return (unsigned long) ~crc; /* transmit complement, per CRC-32 spec */ 2203 } 2204