wlfuzz: compare timestamps
[wimlib] / src / test_support.c
1 /*
2  * test_support.c - Supporting code for tests
3  */
4
5 /*
6  * Copyright (C) 2015-2017 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 #include <stdlib.h>
39 #include <sys/stat.h>
40 #include <unistd.h>
41
42 #include "wimlib.h"
43 #include "wimlib/endianness.h"
44 #include "wimlib/encoding.h"
45 #include "wimlib/metadata.h"
46 #include "wimlib/dentry.h"
47 #include "wimlib/inode.h"
48 #include "wimlib/object_id.h"
49 #include "wimlib/reparse.h"
50 #include "wimlib/scan.h"
51 #include "wimlib/security_descriptor.h"
52 #include "wimlib/test_support.h"
53 #include "wimlib/unix_data.h"
54 #include "wimlib/xattr.h"
55
56 /*----------------------------------------------------------------------------*
57  *                            File tree generation                            *
58  *----------------------------------------------------------------------------*/
59
60 struct generation_context {
61         struct scan_params *params;
62         struct wim_dentry *used_short_names[256];
63         bool metadata_only;
64 };
65
66 static u32
67 rand32(void)
68 {
69         static u64 state = 0x55DB93D0AB838771;
70
71         /* A simple linear congruential generator  */
72         state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
73         return state >> 16;
74 }
75
76 static bool
77 randbool(void)
78 {
79         return (rand32() & 1) != 0;
80 }
81
82 static u8
83 rand8(void)
84 {
85         return (u8)rand32();
86 }
87
88 static u16
89 rand16(void)
90 {
91         return (u16)rand32();
92 }
93
94 static u64
95 rand64(void)
96 {
97         return ((u64)rand32() << 32) | rand32();
98 }
99
100 static u64
101 generate_random_timestamp(void)
102 {
103         /* When setting timestamps on Windows:
104          * - 0 is a special value meaning "not specified"
105          * - if the high bit is set you get STATUS_INVALID_PARAMETER  */
106         return (1 + rand64()) & ~(1ULL << 63);
107 }
108
109 static inline bool
110 is_valid_windows_filename_char(utf16lechar c)
111 {
112         return le16_to_cpu(c) > 31 &&
113                 c != cpu_to_le16('/') &&
114                 c != cpu_to_le16('<') &&
115                 c != cpu_to_le16('>') &&
116                 c != cpu_to_le16(':') &&
117                 c != cpu_to_le16('"') &&
118                 c != cpu_to_le16('/' ) &&
119                 c != cpu_to_le16('\\') &&
120                 c != cpu_to_le16('|') &&
121                 c != cpu_to_le16('?') &&
122                 c != cpu_to_le16('*');
123 }
124
125 /* Is the character valid in a filename on the current platform? */
126 static inline bool
127 is_valid_filename_char(utf16lechar c)
128 {
129 #ifdef __WIN32__
130         return is_valid_windows_filename_char(c);
131 #else
132         return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
133 #endif
134 }
135
136 /* Generate a random filename and return its length. */
137 static int
138 generate_random_filename(utf16lechar name[], int max_len,
139                          struct generation_context *ctx)
140 {
141         int len;
142
143         /* Choose the length of the name. */
144         switch (rand32() % 8) {
145         default:
146                 /* short name  */
147                 len = 1 + (rand32() % 6);
148                 break;
149         case 2:
150         case 3:
151         case 4:
152                 /* medium-length name  */
153                 len = 7 + (rand32() % 8);
154                 break;
155         case 5:
156         case 6:
157                 /* long name  */
158                 len = 15 + (rand32() % 15);
159                 break;
160         case 7:
161                 /* very long name  */
162                 len = 30 + (rand32() % 90);
163                 break;
164         }
165         len = min(len, max_len);
166
167 retry:
168         /* Generate the characters in the name. */
169         for (int i = 0; i < len; i++) {
170                 do {
171                         name[i] = rand16();
172                 } while (!is_valid_filename_char(name[i]));
173         }
174
175         /* Add a null terminator. */
176         name[len] = cpu_to_le16('\0');
177
178         /* Don't generate . and .. */
179         if (name[0] == cpu_to_le16('.') &&
180             (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
181                 goto retry;
182
183         return len;
184 }
185
186 /* The set of characters which are valid in short filenames. */
187 static const char valid_short_name_chars[] = {
188         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
189         'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
190         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
191         '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
192         '}', '~',
193         /* Note: Windows does not allow space and 128-255 in short filenames
194          * (tested on both NTFS and FAT). */
195 };
196
197 static int
198 generate_short_name_component(utf16lechar p[], int len)
199 {
200         for (int i = 0; i < len; i++) {
201                 char c = valid_short_name_chars[rand32() %
202                                                 ARRAY_LEN(valid_short_name_chars)];
203                 p[i] = cpu_to_le16(c);
204         }
205         return len;
206 }
207
208 /* Generate a random short (8.3) filename and return its length.
209  * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
210 static int
211 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
212 {
213         /*
214          * Legal short names on Windows consist of 1 to 8 characters, optionally
215          * followed by a dot then 1 to 3 more characters.  Only certain
216          * characters are allowed.
217          */
218         int base_len = 1 + (rand32() % 8);
219         int ext_len = rand32() % 4;
220         int total_len;
221
222         base_len = generate_short_name_component(name, base_len);
223
224         if (ext_len) {
225                 name[base_len] = cpu_to_le16('.');
226                 ext_len = generate_short_name_component(&name[base_len + 1],
227                                                         ext_len);
228                 total_len = base_len + 1 + ext_len;
229         } else {
230                 total_len = base_len;
231         }
232         name[total_len] = cpu_to_le16('\0');
233         return total_len;
234 }
235
236
237 static const struct {
238         u8 num_subauthorities;
239         u64 identifier_authority;
240         u32 subauthorities[6];
241 } common_sids[] = {
242         { 1, 0, {0}}, /* NULL_SID  */
243         { 1, 1, {0}}, /* WORLD_SID */
244         { 1, 2, {0}}, /* LOCAL_SID */
245         { 1, 3, {0}}, /* CREATOR_OWNER_SID */
246         { 1, 3, {1}}, /* CREATOR_GROUP_SID */
247         { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
248         { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
249         // { 0, 5, {}},  /* NT_AUTHORITY_SID */
250         { 1, 5, {1}}, /* DIALUP_SID */
251         { 1, 5, {2}}, /* NETWORK_SID */
252         { 1, 5, {3}}, /* BATCH_SID */
253         { 1, 5, {4}}, /* INTERACTIVE_SID */
254         { 1, 5, {6}}, /* SERVICE_SID */
255         { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
256         { 1, 5, {8}}, /* PROXY_SID */
257         { 1, 5, {9}}, /* SERVER_LOGON_SID */
258         { 1, 5, {10}}, /* SELF_SID */
259         { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
260         { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
261         { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
262         { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
263         { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
264         { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
265         { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer  */
266         { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS  */
267 };
268
269 /* Generate a SID and return its size in bytes.  */
270 static size_t
271 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
272 {
273         u32 r = rand32();
274
275         sid->revision = 1;
276
277         if (r & 1) {
278                 /* Common SID  */
279                 r = (r >> 1) % ARRAY_LEN(common_sids);
280
281                 sid->sub_authority_count = common_sids[r].num_subauthorities;
282                 for (int i = 0; i < 6; i++) {
283                         sid->identifier_authority[i] =
284                                 common_sids[r].identifier_authority >> (40 - i * 8);
285                 }
286                 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
287                         sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
288         } else {
289                 /* Random SID  */
290
291                 sid->sub_authority_count = 1 + ((r >> 1) % 15);
292
293                 for (int i = 0; i < 6; i++)
294                         sid->identifier_authority[i] = rand8();
295
296                 for (int i = 0; i < sid->sub_authority_count; i++)
297                         sid->sub_authority[i] = cpu_to_le32(rand32());
298         }
299         return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
300 }
301
302 /* Generate an ACL and return its size in bytes.  */
303 static size_t
304 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
305 {
306         u8 *p;
307         u16 ace_count;
308
309         ace_count = rand32() % 16;
310
311         acl->revision = 2;
312         acl->sbz1 = 0;
313         acl->ace_count = cpu_to_le16(ace_count);
314         acl->sbz2 = 0;
315
316         p = (u8 *)(acl + 1);
317
318         for (int i = 0; i < ace_count; i++) {
319                 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
320
321                 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
322                  * same for all  */
323                 if (dacl)
324                         ace->hdr.type = rand32() % 2;
325                 else
326                         ace->hdr.type = 2;
327                 ace->hdr.flags = rand8();
328                 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
329
330                 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
331                         generate_random_sid(&ace->sid, ctx);
332                 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
333         }
334
335         acl->acl_size = cpu_to_le16(p - (u8 *)acl);
336         return p - (u8 *)acl;
337 }
338
339 /* Generate a security descriptor and return its size in bytes.  */
340 static size_t
341 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
342 {
343         wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
344         u16 control;
345         u8 *p;
346
347         control = rand16();
348
349         control &= (wimlib_SE_DACL_AUTO_INHERITED |
350                     wimlib_SE_SACL_AUTO_INHERITED);
351
352         control |= wimlib_SE_SELF_RELATIVE |
353                    wimlib_SE_DACL_PRESENT |
354                    wimlib_SE_SACL_PRESENT;
355
356         desc->revision = 1;
357         desc->sbz1 = 0;
358         desc->control = cpu_to_le16(control);
359
360         p = (u8 *)(desc + 1);
361
362         desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
363         p += generate_random_sid((wimlib_SID *)p, ctx);
364
365         desc->group_offset = cpu_to_le32(p - (u8 *)desc);
366         p += generate_random_sid((wimlib_SID *)p, ctx);
367
368         if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
369                 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
370                 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
371         } else {
372                 desc->dacl_offset = cpu_to_le32(0);
373         }
374
375         if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
376                 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
377                 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
378         } else {
379                 desc->sacl_offset = cpu_to_le32(0);
380         }
381
382         return p - (u8 *)desc;
383 }
384
385 static bool
386 am_root(void)
387 {
388 #ifdef __WIN32__
389         return false;
390 #else
391         return (getuid() == 0);
392 #endif
393 }
394
395 static u32
396 generate_uid(void)
397 {
398 #ifdef __WIN32__
399         return 0;
400 #else
401         if (am_root())
402                 return rand32();
403         return getuid();
404 #endif
405 }
406
407 static u32
408 generate_gid(void)
409 {
410 #ifdef __WIN32__
411         return 0;
412 #else
413         if (am_root())
414                 return rand32();
415         return getgid();
416 #endif
417 }
418
419 #ifdef __WIN32__
420 #  ifndef S_IFLNK
421 #    define S_IFLNK  0120000
422 #  endif
423 #  ifndef S_IFSOCK
424 #    define S_IFSOCK 0140000
425 #  endif
426 #endif
427
428 static int
429 set_random_unix_metadata(struct wim_inode *inode)
430 {
431         struct wimlib_unix_data dat;
432
433         dat.uid = generate_uid();
434         dat.gid = generate_gid();
435         if (inode_is_symlink(inode))
436                 dat.mode = S_IFLNK | 0777;
437         else if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)
438                 dat.mode = S_IFDIR | 0700 | (rand32() % 07777);
439         else if (is_zero_hash(inode_get_hash_of_unnamed_data_stream(inode)) &&
440                  randbool() && am_root())
441         {
442                 dat.mode = rand32() % 07777;
443                 switch (rand32() % 4) {
444                 case 0:
445                         dat.mode |= S_IFIFO;
446                         break;
447                 case 1:
448                         dat.mode |= S_IFCHR;
449                         dat.rdev = 261; /* /dev/zero */
450                         break;
451                 case 2:
452                         dat.mode |= S_IFBLK;
453                         dat.rdev = 261; /* /dev/zero */
454                         break;
455                 default:
456                         dat.mode |= S_IFSOCK;
457                         break;
458                 }
459         } else {
460                 dat.mode = S_IFREG | 0400 | (rand32() % 07777);
461         }
462         dat.rdev = 0;
463
464         if (!inode_set_unix_data(inode, &dat, UNIX_DATA_ALL))
465                 return WIMLIB_ERR_NOMEM;
466
467         return 0;
468 }
469
470 static noinline_for_stack int
471 set_random_xattrs(struct wim_inode *inode)
472 {
473         int num_xattrs = 1 + rand32() % 16;
474         char entries[8192] _aligned_attribute(4);
475         struct wimlib_xattr_entry *entry = (void *)entries;
476         size_t entries_size;
477         struct wimlib_unix_data unix_data;
478         const char *prefix = "user.";
479         static const char capability_name[] = "security.capability";
480         bool generated_capability_xattr = false;
481
482         /*
483          * On Linux, xattrs in the "user" namespace are only permitted on
484          * regular files and directories.  For other types of files we can use
485          * the "trusted" namespace, but this requires root.
486          */
487         if (inode_is_symlink(inode) ||
488             (inode_get_unix_data(inode, &unix_data) &&
489              !S_ISREG(unix_data.mode) && !S_ISDIR(unix_data.mode)))
490         {
491                 if (!am_root())
492                         return 0;
493                 prefix = "trusted.";
494         }
495
496         for (int i = 0; i < num_xattrs; i++) {
497                 int value_len = rand32() % 64;
498                 u8 *p;
499
500                 entry->reserved = 0;
501                 entry->value_len = cpu_to_le32(value_len);
502
503                 if (rand32() % 16 == 0 && am_root() &&
504                     !generated_capability_xattr) {
505                         int name_len = sizeof(capability_name) - 1;
506                         entry->name_len = cpu_to_le16(name_len);
507                         p = mempcpy(entry->name, capability_name, name_len);
508                         generated_capability_xattr = true;
509                 } else {
510                         int name_len = 1 + rand32() % 64;
511
512                         entry->name_len = cpu_to_le16(strlen(prefix) + name_len);
513                         p = mempcpy(entry->name, prefix, strlen(prefix));
514                         *p++ = 'a' + i;
515                         for (int j = 1; j < name_len; j++) {
516                                 do {
517                                         *p = rand8();
518                                 } while (*p == '\0');
519                                 p++;
520                         }
521                 }
522                 for (int j = 0; j < value_len; j++)
523                         *p++ = rand8();
524
525                 while ((uintptr_t)p % 4)
526                         *p++ = 0;
527
528                 entry = (void *)p;
529         }
530
531         entries_size = (char *)entry - entries;
532         wimlib_assert(entries_size > 0 && entries_size % 4 == 0 &&
533                       entries_size <= sizeof(entries));
534
535         if (!inode_set_linux_xattrs(inode, entries, entries_size))
536                 return WIMLIB_ERR_NOMEM;
537
538         return 0;
539 }
540
541 static int
542 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
543 {
544         u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
545                                   FILE_ATTRIBUTE_HIDDEN |
546                                   FILE_ATTRIBUTE_SYSTEM |
547                                   FILE_ATTRIBUTE_ARCHIVE |
548                                   FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
549                                   FILE_ATTRIBUTE_COMPRESSED |
550                                   FILE_ATTRIBUTE_SPARSE_FILE));
551
552         /* File attributes  */
553         inode->i_attributes |= attrib;
554
555         /* Timestamps  */
556         inode->i_creation_time = generate_random_timestamp();
557         inode->i_last_access_time = generate_random_timestamp();
558         inode->i_last_write_time = generate_random_timestamp();
559
560         /* Security descriptor  */
561         if (randbool()) {
562                 char desc[8192] _aligned_attribute(8);
563                 size_t size;
564
565                 size = generate_random_security_descriptor(desc, ctx);
566
567                 wimlib_assert(size <= sizeof(desc));
568
569                 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
570                                                      desc, size);
571                 if (unlikely(inode->i_security_id < 0))
572                         return WIMLIB_ERR_NOMEM;
573         }
574
575         /* Object ID  */
576         if (rand32() % 32 == 0) {
577                 struct wimlib_object_id object_id;
578
579                 for (int i = 0; i < sizeof(object_id); i++)
580                         *((u8 *)&object_id + i) = rand8();
581                 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
582                         return WIMLIB_ERR_NOMEM;
583         }
584
585         /* Standard UNIX permissions and special files */
586         if (rand32() % 16 == 0) {
587                 int ret = set_random_unix_metadata(inode);
588                 if (ret)
589                         return ret;
590         }
591
592         /* Extended attributes */
593         if (rand32() % 32 == 0) {
594                 int ret = set_random_xattrs(inode);
595                 if (ret)
596                         return ret;
597         }
598
599         return 0;
600
601 }
602
603 /* Choose a random size for generated file data.  We want to usually generate
604  * empty, small, or medium files, but occasionally generate large files.  */
605 static size_t
606 select_stream_size(struct generation_context *ctx)
607 {
608         if (ctx->metadata_only)
609                 return 0;
610
611         switch (rand32() % 2048) {
612         default:
613                 /* Empty  */
614                 return 0;
615         case 600 ... 799:
616                 /* Microscopic  */
617                 return rand32() % 64;
618         case 800 ... 1319:
619                 /* Tiny  */
620                 return rand32() % 4096;
621         case 1320 ... 1799:
622                 /* Small  */
623                 return rand32() % 32768;
624         case 1800 ... 2046:
625                 /* Medium  */
626                 return rand32() % 262144;
627         case 2047:
628                 /* Large  */
629                 return rand32() % 134217728;
630         }
631 }
632
633 /* Fill 'buffer' with 'size' bytes of "interesting" file data.  */
634 static void
635 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
636 {
637         size_t mask = -1;
638         size_t num_byte_fills = rand32() % 256;
639
640         if (size == 0)
641                 return;
642
643         /* Start by initializing to a random byte */
644         memset(buffer, rand32() % 256, size);
645
646         /* Add some random bytes in some random places */
647         for (size_t i = 0; i < num_byte_fills; i++) {
648                 u8 b = rand8();
649
650                 size_t count = ((double)size / (double)num_byte_fills) *
651                                 ((double)rand32() / 2e9);
652                 size_t offset = rand32() & ~mask;
653
654                 while (count--) {
655                         buffer[(offset +
656                                 ((rand32()) & mask)) % size] = b;
657                 }
658
659
660                 if (rand32() % 4 == 0)
661                         mask = (size_t)-1 << rand32() % 4;
662         }
663
664         /* Sometimes add a wave pattern */
665         if (rand32() % 8 == 0) {
666                 double magnitude = rand32() % 128;
667                 double scale = 1.0 / (1 + (rand32() % 256));
668
669                 for (size_t i = 0; i < size; i++)
670                         buffer[i] += (int)(magnitude * cos(i * scale));
671         }
672
673         /* Sometimes add some zero regions (holes) */
674         if (rand32() % 4 == 0) {
675                 size_t num_holes = 1 + (rand32() % 16);
676                 for (size_t i = 0; i < num_holes; i++) {
677                         size_t hole_offset = rand32() % size;
678                         size_t hole_len = min(size - hole_offset,
679                                               size / (1 + (rand32() % 16)));
680                         memset(&buffer[hole_offset], 0, hole_len);
681                 }
682         }
683 }
684
685 static int
686 add_stream(struct wim_inode *inode, struct generation_context *ctx,
687            int stream_type, const utf16lechar *stream_name,
688            void *buffer, size_t size)
689 {
690         struct blob_descriptor *blob = NULL;
691         struct wim_inode_stream *strm;
692
693         if (size) {
694                 blob = new_blob_descriptor();
695                 if (!blob)
696                         goto err_nomem;
697                 blob->attached_buffer = buffer;
698                 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
699                 blob->size = size;
700         }
701
702         strm = inode_add_stream(inode, stream_type, stream_name, blob);
703         if (unlikely(!strm))
704                 goto err_nomem;
705
706         prepare_unhashed_blob(blob, inode, strm->stream_id,
707                               ctx->params->unhashed_blobs);
708         return 0;
709
710 err_nomem:
711         free_blob_descriptor(blob);
712         return WIMLIB_ERR_NOMEM;
713 }
714
715 static noinline_for_stack int
716 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
717 {
718         struct reparse_buffer_disk rpbuf;
719         size_t rpdatalen;
720
721         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
722
723         if (randbool()) {
724                 /* Symlink */
725                 int target_nchars;
726                 utf16lechar *targets = (utf16lechar *)rpbuf.link.symlink.data;
727
728                 inode->i_reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
729
730                 target_nchars = generate_random_filename(targets, 255, ctx);
731
732                 rpbuf.link.substitute_name_offset = cpu_to_le16(0);
733                 rpbuf.link.substitute_name_nbytes = cpu_to_le16(2*target_nchars);
734                 rpbuf.link.print_name_offset = cpu_to_le16(2*(target_nchars + 1));
735                 rpbuf.link.print_name_nbytes = cpu_to_le16(2*target_nchars);
736                 targets[target_nchars] = cpu_to_le16(0);
737                 memcpy(&targets[target_nchars + 1], targets, 2*target_nchars);
738                 targets[target_nchars + 1 + target_nchars] = cpu_to_le16(0);
739
740                 rpbuf.link.symlink.flags = cpu_to_le32(SYMBOLIC_LINK_RELATIVE);
741                 rpdatalen = ((u8 *)targets - rpbuf.rpdata) +
742                                 2*(target_nchars + 1 + target_nchars + 1);
743         } else {
744                 rpdatalen = select_stream_size(ctx) % REPARSE_DATA_MAX_SIZE;
745                 generate_data(rpbuf.rpdata, rpdatalen, ctx);
746
747                 if (rpdatalen >= GUID_SIZE && randbool()) {
748                         /* Non-Microsoft reparse tag (16-byte GUID required)  */
749                         u8 *guid = rpbuf.rpdata;
750                         guid[6] = (guid[6] & 0x0F) | 0x40;
751                         guid[8] = (guid[8] & 0x3F) | 0x80;
752                         inode->i_reparse_tag = 0x00000100;
753                 } else {
754                         /* Microsoft reparse tag  */
755                         inode->i_reparse_tag = 0x80000000;
756                 }
757                 inode->i_rp_reserved = rand16();
758         }
759
760         wimlib_assert(rpdatalen < REPARSE_DATA_MAX_SIZE);
761
762         if (!inode_add_stream_with_data(inode, STREAM_TYPE_REPARSE_POINT,
763                                         NO_STREAM_NAME, rpbuf.rpdata,
764                                         rpdatalen, ctx->params->blob_table))
765                 return WIMLIB_ERR_NOMEM;
766
767         return 0;
768 }
769
770 static int
771 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
772                        const utf16lechar *stream_name)
773 {
774         void *buffer = NULL;
775         size_t size;
776
777         size = select_stream_size(ctx);
778         if (size) {
779                 buffer = MALLOC(size);
780                 if (!buffer)
781                         return WIMLIB_ERR_NOMEM;
782                 generate_data(buffer, size, ctx);
783         }
784
785         return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
786                           buffer, size);
787 }
788
789 static int
790 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
791 {
792         int ret;
793         u32 r;
794
795         /* Reparse point (sometimes)  */
796         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
797                 ret = set_random_reparse_point(inode, ctx);
798                 if (ret)
799                         return ret;
800         }
801
802         /* Unnamed data stream (nondirectories and non-symlinks only)  */
803         if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) &&
804             !inode_is_symlink(inode)) {
805                 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
806                 if (ret)
807                         return ret;
808         }
809
810         /* Named data streams (sometimes)  */
811         r = rand32() % 256;
812         if (r > 230) {
813                 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
814                 r -= 230;
815                 while (r--) {
816                         ret = add_random_data_stream(inode, ctx, stream_name);
817                         if (ret)
818                                 return ret;
819                         stream_name[0] += cpu_to_le16(1);
820                 }
821         }
822
823         return 0;
824 }
825
826 static u64
827 select_inode_number(struct generation_context *ctx)
828 {
829         const struct wim_inode_table *table = ctx->params->inode_table;
830         const struct hlist_head *head;
831         const struct wim_inode *inode;
832
833         head = &table->array[rand32() % table->capacity];
834         hlist_for_each_entry(inode, head, i_hlist_node)
835                 if (randbool())
836                         return inode->i_ino;
837
838         return rand32();
839 }
840
841 static u32
842 select_num_children(u32 depth, struct generation_context *ctx)
843 {
844         const double b = 1.01230;
845         u32 r = rand32() % 500;
846         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
847                 (2 - exp(0.04/depth));
848 }
849
850 static bool
851 is_name_valid_in_win32_namespace(const utf16lechar *name)
852 {
853         const utf16lechar *p;
854
855         static const char * const reserved_names[] = {
856                  "CON",  "PRN",  "AUX",  "NUL",
857                  "COM1", "COM2", "COM3", "COM4", "COM5",
858                  "COM6", "COM7", "COM8", "COM9",
859                  "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
860                  "LPT6", "LPT7", "LPT8", "LPT9",
861         };
862
863         /* The name must be nonempty. */
864         if (!name || !*name)
865                 return false;
866
867         /* All characters must be valid on Windows. */
868         for (p = name; *p; p++)
869                 if (!is_valid_windows_filename_char(*p))
870                         return false;
871
872         /* Note: a trailing dot or space is permitted, even though on Windows
873          * such a file can only be accessed using a WinNT-style path. */
874
875         /* The name can't be one of the reserved names or be a reserved name
876          * with an extension.  Case insensitive. */
877         for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
878                 for (size_t j = 0; ; j++) {
879                         u16 c1 = le16_to_cpu(name[j]);
880                         u16 c2 = reserved_names[i][j];
881                         if (c2 == '\0') {
882                                 if (c1 == '\0' || c1 == '.')
883                                         return false;
884                                 break;
885                         }
886                         if (upcase[c1] != upcase[c2])
887                                 break;
888                 }
889         }
890
891         return true;
892 }
893
894 static int
895 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
896                       struct generation_context *ctx)
897 {
898         utf16lechar name[12 + 1];
899         int name_len;
900         u32 hash;
901         struct wim_dentry **bucket;
902
903         /* If the long name is not allowed in the Win32 namespace, then it
904          * cannot be assigned a corresponding short name.  */
905         if (!is_name_valid_in_win32_namespace(child->d_name))
906                 return 0;
907
908 retry:
909         /* Don't select a short name that is already used by a long name within
910          * the same directory.  */
911         do {
912                 name_len = generate_random_short_name(name, ctx);
913         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
914                                                     WIMLIB_CASE_INSENSITIVE));
915
916
917         /* Don't select a short name that is already used by another short name
918          * within the same directory.  */
919         hash = 0;
920         for (const utf16lechar *p = name; *p; p++)
921                 hash = (hash * 31) + *p;
922         FREE(child->d_short_name);
923         child->d_short_name = memdup(name, (name_len + 1) * 2);
924         child->d_short_name_nbytes = name_len * 2;
925
926         if (!child->d_short_name)
927                 return WIMLIB_ERR_NOMEM;
928
929         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
930
931         for (struct wim_dentry *d = *bucket; d != NULL;
932              d = d->d_next_extraction_alias) {
933                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
934                                          d->d_short_name, d->d_short_name_nbytes / 2,
935                                          true)) {
936                         goto retry;
937                 }
938         }
939
940         if (!is_name_valid_in_win32_namespace(child->d_short_name))
941                 goto retry;
942
943         child->d_next_extraction_alias = *bucket;
944         *bucket = child;
945         return 0;
946 }
947
948 static bool
949 inode_has_short_name(const struct wim_inode *inode)
950 {
951         const struct wim_dentry *dentry;
952
953         inode_for_each_dentry(dentry, inode)
954                 if (dentry_has_short_name(dentry))
955                         return true;
956
957         return false;
958 }
959
960 static int
961 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
962                                struct generation_context *ctx)
963 {
964         u32 num_children = select_num_children(depth, ctx);
965         struct wim_dentry *child;
966         int ret;
967
968         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
969
970         /* Generate 'num_children' dentries within 'dir'.  Some may be
971          * directories themselves.  */
972
973         for (u32 i = 0; i < num_children; i++) {
974
975                 /* Generate the next child dentry.  */
976                 struct wim_inode *inode;
977                 u64 ino;
978                 bool is_directory = (rand32() % 16 <= 6);
979                 bool is_reparse = (rand32() % 8 == 0);
980                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
981                 int name_len;
982                 struct wim_dentry *duplicate;
983
984                 /*
985                  * Select an inode number for the new file.  Sometimes choose an
986                  * existing inode number (i.e. create a hard link).  However,
987                  * wimlib intentionally doesn't honor directory hard links, and
988                  * reparse points cannot be represented in the WIM file format
989                  * at all; so don't create hard links for such files.
990                  */
991                 if (is_directory || is_reparse)
992                         ino = 0;
993                 else
994                         ino = select_inode_number(ctx);
995
996                 /* Create the dentry. */
997                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
998                                              ino, 0, ino == 0, &child);
999                 if (ret)
1000                         return ret;
1001
1002                 /* Choose a filename that is unique within the directory.*/
1003                 do {
1004                         name_len = generate_random_filename(name,
1005                                                             ARRAY_LEN(name) - 1,
1006                                                             ctx);
1007                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
1008                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
1009
1010                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
1011                 if (ret) {
1012                         free_dentry(child);
1013                         return ret;
1014                 }
1015
1016                 /* Add the dentry to the directory. */
1017                 duplicate = dentry_add_child(dir, child);
1018                 wimlib_assert(!duplicate);
1019
1020                 inode = child->d_inode;
1021
1022                 if (inode->i_nlink > 1)  /* Existing inode?  */
1023                         continue;
1024
1025                 /* New inode; set attributes, metadata, and data.  */
1026
1027                 if (is_directory)
1028                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
1029                 if (is_reparse)
1030                         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
1031
1032                 ret = set_random_streams(inode, ctx);
1033                 if (ret)
1034                         return ret;
1035
1036                 ret = set_random_metadata(inode, ctx);
1037                 if (ret)
1038                         return ret;
1039
1040                 /* Recurse if it's a directory.  */
1041                 if (is_directory && !is_reparse) {
1042                         ret = generate_dentry_tree_recursive(child, depth + 1,
1043                                                              ctx);
1044                         if (ret)
1045                                 return ret;
1046                 }
1047         }
1048
1049         for_dentry_child(child, dir) {
1050                 /* sometimes generate a unique short name  */
1051                 if (randbool() && !inode_has_short_name(child->d_inode)) {
1052                         ret = set_random_short_name(dir, child, ctx);
1053                         if (ret)
1054                                 return ret;
1055                 }
1056         }
1057
1058         return 0;
1059 }
1060
1061 int
1062 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
1063                      struct scan_params *params)
1064 {
1065         int ret;
1066         struct wim_dentry *root = NULL;
1067         struct generation_context ctx = {
1068                 .params = params,
1069         };
1070
1071         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
1072
1073         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
1074         if (!ret) {
1075                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
1076                 ret = set_random_streams(root->d_inode, &ctx);
1077         }
1078         if (!ret)
1079                 ret = set_random_metadata(root->d_inode, &ctx);
1080         if (!ret)
1081                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
1082         if (!ret)
1083                 *root_ret = root;
1084         else
1085                 free_dentry_tree(root, params->blob_table);
1086         return ret;
1087 }
1088
1089 /*----------------------------------------------------------------------------*
1090  *                            File tree comparison                            *
1091  *----------------------------------------------------------------------------*/
1092
1093 #define INDEX_NODE_TO_DENTRY(node)      \
1094         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
1095
1096 static struct wim_dentry *
1097 dentry_first_child(struct wim_dentry *dentry)
1098 {
1099         return INDEX_NODE_TO_DENTRY(
1100                         avl_tree_first_in_order(dentry->d_inode->i_children));
1101 }
1102
1103 static struct wim_dentry *
1104 dentry_next_sibling(struct wim_dentry *dentry)
1105 {
1106         return INDEX_NODE_TO_DENTRY(
1107                         avl_tree_next_in_order(&dentry->d_index_node));
1108 }
1109
1110 /*
1111  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
1112  * tree 'd2', considering long and short filenames.  In addition, set
1113  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
1114  * other tree, and set 'i_corresponding' of each inode to point to the
1115  * unverified corresponding inode in the other tree.
1116  */
1117 static int
1118 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
1119                                    int cmp_flags)
1120 {
1121         struct wim_dentry *child1;
1122         struct wim_dentry *child2;
1123         int ret;
1124
1125         /* Compare long filenames, case sensitively.  */
1126         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
1127                                 d2->d_name, d2->d_name_nbytes / 2,
1128                                 false))
1129         {
1130                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
1131                       dentry_full_path(d1), dentry_full_path(d2));
1132                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1133         }
1134
1135         /* Compare short filenames, case insensitively.  */
1136         if (!(d2->d_short_name_nbytes == 0 &&
1137               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
1138             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
1139                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
1140                                 true))
1141         {
1142                 ERROR("Short name mismatch; path=\"%"TS"\"",
1143                       dentry_full_path(d1));
1144                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1145         }
1146
1147         /* Match up the dentries  */
1148         d1->d_corresponding = d2;
1149         d2->d_corresponding = d1;
1150
1151         /* Match up the inodes (may overwrite previous value)  */
1152         d1->d_inode->i_corresponding = d2->d_inode;
1153         d2->d_inode->i_corresponding = d1->d_inode;
1154
1155         /* Process children  */
1156         child1 = dentry_first_child(d1);
1157         child2 = dentry_first_child(d2);
1158         while (child1 || child2) {
1159
1160                 if (!child1 || !child2) {
1161                         ERROR("Child count mismatch; "
1162                               "path1=\"%"TS"\", path2=\"%"TS"\"",
1163                               dentry_full_path(d1), dentry_full_path(d2));
1164                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1165                 }
1166
1167                 /* Recurse on this pair of children.  */
1168                 ret = calc_corresponding_files_recursive(child1, child2,
1169                                                          cmp_flags);
1170                 if (ret)
1171                         return ret;
1172
1173                 /* Continue to the next pair of children.  */
1174                 child1 = dentry_next_sibling(child1);
1175                 child2 = dentry_next_sibling(child2);
1176         }
1177         return 0;
1178 }
1179
1180 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
1181  * even if the images being compared are different.  */
1182 static void
1183 assert_inodes_sane(const struct wim_image_metadata *imd)
1184 {
1185         const struct wim_inode *inode;
1186         const struct wim_dentry *dentry;
1187         size_t link_count;
1188
1189         image_for_each_inode(inode, imd) {
1190                 link_count = 0;
1191                 inode_for_each_dentry(dentry, inode) {
1192                         wimlib_assert(dentry->d_inode == inode);
1193                         link_count++;
1194                 }
1195                 wimlib_assert(link_count > 0);
1196                 wimlib_assert(link_count == inode->i_nlink);
1197                 wimlib_assert(inode->i_corresponding != NULL);
1198         }
1199 }
1200
1201 static int
1202 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1203 {
1204         /* My inode is my corresponding dentry's inode's corresponding inode,
1205          * and my inode's corresponding inode is my corresponding dentry's
1206          * inode.  */
1207         const struct wim_inode *a = dentry->d_inode;
1208         const struct wim_inode *b = dentry->d_corresponding->d_inode;
1209         if (a == b->i_corresponding && a->i_corresponding == b)
1210                 return 0;
1211         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1212         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1213 }
1214
1215 static const struct {
1216         u32 flag;
1217         const char *name;
1218 } file_attr_flags[] = {
1219         {FILE_ATTRIBUTE_READONLY,            "READONLY"},
1220         {FILE_ATTRIBUTE_HIDDEN,              "HIDDEN"},
1221         {FILE_ATTRIBUTE_SYSTEM,              "SYSTEM"},
1222         {FILE_ATTRIBUTE_DIRECTORY,           "DIRECTORY"},
1223         {FILE_ATTRIBUTE_ARCHIVE,             "ARCHIVE"},
1224         {FILE_ATTRIBUTE_DEVICE,              "DEVICE"},
1225         {FILE_ATTRIBUTE_NORMAL,              "NORMAL"},
1226         {FILE_ATTRIBUTE_TEMPORARY,           "TEMPORARY"},
1227         {FILE_ATTRIBUTE_SPARSE_FILE,         "SPARSE_FILE"},
1228         {FILE_ATTRIBUTE_REPARSE_POINT,       "REPARSE_POINT"},
1229         {FILE_ATTRIBUTE_COMPRESSED,          "COMPRESSED"},
1230         {FILE_ATTRIBUTE_OFFLINE,             "OFFLINE"},
1231         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1232         {FILE_ATTRIBUTE_ENCRYPTED,           "ENCRYPTED"},
1233         {FILE_ATTRIBUTE_VIRTUAL,             "VIRTUAL"},
1234 };
1235
1236 static int
1237 cmp_attributes(const struct wim_inode *inode1,
1238                const struct wim_inode *inode2, int cmp_flags)
1239 {
1240         const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1241         const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1242         const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1243
1244         /* NORMAL may change, but it must never be set along with other
1245          * attributes. */
1246         if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1247             (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1248                 goto mismatch;
1249
1250         /* DIRECTORY may change in UNIX mode for symlinks. */
1251         if (changed & FILE_ATTRIBUTE_DIRECTORY) {
1252                 if (!(inode_is_symlink(inode1) &&
1253                       (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)))
1254                         goto mismatch;
1255         }
1256
1257         /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1258          * symlink. */
1259         if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1260             !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1261               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1262               !inode_is_symlink(inode1)))
1263                 goto mismatch;
1264
1265         /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1266          * mode if the inode is a directory. */
1267         if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1268             !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1269               ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1270                              WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1271                ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1272                 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1273                 goto mismatch;
1274
1275         /* COMPRESSED may change in UNIX and NTFS-3G modes.  (It *should* be
1276          * preserved in NTFS-3G mode, but it's not implemented yet.) */
1277         if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1278             !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1279                            WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1280                 goto mismatch;
1281
1282         /* All other attributes can change in UNIX mode, but not in any other
1283          * mode. */
1284         if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1285                          FILE_ATTRIBUTE_DIRECTORY |
1286                          FILE_ATTRIBUTE_REPARSE_POINT |
1287                          FILE_ATTRIBUTE_SPARSE_FILE |
1288                          FILE_ATTRIBUTE_COMPRESSED)) &&
1289             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1290                 goto mismatch;
1291
1292         return 0;
1293
1294 mismatch:
1295         ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1296               inode_any_full_path(inode1), inode1->i_attributes,
1297               inode2->i_attributes);
1298         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1299                 u32 flag = file_attr_flags[i].flag;
1300                 if (changed & flag) {
1301                         fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1302                                 file_attr_flags[i].name,
1303                                 (set & flag) ? "set" : "cleared");
1304                 }
1305         }
1306         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1307 }
1308
1309 static int
1310 cmp_object_ids(const struct wim_inode *inode1,
1311                const struct wim_inode *inode2, int cmp_flags)
1312 {
1313         const void *objid1, *objid2;
1314         u32 len1, len2;
1315
1316         objid1 = inode_get_object_id(inode1, &len1);
1317         objid2 = inode_get_object_id(inode2, &len2);
1318
1319         if (!objid1 && !objid2)
1320                 return 0;
1321
1322         if (objid1 && !objid2) {
1323                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1324                         return 0;
1325                 ERROR("%"TS" unexpectedly lost its object ID",
1326                       inode_any_full_path(inode1));
1327                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1328         }
1329
1330         if (!objid1 && objid2) {
1331                 ERROR("%"TS" unexpectedly gained an object ID",
1332                       inode_any_full_path(inode1));
1333                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1334         }
1335
1336         if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1337                 ERROR("Object ID of %"TS" differs",
1338                       inode_any_full_path(inode1));
1339                 fprintf(stderr, "objid1=");
1340                 print_byte_field(objid1, len1, stderr);
1341                 fprintf(stderr, "\nobjid2=");
1342                 print_byte_field(objid2, len2, stderr);
1343                 fprintf(stderr, "\n");
1344                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1345         }
1346
1347         return 0;
1348 }
1349
1350 static int
1351 cmp_unix_metadata(const struct wim_inode *inode1,
1352                   const struct wim_inode *inode2, int cmp_flags)
1353 {
1354         struct wimlib_unix_data dat1, dat2;
1355         bool present1, present2;
1356
1357         present1 = inode_get_unix_data(inode1, &dat1);
1358         present2 = inode_get_unix_data(inode2, &dat2);
1359
1360         if (!present1 && !present2)
1361                 return 0;
1362
1363         if (present1 && !present2) {
1364                 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1365                                  WIMLIB_CMP_FLAG_WINDOWS_MODE))
1366                         return 0;
1367                 ERROR("%"TS" unexpectedly lost its UNIX metadata",
1368                       inode_any_full_path(inode1));
1369                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1370         }
1371
1372         if (!present1 && present2) {
1373                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1374                         return 0;
1375                 ERROR("%"TS" unexpectedly gained UNIX metadata",
1376                       inode_any_full_path(inode1));
1377                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1378         }
1379
1380         if (memcmp(&dat1, &dat2, sizeof(dat1)) != 0) {
1381                 ERROR("UNIX metadata of %"TS" differs: "
1382                       "[uid=%u, gid=%u, mode=0%o, rdev=%u] vs. "
1383                       "[uid=%u, gid=%u, mode=0%o, rdev=%u]",
1384                       inode_any_full_path(inode1),
1385                       dat1.uid, dat1.gid, dat1.mode, dat1.rdev,
1386                       dat2.uid, dat2.gid, dat2.mode, dat2.rdev);
1387                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1388         }
1389
1390         return 0;
1391 }
1392
1393 static int
1394 cmp_xattr_names(const void *p1, const void *p2)
1395 {
1396         const struct wimlib_xattr_entry *entry1 = *(const struct wimlib_xattr_entry **)p1;
1397         const struct wimlib_xattr_entry *entry2 = *(const struct wimlib_xattr_entry **)p2;
1398         u16 name_len1 = le16_to_cpu(entry1->name_len);
1399         u16 name_len2 = le16_to_cpu(entry2->name_len);
1400         int res;
1401
1402         res = cmp_u32(name_len1, name_len2);
1403         if (res)
1404                 return res;
1405
1406         return memcmp(entry1->name, entry2->name, name_len1);
1407 }
1408
1409 /* Validate and sort by name a list of extended attributes */
1410 static int
1411 parse_xattrs(const void *xattrs, u32 len,
1412              const struct wimlib_xattr_entry *entries[],
1413              u32 *num_entries_p)
1414 {
1415         u32 limit = *num_entries_p;
1416         u32 num_entries = 0;
1417         const struct wimlib_xattr_entry *entry = xattrs;
1418
1419         while ((void *)entry < xattrs + len) {
1420                 if (!valid_xattr_entry(entry, xattrs + len - (void *)entry)) {
1421                         ERROR("Invalid xattr entry");
1422                         return WIMLIB_ERR_INVALID_XATTR;
1423                 }
1424                 if (num_entries >= limit) {
1425                         ERROR("Too many xattr entries");
1426                         return WIMLIB_ERR_INVALID_XATTR;
1427                 }
1428                 entries[num_entries++] = entry;
1429                 entry = xattr_entry_next(entry);
1430         }
1431
1432         if (num_entries == 0) {
1433                 ERROR("No xattr entries");
1434                 return WIMLIB_ERR_INVALID_XATTR;
1435         }
1436
1437         qsort(entries, num_entries, sizeof(entries[0]), cmp_xattr_names);
1438
1439         for (u32 i = 1; i < num_entries; i++) {
1440                 if (cmp_xattr_names(&entries[i - 1], &entries[i]) == 0) {
1441                         ERROR("Duplicate xattr names");
1442                         return WIMLIB_ERR_INVALID_XATTR;
1443                 }
1444         }
1445
1446         *num_entries_p = num_entries;
1447         return 0;
1448 }
1449
1450 static int
1451 cmp_linux_xattrs(const struct wim_inode *inode1,
1452                  const struct wim_inode *inode2, int cmp_flags)
1453 {
1454         const void *xattrs1, *xattrs2;
1455         u32 len1, len2;
1456
1457         xattrs1 = inode_get_linux_xattrs(inode1, &len1);
1458         xattrs2 = inode_get_linux_xattrs(inode2, &len2);
1459
1460         if (!xattrs1 && !xattrs2) {
1461                 return 0;
1462         } else if (xattrs1 && !xattrs2) {
1463                 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1464                                  WIMLIB_CMP_FLAG_WINDOWS_MODE))
1465                         return 0;
1466                 ERROR("%"TS" unexpectedly lost its xattrs",
1467                       inode_any_full_path(inode1));
1468                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1469         } else if (!xattrs1 && xattrs2) {
1470                 ERROR("%"TS" unexpectedly gained xattrs",
1471                       inode_any_full_path(inode1));
1472                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1473         } else {
1474                 const int max_entries = 64;
1475                 const struct wimlib_xattr_entry *entries1[max_entries];
1476                 const struct wimlib_xattr_entry *entries2[max_entries];
1477                 u32 xattr_count1 = max_entries;
1478                 u32 xattr_count2 = max_entries;
1479                 int ret;
1480
1481                 ret = parse_xattrs(xattrs1, len1, entries1, &xattr_count1);
1482                 if (ret) {
1483                         ERROR("%"TS": invalid xattrs",
1484                               inode_any_full_path(inode1));
1485                         return ret;
1486                 }
1487                 ret = parse_xattrs(xattrs2, len2, entries2, &xattr_count2);
1488                 if (ret) {
1489                         ERROR("%"TS": invalid xattrs",
1490                               inode_any_full_path(inode2));
1491                         return ret;
1492                 }
1493                 if (xattr_count1 != xattr_count2) {
1494                         ERROR("%"TS": number of xattrs changed.  had %u "
1495                               "before, now has %u", inode_any_full_path(inode1),
1496                               xattr_count1, xattr_count2);
1497                 }
1498                 for (u32 i = 0; i < xattr_count1; i++) {
1499                         const struct wimlib_xattr_entry *entry1 = entries1[i];
1500                         const struct wimlib_xattr_entry *entry2 = entries2[i];
1501
1502                         if (entry1->name_len != entry2->name_len ||
1503                             entry1->value_len != entry2->value_len ||
1504                             entry1->reserved != entry2->reserved ||
1505                             memcmp(entry1->name, entry2->name,
1506                                    le16_to_cpu(entry1->name_len)) ||
1507                             memcmp(entry1->name + le16_to_cpu(entry1->name_len),
1508                                    entry2->name + le16_to_cpu(entry1->name_len),
1509                                    le32_to_cpu(entry1->value_len)))
1510                         {
1511                                 ERROR("xattr %.*s of %"TS" differs",
1512                                       le16_to_cpu(entry1->name_len),
1513                                       entry1->name, inode_any_full_path(inode1));
1514                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1515                         }
1516                 }
1517                 return 0;
1518         }
1519 }
1520
1521 static int
1522 cmp_timestamps(const struct wim_inode *inode1, const struct wim_inode *inode2,
1523                int cmp_flags)
1524 {
1525         if (inode1->i_creation_time != inode2->i_creation_time &&
1526             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1527                 ERROR("Creation time of %"TS" differs",
1528                       inode_any_full_path(inode1));
1529                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1530         }
1531
1532         if (inode1->i_last_write_time != inode2->i_last_write_time) {
1533                 ERROR("Last write time of %"TS" differs",
1534                       inode_any_full_path(inode1));
1535                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1536         }
1537
1538         if (inode1->i_last_access_time != inode2->i_last_access_time) {
1539                 ERROR("Last access time of %"TS" differs",
1540                       inode_any_full_path(inode1));
1541                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1542         }
1543
1544         return 0;
1545 }
1546
1547 static int
1548 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1549            const struct wim_image_metadata *imd1,
1550            const struct wim_image_metadata *imd2, int cmp_flags)
1551 {
1552         int ret;
1553
1554         /* Compare attributes  */
1555         ret = cmp_attributes(inode1, inode2, cmp_flags);
1556         if (ret)
1557                 return ret;
1558
1559         /* Compare security descriptors  */
1560         if (inode_has_security_descriptor(inode1)) {
1561                 if (inode_has_security_descriptor(inode2)) {
1562                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1563                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1564                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1565                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1566
1567                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1568                                 ERROR("Security descriptor of %"TS" differs!",
1569                                       inode_any_full_path(inode1));
1570                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1571                         }
1572                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1573                         ERROR("%"TS" has a security descriptor in the first image but "
1574                               "not in the second image!", inode_any_full_path(inode1));
1575                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1576                 }
1577         } else if (inode_has_security_descriptor(inode2)) {
1578                 /* okay --- consider it acceptable if a default security
1579                  * descriptor was assigned  */
1580                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1581                       /*"not in the first image!", inode_any_full_path(inode1));*/
1582                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1583         }
1584
1585         /* Compare streams  */
1586         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1587                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1588                 const struct wim_inode_stream *strm2;
1589
1590                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1591                     (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1592                      !inode_is_symlink(inode1)))
1593                         continue;
1594
1595                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1596                         continue;
1597
1598                 /* Get the corresponding stream from the second file  */
1599                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1600
1601                 if (!strm2) {
1602                         /* Corresponding stream not found  */
1603                         if (stream_is_named(strm1) &&
1604                             (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1605                                 continue;
1606                         ERROR("Stream of %"TS" is missing in second image; "
1607                               "type %d, named=%d, empty=%d",
1608                               inode_any_full_path(inode1),
1609                               strm1->stream_type,
1610                               stream_is_named(strm1),
1611                               is_zero_hash(stream_hash(strm1)));
1612                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1613                 }
1614
1615                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1616                         ERROR("Stream of %"TS" differs; type %d",
1617                               inode_any_full_path(inode1), strm1->stream_type);
1618                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1619                 }
1620         }
1621
1622         /* Compare object IDs  */
1623         ret = cmp_object_ids(inode1, inode2, cmp_flags);
1624         if (ret)
1625                 return ret;
1626
1627         /* Compare timestamps  */
1628         ret = cmp_timestamps(inode1, inode2, cmp_flags);
1629         if (ret)
1630                 return ret;
1631
1632         /* Compare standard UNIX metadata  */
1633         ret = cmp_unix_metadata(inode1, inode2, cmp_flags);
1634         if (ret)
1635                 return ret;
1636
1637         /* Compare Linux-style xattrs  */
1638         ret = cmp_linux_xattrs(inode1, inode2, cmp_flags);
1639         if (ret)
1640                 return ret;
1641
1642         return 0;
1643 }
1644
1645 static int
1646 cmp_images(const struct wim_image_metadata *imd1,
1647            const struct wim_image_metadata *imd2, int cmp_flags)
1648 {
1649         struct wim_dentry *root1 = imd1->root_dentry;
1650         struct wim_dentry *root2 = imd2->root_dentry;
1651         const struct wim_inode *inode;
1652         int ret;
1653
1654         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1655         if (ret)
1656                 return ret;
1657
1658         /* Verify that the hard links match up between the two images.  */
1659         assert_inodes_sane(imd1);
1660         assert_inodes_sane(imd2);
1661         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1662         if (ret)
1663                 return ret;
1664
1665         /* Compare corresponding inodes.  */
1666         image_for_each_inode(inode, imd1) {
1667                 ret = cmp_inodes(inode, inode->i_corresponding,
1668                                  imd1, imd2, cmp_flags);
1669                 if (ret)
1670                         return ret;
1671         }
1672
1673         return 0;
1674 }
1675
1676 static int
1677 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1678 {
1679         int ret = select_wim_image(wim, image);
1680         if (!ret) {
1681                 *imd_ret = wim_get_current_image_metadata(wim);
1682                 mark_image_dirty(*imd_ret);
1683         }
1684         return ret;
1685 }
1686
1687 WIMLIBAPI int
1688 wimlib_compare_images(WIMStruct *wim1, int image1,
1689                       WIMStruct *wim2, int image2, int cmp_flags)
1690 {
1691         int ret;
1692         struct wim_image_metadata *imd1, *imd2;
1693
1694         ret = load_image(wim1, image1, &imd1);
1695         if (!ret)
1696                 ret = load_image(wim2, image2, &imd2);
1697         if (!ret)
1698                 ret = cmp_images(imd1, imd2, cmp_flags);
1699         return ret;
1700 }
1701
1702 #endif /* ENABLE_TEST_SUPPORT */