[PATCH 0/4] autofs scaling and cleanup patches

[PATCH 0/4] autofs scaling and cleanup patches

[Valerie Aurora Henson]

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(-)

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

[Valerie Aurora Henson]

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

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

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

[Valerie Aurora Henson]

Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
---
 modules/lookup_ldap.c |   49 ++++++++++++++++++++++---------------------------
 1 files changed, 22 insertions(+), 27 deletions(-)

diff --git a/modules/lookup_ldap.c b/modules/lookup_ldap.c
index 42c3235..0ef7bcf 100644
--- a/modules/lookup_ldap.c
+++ b/modules/lookup_ldap.c
@@ -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);
 				}
 			}
-- 
1.6.0.4

[PATCH 3/4] Easy alloca() replacements

[Valerie Aurora Henson]

Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
---
 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(-)

diff --git a/daemon/automount.c b/daemon/automount.c
index 6f078c1..61bbc80 100644
--- a/daemon/automount.c
+++ b/daemon/automount.c
@@ -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;
diff --git a/daemon/direct.c b/daemon/direct.c
index 98fcc07..94216ba 100644
--- a/daemon/direct.c
+++ b/daemon/direct.c
@@ -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];
 
diff --git a/daemon/flag.c b/daemon/flag.c
index d8ca61b..5c4f0c2 100644
--- a/daemon/flag.c
+++ b/daemon/flag.c
@@ -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
diff --git a/daemon/indirect.c b/daemon/indirect.c
index 1232810..31713fd 100644
--- a/daemon/indirect.c
+++ b/daemon/indirect.c
@@ -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];
 
diff --git a/daemon/module.c b/daemon/module.c
index 36eca00..06b39c9 100644
--- a/daemon/module.c
+++ b/daemon/module.c
@@ -58,15 +58,10 @@ struct lookup_mod *open_lookup(const char *name, const char *err_prefix,
 {
 	struct lookup_mod *mod;
 	char buf[MAX_ERR_BUF];
-	char *fnbuf;
-	size_t size_name;
-	size_t size_fnbuf;
+	char fnbuf[PATH_MAX];
 	void *dh;
 	int *ver;
 
-	size_name = _strlen(name, PATH_MAX + 1);
-	if (!size_name)
-		return NULL;
 
 	mod = malloc(sizeof(struct lookup_mod));
 	if (!mod) {
@@ -77,9 +72,9 @@ struct lookup_mod *open_lookup(const char *name, const char *err_prefix,
 		return NULL;
 	}
 
-	size_fnbuf = size_name + strlen(AUTOFS_LIB_DIR) + 13;
-	fnbuf = alloca(size_fnbuf);
-	if (!fnbuf) {
+	if (snprintf(fnbuf,
+		     sizeof(fnbuf), "%s/lookup_%s.so", AUTOFS_LIB_DIR, name) >
+	    sizeof(fnbuf)) {
 		free(mod);
 		if (err_prefix) {
 			char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
@@ -87,7 +82,6 @@ struct lookup_mod *open_lookup(const char *name, const char *err_prefix,
 		}
 		return NULL;
 	}
-	snprintf(fnbuf, size_fnbuf, "%s/lookup_%s.so", AUTOFS_LIB_DIR, name);
 
 	if (!(dh = dlopen(fnbuf, RTLD_NOW))) {
 		if (err_prefix)
@@ -141,15 +135,10 @@ struct parse_mod *open_parse(const char *name, const char *err_prefix,
 {
 	struct parse_mod *mod;
 	char buf[MAX_ERR_BUF];
-	char *fnbuf;
-	size_t size_name;
-	size_t size_fnbuf;
+	char fnbuf[PATH_MAX];
 	void *dh;
 	int *ver;
 
-	size_name = _strlen(name, PATH_MAX + 1);
-	if (!size_name)
-		return NULL;
 
 	mod = malloc(sizeof(struct parse_mod));
 	if (!mod) {
@@ -160,9 +149,9 @@ struct parse_mod *open_parse(const char *name, const char *err_prefix,
 		return NULL;
 	}
 
-	size_fnbuf = size_name + strlen(AUTOFS_LIB_DIR) + 13;
-	fnbuf = alloca(size_fnbuf);
-	if (!fnbuf) {
+	if (snprintf(fnbuf,
+		     sizeof(fnbuf), "%s/parse_%s.so", AUTOFS_LIB_DIR, name) >
+	    sizeof(fnbuf)) {
 		free(mod);
 		if (err_prefix) {
 			char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
@@ -170,7 +159,6 @@ struct parse_mod *open_parse(const char *name, const char *err_prefix,
 		}
 		return NULL;
 	}
-	snprintf(fnbuf, size_fnbuf, "%s/parse_%s.so", AUTOFS_LIB_DIR, name);
 
 	if (!(dh = dlopen(fnbuf, RTLD_NOW))) {
 		if (err_prefix)
@@ -222,15 +210,10 @@ struct mount_mod *open_mount(const char *name, const char *err_prefix)
 {
 	struct mount_mod *mod;
 	char buf[MAX_ERR_BUF];
-	char *fnbuf;
-	size_t size_name;
-	size_t size_fnbuf;
+	char fnbuf[PATH_MAX];
 	void *dh;
 	int *ver;
 
-	size_name = _strlen(name, PATH_MAX + 1);
-	if (!size_name)
-		return NULL;
 
 	mod = malloc(sizeof(struct mount_mod));
 	if (!mod) {
@@ -241,9 +224,9 @@ struct mount_mod *open_mount(const char *name, const char *err_prefix)
 		return NULL;
 	}
 
-	size_fnbuf = size_name + strlen(AUTOFS_LIB_DIR) + 13;
-	fnbuf = alloca(size_fnbuf);
-	if (!fnbuf) {
+	if (snprintf(fnbuf,
+		    sizeof(fnbuf), "%s/mount_%s.so", AUTOFS_LIB_DIR, name) >
+	   sizeof(fnbuf)) {
 		free(mod);
 		if (err_prefix) {
 			char *estr = strerror_r(errno, buf, MAX_ERR_BUF);
@@ -251,7 +234,6 @@ struct mount_mod *open_mount(const char *name, const char *err_prefix)
 		}
 		return NULL;
 	}
-	snprintf(fnbuf, size_fnbuf, "%s/mount_%s.so", AUTOFS_LIB_DIR, name);
 
 	if (!(dh = dlopen(fnbuf, RTLD_NOW))) {
 		if (err_prefix)
diff --git a/lib/cache.c b/lib/cache.c
index 36b8294..bc2c722 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -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 */
diff --git a/lib/cat_path.c b/lib/cat_path.c
index 576b424..60669db 100644
--- a/lib/cat_path.c
+++ b/lib/cat_path.c
@@ -12,7 +12,6 @@
  *
  * ----------------------------------------------------------------------- */
 
-#include <alloca.h>
 #include <string.h>
 #include <limits.h>
 #include <ctype.h>
diff --git a/modules/lookup_nisplus.c b/modules/lookup_nisplus.c
index f15465f..279a8d6 100644
--- a/modules/lookup_nisplus.c
+++ b/modules/lookup_nisplus.c
@@ -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;
diff --git a/modules/mount_autofs.c b/modules/mount_autofs.c
index eb63d8e..effa4fc 100644
--- a/modules/mount_autofs.c
+++ b/modules/mount_autofs.c
@@ -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>
diff --git a/modules/mount_bind.c b/modules/mount_bind.c
index 022d183..3ec467d 100644
--- a/modules/mount_bind.c
+++ b/modules/mount_bind.c
@@ -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;
 
diff --git a/modules/mount_changer.c b/modules/mount_changer.c
index 43b8355..bf77a98 100644
--- a/modules/mount_changer.c
+++ b/modules/mount_changer.c
@@ -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';
diff --git a/modules/mount_ext2.c b/modules/mount_ext2.c
index 4c5b271..a80ccba 100644
--- a/modules/mount_ext2.c
+++ b/modules/mount_ext2.c
@@ -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';
diff --git a/modules/mount_generic.c b/modules/mount_generic.c
index f094d07..17ebfd4 100644
--- a/modules/mount_generic.c
+++ b/modules/mount_generic.c
@@ -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';
-- 
1.6.0.4

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

[Valerie Aurora Henson]

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

From: Paul Wankadia <junyer@google.com>
Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
---
 include/linux/auto_dev-ioctl.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/include/linux/auto_dev-ioctl.h b/include/linux/auto_dev-ioctl.h
index 91a7739..78f4b47 100644
--- a/include/linux/auto_dev-ioctl.h
+++ b/include/linux/auto_dev-ioctl.h
@@ -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"
-- 
1.6.0.4

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

[Jeff Moyer]

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

> Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>

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

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

[Jeff Moyer]

Valerie Aurora Henson <vaurora@redhat.com> writes:
> From: Paul Wankadia <junyer@google.com>
> Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>

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

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

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

[Valerie Aurora Henson]

On Fri, Jan 09, 2009 at 02:17:55PM -0500, Jeff Moyer wrote:
> Valerie Aurora Henson <vaurora@redhat.com> writes:
> > From: Paul Wankadia <junyer@google.com>
> > Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
> 
> 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

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

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

[Valerie Aurora Henson]

On Fri, Jan 09, 2009 at 02:00:01PM -0500, Jeff Moyer wrote:
> Valerie Aurora Henson <vaurora@redhat.com> writes:
> 
> > Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
> 
> > @@ -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 >=.

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

-VAL

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

[Valerie Aurora Henson]

On Fri, Jan 09, 2009 at 01:47:02PM -0500, Valerie Aurora Henson wrote:
> 
> --- a/daemon/direct.c
> +++ b/daemon/direct.c
> @@ -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];
>  

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

-VAL

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 1412 bytes --]

On Sat, Jan 10, 2009 at 6:51 AM, Valerie Aurora Henson
<vaurora@redhat.com>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?


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.

[-- Attachment #1.2: Type: text/html, Size: 1899 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Fri, 2009-01-09 at 14:17 -0500, Jeff Moyer wrote:
> Valerie Aurora Henson <vaurora@redhat.com> writes:
> > From: Paul Wankadia <junyer@google.com>
> > Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
> 
> 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.

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

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

[Ian Kent]

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

Just a first pass reading but noticed ....

> diff --git a/lib/cache.c b/lib/cache.c
> index 36b8294..bc2c722 100644
> --- a/lib/cache.c
> +++ b/lib/cache.c
> @@ -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.

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

>  
>  	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;
>  }
>  

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

[Ian Kent]

On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:
> From: Paul Wankadia <junyer@google.com>
> Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>

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.

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

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

[Ian Kent]

On Sat, 2009-01-10 at 12:29 +0900, Ian Kent wrote:
> On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:
> > From: Paul Wankadia <junyer@google.com>
> > Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
> 
> 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.

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

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

[Ian Kent]

On Fri, 2009-01-09 at 14:51 -0500, Valerie Aurora Henson wrote:
> On Fri, Jan 09, 2009 at 02:17:55PM -0500, Jeff Moyer wrote:
> > Valerie Aurora Henson <vaurora@redhat.com> writes:
> > > From: Paul Wankadia <junyer@google.com>
> > > Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
> > 
> > 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

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

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

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

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

[Ian Kent]

On Sat, 2009-01-10 at 12:19 +1100, Paul Wankadia wrote:
> On Sat, Jan 10, 2009 at 6:51 AM, Valerie Aurora Henson
> <vaurora@redhat.com> 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?
> 
> 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!

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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 1048 bytes --]

On Mon, Jan 12, 2009 at 3:42 AM, Ian Kent <raven@themaw.net> 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.
>
> 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.

[-- Attachment #1.2: Type: text/html, Size: 1575 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Mon, 2009-01-12 at 10:25 +1100, Paul Wankadia wrote:
> On Mon, Jan 12, 2009 at 3:42 AM, Ian Kent <raven@themaw.net> 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
> $ 

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

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

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

[Ian Kent]

On Mon, 2009-01-12 at 10:25 +1100, Paul Wankadia wrote:
> On Mon, Jan 12, 2009 at 3:42 AM, Ian Kent <raven@themaw.net> 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.
>         
>         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.

> How could it be worse? :P

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

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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 722 bytes --]

On Mon, Jan 12, 2009 at 12:19 PM, Ian Kent <raven@themaw.net> wrote:

Oh .. didn't see this before.
>
> > 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. ;)

> 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

[-- Attachment #1.2: Type: text/html, Size: 1256 bytes --]

[-- Attachment #2: additive.txt --]
[-- Type: text/plain, Size: 28373 bytes --]

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

[-- Attachment #3: additive.png --]
[-- Type: image/png, Size: 5781 bytes --]

[-- Attachment #4: one-at-a-time.txt --]
[-- Type: text/plain, Size: 29772 bytes --]

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

[-- Attachment #5: one-at-a-time.png --]
[-- Type: image/png, Size: 5216 bytes --]

[-- Attachment #6: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

[-- Attachment #1: Type: text/plain, Size: 2231 bytes --]

On Mon, 2009-01-12 at 10:19 +0900, Ian Kent wrote:
> 
> Oh .. didn't see this before.
> 
> > How could it be worse? :P
> 
> Hehe, there's an assumption without evidence in there some where.
> 
> > 
> > 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


[-- Attachment #2: hash-report-stats.patch --]
[-- Type: text/x-patch, Size: 3462 bytes --]

Make cache_dump_cache() report some statistical measures instead of

From: Ian Kent <raven@themaw.net>

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(-)


diff --git a/Makefile.rules b/Makefile.rules
index 30716dc..a59c3dd 100644
--- a/Makefile.rules
+++ b/Makefile.rules
@@ -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
diff --git a/daemon/lookup.c b/daemon/lookup.c
index 741d846..a66e3db 100644
--- a/daemon/lookup.c
+++ b/daemon/lookup.c
@@ -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;
 
diff --git a/lib/cache.c b/lib/cache.c
index 4a00367..258afd3 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -36,21 +36,75 @@ void cache_dump_multi(struct list_head *list)
 	}
 }
 
+#include <math.h>
+
+#define min(x, y)	(x <= y ? x : y)
+#define max(x, y)	(x >= y ? x : y)
+
 void cache_dump_cache(struct mapent_cache *mc)
 {
 	struct mapent *me;
+	unsigned long hc_len_min, hc_len_max, hc_empty, h_entries;
+	float hc_len_tot, hc_len_avg, hc_len_var, hc_len_std;
 	unsigned int i;
 
+	/* Calculate average, minimum and maximum chain length */
+
+	hc_len_min = 30000;
+	hc_len_max = 0;
+	hc_len_tot = 0;
+	hc_empty = 0;
+	h_entries = 0;
+
 	for (i = 0; i < mc->size; i++) {
+		unsigned long hc_len = 0;
+
 		me = mc->hash[i];
+
 		if (me == NULL)
-			continue;
-		while (me) {
-			logmsg("me->key=%s me->multi=%p dev=%ld ino=%ld",
-				me->key, me->multi, me->dev, me->ino);
-			me = me->next;
+			hc_empty++;
+		else {
+			while (me) {
+				h_entries++;
+				hc_len++;
+				me = me->next;
+			}
 		}
+		hc_len_min = min(hc_len_min, hc_len);
+		hc_len_max = max(hc_len_max, hc_len);
+		hc_len_tot = hc_len_tot + hc_len;
 	}
+
+	hc_len_avg = hc_len_tot / mc->size;
+
+	/* Calculate chain length variance */
+
+	hc_len_var = 0;
+
+	for (i = 0; i < mc->size; i++) {
+		int hc_len = 0;
+		float hc_dev;
+
+		me = mc->hash[i];
+
+		if (me != NULL) {
+			while (me) {
+				hc_len++;
+				me = me->next;
+			}
+		}
+		hc_dev = ((float) hc_len) - hc_len_avg;
+		hc_dev = hc_dev * hc_dev;
+		hc_len_var = hc_len_var + hc_dev;
+	}
+
+	hc_len_var = hc_len_var / mc->size;
+	hc_len_std = sqrtf(hc_len_var);
+
+	logmsg("cache: entries %u table size %u ideal chain length %.2f",
+		h_entries, mc->size, (float) h_entries/mc->size);
+	logmsg("chain length: empty %u min %u max %u avg %.2f std %.2f",
+		hc_empty, hc_len_min, hc_len_max, hc_len_avg, hc_len_std);
 }
 
 void cache_readlock(struct mapent_cache *mc)

[-- Attachment #3: hash-oaat-algo.patch --]
[-- Type: text/x-patch, Size: 2598 bytes --]

Use proposed oaat algorithm for hash calculation without

From: Ian Kent <raven@themaw.net>

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

 lib/cache.c |   29 ++++++++++++++++++-----------
 1 files changed, 18 insertions(+), 11 deletions(-)


diff --git a/lib/cache.c b/lib/cache.c
index 258afd3..5f64359 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -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;
 

[-- Attachment #4: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Mon, 2009-01-12 at 13:02 +0900, Ian Kent wrote:
> 
> 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
> 

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

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

[Ian Kent]

On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:
> 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.

> 
> From: Paul Wankadia <junyer@google.com>
> Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>
> ---
>  include/linux/auto_dev-ioctl.h |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/include/linux/auto_dev-ioctl.h b/include/linux/auto_dev-ioctl.h
> index 91a7739..78f4b47 100644
> --- a/include/linux/auto_dev-ioctl.h
> +++ b/include/linux/auto_dev-ioctl.h
> @@ -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"

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 4119 bytes --]

On Mon, Jan 12, 2009 at 3:02 PM, Ian Kent <raven@themaw.net> 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
>
> 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,
> 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 <raven@themaw.net> 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
>
>
> 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
> 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.
> 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
> map entry cache is typically very small.

[-- Attachment #1.2: Type: text/html, Size: 5559 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Tue, 2009-01-13 at 12:52 +1100, Paul Wankadia wrote:
> On Mon, Jan 12, 2009 at 3:02 PM, Ian Kent <raven@themaw.net> 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
>         
>         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.

> 
> 
>         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 <raven@themaw.net> 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
>         
>         
>         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.

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

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

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

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

[Ian Kent]

On Tue, 2009-01-13 at 11:24 +0900, Ian Kent wrote:
> On Tue, 2009-01-13 at 12:52 +1100, Paul Wankadia wrote:
> > 
> > 
> >         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?
> > 
> > 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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 1023 bytes --]

On Tue, Jan 13, 2009 at 1:24 PM, Ian Kent <raven@themaw.net> 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.

> 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

> 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 <raven@themaw.net> 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.

[-- Attachment #1.2: Type: text/html, Size: 1955 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Tue, 2009-01-13 at 16:07 +1100, Paul Wankadia wrote:
> On Tue, Jan 13, 2009 at 1:24 PM, Ian Kent <raven@themaw.net> 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.

> 
> 
>         > 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, ;)

> 
> 
>         > 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 <raven@themaw.net> 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

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

[Ian Kent]

On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:
> From: Paul Wankadia <junyer@google.com>
> Signed-off-by: Valerie Aurora Henson <vaurora@redhat.com>

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 <vaurora@redhat.com>

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

The autofs cache lookup performs poorly for large maps.

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

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

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

 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(-)


diff --git a/CHANGELOG b/CHANGELOG
index 43f3205..c1dc1b1 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -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
 -----------------------
diff --git a/include/automount.h b/include/automount.h
index a083b61..938690f 100644
--- a/include/automount.h
+++ b/include/automount.h
@@ -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
diff --git a/include/defaults.h b/include/defaults.h
index 12534ec..9a2430f 100644
--- a/include/defaults.h
+++ b/include/defaults.h
@@ -40,6 +40,8 @@
 #define DEFAULT_APPEND_OPTIONS		1
 #define DEFAULT_AUTH_CONF_FILE		AUTOFS_MAP_DIR "/autofs_ldap_auth.conf"
 
+#define DEFAULT_MAP_HASH_TABLE_SIZE	1024
+
 struct ldap_schema;
 struct ldap_searchdn;
 
@@ -62,6 +64,7 @@ void defaults_free_searchdns(struct ldap_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
 
diff --git a/lib/cache.c b/lib/cache.c
index 4a00367..edb3192 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -190,7 +190,7 @@ struct mapent_cache *cache_init(struct autofs_point *ap, struct map_source *map)
 	if (!mc)
 		return NULL;
 
-	mc->size = HASHSIZE;
+	mc->size = defaults_get_map_hash_table_size();
 
 	mc->hash = malloc(mc->size * sizeof(struct entry *));
 	if (!mc->hash) {
@@ -241,7 +241,7 @@ struct mapent_cache *cache_init_null_cache(struct master *master)
 	if (!mc)
 		return NULL;
 
-	mc->size = HASHSIZE;
+	mc->size = NULL_MAP_HASHSIZE;
 
 	mc->hash = malloc(mc->size * sizeof(struct entry *));
 	if (!mc->hash) {
@@ -279,29 +279,36 @@ 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 int size)
 {
-	unsigned long hashval;
+	u_int32_t hashval;
 	char *s = (char *) key;
 
-	for (hashval = 0; *s != '\0';)
-		hashval += *s++;
+	for (hashval = 0; *s != '\0';) {
+		hashval += (unsigned char) *s++;
+		hashval += (hashval << 10);
+		hashval ^= (hashval >> 6);
+	}
+
+	hashval += (hashval << 3);
+	hashval ^= (hashval >> 11);
+	hashval += (hashval << 15);
 
-	return hashval % HASHSIZE;
+	return hashval % size;
 }
 
-static unsigned int ino_hash(dev_t dev, ino_t ino)
+static u_int32_t ino_hash(dev_t dev, ino_t ino, unsigned int size)
 {
-	unsigned long hashval;
+	u_int32_t hashval;
 
 	hashval = dev + ino;
 
-	return hashval % HASHSIZE;
+	return hashval % size;
 }
 
 int cache_set_ino_index(struct mapent_cache *mc, const char *key, dev_t dev, ino_t ino)
 {
-	unsigned int ino_index = ino_hash(dev, ino);
+	u_int32_t ino_index = ino_hash(dev, ino, mc->size);
 	struct mapent *me;
 
 	me = cache_lookup_distinct(mc, key);
@@ -323,10 +330,10 @@ 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);
+	ino_index = ino_hash(dev, ino, mc->size);
 	head = &mc->ino_index[ino_index];
 
 	list_for_each(p, head) {
@@ -369,7 +376,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)
@@ -385,7 +392,7 @@ struct mapent *cache_lookup_next(struct mapent_cache *mc, struct mapent *me)
 		return this;
 	}
 
-	hashval = hash(me->key) + 1;
+	hashval = hash(me->key, mc->size) + 1;
 	if (hashval < mc->size) {
 		for (i = (unsigned int) hashval; i < mc->size; i++) {
 			this = mc->hash[i];
@@ -433,7 +440,7 @@ struct mapent *cache_lookup(struct mapent_cache *mc, const char *key)
 	if (!key)
 		return NULL;
 
-	for (me = mc->hash[hash(key)]; me != NULL; me = me->next) {
+	for (me = mc->hash[hash(key, mc->size)]; me != NULL; me = me->next) {
 		if (strcmp(key, me->key) == 0)
 			goto done;
 	}
@@ -446,7 +453,7 @@ struct mapent *cache_lookup(struct mapent_cache *mc, const char *key)
 			goto done;
 		}
 
-		for (me = mc->hash[hash("*")]; me != NULL; me = me->next)
+		for (me = mc->hash[hash("*", mc->size)]; me != NULL; me = me->next)
 			if (strcmp("*", me->key) == 0)
 				goto done;
 	}
@@ -462,7 +469,7 @@ struct mapent *cache_lookup_distinct(struct mapent_cache *mc, const char *key)
 	if (!key)
 		return NULL;
 
-	for (me = mc->hash[hash(key)]; me != NULL; me = me->next) {
+	for (me = mc->hash[hash(key, mc->size)]; me != NULL; me = me->next) {
 		if (strcmp(key, me->key) == 0)
 			return me;
 	}
@@ -530,7 +537,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, mc->size);
 	int status;
 
 	me = (struct mapent *) malloc(sizeof(struct mapent));
@@ -750,7 +757,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, mc->size);
 	int status, ret = CHE_OK;
 	char *this;
 
diff --git a/lib/defaults.c b/lib/defaults.c
index ff653e3..0d39716 100644
--- a/lib/defaults.c
+++ b/lib/defaults.c
@@ -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;
+}
+
diff --git a/redhat/autofs.sysconfig.in b/redhat/autofs.sysconfig.in
index 8256888..ff49ff6 100644
--- a/redhat/autofs.sysconfig.in
+++ b/redhat/autofs.sysconfig.in
@@ -89,6 +89,12 @@ BROWSE_MODE="no"
 #
 #AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
 #
+# MAP_HASH_TABLE_SIZE - set the map cache hash table size.
+# 			Should be a power of 2 with a ratio roughly
+# 			between 1:10 and 1:20 for each map.
+#
+#MAP_HASH_TABLE_SIZE=1024
+#
 # General global options
 #
 # If the kernel supports using the autofs miscellanous device
diff --git a/samples/autofs.conf.default.in b/samples/autofs.conf.default.in
index 844a6f3..4496738 100644
--- a/samples/autofs.conf.default.in
+++ b/samples/autofs.conf.default.in
@@ -89,6 +89,12 @@ BROWSE_MODE="no"
 #
 #AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
 #
+# MAP_HASH_TABLE_SIZE - set the map cache hash table size.
+# 			Should be a power of 2 with a ratio roughly
+# 			between 1:10 and 1:20 for each map.
+#
+#MAP_HASH_TABLE_SIZE=1024
+#
 # General global options
 #
 # If the kernel supports using the autofs miscellanous device

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 596 bytes --]

On Tue, Jan 13, 2009 at 4:19 PM, Ian Kent <raven@themaw.net> 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?

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

[-- Attachment #1.2: Type: text/html, Size: 1062 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 179 bytes --]

On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <raven@themaw.net> wrote:

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


LGTM. Thanks.

[-- Attachment #1.2: Type: text/html, Size: 455 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Wed, 2009-01-14 at 14:43 +1100, Paul Wankadia wrote:
> On Tue, Jan 13, 2009 at 4:19 PM, Ian Kent <raven@themaw.net> 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.

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

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

[Ian Kent]

On Wed, 2009-01-14 at 14:58 +1100, Paul Wankadia wrote:
> On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <raven@themaw.net> 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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 958 bytes --]

On Wed, Jan 14, 2009 at 7:47 PM, Ian Kent <raven@themaw.net> 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.


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.

[-- Attachment #1.2: Type: text/html, Size: 1350 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Wed, 2009-01-14 at 21:52 +1100, Paul Wankadia wrote:
> On Wed, Jan 14, 2009 at 7:47 PM, Ian Kent <raven@themaw.net> 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.
> 
> 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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 1140 bytes --]

On Thu, Jan 15, 2009 at 12:17 AM, Ian Kent <raven@themaw.net> 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.


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

[-- Attachment #1.2: Type: text/html, Size: 1530 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Thu, 2009-01-15 at 01:20 +1100, Paul Wankadia wrote:
> On Thu, Jan 15, 2009 at 12:17 AM, Ian Kent <raven@themaw.net> 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.
> 
> 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

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

[Valerie Aurora Henson]

On Wed, Jan 14, 2009 at 05:48:09PM +0900, Ian Kent wrote:
> On Wed, 2009-01-14 at 14:58 +1100, Paul Wankadia wrote:
> > On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <raven@themaw.net> 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

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

[Ian Kent]

On Wed, 2009-01-14 at 21:47 -0500, Valerie Aurora Henson wrote:
> On Wed, Jan 14, 2009 at 05:48:09PM +0900, Ian Kent wrote:
> > On Wed, 2009-01-14 at 14:58 +1100, Paul Wankadia wrote:
> > > On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <raven@themaw.net> 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.

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.

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

> 
> -VAL

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

[Ian Kent]

On Wed, 2009-01-14 at 14:58 +1100, Paul Wankadia wrote:
> On Tue, Jan 13, 2009 at 4:51 PM, Ian Kent <raven@themaw.net> 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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 293 bytes --]

On Thu, Jan 15, 2009 at 1:47 PM, Valerie Aurora Henson
<vaurora@redhat.com>wrote:

Thanks to both of you!  BTW, Paul found and wrote the one-at-a-time
> 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!)

[-- Attachment #1.2: Type: text/html, Size: 562 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Jeff Moyer]

Ian Kent <raven@themaw.net> writes:

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

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

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

[Ian Kent]

On Thu, 2009-01-15 at 10:04 -0500, Jeff Moyer wrote:
> Ian Kent <raven@themaw.net> writes:
> 
> > 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?
> 
> 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

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

[Paul Wankadia]

On 1/16/09, Ian Kent <raven@themaw.net> wrote:

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

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

[Jeff Moyer]

Paul Wankadia <junyer@google.com> writes:

> On 1/16/09, Ian Kent <raven@themaw.net> wrote:
>
>>> 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.

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

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

[Paul Wankadia]

On 1/16/09, Jeff Moyer <jmoyer@redhat.com> wrote:

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

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

[Ian Kent]

On Fri, 2009-01-16 at 07:57 +1100, Paul Wankadia wrote:
> On 1/16/09, Jeff Moyer <jmoyer@redhat.com> wrote:
> 
> > 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.

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

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

[Ian Kent]

On Fri, 2009-01-16 at 00:16 +0900, Ian Kent wrote:
> > 
> > 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.

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

[Ian Kent]

On Fri, 2009-01-16 at 09:27 +0900, Ian Kent wrote:
> On Fri, 2009-01-16 at 07:57 +1100, Paul Wankadia wrote:
> > On 1/16/09, Jeff Moyer <jmoyer@redhat.com> wrote:
> > 
> > > 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.
> 
> 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.
> 
> Ian
> 
> 
> _______________________________________________
> autofs mailing list
> autofs@linux.kernel.org
> http://linux.kernel.org/mailman/listinfo/autofs

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

[Ian Kent]

On Fri, 2009-01-16 at 09:40 +0900, Ian Kent wrote:
> On Fri, 2009-01-16 at 09:27 +0900, Ian Kent wrote:
> > On Fri, 2009-01-16 at 07:57 +1100, Paul Wankadia wrote:
> > > On 1/16/09, Jeff Moyer <jmoyer@redhat.com> wrote:
> > > 
> > > > 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.
> > 
> > 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 <raven@themaw.net>


---

 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") ||
+	    (!(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)
+			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) {

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 4348 bytes --]

On Fri, Jan 16, 2009 at 12:43 PM, Ian Kent <raven@themaw.net> 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 <raven@themaw.net>
>
>
> ---
>
>  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") ||


I suspect that you want && instead.

+           (!(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)


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.

+
>                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) {
>
>
>

[-- Attachment #1.2: Type: text/html, Size: 6932 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Fri, 2009-01-16 at 14:59 +1100, Paul Wankadia wrote:
> On Fri, Jan 16, 2009 at 12:43 PM, Ian Kent <raven@themaw.net> 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 <raven@themaw.net>
>         
>         
>         ---
>         
>          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") ||
> 
> 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.

> 
> 
>         +           (!(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)
> 
> 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. 

> 
> 
>         +                       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) {
>         
>         
> 

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

[Ian Kent]

On Fri, 2009-01-16 at 13:22 +0900, Ian Kent wrote:
> >         
> >         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") ||
> > 
> > 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

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

[Ian Kent]

On Fri, 2009-01-16 at 10:43 +0900, Ian Kent wrote:
> > > 
> > > 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 <raven@themaw.net>


---

 daemon/lookup.c       |    9 ++++++---
 modules/lookup_file.c |   26 ++++++++++++++------------
 2 files changed, 20 insertions(+), 15 deletions(-)


diff --git a/daemon/lookup.c b/daemon/lookup.c
index 741d846..e034348 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") &&
+	    !(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..6f426a5 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)
@@ -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) {

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 839 bytes --]

On Fri, Jan 16, 2009 at 3:21 PM, Ian Kent <raven@themaw.net> 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.


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.

[-- Attachment #1.2: Type: text/html, Size: 1274 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Fri, 2009-01-16 at 17:04 +1100, Paul Wankadia wrote:
> On Fri, Jan 16, 2009 at 3:21 PM, Ian Kent <raven@themaw.net> 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.
> 
> 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

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

[Ian Kent]

On Fri, 2009-01-16 at 15:24 +0900, Ian Kent wrote:
> On Fri, 2009-01-16 at 17:04 +1100, Paul Wankadia wrote:
> > On Fri, Jan 16, 2009 at 3:21 PM, Ian Kent <raven@themaw.net> 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.
> > 
> > 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

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

[Valerie Aurora Henson]

On Thu, Jan 15, 2009 at 12:02:04PM +0900, Ian Kent wrote:
> 
> 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

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

[Valerie Aurora Henson]

On Sat, Jan 10, 2009 at 12:18:36PM +0900, Ian Kent wrote:
> On Fri, 2009-01-09 at 13:47 -0500, Valerie Aurora Henson wrote:
> 
> Just a first pass reading but noticed ....
> 
> > diff --git a/lib/cache.c b/lib/cache.c
> > index 36b8294..bc2c722 100644
> > --- a/lib/cache.c
> > +++ b/lib/cache.c
> > @@ -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.

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

> >  
> >  	/* 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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 1150 bytes --]

On Fri, Jan 16, 2009 at 5:39 PM, Ian Kent <raven@themaw.net> 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.


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

[-- Attachment #1.2: Type: text/html, Size: 1684 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

[-- Attachment #1: Type: text/plain, Size: 1806 bytes --]

On Sun, 2009-01-18 at 04:11 +1100, Paul Wankadia wrote:
> On Fri, Jan 16, 2009 at 5:39 PM, Ian Kent <raven@themaw.net> 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.
> 
> 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


[-- Attachment #2: ols-paper.pdf --]
[-- Type: application/pdf, Size: 128092 bytes --]

[-- Attachment #3: Type: text/plain, Size: 140 bytes --]

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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 763 bytes --]

On Sun, Jan 18, 2009 at 2:26 PM, Ian Kent <raven@themaw.net> 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.


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.

[-- Attachment #1.2: Type: text/html, Size: 1137 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Mon, 2009-01-19 at 12:28 +1100, Paul Wankadia wrote:
> On Sun, Jan 18, 2009 at 2:26 PM, Ian Kent <raven@themaw.net> 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.
> 
> 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

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

[Paul Wankadia]

[-- Attachment #1.1: Type: text/plain, Size: 1162 bytes --]

 On Mon, Jan 19, 2009 at 1:03 PM, Ian Kent <raven@themaw.net> 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.


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

[-- Attachment #1.2: Type: text/html, Size: 1563 bytes --]

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

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

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

[Ian Kent]

On Mon, 2009-01-19 at 16:23 +1100, Paul Wankadia wrote:
> On Mon, Jan 19, 2009 at 1:03 PM, Ian Kent <raven@themaw.net> 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.
> 
> 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.

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