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