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