WIM capture: Share inodes immediately
authorEric Biggers <ebiggers3@gmail.com>
Fri, 29 Mar 2013 02:20:26 +0000 (21:20 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 29 Mar 2013 02:41:24 +0000 (21:41 -0500)
Maintain a map (inode number, device number) => (WIM inode) throughout the
process of capturing a WIM image so that we can immediately detect a dentry that
refers to an already-captured inode.  Then, the inode can be shared immediately,
and its streams need not be read again.  In addition, the inodes need not be
sent through more complicated the hard link group disambiguation code; also, on
UNIX, capturing files with the same inode number but on different devices now
guaranteed to work correctly.

12 files changed:
programs/imagex.c
src/add_image.c
src/dentry.c
src/dentry.h
src/hardlink.c
src/ntfs-capture.c
src/util.c
src/util.h
src/wimlib_internal.h
src/win32.c
src/win32.h
src/write.c

index d9ac676..b78fa32 100644 (file)
@@ -712,8 +712,7 @@ parse_capture_config(tchar **contents_p, size_t nchars,
 {
        ssize_t nlines;
        tchar *p;
-       struct wimlib_capture_source *sources;
-       size_t i, j;
+       size_t i;
        enum capture_config_section cur_section;
 
        memset(config, 0, sizeof(*config));
@@ -1499,7 +1498,6 @@ out_free_capture_sources:
                free(capture_sources);
 out_free_source_list_contents:
        free(source_list_contents);
-out:
        return ret;
 }
 
index ac6be4d..de9a465 100644 (file)
@@ -159,6 +159,7 @@ unix_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                                 char *path,
                                 size_t path_len,
                                 struct wim_lookup_table *lookup_table,
+                                struct wim_inode_table *inode_table,
                                 const struct wimlib_capture_config *config,
                                 int add_image_flags,
                                 wimlib_progress_func_t progress_func);
@@ -168,6 +169,7 @@ unix_capture_directory(struct wim_dentry *dir_dentry,
                       char *path,
                       size_t path_len,
                       struct wim_lookup_table *lookup_table,
+                      struct wim_inode_table *inode_table,
                       const struct wimlib_capture_config *config,
                       int add_image_flags,
                       wimlib_progress_func_t progress_func)
@@ -211,6 +213,7 @@ unix_capture_directory(struct wim_dentry *dir_dentry,
                                                       path,
                                                       path_len + 1 + name_len,
                                                       lookup_table,
+                                                      inode_table,
                                                       config,
                                                       add_image_flags,
                                                       progress_func);
@@ -272,6 +275,7 @@ unix_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                                 char *path,
                                 size_t path_len,
                                 struct wim_lookup_table *lookup_table,
+                                struct wim_inode_table *inode_table,
                                 const struct wimlib_capture_config *config,
                                 int add_image_flags,
                                 wimlib_progress_func_t progress_func)
@@ -346,13 +350,19 @@ unix_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                goto out;
        }
 
-       ret = new_dentry_with_timeless_inode(path_basename_with_len(path, path_len),
-                                            &root);
+       ret = inode_table_new_dentry(inode_table,
+                                    path_basename_with_len(path, path_len),
+                                    stbuf.st_ino,
+                                    stbuf.st_dev,
+                                    &root);
        if (ret)
                goto out;
 
        inode = root->d_inode;
 
+       if (inode->i_nlink > 1) /* Already captured this inode? */
+               goto out;
+
 #ifdef HAVE_STAT_NANOSECOND_PRECISION
        inode->i_creation_time = timespec_to_wim_timestamp(stbuf.st_mtim);
        inode->i_last_write_time = timespec_to_wim_timestamp(stbuf.st_mtim);
@@ -362,17 +372,6 @@ unix_build_dentry_tree_recursive(struct wim_dentry **root_ret,
        inode->i_last_write_time = unix_timestamp_to_wim(stbuf.st_mtime);
        inode->i_last_access_time = unix_timestamp_to_wim(stbuf.st_atime);
 #endif
-       /* Leave the inode number at 0 for directories.  Otherwise grab the
-        * inode number from the `stat' buffer, including the device number if
-        * possible. */
-       if (!S_ISDIR(stbuf.st_mode)) {
-               if (sizeof(ino_t) >= 8)
-                       inode->i_ino = (u64)stbuf.st_ino;
-               else
-                       inode->i_ino = (u64)stbuf.st_ino |
-                                          ((u64)stbuf.st_dev <<
-                                               ((sizeof(ino_t) * 8) & 63));
-       }
        inode->i_resolved = 1;
        if (add_image_flags & WIMLIB_ADD_IMAGE_FLAG_UNIX_DATA) {
                ret = inode_set_unix_data(inode, stbuf.st_uid,
@@ -389,7 +388,7 @@ unix_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                                                inode, lookup_table);
        else if (S_ISDIR(stbuf.st_mode))
                ret = unix_capture_directory(root, path, path_len,
-                                            lookup_table, config,
+                                            lookup_table, inode_table, config,
                                             add_image_flags, progress_func);
        else
                ret = unix_capture_symlink(path, inode, lookup_table);
@@ -438,6 +437,7 @@ static int
 unix_build_dentry_tree(struct wim_dentry **root_ret,
                       const char *root_disk_path,
                       struct wim_lookup_table *lookup_table,
+                      struct wim_inode_table *inode_table,
                       struct sd_set *sd_set,
                       const struct wimlib_capture_config *config,
                       int add_image_flags,
@@ -463,6 +463,7 @@ unix_build_dentry_tree(struct wim_dentry **root_ret,
                                               path_buf,
                                               path_len,
                                               lookup_table,
+                                              inode_table,
                                               config,
                                               add_image_flags,
                                               progress_func);
@@ -670,8 +671,8 @@ new_filler_directory(const tchar *name, struct wim_dentry **dentry_ret)
        DEBUG("Creating filler directory \"%"TS"\"", name);
        ret = new_dentry_with_inode(name, &dentry);
        if (ret == 0) {
-               /* Leave the inode number as 0 for now.  The final inode number
-                * will be assigned later by assign_inode_numbers(). */
+               /* Leave the inode number as 0; this is allowed for non
+                * hard-linked files. */
                dentry->d_inode->i_resolved = 1;
                dentry->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
                *dentry_ret = dentry;
@@ -856,6 +857,7 @@ wimlib_add_image_multisource(WIMStruct *w,
        int (*capture_tree)(struct wim_dentry **,
                            const tchar *,
                            struct wim_lookup_table *,
+                           struct wim_inode_table *,
                            struct sd_set *,
                            const struct wimlib_capture_config *,
                            int,
@@ -866,6 +868,7 @@ wimlib_add_image_multisource(WIMStruct *w,
        struct wim_dentry *branch;
        struct wim_security_data *sd;
        struct wim_image_metadata *imd;
+       struct wim_inode_table inode_table;
        int ret;
        struct sd_set sd_set;
 
@@ -936,11 +939,15 @@ wimlib_add_image_multisource(WIMStruct *w,
        if (ret)
                goto out;
 
+       ret = init_inode_table(&inode_table, 9001);
+       if (ret)
+               goto out;
+
        DEBUG("Allocating security data");
        sd = CALLOC(1, sizeof(struct wim_security_data));
        if (!sd) {
                ret = WIMLIB_ERR_NOMEM;
-               goto out;
+               goto out_destroy_inode_table;
        }
        sd->total_length = 8;
        sd->refcnt = 1;
@@ -948,6 +955,7 @@ wimlib_add_image_multisource(WIMStruct *w,
        sd_set.sd = sd;
        sd_set.rb_root.rb_node = NULL;
 
+
        DEBUG("Using %zu capture sources", num_sources);
        canonicalize_sources_and_targets(sources, num_sources);
        sort_sources(sources, num_sources);
@@ -957,6 +965,7 @@ wimlib_add_image_multisource(WIMStruct *w,
                goto out_free_security_data;
        }
 
+
        DEBUG("Building dentry tree.");
        root_dentry = NULL;
 
@@ -982,6 +991,7 @@ wimlib_add_image_multisource(WIMStruct *w,
                ret = (*capture_tree)(&branch,
                                      sources[i].fs_source_path,
                                      w->lookup_table,
+                                     &inode_table,
                                      &sd_set,
                                      config,
                                      flags,
@@ -1027,12 +1037,8 @@ wimlib_add_image_multisource(WIMStruct *w,
 
        imd = &w->image_metadata[w->hdr.image_count - 1];
 
-       ret = dentry_tree_fix_inodes(root_dentry, &imd->inode_list);
-       if (ret)
-               goto out_destroy_imd;
-
        DEBUG("Assigning hard link group IDs");
-       assign_inode_numbers(&imd->inode_list);
+       inode_table_prepare_inode_list(&inode_table, &imd->inode_list);
 
        ret = xml_add_image(w, name);
        if (ret)
@@ -1041,19 +1047,20 @@ wimlib_add_image_multisource(WIMStruct *w,
        if (add_image_flags & WIMLIB_ADD_IMAGE_FLAG_BOOT)
                wimlib_set_boot_idx(w, w->hdr.image_count);
        ret = 0;
-       goto out_destroy_sd_set;
+       goto out_destroy_inode_table;
 out_destroy_imd:
        destroy_image_metadata(&w->image_metadata[w->hdr.image_count - 1],
                               w->lookup_table);
        w->hdr.image_count--;
-       goto out_destroy_sd_set;
+       goto out_destroy_inode_table;
 out_free_branch:
        free_dentry_tree(branch, w->lookup_table);
 out_free_dentry_tree:
        free_dentry_tree(root_dentry, w->lookup_table);
 out_free_security_data:
        free_security_data(sd);
-out_destroy_sd_set:
+out_destroy_inode_table:
+       destroy_inode_table(&inode_table);
        destroy_sd_set(&sd_set);
 out:
        return ret;
index 82a6b2d..49d5d8c 100644 (file)
@@ -669,7 +669,7 @@ dentry_common_init(struct wim_dentry *dentry)
        dentry->refcnt = 1;
 }
 
-static struct wim_inode *
+struct wim_inode *
 new_timeless_inode()
 {
        struct wim_inode *inode = CALLOC(1, sizeof(struct wim_inode));
index e8d8328..601a40c 100644 (file)
@@ -271,7 +271,14 @@ struct wim_inode {
 
        struct hlist_node i_hlist;
 
-       struct list_head i_lte_inode_list;
+       union {
+               /* Used during image extraction to build a list of inodes that
+                * share a certain stream */
+               struct list_head i_lte_inode_list;
+
+               /* Device number, used only during image capture */
+               u64 i_devno;
+       };
 
        tchar *i_extracted_file;
 
@@ -372,6 +379,9 @@ print_dentry(struct wim_dentry *dentry, void *lookup_table);
 extern int
 print_dentry_full_path(struct wim_dentry *entry, void *ignore);
 
+extern struct wim_inode *
+new_timeless_inode();
+
 extern int
 new_dentry(const tchar *name, struct wim_dentry **dentry_ret);
 
index f8fed90..ff42f26 100644 (file)
  *                            -----------------
  */
 
-/* Hash table to find inodes, identified by their inode ID.
- * */
-struct wim_inode_table {
-       /* Fields for the hash table */
-       struct hlist_head *array;
-       u64 num_entries;
-       u64 capacity;
-
-       /*
-        * Linked list of "extra" inodes.  These may be:
-        *
-        * - inodes with link count 1, which are all allowed to have 0 for their
-        *   inode number, meaning we cannot insert them into the hash table
-        *   before calling assign_inode_numbers().
-         *
-        * - Groups we create ourselves by splitting a nominal inode due to
-        *   inconsistencies in the dentries.  These inodes will share a inode
-        *   number with some other inode until assign_inode_numbers() is
-        *   called.
-        */
-       struct hlist_head extra_inodes;
-};
 
-static int
+int
 init_inode_table(struct wim_inode_table *table, size_t capacity)
 {
        table->array = CALLOC(capacity, sizeof(table->array[0]));
@@ -86,12 +64,6 @@ init_inode_table(struct wim_inode_table *table, size_t capacity)
        return 0;
 }
 
-static inline void
-destroy_inode_table(struct wim_inode_table *table)
-{
-       FREE(table->array);
-}
-
 static inline size_t
 inode_link_count(const struct wim_inode *inode)
 {
@@ -150,6 +122,62 @@ inode_table_insert(struct wim_dentry *dentry, void *_table)
        return 0;
 }
 
+static struct wim_inode *
+inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno)
+{
+       u64 hash = hash_u64(hash_u64(ino) + hash_u64(devno));
+       size_t pos = hash % table->capacity;
+       struct wim_inode *inode;
+       struct hlist_node *cur;
+
+       hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
+               if (inode->i_ino == ino && inode->i_devno == devno) {
+                       DEBUG("Using existing inode {devno=%"PRIu64", ino=%"PRIu64"}",
+                             devno, ino);
+                       inode->i_nlink++;
+                       return inode;
+               }
+       }
+       inode = new_timeless_inode();
+       if (inode) {
+               inode->i_ino = ino;
+               inode->i_devno = devno;
+               hlist_add_head(&inode->i_hlist, &table->array[pos]);
+               table->num_entries++;
+       }
+       return inode;
+}
+
+/* Given a directory entry with the name @name for the file with the inode
+ * number @ino and device number @devno, create a new WIM dentry with an
+ * associated inode, where the inode is shared if an inode with the same @ino
+ * and @devno has already been created.  On success, the new WIM dentry is
+ * written to *dentry_ret, and its inode has i_nlink > 1 if a previously
+ * existing inode was used.
+ */
+int
+inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
+                      u64 ino, u64 devno, struct wim_dentry **dentry_ret)
+{
+       struct wim_dentry *dentry;
+       struct wim_inode *inode;
+       int ret;
+
+       ret = new_dentry(name, &dentry);
+       if (ret)
+               return ret;
+
+       inode = inode_table_get_inode(table, ino, devno);
+       if (!inode) {
+               free_dentry(dentry);
+               return WIMLIB_ERR_NOMEM;
+       }
+       dentry->d_inode = inode;
+       inode_add_dentry(dentry, inode);
+       *dentry_ret = dentry;
+       return 0;
+}
+
 #if defined(ENABLE_ERROR_MESSAGES) || defined(ENABLE_DEBUG)
 static void
 print_inode_dentries(const struct wim_inode *inode)
@@ -286,7 +314,8 @@ fix_true_inode(struct wim_inode *inode, struct hlist_head *inode_list)
  * group remaining.
  */
 static int
-fix_nominal_inode(struct wim_inode *inode, struct hlist_head *inode_list)
+fix_nominal_inode(struct wim_inode *inode, struct hlist_head *inode_list,
+                 bool *ino_changes_needed)
 {
        struct wim_dentry *dentry;
        struct hlist_node *cur, *tmp;
@@ -378,8 +407,8 @@ next_dentry_2:
                list_for_each_entry(dentry, &dentries_with_no_data_streams, tmp_list)
                        inode_add_dentry(dentry, inode);
        }
-       #ifdef ENABLE_DEBUG
         if (num_true_inodes != 1) {
+       #ifdef ENABLE_DEBUG
                inode = container_of(true_inodes.first, struct wim_inode, i_hlist);
 
                tprintf(T("Split nominal inode 0x%"PRIx64" into %zu "
@@ -394,8 +423,9 @@ next_dentry_2:
                }
                tputs(T("----------------------------------------------------"
                        "--------------------------"));
-        }
        #endif
+               *ino_changes_needed = true;
+        }
 
        hlist_for_each_entry_safe(inode, cur, tmp, &true_inodes, i_hlist) {
                ret = fix_true_inode(inode, inode_list);
@@ -406,7 +436,8 @@ next_dentry_2:
 }
 
 static int
-fix_inodes(struct wim_inode_table *table, struct hlist_head *inode_list)
+fix_inodes(struct wim_inode_table *table, struct hlist_head *inode_list,
+          bool *ino_changes_needed)
 {
        struct wim_inode *inode;
        struct hlist_node *cur, *tmp;
@@ -414,7 +445,7 @@ fix_inodes(struct wim_inode_table *table, struct hlist_head *inode_list)
        INIT_HLIST_HEAD(inode_list);
        for (u64 i = 0; i < table->capacity; i++) {
                hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist) {
-                       ret = fix_nominal_inode(inode, inode_list);
+                       ret = fix_nominal_inode(inode, inode_list, ino_changes_needed);
                        if (ret != 0)
                                return ret;
                }
@@ -457,32 +488,57 @@ dentry_tree_fix_inodes(struct wim_dentry *root, struct hlist_head *inode_list)
 {
        struct wim_inode_table inode_tab;
        int ret;
+       bool ino_changes_needed;
 
        DEBUG("Inserting dentries into inode table");
        ret = init_inode_table(&inode_tab, 9001);
-       if (ret != 0)
+       if (ret)
                return ret;
 
        for_dentry_in_tree(root, inode_table_insert, &inode_tab);
 
        DEBUG("Cleaning up the hard link groups");
-       ret = fix_inodes(&inode_tab, inode_list);
+       ino_changes_needed = false;
+       ret = fix_inodes(&inode_tab, inode_list, &ino_changes_needed);
        destroy_inode_table(&inode_tab);
+
+       if (ret == 0 && ino_changes_needed) {
+               u64 cur_ino = 1;
+               struct hlist_node *tmp;
+               struct wim_inode *inode;
+
+               WARNING("Re-assigning inode numbers due to inode inconsistencies");
+               hlist_for_each_entry(inode, tmp, inode_list, i_hlist) {
+                       if (inode->i_nlink > 1)
+                               inode->i_ino = cur_ino++;
+                       else
+                               inode->i_ino = 0;
+               }
+       }
        return ret;
 }
 
-/* Assign inode numbers to a list of inodes and return the next available
- * number. */
-u64
-assign_inode_numbers(struct hlist_head *inode_list)
+/* Assign consecutive inode numbers to the inodes in the inode table, and move
+ * the inodes to a single list @head. */
+void
+inode_table_prepare_inode_list(struct wim_inode_table *table,
+                              struct hlist_head *head)
 {
-       DEBUG("Assigning inode numbers");
        struct wim_inode *inode;
-       struct hlist_node *cur;
+       struct hlist_node *cur, *tmp;
        u64 cur_ino = 1;
-       hlist_for_each_entry(inode, cur, inode_list, i_hlist) {
-               inode->i_ino = cur_ino;
-               cur_ino++;
+
+       INIT_HLIST_HEAD(head);
+       for (size_t i = 0; i < table->capacity; i++) {
+               hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist)
+               {
+                       if (inode->i_nlink > 1)
+                               inode->i_ino = cur_ino++;
+                       else
+                               inode->i_ino = 0;
+                       hlist_add_head(&inode->i_hlist, head);
+               }
+               INIT_HLIST_HEAD(&table->array[i]);
        }
-       return cur_ino;
+       table->num_entries = 0;
 }
index 2647e21..94e74ce 100644 (file)
@@ -119,7 +119,7 @@ out_error:
 /* Load the streams from a file or reparse point in the NTFS volume into the WIM
  * lookup table */
 static int
-capture_ntfs_streams(struct wim_dentry *dentry,
+capture_ntfs_streams(struct wim_inode *inode,
                     ntfs_inode *ni,
                     char *path,
                     size_t path_len,
@@ -173,7 +173,7 @@ capture_ntfs_streams(struct wim_dentry *dentry,
                                goto out_put_actx;
 
                        if (type == AT_REPARSE_POINT)
-                               dentry->d_inode->i_reparse_tag = reparse_tag;
+                               inode->i_reparse_tag = reparse_tag;
 
                        /* Make a lookup table entry for the stream, or use an existing
                         * one if there's already an identical stream. */
@@ -222,19 +222,19 @@ capture_ntfs_streams(struct wim_dentry *dentry,
                if (name_length == 0) {
                        /* Unnamed data stream.  Put the reference to it in the
                         * dentry's inode. */
-                       if (dentry->d_inode->i_lte) {
+                       if (inode->i_lte) {
                                WARNING("Found two un-named data streams for "
                                        "`%s'", path);
                                free_lookup_table_entry(lte);
                        } else {
-                               dentry->d_inode->i_lte = lte;
+                               inode->i_lte = lte;
                        }
                } else {
                        /* Named data stream.  Put the reference to it in the
                         * alternate data stream entries */
                        struct wim_ads_entry *new_ads_entry;
 
-                       new_ads_entry = inode_add_ads_utf16le(dentry->d_inode,
+                       new_ads_entry = inode_add_ads_utf16le(inode,
                                                              attr_record_name(actx->attr),
                                                              name_length * 2);
                        if (!new_ads_entry)
@@ -394,6 +394,7 @@ struct readdir_ctx {
        char *path;
        size_t path_len;
        struct wim_lookup_table *lookup_table;
+       struct wim_inode_table *inode_table;
        struct sd_set *sd_set;
        struct dos_name_map *dos_name_map;
        const struct wimlib_capture_config *config;
@@ -410,6 +411,7 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
                                 size_t path_len,
                                 int name_type,
                                 struct wim_lookup_table *lookup_table,
+                                struct wim_inode_table *inode_table,
                                 struct sd_set *sd_set,
                                 const struct wimlib_capture_config *config,
                                 ntfs_volume **ntfs_vol_p,
@@ -473,7 +475,9 @@ wim_ntfs_capture_filldir(void *dirent, const ntfschar *name,
        child = NULL;
        ret = build_dentry_tree_ntfs_recursive(&child, ctx->dir_ni,
                                               ni, ctx->path, path_len, name_type,
-                                              ctx->lookup_table, ctx->sd_set,
+                                              ctx->lookup_table,
+                                              ctx->inode_table,
+                                              ctx->sd_set,
                                               ctx->config, ctx->ntfs_vol_p,
                                               ctx->add_image_flags,
                                               ctx->progress_func);
@@ -491,13 +495,14 @@ out:
  * the NTFS streams, and build an array of security descriptors.
  */
 static int
-build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
+build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret,
                                 ntfs_inode *dir_ni,
                                 ntfs_inode *ni,
                                 char *path,
                                 size_t path_len,
                                 int name_type,
                                 struct wim_lookup_table *lookup_table,
+                                struct wim_inode_table *inode_table,
                                 struct sd_set *sd_set,
                                 const struct wimlib_capture_config *config,
                                 ntfs_volume **ntfs_vol_p,
@@ -507,6 +512,7 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
        u32 attributes;
        int ret;
        struct wim_dentry *root;
+       struct wim_inode *inode;
 
        if (exclude_path(path, path_len, config, false)) {
                /* Exclude a file or directory tree based on the capture
@@ -519,8 +525,9 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
                        info.scan.excluded = true;
                        progress_func(WIMLIB_PROGRESS_MSG_SCAN_DENTRY, &info);
                }
-               *root_p = NULL;
-               return 0;
+               root = NULL;
+               ret = 0;
+               goto out;
        }
 
        /* Get file attributes */
@@ -545,28 +552,33 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
                progress_func(WIMLIB_PROGRESS_MSG_SCAN_DENTRY, &info);
        }
 
-       /* Create the new WIM dentry */
-       ret = new_dentry_with_timeless_inode(path_basename_with_len(path, path_len),
-                                            &root);
+       /* Create a WIM dentry with an associated inode, which may be shared */
+       ret = inode_table_new_dentry(inode_table,
+                                    path_basename_with_len(path, path_len),
+                                    ni->mft_no,
+                                    0,
+                                    &root);
        if (ret)
                return ret;
 
-       *root_p = root;
+       inode = root->d_inode;
+
+       if (inode->i_nlink > 1) /* Shared inode; nothing more to do */
+               goto out;
 
        if (name_type & FILE_NAME_WIN32) /* Win32 or Win32+DOS name */
                root->is_win32_name = 1;
-       root->d_inode->i_creation_time    = le64_to_cpu(ni->creation_time);
-       root->d_inode->i_last_write_time  = le64_to_cpu(ni->last_data_change_time);
-       root->d_inode->i_last_access_time = le64_to_cpu(ni->last_access_time);
-       root->d_inode->i_attributes       = le32_to_cpu(attributes);
-       root->d_inode->i_ino              = ni->mft_no;
-       root->d_inode->i_resolved         = 1;
+       inode->i_creation_time    = le64_to_cpu(ni->creation_time);
+       inode->i_last_write_time  = le64_to_cpu(ni->last_data_change_time);
+       inode->i_last_access_time = le64_to_cpu(ni->last_access_time);
+       inode->i_attributes       = le32_to_cpu(attributes);
+       inode->i_resolved         = 1;
 
        if (attributes & FILE_ATTR_REPARSE_POINT) {
                /* Junction point, symbolic link, or other reparse point */
-               ret = capture_ntfs_streams(root, ni, path, path_len,
-                                          lookup_table, ntfs_vol_p,
-                                          AT_REPARSE_POINT);
+               ret = capture_ntfs_streams(inode, ni, path,
+                                          path_len, lookup_table,
+                                          ntfs_vol_p, AT_REPARSE_POINT);
        } else if (ni->mrec->flags & MFT_RECORD_IS_DIRECTORY) {
 
                /* Normal directory */
@@ -578,6 +590,7 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
                        .path            = path,
                        .path_len        = path_len,
                        .lookup_table    = lookup_table,
+                       .inode_table     = inode_table,
                        .sd_set          = sd_set,
                        .dos_name_map    = &dos_name_map,
                        .config          = config,
@@ -596,12 +609,12 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
                destroy_dos_name_map(&dos_name_map);
        } else {
                /* Normal file */
-               ret = capture_ntfs_streams(root, ni, path, path_len,
-                                          lookup_table, ntfs_vol_p,
-                                          AT_DATA);
+               ret = capture_ntfs_streams(inode, ni, path,
+                                          path_len, lookup_table,
+                                          ntfs_vol_p, AT_DATA);
        }
-       if (ret != 0)
-               return ret;
+       if (ret)
+               goto out;
 
        if (!(add_image_flags & WIMLIB_ADD_IMAGE_FLAG_NO_ACLS)) {
                /* Get security descriptor */
@@ -617,23 +630,29 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_p,
                                                         ni, dir_ni, sd, ret);
                }
                if (ret > 0) {
-                       root->d_inode->i_security_id = sd_set_add_sd(sd_set, sd, ret);
-                       if (root->d_inode->i_security_id == -1) {
+                       inode->i_security_id = sd_set_add_sd(sd_set, sd, ret);
+                       if (inode->i_security_id == -1) {
                                ERROR("Out of memory");
-                               return WIMLIB_ERR_NOMEM;
+                               ret = WIMLIB_ERR_NOMEM;
+                               goto out;
                        }
                        DEBUG("Added security ID = %u for `%s'",
-                             root->d_inode->i_security_id, path);
+                             inode->i_security_id, path);
                        ret = 0;
                } else if (ret < 0) {
                        ERROR_WITH_ERRNO("Failed to get security information from "
                                         "`%s'", path);
                        ret = WIMLIB_ERR_NTFS_3G;
                } else {
-                       root->d_inode->i_security_id = -1;
+                       inode->i_security_id = -1;
                        DEBUG("No security ID for `%s'", path);
                }
        }
+out:
+       if (ret == 0)
+               *root_ret = root;
+       else
+               free_dentry_tree(root, lookup_table);
        return ret;
 }
 
@@ -641,6 +660,7 @@ int
 build_dentry_tree_ntfs(struct wim_dentry **root_p,
                       const char *device,
                       struct wim_lookup_table *lookup_table,
+                      struct wim_inode_table *inode_table,
                       struct sd_set *sd_set,
                       const struct wimlib_capture_config *config,
                       int add_image_flags,
@@ -695,6 +715,7 @@ build_dentry_tree_ntfs(struct wim_dentry **root_p,
        path[1] = '\0';
        ret = build_dentry_tree_ntfs_recursive(root_p, NULL, root_ni, path, 1,
                                               FILE_NAME_POSIX, lookup_table,
+                                              inode_table,
                                               sd_set,
                                               config, ntfs_vol_p,
                                               add_image_flags,
index 07d5fc6..b688ac2 100644 (file)
@@ -23,8 +23,6 @@
 
 #include "config.h"
 
-#define MINGW_HAS_SECURE_API
-
 #undef _GNU_SOURCE
 /* Make sure the POSIX-compatible strerror_r() is declared, rather than the GNU
  * version, which has a different return type. */
 
 #include <unistd.h> /* for getpid() */
 
+#ifdef __WIN32__
+#include "win32.h"
+#endif
+
 static size_t
 utf16le_strlen(const utf16lechar *s)
 {
index 06c5045..0a2478a 100644 (file)
@@ -279,4 +279,10 @@ wimlib_printf(const tchar *format, ...) FORMAT(printf, 1, 2);
 extern void
 zap_backslashes(tchar *s);
 
+static inline u64
+hash_u64(u64 n)
+{
+       return n * 0x9e37fffffffc0001ULL;
+}
+
 #endif /* _WIMLIB_UTIL_H */
index 6a6bc08..3d7fb48 100644 (file)
@@ -370,8 +370,46 @@ add_new_dentry_tree(WIMStruct *dest_wim, struct wim_dentry *root,
 
 /* hardlink.c */
 
-extern u64
-assign_inode_numbers(struct hlist_head *inode_list);
+/* Hash table to find inodes, given an inode number (in the case of reading
+ * a WIM images), or both an inode number and a device number (in the case of
+ * capturing a WIM image). */
+struct wim_inode_table {
+       /* Fields for the hash table */
+       struct hlist_head *array;
+       u64 num_entries;
+       u64 capacity;
+
+       /*
+        * Linked list of "extra" inodes.  These may be:
+        *
+        * - inodes with link count 1, which are all allowed to have 0 for their
+        *   inode number, meaning we cannot insert them into the hash table.
+         *
+        * - Groups we create ourselves by splitting a nominal inode due to
+        *   inconsistencies in the dentries.  These inodes will share an inode
+        *   number with some other inode until assign_inode_numbers() is
+        *   called.
+        */
+       struct hlist_head extra_inodes;
+};
+
+extern int
+init_inode_table(struct wim_inode_table *table, size_t capacity);
+
+extern int
+inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
+                      u64 ino, u64 devno, struct wim_dentry **dentry_ret);
+
+extern void
+inode_table_prepare_inode_list(struct wim_inode_table *table,
+                              struct hlist_head *head);
+
+static inline void
+destroy_inode_table(struct wim_inode_table *table)
+{
+       FREE(table->array);
+}
+
 
 extern int
 dentry_tree_fix_inodes(struct wim_dentry *root, struct hlist_head *inode_list);
@@ -461,6 +499,7 @@ extern int
 build_dentry_tree_ntfs(struct wim_dentry **root_p,
                       const tchar *device,
                       struct wim_lookup_table *lookup_table,
+                      struct wim_inode_table *inode_table,
                       struct sd_set *sd_set,
                       const struct wimlib_capture_config *config,
                       int add_image_flags,
index 7636c5f..6383809 100644 (file)
@@ -310,6 +310,7 @@ win32_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                                  wchar_t *path,
                                  size_t path_num_chars,
                                  struct wim_lookup_table *lookup_table,
+                                 struct wim_inode_table *inode_table,
                                  struct sd_set *sd_set,
                                  const struct wimlib_capture_config *config,
                                  int add_image_flags,
@@ -323,6 +324,7 @@ win32_recurse_directory(struct wim_dentry *root,
                        wchar_t *dir_path,
                        size_t dir_path_num_chars,
                        struct wim_lookup_table *lookup_table,
+                       struct wim_inode_table *inode_table,
                        struct sd_set *sd_set,
                        const struct wimlib_capture_config *config,
                        int add_image_flags,
@@ -375,6 +377,7 @@ win32_recurse_directory(struct wim_dentry *root,
                                                        dir_path,
                                                        path_len,
                                                        lookup_table,
+                                                       inode_table,
                                                        sd_set,
                                                        config,
                                                        add_image_flags,
@@ -734,6 +737,7 @@ win32_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                                  wchar_t *path,
                                  size_t path_num_chars,
                                  struct wim_lookup_table *lookup_table,
+                                 struct wim_inode_table *inode_table,
                                  struct sd_set *sd_set,
                                  const struct wimlib_capture_config *config,
                                  int add_image_flags,
@@ -792,29 +796,32 @@ win32_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                goto out_close_handle;
        }
 
-       /* Create a WIM dentry */
-       ret = new_dentry_with_timeless_inode(path_basename_with_len(path, path_num_chars),
-                                            &root);
+       /* Create a WIM dentry with an associated inode, which may be shared */
+       ret = inode_table_new_dentry(inode_table,
+                                    path_basename_with_len(path, path_num_chars),
+                                    ((u64)file_info.nFileIndexHigh << 32) |
+                                        (u64)file_info.nFileIndexLow,
+                                    file_info.dwVolumeSerialNumber,
+                                    &root);
+       if (ret)
+               goto out_close_handle;
+
+       ret = win32_get_short_name(root, path);
        if (ret)
                goto out_close_handle;
 
-       /* Start preparing the associated WIM inode */
        inode = root->d_inode;
 
+       if (inode->i_nlink > 1) /* Shared inode; nothing more to do */
+               goto out_close_handle;
+
        inode->i_attributes = file_info.dwFileAttributes;
        inode->i_creation_time = FILETIME_to_u64(&file_info.ftCreationTime);
        inode->i_last_write_time = FILETIME_to_u64(&file_info.ftLastWriteTime);
        inode->i_last_access_time = FILETIME_to_u64(&file_info.ftLastAccessTime);
-       inode->i_ino = ((u64)file_info.nFileIndexHigh << 32) |
-                       (u64)file_info.nFileIndexLow;
-
        inode->i_resolved = 1;
-       add_image_flags &= ~(WIMLIB_ADD_IMAGE_FLAG_ROOT | WIMLIB_ADD_IMAGE_FLAG_SOURCE);
 
-       /* Get DOS name and security descriptor (if any). */
-       ret = win32_get_short_name(root, path);
-       if (ret)
-               goto out_close_handle;
+       add_image_flags &= ~(WIMLIB_ADD_IMAGE_FLAG_ROOT | WIMLIB_ADD_IMAGE_FLAG_SOURCE);
 
        if (!(add_image_flags & WIMLIB_ADD_IMAGE_FLAG_NO_ACLS)) {
                ret = win32_get_security_descriptor(root, sd_set, path, state,
@@ -842,6 +849,7 @@ win32_build_dentry_tree_recursive(struct wim_dentry **root_ret,
                                              path,
                                              path_num_chars,
                                              lookup_table,
+                                             inode_table,
                                              sd_set,
                                              config,
                                              add_image_flags,
@@ -911,6 +919,7 @@ int
 win32_build_dentry_tree(struct wim_dentry **root_ret,
                        const wchar_t *root_disk_path,
                        struct wim_lookup_table *lookup_table,
+                       struct wim_inode_table *inode_table,
                        struct sd_set *sd_set,
                        const struct wimlib_capture_config *config,
                        int add_image_flags,
@@ -941,6 +950,7 @@ win32_build_dentry_tree(struct wim_dentry **root_ret,
                                                path,
                                                path_nchars,
                                                lookup_table,
+                                               inode_table,
                                                sd_set,
                                                config,
                                                add_image_flags,
index 4590976..1df793f 100644 (file)
@@ -9,6 +9,7 @@ extern int
 win32_build_dentry_tree(struct wim_dentry **root_ret,
                        const tchar *root_disk_path,
                        struct wim_lookup_table *lookup_table,
+                       struct wim_inode_table *inode_table,
                        struct sd_set *sd,
                        const struct wimlib_capture_config *config,
                        int add_image_flags,
index 184489b..e5dbbdf 100644 (file)
@@ -1886,7 +1886,6 @@ overwrite_wim_inplace(WIMStruct *w, int write_flags,
        int ret;
        struct list_head stream_list;
        off_t old_wim_end;
-       bool found_modified_image;
 
        DEBUG("Overwriting `%"TS"' in-place", w->filename);
 
@@ -1957,7 +1956,6 @@ overwrite_wim_inplace(WIMStruct *w, int write_flags,
                DEBUG("No new streams were added");
        }
 
-       found_modified_image = false;
        for (int i = 0; i < w->hdr.image_count; i++) {
                if (w->image_metadata[i].modified) {
                        select_wim_image(w, i + 1);