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 /* TODO: why doesn't Windows accept these characters? */
551 /*128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141,*/
552 /*142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155,*/
553 /*156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169,*/
554 /*170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183,*/
555 /*184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197,*/
556 /*198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211,*/
557 /*212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225,*/
558 /*226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,*/
559 /*240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253,*/
564 generate_short_name_component(utf16lechar p[], int len)
566 for (int i = 0; i < len; i++) {
567 char c = valid_short_name_chars[rand32() %
568 ARRAY_LEN(valid_short_name_chars)];
569 p[i] = cpu_to_le16(c);
571 #if 0 /* TODO: we aren't using space yet anyway */
572 while (len > 1 && p[len - 1] == cpu_to_le16(' '))
574 if (p[len - 1] == cpu_to_le16(' '))
575 p[len - 1] = cpu_to_le16('A');
580 /* Generate a random short (8.3) filename and return its length.
581 * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
583 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
586 * Legal short names on Windows consist of 1 to 8 characters, optionally
587 * followed by a dot then 1 to 3 more characters. Only certain
588 * characters are allowed. In addition, trailing spaces are not
591 int base_len = 1 + (rand32() % 8);
592 int ext_len = rand32() % 4;
595 base_len = generate_short_name_component(name, base_len);
598 name[base_len] = cpu_to_le16('.');
599 ext_len = generate_short_name_component(&name[base_len + 1],
601 total_len = base_len + 1 + ext_len;
603 total_len = base_len;
605 name[total_len] = cpu_to_le16('\0');
610 select_inode_number(struct generation_context *ctx)
612 const struct wim_inode_table *table = ctx->params->inode_table;
613 const struct hlist_head *head;
614 const struct wim_inode *inode;
616 head = &table->array[rand32() % table->capacity];
617 hlist_for_each_entry(inode, head, i_hlist_node)
625 select_num_children(u32 depth, struct generation_context *ctx)
627 const double b = 1.01230;
628 u32 r = rand32() % 500;
629 return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
630 (2 - exp(0.04/depth));
634 is_name_valid_in_win32_namespace(const utf16lechar *name)
636 const utf16lechar *p;
638 static const utf16lechar forbidden_names[][5] = {
639 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('N'), },
640 { cpu_to_le16('P'), cpu_to_le16('R'), cpu_to_le16('N'), },
641 { cpu_to_le16('A'), cpu_to_le16('U'), cpu_to_le16('X'), },
642 { cpu_to_le16('N'), cpu_to_le16('U'), cpu_to_le16('L'), },
643 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('1'), },
644 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('2'), },
645 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('3'), },
646 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('4'), },
647 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('5'), },
648 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('6'), },
649 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('7'), },
650 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('8'), },
651 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('9'), },
652 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('1'), },
653 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('2'), },
654 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('3'), },
655 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('4'), },
656 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('5'), },
657 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('6'), },
658 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('7'), },
659 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('8'), },
660 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('9'), },
663 /* The name must be nonempty. */
667 /* All characters must be valid on Windows. */
668 for (p = name; *p; p++)
669 if (!is_valid_windows_filename_char(*p))
672 /* There can't be a trailing dot or space. */
673 if (p[-1] == cpu_to_le16('.') || p[-1] == cpu_to_le16(' '))
676 /* The name can't be one of the reserved names (case insensitively). */
677 for (size_t i = 0; i < ARRAY_LEN(forbidden_names); i++)
678 if (!cmp_utf16le_strings_z(forbidden_names[i], name, true))
685 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
686 struct generation_context *ctx)
688 utf16lechar name[12 + 1];
691 struct wim_dentry **bucket;
693 /* If the long name is not allowed in the Win32 namespace, then it
694 * cannot be assigned a corresponding short name. */
695 if (!is_name_valid_in_win32_namespace(child->d_name))
699 /* Don't select a short name that is already used by a long name within
700 * the same directory. */
702 name_len = generate_random_short_name(name, ctx);
703 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
704 WIMLIB_CASE_INSENSITIVE));
707 /* Don't select a short name that is already used by another short name
708 * within the same directory. */
710 for (const utf16lechar *p = name; *p; p++)
711 hash = (hash * 31) + *p;
712 FREE(child->d_short_name);
713 child->d_short_name = memdup(name, (name_len + 1) * 2);
714 child->d_short_name_nbytes = name_len * 2;
716 if (!child->d_short_name)
717 return WIMLIB_ERR_NOMEM;
719 bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
721 for (struct wim_dentry *d = *bucket; d != NULL;
722 d = d->d_next_extraction_alias) {
723 if (!cmp_utf16le_strings(child->d_short_name, name_len,
724 d->d_short_name, d->d_short_name_nbytes / 2,
730 if (!is_name_valid_in_win32_namespace(child->d_short_name))
733 child->d_next_extraction_alias = *bucket;
739 inode_has_short_name(const struct wim_inode *inode)
741 const struct wim_dentry *dentry;
743 inode_for_each_dentry(dentry, inode)
744 if (dentry_has_short_name(dentry))
751 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
752 struct generation_context *ctx)
754 u32 num_children = select_num_children(depth, ctx);
755 struct wim_dentry *child;
758 memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
760 /* Generate 'num_children' dentries within 'dir'. Some may be
761 * directories themselves. */
763 for (u32 i = 0; i < num_children; i++) {
765 /* Generate the next child dentry. */
766 struct wim_inode *inode;
769 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
771 struct wim_dentry *duplicate;
773 /* Decide whether to create a directory or not. If not a
774 * directory, also decide on the inode number (i.e. we may
775 * generate a "hard link" to an existing file). */
776 is_directory = ((rand32() % 16) <= 6);
780 ino = select_inode_number(ctx);
782 /* Create the dentry. */
783 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
784 ino, 0, is_directory, &child);
788 /* Choose a filename that is unique within the directory.*/
790 name_len = generate_random_filename(name,
793 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
794 WIMLIB_CASE_PLATFORM_DEFAULT));
796 ret = dentry_set_name_utf16le(child, name, name_len * 2);
802 /* Add the dentry to the directory. */
803 duplicate = dentry_add_child(dir, child);
804 wimlib_assert(!duplicate);
806 inode = child->d_inode;
808 if (inode->i_nlink > 1) /* Existing inode? */
811 /* New inode; set attributes, metadata, and data. */
814 inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
816 ret = set_random_metadata(inode, ctx);
820 ret = set_random_streams(inode, ctx, true);
824 /* Recurse if it's a directory. */
826 !(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT))
828 ret = generate_dentry_tree_recursive(child, depth + 1,
835 for_dentry_child(child, dir) {
836 /* sometimes generate a unique short name */
837 if (randbool() && !inode_has_short_name(child->d_inode)) {
838 ret = set_random_short_name(dir, child, ctx);
848 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
849 struct scan_params *params)
852 struct wim_dentry *root = NULL;
853 struct generation_context ctx = {
857 ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only */
859 ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
861 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
862 ret = set_random_metadata(root->d_inode, &ctx);
865 ret = set_random_streams(root->d_inode, &ctx, false);
867 ret = generate_dentry_tree_recursive(root, 1, &ctx);
871 free_dentry_tree(root, params->blob_table);
875 /*----------------------------------------------------------------------------*
876 * File tree comparison *
877 *----------------------------------------------------------------------------*/
879 #define INDEX_NODE_TO_DENTRY(node) \
880 ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
882 static struct wim_dentry *
883 dentry_first_child(struct wim_dentry *dentry)
885 return INDEX_NODE_TO_DENTRY(
886 avl_tree_first_in_order(dentry->d_inode->i_children));
889 static struct wim_dentry *
890 dentry_next_sibling(struct wim_dentry *dentry)
892 return INDEX_NODE_TO_DENTRY(
893 avl_tree_next_in_order(&dentry->d_index_node));
897 * Verify that the dentries in the tree 'd1' exactly match the dentries in the
898 * tree 'd2', considering long and short filenames. In addition, set
899 * 'd_corresponding' of each dentry to point to the corresponding dentry in the
900 * other tree, and set 'i_corresponding' of each inode to point to the
901 * unverified corresponding inode in the other tree.
904 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
907 struct wim_dentry *child1;
908 struct wim_dentry *child2;
911 /* Compare long filenames, case sensitively. */
912 if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
913 d2->d_name, d2->d_name_nbytes / 2,
916 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
917 dentry_full_path(d1), dentry_full_path(d2));
918 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
921 /* Compare short filenames, case insensitively. */
922 if (!(d2->d_short_name_nbytes == 0 &&
923 (cmp_flags & WIMLIB_CMP_FLAG_SHORT_NAMES_NOT_PRESERVED)) &&
924 cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
925 d2->d_short_name, d2->d_short_name_nbytes / 2,
928 ERROR("Short name mismatch; path=\"%"TS"\"",
929 dentry_full_path(d1));
930 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
933 /* Match up the dentries */
934 d1->d_corresponding = d2;
935 d2->d_corresponding = d1;
937 /* Match up the inodes (may overwrite previous value) */
938 d1->d_inode->i_corresponding = d2->d_inode;
939 d2->d_inode->i_corresponding = d1->d_inode;
941 /* Process children */
942 child1 = dentry_first_child(d1);
943 child2 = dentry_first_child(d2);
944 while (child1 || child2) {
946 if (!child1 || !child2) {
947 ERROR("Child count mismatch; "
948 "path1=\"%"TS"\", path2=\"%"TS"\"",
949 dentry_full_path(d1), dentry_full_path(d2));
950 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
953 /* Recurse on this pair of children. */
954 ret = calc_corresponding_files_recursive(child1, child2,
959 /* Continue to the next pair of children. */
960 child1 = dentry_next_sibling(child1);
961 child2 = dentry_next_sibling(child2);
966 /* Perform sanity checks on an image's inodes. All assertions here should pass,
967 * even if the images being compared are different. */
969 assert_inodes_sane(const struct wim_image_metadata *imd)
971 const struct wim_inode *inode;
972 const struct wim_dentry *dentry;
975 image_for_each_inode(inode, imd) {
977 inode_for_each_dentry(dentry, inode) {
978 wimlib_assert(dentry->d_inode == inode);
981 wimlib_assert(link_count > 0);
982 wimlib_assert(link_count == inode->i_nlink);
983 wimlib_assert(inode->i_corresponding != NULL);
988 check_hard_link(struct wim_dentry *dentry, void *_ignore)
990 /* My inode is my corresponding dentry's inode's corresponding inode,
991 * and my inode's corresponding inode is my corresponding dentry's
993 const struct wim_inode *a = dentry->d_inode;
994 const struct wim_inode *b = dentry->d_corresponding->d_inode;
995 if (a == b->i_corresponding && a->i_corresponding == b)
997 ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
998 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1002 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1003 const struct wim_image_metadata *imd1,
1004 const struct wim_image_metadata *imd2, int cmp_flags)
1006 const u32 attrib_diff = inode1->i_attributes ^ inode2->i_attributes;
1007 bool reparse_point_should_preserved = true;
1009 /* Compare attributes */
1010 if (cmp_flags & WIMLIB_CMP_FLAG_ATTRIBUTES_NOT_PRESERVED) {
1012 /* In this mode, we expect that most attributes are not
1013 * preserved. However, FILE_ATTRIBUTE_DIRECTORY should always
1015 if (attrib_diff & FILE_ATTRIBUTE_DIRECTORY)
1016 goto attrib_mismatch;
1018 /* We may also expect FILE_ATTRIBUTE_REPARSE_POINT to be
1019 * preserved for symlinks. It also shouldn't be set if it
1020 * wasn't set before. */
1022 if ((cmp_flags & WIMLIB_CMP_FLAG_IMAGE2_SHOULD_HAVE_SYMLINKS) &&
1023 inode_is_symlink(inode1))
1024 reparse_point_should_preserved = true;
1026 reparse_point_should_preserved = false;
1028 if ((attrib_diff & FILE_ATTRIBUTE_REPARSE_POINT) &&
1029 (reparse_point_should_preserved ||
1030 (inode2->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)))
1031 goto attrib_mismatch;
1034 /* Most attributes should be preserved. */
1036 /* Nothing other than COMPRESSED and NORMAL should have changed.
1038 if (attrib_diff & ~(FILE_ATTRIBUTE_COMPRESSED |
1039 FILE_ATTRIBUTE_NORMAL))
1040 goto attrib_mismatch;
1042 /* COMPRESSED shouldn't have changed unless specifically
1044 if ((attrib_diff & FILE_ATTRIBUTE_COMPRESSED) &&
1045 !(cmp_flags & WIMLIB_CMP_FLAG_COMPRESSION_NOT_PRESERVED))
1046 goto attrib_mismatch;
1048 /* We allow NORMAL to change, but not if the file ended up with
1049 * other attributes set as well. */
1050 if ((attrib_diff & FILE_ATTRIBUTE_NORMAL) &&
1051 (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1052 goto attrib_mismatch;
1055 /* Compare security descriptors */
1056 if (inode_has_security_descriptor(inode1)) {
1057 if (inode_has_security_descriptor(inode2)) {
1058 const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1059 const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1060 size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1061 size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1063 if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1064 ERROR("Security descriptor of %"TS" differs!",
1065 inode_any_full_path(inode1));
1066 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1068 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_SECURITY_NOT_PRESERVED)) {
1069 ERROR("%"TS" has a security descriptor in the first image but "
1070 "not in the second image!", inode_any_full_path(inode1));
1071 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1073 } else if (inode_has_security_descriptor(inode2)) {
1074 /* okay --- consider it acceptable if a default security
1075 * descriptor was assigned */
1076 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1077 /*"not in the first image!", inode_any_full_path(inode1));*/
1078 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1081 /* Compare streams */
1082 for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1083 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1084 const struct wim_inode_stream *strm2;
1086 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1087 !reparse_point_should_preserved)
1090 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1093 /* Get the corresponding stream from the second file */
1094 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1097 /* Corresponding stream not found */
1098 if (stream_is_named(strm1) &&
1099 (cmp_flags & WIMLIB_CMP_FLAG_ADS_NOT_PRESERVED))
1101 ERROR("Stream of %"TS" is missing in second image; "
1102 "type %d, named=%d, empty=%d",
1103 inode_any_full_path(inode1),
1105 stream_is_named(strm1),
1106 is_zero_hash(stream_hash(strm1)));
1107 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1110 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1111 ERROR("Stream of %"TS" differs; type %d",
1112 inode_any_full_path(inode1), strm1->stream_type);
1113 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1120 ERROR("Attribute mismatch; %"TS" has attributes 0x%08"PRIx32" "
1121 "in first image but attributes 0x%08"PRIx32" in second image",
1122 inode_any_full_path(inode1), inode1->i_attributes,
1123 inode2->i_attributes);
1124 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1128 cmp_images(const struct wim_image_metadata *imd1,
1129 const struct wim_image_metadata *imd2, int cmp_flags)
1131 struct wim_dentry *root1 = imd1->root_dentry;
1132 struct wim_dentry *root2 = imd2->root_dentry;
1133 const struct wim_inode *inode;
1136 ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1140 /* Verify that the hard links match up between the two images. */
1141 assert_inodes_sane(imd1);
1142 assert_inodes_sane(imd2);
1143 ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1147 /* Compare corresponding inodes. */
1148 image_for_each_inode(inode, imd1) {
1149 ret = cmp_inodes(inode, inode->i_corresponding,
1150 imd1, imd2, cmp_flags);
1159 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1161 int ret = select_wim_image(wim, image);
1163 *imd_ret = wim_get_current_image_metadata(wim);
1164 mark_image_dirty(*imd_ret);
1170 wimlib_compare_images(WIMStruct *wim1, int image1,
1171 WIMStruct *wim2, int image2, int cmp_flags)
1174 struct wim_image_metadata *imd1, *imd2;
1176 ret = load_image(wim1, image1, &imd1);
1178 ret = load_image(wim2, image2, &imd2);
1180 ret = cmp_images(imd1, imd2, cmp_flags);
1184 #endif /* ENABLE_TEST_SUPPORT */