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