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         /* There can't be a trailing dot or space. */
 673         if (p[-1] == cpu_to_le16('.') || p[-1] == cpu_to_le16(' '))
 674                 return false;
 675
 676         /* The name can't be one of the reserved names (case insensitively). */
 677         for (size_t i = 0; i < ARRAY_LEN(forbidden_names); i++)
 678                 if (!cmp_utf16le_strings_z(forbidden_names[i], name, true))
 679                         return false;
 680
 681         return true;
 682 }
 683
 684 static int
 685 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 686                       struct generation_context *ctx)
 687 {
 688         utf16lechar name[12 + 1];
 689         int name_len;
 690         u32 hash;
 691         struct wim_dentry **bucket;
 692
 693         /* If the long name is not allowed in the Win32 namespace, then it
 694          * cannot be assigned a corresponding short name.  */
 695         if (!is_name_valid_in_win32_namespace(child->d_name))
 696                 return 0;
 697
 698 retry:
 699         /* Don't select a short name that is already used by a long name within
 700          * the same directory.  */
 701         do {
 702                 name_len = generate_random_short_name(name, ctx);
 703         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 704                                                     WIMLIB_CASE_INSENSITIVE));
 705
 706
 707         /* Don't select a short name that is already used by another short name
 708          * within the same directory.  */
 709         hash = 0;
 710         for (const utf16lechar *p = name; *p; p++)
 711                 hash = (hash * 31) + *p;
 712         FREE(child->d_short_name);
 713         child->d_short_name = memdup(name, (name_len + 1) * 2);
 714         child->d_short_name_nbytes = name_len * 2;
 715
 716         if (!child->d_short_name)
 717                 return WIMLIB_ERR_NOMEM;
 718
 719         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 720
 721         for (struct wim_dentry *d = *bucket; d != NULL;
 722              d = d->d_next_extraction_alias) {
 723                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
 724                                          d->d_short_name, d->d_short_name_nbytes / 2,
 725                                          true)) {
 726                         goto retry;
 727                 }
 728         }
 729
 730         if (!is_name_valid_in_win32_namespace(child->d_short_name))
 731                 goto retry;
 732
 733         child->d_next_extraction_alias = *bucket;
 734         *bucket = child;
 735         return 0;
 736 }
 737
 738 static bool
 739 inode_has_short_name(const struct wim_inode *inode)
 740 {
 741         const struct wim_dentry *dentry;
 742
 743         inode_for_each_dentry(dentry, inode)
 744                 if (dentry_has_short_name(dentry))
 745                         return true;
 746
 747         return false;
 748 }
 749
 750 static int
 751 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 752                                struct generation_context *ctx)
 753 {
 754         u32 num_children = select_num_children(depth, ctx);
 755         struct wim_dentry *child;
 756         int ret;
 757
 758         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 759
 760         /* Generate 'num_children' dentries within 'dir'.  Some may be
 761          * directories themselves.  */
 762
 763         for (u32 i = 0; i < num_children; i++) {
 764
 765                 /* Generate the next child dentry.  */
 766                 struct wim_inode *inode;
 767                 u64 ino;
 768                 bool is_directory;
 769                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
 770                 int name_len;
 771                 struct wim_dentry *duplicate;
 772
 773                 /* Decide whether to create a directory or not.  If not a
 774                  * directory, also decide on the inode number (i.e. we may
 775                  * generate a "hard link" to an existing file).  */
 776                 is_directory = ((rand32() % 16) <= 6);
 777                 if (is_directory)
 778                         ino = 0;
 779                 else
 780                         ino = select_inode_number(ctx);
 781
 782                 /* Create the dentry. */
 783                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
 784                                              ino, 0, is_directory, &child);
 785                 if (ret)
 786                         return ret;
 787
 788                 /* Choose a filename that is unique within the directory.*/
 789                 do {
 790                         name_len = generate_random_filename(name,
 791                                                             ARRAY_LEN(name) - 1,
 792                                                             ctx);
 793                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 794                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 795
 796                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
 797                 if (ret) {
 798                         free_dentry(child);
 799                         return ret;
 800                 }
 801
 802                 /* Add the dentry to the directory. */
 803                 duplicate = dentry_add_child(dir, child);
 804                 wimlib_assert(!duplicate);
 805
 806                 inode = child->d_inode;
 807
 808                 if (inode->i_nlink > 1)  /* Existing inode?  */
 809                         continue;
 810
 811                 /* New inode; set attributes, metadata, and data.  */
 812
 813                 if (is_directory)
 814                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
 815
 816                 ret = set_random_metadata(inode, ctx);
 817                 if (ret)
 818                         return ret;
 819
 820                 ret = set_random_streams(inode, ctx, true);
 821                 if (ret)
 822                         return ret;
 823
 824                 /* Recurse if it's a directory.  */
 825                 if (is_directory &&
 826                     !(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT))
 827                 {
 828                         ret = generate_dentry_tree_recursive(child, depth + 1,
 829                                                              ctx);
 830                         if (ret)
 831                                 return ret;
 832                 }
 833         }
 834
 835         for_dentry_child(child, dir) {
 836                 /* sometimes generate a unique short name  */
 837                 if (randbool() && !inode_has_short_name(child->d_inode)) {
 838                         ret = set_random_short_name(dir, child, ctx);
 839                         if (ret)
 840                                 return ret;
 841                 }
 842         }
 843
 844         return 0;
 845 }
 846
 847 int
 848 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
 849                      struct scan_params *params)
 850 {
 851         int ret;
 852         struct wim_dentry *root = NULL;
 853         struct generation_context ctx = {
 854                 .params = params,
 855         };
 856
 857         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
 858
 859         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
 860         if (!ret) {
 861                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
 862                 ret = set_random_metadata(root->d_inode, &ctx);
 863         }
 864         if (!ret)
 865                 ret = set_random_streams(root->d_inode, &ctx, false);
 866         if (!ret)
 867                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
 868         if (!ret)
 869                 *root_ret = root;
 870         else
 871                 free_dentry_tree(root, params->blob_table);
 872         return ret;
 873 }
 874
 875 /*----------------------------------------------------------------------------*
 876  *                            File tree comparison                            *
 877  *----------------------------------------------------------------------------*/
 878
 879 #define INDEX_NODE_TO_DENTRY(node)      \
 880         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
 881
 882 static struct wim_dentry *
 883 dentry_first_child(struct wim_dentry *dentry)
 884 {
 885         return INDEX_NODE_TO_DENTRY(
 886                         avl_tree_first_in_order(dentry->d_inode->i_children));
 887 }
 888
 889 static struct wim_dentry *
 890 dentry_next_sibling(struct wim_dentry *dentry)
 891 {
 892         return INDEX_NODE_TO_DENTRY(
 893                         avl_tree_next_in_order(&dentry->d_index_node));
 894 }
 895
 896 /*
 897  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
 898  * tree 'd2', considering long and short filenames.  In addition, set
 899  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
 900  * other tree, and set 'i_corresponding' of each inode to point to the
 901  * unverified corresponding inode in the other tree.
 902  */
 903 static int
 904 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
 905                                    int cmp_flags)
 906 {
 907         struct wim_dentry *child1;
 908         struct wim_dentry *child2;
 909         int ret;
 910
 911         /* Compare long filenames, case sensitively.  */
 912         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
 913                                 d2->d_name, d2->d_name_nbytes / 2,
 914                                 false))
 915         {
 916                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
 917                       dentry_full_path(d1), dentry_full_path(d2));
 918                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 919         }
 920
 921         /* Compare short filenames, case insensitively.  */
 922         if (!(d2->d_short_name_nbytes == 0 &&
 923               (cmp_flags & WIMLIB_CMP_FLAG_SHORT_NAMES_NOT_PRESERVED)) &&
 924             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
 925                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
 926                                 true))
 927         {
 928                 ERROR("Short name mismatch; path=\"%"TS"\"",
 929                       dentry_full_path(d1));
 930                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 931         }
 932
 933         /* Match up the dentries  */
 934         d1->d_corresponding = d2;
 935         d2->d_corresponding = d1;
 936
 937         /* Match up the inodes (may overwrite previous value)  */
 938         d1->d_inode->i_corresponding = d2->d_inode;
 939         d2->d_inode->i_corresponding = d1->d_inode;
 940
 941         /* Process children  */
 942         child1 = dentry_first_child(d1);
 943         child2 = dentry_first_child(d2);
 944         while (child1 || child2) {
 945
 946                 if (!child1 || !child2) {
 947                         ERROR("Child count mismatch; "
 948                               "path1=\"%"TS"\", path2=\"%"TS"\"",
 949                               dentry_full_path(d1), dentry_full_path(d2));
 950                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 951                 }
 952
 953                 /* Recurse on this pair of children.  */
 954                 ret = calc_corresponding_files_recursive(child1, child2,
 955                                                          cmp_flags);
 956                 if (ret)
 957                         return ret;
 958
 959                 /* Continue to the next pair of children.  */
 960                 child1 = dentry_next_sibling(child1);
 961                 child2 = dentry_next_sibling(child2);
 962         }
 963         return 0;
 964 }
 965
 966 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
 967  * even if the images being compared are different.  */
 968 static void
 969 assert_inodes_sane(const struct wim_image_metadata *imd)
 970 {
 971         const struct wim_inode *inode;
 972         const struct wim_dentry *dentry;
 973         size_t link_count;
 974
 975         image_for_each_inode(inode, imd) {
 976                 link_count = 0;
 977                 inode_for_each_dentry(dentry, inode) {
 978                         wimlib_assert(dentry->d_inode == inode);
 979                         link_count++;
 980                 }
 981                 wimlib_assert(link_count > 0);
 982                 wimlib_assert(link_count == inode->i_nlink);
 983                 wimlib_assert(inode->i_corresponding != NULL);
 984         }
 985 }
 986
 987 static int
 988 check_hard_link(struct wim_dentry *dentry, void *_ignore)
 989 {
 990         /* My inode is my corresponding dentry's inode's corresponding inode,
 991          * and my inode's corresponding inode is my corresponding dentry's
 992          * inode.  */
 993         const struct wim_inode *a = dentry->d_inode;
 994         const struct wim_inode *b = dentry->d_corresponding->d_inode;
 995         if (a == b->i_corresponding && a->i_corresponding == b)
 996                 return 0;
 997         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
 998         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 999 }
1000
1001 static int
1002 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1003            const struct wim_image_metadata *imd1,
1004            const struct wim_image_metadata *imd2, int cmp_flags)
1005 {
1006         const u32 attrib_diff = inode1->i_attributes ^ inode2->i_attributes;
1007         bool reparse_point_should_preserved = true;
1008
1009         /* Compare attributes  */
1010         if (cmp_flags & WIMLIB_CMP_FLAG_ATTRIBUTES_NOT_PRESERVED) {
1011
1012                 /* In this mode, we expect that most attributes are not
1013                  * preserved.  However, FILE_ATTRIBUTE_DIRECTORY should always
1014                  * match.  */
1015                 if (attrib_diff & FILE_ATTRIBUTE_DIRECTORY)
1016                         goto attrib_mismatch;
1017
1018                 /* We may also expect FILE_ATTRIBUTE_REPARSE_POINT to be
1019                  * preserved for symlinks.  It also shouldn't be set if it
1020                  * wasn't set before.  */
1021
1022                 if ((cmp_flags & WIMLIB_CMP_FLAG_IMAGE2_SHOULD_HAVE_SYMLINKS) &&
1023                     inode_is_symlink(inode1))
1024                         reparse_point_should_preserved = true;
1025                 else
1026                         reparse_point_should_preserved = false;
1027
1028                 if ((attrib_diff & FILE_ATTRIBUTE_REPARSE_POINT) &&
1029                     (reparse_point_should_preserved ||
1030                      (inode2->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)))
1031                         goto attrib_mismatch;
1032         } else {
1033
1034                 /* Most attributes should be preserved.  */
1035
1036                 /* Nothing other than COMPRESSED and NORMAL should have changed.
1037                  */
1038                 if (attrib_diff & ~(FILE_ATTRIBUTE_COMPRESSED |
1039                                     FILE_ATTRIBUTE_NORMAL))
1040                         goto attrib_mismatch;
1041
1042                 /* COMPRESSED shouldn't have changed unless specifically
1043                  * excluded.  */
1044                 if ((attrib_diff & FILE_ATTRIBUTE_COMPRESSED) &&
1045                     !(cmp_flags & WIMLIB_CMP_FLAG_COMPRESSION_NOT_PRESERVED))
1046                         goto attrib_mismatch;
1047
1048                 /* We allow NORMAL to change, but not if the file ended up with
1049                  * other attributes set as well.  */
1050                 if ((attrib_diff & FILE_ATTRIBUTE_NORMAL) &&
1051                     (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1052                         goto attrib_mismatch;
1053         }
1054
1055         /* Compare security descriptors  */
1056         if (inode_has_security_descriptor(inode1)) {
1057                 if (inode_has_security_descriptor(inode2)) {
1058                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1059                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1060                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1061                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1062
1063                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1064                                 ERROR("Security descriptor of %"TS" differs!",
1065                                       inode_any_full_path(inode1));
1066                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1067                         }
1068                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_SECURITY_NOT_PRESERVED)) {
1069                         ERROR("%"TS" has a security descriptor in the first image but "
1070                               "not in the second image!", inode_any_full_path(inode1));
1071                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1072                 }
1073         } else if (inode_has_security_descriptor(inode2)) {
1074                 /* okay --- consider it acceptable if a default security
1075                  * descriptor was assigned  */
1076                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1077                       /*"not in the first image!", inode_any_full_path(inode1));*/
1078                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1079         }
1080
1081         /* Compare streams  */
1082         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1083                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1084                 const struct wim_inode_stream *strm2;
1085
1086                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1087                     !reparse_point_should_preserved)
1088                         continue;
1089
1090                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1091                         continue;
1092
1093                 /* Get the corresponding stream from the second file  */
1094                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1095
1096                 if (!strm2) {
1097                         /* Corresponding stream not found  */
1098                         if (stream_is_named(strm1) &&
1099                             (cmp_flags & WIMLIB_CMP_FLAG_ADS_NOT_PRESERVED))
1100                                 continue;
1101                         ERROR("Stream of %"TS" is missing in second image; "
1102                               "type %d, named=%d, empty=%d",
1103                               inode_any_full_path(inode1),
1104                               strm1->stream_type,
1105                               stream_is_named(strm1),
1106                               is_zero_hash(stream_hash(strm1)));
1107                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1108                 }
1109
1110                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1111                         ERROR("Stream of %"TS" differs; type %d",
1112                               inode_any_full_path(inode1), strm1->stream_type);
1113                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1114                 }
1115         }
1116
1117         return 0;
1118
1119 attrib_mismatch:
1120         ERROR("Attribute mismatch; %"TS" has attributes 0x%08"PRIx32" "
1121               "in first image but attributes 0x%08"PRIx32" in second image",
1122               inode_any_full_path(inode1), inode1->i_attributes,
1123               inode2->i_attributes);
1124         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1125 }
1126
1127 static int
1128 cmp_images(const struct wim_image_metadata *imd1,
1129            const struct wim_image_metadata *imd2, int cmp_flags)
1130 {
1131         struct wim_dentry *root1 = imd1->root_dentry;
1132         struct wim_dentry *root2 = imd2->root_dentry;
1133         const struct wim_inode *inode;
1134         int ret;
1135
1136         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1137         if (ret)
1138                 return ret;
1139
1140         /* Verify that the hard links match up between the two images.  */
1141         assert_inodes_sane(imd1);
1142         assert_inodes_sane(imd2);
1143         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1144         if (ret)
1145                 return ret;
1146
1147         /* Compare corresponding inodes.  */
1148         image_for_each_inode(inode, imd1) {
1149                 ret = cmp_inodes(inode, inode->i_corresponding,
1150                                  imd1, imd2, cmp_flags);
1151                 if (ret)
1152                         return ret;
1153         }
1154
1155         return 0;
1156 }
1157
1158 static int
1159 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1160 {
1161         int ret = select_wim_image(wim, image);
1162         if (!ret) {
1163                 *imd_ret = wim_get_current_image_metadata(wim);
1164                 mark_image_dirty(*imd_ret);
1165         }
1166         return ret;
1167 }
1168
1169 WIMLIBAPI int
1170 wimlib_compare_images(WIMStruct *wim1, int image1,
1171                       WIMStruct *wim2, int image2, int cmp_flags)
1172 {
1173         int ret;
1174         struct wim_image_metadata *imd1, *imd2;
1175
1176         ret = load_image(wim1, image1, &imd1);
1177         if (!ret)
1178                 ret = load_image(wim2, image2, &imd2);
1179         if (!ret)
1180                 ret = cmp_images(imd1, imd2, cmp_flags);
1181         return ret;
1182 }
1183
1184 #endif /* ENABLE_TEST_SUPPORT */