Do not use ADS entry workaround on encrypted files
[wimlib] / src / dentry.c
1 /*
2  * dentry.c - see description below
3  */
4
5 /*
6  * Copyright (C) 2012, 2013, 2014 Eric Biggers
7  *
8  * This file is free software; you can redistribute it and/or modify it under
9  * the terms of the GNU Lesser General Public License as published by the Free
10  * Software Foundation; either version 3 of the License, or (at your option) any
11  * later version.
12  *
13  * This file is distributed in the hope that it will be useful, but WITHOUT
14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
16  * details.
17  *
18  * You should have received a copy of the GNU Lesser General Public License
19  * along with this file; if not, see http://www.gnu.org/licenses/.
20  */
21
22 /*
23  * This file contains logic to deal with WIM directory entries, or "dentries":
24  *
25  *  - Reading a dentry tree from a metadata resource in a WIM file
26  *  - Writing a dentry tree to a metadata resource in a WIM file
27  *  - Iterating through a tree of WIM dentries
28  *  - Path lookup: translating a path into a WIM dentry or inode
29  *  - Creating, modifying, and deleting WIM dentries
30  *
31  * Notes:
32  *
33  *  - A WIM file can contain multiple images, each of which has an independent
34  *    tree of dentries.  "On disk", the dentry tree for an image is stored in
35  *    the "metadata resource" for that image.
36  *
37  *  - Multiple dentries in an image may correspond to the same inode, or "file".
38  *    When this occurs, it means that the file has multiple names, or "hard
39  *    links".  A dentry is not a file, but rather the name of a file!
40  *
41  *  - Inodes are not represented explicitly in the WIM file format.  Instead,
42  *    the metadata resource provides a "hard link group ID" for each dentry.
43  *    wimlib handles pulling out actual inodes from this information, but this
44  *    occurs in inode_fixup.c and not in this file.
45  *
46  *  - wimlib does not allow *directory* hard links, so a WIM image really does
47  *    have a *tree* of dentries (and not an arbitrary graph of dentries).
48  *
49  *  - wimlib indexes dentries both case-insensitively and case-sensitively,
50  *    allowing either behavior to be used for path lookup.
51  *
52  *  - Multiple dentries in a directory might have the same case-insensitive
53  *    name.  But wimlib enforces that at most one dentry in a directory can have
54  *    a given case-sensitive name.
55  */
56
57 #ifdef HAVE_CONFIG_H
58 #  include "config.h"
59 #endif
60
61 #include <errno.h>
62
63 #include "wimlib/assert.h"
64 #include "wimlib/dentry.h"
65 #include "wimlib/inode.h"
66 #include "wimlib/encoding.h"
67 #include "wimlib/endianness.h"
68 #include "wimlib/metadata.h"
69 #include "wimlib/paths.h"
70
71 /* On-disk format of a WIM dentry (directory entry), located in the metadata
72  * resource for a WIM image.  */
73 struct wim_dentry_on_disk {
74
75         /* Length of this directory entry in bytes, not including any alternate
76          * data stream entries.  Should be a multiple of 8 so that the following
77          * dentry or alternate data stream entry is aligned on an 8-byte
78          * boundary.  (If not, wimlib will round it up.)  It must be at least as
79          * long as the fixed-length fields of the dentry (WIM_DENTRY_DISK_SIZE),
80          * plus the lengths of the file name and/or short name if present.
81          *
82          * It is also possible for this field to be 0.  This situation, which is
83          * undocumented, indicates the end of a list of sibling nodes in a
84          * directory.  It also means the real length is 8, because the dentry
85          * included only the length field, but that takes up 8 bytes.  */
86         le64 length;
87
88         /* Attributes of the file or directory.  This is a bitwise OR of the
89          * FILE_ATTRIBUTE_* constants and should correspond to the value
90          * retrieved by GetFileAttributes() on Windows. */
91         le32 attributes;
92
93         /* A value that specifies the security descriptor for this file or
94          * directory.  If -1, the file or directory has no security descriptor.
95          * Otherwise, it is a 0-based index into the WIM image's table of
96          * security descriptors (see: `struct wim_security_data') */
97         sle32 security_id;
98
99         /* Offset, in bytes, from the start of the uncompressed metadata
100          * resource of this directory's child directory entries, or 0 if this
101          * directory entry does not correspond to a directory or otherwise does
102          * not have any children. */
103         le64 subdir_offset;
104
105         /* Reserved fields */
106         le64 unused_1;
107         le64 unused_2;
108
109         /* Creation time, last access time, and last write time, in
110          * 100-nanosecond intervals since 12:00 a.m UTC January 1, 1601.  They
111          * should correspond to the times gotten by calling GetFileTime() on
112          * Windows. */
113         le64 creation_time;
114         le64 last_access_time;
115         le64 last_write_time;
116
117         /* Vaguely, the SHA-1 message digest ("hash") of the file's contents.
118          * More specifically, this is for the "unnamed data stream" rather than
119          * any "alternate data streams".  This hash value is used to look up the
120          * corresponding entry in the WIM's stream lookup table to actually find
121          * the file contents within the WIM.
122          *
123          * If the file has no unnamed data stream (e.g. is a directory), then
124          * this field will be all zeroes.  If the unnamed data stream is empty
125          * (i.e. an "empty file"), then this field is also expected to be all
126          * zeroes.  (It will be if wimlib created the WIM image, at least;
127          * otherwise it can't be ruled out that the SHA-1 message digest of 0
128          * bytes of data is given explicitly.)
129          *
130          * If the file has reparse data, then this field will instead specify
131          * the SHA-1 message digest of the reparse data.  If it is somehow
132          * possible for a file to have both an unnamed data stream and reparse
133          * data, then this is not handled by wimlib.
134          *
135          * As a further special case, if this field is all zeroes but there is
136          * an alternate data stream entry with no name and a nonzero SHA-1
137          * message digest field, then that hash must be used instead of this
138          * one.  In fact, when named data streams are present, some versions of
139          * Windows PE contain a bug where they only look in the alternate data
140          * stream entries for the unnamed data stream, not here.
141          */
142         u8 unnamed_stream_hash[SHA1_HASH_SIZE];
143
144         /* The format of the following data is not yet completely known and they
145          * do not correspond to Microsoft's documentation.
146          *
147          * If this directory entry is for a reparse point (has
148          * FILE_ATTRIBUTE_REPARSE_POINT set in the attributes field), then the
149          * version of the following fields containing the reparse tag is valid.
150          * Furthermore, the field notated as not_rpfixed, as far as I can tell,
151          * is supposed to be set to 1 if reparse point fixups (a.k.a. fixing the
152          * targets of absolute symbolic links) were *not* done, and otherwise 0.
153          *
154          * If this directory entry is not for a reparse point, then the version
155          * of the following fields containing the hard_link_group_id is valid.
156          * All MS says about this field is that "If this file is part of a hard
157          * link set, all the directory entries in the set will share the same
158          * value in this field.".  However, more specifically I have observed
159          * the following:
160          *    - If the file is part of a hard link set of size 1, then the
161          *    hard_link_group_id should be set to either 0, which is treated
162          *    specially as indicating "not hardlinked", or any unique value.
163          *    - The specific nonzero values used to identity hard link sets do
164          *    not matter, as long as they are unique.
165          *    - However, due to bugs in Microsoft's software, it is actually NOT
166          *    guaranteed that directory entries that share the same hard link
167          *    group ID are actually hard linked to each either.  See
168          *    inode_fixup.c for the code that handles this.
169          */
170         union {
171                 struct {
172                         le32 rp_unknown_1;
173                         le32 reparse_tag;
174                         le16 rp_unknown_2;
175                         le16 not_rpfixed;
176                 } _packed_attribute reparse;
177                 struct {
178                         le32 rp_unknown_1;
179                         le64 hard_link_group_id;
180                 } _packed_attribute nonreparse;
181         };
182
183         /* Number of alternate data stream entries that directly follow this
184          * dentry on-disk. */
185         le16 num_alternate_data_streams;
186
187         /* If nonzero, this is the length, in bytes, of this dentry's UTF-16LE
188          * encoded short name (8.3 DOS-compatible name), excluding the null
189          * terminator.  If zero, then the long name of this dentry does not have
190          * a corresponding short name (but this does not exclude the possibility
191          * that another dentry for the same file has a short name).  */
192         le16 short_name_nbytes;
193
194         /* If nonzero, this is the length, in bytes, of this dentry's UTF-16LE
195          * encoded "long" name, excluding the null terminator.  If zero, then
196          * this file has no long name.  The root dentry should not have a long
197          * name, but all other dentries in the image should have long names.  */
198         le16 file_name_nbytes;
199
200         /* Beginning of optional, variable-length fields  */
201
202         /* If file_name_nbytes != 0, the next field will be the UTF-16LE encoded
203          * long file name.  This will be null-terminated, so the size of this
204          * field will really be file_name_nbytes + 2.  */
205         /*utf16lechar file_name[];*/
206
207         /* If short_name_nbytes != 0, the next field will be the UTF-16LE
208          * encoded short name.  This will be null-terminated, so the size of
209          * this field will really be short_name_nbytes + 2.  */
210         /*utf16lechar short_name[];*/
211
212         /* If there is still space in the dentry (according to the 'length'
213          * field) after 8-byte alignment, then the remaining space will be a
214          * variable-length list of tagged metadata items.  See tagged_items.c
215          * for more information.  */
216         /* u8 tagged_items[] _aligned_attribute(8); */
217
218 } _packed_attribute;
219         /* If num_alternate_data_streams != 0, then there are that many
220          * alternate data stream entries following the dentry, on an 8-byte
221          * aligned boundary.  They are not counted in the 'length' field of the
222          * dentry.  */
223
224 /* Calculate the minimum unaligned length, in bytes, of an on-disk WIM dentry
225  * that has names of the specified lengths.  (Zero length means the
226  * corresponding name actually does not exist.)  The returned value excludes
227  * tagged metadata items as well as any alternate data stream entries that may
228  * need to follow the dentry.  */
229 static u64
230 dentry_min_len_with_names(u16 file_name_nbytes, u16 short_name_nbytes)
231 {
232         u64 length = sizeof(struct wim_dentry_on_disk);
233         if (file_name_nbytes)
234                 length += (u32)file_name_nbytes + 2;
235         if (short_name_nbytes)
236                 length += (u32)short_name_nbytes + 2;
237         return length;
238 }
239
240 static void
241 do_dentry_set_name(struct wim_dentry *dentry, utf16lechar *file_name,
242                    size_t file_name_nbytes)
243 {
244         FREE(dentry->file_name);
245         dentry->file_name = file_name;
246         dentry->file_name_nbytes = file_name_nbytes;
247
248         if (dentry_has_short_name(dentry)) {
249                 FREE(dentry->short_name);
250                 dentry->short_name = NULL;
251                 dentry->short_name_nbytes = 0;
252         }
253 }
254
255 /*
256  * Set the name of a WIM dentry from a UTF-16LE string.
257  *
258  * This sets the long name of the dentry.  The short name will automatically be
259  * removed, since it may not be appropriate for the new long name.
260  *
261  * The @name string need not be null-terminated, since its length is specified
262  * in @name_nbytes.
263  *
264  * If @name_nbytes is 0, both the long and short names of the dentry will be
265  * removed.
266  *
267  * Only use this function on unlinked dentries, since it doesn't update the name
268  * indices.  For dentries that are currently linked into the tree, use
269  * rename_wim_path().
270  *
271  * Returns 0 or WIMLIB_ERR_NOMEM.
272  */
273 int
274 dentry_set_name_utf16le(struct wim_dentry *dentry, const utf16lechar *name,
275                         size_t name_nbytes)
276 {
277         utf16lechar *dup = NULL;
278
279         if (name_nbytes) {
280                 dup = utf16le_dupz(name, name_nbytes);
281                 if (!dup)
282                         return WIMLIB_ERR_NOMEM;
283         }
284         do_dentry_set_name(dentry, dup, name_nbytes);
285         return 0;
286 }
287
288
289 /*
290  * Set the name of a WIM dentry from a 'tchar' string.
291  *
292  * This sets the long name of the dentry.  The short name will automatically be
293  * removed, since it may not be appropriate for the new long name.
294  *
295  * If @name is NULL or empty, both the long and short names of the dentry will
296  * be removed.
297  *
298  * Only use this function on unlinked dentries, since it doesn't update the name
299  * indices.  For dentries that are currently linked into the tree, use
300  * rename_wim_path().
301  *
302  * Returns 0 or an error code resulting from a failed string conversion.
303  */
304 int
305 dentry_set_name(struct wim_dentry *dentry, const tchar *name)
306 {
307         utf16lechar *name_utf16le = NULL;
308         size_t name_utf16le_nbytes = 0;
309         int ret;
310
311         if (name && *name) {
312                 ret = tstr_to_utf16le(name, tstrlen(name) * sizeof(tchar),
313                                       &name_utf16le, &name_utf16le_nbytes);
314                 if (ret)
315                         return ret;
316         }
317
318         do_dentry_set_name(dentry, name_utf16le, name_utf16le_nbytes);
319         return 0;
320 }
321
322 /* Return the length, in bytes, required for the specified alternate data stream
323  * (ADS) entry on-disk.  This accounts for the fixed-length portion of the ADS
324  * entry, the {stream name and its null terminator} if present, and the padding
325  * after the entry to align the next ADS entry or dentry on an 8-byte boundary
326  * in the uncompressed metadata resource buffer.  */
327 static u64
328 ads_entry_out_total_length(const struct wim_ads_entry *entry)
329 {
330         u64 len = sizeof(struct wim_ads_entry_on_disk);
331         if (entry->stream_name_nbytes)
332                 len += (u32)entry->stream_name_nbytes + 2;
333         return (len + 7) & ~7;
334 }
335
336 /*
337  * Determine whether to include a "dummy" stream when writing a WIM dentry.
338  *
339  * Some versions of Microsoft's WIM software (the boot driver(s) in WinPE 3.0,
340  * for example) contain a bug where they assume the first alternate data stream
341  * (ADS) entry of a dentry with a nonzero ADS count specifies the unnamed
342  * stream, even if it has a name and the unnamed stream is already specified in
343  * the hash field of the dentry itself.
344  *
345  * wimlib has to work around this behavior by carefully emulating the behavior
346  * of (most versions of) ImageX/WIMGAPI, which move the unnamed stream reference
347  * into the alternate stream entries whenever there are named data streams, even
348  * though there is already a field in the dentry itself for the unnamed stream
349  * reference, which then goes to waste.
350  */
351 static bool
352 inode_needs_dummy_stream(const struct wim_inode *inode)
353 {
354         /* Normal case  */
355         if (likely(inode->i_num_ads <= 0))
356                 return false;
357
358         /* Overflow check  */
359         if (inode->i_num_ads >= 0xFFFF)
360                 return false;
361
362         /* Assume the dentry is okay if it already had an unnamed ADS entry when
363          * it was read in.  */
364         if (!inode->i_canonical_streams)
365                 return false;
366
367         /* We can't use use this workaround on encrypted files because WIMGAPI
368          * reports that the WIM is in an incorrect format.  */
369         if (inode->i_attributes & FILE_ATTRIBUTE_ENCRYPTED)
370                 return false;
371
372         return true;
373 }
374
375 /* Calculate the total number of bytes that will be consumed when a dentry is
376  * written.  This includes the fixed-length portion of the dentry, the name
377  * fields, any tagged metadata items, and any alternate data stream entries.
378  * Also includes all alignment bytes.  */
379 u64
380 dentry_out_total_length(const struct wim_dentry *dentry)
381 {
382         const struct wim_inode *inode = dentry->d_inode;
383         u64 len;
384
385         len = dentry_min_len_with_names(dentry->file_name_nbytes,
386                                         dentry->short_name_nbytes);
387         len = (len + 7) & ~7;
388
389         if (inode->i_extra_size) {
390                 len += inode->i_extra_size;
391                 len = (len + 7) & ~7;
392         }
393
394         if (unlikely(inode->i_num_ads)) {
395                 if (inode_needs_dummy_stream(inode))
396                         len += ads_entry_out_total_length(&(struct wim_ads_entry){});
397
398                 for (u16 i = 0; i < inode->i_num_ads; i++)
399                         len += ads_entry_out_total_length(&inode->i_ads_entries[i]);
400         }
401
402         return len;
403 }
404
405 /* Internal version of for_dentry_in_tree() that omits the NULL check  */
406 static int
407 do_for_dentry_in_tree(struct wim_dentry *dentry,
408                       int (*visitor)(struct wim_dentry *, void *), void *arg)
409 {
410         int ret;
411         struct wim_dentry *child;
412
413         ret = (*visitor)(dentry, arg);
414         if (unlikely(ret))
415                 return ret;
416
417         for_dentry_child(child, dentry) {
418                 ret = do_for_dentry_in_tree(child, visitor, arg);
419                 if (unlikely(ret))
420                         return ret;
421         }
422         return 0;
423 }
424
425 /* Internal version of for_dentry_in_tree_depth() that omits the NULL check  */
426 static int
427 do_for_dentry_in_tree_depth(struct wim_dentry *dentry,
428                             int (*visitor)(struct wim_dentry *, void *), void *arg)
429 {
430         int ret;
431         struct wim_dentry *child;
432
433         for_dentry_child_postorder(child, dentry) {
434                 ret = do_for_dentry_in_tree_depth(child, visitor, arg);
435                 if (unlikely(ret))
436                         return ret;
437         }
438         return unlikely((*visitor)(dentry, arg));
439 }
440
441 /*
442  * Call a function on all dentries in a tree.
443  *
444  * @arg will be passed as the second argument to each invocation of @visitor.
445  *
446  * This function does a pre-order traversal --- that is, a parent will be
447  * visited before its children.  It also will visit siblings in order of
448  * case-sensitive filename.  Equivalently, this function visits the entire tree
449  * in the case-sensitive lexicographic order of the full paths.
450  *
451  * It is safe to pass NULL for @root, which means that the dentry tree is empty.
452  * In this case, this function does nothing.
453  *
454  * @visitor must not modify the structure of the dentry tree during the
455  * traversal.
456  *
457  * The return value will be 0 if all calls to @visitor returned 0.  Otherwise,
458  * the return value will be the first nonzero value returned by @visitor.
459  */
460 int
461 for_dentry_in_tree(struct wim_dentry *root,
462                    int (*visitor)(struct wim_dentry *, void *), void *arg)
463 {
464         if (unlikely(!root))
465                 return 0;
466         return do_for_dentry_in_tree(root, visitor, arg);
467 }
468
469 /* Like for_dentry_in_tree(), but do a depth-first traversal of the dentry tree.
470  * That is, the visitor function will be called on a dentry's children before
471  * itself.  It will be safe to free a dentry when visiting it.  */
472 static int
473 for_dentry_in_tree_depth(struct wim_dentry *root,
474                          int (*visitor)(struct wim_dentry *, void *), void *arg)
475 {
476         if (unlikely(!root))
477                 return 0;
478         return do_for_dentry_in_tree_depth(root, visitor, arg);
479 }
480
481 /*
482  * Calculate the full path to @dentry within the WIM image, if not already done.
483  *
484  * The full name will be saved in the cached value 'dentry->_full_path'.
485  *
486  * Whenever possible, use dentry_full_path() instead of calling this and
487  * accessing _full_path directly.
488  *
489  * Returns 0 or an error code resulting from a failed string conversion.
490  */
491 int
492 calculate_dentry_full_path(struct wim_dentry *dentry)
493 {
494         size_t ulen;
495         size_t dummy;
496         const struct wim_dentry *d;
497
498         if (dentry->_full_path)
499                 return 0;
500
501         ulen = 0;
502         d = dentry;
503         do {
504                 ulen += d->file_name_nbytes / sizeof(utf16lechar);
505                 ulen++;
506                 d = d->d_parent;  /* assumes d == d->d_parent for root  */
507         } while (!dentry_is_root(d));
508
509         utf16lechar ubuf[ulen];
510         utf16lechar *p = &ubuf[ulen];
511
512         d = dentry;
513         do {
514                 p -= d->file_name_nbytes / sizeof(utf16lechar);
515                 memcpy(p, d->file_name, d->file_name_nbytes);
516                 *--p = cpu_to_le16(WIM_PATH_SEPARATOR);
517                 d = d->d_parent;  /* assumes d == d->d_parent for root  */
518         } while (!dentry_is_root(d));
519
520         wimlib_assert(p == ubuf);
521
522         return utf16le_to_tstr(ubuf, ulen * sizeof(utf16lechar),
523                                &dentry->_full_path, &dummy);
524 }
525
526 /*
527  * Return the full path to the @dentry within the WIM image, or NULL if the full
528  * path could not be determined due to a string conversion error.
529  *
530  * The returned memory will be cached in the dentry, so the caller is not
531  * responsible for freeing it.
532  */
533 tchar *
534 dentry_full_path(struct wim_dentry *dentry)
535 {
536         calculate_dentry_full_path(dentry);
537         return dentry->_full_path;
538 }
539
540 static int
541 dentry_calculate_subdir_offset(struct wim_dentry *dentry, void *_subdir_offset_p)
542 {
543         if (dentry_is_directory(dentry)) {
544                 u64 *subdir_offset_p = _subdir_offset_p;
545                 struct wim_dentry *child;
546
547                 /* Set offset of directory's child dentries  */
548                 dentry->subdir_offset = *subdir_offset_p;
549
550                 /* Account for child dentries  */
551                 for_dentry_child(child, dentry)
552                         *subdir_offset_p += dentry_out_total_length(child);
553
554                 /* Account for end-of-directory entry  */
555                 *subdir_offset_p += 8;
556         } else {
557                 /* Not a directory; set subdir_offset to 0  */
558                 dentry->subdir_offset = 0;
559         }
560         return 0;
561 }
562
563 /*
564  * Calculate the subdir offsets for a dentry tree, in preparation of writing
565  * that dentry tree to a metadata resource.
566  *
567  * The subdir offset of each dentry is the offset in the uncompressed metadata
568  * resource at which its child dentries begin, or 0 if that dentry has no
569  * children.
570  *
571  * The caller must initialize *subdir_offset_p to the first subdir offset that
572  * is available to use after the root dentry is written.
573  *
574  * When this function returns, *subdir_offset_p will have been advanced past the
575  * size needed for the dentry tree within the uncompressed metadata resource.
576  */
577 void
578 calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p)
579 {
580         for_dentry_in_tree(root, dentry_calculate_subdir_offset, subdir_offset_p);
581 }
582
583 /* Compare the UTF-16LE long filenames of two dentries case insensitively.  */
584 static int
585 dentry_compare_names_case_insensitive(const struct wim_dentry *d1,
586                                       const struct wim_dentry *d2)
587 {
588         return cmp_utf16le_strings(d1->file_name,
589                                    d1->file_name_nbytes / 2,
590                                    d2->file_name,
591                                    d2->file_name_nbytes / 2,
592                                    true);
593 }
594
595 /* Compare the UTF-16LE long filenames of two dentries case sensitively.  */
596 static int
597 dentry_compare_names_case_sensitive(const struct wim_dentry *d1,
598                                     const struct wim_dentry *d2)
599 {
600         return cmp_utf16le_strings(d1->file_name,
601                                    d1->file_name_nbytes / 2,
602                                    d2->file_name,
603                                    d2->file_name_nbytes / 2,
604                                    false);
605 }
606
607 static int
608 _avl_dentry_compare_names_ci(const struct avl_tree_node *n1,
609                              const struct avl_tree_node *n2)
610 {
611         const struct wim_dentry *d1, *d2;
612
613         d1 = avl_tree_entry(n1, struct wim_dentry, d_index_node_ci);
614         d2 = avl_tree_entry(n2, struct wim_dentry, d_index_node_ci);
615         return dentry_compare_names_case_insensitive(d1, d2);
616 }
617
618 static int
619 _avl_dentry_compare_names(const struct avl_tree_node *n1,
620                           const struct avl_tree_node *n2)
621 {
622         const struct wim_dentry *d1, *d2;
623
624         d1 = avl_tree_entry(n1, struct wim_dentry, d_index_node);
625         d2 = avl_tree_entry(n2, struct wim_dentry, d_index_node);
626         return dentry_compare_names_case_sensitive(d1, d2);
627 }
628
629 /* Default case sensitivity behavior for searches with
630  * WIMLIB_CASE_PLATFORM_DEFAULT specified.  This can be modified by passing
631  * WIMLIB_INIT_FLAG_DEFAULT_CASE_SENSITIVE or
632  * WIMLIB_INIT_FLAG_DEFAULT_CASE_INSENSITIVE to wimlib_global_init().  */
633 bool default_ignore_case =
634 #ifdef __WIN32__
635         true
636 #else
637         false
638 #endif
639 ;
640
641 /* Case-sensitive dentry lookup.  Only @file_name and @file_name_nbytes of
642  * @dummy must be valid.  */
643 static struct wim_dentry *
644 dir_lookup(const struct wim_inode *dir, const struct wim_dentry *dummy)
645 {
646         struct avl_tree_node *node;
647
648         node = avl_tree_lookup_node(dir->i_children,
649                                     &dummy->d_index_node,
650                                     _avl_dentry_compare_names);
651         if (!node)
652                 return NULL;
653         return avl_tree_entry(node, struct wim_dentry, d_index_node);
654 }
655
656 /* Case-insensitive dentry lookup.  Only @file_name and @file_name_nbytes of
657  * @dummy must be valid.  */
658 static struct wim_dentry *
659 dir_lookup_ci(const struct wim_inode *dir, const struct wim_dentry *dummy)
660 {
661         struct avl_tree_node *node;
662
663         node = avl_tree_lookup_node(dir->i_children_ci,
664                                     &dummy->d_index_node_ci,
665                                     _avl_dentry_compare_names_ci);
666         if (!node)
667                 return NULL;
668         return avl_tree_entry(node, struct wim_dentry, d_index_node_ci);
669 }
670
671 /* Given a UTF-16LE filename and a directory, look up the dentry for the file.
672  * Return it if found, otherwise NULL.  This has configurable case sensitivity,
673  * and @name need not be null-terminated.  */
674 struct wim_dentry *
675 get_dentry_child_with_utf16le_name(const struct wim_dentry *dentry,
676                                    const utf16lechar *name,
677                                    size_t name_nbytes,
678                                    CASE_SENSITIVITY_TYPE case_ctype)
679 {
680         const struct wim_inode *dir = dentry->d_inode;
681         bool ignore_case = will_ignore_case(case_ctype);
682         struct wim_dentry dummy;
683         struct wim_dentry *child;
684
685         dummy.file_name = (utf16lechar*)name;
686         dummy.file_name_nbytes = name_nbytes;
687
688         if (!ignore_case)
689                 /* Case-sensitive lookup.  */
690                 return dir_lookup(dir, &dummy);
691
692         /* Case-insensitive lookup.  */
693
694         child = dir_lookup_ci(dir, &dummy);
695         if (!child)
696                 return NULL;
697
698         if (likely(list_empty(&child->d_ci_conflict_list)))
699                 /* Only one dentry has this case-insensitive name; return it */
700                 return child;
701
702         /* Multiple dentries have the same case-insensitive name.  Choose the
703          * dentry with the same case-sensitive name, if one exists; otherwise
704          * print a warning and choose one of the possible dentries arbitrarily.
705          */
706         struct wim_dentry *alt = child;
707         size_t num_alts = 0;
708
709         do {
710                 num_alts++;
711                 if (!dentry_compare_names_case_sensitive(&dummy, alt))
712                         return alt;
713                 alt = list_entry(alt->d_ci_conflict_list.next,
714                                  struct wim_dentry, d_ci_conflict_list);
715         } while (alt != child);
716
717         WARNING("Result of case-insensitive lookup is ambiguous\n"
718                 "          (returning \"%"TS"\" of %zu "
719                 "possible files, including \"%"TS"\")",
720                 dentry_full_path(child),
721                 num_alts,
722                 dentry_full_path(list_entry(child->d_ci_conflict_list.next,
723                                             struct wim_dentry,
724                                             d_ci_conflict_list)));
725         return child;
726 }
727
728 /* Given a 'tchar' filename and a directory, look up the dentry for the file.
729  * If the filename was successfully converted to UTF-16LE and the dentry was
730  * found, return it; otherwise return NULL.  This has configurable case
731  * sensitivity.  */
732 struct wim_dentry *
733 get_dentry_child_with_name(const struct wim_dentry *dentry, const tchar *name,
734                            CASE_SENSITIVITY_TYPE case_type)
735 {
736         int ret;
737         const utf16lechar *name_utf16le;
738         size_t name_utf16le_nbytes;
739         struct wim_dentry *child;
740
741         ret = tstr_get_utf16le_and_len(name, &name_utf16le,
742                                        &name_utf16le_nbytes);
743         if (ret)
744                 return NULL;
745
746         child = get_dentry_child_with_utf16le_name(dentry,
747                                                    name_utf16le,
748                                                    name_utf16le_nbytes,
749                                                    case_type);
750         tstr_put_utf16le(name_utf16le);
751         return child;
752 }
753
754 /* This is the UTF-16LE version of get_dentry(), currently private to this file
755  * because no one needs it besides get_dentry().  */
756 static struct wim_dentry *
757 get_dentry_utf16le(WIMStruct *wim, const utf16lechar *path,
758                    CASE_SENSITIVITY_TYPE case_type)
759 {
760         struct wim_dentry *cur_dentry;
761         const utf16lechar *name_start, *name_end;
762
763         /* Start with the root directory of the image.  Note: this will be NULL
764          * if an image has been added directly with wimlib_add_empty_image() but
765          * no files have been added yet; in that case we fail with ENOENT.  */
766         cur_dentry = wim_get_current_root_dentry(wim);
767
768         name_start = path;
769         for (;;) {
770                 if (cur_dentry == NULL) {
771                         errno = ENOENT;
772                         return NULL;
773                 }
774
775                 if (*name_start && !dentry_is_directory(cur_dentry)) {
776                         errno = ENOTDIR;
777                         return NULL;
778                 }
779
780                 while (*name_start == cpu_to_le16(WIM_PATH_SEPARATOR))
781                         name_start++;
782
783                 if (!*name_start)
784                         return cur_dentry;
785
786                 name_end = name_start;
787                 do {
788                         ++name_end;
789                 } while (*name_end != cpu_to_le16(WIM_PATH_SEPARATOR) && *name_end);
790
791                 cur_dentry = get_dentry_child_with_utf16le_name(cur_dentry,
792                                                                 name_start,
793                                                                 (u8*)name_end - (u8*)name_start,
794                                                                 case_type);
795                 name_start = name_end;
796         }
797 }
798
799 /*
800  * WIM path lookup: translate a path in the currently selected WIM image to the
801  * corresponding dentry, if it exists.
802  *
803  * @wim
804  *      The WIMStruct for the WIM.  The search takes place in the currently
805  *      selected image.
806  *
807  * @path
808  *      The path to look up, given relative to the root of the WIM image.
809  *      Characters with value WIM_PATH_SEPARATOR are taken to be path
810  *      separators.  Leading path separators are ignored, whereas one or more
811  *      trailing path separators cause the path to only match a directory.
812  *
813  * @case_type
814  *      The case-sensitivity behavior of this function, as one of the following
815  *      constants:
816  *
817  *    - WIMLIB_CASE_SENSITIVE:  Perform the search case sensitively.  This means
818  *      that names must match exactly.
819  *
820  *    - WIMLIB_CASE_INSENSITIVE:  Perform the search case insensitively.  This
821  *      means that names are considered to match if they are equal when
822  *      transformed to upper case.  If a path component matches multiple names
823  *      case-insensitively, the name that matches the path component
824  *      case-sensitively is chosen, if existent; otherwise one
825  *      case-insensitively matching name is chosen arbitrarily.
826  *
827  *    - WIMLIB_CASE_PLATFORM_DEFAULT:  Perform either case-sensitive or
828  *      case-insensitive search, depending on the value of the global variable
829  *      default_ignore_case.
830  *
831  *    In any case, no Unicode normalization is done before comparing strings.
832  *
833  * Returns a pointer to the dentry that is the result of the lookup, or NULL if
834  * no such dentry exists.  If NULL is returned, errno is set to one of the
835  * following values:
836  *
837  *      ENOTDIR if one of the path components used as a directory existed but
838  *      was not, in fact, a directory.
839  *
840  *      ENOENT otherwise.
841  *
842  * Additional notes:
843  *
844  *    - This function does not consider a reparse point to be a directory, even
845  *      if it has FILE_ATTRIBUTE_DIRECTORY set.
846  *
847  *    - This function does not dereference symbolic links or junction points
848  *      when performing the search.
849  *
850  *    - Since this function ignores leading slashes, the empty path is valid and
851  *      names the root directory of the WIM image.
852  *
853  *    - An image added with wimlib_add_empty_image() does not have a root
854  *      directory yet, and this function will fail with ENOENT for any path on
855  *      such an image.
856  */
857 struct wim_dentry *
858 get_dentry(WIMStruct *wim, const tchar *path, CASE_SENSITIVITY_TYPE case_type)
859 {
860         int ret;
861         const utf16lechar *path_utf16le;
862         struct wim_dentry *dentry;
863
864         ret = tstr_get_utf16le(path, &path_utf16le);
865         if (ret)
866                 return NULL;
867         dentry = get_dentry_utf16le(wim, path_utf16le, case_type);
868         tstr_put_utf16le(path_utf16le);
869         return dentry;
870 }
871
872 /* Modify @path, which is a null-terminated string @len 'tchars' in length,
873  * in-place to produce the path to its parent directory.  */
874 static void
875 to_parent_name(tchar *path, size_t len)
876 {
877         ssize_t i = (ssize_t)len - 1;
878         while (i >= 0 && path[i] == WIM_PATH_SEPARATOR)
879                 i--;
880         while (i >= 0 && path[i] != WIM_PATH_SEPARATOR)
881                 i--;
882         while (i >= 0 && path[i] == WIM_PATH_SEPARATOR)
883                 i--;
884         path[i + 1] = T('\0');
885 }
886
887 /* Similar to get_dentry(), but returns the dentry named by @path with the last
888  * component stripped off.
889  *
890  * Note: The returned dentry is NOT guaranteed to be a directory.  */
891 struct wim_dentry *
892 get_parent_dentry(WIMStruct *wim, const tchar *path,
893                   CASE_SENSITIVITY_TYPE case_type)
894 {
895         size_t path_len = tstrlen(path);
896         tchar buf[path_len + 1];
897
898         tmemcpy(buf, path, path_len + 1);
899         to_parent_name(buf, path_len);
900         return get_dentry(wim, buf, case_type);
901 }
902
903 /*
904  * Create an unlinked dentry.
905  *
906  * @name specifies the long name to give the new dentry.  If NULL or empty, the
907  * new dentry will be given no long name.
908  *
909  * The new dentry will have no short name and no associated inode.
910  *
911  * On success, returns 0 and a pointer to the new, allocated dentry is stored in
912  * *dentry_ret.  On failure, returns WIMLIB_ERR_NOMEM or an error code resulting
913  * from a failed string conversion.
914  */
915 int
916 new_dentry(const tchar *name, struct wim_dentry **dentry_ret)
917 {
918         struct wim_dentry *dentry;
919         int ret;
920
921         dentry = CALLOC(1, sizeof(struct wim_dentry));
922         if (!dentry)
923                 return WIMLIB_ERR_NOMEM;
924
925         if (name && *name) {
926                 ret = dentry_set_name(dentry, name);
927                 if (ret) {
928                         FREE(dentry);
929                         return ret;
930                 }
931         }
932         dentry->d_parent = dentry;
933         *dentry_ret = dentry;
934         return 0;
935 }
936
937 static int
938 _new_dentry_with_inode(const tchar *name, struct wim_dentry **dentry_ret,
939                        bool timeless)
940 {
941         struct wim_dentry *dentry;
942         struct wim_inode *inode;
943         int ret;
944
945         ret = new_dentry(name, &dentry);
946         if (ret)
947                 return ret;
948
949         if (timeless)
950                 inode = new_timeless_inode();
951         else
952                 inode = new_inode();
953         if (!inode) {
954                 free_dentry(dentry);
955                 return WIMLIB_ERR_NOMEM;
956         }
957
958         d_associate(dentry, inode);
959
960         *dentry_ret = dentry;
961         return 0;
962 }
963
964 /* Like new_dentry(), but also allocate an inode and associate it with the
965  * dentry.  The timestamps for the inode will be set to the current time.  */
966 int
967 new_dentry_with_inode(const tchar *name, struct wim_dentry **dentry_ret)
968 {
969         return _new_dentry_with_inode(name, dentry_ret, false);
970 }
971
972 /* Like new_dentry_with_inode(), but don't bother setting the timestamps for the
973  * new inode; instead, just leave them as 0, under the presumption that the
974  * caller will set them itself.  */
975 int
976 new_dentry_with_timeless_inode(const tchar *name, struct wim_dentry **dentry_ret)
977 {
978         return _new_dentry_with_inode(name, dentry_ret, true);
979 }
980
981 /* Create an unnamed dentry with a new inode for a directory with the default
982  * metadata.  */
983 int
984 new_filler_directory(struct wim_dentry **dentry_ret)
985 {
986         int ret;
987         struct wim_dentry *dentry;
988
989         ret = new_dentry_with_inode(NULL, &dentry);
990         if (ret)
991                 return ret;
992         /* Leave the inode number as 0; this is allowed for non
993          * hard-linked files. */
994         dentry->d_inode->i_resolved = 1;
995         dentry->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
996         *dentry_ret = dentry;
997         return 0;
998 }
999
1000 static int
1001 dentry_clear_inode_visited(struct wim_dentry *dentry, void *_ignore)
1002 {
1003         dentry->d_inode->i_visited = 0;
1004         return 0;
1005 }
1006
1007 void
1008 dentry_tree_clear_inode_visited(struct wim_dentry *root)
1009 {
1010         for_dentry_in_tree(root, dentry_clear_inode_visited, NULL);
1011 }
1012
1013 /*
1014  * Free a WIM dentry.
1015  *
1016  * In addition to freeing the dentry itself, this disassociates the dentry from
1017  * its inode.  If the inode is no longer in use, it will be freed as well.
1018  */
1019 void
1020 free_dentry(struct wim_dentry *dentry)
1021 {
1022         if (dentry) {
1023                 d_disassociate(dentry);
1024                 FREE(dentry->file_name);
1025                 FREE(dentry->short_name);
1026                 FREE(dentry->_full_path);
1027                 FREE(dentry);
1028         }
1029 }
1030
1031 static int
1032 do_free_dentry(struct wim_dentry *dentry, void *_ignore)
1033 {
1034         free_dentry(dentry);
1035         return 0;
1036 }
1037
1038 static int
1039 do_free_dentry_and_unref_streams(struct wim_dentry *dentry, void *lookup_table)
1040 {
1041         inode_unref_streams(dentry->d_inode, lookup_table);
1042         free_dentry(dentry);
1043         return 0;
1044 }
1045
1046 /*
1047  * Free all dentries in a tree.
1048  *
1049  * @root:
1050  *      The root of the dentry tree to free.  If NULL, this function has no
1051  *      effect.
1052  *
1053  * @lookup_table:
1054  *      A pointer to the lookup table for the WIM, or NULL if not specified.  If
1055  *      specified, this function will decrement the reference counts of the
1056  *      single-instance streams referenced by the dentries.
1057  *
1058  * This function also releases references to the corresponding inodes.
1059  *
1060  * This function does *not* unlink @root from its parent directory, if it has
1061  * one.  If @root has a parent, the caller must unlink @root before calling this
1062  * function.
1063  */
1064 void
1065 free_dentry_tree(struct wim_dentry *root, struct wim_lookup_table *lookup_table)
1066 {
1067         int (*f)(struct wim_dentry *, void *);
1068
1069         if (lookup_table)
1070                 f = do_free_dentry_and_unref_streams;
1071         else
1072                 f = do_free_dentry;
1073
1074         for_dentry_in_tree_depth(root, f, lookup_table);
1075 }
1076
1077 /* Insert the @child dentry into the case sensitive index of the @dir directory.
1078  * Return NULL if successfully inserted, otherwise a pointer to the
1079  * already-inserted duplicate.  */
1080 static struct wim_dentry *
1081 dir_index_child(struct wim_inode *dir, struct wim_dentry *child)
1082 {
1083         struct avl_tree_node *duplicate;
1084
1085         duplicate = avl_tree_insert(&dir->i_children,
1086                                     &child->d_index_node,
1087                                     _avl_dentry_compare_names);
1088         if (!duplicate)
1089                 return NULL;
1090         return avl_tree_entry(duplicate, struct wim_dentry, d_index_node);
1091 }
1092
1093 /* Insert the @child dentry into the case insensitive index of the @dir
1094  * directory.  Return NULL if successfully inserted, otherwise a pointer to the
1095  * already-inserted duplicate.  */
1096 static struct wim_dentry *
1097 dir_index_child_ci(struct wim_inode *dir, struct wim_dentry *child)
1098 {
1099         struct avl_tree_node *duplicate;
1100
1101         duplicate = avl_tree_insert(&dir->i_children_ci,
1102                                     &child->d_index_node_ci,
1103                                     _avl_dentry_compare_names_ci);
1104         if (!duplicate)
1105                 return NULL;
1106         return avl_tree_entry(duplicate, struct wim_dentry, d_index_node_ci);
1107 }
1108
1109 /* Remove the specified dentry from its directory's case-sensitive index.  */
1110 static void
1111 dir_unindex_child(struct wim_inode *dir, struct wim_dentry *child)
1112 {
1113         avl_tree_remove(&dir->i_children, &child->d_index_node);
1114 }
1115
1116 /* Remove the specified dentry from its directory's case-insensitive index.  */
1117 static void
1118 dir_unindex_child_ci(struct wim_inode *dir, struct wim_dentry *child)
1119 {
1120         avl_tree_remove(&dir->i_children_ci, &child->d_index_node_ci);
1121 }
1122
1123 /* Return true iff the specified dentry is in its parent directory's
1124  * case-insensitive index.  */
1125 static bool
1126 dentry_in_ci_index(const struct wim_dentry *dentry)
1127 {
1128         return !avl_tree_node_is_unlinked(&dentry->d_index_node_ci);
1129 }
1130
1131 /*
1132  * Link a dentry into the tree.
1133  *
1134  * @parent:
1135  *      The dentry that will be the parent of @child.  It must name a directory.
1136  *
1137  * @child:
1138  *      The dentry to link.  It must be currently unlinked.
1139  *
1140  * Returns NULL if successful.  If @parent already contains a dentry with the
1141  * same case-sensitive name as @child, returns a pointer to this duplicate
1142  * dentry.
1143  */
1144 struct wim_dentry *
1145 dentry_add_child(struct wim_dentry *parent, struct wim_dentry *child)
1146 {
1147         struct wim_dentry *duplicate;
1148         struct wim_inode *dir;
1149
1150         wimlib_assert(parent != child);
1151
1152         dir = parent->d_inode;
1153
1154         wimlib_assert(inode_is_directory(dir));
1155
1156         duplicate = dir_index_child(dir, child);
1157         if (duplicate)
1158                 return duplicate;
1159
1160         duplicate = dir_index_child_ci(dir, child);
1161         if (duplicate) {
1162                 list_add(&child->d_ci_conflict_list, &duplicate->d_ci_conflict_list);
1163                 avl_tree_node_set_unlinked(&child->d_index_node_ci);
1164         } else {
1165                 INIT_LIST_HEAD(&child->d_ci_conflict_list);
1166         }
1167         child->d_parent = parent;
1168         return NULL;
1169 }
1170
1171 /* Unlink a dentry from the tree.  */
1172 void
1173 unlink_dentry(struct wim_dentry *dentry)
1174 {
1175         struct wim_inode *dir;
1176
1177         /* Do nothing if the dentry is root or it's already unlinked.  Not
1178          * actually necessary based on the current callers, but we do the check
1179          * here to be safe.  */
1180         if (unlikely(dentry->d_parent == dentry))
1181                 return;
1182
1183         dir = dentry->d_parent->d_inode;
1184
1185         dir_unindex_child(dir, dentry);
1186
1187         if (dentry_in_ci_index(dentry)) {
1188
1189                 dir_unindex_child_ci(dir, dentry);
1190
1191                 if (!list_empty(&dentry->d_ci_conflict_list)) {
1192                         /* Make a different case-insensitively-the-same dentry
1193                          * be the "representative" in the search index.  */
1194                         struct list_head *next;
1195                         struct wim_dentry *other;
1196                         struct wim_dentry *existing;
1197
1198                         next = dentry->d_ci_conflict_list.next;
1199                         other = list_entry(next, struct wim_dentry, d_ci_conflict_list);
1200                         existing = dir_index_child_ci(dir, other);
1201                         wimlib_assert(existing == NULL);
1202                 }
1203         }
1204         list_del(&dentry->d_ci_conflict_list);
1205
1206         /* Not actually necessary, but to be safe don't retain the now-obsolete
1207          * parent pointer.  */
1208         dentry->d_parent = dentry;
1209 }
1210
1211 static int
1212 read_extra_data(const u8 *p, const u8 *end, struct wim_inode *inode)
1213 {
1214         while (((uintptr_t)p & 7) && p < end)
1215                 p++;
1216
1217         if (unlikely(p < end)) {
1218                 inode->i_extra = memdup(p, end - p);
1219                 if (!inode->i_extra)
1220                         return WIMLIB_ERR_NOMEM;
1221                 inode->i_extra_size = end - p;
1222         }
1223         return 0;
1224 }
1225
1226 /* Read a dentry, including all alternate data stream entries that follow it,
1227  * from an uncompressed metadata resource buffer.  */
1228 static int
1229 read_dentry(const u8 * restrict buf, size_t buf_len,
1230             u64 *offset_p, struct wim_dentry **dentry_ret)
1231 {
1232         u64 offset = *offset_p;
1233         u64 length;
1234         const u8 *p;
1235         const struct wim_dentry_on_disk *disk_dentry;
1236         struct wim_dentry *dentry;
1237         struct wim_inode *inode;
1238         u16 short_name_nbytes;
1239         u16 file_name_nbytes;
1240         u64 calculated_size;
1241         int ret;
1242
1243         BUILD_BUG_ON(sizeof(struct wim_dentry_on_disk) != WIM_DENTRY_DISK_SIZE);
1244
1245         /* Before reading the whole dentry, we need to read just the length.
1246          * This is because a dentry of length 8 (that is, just the length field)
1247          * terminates the list of sibling directory entries. */
1248
1249         /* Check for buffer overrun.  */
1250         if (unlikely(offset + sizeof(u64) > buf_len ||
1251                      offset + sizeof(u64) < offset))
1252         {
1253                 ERROR("Directory entry starting at %"PRIu64" ends past the "
1254                       "end of the metadata resource (size %zu)",
1255                       offset, buf_len);
1256                 return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1257         }
1258
1259         /* Get pointer to the dentry data.  */
1260         p = &buf[offset];
1261         disk_dentry = (const struct wim_dentry_on_disk*)p;
1262
1263         /* Get dentry length.  */
1264         length = le64_to_cpu(disk_dentry->length);
1265
1266         /* Check for end-of-directory.  */
1267         if (length <= 8) {
1268                 *dentry_ret = NULL;
1269                 return 0;
1270         }
1271
1272         /* Validate dentry length.  */
1273         if (unlikely(length < sizeof(struct wim_dentry_on_disk))) {
1274                 ERROR("Directory entry has invalid length of %"PRIu64" bytes",
1275                       length);
1276                 return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1277         }
1278
1279         /* Check for buffer overrun.  */
1280         if (unlikely(offset + length > buf_len ||
1281                      offset + length < offset))
1282         {
1283                 ERROR("Directory entry at offset %"PRIu64" and with size "
1284                       "%"PRIu64" ends past the end of the metadata resource "
1285                       "(size %zu)", offset, length, buf_len);
1286                 return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1287         }
1288
1289         /* Allocate new dentry structure, along with a preliminary inode.  */
1290         ret = new_dentry_with_timeless_inode(NULL, &dentry);
1291         if (ret)
1292                 return ret;
1293
1294         inode = dentry->d_inode;
1295
1296         /* Read more fields: some into the dentry, and some into the inode.  */
1297         inode->i_attributes = le32_to_cpu(disk_dentry->attributes);
1298         inode->i_security_id = le32_to_cpu(disk_dentry->security_id);
1299         dentry->subdir_offset = le64_to_cpu(disk_dentry->subdir_offset);
1300         inode->i_creation_time = le64_to_cpu(disk_dentry->creation_time);
1301         inode->i_last_access_time = le64_to_cpu(disk_dentry->last_access_time);
1302         inode->i_last_write_time = le64_to_cpu(disk_dentry->last_write_time);
1303         copy_hash(inode->i_hash, disk_dentry->unnamed_stream_hash);
1304
1305         /* I don't know what's going on here.  It seems like M$ screwed up the
1306          * reparse points, then put the fields in the same place and didn't
1307          * document it.  So we have some fields we read for reparse points, and
1308          * some fields in the same place for non-reparse-points.  */
1309         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1310                 inode->i_rp_unknown_1 = le32_to_cpu(disk_dentry->reparse.rp_unknown_1);
1311                 inode->i_reparse_tag = le32_to_cpu(disk_dentry->reparse.reparse_tag);
1312                 inode->i_rp_unknown_2 = le16_to_cpu(disk_dentry->reparse.rp_unknown_2);
1313                 inode->i_not_rpfixed = le16_to_cpu(disk_dentry->reparse.not_rpfixed);
1314                 /* Leave inode->i_ino at 0.  Note that this means the WIM file
1315                  * cannot archive hard-linked reparse points.  Such a thing
1316                  * doesn't really make sense anyway, although I believe it's
1317                  * theoretically possible to have them on NTFS.  */
1318         } else {
1319                 inode->i_rp_unknown_1 = le32_to_cpu(disk_dentry->nonreparse.rp_unknown_1);
1320                 inode->i_ino = le64_to_cpu(disk_dentry->nonreparse.hard_link_group_id);
1321         }
1322         inode->i_num_ads = le16_to_cpu(disk_dentry->num_alternate_data_streams);
1323
1324         /* Now onto reading the names.  There are two of them: the (long) file
1325          * name, and the short name.  */
1326
1327         short_name_nbytes = le16_to_cpu(disk_dentry->short_name_nbytes);
1328         file_name_nbytes = le16_to_cpu(disk_dentry->file_name_nbytes);
1329
1330         if (unlikely((short_name_nbytes & 1) | (file_name_nbytes & 1))) {
1331                 ERROR("Dentry name is not valid UTF-16 (odd number of bytes)!");
1332                 ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1333                 goto err_free_dentry;
1334         }
1335
1336         /* We now know the length of the file name and short name.  Make sure
1337          * the length of the dentry is large enough to actually hold them.
1338          *
1339          * The calculated length here is unaligned to allow for the possibility
1340          * that the dentry's length is unaligned, although this would be
1341          * unexpected.  */
1342         calculated_size = dentry_min_len_with_names(file_name_nbytes,
1343                                                     short_name_nbytes);
1344
1345         if (unlikely(length < calculated_size)) {
1346                 ERROR("Unexpected end of directory entry! (Expected "
1347                       "at least %"PRIu64" bytes, got %"PRIu64" bytes.)",
1348                       calculated_size, length);
1349                 ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1350                 goto err_free_dentry;
1351         }
1352
1353         /* Advance p to point past the base dentry, to the first name.  */
1354         p += sizeof(struct wim_dentry_on_disk);
1355
1356         /* Read the filename if present.  Note: if the filename is empty, there
1357          * is no null terminator following it.  */
1358         if (file_name_nbytes) {
1359                 dentry->file_name = utf16le_dupz(p, file_name_nbytes);
1360                 if (dentry->file_name == NULL) {
1361                         ret = WIMLIB_ERR_NOMEM;
1362                         goto err_free_dentry;
1363                 }
1364                 dentry->file_name_nbytes = file_name_nbytes;
1365                 p += (u32)file_name_nbytes + 2;
1366         }
1367
1368         /* Read the short filename if present.  Note: if there is no short
1369          * filename, there is no null terminator following it. */
1370         if (short_name_nbytes) {
1371                 dentry->short_name = utf16le_dupz(p, short_name_nbytes);
1372                 if (dentry->short_name == NULL) {
1373                         ret = WIMLIB_ERR_NOMEM;
1374                         goto err_free_dentry;
1375                 }
1376                 dentry->short_name_nbytes = short_name_nbytes;
1377                 p += (u32)short_name_nbytes + 2;
1378         }
1379
1380         /* Read extra data at end of dentry (but before alternate data stream
1381          * entries).  This may contain tagged items.  */
1382         ret = read_extra_data(p, &buf[offset + length], inode);
1383         if (ret)
1384                 goto err_free_dentry;
1385
1386         /* Align the dentry length.  */
1387         length = (length + 7) & ~7;
1388
1389         offset += length;
1390
1391         /* Read the alternate data streams, if present.  inode->i_num_ads tells
1392          * us how many they are, and they will directly follow the dentry in the
1393          * metadata resource buffer.
1394          *
1395          * Note that each alternate data stream entry begins on an 8-byte
1396          * aligned boundary, and the alternate data stream entries seem to NOT
1397          * be included in the dentry->length field for some reason.  */
1398         if (unlikely(inode->i_num_ads != 0)) {
1399                 size_t orig_bytes_remaining;
1400                 size_t bytes_remaining;
1401
1402                 if (offset > buf_len) {
1403                         ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1404                         goto err_free_dentry;
1405                 }
1406                 bytes_remaining = buf_len - offset;
1407                 orig_bytes_remaining = bytes_remaining;
1408                 ret = read_ads_entries(&buf[offset], inode, &bytes_remaining);
1409                 if (ret)
1410                         goto err_free_dentry;
1411                 offset += (orig_bytes_remaining - bytes_remaining);
1412         }
1413
1414         *offset_p = offset;  /* Sets offset of next dentry in directory  */
1415         *dentry_ret = dentry;
1416         return 0;
1417
1418 err_free_dentry:
1419         free_dentry(dentry);
1420         return ret;
1421 }
1422
1423 /* Is the dentry named "." or ".." ?  */
1424 static bool
1425 dentry_is_dot_or_dotdot(const struct wim_dentry *dentry)
1426 {
1427         if (dentry->file_name_nbytes <= 4) {
1428                 if (dentry->file_name_nbytes == 4) {
1429                         if (dentry->file_name[0] == cpu_to_le16('.') &&
1430                             dentry->file_name[1] == cpu_to_le16('.'))
1431                                 return true;
1432                 } else if (dentry->file_name_nbytes == 2) {
1433                         if (dentry->file_name[0] == cpu_to_le16('.'))
1434                                 return true;
1435                 }
1436         }
1437         return false;
1438 }
1439
1440 static int
1441 read_dentry_tree_recursive(const u8 * restrict buf, size_t buf_len,
1442                            struct wim_dentry * restrict dir)
1443 {
1444         u64 cur_offset = dir->subdir_offset;
1445
1446         /* Check for cyclic directory structure, which would cause infinite
1447          * recursion if not handled.  */
1448         for (struct wim_dentry *d = dir->d_parent;
1449              !dentry_is_root(d); d = d->d_parent)
1450         {
1451                 if (unlikely(d->subdir_offset == cur_offset)) {
1452                         ERROR("Cyclic directory structure detected: children "
1453                               "of \"%"TS"\" coincide with children of \"%"TS"\"",
1454                               dentry_full_path(dir), dentry_full_path(d));
1455                         return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1456                 }
1457         }
1458
1459         for (;;) {
1460                 struct wim_dentry *child;
1461                 struct wim_dentry *duplicate;
1462                 int ret;
1463
1464                 /* Read next child of @dir.  */
1465                 ret = read_dentry(buf, buf_len, &cur_offset, &child);
1466                 if (ret)
1467                         return ret;
1468
1469                 /* Check for end of directory.  */
1470                 if (child == NULL)
1471                         return 0;
1472
1473                 /* All dentries except the root should be named.  */
1474                 if (unlikely(!dentry_has_long_name(child))) {
1475                         WARNING("Ignoring unnamed dentry in "
1476                                 "directory \"%"TS"\"", dentry_full_path(dir));
1477                         free_dentry(child);
1478                         continue;
1479                 }
1480
1481                 /* Don't allow files named "." or "..".  */
1482                 if (unlikely(dentry_is_dot_or_dotdot(child))) {
1483                         WARNING("Ignoring file named \".\" or \"..\"; "
1484                                 "potentially malicious archive!!!");
1485                         free_dentry(child);
1486                         continue;
1487                 }
1488
1489                 /* Link the child into the directory.  */
1490                 duplicate = dentry_add_child(dir, child);
1491                 if (unlikely(duplicate)) {
1492                         /* We already found a dentry with this same
1493                          * case-sensitive long name.  Only keep the first one.
1494                          */
1495                         WARNING("Ignoring duplicate file \"%"TS"\" "
1496                                 "(the WIM image already contains a file "
1497                                 "at that path with the exact same name)",
1498                                 dentry_full_path(duplicate));
1499                         free_dentry(child);
1500                         continue;
1501                 }
1502
1503                 /* If this child is a directory that itself has children, call
1504                  * this procedure recursively.  */
1505                 if (child->subdir_offset != 0) {
1506                         if (likely(dentry_is_directory(child))) {
1507                                 ret = read_dentry_tree_recursive(buf,
1508                                                                  buf_len,
1509                                                                  child);
1510                                 if (ret)
1511                                         return ret;
1512                         } else {
1513                                 WARNING("Ignoring children of "
1514                                         "non-directory file \"%"TS"\"",
1515                                         dentry_full_path(child));
1516                         }
1517                 }
1518         }
1519 }
1520
1521 /*
1522  * Read a tree of dentries from a WIM metadata resource.
1523  *
1524  * @buf:
1525  *      Buffer containing an uncompressed WIM metadata resource.
1526  *
1527  * @buf_len:
1528  *      Length of the uncompressed metadata resource, in bytes.
1529  *
1530  * @root_offset
1531  *      Offset in the metadata resource of the root of the dentry tree.
1532  *
1533  * @root_ret:
1534  *      On success, either NULL or a pointer to the root dentry is written to
1535  *      this location.  The former case only occurs in the unexpected case that
1536  *      the tree began with an end-of-directory entry.
1537  *
1538  * Return values:
1539  *      WIMLIB_ERR_SUCCESS (0)
1540  *      WIMLIB_ERR_INVALID_METADATA_RESOURCE
1541  *      WIMLIB_ERR_NOMEM
1542  */
1543 int
1544 read_dentry_tree(const u8 *buf, size_t buf_len,
1545                  u64 root_offset, struct wim_dentry **root_ret)
1546 {
1547         int ret;
1548         struct wim_dentry *root;
1549
1550         DEBUG("Reading dentry tree (root_offset=%"PRIu64")", root_offset);
1551
1552         ret = read_dentry(buf, buf_len, &root_offset, &root);
1553         if (ret)
1554                 return ret;
1555
1556         if (likely(root != NULL)) {
1557                 if (unlikely(dentry_has_long_name(root) ||
1558                              dentry_has_short_name(root)))
1559                 {
1560                         WARNING("The root directory has a nonempty name; "
1561                                 "removing it.");
1562                         dentry_set_name(root, NULL);
1563                 }
1564
1565                 if (unlikely(!dentry_is_directory(root))) {
1566                         ERROR("The root of the WIM image is not a directory!");
1567                         ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1568                         goto err_free_dentry_tree;
1569                 }
1570
1571                 if (likely(root->subdir_offset != 0)) {
1572                         ret = read_dentry_tree_recursive(buf, buf_len, root);
1573                         if (ret)
1574                                 goto err_free_dentry_tree;
1575                 }
1576         } else {
1577                 WARNING("The metadata resource has no directory entries; "
1578                         "treating as an empty image.");
1579         }
1580         *root_ret = root;
1581         return 0;
1582
1583 err_free_dentry_tree:
1584         free_dentry_tree(root, NULL);
1585         return ret;
1586 }
1587
1588 /*
1589  * Write a WIM alternate data stream (ADS) entry to an output buffer.
1590  *
1591  * @ads_entry:
1592  *      The ADS entry to write.
1593  *
1594  * @hash:
1595  *      The hash field to use (instead of the one stored directly in the ADS
1596  *      entry, which isn't valid if the inode has been "resolved").
1597  *
1598  * @p:
1599  *      The memory location to which to write the data.
1600  *
1601  * Returns a pointer to the byte after the last byte written.
1602  */
1603 static u8 *
1604 write_ads_entry(const struct wim_ads_entry *ads_entry,
1605                 const u8 *hash, u8 * restrict p)
1606 {
1607         struct wim_ads_entry_on_disk *disk_ads_entry =
1608                         (struct wim_ads_entry_on_disk*)p;
1609         u8 *orig_p = p;
1610
1611         disk_ads_entry->reserved = cpu_to_le64(ads_entry->reserved);
1612         copy_hash(disk_ads_entry->hash, hash);
1613         disk_ads_entry->stream_name_nbytes = cpu_to_le16(ads_entry->stream_name_nbytes);
1614         p += sizeof(struct wim_ads_entry_on_disk);
1615         if (ads_entry->stream_name_nbytes) {
1616                 p = mempcpy(p, ads_entry->stream_name,
1617                             (u32)ads_entry->stream_name_nbytes + 2);
1618         }
1619         /* Align to 8-byte boundary */
1620         while ((uintptr_t)p & 7)
1621                 *p++ = 0;
1622         disk_ads_entry->length = cpu_to_le64(p - orig_p);
1623         return p;
1624 }
1625
1626 /*
1627  * Write a WIM dentry to an output buffer.
1628  *
1629  * This includes any alternate data stream entries that may follow the dentry
1630  * itself.
1631  *
1632  * @dentry:
1633  *      The dentry to write.
1634  *
1635  * @p:
1636  *      The memory location to which to write the data.
1637  *
1638  * Returns a pointer to the byte following the last written.
1639  */
1640 static u8 *
1641 write_dentry(const struct wim_dentry * restrict dentry, u8 * restrict p)
1642 {
1643         const struct wim_inode *inode;
1644         struct wim_dentry_on_disk *disk_dentry;
1645         const u8 *orig_p;
1646         const u8 *hash;
1647         bool use_dummy_stream;
1648         u16 num_ads;
1649
1650         wimlib_assert(((uintptr_t)p & 7) == 0); /* 8 byte aligned */
1651         orig_p = p;
1652
1653         inode = dentry->d_inode;
1654         use_dummy_stream = inode_needs_dummy_stream(inode);
1655         disk_dentry = (struct wim_dentry_on_disk*)p;
1656
1657         disk_dentry->attributes = cpu_to_le32(inode->i_attributes);
1658         disk_dentry->security_id = cpu_to_le32(inode->i_security_id);
1659         disk_dentry->subdir_offset = cpu_to_le64(dentry->subdir_offset);
1660
1661         disk_dentry->unused_1 = cpu_to_le64(0);
1662         disk_dentry->unused_2 = cpu_to_le64(0);
1663
1664         disk_dentry->creation_time = cpu_to_le64(inode->i_creation_time);
1665         disk_dentry->last_access_time = cpu_to_le64(inode->i_last_access_time);
1666         disk_dentry->last_write_time = cpu_to_le64(inode->i_last_write_time);
1667         if (use_dummy_stream)
1668                 hash = zero_hash;
1669         else
1670                 hash = inode_stream_hash(inode, 0);
1671         copy_hash(disk_dentry->unnamed_stream_hash, hash);
1672         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1673                 disk_dentry->reparse.rp_unknown_1 = cpu_to_le32(inode->i_rp_unknown_1);
1674                 disk_dentry->reparse.reparse_tag = cpu_to_le32(inode->i_reparse_tag);
1675                 disk_dentry->reparse.rp_unknown_2 = cpu_to_le16(inode->i_rp_unknown_2);
1676                 disk_dentry->reparse.not_rpfixed = cpu_to_le16(inode->i_not_rpfixed);
1677         } else {
1678                 disk_dentry->nonreparse.rp_unknown_1 = cpu_to_le32(inode->i_rp_unknown_1);
1679                 disk_dentry->nonreparse.hard_link_group_id =
1680                         cpu_to_le64((inode->i_nlink == 1) ? 0 : inode->i_ino);
1681         }
1682         num_ads = inode->i_num_ads;
1683         if (use_dummy_stream)
1684                 num_ads++;
1685         disk_dentry->num_alternate_data_streams = cpu_to_le16(num_ads);
1686         disk_dentry->short_name_nbytes = cpu_to_le16(dentry->short_name_nbytes);
1687         disk_dentry->file_name_nbytes = cpu_to_le16(dentry->file_name_nbytes);
1688         p += sizeof(struct wim_dentry_on_disk);
1689
1690         wimlib_assert(dentry_is_root(dentry) != dentry_has_long_name(dentry));
1691
1692         if (dentry_has_long_name(dentry))
1693                 p = mempcpy(p, dentry->file_name, (u32)dentry->file_name_nbytes + 2);
1694
1695         if (dentry_has_short_name(dentry))
1696                 p = mempcpy(p, dentry->short_name, (u32)dentry->short_name_nbytes + 2);
1697
1698         /* Align to 8-byte boundary */
1699         while ((uintptr_t)p & 7)
1700                 *p++ = 0;
1701
1702         if (inode->i_extra_size) {
1703                 /* Extra tagged items --- not usually present.  */
1704                 p = mempcpy(p, inode->i_extra, inode->i_extra_size);
1705                 while ((uintptr_t)p & 7)
1706                         *p++ = 0;
1707         }
1708
1709         disk_dentry->length = cpu_to_le64(p - orig_p);
1710
1711         if (use_dummy_stream) {
1712                 hash = inode_unnamed_stream_hash(inode);
1713                 p = write_ads_entry(&(struct wim_ads_entry){}, hash, p);
1714         }
1715
1716         /* Write the alternate data streams entries, if any. */
1717         for (u16 i = 0; i < inode->i_num_ads; i++) {
1718                 hash = inode_stream_hash(inode, i + 1);
1719                 p = write_ads_entry(&inode->i_ads_entries[i], hash, p);
1720         }
1721
1722         return p;
1723 }
1724
1725 static int
1726 write_dir_dentries(struct wim_dentry *dir, void *_pp)
1727 {
1728         if (dir->subdir_offset != 0) {
1729                 u8 **pp = _pp;
1730                 u8 *p = *pp;
1731                 struct wim_dentry *child;
1732
1733                 /* write child dentries */
1734                 for_dentry_child(child, dir)
1735                         p = write_dentry(child, p);
1736
1737                 /* write end of directory entry */
1738                 *(u64*)p = 0;
1739                 p += 8;
1740                 *pp = p;
1741         }
1742         return 0;
1743 }
1744
1745 /*
1746  * Write a directory tree to the metadata resource.
1747  *
1748  * @root:
1749  *      The root of a dentry tree on which calculate_subdir_offsets() has been
1750  *      called.  This cannot be NULL; if the dentry tree is empty, the caller is
1751  *      expected to first generate a dummy root directory.
1752  *
1753  * @p:
1754  *      Pointer to a buffer with enough space for the dentry tree.  This size
1755  *      must have been obtained by calculate_subdir_offsets().
1756  *
1757  * Returns a pointer to the byte following the last written.
1758  */
1759 u8 *
1760 write_dentry_tree(struct wim_dentry *root, u8 *p)
1761 {
1762         DEBUG("Writing dentry tree.");
1763
1764         wimlib_assert(root != NULL);
1765
1766         /* write root dentry and end-of-directory entry following it */
1767         p = write_dentry(root, p);
1768         *(u64*)p = 0;
1769         p += 8;
1770
1771         /* write the rest of the dentry tree */
1772         for_dentry_in_tree(root, write_dir_dentries, &p);
1773
1774         return p;
1775 }