f6e14e97d6a9c0f0e0fae63c2753eecdd8a75cd6
[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         /* HACK: This may instead delete the inode from i_list, but hlist_del()
112          * behaves the same as list_del(). */
113         if (!hlist_unhashed(&inode->i_hlist))
114                 hlist_del(&inode->i_hlist);
115         FREE(inode);
116 }
117
118 /* Return %true iff the alternate data stream entry @entry has the UTF-16LE
119  * stream name @name that has length @name_nbytes bytes.  */
120 static inline bool
121 ads_entry_has_name(const struct wim_ads_entry *entry,
122                    const utf16lechar *name, size_t name_nbytes,
123                    bool ignore_case)
124 {
125         return 0 == cmp_utf16le_strings(name,
126                                         name_nbytes / 2,
127                                         entry->stream_name,
128                                         entry->stream_name_nbytes / 2,
129                                         ignore_case);
130 }
131
132 /*
133  * Returns the alternate data stream entry belonging to @inode that has the
134  * stream name @stream_name, or NULL if the inode has no alternate data stream
135  * with that name.
136  *
137  * If @p stream_name is the empty string, NULL is returned --- that is, this
138  * function will not return "unnamed" alternate data stream entries.
139  */
140 struct wim_ads_entry *
141 inode_get_ads_entry(struct wim_inode *inode, const tchar *stream_name,
142                     u16 *idx_ret)
143 {
144         size_t stream_name_utf16le_nbytes;
145         u16 i;
146         struct wim_ads_entry *result;
147
148         if (inode->i_num_ads == 0)
149                 return NULL;
150
151         if (stream_name[0] == T('\0'))
152                 return NULL;
153
154 #if TCHAR_IS_UTF16LE
155         const utf16lechar *stream_name_utf16le;
156
157         stream_name_utf16le = stream_name;
158         stream_name_utf16le_nbytes = tstrlen(stream_name) * sizeof(tchar);
159 #else
160         utf16lechar *stream_name_utf16le;
161
162         {
163                 int ret = tstr_to_utf16le(stream_name,
164                                           tstrlen(stream_name) *
165                                               sizeof(tchar),
166                                           &stream_name_utf16le,
167                                           &stream_name_utf16le_nbytes);
168                 if (ret)
169                         return NULL;
170         }
171 #endif
172         i = 0;
173         result = NULL;
174         do {
175                 if (ads_entry_has_name(&inode->i_ads_entries[i],
176                                        stream_name_utf16le,
177                                        stream_name_utf16le_nbytes,
178                                        default_ignore_case))
179                 {
180                         if (idx_ret)
181                                 *idx_ret = i;
182                         result = &inode->i_ads_entries[i];
183                         break;
184                 }
185         } while (++i != inode->i_num_ads);
186 #if !TCHAR_IS_UTF16LE
187         FREE(stream_name_utf16le);
188 #endif
189         return result;
190 }
191
192 static int
193 init_ads_entry(struct wim_ads_entry *ads_entry, const void *name,
194                size_t name_nbytes, bool is_utf16le)
195 {
196         int ret = 0;
197         memset(ads_entry, 0, sizeof(*ads_entry));
198
199         if (is_utf16le) {
200                 utf16lechar *p = MALLOC(name_nbytes + sizeof(utf16lechar));
201                 if (p == NULL)
202                         return WIMLIB_ERR_NOMEM;
203                 memcpy(p, name, name_nbytes);
204                 p[name_nbytes / 2] = cpu_to_le16(0);
205                 ads_entry->stream_name = p;
206                 ads_entry->stream_name_nbytes = name_nbytes;
207         } else {
208                 if (name && *(const tchar*)name != T('\0')) {
209                         ret = get_utf16le_string(name, &ads_entry->stream_name,
210                                                  &ads_entry->stream_name_nbytes);
211                 }
212         }
213         return ret;
214 }
215
216 static struct wim_ads_entry *
217 do_inode_add_ads(struct wim_inode *inode, const void *stream_name,
218                  size_t stream_name_nbytes, bool is_utf16le)
219 {
220         u16 num_ads;
221         struct wim_ads_entry *ads_entries;
222         struct wim_ads_entry *new_entry;
223
224         wimlib_assert(stream_name_nbytes != 0);
225
226         if (inode->i_num_ads >= 0xfffe) {
227                 ERROR("Too many alternate data streams in one inode!");
228                 return NULL;
229         }
230         num_ads = inode->i_num_ads + 1;
231         ads_entries = REALLOC(inode->i_ads_entries,
232                               num_ads * sizeof(inode->i_ads_entries[0]));
233         if (ads_entries == NULL) {
234                 ERROR("Failed to allocate memory for new alternate data stream");
235                 return NULL;
236         }
237         inode->i_ads_entries = ads_entries;
238
239         new_entry = &inode->i_ads_entries[num_ads - 1];
240         if (init_ads_entry(new_entry, stream_name, stream_name_nbytes, is_utf16le))
241                 return NULL;
242         new_entry->stream_id = inode->i_next_stream_id++;
243         inode->i_num_ads = num_ads;
244         return new_entry;
245 }
246
247 struct wim_ads_entry *
248 inode_add_ads_utf16le(struct wim_inode *inode,
249                       const utf16lechar *stream_name,
250                       size_t stream_name_nbytes)
251 {
252         DEBUG("Add alternate data stream \"%"WS"\"", stream_name);
253         return do_inode_add_ads(inode, stream_name, stream_name_nbytes, true);
254 }
255
256 /*
257  * Add an alternate stream entry to a WIM inode.  On success, returns a pointer
258  * to the new entry; on failure, returns NULL.
259  *
260  * @stream_name must be a nonempty string.
261  */
262 struct wim_ads_entry *
263 inode_add_ads(struct wim_inode *inode, const tchar *stream_name)
264 {
265         DEBUG("Add alternate data stream \"%"TS"\"", stream_name);
266         return do_inode_add_ads(inode, stream_name,
267                                 tstrlen(stream_name) * sizeof(tchar),
268                                 TCHAR_IS_UTF16LE);
269 }
270
271 int
272 inode_add_ads_with_data(struct wim_inode *inode, const tchar *name,
273                         const void *value, size_t size,
274                         struct wim_lookup_table *lookup_table)
275 {
276         struct wim_ads_entry *new_ads_entry;
277
278         wimlib_assert(inode->i_resolved);
279
280         new_ads_entry = inode_add_ads(inode, name);
281         if (new_ads_entry == NULL)
282                 return WIMLIB_ERR_NOMEM;
283
284         new_ads_entry->lte = new_stream_from_data_buffer(value, size,
285                                                          lookup_table);
286         if (new_ads_entry->lte == NULL) {
287                 inode_remove_ads(inode, new_ads_entry - inode->i_ads_entries,
288                                  lookup_table);
289                 return WIMLIB_ERR_NOMEM;
290         }
291         return 0;
292 }
293
294 bool
295 inode_has_named_stream(const struct wim_inode *inode)
296 {
297         for (u16 i = 0; i < inode->i_num_ads; i++)
298                 if (ads_entry_is_named_stream(&inode->i_ads_entries[i]))
299                         return true;
300         return false;
301 }
302
303 /* Set the unnamed stream of a WIM inode, given a data buffer containing the
304  * stream contents. */
305 int
306 inode_set_unnamed_stream(struct wim_inode *inode, const void *data, size_t len,
307                          struct wim_lookup_table *lookup_table)
308 {
309         inode->i_lte = new_stream_from_data_buffer(data, len, lookup_table);
310         if (inode->i_lte == NULL)
311                 return WIMLIB_ERR_NOMEM;
312         inode->i_resolved = 1;
313         return 0;
314 }
315
316 /* Remove an alternate data stream from a WIM inode  */
317 void
318 inode_remove_ads(struct wim_inode *inode, u16 idx,
319                  struct wim_lookup_table *lookup_table)
320 {
321         struct wim_ads_entry *ads_entry;
322         struct wim_lookup_table_entry *lte;
323
324         wimlib_assert(idx < inode->i_num_ads);
325         wimlib_assert(inode->i_resolved);
326
327         ads_entry = &inode->i_ads_entries[idx];
328
329         DEBUG("Remove alternate data stream \"%"WS"\"", ads_entry->stream_name);
330
331         lte = ads_entry->lte;
332         if (lte)
333                 lte_decrement_refcnt(lte, lookup_table);
334
335         destroy_ads_entry(ads_entry);
336
337         memmove(&inode->i_ads_entries[idx],
338                 &inode->i_ads_entries[idx + 1],
339                 (inode->i_num_ads - idx - 1) * sizeof(inode->i_ads_entries[0]));
340         inode->i_num_ads--;
341 }
342
343 bool
344 inode_has_unix_data(const struct wim_inode *inode)
345 {
346         for (u16 i = 0; i < inode->i_num_ads; i++)
347                 if (ads_entry_is_unix_data(&inode->i_ads_entries[i]))
348                         return true;
349         return false;
350 }
351
352 #ifndef __WIN32__
353 int
354 inode_get_unix_data(const struct wim_inode *inode,
355                     struct wimlib_unix_data *unix_data,
356                     u16 *stream_idx_ret)
357 {
358         const struct wim_ads_entry *ads_entry;
359         const struct wim_lookup_table_entry *lte;
360         size_t size;
361         int ret;
362
363         wimlib_assert(inode->i_resolved);
364
365         ads_entry = inode_get_ads_entry((struct wim_inode*)inode,
366                                         WIMLIB_UNIX_DATA_TAG, NULL);
367         if (ads_entry == NULL)
368                 return NO_UNIX_DATA;
369
370         if (stream_idx_ret)
371                 *stream_idx_ret = ads_entry - inode->i_ads_entries;
372
373         lte = ads_entry->lte;
374         if (lte == NULL)
375                 return NO_UNIX_DATA;
376
377         size = lte->size;
378         if (size != sizeof(struct wimlib_unix_data))
379                 return BAD_UNIX_DATA;
380
381         ret = read_full_stream_into_buf(lte, unix_data);
382         if (ret)
383                 return ret;
384
385         if (unix_data->version != 0)
386                 return BAD_UNIX_DATA;
387         return 0;
388 }
389
390 int
391 inode_set_unix_data(struct wim_inode *inode, u16 uid, u16 gid, u16 mode,
392                     struct wim_lookup_table *lookup_table, int which)
393 {
394         struct wimlib_unix_data unix_data;
395         int ret;
396         bool have_good_unix_data = false;
397         bool have_unix_data = false;
398         u16 stream_idx;
399
400         if (!(which & UNIX_DATA_CREATE)) {
401                 ret = inode_get_unix_data(inode, &unix_data, &stream_idx);
402                 if (ret == 0 || ret == BAD_UNIX_DATA || ret > 0)
403                         have_unix_data = true;
404                 if (ret == 0)
405                         have_good_unix_data = true;
406         }
407         unix_data.version = 0;
408         if (which & UNIX_DATA_UID || !have_good_unix_data)
409                 unix_data.uid = uid;
410         if (which & UNIX_DATA_GID || !have_good_unix_data)
411                 unix_data.gid = gid;
412         if (which & UNIX_DATA_MODE || !have_good_unix_data)
413                 unix_data.mode = mode;
414         ret = inode_add_ads_with_data(inode, WIMLIB_UNIX_DATA_TAG,
415                                       &unix_data,
416                                       sizeof(struct wimlib_unix_data),
417                                       lookup_table);
418         if (ret == 0 && have_unix_data)
419                 inode_remove_ads(inode, stream_idx, lookup_table);
420         return ret;
421 }
422 #endif /* __WIN32__  */
423
424 /*
425  * Resolve an inode's lookup table entries.
426  *
427  * This replaces the SHA1 hash fields (which are used to lookup an entry in the
428  * lookup table) with pointers directly to the lookup table entries.
429  *
430  * If @force is %false:
431  *      If any needed SHA1 message digests are not found in the lookup table,
432  *      WIMLIB_ERR_RESOURCE_NOT_FOUND is returned and the inode is left
433  *      unmodified.
434  * If @force is %true:
435  *      If any needed SHA1 message digests are not found in the lookup table,
436  *      new entries are allocated and inserted into the lookup table.
437  */
438 int
439 inode_resolve_streams(struct wim_inode *inode, struct wim_lookup_table *table,
440                       bool force)
441 {
442         const u8 *hash;
443
444         if (!inode->i_resolved) {
445                 struct wim_lookup_table_entry *lte, *ads_lte;
446
447                 /* Resolve the default file stream */
448                 lte = NULL;
449                 hash = inode->i_hash;
450                 if (!is_zero_hash(hash)) {
451                         lte = lookup_stream(table, hash);
452                         if (!lte) {
453                                 if (force) {
454                                         lte = new_lookup_table_entry();
455                                         if (!lte)
456                                                 return WIMLIB_ERR_NOMEM;
457                                         copy_hash(lte->hash, hash);
458                                         lookup_table_insert(table, lte);
459                                 } else {
460                                         goto stream_not_found;
461                                 }
462                         }
463                 }
464
465                 /* Resolve the alternate data streams */
466                 struct wim_lookup_table_entry *ads_ltes[inode->i_num_ads];
467                 for (u16 i = 0; i < inode->i_num_ads; i++) {
468                         struct wim_ads_entry *cur_entry;
469
470                         ads_lte = NULL;
471                         cur_entry = &inode->i_ads_entries[i];
472                         hash = cur_entry->hash;
473                         if (!is_zero_hash(hash)) {
474                                 ads_lte = lookup_stream(table, hash);
475                                 if (!ads_lte) {
476                                         if (force) {
477                                                 ads_lte = new_lookup_table_entry();
478                                                 if (!ads_lte)
479                                                         return WIMLIB_ERR_NOMEM;
480                                                 copy_hash(ads_lte->hash, hash);
481                                                 lookup_table_insert(table, ads_lte);
482                                         } else {
483                                                 goto stream_not_found;
484                                         }
485                                 }
486                         }
487                         ads_ltes[i] = ads_lte;
488                 }
489                 inode->i_lte = lte;
490                 for (u16 i = 0; i < inode->i_num_ads; i++)
491                         inode->i_ads_entries[i].lte = ads_ltes[i];
492                 inode->i_resolved = 1;
493         }
494         return 0;
495
496 stream_not_found:
497         return stream_not_found_error(inode, hash);
498 }
499
500 void
501 inode_unresolve_streams(struct wim_inode *inode)
502 {
503         if (inode->i_resolved) {
504                 if (inode->i_lte)
505                         copy_hash(inode->i_hash, inode->i_lte->hash);
506                 else
507                         zero_out_hash(inode->i_hash);
508
509                 for (u16 i = 0; i < inode->i_num_ads; i++) {
510                         if (inode->i_ads_entries[i].lte)
511                                 copy_hash(inode->i_ads_entries[i].hash,
512                                           inode->i_ads_entries[i].lte->hash);
513                         else
514                                 zero_out_hash(inode->i_ads_entries[i].hash);
515                 }
516                 inode->i_resolved = 0;
517         }
518 }
519
520 /*
521  * Returns the lookup table entry for stream @stream_idx of the inode, where
522  * stream_idx = 0 means the default un-named file stream, and stream_idx >= 1
523  * corresponds to an alternate data stream.
524  *
525  * This works for both resolved and un-resolved inodes.
526  */
527 struct wim_lookup_table_entry *
528 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
529                  const struct wim_lookup_table *table)
530 {
531         if (inode->i_resolved)
532                 return inode_stream_lte_resolved(inode, stream_idx);
533         else
534                 return inode_stream_lte_unresolved(inode, stream_idx, table);
535 }
536
537 struct wim_lookup_table_entry *
538 inode_unnamed_stream_resolved(const struct wim_inode *inode, u16 *stream_idx_ret)
539 {
540         wimlib_assert(inode->i_resolved);
541         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
542                 if (inode_stream_name_nbytes(inode, i) == 0 &&
543                     !is_zero_hash(inode_stream_hash_resolved(inode, i)))
544                 {
545                         *stream_idx_ret = i;
546                         return inode_stream_lte_resolved(inode, i);
547                 }
548         }
549         *stream_idx_ret = 0;
550         return NULL;
551 }
552
553 struct wim_lookup_table_entry *
554 inode_unnamed_lte_resolved(const struct wim_inode *inode)
555 {
556         u16 stream_idx;
557         return inode_unnamed_stream_resolved(inode, &stream_idx);
558 }
559
560 struct wim_lookup_table_entry *
561 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
562                              const struct wim_lookup_table *table)
563 {
564         wimlib_assert(!inode->i_resolved);
565         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
566                 if (inode_stream_name_nbytes(inode, i) == 0 &&
567                     !is_zero_hash(inode_stream_hash_unresolved(inode, i)))
568                 {
569                         return inode_stream_lte_unresolved(inode, i, table);
570                 }
571         }
572         return NULL;
573 }
574
575 /* Return the lookup table entry for the unnamed data stream of an inode, or
576  * NULL if there is none.
577  *
578  * You'd think this would be easier than it actually is, since the unnamed data
579  * stream should be the one referenced from the inode itself.  Alas, if there
580  * are named data streams, Microsoft's "imagex.exe" program will put the unnamed
581  * data stream in one of the alternate data streams instead of inside the WIM
582  * dentry itself.  So we need to check the alternate data streams too.
583  *
584  * Also, note that a dentry may appear to have more than one unnamed stream, but
585  * if the SHA1 message digest is all 0's then the corresponding stream does not
586  * really "count" (this is the case for the inode's own file stream when the
587  * file stream that should be there is actually in one of the alternate stream
588  * entries.).  This is despite the fact that we may need to extract such a
589  * missing entry as an empty file or empty named data stream.
590  */
591 struct wim_lookup_table_entry *
592 inode_unnamed_lte(const struct wim_inode *inode,
593                   const struct wim_lookup_table *table)
594 {
595         if (inode->i_resolved)
596                 return inode_unnamed_lte_resolved(inode);
597         else
598                 return inode_unnamed_lte_unresolved(inode, table);
599 }
600
601 /* Returns the SHA1 message digest of the unnamed data stream of a WIM inode, or
602  * 'zero_hash' if the unnamed data stream is missing has all zeroes in its SHA1
603  * message digest field.  */
604 const u8 *
605 inode_unnamed_stream_hash(const struct wim_inode *inode)
606 {
607         const u8 *hash;
608
609         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
610                 if (inode_stream_name_nbytes(inode, i) == 0) {
611                         hash = inode_stream_hash(inode, i);
612                         if (!is_zero_hash(hash))
613                                 return hash;
614                 }
615         }
616         return zero_hash;
617 }
618
619 /* Given an unhashed stream, get the pointer to it in an inode.
620  * As this is only for unhashed streams, there can only be one such pointer.  */
621 struct wim_lookup_table_entry **
622 retrieve_lte_pointer(struct wim_lookup_table_entry *lte)
623 {
624         wimlib_assert(lte->unhashed);
625         struct wim_inode *inode = lte->back_inode;
626         u32 stream_id = lte->back_stream_id;
627         if (stream_id == 0)
628                 return &inode->i_lte;
629         else
630                 for (u16 i = 0; i < inode->i_num_ads; i++)
631                         if (inode->i_ads_entries[i].stream_id == stream_id)
632                                 return &inode->i_ads_entries[i].lte;
633         wimlib_assert(0);
634         return NULL;
635 }
636
637 int
638 stream_not_found_error(const struct wim_inode *inode, const u8 *hash)
639 {
640         if (wimlib_print_errors) {
641                 ERROR("\"%"TS"\": stream not found", inode_first_full_path(inode));
642                 tfprintf(stderr, T("        SHA-1 message digest of missing stream:\n        "));
643                 print_hash(hash, stderr);
644                 tputc(T('\n'), stderr);
645         }
646         return WIMLIB_ERR_RESOURCE_NOT_FOUND;
647 }
648
649 /*
650  * Reads the alternate data stream entries of a WIM dentry.
651  *
652  * @p:
653  *      Pointer to buffer that starts with the first alternate stream entry.
654  *
655  * @inode:
656  *      Inode to load the alternate data streams into.  @inode->i_num_ads must
657  *      have been set to the number of alternate data streams that are expected.
658  *
659  * @remaining_size:
660  *      Number of bytes of data remaining in the buffer pointed to by @p.
661  *
662  * On success, inode->i_ads_entries is set to an array of `struct
663  * wim_ads_entry's of length inode->i_num_ads.  On failure, @inode is not
664  * modified.
665  *
666  * Return values:
667  *      WIMLIB_ERR_SUCCESS (0)
668  *      WIMLIB_ERR_INVALID_METADATA_RESOURCE
669  *      WIMLIB_ERR_NOMEM
670  */
671 int
672 read_ads_entries(const u8 * restrict p, struct wim_inode * restrict inode,
673                  size_t nbytes_remaining)
674 {
675         u16 num_ads;
676         struct wim_ads_entry *ads_entries;
677         int ret;
678
679         BUILD_BUG_ON(sizeof(struct wim_ads_entry_on_disk) != WIM_ADS_ENTRY_DISK_SIZE);
680
681         /* Allocate an array for our in-memory representation of the alternate
682          * data stream entries. */
683         num_ads = inode->i_num_ads;
684         ads_entries = CALLOC(num_ads, sizeof(inode->i_ads_entries[0]));
685         if (ads_entries == NULL)
686                 goto out_of_memory;
687
688         /* Read the entries into our newly allocated buffer. */
689         for (u16 i = 0; i < num_ads; i++) {
690                 u64 length;
691                 struct wim_ads_entry *cur_entry;
692                 const struct wim_ads_entry_on_disk *disk_entry =
693                         (const struct wim_ads_entry_on_disk*)p;
694
695                 cur_entry = &ads_entries[i];
696                 ads_entries[i].stream_id = i + 1;
697
698                 /* Do we have at least the size of the fixed-length data we know
699                  * need? */
700                 if (nbytes_remaining < sizeof(struct wim_ads_entry_on_disk))
701                         goto out_invalid;
702
703                 /* Read the length field */
704                 length = le64_to_cpu(disk_entry->length);
705
706                 /* Make sure the length field is neither so small it doesn't
707                  * include all the fixed-length data nor so large it overflows
708                  * the metadata resource buffer. */
709                 if (length < sizeof(struct wim_ads_entry_on_disk) ||
710                     length > nbytes_remaining)
711                         goto out_invalid;
712
713                 /* Read the rest of the fixed-length data. */
714
715                 cur_entry->reserved = le64_to_cpu(disk_entry->reserved);
716                 copy_hash(cur_entry->hash, disk_entry->hash);
717                 cur_entry->stream_name_nbytes = le16_to_cpu(disk_entry->stream_name_nbytes);
718
719                 /* If stream_name_nbytes != 0, this is a named stream.
720                  * Otherwise this is an unnamed stream, or in some cases (bugs
721                  * in Microsoft's software I guess) a meaningless entry
722                  * distinguished from the real unnamed stream entry, if any, by
723                  * the fact that the real unnamed stream entry has a nonzero
724                  * hash field. */
725                 if (cur_entry->stream_name_nbytes) {
726                         /* The name is encoded in UTF16-LE, which uses 2-byte
727                          * coding units, so the length of the name had better be
728                          * an even number of bytes... */
729                         if (cur_entry->stream_name_nbytes & 1)
730                                 goto out_invalid;
731
732                         /* Add the length of the stream name to get the length
733                          * we actually need to read.  Make sure this isn't more
734                          * than the specified length of the entry. */
735                         if (sizeof(struct wim_ads_entry_on_disk) +
736                             cur_entry->stream_name_nbytes > length)
737                                 goto out_invalid;
738
739                         cur_entry->stream_name = MALLOC(cur_entry->stream_name_nbytes + 2);
740                         if (cur_entry->stream_name == NULL)
741                                 goto out_of_memory;
742
743                         memcpy(cur_entry->stream_name,
744                                disk_entry->stream_name,
745                                cur_entry->stream_name_nbytes);
746                         cur_entry->stream_name[cur_entry->stream_name_nbytes / 2] = cpu_to_le16(0);
747                 } else {
748                         /* Mark inode as having weird stream entries.  */
749                         inode->i_canonical_streams = 0;
750                 }
751
752                 /* It's expected that the size of every ADS entry is a multiple
753                  * of 8.  However, to be safe, I'm allowing the possibility of
754                  * an ADS entry at the very end of the metadata resource ending
755                  * un-aligned.  So although we still need to increment the input
756                  * pointer by @length to reach the next ADS entry, it's possible
757                  * that less than @length is actually remaining in the metadata
758                  * resource. We should set the remaining bytes to 0 if this
759                  * happens. */
760                 length = (length + 7) & ~(u64)7;
761                 p += length;
762                 if (nbytes_remaining < length)
763                         nbytes_remaining = 0;
764                 else
765                         nbytes_remaining -= length;
766         }
767         inode->i_ads_entries = ads_entries;
768         inode->i_next_stream_id = inode->i_num_ads + 1;
769         ret = 0;
770         goto out;
771 out_of_memory:
772         ret = WIMLIB_ERR_NOMEM;
773         goto out_free_ads_entries;
774 out_invalid:
775         ERROR("An alternate data stream entry is invalid");
776         ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
777 out_free_ads_entries:
778         if (ads_entries) {
779                 for (u16 i = 0; i < num_ads; i++)
780                         destroy_ads_entry(&ads_entries[i]);
781                 FREE(ads_entries);
782         }
783 out:
784         return ret;
785 }
786
787 /*
788  * Verify a WIM inode:
789  *
790  * - Check to make sure the security ID is valid
791  * - Check to make sure there is at most one unnamed stream
792  * - Check to make sure there is at most one DOS name.
793  *
794  * Return values:
795  *      WIMLIB_ERR_SUCCESS (0)
796  */
797 int
798 verify_inode(struct wim_inode *inode, const struct wim_security_data *sd)
799 {
800         /* Check the security ID.  -1 is valid and means "no security
801          * descriptor".  Anything else has to be a valid index into the WIM
802          * image's security descriptors table. */
803         if (inode->i_security_id < -1 ||
804             (inode->i_security_id >= 0 &&
805              inode->i_security_id >= sd->num_entries))
806         {
807                 WARNING("\"%"TS"\" has an invalid security ID (%d)",
808                         inode_first_full_path(inode), inode->i_security_id);
809                 inode->i_security_id = -1;
810         }
811
812         /* Make sure there is only one unnamed data stream. */
813         unsigned num_unnamed_streams = 0;
814         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
815                 const u8 *hash;
816                 hash = inode_stream_hash(inode, i);
817                 if (inode_stream_name_nbytes(inode, i) == 0 && !is_zero_hash(hash))
818                         num_unnamed_streams++;
819         }
820         if (num_unnamed_streams > 1) {
821                 WARNING("\"%"TS"\" has multiple (%u) un-named streams",
822                         inode_first_full_path(inode), num_unnamed_streams);
823         }
824
825         return 0;
826 }
827
828 void
829 inode_ref_streams(struct wim_inode *inode)
830 {
831         for (unsigned i = 0; i <= inode->i_num_ads; i++) {
832                 struct wim_lookup_table_entry *lte;
833                 lte = inode_stream_lte_resolved(inode, i);
834                 if (lte)
835                         lte->refcnt++;
836         }
837 }
838
839 void
840 inode_unref_streams(struct wim_inode *inode,
841                     struct wim_lookup_table *lookup_table)
842 {
843         struct wim_lookup_table_entry *lte;
844         unsigned i;
845
846         for (i = 0; i <= inode->i_num_ads; i++) {
847                 lte = inode_stream_lte(inode, i, lookup_table);
848                 if (lte)
849                         lte_decrement_refcnt(lte, lookup_table);
850         }
851 }
852
853 int
854 init_inode_table(struct wim_inode_table *table, size_t capacity)
855 {
856         table->array = CALLOC(capacity, sizeof(table->array[0]));
857         if (table->array == NULL) {
858                 ERROR("Cannot initalize inode table: out of memory");
859                 return WIMLIB_ERR_NOMEM;
860         }
861         table->num_entries  = 0;
862         table->capacity  = capacity;
863         INIT_LIST_HEAD(&table->extra_inodes);
864         return 0;
865 }
866
867 void
868 destroy_inode_table(struct wim_inode_table *table)
869 {
870         FREE(table->array);
871 }
872
873 static struct wim_inode *
874 inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno)
875 {
876         u64 hash = hash_u64(hash_u64(ino) + hash_u64(devno));
877         size_t pos = hash % table->capacity;
878         struct wim_inode *inode;
879         struct hlist_node *cur;
880
881         hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
882                 if (inode->i_ino == ino && inode->i_devno == devno) {
883                         DEBUG("Using existing inode {devno=%"PRIu64", ino=%"PRIu64"}",
884                               devno, ino);
885                         inode->i_nlink++;
886                         return inode;
887                 }
888         }
889         inode = new_timeless_inode();
890         if (inode) {
891                 inode->i_ino = ino;
892                 inode->i_devno = devno;
893                 hlist_add_head(&inode->i_hlist, &table->array[pos]);
894                 table->num_entries++;
895         }
896         return inode;
897 }
898
899
900 /* Given a directory entry with the name @name for the file with the inode
901  * number @ino and device number @devno, create a new WIM dentry with an
902  * associated inode, where the inode is shared if an inode with the same @ino
903  * and @devno has already been created.  On success, the new WIM dentry is
904  * written to *dentry_ret, and its inode has i_nlink > 1 if a previously
905  * existing inode was used.
906  */
907 int
908 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
909                        u64 ino, u64 devno, bool noshare,
910                        struct wim_dentry **dentry_ret)
911 {
912         struct wim_dentry *dentry;
913         struct wim_inode *inode;
914         int ret;
915
916         if (noshare) {
917                 /* File that cannot be hardlinked--- Return a new inode with its
918                  * inode and device numbers left at 0. */
919                 ret = new_dentry_with_timeless_inode(name, &dentry);
920                 if (ret)
921                         return ret;
922                 list_add_tail(&dentry->d_inode->i_list, &table->extra_inodes);
923         } else {
924                 /* File that can be hardlinked--- search the table for an
925                  * existing inode matching the inode number and device;
926                  * otherwise create a new inode. */
927                 ret = new_dentry(name, &dentry);
928                 if (ret)
929                         return ret;
930                 inode = inode_table_get_inode(table, ino, devno);
931                 if (!inode) {
932                         free_dentry(dentry);
933                         return WIMLIB_ERR_NOMEM;
934                 }
935                 /* If using an existing inode, we need to gain a reference to
936                  * each of its streams. */
937                 if (inode->i_nlink > 1)
938                         inode_ref_streams(inode);
939                 dentry->d_inode = inode;
940                 inode_add_dentry(dentry, inode);
941         }
942         *dentry_ret = dentry;
943         return 0;
944 }
945
946
947
948 /* Assign consecutive inode numbers to a new set of inodes from the inode table,
949  * and append the inodes to a single list @head that contains the inodes already
950  * existing in the WIM image.  */
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 }