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

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