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