update; add lzms_decompress() stub
[wimlib] / src / dentry.c
1 /*
2  * dentry.c
3  *
4  * In the WIM file format, the dentries are stored in the "metadata resource"
5  * section right after the security data.  Each image in the WIM file has its
6  * own metadata resource with its own security data and dentry tree.  Dentries
7  * in different images may share file resources by referring to the same lookup
8  * table entries.
9  */
10
11 /*
12  * Copyright (C) 2012, 2013 Eric Biggers
13  *
14  * This file is part of wimlib, a library for working with WIM files.
15  *
16  * wimlib is free software; you can redistribute it and/or modify it under the
17  * terms of the GNU General Public License as published by the Free Software
18  * Foundation; either version 3 of the License, or (at your option) any later
19  * version.
20  *
21  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
22  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
23  * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License along with
26  * wimlib; if not, see http://www.gnu.org/licenses/.
27  */
28
29 #ifdef HAVE_CONFIG_H
30 #  include "config.h"
31 #endif
32
33 #include "wimlib.h"
34 #include "wimlib/dentry.h"
35 #include "wimlib/encoding.h"
36 #include "wimlib/endianness.h"
37 #include "wimlib/error.h"
38 #include "wimlib/lookup_table.h"
39 #include "wimlib/metadata.h"
40 #include "wimlib/resource.h"
41 #include "wimlib/security.h"
42 #include "wimlib/sha1.h"
43 #include "wimlib/timestamp.h"
44
45 #include <errno.h>
46
47 /* WIM alternate data stream entry (on-disk format) */
48 struct wim_ads_entry_on_disk {
49         /*  Length of the entry, in bytes.  This apparently includes all
50          *  fixed-length fields, plus the stream name and null terminator if
51          *  present, and the padding up to an 8 byte boundary.  wimlib is a
52          *  little less strict when reading the entries, and only requires that
53          *  the number of bytes from this field is at least as large as the size
54          *  of the fixed length fields and stream name without null terminator.
55          *  */
56         le64  length;
57
58         le64  reserved;
59
60         /* SHA1 message digest of the uncompressed stream; or, alternatively,
61          * can be all zeroes if the stream has zero length. */
62         u8 hash[SHA1_HASH_SIZE];
63
64         /* Length of the stream name, in bytes.  0 if the stream is unnamed.  */
65         le16 stream_name_nbytes;
66
67         /* Stream name in UTF-16LE.  It is @stream_name_nbytes bytes long,
68          * excluding the the null terminator.  There is a null terminator
69          * character if @stream_name_nbytes != 0; i.e., if this stream is named.
70          * */
71         utf16lechar stream_name[];
72 } _packed_attribute;
73
74 #define WIM_ADS_ENTRY_DISK_SIZE 38
75
76 /* On-disk format of a WIM dentry (directory entry), located in the metadata
77  * resource for a WIM image.  */
78 struct wim_dentry_on_disk {
79
80         /* Length of this directory entry in bytes, not including any alternate
81          * data stream entries.  Should be a multiple of 8 so that the following
82          * dentry or alternate data stream entry is aligned on an 8-byte
83          * boundary.  (If not, wimlib will round it up.)  It must be at least as
84          * long as the fixed-length fields of the dentry (WIM_DENTRY_DISK_SIZE),
85          * plus the lengths of the file name and/or short name if present.
86          *
87          * It is also possible for this field to be 0.  This situation, which is
88          * undocumented, indicates the end of a list of sibling nodes in a
89          * directory.  It also means the real length is 8, because the dentry
90          * included only the length field, but that takes up 8 bytes.  */
91         le64 length;
92
93         /* Attributes of the file or directory.  This is a bitwise OR of the
94          * FILE_ATTRIBUTE_* constants and should correspond to the value
95          * retrieved by GetFileAttributes() on Windows. */
96         le32 attributes;
97
98         /* A value that specifies the security descriptor for this file or
99          * directory.  If -1, the file or directory has no security descriptor.
100          * Otherwise, it is a 0-based index into the WIM image's table of
101          * security descriptors (see: `struct wim_security_data') */
102         sle32 security_id;
103
104         /* Offset, in bytes, from the start of the uncompressed metadata
105          * resource of this directory's child directory entries, or 0 if this
106          * directory entry does not correspond to a directory or otherwise does
107          * not have any children. */
108         le64 subdir_offset;
109
110         /* Reserved fields */
111         le64 unused_1;
112         le64 unused_2;
113
114
115         /* Creation time, last access time, and last write time, in
116          * 100-nanosecond intervals since 12:00 a.m UTC January 1, 1601.  They
117          * should correspond to the times gotten by calling GetFileTime() on
118          * Windows. */
119         le64 creation_time;
120         le64 last_access_time;
121         le64 last_write_time;
122
123         /* Vaguely, the SHA-1 message digest ("hash") of the file's contents.
124          * More specifically, this is for the "unnamed data stream" rather than
125          * any "alternate data streams".  This hash value is used to look up the
126          * corresponding entry in the WIM's stream lookup table to actually find
127          * the file contents within the WIM.
128          *
129          * If the file has no unnamed data stream (e.g. is a directory), then
130          * this field will be all zeroes.  If the unnamed data stream is empty
131          * (i.e. an "empty file"), then this field is also expected to be all
132          * zeroes.  (It will be if wimlib created the WIM image, at least;
133          * otherwise it can't be ruled out that the SHA-1 message digest of 0
134          * bytes of data is given explicitly.)
135          *
136          * If the file has reparse data, then this field will instead specify
137          * the SHA-1 message digest of the reparse data.  If it is somehow
138          * possible for a file to have both an unnamed data stream and reparse
139          * data, then this is not handled by wimlib.
140          *
141          * As a further special case, if this field is all zeroes but there is
142          * an alternate data stream entry with no name and a nonzero SHA-1
143          * message digest field, then that hash must be used instead of this
144          * one.  (wimlib does not use this quirk on WIM images it creates.)
145          */
146         u8 unnamed_stream_hash[SHA1_HASH_SIZE];
147
148         /* The format of the following data is not yet completely known and they
149          * do not correspond to Microsoft's documentation.
150          *
151          * If this directory entry is for a reparse point (has
152          * FILE_ATTRIBUTE_REPARSE_POINT set in the attributes field), then the
153          * version of the following fields containing the reparse tag is valid.
154          * Furthermore, the field notated as not_rpfixed, as far as I can tell,
155          * is supposed to be set to 1 if reparse point fixups (a.k.a. fixing the
156          * targets of absolute symbolic links) were *not* done, and otherwise 0.
157          *
158          * If this directory entry is not for a reparse point, then the version
159          * of the following fields containing the hard_link_group_id is valid.
160          * All MS says about this field is that "If this file is part of a hard
161          * link set, all the directory entries in the set will share the same
162          * value in this field.".  However, more specifically I have observed
163          * the following:
164          *    - If the file is part of a hard link set of size 1, then the
165          *    hard_link_group_id should be set to either 0, which is treated
166          *    specially as indicating "not hardlinked", or any unique value.
167          *    - The specific nonzero values used to identity hard link sets do
168          *    not matter, as long as they are unique.
169          *    - However, due to bugs in Microsoft's software, it is actually NOT
170          *    guaranteed that directory entries that share the same hard link
171          *    group ID are actually hard linked to each either.  We have to
172          *    handle this by using special code to use distinguishing features
173          *    (which is possible because some information about the underlying
174          *    inode is repeated in each dentry) to split up these fake hard link
175          *    groups into what they actually are supposed to be.
176          */
177         union {
178                 struct {
179                         le32 rp_unknown_1;
180                         le32 reparse_tag;
181                         le16 rp_unknown_2;
182                         le16 not_rpfixed;
183                 } _packed_attribute reparse;
184                 struct {
185                         le32 rp_unknown_1;
186                         le64 hard_link_group_id;
187                 } _packed_attribute nonreparse;
188         };
189
190         /* Number of alternate data stream entries that directly follow this
191          * dentry on-disk. */
192         le16 num_alternate_data_streams;
193
194         /* Length of this file's UTF-16LE encoded short name (8.3 DOS-compatible
195          * name), if present, in bytes, excluding the null terminator.  If this
196          * file has no short name, then this field should be 0.  */
197         le16 short_name_nbytes;
198
199         /* Length of this file's UTF-16LE encoded "long" name, excluding the
200          * null terminator.  If this file has no short name, then this field
201          * should be 0.  It's expected that only the root dentry has this field
202          * set to 0.  */
203         le16 file_name_nbytes;
204
205         /* Followed by variable length file name, in UTF16-LE, if
206          * file_name_nbytes != 0.  Includes null terminator. */
207         /*utf16lechar file_name[];*/
208
209         /* Followed by variable length short name, in UTF16-LE, if
210          * short_name_nbytes != 0.  Includes null terminator. */
211         /*utf16lechar short_name[];*/
212 } _packed_attribute;
213
214 #define WIM_DENTRY_DISK_SIZE 102
215
216 /* Calculates the unaligned length, in bytes, of an on-disk WIM dentry that has
217  * a file name and short name that take the specified numbers of bytes.  This
218  * excludes any alternate data stream entries that may follow the dentry. */
219 static u64
220 dentry_correct_length_unaligned(u16 file_name_nbytes, u16 short_name_nbytes)
221 {
222         u64 length = sizeof(struct wim_dentry_on_disk);
223         if (file_name_nbytes)
224                 length += file_name_nbytes + 2;
225         if (short_name_nbytes)
226                 length += short_name_nbytes + 2;
227         return length;
228 }
229
230 /* Calculates the unaligned length, in bytes, of an on-disk WIM dentry, based on
231  * the file name length and short name length.  Note that dentry->length is
232  * ignored; also, this excludes any alternate data stream entries that may
233  * follow the dentry. */
234 static u64
235 dentry_correct_length_aligned(const struct wim_dentry *dentry)
236 {
237         u64 len;
238
239         len = dentry_correct_length_unaligned(dentry->file_name_nbytes,
240                                               dentry->short_name_nbytes);
241         return (len + 7) & ~7;
242 }
243
244 /* Duplicates a string of system-dependent encoding into a UTF-16LE string and
245  * returns the string and its length, in bytes, in the pointer arguments.  Frees
246  * any existing string at the return location before overwriting it. */
247 static int
248 get_utf16le_name(const tchar *name, utf16lechar **name_utf16le_ret,
249                  u16 *name_utf16le_nbytes_ret)
250 {
251         utf16lechar *name_utf16le;
252         size_t name_utf16le_nbytes;
253         int ret;
254 #if TCHAR_IS_UTF16LE
255         name_utf16le_nbytes = tstrlen(name) * sizeof(utf16lechar);
256         name_utf16le = MALLOC(name_utf16le_nbytes + sizeof(utf16lechar));
257         if (name_utf16le == NULL)
258                 return WIMLIB_ERR_NOMEM;
259         memcpy(name_utf16le, name, name_utf16le_nbytes + sizeof(utf16lechar));
260         ret = 0;
261 #else
262
263         ret = tstr_to_utf16le(name, tstrlen(name), &name_utf16le,
264                               &name_utf16le_nbytes);
265         if (ret == 0) {
266                 if (name_utf16le_nbytes > 0xffff) {
267                         FREE(name_utf16le);
268                         ERROR("Multibyte string \"%"TS"\" is too long!", name);
269                         ret = WIMLIB_ERR_INVALID_UTF8_STRING;
270                 }
271         }
272 #endif
273         if (ret == 0) {
274                 FREE(*name_utf16le_ret);
275                 *name_utf16le_ret = name_utf16le;
276                 *name_utf16le_nbytes_ret = name_utf16le_nbytes;
277         }
278         return ret;
279 }
280
281 /* Sets the name of a WIM dentry from a multibyte string. */
282 int
283 set_dentry_name(struct wim_dentry *dentry, const tchar *new_name)
284 {
285         int ret;
286         ret = get_utf16le_name(new_name, &dentry->file_name,
287                                &dentry->file_name_nbytes);
288         if (ret == 0) {
289                 /* Clear the short name and recalculate the dentry length */
290                 if (dentry_has_short_name(dentry)) {
291                         FREE(dentry->short_name);
292                         dentry->short_name = NULL;
293                         dentry->short_name_nbytes = 0;
294                 }
295         }
296         return ret;
297 }
298
299 /* Returns the total length of a WIM alternate data stream entry on-disk,
300  * including the stream name, the null terminator, AND the padding after the
301  * entry to align the next ADS entry or dentry on an 8-byte boundary. */
302 static u64
303 ads_entry_total_length(const struct wim_ads_entry *entry)
304 {
305         u64 len = sizeof(struct wim_ads_entry_on_disk);
306         if (entry->stream_name_nbytes)
307                 len += entry->stream_name_nbytes + 2;
308         return (len + 7) & ~7;
309 }
310
311 /*
312  * Determine whether to include a "dummy" stream when writing a WIM dentry:
313  *
314  * Some versions of Microsoft's WIM software (the boot driver(s) in WinPE 3.0,
315  * for example) contain a bug where they assume the first alternate data stream
316  * (ADS) entry of a dentry with a nonzero ADS count specifies the unnamed
317  * stream, even if it has a name and the unnamed stream is already specified in
318  * the hash field of the dentry itself.
319  *
320  * wimlib has to work around this behavior by carefully emulating the behavior
321  * of (most versions of) ImageX/WIMGAPI, which move the unnamed stream reference
322  * into the alternate stream entries whenever there are named data streams, even
323  * though there is already a field in the dentry itself for the unnamed stream
324  * reference, which then goes to waste.
325  */
326 static inline bool inode_needs_dummy_stream(const struct wim_inode *inode)
327 {
328         return (inode->i_num_ads > 0 &&
329                 inode->i_num_ads < 0xffff && /* overflow check */
330                 inode->i_canonical_streams); /* assume the dentry is okay if it
331                                                 already had an unnamed ADS entry
332                                                 when it was read in  */
333 }
334
335 /* Calculate the total number of bytes that will be consumed when a WIM dentry
336  * is written.  This includes base dentry and name fields as well as all
337  * alternate data stream entries and alignment bytes.  */
338 u64
339 dentry_out_total_length(const struct wim_dentry *dentry)
340 {
341         u64 length = dentry_correct_length_aligned(dentry);
342         const struct wim_inode *inode = dentry->d_inode;
343
344         if (inode_needs_dummy_stream(inode))
345                 length += ads_entry_total_length(&(struct wim_ads_entry){});
346
347         for (u16 i = 0; i < inode->i_num_ads; i++)
348                 length += ads_entry_total_length(&inode->i_ads_entries[i]);
349
350         return length;
351 }
352
353 /* Calculate the aligned, total length of a dentry, including all alternate data
354  * stream entries.  Uses dentry->length.  */
355 static u64
356 dentry_in_total_length(const struct wim_dentry *dentry)
357 {
358         u64 length = dentry->length;
359         const struct wim_inode *inode = dentry->d_inode;
360         for (u16 i = 0; i < inode->i_num_ads; i++)
361                 length += ads_entry_total_length(&inode->i_ads_entries[i]);
362         return (length + 7) & ~7;
363 }
364
365 int
366 for_dentry_in_rbtree(struct rb_node *root,
367                      int (*visitor)(struct wim_dentry *, void *),
368                      void *arg)
369 {
370         int ret;
371         struct rb_node *node = root;
372         LIST_HEAD(stack);
373         while (1) {
374                 if (node) {
375                         list_add(&rbnode_dentry(node)->tmp_list, &stack);
376                         node = node->rb_left;
377                 } else {
378                         struct list_head *next;
379                         struct wim_dentry *dentry;
380
381                         next = stack.next;
382                         if (next == &stack)
383                                 return 0;
384                         dentry = container_of(next, struct wim_dentry, tmp_list);
385                         list_del(next);
386                         ret = visitor(dentry, arg);
387                         if (ret != 0)
388                                 return ret;
389                         node = dentry->rb_node.rb_right;
390                 }
391         }
392 }
393
394 static int
395 for_dentry_tree_in_rbtree_depth(struct rb_node *node,
396                                 int (*visitor)(struct wim_dentry*, void*),
397                                 void *arg)
398 {
399         int ret;
400         if (node) {
401                 ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
402                                                       visitor, arg);
403                 if (ret != 0)
404                         return ret;
405                 ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
406                                                       visitor, arg);
407                 if (ret != 0)
408                         return ret;
409                 ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
410                 if (ret != 0)
411                         return ret;
412         }
413         return 0;
414 }
415
416 static int
417 for_dentry_tree_in_rbtree(struct rb_node *node,
418                           int (*visitor)(struct wim_dentry*, void*),
419                           void *arg)
420 {
421         int ret;
422         if (node) {
423                 ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
424                 if (ret)
425                         return ret;
426                 ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
427                 if (ret)
428                         return ret;
429                 ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
430                 if (ret)
431                         return ret;
432         }
433         return 0;
434 }
435
436 /* Calls a function on all directory entries in a WIM dentry tree.  Logically,
437  * this is a pre-order traversal (the function is called on a parent dentry
438  * before its children), but sibling dentries will be visited in order as well.
439  * */
440 int
441 for_dentry_in_tree(struct wim_dentry *root,
442                    int (*visitor)(struct wim_dentry*, void*), void *arg)
443 {
444         int ret;
445
446         if (root == NULL)
447                 return 0;
448         ret = (*visitor)(root, arg);
449         if (ret)
450                 return ret;
451         return for_dentry_tree_in_rbtree(root->d_inode->i_children.rb_node,
452                                          visitor,
453                                          arg);
454 }
455
456 /* Like for_dentry_in_tree(), but the visitor function is always called on a
457  * dentry's children before on itself. */
458 int
459 for_dentry_in_tree_depth(struct wim_dentry *root,
460                          int (*visitor)(struct wim_dentry*, void*), void *arg)
461 {
462         int ret;
463
464         if (root == NULL)
465                 return 0;
466         ret = for_dentry_tree_in_rbtree_depth(root->d_inode->i_children.rb_node,
467                                               visitor, arg);
468         if (ret)
469                 return ret;
470         return (*visitor)(root, arg);
471 }
472
473 /* Calculate the full path of @dentry.  The full path of its parent must have
474  * already been calculated, or it must be the root dentry. */
475 int
476 calculate_dentry_full_path(struct wim_dentry *dentry)
477 {
478         tchar *full_path;
479         u32 full_path_nbytes;
480         int ret;
481
482         if (dentry->_full_path)
483                 return 0;
484
485         if (dentry_is_root(dentry)) {
486                 static const tchar _root_path[] = {WIM_PATH_SEPARATOR, T('\0')};
487                 full_path = TSTRDUP(_root_path);
488                 if (full_path == NULL)
489                         return WIMLIB_ERR_NOMEM;
490                 full_path_nbytes = 1 * sizeof(tchar);
491         } else {
492                 struct wim_dentry *parent;
493                 tchar *parent_full_path;
494                 u32 parent_full_path_nbytes;
495                 size_t filename_nbytes;
496
497                 parent = dentry->parent;
498                 if (dentry_is_root(parent)) {
499                         parent_full_path = T("");
500                         parent_full_path_nbytes = 0;
501                 } else {
502                         if (parent->_full_path == NULL) {
503                                 ret = calculate_dentry_full_path(parent);
504                                 if (ret)
505                                         return ret;
506                         }
507                         parent_full_path = parent->_full_path;
508                         parent_full_path_nbytes = parent->full_path_nbytes;
509                 }
510
511                 /* Append this dentry's name as a tchar string to the full path
512                  * of the parent followed by the path separator */
513         #if TCHAR_IS_UTF16LE
514                 filename_nbytes = dentry->file_name_nbytes;
515         #else
516                 {
517                         int ret = utf16le_to_tstr_nbytes(dentry->file_name,
518                                                          dentry->file_name_nbytes,
519                                                          &filename_nbytes);
520                         if (ret)
521                                 return ret;
522                 }
523         #endif
524
525                 full_path_nbytes = parent_full_path_nbytes + sizeof(tchar) +
526                                    filename_nbytes;
527                 full_path = MALLOC(full_path_nbytes + sizeof(tchar));
528                 if (full_path == NULL)
529                         return WIMLIB_ERR_NOMEM;
530                 memcpy(full_path, parent_full_path, parent_full_path_nbytes);
531                 full_path[parent_full_path_nbytes / sizeof(tchar)] = WIM_PATH_SEPARATOR;
532         #if TCHAR_IS_UTF16LE
533                 memcpy(&full_path[parent_full_path_nbytes / sizeof(tchar) + 1],
534                        dentry->file_name,
535                        filename_nbytes + sizeof(tchar));
536         #else
537                 utf16le_to_tstr_buf(dentry->file_name,
538                                     dentry->file_name_nbytes,
539                                     &full_path[parent_full_path_nbytes /
540                                                sizeof(tchar) + 1]);
541         #endif
542         }
543         dentry->_full_path = full_path;
544         dentry->full_path_nbytes= full_path_nbytes;
545         return 0;
546 }
547
548 static int
549 do_calculate_dentry_full_path(struct wim_dentry *dentry, void *_ignore)
550 {
551         return calculate_dentry_full_path(dentry);
552 }
553
554 int
555 calculate_dentry_tree_full_paths(struct wim_dentry *root)
556 {
557         return for_dentry_in_tree(root, do_calculate_dentry_full_path, NULL);
558 }
559
560 tchar *
561 dentry_full_path(struct wim_dentry *dentry)
562 {
563         calculate_dentry_full_path(dentry);
564         return dentry->_full_path;
565 }
566
567 static int
568 increment_subdir_offset(struct wim_dentry *dentry, void *subdir_offset_p)
569 {
570         *(u64*)subdir_offset_p += dentry_out_total_length(dentry);
571         return 0;
572 }
573
574 static int
575 call_calculate_subdir_offsets(struct wim_dentry *dentry, void *subdir_offset_p)
576 {
577         calculate_subdir_offsets(dentry, subdir_offset_p);
578         return 0;
579 }
580
581 /*
582  * Recursively calculates the subdir offsets for a directory tree.
583  *
584  * @dentry:  The root of the directory tree.
585  * @subdir_offset_p:  The current subdirectory offset; i.e., the subdirectory
586  *                    offset for @dentry.
587  */
588 void
589 calculate_subdir_offsets(struct wim_dentry *dentry, u64 *subdir_offset_p)
590 {
591         struct rb_node *node;
592
593         dentry->subdir_offset = *subdir_offset_p;
594         node = dentry->d_inode->i_children.rb_node;
595         if (node) {
596                 /* Advance the subdir offset by the amount of space the children
597                  * of this dentry take up. */
598                 for_dentry_in_rbtree(node, increment_subdir_offset, subdir_offset_p);
599
600                 /* End-of-directory dentry on disk. */
601                 *subdir_offset_p += 8;
602
603                 /* Recursively call calculate_subdir_offsets() on all the
604                  * children. */
605                 for_dentry_in_rbtree(node, call_calculate_subdir_offsets, subdir_offset_p);
606         } else {
607                 /* On disk, childless directories have a valid subdir_offset
608                  * that points to an 8-byte end-of-directory dentry.  Regular
609                  * files or reparse points have a subdir_offset of 0. */
610                 if (dentry_is_directory(dentry))
611                         *subdir_offset_p += 8;
612                 else
613                         dentry->subdir_offset = 0;
614         }
615 }
616
617 /* Case-sensitive UTF-16LE dentry or stream name comparison.  Used on both UNIX
618  * (always) and Windows (sometimes) */
619 static int
620 compare_utf16le_names_case_sensitive(const utf16lechar *name1, size_t nbytes1,
621                                      const utf16lechar *name2, size_t nbytes2)
622 {
623         /* Return the result if the strings differ up to their minimum length.
624          * Note that we cannot use strcmp() or strncmp() here, as the strings
625          * are in UTF-16LE format. */
626         int result = memcmp(name1, name2, min(nbytes1, nbytes2));
627         if (result)
628                 return result;
629
630         /* The strings are the same up to their minimum length, so return a
631          * result based on their lengths. */
632         if (nbytes1 < nbytes2)
633                 return -1;
634         else if (nbytes1 > nbytes2)
635                 return 1;
636         else
637                 return 0;
638 }
639
640 #ifdef __WIN32__
641 /* Windoze: Case-insensitive UTF-16LE dentry or stream name comparison */
642 static int
643 compare_utf16le_names_case_insensitive(const utf16lechar *name1, size_t nbytes1,
644                                        const utf16lechar *name2, size_t nbytes2)
645 {
646         /* Return the result if the strings differ up to their minimum length.
647          * */
648         int result = _wcsnicmp((const wchar_t*)name1, (const wchar_t*)name2,
649                                min(nbytes1 / 2, nbytes2 / 2));
650         if (result)
651                 return result;
652
653         /* The strings are the same up to their minimum length, so return a
654          * result based on their lengths. */
655         if (nbytes1 < nbytes2)
656                 return -1;
657         else if (nbytes1 > nbytes2)
658                 return 1;
659         else
660                 return 0;
661 }
662 #endif /* __WIN32__ */
663
664 #ifdef __WIN32__
665 #  define compare_utf16le_names compare_utf16le_names_case_insensitive
666 #else
667 #  define compare_utf16le_names compare_utf16le_names_case_sensitive
668 #endif
669
670
671 #ifdef __WIN32__
672 static int
673 dentry_compare_names_case_insensitive(const struct wim_dentry *d1,
674                                       const struct wim_dentry *d2)
675 {
676         return compare_utf16le_names_case_insensitive(d1->file_name,
677                                                       d1->file_name_nbytes,
678                                                       d2->file_name,
679                                                       d2->file_name_nbytes);
680 }
681 #endif /* __WIN32__ */
682
683 static int
684 dentry_compare_names_case_sensitive(const struct wim_dentry *d1,
685                                     const struct wim_dentry *d2)
686 {
687         return compare_utf16le_names_case_sensitive(d1->file_name,
688                                                     d1->file_name_nbytes,
689                                                     d2->file_name,
690                                                     d2->file_name_nbytes);
691 }
692
693 #ifdef __WIN32__
694 #  define dentry_compare_names dentry_compare_names_case_insensitive
695 #else
696 #  define dentry_compare_names dentry_compare_names_case_sensitive
697 #endif
698
699 /* Return %true iff the alternate data stream entry @entry has the UTF-16LE
700  * stream name @name that has length @name_nbytes bytes. */
701 static inline bool
702 ads_entry_has_name(const struct wim_ads_entry *entry,
703                    const utf16lechar *name, size_t name_nbytes)
704 {
705         return !compare_utf16le_names(name, name_nbytes,
706                                       entry->stream_name,
707                                       entry->stream_name_nbytes);
708 }
709
710 /* Given a UTF-16LE filename and a directory, look up the dentry for the file.
711  * Return it if found, otherwise NULL.  This is case-sensitive on UNIX and
712  * case-insensitive on Windows. */
713 struct wim_dentry *
714 get_dentry_child_with_utf16le_name(const struct wim_dentry *dentry,
715                                    const utf16lechar *name,
716                                    size_t name_nbytes)
717 {
718         struct rb_node *node;
719
720 #ifdef __WIN32__
721         node = dentry->d_inode->i_children_case_insensitive.rb_node;
722 #else
723         node = dentry->d_inode->i_children.rb_node;
724 #endif
725
726         struct wim_dentry *child;
727         while (node) {
728         #ifdef __WIN32__
729                 child = rb_entry(node, struct wim_dentry, rb_node_case_insensitive);
730         #else
731                 child = rbnode_dentry(node);
732         #endif
733                 int result = compare_utf16le_names(name, name_nbytes,
734                                                    child->file_name,
735                                                    child->file_name_nbytes);
736                 if (result < 0)
737                         node = node->rb_left;
738                 else if (result > 0)
739                         node = node->rb_right;
740                 else {
741                 #ifdef __WIN32__
742                         if (!list_empty(&child->case_insensitive_conflict_list))
743                         {
744                                 WARNING("Result of case-insensitive lookup is ambiguous "
745                                         "(returning \"%ls\" instead of \"%ls\")",
746                                         child->file_name,
747                                         container_of(child->case_insensitive_conflict_list.next,
748                                                      struct wim_dentry,
749                                                      case_insensitive_conflict_list)->file_name);
750                         }
751                 #endif
752                         return child;
753                 }
754         }
755         return NULL;
756 }
757
758 /* Returns the child of @dentry that has the file name @name.  Returns NULL if
759  * no child has the name. */
760 struct wim_dentry *
761 get_dentry_child_with_name(const struct wim_dentry *dentry, const tchar *name)
762 {
763 #if TCHAR_IS_UTF16LE
764         return get_dentry_child_with_utf16le_name(dentry, name,
765                                                   tstrlen(name) * sizeof(tchar));
766 #else
767         utf16lechar *utf16le_name;
768         size_t utf16le_name_nbytes;
769         int ret;
770         struct wim_dentry *child;
771
772         ret = tstr_to_utf16le(name, tstrlen(name) * sizeof(tchar),
773                               &utf16le_name, &utf16le_name_nbytes);
774         if (ret) {
775                 child = NULL;
776         } else {
777                 child = get_dentry_child_with_utf16le_name(dentry,
778                                                            utf16le_name,
779                                                            utf16le_name_nbytes);
780                 FREE(utf16le_name);
781         }
782         return child;
783 #endif
784 }
785
786 static struct wim_dentry *
787 get_dentry_utf16le(WIMStruct *wim, const utf16lechar *path)
788 {
789         struct wim_dentry *cur_dentry, *parent_dentry;
790         const utf16lechar *p, *pp;
791
792         cur_dentry = parent_dentry = wim_root_dentry(wim);
793         if (cur_dentry == NULL) {
794                 errno = ENOENT;
795                 return NULL;
796         }
797         p = path;
798         while (1) {
799                 while (*p == cpu_to_le16(WIM_PATH_SEPARATOR))
800                         p++;
801                 if (*p == cpu_to_le16('\0'))
802                         break;
803                 pp = p;
804                 while (*pp != cpu_to_le16(WIM_PATH_SEPARATOR) &&
805                        *pp != cpu_to_le16('\0'))
806                         pp++;
807
808                 cur_dentry = get_dentry_child_with_utf16le_name(parent_dentry, p,
809                                                                 (void*)pp - (void*)p);
810                 if (cur_dentry == NULL)
811                         break;
812                 p = pp;
813                 parent_dentry = cur_dentry;
814         }
815         if (cur_dentry == NULL) {
816                 if (dentry_is_directory(parent_dentry))
817                         errno = ENOENT;
818                 else
819                         errno = ENOTDIR;
820         }
821         return cur_dentry;
822 }
823
824 /*
825  * Returns the dentry in the currently selected WIM image named by @path
826  * starting from the root of the WIM image, or NULL if there is no such dentry.
827  *
828  * On Windows, the search is done case-insensitively.
829  */
830 struct wim_dentry *
831 get_dentry(WIMStruct *wim, const tchar *path)
832 {
833 #if TCHAR_IS_UTF16LE
834         return get_dentry_utf16le(wim, path);
835 #else
836         utf16lechar *path_utf16le;
837         size_t path_utf16le_nbytes;
838         int ret;
839         struct wim_dentry *dentry;
840
841         ret = tstr_to_utf16le(path, tstrlen(path) * sizeof(tchar),
842                               &path_utf16le, &path_utf16le_nbytes);
843         if (ret)
844                 return NULL;
845         dentry = get_dentry_utf16le(wim, path_utf16le);
846         FREE(path_utf16le);
847         return dentry;
848 #endif
849 }
850
851 struct wim_inode *
852 wim_pathname_to_inode(WIMStruct *wim, const tchar *path)
853 {
854         struct wim_dentry *dentry;
855         dentry = get_dentry(wim, path);
856         if (dentry)
857                 return dentry->d_inode;
858         else
859                 return NULL;
860 }
861
862 /* Takes in a path of length @len in @buf, and transforms it into a string for
863  * the path of its parent directory. */
864 static void
865 to_parent_name(tchar *buf, size_t len)
866 {
867         ssize_t i = (ssize_t)len - 1;
868         while (i >= 0 && buf[i] == WIM_PATH_SEPARATOR)
869                 i--;
870         while (i >= 0 && buf[i] != WIM_PATH_SEPARATOR)
871                 i--;
872         while (i >= 0 && buf[i] == WIM_PATH_SEPARATOR)
873                 i--;
874         buf[i + 1] = T('\0');
875 }
876
877 /* Returns the dentry that corresponds to the parent directory of @path, or NULL
878  * if the dentry is not found. */
879 struct wim_dentry *
880 get_parent_dentry(WIMStruct *wim, const tchar *path)
881 {
882         size_t path_len = tstrlen(path);
883         tchar buf[path_len + 1];
884
885         tmemcpy(buf, path, path_len + 1);
886         to_parent_name(buf, path_len);
887         return get_dentry(wim, buf);
888 }
889
890 /* Prints the full path of a dentry. */
891 int
892 print_dentry_full_path(struct wim_dentry *dentry, void *_ignore)
893 {
894         int ret = calculate_dentry_full_path(dentry);
895         if (ret)
896                 return ret;
897         tprintf(T("%"TS"\n"), dentry->_full_path);
898         return 0;
899 }
900
901 /* We want to be able to show the names of the file attribute flags that are
902  * set. */
903 struct file_attr_flag {
904         u32 flag;
905         const tchar *name;
906 };
907 struct file_attr_flag file_attr_flags[] = {
908         {FILE_ATTRIBUTE_READONLY,           T("READONLY")},
909         {FILE_ATTRIBUTE_HIDDEN,             T("HIDDEN")},
910         {FILE_ATTRIBUTE_SYSTEM,             T("SYSTEM")},
911         {FILE_ATTRIBUTE_DIRECTORY,          T("DIRECTORY")},
912         {FILE_ATTRIBUTE_ARCHIVE,            T("ARCHIVE")},
913         {FILE_ATTRIBUTE_DEVICE,             T("DEVICE")},
914         {FILE_ATTRIBUTE_NORMAL,             T("NORMAL")},
915         {FILE_ATTRIBUTE_TEMPORARY,          T("TEMPORARY")},
916         {FILE_ATTRIBUTE_SPARSE_FILE,        T("SPARSE_FILE")},
917         {FILE_ATTRIBUTE_REPARSE_POINT,      T("REPARSE_POINT")},
918         {FILE_ATTRIBUTE_COMPRESSED,         T("COMPRESSED")},
919         {FILE_ATTRIBUTE_OFFLINE,            T("OFFLINE")},
920         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED,T("NOT_CONTENT_INDEXED")},
921         {FILE_ATTRIBUTE_ENCRYPTED,          T("ENCRYPTED")},
922         {FILE_ATTRIBUTE_VIRTUAL,            T("VIRTUAL")},
923 };
924
925 /* Prints a directory entry.  @lookup_table is a pointer to the lookup table, if
926  * available.  If the dentry is unresolved and the lookup table is NULL, the
927  * lookup table entries will not be printed.  Otherwise, they will be. */
928 int
929 print_dentry(struct wim_dentry *dentry, void *lookup_table)
930 {
931         const u8 *hash;
932         struct wim_lookup_table_entry *lte;
933         const struct wim_inode *inode = dentry->d_inode;
934         tchar buf[50];
935
936         tprintf(T("[DENTRY]\n"));
937         tprintf(T("Length            = %"PRIu64"\n"), dentry->length);
938         tprintf(T("Attributes        = 0x%x\n"), inode->i_attributes);
939         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++)
940                 if (file_attr_flags[i].flag & inode->i_attributes)
941                         tprintf(T("    FILE_ATTRIBUTE_%"TS" is set\n"),
942                                 file_attr_flags[i].name);
943         tprintf(T("Security ID       = %d\n"), inode->i_security_id);
944         tprintf(T("Subdir offset     = %"PRIu64"\n"), dentry->subdir_offset);
945
946         wim_timestamp_to_str(inode->i_creation_time, buf, sizeof(buf));
947         tprintf(T("Creation Time     = %"TS"\n"), buf);
948
949         wim_timestamp_to_str(inode->i_last_access_time, buf, sizeof(buf));
950         tprintf(T("Last Access Time  = %"TS"\n"), buf);
951
952         wim_timestamp_to_str(inode->i_last_write_time, buf, sizeof(buf));
953         tprintf(T("Last Write Time   = %"TS"\n"), buf);
954
955         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
956                 tprintf(T("Reparse Tag       = 0x%"PRIx32"\n"), inode->i_reparse_tag);
957                 tprintf(T("Reparse Point Flags = 0x%"PRIx16"\n"),
958                         inode->i_not_rpfixed);
959                 tprintf(T("Reparse Point Unknown 2 = 0x%"PRIx32"\n"),
960                         inode->i_rp_unknown_2);
961         }
962         tprintf(T("Reparse Point Unknown 1 = 0x%"PRIx32"\n"),
963                 inode->i_rp_unknown_1);
964         tprintf(T("Hard Link Group   = 0x%"PRIx64"\n"), inode->i_ino);
965         tprintf(T("Hard Link Group Size = %"PRIu32"\n"), inode->i_nlink);
966         tprintf(T("Number of Alternate Data Streams = %hu\n"), inode->i_num_ads);
967         if (dentry_has_long_name(dentry))
968                 wimlib_printf(T("Filename = \"%"WS"\"\n"), dentry->file_name);
969         if (dentry_has_short_name(dentry))
970                 wimlib_printf(T("Short Name \"%"WS"\"\n"), dentry->short_name);
971         if (dentry->_full_path)
972                 tprintf(T("Full Path = \"%"TS"\"\n"), dentry->_full_path);
973
974         lte = inode_stream_lte(dentry->d_inode, 0, lookup_table);
975         if (lte) {
976                 print_lookup_table_entry(lte, stdout);
977         } else {
978                 hash = inode_stream_hash(inode, 0);
979                 if (hash) {
980                         tprintf(T("Hash              = 0x"));
981                         print_hash(hash, stdout);
982                         tputchar(T('\n'));
983                         tputchar(T('\n'));
984                 }
985         }
986         for (u16 i = 0; i < inode->i_num_ads; i++) {
987                 tprintf(T("[Alternate Stream Entry %u]\n"), i);
988                 wimlib_printf(T("Name = \"%"WS"\"\n"),
989                               inode->i_ads_entries[i].stream_name);
990                 tprintf(T("Name Length (UTF16 bytes) = %hu\n"),
991                        inode->i_ads_entries[i].stream_name_nbytes);
992                 hash = inode_stream_hash(inode, i + 1);
993                 if (hash) {
994                         tprintf(T("Hash              = 0x"));
995                         print_hash(hash, stdout);
996                         tputchar(T('\n'));
997                 }
998                 print_lookup_table_entry(inode_stream_lte(inode, i + 1, lookup_table),
999                                          stdout);
1000         }
1001         return 0;
1002 }
1003
1004 /* Initializations done on every `struct wim_dentry'. */
1005 static void
1006 dentry_common_init(struct wim_dentry *dentry)
1007 {
1008         memset(dentry, 0, sizeof(struct wim_dentry));
1009 }
1010
1011 struct wim_inode *
1012 new_timeless_inode(void)
1013 {
1014         struct wim_inode *inode = CALLOC(1, sizeof(struct wim_inode));
1015         if (inode) {
1016                 inode->i_security_id = -1;
1017                 inode->i_nlink = 1;
1018                 inode->i_next_stream_id = 1;
1019                 inode->i_not_rpfixed = 1;
1020                 inode->i_canonical_streams = 1;
1021                 INIT_LIST_HEAD(&inode->i_list);
1022                 INIT_LIST_HEAD(&inode->i_dentry);
1023         }
1024         return inode;
1025 }
1026
1027 static struct wim_inode *
1028 new_inode(void)
1029 {
1030         struct wim_inode *inode = new_timeless_inode();
1031         if (inode) {
1032                 u64 now = get_wim_timestamp();
1033                 inode->i_creation_time = now;
1034                 inode->i_last_access_time = now;
1035                 inode->i_last_write_time = now;
1036         }
1037         return inode;
1038 }
1039
1040 /* Creates an unlinked directory entry. */
1041 int
1042 new_dentry(const tchar *name, struct wim_dentry **dentry_ret)
1043 {
1044         struct wim_dentry *dentry;
1045         int ret;
1046
1047         dentry = MALLOC(sizeof(struct wim_dentry));
1048         if (dentry == NULL)
1049                 return WIMLIB_ERR_NOMEM;
1050
1051         dentry_common_init(dentry);
1052         ret = set_dentry_name(dentry, name);
1053         if (ret == 0) {
1054                 dentry->parent = dentry;
1055                 *dentry_ret = dentry;
1056         } else {
1057                 FREE(dentry);
1058                 ERROR("Failed to set name on new dentry with name \"%"TS"\"",
1059                       name);
1060         }
1061         return ret;
1062 }
1063
1064
1065 static int
1066 _new_dentry_with_inode(const tchar *name, struct wim_dentry **dentry_ret,
1067                         bool timeless)
1068 {
1069         struct wim_dentry *dentry;
1070         int ret;
1071
1072         ret = new_dentry(name, &dentry);
1073         if (ret)
1074                 return ret;
1075
1076         if (timeless)
1077                 dentry->d_inode = new_timeless_inode();
1078         else
1079                 dentry->d_inode = new_inode();
1080         if (dentry->d_inode == NULL) {
1081                 free_dentry(dentry);
1082                 return WIMLIB_ERR_NOMEM;
1083         }
1084
1085         inode_add_dentry(dentry, dentry->d_inode);
1086         *dentry_ret = dentry;
1087         return 0;
1088 }
1089
1090 int
1091 new_dentry_with_timeless_inode(const tchar *name, struct wim_dentry **dentry_ret)
1092 {
1093         return _new_dentry_with_inode(name, dentry_ret, true);
1094 }
1095
1096 int
1097 new_dentry_with_inode(const tchar *name, struct wim_dentry **dentry_ret)
1098 {
1099         return _new_dentry_with_inode(name, dentry_ret, false);
1100 }
1101
1102 int
1103 new_filler_directory(const tchar *name, struct wim_dentry **dentry_ret)
1104 {
1105         int ret;
1106         struct wim_dentry *dentry;
1107
1108         DEBUG("Creating filler directory \"%"TS"\"", name);
1109         ret = new_dentry_with_inode(name, &dentry);
1110         if (ret)
1111                 return ret;
1112         /* Leave the inode number as 0; this is allowed for non
1113          * hard-linked files. */
1114         dentry->d_inode->i_resolved = 1;
1115         dentry->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
1116         *dentry_ret = dentry;
1117         return 0;
1118 }
1119
1120 static int
1121 dentry_clear_inode_visited(struct wim_dentry *dentry, void *_ignore)
1122 {
1123         dentry->d_inode->i_visited = 0;
1124         return 0;
1125 }
1126
1127 void
1128 dentry_tree_clear_inode_visited(struct wim_dentry *root)
1129 {
1130         for_dentry_in_tree(root, dentry_clear_inode_visited, NULL);
1131 }
1132
1133 static int
1134 init_ads_entry(struct wim_ads_entry *ads_entry, const void *name,
1135                size_t name_nbytes, bool is_utf16le)
1136 {
1137         int ret = 0;
1138         memset(ads_entry, 0, sizeof(*ads_entry));
1139
1140         if (is_utf16le) {
1141                 utf16lechar *p = MALLOC(name_nbytes + sizeof(utf16lechar));
1142                 if (p == NULL)
1143                         return WIMLIB_ERR_NOMEM;
1144                 memcpy(p, name, name_nbytes);
1145                 p[name_nbytes / 2] = cpu_to_le16(0);
1146                 ads_entry->stream_name = p;
1147                 ads_entry->stream_name_nbytes = name_nbytes;
1148         } else {
1149                 if (name && *(const tchar*)name != T('\0')) {
1150                         ret = get_utf16le_name(name, &ads_entry->stream_name,
1151                                                &ads_entry->stream_name_nbytes);
1152                 }
1153         }
1154         return ret;
1155 }
1156
1157 static void
1158 destroy_ads_entry(struct wim_ads_entry *ads_entry)
1159 {
1160         FREE(ads_entry->stream_name);
1161 }
1162
1163 /* Frees an inode. */
1164 void
1165 free_inode(struct wim_inode *inode)
1166 {
1167         if (inode) {
1168                 if (inode->i_ads_entries) {
1169                         for (u16 i = 0; i < inode->i_num_ads; i++)
1170                                 destroy_ads_entry(&inode->i_ads_entries[i]);
1171                         FREE(inode->i_ads_entries);
1172                 }
1173                 /* HACK: This may instead delete the inode from i_list, but the
1174                  * hlist_del() behaves the same as list_del(). */
1175                 if (!hlist_unhashed(&inode->i_hlist))
1176                         hlist_del(&inode->i_hlist);
1177                 FREE(inode);
1178         }
1179 }
1180
1181 /* Decrements link count on an inode and frees it if the link count reaches 0.
1182  * */
1183 static void
1184 put_inode(struct wim_inode *inode)
1185 {
1186         wimlib_assert(inode->i_nlink != 0);
1187         if (--inode->i_nlink == 0) {
1188         #ifdef WITH_FUSE
1189                 if (inode->i_num_opened_fds == 0)
1190         #endif
1191                 {
1192                         free_inode(inode);
1193                 }
1194         }
1195 }
1196
1197 /* Frees a WIM dentry.
1198  *
1199  * The corresponding inode (if any) is freed only if its link count is
1200  * decremented to 0.
1201  */
1202 void
1203 free_dentry(struct wim_dentry *dentry)
1204 {
1205         if (dentry) {
1206                 FREE(dentry->file_name);
1207                 FREE(dentry->short_name);
1208                 FREE(dentry->_full_path);
1209                 if (dentry->d_inode)
1210                         put_inode(dentry->d_inode);
1211                 FREE(dentry);
1212         }
1213 }
1214
1215 /* This function is passed as an argument to for_dentry_in_tree_depth() in order
1216  * to free a directory tree. */
1217 static int
1218 do_free_dentry(struct wim_dentry *dentry, void *_lookup_table)
1219 {
1220         struct wim_lookup_table *lookup_table = _lookup_table;
1221
1222         if (lookup_table) {
1223                 struct wim_inode *inode = dentry->d_inode;
1224                 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
1225                         struct wim_lookup_table_entry *lte;
1226
1227                         lte = inode_stream_lte(inode, i, lookup_table);
1228                         if (lte)
1229                                 lte_decrement_refcnt(lte, lookup_table);
1230                 }
1231         }
1232         free_dentry(dentry);
1233         return 0;
1234 }
1235
1236 /*
1237  * Unlinks and frees a dentry tree.
1238  *
1239  * @root:
1240  *      The root of the tree.
1241  *
1242  * @lookup_table:
1243  *      The lookup table for dentries.  If non-NULL, the reference counts in the
1244  *      lookup table for the lookup table entries corresponding to the dentries
1245  *      will be decremented.
1246  */
1247 void
1248 free_dentry_tree(struct wim_dentry *root, struct wim_lookup_table *lookup_table)
1249 {
1250         for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
1251 }
1252
1253 #ifdef __WIN32__
1254
1255 /* Insert a dentry into the case insensitive index for a directory.
1256  *
1257  * This is a red-black tree, but when multiple dentries share the same
1258  * case-insensitive name, only one is inserted into the tree itself; the rest
1259  * are connected in a list.
1260  */
1261 static struct wim_dentry *
1262 dentry_add_child_case_insensitive(struct wim_dentry *parent,
1263                                   struct wim_dentry *child)
1264 {
1265         struct rb_root *root;
1266         struct rb_node **new;
1267         struct rb_node *rb_parent;
1268
1269         root = &parent->d_inode->i_children_case_insensitive;
1270         new = &root->rb_node;
1271         rb_parent = NULL;
1272         while (*new) {
1273                 struct wim_dentry *this = container_of(*new, struct wim_dentry,
1274                                                        rb_node_case_insensitive);
1275                 int result = dentry_compare_names_case_insensitive(child, this);
1276
1277                 rb_parent = *new;
1278
1279                 if (result < 0)
1280                         new = &((*new)->rb_left);
1281                 else if (result > 0)
1282                         new = &((*new)->rb_right);
1283                 else
1284                         return this;
1285         }
1286         rb_link_node(&child->rb_node_case_insensitive, rb_parent, new);
1287         rb_insert_color(&child->rb_node_case_insensitive, root);
1288         return NULL;
1289 }
1290 #endif
1291
1292 /*
1293  * Links a dentry into the directory tree.
1294  *
1295  * @parent: The dentry that will be the parent of @child.
1296  * @child: The dentry to link.
1297  *
1298  * Returns NULL if successful.  If @parent already contains a dentry with the
1299  * same case-sensitive name as @child, the pointer to this duplicate dentry is
1300  * returned.
1301  */
1302 struct wim_dentry *
1303 dentry_add_child(struct wim_dentry * restrict parent,
1304                  struct wim_dentry * restrict child)
1305 {
1306         struct rb_root *root;
1307         struct rb_node **new;
1308         struct rb_node *rb_parent;
1309
1310         wimlib_assert(dentry_is_directory(parent));
1311         wimlib_assert(parent != child);
1312
1313         /* Case sensitive child dentry index */
1314         root = &parent->d_inode->i_children;
1315         new = &root->rb_node;
1316         rb_parent = NULL;
1317         while (*new) {
1318                 struct wim_dentry *this = rbnode_dentry(*new);
1319                 int result = dentry_compare_names_case_sensitive(child, this);
1320
1321                 rb_parent = *new;
1322
1323                 if (result < 0)
1324                         new = &((*new)->rb_left);
1325                 else if (result > 0)
1326                         new = &((*new)->rb_right);
1327                 else
1328                         return this;
1329         }
1330         child->parent = parent;
1331         rb_link_node(&child->rb_node, rb_parent, new);
1332         rb_insert_color(&child->rb_node, root);
1333
1334 #ifdef __WIN32__
1335         {
1336                 struct wim_dentry *existing;
1337                 existing = dentry_add_child_case_insensitive(parent, child);
1338                 if (existing) {
1339                         list_add(&child->case_insensitive_conflict_list,
1340                                  &existing->case_insensitive_conflict_list);
1341                         child->rb_node_case_insensitive.__rb_parent_color = 0;
1342                 } else {
1343                         INIT_LIST_HEAD(&child->case_insensitive_conflict_list);
1344                 }
1345         }
1346 #endif
1347         return NULL;
1348 }
1349
1350 /* Unlink a WIM dentry from the directory entry tree. */
1351 void
1352 unlink_dentry(struct wim_dentry *dentry)
1353 {
1354         struct wim_dentry *parent = dentry->parent;
1355
1356         if (parent == dentry)
1357                 return;
1358         rb_erase(&dentry->rb_node, &parent->d_inode->i_children);
1359 #ifdef __WIN32__
1360         if (dentry->rb_node_case_insensitive.__rb_parent_color) {
1361                 /* This dentry was in the case-insensitive red-black tree. */
1362                 rb_erase(&dentry->rb_node_case_insensitive,
1363                          &parent->d_inode->i_children_case_insensitive);
1364                 if (!list_empty(&dentry->case_insensitive_conflict_list)) {
1365                         /* Make a different case-insensitively-the-same dentry
1366                          * be the "representative" in the red-black tree. */
1367                         struct list_head *next;
1368                         struct wim_dentry *other;
1369                         struct wim_dentry *existing;
1370
1371                         next = dentry->case_insensitive_conflict_list.next;
1372                         other = list_entry(next, struct wim_dentry, case_insensitive_conflict_list);
1373                         existing = dentry_add_child_case_insensitive(parent, other);
1374                         wimlib_assert(existing == NULL);
1375                 }
1376         }
1377         list_del(&dentry->case_insensitive_conflict_list);
1378 #endif
1379 }
1380
1381 /*
1382  * Returns the alternate data stream entry belonging to @inode that has the
1383  * stream name @stream_name, or NULL if the inode has no alternate data stream
1384  * with that name.
1385  *
1386  * If @p stream_name is the empty string, NULL is returned --- that is, this
1387  * function will not return "unnamed" alternate data stream entries.
1388  */
1389 struct wim_ads_entry *
1390 inode_get_ads_entry(struct wim_inode *inode, const tchar *stream_name,
1391                     u16 *idx_ret)
1392 {
1393         if (inode->i_num_ads == 0) {
1394                 return NULL;
1395         } else {
1396                 size_t stream_name_utf16le_nbytes;
1397                 u16 i;
1398                 struct wim_ads_entry *result;
1399
1400                 if (stream_name[0] == T('\0'))
1401                         return NULL;
1402
1403         #if TCHAR_IS_UTF16LE
1404                 const utf16lechar *stream_name_utf16le;
1405
1406                 stream_name_utf16le = stream_name;
1407                 stream_name_utf16le_nbytes = tstrlen(stream_name) * sizeof(tchar);
1408         #else
1409                 utf16lechar *stream_name_utf16le;
1410
1411                 {
1412                         int ret = tstr_to_utf16le(stream_name,
1413                                                   tstrlen(stream_name) *
1414                                                       sizeof(tchar),
1415                                                   &stream_name_utf16le,
1416                                                   &stream_name_utf16le_nbytes);
1417                         if (ret)
1418                                 return NULL;
1419                 }
1420         #endif
1421                 i = 0;
1422                 result = NULL;
1423                 do {
1424                         if (ads_entry_has_name(&inode->i_ads_entries[i],
1425                                                stream_name_utf16le,
1426                                                stream_name_utf16le_nbytes))
1427                         {
1428                                 if (idx_ret)
1429                                         *idx_ret = i;
1430                                 result = &inode->i_ads_entries[i];
1431                                 break;
1432                         }
1433                 } while (++i != inode->i_num_ads);
1434         #if !TCHAR_IS_UTF16LE
1435                 FREE(stream_name_utf16le);
1436         #endif
1437                 return result;
1438         }
1439 }
1440
1441 static struct wim_ads_entry *
1442 do_inode_add_ads(struct wim_inode *inode, const void *stream_name,
1443                  size_t stream_name_nbytes, bool is_utf16le)
1444 {
1445         u16 num_ads;
1446         struct wim_ads_entry *ads_entries;
1447         struct wim_ads_entry *new_entry;
1448
1449         wimlib_assert(stream_name_nbytes != 0);
1450
1451         if (inode->i_num_ads >= 0xfffe) {
1452                 ERROR("Too many alternate data streams in one inode!");
1453                 return NULL;
1454         }
1455         num_ads = inode->i_num_ads + 1;
1456         ads_entries = REALLOC(inode->i_ads_entries,
1457                               num_ads * sizeof(inode->i_ads_entries[0]));
1458         if (ads_entries == NULL) {
1459                 ERROR("Failed to allocate memory for new alternate data stream");
1460                 return NULL;
1461         }
1462         inode->i_ads_entries = ads_entries;
1463
1464         new_entry = &inode->i_ads_entries[num_ads - 1];
1465         if (init_ads_entry(new_entry, stream_name, stream_name_nbytes, is_utf16le))
1466                 return NULL;
1467         new_entry->stream_id = inode->i_next_stream_id++;
1468         inode->i_num_ads = num_ads;
1469         return new_entry;
1470 }
1471
1472 struct wim_ads_entry *
1473 inode_add_ads_utf16le(struct wim_inode *inode,
1474                       const utf16lechar *stream_name,
1475                       size_t stream_name_nbytes)
1476 {
1477         DEBUG("Add alternate data stream \"%"WS"\"", stream_name);
1478         return do_inode_add_ads(inode, stream_name, stream_name_nbytes, true);
1479 }
1480
1481 /*
1482  * Add an alternate stream entry to a WIM inode.  On success, returns a pointer
1483  * to the new entry; on failure, returns NULL.
1484  *
1485  * @stream_name must be a nonempty string.
1486  */
1487 struct wim_ads_entry *
1488 inode_add_ads(struct wim_inode *inode, const tchar *stream_name)
1489 {
1490         DEBUG("Add alternate data stream \"%"TS"\"", stream_name);
1491         return do_inode_add_ads(inode, stream_name,
1492                                 tstrlen(stream_name) * sizeof(tchar),
1493                                 TCHAR_IS_UTF16LE);
1494 }
1495
1496 static struct wim_lookup_table_entry *
1497 add_stream_from_data_buffer(const void *buffer, size_t size,
1498                             struct wim_lookup_table *lookup_table)
1499 {
1500         u8 hash[SHA1_HASH_SIZE];
1501         struct wim_lookup_table_entry *lte, *existing_lte;
1502
1503         sha1_buffer(buffer, size, hash);
1504         existing_lte = lookup_resource(lookup_table, hash);
1505         if (existing_lte) {
1506                 wimlib_assert(existing_lte->size == size);
1507                 lte = existing_lte;
1508                 lte->refcnt++;
1509         } else {
1510                 void *buffer_copy;
1511                 lte = new_lookup_table_entry();
1512                 if (lte == NULL)
1513                         return NULL;
1514                 buffer_copy = memdup(buffer, size);
1515                 if (buffer_copy == NULL) {
1516                         free_lookup_table_entry(lte);
1517                         return NULL;
1518                 }
1519                 lte->resource_location  = RESOURCE_IN_ATTACHED_BUFFER;
1520                 lte->attached_buffer    = buffer_copy;
1521                 lte->size               = size;
1522                 copy_hash(lte->hash, hash);
1523                 lookup_table_insert(lookup_table, lte);
1524         }
1525         return lte;
1526 }
1527
1528 int
1529 inode_add_ads_with_data(struct wim_inode *inode, const tchar *name,
1530                         const void *value, size_t size,
1531                         struct wim_lookup_table *lookup_table)
1532 {
1533         struct wim_ads_entry *new_ads_entry;
1534
1535         wimlib_assert(inode->i_resolved);
1536
1537         new_ads_entry = inode_add_ads(inode, name);
1538         if (new_ads_entry == NULL)
1539                 return WIMLIB_ERR_NOMEM;
1540
1541         new_ads_entry->lte = add_stream_from_data_buffer(value, size,
1542                                                          lookup_table);
1543         if (new_ads_entry->lte == NULL) {
1544                 inode_remove_ads(inode, new_ads_entry - inode->i_ads_entries,
1545                                  lookup_table);
1546                 return WIMLIB_ERR_NOMEM;
1547         }
1548         return 0;
1549 }
1550
1551 bool
1552 inode_has_named_stream(const struct wim_inode *inode)
1553 {
1554         for (u16 i = 0; i < inode->i_num_ads; i++)
1555                 if (ads_entry_is_named_stream(&inode->i_ads_entries[i]))
1556                         return true;
1557         return false;
1558 }
1559
1560 /* Set the unnamed stream of a WIM inode, given a data buffer containing the
1561  * stream contents. */
1562 int
1563 inode_set_unnamed_stream(struct wim_inode *inode, const void *data, size_t len,
1564                          struct wim_lookup_table *lookup_table)
1565 {
1566         inode->i_lte = add_stream_from_data_buffer(data, len, lookup_table);
1567         if (inode->i_lte == NULL)
1568                 return WIMLIB_ERR_NOMEM;
1569         inode->i_resolved = 1;
1570         return 0;
1571 }
1572
1573 /* Remove an alternate data stream from a WIM inode  */
1574 void
1575 inode_remove_ads(struct wim_inode *inode, u16 idx,
1576                  struct wim_lookup_table *lookup_table)
1577 {
1578         struct wim_ads_entry *ads_entry;
1579         struct wim_lookup_table_entry *lte;
1580
1581         wimlib_assert(idx < inode->i_num_ads);
1582         wimlib_assert(inode->i_resolved);
1583
1584         ads_entry = &inode->i_ads_entries[idx];
1585
1586         DEBUG("Remove alternate data stream \"%"WS"\"", ads_entry->stream_name);
1587
1588         lte = ads_entry->lte;
1589         if (lte)
1590                 lte_decrement_refcnt(lte, lookup_table);
1591
1592         destroy_ads_entry(ads_entry);
1593
1594         memmove(&inode->i_ads_entries[idx],
1595                 &inode->i_ads_entries[idx + 1],
1596                 (inode->i_num_ads - idx - 1) * sizeof(inode->i_ads_entries[0]));
1597         inode->i_num_ads--;
1598 }
1599
1600 bool
1601 inode_has_unix_data(const struct wim_inode *inode)
1602 {
1603         for (u16 i = 0; i < inode->i_num_ads; i++)
1604                 if (ads_entry_is_unix_data(&inode->i_ads_entries[i]))
1605                         return true;
1606         return false;
1607 }
1608
1609 #ifndef __WIN32__
1610 int
1611 inode_get_unix_data(const struct wim_inode *inode,
1612                     struct wimlib_unix_data *unix_data,
1613                     u16 *stream_idx_ret)
1614 {
1615         const struct wim_ads_entry *ads_entry;
1616         const struct wim_lookup_table_entry *lte;
1617         size_t size;
1618         int ret;
1619
1620         wimlib_assert(inode->i_resolved);
1621
1622         ads_entry = inode_get_ads_entry((struct wim_inode*)inode,
1623                                         WIMLIB_UNIX_DATA_TAG, NULL);
1624         if (ads_entry == NULL)
1625                 return NO_UNIX_DATA;
1626
1627         if (stream_idx_ret)
1628                 *stream_idx_ret = ads_entry - inode->i_ads_entries;
1629
1630         lte = ads_entry->lte;
1631         if (lte == NULL)
1632                 return NO_UNIX_DATA;
1633
1634         size = lte->size;
1635         if (size != sizeof(struct wimlib_unix_data))
1636                 return BAD_UNIX_DATA;
1637
1638         ret = read_full_stream_into_buf(lte, unix_data);
1639         if (ret)
1640                 return ret;
1641
1642         if (unix_data->version != 0)
1643                 return BAD_UNIX_DATA;
1644         return 0;
1645 }
1646
1647 int
1648 inode_set_unix_data(struct wim_inode *inode, uid_t uid, gid_t gid, mode_t mode,
1649                     struct wim_lookup_table *lookup_table, int which)
1650 {
1651         struct wimlib_unix_data unix_data;
1652         int ret;
1653         bool have_good_unix_data = false;
1654         bool have_unix_data = false;
1655         u16 stream_idx;
1656
1657         if (!(which & UNIX_DATA_CREATE)) {
1658                 ret = inode_get_unix_data(inode, &unix_data, &stream_idx);
1659                 if (ret == 0 || ret == BAD_UNIX_DATA || ret > 0)
1660                         have_unix_data = true;
1661                 if (ret == 0)
1662                         have_good_unix_data = true;
1663         }
1664         unix_data.version = 0;
1665         if (which & UNIX_DATA_UID || !have_good_unix_data)
1666                 unix_data.uid = uid;
1667         if (which & UNIX_DATA_GID || !have_good_unix_data)
1668                 unix_data.gid = gid;
1669         if (which & UNIX_DATA_MODE || !have_good_unix_data)
1670                 unix_data.mode = mode;
1671         ret = inode_add_ads_with_data(inode, WIMLIB_UNIX_DATA_TAG,
1672                                       &unix_data,
1673                                       sizeof(struct wimlib_unix_data),
1674                                       lookup_table);
1675         if (ret == 0 && have_unix_data)
1676                 inode_remove_ads(inode, stream_idx, lookup_table);
1677         return ret;
1678 }
1679 #endif /* !__WIN32__ */
1680
1681 /*
1682  * Reads the alternate data stream entries of a WIM dentry.
1683  *
1684  * @p:
1685  *      Pointer to buffer that starts with the first alternate stream entry.
1686  *
1687  * @inode:
1688  *      Inode to load the alternate data streams into.  @inode->i_num_ads must
1689  *      have been set to the number of alternate data streams that are expected.
1690  *
1691  * @remaining_size:
1692  *      Number of bytes of data remaining in the buffer pointed to by @p.
1693  *
1694  * On success, inode->i_ads_entries is set to an array of `struct
1695  * wim_ads_entry's of length inode->i_num_ads.  On failure, @inode is not
1696  * modified.
1697  *
1698  * Return values:
1699  *      WIMLIB_ERR_SUCCESS (0)
1700  *      WIMLIB_ERR_INVALID_METADATA_RESOURCE
1701  *      WIMLIB_ERR_NOMEM
1702  */
1703 static int
1704 read_ads_entries(const u8 * restrict p, struct wim_inode * restrict inode,
1705                  size_t nbytes_remaining)
1706 {
1707         u16 num_ads;
1708         struct wim_ads_entry *ads_entries;
1709         int ret;
1710
1711         BUILD_BUG_ON(sizeof(struct wim_ads_entry_on_disk) != WIM_ADS_ENTRY_DISK_SIZE);
1712
1713         /* Allocate an array for our in-memory representation of the alternate
1714          * data stream entries. */
1715         num_ads = inode->i_num_ads;
1716         ads_entries = CALLOC(num_ads, sizeof(inode->i_ads_entries[0]));
1717         if (ads_entries == NULL)
1718                 goto out_of_memory;
1719
1720         /* Read the entries into our newly allocated buffer. */
1721         for (u16 i = 0; i < num_ads; i++) {
1722                 u64 length;
1723                 struct wim_ads_entry *cur_entry;
1724                 const struct wim_ads_entry_on_disk *disk_entry =
1725                         (const struct wim_ads_entry_on_disk*)p;
1726
1727                 cur_entry = &ads_entries[i];
1728                 ads_entries[i].stream_id = i + 1;
1729
1730                 /* Do we have at least the size of the fixed-length data we know
1731                  * need? */
1732                 if (nbytes_remaining < sizeof(struct wim_ads_entry_on_disk))
1733                         goto out_invalid;
1734
1735                 /* Read the length field */
1736                 length = le64_to_cpu(disk_entry->length);
1737
1738                 /* Make sure the length field is neither so small it doesn't
1739                  * include all the fixed-length data nor so large it overflows
1740                  * the metadata resource buffer. */
1741                 if (length < sizeof(struct wim_ads_entry_on_disk) ||
1742                     length > nbytes_remaining)
1743                         goto out_invalid;
1744
1745                 /* Read the rest of the fixed-length data. */
1746
1747                 cur_entry->reserved = le64_to_cpu(disk_entry->reserved);
1748                 copy_hash(cur_entry->hash, disk_entry->hash);
1749                 cur_entry->stream_name_nbytes = le16_to_cpu(disk_entry->stream_name_nbytes);
1750
1751                 /* If stream_name_nbytes != 0, this is a named stream.
1752                  * Otherwise this is an unnamed stream, or in some cases (bugs
1753                  * in Microsoft's software I guess) a meaningless entry
1754                  * distinguished from the real unnamed stream entry, if any, by
1755                  * the fact that the real unnamed stream entry has a nonzero
1756                  * hash field. */
1757                 if (cur_entry->stream_name_nbytes) {
1758                         /* The name is encoded in UTF16-LE, which uses 2-byte
1759                          * coding units, so the length of the name had better be
1760                          * an even number of bytes... */
1761                         if (cur_entry->stream_name_nbytes & 1)
1762                                 goto out_invalid;
1763
1764                         /* Add the length of the stream name to get the length
1765                          * we actually need to read.  Make sure this isn't more
1766                          * than the specified length of the entry. */
1767                         if (sizeof(struct wim_ads_entry_on_disk) +
1768                             cur_entry->stream_name_nbytes > length)
1769                                 goto out_invalid;
1770
1771                         cur_entry->stream_name = MALLOC(cur_entry->stream_name_nbytes + 2);
1772                         if (cur_entry->stream_name == NULL)
1773                                 goto out_of_memory;
1774
1775                         memcpy(cur_entry->stream_name,
1776                                disk_entry->stream_name,
1777                                cur_entry->stream_name_nbytes);
1778                         cur_entry->stream_name[cur_entry->stream_name_nbytes / 2] = cpu_to_le16(0);
1779                 } else {
1780                         /* Mark inode as having weird stream entries.  */
1781                         inode->i_canonical_streams = 0;
1782                 }
1783
1784                 /* It's expected that the size of every ADS entry is a multiple
1785                  * of 8.  However, to be safe, I'm allowing the possibility of
1786                  * an ADS entry at the very end of the metadata resource ending
1787                  * un-aligned.  So although we still need to increment the input
1788                  * pointer by @length to reach the next ADS entry, it's possible
1789                  * that less than @length is actually remaining in the metadata
1790                  * resource. We should set the remaining bytes to 0 if this
1791                  * happens. */
1792                 length = (length + 7) & ~(u64)7;
1793                 p += length;
1794                 if (nbytes_remaining < length)
1795                         nbytes_remaining = 0;
1796                 else
1797                         nbytes_remaining -= length;
1798         }
1799         inode->i_ads_entries = ads_entries;
1800         inode->i_next_stream_id = inode->i_num_ads + 1;
1801         ret = 0;
1802         goto out;
1803 out_of_memory:
1804         ret = WIMLIB_ERR_NOMEM;
1805         goto out_free_ads_entries;
1806 out_invalid:
1807         ERROR("An alternate data stream entry is invalid");
1808         ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1809 out_free_ads_entries:
1810         if (ads_entries) {
1811                 for (u16 i = 0; i < num_ads; i++)
1812                         destroy_ads_entry(&ads_entries[i]);
1813                 FREE(ads_entries);
1814         }
1815 out:
1816         return ret;
1817 }
1818
1819 /*
1820  * Reads a WIM directory entry, including all alternate data stream entries that
1821  * follow it, from the WIM image's metadata resource.
1822  *
1823  * @metadata_resource:
1824  *              Pointer to the metadata resource buffer.
1825  *
1826  * @metadata_resource_len:
1827  *              Length of the metadata resource buffer, in bytes.
1828  *
1829  * @offset:     Offset of the dentry within the metadata resource.
1830  *
1831  * @dentry:     A `struct wim_dentry' that will be filled in by this function.
1832  *
1833  * Return 0 on success or nonzero on failure.  On failure, @dentry will have
1834  * been modified, but it will not be left with pointers to any allocated
1835  * buffers.  On success, the dentry->length field must be examined.  If zero,
1836  * this was a special "end of directory" dentry and not a real dentry.  If
1837  * nonzero, this was a real dentry.
1838  *
1839  * Return values:
1840  *      WIMLIB_ERR_SUCCESS (0)
1841  *      WIMLIB_ERR_INVALID_METADATA_RESOURCE
1842  *      WIMLIB_ERR_NOMEM
1843  */
1844 int
1845 read_dentry(const u8 * restrict metadata_resource, u64 metadata_resource_len,
1846             u64 offset, struct wim_dentry * restrict dentry)
1847 {
1848
1849         u64 calculated_size;
1850         utf16lechar *file_name;
1851         utf16lechar *short_name;
1852         u16 short_name_nbytes;
1853         u16 file_name_nbytes;
1854         int ret;
1855         struct wim_inode *inode;
1856         const u8 *p = &metadata_resource[offset];
1857         const struct wim_dentry_on_disk *disk_dentry =
1858                         (const struct wim_dentry_on_disk*)p;
1859
1860         BUILD_BUG_ON(sizeof(struct wim_dentry_on_disk) != WIM_DENTRY_DISK_SIZE);
1861
1862         if ((uintptr_t)p & 7)
1863                 WARNING("WIM dentry is not 8-byte aligned");
1864
1865         dentry_common_init(dentry);
1866
1867         /* Before reading the whole dentry, we need to read just the length.
1868          * This is because a dentry of length 8 (that is, just the length field)
1869          * terminates the list of sibling directory entries. */
1870         if (offset + sizeof(u64) > metadata_resource_len ||
1871             offset + sizeof(u64) < offset)
1872         {
1873                 ERROR("Directory entry starting at %"PRIu64" ends past the "
1874                       "end of the metadata resource (size %"PRIu64")",
1875                       offset, metadata_resource_len);
1876                 return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1877         }
1878         dentry->length = le64_to_cpu(disk_dentry->length);
1879
1880         /* A zero length field (really a length of 8, since that's how big the
1881          * directory entry is...) indicates that this is the end of directory
1882          * dentry.  We do not read it into memory as an actual dentry, so just
1883          * return successfully in this case. */
1884         if (dentry->length == 8)
1885                 dentry->length = 0;
1886         if (dentry->length == 0)
1887                 return 0;
1888
1889         /* Now that we have the actual length provided in the on-disk structure,
1890          * again make sure it doesn't overflow the metadata resource buffer. */
1891         if (offset + dentry->length > metadata_resource_len ||
1892             offset + dentry->length < offset)
1893         {
1894                 ERROR("Directory entry at offset %"PRIu64" and with size "
1895                       "%"PRIu64" ends past the end of the metadata resource "
1896                       "(size %"PRIu64")",
1897                       offset, dentry->length, metadata_resource_len);
1898                 return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1899         }
1900
1901         /* Make sure the dentry length is at least as large as the number of
1902          * fixed-length fields */
1903         if (dentry->length < sizeof(struct wim_dentry_on_disk)) {
1904                 ERROR("Directory entry has invalid length of %"PRIu64" bytes",
1905                       dentry->length);
1906                 return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1907         }
1908
1909         /* Allocate a `struct wim_inode' for this `struct wim_dentry'. */
1910         inode = new_timeless_inode();
1911         if (inode == NULL)
1912                 return WIMLIB_ERR_NOMEM;
1913
1914         /* Read more fields; some into the dentry, and some into the inode. */
1915
1916         inode->i_attributes = le32_to_cpu(disk_dentry->attributes);
1917         inode->i_security_id = le32_to_cpu(disk_dentry->security_id);
1918         dentry->subdir_offset = le64_to_cpu(disk_dentry->subdir_offset);
1919         dentry->d_unused_1 = le64_to_cpu(disk_dentry->unused_1);
1920         dentry->d_unused_2 = le64_to_cpu(disk_dentry->unused_2);
1921         inode->i_creation_time = le64_to_cpu(disk_dentry->creation_time);
1922         inode->i_last_access_time = le64_to_cpu(disk_dentry->last_access_time);
1923         inode->i_last_write_time = le64_to_cpu(disk_dentry->last_write_time);
1924         copy_hash(inode->i_hash, disk_dentry->unnamed_stream_hash);
1925
1926         /* I don't know what's going on here.  It seems like M$ screwed up the
1927          * reparse points, then put the fields in the same place and didn't
1928          * document it.  So we have some fields we read for reparse points, and
1929          * some fields in the same place for non-reparse-point.s */
1930         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1931                 inode->i_rp_unknown_1 = le32_to_cpu(disk_dentry->reparse.rp_unknown_1);
1932                 inode->i_reparse_tag = le32_to_cpu(disk_dentry->reparse.reparse_tag);
1933                 inode->i_rp_unknown_2 = le16_to_cpu(disk_dentry->reparse.rp_unknown_2);
1934                 inode->i_not_rpfixed = le16_to_cpu(disk_dentry->reparse.not_rpfixed);
1935                 /* Leave inode->i_ino at 0.  Note that this means the WIM file
1936                  * cannot archive hard-linked reparse points.  Such a thing
1937                  * doesn't really make sense anyway, although I believe it's
1938                  * theoretically possible to have them on NTFS. */
1939         } else {
1940                 inode->i_rp_unknown_1 = le32_to_cpu(disk_dentry->nonreparse.rp_unknown_1);
1941                 inode->i_ino = le64_to_cpu(disk_dentry->nonreparse.hard_link_group_id);
1942         }
1943
1944         inode->i_num_ads = le16_to_cpu(disk_dentry->num_alternate_data_streams);
1945
1946         short_name_nbytes = le16_to_cpu(disk_dentry->short_name_nbytes);
1947         file_name_nbytes = le16_to_cpu(disk_dentry->file_name_nbytes);
1948
1949         if ((short_name_nbytes & 1) | (file_name_nbytes & 1))
1950         {
1951                 ERROR("Dentry name is not valid UTF-16LE (odd number of bytes)!");
1952                 ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1953                 goto out_free_inode;
1954         }
1955
1956         /* We now know the length of the file name and short name.  Make sure
1957          * the length of the dentry is large enough to actually hold them.
1958          *
1959          * The calculated length here is unaligned to allow for the possibility
1960          * that the dentry->length names an unaligned length, although this
1961          * would be unexpected. */
1962         calculated_size = dentry_correct_length_unaligned(file_name_nbytes,
1963                                                           short_name_nbytes);
1964
1965         if (dentry->length < calculated_size) {
1966                 ERROR("Unexpected end of directory entry! (Expected "
1967                       "at least %"PRIu64" bytes, got %"PRIu64" bytes.)",
1968                       calculated_size, dentry->length);
1969                 ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
1970                 goto out_free_inode;
1971         }
1972
1973         p += sizeof(struct wim_dentry_on_disk);
1974
1975         /* Read the filename if present.  Note: if the filename is empty, there
1976          * is no null terminator following it. */
1977         if (file_name_nbytes) {
1978                 file_name = MALLOC(file_name_nbytes + 2);
1979                 if (file_name == NULL) {
1980                         ERROR("Failed to allocate %d bytes for dentry file name",
1981                               file_name_nbytes + 2);
1982                         ret = WIMLIB_ERR_NOMEM;
1983                         goto out_free_inode;
1984                 }
1985                 memcpy(file_name, p, file_name_nbytes);
1986                 p += file_name_nbytes + 2;
1987                 file_name[file_name_nbytes / 2] = cpu_to_le16(0);
1988         } else {
1989                 file_name = NULL;
1990         }
1991
1992
1993         /* Read the short filename if present.  Note: if there is no short
1994          * filename, there is no null terminator following it. */
1995         if (short_name_nbytes) {
1996                 short_name = MALLOC(short_name_nbytes + 2);
1997                 if (short_name == NULL) {
1998                         ERROR("Failed to allocate %d bytes for dentry short name",
1999                               short_name_nbytes + 2);
2000                         ret = WIMLIB_ERR_NOMEM;
2001                         goto out_free_file_name;
2002                 }
2003                 memcpy(short_name, p, short_name_nbytes);
2004                 p += short_name_nbytes + 2;
2005                 short_name[short_name_nbytes / 2] = cpu_to_le16(0);
2006         } else {
2007                 short_name = NULL;
2008         }
2009
2010         /* Align the dentry length */
2011         dentry->length = (dentry->length + 7) & ~7;
2012
2013         /*
2014          * Read the alternate data streams, if present.  dentry->num_ads tells
2015          * us how many they are, and they will directly follow the dentry
2016          * on-disk.
2017          *
2018          * Note that each alternate data stream entry begins on an 8-byte
2019          * aligned boundary, and the alternate data stream entries seem to NOT
2020          * be included in the dentry->length field for some reason.
2021          */
2022         if (inode->i_num_ads != 0) {
2023                 ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
2024                 if (offset + dentry->length > metadata_resource_len ||
2025                     (ret = read_ads_entries(&metadata_resource[offset + dentry->length],
2026                                             inode,
2027                                             metadata_resource_len - offset - dentry->length)))
2028                 {
2029                         ERROR("Failed to read alternate data stream "
2030                               "entries of WIM dentry \"%"WS"\"", file_name);
2031                         goto out_free_short_name;
2032                 }
2033         }
2034         /* We've read all the data for this dentry.  Set the names and their
2035          * lengths, and we've done. */
2036         dentry->d_inode           = inode;
2037         dentry->file_name         = file_name;
2038         dentry->short_name        = short_name;
2039         dentry->file_name_nbytes  = file_name_nbytes;
2040         dentry->short_name_nbytes = short_name_nbytes;
2041         ret = 0;
2042         goto out;
2043 out_free_short_name:
2044         FREE(short_name);
2045 out_free_file_name:
2046         FREE(file_name);
2047 out_free_inode:
2048         free_inode(inode);
2049 out:
2050         return ret;
2051 }
2052
2053 static const tchar *
2054 dentry_get_file_type_string(const struct wim_dentry *dentry)
2055 {
2056         const struct wim_inode *inode = dentry->d_inode;
2057         if (inode_is_directory(inode))
2058                 return T("directory");
2059         else if (inode_is_symlink(inode))
2060                 return T("symbolic link");
2061         else
2062                 return T("file");
2063 }
2064
2065 /* Reads the children of a dentry, and all their children, ..., etc. from the
2066  * metadata resource and into the dentry tree.
2067  *
2068  * @metadata_resource:
2069  *      An array that contains the uncompressed metadata resource for the WIM
2070  *      file.
2071  *
2072  * @metadata_resource_len:
2073  *      The length of the uncompressed metadata resource, in bytes.
2074  *
2075  * @dentry:
2076  *      A pointer to a `struct wim_dentry' that is the root of the directory
2077  *      tree and has already been read from the metadata resource.  It does not
2078  *      need to be the real root because this procedure is called recursively.
2079  *
2080  * Return values:
2081  *      WIMLIB_ERR_SUCCESS (0)
2082  *      WIMLIB_ERR_INVALID_METADATA_RESOURCE
2083  *      WIMLIB_ERR_NOMEM
2084  */
2085 int
2086 read_dentry_tree(const u8 * restrict metadata_resource,
2087                  u64 metadata_resource_len,
2088                  struct wim_dentry * restrict dentry)
2089 {
2090         u64 cur_offset = dentry->subdir_offset;
2091         struct wim_dentry *child;
2092         struct wim_dentry *duplicate;
2093         struct wim_dentry *parent;
2094         struct wim_dentry cur_child;
2095         int ret;
2096
2097         /*
2098          * If @dentry has no child dentries, nothing more needs to be done for
2099          * this branch.  This is the case for regular files, symbolic links, and
2100          * *possibly* empty directories (although an empty directory may also
2101          * have one child dentry that is the special end-of-directory dentry)
2102          */
2103         if (cur_offset == 0)
2104                 return 0;
2105
2106         /* Check for cyclic directory structure */
2107         for (parent = dentry->parent; !dentry_is_root(parent); parent = parent->parent)
2108         {
2109                 if (unlikely(parent->subdir_offset == cur_offset)) {
2110                         ERROR("Cyclic directory structure directed: children "
2111                               "of \"%"TS"\" coincide with children of \"%"TS"\"",
2112                               dentry_full_path(dentry),
2113                               dentry_full_path(parent));
2114                         return WIMLIB_ERR_INVALID_METADATA_RESOURCE;
2115                 }
2116         }
2117
2118         /* Find and read all the children of @dentry. */
2119         for (;;) {
2120
2121                 /* Read next child of @dentry into @cur_child. */
2122                 ret = read_dentry(metadata_resource, metadata_resource_len,
2123                                   cur_offset, &cur_child);
2124                 if (ret)
2125                         break;
2126
2127                 /* Check for end of directory. */
2128                 if (cur_child.length == 0)
2129                         break;
2130
2131                 /* Not end of directory.  Allocate this child permanently and
2132                  * link it to the parent and previous child. */
2133                 child = memdup(&cur_child, sizeof(struct wim_dentry));
2134                 if (child == NULL) {
2135                         ERROR("Failed to allocate new dentry!");
2136                         ret = WIMLIB_ERR_NOMEM;
2137                         break;
2138                 }
2139
2140                 /* Advance to the offset of the next child.  Note: We need to
2141                  * advance by the TOTAL length of the dentry, not by the length
2142                  * cur_child.length, which although it does take into account
2143                  * the padding, it DOES NOT take into account alternate stream
2144                  * entries. */
2145                 cur_offset += dentry_in_total_length(child);
2146
2147                 if (unlikely(!dentry_has_long_name(child))) {
2148                         WARNING("Ignoring unnamed dentry in "
2149                                 "directory \"%"TS"\"",
2150                                 dentry_full_path(dentry));
2151                         free_dentry(child);
2152                         continue;
2153                 }
2154
2155                 duplicate = dentry_add_child(dentry, child);
2156                 if (unlikely(duplicate)) {
2157                         const tchar *child_type, *duplicate_type;
2158                         child_type = dentry_get_file_type_string(child);
2159                         duplicate_type = dentry_get_file_type_string(duplicate);
2160                         WARNING("Ignoring duplicate %"TS" \"%"TS"\" "
2161                                 "(the WIM image already contains a %"TS" "
2162                                 "at that path with the exact same name)",
2163                                 child_type, dentry_full_path(duplicate),
2164                                 duplicate_type);
2165                         free_dentry(child);
2166                         continue;
2167                 }
2168
2169                 inode_add_dentry(child, child->d_inode);
2170                 /* If there are children of this child, call this
2171                  * procedure recursively. */
2172                 if (child->subdir_offset != 0) {
2173                         if (likely(dentry_is_directory(child))) {
2174                                 ret = read_dentry_tree(metadata_resource,
2175                                                        metadata_resource_len,
2176                                                        child);
2177                                 if (ret)
2178                                         break;
2179                         } else {
2180                                 WARNING("Ignoring children of non-directory \"%"TS"\"",
2181                                         dentry_full_path(child));
2182                         }
2183                 }
2184         }
2185         return ret;
2186 }
2187
2188 /*
2189  * Writes a WIM alternate data stream (ADS) entry to an output buffer.
2190  *
2191  * @ads_entry:  The ADS entry structure.
2192  * @hash:       The hash field to use (instead of the one in the ADS entry).
2193  * @p:          The memory location to write the data to.
2194  *
2195  * Returns a pointer to the byte after the last byte written.
2196  */
2197 static u8 *
2198 write_ads_entry(const struct wim_ads_entry *ads_entry,
2199                 const u8 *hash, u8 * restrict p)
2200 {
2201         struct wim_ads_entry_on_disk *disk_ads_entry =
2202                         (struct wim_ads_entry_on_disk*)p;
2203         u8 *orig_p = p;
2204
2205         disk_ads_entry->reserved = cpu_to_le64(ads_entry->reserved);
2206         copy_hash(disk_ads_entry->hash, hash);
2207         disk_ads_entry->stream_name_nbytes = cpu_to_le16(ads_entry->stream_name_nbytes);
2208         p += sizeof(struct wim_ads_entry_on_disk);
2209         if (ads_entry->stream_name_nbytes) {
2210                 p = mempcpy(p, ads_entry->stream_name,
2211                             ads_entry->stream_name_nbytes + 2);
2212         }
2213         /* Align to 8-byte boundary */
2214         while ((uintptr_t)p & 7)
2215                 *p++ = 0;
2216         disk_ads_entry->length = cpu_to_le64(p - orig_p);
2217         return p;
2218 }
2219
2220 /*
2221  * Writes a WIM dentry to an output buffer.
2222  *
2223  * @dentry:  The dentry structure.
2224  * @p:       The memory location to write the data to.
2225  *
2226  * Returns the pointer to the byte after the last byte we wrote as part of the
2227  * dentry, including any alternate data stream entries.
2228  */
2229 static u8 *
2230 write_dentry(const struct wim_dentry * restrict dentry, u8 * restrict p)
2231 {
2232         const struct wim_inode *inode;
2233         struct wim_dentry_on_disk *disk_dentry;
2234         const u8 *orig_p;
2235         const u8 *hash;
2236         bool use_dummy_stream;
2237         u16 num_ads;
2238
2239         wimlib_assert(((uintptr_t)p & 7) == 0); /* 8 byte aligned */
2240         orig_p = p;
2241
2242         inode = dentry->d_inode;
2243         use_dummy_stream = inode_needs_dummy_stream(inode);
2244         disk_dentry = (struct wim_dentry_on_disk*)p;
2245
2246         disk_dentry->attributes = cpu_to_le32(inode->i_attributes);
2247         disk_dentry->security_id = cpu_to_le32(inode->i_security_id);
2248         disk_dentry->subdir_offset = cpu_to_le64(dentry->subdir_offset);
2249         disk_dentry->unused_1 = cpu_to_le64(dentry->d_unused_1);
2250         disk_dentry->unused_2 = cpu_to_le64(dentry->d_unused_2);
2251         disk_dentry->creation_time = cpu_to_le64(inode->i_creation_time);
2252         disk_dentry->last_access_time = cpu_to_le64(inode->i_last_access_time);
2253         disk_dentry->last_write_time = cpu_to_le64(inode->i_last_write_time);
2254         if (use_dummy_stream)
2255                 hash = zero_hash;
2256         else
2257                 hash = inode_stream_hash(inode, 0);
2258         copy_hash(disk_dentry->unnamed_stream_hash, hash);
2259         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
2260                 disk_dentry->reparse.rp_unknown_1 = cpu_to_le32(inode->i_rp_unknown_1);
2261                 disk_dentry->reparse.reparse_tag = cpu_to_le32(inode->i_reparse_tag);
2262                 disk_dentry->reparse.rp_unknown_2 = cpu_to_le16(inode->i_rp_unknown_2);
2263                 disk_dentry->reparse.not_rpfixed = cpu_to_le16(inode->i_not_rpfixed);
2264         } else {
2265                 disk_dentry->nonreparse.rp_unknown_1 = cpu_to_le32(inode->i_rp_unknown_1);
2266                 disk_dentry->nonreparse.hard_link_group_id =
2267                         cpu_to_le64((inode->i_nlink == 1) ? 0 : inode->i_ino);
2268         }
2269         num_ads = inode->i_num_ads;
2270         if (use_dummy_stream)
2271                 num_ads++;
2272         disk_dentry->num_alternate_data_streams = cpu_to_le16(num_ads);
2273         disk_dentry->short_name_nbytes = cpu_to_le16(dentry->short_name_nbytes);
2274         disk_dentry->file_name_nbytes = cpu_to_le16(dentry->file_name_nbytes);
2275         p += sizeof(struct wim_dentry_on_disk);
2276
2277         wimlib_assert(dentry_is_root(dentry) != dentry_has_long_name(dentry));
2278
2279         if (dentry_has_long_name(dentry))
2280                 p = mempcpy(p, dentry->file_name, dentry->file_name_nbytes + 2);
2281
2282         if (dentry_has_short_name(dentry))
2283                 p = mempcpy(p, dentry->short_name, dentry->short_name_nbytes + 2);
2284
2285         /* Align to 8-byte boundary */
2286         while ((uintptr_t)p & 7)
2287                 *p++ = 0;
2288
2289         /* We calculate the correct length of the dentry ourselves because the
2290          * dentry->length field may been set to an unexpected value from when we
2291          * read the dentry in (for example, there may have been unknown data
2292          * appended to the end of the dentry...).  Furthermore, the dentry may
2293          * have been renamed, thus changing its needed length. */
2294         disk_dentry->length = cpu_to_le64(p - orig_p);
2295
2296         if (use_dummy_stream) {
2297                 hash = inode_unnamed_stream_hash(inode);
2298                 p = write_ads_entry(&(struct wim_ads_entry){}, hash, p);
2299         }
2300
2301         /* Write the alternate data streams entries, if any. */
2302         for (u16 i = 0; i < inode->i_num_ads; i++) {
2303                 hash = inode_stream_hash(inode, i + 1);
2304                 p = write_ads_entry(&inode->i_ads_entries[i], hash, p);
2305         }
2306
2307         return p;
2308 }
2309
2310 static int
2311 write_dentry_cb(struct wim_dentry *dentry, void *_p)
2312 {
2313         u8 **p = _p;
2314         *p = write_dentry(dentry, *p);
2315         return 0;
2316 }
2317
2318 static u8 *
2319 write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p);
2320
2321 static int
2322 write_dentry_tree_recursive_cb(struct wim_dentry *dentry, void *_p)
2323 {
2324         u8 **p = _p;
2325         *p = write_dentry_tree_recursive(dentry, *p);
2326         return 0;
2327 }
2328
2329 /* Recursive function that writes a dentry tree rooted at @parent, not including
2330  * @parent itself, which has already been written. */
2331 static u8 *
2332 write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p)
2333 {
2334         /* Nothing to do if this dentry has no children. */
2335         if (parent->subdir_offset == 0)
2336                 return p;
2337
2338         /* Write child dentries and end-of-directory entry.
2339          *
2340          * Note: we need to write all of this dentry's children before
2341          * recursively writing the directory trees rooted at each of the child
2342          * dentries, since the on-disk dentries for a dentry's children are
2343          * always located at consecutive positions in the metadata resource! */
2344         for_dentry_child(parent, write_dentry_cb, &p);
2345
2346         /* write end of directory entry */
2347         *(le64*)p = cpu_to_le64(0);
2348         p += 8;
2349
2350         /* Recurse on children. */
2351         for_dentry_child(parent, write_dentry_tree_recursive_cb, &p);
2352         return p;
2353 }
2354
2355 /* Writes a directory tree to the metadata resource.
2356  *
2357  * @root:       Root of the dentry tree.
2358  * @p:          Pointer to a buffer with enough space for the dentry tree.
2359  *
2360  * Returns pointer to the byte after the last byte we wrote.
2361  */
2362 u8 *
2363 write_dentry_tree(const struct wim_dentry * restrict root, u8 * restrict p)
2364 {
2365         DEBUG("Writing dentry tree.");
2366         wimlib_assert(dentry_is_root(root));
2367
2368         /* If we're the root dentry, we have no parent that already
2369          * wrote us, so we need to write ourselves. */
2370         p = write_dentry(root, p);
2371
2372         /* Write end of directory entry after the root dentry just to be safe;
2373          * however the root dentry obviously cannot have any siblings. */
2374         *(le64*)p = cpu_to_le64(0);
2375         p += 8;
2376
2377         /* Recursively write the rest of the dentry tree. */
2378         return write_dentry_tree_recursive(root, p);
2379 }
2380
2381
2382 static int
2383 init_wimlib_dentry(struct wimlib_dir_entry *wdentry,
2384                    struct wim_dentry *dentry,
2385                    const WIMStruct *wim,
2386                    int flags)
2387 {
2388         int ret;
2389         size_t dummy;
2390         const struct wim_inode *inode = dentry->d_inode;
2391         struct wim_lookup_table_entry *lte;
2392         const u8 *hash;
2393
2394 #if TCHAR_IS_UTF16LE
2395         wdentry->filename = dentry->file_name;
2396         wdentry->dos_name = dentry->short_name;
2397 #else
2398         if (dentry_has_long_name(dentry)) {
2399                 ret = utf16le_to_tstr(dentry->file_name,
2400                                       dentry->file_name_nbytes,
2401                                       (tchar**)&wdentry->filename,
2402                                       &dummy);
2403                 if (ret)
2404                         return ret;
2405         }
2406         if (dentry_has_short_name(dentry)) {
2407                 ret = utf16le_to_tstr(dentry->short_name,
2408                                       dentry->short_name_nbytes,
2409                                       (tchar**)&wdentry->dos_name,
2410                                       &dummy);
2411                 if (ret)
2412                         return ret;
2413         }
2414 #endif
2415         ret = calculate_dentry_full_path(dentry);
2416         if (ret)
2417                 return ret;
2418         wdentry->full_path = dentry->_full_path;
2419
2420         for (struct wim_dentry *d = dentry; !dentry_is_root(d); d = d->parent)
2421                 wdentry->depth++;
2422
2423         if (inode->i_security_id >= 0) {
2424                 const struct wim_security_data *sd = wim_const_security_data(wim);
2425                 wdentry->security_descriptor = sd->descriptors[inode->i_security_id];
2426                 wdentry->security_descriptor_size = sd->sizes[inode->i_security_id];
2427         }
2428         wdentry->reparse_tag = inode->i_reparse_tag;
2429         wdentry->num_links = inode->i_nlink;
2430         wdentry->attributes = inode->i_attributes;
2431         wdentry->hard_link_group_id = inode->i_ino;
2432         wdentry->creation_time = wim_timestamp_to_timespec(inode->i_creation_time);
2433         wdentry->last_write_time = wim_timestamp_to_timespec(inode->i_last_write_time);
2434         wdentry->last_access_time = wim_timestamp_to_timespec(inode->i_last_access_time);
2435
2436         lte = inode_unnamed_lte(inode, wim->lookup_table);
2437         if (lte) {
2438                 lte_to_wimlib_resource_entry(lte, &wdentry->streams[0].resource);
2439         } else if (!is_zero_hash(hash = inode_unnamed_stream_hash(inode))) {
2440                 if (flags & WIMLIB_ITERATE_DIR_TREE_FLAG_RESOURCES_NEEDED)
2441                         return resource_not_found_error(inode, hash);
2442                 copy_hash(wdentry->streams[0].resource.sha1_hash, hash);
2443                 wdentry->streams[0].resource.is_missing = 1;
2444         }
2445
2446         for (unsigned i = 0; i < inode->i_num_ads; i++) {
2447                 if (!ads_entry_is_named_stream(&inode->i_ads_entries[i]))
2448                         continue;
2449                 lte = inode_stream_lte(inode, i + 1, wim->lookup_table);
2450                 wdentry->num_named_streams++;
2451                 if (lte) {
2452                         lte_to_wimlib_resource_entry(lte, &wdentry->streams[
2453                                                                 wdentry->num_named_streams].resource);
2454                 } else if (!is_zero_hash(hash = inode_stream_hash(inode, i + 1))) {
2455                         if (flags & WIMLIB_ITERATE_DIR_TREE_FLAG_RESOURCES_NEEDED)
2456                                 return resource_not_found_error(inode, hash);
2457                         copy_hash(wdentry->streams[
2458                                   wdentry->num_named_streams].resource.sha1_hash, hash);
2459                         wdentry->streams[
2460                                 wdentry->num_named_streams].resource.is_missing = 1;
2461                 }
2462         #if TCHAR_IS_UTF16LE
2463                 wdentry->streams[wdentry->num_named_streams].stream_name =
2464                                 inode->i_ads_entries[i].stream_name;
2465         #else
2466                 size_t dummy;
2467
2468                 ret = utf16le_to_tstr(inode->i_ads_entries[i].stream_name,
2469                                       inode->i_ads_entries[i].stream_name_nbytes,
2470                                       (tchar**)&wdentry->streams[
2471                                                 wdentry->num_named_streams].stream_name,
2472                                       &dummy);
2473                 if (ret)
2474                         return ret;
2475         #endif
2476         }
2477         return 0;
2478 }
2479
2480 static void
2481 free_wimlib_dentry(struct wimlib_dir_entry *wdentry)
2482 {
2483 #if !TCHAR_IS_UTF16LE
2484         FREE((tchar*)wdentry->filename);
2485         FREE((tchar*)wdentry->dos_name);
2486         for (unsigned i = 1; i <= wdentry->num_named_streams; i++)
2487                 FREE((tchar*)wdentry->streams[i].stream_name);
2488 #endif
2489         FREE(wdentry);
2490 }
2491
2492 struct iterate_dir_tree_ctx {
2493         WIMStruct *wim;
2494         int flags;
2495         wimlib_iterate_dir_tree_callback_t cb;
2496         void *user_ctx;
2497 };
2498
2499 static int
2500 do_iterate_dir_tree(WIMStruct *wim,
2501                     struct wim_dentry *dentry, int flags,
2502                     wimlib_iterate_dir_tree_callback_t cb,
2503                     void *user_ctx);
2504
2505 static int
2506 call_do_iterate_dir_tree(struct wim_dentry *dentry, void *_ctx)
2507 {
2508         struct iterate_dir_tree_ctx *ctx = _ctx;
2509         return do_iterate_dir_tree(ctx->wim, dentry, ctx->flags,
2510                                    ctx->cb, ctx->user_ctx);
2511 }
2512
2513 static int
2514 do_iterate_dir_tree(WIMStruct *wim,
2515                     struct wim_dentry *dentry, int flags,
2516                     wimlib_iterate_dir_tree_callback_t cb,
2517                     void *user_ctx)
2518 {
2519         struct wimlib_dir_entry *wdentry;
2520         int ret = WIMLIB_ERR_NOMEM;
2521
2522
2523         wdentry = CALLOC(1, sizeof(struct wimlib_dir_entry) +
2524                                   (1 + dentry->d_inode->i_num_ads) *
2525                                         sizeof(struct wimlib_stream_entry));
2526         if (wdentry == NULL)
2527                 goto out;
2528
2529         ret = init_wimlib_dentry(wdentry, dentry, wim, flags);
2530         if (ret)
2531                 goto out_free_wimlib_dentry;
2532
2533         if (!(flags & WIMLIB_ITERATE_DIR_TREE_FLAG_CHILDREN)) {
2534                 ret = (*cb)(wdentry, user_ctx);
2535                 if (ret)
2536                         goto out_free_wimlib_dentry;
2537         }
2538
2539         if (flags & (WIMLIB_ITERATE_DIR_TREE_FLAG_RECURSIVE |
2540                      WIMLIB_ITERATE_DIR_TREE_FLAG_CHILDREN))
2541         {
2542                 struct iterate_dir_tree_ctx ctx = {
2543                         .wim      = wim,
2544                         .flags    = flags &= ~WIMLIB_ITERATE_DIR_TREE_FLAG_CHILDREN,
2545                         .cb       = cb,
2546                         .user_ctx = user_ctx,
2547                 };
2548                 ret = for_dentry_child(dentry, call_do_iterate_dir_tree, &ctx);
2549         }
2550 out_free_wimlib_dentry:
2551         free_wimlib_dentry(wdentry);
2552 out:
2553         return ret;
2554 }
2555
2556 struct image_iterate_dir_tree_ctx {
2557         const tchar *path;
2558         int flags;
2559         wimlib_iterate_dir_tree_callback_t cb;
2560         void *user_ctx;
2561 };
2562
2563
2564 static int
2565 image_do_iterate_dir_tree(WIMStruct *wim)
2566 {
2567         struct image_iterate_dir_tree_ctx *ctx = wim->private;
2568         struct wim_dentry *dentry;
2569
2570         dentry = get_dentry(wim, ctx->path);
2571         if (dentry == NULL)
2572                 return WIMLIB_ERR_PATH_DOES_NOT_EXIST;
2573         return do_iterate_dir_tree(wim, dentry, ctx->flags, ctx->cb, ctx->user_ctx);
2574 }
2575
2576 /* API function documented in wimlib.h  */
2577 WIMLIBAPI int
2578 wimlib_iterate_dir_tree(WIMStruct *wim, int image, const tchar *path,
2579                         int flags,
2580                         wimlib_iterate_dir_tree_callback_t cb, void *user_ctx)
2581 {
2582         struct image_iterate_dir_tree_ctx ctx = {
2583                 .path = path,
2584                 .flags = flags,
2585                 .cb = cb,
2586                 .user_ctx = user_ctx,
2587         };
2588         wim->private = &ctx;
2589         return for_image(wim, image, image_do_iterate_dir_tree);
2590 }
2591
2592 /* Returns %true iff the metadata of @inode and @template_inode are reasonably
2593  * consistent with them being the same, unmodified file.  */
2594 static bool
2595 inode_metadata_consistent(const struct wim_inode *inode,
2596                           const struct wim_inode *template_inode,
2597                           const struct wim_lookup_table *template_lookup_table)
2598 {
2599         /* Must have exact same creation time and last write time.  */
2600         if (inode->i_creation_time != template_inode->i_creation_time ||
2601             inode->i_last_write_time != template_inode->i_last_write_time)
2602                 return false;
2603
2604         /* Last access time may have stayed the same or increased, but certainly
2605          * shouldn't have decreased.  */
2606         if (inode->i_last_access_time < template_inode->i_last_access_time)
2607                 return false;
2608
2609         /* Must have same number of alternate data stream entries.  */
2610         if (inode->i_num_ads != template_inode->i_num_ads)
2611                 return false;
2612
2613         /* If the stream entries for the inode are for some reason not resolved,
2614          * then the hashes are already available and the point of this function
2615          * is defeated.  */
2616         if (!inode->i_resolved)
2617                 return false;
2618
2619         /* Iterate through each stream and do some more checks.  */
2620         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
2621                 const struct wim_lookup_table_entry *lte, *template_lte;
2622
2623                 lte = inode_stream_lte_resolved(inode, i);
2624                 template_lte = inode_stream_lte(template_inode, i,
2625                                                 template_lookup_table);
2626
2627                 /* Compare stream sizes.  */
2628                 if (lte && template_lte) {
2629                         if (lte->size != template_lte->size)
2630                                 return false;
2631
2632                         /* If hash happens to be available, compare with template.  */
2633                         if (!lte->unhashed && !template_lte->unhashed &&
2634                             !hashes_equal(lte->hash, template_lte->hash))
2635                                 return false;
2636
2637                 } else if (lte && lte->size) {
2638                         return false;
2639                 } else if (template_lte && template_lte->size) {
2640                         return false;
2641                 }
2642         }
2643
2644         /* All right, barring a full checksum and given that the inodes share a
2645          * path and the user isn't trying to trick us, these inodes most likely
2646          * refer to the same file.  */
2647         return true;
2648 }
2649
2650 /**
2651  * Given an inode @inode that has been determined to be "the same" as another
2652  * inode @template_inode in either the same WIM or another WIM, retrieve some
2653  * useful stream information (e.g. checksums) from @template_inode.
2654  *
2655  * This assumes that the streams for @inode have been resolved (to point
2656  * directly to the appropriate `struct wim_lookup_table_entry's)  but do not
2657  * necessarily have checksum information filled in.
2658  */
2659 static int
2660 inode_copy_checksums(struct wim_inode *inode,
2661                      struct wim_inode *template_inode,
2662                      WIMStruct *wim,
2663                      WIMStruct *template_wim)
2664 {
2665         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
2666                 struct wim_lookup_table_entry *lte, *template_lte;
2667                 struct wim_lookup_table_entry *replace_lte;
2668
2669                 lte = inode_stream_lte_resolved(inode, i);
2670                 template_lte = inode_stream_lte(template_inode, i,
2671                                                 template_wim->lookup_table);
2672
2673                 /* Only take action if both entries exist, the entry for @inode
2674                  * has no checksum calculated, but the entry for @template_inode
2675                  * does.  */
2676                 if (lte == NULL || template_lte == NULL ||
2677                     !lte->unhashed || template_lte->unhashed)
2678                         continue;
2679
2680                 wimlib_assert(lte->refcnt == inode->i_nlink);
2681
2682                 /* If the WIM of the template image is the same as the WIM of
2683                  * the new image, then @template_lte can be used directly.
2684                  *
2685                  * Otherwise, look for a stream with the same hash in the WIM of
2686                  * the new image.  If found, use it; otherwise re-use the entry
2687                  * being discarded, filling in the hash.  */
2688
2689                 if (wim == template_wim)
2690                         replace_lte = template_lte;
2691                 else
2692                         replace_lte = lookup_resource(wim->lookup_table,
2693                                                       template_lte->hash);
2694
2695                 list_del(&lte->unhashed_list);
2696                 if (replace_lte) {
2697                         free_lookup_table_entry(lte);
2698                 } else {
2699                         copy_hash(lte->hash, template_lte->hash);
2700                         lte->unhashed = 0;
2701                         lookup_table_insert(wim->lookup_table, lte);
2702                         lte->refcnt = 0;
2703                         replace_lte = lte;
2704                 }
2705
2706                 if (i == 0)
2707                         inode->i_lte = replace_lte;
2708                 else
2709                         inode->i_ads_entries[i - 1].lte = replace_lte;
2710
2711                 replace_lte->refcnt += inode->i_nlink;
2712         }
2713         return 0;
2714 }
2715
2716 struct reference_template_args {
2717         WIMStruct *wim;
2718         WIMStruct *template_wim;
2719 };
2720
2721 static int
2722 dentry_reference_template(struct wim_dentry *dentry, void *_args)
2723 {
2724         int ret;
2725         struct wim_dentry *template_dentry;
2726         struct wim_inode *inode, *template_inode;
2727         struct reference_template_args *args = _args;
2728         WIMStruct *wim = args->wim;
2729         WIMStruct *template_wim = args->template_wim;
2730
2731         if (dentry->d_inode->i_visited)
2732                 return 0;
2733
2734         ret = calculate_dentry_full_path(dentry);
2735         if (ret)
2736                 return ret;
2737
2738         template_dentry = get_dentry(template_wim, dentry->_full_path);
2739         if (template_dentry == NULL) {
2740                 DEBUG("\"%"TS"\": newly added file", dentry->_full_path);
2741                 return 0;
2742         }
2743
2744         inode = dentry->d_inode;
2745         template_inode = template_dentry->d_inode;
2746
2747         if (inode_metadata_consistent(inode, template_inode,
2748                                       template_wim->lookup_table)) {
2749                 /*DEBUG("\"%"TS"\": No change detected", dentry->_full_path);*/
2750                 ret = inode_copy_checksums(inode, template_inode,
2751                                            wim, template_wim);
2752                 inode->i_visited = 1;
2753         } else {
2754                 DEBUG("\"%"TS"\": change detected!", dentry->_full_path);
2755                 ret = 0;
2756         }
2757         return ret;
2758 }
2759
2760 /* API function documented in wimlib.h  */
2761 WIMLIBAPI int
2762 wimlib_reference_template_image(WIMStruct *wim, int new_image,
2763                                 WIMStruct *template_wim, int template_image,
2764                                 int flags, wimlib_progress_func_t progress_func)
2765 {
2766         int ret;
2767         struct wim_image_metadata *new_imd;
2768
2769         if (wim == NULL || template_wim == NULL)
2770                 return WIMLIB_ERR_INVALID_PARAM;
2771
2772         if (wim == template_wim && new_image == template_image)
2773                 return WIMLIB_ERR_INVALID_PARAM;
2774
2775         if (new_image < 1 || new_image > wim->hdr.image_count)
2776                 return WIMLIB_ERR_INVALID_IMAGE;
2777
2778         if (!wim_has_metadata(wim))
2779                 return WIMLIB_ERR_METADATA_NOT_FOUND;
2780
2781         new_imd = wim->image_metadata[new_image - 1];
2782         if (!new_imd->modified)
2783                 return WIMLIB_ERR_INVALID_PARAM;
2784
2785         ret = select_wim_image(template_wim, template_image);
2786         if (ret)
2787                 return ret;
2788
2789         struct reference_template_args args = {
2790                 .wim = wim,
2791                 .template_wim = template_wim,
2792         };
2793
2794         ret = for_dentry_in_tree(new_imd->root_dentry,
2795                                  dentry_reference_template, &args);
2796         dentry_tree_clear_inode_visited(new_imd->root_dentry);
2797         return ret;
2798 }