--- /dev/null
+/*
+ * test_support.c - Supporting code for tests
+ */
+
+/*
+ * Copyright (C) 2015-2016 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/.
+ */
+
+/*
+ * This file contains specialized test code which is only compiled when the
+ * library is configured with --enable-test-support. The major features are:
+ *
+ * - Random directory tree generation
+ * - Directory tree comparison
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#ifdef ENABLE_TEST_SUPPORT
+
+#include <ctype.h>
+#include <math.h>
+
+#include "wimlib.h"
+#include "wimlib/endianness.h"
+#include "wimlib/encoding.h"
+#include "wimlib/metadata.h"
+#include "wimlib/dentry.h"
+#include "wimlib/inode.h"
+#include "wimlib/reparse.h"
+#include "wimlib/scan.h"
+#include "wimlib/security_descriptor.h"
+#include "wimlib/test_support.h"
+
+/*----------------------------------------------------------------------------*
+ * File tree generation *
+ *----------------------------------------------------------------------------*/
+
+struct generation_context {
+ struct scan_params *params;
+ struct wim_dentry *used_short_names[256];
+ bool metadata_only;
+};
+
+static u32
+rand32(void)
+{
+ static u64 state = 0x55DB93D0AB838771;
+
+ /* A simple linear congruential generator */
+ state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
+ return state >> 16;
+}
+
+static bool
+randbool(void)
+{
+ return (rand32() & 1) != 0;
+}
+
+static u8
+rand8(void)
+{
+ return (u8)rand32();
+}
+
+static u16
+rand16(void)
+{
+ return (u16)rand32();
+}
+
+static u64
+rand64(void)
+{
+ return ((u64)rand32() << 32) | rand32();
+}
+
+static u64
+generate_random_timestamp(void)
+{
+ /* When setting timestamps on Windows:
+ * - 0 is a special value meaning "not specified"
+ * - if the high bit is set you get STATUS_INVALID_PARAMETER */
+ return (1 + rand64()) & ~(1ULL << 63);
+}
+
+static const struct {
+ u8 num_subauthorities;
+ u64 identifier_authority;
+ u32 subauthorities[6];
+} common_sids[] = {
+ { 1, 0, {0}}, /* NULL_SID */
+ { 1, 1, {0}}, /* WORLD_SID */
+ { 1, 2, {0}}, /* LOCAL_SID */
+ { 1, 3, {0}}, /* CREATOR_OWNER_SID */
+ { 1, 3, {1}}, /* CREATOR_GROUP_SID */
+ { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
+ { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
+ // { 0, 5, {}}, /* NT_AUTHORITY_SID */
+ { 1, 5, {1}}, /* DIALUP_SID */
+ { 1, 5, {2}}, /* NETWORK_SID */
+ { 1, 5, {3}}, /* BATCH_SID */
+ { 1, 5, {4}}, /* INTERACTIVE_SID */
+ { 1, 5, {6}}, /* SERVICE_SID */
+ { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
+ { 1, 5, {8}}, /* PROXY_SID */
+ { 1, 5, {9}}, /* SERVER_LOGON_SID */
+ { 1, 5, {10}}, /* SELF_SID */
+ { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
+ { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
+ { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
+ { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
+ { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
+ { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
+ { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer */
+ { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS */
+};
+
+/* Generate a SID and return its size in bytes. */
+static size_t
+generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
+{
+ u32 r = rand32();
+
+ sid->revision = 1;
+
+ if (r & 1) {
+ /* Common SID */
+ r = (r >> 1) % ARRAY_LEN(common_sids);
+
+ sid->sub_authority_count = common_sids[r].num_subauthorities;
+ for (int i = 0; i < 6; i++) {
+ sid->identifier_authority[i] =
+ common_sids[r].identifier_authority >> (40 - i * 8);
+ }
+ for (int i = 0; i < common_sids[r].num_subauthorities; i++)
+ sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
+ } else {
+ /* Random SID */
+
+ sid->sub_authority_count = 1 + ((r >> 1) % 15);
+
+ for (int i = 0; i < 6; i++)
+ sid->identifier_authority[i] = rand8();
+
+ for (int i = 0; i < sid->sub_authority_count; i++)
+ sid->sub_authority[i] = cpu_to_le32(rand32());
+ }
+ return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
+}
+
+/* Generate an ACL and return its size in bytes. */
+static size_t
+generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
+{
+ u8 *p;
+ u16 ace_count;
+
+ ace_count = rand32() % 16;
+
+ acl->revision = 2;
+ acl->sbz1 = 0;
+ acl->ace_count = cpu_to_le16(ace_count);
+ acl->sbz2 = 0;
+
+ p = (u8 *)(acl + 1);
+
+ for (int i = 0; i < ace_count; i++) {
+ wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
+
+ /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
+ * same for all */
+ if (dacl)
+ ace->hdr.type = rand32() % 2;
+ else
+ ace->hdr.type = 2;
+ ace->hdr.flags = rand8();
+ ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
+
+ p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
+ generate_random_sid(&ace->sid, ctx);
+ ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
+ }
+
+ acl->acl_size = cpu_to_le16(p - (u8 *)acl);
+ return p - (u8 *)acl;
+}
+
+/* Generate a security descriptor and return its size in bytes. */
+static size_t
+generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
+{
+ wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
+ u16 control;
+ u8 *p;
+
+ control = rand16();
+
+ control &= (wimlib_SE_DACL_AUTO_INHERITED |
+ wimlib_SE_SACL_AUTO_INHERITED);
+
+ control |= wimlib_SE_SELF_RELATIVE |
+ wimlib_SE_DACL_PRESENT |
+ wimlib_SE_SACL_PRESENT;
+
+ desc->revision = 1;
+ desc->sbz1 = 0;
+ desc->control = cpu_to_le16(control);
+
+ p = (u8 *)(desc + 1);
+
+ desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
+ p += generate_random_sid((wimlib_SID *)p, ctx);
+
+ desc->group_offset = cpu_to_le32(p - (u8 *)desc);
+ p += generate_random_sid((wimlib_SID *)p, ctx);
+
+ if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
+ desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
+ p += generate_random_acl((wimlib_ACL *)p, true, ctx);
+ } else {
+ desc->dacl_offset = cpu_to_le32(0);
+ }
+
+ if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
+ desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
+ p += generate_random_acl((wimlib_ACL *)p, false, ctx);
+ } else {
+ desc->sacl_offset = cpu_to_le32(0);
+ }
+
+ return p - (u8 *)desc;
+}
+
+static int
+set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
+{
+ u32 v = rand32();
+ u32 attrib = (v & (FILE_ATTRIBUTE_READONLY |
+ FILE_ATTRIBUTE_HIDDEN |
+ FILE_ATTRIBUTE_SYSTEM |
+ FILE_ATTRIBUTE_ARCHIVE |
+ FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
+ FILE_ATTRIBUTE_COMPRESSED));
+
+ /* File attributes */
+ inode->i_attributes |= attrib;
+
+ /* Timestamps */
+ inode->i_creation_time = generate_random_timestamp();
+ inode->i_last_access_time = generate_random_timestamp();
+ inode->i_last_write_time = generate_random_timestamp();
+
+ /* Security descriptor */
+ if (randbool()) {
+ char desc[8192] _aligned_attribute(8);
+ size_t size;
+
+ size = generate_random_security_descriptor(desc, ctx);
+
+ wimlib_assert(size <= sizeof(desc));
+
+ inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
+ desc, size);
+ if (unlikely(inode->i_security_id < 0))
+ return WIMLIB_ERR_NOMEM;
+ }
+
+ return 0;
+
+}
+
+/* Choose a random size for generated file data. We want to usually generate
+ * empty, small, or medium files, but occasionally generate large files. */
+static size_t
+select_stream_size(struct generation_context *ctx)
+{
+ if (ctx->metadata_only)
+ return 0;
+
+ switch (rand32() % 2048) {
+ default:
+ /* Empty */
+ return 0;
+ case 600 ... 799:
+ /* Microscopic */
+ return rand32() % 64;
+ case 800 ... 1319:
+ /* Tiny */
+ return rand32() % 4096;
+ case 1320 ... 1799:
+ /* Small */
+ return rand32() % 32768;
+ case 1800 ... 2046:
+ /* Medium */
+ return rand32() % 262144;
+ case 2047:
+ /* Large */
+ return rand32() % 134217728;
+ }
+}
+
+/* Fill 'buffer' with 'size' bytes of "interesting" file data. */
+static void
+generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
+{
+ size_t mask = -1;
+ size_t num_byte_fills = rand32() % 256;
+
+ memset(buffer, rand32() % 256, size);
+
+ for (size_t i = 0; i < num_byte_fills; i++) {
+ u8 b = rand8();
+
+ size_t count = ((double)size / (double)num_byte_fills) *
+ ((double)rand32() / 2e9);
+ size_t offset = rand32() & ~mask;
+
+ while (count--) {
+ buffer[(offset +
+ ((rand32()) & mask)) % size] = b;
+ }
+
+
+ if (rand32() % 4 == 0)
+ mask = (size_t)-1 << rand32() % 4;
+ }
+
+ if (rand32() % 8 == 0) {
+ double magnitude = rand32() % 128;
+ double scale = 1.0 / (1 + (rand32() % 256));
+
+ for (size_t i = 0; i < size; i++)
+ buffer[i] += (int)(magnitude * cos(i * scale));
+ }
+}
+
+static int
+add_stream(struct wim_inode *inode, struct generation_context *ctx,
+ int stream_type, const utf16lechar *stream_name,
+ void *buffer, size_t size)
+{
+ struct blob_descriptor *blob = NULL;
+ struct wim_inode_stream *strm;
+
+ if (size) {
+ blob = new_blob_descriptor();
+ if (!blob)
+ goto err_nomem;
+ blob->attached_buffer = buffer;
+ blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
+ blob->size = size;
+ }
+
+ strm = inode_add_stream(inode, stream_type, stream_name, blob);
+ if (unlikely(!strm))
+ goto err_nomem;
+
+ prepare_unhashed_blob(blob, inode, strm->stream_id,
+ ctx->params->unhashed_blobs);
+ return 0;
+
+err_nomem:
+ free_blob_descriptor(blob);
+ return WIMLIB_ERR_NOMEM;
+}
+
+static int
+set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
+{
+ void *buffer = NULL;
+ size_t rpdatalen = select_stream_size(ctx) % (REPARSE_DATA_MAX_SIZE + 1);
+
+ if (rpdatalen) {
+ buffer = MALLOC(rpdatalen);
+ if (!buffer)
+ return WIMLIB_ERR_NOMEM;
+ generate_data(buffer, rpdatalen, ctx);
+ }
+
+ inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
+ inode->i_rp_reserved = rand16();
+
+ if (rpdatalen >= GUID_SIZE && randbool()) {
+ /* Non-Microsoft reparse tag (16-byte GUID required) */
+ u8 *guid = buffer;
+ guid[6] = (guid[6] & 0x0F) | 0x40;
+ guid[8] = (guid[8] & 0x3F) | 0x80;
+ inode->i_reparse_tag = 0x00000100;
+ } else {
+ /* Microsoft reparse tag */
+ inode->i_reparse_tag = 0x80000000;
+ }
+
+ return add_stream(inode, ctx, STREAM_TYPE_REPARSE_POINT, NO_STREAM_NAME,
+ buffer, rpdatalen);
+}
+
+static int
+add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
+ const utf16lechar *stream_name)
+{
+ void *buffer = NULL;
+ size_t size;
+
+ size = select_stream_size(ctx);
+ if (size) {
+ buffer = MALLOC(size);
+ if (!buffer)
+ return WIMLIB_ERR_NOMEM;
+ generate_data(buffer, size, ctx);
+ }
+
+ return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
+ buffer, size);
+}
+
+static int
+set_random_streams(struct wim_inode *inode, struct generation_context *ctx,
+ bool reparse_ok)
+{
+ int ret;
+ u32 r;
+
+ /* Reparse point (sometimes) */
+ if (reparse_ok && rand32() % 8 == 0) {
+ ret = set_random_reparse_point(inode, ctx);
+ if (ret)
+ return ret;
+ }
+
+ /* Unnamed data stream (nondirectories only) */
+ if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)) {
+ ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
+ if (ret)
+ return ret;
+ }
+
+ /* Named data streams (sometimes) */
+ r = rand32() % 256;
+ if (r > 230) {
+ utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
+ r -= 230;
+ while (r--) {
+ ret = add_random_data_stream(inode, ctx, stream_name);
+ if (ret)
+ return ret;
+ stream_name[0] += cpu_to_le16(1);
+ }
+ }
+
+ return 0;
+}
+
+static int
+generate_random_file_name(tchar name[], int max_len,
+ struct generation_context *ctx)
+{
+ int length;
+ switch (rand32() % 8) {
+ default:
+ /* short name */
+ length = 1 + (rand32() % 6);
+ break;
+ case 2:
+ case 3:
+ case 4:
+ /* medium-length name */
+ length = 7 + (rand32() % 8);
+ break;
+ case 5:
+ case 6:
+ /* long name */
+ length = 15 + (rand32() % 15);
+ break;
+ case 7:
+ /* very long name */
+ length = 30 + (rand32() % 90);
+ break;
+ }
+ length = min(length, max_len);
+ for (int i = 0; i < length; i++)
+ name[i] = 'a' + (rand32() % 26);
+ name[length] = 0;
+ return length;
+}
+
+static u64
+select_inode_number(struct generation_context *ctx)
+{
+ const struct wim_inode_table *table = ctx->params->inode_table;
+ const struct hlist_head *head;
+ const struct wim_inode *inode;
+
+ head = &table->array[rand32() % table->capacity];
+ hlist_for_each_entry(inode, head, i_hlist_node)
+ if (randbool())
+ return inode->i_ino;
+
+ return rand32();
+}
+
+static u32
+select_num_children(u32 depth, struct generation_context *ctx)
+{
+ const double b = 1.01230;
+ u32 r = rand32() % 500;
+ return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
+ (2 - exp(0.04/depth));
+}
+
+static bool
+is_name_forbidden_in_win32_namespace(const utf16lechar *name)
+{
+ static const utf16lechar forbidden_names[][5] = {
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('N'), },
+ { cpu_to_le16('P'), cpu_to_le16('R'), cpu_to_le16('N'), },
+ { cpu_to_le16('A'), cpu_to_le16('U'), cpu_to_le16('X'), },
+ { cpu_to_le16('N'), cpu_to_le16('U'), cpu_to_le16('L'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('1'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('2'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('3'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('4'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('5'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('6'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('7'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('8'), },
+ { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('9'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('1'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('2'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('3'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('4'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('5'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('6'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('7'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('8'), },
+ { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('9'), },
+ };
+
+ if (!name)
+ return false;
+
+ for (size_t i = 0; i < ARRAY_LEN(forbidden_names); i++)
+ if (!cmp_utf16le_strings_z(forbidden_names[i], name, true))
+ return true;
+
+ return false;
+}
+
+static int
+set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
+ struct generation_context *ctx)
+{
+ tchar name[12 + 1];
+ int ret;
+ const utf16lechar *short_name;
+ u32 hash;
+ struct wim_dentry **bucket;
+
+ /* If the long name is not allowed in the Win32 namespace, then it
+ * cannot be assigned a corresponding short name. */
+ if (is_name_forbidden_in_win32_namespace(child->d_name))
+ return 0;
+
+retry:
+ /* Don't select a short name that is already used by a long name within
+ * the same directory. */
+ do {
+ int len = generate_random_file_name(name, 12, ctx);
+
+ /* Legal short names on Windows take one of the following forms:
+ *
+ * - 1 to 8 characters
+ * - 1 to 8 characters, then a dot, then 1 to 3 characters */
+ if (len >= 9) {
+ if (len == 9)
+ len--;
+ else
+ name[8] = T('.');
+ }
+ name[len] = 0;
+ } while (get_dentry_child_with_name(dir, name,
+ WIMLIB_CASE_PLATFORM_DEFAULT));
+
+
+ /* Don't select a short name that is already used by another short name
+ * within the same directory. */
+ hash = 0;
+ for (const tchar *p = name; *p; p++)
+ hash = (hash * 31) + totlower(*p);
+ ret = tstr_get_utf16le(name, &short_name);
+ if (ret)
+ return ret;
+ FREE(child->d_short_name);
+ child->d_short_name = utf16le_dup(short_name);
+ child->d_short_name_nbytes = utf16le_len_bytes(short_name);
+ tstr_put_utf16le(short_name);
+
+ if (!child->d_short_name)
+ return WIMLIB_ERR_NOMEM;
+
+ bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
+
+ for (struct wim_dentry *d = *bucket; d != NULL;
+ d = d->d_next_extraction_alias)
+ if (!cmp_utf16le_strings_z(child->d_short_name,
+ d->d_short_name, true))
+ goto retry;
+
+ if (is_name_forbidden_in_win32_namespace(child->d_short_name))
+ goto retry;
+
+ child->d_next_extraction_alias = *bucket;
+ *bucket = child;
+ return 0;
+}
+
+static bool
+inode_has_short_name(const struct wim_inode *inode)
+{
+ const struct wim_dentry *dentry;
+
+ inode_for_each_dentry(dentry, inode)
+ if (dentry_has_short_name(dentry))
+ return true;
+
+ return false;
+}
+
+static int
+generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
+ struct generation_context *ctx)
+{
+ u32 num_children = select_num_children(depth, ctx);
+ struct wim_dentry *child;
+ int ret;
+
+ memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
+
+ /* Generate 'num_children' dentries within 'dir'. Some may be
+ * directories themselves. */
+
+ for (u32 i = 0; i < num_children; i++) {
+
+ /* Generate the next child dentry. */
+
+ tchar name[128 + 1];
+ struct wim_dentry *duplicate;
+ struct wim_inode *inode;
+ u64 ino;
+ bool is_directory;
+
+ /* Choose a long filename that is unique within the directory.*/
+ do {
+ generate_random_file_name(name, 128, ctx);
+ } while (get_dentry_child_with_name(dir, name,
+ WIMLIB_CASE_PLATFORM_DEFAULT));
+
+ /* Decide whether to create a directory or not.
+ * If not a directory, also decide on the inode number (i.e. we
+ * may generate a "hard link" to an existing file). */
+ is_directory = ((rand32() % 16) <= 6);
+ if (is_directory)
+ ino = 0;
+ else
+ ino = select_inode_number(ctx);
+
+ /* Create the dentry and add it to the directory. */
+ ret = inode_table_new_dentry(ctx->params->inode_table, name,
+ ino, 0, is_directory, &child);
+ if (ret)
+ return ret;
+
+ duplicate = dentry_add_child(dir, child);
+ wimlib_assert(!duplicate);
+
+ inode = child->d_inode;
+
+ if (inode->i_nlink > 1) /* Existing inode? */
+ continue;
+
+ /* New inode; set attributes, metadata, and data. */
+
+ if (is_directory)
+ inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
+
+ ret = set_random_metadata(inode, ctx);
+ if (ret)
+ return ret;
+
+ ret = set_random_streams(inode, ctx, true);
+ if (ret)
+ return ret;
+
+ /* Recurse if it's a directory. */
+ if (is_directory &&
+ !(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT))
+ {
+ ret = generate_dentry_tree_recursive(child, depth + 1,
+ ctx);
+ if (ret)
+ return ret;
+ }
+ }
+
+ for_dentry_child(child, dir) {
+ /* sometimes generate a unique short name */
+ if (randbool() && !inode_has_short_name(child->d_inode)) {
+ ret = set_random_short_name(dir, child, ctx);
+ if (ret)
+ return ret;
+ }
+ }
+
+ return 0;
+}
+
+int
+generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
+ struct scan_params *params)
+{
+ int ret;
+ struct wim_dentry *root = NULL;
+ struct generation_context ctx = {
+ .params = params,
+ };
+
+ ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only */
+
+ ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
+ if (!ret) {
+ root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
+ ret = set_random_metadata(root->d_inode, &ctx);
+ }
+ if (!ret)
+ ret = set_random_streams(root->d_inode, &ctx, false);
+ if (!ret)
+ ret = generate_dentry_tree_recursive(root, 1, &ctx);
+ if (!ret)
+ *root_ret = root;
+ else
+ free_dentry_tree(root, params->blob_table);
+ return ret;
+}
+
+/*----------------------------------------------------------------------------*
+ * File tree comparison *
+ *----------------------------------------------------------------------------*/
+
+#define INDEX_NODE_TO_DENTRY(node) \
+ ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
+
+static struct wim_dentry *
+dentry_first_child(struct wim_dentry *dentry)
+{
+ return INDEX_NODE_TO_DENTRY(
+ avl_tree_first_in_order(dentry->d_inode->i_children));
+}
+
+static struct wim_dentry *
+dentry_next_sibling(struct wim_dentry *dentry)
+{
+ return INDEX_NODE_TO_DENTRY(
+ avl_tree_next_in_order(&dentry->d_index_node));
+}
+
+/*
+ * Verify that the dentries in the tree 'd1' exactly match the dentries in the
+ * tree 'd2', considering long and short filenames. In addition, set
+ * 'd_corresponding' of each dentry to point to the corresponding dentry in the
+ * other tree, and set 'i_corresponding' of each inode to point to the
+ * unverified corresponding inode in the other tree.
+ */
+static int
+calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
+ int cmp_flags)
+{
+ struct wim_dentry *child1;
+ struct wim_dentry *child2;
+ int ret;
+
+ /* Compare long filenames, case sensitively. */
+ if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
+ d2->d_name, d2->d_name_nbytes / 2,
+ false))
+ {
+ ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
+ dentry_full_path(d1), dentry_full_path(d2));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+
+ /* Compare short filenames, case insensitively. */
+ if (!(d2->d_short_name_nbytes == 0 &&
+ (cmp_flags & WIMLIB_CMP_FLAG_SHORT_NAMES_NOT_PRESERVED)) &&
+ cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
+ d2->d_short_name, d2->d_short_name_nbytes / 2,
+ true))
+ {
+ ERROR("Short name mismatch; path=\"%"TS"\"",
+ dentry_full_path(d1));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+
+ /* Match up the dentries */
+ d1->d_corresponding = d2;
+ d2->d_corresponding = d1;
+
+ /* Match up the inodes (may overwrite previous value) */
+ d1->d_inode->i_corresponding = d2->d_inode;
+ d2->d_inode->i_corresponding = d1->d_inode;
+
+ /* Process children */
+ child1 = dentry_first_child(d1);
+ child2 = dentry_first_child(d2);
+ while (child1 || child2) {
+
+ if (!child1 || !child2) {
+ ERROR("Child count mismatch; "
+ "path1=\"%"TS"\", path2=\"%"TS"\"",
+ dentry_full_path(d1), dentry_full_path(d2));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+
+ /* Recurse on this pair of children. */
+ ret = calc_corresponding_files_recursive(child1, child2,
+ cmp_flags);
+ if (ret)
+ return ret;
+
+ /* Continue to the next pair of children. */
+ child1 = dentry_next_sibling(child1);
+ child2 = dentry_next_sibling(child2);
+ }
+ return 0;
+}
+
+/* Perform sanity checks on an image's inodes. All assertions here should pass,
+ * even if the images being compared are different. */
+static void
+assert_inodes_sane(const struct wim_image_metadata *imd)
+{
+ const struct wim_inode *inode;
+ const struct wim_dentry *dentry;
+ size_t link_count;
+
+ image_for_each_inode(inode, imd) {
+ link_count = 0;
+ inode_for_each_dentry(dentry, inode) {
+ wimlib_assert(dentry->d_inode == inode);
+ link_count++;
+ }
+ wimlib_assert(link_count > 0);
+ wimlib_assert(link_count == inode->i_nlink);
+ wimlib_assert(inode->i_corresponding != NULL);
+ }
+}
+
+static int
+check_hard_link(struct wim_dentry *dentry, void *_ignore)
+{
+ /* My inode is my corresponding dentry's inode's corresponding inode,
+ * and my inode's corresponding inode is my corresponding dentry's
+ * inode. */
+ const struct wim_inode *a = dentry->d_inode;
+ const struct wim_inode *b = dentry->d_corresponding->d_inode;
+ if (a == b->i_corresponding && a->i_corresponding == b)
+ return 0;
+ ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+}
+
+static int
+cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
+ const struct wim_image_metadata *imd1,
+ const struct wim_image_metadata *imd2, int cmp_flags)
+{
+ const u32 attrib_diff = inode1->i_attributes ^ inode2->i_attributes;
+ bool reparse_point_should_preserved = true;
+
+ /* Compare attributes */
+ if (cmp_flags & WIMLIB_CMP_FLAG_ATTRIBUTES_NOT_PRESERVED) {
+
+ /* In this mode, we expect that most attributes are not
+ * preserved. However, FILE_ATTRIBUTE_DIRECTORY should always
+ * match. */
+ if (attrib_diff & FILE_ATTRIBUTE_DIRECTORY)
+ goto attrib_mismatch;
+
+ /* We may also expect FILE_ATTRIBUTE_REPARSE_POINT to be
+ * preserved for symlinks. It also shouldn't be set if it
+ * wasn't set before. */
+
+ if ((cmp_flags & WIMLIB_CMP_FLAG_IMAGE2_SHOULD_HAVE_SYMLINKS) &&
+ inode_is_symlink(inode1))
+ reparse_point_should_preserved = true;
+ else
+ reparse_point_should_preserved = false;
+
+ if ((attrib_diff & FILE_ATTRIBUTE_REPARSE_POINT) &&
+ (reparse_point_should_preserved ||
+ (inode2->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)))
+ goto attrib_mismatch;
+ } else {
+
+ /* Most attributes should be preserved. */
+
+ /* Nothing other than COMPRESSED and NORMAL should have changed.
+ */
+ if (attrib_diff & ~(FILE_ATTRIBUTE_COMPRESSED |
+ FILE_ATTRIBUTE_NORMAL))
+ goto attrib_mismatch;
+
+ /* COMPRESSED shouldn't have changed unless specifically
+ * excluded. */
+ if ((attrib_diff & FILE_ATTRIBUTE_COMPRESSED) &&
+ !(cmp_flags & WIMLIB_CMP_FLAG_COMPRESSION_NOT_PRESERVED))
+ goto attrib_mismatch;
+
+ /* We allow NORMAL to change, but not if the file ended up with
+ * other attributes set as well. */
+ if ((attrib_diff & FILE_ATTRIBUTE_NORMAL) &&
+ (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
+ goto attrib_mismatch;
+ }
+
+ /* Compare security descriptors */
+ if (inode_has_security_descriptor(inode1)) {
+ if (inode_has_security_descriptor(inode2)) {
+ const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
+ const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
+ size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
+ size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
+
+ if (size1 != size2 || memcmp(desc1, desc2, size1)) {
+ ERROR("Security descriptor of %"TS" differs!",
+ inode_any_full_path(inode1));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+ } else if (!(cmp_flags & WIMLIB_CMP_FLAG_SECURITY_NOT_PRESERVED)) {
+ ERROR("%"TS" has a security descriptor in the first image but "
+ "not in the second image!", inode_any_full_path(inode1));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+ } else if (inode_has_security_descriptor(inode2)) {
+ /* okay --- consider it acceptable if a default security
+ * descriptor was assigned */
+ /*ERROR("%"TS" has a security descriptor in the second image but "*/
+ /*"not in the first image!", inode_any_full_path(inode1));*/
+ /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
+ }
+
+ /* Compare streams */
+ for (unsigned i = 0; i < inode1->i_num_streams; i++) {
+ const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
+ const struct wim_inode_stream *strm2;
+
+ if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
+ !reparse_point_should_preserved)
+ continue;
+
+ if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
+ continue;
+
+ /* Get the corresponding stream from the second file */
+ strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
+
+ if (!strm2) {
+ /* Corresponding stream not found */
+ if (stream_is_named(strm1) &&
+ (cmp_flags & WIMLIB_CMP_FLAG_ADS_NOT_PRESERVED))
+ continue;
+ ERROR("Stream of %"TS" is missing in second image; "
+ "type %d, named=%d, empty=%d",
+ inode_any_full_path(inode1),
+ strm1->stream_type,
+ stream_is_named(strm1),
+ is_zero_hash(stream_hash(strm1)));
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+
+ if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
+ ERROR("Stream of %"TS" differs; type %d",
+ inode_any_full_path(inode1), strm1->stream_type);
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+ }
+ }
+
+ return 0;
+
+attrib_mismatch:
+ ERROR("Attribute mismatch; %"TS" has attributes 0x%08"PRIx32" "
+ "in first image but attributes 0x%08"PRIx32" in second image",
+ inode_any_full_path(inode1), inode1->i_attributes,
+ inode2->i_attributes);
+ return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
+}
+
+static int
+cmp_images(const struct wim_image_metadata *imd1,
+ const struct wim_image_metadata *imd2, int cmp_flags)
+{
+ struct wim_dentry *root1 = imd1->root_dentry;
+ struct wim_dentry *root2 = imd2->root_dentry;
+ const struct wim_inode *inode;
+ int ret;
+
+ ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
+ if (ret)
+ return ret;
+
+ /* Verify that the hard links match up between the two images. */
+ assert_inodes_sane(imd1);
+ assert_inodes_sane(imd2);
+ ret = for_dentry_in_tree(root1, check_hard_link, NULL);
+ if (ret)
+ return ret;
+
+ /* Compare corresponding inodes. */
+ image_for_each_inode(inode, imd1) {
+ ret = cmp_inodes(inode, inode->i_corresponding,
+ imd1, imd2, cmp_flags);
+ if (ret)
+ return ret;
+ }
+
+ return 0;
+}
+
+static int
+load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
+{
+ int ret = select_wim_image(wim, image);
+ if (!ret) {
+ *imd_ret = wim_get_current_image_metadata(wim);
+ mark_image_dirty(*imd_ret);
+ }
+ return ret;
+}
+
+WIMLIBAPI int
+wimlib_compare_images(WIMStruct *wim1, int image1,
+ WIMStruct *wim2, int image2, int cmp_flags)
+{
+ int ret;
+ struct wim_image_metadata *imd1, *imd2;
+
+ ret = load_image(wim1, image1, &imd1);
+ if (!ret)
+ ret = load_image(wim2, image2, &imd2);
+ if (!ret)
+ ret = cmp_images(imd1, imd2, cmp_flags);
+ return ret;
+}
+
+#endif /* ENABLE_TEST_SUPPORT */
git://wimlib.net / wimlib / blobdiff