1N/A/*
1N/A * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
1N/A * Use is subject to license terms.
1N/A */
1N/A#pragma ident "%Z%%M% %I% %E% SMI"
1N/A
1N/A/*
1N/A * The contents of this file are subject to the Netscape Public
1N/A * License Version 1.1 (the "License"); you may not use this file
1N/A * except in compliance with the License. You may obtain a copy of
1N/A * the License at http://www.mozilla.org/NPL/
1N/A *
1N/A * Software distributed under the License is distributed on an "AS
1N/A * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
1N/A * implied. See the License for the specific language governing
1N/A * rights and limitations under the License.
1N/A *
1N/A * The Original Code is Mozilla Communicator client code, released
1N/A * March 31, 1998.
1N/A *
1N/A * The Initial Developer of the Original Code is Netscape
1N/A * Communications Corporation. Portions created by Netscape are
1N/A * Copyright (C) 1998-1999 Netscape Communications Corporation. All
1N/A * Rights Reserved.
1N/A *
1N/A * Contributor(s):
1N/A */
1N/A/*
1N/A *
1N/A * memcache.c - routines that implement an in-memory cache.
1N/A *
1N/A * To Do: 1) ber_dup_ext().
1N/A * 2) referrals and reference?
1N/A */
1N/A
1N/A#include <assert.h>
1N/A#include "ldap-int.h"
1N/A
1N/A/*
1N/A * Extra size allocated to BerElement.
1N/A * XXXmcs: must match EXBUFSIZ in liblber/io.c?
1N/A */
1N/A#define EXTRA_SIZE 1024
1N/A
1N/A/* Mode constants for function memcache_access() */
1N/A#define MEMCACHE_ACCESS_ADD 0
1N/A#define MEMCACHE_ACCESS_APPEND 1
1N/A#define MEMCACHE_ACCESS_APPEND_LAST 2
1N/A#define MEMCACHE_ACCESS_FIND 3
1N/A#define MEMCACHE_ACCESS_DELETE 4
1N/A#define MEMCACHE_ACCESS_DELETE_ALL 5
1N/A#define MEMCACHE_ACCESS_UPDATE 6
1N/A#define MEMCACHE_ACCESS_FLUSH 7
1N/A#define MEMCACHE_ACCESS_FLUSH_ALL 8
1N/A#define MEMCACHE_ACCESS_FLUSH_LRU 9
1N/A
1N/A/* Mode constants for function memcache_adj_size */
1N/A#define MEMCACHE_SIZE_DEDUCT 0
1N/A#define MEMCACHE_SIZE_ADD 1
1N/A
1N/A#define MEMCACHE_SIZE_ENTRIES 1
1N/A#define MEMCACHE_SIZE_NON_ENTRIES 2
1N/A
1N/A/* Size used for calculation if given size of cache is 0 */
1N/A#define MEMCACHE_DEF_SIZE 131072 /* 128K bytes */
1N/A
1N/A/* Index into different list structure */
1N/A#define LIST_TTL 0
1N/A#define LIST_LRU 1
1N/A#define LIST_TMP 2
1N/A#define LIST_TOTAL 3
1N/A
1N/A
1N/Astatic char *emptyStr = "";
1N/A
1N/A/* Macros to make code more readable */
1N/A#define NSLDAPI_VALID_MEMCACHE_POINTER( cp ) ( (cp) != NULL )
1N/A#define NSLDAPI_STR_NONNULL( s ) ( (s) ? (s) : emptyStr )
1N/A#define NSLDAPI_SAFE_STRLEN( s ) ( (s) ? strlen((s)) + 1 : 1 )
1N/A
1N/A/* Macros dealing with mutex */
1N/A#define LDAP_MEMCACHE_MUTEX_LOCK( c ) \
1N/A if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_lock ) { \
1N/A ((c)->ldmemc_lock_fns).ltf_mutex_lock( (c)->ldmemc_lock ); \
1N/A }
1N/A
1N/A#define LDAP_MEMCACHE_MUTEX_UNLOCK( c ) \
1N/A if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_unlock ) { \
1N/A ((c)->ldmemc_lock_fns).ltf_mutex_unlock( (c)->ldmemc_lock ); \
1N/A }
1N/A
1N/A#define LDAP_MEMCACHE_MUTEX_ALLOC( c ) \
1N/A ((c) && ((c)->ldmemc_lock_fns).ltf_mutex_alloc ? \
1N/A ((c)->ldmemc_lock_fns).ltf_mutex_alloc() : NULL)
1N/A
1N/A#define LDAP_MEMCACHE_MUTEX_FREE( c ) \
1N/A if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_free ) { \
1N/A ((c)->ldmemc_lock_fns).ltf_mutex_free( (c)->ldmemc_lock ); \
1N/A }
1N/A
1N/A/* Macros used for triming unnecessary spaces in a basedn */
1N/A#define NSLDAPI_IS_SPACE( c ) \
1N/A (((c) == ' ') || ((c) == '\t') || ((c) == '\n'))
1N/A
1N/A#define NSLDAPI_IS_SEPARATER( c ) \
1N/A ((c) == ',')
1N/A
1N/A/* Hash table callback function pointer definition */
1N/Atypedef int (*HashFuncPtr)(int table_size, void *key);
1N/Atypedef int (*PutDataPtr)(void **ppTableData, void *key, void *pData);
1N/Atypedef int (*GetDataPtr)(void *pTableData, void *key, void **ppData);
1N/Atypedef int (*RemoveDataPtr)(void **ppTableData, void *key, void **ppData);
1N/Atypedef int (*MiscFuncPtr)(void **ppTableData, void *key, void *pData);
1N/Atypedef void (*ClrTableNodePtr)(void **ppTableData, void *pData);
1N/A
1N/A/* Structure of a node in a hash table */
1N/Atypedef struct HashTableNode_struct {
1N/A void *pData;
1N/A} HashTableNode;
1N/A
1N/A/* Structure of a hash table */
1N/Atypedef struct HashTable_struct {
1N/A HashTableNode *table;
1N/A int size;
1N/A HashFuncPtr hashfunc;
1N/A PutDataPtr putdata;
1N/A GetDataPtr getdata;
1N/A MiscFuncPtr miscfunc;
1N/A RemoveDataPtr removedata;
1N/A ClrTableNodePtr clrtablenode;
1N/A} HashTable;
1N/A
1N/A/* Structure uniquely identifies a search request */
1N/Atypedef struct ldapmemcacheReqId_struct {
1N/A LDAP *ldmemcrid_ld;
1N/A int ldmemcrid_msgid;
1N/A} ldapmemcacheReqId;
1N/A
1N/A/* Structure representing a ldap handle associated to memcache */
1N/Atypedef struct ldapmemcacheld_struct {
1N/A LDAP *ldmemcl_ld;
1N/A struct ldapmemcacheld_struct *ldmemcl_next;
1N/A} ldapmemcacheld;
1N/A
1N/A/* Structure representing header of a search result */
1N/Atypedef struct ldapmemcacheRes_struct {
1N/A char *ldmemcr_basedn;
1N/A unsigned long ldmemcr_crc_key;
1N/A unsigned long ldmemcr_resSize;
1N/A unsigned long ldmemcr_timestamp;
1N/A LDAPMessage *ldmemcr_resHead;
1N/A LDAPMessage *ldmemcr_resTail;
1N/A ldapmemcacheReqId ldmemcr_req_id;
1N/A struct ldapmemcacheRes_struct *ldmemcr_next[LIST_TOTAL];
1N/A struct ldapmemcacheRes_struct *ldmemcr_prev[LIST_TOTAL];
1N/A struct ldapmemcacheRes_struct *ldmemcr_htable_next;
1N/A} ldapmemcacheRes;
1N/A
1N/A/* Structure for memcache statistics */
1N/Atypedef struct ldapmemcacheStats_struct {
1N/A unsigned long ldmemcstat_tries;
1N/A unsigned long ldmemcstat_hits;
1N/A} ldapmemcacheStats;
1N/A
1N/A/* Structure of a memcache object */
1N/Astruct ldapmemcache {
1N/A unsigned long ldmemc_ttl;
1N/A unsigned long ldmemc_size;
1N/A unsigned long ldmemc_size_used;
1N/A unsigned long ldmemc_size_entries;
1N/A char **ldmemc_basedns;
1N/A void *ldmemc_lock;
1N/A ldapmemcacheld *ldmemc_lds;
1N/A HashTable *ldmemc_resTmp;
1N/A HashTable *ldmemc_resLookup;
1N/A ldapmemcacheRes *ldmemc_resHead[LIST_TOTAL];
1N/A ldapmemcacheRes *ldmemc_resTail[LIST_TOTAL];
1N/A struct ldap_thread_fns ldmemc_lock_fns;
1N/A ldapmemcacheStats ldmemc_stats;
1N/A};
1N/A
1N/A/* Function prototypes */
1N/Astatic int memcache_exist(LDAP *ld);
1N/Astatic int memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg);
1N/Astatic int memcache_compare_dn(const char *main_dn, const char *dn, int scope);
1N/Astatic int memcache_dup_message(LDAPMessage *res, int msgid, int fromcache,
1N/A LDAPMessage **ppResCopy, unsigned long *pSize);
1N/Astatic BerElement* memcache_ber_dup(BerElement* pBer, unsigned long *pSize);
1N/A
1N/Astatic void memcache_trim_basedn_spaces(char *basedn);
1N/Astatic int memcache_validate_basedn(LDAPMemCache *cache, const char *basedn);
1N/Astatic int memcache_get_ctrls_len(LDAPControl **ctrls);
1N/Astatic void memcache_append_ctrls(char *buf, LDAPControl **serverCtrls,
1N/A LDAPControl **clientCtrls);
1N/Astatic int memcache_adj_size(LDAPMemCache *cache, unsigned long size,
1N/A int usageFlags, int bAdd);
1N/Astatic int memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes);
1N/Astatic int memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes,
1N/A unsigned long curTime);
1N/Astatic int memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes,
1N/A int index);
1N/Astatic int memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg,
1N/A unsigned long size);
1N/Astatic int memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes,
1N/A int index);
1N/Astatic int memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes);
1N/Astatic int memcache_add(LDAP *ld, unsigned long key, int msgid,
1N/A const char *basedn);
1N/Astatic int memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes);
1N/Astatic int memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes);
1N/Astatic int memcache_remove(LDAP *ld, int msgid);
1N/A#if 0 /* function not used */
1N/Astatic int memcache_remove_all(LDAP *ld);
1N/A#endif /* 0 */
1N/Astatic int memcache_access(LDAPMemCache *cache, int mode,
1N/A void *pData1, void *pData2, void *pData3);
1N/A#ifdef LDAP_DEBUG
1N/Astatic void memcache_print_list( LDAPMemCache *cache, int index );
1N/Astatic void memcache_report_statistics( LDAPMemCache *cache );
1N/A#endif /* LDAP_DEBUG */
1N/A
1N/Astatic int htable_calculate_size(int sizelimit);
1N/Astatic int htable_sizeinbytes(HashTable *pTable);
1N/Astatic int htable_put(HashTable *pTable, void *key, void *pData);
1N/Astatic int htable_get(HashTable *pTable, void *key, void **ppData);
1N/Astatic int htable_misc(HashTable *pTable, void *key, void *pData);
1N/Astatic int htable_remove(HashTable *pTable, void *key, void **ppData);
1N/Astatic int htable_removeall(HashTable *pTable, void *pData);
1N/Astatic int htable_create(int size_limit, HashFuncPtr hashf,
1N/A PutDataPtr putDataf, GetDataPtr getDataf,
1N/A RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef,
1N/A MiscFuncPtr miscOpf, HashTable **ppTable);
1N/Astatic int htable_free(HashTable *pTable);
1N/A
1N/Astatic int msgid_hashf(int table_size, void *key);
1N/Astatic int msgid_putdata(void **ppTableData, void *key, void *pData);
1N/Astatic int msgid_getdata(void *pTableData, void *key, void **ppData);
1N/Astatic int msgid_removedata(void **ppTableData, void *key, void **ppData);
1N/Astatic int msgid_clear_ld_items(void **ppTableData, void *key, void *pData);
1N/Astatic void msgid_clearnode(void **ppTableData, void *pData);
1N/A
1N/Astatic int attrkey_hashf(int table_size, void *key);
1N/Astatic int attrkey_putdata(void **ppTableData, void *key, void *pData);
1N/Astatic int attrkey_getdata(void *pTableData, void *key, void **ppData);
1N/Astatic int attrkey_removedata(void **ppTableData, void *key, void **ppData);
1N/Astatic void attrkey_clearnode(void **ppTableData, void *pData);
1N/A
1N/Astatic unsigned long crc32_convert(char *buf, int len);
1N/A
1N/A/* Create a memcache object. */
1N/Aint
1N/ALDAP_CALL
1N/Aldap_memcache_init( unsigned long ttl, unsigned long size,
1N/A char **baseDNs, struct ldap_thread_fns *thread_fns,
1N/A LDAPMemCache **cachep )
1N/A{
1N/A unsigned long total_size = 0;
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init\n", 0, 0, 0 );
1N/A
1N/A if ( cachep == NULL ) {
1N/A return( LDAP_PARAM_ERROR );
1N/A }
1N/A
1N/A if ((*cachep = (LDAPMemCache*)NSLDAPI_CALLOC(1,
1N/A sizeof(LDAPMemCache))) == NULL) {
1N/A return ( LDAP_NO_MEMORY );
1N/A }
1N/A
1N/A total_size += sizeof(LDAPMemCache);
1N/A
1N/A (*cachep)->ldmemc_ttl = ttl;
1N/A (*cachep)->ldmemc_size = size;
1N/A (*cachep)->ldmemc_lds = NULL;
1N/A
1N/A /* Non-zero default size needed for calculating size of hash tables */
1N/A size = (size ? size : MEMCACHE_DEF_SIZE);
1N/A
1N/A if (thread_fns) {
1N/A memcpy(&((*cachep)->ldmemc_lock_fns), thread_fns,
1N/A sizeof(struct ldap_thread_fns));
1N/A } else {
1N/A memset(&((*cachep)->ldmemc_lock_fns), 0,
1N/A sizeof(struct ldap_thread_fns));
1N/A }
1N/A
1N/A (*cachep)->ldmemc_lock = LDAP_MEMCACHE_MUTEX_ALLOC( *cachep );
1N/A
1N/A /* Cache basedns */
1N/A if (baseDNs != NULL) {
1N/A
1N/A int i;
1N/A
1N/A for (i = 0; baseDNs[i]; i++) {
1N/A ;
1N/A }
1N/A
1N/A (*cachep)->ldmemc_basedns = (char**)NSLDAPI_CALLOC(i + 1,
1N/A sizeof(char*));
1N/A
1N/A if ((*cachep)->ldmemc_basedns == NULL) {
1N/A ldap_memcache_destroy(*cachep);
1N/A *cachep = NULL;
1N/A return ( LDAP_NO_MEMORY );
1N/A }
1N/A
1N/A total_size += (i + 1) * sizeof(char*);
1N/A
1N/A for (i = 0; baseDNs[i]; i++) {
1N/A (*cachep)->ldmemc_basedns[i] = nsldapi_strdup(baseDNs[i]);
1N/A if ((*cachep)->ldmemc_basedns[i] == NULL)
1N/A return ( LDAP_NO_MEMORY );
1N/A total_size += strlen(baseDNs[i]) + 1;
1N/A }
1N/A
1N/A (*cachep)->ldmemc_basedns[i] = NULL;
1N/A }
1N/A
1N/A /* Create hash table for temporary cache */
1N/A if (htable_create(size, msgid_hashf, msgid_putdata, msgid_getdata,
1N/A msgid_removedata, msgid_clearnode, msgid_clear_ld_items,
1N/A &((*cachep)->ldmemc_resTmp)) != LDAP_SUCCESS) {
1N/A ldap_memcache_destroy(*cachep);
1N/A *cachep = NULL;
1N/A return( LDAP_NO_MEMORY );
1N/A }
1N/A
1N/A total_size += htable_sizeinbytes((*cachep)->ldmemc_resTmp);
1N/A
1N/A /* Create hash table for primary cache */
1N/A if (htable_create(size, attrkey_hashf, attrkey_putdata,
1N/A attrkey_getdata, attrkey_removedata, attrkey_clearnode,
1N/A NULL, &((*cachep)->ldmemc_resLookup)) != LDAP_SUCCESS) {
1N/A ldap_memcache_destroy(*cachep);
1N/A *cachep = NULL;
1N/A return( LDAP_NO_MEMORY );
1N/A }
1N/A
1N/A total_size += htable_sizeinbytes((*cachep)->ldmemc_resLookup);
1N/A
1N/A /* See if there is enough room so far */
1N/A if (memcache_adj_size(*cachep, total_size, MEMCACHE_SIZE_NON_ENTRIES,
1N/A MEMCACHE_SIZE_ADD) != LDAP_SUCCESS) {
1N/A ldap_memcache_destroy(*cachep);
1N/A *cachep = NULL;
1N/A return( LDAP_SIZELIMIT_EXCEEDED );
1N/A }
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init new cache 0x%x\n",
1N/A *cachep, 0, 0 );
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Associates a ldap handle to a memcache object. */
1N/Aint
1N/ALDAP_CALL
1N/Aldap_memcache_set( LDAP *ld, LDAPMemCache *cache )
1N/A{
1N/A int nRes = LDAP_SUCCESS;
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_set\n", 0, 0, 0 );
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) )
1N/A return( LDAP_PARAM_ERROR );
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A if (ld->ld_memcache != cache) {
1N/A
1N/A LDAPMemCache *c = ld->ld_memcache;
1N/A ldapmemcacheld *pCur = NULL;
1N/A ldapmemcacheld *pPrev = NULL;
1N/A
1N/A /* First dissociate handle from old cache */
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( c );
1N/A
1N/A pCur = (c ? c->ldmemc_lds : NULL);
1N/A for (; pCur; pCur = pCur->ldmemcl_next) {
1N/A if (pCur->ldmemcl_ld == ld)
1N/A break;
1N/A pPrev = pCur;
1N/A }
1N/A
1N/A if (pCur) {
1N/A
1N/A ldapmemcacheReqId reqid;
1N/A
1N/A reqid.ldmemcrid_ld = ld;
1N/A reqid.ldmemcrid_msgid = -1;
1N/A htable_misc(c->ldmemc_resTmp, (void*)&reqid, (void*)c);
1N/A
1N/A if (pPrev)
1N/A pPrev->ldmemcl_next = pCur->ldmemcl_next;
1N/A else
1N/A c->ldmemc_lds = pCur->ldmemcl_next;
1N/A NSLDAPI_FREE(pCur);
1N/A pCur = NULL;
1N/A
1N/A memcache_adj_size(c, sizeof(ldapmemcacheld),
1N/A MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT);
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( c );
1N/A
1N/A ld->ld_memcache = NULL;
1N/A
1N/A /* Exit if no new cache is specified */
1N/A if (cache == NULL) {
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A
1N/A /* Then associate handle with new cache */
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( cache );
1N/A
1N/A if ((nRes = memcache_adj_size(cache, sizeof(ldapmemcacheld),
1N/A MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_ADD)) != LDAP_SUCCESS) {
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A return nRes;
1N/A }
1N/A
1N/A pCur = (ldapmemcacheld*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheld));
1N/A if (pCur == NULL) {
1N/A memcache_adj_size(cache, sizeof(ldapmemcacheld),
1N/A MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT);
1N/A nRes = LDAP_NO_MEMORY;
1N/A } else {
1N/A pCur->ldmemcl_ld = ld;
1N/A pCur->ldmemcl_next = cache->ldmemc_lds;
1N/A cache->ldmemc_lds = pCur;
1N/A ld->ld_memcache = cache;
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
1N/A }
1N/A
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/* Retrieves memcache with which the ldap handle has been associated. */
1N/Aint
1N/ALDAP_CALL
1N/Aldap_memcache_get( LDAP *ld, LDAPMemCache **cachep )
1N/A{
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_get ld: 0x%x\n", ld, 0, 0 );
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cachep == NULL ) {
1N/A return( LDAP_PARAM_ERROR );
1N/A }
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A *cachep = ld->ld_memcache;
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/*
1N/A * Function that stays inside libldap and proactively expires items from
1N/A * the given cache. This should be called from a newly created thread since
1N/A * it will not return until after ldap_memcache_destroy() is called.
1N/A */
1N/Avoid
1N/ALDAP_CALL
1N/Aldap_memcache_update( LDAPMemCache *cache )
1N/A{
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_update: cache 0x%x\n",
1N/A cache, 0, 0 );
1N/A
1N/A if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
1N/A return;
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( cache );
1N/A memcache_access(cache, MEMCACHE_ACCESS_UPDATE, NULL, NULL, NULL);
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
1N/A}
1N/A
1N/A/* Removes specified entries from given memcache. */
1N/Avoid
1N/ALDAP_CALL
1N/Aldap_memcache_flush( LDAPMemCache *cache, char *dn, int scope )
1N/A{
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "ldap_memcache_flush( cache: 0x%x, dn: %s, scope: %d)\n",
1N/A cache, ( dn == NULL ) ? "(null)" : dn, scope );
1N/A
1N/A if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
1N/A return;
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( cache );
1N/A
1N/A if (!dn) {
1N/A memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL);
1N/A } else {
1N/A memcache_access(cache, MEMCACHE_ACCESS_FLUSH,
1N/A (void*)dn, (void*)(uintptr_t)scope, NULL);
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
1N/A}
1N/A
1N/A/* Destroys the given memcache. */
1N/Avoid
1N/ALDAP_CALL
1N/Aldap_memcache_destroy( LDAPMemCache *cache )
1N/A{
1N/A int i = 0;
1N/A unsigned long size = sizeof(LDAPMemCache);
1N/A ldapmemcacheld *pNode = NULL, *pNextNode = NULL;
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_destroy( 0x%x )\n",
1N/A cache, 0, 0 );
1N/A
1N/A if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
1N/A return;
1N/A }
1N/A
1N/A /* Dissociate all ldap handes from this cache. */
1N/A LDAP_MEMCACHE_MUTEX_LOCK( cache );
1N/A
1N/A for (pNode = cache->ldmemc_lds; pNode; pNode = pNextNode, i++) {
1N/A LDAP_MUTEX_LOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK );
1N/A cache->ldmemc_lds = pNode->ldmemcl_next;
1N/A pNode->ldmemcl_ld->ld_memcache = NULL;
1N/A LDAP_MUTEX_UNLOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK );
1N/A pNextNode = pNode->ldmemcl_next;
1N/A NSLDAPI_FREE(pNode);
1N/A }
1N/A
1N/A size += i * sizeof(ldapmemcacheld);
1N/A
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
1N/A
1N/A /* Free array of basedns */
1N/A if (cache->ldmemc_basedns) {
1N/A for (i = 0; cache->ldmemc_basedns[i]; i++) {
1N/A size += strlen(cache->ldmemc_basedns[i]) + 1;
1N/A NSLDAPI_FREE(cache->ldmemc_basedns[i]);
1N/A }
1N/A size += (i + 1) * sizeof(char*);
1N/A NSLDAPI_FREE(cache->ldmemc_basedns);
1N/A }
1N/A
1N/A /* Free hash table used for temporary cache */
1N/A if (cache->ldmemc_resTmp) {
1N/A size += htable_sizeinbytes(cache->ldmemc_resTmp);
1N/A memcache_access(cache, MEMCACHE_ACCESS_DELETE_ALL, NULL, NULL, NULL);
1N/A htable_free(cache->ldmemc_resTmp);
1N/A }
1N/A
1N/A /* Free hash table used for primary cache */
1N/A if (cache->ldmemc_resLookup) {
1N/A size += htable_sizeinbytes(cache->ldmemc_resLookup);
1N/A memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL);
1N/A htable_free(cache->ldmemc_resLookup);
1N/A }
1N/A
1N/A memcache_adj_size(cache, size, MEMCACHE_SIZE_NON_ENTRIES,
1N/A MEMCACHE_SIZE_DEDUCT);
1N/A
1N/A LDAP_MEMCACHE_MUTEX_FREE( cache );
1N/A
1N/A NSLDAPI_FREE(cache);
1N/A}
1N/A
1N/A/************************* Internal API Functions ****************************/
1N/A
1N/A/* Creates an integer key by applying the Cyclic Reduntency Check algorithm on
1N/A a long string formed by concatenating all the search parameters plus the
1N/A current bind DN. The key is used in the cache for looking up cached
1N/A entries. It is assumed that the CRC algorithm will generate
1N/A different integers from different byte strings. */
1N/Aint
1N/Aldap_memcache_createkey(LDAP *ld, const char *base, int scope,
1N/A const char *filter, char **attrs,
1N/A int attrsonly, LDAPControl **serverctrls,
1N/A LDAPControl **clientctrls, unsigned long *keyp)
1N/A{
1N/A int nRes, i, j, i_smallest;
1N/A int len;
1N/A int defport;
1N/A char buf[50];
1N/A char *tmp, *defhost, *binddn, *keystr, *tmpbase;
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (keyp == NULL) )
1N/A return( LDAP_PARAM_ERROR );
1N/A
1N/A *keyp = 0;
1N/A
1N/A if (!memcache_exist(ld))
1N/A return( LDAP_LOCAL_ERROR );
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
1N/A nRes = memcache_validate_basedn(ld->ld_memcache, base);
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A if (nRes != LDAP_SUCCESS)
1N/A return nRes;
1N/A
1N/A defhost = NSLDAPI_STR_NONNULL(ld->ld_defhost);
1N/A defport = ld->ld_defport;
1N/A tmpbase = nsldapi_strdup(NSLDAPI_STR_NONNULL(base));
1N/A if (tmpbase == NULL)
1N/A return( LDAP_LOCAL_ERROR );
1N/A memcache_trim_basedn_spaces(tmpbase);
1N/A
1N/A if ((binddn = nsldapi_get_binddn(ld)) == NULL)
1N/A binddn = "";
1N/A
1N/A sprintf(buf, "%i\n%i\n%i\n", defport, scope, (attrsonly ? 1 : 0));
1N/A len = NSLDAPI_SAFE_STRLEN(buf) + NSLDAPI_SAFE_STRLEN(tmpbase) +
1N/A NSLDAPI_SAFE_STRLEN(filter) + NSLDAPI_SAFE_STRLEN(defhost) +
1N/A NSLDAPI_SAFE_STRLEN(binddn);
1N/A
1N/A if (attrs) {
1N/A for (i = 0; attrs[i]; i++) {
1N/A
1N/A for (i_smallest = j = i; attrs[j]; j++) {
1N/A if (strcasecmp(attrs[i_smallest], attrs[j]) > 0)
1N/A i_smallest = j;
1N/A }
1N/A
1N/A if (i != i_smallest) {
1N/A tmp = attrs[i];
1N/A attrs[i] = attrs[i_smallest];
1N/A attrs[i_smallest] = tmp;
1N/A }
1N/A
1N/A len += NSLDAPI_SAFE_STRLEN(attrs[i]);
1N/A }
1N/A } else {
1N/A len += 1;
1N/A }
1N/A
1N/A len += memcache_get_ctrls_len(serverctrls) +
1N/A memcache_get_ctrls_len(clientctrls) + 1;
1N/A
1N/A if ((keystr = (char*)NSLDAPI_CALLOC(len, sizeof(char))) == NULL) {
1N/A if (defhost != emptyStr)
1N/A NSLDAPI_FREE(defhost);
1N/A NSLDAPI_FREE(tmpbase);
1N/A return( LDAP_NO_MEMORY );
1N/A }
1N/A
1N/A sprintf(keystr, "%s\n%s\n%s\n%s\n%s\n", binddn, tmpbase,
1N/A NSLDAPI_STR_NONNULL(defhost), NSLDAPI_STR_NONNULL(filter),
1N/A NSLDAPI_STR_NONNULL(buf));
1N/A
1N/A if (attrs) {
1N/A for (i = 0; attrs[i]; i++) {
1N/A strcat(keystr, NSLDAPI_STR_NONNULL(attrs[i]));
1N/A strcat(keystr, "\n");
1N/A }
1N/A } else {
1N/A strcat(keystr, "\n");
1N/A }
1N/A
1N/A for (tmp = keystr; *tmp;
1N/A *tmp += (*tmp >= 'a' && *tmp <= 'z' ? 'A'-'a' : 0), tmp++) {
1N/A ;
1N/A }
1N/A
1N/A memcache_append_ctrls(keystr, serverctrls, clientctrls);
1N/A
1N/A /* CRC algorithm */
1N/A *keyp = crc32_convert(keystr, len);
1N/A
1N/A NSLDAPI_FREE(keystr);
1N/A NSLDAPI_FREE(tmpbase);
1N/A
1N/A return LDAP_SUCCESS;
1N/A}
1N/A
1N/A/* Searches the cache for the right cached entries, and if found, attaches
1N/A them to the given ldap handle. This function relies on locking by the
1N/A caller. */
1N/Aint
1N/Aldap_memcache_result(LDAP *ld, int msgid, unsigned long key)
1N/A{
1N/A int nRes;
1N/A LDAPMessage *pMsg = NULL;
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "ldap_memcache_result( ld: 0x%x, msgid: %d, key: 0x%8.8lx)\n",
1N/A ld, msgid, key );
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) {
1N/A return( LDAP_PARAM_ERROR );
1N/A }
1N/A
1N/A if (!memcache_exist(ld)) {
1N/A return( LDAP_LOCAL_ERROR );
1N/A }
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
1N/A
1N/A /* Search the cache and append the results to ld if found */
1N/A ++ld->ld_memcache->ldmemc_stats.ldmemcstat_tries;
1N/A if ((nRes = memcache_search(ld, key, &pMsg)) == LDAP_SUCCESS) {
1N/A nRes = memcache_add_to_ld(ld, msgid, pMsg);
1N/A ++ld->ld_memcache->ldmemc_stats.ldmemcstat_hits;
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "ldap_memcache_result: key 0x%8.8lx found in cache\n",
1N/A key, 0, 0 );
1N/A } else {
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "ldap_memcache_result: key 0x%8.8lx not found in cache\n",
1N/A key, 0, 0 );
1N/A }
1N/A
1N/A#ifdef LDAP_DEBUG
1N/A memcache_print_list( ld->ld_memcache, LIST_LRU );
1N/A memcache_report_statistics( ld->ld_memcache );
1N/A#endif /* LDAP_DEBUG */
1N/A
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/* Creates a new header in the cache so that entries arriving from the
1N/A directory server can later be cached under the header. */
1N/Aint
1N/Aldap_memcache_new(LDAP *ld, int msgid, unsigned long key, const char *basedn)
1N/A{
1N/A int nRes;
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) ) {
1N/A return( LDAP_PARAM_ERROR );
1N/A }
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A if (!memcache_exist(ld)) {
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A return( LDAP_LOCAL_ERROR );
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
1N/A nRes = memcache_add(ld, key, msgid, basedn);
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/* Appends a chain of entries to an existing cache header. Parameter "bLast"
1N/A indicates whether there will be more entries arriving for the search in
1N/A question. */
1N/Aint
1N/Aldap_memcache_append(LDAP *ld, int msgid, int bLast, LDAPMessage *result)
1N/A{
1N/A int nRes = LDAP_SUCCESS;
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_append( ld: 0x%x, ", ld, 0, 0 );
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "msgid %d, bLast: %d, result: 0x%x)\n",
1N/A msgid, bLast, result );
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || !result ) {
1N/A return( LDAP_PARAM_ERROR );
1N/A }
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A if (!memcache_exist(ld)) {
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A return( LDAP_LOCAL_ERROR );
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
1N/A
1N/A if (!bLast)
1N/A nRes = memcache_append(ld, msgid, result);
1N/A else
1N/A nRes = memcache_append_last(ld, msgid, result);
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "ldap_memcache_append: %s result for msgid %d\n",
1N/A ( nRes == LDAP_SUCCESS ) ? "added" : "failed to add", msgid , 0 );
1N/A
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/* Removes partially cached results for a search as a result of calling
1N/A ldap_abandon() by the client. */
1N/Aint
1N/Aldap_memcache_abandon(LDAP *ld, int msgid)
1N/A{
1N/A int nRes;
1N/A
1N/A if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) {
1N/A return( LDAP_PARAM_ERROR );
1N/A }
1N/A
1N/A LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A if (!memcache_exist(ld)) {
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A return( LDAP_LOCAL_ERROR );
1N/A }
1N/A
1N/A LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
1N/A nRes = memcache_remove(ld, msgid);
1N/A LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
1N/A LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/*************************** helper functions *******************************/
1N/A
1N/A/* Removes extraneous spaces in a basedn so that basedns differ by only those
1N/A spaces will be treated as equal. Extraneous spaces are those that
1N/A precedes the basedn and those that follow a comma. */
1N/A/*
1N/A * XXXmcs: this is a bit too agressive... we need to deal with the fact that
1N/A * commas and spaces may be quoted, in which case it is wrong to remove them.
1N/A */
1N/Astatic void
1N/Amemcache_trim_basedn_spaces(char *basedn)
1N/A{
1N/A char *pRead, *pWrite;
1N/A
1N/A if (!basedn)
1N/A return;
1N/A
1N/A for (pWrite = pRead = basedn; *pRead; ) {
1N/A for (; *pRead && NSLDAPI_IS_SPACE(*pRead); pRead++) {
1N/A ;
1N/A }
1N/A for (; *pRead && !NSLDAPI_IS_SEPARATER(*pRead);
1N/A *(pWrite++) = *(pRead++)) {
1N/A ;
1N/A }
1N/A *(pWrite++) = (*pRead ? *(pRead++) : *pRead);
1N/A }
1N/A}
1N/A
1N/A/* Verifies whether the results of a search should be cached or not by
1N/A checking if the search's basedn falls under any of the basedns for which
1N/A the memcache is responsible. */
1N/Astatic int
1N/Amemcache_validate_basedn(LDAPMemCache *cache, const char *basedn)
1N/A{
1N/A int i;
1N/A
1N/A if ( cache->ldmemc_basedns == NULL ) {
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A
1N/A#if 1
1N/A if (basedn == NULL) {
1N/A basedn = "";
1N/A }
1N/A#else
1N/A /* XXXmcs: I do not understand this code... */
1N/A if (basedn == NULL)
1N/A return (cache->ldmemc_basedns && cache->ldmemc_basedns[0] ?
1N/A LDAP_OPERATIONS_ERROR : LDAP_SUCCESS);
1N/A }
1N/A#endif
1N/A
1N/A for (i = 0; cache->ldmemc_basedns[i]; i++) {
1N/A if (memcache_compare_dn(basedn, cache->ldmemc_basedns[i],
1N/A LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) {
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A }
1N/A
1N/A return( LDAP_OPERATIONS_ERROR );
1N/A}
1N/A
1N/A/* Calculates the length of the buffer needed to concatenate the contents of
1N/A a ldap control. */
1N/Astatic int
1N/Amemcache_get_ctrls_len(LDAPControl **ctrls)
1N/A{
1N/A int len = 0, i;
1N/A
1N/A if (ctrls) {
1N/A for (i = 0; ctrls[i]; i++) {
1N/A len += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) +
1N/A (ctrls[i]->ldctl_value).bv_len + 4;
1N/A }
1N/A }
1N/A
1N/A return len;
1N/A}
1N/A
1N/A/* Contenates the contents of client and server controls to a buffer. */
1N/Astatic void
1N/Amemcache_append_ctrls(char *buf, LDAPControl **serverCtrls,
1N/A LDAPControl **clientCtrls)
1N/A{
1N/A int i, j;
1N/A char *pCh = buf + strlen(buf);
1N/A LDAPControl **ctrls;
1N/A
1N/A for (j = 0; j < 2; j++) {
1N/A
1N/A if ((ctrls = (j ? clientCtrls : serverCtrls)) == NULL)
1N/A continue;
1N/A
1N/A for (i = 0; ctrls[i]; i++) {
1N/A sprintf(pCh, "%s\n", NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid));
1N/A pCh += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) + 1;
1N/A if ((ctrls[i]->ldctl_value).bv_len > 0) {
1N/A memcpy(pCh, (ctrls[i]->ldctl_value).bv_val,
1N/A (ctrls[i]->ldctl_value).bv_len);
1N/A pCh += (ctrls[i]->ldctl_value).bv_len;
1N/A }
1N/A sprintf(pCh, "\n%i\n", (ctrls[i]->ldctl_iscritical ? 1 : 0));
1N/A pCh += 3;
1N/A }
1N/A }
1N/A}
1N/A
1N/A/* Increases or decreases the size (in bytes) the given memcache currently
1N/A uses. If the size goes over the limit, the function returns an error. */
1N/Astatic int
1N/Amemcache_adj_size(LDAPMemCache *cache, unsigned long size,
1N/A int usageFlags, int bAdd)
1N/A{
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "memcache_adj_size: attempting to %s %ld %s bytes...\n",
1N/A bAdd ? "add" : "remove", size,
1N/A ( usageFlags & MEMCACHE_SIZE_ENTRIES ) ? "entry" : "non-entry" );
1N/A
1N/A if (bAdd) {
1N/A cache->ldmemc_size_used += size;
1N/A if ((cache->ldmemc_size > 0) &&
1N/A (cache->ldmemc_size_used > cache->ldmemc_size)) {
1N/A
1N/A if (size > cache->ldmemc_size_entries) {
1N/A cache->ldmemc_size_used -= size;
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "memcache_adj_size: failed (size > size_entries %ld).\n",
1N/A cache->ldmemc_size_entries, 0, 0 );
1N/A return( LDAP_SIZELIMIT_EXCEEDED );
1N/A }
1N/A
1N/A while (cache->ldmemc_size_used > cache->ldmemc_size) {
1N/A if (memcache_access(cache, MEMCACHE_ACCESS_FLUSH_LRU,
1N/A NULL, NULL, NULL) != LDAP_SUCCESS) {
1N/A cache->ldmemc_size_used -= size;
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "memcache_adj_size: failed (LRU flush failed).\n",
1N/A 0, 0, 0 );
1N/A return( LDAP_SIZELIMIT_EXCEEDED );
1N/A }
1N/A }
1N/A }
1N/A if (usageFlags & MEMCACHE_SIZE_ENTRIES)
1N/A cache->ldmemc_size_entries += size;
1N/A } else {
1N/A cache->ldmemc_size_used -= size;
1N/A assert(cache->ldmemc_size_used >= 0);
1N/A if (usageFlags & MEMCACHE_SIZE_ENTRIES)
1N/A cache->ldmemc_size_entries -= size;
1N/A }
1N/A
1N/A#ifdef LDAP_DEBUG
1N/A if ( cache->ldmemc_size == 0 ) { /* no size limit */
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "memcache_adj_size: succeeded (new size: %ld bytes).\n",
1N/A cache->ldmemc_size_used, 0, 0 );
1N/A } else {
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "memcache_adj_size: succeeded (new size: %ld bytes, "
1N/A "free space: %ld bytes).\n", cache->ldmemc_size_used,
1N/A cache->ldmemc_size - cache->ldmemc_size_used, 0 );
1N/A }
1N/A#endif /* LDAP_DEBUG */
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Searches the cache for results for a particular search identified by
1N/A parameter "key", which was generated ldap_memcache_createkey(). */
1N/Astatic int
1N/Amemcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes)
1N/A{
1N/A int nRes;
1N/A ldapmemcacheRes *pRes;
1N/A
1N/A *ppRes = NULL;
1N/A
1N/A if (!memcache_exist(ld))
1N/A return LDAP_LOCAL_ERROR;
1N/A
1N/A nRes = memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_FIND,
1N/A (void*)&key, (void*)(&pRes), NULL);
1N/A
1N/A if (nRes != LDAP_SUCCESS)
1N/A return nRes;
1N/A
1N/A *ppRes = pRes->ldmemcr_resHead;
1N/A assert((pRes->ldmemcr_req_id).ldmemcrid_msgid == -1);
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Adds a new header into the cache as a place holder for entries
1N/A arriving later. */
1N/Astatic int
1N/Amemcache_add(LDAP *ld, unsigned long key, int msgid,
1N/A const char *basedn)
1N/A{
1N/A ldapmemcacheReqId reqid;
1N/A
1N/A if (!memcache_exist(ld))
1N/A return LDAP_LOCAL_ERROR;
1N/A
1N/A reqid.ldmemcrid_msgid = msgid;
1N/A reqid.ldmemcrid_ld = ld;
1N/A
1N/A return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_ADD,
1N/A (void*)&key, (void*)&reqid, (void*)basedn);
1N/A}
1N/A
1N/A/* Appends search entries arriving from the dir server to the cache. */
1N/Astatic int
1N/Amemcache_append(LDAP *ld, int msgid, LDAPMessage *pRes)
1N/A{
1N/A ldapmemcacheReqId reqid;
1N/A
1N/A if (!memcache_exist(ld))
1N/A return LDAP_LOCAL_ERROR;
1N/A
1N/A reqid.ldmemcrid_msgid = msgid;
1N/A reqid.ldmemcrid_ld = ld;
1N/A
1N/A return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND,
1N/A (void*)&reqid, (void*)pRes, NULL);
1N/A}
1N/A
1N/A/* Same as memcache_append(), but the entries being appended are the
1N/A last from the dir server. Once all entries for a search have arrived,
1N/A the entries are moved from secondary to primary cache, and a time
1N/A stamp is given to the entries. */
1N/Astatic int
1N/Amemcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes)
1N/A{
1N/A ldapmemcacheReqId reqid;
1N/A
1N/A if (!memcache_exist(ld))
1N/A return LDAP_LOCAL_ERROR;
1N/A
1N/A reqid.ldmemcrid_msgid = msgid;
1N/A reqid.ldmemcrid_ld = ld;
1N/A
1N/A return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND_LAST,
1N/A (void*)&reqid, (void*)pRes, NULL);
1N/A}
1N/A
1N/A/* Removes entries from the temporary cache. */
1N/Astatic int
1N/Amemcache_remove(LDAP *ld, int msgid)
1N/A{
1N/A ldapmemcacheReqId reqid;
1N/A
1N/A if (!memcache_exist(ld))
1N/A return LDAP_LOCAL_ERROR;
1N/A
1N/A reqid.ldmemcrid_msgid = msgid;
1N/A reqid.ldmemcrid_ld = ld;
1N/A
1N/A return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE,
1N/A (void*)&reqid, NULL, NULL);
1N/A}
1N/A
1N/A#if 0 /* this function is not used */
1N/A/* Wipes out everything in the temporary cache directory. */
1N/Astatic int
1N/Amemcache_remove_all(LDAP *ld)
1N/A{
1N/A if (!memcache_exist(ld))
1N/A return LDAP_LOCAL_ERROR;
1N/A
1N/A return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE_ALL,
1N/A NULL, NULL, NULL);
1N/A}
1N/A#endif /* 0 */
1N/A
1N/A/* Returns TRUE or FALSE */
1N/Astatic int
1N/Amemcache_exist(LDAP *ld)
1N/A{
1N/A return (ld->ld_memcache != NULL);
1N/A}
1N/A
1N/A/* Attaches cached entries to an ldap handle. */
1N/Astatic int
1N/Amemcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg)
1N/A{
1N/A int nRes = LDAP_SUCCESS;
1N/A LDAPMessage **r;
1N/A LDAPMessage *pCopy;
1N/A
1N/A nRes = memcache_dup_message(pMsg, msgid, 1, &pCopy, NULL);
1N/A if (nRes != LDAP_SUCCESS)
1N/A return nRes;
1N/A
1N/A for (r = &(ld->ld_responses); *r; r = &((*r)->lm_next))
1N/A if ((*r)->lm_msgid == msgid)
1N/A break;
1N/A
1N/A if (*r)
1N/A for (r = &((*r)->lm_chain); *r; r = &((*r)->lm_chain)) {
1N/A ;
1N/A }
1N/A
1N/A *r = pCopy;
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/* Check if main_dn is included in {dn, scope} */
1N/Astatic int
1N/Amemcache_compare_dn(const char *main_dn, const char *dn, int scope)
1N/A{
1N/A int nRes;
1N/A char **components = NULL;
1N/A char **main_components = NULL;
1N/A
1N/A components = ldap_explode_dn(dn, 0);
1N/A main_components = ldap_explode_dn(main_dn, 0);
1N/A
1N/A if (!components || !main_components) {
1N/A nRes = LDAP_COMPARE_TRUE;
1N/A }
1N/A else {
1N/A
1N/A int i, main_i;
1N/A
1N/A main_i = ldap_count_values(main_components) - 1;
1N/A i = ldap_count_values(components) - 1;
1N/A
1N/A for (; i >= 0 && main_i >= 0; i--, main_i--) {
1N/A if (strcasecmp(main_components[main_i], components[i]))
1N/A break;
1N/A }
1N/A
1N/A if (i >= 0 && main_i >= 0) {
1N/A nRes = LDAP_COMPARE_FALSE;
1N/A }
1N/A else if (i < 0 && main_i < 0) {
1N/A if (scope != LDAP_SCOPE_ONELEVEL)
1N/A nRes = LDAP_COMPARE_TRUE;
1N/A else
1N/A nRes = LDAP_COMPARE_FALSE;
1N/A }
1N/A else if (main_i < 0) {
1N/A nRes = LDAP_COMPARE_FALSE;
1N/A }
1N/A else {
1N/A if (scope == LDAP_SCOPE_BASE)
1N/A nRes = LDAP_COMPARE_FALSE;
1N/A else if (scope == LDAP_SCOPE_SUBTREE)
1N/A nRes = LDAP_COMPARE_TRUE;
1N/A else if (main_i == 0)
1N/A nRes = LDAP_COMPARE_TRUE;
1N/A else
1N/A nRes = LDAP_COMPARE_FALSE;
1N/A }
1N/A }
1N/A
1N/A if (components)
1N/A ldap_value_free(components);
1N/A
1N/A if (main_components)
1N/A ldap_value_free(main_components);
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/* Dup a complete separate copy of a berelement, including the buffers
1N/A the berelement points to. */
1N/Astatic BerElement*
1N/Amemcache_ber_dup(BerElement* pBer, unsigned long *pSize)
1N/A{
1N/A BerElement *p = ber_dup(pBer);
1N/A
1N/A *pSize = 0;
1N/A
1N/A if (p) {
1N/A
1N/A *pSize += sizeof(BerElement) + EXTRA_SIZE;
1N/A
1N/A if (p->ber_len <= EXTRA_SIZE) {
1N/A p->ber_flags |= LBER_FLAG_NO_FREE_BUFFER;
1N/A p->ber_buf = (char*)p + sizeof(BerElement);
1N/A } else {
1N/A p->ber_flags &= ~LBER_FLAG_NO_FREE_BUFFER;
1N/A p->ber_buf = (char*)NSLDAPI_CALLOC(1, p->ber_len);
1N/A *pSize += (p->ber_buf ? p->ber_len : 0);
1N/A }
1N/A
1N/A if (p->ber_buf) {
1N/A p->ber_ptr = p->ber_buf + (pBer->ber_ptr - pBer->ber_buf);
1N/A p->ber_end = p->ber_buf + p->ber_len;
1N/A memcpy(p->ber_buf, pBer->ber_buf, p->ber_len);
1N/A } else {
1N/A ber_free(p, 0);
1N/A p = NULL;
1N/A *pSize = 0;
1N/A }
1N/A }
1N/A
1N/A return p;
1N/A}
1N/A
1N/A/* Dup a entry or a chain of entries. */
1N/Astatic int
1N/Amemcache_dup_message(LDAPMessage *res, int msgid, int fromcache,
1N/A LDAPMessage **ppResCopy, unsigned long *pSize)
1N/A{
1N/A int nRes = LDAP_SUCCESS;
1N/A unsigned long ber_size;
1N/A LDAPMessage *pCur;
1N/A LDAPMessage **ppCurNew;
1N/A
1N/A *ppResCopy = NULL;
1N/A
1N/A if (pSize)
1N/A *pSize = 0;
1N/A
1N/A /* Make a copy of res */
1N/A for (pCur = res, ppCurNew = ppResCopy; pCur;
1N/A pCur = pCur->lm_chain, ppCurNew = &((*ppCurNew)->lm_chain)) {
1N/A
1N/A if ((*ppCurNew = (LDAPMessage*)NSLDAPI_CALLOC(1,
1N/A sizeof(LDAPMessage))) == NULL) {
1N/A nRes = LDAP_NO_MEMORY;
1N/A break;
1N/A }
1N/A
1N/A memcpy(*ppCurNew, pCur, sizeof(LDAPMessage));
1N/A (*ppCurNew)->lm_next = NULL;
1N/A (*ppCurNew)->lm_ber = memcache_ber_dup(pCur->lm_ber, &ber_size);
1N/A (*ppCurNew)->lm_msgid = msgid;
1N/A (*ppCurNew)->lm_fromcache = (fromcache != 0);
1N/A
1N/A if (pSize)
1N/A *pSize += sizeof(LDAPMessage) + ber_size;
1N/A }
1N/A
1N/A if ((nRes != LDAP_SUCCESS) && (*ppResCopy != NULL)) {
1N/A ldap_msgfree(*ppResCopy);
1N/A *ppResCopy = NULL;
1N/A if (pSize)
1N/A *pSize = 0;
1N/A }
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A/************************* Cache Functions ***********************/
1N/A
1N/A/* Frees a cache header. */
1N/Astatic int
1N/Amemcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes)
1N/A{
1N/A if (pRes) {
1N/A
1N/A unsigned long size = sizeof(ldapmemcacheRes);
1N/A
1N/A if (pRes->ldmemcr_basedn) {
1N/A size += strlen(pRes->ldmemcr_basedn) + 1;
1N/A NSLDAPI_FREE(pRes->ldmemcr_basedn);
1N/A }
1N/A
1N/A if (pRes->ldmemcr_resHead) {
1N/A size += pRes->ldmemcr_resSize;
1N/A ldap_msgfree(pRes->ldmemcr_resHead);
1N/A }
1N/A
1N/A NSLDAPI_FREE(pRes);
1N/A
1N/A memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
1N/A MEMCACHE_SIZE_DEDUCT);
1N/A }
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Detaches a cache header from the list of headers. */
1N/Astatic int
1N/Amemcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index)
1N/A{
1N/A if (pRes->ldmemcr_prev[index])
1N/A pRes->ldmemcr_prev[index]->ldmemcr_next[index] =
1N/A pRes->ldmemcr_next[index];
1N/A
1N/A if (pRes->ldmemcr_next[index])
1N/A pRes->ldmemcr_next[index]->ldmemcr_prev[index] =
1N/A pRes->ldmemcr_prev[index];
1N/A
1N/A if (cache->ldmemc_resHead[index] == pRes)
1N/A cache->ldmemc_resHead[index] = pRes->ldmemcr_next[index];
1N/A
1N/A if (cache->ldmemc_resTail[index] == pRes)
1N/A cache->ldmemc_resTail[index] = pRes->ldmemcr_prev[index];
1N/A
1N/A pRes->ldmemcr_prev[index] = NULL;
1N/A pRes->ldmemcr_next[index] = NULL;
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Inserts a new cache header to a list of headers. */
1N/Astatic int
1N/Amemcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index)
1N/A{
1N/A if (cache->ldmemc_resHead[index])
1N/A cache->ldmemc_resHead[index]->ldmemcr_prev[index] = pRes;
1N/A else
1N/A cache->ldmemc_resTail[index] = pRes;
1N/A
1N/A pRes->ldmemcr_prev[index] = NULL;
1N/A pRes->ldmemcr_next[index] = cache->ldmemc_resHead[index];
1N/A cache->ldmemc_resHead[index] = pRes;
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Appends a chain of entries to the given cache header. */
1N/Astatic int
1N/Amemcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg,
1N/A unsigned long size)
1N/A{
1N/A if (pRes->ldmemcr_resTail)
1N/A pRes->ldmemcr_resTail->lm_chain = pMsg;
1N/A else
1N/A pRes->ldmemcr_resHead = pMsg;
1N/A
1N/A for (pRes->ldmemcr_resTail = pMsg;
1N/A pRes->ldmemcr_resTail->lm_chain;
1N/A pRes->ldmemcr_resTail = pRes->ldmemcr_resTail->lm_chain) {
1N/A ;
1N/A }
1N/A
1N/A pRes->ldmemcr_resSize += size;
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A
1N/A#ifdef LDAP_DEBUG
1N/Astatic void
1N/Amemcache_print_list( LDAPMemCache *cache, int index )
1N/A{
1N/A char *name;
1N/A ldapmemcacheRes *restmp;
1N/A
1N/A switch( index ) {
1N/A case LIST_TTL:
1N/A name = "TTL";
1N/A break;
1N/A case LIST_LRU:
1N/A name = "LRU";
1N/A break;
1N/A case LIST_TMP:
1N/A name = "TMP";
1N/A break;
1N/A case LIST_TOTAL:
1N/A name = "TOTAL";
1N/A break;
1N/A default:
1N/A name = "unknown";
1N/A }
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x %s list:\n",
1N/A cache, name, 0 );
1N/A for ( restmp = cache->ldmemc_resHead[index]; restmp != NULL;
1N/A restmp = restmp->ldmemcr_next[index] ) {
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A " key: 0x%8.8lx, ld: 0x%x, msgid: %d\n",
1N/A restmp->ldmemcr_crc_key,
1N/A restmp->ldmemcr_req_id.ldmemcrid_ld,
1N/A restmp->ldmemcr_req_id.ldmemcrid_msgid );
1N/A }
1N/A LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x end of %s list.\n",
1N/A cache, name, 0 );
1N/A}
1N/A#endif /* LDAP_DEBUG */
1N/A
1N/A/* Tells whether a cached result has expired. */
1N/Astatic int
1N/Amemcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes,
1N/A unsigned long curTime)
1N/A{
1N/A if (!cache->ldmemc_ttl)
1N/A return 0;
1N/A
1N/A return ((unsigned long)difftime(
1N/A (time_t)curTime,
1N/A (time_t)(pRes->ldmemcr_timestamp)) >=
1N/A cache->ldmemc_ttl);
1N/A}
1N/A
1N/A/* Operates the cache in a central place. */
1N/Astatic int
1N/Amemcache_access(LDAPMemCache *cache, int mode,
1N/A void *pData1, void *pData2, void *pData3)
1N/A{
1N/A int nRes = LDAP_SUCCESS;
1N/A unsigned long size = 0;
1N/A
1N/A /* Add a new cache header to the cache. */
1N/A if (mode == MEMCACHE_ACCESS_ADD) {
1N/A unsigned long key = *((unsigned long*)pData1);
1N/A char *basedn = (char*)pData3;
1N/A ldapmemcacheRes *pRes = NULL;
1N/A
1N/A nRes = htable_get(cache->ldmemc_resTmp, pData2, (void**)&pRes);
1N/A if (nRes == LDAP_SUCCESS)
1N/A return( LDAP_ALREADY_EXISTS );
1N/A
1N/A pRes = (ldapmemcacheRes*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheRes));
1N/A if (pRes == NULL)
1N/A return( LDAP_NO_MEMORY );
1N/A
1N/A pRes->ldmemcr_crc_key = key;
1N/A pRes->ldmemcr_req_id = *((ldapmemcacheReqId*)pData2);
1N/A pRes->ldmemcr_basedn = (basedn ? nsldapi_strdup(basedn) : NULL);
1N/A
1N/A size += sizeof(ldapmemcacheRes) + strlen(basedn) + 1;
1N/A nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
1N/A MEMCACHE_SIZE_ADD);
1N/A if (nRes == LDAP_SUCCESS)
1N/A nRes = htable_put(cache->ldmemc_resTmp, pData2, (void*)pRes);
1N/A if (nRes == LDAP_SUCCESS)
1N/A memcache_add_to_list(cache, pRes, LIST_TMP);
1N/A else
1N/A memcache_free_entry(cache, pRes);
1N/A }
1N/A /* Append entries to an existing cache header. */
1N/A else if ((mode == MEMCACHE_ACCESS_APPEND) ||
1N/A (mode == MEMCACHE_ACCESS_APPEND_LAST)) {
1N/A
1N/A LDAPMessage *pMsg = (LDAPMessage*)pData2;
1N/A LDAPMessage *pCopy = NULL;
1N/A ldapmemcacheRes *pRes = NULL;
1N/A
1N/A nRes = htable_get(cache->ldmemc_resTmp, pData1, (void**)&pRes);
1N/A if (nRes != LDAP_SUCCESS)
1N/A return nRes;
1N/A
1N/A nRes = memcache_dup_message(pMsg, pMsg->lm_msgid, 0, &pCopy, &size);
1N/A if (nRes != LDAP_SUCCESS) {
1N/A nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pRes, LIST_TMP);
1N/A memcache_free_entry(cache, pRes);
1N/A return nRes;
1N/A }
1N/A
1N/A nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
1N/A MEMCACHE_SIZE_ADD);
1N/A if (nRes != LDAP_SUCCESS) {
1N/A ldap_msgfree(pCopy);
1N/A nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pRes, LIST_TMP);
1N/A memcache_free_entry(cache, pRes);
1N/A return nRes;
1N/A }
1N/A
1N/A memcache_add_res_to_list(pRes, pCopy, size);
1N/A
1N/A if (mode == MEMCACHE_ACCESS_APPEND)
1N/A return( LDAP_SUCCESS );
1N/A
1N/A nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pRes, LIST_TMP);
1N/A (pRes->ldmemcr_req_id).ldmemcrid_ld = NULL;
1N/A (pRes->ldmemcr_req_id).ldmemcrid_msgid = -1;
1N/A pRes->ldmemcr_timestamp = (unsigned long)time(NULL);
1N/A
1N/A if ((nRes = htable_put(cache->ldmemc_resLookup,
1N/A (void*)&(pRes->ldmemcr_crc_key),
1N/A (void*)pRes)) == LDAP_SUCCESS) {
1N/A memcache_add_to_list(cache, pRes, LIST_TTL);
1N/A memcache_add_to_list(cache, pRes, LIST_LRU);
1N/A } else {
1N/A memcache_free_entry(cache, pRes);
1N/A }
1N/A }
1N/A /* Search for cached entries for a particular search. */
1N/A else if (mode == MEMCACHE_ACCESS_FIND) {
1N/A
1N/A ldapmemcacheRes **ppRes = (ldapmemcacheRes**)pData2;
1N/A
1N/A nRes = htable_get(cache->ldmemc_resLookup, pData1, (void**)ppRes);
1N/A if (nRes != LDAP_SUCCESS)
1N/A return nRes;
1N/A
1N/A if (!memcache_expired(cache, *ppRes, (unsigned long)time(0))) {
1N/A memcache_free_from_list(cache, *ppRes, LIST_LRU);
1N/A memcache_add_to_list(cache, *ppRes, LIST_LRU);
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A
1N/A nRes = htable_remove(cache->ldmemc_resLookup, pData1, NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, *ppRes, LIST_TTL);
1N/A memcache_free_from_list(cache, *ppRes, LIST_LRU);
1N/A memcache_free_entry(cache, *ppRes);
1N/A nRes = LDAP_NO_SUCH_OBJECT;
1N/A *ppRes = NULL;
1N/A }
1N/A /* Remove cached entries in the temporary cache. */
1N/A else if (mode == MEMCACHE_ACCESS_DELETE) {
1N/A
1N/A ldapmemcacheRes *pCurRes = NULL;
1N/A
1N/A if ((nRes = htable_remove(cache->ldmemc_resTmp, pData1,
1N/A (void**)&pCurRes)) == LDAP_SUCCESS) {
1N/A memcache_free_from_list(cache, pCurRes, LIST_TMP);
1N/A memcache_free_entry(cache, pCurRes);
1N/A }
1N/A }
1N/A /* Wipe out the temporary cache. */
1N/A else if (mode == MEMCACHE_ACCESS_DELETE_ALL) {
1N/A
1N/A nRes = htable_removeall(cache->ldmemc_resTmp, (void*)cache);
1N/A }
1N/A /* Remove expired entries from primary cache. */
1N/A else if (mode == MEMCACHE_ACCESS_UPDATE) {
1N/A
1N/A ldapmemcacheRes *pCurRes = cache->ldmemc_resTail[LIST_TTL];
1N/A unsigned long curTime = (unsigned long)time(NULL);
1N/A
1N/A for (; pCurRes; pCurRes = cache->ldmemc_resTail[LIST_TTL]) {
1N/A
1N/A if (!memcache_expired(cache, pCurRes, curTime))
1N/A break;
1N/A
1N/A nRes = htable_remove(cache->ldmemc_resLookup,
1N/A (void*)&(pCurRes->ldmemcr_crc_key), NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pCurRes, LIST_TTL);
1N/A memcache_free_from_list(cache, pCurRes, LIST_LRU);
1N/A memcache_free_entry(cache, pCurRes);
1N/A }
1N/A }
1N/A /* Wipe out the primary cache. */
1N/A else if (mode == MEMCACHE_ACCESS_FLUSH_ALL) {
1N/A
1N/A ldapmemcacheRes *pCurRes = cache->ldmemc_resHead[LIST_TTL];
1N/A
1N/A nRes = htable_removeall(cache->ldmemc_resLookup, (void*)cache);
1N/A
1N/A for (; pCurRes; pCurRes = cache->ldmemc_resHead[LIST_TTL]) {
1N/A memcache_free_from_list(cache, pCurRes, LIST_LRU);
1N/A cache->ldmemc_resHead[LIST_TTL] =
1N/A cache->ldmemc_resHead[LIST_TTL]->ldmemcr_next[LIST_TTL];
1N/A memcache_free_entry(cache, pCurRes);
1N/A }
1N/A cache->ldmemc_resTail[LIST_TTL] = NULL;
1N/A }
1N/A /* Remove cached entries in both primary and temporary cache. */
1N/A else if (mode == MEMCACHE_ACCESS_FLUSH) {
1N/A
1N/A int i, list_id, bDone;
1N/A int scope = (int)(uintptr_t)pData2;
1N/A char *dn = (char*)pData1;
1N/A char *dnTmp;
1N/A BerElement ber;
1N/A LDAPMessage *pMsg;
1N/A ldapmemcacheRes *pRes;
1N/A
1N/A if (cache->ldmemc_basedns) {
1N/A for (i = 0; cache->ldmemc_basedns[i]; i++) {
1N/A if ((memcache_compare_dn(cache->ldmemc_basedns[i], dn,
1N/A LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) ||
1N/A (memcache_compare_dn(dn, cache->ldmemc_basedns[i],
1N/A LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE))
1N/A break;
1N/A }
1N/A if (cache->ldmemc_basedns[i] == NULL)
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A
1N/A for (i = 0; i < 2; i++) {
1N/A
1N/A list_id = (i == 0 ? LIST_TTL : LIST_TMP);
1N/A
1N/A for (pRes = cache->ldmemc_resHead[list_id]; pRes != NULL;
1N/A pRes = pRes->ldmemcr_next[list_id]) {
1N/A
1N/A if ((memcache_compare_dn(pRes->ldmemcr_basedn, dn,
1N/A LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE) &&
1N/A (memcache_compare_dn(dn, pRes->ldmemcr_basedn,
1N/A LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE))
1N/A continue;
1N/A
1N/A for (pMsg = pRes->ldmemcr_resHead, bDone = 0;
1N/A !bDone && pMsg; pMsg = pMsg->lm_chain) {
1N/A
1N/A if (!NSLDAPI_IS_SEARCH_ENTRY( pMsg->lm_msgtype ))
1N/A continue;
1N/A
1N/A ber = *(pMsg->lm_ber);
1N/A if (ber_scanf(&ber, "{a", &dnTmp) != LBER_ERROR) {
1N/A bDone = (memcache_compare_dn(dnTmp, dn, scope) ==
1N/A LDAP_COMPARE_TRUE);
1N/A ldap_memfree(dnTmp);
1N/A }
1N/A }
1N/A
1N/A if (!bDone)
1N/A continue;
1N/A
1N/A if (list_id == LIST_TTL) {
1N/A nRes = htable_remove(cache->ldmemc_resLookup,
1N/A (void*)&(pRes->ldmemcr_crc_key), NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pRes, LIST_TTL);
1N/A memcache_free_from_list(cache, pRes, LIST_LRU);
1N/A } else {
1N/A nRes = htable_remove(cache->ldmemc_resTmp,
1N/A (void*)&(pRes->ldmemcr_req_id), NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pRes, LIST_TMP);
1N/A }
1N/A memcache_free_entry(cache, pRes);
1N/A }
1N/A }
1N/A }
1N/A /* Flush least recently used entries from cache */
1N/A else if (mode == MEMCACHE_ACCESS_FLUSH_LRU) {
1N/A
1N/A ldapmemcacheRes *pRes = cache->ldmemc_resTail[LIST_LRU];
1N/A
1N/A if (pRes == NULL)
1N/A return LDAP_NO_SUCH_OBJECT;
1N/A
1N/A LDAPDebug( LDAP_DEBUG_TRACE,
1N/A "memcache_access FLUSH_LRU: removing key 0x%8.8lx\n",
1N/A pRes->ldmemcr_crc_key, 0, 0 );
1N/A nRes = htable_remove(cache->ldmemc_resLookup,
1N/A (void*)&(pRes->ldmemcr_crc_key), NULL);
1N/A assert(nRes == LDAP_SUCCESS);
1N/A memcache_free_from_list(cache, pRes, LIST_TTL);
1N/A memcache_free_from_list(cache, pRes, LIST_LRU);
1N/A memcache_free_entry(cache, pRes);
1N/A }
1N/A /* Unknown command */
1N/A else {
1N/A nRes = LDAP_PARAM_ERROR;
1N/A }
1N/A
1N/A return nRes;
1N/A}
1N/A
1N/A
1N/A#ifdef LDAP_DEBUG
1N/Astatic void
1N/Amemcache_report_statistics( LDAPMemCache *cache )
1N/A{
1N/A unsigned long hitrate;
1N/A
1N/A if ( cache->ldmemc_stats.ldmemcstat_tries == 0 ) {
1N/A hitrate = 0;
1N/A } else {
1N/A hitrate = ( 100L * cache->ldmemc_stats.ldmemcstat_hits ) /
1N/A cache->ldmemc_stats.ldmemcstat_tries;
1N/A }
1N/A LDAPDebug( LDAP_DEBUG_STATS, "memcache 0x%x:\n", cache, 0, 0 );
1N/A LDAPDebug( LDAP_DEBUG_STATS, " tries: %ld hits: %ld hitrate: %ld%%\n",
1N/A cache->ldmemc_stats.ldmemcstat_tries,
1N/A cache->ldmemc_stats.ldmemcstat_hits, hitrate );
1N/A if ( cache->ldmemc_size <= 0 ) { /* no size limit */
1N/A LDAPDebug( LDAP_DEBUG_STATS, " memory bytes used: %ld\n",
1N/A cache->ldmemc_size_used, 0, 0 );
1N/A } else {
1N/A LDAPDebug( LDAP_DEBUG_STATS, " memory bytes used: %ld free: %ld\n",
1N/A cache->ldmemc_size_used,
1N/A cache->ldmemc_size - cache->ldmemc_size_used, 0 );
1N/A }
1N/A}
1N/A#endif /* LDAP_DEBUG */
1N/A
1N/A/************************ Hash Table Functions *****************************/
1N/A
1N/A/* Calculates size (# of entries) of hash table given the size limit for
1N/A the cache. */
1N/Astatic int
1N/Ahtable_calculate_size(int sizelimit)
1N/A{
1N/A int i, j;
1N/A int size = (int)(((double)sizelimit /
1N/A (double)(sizeof(BerElement) + EXTRA_SIZE)) / 1.5);
1N/A
1N/A /* Get a prime # */
1N/A size = (size & 0x1 ? size : size + 1);
1N/A for (i = 3, j = size / 2; i < j; i++) {
1N/A if ((size % i) == 0) {
1N/A size += 2;
1N/A i = 3;
1N/A j = size / 2;
1N/A }
1N/A }
1N/A
1N/A return size;
1N/A}
1N/A
1N/A/* Returns the size in bytes of the given hash table. */
1N/Astatic int
1N/Ahtable_sizeinbytes(HashTable *pTable)
1N/A{
1N/A if (!pTable)
1N/A return 0;
1N/A
1N/A return (pTable->size * sizeof(HashTableNode));
1N/A}
1N/A
1N/A/* Inserts an item into the hash table. */
1N/Astatic int
1N/Ahtable_put(HashTable *pTable, void *key, void *pData)
1N/A{
1N/A int index = pTable->hashfunc(pTable->size, key);
1N/A
1N/A if (index >= 0 && index < pTable->size)
1N/A return pTable->putdata(&(pTable->table[index].pData), key, pData);
1N/A
1N/A return( LDAP_OPERATIONS_ERROR );
1N/A}
1N/A
1N/A/* Retrieves an item from the hash table. */
1N/Astatic int
1N/Ahtable_get(HashTable *pTable, void *key, void **ppData)
1N/A{
1N/A int index = pTable->hashfunc(pTable->size, key);
1N/A
1N/A *ppData = NULL;
1N/A
1N/A if (index >= 0 && index < pTable->size)
1N/A return pTable->getdata(pTable->table[index].pData, key, ppData);
1N/A
1N/A return( LDAP_OPERATIONS_ERROR );
1N/A}
1N/A
1N/A/* Performs a miscellaneous operation on a hash table entry. */
1N/Astatic int
1N/Ahtable_misc(HashTable *pTable, void *key, void *pData)
1N/A{
1N/A if (pTable->miscfunc) {
1N/A int index = pTable->hashfunc(pTable->size, key);
1N/A if (index >= 0 && index < pTable->size)
1N/A return pTable->miscfunc(&(pTable->table[index].pData), key, pData);
1N/A }
1N/A
1N/A return( LDAP_OPERATIONS_ERROR );
1N/A}
1N/A
1N/A/* Removes an item from the hash table. */
1N/Astatic int
1N/Ahtable_remove(HashTable *pTable, void *key, void **ppData)
1N/A{
1N/A int index = pTable->hashfunc(pTable->size, key);
1N/A
1N/A if (ppData)
1N/A *ppData = NULL;
1N/A
1N/A if (index >= 0 && index < pTable->size)
1N/A return pTable->removedata(&(pTable->table[index].pData), key, ppData);
1N/A
1N/A return( LDAP_OPERATIONS_ERROR );
1N/A}
1N/A
1N/A/* Removes everything in the hash table. */
1N/Astatic int
1N/Ahtable_removeall(HashTable *pTable, void *pData)
1N/A{
1N/A int i;
1N/A
1N/A for (i = 0; i < pTable->size; i++)
1N/A pTable->clrtablenode(&(pTable->table[i].pData), pData);
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Creates a new hash table. */
1N/Astatic int
1N/Ahtable_create(int size_limit, HashFuncPtr hashf,
1N/A PutDataPtr putDataf, GetDataPtr getDataf,
1N/A RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef,
1N/A MiscFuncPtr miscOpf, HashTable **ppTable)
1N/A{
1N/A size_limit = htable_calculate_size(size_limit);
1N/A
1N/A if ((*ppTable = (HashTable*)NSLDAPI_CALLOC(1, sizeof(HashTable))) == NULL)
1N/A return( LDAP_NO_MEMORY );
1N/A
1N/A (*ppTable)->table = (HashTableNode*)NSLDAPI_CALLOC(size_limit,
1N/A sizeof(HashTableNode));
1N/A if ((*ppTable)->table == NULL) {
1N/A NSLDAPI_FREE(*ppTable);
1N/A *ppTable = NULL;
1N/A return( LDAP_NO_MEMORY );
1N/A }
1N/A
1N/A (*ppTable)->size = size_limit;
1N/A (*ppTable)->hashfunc = hashf;
1N/A (*ppTable)->putdata = putDataf;
1N/A (*ppTable)->getdata = getDataf;
1N/A (*ppTable)->miscfunc = miscOpf;
1N/A (*ppTable)->removedata = removeDataf;
1N/A (*ppTable)->clrtablenode = clrNodef;
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Destroys a hash table. */
1N/Astatic int
1N/Ahtable_free(HashTable *pTable)
1N/A{
1N/A NSLDAPI_FREE(pTable->table);
1N/A NSLDAPI_FREE(pTable);
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/**************** Hash table callbacks for temporary cache ****************/
1N/A
1N/A/* Hash function */
1N/Astatic int
1N/Amsgid_hashf(int table_size, void *key)
1N/A{
1N/A uint_t code = (uint_t)(uintptr_t)((ldapmemcacheReqId*)key)->ldmemcrid_ld;
1N/A return (((code << 20) + (code >> 12)) % table_size);
1N/A}
1N/A
1N/A/* Called by hash table to insert an item. */
1N/Astatic int
1N/Amsgid_putdata(void **ppTableData, void *key, void *pData)
1N/A{
1N/A ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
1N/A ldapmemcacheRes *pRes = (ldapmemcacheRes*)pData;
1N/A ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
1N/A ldapmemcacheRes *pCurRes = *ppHead;
1N/A ldapmemcacheRes *pPrev = NULL;
1N/A
1N/A for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) {
1N/A if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
1N/A break;
1N/A pPrev = pCurRes;
1N/A }
1N/A
1N/A if (pCurRes) {
1N/A for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) {
1N/A if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid ==
1N/A pReqId->ldmemcrid_msgid)
1N/A return( LDAP_ALREADY_EXISTS );
1N/A pPrev = pCurRes;
1N/A }
1N/A pPrev->ldmemcr_next[LIST_TTL] = pRes;
1N/A pRes->ldmemcr_prev[LIST_TTL] = pPrev;
1N/A pRes->ldmemcr_next[LIST_TTL] = NULL;
1N/A } else {
1N/A if (pPrev)
1N/A pPrev->ldmemcr_htable_next = pRes;
1N/A else
1N/A *ppHead = pRes;
1N/A pRes->ldmemcr_htable_next = NULL;
1N/A }
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Called by hash table to retrieve an item. */
1N/Astatic int
1N/Amsgid_getdata(void *pTableData, void *key, void **ppData)
1N/A{
1N/A ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
1N/A ldapmemcacheRes *pCurRes = (ldapmemcacheRes*)pTableData;
1N/A
1N/A *ppData = NULL;
1N/A
1N/A for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) {
1N/A if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
1N/A break;
1N/A }
1N/A
1N/A if (!pCurRes)
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A
1N/A for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) {
1N/A if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid ==
1N/A pReqId->ldmemcrid_msgid) {
1N/A *ppData = (void*)pCurRes;
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A }
1N/A
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A}
1N/A
1N/A/* Called by hash table to remove an item. */
1N/Astatic int
1N/Amsgid_removedata(void **ppTableData, void *key, void **ppData)
1N/A{
1N/A ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData);
1N/A ldapmemcacheRes *pCurRes = NULL;
1N/A ldapmemcacheRes *pPrev = NULL;
1N/A ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
1N/A
1N/A if (ppData)
1N/A *ppData = NULL;
1N/A
1N/A for (; pHead; pHead = pHead->ldmemcr_htable_next) {
1N/A if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
1N/A break;
1N/A pPrev = pHead;
1N/A }
1N/A
1N/A if (!pHead)
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A
1N/A for (pCurRes = pHead; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) {
1N/A if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid ==
1N/A pReqId->ldmemcrid_msgid)
1N/A break;
1N/A }
1N/A
1N/A if (!pCurRes)
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A
1N/A if (ppData) {
1N/A pCurRes->ldmemcr_next[LIST_TTL] = NULL;
1N/A pCurRes->ldmemcr_prev[LIST_TTL] = NULL;
1N/A pCurRes->ldmemcr_htable_next = NULL;
1N/A *ppData = (void*)pCurRes;
1N/A }
1N/A
1N/A if (pCurRes != pHead) {
1N/A if (pCurRes->ldmemcr_prev[LIST_TTL])
1N/A pCurRes->ldmemcr_prev[LIST_TTL]->ldmemcr_next[LIST_TTL] =
1N/A pCurRes->ldmemcr_next[LIST_TTL];
1N/A if (pCurRes->ldmemcr_next[LIST_TTL])
1N/A pCurRes->ldmemcr_next[LIST_TTL]->ldmemcr_prev[LIST_TTL] =
1N/A pCurRes->ldmemcr_prev[LIST_TTL];
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A
1N/A if (pPrev) {
1N/A if (pHead->ldmemcr_next[LIST_TTL]) {
1N/A pPrev->ldmemcr_htable_next = pHead->ldmemcr_next[LIST_TTL];
1N/A pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next =
1N/A pHead->ldmemcr_htable_next;
1N/A } else {
1N/A pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next;
1N/A }
1N/A } else {
1N/A if (pHead->ldmemcr_next[LIST_TTL]) {
1N/A *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_next[LIST_TTL];
1N/A pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next =
1N/A pHead->ldmemcr_htable_next;
1N/A } else {
1N/A *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next;
1N/A }
1N/A }
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Called by hash table to remove all cached entries associated to searches
1N/A being performed using the given ldap handle. */
1N/Astatic int
1N/Amsgid_clear_ld_items(void **ppTableData, void *key, void *pData)
1N/A{
1N/A LDAPMemCache *cache = (LDAPMemCache*)pData;
1N/A ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData);
1N/A ldapmemcacheRes *pPrev = NULL;
1N/A ldapmemcacheRes *pCurRes = NULL;
1N/A ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
1N/A
1N/A for (; pHead; pHead = pHead->ldmemcr_htable_next) {
1N/A if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
1N/A break;
1N/A pPrev = pHead;
1N/A }
1N/A
1N/A if (!pHead)
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A
1N/A if (pPrev)
1N/A pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next;
1N/A else
1N/A *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next;
1N/A
1N/A for (pCurRes = pHead; pHead; pCurRes = pHead) {
1N/A pHead = pHead->ldmemcr_next[LIST_TTL];
1N/A memcache_free_from_list(cache, pCurRes, LIST_TMP);
1N/A memcache_free_entry(cache, pCurRes);
1N/A }
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Called by hash table for removing all items in the table. */
1N/Astatic void
1N/Amsgid_clearnode(void **ppTableData, void *pData)
1N/A{
1N/A LDAPMemCache *cache = (LDAPMemCache*)pData;
1N/A ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
1N/A ldapmemcacheRes *pSubHead = *ppHead;
1N/A ldapmemcacheRes *pCurRes = NULL;
1N/A
1N/A for (; *ppHead; pSubHead = *ppHead) {
1N/A ppHead = &((*ppHead)->ldmemcr_htable_next);
1N/A for (pCurRes = pSubHead; pSubHead; pCurRes = pSubHead) {
1N/A pSubHead = pSubHead->ldmemcr_next[LIST_TTL];
1N/A memcache_free_from_list(cache, pCurRes, LIST_TMP);
1N/A memcache_free_entry(cache, pCurRes);
1N/A }
1N/A }
1N/A}
1N/A
1N/A/********************* Hash table for primary cache ************************/
1N/A
1N/A/* Hash function */
1N/Astatic int
1N/Aattrkey_hashf(int table_size, void *key)
1N/A{
1N/A return ((*((unsigned long*)key)) % table_size);
1N/A}
1N/A
1N/A/* Called by hash table to insert an item. */
1N/Astatic int
1N/Aattrkey_putdata(void **ppTableData, void *key, void *pData)
1N/A{
1N/A unsigned long attrkey = *((unsigned long*)key);
1N/A ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
1N/A ldapmemcacheRes *pRes = *ppHead;
1N/A
1N/A for (; pRes; pRes = pRes->ldmemcr_htable_next) {
1N/A if (pRes->ldmemcr_crc_key == attrkey)
1N/A return( LDAP_ALREADY_EXISTS );
1N/A }
1N/A
1N/A pRes = (ldapmemcacheRes*)pData;
1N/A pRes->ldmemcr_htable_next = *ppHead;
1N/A *ppHead = pRes;
1N/A
1N/A return( LDAP_SUCCESS );
1N/A}
1N/A
1N/A/* Called by hash table to retrieve an item. */
1N/Astatic int
1N/Aattrkey_getdata(void *pTableData, void *key, void **ppData)
1N/A{
1N/A unsigned long attrkey = *((unsigned long*)key);
1N/A ldapmemcacheRes *pRes = (ldapmemcacheRes*)pTableData;
1N/A
1N/A for (; pRes; pRes = pRes->ldmemcr_htable_next) {
1N/A if (pRes->ldmemcr_crc_key == attrkey) {
1N/A *ppData = (void*)pRes;
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A }
1N/A
1N/A *ppData = NULL;
1N/A
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A}
1N/A
1N/A/* Called by hash table to remove an item. */
1N/Astatic int
1N/Aattrkey_removedata(void **ppTableData, void *key, void **ppData)
1N/A{
1N/A unsigned long attrkey = *((unsigned long*)key);
1N/A ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
1N/A ldapmemcacheRes *pRes = *ppHead;
1N/A ldapmemcacheRes *pPrev = NULL;
1N/A
1N/A for (; pRes; pRes = pRes->ldmemcr_htable_next) {
1N/A if (pRes->ldmemcr_crc_key == attrkey) {
1N/A if (ppData)
1N/A *ppData = (void*)pRes;
1N/A if (pPrev)
1N/A pPrev->ldmemcr_htable_next = pRes->ldmemcr_htable_next;
1N/A else
1N/A *ppHead = pRes->ldmemcr_htable_next;
1N/A pRes->ldmemcr_htable_next = NULL;
1N/A return( LDAP_SUCCESS );
1N/A }
1N/A pPrev = pRes;
1N/A }
1N/A
1N/A if (ppData)
1N/A *ppData = NULL;
1N/A
1N/A return( LDAP_NO_SUCH_OBJECT );
1N/A}
1N/A
1N/A/* Called by hash table for removing all items in the table. */
1N/Astatic void
1N/Aattrkey_clearnode(void **ppTableData, void *pData)
1N/A{
1N/A ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
1N/A ldapmemcacheRes *pRes = *ppHead;
1N/A
1N/A (void)pData;
1N/A
1N/A for (; *ppHead; pRes = *ppHead) {
1N/A ppHead = &((*ppHead)->ldmemcr_htable_next);
1N/A pRes->ldmemcr_htable_next = NULL;
1N/A }
1N/A}
1N/A
1N/A/***************************** CRC algorithm ********************************/
1N/A
1N/A/* From http://www.faqs.org/faqs/compression-faq/part1/section-25.html */
1N/A
1N/A/*
1N/A * Build auxiliary table for parallel byte-at-a-time CRC-32.
1N/A */
1N/A#define NSLDAPI_CRC32_POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */
1N/A
1N/Astatic unsigned long crc32_table[256] = {
1N/A 0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
1N/A 0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
1N/A 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, 0x4c11db70, 0x48d0c6c7,
1N/A 0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
1N/A 0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3,
1N/A 0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
1N/A 0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58, 0xbaea46ef,
1N/A 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
1N/A 0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb,
1N/A 0xceb42022, 0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
1N/A 0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
1N/A 0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
1N/A 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4,
1N/A 0x0808d07d, 0x0cc9cdca, 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
1N/A 0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08,
1N/A 0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
1N/A 0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc,
1N/A 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
1N/A 0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050,
1N/A 0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
1N/A 0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
1N/A 0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
1N/A 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, 0x4f040d56, 0x4bc510e1,
1N/A 0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
1N/A 0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5,
1N/A 0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
1N/A 0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e, 0xf5ee4bb9,
1N/A 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
1N/A 0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd,
1N/A 0xcda1f604, 0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
1N/A 0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
1N/A 0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
1N/A 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2,
1N/A 0x470cdd2b, 0x43cdc09c, 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
1N/A 0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e,
1N/A 0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
1N/A 0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a,
1N/A 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
1N/A 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676,
1N/A 0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
1N/A 0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
1N/A 0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
1N/A 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4 };
1N/A
1N/A/* Initialized first time "crc32()" is called. If you prefer, you can
1N/A * statically initialize it at compile time. [Another exercise.]
1N/A */
1N/A
1N/Astatic unsigned long
1N/Acrc32_convert(char *buf, int len)
1N/A{
1N/A char *p;
1N/A#ifdef OSF1V4D
1N/A unsigned int crc;
1N/A#else
1N/A unsigned long crc; /* FIXME: this is not 32-bits on all platforms! */
1N/A#endif /* OSF1V4D */
1N/A
1N/A crc = 0xffffffff; /* preload shift register, per CRC-32 spec */
1N/A for (p = buf; len > 0; ++p, --len)
1N/A crc = ((crc << 8) ^ crc32_table[(crc >> 24) ^ *p]) & 0xffffffff;
1N/A
1N/A return (unsigned long) ~crc; /* transmit complement, per CRC-32 spec */
1N/A}