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