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