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 int
 472 generate_random_file_name(tchar name[], int max_len,
 473                           struct generation_context *ctx)
 474 {
 475         int length;
 476         switch (rand32() % 8) {
 477         default:
 478                 /* short name  */
 479                 length = 1 + (rand32() % 6);
 480                 break;
 481         case 2:
 482         case 3:
 483         case 4:
 484                 /* medium-length name  */
 485                 length = 7 + (rand32() % 8);
 486                 break;
 487         case 5:
 488         case 6:
 489                 /* long name  */
 490                 length = 15 + (rand32() % 15);
 491                 break;
 492         case 7:
 493                 /* very long name  */
 494                 length = 30 + (rand32() % 90);
 495                 break;
 496         }
 497         length = min(length, max_len);
 498         for (int i = 0; i < length; i++)
 499                 name[i] = 'a' + (rand32() % 26);
 500         name[length] = 0;
 501         return length;
 502 }
 503
 504 static u64
 505 select_inode_number(struct generation_context *ctx)
 506 {
 507         const struct wim_inode_table *table = ctx->params->inode_table;
 508         const struct hlist_head *head;
 509         const struct wim_inode *inode;
 510
 511         head = &table->array[rand32() % table->capacity];
 512         hlist_for_each_entry(inode, head, i_hlist_node)
 513                 if (randbool())
 514                         return inode->i_ino;
 515
 516         return rand32();
 517 }
 518
 519 static u32
 520 select_num_children(u32 depth, struct generation_context *ctx)
 521 {
 522         const double b = 1.01230;
 523         u32 r = rand32() % 500;
 524         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
 525                 (2 - exp(0.04/depth));
 526 }
 527
 528 static bool
 529 is_name_forbidden_in_win32_namespace(const utf16lechar *name)
 530 {
 531         static const utf16lechar forbidden_names[][5] = {
 532                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('N'), },
 533                 { cpu_to_le16('P'), cpu_to_le16('R'), cpu_to_le16('N'), },
 534                 { cpu_to_le16('A'), cpu_to_le16('U'), cpu_to_le16('X'), },
 535                 { cpu_to_le16('N'), cpu_to_le16('U'), cpu_to_le16('L'), },
 536                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('1'), },
 537                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('2'), },
 538                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('3'), },
 539                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('4'), },
 540                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('5'), },
 541                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('6'), },
 542                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('7'), },
 543                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('8'), },
 544                 { cpu_to_le16('C'), cpu_to_le16('O'), cpu_to_le16('M'), cpu_to_le16('9'), },
 545                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('1'), },
 546                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('2'), },
 547                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('3'), },
 548                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('4'), },
 549                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('5'), },
 550                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('6'), },
 551                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('7'), },
 552                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('8'), },
 553                 { cpu_to_le16('L'), cpu_to_le16('P'), cpu_to_le16('T'), cpu_to_le16('9'), },
 554         };
 555
 556         if (!name)
 557                 return false;
 558
 559         for (size_t i = 0; i < ARRAY_LEN(forbidden_names); i++)
 560                 if (!cmp_utf16le_strings_z(forbidden_names[i], name, true))
 561                         return true;
 562
 563         return false;
 564 }
 565
 566 static int
 567 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 568                       struct generation_context *ctx)
 569 {
 570         tchar name[12 + 1];
 571         int ret;
 572         const utf16lechar *short_name;
 573         u32 hash;
 574         struct wim_dentry **bucket;
 575
 576         /* If the long name is not allowed in the Win32 namespace, then it
 577          * cannot be assigned a corresponding short name.  */
 578         if (is_name_forbidden_in_win32_namespace(child->d_name))
 579                 return 0;
 580
 581 retry:
 582         /* Don't select a short name that is already used by a long name within
 583          * the same directory.  */
 584         do {
 585                 int len = generate_random_file_name(name, 12, ctx);
 586
 587                 /* Legal short names on Windows take one of the following forms:
 588                  *
 589                  *    - 1 to 8 characters
 590                  *    - 1 to 8 characters, then a dot, then 1 to 3 characters */
 591                 if (len >= 9) {
 592                         if (len == 9)
 593                                 len--;
 594                         else
 595                                 name[8] = T('.');
 596                 }
 597                 name[len] = 0;
 598         } while (get_dentry_child_with_name(dir, name,
 599                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 600
 601
 602         /* Don't select a short name that is already used by another short name
 603          * within the same directory.  */
 604         hash = 0;
 605         for (const tchar *p = name; *p; p++)
 606                 hash = (hash * 31) + totlower(*p);
 607         ret = tstr_get_utf16le(name, &short_name);
 608         if (ret)
 609                 return ret;
 610         FREE(child->d_short_name);
 611         child->d_short_name = utf16le_dup(short_name);
 612         child->d_short_name_nbytes = utf16le_len_bytes(short_name);
 613         tstr_put_utf16le(short_name);
 614
 615         if (!child->d_short_name)
 616                 return WIMLIB_ERR_NOMEM;
 617
 618         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 619
 620         for (struct wim_dentry *d = *bucket; d != NULL;
 621              d = d->d_next_extraction_alias)
 622                 if (!cmp_utf16le_strings_z(child->d_short_name,
 623                                            d->d_short_name, true))
 624                         goto retry;
 625
 626         if (is_name_forbidden_in_win32_namespace(child->d_short_name))
 627                 goto retry;
 628
 629         child->d_next_extraction_alias = *bucket;
 630         *bucket = child;
 631         return 0;
 632 }
 633
 634 static bool
 635 inode_has_short_name(const struct wim_inode *inode)
 636 {
 637         const struct wim_dentry *dentry;
 638
 639         inode_for_each_dentry(dentry, inode)
 640                 if (dentry_has_short_name(dentry))
 641                         return true;
 642
 643         return false;
 644 }
 645
 646 static int
 647 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 648                                struct generation_context *ctx)
 649 {
 650         u32 num_children = select_num_children(depth, ctx);
 651         struct wim_dentry *child;
 652         int ret;
 653
 654         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 655
 656         /* Generate 'num_children' dentries within 'dir'.  Some may be
 657          * directories themselves.  */
 658
 659         for (u32 i = 0; i < num_children; i++) {
 660
 661                 /* Generate the next child dentry.  */
 662
 663                 tchar name[128 + 1];
 664                 struct wim_dentry *duplicate;
 665                 struct wim_inode *inode;
 666                 u64 ino;
 667                 bool is_directory;
 668
 669                 /* Choose a long filename that is unique within the directory.*/
 670                 do {
 671                         generate_random_file_name(name, 128, ctx);
 672                 } while (get_dentry_child_with_name(dir, name,
 673                                                     WIMLIB_CASE_PLATFORM_DEFAULT));
 674
 675                 /* Decide whether to create a directory or not.
 676                  * If not a directory, also decide on the inode number (i.e. we
 677                  * may generate a "hard link" to an existing file).  */
 678                 is_directory = ((rand32() % 16) <= 6);
 679                 if (is_directory)
 680                         ino = 0;
 681                 else
 682                         ino = select_inode_number(ctx);
 683
 684                 /* Create the dentry and add it to the directory.  */
 685                 ret = inode_table_new_dentry(ctx->params->inode_table, name,
 686                                              ino, 0, is_directory, &child);
 687                 if (ret)
 688                         return ret;
 689
 690                 duplicate = dentry_add_child(dir, child);
 691                 wimlib_assert(!duplicate);
 692
 693                 inode = child->d_inode;
 694
 695                 if (inode->i_nlink > 1)  /* Existing inode?  */
 696                         continue;
 697
 698                 /* New inode; set attributes, metadata, and data.  */
 699
 700                 if (is_directory)
 701                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
 702
 703                 ret = set_random_metadata(inode, ctx);
 704                 if (ret)
 705                         return ret;
 706
 707                 ret = set_random_streams(inode, ctx, true);
 708                 if (ret)
 709                         return ret;
 710
 711                 /* Recurse if it's a directory.  */
 712                 if (is_directory &&
 713                     !(inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT))
 714                 {
 715                         ret = generate_dentry_tree_recursive(child, depth + 1,
 716                                                              ctx);
 717                         if (ret)
 718                                 return ret;
 719                 }
 720         }
 721
 722         for_dentry_child(child, dir) {
 723                 /* sometimes generate a unique short name  */
 724                 if (randbool() && !inode_has_short_name(child->d_inode)) {
 725                         ret = set_random_short_name(dir, child, ctx);
 726                         if (ret)
 727                                 return ret;
 728                 }
 729         }
 730
 731         return 0;
 732 }
 733
 734 int
 735 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
 736                      struct scan_params *params)
 737 {
 738         int ret;
 739         struct wim_dentry *root = NULL;
 740         struct generation_context ctx = {
 741                 .params = params,
 742         };
 743
 744         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
 745
 746         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
 747         if (!ret) {
 748                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
 749                 ret = set_random_metadata(root->d_inode, &ctx);
 750         }
 751         if (!ret)
 752                 ret = set_random_streams(root->d_inode, &ctx, false);
 753         if (!ret)
 754                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
 755         if (!ret)
 756                 *root_ret = root;
 757         else
 758                 free_dentry_tree(root, params->blob_table);
 759         return ret;
 760 }
 761
 762 /*----------------------------------------------------------------------------*
 763  *                            File tree comparison                            *
 764  *----------------------------------------------------------------------------*/
 765
 766 #define INDEX_NODE_TO_DENTRY(node)      \
 767         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
 768
 769 static struct wim_dentry *
 770 dentry_first_child(struct wim_dentry *dentry)
 771 {
 772         return INDEX_NODE_TO_DENTRY(
 773                         avl_tree_first_in_order(dentry->d_inode->i_children));
 774 }
 775
 776 static struct wim_dentry *
 777 dentry_next_sibling(struct wim_dentry *dentry)
 778 {
 779         return INDEX_NODE_TO_DENTRY(
 780                         avl_tree_next_in_order(&dentry->d_index_node));
 781 }
 782
 783 /*
 784  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
 785  * tree 'd2', considering long and short filenames.  In addition, set
 786  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
 787  * other tree, and set 'i_corresponding' of each inode to point to the
 788  * unverified corresponding inode in the other tree.
 789  */
 790 static int
 791 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
 792                                    int cmp_flags)
 793 {
 794         struct wim_dentry *child1;
 795         struct wim_dentry *child2;
 796         int ret;
 797
 798         /* Compare long filenames, case sensitively.  */
 799         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
 800                                 d2->d_name, d2->d_name_nbytes / 2,
 801                                 false))
 802         {
 803                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
 804                       dentry_full_path(d1), dentry_full_path(d2));
 805                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 806         }
 807
 808         /* Compare short filenames, case insensitively.  */
 809         if (!(d2->d_short_name_nbytes == 0 &&
 810               (cmp_flags & WIMLIB_CMP_FLAG_SHORT_NAMES_NOT_PRESERVED)) &&
 811             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
 812                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
 813                                 true))
 814         {
 815                 ERROR("Short name mismatch; path=\"%"TS"\"",
 816                       dentry_full_path(d1));
 817                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 818         }
 819
 820         /* Match up the dentries  */
 821         d1->d_corresponding = d2;
 822         d2->d_corresponding = d1;
 823
 824         /* Match up the inodes (may overwrite previous value)  */
 825         d1->d_inode->i_corresponding = d2->d_inode;
 826         d2->d_inode->i_corresponding = d1->d_inode;
 827
 828         /* Process children  */
 829         child1 = dentry_first_child(d1);
 830         child2 = dentry_first_child(d2);
 831         while (child1 || child2) {
 832
 833                 if (!child1 || !child2) {
 834                         ERROR("Child count mismatch; "
 835                               "path1=\"%"TS"\", path2=\"%"TS"\"",
 836                               dentry_full_path(d1), dentry_full_path(d2));
 837                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 838                 }
 839
 840                 /* Recurse on this pair of children.  */
 841                 ret = calc_corresponding_files_recursive(child1, child2,
 842                                                          cmp_flags);
 843                 if (ret)
 844                         return ret;
 845
 846                 /* Continue to the next pair of children.  */
 847                 child1 = dentry_next_sibling(child1);
 848                 child2 = dentry_next_sibling(child2);
 849         }
 850         return 0;
 851 }
 852
 853 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
 854  * even if the images being compared are different.  */
 855 static void
 856 assert_inodes_sane(const struct wim_image_metadata *imd)
 857 {
 858         const struct wim_inode *inode;
 859         const struct wim_dentry *dentry;
 860         size_t link_count;
 861
 862         image_for_each_inode(inode, imd) {
 863                 link_count = 0;
 864                 inode_for_each_dentry(dentry, inode) {
 865                         wimlib_assert(dentry->d_inode == inode);
 866                         link_count++;
 867                 }
 868                 wimlib_assert(link_count > 0);
 869                 wimlib_assert(link_count == inode->i_nlink);
 870                 wimlib_assert(inode->i_corresponding != NULL);
 871         }
 872 }
 873
 874 static int
 875 check_hard_link(struct wim_dentry *dentry, void *_ignore)
 876 {
 877         /* My inode is my corresponding dentry's inode's corresponding inode,
 878          * and my inode's corresponding inode is my corresponding dentry's
 879          * inode.  */
 880         const struct wim_inode *a = dentry->d_inode;
 881         const struct wim_inode *b = dentry->d_corresponding->d_inode;
 882         if (a == b->i_corresponding && a->i_corresponding == b)
 883                 return 0;
 884         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
 885         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 886 }
 887
 888 static int
 889 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
 890            const struct wim_image_metadata *imd1,
 891            const struct wim_image_metadata *imd2, int cmp_flags)
 892 {
 893         const u32 attrib_diff = inode1->i_attributes ^ inode2->i_attributes;
 894         bool reparse_point_should_preserved = true;
 895
 896         /* Compare attributes  */
 897         if (cmp_flags & WIMLIB_CMP_FLAG_ATTRIBUTES_NOT_PRESERVED) {
 898
 899                 /* In this mode, we expect that most attributes are not
 900                  * preserved.  However, FILE_ATTRIBUTE_DIRECTORY should always
 901                  * match.  */
 902                 if (attrib_diff & FILE_ATTRIBUTE_DIRECTORY)
 903                         goto attrib_mismatch;
 904
 905                 /* We may also expect FILE_ATTRIBUTE_REPARSE_POINT to be
 906                  * preserved for symlinks.  It also shouldn't be set if it
 907                  * wasn't set before.  */
 908
 909                 if ((cmp_flags & WIMLIB_CMP_FLAG_IMAGE2_SHOULD_HAVE_SYMLINKS) &&
 910                     inode_is_symlink(inode1))
 911                         reparse_point_should_preserved = true;
 912                 else
 913                         reparse_point_should_preserved = false;
 914
 915                 if ((attrib_diff & FILE_ATTRIBUTE_REPARSE_POINT) &&
 916                     (reparse_point_should_preserved ||
 917                      (inode2->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT)))
 918                         goto attrib_mismatch;
 919         } else {
 920
 921                 /* Most attributes should be preserved.  */
 922
 923                 /* Nothing other than COMPRESSED and NORMAL should have changed.
 924                  */
 925                 if (attrib_diff & ~(FILE_ATTRIBUTE_COMPRESSED |
 926                                     FILE_ATTRIBUTE_NORMAL))
 927                         goto attrib_mismatch;
 928
 929                 /* COMPRESSED shouldn't have changed unless specifically
 930                  * excluded.  */
 931                 if ((attrib_diff & FILE_ATTRIBUTE_COMPRESSED) &&
 932                     !(cmp_flags & WIMLIB_CMP_FLAG_COMPRESSION_NOT_PRESERVED))
 933                         goto attrib_mismatch;
 934
 935                 /* We allow NORMAL to change, but not if the file ended up with
 936                  * other attributes set as well.  */
 937                 if ((attrib_diff & FILE_ATTRIBUTE_NORMAL) &&
 938                     (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
 939                         goto attrib_mismatch;
 940         }
 941
 942         /* Compare security descriptors  */
 943         if (inode_has_security_descriptor(inode1)) {
 944                 if (inode_has_security_descriptor(inode2)) {
 945                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
 946                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
 947                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
 948                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
 949
 950                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
 951                                 ERROR("Security descriptor of %"TS" differs!",
 952                                       inode_any_full_path(inode1));
 953                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 954                         }
 955                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_SECURITY_NOT_PRESERVED)) {
 956                         ERROR("%"TS" has a security descriptor in the first image but "
 957                               "not in the second image!", inode_any_full_path(inode1));
 958                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 959                 }
 960         } else if (inode_has_security_descriptor(inode2)) {
 961                 /* okay --- consider it acceptable if a default security
 962                  * descriptor was assigned  */
 963                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
 964                       /*"not in the first image!", inode_any_full_path(inode1));*/
 965                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
 966         }
 967
 968         /* Compare streams  */
 969         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
 970                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
 971                 const struct wim_inode_stream *strm2;
 972
 973                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
 974                     !reparse_point_should_preserved)
 975                         continue;
 976
 977                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
 978                         continue;
 979
 980                 /* Get the corresponding stream from the second file  */
 981                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
 982
 983                 if (!strm2) {
 984                         /* Corresponding stream not found  */
 985                         if (stream_is_named(strm1) &&
 986                             (cmp_flags & WIMLIB_CMP_FLAG_ADS_NOT_PRESERVED))
 987                                 continue;
 988                         ERROR("Stream of %"TS" is missing in second image; "
 989                               "type %d, named=%d, empty=%d",
 990                               inode_any_full_path(inode1),
 991                               strm1->stream_type,
 992                               stream_is_named(strm1),
 993                               is_zero_hash(stream_hash(strm1)));
 994                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
 995                 }
 996
 997                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
 998                         ERROR("Stream of %"TS" differs; type %d",
 999                               inode_any_full_path(inode1), strm1->stream_type);
1000                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1001                 }
1002         }
1003
1004         return 0;
1005
1006 attrib_mismatch:
1007         ERROR("Attribute mismatch; %"TS" has attributes 0x%08"PRIx32" "
1008               "in first image but attributes 0x%08"PRIx32" in second image",
1009               inode_any_full_path(inode1), inode1->i_attributes,
1010               inode2->i_attributes);
1011         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1012 }
1013
1014 static int
1015 cmp_images(const struct wim_image_metadata *imd1,
1016            const struct wim_image_metadata *imd2, int cmp_flags)
1017 {
1018         struct wim_dentry *root1 = imd1->root_dentry;
1019         struct wim_dentry *root2 = imd2->root_dentry;
1020         const struct wim_inode *inode;
1021         int ret;
1022
1023         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1024         if (ret)
1025                 return ret;
1026
1027         /* Verify that the hard links match up between the two images.  */
1028         assert_inodes_sane(imd1);
1029         assert_inodes_sane(imd2);
1030         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1031         if (ret)
1032                 return ret;
1033
1034         /* Compare corresponding inodes.  */
1035         image_for_each_inode(inode, imd1) {
1036                 ret = cmp_inodes(inode, inode->i_corresponding,
1037                                  imd1, imd2, cmp_flags);
1038                 if (ret)
1039                         return ret;
1040         }
1041
1042         return 0;
1043 }
1044
1045 static int
1046 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1047 {
1048         int ret = select_wim_image(wim, image);
1049         if (!ret) {
1050                 *imd_ret = wim_get_current_image_metadata(wim);
1051                 mark_image_dirty(*imd_ret);
1052         }
1053         return ret;
1054 }
1055
1056 WIMLIBAPI int
1057 wimlib_compare_images(WIMStruct *wim1, int image1,
1058                       WIMStruct *wim2, int image2, int cmp_flags)
1059 {
1060         int ret;
1061         struct wim_image_metadata *imd1, *imd2;
1062
1063         ret = load_image(wim1, image1, &imd1);
1064         if (!ret)
1065                 ret = load_image(wim2, image2, &imd2);
1066         if (!ret)
1067                 ret = cmp_images(imd1, imd2, cmp_flags);
1068         return ret;
1069 }
1070
1071 #endif /* ENABLE_TEST_SUPPORT */