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