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

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