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