Back to index

lightning-sunbird  0.9+nobinonly
memcache.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is Mozilla Communicator client code, released
00015  * March 31, 1998.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998-1999
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 /*
00038  *
00039  *  memcache.c - routines that implement an in-memory cache.
00040  *
00041  *  To Do:  1) ber_dup_ext().
00042  *         2) referrals and reference?
00043  */
00044 
00045 #include <assert.h>
00046 #include "ldap-int.h"
00047 
00048 /*
00049  * Extra size allocated to BerElement.
00050  * XXXmcs: must match EXBUFSIZ in liblber/io.c?
00051  */
00052 #define EXTRA_SIZE              1024
00053 
00054 /* Mode constants for function memcache_access() */
00055 #define MEMCACHE_ACCESS_ADD     0
00056 #define MEMCACHE_ACCESS_APPEND         1
00057 #define MEMCACHE_ACCESS_APPEND_LAST 2
00058 #define MEMCACHE_ACCESS_FIND           3
00059 #define MEMCACHE_ACCESS_DELETE         4
00060 #define MEMCACHE_ACCESS_DELETE_ALL  5
00061 #define MEMCACHE_ACCESS_UPDATE         6
00062 #define MEMCACHE_ACCESS_FLUSH          7
00063 #define MEMCACHE_ACCESS_FLUSH_ALL   8
00064 #define MEMCACHE_ACCESS_FLUSH_LRU   9
00065 
00066 /* Mode constants for function memcache_adj_size */
00067 #define MEMCACHE_SIZE_DEDUCT           0
00068 #define MEMCACHE_SIZE_ADD       1
00069 
00070 #define MEMCACHE_SIZE_ENTRIES       1
00071 #define MEMCACHE_SIZE_NON_ENTRIES   2
00072 
00073 /* Size used for calculation if given size of cache is 0 */
00074 #define MEMCACHE_DEF_SIZE       131072           /* 128K bytes */
00075 
00076 /* Index into different list structure */
00077 #define LIST_TTL                0
00078 #define LIST_LRU                1
00079 #define LIST_TMP                2
00080 #define LIST_TOTAL              3
00081 
00082 /* Macros to make code more readable */
00083 #define NSLDAPI_VALID_MEMCACHE_POINTER( cp )     ( (cp) != NULL )
00084 #define NSLDAPI_STR_NONNULL( s )          ( (s) ? (s) : "" )
00085 #define NSLDAPI_SAFE_STRLEN( s )          ( (s) ? strlen((s)) + 1 : 1 )
00086 
00087 /* Macros dealing with mutex */
00088 #define LDAP_MEMCACHE_MUTEX_LOCK( c ) \
00089        if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_lock ) { \
00090            ((c)->ldmemc_lock_fns).ltf_mutex_lock( (c)->ldmemc_lock ); \
00091        }
00092 
00093 #define LDAP_MEMCACHE_MUTEX_UNLOCK( c ) \
00094        if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_unlock ) { \
00095            ((c)->ldmemc_lock_fns).ltf_mutex_unlock( (c)->ldmemc_lock ); \
00096        }
00097 
00098 #define LDAP_MEMCACHE_MUTEX_ALLOC( c ) \
00099        ((c) && ((c)->ldmemc_lock_fns).ltf_mutex_alloc ? \
00100            ((c)->ldmemc_lock_fns).ltf_mutex_alloc() : NULL)
00101 
00102 #define LDAP_MEMCACHE_MUTEX_FREE( c ) \
00103        if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_free ) { \
00104            ((c)->ldmemc_lock_fns).ltf_mutex_free( (c)->ldmemc_lock ); \
00105        }
00106 
00107 /* Macros used for triming unnecessary spaces in a basedn */
00108 #define NSLDAPI_IS_SPACE( c ) \
00109        (((c) == ' ') || ((c) == '\t') || ((c) == '\n'))
00110 
00111 #define NSLDAPI_IS_SEPARATER( c ) \
00112        ((c) == ',')
00113 
00114 /* Hash table callback function pointer definition */
00115 typedef int (*HashFuncPtr)(int table_size, void *key);
00116 typedef int (*PutDataPtr)(void **ppTableData, void *key, void *pData);
00117 typedef int (*GetDataPtr)(void *pTableData, void *key, void **ppData);
00118 typedef int (*RemoveDataPtr)(void **ppTableData, void *key, void **ppData);
00119 typedef int (*MiscFuncPtr)(void **ppTableData, void *key, void *pData);
00120 typedef void (*ClrTableNodePtr)(void **ppTableData, void *pData);
00121 
00122 /* Structure of a node in a hash table */
00123 typedef struct HashTableNode_struct {
00124     void *pData;
00125 } HashTableNode;
00126 
00127 /* Structure of a hash table */
00128 typedef struct HashTable_struct {
00129     HashTableNode   *table;
00130     int                  size;
00131     HashFuncPtr          hashfunc;
00132     PutDataPtr           putdata;
00133     GetDataPtr           getdata;
00134     MiscFuncPtr     miscfunc;
00135     RemoveDataPtr   removedata;
00136     ClrTableNodePtr clrtablenode;
00137 } HashTable;
00138 
00139 /* Structure uniquely identifies a search request */
00140 typedef struct ldapmemcacheReqId_struct {
00141     LDAP                           *ldmemcrid_ld;
00142     int                                   ldmemcrid_msgid;
00143 } ldapmemcacheReqId;
00144 
00145 /* Structure representing a ldap handle associated to memcache */
00146 typedef struct ldapmemcacheld_struct {
00147     LDAP                           *ldmemcl_ld;
00148     struct ldapmemcacheld_struct   *ldmemcl_next;
00149 } ldapmemcacheld;
00150 
00151 /* Structure representing header of a search result */
00152 typedef struct ldapmemcacheRes_struct {
00153     char                           *ldmemcr_basedn;
00154     unsigned long                  ldmemcr_crc_key;
00155     unsigned long                  ldmemcr_resSize;
00156     unsigned long                  ldmemcr_timestamp;
00157     LDAPMessage                           *ldmemcr_resHead;
00158     LDAPMessage                           *ldmemcr_resTail;
00159     ldapmemcacheReqId                     ldmemcr_req_id;
00160     struct ldapmemcacheRes_struct  *ldmemcr_next[LIST_TOTAL];
00161     struct ldapmemcacheRes_struct  *ldmemcr_prev[LIST_TOTAL];
00162     struct ldapmemcacheRes_struct  *ldmemcr_htable_next;
00163 } ldapmemcacheRes;
00164 
00165 /* Structure for memcache statistics */
00166 typedef struct ldapmemcacheStats_struct {
00167     unsigned long                  ldmemcstat_tries;
00168     unsigned long                  ldmemcstat_hits;
00169 } ldapmemcacheStats;
00170 
00171 /* Structure of a memcache object */
00172 struct ldapmemcache {
00173     unsigned long                  ldmemc_ttl;
00174     unsigned long                  ldmemc_size;
00175     unsigned long                  ldmemc_size_used;
00176     unsigned long                  ldmemc_size_entries;
00177     char                           **ldmemc_basedns;
00178     void                           *ldmemc_lock;
00179     ldapmemcacheld                 *ldmemc_lds;
00180     HashTable                      *ldmemc_resTmp;
00181     HashTable                      *ldmemc_resLookup;
00182     ldapmemcacheRes                *ldmemc_resHead[LIST_TOTAL];
00183     ldapmemcacheRes                *ldmemc_resTail[LIST_TOTAL];
00184     struct ldap_thread_fns         ldmemc_lock_fns;
00185     ldapmemcacheStats                     ldmemc_stats;
00186 };
00187 
00188 /* Function prototypes */
00189 static int memcache_exist(LDAP *ld);
00190 static int memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg);
00191 static int memcache_compare_dn(const char *main_dn, const char *dn, int scope);
00192 static int memcache_dup_message(LDAPMessage *res, int msgid, int fromcache, 
00193                             LDAPMessage **ppResCopy, unsigned long *pSize);
00194 static BerElement* memcache_ber_dup(BerElement* pBer, unsigned long *pSize);
00195 
00196 static void memcache_trim_basedn_spaces(char *basedn);
00197 static int memcache_validate_basedn(LDAPMemCache *cache, const char *basedn);
00198 static int memcache_get_ctrls_len(LDAPControl **ctrls);
00199 static void memcache_append_ctrls(char *buf, LDAPControl **serverCtrls,
00200                               LDAPControl **clientCtrls);
00201 static int memcache_adj_size(LDAPMemCache *cache, unsigned long size,
00202                              int usageFlags, int bAdd);
00203 static int memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes);
00204 static int memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes, 
00205                          unsigned long curTime);
00206 static int memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, 
00207                             int index);
00208 static int memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg, 
00209                                 unsigned long size);
00210 static int memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, 
00211                                int index);
00212 static int memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes);
00213 static int memcache_add(LDAP *ld, unsigned long key, int msgid,
00214                      const char *basedn);
00215 static int memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes);
00216 static int memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes);
00217 static int memcache_remove(LDAP *ld, int msgid);
00218 #if 0  /* function not used */
00219 static int memcache_remove_all(LDAP *ld);
00220 #endif /* 0 */
00221 static int memcache_access(LDAPMemCache *cache, int mode, 
00222                         void *pData1, void *pData2, void *pData3);
00223 #ifdef LDAP_DEBUG
00224 static void memcache_print_list( LDAPMemCache *cache, int index );
00225 static void memcache_report_statistics( LDAPMemCache *cache );
00226 #endif /* LDAP_DEBUG */
00227 
00228 static int htable_calculate_size(int sizelimit);
00229 static int htable_sizeinbytes(HashTable *pTable);
00230 static int htable_put(HashTable *pTable, void *key, void *pData);
00231 static int htable_get(HashTable *pTable, void *key, void **ppData);
00232 static int htable_misc(HashTable *pTable, void *key, void *pData);
00233 static int htable_remove(HashTable *pTable, void *key, void **ppData);
00234 static int htable_removeall(HashTable *pTable, void *pData);
00235 static int htable_create(int size_limit, HashFuncPtr hashf,
00236                          PutDataPtr putDataf, GetDataPtr getDataf,
00237                       RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef,
00238                       MiscFuncPtr miscOpf, HashTable **ppTable);
00239 static int htable_free(HashTable *pTable);
00240 
00241 static int msgid_hashf(int table_size, void *key);
00242 static int msgid_putdata(void **ppTableData, void *key, void *pData);
00243 static int msgid_getdata(void *pTableData, void *key, void **ppData);
00244 static int msgid_removedata(void **ppTableData, void *key, void **ppData);
00245 static int msgid_clear_ld_items(void **ppTableData, void *key, void *pData);
00246 static void msgid_clearnode(void **ppTableData, void *pData);
00247 
00248 static int attrkey_hashf(int table_size, void *key);
00249 static int attrkey_putdata(void **ppTableData, void *key, void *pData);
00250 static int attrkey_getdata(void *pTableData, void *key, void **ppData);
00251 static int attrkey_removedata(void **ppTableData, void *key, void **ppData);
00252 static void attrkey_clearnode(void **ppTableData, void *pData);
00253 
00254 static unsigned long crc32_convert(char *buf, int len);
00255 
00256 /* Create a memcache object. */
00257 int
00258 LDAP_CALL
00259 ldap_memcache_init( unsigned long ttl, unsigned long size,
00260                     char **baseDNs, struct ldap_thread_fns *thread_fns,
00261                   LDAPMemCache **cachep )
00262 {
00263     unsigned long total_size = 0;
00264 
00265     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init\n", 0, 0, 0 );
00266 
00267     if ( cachep == NULL ) {
00268        return( LDAP_PARAM_ERROR );
00269     }
00270 
00271     if ((*cachep = (LDAPMemCache*)NSLDAPI_CALLOC(1,
00272            sizeof(LDAPMemCache))) == NULL) {
00273        return ( LDAP_NO_MEMORY );
00274     }
00275 
00276     total_size += sizeof(LDAPMemCache);
00277 
00278     (*cachep)->ldmemc_ttl = ttl;
00279     (*cachep)->ldmemc_size = size;
00280     (*cachep)->ldmemc_lds = NULL;
00281 
00282     /* Non-zero default size needed for calculating size of hash tables */
00283     size = (size ? size : MEMCACHE_DEF_SIZE);
00284 
00285     if (thread_fns) {
00286        memcpy(&((*cachep)->ldmemc_lock_fns), thread_fns, 
00287            sizeof(struct ldap_thread_fns));
00288     } else {
00289        memset(&((*cachep)->ldmemc_lock_fns), 0, 
00290           sizeof(struct ldap_thread_fns));
00291     }
00292 
00293     (*cachep)->ldmemc_lock = LDAP_MEMCACHE_MUTEX_ALLOC( *cachep );
00294 
00295     /* Cache basedns */
00296     if (baseDNs != NULL) {
00297 
00298        int i;
00299 
00300        for (i = 0; baseDNs[i]; i++) {
00301               ;
00302        }
00303 
00304        (*cachep)->ldmemc_basedns = (char**)NSLDAPI_CALLOC(i + 1,
00305               sizeof(char*));
00306 
00307        if ((*cachep)->ldmemc_basedns == NULL) {
00308            ldap_memcache_destroy(*cachep);
00309            *cachep = NULL;
00310            return ( LDAP_NO_MEMORY );
00311        }
00312 
00313        total_size += (i + 1) * sizeof(char*);
00314 
00315        for (i = 0; baseDNs[i]; i++) {
00316            (*cachep)->ldmemc_basedns[i] = nsldapi_strdup(baseDNs[i]);
00317            total_size += strlen(baseDNs[i]) + 1;
00318        }
00319 
00320        (*cachep)->ldmemc_basedns[i] = NULL;
00321     }
00322 
00323     /* Create hash table for temporary cache */
00324     if (htable_create(size, msgid_hashf, msgid_putdata, msgid_getdata,
00325                       msgid_removedata, msgid_clearnode, msgid_clear_ld_items,
00326                     &((*cachep)->ldmemc_resTmp)) != LDAP_SUCCESS) {
00327        ldap_memcache_destroy(*cachep);
00328        *cachep = NULL;
00329        return( LDAP_NO_MEMORY );
00330     }
00331 
00332     total_size += htable_sizeinbytes((*cachep)->ldmemc_resTmp);
00333 
00334     /* Create hash table for primary cache */
00335     if (htable_create(size, attrkey_hashf, attrkey_putdata, 
00336                      attrkey_getdata, attrkey_removedata, attrkey_clearnode,
00337                     NULL, &((*cachep)->ldmemc_resLookup)) != LDAP_SUCCESS) {
00338        ldap_memcache_destroy(*cachep);
00339        *cachep = NULL;
00340        return( LDAP_NO_MEMORY );
00341     }
00342 
00343     total_size += htable_sizeinbytes((*cachep)->ldmemc_resLookup);
00344     
00345     /* See if there is enough room so far */
00346     if (memcache_adj_size(*cachep, total_size, MEMCACHE_SIZE_NON_ENTRIES,
00347                          MEMCACHE_SIZE_ADD) != LDAP_SUCCESS) {
00348        ldap_memcache_destroy(*cachep);
00349        *cachep = NULL;
00350        return( LDAP_SIZELIMIT_EXCEEDED );
00351     }
00352 
00353     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init new cache 0x%x\n",
00354            *cachep, 0, 0 );
00355 
00356     return( LDAP_SUCCESS );
00357 }
00358 
00359 /* Associates a ldap handle to a memcache object. */
00360 int
00361 LDAP_CALL
00362 ldap_memcache_set( LDAP *ld, LDAPMemCache *cache )
00363 {
00364     int nRes = LDAP_SUCCESS;
00365 
00366     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_set\n", 0, 0, 0 );
00367 
00368     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) )
00369        return( LDAP_PARAM_ERROR );
00370 
00371     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00372 
00373     if (ld->ld_memcache != cache) {
00374 
00375         LDAPMemCache *c = ld->ld_memcache;
00376        ldapmemcacheld *pCur = NULL;
00377        ldapmemcacheld *pPrev = NULL;
00378 
00379        /* First dissociate handle from old cache */
00380 
00381        LDAP_MEMCACHE_MUTEX_LOCK( c );
00382 
00383        pCur = (c ? c->ldmemc_lds : NULL);
00384        for (; pCur; pCur = pCur->ldmemcl_next) {
00385            if (pCur->ldmemcl_ld == ld)
00386               break;
00387            pPrev = pCur;
00388        }
00389 
00390        if (pCur) {
00391 
00392            ldapmemcacheReqId reqid;
00393 
00394            reqid.ldmemcrid_ld = ld;
00395            reqid.ldmemcrid_msgid = -1;
00396            htable_misc(c->ldmemc_resTmp, (void*)&reqid, (void*)c);
00397 
00398            if (pPrev)
00399               pPrev->ldmemcl_next = pCur->ldmemcl_next;
00400            else
00401               c->ldmemc_lds = pCur->ldmemcl_next;
00402            NSLDAPI_FREE(pCur);
00403            pCur = NULL;
00404 
00405            memcache_adj_size(c, sizeof(ldapmemcacheld),
00406                        MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT);
00407        }
00408 
00409        LDAP_MEMCACHE_MUTEX_UNLOCK( c );
00410 
00411        ld->ld_memcache = NULL;
00412 
00413        /* Exit if no new cache is specified */
00414        if (cache == NULL) {
00415            LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00416            return( LDAP_SUCCESS );
00417        }
00418 
00419        /* Then associate handle with new cache */
00420 
00421         LDAP_MEMCACHE_MUTEX_LOCK( cache );
00422 
00423        if ((nRes = memcache_adj_size(cache, sizeof(ldapmemcacheld),
00424               MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_ADD)) != LDAP_SUCCESS) {
00425            LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
00426            LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00427            return nRes;
00428        }
00429 
00430        pCur = (ldapmemcacheld*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheld));
00431        if (pCur == NULL) {
00432            memcache_adj_size(cache, sizeof(ldapmemcacheld), 
00433                             MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT);
00434            nRes = LDAP_NO_MEMORY;
00435        } else {
00436            pCur->ldmemcl_ld = ld;
00437            pCur->ldmemcl_next = cache->ldmemc_lds;
00438            cache->ldmemc_lds = pCur;
00439            ld->ld_memcache = cache;
00440        }
00441 
00442        LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
00443     }
00444 
00445     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00446 
00447     return nRes;
00448 }
00449 
00450 /* Retrieves memcache with which the ldap handle has been associated. */
00451 int
00452 LDAP_CALL
00453 ldap_memcache_get( LDAP *ld, LDAPMemCache **cachep )
00454 {
00455     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_get ld: 0x%x\n", ld, 0, 0 );
00456 
00457     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cachep == NULL ) { 
00458        return( LDAP_PARAM_ERROR );
00459     }
00460 
00461     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00462     *cachep = ld->ld_memcache;
00463     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00464 
00465     return( LDAP_SUCCESS );
00466 }
00467 
00468 /*
00469  * Function that stays inside libldap and proactively expires items from
00470  * the given cache.  This should be called from a newly created thread since
00471  * it will not return until after ldap_memcache_destroy() is called.
00472  */
00473 void
00474 LDAP_CALL
00475 ldap_memcache_update( LDAPMemCache *cache )
00476 {
00477     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_update: cache 0x%x\n",
00478            cache, 0, 0 );
00479 
00480     if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
00481        return;
00482     }
00483 
00484     LDAP_MEMCACHE_MUTEX_LOCK( cache );
00485     memcache_access(cache, MEMCACHE_ACCESS_UPDATE, NULL, NULL, NULL);
00486     LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
00487 }
00488 
00489 /* Removes specified entries from given memcache. */
00490 void
00491 LDAP_CALL
00492 ldap_memcache_flush( LDAPMemCache *cache, char *dn, int scope )
00493 {
00494     LDAPDebug( LDAP_DEBUG_TRACE,
00495            "ldap_memcache_flush( cache: 0x%x, dn: %s, scope: %d)\n",
00496            cache, ( dn == NULL ) ? "(null)" : dn, scope );
00497 
00498     if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
00499        return;
00500     }
00501 
00502     LDAP_MEMCACHE_MUTEX_LOCK( cache );
00503 
00504     if (!dn) {
00505        memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL);
00506     } else {
00507        memcache_access(cache, MEMCACHE_ACCESS_FLUSH, 
00508                        (void*)dn, (void*)scope, NULL);
00509     }
00510 
00511     LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
00512 }
00513 
00514 /* Destroys the given memcache. */
00515 void
00516 LDAP_CALL
00517 ldap_memcache_destroy( LDAPMemCache *cache )
00518 {
00519     int i = 0;
00520     unsigned long size = sizeof(LDAPMemCache);
00521     ldapmemcacheld *pNode = NULL, *pNextNode = NULL;
00522 
00523     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_destroy( 0x%x )\n",
00524            cache, 0, 0 );
00525 
00526     if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
00527        return;
00528     }
00529 
00530     /* Dissociate all ldap handes from this cache. */
00531     LDAP_MEMCACHE_MUTEX_LOCK( cache );
00532 
00533     for (pNode = cache->ldmemc_lds; pNode; pNode = pNextNode, i++) {
00534         LDAP_MUTEX_LOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK );
00535        cache->ldmemc_lds = pNode->ldmemcl_next;
00536        pNode->ldmemcl_ld->ld_memcache = NULL;
00537         LDAP_MUTEX_UNLOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK );
00538        pNextNode = pNode->ldmemcl_next;
00539        NSLDAPI_FREE(pNode);
00540     }
00541 
00542     size += i * sizeof(ldapmemcacheld);
00543 
00544     LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
00545 
00546     /* Free array of basedns */
00547     if (cache->ldmemc_basedns) {
00548        for (i = 0; cache->ldmemc_basedns[i]; i++) {
00549            size += strlen(cache->ldmemc_basedns[i]) + 1;
00550            NSLDAPI_FREE(cache->ldmemc_basedns[i]);
00551        }
00552        size += (i + 1) * sizeof(char*);
00553        NSLDAPI_FREE(cache->ldmemc_basedns);
00554     }
00555 
00556     /* Free hash table used for temporary cache */
00557     if (cache->ldmemc_resTmp) {
00558        size += htable_sizeinbytes(cache->ldmemc_resTmp);
00559        memcache_access(cache, MEMCACHE_ACCESS_DELETE_ALL, NULL, NULL, NULL);
00560        htable_free(cache->ldmemc_resTmp);
00561     }
00562 
00563     /* Free hash table used for primary cache */
00564     if (cache->ldmemc_resLookup) {
00565        size += htable_sizeinbytes(cache->ldmemc_resLookup);
00566        memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL);
00567        htable_free(cache->ldmemc_resLookup);
00568     }
00569 
00570     memcache_adj_size(cache, size, MEMCACHE_SIZE_NON_ENTRIES, 
00571                      MEMCACHE_SIZE_DEDUCT);
00572 
00573     LDAP_MEMCACHE_MUTEX_FREE( cache );
00574 
00575     NSLDAPI_FREE(cache);
00576 }
00577 
00578 /************************* Internal API Functions ****************************/
00579 
00580 /* Creates an integer key by applying the Cyclic Reduntency Check algorithm on
00581    a long string formed by concatenating all the search parameters plus the
00582    current bind DN.  The key is used in the cache for looking up cached
00583    entries.  It is assumed that the CRC algorithm will generate
00584    different integers from different byte strings. */
00585 int
00586 ldap_memcache_createkey(LDAP *ld, const char *base, int scope, 
00587                      const char *filter, char **attrs, 
00588                         int attrsonly, LDAPControl **serverctrls, 
00589                         LDAPControl **clientctrls, unsigned long *keyp)
00590 {
00591     int nRes, i, j, i_smallest;
00592     int len;
00593     int defport;
00594     char buf[50];
00595     char *tmp, *defhost, *binddn, *keystr, *tmpbase;
00596 
00597     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (keyp == NULL) )
00598        return( LDAP_PARAM_ERROR );
00599 
00600     *keyp = 0;
00601 
00602     if (!memcache_exist(ld))
00603        return( LDAP_LOCAL_ERROR );
00604 
00605     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00606     LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
00607     nRes = memcache_validate_basedn(ld->ld_memcache, base);
00608     LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
00609     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00610 
00611     if (nRes != LDAP_SUCCESS)
00612        return nRes;
00613 
00614     defhost = NSLDAPI_STR_NONNULL(ld->ld_defhost);
00615     defport = ld->ld_defport;
00616     tmpbase = nsldapi_strdup(NSLDAPI_STR_NONNULL(base));
00617     memcache_trim_basedn_spaces(tmpbase);
00618 
00619     if ((binddn = nsldapi_get_binddn(ld)) == NULL)
00620        binddn = "";
00621 
00622     sprintf(buf, "%i\n%i\n%i\n", defport, scope, (attrsonly ? 1 : 0));
00623     len = NSLDAPI_SAFE_STRLEN(buf) + NSLDAPI_SAFE_STRLEN(tmpbase) +
00624          NSLDAPI_SAFE_STRLEN(filter) + NSLDAPI_SAFE_STRLEN(defhost) +
00625          NSLDAPI_SAFE_STRLEN(binddn);
00626 
00627     if (attrs) {
00628        for (i = 0; attrs[i]; i++) {
00629 
00630            for (i_smallest = j = i; attrs[j]; j++) {
00631               if (strcasecmp(attrs[i_smallest], attrs[j]) > 0)
00632                   i_smallest = j;
00633            }
00634 
00635            if (i != i_smallest) {
00636               tmp = attrs[i];
00637               attrs[i] = attrs[i_smallest];
00638               attrs[i_smallest] = tmp;
00639            }
00640 
00641            len += NSLDAPI_SAFE_STRLEN(attrs[i]);
00642        }
00643     } else {
00644        len += 1;
00645     }
00646 
00647     len += memcache_get_ctrls_len(serverctrls) + 
00648           memcache_get_ctrls_len(clientctrls) + 1;
00649 
00650     if ((keystr = (char*)NSLDAPI_CALLOC(len, sizeof(char))) == NULL) {
00651        NSLDAPI_FREE(defhost);
00652        return( LDAP_NO_MEMORY );
00653     }
00654 
00655     sprintf(keystr, "%s\n%s\n%s\n%s\n%s\n", binddn, tmpbase,
00656            NSLDAPI_STR_NONNULL(defhost), NSLDAPI_STR_NONNULL(filter), 
00657            NSLDAPI_STR_NONNULL(buf));
00658 
00659     if (attrs) {
00660        for (i = 0; attrs[i]; i++) {
00661            strcat(keystr, NSLDAPI_STR_NONNULL(attrs[i]));
00662            strcat(keystr, "\n");
00663        }
00664     } else {
00665        strcat(keystr, "\n");
00666     }
00667 
00668     for (tmp = keystr; *tmp; 
00669          *tmp += (*tmp >= 'a' && *tmp <= 'z' ? 'A'-'a' : 0), tmp++) {
00670               ;
00671        }
00672 
00673     memcache_append_ctrls(keystr, serverctrls, clientctrls);
00674 
00675     /* CRC algorithm */
00676     *keyp = crc32_convert(keystr, len);
00677 
00678     NSLDAPI_FREE(keystr);
00679     NSLDAPI_FREE(tmpbase);
00680 
00681     return LDAP_SUCCESS;
00682 }
00683 
00684 /* Searches the cache for the right cached entries, and if found, attaches
00685    them to the given ldap handle.  This function relies on locking by the
00686    caller. */
00687 int
00688 ldap_memcache_result(LDAP *ld, int msgid, unsigned long key)
00689 {
00690     int nRes;
00691     LDAPMessage *pMsg = NULL;
00692 
00693     LDAPDebug( LDAP_DEBUG_TRACE,
00694            "ldap_memcache_result( ld: 0x%x, msgid: %d, key: 0x%8.8lx)\n",
00695            ld, msgid, key );
00696 
00697     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) {
00698        return( LDAP_PARAM_ERROR );
00699     }
00700 
00701     if (!memcache_exist(ld)) {
00702        return( LDAP_LOCAL_ERROR );
00703     }
00704 
00705     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00706     LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
00707 
00708     /* Search the cache and append the results to ld if found */
00709     ++ld->ld_memcache->ldmemc_stats.ldmemcstat_tries;
00710     if ((nRes = memcache_search(ld, key, &pMsg)) == LDAP_SUCCESS) {
00711        nRes = memcache_add_to_ld(ld, msgid, pMsg);
00712        ++ld->ld_memcache->ldmemc_stats.ldmemcstat_hits;
00713        LDAPDebug( LDAP_DEBUG_TRACE,
00714               "ldap_memcache_result: key 0x%8.8lx found in cache\n",
00715               key, 0, 0 );
00716     } else {
00717        LDAPDebug( LDAP_DEBUG_TRACE,
00718               "ldap_memcache_result: key 0x%8.8lx not found in cache\n",
00719               key, 0, 0 );
00720     }
00721 
00722 #ifdef LDAP_DEBUG
00723     memcache_print_list( ld->ld_memcache, LIST_LRU );
00724     memcache_report_statistics( ld->ld_memcache );
00725 #endif /* LDAP_DEBUG */
00726 
00727     LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
00728     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00729 
00730     return nRes;
00731 }
00732 
00733 /* Creates a new header in the cache so that entries arriving from the
00734    directory server can later be cached under the header. */
00735 int
00736 ldap_memcache_new(LDAP *ld, int msgid, unsigned long key, const char *basedn)
00737 {
00738     int nRes;
00739 
00740     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) ) {
00741        return( LDAP_PARAM_ERROR );
00742     }
00743 
00744     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00745 
00746     if (!memcache_exist(ld)) {
00747         LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00748        return( LDAP_LOCAL_ERROR );
00749     }
00750 
00751     LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
00752     nRes = memcache_add(ld, key, msgid, basedn);
00753     LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
00754     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00755 
00756     return nRes;
00757 }
00758 
00759 /* Appends a chain of entries to an existing cache header.  Parameter "bLast"
00760    indicates whether there will be more entries arriving for the search in
00761    question. */
00762 int
00763 ldap_memcache_append(LDAP *ld, int msgid, int bLast, LDAPMessage *result)
00764 {
00765     int nRes = LDAP_SUCCESS;
00766 
00767     LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_append( ld: 0x%x, ", ld, 0, 0 );
00768     LDAPDebug( LDAP_DEBUG_TRACE, "msgid %d, bLast: %d, result: 0x%x)\n",
00769            msgid, bLast, result );
00770 
00771     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || !result ) {
00772        return( LDAP_PARAM_ERROR );
00773     }
00774 
00775     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00776 
00777     if (!memcache_exist(ld)) {
00778         LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00779        return( LDAP_LOCAL_ERROR );
00780     }
00781 
00782     LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
00783 
00784     if (!bLast)
00785        nRes = memcache_append(ld, msgid, result);
00786     else
00787        nRes = memcache_append_last(ld, msgid, result);
00788 
00789     LDAPDebug( LDAP_DEBUG_TRACE,
00790            "ldap_memcache_append: %s result for msgid %d\n",
00791            ( nRes == LDAP_SUCCESS ) ? "added" : "failed to add", msgid , 0 );
00792 
00793     LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
00794     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00795 
00796     return nRes;
00797 }
00798 
00799 /* Removes partially cached results for a search as a result of calling
00800    ldap_abandon() by the client. */
00801 int
00802 ldap_memcache_abandon(LDAP *ld, int msgid)
00803 {
00804     int nRes;
00805 
00806     if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) {
00807        return( LDAP_PARAM_ERROR );
00808     }
00809 
00810     LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
00811 
00812     if (!memcache_exist(ld)) {
00813         LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00814        return( LDAP_LOCAL_ERROR );
00815     }
00816 
00817     LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
00818     nRes = memcache_remove(ld, msgid);
00819     LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
00820     LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
00821 
00822     return nRes;
00823 }
00824 
00825 /*************************** helper functions *******************************/
00826 
00827 /* Removes extraneous spaces in a basedn so that basedns differ by only those
00828    spaces will be treated as equal.  Extraneous spaces are those that
00829    precedes the basedn and those that follow a comma. */
00830 /*
00831  * XXXmcs: this is a bit too agressive... we need to deal with the fact that
00832  * commas and spaces may be quoted, in which case it is wrong to remove them.
00833  */
00834 static void
00835 memcache_trim_basedn_spaces(char *basedn)
00836 {
00837     char *pRead, *pWrite;
00838 
00839     if (!basedn) 
00840        return;
00841 
00842     for (pWrite = pRead = basedn; *pRead; ) {
00843        for (; *pRead && NSLDAPI_IS_SPACE(*pRead); pRead++) {
00844               ;
00845        }
00846        for (; *pRead && !NSLDAPI_IS_SEPARATER(*pRead);
00847            *(pWrite++) = *(pRead++)) {
00848            ;
00849        }
00850        *(pWrite++) = (*pRead ? *(pRead++) : *pRead);
00851     }
00852 }
00853 
00854 /* Verifies whether the results of a search should be cached or not by
00855    checking if the search's basedn falls under any of the basedns for which
00856    the memcache is responsible. */
00857 static int
00858 memcache_validate_basedn(LDAPMemCache *cache, const char *basedn)
00859 {
00860     int i;
00861 
00862     if ( cache->ldmemc_basedns == NULL ) {
00863        return( LDAP_SUCCESS );
00864     }
00865 
00866 #if 1
00867     if (basedn == NULL) {
00868        basedn = "";
00869     }
00870 #else
00871     /* XXXmcs: I do not understand this code... */
00872     if (basedn == NULL)
00873        return (cache->ldmemc_basedns && cache->ldmemc_basedns[0] ?
00874                                     LDAP_OPERATIONS_ERROR : LDAP_SUCCESS);
00875     }
00876 #endif
00877 
00878     for (i = 0; cache->ldmemc_basedns[i]; i++) {
00879        if (memcache_compare_dn(basedn, cache->ldmemc_basedns[i], 
00880                                LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) {
00881            return( LDAP_SUCCESS );
00882        }
00883     }
00884 
00885     return( LDAP_OPERATIONS_ERROR );
00886 }
00887 
00888 /* Calculates the length of the buffer needed to concatenate the contents of
00889    a ldap control. */
00890 static int
00891 memcache_get_ctrls_len(LDAPControl **ctrls)
00892 {
00893     int len = 0, i;
00894 
00895     if (ctrls) {
00896        for (i = 0; ctrls[i]; i++) {
00897            len += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) +
00898                   (ctrls[i]->ldctl_value).bv_len + 4;
00899        }
00900     }
00901 
00902     return len;
00903 }
00904 
00905 /* Contenates the contents of client and server controls to a buffer. */
00906 static void
00907 memcache_append_ctrls(char *buf, LDAPControl **serverCtrls,
00908                               LDAPControl **clientCtrls)
00909 {
00910     int i, j;
00911     char *pCh = buf + strlen(buf);
00912     LDAPControl **ctrls;
00913 
00914     for (j = 0; j < 2; j++) {
00915 
00916        if ((ctrls = (j ? clientCtrls : serverCtrls)) == NULL)
00917            continue;
00918 
00919        for (i = 0; ctrls[i]; i++) {
00920            sprintf(pCh, "%s\n", NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid));
00921            pCh += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) + 1;
00922            if ((ctrls[i]->ldctl_value).bv_len > 0) {
00923               memcpy(pCh, (ctrls[i]->ldctl_value).bv_val, 
00924                      (ctrls[i]->ldctl_value).bv_len);
00925               pCh += (ctrls[i]->ldctl_value).bv_len;
00926            }
00927            sprintf(pCh, "\n%i\n", (ctrls[i]->ldctl_iscritical ? 1 : 0));
00928            pCh += 3;
00929        }
00930     }
00931 }
00932 
00933 /* Increases or decreases the size (in bytes) the given memcache currently
00934    uses.  If the size goes over the limit, the function returns an error. */
00935 static int
00936 memcache_adj_size(LDAPMemCache *cache, unsigned long size,
00937                   int usageFlags, int bAdd)
00938 {
00939     LDAPDebug( LDAP_DEBUG_TRACE,
00940            "memcache_adj_size: attempting to %s %ld %s bytes...\n",
00941            bAdd ? "add" : "remove", size,
00942            ( usageFlags & MEMCACHE_SIZE_ENTRIES ) ? "entry" : "non-entry" );
00943 
00944     if (bAdd) {
00945        cache->ldmemc_size_used += size;
00946        if ((cache->ldmemc_size > 0) &&
00947            (cache->ldmemc_size_used > cache->ldmemc_size)) {
00948 
00949            if (size > cache->ldmemc_size_entries) {
00950                cache->ldmemc_size_used -= size;
00951               LDAPDebug( LDAP_DEBUG_TRACE,
00952                      "memcache_adj_size: failed (size > size_entries %ld).\n",
00953                      cache->ldmemc_size_entries, 0, 0 );
00954               return( LDAP_SIZELIMIT_EXCEEDED );
00955            }
00956 
00957            while (cache->ldmemc_size_used > cache->ldmemc_size) {
00958               if (memcache_access(cache, MEMCACHE_ACCESS_FLUSH_LRU,
00959                                   NULL, NULL, NULL) != LDAP_SUCCESS) {
00960                    cache->ldmemc_size_used -= size;
00961                   LDAPDebug( LDAP_DEBUG_TRACE,
00962                          "memcache_adj_size: failed (LRU flush failed).\n",
00963                          0, 0, 0 );
00964                   return( LDAP_SIZELIMIT_EXCEEDED );
00965                }
00966            }
00967        }
00968        if (usageFlags & MEMCACHE_SIZE_ENTRIES)
00969            cache->ldmemc_size_entries += size;
00970     } else {
00971        cache->ldmemc_size_used -= size;
00972        assert(cache->ldmemc_size_used >= 0);
00973        if (usageFlags & MEMCACHE_SIZE_ENTRIES)
00974            cache->ldmemc_size_entries -= size;
00975     }
00976 
00977 #ifdef LDAP_DEBUG
00978     if ( cache->ldmemc_size == 0 ) {      /* no size limit */
00979        LDAPDebug( LDAP_DEBUG_TRACE,
00980               "memcache_adj_size: succeeded (new size: %ld bytes).\n",
00981               cache->ldmemc_size_used, 0, 0 );
00982     } else {
00983        LDAPDebug( LDAP_DEBUG_TRACE,
00984               "memcache_adj_size: succeeded (new size: %ld bytes, "
00985               "free space: %ld bytes).\n", cache->ldmemc_size_used,
00986               cache->ldmemc_size - cache->ldmemc_size_used, 0 );
00987     }
00988 #endif /* LDAP_DEBUG */
00989 
00990     return( LDAP_SUCCESS );
00991 }
00992 
00993 /* Searches the cache for results for a particular search identified by
00994    parameter "key", which was generated ldap_memcache_createkey(). */
00995 static int
00996 memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes)
00997 {
00998     int nRes;
00999     ldapmemcacheRes *pRes;
01000 
01001     *ppRes = NULL;
01002 
01003     if (!memcache_exist(ld))
01004         return LDAP_LOCAL_ERROR;
01005 
01006     nRes = memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_FIND,
01007                           (void*)&key, (void*)(&pRes), NULL);
01008 
01009     if (nRes != LDAP_SUCCESS)
01010        return nRes;
01011 
01012     *ppRes = pRes->ldmemcr_resHead;
01013     assert((pRes->ldmemcr_req_id).ldmemcrid_msgid == -1);
01014 
01015     return( LDAP_SUCCESS );
01016 }
01017 
01018 /* Adds a new header into the cache as a place holder for entries
01019    arriving later. */
01020 static int
01021 memcache_add(LDAP *ld, unsigned long key, int msgid,
01022                      const char *basedn)
01023 {
01024     ldapmemcacheReqId reqid;
01025 
01026     if (!memcache_exist(ld))
01027         return LDAP_LOCAL_ERROR;
01028 
01029     reqid.ldmemcrid_msgid = msgid;
01030     reqid.ldmemcrid_ld = ld;
01031 
01032     return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_ADD,
01033                           (void*)&key, (void*)&reqid, (void*)basedn);
01034 }
01035 
01036 /* Appends search entries arriving from the dir server to the cache. */
01037 static int
01038 memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes)
01039 {
01040     ldapmemcacheReqId reqid;
01041 
01042     if (!memcache_exist(ld))
01043         return LDAP_LOCAL_ERROR;
01044 
01045     reqid.ldmemcrid_msgid = msgid;
01046     reqid.ldmemcrid_ld = ld;
01047 
01048     return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND,
01049                           (void*)&reqid, (void*)pRes, NULL);
01050 }
01051 
01052 /* Same as memcache_append(), but the entries being appended are the
01053    last from the dir server.  Once all entries for a search have arrived,
01054    the entries are moved from secondary to primary cache, and a time
01055    stamp is given to the entries. */
01056 static int
01057 memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes)
01058 {
01059     ldapmemcacheReqId reqid;
01060 
01061     if (!memcache_exist(ld))
01062         return LDAP_LOCAL_ERROR;
01063 
01064     reqid.ldmemcrid_msgid = msgid;
01065     reqid.ldmemcrid_ld = ld;
01066 
01067     return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND_LAST,
01068                           (void*)&reqid, (void*)pRes, NULL);
01069 }
01070 
01071 /* Removes entries from the temporary cache. */
01072 static int
01073 memcache_remove(LDAP *ld, int msgid)
01074 {
01075     ldapmemcacheReqId reqid;
01076 
01077     if (!memcache_exist(ld))
01078         return LDAP_LOCAL_ERROR;
01079 
01080     reqid.ldmemcrid_msgid = msgid;
01081     reqid.ldmemcrid_ld = ld;
01082 
01083     return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE,
01084                           (void*)&reqid, NULL, NULL);
01085 }
01086 
01087 #if 0 /* this function is not used */
01088 /* Wipes out everything in the temporary cache directory. */
01089 static int
01090 memcache_remove_all(LDAP *ld)
01091 {
01092     if (!memcache_exist(ld))
01093         return LDAP_LOCAL_ERROR;
01094 
01095     return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE_ALL,
01096                           NULL, NULL, NULL);
01097 }
01098 #endif /* 0 */
01099 
01100 /* Returns TRUE or FALSE */
01101 static int
01102 memcache_exist(LDAP *ld)
01103 {
01104     return (ld->ld_memcache != NULL);
01105 }
01106 
01107 /* Attaches cached entries to an ldap handle. */
01108 static int
01109 memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg)
01110 {
01111     int nRes = LDAP_SUCCESS;
01112     LDAPMessage **r;
01113     LDAPMessage *pCopy;
01114 
01115     nRes = memcache_dup_message(pMsg, msgid, 1, &pCopy, NULL);
01116     if (nRes != LDAP_SUCCESS)
01117        return nRes;
01118 
01119     for (r = &(ld->ld_responses); *r; r = &((*r)->lm_next))
01120        if ((*r)->lm_msgid == msgid)
01121            break;
01122 
01123     if (*r)
01124        for (r = &((*r)->lm_chain); *r; r = &((*r)->lm_chain)) {
01125               ;
01126        }
01127 
01128     *r = pCopy;
01129     
01130     return nRes;
01131 }
01132 
01133 /* Check if main_dn is included in {dn, scope} */
01134 static int
01135 memcache_compare_dn(const char *main_dn, const char *dn, int scope)
01136 {
01137     int nRes;
01138     char **components = NULL;
01139     char **main_components = NULL;
01140 
01141     components = ldap_explode_dn(dn, 0);
01142     main_components = ldap_explode_dn(main_dn, 0);
01143 
01144     if (!components || !main_components) {
01145        nRes = LDAP_COMPARE_TRUE;
01146     }
01147     else {
01148 
01149        int i, main_i;
01150 
01151        main_i = ldap_count_values(main_components) - 1;
01152        i = ldap_count_values(components) - 1;
01153 
01154        for (; i >= 0 && main_i >= 0; i--, main_i--) {
01155            if (strcasecmp(main_components[main_i], components[i]))
01156               break;
01157        }
01158 
01159        if (i >= 0 && main_i >= 0) {
01160            nRes = LDAP_COMPARE_FALSE;
01161        }
01162        else if (i < 0 && main_i < 0) {
01163            if (scope != LDAP_SCOPE_ONELEVEL)
01164               nRes = LDAP_COMPARE_TRUE;
01165            else
01166               nRes = LDAP_COMPARE_FALSE;
01167        }
01168        else if (main_i < 0) {
01169            nRes = LDAP_COMPARE_FALSE;
01170        }
01171        else {
01172            if (scope == LDAP_SCOPE_BASE) 
01173               nRes = LDAP_COMPARE_FALSE;
01174            else if (scope == LDAP_SCOPE_SUBTREE)
01175               nRes = LDAP_COMPARE_TRUE;
01176            else if (main_i == 0)
01177               nRes = LDAP_COMPARE_TRUE;
01178            else
01179               nRes = LDAP_COMPARE_FALSE;
01180        }
01181     }
01182 
01183     if (components)
01184        ldap_value_free(components);
01185 
01186     if (main_components)
01187        ldap_value_free(main_components);
01188 
01189     return nRes;
01190 }
01191 
01192 /* Dup a complete separate copy of a berelement, including the buffers
01193    the berelement points to. */
01194 static BerElement*
01195 memcache_ber_dup(BerElement* pBer, unsigned long *pSize)
01196 {
01197     BerElement *p = ber_dup(pBer);
01198 
01199     *pSize = 0;
01200 
01201     if (p) {
01202 
01203        *pSize += sizeof(BerElement) + EXTRA_SIZE;
01204 
01205        if (p->ber_len <= EXTRA_SIZE) {
01206            p->ber_flags |= LBER_FLAG_NO_FREE_BUFFER;
01207            p->ber_buf = (char*)p + sizeof(BerElement);
01208        } else {
01209            p->ber_flags &= ~LBER_FLAG_NO_FREE_BUFFER;
01210            p->ber_buf = (char*)NSLDAPI_CALLOC(1, p->ber_len);
01211            *pSize += (p->ber_buf ? p->ber_len : 0);
01212        }
01213 
01214        if (p->ber_buf) {
01215            p->ber_ptr = p->ber_buf + (pBer->ber_ptr - pBer->ber_buf);
01216            p->ber_end = p->ber_buf + p->ber_len;
01217            memcpy(p->ber_buf, pBer->ber_buf, p->ber_len);
01218        } else {
01219            ber_free(p, 0);
01220            p = NULL;
01221            *pSize = 0;
01222        }
01223     }
01224 
01225     return p;
01226 }
01227 
01228 /* Dup a entry or a chain of entries. */
01229 static int
01230 memcache_dup_message(LDAPMessage *res, int msgid, int fromcache,
01231                             LDAPMessage **ppResCopy, unsigned long *pSize)
01232 {
01233     int nRes = LDAP_SUCCESS;
01234     unsigned long ber_size;
01235     LDAPMessage *pCur;
01236     LDAPMessage **ppCurNew;
01237 
01238     *ppResCopy = NULL;
01239 
01240     if (pSize)
01241        *pSize = 0;
01242 
01243     /* Make a copy of res */
01244     for (pCur = res, ppCurNew = ppResCopy; pCur; 
01245          pCur = pCur->lm_chain, ppCurNew = &((*ppCurNew)->lm_chain)) {
01246 
01247        if ((*ppCurNew = (LDAPMessage*)NSLDAPI_CALLOC(1, 
01248                                             sizeof(LDAPMessage))) == NULL) {
01249            nRes = LDAP_NO_MEMORY;
01250            break;
01251        }
01252 
01253        memcpy(*ppCurNew, pCur, sizeof(LDAPMessage));
01254        (*ppCurNew)->lm_next = NULL;
01255        (*ppCurNew)->lm_ber = memcache_ber_dup(pCur->lm_ber, &ber_size);
01256        (*ppCurNew)->lm_msgid = msgid;
01257        (*ppCurNew)->lm_fromcache = (fromcache != 0);
01258 
01259        if (pSize)
01260            *pSize += sizeof(LDAPMessage) + ber_size;
01261     }
01262 
01263     if ((nRes != LDAP_SUCCESS) && (*ppResCopy != NULL)) {
01264        ldap_msgfree(*ppResCopy);
01265        *ppResCopy = NULL;
01266        if (pSize)
01267            *pSize = 0;
01268     }
01269 
01270     return nRes;
01271 }
01272 
01273 /************************* Cache Functions ***********************/
01274 
01275 /* Frees a cache header. */
01276 static int
01277 memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes)
01278 {
01279     if (pRes) {
01280 
01281        unsigned long size = sizeof(ldapmemcacheRes); 
01282 
01283        if (pRes->ldmemcr_basedn) {
01284            size += strlen(pRes->ldmemcr_basedn) + 1;
01285            NSLDAPI_FREE(pRes->ldmemcr_basedn);
01286        }
01287 
01288        if (pRes->ldmemcr_resHead) {
01289            size += pRes->ldmemcr_resSize;
01290            ldap_msgfree(pRes->ldmemcr_resHead);
01291        }
01292 
01293        NSLDAPI_FREE(pRes);
01294 
01295        memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
01296                          MEMCACHE_SIZE_DEDUCT);
01297     }
01298 
01299     return( LDAP_SUCCESS );
01300 }
01301 
01302 /* Detaches a cache header from the list of headers. */
01303 static int
01304 memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index)
01305 {
01306     if (pRes->ldmemcr_prev[index])
01307        pRes->ldmemcr_prev[index]->ldmemcr_next[index] = 
01308                                             pRes->ldmemcr_next[index];
01309 
01310     if (pRes->ldmemcr_next[index])
01311        pRes->ldmemcr_next[index]->ldmemcr_prev[index] = 
01312                                             pRes->ldmemcr_prev[index];
01313 
01314     if (cache->ldmemc_resHead[index] == pRes)
01315        cache->ldmemc_resHead[index] = pRes->ldmemcr_next[index];
01316 
01317     if (cache->ldmemc_resTail[index] == pRes)
01318        cache->ldmemc_resTail[index] = pRes->ldmemcr_prev[index];
01319 
01320     pRes->ldmemcr_prev[index] = NULL;
01321     pRes->ldmemcr_next[index] = NULL;
01322 
01323     return( LDAP_SUCCESS );
01324 }
01325 
01326 /* Inserts a new cache header to a list of headers. */
01327 static int
01328 memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index)
01329 {
01330     if (cache->ldmemc_resHead[index])
01331        cache->ldmemc_resHead[index]->ldmemcr_prev[index] = pRes;
01332     else
01333        cache->ldmemc_resTail[index] = pRes;
01334 
01335     pRes->ldmemcr_prev[index] = NULL;
01336     pRes->ldmemcr_next[index] = cache->ldmemc_resHead[index];
01337     cache->ldmemc_resHead[index] = pRes;
01338 
01339     return( LDAP_SUCCESS );
01340 }
01341 
01342 /* Appends a chain of entries to the given cache header. */
01343 static int
01344 memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg,
01345                                 unsigned long size)
01346 {
01347     if (pRes->ldmemcr_resTail)
01348        pRes->ldmemcr_resTail->lm_chain = pMsg;
01349     else
01350        pRes->ldmemcr_resHead = pMsg;
01351 
01352     for (pRes->ldmemcr_resTail = pMsg;
01353          pRes->ldmemcr_resTail->lm_chain;
01354          pRes->ldmemcr_resTail = pRes->ldmemcr_resTail->lm_chain) {
01355               ;
01356        }
01357 
01358     pRes->ldmemcr_resSize += size;
01359 
01360     return( LDAP_SUCCESS );
01361 }
01362 
01363 
01364 #ifdef LDAP_DEBUG
01365 static void
01366 memcache_print_list( LDAPMemCache *cache, int index )
01367 {
01368     char             *name;
01369     ldapmemcacheRes  *restmp;
01370 
01371     switch( index ) {
01372     case LIST_TTL:
01373        name = "TTL";
01374        break;
01375     case LIST_LRU:
01376        name = "LRU";
01377        break;
01378     case LIST_TMP:
01379        name = "TMP";
01380        break;
01381     case LIST_TOTAL:
01382        name = "TOTAL";
01383        break;
01384     default:
01385        name = "unknown";
01386     }
01387 
01388     LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x %s list:\n",
01389            cache, name, 0 );
01390     for ( restmp = cache->ldmemc_resHead[index]; restmp != NULL;
01391            restmp = restmp->ldmemcr_next[index] ) {
01392        LDAPDebug( LDAP_DEBUG_TRACE,
01393               "    key: 0x%8.8lx, ld: 0x%x, msgid: %d\n",
01394               restmp->ldmemcr_crc_key,
01395               restmp->ldmemcr_req_id.ldmemcrid_ld,
01396               restmp->ldmemcr_req_id.ldmemcrid_msgid );
01397     }
01398     LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x end of %s list.\n",
01399            cache, name, 0 );
01400 }
01401 #endif /* LDAP_DEBUG */
01402 
01403 /* Tells whether a cached result has expired. */
01404 static int
01405 memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes,
01406                  unsigned long curTime)
01407 {
01408     if (!cache->ldmemc_ttl)
01409        return 0;
01410 
01411     return ((unsigned long)difftime(
01412                             (time_t)curTime, 
01413                           (time_t)(pRes->ldmemcr_timestamp)) >=
01414                                                cache->ldmemc_ttl);
01415 }
01416 
01417 /* Operates the cache in a central place. */
01418 static int
01419 memcache_access(LDAPMemCache *cache, int mode, 
01420                         void *pData1, void *pData2, void *pData3)
01421 {
01422     int nRes = LDAP_SUCCESS;
01423     unsigned long size = 0;
01424 
01425     /* Add a new cache header to the cache. */
01426     if (mode == MEMCACHE_ACCESS_ADD) {
01427        unsigned long key = *((unsigned long*)pData1);
01428        char *basedn = (char*)pData3;
01429        ldapmemcacheRes *pRes = NULL;
01430 
01431        nRes = htable_get(cache->ldmemc_resTmp, pData2, (void**)&pRes);
01432        if (nRes == LDAP_SUCCESS)
01433            return( LDAP_ALREADY_EXISTS );
01434 
01435        pRes = (ldapmemcacheRes*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheRes));
01436        if (pRes == NULL)
01437            return( LDAP_NO_MEMORY );
01438 
01439        pRes->ldmemcr_crc_key = key;
01440        pRes->ldmemcr_req_id = *((ldapmemcacheReqId*)pData2);
01441        pRes->ldmemcr_basedn = (basedn ? nsldapi_strdup(basedn) : NULL);
01442 
01443        size += sizeof(ldapmemcacheRes) + strlen(basedn) + 1;
01444        nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
01445                                 MEMCACHE_SIZE_ADD);
01446        if (nRes == LDAP_SUCCESS)
01447            nRes = htable_put(cache->ldmemc_resTmp, pData2, (void*)pRes);
01448        if (nRes == LDAP_SUCCESS)
01449            memcache_add_to_list(cache, pRes, LIST_TMP);
01450        else
01451            memcache_free_entry(cache, pRes);
01452     }
01453     /* Append entries to an existing cache header. */
01454     else if ((mode == MEMCACHE_ACCESS_APPEND) ||
01455             (mode == MEMCACHE_ACCESS_APPEND_LAST)) {
01456 
01457        LDAPMessage *pMsg = (LDAPMessage*)pData2;
01458        LDAPMessage *pCopy = NULL;
01459        ldapmemcacheRes *pRes = NULL;
01460 
01461        nRes = htable_get(cache->ldmemc_resTmp, pData1, (void**)&pRes);
01462        if (nRes != LDAP_SUCCESS)
01463            return nRes;
01464 
01465        nRes = memcache_dup_message(pMsg, pMsg->lm_msgid, 0, &pCopy, &size);
01466        if (nRes != LDAP_SUCCESS) {
01467            nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
01468            assert(nRes == LDAP_SUCCESS);
01469            memcache_free_from_list(cache, pRes, LIST_TMP);
01470            memcache_free_entry(cache, pRes);
01471            return nRes;
01472        }
01473 
01474        nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
01475                                 MEMCACHE_SIZE_ADD);
01476        if (nRes != LDAP_SUCCESS) {
01477            ldap_msgfree(pCopy);
01478            nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
01479            assert(nRes == LDAP_SUCCESS);
01480            memcache_free_from_list(cache, pRes, LIST_TMP);
01481            memcache_free_entry(cache, pRes);
01482            return nRes;
01483        }
01484 
01485        memcache_add_res_to_list(pRes, pCopy, size);
01486 
01487        if (mode == MEMCACHE_ACCESS_APPEND)
01488            return( LDAP_SUCCESS );
01489 
01490        nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
01491        assert(nRes == LDAP_SUCCESS);
01492        memcache_free_from_list(cache, pRes, LIST_TMP);
01493        (pRes->ldmemcr_req_id).ldmemcrid_ld = NULL;
01494        (pRes->ldmemcr_req_id).ldmemcrid_msgid = -1;
01495        pRes->ldmemcr_timestamp = (unsigned long)time(NULL);
01496 
01497        if ((nRes = htable_put(cache->ldmemc_resLookup, 
01498                               (void*)&(pRes->ldmemcr_crc_key),
01499                                (void*)pRes)) == LDAP_SUCCESS) {
01500            memcache_add_to_list(cache, pRes, LIST_TTL);
01501            memcache_add_to_list(cache, pRes, LIST_LRU);
01502        } else {
01503            memcache_free_entry(cache, pRes);
01504        }
01505     }
01506     /* Search for cached entries for a particular search. */
01507     else if (mode == MEMCACHE_ACCESS_FIND) {
01508 
01509        ldapmemcacheRes **ppRes = (ldapmemcacheRes**)pData2;
01510 
01511        nRes = htable_get(cache->ldmemc_resLookup, pData1, (void**)ppRes);
01512        if (nRes != LDAP_SUCCESS)
01513            return nRes;
01514 
01515        if (!memcache_expired(cache, *ppRes, (unsigned long)time(0))) {
01516            memcache_free_from_list(cache, *ppRes, LIST_LRU);
01517            memcache_add_to_list(cache, *ppRes, LIST_LRU);
01518            return( LDAP_SUCCESS );
01519        }
01520 
01521        nRes = htable_remove(cache->ldmemc_resLookup, pData1, NULL);
01522        assert(nRes == LDAP_SUCCESS);
01523        memcache_free_from_list(cache, *ppRes, LIST_TTL);
01524        memcache_free_from_list(cache, *ppRes, LIST_LRU);
01525        memcache_free_entry(cache, *ppRes);
01526        nRes = LDAP_NO_SUCH_OBJECT;
01527        *ppRes = NULL;
01528     }
01529     /* Remove cached entries in the temporary cache. */
01530     else if (mode == MEMCACHE_ACCESS_DELETE) {
01531 
01532        ldapmemcacheRes *pCurRes = NULL;
01533 
01534        if ((nRes = htable_remove(cache->ldmemc_resTmp, pData1,
01535                                  (void**)&pCurRes)) == LDAP_SUCCESS) {
01536            memcache_free_from_list(cache, pCurRes, LIST_TMP);
01537            memcache_free_entry(cache, pCurRes);
01538        }
01539     }
01540     /* Wipe out the temporary cache. */
01541     else if (mode == MEMCACHE_ACCESS_DELETE_ALL) {
01542 
01543        nRes = htable_removeall(cache->ldmemc_resTmp, (void*)cache);
01544     }
01545     /* Remove expired entries from primary cache. */
01546     else if (mode == MEMCACHE_ACCESS_UPDATE) {
01547 
01548        ldapmemcacheRes *pCurRes = cache->ldmemc_resTail[LIST_TTL];
01549        unsigned long curTime = (unsigned long)time(NULL);
01550 
01551        for (; pCurRes; pCurRes = cache->ldmemc_resTail[LIST_TTL]) {
01552 
01553            if (!memcache_expired(cache, pCurRes, curTime))
01554               break;
01555 
01556            nRes = htable_remove(cache->ldmemc_resLookup, 
01557                         (void*)&(pCurRes->ldmemcr_crc_key), NULL);
01558            assert(nRes == LDAP_SUCCESS);
01559            memcache_free_from_list(cache, pCurRes, LIST_TTL);
01560            memcache_free_from_list(cache, pCurRes, LIST_LRU);
01561            memcache_free_entry(cache, pCurRes);
01562        }
01563     }
01564     /* Wipe out the primary cache. */
01565     else if (mode == MEMCACHE_ACCESS_FLUSH_ALL) {
01566 
01567        ldapmemcacheRes *pCurRes = cache->ldmemc_resHead[LIST_TTL];
01568 
01569        nRes = htable_removeall(cache->ldmemc_resLookup, (void*)cache);
01570 
01571        for (; pCurRes; pCurRes = cache->ldmemc_resHead[LIST_TTL]) {
01572            memcache_free_from_list(cache, pCurRes, LIST_LRU);
01573            cache->ldmemc_resHead[LIST_TTL] = 
01574                     cache->ldmemc_resHead[LIST_TTL]->ldmemcr_next[LIST_TTL];
01575            memcache_free_entry(cache, pCurRes);
01576        }
01577        cache->ldmemc_resTail[LIST_TTL] = NULL;
01578     }
01579     /* Remove cached entries in both primary and temporary cache. */
01580     else if (mode == MEMCACHE_ACCESS_FLUSH) {
01581 
01582        int i, list_id, bDone;
01583        int scope = (int)pData2;
01584        char *dn = (char*)pData1;
01585        char *dnTmp;
01586        BerElement ber;
01587        LDAPMessage *pMsg;
01588        ldapmemcacheRes *pRes;
01589 
01590        if (cache->ldmemc_basedns) {
01591            for (i = 0; cache->ldmemc_basedns[i]; i++) {
01592               if ((memcache_compare_dn(cache->ldmemc_basedns[i], dn, 
01593                          LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) ||
01594                   (memcache_compare_dn(dn, cache->ldmemc_basedns[i], 
01595                          LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE))
01596                   break;
01597            }
01598            if (cache->ldmemc_basedns[i] == NULL)
01599               return( LDAP_SUCCESS );
01600        }
01601 
01602        for (i = 0; i < 2; i++) {
01603 
01604            list_id = (i == 0 ? LIST_TTL : LIST_TMP);
01605 
01606            for (pRes = cache->ldmemc_resHead[list_id]; pRes != NULL; 
01607                pRes = pRes->ldmemcr_next[list_id]) {
01608 
01609               if ((memcache_compare_dn(pRes->ldmemcr_basedn, dn, 
01610                              LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE) &&
01611                   (memcache_compare_dn(dn, pRes->ldmemcr_basedn, 
01612                              LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE))
01613                   continue;
01614 
01615               for (pMsg = pRes->ldmemcr_resHead, bDone = 0; 
01616                    !bDone && pMsg; pMsg = pMsg->lm_chain) {
01617 
01618                   if (!NSLDAPI_IS_SEARCH_ENTRY( pMsg->lm_msgtype ))
01619                      continue;
01620 
01621                   ber = *(pMsg->lm_ber);
01622                   if (ber_scanf(&ber, "{a", &dnTmp) != LBER_ERROR) {
01623                      bDone = (memcache_compare_dn(dnTmp, dn, scope) == 
01624                                                      LDAP_COMPARE_TRUE);
01625                      ldap_memfree(dnTmp);
01626                   }
01627               }
01628 
01629               if (!bDone)
01630                   continue;
01631 
01632               if (list_id == LIST_TTL) {
01633                   nRes = htable_remove(cache->ldmemc_resLookup, 
01634                              (void*)&(pRes->ldmemcr_crc_key), NULL);
01635                   assert(nRes == LDAP_SUCCESS);
01636                   memcache_free_from_list(cache, pRes, LIST_TTL);
01637                   memcache_free_from_list(cache, pRes, LIST_LRU);
01638               } else {
01639                   nRes = htable_remove(cache->ldmemc_resTmp, 
01640                               (void*)&(pRes->ldmemcr_req_id), NULL);
01641                   assert(nRes == LDAP_SUCCESS);
01642                   memcache_free_from_list(cache, pRes, LIST_TMP);
01643               }
01644               memcache_free_entry(cache, pRes);
01645            }
01646        }
01647     }
01648     /* Flush least recently used entries from cache */
01649     else if (mode == MEMCACHE_ACCESS_FLUSH_LRU) {
01650 
01651        ldapmemcacheRes *pRes = cache->ldmemc_resTail[LIST_LRU];
01652 
01653        if (pRes == NULL)
01654            return LDAP_NO_SUCH_OBJECT;
01655 
01656        LDAPDebug( LDAP_DEBUG_TRACE,
01657               "memcache_access FLUSH_LRU: removing key 0x%8.8lx\n",
01658               pRes->ldmemcr_crc_key, 0, 0 );
01659        nRes = htable_remove(cache->ldmemc_resLookup,
01660                      (void*)&(pRes->ldmemcr_crc_key), NULL);
01661        assert(nRes == LDAP_SUCCESS);
01662        memcache_free_from_list(cache, pRes, LIST_TTL);
01663        memcache_free_from_list(cache, pRes, LIST_LRU);
01664        memcache_free_entry(cache, pRes);
01665     }
01666     /* Unknown command */
01667     else {
01668        nRes = LDAP_PARAM_ERROR;
01669     }
01670 
01671     return nRes;
01672 }
01673 
01674 
01675 #ifdef LDAP_DEBUG
01676 static void
01677 memcache_report_statistics( LDAPMemCache *cache )
01678 {
01679     unsigned long    hitrate;
01680 
01681     if ( cache->ldmemc_stats.ldmemcstat_tries == 0 ) {
01682        hitrate = 0;
01683     } else {
01684        hitrate = ( 100L * cache->ldmemc_stats.ldmemcstat_hits ) /
01685            cache->ldmemc_stats.ldmemcstat_tries;
01686     }
01687     LDAPDebug( LDAP_DEBUG_STATS, "memcache 0x%x:\n", cache, 0, 0 );
01688     LDAPDebug( LDAP_DEBUG_STATS, "    tries: %ld  hits: %ld  hitrate: %ld%%\n",
01689            cache->ldmemc_stats.ldmemcstat_tries,
01690            cache->ldmemc_stats.ldmemcstat_hits, hitrate );
01691     if ( cache->ldmemc_size <= 0 ) {      /* no size limit */
01692        LDAPDebug( LDAP_DEBUG_STATS, "    memory bytes used: %ld\n",
01693               cache->ldmemc_size_used, 0, 0 );
01694     } else {
01695        LDAPDebug( LDAP_DEBUG_STATS, "    memory bytes used: %ld free: %ld\n",
01696               cache->ldmemc_size_used,
01697               cache->ldmemc_size - cache->ldmemc_size_used, 0 );
01698     }
01699 }
01700 #endif /* LDAP_DEBUG */
01701 
01702 /************************ Hash Table Functions *****************************/
01703 
01704 /* Calculates size (# of entries) of hash table given the size limit for
01705    the cache. */
01706 static int
01707 htable_calculate_size(int sizelimit)
01708 {
01709     int i, j;
01710     int size = (int)(((double)sizelimit / 
01711                        (double)(sizeof(BerElement) + EXTRA_SIZE)) / 1.5);
01712 
01713     /* Get a prime # */
01714     size = (size & 0x1 ? size : size + 1);
01715     for (i = 3, j = size / 2; i < j; i++) {
01716        if ((size % i) == 0) {
01717            size += 2;
01718            i = 3;
01719            j = size / 2;
01720        }
01721     }
01722 
01723     return size;
01724 }
01725 
01726 /* Returns the size in bytes of the given hash table. */
01727 static int
01728 htable_sizeinbytes(HashTable *pTable)
01729 {
01730     if (!pTable)
01731        return 0;
01732 
01733     return (pTable->size * sizeof(HashTableNode));
01734 }
01735 
01736 /* Inserts an item into the hash table. */
01737 static int
01738 htable_put(HashTable *pTable, void *key, void *pData)
01739 {
01740     int index = pTable->hashfunc(pTable->size, key);
01741 
01742     if (index >= 0 && index < pTable->size)
01743        return pTable->putdata(&(pTable->table[index].pData), key, pData);
01744 
01745     return( LDAP_OPERATIONS_ERROR );
01746 }
01747 
01748 /* Retrieves an item from the hash table. */
01749 static int
01750 htable_get(HashTable *pTable, void *key, void **ppData)
01751 {
01752     int index = pTable->hashfunc(pTable->size, key);
01753 
01754     *ppData = NULL;
01755 
01756     if (index >= 0 && index < pTable->size)
01757        return pTable->getdata(pTable->table[index].pData, key, ppData);
01758 
01759     return( LDAP_OPERATIONS_ERROR );
01760 }
01761 
01762 /* Performs a miscellaneous operation on a hash table entry. */
01763 static int
01764 htable_misc(HashTable *pTable, void *key, void *pData)
01765 {
01766     if (pTable->miscfunc) {
01767        int index = pTable->hashfunc(pTable->size, key);
01768        if (index >= 0 && index < pTable->size)
01769            return pTable->miscfunc(&(pTable->table[index].pData), key, pData);
01770     }
01771 
01772     return( LDAP_OPERATIONS_ERROR );
01773 }
01774 
01775 /* Removes an item from the hash table. */
01776 static int
01777 htable_remove(HashTable *pTable, void *key, void **ppData)
01778 {
01779     int index = pTable->hashfunc(pTable->size, key);
01780 
01781     if (ppData)
01782        *ppData = NULL;
01783 
01784     if (index >= 0 && index < pTable->size)
01785        return pTable->removedata(&(pTable->table[index].pData), key, ppData);
01786 
01787     return( LDAP_OPERATIONS_ERROR );
01788 }
01789 
01790 /* Removes everything in the hash table. */
01791 static int
01792 htable_removeall(HashTable *pTable, void *pData)
01793 {
01794     int i;
01795 
01796     for (i = 0; i < pTable->size; i++)
01797        pTable->clrtablenode(&(pTable->table[i].pData), pData);
01798 
01799     return( LDAP_SUCCESS );
01800 }
01801 
01802 /* Creates a new hash table. */
01803 static int
01804 htable_create(int size_limit, HashFuncPtr hashf,
01805                       PutDataPtr putDataf, GetDataPtr getDataf,
01806                       RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef,
01807                       MiscFuncPtr miscOpf, HashTable **ppTable)
01808 {
01809     size_limit = htable_calculate_size(size_limit);
01810 
01811     if ((*ppTable = (HashTable*)NSLDAPI_CALLOC(1, sizeof(HashTable))) == NULL)
01812        return( LDAP_NO_MEMORY );
01813 
01814     (*ppTable)->table = (HashTableNode*)NSLDAPI_CALLOC(size_limit, 
01815                                               sizeof(HashTableNode));
01816     if ((*ppTable)->table == NULL) {
01817        NSLDAPI_FREE(*ppTable);
01818        *ppTable = NULL;
01819        return( LDAP_NO_MEMORY );
01820     }
01821 
01822     (*ppTable)->size = size_limit;
01823     (*ppTable)->hashfunc = hashf;
01824     (*ppTable)->putdata = putDataf;
01825     (*ppTable)->getdata = getDataf;
01826     (*ppTable)->miscfunc = miscOpf;
01827     (*ppTable)->removedata = removeDataf;
01828     (*ppTable)->clrtablenode = clrNodef;
01829 
01830     return( LDAP_SUCCESS );
01831 }
01832 
01833 /* Destroys a hash table. */
01834 static int
01835 htable_free(HashTable *pTable)
01836 {
01837     NSLDAPI_FREE(pTable->table);
01838     NSLDAPI_FREE(pTable);
01839     return( LDAP_SUCCESS );
01840 }
01841 
01842 /**************** Hash table callbacks for temporary cache ****************/
01843 
01844 /* Hash function */
01845 static int
01846 msgid_hashf(int table_size, void *key)
01847 {
01848     unsigned code = (unsigned)((ldapmemcacheReqId*)key)->ldmemcrid_ld;
01849     return (((code << 20) + (code >> 12)) % table_size);
01850 }
01851 
01852 /* Called by hash table to insert an item. */
01853 static int
01854 msgid_putdata(void **ppTableData, void *key, void *pData)
01855 {
01856     ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
01857     ldapmemcacheRes *pRes = (ldapmemcacheRes*)pData;
01858     ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
01859     ldapmemcacheRes *pCurRes = *ppHead;
01860     ldapmemcacheRes *pPrev = NULL;
01861 
01862     for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) {
01863        if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
01864            break;
01865        pPrev = pCurRes;
01866     }
01867 
01868     if (pCurRes) {
01869        for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) { 
01870            if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid == 
01871                                              pReqId->ldmemcrid_msgid)
01872               return( LDAP_ALREADY_EXISTS );
01873            pPrev = pCurRes;
01874        }
01875        pPrev->ldmemcr_next[LIST_TTL] = pRes;
01876        pRes->ldmemcr_prev[LIST_TTL] = pPrev;
01877        pRes->ldmemcr_next[LIST_TTL] = NULL;
01878     } else {
01879        if (pPrev)
01880            pPrev->ldmemcr_htable_next = pRes;
01881        else
01882            *ppHead = pRes;
01883        pRes->ldmemcr_htable_next = NULL;
01884     }
01885 
01886     return( LDAP_SUCCESS );
01887 }
01888 
01889 /* Called by hash table to retrieve an item. */
01890 static int
01891 msgid_getdata(void *pTableData, void *key, void **ppData)
01892 {
01893     ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
01894     ldapmemcacheRes *pCurRes = (ldapmemcacheRes*)pTableData;
01895 
01896     *ppData = NULL;
01897     
01898     for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) {
01899        if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
01900            break;
01901     }
01902 
01903     if (!pCurRes)
01904        return( LDAP_NO_SUCH_OBJECT );
01905 
01906     for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) { 
01907        if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid == 
01908                                          pReqId->ldmemcrid_msgid) {
01909            *ppData = (void*)pCurRes;
01910            return( LDAP_SUCCESS );
01911        }
01912     }
01913 
01914     return( LDAP_NO_SUCH_OBJECT );
01915 }
01916 
01917 /* Called by hash table to remove an item. */
01918 static int
01919 msgid_removedata(void **ppTableData, void *key, void **ppData)
01920 {
01921     ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData);
01922     ldapmemcacheRes *pCurRes = NULL;
01923     ldapmemcacheRes *pPrev = NULL;
01924     ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
01925 
01926     if (ppData)
01927        *ppData = NULL;
01928 
01929     for (; pHead; pHead = pHead->ldmemcr_htable_next) {
01930        if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
01931            break;
01932        pPrev = pHead;
01933     }
01934 
01935     if (!pHead)
01936        return( LDAP_NO_SUCH_OBJECT );
01937 
01938     for (pCurRes = pHead; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) { 
01939        if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid == 
01940                                                pReqId->ldmemcrid_msgid)
01941            break;
01942     }
01943 
01944     if (!pCurRes)
01945        return( LDAP_NO_SUCH_OBJECT );
01946 
01947     if (ppData) {
01948        pCurRes->ldmemcr_next[LIST_TTL] = NULL;
01949        pCurRes->ldmemcr_prev[LIST_TTL] = NULL;
01950        pCurRes->ldmemcr_htable_next = NULL;
01951        *ppData = (void*)pCurRes;
01952     }
01953 
01954     if (pCurRes != pHead) {
01955        if (pCurRes->ldmemcr_prev[LIST_TTL])
01956            pCurRes->ldmemcr_prev[LIST_TTL]->ldmemcr_next[LIST_TTL] = 
01957                                             pCurRes->ldmemcr_next[LIST_TTL];
01958        if (pCurRes->ldmemcr_next[LIST_TTL])
01959            pCurRes->ldmemcr_next[LIST_TTL]->ldmemcr_prev[LIST_TTL] = 
01960                                             pCurRes->ldmemcr_prev[LIST_TTL];
01961        return( LDAP_SUCCESS );
01962     }
01963 
01964     if (pPrev) {
01965        if (pHead->ldmemcr_next[LIST_TTL]) {
01966            pPrev->ldmemcr_htable_next = pHead->ldmemcr_next[LIST_TTL];
01967            pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next = 
01968                                         pHead->ldmemcr_htable_next;
01969        } else {
01970            pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next;
01971        }
01972     } else {
01973        if (pHead->ldmemcr_next[LIST_TTL]) {
01974            *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_next[LIST_TTL];
01975            pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next = 
01976                                         pHead->ldmemcr_htable_next;
01977        } else {
01978            *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next;
01979        }
01980     }
01981     
01982     return( LDAP_SUCCESS );
01983 }
01984 
01985 /* Called by hash table to remove all cached entries associated to searches
01986    being performed using the given ldap handle. */
01987 static int
01988 msgid_clear_ld_items(void **ppTableData, void *key, void *pData)
01989 {
01990     LDAPMemCache *cache = (LDAPMemCache*)pData;
01991     ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData);
01992     ldapmemcacheRes *pPrev = NULL;
01993     ldapmemcacheRes *pCurRes = NULL;
01994     ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
01995     
01996     for (; pHead; pHead = pHead->ldmemcr_htable_next) {
01997        if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
01998            break;
01999        pPrev = pHead;
02000     }
02001 
02002     if (!pHead)
02003        return( LDAP_NO_SUCH_OBJECT );
02004 
02005     if (pPrev)
02006        pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next;
02007     else
02008        *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next;
02009 
02010     for (pCurRes = pHead; pHead; pCurRes = pHead) {
02011        pHead = pHead->ldmemcr_next[LIST_TTL];
02012        memcache_free_from_list(cache, pCurRes, LIST_TMP);
02013        memcache_free_entry(cache, pCurRes);
02014     }
02015 
02016     return( LDAP_SUCCESS );
02017 }
02018 
02019 /* Called by hash table for removing all items in the table. */
02020 static void
02021 msgid_clearnode(void **ppTableData, void *pData)
02022 {
02023     LDAPMemCache *cache = (LDAPMemCache*)pData;
02024     ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
02025     ldapmemcacheRes *pSubHead = *ppHead;
02026     ldapmemcacheRes *pCurRes = NULL;
02027 
02028     for (; *ppHead; pSubHead = *ppHead) {
02029        ppHead = &((*ppHead)->ldmemcr_htable_next);
02030        for (pCurRes = pSubHead; pSubHead; pCurRes = pSubHead) {
02031            pSubHead = pSubHead->ldmemcr_next[LIST_TTL];
02032            memcache_free_from_list(cache, pCurRes, LIST_TMP);
02033            memcache_free_entry(cache, pCurRes);
02034        }
02035     }
02036 }
02037 
02038 /********************* Hash table for primary cache ************************/
02039 
02040 /* Hash function */
02041 static int
02042 attrkey_hashf(int table_size, void *key)
02043 {
02044     return ((*((unsigned long*)key)) % table_size);
02045 }
02046 
02047 /* Called by hash table to insert an item. */
02048 static int
02049 attrkey_putdata(void **ppTableData, void *key, void *pData)
02050 {
02051     unsigned long attrkey = *((unsigned long*)key);
02052     ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
02053     ldapmemcacheRes *pRes = *ppHead;
02054 
02055     for (; pRes; pRes = pRes->ldmemcr_htable_next) {
02056        if (pRes->ldmemcr_crc_key == attrkey)
02057            return( LDAP_ALREADY_EXISTS );
02058     }
02059 
02060     pRes = (ldapmemcacheRes*)pData;
02061     pRes->ldmemcr_htable_next = *ppHead;
02062     *ppHead = pRes;
02063 
02064     return( LDAP_SUCCESS );
02065 }
02066 
02067 /* Called by hash table to retrieve an item. */
02068 static int
02069 attrkey_getdata(void *pTableData, void *key, void **ppData)
02070 {
02071     unsigned long attrkey = *((unsigned long*)key);
02072     ldapmemcacheRes *pRes = (ldapmemcacheRes*)pTableData;
02073     
02074     for (; pRes; pRes = pRes->ldmemcr_htable_next) {
02075        if (pRes->ldmemcr_crc_key == attrkey) {
02076            *ppData = (void*)pRes;
02077            return( LDAP_SUCCESS );
02078        }
02079     }
02080 
02081     *ppData = NULL;
02082 
02083     return( LDAP_NO_SUCH_OBJECT );
02084 }
02085 
02086 /* Called by hash table to remove an item. */
02087 static int
02088 attrkey_removedata(void **ppTableData, void *key, void **ppData)
02089 {
02090     unsigned long attrkey = *((unsigned long*)key);
02091     ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
02092     ldapmemcacheRes *pRes = *ppHead;
02093     ldapmemcacheRes *pPrev = NULL;
02094     
02095     for (; pRes; pRes = pRes->ldmemcr_htable_next) {
02096        if (pRes->ldmemcr_crc_key == attrkey) {
02097            if (ppData)
02098               *ppData = (void*)pRes;
02099            if (pPrev)
02100               pPrev->ldmemcr_htable_next = pRes->ldmemcr_htable_next;
02101            else
02102               *ppHead = pRes->ldmemcr_htable_next;
02103            pRes->ldmemcr_htable_next = NULL;
02104            return( LDAP_SUCCESS );
02105        }
02106        pPrev = pRes;
02107     }
02108 
02109     if (ppData)
02110        *ppData = NULL;
02111 
02112     return( LDAP_NO_SUCH_OBJECT );
02113 }
02114 
02115 /* Called by hash table for removing all items in the table. */
02116 static void
02117 attrkey_clearnode(void **ppTableData, void *pData)
02118 {
02119     ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
02120     ldapmemcacheRes *pRes = *ppHead;
02121 
02122     (void)pData;
02123 
02124     for (; *ppHead; pRes = *ppHead) {
02125        ppHead = &((*ppHead)->ldmemcr_htable_next);
02126        pRes->ldmemcr_htable_next = NULL;
02127     }
02128 }
02129 
02130 /***************************** CRC algorithm ********************************/
02131 
02132 /* From http://www.faqs.org/faqs/compression-faq/part1/section-25.html */
02133 
02134 /*
02135  * Build auxiliary table for parallel byte-at-a-time CRC-32.
02136  */
02137 #define NSLDAPI_CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */
02138 
02139 static unsigned long crc32_table[256] = { 
02140     0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b, 
02141     0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61, 
02142     0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, 0x4c11db70, 0x48d0c6c7, 
02143     0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75, 
02144     0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 
02145     0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039, 
02146     0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58, 0xbaea46ef, 
02147     0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d, 
02148     0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb, 
02149     0xceb42022, 0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 
02150     0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0, 
02151     0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072, 
02152     0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4, 
02153     0x0808d07d, 0x0cc9cdca, 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde, 
02154     0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 
02155     0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba, 
02156     0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc, 
02157     0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6, 
02158     0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050, 
02159     0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 
02160     0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34, 
02161     0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637, 
02162     0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, 0x4f040d56, 0x4bc510e1, 
02163     0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53, 
02164     0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 
02165     0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff, 
02166     0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e, 0xf5ee4bb9, 
02167     0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b, 
02168     0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 
02169     0xcda1f604, 0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 
02170     0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71, 
02171     0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3, 
02172     0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2, 
02173     0x470cdd2b, 0x43cdc09c, 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8, 
02174     0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 
02175     0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec, 
02176     0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a, 
02177     0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0, 
02178     0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676, 
02179     0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 
02180     0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662, 
02181     0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668, 
02182     0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4 };
02183 
02184 /* Initialized first time "crc32()" is called. If you prefer, you can
02185  * statically initialize it at compile time. [Another exercise.]
02186  */
02187 
02188 static unsigned long
02189 crc32_convert(char *buf, int len)
02190 {
02191     char *p;
02192 #ifdef OSF1V4D
02193     unsigned int crc;
02194 #else
02195     unsigned long crc;          /* FIXME: this is not 32-bits on all platforms! */
02196 #endif /* OSF1V4D */
02197 
02198     crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
02199     for (p = buf; len > 0; ++p, --len)
02200        crc = ((crc << 8) ^ crc32_table[(crc >> 24) ^ *p]) & 0xffffffff;
02201 
02202     return (unsigned long) ~crc;    /* transmit complement, per CRC-32 spec */
02203 }