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

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