From b0b65688a9fb875e464457ee6449b8793f0f8a03 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Mon, 20 Aug 2012 14:39:30 -0500 Subject: [PATCH] Make lookup table use hlist --- src/dentry.c | 38 ++++------ src/dentry.h | 3 +- src/hardlink.c | 22 +++++- src/lookup_table.c | 166 ++++++++++++++---------------------------- src/lookup_table.h | 18 +++-- src/modify.c | 7 +- src/mount.c | 28 ++++++- src/resource.c | 2 +- src/symlink.c | 19 +++++ src/wim.c | 4 +- src/wimlib_internal.h | 2 +- 11 files changed, 156 insertions(+), 153 deletions(-) diff --git a/src/dentry.c b/src/dentry.c index 50351fb0..98d117b9 100644 --- a/src/dentry.c +++ b/src/dentry.c @@ -579,24 +579,20 @@ struct dentry *clone_dentry(struct dentry *old) return new; } -/* Arguments for do_free_dentry(). */ -struct free_dentry_args { - struct lookup_table *lookup_table; - bool lt_decrement_refcnt; -}; - /* * This function is passed as an argument to for_dentry_in_tree_depth() in order * to free a directory tree. __args is a pointer to a `struct free_dentry_args'. */ -static int do_free_dentry(struct dentry *dentry, void *__args) +static int do_free_dentry(struct dentry *dentry, void *__lookup_table) { - struct free_dentry_args *args = (struct free_dentry_args*)__args; - - if (args->lt_decrement_refcnt && !dentry_is_directory(dentry)) { - wimlib_assert(!dentry->resolved); - lookup_table_decrement_refcnt(args->lookup_table, - dentry->hash); + struct lookup_table *lookup_table = __lookup_table; + if (lookup_table) { + struct lookup_table_entry *lte; + if (dentry->resolved) + lte = dentry->lte; + else + lte = __lookup_resource(lookup_table, dentry->hash); + lte_decrement_refcnt(lte, lookup_table); } wimlib_assert(dentry->refcnt != 0); @@ -609,20 +605,16 @@ static int do_free_dentry(struct dentry *dentry, void *__args) * Unlinks and frees a dentry tree. * * @root: The root of the tree. - * @lookup_table: The lookup table for dentries. - * @decrement_refcnt: True if the dentries in the tree are to have their - * reference counts in the lookup table decremented. + * @lookup_table: The lookup table for dentries. If non-NULL, the + * reference counts in the lookup table for the lookup + * table entries corresponding to the dentries will be + * decremented. */ -void free_dentry_tree(struct dentry *root, struct lookup_table *lookup_table, - bool lt_decrement_refcnt) +void free_dentry_tree(struct dentry *root, struct lookup_table *lookup_table) { if (!root || !root->parent) return; - - struct free_dentry_args args; - args.lookup_table = lookup_table; - args.lt_decrement_refcnt = lt_decrement_refcnt; - for_dentry_in_tree_depth(root, do_free_dentry, &args); + for_dentry_in_tree_depth(root, do_free_dentry, lookup_table); } int increment_dentry_refcnt(struct dentry *dentry, void *ignore) diff --git a/src/dentry.h b/src/dentry.h index 03281447..f8f05235 100644 --- a/src/dentry.h +++ b/src/dentry.h @@ -329,8 +329,7 @@ extern void free_dentry(struct dentry *dentry); extern void put_dentry(struct dentry *dentry); extern struct dentry *clone_dentry(struct dentry *old); extern void free_dentry_tree(struct dentry *root, - struct lookup_table *lookup_table, - bool lt_decrement_refcnt); + struct lookup_table *lookup_table); extern int increment_dentry_refcnt(struct dentry *dentry, void *ignore); extern int decrement_dentry_refcnt(struct dentry *dentry, void *ignore); diff --git a/src/hardlink.c b/src/hardlink.c index 20faa555..ba4f2e16 100644 --- a/src/hardlink.c +++ b/src/hardlink.c @@ -1,3 +1,22 @@ +/* + * Copyright (C) 2012 Eric Biggers + * + * This file is part of wimlib, a library for working with WIM files. + * + * wimlib is free software; you can redistribute it and/or modify it under the + * terms of the GNU Lesser General Public License as published by the Free + * Software Foundation; either version 2.1 of the License, or (at your option) + * any later version. + * + * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more + * details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with wimlib; if not, see http://www.gnu.org/licenses/. + */ + #include "wimlib_internal.h" #include "dentry.h" #include "list.h" @@ -59,8 +78,9 @@ err: * we keep a linked list of the single dentries, and assign them hard link group * IDs later. */ -int link_group_table_insert(struct dentry *dentry, struct link_group_table *table) +int link_group_table_insert(struct dentry *dentry, void *__table) { + struct link_group_table *table = __table; size_t pos; struct link_group *group; diff --git a/src/lookup_table.c b/src/lookup_table.c index 66c46700..2ccb0ef8 100644 --- a/src/lookup_table.c +++ b/src/lookup_table.c @@ -32,7 +32,7 @@ struct lookup_table *new_lookup_table(size_t capacity) { struct lookup_table *table; - struct lookup_table_entry **array; + struct hlist_head *array; table = MALLOC(sizeof(struct lookup_table)); if (!table) @@ -70,7 +70,6 @@ struct lookup_table_entry *new_lookup_table_entry() return lte; } - void free_lookup_table_entry(struct lookup_table_entry *lte) { if (lte) { @@ -81,85 +80,50 @@ void free_lookup_table_entry(struct lookup_table_entry *lte) } } +static int do_free_lookup_table_entry(struct lookup_table_entry *entry, + void *ignore) +{ + free_lookup_table_entry(entry); + return 0; +} + + +void free_lookup_table(struct lookup_table *table) +{ + DEBUG("Freeing lookup table"); + if (table) { + if (table->array) { + for_lookup_table_entry(table, + do_free_lookup_table_entry, + NULL); + FREE(table->array); + } + FREE(table); + } +} + /* * Inserts an entry into the lookup table. * - * @lookup_table: A pointer to the lookup table. - * @entry: A pointer to the entry to insert. + * @table: A pointer to the lookup table. + * @entry: A pointer to the entry to insert. */ void lookup_table_insert(struct lookup_table *table, struct lookup_table_entry *lte) { - size_t pos; - pos = lte->hash_short % table->capacity; - lte->next = table->array[pos]; - table->array[pos] = lte; + size_t i = lte->hash_short % table->capacity; + hlist_add_head(<e->hash_list, &table->array[i]); + /* XXX Make the table grow when too many entries have been inserted. */ table->num_entries++; } -/* Unlinks a lookup table entry from the table; does not free it. */ -void lookup_table_unlink(struct lookup_table *table, - struct lookup_table_entry *lte) -{ - size_t pos; - struct lookup_table_entry *prev, *cur_entry, *next; - - pos = lte->hash_short % table->capacity; - prev = NULL; - cur_entry = table->array[pos]; - - while (cur_entry) { - next = cur_entry->next; - if (cur_entry == lte) { - if (prev) - prev->next = next; - else - table->array[pos] = next; - table->num_entries--; - return; - } - prev = cur_entry; - cur_entry = next; - } -} - -/* Decrement the reference count for the dentry having hash value @hash in the - * lookup table. The lookup table entry is unlinked and freed if there are no - * references to in remaining. */ -struct lookup_table_entry * -lookup_table_decrement_refcnt(struct lookup_table* table, const u8 hash[]) -{ - size_t pos = *(size_t*)hash % table->capacity; - struct lookup_table_entry *prev = NULL; - struct lookup_table_entry *entry = table->array[pos]; - struct lookup_table_entry *next; - while (entry) { - next = entry->next; - if (memcmp(hash, entry->hash, WIM_HASH_SIZE) == 0) { - wimlib_assert(entry->refcnt != 0); - if (--entry->refcnt == 0) { - if (entry->num_opened_fds == 0) { - free_lookup_table_entry(entry); - entry = NULL; - } - if (prev) - prev->next = next; - else - table->array[pos] = next; - break; - } - } - prev = entry; - entry = next; - } - return entry; -} - -/* Like lookup_table_decrement_refcnt(), but for when we already know the lookup - * table entry. */ +/* Decrements the reference count for the lookup table entry @lte. If its + * reference count reaches 0, it is unlinked from the lookup table. If, + * furthermore, the entry has no opened file descriptors associated with it, the + * entry is freed. */ struct lookup_table_entry * lte_decrement_refcnt(struct lookup_table_entry *lte, struct lookup_table *table) { @@ -184,18 +148,17 @@ int for_lookup_table_entry(struct lookup_table *table, int (*visitor)(struct lookup_table_entry *, void *), void *arg) { - struct lookup_table_entry *entry, *next; - size_t i; + struct lookup_table_entry *lte; + struct hlist_node *pos, *tmp; int ret; - for (i = 0; i < table->capacity; i++) { - entry = table->array[i]; - while (entry) { - next = entry->next; - ret = visitor(entry, arg); + for (size_t i = 0; i < table->capacity; i++) { + hlist_for_each_entry_safe(lte, pos, tmp, &table->array[i], + hash_list) + { + ret = visitor(lte, arg); if (ret != 0) return ret; - entry = next; } } return 0; @@ -303,23 +266,7 @@ int write_lookup_table_entry(struct lookup_table_entry *lte, void *__out) return 0; } -static int do_free_lookup_table_entry(struct lookup_table_entry *entry, - void *ignore) -{ - free_lookup_table_entry(entry); - return 0; -} -void free_lookup_table(struct lookup_table *table) -{ - if (!table) - return; - if (table->array) { - for_lookup_table_entry(table, do_free_lookup_table_entry, NULL); - FREE(table->array); - } - FREE(table); -} int zero_out_refcnts(struct lookup_table_entry *entry, void *ignore) { @@ -327,21 +274,21 @@ int zero_out_refcnts(struct lookup_table_entry *entry, void *ignore) return 0; } -int print_lookup_table_entry(struct lookup_table_entry *entry, void *ignore) +int print_lookup_table_entry(struct lookup_table_entry *lte, void *ignore) { printf("Offset = %"PRIu64" bytes\n", - entry->resource_entry.offset); + lte->resource_entry.offset); printf("Size = %"PRIu64" bytes\n", - (u64)entry->resource_entry.size); + (u64)lte->resource_entry.size); printf("Original size = %"PRIu64" bytes\n", - entry->resource_entry.original_size); - printf("Part Number = %hu\n", entry->part_number); - printf("Reference Count = %u\n", entry->refcnt); + lte->resource_entry.original_size); + printf("Part Number = %hu\n", lte->part_number); + printf("Reference Count = %u\n", lte->refcnt); printf("Hash = "); - print_hash(entry->hash); + print_hash(lte->hash); putchar('\n'); printf("Flags = "); - u8 flags = entry->resource_entry.flags; + u8 flags = lte->resource_entry.flags; if (flags & WIM_RESHDR_FLAG_COMPRESSED) fputs("WIM_RESHDR_FLAG_COMPRESSED, ", stdout); if (flags & WIM_RESHDR_FLAG_FREE) @@ -351,8 +298,8 @@ int print_lookup_table_entry(struct lookup_table_entry *entry, void *ignore) if (flags & WIM_RESHDR_FLAG_SPANNED) fputs("WIM_RESHDR_FLAG_SPANNED, ", stdout); putchar('\n'); - if (entry->file_on_disk) - printf("File on Disk = `%s'\n", entry->file_on_disk); + if (lte->file_on_disk && !lte->is_symlink) + printf("File on Disk = `%s'\n", lte->file_on_disk); putchar('\n'); return 0; } @@ -363,25 +310,24 @@ int print_lookup_table_entry(struct lookup_table_entry *entry, void *ignore) WIMLIBAPI void wimlib_print_lookup_table(WIMStruct *w) { for_lookup_table_entry(w->lookup_table, - print_lookup_table_entry, NULL); + print_lookup_table_entry, + NULL); } /* * Looks up an entry in the lookup table. */ struct lookup_table_entry * -__lookup_resource(const struct lookup_table *lookup_table, const u8 hash[]) +__lookup_resource(const struct lookup_table *table, const u8 hash[]) { - size_t pos; + size_t i; struct lookup_table_entry *lte; + struct hlist_node *pos; - pos = *(size_t*)hash % lookup_table->capacity; - lte = lookup_table->array[pos]; - while (lte) { + i = *(size_t*)hash % table->capacity; + hlist_for_each_entry(lte, pos, &table->array[i], hash_list) if (memcmp(hash, lte->hash, WIM_HASH_SIZE) == 0) return lte; - lte = lte->next; - } return NULL; } diff --git a/src/lookup_table.h b/src/lookup_table.h index 7d8474f6..87198143 100644 --- a/src/lookup_table.h +++ b/src/lookup_table.h @@ -16,7 +16,7 @@ * offsets and sizes of uncompressed or compressed file resources. It is * implemented as a hash table. */ struct lookup_table { - struct lookup_table_entry **array; + struct hlist_head *array; u64 num_entries; u64 capacity; }; @@ -34,9 +34,8 @@ struct wimlib_fd; */ struct lookup_table_entry { - /* The next struct lookup_table_entry in the hash bucket. NULL if this is the - * last one. */ - struct lookup_table_entry *next; + /* List of lookup table entries in this hash bucket */ + struct hlist_node hash_list; /* @resource_entry is read from the lookup table in the WIM * file; it says where to find the file resource in the WIM @@ -131,8 +130,13 @@ extern struct lookup_table *new_lookup_table(size_t capacity); extern void lookup_table_insert(struct lookup_table *table, struct lookup_table_entry *lte); -extern void lookup_table_unlink(struct lookup_table *table, - struct lookup_table_entry *lte); +/* Unlinks a lookup table entry from the table; does not free it. */ +static inline void lookup_table_unlink(struct lookup_table *table, + struct lookup_table_entry *lte) +{ + hlist_del(<e->hash_list); + table->num_entries--; +} extern struct lookup_table_entry * lookup_table_decrement_refcnt(struct lookup_table* table, const u8 hash[]); @@ -149,7 +153,7 @@ extern int for_lookup_table_entry(struct lookup_table *table, void *arg); extern struct lookup_table_entry * -__lookup_resource(const struct lookup_table *lookup_table, const u8 hash[]); +__lookup_resource(const struct lookup_table *table, const u8 hash[]); extern int lookup_resource(WIMStruct *w, const char *path, int lookup_flags, struct dentry **dentry_ret, diff --git a/src/modify.c b/src/modify.c index 41c745b4..5250ff6e 100644 --- a/src/modify.c +++ b/src/modify.c @@ -44,10 +44,7 @@ void destroy_image_metadata(struct image_metadata *imd,struct lookup_table *lt) { - if (lt) - free_dentry_tree(imd->root_dentry, lt, true); - else - free_dentry_tree(imd->root_dentry, NULL, false); + free_dentry_tree(imd->root_dentry, lt); free_security_data(imd->security_data); free_link_group_table(imd->lgt); @@ -564,6 +561,6 @@ out_destroy_imd: w->hdr.image_count--; return ret; out_free_dentry_tree: - free_dentry_tree(root_dentry, w->lookup_table, true); + free_dentry_tree(root_dentry, w->lookup_table); return ret; } diff --git a/src/mount.c b/src/mount.c index edd9cd1d..25b6bcd5 100644 --- a/src/mount.c +++ b/src/mount.c @@ -1422,6 +1422,7 @@ static int wimfs_symlink(const char *to, const char *from) dentry->attributes = FILE_ATTRIBUTE_REPARSE_POINT; dentry->reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK; + dentry->hard_link = next_link_group_id++; if (dentry_set_symlink(dentry, to, w->lookup_table, <e) != 0) goto out_free_dentry; @@ -1583,6 +1584,24 @@ static struct fuse_operations wimfs_operations = { }; +static int check_lte_refcnt(struct lookup_table_entry *lte, void *ignore) +{ + size_t lte_group_size = 0; + struct list_head *cur; + list_for_each(cur, <e->lte_group_list) + lte_group_size++; + if (lte_group_size > lte->refcnt) { +#ifdef ENABLE_ERROR_MESSAGES + ERROR("The following lookup table entry has a reference count " + "of %u, but", lte->refcnt); + ERROR("We found %u references to it", lte_group_size); + print_lookup_table_entry(lte, NULL); +#endif + return WIMLIB_ERR_INVALID_DENTRY; + } + return 0; +} + /* Mounts a WIM file. */ WIMLIBAPI int wimlib_mount(WIMStruct *wim, int image, const char *dir, int flags) @@ -1611,6 +1630,10 @@ WIMLIBAPI int wimlib_mount(WIMStruct *wim, int image, const char *dir, for_dentry_in_tree(wim_root_dentry(wim), dentry_resolve_ltes, wim->lookup_table); + ret = for_lookup_table_entry(wim->lookup_table, check_lte_refcnt, NULL); + if (ret != 0) + return ret; + if (flags & WIMLIB_MOUNT_FLAG_READWRITE) wim_get_current_image_metadata(wim)->modified = true; @@ -1765,7 +1788,10 @@ WIMLIBAPI int wimlib_unmount(const char *dir, int flags) * filesystem daemon has crashed or failed for some reason. * * XXX come up with some method to determine if the filesystem - * daemon has really crashed or not. */ + * daemon has really crashed or not. + * + * XXX Idea: have mount daemon write its PID into the WIM file header? + * */ gettimeofday(&now, NULL); timeout.tv_sec = now.tv_sec + 600; diff --git a/src/resource.c b/src/resource.c index 49de59a4..6608529c 100644 --- a/src/resource.c +++ b/src/resource.c @@ -1025,7 +1025,7 @@ int read_metadata_resource(FILE *fp, int wim_ctype, struct image_metadata *imd) out_free_lgt: free_link_group_table(lgt); out_free_dentry_tree: - free_dentry_tree(dentry, NULL, false); + free_dentry_tree(dentry, NULL); out_free_security_data: free_security_data(sd); out_free_buf: diff --git a/src/symlink.c b/src/symlink.c index 3472ed11..f16d8c22 100644 --- a/src/symlink.c +++ b/src/symlink.c @@ -1,3 +1,22 @@ +/* + * Copyright (C) 2012 Eric Biggers + * + * This file is part of wimlib, a library for working with WIM files. + * + * wimlib is free software; you can redistribute it and/or modify it under the + * terms of the GNU Lesser General Public License as published by the Free + * Software Foundation; either version 2.1 of the License, or (at your option) + * any later version. + * + * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more + * details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with wimlib; if not, see http://www.gnu.org/licenses/. + */ + #include "dentry.h" #include "io.h" #include "lookup_table.h" diff --git a/src/wim.c b/src/wim.c index 45df3657..b2ed8d98 100644 --- a/src/wim.c +++ b/src/wim.c @@ -540,7 +540,7 @@ WIMLIBAPI int wimlib_open_wim(const char *wim_file, int flags, * closes all files associated with the WIMStruct. */ WIMLIBAPI void wimlib_free(WIMStruct *w) { - uint i; + DEBUG("Freeing WIMStruct"); if (!w) return; @@ -555,7 +555,7 @@ WIMLIBAPI void wimlib_free(WIMStruct *w) FREE(w->xml_data); free_wim_info(w->wim_info); if (w->image_metadata) { - for (i = 0; i < w->hdr.image_count; i++) + for (uint i = 0; i < w->hdr.image_count; i++) destroy_image_metadata(&w->image_metadata[i], NULL); FREE(w->image_metadata); } diff --git a/src/wimlib_internal.h b/src/wimlib_internal.h index 3ebf205c..bc7505d2 100644 --- a/src/wimlib_internal.h +++ b/src/wimlib_internal.h @@ -322,7 +322,7 @@ static inline void print_hash(const u8 hash[]) struct link_group_table *new_link_group_table(u64 capacity); int link_group_table_insert(struct dentry *dentry, - struct link_group_table *table); + void *__table); void free_link_group_table(struct link_group_table *table); u64 assign_link_groups(struct link_group_table *table); int link_groups_free_duplicate_data(struct link_group_table *table); -- 2.43.0