Cleanup timestamp conversion code
[wimlib] / src / inode.c
1 /*
2  * inode.c
3  *
4  * Functions that operate on WIM inodes.
5  *
6  * See dentry.c for a description of the relationship between WIM dentries and
7  * WIM inodes.
8  */
9
10 /*
11  * Copyright (C) 2012, 2013, 2014 Eric Biggers
12  *
13  * This file is free software; you can redistribute it and/or modify it under
14  * the terms of the GNU Lesser General Public License as published by the Free
15  * Software Foundation; either version 3 of the License, or (at your option) any
16  * later version.
17  *
18  * This file is distributed in the hope that it will be useful, but WITHOUT
19  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
21  * details.
22  *
23  * You should have received a copy of the GNU Lesser General Public License
24  * along with this file; if not, see http://www.gnu.org/licenses/.
25  */
26
27 #ifdef HAVE_CONFIG_H
28 #  include "config.h"
29 #endif
30
31 #include "wimlib/assert.h"
32 #include "wimlib/dentry.h" /* Only for dentry_full_path().  Otherwise the code
33                               in this file doesn't care about file names/paths.
34                             */
35 #include "wimlib/encoding.h"
36 #include "wimlib/endianness.h"
37 #include "wimlib/error.h"
38 #include "wimlib/inode.h"
39 #include "wimlib/inode_table.h"
40 #include "wimlib/lookup_table.h"
41 #include "wimlib/security.h"
42 #include "wimlib/timestamp.h"
43
44 #include <errno.h>
45
46 /* Allocate a new inode.  Set the timestamps to the current time.  */
47 struct wim_inode *
48 new_inode(void)
49 {
50         struct wim_inode *inode = new_timeless_inode();
51         if (inode) {
52                 u64 now = now_as_wim_timestamp();
53                 inode->i_creation_time = now;
54                 inode->i_last_access_time = now;
55                 inode->i_last_write_time = now;
56         }
57         return inode;
58 }
59
60 /* Allocate a new inode.  Leave the timestamps zeroed out.  */
61 struct wim_inode *
62 new_timeless_inode(void)
63 {
64         struct wim_inode *inode = CALLOC(1, sizeof(struct wim_inode));
65         if (inode) {
66                 inode->i_security_id = -1;
67                 inode->i_nlink = 1;
68                 inode->i_next_stream_id = 1;
69                 inode->i_not_rpfixed = 1;
70                 inode->i_canonical_streams = 1;
71                 INIT_LIST_HEAD(&inode->i_list);
72                 INIT_LIST_HEAD(&inode->i_dentry);
73         }
74         return inode;
75 }
76
77 /* Decrement link count on an inode.  */
78 void
79 put_inode(struct wim_inode *inode)
80 {
81         wimlib_assert(inode->i_nlink != 0);
82         if (--inode->i_nlink == 0) {
83                 /* If FUSE mounts are enabled, we must keep a unlinked inode
84                  * around until all file descriptors to it have been closed.  */
85         #ifdef WITH_FUSE
86                 if (inode->i_num_opened_fds == 0)
87         #endif
88                         free_inode(inode);
89         }
90 }
91
92 /* Free memory allocated within an alternate data stream entry.  */
93 static void
94 destroy_ads_entry(struct wim_ads_entry *ads_entry)
95 {
96         FREE(ads_entry->stream_name);
97 }
98
99 /* Free an inode.  Only use this if there can't be other links to the inode or
100  * if it doesn't matter if there are.  */
101 void
102 free_inode(struct wim_inode *inode)
103 {
104         if (unlikely(!inode))
105                 return;
106
107         if (unlikely(inode->i_ads_entries)) {
108                 for (u16 i = 0; i < inode->i_num_ads; i++)
109                         destroy_ads_entry(&inode->i_ads_entries[i]);
110                 FREE(inode->i_ads_entries);
111         }
112         if (unlikely(inode->i_extra))
113                 FREE(inode->i_extra);
114         /* HACK: This may instead delete the inode from i_list, but hlist_del()
115          * behaves the same as list_del(). */
116         if (!hlist_unhashed(&inode->i_hlist))
117                 hlist_del(&inode->i_hlist);
118         FREE(inode);
119 }
120
121 /* Return %true iff the alternate data stream entry @entry has the UTF-16LE
122  * stream name @name that has length @name_nbytes bytes.  */
123 static inline bool
124 ads_entry_has_name(const struct wim_ads_entry *entry,
125                    const utf16lechar *name, size_t name_nbytes,
126                    bool ignore_case)
127 {
128         return 0 == cmp_utf16le_strings(name,
129                                         name_nbytes / 2,
130                                         entry->stream_name,
131                                         entry->stream_name_nbytes / 2,
132                                         ignore_case);
133 }
134
135 /*
136  * Returns the alternate data stream entry belonging to @inode that has the
137  * stream name @stream_name, or NULL if the inode has no alternate data stream
138  * with that name.
139  *
140  * If @p stream_name is the empty string, NULL is returned --- that is, this
141  * function will not return "unnamed" alternate data stream entries.
142  *
143  * If NULL is returned, errno is set.
144  */
145 struct wim_ads_entry *
146 inode_get_ads_entry(struct wim_inode *inode, const tchar *stream_name)
147 {
148         int ret;
149         const utf16lechar *stream_name_utf16le;
150         size_t stream_name_utf16le_nbytes;
151         u16 i;
152         struct wim_ads_entry *result;
153
154         if (inode->i_num_ads == 0) {
155                 errno = ENOENT;
156                 return NULL;
157         }
158
159         if (stream_name[0] == T('\0')) {
160                 errno = ENOENT;
161                 return NULL;
162         }
163
164         ret = tstr_get_utf16le_and_len(stream_name, &stream_name_utf16le,
165                                        &stream_name_utf16le_nbytes);
166         if (ret)
167                 return NULL;
168
169         i = 0;
170         result = NULL;
171         do {
172                 if (ads_entry_has_name(&inode->i_ads_entries[i],
173                                        stream_name_utf16le,
174                                        stream_name_utf16le_nbytes,
175                                        default_ignore_case))
176                 {
177                         result = &inode->i_ads_entries[i];
178                         break;
179                 }
180         } while (++i != inode->i_num_ads);
181
182         tstr_put_utf16le(stream_name_utf16le);
183
184         if (!result)
185                 errno = ENOENT;
186         return result;
187 }
188
189 static struct wim_ads_entry *
190 do_inode_add_ads(struct wim_inode *inode,
191                  utf16lechar *stream_name, size_t stream_name_nbytes)
192 {
193         u16 num_ads;
194         struct wim_ads_entry *ads_entries;
195         struct wim_ads_entry *new_entry;
196
197         if (inode->i_num_ads >= 0xfffe) {
198                 ERROR("File \"%"TS"\" has too many alternate data streams!",
199                       inode_first_full_path(inode));
200                 errno = EFBIG;
201                 return NULL;
202         }
203         num_ads = inode->i_num_ads + 1;
204         ads_entries = REALLOC(inode->i_ads_entries,
205                               num_ads * sizeof(inode->i_ads_entries[0]));
206         if (!ads_entries)
207                 return NULL;
208
209         inode->i_ads_entries = ads_entries;
210
211         new_entry = &inode->i_ads_entries[num_ads - 1];
212
213         memset(new_entry, 0, sizeof(struct wim_ads_entry));
214         new_entry->stream_name = stream_name;
215         new_entry->stream_name_nbytes = stream_name_nbytes;
216         new_entry->stream_id = inode->i_next_stream_id++;
217         inode->i_num_ads = num_ads;
218         return new_entry;
219 }
220
221 /*
222  * Add an alternate data stream entry to a WIM inode (UTF-16LE version).  On
223  * success, returns a pointer to the new entry.  Note that this pointer might
224  * become invalid if another ADS entry is added to the inode.  On failure,
225  * returns NULL and sets errno.
226  */
227 struct wim_ads_entry *
228 inode_add_ads_utf16le(struct wim_inode *inode,
229                       const utf16lechar *stream_name, size_t stream_name_nbytes)
230 {
231         utf16lechar *dup = NULL;
232         struct wim_ads_entry *result;
233
234         if (stream_name_nbytes) {
235                 dup = utf16le_dupz(stream_name, stream_name_nbytes);
236                 if (!dup)
237                         return NULL;
238         }
239
240         result = do_inode_add_ads(inode, dup, stream_name_nbytes);
241         if (!result)
242                 FREE(dup);
243         return result;
244 }
245
246 /*
247  * Add an alternate data stream entry to a WIM inode (tchar version).  On
248  * success, returns a pointer to the new entry.  Note that this pointer might
249  * become invalid if another ADS entry is added to the inode.  On failure,
250  * returns NULL and sets errno.
251  */
252 struct wim_ads_entry *
253 inode_add_ads(struct wim_inode *inode, const tchar *stream_name)
254 {
255         utf16lechar *stream_name_utf16le = NULL;
256         size_t stream_name_utf16le_nbytes = 0;
257         struct wim_ads_entry *result;
258
259         if (stream_name && *stream_name)
260                 if (tstr_to_utf16le(stream_name,
261                                     tstrlen(stream_name) * sizeof(tchar),
262                                     &stream_name_utf16le,
263                                     &stream_name_utf16le_nbytes))
264                         return NULL;
265
266         result = do_inode_add_ads(inode, stream_name_utf16le,
267                                   stream_name_utf16le_nbytes);
268         if (!result)
269                 FREE(stream_name_utf16le);
270         return result;
271 }
272
273 /*
274  * Add an data alternate stream entry to a WIM inode, where the contents of the
275  * new stream are specified in a data buffer.  The inode must be resolved.
276  *
277  * On success, returns a pointer to the new alternate data stream entry.  Note
278  * that this pointer might become invalid if another ADS entry is added to the
279  * inode.  On failure, returns NULL and sets errno.
280  */
281 struct wim_ads_entry *
282 inode_add_ads_with_data(struct wim_inode *inode, const tchar *name,
283                         const void *value, size_t size,
284                         struct wim_lookup_table *lookup_table)
285 {
286         struct wim_ads_entry *new_entry;
287
288         wimlib_assert(inode->i_resolved);
289
290         new_entry = inode_add_ads(inode, name);
291         if (!new_entry)
292                 return NULL;
293
294         new_entry->lte = new_stream_from_data_buffer(value, size, lookup_table);
295         if (!new_entry->lte) {
296                 inode_remove_ads(inode, new_entry, NULL);
297                 return NULL;
298         }
299         return new_entry;
300 }
301
302 /*
303  * Does the inode have any named data streams?
304  */
305 bool
306 inode_has_named_stream(const struct wim_inode *inode)
307 {
308         for (u16 i = 0; i < inode->i_num_ads; i++)
309                 if (ads_entry_is_named_stream(&inode->i_ads_entries[i]))
310                         return true;
311         return false;
312 }
313
314 /* Set the unnamed stream of a WIM inode, given a data buffer containing the
315  * stream contents.  The inode must be resolved and cannot have an unnamed
316  * stream specified already.  */
317 int
318 inode_set_unnamed_stream(struct wim_inode *inode, const void *data, size_t len,
319                          struct wim_lookup_table *lookup_table)
320 {
321         wimlib_assert(inode->i_resolved);
322         wimlib_assert(!inode->i_lte);
323         inode->i_lte = new_stream_from_data_buffer(data, len, lookup_table);
324         if (!inode->i_lte)
325                 return WIMLIB_ERR_NOMEM;
326         return 0;
327 }
328
329 /* Remove an alternate data stream from a WIM inode.  */
330 void
331 inode_remove_ads(struct wim_inode *inode, struct wim_ads_entry *entry,
332                  struct wim_lookup_table *lookup_table)
333 {
334         struct wim_lookup_table_entry *lte;
335         unsigned idx = entry - inode->i_ads_entries;
336
337         wimlib_assert(idx < inode->i_num_ads);
338         wimlib_assert(inode->i_resolved);
339
340         lte = entry->lte;
341         if (lte)
342                 lte_decrement_refcnt(lte, lookup_table);
343
344         destroy_ads_entry(entry);
345
346         memmove(&inode->i_ads_entries[idx],
347                 &inode->i_ads_entries[idx + 1],
348                 (inode->i_num_ads - idx - 1) * sizeof(inode->i_ads_entries[0]));
349         inode->i_num_ads--;
350 }
351
352 /*
353  * Resolve an inode's single-instance streams.
354  *
355  * This takes each SHA-1 message digest stored in the inode or one of its ADS
356  * entries and replaces it with a pointer directly to the appropriate 'struct
357  * wim_lookup_table_entry' currently inserted into @table to represent the
358  * single-instance stream having that SHA-1 message digest.
359  *
360  * If @force is %false:
361  *      If any of the needed single-instance streams do not exist in @table,
362  *      return WIMLIB_ERR_RESOURCE_NOT_FOUND and leave the inode unmodified.
363  * If @force is %true:
364  *      If any of the needed single-instance streams do not exist in @table,
365  *      allocate new entries for them and insert them into @table.  This does
366  *      not, of course, cause these streams to magically exist, but this is
367  *      needed by the code for extraction from a pipe.
368  *
369  * If the inode is already resolved, this function does nothing.
370  *
371  * Returns 0 on success; WIMLIB_ERR_NOMEM if out of memory; or
372  * WIMLIB_ERR_RESOURCE_NOT_FOUND if @force is %false and at least one
373  * single-instance stream referenced by the inode was missing.
374  */
375 int
376 inode_resolve_streams(struct wim_inode *inode, struct wim_lookup_table *table,
377                       bool force)
378 {
379         const u8 *hash;
380         struct wim_lookup_table_entry *lte, *ads_lte;
381
382         if (inode->i_resolved)
383                 return 0;
384
385         struct wim_lookup_table_entry *ads_ltes[inode->i_num_ads];
386
387         /* Resolve the default data stream */
388         lte = NULL;
389         hash = inode->i_hash;
390         if (!is_zero_hash(hash)) {
391                 lte = lookup_stream(table, hash);
392                 if (!lte) {
393                         if (force) {
394                                 lte = new_lookup_table_entry();
395                                 if (!lte)
396                                         return WIMLIB_ERR_NOMEM;
397                                 copy_hash(lte->hash, hash);
398                                 lookup_table_insert(table, lte);
399                         } else {
400                                 goto stream_not_found;
401                         }
402                 }
403         }
404
405         /* Resolve the alternate data streams */
406         for (u16 i = 0; i < inode->i_num_ads; i++) {
407                 struct wim_ads_entry *cur_entry;
408
409                 ads_lte = NULL;
410                 cur_entry = &inode->i_ads_entries[i];
411                 hash = cur_entry->hash;
412                 if (!is_zero_hash(hash)) {
413                         ads_lte = lookup_stream(table, hash);
414                         if (!ads_lte) {
415                                 if (force) {
416                                         ads_lte = new_lookup_table_entry();
417                                         if (!ads_lte)
418                                                 return WIMLIB_ERR_NOMEM;
419                                         copy_hash(ads_lte->hash, hash);
420                                         lookup_table_insert(table, ads_lte);
421                                 } else {
422                                         goto stream_not_found;
423                                 }
424                         }
425                 }
426                 ads_ltes[i] = ads_lte;
427         }
428         inode->i_lte = lte;
429         for (u16 i = 0; i < inode->i_num_ads; i++)
430                 inode->i_ads_entries[i].lte = ads_ltes[i];
431         inode->i_resolved = 1;
432         return 0;
433
434 stream_not_found:
435         return stream_not_found_error(inode, hash);
436 }
437
438 /*
439  * Undo the effects of inode_resolve_streams().
440  *
441  * If the inode is not resolved, this function does nothing.
442  */
443 void
444 inode_unresolve_streams(struct wim_inode *inode)
445 {
446         if (!inode->i_resolved)
447                 return;
448
449         if (inode->i_lte)
450                 copy_hash(inode->i_hash, inode->i_lte->hash);
451         else
452                 zero_out_hash(inode->i_hash);
453
454         for (u16 i = 0; i < inode->i_num_ads; i++) {
455                 if (inode->i_ads_entries[i].lte)
456                         copy_hash(inode->i_ads_entries[i].hash,
457                                   inode->i_ads_entries[i].lte->hash);
458                 else
459                         zero_out_hash(inode->i_ads_entries[i].hash);
460         }
461         inode->i_resolved = 0;
462 }
463
464 int
465 stream_not_found_error(const struct wim_inode *inode, const u8 *hash)
466 {
467         if (wimlib_print_errors) {
468                 tchar hashstr[SHA1_HASH_SIZE * 2 + 1];
469
470                 sprint_hash(hash, hashstr);
471
472                 ERROR("\"%"TS"\": stream not found\n"
473                       "        SHA-1 message digest of missing stream:\n"
474                       "        %"TS"",
475                       inode_first_full_path(inode), hashstr);
476         }
477         return WIMLIB_ERR_RESOURCE_NOT_FOUND;
478 }
479
480 /*
481  * Return the lookup table entry for stream @stream_idx of the inode, where
482  * stream_idx = 0 means the default un-named file stream, and stream_idx >= 1
483  * corresponds to an alternate data stream.
484  *
485  * This works for both resolved and un-resolved inodes.
486  */
487 struct wim_lookup_table_entry *
488 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
489                  const struct wim_lookup_table *table)
490 {
491         if (inode->i_resolved)
492                 return inode_stream_lte_resolved(inode, stream_idx);
493         else
494                 return inode_stream_lte_unresolved(inode, stream_idx, table);
495 }
496
497 /*
498  * Return the lookup table entry for the unnamed data stream of a *resolved*
499  * inode, or NULL if there is none.  Also return the 0-based index of the
500  * corresponding stream in *stream_idx_ret.
501  */
502 struct wim_lookup_table_entry *
503 inode_unnamed_stream_resolved(const struct wim_inode *inode, u16 *stream_idx_ret)
504 {
505         wimlib_assert(inode->i_resolved);
506         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
507                 if (inode_stream_name_nbytes(inode, i) == 0 &&
508                     !is_zero_hash(inode_stream_hash_resolved(inode, i)))
509                 {
510                         *stream_idx_ret = i;
511                         return inode_stream_lte_resolved(inode, i);
512                 }
513         }
514         *stream_idx_ret = 0;
515         return NULL;
516 }
517
518 /*
519  * Return the lookup table entry for the unnamed data stream of a *resolved*
520  * inode, or NULL if there is none.
521  */
522 struct wim_lookup_table_entry *
523 inode_unnamed_lte_resolved(const struct wim_inode *inode)
524 {
525         u16 stream_idx;
526         return inode_unnamed_stream_resolved(inode, &stream_idx);
527 }
528
529 /*
530  * Return the lookup table entry for the unnamed data stream of an *unresolved*
531  * inode, or NULL if there is none.
532  */
533 struct wim_lookup_table_entry *
534 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
535                              const struct wim_lookup_table *table)
536 {
537         wimlib_assert(!inode->i_resolved);
538         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
539                 if (inode_stream_name_nbytes(inode, i) == 0 &&
540                     !is_zero_hash(inode_stream_hash_unresolved(inode, i)))
541                 {
542                         return inode_stream_lte_unresolved(inode, i, table);
543                 }
544         }
545         return NULL;
546 }
547
548 /*
549  * Return the lookup table entry for the unnamed data stream of an inode, or
550  * NULL if there is none.
551  *
552  * You'd think this would be easier than it actually is, since the unnamed data
553  * stream should be the one referenced from the inode itself.  Alas, if there
554  * are named data streams, Microsoft's "imagex.exe" program will put the unnamed
555  * data stream in one of the alternate data streams instead of inside the WIM
556  * dentry itself.  So we need to check the alternate data streams too.
557  *
558  * Also, note that a dentry may appear to have more than one unnamed stream, but
559  * if the SHA-1 message digest is all 0's then the corresponding stream does not
560  * really "count" (this is the case for the inode's own file stream when the
561  * file stream that should be there is actually in one of the alternate stream
562  * entries.).  This is despite the fact that we may need to extract such a
563  * missing entry as an empty file or empty named data stream.
564  */
565 struct wim_lookup_table_entry *
566 inode_unnamed_lte(const struct wim_inode *inode,
567                   const struct wim_lookup_table *table)
568 {
569         if (inode->i_resolved)
570                 return inode_unnamed_lte_resolved(inode);
571         else
572                 return inode_unnamed_lte_unresolved(inode, table);
573 }
574
575 /*
576  * Return the SHA-1 message digest of the unnamed data stream of a WIM inode.
577  *
578  * If inode does not have an unnamed data stream, this returns a void SHA-1
579  * message digest containing all zero bytes.
580  */
581 const u8 *
582 inode_unnamed_stream_hash(const struct wim_inode *inode)
583 {
584         const u8 *hash;
585
586         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
587                 if (inode_stream_name_nbytes(inode, i) == 0) {
588                         hash = inode_stream_hash(inode, i);
589                         if (!is_zero_hash(hash))
590                                 return hash;
591                 }
592         }
593         return zero_hash;
594 }
595
596 /*
597  * Translate a single-instance stream entry into the pointer contained in the
598  * inode (or ads entry of an inode) that references it.
599  *
600  * This is only possible for "unhashed" streams, which are guaranteed to have
601  * only one reference, and that reference is guaranteed to be in a resolved
602  * inode.  (It can't be in an unresolved inode, since that would imply the hash
603  * is known!)
604  */
605 struct wim_lookup_table_entry **
606 retrieve_lte_pointer(struct wim_lookup_table_entry *lte)
607 {
608         wimlib_assert(lte->unhashed);
609         struct wim_inode *inode = lte->back_inode;
610         u32 stream_id = lte->back_stream_id;
611         if (stream_id == 0)
612                 return &inode->i_lte;
613         else
614                 for (u16 i = 0; i < inode->i_num_ads; i++)
615                         if (inode->i_ads_entries[i].stream_id == stream_id)
616                                 return &inode->i_ads_entries[i].lte;
617         wimlib_assert(0);
618         return NULL;
619 }
620
621 /*
622  * Read the alternate data stream entries of a WIM dentry.
623  *
624  * @p:
625  *      Pointer to buffer that starts with the first alternate stream entry.
626  *
627  * @inode:
628  *      Inode to load the alternate data streams into.  @inode->i_num_ads must
629  *      have been set to the number of alternate data streams that are expected.
630  *
631  * @nbytes_remaining_p:
632  *      Number of bytes of data remaining in the buffer pointed to by @p.
633  *      On success this will be updated to point just past the ADS entries.
634  *
635  * On success, inode->i_ads_entries is set to an array of `struct
636  * wim_ads_entry's of length inode->i_num_ads.  On failure, @inode is not
637  * modified.
638  *
639  * Return values:
640  *      WIMLIB_ERR_SUCCESS (0)
641  *      WIMLIB_ERR_INVALID_METADATA_RESOURCE
642  *      WIMLIB_ERR_NOMEM
643  */
644 int
645 read_ads_entries(const u8 * restrict p, struct wim_inode * restrict inode,
646                  size_t *nbytes_remaining_p)
647 {
648         size_t nbytes_remaining = *nbytes_remaining_p;
649         u16 num_ads;
650         struct wim_ads_entry *ads_entries;
651         int ret;
652
653         BUILD_BUG_ON(sizeof(struct wim_ads_entry_on_disk) != WIM_ADS_ENTRY_DISK_SIZE);
654
655         /* Allocate an array for our in-memory representation of the alternate
656          * data stream entries. */
657         num_ads = inode->i_num_ads;
658         ads_entries = CALLOC(num_ads, sizeof(inode->i_ads_entries[0]));
659         if (!ads_entries)
660                 goto out_of_memory;
661
662         /* Read the entries into our newly allocated buffer. */
663         for (u16 i = 0; i < num_ads; i++) {
664                 u64 length;
665                 struct wim_ads_entry *cur_entry;
666                 const struct wim_ads_entry_on_disk *disk_entry =
667                         (const struct wim_ads_entry_on_disk*)p;
668
669                 cur_entry = &ads_entries[i];
670                 ads_entries[i].stream_id = i + 1;
671
672                 /* Do we have at least the size of the fixed-length data we know
673                  * need? */
674                 if (nbytes_remaining < sizeof(struct wim_ads_entry_on_disk))
675                         goto out_invalid;
676
677                 /* Read the length field */
678                 length = le64_to_cpu(disk_entry->length);
679
680                 /* Make sure the length field is neither so small it doesn't
681                  * include all the fixed-length data nor so large it overflows
682                  * the metadata resource buffer. */
683                 if (length < sizeof(struct wim_ads_entry_on_disk) ||
684                     length > nbytes_remaining)
685                         goto out_invalid;
686
687                 /* Read the rest of the fixed-length data. */
688
689                 cur_entry->reserved = le64_to_cpu(disk_entry->reserved);
690                 copy_hash(cur_entry->hash, disk_entry->hash);
691                 cur_entry->stream_name_nbytes = le16_to_cpu(disk_entry->stream_name_nbytes);
692
693                 /* If stream_name_nbytes != 0, this is a named stream.
694                  * Otherwise this is an unnamed stream, or in some cases (bugs
695                  * in Microsoft's software I guess) a meaningless entry
696                  * distinguished from the real unnamed stream entry, if any, by
697                  * the fact that the real unnamed stream entry has a nonzero
698                  * hash field. */
699                 if (cur_entry->stream_name_nbytes) {
700                         /* The name is encoded in UTF16-LE, which uses 2-byte
701                          * coding units, so the length of the name had better be
702                          * an even number of bytes... */
703                         if (cur_entry->stream_name_nbytes & 1)
704                                 goto out_invalid;
705
706                         /* Add the length of the stream name to get the length
707                          * we actually need to read.  Make sure this isn't more
708                          * than the specified length of the entry. */
709                         if (sizeof(struct wim_ads_entry_on_disk) +
710                             cur_entry->stream_name_nbytes > length)
711                                 goto out_invalid;
712
713                         cur_entry->stream_name = utf16le_dupz(disk_entry->stream_name,
714                                                               cur_entry->stream_name_nbytes);
715                         if (!cur_entry->stream_name)
716                                 goto out_of_memory;
717                 } else {
718                         /* Mark inode as having weird stream entries.  */
719                         inode->i_canonical_streams = 0;
720                 }
721
722                 /* It's expected that the size of every ADS entry is a multiple
723                  * of 8.  However, to be safe, I'm allowing the possibility of
724                  * an ADS entry at the very end of the metadata resource ending
725                  * un-aligned.  So although we still need to increment the input
726                  * pointer by @length to reach the next ADS entry, it's possible
727                  * that less than @length is actually remaining in the metadata
728                  * resource. We should set the remaining bytes to 0 if this
729                  * happens. */
730                 length = (length + 7) & ~7;
731                 p += length;
732                 if (nbytes_remaining < length)
733                         nbytes_remaining = 0;
734                 else
735                         nbytes_remaining -= length;
736         }
737         inode->i_ads_entries = ads_entries;
738         inode->i_next_stream_id = inode->i_num_ads + 1;
739         *nbytes_remaining_p = nbytes_remaining;
740         ret = 0;
741         goto out;
742 out_of_memory:
743         ret = WIMLIB_ERR_NOMEM;
744         goto out_free_ads_entries;
745 out_invalid:
746         ERROR("An alternate data stream entry is invalid");
747         ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
748 out_free_ads_entries:
749         if (ads_entries) {
750                 for (u16 i = 0; i < num_ads; i++)
751                         destroy_ads_entry(&ads_entries[i]);
752                 FREE(ads_entries);
753         }
754 out:
755         return ret;
756 }
757
758 /* Check a WIM inode for unusual field values.  */
759 void
760 check_inode(struct wim_inode *inode, const struct wim_security_data *sd)
761 {
762         /* Check the security ID.  -1 is valid and means "no security
763          * descriptor".  Anything else has to be a valid index into the WIM
764          * image's security descriptors table. */
765         if (inode->i_security_id < -1 ||
766             (inode->i_security_id >= 0 &&
767              inode->i_security_id >= sd->num_entries))
768         {
769                 WARNING("\"%"TS"\" has an invalid security ID (%d)",
770                         inode_first_full_path(inode), inode->i_security_id);
771                 inode->i_security_id = -1;
772         }
773
774         /* Make sure there is only one unnamed data stream. */
775         unsigned num_unnamed_streams = 0;
776         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
777                 const u8 *hash;
778                 hash = inode_stream_hash(inode, i);
779                 if (inode_stream_name_nbytes(inode, i) == 0 && !is_zero_hash(hash))
780                         num_unnamed_streams++;
781         }
782         if (num_unnamed_streams > 1) {
783                 WARNING("\"%"TS"\" has multiple (%u) un-named streams",
784                         inode_first_full_path(inode), num_unnamed_streams);
785                 /* We currently don't treat this as an error and will just end
786                  * up using the first unnamed data stream in the inode.  */
787         }
788 }
789
790 /* Acquire another reference to each single-instance stream referenced by this
791  * inode.  This is necessary when creating a hard link to this inode.
792  *
793  * The inode must be resolved.  */
794 void
795 inode_ref_streams(struct wim_inode *inode)
796 {
797         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
798                 struct wim_lookup_table_entry *lte;
799
800                 lte = inode_stream_lte_resolved(inode, i);
801                 if (lte)
802                         lte->refcnt++;
803         }
804 }
805
806 /* Drop a reference to each single-instance stream referenced by this inode.
807  * This is necessary when deleting a hard link to this inode.  */
808 void
809 inode_unref_streams(struct wim_inode *inode,
810                     struct wim_lookup_table *lookup_table)
811 {
812         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
813                 struct wim_lookup_table_entry *lte;
814
815                 lte = inode_stream_lte(inode, i, lookup_table);
816                 if (lte)
817                         lte_decrement_refcnt(lte, lookup_table);
818         }
819 }
820
821 /* Initialize a hash table for hard link detection.  */
822 int
823 init_inode_table(struct wim_inode_table *table, size_t capacity)
824 {
825         table->array = CALLOC(capacity, sizeof(table->array[0]));
826         if (!table->array)
827                 return WIMLIB_ERR_NOMEM;
828         table->num_entries  = 0;
829         table->capacity  = capacity;
830         INIT_LIST_HEAD(&table->extra_inodes);
831         return 0;
832 }
833
834 /* Free the memory allocated by init_inode_table().  */
835 void
836 destroy_inode_table(struct wim_inode_table *table)
837 {
838         FREE(table->array);
839 }
840
841 static struct wim_inode *
842 inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno)
843 {
844         u64 hash = hash_u64(hash_u64(ino) + hash_u64(devno));
845         size_t pos = hash % table->capacity;
846         struct wim_inode *inode;
847         struct hlist_node *cur;
848
849         /* Search for an existing inode having the same inode number and device
850          * number.  */
851         hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
852                 if (inode->i_ino == ino && inode->i_devno == devno) {
853                         /* Found; use the existing inode.  */
854                         inode->i_nlink++;
855                         return inode;
856                 }
857         }
858
859         /* Create a new inode and insert it into the table.  */
860         inode = new_timeless_inode();
861         if (inode) {
862                 inode->i_ino = ino;
863                 inode->i_devno = devno;
864                 hlist_add_head(&inode->i_hlist, &table->array[pos]);
865                 table->num_entries++;
866         }
867         return inode;
868 }
869
870 /*
871  * Allocate a new dentry, with hard link detection.
872  *
873  * @table
874  *      The inode table being used for the current directory scan operation.  It
875  *      will contain the mapping from (ino, devno) pairs to inodes.
876  *
877  * @name
878  *      The name to give the new dentry.
879  *
880  * @ino
881  *      The inode number of the file, read from the filesystem.
882  *
883  * @devno
884  *      The device number of the file, read from the filesystem.  Proper setting
885  *      of this parameter prevents cross-device hardlinks from being created.
886  *      If this is not a problem (perhaps because the current directory scan
887  *      operation is guaranteed to never traverse a filesystem boundary), then
888  *      this parameter can just be a fixed value such as 0.
889  *
890  * @noshare
891  *      If %true, the new dentry will not be hard linked to any existing inode,
892  *      regardless of the values of @ino and @devno.  If %false, normal hard
893  *      link detection will be done.
894  *
895  * @dentry_ret
896  *      On success, a pointer to the new dentry will be returned in this
897  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
898  *      function created a hard link to an existing inode rather than creating a
899  *      new inode.
900  *
901  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
902  * resulting from a failed string conversion.
903  */
904 int
905 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
906                        u64 ino, u64 devno, bool noshare,
907                        struct wim_dentry **dentry_ret)
908 {
909         struct wim_dentry *dentry;
910         struct wim_inode *inode;
911         int ret;
912
913         if (noshare) {
914                 /* File that cannot be hardlinked--- Return a new inode with its
915                  * inode and device numbers left at 0. */
916                 ret = new_dentry_with_timeless_inode(name, &dentry);
917                 if (ret)
918                         return ret;
919                 list_add_tail(&dentry->d_inode->i_list, &table->extra_inodes);
920         } else {
921                 /* File that can be hardlinked--- search the table for an
922                  * existing inode matching the inode number and device;
923                  * otherwise create a new inode. */
924                 ret = new_dentry(name, &dentry);
925                 if (ret)
926                         return ret;
927                 inode = inode_table_get_inode(table, ino, devno);
928                 if (!inode) {
929                         free_dentry(dentry);
930                         return WIMLIB_ERR_NOMEM;
931                 }
932                 /* If using an existing inode, we need to gain a reference to
933                  * each of its streams. */
934                 if (inode->i_nlink > 1)
935                         inode_ref_streams(inode);
936                 dentry->d_inode = inode;
937                 inode_add_dentry(dentry, inode);
938         }
939         *dentry_ret = dentry;
940         return 0;
941 }
942
943
944
945 /*
946  * Following the allocation of dentries with hard link detection using
947  * inode_table_new_dentry(), this function will assign consecutive inode numbers
948  * to the new set of inodes.  It will also append the list of new inodes to the
949  * list @head, which must contain any inodes already existing in the WIM image.
950  */
951 void
952 inode_table_prepare_inode_list(struct wim_inode_table *table,
953                                struct list_head *head)
954 {
955         struct wim_inode *inode, *tmp_inode;
956         struct hlist_node *cur, *tmp;
957         u64 cur_ino = 1;
958
959         /* Re-assign inode numbers in the existing list to avoid duplicates. */
960         list_for_each_entry(inode, head, i_list)
961                 inode->i_ino = cur_ino++;
962
963         /* Assign inode numbers to the new inodes and move them to the image's
964          * inode list. */
965         for (size_t i = 0; i < table->capacity; i++) {
966                 hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist)
967                 {
968                         inode->i_ino = cur_ino++;
969                         inode->i_devno = 0;
970                         list_add_tail(&inode->i_list, head);
971                 }
972                 INIT_HLIST_HEAD(&table->array[i]);
973         }
974         list_for_each_entry_safe(inode, tmp_inode, &table->extra_inodes, i_list)
975         {
976                 inode->i_ino = cur_ino++;
977                 inode->i_devno = 0;
978                 list_add_tail(&inode->i_list, head);
979         }
980         INIT_LIST_HEAD(&table->extra_inodes);
981         table->num_entries = 0;
982 }