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->link_count != 0);
 957         if (--inode->link_count == 0) {
 958         #ifdef WITH_FUSE
 959                 if (inode->num_opened_fds == 0)
 960         #endif
 961                 {
 962                         free_inode(inode);
 963                 }
 964         }
 965 }
 966
 967 /* Frees a WIM dentry.
 968  *
 969  * The inode is freed only if its link count is decremented to 0.
 970  */
 971 void free_dentry(struct dentry *dentry)
 972 {
 973         FREE(dentry->file_name);
 974         FREE(dentry->file_name_utf8);
 975         FREE(dentry->short_name);
 976         FREE(dentry->full_path_utf8);
 977         if (dentry->d_inode)
 978                 put_inode(dentry->d_inode);
 979         FREE(dentry);
 980 }
 981
 982 void put_dentry(struct dentry *dentry)
 983 {
 984         wimlib_assert(dentry->refcnt != 0);
 985         if (--dentry->refcnt == 0)
 986                 free_dentry(dentry);
 987 }
 988
 989 /*
 990  * This function is passed as an argument to for_dentry_in_tree_depth() in order
 991  * to free a directory tree.  __args is a pointer to a `struct free_dentry_args'.
 992  */
 993 static int do_free_dentry(struct dentry *dentry, void *__lookup_table)
 994 {
 995         struct lookup_table *lookup_table = __lookup_table;
 996         unsigned i;
 997
 998         if (lookup_table) {
 999                 struct lookup_table_entry *lte;
1000                 struct inode *inode = dentry->d_inode;
1001                 wimlib_assert(inode->link_count != 0);
1002                 for (i = 0; i <= inode->num_ads; i++) {
1003                         lte = inode_stream_lte(inode, i, lookup_table);
1004                         if (lte)
1005                                 lte_decrement_refcnt(lte, lookup_table);
1006                 }
1007         }
1008
1009         put_dentry(dentry);
1010         return 0;
1011 }
1012
1013 /*
1014  * Unlinks and frees a dentry tree.
1015  *
1016  * @root:               The root of the tree.
1017  * @lookup_table:       The lookup table for dentries.  If non-NULL, the
1018  *                      reference counts in the lookup table for the lookup
1019  *                      table entries corresponding to the dentries will be
1020  *                      decremented.
1021  */
1022 void free_dentry_tree(struct dentry *root, struct lookup_table *lookup_table)
1023 {
1024         if (root)
1025                 for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
1026 }
1027
1028 int increment_dentry_refcnt(struct dentry *dentry, void *ignore)
1029 {
1030         dentry->refcnt++;
1031         return 0;
1032 }
1033
1034 /*
1035  * Links a dentry into the directory tree.
1036  *
1037  * @dentry: The dentry to link.
1038  * @parent: The dentry that will be the parent of @dentry.
1039  */
1040 bool dentry_add_child(struct dentry * restrict parent,
1041                       struct dentry * restrict child)
1042 {
1043         wimlib_assert(dentry_is_directory(parent));
1044
1045         struct rb_root *root = &parent->d_inode->children;
1046         struct rb_node **new = &(root->rb_node);
1047         struct rb_node *rb_parent = NULL;
1048
1049         while (*new) {
1050                 struct dentry *this = rbnode_dentry(*new);
1051                 int result = dentry_compare_names(child, this);
1052
1053                 rb_parent = *new;
1054
1055                 if (result < 0)
1056                         new = &((*new)->rb_left);
1057                 else if (result > 0)
1058                         new = &((*new)->rb_right);
1059                 else
1060                         return false;
1061         }
1062         child->parent = parent;
1063         rb_link_node(&child->rb_node, rb_parent, new);
1064         rb_insert_color(&child->rb_node, root);
1065         return true;
1066 }
1067
1068 #ifdef WITH_FUSE
1069 /*
1070  * Unlink a dentry from the directory tree.
1071  *
1072  * Note: This merely removes it from the in-memory tree structure.
1073  */
1074 void unlink_dentry(struct dentry *dentry)
1075 {
1076         struct dentry *parent = dentry->parent;
1077         if (parent == dentry)
1078                 return;
1079         rb_erase(&dentry->rb_node, &parent->d_inode->children);
1080 }
1081 #endif
1082
1083 static inline struct dentry *inode_first_dentry(struct inode *inode)
1084 {
1085         wimlib_assert(inode->dentry_list.next != &inode->dentry_list);
1086         return container_of(inode->dentry_list.next, struct dentry,
1087                             inode_dentry_list);
1088 }
1089
1090 static int verify_inode(struct inode *inode, const WIMStruct *w)
1091 {
1092         const struct lookup_table *table = w->lookup_table;
1093         const struct wim_security_data *sd = wim_const_security_data(w);
1094         const struct dentry *first_dentry = inode_first_dentry(inode);
1095         int ret = WIMLIB_ERR_INVALID_DENTRY;
1096
1097         /* Check the security ID */
1098         if (inode->security_id < -1) {
1099                 ERROR("Dentry `%s' has an invalid security ID (%d)",
1100                         first_dentry->full_path_utf8, inode->security_id);
1101                 goto out;
1102         }
1103         if (inode->security_id >= sd->num_entries) {
1104                 ERROR("Dentry `%s' has an invalid security ID (%d) "
1105                       "(there are only %u entries in the security table)",
1106                         first_dentry->full_path_utf8, inode->security_id,
1107                         sd->num_entries);
1108                 goto out;
1109         }
1110
1111         /* Check that lookup table entries for all the resources exist, except
1112          * if the SHA1 message digest is all 0's, which indicates there is
1113          * intentionally no resource there.  */
1114         if (w->hdr.total_parts == 1) {
1115                 for (unsigned i = 0; i <= inode->num_ads; i++) {
1116                         struct lookup_table_entry *lte;
1117                         const u8 *hash;
1118                         hash = inode_stream_hash_unresolved(inode, i);
1119                         lte = __lookup_resource(table, hash);
1120                         if (!lte && !is_zero_hash(hash)) {
1121                                 ERROR("Could not find lookup table entry for stream "
1122                                       "%u of dentry `%s'", i, first_dentry->full_path_utf8);
1123                                 goto out;
1124                         }
1125                         if (lte)
1126                                 lte->real_refcnt += inode->link_count;
1127
1128                         /* The following is now done when required by
1129                          * wim_run_full_verifications(). */
1130
1131                 #if 0
1132                         if (lte && !w->full_verification_in_progress &&
1133                             lte->real_refcnt > lte->refcnt)
1134                         {
1135                         #ifdef ENABLE_ERROR_MESSAGES
1136                                 WARNING("The following lookup table entry "
1137                                         "has a reference count of %u, but",
1138                                         lte->refcnt);
1139                                 WARNING("We found %u references to it",
1140                                         lte->real_refcnt);
1141                                 WARNING("(One dentry referencing it is at `%s')",
1142                                          first_dentry->full_path_utf8);
1143
1144                                 print_lookup_table_entry(lte);
1145                         #endif
1146                                 /* Guess what!  install.wim for Windows 8
1147                                  * contains many streams referenced by more
1148                                  * dentries than the refcnt stated in the lookup
1149                                  * table entry.  So we will need to handle this
1150                                  * case and not just make it be an error...  I'm
1151                                  * just setting the reference count to the
1152                                  * number of references we found.
1153                                  * (Unfortunately, even after doing this, the
1154                                  * reference count could be too low if it's also
1155                                  * referenced in other WIM images) */
1156
1157                         #if 1
1158                                 lte->refcnt = lte->real_refcnt;
1159                                 WARNING("Fixing reference count");
1160                         #else
1161                                 goto out;
1162                         #endif
1163                         }
1164                 #endif
1165                 }
1166         }
1167
1168         /* Make sure there is only one un-named stream. */
1169         unsigned num_unnamed_streams = 0;
1170         for (unsigned i = 0; i <= inode->num_ads; i++) {
1171                 const u8 *hash;
1172                 hash = inode_stream_hash_unresolved(inode, i);
1173                 if (!inode_stream_name_len(inode, i) && !is_zero_hash(hash))
1174                         num_unnamed_streams++;
1175         }
1176         if (num_unnamed_streams > 1) {
1177                 ERROR("Dentry `%s' has multiple (%u) un-named streams",
1178                       first_dentry->full_path_utf8, num_unnamed_streams);
1179                 goto out;
1180         }
1181         inode->verified = true;
1182         ret = 0;
1183 out:
1184         return ret;
1185 }
1186
1187 /* Run some miscellaneous verifications on a WIM dentry */
1188 int verify_dentry(struct dentry *dentry, void *wim)
1189 {
1190         int ret;
1191
1192         if (!dentry->d_inode->verified) {
1193                 ret = verify_inode(dentry->d_inode, wim);
1194                 if (ret != 0)
1195                         return ret;
1196         }
1197
1198         /* Cannot have a short name but no long name */
1199         if (dentry->short_name_len && !dentry->file_name_len) {
1200                 ERROR("Dentry `%s' has a short name but no long name",
1201                       dentry->full_path_utf8);
1202                 return WIMLIB_ERR_INVALID_DENTRY;
1203         }
1204
1205         /* Make sure root dentry is unnamed */
1206         if (dentry_is_root(dentry)) {
1207                 if (dentry->file_name_len) {
1208                         ERROR("The root dentry is named `%s', but it must "
1209                               "be unnamed", dentry->file_name_utf8);
1210                         return WIMLIB_ERR_INVALID_DENTRY;
1211                 }
1212         }
1213
1214 #if 0
1215         /* Check timestamps */
1216         if (inode->last_access_time < inode->creation_time ||
1217             inode->last_write_time < inode->creation_time) {
1218                 WARNING("Dentry `%s' was created after it was last accessed or "
1219                       "written to", dentry->full_path_utf8);
1220         }
1221 #endif
1222
1223         return 0;
1224 }
1225
1226
1227 #ifdef WITH_FUSE
1228 /* Returns the alternate data stream entry belonging to @inode that has the
1229  * stream name @stream_name. */
1230 struct ads_entry *inode_get_ads_entry(struct inode *inode,
1231                                       const char *stream_name,
1232                                       u16 *idx_ret)
1233 {
1234         size_t stream_name_len;
1235         if (!stream_name)
1236                 return NULL;
1237         if (inode->num_ads) {
1238                 u16 i = 0;
1239                 stream_name_len = strlen(stream_name);
1240                 do {
1241                         if (ads_entry_has_name(&inode->ads_entries[i],
1242                                                stream_name, stream_name_len))
1243                         {
1244                                 if (idx_ret)
1245                                         *idx_ret = i;
1246                                 return &inode->ads_entries[i];
1247                         }
1248                 } while (++i != inode->num_ads);
1249         }
1250         return NULL;
1251 }
1252 #endif
1253
1254 #if defined(WITH_FUSE) || defined(WITH_NTFS_3G)
1255 /*
1256  * Add an alternate stream entry to an inode and return a pointer to it, or NULL
1257  * if memory could not be allocated.
1258  */
1259 struct ads_entry *inode_add_ads(struct inode *inode, const char *stream_name)
1260 {
1261         u16 num_ads;
1262         struct ads_entry *ads_entries;
1263         struct ads_entry *new_entry;
1264
1265         DEBUG("Add alternate data stream \"%s\"", stream_name);
1266
1267         if (inode->num_ads >= 0xfffe) {
1268                 ERROR("Too many alternate data streams in one inode!");
1269                 return NULL;
1270         }
1271         num_ads = inode->num_ads + 1;
1272         ads_entries = REALLOC(inode->ads_entries,
1273                               num_ads * sizeof(inode->ads_entries[0]));
1274         if (!ads_entries) {
1275                 ERROR("Failed to allocate memory for new alternate data stream");
1276                 return NULL;
1277         }
1278         inode->ads_entries = ads_entries;
1279
1280         new_entry = &inode->ads_entries[num_ads - 1];
1281         if (init_ads_entry(new_entry, stream_name) != 0)
1282                 return NULL;
1283 #ifdef WITH_FUSE
1284         new_entry->stream_id = inode->next_stream_id++;
1285 #endif
1286         inode->num_ads = num_ads;
1287         return new_entry;
1288 }
1289 #endif
1290
1291 #ifdef WITH_FUSE
1292 /* Remove an alternate data stream from the inode  */
1293 void inode_remove_ads(struct inode *inode, u16 idx,
1294                       struct lookup_table *lookup_table)
1295 {
1296         struct ads_entry *ads_entry;
1297         struct lookup_table_entry *lte;
1298
1299         wimlib_assert(idx < inode->num_ads);
1300         wimlib_assert(inode->resolved);
1301
1302         ads_entry = &inode->ads_entries[idx];
1303
1304         DEBUG("Remove alternate data stream \"%s\"", ads_entry->stream_name_utf8);
1305
1306         lte = ads_entry->lte;
1307         if (lte)
1308                 lte_decrement_refcnt(lte, lookup_table);
1309
1310         destroy_ads_entry(ads_entry);
1311
1312         memcpy(&inode->ads_entries[idx],
1313                &inode->ads_entries[idx + 1],
1314                (inode->num_ads - idx - 1) * sizeof(inode->ads_entries[0]));
1315         inode->num_ads--;
1316 }
1317 #endif
1318
1319
1320
1321 /*
1322  * Reads the alternate data stream entries for a dentry.
1323  *
1324  * @p:  Pointer to buffer that starts with the first alternate stream entry.
1325  *
1326  * @inode:      Inode to load the alternate data streams into.
1327  *                      @inode->num_ads must have been set to the number of
1328  *                      alternate data streams that are expected.
1329  *
1330  * @remaining_size:     Number of bytes of data remaining in the buffer pointed
1331  *                              to by @p.
1332  *
1333  * The format of the on-disk alternate stream entries is as follows:
1334  *
1335  * struct ads_entry_on_disk {
1336  *      u64  length;          // Length of the entry, in bytes.  This includes
1337  *                                  all fields (including the stream name and
1338  *                                  null terminator if present, AND the padding!).
1339  *      u64  reserved;        // Seems to be unused
1340  *      u8   hash[20];        // SHA1 message digest of the uncompressed stream
1341  *      u16  stream_name_len; // Length of the stream name, in bytes
1342  *      char stream_name[];   // Stream name in UTF-16LE, @stream_name_len bytes long,
1343  *                                  not including null terminator
1344  *      u16  zero;            // UTF-16 null terminator for the stream name, NOT
1345  *                                  included in @stream_name_len.  Based on what
1346  *                                  I've observed from filenames in dentries,
1347  *                                  this field should not exist when
1348  *                                  (@stream_name_len == 0), but you can't
1349  *                                  actually tell because of the padding anyway
1350  *                                  (provided that the padding is zeroed, which
1351  *                                  it always seems to be).
1352  *      char padding[];       // Padding to make the size a multiple of 8 bytes.
1353  * };
1354  *
1355  * In addition, the entries are 8-byte aligned.
1356  *
1357  * Return 0 on success or nonzero on failure.  On success, inode->ads_entries
1358  * is set to an array of `struct ads_entry's of length inode->num_ads.  On
1359  * failure, @inode is not modified.
1360  */
1361 static int read_ads_entries(const u8 *p, struct inode *inode,
1362                             u64 remaining_size)
1363 {
1364         u16 num_ads;
1365         struct ads_entry *ads_entries;
1366         int ret;
1367
1368         num_ads = inode->num_ads;
1369         ads_entries = CALLOC(num_ads, sizeof(inode->ads_entries[0]));
1370         if (!ads_entries) {
1371                 ERROR("Could not allocate memory for %"PRIu16" "
1372                       "alternate data stream entries", num_ads);
1373                 return WIMLIB_ERR_NOMEM;
1374         }
1375
1376         for (u16 i = 0; i < num_ads; i++) {
1377                 struct ads_entry *cur_entry;
1378                 u64 length;
1379                 u64 length_no_padding;
1380                 u64 total_length;
1381                 size_t utf8_len;
1382                 const u8 *p_save = p;
1383
1384                 cur_entry = &ads_entries[i];
1385
1386         #ifdef WITH_FUSE
1387                 ads_entries[i].stream_id = i + 1;
1388         #endif
1389
1390                 /* Read the base stream entry, excluding the stream name. */
1391                 if (remaining_size < WIM_ADS_ENTRY_DISK_SIZE) {
1392                         ERROR("Stream entries go past end of metadata resource");
1393                         ERROR("(remaining_size = %"PRIu64")", remaining_size);
1394                         ret = WIMLIB_ERR_INVALID_DENTRY;
1395                         goto out_free_ads_entries;
1396                 }
1397
1398                 p = get_u64(p, &length);
1399                 p += 8; /* Skip the reserved field */
1400                 p = get_bytes(p, SHA1_HASH_SIZE, (u8*)cur_entry->hash);
1401                 p = get_u16(p, &cur_entry->stream_name_len);
1402
1403                 cur_entry->stream_name = NULL;
1404                 cur_entry->stream_name_utf8 = NULL;
1405
1406                 /* Length including neither the null terminator nor the padding
1407                  * */
1408                 length_no_padding = WIM_ADS_ENTRY_DISK_SIZE +
1409                                     cur_entry->stream_name_len;
1410
1411                 /* Length including the null terminator and the padding */
1412                 total_length = ((length_no_padding + 2) + 7) & ~7;
1413
1414                 wimlib_assert(total_length == ads_entry_total_length(cur_entry));
1415
1416                 if (remaining_size < length_no_padding) {
1417                         ERROR("Stream entries go past end of metadata resource");
1418                         ERROR("(remaining_size = %"PRIu64" bytes, "
1419                               "length_no_padding = %"PRIu64" bytes)",
1420                               remaining_size, length_no_padding);
1421                         ret = WIMLIB_ERR_INVALID_DENTRY;
1422                         goto out_free_ads_entries;
1423                 }
1424
1425                 /* The @length field in the on-disk ADS entry is expected to be
1426                  * equal to @total_length, which includes all of the entry and
1427                  * the padding that follows it to align the next ADS entry to an
1428                  * 8-byte boundary.  However, to be safe, we'll accept the
1429                  * length field as long as it's not less than the un-padded
1430                  * total length and not more than the padded total length. */
1431                 if (length < length_no_padding || length > total_length) {
1432                         ERROR("Stream entry has unexpected length "
1433                               "field (length field = %"PRIu64", "
1434                               "unpadded total length = %"PRIu64", "
1435                               "padded total length = %"PRIu64")",
1436                               length, length_no_padding, total_length);
1437                         ret = WIMLIB_ERR_INVALID_DENTRY;
1438                         goto out_free_ads_entries;
1439                 }
1440
1441                 if (cur_entry->stream_name_len) {
1442                         cur_entry->stream_name = MALLOC(cur_entry->stream_name_len);
1443                         if (!cur_entry->stream_name) {
1444                                 ret = WIMLIB_ERR_NOMEM;
1445                                 goto out_free_ads_entries;
1446                         }
1447                         get_bytes(p, cur_entry->stream_name_len,
1448                                   (u8*)cur_entry->stream_name);
1449                         cur_entry->stream_name_utf8 = utf16_to_utf8(cur_entry->stream_name,
1450                                                                     cur_entry->stream_name_len,
1451                                                                     &utf8_len);
1452                         cur_entry->stream_name_utf8_len = utf8_len;
1453
1454                         if (!cur_entry->stream_name_utf8) {
1455                                 ret = WIMLIB_ERR_NOMEM;
1456                                 goto out_free_ads_entries;
1457                         }
1458                 }
1459                 /* It's expected that the size of every ADS entry is a multiple
1460                  * of 8.  However, to be safe, I'm allowing the possibility of
1461                  * an ADS entry at the very end of the metadata resource ending
1462                  * un-aligned.  So although we still need to increment the input
1463                  * pointer by @total_length to reach the next ADS entry, it's
1464                  * possible that less than @total_length is actually remaining
1465                  * in the metadata resource. We should set the remaining size to
1466                  * 0 bytes if this happens. */
1467                 p = p_save + total_length;
1468                 if (remaining_size < total_length)
1469                         remaining_size = 0;
1470                 else
1471                         remaining_size -= total_length;
1472         }
1473         inode->ads_entries = ads_entries;
1474 #ifdef WITH_FUSE
1475         inode->next_stream_id = inode->num_ads + 1;
1476 #endif
1477         return 0;
1478 out_free_ads_entries:
1479         for (u16 i = 0; i < num_ads; i++)
1480                 destroy_ads_entry(&ads_entries[i]);
1481         FREE(ads_entries);
1482         return ret;
1483 }
1484
1485 /*
1486  * Reads a directory entry, including all alternate data stream entries that
1487  * follow it, from the WIM image's metadata resource.
1488  *
1489  * @metadata_resource:  Buffer containing the uncompressed metadata resource.
1490  * @metadata_resource_len:   Length of the metadata resource.
1491  * @offset:     Offset of this directory entry in the metadata resource.
1492  * @dentry:     A `struct dentry' that will be filled in by this function.
1493  *
1494  * Return 0 on success or nonzero on failure.  On failure, @dentry will have
1495  * been modified, but it will not be left with pointers to any allocated
1496  * buffers.  On success, the dentry->length field must be examined.  If zero,
1497  * this was a special "end of directory" dentry and not a real dentry.  If
1498  * nonzero, this was a real dentry.
1499  */
1500 int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len,
1501                 u64 offset, struct dentry *dentry)
1502 {
1503         const u8 *p;
1504         u64 calculated_size;
1505         char *file_name = NULL;
1506         char *file_name_utf8 = NULL;
1507         char *short_name = NULL;
1508         u16 short_name_len;
1509         u16 file_name_len;
1510         size_t file_name_utf8_len = 0;
1511         int ret;
1512         struct inode *inode = NULL;
1513
1514         dentry_common_init(dentry);
1515
1516         /*Make sure the dentry really fits into the metadata resource.*/
1517         if (offset + 8 > metadata_resource_len || offset + 8 < offset) {
1518                 ERROR("Directory entry starting at %"PRIu64" ends past the "
1519                       "end of the metadata resource (size %"PRIu64")",
1520                       offset, metadata_resource_len);
1521                 return WIMLIB_ERR_INVALID_DENTRY;
1522         }
1523
1524         /* Before reading the whole dentry, we need to read just the length.
1525          * This is because a dentry of length 8 (that is, just the length field)
1526          * terminates the list of sibling directory entries. */
1527
1528         p = get_u64(&metadata_resource[offset], &dentry->length);
1529
1530         /* A zero length field (really a length of 8, since that's how big the
1531          * directory entry is...) indicates that this is the end of directory
1532          * dentry.  We do not read it into memory as an actual dentry, so just
1533          * return successfully in that case. */
1534         if (dentry->length == 0)
1535                 return 0;
1536
1537         /* If the dentry does not overflow the metadata resource buffer and is
1538          * not too short, read the rest of it (excluding the alternate data
1539          * streams, but including the file name and short name variable-length
1540          * fields) into memory. */
1541         if (offset + dentry->length >= metadata_resource_len
1542             || offset + dentry->length < offset)
1543         {
1544                 ERROR("Directory entry at offset %"PRIu64" and with size "
1545                       "%"PRIu64" ends past the end of the metadata resource "
1546                       "(size %"PRIu64")",
1547                       offset, dentry->length, metadata_resource_len);
1548                 return WIMLIB_ERR_INVALID_DENTRY;
1549         }
1550
1551         if (dentry->length < WIM_DENTRY_DISK_SIZE) {
1552                 ERROR("Directory entry has invalid length of %"PRIu64" bytes",
1553                       dentry->length);
1554                 return WIMLIB_ERR_INVALID_DENTRY;
1555         }
1556
1557         inode = new_timeless_inode();
1558         if (!inode)
1559                 return WIMLIB_ERR_NOMEM;
1560
1561         p = get_u32(p, &inode->attributes);
1562         p = get_u32(p, (u32*)&inode->security_id);
1563         p = get_u64(p, &dentry->subdir_offset);
1564
1565         /* 2 unused fields */
1566         p += 2 * sizeof(u64);
1567         /*p = get_u64(p, &dentry->unused1);*/
1568         /*p = get_u64(p, &dentry->unused2);*/
1569
1570         p = get_u64(p, &inode->creation_time);
1571         p = get_u64(p, &inode->last_access_time);
1572         p = get_u64(p, &inode->last_write_time);
1573
1574         p = get_bytes(p, SHA1_HASH_SIZE, inode->hash);
1575
1576         /*
1577          * I don't know what's going on here.  It seems like M$ screwed up the
1578          * reparse points, then put the fields in the same place and didn't
1579          * document it.  The WIM_HDR_FLAG_RP_FIX flag in the WIM header might
1580          * have something to do with this, but it's not documented.
1581          */
1582         if (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1583                 /* ??? */
1584                 p += 4;
1585                 p = get_u32(p, &inode->reparse_tag);
1586                 p += 4;
1587         } else {
1588                 p = get_u32(p, &inode->reparse_tag);
1589                 p = get_u64(p, &inode->ino);
1590         }
1591
1592         /* By the way, the reparse_reserved field does not actually exist (at
1593          * least when the file is not a reparse point) */
1594
1595         p = get_u16(p, &inode->num_ads);
1596
1597         p = get_u16(p, &short_name_len);
1598         p = get_u16(p, &file_name_len);
1599
1600         /* We now know the length of the file name and short name.  Make sure
1601          * the length of the dentry is large enough to actually hold them.
1602          *
1603          * The calculated length here is unaligned to allow for the possibility
1604          * that the dentry->length names an unaligned length, although this
1605          * would be unexpected. */
1606         calculated_size = __dentry_correct_length_unaligned(file_name_len,
1607                                                             short_name_len);
1608
1609         if (dentry->length < calculated_size) {
1610                 ERROR("Unexpected end of directory entry! (Expected "
1611                       "at least %"PRIu64" bytes, got %"PRIu64" bytes. "
1612                       "short_name_len = %hu, file_name_len = %hu)",
1613                       calculated_size, dentry->length,
1614                       short_name_len, file_name_len);
1615                 ret = WIMLIB_ERR_INVALID_DENTRY;
1616                 goto out_free_inode;
1617         }
1618
1619         /* Read the filename if present.  Note: if the filename is empty, there
1620          * is no null terminator following it. */
1621         if (file_name_len) {
1622                 file_name = MALLOC(file_name_len);
1623                 if (!file_name) {
1624                         ERROR("Failed to allocate %hu bytes for dentry file name",
1625                               file_name_len);
1626                         ret = WIMLIB_ERR_NOMEM;
1627                         goto out_free_inode;
1628                 }
1629                 p = get_bytes(p, file_name_len, file_name);
1630
1631                 /* Convert filename to UTF-8. */
1632                 file_name_utf8 = utf16_to_utf8(file_name, file_name_len,
1633                                                &file_name_utf8_len);
1634
1635                 if (!file_name_utf8) {
1636                         ERROR("Failed to allocate memory to convert UTF-16 "
1637                               "filename (%hu bytes) to UTF-8", file_name_len);
1638                         ret = WIMLIB_ERR_NOMEM;
1639                         goto out_free_file_name;
1640                 }
1641                 if (*(u16*)p)
1642                         WARNING("Expected two zero bytes following the file name "
1643                                 "`%s', but found non-zero bytes", file_name_utf8);
1644                 p += 2;
1645         }
1646
1647         /* Align the calculated size */
1648         calculated_size = (calculated_size + 7) & ~7;
1649
1650         if (dentry->length > calculated_size) {
1651                 /* Weird; the dentry says it's longer than it should be.  Note
1652                  * that the length field does NOT include the size of the
1653                  * alternate stream entries. */
1654
1655                 /* Strangely, some directory entries inexplicably have a little
1656                  * over 70 bytes of extra data.  The exact amount of data seems
1657                  * to be 72 bytes, but it is aligned on the next 8-byte
1658                  * boundary.  It does NOT seem to be alternate data stream
1659                  * entries.  Here's an example of the aligned data:
1660                  *
1661                  * 01000000 40000000 6c786bba c58ede11 b0bb0026 1870892a b6adb76f
1662                  * e63a3e46 8fca8653 0d2effa1 6c786bba c58ede11 b0bb0026 1870892a
1663                  * 00000000 00000000 00000000 00000000
1664                  *
1665                  * Here's one interpretation of how the data is laid out.
1666                  *
1667                  * struct unknown {
1668                  *      u32 field1; (always 0x00000001)
1669                  *      u32 field2; (always 0x40000000)
1670                  *      u8  data[48]; (???)
1671                  *      u64 reserved1; (always 0)
1672                  *      u64 reserved2; (always 0)
1673                  * };*/
1674                 DEBUG("Dentry for file or directory `%s' has %zu extra "
1675                       "bytes of data",
1676                       file_name_utf8, dentry->length - calculated_size);
1677         }
1678
1679         /* Read the short filename if present.  Note: if there is no short
1680          * filename, there is no null terminator following it. */
1681         if (short_name_len) {
1682                 short_name = MALLOC(short_name_len);
1683                 if (!short_name) {
1684                         ERROR("Failed to allocate %hu bytes for short filename",
1685                               short_name_len);
1686                         ret = WIMLIB_ERR_NOMEM;
1687                         goto out_free_file_name_utf8;
1688                 }
1689
1690                 p = get_bytes(p, short_name_len, short_name);
1691                 if (*(u16*)p)
1692                         WARNING("Expected two zero bytes following the short name of "
1693                                 "`%s', but found non-zero bytes", file_name_utf8);
1694                 p += 2;
1695         }
1696
1697         /*
1698          * Read the alternate data streams, if present.  dentry->num_ads tells
1699          * us how many they are, and they will directly follow the dentry
1700          * on-disk.
1701          *
1702          * Note that each alternate data stream entry begins on an 8-byte
1703          * aligned boundary, and the alternate data stream entries are NOT
1704          * included in the dentry->length field for some reason.
1705          */
1706         if (inode->num_ads != 0) {
1707
1708                 /* Trying different lengths is just a hack to make sure we have
1709                  * a chance of reading the ADS entries correctly despite the
1710                  * poor documentation. */
1711
1712                 if (calculated_size != dentry->length) {
1713                         WARNING("Trying calculated dentry length (%"PRIu64") "
1714                                 "instead of dentry->length field (%"PRIu64") "
1715                                 "to read ADS entries",
1716                                 calculated_size, dentry->length);
1717                 }
1718                 u64 lengths_to_try[3] = {calculated_size,
1719                                          (dentry->length + 7) & ~7,
1720                                          dentry->length};
1721                 ret = WIMLIB_ERR_INVALID_DENTRY;
1722                 for (size_t i = 0; i < ARRAY_LEN(lengths_to_try); i++) {
1723                         if (lengths_to_try[i] > metadata_resource_len - offset)
1724                                 continue;
1725                         ret = read_ads_entries(&metadata_resource[offset + lengths_to_try[i]],
1726                                                inode,
1727                                                metadata_resource_len - offset - lengths_to_try[i]);
1728                         if (ret == 0)
1729                                 goto out;
1730                 }
1731                 ERROR("Failed to read alternate data stream "
1732                       "entries of `%s'", dentry->file_name_utf8);
1733                 goto out_free_short_name;
1734         }
1735 out:
1736
1737         /* We've read all the data for this dentry.  Set the names and their
1738          * lengths, and we've done. */
1739         dentry->d_inode            = inode;
1740         dentry->file_name          = file_name;
1741         dentry->file_name_utf8     = file_name_utf8;
1742         dentry->short_name         = short_name;
1743         dentry->file_name_len      = file_name_len;
1744         dentry->file_name_utf8_len = file_name_utf8_len;
1745         dentry->short_name_len     = short_name_len;
1746         return 0;
1747 out_free_short_name:
1748         FREE(short_name);
1749 out_free_file_name_utf8:
1750         FREE(file_name_utf8);
1751 out_free_file_name:
1752         FREE(file_name);
1753 out_free_inode:
1754         free_inode(inode);
1755         return ret;
1756 }
1757
1758 /* Reads the children of a dentry, and all their children, ..., etc. from the
1759  * metadata resource and into the dentry tree.
1760  *
1761  * @metadata_resource:  An array that contains the uncompressed metadata
1762  *                      resource for the WIM file.
1763  *
1764  * @metadata_resource_len:  The length of the uncompressed metadata resource, in
1765  *                          bytes.
1766  *
1767  * @dentry:     A pointer to a `struct dentry' that is the root of the directory
1768  *              tree and has already been read from the metadata resource.  It
1769  *              does not need to be the real root because this procedure is
1770  *              called recursively.
1771  *
1772  * @return:     Zero on success, nonzero on failure.
1773  */
1774 int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
1775                      struct dentry *dentry)
1776 {
1777         u64 cur_offset = dentry->subdir_offset;
1778         struct dentry *child;
1779         struct dentry cur_child;
1780         int ret;
1781
1782         /*
1783          * If @dentry has no child dentries, nothing more needs to be done for
1784          * this branch.  This is the case for regular files, symbolic links, and
1785          * *possibly* empty directories (although an empty directory may also
1786          * have one child dentry that is the special end-of-directory dentry)
1787          */
1788         if (cur_offset == 0)
1789                 return 0;
1790
1791         /* Find and read all the children of @dentry. */
1792         while (1) {
1793
1794                 /* Read next child of @dentry into @cur_child. */
1795                 ret = read_dentry(metadata_resource, metadata_resource_len,
1796                                   cur_offset, &cur_child);
1797                 if (ret != 0)
1798                         break;
1799
1800                 /* Check for end of directory. */
1801                 if (cur_child.length == 0)
1802                         break;
1803
1804                 /* Not end of directory.  Allocate this child permanently and
1805                  * link it to the parent and previous child. */
1806                 child = MALLOC(sizeof(struct dentry));
1807                 if (!child) {
1808                         ERROR("Failed to allocate %zu bytes for new dentry",
1809                               sizeof(struct dentry));
1810                         ret = WIMLIB_ERR_NOMEM;
1811                         break;
1812                 }
1813                 memcpy(child, &cur_child, sizeof(struct dentry));
1814                 dentry_add_child(dentry, child);
1815                 inode_add_dentry(child, child->d_inode);
1816
1817                 /* If there are children of this child, call this procedure
1818                  * recursively. */
1819                 if (child->subdir_offset != 0) {
1820                         ret = read_dentry_tree(metadata_resource,
1821                                                metadata_resource_len, child);
1822                         if (ret != 0)
1823                                 break;
1824                 }
1825
1826                 /* Advance to the offset of the next child.  Note: We need to
1827                  * advance by the TOTAL length of the dentry, not by the length
1828                  * child->length, which although it does take into account the
1829                  * padding, it DOES NOT take into account alternate stream
1830                  * entries. */
1831                 cur_offset += dentry_total_length(child);
1832         }
1833         return ret;
1834 }
1835
1836 /*
1837  * Writes a WIM dentry to an output buffer.
1838  *
1839  * @dentry:  The dentry structure.
1840  * @p:       The memory location to write the data to.
1841  * @return:  Pointer to the byte after the last byte we wrote as part of the
1842  *              dentry.
1843  */
1844 static u8 *write_dentry(const struct dentry *dentry, u8 *p)
1845 {
1846         u8 *orig_p = p;
1847         const u8 *hash;
1848         const struct inode *inode = dentry->d_inode;
1849
1850         /* We calculate the correct length of the dentry ourselves because the
1851          * dentry->length field may been set to an unexpected value from when we
1852          * read the dentry in (for example, there may have been unknown data
1853          * appended to the end of the dentry...) */
1854         u64 length = dentry_correct_length(dentry);
1855
1856         p = put_u64(p, length);
1857         p = put_u32(p, inode->attributes);
1858         p = put_u32(p, inode->security_id);
1859         p = put_u64(p, dentry->subdir_offset);
1860         p = put_u64(p, 0); /* unused1 */
1861         p = put_u64(p, 0); /* unused2 */
1862         p = put_u64(p, inode->creation_time);
1863         p = put_u64(p, inode->last_access_time);
1864         p = put_u64(p, inode->last_write_time);
1865         hash = inode_stream_hash(inode, 0);
1866         p = put_bytes(p, SHA1_HASH_SIZE, hash);
1867         if (inode->attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1868                 p = put_zeroes(p, 4);
1869                 p = put_u32(p, inode->reparse_tag);
1870                 p = put_zeroes(p, 4);
1871         } else {
1872                 u64 link_group_id;
1873                 p = put_u32(p, 0);
1874                 if (inode->link_count == 1)
1875                         link_group_id = 0;
1876                 else
1877                         link_group_id = inode->ino;
1878                 p = put_u64(p, link_group_id);
1879         }
1880         p = put_u16(p, inode->num_ads);
1881         p = put_u16(p, dentry->short_name_len);
1882         p = put_u16(p, dentry->file_name_len);
1883         if (dentry->file_name_len) {
1884                 p = put_bytes(p, dentry->file_name_len, (u8*)dentry->file_name);
1885                 p = put_u16(p, 0); /* filename padding, 2 bytes. */
1886         }
1887         if (dentry->short_name) {
1888                 p = put_bytes(p, dentry->short_name_len, (u8*)dentry->short_name);
1889                 p = put_u16(p, 0); /* short name padding, 2 bytes */
1890         }
1891
1892         /* Align to 8-byte boundary */
1893         wimlib_assert(length >= (p - orig_p) && length - (p - orig_p) <= 7);
1894         p = put_zeroes(p, length - (p - orig_p));
1895
1896         /* Write the alternate data streams, if there are any.  Please see
1897          * read_ads_entries() for comments about the format of the on-disk
1898          * alternate data stream entries. */
1899         for (u16 i = 0; i < inode->num_ads; i++) {
1900                 p = put_u64(p, ads_entry_total_length(&inode->ads_entries[i]));
1901                 p = put_u64(p, 0); /* Unused */
1902                 hash = inode_stream_hash(inode, i + 1);
1903                 p = put_bytes(p, SHA1_HASH_SIZE, hash);
1904                 p = put_u16(p, inode->ads_entries[i].stream_name_len);
1905                 if (inode->ads_entries[i].stream_name_len) {
1906                         p = put_bytes(p, inode->ads_entries[i].stream_name_len,
1907                                          (u8*)inode->ads_entries[i].stream_name);
1908                         p = put_u16(p, 0);
1909                 }
1910                 p = put_zeroes(p, (8 - (p - orig_p) % 8) % 8);
1911         }
1912         wimlib_assert(p - orig_p == __dentry_total_length(dentry, length));
1913         return p;
1914 }
1915
1916 static int write_dentry_cb(struct dentry *dentry, void *_p)
1917 {
1918         u8 **p = _p;
1919         *p = write_dentry(dentry, *p);
1920         return 0;
1921 }
1922
1923 static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p);
1924
1925 static int write_dentry_tree_recursive_cb(struct dentry *dentry, void *_p)
1926 {
1927         u8 **p = _p;
1928         *p = write_dentry_tree_recursive(dentry, *p);
1929         return 0;
1930 }
1931
1932 /* Recursive function that writes a dentry tree rooted at @parent, not including
1933  * @parent itself, which has already been written. */
1934 static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p)
1935 {
1936         /* Nothing to do if this dentry has no children. */
1937         if (parent->subdir_offset == 0)
1938                 return p;
1939
1940         /* Write child dentries and end-of-directory entry.
1941          *
1942          * Note: we need to write all of this dentry's children before
1943          * recursively writing the directory trees rooted at each of the child
1944          * dentries, since the on-disk dentries for a dentry's children are
1945          * always located at consecutive positions in the metadata resource! */
1946         for_dentry_in_rbtree(parent->d_inode->children.rb_node, write_dentry_cb, &p);
1947
1948         /* write end of directory entry */
1949         p = put_u64(p, 0);
1950
1951         /* Recurse on children. */
1952         for_dentry_in_rbtree(parent->d_inode->children.rb_node,
1953                              write_dentry_tree_recursive_cb, &p);
1954         return p;
1955 }
1956
1957 /* Writes a directory tree to the metadata resource.
1958  *
1959  * @root:       Root of the dentry tree.
1960  * @p:          Pointer to a buffer with enough space for the dentry tree.
1961  *
1962  * Returns pointer to the byte after the last byte we wrote.
1963  */
1964 u8 *write_dentry_tree(const struct dentry *root, u8 *p)
1965 {
1966         DEBUG("Writing dentry tree.");
1967         wimlib_assert(dentry_is_root(root));
1968
1969         /* If we're the root dentry, we have no parent that already
1970          * wrote us, so we need to write ourselves. */
1971         p = write_dentry(root, p);
1972
1973         /* Write end of directory entry after the root dentry just to be safe;
1974          * however the root dentry obviously cannot have any siblings. */
1975         p = put_u64(p, 0);
1976
1977         /* Recursively write the rest of the dentry tree. */
1978         return write_dentry_tree_recursive(root, p);
1979 }
1980