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

   1 /*
   2  * win32_capture.c - Windows-specific code for capturing files into a WIM image.
   3  *
   4  * This now uses the native Windows NT API a lot and not just Win32.
   5  */
   6
   7 /*
   8  * Copyright (C) 2013-2016 Eric Biggers
   9  *
  10  * This file is free software; you can redistribute it and/or modify it under
  11  * the terms of the GNU Lesser General Public License as published by the Free
  12  * Software Foundation; either version 3 of the License, or (at your option) any
  13  * later version.
  14  *
  15  * This file is distributed in the hope that it will be useful, but WITHOUT
  16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  17  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  18  * details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with this file; if not, see http://www.gnu.org/licenses/.
  22  */
  23
  24 #ifdef __WIN32__
  25
  26 #ifdef HAVE_CONFIG_H
  27 #  include "config.h"
  28 #endif
  29
  30 #include "wimlib/win32_common.h"
  31
  32 #include "wimlib/assert.h"
  33 #include "wimlib/blob_table.h"
  34 #include "wimlib/capture.h"
  35 #include "wimlib/dentry.h"
  36 #include "wimlib/encoding.h"
  37 #include "wimlib/endianness.h"
  38 #include "wimlib/error.h"
  39 #include "wimlib/paths.h"
  40 #include "wimlib/reparse.h"
  41 #include "wimlib/win32_vss.h"
  42 #include "wimlib/wof.h"
  43
  44 struct winnt_scan_ctx {
  45         struct capture_params *params;
  46         bool is_ntfs;
  47         u32 vol_flags;
  48         unsigned long num_get_sd_access_denied;
  49         unsigned long num_get_sacl_priv_notheld;
  50
  51         /* True if WOF is definitely not attached to the volume being scanned;
  52          * false if it may be  */
  53         bool wof_not_attached;
  54
  55         /* A reference to the VSS snapshot being used, or NULL if none  */
  56         struct vss_snapshot *snapshot;
  57 };
  58
  59 static inline const wchar_t *
  60 printable_path(const wchar_t *full_path)
  61 {
  62         /* Skip over \\?\ or \??\  */
  63         return full_path + 4;
  64 }
  65
  66 /* Description of where data is located on a Windows filesystem  */
  67 struct windows_file {
  68
  69         /* Is the data the raw encrypted data of an EFS-encrypted file?  */
  70         u64 is_encrypted : 1;
  71
  72         /* Is this file "open by file ID" rather than the regular "open by
  73          * path"?  "Open by file ID" uses resources more efficiently.  */
  74         u64 is_file_id : 1;
  75
  76         /* The file's LCN (logical cluster number) for sorting, or 0 if unknown.
  77          */
  78         u64 sort_key : 62;
  79
  80         /* Length of the path in bytes, excluding the null terminator if
  81          * present.  */
  82         size_t path_nbytes;
  83
  84         /* A reference to the VSS snapshot containing the file, or NULL if none.
  85          */
  86         struct vss_snapshot *snapshot;
  87
  88         /* The path to the file.  If 'is_encrypted=0' this is an NT namespace
  89          * path; if 'is_encrypted=1' this is a Win32 namespace path.  If
  90          * 'is_file_id=0', then the path is null-terminated.  If 'is_file_id=1'
  91          * (only allowed with 'is_encrypted=0') the path ends with a binary file
  92          * ID and may not be null-terminated.  */
  93         wchar_t path[0];
  94 };
  95
  96 /* Allocate a structure to describe the location of a data stream by path.  */
  97 static struct windows_file *
  98 alloc_windows_file(const wchar_t *path, size_t path_nchars,
  99                    const wchar_t *stream_name, size_t stream_name_nchars,
 100                    struct vss_snapshot *snapshot, bool is_encrypted)
 101 {
 102         size_t full_path_nbytes;
 103         struct windows_file *file;
 104         wchar_t *p;
 105
 106         full_path_nbytes = path_nchars * sizeof(wchar_t);
 107         if (stream_name_nchars)
 108                 full_path_nbytes += (1 + stream_name_nchars) * sizeof(wchar_t);
 109
 110         file = MALLOC(sizeof(struct windows_file) + full_path_nbytes +
 111                       sizeof(wchar_t));
 112         if (!file)
 113                 return NULL;
 114
 115         file->is_encrypted = is_encrypted;
 116         file->is_file_id = 0;
 117         file->sort_key = 0;
 118         file->path_nbytes = full_path_nbytes;
 119         file->snapshot = vss_get_snapshot(snapshot);
 120         p = wmempcpy(file->path, path, path_nchars);
 121         if (stream_name_nchars) {
 122                 /* Named data stream  */
 123                 *p++ = L':';
 124                 p = wmempcpy(p, stream_name, stream_name_nchars);
 125         }
 126         *p = L'\0';
 127         return file;
 128 }
 129
 130 /* Allocate a structure to describe the location of a file by ID.  */
 131 static struct windows_file *
 132 alloc_windows_file_for_file_id(u64 file_id, const wchar_t *root_path,
 133                                size_t root_path_nchars,
 134                                struct vss_snapshot *snapshot)
 135 {
 136         size_t full_path_nbytes;
 137         struct windows_file *file;
 138         wchar_t *p;
 139
 140         full_path_nbytes = (root_path_nchars * sizeof(wchar_t)) +
 141                            sizeof(file_id);
 142         file = MALLOC(sizeof(struct windows_file) + full_path_nbytes +
 143                       sizeof(wchar_t));
 144         if (!file)
 145                 return NULL;
 146
 147         file->is_encrypted = 0;
 148         file->is_file_id = 1;
 149         file->sort_key = 0;
 150         file->path_nbytes = full_path_nbytes;
 151         file->snapshot = vss_get_snapshot(snapshot);
 152         p = wmempcpy(file->path, root_path, root_path_nchars);
 153         p = mempcpy(p, &file_id, sizeof(file_id));
 154         *p = L'\0';
 155         return file;
 156 }
 157
 158 /* Add a stream, located on a Windows filesystem, to the specified WIM inode. */
 159 static int
 160 add_stream(struct wim_inode *inode, struct windows_file *windows_file,
 161            u64 stream_size, int stream_type, const utf16lechar *stream_name,
 162            struct list_head *unhashed_blobs)
 163 {
 164         struct blob_descriptor *blob = NULL;
 165         struct wim_inode_stream *strm;
 166         int ret;
 167
 168         if (!windows_file)
 169                 goto err_nomem;
 170
 171         /* If the stream is nonempty, create a blob descriptor for it.  */
 172         if (stream_size) {
 173                 blob = new_blob_descriptor();
 174                 if (!blob)
 175                         goto err_nomem;
 176                 blob->windows_file = windows_file;
 177                 blob->blob_location = BLOB_IN_WINDOWS_FILE;
 178                 blob->file_inode = inode;
 179                 blob->size = stream_size;
 180                 windows_file = NULL;
 181         }
 182
 183         strm = inode_add_stream(inode, stream_type, stream_name, blob);
 184         if (!strm)
 185                 goto err_nomem;
 186
 187         prepare_unhashed_blob(blob, inode, strm->stream_id, unhashed_blobs);
 188         ret = 0;
 189 out:
 190         if (windows_file)
 191                 free_windows_file(windows_file);
 192         return ret;
 193
 194 err_nomem:
 195         free_blob_descriptor(blob);
 196         ret = WIMLIB_ERR_NOMEM;
 197         goto out;
 198 }
 199
 200 struct windows_file *
 201 clone_windows_file(const struct windows_file *file)
 202 {
 203         struct windows_file *new;
 204
 205         new = memdup(file, sizeof(*file) + file->path_nbytes + sizeof(wchar_t));
 206         if (new)
 207                 vss_get_snapshot(new->snapshot);
 208         return new;
 209 }
 210
 211 void
 212 free_windows_file(struct windows_file *file)
 213 {
 214         vss_put_snapshot(file->snapshot);
 215         FREE(file);
 216 }
 217
 218 int
 219 cmp_windows_files(const struct windows_file *file1,
 220                   const struct windows_file *file2)
 221 {
 222         /* Compare by starting LCN (logical cluster number)  */
 223         int v = cmp_u64(file1->sort_key, file2->sort_key);
 224         if (v)
 225                 return v;
 226
 227         /* Fall back to comparing files by path (arbitrary heuristic).  */
 228         v = memcmp(file1->path, file2->path,
 229                    min(file1->path_nbytes, file2->path_nbytes));
 230         if (v)
 231                 return v;
 232
 233         return cmp_u32(file1->path_nbytes, file2->path_nbytes);
 234 }
 235
 236 const wchar_t *
 237 get_windows_file_path(const struct windows_file *file)
 238 {
 239         return file->path;
 240 }
 241
 242 /*
 243  * Open the file named by the NT namespace path @path of length @path_nchars
 244  * characters.  If @cur_dir is not NULL then the path is given relative to
 245  * @cur_dir; otherwise the path is absolute.  @perms is the access mask of
 246  * permissions to request on the handle.  SYNCHRONIZE permision is always added.
 247  */
 248 static NTSTATUS
 249 winnt_openat(HANDLE cur_dir, const wchar_t *path, size_t path_nchars,
 250              ACCESS_MASK perms, HANDLE *h_ret)
 251 {
 252         UNICODE_STRING name = {
 253                 .Length = path_nchars * sizeof(wchar_t),
 254                 .MaximumLength = path_nchars * sizeof(wchar_t),
 255                 .Buffer = (wchar_t *)path,
 256         };
 257         OBJECT_ATTRIBUTES attr = {
 258                 .Length = sizeof(attr),
 259                 .RootDirectory = cur_dir,
 260                 .ObjectName = &name,
 261         };
 262         IO_STATUS_BLOCK iosb;
 263         NTSTATUS status;
 264         ULONG options = FILE_OPEN_REPARSE_POINT | FILE_OPEN_FOR_BACKUP_INTENT;
 265
 266         perms |= SYNCHRONIZE;
 267         if (perms & (FILE_READ_DATA | FILE_LIST_DIRECTORY)) {
 268                 options |= FILE_SYNCHRONOUS_IO_NONALERT;
 269                 options |= FILE_SEQUENTIAL_ONLY;
 270         }
 271 retry:
 272         status = NtOpenFile(h_ret, perms, &attr, &iosb,
 273                             FILE_SHARE_VALID_FLAGS, options);
 274         if (!NT_SUCCESS(status)) {
 275                 /* Try requesting fewer permissions  */
 276                 if (status == STATUS_ACCESS_DENIED ||
 277                     status == STATUS_PRIVILEGE_NOT_HELD) {
 278                         if (perms & ACCESS_SYSTEM_SECURITY) {
 279                                 perms &= ~ACCESS_SYSTEM_SECURITY;
 280                                 goto retry;
 281                         }
 282                         if (perms & READ_CONTROL) {
 283                                 perms &= ~READ_CONTROL;
 284                                 goto retry;
 285                         }
 286                 }
 287         }
 288         return status;
 289 }
 290
 291 static NTSTATUS
 292 winnt_open(const wchar_t *path, size_t path_nchars, ACCESS_MASK perms,
 293            HANDLE *h_ret)
 294 {
 295         return winnt_openat(NULL, path, path_nchars, perms, h_ret);
 296 }
 297
 298 static const wchar_t *
 299 windows_file_to_string(const struct windows_file *file, u8 *buf, size_t bufsize)
 300 {
 301         if (file->is_file_id) {
 302                 u64 file_id;
 303                 memcpy(&file_id,
 304                        (u8 *)file->path + file->path_nbytes - sizeof(file_id),
 305                        sizeof(file_id));
 306                 swprintf((wchar_t *)buf, L"NTFS inode 0x%016"PRIx64, file_id);
 307         } else if (file->path_nbytes + 3 * sizeof(wchar_t) <= bufsize) {
 308                 swprintf((wchar_t *)buf, L"\"%ls\"", file->path);
 309         } else {
 310                 return L"(name too long)";
 311         }
 312         return (wchar_t *)buf;
 313 }
 314
 315 static int
 316 read_winnt_stream_prefix(const struct windows_file *file,
 317                          u64 size, const struct read_blob_callbacks *cbs)
 318 {
 319         IO_STATUS_BLOCK iosb;
 320         UNICODE_STRING name = {
 321                 .Buffer = (wchar_t *)file->path,
 322                 .Length = file->path_nbytes,
 323                 .MaximumLength = file->path_nbytes,
 324         };
 325         OBJECT_ATTRIBUTES attr = {
 326                 .Length = sizeof(attr),
 327                 .ObjectName = &name,
 328         };
 329         HANDLE h;
 330         NTSTATUS status;
 331         u8 buf[BUFFER_SIZE] _aligned_attribute(8);
 332         u64 bytes_remaining;
 333         int ret;
 334
 335         status = NtOpenFile(&h, FILE_READ_DATA | SYNCHRONIZE,
 336                             &attr, &iosb,
 337                             FILE_SHARE_VALID_FLAGS,
 338                             FILE_OPEN_REPARSE_POINT |
 339                                 FILE_OPEN_FOR_BACKUP_INTENT |
 340                                 FILE_SYNCHRONOUS_IO_NONALERT |
 341                                 FILE_SEQUENTIAL_ONLY |
 342                                 (file->is_file_id ? FILE_OPEN_BY_FILE_ID : 0));
 343         if (unlikely(!NT_SUCCESS(status))) {
 344                 if (status == STATUS_SHARING_VIOLATION) {
 345                         ERROR("Can't open %ls for reading:\n"
 346                               "        File is in use by another process! "
 347                               "Consider using snapshot (VSS) mode.",
 348                               windows_file_to_string(file, buf, sizeof(buf)));
 349                 } else {
 350                         winnt_error(status, L"Can't open %ls for reading",
 351                                     windows_file_to_string(file, buf, sizeof(buf)));
 352                 }
 353                 return WIMLIB_ERR_OPEN;
 354         }
 355
 356         ret = 0;
 357         bytes_remaining = size;
 358         while (bytes_remaining) {
 359                 IO_STATUS_BLOCK iosb;
 360                 ULONG count;
 361                 ULONG bytes_read;
 362                 const unsigned max_tries = 5;
 363                 unsigned tries_remaining = max_tries;
 364
 365                 count = min(sizeof(buf), bytes_remaining);
 366
 367         retry_read:
 368                 status = NtReadFile(h, NULL, NULL, NULL,
 369                                     &iosb, buf, count, NULL, NULL);
 370                 if (unlikely(!NT_SUCCESS(status))) {
 371                         if (status == STATUS_END_OF_FILE) {
 372                                 ERROR("%ls: File was concurrently truncated",
 373                                       windows_file_to_string(file, buf, sizeof(buf)));
 374                                 ret = WIMLIB_ERR_CONCURRENT_MODIFICATION_DETECTED;
 375                         } else {
 376                                 winnt_warning(status, L"Error reading data from %ls",
 377                                               windows_file_to_string(file, buf, sizeof(buf)));
 378
 379                                 /* Currently these retries are purely a guess;
 380                                  * there is no reproducible problem that they solve.  */
 381                                 if (--tries_remaining) {
 382                                         int delay = 100;
 383                                         if (status == STATUS_INSUFFICIENT_RESOURCES ||
 384                                             status == STATUS_NO_MEMORY) {
 385                                                 delay *= 25;
 386                                         }
 387                                         WARNING("Retrying after %dms...", delay);
 388                                         Sleep(delay);
 389                                         goto retry_read;
 390                                 }
 391                                 ERROR("Too many retries; returning failure");
 392                                 ret = WIMLIB_ERR_READ;
 393                         }
 394                         break;
 395                 } else if (unlikely(tries_remaining != max_tries)) {
 396                         WARNING("A read request had to be retried multiple times "
 397                                 "before it succeeded!");
 398                 }
 399
 400                 bytes_read = iosb.Information;
 401
 402                 bytes_remaining -= bytes_read;
 403                 ret = call_consume_chunk(buf, bytes_read, cbs);
 404                 if (ret)
 405                         break;
 406         }
 407         NtClose(h);
 408         return ret;
 409 }
 410
 411 struct win32_encrypted_read_ctx {
 412         const struct read_blob_callbacks *cbs;
 413         int wimlib_err_code;
 414         u64 bytes_remaining;
 415 };
 416
 417 static DWORD WINAPI
 418 win32_encrypted_export_cb(unsigned char *data, void *_ctx, unsigned long len)
 419 {
 420         struct win32_encrypted_read_ctx *ctx = _ctx;
 421         int ret;
 422         size_t bytes_to_consume = min(len, ctx->bytes_remaining);
 423
 424         if (bytes_to_consume == 0)
 425                 return ERROR_SUCCESS;
 426
 427         ret = call_consume_chunk(data, bytes_to_consume, ctx->cbs);
 428         if (ret) {
 429                 ctx->wimlib_err_code = ret;
 430                 /* It doesn't matter what error code is returned here, as long
 431                  * as it isn't ERROR_SUCCESS.  */
 432                 return ERROR_READ_FAULT;
 433         }
 434         ctx->bytes_remaining -= bytes_to_consume;
 435         return ERROR_SUCCESS;
 436 }
 437
 438 static int
 439 read_win32_encrypted_file_prefix(const wchar_t *path, bool is_dir, u64 size,
 440                                  const struct read_blob_callbacks *cbs)
 441 {
 442         struct win32_encrypted_read_ctx export_ctx;
 443         DWORD err;
 444         void *file_ctx;
 445         int ret;
 446         DWORD flags = 0;
 447
 448         if (is_dir)
 449                 flags |= CREATE_FOR_DIR;
 450
 451         export_ctx.cbs = cbs;
 452         export_ctx.wimlib_err_code = 0;
 453         export_ctx.bytes_remaining = size;
 454
 455         err = OpenEncryptedFileRaw(path, flags, &file_ctx);
 456         if (err != ERROR_SUCCESS) {
 457                 win32_error(err,
 458                             L"Failed to open encrypted file \"%ls\" for raw read",
 459                             printable_path(path));
 460                 return WIMLIB_ERR_OPEN;
 461         }
 462         err = ReadEncryptedFileRaw(win32_encrypted_export_cb,
 463                                    &export_ctx, file_ctx);
 464         if (err != ERROR_SUCCESS) {
 465                 ret = export_ctx.wimlib_err_code;
 466                 if (ret == 0) {
 467                         win32_error(err,
 468                                     L"Failed to read encrypted file \"%ls\"",
 469                                     printable_path(path));
 470                         ret = WIMLIB_ERR_READ;
 471                 }
 472         } else if (export_ctx.bytes_remaining != 0) {
 473                 ERROR("Only could read %"PRIu64" of %"PRIu64" bytes from "
 474                       "encrypted file \"%ls\"",
 475                       size - export_ctx.bytes_remaining, size,
 476                       printable_path(path));
 477                 ret = WIMLIB_ERR_READ;
 478         } else {
 479                 ret = 0;
 480         }
 481         CloseEncryptedFileRaw(file_ctx);
 482         return ret;
 483 }
 484
 485 /* Read the first @size bytes from the file, or named data stream of a file,
 486  * described by @blob.  */
 487 int
 488 read_windows_file_prefix(const struct blob_descriptor *blob, u64 size,
 489                          const struct read_blob_callbacks *cbs)
 490 {
 491         const struct windows_file *file = blob->windows_file;
 492
 493         if (unlikely(file->is_encrypted)) {
 494                 bool is_dir = (blob->file_inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY);
 495                 return read_win32_encrypted_file_prefix(file->path, is_dir, size, cbs);
 496         }
 497
 498         return read_winnt_stream_prefix(file, size, cbs);
 499 }
 500
 501 /*
 502  * Load the short name of a file into a WIM dentry.
 503  */
 504 static noinline_for_stack NTSTATUS
 505 winnt_get_short_name(HANDLE h, struct wim_dentry *dentry)
 506 {
 507         /* It's not any harder to just make the NtQueryInformationFile() system
 508          * call ourselves, and it saves a dumb call to FindFirstFile() which of
 509          * course has to create its own handle.  */
 510         NTSTATUS status;
 511         IO_STATUS_BLOCK iosb;
 512         u8 buf[128] _aligned_attribute(8);
 513         const FILE_NAME_INFORMATION *info;
 514
 515         status = NtQueryInformationFile(h, &iosb, buf, sizeof(buf),
 516                                         FileAlternateNameInformation);
 517         info = (const FILE_NAME_INFORMATION *)buf;
 518         if (NT_SUCCESS(status) && info->FileNameLength != 0) {
 519                 dentry->d_short_name = utf16le_dupz(info->FileName,
 520                                                     info->FileNameLength);
 521                 if (!dentry->d_short_name)
 522                         return STATUS_NO_MEMORY;
 523                 dentry->d_short_name_nbytes = info->FileNameLength;
 524         }
 525         return status;
 526 }
 527
 528 /*
 529  * Load the security descriptor of a file into the corresponding inode and the
 530  * WIM image's security descriptor set.
 531  */
 532 static noinline_for_stack int
 533 winnt_load_security_descriptor(HANDLE h, struct wim_inode *inode,
 534                                const wchar_t *full_path,
 535                                struct winnt_scan_ctx *ctx)
 536 {
 537         SECURITY_INFORMATION requestedInformation;
 538         u8 _buf[4096] _aligned_attribute(8);
 539         u8 *buf;
 540         ULONG bufsize;
 541         ULONG len_needed;
 542         NTSTATUS status;
 543
 544         /*
 545          * LABEL_SECURITY_INFORMATION is needed on Windows Vista and 7 because
 546          * Microsoft decided to add mandatory integrity labels to the SACL but
 547          * not have them returned by SACL_SECURITY_INFORMATION.
 548          *
 549          * BACKUP_SECURITY_INFORMATION is needed on Windows 8 because Microsoft
 550          * decided to add even more stuff to the SACL and still not have it
 551          * returned by SACL_SECURITY_INFORMATION; but they did remember that
 552          * backup applications exist and simply want to read the stupid thing
 553          * once and for all, so they added a flag to read the entire security
 554          * descriptor.
 555          *
 556          * Older versions of Windows tolerate these new flags being passed in.
 557          */
 558         requestedInformation = OWNER_SECURITY_INFORMATION |
 559                                GROUP_SECURITY_INFORMATION |
 560                                DACL_SECURITY_INFORMATION |
 561                                SACL_SECURITY_INFORMATION |
 562                                LABEL_SECURITY_INFORMATION |
 563                                BACKUP_SECURITY_INFORMATION;
 564
 565         buf = _buf;
 566         bufsize = sizeof(_buf);
 567
 568         /*
 569          * We need the file's security descriptor in
 570          * SECURITY_DESCRIPTOR_RELATIVE format, and we currently have a handle
 571          * opened with as many relevant permissions as possible.  At this point,
 572          * on Windows there are a number of options for reading a file's
 573          * security descriptor:
 574          *
 575          * GetFileSecurity():  This takes in a path and returns the
 576          * SECURITY_DESCRIPTOR_RELATIVE.  Problem: this uses an internal handle,
 577          * not ours, and the handle created internally doesn't specify
 578          * FILE_FLAG_BACKUP_SEMANTICS.  Therefore there can be access denied
 579          * errors on some files and directories, even when running as the
 580          * Administrator.
 581          *
 582          * GetSecurityInfo():  This takes in a handle and returns the security
 583          * descriptor split into a bunch of different parts.  This should work,
 584          * but it's dumb because we have to put the security descriptor back
 585          * together again.
 586          *
 587          * BackupRead():  This can read the security descriptor, but this is a
 588          * difficult-to-use API, probably only works as the Administrator, and
 589          * the format of the returned data is not well documented.
 590          *
 591          * NtQuerySecurityObject():  This is exactly what we need, as it takes
 592          * in a handle and returns the security descriptor in
 593          * SECURITY_DESCRIPTOR_RELATIVE format.  Only problem is that it's a
 594          * ntdll function and therefore not officially part of the Win32 API.
 595          * Oh well.
 596          */
 597         while (!NT_SUCCESS(status = NtQuerySecurityObject(h,
 598                                                           requestedInformation,
 599                                                           (PSECURITY_DESCRIPTOR)buf,
 600                                                           bufsize,
 601                                                           &len_needed)))
 602         {
 603                 switch (status) {
 604                 case STATUS_BUFFER_TOO_SMALL:
 605                         wimlib_assert(buf == _buf);
 606                         buf = MALLOC(len_needed);
 607                         if (!buf) {
 608                                 status = STATUS_NO_MEMORY;
 609                                 goto out;
 610                         }
 611                         bufsize = len_needed;
 612                         break;
 613                 case STATUS_PRIVILEGE_NOT_HELD:
 614                 case STATUS_ACCESS_DENIED:
 615                         if (ctx->params->add_flags & WIMLIB_ADD_FLAG_STRICT_ACLS) {
 616                 default:
 617                                 /* Permission denied in STRICT_ACLS mode, or
 618                                  * unknown error.  */
 619                                 goto out;
 620                         }
 621                         if (requestedInformation & SACL_SECURITY_INFORMATION) {
 622                                 /* Try again without the SACL.  */
 623                                 ctx->num_get_sacl_priv_notheld++;
 624                                 requestedInformation &= ~(SACL_SECURITY_INFORMATION |
 625                                                           LABEL_SECURITY_INFORMATION |
 626                                                           BACKUP_SECURITY_INFORMATION);
 627                                 break;
 628                         }
 629                         /* Fake success (useful when capturing as
 630                          * non-Administrator).  */
 631                         ctx->num_get_sd_access_denied++;
 632                         status = STATUS_SUCCESS;
 633                         goto out;
 634                 }
 635         }
 636
 637         /* We can get a length of 0 with Samba.  Assume that means "no security
 638          * descriptor".  */
 639         if (len_needed == 0)
 640                 goto out;
 641
 642         /* Add the security descriptor to the WIM image, and save its ID in
 643          * the file's inode.  */
 644         inode->i_security_id = sd_set_add_sd(ctx->params->sd_set, buf, len_needed);
 645         if (unlikely(inode->i_security_id < 0))
 646                 status = STATUS_NO_MEMORY;
 647 out:
 648         if (unlikely(buf != _buf))
 649                 FREE(buf);
 650         if (!NT_SUCCESS(status)) {
 651                 winnt_error(status, L"\"%ls\": Can't read security descriptor",
 652                             printable_path(full_path));
 653                 return WIMLIB_ERR_STAT;
 654         }
 655         return 0;
 656 }
 657
 658 static int
 659 winnt_build_dentry_tree_recursive(struct wim_dentry **root_ret,
 660                                   HANDLE cur_dir,
 661                                   wchar_t *full_path,
 662                                   size_t full_path_nchars,
 663                                   wchar_t *relative_path,
 664                                   size_t relative_path_nchars,
 665                                   const wchar_t *filename,
 666                                   struct winnt_scan_ctx *ctx);
 667
 668 static int
 669 winnt_recurse_directory(HANDLE h,
 670                         wchar_t *full_path,
 671                         size_t full_path_nchars,
 672                         struct wim_dentry *parent,
 673                         struct winnt_scan_ctx *ctx)
 674 {
 675         void *buf;
 676         const size_t bufsize = 8192;
 677         IO_STATUS_BLOCK iosb;
 678         NTSTATUS status;
 679         int ret;
 680
 681         buf = MALLOC(bufsize);
 682         if (!buf)
 683                 return WIMLIB_ERR_NOMEM;
 684
 685         /* Using NtQueryDirectoryFile() we can re-use the same open handle,
 686          * which we opened with FILE_FLAG_BACKUP_SEMANTICS.  */
 687
 688         while (NT_SUCCESS(status = NtQueryDirectoryFile(h, NULL, NULL, NULL,
 689                                                         &iosb, buf, bufsize,
 690                                                         FileNamesInformation,
 691                                                         FALSE, NULL, FALSE)))
 692         {
 693                 const FILE_NAMES_INFORMATION *info = buf;
 694                 for (;;) {
 695                         if (!should_ignore_filename(info->FileName,
 696                                                     info->FileNameLength / 2))
 697                         {
 698                                 wchar_t *p;
 699                                 wchar_t *filename;
 700                                 struct wim_dentry *child;
 701
 702                                 p = full_path + full_path_nchars;
 703                                 /* Only add a backslash if we don't already have
 704                                  * one.  This prevents a duplicate backslash
 705                                  * from being added when the path to the capture
 706                                  * dir had a trailing backslash.  */
 707                                 if (*(p - 1) != L'\\')
 708                                         *p++ = L'\\';
 709                                 filename = p;
 710                                 p = wmempcpy(filename, info->FileName,
 711                                              info->FileNameLength / 2);
 712                                 *p = '\0';
 713
 714                                 ret = winnt_build_dentry_tree_recursive(
 715                                                         &child,
 716                                                         h,
 717                                                         full_path,
 718                                                         p - full_path,
 719                                                         filename,
 720                                                         info->FileNameLength / 2,
 721                                                         filename,
 722                                                         ctx);
 723
 724                                 full_path[full_path_nchars] = L'\0';
 725
 726                                 if (ret)
 727                                         goto out_free_buf;
 728                                 attach_scanned_tree(parent, child,
 729                                                     ctx->params->blob_table);
 730                         }
 731                         if (info->NextEntryOffset == 0)
 732                                 break;
 733                         info = (const FILE_NAMES_INFORMATION *)
 734                                         ((const u8 *)info + info->NextEntryOffset);
 735                 }
 736         }
 737
 738         if (unlikely(status != STATUS_NO_MORE_FILES)) {
 739                 winnt_error(status, L"\"%ls\": Can't read directory",
 740                             printable_path(full_path));
 741                 ret = WIMLIB_ERR_READ;
 742         }
 743 out_free_buf:
 744         FREE(buf);
 745         return ret;
 746 }
 747
 748 /* Reparse point fixup status code  */
 749 #define RP_FIXED        (-1)
 750
 751 static bool
 752 file_has_ino_and_dev(HANDLE h, u64 ino, u64 dev)
 753 {
 754         NTSTATUS status;
 755         IO_STATUS_BLOCK iosb;
 756         FILE_INTERNAL_INFORMATION int_info;
 757         FILE_FS_VOLUME_INFORMATION vol_info;
 758
 759         status = NtQueryInformationFile(h, &iosb, &int_info, sizeof(int_info),
 760                                         FileInternalInformation);
 761         if (!NT_SUCCESS(status))
 762                 return false;
 763
 764         if (int_info.IndexNumber.QuadPart != ino)
 765                 return false;
 766
 767         status = NtQueryVolumeInformationFile(h, &iosb,
 768                                               &vol_info, sizeof(vol_info),
 769                                               FileFsVolumeInformation);
 770         if (!(NT_SUCCESS(status) || status == STATUS_BUFFER_OVERFLOW))
 771                 return false;
 772
 773         if (iosb.Information <
 774              offsetof(FILE_FS_VOLUME_INFORMATION, VolumeSerialNumber) +
 775              sizeof(vol_info.VolumeSerialNumber))
 776                 return false;
 777
 778         return (vol_info.VolumeSerialNumber == dev);
 779 }
 780
 781 /*
 782  * This is the Windows equivalent of unix_relativize_link_target(); see there
 783  * for general details.  This version works with an "absolute" Windows link
 784  * target, specified from the root of the Windows kernel object namespace.  Note
 785  * that we have to open directories with a trailing slash when present because
 786  * \??\E: opens the E: device itself and not the filesystem root directory.
 787  */
 788 static const wchar_t *
 789 winnt_relativize_link_target(const wchar_t *target, size_t target_nbytes,
 790                              u64 ino, u64 dev)
 791 {
 792         UNICODE_STRING name;
 793         OBJECT_ATTRIBUTES attr;
 794         IO_STATUS_BLOCK iosb;
 795         NTSTATUS status;
 796         const wchar_t *target_end;
 797         const wchar_t *p;
 798
 799         target_end = target + (target_nbytes / sizeof(wchar_t));
 800
 801         /* Empty path??? */
 802         if (target_end == target)
 803                 return target;
 804
 805         /* No leading slash???  */
 806         if (target[0] != L'\\')
 807                 return target;
 808
 809         /* UNC path???  */
 810         if ((target_end - target) >= 2 &&
 811             target[0] == L'\\' && target[1] == L'\\')
 812                 return target;
 813
 814         attr.Length = sizeof(attr);
 815         attr.RootDirectory = NULL;
 816         attr.ObjectName = &name;
 817         attr.Attributes = 0;
 818         attr.SecurityDescriptor = NULL;
 819         attr.SecurityQualityOfService = NULL;
 820
 821         name.Buffer = (wchar_t *)target;
 822         name.Length = 0;
 823         p = target;
 824         do {
 825                 HANDLE h;
 826                 const wchar_t *orig_p = p;
 827
 828                 /* Skip non-backslashes  */
 829                 while (p != target_end && *p != L'\\')
 830                         p++;
 831
 832                 /* Skip backslashes  */
 833                 while (p != target_end && *p == L'\\')
 834                         p++;
 835
 836                 /* Append path component  */
 837                 name.Length += (p - orig_p) * sizeof(wchar_t);
 838                 name.MaximumLength = name.Length;
 839
 840                 /* Try opening the file  */
 841                 status = NtOpenFile(&h,
 842                                     FILE_READ_ATTRIBUTES | FILE_TRAVERSE,
 843                                     &attr,
 844                                     &iosb,
 845                                     FILE_SHARE_VALID_FLAGS,
 846                                     FILE_OPEN_FOR_BACKUP_INTENT);
 847
 848                 if (NT_SUCCESS(status)) {
 849                         /* Reset root directory  */
 850                         if (attr.RootDirectory)
 851                                 NtClose(attr.RootDirectory);
 852                         attr.RootDirectory = h;
 853                         name.Buffer = (wchar_t *)p;
 854                         name.Length = 0;
 855
 856                         if (file_has_ino_and_dev(h, ino, dev))
 857                                 goto out_close_root_dir;
 858                 }
 859         } while (p != target_end);
 860
 861         p = target;
 862
 863 out_close_root_dir:
 864         if (attr.RootDirectory)
 865                 NtClose(attr.RootDirectory);
 866         while (p > target && *(p - 1) == L'\\')
 867                 p--;
 868         return p;
 869 }
 870
 871 static int
 872 winnt_rpfix_progress(struct capture_params *params, const wchar_t *path,
 873                      const struct link_reparse_point *link, int scan_status)
 874 {
 875         size_t print_name_nchars = link->print_name_nbytes / sizeof(wchar_t);
 876         wchar_t print_name0[print_name_nchars + 1];
 877
 878         wmemcpy(print_name0, link->print_name, print_name_nchars);
 879         print_name0[print_name_nchars] = L'\0';
 880
 881         params->progress.scan.cur_path = path;
 882         params->progress.scan.symlink_target = print_name0;
 883         return do_capture_progress(params, scan_status, NULL);
 884 }
 885
 886 static int
 887 winnt_try_rpfix(struct reparse_buffer_disk *rpbuf, u16 *rpbuflen_p,
 888                 const wchar_t *path, struct capture_params *params)
 889 {
 890         struct link_reparse_point link;
 891         const wchar_t *rel_target;
 892         int ret;
 893
 894         if (parse_link_reparse_point(rpbuf, *rpbuflen_p, &link)) {
 895                 /* Couldn't understand the reparse data; don't do the fixup.  */
 896                 return 0;
 897         }
 898
 899         /*
 900          * Don't do reparse point fixups on relative symbolic links.
 901          *
 902          * On Windows, a relative symbolic link is supposed to be identifiable
 903          * by having reparse tag WIM_IO_REPARSE_TAG_SYMLINK and flags
 904          * SYMBOLIC_LINK_RELATIVE.  We will use this information, although this
 905          * may not always do what the user expects, since drive-relative
 906          * symbolic links such as "\Users\Public" have SYMBOLIC_LINK_RELATIVE
 907          * set, in addition to truly relative symbolic links such as "Users" or
 908          * "Users\Public".  However, WIMGAPI (as of Windows 8.1) has this same
 909          * behavior.
 910          *
 911          * Otherwise, as far as I can tell, the targets of symbolic links that
 912          * are NOT relative, as well as junctions (note: a mountpoint is the
 913          * sames thing as a junction), must be NT namespace paths, for example:
 914          *
 915          *     - \??\e:\Users\Public
 916          *     - \DosDevices\e:\Users\Public
 917          *     - \Device\HardDiskVolume4\Users\Public
 918          *     - \??\Volume{c47cb07c-946e-4155-b8f7-052e9cec7628}\Users\Public
 919          *     - \DosDevices\Volume{c47cb07c-946e-4155-b8f7-052e9cec7628}\Users\Public
 920          */
 921         if (link_is_relative_symlink(&link))
 922                 return 0;
 923
 924         rel_target = winnt_relativize_link_target(link.substitute_name,
 925                                                   link.substitute_name_nbytes,
 926                                                   params->capture_root_ino,
 927                                                   params->capture_root_dev);
 928
 929         if (rel_target == link.substitute_name) {
 930                 /* Target points outside of the tree being captured or had an
 931                  * unrecognized path format.  Don't adjust it.  */
 932                 return winnt_rpfix_progress(params, path, &link,
 933                                             WIMLIB_SCAN_DENTRY_NOT_FIXED_SYMLINK);
 934         }
 935
 936         /* We have an absolute target pointing within the directory being
 937          * captured. @rel_target is the suffix of the link target that is the
 938          * part relative to the directory being captured.
 939          *
 940          * We will cut off the prefix before this part (which is the path to the
 941          * directory being captured) and add a dummy prefix.  Since the process
 942          * will need to be reversed when applying the image, it doesn't matter
 943          * what exactly the prefix is, as long as it looks like an absolute
 944          * path.  */
 945
 946         static const wchar_t prefix[6] = L"\\??\\X:";
 947         static const size_t num_unprintable_chars = 4;
 948
 949         size_t rel_target_nbytes =
 950                 link.substitute_name_nbytes - ((const u8 *)rel_target -
 951                                                (const u8 *)link.substitute_name);
 952
 953         wchar_t tmp[(sizeof(prefix) + rel_target_nbytes) / sizeof(wchar_t)];
 954
 955         memcpy(tmp, prefix, sizeof(prefix));
 956         memcpy(tmp + ARRAY_LEN(prefix), rel_target, rel_target_nbytes);
 957
 958         link.substitute_name = tmp;
 959         link.substitute_name_nbytes = sizeof(tmp);
 960
 961         link.print_name = link.substitute_name + num_unprintable_chars;
 962         link.print_name_nbytes = link.substitute_name_nbytes -
 963                                  (num_unprintable_chars * sizeof(wchar_t));
 964
 965         if (make_link_reparse_point(&link, rpbuf, rpbuflen_p))
 966                 return 0;
 967
 968         ret = winnt_rpfix_progress(params, path, &link,
 969                                    WIMLIB_SCAN_DENTRY_FIXED_SYMLINK);
 970         if (ret)
 971                 return ret;
 972         return RP_FIXED;
 973 }
 974
 975 /* Load the reparse data of a file into the corresponding WIM inode.  If the
 976  * reparse point is a symbolic link or junction with an absolute target and
 977  * RPFIX mode is enabled, then also rewrite its target to be relative to the
 978  * capture root.  */
 979 static noinline_for_stack int
 980 winnt_load_reparse_data(HANDLE h, struct wim_inode *inode,
 981                         const wchar_t *full_path, struct capture_params *params)
 982 {
 983         struct reparse_buffer_disk rpbuf;
 984         NTSTATUS status;
 985         u32 len;
 986         u16 rpbuflen;
 987         int ret;
 988
 989         if (inode->i_attributes & FILE_ATTRIBUTE_ENCRYPTED) {
 990                 /* See comment above assign_stream_types_encrypted()  */
 991                 WARNING("Ignoring reparse data of encrypted file \"%ls\"",
 992                         printable_path(full_path));
 993                 return 0;
 994         }
 995
 996         status = winnt_fsctl(h, FSCTL_GET_REPARSE_POINT,
 997                              NULL, 0, &rpbuf, sizeof(rpbuf), &len);
 998         if (!NT_SUCCESS(status)) {
 999                 winnt_error(status, L"\"%ls\": Can't get reparse point",
1000                             printable_path(full_path));
1001                 return WIMLIB_ERR_READLINK;
1002         }
1003
1004         rpbuflen = len;
1005
1006         if (unlikely(rpbuflen < REPARSE_DATA_OFFSET)) {
1007                 ERROR("\"%ls\": reparse point buffer is too short",
1008                       printable_path(full_path));
1009                 return WIMLIB_ERR_INVALID_REPARSE_DATA;
1010         }
1011
1012         if (params->add_flags & WIMLIB_ADD_FLAG_RPFIX) {
1013                 ret = winnt_try_rpfix(&rpbuf, &rpbuflen, full_path, params);
1014                 if (ret == RP_FIXED)
1015                         inode->i_rp_flags &= ~WIM_RP_FLAG_NOT_FIXED;
1016                 else if (ret)
1017                         return ret;
1018         }
1019
1020         inode->i_reparse_tag = le32_to_cpu(rpbuf.rptag);
1021         inode->i_rp_reserved = le16_to_cpu(rpbuf.rpreserved);
1022
1023         if (!inode_add_stream_with_data(inode,
1024                                         STREAM_TYPE_REPARSE_POINT,
1025                                         NO_STREAM_NAME,
1026                                         rpbuf.rpdata,
1027                                         rpbuflen - REPARSE_DATA_OFFSET,
1028                                         params->blob_table))
1029                 return WIMLIB_ERR_NOMEM;
1030
1031         return 0;
1032 }
1033
1034 static DWORD WINAPI
1035 win32_tally_encrypted_size_cb(unsigned char *_data, void *_size_ret,
1036                               unsigned long len)
1037 {
1038         *(u64*)_size_ret += len;
1039         return ERROR_SUCCESS;
1040 }
1041
1042 static int
1043 win32_get_encrypted_file_size(const wchar_t *path, bool is_dir, u64 *size_ret)
1044 {
1045         DWORD err;
1046         void *file_ctx;
1047         int ret;
1048         DWORD flags = 0;
1049
1050         if (is_dir)
1051                 flags |= CREATE_FOR_DIR;
1052
1053         err = OpenEncryptedFileRaw(path, flags, &file_ctx);
1054         if (err != ERROR_SUCCESS) {
1055                 win32_error(err,
1056                             L"Failed to open encrypted file \"%ls\" for raw read",
1057                             printable_path(path));
1058                 return WIMLIB_ERR_OPEN;
1059         }
1060         *size_ret = 0;
1061         err = ReadEncryptedFileRaw(win32_tally_encrypted_size_cb,
1062                                    size_ret, file_ctx);
1063         if (err != ERROR_SUCCESS) {
1064                 win32_error(err,
1065                             L"Failed to read raw encrypted data from \"%ls\"",
1066                             printable_path(path));
1067                 ret = WIMLIB_ERR_READ;
1068         } else {
1069                 ret = 0;
1070         }
1071         CloseEncryptedFileRaw(file_ctx);
1072         return ret;
1073 }
1074
1075 static int
1076 winnt_scan_efsrpc_raw_data(struct wim_inode *inode,
1077                            wchar_t *path, size_t path_nchars,
1078                            struct winnt_scan_ctx *ctx)
1079 {
1080         const bool is_dir = (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY);
1081         struct windows_file *windows_file;
1082         u64 size;
1083         int ret;
1084
1085         /* OpenEncryptedFileRaw() expects a Win32 name.  */
1086         wimlib_assert(!wmemcmp(path, L"\\??\\", 4));
1087         path[1] = L'\\';
1088
1089         ret = win32_get_encrypted_file_size(path, is_dir, &size);
1090         if (ret)
1091                 goto out;
1092
1093         /* Empty EFSRPC data does not make sense  */
1094         wimlib_assert(size != 0);
1095
1096         windows_file = alloc_windows_file(path, path_nchars, NULL, 0,
1097                                           ctx->snapshot, true);
1098         ret = add_stream(inode, windows_file, size, STREAM_TYPE_EFSRPC_RAW_DATA,
1099                          NO_STREAM_NAME, ctx->params->unhashed_blobs);
1100 out:
1101         path[1] = L'?';
1102         return ret;
1103 }
1104
1105 static bool
1106 get_data_stream_name(const wchar_t *raw_stream_name, size_t raw_stream_name_nchars,
1107                      const wchar_t **stream_name_ret, size_t *stream_name_nchars_ret)
1108 {
1109         const wchar_t *sep, *type, *end;
1110
1111         /* The stream name should be returned as :NAME:TYPE  */
1112         if (raw_stream_name_nchars < 1)
1113                 return false;
1114         if (raw_stream_name[0] != L':')
1115                 return false;
1116
1117         raw_stream_name++;
1118         raw_stream_name_nchars--;
1119
1120         end = raw_stream_name + raw_stream_name_nchars;
1121
1122         sep = wmemchr(raw_stream_name, L':', raw_stream_name_nchars);
1123         if (!sep)
1124                 return false;
1125
1126         type = sep + 1;
1127         if (end - type != 5)
1128                 return false;
1129
1130         if (wmemcmp(type, L"$DATA", 5))
1131                 return false;
1132
1133         *stream_name_ret = raw_stream_name;
1134         *stream_name_nchars_ret = sep - raw_stream_name;
1135         return true;
1136 }
1137
1138 static int
1139 winnt_scan_data_stream(const wchar_t *path, size_t path_nchars,
1140                        wchar_t *raw_stream_name, size_t raw_stream_name_nchars,
1141                        u64 stream_size, struct wim_inode *inode,
1142                        struct winnt_scan_ctx *ctx)
1143 {
1144         wchar_t *stream_name;
1145         size_t stream_name_nchars;
1146         struct windows_file *windows_file;
1147
1148         /* Given the raw stream name (which is something like
1149          * :streamname:$DATA), extract just the stream name part (streamname).
1150          * Ignore any non-$DATA streams.  */
1151         if (!get_data_stream_name(raw_stream_name, raw_stream_name_nchars,
1152                                   (const wchar_t **)&stream_name,
1153                                   &stream_name_nchars))
1154                 return 0;
1155
1156         stream_name[stream_name_nchars] = L'\0';
1157
1158         windows_file = alloc_windows_file(path, path_nchars,
1159                                           stream_name, stream_name_nchars,
1160                                           ctx->snapshot, false);
1161         return add_stream(inode, windows_file, stream_size, STREAM_TYPE_DATA,
1162                           stream_name, ctx->params->unhashed_blobs);
1163 }
1164
1165 /*
1166  * Load information about the data streams of an open file into a WIM inode.
1167  *
1168  * We use the NtQueryInformationFile() system call instead of FindFirstStream()
1169  * and FindNextStream().  This is done for two reasons:
1170  *
1171  * - FindFirstStream() opens its own handle to the file or directory and
1172  *   apparently does so without specifying FILE_FLAG_BACKUP_SEMANTICS, thereby
1173  *   causing access denied errors on certain files (even when running as the
1174  *   Administrator).
1175  * - FindFirstStream() and FindNextStream() is only available on Windows Vista
1176  *   and later, whereas the stream support in NtQueryInformationFile() was
1177  *   already present in Windows XP.
1178  */
1179 static noinline_for_stack int
1180 winnt_scan_data_streams(HANDLE h, const wchar_t *path, size_t path_nchars,
1181                         struct wim_inode *inode, u64 file_size,
1182                         struct winnt_scan_ctx *ctx)
1183 {
1184         int ret;
1185         u8 _buf[4096] _aligned_attribute(8);
1186         u8 *buf;
1187         size_t bufsize;
1188         IO_STATUS_BLOCK iosb;
1189         NTSTATUS status;
1190         FILE_STREAM_INFORMATION *info;
1191
1192         buf = _buf;
1193         bufsize = sizeof(_buf);
1194
1195         if (!(ctx->vol_flags & FILE_NAMED_STREAMS))
1196                 goto unnamed_only;
1197
1198         /* Get a buffer containing the stream information.  */
1199         while (!NT_SUCCESS(status = NtQueryInformationFile(h,
1200                                                            &iosb,
1201                                                            buf,
1202                                                            bufsize,
1203                                                            FileStreamInformation)))
1204         {
1205
1206                 switch (status) {
1207                 case STATUS_BUFFER_OVERFLOW:
1208                         {
1209                                 u8 *newbuf;
1210
1211                                 bufsize *= 2;
1212                                 if (buf == _buf)
1213                                         newbuf = MALLOC(bufsize);
1214                                 else
1215                                         newbuf = REALLOC(buf, bufsize);
1216                                 if (!newbuf) {
1217                                         ret = WIMLIB_ERR_NOMEM;
1218                                         goto out_free_buf;
1219                                 }
1220                                 buf = newbuf;
1221                         }
1222                         break;
1223                 case STATUS_NOT_IMPLEMENTED:
1224                 case STATUS_NOT_SUPPORTED:
1225                 case STATUS_INVALID_INFO_CLASS:
1226                         goto unnamed_only;
1227                 default:
1228                         winnt_error(status,
1229                                     L"\"%ls\": Failed to query stream information",
1230                                     printable_path(path));
1231                         ret = WIMLIB_ERR_READ;
1232                         goto out_free_buf;
1233                 }
1234         }
1235
1236         if (iosb.Information == 0) {
1237                 /* No stream information.  */
1238                 ret = 0;
1239                 goto out_free_buf;
1240         }
1241
1242         /* Parse one or more stream information structures.  */
1243         info = (FILE_STREAM_INFORMATION *)buf;
1244         for (;;) {
1245                 /* Load the stream information.  */
1246                 ret = winnt_scan_data_stream(path, path_nchars,
1247                                              info->StreamName,
1248                                              info->StreamNameLength / 2,
1249                                              info->StreamSize.QuadPart,
1250                                              inode, ctx);
1251                 if (ret)
1252                         goto out_free_buf;
1253
1254                 if (info->NextEntryOffset == 0) {
1255                         /* No more stream information.  */
1256                         break;
1257                 }
1258                 /* Advance to next stream information.  */
1259                 info = (FILE_STREAM_INFORMATION *)
1260                                 ((u8 *)info + info->NextEntryOffset);
1261         }
1262         ret = 0;
1263         goto out_free_buf;
1264
1265 unnamed_only:
1266         /* The volume does not support named streams.  Only capture the unnamed
1267          * data stream.  */
1268         if (inode->i_attributes & (FILE_ATTRIBUTE_DIRECTORY |
1269                                    FILE_ATTRIBUTE_REPARSE_POINT))
1270         {
1271                 ret = 0;
1272                 goto out_free_buf;
1273         }
1274
1275         {
1276                 wchar_t stream_name[] = L"::$DATA";
1277                 ret = winnt_scan_data_stream(path, path_nchars, stream_name, 7,
1278                                              file_size, inode, ctx);
1279         }
1280 out_free_buf:
1281         /* Free buffer if allocated on heap.  */
1282         if (unlikely(buf != _buf))
1283                 FREE(buf);
1284         return ret;
1285 }
1286
1287 static u64
1288 extract_starting_lcn(const RETRIEVAL_POINTERS_BUFFER *extents)
1289 {
1290         if (extents->ExtentCount < 1)
1291                 return 0;
1292
1293         return extents->Extents[0].Lcn.QuadPart;
1294 }
1295
1296 static noinline_for_stack u64
1297 get_sort_key(HANDLE h)
1298 {
1299         STARTING_VCN_INPUT_BUFFER in = { .StartingVcn.QuadPart = 0 };
1300         RETRIEVAL_POINTERS_BUFFER out;
1301
1302         if (!NT_SUCCESS(winnt_fsctl(h, FSCTL_GET_RETRIEVAL_POINTERS,
1303                                     &in, sizeof(in), &out, sizeof(out), NULL)))
1304                 return 0;
1305
1306         return extract_starting_lcn(&out);
1307 }
1308
1309 static void
1310 set_sort_key(struct wim_inode *inode, u64 sort_key)
1311 {
1312         for (unsigned i = 0; i < inode->i_num_streams; i++) {
1313                 struct wim_inode_stream *strm = &inode->i_streams[i];
1314                 struct blob_descriptor *blob = stream_blob_resolved(strm);
1315                 if (blob && blob->blob_location == BLOB_IN_WINDOWS_FILE)
1316                         blob->windows_file->sort_key = sort_key;
1317         }
1318 }
1319
1320 static inline bool
1321 should_try_to_use_wimboot_hash(const struct wim_inode *inode,
1322                                const struct winnt_scan_ctx *ctx,
1323                                const struct capture_params *params)
1324 {
1325         /* Directories and encrypted files aren't valid for external backing. */
1326         if (inode->i_attributes & (FILE_ATTRIBUTE_DIRECTORY |
1327                                    FILE_ATTRIBUTE_ENCRYPTED))
1328                 return false;
1329
1330         /* If the file is a reparse point, then try the hash fixup if it's a WOF
1331          * reparse point and we're in WIMBOOT mode.  Otherwise, try the hash
1332          * fixup if WOF may be attached. */
1333         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)
1334                 return (inode->i_reparse_tag == WIM_IO_REPARSE_TAG_WOF) &&
1335                         (params->add_flags & WIMLIB_ADD_FLAG_WIMBOOT);
1336         return !ctx->wof_not_attached;
1337 }
1338
1339 /*
1340  * This function implements an optimization for capturing files from a
1341  * filesystem with a backing WIM(s).  If a file is WIM-backed, then we can
1342  * retrieve the SHA-1 message digest of its original contents from its reparse
1343  * point.  This may eliminate the need to read the file's data and/or allow the
1344  * file's data to be immediately deduplicated with existing data in the WIM.
1345  *
1346  * If WOF is attached, then this function is merely an optimization, but
1347  * potentially a very effective one.  If WOF is detached, then this function
1348  * really causes WIM-backed files to be, effectively, automatically
1349  * "dereferenced" when possible; the unnamed data stream is updated to reference
1350  * the original contents and the reparse point is removed.
1351  *
1352  * This function returns 0 if the fixup succeeded or was intentionally not
1353  * executed.  Otherwise it returns an error code.
1354  */
1355 static noinline_for_stack int
1356 try_to_use_wimboot_hash(HANDLE h, struct wim_inode *inode,
1357                         struct winnt_scan_ctx *ctx, const wchar_t *full_path)
1358 {
1359         struct blob_table *blob_table = ctx->params->blob_table;
1360         struct wim_inode_stream *reparse_strm = NULL;
1361         struct wim_inode_stream *strm;
1362         struct blob_descriptor *blob;
1363         u8 hash[SHA1_HASH_SIZE];
1364         int ret;
1365
1366         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
1367                 struct reparse_buffer_disk rpbuf;
1368                 struct {
1369                         struct wof_external_info wof_info;
1370                         struct wim_provider_rpdata wim_info;
1371                 } *rpdata = (void *)rpbuf.rpdata;
1372                 struct blob_descriptor *reparse_blob;
1373
1374                 /* The file has a WOF reparse point, so WOF must be detached.
1375                  * We can read the reparse point directly.  */
1376                 ctx->wof_not_attached = true;
1377                 reparse_strm = inode_get_unnamed_stream(inode, STREAM_TYPE_REPARSE_POINT);
1378                 reparse_blob = stream_blob_resolved(reparse_strm);
1379
1380                 if (!reparse_blob || reparse_blob->size < sizeof(*rpdata))
1381                         return 0;  /* Not a WIM-backed file  */
1382
1383                 ret = read_blob_into_buf(reparse_blob, rpdata);
1384                 if (ret)
1385                         return ret;
1386
1387                 if (rpdata->wof_info.version != WOF_CURRENT_VERSION ||
1388                     rpdata->wof_info.provider != WOF_PROVIDER_WIM ||
1389                     rpdata->wim_info.version != 2)
1390                         return 0;  /* Not a WIM-backed file  */
1391
1392                 /* Okay, this is a WIM backed file.  Get its SHA-1 hash.  */
1393                 copy_hash(hash, rpdata->wim_info.unnamed_data_stream_hash);
1394         } else {
1395                 struct {
1396                         struct wof_external_info wof_info;
1397                         struct wim_provider_external_info wim_info;
1398                 } out;
1399                 NTSTATUS status;
1400
1401                 /* WOF may be attached.  Try reading this file's external
1402                  * backing info.  */
1403                 status = winnt_fsctl(h, FSCTL_GET_EXTERNAL_BACKING,
1404                                      NULL, 0, &out, sizeof(out), NULL);
1405
1406                 /* Is WOF not attached?  */
1407                 if (status == STATUS_INVALID_DEVICE_REQUEST ||
1408                     status == STATUS_NOT_SUPPORTED) {
1409                         ctx->wof_not_attached = true;
1410                         return 0;
1411                 }
1412
1413                 /* Is this file not externally backed?  */
1414                 if (status == STATUS_OBJECT_NOT_EXTERNALLY_BACKED)
1415                         return 0;
1416
1417                 /* Does this file have an unknown type of external backing that
1418                  * needed a larger information buffer?  */
1419                 if (status == STATUS_BUFFER_TOO_SMALL)
1420                         return 0;
1421
1422                 /* Was there some other failure?  */
1423                 if (status != STATUS_SUCCESS) {
1424                         winnt_error(status,
1425                                     L"\"%ls\": FSCTL_GET_EXTERNAL_BACKING failed",
1426                                     full_path);
1427                         return WIMLIB_ERR_STAT;
1428                 }
1429
1430                 /* Is this file backed by a WIM?  */
1431                 if (out.wof_info.version != WOF_CURRENT_VERSION ||
1432                     out.wof_info.provider != WOF_PROVIDER_WIM ||
1433                     out.wim_info.version != WIM_PROVIDER_CURRENT_VERSION)
1434                         return 0;
1435
1436                 /* Okay, this is a WIM backed file.  Get its SHA-1 hash.  */
1437                 copy_hash(hash, out.wim_info.unnamed_data_stream_hash);
1438         }
1439
1440         /* If the file's unnamed data stream is nonempty, then fill in its hash
1441          * and deduplicate it if possible.
1442          *
1443          * With WOF detached, we require that the blob *must* de-duplicable for
1444          * any action can be taken, since without WOF we can't fall back to
1445          * getting the "dereferenced" data by reading the stream (the real
1446          * stream is sparse and contains all zeroes).  */
1447         strm = inode_get_unnamed_data_stream(inode);
1448         if (strm && (blob = stream_blob_resolved(strm))) {
1449                 struct blob_descriptor **back_ptr;
1450
1451                 if (reparse_strm && !lookup_blob(blob_table, hash))
1452                         return 0;
1453                 back_ptr = retrieve_pointer_to_unhashed_blob(blob);
1454                 copy_hash(blob->hash, hash);
1455                 if (after_blob_hashed(blob, back_ptr, blob_table) != blob)
1456                         free_blob_descriptor(blob);
1457         }
1458
1459         /* Remove the reparse point, if present.  */
1460         if (reparse_strm) {
1461                 inode_remove_stream(inode, reparse_strm, blob_table);
1462                 inode->i_attributes &= ~(FILE_ATTRIBUTE_REPARSE_POINT |
1463                                          FILE_ATTRIBUTE_SPARSE_FILE);
1464                 if (inode->i_attributes == 0)
1465                         inode->i_attributes = FILE_ATTRIBUTE_NORMAL;
1466         }
1467
1468         return 0;
1469 }
1470
1471 struct file_info {
1472         u32 attributes;
1473         u32 num_links;
1474         u64 creation_time;
1475         u64 last_write_time;
1476         u64 last_access_time;
1477         u64 ino;
1478         u64 end_of_file;
1479 };
1480
1481 static noinline_for_stack NTSTATUS
1482 get_file_info(HANDLE h, struct file_info *info)
1483 {
1484         IO_STATUS_BLOCK iosb;
1485         NTSTATUS status;
1486         FILE_ALL_INFORMATION all_info;
1487
1488         status = NtQueryInformationFile(h, &iosb, &all_info, sizeof(all_info),
1489                                         FileAllInformation);
1490
1491         if (unlikely(!NT_SUCCESS(status) && status != STATUS_BUFFER_OVERFLOW))
1492                 return status;
1493
1494         info->attributes = all_info.BasicInformation.FileAttributes;
1495         info->num_links = all_info.StandardInformation.NumberOfLinks;
1496         info->creation_time = all_info.BasicInformation.CreationTime.QuadPart;
1497         info->last_write_time = all_info.BasicInformation.LastWriteTime.QuadPart;
1498         info->last_access_time = all_info.BasicInformation.LastAccessTime.QuadPart;
1499         info->ino = all_info.InternalInformation.IndexNumber.QuadPart;
1500         info->end_of_file = all_info.StandardInformation.EndOfFile.QuadPart;
1501         return STATUS_SUCCESS;
1502 }
1503
1504 static void
1505 get_volume_information(HANDLE h, const wchar_t *full_path,
1506                        struct winnt_scan_ctx *ctx)
1507 {
1508         u8 _attr_info[sizeof(FILE_FS_ATTRIBUTE_INFORMATION) + 128] _aligned_attribute(8);
1509         FILE_FS_ATTRIBUTE_INFORMATION *attr_info = (void *)_attr_info;
1510         FILE_FS_VOLUME_INFORMATION vol_info;
1511         struct file_info file_info;
1512         IO_STATUS_BLOCK iosb;
1513         NTSTATUS status;
1514
1515         /* Get volume flags  */
1516         status = NtQueryVolumeInformationFile(h, &iosb, attr_info,
1517                                               sizeof(_attr_info),
1518                                               FileFsAttributeInformation);
1519         if (NT_SUCCESS(status)) {
1520                 ctx->vol_flags = attr_info->FileSystemAttributes;
1521                 ctx->is_ntfs = (attr_info->FileSystemNameLength == 4 * sizeof(wchar_t)) &&
1522                                 !wmemcmp(attr_info->FileSystemName, L"NTFS", 4);
1523         } else {
1524                 winnt_warning(status, L"\"%ls\": Can't get volume attributes",
1525                               printable_path(full_path));
1526         }
1527
1528         /* Get volume ID.  */
1529         status = NtQueryVolumeInformationFile(h, &iosb, &vol_info,
1530                                               sizeof(vol_info),
1531                                               FileFsVolumeInformation);
1532         if ((NT_SUCCESS(status) || status == STATUS_BUFFER_OVERFLOW) &&
1533             (iosb.Information >= offsetof(FILE_FS_VOLUME_INFORMATION,
1534                                           VolumeSerialNumber) +
1535              sizeof(vol_info.VolumeSerialNumber)))
1536         {
1537                 ctx->params->capture_root_dev = vol_info.VolumeSerialNumber;
1538         } else {
1539                 winnt_warning(status, L"\"%ls\": Can't get volume ID",
1540                               printable_path(full_path));
1541         }
1542
1543         /* Get inode number.  */
1544         status = get_file_info(h, &file_info);
1545         if (NT_SUCCESS(status)) {
1546                 ctx->params->capture_root_ino = file_info.ino;
1547         } else {
1548                 winnt_warning(status, L"\"%ls\": Can't get file information",
1549                               printable_path(full_path));
1550         }
1551 }
1552
1553 static int
1554 winnt_build_dentry_tree_recursive(struct wim_dentry **root_ret,
1555                                   HANDLE cur_dir,
1556                                   wchar_t *full_path,
1557                                   size_t full_path_nchars,
1558                                   wchar_t *relative_path,
1559                                   size_t relative_path_nchars,
1560                                   const wchar_t *filename,
1561                                   struct winnt_scan_ctx *ctx)
1562 {
1563         struct wim_dentry *root = NULL;
1564         struct wim_inode *inode = NULL;
1565         HANDLE h = NULL;
1566         int ret;
1567         NTSTATUS status;
1568         struct file_info file_info;
1569         u64 sort_key;
1570
1571         ret = try_exclude(full_path, ctx->params);
1572         if (unlikely(ret < 0)) /* Excluded? */
1573                 goto out_progress;
1574         if (unlikely(ret > 0)) /* Error? */
1575                 goto out;
1576
1577         /* Open the file with permission to read metadata.  Although we will
1578          * later need a handle with FILE_LIST_DIRECTORY permission (or,
1579          * equivalently, FILE_READ_DATA; they're the same numeric value) if the
1580          * file is a directory, it can significantly slow things down to request
1581          * this permission on all nondirectories.  Perhaps it causes Windows to
1582          * start prefetching the file contents...  */
1583         status = winnt_openat(cur_dir, relative_path, relative_path_nchars,
1584                               FILE_READ_ATTRIBUTES | READ_CONTROL |
1585                                         ACCESS_SYSTEM_SECURITY,
1586                               &h);
1587         if (unlikely(!NT_SUCCESS(status))) {
1588                 if (status == STATUS_DELETE_PENDING) {
1589                         WARNING("\"%ls\": Deletion pending; skipping file",
1590                                 printable_path(full_path));
1591                         ret = 0;
1592                         goto out;
1593                 }
1594                 if (status == STATUS_SHARING_VIOLATION) {
1595                         ERROR("Can't open \"%ls\":\n"
1596                               "        File is in use by another process! "
1597                               "Consider using snapshot (VSS) mode.",
1598                               printable_path(full_path));
1599                         ret = WIMLIB_ERR_OPEN;
1600                         goto out;
1601                 }
1602                 winnt_error(status, L"\"%ls\": Can't open file",
1603                             printable_path(full_path));
1604                 if (status == STATUS_FVE_LOCKED_VOLUME)
1605                         ret = WIMLIB_ERR_FVE_LOCKED_VOLUME;
1606                 else
1607                         ret = WIMLIB_ERR_OPEN;
1608                 goto out;
1609         }
1610
1611         /* Get information about the file.  */
1612         status = get_file_info(h, &file_info);
1613         if (!NT_SUCCESS(status)) {
1614                 winnt_error(status, L"\"%ls\": Can't get file information",
1615                             printable_path(full_path));
1616                 ret = WIMLIB_ERR_STAT;
1617                 goto out;
1618         }
1619
1620         /* Create a WIM dentry with an associated inode, which may be shared.
1621          *
1622          * However, we need to explicitly check for directories and files with
1623          * only 1 link and refuse to hard link them.  This is because Windows
1624          * has a bug where it can return duplicate File IDs for files and
1625          * directories on the FAT filesystem.
1626          *
1627          * Since we don't follow mount points on Windows, we don't need to query
1628          * the volume ID per-file.  Just once, for the root, is enough.  But we
1629          * can't simply pass 0, because then there could be inode collisions
1630          * among multiple calls to win32_build_dentry_tree() that are scanning
1631          * files on different volumes.  */
1632         ret = inode_table_new_dentry(ctx->params->inode_table,
1633                                      filename,
1634                                      file_info.ino,
1635                                      ctx->params->capture_root_dev,
1636                                      (file_info.num_links <= 1),
1637                                      &root);
1638         if (ret)
1639                 goto out;
1640
1641         /* Get the short (DOS) name of the file.  */
1642         status = winnt_get_short_name(h, root);
1643
1644         /* If we can't read the short filename for any reason other than
1645          * out-of-memory, just ignore the error and assume the file has no short
1646          * name.  This shouldn't be an issue, since the short names are
1647          * essentially obsolete anyway.  */
1648         if (unlikely(status == STATUS_NO_MEMORY)) {
1649                 ret = WIMLIB_ERR_NOMEM;
1650                 goto out;
1651         }
1652
1653         inode = root->d_inode;
1654
1655         if (inode->i_nlink > 1) {
1656                 /* Shared inode (hard link); skip reading per-inode information.
1657                  */
1658                 goto out_progress;
1659         }
1660
1661         inode->i_attributes = file_info.attributes;
1662         inode->i_creation_time = file_info.creation_time;
1663         inode->i_last_write_time = file_info.last_write_time;
1664         inode->i_last_access_time = file_info.last_access_time;
1665
1666         /* Get the file's security descriptor, unless we are capturing in
1667          * NO_ACLS mode or the volume does not support security descriptors.  */
1668         if (!(ctx->params->add_flags & WIMLIB_ADD_FLAG_NO_ACLS)
1669             && (ctx->vol_flags & FILE_PERSISTENT_ACLS))
1670         {
1671                 ret = winnt_load_security_descriptor(h, inode, full_path, ctx);
1672                 if (ret)
1673                         goto out;
1674         }
1675
1676         /* If this is a reparse point, load the reparse data.  */
1677         if (unlikely(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)) {
1678                 ret = winnt_load_reparse_data(h, inode, full_path, ctx->params);
1679                 if (ret)
1680                         goto out;
1681         }
1682
1683         sort_key = get_sort_key(h);
1684
1685         if (unlikely(inode->i_attributes & FILE_ATTRIBUTE_ENCRYPTED)) {
1686                 /* Load information about the raw encrypted data.  This is
1687                  * needed for any directory or non-directory that has
1688                  * FILE_ATTRIBUTE_ENCRYPTED set.
1689                  *
1690                  * Note: since OpenEncryptedFileRaw() fails with
1691                  * ERROR_SHARING_VIOLATION if there are any open handles to the
1692                  * file, we have to close the file and re-open it later if
1693                  * needed.  */
1694                 NtClose(h);
1695                 h = NULL;
1696                 ret = winnt_scan_efsrpc_raw_data(inode, full_path,
1697                                                  full_path_nchars, ctx);
1698                 if (ret)
1699                         goto out;
1700         } else {
1701                 /*
1702                  * Load information about data streams (unnamed and named).
1703                  *
1704                  * Skip this step for encrypted files, since the data from
1705                  * ReadEncryptedFileRaw() already contains all data streams (and
1706                  * they do in fact all get restored by WriteEncryptedFileRaw().)
1707                  *
1708                  * Note: WIMGAPI (as of Windows 8.1) gets wrong and stores both
1709                  * the EFSRPC data and the named data stream(s)...!
1710                  */
1711                 ret = winnt_scan_data_streams(h,
1712                                               full_path,
1713                                               full_path_nchars,
1714                                               inode,
1715                                               file_info.end_of_file,
1716                                               ctx);
1717                 if (ret)
1718                         goto out;
1719         }
1720
1721         if (unlikely(should_try_to_use_wimboot_hash(inode, ctx, ctx->params))) {
1722                 ret = try_to_use_wimboot_hash(h, inode, ctx, full_path);
1723                 if (ret)
1724                         goto out;
1725         }
1726
1727         set_sort_key(inode, sort_key);
1728
1729         if (inode_is_directory(inode)) {
1730
1731                 /* Directory: recurse to children.  */
1732
1733                 /* Re-open the directory with FILE_LIST_DIRECTORY access.  */
1734                 if (h) {
1735                         NtClose(h);
1736                         h = NULL;
1737                 }
1738                 status = winnt_openat(cur_dir, relative_path,
1739                                       relative_path_nchars, FILE_LIST_DIRECTORY,
1740                                       &h);
1741                 if (!NT_SUCCESS(status)) {
1742                         winnt_error(status, L"\"%ls\": Can't open directory",
1743                                     printable_path(full_path));
1744                         ret = WIMLIB_ERR_OPEN;
1745                         goto out;
1746                 }
1747                 ret = winnt_recurse_directory(h,
1748                                               full_path,
1749                                               full_path_nchars,
1750                                               root,
1751                                               ctx);
1752                 if (ret)
1753                         goto out;
1754         }
1755
1756 out_progress:
1757         ctx->params->progress.scan.cur_path = full_path;
1758         if (likely(root))
1759                 ret = do_capture_progress(ctx->params, WIMLIB_SCAN_DENTRY_OK, inode);
1760         else
1761                 ret = do_capture_progress(ctx->params, WIMLIB_SCAN_DENTRY_EXCLUDED, NULL);
1762 out:
1763         if (likely(h))
1764                 NtClose(h);
1765         if (unlikely(ret)) {
1766                 free_dentry_tree(root, ctx->params->blob_table);
1767                 root = NULL;
1768                 ret = report_capture_error(ctx->params, ret, full_path);
1769         }
1770         *root_ret = root;
1771         return ret;
1772 }
1773
1774 static void
1775 winnt_do_scan_warnings(const wchar_t *path, const struct winnt_scan_ctx *ctx)
1776 {
1777         if (likely(ctx->num_get_sacl_priv_notheld == 0 &&
1778                    ctx->num_get_sd_access_denied == 0))
1779                 return;
1780
1781         WARNING("Scan of \"%ls\" complete, but with one or more warnings:", path);
1782         if (ctx->num_get_sacl_priv_notheld != 0) {
1783                 WARNING("- Could not capture SACL (System Access Control List)\n"
1784                         "            on %lu files or directories.",
1785                         ctx->num_get_sacl_priv_notheld);
1786         }
1787         if (ctx->num_get_sd_access_denied != 0) {
1788                 WARNING("- Could not capture security descriptor at all\n"
1789                         "            on %lu files or directories.",
1790                         ctx->num_get_sd_access_denied);
1791         }
1792         WARNING("To fully capture all security descriptors, run the program\n"
1793                 "          with Administrator rights.");
1794 }
1795
1796 /*----------------------------------------------------------------------------*
1797  *                         Fast MFT scan implementation                       *
1798  *----------------------------------------------------------------------------*/
1799
1800 #define ENABLE_FAST_MFT_SCAN    1
1801
1802 #ifdef ENABLE_FAST_MFT_SCAN
1803
1804 typedef struct {
1805         u64 StartingCluster;
1806         u64 ClusterCount;
1807 } CLUSTER_RANGE;
1808
1809 typedef struct {
1810         u64 StartingFileReferenceNumber;
1811         u64 EndingFileReferenceNumber;
1812 } FILE_REFERENCE_RANGE;
1813
1814 /* The FSCTL_QUERY_FILE_LAYOUT ioctl.  This ioctl can be used on Windows 8 and
1815  * later to scan the MFT of an NTFS volume.  */
1816 #define FSCTL_QUERY_FILE_LAYOUT         CTL_CODE(FILE_DEVICE_FILE_SYSTEM, 157, METHOD_NEITHER, FILE_ANY_ACCESS)
1817
1818 /* The input to FSCTL_QUERY_FILE_LAYOUT  */
1819 typedef struct {
1820         u32 NumberOfPairs;
1821 #define QUERY_FILE_LAYOUT_RESTART                                       0x00000001
1822 #define QUERY_FILE_LAYOUT_INCLUDE_NAMES                                 0x00000002
1823 #define QUERY_FILE_LAYOUT_INCLUDE_STREAMS                               0x00000004
1824 #define QUERY_FILE_LAYOUT_INCLUDE_EXTENTS                               0x00000008
1825 #define QUERY_FILE_LAYOUT_INCLUDE_EXTRA_INFO                            0x00000010
1826 #define QUERY_FILE_LAYOUT_INCLUDE_STREAMS_WITH_NO_CLUSTERS_ALLOCATED    0x00000020
1827         u32 Flags;
1828 #define QUERY_FILE_LAYOUT_FILTER_TYPE_NONE              0
1829 #define QUERY_FILE_LAYOUT_FILTER_TYPE_CLUSTERS          1
1830 #define QUERY_FILE_LAYOUT_FILTER_TYPE_FILEID            2
1831 #define QUERY_FILE_LAYOUT_NUM_FILTER_TYPES              3
1832         u32 FilterType;
1833         u32 Reserved;
1834         union {
1835                 CLUSTER_RANGE ClusterRanges[1];
1836                 FILE_REFERENCE_RANGE FileReferenceRanges[1];
1837         } Filter;
1838 } QUERY_FILE_LAYOUT_INPUT;
1839
1840 /* The header of the buffer returned by FSCTL_QUERY_FILE_LAYOUT  */
1841 typedef struct {
1842         u32 FileEntryCount;
1843         u32 FirstFileOffset;
1844 #define QUERY_FILE_LAYOUT_SINGLE_INSTANCED                              0x00000001
1845         u32 Flags;
1846         u32 Reserved;
1847 } QUERY_FILE_LAYOUT_OUTPUT;
1848
1849 /* Inode information returned by FSCTL_QUERY_FILE_LAYOUT  */
1850 typedef struct {
1851         u32 Version;
1852         u32 NextFileOffset;
1853         u32 Flags;
1854         u32 FileAttributes;
1855         u64 FileReferenceNumber;
1856         u32 FirstNameOffset;
1857         u32 FirstStreamOffset;
1858         u32 ExtraInfoOffset;
1859         u32 Reserved;
1860 } FILE_LAYOUT_ENTRY;
1861
1862 /* Extra inode information returned by FSCTL_QUERY_FILE_LAYOUT  */
1863 typedef struct {
1864         struct {
1865                 u64 CreationTime;
1866                 u64 LastAccessTime;
1867                 u64 LastWriteTime;
1868                 u64 ChangeTime;
1869                 u32 FileAttributes;
1870         } BasicInformation;
1871         u32 OwnerId;
1872         u32 SecurityId;
1873         s64 Usn;
1874 } FILE_LAYOUT_INFO_ENTRY;
1875
1876 /* Filename (or dentry) information returned by FSCTL_QUERY_FILE_LAYOUT  */
1877 typedef struct {
1878         u32 NextNameOffset;
1879 #define FILE_LAYOUT_NAME_ENTRY_PRIMARY  0x00000001
1880 #define FILE_LAYOUT_NAME_ENTRY_DOS      0x00000002
1881         u32 Flags;
1882         u64 ParentFileReferenceNumber;
1883         u32 FileNameLength;
1884         u32 Reserved;
1885         wchar_t FileName[1];
1886 } FILE_LAYOUT_NAME_ENTRY;
1887
1888 /* Stream information returned by FSCTL_QUERY_FILE_LAYOUT  */
1889 typedef struct {
1890         u32 Version;
1891         u32 NextStreamOffset;
1892 #define STREAM_LAYOUT_ENTRY_IMMOVABLE                   0x00000001
1893 #define STREAM_LAYOUT_ENTRY_PINNED                      0x00000002
1894 #define STREAM_LAYOUT_ENTRY_RESIDENT                    0x00000004
1895 #define STREAM_LAYOUT_ENTRY_NO_CLUSTERS_ALLOCATED       0x00000008
1896         u32 Flags;
1897         u32 ExtentInformationOffset;
1898         u64 AllocationSize;
1899         u64 EndOfFile;
1900         u64 Reserved;
1901         u32 AttributeFlags;
1902         u32 StreamIdentifierLength;
1903         wchar_t StreamIdentifier[1];
1904 } STREAM_LAYOUT_ENTRY;
1905
1906
1907 typedef struct {
1908 #define STREAM_EXTENT_ENTRY_AS_RETRIEVAL_POINTERS       0x00000001
1909 #define STREAM_EXTENT_ENTRY_ALL_EXTENTS                 0x00000002
1910         u32 Flags;
1911         union {
1912                 RETRIEVAL_POINTERS_BUFFER RetrievalPointers;
1913         } ExtentInformation;
1914 } STREAM_EXTENT_ENTRY;
1915
1916 /* Extract the MFT number part of the full inode number  */
1917 #define NTFS_MFT_NO(ref)        ((ref) & (((u64)1 << 48) - 1))
1918
1919 /* Is the file the root directory of the NTFS volume?  The root directory always
1920  * occupies MFT record 5.  */
1921 #define NTFS_IS_ROOT_FILE(ino)  (NTFS_MFT_NO(ino) == 5)
1922
1923 /* Is the file a special NTFS file, other than the root directory?  The special
1924  * files are the first 16 records in the MFT.  */
1925 #define NTFS_IS_SPECIAL_FILE(ino)                       \
1926         (NTFS_MFT_NO(ino) <= 15 && !NTFS_IS_ROOT_FILE(ino))
1927
1928 /* Intermediate inode structure.  This is used to temporarily save information
1929  * from FSCTL_QUERY_FILE_LAYOUT before creating the full 'struct wim_inode'.  */
1930 struct ntfs_inode {
1931         struct avl_tree_node index_node;
1932         u64 ino;
1933         u64 creation_time;
1934         u64 last_access_time;
1935         u64 last_write_time;
1936         u64 starting_lcn;
1937         u32 attributes;
1938         u32 security_id;
1939         u32 num_aliases;
1940         u32 num_streams;
1941         u32 first_stream_offset;
1942         struct ntfs_dentry *first_child;
1943         wchar_t short_name[13];
1944 };
1945
1946 /* Intermediate dentry structure.  This is used to temporarily save information
1947  * from FSCTL_QUERY_FILE_LAYOUT before creating the full 'struct wim_dentry'. */
1948 struct ntfs_dentry {
1949         u32 offset_from_inode : 31;
1950         u32 is_primary : 1;
1951         union {
1952                 /* Note: build_children_lists() replaces 'parent_ino' with
1953                  * 'next_child'.  */
1954                 u64 parent_ino;
1955                 struct ntfs_dentry *next_child;
1956         };
1957         wchar_t name[0];
1958 };
1959
1960 /* Intermediate stream structure.  This is used to temporarily save information
1961  * from FSCTL_QUERY_FILE_LAYOUT before creating the full 'struct
1962  * wim_inode_stream'.  */
1963 struct ntfs_stream {
1964         u64 size;
1965         wchar_t name[0];
1966 };
1967
1968 /* Map of all known NTFS inodes, keyed by inode number  */
1969 struct ntfs_inode_map {
1970         struct avl_tree_node *root;
1971 };
1972
1973 #define NTFS_INODE(node)                                \
1974         avl_tree_entry((node), struct ntfs_inode, index_node)
1975
1976 #define SKIP_ALIGNED(p, size)   ((void *)(p) + ALIGN((size), 8))
1977
1978 /* Get a pointer to the first dentry of the inode.  */
1979 #define FIRST_DENTRY(ni) SKIP_ALIGNED((ni), sizeof(struct ntfs_inode))
1980
1981 /* Get a pointer to the first stream of the inode.  */
1982 #define FIRST_STREAM(ni) ((const void *)ni + ni->first_stream_offset)
1983
1984 /* Advance to the next dentry of the inode.  */
1985 #define NEXT_DENTRY(nd)  SKIP_ALIGNED((nd), sizeof(struct ntfs_dentry) +   \
1986                                 (wcslen((nd)->name) + 1) * sizeof(wchar_t))
1987
1988 /* Advance to the next stream of the inode.  */
1989 #define NEXT_STREAM(ns)  SKIP_ALIGNED((ns), sizeof(struct ntfs_stream) +   \
1990                                 (wcslen((ns)->name) + 1) * sizeof(wchar_t))
1991
1992 static int
1993 _avl_cmp_ntfs_inodes(const struct avl_tree_node *node1,
1994                      const struct avl_tree_node *node2)
1995 {
1996         return cmp_u64(NTFS_INODE(node1)->ino, NTFS_INODE(node2)->ino);
1997 }
1998
1999 /* Adds an NTFS inode to the map.  */
2000 static void
2001 ntfs_inode_map_add_inode(struct ntfs_inode_map *map, struct ntfs_inode *ni)
2002 {
2003         if (avl_tree_insert(&map->root, &ni->index_node, _avl_cmp_ntfs_inodes)) {
2004                 WARNING("Inode 0x%016"PRIx64" is a duplicate!", ni->ino);
2005                 FREE(ni);
2006         }
2007 }
2008
2009 /* Find an ntfs_inode in the map by inode number.  Returns NULL if not found. */
2010 static struct ntfs_inode *
2011 ntfs_inode_map_lookup(struct ntfs_inode_map *map, u64 ino)
2012 {
2013         struct ntfs_inode tmp;
2014         struct avl_tree_node *res;
2015
2016         tmp.ino = ino;
2017         res = avl_tree_lookup_node(map->root, &tmp.index_node, _avl_cmp_ntfs_inodes);
2018         if (!res)
2019                 return NULL;
2020         return NTFS_INODE(res);
2021 }
2022
2023 /* Remove an ntfs_inode from the map and free it.  */
2024 static void
2025 ntfs_inode_map_remove(struct ntfs_inode_map *map, struct ntfs_inode *ni)
2026 {
2027         avl_tree_remove(&map->root, &ni->index_node);
2028         FREE(ni);
2029 }
2030
2031 /* Free all ntfs_inodes in the map.  */
2032 static void
2033 ntfs_inode_map_destroy(struct ntfs_inode_map *map)
2034 {
2035         struct ntfs_inode *ni;
2036
2037         avl_tree_for_each_in_postorder(ni, map->root, struct ntfs_inode, index_node)
2038                 FREE(ni);
2039 }
2040
2041 static bool
2042 file_has_streams(const FILE_LAYOUT_ENTRY *file)
2043 {
2044         return (file->FirstStreamOffset != 0) &&
2045                 !(file->FileAttributes & FILE_ATTRIBUTE_ENCRYPTED);
2046 }
2047
2048 static bool
2049 is_valid_name_entry(const FILE_LAYOUT_NAME_ENTRY *name)
2050 {
2051         return name->FileNameLength > 0 &&
2052                 name->FileNameLength % 2 == 0 &&
2053                 !wmemchr(name->FileName, L'\0', name->FileNameLength / 2) &&
2054                 (!(name->Flags & FILE_LAYOUT_NAME_ENTRY_DOS) ||
2055                  name->FileNameLength <= 24);
2056 }
2057
2058 /* Validate the FILE_LAYOUT_NAME_ENTRYs of the specified file and compute the
2059  * total length in bytes of the ntfs_dentry structures needed to hold the name
2060  * information.  */
2061 static int
2062 validate_names_and_compute_total_length(const FILE_LAYOUT_ENTRY *file,
2063                                         size_t *total_length_ret)
2064 {
2065         const FILE_LAYOUT_NAME_ENTRY *name =
2066                 (const void *)file + file->FirstNameOffset;
2067         size_t total = 0;
2068         size_t num_long_names = 0;
2069
2070         for (;;) {
2071                 if (unlikely(!is_valid_name_entry(name))) {
2072                         ERROR("Invalid FILE_LAYOUT_NAME_ENTRY! "
2073                               "FileReferenceNumber=0x%016"PRIx64", "
2074                               "FileNameLength=%"PRIu32", "
2075                               "FileName=%.*ls, Flags=0x%08"PRIx32,
2076                               file->FileReferenceNumber,
2077                               name->FileNameLength,
2078                               (int)(name->FileNameLength / 2),
2079                               name->FileName, name->Flags);
2080                         return WIMLIB_ERR_UNSUPPORTED;
2081                 }
2082                 if (name->Flags != FILE_LAYOUT_NAME_ENTRY_DOS) {
2083                         num_long_names++;
2084                         total += ALIGN(sizeof(struct ntfs_dentry) +
2085                                        name->FileNameLength + sizeof(wchar_t),
2086                                        8);
2087                 }
2088                 if (name->NextNameOffset == 0)
2089                         break;
2090                 name = (const void *)name + name->NextNameOffset;
2091         }
2092
2093         if (unlikely(num_long_names == 0)) {
2094                 ERROR("Inode 0x%016"PRIx64" has no long names!",
2095                       file->FileReferenceNumber);
2096                 return WIMLIB_ERR_UNSUPPORTED;
2097         }
2098
2099         *total_length_ret = total;
2100         return 0;
2101 }
2102
2103 static bool
2104 is_valid_stream_entry(const STREAM_LAYOUT_ENTRY *stream)
2105 {
2106         return stream->StreamIdentifierLength % 2 == 0 &&
2107                 !wmemchr(stream->StreamIdentifier , L'\0',
2108                          stream->StreamIdentifierLength / 2);
2109 }
2110
2111 /*
2112  * If the specified STREAM_LAYOUT_ENTRY represents a DATA stream as opposed to
2113  * some other type of NTFS stream such as a STANDARD_INFORMATION stream, return
2114  * true and set *stream_name_ret and *stream_name_nchars_ret to specify just the
2115  * stream name.  For example, ":foo:$DATA" would become "foo" with length 3
2116  * characters.  Otherwise return false.
2117  */
2118 static bool
2119 use_stream(const FILE_LAYOUT_ENTRY *file, const STREAM_LAYOUT_ENTRY *stream,
2120            const wchar_t **stream_name_ret, size_t *stream_name_nchars_ret)
2121 {
2122         const wchar_t *stream_name;
2123         size_t stream_name_nchars;
2124
2125         if (stream->StreamIdentifierLength == 0) {
2126                 /* The unnamed data stream may be given as an empty string
2127                  * rather than as "::$DATA".  Handle it both ways.  */
2128                 stream_name = L"";
2129                 stream_name_nchars = 0;
2130         } else if (!get_data_stream_name(stream->StreamIdentifier,
2131                                          stream->StreamIdentifierLength / 2,
2132                                          &stream_name, &stream_name_nchars))
2133                 return false;
2134
2135         /* Skip the unnamed data stream for directories.  */
2136         if (stream_name_nchars == 0 &&
2137             (file->FileAttributes & FILE_ATTRIBUTE_DIRECTORY))
2138                 return false;
2139
2140         *stream_name_ret = stream_name;
2141         *stream_name_nchars_ret = stream_name_nchars;
2142         return true;
2143 }
2144
2145 /* Validate the STREAM_LAYOUT_ENTRYs of the specified file and compute the total
2146  * length in bytes of the ntfs_stream structures needed to hold the stream
2147  * information.  */
2148 static int
2149 validate_streams_and_compute_total_length(const FILE_LAYOUT_ENTRY *file,
2150                                           size_t *total_length_ret)
2151 {
2152         const STREAM_LAYOUT_ENTRY *stream =
2153                 (const void *)file + file->FirstStreamOffset;
2154         size_t total = 0;
2155         for (;;) {
2156                 const wchar_t *name;
2157                 size_t name_nchars;
2158
2159                 if (unlikely(!is_valid_stream_entry(stream))) {
2160                         WARNING("Invalid STREAM_LAYOUT_ENTRY! "
2161                                 "FileReferenceNumber=0x%016"PRIx64", "
2162                                 "StreamIdentifierLength=%"PRIu32", "
2163                                 "StreamIdentifier=%.*ls",
2164                                 file->FileReferenceNumber,
2165                                 stream->StreamIdentifierLength,
2166                                 (int)(stream->StreamIdentifierLength / 2),
2167                                 stream->StreamIdentifier);
2168                         return WIMLIB_ERR_UNSUPPORTED;
2169                 }
2170
2171                 if (use_stream(file, stream, &name, &name_nchars)) {
2172                         total += ALIGN(sizeof(struct ntfs_stream) +
2173                                        (name_nchars + 1) * sizeof(wchar_t), 8);
2174                 }
2175                 if (stream->NextStreamOffset == 0)
2176                         break;
2177                 stream = (const void *)stream + stream->NextStreamOffset;
2178         }
2179
2180         *total_length_ret = total;
2181         return 0;
2182 }
2183
2184 static void *
2185 load_name_information(const FILE_LAYOUT_ENTRY *file, struct ntfs_inode *ni,
2186                       void *p)
2187 {
2188         const FILE_LAYOUT_NAME_ENTRY *name =
2189                 (const void *)file + file->FirstNameOffset;
2190         for (;;) {
2191                 struct ntfs_dentry *nd = p;
2192                 /* Note that a name may be just a short (DOS) name, just a long
2193                  * name, or both a short name and a long name.  If there is a
2194                  * short name, one name should also be marked as "primary" to
2195                  * indicate which long name the short name is associated with.
2196                  * Also, there should be at most one short name per inode.  */
2197                 if (name->Flags & FILE_LAYOUT_NAME_ENTRY_DOS) {
2198                         memcpy(ni->short_name,
2199                                name->FileName, name->FileNameLength);
2200                         ni->short_name[name->FileNameLength / 2] = L'\0';
2201                 }
2202                 if (name->Flags != FILE_LAYOUT_NAME_ENTRY_DOS) {
2203                         ni->num_aliases++;
2204                         nd->offset_from_inode = (u8 *)nd - (u8 *)ni;
2205                         nd->is_primary = ((name->Flags &
2206                                            FILE_LAYOUT_NAME_ENTRY_PRIMARY) != 0);
2207                         nd->parent_ino = name->ParentFileReferenceNumber;
2208                         memcpy(nd->name, name->FileName, name->FileNameLength);
2209                         nd->name[name->FileNameLength / 2] = L'\0';
2210                         p += ALIGN(sizeof(struct ntfs_dentry) +
2211                                    name->FileNameLength + sizeof(wchar_t), 8);
2212                 }
2213                 if (name->NextNameOffset == 0)
2214                         break;
2215                 name = (const void *)name + name->NextNameOffset;
2216         }
2217         return p;
2218 }
2219
2220 static u64
2221 load_starting_lcn(const STREAM_LAYOUT_ENTRY *stream)
2222 {
2223         const STREAM_EXTENT_ENTRY *entry;
2224
2225         if (stream->ExtentInformationOffset == 0)
2226                 return 0;
2227
2228         entry = (const void *)stream + stream->ExtentInformationOffset;
2229
2230         if (!(entry->Flags & STREAM_EXTENT_ENTRY_AS_RETRIEVAL_POINTERS))
2231                 return 0;
2232
2233         return extract_starting_lcn(&entry->ExtentInformation.RetrievalPointers);
2234 }
2235
2236 static void *
2237 load_stream_information(const FILE_LAYOUT_ENTRY *file, struct ntfs_inode *ni,
2238                         void *p)
2239 {
2240         const STREAM_LAYOUT_ENTRY *stream =
2241                 (const void *)file + file->FirstStreamOffset;
2242         const u32 first_stream_offset = (const u8 *)p - (const u8 *)ni;
2243         for (;;) {
2244                 struct ntfs_stream *ns = p;
2245                 const wchar_t *name;
2246                 size_t name_nchars;
2247
2248                 if (use_stream(file, stream, &name, &name_nchars)) {
2249                         ni->first_stream_offset = first_stream_offset;
2250                         ni->num_streams++;
2251                         if (name_nchars == 0)
2252                                 ni->starting_lcn = load_starting_lcn(stream);
2253                         ns->size = stream->EndOfFile;
2254                         wmemcpy(ns->name, name, name_nchars);
2255                         ns->name[name_nchars] = L'\0';
2256                         p += ALIGN(sizeof(struct ntfs_stream) +
2257                                    (name_nchars + 1) * sizeof(wchar_t), 8);
2258                 }
2259                 if (stream->NextStreamOffset == 0)
2260                         break;
2261                 stream = (const void *)stream + stream->NextStreamOffset;
2262         }
2263         return p;
2264 }
2265
2266 /* Process the information for a file given by FSCTL_QUERY_FILE_LAYOUT.  */
2267 static int
2268 load_one_file(const FILE_LAYOUT_ENTRY *file, struct ntfs_inode_map *inode_map)
2269 {
2270         const FILE_LAYOUT_INFO_ENTRY *info =
2271                 (const void *)file + file->ExtraInfoOffset;
2272         size_t inode_size;
2273         struct ntfs_inode *ni;
2274         size_t n;
2275         int ret;
2276         void *p;
2277
2278         inode_size = ALIGN(sizeof(struct ntfs_inode), 8);
2279
2280         /* The root file should have no names, and all other files should have
2281          * at least one name.  But just in case, we ignore the names of the root
2282          * file, and we ignore any non-root file with no names.  */
2283         if (!NTFS_IS_ROOT_FILE(file->FileReferenceNumber)) {
2284                 if (file->FirstNameOffset == 0)
2285                         return 0;
2286                 ret = validate_names_and_compute_total_length(file, &n);
2287                 if (ret)
2288                         return ret;
2289                 inode_size += n;
2290         }
2291
2292         if (file_has_streams(file)) {
2293                 ret = validate_streams_and_compute_total_length(file, &n);
2294                 if (ret)
2295                         return ret;
2296                 inode_size += n;
2297         }
2298
2299         /* To save memory, we allocate the ntfs_dentry's and ntfs_stream's in
2300          * the same memory block as their ntfs_inode.  */
2301         ni = CALLOC(1, inode_size);
2302         if (!ni)
2303                 return WIMLIB_ERR_NOMEM;
2304
2305         ni->ino = file->FileReferenceNumber;
2306         ni->attributes = info->BasicInformation.FileAttributes;
2307         ni->creation_time = info->BasicInformation.CreationTime;
2308         ni->last_write_time = info->BasicInformation.LastWriteTime;
2309         ni->last_access_time = info->BasicInformation.LastAccessTime;
2310         ni->security_id = info->SecurityId;
2311
2312         p = FIRST_DENTRY(ni);
2313
2314         if (!NTFS_IS_ROOT_FILE(file->FileReferenceNumber))
2315                 p = load_name_information(file, ni, p);
2316
2317         if (file_has_streams(file))
2318                 p = load_stream_information(file, ni, p);
2319
2320         wimlib_assert((u8 *)p - (u8 *)ni == inode_size);
2321
2322         ntfs_inode_map_add_inode(inode_map, ni);
2323         return 0;
2324 }
2325
2326 /*
2327  * Quickly find all files on an NTFS volume by using FSCTL_QUERY_FILE_LAYOUT to
2328  * scan the MFT.  The NTFS volume is specified by the NT namespace path @path.
2329  * For each file, allocate an 'ntfs_inode' structure for each file and add it to
2330  * 'inode_map' keyed by inode number.  Include NTFS special files such as
2331  * $Bitmap (they will be removed later).
2332  */
2333 static int
2334 load_files_from_mft(const wchar_t *path, struct ntfs_inode_map *inode_map)
2335 {
2336         HANDLE h = NULL;
2337         QUERY_FILE_LAYOUT_INPUT in = (QUERY_FILE_LAYOUT_INPUT) {
2338                 .NumberOfPairs = 0,
2339                 .Flags = QUERY_FILE_LAYOUT_RESTART |
2340                          QUERY_FILE_LAYOUT_INCLUDE_NAMES |
2341                          QUERY_FILE_LAYOUT_INCLUDE_STREAMS |
2342                          QUERY_FILE_LAYOUT_INCLUDE_EXTENTS |
2343                          QUERY_FILE_LAYOUT_INCLUDE_EXTRA_INFO |
2344                          QUERY_FILE_LAYOUT_INCLUDE_STREAMS_WITH_NO_CLUSTERS_ALLOCATED,
2345                 .FilterType = QUERY_FILE_LAYOUT_FILTER_TYPE_NONE,
2346         };
2347         const size_t outsize = 32768;
2348         QUERY_FILE_LAYOUT_OUTPUT *out = NULL;
2349         int ret;
2350         NTSTATUS status;
2351
2352         status = winnt_open(path, wcslen(path),
2353                             FILE_READ_DATA | FILE_READ_ATTRIBUTES, &h);
2354         if (!NT_SUCCESS(status)) {
2355                 ret = -1; /* Silently try standard recursive scan instead  */
2356                 goto out;
2357         }
2358
2359         out = MALLOC(outsize);
2360         if (!out) {
2361                 ret = WIMLIB_ERR_NOMEM;
2362                 goto out;
2363         }
2364
2365         while (NT_SUCCESS(status = winnt_fsctl(h, FSCTL_QUERY_FILE_LAYOUT,
2366                                                &in, sizeof(in),
2367                                                out, outsize, NULL)))
2368         {
2369                 const FILE_LAYOUT_ENTRY *file =
2370                         (const void *)out + out->FirstFileOffset;
2371                 for (;;) {
2372                         ret = load_one_file(file, inode_map);
2373                         if (ret)
2374                                 goto out;
2375                         if (file->NextFileOffset == 0)
2376                                 break;
2377                         file = (const void *)file + file->NextFileOffset;
2378                 }
2379                 in.Flags &= ~QUERY_FILE_LAYOUT_RESTART;
2380         }
2381
2382         /* Normally, FSCTL_QUERY_FILE_LAYOUT fails with STATUS_END_OF_FILE after
2383          * all files have been enumerated.  */
2384         if (status != STATUS_END_OF_FILE) {
2385                 if (status == STATUS_INVALID_DEVICE_REQUEST /* old OS */ ||
2386                     status == STATUS_INVALID_PARAMETER /* not root directory */ ) {
2387                         /* Silently try standard recursive scan instead  */
2388                         ret = -1;
2389                 } else {
2390                         winnt_error(status,
2391                                     L"Error enumerating files on volume \"%ls\"",
2392                                     path);
2393                         /* Try standard recursive scan instead  */
2394                         ret = WIMLIB_ERR_UNSUPPORTED;
2395                 }
2396                 goto out;
2397         }
2398         ret = 0;
2399 out:
2400         FREE(out);
2401         NtClose(h);
2402         return ret;
2403 }
2404
2405 /* Build the list of child dentries for each inode in @map.  This is done by
2406  * iterating through each name of each inode and adding it to its parent's
2407  * children list.  Note that every name should have a parent, i.e. should belong
2408  * to some directory.  The root directory does not have any names.  */
2409 static int
2410 build_children_lists(struct ntfs_inode_map *map, struct ntfs_inode **root_ret)
2411 {
2412         struct ntfs_inode *ni;
2413
2414         avl_tree_for_each_in_order(ni, map->root, struct ntfs_inode, index_node)
2415         {
2416                 struct ntfs_dentry *nd;
2417                 u32 n;
2418
2419                 if (NTFS_IS_ROOT_FILE(ni->ino)) {
2420                         *root_ret = ni;
2421                         continue;
2422                 }
2423
2424                 n = ni->num_aliases;
2425                 nd = FIRST_DENTRY(ni);
2426                 for (;;) {
2427                         struct ntfs_inode *parent;
2428
2429                         parent = ntfs_inode_map_lookup(map, nd->parent_ino);
2430                         if (unlikely(!parent)) {
2431                                 ERROR("Parent inode 0x%016"PRIx64" of"
2432                                       "directory entry \"%ls\" (inode "
2433                                       "0x%016"PRIx64") was missing from the "
2434                                       "MFT listing!",
2435                                       nd->parent_ino, nd->name, ni->ino);
2436                                 return WIMLIB_ERR_UNSUPPORTED;
2437                         }
2438                         nd->next_child = parent->first_child;
2439                         parent->first_child = nd;
2440                         if (!--n)
2441                                 break;
2442                         nd = NEXT_DENTRY(nd);
2443                 }
2444         }
2445         return 0;
2446 }
2447
2448 struct security_map_node {
2449         struct avl_tree_node index_node;
2450         u32 disk_security_id;
2451         u32 wim_security_id;
2452 };
2453
2454 /* Map from disk security IDs to WIM security IDs  */
2455 struct security_map {
2456         struct avl_tree_node *root;
2457 };
2458
2459 #define SECURITY_MAP_NODE(node)                         \
2460         avl_tree_entry((node), struct security_map_node, index_node)
2461
2462 static int
2463 _avl_cmp_security_map_nodes(const struct avl_tree_node *node1,
2464                             const struct avl_tree_node *node2)
2465 {
2466         return cmp_u32(SECURITY_MAP_NODE(node1)->disk_security_id,
2467                        SECURITY_MAP_NODE(node2)->disk_security_id);
2468 }
2469
2470 static s32
2471 security_map_lookup(struct security_map *map, u32 disk_security_id)
2472 {
2473         struct security_map_node tmp;
2474         const struct avl_tree_node *res;
2475
2476         if (disk_security_id == 0)  /* No on-disk security ID; uncacheable  */
2477                 return -1;
2478
2479         tmp.disk_security_id = disk_security_id;
2480         res = avl_tree_lookup_node(map->root, &tmp.index_node,
2481                                    _avl_cmp_security_map_nodes);
2482         if (!res)
2483                 return -1;
2484         return SECURITY_MAP_NODE(res)->wim_security_id;
2485 }
2486
2487 static int
2488 security_map_insert(struct security_map *map, u32 disk_security_id,
2489                     u32 wim_security_id)
2490 {
2491         struct security_map_node *node;
2492
2493         if (disk_security_id == 0)  /* No on-disk security ID; uncacheable  */
2494                 return 0;
2495
2496         node = MALLOC(sizeof(*node));
2497         if (!node)
2498                 return WIMLIB_ERR_NOMEM;
2499
2500         node->disk_security_id = disk_security_id;
2501         node->wim_security_id = wim_security_id;
2502         avl_tree_insert(&map->root, &node->index_node,
2503                         _avl_cmp_security_map_nodes);
2504         return 0;
2505 }
2506
2507 static void
2508 security_map_destroy(struct security_map *map)
2509 {
2510         struct security_map_node *node;
2511
2512         avl_tree_for_each_in_postorder(node, map->root,
2513                                        struct security_map_node, index_node)
2514                 FREE(node);
2515 }
2516
2517 /*
2518  * Turn our temporary NTFS structures into the final WIM structures:
2519  *
2520  *      ntfs_inode      => wim_inode
2521  *      ntfs_dentry     => wim_dentry
2522  *      ntfs_stream     => wim_inode_stream
2523  *
2524  * This also handles things such as exclusions and issuing progress messages.
2525  * It's similar to winnt_build_dentry_tree_recursive(), but this is much faster
2526  * because almost all information we need is already loaded in memory in the
2527  * ntfs_* structures.  However, in some cases we still fall back to
2528  * winnt_build_dentry_tree_recursive() and/or opening the file.
2529  */
2530 static int
2531 generate_wim_structures_recursive(struct wim_dentry **root_ret,
2532                                   wchar_t *path, size_t path_nchars,
2533                                   const wchar_t *filename, bool is_primary_name,
2534                                   struct ntfs_inode *ni,
2535                                   struct winnt_scan_ctx *ctx,
2536                                   struct ntfs_inode_map *inode_map,
2537                                   struct security_map *security_map)
2538 {
2539         int ret = 0;
2540         struct wim_dentry *root = NULL;
2541         struct wim_inode *inode = NULL;
2542         const struct ntfs_stream *ns;
2543
2544         /* Completely ignore NTFS special files.  */
2545         if (NTFS_IS_SPECIAL_FILE(ni->ino))
2546                 goto out;
2547
2548         /* Fall back to a recursive scan for unhandled cases.  Reparse points,
2549          * in particular, can't be properly handled here because a commonly used
2550          * filter driver (WOF) hides reparse points from regular filesystem APIs
2551          * but not from FSCTL_QUERY_FILE_LAYOUT.  */
2552         if (ni->attributes & (FILE_ATTRIBUTE_REPARSE_POINT |
2553                               FILE_ATTRIBUTE_ENCRYPTED))
2554         {
2555                 ret = winnt_build_dentry_tree_recursive(&root,
2556                                                         NULL,
2557                                                         path,
2558                                                         path_nchars,
2559                                                         path,
2560                                                         path_nchars,
2561                                                         filename,
2562                                                         ctx);
2563                 goto out;
2564         }
2565
2566         /* Test for exclusion based on path.  */
2567         ret = try_exclude(path, ctx->params);
2568         if (unlikely(ret < 0)) /* Excluded? */
2569                 goto out_progress;
2570         if (unlikely(ret > 0)) /* Error? */
2571                 goto out;
2572
2573         /* Create the WIM dentry and possibly a new WIM inode  */
2574         ret = inode_table_new_dentry(ctx->params->inode_table, filename,
2575                                      ni->ino, ctx->params->capture_root_dev,
2576                                      false, &root);
2577         if (ret)
2578                 goto out;
2579
2580         inode = root->d_inode;
2581
2582         /* Set the short name if needed.  */
2583         if (is_primary_name && *ni->short_name) {
2584                 size_t nbytes = wcslen(ni->short_name) * sizeof(wchar_t);
2585                 root->d_short_name = memdup(ni->short_name,
2586                                             nbytes + sizeof(wchar_t));
2587                 if (!root->d_short_name) {
2588                         ret = WIMLIB_ERR_NOMEM;
2589                         goto out;
2590                 }
2591                 root->d_short_name_nbytes = nbytes;
2592         }
2593
2594         if (inode->i_nlink > 1) { /* Already seen this inode?  */
2595                 ret = 0;
2596                 goto out_progress;
2597         }
2598
2599         /* The file attributes and timestamps were cached from the MFT.  */
2600         inode->i_attributes = ni->attributes;
2601         inode->i_creation_time = ni->creation_time;
2602         inode->i_last_write_time = ni->last_write_time;
2603         inode->i_last_access_time = ni->last_access_time;
2604
2605         /* Set the security descriptor if needed.  */
2606         if (!(ctx->params->add_flags & WIMLIB_ADD_FLAG_NO_ACLS)) {
2607                 /* Look up the WIM security ID that corresponds to the on-disk
2608                  * security ID.  */
2609                 s32 wim_security_id =
2610                         security_map_lookup(security_map, ni->security_id);
2611                 if (likely(wim_security_id >= 0)) {
2612                         /* The mapping for this security ID is already cached.*/
2613                         inode->i_security_id = wim_security_id;
2614                 } else {
2615                         HANDLE h;
2616                         NTSTATUS status;
2617
2618                         /* Create a mapping for this security ID and insert it
2619                          * into the security map.  */
2620
2621                         status = winnt_open(path, path_nchars,
2622                                             READ_CONTROL |
2623                                                 ACCESS_SYSTEM_SECURITY, &h);
2624                         if (!NT_SUCCESS(status)) {
2625                                 winnt_error(status, L"Can't open \"%ls\" to "
2626                                             "read security descriptor",
2627                                             printable_path(path));
2628                                 ret = WIMLIB_ERR_OPEN;
2629                                 goto out;
2630                         }
2631                         ret = winnt_load_security_descriptor(h, inode, path, ctx);
2632                         NtClose(h);
2633                         if (ret)
2634                                 goto out;
2635
2636                         ret = security_map_insert(security_map, ni->security_id,
2637                                                   inode->i_security_id);
2638                         if (ret)
2639                                 goto out;
2640                 }
2641         }
2642
2643         /* Add data streams based on the cached information from the MFT.  */
2644         ns = FIRST_STREAM(ni);
2645         for (u32 i = 0; i < ni->num_streams; i++) {
2646                 struct windows_file *windows_file;
2647
2648                 /* Reference the stream by path if it's a named data stream, or
2649                  * if the volume doesn't support "open by file ID", or if the
2650                  * application hasn't explicitly opted in to "open by file ID".
2651                  * Otherwise, only save the inode number (file ID).  */
2652                 if (*ns->name ||
2653                     !(ctx->vol_flags & FILE_SUPPORTS_OPEN_BY_FILE_ID) ||
2654                     !(ctx->params->add_flags & WIMLIB_ADD_FLAG_FILE_PATHS_UNNEEDED))
2655                 {
2656                         windows_file = alloc_windows_file(path,
2657                                                           path_nchars,
2658                                                           ns->name,
2659                                                           wcslen(ns->name),
2660                                                           ctx->snapshot,
2661                                                           false);
2662                 } else {
2663                         windows_file = alloc_windows_file_for_file_id(ni->ino,
2664                                                                       path,
2665                                                                       ctx->params->capture_root_nchars + 1,
2666                                                                       ctx->snapshot);
2667                 }
2668
2669                 ret = add_stream(inode, windows_file, ns->size,
2670                                  STREAM_TYPE_DATA, ns->name,
2671                                  ctx->params->unhashed_blobs);
2672                 if (ret)
2673                         goto out;
2674                 ns = NEXT_STREAM(ns);
2675         }
2676
2677         set_sort_key(inode, ni->starting_lcn);
2678
2679         /* If processing a directory, then recurse to its children.  In this
2680          * version there is no need to go to disk, as we already have the list
2681          * of children cached from the MFT.  */
2682         if (inode_is_directory(inode)) {
2683                 const struct ntfs_dentry *nd = ni->first_child;
2684
2685                 while (nd != NULL) {
2686                         const size_t name_len = wcslen(nd->name);
2687                         wchar_t *p = path + path_nchars;
2688                         struct wim_dentry *child;
2689                         const struct ntfs_dentry *next = nd->next_child;
2690
2691                         if (*(p - 1) != L'\\')
2692                                 *p++ = L'\\';
2693                         p = wmempcpy(p, nd->name, name_len);
2694                         *p = '\0';
2695
2696                         ret = generate_wim_structures_recursive(
2697                                         &child,
2698                                         path,
2699                                         p - path,
2700                                         nd->name,
2701                                         nd->is_primary,
2702                                         (void *)nd - nd->offset_from_inode,
2703                                         ctx,
2704                                         inode_map,
2705                                         security_map);
2706
2707                         path[path_nchars] = L'\0';
2708
2709                         if (ret)
2710                                 goto out;
2711
2712                         attach_scanned_tree(root, child, ctx->params->blob_table);
2713                         nd = next;
2714                 }
2715         }
2716
2717 out_progress:
2718         ctx->params->progress.scan.cur_path = path;
2719         if (likely(root))
2720                 ret = do_capture_progress(ctx->params, WIMLIB_SCAN_DENTRY_OK, inode);
2721         else
2722                 ret = do_capture_progress(ctx->params, WIMLIB_SCAN_DENTRY_EXCLUDED, NULL);
2723 out:
2724         if (--ni->num_aliases == 0) {
2725                 /* Memory usage optimization: when we don't need the ntfs_inode
2726                  * (and its names and streams) anymore, free it.  */
2727                 ntfs_inode_map_remove(inode_map, ni);
2728         }
2729         if (unlikely(ret)) {
2730                 free_dentry_tree(root, ctx->params->blob_table);
2731                 root = NULL;
2732         }
2733         *root_ret = root;
2734         return ret;
2735 }
2736
2737 static int
2738 winnt_build_dentry_tree_fast(struct wim_dentry **root_ret, wchar_t *path,
2739                              size_t path_nchars, struct winnt_scan_ctx *ctx)
2740 {
2741         struct ntfs_inode_map inode_map = { .root = NULL };
2742         struct security_map security_map = { .root = NULL };
2743         struct ntfs_inode *root = NULL;
2744         bool adjust_path;
2745         int ret;
2746
2747         adjust_path = (path[path_nchars - 1] == L'\\');
2748         if (adjust_path)
2749                 path[path_nchars - 1] = L'\0';
2750
2751         ret = load_files_from_mft(path, &inode_map);
2752
2753         if (adjust_path)
2754                 path[path_nchars - 1] = L'\\';
2755
2756         if (ret)
2757                 goto out;
2758
2759         ret = build_children_lists(&inode_map, &root);
2760         if (ret)
2761                 goto out;
2762
2763         if (!root) {
2764                 ERROR("The MFT listing for volume \"%ls\" did not include a "
2765                       "root directory!", path);
2766                 ret = WIMLIB_ERR_UNSUPPORTED;
2767                 goto out;
2768         }
2769
2770         root->num_aliases = 1;
2771
2772         ret = generate_wim_structures_recursive(root_ret, path, path_nchars,
2773                                                 L"", false, root, ctx,
2774                                                 &inode_map, &security_map);
2775 out:
2776         ntfs_inode_map_destroy(&inode_map);
2777         security_map_destroy(&security_map);
2778         return ret;
2779 }
2780
2781 #endif /* ENABLE_FAST_MFT_SCAN */
2782
2783 /*----------------------------------------------------------------------------*
2784  *                 Entry point for directory tree scans on Windows            *
2785  *----------------------------------------------------------------------------*/
2786
2787 #define WINDOWS_NT_MAX_PATH 32768
2788
2789 int
2790 win32_build_dentry_tree(struct wim_dentry **root_ret,
2791                         const wchar_t *root_disk_path,
2792                         struct capture_params *params)
2793 {
2794         wchar_t *path = NULL;
2795         struct winnt_scan_ctx ctx = { .params = params };
2796         UNICODE_STRING ntpath;
2797         size_t ntpath_nchars;
2798         HANDLE h = NULL;
2799         NTSTATUS status;
2800         int ret;
2801
2802         /* WARNING: There is no check for overflow later when this buffer is
2803          * being used!  But it's as long as the maximum path length understood
2804          * by Windows NT (which is NOT the same as MAX_PATH).  */
2805         path = MALLOC((WINDOWS_NT_MAX_PATH + 1) * sizeof(wchar_t));
2806         if (!path)
2807                 return WIMLIB_ERR_NOMEM;
2808
2809         if (params->add_flags & WIMLIB_ADD_FLAG_SNAPSHOT)
2810                 ret = vss_create_snapshot(root_disk_path, &ntpath, &ctx.snapshot);
2811         else
2812                 ret = win32_path_to_nt_path(root_disk_path, &ntpath);
2813
2814         if (ret)
2815                 goto out;
2816
2817         if (ntpath.Length < 4 * sizeof(wchar_t) ||
2818             ntpath.Length > WINDOWS_NT_MAX_PATH * sizeof(wchar_t) ||
2819             wmemcmp(ntpath.Buffer, L"\\??\\", 4))
2820         {
2821                 ERROR("\"%ls\": unrecognized path format", root_disk_path);
2822                 ret = WIMLIB_ERR_INVALID_PARAM;
2823         } else {
2824                 ntpath_nchars = ntpath.Length / sizeof(wchar_t);
2825                 wmemcpy(path, ntpath.Buffer, ntpath_nchars);
2826                 path[ntpath_nchars] = L'\0';
2827
2828                 params->capture_root_nchars = ntpath_nchars;
2829                 if (path[ntpath_nchars - 1] == L'\\')
2830                         params->capture_root_nchars--;
2831                 ret = 0;
2832         }
2833         HeapFree(GetProcessHeap(), 0, ntpath.Buffer);
2834         if (ret)
2835                 goto out;
2836
2837         status = winnt_open(path, ntpath_nchars, FILE_READ_ATTRIBUTES, &h);
2838         if (!NT_SUCCESS(status)) {
2839                 winnt_error(status, L"Can't open \"%ls\"", printable_path(path));
2840                 if (status == STATUS_FVE_LOCKED_VOLUME)
2841                         ret = WIMLIB_ERR_FVE_LOCKED_VOLUME;
2842                 else
2843                         ret = WIMLIB_ERR_OPEN;
2844                 goto out;
2845         }
2846
2847         get_volume_information(h, path, &ctx);
2848
2849         NtClose(h);
2850
2851 #ifdef ENABLE_FAST_MFT_SCAN
2852         if (ctx.is_ntfs && !_wgetenv(L"WIMLIB_DISABLE_QUERY_FILE_LAYOUT")) {
2853                 ret = winnt_build_dentry_tree_fast(root_ret, path,
2854                                                    ntpath_nchars, &ctx);
2855                 if (ret >= 0 && ret != WIMLIB_ERR_UNSUPPORTED)
2856                         goto out;
2857                 if (ret >= 0) {
2858                         WARNING("A problem occurred during the fast MFT scan.\n"
2859                                 "          Falling back to the standard "
2860                                 "recursive directory tree scan.");
2861                 }
2862         }
2863 #endif
2864         ret = winnt_build_dentry_tree_recursive(root_ret, NULL,
2865                                                 path, ntpath_nchars,
2866                                                 path, ntpath_nchars,
2867                                                 L"", &ctx);
2868 out:
2869         vss_put_snapshot(ctx.snapshot);
2870         FREE(path);
2871         if (ret == 0)
2872                 winnt_do_scan_warnings(root_disk_path, &ctx);
2873         return ret;
2874 }
2875
2876 #endif /* __WIN32__ */