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