Make lookup table use hlist
authorEric Biggers <ebiggers3@gmail.com>
Mon, 20 Aug 2012 19:39:30 +0000 (14:39 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Mon, 20 Aug 2012 19:39:30 +0000 (14:39 -0500)
src/dentry.c
src/dentry.h
src/hardlink.c
src/lookup_table.c
src/lookup_table.h
src/modify.c
src/mount.c
src/resource.c
src/symlink.c
src/wim.c
src/wimlib_internal.h

index 50351fb..98d117b 100644 (file)
@@ -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)
index 0328144..f8f0523 100644 (file)
@@ -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);
 
index 20faa55..ba4f2e1 100644 (file)
@@ -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;
 
index 66c4670..2ccb0ef 100644 (file)
@@ -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(&lte->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;
 }
 
index 7d8474f..8719814 100644 (file)
@@ -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(&lte->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,
index 41c745b..5250ff6 100644 (file)
 
 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;
 }
index edd9cd1..25b6bcd 100644 (file)
@@ -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, &lte) != 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, &lte->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;
index 49de59a..6608529 100644 (file)
@@ -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:
index 3472ed1..f16d8c2 100644 (file)
@@ -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"
index 45df365..b2ed8d9 100644 (file)
--- 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);
        }
index 3ebf205..bc7505d 100644 (file)
@@ -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);