Cleanup
[wimlib] / include / wimlib / lookup_table.h
1 #ifndef _WIMLIB_LOOKUP_TABLE_H
2 #define _WIMLIB_LOOKUP_TABLE_H
3
4 #include "wimlib/assert.h"
5 #include "wimlib/dentry.h"
6 #include "wimlib/list.h"
7 #include "wimlib/sha1.h"
8 #include "wimlib/types.h"
9 #include "wimlib/wim.h"
10
11 #define LOOKUP_FLAG_ADS_OK              0x00000001
12 #define LOOKUP_FLAG_DIRECTORY_OK        0x00000002
13
14
15 /* The lookup table of a WIM file maps SHA1 message digests to streams of data.
16  * Here, the in-memory structure is implemented as a hash table.
17  *
18  * Given a SHA1 message digest, the mapped-to stream is specified by an offset
19  * in the WIM, an uncompressed and compressed size, and resource flags (see
20  * 'struct resource_entry').  But, we associate additional information, such as
21  * a reference count, with each stream, so the actual mapping is from SHA1
22  * message digests to 'struct wim_lookup_table_entry's, each of which contains
23  * an embedded 'struct resource_entry'.
24  *
25  * Note: Everything will break horribly if there is a SHA1 collision.
26  */
27 struct wim_lookup_table {
28         struct hlist_head *array;
29         u64 num_entries;
30         u64 capacity;
31         struct list_head *unhashed_streams;
32 };
33
34 #ifdef WITH_NTFS_3G
35
36 struct _ntfs_volume;
37
38 struct ntfs_location {
39         tchar *path;
40         utf16lechar *stream_name;
41         u16 stream_name_nchars;
42         struct _ntfs_volume *ntfs_vol;
43         bool is_reparse_point;
44 };
45 #endif
46
47 /* An enumerated type that identifies where the stream corresponding to this
48  * lookup table entry is actually located.
49  *
50  * If we open a WIM and read its lookup table, the location is set to
51  * RESOURCE_IN_WIM since all the streams will initially be located in the WIM.
52  * However, to handle situations such as image capture and image mount, we allow
53  * the actual location of the stream to be somewhere else, such as an external
54  * file.
55  */
56 enum resource_location {
57         /* The lookup table entry does not yet correspond to a stream; this is a
58          * temporary state only.  */
59         RESOURCE_NONEXISTENT = 0,
60
61         /* The stream is located in a resource in a WIM file identified by the
62          * `struct wim_resource_spec' pointed to by @rspec.  @offset_in_res
63          * identifies the offset at which this particular stream begins in the
64          * uncompressed data of the resource; this is normally 0, but in general
65          * a WIM resource may be "packed" and potentially contain multiple
66          * streams.  */
67         RESOURCE_IN_WIM,
68
69         /* The stream is located in the external file named by @file_on_disk.
70          * On Windows, @file_on_disk may actually specify a named data stream
71          * (file path, then colon, then name of the stream).  */
72         RESOURCE_IN_FILE_ON_DISK,
73
74         /* The stream is directly attached in the in-memory buffer pointed to by
75          * @attached_buffer.  */
76         RESOURCE_IN_ATTACHED_BUFFER,
77
78 #ifdef WITH_FUSE
79         /* The stream is located in the external file named by
80          * @staging_file_name, located in the staging directory for a read-write
81          * mount.  */
82         RESOURCE_IN_STAGING_FILE,
83 #endif
84
85 #ifdef WITH_NTFS_3G
86         /* The stream is located in an NTFS volume.  It is identified by volume,
87          * filename, data stream name, and by whether it is a reparse point or
88          * not.  @ntfs_loc points to a structure containing this information.
89          * */
90         RESOURCE_IN_NTFS_VOLUME,
91 #endif
92
93 #ifdef __WIN32__
94         /* Windows only: the stream is located in the external file named by
95          * @file_on_disk, but the file is encrypted and must be read using the
96          * appropriate Windows API.  */
97         RESOURCE_WIN32_ENCRYPTED,
98 #endif
99
100 };
101
102 /* Specification for a stream, which may be the contents of a file (unnamed data
103  * stream), a named data stream, reparse point data, or a WIM metadata resource.
104  *
105  * One instance of this structure is created for each entry in the WIM's lookup
106  * table, hence the name of the struct.  Each of these entries contains the SHA1
107  * message digest of a stream and the location of the stream data in the WIM
108  * file (size, location, flags).  The in-memory lookup table is a map from SHA1
109  * message digests to stream locations.  */
110 struct wim_lookup_table_entry {
111
112         /* List node for a hash bucket of the lookup table.  */
113         struct hlist_node hash_list;
114
115         /* Uncompressed size of this stream.  */
116         u64 size;
117
118         /* Stream flags (WIM_RESHDR_FLAG_*).  */
119         u32 flags : 8;
120
121         /* One of the `enum resource_location' values documented above.  */
122         u32 resource_location : 4;
123
124         /* 1 if this stream has not had a SHA1 message digest calculated for it
125          * yet.  */
126         u32 unhashed : 1;
127
128         /* Temoorary fields used when writing streams; set as documented for
129          * prepare_stream_list_for_write().  */
130         u32 unique_size : 1;
131         u32 will_be_in_output_wim : 1;
132
133         /* Set to 1 when a metadata entry has its checksum changed; in such
134          * cases the hash cannot be used to verify the data if the metadata
135          * resource is read again.  (This could be avoided if we used separate
136          * fields for input/output checksum, but most stream entries wouldn't
137          * need this.)  */
138         u32 dont_check_metadata_hash : 1;
139
140         union {
141                 /* (On-disk field) SHA1 message digest of the stream referenced
142                  * by this lookup table entry.  */
143                 u8  hash[SHA1_HASH_SIZE];
144
145                 /* First 4 or 8 bytes of the SHA1 message digest, used for
146                  * inserting the entry into the hash table.  Since the SHA1
147                  * message digest can be considered random, we don't really need
148                  * the full 20 byte hash just to insert the entry in a hash
149                  * table.  */
150                 size_t hash_short;
151
152                 /* Unhashed entries only (unhashed == 1): these variables make
153                  * it possible to find the pointer to this 'struct
154                  * wim_lookup_table_entry' contained in either 'struct
155                  * wim_ads_entry' or 'struct wim_inode'.  There can be at most 1
156                  * such pointer, as we can only join duplicate streams after
157                  * they have been hashed.  */
158                 struct {
159                         struct wim_inode *back_inode;
160                         u32 back_stream_id;
161                 };
162         };
163
164         /* Number of times this lookup table entry is referenced by dentries in
165          * the WIM.  When a WIM's lookup table is read, this field is
166          * initialized from a corresponding entry; while it should be correct,
167          * in general it may not be.  wim_recalculate_refcnts() recalculates the
168          * reference counts for all streams and is run before doing any
169          * deletions.  */
170         u32 refcnt;
171
172         /* When a WIM file is written, this is set to the number of references
173          * (by dentries) to this stream in the output WIM file.
174          *
175          * During extraction, this is set to the number of times the stream must
176          * be extracted.
177          *
178          * During image export, this is set to the number of references of this
179          * stream that originated from the source WIM.  */
180         u32 out_refcnt;
181
182 #ifdef WITH_FUSE
183         /* Number of times this stream has been opened; used only during
184          * mounting.  */
185         u16 num_opened_fds;
186 #endif
187
188         /* Specification of where this stream is actually located.  Which member
189          * is valid is determined by the @resource_location field.  */
190         union {
191                 struct {
192                         struct wim_resource_spec *rspec;
193                         u64 offset_in_res;
194                 };
195                 tchar *file_on_disk;
196                 void *attached_buffer;
197         #ifdef WITH_FUSE
198                 tchar *staging_file_name;
199         #endif
200         #ifdef WITH_NTFS_3G
201                 struct ntfs_location *ntfs_loc;
202         #endif
203         };
204
205         /* Links together streams that share the same underlying WIM resource.
206          * The head is the `stream_list' member of `struct wim_resource_spec'.
207          */
208         struct list_head rspec_node;
209
210         /* This field is used during the hardlink and symlink image extraction
211          * modes.   In these modes, all identical files are linked together, and
212          * @extracted_file will be set to the filename of the first extracted
213          * file containing this stream.  */
214         tchar *extracted_file;
215
216         /* Temporary fields  */
217         union {
218                 /* Fields used temporarily during WIM file writing.  */
219                 struct {
220                         union {
221                                 /* List node used for stream size table.  */
222                                 struct hlist_node hash_list_2;
223
224                                 /* Metadata for the underlying packed resource
225                                  * in the WIM being written (only valid if
226                                  * WIM_RESHDR_FLAG_PACKED_STREAMS set in
227                                  * out_reshdr.flags).  */
228                                 struct {
229                                         u64 out_res_offset_in_wim;
230                                         u64 out_res_size_in_wim;
231                                 };
232                         };
233
234                         /* Links streams being written to the WIM.  */
235                         struct list_head write_streams_list;
236
237                         /* Metadata for this stream in the WIM being written.
238                          */
239                         struct wim_reshdr out_reshdr;
240                 };
241
242                 /* Used temporarily during extraction  */
243                 union {
244                         /* Dentries to extract that reference this stream.
245                          * out_refcnt tracks the number of slots filled.  */
246                         struct wim_dentry *inline_lte_dentries[7];
247                         struct {
248                                 struct wim_dentry **lte_dentries;
249                                 size_t alloc_lte_dentries;
250                         };
251                 };
252
253                 /* Actual reference count to this stream (only used while
254                  * verifying an image).  */
255                 u32 real_refcnt;
256         };
257
258         /* Temporary list fields.  */
259         union {
260                 /* Links streams for writing lookup table.  */
261                 struct list_head lookup_table_list;
262
263                 /* Links streams being extracted.  */
264                 struct list_head extraction_list;
265
266                 /* Links streams being exported.  */
267                 struct list_head export_stream_list;
268         };
269
270         /* Links streams that are still unhashed after being been added to a
271          * WIM.  */
272         struct list_head unhashed_list;
273 };
274
275 static inline bool
276 lte_is_partial(const struct wim_lookup_table_entry * lte)
277 {
278         return lte->resource_location == RESOURCE_IN_WIM &&
279                lte->size != lte->rspec->uncompressed_size;
280 }
281
282 static inline bool
283 lte_filename_valid(const struct wim_lookup_table_entry *lte)
284 {
285         return     lte->resource_location == RESOURCE_IN_FILE_ON_DISK
286         #ifdef __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) _malloc_attribute;
297
298 extern int
299 read_wim_lookup_table(WIMStruct *wim);
300
301 extern int
302 write_wim_lookup_table_from_stream_list(struct list_head *stream_list,
303                                         struct filedes *out_fd,
304                                         u16 part_number,
305                                         struct wim_reshdr *out_reshdr,
306                                         int write_resource_flags,
307                                         struct wimlib_lzx_context **comp_ctx);
308
309 extern void
310 free_lookup_table(struct wim_lookup_table *table);
311
312 extern void
313 lookup_table_insert(struct wim_lookup_table *table, struct wim_lookup_table_entry *lte);
314
315 /* Unlinks a lookup table entry from the table; does not free it.  */
316 static inline void
317 lookup_table_unlink(struct wim_lookup_table *table, struct wim_lookup_table_entry *lte)
318 {
319         wimlib_assert(!lte->unhashed);
320         hlist_del(&lte->hash_list);
321         wimlib_assert(table->num_entries != 0);
322         table->num_entries--;
323 }
324
325 extern struct wim_lookup_table_entry *
326 new_lookup_table_entry(void) _malloc_attribute;
327
328 extern struct wim_lookup_table_entry *
329 clone_lookup_table_entry(const struct wim_lookup_table_entry *lte)
330                         _malloc_attribute;
331
332 extern void
333 print_lookup_table_entry(const struct wim_lookup_table_entry *lte, FILE *out);
334
335 extern void
336 free_lookup_table_entry(struct wim_lookup_table_entry *lte);
337
338 extern void
339 lte_to_wimlib_resource_entry(const struct wim_lookup_table_entry *lte,
340                              struct wimlib_resource_entry *wentry);
341
342 extern int
343 for_lookup_table_entry(struct wim_lookup_table *table,
344                        int (*visitor)(struct wim_lookup_table_entry *, void *),
345                        void *arg);
346
347 extern int
348 sort_stream_list(struct list_head *stream_list,
349                  size_t list_head_offset,
350                  int (*compar)(const void *, const void*));
351
352 extern int
353 sort_stream_list_by_sequential_order(struct list_head *stream_list,
354                                      size_t list_head_offset);
355
356 extern int
357 for_lookup_table_entry_pos_sorted(struct wim_lookup_table *table,
358                                   int (*visitor)(struct wim_lookup_table_entry *,
359                                                  void *),
360                                   void *arg);
361
362 extern struct wim_lookup_table_entry *
363 lookup_resource(const struct wim_lookup_table *table, const u8 hash[]);
364
365 extern int
366 wim_pathname_to_stream(WIMStruct *wim, const tchar *path,
367                        int lookup_flags,
368                        struct wim_dentry **dentry_ret,
369                        struct wim_lookup_table_entry **lte_ret,
370                        u16 *stream_idx_ret);
371
372 extern void
373 lte_decrement_refcnt(struct wim_lookup_table_entry *lte,
374                      struct wim_lookup_table *table);
375 #ifdef WITH_FUSE
376 extern void
377 lte_decrement_num_opened_fds(struct wim_lookup_table_entry *lte);
378 #endif
379
380 extern int
381 lte_zero_out_refcnt(struct wim_lookup_table_entry *lte, void *ignore);
382
383 extern int
384 lte_zero_real_refcnt(struct wim_lookup_table_entry *lte, void *ignore);
385
386 extern int
387 lte_free_extracted_file(struct wim_lookup_table_entry *lte, void *ignore);
388
389 static inline void
390 lte_bind_wim_resource_spec(struct wim_lookup_table_entry *lte,
391                            struct wim_resource_spec *rspec)
392 {
393         lte->resource_location = RESOURCE_IN_WIM;
394         lte->rspec = rspec;
395         list_add_tail(&lte->rspec_node, &rspec->stream_list);
396 }
397
398 static inline void
399 lte_unbind_wim_resource_spec(struct wim_lookup_table_entry *lte)
400 {
401         list_del(&lte->rspec_node);
402         lte->resource_location = RESOURCE_NONEXISTENT;
403 }
404
405 extern int
406 inode_resolve_ltes(struct wim_inode *inode, struct wim_lookup_table *table,
407                    bool force);
408
409 extern int
410 resource_not_found_error(const struct wim_inode *inode, const u8 *hash);
411
412 extern void
413 inode_unresolve_ltes(struct wim_inode *inode);
414
415 static inline struct wim_lookup_table_entry *
416 inode_stream_lte_resolved(const struct wim_inode *inode, unsigned stream_idx)
417 {
418         wimlib_assert(inode->i_resolved);
419         wimlib_assert(stream_idx <= inode->i_num_ads);
420         if (stream_idx == 0)
421                 return inode->i_lte;
422         else
423                 return inode->i_ads_entries[stream_idx - 1].lte;
424 }
425
426 static inline struct wim_lookup_table_entry *
427 inode_stream_lte_unresolved(const struct wim_inode *inode, unsigned stream_idx,
428                             const struct wim_lookup_table *table)
429 {
430         wimlib_assert(!inode->i_resolved);
431         wimlib_assert(stream_idx <= inode->i_num_ads);
432         if (!table)
433                 return NULL;
434         if (stream_idx == 0)
435                 return lookup_resource(table, inode->i_hash);
436         else
437                 return lookup_resource(table,
438                                          inode->i_ads_entries[
439                                                 stream_idx - 1].hash);
440 }
441
442 extern struct wim_lookup_table_entry *
443 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
444                  const struct wim_lookup_table *table);
445
446 static inline const u8 *
447 inode_stream_hash_unresolved(const struct wim_inode *inode, unsigned stream_idx)
448 {
449         wimlib_assert(!inode->i_resolved);
450         wimlib_assert(stream_idx <= inode->i_num_ads);
451         if (stream_idx == 0)
452                 return inode->i_hash;
453         else
454                 return inode->i_ads_entries[stream_idx - 1].hash;
455 }
456
457
458 static inline const u8 *
459 inode_stream_hash_resolved(const struct wim_inode *inode, unsigned stream_idx)
460 {
461         struct wim_lookup_table_entry *lte;
462         lte = inode_stream_lte_resolved(inode, stream_idx);
463         if (lte)
464                 return lte->hash;
465         else
466                 return zero_hash;
467 }
468
469 /*
470  * Returns the hash for stream @stream_idx of the inode, where stream_idx = 0
471  * means the default un-named file stream, and stream_idx >= 1 corresponds to an
472  * alternate data stream.
473  *
474  * This works for both resolved and un-resolved dentries.
475  */
476 static inline const u8 *
477 inode_stream_hash(const struct wim_inode *inode, unsigned stream_idx)
478 {
479         if (inode->i_resolved)
480                 return inode_stream_hash_resolved(inode, stream_idx);
481         else
482                 return inode_stream_hash_unresolved(inode, stream_idx);
483 }
484
485 static inline u16
486 inode_stream_name_nbytes(const struct wim_inode *inode, unsigned stream_idx)
487 {
488         wimlib_assert(stream_idx <= inode->i_num_ads);
489         if (stream_idx == 0)
490                 return 0;
491         else
492                 return inode->i_ads_entries[stream_idx - 1].stream_name_nbytes;
493 }
494
495 extern struct wim_lookup_table_entry *
496 inode_unnamed_stream_resolved(const struct wim_inode *inode, u16 *stream_idx_ret);
497
498 extern struct wim_lookup_table_entry *
499 inode_unnamed_lte_resolved(const struct wim_inode *inode);
500
501 extern struct wim_lookup_table_entry *
502 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
503                              const struct wim_lookup_table *table);
504
505 extern struct wim_lookup_table_entry *
506 inode_unnamed_lte(const struct wim_inode *inode, const struct wim_lookup_table *table);
507
508 extern const u8 *
509 inode_unnamed_stream_hash(const struct wim_inode *inode);
510
511 static inline void
512 lookup_table_insert_unhashed(struct wim_lookup_table *table,
513                              struct wim_lookup_table_entry *lte,
514                              struct wim_inode *back_inode,
515                              u32 back_stream_id)
516 {
517         lte->unhashed = 1;
518         lte->back_inode = back_inode;
519         lte->back_stream_id = back_stream_id;
520         list_add_tail(&lte->unhashed_list, table->unhashed_streams);
521 }
522
523 extern int
524 hash_unhashed_stream(struct wim_lookup_table_entry *lte,
525                      struct wim_lookup_table *lookup_table,
526                      struct wim_lookup_table_entry **lte_ret);
527
528 extern struct wim_lookup_table_entry **
529 retrieve_lte_pointer(struct wim_lookup_table_entry *lte);
530
531 #endif /* _WIMLIB_LOOKUP_TABLE_H */