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