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