wimlib.net Git - wimlib/blob - src/test_support.c

   1 /*
   2  * test_support.c - Supporting code for tests
   3  */
   4
   5 /*
   6  * Copyright (C) 2015-2018 Eric Biggers
   7  *
   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
  11  * later version.
  12  *
  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
  16  * details.
  17  *
  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/.
  20  */
  21
  22 /*
  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:
  25  *
  26  *      - Random directory tree generation
  27  *      - Directory tree comparison
  28  */
  29
  30 #ifdef HAVE_CONFIG_H
  31 #  include "config.h"
  32 #endif
  33
  34 #ifdef ENABLE_TEST_SUPPORT
  35
  36 #include <ctype.h>
  37 #include <math.h>
  38 #include <stdlib.h>
  39 #include <sys/stat.h>
  40 #include <unistd.h>
  41
  42 #include "wimlib.h"
  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"
  54 #include "wimlib/xattr.h"
  55
  56 /*----------------------------------------------------------------------------*
  57  *                            File tree generation                            *
  58  *----------------------------------------------------------------------------*/
  59
  60 struct generation_context {
  61         struct scan_params *params;
  62         struct wim_dentry *used_short_names[256];
  63         bool metadata_only;
  64 };
  65
  66 static u32
  67 rand32(void)
  68 {
  69         static u64 state = 0x55DB93D0AB838771;
  70
  71         /* A simple linear congruential generator  */
  72         state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
  73         return state >> 16;
  74 }
  75
  76 static bool
  77 randbool(void)
  78 {
  79         return (rand32() & 1) != 0;
  80 }
  81
  82 static u8
  83 rand8(void)
  84 {
  85         return (u8)rand32();
  86 }
  87
  88 static u16
  89 rand16(void)
  90 {
  91         return (u16)rand32();
  92 }
  93
  94 static u64
  95 rand64(void)
  96 {
  97         return ((u64)rand32() << 32) | rand32();
  98 }
  99
 100 static u64
 101 generate_random_timestamp(void)
 102 {
 103         /* When setting timestamps on Windows:
 104          * - 0 is a special value meaning "not specified"
 105          * - if the high bit is set you get STATUS_INVALID_PARAMETER  */
 106         return (1 + rand64()) & ~(1ULL << 63);
 107 }
 108
 109 static inline bool
 110 is_valid_windows_filename_char(utf16lechar c)
 111 {
 112         return le16_to_cpu(c) > 31 &&
 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('?') &&
 122                 c != cpu_to_le16('*');
 123 }
 124
 125 /* Is the character valid in a filename on the current platform? */
 126 static inline bool
 127 is_valid_filename_char(utf16lechar c)
 128 {
 129 #ifdef __WIN32__
 130         return is_valid_windows_filename_char(c);
 131 #else
 132         return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
 133 #endif
 134 }
 135
 136 /* Generate a random filename and return its length. */
 137 static int
 138 generate_random_filename(utf16lechar name[], int max_len,
 139                          struct generation_context *ctx)
 140 {
 141         int len;
 142
 143         /* Choose the length of the name. */
 144         switch (rand32() % 8) {
 145         default:
 146                 /* short name  */
 147                 len = 1 + (rand32() % 6);
 148                 break;
 149         case 2:
 150         case 3:
 151         case 4:
 152                 /* medium-length name  */
 153                 len = 7 + (rand32() % 8);
 154                 break;
 155         case 5:
 156         case 6:
 157                 /* long name  */
 158                 len = 15 + (rand32() % 15);
 159                 break;
 160         case 7:
 161                 /* very long name  */
 162                 len = 30 + (rand32() % 90);
 163                 break;
 164         }
 165         len = min(len, max_len);
 166
 167 retry:
 168         /* Generate the characters in the name. */
 169         for (int i = 0; i < len; i++) {
 170                 do {
 171                         name[i] = rand16();
 172                 } while (!is_valid_filename_char(name[i]));
 173         }
 174
 175         /* Add a null terminator. */
 176         name[len] = cpu_to_le16('\0');
 177
 178         /* Don't generate . and .. */
 179         if (name[0] == cpu_to_le16('.') &&
 180             (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
 181                 goto retry;
 182
 183         return len;
 184 }
 185
 186 /* The set of characters which are valid in short filenames. */
 187 static const char valid_short_name_chars[] = {
 188         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 189         'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
 190         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 191         '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
 192         '}', '~',
 193         /* Note: Windows does not allow space and 128-255 in short filenames
 194          * (tested on both NTFS and FAT). */
 195 };
 196
 197 static int
 198 generate_short_name_component(utf16lechar p[], int len)
 199 {
 200         for (int i = 0; i < len; i++) {
 201                 char c = valid_short_name_chars[rand32() %
 202                                                 ARRAY_LEN(valid_short_name_chars)];
 203                 p[i] = cpu_to_le16(c);
 204         }
 205         return len;
 206 }
 207
 208 /* Generate a random short (8.3) filename and return its length.
 209  * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
 210 static int
 211 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
 212 {
 213         /*
 214          * Legal short names on Windows consist of 1 to 8 characters, optionally
 215          * followed by a dot then 1 to 3 more characters.  Only certain
 216          * characters are allowed.
 217          */
 218         int base_len = 1 + (rand32() % 8);
 219         int ext_len = rand32() % 4;
 220         int total_len;
 221
 222         base_len = generate_short_name_component(name, base_len);
 223
 224         if (ext_len) {
 225                 name[base_len] = cpu_to_le16('.');
 226                 ext_len = generate_short_name_component(&name[base_len + 1],
 227                                                         ext_len);
 228                 total_len = base_len + 1 + ext_len;
 229         } else {
 230                 total_len = base_len;
 231         }
 232         name[total_len] = cpu_to_le16('\0');
 233         return total_len;
 234 }
 235
 236
 237 static const struct {
 238         u8 num_subauthorities;
 239         u64 identifier_authority;
 240         u32 subauthorities[6];
 241 } common_sids[] = {
 242         { 1, 0, {0}}, /* NULL_SID  */
 243         { 1, 1, {0}}, /* WORLD_SID */
 244         { 1, 2, {0}}, /* LOCAL_SID */
 245         { 1, 3, {0}}, /* CREATOR_OWNER_SID */
 246         { 1, 3, {1}}, /* CREATOR_GROUP_SID */
 247         { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
 248         { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
 249         // { 0, 5, {}},  /* NT_AUTHORITY_SID */
 250         { 1, 5, {1}}, /* DIALUP_SID */
 251         { 1, 5, {2}}, /* NETWORK_SID */
 252         { 1, 5, {3}}, /* BATCH_SID */
 253         { 1, 5, {4}}, /* INTERACTIVE_SID */
 254         { 1, 5, {6}}, /* SERVICE_SID */
 255         { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
 256         { 1, 5, {8}}, /* PROXY_SID */
 257         { 1, 5, {9}}, /* SERVER_LOGON_SID */
 258         { 1, 5, {10}}, /* SELF_SID */
 259         { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
 260         { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
 261         { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
 262         { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
 263         { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
 264         { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
 265         { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer  */
 266         { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS  */
 267 };
 268
 269 /* Generate a SID and return its size in bytes.  */
 270 static size_t
 271 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
 272 {
 273         u32 r = rand32();
 274
 275         sid->revision = 1;
 276
 277         if (r & 1) {
 278                 /* Common SID  */
 279                 r = (r >> 1) % ARRAY_LEN(common_sids);
 280
 281                 sid->sub_authority_count = common_sids[r].num_subauthorities;
 282                 for (int i = 0; i < 6; i++) {
 283                         sid->identifier_authority[i] =
 284                                 common_sids[r].identifier_authority >> (40 - i * 8);
 285                 }
 286                 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
 287                         sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
 288         } else {
 289                 /* Random SID  */
 290
 291                 sid->sub_authority_count = 1 + ((r >> 1) % 15);
 292
 293                 for (int i = 0; i < 6; i++)
 294                         sid->identifier_authority[i] = rand8();
 295
 296                 for (int i = 0; i < sid->sub_authority_count; i++)
 297                         sid->sub_authority[i] = cpu_to_le32(rand32());
 298         }
 299         return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
 300 }
 301
 302 /* Generate an ACL and return its size in bytes.  */
 303 static size_t
 304 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
 305 {
 306         u8 *p;
 307         u16 ace_count;
 308
 309         ace_count = rand32() % 16;
 310
 311         acl->revision = 2;
 312         acl->sbz1 = 0;
 313         acl->ace_count = cpu_to_le16(ace_count);
 314         acl->sbz2 = 0;
 315
 316         p = (u8 *)(acl + 1);
 317
 318         for (int i = 0; i < ace_count; i++) {
 319                 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
 320
 321                 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
 322                  * same for all  */
 323                 if (dacl)
 324                         ace->hdr.type = rand32() % 2;
 325                 else
 326                         ace->hdr.type = 2;
 327                 ace->hdr.flags = rand8();
 328                 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
 329
 330                 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
 331                         generate_random_sid(&ace->sid, ctx);
 332                 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
 333         }
 334
 335         acl->acl_size = cpu_to_le16(p - (u8 *)acl);
 336         return p - (u8 *)acl;
 337 }
 338
 339 /* Generate a security descriptor and return its size in bytes.  */
 340 static size_t
 341 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
 342 {
 343         wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
 344         u16 control;
 345         u8 *p;
 346
 347         control = rand16();
 348
 349         control &= (wimlib_SE_DACL_AUTO_INHERITED |
 350                     wimlib_SE_SACL_AUTO_INHERITED);
 351
 352         control |= wimlib_SE_SELF_RELATIVE |
 353                    wimlib_SE_DACL_PRESENT |
 354                    wimlib_SE_SACL_PRESENT;
 355
 356         desc->revision = 1;
 357         desc->sbz1 = 0;
 358         desc->control = cpu_to_le16(control);
 359
 360         p = (u8 *)(desc + 1);
 361
 362         desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
 363         p += generate_random_sid((wimlib_SID *)p, ctx);
 364
 365         desc->group_offset = cpu_to_le32(p - (u8 *)desc);
 366         p += generate_random_sid((wimlib_SID *)p, ctx);
 367
 368         if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
 369                 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
 370                 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
 371         } else {
 372                 desc->dacl_offset = cpu_to_le32(0);
 373         }
 374
 375         if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
 376                 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
 377                 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
 378         } else {
 379                 desc->sacl_offset = cpu_to_le32(0);
 380         }
 381
 382         return p - (u8 *)desc;
 383 }
 384
 385 static bool
 386 am_root(void)
 387 {
 388 #ifdef __WIN32__
 389         return false;
 390 #else
 391         return (getuid() == 0);
 392 #endif
 393 }
 394
 395 static u32
 396 generate_uid(void)
 397 {
 398 #ifdef __WIN32__
 399         return 0;
 400 #else
 401         if (am_root())
 402                 return rand32();
 403         return getuid();
 404 #endif
 405 }
 406
 407 static u32
 408 generate_gid(void)
 409 {
 410 #ifdef __WIN32__
 411         return 0;
 412 #else
 413         if (am_root())
 414                 return rand32();
 415         return getgid();
 416 #endif
 417 }
 418
 419 #ifdef __WIN32__
 420 #  ifndef S_IFLNK
 421 #    define S_IFLNK  0120000
 422 #  endif
 423 #  ifndef S_IFSOCK
 424 #    define S_IFSOCK 0140000
 425 #  endif
 426 #endif
 427
 428 static int
 429 set_random_unix_metadata(struct wim_inode *inode)
 430 {
 431         struct wimlib_unix_data dat;
 432
 433         dat.uid = generate_uid();
 434         dat.gid = generate_gid();
 435         if (inode_is_symlink(inode))
 436                 dat.mode = S_IFLNK | 0777;
 437         else if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)
 438                 dat.mode = S_IFDIR | 0700 | (rand32() % 07777);
 439         else if (is_zero_hash(inode_get_hash_of_unnamed_data_stream(inode)) &&
 440                  randbool() && am_root())
 441         {
 442                 dat.mode = rand32() % 07777;
 443                 switch (rand32() % 4) {
 444                 case 0:
 445                         dat.mode |= S_IFIFO;
 446                         break;
 447                 case 1:
 448                         dat.mode |= S_IFCHR;
 449                         dat.rdev = 261; /* /dev/zero */
 450                         break;
 451                 case 2:
 452                         dat.mode |= S_IFBLK;
 453                         dat.rdev = 261; /* /dev/zero */
 454                         break;
 455                 default:
 456                         dat.mode |= S_IFSOCK;
 457                         break;
 458                 }
 459         } else {
 460                 dat.mode = S_IFREG | 0400 | (rand32() % 07777);
 461         }
 462         dat.rdev = 0;
 463
 464         if (!inode_set_unix_data(inode, &dat, UNIX_DATA_ALL))
 465                 return WIMLIB_ERR_NOMEM;
 466
 467         return 0;
 468 }
 469
 470 static noinline_for_stack int
 471 set_random_xattrs(struct wim_inode *inode)
 472 {
 473         int num_xattrs = 1 + rand32() % 16;
 474         char entries[8192];
 475         struct wim_xattr_entry *entry = (void *)entries;
 476         size_t entries_size;
 477         struct wimlib_unix_data unix_data;
 478         const char *prefix = "user.";
 479         static const char capability_name[] = "security.capability";
 480         bool generated_capability_xattr = false;
 481
 482         /*
 483          * On Linux, xattrs in the "user" namespace are only permitted on
 484          * regular files and directories.  For other types of files we can use
 485          * the "trusted" namespace, but this requires root.
 486          */
 487         if (inode_is_symlink(inode) ||
 488             (inode_get_unix_data(inode, &unix_data) &&
 489              !S_ISREG(unix_data.mode) && !S_ISDIR(unix_data.mode)))
 490         {
 491                 if (!am_root())
 492                         return 0;
 493                 prefix = "trusted.";
 494         }
 495
 496         for (int i = 0; i < num_xattrs; i++) {
 497                 int value_len = rand32() % 64;
 498                 u8 *p;
 499
 500                 entry->value_len = cpu_to_le16(value_len);
 501                 entry->flags = 0;
 502
 503                 if (rand32() % 16 == 0 && am_root() &&
 504                     !generated_capability_xattr) {
 505                         int name_len = sizeof(capability_name) - 1;
 506                         entry->name_len = name_len;
 507                         p = mempcpy(entry->name, capability_name, name_len + 1);
 508                         generated_capability_xattr = true;
 509                 } else {
 510                         int name_len = 1 + rand32() % 64;
 511
 512                         entry->name_len = strlen(prefix) + name_len;
 513                         p = mempcpy(entry->name, prefix, strlen(prefix));
 514                         *p++ = 'a' + i;
 515                         for (int j = 1; j < name_len; j++) {
 516                                 do {
 517                                         *p = rand8();
 518                                 } while (*p == '\0');
 519                                 p++;
 520                         }
 521                         *p++ = '\0';
 522                 }
 523                 for (int j = 0; j < value_len; j++)
 524                         *p++ = rand8();
 525
 526                 entry = (void *)p;
 527         }
 528
 529         entries_size = (char *)entry - entries;
 530         wimlib_assert(entries_size > 0 && entries_size <= sizeof(entries));
 531
 532         if (!inode_set_xattrs(inode, entries, entries_size))
 533                 return WIMLIB_ERR_NOMEM;
 534
 535         return 0;
 536 }
 537
 538 static int
 539 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
 540 {
 541         u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
 542                                   FILE_ATTRIBUTE_HIDDEN |
 543                                   FILE_ATTRIBUTE_SYSTEM |
 544                                   FILE_ATTRIBUTE_ARCHIVE |
 545                                   FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
 546                                   FILE_ATTRIBUTE_COMPRESSED |
 547                                   FILE_ATTRIBUTE_SPARSE_FILE));
 548
 549         /* File attributes  */
 550         inode->i_attributes |= attrib;
 551
 552         /* Timestamps  */
 553         inode->i_creation_time = generate_random_timestamp();
 554         inode->i_last_access_time = generate_random_timestamp();
 555         inode->i_last_write_time = generate_random_timestamp();
 556
 557         /* Security descriptor  */
 558         if (randbool()) {
 559                 char desc[8192] _aligned_attribute(8);
 560                 size_t size;
 561
 562                 size = generate_random_security_descriptor(desc, ctx);
 563
 564                 wimlib_assert(size <= sizeof(desc));
 565
 566                 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
 567                                                      desc, size);
 568                 if (unlikely(inode->i_security_id < 0))
 569                         return WIMLIB_ERR_NOMEM;
 570         }
 571
 572         /* Object ID  */
 573         if (rand32() % 32 == 0) {
 574                 struct wimlib_object_id object_id;
 575
 576                 for (int i = 0; i < sizeof(object_id); i++)
 577                         *((u8 *)&object_id + i) = rand8();
 578                 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
 579                         return WIMLIB_ERR_NOMEM;
 580         }
 581
 582         /* Standard UNIX permissions and special files */
 583         if (rand32() % 16 == 0) {
 584                 int ret = set_random_unix_metadata(inode);
 585                 if (ret)
 586                         return ret;
 587         }
 588
 589         /* Extended attributes */
 590         if (rand32() % 32 == 0) {
 591                 int ret = set_random_xattrs(inode);
 592                 if (ret)
 593                         return ret;
 594         }
 595
 596         return 0;
 597
 598 }
 599
 600 /* Choose a random size for generated file data.  We want to usually generate
 601  * empty, small, or medium files, but occasionally generate large files.  */
 602 static size_t
 603 select_stream_size(struct generation_context *ctx)
 604 {
 605         if (ctx->metadata_only)
 606                 return 0;
 607
 608         switch (rand32() % 2048) {
 609         default:
 610                 /* Empty  */
 611                 return 0;
 612         case 600 ... 799:
 613                 /* Microscopic  */
 614                 return rand32() % 64;
 615         case 800 ... 1319:
 616                 /* Tiny  */
 617                 return rand32() % 4096;
 618         case 1320 ... 1799:
 619                 /* Small  */
 620                 return rand32() % 32768;
 621         case 1800 ... 2046:
 622                 /* Medium  */
 623                 return rand32() % 262144;
 624         case 2047:
 625                 /* Large  */
 626                 return rand32() % 134217728;
 627         }
 628 }
 629
 630 /* Fill 'buffer' with 'size' bytes of "interesting" file data.  */
 631 static void
 632 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
 633 {
 634         size_t mask = -1;
 635         size_t num_byte_fills = rand32() % 256;
 636
 637         if (size == 0)
 638                 return;
 639
 640         /* Start by initializing to a random byte */
 641         memset(buffer, rand32() % 256, size);
 642
 643         /* Add some random bytes in some random places */
 644         for (size_t i = 0; i < num_byte_fills; i++) {
 645                 u8 b = rand8();
 646
 647                 size_t count = ((double)size / (double)num_byte_fills) *
 648                                 ((double)rand32() / 2e9);
 649                 size_t offset = rand32() & ~mask;
 650
 651                 while (count--) {
 652                         buffer[(offset +
 653                                 ((rand32()) & mask)) % size] = b;
 654                 }
 655
 656
 657                 if (rand32() % 4 == 0)
 658                         mask = (size_t)-1 << rand32() % 4;
 659         }
 660
 661         /* Sometimes add a wave pattern */
 662         if (rand32() % 8 == 0) {
 663                 double magnitude = rand32() % 128;
 664                 double scale = 1.0 / (1 + (rand32() % 256));
 665
 666                 for (size_t i = 0; i < size; i++)
 667                         buffer[i] += (int)(magnitude * cos(i * scale));
 668         }
 669
 670         /* Sometimes add some zero regions (holes) */
 671         if (rand32() % 4 == 0) {
 672                 size_t num_holes = 1 + (rand32() % 16);
 673                 for (size_t i = 0; i < num_holes; i++) {
 674                         size_t hole_offset = rand32() % size;
 675                         size_t hole_len = min(size - hole_offset,
 676                                               size / (1 + (rand32() % 16)));
 677                         memset(&buffer[hole_offset], 0, hole_len);
 678                 }
 679         }
 680 }
 681
 682 static noinline_for_stack int
 683 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
 684 {
 685         struct reparse_buffer_disk rpbuf;
 686         size_t rpdatalen;
 687
 688         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 689
 690         if (randbool()) {
 691                 /* Symlink */
 692                 int target_nchars;
 693                 utf16lechar *targets = (utf16lechar *)rpbuf.link.symlink.data;
 694
 695                 inode->i_reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
 696
 697                 target_nchars = generate_random_filename(targets, 255, ctx);
 698
 699                 rpbuf.link.substitute_name_offset = cpu_to_le16(0);
 700                 rpbuf.link.substitute_name_nbytes = cpu_to_le16(2*target_nchars);
 701                 rpbuf.link.print_name_offset = cpu_to_le16(2*(target_nchars + 1));
 702                 rpbuf.link.print_name_nbytes = cpu_to_le16(2*target_nchars);
 703                 targets[target_nchars] = cpu_to_le16(0);
 704                 memcpy(&targets[target_nchars + 1], targets, 2*target_nchars);
 705                 targets[target_nchars + 1 + target_nchars] = cpu_to_le16(0);
 706
 707                 rpbuf.link.symlink.flags = cpu_to_le32(SYMBOLIC_LINK_RELATIVE);
 708                 rpdatalen = ((u8 *)targets - rpbuf.rpdata) +
 709                                 2*(target_nchars + 1 + target_nchars + 1);
 710         } else {
 711                 rpdatalen = select_stream_size(ctx) % REPARSE_DATA_MAX_SIZE;
 712                 generate_data(rpbuf.rpdata, rpdatalen, ctx);
 713
 714                 if (rpdatalen >= GUID_SIZE && randbool()) {
 715                         /* Non-Microsoft reparse tag (16-byte GUID required)  */
 716                         u8 *guid = rpbuf.rpdata;
 717                         guid[6] = (guid[6] & 0x0F) | 0x40;
 718                         guid[8] = (guid[8] & 0x3F) | 0x80;
 719                         inode->i_reparse_tag = 0x00000100;
 720                 } else {
 721                         /* Microsoft reparse tag  */
 722                         inode->i_reparse_tag = 0x80000000;
 723                 }
 724                 inode->i_rp_reserved = rand16();
 725         }
 726
 727         wimlib_assert(rpdatalen < REPARSE_DATA_MAX_SIZE);
 728
 729         if (!inode_add_stream_with_data(inode, STREAM_TYPE_REPARSE_POINT,
 730                                         NO_STREAM_NAME, rpbuf.rpdata,
 731                                         rpdatalen, ctx->params->blob_table))
 732                 return WIMLIB_ERR_NOMEM;
 733
 734         return 0;
 735 }
 736
 737 static int
 738 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
 739                        const utf16lechar *stream_name)
 740 {
 741         void *buffer = NULL;
 742         size_t size;
 743         int ret;
 744
 745         size = select_stream_size(ctx);
 746         if (size) {
 747                 buffer = MALLOC(size);
 748                 if (!buffer)
 749                         return WIMLIB_ERR_NOMEM;
 750                 generate_data(buffer, size, ctx);
 751         }
 752
 753         ret = 0;
 754         if (!inode_add_stream_with_data(inode, STREAM_TYPE_DATA, stream_name,
 755                                         buffer, size, ctx->params->blob_table))
 756                 ret = WIMLIB_ERR_NOMEM;
 757         FREE(buffer);
 758         return ret;
 759 }
 760
 761 static int
 762 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
 763 {
 764         int ret;
 765         u32 r;
 766
 767         /* Reparse point (sometimes)  */
 768         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
 769                 ret = set_random_reparse_point(inode, ctx);
 770                 if (ret)
 771                         return ret;
 772         }
 773
 774         /* Unnamed data stream (nondirectories and non-symlinks only)  */
 775         if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) &&
 776             !inode_is_symlink(inode)) {
 777                 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
 778                 if (ret)
 779                         return ret;
 780         }
 781
 782         /* Named data streams (sometimes)  */
 783         r = rand32() % 256;
 784         if (r > 230) {
 785                 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
 786                 r -= 230;
 787                 while (r--) {
 788                         ret = add_random_data_stream(inode, ctx, stream_name);
 789                         if (ret)
 790                                 return ret;
 791                         stream_name[0] += cpu_to_le16(1);
 792                 }
 793         }
 794
 795         return 0;
 796 }
 797
 798 static u64
 799 select_inode_number(struct generation_context *ctx)
 800 {
 801         const struct wim_inode_table *table = ctx->params->inode_table;
 802         const struct hlist_head *head;
 803         const struct wim_inode *inode;
 804
 805         head = &table->array[rand32() % table->capacity];
 806         hlist_for_each_entry(inode, head, i_hlist_node)
 807                 if (randbool())
 808                         return inode->i_ino;
 809
 810         return rand32();
 811 }
 812
 813 static u32
 814 select_num_children(u32 depth, struct generation_context *ctx)
 815 {
 816         const double b = 1.01230;
 817         u32 r = rand32() % 500;
 818         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
 819                 (2 - exp(0.04/depth));
 820 }
 821
 822 static bool
 823 is_name_valid_in_win32_namespace(const utf16lechar *name)
 824 {
 825         const utf16lechar *p;
 826
 827         static const char * const reserved_names[] = {
 828                  "CON",  "PRN",  "AUX",  "NUL",
 829                  "COM1", "COM2", "COM3", "COM4", "COM5",
 830                  "COM6", "COM7", "COM8", "COM9",
 831                  "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
 832                  "LPT6", "LPT7", "LPT8", "LPT9",
 833         };
 834
 835         /* The name must be nonempty. */
 836         if (!name || !*name)
 837                 return false;
 838
 839         /* All characters must be valid on Windows. */
 840         for (p = name; *p; p++)
 841                 if (!is_valid_windows_filename_char(*p))
 842                         return false;
 843
 844         /* Note: a trailing dot or space is permitted, even though on Windows
 845          * such a file can only be accessed using a WinNT-style path. */
 846
 847         /* The name can't be one of the reserved names or be a reserved name
 848          * with an extension.  Case insensitive. */
 849         for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
 850                 for (size_t j = 0; ; j++) {
 851                         u16 c1 = le16_to_cpu(name[j]);
 852                         u16 c2 = reserved_names[i][j];
 853                         if (c2 == '\0') {
 854                                 if (c1 == '\0' || c1 == '.')
 855                                         return false;
 856                                 break;
 857                         }
 858                         if (upcase[c1] != upcase[c2])
 859                                 break;
 860                 }
 861         }
 862
 863         return true;
 864 }
 865
 866 static int
 867 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 868                       struct generation_context *ctx)
 869 {
 870         utf16lechar name[12 + 1];
 871         int name_len;
 872         u32 hash;
 873         struct wim_dentry **bucket;
 874
 875         /* If the long name is not allowed in the Win32 namespace, then it
 876          * cannot be assigned a corresponding short name.  */
 877         if (!is_name_valid_in_win32_namespace(child->d_name))
 878                 return 0;
 879
 880 retry:
 881         /* Don't select a short name that is already used by a long name within
 882          * the same directory.  */
 883         do {
 884                 name_len = generate_random_short_name(name, ctx);
 885         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 886                                                     WIMLIB_CASE_INSENSITIVE));
 887
 888
 889         /* Don't select a short name that is already used by another short name
 890          * within the same directory.  */
 891         hash = 0;
 892         for (const utf16lechar *p = name; *p; p++)
 893                 hash = (hash * 31) + *p;
 894         FREE(child->d_short_name);
 895         child->d_short_name = memdup(name, (name_len + 1) * 2);
 896         child->d_short_name_nbytes = name_len * 2;
 897
 898         if (!child->d_short_name)
 899                 return WIMLIB_ERR_NOMEM;
 900
 901         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 902
 903         for (struct wim_dentry *d = *bucket; d != NULL;
 904              d = d->d_next_extraction_alias) {
 905                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
 906                                          d->d_short_name, d->d_short_name_nbytes / 2,
 907                                          true)) {
 908                         goto retry;
 909                 }
 910         }
 911
 912         if (!is_name_valid_in_win32_namespace(child->d_short_name))
 913                 goto retry;
 914
 915         child->d_next_extraction_alias = *bucket;
 916         *bucket = child;
 917         return 0;
 918 }
 919
 920 static bool
 921 inode_has_short_name(const struct wim_inode *inode)
 922 {
 923         const struct wim_dentry *dentry;
 924
 925         inode_for_each_dentry(dentry, inode)
 926                 if (dentry_has_short_name(dentry))
 927                         return true;
 928
 929         return false;
 930 }
 931
 932 static int
 933 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 934                                struct generation_context *ctx)
 935 {
 936         u32 num_children = select_num_children(depth, ctx);
 937         struct wim_dentry *child;
 938         int ret;
 939
 940         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 941
 942         /* Generate 'num_children' dentries within 'dir'.  Some may be
 943          * directories themselves.  */
 944
 945         for (u32 i = 0; i < num_children; i++) {
 946
 947                 /* Generate the next child dentry.  */
 948                 struct wim_inode *inode;
 949                 u64 ino;
 950                 bool is_directory = (rand32() % 16 <= 6);
 951                 bool is_reparse = (rand32() % 8 == 0);
 952                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
 953                 int name_len;
 954                 struct wim_dentry *duplicate;
 955
 956                 /*
 957                  * Select an inode number for the new file.  Sometimes choose an
 958                  * existing inode number (i.e. create a hard link).  However,
 959                  * wimlib intentionally doesn't honor directory hard links, and
 960                  * reparse points cannot be represented in the WIM file format
 961                  * at all; so don't create hard links for such files.
 962                  */
 963                 if (is_directory || is_reparse)
 964                         ino = 0;
 965                 else
 966                         ino = select_inode_number(ctx);
 967
 968                 /* Create the dentry. */
 969                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
 970                                              ino, 0, ino == 0, &child);
 971                 if (ret)
 972                         return ret;
 973
 974                 /* Choose a filename that is unique within the directory.*/
 975                 do {
 976                         name_len = generate_random_filename(name,
 977                                                             ARRAY_LEN(name) - 1,
 978                                                             ctx);
 979                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 980                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 981
 982                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
 983                 if (ret) {
 984                         free_dentry(child);
 985                         return ret;
 986                 }
 987
 988                 /* Add the dentry to the directory. */
 989                 duplicate = dentry_add_child(dir, child);
 990                 wimlib_assert(!duplicate);
 991
 992                 inode = child->d_inode;
 993
 994                 if (inode->i_nlink > 1)  /* Existing inode?  */
 995                         continue;
 996
 997                 /* New inode; set attributes, metadata, and data.  */
 998
 999                 if (is_directory)
1000                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
1001                 if (is_reparse)
1002                         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
1003
1004                 ret = set_random_streams(inode, ctx);
1005                 if (ret)
1006                         return ret;
1007
1008                 ret = set_random_metadata(inode, ctx);
1009                 if (ret)
1010                         return ret;
1011
1012                 /* Recurse if it's a directory.  */
1013                 if (is_directory && !is_reparse) {
1014                         ret = generate_dentry_tree_recursive(child, depth + 1,
1015                                                              ctx);
1016                         if (ret)
1017                                 return ret;
1018                 }
1019         }
1020
1021         for_dentry_child(child, dir) {
1022                 /* sometimes generate a unique short name  */
1023                 if (randbool() && !inode_has_short_name(child->d_inode)) {
1024                         ret = set_random_short_name(dir, child, ctx);
1025                         if (ret)
1026                                 return ret;
1027                 }
1028         }
1029
1030         return 0;
1031 }
1032
1033 int
1034 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
1035                      struct scan_params *params)
1036 {
1037         int ret;
1038         struct wim_dentry *root = NULL;
1039         struct generation_context ctx = {
1040                 .params = params,
1041         };
1042
1043         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
1044
1045         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
1046         if (!ret) {
1047                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
1048                 ret = set_random_streams(root->d_inode, &ctx);
1049         }
1050         if (!ret)
1051                 ret = set_random_metadata(root->d_inode, &ctx);
1052         if (!ret)
1053                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
1054         if (!ret)
1055                 *root_ret = root;
1056         else
1057                 free_dentry_tree(root, params->blob_table);
1058         return ret;
1059 }
1060
1061 /*----------------------------------------------------------------------------*
1062  *                            File tree comparison                            *
1063  *----------------------------------------------------------------------------*/
1064
1065 #define INDEX_NODE_TO_DENTRY(node)      \
1066         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
1067
1068 static struct wim_dentry *
1069 dentry_first_child(struct wim_dentry *dentry)
1070 {
1071         return INDEX_NODE_TO_DENTRY(
1072                         avl_tree_first_in_order(dentry->d_inode->i_children));
1073 }
1074
1075 static struct wim_dentry *
1076 dentry_next_sibling(struct wim_dentry *dentry)
1077 {
1078         return INDEX_NODE_TO_DENTRY(
1079                         avl_tree_next_in_order(&dentry->d_index_node));
1080 }
1081
1082 /*
1083  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
1084  * tree 'd2', considering long and short filenames.  In addition, set
1085  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
1086  * other tree, and set 'i_corresponding' of each inode to point to the
1087  * unverified corresponding inode in the other tree.
1088  */
1089 static int
1090 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
1091                                    int cmp_flags)
1092 {
1093         struct wim_dentry *child1;
1094         struct wim_dentry *child2;
1095         int ret;
1096
1097         /* Compare long filenames, case sensitively.  */
1098         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
1099                                 d2->d_name, d2->d_name_nbytes / 2,
1100                                 false))
1101         {
1102                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
1103                       dentry_full_path(d1), dentry_full_path(d2));
1104                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1105         }
1106
1107         /* Compare short filenames, case insensitively.  */
1108         if (!(d2->d_short_name_nbytes == 0 &&
1109               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
1110             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
1111                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
1112                                 true))
1113         {
1114                 ERROR("Short name mismatch; path=\"%"TS"\"",
1115                       dentry_full_path(d1));
1116                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1117         }
1118
1119         /* Match up the dentries  */
1120         d1->d_corresponding = d2;
1121         d2->d_corresponding = d1;
1122
1123         /* Match up the inodes (may overwrite previous value)  */
1124         d1->d_inode->i_corresponding = d2->d_inode;
1125         d2->d_inode->i_corresponding = d1->d_inode;
1126
1127         /* Process children  */
1128         child1 = dentry_first_child(d1);
1129         child2 = dentry_first_child(d2);
1130         while (child1 || child2) {
1131
1132                 if (!child1 || !child2) {
1133                         ERROR("Child count mismatch; "
1134                               "path1=\"%"TS"\", path2=\"%"TS"\"",
1135                               dentry_full_path(d1), dentry_full_path(d2));
1136                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1137                 }
1138
1139                 /* Recurse on this pair of children.  */
1140                 ret = calc_corresponding_files_recursive(child1, child2,
1141                                                          cmp_flags);
1142                 if (ret)
1143                         return ret;
1144
1145                 /* Continue to the next pair of children.  */
1146                 child1 = dentry_next_sibling(child1);
1147                 child2 = dentry_next_sibling(child2);
1148         }
1149         return 0;
1150 }
1151
1152 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
1153  * even if the images being compared are different.  */
1154 static void
1155 assert_inodes_sane(const struct wim_image_metadata *imd)
1156 {
1157         const struct wim_inode *inode;
1158         const struct wim_dentry *dentry;
1159         size_t link_count;
1160
1161         image_for_each_inode(inode, imd) {
1162                 link_count = 0;
1163                 inode_for_each_dentry(dentry, inode) {
1164                         wimlib_assert(dentry->d_inode == inode);
1165                         link_count++;
1166                 }
1167                 wimlib_assert(link_count > 0);
1168                 wimlib_assert(link_count == inode->i_nlink);
1169                 wimlib_assert(inode->i_corresponding != NULL);
1170         }
1171 }
1172
1173 static int
1174 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1175 {
1176         /* My inode is my corresponding dentry's inode's corresponding inode,
1177          * and my inode's corresponding inode is my corresponding dentry's
1178          * inode.  */
1179         const struct wim_inode *a = dentry->d_inode;
1180         const struct wim_inode *b = dentry->d_corresponding->d_inode;
1181         if (a == b->i_corresponding && a->i_corresponding == b)
1182                 return 0;
1183         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1184         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1185 }
1186
1187 static const struct {
1188         u32 flag;
1189         const char *name;
1190 } file_attr_flags[] = {
1191         {FILE_ATTRIBUTE_READONLY,            "READONLY"},
1192         {FILE_ATTRIBUTE_HIDDEN,              "HIDDEN"},
1193         {FILE_ATTRIBUTE_SYSTEM,              "SYSTEM"},
1194         {FILE_ATTRIBUTE_DIRECTORY,           "DIRECTORY"},
1195         {FILE_ATTRIBUTE_ARCHIVE,             "ARCHIVE"},
1196         {FILE_ATTRIBUTE_DEVICE,              "DEVICE"},
1197         {FILE_ATTRIBUTE_NORMAL,              "NORMAL"},
1198         {FILE_ATTRIBUTE_TEMPORARY,           "TEMPORARY"},
1199         {FILE_ATTRIBUTE_SPARSE_FILE,         "SPARSE_FILE"},
1200         {FILE_ATTRIBUTE_REPARSE_POINT,       "REPARSE_POINT"},
1201         {FILE_ATTRIBUTE_COMPRESSED,          "COMPRESSED"},
1202         {FILE_ATTRIBUTE_OFFLINE,             "OFFLINE"},
1203         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1204         {FILE_ATTRIBUTE_ENCRYPTED,           "ENCRYPTED"},
1205         {FILE_ATTRIBUTE_VIRTUAL,             "VIRTUAL"},
1206 };
1207
1208 static int
1209 cmp_attributes(const struct wim_inode *inode1,
1210                const struct wim_inode *inode2, int cmp_flags)
1211 {
1212         const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1213         const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1214         const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1215
1216         /* NORMAL may change, but it must never be set along with other
1217          * attributes. */
1218         if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1219             (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1220                 goto mismatch;
1221
1222         /* DIRECTORY may change in UNIX mode for symlinks. */
1223         if (changed & FILE_ATTRIBUTE_DIRECTORY) {
1224                 if (!(inode_is_symlink(inode1) &&
1225                       (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)))
1226                         goto mismatch;
1227         }
1228
1229         /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1230          * symlink. */
1231         if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1232             !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1233               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1234               !inode_is_symlink(inode1)))
1235                 goto mismatch;
1236
1237         /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1238          * mode if the inode is a directory. */
1239         if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1240             !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1241               ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1242                              WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1243                ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1244                 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1245                 goto mismatch;
1246
1247         /* COMPRESSED may change in UNIX and NTFS-3G modes.  (It *should* be
1248          * preserved in NTFS-3G mode, but it's not implemented yet.) */
1249         if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1250             !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1251                            WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1252                 goto mismatch;
1253
1254         /* All other attributes can change in UNIX mode, but not in any other
1255          * mode. */
1256         if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1257                          FILE_ATTRIBUTE_DIRECTORY |
1258                          FILE_ATTRIBUTE_REPARSE_POINT |
1259                          FILE_ATTRIBUTE_SPARSE_FILE |
1260                          FILE_ATTRIBUTE_COMPRESSED)) &&
1261             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1262                 goto mismatch;
1263
1264         return 0;
1265
1266 mismatch:
1267         ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1268               inode_any_full_path(inode1), inode1->i_attributes,
1269               inode2->i_attributes);
1270         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1271                 u32 flag = file_attr_flags[i].flag;
1272                 if (changed & flag) {
1273                         fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1274                                 file_attr_flags[i].name,
1275                                 (set & flag) ? "set" : "cleared");
1276                 }
1277         }
1278         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1279 }
1280
1281 static int
1282 cmp_object_ids(const struct wim_inode *inode1,
1283                const struct wim_inode *inode2, int cmp_flags)
1284 {
1285         const void *objid1, *objid2;
1286         u32 len1, len2;
1287
1288         objid1 = inode_get_object_id(inode1, &len1);
1289         objid2 = inode_get_object_id(inode2, &len2);
1290
1291         if (!objid1 && !objid2)
1292                 return 0;
1293
1294         if (objid1 && !objid2) {
1295                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1296                         return 0;
1297                 ERROR("%"TS" unexpectedly lost its object ID",
1298                       inode_any_full_path(inode1));
1299                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1300         }
1301
1302         if (!objid1 && objid2) {
1303                 ERROR("%"TS" unexpectedly gained an object ID",
1304                       inode_any_full_path(inode1));
1305                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1306         }
1307
1308         if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1309                 ERROR("Object ID of %"TS" differs",
1310                       inode_any_full_path(inode1));
1311                 fprintf(stderr, "objid1=");
1312                 print_byte_field(objid1, len1, stderr);
1313                 fprintf(stderr, "\nobjid2=");
1314                 print_byte_field(objid2, len2, stderr);
1315                 fprintf(stderr, "\n");
1316                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1317         }
1318
1319         return 0;
1320 }
1321
1322 static int
1323 cmp_unix_metadata(const struct wim_inode *inode1,
1324                   const struct wim_inode *inode2, int cmp_flags)
1325 {
1326         struct wimlib_unix_data dat1, dat2;
1327         bool present1, present2;
1328
1329         present1 = inode_get_unix_data(inode1, &dat1);
1330         present2 = inode_get_unix_data(inode2, &dat2);
1331
1332         if (!present1 && !present2)
1333                 return 0;
1334
1335         if (present1 && !present2) {
1336                 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1337                                  WIMLIB_CMP_FLAG_WINDOWS_MODE))
1338                         return 0;
1339                 ERROR("%"TS" unexpectedly lost its UNIX metadata",
1340                       inode_any_full_path(inode1));
1341                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1342         }
1343
1344         if (!present1 && present2) {
1345                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1346                         return 0;
1347                 ERROR("%"TS" unexpectedly gained UNIX metadata",
1348                       inode_any_full_path(inode1));
1349                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1350         }
1351
1352         if (memcmp(&dat1, &dat2, sizeof(dat1)) != 0) {
1353                 ERROR("UNIX metadata of %"TS" differs: "
1354                       "[uid=%u, gid=%u, mode=0%o, rdev=%u] vs. "
1355                       "[uid=%u, gid=%u, mode=0%o, rdev=%u]",
1356                       inode_any_full_path(inode1),
1357                       dat1.uid, dat1.gid, dat1.mode, dat1.rdev,
1358                       dat2.uid, dat2.gid, dat2.mode, dat2.rdev);
1359                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1360         }
1361
1362         return 0;
1363 }
1364
1365 static int
1366 cmp_xattr_names(const void *p1, const void *p2)
1367 {
1368         const struct wim_xattr_entry *entry1 = *(const struct wim_xattr_entry **)p1;
1369         const struct wim_xattr_entry *entry2 = *(const struct wim_xattr_entry **)p2;
1370         int res;
1371
1372         res = entry1->name_len - entry2->name_len;
1373         if (res)
1374                 return res;
1375
1376         return memcmp(entry1->name, entry2->name, entry1->name_len);
1377 }
1378
1379 /* Validate and sort by name a list of extended attributes */
1380 static int
1381 parse_xattrs(const void *xattrs, u32 len,
1382              const struct wim_xattr_entry *entries[],
1383              u32 *num_entries_p)
1384 {
1385         u32 limit = *num_entries_p;
1386         u32 num_entries = 0;
1387         const struct wim_xattr_entry *entry = xattrs;
1388
1389         while ((void *)entry < xattrs + len) {
1390                 if (!valid_xattr_entry(entry, xattrs + len - (void *)entry)) {
1391                         ERROR("Invalid xattr entry");
1392                         return WIMLIB_ERR_INVALID_XATTR;
1393                 }
1394                 if (num_entries >= limit) {
1395                         ERROR("Too many xattr entries");
1396                         return WIMLIB_ERR_INVALID_XATTR;
1397                 }
1398                 entries[num_entries++] = entry;
1399                 entry = xattr_entry_next(entry);
1400         }
1401
1402         if (num_entries == 0) {
1403                 ERROR("No xattr entries");
1404                 return WIMLIB_ERR_INVALID_XATTR;
1405         }
1406
1407         qsort(entries, num_entries, sizeof(entries[0]), cmp_xattr_names);
1408
1409         for (u32 i = 1; i < num_entries; i++) {
1410                 if (cmp_xattr_names(&entries[i - 1], &entries[i]) == 0) {
1411                         ERROR("Duplicate xattr names");
1412                         return WIMLIB_ERR_INVALID_XATTR;
1413                 }
1414         }
1415
1416         *num_entries_p = num_entries;
1417         return 0;
1418 }
1419
1420 static int
1421 cmp_xattrs(const struct wim_inode *inode1, const struct wim_inode *inode2,
1422            int cmp_flags)
1423 {
1424         const void *xattrs1, *xattrs2;
1425         u32 len1, len2;
1426
1427         xattrs1 = inode_get_xattrs(inode1, &len1);
1428         xattrs2 = inode_get_xattrs(inode2, &len2);
1429
1430         if (!xattrs1 && !xattrs2) {
1431                 return 0;
1432         } else if (xattrs1 && !xattrs2) {
1433                 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1434                                  WIMLIB_CMP_FLAG_WINDOWS_MODE))
1435                         return 0;
1436                 ERROR("%"TS" unexpectedly lost its xattrs",
1437                       inode_any_full_path(inode1));
1438                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1439         } else if (!xattrs1 && xattrs2) {
1440                 ERROR("%"TS" unexpectedly gained xattrs",
1441                       inode_any_full_path(inode1));
1442                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1443         } else {
1444                 const int max_entries = 64;
1445                 const struct wim_xattr_entry *entries1[max_entries];
1446                 const struct wim_xattr_entry *entries2[max_entries];
1447                 u32 xattr_count1 = max_entries;
1448                 u32 xattr_count2 = max_entries;
1449                 int ret;
1450
1451                 ret = parse_xattrs(xattrs1, len1, entries1, &xattr_count1);
1452                 if (ret) {
1453                         ERROR("%"TS": invalid xattrs",
1454                               inode_any_full_path(inode1));
1455                         return ret;
1456                 }
1457                 ret = parse_xattrs(xattrs2, len2, entries2, &xattr_count2);
1458                 if (ret) {
1459                         ERROR("%"TS": invalid xattrs",
1460                               inode_any_full_path(inode2));
1461                         return ret;
1462                 }
1463                 if (xattr_count1 != xattr_count2) {
1464                         ERROR("%"TS": number of xattrs changed.  had %u "
1465                               "before, now has %u", inode_any_full_path(inode1),
1466                               xattr_count1, xattr_count2);
1467                 }
1468                 for (u32 i = 0; i < xattr_count1; i++) {
1469                         const struct wim_xattr_entry *entry1 = entries1[i];
1470                         const struct wim_xattr_entry *entry2 = entries2[i];
1471
1472                         if (entry1->value_len != entry2->value_len ||
1473                             entry1->name_len != entry2->name_len ||
1474                             entry1->flags != entry2->flags ||
1475                             memcmp(entry1->name, entry2->name,
1476                                    entry1->name_len) ||
1477                             memcmp(entry1->name + entry1->name_len + 1,
1478                                    entry2->name + entry2->name_len + 1,
1479                                    le16_to_cpu(entry1->value_len)))
1480                         {
1481                                 ERROR("xattr %.*s of %"TS" differs",
1482                                       entry1->name_len, entry1->name,
1483                                       inode_any_full_path(inode1));
1484                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1485                         }
1486                 }
1487                 return 0;
1488         }
1489 }
1490
1491 static int
1492 cmp_timestamps(const struct wim_inode *inode1, const struct wim_inode *inode2,
1493                int cmp_flags)
1494 {
1495         if (inode1->i_creation_time != inode2->i_creation_time &&
1496             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1497                 ERROR("Creation time of %"TS" differs",
1498                       inode_any_full_path(inode1));
1499                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1500         }
1501
1502         if (inode1->i_last_write_time != inode2->i_last_write_time) {
1503                 ERROR("Last write time of %"TS" differs",
1504                       inode_any_full_path(inode1));
1505                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1506         }
1507
1508         if (inode1->i_last_access_time != inode2->i_last_access_time) {
1509                 ERROR("Last access time of %"TS" differs",
1510                       inode_any_full_path(inode1));
1511                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1512         }
1513
1514         return 0;
1515 }
1516
1517 static int
1518 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1519            const struct wim_image_metadata *imd1,
1520            const struct wim_image_metadata *imd2, int cmp_flags)
1521 {
1522         int ret;
1523
1524         /* Compare attributes  */
1525         ret = cmp_attributes(inode1, inode2, cmp_flags);
1526         if (ret)
1527                 return ret;
1528
1529         /* Compare security descriptors  */
1530         if (inode_has_security_descriptor(inode1)) {
1531                 if (inode_has_security_descriptor(inode2)) {
1532                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1533                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1534                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1535                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1536
1537                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1538                                 ERROR("Security descriptor of %"TS" differs!",
1539                                       inode_any_full_path(inode1));
1540                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1541                         }
1542                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1543                         ERROR("%"TS" has a security descriptor in the first image but "
1544                               "not in the second image!", inode_any_full_path(inode1));
1545                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1546                 }
1547         } else if (inode_has_security_descriptor(inode2)) {
1548                 /* okay --- consider it acceptable if a default security
1549                  * descriptor was assigned  */
1550                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1551                       /*"not in the first image!", inode_any_full_path(inode1));*/
1552                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1553         }
1554
1555         /* Compare streams  */
1556         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1557                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1558                 const struct wim_inode_stream *strm2;
1559
1560                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1561                     (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1562                      !inode_is_symlink(inode1)))
1563                         continue;
1564
1565                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1566                         continue;
1567
1568                 /* Get the corresponding stream from the second file  */
1569                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1570
1571                 if (!strm2) {
1572                         /* Corresponding stream not found  */
1573                         if (stream_is_named(strm1) &&
1574                             (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1575                                 continue;
1576                         ERROR("Stream of %"TS" is missing in second image; "
1577                               "type %d, named=%d, empty=%d",
1578                               inode_any_full_path(inode1),
1579                               strm1->stream_type,
1580                               stream_is_named(strm1),
1581                               is_zero_hash(stream_hash(strm1)));
1582                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1583                 }
1584
1585                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1586                         ERROR("Stream of %"TS" differs; type %d",
1587                               inode_any_full_path(inode1), strm1->stream_type);
1588                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1589                 }
1590         }
1591
1592         /* Compare object IDs  */
1593         ret = cmp_object_ids(inode1, inode2, cmp_flags);
1594         if (ret)
1595                 return ret;
1596
1597         /* Compare timestamps  */
1598         ret = cmp_timestamps(inode1, inode2, cmp_flags);
1599         if (ret)
1600                 return ret;
1601
1602         /* Compare standard UNIX metadata  */
1603         ret = cmp_unix_metadata(inode1, inode2, cmp_flags);
1604         if (ret)
1605                 return ret;
1606
1607         /* Compare extended attributes  */
1608         ret = cmp_xattrs(inode1, inode2, cmp_flags);
1609         if (ret)
1610                 return ret;
1611
1612         return 0;
1613 }
1614
1615 static int
1616 cmp_images(const struct wim_image_metadata *imd1,
1617            const struct wim_image_metadata *imd2, int cmp_flags)
1618 {
1619         struct wim_dentry *root1 = imd1->root_dentry;
1620         struct wim_dentry *root2 = imd2->root_dentry;
1621         const struct wim_inode *inode;
1622         int ret;
1623
1624         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1625         if (ret)
1626                 return ret;
1627
1628         /* Verify that the hard links match up between the two images.  */
1629         assert_inodes_sane(imd1);
1630         assert_inodes_sane(imd2);
1631         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1632         if (ret)
1633                 return ret;
1634
1635         /* Compare corresponding inodes.  */
1636         image_for_each_inode(inode, imd1) {
1637                 ret = cmp_inodes(inode, inode->i_corresponding,
1638                                  imd1, imd2, cmp_flags);
1639                 if (ret)
1640                         return ret;
1641         }
1642
1643         return 0;
1644 }
1645
1646 static int
1647 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1648 {
1649         int ret = select_wim_image(wim, image);
1650         if (!ret) {
1651                 *imd_ret = wim_get_current_image_metadata(wim);
1652                 mark_image_dirty(*imd_ret);
1653         }
1654         return ret;
1655 }
1656
1657 WIMLIBAPI int
1658 wimlib_compare_images(WIMStruct *wim1, int image1,
1659                       WIMStruct *wim2, int image2, int cmp_flags)
1660 {
1661         int ret;
1662         struct wim_image_metadata *imd1, *imd2;
1663
1664         ret = load_image(wim1, image1, &imd1);
1665         if (!ret)
1666                 ret = load_image(wim2, image2, &imd2);
1667         if (!ret)
1668                 ret = cmp_images(imd1, imd2, cmp_flags);
1669         return ret;
1670 }
1671
1672 #endif /* ENABLE_TEST_SUPPORT */