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

   1 /*
   2  * test_support.c - Supporting code for tests
   3  */
   4
   5 /*
   6  * Copyright 2015-2023 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] = cpu_to_le16(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 #ifdef _WIN32
 479         const char *prefix = "";
 480 #else
 481         const char *prefix = "user.";
 482 #endif
 483         static const char capability_name[] = "security.capability";
 484         bool generated_capability_xattr = false;
 485
 486         /*
 487          * On Linux, xattrs in the "user" namespace are only permitted on
 488          * regular files and directories.  For other types of files we can use
 489          * the "trusted" namespace, but this requires root.
 490          */
 491         if (inode_is_symlink(inode) ||
 492             (inode_get_unix_data(inode, &unix_data) &&
 493              !S_ISREG(unix_data.mode) && !S_ISDIR(unix_data.mode)))
 494         {
 495                 if (!am_root())
 496                         return 0;
 497                 prefix = "trusted.";
 498         }
 499
 500         for (int i = 0; i < num_xattrs; i++) {
 501                 int value_len = rand32() % 64;
 502                 u8 *p;
 503
 504         #ifdef _WIN32
 505                 if (value_len == 0)
 506                         value_len++;
 507         #endif
 508
 509                 entry->value_len = cpu_to_le16(value_len);
 510                 entry->flags = 0;
 511
 512                 if (rand32() % 16 == 0 && am_root() &&
 513                     !generated_capability_xattr) {
 514                         int name_len = sizeof(capability_name) - 1;
 515                         entry->name_len = name_len;
 516                         p = mempcpy(entry->name, capability_name, name_len + 1);
 517                         generated_capability_xattr = true;
 518                 } else {
 519                         int name_len = 1 + rand32() % 64;
 520
 521                         entry->name_len = strlen(prefix) + name_len;
 522                         p = mempcpy(entry->name, prefix, strlen(prefix));
 523                         *p++ = 'A' + i;
 524                         for (int j = 1; j < name_len; j++) {
 525                                 do {
 526                                 #ifdef _WIN32
 527                                         *p = 'A' + rand8() % 26;
 528                                 #else
 529                                         *p = rand8();
 530                                 #endif
 531                                 } while (*p == '\0');
 532                                 p++;
 533                         }
 534                         *p++ = '\0';
 535                 }
 536                 for (int j = 0; j < value_len; j++)
 537                         *p++ = rand8();
 538
 539                 entry = (void *)p;
 540         }
 541
 542         entries_size = (char *)entry - entries;
 543         wimlib_assert(entries_size > 0 && entries_size <= sizeof(entries));
 544
 545         if (!inode_set_xattrs(inode, entries, entries_size))
 546                 return WIMLIB_ERR_NOMEM;
 547
 548         return 0;
 549 }
 550
 551 static int
 552 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
 553 {
 554         u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
 555                                   FILE_ATTRIBUTE_HIDDEN |
 556                                   FILE_ATTRIBUTE_SYSTEM |
 557                                   FILE_ATTRIBUTE_ARCHIVE |
 558                                   FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
 559                                   FILE_ATTRIBUTE_COMPRESSED |
 560                                   FILE_ATTRIBUTE_SPARSE_FILE));
 561
 562         /* File attributes  */
 563         inode->i_attributes |= attrib;
 564
 565         /* Timestamps  */
 566         inode->i_creation_time = generate_random_timestamp();
 567         inode->i_last_access_time = generate_random_timestamp();
 568         inode->i_last_write_time = generate_random_timestamp();
 569
 570         /* Security descriptor  */
 571         if (randbool()) {
 572                 char desc[8192] __attribute__((aligned(8)));
 573                 size_t size;
 574
 575                 size = generate_random_security_descriptor(desc, ctx);
 576
 577                 wimlib_assert(size <= sizeof(desc));
 578
 579                 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
 580                                                      desc, size);
 581                 if (unlikely(inode->i_security_id < 0))
 582                         return WIMLIB_ERR_NOMEM;
 583         }
 584
 585         /* Object ID  */
 586         if (rand32() % 32 == 0) {
 587                 struct wimlib_object_id object_id;
 588
 589                 for (int i = 0; i < sizeof(object_id); i++)
 590                         *((u8 *)&object_id + i) = rand8();
 591                 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
 592                         return WIMLIB_ERR_NOMEM;
 593         }
 594
 595         /* Standard UNIX permissions and special files */
 596         if (rand32() % 16 == 0) {
 597                 int ret = set_random_unix_metadata(inode);
 598                 if (ret)
 599                         return ret;
 600         }
 601
 602         /* Extended attributes */
 603         if (rand32() % 32 == 0) {
 604                 int ret = set_random_xattrs(inode);
 605                 if (ret)
 606                         return ret;
 607         }
 608
 609         return 0;
 610
 611 }
 612
 613 /* Choose a random size for generated file data.  We want to usually generate
 614  * empty, small, or medium files, but occasionally generate large files.  */
 615 static size_t
 616 select_stream_size(struct generation_context *ctx)
 617 {
 618         if (ctx->metadata_only)
 619                 return 0;
 620
 621         switch (rand32() % 2048) {
 622         default:
 623                 /* Empty  */
 624                 return 0;
 625         case 600 ... 799:
 626                 /* Microscopic  */
 627                 return rand32() % 64;
 628         case 800 ... 1319:
 629                 /* Tiny  */
 630                 return rand32() % 4096;
 631         case 1320 ... 1799:
 632                 /* Small  */
 633                 return rand32() % 32768;
 634         case 1800 ... 2046:
 635                 /* Medium  */
 636                 return rand32() % 262144;
 637         case 2047:
 638                 /* Large  */
 639                 return rand32() % 134217728;
 640         }
 641 }
 642
 643 /* Fill 'buffer' with 'size' bytes of "interesting" file data.  */
 644 static void
 645 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
 646 {
 647         size_t mask = -1;
 648         size_t num_byte_fills = rand32() % 256;
 649
 650         if (size == 0)
 651                 return;
 652
 653         /* Start by initializing to a random byte */
 654         memset(buffer, rand32() % 256, size);
 655
 656         /* Add some random bytes in some random places */
 657         for (size_t i = 0; i < num_byte_fills; i++) {
 658                 u8 b = rand8();
 659
 660                 size_t count = ((double)size / (double)num_byte_fills) *
 661                                 ((double)rand32() / 2e9);
 662                 size_t offset = rand32() & ~mask;
 663
 664                 while (count--) {
 665                         buffer[(offset +
 666                                 ((rand32()) & mask)) % size] = b;
 667                 }
 668
 669
 670                 if (rand32() % 4 == 0)
 671                         mask = (size_t)-1 << rand32() % 4;
 672         }
 673
 674         /* Sometimes add a wave pattern */
 675         if (rand32() % 8 == 0) {
 676                 double magnitude = rand32() % 128;
 677                 double scale = 1.0 / (1 + (rand32() % 256));
 678
 679                 for (size_t i = 0; i < size; i++)
 680                         buffer[i] += (int)(magnitude * cos(i * scale));
 681         }
 682
 683         /* Sometimes add some zero regions (holes) */
 684         if (rand32() % 4 == 0) {
 685                 size_t num_holes = 1 + (rand32() % 16);
 686                 for (size_t i = 0; i < num_holes; i++) {
 687                         size_t hole_offset = rand32() % size;
 688                         size_t hole_len = min(size - hole_offset,
 689                                               size / (1 + (rand32() % 16)));
 690                         memset(&buffer[hole_offset], 0, hole_len);
 691                 }
 692         }
 693 }
 694
 695 static noinline_for_stack int
 696 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
 697 {
 698         struct reparse_buffer_disk rpbuf;
 699         size_t rpdatalen;
 700
 701         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 702
 703         if (randbool()) {
 704                 /* Symlink */
 705                 int target_nchars;
 706                 utf16lechar *targets = (utf16lechar *)rpbuf.link.symlink.data;
 707
 708                 inode->i_reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
 709
 710                 target_nchars = generate_random_filename(targets, 255, ctx);
 711
 712                 rpbuf.link.substitute_name_offset = cpu_to_le16(0);
 713                 rpbuf.link.substitute_name_nbytes = cpu_to_le16(2*target_nchars);
 714                 rpbuf.link.print_name_offset = cpu_to_le16(2*(target_nchars + 1));
 715                 rpbuf.link.print_name_nbytes = cpu_to_le16(2*target_nchars);
 716                 targets[target_nchars] = cpu_to_le16(0);
 717                 memcpy(&targets[target_nchars + 1], targets, 2*target_nchars);
 718                 targets[target_nchars + 1 + target_nchars] = cpu_to_le16(0);
 719
 720                 rpbuf.link.symlink.flags = cpu_to_le32(SYMBOLIC_LINK_RELATIVE);
 721                 rpdatalen = ((u8 *)targets - rpbuf.rpdata) +
 722                                 2*(target_nchars + 1 + target_nchars + 1);
 723         } else {
 724                 rpdatalen = select_stream_size(ctx) % REPARSE_DATA_MAX_SIZE;
 725                 generate_data(rpbuf.rpdata, rpdatalen, ctx);
 726
 727                 if (rpdatalen >= GUID_SIZE && randbool()) {
 728                         /* Non-Microsoft reparse tag (16-byte GUID required)  */
 729                         u8 *guid = rpbuf.rpdata;
 730                         guid[6] = (guid[6] & 0x0F) | 0x40;
 731                         guid[8] = (guid[8] & 0x3F) | 0x80;
 732                         inode->i_reparse_tag = 0x00000100;
 733                 } else {
 734                         /* Microsoft reparse tag  */
 735                         inode->i_reparse_tag = 0x80000000;
 736                 }
 737                 inode->i_rp_reserved = rand16();
 738         }
 739
 740         wimlib_assert(rpdatalen < REPARSE_DATA_MAX_SIZE);
 741
 742         if (!inode_add_stream_with_data(inode, STREAM_TYPE_REPARSE_POINT,
 743                                         NO_STREAM_NAME, rpbuf.rpdata,
 744                                         rpdatalen, ctx->params->blob_table))
 745                 return WIMLIB_ERR_NOMEM;
 746
 747         return 0;
 748 }
 749
 750 static int
 751 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
 752                        const utf16lechar *stream_name)
 753 {
 754         void *buffer = NULL;
 755         size_t size;
 756         int ret;
 757
 758         size = select_stream_size(ctx);
 759         if (size) {
 760                 buffer = MALLOC(size);
 761                 if (!buffer)
 762                         return WIMLIB_ERR_NOMEM;
 763                 generate_data(buffer, size, ctx);
 764         }
 765
 766         ret = 0;
 767         if (!inode_add_stream_with_data(inode, STREAM_TYPE_DATA, stream_name,
 768                                         buffer, size, ctx->params->blob_table))
 769                 ret = WIMLIB_ERR_NOMEM;
 770         FREE(buffer);
 771         return ret;
 772 }
 773
 774 static int
 775 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
 776 {
 777         int ret;
 778         u32 r;
 779
 780         /* Reparse point (sometimes)  */
 781         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
 782                 ret = set_random_reparse_point(inode, ctx);
 783                 if (ret)
 784                         return ret;
 785         }
 786
 787         /* Unnamed data stream (nondirectories and non-symlinks only)  */
 788         if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) &&
 789             !inode_is_symlink(inode)) {
 790                 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
 791                 if (ret)
 792                         return ret;
 793         }
 794
 795         /* Named data streams (sometimes)  */
 796         r = rand32() % 256;
 797         if (r > 230) {
 798                 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
 799                 r -= 230;
 800                 while (r--) {
 801                         ret = add_random_data_stream(inode, ctx, stream_name);
 802                         if (ret)
 803                                 return ret;
 804                         stream_name[0] =
 805                                 cpu_to_le16(le16_to_cpu(stream_name[0]) + 1);
 806                 }
 807         }
 808
 809         return 0;
 810 }
 811
 812 static u64
 813 select_inode_number(struct generation_context *ctx)
 814 {
 815         const struct wim_inode_table *table = ctx->params->inode_table;
 816         const struct hlist_head *head;
 817         const struct wim_inode *inode;
 818
 819         head = &table->array[rand32() % table->capacity];
 820         hlist_for_each_entry(inode, head, i_hlist_node)
 821                 if (randbool())
 822                         return inode->i_ino;
 823
 824         return rand32();
 825 }
 826
 827 static u32
 828 select_num_children(u32 depth, struct generation_context *ctx)
 829 {
 830         const double b = 1.01230;
 831         u32 r = rand32() % 500;
 832         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
 833                 (2 - exp(0.04/depth));
 834 }
 835
 836 static bool
 837 is_name_valid_in_win32_namespace(const utf16lechar *name)
 838 {
 839         const utf16lechar *p;
 840
 841         static const char * const reserved_names[] = {
 842                  "CON",  "PRN",  "AUX",  "NUL",
 843                  "COM1", "COM2", "COM3", "COM4", "COM5",
 844                  "COM6", "COM7", "COM8", "COM9",
 845                  "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
 846                  "LPT6", "LPT7", "LPT8", "LPT9",
 847         };
 848
 849         /* The name must be nonempty. */
 850         if (!name || !*name)
 851                 return false;
 852
 853         /* All characters must be valid on Windows. */
 854         for (p = name; *p; p++)
 855                 if (!is_valid_windows_filename_char(*p))
 856                         return false;
 857
 858         /* Note: a trailing dot or space is permitted, even though on Windows
 859          * such a file can only be accessed using a WinNT-style path. */
 860
 861         /* The name can't be one of the reserved names or be a reserved name
 862          * with an extension.  Case insensitive. */
 863         for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
 864                 for (size_t j = 0; ; j++) {
 865                         u16 c1 = le16_to_cpu(name[j]);
 866                         u16 c2 = reserved_names[i][j];
 867                         if (c2 == '\0') {
 868                                 if (c1 == '\0' || c1 == '.')
 869                                         return false;
 870                                 break;
 871                         }
 872                         if (upcase[c1] != upcase[c2])
 873                                 break;
 874                 }
 875         }
 876
 877         return true;
 878 }
 879
 880 static int
 881 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 882                       struct generation_context *ctx)
 883 {
 884         utf16lechar name[12 + 1];
 885         int name_len;
 886         u32 hash;
 887         struct wim_dentry **bucket;
 888
 889         /* If the long name is not allowed in the Win32 namespace, then it
 890          * cannot be assigned a corresponding short name.  */
 891         if (!is_name_valid_in_win32_namespace(child->d_name))
 892                 return 0;
 893
 894 retry:
 895         /* Don't select a short name that is already used by a long name within
 896          * the same directory.  */
 897         do {
 898                 name_len = generate_random_short_name(name, ctx);
 899         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 900                                                     WIMLIB_CASE_INSENSITIVE));
 901
 902
 903         /* Don't select a short name that is already used by another short name
 904          * within the same directory.  */
 905         hash = 0;
 906         for (const utf16lechar *p = name; *p; p++)
 907                 hash = (hash * 31) + le16_to_cpu(*p);
 908         FREE(child->d_short_name);
 909         child->d_short_name = memdup(name, (name_len + 1) * 2);
 910         child->d_short_name_nbytes = name_len * 2;
 911
 912         if (!child->d_short_name)
 913                 return WIMLIB_ERR_NOMEM;
 914
 915         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 916
 917         for (struct wim_dentry *d = *bucket; d != NULL;
 918              d = d->d_next_extraction_alias) {
 919                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
 920                                          d->d_short_name, d->d_short_name_nbytes / 2,
 921                                          true)) {
 922                         goto retry;
 923                 }
 924         }
 925
 926         if (!is_name_valid_in_win32_namespace(child->d_short_name))
 927                 goto retry;
 928
 929         child->d_next_extraction_alias = *bucket;
 930         *bucket = child;
 931         return 0;
 932 }
 933
 934 static bool
 935 inode_has_short_name(const struct wim_inode *inode)
 936 {
 937         const struct wim_dentry *dentry;
 938
 939         inode_for_each_dentry(dentry, inode)
 940                 if (dentry_has_short_name(dentry))
 941                         return true;
 942
 943         return false;
 944 }
 945
 946 static int
 947 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 948                                struct generation_context *ctx)
 949 {
 950         u32 num_children = select_num_children(depth, ctx);
 951         struct wim_dentry *child;
 952         int ret;
 953
 954         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 955
 956         /* Generate 'num_children' dentries within 'dir'.  Some may be
 957          * directories themselves.  */
 958
 959         for (u32 i = 0; i < num_children; i++) {
 960
 961                 /* Generate the next child dentry.  */
 962                 struct wim_inode *inode;
 963                 u64 ino;
 964                 bool is_directory = (rand32() % 16 <= 6);
 965                 bool is_reparse = (rand32() % 8 == 0);
 966                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
 967                 int name_len;
 968                 struct wim_dentry *duplicate;
 969
 970                 /*
 971                  * Select an inode number for the new file.  Sometimes choose an
 972                  * existing inode number (i.e. create a hard link).  However,
 973                  * wimlib intentionally doesn't honor directory hard links, and
 974                  * reparse points cannot be represented in the WIM file format
 975                  * at all; so don't create hard links for such files.
 976                  */
 977                 if (is_directory || is_reparse)
 978                         ino = 0;
 979                 else
 980                         ino = select_inode_number(ctx);
 981
 982                 /* Create the dentry. */
 983                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
 984                                              ino, 0, ino == 0, &child);
 985                 if (ret)
 986                         return ret;
 987
 988                 /* Choose a filename that is unique within the directory.*/
 989                 do {
 990                         name_len = generate_random_filename(name,
 991                                                             ARRAY_LEN(name) - 1,
 992                                                             ctx);
 993                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 994                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 995
 996                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
 997                 if (ret) {
 998                         free_dentry(child);
 999                         return ret;
1000                 }
1001
1002                 /* Add the dentry to the directory. */
1003                 duplicate = dentry_add_child(dir, child);
1004                 wimlib_assert(!duplicate);
1005
1006                 inode = child->d_inode;
1007
1008                 if (inode->i_nlink > 1)  /* Existing inode?  */
1009                         continue;
1010
1011                 /* New inode; set attributes, metadata, and data.  */
1012
1013                 if (is_directory)
1014                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
1015                 if (is_reparse)
1016                         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
1017
1018                 ret = set_random_streams(inode, ctx);
1019                 if (ret)
1020                         return ret;
1021
1022                 ret = set_random_metadata(inode, ctx);
1023                 if (ret)
1024                         return ret;
1025
1026                 /* Recurse if it's a directory.  */
1027                 if (is_directory && !is_reparse) {
1028                         ret = generate_dentry_tree_recursive(child, depth + 1,
1029                                                              ctx);
1030                         if (ret)
1031                                 return ret;
1032                 }
1033         }
1034
1035         for_dentry_child(child, dir) {
1036                 /* sometimes generate a unique short name  */
1037                 if (randbool() && !inode_has_short_name(child->d_inode)) {
1038                         ret = set_random_short_name(dir, child, ctx);
1039                         if (ret)
1040                                 return ret;
1041                 }
1042         }
1043
1044         return 0;
1045 }
1046
1047 int
1048 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
1049                      struct scan_params *params)
1050 {
1051         int ret;
1052         struct wim_dentry *root = NULL;
1053         struct generation_context ctx = {
1054                 .params = params,
1055         };
1056
1057         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
1058
1059         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
1060         if (!ret) {
1061                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
1062                 ret = set_random_streams(root->d_inode, &ctx);
1063         }
1064         if (!ret)
1065                 ret = set_random_metadata(root->d_inode, &ctx);
1066         if (!ret)
1067                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
1068         if (!ret)
1069                 *root_ret = root;
1070         else
1071                 free_dentry_tree(root, params->blob_table);
1072         return ret;
1073 }
1074
1075 /*----------------------------------------------------------------------------*
1076  *                            File tree comparison                            *
1077  *----------------------------------------------------------------------------*/
1078
1079 #define INDEX_NODE_TO_DENTRY(node)      \
1080         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
1081
1082 static struct wim_dentry *
1083 dentry_first_child(struct wim_dentry *dentry)
1084 {
1085         return INDEX_NODE_TO_DENTRY(
1086                         avl_tree_first_in_order(dentry->d_inode->i_children));
1087 }
1088
1089 static struct wim_dentry *
1090 dentry_next_sibling(struct wim_dentry *dentry)
1091 {
1092         return INDEX_NODE_TO_DENTRY(
1093                         avl_tree_next_in_order(&dentry->d_index_node));
1094 }
1095
1096 /*
1097  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
1098  * tree 'd2', considering long and short filenames.  In addition, set
1099  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
1100  * other tree, and set 'i_corresponding' of each inode to point to the
1101  * unverified corresponding inode in the other tree.
1102  */
1103 static int
1104 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
1105                                    int cmp_flags)
1106 {
1107         struct wim_dentry *child1;
1108         struct wim_dentry *child2;
1109         int ret;
1110
1111         /* Compare long filenames, case sensitively.  */
1112         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
1113                                 d2->d_name, d2->d_name_nbytes / 2,
1114                                 false))
1115         {
1116                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
1117                       dentry_full_path(d1), dentry_full_path(d2));
1118                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1119         }
1120
1121         /* Compare short filenames, case insensitively.  */
1122         if (!(d2->d_short_name_nbytes == 0 &&
1123               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
1124             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
1125                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
1126                                 true))
1127         {
1128                 ERROR("Short name mismatch; path=\"%"TS"\"",
1129                       dentry_full_path(d1));
1130                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1131         }
1132
1133         /* Match up the dentries  */
1134         d1->d_corresponding = d2;
1135         d2->d_corresponding = d1;
1136
1137         /* Match up the inodes (may overwrite previous value)  */
1138         d1->d_inode->i_corresponding = d2->d_inode;
1139         d2->d_inode->i_corresponding = d1->d_inode;
1140
1141         /* Process children  */
1142         child1 = dentry_first_child(d1);
1143         child2 = dentry_first_child(d2);
1144         while (child1 || child2) {
1145
1146                 if (!child1 || !child2) {
1147                         ERROR("Child count mismatch; "
1148                               "path1=\"%"TS"\", path2=\"%"TS"\"",
1149                               dentry_full_path(d1), dentry_full_path(d2));
1150                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1151                 }
1152
1153                 /* Recurse on this pair of children.  */
1154                 ret = calc_corresponding_files_recursive(child1, child2,
1155                                                          cmp_flags);
1156                 if (ret)
1157                         return ret;
1158
1159                 /* Continue to the next pair of children.  */
1160                 child1 = dentry_next_sibling(child1);
1161                 child2 = dentry_next_sibling(child2);
1162         }
1163         return 0;
1164 }
1165
1166 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
1167  * even if the images being compared are different.  */
1168 static void
1169 assert_inodes_sane(const struct wim_image_metadata *imd)
1170 {
1171         const struct wim_inode *inode;
1172         const struct wim_dentry *dentry;
1173         size_t link_count;
1174
1175         image_for_each_inode(inode, imd) {
1176                 link_count = 0;
1177                 inode_for_each_dentry(dentry, inode) {
1178                         wimlib_assert(dentry->d_inode == inode);
1179                         link_count++;
1180                 }
1181                 wimlib_assert(link_count > 0);
1182                 wimlib_assert(link_count == inode->i_nlink);
1183                 wimlib_assert(inode->i_corresponding != NULL);
1184         }
1185 }
1186
1187 static int
1188 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1189 {
1190         /* My inode is my corresponding dentry's inode's corresponding inode,
1191          * and my inode's corresponding inode is my corresponding dentry's
1192          * inode.  */
1193         const struct wim_inode *a = dentry->d_inode;
1194         const struct wim_inode *b = dentry->d_corresponding->d_inode;
1195         if (a == b->i_corresponding && a->i_corresponding == b)
1196                 return 0;
1197         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1198         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1199 }
1200
1201 static const struct {
1202         u32 flag;
1203         const char *name;
1204 } file_attr_flags[] = {
1205         {FILE_ATTRIBUTE_READONLY,            "READONLY"},
1206         {FILE_ATTRIBUTE_HIDDEN,              "HIDDEN"},
1207         {FILE_ATTRIBUTE_SYSTEM,              "SYSTEM"},
1208         {FILE_ATTRIBUTE_DIRECTORY,           "DIRECTORY"},
1209         {FILE_ATTRIBUTE_ARCHIVE,             "ARCHIVE"},
1210         {FILE_ATTRIBUTE_DEVICE,              "DEVICE"},
1211         {FILE_ATTRIBUTE_NORMAL,              "NORMAL"},
1212         {FILE_ATTRIBUTE_TEMPORARY,           "TEMPORARY"},
1213         {FILE_ATTRIBUTE_SPARSE_FILE,         "SPARSE_FILE"},
1214         {FILE_ATTRIBUTE_REPARSE_POINT,       "REPARSE_POINT"},
1215         {FILE_ATTRIBUTE_COMPRESSED,          "COMPRESSED"},
1216         {FILE_ATTRIBUTE_OFFLINE,             "OFFLINE"},
1217         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1218         {FILE_ATTRIBUTE_ENCRYPTED,           "ENCRYPTED"},
1219         {FILE_ATTRIBUTE_VIRTUAL,             "VIRTUAL"},
1220 };
1221
1222 static int
1223 cmp_attributes(const struct wim_inode *inode1,
1224                const struct wim_inode *inode2, int cmp_flags)
1225 {
1226         const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1227         const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1228         const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1229
1230         /* NORMAL may change, but it must never be set along with other
1231          * attributes. */
1232         if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1233             (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1234                 goto mismatch;
1235
1236         /* DIRECTORY may change in UNIX mode for symlinks. */
1237         if (changed & FILE_ATTRIBUTE_DIRECTORY) {
1238                 if (!(inode_is_symlink(inode1) &&
1239                       (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)))
1240                         goto mismatch;
1241         }
1242
1243         /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1244          * symlink. */
1245         if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1246             !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1247               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1248               !inode_is_symlink(inode1)))
1249                 goto mismatch;
1250
1251         /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1252          * mode if the inode is a directory. */
1253         if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1254             !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1255               ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1256                              WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1257                ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1258                 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1259                 goto mismatch;
1260
1261         /* COMPRESSED may change in UNIX and NTFS-3G modes.  (It *should* be
1262          * preserved in NTFS-3G mode, but it's not implemented yet.) */
1263         if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1264             !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1265                            WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1266                 goto mismatch;
1267
1268         /* All other attributes can change in UNIX mode, but not in any other
1269          * mode. */
1270         if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1271                          FILE_ATTRIBUTE_DIRECTORY |
1272                          FILE_ATTRIBUTE_REPARSE_POINT |
1273                          FILE_ATTRIBUTE_SPARSE_FILE |
1274                          FILE_ATTRIBUTE_COMPRESSED)) &&
1275             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1276                 goto mismatch;
1277
1278         return 0;
1279
1280 mismatch:
1281         ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1282               inode_any_full_path(inode1), inode1->i_attributes,
1283               inode2->i_attributes);
1284         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1285                 u32 flag = file_attr_flags[i].flag;
1286                 if (changed & flag) {
1287                         fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1288                                 file_attr_flags[i].name,
1289                                 (set & flag) ? "set" : "cleared");
1290                 }
1291         }
1292         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1293 }
1294
1295 static int
1296 cmp_object_ids(const struct wim_inode *inode1,
1297                const struct wim_inode *inode2, int cmp_flags)
1298 {
1299         const void *objid1, *objid2;
1300         u32 len1, len2;
1301
1302         objid1 = inode_get_object_id(inode1, &len1);
1303         objid2 = inode_get_object_id(inode2, &len2);
1304
1305         if (!objid1 && !objid2)
1306                 return 0;
1307
1308         if (objid1 && !objid2) {
1309                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1310                         return 0;
1311                 ERROR("%"TS" unexpectedly lost its object ID",
1312                       inode_any_full_path(inode1));
1313                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1314         }
1315
1316         if (!objid1 && objid2) {
1317                 ERROR("%"TS" unexpectedly gained an object ID",
1318                       inode_any_full_path(inode1));
1319                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1320         }
1321
1322         if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1323                 ERROR("Object ID of %"TS" differs",
1324                       inode_any_full_path(inode1));
1325                 fprintf(stderr, "objid1=");
1326                 print_byte_field(objid1, len1, stderr);
1327                 fprintf(stderr, "\nobjid2=");
1328                 print_byte_field(objid2, len2, stderr);
1329                 fprintf(stderr, "\n");
1330                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1331         }
1332
1333         return 0;
1334 }
1335
1336 static int
1337 cmp_unix_metadata(const struct wim_inode *inode1,
1338                   const struct wim_inode *inode2, int cmp_flags)
1339 {
1340         struct wimlib_unix_data dat1, dat2;
1341         bool present1, present2;
1342
1343         present1 = inode_get_unix_data(inode1, &dat1);
1344         present2 = inode_get_unix_data(inode2, &dat2);
1345
1346         if (!present1 && !present2)
1347                 return 0;
1348
1349         if (present1 && !present2) {
1350                 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1351                                  WIMLIB_CMP_FLAG_WINDOWS_MODE))
1352                         return 0;
1353                 ERROR("%"TS" unexpectedly lost its UNIX metadata",
1354                       inode_any_full_path(inode1));
1355                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1356         }
1357
1358         if (!present1 && present2) {
1359                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1360                         return 0;
1361                 ERROR("%"TS" unexpectedly gained UNIX metadata",
1362                       inode_any_full_path(inode1));
1363                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1364         }
1365
1366         if (memcmp(&dat1, &dat2, sizeof(dat1)) != 0) {
1367                 ERROR("UNIX metadata of %"TS" differs: "
1368                       "[uid=%u, gid=%u, mode=0%o, rdev=%u] vs. "
1369                       "[uid=%u, gid=%u, mode=0%o, rdev=%u]",
1370                       inode_any_full_path(inode1),
1371                       dat1.uid, dat1.gid, dat1.mode, dat1.rdev,
1372                       dat2.uid, dat2.gid, dat2.mode, dat2.rdev);
1373                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1374         }
1375
1376         return 0;
1377 }
1378
1379 static int
1380 cmp_xattr_names(const void *p1, const void *p2)
1381 {
1382         const struct wim_xattr_entry *entry1 = *(const struct wim_xattr_entry **)p1;
1383         const struct wim_xattr_entry *entry2 = *(const struct wim_xattr_entry **)p2;
1384         int res;
1385
1386         res = entry1->name_len - entry2->name_len;
1387         if (res)
1388                 return res;
1389
1390         return memcmp(entry1->name, entry2->name, entry1->name_len);
1391 }
1392
1393 /* Validate and sort by name a list of extended attributes */
1394 static int
1395 parse_xattrs(const void *xattrs, u32 len,
1396              const struct wim_xattr_entry *entries[],
1397              u32 *num_entries_p)
1398 {
1399         u32 limit = *num_entries_p;
1400         u32 num_entries = 0;
1401         const struct wim_xattr_entry *entry = xattrs;
1402
1403         while ((void *)entry < xattrs + len) {
1404                 if (!valid_xattr_entry(entry, xattrs + len - (void *)entry)) {
1405                         ERROR("Invalid xattr entry");
1406                         return WIMLIB_ERR_INVALID_XATTR;
1407                 }
1408                 if (num_entries >= limit) {
1409                         ERROR("Too many xattr entries");
1410                         return WIMLIB_ERR_INVALID_XATTR;
1411                 }
1412                 entries[num_entries++] = entry;
1413                 entry = xattr_entry_next(entry);
1414         }
1415
1416         if (num_entries == 0) {
1417                 ERROR("No xattr entries");
1418                 return WIMLIB_ERR_INVALID_XATTR;
1419         }
1420
1421         qsort(entries, num_entries, sizeof(entries[0]), cmp_xattr_names);
1422
1423         for (u32 i = 1; i < num_entries; i++) {
1424                 if (cmp_xattr_names(&entries[i - 1], &entries[i]) == 0) {
1425                         ERROR("Duplicate xattr names");
1426                         return WIMLIB_ERR_INVALID_XATTR;
1427                 }
1428         }
1429
1430         *num_entries_p = num_entries;
1431         return 0;
1432 }
1433
1434 static int
1435 cmp_xattrs(const struct wim_inode *inode1, const struct wim_inode *inode2,
1436            int cmp_flags)
1437 {
1438         const void *xattrs1, *xattrs2;
1439         u32 len1, len2;
1440
1441         xattrs1 = inode_get_xattrs(inode1, &len1);
1442         xattrs2 = inode_get_xattrs(inode2, &len2);
1443
1444         if (!xattrs1 && !xattrs2) {
1445                 return 0;
1446         } else if (xattrs1 && !xattrs2) {
1447                 if (cmp_flags & WIMLIB_CMP_FLAG_NTFS_3G_MODE)
1448                         return 0;
1449                 ERROR("%"TS" unexpectedly lost its xattrs",
1450                       inode_any_full_path(inode1));
1451                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1452         } else if (!xattrs1 && xattrs2) {
1453                 ERROR("%"TS" unexpectedly gained xattrs",
1454                       inode_any_full_path(inode1));
1455                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1456         } else {
1457                 const int max_entries = 64;
1458                 const struct wim_xattr_entry *entries1[max_entries];
1459                 const struct wim_xattr_entry *entries2[max_entries];
1460                 u32 xattr_count1 = max_entries;
1461                 u32 xattr_count2 = max_entries;
1462                 int ret;
1463
1464                 ret = parse_xattrs(xattrs1, len1, entries1, &xattr_count1);
1465                 if (ret) {
1466                         ERROR("%"TS": invalid xattrs",
1467                               inode_any_full_path(inode1));
1468                         return ret;
1469                 }
1470                 ret = parse_xattrs(xattrs2, len2, entries2, &xattr_count2);
1471                 if (ret) {
1472                         ERROR("%"TS": invalid xattrs",
1473                               inode_any_full_path(inode2));
1474                         return ret;
1475                 }
1476                 if (xattr_count1 != xattr_count2) {
1477                         ERROR("%"TS": number of xattrs changed.  had %u "
1478                               "before, now has %u", inode_any_full_path(inode1),
1479                               xattr_count1, xattr_count2);
1480                 }
1481                 for (u32 i = 0; i < xattr_count1; i++) {
1482                         const struct wim_xattr_entry *entry1 = entries1[i];
1483                         const struct wim_xattr_entry *entry2 = entries2[i];
1484
1485                         if (entry1->value_len != entry2->value_len ||
1486                             entry1->name_len != entry2->name_len ||
1487                             entry1->flags != entry2->flags ||
1488                             memcmp(entry1->name, entry2->name,
1489                                    entry1->name_len) ||
1490                             memcmp(entry1->name + entry1->name_len + 1,
1491                                    entry2->name + entry2->name_len + 1,
1492                                    le16_to_cpu(entry1->value_len)))
1493                         {
1494                                 ERROR("xattr %.*s of %"TS" differs",
1495                                       entry1->name_len, entry1->name,
1496                                       inode_any_full_path(inode1));
1497                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1498                         }
1499                 }
1500                 return 0;
1501         }
1502 }
1503
1504 static int
1505 cmp_timestamps(const struct wim_inode *inode1, const struct wim_inode *inode2,
1506                int cmp_flags)
1507 {
1508         if (inode1->i_creation_time != inode2->i_creation_time &&
1509             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1510                 ERROR("Creation time of %"TS" differs",
1511                       inode_any_full_path(inode1));
1512                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1513         }
1514
1515         if (inode1->i_last_write_time != inode2->i_last_write_time) {
1516                 ERROR("Last write time of %"TS" differs",
1517                       inode_any_full_path(inode1));
1518                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1519         }
1520
1521         if (inode1->i_last_access_time != inode2->i_last_access_time) {
1522                 ERROR("Last access time of %"TS" differs",
1523                       inode_any_full_path(inode1));
1524                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1525         }
1526
1527         return 0;
1528 }
1529
1530 static int
1531 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1532            const struct wim_image_metadata *imd1,
1533            const struct wim_image_metadata *imd2, int cmp_flags)
1534 {
1535         int ret;
1536
1537         /* Compare attributes  */
1538         ret = cmp_attributes(inode1, inode2, cmp_flags);
1539         if (ret)
1540                 return ret;
1541
1542         /* Compare security descriptors  */
1543         if (inode_has_security_descriptor(inode1)) {
1544                 if (inode_has_security_descriptor(inode2)) {
1545                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1546                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1547                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1548                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1549
1550                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1551                                 ERROR("Security descriptor of %"TS" differs!",
1552                                       inode_any_full_path(inode1));
1553                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1554                         }
1555                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1556                         ERROR("%"TS" has a security descriptor in the first image but "
1557                               "not in the second image!", inode_any_full_path(inode1));
1558                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1559                 }
1560         } else if (inode_has_security_descriptor(inode2)) {
1561                 /* okay --- consider it acceptable if a default security
1562                  * descriptor was assigned  */
1563                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1564                       /*"not in the first image!", inode_any_full_path(inode1));*/
1565                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1566         }
1567
1568         /* Compare streams  */
1569         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1570                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1571                 const struct wim_inode_stream *strm2;
1572
1573                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1574                     (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1575                      !inode_is_symlink(inode1)))
1576                         continue;
1577
1578                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1579                         continue;
1580
1581                 /* Get the corresponding stream from the second file  */
1582                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1583
1584                 if (!strm2) {
1585                         /* Corresponding stream not found  */
1586                         if (stream_is_named(strm1) &&
1587                             (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1588                                 continue;
1589                         ERROR("Stream of %"TS" is missing in second image; "
1590                               "type %d, named=%d, empty=%d",
1591                               inode_any_full_path(inode1),
1592                               strm1->stream_type,
1593                               stream_is_named(strm1),
1594                               is_zero_hash(stream_hash(strm1)));
1595                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1596                 }
1597
1598                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1599                         ERROR("Stream of %"TS" differs; type %d",
1600                               inode_any_full_path(inode1), strm1->stream_type);
1601                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1602                 }
1603         }
1604
1605         /* Compare object IDs  */
1606         ret = cmp_object_ids(inode1, inode2, cmp_flags);
1607         if (ret)
1608                 return ret;
1609
1610         /* Compare timestamps  */
1611         ret = cmp_timestamps(inode1, inode2, cmp_flags);
1612         if (ret)
1613                 return ret;
1614
1615         /* Compare standard UNIX metadata  */
1616         ret = cmp_unix_metadata(inode1, inode2, cmp_flags);
1617         if (ret)
1618                 return ret;
1619
1620         /* Compare extended attributes  */
1621         ret = cmp_xattrs(inode1, inode2, cmp_flags);
1622         if (ret)
1623                 return ret;
1624
1625         return 0;
1626 }
1627
1628 static int
1629 cmp_images(const struct wim_image_metadata *imd1,
1630            const struct wim_image_metadata *imd2, int cmp_flags)
1631 {
1632         struct wim_dentry *root1 = imd1->root_dentry;
1633         struct wim_dentry *root2 = imd2->root_dentry;
1634         const struct wim_inode *inode;
1635         int ret;
1636
1637         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1638         if (ret)
1639                 return ret;
1640
1641         /* Verify that the hard links match up between the two images.  */
1642         assert_inodes_sane(imd1);
1643         assert_inodes_sane(imd2);
1644         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1645         if (ret)
1646                 return ret;
1647
1648         /* Compare corresponding inodes.  */
1649         image_for_each_inode(inode, imd1) {
1650                 ret = cmp_inodes(inode, inode->i_corresponding,
1651                                  imd1, imd2, cmp_flags);
1652                 if (ret)
1653                         return ret;
1654         }
1655
1656         return 0;
1657 }
1658
1659 static int
1660 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1661 {
1662         int ret = select_wim_image(wim, image);
1663         if (!ret) {
1664                 *imd_ret = wim_get_current_image_metadata(wim);
1665                 mark_image_dirty(*imd_ret);
1666         }
1667         return ret;
1668 }
1669
1670 WIMLIBAPI int
1671 wimlib_compare_images(WIMStruct *wim1, int image1,
1672                       WIMStruct *wim2, int image2, int cmp_flags)
1673 {
1674         int ret;
1675         struct wim_image_metadata *imd1, *imd2;
1676
1677         ret = load_image(wim1, image1, &imd1);
1678         if (!ret)
1679                 ret = load_image(wim2, image2, &imd2);
1680         if (!ret)
1681                 ret = cmp_images(imd1, imd2, cmp_flags);
1682         return ret;
1683 }
1684
1685 #endif /* ENABLE_TEST_SUPPORT */