[packages/autofs.git] / autofs-5.0.4-make-hash-table-scale-to-thousands-of-entries.patch

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 0fb7db5..912c088 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -5,6 +5,8 @@
 - fix negative caching for non-existent map keys.
 - use CLOEXEC flag.
 - fix select(2) fd limit.
+- 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 a55ddbc..fa24885 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..fe36f45 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
Commit	Line	Data
e5fd101c PS	1	autofs-5.0.4 - make hash table scale to thousands of entries
	2
	3	From: Valerie Aurora Henson <vaurora@redhat.com>
	4
	5	Originally written by Paul Wankadia <junyer@google.com>.
	6
	7	The autofs cache lookup performs poorly for large maps.
	8
	9	The additive hashing algorithm used by autofs results in a clustering
	10	of hash values around the average hash chain size. It is biased toward
	11	a small range of hash indexes which becomes worse as the hash table size
	12	increases.
	13
	14	Simple testing shows that the "One-at-a-time" hash function (implemented
	15	by this patch) gives a much better distribution of hash indexes as table
	16	size increases.
	17
	18	The only change made to the original patch is to make the hash table size
	19	configurable with a default somewhat larger than it is currently.
	20	---
	21
	22	CHANGELOG \| 2 ++
	23	include/automount.h \| 2 +-
	24	include/defaults.h \| 3 +++
	25	lib/cache.c \| 47 +++++++++++++++++++++++-----------------
	26	lib/defaults.c \| 16 +++++++++++++-
	27	redhat/autofs.sysconfig.in \| 6 +++++
	28	samples/autofs.conf.default.in \| 6 +++++
	29	7 files changed, 60 insertions(+), 22 deletions(-)
	30
	31
	32	diff --git a/CHANGELOG b/CHANGELOG
	33	index 0fb7db5..912c088 100644
	34	--- a/CHANGELOG
	35	+++ b/CHANGELOG
	36	@@ -5,6 +5,8 @@
	37	- fix negative caching for non-existent map keys.
	38	- use CLOEXEC flag.
	39	- fix select(2) fd limit.
	40	+- make hash table scale to thousands of entries (Paul Wankadia,
	41	+ Valerie Aurora Henson).
	42
	43	4/11/2008 autofs-5.0.4
	44	-----------------------
	45	diff --git a/include/automount.h b/include/automount.h
	46	index a55ddbc..fa24885 100644
	47	--- a/include/automount.h
	48	+++ b/include/automount.h
	49	@@ -128,7 +128,7 @@ struct autofs_point;
	50	#define CHE_DUPLICATE 0x0020
	51	#define CHE_UNAVAIL 0x0040
	52
	53	-#define HASHSIZE 77
	54	+#define NULL_MAP_HASHSIZE 64
	55	#define NEGATIVE_TIMEOUT 10
	56	#define UMOUNT_RETRIES 8
	57	#define EXPIRE_RETRIES 3
	58	diff --git a/include/defaults.h b/include/defaults.h
	59	index 12534ec..9a2430f 100644
	60	--- a/include/defaults.h
	61	+++ b/include/defaults.h
	62	@@ -40,6 +40,8 @@
	63	#define DEFAULT_APPEND_OPTIONS 1
	64	#define DEFAULT_AUTH_CONF_FILE AUTOFS_MAP_DIR "/autofs_ldap_auth.conf"
65
66	+#define DEFAULT_MAP_HASH_TABLE_SIZE 1024
67	+
68	struct ldap_schema;
69	struct ldap_searchdn;
70
71	@@ -62,6 +64,7 @@ void defaults_free_searchdns(struct ldap_searchdn *);
72	unsigned int defaults_get_append_options(void);
73	unsigned int defaults_get_umount_wait(void);
74	const char *defaults_get_auth_conf_file(void);
75	+unsigned int defaults_get_map_hash_table_size(void);
76
77	#endif
78
79	diff --git a/lib/cache.c b/lib/cache.c
80	index 4a00367..edb3192 100644
81	--- a/lib/cache.c
82	+++ b/lib/cache.c
83	@@ -190,7 +190,7 @@ struct mapent_cache cache_init(struct autofs_point ap, struct map_source *map)
84	if (!mc)
85	return NULL;
86
87	- mc->size = HASHSIZE;
88	+ mc->size = defaults_get_map_hash_table_size();
89
90	mc->hash = malloc(mc->size * sizeof(struct entry *));
91	if (!mc->hash) {
92	@@ -241,7 +241,7 @@ struct mapent_cache cache_init_null_cache(struct master master)
93	if (!mc)
94	return NULL;
95
96	- mc->size = HASHSIZE;
97	+ mc->size = NULL_MAP_HASHSIZE;
98
99	mc->hash = malloc(mc->size * sizeof(struct entry *));
100	if (!mc->hash) {
101	@@ -279,29 +279,36 @@ struct mapent_cache cache_init_null_cache(struct master master)
102	return mc;
103	}
104
105	-static unsigned int hash(const char *key)
106	+static u_int32_t hash(const char *key, unsigned int size)
107	{
108	- unsigned long hashval;
109	+ u_int32_t hashval;
110	char s = (char ) key;
111
112	- for (hashval = 0; *s != '\0';)
113	- hashval += *s++;
114	+ for (hashval = 0; *s != '\0';) {
115	+ hashval += (unsigned char) *s++;
116	+ hashval += (hashval << 10);
117	+ hashval ^= (hashval >> 6);
118	+ }
119	+
120	+ hashval += (hashval << 3);
121	+ hashval ^= (hashval >> 11);
122	+ hashval += (hashval << 15);
123
124	- return hashval % HASHSIZE;
125	+ return hashval % size;
126	}
127
128	-static unsigned int ino_hash(dev_t dev, ino_t ino)
129	+static u_int32_t ino_hash(dev_t dev, ino_t ino, unsigned int size)
130	{
131	- unsigned long hashval;
132	+ u_int32_t hashval;
133
134	hashval = dev + ino;
135
136	- return hashval % HASHSIZE;
137	+ return hashval % size;
138	}
139
140	int cache_set_ino_index(struct mapent_cache mc, const char key, dev_t dev, ino_t ino)
141	{
142	- unsigned int ino_index = ino_hash(dev, ino);
143	+ u_int32_t ino_index = ino_hash(dev, ino, mc->size);
144	struct mapent *me;
145
146	me = cache_lookup_distinct(mc, key);
147	@@ -323,10 +330,10 @@ struct mapent cache_lookup_ino(struct mapent_cache mc, dev_t dev, ino_t ino)
148	{
149	struct mapent *me = NULL;
150	struct list_head head, p;
151	- unsigned int ino_index;
152	+ u_int32_t ino_index;
153
154	ino_index_lock(mc);
155	- ino_index = ino_hash(dev, ino);
156	+ ino_index = ino_hash(dev, ino, mc->size);
157	head = &mc->ino_index[ino_index];
158
159	list_for_each(p, head) {
160	@@ -369,7 +376,7 @@ struct mapent cache_lookup_first(struct mapent_cache mc)
161	struct mapent cache_lookup_next(struct mapent_cache mc, struct mapent *me)
162	{
163	struct mapent *this;
164	- unsigned long hashval;
165	+ u_int32_t hashval;
166	unsigned int i;
167
168	if (!me)
169	@@ -385,7 +392,7 @@ struct mapent cache_lookup_next(struct mapent_cache mc, struct mapent *me)
170	return this;
171	}
172
173	- hashval = hash(me->key) + 1;
174	+ hashval = hash(me->key, mc->size) + 1;
175	if (hashval < mc->size) {
176	for (i = (unsigned int) hashval; i < mc->size; i++) {
177	this = mc->hash[i];
178	@@ -433,7 +440,7 @@ struct mapent cache_lookup(struct mapent_cache mc, const char *key)
179	if (!key)
180	return NULL;
181
182	- for (me = mc->hash[hash(key)]; me != NULL; me = me->next) {
183	+ for (me = mc->hash[hash(key, mc->size)]; me != NULL; me = me->next) {
184	if (strcmp(key, me->key) == 0)
185	goto done;
186	}
187	@@ -446,7 +453,7 @@ struct mapent cache_lookup(struct mapent_cache mc, const char *key)
188	goto done;
189	}
190
191	- for (me = mc->hash[hash("*")]; me != NULL; me = me->next)
192	+ for (me = mc->hash[hash("*", mc->size)]; me != NULL; me = me->next)
193	if (strcmp("*", me->key) == 0)
194	goto done;
195	}
196	@@ -462,7 +469,7 @@ struct mapent cache_lookup_distinct(struct mapent_cache mc, const char *key)
197	if (!key)
198	return NULL;
199
200	- for (me = mc->hash[hash(key)]; me != NULL; me = me->next) {
201	+ for (me = mc->hash[hash(key, mc->size)]; me != NULL; me = me->next) {
202	if (strcmp(key, me->key) == 0)
203	return me;
204	}
205	@@ -530,7 +537,7 @@ int cache_add(struct mapent_cache mc, struct map_source ms, const char *key, c
206	{
207	struct mapent me, existing = NULL;
208	char pkey, pent;
209	- unsigned int hashval = hash(key);
210	+ u_int32_t hashval = hash(key, mc->size);
211	int status;
212
213	me = (struct mapent *) malloc(sizeof(struct mapent));
214	@@ -750,7 +757,7 @@ int cache_update(struct mapent_cache mc, struct map_source ms, const char *key
215	int cache_delete(struct mapent_cache mc, const char key)
216	{
217	struct mapent me = NULL, pred;
218	- unsigned int hashval = hash(key);
219	+ u_int32_t hashval = hash(key, mc->size);
220	int status, ret = CHE_OK;
221	char *this;
222
223	diff --git a/lib/defaults.c b/lib/defaults.c
224	index ff653e3..0d39716 100644
225	--- a/lib/defaults.c
226	+++ b/lib/defaults.c
227	@@ -49,6 +49,8 @@
228	#define ENV_UMOUNT_WAIT "UMOUNT_WAIT"
229	#define ENV_AUTH_CONF_FILE "AUTH_CONF_FILE"
230
231	+#define ENV_MAP_HASH_TABLE_SIZE "MAP_HASH_TABLE_SIZE"
232	+
233	static const char *default_master_map_name = DEFAULT_MASTER_MAP_NAME;
234	static const char *default_auth_conf_file = DEFAULT_AUTH_CONF_FILE;
235
236	@@ -323,7 +325,8 @@ unsigned int defaults_read_config(unsigned int to_syslog)
237	check_set_config_value(key, ENV_NAME_VALUE_ATTR, value, to_syslog) \|\|
238	check_set_config_value(key, ENV_APPEND_OPTIONS, value, to_syslog) \|\|
239	check_set_config_value(key, ENV_UMOUNT_WAIT, value, to_syslog) \|\|
240	- check_set_config_value(key, ENV_AUTH_CONF_FILE, value, to_syslog))
241	+ check_set_config_value(key, ENV_AUTH_CONF_FILE, value, to_syslog) \|\|
242	+ check_set_config_value(key, ENV_MAP_HASH_TABLE_SIZE, value, to_syslog))
243	;
244	}
245
246	@@ -672,3 +675,14 @@ const char *defaults_get_auth_conf_file(void)
247	return (const char *) cf;
248	}
249
250	+unsigned int defaults_get_map_hash_table_size(void)
251	+{
252	+ long size;
253	+
254	+ size = get_env_number(ENV_MAP_HASH_TABLE_SIZE);
255	+ if (size < 0)
256	+ size = DEFAULT_MAP_HASH_TABLE_SIZE;
257	+
258	+ return (unsigned int) size;
259	+}
260	+
261	diff --git a/redhat/autofs.sysconfig.in b/redhat/autofs.sysconfig.in
262	index 8256888..fe36f45 100644
263	--- a/redhat/autofs.sysconfig.in
264	+++ b/redhat/autofs.sysconfig.in
265	@@ -89,6 +89,12 @@ BROWSE_MODE="no"
266	#
267	#AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
268	#
269	+# MAP_HASH_TABLE_SIZE - set the map cache hash table size.
270	+# Should be a power of 2 with a ratio roughly
271	+# between 1:10 and 1:20 for each map.
272	+#
273	+#MAP_HASH_TABLE_SIZE=1024
274	+#
275	# General global options
276	#
277	# If the kernel supports using the autofs miscellanous device
278	diff --git a/samples/autofs.conf.default.in b/samples/autofs.conf.default.in
279	index 844a6f3..4496738 100644
280	--- a/samples/autofs.conf.default.in
281	+++ b/samples/autofs.conf.default.in
282	@@ -89,6 +89,12 @@ BROWSE_MODE="no"
283	#
284	#AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
285	#
286	+# MAP_HASH_TABLE_SIZE - set the map cache hash table size.
287	+# Should be a power of 2 with a ratio roughly
288	+# between 1:10 and 1:20 for each map.
289	+#
290	+#MAP_HASH_TABLE_SIZE=1024
291	+#
292	# General global options
293	#
294	# If the kernel supports using the autofs miscellanous device