xref: /dports/sysutils/wimlib/wimlib-1.13.0/src/win32_capture.c

/*
 * win32_capture.c - Windows-specific code for capturing files into a WIM image.
 *
 * This now uses the native Windows NT API a lot and not just Win32.
 */

/*
 * Copyright (C) 2013-2018 Eric Biggers
 *
 * This file is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the Free
 * Software Foundation; either version 3 of the License, or (at your option) any
 * later version.
 *
 * This file is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this file; if not, see http://www.gnu.org/licenses/.
 */

#ifdef __WIN32__

#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif

#include "wimlib/win32_common.h"

#include "wimlib/assert.h"
#include "wimlib/blob_table.h"
#include "wimlib/dentry.h"
#include "wimlib/encoding.h"
#include "wimlib/endianness.h"
#include "wimlib/error.h"
#include "wimlib/object_id.h"
#include "wimlib/paths.h"
#include "wimlib/reparse.h"
#include "wimlib/scan.h"
#include "wimlib/win32_vss.h"
#include "wimlib/wof.h"
#include "wimlib/xattr.h"

struct winnt_scan_ctx {
	struct scan_params *params;
	bool is_ntfs;
	u32 vol_flags;
	unsigned long num_get_sd_access_denied;
	unsigned long num_get_sacl_priv_notheld;

	/* True if WOF is definitely not attached to the volume being scanned;
	 * false if it may be  */
	bool wof_not_attached;

	/* A reference to the VSS snapshot being used, or NULL if none  */
	struct vss_snapshot *snapshot;
};

static inline const wchar_t *
printable_path(const struct winnt_scan_ctx *ctx)
{
	/* Skip over \\?\ or \??\  */
	return ctx->params->cur_path + 4;
}

/* Description of where data is located on a Windows filesystem  */
struct windows_file {

	/* Is the data the raw encrypted data of an EFS-encrypted file?  */
	u64 is_encrypted : 1;

	/* Is this file "open by file ID" rather than the regular "open by
	 * path"?  "Open by file ID" uses resources more efficiently.  */
	u64 is_file_id : 1;

	/* The file's LCN (logical cluster number) for sorting, or 0 if unknown.
	 */
	u64 sort_key : 62;

	/* Length of the path in bytes, excluding the null terminator if
	 * present.  */
	size_t path_nbytes;

	/* A reference to the VSS snapshot containing the file, or NULL if none.
	 */
	struct vss_snapshot *snapshot;

	/* The path to the file.  If 'is_encrypted=0' this is an NT namespace
	 * path; if 'is_encrypted=1' this is a Win32 namespace path.  If
	 * 'is_file_id=0', then the path is null-terminated.  If 'is_file_id=1'
	 * (only allowed with 'is_encrypted=0') the path ends with a binary file
	 * ID and may not be null-terminated.  */
	wchar_t path[0];
};

/* Allocate a structure to describe the location of a data stream by path.  */
static struct windows_file *
alloc_windows_file(const wchar_t *path, size_t path_nchars,
		   const wchar_t *stream_name, size_t stream_name_nchars,
		   struct vss_snapshot *snapshot, bool is_encrypted)
{
	size_t full_path_nbytes;
	struct windows_file *file;
	wchar_t *p;

	full_path_nbytes = path_nchars * sizeof(wchar_t);
	if (stream_name_nchars)
		full_path_nbytes += (1 + stream_name_nchars) * sizeof(wchar_t);

	file = MALLOC(sizeof(struct windows_file) + full_path_nbytes +
		      sizeof(wchar_t));
	if (!file)
		return NULL;

	file->is_encrypted = is_encrypted;
	file->is_file_id = 0;
	file->sort_key = 0;
	file->path_nbytes = full_path_nbytes;
	file->snapshot = vss_get_snapshot(snapshot);
	p = wmempcpy(file->path, path, path_nchars);
	if (stream_name_nchars) {
		/* Named data stream  */
		*p++ = L':';
		p = wmempcpy(p, stream_name, stream_name_nchars);
	}
	*p = L'\0';
	return file;
}

/* Allocate a structure to describe the location of a file by ID.  */
static struct windows_file *
alloc_windows_file_for_file_id(u64 file_id, const wchar_t *root_path,
			       size_t root_path_nchars,
			       struct vss_snapshot *snapshot)
{
	size_t full_path_nbytes;
	struct windows_file *file;
	wchar_t *p;

	full_path_nbytes = (root_path_nchars * sizeof(wchar_t)) +
			   sizeof(file_id);
	file = MALLOC(sizeof(struct windows_file) + full_path_nbytes +
		      sizeof(wchar_t));
	if (!file)
		return NULL;

	file->is_encrypted = 0;
	file->is_file_id = 1;
	file->sort_key = 0;
	file->path_nbytes = full_path_nbytes;
	file->snapshot = vss_get_snapshot(snapshot);
	p = wmempcpy(file->path, root_path, root_path_nchars);
	p = mempcpy(p, &file_id, sizeof(file_id));
	*p = L'\0';
	return file;
}

/* Add a stream, located on a Windows filesystem, to the specified WIM inode. */
static int
add_stream(struct wim_inode *inode, struct windows_file *windows_file,
	   u64 stream_size, int stream_type, const utf16lechar *stream_name,
	   struct list_head *unhashed_blobs)
{
	struct blob_descriptor *blob = NULL;
	struct wim_inode_stream *strm;
	int ret;

	if (!windows_file)
		goto err_nomem;

	/* If the stream is nonempty, create a blob descriptor for it.  */
	if (stream_size) {
		blob = new_blob_descriptor();
		if (!blob)
			goto err_nomem;
		blob->windows_file = windows_file;
		blob->blob_location = BLOB_IN_WINDOWS_FILE;
		blob->file_inode = inode;
		blob->size = stream_size;
		windows_file = NULL;
	}

	strm = inode_add_stream(inode, stream_type, stream_name, blob);
	if (!strm)
		goto err_nomem;

	prepare_unhashed_blob(blob, inode, strm->stream_id, unhashed_blobs);
	ret = 0;
out:
	if (windows_file)
		free_windows_file(windows_file);
	return ret;

err_nomem:
	free_blob_descriptor(blob);
	ret = WIMLIB_ERR_NOMEM;
	goto out;
}

struct windows_file *
clone_windows_file(const struct windows_file *file)
{
	struct windows_file *new;

	new = memdup(file, sizeof(*file) + file->path_nbytes + sizeof(wchar_t));
	if (new)
		vss_get_snapshot(new->snapshot);
	return new;
}

void
free_windows_file(struct windows_file *file)
{
	vss_put_snapshot(file->snapshot);
	FREE(file);
}

int
cmp_windows_files(const struct windows_file *file1,
		  const struct windows_file *file2)
{
	/* Compare by starting LCN (logical cluster number)  */
	int v = cmp_u64(file1->sort_key, file2->sort_key);
	if (v)
		return v;

	/* Fall back to comparing files by path (arbitrary heuristic).  */
	v = memcmp(file1->path, file2->path,
		   min(file1->path_nbytes, file2->path_nbytes));
	if (v)
		return v;

	return cmp_u32(file1->path_nbytes, file2->path_nbytes);
}

const wchar_t *
get_windows_file_path(const struct windows_file *file)
{
	return file->path;
}

/*
 * Open the file named by the NT namespace path @path of length @path_nchars
 * characters.  If @cur_dir is not NULL then the path is given relative to
 * @cur_dir; otherwise the path is absolute.  @perms is the access mask of
 * permissions to request on the handle.  SYNCHRONIZE permision is always added.
 */
static NTSTATUS
winnt_openat(HANDLE cur_dir, const wchar_t *path, size_t path_nchars,
	     ACCESS_MASK perms, HANDLE *h_ret)
{
	UNICODE_STRING name = {
		.Length = path_nchars * sizeof(wchar_t),
		.MaximumLength = path_nchars * sizeof(wchar_t),
		.Buffer = (wchar_t *)path,
	};
	OBJECT_ATTRIBUTES attr = {
		.Length = sizeof(attr),
		.RootDirectory = cur_dir,
		.ObjectName = &name,
	};
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;
	ULONG options = FILE_OPEN_REPARSE_POINT | FILE_OPEN_FOR_BACKUP_INTENT;

	perms |= SYNCHRONIZE;
	if (perms & (FILE_READ_DATA | FILE_LIST_DIRECTORY)) {
		options |= FILE_SYNCHRONOUS_IO_NONALERT;
		options |= FILE_SEQUENTIAL_ONLY;
	}
retry:
	status = NtOpenFile(h_ret, perms, &attr, &iosb,
			    FILE_SHARE_VALID_FLAGS, options);
	if (!NT_SUCCESS(status)) {
		/* Try requesting fewer permissions  */
		if (status == STATUS_ACCESS_DENIED ||
		    status == STATUS_PRIVILEGE_NOT_HELD) {
			if (perms & ACCESS_SYSTEM_SECURITY) {
				perms &= ~ACCESS_SYSTEM_SECURITY;
				goto retry;
			}
			if (perms & READ_CONTROL) {
				perms &= ~READ_CONTROL;
				goto retry;
			}
		}
	}
	return status;
}

static NTSTATUS
winnt_open(const wchar_t *path, size_t path_nchars, ACCESS_MASK perms,
	   HANDLE *h_ret)
{
	return winnt_openat(NULL, path, path_nchars, perms, h_ret);
}

static const wchar_t *
windows_file_to_string(const struct windows_file *file, u8 *buf, size_t bufsize)
{
	if (file->is_file_id) {
		u64 file_id;
		memcpy(&file_id,
		       (u8 *)file->path + file->path_nbytes - sizeof(file_id),
		       sizeof(file_id));
		swprintf((wchar_t *)buf, L"NTFS inode 0x%016"PRIx64, file_id);
	} else if (file->path_nbytes + 3 * sizeof(wchar_t) <= bufsize) {
		swprintf((wchar_t *)buf, L"\"%ls\"", file->path);
	} else {
		return L"(name too long)";
	}
	return (wchar_t *)buf;
}

static int
read_winnt_stream_prefix(const struct windows_file *file,
			 u64 size, const struct consume_chunk_callback *cb)
{
	IO_STATUS_BLOCK iosb;
	UNICODE_STRING name = {
		.Buffer = (wchar_t *)file->path,
		.Length = file->path_nbytes,
		.MaximumLength = file->path_nbytes,
	};
	OBJECT_ATTRIBUTES attr = {
		.Length = sizeof(attr),
		.ObjectName = &name,
	};
	HANDLE h;
	NTSTATUS status;
	u8 buf[BUFFER_SIZE] _aligned_attribute(8);
	u64 bytes_remaining;
	int ret;

	status = NtOpenFile(&h, FILE_READ_DATA | SYNCHRONIZE,
			    &attr, &iosb,
			    FILE_SHARE_VALID_FLAGS,
			    FILE_OPEN_REPARSE_POINT |
				FILE_OPEN_FOR_BACKUP_INTENT |
				FILE_SYNCHRONOUS_IO_NONALERT |
				FILE_SEQUENTIAL_ONLY |
				(file->is_file_id ? FILE_OPEN_BY_FILE_ID : 0));
	if (unlikely(!NT_SUCCESS(status))) {
		if (status == STATUS_SHARING_VIOLATION) {
			ERROR("Can't open %ls for reading:\n"
			      "        File is in use by another process! "
			      "Consider using snapshot (VSS) mode.",
			      windows_file_to_string(file, buf, sizeof(buf)));
		} else {
			winnt_error(status, L"Can't open %ls for reading",
				    windows_file_to_string(file, buf, sizeof(buf)));
		}
		return WIMLIB_ERR_OPEN;
	}

	ret = 0;
	bytes_remaining = size;
	while (bytes_remaining) {
		IO_STATUS_BLOCK iosb;
		ULONG count;
		ULONG bytes_read;
		const unsigned max_tries = 5;
		unsigned tries_remaining = max_tries;

		count = min(sizeof(buf), bytes_remaining);

	retry_read:
		status = NtReadFile(h, NULL, NULL, NULL,
				    &iosb, buf, count, NULL, NULL);
		if (unlikely(!NT_SUCCESS(status))) {
			if (status == STATUS_END_OF_FILE) {
				ERROR("%ls: File was concurrently truncated",
				      windows_file_to_string(file, buf, sizeof(buf)));
				ret = WIMLIB_ERR_CONCURRENT_MODIFICATION_DETECTED;
			} else {
				winnt_warning(status, L"Error reading data from %ls",
					      windows_file_to_string(file, buf, sizeof(buf)));

				/* Currently these retries are purely a guess;
				 * there is no reproducible problem that they solve.  */
				if (--tries_remaining) {
					int delay = 100;
					if (status == STATUS_INSUFFICIENT_RESOURCES ||
					    status == STATUS_NO_MEMORY) {
						delay *= 25;
					}
					WARNING("Retrying after %dms...", delay);
					Sleep(delay);
					goto retry_read;
				}
				ERROR("Too many retries; returning failure");
				ret = WIMLIB_ERR_READ;
			}
			break;
		} else if (unlikely(tries_remaining != max_tries)) {
			WARNING("A read request had to be retried multiple times "
				"before it succeeded!");
		}

		bytes_read = iosb.Information;

		bytes_remaining -= bytes_read;
		ret = consume_chunk(cb, buf, bytes_read);
		if (ret)
			break;
	}
	NtClose(h);
	return ret;
}

struct win32_encrypted_read_ctx {
	const struct consume_chunk_callback *cb;
	int wimlib_err_code;
	u64 bytes_remaining;
};

static DWORD WINAPI
win32_encrypted_export_cb(unsigned char *data, void *_ctx, unsigned long len)
{
	struct win32_encrypted_read_ctx *ctx = _ctx;
	int ret;
	size_t bytes_to_consume = min(len, ctx->bytes_remaining);

	if (bytes_to_consume == 0)
		return ERROR_SUCCESS;

	ret = consume_chunk(ctx->cb, data, bytes_to_consume);
	if (ret) {
		ctx->wimlib_err_code = ret;
		/* It doesn't matter what error code is returned here, as long
		 * as it isn't ERROR_SUCCESS.  */
		return ERROR_READ_FAULT;
	}
	ctx->bytes_remaining -= bytes_to_consume;
	return ERROR_SUCCESS;
}

static int
read_win32_encrypted_file_prefix(const wchar_t *path, bool is_dir, u64 size,
				 const struct consume_chunk_callback *cb)
{
	struct win32_encrypted_read_ctx export_ctx;
	DWORD err;
	void *file_ctx;
	int ret;
	DWORD flags = 0;

	if (is_dir)
		flags |= CREATE_FOR_DIR;

	export_ctx.cb = cb;
	export_ctx.wimlib_err_code = 0;
	export_ctx.bytes_remaining = size;

	err = OpenEncryptedFileRaw(path, flags, &file_ctx);
	if (err != ERROR_SUCCESS) {
		win32_error(err,
			    L"Failed to open encrypted file \"%ls\" for raw read",
			    path);
		return WIMLIB_ERR_OPEN;
	}
	err = ReadEncryptedFileRaw(win32_encrypted_export_cb,
				   &export_ctx, file_ctx);
	if (err != ERROR_SUCCESS) {
		ret = export_ctx.wimlib_err_code;
		if (ret == 0) {
			win32_error(err,
				    L"Failed to read encrypted file \"%ls\"",
				    path);
			ret = WIMLIB_ERR_READ;
		}
	} else if (export_ctx.bytes_remaining != 0) {
		ERROR("Only could read %"PRIu64" of %"PRIu64" bytes from "
		      "encrypted file \"%ls\"",
		      size - export_ctx.bytes_remaining, size,
		      path);
		ret = WIMLIB_ERR_READ;
	} else {
		ret = 0;
	}
	CloseEncryptedFileRaw(file_ctx);
	return ret;
}

/* Read the first @size bytes from the file, or named data stream of a file,
 * described by @blob.  */
int
read_windows_file_prefix(const struct blob_descriptor *blob, u64 size,
			 const struct consume_chunk_callback *cb)
{
	const struct windows_file *file = blob->windows_file;

	if (unlikely(file->is_encrypted)) {
		bool is_dir = (blob->file_inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY);
		return read_win32_encrypted_file_prefix(file->path, is_dir, size, cb);
	}

	return read_winnt_stream_prefix(file, size, cb);
}

/*
 * Load the short name of a file into a WIM dentry.
 */
static noinline_for_stack NTSTATUS
winnt_get_short_name(HANDLE h, struct wim_dentry *dentry)
{
	/* It's not any harder to just make the NtQueryInformationFile() system
	 * call ourselves, and it saves a dumb call to FindFirstFile() which of
	 * course has to create its own handle.  */
	NTSTATUS status;
	IO_STATUS_BLOCK iosb;
	u8 buf[128] _aligned_attribute(8);
	const FILE_NAME_INFORMATION *info;

	status = NtQueryInformationFile(h, &iosb, buf, sizeof(buf),
					FileAlternateNameInformation);
	info = (const FILE_NAME_INFORMATION *)buf;
	if (NT_SUCCESS(status) && info->FileNameLength != 0) {
		dentry->d_short_name = utf16le_dupz(info->FileName,
						    info->FileNameLength);
		if (!dentry->d_short_name)
			return STATUS_NO_MEMORY;
		dentry->d_short_name_nbytes = info->FileNameLength;
	}
	return status;
}

/*
 * Load the security descriptor of a file into the corresponding inode and the
 * WIM image's security descriptor set.
 */
static noinline_for_stack int
winnt_load_security_descriptor(HANDLE h, struct wim_inode *inode,
			       struct winnt_scan_ctx *ctx)
{
	SECURITY_INFORMATION requestedInformation;
	u8 _buf[4096] _aligned_attribute(8);
	u8 *buf;
	ULONG bufsize;
	ULONG len_needed;
	NTSTATUS status;

	/*
	 * LABEL_SECURITY_INFORMATION is needed on Windows Vista and 7 because
	 * Microsoft decided to add mandatory integrity labels to the SACL but
	 * not have them returned by SACL_SECURITY_INFORMATION.
	 *
	 * BACKUP_SECURITY_INFORMATION is needed on Windows 8 because Microsoft
	 * decided to add even more stuff to the SACL and still not have it
	 * returned by SACL_SECURITY_INFORMATION; but they did remember that
	 * backup applications exist and simply want to read the stupid thing
	 * once and for all, so they added a flag to read the entire security
	 * descriptor.
	 *
	 * Older versions of Windows tolerate these new flags being passed in.
	 */
	requestedInformation = OWNER_SECURITY_INFORMATION |
			       GROUP_SECURITY_INFORMATION |
			       DACL_SECURITY_INFORMATION |
			       SACL_SECURITY_INFORMATION |
			       LABEL_SECURITY_INFORMATION |
			       BACKUP_SECURITY_INFORMATION;

	buf = _buf;
	bufsize = sizeof(_buf);

	/*
	 * We need the file's security descriptor in
	 * SECURITY_DESCRIPTOR_RELATIVE format, and we currently have a handle
	 * opened with as many relevant permissions as possible.  At this point,
	 * on Windows there are a number of options for reading a file's
	 * security descriptor:
	 *
	 * GetFileSecurity():  This takes in a path and returns the
	 * SECURITY_DESCRIPTOR_RELATIVE.  Problem: this uses an internal handle,
	 * not ours, and the handle created internally doesn't specify
	 * FILE_FLAG_BACKUP_SEMANTICS.  Therefore there can be access denied
	 * errors on some files and directories, even when running as the
	 * Administrator.
	 *
	 * GetSecurityInfo():  This takes in a handle and returns the security
	 * descriptor split into a bunch of different parts.  This should work,
	 * but it's dumb because we have to put the security descriptor back
	 * together again.
	 *
	 * BackupRead():  This can read the security descriptor, but this is a
	 * difficult-to-use API, probably only works as the Administrator, and
	 * the format of the returned data is not well documented.
	 *
	 * NtQuerySecurityObject():  This is exactly what we need, as it takes
	 * in a handle and returns the security descriptor in
	 * SECURITY_DESCRIPTOR_RELATIVE format.  Only problem is that it's a
	 * ntdll function and therefore not officially part of the Win32 API.
	 * Oh well.
	 */
	while (!NT_SUCCESS(status = NtQuerySecurityObject(h,
							  requestedInformation,
							  (PSECURITY_DESCRIPTOR)buf,
							  bufsize,
							  &len_needed)))
	{
		switch (status) {
		case STATUS_BUFFER_TOO_SMALL:
			wimlib_assert(buf == _buf);
			buf = MALLOC(len_needed);
			if (!buf) {
				status = STATUS_NO_MEMORY;
				goto out;
			}
			bufsize = len_needed;
			break;
		case STATUS_PRIVILEGE_NOT_HELD:
		case STATUS_ACCESS_DENIED:
			if (ctx->params->add_flags & WIMLIB_ADD_FLAG_STRICT_ACLS) {
		default:
				/* Permission denied in STRICT_ACLS mode, or
				 * unknown error.  */
				goto out;
			}
			if (requestedInformation & SACL_SECURITY_INFORMATION) {
				/* Try again without the SACL.  */
				ctx->num_get_sacl_priv_notheld++;
				requestedInformation &= ~(SACL_SECURITY_INFORMATION |
							  LABEL_SECURITY_INFORMATION |
							  BACKUP_SECURITY_INFORMATION);
				break;
			}
			/* Fake success (useful when capturing as
			 * non-Administrator).  */
			ctx->num_get_sd_access_denied++;
			status = STATUS_SUCCESS;
			goto out;
		}
	}

	/* We can get a length of 0 with Samba.  Assume that means "no security
	 * descriptor".  */
	if (len_needed == 0)
		goto out;

	/* Add the security descriptor to the WIM image, and save its ID in
	 * the file's inode.  */
	inode->i_security_id = sd_set_add_sd(ctx->params->sd_set, buf, len_needed);
	if (unlikely(inode->i_security_id < 0))
		status = STATUS_NO_MEMORY;
out:
	if (unlikely(buf != _buf))
		FREE(buf);
	if (!NT_SUCCESS(status)) {
		winnt_error(status, L"\"%ls\": Can't read security descriptor",
			    printable_path(ctx));
		return WIMLIB_ERR_STAT;
	}
	return 0;
}

/* Load a file's object ID into the corresponding WIM inode.  */
static noinline_for_stack int
winnt_load_object_id(HANDLE h, struct wim_inode *inode,
		     struct winnt_scan_ctx *ctx)
{
	FILE_OBJECTID_BUFFER buffer;
	NTSTATUS status;
	u32 len;

	if (!(ctx->vol_flags & FILE_SUPPORTS_OBJECT_IDS))
		return 0;

	status = winnt_fsctl(h, FSCTL_GET_OBJECT_ID, NULL, 0,
			     &buffer, sizeof(buffer), &len);

	if (status == STATUS_OBJECTID_NOT_FOUND) /* No object ID  */
		return 0;

	if (status == STATUS_INVALID_DEVICE_REQUEST ||
	    status == STATUS_NOT_SUPPORTED /* Samba volume, WinXP */) {
		/* The filesystem claimed to support object IDs, but we can't
		 * actually read them.  This happens with Samba.  */
		ctx->vol_flags &= ~FILE_SUPPORTS_OBJECT_IDS;
		return 0;
	}

	if (!NT_SUCCESS(status)) {
		winnt_error(status, L"\"%ls\": Can't read object ID",
			    printable_path(ctx));
		return WIMLIB_ERR_STAT;
	}

	if (len == 0) /* No object ID (for directories)  */
		return 0;

	if (!inode_set_object_id(inode, &buffer, len))
		return WIMLIB_ERR_NOMEM;

	return 0;
}

/* Load a file's extended attributes into the corresponding WIM inode.  */
static noinline_for_stack int
winnt_load_xattrs(HANDLE h, struct wim_inode *inode,
		  struct winnt_scan_ctx *ctx, u32 ea_size)
{
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;
	u8 _buf[1024] _aligned_attribute(4);
	u8 *buf = _buf;
	const FILE_FULL_EA_INFORMATION *ea;
	struct wim_xattr_entry *entry;
	int ret;


	/*
	 * EaSize from FILE_EA_INFORMATION is apparently supposed to give the
	 * size of the buffer required for NtQueryEaFile(), but it doesn't
	 * actually work correctly; it can be off by about 4 bytes per xattr.
	 *
	 * So just start out by doubling the advertised size, and also handle
	 * STATUS_BUFFER_OVERFLOW just in case.
	 */
retry:
	if (unlikely(ea_size * 2 < ea_size))
		ea_size = UINT32_MAX;
	else
		ea_size *= 2;
	if (unlikely(ea_size > sizeof(_buf))) {
		buf = MALLOC(ea_size);
		if (!buf) {
			if (ea_size >= (1 << 20)) {
				WARNING("\"%ls\": EaSize was extremely large (%u)",
					printable_path(ctx), ea_size);
			}
			return WIMLIB_ERR_NOMEM;
		}
	}

	status = NtQueryEaFile(h, &iosb, buf, ea_size,
			       FALSE, NULL, 0, NULL, TRUE);

	if (unlikely(!NT_SUCCESS(status))) {
		if (status == STATUS_BUFFER_OVERFLOW) {
			if (buf != _buf) {
				FREE(buf);
				buf = NULL;
			}
			goto retry;
		}
		if (status == STATUS_NO_EAS_ON_FILE) {
			/*
			 * FILE_EA_INFORMATION.EaSize was nonzero so this
			 * shouldn't happen, but just in case...
			 */
			ret = 0;
			goto out;
		}
		winnt_error(status, L"\"%ls\": Can't read extended attributes",
			    printable_path(ctx));
		ret = WIMLIB_ERR_STAT;
		goto out;
	}

	ea = (const FILE_FULL_EA_INFORMATION *)buf;
	entry = (struct wim_xattr_entry *)buf;
	for (;;) {
		/*
		 * wim_xattr_entry is not larger than FILE_FULL_EA_INFORMATION,
		 * so we can reuse the same buffer by overwriting the
		 * FILE_FULL_EA_INFORMATION with the wim_xattr_entry in-place.
		 */
		FILE_FULL_EA_INFORMATION _ea;

		STATIC_ASSERT(offsetof(struct wim_xattr_entry, name) <=
			      offsetof(FILE_FULL_EA_INFORMATION, EaName));
		wimlib_assert((u8 *)entry <= (const u8 *)ea);

		memcpy(&_ea, ea, sizeof(_ea));

		entry->value_len = cpu_to_le16(_ea.EaValueLength);
		entry->name_len = _ea.EaNameLength;
		entry->flags = _ea.Flags;
		memmove(entry->name, ea->EaName, _ea.EaNameLength);
		entry->name[_ea.EaNameLength] = '\0';
		memmove(&entry->name[_ea.EaNameLength + 1],
			&ea->EaName[_ea.EaNameLength + 1], _ea.EaValueLength);
		entry = (struct wim_xattr_entry *)
			 &entry->name[_ea.EaNameLength + 1 + _ea.EaValueLength];
		if (_ea.NextEntryOffset == 0)
			break;
		ea = (const FILE_FULL_EA_INFORMATION *)
			((const u8 *)ea + _ea.NextEntryOffset);
	}
	wimlib_assert((u8 *)entry - buf <= ea_size);

	ret = WIMLIB_ERR_NOMEM;
	if (!inode_set_xattrs(inode, buf, (u8 *)entry - buf))
		goto out;
	ret = 0;
out:
	if (unlikely(buf != _buf))
		FREE(buf);
	return ret;
}

static int
winnt_build_dentry_tree_recursive(struct wim_dentry **root_ret,
				  HANDLE cur_dir,
				  const wchar_t *relative_path,
				  size_t relative_path_nchars,
				  const wchar_t *filename,
				  struct winnt_scan_ctx *ctx);

static int
winnt_recurse_directory(HANDLE h,
			struct wim_dentry *parent,
			struct winnt_scan_ctx *ctx)
{
	void *buf;
	const size_t bufsize = 8192;
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;
	int ret;

	buf = MALLOC(bufsize);
	if (!buf)
		return WIMLIB_ERR_NOMEM;

	/* Using NtQueryDirectoryFile() we can re-use the same open handle,
	 * which we opened with FILE_FLAG_BACKUP_SEMANTICS.  */

	while (NT_SUCCESS(status = NtQueryDirectoryFile(h, NULL, NULL, NULL,
							&iosb, buf, bufsize,
							FileNamesInformation,
							FALSE, NULL, FALSE)))
	{
		const FILE_NAMES_INFORMATION *info = buf;
		for (;;) {
			if (!should_ignore_filename(info->FileName,
						    info->FileNameLength / 2))
			{
				struct wim_dentry *child;
				size_t orig_path_nchars;
				const wchar_t *filename;

				ret = WIMLIB_ERR_NOMEM;
				filename = pathbuf_append_name(ctx->params,
							       info->FileName,
							       info->FileNameLength / 2,
							       &orig_path_nchars);
				if (!filename)
					goto out_free_buf;

				ret = winnt_build_dentry_tree_recursive(
							&child,
							h,
							filename,
							info->FileNameLength / 2,
							filename,
							ctx);

				pathbuf_truncate(ctx->params, orig_path_nchars);

				if (ret)
					goto out_free_buf;
				attach_scanned_tree(parent, child,
						    ctx->params->blob_table);
			}
			if (info->NextEntryOffset == 0)
				break;
			info = (const FILE_NAMES_INFORMATION *)
					((const u8 *)info + info->NextEntryOffset);
		}
	}

	if (unlikely(status != STATUS_NO_MORE_FILES)) {
		winnt_error(status, L"\"%ls\": Can't read directory",
			    printable_path(ctx));
		ret = WIMLIB_ERR_READ;
	}
out_free_buf:
	FREE(buf);
	return ret;
}

/* Reparse point fixup status code  */
#define RP_FIXED	(-1)

static bool
file_has_ino_and_dev(HANDLE h, u64 ino, u64 dev)
{
	NTSTATUS status;
	IO_STATUS_BLOCK iosb;
	FILE_INTERNAL_INFORMATION int_info;
	FILE_FS_VOLUME_INFORMATION vol_info;

	status = NtQueryInformationFile(h, &iosb, &int_info, sizeof(int_info),
					FileInternalInformation);
	if (!NT_SUCCESS(status))
		return false;

	if (int_info.IndexNumber.QuadPart != ino)
		return false;

	status = NtQueryVolumeInformationFile(h, &iosb,
					      &vol_info, sizeof(vol_info),
					      FileFsVolumeInformation);
	if (!(NT_SUCCESS(status) || status == STATUS_BUFFER_OVERFLOW))
		return false;

	if (iosb.Information <
	     offsetof(FILE_FS_VOLUME_INFORMATION, VolumeSerialNumber) +
	     sizeof(vol_info.VolumeSerialNumber))
		return false;

	return (vol_info.VolumeSerialNumber == dev);
}

/*
 * This is the Windows equivalent of unix_relativize_link_target(); see there
 * for general details.  This version works with an "absolute" Windows link
 * target, specified from the root of the Windows kernel object namespace.  Note
 * that we have to open directories with a trailing slash when present because
 * \??\E: opens the E: device itself and not the filesystem root directory.
 */
static const wchar_t *
winnt_relativize_link_target(const wchar_t *target, size_t target_nbytes,
			     u64 ino, u64 dev)
{
	UNICODE_STRING name;
	OBJECT_ATTRIBUTES attr;
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;
	const wchar_t *target_end;
	const wchar_t *p;

	target_end = target + (target_nbytes / sizeof(wchar_t));

	/* Empty path??? */
	if (target_end == target)
		return target;

	/* No leading slash???  */
	if (target[0] != L'\\')
		return target;

	/* UNC path???  */
	if ((target_end - target) >= 2 &&
	    target[0] == L'\\' && target[1] == L'\\')
		return target;

	attr.Length = sizeof(attr);
	attr.RootDirectory = NULL;
	attr.ObjectName = &name;
	attr.Attributes = 0;
	attr.SecurityDescriptor = NULL;
	attr.SecurityQualityOfService = NULL;

	name.Buffer = (wchar_t *)target;
	name.Length = 0;
	p = target;
	do {
		HANDLE h;
		const wchar_t *orig_p = p;

		/* Skip non-backslashes  */
		while (p != target_end && *p != L'\\')
			p++;

		/* Skip backslashes  */
		while (p != target_end && *p == L'\\')
			p++;

		/* Append path component  */
		name.Length += (p - orig_p) * sizeof(wchar_t);
		name.MaximumLength = name.Length;

		/* Try opening the file  */
		status = NtOpenFile(&h,
				    FILE_READ_ATTRIBUTES | FILE_TRAVERSE,
				    &attr,
				    &iosb,
				    FILE_SHARE_VALID_FLAGS,
				    FILE_OPEN_FOR_BACKUP_INTENT);

		if (NT_SUCCESS(status)) {
			/* Reset root directory  */
			if (attr.RootDirectory)
				NtClose(attr.RootDirectory);
			attr.RootDirectory = h;
			name.Buffer = (wchar_t *)p;
			name.Length = 0;

			if (file_has_ino_and_dev(h, ino, dev))
				goto out_close_root_dir;
		}
	} while (p != target_end);

	p = target;

out_close_root_dir:
	if (attr.RootDirectory)
		NtClose(attr.RootDirectory);
	while (p > target && *(p - 1) == L'\\')
		p--;
	return p;
}

static int
winnt_rpfix_progress(struct scan_params *params,
		     const struct link_reparse_point *link, int scan_status)
{
	size_t print_name_nchars = link->print_name_nbytes / sizeof(wchar_t);
	wchar_t print_name0[print_name_nchars + 1];

	wmemcpy(print_name0, link->print_name, print_name_nchars);
	print_name0[print_name_nchars] = L'\0';

	params->progress.scan.symlink_target = print_name0;
	return do_scan_progress(params, scan_status, NULL);
}

static int
winnt_try_rpfix(struct reparse_buffer_disk *rpbuf, u16 *rpbuflen_p,
		struct scan_params *params)
{
	struct link_reparse_point link;
	const wchar_t *rel_target;
	int ret;

	if (parse_link_reparse_point(rpbuf, *rpbuflen_p, &link)) {
		/* Couldn't understand the reparse data; don't do the fixup.  */
		return 0;
	}

	/*
	 * Don't do reparse point fixups on relative symbolic links.
	 *
	 * On Windows, a relative symbolic link is supposed to be identifiable
	 * by having reparse tag WIM_IO_REPARSE_TAG_SYMLINK and flags
	 * SYMBOLIC_LINK_RELATIVE.  We will use this information, although this
	 * may not always do what the user expects, since drive-relative
	 * symbolic links such as "\Users\Public" have SYMBOLIC_LINK_RELATIVE
	 * set, in addition to truly relative symbolic links such as "Users" or
	 * "Users\Public".  However, WIMGAPI (as of Windows 8.1) has this same
	 * behavior.
	 *
	 * Otherwise, as far as I can tell, the targets of symbolic links that
	 * are NOT relative, as well as junctions (note: a mountpoint is the
	 * sames thing as a junction), must be NT namespace paths, for example:
	 *
	 *     - \??\e:\Users\Public
	 *     - \DosDevices\e:\Users\Public
	 *     - \Device\HardDiskVolume4\Users\Public
	 *     - \??\Volume{c47cb07c-946e-4155-b8f7-052e9cec7628}\Users\Public
	 *     - \DosDevices\Volume{c47cb07c-946e-4155-b8f7-052e9cec7628}\Users\Public
	 */
	if (link_is_relative_symlink(&link))
		return 0;

	rel_target = winnt_relativize_link_target(link.substitute_name,
						  link.substitute_name_nbytes,
						  params->capture_root_ino,
						  params->capture_root_dev);

	if (rel_target == link.substitute_name) {
		/* Target points outside of the tree being captured or had an
		 * unrecognized path format.  Don't adjust it.  */
		return winnt_rpfix_progress(params, &link,
					    WIMLIB_SCAN_DENTRY_NOT_FIXED_SYMLINK);
	}

	/* We have an absolute target pointing within the directory being
	 * captured. @rel_target is the suffix of the link target that is the
	 * part relative to the directory being captured.
	 *
	 * We will cut off the prefix before this part (which is the path to the
	 * directory being captured) and add a dummy prefix.  Since the process
	 * will need to be reversed when applying the image, it doesn't matter
	 * what exactly the prefix is, as long as it looks like an absolute
	 * path.  */

	static const wchar_t prefix[6] = L"\\??\\X:";
	static const size_t num_unprintable_chars = 4;

	size_t rel_target_nbytes =
		link.substitute_name_nbytes - ((const u8 *)rel_target -
					       (const u8 *)link.substitute_name);

	wchar_t tmp[(sizeof(prefix) + rel_target_nbytes) / sizeof(wchar_t)];

	memcpy(tmp, prefix, sizeof(prefix));
	memcpy(tmp + ARRAY_LEN(prefix), rel_target, rel_target_nbytes);

	link.substitute_name = tmp;
	link.substitute_name_nbytes = sizeof(tmp);

	link.print_name = link.substitute_name + num_unprintable_chars;
	link.print_name_nbytes = link.substitute_name_nbytes -
				 (num_unprintable_chars * sizeof(wchar_t));

	if (make_link_reparse_point(&link, rpbuf, rpbuflen_p))
		return 0;

	ret = winnt_rpfix_progress(params, &link,
				   WIMLIB_SCAN_DENTRY_FIXED_SYMLINK);
	if (ret)
		return ret;
	return RP_FIXED;
}

/* Load the reparse data of a file into the corresponding WIM inode.  If the
 * reparse point is a symbolic link or junction with an absolute target and
 * RPFIX mode is enabled, then also rewrite its target to be relative to the
 * capture root.  */
static noinline_for_stack int
winnt_load_reparse_data(HANDLE h, struct wim_inode *inode,
			struct winnt_scan_ctx *ctx)
{
	struct reparse_buffer_disk rpbuf;
	NTSTATUS status;
	u32 len;
	u16 rpbuflen;
	int ret;

	if (inode->i_attributes & FILE_ATTRIBUTE_ENCRYPTED) {
		/* See comment above assign_stream_types_encrypted()  */
		WARNING("Ignoring reparse data of encrypted file \"%ls\"",
			printable_path(ctx));
		return 0;
	}

	status = winnt_fsctl(h, FSCTL_GET_REPARSE_POINT,
			     NULL, 0, &rpbuf, sizeof(rpbuf), &len);
	if (!NT_SUCCESS(status)) {
		winnt_error(status, L"\"%ls\": Can't get reparse point",
			    printable_path(ctx));
		return WIMLIB_ERR_READLINK;
	}

	rpbuflen = len;

	if (unlikely(rpbuflen < REPARSE_DATA_OFFSET)) {
		ERROR("\"%ls\": reparse point buffer is too short",
		      printable_path(ctx));
		return WIMLIB_ERR_INVALID_REPARSE_DATA;
	}

	if (le32_to_cpu(rpbuf.rptag) == WIM_IO_REPARSE_TAG_DEDUP) {
		/*
		 * Windows treats Data Deduplication reparse points specially.
		 * Reads from the unnamed data stream actually return the
		 * redirected file contents, even with FILE_OPEN_REPARSE_POINT.
		 * Deduplicated files also cannot be properly restored without
		 * also restoring the "System Volume Information" directory,
		 * which wimlib excludes by default.  Therefore, the logical
		 * behavior for us seems to be to ignore the reparse point and
		 * treat the file as a normal file.
		 */
		inode->i_attributes &= ~FILE_ATTRIBUTE_REPARSE_POINT;
		return 0;
	}

	if (ctx->params->add_flags & WIMLIB_ADD_FLAG_RPFIX) {
		ret = winnt_try_rpfix(&rpbuf, &rpbuflen, ctx->params);
		if (ret == RP_FIXED)
			inode->i_rp_flags &= ~WIM_RP_FLAG_NOT_FIXED;
		else if (ret)
			return ret;
	}

	inode->i_reparse_tag = le32_to_cpu(rpbuf.rptag);
	inode->i_rp_reserved = le16_to_cpu(rpbuf.rpreserved);

	if (!inode_add_stream_with_data(inode,
					STREAM_TYPE_REPARSE_POINT,
					NO_STREAM_NAME,
					rpbuf.rpdata,
					rpbuflen - REPARSE_DATA_OFFSET,
					ctx->params->blob_table))
		return WIMLIB_ERR_NOMEM;

	return 0;
}

static DWORD WINAPI
win32_tally_encrypted_size_cb(unsigned char *_data, void *_size_ret,
			      unsigned long len)
{
	*(u64*)_size_ret += len;
	return ERROR_SUCCESS;
}

static int
win32_get_encrypted_file_size(const wchar_t *path, bool is_dir, u64 *size_ret)
{
	DWORD err;
	void *file_ctx;
	int ret;
	DWORD flags = 0;

	if (is_dir)
		flags |= CREATE_FOR_DIR;

	err = OpenEncryptedFileRaw(path, flags, &file_ctx);
	if (err != ERROR_SUCCESS) {
		win32_error(err,
			    L"Failed to open encrypted file \"%ls\" for raw read",
			    path);
		return WIMLIB_ERR_OPEN;
	}
	*size_ret = 0;
	err = ReadEncryptedFileRaw(win32_tally_encrypted_size_cb,
				   size_ret, file_ctx);
	if (err != ERROR_SUCCESS) {
		win32_error(err,
			    L"Failed to read raw encrypted data from \"%ls\"",
			    path);
		ret = WIMLIB_ERR_READ;
	} else {
		ret = 0;
	}
	CloseEncryptedFileRaw(file_ctx);
	return ret;
}

static int
winnt_scan_efsrpc_raw_data(struct wim_inode *inode,
			   struct winnt_scan_ctx *ctx)
{
	wchar_t *path = ctx->params->cur_path;
	size_t path_nchars = ctx->params->cur_path_nchars;
	const bool is_dir = (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY);
	struct windows_file *windows_file;
	u64 size;
	int ret;

	/* OpenEncryptedFileRaw() expects a Win32 name.  */
	wimlib_assert(!wmemcmp(path, L"\\??\\", 4));
	path[1] = L'\\';

	ret = win32_get_encrypted_file_size(path, is_dir, &size);
	if (ret)
		goto out;

	/* Empty EFSRPC data does not make sense  */
	wimlib_assert(size != 0);

	windows_file = alloc_windows_file(path, path_nchars, NULL, 0,
					  ctx->snapshot, true);
	ret = add_stream(inode, windows_file, size, STREAM_TYPE_EFSRPC_RAW_DATA,
			 NO_STREAM_NAME, ctx->params->unhashed_blobs);
out:
	path[1] = L'?';
	return ret;
}

static bool
get_data_stream_name(const wchar_t *raw_stream_name, size_t raw_stream_name_nchars,
		     const wchar_t **stream_name_ret, size_t *stream_name_nchars_ret)
{
	const wchar_t *sep, *type, *end;

	/* The stream name should be returned as :NAME:TYPE  */
	if (raw_stream_name_nchars < 1)
		return false;
	if (raw_stream_name[0] != L':')
		return false;

	raw_stream_name++;
	raw_stream_name_nchars--;

	end = raw_stream_name + raw_stream_name_nchars;

	sep = wmemchr(raw_stream_name, L':', raw_stream_name_nchars);
	if (!sep)
		return false;

	type = sep + 1;
	if (end - type != 5)
		return false;

	if (wmemcmp(type, L"$DATA", 5))
		return false;

	*stream_name_ret = raw_stream_name;
	*stream_name_nchars_ret = sep - raw_stream_name;
	return true;
}

static int
winnt_scan_data_stream(wchar_t *raw_stream_name, size_t raw_stream_name_nchars,
		       u64 stream_size, struct wim_inode *inode,
		       struct winnt_scan_ctx *ctx)
{
	wchar_t *stream_name;
	size_t stream_name_nchars;
	struct windows_file *windows_file;

	/* Given the raw stream name (which is something like
	 * :streamname:$DATA), extract just the stream name part (streamname).
	 * Ignore any non-$DATA streams.  */
	if (!get_data_stream_name(raw_stream_name, raw_stream_name_nchars,
				  (const wchar_t **)&stream_name,
				  &stream_name_nchars))
		return 0;

	stream_name[stream_name_nchars] = L'\0';

	windows_file = alloc_windows_file(ctx->params->cur_path,
					  ctx->params->cur_path_nchars,
					  stream_name, stream_name_nchars,
					  ctx->snapshot, false);
	return add_stream(inode, windows_file, stream_size, STREAM_TYPE_DATA,
			  stream_name, ctx->params->unhashed_blobs);
}

/*
 * Load information about the data streams of an open file into a WIM inode.
 *
 * We use the NtQueryInformationFile() system call instead of FindFirstStream()
 * and FindNextStream().  This is done for two reasons:
 *
 * - FindFirstStream() opens its own handle to the file or directory and
 *   apparently does so without specifying FILE_FLAG_BACKUP_SEMANTICS, thereby
 *   causing access denied errors on certain files (even when running as the
 *   Administrator).
 * - FindFirstStream() and FindNextStream() is only available on Windows Vista
 *   and later, whereas the stream support in NtQueryInformationFile() was
 *   already present in Windows XP.
 */
static noinline_for_stack int
winnt_scan_data_streams(HANDLE h, struct wim_inode *inode, u64 file_size,
			struct winnt_scan_ctx *ctx)
{
	int ret;
	u8 _buf[4096] _aligned_attribute(8);
	u8 *buf;
	size_t bufsize;
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;
	FILE_STREAM_INFORMATION *info;

	buf = _buf;
	bufsize = sizeof(_buf);

	if (!(ctx->vol_flags & FILE_NAMED_STREAMS))
		goto unnamed_only;

	/* Get a buffer containing the stream information.  */
	while (!NT_SUCCESS(status = NtQueryInformationFile(h,
							   &iosb,
							   buf,
							   bufsize,
							   FileStreamInformation)))
	{

		switch (status) {
		case STATUS_BUFFER_OVERFLOW:
			{
				u8 *newbuf;

				bufsize *= 2;
				if (buf == _buf)
					newbuf = MALLOC(bufsize);
				else
					newbuf = REALLOC(buf, bufsize);
				if (!newbuf) {
					ret = WIMLIB_ERR_NOMEM;
					goto out_free_buf;
				}
				buf = newbuf;
			}
			break;
		case STATUS_NOT_IMPLEMENTED:
		case STATUS_NOT_SUPPORTED:
		case STATUS_INVALID_INFO_CLASS:
			goto unnamed_only;
		default:
			winnt_error(status,
				    L"\"%ls\": Failed to query stream information",
				    printable_path(ctx));
			ret = WIMLIB_ERR_READ;
			goto out_free_buf;
		}
	}

	if (iosb.Information == 0) {
		/* No stream information.  */
		ret = 0;
		goto out_free_buf;
	}

	/* Parse one or more stream information structures.  */
	info = (FILE_STREAM_INFORMATION *)buf;
	for (;;) {
		/* Load the stream information.  */
		ret = winnt_scan_data_stream(info->StreamName,
					     info->StreamNameLength / 2,
					     info->StreamSize.QuadPart,
					     inode, ctx);
		if (ret)
			goto out_free_buf;

		if (info->NextEntryOffset == 0) {
			/* No more stream information.  */
			break;
		}
		/* Advance to next stream information.  */
		info = (FILE_STREAM_INFORMATION *)
				((u8 *)info + info->NextEntryOffset);
	}
	ret = 0;
	goto out_free_buf;

unnamed_only:
	/* The volume does not support named streams.  Only capture the unnamed
	 * data stream.  */
	if (inode->i_attributes & (FILE_ATTRIBUTE_DIRECTORY |
				   FILE_ATTRIBUTE_REPARSE_POINT))
	{
		ret = 0;
		goto out_free_buf;
	}

	{
		wchar_t stream_name[] = L"::$DATA";
		ret = winnt_scan_data_stream(stream_name, 7, file_size,
					     inode, ctx);
	}
out_free_buf:
	/* Free buffer if allocated on heap.  */
	if (unlikely(buf != _buf))
		FREE(buf);
	return ret;
}

static u64
extract_starting_lcn(const RETRIEVAL_POINTERS_BUFFER *extents)
{
	if (extents->ExtentCount < 1)
		return 0;

	return extents->Extents[0].Lcn.QuadPart;
}

static noinline_for_stack u64
get_sort_key(HANDLE h)
{
	STARTING_VCN_INPUT_BUFFER in = { .StartingVcn.QuadPart = 0 };
	RETRIEVAL_POINTERS_BUFFER out;

	if (!NT_SUCCESS(winnt_fsctl(h, FSCTL_GET_RETRIEVAL_POINTERS,
				    &in, sizeof(in), &out, sizeof(out), NULL)))
		return 0;

	return extract_starting_lcn(&out);
}

static void
set_sort_key(struct wim_inode *inode, u64 sort_key)
{
	for (unsigned i = 0; i < inode->i_num_streams; i++) {
		struct wim_inode_stream *strm = &inode->i_streams[i];
		struct blob_descriptor *blob = stream_blob_resolved(strm);
		if (blob && blob->blob_location == BLOB_IN_WINDOWS_FILE)
			blob->windows_file->sort_key = sort_key;
	}
}

static inline bool
should_try_to_use_wimboot_hash(const struct wim_inode *inode,
			       const struct winnt_scan_ctx *ctx)
{
	/* Directories and encrypted files aren't valid for external backing. */
	if (inode->i_attributes & (FILE_ATTRIBUTE_DIRECTORY |
				   FILE_ATTRIBUTE_ENCRYPTED))
		return false;

	/* If the file is a reparse point, then try the hash fixup if it's a WOF
	 * reparse point and we're in WIMBOOT mode.  Otherwise, try the hash
	 * fixup if WOF may be attached. */
	if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)
		return (inode->i_reparse_tag == WIM_IO_REPARSE_TAG_WOF) &&
			(ctx->params->add_flags & WIMLIB_ADD_FLAG_WIMBOOT);
	return !ctx->wof_not_attached;
}

/*
 * This function implements an optimization for capturing files from a
 * filesystem with a backing WIM(s).  If a file is WIM-backed, then we can
 * retrieve the SHA-1 message digest of its original contents from its reparse
 * point.  This may eliminate the need to read the file's data and/or allow the
 * file's data to be immediately deduplicated with existing data in the WIM.
 *
 * If WOF is attached, then this function is merely an optimization, but
 * potentially a very effective one.  If WOF is detached, then this function
 * really causes WIM-backed files to be, effectively, automatically
 * "dereferenced" when possible; the unnamed data stream is updated to reference
 * the original contents and the reparse point is removed.
 *
 * This function returns 0 if the fixup succeeded or was intentionally not
 * executed.  Otherwise it returns an error code.
 */
static noinline_for_stack int
try_to_use_wimboot_hash(HANDLE h, struct wim_inode *inode,
			struct winnt_scan_ctx *ctx)
{
	struct blob_table *blob_table = ctx->params->blob_table;
	struct wim_inode_stream *reparse_strm = NULL;
	struct wim_inode_stream *strm;
	struct blob_descriptor *blob;
	u8 hash[SHA1_HASH_SIZE];
	int ret;

	if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
		struct reparse_buffer_disk rpbuf;
		struct {
			struct wof_external_info wof_info;
			struct wim_provider_rpdata wim_info;
		} *rpdata = (void *)rpbuf.rpdata;
		struct blob_descriptor *reparse_blob;

		/* The file has a WOF reparse point, so WOF must be detached.
		 * We can read the reparse point directly.  */
		ctx->wof_not_attached = true;
		reparse_strm = inode_get_unnamed_stream(inode, STREAM_TYPE_REPARSE_POINT);
		reparse_blob = stream_blob_resolved(reparse_strm);

		if (!reparse_blob || reparse_blob->size < sizeof(*rpdata))
			return 0;  /* Not a WIM-backed file  */

		ret = read_blob_into_buf(reparse_blob, rpdata);
		if (ret)
			return ret;

		if (rpdata->wof_info.version != WOF_CURRENT_VERSION ||
		    rpdata->wof_info.provider != WOF_PROVIDER_WIM ||
		    rpdata->wim_info.version != 2)
			return 0;  /* Not a WIM-backed file  */

		/* Okay, this is a WIM backed file.  Get its SHA-1 hash.  */
		copy_hash(hash, rpdata->wim_info.unnamed_data_stream_hash);
	} else {
		struct {
			struct wof_external_info wof_info;
			struct wim_provider_external_info wim_info;
		} out;
		NTSTATUS status;

		/* WOF may be attached.  Try reading this file's external
		 * backing info.  */
		status = winnt_fsctl(h, FSCTL_GET_EXTERNAL_BACKING,
				     NULL, 0, &out, sizeof(out), NULL);

		/* Is WOF not attached?  */
		if (status == STATUS_INVALID_DEVICE_REQUEST ||
		    status == STATUS_NOT_SUPPORTED) {
			ctx->wof_not_attached = true;
			return 0;
		}

		/* Is this file not externally backed?  */
		if (status == STATUS_OBJECT_NOT_EXTERNALLY_BACKED)
			return 0;

		/* Does this file have an unknown type of external backing that
		 * needed a larger information buffer?  */
		if (status == STATUS_BUFFER_TOO_SMALL)
			return 0;

		/* Was there some other failure?  */
		if (status != STATUS_SUCCESS) {
			winnt_error(status,
				    L"\"%ls\": FSCTL_GET_EXTERNAL_BACKING failed",
				    printable_path(ctx));
			return WIMLIB_ERR_STAT;
		}

		/* Is this file backed by a WIM?  */
		if (out.wof_info.version != WOF_CURRENT_VERSION ||
		    out.wof_info.provider != WOF_PROVIDER_WIM ||
		    out.wim_info.version != WIM_PROVIDER_CURRENT_VERSION)
			return 0;

		/* Okay, this is a WIM backed file.  Get its SHA-1 hash.  */
		copy_hash(hash, out.wim_info.unnamed_data_stream_hash);
	}

	/* If the file's unnamed data stream is nonempty, then fill in its hash
	 * and deduplicate it if possible.
	 *
	 * With WOF detached, we require that the blob *must* de-duplicable for
	 * any action can be taken, since without WOF we can't fall back to
	 * getting the "dereferenced" data by reading the stream (the real
	 * stream is sparse and contains all zeroes).  */
	strm = inode_get_unnamed_data_stream(inode);
	if (strm && (blob = stream_blob_resolved(strm))) {
		struct blob_descriptor **back_ptr;

		if (reparse_strm && !lookup_blob(blob_table, hash))
			return 0;
		back_ptr = retrieve_pointer_to_unhashed_blob(blob);
		copy_hash(blob->hash, hash);
		if (after_blob_hashed(blob, back_ptr, blob_table) != blob)
			free_blob_descriptor(blob);
	}

	/* Remove the reparse point, if present.  */
	if (reparse_strm) {
		inode_remove_stream(inode, reparse_strm, blob_table);
		inode->i_attributes &= ~(FILE_ATTRIBUTE_REPARSE_POINT |
					 FILE_ATTRIBUTE_SPARSE_FILE);
		if (inode->i_attributes == 0)
			inode->i_attributes = FILE_ATTRIBUTE_NORMAL;
	}

	return 0;
}

struct file_info {
	u32 attributes;
	u32 num_links;
	u64 creation_time;
	u64 last_write_time;
	u64 last_access_time;
	u64 ino;
	u64 end_of_file;
	u32 ea_size;
};

static noinline_for_stack NTSTATUS
get_file_info(HANDLE h, struct file_info *info)
{
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;
	FILE_ALL_INFORMATION all_info;

	status = NtQueryInformationFile(h, &iosb, &all_info, sizeof(all_info),
					FileAllInformation);

	if (unlikely(!NT_SUCCESS(status) && status != STATUS_BUFFER_OVERFLOW))
		return status;

	info->attributes = all_info.BasicInformation.FileAttributes;
	info->num_links = all_info.StandardInformation.NumberOfLinks;
	info->creation_time = all_info.BasicInformation.CreationTime.QuadPart;
	info->last_write_time = all_info.BasicInformation.LastWriteTime.QuadPart;
	info->last_access_time = all_info.BasicInformation.LastAccessTime.QuadPart;
	info->ino = all_info.InternalInformation.IndexNumber.QuadPart;
	info->end_of_file = all_info.StandardInformation.EndOfFile.QuadPart;
	info->ea_size = all_info.EaInformation.EaSize;
	return STATUS_SUCCESS;
}

static void
get_volume_information(HANDLE h, struct winnt_scan_ctx *ctx)
{
	u8 _attr_info[sizeof(FILE_FS_ATTRIBUTE_INFORMATION) + 128] _aligned_attribute(8);
	FILE_FS_ATTRIBUTE_INFORMATION *attr_info = (void *)_attr_info;
	FILE_FS_VOLUME_INFORMATION vol_info;
	struct file_info file_info;
	IO_STATUS_BLOCK iosb;
	NTSTATUS status;

	/* Get volume flags  */
	status = NtQueryVolumeInformationFile(h, &iosb, attr_info,
					      sizeof(_attr_info),
					      FileFsAttributeInformation);
	if (NT_SUCCESS(status)) {
		ctx->vol_flags = attr_info->FileSystemAttributes;
		ctx->is_ntfs = (attr_info->FileSystemNameLength == 4 * sizeof(wchar_t)) &&
				!wmemcmp(attr_info->FileSystemName, L"NTFS", 4);
	} else {
		winnt_warning(status, L"\"%ls\": Can't get volume attributes",
			      printable_path(ctx));
	}

	/* Get volume ID.  */
	status = NtQueryVolumeInformationFile(h, &iosb, &vol_info,
					      sizeof(vol_info),
					      FileFsVolumeInformation);
	if ((NT_SUCCESS(status) || status == STATUS_BUFFER_OVERFLOW) &&
	    (iosb.Information >= offsetof(FILE_FS_VOLUME_INFORMATION,
					  VolumeSerialNumber) +
	     sizeof(vol_info.VolumeSerialNumber)))
	{
		ctx->params->capture_root_dev = vol_info.VolumeSerialNumber;
	} else {
		winnt_warning(status, L"\"%ls\": Can't get volume ID",
			      printable_path(ctx));
	}

	/* Get inode number.  */
	status = get_file_info(h, &file_info);
	if (NT_SUCCESS(status)) {
		ctx->params->capture_root_ino = file_info.ino;
	} else {
		winnt_warning(status, L"\"%ls\": Can't get file information",
			      printable_path(ctx));
	}
}

static int
winnt_build_dentry_tree_recursive(struct wim_dentry **root_ret,
				  HANDLE cur_dir,
				  const wchar_t *relative_path,
				  size_t relative_path_nchars,
				  const wchar_t *filename,
				  struct winnt_scan_ctx *ctx)
{
	struct wim_dentry *root = NULL;
	struct wim_inode *inode = NULL;
	HANDLE h = NULL;
	int ret;
	NTSTATUS status;
	struct file_info file_info;
	u64 sort_key;

	ret = try_exclude(ctx->params);
	if (unlikely(ret < 0)) /* Excluded? */
		goto out_progress;
	if (unlikely(ret > 0)) /* Error? */
		goto out;

	/* Open the file with permission to read metadata.  Although we will
	 * later need a handle with FILE_LIST_DIRECTORY permission (or,
	 * equivalently, FILE_READ_DATA; they're the same numeric value) if the
	 * file is a directory, it can significantly slow things down to request
	 * this permission on all nondirectories.  Perhaps it causes Windows to
	 * start prefetching the file contents...  */
	status = winnt_openat(cur_dir, relative_path, relative_path_nchars,
			      FILE_READ_ATTRIBUTES | FILE_READ_EA |
				READ_CONTROL | ACCESS_SYSTEM_SECURITY,
			      &h);
	if (unlikely(!NT_SUCCESS(status))) {
		if (status == STATUS_DELETE_PENDING) {
			WARNING("\"%ls\": Deletion pending; skipping file",
				printable_path(ctx));
			ret = 0;
			goto out;
		}
		if (status == STATUS_SHARING_VIOLATION) {
			ERROR("Can't open \"%ls\":\n"
			      "        File is in use by another process! "
			      "Consider using snapshot (VSS) mode.",
			      printable_path(ctx));
			ret = WIMLIB_ERR_OPEN;
			goto out;
		}
		winnt_error(status, L"\"%ls\": Can't open file",
			    printable_path(ctx));
		if (status == STATUS_FVE_LOCKED_VOLUME)
			ret = WIMLIB_ERR_FVE_LOCKED_VOLUME;
		else
			ret = WIMLIB_ERR_OPEN;
		goto out;
	}

	/* Get information about the file.  */
	status = get_file_info(h, &file_info);
	if (!NT_SUCCESS(status)) {
		winnt_error(status, L"\"%ls\": Can't get file information",
			    printable_path(ctx));
		ret = WIMLIB_ERR_STAT;
		goto out;
	}

	/* Create a WIM dentry with an associated inode, which may be shared.
	 *
	 * However, we need to explicitly check for directories and files with
	 * only 1 link and refuse to hard link them.  This is because Windows
	 * has a bug where it can return duplicate File IDs for files and
	 * directories on the FAT filesystem.
	 *
	 * Since we don't follow mount points on Windows, we don't need to query
	 * the volume ID per-file.  Just once, for the root, is enough.  But we
	 * can't simply pass 0, because then there could be inode collisions
	 * among multiple calls to win32_build_dentry_tree() that are scanning
	 * files on different volumes.  */
	ret = inode_table_new_dentry(ctx->params->inode_table,
				     filename,
				     file_info.ino,
				     ctx->params->capture_root_dev,
				     (file_info.num_links <= 1),
				     &root);
	if (ret)
		goto out;

	/* Get the short (DOS) name of the file.  */
	status = winnt_get_short_name(h, root);

	/* If we can't read the short filename for any reason other than
	 * out-of-memory, just ignore the error and assume the file has no short
	 * name.  This shouldn't be an issue, since the short names are
	 * essentially obsolete anyway.  */
	if (unlikely(status == STATUS_NO_MEMORY)) {
		ret = WIMLIB_ERR_NOMEM;
		goto out;
	}

	inode = root->d_inode;

	if (inode->i_nlink > 1) {
		/* Shared inode (hard link); skip reading per-inode information.
		 */
		goto out_progress;
	}

	inode->i_attributes = file_info.attributes;
	inode->i_creation_time = file_info.creation_time;
	inode->i_last_write_time = file_info.last_write_time;
	inode->i_last_access_time = file_info.last_access_time;

	/* Get the file's security descriptor, unless we are capturing in
	 * NO_ACLS mode or the volume does not support security descriptors.  */
	if (!(ctx->params->add_flags & WIMLIB_ADD_FLAG_NO_ACLS)
	    && (ctx->vol_flags & FILE_PERSISTENT_ACLS))
	{
		ret = winnt_load_security_descriptor(h, inode, ctx);
		if (ret)
			goto out;
	}

	/* Get the file's object ID.  */
	ret = winnt_load_object_id(h, inode, ctx);
	if (ret)
		goto out;

	/* Get the file's extended attributes.  */
	if (unlikely(file_info.ea_size != 0)) {
		ret = winnt_load_xattrs(h, inode, ctx, file_info.ea_size);
		if (ret)
			goto out;
	}

	/* If this is a reparse point, load the reparse data.  */
	if (unlikely(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)) {
		ret = winnt_load_reparse_data(h, inode, ctx);
		if (ret)
			goto out;
	}

	sort_key = get_sort_key(h);

	if (unlikely(inode->i_attributes & FILE_ATTRIBUTE_ENCRYPTED)) {
		/* Load information about the raw encrypted data.  This is
		 * needed for any directory or non-directory that has
		 * FILE_ATTRIBUTE_ENCRYPTED set.
		 *
		 * Note: since OpenEncryptedFileRaw() fails with
		 * ERROR_SHARING_VIOLATION if there are any open handles to the
		 * file, we have to close the file and re-open it later if
		 * needed.  */
		NtClose(h);
		h = NULL;
		ret = winnt_scan_efsrpc_raw_data(inode, ctx);
		if (ret)
			goto out;
	} else {
		/*
		 * Load information about data streams (unnamed and named).
		 *
		 * Skip this step for encrypted files, since the data from
		 * ReadEncryptedFileRaw() already contains all data streams (and
		 * they do in fact all get restored by WriteEncryptedFileRaw().)
		 *
		 * Note: WIMGAPI (as of Windows 8.1) gets wrong and stores both
		 * the EFSRPC data and the named data stream(s)...!
		 */
		ret = winnt_scan_data_streams(h,
					      inode,
					      file_info.end_of_file,
					      ctx);
		if (ret)
			goto out;
	}

	if (unlikely(should_try_to_use_wimboot_hash(inode, ctx))) {
		ret = try_to_use_wimboot_hash(h, inode, ctx);
		if (ret)
			goto out;
	}

	set_sort_key(inode, sort_key);

	if (inode_is_directory(inode)) {

		/* Directory: recurse to children.  */

		/* Re-open the directory with FILE_LIST_DIRECTORY access.  */
		if (h) {
			NtClose(h);
			h = NULL;
		}
		status = winnt_openat(cur_dir, relative_path,
				      relative_path_nchars, FILE_LIST_DIRECTORY,
				      &h);
		if (!NT_SUCCESS(status)) {
			winnt_error(status, L"\"%ls\": Can't open directory",
				    printable_path(ctx));
			ret = WIMLIB_ERR_OPEN;
			goto out;
		}
		ret = winnt_recurse_directory(h, root, ctx);
		if (ret)
			goto out;
	}

out_progress:
	if (likely(root))
		ret = do_scan_progress(ctx->params, WIMLIB_SCAN_DENTRY_OK, inode);
	else
		ret = do_scan_progress(ctx->params, WIMLIB_SCAN_DENTRY_EXCLUDED, NULL);
out:
	if (likely(h))
		NtClose(h);
	if (unlikely(ret)) {
		free_dentry_tree(root, ctx->params->blob_table);
		root = NULL;
		ret = report_scan_error(ctx->params, ret);
	}
	*root_ret = root;
	return ret;
}

static void
winnt_do_scan_warnings(const wchar_t *path, const struct winnt_scan_ctx *ctx)
{
	if (likely(ctx->num_get_sacl_priv_notheld == 0 &&
		   ctx->num_get_sd_access_denied == 0))
		return;

	WARNING("Scan of \"%ls\" complete, but with one or more warnings:", path);
	if (ctx->num_get_sacl_priv_notheld != 0) {
		WARNING("- Could not capture SACL (System Access Control List)\n"
			"            on %lu files or directories.",
			ctx->num_get_sacl_priv_notheld);
	}
	if (ctx->num_get_sd_access_denied != 0) {
		WARNING("- Could not capture security descriptor at all\n"
			"            on %lu files or directories.",
			ctx->num_get_sd_access_denied);
	}
	WARNING("To fully capture all security descriptors, run the program\n"
		"          with Administrator rights.");
}

/*----------------------------------------------------------------------------*
 *                         Fast MFT scan implementation                       *
 *----------------------------------------------------------------------------*/

#define ENABLE_FAST_MFT_SCAN	1

#ifdef ENABLE_FAST_MFT_SCAN

typedef struct {
	u64 StartingCluster;
	u64 ClusterCount;
} CLUSTER_RANGE;

typedef struct {
	u64 StartingFileReferenceNumber;
	u64 EndingFileReferenceNumber;
} FILE_REFERENCE_RANGE;

/* The FSCTL_QUERY_FILE_LAYOUT ioctl.  This ioctl can be used on Windows 8 and
 * later to scan the MFT of an NTFS volume.  */
#define FSCTL_QUERY_FILE_LAYOUT		CTL_CODE(FILE_DEVICE_FILE_SYSTEM, 157, METHOD_NEITHER, FILE_ANY_ACCESS)

/* The input to FSCTL_QUERY_FILE_LAYOUT  */
typedef struct {
	u32 NumberOfPairs;
#define QUERY_FILE_LAYOUT_RESTART					0x00000001
#define QUERY_FILE_LAYOUT_INCLUDE_NAMES					0x00000002
#define QUERY_FILE_LAYOUT_INCLUDE_STREAMS				0x00000004
#define QUERY_FILE_LAYOUT_INCLUDE_EXTENTS				0x00000008
#define QUERY_FILE_LAYOUT_INCLUDE_EXTRA_INFO				0x00000010
#define QUERY_FILE_LAYOUT_INCLUDE_STREAMS_WITH_NO_CLUSTERS_ALLOCATED	0x00000020
	u32 Flags;
#define QUERY_FILE_LAYOUT_FILTER_TYPE_NONE		0
#define QUERY_FILE_LAYOUT_FILTER_TYPE_CLUSTERS		1
#define QUERY_FILE_LAYOUT_FILTER_TYPE_FILEID		2
#define QUERY_FILE_LAYOUT_NUM_FILTER_TYPES		3
	u32 FilterType;
	u32 Reserved;
	union {
		CLUSTER_RANGE ClusterRanges[1];
		FILE_REFERENCE_RANGE FileReferenceRanges[1];
	} Filter;
} QUERY_FILE_LAYOUT_INPUT;

/* The header of the buffer returned by FSCTL_QUERY_FILE_LAYOUT  */
typedef struct {
	u32 FileEntryCount;
	u32 FirstFileOffset;
#define QUERY_FILE_LAYOUT_SINGLE_INSTANCED				0x00000001
	u32 Flags;
	u32 Reserved;
} QUERY_FILE_LAYOUT_OUTPUT;

/* Inode information returned by FSCTL_QUERY_FILE_LAYOUT  */
typedef struct {
	u32 Version;
	u32 NextFileOffset;
	u32 Flags;
	u32 FileAttributes;
	u64 FileReferenceNumber;
	u32 FirstNameOffset;
	u32 FirstStreamOffset;
	u32 ExtraInfoOffset;
	u32 Reserved;
} FILE_LAYOUT_ENTRY;

/* Extra inode information returned by FSCTL_QUERY_FILE_LAYOUT  */
typedef struct {
	struct {
		u64 CreationTime;
		u64 LastAccessTime;
		u64 LastWriteTime;
		u64 ChangeTime;
		u32 FileAttributes;
	} BasicInformation;
	u32 OwnerId;
	u32 SecurityId;
	s64 Usn;
} FILE_LAYOUT_INFO_ENTRY;

/* Filename (or dentry) information returned by FSCTL_QUERY_FILE_LAYOUT  */
typedef struct {
	u32 NextNameOffset;
#define FILE_LAYOUT_NAME_ENTRY_PRIMARY	0x00000001
#define FILE_LAYOUT_NAME_ENTRY_DOS	0x00000002
	u32 Flags;
	u64 ParentFileReferenceNumber;
	u32 FileNameLength;
	u32 Reserved;
	wchar_t FileName[1];
} FILE_LAYOUT_NAME_ENTRY;

/* Stream information returned by FSCTL_QUERY_FILE_LAYOUT  */
typedef struct {
	u32 Version;
	u32 NextStreamOffset;
#define STREAM_LAYOUT_ENTRY_IMMOVABLE			0x00000001
#define STREAM_LAYOUT_ENTRY_PINNED			0x00000002
#define STREAM_LAYOUT_ENTRY_RESIDENT			0x00000004
#define STREAM_LAYOUT_ENTRY_NO_CLUSTERS_ALLOCATED	0x00000008
	u32 Flags;
	u32 ExtentInformationOffset;
	u64 AllocationSize;
	u64 EndOfFile;
	u64 Reserved;
	u32 AttributeFlags;
	u32 StreamIdentifierLength;
	wchar_t StreamIdentifier[1];
} STREAM_LAYOUT_ENTRY;


typedef struct {
#define STREAM_EXTENT_ENTRY_AS_RETRIEVAL_POINTERS	0x00000001
#define STREAM_EXTENT_ENTRY_ALL_EXTENTS			0x00000002
	u32 Flags;
	union {
		RETRIEVAL_POINTERS_BUFFER RetrievalPointers;
	} ExtentInformation;
} STREAM_EXTENT_ENTRY;

/* Extract the MFT number part of the full inode number  */
#define NTFS_MFT_NO(ref)	((ref) & (((u64)1 << 48) - 1))

/* Is the file the root directory of the NTFS volume?  The root directory always
 * occupies MFT record 5.  */
#define NTFS_IS_ROOT_FILE(ino)	(NTFS_MFT_NO(ino) == 5)

/* Is the file a special NTFS file, other than the root directory?  The special
 * files are the first 16 records in the MFT.  */
#define NTFS_IS_SPECIAL_FILE(ino)			\
	(NTFS_MFT_NO(ino) <= 15 && !NTFS_IS_ROOT_FILE(ino))

#define NTFS_SPECIAL_STREAM_OBJECT_ID		0x00000001
#define NTFS_SPECIAL_STREAM_EA			0x00000002
#define NTFS_SPECIAL_STREAM_EA_INFORMATION	0x00000004

/* Intermediate inode structure.  This is used to temporarily save information
 * from FSCTL_QUERY_FILE_LAYOUT before creating the full 'struct wim_inode'.  */
struct ntfs_inode {
	struct avl_tree_node index_node;
	u64 ino;
	u64 creation_time;
	u64 last_access_time;
	u64 last_write_time;
	u64 starting_lcn;
	u32 attributes;
	u32 security_id;
	u32 num_aliases;
	u32 num_streams;
	u32 special_streams;
	u32 first_stream_offset;
	struct ntfs_dentry *first_child;
	wchar_t short_name[13];
};

/* Intermediate dentry structure.  This is used to temporarily save information
 * from FSCTL_QUERY_FILE_LAYOUT before creating the full 'struct wim_dentry'. */
struct ntfs_dentry {
	u32 offset_from_inode : 31;
	u32 is_primary : 1;
	union {
		/* Note: build_children_lists() replaces 'parent_ino' with
		 * 'next_child'.  */
		u64 parent_ino;
		struct ntfs_dentry *next_child;
	};
	wchar_t name[0];
};

/* Intermediate stream structure.  This is used to temporarily save information
 * from FSCTL_QUERY_FILE_LAYOUT before creating the full 'struct
 * wim_inode_stream'.  */
struct ntfs_stream {
	u64 size;
	wchar_t name[0];
};

/* Map of all known NTFS inodes, keyed by inode number  */
struct ntfs_inode_map {
	struct avl_tree_node *root;
};

#define NTFS_INODE(node)				\
	avl_tree_entry((node), struct ntfs_inode, index_node)

#define SKIP_ALIGNED(p, size)	((void *)(p) + ALIGN((size), 8))

/* Get a pointer to the first dentry of the inode.  */
#define FIRST_DENTRY(ni) SKIP_ALIGNED((ni), sizeof(struct ntfs_inode))

/* Get a pointer to the first stream of the inode.  */
#define FIRST_STREAM(ni) ((const void *)ni + ni->first_stream_offset)

/* Advance to the next dentry of the inode.  */
#define NEXT_DENTRY(nd)	 SKIP_ALIGNED((nd), sizeof(struct ntfs_dentry) +   \
				(wcslen((nd)->name) + 1) * sizeof(wchar_t))

/* Advance to the next stream of the inode.  */
#define NEXT_STREAM(ns)	 SKIP_ALIGNED((ns), sizeof(struct ntfs_stream) +   \
				(wcslen((ns)->name) + 1) * sizeof(wchar_t))

static int
_avl_cmp_ntfs_inodes(const struct avl_tree_node *node1,
		     const struct avl_tree_node *node2)
{
	return cmp_u64(NTFS_INODE(node1)->ino, NTFS_INODE(node2)->ino);
}

/* Adds an NTFS inode to the map.  */
static void
ntfs_inode_map_add_inode(struct ntfs_inode_map *map, struct ntfs_inode *ni)
{
	if (avl_tree_insert(&map->root, &ni->index_node, _avl_cmp_ntfs_inodes)) {
		WARNING("Inode 0x%016"PRIx64" is a duplicate!", ni->ino);
		FREE(ni);
	}
}

/* Find an ntfs_inode in the map by inode number.  Returns NULL if not found. */
static struct ntfs_inode *
ntfs_inode_map_lookup(struct ntfs_inode_map *map, u64 ino)
{
	struct ntfs_inode tmp;
	struct avl_tree_node *res;

	tmp.ino = ino;
	res = avl_tree_lookup_node(map->root, &tmp.index_node, _avl_cmp_ntfs_inodes);
	if (!res)
		return NULL;
	return NTFS_INODE(res);
}

/* Remove an ntfs_inode from the map and free it.  */
static void
ntfs_inode_map_remove(struct ntfs_inode_map *map, struct ntfs_inode *ni)
{
	avl_tree_remove(&map->root, &ni->index_node);
	FREE(ni);
}

/* Free all ntfs_inodes in the map.  */
static void
ntfs_inode_map_destroy(struct ntfs_inode_map *map)
{
	struct ntfs_inode *ni;

	avl_tree_for_each_in_postorder(ni, map->root, struct ntfs_inode, index_node)
		FREE(ni);
}

static bool
file_has_streams(const FILE_LAYOUT_ENTRY *file)
{
	return (file->FirstStreamOffset != 0) &&
		!(file->FileAttributes & FILE_ATTRIBUTE_ENCRYPTED);
}

static bool
is_valid_name_entry(const FILE_LAYOUT_NAME_ENTRY *name)
{
	return name->FileNameLength > 0 &&
		name->FileNameLength % 2 == 0 &&
		!wmemchr(name->FileName, L'\0', name->FileNameLength / 2) &&
		(!(name->Flags & FILE_LAYOUT_NAME_ENTRY_DOS) ||
		 name->FileNameLength <= 24);
}

/* Validate the FILE_LAYOUT_NAME_ENTRYs of the specified file and compute the
 * total length in bytes of the ntfs_dentry structures needed to hold the name
 * information.  */
static int
validate_names_and_compute_total_length(const FILE_LAYOUT_ENTRY *file,
					size_t *total_length_ret)
{
	const FILE_LAYOUT_NAME_ENTRY *name =
		(const void *)file + file->FirstNameOffset;
	size_t total = 0;
	size_t num_long_names = 0;

	for (;;) {
		if (unlikely(!is_valid_name_entry(name))) {
			ERROR("Invalid FILE_LAYOUT_NAME_ENTRY! "
			      "FileReferenceNumber=0x%016"PRIx64", "
			      "FileNameLength=%"PRIu32", "
			      "FileName=%.*ls, Flags=0x%08"PRIx32,
			      file->FileReferenceNumber,
			      name->FileNameLength,
			      (int)(name->FileNameLength / 2),
			      name->FileName, name->Flags);
			return WIMLIB_ERR_UNSUPPORTED;
		}
		if (name->Flags != FILE_LAYOUT_NAME_ENTRY_DOS) {
			num_long_names++;
			total += ALIGN(sizeof(struct ntfs_dentry) +
				       name->FileNameLength + sizeof(wchar_t),
				       8);
		}
		if (name->NextNameOffset == 0)
			break;
		name = (const void *)name + name->NextNameOffset;
	}

	if (unlikely(num_long_names == 0)) {
		ERROR("Inode 0x%016"PRIx64" has no long names!",
		      file->FileReferenceNumber);
		return WIMLIB_ERR_UNSUPPORTED;
	}

	*total_length_ret = total;
	return 0;
}

static bool
is_valid_stream_entry(const STREAM_LAYOUT_ENTRY *stream)
{
	return stream->StreamIdentifierLength % 2 == 0 &&
		!wmemchr(stream->StreamIdentifier , L'\0',
			 stream->StreamIdentifierLength / 2);
}

/* assumes that 'id' is a wide string literal */
#define stream_has_identifier(stream, id)				\
	((stream)->StreamIdentifierLength == sizeof(id) - 2 &&		\
	 !memcmp((stream)->StreamIdentifier, id, sizeof(id) - 2))
/*
 * If the specified STREAM_LAYOUT_ENTRY represents a DATA stream as opposed to
 * some other type of NTFS stream such as a STANDARD_INFORMATION stream, return
 * true and set *stream_name_ret and *stream_name_nchars_ret to specify just the
 * stream name.  For example, ":foo:$DATA" would become "foo" with length 3
 * characters.  Otherwise return false.
 */
static bool
use_stream(const FILE_LAYOUT_ENTRY *file, const STREAM_LAYOUT_ENTRY *stream,
	   const wchar_t **stream_name_ret, size_t *stream_name_nchars_ret)
{
	const wchar_t *stream_name;
	size_t stream_name_nchars;

	if (stream->StreamIdentifierLength == 0) {
		/* The unnamed data stream may be given as an empty string
		 * rather than as "::$DATA".  Handle it both ways.  */
		stream_name = L"";
		stream_name_nchars = 0;
	} else if (!get_data_stream_name(stream->StreamIdentifier,
					 stream->StreamIdentifierLength / 2,
					 &stream_name, &stream_name_nchars))
		return false;

	/* Skip the unnamed data stream for directories.  */
	if (stream_name_nchars == 0 &&
	    (file->FileAttributes & FILE_ATTRIBUTE_DIRECTORY))
		return false;

	*stream_name_ret = stream_name;
	*stream_name_nchars_ret = stream_name_nchars;
	return true;
}

/* Validate the STREAM_LAYOUT_ENTRYs of the specified file and compute the total
 * length in bytes of the ntfs_stream structures needed to hold the stream
 * information.  In addition, set *special_streams_ret to a bitmask of special
 * stream types that were found.  */
static int
validate_streams_and_compute_total_length(const FILE_LAYOUT_ENTRY *file,
					  size_t *total_length_ret,
					  u32 *special_streams_ret)
{
	const STREAM_LAYOUT_ENTRY *stream =
		(const void *)file + file->FirstStreamOffset;
	size_t total = 0;
	u32 special_streams = 0;

	for (;;) {
		const wchar_t *name;
		size_t name_nchars;

		if (unlikely(!is_valid_stream_entry(stream))) {
			WARNING("Invalid STREAM_LAYOUT_ENTRY! "
				"FileReferenceNumber=0x%016"PRIx64", "
				"StreamIdentifierLength=%"PRIu32", "
				"StreamIdentifier=%.*ls",
				file->FileReferenceNumber,
				stream->StreamIdentifierLength,
				(int)(stream->StreamIdentifierLength / 2),
				stream->StreamIdentifier);
			return WIMLIB_ERR_UNSUPPORTED;
		}

		if (use_stream(file, stream, &name, &name_nchars)) {
			total += ALIGN(sizeof(struct ntfs_stream) +
				       (name_nchars + 1) * sizeof(wchar_t), 8);
		} else if (stream_has_identifier(stream, L"::$OBJECT_ID")) {
			special_streams |= NTFS_SPECIAL_STREAM_OBJECT_ID;
		} else if (stream_has_identifier(stream, L"::$EA")) {
			special_streams |= NTFS_SPECIAL_STREAM_EA;
		} else if (stream_has_identifier(stream, L"::$EA_INFORMATION")) {
			special_streams |= NTFS_SPECIAL_STREAM_EA_INFORMATION;
		}
		if (stream->NextStreamOffset == 0)
			break;
		stream = (const void *)stream + stream->NextStreamOffset;
	}

	*total_length_ret = total;
	*special_streams_ret = special_streams;
	return 0;
}

static void *
load_name_information(const FILE_LAYOUT_ENTRY *file, struct ntfs_inode *ni,
		      void *p)
{
	const FILE_LAYOUT_NAME_ENTRY *name =
		(const void *)file + file->FirstNameOffset;
	for (;;) {
		struct ntfs_dentry *nd = p;
		/* Note that a name may be just a short (DOS) name, just a long
		 * name, or both a short name and a long name.  If there is a
		 * short name, one name should also be marked as "primary" to
		 * indicate which long name the short name is associated with.
		 * Also, there should be at most one short name per inode.  */
		if (name->Flags & FILE_LAYOUT_NAME_ENTRY_DOS) {
			memcpy(ni->short_name,
			       name->FileName, name->FileNameLength);
			ni->short_name[name->FileNameLength / 2] = L'\0';
		}
		if (name->Flags != FILE_LAYOUT_NAME_ENTRY_DOS) {
			ni->num_aliases++;
			nd->offset_from_inode = (u8 *)nd - (u8 *)ni;
			nd->is_primary = ((name->Flags &
					   FILE_LAYOUT_NAME_ENTRY_PRIMARY) != 0);
			nd->parent_ino = name->ParentFileReferenceNumber;
			memcpy(nd->name, name->FileName, name->FileNameLength);
			nd->name[name->FileNameLength / 2] = L'\0';
			p += ALIGN(sizeof(struct ntfs_dentry) +
				   name->FileNameLength + sizeof(wchar_t), 8);
		}
		if (name->NextNameOffset == 0)
			break;
		name = (const void *)name + name->NextNameOffset;
	}
	return p;
}

static u64
load_starting_lcn(const STREAM_LAYOUT_ENTRY *stream)
{
	const STREAM_EXTENT_ENTRY *entry;

	if (stream->ExtentInformationOffset == 0)
		return 0;

	entry = (const void *)stream + stream->ExtentInformationOffset;

	if (!(entry->Flags & STREAM_EXTENT_ENTRY_AS_RETRIEVAL_POINTERS))
		return 0;

	return extract_starting_lcn(&entry->ExtentInformation.RetrievalPointers);
}

static void *
load_stream_information(const FILE_LAYOUT_ENTRY *file, struct ntfs_inode *ni,
			void *p)
{
	const STREAM_LAYOUT_ENTRY *stream =
		(const void *)file + file->FirstStreamOffset;
	const u32 first_stream_offset = (const u8 *)p - (const u8 *)ni;
	for (;;) {
		struct ntfs_stream *ns = p;
		const wchar_t *name;
		size_t name_nchars;

		if (use_stream(file, stream, &name, &name_nchars)) {
			ni->first_stream_offset = first_stream_offset;
			ni->num_streams++;
			if (name_nchars == 0)
				ni->starting_lcn = load_starting_lcn(stream);
			ns->size = stream->EndOfFile;
			wmemcpy(ns->name, name, name_nchars);
			ns->name[name_nchars] = L'\0';
			p += ALIGN(sizeof(struct ntfs_stream) +
				   (name_nchars + 1) * sizeof(wchar_t), 8);
		}
		if (stream->NextStreamOffset == 0)
			break;
		stream = (const void *)stream + stream->NextStreamOffset;
	}
	return p;
}

/* Process the information for a file given by FSCTL_QUERY_FILE_LAYOUT.  */
static int
load_one_file(const FILE_LAYOUT_ENTRY *file, struct ntfs_inode_map *inode_map)
{
	const FILE_LAYOUT_INFO_ENTRY *info =
		(const void *)file + file->ExtraInfoOffset;
	size_t inode_size;
	struct ntfs_inode *ni;
	size_t n;
	int ret;
	void *p;
	u32 special_streams = 0;

	inode_size = ALIGN(sizeof(struct ntfs_inode), 8);

	/* The root file should have no names, and all other files should have
	 * at least one name.  But just in case, we ignore the names of the root
	 * file, and we ignore any non-root file with no names.  */
	if (!NTFS_IS_ROOT_FILE(file->FileReferenceNumber)) {
		if (file->FirstNameOffset == 0)
			return 0;
		ret = validate_names_and_compute_total_length(file, &n);
		if (ret)
			return ret;
		inode_size += n;
	}

	if (file_has_streams(file)) {
		ret = validate_streams_and_compute_total_length(file, &n,
								&special_streams);
		if (ret)
			return ret;
		inode_size += n;
	}

	/* To save memory, we allocate the ntfs_dentry's and ntfs_stream's in
	 * the same memory block as their ntfs_inode.  */
	ni = CALLOC(1, inode_size);
	if (!ni)
		return WIMLIB_ERR_NOMEM;

	ni->ino = file->FileReferenceNumber;
	ni->attributes = info->BasicInformation.FileAttributes;
	ni->creation_time = info->BasicInformation.CreationTime;
	ni->last_write_time = info->BasicInformation.LastWriteTime;
	ni->last_access_time = info->BasicInformation.LastAccessTime;
	ni->security_id = info->SecurityId;
	ni->special_streams = special_streams;

	p = FIRST_DENTRY(ni);

	if (!NTFS_IS_ROOT_FILE(file->FileReferenceNumber))
		p = load_name_information(file, ni, p);

	if (file_has_streams(file))
		p = load_stream_information(file, ni, p);

	wimlib_assert((u8 *)p - (u8 *)ni == inode_size);

	ntfs_inode_map_add_inode(inode_map, ni);
	return 0;
}

/*
 * Quickly find all files on an NTFS volume by using FSCTL_QUERY_FILE_LAYOUT to
 * scan the MFT.  The NTFS volume is specified by the NT namespace path @path.
 * For each file, allocate an 'ntfs_inode' structure for each file and add it to
 * 'inode_map' keyed by inode number.  Include NTFS special files such as
 * $Bitmap (they will be removed later).
 */
static int
load_files_from_mft(const wchar_t *path, struct ntfs_inode_map *inode_map)
{
	HANDLE h = NULL;
	QUERY_FILE_LAYOUT_INPUT in = (QUERY_FILE_LAYOUT_INPUT) {
		.NumberOfPairs = 0,
		.Flags = QUERY_FILE_LAYOUT_RESTART |
			 QUERY_FILE_LAYOUT_INCLUDE_NAMES |
			 QUERY_FILE_LAYOUT_INCLUDE_STREAMS |
			 QUERY_FILE_LAYOUT_INCLUDE_EXTENTS |
			 QUERY_FILE_LAYOUT_INCLUDE_EXTRA_INFO |
			 QUERY_FILE_LAYOUT_INCLUDE_STREAMS_WITH_NO_CLUSTERS_ALLOCATED,
		.FilterType = QUERY_FILE_LAYOUT_FILTER_TYPE_NONE,
	};
	size_t outsize = 32768;
	QUERY_FILE_LAYOUT_OUTPUT *out = NULL;
	int ret;
	NTSTATUS status;

	status = winnt_open(path, wcslen(path),
			    FILE_READ_DATA | FILE_READ_ATTRIBUTES, &h);
	if (!NT_SUCCESS(status)) {
		ret = -1; /* Silently try standard recursive scan instead  */
		goto out;
	}

	for (;;) {
		/* Allocate a buffer for the output of the ioctl.  */
		out = MALLOC(outsize);
		if (!out) {
			ret = WIMLIB_ERR_NOMEM;
			goto out;
		}

		/* Execute FSCTL_QUERY_FILE_LAYOUT until it fails.  */
		while (NT_SUCCESS(status = winnt_fsctl(h,
						       FSCTL_QUERY_FILE_LAYOUT,
						       &in, sizeof(in),
						       out, outsize, NULL)))
		{
			const FILE_LAYOUT_ENTRY *file =
				(const void *)out + out->FirstFileOffset;
			for (;;) {
				ret = load_one_file(file, inode_map);
				if (ret)
					goto out;
				if (file->NextFileOffset == 0)
					break;
				file = (const void *)file + file->NextFileOffset;
			}
			in.Flags &= ~QUERY_FILE_LAYOUT_RESTART;
		}

		/* Enlarge the buffer if needed.  */
		if (status != STATUS_BUFFER_TOO_SMALL)
			break;
		FREE(out);
		outsize *= 2;
	}

	/* Normally, FSCTL_QUERY_FILE_LAYOUT fails with STATUS_END_OF_FILE after
	 * all files have been enumerated.  */
	if (status != STATUS_END_OF_FILE) {
		if (status == STATUS_INVALID_DEVICE_REQUEST /* old OS */ ||
		    status == STATUS_NOT_SUPPORTED /* Samba volume, WinXP */ ||
		    status == STATUS_INVALID_PARAMETER /* not root directory */ )
		{
			/* Silently try standard recursive scan instead  */
			ret = -1;
		} else {
			winnt_error(status,
				    L"Error enumerating files on volume \"%ls\"",
				    path);
			/* Try standard recursive scan instead  */
			ret = WIMLIB_ERR_UNSUPPORTED;
		}
		goto out;
	}
	ret = 0;
out:
	FREE(out);
	NtClose(h);
	return ret;
}

/* Build the list of child dentries for each inode in @map.  This is done by
 * iterating through each name of each inode and adding it to its parent's
 * children list.  Note that every name should have a parent, i.e. should belong
 * to some directory.  The root directory does not have any names.  */
static int
build_children_lists(struct ntfs_inode_map *map, struct ntfs_inode **root_ret)
{
	struct ntfs_inode *ni;

	avl_tree_for_each_in_order(ni, map->root, struct ntfs_inode, index_node)
	{
		struct ntfs_dentry *nd;
		u32 n;

		if (NTFS_IS_ROOT_FILE(ni->ino)) {
			*root_ret = ni;
			continue;
		}

		n = ni->num_aliases;
		nd = FIRST_DENTRY(ni);
		for (;;) {
			struct ntfs_inode *parent;

			parent = ntfs_inode_map_lookup(map, nd->parent_ino);
			if (unlikely(!parent)) {
				ERROR("Parent inode 0x%016"PRIx64" of"
				      "directory entry \"%ls\" (inode "
				      "0x%016"PRIx64") was missing from the "
				      "MFT listing!",
				      nd->parent_ino, nd->name, ni->ino);
				return WIMLIB_ERR_UNSUPPORTED;
			}
			nd->next_child = parent->first_child;
			parent->first_child = nd;
			if (!--n)
				break;
			nd = NEXT_DENTRY(nd);
		}
	}
	return 0;
}

struct security_map_node {
	struct avl_tree_node index_node;
	u32 disk_security_id;
	u32 wim_security_id;
};

/* Map from disk security IDs to WIM security IDs  */
struct security_map {
	struct avl_tree_node *root;
};

#define SECURITY_MAP_NODE(node)				\
	avl_tree_entry((node), struct security_map_node, index_node)

static int
_avl_cmp_security_map_nodes(const struct avl_tree_node *node1,
			    const struct avl_tree_node *node2)
{
	return cmp_u32(SECURITY_MAP_NODE(node1)->disk_security_id,
		       SECURITY_MAP_NODE(node2)->disk_security_id);
}

static s32
security_map_lookup(struct security_map *map, u32 disk_security_id)
{
	struct security_map_node tmp;
	const struct avl_tree_node *res;

	if (disk_security_id == 0)  /* No on-disk security ID; uncacheable  */
		return -1;

	tmp.disk_security_id = disk_security_id;
	res = avl_tree_lookup_node(map->root, &tmp.index_node,
				   _avl_cmp_security_map_nodes);
	if (!res)
		return -1;
	return SECURITY_MAP_NODE(res)->wim_security_id;
}

static int
security_map_insert(struct security_map *map, u32 disk_security_id,
		    u32 wim_security_id)
{
	struct security_map_node *node;

	if (disk_security_id == 0)  /* No on-disk security ID; uncacheable  */
		return 0;

	node = MALLOC(sizeof(*node));
	if (!node)
		return WIMLIB_ERR_NOMEM;

	node->disk_security_id = disk_security_id;
	node->wim_security_id = wim_security_id;
	avl_tree_insert(&map->root, &node->index_node,
			_avl_cmp_security_map_nodes);
	return 0;
}

static void
security_map_destroy(struct security_map *map)
{
	struct security_map_node *node;

	avl_tree_for_each_in_postorder(node, map->root,
				       struct security_map_node, index_node)
		FREE(node);
}

/*
 * Turn our temporary NTFS structures into the final WIM structures:
 *
 *	ntfs_inode	=> wim_inode
 *	ntfs_dentry	=> wim_dentry
 *	ntfs_stream	=> wim_inode_stream
 *
 * This also handles things such as exclusions and issuing progress messages.
 * It's similar to winnt_build_dentry_tree_recursive(), but this is much faster
 * because almost all information we need is already loaded in memory in the
 * ntfs_* structures.  However, in some cases we still fall back to
 * winnt_build_dentry_tree_recursive() and/or opening the file.
 */
static int
generate_wim_structures_recursive(struct wim_dentry **root_ret,
				  const wchar_t *filename, bool is_primary_name,
				  struct ntfs_inode *ni,
				  struct winnt_scan_ctx *ctx,
				  struct ntfs_inode_map *inode_map,
				  struct security_map *security_map)
{
	int ret = 0;
	struct wim_dentry *root = NULL;
	struct wim_inode *inode = NULL;
	const struct ntfs_stream *ns;

	/* Completely ignore NTFS special files.  */
	if (NTFS_IS_SPECIAL_FILE(ni->ino))
		goto out;

	/* Fall back to a recursive scan for unhandled cases.  Reparse points,
	 * in particular, can't be properly handled here because a commonly used
	 * filter driver (WOF) hides reparse points from regular filesystem APIs
	 * but not from FSCTL_QUERY_FILE_LAYOUT.  */
	if (ni->attributes & (FILE_ATTRIBUTE_REPARSE_POINT |
			      FILE_ATTRIBUTE_ENCRYPTED) ||
	    ni->special_streams != 0)
	{
		ret = winnt_build_dentry_tree_recursive(&root,
							NULL,
							ctx->params->cur_path,
							ctx->params->cur_path_nchars,
							filename,
							ctx);
		goto out;
	}

	/* Test for exclusion based on path.  */
	ret = try_exclude(ctx->params);
	if (unlikely(ret < 0)) /* Excluded? */
		goto out_progress;
	if (unlikely(ret > 0)) /* Error? */
		goto out;

	/* Create the WIM dentry and possibly a new WIM inode  */
	ret = inode_table_new_dentry(ctx->params->inode_table, filename,
				     ni->ino, ctx->params->capture_root_dev,
				     false, &root);
	if (ret)
		goto out;

	inode = root->d_inode;

	/* Set the short name if needed.  */
	if (is_primary_name && *ni->short_name) {
		size_t nbytes = wcslen(ni->short_name) * sizeof(wchar_t);
		root->d_short_name = memdup(ni->short_name,
					    nbytes + sizeof(wchar_t));
		if (!root->d_short_name) {
			ret = WIMLIB_ERR_NOMEM;
			goto out;
		}
		root->d_short_name_nbytes = nbytes;
	}

	if (inode->i_nlink > 1) { /* Already seen this inode?  */
		ret = 0;
		goto out_progress;
	}

	/* The file attributes and timestamps were cached from the MFT.  */
	inode->i_attributes = ni->attributes;
	inode->i_creation_time = ni->creation_time;
	inode->i_last_write_time = ni->last_write_time;
	inode->i_last_access_time = ni->last_access_time;

	/* Set the security descriptor if needed.  */
	if (!(ctx->params->add_flags & WIMLIB_ADD_FLAG_NO_ACLS)) {
		/* Look up the WIM security ID that corresponds to the on-disk
		 * security ID.  */
		s32 wim_security_id =
			security_map_lookup(security_map, ni->security_id);
		if (likely(wim_security_id >= 0)) {
			/* The mapping for this security ID is already cached.*/
			inode->i_security_id = wim_security_id;
		} else {
			HANDLE h;
			NTSTATUS status;

			/* Create a mapping for this security ID and insert it
			 * into the security map.  */

			status = winnt_open(ctx->params->cur_path,
					    ctx->params->cur_path_nchars,
					    READ_CONTROL |
						ACCESS_SYSTEM_SECURITY, &h);
			if (!NT_SUCCESS(status)) {
				winnt_error(status, L"Can't open \"%ls\" to "
					    "read security descriptor",
					    printable_path(ctx));
				ret = WIMLIB_ERR_OPEN;
				goto out;
			}
			ret = winnt_load_security_descriptor(h, inode, ctx);
			NtClose(h);
			if (ret)
				goto out;

			ret = security_map_insert(security_map, ni->security_id,
						  inode->i_security_id);
			if (ret)
				goto out;
		}
	}

	/* Add data streams based on the cached information from the MFT.  */
	ns = FIRST_STREAM(ni);
	for (u32 i = 0; i < ni->num_streams; i++) {
		struct windows_file *windows_file;

		/* Reference the stream by path if it's a named data stream, or
		 * if the volume doesn't support "open by file ID", or if the
		 * application hasn't explicitly opted in to "open by file ID".
		 * Otherwise, only save the inode number (file ID).  */
		if (*ns->name ||
		    !(ctx->vol_flags & FILE_SUPPORTS_OPEN_BY_FILE_ID) ||
		    !(ctx->params->add_flags & WIMLIB_ADD_FLAG_FILE_PATHS_UNNEEDED))
		{
			windows_file = alloc_windows_file(ctx->params->cur_path,
							  ctx->params->cur_path_nchars,
							  ns->name,
							  wcslen(ns->name),
							  ctx->snapshot,
							  false);
		} else {
			windows_file = alloc_windows_file_for_file_id(ni->ino,
								      ctx->params->cur_path,
								      ctx->params->root_path_nchars,
								      ctx->snapshot);
		}

		ret = add_stream(inode, windows_file, ns->size,
				 STREAM_TYPE_DATA, ns->name,
				 ctx->params->unhashed_blobs);
		if (ret)
			goto out;
		ns = NEXT_STREAM(ns);
	}

	set_sort_key(inode, ni->starting_lcn);

	/* If processing a directory, then recurse to its children.  In this
	 * version there is no need to go to disk, as we already have the list
	 * of children cached from the MFT.  */
	if (inode_is_directory(inode)) {
		const struct ntfs_dentry *nd = ni->first_child;

		while (nd != NULL) {
			size_t orig_path_nchars;
			struct wim_dentry *child;
			const struct ntfs_dentry *next = nd->next_child;

			ret = WIMLIB_ERR_NOMEM;
			if (!pathbuf_append_name(ctx->params, nd->name,
						 wcslen(nd->name),
						 &orig_path_nchars))
				goto out;

			ret = generate_wim_structures_recursive(
					&child,
					nd->name,
					nd->is_primary,
					(void *)nd - nd->offset_from_inode,
					ctx,
					inode_map,
					security_map);

			pathbuf_truncate(ctx->params, orig_path_nchars);

			if (ret)
				goto out;

			attach_scanned_tree(root, child, ctx->params->blob_table);
			nd = next;
		}
	}

out_progress:
	if (likely(root))
		ret = do_scan_progress(ctx->params, WIMLIB_SCAN_DENTRY_OK, inode);
	else
		ret = do_scan_progress(ctx->params, WIMLIB_SCAN_DENTRY_EXCLUDED, NULL);
out:
	if (--ni->num_aliases == 0) {
		/* Memory usage optimization: when we don't need the ntfs_inode
		 * (and its names and streams) anymore, free it.  */
		ntfs_inode_map_remove(inode_map, ni);
	}
	if (unlikely(ret)) {
		free_dentry_tree(root, ctx->params->blob_table);
		root = NULL;
	}
	*root_ret = root;
	return ret;
}

static int
winnt_build_dentry_tree_fast(struct wim_dentry **root_ret,
			     struct winnt_scan_ctx *ctx)
{
	struct ntfs_inode_map inode_map = { .root = NULL };
	struct security_map security_map = { .root = NULL };
	struct ntfs_inode *root = NULL;
	wchar_t *path = ctx->params->cur_path;
	size_t path_nchars = ctx->params->cur_path_nchars;
	bool adjust_path;
	int ret;

	adjust_path = (path[path_nchars - 1] == L'\\');
	if (adjust_path)
		path[path_nchars - 1] = L'\0';

	ret = load_files_from_mft(path, &inode_map);

	if (adjust_path)
		path[path_nchars - 1] = L'\\';

	if (ret)
		goto out;

	ret = build_children_lists(&inode_map, &root);
	if (ret)
		goto out;

	if (!root) {
		ERROR("The MFT listing for volume \"%ls\" did not include a "
		      "root directory!", path);
		ret = WIMLIB_ERR_UNSUPPORTED;
		goto out;
	}

	root->num_aliases = 1;

	ret = generate_wim_structures_recursive(root_ret, L"", false, root, ctx,
						&inode_map, &security_map);
out:
	ntfs_inode_map_destroy(&inode_map);
	security_map_destroy(&security_map);
	return ret;
}

#endif /* ENABLE_FAST_MFT_SCAN */

/*----------------------------------------------------------------------------*
 *                 Entry point for directory tree scans on Windows            *
 *----------------------------------------------------------------------------*/

int
win32_build_dentry_tree(struct wim_dentry **root_ret,
			const wchar_t *root_disk_path,
			struct scan_params *params)
{
	struct winnt_scan_ctx ctx = { .params = params };
	UNICODE_STRING ntpath;
	HANDLE h = NULL;
	NTSTATUS status;
	int ret;

	if (params->add_flags & WIMLIB_ADD_FLAG_SNAPSHOT)
		ret = vss_create_snapshot(root_disk_path, &ntpath, &ctx.snapshot);
	else
		ret = win32_path_to_nt_path(root_disk_path, &ntpath);

	if (ret)
		goto out;

	if (ntpath.Length < 4 * sizeof(wchar_t) ||
	    wmemcmp(ntpath.Buffer, L"\\??\\", 4))
	{
		ERROR("\"%ls\": unrecognized path format", root_disk_path);
		ret = WIMLIB_ERR_INVALID_PARAM;
	} else {
		ret = pathbuf_init(params, ntpath.Buffer);
	}
	HeapFree(GetProcessHeap(), 0, ntpath.Buffer);
	if (ret)
		goto out;

	status = winnt_open(params->cur_path, params->cur_path_nchars,
			    FILE_READ_ATTRIBUTES, &h);
	if (!NT_SUCCESS(status)) {
		winnt_error(status, L"Can't open \"%ls\"", root_disk_path);
		if (status == STATUS_FVE_LOCKED_VOLUME)
			ret = WIMLIB_ERR_FVE_LOCKED_VOLUME;
		else
			ret = WIMLIB_ERR_OPEN;
		goto out;
	}

	get_volume_information(h, &ctx);

	NtClose(h);

#ifdef ENABLE_FAST_MFT_SCAN
	if (ctx.is_ntfs && !_wgetenv(L"WIMLIB_DISABLE_QUERY_FILE_LAYOUT")) {
		ret = winnt_build_dentry_tree_fast(root_ret, &ctx);
		if (ret >= 0 && ret != WIMLIB_ERR_UNSUPPORTED)
			goto out;
		if (ret >= 0) {
			WARNING("A problem occurred during the fast MFT scan.\n"
				"          Falling back to the standard "
				"recursive directory tree scan.");
		}
	}
#endif
	ret = winnt_build_dentry_tree_recursive(root_ret, NULL,
						params->cur_path,
						params->cur_path_nchars,
						L"", &ctx);
out:
	vss_put_snapshot(ctx.snapshot);
	if (ret == 0)
		winnt_do_scan_warnings(root_disk_path, &ctx);
	return ret;
}

#endif /* __WIN32__ */