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

   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