From: Eric Biggers Date: Mon, 3 Sep 2012 04:15:24 +0000 (-0500) Subject: Rewrite to use inodes (IN PROGRESS) X-Git-Tag: v1.0.2~14 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=67f45cecd793345416d5d85fbe37ec54b1bb6ef8 Rewrite to use inodes (IN PROGRESS) --- diff --git a/src/dentry.c b/src/dentry.c index 3c3c18bc..20fd3491 100644 --- a/src/dentry.c +++ b/src/dentry.c @@ -77,8 +77,9 @@ static u64 dentry_correct_length(const struct dentry *dentry) static u64 __dentry_total_length(const struct dentry *dentry, u64 length) { - for (u16 i = 0; i < dentry->num_ads; i++) - length += ads_entry_total_length(&dentry->ads_entries[i]); + const struct inode *inode = dentry->inode; + for (u16 i = 0; i < inode->num_ads; i++) + length += ads_entry_total_length(inode->ads_entries[i]); return (length + 7) & ~7; } @@ -98,13 +99,14 @@ u64 dentry_total_length(const struct dentry *dentry) /* Transfers file attributes from a `stat' buffer to a struct dentry. */ void stbuf_to_dentry(const struct stat *stbuf, struct dentry *dentry) { + struct inode *inode = dentry->inode; if (S_ISLNK(stbuf->st_mode)) { - dentry->attributes = FILE_ATTRIBUTE_REPARSE_POINT; - dentry->reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK; + inode->attributes = FILE_ATTRIBUTE_REPARSE_POINT; + inode->reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK; } else if (S_ISDIR(stbuf->st_mode)) { - dentry->attributes = FILE_ATTRIBUTE_DIRECTORY; + inode->attributes = FILE_ATTRIBUTE_DIRECTORY; } else { - dentry->attributes = FILE_ATTRIBUTE_NORMAL; + inode->attributes = FILE_ATTRIBUTE_NORMAL; } if (sizeof(ino_t) >= 8) dentry->link_group_id = (u64)stbuf->st_ino; @@ -112,161 +114,89 @@ void stbuf_to_dentry(const struct stat *stbuf, struct dentry *dentry) dentry->link_group_id = (u64)stbuf->st_ino | ((u64)stbuf->st_dev << (sizeof(ino_t) * 8)); /* Set timestamps */ - dentry->creation_time = timespec_to_wim_timestamp(&stbuf->st_mtim); - dentry->last_write_time = timespec_to_wim_timestamp(&stbuf->st_mtim); - dentry->last_access_time = timespec_to_wim_timestamp(&stbuf->st_atim); + inode->creation_time = timespec_to_wim_timestamp(&stbuf->st_mtim); + inode->last_write_time = timespec_to_wim_timestamp(&stbuf->st_mtim); + inode->last_access_time = timespec_to_wim_timestamp(&stbuf->st_atim); } /* Sets all the timestamp fields of the dentry to the current time. */ -void dentry_update_all_timestamps(struct dentry *dentry) +void inode_update_all_timestamps(struct inode *inode) { u64 now = get_wim_timestamp(); - dentry->creation_time = now; - dentry->last_access_time = now; - dentry->last_write_time = now; + inode->creation_time = now; + inode->last_access_time = now; + inode->last_write_time = now; } -/* Returns the alternate data stream entry belonging to @dentry that has the +/* Returns the alternate data stream entry belonging to @inode that has the * stream name @stream_name. */ -struct ads_entry *dentry_get_ads_entry(struct dentry *dentry, - const char *stream_name) +struct ads_entry *inode_get_ads_entry(struct inode *inode, + const char *stream_name) { size_t stream_name_len; if (!stream_name) return NULL; - if (dentry->num_ads) { + if (inode->num_ads) { u16 i = 0; stream_name_len = strlen(stream_name); do { - if (ads_entry_has_name(&dentry->ads_entries[i], + if (ads_entry_has_name(inode->ads_entries[i], stream_name, stream_name_len)) - return &dentry->ads_entries[i]; - } while (++i != dentry->num_ads); + return inode->ads_entries[i]; + } while (++i != inode->num_ads); } return NULL; } -static void ads_entry_init(struct ads_entry *ads_entry) + +static struct ads_entry *new_ads_entry(const char *name) { - memset(ads_entry, 0, sizeof(struct ads_entry)); + struct ads_entry *ads_entry = CALLOC(1, sizeof(struct ads_entry)); + if (!ads_entry) + return NULL; INIT_LIST_HEAD(&ads_entry->lte_group_list.list); ads_entry->lte_group_list.type = STREAM_TYPE_ADS; + if (name && *name) { + if (change_ads_name(ads_entry, name)) { + FREE(ads_entry); + return NULL; + } + } + return ads_entry; } /* - * Add an alternate stream entry to a dentry and return a pointer to it, or NULL + * Add an alternate stream entry to an inode and return a pointer to it, or NULL * if memory could not be allocated. */ -struct ads_entry *dentry_add_ads(struct dentry *dentry, const char *stream_name) +struct ads_entry *inode_add_ads(struct inode *inode, const char *stream_name) { u16 num_ads; - struct ads_entry *ads_entries; + struct ads_entry **ads_entries; struct ads_entry *new_entry; - DEBUG("Add alternate data stream %s:%s", - dentry->file_name_utf8, stream_name); - - if (dentry->num_ads == 0xffff) { - ERROR("Too many alternate data streams in one dentry!"); + if (inode->num_ads == 0xffff) { + ERROR("Too many alternate data streams in one inode!"); return NULL; } - num_ads = dentry->num_ads + 1; - ads_entries = REALLOC(dentry->ads_entries, - num_ads * sizeof(dentry->ads_entries[0])); + num_ads = inode->num_ads + 1; + ads_entries = REALLOC(inode->ads_entries, + num_ads * sizeof(inode->ads_entries[0])); if (!ads_entries) { ERROR("Failed to allocate memory for new alternate data stream"); return NULL; } - wimlib_assert(ads_entries == dentry->ads_entries || - ads_entries < dentry->ads_entries || - ads_entries > dentry->ads_entries + dentry->num_ads); - if (ads_entries != dentry->ads_entries) { - /* We moved the ADS entries. Adjust the stream lists. */ - for (u16 i = 0; i < dentry->num_ads; i++) { - struct list_head *cur = &ads_entries[i].lte_group_list.list; - struct list_head *prev = cur->prev; - struct list_head *next; - if ((u8*)prev >= (u8*)dentry->ads_entries - && (u8*)prev < (u8*)(dentry->ads_entries + dentry->num_ads)) { - /* Previous entry was located in the same ads_entries - * array! Adjust our own prev pointer. */ - u16 idx = (struct ads_entry*)prev - - (struct ads_entry*)&dentry->ads_entries[0].lte_group_list.list; - cur->prev = &ads_entries[idx].lte_group_list.list; - } else { - /* Previous entry is located in a different ads_entries - * array. Adjust its next pointer. */ - prev->next = cur; - } - next = cur->next; - if ((u8*)next >= (u8*)dentry->ads_entries - && (u8*)next < (u8*)(dentry->ads_entries + dentry->num_ads)) { - /* Next entry was located in the same ads_entries array! - * Adjust our own next pointer. */ - u16 idx = (struct ads_entry*)next - - (struct ads_entry*)&dentry->ads_entries[0].lte_group_list.list; - cur->next = &ads_entries[idx].lte_group_list.list; - } else { - /* Next entry is located in a different ads_entries - * array. Adjust its prev pointer. */ - next->prev = cur; - } - } - } + inode->ads_entries = ads_entries; - new_entry = &ads_entries[num_ads - 1]; - ads_entry_init(new_entry); - if (change_ads_name(new_entry, stream_name) != 0) + new_entry = new_ads_entry(stream_name); + if (new_entry) return NULL; - dentry->ads_entries = ads_entries; - dentry->num_ads = num_ads; + inode->num_ads = num_ads; + ads_entries[num_ads - 1] = new_entry; return new_entry; } -/* Remove an alternate data stream from a dentry. - * - * The corresponding lookup table entry for the stream is NOT changed. - * - * @dentry: The dentry - * @ads_entry: The alternate data stream entry (it MUST be one of the - * ads_entry's in the array dentry->ads_entries). - */ -void dentry_remove_ads(struct dentry *dentry, struct ads_entry *ads_entry) -{ - u16 idx; - u16 following; - - wimlib_assert(dentry->num_ads); - idx = ads_entry - dentry->ads_entries; - wimlib_assert(idx < dentry->num_ads); - following = dentry->num_ads - idx - 1; - - destroy_ads_entry(ads_entry); - memcpy(ads_entry, ads_entry + 1, following * sizeof(struct ads_entry)); - - /* We moved the ADS entries. Adjust the stream lists. */ - for (u16 i = 0; i < following; i++) { - struct list_head *cur = &ads_entry[i].lte_group_list.list; - struct list_head *prev = cur->prev; - struct list_head *next; - if ((u8*)prev >= (u8*)(ads_entry + 1) - && (u8*)prev < (u8*)(ads_entry + following + 1)) { - cur->prev = (struct list_head*)((u8*)prev - sizeof(struct ads_entry)); - } else { - prev->next = cur; - } - next = cur->next; - if ((u8*)next >= (u8*)(ads_entry + 1) - && (u8*)next < (u8*)(ads_entry + following + 1)) { - cur->next = (struct list_head*)((u8*)next - sizeof(struct ads_entry)); - } else { - next->prev = cur; - } - } - - dentry->num_ads--; -} /* * Calls a function on all directory entries in a directory tree. It is called @@ -521,17 +451,18 @@ int print_dentry(struct dentry *dentry, void *lookup_table) { const u8 *hash; struct lookup_table_entry *lte; + const struct inode *inode = dentry->inode; time_t time; char *p; printf("[DENTRY]\n"); printf("Length = %"PRIu64"\n", dentry->length); - printf("Attributes = 0x%x\n", dentry->attributes); + printf("Attributes = 0x%x\n", inode->attributes); for (unsigned i = 0; i < ARRAY_LEN(file_attr_flags); i++) - if (file_attr_flags[i].flag & dentry->attributes) + if (file_attr_flags[i].flag & inode->attributes) printf(" FILE_ATTRIBUTE_%s is set\n", file_attr_flags[i].name); - printf("Security ID = %d\n", dentry->security_id); + printf("Security ID = %d\n", inode->security_id); printf("Subdir offset = %"PRIu64"\n", dentry->subdir_offset); #if 0 printf("Unused1 = 0x%"PRIu64"\n", dentry->unused1); @@ -544,24 +475,24 @@ int print_dentry(struct dentry *dentry, void *lookup_table) #endif /* Translate the timestamps into something readable */ - time = wim_timestamp_to_unix(dentry->creation_time); + time = wim_timestamp_to_unix(inode->creation_time); p = asctime(gmtime(&time)); *(strrchr(p, '\n')) = '\0'; printf("Creation Time = %s UTC\n", p); - time = wim_timestamp_to_unix(dentry->last_access_time); + time = wim_timestamp_to_unix(inode->last_access_time); p = asctime(gmtime(&time)); *(strrchr(p, '\n')) = '\0'; printf("Last Access Time = %s UTC\n", p); - time = wim_timestamp_to_unix(dentry->last_write_time); + time = wim_timestamp_to_unix(inode->last_write_time); p = asctime(gmtime(&time)); *(strrchr(p, '\n')) = '\0'; printf("Last Write Time = %s UTC\n", p); - printf("Reparse Tag = 0x%"PRIx32"\n", dentry->reparse_tag); + printf("Reparse Tag = 0x%"PRIx32"\n", inode->reparse_tag); printf("Hard Link Group = 0x%"PRIx64"\n", dentry->link_group_id); - printf("Number of Alternate Data Streams = %hu\n", dentry->num_ads); + printf("Number of Alternate Data Streams = %hu\n", inode->num_ads); printf("Filename = \""); print_string(dentry->file_name, dentry->file_name_len); puts("\""); @@ -573,11 +504,11 @@ int print_dentry(struct dentry *dentry, void *lookup_table) puts("\""); printf("Short Name Length = %hu\n", dentry->short_name_len); printf("Full Path (UTF-8) = \"%s\"\n", dentry->full_path_utf8); - lte = dentry_stream_lte(dentry, 0, lookup_table); + lte = inode_stream_lte(dentry->inode, 0, lookup_table); if (lte) { print_lookup_table_entry(lte); } else { - hash = dentry_stream_hash(dentry, 0); + hash = inode_stream_hash(inode, 0); if (hash) { printf("Hash = 0x"); print_hash(hash); @@ -585,19 +516,19 @@ int print_dentry(struct dentry *dentry, void *lookup_table) putchar('\n'); } } - for (u16 i = 0; i < dentry->num_ads; i++) { + for (u16 i = 0; i < inode->num_ads; i++) { printf("[Alternate Stream Entry %u]\n", i); - printf("Name = \"%s\"\n", dentry->ads_entries[i].stream_name_utf8); + printf("Name = \"%s\"\n", inode->ads_entries[i]->stream_name_utf8); printf("Name Length (UTF-16) = %u\n", - dentry->ads_entries[i].stream_name_len); - hash = dentry_stream_hash(dentry, i + 1); + inode->ads_entries[i]->stream_name_len); + hash = inode_stream_hash(inode, i + 1); if (hash) { printf("Hash = 0x"); print_hash(hash); putchar('\n'); } - print_lookup_table_entry(dentry_stream_lte(dentry, i + 1, - lookup_table)); + print_lookup_table_entry(inode_stream_lte(inode, i + 1, + lookup_table)); } return 0; } @@ -607,9 +538,21 @@ static void dentry_common_init(struct dentry *dentry) { memset(dentry, 0, sizeof(struct dentry)); dentry->refcnt = 1; - dentry->security_id = -1; - dentry->ads_entries_status = ADS_ENTRIES_DEFAULT; - dentry->lte_group_list.type = STREAM_TYPE_NORMAL; +} + +struct inode *new_inode() +{ + struct inode *inode = CALLOC(1, sizeof(struct inode)); + u64 now = get_wim_timestamp(); + if (!inode) + return NULL; + inode->security_id = -1; + inode->link_count = 1; + inode->creation_time = now; + inode->last_access_time = now; + inode->last_write_time = now; + INIT_LIST_HEAD(&inode->dentry_list); + return inode; } /* @@ -631,12 +574,10 @@ struct dentry *new_dentry(const char *name) if (change_dentry_name(dentry, name) != 0) goto err; - dentry_update_all_timestamps(dentry); dentry->next = dentry; dentry->prev = dentry; dentry->parent = dentry; - INIT_LIST_HEAD(&dentry->link_group_list); - INIT_LIST_HEAD(&dentry->lte_group_list.list); + return dentry; err: FREE(dentry); @@ -644,57 +585,114 @@ err: return NULL; } -void dentry_free_ads_entries(struct dentry *dentry) +struct dentry *new_dentry_with_inode(const char *name) { - for (u16 i = 0; i < dentry->num_ads; i++) - destroy_ads_entry(&dentry->ads_entries[i]); - FREE(dentry->ads_entries); - dentry->ads_entries = NULL; - dentry->num_ads = 0; + struct dentry *dentry; + dentry = new_dentry(name); + if (dentry) { + dentry->inode = new_inode(); + if (dentry->inode) { + list_add(&dentry->inode_dentry_list, + &dentry->inode->dentry_list); + } else { + free_dentry(dentry); + dentry = NULL; + } + } + return dentry; } -static void __destroy_dentry(struct dentry *dentry) +static void free_ads_entry(struct ads_entry *entry) { - FREE(dentry->file_name); - FREE(dentry->file_name_utf8); - FREE(dentry->short_name); - FREE(dentry->full_path_utf8); - if (dentry->extracted_file != dentry->full_path_utf8) - FREE(dentry->extracted_file); + if (entry) { + FREE(entry->stream_name); + FREE(entry->stream_name_utf8); + FREE(entry); + } } -/* Frees a WIM dentry. */ -void free_dentry(struct dentry *dentry) + +#ifdef WITH_FUSE +/* Remove an alternate data stream from a dentry. + * + * The corresponding lookup table entry for the stream is NOT changed. + * + * @dentry: The dentry + * @ads_entry: The alternate data stream entry (it MUST be one of the + * ads_entry's in the array dentry->ads_entries). + */ +void dentry_remove_ads(struct dentry *dentry, struct ads_entry *ads_entry) { - wimlib_assert(dentry); - __destroy_dentry(dentry); - /* Don't destroy the ADS entries if they "belong" to a different dentry - * */ - if (dentry->ads_entries_status != ADS_ENTRIES_USER) - dentry_free_ads_entries(dentry); - FREE(dentry); + u16 idx; + u16 following; + + wimlib_assert(dentry->num_ads); + idx = ads_entry - dentry->ads_entries; + wimlib_assert(idx < dentry->num_ads); + following = dentry->num_ads - idx - 1; + + destroy_ads_entry(ads_entry); + memcpy(ads_entry, ads_entry + 1, following * sizeof(struct ads_entry)); + + /* We moved the ADS entries. Adjust the stream lists. */ + for (u16 i = 0; i < following; i++) { + struct list_head *cur = &ads_entry[i].lte_group_list.list; + struct list_head *prev = cur->prev; + struct list_head *next; + if ((u8*)prev >= (u8*)(ads_entry + 1) + && (u8*)prev < (u8*)(ads_entry + following + 1)) { + cur->prev = (struct list_head*)((u8*)prev - sizeof(struct ads_entry)); + } else { + prev->next = cur; + } + next = cur->next; + if ((u8*)next >= (u8*)(ads_entry + 1) + && (u8*)next < (u8*)(ads_entry + following + 1)) { + cur->next = (struct list_head*)((u8*)next - sizeof(struct ads_entry)); + } else { + next->prev = cur; + } + } + dentry->num_ads--; } +#endif -/* Like free_dentry(), but assigns a new ADS entries owner if this dentry was - * the previous owner, and also deletes the dentry from its link_group_list */ -void put_dentry(struct dentry *dentry) +static void inode_free_ads_entries(struct inode *inode) { - if (dentry->ads_entries_status == ADS_ENTRIES_OWNER) { - struct dentry *new_owner; - list_for_each_entry(new_owner, &dentry->link_group_list, - link_group_list) - { - if (new_owner->ads_entries_status == ADS_ENTRIES_USER) { - new_owner->ads_entries_status = ADS_ENTRIES_OWNER; - break; - } - } - dentry->ads_entries_status = ADS_ENTRIES_USER; + if (inode->ads_entries) { + for (u16 i = 0; i < inode->num_ads; i++) + free_ads_entry(inode->ads_entries[i]); + FREE(inode->ads_entries); } - list_del(&dentry->link_group_list); - free_dentry(dentry); } +void free_inode(struct inode *inode) +{ + wimlib_assert(inode); + inode_free_ads_entries(inode); + FREE(inode); +} + +void put_inode(struct inode *inode) +{ + if (inode) { + wimlib_assert(inode->link_count); + if (--inode->link_count) + free_inode(inode); + } +} + +/* Frees a WIM dentry. */ +void free_dentry(struct dentry *dentry) +{ + wimlib_assert(dentry); + FREE(dentry->file_name); + FREE(dentry->file_name_utf8); + FREE(dentry->short_name); + FREE(dentry->full_path_utf8); + put_inode(dentry->inode); + FREE(dentry); +} /* Partically clones a dentry. * @@ -702,7 +700,6 @@ void put_dentry(struct dentry *dentry) * - memory for file names is not cloned (the pointers are all set to NULL * and the lengths are set to zero) * - next, prev, and children pointers and not touched - * - stream entries are not cloned (pointer left untouched). */ struct dentry *clone_dentry(struct dentry *old) { @@ -727,11 +724,12 @@ static int do_free_dentry(struct dentry *dentry, void *__lookup_table) { struct lookup_table *lookup_table = __lookup_table; struct lookup_table_entry *lte; + struct inode *inode = dentry->inode; unsigned i; if (lookup_table) { - for (i = 0; i <= dentry->num_ads; i++) { - lte = dentry_stream_lte(dentry, i, lookup_table); + for (i = 0; i <= inode->num_ads; i++) { + lte = inode_stream_lte(inode, i, lookup_table); lte_decrement_refcnt(lte, lookup_table); } } @@ -889,8 +887,8 @@ static int calculate_dentry_statistics(struct dentry *dentry, void *arg) else ++*stats->file_count; - for (unsigned i = 0; i <= dentry->num_ads; i++) { - lte = dentry_stream_lte(dentry, i, stats->lookup_table); + for (unsigned i = 0; i <= dentry->inode->num_ads; i++) { + lte = inode_stream_lte(dentry->inode, i, stats->lookup_table); if (lte) { *stats->total_bytes += wim_resource_size(lte); if (++lte->out_refcnt == 1) @@ -926,8 +924,8 @@ void calculate_dir_tree_statistics(struct dentry *root, struct lookup_table *tab * * @p: Pointer to buffer that starts with the first alternate stream entry. * - * @dentry: Dentry to load the alternate data streams into. - * @dentry->num_ads must have been set to the number of + * @inode: Inode to load the alternate data streams into. + * @inode->num_ads must have been set to the number of * alternate data streams that are expected. * * @remaining_size: Number of bytes of data remaining in the buffer pointed @@ -957,19 +955,19 @@ void calculate_dir_tree_statistics(struct dentry *root, struct lookup_table *tab * * In addition, the entries are 8-byte aligned. * - * Return 0 on success or nonzero on failure. On success, dentry->ads_entries - * is set to an array of `struct ads_entry's of length dentry->num_ads. On - * failure, @dentry is not modified. + * Return 0 on success or nonzero on failure. On success, inode->ads_entries + * is set to an array of `struct ads_entry's of length inode->num_ads. On + * failure, @inode is not modified. */ -static int read_ads_entries(const u8 *p, struct dentry *dentry, +static int read_ads_entries(const u8 *p, struct inode *inode, u64 remaining_size) { u16 num_ads; - struct ads_entry *ads_entries; + struct ads_entry **ads_entries; int ret; - num_ads = dentry->num_ads; - ads_entries = CALLOC(num_ads, sizeof(struct ads_entry)); + num_ads = inode->num_ads; + ads_entries = CALLOC(num_ads, sizeof(inode->ads_entries[0])); if (!ads_entries) { ERROR("Could not allocate memory for %"PRIu16" " "alternate data stream entries", num_ads); @@ -977,13 +975,21 @@ static int read_ads_entries(const u8 *p, struct dentry *dentry, } for (u16 i = 0; i < num_ads; i++) { - struct ads_entry *cur_entry = &ads_entries[i]; + struct ads_entry *cur_entry; u64 length; u64 length_no_padding; u64 total_length; size_t utf8_len; const u8 *p_save = p; + cur_entry = new_ads_entry(NULL); + if (!cur_entry) { + ret = WIMLIB_ERR_NOMEM; + goto out_free_ads_entries; + } + + ads_entries[i] = cur_entry; + /* Read the base stream entry, excluding the stream name. */ if (remaining_size < WIM_ADS_ENTRY_DISK_SIZE) { ERROR("Stream entries go past end of metadata resource"); @@ -1067,13 +1073,11 @@ static int read_ads_entries(const u8 *p, struct dentry *dentry, else remaining_size -= total_length; } - dentry->ads_entries = ads_entries; + inode->ads_entries = ads_entries; return 0; out_free_ads_entries: - for (u16 i = 0; i < num_ads; i++) { - FREE(ads_entries[i].stream_name); - FREE(ads_entries[i].stream_name_utf8); - } + for (u16 i = 0; i < num_ads; i++) + free_ads_entry(ads_entries[i]); FREE(ads_entries); return ret; } @@ -1105,6 +1109,7 @@ int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, u16 file_name_len; size_t file_name_utf8_len = 0; int ret; + struct inode *inode = NULL; dentry_common_init(dentry); @@ -1149,8 +1154,12 @@ int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, return WIMLIB_ERR_INVALID_DENTRY; } - p = get_u32(p, &dentry->attributes); - p = get_u32(p, (u32*)&dentry->security_id); + inode = new_inode(); + if (!inode) + return WIMLIB_ERR_NOMEM; + + p = get_u32(p, &inode->attributes); + p = get_u32(p, (u32*)&inode->security_id); p = get_u64(p, &dentry->subdir_offset); /* 2 unused fields */ @@ -1158,11 +1167,11 @@ int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, /*p = get_u64(p, &dentry->unused1);*/ /*p = get_u64(p, &dentry->unused2);*/ - p = get_u64(p, &dentry->creation_time); - p = get_u64(p, &dentry->last_access_time); - p = get_u64(p, &dentry->last_write_time); + p = get_u64(p, &inode->creation_time); + p = get_u64(p, &inode->last_access_time); + p = get_u64(p, &inode->last_write_time); - p = get_bytes(p, SHA1_HASH_SIZE, dentry->hash); + p = get_bytes(p, SHA1_HASH_SIZE, inode->hash); /* * I don't know what's going on here. It seems like M$ screwed up the @@ -1170,20 +1179,20 @@ int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, * document it. The WIM_HDR_FLAG_RP_FIX flag in the WIM header might * have something to do with this, but it's not documented. */ - if (dentry->attributes & FILE_ATTRIBUTE_REPARSE_POINT) { + if (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) { /* ??? */ p += 4; - p = get_u32(p, &dentry->reparse_tag); + p = get_u32(p, &inode->reparse_tag); p += 4; } else { - p = get_u32(p, &dentry->reparse_tag); + p = get_u32(p, &inode->reparse_tag); p = get_u64(p, &dentry->link_group_id); } /* By the way, the reparse_reserved field does not actually exist (at * least when the file is not a reparse point) */ - p = get_u16(p, &dentry->num_ads); + p = get_u16(p, &inode->num_ads); p = get_u16(p, &short_name_len); p = get_u16(p, &file_name_len); @@ -1292,7 +1301,7 @@ int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, * aligned boundary, and the alternate data stream entries are NOT * included in the dentry->length field for some reason. */ - if (dentry->num_ads != 0) { + if (inode->num_ads != 0) { if (calculated_size > metadata_resource_len - offset) { ERROR("Not enough space in metadata resource for " "alternate stream entries"); @@ -1300,7 +1309,7 @@ int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, goto out_free_short_name; } ret = read_ads_entries(&metadata_resource[offset + calculated_size], - dentry, + inode, metadata_resource_len - offset - calculated_size); if (ret != 0) goto out_free_short_name; @@ -1321,6 +1330,8 @@ out_free_file_name_utf8: FREE(file_name_utf8); out_free_file_name: FREE(file_name); +out_free_inode: + free_inode(inode); return ret; } @@ -1330,18 +1341,19 @@ int verify_dentry(struct dentry *dentry, void *wim) const WIMStruct *w = wim; const struct lookup_table *table = w->lookup_table; const struct wim_security_data *sd = wim_const_security_data(w); + const struct inode *inode = dentry->inode; int ret = WIMLIB_ERR_INVALID_DENTRY; /* Check the security ID */ - if (dentry->security_id < -1) { + if (inode->security_id < -1) { ERROR("Dentry `%s' has an invalid security ID (%d)", - dentry->full_path_utf8, dentry->security_id); + dentry->full_path_utf8, inode->security_id); goto out; } - if (dentry->security_id >= sd->num_entries) { + if (inode->security_id >= sd->num_entries) { ERROR("Dentry `%s' has an invalid security ID (%d) " "(there are only %u entries in the security table)", - dentry->full_path_utf8, dentry->security_id, + dentry->full_path_utf8, inode->security_id, sd->num_entries); goto out; } @@ -1350,10 +1362,10 @@ int verify_dentry(struct dentry *dentry, void *wim) * if the SHA1 message digest is all 0's, which indicates there is * intentionally no resource there. */ if (w->hdr.total_parts == 1) { - for (unsigned i = 0; i <= dentry->num_ads; i++) { + for (unsigned i = 0; i <= inode->num_ads; i++) { struct lookup_table_entry *lte; const u8 *hash; - hash = dentry_stream_hash_unresolved(dentry, i); + hash = inode_stream_hash_unresolved(inode, i); lte = __lookup_resource(table, hash); if (!lte && !is_zero_hash(hash)) { ERROR("Could not find lookup table entry for stream " @@ -1365,10 +1377,10 @@ int verify_dentry(struct dentry *dentry, void *wim) /* Make sure there is only one un-named stream. */ unsigned num_unnamed_streams = 0; - for (unsigned i = 0; i <= dentry->num_ads; i++) { + for (unsigned i = 0; i <= inode->num_ads; i++) { const u8 *hash; - hash = dentry_stream_hash_unresolved(dentry, i); - if (!dentry_stream_name_len(dentry, i) && !is_zero_hash(hash)) + hash = inode_stream_hash_unresolved(inode, i); + if (!inode_stream_name_len(inode, i) && !is_zero_hash(hash)) num_unnamed_streams++; } if (num_unnamed_streams > 1) { @@ -1395,8 +1407,8 @@ int verify_dentry(struct dentry *dentry, void *wim) #if 0 /* Check timestamps */ - if (dentry->last_access_time < dentry->creation_time || - dentry->last_write_time < dentry->creation_time) { + if (inode->last_access_time < inode->creation_time || + inode->last_write_time < inode->creation_time) { WARNING("Dentry `%s' was created after it was last accessed or " "written to", dentry->full_path_utf8); } @@ -1419,6 +1431,7 @@ static u8 *write_dentry(const struct dentry *dentry, u8 *p) { u8 *orig_p = p; const u8 *hash; + const struct inode *inode = dentry->inode; /* We calculate the correct length of the dentry ourselves because the * dentry->length field may been set to an unexpected value from when we @@ -1427,30 +1440,30 @@ static u8 *write_dentry(const struct dentry *dentry, u8 *p) u64 length = dentry_correct_length(dentry); p = put_u64(p, length); - p = put_u32(p, dentry->attributes); - p = put_u32(p, dentry->security_id); + p = put_u32(p, inode->attributes); + p = put_u32(p, inode->security_id); p = put_u64(p, dentry->subdir_offset); p = put_u64(p, 0); /* unused1 */ p = put_u64(p, 0); /* unused2 */ - p = put_u64(p, dentry->creation_time); - p = put_u64(p, dentry->last_access_time); - p = put_u64(p, dentry->last_write_time); - hash = dentry_stream_hash(dentry, 0); + p = put_u64(p, inode->creation_time); + p = put_u64(p, inode->last_access_time); + p = put_u64(p, inode->last_write_time); + hash = inode_stream_hash(inode, 0); p = put_bytes(p, SHA1_HASH_SIZE, hash); - if (dentry->attributes & FILE_ATTRIBUTE_REPARSE_POINT) { + if (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) { p = put_zeroes(p, 4); - p = put_u32(p, dentry->reparse_tag); + p = put_u32(p, inode->reparse_tag); p = put_zeroes(p, 4); } else { u64 link_group_id; p = put_u32(p, 0); - if (dentry->link_group_list.next == &dentry->link_group_list) + if (dentry->inode->link_count == 1) link_group_id = 0; else - link_group_id = dentry->link_group_id; + link_group_id = dentry->inode->ino; p = put_u64(p, link_group_id); } - p = put_u16(p, dentry->num_ads); + p = put_u16(p, inode->num_ads); p = put_u16(p, dentry->short_name_len); p = put_u16(p, dentry->file_name_len); if (dentry->file_name_len) { @@ -1470,15 +1483,15 @@ static u8 *write_dentry(const struct dentry *dentry, u8 *p) /* Write the alternate data streams, if there are any. Please see * read_ads_entries() for comments about the format of the on-disk * alternate data stream entries. */ - for (u16 i = 0; i < dentry->num_ads; i++) { - p = put_u64(p, ads_entry_total_length(&dentry->ads_entries[i])); + for (u16 i = 0; i < inode->num_ads; i++) { + p = put_u64(p, ads_entry_total_length(inode->ads_entries[i])); p = put_u64(p, 0); /* Unused */ - hash = dentry_stream_hash(dentry, i + 1); + hash = inode_stream_hash(inode, i + 1); p = put_bytes(p, SHA1_HASH_SIZE, hash); - p = put_u16(p, dentry->ads_entries[i].stream_name_len); - if (dentry->ads_entries[i].stream_name_len) { - p = put_bytes(p, dentry->ads_entries[i].stream_name_len, - (u8*)dentry->ads_entries[i].stream_name); + p = put_u16(p, inode->ads_entries[i]->stream_name_len); + if (inode->ads_entries[i]->stream_name_len) { + p = put_bytes(p, inode->ads_entries[i]->stream_name_len, + (u8*)inode->ads_entries[i]->stream_name); p = put_u16(p, 0); } p = put_zeroes(p, (8 - (p - orig_p) % 8) % 8); diff --git a/src/dentry.h b/src/dentry.h index 8283b596..5881c897 100644 --- a/src/dentry.h +++ b/src/dentry.h @@ -82,6 +82,9 @@ struct ads_entry { /* Doubly linked list of streams that share the same lookup table entry */ struct stream_list_head lte_group_list; + + /* Containing inode */ + struct inode *inode; }; /* Returns the total length of a WIM alternate data stream entry on-disk, @@ -95,12 +98,6 @@ static inline u64 ads_entry_total_length(const struct ads_entry *entry) return (len + 7) & ~7; } -static inline void destroy_ads_entry(struct ads_entry *entry) -{ - FREE(entry->stream_name); - FREE(entry->stream_name_utf8); -} - static inline bool ads_entry_has_name(const struct ads_entry *entry, const char *name, size_t name_len) { @@ -118,6 +115,60 @@ static inline bool ads_entries_have_same_name(const struct ads_entry *entry_1, entry_1->stream_name_len) == 0; } +struct inode { + /* Timestamps for the inode. The timestamps are the number of + * 100-nanosecond intervals that have elapsed since 12:00 A.M., January + * 1st, 1601, UTC. This is the same format used in NTFS inodes. */ + u64 creation_time; + u64 last_access_time; + u64 last_write_time; + + /* The file attributes associated with this inode. This is a bitwise OR + * of the FILE_ATTRIBUTE_* flags. */ + u32 attributes; + + /* The index of the security descriptor in the WIM image's table of + * security descriptors that contains this file's security information. + * If -1, no security information exists for this file. */ + int32_t security_id; + + /* %true iff the inode's lookup table entries has been resolved (i.e. + * the @lte field is valid, but the @hash field is not valid) + * + * (This is not an on-disk field.) */ + bool resolved; + + u16 num_ads; + + /* A hash of the file's contents, or a pointer to the lookup table entry + * for this dentry if the lookup table entries have been resolved. + * + * More specifically, this is for the un-named default file stream, as + * opposed to the alternate (named) file streams, which may have their + * own lookup table entries. */ + union { + u8 hash[SHA1_HASH_SIZE]; + struct lookup_table_entry *lte; + }; + + /* Identity of a reparse point. See + * http://msdn.microsoft.com/en-us/library/windows/desktop/aa365503(v=vs.85).aspx + * for what a reparse point is. */ + u32 reparse_tag; + + u32 link_count; + + struct ads_entry **ads_entries; + + u64 ino; + + struct list_head dentry_list; + union { + struct stream_list_head lte_group_list; + struct hlist_node hlist; + }; + char *extracted_file; +}; /* * In-memory structure for a WIM directory entry (dentry). There is a directory @@ -153,6 +204,8 @@ struct dentry { /* Pointer to a child of this directory entry. */ struct dentry *children; + struct inode *inode; + /* * Size of directory entry on disk, in bytes. Typical size is around * 104 to 120 bytes. @@ -173,14 +226,6 @@ struct dentry { */ u64 length; - /* The file attributes associated with this file. This is a bitwise OR - * of the FILE_ATTRIBUTE_* flags. */ - u32 attributes; - - /* The index of the security descriptor in the WIM image's table of - * security descriptors that contains this file's security information. - * If -1, no security information exists for this file. */ - int32_t security_id; /* The offset, from the start of the uncompressed WIM metadata resource * for this image, of this dentry's child dentries. 0 if the directory @@ -188,34 +233,6 @@ struct dentry { * points. */ u64 subdir_offset; - /* Timestamps for the dentry. The timestamps are the number of - * 100-nanosecond intervals that have elapsed since 12:00 A.M., January - * 1st, 1601, UTC. This is the same format used in NTFS inodes. */ - u64 creation_time; - u64 last_access_time; - u64 last_write_time; - - /* %true iff the dentry's lookup table entry has been resolved (i.e. the - * @lte field is valid, but the @hash field is not valid) - * - * (This is not an on-disk field.) */ - bool resolved; - - /* A hash of the file's contents, or a pointer to the lookup table entry - * for this dentry if the lookup table entries have been resolved. - * - * More specifically, this is for the un-named default file stream, as - * opposed to the alternate (named) file streams, which may have their - * own lookup table entries. */ - union { - u8 hash[SHA1_HASH_SIZE]; - struct lookup_table_entry *lte; - }; - - /* Identity of a reparse point. See - * http://msdn.microsoft.com/en-us/library/windows/desktop/aa365503(v=vs.85).aspx - * for what a reparse point is. */ - u32 reparse_tag; /* Although M$'s documentation does not tell you this, it seems that the * reparse_reserved field does not actually exist. So the hard_link @@ -232,9 +249,6 @@ struct dentry { * WIMs that wimlib writes maintain this restriction. */ u64 link_group_id; - /* Number of alternate data streams associated with this file. */ - u16 num_ads; - /* Length of short filename, in bytes, not including the terminating * zero wide-character. */ u16 short_name_len; @@ -260,9 +274,6 @@ struct dentry { char *full_path_utf8; u32 full_path_utf8_len; - /* Alternate stream entries for this dentry (malloc()ed buffer). */ - struct ads_entry *ads_entries; - union { /* Number of references to the dentry tree itself, as in multiple * WIMStructs */ @@ -273,33 +284,9 @@ struct dentry { u32 num_times_opened; }; - enum { - /* This dentry is the owner of its ads_entries, although it may - * be in a hard link set */ - ADS_ENTRIES_DEFAULT = 0, - - /* This dentry is the owner of the ads_entries in the hard link - * set */ - ADS_ENTRIES_OWNER, - - /* This dentry shares its ads_entries with a dentry in the hard - * link set that has ADS_ENTRIES_OWNER set. */ - ADS_ENTRIES_USER - } ads_entries_status; - - /* List of dentries in the hard link set */ - struct list_head link_group_list; - - union { - /* List of dentries sharing the same lookup table entry */ - struct stream_list_head lte_group_list; - struct list_head tmp_list; - }; - - /* Path to extracted file on disk (used during extraction only) - * (malloc()ed buffer, or set the same as full_path_utf8) */ - char *extracted_file; + struct list_head inode_dentry_list; + struct list_head tmp_list; }; @@ -347,9 +334,12 @@ extern struct dentry *get_dentry_child_with_name(const struct dentry *dentry, extern void dentry_update_all_timestamps(struct dentry *dentry); extern void init_dentry(struct dentry *dentry, const char *name); extern struct dentry *new_dentry(const char *name); +extern struct dentry *new_dentry_with_inode(const char *name); extern void dentry_free_ads_entries(struct dentry *dentry); extern void free_dentry(struct dentry *dentry); +extern void free_inode(struct inode *inode); +extern void put_inode(struct inode *inode); extern void put_dentry(struct dentry *dentry); extern struct dentry *clone_dentry(struct dentry *old); extern void free_dentry_tree(struct dentry *root, @@ -378,13 +368,10 @@ extern u8 *write_dentry_tree(const struct dentry *tree, u8 *p); /* Return the number of dentries in the hard link group */ static inline size_t dentry_link_group_size(const struct dentry *dentry) { - const struct list_head *cur = &dentry->link_group_list; + const struct list_head *cur; size_t size = 0; - wimlib_assert(cur != NULL); - do { + list_for_each(cur, &dentry->inode_dentry_list) size++; - cur = cur->next; - } while (cur != &dentry->link_group_list); return size; } @@ -403,19 +390,29 @@ static inline bool dentry_is_only_child(const struct dentry *dentry) return dentry->next == dentry; } +static inline bool inode_is_directory(const struct inode *inode) +{ + return (inode->attributes & FILE_ATTRIBUTE_DIRECTORY) + && !(inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT); +} + static inline bool dentry_is_directory(const struct dentry *dentry) { - return (dentry->attributes & FILE_ATTRIBUTE_DIRECTORY) - && !(dentry->attributes & FILE_ATTRIBUTE_REPARSE_POINT); + return inode_is_directory(dentry->inode); } /* For our purposes, we consider "real" symlinks and "junction points" to both * be symlinks. */ +static inline bool inode_is_symlink(const struct inode *inode) +{ + return (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) + && ((inode->reparse_tag == WIM_IO_REPARSE_TAG_SYMLINK) || + inode->reparse_tag == WIM_IO_REPARSE_TAG_MOUNT_POINT); +} + static inline bool dentry_is_symlink(const struct dentry *dentry) { - return (dentry->attributes & FILE_ATTRIBUTE_REPARSE_POINT) - && ((dentry->reparse_tag == WIM_IO_REPARSE_TAG_SYMLINK) || - dentry->reparse_tag == WIM_IO_REPARSE_TAG_MOUNT_POINT); + return inode_is_symlink(dentry->inode); } static inline bool dentry_is_regular_file(const struct dentry *dentry) diff --git a/src/extract.c b/src/extract.c index e42aba4d..26164028 100644 --- a/src/extract.c +++ b/src/extract.c @@ -124,11 +124,9 @@ static int extract_regular_file_unlinked(WIMStruct *w, int out_fd; int ret; - const struct list_head *head = &dentry->link_group_list; + struct inode *inode = dentry->inode; - if (head->next != head && - !(extract_flags & WIMLIB_EXTRACT_FLAG_MULTI_IMAGE)) - { + if (!(extract_flags & WIMLIB_EXTRACT_FLAG_MULTI_IMAGE)) { /* This dentry is one of a hard link set of at least 2 dentries. * If one of the other dentries has already been extracted, make * a hard link to the file corresponding to this @@ -136,25 +134,25 @@ static int extract_regular_file_unlinked(WIMStruct *w, * file, and set the dentry->extracted_file field so that other * dentries in the hard link group can link to it. */ struct dentry *other; - list_for_each_entry(other, head, link_group_list) { - if (other->extracted_file) { - DEBUG("Extracting hard link `%s' => `%s'", - output_path, other->extracted_file); - if (link(other->extracted_file, output_path) != 0) { - ERROR_WITH_ERRNO("Failed to hard link " - "`%s' to `%s'", - output_path, - other->extracted_file); - return WIMLIB_ERR_LINK; - } - return 0; + if (inode->extracted_file) { + DEBUG("Extracting hard link `%s' => `%s'", + output_path, inode->extracted_file); + if (link(inode->extracted_file, output_path) != 0) { + ERROR_WITH_ERRNO("Failed to hard link " + "`%s' to `%s'", + output_path, + inode->extracted_file); + return WIMLIB_ERR_LINK; } + return 0; } - FREE(dentry->extracted_file); - dentry->extracted_file = STRDUP(output_path); - if (!dentry->extracted_file) { - ERROR("Failed to allocate memory for filename"); - return WIMLIB_ERR_NOMEM; + if (inode->link_count > 1) { + FREE(inode->extracted_file); + inode->extracted_file = STRDUP(output_path); + if (!inode->extracted_file) { + ERROR("Failed to allocate memory for filename"); + return WIMLIB_ERR_NOMEM; + } } } @@ -198,8 +196,9 @@ static int extract_regular_file(WIMStruct *w, int extract_flags) { struct lookup_table_entry *lte; + const struct inode *inode = dentry->inode; - lte = dentry_unnamed_lte(dentry, w->lookup_table); + lte = inode_unnamed_lte(inode, w->lookup_table); if ((extract_flags & (WIMLIB_EXTRACT_FLAG_SYMLINK | WIMLIB_EXTRACT_FLAG_HARDLINK)) && lte) { @@ -221,7 +220,7 @@ static int extract_symlink(const struct dentry *dentry, const char *output_path, const WIMStruct *w) { char target[4096]; - ssize_t ret = dentry_readlink(dentry, target, sizeof(target), w); + ssize_t ret = inode_readlink(dentry->inode, target, sizeof(target), w); if (ret <= 0) { ERROR("Could not read the symbolic link from dentry `%s'", dentry->full_path_utf8); @@ -321,8 +320,8 @@ static int apply_dentry_timestamps(struct dentry *dentry, void *arg) output_path[len + dentry->full_path_utf8_len] = '\0'; struct timeval tv[2]; - wim_timestamp_to_timeval(dentry->last_access_time, &tv[0]); - wim_timestamp_to_timeval(dentry->last_write_time, &tv[1]); + wim_timestamp_to_timeval(dentry->inode->last_access_time, &tv[0]); + wim_timestamp_to_timeval(dentry->inode->last_write_time, &tv[1]); if (lutimes(output_path, tv) != 0) { WARNING("Failed to set timestamp on file `%s': %s", output_path, strerror(errno)); diff --git a/src/hardlink.c b/src/hardlink.c index 903d0ccd..d2876e5e 100644 --- a/src/hardlink.c +++ b/src/hardlink.c @@ -2,8 +2,8 @@ * hardlink.c * * Code to deal with hard links in WIMs. Essentially, the WIM dentries are put - * into a hash table indexed by the hard link group ID field, then for each hard - * link group, a linked list is made to connect the dentries. + * into a hash table indexed by the inode ID field, then for each hard + * inode, a linked list is made to connect the dentries. */ /* @@ -35,66 +35,51 @@ * dentry | | * / \ ----------- ----------- * | dentry<---| struct | | struct |---> dentry - * \ / |link_group| |link_group| + * \ / |inode| |inode| * dentry ------------ ------------ * ^ ^ * | | * | | dentry * ----------- ----------- / \ * dentry<---| struct | | struct |---> dentry dentry - * / |link_group| |link_group| \ / + * / |inode| |inode| \ / * dentry ------------ ------------ dentry * ^ ^ * | | * ----------------- - * link_group_table->array | idx 0 | idx 1 | + * inode_table->array | idx 0 | idx 1 | * ----------------- */ -/* Hard link group; it's identified by its hard link group ID and points to a - * circularly linked list of dentries. */ -struct link_group { - u64 link_group_id; - - /* Pointer to use to make a singly-linked list of link groups. */ - struct link_group *next; - - /* This is a pointer to the circle and not part of the circle itself. - * This makes it easy to iterate through other dentries hard-linked to a - * given dentry without having to find the "head" of the list first. */ - struct list_head *dentry_list; -}; - -/* Hash table to find hard link groups, identified by their hard link group ID. +/* Hash table to find inodes, identified by their inode ID. * */ -struct link_group_table { +struct inode_table { /* Fields for the hash table */ - struct link_group **array; + struct hlist_head *array; u64 num_entries; u64 capacity; /* - * Linked list of "extra" groups. These may be: + * Linked list of "extra" inodes. These may be: * - * - Hard link groups of size 1, which are all allowed to have 0 for - * their hard link group ID, meaning we cannot insert them into the - * hash table before calling assign_link_group_ids(). + * - 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 hard link group - * due to inconsistencies in the dentries. These groups will share a - * hard link group ID with some other group until - * assign_link_group_ids() is called. + * - Groups we create ourselves by splitting a nominal inode due to + * inconsistencies in the dentries. These inodes will share a inode + * ID with some other inode until assign_inode_numbers() is called. */ - struct link_group *extra_groups; + struct hlist_head extra_inodes; }; -/* Returns pointer to a new link group table having the specified capacity */ -struct link_group_table *new_link_group_table(size_t capacity) +/* Returns pointer to a new inode table having the specified capacity */ +struct inode_table *new_inode_table(size_t capacity) { - struct link_group_table *table; - struct link_group **array; + struct inode_table *table; + struct hlist_head *array; - table = MALLOC(sizeof(struct link_group_table)); + table = MALLOC(sizeof(struct inode_table)); if (!table) goto err; array = CALLOC(capacity, sizeof(array[0])); @@ -105,74 +90,61 @@ struct link_group_table *new_link_group_table(size_t capacity) table->num_entries = 0; table->capacity = capacity; table->array = array; - table->extra_groups = NULL; + INIT_HLIST_HEAD(&table->extra_inodes); return table; err: - ERROR("Failed to allocate memory for link group table with capacity %zu", + ERROR("Failed to allocate memory for inode table with capacity %zu", capacity); return NULL; } /* - * Insert a dentry into the hard link group table based on its hard link group + * Insert a dentry into the inode table based on its inode * ID. * - * If there is already a dentry in the table having the same hard link group ID, - * and the hard link group ID is not 0, the dentry is added to the circular - * linked list for that hard link group. + * If there is already a dentry in the table having the same inode ID, + * and the inode ID is not 0, the dentry is added to the circular + * linked list for that inode. * - * If the hard link group ID is 0, this indicates a dentry that's in a hard link - * group by itself (has a link count of 1). We can't insert it into the hash - * table itself because we don't know what hard link group IDs are available to + * If the inode ID is 0, this indicates a dentry that's in a hard link + * inode by itself (has a link count of 1). We can't insert it into the hash + * table itself because we don't know what inode numbers are available to * give it (this could be kept track of but would be more difficult). Instead - * we keep a linked list of the single dentries, and assign them hard link group - * IDs later. + * we keep a linked list of the single dentries, and assign them inode + * numbers later. */ -int link_group_table_insert(struct dentry *dentry, void *__table) +int inode_table_insert(struct dentry *dentry, void *__table) { - struct link_group_table *table = __table; + struct inode_table *table = __table; size_t pos; - struct link_group *group; + struct inode *inode; + struct inode *d_inode = dentry->inode; - if (dentry->link_group_id == 0) { - /* Single group--- Add to the list of extra groups (we can't put + if (d_inode->ino == 0) { + + /* Single inode--- Add to the list of extra inodes (we can't put * it in the table itself because all the singles have a link - * group ID of 0) */ - group = MALLOC(sizeof(struct link_group)); - if (!group) - return WIMLIB_ERR_NOMEM; - group->link_group_id = 0; - group->next = table->extra_groups; - table->extra_groups = group; - INIT_LIST_HEAD(&dentry->link_group_list); - group->dentry_list = &dentry->link_group_list; + * inode ID of 0) */ + list_add(&dentry->inode_dentry_list, &d_inode->dentry_list); + hlist_add_head(&d_inode->hlist, &table->extra_inodes); } else { - /* Hard link group that may contain multiple dentries (the code - * will work even if the group actually contains only 1 dentry + /* Hard inode that may contain multiple dentries (the code + * will work even if the inode actually contains only 1 dentry * though) */ - - /* Try adding to existing hard link group */ - pos = dentry->link_group_id % table->capacity; - group = table->array[pos]; - while (group) { - if (group->link_group_id == dentry->link_group_id) { - list_add(&dentry->link_group_list, - group->dentry_list); - return 0; + struct hlist_node *cur; + + /* Try adding to existing inode */ + pos = d_inode->ino % table->capacity; + hlist_for_each_entry(inode, cur, &table->array[pos], hlist) { + if (inode->ino == d_inode->ino) { + list_add(&dentry->inode_dentry_list, + &inode->dentry_list); } - group = group->next; } - /* Add new hard link group to the table */ - - group = MALLOC(sizeof(struct link_group)); - if (!group) - return WIMLIB_ERR_NOMEM; - group->link_group_id = dentry->link_group_id; - group->next = table->array[pos]; - INIT_LIST_HEAD(&dentry->link_group_list); - group->dentry_list = &dentry->link_group_list; - table->array[pos] = group; + /* Add new inode to the table */ + list_add(&dentry->inode_dentry_list, &d_inode->dentry_list); + hlist_add_head(&d_inode->hlist, &table->array[pos]); /* XXX Make the table grow when too many entries have been * inserted. */ @@ -181,111 +153,58 @@ int link_group_table_insert(struct dentry *dentry, void *__table) return 0; } -static void free_link_group_list(struct link_group *group) -{ - struct link_group *next_group; - while (group) { - next_group = group->next; - FREE(group); - group = next_group; - } -} - -/* Frees a link group table. */ -void free_link_group_table(struct link_group_table *table) +/* Frees a inode table. */ +void free_inode_table(struct inode_table *table) { if (table) { - if (table->array) - for (size_t i = 0; i < table->capacity; i++) - free_link_group_list(table->array[i]); - free_link_group_list(table->extra_groups); + FREE(table->array); FREE(table); } } static u64 -assign_link_group_ids_to_list(struct link_group *group, u64 id, - struct link_group **extra_groups) +assign_inos_to_list(struct hlist_head *head, u64 cur_ino) { + struct inode *inode; + struct hlist_node *cur; struct dentry *dentry; - struct list_head *cur_head; - struct link_group *prev_group = NULL; - struct link_group *cur_group = group; - while (cur_group) { - cur_head = cur_group->dentry_list; - do { - dentry = container_of(cur_head, - struct dentry, - link_group_list); - dentry->link_group_id = id; - cur_head = cur_head->next; - } while (cur_head != cur_group->dentry_list); - cur_group->link_group_id = id; - id++; - prev_group = cur_group; - cur_group = cur_group->next; + hlist_for_each_entry(inode, cur, head, hlist) { } - if (group && extra_groups) { - prev_group->next = *extra_groups; - *extra_groups = group; - } - return id; + return cur_ino; } -/* Insert the link groups in the `extra_groups' list into the hash table */ -static void insert_extra_groups(struct link_group_table *table) +/* Assign the inode numbers to dentries in a inode table, and return the + * next available inode ID. */ +u64 assign_inode_numbers(struct hlist_head *inode_list) { - struct link_group *group, *next_group; - size_t pos; - - group = table->extra_groups; - while (group) { - next_group = group->next; - pos = group->link_group_id % table->capacity; - group->next = table->array[pos]; - table->array[pos] = group; - group = next_group; + struct inode *inode; + struct hlist_node *cur; + u64 cur_ino = 1; + struct dentry *dentry; + hlist_for_each_entry(inode, cur, inode_list, hlist) { + list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) + dentry->link_group_id = cur_ino; + inode->ino = cur_ino; + cur_ino++; } - table->extra_groups = NULL; + return cur_ino; } -/* Assign the link group IDs to dentries in a link group table, and return the - * next available link group ID. */ -u64 assign_link_group_ids(struct link_group_table *table) -{ - DEBUG("Assigning link groups"); - struct link_group *extra_groups = table->extra_groups; - - /* Assign consecutive link group IDs to each link group in the hash - * table */ - u64 id = 1; - for (size_t i = 0; i < table->capacity; i++) { - id = assign_link_group_ids_to_list(table->array[i], id, - &table->extra_groups); - table->array[i] = NULL; - } - /* Assign link group IDs to the "extra" link groups and insert them into - * the hash table */ - id = assign_link_group_ids_to_list(extra_groups, id, NULL); - insert_extra_groups(table); - return id; +static void +print_inode_dentries(const struct inode *inode) +{ + struct dentry *dentry; + list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) + printf("`%s'\n", dentry->full_path_utf8); } - - -static void inconsistent_link_group(const struct dentry *first_dentry) +static void inconsistent_inode(const struct inode *inode) { - const struct dentry *dentry = first_dentry; - ERROR("An inconsistent hard link group that we cannot correct has been " "detected"); ERROR("The dentries are located at the following paths:"); - do { - ERROR("`%s'", dentry->full_path_utf8); - } while ((dentry = container_of(dentry->link_group_list.next, - const struct dentry, - link_group_list)) != first_dentry); + print_inode_dentries(inode); } static bool ref_dentries_consistent(const struct dentry * restrict ref_dentry_1, @@ -293,19 +212,19 @@ static bool ref_dentries_consistent(const struct dentry * restrict ref_dentry_1, { wimlib_assert(ref_dentry_1 != ref_dentry_2); - if (ref_dentry_1->num_ads != ref_dentry_2->num_ads) + if (ref_dentry_1->inode->num_ads != ref_dentry_2->inode->num_ads) return false; - if (ref_dentry_1->security_id != ref_dentry_2->security_id - || ref_dentry_1->attributes != ref_dentry_2->attributes) + if (ref_dentry_1->inode->security_id != ref_dentry_2->inode->security_id + || ref_dentry_1->inode->attributes != ref_dentry_2->inode->attributes) return false; - for (unsigned i = 0; i <= ref_dentry_1->num_ads; i++) { + for (unsigned i = 0; i <= ref_dentry_1->inode->num_ads; i++) { const u8 *ref_1_hash, *ref_2_hash; - ref_1_hash = dentry_stream_hash(ref_dentry_1, i); - ref_2_hash = dentry_stream_hash(ref_dentry_2, i); + ref_1_hash = inode_stream_hash(ref_dentry_1->inode, i); + ref_2_hash = inode_stream_hash(ref_dentry_2->inode, i); if (!hashes_equal(ref_1_hash, ref_2_hash)) return false; - if (i && !ads_entries_have_same_name(&ref_dentry_1->ads_entries[i - 1], - &ref_dentry_2->ads_entries[i - 1])) + if (i && !ads_entries_have_same_name(ref_dentry_1->inode->ads_entries[i - 1], + ref_dentry_2->inode->ads_entries[i - 1])) return false; } @@ -317,19 +236,20 @@ static bool dentries_consistent(const struct dentry * restrict ref_dentry, { wimlib_assert(ref_dentry != dentry); - if (ref_dentry->num_ads != dentry->num_ads && dentry->num_ads != 0) + if (ref_dentry->inode->num_ads != dentry->inode->num_ads && + dentry->inode->num_ads != 0) return false; - if (ref_dentry->security_id != dentry->security_id - || ref_dentry->attributes != dentry->attributes) + if (ref_dentry->inode->security_id != dentry->inode->security_id + || ref_dentry->inode->attributes != dentry->inode->attributes) return false; - for (unsigned i = 0; i <= min(ref_dentry->num_ads, dentry->num_ads); i++) { + for (unsigned i = 0; i <= min(ref_dentry->inode->num_ads, dentry->inode->num_ads); i++) { const u8 *ref_hash, *hash; - ref_hash = dentry_stream_hash(ref_dentry, i); - hash = dentry_stream_hash(dentry, i); + ref_hash = inode_stream_hash(ref_dentry->inode, i); + hash = inode_stream_hash(dentry->inode, i); if (!hashes_equal(ref_hash, hash) && !is_zero_hash(hash)) return false; - if (i && !ads_entries_have_same_name(&ref_dentry->ads_entries[i - 1], - &dentry->ads_entries[i - 1])) + if (i && !ads_entries_have_same_name(ref_dentry->inode->ads_entries[i - 1], + dentry->inode->ads_entries[i - 1])) return false; } return true; @@ -342,15 +262,30 @@ print_dentry_list(const struct dentry *first_dentry) const struct dentry *dentry = first_dentry; do { printf("`%s'\n", dentry->full_path_utf8); - } while ((dentry = container_of(dentry->link_group_list.next, + } while ((dentry = container_of(dentry->inode_dentry_list.next, struct dentry, - link_group_list)) != first_dentry); + inode_dentry_list)) != first_dentry); } + #endif -/* Fix up a "true" link group and check for inconsistencies */ -static int -fix_true_link_group(struct dentry *first_dentry) +static size_t inode_link_count(const struct inode *inode) +{ + const struct list_head *cur; + size_t size = 0; + list_for_each(cur, &inode->dentry_list) + size++; + return size; +} + +static struct dentry *inode_first_dentry(struct inode *inode) +{ + return container_of(inode->dentry_list.next, struct dentry, + inode_dentry_list); +} + +/* Fix up a "true" inode and check for inconsistencies */ +static int fix_true_inode(struct inode *inode) { struct dentry *dentry; struct dentry *ref_dentry = NULL; @@ -359,110 +294,80 @@ fix_true_link_group(struct dentry *first_dentry) u64 last_atime = 0; bool found_short_name = false; - dentry = first_dentry; - do { - if (!ref_dentry || ref_dentry->num_ads == 0) + list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) { + if (!ref_dentry || ref_dentry->inode->num_ads == 0) ref_dentry = dentry; if (dentry->short_name_len) { if (found_short_name) { ERROR("Multiple short names in hard link " "group!"); - inconsistent_link_group(first_dentry); + inconsistent_inode(inode); return WIMLIB_ERR_INVALID_DENTRY; } else { found_short_name = true; } } - if (dentry->creation_time > last_ctime) - last_ctime = dentry->creation_time; - if (dentry->last_write_time > last_mtime) - last_mtime = dentry->last_write_time; - if (dentry->last_access_time > last_atime) - last_atime = dentry->last_access_time; - } while ((dentry = container_of(dentry->link_group_list.next, - struct dentry, - link_group_list)) != first_dentry); - + if (dentry->inode->creation_time > last_ctime) + last_ctime = dentry->inode->creation_time; + if (dentry->inode->last_write_time > last_mtime) + last_mtime = dentry->inode->last_write_time; + if (dentry->inode->last_access_time > last_atime) + last_atime = dentry->inode->last_access_time; + } - ref_dentry->ads_entries_status = ADS_ENTRIES_OWNER; - dentry = first_dentry; - do { + list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) { if (dentry != ref_dentry) { if (!dentries_consistent(ref_dentry, dentry)) { - inconsistent_link_group(first_dentry); + inconsistent_inode(inode); return WIMLIB_ERR_INVALID_DENTRY; } - copy_hash(dentry->hash, ref_dentry->hash); - dentry_free_ads_entries(dentry); - dentry->num_ads = ref_dentry->num_ads; - dentry->ads_entries = ref_dentry->ads_entries; - dentry->ads_entries_status = ADS_ENTRIES_USER; + /* Free the unneeded `struct inode'. */ + free_inode(dentry->inode); + dentry->inode = ref_dentry->inode; + ref_dentry->inode->link_count++; } - dentry->creation_time = last_ctime; - dentry->last_write_time = last_mtime; - dentry->last_access_time = last_atime; - } while ((dentry = container_of(dentry->link_group_list.next, - struct dentry, - link_group_list)) != first_dentry); + } + ref_dentry->inode->creation_time = last_ctime; + ref_dentry->inode->last_write_time = last_mtime; + ref_dentry->inode->last_access_time = last_atime; + wimlib_assert(inode_link_count(inode) == inode->link_count); return 0; } /* - * Fixes up a nominal link group. + * Fixes up a nominal inode. * - * By a nominal link group we mean a group of two or more dentries that share + * By a nominal inode we mean a group of two or more dentries that share * the same hard link group ID. * - * If dentries in the group are found to be inconsistent, we may split the group - * into several "true" hard link groups. @new_groups points to a linked list of - * these split groups, and if we create any, they will be added to this list. - * - * After splitting up each nominal link group into the "true" link groups we - * will canonicalize the link groups. To do this, we: + * If dentries in the inode are found to be inconsistent, we may split the inode + * into several "true" inodes. @new_inodes points to a linked list of + * these split inodes, and if we create any, they will be added to this list. * - * - Assign all the dentries in the link group the most recent timestamp - * among all the corresponding timestamps in the link group, for each of - * the three categories of time stamps. - * - * - Make sure the dentry->hash field is valid in all the dentries, if - * possible (this field may be all zeroes, and in the context of a hard - * link group this must be interpreted as implicitly refering to the same - * stream as another dentry in the hard link group that does NOT have all - * zeroes for this field). - * - * - Make sure dentry->num_ads is the same in all the dentries in the link - * group. In some cases, it's possible for it to be set to 0 when it - * actually must be interpreted as being the same as the number of - * alternate data streams in another dentry in the hard link group that has - * a nonzero number of alternate data streams. - * - * - Make sure only the dentry->ads_entries array is only allocated for one - * dentry in the hard link group. This dentry will have - * dentry->ads_entries_status set to ADS_ENTRIES_OWNER, while the others - * will have dentry->ads_entries_status set to ADS_ENTRIES_USER. + * After splitting up each nominal inode into the "true" inodes we + * will canonicalize the link group by getting rid of all the superfluous + * `struct inodes'. There will be just one `struct inode' for each hard link + * group remaining. */ static int -fix_nominal_link_group(struct link_group *group, - struct link_group **new_groups) +fix_nominal_inode(struct inode *inode, struct hlist_head *inode_list) { struct dentry *tmp, *dentry, *ref_dentry; + struct hlist_node *cur; int ret; - size_t num_true_link_groups; - struct list_head *head; + size_t num_true_inodes; LIST_HEAD(dentries_with_data_streams); LIST_HEAD(dentries_with_no_data_streams); - LIST_HEAD(true_link_groups); + HLIST_HEAD(true_inodes); - /* Create a list of dentries in the nominal hard link group that have at + /* Create a list of dentries in the nominal inode that have at * least one data stream with a non-zero hash, and another list that * contains the dentries that have a zero hash for all data streams. */ - dentry = container_of(group->dentry_list, struct dentry, - link_group_list); - do { - for (unsigned i = 0; i <= dentry->num_ads; i++) { + list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) { + for (unsigned i = 0; i <= dentry->inode->num_ads; i++) { const u8 *hash; - hash = dentry_stream_hash(dentry, i); + hash = inode_stream_hash(dentry->inode, i); if (!is_zero_hash(hash)) { list_add(&dentry->tmp_list, &dentries_with_data_streams); @@ -472,93 +377,85 @@ fix_nominal_link_group(struct link_group *group, list_add(&dentry->tmp_list, &dentries_with_no_data_streams); next_dentry: - dentry = container_of(dentry->link_group_list.next, - struct dentry, - link_group_list); - } while (&dentry->link_group_list != group->dentry_list); + ; + } /* If there are no dentries with data streams, we require the nominal - * link group to be a true link group */ + * inode to be a true inode */ if (list_empty(&dentries_with_data_streams)) { #ifdef ENABLE_DEBUG { - size_t size = dentry_link_group_size(dentry); - if (size > 1) { + if (inode->link_count > 1) { DEBUG("Found link group of size %zu without " - "any data streams:", size); - print_dentry_list(dentry); + "any data streams:", inode->link_count); + print_inode_dentries(inode); DEBUG("We are going to interpret it as true " "link group, provided that the dentries " "are consistent."); } } #endif - return fix_true_link_group(container_of(group->dentry_list, - struct dentry, - link_group_list)); + hlist_add_head(&inode->hlist, inode_list); + return fix_true_inode(inode); } /* One or more dentries had data streams specified. We check each of * these dentries for consistency with the others to form a set of true - * link groups. */ - num_true_link_groups = 0; - list_for_each_entry_safe(dentry, tmp, &dentries_with_data_streams, - tmp_list) + * inodes. */ + num_true_inodes = 0; + list_for_each_entry(dentry, &dentries_with_data_streams, tmp_list) { - list_del(&dentry->tmp_list); - - /* Look for a true link group that is consistent with + /* Look for a true inode that is consistent with * this dentry and add this dentry to it. Or, if none - * of the true link groups are consistent with this + * of the true inodes are consistent with this * dentry, make a new one. */ - list_for_each_entry(ref_dentry, &true_link_groups, tmp_list) { - if (ref_dentries_consistent(ref_dentry, dentry)) { - list_add(&dentry->link_group_list, - &ref_dentry->link_group_list); + hlist_for_each_entry(inode, cur, &true_inodes, hlist) { + if (ref_dentries_consistent(inode_first_dentry(inode), dentry)) { + list_add(&dentry->inode_dentry_list, + &inode->dentry_list); goto next_dentry_2; } } - num_true_link_groups++; - list_add(&dentry->tmp_list, &true_link_groups); - INIT_LIST_HEAD(&dentry->link_group_list); + num_true_inodes++; + hlist_add_head(&dentry->inode->hlist, &true_inodes); + INIT_LIST_HEAD(&dentry->inode->dentry_list); + list_add(&dentry->inode_dentry_list, &dentry->inode->dentry_list); next_dentry_2: ; } - wimlib_assert(num_true_link_groups != 0); + wimlib_assert(num_true_inodes != 0); /* If there were dentries with no data streams, we require there to only - * be one true link group so that we know which link group to assign the + * be one true inode so that we know which inode to assign the * streamless dentries to. */ if (!list_empty(&dentries_with_no_data_streams)) { - if (num_true_link_groups != 1) { - ERROR("Hard link group ambiguity detected!"); - ERROR("We split up hard link group 0x%"PRIx64" due to " - "inconsistencies,", group->link_group_id); + if (num_true_inodes != 1) { + ERROR("Hard inode ambiguity detected!"); + ERROR("We split up inode 0x%"PRIx64" due to " + "inconsistencies,", inode->ino); ERROR("but dentries with no stream information remained. " "We don't know which true hard link"); - ERROR("group to assign them to."); + ERROR("inode to assign them to."); return WIMLIB_ERR_INVALID_DENTRY; } /* Assign the streamless dentries to the one and only true link - * group. */ - ref_dentry = container_of(true_link_groups.next, - struct dentry, - tmp_list); + * inode. */ + ref_dentry = inode_first_dentry(inode); list_for_each_entry(dentry, &dentries_with_no_data_streams, tmp_list) - list_add(&dentry->link_group_list, &ref_dentry->link_group_list); + list_add(&dentry->inode_dentry_list, &inode->dentry_list); } - if (num_true_link_groups != 1) { + if (num_true_inodes != 1) { #ifdef ENABLE_DEBUG { - printf("Split nominal link group 0x%"PRIx64" into %zu " - "link groups:\n", - group->link_group_id, num_true_link_groups); + printf("Split nominal inode 0x%"PRIx64" into %zu " + "inodes:\n", + inode->ino, num_true_inodes); puts("------------------------------------------------------------------------------"); size_t i = 1; - list_for_each_entry(dentry, &true_link_groups, tmp_list) { - printf("[Split link group %zu]\n", i++); - print_dentry_list(dentry); + hlist_for_each_entry(inode, cur, &true_inodes, hlist) { + printf("[Split inode %zu]\n", i++); + print_inode_dentries(inode); putchar('\n'); } puts("------------------------------------------------------------------------------"); @@ -566,56 +463,36 @@ next_dentry_2: #endif } - list_for_each_entry(dentry, &true_link_groups, tmp_list) { - ret = fix_true_link_group(dentry); + hlist_for_each_entry(inode, cur, &true_inodes, hlist) { + hlist_add_head(&inode->hlist, inode_list); + ret = fix_true_inode(inode); if (ret != 0) return ret; } - - /* Make new `struct link_group's for the new link groups */ - for (head = true_link_groups.next->next; - head != &true_link_groups; - head = head->next) - { - dentry = container_of(head, struct dentry, tmp_list); - group = MALLOC(sizeof(*group)); - if (!group) { - ERROR("Out of memory"); - return WIMLIB_ERR_NOMEM; - } - group->link_group_id = dentry->link_group_id; - group->dentry_list = &dentry->link_group_list; - group->next = *new_groups; - *new_groups = group; - } return 0; } /* - * Goes through each link group and shares the ads_entries (Alternate Data - * Stream entries) field of each dentry among members of a hard link group. + * Goes through each inode and shares the inodes among members of a hard + * inode. * - * In the process, the dentries in each link group are checked for consistency. + * In the process, the dentries in each inode are checked for consistency. * If they contain data features that indicate they cannot really be in the same - * hard link group, this should be an error, but in reality this case needs to - * be handled, so we split the dentries into different hard link groups. - * - * One of the dentries in each hard link group group is arbitrarily assigned the - * role of "owner" of the memory pointed to by the @ads_entries field, - * (ADS_ENTRIES_OWNER), while the others are "users" (ADS_ENTRIES_USER) who are - * not allowed to free the memory. + * inode, this should be an error, but in reality this case needs to + * be handled, so we split the dentries into different inodes. */ -int fix_link_groups(struct link_group_table *table) +int fix_inodes(struct inode_table *table, struct hlist_head *inode_list) { + struct inode *inode; + struct hlist_node *cur, *tmp; + int ret = 0; + INIT_HLIST_HEAD(inode_list); for (u64 i = 0; i < table->capacity; i++) { - struct link_group *group = table->array[i]; - while (group) { - int ret; - ret = fix_nominal_link_group(group, &table->extra_groups); + hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], hlist) { + ret = fix_nominal_inode(inode, inode_list); if (ret != 0) - return ret; - group = group->next; + break; } } - return 0; + return ret; } diff --git a/src/list.h b/src/list.h index e21f6d17..b5717c48 100644 --- a/src/list.h +++ b/src/list.h @@ -41,7 +41,7 @@ struct hlist_node { /* * Structure used to create a linked list of streams that share the same lookup - * table entry. This structure may be embedded in either a dentry (for the + * table entry. This structure may be embedded in either a inode (for the * un-named data stream) or an ads_entry (for an alternate data stream). The * @type field indicates which of these structures the stream_list_head is * embedded in. diff --git a/src/lookup_table.c b/src/lookup_table.c index 5408baf6..54b5d756 100644 --- a/src/lookup_table.c +++ b/src/lookup_table.c @@ -422,7 +422,7 @@ __lookup_resource(const struct lookup_table *table, const u8 hash[]) * Finds the dentry, lookup table entry, and stream index for a WIM file stream, * given a path name. * - * This is only for pre-resolved dentries. + * This is only for pre-resolved inodes. */ int lookup_resource(WIMStruct *w, const char *path, int lookup_flags, @@ -434,6 +434,7 @@ int lookup_resource(WIMStruct *w, const char *path, struct lookup_table_entry *lte; unsigned stream_idx; const char *stream_name = NULL; + struct inode *inode; char *p = NULL; if (lookup_flags & LOOKUP_FLAG_ADS_OK) { @@ -450,22 +451,25 @@ int lookup_resource(WIMStruct *w, const char *path, if (!dentry) return -ENOENT; - wimlib_assert(dentry->resolved); + inode = dentry->inode; + + wimlib_assert(inode->resolved); - lte = dentry->lte; if (!(lookup_flags & LOOKUP_FLAG_DIRECTORY_OK) - && dentry_is_directory(dentry)) + && inode_is_directory(inode)) return -EISDIR; + + lte = inode->lte; stream_idx = 0; if (stream_name) { size_t stream_name_len = strlen(stream_name); - for (u16 i = 0; i < dentry->num_ads; i++) { - if (ads_entry_has_name(&dentry->ads_entries[i], + for (u16 i = 0; i < inode->num_ads; i++) { + if (ads_entry_has_name(inode->ads_entries[i], stream_name, stream_name_len)) { stream_idx = i + 1; - lte = dentry->ads_entries[i].lte; + lte = inode->ads_entries[i]->lte; goto out; } } @@ -481,6 +485,36 @@ out: return 0; } +static int inode_resolve_ltes(struct inode *inode, struct lookup_table *table) +{ + struct lookup_table_entry *lte; + + /* Resolve the default file stream */ + lte = __lookup_resource(table, inode->hash); + if (lte) + list_add(&inode->lte_group_list.list, <e->lte_group_list); + else + INIT_LIST_HEAD(&inode->lte_group_list.list); + inode->lte = lte; + inode->lte_group_list.type = STREAM_TYPE_NORMAL; + inode->resolved = true; + + /* Resolve the alternate data streams */ + for (u16 i = 0; i < inode->num_ads; i++) { + struct ads_entry *cur_entry = inode->ads_entries[i]; + + lte = __lookup_resource(table, cur_entry->hash); + if (lte) + list_add(&cur_entry->lte_group_list.list, + <e->lte_group_list); + else + INIT_LIST_HEAD(&cur_entry->lte_group_list.list); + cur_entry->lte = lte; + cur_entry->lte_group_list.type = STREAM_TYPE_ADS; + } + return 0; +} + /* Resolve a dentry's lookup table entries * * This replaces the SHA1 hash fields (which are used to lookup an entry in the @@ -490,65 +524,40 @@ out: * This function always succeeds; unresolved lookup table entries are given a * NULL pointer. */ -int dentry_resolve_ltes(struct dentry *dentry, void *__table) +int dentry_resolve_ltes(struct dentry *dentry, void *table) { - struct lookup_table *table = __table; - struct lookup_table_entry *lte; - - if (dentry->resolved) + if (dentry->inode->resolved) return 0; - - /* Resolve the default file stream */ - lte = __lookup_resource(table, dentry->hash); - if (lte) - list_add(&dentry->lte_group_list.list, <e->lte_group_list); else - INIT_LIST_HEAD(&dentry->lte_group_list.list); - dentry->lte = lte; - dentry->lte_group_list.type = STREAM_TYPE_NORMAL; - dentry->resolved = true; - - /* Resolve the alternate data streams */ - if (dentry->ads_entries_status != ADS_ENTRIES_USER) { - for (u16 i = 0; i < dentry->num_ads; i++) { - struct ads_entry *cur_entry = &dentry->ads_entries[i]; - - lte = __lookup_resource(table, cur_entry->hash); - if (lte) - list_add(&cur_entry->lte_group_list.list, - <e->lte_group_list); - else - INIT_LIST_HEAD(&cur_entry->lte_group_list.list); - cur_entry->lte = lte; - cur_entry->lte_group_list.type = STREAM_TYPE_ADS; - } - } - return 0; + return inode_resolve_ltes(dentry->inode, table); } -/* Return the lookup table entry for the unnamed data stream of a dentry, or + + + +/* Return the lookup table entry for the unnamed data stream of a inode, or * NULL if there is none. * * You'd think this would be easier than it actually is, since the unnamed data - * stream should be the one referenced from the dentry itself. Alas, if there + * stream should be the one referenced from the inode itself. Alas, if there * are named data streams, Microsoft's "imagex.exe" program will put the unnamed * data stream in one of the alternate data streams instead of inside the - * dentry. So we need to check the alternate data streams too. + * inode. So we need to check the alternate data streams too. * - * Also, note that a dentry may appear to have than one unnamed stream, but if + * Also, note that a inode may appear to have than one unnamed stream, but if * the SHA1 message digest is all 0's then the corresponding stream does not - * really "count" (this is the case for the dentry's own file stream when the + * really "count" (this is the case for the inode's own file stream when the * file stream that should be there is actually in one of the alternate stream * entries.). This is despite the fact that we may need to extract such a * missing entry as an empty file or empty named data stream. */ struct lookup_table_entry * -dentry_unnamed_lte(const struct dentry *dentry, +inode_unnamed_lte(const struct inode *inode, const struct lookup_table *table) { - if (dentry->resolved) - return dentry_unnamed_lte_resolved(dentry); + if (inode->resolved) + return inode_unnamed_lte_resolved(inode); else - return dentry_unnamed_lte_unresolved(dentry, table); + return inode_unnamed_lte_unresolved(inode, table); } diff --git a/src/lookup_table.h b/src/lookup_table.h index 6fc5ae50..ede2bfe6 100644 --- a/src/lookup_table.h +++ b/src/lookup_table.h @@ -300,75 +300,66 @@ static inline struct resource_entry* wim_metadata_resource_entry(WIMStruct *w) } static inline struct lookup_table_entry * -dentry_stream_lte_resolved(const struct dentry *dentry, unsigned stream_idx) +inode_stream_lte_resolved(const struct inode *inode, unsigned stream_idx) { - wimlib_assert(dentry->resolved); - wimlib_assert(stream_idx <= dentry->num_ads); + wimlib_assert(inode->resolved); + wimlib_assert(stream_idx <= inode->num_ads); if (stream_idx == 0) - return dentry->lte; + return inode->lte; else - return dentry->ads_entries[stream_idx - 1].lte; + return inode->ads_entries[stream_idx - 1]->lte; } static inline struct lookup_table_entry * -dentry_stream_lte_unresolved(const struct dentry *dentry, unsigned stream_idx, +inode_stream_lte_unresolved(const struct inode *inode, unsigned stream_idx, const struct lookup_table *table) { - wimlib_assert(!dentry->resolved); - wimlib_assert(stream_idx <= dentry->num_ads); + wimlib_assert(!inode->resolved); + wimlib_assert(stream_idx <= inode->num_ads); if (!table) return NULL; if (stream_idx == 0) - return __lookup_resource(table, dentry->hash); + return __lookup_resource(table, inode->hash); else return __lookup_resource(table, - dentry->ads_entries[ - stream_idx - 1].hash); + inode->ads_entries[ + stream_idx - 1]->hash); } /* - * Returns the lookup table entry for stream @stream_idx of the dentry, where + * Returns the lookup table entry for stream @stream_idx of the inode, where * stream_idx = 0 means the default un-named file stream, and stream_idx >= 1 * corresponds to an alternate data stream. * * This works for both resolved and un-resolved dentries. */ static inline struct lookup_table_entry * -dentry_stream_lte(const struct dentry *dentry, unsigned stream_idx, - const struct lookup_table *table) +inode_stream_lte(const struct inode *inode, unsigned stream_idx, + const struct lookup_table *table) { - if (dentry->resolved) - return dentry_stream_lte_resolved(dentry, stream_idx); + if (inode->resolved) + return inode_stream_lte_resolved(inode, stream_idx); else - return dentry_stream_lte_unresolved(dentry, stream_idx, table); + return inode_stream_lte_unresolved(inode, stream_idx, table); } -static inline const u8 *dentry_stream_hash_unresolved(const struct dentry *dentry, - unsigned stream_idx) +static inline const u8 *inode_stream_hash_unresolved(const struct inode *inode, + unsigned stream_idx) { - wimlib_assert(!dentry->resolved); - wimlib_assert(stream_idx <= dentry->num_ads); + wimlib_assert(!inode->resolved); + wimlib_assert(stream_idx <= inode->num_ads); if (stream_idx == 0) - return dentry->hash; + return inode->hash; else - return dentry->ads_entries[stream_idx - 1].hash; + return inode->ads_entries[stream_idx - 1]->hash; } -static inline u16 dentry_stream_name_len(const struct dentry *dentry, - unsigned stream_idx) -{ - wimlib_assert(stream_idx <= dentry->num_ads); - if (stream_idx == 0) - return 0; - else - return dentry->ads_entries[stream_idx - 1].stream_name_len; -} -static inline const u8 *dentry_stream_hash_resolved(const struct dentry *dentry, - unsigned stream_idx) +static inline const u8 *inode_stream_hash_resolved(const struct inode *inode, + unsigned stream_idx) { struct lookup_table_entry *lte; - lte = dentry_stream_lte_resolved(dentry, stream_idx); + lte = inode_stream_lte_resolved(inode, stream_idx); if (lte) return lte->hash; else @@ -376,46 +367,57 @@ static inline const u8 *dentry_stream_hash_resolved(const struct dentry *dentry, } /* - * Returns the hash for stream @stream_idx of the dentry, where stream_idx = 0 + * Returns the hash for stream @stream_idx of the inode, where stream_idx = 0 * means the default un-named file stream, and stream_idx >= 1 corresponds to an * alternate data stream. * * This works for both resolved and un-resolved dentries. */ -static inline const u8 *dentry_stream_hash(const struct dentry *dentry, - unsigned stream_idx) +static inline const u8 *inode_stream_hash(const struct inode *inode, + unsigned stream_idx) { - if (dentry->resolved) - return dentry_stream_hash_resolved(dentry, stream_idx); + if (inode->resolved) + return inode_stream_hash_resolved(inode, stream_idx); else - return dentry_stream_hash_unresolved(dentry, stream_idx); + return inode_stream_hash_unresolved(inode, stream_idx); +} + +static inline u16 inode_stream_name_len(const struct inode *inode, + unsigned stream_idx) +{ + wimlib_assert(stream_idx <= inode->num_ads); + if (stream_idx == 0) + return 0; + else + return inode->ads_entries[stream_idx - 1]->stream_name_len; } static inline struct lookup_table_entry * -dentry_unnamed_lte_resolved(const struct dentry *dentry) +inode_unnamed_lte_resolved(const struct inode *inode) { - wimlib_assert(dentry->resolved); - for (unsigned i = 0; i <= dentry->num_ads; i++) - if (dentry_stream_name_len(dentry, i) == 0 && - !is_zero_hash(dentry_stream_hash_resolved(dentry, i))) - return dentry_stream_lte_resolved(dentry, i); + wimlib_assert(inode->resolved); + for (unsigned i = 0; i <= inode->num_ads; i++) + if (inode_stream_name_len(inode, i) == 0 && + !is_zero_hash(inode_stream_hash_resolved(inode, i))) + return inode_stream_lte_resolved(inode, i); return NULL; } static inline struct lookup_table_entry * -dentry_unnamed_lte_unresolved(const struct dentry *dentry, - const struct lookup_table *table) +inode_unnamed_lte_unresolved(const struct inode *inode, + const struct lookup_table *table) { - wimlib_assert(!dentry->resolved); - for (unsigned i = 0; i <= dentry->num_ads; i++) - if (dentry_stream_name_len(dentry, i) == 0 && - !is_zero_hash(dentry_stream_hash_unresolved(dentry, i))) - return dentry_stream_lte_unresolved(dentry, i, table); + wimlib_assert(!inode->resolved); + for (unsigned i = 0; i <= inode->num_ads; i++) + if (inode_stream_name_len(inode, i) == 0 && + !is_zero_hash(inode_stream_hash_unresolved(inode, i))) + return inode_stream_lte_unresolved(inode, i, table); return NULL; } extern struct lookup_table_entry * -dentry_unnamed_lte(const struct dentry *dentry, - const struct lookup_table *table); +inode_unnamed_lte(const struct inode *inode, + const struct lookup_table *table); + #endif diff --git a/src/modify.c b/src/modify.c index 8519881d..d2b03abe 100644 --- a/src/modify.c +++ b/src/modify.c @@ -48,7 +48,6 @@ void destroy_image_metadata(struct image_metadata *imd,struct lookup_table *lt) { free_dentry_tree(imd->root_dentry, lt); free_security_data(imd->security_data); - free_link_group_table(imd->lgt); /* Get rid of the lookup table entry for this image's metadata resource * */ @@ -128,13 +127,13 @@ static int build_dentry_tree(struct dentry **root_ret, const char *root_disk_pat else filename = path_basename(root_disk_path); - root = new_dentry(filename); + root = new_dentry_with_inode(filename); if (!root) return WIMLIB_ERR_NOMEM; stbuf_to_dentry(&root_stbuf, root); add_flags &= ~WIMLIB_ADD_IMAGE_FLAG_ROOT; - root->resolved = true; + root->inode->resolved = true; if (dentry_is_directory(root)) { /* Open the directory on disk */ @@ -185,8 +184,8 @@ static int build_dentry_tree(struct dentry **root_ret, const char *root_disk_pat } deref_name_buf[deref_name_len] = '\0'; DEBUG("Read symlink `%s'", deref_name_buf); - ret = dentry_set_symlink(root, deref_name_buf, - lookup_table, NULL); + ret = inode_set_symlink(root->inode, deref_name_buf, + lookup_table, NULL); } else { /* Regular file */ struct lookup_table_entry *lte; @@ -227,7 +226,7 @@ static int build_dentry_tree(struct dentry **root_ret, const char *root_disk_pat copy_hash(lte->hash, hash); lookup_table_insert(lookup_table, lte); } - root->lte = lte; + root->inode->lte = lte; } out: *root_ret = root; @@ -254,16 +253,16 @@ static int add_lte_to_dest_wim(struct dentry *dentry, void *arg) src_wim = ((struct wim_pair*)arg)->src_wim; dest_wim = ((struct wim_pair*)arg)->dest_wim; - wimlib_assert(!dentry->resolved); + wimlib_assert(!dentry->inode->resolved); - for (unsigned i = 0; i < (unsigned)dentry->num_ads + 1; i++) { + for (unsigned i = 0; i < (unsigned)dentry->inode->num_ads + 1; i++) { struct lookup_table_entry *src_lte, *dest_lte; - src_lte = dentry_stream_lte_unresolved(dentry, i, - src_wim->lookup_table); + src_lte = inode_stream_lte_unresolved(dentry->inode, i, + src_wim->lookup_table); if (!src_lte) continue; - dest_lte = dentry_stream_lte_unresolved(dentry, i, - dest_wim->lookup_table); + dest_lte = inode_stream_lte_unresolved(dentry->inode, i, + dest_wim->lookup_table); if (dest_lte) { dest_lte->refcnt++; } else { @@ -314,10 +313,6 @@ static int add_new_dentry_tree(WIMStruct *w, struct dentry *root_dentry, if (!metadata_lte) goto out_free_imd; - lgt = new_link_group_table(9001); - if (!lgt) - goto out_free_metadata_lte; - metadata_lte->resource_entry.flags = WIM_RESHDR_FLAG_METADATA; random_hash(metadata_lte->hash); lookup_table_insert(w->lookup_table, metadata_lte); @@ -327,7 +322,6 @@ static int add_new_dentry_tree(WIMStruct *w, struct dentry *root_dentry, new_imd->root_dentry = root_dentry; new_imd->metadata_lte = metadata_lte; new_imd->security_data = sd; - new_imd->lgt = lgt; new_imd->modified = true; FREE(w->image_metadata); @@ -811,7 +805,8 @@ int do_add_image(WIMStruct *w, const char *dir, const char *name, struct dentry *root_dentry = NULL; struct wim_security_data *sd; struct capture_config config; - struct link_group_table *lgt; + struct inode_table *inode_tab; + struct hlist_head inode_list; int ret; DEBUG("Adding dentry tree from directory or NTFS volume `%s'.", dir); @@ -875,20 +870,17 @@ int do_add_image(WIMStruct *w, const char *dir, const char *name, if (ret != 0) goto out_free_dentry_tree; - lgt = w->image_metadata[w->hdr.image_count - 1].lgt; - DEBUG("Inserting dentries into hard link group table"); - ret = for_dentry_in_tree(root_dentry, link_group_table_insert, lgt); - - if (ret != 0) - goto out_destroy_imd; + DEBUG("Inserting dentries into inode table"); + for_dentry_in_tree(root_dentry, inode_table_insert, inode_tab); DEBUG("Cleanup up the hard link groups"); - ret = fix_link_groups(lgt); + ret = fix_inodes(inode_tab, &inode_list); + free_inode_table(inode_tab); if (ret != 0) goto out_destroy_imd; DEBUG("Assigning hard link group IDs"); - assign_link_group_ids(w->image_metadata[w->hdr.image_count - 1].lgt); + assign_inode_numbers(&inode_list); if (flags & WIMLIB_ADD_IMAGE_FLAG_BOOT) wimlib_set_boot_idx(w, w->hdr.image_count); diff --git a/src/mount.c b/src/mount.c index 6efe84c6..530fdf68 100644 --- a/src/mount.c +++ b/src/mount.c @@ -51,14 +51,45 @@ #include #endif +/* File descriptor to a file open on the WIM filesystem. */ struct wimlib_fd { + /* Index of this file descriptor in the lookup table entry's table of + * file descriptors */ u16 idx; + + /* Index of the stream we've opened from a dentry */ + u16 stream_idx; + + /* Native file descriptor to the staging file */ int staging_fd; - u64 hard_link_group; + + /* Pointer to lookup table entry that has the table of file descriptors + * containing this file descriptor */ struct lookup_table_entry *lte; - struct dentry *dentry; + + union { + struct dentry *dentry; + struct ads_entry *ads_entry; + }; + + /* Hard link group ID of the dentry containing the stream that was + * opened to produce this file descriptor. + * + * This is always valid even if @dentry is NULL. It can be used to + * identify file descriptors corresponding to the same hard-linked + * stream, even if the specific dentry under which the stream was opened + * has been unlinked. */ + u64 link_group_id; }; +static inline struct dentry *fd_dentry(const struct wimlib_fd *fd) +{ + if (fd->stream_idx == 0) + return fd->dentry; + else + return fd->ads_entry ? fd->ads_entry->dentry : NULL; +} + /* The WIMStruct for the mounted WIM. */ static WIMStruct *w; @@ -175,14 +206,37 @@ static void remove_dentry(struct dentry *dentry, wimlib_assert(dentry); wimlib_assert(dentry->resolved); - struct lookup_table_entry *lte = dentry->lte; + if (dentry->ads_entries_status == ADS_ENTRIES_OWNER) { + struct dentry *new_owner; + list_for_each_entry(new_owner, &dentry->link_group_list, + link_group_list) + { + if (new_owner->ads_entries_status == ADS_ENTRIES_USER) { + new_owner->ads_entries_status = ADS_ENTRIES_OWNER; + for (u16 i = 0; i < dentry->num_ads; i++) + dentry->ads_entries[i]->dentry = new_owner; + break; + } + } + dentry->ads_entries_status = ADS_ENTRIES_USER; + } + list_del(&dentry->link_group_list); + list_del(&dentry->lte_group_list); + u16 i = 0; + struct lookup_table_entry *lte = dentry->lte; while (1) { lte = lte_decrement_refcnt(lte, lookup_table); if (lte && lte->num_opened_fds) - for (u16 i = 0; i < lte->num_allocated_fds; i++) - if (lte->fds[i] && lte->fds[i]->dentry == dentry) - lte->fds[i]->dentry = NULL; + for (u16 j = 0; j < lte->num_allocated_fds; j++) + if (lte->fds[j] && + lte->fds[j]->link_group_id == dentry->link_group_id + && ((lte->fds[j].stream_idx == 0 && + lte->fds[j].dentry == dentry) || + (lte->fds[j].stream_idx && + lte->fds[j].ads_entry && + lte->fds[j].ads_entry->dentry == dentry))) + lte->fds[j].dentry = NULL; if (i == dentry->num_ads) break; lte = dentry->ads_entries[i].lte; @@ -190,7 +244,7 @@ static void remove_dentry(struct dentry *dentry, } unlink_dentry(dentry); - put_dentry(dentry); + free_dentry(dentry); } static void remove_ads(struct dentry *dentry, @@ -200,10 +254,30 @@ static void remove_ads(struct dentry *dentry, struct lookup_table_entry *lte; wimlib_assert(dentry->resolved); + wimlib_assert(ads_entry - dentry->ads_entries < dentry->num_ads); lte = lte_decrement_refcnt(ads_entry->lte, lookup_table); if (lte) - list_del(&ads_entry->lte_group_list.list); + for (u16 i = 0; i < lte->num_allocated_fds; i++) + if (lte->fds[i] && lte->fds[i]->dentry == dentry) + lte->fds[i]->dentry = NULL; + + /* Fix up file descriptor stream indexes */ + for (u16 i = ads_entry - dentry->ads_entries + 1; i < dentry->num_ads; i++) { + struct lookup_table_entry *lte = ads_entry[i].lte; + if (lte) { + for (u16 open_fd_idx = 0, fd_idx = 0; + open_fd_idx < lte->num_opened_fds; fd_idx++) + { + if (lte->fds[fd_idx]) { + open_fd_idx++; + if (lte->fds[fd_idx]->dentry == dentry + && lte->fds[fd_idx]->stream_idx > idx) + lte->fds[fd_idx]->stream_id + } + } + } + } dentry_remove_ads(dentry, ads_entry); } @@ -309,12 +383,18 @@ static int create_staging_file(char **name_ret, int open_flags) /* * Removes open file descriptors from a lookup table entry @old_lte where the - * file descriptors have opened the corresponding file resource in the context - * of the hard link group @link_group; these file descriptors are extracted and - * placed in a new lookup table entry, which is returned. + * removed file descriptors have opened the corresponding file resource in the + * context of a dentry in the hard link group @link_group and a stream at index + * @stream_idx. These file descriptors are extracted and placed in a new lookup + * table entry, which is returned. + * + * Note we need to examine the link_group_id of each file descriptor and not + * dentry->link_group_id of each file descriptor, since dentry may be NULL in + * the case of an un-linked dentry. */ static struct lookup_table_entry * -lte_extract_fds(struct lookup_table_entry *old_lte, u64 link_group) +lte_extract_fds(struct lookup_table_entry *old_lte, u64 link_group_id, + u16 stream_idx) { u16 num_transferred_fds; struct lookup_table_entry *new_lte; @@ -325,8 +405,9 @@ lte_extract_fds(struct lookup_table_entry *old_lte, u64 link_group) num_transferred_fds = 0; for (u16 i = 0; i < old_lte->num_allocated_fds; i++) - if (old_lte->fds[i] && old_lte->fds[i]->dentry && - old_lte->fds[i]->dentry->link_group_id == link_group) + if (old_lte->fds[i] + && old_lte->fds[i]->link_group_id == link_group_id + && old_lte->fds[i]->stream_idx == stream_idx) num_transferred_fds++; DEBUG("Transferring %u file descriptors", num_transferred_fds); @@ -336,8 +417,9 @@ lte_extract_fds(struct lookup_table_entry *old_lte, u64 link_group) return NULL; } for (u16 i = 0, j = 0; ; i++) { - if (old_lte->fds[i] && old_lte->fds[i]->dentry && - old_lte->fds[i]->dentry->link_group_id == link_group) { + if (old_lte->fds[i] + && old_lte->fds[i]->link_group_id == link_group_id + && old_lte->fds[i]->stream_idx == stream_idx) { struct wimlib_fd *fd = old_lte->fds[i]; old_lte->fds[i] = NULL; fd->lte = new_lte; @@ -440,7 +522,8 @@ static int extract_resource_to_staging_dir(struct dentry *dentry, * lookup table entry. */ - DEBUG("Extracting resource `%s' to staging directory", dentry->full_path_utf8); + DEBUG("Extracting dentry `%s' stream %u to staging directory", + dentry->full_path_utf8, stream_idx); old_lte = *lte; fd = create_staging_file(&staging_file_name, O_WRONLY); @@ -463,9 +546,15 @@ static int extract_resource_to_staging_dir(struct dentry *dentry, link_group_size = dentry_link_group_size(dentry); if (old_lte) { + wimlib_assert(old_lte->resource_location == RESOURCE_IN_WIM); if (link_group_size == old_lte->refcnt) { - /* This hard link group is the only user of the lookup - * table entry, so we can re-use it. */ + /* The reference count of the existing lookup table + * entry is the same as the size of the hard link group + * associated with the dentry; therefore, ALL the + * references to the lookup table entry correspond to + * the stream we're trying to extract. So the lookup + * table entry can be re-used. + */ DEBUG("Re-using lookup table entry"); lookup_table_unlink(w->lookup_table, old_lte); new_lte = old_lte; @@ -473,22 +562,22 @@ static int extract_resource_to_staging_dir(struct dentry *dentry, DEBUG("Splitting lookup table entry " "(link_group_size = %zu, lte refcnt = %u)", link_group_size, old_lte->refcnt); - /* Split a hard link group away from the "lookup table - * entry" hard link group (i.e. we had two hard link - * groups that were identical, but now we are changing - * one of them) */ - - /* XXX - * The ADS really complicate things here and not - * everything is going to work correctly yet. For - * example it could be the same that a file contains two - * file streams that are identical and therefore share - * the same lookup table entry despite the fact that the - * streams themselves are not hardlinked. - * XXX*/ + /* The stream we are going to change does not account + * for all the references to the lookup table entry. + * The other references to the lookup table entry may be + * from different hard link groups or from other streams + * in the same hard link group. + */ + wimlib_assert(old_lte->refcnt > link_group_size); - new_lte = lte_extract_fds(old_lte, dentry->link_group_id); + /* First, find the old lookup table entry's file + * descriptors that were opened in the context of the + * stream we're going to change, and allocate a new + * lookup table entry containing those file descriptors. + * */ + new_lte = lte_extract_fds(old_lte, link_group_id, + stream_idx); if (!new_lte) { ret = -ENOMEM; goto out_delete_staging_file; @@ -510,8 +599,6 @@ static int extract_resource_to_staging_dir(struct dentry *dentry, new_lte->resource_entry.original_size = size; new_lte->refcnt = link_group_size; random_hash(new_lte->hash); - if (new_lte->staging_file_name) - FREE(new_lte->staging_file_name); new_lte->staging_file_name = staging_file_name; new_lte->resource_location = RESOURCE_IN_STAGING_FILE; @@ -565,7 +652,7 @@ static void make_staging_dir() } static int remove_file_or_directory(const char *fpath, const struct stat *sb, - int typeflag, struct FTW *ftwbuf) + int typeflag, struct FTW *ftwbuf) { if (remove(fpath) == 0) return 0; @@ -577,7 +664,7 @@ static int remove_file_or_directory(const char *fpath, const struct stat *sb, /* * Deletes the staging directory and all the files contained in it. */ -static inline int delete_staging_dir() +static int delete_staging_dir() { int ret; @@ -599,18 +686,16 @@ static mqd_t daemon_to_unmount_mq; /* Simple function that returns the concatenation of 4 strings. */ static char *strcat_dup(const char *s1, const char *s2, const char *s3, - const char *s4) + const char *s4) { size_t len = strlen(s1) + strlen(s2) + strlen(s3) + strlen(s4) + 1; char *p = MALLOC(len); if (!p) return NULL; - *p = '\0'; - strcat(p, s1); - strcat(p, s2); - strcat(p, s3); - strcat(p, s4); - return p; + p = strcpy(p, s1); + p = strcat(p, s2); + p = strcat(p, s3); + return strcat(p, s4); } /* Removes trailing forward slashes in a string. */ @@ -1244,6 +1329,8 @@ static int wimfs_open(const char *path, struct fuse_file_info *fi) return ret; fd->dentry = dentry; + fd->stream_idx = stream_idx; + fd->link_group_id = dentry->link_group_id; /* The file resource may be in the staging directory (read-write * mounts only) or in the WIM. If it's in the staging @@ -1665,12 +1752,14 @@ static int wimfs_truncate(const char *path, off_t size) if (!lte) /* Already a zero-length file */ return 0; - if (lte->staging_file_name) { + if (lte->resource_location == RESOURCE_IN_STAGING_FILE) { + wimlib_assert(lte->staging_file_name); ret = truncate(lte->staging_file_name, size); if (ret != 0) return -errno; lte->resource_entry.original_size = size; } else { + wimlib_assert(lte->resource_location == RESOURCE_IN_WIM); /* File in WIM. Extract it to the staging directory, but only * the first @size bytes of it. */ ret = extract_resource_to_staging_dir(dentry, stream_idx, diff --git a/src/resource.c b/src/resource.c index 5ae2dff2..167901c9 100644 --- a/src/resource.c +++ b/src/resource.c @@ -1092,8 +1092,8 @@ int write_dentry_resources(struct dentry *dentry, void *wim_p) printf("Writing streams for `%s'\n", dentry->full_path_utf8); } - for (unsigned i = 0; i <= dentry->num_ads; i++) { - lte = dentry_stream_lte(dentry, i, w->lookup_table); + for (unsigned i = 0; i <= dentry->inode->num_ads; i++) { + lte = inode_stream_lte(dentry->inode, i, w->lookup_table); if (lte && ++lte->out_refcnt == 1) { ret = write_wim_resource(lte, w->out_fp, ctype, <e->output_resource_entry); @@ -1128,10 +1128,11 @@ int read_metadata_resource(WIMStruct *w, struct image_metadata *imd) u32 dentry_offset; int ret; struct dentry *dentry; - struct link_group_table *lgt; + struct inode_table *inode_tab; const struct lookup_table_entry *metadata_lte; u64 metadata_len; u64 metadata_offset; + struct hlist_head inode_list; metadata_lte = imd->metadata_lte; metadata_len = wim_resource_size(metadata_lte); @@ -1218,30 +1219,26 @@ int read_metadata_resource(WIMStruct *w, struct image_metadata *imd) /* Build hash table that maps hard link group IDs to dentry sets */ DEBUG("Building link group table"); - lgt = new_link_group_table(9001); - if (!lgt) + inode_tab = new_inode_table(9001); + if (!inode_tab) goto out_free_dentry_tree; - ret = for_dentry_in_tree(dentry, link_group_table_insert, lgt); - if (ret != 0) - goto out_free_lgt; + for_dentry_in_tree(dentry, inode_table_insert, inode_tab); DEBUG("Fixing inconsistencies in the link groups"); - ret = fix_link_groups(lgt); + ret = fix_inodes(inode_tab, &inode_list); + free_inode_table(inode_tab); if (ret != 0) - goto out_free_lgt; + goto out_free_dentry_tree; DEBUG("Running miscellaneous verifications on the dentry tree"); ret = for_dentry_in_tree(dentry, verify_dentry, w); if (ret != 0) - goto out_free_lgt; + goto out_free_dentry_tree; DEBUG("Done reading image metadata"); - imd->lgt = lgt; imd->root_dentry = dentry; goto out_free_buf; -out_free_lgt: - free_link_group_table(lgt); out_free_dentry_tree: free_dentry_tree(dentry, NULL); out_free_security_data: diff --git a/src/symlink.c b/src/symlink.c index 3b8ed435..cf2f863b 100644 --- a/src/symlink.c +++ b/src/symlink.c @@ -162,15 +162,15 @@ out: * * The dentry may be either "real" symlink or a junction point. */ -ssize_t dentry_readlink(const struct dentry *dentry, char *buf, size_t buf_len, - const WIMStruct *w) +ssize_t inode_readlink(const struct inode *inode, char *buf, size_t buf_len, + const WIMStruct *w) { const struct lookup_table_entry *lte; int ret; - wimlib_assert(dentry_is_symlink(dentry)); + wimlib_assert(inode_is_symlink(inode)); - lte = dentry_unnamed_lte(dentry, w->lookup_table); + lte = inode_unnamed_lte(inode, w->lookup_table); if (!lte) return -EIO; @@ -182,17 +182,20 @@ ssize_t dentry_readlink(const struct dentry *dentry, char *buf, size_t buf_len, if (ret != 0) return -EIO; return get_symlink_name(res_buf, wim_resource_size(lte), buf, - buf_len, dentry->reparse_tag); + buf_len, inode->reparse_tag); } -static int dentry_set_symlink_buf(struct dentry *dentry, - struct lookup_table_entry *lte) +static int inode_set_symlink_buf(struct inode *inode, + struct lookup_table_entry *lte) { +#if 0 struct ads_entry *ads_entries; - ads_entries = CALLOC(2, sizeof(struct ads_entry)); + ads_entries = MALLOC(2, sizeof(struct ads_entry)); if (!ads_entries) return WIMLIB_ERR_NOMEM; + ads_entry_init(&ads_entries[0]); + ads_entry_init(&ads_entries[1]); wimlib_assert(dentry->num_ads == 0); wimlib_assert(dentry->ads_entries == NULL); @@ -202,6 +205,9 @@ static int dentry_set_symlink_buf(struct dentry *dentry, /*dentry_free_ads_entries(dentry);*/ dentry->num_ads = 2; dentry->ads_entries = ads_entries; +#endif + wimlib_assert(inode->resolved); + inode->lte = lte; return 0; } @@ -216,9 +222,9 @@ static int dentry_set_symlink_buf(struct dentry *dentry, * * On failure @dentry and @lookup_table are not modified. */ -int dentry_set_symlink(struct dentry *dentry, const char *target, - struct lookup_table *lookup_table, - struct lookup_table_entry **lte_ret) +int inode_set_symlink(struct inode *inode, const char *target, + struct lookup_table *lookup_table, + struct lookup_table_entry **lte_ret) { int ret; @@ -257,12 +263,12 @@ int dentry_set_symlink(struct dentry *dentry, const char *target, copy_hash(lte->hash, symlink_buf_hash); } - ret = dentry_set_symlink_buf(dentry, lte); + ret = inode_set_symlink_buf(inode, lte); if (ret != 0) goto out_free_lte; - dentry->resolved = true; + inode->resolved = true; DEBUG("Loaded symlink buf"); diff --git a/src/wim.c b/src/wim.c index e4da0a26..557cda9c 100644 --- a/src/wim.c +++ b/src/wim.c @@ -209,7 +209,6 @@ int wimlib_select_image(WIMStruct *w, int image) destroy_image_metadata(imd, NULL); imd->root_dentry = NULL; imd->security_data = NULL; - imd->lgt = NULL; } } diff --git a/src/wimlib_internal.h b/src/wimlib_internal.h index 57188c40..f9a4ad8a 100644 --- a/src/wimlib_internal.h +++ b/src/wimlib_internal.h @@ -30,6 +30,8 @@ #include "util.h" struct stat; +struct hlist_head; +struct inode; #define WIM_MAGIC_LEN 8 #define WIM_GID_LEN 16 @@ -221,7 +223,7 @@ struct wim_security_data { u32 refcnt; }; -struct link_group_table; +struct inode_table; /* Metadata resource for an image. */ @@ -232,9 +234,6 @@ struct image_metadata { /* Pointer to the security data for the image. */ struct wim_security_data *security_data; - /* Hard link group table */ - struct link_group_table *lgt; - /* A pointer to the lookup table entry for this image's metadata * resource. */ struct lookup_table_entry *metadata_lte; @@ -348,12 +347,11 @@ struct capture_config { /* hardlink.c */ -struct link_group_table *new_link_group_table(size_t capacity); -int link_group_table_insert(struct dentry *dentry, - void *__table); -void free_link_group_table(struct link_group_table *table); -u64 assign_link_group_ids(struct link_group_table *table); -int fix_link_groups(struct link_group_table *table); +struct inode_table *new_inode_table(size_t capacity); +int inode_table_insert(struct dentry *dentry, void *__table); +void free_inode_table(struct inode_table *table); +u64 assign_inode_numbers(struct hlist_head *inode_list); +int fix_inodes(struct inode_table *table, struct hlist_head *inode_list); /* header.c */ @@ -429,14 +427,14 @@ u8 *write_security_data(const struct wim_security_data *sd, u8 *p); void free_security_data(struct wim_security_data *sd); /* symlink.c */ -ssize_t dentry_readlink(const struct dentry *dentry, char *buf, size_t buf_len, +ssize_t inode_readlink(const struct inode *inode, char *buf, size_t buf_len, const WIMStruct *w); extern void *make_symlink_reparse_data_buf(const char *symlink_target, size_t *len_ret); -extern int dentry_set_symlink(struct dentry *dentry, - const char *target, - struct lookup_table *lookup_table, - struct lookup_table_entry **lte_ret); +extern int inode_set_symlink(struct inode *inode, + const char *target, + struct lookup_table *lookup_table, + struct lookup_table_entry **lte_ret); /* wim.c */ extern WIMStruct *new_wim_struct();