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