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
ldap_memcache_init(unsigned long ttl,unsigned long size,char ** baseDNs,struct ldap_thread_fns * thread_fns,LDAPMemCache ** cachep)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
ldap_memcache_set(LDAP * ld,LDAPMemCache * cache)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
ldap_memcache_get(LDAP * ld,LDAPMemCache ** cachep)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
ldap_memcache_update(LDAPMemCache * cache)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
ldap_memcache_flush(LDAPMemCache * cache,char * dn,int scope)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
ldap_memcache_destroy(LDAPMemCache * cache)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
ldap_memcache_createkey(LDAP * ld,const char * base,int scope,const char * filter,char ** attrs,int attrsonly,LDAPControl ** serverctrls,LDAPControl ** clientctrls,unsigned long * keyp)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
ldap_memcache_result(LDAP * ld,int msgid,unsigned long key)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
ldap_memcache_new(LDAP * ld,int msgid,unsigned long key,const char * basedn)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
ldap_memcache_append(LDAP * ld,int msgid,int bLast,LDAPMessage * result)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
ldap_memcache_abandon(LDAP * ld,int msgid)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
memcache_trim_basedn_spaces(char * basedn)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
memcache_validate_basedn(LDAPMemCache * cache,const char * basedn)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