2 * test_support.c - Supporting code for tests
6 * Copyright (C) 2015-2016 Eric Biggers
8 * This file is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU Lesser General Public License as published by the Free
10 * Software Foundation; either version 3 of the License, or (at your option) any
13 * This file is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this file; if not, see http://www.gnu.org/licenses/.
23 * This file contains specialized test code which is only compiled when the
24 * library is configured with --enable-test-support. The major features are:
26 * - Random directory tree generation
27 * - Directory tree comparison
34 #ifdef ENABLE_TEST_SUPPORT
40 #include "wimlib/endianness.h"
41 #include "wimlib/encoding.h"
42 #include "wimlib/metadata.h"
43 #include "wimlib/dentry.h"
44 #include "wimlib/inode.h"
45 #include "wimlib/object_id.h"
46 #include "wimlib/reparse.h"
47 #include "wimlib/scan.h"
48 #include "wimlib/security_descriptor.h"
49 #include "wimlib/test_support.h"
51 /*----------------------------------------------------------------------------*
52 * File tree generation *
53 *----------------------------------------------------------------------------*/
55 struct generation_context {
56 struct scan_params *params;
57 struct wim_dentry *used_short_names[256];
64 static u64 state = 0x55DB93D0AB838771;
66 /* A simple linear congruential generator */
67 state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
74 return (rand32() & 1) != 0;
92 return ((u64)rand32() << 32) | rand32();
96 generate_random_timestamp(void)
98 /* When setting timestamps on Windows:
99 * - 0 is a special value meaning "not specified"
100 * - if the high bit is set you get STATUS_INVALID_PARAMETER */
101 return (1 + rand64()) & ~(1ULL << 63);
104 static const struct {
105 u8 num_subauthorities;
106 u64 identifier_authority;
107 u32 subauthorities[6];
109 { 1, 0, {0}}, /* NULL_SID */
110 { 1, 1, {0}}, /* WORLD_SID */
111 { 1, 2, {0}}, /* LOCAL_SID */
112 { 1, 3, {0}}, /* CREATOR_OWNER_SID */
113 { 1, 3, {1}}, /* CREATOR_GROUP_SID */
114 { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
115 { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
116 // { 0, 5, {}}, /* NT_AUTHORITY_SID */
117 { 1, 5, {1}}, /* DIALUP_SID */
118 { 1, 5, {2}}, /* NETWORK_SID */
119 { 1, 5, {3}}, /* BATCH_SID */
120 { 1, 5, {4}}, /* INTERACTIVE_SID */
121 { 1, 5, {6}}, /* SERVICE_SID */
122 { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
123 { 1, 5, {8}}, /* PROXY_SID */
124 { 1, 5, {9}}, /* SERVER_LOGON_SID */
125 { 1, 5, {10}}, /* SELF_SID */
126 { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
127 { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
128 { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
129 { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
130 { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
131 { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
132 { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer */
133 { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS */
136 /* Generate a SID and return its size in bytes. */
138 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
146 r = (r >> 1) % ARRAY_LEN(common_sids);
148 sid->sub_authority_count = common_sids[r].num_subauthorities;
149 for (int i = 0; i < 6; i++) {
150 sid->identifier_authority[i] =
151 common_sids[r].identifier_authority >> (40 - i * 8);
153 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
154 sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
158 sid->sub_authority_count = 1 + ((r >> 1) % 15);
160 for (int i = 0; i < 6; i++)
161 sid->identifier_authority[i] = rand8();
163 for (int i = 0; i < sid->sub_authority_count; i++)
164 sid->sub_authority[i] = cpu_to_le32(rand32());
166 return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
169 /* Generate an ACL and return its size in bytes. */
171 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
176 ace_count = rand32() % 16;
180 acl->ace_count = cpu_to_le16(ace_count);
185 for (int i = 0; i < ace_count; i++) {
186 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
188 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
191 ace->hdr.type = rand32() % 2;
194 ace->hdr.flags = rand8();
195 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
197 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
198 generate_random_sid(&ace->sid, ctx);
199 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
202 acl->acl_size = cpu_to_le16(p - (u8 *)acl);
203 return p - (u8 *)acl;
206 /* Generate a security descriptor and return its size in bytes. */
208 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
210 wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
216 control &= (wimlib_SE_DACL_AUTO_INHERITED |
217 wimlib_SE_SACL_AUTO_INHERITED);
219 control |= wimlib_SE_SELF_RELATIVE |
220 wimlib_SE_DACL_PRESENT |
221 wimlib_SE_SACL_PRESENT;
225 desc->control = cpu_to_le16(control);
227 p = (u8 *)(desc + 1);
229 desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
230 p += generate_random_sid((wimlib_SID *)p, ctx);
232 desc->group_offset = cpu_to_le32(p - (u8 *)desc);
233 p += generate_random_sid((wimlib_SID *)p, ctx);
235 if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
236 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
237 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
239 desc->dacl_offset = cpu_to_le32(0);
242 if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
243 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
244 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
246 desc->sacl_offset = cpu_to_le32(0);
249 return p - (u8 *)desc;
253 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
255 u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
256 FILE_ATTRIBUTE_HIDDEN |
257 FILE_ATTRIBUTE_SYSTEM |
258 FILE_ATTRIBUTE_ARCHIVE |
259 FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
260 FILE_ATTRIBUTE_COMPRESSED |
261 FILE_ATTRIBUTE_SPARSE_FILE));
263 /* File attributes */
264 inode->i_attributes |= attrib;
267 inode->i_creation_time = generate_random_timestamp();
268 inode->i_last_access_time = generate_random_timestamp();
269 inode->i_last_write_time = generate_random_timestamp();
271 /* Security descriptor */
273 char desc[8192] _aligned_attribute(8);
276 size = generate_random_security_descriptor(desc, ctx);
278 wimlib_assert(size <= sizeof(desc));
280 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
282 if (unlikely(inode->i_security_id < 0))
283 return WIMLIB_ERR_NOMEM;
287 if (rand32() % 32 == 0) {
288 struct wimlib_object_id object_id;
290 for (int i = 0; i < sizeof(object_id); i++)
291 *((u8 *)&object_id + i) = rand8();
292 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
293 return WIMLIB_ERR_NOMEM;
300 /* Choose a random size for generated file data. We want to usually generate
301 * empty, small, or medium files, but occasionally generate large files. */
303 select_stream_size(struct generation_context *ctx)
305 if (ctx->metadata_only)
308 switch (rand32() % 2048) {
314 return rand32() % 64;
317 return rand32() % 4096;
320 return rand32() % 32768;
323 return rand32() % 262144;
326 return rand32() % 134217728;
330 /* Fill 'buffer' with 'size' bytes of "interesting" file data. */
332 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
335 size_t num_byte_fills = rand32() % 256;
337 /* Start by initializing to a random byte */
338 memset(buffer, rand32() % 256, size);
340 /* Add some random bytes in some random places */
341 for (size_t i = 0; i < num_byte_fills; i++) {
344 size_t count = ((double)size / (double)num_byte_fills) *
345 ((double)rand32() / 2e9);
346 size_t offset = rand32() & ~mask;
350 ((rand32()) & mask)) % size] = b;
354 if (rand32() % 4 == 0)
355 mask = (size_t)-1 << rand32() % 4;
358 /* Sometimes add a wave pattern */
359 if (rand32() % 8 == 0) {
360 double magnitude = rand32() % 128;
361 double scale = 1.0 / (1 + (rand32() % 256));
363 for (size_t i = 0; i < size; i++)
364 buffer[i] += (int)(magnitude * cos(i * scale));
367 /* Sometimes add some zero regions (holes) */
368 if (rand32() % 4 == 0) {
369 size_t num_holes = 1 + (rand32() % 16);
370 for (size_t i = 0; i < num_holes; i++) {
371 size_t hole_offset = rand32() % size;
372 size_t hole_len = min(size - hole_offset,
373 size / (1 + (rand32() % 16)));
374 memset(&buffer[hole_offset], 0, hole_len);
380 add_stream(struct wim_inode *inode, struct generation_context *ctx,
381 int stream_type, const utf16lechar *stream_name,
382 void *buffer, size_t size)
384 struct blob_descriptor *blob = NULL;
385 struct wim_inode_stream *strm;
388 blob = new_blob_descriptor();
391 blob->attached_buffer = buffer;
392 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
396 strm = inode_add_stream(inode, stream_type, stream_name, blob);
400 prepare_unhashed_blob(blob, inode, strm->stream_id,
401 ctx->params->unhashed_blobs);
405 free_blob_descriptor(blob);
406 return WIMLIB_ERR_NOMEM;
410 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
413 size_t rpdatalen = select_stream_size(ctx) % (REPARSE_DATA_MAX_SIZE + 1);
416 buffer = MALLOC(rpdatalen);
418 return WIMLIB_ERR_NOMEM;
419 generate_data(buffer, rpdatalen, ctx);
422 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
423 inode->i_rp_reserved = rand16();
425 if (rpdatalen >= GUID_SIZE && randbool()) {
426 /* Non-Microsoft reparse tag (16-byte GUID required) */
428 guid[6] = (guid[6] & 0x0F) | 0x40;
429 guid[8] = (guid[8] & 0x3F) | 0x80;
430 inode->i_reparse_tag = 0x00000100;
432 /* Microsoft reparse tag */
433 inode->i_reparse_tag = 0x80000000;
436 return add_stream(inode, ctx, STREAM_TYPE_REPARSE_POINT, NO_STREAM_NAME,
441 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
442 const utf16lechar *stream_name)
447 size = select_stream_size(ctx);
449 buffer = MALLOC(size);
451 return WIMLIB_ERR_NOMEM;
452 generate_data(buffer, size, ctx);
455 return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
460 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
465 /* Reparse point (sometimes) */
466 if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
467 ret = set_random_reparse_point(inode, ctx);
472 /* Unnamed data stream (nondirectories only) */
473 if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)) {
474 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
479 /* Named data streams (sometimes) */
482 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
485 ret = add_random_data_stream(inode, ctx, stream_name);
488 stream_name[0] += cpu_to_le16(1);
496 is_valid_windows_filename_char(utf16lechar c)
498 return le16_to_cpu(c) > 31 &&
499 c != cpu_to_le16('/') &&
500 c != cpu_to_le16('<') &&
501 c != cpu_to_le16('>') &&
502 c != cpu_to_le16(':') &&
503 c != cpu_to_le16('"') &&
504 c != cpu_to_le16('/' ) &&
505 c != cpu_to_le16('\\') &&
506 c != cpu_to_le16('|') &&
507 c != cpu_to_le16('?') &&
508 c != cpu_to_le16('*');
511 /* Is the character valid in a filename on the current platform? */
513 is_valid_filename_char(utf16lechar c)
516 return is_valid_windows_filename_char(c);
518 return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
522 /* Generate a random filename and return its length. */
524 generate_random_filename(utf16lechar name[], int max_len,
525 struct generation_context *ctx)
529 /* Choose the length of the name. */
530 switch (rand32() % 8) {
533 len = 1 + (rand32() % 6);
538 /* medium-length name */
539 len = 7 + (rand32() % 8);
544 len = 15 + (rand32() % 15);
548 len = 30 + (rand32() % 90);
551 len = min(len, max_len);
554 /* Generate the characters in the name. */
555 for (int i = 0; i < len; i++) {
558 } while (!is_valid_filename_char(name[i]));
561 /* Add a null terminator. */
562 name[len] = cpu_to_le16('\0');
564 /* Don't generate . and .. */
565 if (name[0] == cpu_to_le16('.') &&
566 (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
572 /* The set of characters which are valid in short filenames. */
573 static const char valid_short_name_chars[] = {
574 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
575 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
576 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
577 '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
579 /* Note: Windows does not allow space and 128-255 in short filenames
580 * (tested on both NTFS and FAT). */
584 generate_short_name_component(utf16lechar p[], int len)
586 for (int i = 0; i < len; i++) {
587 char c = valid_short_name_chars[rand32() %
588 ARRAY_LEN(valid_short_name_chars)];
589 p[i] = cpu_to_le16(c);
594 /* Generate a random short (8.3) filename and return its length.
595 * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
597 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
600 * Legal short names on Windows consist of 1 to 8 characters, optionally
601 * followed by a dot then 1 to 3 more characters. Only certain
602 * characters are allowed.
604 int base_len = 1 + (rand32() % 8);
605 int ext_len = rand32() % 4;
608 base_len = generate_short_name_component(name, base_len);
611 name[base_len] = cpu_to_le16('.');
612 ext_len = generate_short_name_component(&name[base_len + 1],
614 total_len = base_len + 1 + ext_len;
616 total_len = base_len;
618 name[total_len] = cpu_to_le16('\0');
623 select_inode_number(struct generation_context *ctx)
625 const struct wim_inode_table *table = ctx->params->inode_table;
626 const struct hlist_head *head;
627 const struct wim_inode *inode;
629 head = &table->array[rand32() % table->capacity];
630 hlist_for_each_entry(inode, head, i_hlist_node)
638 select_num_children(u32 depth, struct generation_context *ctx)
640 const double b = 1.01230;
641 u32 r = rand32() % 500;
642 return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
643 (2 - exp(0.04/depth));
647 is_name_valid_in_win32_namespace(const utf16lechar *name)
649 const utf16lechar *p;
651 static const char * const reserved_names[] = {
652 "CON", "PRN", "AUX", "NUL",
653 "COM1", "COM2", "COM3", "COM4", "COM5",
654 "COM6", "COM7", "COM8", "COM9",
655 "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
656 "LPT6", "LPT7", "LPT8", "LPT9",
659 /* The name must be nonempty. */
663 /* All characters must be valid on Windows. */
664 for (p = name; *p; p++)
665 if (!is_valid_windows_filename_char(*p))
668 /* Note: a trailing dot or space is permitted, even though on Windows
669 * such a file can only be accessed using a WinNT-style path. */
671 /* The name can't be one of the reserved names or be a reserved name
672 * with an extension. Case insensitive. */
673 for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
674 for (size_t j = 0; ; j++) {
675 u16 c1 = le16_to_cpu(name[j]);
676 u16 c2 = reserved_names[i][j];
678 if (c1 == '\0' || c1 == '.')
682 if (upcase[c1] != upcase[c2])
691 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
692 struct generation_context *ctx)
694 utf16lechar name[12 + 1];
697 struct wim_dentry **bucket;
699 /* If the long name is not allowed in the Win32 namespace, then it
700 * cannot be assigned a corresponding short name. */
701 if (!is_name_valid_in_win32_namespace(child->d_name))
705 /* Don't select a short name that is already used by a long name within
706 * the same directory. */
708 name_len = generate_random_short_name(name, ctx);
709 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
710 WIMLIB_CASE_INSENSITIVE));
713 /* Don't select a short name that is already used by another short name
714 * within the same directory. */
716 for (const utf16lechar *p = name; *p; p++)
717 hash = (hash * 31) + *p;
718 FREE(child->d_short_name);
719 child->d_short_name = memdup(name, (name_len + 1) * 2);
720 child->d_short_name_nbytes = name_len * 2;
722 if (!child->d_short_name)
723 return WIMLIB_ERR_NOMEM;
725 bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
727 for (struct wim_dentry *d = *bucket; d != NULL;
728 d = d->d_next_extraction_alias) {
729 if (!cmp_utf16le_strings(child->d_short_name, name_len,
730 d->d_short_name, d->d_short_name_nbytes / 2,
736 if (!is_name_valid_in_win32_namespace(child->d_short_name))
739 child->d_next_extraction_alias = *bucket;
745 inode_has_short_name(const struct wim_inode *inode)
747 const struct wim_dentry *dentry;
749 inode_for_each_dentry(dentry, inode)
750 if (dentry_has_short_name(dentry))
757 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
758 struct generation_context *ctx)
760 u32 num_children = select_num_children(depth, ctx);
761 struct wim_dentry *child;
764 memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
766 /* Generate 'num_children' dentries within 'dir'. Some may be
767 * directories themselves. */
769 for (u32 i = 0; i < num_children; i++) {
771 /* Generate the next child dentry. */
772 struct wim_inode *inode;
774 bool is_directory = (rand32() % 16 <= 6);
775 bool is_reparse = (rand32() % 8 == 0);
776 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
778 struct wim_dentry *duplicate;
781 * Select an inode number for the new file. Sometimes choose an
782 * existing inode number (i.e. create a hard link). However,
783 * wimlib intentionally doesn't honor directory hard links, and
784 * reparse points cannot be represented in the WIM file format
785 * at all; so don't create hard links for such files.
787 if (is_directory || is_reparse)
790 ino = select_inode_number(ctx);
792 /* Create the dentry. */
793 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
794 ino, 0, ino == 0, &child);
798 /* Choose a filename that is unique within the directory.*/
800 name_len = generate_random_filename(name,
803 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
804 WIMLIB_CASE_PLATFORM_DEFAULT));
806 ret = dentry_set_name_utf16le(child, name, name_len * 2);
812 /* Add the dentry to the directory. */
813 duplicate = dentry_add_child(dir, child);
814 wimlib_assert(!duplicate);
816 inode = child->d_inode;
818 if (inode->i_nlink > 1) /* Existing inode? */
821 /* New inode; set attributes, metadata, and data. */
824 inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
826 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
828 ret = set_random_streams(inode, ctx);
832 ret = set_random_metadata(inode, ctx);
836 /* Recurse if it's a directory. */
837 if (is_directory && !is_reparse) {
838 ret = generate_dentry_tree_recursive(child, depth + 1,
845 for_dentry_child(child, dir) {
846 /* sometimes generate a unique short name */
847 if (randbool() && !inode_has_short_name(child->d_inode)) {
848 ret = set_random_short_name(dir, child, ctx);
858 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
859 struct scan_params *params)
862 struct wim_dentry *root = NULL;
863 struct generation_context ctx = {
867 ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only */
869 ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
871 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
872 ret = set_random_streams(root->d_inode, &ctx);
875 ret = set_random_metadata(root->d_inode, &ctx);
877 ret = generate_dentry_tree_recursive(root, 1, &ctx);
881 free_dentry_tree(root, params->blob_table);
885 /*----------------------------------------------------------------------------*
886 * File tree comparison *
887 *----------------------------------------------------------------------------*/
889 #define INDEX_NODE_TO_DENTRY(node) \
890 ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
892 static struct wim_dentry *
893 dentry_first_child(struct wim_dentry *dentry)
895 return INDEX_NODE_TO_DENTRY(
896 avl_tree_first_in_order(dentry->d_inode->i_children));
899 static struct wim_dentry *
900 dentry_next_sibling(struct wim_dentry *dentry)
902 return INDEX_NODE_TO_DENTRY(
903 avl_tree_next_in_order(&dentry->d_index_node));
907 * Verify that the dentries in the tree 'd1' exactly match the dentries in the
908 * tree 'd2', considering long and short filenames. In addition, set
909 * 'd_corresponding' of each dentry to point to the corresponding dentry in the
910 * other tree, and set 'i_corresponding' of each inode to point to the
911 * unverified corresponding inode in the other tree.
914 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
917 struct wim_dentry *child1;
918 struct wim_dentry *child2;
921 /* Compare long filenames, case sensitively. */
922 if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
923 d2->d_name, d2->d_name_nbytes / 2,
926 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
927 dentry_full_path(d1), dentry_full_path(d2));
928 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
931 /* Compare short filenames, case insensitively. */
932 if (!(d2->d_short_name_nbytes == 0 &&
933 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
934 cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
935 d2->d_short_name, d2->d_short_name_nbytes / 2,
938 ERROR("Short name mismatch; path=\"%"TS"\"",
939 dentry_full_path(d1));
940 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
943 /* Match up the dentries */
944 d1->d_corresponding = d2;
945 d2->d_corresponding = d1;
947 /* Match up the inodes (may overwrite previous value) */
948 d1->d_inode->i_corresponding = d2->d_inode;
949 d2->d_inode->i_corresponding = d1->d_inode;
951 /* Process children */
952 child1 = dentry_first_child(d1);
953 child2 = dentry_first_child(d2);
954 while (child1 || child2) {
956 if (!child1 || !child2) {
957 ERROR("Child count mismatch; "
958 "path1=\"%"TS"\", path2=\"%"TS"\"",
959 dentry_full_path(d1), dentry_full_path(d2));
960 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
963 /* Recurse on this pair of children. */
964 ret = calc_corresponding_files_recursive(child1, child2,
969 /* Continue to the next pair of children. */
970 child1 = dentry_next_sibling(child1);
971 child2 = dentry_next_sibling(child2);
976 /* Perform sanity checks on an image's inodes. All assertions here should pass,
977 * even if the images being compared are different. */
979 assert_inodes_sane(const struct wim_image_metadata *imd)
981 const struct wim_inode *inode;
982 const struct wim_dentry *dentry;
985 image_for_each_inode(inode, imd) {
987 inode_for_each_dentry(dentry, inode) {
988 wimlib_assert(dentry->d_inode == inode);
991 wimlib_assert(link_count > 0);
992 wimlib_assert(link_count == inode->i_nlink);
993 wimlib_assert(inode->i_corresponding != NULL);
998 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1000 /* My inode is my corresponding dentry's inode's corresponding inode,
1001 * and my inode's corresponding inode is my corresponding dentry's
1003 const struct wim_inode *a = dentry->d_inode;
1004 const struct wim_inode *b = dentry->d_corresponding->d_inode;
1005 if (a == b->i_corresponding && a->i_corresponding == b)
1007 ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1008 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1011 static const struct {
1014 } file_attr_flags[] = {
1015 {FILE_ATTRIBUTE_READONLY, "READONLY"},
1016 {FILE_ATTRIBUTE_HIDDEN, "HIDDEN"},
1017 {FILE_ATTRIBUTE_SYSTEM, "SYSTEM"},
1018 {FILE_ATTRIBUTE_DIRECTORY, "DIRECTORY"},
1019 {FILE_ATTRIBUTE_ARCHIVE, "ARCHIVE"},
1020 {FILE_ATTRIBUTE_DEVICE, "DEVICE"},
1021 {FILE_ATTRIBUTE_NORMAL, "NORMAL"},
1022 {FILE_ATTRIBUTE_TEMPORARY, "TEMPORARY"},
1023 {FILE_ATTRIBUTE_SPARSE_FILE, "SPARSE_FILE"},
1024 {FILE_ATTRIBUTE_REPARSE_POINT, "REPARSE_POINT"},
1025 {FILE_ATTRIBUTE_COMPRESSED, "COMPRESSED"},
1026 {FILE_ATTRIBUTE_OFFLINE, "OFFLINE"},
1027 {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1028 {FILE_ATTRIBUTE_ENCRYPTED, "ENCRYPTED"},
1029 {FILE_ATTRIBUTE_VIRTUAL, "VIRTUAL"},
1033 cmp_attributes(const struct wim_inode *inode1,
1034 const struct wim_inode *inode2, int cmp_flags)
1036 const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1037 const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1038 const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1040 /* NORMAL may change, but it must never be set along with other
1042 if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1043 (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1046 /* DIRECTORY must not change. */
1047 if (changed & FILE_ATTRIBUTE_DIRECTORY)
1050 /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1052 if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1053 !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1054 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1055 !inode_is_symlink(inode1)))
1058 /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1059 * mode if the inode is a directory. */
1060 if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1061 !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1062 ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1063 WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1064 ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1065 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1068 /* COMPRESSED may change in UNIX and NTFS-3G modes. (It *should* be
1069 * preserved in NTFS-3G mode, but it's not implemented yet.) */
1070 if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1071 !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1072 WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1075 /* All other attributes can change in UNIX mode, but not in any other
1077 if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1078 FILE_ATTRIBUTE_DIRECTORY |
1079 FILE_ATTRIBUTE_REPARSE_POINT |
1080 FILE_ATTRIBUTE_SPARSE_FILE |
1081 FILE_ATTRIBUTE_COMPRESSED)) &&
1082 !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1088 ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1089 inode_any_full_path(inode1), inode1->i_attributes,
1090 inode2->i_attributes);
1091 for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1092 u32 flag = file_attr_flags[i].flag;
1093 if (changed & flag) {
1094 fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1095 file_attr_flags[i].name,
1096 (set & flag) ? "set" : "cleared");
1099 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1103 cmp_object_ids(const struct wim_inode *inode1,
1104 const struct wim_inode *inode2, int cmp_flags)
1106 const void *objid1, *objid2;
1109 objid1 = inode_get_object_id(inode1, &len1);
1110 objid2 = inode_get_object_id(inode2, &len2);
1112 if (!objid1 && !objid2)
1115 if (objid1 && !objid2) {
1116 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1118 ERROR("%"TS" unexpectedly lost its object ID",
1119 inode_any_full_path(inode1));
1120 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1123 if (!objid1 && objid2) {
1124 ERROR("%"TS" unexpectedly gained an object ID",
1125 inode_any_full_path(inode1));
1126 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1129 if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1130 ERROR("Object ID of %"TS" differs",
1131 inode_any_full_path(inode1));
1132 fprintf(stderr, "objid1=");
1133 print_byte_field(objid1, len1, stderr);
1134 fprintf(stderr, "\nobjid2=");
1135 print_byte_field(objid2, len2, stderr);
1136 fprintf(stderr, "\n");
1137 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1144 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1145 const struct wim_image_metadata *imd1,
1146 const struct wim_image_metadata *imd2, int cmp_flags)
1150 /* Compare attributes */
1151 ret = cmp_attributes(inode1, inode2, cmp_flags);
1155 /* Compare security descriptors */
1156 if (inode_has_security_descriptor(inode1)) {
1157 if (inode_has_security_descriptor(inode2)) {
1158 const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1159 const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1160 size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1161 size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1163 if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1164 ERROR("Security descriptor of %"TS" differs!",
1165 inode_any_full_path(inode1));
1166 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1168 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1169 ERROR("%"TS" has a security descriptor in the first image but "
1170 "not in the second image!", inode_any_full_path(inode1));
1171 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1173 } else if (inode_has_security_descriptor(inode2)) {
1174 /* okay --- consider it acceptable if a default security
1175 * descriptor was assigned */
1176 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1177 /*"not in the first image!", inode_any_full_path(inode1));*/
1178 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1181 /* Compare streams */
1182 for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1183 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1184 const struct wim_inode_stream *strm2;
1186 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1187 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1188 !inode_is_symlink(inode1)))
1191 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1194 /* Get the corresponding stream from the second file */
1195 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1198 /* Corresponding stream not found */
1199 if (stream_is_named(strm1) &&
1200 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1202 ERROR("Stream of %"TS" is missing in second image; "
1203 "type %d, named=%d, empty=%d",
1204 inode_any_full_path(inode1),
1206 stream_is_named(strm1),
1207 is_zero_hash(stream_hash(strm1)));
1208 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1211 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1212 ERROR("Stream of %"TS" differs; type %d",
1213 inode_any_full_path(inode1), strm1->stream_type);
1214 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1218 /* Compare object IDs */
1219 ret = cmp_object_ids(inode1, inode2, cmp_flags);
1227 cmp_images(const struct wim_image_metadata *imd1,
1228 const struct wim_image_metadata *imd2, int cmp_flags)
1230 struct wim_dentry *root1 = imd1->root_dentry;
1231 struct wim_dentry *root2 = imd2->root_dentry;
1232 const struct wim_inode *inode;
1235 ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1239 /* Verify that the hard links match up between the two images. */
1240 assert_inodes_sane(imd1);
1241 assert_inodes_sane(imd2);
1242 ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1246 /* Compare corresponding inodes. */
1247 image_for_each_inode(inode, imd1) {
1248 ret = cmp_inodes(inode, inode->i_corresponding,
1249 imd1, imd2, cmp_flags);
1258 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1260 int ret = select_wim_image(wim, image);
1262 *imd_ret = wim_get_current_image_metadata(wim);
1263 mark_image_dirty(*imd_ret);
1269 wimlib_compare_images(WIMStruct *wim1, int image1,
1270 WIMStruct *wim2, int image2, int cmp_flags)
1273 struct wim_image_metadata *imd1, *imd2;
1275 ret = load_image(wim1, image1, &imd1);
1277 ret = load_image(wim2, image2, &imd2);
1279 ret = cmp_images(imd1, imd2, cmp_flags);
1283 #endif /* ENABLE_TEST_SUPPORT */