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