From 887791bacf8a1b39a610734e5c27c55f88513750 Mon Sep 17 00:00:00 2001 From: Jeffrey Altman Date: Mon, 21 Nov 2011 08:42:13 -0500 Subject: [PATCH] Windows: Use Jenkins' Hash Replace the non-string hash functions with Jenkins' Hash derived hash values. Bump the cache version value because the hash function has changed. Change-Id: I9de789a48abab38ceb16e928bfc0c10e2a88747e Reviewed-on: http://gerrit.openafs.org/6102 Tested-by: BuildBot Tested-by: Jeffrey Altman Reviewed-by: Jeffrey Altman --- src/WINNT/afsd/cm_buf.c | 2 +- src/WINNT/afsd/cm_buf.h | 11 +++++------ src/WINNT/afsd/cm_callback.c | 1 + src/WINNT/afsd/cm_cell.h | 2 +- src/WINNT/afsd/cm_memmap.c | 17 +++++++++-------- src/WINNT/afsd/cm_memmap.h | 2 +- src/WINNT/afsd/cm_scache.c | 2 +- src/WINNT/afsd/cm_scache.h | 13 ++++++++----- src/WINNT/afsd/cm_utils.c | 13 +++++++++++++ src/WINNT/afsd/cm_utils.h | 3 +++ src/WINNT/afsd/cm_volume.h | 7 +++++-- 11 files changed, 48 insertions(+), 25 deletions(-) diff --git a/src/WINNT/afsd/cm_buf.c b/src/WINNT/afsd/cm_buf.c index b9ea1cb58..2377df2d2 100644 --- a/src/WINNT/afsd/cm_buf.c +++ b/src/WINNT/afsd/cm_buf.c @@ -488,7 +488,7 @@ long buf_Init(int newFile, cm_buf_ops_t *opsp, afs_uint64 nbuffers) cm_data.buf_nOrigBuffers = cm_data.buf_nbuffers; /* lower hash size to a prime number */ - cm_data.buf_hashSize = osi_PrimeLessThan((afs_uint32)(cm_data.buf_nbuffers/7 + 1)); + cm_data.buf_hashSize = cm_NextHighestPowerOf2((afs_uint32)(cm_data.buf_nbuffers/7)); /* create hash table */ memset((void *)cm_data.buf_scacheHashTablepp, 0, cm_data.buf_hashSize * sizeof(cm_buf_t *)); diff --git a/src/WINNT/afsd/cm_buf.h b/src/WINNT/afsd/cm_buf.h index 3c5e293ce..992c4abed 100644 --- a/src/WINNT/afsd/cm_buf.h +++ b/src/WINNT/afsd/cm_buf.h @@ -13,6 +13,8 @@ #define OPENAFS_WINNT_AFSD_BUF_H 1 #include +#include + #ifdef DISKCACHE95 #include "cm_diskcache.h" #endif /* DISKCACHE95 */ @@ -28,13 +30,10 @@ #define CM_BUF_CACHETYPE_VIRTUAL 2 extern int buf_cacheType; -/* force it to be signed so that mod comes out positive or 0 */ -#define BUF_HASH(fidp,offsetp) ((((fidp)->hash \ - +(offsetp)->LowPart) / cm_data.buf_blockSize) \ - % cm_data.buf_hashSize) +#define BUF_HASH(fidp, offsetp) \ + (opr_jhash((uint32_t *)(offsetp), 2, (fidp)->hash) & (cm_data.buf_hashSize - 1)) -/* another hash fn */ -#define BUF_FILEHASH(fidp) ((fidp)->hash % cm_data.buf_hashSize) +#define BUF_FILEHASH(fidp) ((fidp)->hash & (cm_data.buf_hashSize - 1)) #define CM_BUF_MAGIC ('B' | 'U' <<8 | 'F'<<16 | 'F'<<24) diff --git a/src/WINNT/afsd/cm_callback.c b/src/WINNT/afsd/cm_callback.c index aef677783..9889f7908 100644 --- a/src/WINNT/afsd/cm_callback.c +++ b/src/WINNT/afsd/cm_callback.c @@ -169,6 +169,7 @@ void cm_RevokeCallback(struct rx_call *callp, cm_cell_t * cellp, AFSFid *fidp) tfid.volume = fidp->Volume; tfid.vnode = fidp->Vnode; tfid.unique = fidp->Unique; + CM_FID_GEN_HASH(&tfid); hash = CM_SCACHE_HASH(&tfid); osi_Log3(afsd_logp, "RevokeCallback vol %u vn %u uniq %u", diff --git a/src/WINNT/afsd/cm_cell.h b/src/WINNT/afsd/cm_cell.h index d3058ff1f..4fffa78da 100644 --- a/src/WINNT/afsd/cm_cell.h +++ b/src/WINNT/afsd/cm_cell.h @@ -46,7 +46,7 @@ typedef struct cm_cell_rock { #define CM_CELL_NAME_HASH(name) (SDBMHash(name) % cm_data.cellHashTableSize) -#define CM_CELL_ID_HASH(id) ((unsigned long) id % cm_data.cellHashTableSize) +#define CM_CELL_ID_HASH(id) (opr_jhash_int(id, 0) & (cm_data.cellHashTableSize - 1)) extern void cm_InitCell(int newFile, long maxCells); diff --git a/src/WINNT/afsd/cm_memmap.c b/src/WINNT/afsd/cm_memmap.c index d43728052..c94e4a768 100644 --- a/src/WINNT/afsd/cm_memmap.c +++ b/src/WINNT/afsd/cm_memmap.c @@ -50,7 +50,7 @@ afs_uint64 ComputeSizeOfCellHT(DWORD maxcells) { afs_uint64 size; - size = osi_PrimeLessThan((afs_uint32)(maxcells/7 + 1)) * sizeof(cm_cell_t *); + size = cm_NextHighestPowerOf2((afs_uint32)(maxcells/7)) * sizeof(cm_cell_t *); return size; } @@ -58,7 +58,7 @@ afs_uint64 ComputeSizeOfVolumeHT(DWORD maxvols) { afs_uint64 size; - size = osi_PrimeLessThan((afs_uint32)(maxvols/7 + 1)) * sizeof(cm_volume_t *); + size = cm_NextHighestPowerOf2((afs_uint32)(maxvols/7)) * sizeof(cm_volume_t *); return size; } @@ -90,7 +90,7 @@ afs_uint64 ComputeSizeOfSCacheHT(DWORD stats) { afs_uint64 size; - size = osi_PrimeLessThan(stats / 2 + 1) * sizeof(cm_scache_t *);; + size = cm_NextHighestPowerOf2(stats / 2 ) * sizeof(cm_scache_t *);; return size; } @@ -114,7 +114,7 @@ afs_uint64 ComputeSizeOfDataHT(afs_uint64 cacheBlocks) { afs_uint64 size; - size = osi_PrimeLessThan((afs_uint32)(cacheBlocks/7 + 1)) * sizeof(cm_buf_t *); + size = cm_NextHighestPowerOf2((afs_uint32)(cacheBlocks/7)) * sizeof(cm_buf_t *); return size; } @@ -884,9 +884,10 @@ cm_InitMappedMemory(DWORD virtualCache, char * cachePath, DWORD stats, DWORD max cm_data.chunkSize = chunkSize; cm_data.blockSize = blockSize; cm_data.bufferSize = mappingSize; - cm_data.scacheHashTableSize = osi_PrimeLessThan(stats / 2 + 1); - cm_data.volumeHashTableSize = osi_PrimeLessThan((afs_uint32)(maxVols/7 + 1)); - cm_data.cellHashTableSize = osi_PrimeLessThan((afs_uint32)(maxCells/7 + 1)); + + cm_data.scacheHashTableSize = cm_NextHighestPowerOf2(stats / 2); + cm_data.volumeHashTableSize = cm_NextHighestPowerOf2((afs_uint32)(maxVols/7)); + cm_data.cellHashTableSize = cm_NextHighestPowerOf2((afs_uint32)(maxCells/7)); if (virtualCache) { cm_data.cacheType = CM_BUF_CACHETYPE_VIRTUAL; } else { @@ -896,7 +897,7 @@ cm_InitMappedMemory(DWORD virtualCache, char * cachePath, DWORD stats, DWORD max cm_data.buf_nbuffers = cacheBlocks; cm_data.buf_nOrigBuffers = 0; cm_data.buf_blockSize = blockSize; - cm_data.buf_hashSize = osi_PrimeLessThan((afs_uint32)(cacheBlocks/7 + 1)); + cm_data.buf_hashSize = cm_NextHighestPowerOf2((afs_uint32)(cacheBlocks/7)); cm_data.mountRootGen = 0; diff --git a/src/WINNT/afsd/cm_memmap.h b/src/WINNT/afsd/cm_memmap.h index 76316e80f..2aa247512 100644 --- a/src/WINNT/afsd/cm_memmap.h +++ b/src/WINNT/afsd/cm_memmap.h @@ -10,7 +10,7 @@ #ifndef CM_MEMMAP_H #define CM_MEMMAP_H 1 -#define CM_CONFIG_DATA_VERSION 17 +#define CM_CONFIG_DATA_VERSION 18 #define CM_CONFIG_DATA_MAGIC ('A' | 'F'<<8 | 'S'<<16 | CM_CONFIG_DATA_VERSION<<24) typedef struct cm_config_data { diff --git a/src/WINNT/afsd/cm_scache.c b/src/WINNT/afsd/cm_scache.c index 98ba61ca2..b5666ad4c 100644 --- a/src/WINNT/afsd/cm_scache.c +++ b/src/WINNT/afsd/cm_scache.c @@ -353,7 +353,7 @@ void cm_SetFid(cm_fid_t *fidp, afs_uint32 cell, afs_uint32 volume, afs_uint32 vn fidp->volume = volume; fidp->vnode = vnode; fidp->unique = unique; - fidp->hash = ((cell & 0xF) << 28) | ((volume & 0x3F) << 22) | ((vnode & 0x7FF) << 11) | (unique & 0x7FF); + CM_FID_GEN_HASH(fidp); } /* like strcmp, only for fids */ diff --git a/src/WINNT/afsd/cm_scache.h b/src/WINNT/afsd/cm_scache.h index 122f32376..3cf170db6 100644 --- a/src/WINNT/afsd/cm_scache.h +++ b/src/WINNT/afsd/cm_scache.h @@ -10,6 +10,8 @@ #ifndef OPENAFS_WINNT_AFSD_CM_SCACHE_H #define OPENAFS_WINNT_AFSD_CM_SCACHE_H 1 +#include + #define MOUNTPOINTLEN 1024 /* max path length for symlink; same as AFSPATHMAX */ typedef struct cm_fid { @@ -347,11 +349,12 @@ typedef struct cm_scache { * doesn't necessarily know the cell in the case of a multihomed server * contacting us from a mystery address. */ -#define CM_SCACHE_HASH(fidp) (((unsigned long) \ - ((fidp)->volume + \ - (fidp)->vnode + \ - (fidp)->unique)) \ - % cm_data.scacheHashTableSize) + +#define CM_FID_GEN_HASH(fidp) do { \ + (fidp)->hash = opr_jhash(&(fidp)->volume, 3, 0); \ +} while(0) + +#define CM_SCACHE_HASH(fidp) ((fidp)->hash & (cm_data.scacheHashTableSize - 1)) #include "cm_conn.h" #include "cm_buf.h" diff --git a/src/WINNT/afsd/cm_utils.c b/src/WINNT/afsd/cm_utils.c index f16d57426..0d2f7132f 100644 --- a/src/WINNT/afsd/cm_utils.c +++ b/src/WINNT/afsd/cm_utils.c @@ -1103,3 +1103,16 @@ void cm_UnixTimeFromSearchTime(time_t *unixTimep, afs_uint32 searchTime) *unixTimep = mktime(&localTm); } + +afs_uint32 +cm_NextHighestPowerOf2(afs_uint32 n) +{ + n--; + n |= n >> 1; + n |= n >> 2; + n |= n >> 4; + n |= n >> 8; + n |= n >> 16; + n++; + return n; +} diff --git a/src/WINNT/afsd/cm_utils.h b/src/WINNT/afsd/cm_utils.h index b7e27d165..d91442cf3 100644 --- a/src/WINNT/afsd/cm_utils.h +++ b/src/WINNT/afsd/cm_utils.h @@ -150,4 +150,7 @@ cm_InterlockedOr(LONG * pdest, LONG value) #endif #endif +extern afs_uint32 +cm_NextHighestPowerOf2(afs_uint32 n); + #endif /* OPENAFS_WINNT_AFSD_CM_UTILS_H */ diff --git a/src/WINNT/afsd/cm_volume.h b/src/WINNT/afsd/cm_volume.h index ff0589abf..b29d92915 100644 --- a/src/WINNT/afsd/cm_volume.h +++ b/src/WINNT/afsd/cm_volume.h @@ -10,6 +10,8 @@ #ifndef OPENAFS_WINNT_AFSD_CM_VOLUME_H #define OPENAFS_WINNT_AFSD_CM_VOLUME_H 1 +#include + #define VL_MAXNAMELEN 65 #define CM_VOLUME_MAGIC ('V' | 'O' <<8 | 'L'<<16 | 'M'<<24) @@ -82,8 +84,9 @@ extern long cm_FindVolumeByID(struct cm_cell *cellp, afs_uint32 volumeID, * doesn't necessarily know the cell in the case of a multihomed server * contacting us from a mystery address. */ -#define CM_VOLUME_ID_HASH(volid) ((unsigned long) volid \ - % cm_data.volumeHashTableSize) + +#define CM_VOLUME_ID_HASH(volid) \ + (opr_jhash_int((volid), 0) & (cm_data.volumeHashTableSize - 1)) #define CM_VOLUME_NAME_HASH(name) (SDBMHash(name) % cm_data.volumeHashTableSize) -- 2.39.5