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 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
 255                                   FILE_ATTRIBUTE_HIDDEN |
 256                                   FILE_ATTRIBUTE_SYSTEM |
 257                                   FILE_ATTRIBUTE_ARCHIVE |
 258                                   FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
 259                                   FILE_ATTRIBUTE_COMPRESSED |
 260                                   FILE_ATTRIBUTE_SPARSE_FILE));
 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         /* Start by initializing to a random byte */
 327         memset(buffer, rand32() % 256, size);
 328
 329         /* Add some random bytes in some random places */
 330         for (size_t i = 0; i < num_byte_fills; i++) {
 331                 u8 b = rand8();
 332
 333                 size_t count = ((double)size / (double)num_byte_fills) *
 334                                 ((double)rand32() / 2e9);
 335                 size_t offset = rand32() & ~mask;
 336
 337                 while (count--) {
 338                         buffer[(offset +
 339                                 ((rand32()) & mask)) % size] = b;
 340                 }
 341
 342
 343                 if (rand32() % 4 == 0)
 344                         mask = (size_t)-1 << rand32() % 4;
 345         }
 346
 347         /* Sometimes add a wave pattern */
 348         if (rand32() % 8 == 0) {
 349                 double magnitude = rand32() % 128;
 350                 double scale = 1.0 / (1 + (rand32() % 256));
 351
 352                 for (size_t i = 0; i < size; i++)
 353                         buffer[i] += (int)(magnitude * cos(i * scale));
 354         }
 355
 356         /* Sometimes add some zero regions (holes) */
 357         if (rand32() % 4 == 0) {
 358                 size_t num_holes = 1 + (rand32() % 16);
 359                 for (size_t i = 0; i < num_holes; i++) {
 360                         size_t hole_offset = rand32() % size;
 361                         size_t hole_len = min(size - hole_offset,
 362                                               size / (1 + (rand32() % 16)));
 363                         memset(&buffer[hole_offset], 0, hole_len);
 364                 }
 365         }
 366 }
 367
 368 static int
 369 add_stream(struct wim_inode *inode, struct generation_context *ctx,
 370            int stream_type, const utf16lechar *stream_name,
 371            void *buffer, size_t size)
 372 {
 373         struct blob_descriptor *blob = NULL;
 374         struct wim_inode_stream *strm;
 375
 376         if (size) {
 377                 blob = new_blob_descriptor();
 378                 if (!blob)
 379                         goto err_nomem;
 380                 blob->attached_buffer = buffer;
 381                 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
 382                 blob->size = size;
 383         }
 384
 385         strm = inode_add_stream(inode, stream_type, stream_name, blob);
 386         if (unlikely(!strm))
 387                 goto err_nomem;
 388
 389         prepare_unhashed_blob(blob, inode, strm->stream_id,
 390                               ctx->params->unhashed_blobs);
 391         return 0;
 392
 393 err_nomem:
 394         free_blob_descriptor(blob);
 395         return WIMLIB_ERR_NOMEM;
 396 }
 397
 398 static int
 399 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
 400 {
 401         void *buffer = NULL;
 402         size_t rpdatalen = select_stream_size(ctx) % (REPARSE_DATA_MAX_SIZE + 1);
 403
 404         if (rpdatalen) {
 405                 buffer = MALLOC(rpdatalen);
 406                 if (!buffer)
 407                         return WIMLIB_ERR_NOMEM;
 408                 generate_data(buffer, rpdatalen, ctx);
 409         }
 410
 411         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 412         inode->i_rp_reserved = rand16();
 413
 414         if (rpdatalen >= GUID_SIZE && randbool()) {
 415                 /* Non-Microsoft reparse tag (16-byte GUID required)  */
 416                 u8 *guid = buffer;
 417                 guid[6] = (guid[6] & 0x0F) | 0x40;
 418                 guid[8] = (guid[8] & 0x3F) | 0x80;
 419                 inode->i_reparse_tag = 0x00000100;
 420         } else {
 421                 /* Microsoft reparse tag  */
 422                 inode->i_reparse_tag = 0x80000000;
 423         }
 424
 425         return add_stream(inode, ctx, STREAM_TYPE_REPARSE_POINT, NO_STREAM_NAME,
 426                           buffer, rpdatalen);
 427 }
 428
 429 static int
 430 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
 431                        const utf16lechar *stream_name)
 432 {
 433         void *buffer = NULL;
 434         size_t size;
 435
 436         size = select_stream_size(ctx);
 437         if (size) {
 438                 buffer = MALLOC(size);
 439                 if (!buffer)
 440                         return WIMLIB_ERR_NOMEM;
 441                 generate_data(buffer, size, ctx);
 442         }
 443
 444         return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
 445                           buffer, size);
 446 }
 447
 448 static int
 449 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
 450 {
 451         int ret;
 452         u32 r;
 453
 454         /* Reparse point (sometimes)  */
 455         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
 456                 ret = set_random_reparse_point(inode, ctx);
 457                 if (ret)
 458                         return ret;
 459         }
 460
 461         /* Unnamed data stream (nondirectories only)  */
 462         if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)) {
 463                 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
 464                 if (ret)
 465                         return ret;
 466         }
 467
 468         /* Named data streams (sometimes)  */
 469         r = rand32() % 256;
 470         if (r > 230) {
 471                 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
 472                 r -= 230;
 473                 while (r--) {
 474                         ret = add_random_data_stream(inode, ctx, stream_name);
 475                         if (ret)
 476                                 return ret;
 477                         stream_name[0] += cpu_to_le16(1);
 478                 }
 479         }
 480
 481         return 0;
 482 }
 483
 484 static inline bool
 485 is_valid_windows_filename_char(utf16lechar c)
 486 {
 487         return le16_to_cpu(c) > 31 &&
 488                 c != cpu_to_le16('/') &&
 489                 c != cpu_to_le16('<') &&
 490                 c != cpu_to_le16('>') &&
 491                 c != cpu_to_le16(':') &&
 492                 c != cpu_to_le16('"') &&
 493                 c != cpu_to_le16('/' ) &&
 494                 c != cpu_to_le16('\\') &&
 495                 c != cpu_to_le16('|') &&
 496                 c != cpu_to_le16('?') &&
 497                 c != cpu_to_le16('*');
 498 }
 499
 500 /* Is the character valid in a filename on the current platform? */
 501 static inline bool
 502 is_valid_filename_char(utf16lechar c)
 503 {
 504 #ifdef __WIN32__
 505         return is_valid_windows_filename_char(c);
 506 #else
 507         return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
 508 #endif
 509 }
 510
 511 /* Generate a random filename and return its length. */
 512 static int
 513 generate_random_filename(utf16lechar name[], int max_len,
 514                          struct generation_context *ctx)
 515 {
 516         int len;
 517
 518         /* Choose the length of the name. */
 519         switch (rand32() % 8) {
 520         default:
 521                 /* short name  */
 522                 len = 1 + (rand32() % 6);
 523                 break;
 524         case 2:
 525         case 3:
 526         case 4:
 527                 /* medium-length name  */
 528                 len = 7 + (rand32() % 8);
 529                 break;
 530         case 5:
 531         case 6:
 532                 /* long name  */
 533                 len = 15 + (rand32() % 15);
 534                 break;
 535         case 7:
 536                 /* very long name  */
 537                 len = 30 + (rand32() % 90);
 538                 break;
 539         }
 540         len = min(len, max_len);
 541
 542 retry:
 543         /* Generate the characters in the name. */
 544         for (int i = 0; i < len; i++) {
 545                 do {
 546                         name[i] = rand16();
 547                 } while (!is_valid_filename_char(name[i]));
 548         }
 549
 550         /* Add a null terminator. */
 551         name[len] = cpu_to_le16('\0');
 552
 553         /* Don't generate . and .. */
 554         if (name[0] == cpu_to_le16('.') &&
 555             (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
 556                 goto retry;
 557
 558         return len;
 559 }
 560
 561 /* The set of characters which are valid in short filenames. */
 562 static const char valid_short_name_chars[] = {
 563         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 564         'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
 565         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 566         '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
 567         '}', '~',
 568         /* Note: Windows does not allow space and 128-255 in short filenames
 569          * (tested on both NTFS and FAT). */
 570 };
 571
 572 static int
 573 generate_short_name_component(utf16lechar p[], int len)
 574 {
 575         for (int i = 0; i < len; i++) {
 576                 char c = valid_short_name_chars[rand32() %
 577                                                 ARRAY_LEN(valid_short_name_chars)];
 578                 p[i] = cpu_to_le16(c);
 579         }
 580         return len;
 581 }
 582
 583 /* Generate a random short (8.3) filename and return its length.
 584  * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
 585 static int
 586 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
 587 {
 588         /*
 589          * Legal short names on Windows consist of 1 to 8 characters, optionally
 590          * followed by a dot then 1 to 3 more characters.  Only certain
 591          * characters are allowed.
 592          */
 593         int base_len = 1 + (rand32() % 8);
 594         int ext_len = rand32() % 4;
 595         int total_len;
 596
 597         base_len = generate_short_name_component(name, base_len);
 598
 599         if (ext_len) {
 600                 name[base_len] = cpu_to_le16('.');
 601                 ext_len = generate_short_name_component(&name[base_len + 1],
 602                                                         ext_len);
 603                 total_len = base_len + 1 + ext_len;
 604         } else {
 605                 total_len = base_len;
 606         }
 607         name[total_len] = cpu_to_le16('\0');
 608         return total_len;
 609 }
 610
 611 static u64
 612 select_inode_number(struct generation_context *ctx)
 613 {
 614         const struct wim_inode_table *table = ctx->params->inode_table;
 615         const struct hlist_head *head;
 616         const struct wim_inode *inode;
 617
 618         head = &table->array[rand32() % table->capacity];
 619         hlist_for_each_entry(inode, head, i_hlist_node)
 620                 if (randbool())
 621                         return inode->i_ino;
 622
 623         return rand32();
 624 }
 625
 626 static u32
 627 select_num_children(u32 depth, struct generation_context *ctx)
 628 {
 629         const double b = 1.01230;
 630         u32 r = rand32() % 500;
 631         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
 632                 (2 - exp(0.04/depth));
 633 }
 634
 635 static bool
 636 is_name_valid_in_win32_namespace(const utf16lechar *name)
 637 {
 638         const utf16lechar *p;
 639
 640         static const char * const reserved_names[] = {
 641                  "CON",  "PRN",  "AUX",  "NUL",
 642                  "COM1", "COM2", "COM3", "COM4", "COM5",
 643                  "COM6", "COM7", "COM8", "COM9",
 644                  "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
 645                  "LPT6", "LPT7", "LPT8", "LPT9",
 646         };
 647
 648         /* The name must be nonempty. */
 649         if (!name || !*name)
 650                 return false;
 651
 652         /* All characters must be valid on Windows. */
 653         for (p = name; *p; p++)
 654                 if (!is_valid_windows_filename_char(*p))
 655                         return false;
 656
 657         /* Note: a trailing dot or space is permitted, even though on Windows
 658          * such a file can only be accessed using a WinNT-style path. */
 659
 660         /* The name can't be one of the reserved names or be a reserved name
 661          * with an extension.  Case insensitive. */
 662         for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
 663                 for (size_t j = 0; ; j++) {
 664                         u16 c1 = le16_to_cpu(name[j]);
 665                         u16 c2 = reserved_names[i][j];
 666                         if (c2 == '\0') {
 667                                 if (c1 == '\0' || c1 == '.')
 668                                         return false;
 669                                 break;
 670                         }
 671                         if (upcase[c1] != upcase[c2])
 672                                 break;
 673                 }
 674         }
 675
 676         return true;
 677 }
 678
 679 static int
 680 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 681                       struct generation_context *ctx)
 682 {
 683         utf16lechar name[12 + 1];
 684         int name_len;
 685         u32 hash;
 686         struct wim_dentry **bucket;
 687
 688         /* If the long name is not allowed in the Win32 namespace, then it
 689          * cannot be assigned a corresponding short name.  */
 690         if (!is_name_valid_in_win32_namespace(child->d_name))
 691                 return 0;
 692
 693 retry:
 694         /* Don't select a short name that is already used by a long name within
 695          * the same directory.  */
 696         do {
 697                 name_len = generate_random_short_name(name, ctx);
 698         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 699                                                     WIMLIB_CASE_INSENSITIVE));
 700
 701
 702         /* Don't select a short name that is already used by another short name
 703          * within the same directory.  */
 704         hash = 0;
 705         for (const utf16lechar *p = name; *p; p++)
 706                 hash = (hash * 31) + *p;
 707         FREE(child->d_short_name);
 708         child->d_short_name = memdup(name, (name_len + 1) * 2);
 709         child->d_short_name_nbytes = name_len * 2;
 710
 711         if (!child->d_short_name)
 712                 return WIMLIB_ERR_NOMEM;
 713
 714         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 715
 716         for (struct wim_dentry *d = *bucket; d != NULL;
 717              d = d->d_next_extraction_alias) {
 718                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
 719                                          d->d_short_name, d->d_short_name_nbytes / 2,
 720                                          true)) {
 721                         goto retry;
 722                 }
 723         }
 724
 725         if (!is_name_valid_in_win32_namespace(child->d_short_name))
 726                 goto retry;
 727
 728         child->d_next_extraction_alias = *bucket;
 729         *bucket = child;
 730         return 0;
 731 }
 732
 733 static bool
 734 inode_has_short_name(const struct wim_inode *inode)
 735 {
 736         const struct wim_dentry *dentry;
 737
 738         inode_for_each_dentry(dentry, inode)
 739                 if (dentry_has_short_name(dentry))
 740                         return true;
 741
 742         return false;
 743 }
 744
 745 static int
 746 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 747                                struct generation_context *ctx)
 748 {
 749         u32 num_children = select_num_children(depth, ctx);
 750         struct wim_dentry *child;
 751         int ret;
 752
 753         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 754
 755         /* Generate 'num_children' dentries within 'dir'.  Some may be
 756          * directories themselves.  */
 757
 758         for (u32 i = 0; i < num_children; i++) {
 759
 760                 /* Generate the next child dentry.  */
 761                 struct wim_inode *inode;
 762                 u64 ino;
 763                 bool is_directory = (rand32() % 16 <= 6);
 764                 bool is_reparse = (rand32() % 8 == 0);
 765                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
 766                 int name_len;
 767                 struct wim_dentry *duplicate;
 768
 769                 /*
 770                  * Select an inode number for the new file.  Sometimes choose an
 771                  * existing inode number (i.e. create a hard link).  However,
 772                  * wimlib intentionally doesn't honor directory hard links, and
 773                  * reparse points cannot be represented in the WIM file format
 774                  * at all; so don't create hard links for such files.
 775                  */
 776                 if (is_directory || is_reparse)
 777                         ino = 0;
 778                 else
 779                         ino = select_inode_number(ctx);
 780
 781                 /* Create the dentry. */
 782                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
 783                                              ino, 0, ino == 0, &child);
 784                 if (ret)
 785                         return ret;
 786
 787                 /* Choose a filename that is unique within the directory.*/
 788                 do {
 789                         name_len = generate_random_filename(name,
 790                                                             ARRAY_LEN(name) - 1,
 791                                                             ctx);
 792                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 793                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 794
 795                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
 796                 if (ret) {
 797                         free_dentry(child);
 798                         return ret;
 799                 }
 800
 801                 /* Add the dentry to the directory. */
 802                 duplicate = dentry_add_child(dir, child);
 803                 wimlib_assert(!duplicate);
 804
 805                 inode = child->d_inode;
 806
 807                 if (inode->i_nlink > 1)  /* Existing inode?  */
 808                         continue;
 809
 810                 /* New inode; set attributes, metadata, and data.  */
 811
 812                 if (is_directory)
 813                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
 814                 if (is_reparse)
 815                         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 816
 817                 ret = set_random_streams(inode, ctx);
 818                 if (ret)
 819                         return ret;
 820
 821                 ret = set_random_metadata(inode, ctx);
 822                 if (ret)
 823                         return ret;
 824
 825                 /* Recurse if it's a directory.  */
 826                 if (is_directory && !is_reparse) {
 827                         ret = generate_dentry_tree_recursive(child, depth + 1,
 828                                                              ctx);
 829                         if (ret)
 830                                 return ret;
 831                 }
 832         }
 833
 834         for_dentry_child(child, dir) {
 835                 /* sometimes generate a unique short name  */
 836                 if (randbool() && !inode_has_short_name(child->d_inode)) {
 837                         ret = set_random_short_name(dir, child, ctx);
 838                         if (ret)
 839                                 return ret;
 840                 }
 841         }
 842
 843         return 0;
 844 }
 845
 846 int
 847 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
 848                      struct scan_params *params)
 849 {
 850         int ret;
 851         struct wim_dentry *root = NULL;
 852         struct generation_context ctx = {
 853                 .params = params,
 854         };
 855
 856         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
 857
 858         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
 859         if (!ret) {
 860                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
 861                 ret = set_random_streams(root->d_inode, &ctx);
 862         }
 863         if (!ret)
 864                 ret = set_random_metadata(root->d_inode, &ctx);
 865         if (!ret)
 866                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
 867         if (!ret)
 868                 *root_ret = root;
 869         else
 870                 free_dentry_tree(root, params->blob_table);
 871         return ret;
 872 }
 873
 874 /*----------------------------------------------------------------------------*
 875  *                            File tree comparison                            *
 876  *----------------------------------------------------------------------------*/
 877
 878 #define INDEX_NODE_TO_DENTRY(node)      \
 879         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
 880
 881 static struct wim_dentry *
 882 dentry_first_child(struct wim_dentry *dentry)
 883 {
 884         return INDEX_NODE_TO_DENTRY(
 885                         avl_tree_first_in_order(dentry->d_inode->i_children));
 886 }
 887
 888 static struct wim_dentry *
 889 dentry_next_sibling(struct wim_dentry *dentry)
 890 {
 891         return INDEX_NODE_TO_DENTRY(
 892                         avl_tree_next_in_order(&dentry->d_index_node));
 893 }
 894
 895 /*
 896  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
 897  * tree 'd2', considering long and short filenames.  In addition, set
 898  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
 899  * other tree, and set 'i_corresponding' of each inode to point to the
 900  * unverified corresponding inode in the other tree.
 901  */
 902 static int
 903 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
 904                                    int cmp_flags)
 905 {
 906         struct wim_dentry *child1;
 907         struct wim_dentry *child2;
 908         int ret;
 909
 910         /* Compare long filenames, case sensitively.  */
 911         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
 912                                 d2->d_name, d2->d_name_nbytes / 2,
 913                                 false))
 914         {
 915                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
 916                       dentry_full_path(d1), dentry_full_path(d2));
 917                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 918         }
 919
 920         /* Compare short filenames, case insensitively.  */
 921         if (!(d2->d_short_name_nbytes == 0 &&
 922               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
 923             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
 924                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
 925                                 true))
 926         {
 927                 ERROR("Short name mismatch; path=\"%"TS"\"",
 928                       dentry_full_path(d1));
 929                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 930         }
 931
 932         /* Match up the dentries  */
 933         d1->d_corresponding = d2;
 934         d2->d_corresponding = d1;
 935
 936         /* Match up the inodes (may overwrite previous value)  */
 937         d1->d_inode->i_corresponding = d2->d_inode;
 938         d2->d_inode->i_corresponding = d1->d_inode;
 939
 940         /* Process children  */
 941         child1 = dentry_first_child(d1);
 942         child2 = dentry_first_child(d2);
 943         while (child1 || child2) {
 944
 945                 if (!child1 || !child2) {
 946                         ERROR("Child count mismatch; "
 947                               "path1=\"%"TS"\", path2=\"%"TS"\"",
 948                               dentry_full_path(d1), dentry_full_path(d2));
 949                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 950                 }
 951
 952                 /* Recurse on this pair of children.  */
 953                 ret = calc_corresponding_files_recursive(child1, child2,
 954                                                          cmp_flags);
 955                 if (ret)
 956                         return ret;
 957
 958                 /* Continue to the next pair of children.  */
 959                 child1 = dentry_next_sibling(child1);
 960                 child2 = dentry_next_sibling(child2);
 961         }
 962         return 0;
 963 }
 964
 965 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
 966  * even if the images being compared are different.  */
 967 static void
 968 assert_inodes_sane(const struct wim_image_metadata *imd)
 969 {
 970         const struct wim_inode *inode;
 971         const struct wim_dentry *dentry;
 972         size_t link_count;
 973
 974         image_for_each_inode(inode, imd) {
 975                 link_count = 0;
 976                 inode_for_each_dentry(dentry, inode) {
 977                         wimlib_assert(dentry->d_inode == inode);
 978                         link_count++;
 979                 }
 980                 wimlib_assert(link_count > 0);
 981                 wimlib_assert(link_count == inode->i_nlink);
 982                 wimlib_assert(inode->i_corresponding != NULL);
 983         }
 984 }
 985
 986 static int
 987 check_hard_link(struct wim_dentry *dentry, void *_ignore)
 988 {
 989         /* My inode is my corresponding dentry's inode's corresponding inode,
 990          * and my inode's corresponding inode is my corresponding dentry's
 991          * inode.  */
 992         const struct wim_inode *a = dentry->d_inode;
 993         const struct wim_inode *b = dentry->d_corresponding->d_inode;
 994         if (a == b->i_corresponding && a->i_corresponding == b)
 995                 return 0;
 996         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
 997         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 998 }
 999
1000 static const struct {
1001         u32 flag;
1002         const char *name;
1003 } file_attr_flags[] = {
1004         {FILE_ATTRIBUTE_READONLY,            "READONLY"},
1005         {FILE_ATTRIBUTE_HIDDEN,              "HIDDEN"},
1006         {FILE_ATTRIBUTE_SYSTEM,              "SYSTEM"},
1007         {FILE_ATTRIBUTE_DIRECTORY,           "DIRECTORY"},
1008         {FILE_ATTRIBUTE_ARCHIVE,             "ARCHIVE"},
1009         {FILE_ATTRIBUTE_DEVICE,              "DEVICE"},
1010         {FILE_ATTRIBUTE_NORMAL,              "NORMAL"},
1011         {FILE_ATTRIBUTE_TEMPORARY,           "TEMPORARY"},
1012         {FILE_ATTRIBUTE_SPARSE_FILE,         "SPARSE_FILE"},
1013         {FILE_ATTRIBUTE_REPARSE_POINT,       "REPARSE_POINT"},
1014         {FILE_ATTRIBUTE_COMPRESSED,          "COMPRESSED"},
1015         {FILE_ATTRIBUTE_OFFLINE,             "OFFLINE"},
1016         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1017         {FILE_ATTRIBUTE_ENCRYPTED,           "ENCRYPTED"},
1018         {FILE_ATTRIBUTE_VIRTUAL,             "VIRTUAL"},
1019 };
1020
1021 static int
1022 cmp_attributes(const struct wim_inode *inode1,
1023                const struct wim_inode *inode2, int cmp_flags)
1024 {
1025         const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1026         const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1027         const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1028
1029         /* NORMAL may change, but it must never be set along with other
1030          * attributes. */
1031         if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1032             (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1033                 goto mismatch;
1034
1035         /* DIRECTORY must not change. */
1036         if (changed & FILE_ATTRIBUTE_DIRECTORY)
1037                 goto mismatch;
1038
1039         /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1040          * symlink. */
1041         if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1042             !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1043               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1044               !inode_is_symlink(inode1)))
1045                 goto mismatch;
1046
1047         /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1048          * mode if the inode is a directory. */
1049         if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1050             !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1051               ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1052                              WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1053                ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1054                 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1055                 goto mismatch;
1056
1057         /* COMPRESSED may change in UNIX and NTFS-3G modes.  (It *should* be
1058          * preserved in NTFS-3G mode, but it's not implemented yet.) */
1059         if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1060             !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1061                            WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1062                 goto mismatch;
1063
1064         /* All other attributes can change in UNIX mode, but not in any other
1065          * mode. */
1066         if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1067                          FILE_ATTRIBUTE_DIRECTORY |
1068                          FILE_ATTRIBUTE_REPARSE_POINT |
1069                          FILE_ATTRIBUTE_SPARSE_FILE |
1070                          FILE_ATTRIBUTE_COMPRESSED)) &&
1071             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1072                 goto mismatch;
1073
1074         return 0;
1075
1076 mismatch:
1077         ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1078               inode_any_full_path(inode1), inode1->i_attributes,
1079               inode2->i_attributes);
1080         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1081                 u32 flag = file_attr_flags[i].flag;
1082                 if (changed & flag) {
1083                         fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1084                                 file_attr_flags[i].name,
1085                                 (set & flag) ? "set" : "cleared");
1086                 }
1087         }
1088         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1089 }
1090
1091 static int
1092 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1093            const struct wim_image_metadata *imd1,
1094            const struct wim_image_metadata *imd2, int cmp_flags)
1095 {
1096         int ret;
1097
1098         /* Compare attributes  */
1099         ret = cmp_attributes(inode1, inode2, cmp_flags);
1100         if (ret)
1101                 return ret;
1102
1103         /* Compare security descriptors  */
1104         if (inode_has_security_descriptor(inode1)) {
1105                 if (inode_has_security_descriptor(inode2)) {
1106                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1107                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1108                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1109                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1110
1111                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1112                                 ERROR("Security descriptor of %"TS" differs!",
1113                                       inode_any_full_path(inode1));
1114                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1115                         }
1116                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1117                         ERROR("%"TS" has a security descriptor in the first image but "
1118                               "not in the second image!", inode_any_full_path(inode1));
1119                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1120                 }
1121         } else if (inode_has_security_descriptor(inode2)) {
1122                 /* okay --- consider it acceptable if a default security
1123                  * descriptor was assigned  */
1124                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1125                       /*"not in the first image!", inode_any_full_path(inode1));*/
1126                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1127         }
1128
1129         /* Compare streams  */
1130         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1131                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1132                 const struct wim_inode_stream *strm2;
1133
1134                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1135                     (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1136                      !inode_is_symlink(inode1)))
1137                         continue;
1138
1139                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1140                         continue;
1141
1142                 /* Get the corresponding stream from the second file  */
1143                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1144
1145                 if (!strm2) {
1146                         /* Corresponding stream not found  */
1147                         if (stream_is_named(strm1) &&
1148                             (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1149                                 continue;
1150                         ERROR("Stream of %"TS" is missing in second image; "
1151                               "type %d, named=%d, empty=%d",
1152                               inode_any_full_path(inode1),
1153                               strm1->stream_type,
1154                               stream_is_named(strm1),
1155                               is_zero_hash(stream_hash(strm1)));
1156                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1157                 }
1158
1159                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1160                         ERROR("Stream of %"TS" differs; type %d",
1161                               inode_any_full_path(inode1), strm1->stream_type);
1162                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1163                 }
1164         }
1165
1166         return 0;
1167 }
1168
1169 static int
1170 cmp_images(const struct wim_image_metadata *imd1,
1171            const struct wim_image_metadata *imd2, int cmp_flags)
1172 {
1173         struct wim_dentry *root1 = imd1->root_dentry;
1174         struct wim_dentry *root2 = imd2->root_dentry;
1175         const struct wim_inode *inode;
1176         int ret;
1177
1178         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1179         if (ret)
1180                 return ret;
1181
1182         /* Verify that the hard links match up between the two images.  */
1183         assert_inodes_sane(imd1);
1184         assert_inodes_sane(imd2);
1185         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1186         if (ret)
1187                 return ret;
1188
1189         /* Compare corresponding inodes.  */
1190         image_for_each_inode(inode, imd1) {
1191                 ret = cmp_inodes(inode, inode->i_corresponding,
1192                                  imd1, imd2, cmp_flags);
1193                 if (ret)
1194                         return ret;
1195         }
1196
1197         return 0;
1198 }
1199
1200 static int
1201 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1202 {
1203         int ret = select_wim_image(wim, image);
1204         if (!ret) {
1205                 *imd_ret = wim_get_current_image_metadata(wim);
1206                 mark_image_dirty(*imd_ret);
1207         }
1208         return ret;
1209 }
1210
1211 WIMLIBAPI int
1212 wimlib_compare_images(WIMStruct *wim1, int image1,
1213                       WIMStruct *wim2, int image2, int cmp_flags)
1214 {
1215         int ret;
1216         struct wim_image_metadata *imd1, *imd2;
1217
1218         ret = load_image(wim1, image1, &imd1);
1219         if (!ret)
1220                 ret = load_image(wim2, image2, &imd2);
1221         if (!ret)
1222                 ret = cmp_images(imd1, imd2, cmp_flags);
1223         return ret;
1224 }
1225
1226 #endif /* ENABLE_TEST_SUPPORT */