for_dentry_in_tree(): Remove some gotos
[wimlib] / src / dentry.c
1 /*
2  * dentry.c
3  *
4  * A dentry (directory entry) contains the metadata for a file.  In the WIM file
5  * format, the dentries are stored in the "metadata resource" section right
6  * after the security data.  Each image in the WIM file has its own metadata
7  * resource with its own security data and dentry tree.  Dentries in different
8  * images may share file resources by referring to the same lookup table
9  * entries.
10  */
11
12 /*
13  * Copyright (C) 2012 Eric Biggers
14  *
15  * This file is part of wimlib, a library for working with WIM files.
16  *
17  * wimlib is free software; you can redistribute it and/or modify it under the
18  * terms of the GNU General Public License as published by the Free Software
19  * Foundation; either version 3 of the License, or (at your option) any later
20  * version.
21  *
22  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
23  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
24  * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
25  *
26  * You should have received a copy of the GNU General Public License along with
27  * wimlib; if not, see http://www.gnu.org/licenses/.
28  */
29
30 #include <errno.h>
31 #include <sys/stat.h>
32 #include <time.h>
33 #include <unistd.h>
34
35 #include "dentry.h"
36 #include "io.h"
37 #include "lookup_table.h"
38 #include "sha1.h"
39 #include "timestamp.h"
40 #include "wimlib_internal.h"
41
42
43 /* Calculates the unaligned length, in bytes, of an on-disk WIM dentry that has
44  * a file name and short name that take the specified numbers of bytes.  This
45  * excludes any alternate data stream entries that may follow the dentry. */
46 static u64 __dentry_correct_length_unaligned(u16 file_name_len,
47                                              u16 short_name_len)
48 {
49         u64 length = WIM_DENTRY_DISK_SIZE;
50         if (file_name_len)
51                 length += file_name_len + 2;
52         if (short_name_len)
53                 length += short_name_len + 2;
54         return length;
55 }
56
57 /* Calculates the unaligned length, in bytes, of an on-disk WIM dentry, based on
58  * the file name length and short name length.  Note that dentry->length is
59  * ignored; also, this excludes any alternate data stream entries that may
60  * follow the dentry. */
61 static u64 dentry_correct_length_unaligned(const struct dentry *dentry)
62 {
63         return __dentry_correct_length_unaligned(dentry->file_name_len,
64                                                  dentry->short_name_len);
65 }
66
67 /* Return the "correct" value to write in the length field of a WIM dentry,
68  * based on the file name length and short name length. */
69 static u64 dentry_correct_length(const struct dentry *dentry)
70 {
71         return (dentry_correct_length_unaligned(dentry) + 7) & ~7;
72 }
73
74 /* Return %true iff @dentry has the UTF-8 file name @name that has length
75  * @name_len bytes. */
76 static bool dentry_has_name(const struct dentry *dentry, const char *name,
77                             size_t name_len)
78 {
79         if (dentry->file_name_utf8_len != name_len)
80                 return false;
81         return memcmp(dentry->file_name_utf8, name, name_len) == 0;
82 }
83
84 /* Return %true iff the alternate data stream entry @entry has the UTF-8 stream
85  * name @name that has length @name_len bytes. */
86 static inline bool ads_entry_has_name(const struct ads_entry *entry,
87                                       const char *name, size_t name_len)
88 {
89         if (entry->stream_name_utf8_len != name_len)
90                 return false;
91         return memcmp(entry->stream_name_utf8, name, name_len) == 0;
92 }
93
94 /* Duplicates a UTF-8 name into UTF-8 and UTF-16 strings and returns the strings
95  * and their lengths in the pointer arguments */
96 int get_names(char **name_utf16_ret, char **name_utf8_ret,
97               u16 *name_utf16_len_ret, u16 *name_utf8_len_ret,
98               const char *name)
99 {
100         size_t utf8_len;
101         size_t utf16_len;
102         char *name_utf16, *name_utf8;
103
104         utf8_len = strlen(name);
105
106         name_utf16 = utf8_to_utf16(name, utf8_len, &utf16_len);
107
108         if (!name_utf16)
109                 return WIMLIB_ERR_NOMEM;
110
111         name_utf8 = MALLOC(utf8_len + 1);
112         if (!name_utf8) {
113                 FREE(name_utf8);
114                 return WIMLIB_ERR_NOMEM;
115         }
116         memcpy(name_utf8, name, utf8_len + 1);
117         FREE(*name_utf8_ret);
118         FREE(*name_utf16_ret);
119         *name_utf8_ret      = name_utf8;
120         *name_utf16_ret     = name_utf16;
121         *name_utf8_len_ret  = utf8_len;
122         *name_utf16_len_ret = utf16_len;
123         return 0;
124 }
125
126 /* Changes the name of a dentry to @new_name.  Only changes the file_name and
127  * file_name_utf8 fields; does not change the short_name, short_name_utf8, or
128  * full_path_utf8 fields.  Also recalculates its length. */
129 static int change_dentry_name(struct dentry *dentry, const char *new_name)
130 {
131         int ret;
132
133         ret = get_names(&dentry->file_name, &dentry->file_name_utf8,
134                         &dentry->file_name_len, &dentry->file_name_utf8_len,
135                          new_name);
136         FREE(dentry->short_name);
137         dentry->short_name_len = 0;
138         if (ret == 0)
139                 dentry->length = dentry_correct_length(dentry);
140         return ret;
141 }
142
143 /*
144  * Changes the name of an alternate data stream */
145 static int change_ads_name(struct ads_entry *entry, const char *new_name)
146 {
147         return get_names(&entry->stream_name, &entry->stream_name_utf8,
148                          &entry->stream_name_len,
149                          &entry->stream_name_utf8_len,
150                          new_name);
151 }
152
153 /* Returns the total length of a WIM alternate data stream entry on-disk,
154  * including the stream name, the null terminator, AND the padding after the
155  * entry to align the next one (or the next dentry) on an 8-byte boundary. */
156 static u64 ads_entry_total_length(const struct ads_entry *entry)
157 {
158         u64 len = WIM_ADS_ENTRY_DISK_SIZE;
159         if (entry->stream_name_len)
160                 len += entry->stream_name_len + 2;
161         return (len + 7) & ~7;
162 }
163
164
165 static u64 __dentry_total_length(const struct dentry *dentry, u64 length)
166 {
167         const struct inode *inode = dentry->d_inode;
168         for (u16 i = 0; i < inode->num_ads; i++)
169                 length += ads_entry_total_length(&inode->ads_entries[i]);
170         return (length + 7) & ~7;
171 }
172
173 /* Calculate the aligned *total* length of an on-disk WIM dentry.  This includes
174  * all alternate data streams. */
175 u64 dentry_correct_total_length(const struct dentry *dentry)
176 {
177         return __dentry_total_length(dentry,
178                                      dentry_correct_length_unaligned(dentry));
179 }
180
181 /* Like dentry_correct_total_length(), but use the existing dentry->length field
182  * instead of calculating its "correct" value. */
183 static u64 dentry_total_length(const struct dentry *dentry)
184 {
185         return __dentry_total_length(dentry, dentry->length);
186 }
187
188 /* Transfers file attributes from a `stat' buffer to a WIM "inode". */
189 void stbuf_to_inode(const struct stat *stbuf, struct inode *inode)
190 {
191         if (S_ISLNK(stbuf->st_mode)) {
192                 inode->attributes = FILE_ATTRIBUTE_REPARSE_POINT;
193                 inode->reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
194         } else if (S_ISDIR(stbuf->st_mode)) {
195                 inode->attributes = FILE_ATTRIBUTE_DIRECTORY;
196         } else {
197                 inode->attributes = FILE_ATTRIBUTE_NORMAL;
198         }
199         if (sizeof(ino_t) >= 8)
200                 inode->ino = (u64)stbuf->st_ino;
201         else
202                 inode->ino = (u64)stbuf->st_ino |
203                                    ((u64)stbuf->st_dev << ((sizeof(ino_t) * 8) & 63));
204         /* Set timestamps */
205         inode->creation_time = timespec_to_wim_timestamp(&stbuf->st_mtim);
206         inode->last_write_time = timespec_to_wim_timestamp(&stbuf->st_mtim);
207         inode->last_access_time = timespec_to_wim_timestamp(&stbuf->st_atim);
208 }
209
210 #ifdef WITH_FUSE
211 /* Transfers file attributes from a struct inode to a `stat' buffer.
212  *
213  * The lookup table entry tells us which stream in the inode we are statting.
214  * For a named data stream, everything returned is the same as the unnamed data
215  * stream except possibly the size and block count. */
216 int inode_to_stbuf(const struct inode *inode, struct lookup_table_entry *lte,
217                    struct stat *stbuf)
218 {
219         if (inode_is_symlink(inode))
220                 stbuf->st_mode = S_IFLNK | 0777;
221         else if (inode_is_directory(inode))
222                 stbuf->st_mode = S_IFDIR | 0755;
223         else
224                 stbuf->st_mode = S_IFREG | 0755;
225
226         stbuf->st_ino   = (ino_t)inode->ino;
227         stbuf->st_nlink = inode->link_count;
228         stbuf->st_uid   = getuid();
229         stbuf->st_gid   = getgid();
230
231         if (lte) {
232                 if (lte->resource_location == RESOURCE_IN_STAGING_FILE) {
233                         wimlib_assert(lte->staging_file_name);
234                         struct stat native_stat;
235                         if (stat(lte->staging_file_name, &native_stat) != 0) {
236                                 DEBUG("Failed to stat `%s': %m",
237                                       lte->staging_file_name);
238                                 return -errno;
239                         }
240                         stbuf->st_size = native_stat.st_size;
241                 } else {
242                         stbuf->st_size = wim_resource_size(lte);
243                 }
244         } else {
245                 stbuf->st_size = 0;
246         }
247
248         stbuf->st_atime   = wim_timestamp_to_unix(inode->last_access_time);
249         stbuf->st_mtime   = wim_timestamp_to_unix(inode->last_write_time);
250         stbuf->st_ctime   = wim_timestamp_to_unix(inode->creation_time);
251         stbuf->st_blocks  = (stbuf->st_size + 511) / 512;
252         return 0;
253 }
254 #endif
255
256 int for_dentry_in_rbtree(struct rb_node *root,
257                          int (*visitor)(struct dentry *, void *),
258                          void *arg)
259 {
260         int ret;
261         struct rb_node *node = root;
262         LIST_HEAD(stack);
263         while (true) {
264                 if (node) {
265                         list_add(&rbnode_dentry(node)->tmp_list, &stack);
266                         node = node->rb_left;
267                 } else {
268                         struct list_head *next;
269                         struct dentry *dentry;
270
271                         next = stack.next;
272                         if (next == &stack)
273                                 return 0;
274                         dentry = container_of(next, struct dentry, tmp_list);
275                         list_del(next);
276                         ret = visitor(dentry, arg);
277                         if (ret != 0)
278                                 return ret;
279                         node = dentry->rb_node.rb_right;
280                 }
281         }
282 }
283
284 static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
285                                            int (*visitor)(struct dentry*, void*),
286                                            void *arg)
287 {
288         int ret;
289         if (node) {
290                 ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
291                                                       visitor, arg);
292                 if (ret != 0)
293                         return ret;
294                 ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
295                                                       visitor, arg);
296                 if (ret != 0)
297                         return ret;
298                 ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
299                 if (ret != 0)
300                         return ret;
301         }
302         return 0;
303 }
304
305 /*
306  * Calls a function on all directory entries in a WIM dentry tree.  Logically,
307  * this is a pre-order traversal (the function is called on a parent dentry
308  * before its children), but sibling dentries will be visited in order as well.
309  *
310  * In reality, the data structures are more complicated than the above might
311  * suggest because there is a separate red-black tree for each dentry that
312  * contains its direct children.
313  */
314 int for_dentry_in_tree(struct dentry *root,
315                        int (*visitor)(struct dentry*, void*), void *arg)
316 {
317         int ret;
318         struct list_head main_stack;
319         struct list_head sibling_stack;
320         struct list_head *sibling_stack_bottom;
321         struct dentry *main_dentry;
322         struct rb_node *node;
323         struct list_head *next_sibling;
324         struct dentry *dentry;
325
326         ret = visitor(root, arg);
327         if (ret != 0)
328                 return ret;
329
330         main_dentry = root;
331         sibling_stack_bottom = &sibling_stack;
332         INIT_LIST_HEAD(&main_stack);
333         INIT_LIST_HEAD(&sibling_stack);
334
335         list_add(&root->tmp_list, &main_stack);
336         node = root->d_inode->children.rb_node;
337
338         while (1) {
339                 // Prepare for non-recursive in-order traversal of the red-black
340                 // tree of this dentry's children
341
342                 while (node) {
343                         // Push this node to the sibling stack and examine the
344                         // left neighbor, if any
345                         list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
346                         node = node->rb_left;
347                 }
348
349                 next_sibling = sibling_stack.next;
350                 if (next_sibling == sibling_stack_bottom) {
351                         // Done with all siblings.  Pop the main dentry to move
352                         // back up one level.
353                         main_dentry = container_of(main_stack.next,
354                                                    struct dentry,
355                                                    tmp_list);
356                         list_del(&main_dentry->tmp_list);
357
358                         if (main_dentry == root)
359                                 goto out;
360
361                         // Restore sibling stack bottom from the previous level
362                         sibling_stack_bottom = (void*)main_dentry->parent;
363
364                         // Restore the just-popped main dentry's parent
365                         main_dentry->parent = container_of(main_stack.next,
366                                                            struct dentry,
367                                                            tmp_list);
368
369                         // The next sibling to traverse in the previous level,
370                         // in the in-order traversal of the red-black tree, is
371                         // the one to the right.
372                         node = main_dentry->rb_node.rb_right;
373                 } else {
374                         // The sibling stack is not empty, so there are more to
375                         // go!
376
377                         // Pop a sibling from the stack.
378                         list_del(next_sibling);
379                         dentry = container_of(next_sibling, struct dentry, tmp_list);
380
381                         // Visit the sibling.
382                         ret = visitor(dentry, arg);
383                         if (ret != 0) {
384                                 // Failed.  Restore parent pointers for the
385                                 // dentries in the main stack
386                                 list_del(&root->tmp_list);
387                                 list_for_each_entry(dentry, &main_stack, tmp_list) {
388                                         dentry->parent = container_of(dentry->tmp_list.next,
389                                                                       struct dentry,
390                                                                       tmp_list);
391                                 }
392                                 goto out;
393                         }
394
395                         // We'd like to recursively visit the dentry tree rooted
396                         // at this sibling.  To do this, add it to the main
397                         // stack, save the bottom of this level's sibling stack
398                         // in the dentry->parent field, re-set the bottom of the
399                         // sibling stack to be its current height, and set
400                         // main_dentry to the sibling so it becomes the parent
401                         // dentry in the next iteration through the outer loop.
402                         if (inode_has_children(dentry->d_inode)) {
403                                 list_add(&dentry->tmp_list, &main_stack);
404                                 dentry->parent = (void*)sibling_stack_bottom;
405                                 sibling_stack_bottom = sibling_stack.next;
406
407                                 main_dentry = dentry;
408                                 node = main_dentry->d_inode->children.rb_node;
409                         } else  {
410                                 node = dentry->rb_node.rb_right;
411                         }
412                 }
413         }
414 out:
415         root->parent = root;
416         return ret;
417 }
418
419 /*
420  * Like for_dentry_in_tree(), but the visitor function is always called on a
421  * dentry's children before on itself.
422  */
423 int for_dentry_in_tree_depth(struct dentry *root,
424                              int (*visitor)(struct dentry*, void*), void *arg)
425 {
426 #if 1
427         int ret;
428         ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
429                                               visitor, arg);
430         if (ret != 0)
431                 return ret;
432         return visitor(root, arg);
433
434 #else
435         int ret;
436         struct list_head main_stack;
437         struct list_head sibling_stack;
438         struct list_head *sibling_stack_bottom;
439         struct dentry *main_dentry;
440         struct rb_node *node;
441         struct list_head *next_sibling;
442         struct dentry *dentry;
443
444         main_dentry = root;
445         sibling_stack_bottom = &sibling_stack;
446         INIT_LIST_HEAD(&main_stack);
447         INIT_LIST_HEAD(&sibling_stack);
448
449         list_add(&main_dentry->tmp_list, &main_stack);
450
451         while (1) {
452                 node = main_dentry->d_inode->children.rb_node;
453
454                 while (1) {
455                         if (node->rb_left) {
456                                 list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
457                                 node = node->rb_left;
458                                 continue;
459                         }
460                         if (node->rb_right) {
461                                 list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
462                                 node = node->rb_right;
463                                 continue;
464                         }
465                         list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
466                 }
467
468         pop_sibling:
469                 next_sibling = sibling_stack.next;
470                 if (next_sibling == sibling_stack_bottom) {
471                         main_dentry = container_of(main_stack.next,
472                                                    struct dentry,
473                                                    tmp_list);
474                         list_del(&main_dentry->tmp_list);
475
476
477                         sibling_stack_bottom = (void*)main_dentry->parent;
478
479                         if (main_dentry == root) {
480                                 main_dentry->parent = main_dentry;
481                                 ret = visitor(dentry, arg);
482                                 return ret;
483                         } else {
484                                 main_dentry->parent = container_of(main_stack.next,
485                                                                    struct dentry,
486                                                                    tmp_list);
487                         }
488
489                         ret = visitor(main_dentry, arg);
490
491                         if (ret != 0) {
492                                 list_del(&root->tmp_list);
493                                 list_for_each_entry(dentry, &main_stack, tmp_list) {
494                                         dentry->parent = container_of(dentry->tmp_list.next,
495                                                                       struct dentry,
496                                                                       tmp_list);
497                                 }
498                                 root->parent = root;
499                                 return ret;
500                         }
501                         goto pop_sibling;
502                 } else {
503
504                         list_del(next_sibling);
505                         dentry = container_of(next_sibling, struct dentry, tmp_list);
506
507
508                         list_add(&dentry->tmp_list, &main_stack);
509                         dentry->parent = (void*)sibling_stack_bottom;
510                         sibling_stack_bottom = sibling_stack.next;
511
512                         main_dentry = dentry;
513                 }
514         }
515 #endif
516 }
517
518 /*
519  * Calculate the full path of @dentry, based on its parent's full path and on
520  * its UTF-8 file name.
521  */
522 int calculate_dentry_full_path(struct dentry *dentry, void *ignore)
523 {
524         char *full_path;
525         u32 full_path_len;
526         if (dentry_is_root(dentry)) {
527                 full_path = MALLOC(2);
528                 if (!full_path)
529                         goto oom;
530                 full_path[0] = '/';
531                 full_path[1] = '\0';
532                 full_path_len = 1;
533         } else {
534                 char *parent_full_path;
535                 u32 parent_full_path_len;
536                 const struct dentry *parent = dentry->parent;
537
538                 if (dentry_is_root(parent)) {
539                         parent_full_path = "";
540                         parent_full_path_len = 0;
541                 } else {
542                         parent_full_path = parent->full_path_utf8;
543                         parent_full_path_len = parent->full_path_utf8_len;
544                 }
545
546                 full_path_len = parent_full_path_len + 1 +
547                                 dentry->file_name_utf8_len;
548                 full_path = MALLOC(full_path_len + 1);
549                 if (!full_path)
550                         goto oom;
551
552                 memcpy(full_path, parent_full_path, parent_full_path_len);
553                 full_path[parent_full_path_len] = '/';
554                 memcpy(full_path + parent_full_path_len + 1,
555                        dentry->file_name_utf8,
556                        dentry->file_name_utf8_len);
557                 full_path[full_path_len] = '\0';
558         }
559         FREE(dentry->full_path_utf8);
560         dentry->full_path_utf8 = full_path;
561         dentry->full_path_utf8_len = full_path_len;
562         return 0;
563 oom:
564         ERROR("Out of memory while calculating dentry full path");
565         return WIMLIB_ERR_NOMEM;
566 }
567
568 static int increment_subdir_offset(struct dentry *dentry, void *subdir_offset_p)
569 {
570         *(u64*)subdir_offset_p += dentry_correct_total_length(dentry);
571         return 0;
572 }
573
574 static int call_calculate_subdir_offsets(struct dentry *dentry,
575                                          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 calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
589 {
590         struct rb_node *node;
591
592         dentry->subdir_offset = *subdir_offset_p;
593         node = dentry->d_inode->children.rb_node;
594         if (node) {
595                 /* Advance the subdir offset by the amount of space the children
596                  * of this dentry take up. */
597                 for_dentry_in_rbtree(node, increment_subdir_offset, subdir_offset_p);
598
599                 /* End-of-directory dentry on disk. */
600                 *subdir_offset_p += 8;
601
602                 /* Recursively call calculate_subdir_offsets() on all the
603                  * children. */
604                 for_dentry_in_rbtree(node, call_calculate_subdir_offsets, subdir_offset_p);
605         } else {
606                 /* On disk, childless directories have a valid subdir_offset
607                  * that points to an 8-byte end-of-directory dentry.  Regular
608                  * files or reparse points have a subdir_offset of 0. */
609                 if (dentry_is_directory(dentry))
610                         *subdir_offset_p += 8;
611                 else
612                         dentry->subdir_offset = 0;
613         }
614 }
615
616 static int compare_names(const char *name_1, size_t len_1,
617                          const char *name_2, size_t len_2)
618 {
619         if (len_1 < len_2)
620                 return -1;
621         else if (len_1 > len_2)
622                 return 1;
623         else
624                 return memcmp(name_1, name_2, len_1);
625 }
626
627 static int dentry_compare_names(const struct dentry *d1, const struct dentry *d2)
628 {
629         return compare_names(d1->file_name_utf8, d1->file_name_utf8_len,
630                              d2->file_name_utf8, d2->file_name_utf8_len);
631 }
632
633
634 static struct dentry *
635 get_rbtree_child_with_name(const struct rb_node *node,
636                            const char *name, size_t name_len)
637 {
638         do {
639                 struct dentry *child = rbnode_dentry(node);
640                 int result = compare_names(name, name_len,
641                                            child->file_name_utf8,
642                                            child->file_name_utf8_len);
643                 if (result < 0)
644                         node = node->rb_left;
645                 else if (result > 0)
646                         node = node->rb_right;
647                 else
648                         return child;
649         } while (node);
650         return NULL;
651 }
652
653 /* Returns the child of @dentry that has the file name @name.
654  * Returns NULL if no child has the name. */
655 struct dentry *get_dentry_child_with_name(const struct dentry *dentry,
656                                           const char *name)
657 {
658         struct rb_node *node = dentry->d_inode->children.rb_node;
659         if (node)
660                 return get_rbtree_child_with_name(node, name, strlen(name));
661         else
662                 return NULL;
663 }
664
665 /* Retrieves the dentry that has the UTF-8 @path relative to the dentry
666  * @cur_dentry.  Returns NULL if no dentry having the path is found. */
667 static struct dentry *get_dentry_relative_path(struct dentry *cur_dentry,
668                                                const char *path)
669 {
670         if (*path == '\0')
671                 return cur_dentry;
672
673         struct rb_node *node = cur_dentry->d_inode->children.rb_node;
674         if (node) {
675                 struct dentry *child;
676                 size_t base_len;
677                 const char *new_path;
678
679                 new_path = path_next_part(path, &base_len);
680
681                 child = get_rbtree_child_with_name(node, path, base_len);
682                 if (child)
683                         return get_dentry_relative_path(child, new_path);
684         }
685         return NULL;
686 }
687
688 /* Returns the dentry corresponding to the UTF-8 @path, or NULL if there is no
689  * such dentry. */
690 struct dentry *get_dentry(WIMStruct *w, const char *path)
691 {
692         struct dentry *root = wim_root_dentry(w);
693         while (*path == '/')
694                 path++;
695         return get_dentry_relative_path(root, path);
696 }
697
698 struct inode *wim_pathname_to_inode(WIMStruct *w, const char *path)
699 {
700         struct dentry *dentry;
701         dentry = get_dentry(w, path);
702         if (dentry)
703                 return dentry->d_inode;
704         else
705                 return NULL;
706 }
707
708 /* Returns the dentry that corresponds to the parent directory of @path, or NULL
709  * if the dentry is not found. */
710 struct dentry *get_parent_dentry(WIMStruct *w, const char *path)
711 {
712         size_t path_len = strlen(path);
713         char buf[path_len + 1];
714
715         memcpy(buf, path, path_len + 1);
716
717         to_parent_name(buf, path_len);
718
719         return get_dentry(w, buf);
720 }
721
722 /* Prints the full path of a dentry. */
723 int print_dentry_full_path(struct dentry *dentry, void *ignore)
724 {
725         if (dentry->full_path_utf8)
726                 puts(dentry->full_path_utf8);
727         return 0;
728 }
729
730 /* We want to be able to show the names of the file attribute flags that are
731  * set. */
732 struct file_attr_flag {
733         u32 flag;
734         const char *name;
735 };
736 struct file_attr_flag file_attr_flags[] = {
737         {FILE_ATTRIBUTE_READONLY,           "READONLY"},
738         {FILE_ATTRIBUTE_HIDDEN,             "HIDDEN"},
739         {FILE_ATTRIBUTE_SYSTEM,             "SYSTEM"},
740         {FILE_ATTRIBUTE_DIRECTORY,          "DIRECTORY"},
741         {FILE_ATTRIBUTE_ARCHIVE,            "ARCHIVE"},
742         {FILE_ATTRIBUTE_DEVICE,             "DEVICE"},
743         {FILE_ATTRIBUTE_NORMAL,             "NORMAL"},
744         {FILE_ATTRIBUTE_TEMPORARY,          "TEMPORARY"},
745         {FILE_ATTRIBUTE_SPARSE_FILE,        "SPARSE_FILE"},
746         {FILE_ATTRIBUTE_REPARSE_POINT,      "REPARSE_POINT"},
747         {FILE_ATTRIBUTE_COMPRESSED,         "COMPRESSED"},
748         {FILE_ATTRIBUTE_OFFLINE,            "OFFLINE"},
749         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED,"NOT_CONTENT_INDEXED"},
750         {FILE_ATTRIBUTE_ENCRYPTED,          "ENCRYPTED"},
751         {FILE_ATTRIBUTE_VIRTUAL,            "VIRTUAL"},
752 };
753
754 /* Prints a directory entry.  @lookup_table is a pointer to the lookup table, if
755  * available.  If the dentry is unresolved and the lookup table is NULL, the
756  * lookup table entries will not be printed.  Otherwise, they will be. */
757 int print_dentry(struct dentry *dentry, void *lookup_table)
758 {
759         const u8 *hash;
760         struct lookup_table_entry *lte;
761         const struct inode *inode = dentry->d_inode;
762         time_t time;
763         char *p;
764
765         printf("[DENTRY]\n");
766         printf("Length            = %"PRIu64"\n", dentry->length);
767         printf("Attributes        = 0x%x\n", inode->attributes);
768         for (unsigned i = 0; i < ARRAY_LEN(file_attr_flags); i++)
769                 if (file_attr_flags[i].flag & inode->attributes)
770                         printf("    FILE_ATTRIBUTE_%s is set\n",
771                                 file_attr_flags[i].name);
772         printf("Security ID       = %d\n", inode->security_id);
773         printf("Subdir offset     = %"PRIu64"\n", dentry->subdir_offset);
774
775         /* Translate the timestamps into something readable */
776         time = wim_timestamp_to_unix(inode->creation_time);
777         p = asctime(gmtime(&time));
778         *(strrchr(p, '\n')) = '\0';
779         printf("Creation Time     = %s UTC\n", p);
780
781         time = wim_timestamp_to_unix(inode->last_access_time);
782         p = asctime(gmtime(&time));
783         *(strrchr(p, '\n')) = '\0';
784         printf("Last Access Time  = %s UTC\n", p);
785
786         time = wim_timestamp_to_unix(inode->last_write_time);
787         p = asctime(gmtime(&time));
788         *(strrchr(p, '\n')) = '\0';
789         printf("Last Write Time   = %s UTC\n", p);
790
791         printf("Reparse Tag       = 0x%"PRIx32"\n", inode->reparse_tag);
792         printf("Hard Link Group   = 0x%"PRIx64"\n", inode->ino);
793         printf("Hard Link Group Size = %"PRIu32"\n", inode->link_count);
794         printf("Number of Alternate Data Streams = %hu\n", inode->num_ads);
795         printf("Filename          = \"");
796         print_string(dentry->file_name, dentry->file_name_len);
797         puts("\"");
798         printf("Filename Length   = %hu\n", dentry->file_name_len);
799         printf("Filename (UTF-8)  = \"%s\"\n", dentry->file_name_utf8);
800         printf("Filename (UTF-8) Length = %hu\n", dentry->file_name_utf8_len);
801         printf("Short Name        = \"");
802         print_string(dentry->short_name, dentry->short_name_len);
803         puts("\"");
804         printf("Short Name Length = %hu\n", dentry->short_name_len);
805         printf("Full Path (UTF-8) = \"%s\"\n", dentry->full_path_utf8);
806         lte = inode_stream_lte(dentry->d_inode, 0, lookup_table);
807         if (lte) {
808                 print_lookup_table_entry(lte);
809         } else {
810                 hash = inode_stream_hash(inode, 0);
811                 if (hash) {
812                         printf("Hash              = 0x");
813                         print_hash(hash);
814                         putchar('\n');
815                         putchar('\n');
816                 }
817         }
818         for (u16 i = 0; i < inode->num_ads; i++) {
819                 printf("[Alternate Stream Entry %u]\n", i);
820                 printf("Name = \"%s\"\n", inode->ads_entries[i].stream_name_utf8);
821                 printf("Name Length (UTF-16) = %u\n",
822                         inode->ads_entries[i].stream_name_len);
823                 hash = inode_stream_hash(inode, i + 1);
824                 if (hash) {
825                         printf("Hash              = 0x");
826                         print_hash(hash);
827                         putchar('\n');
828                 }
829                 print_lookup_table_entry(inode_stream_lte(inode, i + 1,
830                                                           lookup_table));
831         }
832         return 0;
833 }
834
835 /* Initializations done on every `struct dentry'. */
836 static void dentry_common_init(struct dentry *dentry)
837 {
838         memset(dentry, 0, sizeof(struct dentry));
839         dentry->refcnt = 1;
840 }
841
842 static struct inode *new_timeless_inode()
843 {
844         struct inode *inode = CALLOC(1, sizeof(struct inode));
845         if (inode) {
846                 inode->security_id = -1;
847                 inode->link_count = 1;
848         #ifdef WITH_FUSE
849                 inode->next_stream_id = 1;
850         #endif
851                 INIT_LIST_HEAD(&inode->dentry_list);
852         }
853         return inode;
854 }
855
856 static struct inode *new_inode()
857 {
858         struct inode *inode = new_timeless_inode();
859         if (inode) {
860                 u64 now = get_wim_timestamp();
861                 inode->creation_time = now;
862                 inode->last_access_time = now;
863                 inode->last_write_time = now;
864         }
865         return inode;
866 }
867
868 /*
869  * Creates an unlinked directory entry.
870  *
871  * @name:  The UTF-8 filename of the new dentry.
872  *
873  * Returns a pointer to the new dentry, or NULL if out of memory.
874  */
875 struct dentry *new_dentry(const char *name)
876 {
877         struct dentry *dentry;
878
879         dentry = MALLOC(sizeof(struct dentry));
880         if (!dentry)
881                 goto err;
882
883         dentry_common_init(dentry);
884         if (change_dentry_name(dentry, name) != 0)
885                 goto err;
886
887         dentry->parent = dentry;
888
889         return dentry;
890 err:
891         FREE(dentry);
892         ERROR("Failed to allocate new dentry");
893         return NULL;
894 }
895
896
897 static struct dentry *__new_dentry_with_inode(const char *name, bool timeless)
898 {
899         struct dentry *dentry;
900         dentry = new_dentry(name);
901         if (dentry) {
902                 if (timeless)
903                         dentry->d_inode = new_timeless_inode();
904                 else
905                         dentry->d_inode = new_inode();
906                 if (dentry->d_inode) {
907                         inode_add_dentry(dentry, dentry->d_inode);
908                 } else {
909                         free_dentry(dentry);
910                         dentry = NULL;
911                 }
912         }
913         return dentry;
914 }
915
916 struct dentry *new_dentry_with_timeless_inode(const char *name)
917 {
918         return __new_dentry_with_inode(name, true);
919 }
920
921 struct dentry *new_dentry_with_inode(const char *name)
922 {
923         return __new_dentry_with_inode(name, false);
924 }
925
926
927 static int init_ads_entry(struct ads_entry *ads_entry, const char *name)
928 {
929         int ret = 0;
930         memset(ads_entry, 0, sizeof(*ads_entry));
931         if (name && *name)
932                 ret = change_ads_name(ads_entry, name);
933         return ret;
934 }
935
936 static void destroy_ads_entry(struct ads_entry *ads_entry)
937 {
938         FREE(ads_entry->stream_name);
939         FREE(ads_entry->stream_name_utf8);
940 }
941
942
943 /* Frees an inode. */
944 void free_inode(struct inode *inode)
945 {
946         if (inode) {
947                 if (inode->ads_entries) {
948                         for (u16 i = 0; i < inode->num_ads; i++)
949                                 destroy_ads_entry(&inode->ads_entries[i]);
950                         FREE(inode->ads_entries);
951                 }
952         #ifdef WITH_FUSE
953                 wimlib_assert(inode->num_opened_fds == 0);
954                 FREE(inode->fds);
955         #endif
956                 FREE(inode->extracted_file);
957                 FREE(inode);
958         }
959 }
960
961 /* Decrements link count on an inode and frees it if the link count reaches 0.
962  * */
963 static void put_inode(struct inode *inode)
964 {
965         wimlib_assert(inode);
966         wimlib_assert(inode->link_count);
967         if (--inode->link_count == 0) {
968         #ifdef WITH_FUSE
969                 if (inode->num_opened_fds == 0)
970         #endif
971                 {
972                         free_inode(inode);
973                 }
974         }
975 }
976
977 /* Frees a WIM dentry.
978  *
979  * The inode is freed only if its link count is decremented to 0.
980  */
981 void free_dentry(struct dentry *dentry)
982 {
983         wimlib_assert(dentry != NULL);
984         FREE(dentry->file_name);
985         FREE(dentry->file_name_utf8);
986         FREE(dentry->short_name);
987         FREE(dentry->full_path_utf8);
988         if (dentry->d_inode)
989                 put_inode(dentry->d_inode);
990         FREE(dentry);
991 }
992
993 void put_dentry(struct dentry *dentry)
994 {
995         wimlib_assert(dentry != NULL);
996         wimlib_assert(dentry->refcnt != 0);
997
998         if (--dentry->refcnt == 0)
999                 free_dentry(dentry);
1000 }
1001
1002 /*
1003  * This function is passed as an argument to for_dentry_in_tree_depth() in order
1004  * to free a directory tree.  __args is a pointer to a `struct free_dentry_args'.
1005  */
1006 static int do_free_dentry(struct dentry *dentry, void *__lookup_table)
1007 {
1008         struct lookup_table *lookup_table = __lookup_table;
1009         unsigned i;
1010
1011         if (lookup_table) {
1012                 struct lookup_table_entry *lte;
1013                 struct inode *inode = dentry->d_inode;
1014                 wimlib_assert(inode->link_count);
1015                 for (i = 0; i <= inode->num_ads; i++) {
1016                         lte = inode_stream_lte(inode, i, lookup_table);
1017                         if (lte)
1018                                 lte_decrement_refcnt(lte, lookup_table);
1019                 }
1020         }
1021
1022         put_dentry(dentry);
1023         return 0;
1024 }
1025
1026 /*
1027  * Unlinks and frees a dentry tree.
1028  *
1029  * @root:               The root of the tree.
1030  * @lookup_table:       The lookup table for dentries.  If non-NULL, the
1031  *                      reference counts in the lookup table for the lookup
1032  *                      table entries corresponding to the dentries will be
1033  *                      decremented.
1034  */
1035 void free_dentry_tree(struct dentry *root, struct lookup_table *lookup_table)
1036 {
1037         if (!root || !root->parent)
1038                 return;
1039         for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
1040 }
1041
1042 int increment_dentry_refcnt(struct dentry *dentry, void *ignore)
1043 {
1044         dentry->refcnt++;
1045         return 0;
1046 }
1047
1048 /*
1049  * Links a dentry into the directory tree.
1050  *
1051  * @dentry: The dentry to link.
1052  * @parent: The dentry that will be the parent of @dentry.
1053  */
1054 bool dentry_add_child(struct dentry * restrict parent,
1055                       struct dentry * restrict child)
1056 {
1057         wimlib_assert(dentry_is_directory(parent));
1058
1059         struct rb_root *root = &parent->d_inode->children;
1060         struct rb_node **new = &(root->rb_node);
1061         struct rb_node *rb_parent = NULL;
1062
1063         while (*new) {
1064                 struct dentry *this = rbnode_dentry(*new);
1065                 int result = dentry_compare_names(child, this);
1066
1067                 rb_parent = *new;
1068
1069                 if (result < 0)
1070                         new = &((*new)->rb_left);
1071                 else if (result > 0)
1072                         new = &((*new)->rb_right);
1073                 else
1074                         return false;
1075         }
1076         child->parent = parent;
1077         rb_link_node(&child->rb_node, rb_parent, new);
1078         rb_insert_color(&child->rb_node, root);
1079         return true;
1080 }
1081
1082 #ifdef WITH_FUSE
1083 /*
1084  * Unlink a dentry from the directory tree.
1085  *
1086  * Note: This merely removes it from the in-memory tree structure.
1087  */
1088 void unlink_dentry(struct dentry *dentry)
1089 {
1090         struct dentry *parent = dentry->parent;
1091         if (parent == dentry)
1092                 return;
1093         rb_erase(&dentry->rb_node, &parent->d_inode->children);
1094 }
1095 #endif
1096
1097 static inline struct dentry *inode_first_dentry(struct inode *inode)
1098 {
1099         wimlib_assert(inode->dentry_list.next != &inode->dentry_list);
1100         return container_of(inode->dentry_list.next, struct dentry,
1101                             inode_dentry_list);
1102 }
1103
1104 static int verify_inode(struct inode *inode, const WIMStruct *w)
1105 {
1106         const struct lookup_table *table = w->lookup_table;
1107         const struct wim_security_data *sd = wim_const_security_data(w);
1108         const struct dentry *first_dentry = inode_first_dentry(inode);
1109         int ret = WIMLIB_ERR_INVALID_DENTRY;
1110
1111         /* Check the security ID */
1112         if (inode->security_id < -1) {
1113                 ERROR("Dentry `%s' has an invalid security ID (%d)",
1114                         first_dentry->full_path_utf8, inode->security_id);
1115                 goto out;
1116         }
1117         if (inode->security_id >= sd->num_entries) {
1118                 ERROR("Dentry `%s' has an invalid security ID (%d) "
1119                       "(there are only %u entries in the security table)",
1120                         first_dentry->full_path_utf8, inode->security_id,
1121                         sd->num_entries);
1122                 goto out;
1123         }
1124
1125         /* Check that lookup table entries for all the resources exist, except
1126          * if the SHA1 message digest is all 0's, which indicates there is
1127          * intentionally no resource there.  */
1128         if (w->hdr.total_parts == 1) {
1129                 for (unsigned i = 0; i <= inode->num_ads; i++) {
1130                         struct lookup_table_entry *lte;
1131                         const u8 *hash;
1132                         hash = inode_stream_hash_unresolved(inode, i);
1133                         lte = __lookup_resource(table, hash);
1134                         if (!lte && !is_zero_hash(hash)) {
1135                                 ERROR("Could not find lookup table entry for stream "
1136                                       "%u of dentry `%s'", i, first_dentry->full_path_utf8);
1137                                 goto out;
1138                         }
1139                         if (lte && (lte->real_refcnt += inode->link_count) > lte->refcnt)
1140                         {
1141                         #ifdef ENABLE_ERROR_MESSAGES
1142                                 WARNING("The following lookup table entry "
1143                                         "has a reference count of %u, but",
1144                                         lte->refcnt);
1145                                 WARNING("We found %u references to it",
1146                                         lte->real_refcnt);
1147                                 WARNING("(One dentry referencing it is at `%s')",
1148                                          first_dentry->full_path_utf8);
1149
1150                                 print_lookup_table_entry(lte);
1151                         #endif
1152                                 /* Guess what!  install.wim for Windows 8
1153                                  * contains a stream with 2 dentries referencing
1154                                  * it, but the lookup table entry has reference
1155                                  * count of 1.  So we will need to handle this
1156                                  * case and not just make it be an error...  I'm
1157                                  * just setting the reference count to the
1158                                  * number of references we found.
1159                                  * (Unfortunately, even after doing this, the
1160                                  * reference count could be too low if it's also
1161                                  * referenced in other WIM images) */
1162
1163                         #if 1
1164                                 lte->refcnt = lte->real_refcnt;
1165                                 WARNING("Fixing reference count");
1166                         #else
1167                                 goto out;
1168                         #endif
1169                         }
1170                 }
1171         }
1172
1173         /* Make sure there is only one un-named stream. */
1174         unsigned num_unnamed_streams = 0;
1175         for (unsigned i = 0; i <= inode->num_ads; i++) {
1176                 const u8 *hash;
1177                 hash = inode_stream_hash_unresolved(inode, i);
1178                 if (!inode_stream_name_len(inode, i) && !is_zero_hash(hash))
1179                         num_unnamed_streams++;
1180         }
1181         if (num_unnamed_streams > 1) {
1182                 ERROR("Dentry `%s' has multiple (%u) un-named streams",
1183                       first_dentry->full_path_utf8, num_unnamed_streams);
1184                 goto out;
1185         }
1186         inode->verified = true;
1187         ret = 0;
1188 out:
1189         return ret;
1190 }
1191
1192 /* Run some miscellaneous verifications on a WIM dentry */
1193 int verify_dentry(struct dentry *dentry, void *wim)
1194 {
1195         int ret;
1196
1197         if (!dentry->d_inode->verified) {
1198                 ret = verify_inode(dentry->d_inode, wim);
1199                 if (ret != 0)
1200                         return ret;
1201         }
1202
1203         /* Cannot have a short name but no long name */
1204         if (dentry->short_name_len && !dentry->file_name_len) {
1205                 ERROR("Dentry `%s' has a short name but no long name",
1206                       dentry->full_path_utf8);
1207                 return WIMLIB_ERR_INVALID_DENTRY;
1208         }
1209
1210         /* Make sure root dentry is unnamed */
1211         if (dentry_is_root(dentry)) {
1212                 if (dentry->file_name_len) {
1213                         ERROR("The root dentry is named `%s', but it must "
1214                               "be unnamed", dentry->file_name_utf8);
1215                         return WIMLIB_ERR_INVALID_DENTRY;
1216                 }
1217         }
1218
1219 #if 0
1220         /* Check timestamps */
1221         if (inode->last_access_time < inode->creation_time ||
1222             inode->last_write_time < inode->creation_time) {
1223                 WARNING("Dentry `%s' was created after it was last accessed or "
1224                       "written to", dentry->full_path_utf8);
1225         }
1226 #endif
1227
1228         return 0;
1229 }
1230
1231
1232 #ifdef WITH_FUSE
1233 /* Returns the alternate data stream entry belonging to @inode that has the
1234  * stream name @stream_name. */
1235 struct ads_entry *inode_get_ads_entry(struct inode *inode,
1236                                       const char *stream_name,
1237                                       u16 *idx_ret)
1238 {
1239         size_t stream_name_len;
1240         if (!stream_name)
1241                 return NULL;
1242         if (inode->num_ads) {
1243                 u16 i = 0;
1244                 stream_name_len = strlen(stream_name);
1245                 do {
1246                         if (ads_entry_has_name(&inode->ads_entries[i],
1247                                                stream_name, stream_name_len))
1248                         {
1249                                 if (idx_ret)
1250                                         *idx_ret = i;
1251                                 return &inode->ads_entries[i];
1252                         }
1253                 } while (++i != inode->num_ads);
1254         }
1255         return NULL;
1256 }
1257 #endif
1258
1259 #if defined(WITH_FUSE) || defined(WITH_NTFS_3G)
1260 /*
1261  * Add an alternate stream entry to an inode and return a pointer to it, or NULL
1262  * if memory could not be allocated.
1263  */
1264 struct ads_entry *inode_add_ads(struct inode *inode, const char *stream_name)
1265 {
1266         u16 num_ads;
1267         struct ads_entry *ads_entries;
1268         struct ads_entry *new_entry;
1269
1270         DEBUG("Add alternate data stream \"%s\"", stream_name);
1271
1272         if (inode->num_ads >= 0xfffe) {
1273                 ERROR("Too many alternate data streams in one inode!");
1274                 return NULL;
1275         }
1276         num_ads = inode->num_ads + 1;
1277         ads_entries = REALLOC(inode->ads_entries,
1278                               num_ads * sizeof(inode->ads_entries[0]));
1279         if (!ads_entries) {
1280                 ERROR("Failed to allocate memory for new alternate data stream");
1281                 return NULL;
1282         }
1283         inode->ads_entries = ads_entries;
1284
1285         new_entry = &inode->ads_entries[num_ads - 1];
1286         if (init_ads_entry(new_entry, stream_name) != 0)
1287                 return NULL;
1288 #ifdef WITH_FUSE
1289         new_entry->stream_id = inode->next_stream_id++;
1290 #endif
1291         inode->num_ads = num_ads;
1292         return new_entry;
1293 }
1294 #endif
1295
1296 #ifdef WITH_FUSE
1297 /* Remove an alternate data stream from the inode  */
1298 void inode_remove_ads(struct inode *inode, u16 idx,
1299                       struct lookup_table *lookup_table)
1300 {
1301         struct ads_entry *ads_entry;
1302         struct lookup_table_entry *lte;
1303
1304         wimlib_assert(idx < inode->num_ads);
1305         wimlib_assert(inode->resolved);
1306
1307         ads_entry = &inode->ads_entries[idx];
1308
1309         DEBUG("Remove alternate data stream \"%s\"", ads_entry->stream_name_utf8);
1310
1311         lte = ads_entry->lte;
1312         if (lte)
1313                 lte_decrement_refcnt(lte, lookup_table);
1314
1315         destroy_ads_entry(ads_entry);
1316
1317         memcpy(&inode->ads_entries[idx],
1318                &inode->ads_entries[idx + 1],
1319                (inode->num_ads - idx - 1) * sizeof(inode->ads_entries[0]));
1320         inode->num_ads--;
1321 }
1322 #endif
1323
1324
1325
1326 /*
1327  * Reads the alternate data stream entries for a dentry.
1328  *
1329  * @p:  Pointer to buffer that starts with the first alternate stream entry.
1330  *
1331  * @inode:      Inode to load the alternate data streams into.
1332  *                      @inode->num_ads must have been set to the number of
1333  *                      alternate data streams that are expected.
1334  *
1335  * @remaining_size:     Number of bytes of data remaining in the buffer pointed
1336  *                              to by @p.
1337  *
1338  * The format of the on-disk alternate stream entries is as follows:
1339  *
1340  * struct ads_entry_on_disk {
1341  *      u64  length;          // Length of the entry, in bytes.  This includes
1342  *                                  all fields (including the stream name and
1343  *                                  null terminator if present, AND the padding!).
1344  *      u64  reserved;        // Seems to be unused
1345  *      u8   hash[20];        // SHA1 message digest of the uncompressed stream
1346  *      u16  stream_name_len; // Length of the stream name, in bytes
1347  *      char stream_name[];   // Stream name in UTF-16LE, @stream_name_len bytes long,
1348  *                                  not including null terminator
1349  *      u16  zero;            // UTF-16 null terminator for the stream name, NOT
1350  *                                  included in @stream_name_len.  Based on what
1351  *                                  I've observed from filenames in dentries,
1352  *                                  this field should not exist when
1353  *                                  (@stream_name_len == 0), but you can't
1354  *                                  actually tell because of the padding anyway
1355  *                                  (provided that the padding is zeroed, which
1356  *                                  it always seems to be).
1357  *      char padding[];       // Padding to make the size a multiple of 8 bytes.
1358  * };
1359  *
1360  * In addition, the entries are 8-byte aligned.
1361  *
1362  * Return 0 on success or nonzero on failure.  On success, inode->ads_entries
1363  * is set to an array of `struct ads_entry's of length inode->num_ads.  On
1364  * failure, @inode is not modified.
1365  */
1366 static int read_ads_entries(const u8 *p, struct inode *inode,
1367                             u64 remaining_size)
1368 {
1369         u16 num_ads;
1370         struct ads_entry *ads_entries;
1371         int ret;
1372
1373         num_ads = inode->num_ads;
1374         ads_entries = CALLOC(num_ads, sizeof(inode->ads_entries[0]));
1375         if (!ads_entries) {
1376                 ERROR("Could not allocate memory for %"PRIu16" "
1377                       "alternate data stream entries", num_ads);
1378                 return WIMLIB_ERR_NOMEM;
1379         }
1380
1381         for (u16 i = 0; i < num_ads; i++) {
1382                 struct ads_entry *cur_entry;
1383                 u64 length;
1384                 u64 length_no_padding;
1385                 u64 total_length;
1386                 size_t utf8_len;
1387                 const u8 *p_save = p;
1388
1389                 cur_entry = &ads_entries[i];
1390
1391         #ifdef WITH_FUSE
1392                 ads_entries[i].stream_id = i + 1;
1393         #endif
1394
1395                 /* Read the base stream entry, excluding the stream name. */
1396                 if (remaining_size < WIM_ADS_ENTRY_DISK_SIZE) {
1397                         ERROR("Stream entries go past end of metadata resource");
1398                         ERROR("(remaining_size = %"PRIu64")", remaining_size);
1399                         ret = WIMLIB_ERR_INVALID_DENTRY;
1400                         goto out_free_ads_entries;
1401                 }
1402
1403                 p = get_u64(p, &length);
1404                 p += 8; /* Skip the reserved field */
1405                 p = get_bytes(p, SHA1_HASH_SIZE, (u8*)cur_entry->hash);
1406                 p = get_u16(p, &cur_entry->stream_name_len);
1407
1408                 cur_entry->stream_name = NULL;
1409                 cur_entry->stream_name_utf8 = NULL;
1410
1411                 /* Length including neither the null terminator nor the padding
1412                  * */
1413                 length_no_padding = WIM_ADS_ENTRY_DISK_SIZE +
1414                                     cur_entry->stream_name_len;
1415
1416                 /* Length including the null terminator and the padding */
1417                 total_length = ((length_no_padding + 2) + 7) & ~7;
1418
1419                 wimlib_assert(total_length == ads_entry_total_length(cur_entry));
1420
1421                 if (remaining_size < length_no_padding) {
1422                         ERROR("Stream entries go past end of metadata resource");
1423                         ERROR("(remaining_size = %"PRIu64" bytes, "
1424                               "length_no_padding = %"PRIu64" bytes)",
1425                               remaining_size, length_no_padding);
1426                         ret = WIMLIB_ERR_INVALID_DENTRY;
1427                         goto out_free_ads_entries;
1428                 }
1429
1430                 /* The @length field in the on-disk ADS entry is expected to be
1431                  * equal to @total_length, which includes all of the entry and
1432                  * the padding that follows it to align the next ADS entry to an
1433                  * 8-byte boundary.  However, to be safe, we'll accept the
1434                  * length field as long as it's not less than the un-padded
1435                  * total length and not more than the padded total length. */
1436                 if (length < length_no_padding || length > total_length) {
1437                         ERROR("Stream entry has unexpected length "
1438                               "field (length field = %"PRIu64", "
1439                               "unpadded total length = %"PRIu64", "
1440                               "padded total length = %"PRIu64")",
1441                               length, length_no_padding, total_length);
1442                         ret = WIMLIB_ERR_INVALID_DENTRY;
1443                         goto out_free_ads_entries;
1444                 }
1445
1446                 if (cur_entry->stream_name_len) {
1447                         cur_entry->stream_name = MALLOC(cur_entry->stream_name_len);
1448                         if (!cur_entry->stream_name) {
1449                                 ret = WIMLIB_ERR_NOMEM;
1450                                 goto out_free_ads_entries;
1451                         }
1452                         get_bytes(p, cur_entry->stream_name_len,
1453                                   (u8*)cur_entry->stream_name);
1454                         cur_entry->stream_name_utf8 = utf16_to_utf8(cur_entry->stream_name,
1455                                                                     cur_entry->stream_name_len,
1456                                                                     &utf8_len);
1457                         cur_entry->stream_name_utf8_len = utf8_len;
1458
1459                         if (!cur_entry->stream_name_utf8) {
1460                                 ret = WIMLIB_ERR_NOMEM;
1461                                 goto out_free_ads_entries;
1462                         }
1463                 }
1464                 /* It's expected that the size of every ADS entry is a multiple
1465                  * of 8.  However, to be safe, I'm allowing the possibility of
1466                  * an ADS entry at the very end of the metadata resource ending
1467                  * un-aligned.  So although we still need to increment the input
1468                  * pointer by @total_length to reach the next ADS entry, it's
1469                  * possible that less than @total_length is actually remaining
1470                  * in the metadata resource. We should set the remaining size to
1471                  * 0 bytes if this happens. */
1472                 p = p_save + total_length;
1473                 if (remaining_size < total_length)
1474                         remaining_size = 0;
1475                 else
1476                         remaining_size -= total_length;
1477         }
1478         inode->ads_entries = ads_entries;
1479 #ifdef WITH_FUSE
1480         inode->next_stream_id = inode->num_ads + 1;
1481 #endif
1482         return 0;
1483 out_free_ads_entries:
1484         for (u16 i = 0; i < num_ads; i++)
1485                 destroy_ads_entry(&ads_entries[i]);
1486         FREE(ads_entries);
1487         return ret;
1488 }
1489
1490 /*
1491  * Reads a directory entry, including all alternate data stream entries that
1492  * follow it, from the WIM image's metadata resource.
1493  *
1494  * @metadata_resource:  Buffer containing the uncompressed metadata resource.
1495  * @metadata_resource_len:   Length of the metadata resource.
1496  * @offset:     Offset of this directory entry in the metadata resource.
1497  * @dentry:     A `struct dentry' that will be filled in by this function.
1498  *
1499  * Return 0 on success or nonzero on failure.  On failure, @dentry have been
1500  * modified, bu it will be left with no pointers to any allocated buffers.
1501  * On success, the dentry->length field must be examined.  If zero, this was a
1502  * special "end of directory" dentry and not a real dentry.  If nonzero, this
1503  * was a real dentry.
1504  */
1505 int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len,
1506                 u64 offset, struct dentry *dentry)
1507 {
1508         const u8 *p;
1509         u64 calculated_size;
1510         char *file_name = NULL;
1511         char *file_name_utf8 = NULL;
1512         char *short_name = NULL;
1513         u16 short_name_len;
1514         u16 file_name_len;
1515         size_t file_name_utf8_len = 0;
1516         int ret;
1517         struct inode *inode = NULL;
1518
1519         dentry_common_init(dentry);
1520
1521         /*Make sure the dentry really fits into the metadata resource.*/
1522         if (offset + 8 > metadata_resource_len || offset + 8 < offset) {
1523                 ERROR("Directory entry starting at %"PRIu64" ends past the "
1524                       "end of the metadata resource (size %"PRIu64")",
1525                       offset, metadata_resource_len);
1526                 return WIMLIB_ERR_INVALID_DENTRY;
1527         }
1528
1529         /* Before reading the whole dentry, we need to read just the length.
1530          * This is because a dentry of length 8 (that is, just the length field)
1531          * terminates the list of sibling directory entries. */
1532
1533         p = get_u64(&metadata_resource[offset], &dentry->length);
1534
1535         /* A zero length field (really a length of 8, since that's how big the
1536          * directory entry is...) indicates that this is the end of directory
1537          * dentry.  We do not read it into memory as an actual dentry, so just
1538          * return successfully in that case. */
1539         if (dentry->length == 0)
1540                 return 0;
1541
1542         /* If the dentry does not overflow the metadata resource buffer and is
1543          * not too short, read the rest of it (excluding the alternate data
1544          * streams, but including the file name and short name variable-length
1545          * fields) into memory. */
1546         if (offset + dentry->length >= metadata_resource_len
1547             || offset + dentry->length < offset)
1548         {
1549                 ERROR("Directory entry at offset %"PRIu64" and with size "
1550                       "%"PRIu64" ends past the end of the metadata resource "
1551                       "(size %"PRIu64")",
1552                       offset, dentry->length, metadata_resource_len);
1553                 return WIMLIB_ERR_INVALID_DENTRY;
1554         }
1555
1556         if (dentry->length < WIM_DENTRY_DISK_SIZE) {
1557                 ERROR("Directory entry has invalid length of %"PRIu64" bytes",
1558                       dentry->length);
1559                 return WIMLIB_ERR_INVALID_DENTRY;
1560         }
1561
1562         inode = new_timeless_inode();
1563         if (!inode)
1564                 return WIMLIB_ERR_NOMEM;
1565
1566         p = get_u32(p, &inode->attributes);
1567         p = get_u32(p, (u32*)&inode->security_id);
1568         p = get_u64(p, &dentry->subdir_offset);
1569
1570         /* 2 unused fields */
1571         p += 2 * sizeof(u64);
1572         /*p = get_u64(p, &dentry->unused1);*/
1573         /*p = get_u64(p, &dentry->unused2);*/
1574
1575         p = get_u64(p, &inode->creation_time);
1576         p = get_u64(p, &inode->last_access_time);
1577         p = get_u64(p, &inode->last_write_time);
1578
1579         p = get_bytes(p, SHA1_HASH_SIZE, inode->hash);
1580
1581         /*
1582          * I don't know what's going on here.  It seems like M$ screwed up the
1583          * reparse points, then put the fields in the same place and didn't
1584          * document it.  The WIM_HDR_FLAG_RP_FIX flag in the WIM header might
1585          * have something to do with this, but it's not documented.
1586          */
1587         if (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1588                 /* ??? */
1589                 p += 4;
1590                 p = get_u32(p, &inode->reparse_tag);
1591                 p += 4;
1592         } else {
1593                 p = get_u32(p, &inode->reparse_tag);
1594                 p = get_u64(p, &inode->ino);
1595         }
1596
1597         /* By the way, the reparse_reserved field does not actually exist (at
1598          * least when the file is not a reparse point) */
1599
1600         p = get_u16(p, &inode->num_ads);
1601
1602         p = get_u16(p, &short_name_len);
1603         p = get_u16(p, &file_name_len);
1604
1605         /* We now know the length of the file name and short name.  Make sure
1606          * the length of the dentry is large enough to actually hold them.
1607          *
1608          * The calculated length here is unaligned to allow for the possibility
1609          * that the dentry->length names an unaligned length, although this
1610          * would be unexpected. */
1611         calculated_size = __dentry_correct_length_unaligned(file_name_len,
1612                                                             short_name_len);
1613
1614         if (dentry->length < calculated_size) {
1615                 ERROR("Unexpected end of directory entry! (Expected "
1616                       "at least %"PRIu64" bytes, got %"PRIu64" bytes. "
1617                       "short_name_len = %hu, file_name_len = %hu)",
1618                       calculated_size, dentry->length,
1619                       short_name_len, file_name_len);
1620                 ret = WIMLIB_ERR_INVALID_DENTRY;
1621                 goto out_free_inode;
1622         }
1623
1624         /* Read the filename if present.  Note: if the filename is empty, there
1625          * is no null terminator following it. */
1626         if (file_name_len) {
1627                 file_name = MALLOC(file_name_len);
1628                 if (!file_name) {
1629                         ERROR("Failed to allocate %hu bytes for dentry file name",
1630                               file_name_len);
1631                         ret = WIMLIB_ERR_NOMEM;
1632                         goto out_free_inode;
1633                 }
1634                 p = get_bytes(p, file_name_len, file_name);
1635
1636                 /* Convert filename to UTF-8. */
1637                 file_name_utf8 = utf16_to_utf8(file_name, file_name_len,
1638                                                &file_name_utf8_len);
1639
1640                 if (!file_name_utf8) {
1641                         ERROR("Failed to allocate memory to convert UTF-16 "
1642                               "filename (%hu bytes) to UTF-8", file_name_len);
1643                         ret = WIMLIB_ERR_NOMEM;
1644                         goto out_free_file_name;
1645                 }
1646                 if (*(u16*)p)
1647                         WARNING("Expected two zero bytes following the file name "
1648                                 "`%s', but found non-zero bytes", file_name_utf8);
1649                 p += 2;
1650         }
1651
1652         /* Align the calculated size */
1653         calculated_size = (calculated_size + 7) & ~7;
1654
1655         if (dentry->length > calculated_size) {
1656                 /* Weird; the dentry says it's longer than it should be.  Note
1657                  * that the length field does NOT include the size of the
1658                  * alternate stream entries. */
1659
1660                 /* Strangely, some directory entries inexplicably have a little
1661                  * over 70 bytes of extra data.  The exact amount of data seems
1662                  * to be 72 bytes, but it is aligned on the next 8-byte
1663                  * boundary.  It does NOT seem to be alternate data stream
1664                  * entries.  Here's an example of the aligned data:
1665                  *
1666                  * 01000000 40000000 6c786bba c58ede11 b0bb0026 1870892a b6adb76f
1667                  * e63a3e46 8fca8653 0d2effa1 6c786bba c58ede11 b0bb0026 1870892a
1668                  * 00000000 00000000 00000000 00000000
1669                  *
1670                  * Here's one interpretation of how the data is laid out.
1671                  *
1672                  * struct unknown {
1673                  *      u32 field1; (always 0x00000001)
1674                  *      u32 field2; (always 0x40000000)
1675                  *      u8  data[48]; (???)
1676                  *      u64 reserved1; (always 0)
1677                  *      u64 reserved2; (always 0)
1678                  * };*/
1679                 DEBUG("Dentry for file or directory `%s' has %zu extra "
1680                       "bytes of data",
1681                       file_name_utf8, dentry->length - calculated_size);
1682         }
1683
1684         /* Read the short filename if present.  Note: if there is no short
1685          * filename, there is no null terminator following it. */
1686         if (short_name_len) {
1687                 short_name = MALLOC(short_name_len);
1688                 if (!short_name) {
1689                         ERROR("Failed to allocate %hu bytes for short filename",
1690                               short_name_len);
1691                         ret = WIMLIB_ERR_NOMEM;
1692                         goto out_free_file_name_utf8;
1693                 }
1694
1695                 p = get_bytes(p, short_name_len, short_name);
1696                 if (*(u16*)p)
1697                         WARNING("Expected two zero bytes following the short name of "
1698                                 "`%s', but found non-zero bytes", file_name_utf8);
1699                 p += 2;
1700         }
1701
1702         /*
1703          * Read the alternate data streams, if present.  dentry->num_ads tells
1704          * us how many they are, and they will directly follow the dentry
1705          * on-disk.
1706          *
1707          * Note that each alternate data stream entry begins on an 8-byte
1708          * aligned boundary, and the alternate data stream entries are NOT
1709          * included in the dentry->length field for some reason.
1710          */
1711         if (inode->num_ads != 0) {
1712
1713                 /* Trying different lengths is just a hack to make sure we have
1714                  * a chance of reading the ADS entries correctly despite the
1715                  * poor documentation. */
1716
1717                 if (calculated_size != dentry->length) {
1718                         WARNING("Trying calculated dentry length (%"PRIu64") "
1719                                 "instead of dentry->length field (%"PRIu64") "
1720                                 "to read ADS entries",
1721                                 calculated_size, dentry->length);
1722                 }
1723                 u64 lengths_to_try[3] = {calculated_size,
1724                                          (dentry->length + 7) & ~7,
1725                                          dentry->length};
1726                 ret = WIMLIB_ERR_INVALID_DENTRY;
1727                 for (size_t i = 0; i < ARRAY_LEN(lengths_to_try); i++) {
1728                         if (lengths_to_try[i] > metadata_resource_len - offset)
1729                                 continue;
1730                         ret = read_ads_entries(&metadata_resource[offset + lengths_to_try[i]],
1731                                                inode,
1732                                                metadata_resource_len - offset - lengths_to_try[i]);
1733                         if (ret == 0)
1734                                 goto out;
1735                 }
1736                 ERROR("Failed to read alternate data stream "
1737                       "entries of `%s'", dentry->file_name_utf8);
1738                 goto out_free_short_name;
1739         }
1740 out:
1741
1742         /* We've read all the data for this dentry.  Set the names and their
1743          * lengths, and we've done. */
1744         dentry->d_inode            = inode;
1745         dentry->file_name          = file_name;
1746         dentry->file_name_utf8     = file_name_utf8;
1747         dentry->short_name         = short_name;
1748         dentry->file_name_len      = file_name_len;
1749         dentry->file_name_utf8_len = file_name_utf8_len;
1750         dentry->short_name_len     = short_name_len;
1751         return 0;
1752 out_free_short_name:
1753         FREE(short_name);
1754 out_free_file_name_utf8:
1755         FREE(file_name_utf8);
1756 out_free_file_name:
1757         FREE(file_name);
1758 out_free_inode:
1759         free_inode(inode);
1760         return ret;
1761 }
1762
1763 /* Reads the children of a dentry, and all their children, ..., etc. from the
1764  * metadata resource and into the dentry tree.
1765  *
1766  * @metadata_resource:  An array that contains the uncompressed metadata
1767  *                      resource for the WIM file.
1768  *
1769  * @metadata_resource_len:  The length of the uncompressed metadata resource, in
1770  *                          bytes.
1771  *
1772  * @dentry:     A pointer to a `struct dentry' that is the root of the directory
1773  *              tree and has already been read from the metadata resource.  It
1774  *              does not need to be the real root because this procedure is
1775  *              called recursively.
1776  *
1777  * @return:     Zero on success, nonzero on failure.
1778  */
1779 int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
1780                      struct dentry *dentry)
1781 {
1782         u64 cur_offset = dentry->subdir_offset;
1783         struct dentry *prev_child = NULL;
1784         struct dentry *first_child = NULL;
1785         struct dentry *child;
1786         struct dentry cur_child;
1787         int ret;
1788
1789         /*
1790          * If @dentry has no child dentries, nothing more needs to be done for
1791          * this branch.  This is the case for regular files, symbolic links, and
1792          * *possibly* empty directories (although an empty directory may also
1793          * have one child dentry that is the special end-of-directory dentry)
1794          */
1795         if (cur_offset == 0)
1796                 return 0;
1797
1798         /* Find and read all the children of @dentry. */
1799         while (1) {
1800
1801                 /* Read next child of @dentry into @cur_child. */
1802                 ret = read_dentry(metadata_resource, metadata_resource_len,
1803                                   cur_offset, &cur_child);
1804                 if (ret != 0)
1805                         break;
1806
1807                 /* Check for end of directory. */
1808                 if (cur_child.length == 0)
1809                         break;
1810
1811                 /* Not end of directory.  Allocate this child permanently and
1812                  * link it to the parent and previous child. */
1813                 child = MALLOC(sizeof(struct dentry));
1814                 if (!child) {
1815                         ERROR("Failed to allocate %zu bytes for new dentry",
1816                               sizeof(struct dentry));
1817                         ret = WIMLIB_ERR_NOMEM;
1818                         break;
1819                 }
1820                 memcpy(child, &cur_child, sizeof(struct dentry));
1821
1822                 dentry_add_child(dentry, child);
1823
1824                 inode_add_dentry(child, child->d_inode);
1825
1826                 /* If there are children of this child, call this procedure
1827                  * recursively. */
1828                 if (child->subdir_offset != 0) {
1829                         ret = read_dentry_tree(metadata_resource,
1830                                                metadata_resource_len, child);
1831                         if (ret != 0)
1832                                 break;
1833                 }
1834
1835                 /* Advance to the offset of the next child.  Note: We need to
1836                  * advance by the TOTAL length of the dentry, not by the length
1837                  * child->length, which although it does take into account the
1838                  * padding, it DOES NOT take into account alternate stream
1839                  * entries. */
1840                 cur_offset += dentry_total_length(child);
1841         }
1842         return ret;
1843 }
1844
1845 /*
1846  * Writes a WIM dentry to an output buffer.
1847  *
1848  * @dentry:  The dentry structure.
1849  * @p:       The memory location to write the data to.
1850  * @return:  Pointer to the byte after the last byte we wrote as part of the
1851  *              dentry.
1852  */
1853 static u8 *write_dentry(const struct dentry *dentry, u8 *p)
1854 {
1855         u8 *orig_p = p;
1856         const u8 *hash;
1857         const struct inode *inode = dentry->d_inode;
1858
1859         /* We calculate the correct length of the dentry ourselves because the
1860          * dentry->length field may been set to an unexpected value from when we
1861          * read the dentry in (for example, there may have been unknown data
1862          * appended to the end of the dentry...) */
1863         u64 length = dentry_correct_length(dentry);
1864
1865         p = put_u64(p, length);
1866         p = put_u32(p, inode->attributes);
1867         p = put_u32(p, inode->security_id);
1868         p = put_u64(p, dentry->subdir_offset);
1869         p = put_u64(p, 0); /* unused1 */
1870         p = put_u64(p, 0); /* unused2 */
1871         p = put_u64(p, inode->creation_time);
1872         p = put_u64(p, inode->last_access_time);
1873         p = put_u64(p, inode->last_write_time);
1874         hash = inode_stream_hash(inode, 0);
1875         p = put_bytes(p, SHA1_HASH_SIZE, hash);
1876         if (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1877                 p = put_zeroes(p, 4);
1878                 p = put_u32(p, inode->reparse_tag);
1879                 p = put_zeroes(p, 4);
1880         } else {
1881                 u64 link_group_id;
1882                 p = put_u32(p, 0);
1883                 if (inode->link_count == 1)
1884                         link_group_id = 0;
1885                 else
1886                         link_group_id = inode->ino;
1887                 p = put_u64(p, link_group_id);
1888         }
1889         p = put_u16(p, inode->num_ads);
1890         p = put_u16(p, dentry->short_name_len);
1891         p = put_u16(p, dentry->file_name_len);
1892         if (dentry->file_name_len) {
1893                 p = put_bytes(p, dentry->file_name_len, (u8*)dentry->file_name);
1894                 p = put_u16(p, 0); /* filename padding, 2 bytes. */
1895         }
1896         if (dentry->short_name) {
1897                 p = put_bytes(p, dentry->short_name_len, (u8*)dentry->short_name);
1898                 p = put_u16(p, 0); /* short name padding, 2 bytes */
1899         }
1900
1901         /* Align to 8-byte boundary */
1902         wimlib_assert(length >= (p - orig_p) && length - (p - orig_p) <= 7);
1903         p = put_zeroes(p, length - (p - orig_p));
1904
1905         /* Write the alternate data streams, if there are any.  Please see
1906          * read_ads_entries() for comments about the format of the on-disk
1907          * alternate data stream entries. */
1908         for (u16 i = 0; i < inode->num_ads; i++) {
1909                 p = put_u64(p, ads_entry_total_length(&inode->ads_entries[i]));
1910                 p = put_u64(p, 0); /* Unused */
1911                 hash = inode_stream_hash(inode, i + 1);
1912                 p = put_bytes(p, SHA1_HASH_SIZE, hash);
1913                 p = put_u16(p, inode->ads_entries[i].stream_name_len);
1914                 if (inode->ads_entries[i].stream_name_len) {
1915                         p = put_bytes(p, inode->ads_entries[i].stream_name_len,
1916                                          (u8*)inode->ads_entries[i].stream_name);
1917                         p = put_u16(p, 0);
1918                 }
1919                 p = put_zeroes(p, (8 - (p - orig_p) % 8) % 8);
1920         }
1921         wimlib_assert(p - orig_p == __dentry_total_length(dentry, length));
1922         return p;
1923 }
1924
1925 static int write_dentry_cb(struct dentry *dentry, void *_p)
1926 {
1927         u8 **p = _p;
1928         *p = write_dentry(dentry, *p);
1929         return 0;
1930 }
1931
1932 static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p);
1933
1934 static int write_dentry_tree_recursive_cb(struct dentry *dentry, void *_p)
1935 {
1936         u8 **p = _p;
1937         *p = write_dentry_tree_recursive(dentry, *p);
1938         return 0;
1939 }
1940
1941 /* Recursive function that writes a dentry tree rooted at @parent, not including
1942  * @parent itself, which has already been written. */
1943 static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p)
1944 {
1945         /* Nothing to do if this dentry has no children. */
1946         if (parent->subdir_offset == 0)
1947                 return p;
1948
1949         /* Write child dentries and end-of-directory entry.
1950          *
1951          * Note: we need to write all of this dentry's children before
1952          * recursively writing the directory trees rooted at each of the child
1953          * dentries, since the on-disk dentries for a dentry's children are
1954          * always located at consecutive positions in the metadata resource! */
1955         for_dentry_in_rbtree(parent->d_inode->children.rb_node, write_dentry_cb, &p);
1956
1957         /* write end of directory entry */
1958         p = put_u64(p, 0);
1959
1960         /* Recurse on children. */
1961         for_dentry_in_rbtree(parent->d_inode->children.rb_node,
1962                              write_dentry_tree_recursive_cb, &p);
1963         return p;
1964 }
1965
1966 /* Writes a directory tree to the metadata resource.
1967  *
1968  * @root:       Root of the dentry tree.
1969  * @p:          Pointer to a buffer with enough space for the dentry tree.
1970  *
1971  * Returns pointer to the byte after the last byte we wrote.
1972  */
1973 u8 *write_dentry_tree(const struct dentry *root, u8 *p)
1974 {
1975         DEBUG("Writing dentry tree.");
1976         wimlib_assert(dentry_is_root(root));
1977
1978         /* If we're the root dentry, we have no parent that already
1979          * wrote us, so we need to write ourselves. */
1980         p = write_dentry(root, p);
1981
1982         /* Write end of directory entry after the root dentry just to be safe;
1983          * however the root dentry obviously cannot have any siblings. */
1984         p = put_u64(p, 0);
1985
1986         /* Recursively write the rest of the dentry tree. */
1987         return write_dentry_tree_recursive(root, p);
1988 }
1989