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