X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fblob_table.c;h=96290e8de777afef6137f0e4d45433d5823e6e67;hp=e9766b5f6419db7d1f35c4b79815a4169954a6ed;hb=cf13fe6161a69db6cbf17637b60c978fd746078a;hpb=8214debe2f127bc6d56407c1fb4bee194af83478 diff --git a/src/blob_table.c b/src/blob_table.c index e9766b5f..96290e8d 100644 --- a/src/blob_table.c +++ b/src/blob_table.c @@ -34,6 +34,7 @@ #include /* for unlink() */ #include "wimlib/assert.h" +#include "wimlib/bitops.h" #include "wimlib/blob_table.h" #include "wimlib/encoding.h" #include "wimlib/endianness.h" @@ -49,15 +50,25 @@ 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) @@ -167,12 +178,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 @@ -287,7 +298,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 +312,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 +332,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 +355,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 +372,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 +403,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 +417,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,10 +660,10 @@ 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); } @@ -860,7 +893,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;