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

   1 #ifndef _WIMLIB_LOOKUP_TABLE_H
   2 #define _WIMLIB_LOOKUP_TABLE_H
   3 #include "wimlib_internal.h"
   4 #include "dentry.h"
   5 #include "sha1.h"
   6 #include <sys/types.h>
   7
   8 /* Size of each lookup table entry in the WIM file. */
   9 #define WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE 50
  10
  11 #define LOOKUP_FLAG_ADS_OK              0x00000001
  12 #define LOOKUP_FLAG_DIRECTORY_OK        0x00000002
  13
  14 #ifdef __WIN32__
  15 #include <windef.h>
  16 #endif
  17
  18
  19 /* The lookup table of a WIM file maps SHA1 message digests to streams of data.
  20  * Here, the in-memory structure is implemented as a hash table.
  21  *
  22  * Given a SHA1 message digest, the mapped-to stream is specified by an offset
  23  * in the WIM, an uncompressed and compressed size, and resource flags (see
  24  * 'struct resource_entry').  But, we associate additional information, such as
  25  * a reference count, with each stream, so the actual mapping is from SHA1
  26  * message digests to 'struct wim_lookup_table_entry's, each of which contains
  27  * an embedded 'struct resource_entry'.
  28  *
  29  * Note: Everything will break horribly if there is a SHA1 collision.
  30  */
  31 struct wim_lookup_table {
  32         struct hlist_head *array;
  33         u64 num_entries;
  34         u64 capacity;
  35         struct list_head *unhashed_streams;
  36 };
  37
  38 #ifdef WITH_NTFS_3G
  39 struct ntfs_location {
  40         tchar *path;
  41         utf16lechar *stream_name;
  42         u16 stream_name_nchars;
  43         struct _ntfs_volume *ntfs_vol;
  44         bool is_reparse_point;
  45 };
  46 #endif
  47
  48 /* An enumerated type that identifies where the stream corresponding to this
  49  * lookup table entry is actually located.
  50  *
  51  * If we open a WIM and read its lookup table, the location is set to
  52  * RESOURCE_IN_WIM since all the streams will initially be located in the WIM.
  53  * However, to deal with problems such as image capture and image mount, we
  54  * allow the actual location of the stream to be somewhere else, such as an
  55  * external file.
  56  */
  57 enum resource_location {
  58         /* The lookup table entry does not correspond to a stream (this state
  59          * should exist only temporarily) */
  60         RESOURCE_NONEXISTENT = 0,
  61
  62         /* The stream resource is located in a WIM file.  The WIMStruct for the
  63          * WIM file will be pointed to by the @wim member. */
  64         RESOURCE_IN_WIM,
  65
  66         /* The stream resource is located in an external file.  The name of the
  67          * file will be provided by @file_on_disk member.  In addition, if
  68          * @file_on_disk_fp is not NULL, it will be an open FILE * to the file.
  69          * */
  70         RESOURCE_IN_FILE_ON_DISK,
  71
  72         /* The stream resource is directly attached in an in-memory buffer
  73          * pointed to by @attached_buffer. */
  74         RESOURCE_IN_ATTACHED_BUFFER,
  75
  76 #ifdef WITH_FUSE
  77         /* The stream resource is located in an external file in the staging
  78          * directory for a read-write mount.  */
  79         RESOURCE_IN_STAGING_FILE,
  80 #endif
  81
  82 #ifdef WITH_NTFS_3G
  83         /* The stream resource is located in an NTFS volume.  It is identified
  84          * by volume, filename, data stream name, and by whether it is a reparse
  85          * point or not. @ntfs_loc points to a structure containing this
  86          * information. */
  87         RESOURCE_IN_NTFS_VOLUME,
  88 #endif
  89
  90 #ifdef __WIN32__
  91         /* Resource must be accessed using Win32 API (may be a named data
  92          * stream) */
  93         RESOURCE_WIN32,
  94
  95         /* Windows only: the file is on disk in the file named @file_on_disk,
  96          * but the file is encrypted and must be read using special functions.
  97          * */
  98         RESOURCE_WIN32_ENCRYPTED,
  99 #endif
 100
 101 };
 102
 103 /*
 104  * An entry in the lookup table in the WIM file.
 105  *
 106  * It is used to find data streams for files in the WIM.
 107  *
 108  * Metadata resources and reparse point data buffers will also have lookup table
 109  * entries associated with the data.
 110  *
 111  * The lookup_table_entry for a given dentry or alternate stream entry in the
 112  * WIM is found using the SHA1 message digest field.
 113  */
 114 struct wim_lookup_table_entry {
 115
 116         /* List of lookup table entries in this hash bucket */
 117         struct hlist_node hash_list;
 118
 119         /* Location and size of the stream in the WIM, whether it is compressed
 120          * or not, and whether it's a metadata resource or not.  This is an
 121          * on-disk field. */
 122         struct resource_entry resource_entry;
 123
 124         /* Specifies which part of the split WIM the resource is located in.
 125          * This is on on-disk field.
 126          *
 127          * In stand-alone WIMs, this must be 1.
 128          *
 129          * In split WIMs, every split WIM part has its own lookup table, and in
 130          * read_lookup_table() it's currently expected that the part number of
 131          * each lookup table entry in a split WIM part's lookup table is the
 132          * same as the part number of that split WIM part.  So this makes this
 133          * field redundant since we store a pointer to the corresponding
 134          * WIMStruct in the lookup table entry anyway.
 135          */
 136         u16 part_number;
 137
 138         /* One of the `enum resource_location' values documented above. */
 139         u16 resource_location : 5;
 140
 141         /* 1 if this stream is a unique size (only set while writing streams). */
 142         u8 unique_size : 1;
 143
 144         /* 1 if this stream had a SHA1-message digest calculated for it yet? */
 145         u8 unhashed : 1;
 146
 147         u8 deferred : 1;
 148
 149         u8 no_progress : 1;
 150
 151         /* (On-disk field)
 152          * Number of times this lookup table entry is referenced by dentries.
 153          * Unfortunately, this field is not always set correctly in Microsoft's
 154          * WIMs, so we have no choice but to fix it if more references to the
 155          * lookup table entry are found than stated here. */
 156         u32 refcnt;
 157
 158         union {
 159                 /* (On-disk field) SHA1 message digest of the stream referenced
 160                  * by this lookup table entry */
 161                 u8  hash[SHA1_HASH_SIZE];
 162
 163                 /* First 4 or 8 bytes of the SHA1 message digest, used for
 164                  * inserting the entry into the hash table.  Since the SHA1
 165                  * message digest can be considered random, we don't really need
 166                  * the full 20 byte hash just to insert the entry in a hash
 167                  * table. */
 168                 size_t hash_short;
 169
 170                 /* Unhashed entries only (unhashed == 1): these variables make
 171                  * it possible to find the pointer to this 'struct
 172                  * wim_lookup_table_entry' contained in either 'struct
 173                  * wim_ads_entry' or 'struct wim_inode'.  There can be at most 1
 174                  * such pointer, as we can only join duplicate streams after
 175                  * they have been hashed.  */
 176                 struct {
 177                         struct wim_inode *back_inode;
 178                         u32 back_stream_id;
 179                 };
 180         };
 181
 182         /* When a WIM file is written, out_refcnt starts at 0 and is incremented
 183          * whenever the stream pointed to by this lookup table entry needs to be
 184          * written.  The stream only need to be written when out_refcnt is
 185          * nonzero, since otherwise it is not referenced by any dentries. */
 186         u32 out_refcnt;
 187
 188         /* Pointers to somewhere where the stream is actually located.  See the
 189          * comments for the @resource_location field above. */
 190         union {
 191                 WIMStruct *wim;
 192                 tchar *file_on_disk;
 193                 void *attached_buffer;
 194         #ifdef WITH_FUSE
 195                 tchar *staging_file_name;
 196         #endif
 197         #ifdef WITH_NTFS_3G
 198                 struct ntfs_location *ntfs_loc;
 199         #endif
 200         };
 201
 202         /* Actual reference count to this stream (only used while
 203          * verifying an image). */
 204         u32 real_refcnt;
 205
 206         union {
 207         #ifdef WITH_FUSE
 208                 /* Number of times this stream has been opened (used only during
 209                  * mounting) */
 210                 u16 num_opened_fds;
 211         #endif
 212
 213                 /* This field is used for the special hardlink or symlink image
 214                  * extraction mode.   In these mode, all identical files are linked
 215                  * together, and @extracted_file will be set to the filename of the
 216                  * first extracted file containing this stream.  */
 217                 tchar *extracted_file;
 218         };
 219
 220         union {
 221                 /* When a WIM file is written, @output_resource_entry is filled
 222                  * in with the resource entry for the output WIM.  This will not
 223                  * necessarily be the same as the @resource_entry since: - The
 224                  * stream may have a different offset in the new WIM - The
 225                  * stream may have a different compressed size in the new WIM if
 226                  * the compression type changed
 227                  */
 228                 struct resource_entry output_resource_entry;
 229
 230                 struct {
 231                         struct list_head msg_list;
 232                         struct list_head being_compressed_list;
 233                 };
 234                 struct list_head inode_list;
 235
 236                 struct {
 237                         struct hlist_node hash_list_2;
 238
 239                         struct list_head write_streams_list;
 240                 };
 241         };
 242
 243         /* Temporary list fields */
 244         union {
 245                 struct list_head unhashed_list;
 246                 struct list_head swm_stream_list;
 247                 struct list_head extraction_list;
 248                 struct list_head export_stream_list;
 249         };
 250 };
 251
 252 static inline u64
 253 wim_resource_size(const struct wim_lookup_table_entry *lte)
 254 {
 255         return lte->resource_entry.original_size;
 256 }
 257
 258 static inline u64
 259 wim_resource_chunks(const struct wim_lookup_table_entry *lte)
 260 {
 261         return (wim_resource_size(lte) + WIM_CHUNK_SIZE - 1) / WIM_CHUNK_SIZE;
 262 }
 263
 264 static inline u64
 265 wim_resource_compressed_size(const struct wim_lookup_table_entry *lte)
 266 {
 267         return lte->resource_entry.size;
 268 }
 269
 270 /*
 271  * XXX Probably should store the compression type directly in the lookup table
 272  * entry
 273  */
 274 static inline int
 275 wim_resource_compression_type(const struct wim_lookup_table_entry *lte)
 276 {
 277         if (!(lte->resource_entry.flags & WIM_RESHDR_FLAG_COMPRESSED)
 278             || lte->resource_location != RESOURCE_IN_WIM)
 279                 return WIMLIB_COMPRESSION_TYPE_NONE;
 280         return wimlib_get_compression_type(lte->wim);
 281 }
 282
 283 static inline bool
 284 lte_filename_valid(const struct wim_lookup_table_entry *lte)
 285 {
 286         return lte->resource_location == RESOURCE_IN_FILE_ON_DISK
 287         #ifdef __WIN32__
 288                 || lte->resource_location == RESOURCE_WIN32
 289                 || lte->resource_location == RESOURCE_WIN32_ENCRYPTED
 290         #endif
 291         #ifdef WITH_FUSE
 292                 || lte->resource_location == RESOURCE_IN_STAGING_FILE
 293         #endif
 294                 ;
 295 }
 296
 297 extern struct wim_lookup_table *
 298 new_lookup_table(size_t capacity);
 299
 300 extern int
 301 read_lookup_table(WIMStruct *w);
 302
 303 extern int
 304 write_lookup_table(WIMStruct *w, int image, struct resource_entry *out_res_entry);
 305
 306 extern void
 307 free_lookup_table(struct wim_lookup_table *table);
 308
 309 extern void
 310 lookup_table_insert(struct wim_lookup_table *table, struct wim_lookup_table_entry *lte);
 311
 312 /* Unlinks a lookup table entry from the table; does not free it. */
 313 static inline void
 314 lookup_table_unlink(struct wim_lookup_table *table, struct wim_lookup_table_entry *lte)
 315 {
 316         wimlib_assert(!lte->unhashed);
 317         hlist_del(&lte->hash_list);
 318         wimlib_assert(table->num_entries != 0);
 319         table->num_entries--;
 320 }
 321
 322 extern struct wim_lookup_table_entry *
 323 new_lookup_table_entry();
 324
 325 extern struct wim_lookup_table_entry *
 326 clone_lookup_table_entry(const struct wim_lookup_table_entry *lte);
 327
 328 extern void
 329 print_lookup_table_entry(const struct wim_lookup_table_entry *entry,
 330                          FILE *out);
 331
 332 extern void
 333 free_lookup_table_entry(struct wim_lookup_table_entry *lte);
 334
 335 extern int
 336 for_lookup_table_entry(struct wim_lookup_table *table,
 337                        int (*visitor)(struct wim_lookup_table_entry *, void *),
 338                        void *arg);
 339
 340 extern int
 341 cmp_streams_by_wim_position(const void *p1, const void *p2);
 342
 343 extern int
 344 for_lookup_table_entry_pos_sorted(struct wim_lookup_table *table,
 345                                   int (*visitor)(struct wim_lookup_table_entry *,
 346                                                  void *),
 347                                   void *arg);
 348
 349 extern struct wim_lookup_table_entry *
 350 __lookup_resource(const struct wim_lookup_table *table, const u8 hash[]);
 351
 352 extern int
 353 lookup_resource(WIMStruct *w, const tchar *path,
 354                 int lookup_flags, struct wim_dentry **dentry_ret,
 355                 struct wim_lookup_table_entry **lte_ret, u16 *stream_idx_ret);
 356
 357 extern void
 358 lte_decrement_refcnt(struct wim_lookup_table_entry *lte,
 359                      struct wim_lookup_table *table);
 360 #ifdef WITH_FUSE
 361 extern void
 362 lte_decrement_num_opened_fds(struct wim_lookup_table_entry *lte);
 363 #endif
 364
 365 extern int
 366 lte_zero_out_refcnt(struct wim_lookup_table_entry *entry, void *ignore);
 367
 368 extern int
 369 lte_zero_real_refcnt(struct wim_lookup_table_entry *entry, void *ignore);
 370
 371 extern int
 372 lte_free_extracted_file(struct wim_lookup_table_entry *lte, void *ignore);
 373
 374 extern void
 375 inode_resolve_ltes(struct wim_inode *inode, struct wim_lookup_table *table);
 376
 377 extern void
 378 inode_unresolve_ltes(struct wim_inode *inode);
 379
 380 extern int
 381 write_lookup_table_entry(struct wim_lookup_table_entry *lte, void *__out);
 382
 383 static inline struct wim_lookup_table_entry *
 384 inode_stream_lte_resolved(const struct wim_inode *inode, unsigned stream_idx)
 385 {
 386         wimlib_assert(inode->i_resolved);
 387         wimlib_assert(stream_idx <= inode->i_num_ads);
 388         if (stream_idx == 0)
 389                 return inode->i_lte;
 390         else
 391                 return inode->i_ads_entries[stream_idx - 1].lte;
 392 }
 393
 394 static inline struct wim_lookup_table_entry *
 395 inode_stream_lte_unresolved(const struct wim_inode *inode, unsigned stream_idx,
 396                             const struct wim_lookup_table *table)
 397 {
 398         wimlib_assert(!inode->i_resolved);
 399         wimlib_assert(stream_idx <= inode->i_num_ads);
 400         if (!table)
 401                 return NULL;
 402         if (stream_idx == 0)
 403                 return __lookup_resource(table, inode->i_hash);
 404         else
 405                 return __lookup_resource(table,
 406                                          inode->i_ads_entries[
 407                                                 stream_idx - 1].hash);
 408 }
 409
 410 extern struct wim_lookup_table_entry *
 411 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
 412                  const struct wim_lookup_table *table);
 413
 414 static inline const u8 *
 415 inode_stream_hash_unresolved(const struct wim_inode *inode, unsigned stream_idx)
 416 {
 417         wimlib_assert(!inode->i_resolved);
 418         wimlib_assert(stream_idx <= inode->i_num_ads);
 419         if (stream_idx == 0)
 420                 return inode->i_hash;
 421         else
 422                 return inode->i_ads_entries[stream_idx - 1].hash;
 423 }
 424
 425
 426 static inline const u8 *
 427 inode_stream_hash_resolved(const struct wim_inode *inode, unsigned stream_idx)
 428 {
 429         struct wim_lookup_table_entry *lte;
 430         lte = inode_stream_lte_resolved(inode, stream_idx);
 431         if (lte)
 432                 return lte->hash;
 433         else
 434                 return zero_hash;
 435 }
 436
 437 /*
 438  * Returns the hash for stream @stream_idx of the inode, where stream_idx = 0
 439  * means the default un-named file stream, and stream_idx >= 1 corresponds to an
 440  * alternate data stream.
 441  *
 442  * This works for both resolved and un-resolved dentries.
 443  */
 444 static inline const u8 *
 445 inode_stream_hash(const struct wim_inode *inode, unsigned stream_idx)
 446 {
 447         if (inode->i_resolved)
 448                 return inode_stream_hash_resolved(inode, stream_idx);
 449         else
 450                 return inode_stream_hash_unresolved(inode, stream_idx);
 451 }
 452
 453 static inline u16
 454 inode_stream_name_nbytes(const struct wim_inode *inode, unsigned stream_idx)
 455 {
 456         wimlib_assert(stream_idx <= inode->i_num_ads);
 457         if (stream_idx == 0)
 458                 return 0;
 459         else
 460                 return inode->i_ads_entries[stream_idx - 1].stream_name_nbytes;
 461 }
 462
 463 static inline struct wim_lookup_table_entry *
 464 inode_unnamed_lte_resolved(const struct wim_inode *inode)
 465 {
 466         wimlib_assert(inode->i_resolved);
 467         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
 468                 if (inode_stream_name_nbytes(inode, i) == 0 &&
 469                     !is_zero_hash(inode_stream_hash_resolved(inode, i)))
 470                 {
 471                         return inode_stream_lte_resolved(inode, i);
 472                 }
 473         }
 474         return NULL;
 475 }
 476
 477 static inline struct wim_lookup_table_entry *
 478 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
 479                              const struct wim_lookup_table *table)
 480 {
 481         wimlib_assert(!inode->i_resolved);
 482         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
 483                 if (inode_stream_name_nbytes(inode, i) == 0 &&
 484                     !is_zero_hash(inode_stream_hash_unresolved(inode, i)))
 485                 {
 486                         return inode_stream_lte_unresolved(inode, i, table);
 487                 }
 488         }
 489         return NULL;
 490 }
 491
 492 extern struct wim_lookup_table_entry *
 493 inode_unnamed_lte(const struct wim_inode *inode, const struct wim_lookup_table *table);
 494
 495 extern u64
 496 lookup_table_total_stream_size(struct wim_lookup_table *table);
 497
 498
 499 static inline void
 500 lookup_table_insert_unhashed(struct wim_lookup_table *table,
 501                              struct wim_lookup_table_entry *lte,
 502                              struct wim_inode *back_inode,
 503                              u32 back_stream_id)
 504 {
 505         lte->unhashed = 1;
 506         lte->back_inode = back_inode;
 507         lte->back_stream_id = back_stream_id;
 508         list_add_tail(&lte->unhashed_list, table->unhashed_streams);
 509 }
 510
 511 extern int
 512 hash_unhashed_stream(struct wim_lookup_table_entry *lte,
 513                      struct wim_lookup_table *lookup_table,
 514                      struct wim_lookup_table_entry **lte_ret);
 515
 516 extern struct wim_lookup_table_entry **
 517 retrieve_lte_pointer(struct wim_lookup_table_entry *lte);
 518
 519 #endif