xref: /illumos-gate/usr/src/lib/libldap5/sources/ldap/common/memcache.c (revision 1da57d551424de5a9d469760be7c4b4d4f10a755)
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