wimlib.net Git - wimlib/blob - src/dentry.c

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