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