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