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