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);
105 is_valid_windows_filename_char(utf16lechar c)
107 return le16_to_cpu(c) > 31 &&
108 c != cpu_to_le16('/') &&
109 c != cpu_to_le16('<') &&
110 c != cpu_to_le16('>') &&
111 c != cpu_to_le16(':') &&
112 c != cpu_to_le16('"') &&
113 c != cpu_to_le16('/' ) &&
114 c != cpu_to_le16('\\') &&
115 c != cpu_to_le16('|') &&
116 c != cpu_to_le16('?') &&
117 c != cpu_to_le16('*');
120 /* Is the character valid in a filename on the current platform? */
122 is_valid_filename_char(utf16lechar c)
125 return is_valid_windows_filename_char(c);
127 return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
131 /* Generate a random filename and return its length. */
133 generate_random_filename(utf16lechar name[], int max_len,
134 struct generation_context *ctx)
138 /* Choose the length of the name. */
139 switch (rand32() % 8) {
142 len = 1 + (rand32() % 6);
147 /* medium-length name */
148 len = 7 + (rand32() % 8);
153 len = 15 + (rand32() % 15);
157 len = 30 + (rand32() % 90);
160 len = min(len, max_len);
163 /* Generate the characters in the name. */
164 for (int i = 0; i < len; i++) {
167 } while (!is_valid_filename_char(name[i]));
170 /* Add a null terminator. */
171 name[len] = cpu_to_le16('\0');
173 /* Don't generate . and .. */
174 if (name[0] == cpu_to_le16('.') &&
175 (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
181 /* The set of characters which are valid in short filenames. */
182 static const char valid_short_name_chars[] = {
183 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
184 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
185 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
186 '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
188 /* Note: Windows does not allow space and 128-255 in short filenames
189 * (tested on both NTFS and FAT). */
193 generate_short_name_component(utf16lechar p[], int len)
195 for (int i = 0; i < len; i++) {
196 char c = valid_short_name_chars[rand32() %
197 ARRAY_LEN(valid_short_name_chars)];
198 p[i] = cpu_to_le16(c);
203 /* Generate a random short (8.3) filename and return its length.
204 * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
206 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
209 * Legal short names on Windows consist of 1 to 8 characters, optionally
210 * followed by a dot then 1 to 3 more characters. Only certain
211 * characters are allowed.
213 int base_len = 1 + (rand32() % 8);
214 int ext_len = rand32() % 4;
217 base_len = generate_short_name_component(name, base_len);
220 name[base_len] = cpu_to_le16('.');
221 ext_len = generate_short_name_component(&name[base_len + 1],
223 total_len = base_len + 1 + ext_len;
225 total_len = base_len;
227 name[total_len] = cpu_to_le16('\0');
232 static const struct {
233 u8 num_subauthorities;
234 u64 identifier_authority;
235 u32 subauthorities[6];
237 { 1, 0, {0}}, /* NULL_SID */
238 { 1, 1, {0}}, /* WORLD_SID */
239 { 1, 2, {0}}, /* LOCAL_SID */
240 { 1, 3, {0}}, /* CREATOR_OWNER_SID */
241 { 1, 3, {1}}, /* CREATOR_GROUP_SID */
242 { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
243 { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
244 // { 0, 5, {}}, /* NT_AUTHORITY_SID */
245 { 1, 5, {1}}, /* DIALUP_SID */
246 { 1, 5, {2}}, /* NETWORK_SID */
247 { 1, 5, {3}}, /* BATCH_SID */
248 { 1, 5, {4}}, /* INTERACTIVE_SID */
249 { 1, 5, {6}}, /* SERVICE_SID */
250 { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
251 { 1, 5, {8}}, /* PROXY_SID */
252 { 1, 5, {9}}, /* SERVER_LOGON_SID */
253 { 1, 5, {10}}, /* SELF_SID */
254 { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
255 { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
256 { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
257 { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
258 { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
259 { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
260 { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer */
261 { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS */
264 /* Generate a SID and return its size in bytes. */
266 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
274 r = (r >> 1) % ARRAY_LEN(common_sids);
276 sid->sub_authority_count = common_sids[r].num_subauthorities;
277 for (int i = 0; i < 6; i++) {
278 sid->identifier_authority[i] =
279 common_sids[r].identifier_authority >> (40 - i * 8);
281 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
282 sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
286 sid->sub_authority_count = 1 + ((r >> 1) % 15);
288 for (int i = 0; i < 6; i++)
289 sid->identifier_authority[i] = rand8();
291 for (int i = 0; i < sid->sub_authority_count; i++)
292 sid->sub_authority[i] = cpu_to_le32(rand32());
294 return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
297 /* Generate an ACL and return its size in bytes. */
299 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
304 ace_count = rand32() % 16;
308 acl->ace_count = cpu_to_le16(ace_count);
313 for (int i = 0; i < ace_count; i++) {
314 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
316 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
319 ace->hdr.type = rand32() % 2;
322 ace->hdr.flags = rand8();
323 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
325 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
326 generate_random_sid(&ace->sid, ctx);
327 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
330 acl->acl_size = cpu_to_le16(p - (u8 *)acl);
331 return p - (u8 *)acl;
334 /* Generate a security descriptor and return its size in bytes. */
336 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
338 wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
344 control &= (wimlib_SE_DACL_AUTO_INHERITED |
345 wimlib_SE_SACL_AUTO_INHERITED);
347 control |= wimlib_SE_SELF_RELATIVE |
348 wimlib_SE_DACL_PRESENT |
349 wimlib_SE_SACL_PRESENT;
353 desc->control = cpu_to_le16(control);
355 p = (u8 *)(desc + 1);
357 desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
358 p += generate_random_sid((wimlib_SID *)p, ctx);
360 desc->group_offset = cpu_to_le32(p - (u8 *)desc);
361 p += generate_random_sid((wimlib_SID *)p, ctx);
363 if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
364 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
365 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
367 desc->dacl_offset = cpu_to_le32(0);
370 if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
371 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
372 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
374 desc->sacl_offset = cpu_to_le32(0);
377 return p - (u8 *)desc;
381 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
383 u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
384 FILE_ATTRIBUTE_HIDDEN |
385 FILE_ATTRIBUTE_SYSTEM |
386 FILE_ATTRIBUTE_ARCHIVE |
387 FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
388 FILE_ATTRIBUTE_COMPRESSED |
389 FILE_ATTRIBUTE_SPARSE_FILE));
391 /* File attributes */
392 inode->i_attributes |= attrib;
395 inode->i_creation_time = generate_random_timestamp();
396 inode->i_last_access_time = generate_random_timestamp();
397 inode->i_last_write_time = generate_random_timestamp();
399 /* Security descriptor */
401 char desc[8192] _aligned_attribute(8);
404 size = generate_random_security_descriptor(desc, ctx);
406 wimlib_assert(size <= sizeof(desc));
408 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
410 if (unlikely(inode->i_security_id < 0))
411 return WIMLIB_ERR_NOMEM;
415 if (rand32() % 32 == 0) {
416 struct wimlib_object_id object_id;
418 for (int i = 0; i < sizeof(object_id); i++)
419 *((u8 *)&object_id + i) = rand8();
420 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
421 return WIMLIB_ERR_NOMEM;
428 /* Choose a random size for generated file data. We want to usually generate
429 * empty, small, or medium files, but occasionally generate large files. */
431 select_stream_size(struct generation_context *ctx)
433 if (ctx->metadata_only)
436 switch (rand32() % 2048) {
442 return rand32() % 64;
445 return rand32() % 4096;
448 return rand32() % 32768;
451 return rand32() % 262144;
454 return rand32() % 134217728;
458 /* Fill 'buffer' with 'size' bytes of "interesting" file data. */
460 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
463 size_t num_byte_fills = rand32() % 256;
468 /* Start by initializing to a random byte */
469 memset(buffer, rand32() % 256, size);
471 /* Add some random bytes in some random places */
472 for (size_t i = 0; i < num_byte_fills; i++) {
475 size_t count = ((double)size / (double)num_byte_fills) *
476 ((double)rand32() / 2e9);
477 size_t offset = rand32() & ~mask;
481 ((rand32()) & mask)) % size] = b;
485 if (rand32() % 4 == 0)
486 mask = (size_t)-1 << rand32() % 4;
489 /* Sometimes add a wave pattern */
490 if (rand32() % 8 == 0) {
491 double magnitude = rand32() % 128;
492 double scale = 1.0 / (1 + (rand32() % 256));
494 for (size_t i = 0; i < size; i++)
495 buffer[i] += (int)(magnitude * cos(i * scale));
498 /* Sometimes add some zero regions (holes) */
499 if (rand32() % 4 == 0) {
500 size_t num_holes = 1 + (rand32() % 16);
501 for (size_t i = 0; i < num_holes; i++) {
502 size_t hole_offset = rand32() % size;
503 size_t hole_len = min(size - hole_offset,
504 size / (1 + (rand32() % 16)));
505 memset(&buffer[hole_offset], 0, hole_len);
511 add_stream(struct wim_inode *inode, struct generation_context *ctx,
512 int stream_type, const utf16lechar *stream_name,
513 void *buffer, size_t size)
515 struct blob_descriptor *blob = NULL;
516 struct wim_inode_stream *strm;
519 blob = new_blob_descriptor();
522 blob->attached_buffer = buffer;
523 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
527 strm = inode_add_stream(inode, stream_type, stream_name, blob);
531 prepare_unhashed_blob(blob, inode, strm->stream_id,
532 ctx->params->unhashed_blobs);
536 free_blob_descriptor(blob);
537 return WIMLIB_ERR_NOMEM;
540 static noinline_for_stack int
541 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
543 struct reparse_buffer_disk rpbuf;
546 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
551 utf16lechar *targets = (utf16lechar *)rpbuf.link.symlink.data;
553 inode->i_reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
555 target_nchars = generate_random_filename(targets, 255, ctx);
557 rpbuf.link.substitute_name_offset = cpu_to_le16(0);
558 rpbuf.link.substitute_name_nbytes = cpu_to_le16(2*target_nchars);
559 rpbuf.link.print_name_offset = cpu_to_le16(2*(target_nchars + 1));
560 rpbuf.link.print_name_nbytes = cpu_to_le16(2*target_nchars);
561 targets[target_nchars] = cpu_to_le16(0);
562 memcpy(&targets[target_nchars + 1], targets, 2*target_nchars);
563 targets[target_nchars + 1 + target_nchars] = cpu_to_le16(0);
565 rpbuf.link.symlink.flags = cpu_to_le32(SYMBOLIC_LINK_RELATIVE);
566 rpdatalen = ((u8 *)targets - rpbuf.rpdata) +
567 2*(target_nchars + 1 + target_nchars + 1);
569 rpdatalen = select_stream_size(ctx) % REPARSE_DATA_MAX_SIZE;
570 generate_data(rpbuf.rpdata, rpdatalen, ctx);
572 if (rpdatalen >= GUID_SIZE && randbool()) {
573 /* Non-Microsoft reparse tag (16-byte GUID required) */
574 u8 *guid = rpbuf.rpdata;
575 guid[6] = (guid[6] & 0x0F) | 0x40;
576 guid[8] = (guid[8] & 0x3F) | 0x80;
577 inode->i_reparse_tag = 0x00000100;
579 /* Microsoft reparse tag */
580 inode->i_reparse_tag = 0x80000000;
582 inode->i_rp_reserved = rand16();
585 wimlib_assert(rpdatalen < REPARSE_DATA_MAX_SIZE);
587 if (!inode_add_stream_with_data(inode, STREAM_TYPE_REPARSE_POINT,
588 NO_STREAM_NAME, rpbuf.rpdata,
589 rpdatalen, ctx->params->blob_table))
590 return WIMLIB_ERR_NOMEM;
596 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
597 const utf16lechar *stream_name)
602 size = select_stream_size(ctx);
604 buffer = MALLOC(size);
606 return WIMLIB_ERR_NOMEM;
607 generate_data(buffer, size, ctx);
610 return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
615 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
620 /* Reparse point (sometimes) */
621 if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
622 ret = set_random_reparse_point(inode, ctx);
627 /* Unnamed data stream (nondirectories and non-symlinks only) */
628 if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) &&
629 !inode_is_symlink(inode)) {
630 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
635 /* Named data streams (sometimes) */
638 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
641 ret = add_random_data_stream(inode, ctx, stream_name);
644 stream_name[0] += cpu_to_le16(1);
652 select_inode_number(struct generation_context *ctx)
654 const struct wim_inode_table *table = ctx->params->inode_table;
655 const struct hlist_head *head;
656 const struct wim_inode *inode;
658 head = &table->array[rand32() % table->capacity];
659 hlist_for_each_entry(inode, head, i_hlist_node)
667 select_num_children(u32 depth, struct generation_context *ctx)
669 const double b = 1.01230;
670 u32 r = rand32() % 500;
671 return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
672 (2 - exp(0.04/depth));
676 is_name_valid_in_win32_namespace(const utf16lechar *name)
678 const utf16lechar *p;
680 static const char * const reserved_names[] = {
681 "CON", "PRN", "AUX", "NUL",
682 "COM1", "COM2", "COM3", "COM4", "COM5",
683 "COM6", "COM7", "COM8", "COM9",
684 "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
685 "LPT6", "LPT7", "LPT8", "LPT9",
688 /* The name must be nonempty. */
692 /* All characters must be valid on Windows. */
693 for (p = name; *p; p++)
694 if (!is_valid_windows_filename_char(*p))
697 /* Note: a trailing dot or space is permitted, even though on Windows
698 * such a file can only be accessed using a WinNT-style path. */
700 /* The name can't be one of the reserved names or be a reserved name
701 * with an extension. Case insensitive. */
702 for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
703 for (size_t j = 0; ; j++) {
704 u16 c1 = le16_to_cpu(name[j]);
705 u16 c2 = reserved_names[i][j];
707 if (c1 == '\0' || c1 == '.')
711 if (upcase[c1] != upcase[c2])
720 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
721 struct generation_context *ctx)
723 utf16lechar name[12 + 1];
726 struct wim_dentry **bucket;
728 /* If the long name is not allowed in the Win32 namespace, then it
729 * cannot be assigned a corresponding short name. */
730 if (!is_name_valid_in_win32_namespace(child->d_name))
734 /* Don't select a short name that is already used by a long name within
735 * the same directory. */
737 name_len = generate_random_short_name(name, ctx);
738 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
739 WIMLIB_CASE_INSENSITIVE));
742 /* Don't select a short name that is already used by another short name
743 * within the same directory. */
745 for (const utf16lechar *p = name; *p; p++)
746 hash = (hash * 31) + *p;
747 FREE(child->d_short_name);
748 child->d_short_name = memdup(name, (name_len + 1) * 2);
749 child->d_short_name_nbytes = name_len * 2;
751 if (!child->d_short_name)
752 return WIMLIB_ERR_NOMEM;
754 bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
756 for (struct wim_dentry *d = *bucket; d != NULL;
757 d = d->d_next_extraction_alias) {
758 if (!cmp_utf16le_strings(child->d_short_name, name_len,
759 d->d_short_name, d->d_short_name_nbytes / 2,
765 if (!is_name_valid_in_win32_namespace(child->d_short_name))
768 child->d_next_extraction_alias = *bucket;
774 inode_has_short_name(const struct wim_inode *inode)
776 const struct wim_dentry *dentry;
778 inode_for_each_dentry(dentry, inode)
779 if (dentry_has_short_name(dentry))
786 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
787 struct generation_context *ctx)
789 u32 num_children = select_num_children(depth, ctx);
790 struct wim_dentry *child;
793 memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
795 /* Generate 'num_children' dentries within 'dir'. Some may be
796 * directories themselves. */
798 for (u32 i = 0; i < num_children; i++) {
800 /* Generate the next child dentry. */
801 struct wim_inode *inode;
803 bool is_directory = (rand32() % 16 <= 6);
804 bool is_reparse = (rand32() % 8 == 0);
805 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
807 struct wim_dentry *duplicate;
810 * Select an inode number for the new file. Sometimes choose an
811 * existing inode number (i.e. create a hard link). However,
812 * wimlib intentionally doesn't honor directory hard links, and
813 * reparse points cannot be represented in the WIM file format
814 * at all; so don't create hard links for such files.
816 if (is_directory || is_reparse)
819 ino = select_inode_number(ctx);
821 /* Create the dentry. */
822 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
823 ino, 0, ino == 0, &child);
827 /* Choose a filename that is unique within the directory.*/
829 name_len = generate_random_filename(name,
832 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
833 WIMLIB_CASE_PLATFORM_DEFAULT));
835 ret = dentry_set_name_utf16le(child, name, name_len * 2);
841 /* Add the dentry to the directory. */
842 duplicate = dentry_add_child(dir, child);
843 wimlib_assert(!duplicate);
845 inode = child->d_inode;
847 if (inode->i_nlink > 1) /* Existing inode? */
850 /* New inode; set attributes, metadata, and data. */
853 inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
855 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
857 ret = set_random_streams(inode, ctx);
861 ret = set_random_metadata(inode, ctx);
865 /* Recurse if it's a directory. */
866 if (is_directory && !is_reparse) {
867 ret = generate_dentry_tree_recursive(child, depth + 1,
874 for_dentry_child(child, dir) {
875 /* sometimes generate a unique short name */
876 if (randbool() && !inode_has_short_name(child->d_inode)) {
877 ret = set_random_short_name(dir, child, ctx);
887 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
888 struct scan_params *params)
891 struct wim_dentry *root = NULL;
892 struct generation_context ctx = {
896 ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only */
898 ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
900 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
901 ret = set_random_streams(root->d_inode, &ctx);
904 ret = set_random_metadata(root->d_inode, &ctx);
906 ret = generate_dentry_tree_recursive(root, 1, &ctx);
910 free_dentry_tree(root, params->blob_table);
914 /*----------------------------------------------------------------------------*
915 * File tree comparison *
916 *----------------------------------------------------------------------------*/
918 #define INDEX_NODE_TO_DENTRY(node) \
919 ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
921 static struct wim_dentry *
922 dentry_first_child(struct wim_dentry *dentry)
924 return INDEX_NODE_TO_DENTRY(
925 avl_tree_first_in_order(dentry->d_inode->i_children));
928 static struct wim_dentry *
929 dentry_next_sibling(struct wim_dentry *dentry)
931 return INDEX_NODE_TO_DENTRY(
932 avl_tree_next_in_order(&dentry->d_index_node));
936 * Verify that the dentries in the tree 'd1' exactly match the dentries in the
937 * tree 'd2', considering long and short filenames. In addition, set
938 * 'd_corresponding' of each dentry to point to the corresponding dentry in the
939 * other tree, and set 'i_corresponding' of each inode to point to the
940 * unverified corresponding inode in the other tree.
943 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
946 struct wim_dentry *child1;
947 struct wim_dentry *child2;
950 /* Compare long filenames, case sensitively. */
951 if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
952 d2->d_name, d2->d_name_nbytes / 2,
955 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
956 dentry_full_path(d1), dentry_full_path(d2));
957 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
960 /* Compare short filenames, case insensitively. */
961 if (!(d2->d_short_name_nbytes == 0 &&
962 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
963 cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
964 d2->d_short_name, d2->d_short_name_nbytes / 2,
967 ERROR("Short name mismatch; path=\"%"TS"\"",
968 dentry_full_path(d1));
969 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
972 /* Match up the dentries */
973 d1->d_corresponding = d2;
974 d2->d_corresponding = d1;
976 /* Match up the inodes (may overwrite previous value) */
977 d1->d_inode->i_corresponding = d2->d_inode;
978 d2->d_inode->i_corresponding = d1->d_inode;
980 /* Process children */
981 child1 = dentry_first_child(d1);
982 child2 = dentry_first_child(d2);
983 while (child1 || child2) {
985 if (!child1 || !child2) {
986 ERROR("Child count mismatch; "
987 "path1=\"%"TS"\", path2=\"%"TS"\"",
988 dentry_full_path(d1), dentry_full_path(d2));
989 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
992 /* Recurse on this pair of children. */
993 ret = calc_corresponding_files_recursive(child1, child2,
998 /* Continue to the next pair of children. */
999 child1 = dentry_next_sibling(child1);
1000 child2 = dentry_next_sibling(child2);
1005 /* Perform sanity checks on an image's inodes. All assertions here should pass,
1006 * even if the images being compared are different. */
1008 assert_inodes_sane(const struct wim_image_metadata *imd)
1010 const struct wim_inode *inode;
1011 const struct wim_dentry *dentry;
1014 image_for_each_inode(inode, imd) {
1016 inode_for_each_dentry(dentry, inode) {
1017 wimlib_assert(dentry->d_inode == inode);
1020 wimlib_assert(link_count > 0);
1021 wimlib_assert(link_count == inode->i_nlink);
1022 wimlib_assert(inode->i_corresponding != NULL);
1027 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1029 /* My inode is my corresponding dentry's inode's corresponding inode,
1030 * and my inode's corresponding inode is my corresponding dentry's
1032 const struct wim_inode *a = dentry->d_inode;
1033 const struct wim_inode *b = dentry->d_corresponding->d_inode;
1034 if (a == b->i_corresponding && a->i_corresponding == b)
1036 ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1037 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1040 static const struct {
1043 } file_attr_flags[] = {
1044 {FILE_ATTRIBUTE_READONLY, "READONLY"},
1045 {FILE_ATTRIBUTE_HIDDEN, "HIDDEN"},
1046 {FILE_ATTRIBUTE_SYSTEM, "SYSTEM"},
1047 {FILE_ATTRIBUTE_DIRECTORY, "DIRECTORY"},
1048 {FILE_ATTRIBUTE_ARCHIVE, "ARCHIVE"},
1049 {FILE_ATTRIBUTE_DEVICE, "DEVICE"},
1050 {FILE_ATTRIBUTE_NORMAL, "NORMAL"},
1051 {FILE_ATTRIBUTE_TEMPORARY, "TEMPORARY"},
1052 {FILE_ATTRIBUTE_SPARSE_FILE, "SPARSE_FILE"},
1053 {FILE_ATTRIBUTE_REPARSE_POINT, "REPARSE_POINT"},
1054 {FILE_ATTRIBUTE_COMPRESSED, "COMPRESSED"},
1055 {FILE_ATTRIBUTE_OFFLINE, "OFFLINE"},
1056 {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1057 {FILE_ATTRIBUTE_ENCRYPTED, "ENCRYPTED"},
1058 {FILE_ATTRIBUTE_VIRTUAL, "VIRTUAL"},
1062 cmp_attributes(const struct wim_inode *inode1,
1063 const struct wim_inode *inode2, int cmp_flags)
1065 const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1066 const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1067 const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1069 /* NORMAL may change, but it must never be set along with other
1071 if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1072 (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1075 /* DIRECTORY may change in UNIX mode for symlinks. */
1076 if (changed & FILE_ATTRIBUTE_DIRECTORY) {
1077 if (!(inode_is_symlink(inode1) &&
1078 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)))
1082 /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1084 if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1085 !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1086 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1087 !inode_is_symlink(inode1)))
1090 /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1091 * mode if the inode is a directory. */
1092 if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1093 !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1094 ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1095 WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1096 ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1097 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1100 /* COMPRESSED may change in UNIX and NTFS-3G modes. (It *should* be
1101 * preserved in NTFS-3G mode, but it's not implemented yet.) */
1102 if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1103 !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1104 WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1107 /* All other attributes can change in UNIX mode, but not in any other
1109 if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1110 FILE_ATTRIBUTE_DIRECTORY |
1111 FILE_ATTRIBUTE_REPARSE_POINT |
1112 FILE_ATTRIBUTE_SPARSE_FILE |
1113 FILE_ATTRIBUTE_COMPRESSED)) &&
1114 !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1120 ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1121 inode_any_full_path(inode1), inode1->i_attributes,
1122 inode2->i_attributes);
1123 for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1124 u32 flag = file_attr_flags[i].flag;
1125 if (changed & flag) {
1126 fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1127 file_attr_flags[i].name,
1128 (set & flag) ? "set" : "cleared");
1131 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1135 cmp_object_ids(const struct wim_inode *inode1,
1136 const struct wim_inode *inode2, int cmp_flags)
1138 const void *objid1, *objid2;
1141 objid1 = inode_get_object_id(inode1, &len1);
1142 objid2 = inode_get_object_id(inode2, &len2);
1144 if (!objid1 && !objid2)
1147 if (objid1 && !objid2) {
1148 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1150 ERROR("%"TS" unexpectedly lost its object ID",
1151 inode_any_full_path(inode1));
1152 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1155 if (!objid1 && objid2) {
1156 ERROR("%"TS" unexpectedly gained an object ID",
1157 inode_any_full_path(inode1));
1158 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1161 if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1162 ERROR("Object ID of %"TS" differs",
1163 inode_any_full_path(inode1));
1164 fprintf(stderr, "objid1=");
1165 print_byte_field(objid1, len1, stderr);
1166 fprintf(stderr, "\nobjid2=");
1167 print_byte_field(objid2, len2, stderr);
1168 fprintf(stderr, "\n");
1169 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1176 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1177 const struct wim_image_metadata *imd1,
1178 const struct wim_image_metadata *imd2, int cmp_flags)
1182 /* Compare attributes */
1183 ret = cmp_attributes(inode1, inode2, cmp_flags);
1187 /* Compare security descriptors */
1188 if (inode_has_security_descriptor(inode1)) {
1189 if (inode_has_security_descriptor(inode2)) {
1190 const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1191 const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1192 size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1193 size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1195 if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1196 ERROR("Security descriptor of %"TS" differs!",
1197 inode_any_full_path(inode1));
1198 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1200 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1201 ERROR("%"TS" has a security descriptor in the first image but "
1202 "not in the second image!", inode_any_full_path(inode1));
1203 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1205 } else if (inode_has_security_descriptor(inode2)) {
1206 /* okay --- consider it acceptable if a default security
1207 * descriptor was assigned */
1208 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1209 /*"not in the first image!", inode_any_full_path(inode1));*/
1210 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1213 /* Compare streams */
1214 for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1215 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1216 const struct wim_inode_stream *strm2;
1218 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1219 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1220 !inode_is_symlink(inode1)))
1223 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1226 /* Get the corresponding stream from the second file */
1227 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1230 /* Corresponding stream not found */
1231 if (stream_is_named(strm1) &&
1232 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1234 ERROR("Stream of %"TS" is missing in second image; "
1235 "type %d, named=%d, empty=%d",
1236 inode_any_full_path(inode1),
1238 stream_is_named(strm1),
1239 is_zero_hash(stream_hash(strm1)));
1240 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1243 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1244 ERROR("Stream of %"TS" differs; type %d",
1245 inode_any_full_path(inode1), strm1->stream_type);
1246 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1250 /* Compare object IDs */
1251 ret = cmp_object_ids(inode1, inode2, cmp_flags);
1259 cmp_images(const struct wim_image_metadata *imd1,
1260 const struct wim_image_metadata *imd2, int cmp_flags)
1262 struct wim_dentry *root1 = imd1->root_dentry;
1263 struct wim_dentry *root2 = imd2->root_dentry;
1264 const struct wim_inode *inode;
1267 ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1271 /* Verify that the hard links match up between the two images. */
1272 assert_inodes_sane(imd1);
1273 assert_inodes_sane(imd2);
1274 ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1278 /* Compare corresponding inodes. */
1279 image_for_each_inode(inode, imd1) {
1280 ret = cmp_inodes(inode, inode->i_corresponding,
1281 imd1, imd2, cmp_flags);
1290 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1292 int ret = select_wim_image(wim, image);
1294 *imd_ret = wim_get_current_image_metadata(wim);
1295 mark_image_dirty(*imd_ret);
1301 wimlib_compare_images(WIMStruct *wim1, int image1,
1302 WIMStruct *wim2, int image2, int cmp_flags)
1305 struct wim_image_metadata *imd1, *imd2;
1307 ret = load_image(wim1, image1, &imd1);
1309 ret = load_image(wim2, image2, &imd2);
1311 ret = cmp_images(imd1, imd2, cmp_flags);
1315 #endif /* ENABLE_TEST_SUPPORT */