Skip to contentSkip to conversation

autofs scaling and cleanup patches

PATCH In review Valerie Aurora Henson 4 participants 66 messages Jan 9, 2009 – Jan 19, 2009

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover autofs scaling and cleanup patches

This is a small collection of patches generated from discussions with Google folks. The first makes the mount entry cache scale to thousands of entries. The second is prep for the next patch; it just cleans up use of fixed buffer sizes so that it's easier to tell what's going on. The third removes some instances of alloca() - I had the help of Coccinelle on this one. The fourth fixes an include to use the userland include instead of the kernel include.

Valerie Aurora Henson (4):
Make hash table scale to thousands of entries Make MAX_ERR_BUF and PARSE_MAX_BUF use easier to audit Easy alloca() replacements
Replace <linux/string.h> with <string.h>

 daemon/automount.c             |    6 ++--
 daemon/direct.c                |    8 ++----
 daemon/flag.c                  |   12 +++++-----
 daemon/indirect.c              |    8 ++----
 daemon/module.c                |   42 +++++++++------------------------
 include/automount.h            |    2 +-
 include/linux/auto_dev-ioctl.h |    2 +-
 lib/cache.c                    |   49 +++++++++++++++++++--------------------
 lib/cat_path.c                 |    1 -
 modules/lookup_ldap.c          |   49 ++++++++++++++++++----------------------
 modules/lookup_nisplus.c       |   22 ++++++++++++++----
 modules/mount_autofs.c         |    1 -
 modules/mount_bind.c           |    7 +----
 modules/mount_changer.c        |    5 +---
 modules/mount_ext2.c           |    5 +---
 modules/mount_generic.c        |    5 +---
 16 files changed, 97 insertions(+), 127 deletions(-)
#1 lore raw

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

From: Paul Wankadia <[email protected]>

---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +18 -11
index ce47e04..36b8294 100644
@@ -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;
 
Signature · 1 line
1.6.0.4
#2 lore raw

PATCH 2/4 Make MAX_ERR_BUF and PARSE_MAX_BUF use easier to audit

---
 modules/lookup_ldap.c |   49 ++++++++++++++++++++++---------------------------
 1 files changed, 22 insertions(+), 27 deletions(-)
modules/lookup_ldap.c +22 -27
index 42c3235..0ef7bcf 100644
@@ -275,7 +275,7 @@ LDAP *init_ldap_connection(unsigned logopt, const char *uri, struct lookup_conte
 
 static int get_query_dn(unsigned logopt, LDAP *ldap, struct lookup_context *ctxt, const char *class, const char *key)
 {
-	char buf[PARSE_MAX_BUF];
+	char buf[MAX_ERR_BUF];
 	char *query, *dn, *qdn;
 	LDAPMessage *result, *e;
 	struct ldap_searchdn *sdns = NULL;
@@ -299,7 +299,7 @@ static int get_query_dn(unsigned logopt, LDAP *ldap, struct lookup_context *ctxt
 
 	query = alloca(l);
 	if (query == NULL) {
-		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
+		char *estr = strerror_r(errno, buf, sizeof(buf));
 		crit(logopt, MODPREFIX "alloca: %s", estr);
 		return NSS_STATUS_UNAVAIL;
 	}
@@ -1074,7 +1074,7 @@ static int parse_server_string(unsigned logopt, const char *url, struct lookup_c
 			}
 			if (!tmp) {
 				char *estr;
-				estr = strerror_r(errno, buf, MAX_ERR_BUF);
+				estr = strerror_r(errno, buf, sizeof(buf));
 				logerr(MODPREFIX "malloc: %s", estr);
 				return 0;
 			}
@@ -1096,7 +1096,7 @@ static int parse_server_string(unsigned logopt, const char *url, struct lookup_c
 			tmp = malloc(l + 1);
 			if (!tmp) {
 				char *estr;
-				estr = strerror_r(errno, buf, MAX_ERR_BUF);
+				estr = strerror_r(errno, buf, sizeof(buf));
 				crit(logopt, MODPREFIX "malloc: %s", estr);
 				return 0;
 			}
@@ -1131,7 +1131,7 @@ static int parse_server_string(unsigned logopt, const char *url, struct lookup_c
 		/* Isolate the server's name. */
 		if (!tmp) {
 			char *estr;
-			estr = strerror_r(errno, buf, MAX_ERR_BUF);
+			estr = strerror_r(errno, buf, sizeof(buf));
 			logerr(MODPREFIX "malloc: %s", estr);
 			return 0;
 		}
@@ -1172,7 +1172,7 @@ static int parse_server_string(unsigned logopt, const char *url, struct lookup_c
 				ctxt->mapname = map;
 			else {
 				char *estr;
-				estr = strerror_r(errno, buf, MAX_ERR_BUF);
+				estr = strerror_r(errno, buf, sizeof(buf));
 				logerr(MODPREFIX "malloc: %s", estr);
 				if (ctxt->server)
 					free(ctxt->server);
@@ -1183,7 +1183,7 @@ static int parse_server_string(unsigned logopt, const char *url, struct lookup_c
 			base = malloc(l + 1);
 			if (!base) {
 				char *estr;
-				estr = strerror_r(errno, buf, MAX_ERR_BUF);
+				estr = strerror_r(errno, buf, sizeof(buf));
 				logerr(MODPREFIX "malloc: %s", estr);
 				if (ctxt->server)
 					free(ctxt->server);
@@ -1197,7 +1197,7 @@ static int parse_server_string(unsigned logopt, const char *url, struct lookup_c
 		char *map = malloc(l + 1);
 		if (!map) {
 			char *estr;
-			estr = strerror_r(errno, buf, MAX_ERR_BUF);
+			estr = strerror_r(errno, buf, sizeof(buf));
 			logerr(MODPREFIX "malloc: %s", estr);
 			if (ctxt->server)
 				free(ctxt->server);
@@ -1310,7 +1310,7 @@ int lookup_init(const char *mapfmt, int argc, const char *const *argv, void **co
 	/* If we can't build a context, bail. */
 	ctxt = malloc(sizeof(struct lookup_context));
 	if (!ctxt) {
-		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
+		char *estr = strerror_r(errno, buf, sizeof(buf));
 		logerr(MODPREFIX "malloc: %s", estr);
 		return 1;
 	}
@@ -1411,8 +1411,9 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 	unsigned int timeout = master->default_timeout;
 	unsigned int logging = master->default_logging;
 	unsigned int logopt = master->logopt;
-	int rv, l, count, blen;
-	char buf[PARSE_MAX_BUF];
+	int rv, l, count;
+	char buf[MAX_ERR_BUF];
+	char parse_buf[PARSE_MAX_BUF];
 	char *query;
 	LDAPMessage *result, *e;
 	char *class, *info, *entry;
@@ -1434,7 +1435,7 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 
 	query = alloca(l);
 	if (query == NULL) {
-		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
+		char *estr = strerror_r(errno, buf, sizeof(buf));
 		logerr(MODPREFIX "alloca: %s", estr);
 		return NSS_STATUS_UNAVAIL;
 	}
@@ -1524,18 +1525,12 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 			goto next;
 		}
 
-		blen = strlen(*keyValue) + 1 + strlen(*values) + 2;
-		if (blen > PARSE_MAX_BUF) {
+		if (snprintf(parse_buf, sizeof(parse_buf), "%s %s",
+			     *keyValue, *values) > sizeof(parse_buf)) {
 			error(logopt, MODPREFIX "map entry too long");
 			ldap_value_free(values);
 			goto next;
 		}
-		memset(buf, 0, PARSE_MAX_BUF);
-
-		strcpy(buf, *keyValue);
-		strcat(buf, " ");
-		strcat(buf, *values);
-
 		master_parse_entry(buf, timeout, logging, age);
 next:
 		ldap_value_free(keyValue);
@@ -1553,7 +1548,7 @@ static int get_percent_decoded_len(const char *name)
 {
 	int escapes = 0;
 	int escaped = 0;
-	char *tmp = name;
+	const char *tmp = name;
 	int look_for_close = 0;
 
 	while (*tmp) {
@@ -2052,7 +2047,7 @@ static int do_get_entries(struct ldap_search_params *sp, struct map_source *sour
 				mapent = malloc(v_len + 1);
 				if (!mapent) {
 					char *estr;
-					estr = strerror_r(errno, buf, MAX_ERR_BUF);
+					estr = strerror_r(errno, buf, sizeof(buf));
 					logerr(MODPREFIX "malloc: %s", estr);
 					ldap_value_free_len(bvValues);
 					goto next;
@@ -2072,7 +2067,7 @@ static int do_get_entries(struct ldap_search_params *sp, struct map_source *sour
 					mapent_len = new_size;
 				} else {
 					char *estr;
-					estr = strerror_r(errno, buf, MAX_ERR_BUF);
+					estr = strerror_r(errno, buf, sizeof(buf));
 					logerr(MODPREFIX "realloc: %s", estr);
 				}
 			}
@@ -2173,7 +2168,7 @@ static int read_one_map(struct autofs_point *ap,
 
 	sp.query = alloca(l);
 	if (sp.query == NULL) {
-		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
+		char *estr = strerror_r(errno, buf, sizeof(buf));
 		logerr(MODPREFIX "malloc: %s", estr);
 		return NSS_STATUS_UNAVAIL;
 	}
@@ -2327,7 +2322,7 @@ static int lookup_one(struct autofs_point *ap,
 
 	query = alloca(l);
 	if (query == NULL) {
-		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
+		char *estr = strerror_r(errno, buf, sizeof(buf));
 		crit(ap->logopt, MODPREFIX "malloc: %s", estr);
 		if (enc_len1) {
 			free(enc_key1);
@@ -2499,7 +2494,7 @@ static int lookup_one(struct autofs_point *ap,
 				mapent = malloc(v_len + 1);
 				if (!mapent) {
 					char *estr;
-					estr = strerror_r(errno, buf, MAX_ERR_BUF);
+					estr = strerror_r(errno, buf, sizeof(buf));
 					logerr(MODPREFIX "malloc: %s", estr);
 					ldap_value_free_len(bvValues);
 					goto next;
@@ -2519,7 +2514,7 @@ static int lookup_one(struct autofs_point *ap,
 					mapent_len = new_size;
 				} else {
 					char *estr;
-					estr = strerror_r(errno, buf, MAX_ERR_BUF);
+					estr = strerror_r(errno, buf, sizeof(buf));
 					logerr(MODPREFIX "realloc: %s", estr);
 				}
 			}
Signature · 1 line
1.6.0.4
#3 lore raw

PATCH 3/4 Easy alloca() replacements

---
 daemon/automount.c       |    6 +++---
 daemon/direct.c          |    8 +++-----
 daemon/flag.c            |   12 ++++++------
 daemon/indirect.c        |    8 +++-----
 daemon/module.c          |   42 ++++++++++++------------------------------
 lib/cache.c              |   20 ++++++--------------
 lib/cat_path.c           |    1 -
 modules/lookup_nisplus.c |   22 +++++++++++++++++-----
 modules/mount_autofs.c   |    1 -
 modules/mount_bind.c     |    7 ++-----
 modules/mount_changer.c  |    5 +----
 modules/mount_ext2.c     |    5 +----
 modules/mount_generic.c  |    5 +----
 13 files changed, 55 insertions(+), 87 deletions(-)
daemon/automount.c +3 -3
index 6f078c1..61bbc80 100644
@@ -124,8 +124,8 @@ static int do_mkdir(const char *parent, const char *path, mode_t mode)
 
 int mkdir_path(const char *path, mode_t mode)
 {
-	char *buf = alloca(strlen(path) + 1);
-	char *parent = alloca(strlen(path) + 1);
+	char buf[PATH_MAX];
+	char parent[PATH_MAX];
 	const char *cp = path, *lcp = path;
 	char *bp = buf, *pp = parent;
 
@@ -160,7 +160,7 @@ int mkdir_path(const char *path, mode_t mode)
 int rmdir_path(struct autofs_point *ap, const char *path, dev_t dev)
 {
 	int len = strlen(path);
-	char *buf = alloca(len + 1);
+	char buf[PATH_MAX];
 	char *cp;
 	int first = 1;
 	struct stat st;
daemon/direct.c +3 -5
index 98fcc07..94216ba 100644
@@ -742,11 +742,9 @@ int mount_autofs_offset(struct autofs_point *ap, struct mapent *me, const char *
 
 	type = ap->entry->maps->type;
 	if (type && !strcmp(ap->entry->maps->type, "hosts")) {
-		char *tmp = alloca(7);
-		if (tmp) {
-			strcpy(tmp, "-hosts");
-			map_name = (const char *) tmp;
-		}
+		char tmp[7];
+		strcpy(tmp, "-hosts");
+		map_name = (const char *) tmp;
 	} else
 		map_name = me->mc->map->argv[0];
 
daemon/flag.c +6 -6
index d8ca61b..5c4f0c2 100644
@@ -25,10 +25,10 @@
 #include <time.h>
 #include <unistd.h>
 #include <string.h>
-#include <alloca.h>
 #include <stdio.h>
 #include <signal.h>
 #include <errno.h>
+#include <limits.h>
 
 #define MAX_PIDSIZE	20
 #define FLAG_FILE	AUTOFS_FLAG_DIR "/autofs-running"
@@ -113,12 +113,12 @@ void release_flag_file(void)
 /* * Try to create flag file */
 int aquire_flag_file(void)
 {
-	char *linkf;
-	int len;
+	char linkf[PATH_MAX];
 
-	len = strlen(FLAG_FILE) + MAX_PIDSIZE;
-	linkf = alloca(len + 1);
-	snprintf(linkf, len, "%s.%d", FLAG_FILE, getpid());
+	if (snprintf(linkf, sizeof(linkf), "%s.%d", FLAG_FILE, getpid()) >
+	    sizeof(linkf))
+		/* Didn't acquire it */
+		return 0;
 
 	/*
 	 * Repeat until it was us who made the link or we find the
daemon/indirect.c +3 -5
index 1232810..31713fd 100644
@@ -144,11 +144,9 @@ static int do_mount_autofs_indirect(struct autofs_point *ap, const char *root)
 
 	type = ap->entry->maps->type;
 	if (type && !strcmp(ap->entry->maps->type, "hosts")) {
-		char *tmp = alloca(7);
-		if (tmp) {
-			strcpy(tmp, "-hosts");
-			map_name = (const char *) tmp;
-		}
+		char tmp[7];
+		strcpy(tmp, "-hosts");
+		map_name = (const char *) tmp;
 	} else
 		map_name = ap->entry->maps->argv[0];
 
daemon/module.c +12 -30

105 lines not on this page · raw message

lib/cache.c +6 -14
index 36b8294..bc2c722 100644
@@ -484,27 +484,19 @@ struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s
 {
 	struct list_head *p;
 	struct mapent *this;
-	int plen = strlen(prefix);
-	char *o_key;
+	char o_key[KEY_MAX_LEN];
 
 	/* root offset duplicates "/" */
-	if (plen > 1) {
-		o_key = alloca(plen + strlen(offset) + 1);
-		strcpy(o_key, prefix);
-		strcat(o_key, offset);
-	} else {
-		o_key = alloca(strlen(offset) + 1);
-		strcpy(o_key, offset);
-	}
+	if (snprintf(o_key, sizeof(o_key), "%s%s", prefix, offset) >
+	    sizeof(o_key))
+		return NULL;
 
 	list_for_each(p, head) {
 		this = list_entry(p, struct mapent, multi_list);
 		if (!strcmp(&this->key[start], o_key))
-			goto done;
+			return this;
 	}
-	this = NULL;
-done:
-	return this;
+	return NULL;
 }
 
 /* cache must be read locked by caller */
lib/cat_path.c +0 -1
index 576b424..60669db 100644
@@ -12,7 +12,6 @@
  *
  * ----------------------------------------------------------------------- */
 
-#include <alloca.h>
 #include <string.h>
 #include <limits.h>
 #include <ctype.h>
modules/lookup_nisplus.c +17 -5
index f15465f..279a8d6 100644
@@ -93,7 +93,7 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 	int cur_state, len;
 
 	pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cur_state);
-	tablename = alloca(strlen(ctxt->mapname) + strlen(ctxt->domainname) + 20);
+	tablename = malloc(strlen(ctxt->mapname) + strlen(ctxt->domainname) + 20);
 	if (!tablename) {
 		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
 		logerr(MODPREFIX "alloca: %s", estr);
@@ -108,6 +108,7 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 		nis_freeresult(result);
 		crit(logopt,
 		     MODPREFIX "couldn't locate nis+ table %s", ctxt->mapname);
+		free(tablename);
 		pthread_setcancelstate(cur_state, NULL);
 		return NSS_STATUS_NOTFOUND;
 	}
@@ -119,6 +120,7 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 		nis_freeresult(result);
 		crit(logopt,
 		     MODPREFIX "couldn't enumrate nis+ map %s", ctxt->mapname);
+		free(tablename);
 		pthread_setcancelstate(cur_state, NULL);
 		return NSS_STATUS_UNAVAIL;
 	}
@@ -156,6 +158,7 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 	}
 
 	nis_freeresult(result);
+	free(tablename);
 	pthread_setcancelstate(cur_state, NULL);
 
 	return NSS_STATUS_SUCCESS;
@@ -181,7 +184,8 @@ int lookup_read_map(struct autofs_point *ap, time_t age, void *context)
 	mc = source->mc;
 
 	pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cur_state);
-	tablename = alloca(strlen(ctxt->mapname) + strlen(ctxt->domainname) + 20);
+	tablename = alloca(strlen(ctxt->mapname) + strlen(ctxt->domainname) +
+			   20);
 	if (!tablename) {
 		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
 		logerr(MODPREFIX "alloca: %s", estr);
@@ -196,6 +200,7 @@ int lookup_read_map(struct autofs_point *ap, time_t age, void *context)
 		nis_freeresult(result);
 		crit(ap->logopt,
 		     MODPREFIX "couldn't locate nis+ table %s", ctxt->mapname);
+		free(tablename);
 		pthread_setcancelstate(cur_state, NULL);
 		return NSS_STATUS_NOTFOUND;
 	}
@@ -207,6 +212,7 @@ int lookup_read_map(struct autofs_point *ap, time_t age, void *context)
 		nis_freeresult(result);
 		crit(ap->logopt,
 		     MODPREFIX "couldn't enumrate nis+ map %s", ctxt->mapname);
+		free(tablename);
 		pthread_setcancelstate(cur_state, NULL);
 		return NSS_STATUS_UNAVAIL;
 	}
@@ -246,6 +252,7 @@ int lookup_read_map(struct autofs_point *ap, time_t age, void *context)
 
 	source->age = age;
 
+	free(tablename);
 	pthread_setcancelstate(cur_state, NULL);
 
 	return NSS_STATUS_SUCCESS;
@@ -272,8 +279,8 @@ static int lookup_one(struct autofs_point *ap,
 	mc = source->mc;
 
 	pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cur_state);
-	tablename = alloca(strlen(key) +
-			strlen(ctxt->mapname) + strlen(ctxt->domainname) + 20);
+	tablename = malloc(strlen(key) + strlen(ctxt->mapname) +
+			   strlen(ctxt->domainname) + 20);
 	if (!tablename) {
 		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
 		logerr(MODPREFIX "alloca: %s", estr);
@@ -287,6 +294,7 @@ static int lookup_one(struct autofs_point *ap,
 	if (result->status != NIS_SUCCESS && result->status != NIS_S_SUCCESS) {
 		nis_error rs = result->status;
 		nis_freeresult(result);
+		free(tablename);
 		pthread_setcancelstate(cur_state, NULL);
 		if (rs == NIS_NOTFOUND ||
 		    rs == NIS_S_NOTFOUND ||
@@ -304,6 +312,7 @@ static int lookup_one(struct autofs_point *ap,
 	cache_unlock(mc);
 
 	nis_freeresult(result);
+	free(tablename);
 	pthread_setcancelstate(cur_state, NULL);
 
 	return ret;
@@ -328,7 +337,8 @@ static int lookup_wild(struct autofs_point *ap, struct lookup_context *ctxt)
 	mc = source->mc;
 
 	pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cur_state);
-	tablename = alloca(strlen(ctxt->mapname) + strlen(ctxt->domainname) + 20);
+	tablename = malloc(strlen(ctxt->mapname) + strlen(ctxt->domainname) +
+			   20);
 	if (!tablename) {
 		char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
 		logerr(MODPREFIX "alloca: %s", estr);
@@ -342,6 +352,7 @@ static int lookup_wild(struct autofs_point *ap, struct lookup_context *ctxt)
 	if (result->status != NIS_SUCCESS && result->status != NIS_S_SUCCESS) {
 		nis_error rs = result->status;
 		nis_freeresult(result);
+		free(tablename);
 		pthread_setcancelstate(cur_state, NULL);
 		if (rs == NIS_NOTFOUND ||
 		    rs == NIS_S_NOTFOUND ||
@@ -358,6 +369,7 @@ static int lookup_wild(struct autofs_point *ap, struct lookup_context *ctxt)
 	cache_unlock(mc);
 
 	nis_freeresult(result);
+	free(tablename);
 	pthread_setcancelstate(cur_state, NULL);
 
 	return ret;
modules/mount_autofs.c +0 -1
index eb63d8e..effa4fc 100644
@@ -20,7 +20,6 @@
 #include <unistd.h>
 #include <string.h>
 #include <signal.h>
-#include <alloca.h>
 #include <sys/param.h>
 #include <sys/types.h>
 #include <sys/stat.h>
modules/mount_bind.c +2 -5
index 022d183..3ec467d 100644
@@ -71,7 +71,7 @@ out:
 int mount_mount(struct autofs_point *ap, const char *root, const char *name, int name_len,
 		const char *what, const char *fstype, const char *options, void *context)
 {
-	char *fullpath;
+	char fullpath[PATH_MAX];
 	char buf[MAX_ERR_BUF];
 	int err;
 	int i, len;
@@ -82,14 +82,11 @@ int mount_mount(struct autofs_point *ap, const char *root, const char *name, int
 	/* Root offset of multi-mount */
 	len = strlen(root);
 	if (root[len - 1] == '/') {
-		fullpath = alloca(len);
 		len = snprintf(fullpath, len, "%s", root);
 	/* Direct mount name is absolute path so don't use root */
 	} else if (*name == '/') {
-		fullpath = alloca(len + 1);
 		len = sprintf(fullpath, "%s", root);
 	} else {
-		fullpath = alloca(len + name_len + 2);
 		len = sprintf(fullpath, "%s/%s", root, name);
 	}
 	fullpath[len] = '\0';
@@ -143,7 +140,7 @@ int mount_mount(struct autofs_point *ap, const char *root, const char *name, int
 		}
 	} else {
 		char *cp;
-		char *basepath = alloca(strlen(fullpath) + 1);
+		char basepath[PATH_MAX];
 		int status;
 		struct stat st;
 
modules/mount_changer.c +1 -4
index 43b8355..bf77a98 100644
@@ -46,7 +46,7 @@ int mount_init(void **context)
 int mount_mount(struct autofs_point *ap, const char *root, const char *name, int name_len,
 		const char *what, const char *fstype, const char *options, void *context)
 {
-	char *fullpath;
+	char fullpath[PATH_MAX];
 	char buf[MAX_ERR_BUF];
 	int err;
 	int len, status, existed = 1;
@@ -59,14 +59,11 @@ int mount_mount(struct autofs_point *ap, const char *root, const char *name, int
 	/* Root offset of multi-mount */
 	len = strlen(root);
 	if (root[len - 1] == '/') {
-		fullpath = alloca(len);
 		len = snprintf(fullpath, len, "%s", root);
 	/* Direct mount name is absolute path so don't use root */
 	} else if (*name == '/') {
-		fullpath = alloca(len + 1);
 		len = sprintf(fullpath, "%s", root);
 	} else {
-		fullpath = alloca(len + name_len + 2);
 		len = sprintf(fullpath, "%s/%s", root, name);
 	}
 	fullpath[len] = '\0';
modules/mount_ext2.c +1 -4
index 4c5b271..a80ccba 100644
@@ -38,7 +38,7 @@ int mount_init(void **context)
 int mount_mount(struct autofs_point *ap, const char *root, const char *name, int name_len,
 		const char *what, const char *fstype, const char *options, void *context)
 {
-	char *fullpath;
+	char fullpath[PATH_MAX];
 	char buf[MAX_ERR_BUF];
 	const char *p, *p1;
 	int err, ro = 0;
@@ -51,14 +51,11 @@ int mount_mount(struct autofs_point *ap, const char *root, const char *name, int
 	/* Root offset of multi-mount */
 	len = strlen(root);
 	if (root[len - 1] == '/') {
-		fullpath = alloca(len);
 		len = snprintf(fullpath, len, "%s", root);
 	/* Direct mount name is absolute path so don't use root */
 	} else if (*name == '/') {
-		fullpath = alloca(len + 1);
 		len = sprintf(fullpath, "%s", root);
 	} else {
-		fullpath = alloca(len + name_len + 2);
 		len = sprintf(fullpath, "%s/%s", root, name);
 	}
 	fullpath[len] = '\0';
modules/mount_generic.c +1 -4
index f094d07..17ebfd4 100644
@@ -39,7 +39,7 @@ int mount_mount(struct autofs_point *ap, const char *root, const char *name, int
 		const char *what, const char *fstype, const char *options,
 		void *context)
 {
-	char *fullpath;
+	char fullpath[PATH_MAX];
 	char buf[MAX_ERR_BUF];
 	int err;
 	int len, status, existed = 1;
@@ -50,14 +50,11 @@ int mount_mount(struct autofs_point *ap, const char *root, const char *name, int
 	/* Root offset of multi-mount */
 	len = strlen(root);
 	if (root[len - 1] == '/') {
-		fullpath = alloca(len);
 		len = snprintf(fullpath, len, "%s", root);
 	/* Direct mount name is absolute path so don't use root */
 	} else if (*name == '/') {
-		fullpath = alloca(len + 1);
 		len = sprintf(fullpath, "%s", root);
 	} else {
-		fullpath = alloca(len + name_len + 2);
 		len = sprintf(fullpath, "%s/%s", root, name);
 	}
 	fullpath[len] = '\0';
Signature · 1 line
1.6.0.4
#4 lore raw

PATCH 4/4 Replace <linux/string.h> with <string.h>

If installed, <linux/string.h> just includes the user-level string.h. If it's not installed, the compile fails.

From: Paul Wankadia <[email protected]>

---
 include/linux/auto_dev-ioctl.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
include/linux/auto_dev-ioctl.h +1 -1
index 91a7739..78f4b47 100644
@@ -10,7 +10,7 @@
 #ifndef _LINUX_AUTO_DEV_IOCTL_H
 #define _LINUX_AUTO_DEV_IOCTL_H
 
-#include <linux/string.h>
+#include <string.h>
 #include <linux/types.h>
 
 #define AUTOFS_DEVICE_NAME		"autofs"
Signature · 1 line
1.6.0.4
maintainer
#5 lore raw

Re: [PATCH 4/4] Replace <linux/string.h> with <string.h>

Quoted 2 lines · Valerie Aurora Henson

If installed, <linux/string.h> just includes the user-level string.h. If it's not installed, the compile fails.

Right.

This include file is also used by the kernel and I'd like to keep them the same. Maybe we need some #ifdef __KERNEL__ here as I think include <string.h> will fail during a kernel build.

Or maybe we need to move the include to fs/autofs4/dev-ioctl.c as I don't use any str* functions in the include file any more.

Quoted 20 lines

From: Paul Wankadia <[email protected]>

---
 include/linux/auto_dev-ioctl.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
include/linux/auto_dev-ioctl.h +1 -1
index 91a7739..78f4b47 100644
@@ -10,7 +10,7 @@
 #ifndef _LINUX_AUTO_DEV_IOCTL_H
 #define _LINUX_AUTO_DEV_IOCTL_H
 
-#include <linux/string.h>
+#include <string.h>
 #include <linux/types.h>
 
 #define AUTOFS_DEVICE_NAME		"autofs"
#6 lore raw

Re: [PATCH 3/4] Easy alloca() replacements

In reply to Valerie Aurora Henson
Quoted 8 lines · Valerie Aurora Henson
daemon/direct.c +0 -1
@@ -742,11 +742,9 @@ int mount_autofs_offset(struct autofs_point *ap, struct mapent *me, const char *
 
 	type = ap->entry->maps->type;
 	if (type && !strcmp(ap->entry->maps->type, "hosts")) {
-		char *tmp = alloca(7);

daemon/direct.c int mount_autofs_offset(struct autofs_point *ap, struct mapent *me, const char * · line 750

Quoted 10 lines
daemon/direct.c +3 -4
-		if (tmp) {
-			strcpy(tmp, "-hosts");
-			map_name = (const char *) tmp;
-		}
+		char tmp[7];
+		strcpy(tmp, "-hosts");
+		map_name = (const char *) tmp;
 	} else
 		map_name = me->mc->map->argv[0];
 

tmp is being accessed outside of the scope it is declared in, I'll fix that too.

-VAL

maintainer
#7 lore raw

Re: [PATCH 3/4] Easy alloca() replacements

In reply to Valerie Aurora Henson

On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:

Just a first pass reading but noticed ....

lib/cache.c struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s · line 487

Quoted 11 lines
lib/cache.c +1 -2
index 36b8294..bc2c722 100644
@@ -484,27 +484,19 @@ struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s
 {
 	struct list_head *p;
 	struct mapent *this;
-	int plen = strlen(prefix);
-	char *o_key;
+	char o_key[KEY_MAX_LEN];

I know this looks right but I think it will end up being a problem latter. I know there are places in the map lookup libraries that restrict these to KEY_MAX_LEN, which is needed for indirect map keys, but direct map keys really shouldn't have this restriction as they should be able to be as long as PATH_MAX but that brings the issue of needing to audit and adjust the maximum parse buffer as well. So we will need to get around to that at some point as well.

lib/cache.c struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s · line 492

Quoted 13 lines
lib/cache.c +3 -8
 	/* root offset duplicates "/" */
-	if (plen > 1) {
-		o_key = alloca(plen + strlen(offset) + 1);
-		strcpy(o_key, prefix);
-		strcat(o_key, offset);
-	} else {
-		o_key = alloca(strlen(offset) + 1);
-		strcpy(o_key, offset);
-	}
+	if (snprintf(o_key, sizeof(o_key), "%s%s", prefix, offset) >
+	    sizeof(o_key))
+		return NULL;

Looks like this will set o_key to "//..." for strlen(prefix) == 1.

Quoted 13 lines
lib/cache.c +2 -4
 	list_for_each(p, head) {
 		this = list_entry(p, struct mapent, multi_list);
 		if (!strcmp(&this->key[start], o_key))
-			goto done;
+			return this;
 	}
-	this = NULL;
-done:
-	return this;
+	return NULL;
 }
 
#8 lore raw

Re: [PATCH 3/4] Easy alloca() replacements

Quoted 16 lines · Ian Kent

On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:

Just a first pass reading but noticed ....

lib/cache.c struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s · line 487

Quoted 11 lines
lib/cache.c +1 -2
index 36b8294..bc2c722 100644
@@ -484,27 +484,19 @@ struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s
 {
 	struct list_head *p;
 	struct mapent *this;
-	int plen = strlen(prefix);
-	char *o_key;
+	char o_key[KEY_MAX_LEN];
Quoted 7 lines

I know this looks right but I think it will end up being a problem latter. I know there are places in the map lookup libraries that restrict these to KEY_MAX_LEN, which is needed for indirect map keys, but direct map keys really shouldn't have this restriction as they should be able to be as long as PATH_MAX but that brings the issue of needing to audit and adjust the maximum parse buffer as well. So we will need to get around to that at some point as well.

It certainly won't hurt to make this PATH_MAX - I'll do that unless I hear otherwise.

Quoted 15 lines

lib/cache.c struct mapent *cache_lookup_offset(const char *prefix, const char *offset, int s · line 492

Quoted 13 lines
lib/cache.c +3 -8
 	/* root offset duplicates "/" */
-	if (plen > 1) {
-		o_key = alloca(plen + strlen(offset) + 1);
-		strcpy(o_key, prefix);
-		strcat(o_key, offset);
-	} else {
-		o_key = alloca(strlen(offset) + 1);
-		strcpy(o_key, offset);
-	}
+	if (snprintf(o_key, sizeof(o_key), "%s%s", prefix, offset) >
+	    sizeof(o_key))
+		return NULL;

Looks like this will set o_key to "//..." for strlen(prefix) == 1.

I'll fix it, thanks

-VAL

#9 lore raw

Re: [PATCH 2/4] Make MAX_ERR_BUF and PARSE_MAX_BUF use easier to audit

In reply to Valerie Aurora Henson

modules/lookup_ldap.c int lookup_read_master(struct master *master, time_t age, void *context) · line 1529

Quoted 10 lines · Valerie Aurora Henson
modules/lookup_ldap.c +2 -2
@@ -1524,18 +1525,12 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 			goto next;
 		}
 
-		blen = strlen(*keyValue) + 1 + strlen(*values) + 2;
-		if (blen > PARSE_MAX_BUF) {
+		if (snprintf(parse_buf, sizeof(parse_buf), "%s %s",
+			     *keyValue, *values) > sizeof(parse_buf)) {

I think this should be >=.

Cheers,
Jeff

#10 lore raw

Re: [PATCH 2/4] Make MAX_ERR_BUF and PARSE_MAX_BUF use easier to audit

Quoted 8 lines · Jeff Moyer
Quoted 6 lines · Valerie Aurora Henson
modules/lookup_ldap.c +0 -0
@@ -1524,18 +1525,12 @@ int lookup_read_master(struct master *master, time_t age, void *context)
 			goto next;
 		}
 
Quoted 6 lines

modules/lookup_ldap.c int lookup_read_master(struct master *master, time_t age, void *context) · line 1529

Quoted 4 lines
modules/lookup_ldap.c +2 -2
-		blen = strlen(*keyValue) + 1 + strlen(*values) + 2;
-		if (blen > PARSE_MAX_BUF) {
+		if (snprintf(parse_buf, sizeof(parse_buf), "%s %s",
+			     *keyValue, *values) > sizeof(parse_buf)) {

I think this should be >=.

Yes, they all should be. I'll regenerate. Thanks,

-VAL

#11 lore raw

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

In reply to Valerie Aurora Henson
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

Most patches of this nature come with some description of a performance problem and how the patch solves it. Which caching algorithm is implemented below? There are, of course, many hashing algorithms for variable length strings. Can we get some rationale for the change? I'm not against it, I'd just like a *little* explanation.

Cheers,
Jeff

Quoted 100 lines
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +18 -11
index ce47e04..36b8294 100644
@@ -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;
#12 lore raw

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

Quoted 9 lines · Jeff Moyer
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

Most patches of this nature come with some description of a performance problem and how the patch solves it. Which caching algorithm is implemented below? There are, of course, many hashing algorithms for variable length strings. Can we get some rationale for the change? I'm not against it, I'd just like a *little* explanation.

This is where I get to blame my cold for being stupid. :)

Yes, the original author (Paul Wankadia, now cc'd) gave me a little information on that front, I just forgot to pass it on. It's the "One-at-a-Time" hash function by Bob Jenkins. See:

http://burtleburtle.net/bob/hash/doobs.html

What I vaguely recall from our conversation is an order of magnitude improvement in elapsed time for large (thousands) numbers of maps, but I'll let Paul be more specific. Do we have a test for thousands of entries somewhere in our automated tests?

-VAL

Quoted 104 lines

Cheers,
Jeff

Quoted 100 lines
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +18 -11
index ce47e04..36b8294 100644
@@ -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;
#13 lore raw

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

Quoted 12 lines · Valerie Aurora Henson

Most patches of this nature come with some description of a performance

Quoted 4 lines

problem and how the patch solves it. Which caching algorithm is implemented below? There are, of course, many hashing algorithms for variable length strings. Can we get some rationale for the change? I'm not against it, I'd just like a *little* explanation.

This is where I get to blame my cold for being stupid. :)

Yes, the original author (Paul Wankadia, now cc'd) gave me a little information on that front, I just forgot to pass it on. It's the "One-at-a-Time" hash function by Bob Jenkins. See:

Quoted 6 lines

http://burtleburtle.net/bob/hash/doobs.html

What I vaguely recall from our conversation is an order of magnitude improvement in elapsed time for large (thousands) numbers of maps, but I'll let Paul be more specific. Do we have a test for thousands of entries somewhere in our automated tests?

It's just that the additive hash function and the tiny, non-prime hash table size offended my delicate sensibilities. ;)

Actually, we discovered that reloading a large file map took well over ten seconds. Profiling revealed that the daemon spent most of its time calling strcmp(3).

Oh, and I should note that the problem was observed in autofs v4. I'll be looking more closely at autofs v5 in the near future.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#14 lore raw

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

Quoted 31 lines · Paul Wankadia

On Sat, Jan 10, 2009 at 6:51 AM, Valerie Aurora Henson <[email protected]> wrote:

> Most patches of this nature come with some description of a performance
> problem and how the patch solves it. Which caching algorithm is
> implemented below? There are, of course, many hashing algorithms for
> variable length strings. Can we get some rationale for the change? I'm
> not against it, I'd just like a *little* explanation.

This is where I get to blame my cold for being stupid. :)

Yes, the original author (Paul Wankadia, now cc'd) gave me a little
information on that front, I just forgot to pass it on. It's the
"One-at-a-Time" hash function by Bob Jenkins. See:

http://burtleburtle.net/bob/hash/doobs.html

What I vaguely recall from our conversation is an order of magnitude
improvement in elapsed time for large (thousands) numbers of maps, but
I'll let Paul be more specific. Do we have a test for thousands of
entries somewhere in our automated tests?

Quoted 2 lines

It's just that the additive hash function and the tiny, non-prime hash table size offended my delicate sensibilities. ;)

Oh .. right, looks like v4 uses a prime to me but I did mean to use a prime in v5, oops!

Quoted 7 lines

Actually, we discovered that reloading a large file map took well over ten seconds. Profiling revealed that the daemon spent most of its time calling strcmp(3).

Oh, and I should note that the problem was observed in autofs v4. I'll be looking more closely at autofs v5 in the near future.

It's much the same, the hash size is not much bigger and it can well do with a healthy increase. I don't know what sort of distribution the simple additive hash gives and if we are going to change it then we should do some checking with representative strings to ensure that what we use is in fact better.

Ian

#15 lore raw

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

Quoted 5 lines · Ian Kent

It's just that the additive hash function and the tiny, non-prime hash

Quoted 1 line

table size offended my delicate sensibilities. ;)

Oh .. right, looks like v4 uses a prime to me but I did mean to use a prime in v5, oops!

$ factor 27 77
27: 3 3 3
77: 7 11
$
Quoted 4 lines

Actually, we discovered that reloading a large file map took well over

Quoted 3 lines

ten seconds. Profiling revealed that the daemon spent most of its time calling strcmp(3).

Quoted 8 lines
Quoted 2 lines

Oh, and I should note that the problem was observed in autofs v4. I'll be looking more closely at autofs v5 in the near future.

It's much the same, the hash size is not much bigger and it can well do with a healthy increase. I don't know what sort of distribution the simple additive hash gives and if we are going to change it then we should do some checking with representative strings to ensure that what we use is in fact better.

How could it be worse? :P

I'll check our large file map just to satisfy my curiosity.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#16 lore raw

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

Quoted 6 lines · Paul Wankadia

On Mon, Jan 12, 2009 at 3:42 AM, Ian Kent <[email protected]> wrote:

> It's just that the additive hash function and the tiny, non-prime hash
> table size offended my delicate sensibilities. ;)

Quoted 8 lines

Oh .. right, looks like v4 uses a prime to me but I did mean to use a
prime in v5, oops!

$ factor 27 77
27: 3 3 3
77: 7 11
$ 

Yeah, yeah, I realized how stupid I was just after I made the post, double oops!

Quoted 26 lines

> Actually, we discovered that reloading a large file map took well over
> ten seconds. Profiling revealed that the daemon spent most of its time
> calling strcmp(3).
>
> Oh, and I should note that the problem was observed in autofs v4. I'll
> be looking more closely at autofs v5 in the near future.

It's much the same, the hash size is not much bigger and it can well do
with a healthy increase. I don't know what sort of distribution the
simple additive hash gives and if we are going to change it then we
should do some checking with representative strings to ensure that what
we use is in fact better.

How could it be worse? :P

I'll check our large file map just to satisfy my curiosity.

maintainer
#17 lore raw

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

In reply to Paul Wankadia
Quoted 26 lines · Paul Wankadia

On Mon, Jan 12, 2009 at 3:42 AM, Ian Kent <[email protected]> wrote:

> It's just that the additive hash function and the tiny, non-prime hash
> table size offended my delicate sensibilities. ;)

Oh .. right, looks like v4 uses a prime to me but I did mean to use a
prime in v5, oops!

$ factor 27 77
27: 3 3 3
77: 7 11
$ 

> Actually, we discovered that reloading a large file map took well over
> ten seconds. Profiling revealed that the daemon spent most of its time
> calling strcmp(3).
>
> Oh, and I should note that the problem was observed in autofs v4. I'll
> be looking more closely at autofs v5 in the near future.

Quoted 10 lines

It's much the same, the hash size is not much bigger and it can well do
with a healthy increase. I don't know what sort of distribution the
simple additive hash gives and if we are going to change it then we
should do some checking with representative strings to ensure that what
we use is in fact better.

Oh .. didn't see this before.

Quoted 1 line

How could it be worse? :P

Hehe, there's an assumption without evidence in there some where.

Quoted 3 lines

I'll check our large file map just to satisfy my curiosity.

Give me a chance and I'll do a couple of patches to add some statistical calculations to cache_dump_cache() so we can see the state of the hash table after a map is loaded.

Ian

#18 lore raw

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

On Mon, Jan 12, 2009 at 12:19 PM, Ian Kent <[email protected]> wrote:

Oh .. didn't see this before.

Quoted 4 lines
Quoted 2 lines

How could it be worse? :P

Hehe, there's an assumption without evidence in there some where.

Well, yes, I assumed that almost anything would be better than the additive hash function. ;)

Quoted 5 lines

I'll check our large file map just to satisfy my curiosity.

Give me a chance and I'll do a couple of patches to add some statistical calculations to cache_dump_cache() so we can see the state of the hash table after a map is loaded.

Here are the raw data and the corresponding plots:

additive.txt (text/plain) 28K
additive.png (image/png) 6K
one-at-a-time.txt (text/plain) 30K
one-at-a-time.png (image/png) 6K

0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 0
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0
58 0
59 0
60 0
61 0
62 0
63 0
64 0
65 0
66 0
67 0
68 0
69 0
70 0
71 0
72 0
73 0
74 0
75 0
76 0
77 0
78 0
79 0
80 0
81 0
82 0
83 0
84 0
85 0
86 0
87 0
88 0
89 0
90 0
91 0
92 0
93 0
94 0
95 0
96 0
97 0
98 0
99 1
100 0
101 0
102 0
103 0
104 0
105 0
106 0
107 0
108 0
109 0
110 0
111 0
112 1
113 0
114 1
115 0
116 0
117 0
118 0
119 0
120 0
121 0
122 0
123 0
124 0
125 0
126 0
127 0
128 0
129 0
130 0
131 0
132 0
133 0
134 0
135 0
136 0
137 0
138 0
139 0
140 0
141 0
142 0
143 0
144 0
145 0
146 0
147 0
148 0
149 0
150 0
151 0
152 0
153 0
154 0
155 0
156 0
157 0
158 0
159 0
160 0
161 0
162 0
163 0
164 0
165 0
166 1
167 0
168 0
169 0
170 0
171 0
172 0
173 0
174 0
175 0
176 0
177 0
178 0
179 0
180 0
181 0
182 0
183 0
184 0
185 0
186 0
187 0
188 0
189 0
190 0
191 0
192 0
193 0
194 1
195 0
196 0
197 1
198 0
199 0
200 1
201 0
202 1
203 0
204 1
205 3
206 0
207 1
208 2
209 3
210 2
211 3
212 1
213 0
214 2
215 2
216 0
217 2
218 1
219 2
220 1
221 0
222 3
223 2
224 1
225 1
226 0
227 0
228 1
229 0
230 2
231 0
232 1
233 2
234 0
235 1
236 0
237 0
238 0
239 0
240 0
241 0
242 0
243 0
244 0
245 0
246 0
247 0
248 0
249 0
250 0
251 0
252 0
253 0
254 0
255 0
256 0
257 0
258 1
259 0
260 0
261 0
262 0
263 0
264 0
265 0
266 1
267 0
268 0
269 0
270 0
271 0
272 0
273 0
274 0
275 0
276 0
277 0
278 0
279 0
280 0
281 0
282 0
283 0
284 0
285 0
286 0
287 0
288 0
289 0
290 0
291 0
292 0
293 1
294 4
295 3
296 3
297 3
298 3
299 4
300 5
301 5
302 7
303 10
304 12
305 13
306 13
307 14
308 16
309 26
310 16
311 22
312 18
313 23
314 29
315 31
316 35
317 34
318 33
319 30
320 34
321 40
322 31
323 31
324 49
325 35
326 30
327 38
328 31
329 33
330 26
331 32
332 18
333 23
334 34
335 24
336 20
337 22
338 16
339 19
340 17
341 15
342 8
343 17
344 13
345 12
346 11
347 6
348 10
349 4
350 5
351 7
352 5
353 3
354 3
355 0
356 2
357 2
358 2
359 0
360 3
361 0
362 0
363 1
364 0
365 0
366 0
367 0
368 0
369 0
370 0
371 0
372 0
373 0
374 0
375 0
376 0
377 0
378 0
379 0
380 0
381 0
382 0
383 0
384 0
385 0
386 0
387 0
388 1
389 0
390 0
391 1
392 0
393 0
394 1
395 0
396 0
397 3
398 2
399 1
400 5
401 1
402 8
403 9
404 9
405 13
406 9
407 20
408 16
409 17
410 23
411 18
412 33
413 26
414 34
415 42
416 52
417 44
418 40
419 51
420 54
421 61
422 56
423 56
424 61
425 65
426 65
427 75
428 57
429 65
430 61
431 62
432 60
433 56
434 61
435 52
436 53
437 48
438 61
439 58
440 46
441 38
442 43
443 26
444 33
445 38
446 38
447 20
448 26
449 39
450 25
451 26
452 16
453 16
454 17
455 9
456 10
457 12
458 9
459 4
460 7
461 2
462 7
463 7
464 5
465 0
466 0
467 0
468 1
469 1
470 0
471 1
472 2
473 0
474 1
475 2
476 1
477 0
478 0
479 0
480 0
481 0
482 0
483 0
484 0
485 0
486 0
487 0
488 1
489 0
490 1
491 0
492 0
493 1
494 0
495 0
496 1
497 3
498 2
499 6
500 2
501 4
502 4
503 5
504 5
505 8
506 12
507 20
508 23
509 20
510 39
511 35
512 26
513 38
514 46
515 59
516 56
517 58
518 68
519 65
520 91
521 87
522 101
523 115
524 92
525 114
526 140
527 119
528 129
529 138
530 145
531 123
532 143
533 123
534 159
535 147
536 151
537 140
538 153
539 159
540 114
541 112
542 110
543 124
544 116
545 123
546 108
547 94
548 110
549 80
550 86
551 77
552 68
553 89
554 66
555 46
556 40
557 54
558 41
559 34
560 42
561 44
562 26
563 26
564 24
565 27
566 23
567 20
568 11
569 12
570 20
571 10
572 6
573 13
574 8
575 5
576 3
577 4
578 0
579 1
580 3
581 0
582 3
583 1
584 4
585 0
586 0
587 0
588 4
589 1
590 0
591 0
592 0
593 0
594 0
595 0
596 0
597 2
598 3
599 2
600 0
601 0
602 2
603 5
604 5
605 1
606 5
607 12
608 19
609 16
610 24
611 22
612 33
613 30
614 36
615 33
616 40
617 63
618 54
619 52
620 68
621 73
622 75
623 85
624 90
625 117
626 121
627 116
628 109
629 130
630 142
631 160
632 174
633 153
634 160
635 165
636 192
637 171
638 169
639 187
640 210
641 200
642 212
643 187
644 177
645 191
646 201
647 194
648 158
649 183
650 203
651 182
652 161
653 154
654 154
655 153
656 120
657 120
658 115
659 102
660 122
661 87
662 102
663 93
664 84
665 87
666 75
667 58
668 63
669 62
670 54
671 37
672 43
673 34
674 32
675 24
676 33
677 20
678 12
679 13
680 14
681 11
682 7
683 12
684 5
685 4
686 3
687 3
688 4
689 2
690 2
691 3
692 2
693 0
694 1
695 3
696 1
697 0
698 1
699 1
700 0
701 2
702 1
703 2
704 0
705 2
706 5
707 7
708 5
709 11
710 11
711 8
712 10
713 15
714 15
715 19
716 19
717 18
718 30
719 32
720 27
721 41
722 46
723 59
724 71
725 53
726 59
727 76
728 87
729 72
730 115
731 102
732 135
733 109
734 137
735 133
736 129
737 129
738 174
739 177
740 155
741 167
742 189
743 164
744 187
745 212
746 172
747 194
748 183
749 183
750 170
751 180
752 199
753 199
754 172
755 185
756 160
757 159
758 163
759 163
760 163
761 132
762 118
763 127
764 142
765 113
766 119
767 136
768 102
769 105
770 106
771 93
772 73
773 66
774 65
775 68
776 45
777 61
778 59
779 47
780 38
781 31
782 40
783 34
784 26
785 17
786 21
787 20
788 16
789 11
790 16
791 13
792 6
793 8
794 5
795 2
796 5
797 4
798 4
799 3
800 2
801 3
802 5
803 1
804 2
805 1
806 4
807 2
808 5
809 2
810 7
811 2
812 5
813 8
814 8
815 7
816 9
817 10
818 10
819 18
820 11
821 19
822 17
823 25
824 33
825 30
826 38
827 37
828 42
829 49
830 42
831 50
832 62
833 90
834 57
835 71
836 70
837 81
838 94
839 83
840 93
841 105
842 93
843 110
844 124
845 117
846 142
847 133
848 125
849 127
850 125
851 146
852 155
853 156
854 141
855 143
856 167
857 158
858 135
859 149
860 147
861 145
862 135
863 142
864 139
865 133
866 117
867 119
868 124
869 114
870 121
871 117
872 91
873 91
874 88
875 78
876 94
877 64
878 74
879 70
880 56
881 71
882 63
883 49
884 47
885 28
886 40
887 29
888 23
889 24
890 29
891 17
892 18
893 16
894 18
895 15
896 12
897 15
898 18
899 8
900 7
901 6
902 3
903 3
904 1
905 3
906 2
907 3
908 5
909 4
910 3
911 1
912 2
913 2
914 2
915 2
916 3
917 4
918 1
919 1
920 5
921 4
922 2
923 5
924 6
925 11
926 6
927 5
928 9
929 7
930 19
931 16
932 24
933 30
934 18
935 28
936 19
937 35
938 32
939 30
940 44
941 39
942 37
943 52
944 50
945 73
946 60
947 67
948 59
949 66
950 60
951 70
952 67
953 70
954 74
955 82
956 91
957 78
958 74
959 78
960 84
961 72
962 89
963 73
964 93
965 72
966 91
967 85
968 82
969 83
970 70
971 74
972 83
973 53
974 71
975 66
976 83
977 54
978 68
979 59
980 43
981 49
982 34
983 43
984 33
985 34
986 49
987 30
988 28
989 28
990 34
991 24
992 21
993 26
994 22
995 18
996 22
997 15
998 16
999 17
1000 9
1001 8
1002 8
1003 11
1004 9
1005 5
1006 11
1007 6
1008 3
1009 9
1010 5
1011 3
1012 2
1013 5
1014 3
1015 4
1016 0
1017 4
1018 0
1019 4
1020 2
1021 3
1022 5
1023 4
1024 4
1025 1
1026 5
1027 4
1028 7
1029 7
1030 6
1031 7
1032 9
1033 5
1034 7
1035 6
1036 13
1037 12
1038 9
1039 8
1040 13
1041 21
1042 12
1043 20
1044 15
1045 31
1046 27
1047 14
1048 28
1049 33
1050 30
1051 33
1052 31
1053 38
1054 50
1055 29
1056 39
1057 30
1058 50
1059 47
1060 50
1061 48
1062 45
1063 50
1064 55
1065 38
1066 52
1067 47
1068 53
1069 44
1070 57
1071 46
1072 57
1073 60
1074 60
1075 49
1076 54
1077 63
1078 40
1079 54
1080 41
1081 51
1082 43
1083 39
1084 50
1085 32
1086 37
1087 36
1088 29
1089 28
1090 36
1091 25
1092 33
1093 27
1094 29
1095 22
1096 26
1097 28
1098 17
1099 17
1100 24
1101 11
1102 13
1103 11
1104 4
1105 8
1106 16
1107 7
1108 17
1109 7
1110 9
1111 9
1112 4
1113 7
1114 4
1115 5
1116 3
1117 6
1118 6
1119 3
1120 4
1121 3
1122 4
1123 2
1124 1
1125 5
1126 3
1127 3
1128 3
1129 3
1130 0
1131 4
1132 2
1133 4
1134 2
1135 5
1136 4
1137 6
1138 4
1139 7
1140 4
1141 5
1142 8
1143 5
1144 6
1145 7
1146 10
1147 11
1148 8
1149 9
1150 14
1151 11
1152 16
1153 14
1154 16
1155 26
1156 15
1157 17
1158 19
1159 15
1160 18
1161 22
1162 25
1163 23
1164 28
1165 20
1166 17
1167 20
1168 21
1169 34
1170 35
1171 20
1172 25
1173 28
1174 31
1175 32
1176 23
1177 24
1178 22
1179 33
1180 25
1181 36
1182 26
1183 29
1184 37
1185 34
1186 21
1187 21
1188 26
1189 24
1190 24
1191 21
1192 20
1193 27
1194 29
1195 24
1196 19
1197 25
1198 21
1199 13
1200 15
1201 13
1202 19
1203 13
1204 18
1205 9
1206 12
1207 14
1208 4
1209 11
1210 11
1211 6
1212 6
1213 8
1214 4
1215 4
1216 4
1217 5
1218 3
1219 5
1220 4
1221 3
1222 5
1223 3
1224 3
1225 5
1226 5
1227 0
1228 2
1229 4
1230 1
1231 2
1232 4
1233 1
1234 2
1235 4
1236 5
1237 3
1238 3
1239 4
1240 2
1241 4
1242 6
1243 5
1244 3
1245 1
1246 8
1247 4
1248 3
1249 6
1250 9
1251 6
1252 5
1253 5
1254 10
1255 10
1256 6
1257 5
1258 10
1259 6
1260 7
1261 11
1262 9
1263 12
1264 13
1265 15
1266 8
1267 10
1268 16
1269 16
1270 14
1271 14
1272 10
1273 16
1274 13
1275 15
1276 12
1277 15
1278 14
1279 24
1280 15
1281 13
1282 19
1283 19
1284 19
1285 23
1286 21
1287 13
1288 17
1289 14
1290 17
1291 14
1292 14
1293 12
1294 13
1295 16
1296 17
1297 13
1298 17
1299 16
1300 9
1301 12
1302 7
1303 15
1304 9
1305 17
1306 11
1307 10
1308 1
1309 10
1310 10
1311 5
1312 4
1313 7
1314 7
1315 13
1316 4
1317 2
1318 9
1319 7
1320 2
1321 3
1322 3
1323 8
1324 2
1325 2
1326 2
1327 5
1328 2
1329 3
1330 3
1331 0
1332 2
1333 2
1334 5
1335 2
1336 2
1337 1
1338 3
1339 5
1340 2
1341 2
1342 2
1343 3
1344 2
1345 2
1346 1
1347 5
1348 1
1349 5
1350 1
1351 3
1352 0
1353 2
1354 2
1355 3
1356 6
1357 1
1358 6
1359 5
1360 4
1361 6
1362 13
1363 4
1364 9
1365 8
1366 7
1367 6
1368 10
1369 5
1370 8
1371 5
1372 3
1373 10
1374 11
1375 11
1376 12
1377 7
1378 16
1379 13
1380 2
1381 10
1382 15
1383 8
1384 9
1385 12
1386 8
1387 12
1388 4
1389 9
1390 8
1391 11
1392 13
1393 9
1394 11
1395 11
1396 7
1397 8
1398 9
1399 10
1400 13
1401 11
1402 13
1403 8
1404 8
1405 10
1406 3
1407 10
1408 6
1409 10
1410 10
1411 3
1412 6
1413 3
1414 7
1415 3
1416 3
1417 8
1418 5
1419 4
1420 5
1421 3
1422 4
1423 2
1424 3
1425 3
1426 2
1427 5
1428 6
1429 3
1430 2
1431 3
1432 3
1433 0
1434 1
1435 1
1436 1
1437 2
1438 2
1439 0
1440 2
1441 0
1442 3
1443 2
1444 0
1445 2
1446 1
1447 1
1448 3
1449 3
1450 2
1451 2
1452 6
1453 4
1454 3
1455 3
1456 1
1457 4
1458 1
1459 1
1460 2
1461 3
1462 2
1463 1
1464 3
1465 5
1466 5
1467 5
1468 2
1469 2
1470 2
1471 5
1472 2
1473 6
1474 3
1475 3
1476 1
1477 6
1478 1
1479 3
1480 1
1481 4
1482 7
1483 3
1484 7
1485 2
1486 11
1487 4
1488 8
1489 4
1490 6
1491 6
1492 6
1493 4
1494 4
1495 4
1496 7
1497 5
1498 3
1499 6
1500 13
1501 3
1502 7
1503 4
1504 9
1505 9
1506 2
1507 5
1508 4
1509 9
1510 4
1511 7
1512 6
1513 6
1514 5
1515 5
1516 6
1517 6
1518 3
1519 3
1520 7
1521 5
1522 3
1523 4
1524 1
1525 2
1526 3
1527 7
1528 2
1529 3
1530 4
1531 3
1532 1
1533 1
1534 2
1535 2
1536 3
1537 2
1538 2
1539 0
1540 0
1541 0
1542 2
1543 1
1544 2
1545 0
1546 3
1547 0
1548 1
1549 1
1550 1
1551 2
1552 0
1553 0
1554 0
1555 0
1556 0
1557 0
1558 0
1559 3
1560 0
1561 1
1562 0
1563 2
1564 1
1565 0
1566 0
1567 1
1568 1
1569 1
1570 1
1571 0
1572 1
1573 1
1574 0
1575 2
1576 0
1577 0
1578 0
1579 0
1580 1
1581 2
1582 0
1583 0
1584 0
1585 0
1586 1
1587 0
1588 0
1589 1
1590 0
1591 0
1592 1
1593 0
1594 0
1595 0
1596 1
1597 2
1598 1
1599 0
1600 0
1601 0
1602 0
1603 0
1604 0
1605 1
1606 0
1607 0
1608 1
1609 0
1610 0
1611 0
1612 2
1613 1
1614 2
1615 0
1616 0
1617 0
1618 2
1619 1
1620 0
1621 1
1622 1
1623 0
1624 0
1625 1
1626 0
1627 1
1628 0
1629 0
1630 0
1631 0
1632 0
1633 0
1634 0
1635 1
1636 0
1637 1
1638 0
1639 0
1640 0
1641 1
1642 0
1643 0
1644 0
1645 0
1646 0
1647 1
1648 0
1649 0
1650 0
1651 0
1652 1
1653 1
1654 0
1655 0
1656 0
1657 1
1658 0
1659 1
1660 0
1661 3
1662 0
1663 1
1664 0
1665 0
1666 0
1667 2
1668 1
1669 0
1670 1
1671 0
1672 0
1673 3
1674 0
1675 1
1676 2
1677 0
1678 0
1679 0
1680 0
1681 0
1682 0
1683 1
1684 0
1685 0
1686 0
1687 1
1688 0
1689 0
1690 0
1691 0
1692 0
1693 1
1694 0
1695 1
1696 0
1697 1
1698 2
1699 0
1700 0
1701 0
1702 0
1703 2
1704 1
1705 0
1706 0
1707 0
1708 0
1709 0
1710 0
1711 0
1712 1
1713 0
1714 0
1715 1
1716 0
1717 0
1718 0
1719 1
1720 0
1721 0
1722 1
1723 0
1724 0
1725 1
1726 1
1727 0
1728 0
1729 1
1730 0
1731 0
1732 0
1733 0
1734 0
1735 0
1736 1
1737 0
1738 1
1739 0
1740 0
1741 0
1742 1
1743 0
1744 0
1745 0
1746 2
1747 1
1748 0
1749 1
1750 0
1751 0
1752 0
1753 0
1754 0
1755 1
1756 0
1757 0
1758 0
1759 0
1760 0
1761 0
1762 0
1763 0
1764 0
1765 0
1766 1
1767 0
1768 2
1769 0
1770 1
1771 0
1772 1
1773 2
1774 0
1775 1
1776 0
1777 0
1778 1
1779 0
1780 2
1781 0
1782 0
1783 1
1784 0
1785 1
1786 0
1787 1
1788 0
1789 2
1790 0
1791 1
1792 0
1793 0
1794 0
1795 0
1796 0
1797 0
1798 0
1799 0
1800 0
1801 0
1802 0
1803 0
1804 0
1805 1
1806 0
1807 0
1808 0
1809 0
1810 0
1811 0
1812 0
1813 0
1814 0
1815 0
1816 1
1817 1
1818 0
1819 0
1820 0
1821 0
1822 0
1823 0
1824 0
1825 0
1826 0
1827 0
1828 1
1829 0
1830 1
1831 0
1832 0
1833 0
1834 0
1835 1
1836 1
1837 0
1838 2
1839 0
1840 0
1841 0
1842 0
1843 1
1844 0
1845 0
1846 0
1847 0
1848 0
1849 0
1850 0
1851 0
1852 2
1853 0
1854 1
1855 0
1856 0
1857 0
1858 0
1859 0
1860 0
1861 0
1862 0
1863 0
1864 1
1865 0
1866 0
1867 0
1868 0
1869 0
1870 0
1871 1
1872 0
1873 0
1874 0
1875 0
1876 1
1877 0
1878 0
1879 0
1880 0
1881 0
1882 0
1883 0
1884 0
1885 0
1886 0
1887 0
1888 0
1889 0
1890 0
1891 0
1892 0
1893 0
1894 0
1895 1
1896 0
1897 0
1898 0
1899 0
1900 0
1901 0
1902 1
1903 0
1904 0
1905 1
1906 0
1907 0
1908 0
1909 0
1910 0
1911 1
1912 0
1913 1
1914 0
1915 0
1916 1
1917 0
1918 1
1919 0
1920 0
1921 1
1922 0
1923 0
1924 0
1925 0
1926 0
1927 0
1928 0
1929 0
1930 0
1931 1
1932 1
1933 0
1934 0
1935 0
1936 0
1937 1
1938 0
1939 1
1940 0
1941 0
1942 2
1943 0
1944 1
1945 1
1946 0
1947 0
1948 1
1949 0
1950 0
1951 1
1952 0
1953 1
1954 0
1955 0
1956 0
1957 1
1958 0
1959 0
1960 1
1961 0
1962 0
1963 1
1964 0
1965 0
1966 0
1967 1
1968 0
1969 0
1970 2
1971 0
1972 0
1973 1
1974 0
1975 0
1976 0
1977 0
1978 0
1979 1
1980 0
1981 2
1982 0
1983 1
1984 0
1985 0
1986 1
1987 0
1988 1
1989 1
1990 1
1991 0
1992 0
1993 0
1994 0
1995 0
1996 0
1997 0
1998 0
1999 0
2000 1
2001 0
2002 1
2003 1
2004 0
2005 2
2006 0
2007 0
2008 0
2009 0
2010 0
2011 0
2012 0
2013 0
2014 0
2015 1
2016 0
2017 1
2018 0
2019 0
2020 0
2021 0
2022 0
2023 0
2024 1
2025 1
2026 0
2027 0
2028 0
2029 0
2030 1
2031 0
2032 0
2033 2
2034 1
2035 2
2036 0
2037 0
2038 0
2039 1
2040 0
2041 0
2042 0
2043 0
2044 0
2045 0
2046 0
2047 0
2048 0
2049 0
2050 1
2051 0
2052 0
2053 1
2054 0
2055 0
2056 0
2057 0
2058 0
2059 0
2060 0
2061 0
2062 0
2063 0
2064 0
2065 1
2066 0
2067 0
2068 0
2069 0
2070 1
2071 0
2072 0
2073 0
2074 0
2075 0
2076 0
2077 0
2078 0
2079 1
2080 0
2081 0
2082 0
2083 0
2084 0
2085 0
2086 0
2087 0
2088 0
2089 2
2090 0
2091 0
2092 0
2093 1
2094 1
2095 0
2096 0
2097 0
2098 0
2099 1
2100 0
2101 0
2102 0
2103 0
2104 0
2105 1
2106 0
2107 0
2108 0
2109 0
2110 0
2111 1
2112 0
2113 0
2114 0
2115 0
2116 0
2117 0
2118 0
2119 0
2120 0
2121 1
2122 0
2123 0
2124 0
2125 0
2126 0
2127 0
2128 1
2129 0
2130 1
2131 0
2132 1
2133 0
2134 0
2135 0
2136 0
2137 0
2138 1
2139 1
2140 0
2141 0
2142 0
2143 0
2144 0
2145 1
2146 0
2147 0
2148 0
2149 0
2150 0
2151 0
2152 0
2153 0
2154 1
2155 0
2156 0
2157 0
2158 0
2159 1
2160 0
2161 0
2162 0
2163 0
2164 0
2165 0
2166 0
2167 0
2168 1
2169 0
2170 0
2171 1
2172 0
2173 0
2174 0
2175 0
2176 0
2177 0
2178 0
2179 0
2180 0
2181 0
2182 0
2183 0
2184 0
2185 0
2186 0
2187 0
2188 0
2189 0
2190 0
2191 0
2192 0
2193 0
2194 0
2195 0
2196 0
2197 1
2198 0
2199 0
2200 0
2201 0
2202 0
2203 0
2204 0
2205 0
2206 0
2207 0
2208 0
2209 0
2210 0
2211 1
2212 1
2213 0
2214 0
2215 0
2216 0
2217 1
2218 0
2219 0
2220 0
2221 0
2222 0
2223 0
2224 0
2225 0
2226 1
2227 0
2228 0
2229 1
2230 0
2231 0
2232 0
2233 0
2234 0
2235 1
2236 0
2237 0
2238 0
2239 0
2240 0
2241 0
2242 1
2243 0
2244 0
2245 1
2246 0
2247 0
2248 0
2249 0
2250 0
2251 0
2252 0
2253 1
2254 0
2255 0
2256 0
2257 0
2258 0
2259 0
2260 0
2261 0
2262 0
2263 0
2264 0
2265 0
2266 0
2267 0
2268 0
2269 0
2270 0
2271 0
2272 0
2273 0
2274 2
2275 0
2276 0
2277 0
2278 0
2279 0
2280 0
2281 0
2282 0
2283 0
2284 0
2285 0
2286 0
2287 0
2288 0
2289 0
2290 0
2291 1
2292 0
2293 1
2294 0
2295 0
2296 1
2297 0
2298 0
2299 0
2300 0
2301 0
2302 1
2303 0
2304 0
2305 0
2306 0
2307 0
2308 0
2309 0
2310 0
2311 0
2312 1
2313 2
2314 0
2315 0
2316 0
2317 0
2318 0
2319 0
2320 0
2321 0
2322 0
2323 0
2324 0
2325 0
2326 0
2327 0
2328 0
2329 0
2330 0
2331 0
2332 0
2333 0
2334 0
2335 0
2336 0
2337 0
2338 0
2339 0
2340 0
2341 0
2342 1
2343 0
2344 0
2345 0
2346 0
2347 0
2348 0
2349 1
2350 0
2351 0
2352 0
2353 0
2354 0
2355 0
2356 0
2357 0
2358 0
2359 0
2360 0
2361 0
2362 0
2363 0
2364 1
2365 0
2366 0
2367 0
2368 0
2369 0
2370 0
2371 0
2372 0
2373 0
2374 0
2375 0
2376 0
2377 0
2378 0
2379 1
2380 0
2381 0
2382 1
2383 0
2384 1
2385 0
2386 0
2387 0
2388 0
2389 0
2390 0
2391 0
2392 0
2393 0
2394 0
2395 0
2396 0
2397 0
2398 0
2399 0
2400 0
2401 0
2402 0
2403 0
2404 0
2405 0
2406 0
2407 0
2408 0
2409 0
2410 0
2411 0
2412 0
2413 0
2414 0
2415 0
2416 0
2417 0
2418 0
2419 0
2420 0
2421 0
2422 0
2423 0
2424 0
2425 0
2426 0
2427 0
2428 0
2429 0
2430 0
2431 0
2432 0
2433 0
2434 0
2435 0
2436 1
2437 0
2438 0
2439 0
2440 1
2441 0
2442 0
2443 1
2444 0
2445 0
2446 0
2447 1
2448 0
2449 0
2450 0
2451 0
2452 0
2453 0
2454 0
2455 0
2456 0
2457 0
2458 0
2459 0
2460 0
2461 0
2462 0
2463 0
2464 0
2465 0
2466 0
2467 0
2468 0
2469 0
2470 0
2471 1
2472 0
2473 0
2474 0
2475 0
2476 0
2477 1
2478 0
2479 0
2480 0
2481 0
2482 0
2483 0
2484 0
2485 0
2486 0
2487 0
2488 0
2489 0
2490 0
2491 0
2492 0
2493 0
2494 0
2495 0
2496 0
2497 0
2498 0
2499 0
2500 0
2501 0
2502 0
2503 0
2504 0
2505 0
2506 0
2507 0
2508 0
2509 0
2510 0
2511 0
2512 0
2513 0
2514 0
2515 0
2516 0
2517 0
2518 0
2519 0
2520 0
2521 0
2522 0
2523 0
2524 0
2525 0
2526 0
2527 0
2528 0
2529 0
2530 0
2531 0
2532 0
2533 0
2534 0
2535 0
2536 0
2537 0
2538 0
2539 0
2540 0
2541 0
2542 0
2543 0
2544 0
2545 0
2546 0
2547 0
2548 0
2549 0
2550 1
2551 0
2552 0
2553 0
2554 0
2555 0
2556 0
2557 0
2558 0
2559 0
2560 0
2561 0
2562 0
2563 0
2564 0
2565 0
2566 0
2567 0
2568 0
2569 0
2570 0
2571 0
2572 0
2573 0
2574 0
2575 0
2576 1
2577 0
2578 0
2579 0
2580 0
2581 0
2582 0
2583 0
2584 0
2585 0
2586 0
2587 0
2588 0
2589 0
2590 0
2591 0
2592 0
2593 0
2594 0
2595 0
2596 0
2597 0
2598 0
2599 0
2600 0
2601 0
2602 0
2603 0
2604 0
2605 0
2606 0
2607 0
2608 0
2609 0
2610 0
2611 0
2612 0
2613 0
2614 0
2615 0
2616 0
2617 0
2618 0
2619 0
2620 0
2621 0
2622 0
2623 0
2624 0
2625 0
2626 0
2627 0
2628 0
2629 0
2630 0
2631 0
2632 0
2633 0
2634 0
2635 0
2636 0
2637 0
2638 0
2639 0
2640 0
2641 0
2642 0
2643 0
2644 0
2645 0
2646 0
2647 0
2648 0
2649 0
2650 0
2651 0
2652 0
2653 0
2654 0
2655 0
2656 0
2657 0
2658 0
2659 0
2660 0
2661 0
2662 0
2663 0
2664 0
2665 1
2666 0
2667 1
2668 0
2669 0
2670 0
2671 0
2672 0
2673 0
2674 0
2675 0
2676 0
2677 0
2678 0
2679 0
2680 0
2681 0
2682 0
2683 0
2684 0
2685 0
2686 0
2687 0
2688 0
2689 0
2690 0
2691 0
2692 0
2693 0
2694 0
2695 0
2696 0
2697 0
2698 0
2699 0
2700 0
2701 0
2702 0
2703 0
2704 0
2705 0
2706 0
2707 0
2708 0
2709 0
2710 0
2711 0
2712 0
2713 0
2714 0
2715 0
2716 1
2717 0
2718 0
2719 0
2720 0
2721 0
2722 0
2723 0
2724 0
2725 0
2726 0
2727 0
2728 0
2729 0
2730 0
2731 0
2732 0
2733 0
2734 0
2735 0
2736 0
2737 0
2738 0
2739 0
2740 0
2741 0
2742 0
2743 0
2744 0
2745 0
2746 0
2747 0
2748 0
2749 0
2750 0
2751 0
2752 0
2753 0
2754 0
2755 0
2756 0
2757 0
2758 0
2759 0
2760 0
2761 1
2762 0
2763 0
2764 0
2765 0
2766 0
2767 0
2768 0
2769 0
2770 0
2771 0
2772 0
2773 0
2774 0
2775 0
2776 0
2777 0
2778 0
2779 0
2780 0
2781 0
2782 0
2783 0
2784 0
2785 0
2786 0
2787 0
2788 0
2789 0
2790 0
2791 0
2792 0
2793 0
2794 0
2795 0
2796 0
2797 0
2798 0
2799 0
2800 0
2801 0
2802 0
2803 0
2804 0
2805 0
2806 0
2807 0
2808 0
2809 0
2810 0
2811 0
2812 0
2813 0
2814 0
2815 0
2816 0
2817 0
2818 0
2819 1
2820 0
2821 0
2822 0
2823 0
2824 0
2825 0
2826 0
2827 0
2828 0
2829 0
2830 0
2831 0
2832 0
2833 0
2834 0
2835 0
2836 0
2837 0
2838 0
2839 0
2840 0
2841 0
2842 0
2843 0
2844 0
2845 0
2846 0
2847 0
2848 0
2849 0
2850 0
2851 0
2852 0
2853 0
2854 0
2855 0
2856 0
2857 0
2858 0
2859 1
2860 0
2861 0
2862 0
2863 0
2864 0
2865 0
2866 0
2867 0
2868 0
2869 0
2870 0
2871 0
2872 0
2873 0
2874 0
2875 0
2876 0
2877 0
2878 0
2879 0
2880 0
2881 0
2882 0
2883 0
2884 0
2885 0
2886 0
2887 0
2888 0
2889 0
2890 0
2891 0
2892 0
2893 0
2894 0
2895 0
2896 0
2897 0
2898 0
2899 0
2900 0
2901 0
2902 0
2903 0
2904 0
2905 0
2906 0
2907 0
2908 0
2909 0
2910 0
2911 0
2912 0
2913 0
2914 0
2915 0
2916 0
2917 0
2918 0
2919 0
2920 0
2921 0
2922 0
2923 0
2924 0
2925 0
2926 0
2927 0
2928 0
2929 0
2930 0
2931 0
2932 0
2933 0
2934 0
2935 0
2936 0
2937 0
2938 0
2939 0
2940 0
2941 0
2942 0
2943 0
2944 0
2945 0
2946 0
2947 0
2948 0
2949 0
2950 0
2951 0
2952 0
2953 0
2954 0
2955 0
2956 0
2957 0
2958 0
2959 0
2960 0
2961 0
2962 0
2963 0
2964 0
2965 1
2966 0
2967 0
2968 0
2969 0
2970 0
2971 0
2972 0
2973 0
2974 0
2975 0
2976 0
2977 0
2978 0
2979 0
2980 0
2981 0
2982 0
2983 0
2984 0
2985 0
2986 0
2987 0
2988 0
2989 0
2990 0
2991 0
2992 0
2993 0
2994 0
2995 0
2996 0
2997 0
2998 0
2999 0
3000 0
3001 0
3002 0
3003 0
3004 0
3005 0
3006 0
3007 0
3008 0
3009 0
3010 0
3011 0
3012 0
3013 0
3014 0
3015 0
3016 0
3017 0
3018 0
3019 0
3020 0
3021 0
3022 0
3023 0
3024 0
3025 0
3026 0
3027 0
3028 0
3029 0
3030 0
3031 0
3032 0
3033 0
3034 0
3035 0
3036 0
3037 0
3038 0
3039 0
3040 0
3041 0
3042 0
3043 0
3044 0
3045 0
3046 0
3047 0
3048 0
3049 0
3050 0
3051 0
3052 0
3053 0
3054 0
3055 0
3056 0
3057 0
3058 0
3059 0
3060 0
3061 0
3062 0
3063 0
3064 0
3065 0
3066 0
3067 0
3068 0
3069 0
3070 0
3071 0
3072 0
3073 0
3074 0
3075 0
3076 0
3077 0
3078 0
3079 0
3080 1
3081 0
3082 0
3083 0
3084 0
3085 0
3086 0
3087 0
3088 0
3089 0
3090 0
3091 0
3092 0
3093 0
3094 0
3095 0
3096 0
3097 0
3098 0
3099 0
3100 0
3101 0
3102 0
3103 0
3104 0
3105 0
3106 0
3107 0
3108 0
3109 0
3110 0
3111 0
3112 0
3113 0
3114 0
3115 0
3116 0
3117 0
3118 0
3119 0
3120 0
3121 0
3122 0
3123 0
3124 0
3125 0
3126 0
3127 0
3128 0
3129 0
3130 0
3131 0
3132 0
3133 0
3134 0
3135 0
3136 0
3137 0
3138 0
3139 0
3140 0
3141 0
3142 0
3143 0
3144 0
3145 0
3146 0
3147 0
3148 0
3149 0
3150 0
3151 0
3152 0
3153 0
3154 0
3155 0
3156 0
3157 0
3158 0
3159 0
3160 0
3161 0
3162 0
3163 0
3164 0
3165 0
3166 0
3167 0
3168 0
3169 0
3170 0
3171 0
3172 0
3173 0
3174 0
3175 0
3176 0
3177 0
3178 0
3179 0
3180 0
3181 0
3182 0
3183 0
3184 0
3185 0
3186 0
3187 0
3188 0
3189 0
3190 0
3191 0
3192 0
3193 0
3194 0
3195 0
3196 0
3197 0
3198 0
3199 0
3200 0
3201 0
3202 0
3203 0
3204 0
3205 0
3206 0
3207 0
3208 0
3209 0
3210 0
3211 0
3212 0
3213 0
3214 0
3215 0
3216 0
3217 0
3218 0
3219 0
3220 0
3221 0
3222 0
3223 0
3224 0
3225 0
3226 0
3227 0
3228 0
3229 0
3230 0
3231 0
3232 0
3233 0
3234 0
3235 0
3236 0
3237 0
3238 0
3239 0
3240 0
3241 0
3242 0
3243 0
3244 0
3245 0
3246 0
3247 0
3248 0
3249 0
3250 0
3251 0
3252 0
3253 0
3254 0
3255 0
3256 0
3257 0
3258 0
3259 0
3260 0
3261 0
3262 0
3263 0
3264 0
3265 0
3266 0
3267 0
3268 0
3269 0
3270 0
3271 0
3272 0
3273 0
3274 0
3275 0
3276 0
3277 0
3278 0
3279 0
3280 0
3281 0
3282 0
3283 0
3284 0
3285 0
3286 0
3287 0
3288 0
3289 0
3290 0
3291 0
3292 0
3293 0
3294 0
3295 0
3296 0
3297 0
3298 0
3299 0
3300 0
3301 0
3302 0
3303 0
3304 0
3305 0
3306 0
3307 0
3308 0
3309 0
3310 0
3311 0
3312 0
3313 0
3314 0
3315 0
3316 0
3317 0
3318 0
3319 0
3320 0
3321 0
3322 0
3323 0
3324 0
3325 0
3326 0
3327 0
3328 0
3329 0
3330 0
3331 0
3332 0
3333 0
3334 0
3335 0
3336 0
3337 0
3338 0
3339 0
3340 0
3341 0
3342 0
3343 0
3344 0
3345 0
3346 0
3347 0
3348 0
3349 0
3350 0
3351 0
3352 0
3353 0
3354 0
3355 0
3356 0
3357 0
3358 0
3359 0
3360 0
3361 0
3362 0
3363 0
3364 0
3365 0
3366 0
3367 0
3368 0
3369 0
3370 0
3371 0
3372 0
3373 0
3374 0
3375 0
3376 0
3377 0
3378 0
3379 0
3380 0
3381 0
3382 0
3383 0
3384 0
3385 0
3386 0
3387 0
3388 0
3389 0
3390 0
3391 0
3392 0
3393 0
3394 0
3395 0
3396 0
3397 0
3398 0
3399 0
3400 0
3401 0
3402 0
3403 0
3404 0
3405 0
3406 0
3407 0
3408 0
3409 0
3410 0
3411 0
3412 0
3413 0
3414 0
3415 0
3416 0
3417 0
3418 0
3419 0
3420 0
3421 0
3422 0
3423 0
3424 0
3425 0
3426 0
3427 0
3428 0
3429 0
3430 0
3431 0
3432 0
3433 0
3434 0
3435 0
3436 0
3437 0
3438 0
3439 0
3440 0
3441 0
3442 0
3443 0
3444 0
3445 0
3446 0
3447 0
3448 0
3449 0
3450 0
3451 0
3452 0
3453 0
3454 0
3455 0
3456 0
3457 0
3458 0
3459 0
3460 0
3461 0
3462 0
3463 0
3464 0
3465 0
3466 0
3467 0
3468 0
3469 0
3470 0
3471 0
3472 0
3473 0
3474 0
3475 0
3476 0
3477 0
3478 0
3479 0
3480 0
3481 0
3482 0
3483 0
3484 0
3485 0
3486 0
3487 0
3488 0
3489 0
3490 0
3491 0
3492 0
3493 0
3494 0
3495 0
3496 0
3497 0
3498 0
3499 0
3500 0
3501 0
3502 0
3503 0
3504 0
3505 0
3506 0
3507 0
3508 0
3509 0
3510 0
3511 0
3512 0
3513 0
3514 0
3515 0
3516 0
3517 0
3518 0
3519 0
3520 0
3521 0
3522 0
3523 0
3524 0
3525 0
3526 0
3527 0
3528 0
3529 0
3530 0
3531 0
3532 0
3533 0
3534 0
3535 0
3536 0
3537 0
3538 0
3539 0
3540 0
3541 0
3542 0
3543 0
3544 0
3545 0
3546 0
3547 0
3548 0
3549 0
3550 0
3551 0
3552 0
3553 0
3554 0
3555 0
3556 0
3557 0
3558 0
3559 0
3560 0
3561 0
3562 0
3563 0
3564 0
3565 0
3566 0
3567 0
3568 0
3569 0
3570 0
3571 0
3572 0
3573 0
3574 0
3575 0
3576 0
3577 0
3578 0
3579 0
3580 0
3581 0
3582 0
3583 0
3584 0
3585 0
3586 0
3587 0
3588 0
3589 0
3590 0
3591 0
3592 0
3593 0
3594 0
3595 0
3596 0
3597 0
3598 0
3599 0
3600 0
3601 0
3602 0
3603 0
3604 0
3605 0
3606 0
3607 0
3608 0
3609 0
3610 0
3611 0
3612 0
3613 0
3614 0
3615 0
3616 0
3617 0
3618 0
3619 0
3620 0
3621 0
3622 0
3623 0
3624 0
3625 0
3626 0
3627 0
3628 0
3629 0
3630 0
3631 0
3632 0
3633 0
3634 0
3635 0
3636 0
3637 0
3638 0
3639 0
3640 0
3641 0
3642 0
3643 0
3644 0
3645 0
3646 0
3647 0
3648 0
3649 0
3650 0
3651 0
3652 0
3653 0
3654 0
3655 0
3656 0
3657 0
3658 0
3659 0
3660 0
3661 0
3662 0
3663 0
3664 0
3665 0
3666 0
3667 0
3668 0
3669 0
3670 0
3671 0
3672 0
3673 0
3674 0
3675 0
3676 0
3677 0
3678 0
3679 0
3680 0
3681 0
3682 0
3683 0
3684 0
3685 0
3686 0
3687 0
3688 0
3689 0
3690 0
3691 0
3692 0
3693 0
3694 0
3695 0
3696 0
3697 0
3698 0
3699 0
3700 0
3701 0
3702 0
3703 0
3704 0
3705 0
3706 0
3707 0
3708 0
3709 0
3710 0
3711 0
3712 0
3713 0
3714 0
3715 0
3716 0
3717 0
3718 0
3719 0
3720 0
3721 0
3722 0
3723 0
3724 0
3725 0
3726 0
3727 0
3728 0
3729 0
3730 0
3731 0
3732 0
3733 0
3734 0
3735 0
3736 0
3737 0
3738 0
3739 0
3740 0
3741 0
3742 0
3743 0
3744 0
3745 0
3746 0
3747 0
3748 0
3749 0
3750 0
3751 0
3752 0
3753 0
3754 0
3755 0
3756 0
3757 0
3758 0
3759 0
3760 0
3761 0
3762 0
3763 0
3764 0
3765 0
3766 0
3767 0
3768 0
3769 0
3770 0
3771 0
3772 0
3773 0
3774 0
3775 0
3776 0
3777 0
3778 0
3779 0
3780 0
3781 0
3782 0
3783 0
3784 0
3785 0
3786 0
3787 0
3788 0
3789 0
3790 0
3791 0
3792 0
3793 0
3794 0
3795 0
3796 0
3797 0
3798 0
3799 0
3800 0
3801 0
3802 0
3803 0
3804 0
3805 0
3806 0
3807 0
3808 0
3809 0
3810 0
3811 0
3812 0
3813 0
3814 0
3815 0
3816 0
3817 0
3818 0
3819 0
3820 0
3821 0
3822 0
3823 0
3824 0
3825 0
3826 0
3827 0
3828 0
3829 0
3830 0
3831 0
3832 0
3833 0
3834 0
3835 0
3836 0
3837 0
3838 0
3839 0
3840 0
3841 0
3842 0
3843 0
3844 0
3845 0
3846 0
3847 0
3848 0
3849 0
3850 0
3851 0
3852 0
3853 0
3854 0
3855 0
3856 0
3857 0
3858 0
3859 0
3860 0
3861 0
3862 0
3863 0
3864 0
3865 0
3866 0
3867 0
3868 0
3869 0
3870 0
3871 0
3872 0
3873 0
3874 0
3875 0
3876 0
3877 0
3878 0
3879 0
3880 0
3881 0
3882 0
3883 0
3884 0
3885 0
3886 0
3887 0
3888 0
3889 0
3890 0
3891 0
3892 0
3893 0
3894 0
3895 0
3896 0
3897 0
3898 0
3899 0
3900 0
3901 0
3902 0
3903 0
3904 0
3905 0
3906 0
3907 0
3908 0
3909 0
3910 0
3911 0
3912 0
3913 0
3914 0
3915 0
3916 0
3917 0
3918 0
3919 0
3920 0
3921 0
3922 0
3923 0
3924 0
3925 0
3926 0
3927 0
3928 0
3929 0
3930 0
3931 0
3932 0
3933 0
3934 0
3935 0
3936 0
3937 0
3938 0
3939 0
3940 0
3941 0
3942 0
3943 0
3944 0
3945 0
3946 0
3947 0
3948 0
3949 0
3950 0
3951 0
3952 0
3953 0
3954 0
3955 0
3956 0
3957 0
3958 0
3959 0
3960 0
3961 0
3962 0
3963 0
3964 0
3965 0
3966 0
3967 0
3968 0
3969 0
3970 0
3971 0
3972 0
3973 0
3974 0
3975 0
3976 0
3977 0
3978 0
3979 0
3980 0
3981 0
3982 0
3983 0
3984 0
3985 0
3986 0
3987 0
3988 0
3989 0
3990 0
3991 0
3992 0
3993 0
3994 0
3995 0
3996 0
3997 0
3998 0
3999 0
4000 0
4001 0
4002 0
4003 0
4004 0
4005 0
4006 0
4007 0
4008 0
4009 0
4010 0
4011 0
4012 0
4013 0
4014 0
4015 0
4016 0
4017 0
4018 0
4019 0
4020 0
4021 0
4022 0
4023 0
4024 0
4025 0
4026 0
4027 0
4028 0
4029 0
4030 0
4031 0
4032 0
4033 0
4034 0
4035 0
4036 0
4037 0
4038 0
4039 0
4040 0
4041 0
4042 0
4043 0
4044 0
4045 0
4046 0
4047 0
4048 0
4049 0
4050 0
4051 0
4052 0
4053 0
4054 0
4055 0
4056 0
4057 0
4058 0
4059 0
4060 0
4061 0
4062 0
4063 0
4064 0
4065 0
4066 0
4067 0
4068 0
4069 0
4070 0
4071 0
4072 0
4073 0
4074 0
4075 0
4076 0
4077 0
4078 0
4079 0
4080 0
4081 0
4082 0
4083 0
4084 0
4085 0
4086 0
4087 0
4088 0
4089 0
4090 0
4091 0
4092 0
4093 0
4094 0
4095 0

4,100 lines not shown · raw message

Part of this message is not shown here. View the raw message.

maintainer
#19 lore raw

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

In reply to Ian Kent
Quoted 8 lines · Ian Kent

Oh .. didn't see this before.

Quoted 1 line

How could it be worse? :P

Hehe, there's an assumption without evidence in there some where.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

I'll check our large file map just to satisfy my curiosity.

Give me a chance and I'll do a couple of patches to add some statistical calculations to cache_dump_cache() so we can see the state of the hash table after a map is loaded.

Here are a couple of patches we can use to check what is going on (my math may be wrong so it would be good if folks could check). They should apply to the git repo source.

The first patch hash-report-stats.patch modifies cache_dump_cache() to report some statistics.

The second patch hash-oaat-algo.patch makes the cache use the Vals proposed oaat algorithm without changing the hash table size for comparison.

I used an indirect map with 35000 entries as a quick check.

There are a couple of problems with this, first the map keys are a bit random and so are not representative of actual maps and since we use multiple caches in v5 the number of entries in a given cache may be quite different from the total number of entries.

But, if my math is correct, we can get some marginally useful information from the experiment.

The results:

Current algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 381 max 501 avg 454.55 std 22.78

oaat algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 402 max 532 avg 454.55 std 22.27

This looks a bit odd, my math is probably broken somehow.

I have to conclude that while the oaat algorithm looks worse some how, if the math is OK, then it is likely that there are more chains closer to the average length with less outliers (smaller variance in chain length) than there are with the current algorithm.

It would be good if we could get some real world numbers for both indirect and direct maps (mainly because direct maps have somewhat different keys, full path compared to directory component).

I will do some more checks with the proposed large hash table size to see if the small table size is hiding any bias in the distribution.

Ian

Make cache_dump_cache() report some statistical measures instead of

From: Ian Kent <[email protected]>

dumping contents of the cache.

This gets a little more complicated with v5 as we have a cache for each map entry which itself can have multiple caches. So hash size for large master maps matters.
---

 Makefile.rules  |    2 +-
 daemon/lookup.c |    3 +++
 lib/cache.c     |   64 +++++++++++++++++++++++++++++++++++++++++++++++++++----
 3 files changed, 63 insertions(+), 6 deletions(-)
Makefile.rules +1 -1
index 30716dc..a59c3dd 100644
@@ -13,7 +13,7 @@ INCFILES = COPYING COPYRIGHT NEWS README* TODO Makefile Makefile.rules \
 INSTALLROOT = $(DESTDIR)
 
 # autofs utility library
-AUTOFS_LIB = ../lib/autofs.a
+AUTOFS_LIB = ../lib/autofs.a -lm
 
 # Compilers, linkers and flags
 # The STRIP defined here *must not* remove any dynamic-loading symbols
daemon/lookup.c +3 -0
index 741d846..a66e3db 100644
@@ -261,6 +261,8 @@ int lookup_nss_read_master(struct master *master, time_t age)
 	return !result;
 }
 
+void cache_dump_cache(struct mapent_cache *mc);
+
 static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t age)
 {
 	struct lookup_mod *lookup;
@@ -296,6 +298,7 @@ static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t a
 	ap->entry->current = map;
 
 	status = lookup->lookup_read_map(ap, age, lookup->context);
+	cache_dump_cache(map->mc);
 
 	map->stale = 0;
 
lib/cache.c +59 -5

80 lines not on this page · raw message

Use proposed oaat algorithm for hash calculation without

From: Ian Kent <[email protected]>

increasing hash table size for comparison against additive algorithm.
---

 lib/cache.c |   29 ++++++++++++++++++-----------
 1 files changed, 18 insertions(+), 11 deletions(-)
lib/cache.c +18 -11
index 258afd3..5f64359 100644
@@ -333,20 +333,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;
 
@@ -355,7 +362,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);
@@ -377,7 +384,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);
@@ -423,7 +430,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)
@@ -584,7 +591,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));
@@ -804,7 +811,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;
 

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#20 lore raw

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

Quoted 13 lines · Ian Kent

I used an indirect map with 35000 entries as a quick check.

There are a couple of problems with this, first the map keys are a bit random and so are not representative of actual maps and since we use multiple caches in v5 the number of entries in a given cache may be quite different from the total number of entries.

But, if my math is correct, we can get some marginally useful information from the experiment.

The results:

Quoted 8 lines

Current algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 381 max 501 avg 454.55 std 22.78

oaat algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 402 max 532 avg 454.55 std 22.27

Here are some more stats.

cache: entries 35000 table size 977 ideal chain length 35.82 chain length: empty 627 min 0 max 284 avg 35.82 std 72.14

cache: entries 35000 table size 977 ideal chain length 35.82 chain length: empty 0 min 17 max 59 avg 35.82 std 6.05

cache: entries 35000 table size 2039 ideal chain length 17.17 chain length: empty 1689 min 0 max 284 avg 17.17 std 53.05

cache: entries 35000 table size 2039 ideal chain length 17.17 chain length: empty 0 min 6 max 32 avg 17.17 std 4.18

cache: entries 35000 table size 4093 ideal chain length 8.55 chain length: empty 3743 min 0 max 284 avg 8.55 std 38.41

cache: entries 35000 table size 4093 ideal chain length 8.55 chain length: empty 2 min 0 max 21 avg 8.55 std 2.99

There's clearly something wrong with my min and probably max calculation but the stats still show some interesting information.

It looks like the additive algorithm is biased toward a small range of hash indexes which becomes more significant as the table size increases. So the distribution is significantly better as table size increases.

I'm not clear on what the graphs (Pauls) are displaying but my impression is that they also show this same distribution bias toward clustering for the additive hash. Assuming they were done using actual map keys that would indicate that the benefit is likely fairly general.

The only question remaining is how large should we make the table. A size of around 4k will lead to a lot of wasted space for many common configurations (including configurations that have many map entries spread over several individual maps) but a size around 1k still gives fairly long chains for large maps.

Suggestions?

PS. I'll need to make a couple of other changes as well, eg. the null map entry cache is typically very small.

Ian

#21 lore raw

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

On Mon, Jan 12, 2009 at 3:02 PM, Ian Kent <[email protected]> wrote:

Here are a couple of patches we can use to check what is going on (my

Quoted 26 lines

math may be wrong so it would be good if folks could check). They should apply to the git repo source.

The first patch hash-report-stats.patch modifies cache_dump_cache() to report some statistics.

The second patch hash-oaat-algo.patch makes the cache use the Vals proposed oaat algorithm without changing the hash table size for comparison.

I used an indirect map with 35000 entries as a quick check.

There are a couple of problems with this, first the map keys are a bit random and so are not representative of actual maps and since we use multiple caches in v5 the number of entries in a given cache may be quite different from the total number of entries.

But, if my math is correct, we can get some marginally useful information from the experiment.

The results:

Current algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 381 max 501 avg 454.55 std 22.78

Quoted 5 lines

oaat algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 402 max 532 avg 454.55 std 22.27

This looks a bit odd, my math is probably broken somehow.

Perhaps you could calculate the median instead of the mean?

I have to conclude that while the oaat algorithm looks worse some how,

Quoted 10 lines

if the math is OK, then it is likely that there are more chains closer to the average length with less outliers (smaller variance in chain length) than there are with the current algorithm.

It would be good if we could get some real world numbers for both indirect and direct maps (mainly because direct maps have somewhat different keys, full path compared to directory component).

I will do some more checks with the proposed large hash table size to see if the small table size is hiding any bias in the distribution.

On Mon, Jan 12, 2009 at 3:58 PM, Ian Kent <[email protected]> wrote:

Here are some more stats.

Quoted 18 lines

cache: entries 35000 table size 977 ideal chain length 35.82 chain length: empty 627 min 0 max 284 avg 35.82 std 72.14

cache: entries 35000 table size 977 ideal chain length 35.82 chain length: empty 0 min 17 max 59 avg 35.82 std 6.05

cache: entries 35000 table size 2039 ideal chain length 17.17 chain length: empty 1689 min 0 max 284 avg 17.17 std 53.05

cache: entries 35000 table size 2039 ideal chain length 17.17 chain length: empty 0 min 6 max 32 avg 17.17 std 4.18

cache: entries 35000 table size 4093 ideal chain length 8.55 chain length: empty 3743 min 0 max 284 avg 8.55 std 38.41

Quoted 6 lines

cache: entries 35000 table size 4093 ideal chain length 8.55 chain length: empty 2 min 0 max 21 avg 8.55 std 2.99

There's clearly something wrong with my min and probably max calculation but the stats still show some interesting information.

Why do you think that you've miscalculated the minimum?

It looks like the additive algorithm is biased toward a small range of

Quoted 7 lines

hash indexes which becomes more significant as the table size increases. So the distribution is significantly better as table size increases.

I'm not clear on what the graphs (Pauls) are displaying but my impression is that they also show this same distribution bias toward clustering for the additive hash. Assuming they were done using actual map keys that would indicate that the benefit is likely fairly general.

I plotted the number of elements in each bucket.

As you now see, the additive hash function doesn't scale.

The only question remaining is how large should we make the table.

Quoted 6 lines

A size of around 4k will lead to a lot of wasted space for many common configurations (including configurations that have many map entries spread over several individual maps) but a size around 1k still gives fairly long chains for large maps.

Suggestions?

Perhaps you could make it configurable?

PS. I'll need to make a couple of other changes as well, eg. the null

Quoted 1 line

map entry cache is typically very small.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#22 lore raw

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

Quoted 37 lines · Paul Wankadia

On Mon, Jan 12, 2009 at 3:02 PM, Ian Kent <[email protected]> wrote:

Here are a couple of patches we can use to check what is going on (my
math may be wrong so it would be good if folks could check). They should
apply to the git repo source.

The first patch hash-report-stats.patch modifies cache_dump_cache() to
report some statistics.

The second patch hash-oaat-algo.patch makes the cache use the Vals
proposed oaat algorithm without changing the hash table size for
comparison.

I used an indirect map with 35000 entries as a quick check.

There are a couple of problems with this, first the map keys are a bit
random and so are not representative of actual maps and since we use
multiple caches in v5 the number of entries in a given cache may be
quite different from the total number of entries.

But, if my math is correct, we can get some marginally useful information from the experiment.

The results:

Current algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 381 max 501 avg 454.55 std 22.78

Quoted 7 lines

oaat algorithm:
cache: entries 35000 table size 77 ideal chain length 454.55 chain length: empty 0 min 402 max 532 avg 454.55 std 22.27

This looks a bit odd, my math is probably broken somehow.

Perhaps you could calculate the median instead of the mean?

I was thinking that the min and max looked a bit odd.
To calculate the median we would have to assume a normal distribution (or find some way to work out what type of distribution it is, too hard) and then it's (min + max)/2.

Quoted 46 lines

I have to conclude that while the oaat algorithm looks worse some how,
if the math is OK, then it is likely that there are more chains closer
to the average length with less outliers (smaller variance in chain
length) than there are with the current algorithm.

It would be good if we could get some real world numbers for both
indirect and direct maps (mainly because direct maps have somewhat
different keys, full path compared to directory component).

I will do some more checks with the proposed large hash table size to
see if the small table size is hiding any bias in the distribution.

On Mon, Jan 12, 2009 at 3:58 PM, Ian Kent <[email protected]> wrote:

Here are some more stats.

cache: entries 35000 table size 977 ideal chain length 35.82 chain length: empty 627 min 0 max 284 avg 35.82 std 72.14

cache: entries 35000 table size 977 ideal chain length 35.82 chain length: empty 0 min 17 max 59 avg 35.82 std 6.05

cache: entries 35000 table size 2039 ideal chain length 17.17 chain length: empty 1689 min 0 max 284 avg 17.17 std 53.05

cache: entries 35000 table size 2039 ideal chain length 17.17 chain length: empty 0 min 6 max 32 avg 17.17 std 4.18

cache: entries 35000 table size 4093 ideal chain length 8.55 chain length: empty 3743 min 0 max 284 avg 8.55 std 38.41

cache: entries 35000 table size 4093 ideal chain length 8.55 chain length: empty 2 min 0 max 21 avg 8.55 std 2.99

Quoted 5 lines

There's clearly something wrong with my min and probably max calculation
but the stats still show some interesting information.

Why do you think that you've miscalculated the minimum?

Well, maybe I haven't but I thought min should be > 0. But, it's not worth worrying about as I think we've managed to show a clear improvement.

Quoted 17 lines

It looks like the additive algorithm is biased toward a small range of
hash indexes which becomes more significant as the table size increases.
So the distribution is significantly better as table size increases.

I'm not clear on what the graphs (Pauls) are displaying but my impression is that they also show this same distribution bias toward
clustering for the additive hash. Assuming they were done using actual
map keys that would indicate that the benefit is likely fairly general.

Quoted 3 lines

I plotted the number of elements in each bucket.

As you now see, the additive hash function doesn't scale.

Sure and now we can say why it doesn't scale in the patch description.

Quoted 12 lines

The only question remaining is how large should we make the table.
A size of around 4k will lead to a lot of wasted space for many common
configurations (including configurations that have many map entries
spread over several individual maps) but a size around 1k still gives
fairly long chains for large maps.

Quoted 3 lines

Suggestions?

Perhaps you could make it configurable?

Perhaps, but I don't think this is the sort of thing that should be configurable so I'd prefer to make it a compile time option rather than a run time configuration setting.

Quoted 6 lines

PS. I'll need to make a couple of other changes as well, eg. the null
map entry cache is typically very small.

maintainer
#23 lore raw

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

Quoted 13 lines · Ian Kent
Quoted 12 lines · Paul Wankadia

The only question remaining is how large should we make the table.
A size of around 4k will lead to a lot of wasted space for many common
configurations (including configurations that have many map entries
spread over several individual maps) but a size around 1k still gives
fairly long chains for large maps.

Quoted 7 lines
Quoted 3 lines

Suggestions?

Perhaps you could make it configurable?

Perhaps, but I don't think this is the sort of thing that should be configurable so I'd prefer to make it a compile time option rather than a run time configuration setting.

I've changed my mind, ;), configurable it is with a default of 977.

Ian

#24 lore raw

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

Quoted 5 lines · Ian Kent

Why do you think that you've miscalculated the minimum?

Well, maybe I haven't but I thought min should be > 0. But, it's not worth worrying about as I think we've managed to show a clear improvement.

The minimum was zero because there were empty buckets.

Quoted 5 lines

I plotted the number of elements in each bucket.

Quoted 2 lines

As you now see, the additive hash function doesn't scale.

Sure and now we can say why it doesn't scale in the patch description.

More importantly, who's the scapegoat? :P

Quoted 5 lines

Perhaps you could make it configurable?

Perhaps, but I don't think this is the sort of thing that should be configurable so I'd prefer to make it a compile time option rather than a run time configuration setting.

On Tue, Jan 13, 2009 at 3:15 PM, Ian Kent <[email protected]> wrote:

I've changed my mind, ;), configurable it is with a default of 977.

The hash function is good now, so the size of the hash table can be a power of two.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#25 lore raw

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

Quoted 10 lines · Paul Wankadia

On Tue, Jan 13, 2009 at 1:24 PM, Ian Kent <[email protected]> wrote:

> Why do you think that you've miscalculated the minimum?

Well, maybe I haven't but I thought min should be > 0. But, it's not worth worrying about as I think we've managed to show a
clear improvement.

The minimum was zero because there were empty buckets.

Probably, but I used a separate variable to count zero buckets so the chain lengths should be at least 1, but hey, unless the analysis here is wrong (and I don't think it is) I'm not not going to spend time on it.

Quoted 10 lines

> I plotted the number of elements in each bucket. >
> As you now see, the additive hash function doesn't scale.

Sure and now we can say why it doesn't scale in the patch description.

More importantly, who's the scapegoat? :P

That would be me, ;)

Quoted 10 lines

> Perhaps you could make it configurable?

Perhaps, but I don't think this is the sort of thing that should be
configurable so I'd prefer to make it a compile time option rather than
a run time configuration setting.

Quoted 7 lines

On Tue, Jan 13, 2009 at 3:15 PM, Ian Kent <[email protected]> wrote:

I've changed my mind, ;), configurable it is with a default of 977.

The hash function is good now, so the size of the hash table can be a power of two.

So your suggesting 1024 then, does it matter?

Ian

#26 lore raw

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

Quoted 3 lines · Ian Kent

More importantly, who's the scapegoat? :P

That would be me, ;)

It seems that autofs v5 doesn't read an indirect map into the cache unless ghosting is enabled, so I'm thinking about adding a map option to force the read. Has the file map reloading logic changed significantly since autofs v4?

Quoted 4 lines

The hash function is good now, so the size of the hash table can be a

Quoted 1 line

power of two.

So your suggesting 1024 then, does it matter?

%1024 should become &1023 due to strength reduction, but it's not overly important.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#27 lore raw

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

Quoted 10 lines · Paul Wankadia

On Tue, Jan 13, 2009 at 4:19 PM, Ian Kent <[email protected]> wrote:

> More importantly, who's the scapegoat? :P

That would be me, ;)

It seems that autofs v5 doesn't read an indirect map into the cache unless ghosting is enabled, so I'm thinking about adding a map option to force the read. Has the file map reloading logic changed significantly since autofs v4?

It's a bit hard to give a good answer to that as there have been so many changes but, having said that, it shouldn't have changed much except for the obvious one that it tries not to read the entire map unless it has to. Adding the "--ghost" or "browse" option will cause it to read the entire map. Also, the internal default, which is "browse" enabled by default, is overridden by the default installed configuration with BROWSE_MODE="no" so v5 behaves the same as v4.

Quoted 11 lines

> The hash function is good now, so the size of the hash table can be a
> power of two.

So your suggesting 1024 then, does it matter?

%1024 should become &1023 due to strength reduction, but it's not overly important.

#28 lore raw

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

Quoted 5 lines · Ian Kent

It seems that autofs v5 doesn't read an indirect map into the cache

Quoted 3 lines

unless ghosting is enabled, so I'm thinking about adding a map option to force the read. Has the file map reloading logic changed significantly since autofs v4?

Quoted 7 lines

It's a bit hard to give a good answer to that as there have been so many changes but, having said that, it shouldn't have changed much except for the obvious one that it tries not to read the entire map unless it has to. Adding the "--ghost" or "browse" option will cause it to read the entire map. Also, the internal default, which is "browse" enabled by default, is overridden by the default installed configuration with BROWSE_MODE="no" so v5 behaves the same as v4.

Sorry, I meant the logic that reloads the file map if it's been modified. I know that autofs v4 checked the mtime, but I can't see where autofs v5 does that.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#29 lore raw

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

Quoted 24 lines · Paul Wankadia

On Wed, Jan 14, 2009 at 7:47 PM, Ian Kent <[email protected]> wrote:

> It seems that autofs v5 doesn't read an indirect map into the cache
> unless ghosting is enabled, so I'm thinking about adding a map option
> to force the read. Has the file map reloading logic changed > significantly since autofs v4?

It's a bit hard to give a good answer to that as there have been so many
changes but, having said that, it shouldn't have changed much except for
the obvious one that it tries not to read the entire map unless it has
to. Adding the "--ghost" or "browse" option will cause it to read the
entire map. Also, the internal default, which is "browse" enabled by
default, is overridden by the default installed configuration with
BROWSE_MODE="no" so v5 behaves the same as v4.

Quoted 3 lines

Sorry, I meant the logic that reloads the file map if it's been modified. I know that autofs v4 checked the mtime, but I can't see where autofs v5 does that.

Yeah, I didn't think I got rid of that.

But the check for a mismatch between the cache and a file key lookup should be sufficient to only cause a read when the map has actually changed. I guess we could get multiple HUP signals, one following just after the other has finished, but that would be a system admin error and you'd probably want to know about that since we can't make a similar check some other map sources. I probably should get around to removing the mtime stuff all-together, perhaps you could let me know if things work as they should (or not) so I can clean (or fix) that up.

Ian

#30 lore raw

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

Quoted 6 lines · Ian Kent

Sorry, I meant the logic that reloads the file map if it's been

Quoted 2 lines

modified. I know that autofs v4 checked the mtime, but I can't see where autofs v5 does that.

Yeah, I didn't think I got rid of that.

Quoted 8 lines

But the check for a mismatch between the cache and a file key lookup should be sufficient to only cause a read when the map has actually changed. I guess we could get multiple HUP signals, one following just after the other has finished, but that would be a system admin error and you'd probably want to know about that since we can't make a similar check some other map sources. I probably should get around to removing the mtime stuff all-together, perhaps you could let me know if things work as they should (or not) so I can clean (or fix) that up.

Are you saying that every lookup for an indirect map will hit the file? If that's the case, then what's the point of the cache? If that's not the case, but you're not checking the mtime either, then how do you know when the file has been modified? (Please excuse the silly questions.)

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#31 lore raw

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

Quoted 28 lines · Paul Wankadia

On Thu, Jan 15, 2009 at 12:17 AM, Ian Kent <[email protected]> wrote:

> Sorry, I meant the logic that reloads the file map if it's been
> modified. I know that autofs v4 checked the mtime, but I can't see
> where autofs v5 does that.

Yeah, I didn't think I got rid of that.

But the check for a mismatch between the cache and a file key lookup
should be sufficient to only cause a read when the map has actually
changed. I guess we could get multiple HUP signals, one following just
after the other has finished, but that would be a system admin error and
you'd probably want to know about that since we can't make a similar
check some other map sources. I probably should get around to removing
the mtime stuff all-together, perhaps you could let me know if things
work as they should (or not) so I can clean (or fix) that up.

Quoted 6 lines

Are you saying that every lookup for an indirect map will hit the file? If that's the case, then what's the point of the cache? If that's not the case, but you're not checking the mtime either, then how do you know when the file has been modified? (Please excuse the silly questions.)

Umm .... yeah (runs and hides behind a large bookshelf in office).

This isn't a silly question at all.

It's something that could make the poor performance of the hash function look efficient and needs to be fixed (at least it matters for large maps).

In the beginning I used the cache, well, like a cache, and required a HUP signal to update the maps. That was seen to be "just not good enough" as people required the map entry used to be up to date at the time of use. This lead to the cache gradually becoming more of a reference used to check currency of map entries to trigger map re-reads when differences were spotted. This seemed better than just using periodic map re-reads and seems to work OK. Remember that in v5 the cache starts empty for nobrowse indirect mounts and old entries get cleaned out upon receiving a HUP signal. That's OK for maps that have direct key lookup but for really large file maps it's almost certainly worse than the poor hashing algorithm.

We use the cache a lot, for a bunch of other checks, to maintain context for multi-mount map entries and for direct maps. Map entries with multiple offsets (the so called multi-mount map entries) the entry is expanded, each offset added to the cache and a mount trigger mounted. This is part of the mount/umount "as you go" functionality in v5 which is really useful for servers with really large export lists, for example. Because of the nature of direct mounts the entire map must be read at startup and a HUP signal must be sent to the daemon for changes to be seen and we never go to the map during lookups, only the cache.

But onto the problem.

It should be fairly straight forward to start using the map mtime again. The time stamp on cache entries that have been added will be later than the mtime if the file map hasn't changed so we can use that. But we also need to prevent re-reading the map from the beginning as we populate the cache. I was thinking that I could add each entry read during a lookup to the cache so that they would be found on subsequent lookups (as long as the mtime is earlier than the time stamp). Additionally, I could keep track of the file position so I don't read entries already read. It likely won't be quite as simple in the end but we really need to do something to for really large maps.

Any other thoughts?

Ian

#32 lore raw

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

Quoted 13 lines · Ian Kent

But onto the problem.

It should be fairly straight forward to start using the map mtime again. The time stamp on cache entries that have been added will be later than the mtime if the file map hasn't changed so we can use that. But we also need to prevent re-reading the map from the beginning as we populate the cache. I was thinking that I could add each entry read during a lookup to the cache so that they would be found on subsequent lookups (as long as the mtime is earlier than the time stamp). Additionally, I could keep track of the file position so I don't read entries already read. It likely won't be quite as simple in the end but we really need to do something to for really large maps.

Quoted 1 line

Any other thoughts?

Sure, just read the whole map. Even large maps aren't that big. What are we talking, 10k? 50k? You're better off reading the whole thing in at once.

Cheers,
Jeff

maintainer
#33 lore raw

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

Quoted 15 lines · Jeff Moyer
Quoted 13 lines · Ian Kent

But onto the problem.

It should be fairly straight forward to start using the map mtime again. The time stamp on cache entries that have been added will be later than the mtime if the file map hasn't changed so we can use that. But we also need to prevent re-reading the map from the beginning as we populate the cache. I was thinking that I could add each entry read during a lookup to the cache so that they would be found on subsequent lookups (as long as the mtime is earlier than the time stamp). Additionally, I could keep track of the file position so I don't read entries already read. It likely won't be quite as simple in the end but we really need to do something to for really large maps.

Quoted 5 lines
Quoted 1 line

Any other thoughts?

Sure, just read the whole map. Even large maps aren't that big. What are we talking, 10k? 50k? You're better off reading the whole thing in at once.

Yeah, that would be best. I'll have a think about how to detect when to do that. Maybe we can rip out that convoluted change detection logic for file maps, after all they should be fairly simple to deal with.

Ian

#34 lore raw

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

Quoted 7 lines · Ian Kent
Quoted 3 lines

Sure, just read the whole map. Even large maps aren't that big. What are we talking, 10k? 50k? You're better off reading the whole thing in at once.

Yeah, that would be best. I'll have a think about how to detect when to do that. Maybe we can rip out that convoluted change detection logic for file maps, after all they should be fairly simple to deal with.

If inotify can play nicely with the existing event handling, then it could be worth considering.

#35 lore raw

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

Quoted 6 lines · Paul Wankadia
Quoted 4 lines · Ian Kent
Quoted 3 lines

Sure, just read the whole map. Even large maps aren't that big. What are we talking, 10k? 50k? You're better off reading the whole thing in at once.

Quoted 6 lines
Quoted 3 lines

Yeah, that would be best. I'll have a think about how to detect when to do that. Maybe we can rip out that convoluted change detection logic for file maps, after all they should be fairly simple to deal with.

If inotify can play nicely with the existing event handling, then it could be worth considering.

Ian was coming up with a scheme to only read part of the map. Because the map is just a flat file, he surmised that a lookup could happen like so:

first lookup, start at the beginning of the file

walk the entries, adding each to the cache until you find the entry you're looking for

cache the offset into the file and stop reading

When a cache miss comes in, start reading the file again at the last offset (so long as the file hasn't changed on disk)

My argument is that you're not really saving much. Just cache the whole file. I agree that you probably want to detect changes, still. For that, you can use mtime or inotify. You could make a case for either side, though I think I'd argue for keeping the mtime approach (as the map may change multiple times before we actually try to read it, and doing the read in the lookup path really shouldn't be that big of a deal). Of course, I haven't profiled this, so that may be worth doing.

Cheers,
Jeff

#36 lore raw

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

Quoted 7 lines · Jeff Moyer

My argument is that you're not really saving much. Just cache the whole file. I agree that you probably want to detect changes, still. For that, you can use mtime or inotify. You could make a case for either side, though I think I'd argue for keeping the mtime approach (as the map may change multiple times before we actually try to read it, and doing the read in the lookup path really shouldn't be that big of a deal). Of course, I haven't profiled this, so that may be worth doing.

If we can simply flag the cached version as stale, then lazy reloads should be possible.

maintainer
#37 lore raw

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

Quoted 10 lines · Paul Wankadia
Quoted 7 lines · Jeff Moyer

My argument is that you're not really saving much. Just cache the whole file. I agree that you probably want to detect changes, still. For that, you can use mtime or inotify. You could make a case for either side, though I think I'd argue for keeping the mtime approach (as the map may change multiple times before we actually try to read it, and doing the read in the lookup path really shouldn't be that big of a deal). Of course, I haven't profiled this, so that may be worth doing.

Quoted 2 lines

If we can simply flag the cached version as stale, then lazy reloads should be possible.

Maybe not.

The layer of code above the lookup modules does the re-loads but it is general wrt. the map type so for a "nobrowse" map it won't read the map. I'm not sure yet that putting special case exceptions in that code is a good thing to do or even straight forward. But, for the large map case, we can consider reading the entire map an expensive operation, so if we did change the layer above and we found the map needed to be modified then marked the map as stale we would need to scan the file map for the key (as the map is out of date) and then read the whole map later. That means we would end up reading the map at least one and a half times (on average) instead of once (assuming no lookups between marking the map stale and re-reading).

I'm tending toward reading the map during the lookup so the map is up to date when we look for the key in the cache.

Ian

maintainer
#38 lore raw

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

Quoted 14 lines · Ian Kent
Quoted 10 lines · Paul Wankadia
Quoted 7 lines · Jeff Moyer

My argument is that you're not really saving much. Just cache the whole file. I agree that you probably want to detect changes, still. For that, you can use mtime or inotify. You could make a case for either side, though I think I'd argue for keeping the mtime approach (as the map may change multiple times before we actually try to read it, and doing the read in the lookup path really shouldn't be that big of a deal). Of course, I haven't profiled this, so that may be worth doing.

Quoted 2 lines

If we can simply flag the cached version as stale, then lazy reloads should be possible.

Quoted 6 lines

Maybe not.

The layer of code above the lookup modules does the re-loads but it is general wrt. the map type so for a "nobrowse" map it won't read the map. I'm not sure yet that putting special case exceptions in that code is a good thing to do or even straight forward. But, for the large map case,

Or maybe I'm talking nonsense as it looks like I've actually got plenty of map type context in the layer above, hehe.

Quoted 18 lines

we can consider reading the entire map an expensive operation, so if we did change the layer above and we found the map needed to be modified then marked the map as stale we would need to scan the file map for the key (as the map is out of date) and then read the whole map later. That means we would end up reading the map at least one and a half times (on average) instead of once (assuming no lookups between marking the map stale and re-reading).

I'm tending toward reading the map during the lookup so the map is up to date when we look for the key in the cache.

Ian

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#39 lore raw

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

Quoted 17 lines · Ian Kent
Quoted 16 lines · Ian Kent
Quoted 10 lines · Paul Wankadia
Quoted 7 lines · Jeff Moyer

My argument is that you're not really saving much. Just cache the whole file. I agree that you probably want to detect changes, still. For that, you can use mtime or inotify. You could make a case for either side, though I think I'd argue for keeping the mtime approach (as the map may change multiple times before we actually try to read it, and doing the read in the lookup path really shouldn't be that big of a deal). Of course, I haven't profiled this, so that may be worth doing.

Quoted 2 lines

If we can simply flag the cached version as stale, then lazy reloads should be possible.

Maybe not.

Quoted 18 lines
Quoted 4 lines

The layer of code above the lookup modules does the re-loads but it is general wrt. the map type so for a "nobrowse" map it won't read the map. I'm not sure yet that putting special case exceptions in that code is a good thing to do or even straight forward. But, for the large map case,

Or maybe I'm talking nonsense as it looks like I've actually got plenty of map type context in the layer above, hehe.

Quoted 10 lines

we can consider reading the entire map an expensive operation, so if we did change the layer above and we found the map needed to be modified then marked the map as stale we would need to scan the file map for the key (as the map is out of date) and then read the whole map later. That means we would end up reading the map at least one and a half times (on average) instead of once (assuming no lookups between marking the map stale and re-reading).

I'm tending toward reading the map during the lookup so the map is up to date when we look for the key in the cache.

Or maybe not.

If we take advantage of the existing code to mark the map as stale and handle the re-read and we accept the overhead of scanning the file map while waiting for the update something like this could be all that's needed.

autofs-5.0.4 - always read file maps

From: Ian Kent <[email protected]>

---

 daemon/lookup.c       |    9 ++++++---
 modules/lookup_file.c |   11 ++++++++++-
 2 files changed, 16 insertions(+), 4 deletions(-)
daemon/lookup.c +6 -3
index 741d846..b954045 100644
@@ -283,10 +283,13 @@ static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t a
 	 * for the fail cases to function correctly and to cache the
 	 * lookup handle.
 	 *
-	 * We always need to whole map for direct mounts in order to
-	 * mount the triggers.
+	 * We always need to read the whole map for direct mounts in
+	 * order to mount the triggers. We also want to read the whole
+	 * map if it's a file map to avoid potentially lengthy linear
+	 * file scanning.
 	 */
-	if (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type != LKP_DIRECT)
+	if (strcmp(map->type, "file") ||
+	    (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type != LKP_DIRECT))
 		return NSS_STATUS_SUCCESS;
 
 	if (!map->stale)
modules/lookup_file.c +10 -1
index 95b9f6f..9a1c39b 100644
@@ -93,7 +93,6 @@ int lookup_init(const char *mapfmt, int argc, const char *const *argv, void **co
 		     argv[0]);
 		return 1;
 	}
-		
 	ctxt->mtime = st.st_mtime;
 
 	if (!mapfmt)
@@ -1064,7 +1063,16 @@ int lookup_mount(struct autofs_point *ap, const char *name, int name_len, void *
 	if (ap->type == LKP_INDIRECT && *key != '/') {
 		char *lkp_key;
 
+		/*
+		 * We can skip the map lookup and cache update altogether
+		 * if we know the map hasn't been modified since it was
+		 * last read.
+		 */
 		cache_readlock(mc);
+		me = cache_lookup_first(mc);
+		if (me && ctxt->mtime <= me->age)
+			goto do_lookup;
+
 		me = cache_lookup_distinct(mc, key);
 		if (me && me->multi)
 			lkp_key = strdup(me->multi->key);
@@ -1088,6 +1096,7 @@ int lookup_mount(struct autofs_point *ap, const char *name, int name_len, void *
 	}
 
 	cache_readlock(mc);
+do_lookup:
 	me = cache_lookup(mc, key);
 	/* Stale mapent => check for entry in alternate source or wildcard */
 	if (me && !me->mapent) {
#40 lore raw

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

Quoted 54 lines · Ian Kent
Quoted 7 lines
Quoted 7 lines

If we can simply flag the cached version as stale, then lazy reloads

Quoted 1 line

should be possible.

Maybe not.

The layer of code above the lookup modules does the re-loads but it is general wrt. the map type so for a "nobrowse" map it won't read the

map.

Quoted 15 lines
Quoted 2 lines

I'm not sure yet that putting special case exceptions in that code is a good thing to do or even straight forward. But, for the large map case,

Or maybe I'm talking nonsense as it looks like I've actually got plenty of map type context in the layer above, hehe.

Quoted 9 lines

we can consider reading the entire map an expensive operation, so if we did change the layer above and we found the map needed to be modified then marked the map as stale we would need to scan the file map for the key (as the map is out of date) and then read the whole map later. That means we would end up reading the map at least one and a half times (on average) instead of once (assuming no lookups between marking the map stale and re-reading).

I'm tending toward reading the map during the lookup so the map is up

to

Quoted 1 line
Quoted 1 line

date when we look for the key in the cache.

Or maybe not.

If we take advantage of the existing code to mark the map as stale and handle the re-read and we accept the overhead of scanning the file map while waiting for the update something like this could be all that's needed.

autofs-5.0.4 - always read file maps

From: Ian Kent <[email protected]>

---

 daemon/lookup.c       |    9 ++++++---
 modules/lookup_file.c |   11 ++++++++++-
 2 files changed, 16 insertions(+), 4 deletions(-)
daemon/lookup.c +0 -0
index 741d846..b954045 100644
@@ -283,10 +283,13 @@ static int do_read_map(struct autofs_point *ap,

struct map_source *map, time_t a
* for the fail cases to function correctly and to cache the
* lookup handle.
*

daemon/lookup.c static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t a · line 291

Quoted 9 lines
daemon/lookup.c +5 -3
-        * We always need to whole map for direct mounts in order to
-        * mount the triggers.
+        * We always need to read the whole map for direct mounts in
+        * order to mount the triggers. We also want to read the whole
+        * map if it's a file map to avoid potentially lengthy linear
+        * file scanning.
        */
-       if (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type != LKP_DIRECT)
+       if (strcmp(map->type, "file") ||

I suspect that you want && instead.

+ (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type != LKP_DIRECT))

Quoted 19 lines
               return NSS_STATUS_SUCCESS;

       if (!map->stale)
modules/lookup_file.c +0 -1
index 95b9f6f..9a1c39b 100644
@@ -93,7 +93,6 @@ int lookup_init(const char *mapfmt, int argc, const char
 *const *argv, void **co
                    argv[0]);
               return 1;
       }
-
       ctxt->mtime = st.st_mtime;
 

if (!mapfmt)

modules/lookup_file.c +0 -0
@@ -1064,7 +1063,16 @@ int lookup_mount(struct autofs_point *ap, const char
 *name, int name_len, void *
       if (ap->type == LKP_INDIRECT && *key != '/') {

modules/lookup_file.c int lookup_mount(struct autofs_point *ap, const char · line 1074

Quoted 10 lines
modules/lookup_file.c +7 -0
               char *lkp_key;
 
+               /*
+                * We can skip the map lookup and cache update altogether
+                * if we know the map hasn't been modified since it was
+                * last read.
+                */
               cache_readlock(mc);
+               me = cache_lookup_first(mc);
+               if (me && ctxt->mtime <= me->age)

You have to call stat(2) or fstat(2) at some point or else ctxt->mtime will never change.

+ goto do_lookup;

My brain is bleeding.

+

Quoted 12 lines
modules/lookup_file.c +1 -0
               me = cache_lookup_distinct(mc, key);
               if (me && me->multi)
                       lkp_key = strdup(me->multi->key);
@@ -1088,6 +1096,7 @@ int lookup_mount(struct autofs_point *ap, const char
 *name, int name_len, void *
       }
 
       cache_readlock(mc);
+do_lookup:
       me = cache_lookup(mc, key);
       /* Stale mapent => check for entry in alternate source or wildcard

*/

Quoted 4 lines
       if (me && !me->mapent) {

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#41 lore raw

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

Quoted 86 lines · Paul Wankadia

On Fri, Jan 16, 2009 at 12:43 PM, Ian Kent <[email protected]> wrote:

> > > If we can simply flag the cached version as stale, then lazy reloads
> > > should be possible.
> >
> > Maybe not.
> >
> > The layer of code above the lookup modules does the re-loads but it is
> > general wrt. the map type so for a "nobrowse" map it won't read the map.
> > I'm not sure yet that putting special case exceptions in that code is a
> > good thing to do or even straight forward. But, for the large map case,
>
> Or maybe I'm talking nonsense as it looks like I've actually got plenty
> of map type context in the layer above, hehe.
>
> > we can consider reading the entire map an expensive operation, so if we
> > did change the layer above and we found the map needed to be modified
> > then marked the map as stale we would need to scan the file map for the
> > key (as the map is out of date) and then read the whole map later. That
> > means we would end up reading the map at least one and a half times (on
> > average) instead of once (assuming no lookups between marking the map
> > stale and re-reading).
> >
> > I'm tending toward reading the map during the lookup so the map is up to
> > date when we look for the key in the cache.

Or maybe not.

If we take advantage of the existing code to mark the map as stale and
handle the re-read and we accept the overhead of scanning the file map
while waiting for the update something like this could be all that's
needed.

autofs-5.0.4 - always read file maps

From: Ian Kent <[email protected]>

---

daemon/lookup.c | 9 ++++++---
modules/lookup_file.c | 11 ++++++++++-
2 files changed, 16 insertions(+), 4 deletions(-)

diff --git a/daemon/lookup.c b/daemon/lookup.c index 741d846..b954045 100644
--- a/daemon/lookup.c
+++ b/daemon/lookup.c
@@ -283,10 +283,13 @@ static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t a
* for the fail cases to function correctly and to
cache the
* lookup handle.
*
- * We always need to whole map for direct mounts in
order to
- * mount the triggers.
+ * We always need to read the whole map for direct
mounts in
+ * order to mount the triggers. We also want to read
the whole
+ * map if it's a file map to avoid potentially lengthy
linear
+ * file scanning.
*/
- if (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type !=
LKP_DIRECT)
+ if (strcmp(map->type, "file") ||

Quoted 1 line

I suspect that you want && instead.

Yeah, I think that isn't quite right but I also think that && won't fix it. I'll think on that one again.

Quoted 36 lines

        +           (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type !=
        LKP_DIRECT))
                       return NSS_STATUS_SUCCESS;
        
               if (!map->stale)
        diff --git a/modules/lookup_file.c b/modules/lookup_file.c
        index 95b9f6f..9a1c39b 100644
        --- a/modules/lookup_file.c
        +++ b/modules/lookup_file.c
        @@ -93,7 +93,6 @@ int lookup_init(const char *mapfmt, int
        argc, const char *const *argv, void **co
                            argv[0]);
                       return 1;
               }
        -
               ctxt->mtime = st.st_mtime;
        
               if (!mapfmt)
        @@ -1064,7 +1063,16 @@ int lookup_mount(struct autofs_point
        *ap, const char *name, int name_len, void *
               if (ap->type == LKP_INDIRECT && *key != '/') {
                       char *lkp_key;
        
        +               /*
        +                * We can skip the map lookup and cache update
        altogether
        +                * if we know the map hasn't been modified
        since it was
        +                * last read.
        +                */
                       cache_readlock(mc);
        +               me = cache_lookup_first(mc);
        +               if (me && ctxt->mtime <= me->age)
Quoted 2 lines

You have to call stat(2) or fstat(2) at some point or else ctxt->mtime will never change.

We set the mtime when we read the entire map, see modules/lookup_file.c:lookup_read_map(). This is totally taking advantage of the existing code to read a map that is marked as stale. It doesn't however attempt to simplify the code which works out if we need to mark the map stale but we probably don't want to anyway as we need to ensure we use up to date entries for lookups done while waiting for the map update to be done.

Quoted 24 lines

+ goto do_lookup;

My brain is bleeding.

        +
                       me = cache_lookup_distinct(mc, key);
                       if (me && me->multi)
                               lkp_key = strdup(me->multi->key);
        @@ -1088,6 +1096,7 @@ int lookup_mount(struct autofs_point
        *ap, const char *name, int name_len, void *
               }
        
               cache_readlock(mc);
        +do_lookup:
               me = cache_lookup(mc, key);
               /* Stale mapent => check for entry in alternate source
        or wildcard */
               if (me && !me->mapent) {
maintainer
#42 lore raw

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

Quoted 26 lines · Ian Kent
Quoted 26 lines

diff --git a/daemon/lookup.c b/daemon/lookup.c index 741d846..b954045 100644
--- a/daemon/lookup.c
+++ b/daemon/lookup.c
@@ -283,10 +283,13 @@ static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t a
* for the fail cases to function correctly and to
cache the
* lookup handle.
*
- * We always need to whole map for direct mounts in
order to
- * mount the triggers.
+ * We always need to read the whole map for direct
mounts in
+ * order to mount the triggers. We also want to read
the whole
+ * map if it's a file map to avoid potentially lengthy
linear
+ * file scanning.
*/
- if (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type !=
LKP_DIRECT)
+ if (strcmp(map->type, "file") ||

Quoted 4 lines
Quoted 1 line

I suspect that you want && instead.

Yeah, I think that isn't quite right but I also think that && won't fix it. I'll think on that one again.

On second thoughts, I think you were right the first time, && it is.

But the real question is whether we are willing to put up with the overhead of file scan lookups while we wait for the a map read to complete. That probably won't happen all that often so I'm thinking maybe it's ok.

Ian

#43 lore raw

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

In reply to Ian Kent
Quoted 5 lines · Ian Kent

+ if (me && ctxt->mtime <= me->age)

Quoted 3 lines

You have to call stat(2) or fstat(2) at some point or else ctxt->mtime will never change.

Quoted 7 lines

We set the mtime when we read the entire map, see modules/lookup_file.c:lookup_read_map(). This is totally taking advantage of the existing code to read a map that is marked as stale. It doesn't however attempt to simplify the code which works out if we need to mark the map stale but we probably don't want to anyway as we need to ensure we use up to date entries for lookups done while waiting for the map update to be done.

Sorry, I don't understand how that condition will evaluate to false. You won't read the map until ctxt->mtime changes, but it won't change until you read the map.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#44 lore raw

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

Quoted 22 lines · Paul Wankadia

On Fri, Jan 16, 2009 at 3:21 PM, Ian Kent <[email protected]> wrote:

> + if (me && ctxt->mtime <= me->age)
>
> You have to call stat(2) or fstat(2) at some point or else ctxt->mtime
> will never change.

We set the mtime when we read the entire map, see modules/lookup_file.c:lookup_read_map(). This is totally taking
advantage of the existing code to read a map that is marked as stale. It
doesn't however attempt to simplify the code which works out if we need
to mark the map stale but we probably don't want to anyway as we need to
ensure we use up to date entries for lookups done while waiting for the
map update to be done.

Quoted 3 lines

Sorry, I don't understand how that condition will evaluate to false. You won't read the map until ctxt->mtime changes, but it won't change until you read the map.

Mmmm .. before that last change I was assuming the code which sets the stale flag would cause the read but then I removed that bit and ... oops!

Ian

maintainer
#45 lore raw

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

Quoted 23 lines · Ian Kent
Quoted 22 lines · Paul Wankadia

On Fri, Jan 16, 2009 at 3:21 PM, Ian Kent <[email protected]> wrote:

> + if (me && ctxt->mtime <= me->age)
>
> You have to call stat(2) or fstat(2) at some point or else ctxt->mtime
> will never change.

We set the mtime when we read the entire map, see modules/lookup_file.c:lookup_read_map(). This is totally taking
advantage of the existing code to read a map that is marked as stale. It
doesn't however attempt to simplify the code which works out if we need
to mark the map stale but we probably don't want to anyway as we need to
ensure we use up to date entries for lookups done while waiting for the
map update to be done.

Quoted 7 lines
Quoted 3 lines

Sorry, I don't understand how that condition will evaluate to false. You won't read the map until ctxt->mtime changes, but it won't change until you read the map.

Mmmm .. before that last change I was assuming the code which sets the stale flag would cause the read but then I removed that bit and ... oops!

Because, after a mount lookup we check the stale status and queue a map read if the map is stale. But then I went and removed the bit that sets the map stale because it's lazy in identifying if the map has changed so we could get quite a few mount lookups before a map read gets queued. I'll add back the stat(2) I originally had their before I posted the patch.

I'm also thinking of checking if a map read task is in progress when a mount lookup comes in and waiting for it to complete before continuing with the lookup (to reduce the number of file scans a bit). But I'll need to have a look around to see if that will be a problem.

Ian

#46 lore raw

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

Quoted 8 lines · Ian Kent
Quoted 7 lines

Sorry, I don't understand how that condition will evaluate to false.

Quoted 2 lines

You won't read the map until ctxt->mtime changes, but it won't change until you read the map.

Mmmm .. before that last change I was assuming the code which sets the stale flag would cause the read but then I removed that bit and ... oops!

Quoted 6 lines

Because, after a mount lookup we check the stale status and queue a map read if the map is stale. But then I went and removed the bit that sets the map stale because it's lazy in identifying if the map has changed so we could get quite a few mount lookups before a map read gets queued. I'll add back the stat(2) I originally had their before I posted the patch.

Thanks!

I'm also thinking of checking if a map read task is in progress when a

Quoted 3 lines

mount lookup comes in and waiting for it to complete before continuing with the lookup (to reduce the number of file scans a bit). But I'll need to have a look around to see if that will be a problem.

Is there a design document for autofs v5 that you're permitted to share?

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#47 lore raw

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

Quoted 37 lines · Paul Wankadia

On Fri, Jan 16, 2009 at 5:39 PM, Ian Kent <[email protected]> wrote:

> > Sorry, I don't understand how that condition will evaluate to false.
> > You won't read the map until ctxt->mtime changes, but it won't change
> > until you read the map.
>
> Mmmm .. before that last change I was assuming the code which sets the
> stale flag would cause the read but then I removed that bit and ...
> oops!

Because, after a mount lookup we check the stale status and queue a map
read if the map is stale. But then I went and removed the bit that sets
the map stale because it's lazy in identifying if the map has changed so
we could get quite a few mount lookups before a map read gets queued.
I'll add back the stat(2) I originally had their before I posted the
patch.

Thanks!

I'm also thinking of checking if a map read task is in progress when a
mount lookup comes in and waiting for it to complete before continuing
with the lookup (to reduce the number of file scans a bit). But I'll
need to have a look around to see if that will be a problem.

Quoted 2 lines

Is there a design document for autofs v5 that you're permitted to share?

There isn't, but even of there were it wouldn't have a level of detail that would be useful in cases like this and if it did it would have become hopelessly out of date as time has passed.

However, the attached pdf, written by Jeff and myself, has a high level overview of v5 and what it seeks to achieve.

Ian

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

#48 lore raw

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

Quoted 9 lines · Ian Kent

Is there a design document for autofs v5 that you're permitted to

Quoted 1 line

share?

There isn't, but even of there were it wouldn't have a level of detail that would be useful in cases like this and if it did it would have become hopelessly out of date as time has passed.

However, the attached pdf, written by Jeff and myself, has a high level overview of v5 and what it seeks to achieve.

Cool, thanks.

It's just that your earlier comment regarding a concurrency issue led me to wonder about the use of Pthreads. In particular, I'm not sure what the rationale was, but I'd also like to understand the control flow, so that's why I was interested in a design document of some sort.

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#49 lore raw

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

Quoted 18 lines · Paul Wankadia

On Sun, Jan 18, 2009 at 2:26 PM, Ian Kent <[email protected]> wrote:

> Is there a design document for autofs v5 that you're permitted to
> share?

There isn't, but even of there were it wouldn't have a level of detail
that would be useful in cases like this and if it did it would have
become hopelessly out of date as time has passed.

However, the attached pdf, written by Jeff and myself, has a high level
overview of v5 and what it seeks to achieve.

Quoted 7 lines

Cool, thanks.

It's just that your earlier comment regarding a concurrency issue led me to wonder about the use of Pthreads. In particular, I'm not sure what the rationale was, but I'd also like to understand the control flow, so that's why I was interested in a design document of some sort.

Right.

One of the things that v5 does is to move the master map parsing out of the init script and into the daemon itself. That means that the daemon then has to manage each of the master map mounts as well. Using individual sub-processes has a whole set of problems related to the supervising process communicating with and knowing the state of those sub-processes so v5 changed to a threaded model which of course has it's own set of difficulties.

Ian

#50 lore raw

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

Quoted 8 lines · Ian Kent

It's just that your earlier comment regarding a concurrency issue led

Quoted 4 lines

me to wonder about the use of Pthreads. In particular, I'm not sure what the rationale was, but I'd also like to understand the control flow, so that's why I was interested in a design document of some sort.

Right.

Quoted 7 lines

One of the things that v5 does is to move the master map parsing out of the init script and into the daemon itself. That means that the daemon then has to manage each of the master map mounts as well. Using individual sub-processes has a whole set of problems related to the supervising process communicating with and knowing the state of those sub-processes so v5 changed to a threaded model which of course has it's own set of difficulties.

Does the daemon need multiple processes/threads because of the ioctl(2) calls that block?

On a related note, is the autofs device a step towards a completely revised kernel interface? I've started to contemplate the use of socket pairs instead of pipes and ioctl(2) calls. (NBD seems to be a simple example of this style.)

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#51 lore raw

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

Quoted 30 lines · Paul Wankadia

On Mon, Jan 19, 2009 at 1:03 PM, Ian Kent <[email protected]> wrote:

> It's just that your earlier comment regarding a concurrency issue led
> me to wonder about the use of Pthreads. In particular, I'm not sure
> what the rationale was, but I'd also like to understand the control
> flow, so that's why I was interested in a design document of some
> sort.

Right.

One of the things that v5 does is to move the master map parsing out of
the init script and into the daemon itself. That means that the daemon
then has to manage each of the master map mounts as well. Using
individual sub-processes has a whole set of problems related to the
supervising process communicating with and knowing the state of those
sub-processes so v5 changed to a threaded model which of course has it's
own set of difficulties.

Quoted 2 lines

Does the daemon need multiple processes/threads because of the ioctl(2) calls that block?

A whole bunch of things can block, for example stat(2) on a path against a down server.

There is one thread for each master map mount which creates worker threads to do mounts and expires. Ideally any mount blocking will not affect other mounts and hopefully an expire blocked for some reason won't stop mount requests. That seems to pretty much work now so things aren't too bad.

Quoted 5 lines

On a related note, is the autofs device a step towards a completely revised kernel interface? I've started to contemplate the use of socket pairs instead of pipes and ioctl(2) calls. (NBD seems to be a simple example of this style.)

Kind of. The change was needed to solve a fairly significant problem. I can't see how using sockets can make a difference really because the source of blocking isn't the interface but rather the things it needs to do.

But it gets worse as Generic Netlink is a socket based interface, a recommended ioctl replacement and trying to use that for the re-implementation was nothing short of a nightmare. I failed to get a working implementation after several weeks of work. I have the broken implementation around somewhere, at least as far as I got, if you want to run with that as a project. Mind you, if user space libnl becomes thread safe at some point we may want to re-consider this as a viable approach. It depends on other things as well, but mostly on how we might change the expire infrastructure post 5.0 (it isn't going to change for 5.0 and we need to retain backward compatibility), namely. whether we change to using the in kernel VFS mount expire mechanism and whether that will resolve the significant overhead when expiring large maps that use the "browse" option or how that issue will be otherwise resolved. So, yes, I'm thinking about these things but there is still enough to do with 5.0 to not spend a lot of time on it.

So this interface is the one that will be used until we can come up with a better one. The reason for the re-implementation is described in detail in Documentation/filesystems/autofs4-mount-control.txt. The most important part of this, as it relates to this thread of work, is the AUTOFS_DEV_IOCTL_ISMOUNTPOINT ioctl. We observed that is_mounted() was by far and away the top CPU user because it is used a lot and scans either /proc/mounts or /etc/mtab. My testing showed that using an updated kernel had a big effect on CPU usage.

Ian

maintainer
#52 lore raw

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

In reply to Ian Kent
Quoted 10 lines · Ian Kent
Quoted 3 lines
Quoted 3 lines

I'm tending toward reading the map during the lookup so the map is up to date when we look for the key in the cache.

Or maybe not.

If we take advantage of the existing code to mark the map as stale and handle the re-read and we accept the overhead of scanning the file map while waiting for the update something like this could be all that's needed.

So here is a slightly updated patch.

autofs-5.0.4 - always read file maps

From: Ian Kent <[email protected]>

---

 daemon/lookup.c       |    9 ++++++---
 modules/lookup_file.c |   26 ++++++++++++++------------
 2 files changed, 20 insertions(+), 15 deletions(-)
daemon/lookup.c +6 -3
index 741d846..e034348 100644
@@ -283,10 +283,13 @@ static int do_read_map(struct autofs_point *ap, struct map_source *map, time_t a
 	 * for the fail cases to function correctly and to cache the
 	 * lookup handle.
 	 *
-	 * We always need to whole map for direct mounts in order to
-	 * mount the triggers.
+	 * We always need to read the whole map for direct mounts in
+	 * order to mount the triggers. We also want to read the whole
+	 * map if it's a file map to avoid potentially lengthy linear
+	 * file scanning.
 	 */
-	if (!(ap->flags & MOUNT_FLAG_GHOST) && ap->type != LKP_DIRECT)
+	if (strcmp(map->type, "file") &&
+	    !(ap->flags & MOUNT_FLAG_GHOST) && ap->type != LKP_DIRECT)
 		return NSS_STATUS_SUCCESS;
 
 	if (!map->stale)
modules/lookup_file.c +14 -12
index 95b9f6f..6f426a5 100644
@@ -93,7 +93,6 @@ int lookup_init(const char *mapfmt, int argc, const char *const *argv, void **co
 		     argv[0]);
 		return 1;
 	}
-		
 	ctxt->mtime = st.st_mtime;
 
 	if (!mapfmt)
@@ -951,9 +950,6 @@ static int check_map_indirect(struct autofs_point *ap,
 	if (ret == CHE_FAIL)
 		return NSS_STATUS_NOTFOUND;
 
-	if (ret & CHE_UPDATED)
-		source->stale = 1;
-
 	pthread_cleanup_push(cache_lock_cleanup, mc);
 	cache_writelock(mc);
 	exists = cache_lookup_distinct(mc, key);
@@ -963,7 +959,6 @@ static int check_map_indirect(struct autofs_point *ap,
 			free(exists->mapent);
 			exists->mapent = NULL;
 			exists->status = 0;
-			source->stale = 1;
 		}
 	}
 	pthread_cleanup_pop(1);
@@ -985,14 +980,8 @@ static int check_map_indirect(struct autofs_point *ap,
 		we = cache_lookup_distinct(mc, "*");
 		if (we) {
 			/* Wildcard entry existed and is now gone */
-			if (we->source == source && (wild & CHE_MISSING)) {
+			if (we->source == source && (wild & CHE_MISSING))
 				cache_delete(mc, "*");
-				source->stale = 1;
-			}
-		} else {
-			/* Wildcard not in map but now is */
-			if (wild & (CHE_OK | CHE_UPDATED))
-				source->stale = 1;
 		}
 		pthread_cleanup_pop(1);
 
@@ -1064,7 +1053,19 @@ int lookup_mount(struct autofs_point *ap, const char *name, int name_len, void *
 	if (ap->type == LKP_INDIRECT && *key != '/') {
 		char *lkp_key;
 
+		/*
+		 * We can skip the map lookup and cache update altogether
+		 * if we know the map hasn't been modified since it was
+		 * last read. If it has then we can mark the map stale
+		 * so a re-read is triggered following the lookup.
+		 */
 		cache_readlock(mc);
+		me = cache_lookup_first(mc);
+		if (me && ctxt->mtime <= me->age)
+			goto do_cache_lookup;
+		else
+			source->stale = 1;
+
 		me = cache_lookup_distinct(mc, key);
 		if (me && me->multi)
 			lkp_key = strdup(me->multi->key);
@@ -1088,6 +1089,7 @@ int lookup_mount(struct autofs_point *ap, const char *name, int name_len, void *
 	}
 
 	cache_readlock(mc);
+do_cache_lookup:
 	me = cache_lookup(mc, key);
 	/* Stale mapent => check for entry in alternate source or wildcard */
 	if (me && !me->mapent) {
maintainer
#53 lore raw

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

In reply to Ian Kent
Quoted 4 lines · Ian Kent
Quoted 4 lines

Sure, just read the whole map. Even large maps aren't that big. What are we talking, 10k? 50k? You're better off reading the whole thing in at once.

As far as I can tell, up to about 10k is most common for large configurations. But people also have maps as large as 30 - 40k entries, so we should be thinking maps of that order in this discussion.

maintainer
#54 lore raw

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

In reply to Valerie Aurora Henson
Quoted 13 lines · Valerie Aurora Henson
Quoted 9 lines · Jeff Moyer
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

Most patches of this nature come with some description of a performance problem and how the patch solves it. Which caching algorithm is implemented below? There are, of course, many hashing algorithms for variable length strings. Can we get some rationale for the change? I'm not against it, I'd just like a *little* explanation.

This is where I get to blame my cold for being stupid. :)

Quoted 8 lines

Yes, the original author (Paul Wankadia, now cc'd) gave me a little information on that front, I just forgot to pass it on. It's the "One-at-a-Time" hash function by Bob Jenkins. See:

http://burtleburtle.net/bob/hash/doobs.html

What I vaguely recall from our conversation is an order of magnitude improvement in elapsed time for large (thousands) numbers of maps, but

Sorry to be trivail, but that probably should read "maps with thousands of entries".

Quoted 2 lines

I'll let Paul be more specific. Do we have a test for thousands of entries somewhere in our automated tests?

Not yet.

That will be quite interesting to write given that, at best, the test will work but we are interested in how long it should take which could be a bit like "how long is a piece of string" with varying hardware.

We will need two parts for the tests, for indirect and direct map types.

Quoted 112 lines

-VAL

Quoted 95 lines

Cheers,
Jeff

Quoted 91 lines
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +17 -10
index ce47e04..36b8294 100644
@@ -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;
 
Quoted 9 lines

lib/cache.c int cache_update(struct mapent_cache *mc, struct map_source *ms, const char *key · line 764

Quoted 9 lines
lib/cache.c +1 -1
 	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;

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#55 lore raw

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

In reply to Jeff Moyer
Quoted 9 lines · Jeff Moyer
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

Most patches of this nature come with some description of a performance problem and how the patch solves it. Which caching algorithm is implemented below? There are, of course, many hashing algorithms for variable length strings. Can we get some rationale for the change? I'm not against it, I'd just like a *little* explanation.

Thanks for spending some time on autofs Val, it's much appreciated.

As Jeff says, a brief description would save me guessing what to put with the patches. These days I try to have a description with all patches, no matter how trivial.

Quoted 109 lines

Cheers,
Jeff

Quoted 93 lines
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +17 -10
index ce47e04..36b8294 100644
@@ -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));

lib/cache.c int cache_update(struct mapent_cache *mc, struct map_source *ms, const char *key · line 764

Quoted 7 lines
lib/cache.c +1 -1
@@ -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;

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#56 lore raw

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

In reply to Valerie Aurora Henson
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

Perhaps this will help with the description.

What I think is the main point of this patch is that, with the trivial hash function, the length of the chains aren't evenly spread causing some chains to be excessively long for large maps. And the size of the hash table is too small because for 10000 entries we would have chains of about 130 entries if they were in fact spread evenly, and the claim is that they aren't.

Quoted 101 lines
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +18 -11
index ce47e04..36b8294 100644
@@ -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;
 
maintainer
#57 lore raw

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

Quoted 4 lines · Ian Kent
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

Quoted 8 lines

Perhaps this will help with the description.

What I think is the main point of this patch is that, with the trivial hash function, the length of the chains aren't evenly spread causing some chains to be excessively long for large maps. And the size of the hash table is too small because for 10000 entries we would have chains of about 130 entries if they were in fact spread evenly, and the claim is that they aren't.

And, yes, we should also be able to do much better than chain lengths of around 130.

A simple minded check would be to modify the cache_dump_cache() function to report chain lengths, add a call to it in a couple of strategic places and construct a test to load a large map. The difficulty, of course, is to ensure we are using strings with a distribution of characters that are really representative of map keys.

Quoted 107 lines
Quoted 94 lines
---
 include/automount.h |    2 +-
 lib/cache.c         |   29 ++++++++++++++++++-----------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/automount.h +1 -1
index 1ba0d3c..2a082b5 100644
@@ -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
lib/cache.c +17 -10
index ce47e04..36b8294 100644
@@ -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));

lib/cache.c int cache_update(struct mapent_cache *mc, struct map_source *ms, const char *key · line 765

Quoted 8 lines
lib/cache.c +1 -1
@@ -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;
 

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#58 lore raw

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

In reply to Valerie Aurora Henson
Quoted 2 lines · Valerie Aurora Henson

From: Paul Wankadia <[email protected]>

I think were about done with this.
Here's a patch with a few changes by me, please comment.

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

From: Valerie Aurora Henson <[email protected]>

Originally written by Paul Wankadia <[email protected]>.

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.
---

 CHANGELOG                      |    2 ++
 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 +++++
 7 files changed, 60 insertions(+), 22 deletions(-)
CHANGELOG +2 -0
index 43f3205..c1dc1b1 100644
@@ -4,6 +4,8 @@
 - fix nested submount expire deadlock.
 - fix negative caching for non-existent map keys.
 - use CLOEXEC flag.
+- make hash table scale to thousands of entries (Paul Wankadia,
+  Valerie Aurora Henson).
 
 4/11/2008 autofs-5.0.4
 -----------------------
include/automount.h +1 -1
index a083b61..938690f 100644
@@ -128,7 +128,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
include/defaults.h +3 -0
index 12534ec..9a2430f 100644
@@ -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_searchdn *);
 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
 
lib/cache.c +27 -20

129 lines not on this page · raw message

lib/defaults.c +15 -1
index ff653e3..0d39716 100644
@@ -49,6 +49,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;
 
@@ -323,7 +325,8 @@ unsigned int defaults_read_config(unsigned int to_syslog)
 		    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))
 			;
 	}
 
@@ -672,3 +675,14 @@ const char *defaults_get_auth_conf_file(void)
 	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;
+}
+
redhat/autofs.sysconfig.in +6 -0
index 8256888..ff49ff6 100644
@@ -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
 #
 # If the kernel supports using the autofs miscellanous device
samples/autofs.conf.default.in +6 -0
index 844a6f3..4496738 100644
@@ -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
 #
 # If the kernel supports using the autofs miscellanous device
maintainer
#60 lore raw

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

Quoted 6 lines · Paul Wankadia

On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <[email protected]> wrote:

I think were about done with this.
Here's a patch with a few changes by me, please comment.

LGTM. Thanks.

Great.
I'll wait and see if Val spots anything before I commit it.

Ian

#61 lore raw

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

Quoted 10 lines · Ian Kent
Quoted 6 lines · Paul Wankadia

On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <[email protected]> wrote:

I think were about done with this.
Here's a patch with a few changes by me, please comment.

LGTM. Thanks.

Great.
I'll wait and see if Val spots anything before I commit it.

Just a quick note - I'm very sick right now (just a cold, but a nasty one) and not up to writing or reviewing patches. I'll take a look as soon as my brain is reliable, hopefully in the next couple of days.

Thanks to both of you! BTW, Paul found and wrote the one-at-a-time hash algorithm, credit where credit is due.

-VAL

maintainer
#62 lore raw

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

Quoted 7 lines · Valerie Aurora Henson
Quoted 6 lines · Ian Kent
Quoted 5 lines · Paul Wankadia

On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <[email protected]> wrote:

I think were about done with this.
Here's a patch with a few changes by me, please comment.

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

LGTM. Thanks.

Great.
I'll wait and see if Val spots anything before I commit it.

Just a quick note - I'm very sick right now (just a cold, but a nasty one) and not up to writing or reviewing patches. I'll take a look as soon as my brain is reliable, hopefully in the next couple of days.

Bummer, hope you recover soon.

I'm about to commit it so we'll have to deal with any concerns you have as update patches. It's not much different to the original anyway. We also need to spend a bit more time on the other three patches you posted when your up to it. I think Jeff got some regressions when testing these. In any case the most recent issue Paul has flagged is probably a higher priority atm.

Quoted 3 lines

Thanks to both of you! BTW, Paul found and wrote the one-at-a-time hash algorithm, credit where credit is due.

Yep, I noted both of you in the CHANGELOG.

Quoted 2 lines

-VAL

#63 lore raw

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

Quoted 5 lines · Ian Kent

Bummer, hope you recover soon.

I'm about to commit it so we'll have to deal with any concerns you have as update patches. It's not much different to the original anyway. We

I just reviewed and no concerns. Thanks!

-VAL

#64 lore raw

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

In reply to Valerie Aurora Henson

On Thu, Jan 15, 2009 at 1:47 PM, Valerie Aurora Henson <[email protected]>wrote:

Thanks to both of you! BTW, Paul found and wrote the one-at-a-time

Quoted 1 line

hash algorithm, credit where credit is due.

I must point out that Bob Jenkins wrote it and released it into the public domain. (Hi, Bob!)

_______________________________________________
autofs mailing list
[email protected]
http://linux.kernel.org/mailman/listinfo/autofs

maintainer
#65 lore raw

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

In reply to Paul Wankadia
Quoted 8 lines · Paul Wankadia

On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <[email protected]> wrote:

I think were about done with this.
Here's a patch with a few changes by me, please comment.

LGTM. Thanks.

Committed to git, along with a couple of others.

Ian