wimlib.net Git - wimlib/blob - src/lookup_table.c

   1 /*
   2  * lookup_table.c
   3  *
   4  * Lookup table, implemented as a hash table, that maps SHA1 message digests to
   5  * data streams.
   6  */
   7
   8 /*
   9  * Copyright (C) 2012, 2013 Eric Biggers
  10  *
  11  * This file is part of wimlib, a library for working with WIM files.
  12  *
  13  * wimlib is free software; you can redistribute it and/or modify it under the
  14  * terms of the GNU General Public License as published by the Free
  15  * Software Foundation; either version 3 of the License, or (at your option)
  16  * any later version.
  17  *
  18  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
  19  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  20  * A PARTICULAR PURPOSE. See the GNU General Public License for more
  21  * details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with wimlib; if not, see http://www.gnu.org/licenses/.
  25  */
  26
  27 #ifdef HAVE_CONFIG_H
  28 #  include "config.h"
  29 #endif
  30
  31 #include "wimlib/buffer_io.h"
  32 #include "wimlib/error.h"
  33 #include "wimlib/file_io.h"
  34 #include "wimlib/lookup_table.h"
  35 #include "wimlib/metadata.h"
  36 #include "wimlib/paths.h"
  37 #include "wimlib/resource.h"
  38 #include "wimlib/util.h"
  39
  40 #include <errno.h>
  41 #include <stdlib.h>
  42 #ifdef WITH_FUSE
  43 #  include <unistd.h> /* for unlink() */
  44 #endif
  45
  46 struct wim_lookup_table *
  47 new_lookup_table(size_t capacity)
  48 {
  49         struct wim_lookup_table *table;
  50         struct hlist_head *array;
  51
  52         table = CALLOC(1, sizeof(struct wim_lookup_table));
  53         if (table) {
  54                 array = CALLOC(capacity, sizeof(array[0]));
  55                 if (array) {
  56                         table->num_entries = 0;
  57                         table->capacity = capacity;
  58                         table->array = array;
  59                 } else {
  60                         FREE(table);
  61                         table = NULL;
  62                         ERROR("Failed to allocate memory for lookup table "
  63                               "with capacity %zu", capacity);
  64                 }
  65         }
  66         return table;
  67 }
  68
  69 struct wim_lookup_table_entry *
  70 new_lookup_table_entry(void)
  71 {
  72         struct wim_lookup_table_entry *lte;
  73
  74         lte = CALLOC(1, sizeof(struct wim_lookup_table_entry));
  75         if (lte) {
  76                 lte->part_number  = 1;
  77                 lte->refcnt       = 1;
  78         } else {
  79                 ERROR("Out of memory (tried to allocate %zu bytes for "
  80                       "lookup table entry)",
  81                       sizeof(struct wim_lookup_table_entry));
  82         }
  83         return lte;
  84 }
  85
  86 struct wim_lookup_table_entry *
  87 clone_lookup_table_entry(const struct wim_lookup_table_entry *old)
  88 {
  89         struct wim_lookup_table_entry *new;
  90
  91         new = MALLOC(sizeof(*new));
  92         if (!new)
  93                 return NULL;
  94
  95         memcpy(new, old, sizeof(*old));
  96         new->extracted_file = NULL;
  97         switch (new->resource_location) {
  98 #ifdef __WIN32__
  99         case RESOURCE_WIN32:
 100         case RESOURCE_WIN32_ENCRYPTED:
 101 #else
 102         case RESOURCE_IN_FILE_ON_DISK:
 103 #endif
 104 #ifdef WITH_FUSE
 105         case RESOURCE_IN_STAGING_FILE:
 106                 BUILD_BUG_ON((void*)&old->file_on_disk !=
 107                              (void*)&old->staging_file_name);
 108 #endif
 109                 new->file_on_disk = TSTRDUP(old->file_on_disk);
 110                 if (!new->file_on_disk)
 111                         goto out_free;
 112                 break;
 113         case RESOURCE_IN_ATTACHED_BUFFER:
 114                 new->attached_buffer = MALLOC(wim_resource_size(old));
 115                 if (!new->attached_buffer)
 116                         goto out_free;
 117                 memcpy(new->attached_buffer, old->attached_buffer,
 118                        wim_resource_size(old));
 119                 break;
 120 #ifdef WITH_NTFS_3G
 121         case RESOURCE_IN_NTFS_VOLUME:
 122                 if (old->ntfs_loc) {
 123                         struct ntfs_location *loc;
 124                         loc = MALLOC(sizeof(*loc));
 125                         if (!loc)
 126                                 goto out_free;
 127                         memcpy(loc, old->ntfs_loc, sizeof(*loc));
 128                         loc->path = NULL;
 129                         loc->stream_name = NULL;
 130                         new->ntfs_loc = loc;
 131                         loc->path = STRDUP(old->ntfs_loc->path);
 132                         if (!loc->path)
 133                                 goto out_free;
 134                         loc->stream_name = MALLOC((loc->stream_name_nchars + 1) * 2);
 135                         if (!loc->stream_name)
 136                                 goto out_free;
 137                         memcpy(loc->stream_name,
 138                                old->ntfs_loc->stream_name,
 139                                (loc->stream_name_nchars + 1) * 2);
 140                 }
 141                 break;
 142 #endif
 143         default:
 144                 break;
 145         }
 146         return new;
 147 out_free:
 148         free_lookup_table_entry(new);
 149         return NULL;
 150 }
 151
 152 void
 153 free_lookup_table_entry(struct wim_lookup_table_entry *lte)
 154 {
 155         if (lte) {
 156                 switch (lte->resource_location) {
 157         #ifdef __WIN32__
 158                 case RESOURCE_WIN32:
 159                 case RESOURCE_WIN32_ENCRYPTED:
 160         #else
 161                 case RESOURCE_IN_FILE_ON_DISK:
 162         #endif
 163         #ifdef WITH_FUSE
 164                 case RESOURCE_IN_STAGING_FILE:
 165                         BUILD_BUG_ON((void*)&lte->file_on_disk !=
 166                                      (void*)&lte->staging_file_name);
 167         #endif
 168                 case RESOURCE_IN_ATTACHED_BUFFER:
 169                         BUILD_BUG_ON((void*)&lte->file_on_disk !=
 170                                      (void*)&lte->attached_buffer);
 171                         FREE(lte->file_on_disk);
 172                         break;
 173 #ifdef WITH_NTFS_3G
 174                 case RESOURCE_IN_NTFS_VOLUME:
 175                         if (lte->ntfs_loc) {
 176                                 FREE(lte->ntfs_loc->path);
 177                                 FREE(lte->ntfs_loc->stream_name);
 178                                 FREE(lte->ntfs_loc);
 179                         }
 180                         break;
 181 #endif
 182                 default:
 183                         break;
 184                 }
 185                 FREE(lte);
 186         }
 187 }
 188
 189 static int
 190 do_free_lookup_table_entry(struct wim_lookup_table_entry *entry, void *ignore)
 191 {
 192         free_lookup_table_entry(entry);
 193         return 0;
 194 }
 195
 196
 197 void
 198 free_lookup_table(struct wim_lookup_table *table)
 199 {
 200         DEBUG2("Freeing lookup table");
 201         if (table) {
 202                 if (table->array) {
 203                         for_lookup_table_entry(table,
 204                                                do_free_lookup_table_entry,
 205                                                NULL);
 206                         FREE(table->array);
 207                 }
 208                 FREE(table);
 209         }
 210 }
 211
 212 /*
 213  * Inserts an entry into the lookup table.
 214  *
 215  * @table:      A pointer to the lookup table.
 216  * @lte:        A pointer to the entry to insert.
 217  */
 218 void
 219 lookup_table_insert(struct wim_lookup_table *table,
 220                     struct wim_lookup_table_entry *lte)
 221 {
 222         size_t i = lte->hash_short % table->capacity;
 223         hlist_add_head(&lte->hash_list, &table->array[i]);
 224
 225         /* XXX Make the table grow when too many entries have been inserted. */
 226         table->num_entries++;
 227 }
 228
 229 static void
 230 finalize_lte(struct wim_lookup_table_entry *lte)
 231 {
 232         #ifdef WITH_FUSE
 233         if (lte->resource_location == RESOURCE_IN_STAGING_FILE) {
 234                 unlink(lte->staging_file_name);
 235                 list_del(&lte->unhashed_list);
 236         }
 237         #endif
 238         free_lookup_table_entry(lte);
 239 }
 240
 241 /* Decrements the reference count for the lookup table entry @lte.  If its
 242  * reference count reaches 0, it is unlinked from the lookup table.  If,
 243  * furthermore, the entry has no opened file descriptors associated with it, the
 244  * entry is freed.  */
 245 void
 246 lte_decrement_refcnt(struct wim_lookup_table_entry *lte,
 247                      struct wim_lookup_table *table)
 248 {
 249         wimlib_assert(lte != NULL);
 250         wimlib_assert(lte->refcnt != 0);
 251         if (--lte->refcnt == 0) {
 252                 if (lte->unhashed)
 253                         list_del(&lte->unhashed_list);
 254                 else
 255                         lookup_table_unlink(table, lte);
 256         #ifdef WITH_FUSE
 257                 if (lte->num_opened_fds == 0)
 258         #endif
 259                         finalize_lte(lte);
 260         }
 261 }
 262
 263 #ifdef WITH_FUSE
 264 void
 265 lte_decrement_num_opened_fds(struct wim_lookup_table_entry *lte)
 266 {
 267         if (lte->num_opened_fds != 0)
 268                 if (--lte->num_opened_fds == 0 && lte->refcnt == 0)
 269                         finalize_lte(lte);
 270 }
 271 #endif
 272
 273 /* Calls a function on all the entries in the WIM lookup table.  Stop early and
 274  * return nonzero if any call to the function returns nonzero. */
 275 int
 276 for_lookup_table_entry(struct wim_lookup_table *table,
 277                        int (*visitor)(struct wim_lookup_table_entry *, void *),
 278                        void *arg)
 279 {
 280         struct wim_lookup_table_entry *lte;
 281         struct hlist_node *pos, *tmp;
 282         int ret;
 283
 284         for (size_t i = 0; i < table->capacity; i++) {
 285                 hlist_for_each_entry_safe(lte, pos, tmp, &table->array[i],
 286                                           hash_list)
 287                 {
 288                         wimlib_assert2(!(lte->resource_entry.flags & WIM_RESHDR_FLAG_METADATA));
 289                         ret = visitor(lte, arg);
 290                         if (ret)
 291                                 return ret;
 292                 }
 293         }
 294         return 0;
 295 }
 296
 297 int
 298 cmp_streams_by_wim_position(const void *p1, const void *p2)
 299 {
 300         const struct wim_lookup_table_entry *lte1, *lte2;
 301         lte1 = *(const struct wim_lookup_table_entry**)p1;
 302         lte2 = *(const struct wim_lookup_table_entry**)p2;
 303         if (lte1->resource_entry.offset < lte2->resource_entry.offset)
 304                 return -1;
 305         else if (lte1->resource_entry.offset > lte2->resource_entry.offset)
 306                 return 1;
 307         else
 308                 return 0;
 309 }
 310
 311
 312 static int
 313 add_lte_to_array(struct wim_lookup_table_entry *lte,
 314                  void *_pp)
 315 {
 316         struct wim_lookup_table_entry ***pp = _pp;
 317         *(*pp)++ = lte;
 318         return 0;
 319 }
 320
 321 /* Iterate through the lookup table entries, but first sort them by stream
 322  * offset in the WIM.  Caution: this is intended to be used when the stream
 323  * offset field has actually been set. */
 324 int
 325 for_lookup_table_entry_pos_sorted(struct wim_lookup_table *table,
 326                                   int (*visitor)(struct wim_lookup_table_entry *,
 327                                                  void *),
 328                                   void *arg)
 329 {
 330         struct wim_lookup_table_entry **lte_array, **p;
 331         size_t num_streams = table->num_entries;
 332         int ret;
 333
 334         lte_array = MALLOC(num_streams * sizeof(lte_array[0]));
 335         if (!lte_array)
 336                 return WIMLIB_ERR_NOMEM;
 337         p = lte_array;
 338         for_lookup_table_entry(table, add_lte_to_array, &p);
 339
 340         wimlib_assert(p == lte_array + num_streams);
 341
 342         qsort(lte_array, num_streams, sizeof(lte_array[0]),
 343               cmp_streams_by_wim_position);
 344         ret = 0;
 345         for (size_t i = 0; i < num_streams; i++) {
 346                 ret = visitor(lte_array[i], arg);
 347                 if (ret)
 348                         break;
 349         }
 350         FREE(lte_array);
 351         return ret;
 352 }
 353
 354
 355 /* Size of each lookup table entry in the WIM file. */
 356 #define WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE 50
 357
 358 /*
 359  * Reads the lookup table from a WIM file.
 360  *
 361  * Saves lookup table entries for non-metadata streams in a hash table, and
 362  * saves the metadata entry for each image in a special per-image location (the
 363  * image_metadata array).
 364  */
 365 int
 366 read_lookup_table(WIMStruct *w)
 367 {
 368         int ret;
 369         size_t num_entries;
 370         struct wim_lookup_table *table;
 371         struct wim_lookup_table_entry *cur_entry, *duplicate_entry;
 372         u8 table_buf[(BUFFER_SIZE / WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE) *
 373                         WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
 374         const u8 *p;
 375         off_t offset;
 376         size_t buf_entries_remaining;
 377
 378         DEBUG("Reading lookup table: offset %"PRIu64", size %"PRIu64"",
 379               w->hdr.lookup_table_res_entry.offset,
 380               w->hdr.lookup_table_res_entry.original_size);
 381
 382         if (resource_is_compressed(&w->hdr.lookup_table_res_entry)) {
 383                 ERROR("Didn't expect a compressed lookup table!");
 384                 ERROR("Ask the author to implement support for this.");
 385                 return WIMLIB_ERR_COMPRESSED_LOOKUP_TABLE;
 386         }
 387
 388         num_entries = w->hdr.lookup_table_res_entry.size /
 389                       WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE;
 390         table = new_lookup_table(num_entries * 2 + 1);
 391         if (!table)
 392                 return WIMLIB_ERR_NOMEM;
 393
 394         w->current_image = 0;
 395         offset = w->hdr.lookup_table_res_entry.offset;
 396         buf_entries_remaining = 0;
 397         for (; num_entries != 0; num_entries--, buf_entries_remaining--) {
 398                 if (buf_entries_remaining == 0) {
 399                         size_t entries_to_read, bytes_to_read;
 400
 401                         entries_to_read = min(sizeof(table_buf) /
 402                                                 WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE,
 403                                               num_entries);
 404                         bytes_to_read = entries_to_read *
 405                                                 WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE;
 406                         if (full_pread(w->in_fd, table_buf,
 407                                        bytes_to_read, offset) != bytes_to_read)
 408                         {
 409                                 ERROR_WITH_ERRNO("Error reading lookup table "
 410                                                  "(offset=%"PRIu64")", offset);
 411                                 ret = WIMLIB_ERR_READ;
 412                                 goto out_free_lookup_table;
 413                         }
 414                         offset += bytes_to_read;
 415                         p = table_buf;
 416                         buf_entries_remaining = entries_to_read;
 417                 }
 418                 cur_entry = new_lookup_table_entry();
 419                 if (!cur_entry) {
 420                         ret = WIMLIB_ERR_NOMEM;
 421                         goto out_free_lookup_table;
 422                 }
 423
 424                 cur_entry->wim = w;
 425                 cur_entry->resource_location = RESOURCE_IN_WIM;
 426                 p = get_resource_entry(p, &cur_entry->resource_entry);
 427                 p = get_u16(p, &cur_entry->part_number);
 428                 p = get_u32(p, &cur_entry->refcnt);
 429                 p = get_bytes(p, SHA1_HASH_SIZE, cur_entry->hash);
 430
 431                 if (cur_entry->part_number != w->hdr.part_number) {
 432                         ERROR("A lookup table entry in part %hu of the WIM "
 433                               "points to part %hu",
 434                               w->hdr.part_number, cur_entry->part_number);
 435                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 436                         goto out_free_cur_entry;
 437                 }
 438
 439                 if (is_zero_hash(cur_entry->hash)) {
 440                         ERROR("The WIM lookup table contains an entry with a "
 441                               "SHA1 message digest of all 0's");
 442                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 443                         goto out_free_cur_entry;
 444                 }
 445
 446                 if (!(cur_entry->resource_entry.flags & WIM_RESHDR_FLAG_COMPRESSED)
 447                     && (cur_entry->resource_entry.size !=
 448                         cur_entry->resource_entry.original_size))
 449                 {
 450                 #ifdef ENABLE_ERROR_MESSAGES
 451                         ERROR("Found uncompressed resource with original size "
 452                               "not the same as compressed size");
 453                         ERROR("The lookup table entry for the resource is as follows:");
 454                         print_lookup_table_entry(cur_entry, stderr);
 455                 #endif
 456                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 457                         goto out_free_cur_entry;
 458                 }
 459
 460                 if (cur_entry->resource_entry.flags & WIM_RESHDR_FLAG_METADATA) {
 461                         /* Lookup table entry for a metadata resource */
 462                         if (cur_entry->refcnt != 1) {
 463                         #ifdef ENABLE_ERROR_MESSAGES
 464                                 ERROR("Found metadata resource with refcnt != 1:");
 465                                 print_lookup_table_entry(cur_entry, stderr);
 466                         #endif
 467                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 468                                 goto out_free_cur_entry;
 469                         }
 470
 471                         if (w->hdr.part_number != 1) {
 472                                 ERROR("Found a metadata resource in a "
 473                                       "non-first part of the split WIM!");
 474                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 475                                 goto out_free_cur_entry;
 476                         }
 477                         if (w->current_image == w->hdr.image_count) {
 478                                 ERROR("The WIM header says there are %u images "
 479                                       "in the WIM, but we found more metadata "
 480                                       "resources than this", w->hdr.image_count);
 481                                 ret = WIMLIB_ERR_IMAGE_COUNT;
 482                                 goto out_free_cur_entry;
 483                         }
 484
 485                         /* Notice very carefully:  We are assigning the metadata
 486                          * resources in the exact order mirrored by their lookup
 487                          * table entries on disk, which is the behavior of
 488                          * Microsoft's software.  In particular, this overrides
 489                          * the actual locations of the metadata resources
 490                          * themselves in the WIM file as well as any information
 491                          * written in the XML data. */
 492                         DEBUG("Found metadata resource for image %u at "
 493                               "offset %"PRIu64".",
 494                               w->current_image + 1,
 495                               cur_entry->resource_entry.offset);
 496                         w->image_metadata[
 497                                 w->current_image++]->metadata_lte = cur_entry;
 498                 } else {
 499                         /* Lookup table entry for a stream that is not a
 500                          * metadata resource */
 501                         duplicate_entry = __lookup_resource(table, cur_entry->hash);
 502                         if (duplicate_entry) {
 503                         #ifdef ENABLE_ERROR_MESSAGES
 504                                 ERROR("The WIM lookup table contains two entries with the "
 505                                       "same SHA1 message digest!");
 506                                 ERROR("The first entry is:");
 507                                 print_lookup_table_entry(duplicate_entry, stderr);
 508                                 ERROR("The second entry is:");
 509                                 print_lookup_table_entry(cur_entry, stderr);
 510                         #endif
 511                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 512                                 goto out_free_cur_entry;
 513                         }
 514                         lookup_table_insert(table, cur_entry);
 515                 }
 516         }
 517
 518         if (w->hdr.part_number == 1 && w->current_image != w->hdr.image_count)
 519         {
 520                 ERROR("The WIM header says there are %u images "
 521                       "in the WIM, but we only found %d metadata "
 522                       "resources!", w->hdr.image_count, w->current_image);
 523                 ret = WIMLIB_ERR_IMAGE_COUNT;
 524                 goto out_free_lookup_table;
 525         }
 526         DEBUG("Done reading lookup table.");
 527         w->lookup_table = table;
 528         ret = 0;
 529         goto out;
 530 out_free_cur_entry:
 531         FREE(cur_entry);
 532 out_free_lookup_table:
 533         free_lookup_table(table);
 534 out:
 535         w->current_image = 0;
 536         return ret;
 537 }
 538
 539
 540 static u8 *
 541 write_lookup_table_entry(const struct wim_lookup_table_entry *lte, u8 *buf_p)
 542 {
 543         buf_p = put_resource_entry(buf_p, &lte->output_resource_entry);
 544         buf_p = put_u16(buf_p, lte->part_number);
 545         buf_p = put_u32(buf_p, lte->out_refcnt);
 546         buf_p = put_bytes(buf_p, SHA1_HASH_SIZE, lte->hash);
 547         return buf_p;
 548 }
 549
 550 int
 551 write_lookup_table_from_stream_list(struct list_head *stream_list,
 552                                     int out_fd,
 553                                     struct resource_entry *out_res_entry)
 554 {
 555         int ret;
 556         off_t start_offset;
 557         u8 table_buf[(BUFFER_SIZE / WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE) *
 558                         WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
 559         u8 *buf_p;
 560         size_t table_size;
 561         size_t bytes_to_write;
 562         struct wim_lookup_table_entry *lte;
 563
 564         start_offset = filedes_offset(out_fd);
 565         if (start_offset == -1)
 566                 goto write_error;
 567
 568         buf_p = table_buf;
 569         table_size = 0;
 570         list_for_each_entry(lte, stream_list, lookup_table_list) {
 571                 if (buf_p == table_buf + sizeof(table_buf)) {
 572                         bytes_to_write = sizeof(table_buf);
 573                         if (full_write(out_fd, table_buf,
 574                                        bytes_to_write) != bytes_to_write)
 575                                 goto write_error;
 576                         table_size += bytes_to_write;
 577                         buf_p = table_buf;
 578                 }
 579                 buf_p = write_lookup_table_entry(lte, buf_p);
 580         }
 581         bytes_to_write = buf_p - table_buf;
 582         if (bytes_to_write != 0) {
 583                 if (full_write(out_fd, table_buf,
 584                                bytes_to_write) != bytes_to_write)
 585                         goto write_error;
 586                 table_size += bytes_to_write;
 587         }
 588         out_res_entry->offset        = start_offset;
 589         out_res_entry->size          = table_size;
 590         out_res_entry->original_size = table_size;
 591         out_res_entry->flags         = WIM_RESHDR_FLAG_METADATA;
 592         ret = 0;
 593 out:
 594         return ret;
 595 write_error:
 596         ERROR_WITH_ERRNO("Failed to write lookup table");
 597         ret = WIMLIB_ERR_WRITE;
 598         goto out;
 599 }
 600
 601 static int
 602 append_lookup_table_entry(struct wim_lookup_table_entry *lte, void *_list)
 603 {
 604         if (lte->out_refcnt != 0)
 605                 list_add_tail(&lte->lookup_table_list, (struct list_head*)_list);
 606         return 0;
 607 }
 608
 609 /* Writes the WIM lookup table to the output file. */
 610 int
 611 write_lookup_table(WIMStruct *w, int image, struct resource_entry *out_res_entry)
 612 {
 613         LIST_HEAD(stream_list);
 614         int start_image;
 615         int end_image;
 616
 617         if (image == WIMLIB_ALL_IMAGES) {
 618                 start_image = 1;
 619                 end_image = w->hdr.image_count;
 620         } else {
 621                 start_image = image;
 622                 end_image = image;
 623         }
 624
 625         for (int i = start_image; i <= end_image; i++) {
 626                 struct wim_lookup_table_entry *metadata_lte;
 627
 628                 metadata_lte = w->image_metadata[i - 1]->metadata_lte;
 629                 metadata_lte->out_refcnt = 1;
 630                 metadata_lte->output_resource_entry.flags |= WIM_RESHDR_FLAG_METADATA;
 631                 append_lookup_table_entry(metadata_lte, &stream_list);
 632         }
 633         for_lookup_table_entry(w->lookup_table,
 634                                append_lookup_table_entry,
 635                                &stream_list);
 636         return write_lookup_table_from_stream_list(&stream_list,
 637                                                    w->out_fd,
 638                                                    out_res_entry);
 639 }
 640
 641 int
 642 lte_zero_real_refcnt(struct wim_lookup_table_entry *lte, void *_ignore)
 643 {
 644         lte->real_refcnt = 0;
 645         return 0;
 646 }
 647
 648 int
 649 lte_zero_out_refcnt(struct wim_lookup_table_entry *lte, void *_ignore)
 650 {
 651         lte->out_refcnt = 0;
 652         return 0;
 653 }
 654
 655 int
 656 lte_free_extracted_file(struct wim_lookup_table_entry *lte, void *_ignore)
 657 {
 658         if (lte->extracted_file != NULL) {
 659                 FREE(lte->extracted_file);
 660                 lte->extracted_file = NULL;
 661         }
 662         return 0;
 663 }
 664
 665 void
 666 print_lookup_table_entry(const struct wim_lookup_table_entry *lte, FILE *out)
 667 {
 668         if (!lte) {
 669                 tputc(T('\n'), out);
 670                 return;
 671         }
 672         tfprintf(out, T("Offset            = %"PRIu64" bytes\n"),
 673                  lte->resource_entry.offset);
 674
 675         tfprintf(out, T("Size              = %"PRIu64" bytes\n"),
 676                  (u64)lte->resource_entry.size);
 677
 678         tfprintf(out, T("Original size     = %"PRIu64" bytes\n"),
 679                  lte->resource_entry.original_size);
 680
 681         tfprintf(out, T("Part Number       = %hu\n"), lte->part_number);
 682         tfprintf(out, T("Reference Count   = %u\n"), lte->refcnt);
 683
 684         if (lte->unhashed) {
 685                 tfprintf(out, T("(Unhashed: inode %p, stream_id = %u)\n"),
 686                          lte->back_inode, lte->back_stream_id);
 687         } else {
 688                 tfprintf(out, T("Hash              = 0x"));
 689                 print_hash(lte->hash, out);
 690                 tputc(T('\n'), out);
 691         }
 692
 693         tfprintf(out, T("Flags             = "));
 694         u8 flags = lte->resource_entry.flags;
 695         if (flags & WIM_RESHDR_FLAG_COMPRESSED)
 696                 tfputs(T("WIM_RESHDR_FLAG_COMPRESSED, "), out);
 697         if (flags & WIM_RESHDR_FLAG_FREE)
 698                 tfputs(T("WIM_RESHDR_FLAG_FREE, "), out);
 699         if (flags & WIM_RESHDR_FLAG_METADATA)
 700                 tfputs(T("WIM_RESHDR_FLAG_METADATA, "), out);
 701         if (flags & WIM_RESHDR_FLAG_SPANNED)
 702                 tfputs(T("WIM_RESHDR_FLAG_SPANNED, "), out);
 703         tputc(T('\n'), out);
 704         switch (lte->resource_location) {
 705         case RESOURCE_IN_WIM:
 706                 if (lte->wim->filename) {
 707                         tfprintf(out, T("WIM file          = `%"TS"'\n"),
 708                                  lte->wim->filename);
 709                 }
 710                 break;
 711 #ifdef __WIN32__
 712         case RESOURCE_WIN32:
 713         case RESOURCE_WIN32_ENCRYPTED:
 714 #else
 715         case RESOURCE_IN_FILE_ON_DISK:
 716 #endif
 717                 tfprintf(out, T("File on Disk      = `%"TS"'\n"),
 718                          lte->file_on_disk);
 719                 break;
 720 #ifdef WITH_FUSE
 721         case RESOURCE_IN_STAGING_FILE:
 722                 tfprintf(out, T("Staging File      = `%"TS"'\n"),
 723                                 lte->staging_file_name);
 724                 break;
 725 #endif
 726         default:
 727                 break;
 728         }
 729         tputc(T('\n'), out);
 730 }
 731
 732 static int
 733 do_print_lookup_table_entry(struct wim_lookup_table_entry *lte, void *fp)
 734 {
 735         print_lookup_table_entry(lte, (FILE*)fp);
 736         return 0;
 737 }
 738
 739 /*
 740  * Prints the lookup table of a WIM file.
 741  */
 742 WIMLIBAPI void
 743 wimlib_print_lookup_table(WIMStruct *w)
 744 {
 745         for_lookup_table_entry(w->lookup_table,
 746                                do_print_lookup_table_entry,
 747                                stdout);
 748 }
 749
 750 /* Given a SHA1 message digest, return the corresponding entry in the WIM's
 751  * lookup table, or NULL if there is none.  */
 752 struct wim_lookup_table_entry *
 753 __lookup_resource(const struct wim_lookup_table *table, const u8 hash[])
 754 {
 755         size_t i;
 756         struct wim_lookup_table_entry *lte;
 757         struct hlist_node *pos;
 758
 759         wimlib_assert(table != NULL);
 760         wimlib_assert(hash != NULL);
 761
 762         i = *(size_t*)hash % table->capacity;
 763         hlist_for_each_entry(lte, pos, &table->array[i], hash_list)
 764                 if (hashes_equal(hash, lte->hash))
 765                         return lte;
 766         return NULL;
 767 }
 768
 769 #ifdef WITH_FUSE
 770 /*
 771  * Finds the dentry, lookup table entry, and stream index for a WIM file stream,
 772  * given a path name.
 773  *
 774  * This is only for pre-resolved inodes.
 775  */
 776 int
 777 lookup_resource(WIMStruct *w,
 778                 const tchar *path,
 779                 int lookup_flags,
 780                 struct wim_dentry **dentry_ret,
 781                 struct wim_lookup_table_entry **lte_ret,
 782                 u16 *stream_idx_ret)
 783 {
 784         struct wim_dentry *dentry;
 785         struct wim_lookup_table_entry *lte;
 786         u16 stream_idx;
 787         const tchar *stream_name = NULL;
 788         struct wim_inode *inode;
 789         tchar *p = NULL;
 790
 791         if (lookup_flags & LOOKUP_FLAG_ADS_OK) {
 792                 stream_name = path_stream_name(path);
 793                 if (stream_name) {
 794                         p = (tchar*)stream_name - 1;
 795                         *p = T('\0');
 796                 }
 797         }
 798
 799         dentry = get_dentry(w, path);
 800         if (p)
 801                 *p = T(':');
 802         if (!dentry)
 803                 return -errno;
 804
 805         inode = dentry->d_inode;
 806
 807         wimlib_assert(inode->i_resolved);
 808
 809         if (!(lookup_flags & LOOKUP_FLAG_DIRECTORY_OK)
 810               && inode_is_directory(inode))
 811                 return -EISDIR;
 812
 813         if (stream_name) {
 814                 struct wim_ads_entry *ads_entry;
 815                 u16 ads_idx;
 816                 ads_entry = inode_get_ads_entry(inode, stream_name,
 817                                                 &ads_idx);
 818                 if (ads_entry) {
 819                         stream_idx = ads_idx + 1;
 820                         lte = ads_entry->lte;
 821                         goto out;
 822                 } else {
 823                         return -ENOENT;
 824                 }
 825         } else {
 826                 lte = inode->i_lte;
 827                 stream_idx = 0;
 828         }
 829 out:
 830         if (dentry_ret)
 831                 *dentry_ret = dentry;
 832         if (lte_ret)
 833                 *lte_ret = lte;
 834         if (stream_idx_ret)
 835                 *stream_idx_ret = stream_idx;
 836         return 0;
 837 }
 838 #endif
 839
 840 /*
 841  * XXX Probably should store the compression type directly in the lookup table
 842  * entry
 843  */
 844 int
 845 wim_resource_compression_type(const struct wim_lookup_table_entry *lte)
 846 {
 847         if (!(lte->resource_entry.flags & WIM_RESHDR_FLAG_COMPRESSED)
 848             || lte->resource_location != RESOURCE_IN_WIM)
 849                 return WIMLIB_COMPRESSION_TYPE_NONE;
 850         return wimlib_get_compression_type(lte->wim);
 851 }
 852
 853 /* Resolve an inode's lookup table entries
 854  *
 855  * This replaces the SHA1 hash fields (which are used to lookup an entry in the
 856  * lookup table) with pointers directly to the lookup table entries.  A circular
 857  * linked list of streams sharing the same lookup table entry is created.
 858  *
 859  * This function always succeeds; unresolved lookup table entries are given a
 860  * NULL pointer.
 861  */
 862 void
 863 inode_resolve_ltes(struct wim_inode *inode, struct wim_lookup_table *table)
 864 {
 865
 866         if (!inode->i_resolved) {
 867                 struct wim_lookup_table_entry *lte;
 868                 /* Resolve the default file stream */
 869                 lte = __lookup_resource(table, inode->i_hash);
 870                 inode->i_lte = lte;
 871                 inode->i_resolved = 1;
 872
 873                 /* Resolve the alternate data streams */
 874                 for (u16 i = 0; i < inode->i_num_ads; i++) {
 875                         struct wim_ads_entry *cur_entry = &inode->i_ads_entries[i];
 876                         lte = __lookup_resource(table, cur_entry->hash);
 877                         cur_entry->lte = lte;
 878                 }
 879         }
 880 }
 881
 882 void
 883 inode_unresolve_ltes(struct wim_inode *inode)
 884 {
 885         if (inode->i_resolved) {
 886                 if (inode->i_lte)
 887                         copy_hash(inode->i_hash, inode->i_lte->hash);
 888                 else
 889                         zero_out_hash(inode->i_hash);
 890
 891                 for (u16 i = 0; i < inode->i_num_ads; i++) {
 892                         if (inode->i_ads_entries[i].lte)
 893                                 copy_hash(inode->i_ads_entries[i].hash,
 894                                           inode->i_ads_entries[i].lte->hash);
 895                         else
 896                                 zero_out_hash(inode->i_ads_entries[i].hash);
 897                 }
 898                 inode->i_resolved = 0;
 899         }
 900 }
 901
 902 /*
 903  * Returns the lookup table entry for stream @stream_idx of the inode, where
 904  * stream_idx = 0 means the default un-named file stream, and stream_idx >= 1
 905  * corresponds to an alternate data stream.
 906  *
 907  * This works for both resolved and un-resolved inodes.
 908  */
 909 struct wim_lookup_table_entry *
 910 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
 911                  const struct wim_lookup_table *table)
 912 {
 913         if (inode->i_resolved)
 914                 return inode_stream_lte_resolved(inode, stream_idx);
 915         else
 916                 return inode_stream_lte_unresolved(inode, stream_idx, table);
 917 }
 918
 919 struct wim_lookup_table_entry *
 920 inode_unnamed_lte_resolved(const struct wim_inode *inode)
 921 {
 922         wimlib_assert(inode->i_resolved);
 923         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
 924                 if (inode_stream_name_nbytes(inode, i) == 0 &&
 925                     !is_zero_hash(inode_stream_hash_resolved(inode, i)))
 926                 {
 927                         return inode_stream_lte_resolved(inode, i);
 928                 }
 929         }
 930         return NULL;
 931 }
 932
 933 struct wim_lookup_table_entry *
 934 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
 935                              const struct wim_lookup_table *table)
 936 {
 937         wimlib_assert(!inode->i_resolved);
 938         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
 939                 if (inode_stream_name_nbytes(inode, i) == 0 &&
 940                     !is_zero_hash(inode_stream_hash_unresolved(inode, i)))
 941                 {
 942                         return inode_stream_lte_unresolved(inode, i, table);
 943                 }
 944         }
 945         return NULL;
 946 }
 947
 948 /* Return the lookup table entry for the unnamed data stream of an inode, or
 949  * NULL if there is none.
 950  *
 951  * You'd think this would be easier than it actually is, since the unnamed data
 952  * stream should be the one referenced from the inode itself.  Alas, if there
 953  * are named data streams, Microsoft's "imagex.exe" program will put the unnamed
 954  * data stream in one of the alternate data streams instead of inside the WIM
 955  * dentry itself.  So we need to check the alternate data streams too.
 956  *
 957  * Also, note that a dentry may appear to have more than one unnamed stream, but
 958  * if the SHA1 message digest is all 0's then the corresponding stream does not
 959  * really "count" (this is the case for the inode's own file stream when the
 960  * file stream that should be there is actually in one of the alternate stream
 961  * entries.).  This is despite the fact that we may need to extract such a
 962  * missing entry as an empty file or empty named data stream.
 963  */
 964 struct wim_lookup_table_entry *
 965 inode_unnamed_lte(const struct wim_inode *inode,
 966                   const struct wim_lookup_table *table)
 967 {
 968         if (inode->i_resolved)
 969                 return inode_unnamed_lte_resolved(inode);
 970         else
 971                 return inode_unnamed_lte_unresolved(inode, table);
 972 }
 973
 974 static int
 975 lte_add_stream_size(struct wim_lookup_table_entry *lte, void *total_bytes_p)
 976 {
 977         *(u64*)total_bytes_p += lte->resource_entry.size;
 978         return 0;
 979 }
 980
 981 u64
 982 lookup_table_total_stream_size(struct wim_lookup_table *table)
 983 {
 984         u64 total_size = 0;
 985         for_lookup_table_entry(table, lte_add_stream_size, &total_size);
 986         return total_size;
 987 }
 988
 989 struct wim_lookup_table_entry **
 990 retrieve_lte_pointer(struct wim_lookup_table_entry *lte)
 991 {
 992         wimlib_assert(lte->unhashed);
 993         struct wim_inode *inode = lte->back_inode;
 994         u32 stream_id = lte->back_stream_id;
 995         if (stream_id == 0)
 996                 return &inode->i_lte;
 997         else
 998                 for (u16 i = 0; i < inode->i_num_ads; i++)
 999                         if (inode->i_ads_entries[i].stream_id == stream_id)
1000                                 return &inode->i_ads_entries[i].lte;
1001         wimlib_assert(0);
1002         return NULL;
1003 }
1004
1005 /* Calculate the SHA1 message digest of a stream and move it from the list of
1006  * unhashed streams to the stream lookup table, possibly joining it with an
1007  * existing lookup table entry for an identical stream.
1008  *
1009  * @lte:  An unhashed lookup table entry.
1010  * @lookup_table:  Lookup table for the WIM.
1011  * @lte_ret:  On success, write a pointer to the resulting lookup table
1012  *            entry to this location.  This will be the same as @lte
1013  *            if it was inserted into the lookup table, or different if
1014  *            a duplicate stream was found.
1015  *
1016  * Returns 0 on success; nonzero if there is an error reading the stream.
1017  */
1018 int
1019 hash_unhashed_stream(struct wim_lookup_table_entry *lte,
1020                      struct wim_lookup_table *lookup_table,
1021                      struct wim_lookup_table_entry **lte_ret)
1022 {
1023         int ret;
1024         struct wim_lookup_table_entry *duplicate_lte;
1025         struct wim_lookup_table_entry **back_ptr;
1026
1027         wimlib_assert(lte->unhashed);
1028
1029         /* back_ptr must be saved because @back_inode and @back_stream_id are in
1030          * union with the SHA1 message digest and will no longer be valid once
1031          * the SHA1 has been calculated. */
1032         back_ptr = retrieve_lte_pointer(lte);
1033
1034         ret = sha1_resource(lte);
1035         if (ret)
1036                 return ret;
1037
1038         /* Look for a duplicate stream */
1039         duplicate_lte = __lookup_resource(lookup_table, lte->hash);
1040         list_del(&lte->unhashed_list);
1041         if (duplicate_lte) {
1042                 /* We have a duplicate stream.  Transfer the reference counts
1043                  * from this stream to the duplicate, update the reference to
1044                  * this stream (in an inode or ads_entry) to point to the
1045                  * duplicate, then free this stream. */
1046                 wimlib_assert(!(duplicate_lte->unhashed));
1047                 duplicate_lte->refcnt += lte->refcnt;
1048                 duplicate_lte->out_refcnt += lte->refcnt;
1049                 *back_ptr = duplicate_lte;
1050                 free_lookup_table_entry(lte);
1051                 lte = duplicate_lte;
1052         } else {
1053                 /* No duplicate stream, so we need to insert
1054                  * this stream into the lookup table and treat
1055                  * it as a hashed stream. */
1056                 lookup_table_insert(lookup_table, lte);
1057                 lte->unhashed = 0;
1058         }
1059         if (lte_ret)
1060                 *lte_ret = lte;
1061         return 0;
1062 }
1063