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