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