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
  39 #include "wimlib.h"
  40 #include "wimlib/endianness.h"
  41 #include "wimlib/encoding.h"
  42 #include "wimlib/metadata.h"
  43 #include "wimlib/dentry.h"
  44 #include "wimlib/inode.h"
  45 #include "wimlib/reparse.h"
  46 #include "wimlib/scan.h"
  47 #include "wimlib/security_descriptor.h"
  48 #include "wimlib/test_support.h"
  49
  50 /*----------------------------------------------------------------------------*
  51  *                            File tree generation                            *
  52  *----------------------------------------------------------------------------*/
  53
  54 struct generation_context {
  55         struct scan_params *params;
  56         struct wim_dentry *used_short_names[256];
  57         bool metadata_only;
  58 };
  59
  60 static u32
  61 rand32(void)
  62 {
  63         static u64 state = 0x55DB93D0AB838771;
  64
  65         /* A simple linear congruential generator  */
  66         state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
  67         return state >> 16;
  68 }
  69
  70 static bool
  71 randbool(void)
  72 {
  73         return (rand32() & 1) != 0;
  74 }
  75
  76 static u8
  77 rand8(void)
  78 {
  79         return (u8)rand32();
  80 }
  81
  82 static u16
  83 rand16(void)
  84 {
  85         return (u16)rand32();
  86 }
  87
  88 static u64
  89 rand64(void)
  90 {
  91         return ((u64)rand32() << 32) | rand32();
  92 }
  93
  94 static u64
  95 generate_random_timestamp(void)
  96 {
  97         /* When setting timestamps on Windows:
  98          * - 0 is a special value meaning "not specified"
  99          * - if the high bit is set you get STATUS_INVALID_PARAMETER  */
 100         return (1 + rand64()) & ~(1ULL << 63);
 101 }
 102
 103 static const struct {
 104         u8 num_subauthorities;
 105         u64 identifier_authority;
 106         u32 subauthorities[6];
 107 } common_sids[] = {
 108         { 1, 0, {0}}, /* NULL_SID  */
 109         { 1, 1, {0}}, /* WORLD_SID */
 110         { 1, 2, {0}}, /* LOCAL_SID */
 111         { 1, 3, {0}}, /* CREATOR_OWNER_SID */
 112         { 1, 3, {1}}, /* CREATOR_GROUP_SID */
 113         { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
 114         { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
 115         // { 0, 5, {}},  /* NT_AUTHORITY_SID */
 116         { 1, 5, {1}}, /* DIALUP_SID */
 117         { 1, 5, {2}}, /* NETWORK_SID */
 118         { 1, 5, {3}}, /* BATCH_SID */
 119         { 1, 5, {4}}, /* INTERACTIVE_SID */
 120         { 1, 5, {6}}, /* SERVICE_SID */
 121         { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
 122         { 1, 5, {8}}, /* PROXY_SID */
 123         { 1, 5, {9}}, /* SERVER_LOGON_SID */
 124         { 1, 5, {10}}, /* SELF_SID */
 125         { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
 126         { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
 127         { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
 128         { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
 129         { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
 130         { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
 131         { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer  */
 132         { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS  */
 133 };
 134
 135 /* Generate a SID and return its size in bytes.  */
 136 static size_t
 137 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
 138 {
 139         u32 r = rand32();
 140
 141         sid->revision = 1;
 142
 143         if (r & 1) {
 144                 /* Common SID  */
 145                 r = (r >> 1) % ARRAY_LEN(common_sids);
 146
 147                 sid->sub_authority_count = common_sids[r].num_subauthorities;
 148                 for (int i = 0; i < 6; i++) {
 149                         sid->identifier_authority[i] =
 150                                 common_sids[r].identifier_authority >> (40 - i * 8);
 151                 }
 152                 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
 153                         sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
 154         } else {
 155                 /* Random SID  */
 156
 157                 sid->sub_authority_count = 1 + ((r >> 1) % 15);
 158
 159                 for (int i = 0; i < 6; i++)
 160                         sid->identifier_authority[i] = rand8();
 161
 162                 for (int i = 0; i < sid->sub_authority_count; i++)
 163                         sid->sub_authority[i] = cpu_to_le32(rand32());
 164         }
 165         return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
 166 }
 167
 168 /* Generate an ACL and return its size in bytes.  */
 169 static size_t
 170 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
 171 {
 172         u8 *p;
 173         u16 ace_count;
 174
 175         ace_count = rand32() % 16;
 176
 177         acl->revision = 2;
 178         acl->sbz1 = 0;
 179         acl->ace_count = cpu_to_le16(ace_count);
 180         acl->sbz2 = 0;
 181
 182         p = (u8 *)(acl + 1);
 183
 184         for (int i = 0; i < ace_count; i++) {
 185                 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
 186
 187                 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
 188                  * same for all  */
 189                 if (dacl)
 190                         ace->hdr.type = rand32() % 2;
 191                 else
 192                         ace->hdr.type = 2;
 193                 ace->hdr.flags = rand8();
 194                 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
 195
 196                 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
 197                         generate_random_sid(&ace->sid, ctx);
 198                 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
 199         }
 200
 201         acl->acl_size = cpu_to_le16(p - (u8 *)acl);
 202         return p - (u8 *)acl;
 203 }
 204
 205 /* Generate a security descriptor and return its size in bytes.  */
 206 static size_t
 207 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
 208 {
 209         wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
 210         u16 control;
 211         u8 *p;
 212
 213         control = rand16();
 214
 215         control &= (wimlib_SE_DACL_AUTO_INHERITED |
 216                     wimlib_SE_SACL_AUTO_INHERITED);
 217
 218         control |= wimlib_SE_SELF_RELATIVE |
 219                    wimlib_SE_DACL_PRESENT |
 220                    wimlib_SE_SACL_PRESENT;
 221
 222         desc->revision = 1;
 223         desc->sbz1 = 0;
 224         desc->control = cpu_to_le16(control);
 225
 226         p = (u8 *)(desc + 1);
 227
 228         desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
 229         p += generate_random_sid((wimlib_SID *)p, ctx);
 230
 231         desc->group_offset = cpu_to_le32(p - (u8 *)desc);
 232         p += generate_random_sid((wimlib_SID *)p, ctx);
 233
 234         if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
 235                 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
 236                 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
 237         } else {
 238                 desc->dacl_offset = cpu_to_le32(0);
 239         }
 240
 241         if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
 242                 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
 243                 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
 244         } else {
 245                 desc->sacl_offset = cpu_to_le32(0);
 246         }
 247
 248         return p - (u8 *)desc;
 249 }
 250
 251 static int
 252 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
 253 {
 254         u32 v = rand32();
 255         u32 attrib = (v & (FILE_ATTRIBUTE_READONLY |
 256                            FILE_ATTRIBUTE_HIDDEN |
 257                            FILE_ATTRIBUTE_SYSTEM |
 258                            FILE_ATTRIBUTE_ARCHIVE |
 259                            FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
 260                            FILE_ATTRIBUTE_COMPRESSED |
 261                            FILE_ATTRIBUTE_SPARSE_FILE));
 262
 263         /* File attributes  */
 264         inode->i_attributes |= attrib;
 265
 266         /* Timestamps  */
 267         inode->i_creation_time = generate_random_timestamp();
 268         inode->i_last_access_time = generate_random_timestamp();
 269         inode->i_last_write_time = generate_random_timestamp();
 270
 271         /* Security descriptor  */
 272         if (randbool()) {
 273                 char desc[8192] _aligned_attribute(8);
 274                 size_t size;
 275
 276                 size = generate_random_security_descriptor(desc, ctx);
 277
 278                 wimlib_assert(size <= sizeof(desc));
 279
 280                 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
 281                                                      desc, size);
 282                 if (unlikely(inode->i_security_id < 0))
 283                         return WIMLIB_ERR_NOMEM;
 284         }
 285
 286         return 0;
 287
 288 }
 289
 290 /* Choose a random size for generated file data.  We want to usually generate
 291  * empty, small, or medium files, but occasionally generate large files.  */
 292 static size_t
 293 select_stream_size(struct generation_context *ctx)
 294 {
 295         if (ctx->metadata_only)
 296                 return 0;
 297
 298         switch (rand32() % 2048) {
 299         default:
 300                 /* Empty  */
 301                 return 0;
 302         case 600 ... 799:
 303                 /* Microscopic  */
 304                 return rand32() % 64;
 305         case 800 ... 1319:
 306                 /* Tiny  */
 307                 return rand32() % 4096;
 308         case 1320 ... 1799:
 309                 /* Small  */
 310                 return rand32() % 32768;
 311         case 1800 ... 2046:
 312                 /* Medium  */
 313                 return rand32() % 262144;
 314         case 2047:
 315                 /* Large  */
 316                 return rand32() % 134217728;
 317         }
 318 }
 319
 320 /* Fill 'buffer' with 'size' bytes of "interesting" file data.  */
 321 static void
 322 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
 323 {
 324         size_t mask = -1;
 325         size_t num_byte_fills = rand32() % 256;
 326
 327         /* Start by initializing to a random byte */
 328         memset(buffer, rand32() % 256, size);
 329
 330         /* Add some random bytes in some random places */
 331         for (size_t i = 0; i < num_byte_fills; i++) {
 332                 u8 b = rand8();
 333
 334                 size_t count = ((double)size / (double)num_byte_fills) *
 335                                 ((double)rand32() / 2e9);
 336                 size_t offset = rand32() & ~mask;
 337
 338                 while (count--) {
 339                         buffer[(offset +
 340                                 ((rand32()) & mask)) % size] = b;
 341                 }
 342
 343
 344                 if (rand32() % 4 == 0)
 345                         mask = (size_t)-1 << rand32() % 4;
 346         }
 347
 348         /* Sometimes add a wave pattern */
 349         if (rand32() % 8 == 0) {
 350                 double magnitude = rand32() % 128;
 351                 double scale = 1.0 / (1 + (rand32() % 256));
 352
 353                 for (size_t i = 0; i < size; i++)
 354                         buffer[i] += (int)(magnitude * cos(i * scale));
 355         }
 356
 357         /* Sometimes add some zero regions (holes) */
 358         if (rand32() % 4 == 0) {
 359                 size_t num_holes = 1 + (rand32() % 16);
 360                 for (size_t i = 0; i < num_holes; i++) {
 361                         size_t hole_offset = rand32() % size;
 362                         size_t hole_len = min(size - hole_offset,
 363                                               size / (1 + (rand32() % 16)));
 364                         memset(&buffer[hole_offset], 0, hole_len);
 365                 }
 366         }
 367 }
 368
 369 static int
 370 add_stream(struct wim_inode *inode, struct generation_context *ctx,
 371            int stream_type, const utf16lechar *stream_name,
 372            void *buffer, size_t size)
 373 {
 374         struct blob_descriptor *blob = NULL;
 375         struct wim_inode_stream *strm;
 376
 377         if (size) {
 378                 blob = new_blob_descriptor();
 379                 if (!blob)
 380                         goto err_nomem;
 381                 blob->attached_buffer = buffer;
 382                 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
 383                 blob->size = size;
 384         }
 385
 386         strm = inode_add_stream(inode, stream_type, stream_name, blob);
 387         if (unlikely(!strm))
 388                 goto err_nomem;
 389
 390         prepare_unhashed_blob(blob, inode, strm->stream_id,
 391                               ctx->params->unhashed_blobs);
 392         return 0;
 393
 394 err_nomem:
 395         free_blob_descriptor(blob);
 396         return WIMLIB_ERR_NOMEM;
 397 }
 398
 399 static int
 400 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
 401 {
 402         void *buffer = NULL;
 403         size_t rpdatalen = select_stream_size(ctx) % (REPARSE_DATA_MAX_SIZE + 1);
 404
 405         if (rpdatalen) {
 406                 buffer = MALLOC(rpdatalen);
 407                 if (!buffer)
 408                         return WIMLIB_ERR_NOMEM;
 409                 generate_data(buffer, rpdatalen, ctx);
 410         }
 411
 412         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 413         inode->i_rp_reserved = rand16();
 414
 415         if (rpdatalen >= GUID_SIZE && randbool()) {
 416                 /* Non-Microsoft reparse tag (16-byte GUID required)  */
 417                 u8 *guid = buffer;
 418                 guid[6] = (guid[6] & 0x0F) | 0x40;
 419                 guid[8] = (guid[8] & 0x3F) | 0x80;
 420                 inode->i_reparse_tag = 0x00000100;
 421         } else {
 422                 /* Microsoft reparse tag  */
 423                 inode->i_reparse_tag = 0x80000000;
 424         }
 425
 426         return add_stream(inode, ctx, STREAM_TYPE_REPARSE_POINT, NO_STREAM_NAME,
 427                           buffer, rpdatalen);
 428 }
 429
 430 static int
 431 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
 432                        const utf16lechar *stream_name)
 433 {
 434         void *buffer = NULL;
 435         size_t size;
 436
 437         size = select_stream_size(ctx);
 438         if (size) {
 439                 buffer = MALLOC(size);
 440                 if (!buffer)
 441                         return WIMLIB_ERR_NOMEM;
 442                 generate_data(buffer, size, ctx);
 443         }
 444
 445         return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
 446                           buffer, size);
 447 }
 448
 449 static int
 450 set_random_streams(struct wim_inode *inode, struct generation_context *ctx,
 451                    bool reparse_ok)
 452 {
 453         int ret;
 454         u32 r;
 455
 456         /* Reparse point (sometimes)  */
 457         if (reparse_ok && rand32() % 8 == 0) {
 458                 ret = set_random_reparse_point(inode, ctx);
 459                 if (ret)
 460                         return ret;
 461         }
 462
 463         /* Unnamed data stream (nondirectories only)  */
 464         if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)) {
 465                 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
 466                 if (ret)
 467                         return ret;
 468         }
 469
 470         /* Named data streams (sometimes)  */
 471         r = rand32() % 256;
 472         if (r > 230) {
 473                 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
 474                 r -= 230;
 475                 while (r--) {
 476                         ret = add_random_data_stream(inode, ctx, stream_name);
 477                         if (ret)
 478                                 return ret;
 479                         stream_name[0] += cpu_to_le16(1);
 480                 }
 481         }
 482
 483         return 0;
 484 }
 485
 486 static inline bool
 487 is_valid_windows_filename_char(utf16lechar c)
 488 {
 489         return le16_to_cpu(c) > 31 &&
 490                 c != cpu_to_le16('/') &&
 491                 c != cpu_to_le16('<') &&
 492                 c != cpu_to_le16('>') &&
 493                 c != cpu_to_le16(':') &&
 494                 c != cpu_to_le16('"') &&
 495                 c != cpu_to_le16('/' ) &&
 496                 c != cpu_to_le16('\\') &&
 497                 c != cpu_to_le16('|') &&
 498                 c != cpu_to_le16('?') &&
 499                 c != cpu_to_le16('*');
 500 }
 501
 502 /* Is the character valid in a filename on the current platform? */
 503 static inline bool
 504 is_valid_filename_char(utf16lechar c)
 505 {
 506 #ifdef __WIN32__
 507         return is_valid_windows_filename_char(c);
 508 #else
 509         return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
 510 #endif
 511 }
 512
 513 /* Generate a random filename and return its length. */
 514 static int
 515 generate_random_filename(utf16lechar name[], int max_len,
 516                          struct generation_context *ctx)
 517 {
 518         int len;
 519
 520         /* Choose the length of the name. */
 521         switch (rand32() % 8) {
 522         default:
 523                 /* short name  */
 524                 len = 1 + (rand32() % 6);
 525                 break;
 526         case 2:
 527         case 3:
 528         case 4:
 529                 /* medium-length name  */
 530                 len = 7 + (rand32() % 8);
 531                 break;
 532         case 5:
 533         case 6:
 534                 /* long name  */
 535                 len = 15 + (rand32() % 15);
 536                 break;
 537         case 7:
 538                 /* very long name  */
 539                 len = 30 + (rand32() % 90);
 540                 break;
 541         }
 542         len = min(len, max_len);
 543
 544         /* Generate the characters in the name. */
 545         for (int i = 0; i < len; i++) {
 546                 do {
 547                         name[i] = rand16();
 548                 } while (!is_valid_filename_char(name[i]));
 549         }
 550
 551         /* Add a null terminator. */
 552         name[len] = cpu_to_le16('\0');
 553
 554         return len;
 555 }
 556
 557 /* The set of characters which are valid in short filenames. */
 558 static const char valid_short_name_chars[] = {
 559         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 560         'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
 561         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 562         '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
 563         '}', '~',
 564         /* Note: Windows does not allow space and 128-255 in short filenames
 565          * (tested on both NTFS and FAT). */
 566 };
 567
 568 static int
 569 generate_short_name_component(utf16lechar p[], int len)
 570 {
 571         for (int i = 0; i < len; i++) {
 572                 char c = valid_short_name_chars[rand32() %
 573                                                 ARRAY_LEN(valid_short_name_chars)];
 574                 p[i] = cpu_to_le16(c);
 575         }
 576         return len;
 577 }
 578
 579 /* Generate a random short (8.3) filename and return its length.
 580  * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
 581 static int
 582 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
 583 {
 584         /*
 585          * Legal short names on Windows consist of 1 to 8 characters, optionally
 586          * followed by a dot then 1 to 3 more characters.  Only certain
 587          * characters are allowed.
 588          */
 589         int base_len = 1 + (rand32() % 8);
 590         int ext_len = rand32() % 4;
 591         int total_len;
 592
 593         base_len = generate_short_name_component(name, base_len);
 594
 595         if (ext_len) {
 596                 name[base_len] = cpu_to_le16('.');
 597                 ext_len = generate_short_name_component(&name[base_len + 1],
 598                                                         ext_len);
 599                 total_len = base_len + 1 + ext_len;
 600         } else {
 601                 total_len = base_len;
 602         }
 603         name[total_len] = cpu_to_le16('\0');
 604         return total_len;
 605 }
 606
 607 static u64
 608 select_inode_number(struct generation_context *ctx)
 609 {
 610         const struct wim_inode_table *table = ctx->params->inode_table;
 611         const struct hlist_head *head;
 612         const struct wim_inode *inode;
 613
 614         head = &table->array[rand32() % table->capacity];
 615         hlist_for_each_entry(inode, head, i_hlist_node)
 616                 if (randbool())
 617                         return inode->i_ino;
 618
 619         return rand32();
 620 }
 621
 622 static u32
 623 select_num_children(u32 depth, struct generation_context *ctx)
 624 {
 625         const double b = 1.01230;
 626         u32 r = rand32() % 500;
 627         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
 628                 (2 - exp(0.04/depth));
 629 }
 630
 631 static bool
 632 is_name_valid_in_win32_namespace(const utf16lechar *name)
 633 {
 634         const utf16lechar *p;
 635
 636         static const char * const reserved_names[] = {
 637                  "CON",  "PRN",  "AUX",  "NUL",
 638                  "COM1", "COM2", "COM3", "COM4", "COM5",
 639                  "COM6", "COM7", "COM8", "COM9",
 640                  "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
 641                  "LPT6", "LPT7", "LPT8", "LPT9",
 642         };
 643
 644         /* The name must be nonempty. */
 645         if (!name || !*name)
 646                 return false;
 647
 648         /* All characters must be valid on Windows. */
 649         for (p = name; *p; p++)
 650                 if (!is_valid_windows_filename_char(*p))
 651                         return false;
 652
 653         /* Note: a trailing dot or space is permitted, even though on Windows
 654          * such a file can only be accessed using a WinNT-style path. */
 655
 656         /* The name can't be one of the reserved names or be a reserved name
 657          * with an extension.  Case insensitive. */
 658         for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
 659                 for (size_t j = 0; ; j++) {
 660                         u16 c1 = le16_to_cpu(name[j]);
 661                         u16 c2 = reserved_names[i][j];
 662                         if (c2 == '\0') {
 663                                 if (c1 == '\0' || c1 == '.')
 664                                         return false;
 665                                 break;
 666                         }
 667                         if (upcase[c1] != upcase[c2])
 668                                 break;
 669                 }
 670         }
 671
 672         return true;
 673 }
 674
 675 static int
 676 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 677                       struct generation_context *ctx)
 678 {
 679         utf16lechar name[12 + 1];
 680         int name_len;
 681         u32 hash;
 682         struct wim_dentry **bucket;
 683
 684         /* If the long name is not allowed in the Win32 namespace, then it
 685          * cannot be assigned a corresponding short name.  */
 686         if (!is_name_valid_in_win32_namespace(child->d_name))
 687                 return 0;
 688
 689 retry:
 690         /* Don't select a short name that is already used by a long name within
 691          * the same directory.  */
 692         do {
 693                 name_len = generate_random_short_name(name, ctx);
 694         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 695                                                     WIMLIB_CASE_INSENSITIVE));
 696
 697
 698         /* Don't select a short name that is already used by another short name
 699          * within the same directory.  */
 700         hash = 0;
 701         for (const utf16lechar *p = name; *p; p++)
 702                 hash = (hash * 31) + *p;
 703         FREE(child->d_short_name);
 704         child->d_short_name = memdup(name, (name_len + 1) * 2);
 705         child->d_short_name_nbytes = name_len * 2;
 706
 707         if (!child->d_short_name)
 708                 return WIMLIB_ERR_NOMEM;
 709
 710         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 711
 712         for (struct wim_dentry *d = *bucket; d != NULL;
 713              d = d->d_next_extraction_alias) {
 714                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
 715                                          d->d_short_name, d->d_short_name_nbytes / 2,
 716                                          true)) {
 717                         goto retry;
 718                 }
 719         }
 720
 721         if (!is_name_valid_in_win32_namespace(child->d_short_name))
 722                 goto retry;
 723
 724         child->d_next_extraction_alias = *bucket;
 725         *bucket = child;
 726         return 0;
 727 }
 728
 729 static bool
 730 inode_has_short_name(const struct wim_inode *inode)
 731 {
 732         const struct wim_dentry *dentry;
 733
 734         inode_for_each_dentry(dentry, inode)
 735                 if (dentry_has_short_name(dentry))
 736                         return true;
 737
 738         return false;
 739 }
 740
 741 static int
 742 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 743                                struct generation_context *ctx)
 744 {
 745         u32 num_children = select_num_children(depth, ctx);
 746         struct wim_dentry *child;
 747         int ret;
 748
 749         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 750
 751         /* Generate 'num_children' dentries within 'dir'.  Some may be
 752          * directories themselves.  */
 753
 754         for (u32 i = 0; i < num_children; i++) {
 755
 756                 /* Generate the next child dentry.  */
 757                 struct wim_inode *inode;
 758                 u64 ino;
 759                 bool is_directory;
 760                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
 761                 int name_len;
 762                 struct wim_dentry *duplicate;
 763
 764                 /* Decide whether to create a directory or not.  If not a
 765                  * directory, also decide on the inode number (i.e. we may
 766                  * generate a "hard link" to an existing file).  */
 767                 is_directory = ((rand32() % 16) <= 6);
 768                 if (is_directory)
 769                         ino = 0;
 770                 else
 771                         ino = select_inode_number(ctx);
 772
 773                 /* Create the dentry. */
 774                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
 775                                              ino, 0, is_directory, &child);
 776                 if (ret)
 777                         return ret;
 778
 779                 /* Choose a filename that is unique within the directory.*/
 780                 do {
 781                         name_len = generate_random_filename(name,
 782                                                             ARRAY_LEN(name) - 1,
 783                                                             ctx);
 784                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 785                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 786
 787                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
 788                 if (ret) {
 789                         free_dentry(child);
 790                         return ret;
 791                 }
 792
 793                 /* Add the dentry to the directory. */
 794                 duplicate = dentry_add_child(dir, child);
 795                 wimlib_assert(!duplicate);
 796
 797                 inode = child->d_inode;
 798
 799                 if (inode->i_nlink > 1)  /* Existing inode?  */
 800                         continue;
 801
 802                 /* New inode; set attributes, metadata, and data.  */
 803
 804                 if (is_directory)
 805                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
 806
 807                 ret = set_random_metadata(inode, ctx);
 808                 if (ret)
 809                         return ret;
 810
 811                 ret = set_random_streams(inode, ctx, true);
 812                 if (ret)
 813                         return ret;
 814
 815                 /* Recurse if it's a directory.  */
 816                 if (is_directory &&
 817                     !(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT))
 818                 {
 819                         ret = generate_dentry_tree_recursive(child, depth + 1,
 820                                                              ctx);
 821                         if (ret)
 822                                 return ret;
 823                 }
 824         }
 825
 826         for_dentry_child(child, dir) {
 827                 /* sometimes generate a unique short name  */
 828                 if (randbool() && !inode_has_short_name(child->d_inode)) {
 829                         ret = set_random_short_name(dir, child, ctx);
 830                         if (ret)
 831                                 return ret;
 832                 }
 833         }
 834
 835         return 0;
 836 }
 837
 838 int
 839 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
 840                      struct scan_params *params)
 841 {
 842         int ret;
 843         struct wim_dentry *root = NULL;
 844         struct generation_context ctx = {
 845                 .params = params,
 846         };
 847
 848         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
 849
 850         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
 851         if (!ret) {
 852                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
 853                 ret = set_random_metadata(root->d_inode, &ctx);
 854         }
 855         if (!ret)
 856                 ret = set_random_streams(root->d_inode, &ctx, false);
 857         if (!ret)
 858                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
 859         if (!ret)
 860                 *root_ret = root;
 861         else
 862                 free_dentry_tree(root, params->blob_table);
 863         return ret;
 864 }
 865
 866 /*----------------------------------------------------------------------------*
 867  *                            File tree comparison                            *
 868  *----------------------------------------------------------------------------*/
 869
 870 #define INDEX_NODE_TO_DENTRY(node)      \
 871         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
 872
 873 static struct wim_dentry *
 874 dentry_first_child(struct wim_dentry *dentry)
 875 {
 876         return INDEX_NODE_TO_DENTRY(
 877                         avl_tree_first_in_order(dentry->d_inode->i_children));
 878 }
 879
 880 static struct wim_dentry *
 881 dentry_next_sibling(struct wim_dentry *dentry)
 882 {
 883         return INDEX_NODE_TO_DENTRY(
 884                         avl_tree_next_in_order(&dentry->d_index_node));
 885 }
 886
 887 /*
 888  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
 889  * tree 'd2', considering long and short filenames.  In addition, set
 890  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
 891  * other tree, and set 'i_corresponding' of each inode to point to the
 892  * unverified corresponding inode in the other tree.
 893  */
 894 static int
 895 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
 896                                    int cmp_flags)
 897 {
 898         struct wim_dentry *child1;
 899         struct wim_dentry *child2;
 900         int ret;
 901
 902         /* Compare long filenames, case sensitively.  */
 903         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
 904                                 d2->d_name, d2->d_name_nbytes / 2,
 905                                 false))
 906         {
 907                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
 908                       dentry_full_path(d1), dentry_full_path(d2));
 909                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 910         }
 911
 912         /* Compare short filenames, case insensitively.  */
 913         if (!(d2->d_short_name_nbytes == 0 &&
 914               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
 915             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
 916                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
 917                                 true))
 918         {
 919                 ERROR("Short name mismatch; path=\"%"TS"\"",
 920                       dentry_full_path(d1));
 921                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 922         }
 923
 924         /* Match up the dentries  */
 925         d1->d_corresponding = d2;
 926         d2->d_corresponding = d1;
 927
 928         /* Match up the inodes (may overwrite previous value)  */
 929         d1->d_inode->i_corresponding = d2->d_inode;
 930         d2->d_inode->i_corresponding = d1->d_inode;
 931
 932         /* Process children  */
 933         child1 = dentry_first_child(d1);
 934         child2 = dentry_first_child(d2);
 935         while (child1 || child2) {
 936
 937                 if (!child1 || !child2) {
 938                         ERROR("Child count mismatch; "
 939                               "path1=\"%"TS"\", path2=\"%"TS"\"",
 940                               dentry_full_path(d1), dentry_full_path(d2));
 941                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 942                 }
 943
 944                 /* Recurse on this pair of children.  */
 945                 ret = calc_corresponding_files_recursive(child1, child2,
 946                                                          cmp_flags);
 947                 if (ret)
 948                         return ret;
 949
 950                 /* Continue to the next pair of children.  */
 951                 child1 = dentry_next_sibling(child1);
 952                 child2 = dentry_next_sibling(child2);
 953         }
 954         return 0;
 955 }
 956
 957 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
 958  * even if the images being compared are different.  */
 959 static void
 960 assert_inodes_sane(const struct wim_image_metadata *imd)
 961 {
 962         const struct wim_inode *inode;
 963         const struct wim_dentry *dentry;
 964         size_t link_count;
 965
 966         image_for_each_inode(inode, imd) {
 967                 link_count = 0;
 968                 inode_for_each_dentry(dentry, inode) {
 969                         wimlib_assert(dentry->d_inode == inode);
 970                         link_count++;
 971                 }
 972                 wimlib_assert(link_count > 0);
 973                 wimlib_assert(link_count == inode->i_nlink);
 974                 wimlib_assert(inode->i_corresponding != NULL);
 975         }
 976 }
 977
 978 static int
 979 check_hard_link(struct wim_dentry *dentry, void *_ignore)
 980 {
 981         /* My inode is my corresponding dentry's inode's corresponding inode,
 982          * and my inode's corresponding inode is my corresponding dentry's
 983          * inode.  */
 984         const struct wim_inode *a = dentry->d_inode;
 985         const struct wim_inode *b = dentry->d_corresponding->d_inode;
 986         if (a == b->i_corresponding && a->i_corresponding == b)
 987                 return 0;
 988         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
 989         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 990 }
 991
 992 static const struct {
 993         u32 flag;
 994         const char *name;
 995 } file_attr_flags[] = {
 996         {FILE_ATTRIBUTE_READONLY,            "READONLY"},
 997         {FILE_ATTRIBUTE_HIDDEN,              "HIDDEN"},
 998         {FILE_ATTRIBUTE_SYSTEM,              "SYSTEM"},
 999         {FILE_ATTRIBUTE_DIRECTORY,           "DIRECTORY"},
1000         {FILE_ATTRIBUTE_ARCHIVE,             "ARCHIVE"},
1001         {FILE_ATTRIBUTE_DEVICE,              "DEVICE"},
1002         {FILE_ATTRIBUTE_NORMAL,              "NORMAL"},
1003         {FILE_ATTRIBUTE_TEMPORARY,           "TEMPORARY"},
1004         {FILE_ATTRIBUTE_SPARSE_FILE,         "SPARSE_FILE"},
1005         {FILE_ATTRIBUTE_REPARSE_POINT,       "REPARSE_POINT"},
1006         {FILE_ATTRIBUTE_COMPRESSED,          "COMPRESSED"},
1007         {FILE_ATTRIBUTE_OFFLINE,             "OFFLINE"},
1008         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1009         {FILE_ATTRIBUTE_ENCRYPTED,           "ENCRYPTED"},
1010         {FILE_ATTRIBUTE_VIRTUAL,             "VIRTUAL"},
1011 };
1012
1013 static int
1014 cmp_attributes(const struct wim_inode *inode1,
1015                const struct wim_inode *inode2, int cmp_flags)
1016 {
1017         const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1018         const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1019         const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1020
1021         /* NORMAL may change, but it must never be set along with other
1022          * attributes. */
1023         if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1024             (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1025                 goto mismatch;
1026
1027         /* DIRECTORY must not change. */
1028         if (changed & FILE_ATTRIBUTE_DIRECTORY)
1029                 goto mismatch;
1030
1031         /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1032          * symlink. */
1033         if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1034             !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1035               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1036               !inode_is_symlink(inode1)))
1037                 goto mismatch;
1038
1039         /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1040          * mode if the inode is a directory. */
1041         if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1042             !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1043               ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1044                              WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1045                ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1046                 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1047                 goto mismatch;
1048
1049         /* COMPRESSED may change in UNIX and NTFS-3G modes.  (It *should* be
1050          * preserved in NTFS-3G mode, but it's not implemented yet.) */
1051         if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1052             !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1053                            WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1054                 goto mismatch;
1055
1056         /* All other attributes can change in UNIX mode, but not in any other
1057          * mode. */
1058         if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1059                          FILE_ATTRIBUTE_DIRECTORY |
1060                          FILE_ATTRIBUTE_REPARSE_POINT |
1061                          FILE_ATTRIBUTE_SPARSE_FILE |
1062                          FILE_ATTRIBUTE_COMPRESSED)) &&
1063             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1064                 goto mismatch;
1065
1066         return 0;
1067
1068 mismatch:
1069         ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1070               inode_any_full_path(inode1), inode1->i_attributes,
1071               inode2->i_attributes);
1072         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1073                 u32 flag = file_attr_flags[i].flag;
1074                 if (changed & flag) {
1075                         fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1076                                 file_attr_flags[i].name,
1077                                 (set & flag) ? "set" : "cleared");
1078                 }
1079         }
1080         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1081 }
1082
1083 static int
1084 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1085            const struct wim_image_metadata *imd1,
1086            const struct wim_image_metadata *imd2, int cmp_flags)
1087 {
1088         int ret;
1089
1090         /* Compare attributes  */
1091         ret = cmp_attributes(inode1, inode2, cmp_flags);
1092         if (ret)
1093                 return ret;
1094
1095         /* Compare security descriptors  */
1096         if (inode_has_security_descriptor(inode1)) {
1097                 if (inode_has_security_descriptor(inode2)) {
1098                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1099                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1100                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1101                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1102
1103                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1104                                 ERROR("Security descriptor of %"TS" differs!",
1105                                       inode_any_full_path(inode1));
1106                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1107                         }
1108                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1109                         ERROR("%"TS" has a security descriptor in the first image but "
1110                               "not in the second image!", inode_any_full_path(inode1));
1111                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1112                 }
1113         } else if (inode_has_security_descriptor(inode2)) {
1114                 /* okay --- consider it acceptable if a default security
1115                  * descriptor was assigned  */
1116                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1117                       /*"not in the first image!", inode_any_full_path(inode1));*/
1118                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1119         }
1120
1121         /* Compare streams  */
1122         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1123                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1124                 const struct wim_inode_stream *strm2;
1125
1126                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1127                     (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1128                      !inode_is_symlink(inode1)))
1129                         continue;
1130
1131                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1132                         continue;
1133
1134                 /* Get the corresponding stream from the second file  */
1135                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1136
1137                 if (!strm2) {
1138                         /* Corresponding stream not found  */
1139                         if (stream_is_named(strm1) &&
1140                             (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1141                                 continue;
1142                         ERROR("Stream of %"TS" is missing in second image; "
1143                               "type %d, named=%d, empty=%d",
1144                               inode_any_full_path(inode1),
1145                               strm1->stream_type,
1146                               stream_is_named(strm1),
1147                               is_zero_hash(stream_hash(strm1)));
1148                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1149                 }
1150
1151                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1152                         ERROR("Stream of %"TS" differs; type %d",
1153                               inode_any_full_path(inode1), strm1->stream_type);
1154                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1155                 }
1156         }
1157
1158         return 0;
1159 }
1160
1161 static int
1162 cmp_images(const struct wim_image_metadata *imd1,
1163            const struct wim_image_metadata *imd2, int cmp_flags)
1164 {
1165         struct wim_dentry *root1 = imd1->root_dentry;
1166         struct wim_dentry *root2 = imd2->root_dentry;
1167         const struct wim_inode *inode;
1168         int ret;
1169
1170         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1171         if (ret)
1172                 return ret;
1173
1174         /* Verify that the hard links match up between the two images.  */
1175         assert_inodes_sane(imd1);
1176         assert_inodes_sane(imd2);
1177         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1178         if (ret)
1179                 return ret;
1180
1181         /* Compare corresponding inodes.  */
1182         image_for_each_inode(inode, imd1) {
1183                 ret = cmp_inodes(inode, inode->i_corresponding,
1184                                  imd1, imd2, cmp_flags);
1185                 if (ret)
1186                         return ret;
1187         }
1188
1189         return 0;
1190 }
1191
1192 static int
1193 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1194 {
1195         int ret = select_wim_image(wim, image);
1196         if (!ret) {
1197                 *imd_ret = wim_get_current_image_metadata(wim);
1198                 mark_image_dirty(*imd_ret);
1199         }
1200         return ret;
1201 }
1202
1203 WIMLIBAPI int
1204 wimlib_compare_images(WIMStruct *wim1, int image1,
1205                       WIMStruct *wim2, int image2, int cmp_flags)
1206 {
1207         int ret;
1208         struct wim_image_metadata *imd1, *imd2;
1209
1210         ret = load_image(wim1, image1, &imd1);
1211         if (!ret)
1212                 ret = load_image(wim2, image2, &imd2);
1213         if (!ret)
1214                 ret = cmp_images(imd1, imd2, cmp_flags);
1215         return ret;
1216 }
1217
1218 #endif /* ENABLE_TEST_SUPPORT */