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