autofs-5.0.4 - make hash table scale to thousands of entries

From: Valerie Aurora Henson <vaurora@redhat.com>

Originally written by Paul Wankadia <junyer@google.com>.

The autofs cache lookup performs poorly for large maps.

The additive hashing algorithm used by autofs results in a clustering
of hash values around the average hash chain size. It is biased toward
a small range of hash indexes which becomes worse as the hash table size
increases.

Simple testing shows that the "One-at-a-time" hash function (implemented
by this patch) gives a much better distribution of hash indexes as table
size increases.

The only change made to the original patch is to make the hash table size
configurable with a default somewhat larger than it is currently.
---

 include/automount.h            |    2 -
 include/defaults.h             |    3 ++
 lib/cache.c                    |   47 +++++++++++++++++++++++------------------
 lib/defaults.c                 |   16 +++++++++++++
 redhat/autofs.sysconfig.in     |    6 +++++
 samples/autofs.conf.default.in |    6 +++++
 6 files changed, 58 insertions(+), 22 deletions(-)


--- autofs-5.0.1.orig/include/automount.h
+++ autofs-5.0.1/include/automount.h
@@ -124,7 +124,7 @@ struct autofs_point; 
 #define CHE_DUPLICATE	0x0020
 #define CHE_UNAVAIL	0x0040
 
-#define HASHSIZE		77
+#define NULL_MAP_HASHSIZE	64
 #define NEGATIVE_TIMEOUT	10
 #define UMOUNT_RETRIES		8
 #define EXPIRE_RETRIES		3
--- autofs-5.0.1.orig/include/defaults.h
+++ autofs-5.0.1/include/defaults.h
@@ -40,6 +40,8 @@
 #define DEFAULT_APPEND_OPTIONS		1
 #define DEFAULT_AUTH_CONF_FILE		AUTOFS_MAP_DIR "/autofs_ldap_auth.conf"
 
+#define DEFAULT_MAP_HASH_TABLE_SIZE	1024
+
 struct ldap_schema;
 struct ldap_searchdn;
 
@@ -62,6 +64,7 @@ void defaults_free_searchdns(struct ldap
 unsigned int defaults_get_append_options(void);
 unsigned int defaults_get_umount_wait(void);
 const char *defaults_get_auth_conf_file(void);
+unsigned int defaults_get_map_hash_table_size(void);
 
 #endif
 
--- autofs-5.0.1.orig/lib/cache.c
+++ autofs-5.0.1/lib/cache.c
@@ -177,7 +177,7 @@ struct mapent_cache *cache_init(struct a
 	if (!mc)
 		return NULL;
 
-	mc->size = HASHSIZE;
+	mc->size = defaults_get_map_hash_table_size();
 
 	mc->hash = malloc(mc->size * sizeof(struct entry *));
 	if (!mc->hash) {
@@ -228,7 +228,7 @@ struct mapent_cache *cache_init_null_cac
 	if (!mc)
 		return NULL;
 
-	mc->size = HASHSIZE;
+	mc->size = NULL_MAP_HASHSIZE;
 
 	mc->hash = malloc(mc->size * sizeof(struct entry *));
 	if (!mc->hash) {
@@ -266,29 +266,36 @@ struct mapent_cache *cache_init_null_cac
 	return mc;
 }
 
-static unsigned int hash(const char *key)
+static u_int32_t hash(const char *key, unsigned int size)
 {
-	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;
+	return hashval % size;
 }
 
-static unsigned int ino_hash(dev_t dev, ino_t ino)
+static u_int32_t ino_hash(dev_t dev, ino_t ino, unsigned int size)
 {
-	unsigned long hashval;
+	u_int32_t hashval;
 
 	hashval = dev + ino;
 
-	return hashval % HASHSIZE;
+	return hashval % size;
 }
 
 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, mc->size);
 	struct mapent *me;
 
 	me = cache_lookup_distinct(mc, key);
@@ -310,10 +317,10 @@ struct mapent *cache_lookup_ino(struct m
 {
 	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);
+	ino_index = ino_hash(dev, ino, mc->size);
 	head = &mc->ino_index[ino_index];
 
 	list_for_each(p, head) {
@@ -356,7 +363,7 @@ struct mapent *cache_lookup_first(struct
 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)
@@ -372,7 +379,7 @@ struct mapent *cache_lookup_next(struct 
 		return this;
 	}
 
-	hashval = hash(me->key) + 1;
+	hashval = hash(me->key, mc->size) + 1;
 	if (hashval < mc->size) {
 		for (i = (unsigned int) hashval; i < mc->size; i++) {
 			this = mc->hash[i];
@@ -420,7 +427,7 @@ struct mapent *cache_lookup(struct mapen
 	if (!key)
 		return NULL;
 
-	for (me = mc->hash[hash(key)]; me != NULL; me = me->next) {
+	for (me = mc->hash[hash(key, mc->size)]; me != NULL; me = me->next) {
 		if (strcmp(key, me->key) == 0)
 			goto done;
 	}
@@ -433,7 +440,7 @@ struct mapent *cache_lookup(struct mapen
 			goto done;
 		}
 
-		for (me = mc->hash[hash("*")]; me != NULL; me = me->next)
+		for (me = mc->hash[hash("*", mc->size)]; me != NULL; me = me->next)
 			if (strcmp("*", me->key) == 0)
 				goto done;
 	}
@@ -449,7 +456,7 @@ struct mapent *cache_lookup_distinct(str
 	if (!key)
 		return NULL;
 
-	for (me = mc->hash[hash(key)]; me != NULL; me = me->next) {
+	for (me = mc->hash[hash(key, mc->size)]; me != NULL; me = me->next) {
 		if (strcmp(key, me->key) == 0)
 			return me;
 	}
@@ -517,7 +524,7 @@ int cache_add(struct mapent_cache *mc, s
 {
 	struct mapent *me, *existing = NULL;
 	char *pkey, *pent;
-	unsigned int hashval = hash(key);
+	u_int32_t hashval = hash(key, mc->size);
 	int status;
 
 	me = (struct mapent *) malloc(sizeof(struct mapent));
@@ -736,7 +743,7 @@ int cache_update(struct mapent_cache *mc
 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, mc->size);
 	int status, ret = CHE_OK;
 	char *this;
 
--- autofs-5.0.1.orig/lib/defaults.c
+++ autofs-5.0.1/lib/defaults.c
@@ -48,6 +48,8 @@
 #define ENV_UMOUNT_WAIT			"UMOUNT_WAIT"
 #define ENV_AUTH_CONF_FILE		"AUTH_CONF_FILE"
 
+#define ENV_MAP_HASH_TABLE_SIZE		"MAP_HASH_TABLE_SIZE"
+
 static const char *default_master_map_name = DEFAULT_MASTER_MAP_NAME;
 static const char *default_auth_conf_file  = DEFAULT_AUTH_CONF_FILE;
 
@@ -322,7 +324,8 @@ unsigned int defaults_read_config(unsign
 		    check_set_config_value(key, ENV_NAME_VALUE_ATTR, value, to_syslog) ||
 		    check_set_config_value(key, ENV_APPEND_OPTIONS, value, to_syslog) ||
 		    check_set_config_value(key, ENV_UMOUNT_WAIT, value, to_syslog) ||
-		    check_set_config_value(key, ENV_AUTH_CONF_FILE, value, to_syslog))
+		    check_set_config_value(key, ENV_AUTH_CONF_FILE, value, to_syslog) ||
+		    check_set_config_value(key, ENV_MAP_HASH_TABLE_SIZE, value, to_syslog))
 			;
 	}
 
@@ -671,3 +674,14 @@ const char *defaults_get_auth_conf_file(
 	return (const char *) cf;
 }
 
+unsigned int defaults_get_map_hash_table_size(void)
+{
+	long size;
+
+	size = get_env_number(ENV_MAP_HASH_TABLE_SIZE);
+	if (size < 0)
+		size = DEFAULT_MAP_HASH_TABLE_SIZE;
+
+	return (unsigned int) size;
+}
+
--- autofs-5.0.1.orig/redhat/autofs.sysconfig.in
+++ autofs-5.0.1/redhat/autofs.sysconfig.in
@@ -89,6 +89,12 @@ BROWSE_MODE="no"
 #
 #AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
 #
+# MAP_HASH_TABLE_SIZE - set the map cache hash table size.
+# 			Should be a power of 2 with a ratio roughly
+# 			between 1:10 and 1:20 for each map.
+#
+#MAP_HASH_TABLE_SIZE=1024
+#
 # General global options
 #
 #OPTIONS=""
--- autofs-5.0.1.orig/samples/autofs.conf.default.in
+++ autofs-5.0.1/samples/autofs.conf.default.in
@@ -89,6 +89,12 @@ BROWSE_MODE="no"
 #
 #AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
 #
+# MAP_HASH_TABLE_SIZE - set the map cache hash table size.
+# 			Should be a power of 2 with a ratio roughly
+# 			between 1:10 and 1:20 for each map.
+#
+#MAP_HASH_TABLE_SIZE=1024
+#
 # General global options
 #
 #OPTIONS=""