Make WIMStructs reference-counted
[wimlib] / src / blob_table.c
index 29d44d9..1509a83 100644 (file)
@@ -34,6 +34,7 @@
 #include <unistd.h> /* for unlink()  */
 
 #include "wimlib/assert.h"
+#include "wimlib/bitops.h"
 #include "wimlib/blob_table.h"
 #include "wimlib/encoding.h"
 #include "wimlib/endianness.h"
 struct blob_table {
        struct hlist_head *array;
        size_t num_blobs;
-       size_t capacity;
+       size_t mask; /* capacity - 1; capacity is a power of 2  */
 };
 
+static size_t
+next_power_of_2(size_t n)
+{
+       if (n <= 1)
+               return 1;
+       return (size_t)1 << (1 + flsw(n - 1));
+}
+
 struct blob_table *
 new_blob_table(size_t capacity)
 {
        struct blob_table *table;
        struct hlist_head *array;
 
+       capacity = next_power_of_2(capacity);
+
        table = MALLOC(sizeof(struct blob_table));
        if (table == NULL)
                goto oom;
@@ -69,7 +80,7 @@ new_blob_table(size_t capacity)
        }
 
        table->num_blobs = 0;
-       table->capacity = capacity;
+       table->mask = capacity - 1;
        table->array = array;
        return table;
 
@@ -99,7 +110,7 @@ free_blob_table(struct blob_table *table)
 struct blob_descriptor *
 new_blob_descriptor(void)
 {
-       BUILD_BUG_ON(BLOB_NONEXISTENT != 0);
+       STATIC_ASSERT(BLOB_NONEXISTENT == 0);
        return CALLOC(1, sizeof(struct blob_descriptor));
 }
 
@@ -124,8 +135,8 @@ clone_blob_descriptor(const struct blob_descriptor *old)
 #endif
 #ifdef WITH_FUSE
        case BLOB_IN_STAGING_FILE:
-               BUILD_BUG_ON((void*)&old->file_on_disk !=
-                            (void*)&old->staging_file_name);
+               STATIC_ASSERT((void*)&old->file_on_disk ==
+                             (void*)&old->staging_file_name);
 #endif
                new->file_on_disk = TSTRDUP(old->file_on_disk);
                if (new->file_on_disk == NULL)
@@ -151,15 +162,24 @@ out_free:
        return NULL;
 }
 
-static void
+/* Release a blob descriptor from its location, if any, and set its new location
+ * to BLOB_NONEXISTENT.  */
+void
 blob_release_location(struct blob_descriptor *blob)
 {
        switch (blob->blob_location) {
-       case BLOB_IN_WIM:
+       case BLOB_IN_WIM: {
+               struct wim_resource_descriptor *rdesc = blob->rdesc;
+
                list_del(&blob->rdesc_node);
-               if (list_empty(&blob->rdesc->blob_list))
-                       FREE(blob->rdesc);
+               if (list_empty(&rdesc->blob_list)) {
+                       wimlib_assert(rdesc->wim->refcnt > 0);
+                       if (--rdesc->wim->refcnt == 0)
+                               finalize_wim_struct(rdesc->wim);
+                       FREE(rdesc);
+               }
                break;
+       }
        case BLOB_IN_FILE_ON_DISK:
 #ifdef __WIN32__
        case BLOB_IN_WINNT_FILE_ON_DISK:
@@ -167,12 +187,12 @@ blob_release_location(struct blob_descriptor *blob)
 #endif
 #ifdef WITH_FUSE
        case BLOB_IN_STAGING_FILE:
-               BUILD_BUG_ON((void*)&blob->file_on_disk !=
-                            (void*)&blob->staging_file_name);
+               STATIC_ASSERT((void*)&blob->file_on_disk ==
+                             (void*)&blob->staging_file_name);
 #endif
        case BLOB_IN_ATTACHED_BUFFER:
-               BUILD_BUG_ON((void*)&blob->file_on_disk !=
-                            (void*)&blob->attached_buffer);
+               STATIC_ASSERT((void*)&blob->file_on_disk ==
+                             (void*)&blob->attached_buffer);
                FREE(blob->file_on_disk);
                break;
 #ifdef WITH_NTFS_3G
@@ -182,6 +202,7 @@ blob_release_location(struct blob_descriptor *blob)
                break;
 #endif
        }
+       blob->blob_location = BLOB_NONEXISTENT;
 }
 
 void
@@ -287,7 +308,7 @@ blob_decrement_num_opened_fds(struct blob_descriptor *blob)
 static void
 blob_table_insert_raw(struct blob_table *table, struct blob_descriptor *blob)
 {
-       size_t i = blob->hash_short % table->capacity;
+       size_t i = blob->hash_short & table->mask;
 
        hlist_add_head(&blob->hash_list, &table->array[i]);
 }
@@ -301,14 +322,14 @@ enlarge_blob_table(struct blob_table *table)
        struct hlist_node *tmp;
        size_t i;
 
-       old_capacity = table->capacity;
+       old_capacity = table->mask + 1;
        new_capacity = old_capacity * 2;
        new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
        if (new_array == NULL)
                return;
        old_array = table->array;
        table->array = new_array;
-       table->capacity = new_capacity;
+       table->mask = new_capacity - 1;
 
        for (i = 0; i < old_capacity; i++)
                hlist_for_each_entry_safe(blob, tmp, &old_array[i], hash_list)
@@ -321,7 +342,7 @@ void
 blob_table_insert(struct blob_table *table, struct blob_descriptor *blob)
 {
        blob_table_insert_raw(table, blob);
-       if (++table->num_blobs > table->capacity)
+       if (table->num_blobs++ > table->mask)
                enlarge_blob_table(table);
 }
 
@@ -344,7 +365,7 @@ lookup_blob(const struct blob_table *table, const u8 *hash)
        size_t i;
        struct blob_descriptor *blob;
 
-       i = load_size_t_unaligned(hash) % table->capacity;
+       i = load_size_t_unaligned(hash) & table->mask;
        hlist_for_each_entry(blob, &table->array[i], hash_list)
                if (hashes_equal(hash, blob->hash))
                        return blob;
@@ -361,7 +382,7 @@ for_blob_in_table(struct blob_table *table,
        struct hlist_node *tmp;
        int ret;
 
-       for (size_t i = 0; i < table->capacity; i++) {
+       for (size_t i = 0; i <= table->mask; i++) {
                hlist_for_each_entry_safe(blob, tmp, &table->array[i],
                                          hash_list)
                {
@@ -392,7 +413,12 @@ cmp_blobs_by_sequential_order(const void *p1, const void *p2)
 
        v = (int)blob1->blob_location - (int)blob2->blob_location;
 
-       /* Different locations?  */
+       /* Different locations?  Note: "unsafe compaction mode" requires that
+        * blobs in WIMs sort before all others.  For the logic here to ensure
+        * this, BLOB_IN_WIM must have the lowest value among all defined
+        * blob_locations.  Statically verify that the enum values haven't
+        * changed.  */
+       STATIC_ASSERT(BLOB_NONEXISTENT == 0 && BLOB_IN_WIM == 1);
        if (v)
                return v;
 
@@ -401,22 +427,39 @@ cmp_blobs_by_sequential_order(const void *p1, const void *p2)
                wim1 = blob1->rdesc->wim;
                wim2 = blob2->rdesc->wim;
 
-               /* Different (possibly split) WIMs?  */
+               /* Different WIM files?  */
                if (wim1 != wim2) {
+
+                       /* Resources from the WIM file currently being compacted
+                        * (if any) must always sort first.  */
+                       v = (int)wim2->being_compacted - (int)wim1->being_compacted;
+                       if (v)
+                               return v;
+
+                       /* Different split WIMs?  */
                        v = cmp_guids(wim1->hdr.guid, wim2->hdr.guid);
                        if (v)
                                return v;
+
+                       /* Different part numbers in the same split WIM?  */
+                       v = (int)wim1->hdr.part_number - (int)wim2->hdr.part_number;
+                       if (v)
+                               return v;
+
+                       /* Probably two WIMStructs for the same on-disk file.
+                        * Just sort by pointer.  */
+                       return wim1 < wim2 ? -1 : 1;
                }
 
-               /* Different part numbers in the same WIM?  */
-               v = (int)wim1->hdr.part_number - (int)wim2->hdr.part_number;
-               if (v)
-                       return v;
+               /* Same WIM file  */
 
+               /* Sort by increasing resource offset  */
                if (blob1->rdesc->offset_in_wim != blob2->rdesc->offset_in_wim)
                        return cmp_u64(blob1->rdesc->offset_in_wim,
                                       blob2->rdesc->offset_in_wim);
 
+               /* The blobs are in the same solid resource.  Sort by increasing
+                * offset in the resource.  */
                return cmp_u64(blob1->offset_in_res, blob2->offset_in_res);
 
        case BLOB_IN_FILE_ON_DISK:
@@ -627,22 +670,12 @@ do_load_solid_info(WIMStruct *wim, struct wim_resource_descriptor **rdescs,
 
                /* Compression format numbers must be the same as in
                 * WIMGAPI to be compatible here.  */
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_NONE != 0);
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_XPRESS != 1);
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_LZX != 2);
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_LZMS != 3);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_NONE == 0);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_XPRESS == 1);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_LZX == 2);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_LZMS == 3);
                rdesc->compression_type = le32_to_cpu(hdr.compression_format);
-
                rdesc->chunk_size = le32_to_cpu(hdr.chunk_size);
-
-               DEBUG("Solid resource %zu/%zu: %"PRIu64" => %"PRIu64" "
-                     "(%"TS"/%"PRIu32") @ +%"PRIu64"",
-                     i + 1, num_rdescs,
-                     rdesc->uncompressed_size,
-                     rdesc->size_in_wim,
-                     wimlib_get_compression_type_string(rdesc->compression_type),
-                     rdesc->chunk_size,
-                     rdesc->offset_in_wim);
        }
        return 0;
 }
@@ -684,6 +717,8 @@ load_solid_info(WIMStruct *wim,
        if (ret)
                goto out_free_rdescs;
 
+       wim->refcnt += num_rdescs;
+
        *rdescs_ret = rdescs;
        *num_rdescs_ret = num_rdescs;
        return 0;
@@ -724,9 +759,12 @@ static void
 free_solid_rdescs(struct wim_resource_descriptor **rdescs, size_t num_rdescs)
 {
        if (rdescs) {
-               for (size_t i = 0; i < num_rdescs; i++)
-                       if (list_empty(&rdescs[i]->blob_list))
+               for (size_t i = 0; i < num_rdescs; i++) {
+                       if (list_empty(&rdescs[i]->blob_list)) {
+                               rdescs[i]->wim->refcnt--;
                                FREE(rdescs[i]);
+                       }
+               }
                FREE(rdescs);
        }
 }
@@ -859,8 +897,6 @@ read_blob_table(WIMStruct *wim)
        struct wim_resource_descriptor **cur_solid_rdescs = NULL;
        size_t cur_num_solid_rdescs = 0;
 
-       DEBUG("Reading blob table.");
-
        /* Calculate the number of entries in the blob table.  */
        num_entries = wim->hdr.blob_table_reshdr.uncompressed_size /
                      sizeof(struct blob_descriptor_disk);
@@ -872,7 +908,7 @@ read_blob_table(WIMStruct *wim)
 
        /* Allocate a hash table to map SHA-1 message digests into blob
         * descriptors.  This is the in-memory "blob table".  */
-       table = new_blob_table(num_entries * 2 + 1);
+       table = new_blob_table(num_entries);
        if (!table)
                goto oom;
 
@@ -887,13 +923,6 @@ read_blob_table(WIMStruct *wim)
                /* Get the resource header  */
                get_wim_reshdr(&disk_entry->reshdr, &reshdr);
 
-               DEBUG("reshdr: size_in_wim=%"PRIu64", "
-                     "uncompressed_size=%"PRIu64", "
-                     "offset_in_wim=%"PRIu64", "
-                     "flags=0x%02x",
-                     reshdr.size_in_wim, reshdr.uncompressed_size,
-                     reshdr.offset_in_wim, reshdr.flags);
-
                /* Ignore SOLID flag if it isn't supposed to be used in this WIM
                 * version.  */
                if (wim->hdr.wim_version == WIM_VERSION_DEFAULT)
@@ -967,6 +996,7 @@ read_blob_table(WIMStruct *wim)
                                goto oom;
 
                        wim_reshdr_to_desc_and_blob(&reshdr, wim, rdesc, cur_blob);
+                       wim->refcnt++;
                }
 
                /* cur_blob is now a blob bound to a resource.  */
@@ -1038,11 +1068,6 @@ read_blob_table(WIMStruct *wim)
                         * this overrides the actual locations of the metadata
                         * resources themselves in the WIM file as well as any
                         * information written in the XML data.  */
-                       DEBUG("Found metadata resource for image %"PRIu32" at "
-                             "offset %"PRIu64".",
-                             image_index + 1,
-                             reshdr.offset_in_wim);
-
                        wim->image_metadata[image_index++]->metadata_blob = cur_blob;
                } else {
                        /* Blob table entry for a non-metadata blob.  */
@@ -1094,7 +1119,6 @@ read_blob_table(WIMStruct *wim)
                        num_wrong_part_blobs);
        }
 
-       DEBUG("Done reading blob table.");
        wim->blob_table = table;
        ret = 0;
        goto out_free_buf;
@@ -1154,9 +1178,6 @@ write_blob_table_from_blob_list(struct list_head *blob_list,
                }
        }
 
-       DEBUG("Writing WIM blob table (size=%zu, offset=%"PRIu64")",
-             table_size, out_fd->offset);
-
        table_buf = MALLOC(table_size);
        if (table_buf == NULL) {
                ERROR("Failed to allocate %zu bytes for temporary blob table",
@@ -1215,7 +1236,6 @@ write_blob_table_from_blob_list(struct list_head *blob_list,
                                             NULL,
                                             write_resource_flags);
        FREE(table_buf);
-       DEBUG("ret=%d", ret);
        return ret;
 }