inode_table: make the inode table resizable

diff --git a/include/wimlib/bitops.h b/include/wimlib/bitops.h
index 191e95a10f7d537eb215cddfa90914adbe94f334..14c73593521b8bbba6a5646058d7f21500b534af 100644 (file)
--- a/include/wimlib/bitops.h
+++ b/include/wimlib/bitops.h
@@ -89,4 +89,14 @@ ffsw(machine_word_t v)
                return ffs64(v);
 }
 
+/* Round up to nearest power of 2  */
+
+static inline size_t
+roundup_pow_of_2(size_t n)
+{
+       if (n <= 1)
+               return 1;
+       return (size_t)1 << (1 + flsw(n - 1));
+}
+
 #endif /* _WIMLIB_BITOPS_H */

diff --git a/include/wimlib/inode_table.h b/include/wimlib/inode_table.h
index 9e8485a1b2502a2890394f70398b8099ef81e4d8..4d4fab5ec5678100d7dac4212d5e865985eb8d32 100644 (file)
--- a/include/wimlib/inode_table.h
+++ b/include/wimlib/inode_table.h
@@ -3,6 +3,7 @@
 
 #include "wimlib/list.h"
 #include "wimlib/types.h"
+#include "wimlib/util.h"
 
 struct wim_dentry;
 
@@ -13,11 +14,20 @@ struct wim_dentry;
  * cases the inodes are linked by i_hlist_node.  */
 struct wim_inode_table {
        struct hlist_head *array;
+       size_t filled;
        size_t capacity;
        struct hlist_head extra_inodes;
 };
 
 
+/* Compute the index of the hash bucket to use for the given inode number and
+ * device number.  */
+static inline size_t
+hash_inode(const struct wim_inode_table *table, u64 ino, u64 devno)
+{
+       return (hash_u64(ino) + devno) & (table->capacity - 1);
+}
+
 extern int
 init_inode_table(struct wim_inode_table *table, size_t capacity);
 
@@ -26,6 +36,9 @@ inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
                       u64 ino, u64 devno, bool noshare,
                       struct wim_dentry **dentry_ret);
 
+extern void
+enlarge_inode_table(struct wim_inode_table *table);
+
 extern void
 inode_table_prepare_inode_list(struct wim_inode_table *table,
                               struct hlist_head *head);

diff --git a/src/blob_table.c b/src/blob_table.c
index 5d464a979d5ed0ac2f9c71b734600746c238586f..54eca2c9f9d753514056cd082aeaae2673d47af2 100644 (file)
--- a/src/blob_table.c
+++ b/src/blob_table.c
@@ -54,21 +54,13 @@ struct blob_table {
        size_t mask; /* capacity - 1; capacity is a power of 2  */
 };
 
-static size_t
-next_power_of_2(size_t n)
-{
-       if (n <= 1)
-               return 1;
-       return (size_t)1 << (1 + flsw(n - 1));
-}
-
 struct blob_table *
 new_blob_table(size_t capacity)
 {
        struct blob_table *table;
        struct hlist_head *array;
 
-       capacity = next_power_of_2(capacity);
+       capacity = roundup_pow_of_2(capacity);
 
        table = MALLOC(sizeof(struct blob_table));
        if (table == NULL)

diff --git a/src/inode_fixup.c b/src/inode_fixup.c
index 51893fc19096463098f32151bef7304839abdf7a..b0b13aacf8f142104cd28ba8dd051c73c0d7dcaf 100644 (file)
--- a/src/inode_fixup.c
+++ b/src/inode_fixup.c
@@ -72,7 +72,7 @@ inode_table_insert(struct wim_dentry *dentry, void *_params)
        }
 
        /* Try adding this dentry to an existing inode.  */
-       pos = d_inode->i_ino % table->capacity;
+       pos = hash_inode(table, d_inode->i_ino, 0);
        hlist_for_each_entry(inode, &table->array[pos], i_hlist_node) {
                if (inode->i_ino != d_inode->i_ino) {
                        continue;
@@ -108,6 +108,8 @@ inode_table_insert(struct wim_dentry *dentry, void *_params)
 
        /* Keep this dentry's inode.  */
        hlist_add_head(&d_inode->i_hlist_node, &table->array[pos]);
+       if (++table->filled > table->capacity)
+               enlarge_inode_table(table);
        return 0;
 }
 
@@ -175,7 +177,7 @@ dentry_tree_fix_inodes(struct wim_dentry *root, struct hlist_head *inode_list)
 
        /* We use a hash table to map inode numbers to inodes.  */
 
-       ret = init_inode_table(&params.inode_table, 9001);
+       ret = init_inode_table(&params.inode_table, 64);
        if (ret)
                return ret;
 

diff --git a/src/inode_table.c b/src/inode_table.c
index e9c92d6a0571fa13ace88029452e8455cbb25231..248d0223962c03523431e1b19b498fb9cd8e7cfa 100644 (file)
--- a/src/inode_table.c
+++ b/src/inode_table.c
@@ -3,7 +3,7 @@
  */
 
 /*
- * Copyright (C) 2012, 2013, 2014 Eric Biggers
+ * Copyright (C) 2012-2016 Eric Biggers
  *
  * This file is free software; you can redistribute it and/or modify it under
  * the terms of the GNU Lesser General Public License as published by the Free
@@ -23,6 +23,7 @@
 #  include "config.h"
 #endif
 
+#include "wimlib/bitops.h"
 #include "wimlib/dentry.h"
 #include "wimlib/error.h"
 #include "wimlib/inode.h"
@@ -34,9 +35,11 @@
 int
 init_inode_table(struct wim_inode_table *table, size_t capacity)
 {
+       capacity = roundup_pow_of_2(capacity);
        table->array = CALLOC(capacity, sizeof(table->array[0]));
        if (!table->array)
                return WIMLIB_ERR_NOMEM;
+       table->filled = 0;
        table->capacity = capacity;
        INIT_HLIST_HEAD(&table->extra_inodes);
        return 0;
@@ -49,6 +52,32 @@ destroy_inode_table(struct wim_inode_table *table)
        FREE(table->array);
 }
 
+/* Double the capacity of the inode hash table.  */
+void
+enlarge_inode_table(struct wim_inode_table *table)
+{
+       const size_t old_capacity = table->capacity;
+       const size_t new_capacity = old_capacity * 2;
+       struct hlist_head *old_array = table->array;
+       struct hlist_head *new_array;
+       struct wim_inode *inode;
+       struct hlist_node *tmp;
+
+       new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
+       if (!new_array)
+               return;
+       table->array = new_array;
+       table->capacity = new_capacity;
+       for (size_t i = 0; i < old_capacity; i++) {
+               hlist_for_each_entry_safe(inode, tmp, &old_array[i], i_hlist_node) {
+                       hlist_add_head(&inode->i_hlist_node,
+                                      &new_array[hash_inode(table, inode->i_ino,
+                                                            inode->i_devno)]);
+               }
+       }
+       FREE(old_array);
+}
+
 /*
  * Allocate a new dentry, with hard link detection.
  *
@@ -98,8 +127,7 @@ inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
                list = &table->extra_inodes;
        } else {
                /* Hard link detection  */
-               list = &table->array[hash_u64(hash_u64(ino) + hash_u64(devno))
-                                    % table->capacity];
+               list = &table->array[hash_inode(table, ino, devno)];
                hlist_for_each_entry(inode, list, i_hlist_node) {
                        if (inode->i_ino != ino || inode->i_devno != devno)
                                continue;
@@ -121,9 +149,12 @@ inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
        if (ret)
                return ret;
        inode = dentry->d_inode;
-       hlist_add_head(&inode->i_hlist_node, list);
        inode->i_ino = ino;
        inode->i_devno = devno;
+       hlist_add_head(&inode->i_hlist_node, list);
+       if (list != &table->extra_inodes)
+               if (++table->filled > table->capacity)
+                       enlarge_inode_table(table);
        *dentry_ret = dentry;
        return 0;
 }

diff --git a/src/update_image.c b/src/update_image.c
index c07b19d6db609cb25a5bfdaefb7faf57b93b184b..63982cfea705e36381ebeca36b45ab0de433f876 100644 (file)
--- a/src/update_image.c
+++ b/src/update_image.c
@@ -1095,7 +1095,7 @@ execute_update_commands(WIMStruct *wim,
                inode_table = alloca(sizeof(struct wim_inode_table));
                sd_set = alloca(sizeof(struct wim_sd_set));
 
-               ret = init_inode_table(inode_table, 9001);
+               ret = init_inode_table(inode_table, 64);
                if (ret)
                        goto out;