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