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
43 #include "wimlib/endianness.h"
44 #include "wimlib/encoding.h"
45 #include "wimlib/metadata.h"
46 #include "wimlib/dentry.h"
47 #include "wimlib/inode.h"
48 #include "wimlib/object_id.h"
49 #include "wimlib/reparse.h"
50 #include "wimlib/scan.h"
51 #include "wimlib/security_descriptor.h"
52 #include "wimlib/test_support.h"
53 #include "wimlib/unix_data.h"
55 /*----------------------------------------------------------------------------*
56 * File tree generation *
57 *----------------------------------------------------------------------------*/
59 struct generation_context {
60 struct scan_params *params;
61 struct wim_dentry *used_short_names[256];
68 static u64 state = 0x55DB93D0AB838771;
70 /* A simple linear congruential generator */
71 state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
78 return (rand32() & 1) != 0;
96 return ((u64)rand32() << 32) | rand32();
100 generate_random_timestamp(void)
102 /* When setting timestamps on Windows:
103 * - 0 is a special value meaning "not specified"
104 * - if the high bit is set you get STATUS_INVALID_PARAMETER */
105 return (1 + rand64()) & ~(1ULL << 63);
109 is_valid_windows_filename_char(utf16lechar c)
111 return le16_to_cpu(c) > 31 &&
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('/' ) &&
118 c != cpu_to_le16('\\') &&
119 c != cpu_to_le16('|') &&
120 c != cpu_to_le16('?') &&
121 c != cpu_to_le16('*');
124 /* Is the character valid in a filename on the current platform? */
126 is_valid_filename_char(utf16lechar c)
129 return is_valid_windows_filename_char(c);
131 return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
135 /* Generate a random filename and return its length. */
137 generate_random_filename(utf16lechar name[], int max_len,
138 struct generation_context *ctx)
142 /* Choose the length of the name. */
143 switch (rand32() % 8) {
146 len = 1 + (rand32() % 6);
151 /* medium-length name */
152 len = 7 + (rand32() % 8);
157 len = 15 + (rand32() % 15);
161 len = 30 + (rand32() % 90);
164 len = min(len, max_len);
167 /* Generate the characters in the name. */
168 for (int i = 0; i < len; i++) {
171 } while (!is_valid_filename_char(name[i]));
174 /* Add a null terminator. */
175 name[len] = cpu_to_le16('\0');
177 /* Don't generate . and .. */
178 if (name[0] == cpu_to_le16('.') &&
179 (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
185 /* The set of characters which are valid in short filenames. */
186 static const char valid_short_name_chars[] = {
187 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
188 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
189 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
190 '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
192 /* Note: Windows does not allow space and 128-255 in short filenames
193 * (tested on both NTFS and FAT). */
197 generate_short_name_component(utf16lechar p[], int len)
199 for (int i = 0; i < len; i++) {
200 char c = valid_short_name_chars[rand32() %
201 ARRAY_LEN(valid_short_name_chars)];
202 p[i] = cpu_to_le16(c);
207 /* Generate a random short (8.3) filename and return its length.
208 * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
210 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
213 * Legal short names on Windows consist of 1 to 8 characters, optionally
214 * followed by a dot then 1 to 3 more characters. Only certain
215 * characters are allowed.
217 int base_len = 1 + (rand32() % 8);
218 int ext_len = rand32() % 4;
221 base_len = generate_short_name_component(name, base_len);
224 name[base_len] = cpu_to_le16('.');
225 ext_len = generate_short_name_component(&name[base_len + 1],
227 total_len = base_len + 1 + ext_len;
229 total_len = base_len;
231 name[total_len] = cpu_to_le16('\0');
236 static const struct {
237 u8 num_subauthorities;
238 u64 identifier_authority;
239 u32 subauthorities[6];
241 { 1, 0, {0}}, /* NULL_SID */
242 { 1, 1, {0}}, /* WORLD_SID */
243 { 1, 2, {0}}, /* LOCAL_SID */
244 { 1, 3, {0}}, /* CREATOR_OWNER_SID */
245 { 1, 3, {1}}, /* CREATOR_GROUP_SID */
246 { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
247 { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
248 // { 0, 5, {}}, /* NT_AUTHORITY_SID */
249 { 1, 5, {1}}, /* DIALUP_SID */
250 { 1, 5, {2}}, /* NETWORK_SID */
251 { 1, 5, {3}}, /* BATCH_SID */
252 { 1, 5, {4}}, /* INTERACTIVE_SID */
253 { 1, 5, {6}}, /* SERVICE_SID */
254 { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
255 { 1, 5, {8}}, /* PROXY_SID */
256 { 1, 5, {9}}, /* SERVER_LOGON_SID */
257 { 1, 5, {10}}, /* SELF_SID */
258 { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
259 { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
260 { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
261 { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
262 { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
263 { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
264 { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer */
265 { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS */
268 /* Generate a SID and return its size in bytes. */
270 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
278 r = (r >> 1) % ARRAY_LEN(common_sids);
280 sid->sub_authority_count = common_sids[r].num_subauthorities;
281 for (int i = 0; i < 6; i++) {
282 sid->identifier_authority[i] =
283 common_sids[r].identifier_authority >> (40 - i * 8);
285 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
286 sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
290 sid->sub_authority_count = 1 + ((r >> 1) % 15);
292 for (int i = 0; i < 6; i++)
293 sid->identifier_authority[i] = rand8();
295 for (int i = 0; i < sid->sub_authority_count; i++)
296 sid->sub_authority[i] = cpu_to_le32(rand32());
298 return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
301 /* Generate an ACL and return its size in bytes. */
303 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
308 ace_count = rand32() % 16;
312 acl->ace_count = cpu_to_le16(ace_count);
317 for (int i = 0; i < ace_count; i++) {
318 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
320 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
323 ace->hdr.type = rand32() % 2;
326 ace->hdr.flags = rand8();
327 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
329 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
330 generate_random_sid(&ace->sid, ctx);
331 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
334 acl->acl_size = cpu_to_le16(p - (u8 *)acl);
335 return p - (u8 *)acl;
338 /* Generate a security descriptor and return its size in bytes. */
340 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
342 wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
348 control &= (wimlib_SE_DACL_AUTO_INHERITED |
349 wimlib_SE_SACL_AUTO_INHERITED);
351 control |= wimlib_SE_SELF_RELATIVE |
352 wimlib_SE_DACL_PRESENT |
353 wimlib_SE_SACL_PRESENT;
357 desc->control = cpu_to_le16(control);
359 p = (u8 *)(desc + 1);
361 desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
362 p += generate_random_sid((wimlib_SID *)p, ctx);
364 desc->group_offset = cpu_to_le32(p - (u8 *)desc);
365 p += generate_random_sid((wimlib_SID *)p, ctx);
367 if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
368 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
369 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
371 desc->dacl_offset = cpu_to_le32(0);
374 if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
375 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
376 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
378 desc->sacl_offset = cpu_to_le32(0);
381 return p - (u8 *)desc;
390 return (getuid() == 0);
420 # define S_IFLNK 0120000
423 # define S_IFSOCK 0140000
428 set_random_unix_metadata(struct wim_inode *inode)
430 struct wimlib_unix_data dat;
432 dat.uid = generate_uid();
433 dat.gid = generate_gid();
434 if (inode_is_symlink(inode))
435 dat.mode = S_IFLNK | 0777;
436 else if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)
437 dat.mode = S_IFDIR | 0700 | (rand32() % 07777);
438 else if (is_zero_hash(inode_get_hash_of_unnamed_data_stream(inode)) &&
439 randbool() && am_root())
441 dat.mode = rand32() % 07777;
442 switch (rand32() % 4) {
448 dat.rdev = 261; /* /dev/zero */
452 dat.rdev = 261; /* /dev/zero */
455 dat.mode |= S_IFSOCK;
459 dat.mode = S_IFREG | 0400 | (rand32() % 07777);
463 if (!inode_set_unix_data(inode, &dat, UNIX_DATA_ALL))
464 return WIMLIB_ERR_NOMEM;
470 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
472 u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
473 FILE_ATTRIBUTE_HIDDEN |
474 FILE_ATTRIBUTE_SYSTEM |
475 FILE_ATTRIBUTE_ARCHIVE |
476 FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
477 FILE_ATTRIBUTE_COMPRESSED |
478 FILE_ATTRIBUTE_SPARSE_FILE));
480 /* File attributes */
481 inode->i_attributes |= attrib;
484 inode->i_creation_time = generate_random_timestamp();
485 inode->i_last_access_time = generate_random_timestamp();
486 inode->i_last_write_time = generate_random_timestamp();
488 /* Security descriptor */
490 char desc[8192] _aligned_attribute(8);
493 size = generate_random_security_descriptor(desc, ctx);
495 wimlib_assert(size <= sizeof(desc));
497 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
499 if (unlikely(inode->i_security_id < 0))
500 return WIMLIB_ERR_NOMEM;
504 if (rand32() % 32 == 0) {
505 struct wimlib_object_id object_id;
507 for (int i = 0; i < sizeof(object_id); i++)
508 *((u8 *)&object_id + i) = rand8();
509 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
510 return WIMLIB_ERR_NOMEM;
513 /* Standard UNIX permissions and special files */
514 if (rand32() % 16 == 0) {
515 int ret = set_random_unix_metadata(inode);
524 /* Choose a random size for generated file data. We want to usually generate
525 * empty, small, or medium files, but occasionally generate large files. */
527 select_stream_size(struct generation_context *ctx)
529 if (ctx->metadata_only)
532 switch (rand32() % 2048) {
538 return rand32() % 64;
541 return rand32() % 4096;
544 return rand32() % 32768;
547 return rand32() % 262144;
550 return rand32() % 134217728;
554 /* Fill 'buffer' with 'size' bytes of "interesting" file data. */
556 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
559 size_t num_byte_fills = rand32() % 256;
564 /* Start by initializing to a random byte */
565 memset(buffer, rand32() % 256, size);
567 /* Add some random bytes in some random places */
568 for (size_t i = 0; i < num_byte_fills; i++) {
571 size_t count = ((double)size / (double)num_byte_fills) *
572 ((double)rand32() / 2e9);
573 size_t offset = rand32() & ~mask;
577 ((rand32()) & mask)) % size] = b;
581 if (rand32() % 4 == 0)
582 mask = (size_t)-1 << rand32() % 4;
585 /* Sometimes add a wave pattern */
586 if (rand32() % 8 == 0) {
587 double magnitude = rand32() % 128;
588 double scale = 1.0 / (1 + (rand32() % 256));
590 for (size_t i = 0; i < size; i++)
591 buffer[i] += (int)(magnitude * cos(i * scale));
594 /* Sometimes add some zero regions (holes) */
595 if (rand32() % 4 == 0) {
596 size_t num_holes = 1 + (rand32() % 16);
597 for (size_t i = 0; i < num_holes; i++) {
598 size_t hole_offset = rand32() % size;
599 size_t hole_len = min(size - hole_offset,
600 size / (1 + (rand32() % 16)));
601 memset(&buffer[hole_offset], 0, hole_len);
607 add_stream(struct wim_inode *inode, struct generation_context *ctx,
608 int stream_type, const utf16lechar *stream_name,
609 void *buffer, size_t size)
611 struct blob_descriptor *blob = NULL;
612 struct wim_inode_stream *strm;
615 blob = new_blob_descriptor();
618 blob->attached_buffer = buffer;
619 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
623 strm = inode_add_stream(inode, stream_type, stream_name, blob);
627 prepare_unhashed_blob(blob, inode, strm->stream_id,
628 ctx->params->unhashed_blobs);
632 free_blob_descriptor(blob);
633 return WIMLIB_ERR_NOMEM;
636 static noinline_for_stack int
637 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
639 struct reparse_buffer_disk rpbuf;
642 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
647 utf16lechar *targets = (utf16lechar *)rpbuf.link.symlink.data;
649 inode->i_reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
651 target_nchars = generate_random_filename(targets, 255, ctx);
653 rpbuf.link.substitute_name_offset = cpu_to_le16(0);
654 rpbuf.link.substitute_name_nbytes = cpu_to_le16(2*target_nchars);
655 rpbuf.link.print_name_offset = cpu_to_le16(2*(target_nchars + 1));
656 rpbuf.link.print_name_nbytes = cpu_to_le16(2*target_nchars);
657 targets[target_nchars] = cpu_to_le16(0);
658 memcpy(&targets[target_nchars + 1], targets, 2*target_nchars);
659 targets[target_nchars + 1 + target_nchars] = cpu_to_le16(0);
661 rpbuf.link.symlink.flags = cpu_to_le32(SYMBOLIC_LINK_RELATIVE);
662 rpdatalen = ((u8 *)targets - rpbuf.rpdata) +
663 2*(target_nchars + 1 + target_nchars + 1);
665 rpdatalen = select_stream_size(ctx) % REPARSE_DATA_MAX_SIZE;
666 generate_data(rpbuf.rpdata, rpdatalen, ctx);
668 if (rpdatalen >= GUID_SIZE && randbool()) {
669 /* Non-Microsoft reparse tag (16-byte GUID required) */
670 u8 *guid = rpbuf.rpdata;
671 guid[6] = (guid[6] & 0x0F) | 0x40;
672 guid[8] = (guid[8] & 0x3F) | 0x80;
673 inode->i_reparse_tag = 0x00000100;
675 /* Microsoft reparse tag */
676 inode->i_reparse_tag = 0x80000000;
678 inode->i_rp_reserved = rand16();
681 wimlib_assert(rpdatalen < REPARSE_DATA_MAX_SIZE);
683 if (!inode_add_stream_with_data(inode, STREAM_TYPE_REPARSE_POINT,
684 NO_STREAM_NAME, rpbuf.rpdata,
685 rpdatalen, ctx->params->blob_table))
686 return WIMLIB_ERR_NOMEM;
692 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
693 const utf16lechar *stream_name)
698 size = select_stream_size(ctx);
700 buffer = MALLOC(size);
702 return WIMLIB_ERR_NOMEM;
703 generate_data(buffer, size, ctx);
706 return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
711 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
716 /* Reparse point (sometimes) */
717 if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
718 ret = set_random_reparse_point(inode, ctx);
723 /* Unnamed data stream (nondirectories and non-symlinks only) */
724 if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) &&
725 !inode_is_symlink(inode)) {
726 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
731 /* Named data streams (sometimes) */
734 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
737 ret = add_random_data_stream(inode, ctx, stream_name);
740 stream_name[0] += cpu_to_le16(1);
748 select_inode_number(struct generation_context *ctx)
750 const struct wim_inode_table *table = ctx->params->inode_table;
751 const struct hlist_head *head;
752 const struct wim_inode *inode;
754 head = &table->array[rand32() % table->capacity];
755 hlist_for_each_entry(inode, head, i_hlist_node)
763 select_num_children(u32 depth, struct generation_context *ctx)
765 const double b = 1.01230;
766 u32 r = rand32() % 500;
767 return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
768 (2 - exp(0.04/depth));
772 is_name_valid_in_win32_namespace(const utf16lechar *name)
774 const utf16lechar *p;
776 static const char * const reserved_names[] = {
777 "CON", "PRN", "AUX", "NUL",
778 "COM1", "COM2", "COM3", "COM4", "COM5",
779 "COM6", "COM7", "COM8", "COM9",
780 "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
781 "LPT6", "LPT7", "LPT8", "LPT9",
784 /* The name must be nonempty. */
788 /* All characters must be valid on Windows. */
789 for (p = name; *p; p++)
790 if (!is_valid_windows_filename_char(*p))
793 /* Note: a trailing dot or space is permitted, even though on Windows
794 * such a file can only be accessed using a WinNT-style path. */
796 /* The name can't be one of the reserved names or be a reserved name
797 * with an extension. Case insensitive. */
798 for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
799 for (size_t j = 0; ; j++) {
800 u16 c1 = le16_to_cpu(name[j]);
801 u16 c2 = reserved_names[i][j];
803 if (c1 == '\0' || c1 == '.')
807 if (upcase[c1] != upcase[c2])
816 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
817 struct generation_context *ctx)
819 utf16lechar name[12 + 1];
822 struct wim_dentry **bucket;
824 /* If the long name is not allowed in the Win32 namespace, then it
825 * cannot be assigned a corresponding short name. */
826 if (!is_name_valid_in_win32_namespace(child->d_name))
830 /* Don't select a short name that is already used by a long name within
831 * the same directory. */
833 name_len = generate_random_short_name(name, ctx);
834 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
835 WIMLIB_CASE_INSENSITIVE));
838 /* Don't select a short name that is already used by another short name
839 * within the same directory. */
841 for (const utf16lechar *p = name; *p; p++)
842 hash = (hash * 31) + *p;
843 FREE(child->d_short_name);
844 child->d_short_name = memdup(name, (name_len + 1) * 2);
845 child->d_short_name_nbytes = name_len * 2;
847 if (!child->d_short_name)
848 return WIMLIB_ERR_NOMEM;
850 bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
852 for (struct wim_dentry *d = *bucket; d != NULL;
853 d = d->d_next_extraction_alias) {
854 if (!cmp_utf16le_strings(child->d_short_name, name_len,
855 d->d_short_name, d->d_short_name_nbytes / 2,
861 if (!is_name_valid_in_win32_namespace(child->d_short_name))
864 child->d_next_extraction_alias = *bucket;
870 inode_has_short_name(const struct wim_inode *inode)
872 const struct wim_dentry *dentry;
874 inode_for_each_dentry(dentry, inode)
875 if (dentry_has_short_name(dentry))
882 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
883 struct generation_context *ctx)
885 u32 num_children = select_num_children(depth, ctx);
886 struct wim_dentry *child;
889 memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
891 /* Generate 'num_children' dentries within 'dir'. Some may be
892 * directories themselves. */
894 for (u32 i = 0; i < num_children; i++) {
896 /* Generate the next child dentry. */
897 struct wim_inode *inode;
899 bool is_directory = (rand32() % 16 <= 6);
900 bool is_reparse = (rand32() % 8 == 0);
901 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
903 struct wim_dentry *duplicate;
906 * Select an inode number for the new file. Sometimes choose an
907 * existing inode number (i.e. create a hard link). However,
908 * wimlib intentionally doesn't honor directory hard links, and
909 * reparse points cannot be represented in the WIM file format
910 * at all; so don't create hard links for such files.
912 if (is_directory || is_reparse)
915 ino = select_inode_number(ctx);
917 /* Create the dentry. */
918 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
919 ino, 0, ino == 0, &child);
923 /* Choose a filename that is unique within the directory.*/
925 name_len = generate_random_filename(name,
928 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
929 WIMLIB_CASE_PLATFORM_DEFAULT));
931 ret = dentry_set_name_utf16le(child, name, name_len * 2);
937 /* Add the dentry to the directory. */
938 duplicate = dentry_add_child(dir, child);
939 wimlib_assert(!duplicate);
941 inode = child->d_inode;
943 if (inode->i_nlink > 1) /* Existing inode? */
946 /* New inode; set attributes, metadata, and data. */
949 inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
951 inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
953 ret = set_random_streams(inode, ctx);
957 ret = set_random_metadata(inode, ctx);
961 /* Recurse if it's a directory. */
962 if (is_directory && !is_reparse) {
963 ret = generate_dentry_tree_recursive(child, depth + 1,
970 for_dentry_child(child, dir) {
971 /* sometimes generate a unique short name */
972 if (randbool() && !inode_has_short_name(child->d_inode)) {
973 ret = set_random_short_name(dir, child, ctx);
983 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
984 struct scan_params *params)
987 struct wim_dentry *root = NULL;
988 struct generation_context ctx = {
992 ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only */
994 ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
996 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
997 ret = set_random_streams(root->d_inode, &ctx);
1000 ret = set_random_metadata(root->d_inode, &ctx);
1002 ret = generate_dentry_tree_recursive(root, 1, &ctx);
1006 free_dentry_tree(root, params->blob_table);
1010 /*----------------------------------------------------------------------------*
1011 * File tree comparison *
1012 *----------------------------------------------------------------------------*/
1014 #define INDEX_NODE_TO_DENTRY(node) \
1015 ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
1017 static struct wim_dentry *
1018 dentry_first_child(struct wim_dentry *dentry)
1020 return INDEX_NODE_TO_DENTRY(
1021 avl_tree_first_in_order(dentry->d_inode->i_children));
1024 static struct wim_dentry *
1025 dentry_next_sibling(struct wim_dentry *dentry)
1027 return INDEX_NODE_TO_DENTRY(
1028 avl_tree_next_in_order(&dentry->d_index_node));
1032 * Verify that the dentries in the tree 'd1' exactly match the dentries in the
1033 * tree 'd2', considering long and short filenames. In addition, set
1034 * 'd_corresponding' of each dentry to point to the corresponding dentry in the
1035 * other tree, and set 'i_corresponding' of each inode to point to the
1036 * unverified corresponding inode in the other tree.
1039 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
1042 struct wim_dentry *child1;
1043 struct wim_dentry *child2;
1046 /* Compare long filenames, case sensitively. */
1047 if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
1048 d2->d_name, d2->d_name_nbytes / 2,
1051 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
1052 dentry_full_path(d1), dentry_full_path(d2));
1053 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1056 /* Compare short filenames, case insensitively. */
1057 if (!(d2->d_short_name_nbytes == 0 &&
1058 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
1059 cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
1060 d2->d_short_name, d2->d_short_name_nbytes / 2,
1063 ERROR("Short name mismatch; path=\"%"TS"\"",
1064 dentry_full_path(d1));
1065 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1068 /* Match up the dentries */
1069 d1->d_corresponding = d2;
1070 d2->d_corresponding = d1;
1072 /* Match up the inodes (may overwrite previous value) */
1073 d1->d_inode->i_corresponding = d2->d_inode;
1074 d2->d_inode->i_corresponding = d1->d_inode;
1076 /* Process children */
1077 child1 = dentry_first_child(d1);
1078 child2 = dentry_first_child(d2);
1079 while (child1 || child2) {
1081 if (!child1 || !child2) {
1082 ERROR("Child count mismatch; "
1083 "path1=\"%"TS"\", path2=\"%"TS"\"",
1084 dentry_full_path(d1), dentry_full_path(d2));
1085 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1088 /* Recurse on this pair of children. */
1089 ret = calc_corresponding_files_recursive(child1, child2,
1094 /* Continue to the next pair of children. */
1095 child1 = dentry_next_sibling(child1);
1096 child2 = dentry_next_sibling(child2);
1101 /* Perform sanity checks on an image's inodes. All assertions here should pass,
1102 * even if the images being compared are different. */
1104 assert_inodes_sane(const struct wim_image_metadata *imd)
1106 const struct wim_inode *inode;
1107 const struct wim_dentry *dentry;
1110 image_for_each_inode(inode, imd) {
1112 inode_for_each_dentry(dentry, inode) {
1113 wimlib_assert(dentry->d_inode == inode);
1116 wimlib_assert(link_count > 0);
1117 wimlib_assert(link_count == inode->i_nlink);
1118 wimlib_assert(inode->i_corresponding != NULL);
1123 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1125 /* My inode is my corresponding dentry's inode's corresponding inode,
1126 * and my inode's corresponding inode is my corresponding dentry's
1128 const struct wim_inode *a = dentry->d_inode;
1129 const struct wim_inode *b = dentry->d_corresponding->d_inode;
1130 if (a == b->i_corresponding && a->i_corresponding == b)
1132 ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1133 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1136 static const struct {
1139 } file_attr_flags[] = {
1140 {FILE_ATTRIBUTE_READONLY, "READONLY"},
1141 {FILE_ATTRIBUTE_HIDDEN, "HIDDEN"},
1142 {FILE_ATTRIBUTE_SYSTEM, "SYSTEM"},
1143 {FILE_ATTRIBUTE_DIRECTORY, "DIRECTORY"},
1144 {FILE_ATTRIBUTE_ARCHIVE, "ARCHIVE"},
1145 {FILE_ATTRIBUTE_DEVICE, "DEVICE"},
1146 {FILE_ATTRIBUTE_NORMAL, "NORMAL"},
1147 {FILE_ATTRIBUTE_TEMPORARY, "TEMPORARY"},
1148 {FILE_ATTRIBUTE_SPARSE_FILE, "SPARSE_FILE"},
1149 {FILE_ATTRIBUTE_REPARSE_POINT, "REPARSE_POINT"},
1150 {FILE_ATTRIBUTE_COMPRESSED, "COMPRESSED"},
1151 {FILE_ATTRIBUTE_OFFLINE, "OFFLINE"},
1152 {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1153 {FILE_ATTRIBUTE_ENCRYPTED, "ENCRYPTED"},
1154 {FILE_ATTRIBUTE_VIRTUAL, "VIRTUAL"},
1158 cmp_attributes(const struct wim_inode *inode1,
1159 const struct wim_inode *inode2, int cmp_flags)
1161 const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1162 const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1163 const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1165 /* NORMAL may change, but it must never be set along with other
1167 if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1168 (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1171 /* DIRECTORY may change in UNIX mode for symlinks. */
1172 if (changed & FILE_ATTRIBUTE_DIRECTORY) {
1173 if (!(inode_is_symlink(inode1) &&
1174 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)))
1178 /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1180 if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1181 !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1182 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1183 !inode_is_symlink(inode1)))
1186 /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1187 * mode if the inode is a directory. */
1188 if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1189 !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1190 ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1191 WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1192 ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1193 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1196 /* COMPRESSED may change in UNIX and NTFS-3G modes. (It *should* be
1197 * preserved in NTFS-3G mode, but it's not implemented yet.) */
1198 if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1199 !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1200 WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1203 /* All other attributes can change in UNIX mode, but not in any other
1205 if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1206 FILE_ATTRIBUTE_DIRECTORY |
1207 FILE_ATTRIBUTE_REPARSE_POINT |
1208 FILE_ATTRIBUTE_SPARSE_FILE |
1209 FILE_ATTRIBUTE_COMPRESSED)) &&
1210 !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1216 ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1217 inode_any_full_path(inode1), inode1->i_attributes,
1218 inode2->i_attributes);
1219 for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1220 u32 flag = file_attr_flags[i].flag;
1221 if (changed & flag) {
1222 fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1223 file_attr_flags[i].name,
1224 (set & flag) ? "set" : "cleared");
1227 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1231 cmp_object_ids(const struct wim_inode *inode1,
1232 const struct wim_inode *inode2, int cmp_flags)
1234 const void *objid1, *objid2;
1237 objid1 = inode_get_object_id(inode1, &len1);
1238 objid2 = inode_get_object_id(inode2, &len2);
1240 if (!objid1 && !objid2)
1243 if (objid1 && !objid2) {
1244 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1246 ERROR("%"TS" unexpectedly lost its object ID",
1247 inode_any_full_path(inode1));
1248 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1251 if (!objid1 && objid2) {
1252 ERROR("%"TS" unexpectedly gained an object ID",
1253 inode_any_full_path(inode1));
1254 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1257 if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1258 ERROR("Object ID of %"TS" differs",
1259 inode_any_full_path(inode1));
1260 fprintf(stderr, "objid1=");
1261 print_byte_field(objid1, len1, stderr);
1262 fprintf(stderr, "\nobjid2=");
1263 print_byte_field(objid2, len2, stderr);
1264 fprintf(stderr, "\n");
1265 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1272 cmp_unix_metadata(const struct wim_inode *inode1,
1273 const struct wim_inode *inode2, int cmp_flags)
1275 struct wimlib_unix_data dat1, dat2;
1276 bool present1, present2;
1278 present1 = inode_get_unix_data(inode1, &dat1);
1279 present2 = inode_get_unix_data(inode2, &dat2);
1281 if (!present1 && !present2)
1284 if (present1 && !present2) {
1285 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1286 WIMLIB_CMP_FLAG_WINDOWS_MODE))
1288 ERROR("%"TS" unexpectedly lost its UNIX metadata",
1289 inode_any_full_path(inode1));
1290 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1293 if (!present1 && present2) {
1294 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1296 ERROR("%"TS" unexpectedly gained UNIX metadata",
1297 inode_any_full_path(inode1));
1298 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1301 if (memcmp(&dat1, &dat2, sizeof(dat1)) != 0) {
1302 ERROR("UNIX metadata of %"TS" differs: "
1303 "[uid=%u, gid=%u, mode=0%o, rdev=%u] vs. "
1304 "[uid=%u, gid=%u, mode=0%o, rdev=%u]",
1305 inode_any_full_path(inode1),
1306 dat1.uid, dat1.gid, dat1.mode, dat1.rdev,
1307 dat2.uid, dat2.gid, dat2.mode, dat2.rdev);
1308 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1315 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1316 const struct wim_image_metadata *imd1,
1317 const struct wim_image_metadata *imd2, int cmp_flags)
1321 /* Compare attributes */
1322 ret = cmp_attributes(inode1, inode2, cmp_flags);
1326 /* Compare security descriptors */
1327 if (inode_has_security_descriptor(inode1)) {
1328 if (inode_has_security_descriptor(inode2)) {
1329 const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1330 const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1331 size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1332 size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1334 if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1335 ERROR("Security descriptor of %"TS" differs!",
1336 inode_any_full_path(inode1));
1337 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1339 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1340 ERROR("%"TS" has a security descriptor in the first image but "
1341 "not in the second image!", inode_any_full_path(inode1));
1342 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1344 } else if (inode_has_security_descriptor(inode2)) {
1345 /* okay --- consider it acceptable if a default security
1346 * descriptor was assigned */
1347 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1348 /*"not in the first image!", inode_any_full_path(inode1));*/
1349 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1352 /* Compare streams */
1353 for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1354 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1355 const struct wim_inode_stream *strm2;
1357 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1358 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1359 !inode_is_symlink(inode1)))
1362 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1365 /* Get the corresponding stream from the second file */
1366 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1369 /* Corresponding stream not found */
1370 if (stream_is_named(strm1) &&
1371 (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1373 ERROR("Stream of %"TS" is missing in second image; "
1374 "type %d, named=%d, empty=%d",
1375 inode_any_full_path(inode1),
1377 stream_is_named(strm1),
1378 is_zero_hash(stream_hash(strm1)));
1379 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1382 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1383 ERROR("Stream of %"TS" differs; type %d",
1384 inode_any_full_path(inode1), strm1->stream_type);
1385 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1389 /* Compare object IDs */
1390 ret = cmp_object_ids(inode1, inode2, cmp_flags);
1394 /* Compare standard UNIX metadata */
1395 ret = cmp_unix_metadata(inode1, inode2, cmp_flags);
1403 cmp_images(const struct wim_image_metadata *imd1,
1404 const struct wim_image_metadata *imd2, int cmp_flags)
1406 struct wim_dentry *root1 = imd1->root_dentry;
1407 struct wim_dentry *root2 = imd2->root_dentry;
1408 const struct wim_inode *inode;
1411 ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1415 /* Verify that the hard links match up between the two images. */
1416 assert_inodes_sane(imd1);
1417 assert_inodes_sane(imd2);
1418 ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1422 /* Compare corresponding inodes. */
1423 image_for_each_inode(inode, imd1) {
1424 ret = cmp_inodes(inode, inode->i_corresponding,
1425 imd1, imd2, cmp_flags);
1434 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1436 int ret = select_wim_image(wim, image);
1438 *imd_ret = wim_get_current_image_metadata(wim);
1439 mark_image_dirty(*imd_ret);
1445 wimlib_compare_images(WIMStruct *wim1, int image1,
1446 WIMStruct *wim2, int image2, int cmp_flags)
1449 struct wim_image_metadata *imd1, *imd2;
1451 ret = load_image(wim1, image1, &imd1);
1453 ret = load_image(wim2, image2, &imd2);
1455 ret = cmp_images(imd1, imd2, cmp_flags);
1459 #endif /* ENABLE_TEST_SUPPORT */