1 autofs-5.0.4 - make hash table scale to thousands of entries
3 From: Valerie Aurora Henson <vaurora@redhat.com>
5 Originally written by Paul Wankadia <junyer@google.com>.
7 The autofs cache lookup performs poorly for large maps.
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
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
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.
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(-)
32 diff --git a/CHANGELOG b/CHANGELOG
33 index 0fb7db5..912c088 100644
37 - fix negative caching for non-existent map keys.
39 - fix select(2) fd limit.
40 +- make hash table scale to thousands of entries (Paul Wankadia,
41 + Valerie Aurora Henson).
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
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
63 #define DEFAULT_APPEND_OPTIONS 1
64 #define DEFAULT_AUTH_CONF_FILE AUTOFS_MAP_DIR "/autofs_ldap_auth.conf"
66 +#define DEFAULT_MAP_HASH_TABLE_SIZE 1024
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);
79 diff --git a/lib/cache.c b/lib/cache.c
80 index 4a00367..edb3192 100644
83 @@ -190,7 +190,7 @@ struct mapent_cache *cache_init(struct autofs_point *ap, struct map_source *map)
87 - mc->size = HASHSIZE;
88 + mc->size = defaults_get_map_hash_table_size();
90 mc->hash = malloc(mc->size * sizeof(struct entry *));
92 @@ -241,7 +241,7 @@ struct mapent_cache *cache_init_null_cache(struct master *master)
96 - mc->size = HASHSIZE;
97 + mc->size = NULL_MAP_HASHSIZE;
99 mc->hash = malloc(mc->size * sizeof(struct entry *));
101 @@ -279,29 +279,36 @@ struct mapent_cache *cache_init_null_cache(struct master *master)
105 -static unsigned int hash(const char *key)
106 +static u_int32_t hash(const char *key, unsigned int size)
108 - unsigned long hashval;
110 char *s = (char *) key;
112 - for (hashval = 0; *s != '\0';)
114 + for (hashval = 0; *s != '\0';) {
115 + hashval += (unsigned char) *s++;
116 + hashval += (hashval << 10);
117 + hashval ^= (hashval >> 6);
120 + hashval += (hashval << 3);
121 + hashval ^= (hashval >> 11);
122 + hashval += (hashval << 15);
124 - return hashval % HASHSIZE;
125 + return hashval % size;
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)
131 - unsigned long hashval;
136 - return hashval % HASHSIZE;
137 + return hashval % size;
140 int cache_set_ino_index(struct mapent_cache *mc, const char *key, dev_t dev, ino_t ino)
142 - unsigned int ino_index = ino_hash(dev, ino);
143 + u_int32_t ino_index = ino_hash(dev, ino, mc->size);
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)
149 struct mapent *me = NULL;
150 struct list_head *head, *p;
151 - unsigned int ino_index;
152 + u_int32_t ino_index;
155 - ino_index = ino_hash(dev, ino);
156 + ino_index = ino_hash(dev, ino, mc->size);
157 head = &mc->ino_index[ino_index];
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)
164 - unsigned long hashval;
169 @@ -385,7 +392,7 @@ struct mapent *cache_lookup_next(struct mapent_cache *mc, struct mapent *me)
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++) {
178 @@ -433,7 +440,7 @@ struct mapent *cache_lookup(struct mapent_cache *mc, const char *key)
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)
187 @@ -446,7 +453,7 @@ struct mapent *cache_lookup(struct mapent_cache *mc, const char *key)
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)
196 @@ -462,7 +469,7 @@ struct mapent *cache_lookup_distinct(struct mapent_cache *mc, const char *key)
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)
205 @@ -530,7 +537,7 @@ int cache_add(struct mapent_cache *mc, struct map_source *ms, const char *key, c
207 struct mapent *me, *existing = NULL;
209 - unsigned int hashval = hash(key);
210 + u_int32_t hashval = hash(key, mc->size);
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)
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;
223 diff --git a/lib/defaults.c b/lib/defaults.c
224 index ff653e3..0d39716 100644
228 #define ENV_UMOUNT_WAIT "UMOUNT_WAIT"
229 #define ENV_AUTH_CONF_FILE "AUTH_CONF_FILE"
231 +#define ENV_MAP_HASH_TABLE_SIZE "MAP_HASH_TABLE_SIZE"
233 static const char *default_master_map_name = DEFAULT_MASTER_MAP_NAME;
234 static const char *default_auth_conf_file = DEFAULT_AUTH_CONF_FILE;
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))
246 @@ -672,3 +675,14 @@ const char *defaults_get_auth_conf_file(void)
247 return (const char *) cf;
250 +unsigned int defaults_get_map_hash_table_size(void)
254 + size = get_env_number(ENV_MAP_HASH_TABLE_SIZE);
256 + size = DEFAULT_MAP_HASH_TABLE_SIZE;
258 + return (unsigned int) size;
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"
267 #AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
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.
273 +#MAP_HASH_TABLE_SIZE=1024
275 # General global options
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"
284 #AUTH_CONF_FILE="@@autofsmapdir@@/autofs_ldap_auth.conf"
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.
290 +#MAP_HASH_TABLE_SIZE=1024
292 # General global options
294 # If the kernel supports using the autofs miscellanous device