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