Windows: Use Jenkins' Hash
authorJeffrey Altman <jaltman@your-file-system.com>
Mon, 21 Nov 2011 13:42:13 +0000 (08:42 -0500)
committerJeffrey Altman <jaltman@secure-endpoints.com>
Tue, 22 Nov 2011 21:48:37 +0000 (13:48 -0800)
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 <buildbot@rampaginggeek.com>
Tested-by: Jeffrey Altman <jaltman@secure-endpoints.com>
Reviewed-by: Jeffrey Altman <jaltman@secure-endpoints.com>

src/WINNT/afsd/cm_buf.c
src/WINNT/afsd/cm_buf.h
src/WINNT/afsd/cm_callback.c
src/WINNT/afsd/cm_cell.h
src/WINNT/afsd/cm_memmap.c
src/WINNT/afsd/cm_memmap.h
src/WINNT/afsd/cm_scache.c
src/WINNT/afsd/cm_scache.h
src/WINNT/afsd/cm_utils.c
src/WINNT/afsd/cm_utils.h
src/WINNT/afsd/cm_volume.h

index b9ea1cb..2377df2 100644 (file)
@@ -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 *));
index 3c5e293..992c4ab 100644 (file)
@@ -13,6 +13,8 @@
 #define OPENAFS_WINNT_AFSD_BUF_H 1
 
 #include <osi.h>
+#include <opr/jhash.h>
+
 #ifdef DISKCACHE95
 #include "cm_diskcache.h"
 #endif /* DISKCACHE95 */
 #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)
 
index aef6777..9889f79 100644 (file)
@@ -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",
index d3058ff..4fffa78 100644 (file)
@@ -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);
 
index d437280..c94e4a7 100644 (file)
@@ -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;
 
index 76316e8..2aa2475 100644 (file)
@@ -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 {
index 98ba61c..b5666ad 100644 (file)
@@ -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 */
index 122f323..3cf170d 100644 (file)
@@ -10,6 +10,8 @@
 #ifndef OPENAFS_WINNT_AFSD_CM_SCACHE_H
 #define OPENAFS_WINNT_AFSD_CM_SCACHE_H 1
 
+#include <opr/jhash.h>
+
 #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"
index f16d574..0d2f713 100644 (file)
@@ -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;
+}
index b7e27d1..d91442c 100644 (file)
@@ -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 */
index ff0589a..b29d929 100644 (file)
@@ -10,6 +10,8 @@
 #ifndef OPENAFS_WINNT_AFSD_CM_VOLUME_H
 #define OPENAFS_WINNT_AFSD_CM_VOLUME_H 1
 
+#include <opr/jhash.h>
+
 #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)