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         /* (On-disk field)
 150          * Number of times this lookup table entry is referenced by dentries.
 151          * Unfortunately, this field is not always set correctly in Microsoft's
 152          * WIMs, so we have no choice but to fix it if more references to the
 153          * lookup table entry are found than stated here. */
 154         u32 refcnt;
 155
 156         union {
 157                 /* (On-disk field) SHA1 message digest of the stream referenced
 158                  * by this lookup table entry */
 159                 u8  hash[SHA1_HASH_SIZE];
 160
 161                 /* First 4 or 8 bytes of the SHA1 message digest, used for
 162                  * inserting the entry into the hash table.  Since the SHA1
 163                  * message digest can be considered random, we don't really need
 164                  * the full 20 byte hash just to insert the entry in a hash
 165                  * table. */
 166                 size_t hash_short;
 167
 168                 /* Unhashed entries only (unhashed == 1): these variables make
 169                  * it possible to find the pointer to this 'struct
 170                  * wim_lookup_table_entry' contained in either 'struct
 171                  * wim_ads_entry' or 'struct wim_inode'.  There can be at most 1
 172                  * such pointer, as we can only join duplicate streams after
 173                  * they have been hashed.  */
 174                 struct {
 175                         struct wim_inode *back_inode;
 176                         u32 back_stream_id;
 177                 };
 178         };
 179
 180         /* When a WIM file is written, out_refcnt starts at 0 and is incremented
 181          * whenever the stream pointed to by this lookup table entry needs to be
 182          * written.  The stream only need to be written when out_refcnt is
 183          * nonzero, since otherwise it is not referenced by any dentries. */
 184         u32 out_refcnt;
 185
 186         /* Pointers to somewhere where the stream is actually located.  See the
 187          * comments for the @resource_location field above. */
 188         union {
 189                 WIMStruct *wim;
 190                 tchar *file_on_disk;
 191                 void *attached_buffer;
 192         #ifdef WITH_FUSE
 193                 tchar *staging_file_name;
 194         #endif
 195         #ifdef WITH_NTFS_3G
 196                 struct ntfs_location *ntfs_loc;
 197         #endif
 198         };
 199
 200         /* Actual reference count to this stream (only used while
 201          * verifying an image). */
 202         u32 real_refcnt;
 203
 204         union {
 205         #ifdef WITH_FUSE
 206                 /* Number of times this stream has been opened (used only during
 207                  * mounting) */
 208                 u16 num_opened_fds;
 209         #endif
 210
 211                 /* This field is used for the special hardlink or symlink image
 212                  * extraction mode.   In these mode, all identical files are linked
 213                  * together, and @extracted_file will be set to the filename of the
 214                  * first extracted file containing this stream.  */
 215                 tchar *extracted_file;
 216         };
 217
 218         union {
 219                 /* When a WIM file is written, @output_resource_entry is filled
 220                  * in with the resource entry for the output WIM.  This will not
 221                  * necessarily be the same as the @resource_entry since: - The
 222                  * stream may have a different offset in the new WIM - The
 223                  * stream may have a different compressed size in the new WIM if
 224                  * the compression type changed
 225                  */
 226                 struct resource_entry output_resource_entry;
 227
 228                 struct {
 229                         struct list_head msg_list;
 230                         struct list_head being_compressed_list;
 231                 };
 232                 struct list_head inode_list;
 233
 234                 struct {
 235                         struct hlist_node hash_list_2;
 236
 237                         struct list_head write_streams_list;
 238                 };
 239         };
 240
 241         /* Temporary list fields */
 242         union {
 243                 struct list_head unhashed_list;
 244                 struct list_head swm_stream_list;
 245                 struct list_head extraction_list;
 246                 struct list_head export_stream_list;
 247         };
 248 };
 249
 250 static inline u64
 251 wim_resource_size(const struct wim_lookup_table_entry *lte)
 252 {
 253         return lte->resource_entry.original_size;
 254 }
 255
 256 static inline u64
 257 wim_resource_chunks(const struct wim_lookup_table_entry *lte)
 258 {
 259         return (wim_resource_size(lte) + WIM_CHUNK_SIZE - 1) / WIM_CHUNK_SIZE;
 260 }
 261
 262 static inline u64
 263 wim_resource_compressed_size(const struct wim_lookup_table_entry *lte)
 264 {
 265         return lte->resource_entry.size;
 266 }
 267
 268 /*
 269  * XXX Probably should store the compression type directly in the lookup table
 270  * entry
 271  */
 272 static inline int
 273 wim_resource_compression_type(const struct wim_lookup_table_entry *lte)
 274 {
 275         if (!(lte->resource_entry.flags & WIM_RESHDR_FLAG_COMPRESSED)
 276             || lte->resource_location != RESOURCE_IN_WIM)
 277                 return WIMLIB_COMPRESSION_TYPE_NONE;
 278         return wimlib_get_compression_type(lte->wim);
 279 }
 280
 281 static inline bool
 282 lte_filename_valid(const struct wim_lookup_table_entry *lte)
 283 {
 284         return lte->resource_location == RESOURCE_IN_FILE_ON_DISK
 285         #ifdef __WIN32__
 286                 || lte->resource_location == RESOURCE_WIN32
 287                 || lte->resource_location == RESOURCE_WIN32_ENCRYPTED
 288         #endif
 289         #ifdef WITH_FUSE
 290                 || lte->resource_location == RESOURCE_IN_STAGING_FILE
 291         #endif
 292                 ;
 293 }
 294
 295 extern struct wim_lookup_table *
 296 new_lookup_table(size_t capacity);
 297
 298 extern int
 299 read_lookup_table(WIMStruct *w);
 300
 301 extern int
 302 write_lookup_table(WIMStruct *w, int image, struct resource_entry *out_res_entry);
 303
 304 extern void
 305 free_lookup_table(struct wim_lookup_table *table);
 306
 307 extern void
 308 lookup_table_insert(struct wim_lookup_table *table, struct wim_lookup_table_entry *lte);
 309
 310 /* Unlinks a lookup table entry from the table; does not free it. */
 311 static inline void
 312 lookup_table_unlink(struct wim_lookup_table *table, struct wim_lookup_table_entry *lte)
 313 {
 314         wimlib_assert(!lte->unhashed);
 315         hlist_del(&lte->hash_list);
 316         wimlib_assert(table->num_entries != 0);
 317         table->num_entries--;
 318 }
 319
 320 extern struct wim_lookup_table_entry *
 321 new_lookup_table_entry();
 322
 323 extern struct wim_lookup_table_entry *
 324 clone_lookup_table_entry(const struct wim_lookup_table_entry *lte);
 325
 326 extern void
 327 print_lookup_table_entry(const struct wim_lookup_table_entry *entry,
 328                          FILE *out);
 329
 330 extern void
 331 free_lookup_table_entry(struct wim_lookup_table_entry *lte);
 332
 333 extern int
 334 for_lookup_table_entry(struct wim_lookup_table *table,
 335                        int (*visitor)(struct wim_lookup_table_entry *, void *),
 336                        void *arg);
 337
 338 extern int
 339 cmp_streams_by_wim_position(const void *p1, const void *p2);
 340
 341 extern int
 342 for_lookup_table_entry_pos_sorted(struct wim_lookup_table *table,
 343                                   int (*visitor)(struct wim_lookup_table_entry *,
 344                                                  void *),
 345                                   void *arg);
 346
 347 extern struct wim_lookup_table_entry *
 348 __lookup_resource(const struct wim_lookup_table *table, const u8 hash[]);
 349
 350 extern int
 351 lookup_resource(WIMStruct *w, const tchar *path,
 352                 int lookup_flags, struct wim_dentry **dentry_ret,
 353                 struct wim_lookup_table_entry **lte_ret, u16 *stream_idx_ret);
 354
 355 extern void
 356 lte_decrement_refcnt(struct wim_lookup_table_entry *lte,
 357                      struct wim_lookup_table *table);
 358 #ifdef WITH_FUSE
 359 extern void
 360 lte_decrement_num_opened_fds(struct wim_lookup_table_entry *lte);
 361 #endif
 362
 363 extern int
 364 lte_zero_out_refcnt(struct wim_lookup_table_entry *entry, void *ignore);
 365
 366 extern int
 367 lte_zero_real_refcnt(struct wim_lookup_table_entry *entry, void *ignore);
 368
 369 extern int
 370 lte_free_extracted_file(struct wim_lookup_table_entry *lte, void *ignore);
 371
 372 extern void
 373 inode_resolve_ltes(struct wim_inode *inode, struct wim_lookup_table *table);
 374
 375 extern void
 376 inode_unresolve_ltes(struct wim_inode *inode);
 377
 378 extern int
 379 write_lookup_table_entry(struct wim_lookup_table_entry *lte, void *__out);
 380
 381 static inline struct wim_lookup_table_entry *
 382 inode_stream_lte_resolved(const struct wim_inode *inode, unsigned stream_idx)
 383 {
 384         wimlib_assert(inode->i_resolved);
 385         wimlib_assert(stream_idx <= inode->i_num_ads);
 386         if (stream_idx == 0)
 387                 return inode->i_lte;
 388         else
 389                 return inode->i_ads_entries[stream_idx - 1].lte;
 390 }
 391
 392 static inline struct wim_lookup_table_entry *
 393 inode_stream_lte_unresolved(const struct wim_inode *inode, unsigned stream_idx,
 394                             const struct wim_lookup_table *table)
 395 {
 396         wimlib_assert(!inode->i_resolved);
 397         wimlib_assert(stream_idx <= inode->i_num_ads);
 398         if (!table)
 399                 return NULL;
 400         if (stream_idx == 0)
 401                 return __lookup_resource(table, inode->i_hash);
 402         else
 403                 return __lookup_resource(table,
 404                                          inode->i_ads_entries[
 405                                                 stream_idx - 1].hash);
 406 }
 407
 408 extern struct wim_lookup_table_entry *
 409 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
 410                  const struct wim_lookup_table *table);
 411
 412 static inline const u8 *
 413 inode_stream_hash_unresolved(const struct wim_inode *inode, unsigned stream_idx)
 414 {
 415         wimlib_assert(!inode->i_resolved);
 416         wimlib_assert(stream_idx <= inode->i_num_ads);
 417         if (stream_idx == 0)
 418                 return inode->i_hash;
 419         else
 420                 return inode->i_ads_entries[stream_idx - 1].hash;
 421 }
 422
 423
 424 static inline const u8 *
 425 inode_stream_hash_resolved(const struct wim_inode *inode, unsigned stream_idx)
 426 {
 427         struct wim_lookup_table_entry *lte;
 428         lte = inode_stream_lte_resolved(inode, stream_idx);
 429         if (lte)
 430                 return lte->hash;
 431         else
 432                 return zero_hash;
 433 }
 434
 435 /*
 436  * Returns the hash for stream @stream_idx of the inode, where stream_idx = 0
 437  * means the default un-named file stream, and stream_idx >= 1 corresponds to an
 438  * alternate data stream.
 439  *
 440  * This works for both resolved and un-resolved dentries.
 441  */
 442 static inline const u8 *
 443 inode_stream_hash(const struct wim_inode *inode, unsigned stream_idx)
 444 {
 445         if (inode->i_resolved)
 446                 return inode_stream_hash_resolved(inode, stream_idx);
 447         else
 448                 return inode_stream_hash_unresolved(inode, stream_idx);
 449 }
 450
 451 static inline u16
 452 inode_stream_name_nbytes(const struct wim_inode *inode, unsigned stream_idx)
 453 {
 454         wimlib_assert(stream_idx <= inode->i_num_ads);
 455         if (stream_idx == 0)
 456                 return 0;
 457         else
 458                 return inode->i_ads_entries[stream_idx - 1].stream_name_nbytes;
 459 }
 460
 461 static inline struct wim_lookup_table_entry *
 462 inode_unnamed_lte_resolved(const struct wim_inode *inode)
 463 {
 464         wimlib_assert(inode->i_resolved);
 465         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
 466                 if (inode_stream_name_nbytes(inode, i) == 0 &&
 467                     !is_zero_hash(inode_stream_hash_resolved(inode, i)))
 468                 {
 469                         return inode_stream_lte_resolved(inode, i);
 470                 }
 471         }
 472         return NULL;
 473 }
 474
 475 static inline struct wim_lookup_table_entry *
 476 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
 477                              const struct wim_lookup_table *table)
 478 {
 479         wimlib_assert(!inode->i_resolved);
 480         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
 481                 if (inode_stream_name_nbytes(inode, i) == 0 &&
 482                     !is_zero_hash(inode_stream_hash_unresolved(inode, i)))
 483                 {
 484                         return inode_stream_lte_unresolved(inode, i, table);
 485                 }
 486         }
 487         return NULL;
 488 }
 489
 490 extern struct wim_lookup_table_entry *
 491 inode_unnamed_lte(const struct wim_inode *inode, const struct wim_lookup_table *table);
 492
 493 extern u64
 494 lookup_table_total_stream_size(struct wim_lookup_table *table);
 495
 496
 497 static inline void
 498 lookup_table_insert_unhashed(struct wim_lookup_table *table,
 499                              struct wim_lookup_table_entry *lte,
 500                              struct wim_inode *back_inode,
 501                              u32 back_stream_id)
 502 {
 503         lte->unhashed = 1;
 504         lte->back_inode = back_inode;
 505         lte->back_stream_id = back_stream_id;
 506         list_add_tail(&lte->unhashed_list, table->unhashed_streams);
 507 }
 508
 509 extern int
 510 hash_unhashed_stream(struct wim_lookup_table_entry *lte,
 511                      struct wim_lookup_table *lookup_table,
 512                      struct wim_lookup_table_entry **lte_ret);
 513
 514 extern struct wim_lookup_table_entry **
 515 retrieve_lte_pointer(struct wim_lookup_table_entry *lte);
 516
 517 #endif