Reviewed code in dentry.c and {read,write}_metadata_resource()
[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  *
14  * Copyright (C) 2010 Carl Thijssen
15  * Copyright (C) 2012 Eric Biggers
16  *
17  * This file is part of wimlib, a library for working with WIM files.
18  *
19  * wimlib is free software; you can redistribute it and/or modify it under the
20  * terms of the GNU Lesser General Public License as published by the Free
21  * Software Foundation; either version 2.1 of the License, or (at your option)
22  * any later version.
23  *
24  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
25  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
26  * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
27  * details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with wimlib; if not, see http://www.gnu.org/licenses/.
31  */
32
33 #include <errno.h>
34 #include <sys/stat.h>
35 #include <time.h>
36 #include <unistd.h>
37
38 #include "dentry.h"
39 #include "io.h"
40 #include "lookup_table.h"
41 #include "sha1.h"
42 #include "timestamp.h"
43 #include "wimlib_internal.h"
44
45 /*
46  * Returns true if @dentry has the UTF-8 file name @name that has length
47  * @name_len.
48  */
49 static bool dentry_has_name(const struct dentry *dentry, const char *name, 
50                             size_t name_len)
51 {
52         if (dentry->file_name_utf8_len != name_len)
53                 return false;
54         return memcmp(dentry->file_name_utf8, name, name_len) == 0;
55 }
56
57 /* Real length of a dentry, including the alternate data stream entries, which
58  * are not included in the dentry->length field... */
59 u64 dentry_total_length(const struct dentry *dentry)
60 {
61         u64 length = (dentry->length + 7) & ~7;
62         for (u16 i = 0; i < dentry->num_ads; i++)
63                 length += ads_entry_total_length(&dentry->ads_entries[i]);
64         return length;
65 }
66
67 /* Transfers file attributes from a `stat' buffer to a struct dentry. */
68 void stbuf_to_dentry(const struct stat *stbuf, struct dentry *dentry)
69 {
70         if (S_ISLNK(stbuf->st_mode)) {
71                 dentry->attributes = FILE_ATTRIBUTE_REPARSE_POINT;
72                 dentry->reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
73         } else if (S_ISDIR(stbuf->st_mode)) {
74                 dentry->attributes = FILE_ATTRIBUTE_DIRECTORY;
75         } else {
76                 dentry->attributes = FILE_ATTRIBUTE_NORMAL;
77         }
78         if (sizeof(ino_t) >= 8)
79                 dentry->hard_link = (u64)stbuf->st_ino;
80         else
81                 dentry->hard_link = (u64)stbuf->st_ino |
82                                    ((u64)stbuf->st_dev << (sizeof(ino_t) * 8));
83         /* Set timestamps */
84         dentry->creation_time = timespec_to_wim_timestamp(&stbuf->st_mtim);
85         dentry->last_write_time = timespec_to_wim_timestamp(&stbuf->st_mtim);
86         dentry->last_access_time = timespec_to_wim_timestamp(&stbuf->st_atim);
87 }
88
89
90 /* Sets all the timestamp fields of the dentry to the current time. */
91 void dentry_update_all_timestamps(struct dentry *dentry)
92 {
93         u64 now = get_wim_timestamp();
94         dentry->creation_time    = now;
95         dentry->last_access_time = now;
96         dentry->last_write_time  = now;
97 }
98
99 /* Returns the alternate data stream entry belonging to @dentry that has the
100  * stream name @stream_name. */
101 struct ads_entry *dentry_get_ads_entry(struct dentry *dentry,
102                                        const char *stream_name)
103 {
104         size_t stream_name_len;
105         if (!stream_name)
106                 return NULL;
107         if (dentry->num_ads) {
108                 u16 i = 0;
109                 stream_name_len = strlen(stream_name);
110                 do {
111                         if (ads_entry_has_name(&dentry->ads_entries[i],
112                                                stream_name, stream_name_len))
113                                 return &dentry->ads_entries[i];
114                 } while (++i != dentry->num_ads);
115         }
116         return NULL;
117 }
118
119 static void ads_entry_init(struct ads_entry *ads_entry)
120 {
121         memset(ads_entry, 0, sizeof(struct ads_entry));
122         INIT_LIST_HEAD(&ads_entry->lte_group_list.list);
123         ads_entry->lte_group_list.type = STREAM_TYPE_ADS;
124 }
125
126 /* 
127  * Add an alternate stream entry to a dentry and return a pointer to it, or NULL
128  * if memory could not be allocated.
129  */
130 struct ads_entry *dentry_add_ads(struct dentry *dentry, const char *stream_name)
131 {
132         u16 num_ads;
133         struct ads_entry *ads_entries;
134         struct ads_entry *new_entry;
135
136         DEBUG("Add alternate data stream %s:%s",
137                dentry->file_name_utf8, stream_name);
138
139         if (dentry->num_ads == 0xffff)
140                 return NULL;
141         num_ads = dentry->num_ads + 1;
142         ads_entries = REALLOC(dentry->ads_entries,
143                               num_ads * sizeof(struct ads_entry));
144         if (!ads_entries)
145                 return NULL;
146         if (ads_entries != dentry->ads_entries) {
147                 /* We moved the ADS entries.  Adjust the stream lists. */
148                 for (u16 i = 0; i < dentry->num_ads; i++) {
149                         struct list_head *cur = &ads_entries[i].lte_group_list.list;
150                         cur->prev->next = cur;
151                         cur->next->prev = cur;
152                 }
153         }
154
155         new_entry = &ads_entries[num_ads - 1];
156         ads_entry_init(new_entry);
157         if (change_ads_name(new_entry, stream_name) != 0)
158                 return NULL;
159         dentry->ads_entries = ads_entries;
160         dentry->num_ads = num_ads;
161         return new_entry;
162 }
163
164 /* Remove an alternate data stream from a dentry.
165  *
166  * The corresponding lookup table entry for the stream is NOT changed.
167  *
168  * @dentry:     The dentry
169  * @ads_entry:  The alternate data stream entry (it MUST be one of the
170  *                 ads_entry's in the array dentry->ads_entries).
171  */
172 void dentry_remove_ads(struct dentry *dentry, struct ads_entry *ads_entry)
173 {
174         u16 idx;
175         u16 following;
176
177         wimlib_assert(dentry->num_ads);
178         idx = ads_entry - dentry->ads_entries;
179         wimlib_assert(idx < dentry->num_ads);
180         following = dentry->num_ads - idx - 1;
181
182         destroy_ads_entry(ads_entry);
183         memcpy(ads_entry, ads_entry + 1, following * sizeof(struct ads_entry));
184
185         /* We moved the ADS entries.  Adjust the stream lists. */
186         for (u16 i = 0; i < following; i++) {
187                 struct list_head *cur = &ads_entry[i].lte_group_list.list;
188                 cur->prev->next = cur;
189                 cur->next->prev = cur;
190         }
191
192         dentry->num_ads--;
193 }
194
195 /* 
196  * Calls a function on all directory entries in a directory tree.  It is called
197  * on a parent before its children.
198  */
199 int for_dentry_in_tree(struct dentry *root, 
200                        int (*visitor)(struct dentry*, void*), void *arg)
201 {
202         int ret;
203         struct dentry *child;
204
205         ret = visitor(root, arg);
206
207         if (ret != 0)
208                 return ret;
209
210         child = root->children;
211
212         if (!child)
213                 return 0;
214
215         do {
216                 ret = for_dentry_in_tree(child, visitor, arg);
217                 if (ret != 0)
218                         return ret;
219                 child = child->next;
220         } while (child != root->children);
221         return 0;
222 }
223
224 /* 
225  * Like for_dentry_in_tree(), but the visitor function is always called on a
226  * dentry's children before on itself.
227  */
228 int for_dentry_in_tree_depth(struct dentry *root, 
229                              int (*visitor)(struct dentry*, void*), void *arg)
230 {
231         int ret;
232         struct dentry *child;
233         struct dentry *next;
234
235         child = root->children;
236         if (child) {
237                 do {
238                         next = child->next;
239                         ret = for_dentry_in_tree_depth(child, visitor, arg);
240                         if (ret != 0)
241                                 return ret;
242                         child = next;
243                 } while (child != root->children);
244         }
245         return visitor(root, arg);
246 }
247
248 /* 
249  * Calculate the full path of @dentry, based on its parent's full path and on
250  * its UTF-8 file name. 
251  */
252 int calculate_dentry_full_path(struct dentry *dentry, void *ignore)
253 {
254         char *full_path;
255         u32 full_path_len;
256         if (dentry_is_root(dentry)) {
257                 full_path = MALLOC(2);
258                 if (!full_path)
259                         goto oom;
260                 full_path[0] = '/';
261                 full_path[1] = '\0';
262                 full_path_len = 1;
263         } else {
264                 char *parent_full_path;
265                 u32 parent_full_path_len;
266                 const struct dentry *parent = dentry->parent;
267
268                 if (dentry_is_root(parent)) {
269                         parent_full_path = "";
270                         parent_full_path_len = 0;
271                 } else {
272                         parent_full_path = parent->full_path_utf8;
273                         parent_full_path_len = parent->full_path_utf8_len;
274                 }
275
276                 full_path_len = parent_full_path_len + 1 +
277                                 dentry->file_name_utf8_len;
278                 full_path = MALLOC(full_path_len + 1);
279                 if (!full_path)
280                         goto oom;
281
282                 memcpy(full_path, parent_full_path, parent_full_path_len);
283                 full_path[parent_full_path_len] = '/';
284                 memcpy(full_path + parent_full_path_len + 1,
285                        dentry->file_name_utf8,
286                        dentry->file_name_utf8_len);
287                 full_path[full_path_len] = '\0';
288         }
289         FREE(dentry->full_path_utf8);
290         dentry->full_path_utf8 = full_path;
291         dentry->full_path_utf8_len = full_path_len;
292         return 0;
293 oom:
294         ERROR("Out of memory while calculating dentry full path");
295         return WIMLIB_ERR_NOMEM;
296 }
297
298 /* 
299  * Recursively calculates the subdir offsets for a directory tree. 
300  *
301  * @dentry:  The root of the directory tree.
302  * @subdir_offset_p:  The current subdirectory offset; i.e., the subdirectory
303  *      offset for @dentry. 
304  */
305 void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
306 {
307         struct dentry *child;
308
309         child = dentry->children;
310         dentry->subdir_offset = *subdir_offset_p;
311
312         if (child) {
313                 /* Advance the subdir offset by the amount of space the children
314                  * of this dentry take up. */
315                 do {
316                         *subdir_offset_p += dentry_total_length(child);
317                         child = child->next;
318                 } while (child != dentry->children);
319
320                 /* End-of-directory dentry on disk. */
321                 *subdir_offset_p += 8;
322
323                 /* Recursively call calculate_subdir_offsets() on all the
324                  * children. */
325                 do {
326                         calculate_subdir_offsets(child, subdir_offset_p);
327                         child = child->next;
328                 } while (child != dentry->children);
329         } else {
330                 /* On disk, childless directories have a valid subdir_offset
331                  * that points to an 8-byte end-of-directory dentry.  Regular
332                  * files or reparse points have a subdir_offset of 0. */
333                 if (dentry_is_directory(dentry))
334                         *subdir_offset_p += 8;
335                 else
336                         dentry->subdir_offset = 0;
337         }
338 }
339
340
341 /* Returns the child of @dentry that has the file name @name.  
342  * Returns NULL if no child has the name. */
343 struct dentry *get_dentry_child_with_name(const struct dentry *dentry, 
344                                           const char *name)
345 {
346         struct dentry *child;
347         size_t name_len;
348         
349         child = dentry->children;
350         if (child) {
351                 name_len = strlen(name);
352                 do {
353                         if (dentry_has_name(child, name, name_len))
354                                 return child;
355                         child = child->next;
356                 } while (child != dentry->children);
357         }
358         return NULL;
359 }
360
361 /* Retrieves the dentry that has the UTF-8 @path relative to the dentry
362  * @cur_dir.  Returns NULL if no dentry having the path is found. */
363 static struct dentry *get_dentry_relative_path(struct dentry *cur_dir,
364                                                const char *path)
365 {
366         struct dentry *child;
367         size_t base_len;
368         const char *new_path;
369
370         if (*path == '\0')
371                 return cur_dir;
372
373         child = cur_dir->children;
374         if (child) {
375                 new_path = path_next_part(path, &base_len);
376                 do {
377                         if (dentry_has_name(child, path, base_len))
378                                 return get_dentry_relative_path(child, new_path);
379                         child = child->next;
380                 } while (child != cur_dir->children);
381         }
382         return NULL;
383 }
384
385 /* Returns the dentry corresponding to the UTF-8 @path, or NULL if there is no
386  * such dentry. */
387 struct dentry *get_dentry(WIMStruct *w, const char *path)
388 {
389         struct dentry *root = wim_root_dentry(w);
390         while (*path == '/')
391                 path++;
392         return get_dentry_relative_path(root, path);
393 }
394
395 /* Returns the dentry that corresponds to the parent directory of @path, or NULL
396  * if the dentry is not found. */
397 struct dentry *get_parent_dentry(WIMStruct *w, const char *path)
398 {
399         size_t path_len = strlen(path);
400         char buf[path_len + 1];
401
402         memcpy(buf, path, path_len + 1);
403
404         to_parent_name(buf, path_len);
405
406         return get_dentry(w, buf);
407 }
408
409 /* Prints the full path of a dentry. */
410 int print_dentry_full_path(struct dentry *dentry, void *ignore)
411 {
412         if (dentry->full_path_utf8)
413                 puts(dentry->full_path_utf8);
414         return 0;
415 }
416
417 /* We want to be able to show the names of the file attribute flags that are
418  * set. */
419 struct file_attr_flag {
420         u32 flag;
421         const char *name;
422 };
423 struct file_attr_flag file_attr_flags[] = {
424         {FILE_ATTRIBUTE_READONLY,           "READONLY"},
425         {FILE_ATTRIBUTE_HIDDEN,             "HIDDEN"},
426         {FILE_ATTRIBUTE_SYSTEM,             "SYSTEM"},
427         {FILE_ATTRIBUTE_DIRECTORY,          "DIRECTORY"},
428         {FILE_ATTRIBUTE_ARCHIVE,            "ARCHIVE"},
429         {FILE_ATTRIBUTE_DEVICE,             "DEVICE"},
430         {FILE_ATTRIBUTE_NORMAL,             "NORMAL"},
431         {FILE_ATTRIBUTE_TEMPORARY,          "TEMPORARY"},
432         {FILE_ATTRIBUTE_SPARSE_FILE,        "SPARSE_FILE"},
433         {FILE_ATTRIBUTE_REPARSE_POINT,      "REPARSE_POINT"},
434         {FILE_ATTRIBUTE_COMPRESSED,         "COMPRESSED"},
435         {FILE_ATTRIBUTE_OFFLINE,            "OFFLINE"},
436         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED,"NOT_CONTENT_INDEXED"},
437         {FILE_ATTRIBUTE_ENCRYPTED,          "ENCRYPTED"},
438         {FILE_ATTRIBUTE_VIRTUAL,            "VIRTUAL"},
439 };
440
441 /* Prints a directory entry.  @lookup_table is a pointer to the lookup table, if
442  * available.  If the dentry is unresolved and the lookup table is NULL, the
443  * lookup table entries will not be printed.  Otherwise, they will be. */
444 int print_dentry(struct dentry *dentry, void *lookup_table)
445 {
446         const u8 *hash;
447         struct lookup_table_entry *lte;
448
449         printf("[DENTRY]\n");
450         printf("Length            = %"PRIu64"\n", dentry->length);
451         printf("Attributes        = 0x%x\n", dentry->attributes);
452         for (unsigned i = 0; i < ARRAY_LEN(file_attr_flags); i++)
453                 if (file_attr_flags[i].flag & dentry->attributes)
454                         printf("    FILE_ATTRIBUTE_%s is set\n",
455                                 file_attr_flags[i].name);
456         printf("Security ID       = %d\n", dentry->security_id);
457         printf("Subdir offset     = %"PRIu64"\n", dentry->subdir_offset);
458 #if 0
459         printf("Unused1           = 0x%"PRIu64"\n", dentry->unused1);
460         printf("Unused2           = %"PRIu64"\n", dentry->unused2);
461 #endif
462 #if 0
463         printf("Creation Time     = 0x%"PRIx64"\n");
464         printf("Last Access Time  = 0x%"PRIx64"\n");
465         printf("Last Write Time   = 0x%"PRIx64"\n");
466 #endif
467
468         /* Translate the timestamps into something readable */
469         time_t creat_time = wim_timestamp_to_unix(dentry->creation_time);
470         time_t access_time = wim_timestamp_to_unix(dentry->last_access_time);
471         time_t mod_time = wim_timestamp_to_unix(dentry->last_write_time);
472         printf("Creation Time     = %s", asctime(gmtime(&creat_time)));
473         printf("Last Access Time  = %s", asctime(gmtime(&access_time)));
474         printf("Last Write Time   = %s", asctime(gmtime(&mod_time)));
475
476         printf("Reparse Tag       = 0x%"PRIx32"\n", dentry->reparse_tag);
477         printf("Hard Link Group   = 0x%"PRIx64"\n", dentry->hard_link);
478         printf("Number of Alternate Data Streams = %hu\n", dentry->num_ads);
479         printf("Filename          = \"");
480         print_string(dentry->file_name, dentry->file_name_len);
481         puts("\"");
482         printf("Filename Length   = %hu\n", dentry->file_name_len);
483         printf("Filename (UTF-8)  = \"%s\"\n", dentry->file_name_utf8);
484         printf("Filename (UTF-8) Length = %hu\n", dentry->file_name_utf8_len);
485         printf("Short Name        = \"");
486         print_string(dentry->short_name, dentry->short_name_len);
487         puts("\"");
488         printf("Short Name Length = %hu\n", dentry->short_name_len);
489         printf("Full Path (UTF-8) = \"%s\"\n", dentry->full_path_utf8);
490         lte = dentry_stream_lte(dentry, 0, lookup_table);
491         if (lte) {
492                 print_lookup_table_entry(lte);
493         } else {
494                 hash = dentry_stream_hash(dentry, 0);
495                 if (hash) {
496                         printf("Hash              = 0x"); 
497                         print_hash(hash);
498                         putchar('\n');
499                         putchar('\n');
500                 }
501         }
502         for (u16 i = 0; i < dentry->num_ads; i++) {
503                 printf("[Alternate Stream Entry %u]\n", i);
504                 printf("Name = \"%s\"\n", dentry->ads_entries[i].stream_name_utf8);
505                 printf("Name Length (UTF-16) = %u\n",
506                                 dentry->ads_entries[i].stream_name_len);
507                 hash = dentry_stream_hash(dentry, i + 1);
508                 if (hash) {
509                         printf("Hash              = 0x"); 
510                         print_hash(hash);
511                         putchar('\n');
512                 }
513                 print_lookup_table_entry(dentry_stream_lte(dentry, i + 1,
514                                                            lookup_table));
515         }
516         return 0;
517 }
518
519 /* Initializations done on every `struct dentry'. */
520 static void dentry_common_init(struct dentry *dentry)
521 {
522         memset(dentry, 0, sizeof(struct dentry));
523         dentry->refcnt = 1;
524         dentry->security_id = -1;
525         dentry->ads_entries_status = ADS_ENTRIES_DEFAULT;
526         dentry->lte_group_list.type = STREAM_TYPE_NORMAL;
527 }
528
529 /* 
530  * Creates an unlinked directory entry.
531  *
532  * @name:  The UTF-8 filename of the new dentry.
533  *
534  * Returns a pointer to the new dentry, or NULL if out of memory.
535  */
536 struct dentry *new_dentry(const char *name)
537 {
538         struct dentry *dentry;
539         
540         dentry = MALLOC(sizeof(struct dentry));
541         if (!dentry)
542                 goto err;
543
544         dentry_common_init(dentry);
545         if (change_dentry_name(dentry, name) != 0)
546                 goto err;
547
548         dentry_update_all_timestamps(dentry);
549         dentry->next   = dentry;
550         dentry->prev   = dentry;
551         dentry->parent = dentry;
552         INIT_LIST_HEAD(&dentry->link_group_list);
553         return dentry;
554 err:
555         FREE(dentry);
556         ERROR("Failed to allocate new dentry");
557         return NULL;
558 }
559
560 void dentry_free_ads_entries(struct dentry *dentry)
561 {
562         for (u16 i = 0; i < dentry->num_ads; i++)
563                 destroy_ads_entry(&dentry->ads_entries[i]);
564         FREE(dentry->ads_entries);
565         dentry->ads_entries = NULL;
566         dentry->num_ads = 0;
567 }
568
569 static void __destroy_dentry(struct dentry *dentry)
570 {
571         FREE(dentry->file_name);
572         FREE(dentry->file_name_utf8);
573         FREE(dentry->short_name);
574         FREE(dentry->full_path_utf8);
575         FREE(dentry->extracted_file);
576 }
577
578 /* Frees a WIM dentry. */
579 void free_dentry(struct dentry *dentry)
580 {
581         wimlib_assert(dentry);
582         __destroy_dentry(dentry);
583         /* Don't destroy the ADS entries if they "belong" to a different dentry
584          * */
585         if (dentry->ads_entries_status != ADS_ENTRIES_USER)
586                 dentry_free_ads_entries(dentry);
587         FREE(dentry);
588 }
589
590 /* Like free_dentry(), but assigns a new ADS entries owner if this dentry was
591  * the previous owner, and also deletes the dentry from its link_group_list */
592 void put_dentry(struct dentry *dentry)
593 {
594         if (dentry->ads_entries_status == ADS_ENTRIES_OWNER) {
595                 struct dentry *new_owner;
596                 list_for_each_entry(new_owner, &dentry->link_group_list,
597                                     link_group_list)
598                 {
599                         if (new_owner->ads_entries_status == ADS_ENTRIES_USER) {
600                                 new_owner->ads_entries_status = ADS_ENTRIES_OWNER;
601                                 break;
602                         }
603                 }
604                 dentry->ads_entries_status = ADS_ENTRIES_USER;
605         }
606         struct list_head *next;
607         list_del(&dentry->link_group_list);
608         free_dentry(dentry);
609 }
610
611
612 /* Partically clones a dentry.
613  *
614  * Beware:
615  *      - memory for file names is not cloned (the pointers are all set to NULL
616  *        and the lengths are set to zero)
617  *      - next, prev, and children pointers and not touched
618  *      - stream entries are not cloned (pointer left untouched).
619  */
620 struct dentry *clone_dentry(struct dentry *old)
621 {
622         struct dentry *new = MALLOC(sizeof(struct dentry));
623         if (!new)
624                 return NULL;
625         memcpy(new, old, sizeof(struct dentry));
626         new->file_name          = NULL;
627         new->file_name_len      = 0;
628         new->file_name_utf8     = NULL;
629         new->file_name_utf8_len = 0;
630         new->short_name         = NULL;
631         new->short_name_len     = 0;
632         return new;
633 }
634
635 /* 
636  * This function is passed as an argument to for_dentry_in_tree_depth() in order
637  * to free a directory tree.  __args is a pointer to a `struct free_dentry_args'.
638  */
639 static int do_free_dentry(struct dentry *dentry, void *__lookup_table)
640 {
641         struct lookup_table *lookup_table = __lookup_table;
642         struct lookup_table_entry *lte;
643         unsigned i;
644
645         if (lookup_table) {
646                 for (i = 0; i <= dentry->num_ads; i++) {
647                         lte = dentry_stream_lte(dentry, i, lookup_table);
648                         lte_decrement_refcnt(lte, lookup_table);
649                 }
650         }
651
652         wimlib_assert(dentry->refcnt != 0);
653         if (--dentry->refcnt == 0)
654                 free_dentry(dentry);
655         return 0;
656 }
657
658 /* 
659  * Unlinks and frees a dentry tree.
660  *
661  * @root:               The root of the tree.
662  * @lookup_table:       The lookup table for dentries.  If non-NULL, the
663  *                      reference counts in the lookup table for the lookup
664  *                      table entries corresponding to the dentries will be
665  *                      decremented.
666  */
667 void free_dentry_tree(struct dentry *root, struct lookup_table *lookup_table)
668 {
669         if (!root || !root->parent)
670                 return;
671         for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
672 }
673
674 int increment_dentry_refcnt(struct dentry *dentry, void *ignore)
675 {
676         dentry->refcnt++;
677         return 0;
678 }
679
680 /* 
681  * Links a dentry into the directory tree.
682  *
683  * @dentry: The dentry to link.
684  * @parent: The dentry that will be the parent of @dentry.
685  */
686 void link_dentry(struct dentry *dentry, struct dentry *parent)
687 {
688         wimlib_assert(dentry_is_directory(parent));
689         dentry->parent = parent;
690         if (parent->children) {
691                 /* Not an only child; link to siblings. */
692                 dentry->next = parent->children;
693                 dentry->prev = parent->children->prev;
694                 dentry->next->prev = dentry;
695                 dentry->prev->next = dentry;
696         } else {
697                 /* Only child; link to parent. */
698                 parent->children = dentry;
699                 dentry->next = dentry;
700                 dentry->prev = dentry;
701         }
702 }
703
704
705 /* Unlink a dentry from the directory tree. 
706  *
707  * Note: This merely removes it from the in-memory tree structure.  See
708  * remove_dentry() in mount.c for a function implemented on top of this one that
709  * frees the dentry and implements reference counting for the lookup table
710  * entries. */
711 void unlink_dentry(struct dentry *dentry)
712 {
713         if (dentry_is_root(dentry))
714                 return;
715         if (dentry_is_only_child(dentry)) {
716                 dentry->parent->children = NULL;
717         } else {
718                 if (dentry_is_first_sibling(dentry))
719                         dentry->parent->children = dentry->next;
720                 dentry->next->prev = dentry->prev;
721                 dentry->prev->next = dentry->next;
722         }
723 }
724
725
726 /* Recalculates the length of @dentry based on its file name length and short
727  * name length.  */
728 static inline void recalculate_dentry_size(struct dentry *dentry)
729 {
730         dentry->length = WIM_DENTRY_DISK_SIZE + dentry->file_name_len + 
731                          2 + dentry->short_name_len;
732         /* Must be multiple of 8. */
733         dentry->length = (dentry->length + 7) & ~7;
734 }
735
736 /* Duplicates a UTF-8 name into UTF-8 and UTF-16 strings and returns the strings
737  * and their lengths in the pointer arguments */
738 int get_names(char **name_utf16_ret, char **name_utf8_ret,
739               u16 *name_utf16_len_ret, u16 *name_utf8_len_ret,
740               const char *name)
741 {
742         size_t utf8_len;
743         size_t utf16_len;
744         char *name_utf16, *name_utf8;
745
746         utf8_len = strlen(name);
747
748         name_utf16 = utf8_to_utf16(name, utf8_len, &utf16_len);
749
750         if (!name_utf16)
751                 return WIMLIB_ERR_NOMEM;
752
753         name_utf8 = MALLOC(utf8_len + 1);
754         if (!name_utf8) {
755                 FREE(name_utf8);
756                 return WIMLIB_ERR_NOMEM;
757         }
758         memcpy(name_utf8, name, utf8_len + 1);
759         FREE(*name_utf8_ret);
760         FREE(*name_utf16_ret);
761         *name_utf8_ret      = name_utf8;
762         *name_utf16_ret     = name_utf16;
763         *name_utf8_len_ret  = utf8_len;
764         *name_utf16_len_ret = utf16_len;
765         return 0;
766 }
767
768 /* Changes the name of a dentry to @new_name.  Only changes the file_name and
769  * file_name_utf8 fields; does not change the short_name, short_name_utf8, or
770  * full_path_utf8 fields.  Also recalculates its length. */
771 int change_dentry_name(struct dentry *dentry, const char *new_name)
772 {
773         int ret;
774
775         ret = get_names(&dentry->file_name, &dentry->file_name_utf8,
776                         &dentry->file_name_len, &dentry->file_name_utf8_len,
777                          new_name);
778         if (ret == 0)
779                 recalculate_dentry_size(dentry);
780         return ret;
781 }
782
783 /*
784  * Changes the name of an alternate data stream */
785 int change_ads_name(struct ads_entry *entry, const char *new_name)
786 {
787         return get_names(&entry->stream_name, &entry->stream_name_utf8,
788                          &entry->stream_name_len,
789                          &entry->stream_name_utf8_len,
790                          new_name);
791 }
792
793 /* Parameters for calculate_dentry_statistics(). */
794 struct image_statistics {
795         struct lookup_table *lookup_table;
796         u64 *dir_count;
797         u64 *file_count;
798         u64 *total_bytes;
799         u64 *hard_link_bytes;
800 };
801
802 static int calculate_dentry_statistics(struct dentry *dentry, void *arg)
803 {
804         struct image_statistics *stats;
805         struct lookup_table_entry *lte; 
806         
807         stats = arg;
808
809         if (dentry_is_directory(dentry) && !dentry_is_root(dentry))
810                 ++*stats->dir_count;
811         else
812                 ++*stats->file_count;
813
814         for (unsigned i = 0; i <= dentry->num_ads; i++) {
815                 lte = dentry_stream_lte(dentry, i, stats->lookup_table);
816                 if (lte) {
817                         *stats->total_bytes += wim_resource_size(lte);
818                         if (++lte->out_refcnt == 1)
819                                 *stats->hard_link_bytes += wim_resource_size(lte);
820                 }
821         }
822         return 0;
823 }
824
825 /* Calculates some statistics about a dentry tree. */
826 void calculate_dir_tree_statistics(struct dentry *root, struct lookup_table *table, 
827                                    u64 *dir_count_ret, u64 *file_count_ret, 
828                                    u64 *total_bytes_ret, 
829                                    u64 *hard_link_bytes_ret)
830 {
831         struct image_statistics stats;
832         *dir_count_ret         = 0;
833         *file_count_ret        = 0;
834         *total_bytes_ret       = 0;
835         *hard_link_bytes_ret   = 0;
836         stats.lookup_table     = table;
837         stats.dir_count       = dir_count_ret;
838         stats.file_count      = file_count_ret;
839         stats.total_bytes     = total_bytes_ret;
840         stats.hard_link_bytes = hard_link_bytes_ret;
841         for_lookup_table_entry(table, zero_out_refcnts, NULL);
842         for_dentry_in_tree(root, calculate_dentry_statistics, &stats);
843 }
844
845
846 /* 
847  * Reads the alternate data stream entries for a dentry.
848  *
849  * @p:  Pointer to buffer that starts with the first alternate stream entry.
850  *
851  * @dentry:     Dentry to load the alternate data streams into.
852  *                      @dentry->num_ads must have been set to the number of
853  *                      data streams that are expected.
854  *
855  * @remaining_size:     Number of bytes of data remaining in the buffer pointed
856  *                              to by @p.
857  *
858  * The format of the on-disk alternate stream entries is as follows:
859  *
860  * struct ads_entry_on_disk {
861  *      u64  length;          // Length of the entry, in bytes
862  *      u64  reserved;        // Seems to be unused
863  *      u8   hash[20];        // SHA1 message digest of the uncompressed stream
864  *      u16  stream_name_len; // Length of the stream name, in bytes
865  *      char stream_name[];   // Stream name in UTF-16LE, @stream_name_len bytes long,
866  *                            //    not including null terminator
867  *      u16  zero;            // UTF-16 null terminator for the stream name, NOT
868  *                            //    included in @stream_name_len
869  * };
870  *
871  * In addition, the entries are 8-byte aligned.
872  *
873  * Return 0 on success or nonzero on failure.  On success, dentry->ads_entries
874  * is set to an array of `struct ads_entry's of length dentry->num_ads.  On
875  * failure, @dentry is not modified.
876  */
877 static int read_ads_entries(const u8 *p, struct dentry *dentry,
878                             u64 remaining_size)
879 {
880         u16 num_ads;
881         struct ads_entry *ads_entries;
882         int ret;
883
884         num_ads = dentry->num_ads;
885         ads_entries = CALLOC(num_ads, sizeof(struct ads_entry));
886         if (!ads_entries) {
887                 ERROR("Could not allocate memory for %"PRIu16" "
888                       "alternate data stream entries", num_ads);
889                 return WIMLIB_ERR_NOMEM;
890         }
891
892         for (u16 i = 0; i < num_ads; i++) {
893                 struct ads_entry *cur_entry = &ads_entries[i];
894                 u64 length;
895                 size_t utf8_len;
896                 const char *p_save = p;
897
898                 /* Read the base stream entry, excluding the stream name. */
899                 if (remaining_size < WIM_ADS_ENTRY_DISK_SIZE) {
900                         ERROR("Stream entries go past end of metadata resource");
901                         ERROR("(remaining_size = %"PRIu64")", remaining_size);
902                         ret = WIMLIB_ERR_INVALID_DENTRY;
903                         goto out_free_ads_entries;
904                 }
905                 remaining_size -= WIM_ADS_ENTRY_DISK_SIZE;
906
907                 p = get_u64(p, &length); /* ADS entry length */
908                 p += 8; /* Unused */
909                 p = get_bytes(p, SHA1_HASH_SIZE, (u8*)cur_entry->hash);
910                 p = get_u16(p, &cur_entry->stream_name_len);
911
912                 cur_entry->stream_name = NULL;
913                 cur_entry->stream_name_utf8 = NULL;
914
915                 if (remaining_size < cur_entry->stream_name_len + 2) {
916                         ERROR("Stream entries go past end of metadata resource");
917                         ERROR("(remaining_size = %"PRIu64" bytes, stream_name_len "
918                               "= %"PRIu16" bytes", remaining_size,
919                               cur_entry->stream_name_len);
920                         ret = WIMLIB_ERR_INVALID_DENTRY;
921                         goto out_free_ads_entries;
922                 }
923                 remaining_size -= cur_entry->stream_name_len + 2;
924
925                 cur_entry->stream_name = MALLOC(cur_entry->stream_name_len);
926                 if (!cur_entry->stream_name) {
927                         ret = WIMLIB_ERR_NOMEM;
928                         goto out_free_ads_entries;
929                 }
930                 get_bytes(p, cur_entry->stream_name_len,
931                           (u8*)cur_entry->stream_name);
932                 cur_entry->stream_name_utf8 = utf16_to_utf8(cur_entry->stream_name,
933                                                             cur_entry->stream_name_len,
934                                                             &utf8_len);
935                 cur_entry->stream_name_utf8_len = utf8_len;
936
937                 if (!cur_entry->stream_name_utf8) {
938                         ret = WIMLIB_ERR_NOMEM;
939                         goto out_free_ads_entries;
940                 }
941                 p = p_save + ads_entry_total_length(cur_entry);
942         }
943         dentry->ads_entries = ads_entries;
944         return 0;
945 out_free_ads_entries:
946         for (u16 i = 0; i < num_ads; i++) {
947                 FREE(ads_entries[i].stream_name);
948                 FREE(ads_entries[i].stream_name_utf8);
949         }
950         FREE(ads_entries);
951         return ret;
952 }
953
954 /* 
955  * Reads a directory entry, including all alternate data stream entries that
956  * follow it, from the WIM image's metadata resource.
957  *
958  * @metadata_resource:  Buffer containing the uncompressed metadata resource.
959  * @metadata_resource_len:   Length of the metadata resource.
960  * @offset:     Offset of this directory entry in the metadata resource.
961  * @dentry:     A `struct dentry' that will be filled in by this function.
962  *
963  * Return 0 on success or nonzero on failure.  On failure, @dentry have been
964  * modified, bu it will be left with no pointers to any allocated buffers.
965  * On success, the dentry->length field must be examined.  If zero, this was a
966  * special "end of directory" dentry and not a real dentry.  If nonzero, this
967  * was a real dentry.
968  */
969 int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len, 
970                 u64 offset, struct dentry *dentry)
971 {
972         const u8 *p;
973         u64 calculated_size;
974         char *file_name;
975         char *file_name_utf8;
976         char *short_name;
977         u16 short_name_len;
978         u16 file_name_len;
979         size_t file_name_utf8_len;
980         int ret;
981
982         dentry_common_init(dentry);
983
984         /*Make sure the dentry really fits into the metadata resource.*/
985         if (offset + 8 > metadata_resource_len) {
986                 ERROR("Directory entry starting at %"PRIu64" ends past the "
987                       "end of the metadata resource (size %"PRIu64")",
988                       offset, metadata_resource_len);
989                 return WIMLIB_ERR_INVALID_DENTRY;
990         }
991
992         /* Before reading the whole dentry, we need to read just the length.
993          * This is because a dentry of length 8 (that is, just the length field)
994          * terminates the list of sibling directory entries. */
995
996         p = get_u64(&metadata_resource[offset], &dentry->length);
997
998         /* A zero length field (really a length of 8, since that's how big the
999          * directory entry is...) indicates that this is the end of directory
1000          * dentry.  We do not read it into memory as an actual dentry, so just
1001          * return successfully in that case. */
1002         if (dentry->length == 0)
1003                 return 0;
1004
1005         /* If the dentry does not overflow the metadata resource buffer and is
1006          * not too short, read the rest of it (excluding the alternate data
1007          * streams, but including the file name and short name variable-length
1008          * fields) into memory. */
1009         if (offset + dentry->length >= metadata_resource_len) {
1010                 ERROR("Directory entry at offset %"PRIu64" and with size "
1011                       "%"PRIu64" ends past the end of the metadata resource "
1012                       "(size %"PRIu64")",
1013                       offset, dentry->length, metadata_resource_len);
1014                 return WIMLIB_ERR_INVALID_DENTRY;
1015         }
1016
1017         if (dentry->length < WIM_DENTRY_DISK_SIZE) {
1018                 ERROR("Directory entry has invalid length of %"PRIu64" bytes",
1019                       dentry->length);
1020                 return WIMLIB_ERR_INVALID_DENTRY;
1021         }
1022
1023         p = get_u32(p, &dentry->attributes);
1024         p = get_u32(p, (u32*)&dentry->security_id);
1025         p = get_u64(p, &dentry->subdir_offset);
1026
1027         /* 2 unused fields */
1028         p += 2 * sizeof(u64);
1029         /*p = get_u64(p, &dentry->unused1);*/
1030         /*p = get_u64(p, &dentry->unused2);*/
1031
1032         p = get_u64(p, &dentry->creation_time);
1033         p = get_u64(p, &dentry->last_access_time);
1034         p = get_u64(p, &dentry->last_write_time);
1035
1036         p = get_bytes(p, SHA1_HASH_SIZE, dentry->hash);
1037         
1038         /*
1039          * I don't know what's going on here.  It seems like M$ screwed up the
1040          * reparse points, then put the fields in the same place and didn't
1041          * document it.  The WIM_HDR_FLAG_RP_FIX flag in the WIM header might
1042          * have something to do with this, but it's not documented.
1043          */
1044         if (dentry->attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1045                 /* ??? */
1046                 p += 4;
1047                 p = get_u32(p, &dentry->reparse_tag);
1048                 p += 4;
1049         } else {
1050                 p = get_u32(p, &dentry->reparse_tag);
1051                 p = get_u64(p, &dentry->hard_link);
1052         }
1053
1054         /* By the way, the reparse_reserved field does not actually exist (at
1055          * least when the file is not a reparse point) */
1056         
1057         p = get_u16(p, &dentry->num_ads);
1058
1059         p = get_u16(p, &short_name_len);
1060         p = get_u16(p, &file_name_len);
1061
1062         /* We now know the length of the file name and short name.  These should
1063          * be included in the dentry length, but make sure the numbers are
1064          * consistent. */
1065         calculated_size = WIM_DENTRY_DISK_SIZE + file_name_len + 2 +
1066                           short_name_len;
1067
1068         if (dentry->length < calculated_size) {
1069                 ERROR("Unexpected end of directory entry! (Expected "
1070                       "%"PRIu64" bytes, got %"PRIu64" bytes. "
1071                       "short_name_len = %hu, file_name_len = %hu)", 
1072                       calculated_size, dentry->length,
1073                       short_name_len, file_name_len);
1074                 return WIMLIB_ERR_INVALID_DENTRY;
1075         }
1076
1077         /* Read the filename. */
1078         file_name = MALLOC(file_name_len);
1079         if (!file_name) {
1080                 ERROR("Failed to allocate %hu bytes for dentry file name",
1081                       file_name_len);
1082                 return WIMLIB_ERR_NOMEM;
1083         }
1084         p = get_bytes(p, file_name_len, file_name);
1085
1086         /* Convert filename to UTF-8. */
1087         file_name_utf8 = utf16_to_utf8(file_name, file_name_len, 
1088                                        &file_name_utf8_len);
1089
1090         if (!file_name_utf8) {
1091                 ERROR("Failed to allocate memory to convert UTF-16 "
1092                       "filename (%hu bytes) to UTF-8", file_name_len);
1093                 ret = WIMLIB_ERR_NOMEM;
1094                 goto out_free_file_name;
1095         }
1096
1097         /* Undocumented padding between file name and short name.  This probably
1098          * is supposed to be a terminating null character. */
1099         p += 2;
1100
1101         /* Read the short filename. */
1102         short_name = MALLOC(short_name_len);
1103         if (!short_name) {
1104                 ERROR("Failed to allocate %hu bytes for short filename",
1105                       short_name_len);
1106                 ret = WIMLIB_ERR_NOMEM;
1107                 goto out_free_file_name_utf8;
1108         }
1109
1110         p = get_bytes(p, short_name_len, short_name);
1111
1112         /* Some directory entries inexplicably have a little over 70 bytes of
1113          * extra data.  The exact amount of data seems to be 72 bytes, but it is
1114          * aligned on the next 8-byte boundary.  It does NOT seem to be
1115          * alternate data stream entries.  Here's an example of the aligned
1116          * data:
1117          *
1118          * 01000000 40000000 6c786bba c58ede11 b0bb0026 1870892a b6adb76f
1119          * e63a3e46 8fca8653 0d2effa1 6c786bba c58ede11 b0bb0026 1870892a
1120          * 00000000 00000000 00000000 00000000
1121          *
1122          * Here's one interpretation of how the data is laid out.
1123          *
1124          * struct unknown {
1125          *      u32 field1; (always 0x00000001)
1126          *      u32 field2; (always 0x40000000)
1127          *      u8  data[48]; (???)
1128          *      u64 reserved1; (always 0)
1129          *      u64 reserved2; (always 0)
1130          * };*/
1131 #if 0
1132         if (dentry->length - calculated_size >= WIM_ADS_ENTRY_DISK_SIZE) {
1133                 printf("%s: %lu / %lu (", file_name_utf8, 
1134                                 calculated_size, dentry->length);
1135                 print_string(p + WIM_ADS_ENTRY_DISK_SIZE, dentry->length - calculated_size - WIM_ADS_ENTRY_DISK_SIZE);
1136                 puts(")");
1137                 print_byte_field(p, dentry->length - calculated_size);
1138                 putchar('\n');
1139         }
1140 #endif
1141
1142         /* 
1143          * Read the alternate data streams, if present.  dentry->num_ads tells
1144          * us how many they are, and they will directly follow the dentry
1145          * on-disk.
1146          *
1147          * Note that each alternate data stream entry begins on an 8-byte
1148          * aligned boundary, and the alternate data stream entries are NOT
1149          * included in the dentry->length field for some reason.
1150          */
1151         if (dentry->num_ads != 0) {
1152                 calculated_size = (calculated_size + 7) & ~7;
1153                 if (calculated_size > metadata_resource_len - offset) {
1154                         ERROR("Not enough space in metadata resource for "
1155                               "alternate stream entries");
1156                         ret = WIMLIB_ERR_INVALID_DENTRY;
1157                         goto out_free_short_name;
1158                 }
1159                 ret = read_ads_entries(&metadata_resource[offset + calculated_size],
1160                                        dentry,
1161                                        metadata_resource_len - offset - calculated_size);
1162                 if (ret != 0)
1163                         goto out_free_short_name;
1164         }
1165
1166         /* We've read all the data for this dentry.  Set the names and their
1167          * lengths, and we've done. */
1168         dentry->file_name          = file_name;
1169         dentry->file_name_utf8     = file_name_utf8;
1170         dentry->short_name         = short_name;
1171         dentry->file_name_len      = file_name_len;
1172         dentry->file_name_utf8_len = file_name_utf8_len;
1173         dentry->short_name_len     = short_name_len;
1174         return 0;
1175 out_free_short_name:
1176         FREE(short_name);
1177 out_free_file_name_utf8:
1178         FREE(file_name_utf8);
1179 out_free_file_name:
1180         FREE(file_name);
1181         return ret;
1182 }
1183
1184 /* 
1185  * Writes a WIM dentry to an output buffer.
1186  *
1187  * @dentry:  The dentry structure.
1188  * @p:       The memory location to write the data to.
1189  * @return:  Pointer to the byte after the last byte we wrote as part of the
1190  *              dentry.
1191  */
1192 static u8 *write_dentry(const struct dentry *dentry, u8 *p)
1193 {
1194         u8 *orig_p = p;
1195         unsigned padding;
1196         const u8 *hash;
1197
1198         p = put_u64(p, dentry->length);
1199         p = put_u32(p, dentry->attributes);
1200         p = put_u32(p, dentry->security_id);
1201         p = put_u64(p, dentry->subdir_offset);
1202         p = put_u64(p, 0); /* unused1 */
1203         p = put_u64(p, 0); /* unused2 */
1204         p = put_u64(p, dentry->creation_time);
1205         p = put_u64(p, dentry->last_access_time);
1206         p = put_u64(p, dentry->last_write_time);
1207         if (dentry->resolved && dentry->lte)
1208                 hash = dentry->lte->hash;
1209         else
1210                 hash = dentry->hash;
1211         p = put_bytes(p, SHA1_HASH_SIZE, hash);
1212         if (dentry->attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1213                 p = put_zeroes(p, 4);
1214                 p = put_u32(p, dentry->reparse_tag);
1215                 p = put_zeroes(p, 4);
1216         } else {
1217                 u64 hard_link;
1218                 p = put_u32(p, 0);
1219                 if (dentry->link_group_list.next == &dentry->link_group_list)
1220                         hard_link = 0;
1221                 else
1222                         hard_link = dentry->hard_link;
1223                 p = put_u64(p, hard_link);
1224         }
1225         p = put_u16(p, dentry->num_ads);
1226         p = put_u16(p, dentry->short_name_len);
1227         p = put_u16(p, dentry->file_name_len);
1228         p = put_bytes(p, dentry->file_name_len, (u8*)dentry->file_name);
1229         p = put_u16(p, 0); /* filename padding, 2 bytes. */
1230         p = put_bytes(p, dentry->short_name_len, (u8*)dentry->short_name);
1231
1232         wimlib_assert(p - orig_p <= dentry->length);
1233         if (p - orig_p < dentry->length)
1234                 p = put_zeroes(p, dentry->length - (p - orig_p));
1235
1236         /* Align to 8-byte boundary */
1237         p = put_zeroes(p, (8 - dentry->length % 8) % 8);
1238
1239         /* Write the alternate data streams, if there are any.  Please see
1240          * read_ads_entries() for comments about the format of the on-disk
1241          * alternate data stream entries. */
1242         for (u16 i = 0; i < dentry->num_ads; i++) {
1243                 p = put_u64(p, ads_entry_total_length(&dentry->ads_entries[i]));
1244                 p = put_u64(p, 0); /* Unused */
1245                 if (dentry->resolved && dentry->ads_entries[i].lte)
1246                         hash = dentry->ads_entries[i].lte->hash;
1247                 else
1248                         hash = dentry->ads_entries[i].hash;
1249                 p = put_bytes(p, SHA1_HASH_SIZE, hash);
1250                 p = put_u16(p, dentry->ads_entries[i].stream_name_len);
1251                 p = put_bytes(p, dentry->ads_entries[i].stream_name_len,
1252                                  (u8*)dentry->ads_entries[i].stream_name);
1253                 p = put_u16(p, 0);
1254                 p = put_zeroes(p, (8 - (p - orig_p) % 8) % 8);
1255         }
1256         return p;
1257 }
1258
1259 /* Recursive function that writes a dentry tree rooted at @parent, not including
1260  * @parent itself, which has already been written. */
1261 static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p)
1262 {
1263         const struct dentry *child;
1264
1265         /* Nothing to do if this dentry has no children. */
1266         if (parent->subdir_offset == 0)
1267                 return p;
1268
1269         /* Write child dentries and end-of-directory entry. 
1270          *
1271          * Note: we need to write all of this dentry's children before
1272          * recursively writing the directory trees rooted at each of the child
1273          * dentries, since the on-disk dentries for a dentry's children are
1274          * always located at consecutive positions in the metadata resource! */
1275         child = parent->children;
1276         if (child) {
1277                 do {
1278                         p = write_dentry(child, p);
1279                         child = child->next;
1280                 } while (child != parent->children);
1281         }
1282
1283         /* write end of directory entry */
1284         p = put_u64(p, 0);
1285
1286         /* Recurse on children. */
1287         if (child) {
1288                 do {
1289                         p = write_dentry_tree_recursive(child, p);
1290                         child = child->next;
1291                 } while (child != parent->children);
1292         }
1293         return p;
1294 }
1295
1296 /* Writes a directory tree to the metadata resource.
1297  *
1298  * @root:       Root of the dentry tree.
1299  * @p:          Pointer to a buffer with enough space for the dentry tree.
1300  *
1301  * Returns pointer to the byte after the last byte we wrote.
1302  */
1303 u8 *write_dentry_tree(const struct dentry *root, u8 *p)
1304 {
1305         wimlib_assert(dentry_is_root(root));
1306
1307         /* If we're the root dentry, we have no parent that already
1308          * wrote us, so we need to write ourselves. */
1309         p = write_dentry(root, p);
1310
1311         /* Write end of directory entry after the root dentry just to be safe;
1312          * however the root dentry obviously cannot have any siblings. */
1313         p = put_u64(p, 0);
1314
1315         /* Recursively write the rest of the dentry tree. */
1316         return write_dentry_tree_recursive(root, p);
1317 }
1318
1319 /* Reads the children of a dentry, and all their children, ..., etc. from the
1320  * metadata resource and into the dentry tree.
1321  *
1322  * @metadata_resource:  An array that contains the uncompressed metadata
1323  *                      resource for the WIM file.
1324  *
1325  * @metadata_resource_len:  The length of the uncompressed metadata resource, in
1326  *                          bytes.
1327  *
1328  * @dentry:     A pointer to a `struct dentry' that is the root of the directory
1329  *              tree and has already been read from the metadata resource.  It
1330  *              does not need to be the real root because this procedure is
1331  *              called recursively.
1332  *
1333  * @return:     Zero on success, nonzero on failure.
1334  */
1335 int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
1336                      struct dentry *dentry)
1337 {
1338         u64 cur_offset = dentry->subdir_offset;
1339         struct dentry *prev_child = NULL;
1340         struct dentry *first_child = NULL;
1341         struct dentry *child;
1342         struct dentry cur_child;
1343         int ret;
1344
1345         /* 
1346          * If @dentry has no child dentries, nothing more needs to be done for
1347          * this branch.  This is the case for regular files, symbolic links, and
1348          * *possibly* empty directories (although an empty directory may also
1349          * have one child dentry that is the special end-of-directory dentry)
1350          */
1351         if (cur_offset == 0)
1352                 return 0;
1353
1354         /* Find and read all the children of @dentry. */
1355         while (1) {
1356
1357                 /* Read next child of @dentry into @cur_child. */
1358                 ret = read_dentry(metadata_resource, metadata_resource_len, 
1359                                   cur_offset, &cur_child);
1360                 if (ret != 0)
1361                         break;
1362
1363                 /* Check for end of directory. */
1364                 if (cur_child.length == 0)
1365                         break;
1366
1367                 /* Not end of directory.  Allocate this child permanently and
1368                  * link it to the parent and previous child. */
1369                 child = MALLOC(sizeof(struct dentry));
1370                 if (!child) {
1371                         ERROR("Failed to allocate %zu bytes for new dentry",
1372                               sizeof(struct dentry));
1373                         ret = WIMLIB_ERR_NOMEM;
1374                         break;
1375                 }
1376                 memcpy(child, &cur_child, sizeof(struct dentry));
1377
1378                 if (prev_child) {
1379                         prev_child->next = child;
1380                         child->prev = prev_child;
1381                 } else {
1382                         first_child = child;
1383                 }
1384
1385                 child->parent = dentry;
1386                 prev_child = child;
1387
1388                 /* If there are children of this child, call this procedure
1389                  * recursively. */
1390                 if (child->subdir_offset != 0) {
1391                         ret = read_dentry_tree(metadata_resource, 
1392                                                metadata_resource_len, child);
1393                         if (ret != 0)
1394                                 break;
1395                 }
1396
1397                 /* Advance to the offset of the next child. */
1398                 cur_offset += dentry_total_length(child);
1399         }
1400
1401         /* Link last child to first one, and set parent's children pointer to
1402          * the first child.  */
1403         if (prev_child) {
1404                 prev_child->next = first_child;
1405                 first_child->prev = prev_child;
1406         }
1407         dentry->children = first_child;
1408         return ret;
1409 }