+/* 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);
+}
+
+static bool
+is_object_id_stream(const STREAM_LAYOUT_ENTRY *stream)
+{
+ return stream->StreamIdentifierLength == 24 &&
+ !wmemcmp(stream->StreamIdentifier, L"::$OBJECT_ID", 12);
+}
+
+/*
+ * 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 *have_object_id_ret=true if the file has an
+ * object ID stream. */
+static int
+validate_streams_and_compute_total_length(const FILE_LAYOUT_ENTRY *file,
+ size_t *total_length_ret,
+ bool *have_object_id_ret)