From c6a1140e085f633273fcf47a6462bd9382ce118a Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Thu, 28 Mar 2013 21:20:26 -0500 Subject: [PATCH 1/1] WIM capture: Share inodes immediately 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. --- programs/imagex.c | 4 +- src/add_image.c | 57 +++++++++------- src/dentry.c | 2 +- src/dentry.h | 12 +++- src/hardlink.c | 148 +++++++++++++++++++++++++++++------------- src/ntfs-capture.c | 85 +++++++++++++++--------- src/util.c | 6 +- src/util.h | 6 ++ src/wimlib_internal.h | 43 +++++++++++- src/win32.c | 34 ++++++---- src/win32.h | 1 + src/write.c | 2 - 12 files changed, 274 insertions(+), 126 deletions(-) diff --git a/programs/imagex.c b/programs/imagex.c index d9ac676f..b78fa325 100644 --- a/programs/imagex.c +++ b/programs/imagex.c @@ -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; } diff --git a/src/add_image.c b/src/add_image.c index ac6be4d1..de9a465f 100644 --- a/src/add_image.c +++ b/src/add_image.c @@ -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; diff --git a/src/dentry.c b/src/dentry.c index 82a6b2d3..49d5d8cb 100644 --- a/src/dentry.c +++ b/src/dentry.c @@ -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)); diff --git a/src/dentry.h b/src/dentry.h index e8d8328d..601a40c5 100644 --- a/src/dentry.h +++ b/src/dentry.h @@ -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); diff --git a/src/hardlink.c b/src/hardlink.c index f8fed90e..ff42f26f 100644 --- a/src/hardlink.c +++ b/src/hardlink.c @@ -49,30 +49,8 @@ * ----------------- */ -/* 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; } diff --git a/src/ntfs-capture.c b/src/ntfs-capture.c index 2647e217..94e74cee 100644 --- a/src/ntfs-capture.c +++ b/src/ntfs-capture.c @@ -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, diff --git a/src/util.c b/src/util.c index 07d5fc6b..b688ac21 100644 --- a/src/util.c +++ b/src/util.c @@ -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. */ @@ -43,6 +41,10 @@ #include /* for getpid() */ +#ifdef __WIN32__ +#include "win32.h" +#endif + static size_t utf16le_strlen(const utf16lechar *s) { diff --git a/src/util.h b/src/util.h index 06c5045d..0a2478a5 100644 --- a/src/util.h +++ b/src/util.h @@ -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 */ diff --git a/src/wimlib_internal.h b/src/wimlib_internal.h index 6a6bc083..3d7fb488 100644 --- a/src/wimlib_internal.h +++ b/src/wimlib_internal.h @@ -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, diff --git a/src/win32.c b/src/win32.c index 7636c5fe..63838090 100644 --- a/src/win32.c +++ b/src/win32.c @@ -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, diff --git a/src/win32.h b/src/win32.h index 45909768..1df793f1 100644 --- a/src/win32.h +++ b/src/win32.h @@ -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, diff --git a/src/write.c b/src/write.c index 184489b1..e5dbbdf9 100644 --- a/src/write.c +++ b/src/write.c @@ -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); -- 2.43.0