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