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