[autofs] [PATCH 1/4] Make hash table scale to thousands of entries

[Valerie Aurora Henson]

From: Paul Wankadia <jun...@google.com>
Signed-off-by: Valerie Aurora Henson <vaur...@redhat.com>
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)

diff --git a/include/automount.h b/include/automount.h
index 1ba0d3c..2a082b5 100644
--- a/include/automount.h
+++ b/include/automount.h
@@ -126,7 +126,7 @@ struct autofs_point;
 #define CHE_DUPLICATE  0x0020
 #define CHE_UNAVAIL    0x0040
 
-#define HASHSIZE               77
+#define HASHSIZE               4096
 #define NEGATIVE_TIMEOUT       10
 #define UMOUNT_RETRIES         8
 #define EXPIRE_RETRIES         3
diff --git a/lib/cache.c b/lib/cache.c
index ce47e04..36b8294 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -281,20 +281,27 @@ struct mapent_cache *cache_init_null_cache(struct master 
*master)
        return mc;
 }
 
-static unsigned int hash(const char *key)
+static u_int32_t hash(const char *key)
 {
-       unsigned long hashval;
+       u_int32_t hashval;
        char *s = (char *) key;
 
-       for (hashval = 0; *s != '\0';)
-               hashval += *s++;
+       for (hashval = 0; *s != '\0';) {
+               hashval += (unsigned char) *s++;
+               hashval += (hashval << 10);
+               hashval ^= (hashval >> 6);
+       }
+
+       hashval += (hashval << 3);
+       hashval ^= (hashval >> 11);
+       hashval += (hashval << 15);
 
        return hashval % HASHSIZE;
 }
 
-static unsigned int ino_hash(dev_t dev, ino_t ino)
+static u_int32_t ino_hash(dev_t dev, ino_t ino)
 {
-       unsigned long hashval;
+       u_int32_t hashval;
 
        hashval = dev + ino;
 
@@ -303,7 +310,7 @@ static unsigned int ino_hash(dev_t dev, ino_t ino)
 
 int cache_set_ino_index(struct mapent_cache *mc, const char *key, dev_t dev, 
ino_t ino)
 {
-       unsigned int ino_index = ino_hash(dev, ino);
+       u_int32_t ino_index = ino_hash(dev, ino);
        struct mapent *me;
 
        me = cache_lookup_distinct(mc, key);
@@ -325,7 +332,7 @@ struct mapent *cache_lookup_ino(struct mapent_cache *mc, 
dev_t dev, ino_t ino)
 {
        struct mapent *me = NULL;
        struct list_head *head, *p;
-       unsigned int ino_index;
+       u_int32_t ino_index;
 
        ino_index_lock(mc);
        ino_index = ino_hash(dev, ino);
@@ -371,7 +378,7 @@ struct mapent *cache_lookup_first(struct mapent_cache *mc)
 struct mapent *cache_lookup_next(struct mapent_cache *mc, struct mapent *me)
 {
        struct mapent *this;
-       unsigned long hashval;
+       u_int32_t hashval;
        unsigned int i;
 
        if (!me)
@@ -532,7 +539,7 @@ int cache_add(struct mapent_cache *mc, struct map_source 
*ms, const char *key, c
 {
        struct mapent *me, *existing = NULL;
        char *pkey, *pent;
-       unsigned int hashval = hash(key);
+       u_int32_t hashval = hash(key);
        int status;
 
        me = (struct mapent *) malloc(sizeof(struct mapent));
@@ -752,7 +759,7 @@ int cache_update(struct mapent_cache *mc, struct map_source 
*ms, const char *key
 int cache_delete(struct mapent_cache *mc, const char *key)
 {
        struct mapent *me = NULL, *pred;
-       unsigned int hashval = hash(key);
+       u_int32_t hashval = hash(key);
        int status, ret = CHE_OK;
        char *this;
 
-- 
1.6.0.4

_______________________________________________
autofs mailing list
autofs@linux.kernel.org
http://linux.kernel.org/mailman/listinfo/autofs