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