+/*----------------------------------------------------------------------------*
+ * 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))
+
+/* 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 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);
+}
+
+/*
+ * 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)