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/reparse.h"
46 #include "wimlib/scan.h"
47 #include "wimlib/security_descriptor.h"
48 #include "wimlib/test_support.h"
50 /*----------------------------------------------------------------------------*
51 * File tree generation *
52 *----------------------------------------------------------------------------*/
54 struct generation_context {
55 struct scan_params *params;
56 struct wim_dentry *used_short_names[256];
63 static u64 state = 0x55DB93D0AB838771;
65 /* A simple linear congruential generator */
66 state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
73 return (rand32() & 1) != 0;
91 return ((u64)rand32() << 32) | rand32();
95 generate_random_timestamp(void)
97 /* When setting timestamps on Windows:
98 * - 0 is a special value meaning "not specified"
99 * - if the high bit is set you get STATUS_INVALID_PARAMETER */
100 return (1 + rand64()) & ~(1ULL << 63);
103 static const struct {
104 u8 num_subauthorities;
105 u64 identifier_authority;
106 u32 subauthorities[6];
108 { 1, 0, {0}}, /* NULL_SID */
109 { 1, 1, {0}}, /* WORLD_SID */
110 { 1, 2, {0}}, /* LOCAL_SID */
111 { 1, 3, {0}}, /* CREATOR_OWNER_SID */
112 { 1, 3, {1}}, /* CREATOR_GROUP_SID */
113 { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
114 { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
115 // { 0, 5, {}}, /* NT_AUTHORITY_SID */
116 { 1, 5, {1}}, /* DIALUP_SID */
117 { 1, 5, {2}}, /* NETWORK_SID */
118 { 1, 5, {3}}, /* BATCH_SID */
119 { 1, 5, {4}}, /* INTERACTIVE_SID */
120 { 1, 5, {6}}, /* SERVICE_SID */
121 { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
122 { 1, 5, {8}}, /* PROXY_SID */
123 { 1, 5, {9}}, /* SERVER_LOGON_SID */
124 { 1, 5, {10}}, /* SELF_SID */
125 { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
126 { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
127 { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
128 { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
129 { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
130 { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
131 { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer */
132 { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS */
135 /* Generate a SID and return its size in bytes. */
137 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
145 r = (r >> 1) % ARRAY_LEN(common_sids);
147 sid->sub_authority_count = common_sids[r].num_subauthorities;
148 for (int i = 0; i < 6; i++) {
149 sid->identifier_authority[i] =
150 common_sids[r].identifier_authority >> (40 - i * 8);
152 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
153 sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
157 sid->sub_authority_count = 1 + ((r >> 1) % 15);
159 for (int i = 0; i < 6; i++)
160 sid->identifier_authority[i] = rand8();
162 for (int i = 0; i < sid->sub_authority_count; i++)
163 sid->sub_authority[i] = cpu_to_le32(rand32());
165 return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
168 /* Generate an ACL and return its size in bytes. */
170 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
175 ace_count = rand32() % 16;
179 acl->ace_count = cpu_to_le16(ace_count);
184 for (int i = 0; i < ace_count; i++) {
185 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
187 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
190 ace->hdr.type = rand32() % 2;
193 ace->hdr.flags = rand8();
194 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
196 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
197 generate_random_sid(&ace->sid, ctx);
198 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
201 acl->acl_size = cpu_to_le16(p - (u8 *)acl);
202 return p - (u8 *)acl;
205 /* Generate a security descriptor and return its size in bytes. */
207 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
209 wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
215 control &= (wimlib_SE_DACL_AUTO_INHERITED |
216 wimlib_SE_SACL_AUTO_INHERITED);
218 control |= wimlib_SE_SELF_RELATIVE |
219 wimlib_SE_DACL_PRESENT |
220 wimlib_SE_SACL_PRESENT;
224 desc->control = cpu_to_le16(control);
226 p = (u8 *)(desc + 1);
228 desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
229 p += generate_random_sid((wimlib_SID *)p, ctx);
231 desc->group_offset = cpu_to_le32(p - (u8 *)desc);
232 p += generate_random_sid((wimlib_SID *)p, ctx);
234 if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
235 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
236 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
238 desc->dacl_offset = cpu_to_le32(0);
241 if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
242 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
243 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
245 desc->sacl_offset = cpu_to_le32(0);
248 return p - (u8 *)desc;
252 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
255 u32 attrib = (v & (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));
262 /* File attributes */
263 inode->i_attributes |= attrib;
266 inode->i_creation_time = generate_random_timestamp();
267 inode->i_last_access_time = generate_random_timestamp();
268 inode->i_last_write_time = generate_random_timestamp();
270 /* Security descriptor */
272 char desc[8192] _aligned_attribute(8);
275 size = generate_random_security_descriptor(desc, ctx);
277 wimlib_assert(size <= sizeof(desc));
279 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
281 if (unlikely(inode->i_security_id < 0))
282 return WIMLIB_ERR_NOMEM;
289 /* Choose a random size for generated file data. We want to usually generate
290 * empty, small, or medium files, but occasionally generate large files. */
292 select_stream_size(struct generation_context *ctx)
294 if (ctx->metadata_only)
297 switch (rand32() % 2048) {
303 return rand32() % 64;
306 return rand32() % 4096;
309 return rand32() % 32768;
312 return rand32() % 262144;
315 return rand32() % 134217728;
319 /* Fill 'buffer' with 'size' bytes of "interesting" file data. */
321 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
324 size_t num_byte_fills = rand32() % 256;
326 memset(buffer, rand32() % 256, size);
328 for (size_t i = 0; i < num_byte_fills; i++) {
331 size_t count = ((double)size / (double)num_byte_fills) *
332 ((double)rand32() / 2e9);
333 size_t offset = rand32() & ~mask;
337 ((rand32()) & mask)) % size] = b;
341 if (rand32() % 4 == 0)
342 mask = (size_t)-1 << rand32() % 4;
345 if (rand32() % 8 == 0) {
346 double magnitude = rand32() % 128;
347 double scale = 1.0 / (1 + (rand32() % 256));
349 for (size_t i = 0; i < size; i++)
350 buffer[i] += (int)(magnitude * cos(i * scale));
355 add_stream(struct wim_inode *inode, struct generation_context *ctx,
356 int stream_type, const utf16lechar *stream_name,
357 void *buffer, size_t size)
359 struct blob_descriptor *blob = NULL;
360 struct wim_inode_stream *strm;
363 blob = new_blob_descriptor();
366 blob->attached_buffer = buffer;
367 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
371 strm = inode_add_stream(inode, stream_type, stream_name, blob);
375 prepare_unhashed_blob(blob, inode, strm->stream_id,
376 ctx->params->unhashed_blobs);
380 free_blob_descriptor(blob);
381 return WIMLIB_ERR_NOMEM;
385 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
388 size_t rpdatalen = select_stream_size(ctx) % (REPARSE_DATA_MAX_SIZE + 1);
391 buffer = MALLOC(rpdatalen);
393 return WIMLIB_ERR_NOMEM;
394 generate_data(buffer, rpdatalen, ctx);
397 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
398 inode->i_rp_reserved = rand16();
400 if (rpdatalen >= GUID_SIZE && randbool()) {
401 /* Non-Microsoft reparse tag (16-byte GUID required) */
403 guid[6] = (guid[6] & 0x0F) | 0x40;
404 guid[8] = (guid[8] & 0x3F) | 0x80;
405 inode->i_reparse_tag = 0x00000100;
407 /* Microsoft reparse tag */
408 inode->i_reparse_tag = 0x80000000;
411 return add_stream(inode, ctx, STREAM_TYPE_REPARSE_POINT, NO_STREAM_NAME,
416 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
417 const utf16lechar *stream_name)
422 size = select_stream_size(ctx);
424 buffer = MALLOC(size);
426 return WIMLIB_ERR_NOMEM;
427 generate_data(buffer, size, ctx);
430 return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
435 set_random_streams(struct wim_inode *inode, struct generation_context *ctx,
441 /* Reparse point (sometimes) */
442 if (reparse_ok && rand32() % 8 == 0) {
443 ret = set_random_reparse_point(inode, ctx);
448 /* Unnamed data stream (nondirectories only) */
449 if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)) {
450 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
455 /* Named data streams (sometimes) */
458 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
461 ret = add_random_data_stream(inode, ctx, stream_name);
464 stream_name[0] += cpu_to_le16(1);
472 is_valid_windows_filename_char(utf16lechar c)
474 return le16_to_cpu(c) > 31 &&
475 c != cpu_to_le16('/') &&
476 c != cpu_to_le16('<') &&
477 c != cpu_to_le16('>') &&
478 c != cpu_to_le16(':') &&
479 c != cpu_to_le16('"') &&
480 c != cpu_to_le16('/' ) &&
481 c != cpu_to_le16('\\') &&
482 c != cpu_to_le16('|') &&
483 c != cpu_to_le16('?') &&
484 c != cpu_to_le16('*');
487 /* Is the character valid in a filename on the current platform? */
489 is_valid_filename_char(utf16lechar c)
492 return is_valid_windows_filename_char(c);
494 return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
498 /* Generate a random filename and return its length. */
500 generate_random_filename(utf16lechar name[], int max_len,
501 struct generation_context *ctx)
505 /* Choose the length of the name. */
506 switch (rand32() % 8) {
509 len = 1 + (rand32() % 6);
514 /* medium-length name */
515 len = 7 + (rand32() % 8);
520 len = 15 + (rand32() % 15);
524 len = 30 + (rand32() % 90);
527 len = min(len, max_len);
529 /* Generate the characters in the name. */
530 for (int i = 0; i < len; i++) {
533 } while (!is_valid_filename_char(name[i]));
536 /* Add a null terminator. */
537 name[len] = cpu_to_le16('\0');
542 /* The set of characters which are valid in short filenames. */
543 static const char valid_short_name_chars[] = {
544 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
545 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
546 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
547 '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
549 /* Note: Windows does not allow space and 128-255 in short filenames
550 * (tested on both NTFS and FAT). */
554 generate_short_name_component(utf16lechar p[], int len)
556 for (int i = 0; i < len; i++) {
557 char c = valid_short_name_chars[rand32() %
558 ARRAY_LEN(valid_short_name_chars)];
559 p[i] = cpu_to_le16(c);
564 /* Generate a random short (8.3) filename and return its length.
565 * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
567 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
570 * Legal short names on Windows consist of 1 to 8 characters, optionally
571 * followed by a dot then 1 to 3 more characters. Only certain
572 * characters are allowed.
574 int base_len = 1 + (rand32() % 8);
575 int ext_len = rand32() % 4;
578 base_len = generate_short_name_component(name, base_len);
581 name[base_len] = cpu_to_le16('.');
582 ext_len = generate_short_name_component(&name[base_len + 1],
584 total_len = base_len + 1 + ext_len;
586 total_len = base_len;
588 name[total_len] = cpu_to_le16('\0');
593 select_inode_number(struct generation_context *ctx)
595 const struct wim_inode_table *table = ctx->params->inode_table;
596 const struct hlist_head *head;
597 const struct wim_inode *inode;
599 head = &table->array[rand32() % table->capacity];
600 hlist_for_each_entry(inode, head, i_hlist_node)
608 select_num_children(u32 depth, struct generation_context *ctx)
610 const double b = 1.01230;
611 u32 r = rand32() % 500;
612 return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
613 (2 - exp(0.04/depth));
617 is_name_valid_in_win32_namespace(const utf16lechar *name)
619 const utf16lechar *p;
621 static const utf16lechar forbidden_names[][5] = {
622 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('N'), },
623 { cpu_to_le16('P'), cpu_to_le16('R'), cpu_to_le16('N'), },
624 { cpu_to_le16('A'), cpu_to_le16('U'), cpu_to_le16('X'), },
625 { cpu_to_le16('N'), cpu_to_le16('U'), cpu_to_le16('L'), },
626 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('1'), },
627 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('2'), },
628 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('3'), },
629 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('4'), },
630 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('5'), },
631 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('6'), },
632 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('7'), },
633 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('8'), },
634 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('9'), },
635 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('1'), },
636 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('2'), },
637 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('3'), },
638 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('4'), },
639 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('5'), },
640 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('6'), },
641 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('7'), },
642 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('8'), },
643 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('9'), },
646 /* The name must be nonempty. */
650 /* All characters must be valid on Windows. */
651 for (p = name; *p; p++)
652 if (!is_valid_windows_filename_char(*p))
655 /* Note: a trailing dot or space is permitted, even though on Windows
656 * such a file can only be accessed using a WinNT-style path. */
658 /* The name can't be one of the reserved names (case insensitively). */
659 for (size_t i = 0; i < ARRAY_LEN(forbidden_names); i++)
660 if (!cmp_utf16le_strings_z(forbidden_names[i], name, true))
667 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
668 struct generation_context *ctx)
670 utf16lechar name[12 + 1];
673 struct wim_dentry **bucket;
675 /* If the long name is not allowed in the Win32 namespace, then it
676 * cannot be assigned a corresponding short name. */
677 if (!is_name_valid_in_win32_namespace(child->d_name))
681 /* Don't select a short name that is already used by a long name within
682 * the same directory. */
684 name_len = generate_random_short_name(name, ctx);
685 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
686 WIMLIB_CASE_INSENSITIVE));
689 /* Don't select a short name that is already used by another short name
690 * within the same directory. */
692 for (const utf16lechar *p = name; *p; p++)
693 hash = (hash * 31) + *p;
694 FREE(child->d_short_name);
695 child->d_short_name = memdup(name, (name_len + 1) * 2);
696 child->d_short_name_nbytes = name_len * 2;
698 if (!child->d_short_name)
699 return WIMLIB_ERR_NOMEM;
701 bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
703 for (struct wim_dentry *d = *bucket; d != NULL;
704 d = d->d_next_extraction_alias) {
705 if (!cmp_utf16le_strings(child->d_short_name, name_len,
706 d->d_short_name, d->d_short_name_nbytes / 2,
712 if (!is_name_valid_in_win32_namespace(child->d_short_name))
715 child->d_next_extraction_alias = *bucket;
721 inode_has_short_name(const struct wim_inode *inode)
723 const struct wim_dentry *dentry;
725 inode_for_each_dentry(dentry, inode)
726 if (dentry_has_short_name(dentry))
733 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
734 struct generation_context *ctx)
736 u32 num_children = select_num_children(depth, ctx);
737 struct wim_dentry *child;
740 memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
742 /* Generate 'num_children' dentries within 'dir'. Some may be
743 * directories themselves. */
745 for (u32 i = 0; i < num_children; i++) {
747 /* Generate the next child dentry. */
748 struct wim_inode *inode;
751 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
753 struct wim_dentry *duplicate;
755 /* Decide whether to create a directory or not. If not a
756 * directory, also decide on the inode number (i.e. we may
757 * generate a "hard link" to an existing file). */
758 is_directory = ((rand32() % 16) <= 6);
762 ino = select_inode_number(ctx);
764 /* Create the dentry. */
765 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
766 ino, 0, is_directory, &child);
770 /* Choose a filename that is unique within the directory.*/
772 name_len = generate_random_filename(name,
775 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
776 WIMLIB_CASE_PLATFORM_DEFAULT));
778 ret = dentry_set_name_utf16le(child, name, name_len * 2);
784 /* Add the dentry to the directory. */
785 duplicate = dentry_add_child(dir, child);
786 wimlib_assert(!duplicate);
788 inode = child->d_inode;
790 if (inode->i_nlink > 1) /* Existing inode? */
793 /* New inode; set attributes, metadata, and data. */
796 inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
798 ret = set_random_metadata(inode, ctx);
802 ret = set_random_streams(inode, ctx, true);
806 /* Recurse if it's a directory. */
808 !(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT))
810 ret = generate_dentry_tree_recursive(child, depth + 1,
817 for_dentry_child(child, dir) {
818 /* sometimes generate a unique short name */
819 if (randbool() && !inode_has_short_name(child->d_inode)) {
820 ret = set_random_short_name(dir, child, ctx);
830 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
831 struct scan_params *params)
834 struct wim_dentry *root = NULL;
835 struct generation_context ctx = {
839 ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only */
841 ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
843 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
844 ret = set_random_metadata(root->d_inode, &ctx);
847 ret = set_random_streams(root->d_inode, &ctx, false);
849 ret = generate_dentry_tree_recursive(root, 1, &ctx);
853 free_dentry_tree(root, params->blob_table);
857 /*----------------------------------------------------------------------------*
858 * File tree comparison *
859 *----------------------------------------------------------------------------*/
861 #define INDEX_NODE_TO_DENTRY(node) \
862 ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
864 static struct wim_dentry *
865 dentry_first_child(struct wim_dentry *dentry)
867 return INDEX_NODE_TO_DENTRY(
868 avl_tree_first_in_order(dentry->d_inode->i_children));
871 static struct wim_dentry *
872 dentry_next_sibling(struct wim_dentry *dentry)
874 return INDEX_NODE_TO_DENTRY(
875 avl_tree_next_in_order(&dentry->d_index_node));
879 * Verify that the dentries in the tree 'd1' exactly match the dentries in the
880 * tree 'd2', considering long and short filenames. In addition, set
881 * 'd_corresponding' of each dentry to point to the corresponding dentry in the
882 * other tree, and set 'i_corresponding' of each inode to point to the
883 * unverified corresponding inode in the other tree.
886 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
889 struct wim_dentry *child1;
890 struct wim_dentry *child2;
893 /* Compare long filenames, case sensitively. */
894 if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
895 d2->d_name, d2->d_name_nbytes / 2,
898 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
899 dentry_full_path(d1), dentry_full_path(d2));
900 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
903 /* Compare short filenames, case insensitively. */
904 if (!(d2->d_short_name_nbytes == 0 &&
905 (cmp_flags & WIMLIB_CMP_FLAG_SHORT_NAMES_NOT_PRESERVED)) &&
906 cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
907 d2->d_short_name, d2->d_short_name_nbytes / 2,
910 ERROR("Short name mismatch; path=\"%"TS"\"",
911 dentry_full_path(d1));
912 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
915 /* Match up the dentries */
916 d1->d_corresponding = d2;
917 d2->d_corresponding = d1;
919 /* Match up the inodes (may overwrite previous value) */
920 d1->d_inode->i_corresponding = d2->d_inode;
921 d2->d_inode->i_corresponding = d1->d_inode;
923 /* Process children */
924 child1 = dentry_first_child(d1);
925 child2 = dentry_first_child(d2);
926 while (child1 || child2) {
928 if (!child1 || !child2) {
929 ERROR("Child count mismatch; "
930 "path1=\"%"TS"\", path2=\"%"TS"\"",
931 dentry_full_path(d1), dentry_full_path(d2));
932 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
935 /* Recurse on this pair of children. */
936 ret = calc_corresponding_files_recursive(child1, child2,
941 /* Continue to the next pair of children. */
942 child1 = dentry_next_sibling(child1);
943 child2 = dentry_next_sibling(child2);
948 /* Perform sanity checks on an image's inodes. All assertions here should pass,
949 * even if the images being compared are different. */
951 assert_inodes_sane(const struct wim_image_metadata *imd)
953 const struct wim_inode *inode;
954 const struct wim_dentry *dentry;
957 image_for_each_inode(inode, imd) {
959 inode_for_each_dentry(dentry, inode) {
960 wimlib_assert(dentry->d_inode == inode);
963 wimlib_assert(link_count > 0);
964 wimlib_assert(link_count == inode->i_nlink);
965 wimlib_assert(inode->i_corresponding != NULL);
970 check_hard_link(struct wim_dentry *dentry, void *_ignore)
972 /* My inode is my corresponding dentry's inode's corresponding inode,
973 * and my inode's corresponding inode is my corresponding dentry's
975 const struct wim_inode *a = dentry->d_inode;
976 const struct wim_inode *b = dentry->d_corresponding->d_inode;
977 if (a == b->i_corresponding && a->i_corresponding == b)
979 ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
980 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
984 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
985 const struct wim_image_metadata *imd1,
986 const struct wim_image_metadata *imd2, int cmp_flags)
988 const u32 attrib_diff = inode1->i_attributes ^ inode2->i_attributes;
989 bool reparse_point_should_preserved = true;
991 /* Compare attributes */
992 if (cmp_flags & WIMLIB_CMP_FLAG_ATTRIBUTES_NOT_PRESERVED) {
994 /* In this mode, we expect that most attributes are not
995 * preserved. However, FILE_ATTRIBUTE_DIRECTORY should always
997 if (attrib_diff & FILE_ATTRIBUTE_DIRECTORY)
998 goto attrib_mismatch;
1000 /* We may also expect FILE_ATTRIBUTE_REPARSE_POINT to be
1001 * preserved for symlinks. It also shouldn't be set if it
1002 * wasn't set before. */
1004 if ((cmp_flags & WIMLIB_CMP_FLAG_IMAGE2_SHOULD_HAVE_SYMLINKS) &&
1005 inode_is_symlink(inode1))
1006 reparse_point_should_preserved = true;
1008 reparse_point_should_preserved = false;
1010 if ((attrib_diff & FILE_ATTRIBUTE_REPARSE_POINT) &&
1011 (reparse_point_should_preserved ||
1012 (inode2->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)))
1013 goto attrib_mismatch;
1016 /* Most attributes should be preserved. */
1018 /* Nothing other than COMPRESSED and NORMAL should have changed.
1020 if (attrib_diff & ~(FILE_ATTRIBUTE_COMPRESSED |
1021 FILE_ATTRIBUTE_NORMAL))
1022 goto attrib_mismatch;
1024 /* COMPRESSED shouldn't have changed unless specifically
1026 if ((attrib_diff & FILE_ATTRIBUTE_COMPRESSED) &&
1027 !(cmp_flags & WIMLIB_CMP_FLAG_COMPRESSION_NOT_PRESERVED))
1028 goto attrib_mismatch;
1030 /* We allow NORMAL to change, but not if the file ended up with
1031 * other attributes set as well. */
1032 if ((attrib_diff & FILE_ATTRIBUTE_NORMAL) &&
1033 (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1034 goto attrib_mismatch;
1037 /* Compare security descriptors */
1038 if (inode_has_security_descriptor(inode1)) {
1039 if (inode_has_security_descriptor(inode2)) {
1040 const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1041 const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1042 size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1043 size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1045 if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1046 ERROR("Security descriptor of %"TS" differs!",
1047 inode_any_full_path(inode1));
1048 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1050 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_SECURITY_NOT_PRESERVED)) {
1051 ERROR("%"TS" has a security descriptor in the first image but "
1052 "not in the second image!", inode_any_full_path(inode1));
1053 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1055 } else if (inode_has_security_descriptor(inode2)) {
1056 /* okay --- consider it acceptable if a default security
1057 * descriptor was assigned */
1058 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1059 /*"not in the first image!", inode_any_full_path(inode1));*/
1060 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1063 /* Compare streams */
1064 for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1065 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1066 const struct wim_inode_stream *strm2;
1068 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1069 !reparse_point_should_preserved)
1072 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1075 /* Get the corresponding stream from the second file */
1076 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1079 /* Corresponding stream not found */
1080 if (stream_is_named(strm1) &&
1081 (cmp_flags & WIMLIB_CMP_FLAG_ADS_NOT_PRESERVED))
1083 ERROR("Stream of %"TS" is missing in second image; "
1084 "type %d, named=%d, empty=%d",
1085 inode_any_full_path(inode1),
1087 stream_is_named(strm1),
1088 is_zero_hash(stream_hash(strm1)));
1089 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1092 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1093 ERROR("Stream of %"TS" differs; type %d",
1094 inode_any_full_path(inode1), strm1->stream_type);
1095 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1102 ERROR("Attribute mismatch; %"TS" has attributes 0x%08"PRIx32" "
1103 "in first image but attributes 0x%08"PRIx32" in second image",
1104 inode_any_full_path(inode1), inode1->i_attributes,
1105 inode2->i_attributes);
1106 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1110 cmp_images(const struct wim_image_metadata *imd1,
1111 const struct wim_image_metadata *imd2, int cmp_flags)
1113 struct wim_dentry *root1 = imd1->root_dentry;
1114 struct wim_dentry *root2 = imd2->root_dentry;
1115 const struct wim_inode *inode;
1118 ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1122 /* Verify that the hard links match up between the two images. */
1123 assert_inodes_sane(imd1);
1124 assert_inodes_sane(imd2);
1125 ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1129 /* Compare corresponding inodes. */
1130 image_for_each_inode(inode, imd1) {
1131 ret = cmp_inodes(inode, inode->i_corresponding,
1132 imd1, imd2, cmp_flags);
1141 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1143 int ret = select_wim_image(wim, image);
1145 *imd_ret = wim_get_current_image_metadata(wim);
1146 mark_image_dirty(*imd_ret);
1152 wimlib_compare_images(WIMStruct *wim1, int image1,
1153 WIMStruct *wim2, int image2, int cmp_flags)
1156 struct wim_image_metadata *imd1, *imd2;
1158 ret = load_image(wim1, image1, &imd1);
1160 ret = load_image(wim2, image2, &imd2);
1162 ret = cmp_images(imd1, imd2, cmp_flags);
1166 #endif /* ENABLE_TEST_SUPPORT */