4 * Functions that operate on WIM inodes.
6 * See dentry.c for a description of the relationship between WIM dentries and
11 * Copyright (C) 2012, 2013, 2014 Eric Biggers
13 * This file is part of wimlib, a library for working with WIM files.
15 * wimlib is free software; you can redistribute it and/or modify it under the
16 * terms of the GNU General Public License as published by the Free
17 * Software Foundation; either version 3 of the License, or (at your option)
20 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
21 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
22 * A PARTICULAR PURPOSE. See the GNU General Public License for more
25 * You should have received a copy of the GNU General Public License
26 * along with wimlib; if not, see http://www.gnu.org/licenses/.
33 #include "wimlib/assert.h"
34 #include "wimlib/dentry.h" /* Only for dentry_full_path(). Otherwise the code
35 in this file doesn't care about file names/paths.
37 #include "wimlib/encoding.h"
38 #include "wimlib/endianness.h"
39 #include "wimlib/error.h"
40 #include "wimlib/inode.h"
41 #include "wimlib/inode_table.h"
42 #include "wimlib/lookup_table.h"
43 #include "wimlib/security.h"
44 #include "wimlib/timestamp.h"
48 /* Allocate a new inode. Set the timestamps to the current time. */
52 struct wim_inode *inode = new_timeless_inode();
54 u64 now = get_wim_timestamp();
55 inode->i_creation_time = now;
56 inode->i_last_access_time = now;
57 inode->i_last_write_time = now;
62 /* Allocate a new inode. Leave the timestamps zeroed out. */
64 new_timeless_inode(void)
66 struct wim_inode *inode = CALLOC(1, sizeof(struct wim_inode));
68 inode->i_security_id = -1;
70 inode->i_next_stream_id = 1;
71 inode->i_not_rpfixed = 1;
72 inode->i_canonical_streams = 1;
73 INIT_LIST_HEAD(&inode->i_list);
74 INIT_LIST_HEAD(&inode->i_dentry);
79 /* Decrement link count on an inode. */
81 put_inode(struct wim_inode *inode)
83 wimlib_assert(inode->i_nlink != 0);
84 if (--inode->i_nlink == 0) {
85 /* If FUSE mounts are enabled, we must keep a unlinked inode
86 * around until all file descriptors to it have been closed. */
88 if (inode->i_num_opened_fds == 0)
94 /* Free memory allocated within an alternate data stream entry. */
96 destroy_ads_entry(struct wim_ads_entry *ads_entry)
98 FREE(ads_entry->stream_name);
101 /* Free an inode. Only use this if there can't be other links to the inode or
102 * if it doesn't matter if there are. */
104 free_inode(struct wim_inode *inode)
106 if (unlikely(!inode))
109 if (unlikely(inode->i_ads_entries)) {
110 for (u16 i = 0; i < inode->i_num_ads; i++)
111 destroy_ads_entry(&inode->i_ads_entries[i]);
112 FREE(inode->i_ads_entries);
114 if (unlikely(inode->i_extra))
115 FREE(inode->i_extra);
116 /* HACK: This may instead delete the inode from i_list, but hlist_del()
117 * behaves the same as list_del(). */
118 if (!hlist_unhashed(&inode->i_hlist))
119 hlist_del(&inode->i_hlist);
123 /* Return %true iff the alternate data stream entry @entry has the UTF-16LE
124 * stream name @name that has length @name_nbytes bytes. */
126 ads_entry_has_name(const struct wim_ads_entry *entry,
127 const utf16lechar *name, size_t name_nbytes,
130 return 0 == cmp_utf16le_strings(name,
133 entry->stream_name_nbytes / 2,
138 * Returns the alternate data stream entry belonging to @inode that has the
139 * stream name @stream_name, or NULL if the inode has no alternate data stream
142 * If @p stream_name is the empty string, NULL is returned --- that is, this
143 * function will not return "unnamed" alternate data stream entries.
145 * If NULL is returned, errno is set.
147 struct wim_ads_entry *
148 inode_get_ads_entry(struct wim_inode *inode, const tchar *stream_name)
151 const utf16lechar *stream_name_utf16le;
152 size_t stream_name_utf16le_nbytes;
154 struct wim_ads_entry *result;
156 if (inode->i_num_ads == 0) {
161 if (stream_name[0] == T('\0')) {
166 ret = tstr_get_utf16le_and_len(stream_name, &stream_name_utf16le,
167 &stream_name_utf16le_nbytes);
174 if (ads_entry_has_name(&inode->i_ads_entries[i],
176 stream_name_utf16le_nbytes,
177 default_ignore_case))
179 result = &inode->i_ads_entries[i];
182 } while (++i != inode->i_num_ads);
184 tstr_put_utf16le(stream_name_utf16le);
191 static struct wim_ads_entry *
192 do_inode_add_ads(struct wim_inode *inode,
193 utf16lechar *stream_name, size_t stream_name_nbytes)
196 struct wim_ads_entry *ads_entries;
197 struct wim_ads_entry *new_entry;
199 if (inode->i_num_ads >= 0xfffe) {
200 ERROR("File \"%"TS"\" has too many alternate data streams!",
201 inode_first_full_path(inode));
205 num_ads = inode->i_num_ads + 1;
206 ads_entries = REALLOC(inode->i_ads_entries,
207 num_ads * sizeof(inode->i_ads_entries[0]));
211 inode->i_ads_entries = ads_entries;
213 new_entry = &inode->i_ads_entries[num_ads - 1];
215 memset(new_entry, 0, sizeof(struct wim_ads_entry));
216 new_entry->stream_name = stream_name;
217 new_entry->stream_name_nbytes = stream_name_nbytes;
218 new_entry->stream_id = inode->i_next_stream_id++;
219 inode->i_num_ads = num_ads;
224 * Add an alternate data stream entry to a WIM inode (UTF-16LE version). On
225 * success, returns a pointer to the new entry. Note that this pointer might
226 * become invalid if another ADS entry is added to the inode. On failure,
227 * returns NULL and sets errno.
229 struct wim_ads_entry *
230 inode_add_ads_utf16le(struct wim_inode *inode,
231 const utf16lechar *stream_name, size_t stream_name_nbytes)
233 utf16lechar *dup = NULL;
234 struct wim_ads_entry *result;
236 if (stream_name_nbytes) {
237 dup = utf16le_dupz(stream_name, stream_name_nbytes);
242 result = do_inode_add_ads(inode, dup, stream_name_nbytes);
249 * Add an alternate data stream entry to a WIM inode (tchar version). On
250 * success, returns a pointer to the new entry. Note that this pointer might
251 * become invalid if another ADS entry is added to the inode. On failure,
252 * returns NULL and sets errno.
254 struct wim_ads_entry *
255 inode_add_ads(struct wim_inode *inode, const tchar *stream_name)
257 utf16lechar *stream_name_utf16le = NULL;
258 size_t stream_name_utf16le_nbytes = 0;
259 struct wim_ads_entry *result;
261 if (stream_name && *stream_name)
262 if (tstr_to_utf16le(stream_name,
263 tstrlen(stream_name) * sizeof(tchar),
264 &stream_name_utf16le,
265 &stream_name_utf16le_nbytes))
268 result = do_inode_add_ads(inode, stream_name_utf16le,
269 stream_name_utf16le_nbytes);
271 FREE(stream_name_utf16le);
276 * Add an data alternate stream entry to a WIM inode, where the contents of the
277 * new stream are specified in a data buffer. The inode must be resolved.
279 * On success, returns a pointer to the new alternate data stream entry. Note
280 * that this pointer might become invalid if another ADS entry is added to the
281 * inode. On failure, returns NULL and sets errno.
283 struct wim_ads_entry *
284 inode_add_ads_with_data(struct wim_inode *inode, const tchar *name,
285 const void *value, size_t size,
286 struct wim_lookup_table *lookup_table)
288 struct wim_ads_entry *new_entry;
290 wimlib_assert(inode->i_resolved);
292 new_entry = inode_add_ads(inode, name);
296 new_entry->lte = new_stream_from_data_buffer(value, size, lookup_table);
297 if (!new_entry->lte) {
298 inode_remove_ads(inode, new_entry, NULL);
305 * Does the inode have any named data streams?
308 inode_has_named_stream(const struct wim_inode *inode)
310 for (u16 i = 0; i < inode->i_num_ads; i++)
311 if (ads_entry_is_named_stream(&inode->i_ads_entries[i]))
316 /* Set the unnamed stream of a WIM inode, given a data buffer containing the
317 * stream contents. The inode must be resolved and cannot have an unnamed
318 * stream specified already. */
320 inode_set_unnamed_stream(struct wim_inode *inode, const void *data, size_t len,
321 struct wim_lookup_table *lookup_table)
323 wimlib_assert(inode->i_resolved);
324 wimlib_assert(!inode->i_lte);
325 inode->i_lte = new_stream_from_data_buffer(data, len, lookup_table);
327 return WIMLIB_ERR_NOMEM;
331 /* Remove an alternate data stream from a WIM inode. */
333 inode_remove_ads(struct wim_inode *inode, struct wim_ads_entry *entry,
334 struct wim_lookup_table *lookup_table)
336 struct wim_lookup_table_entry *lte;
337 unsigned idx = entry - inode->i_ads_entries;
339 wimlib_assert(idx < inode->i_num_ads);
340 wimlib_assert(inode->i_resolved);
344 lte_decrement_refcnt(lte, lookup_table);
346 destroy_ads_entry(entry);
348 memmove(&inode->i_ads_entries[idx],
349 &inode->i_ads_entries[idx + 1],
350 (inode->i_num_ads - idx - 1) * sizeof(inode->i_ads_entries[0]));
355 * Resolve an inode's single-instance streams.
357 * This takes each SHA-1 message digest stored in the inode or one of its ADS
358 * entries and replaces it with a pointer directly to the appropriate 'struct
359 * wim_lookup_table_entry' currently inserted into @table to represent the
360 * single-instance stream having that SHA-1 message digest.
362 * If @force is %false:
363 * If any of the needed single-instance streams do not exist in @table,
364 * return WIMLIB_ERR_RESOURCE_NOT_FOUND and leave the inode unmodified.
365 * If @force is %true:
366 * If any of the needed single-instance streams do not exist in @table,
367 * allocate new entries for them and insert them into @table. This does
368 * not, of course, cause these streams to magically exist, but this is
369 * needed by the code for extraction from a pipe.
371 * If the inode is already resolved, this function does nothing.
373 * Returns 0 on success; WIMLIB_ERR_NOMEM if out of memory; or
374 * WIMLIB_ERR_RESOURCE_NOT_FOUND if @force is %false and at least one
375 * single-instance stream referenced by the inode was missing.
378 inode_resolve_streams(struct wim_inode *inode, struct wim_lookup_table *table,
382 struct wim_lookup_table_entry *lte, *ads_lte;
384 if (inode->i_resolved)
387 struct wim_lookup_table_entry *ads_ltes[inode->i_num_ads];
389 /* Resolve the default data stream */
391 hash = inode->i_hash;
392 if (!is_zero_hash(hash)) {
393 lte = lookup_stream(table, hash);
396 lte = new_lookup_table_entry();
398 return WIMLIB_ERR_NOMEM;
399 copy_hash(lte->hash, hash);
400 lookup_table_insert(table, lte);
402 goto stream_not_found;
407 /* Resolve the alternate data streams */
408 for (u16 i = 0; i < inode->i_num_ads; i++) {
409 struct wim_ads_entry *cur_entry;
412 cur_entry = &inode->i_ads_entries[i];
413 hash = cur_entry->hash;
414 if (!is_zero_hash(hash)) {
415 ads_lte = lookup_stream(table, hash);
418 ads_lte = new_lookup_table_entry();
420 return WIMLIB_ERR_NOMEM;
421 copy_hash(ads_lte->hash, hash);
422 lookup_table_insert(table, ads_lte);
424 goto stream_not_found;
428 ads_ltes[i] = ads_lte;
431 for (u16 i = 0; i < inode->i_num_ads; i++)
432 inode->i_ads_entries[i].lte = ads_ltes[i];
433 inode->i_resolved = 1;
437 return stream_not_found_error(inode, hash);
441 * Undo the effects of inode_resolve_streams().
443 * If the inode is not resolved, this function does nothing.
446 inode_unresolve_streams(struct wim_inode *inode)
448 if (!inode->i_resolved)
452 copy_hash(inode->i_hash, inode->i_lte->hash);
454 zero_out_hash(inode->i_hash);
456 for (u16 i = 0; i < inode->i_num_ads; i++) {
457 if (inode->i_ads_entries[i].lte)
458 copy_hash(inode->i_ads_entries[i].hash,
459 inode->i_ads_entries[i].lte->hash);
461 zero_out_hash(inode->i_ads_entries[i].hash);
463 inode->i_resolved = 0;
467 stream_not_found_error(const struct wim_inode *inode, const u8 *hash)
469 if (wimlib_print_errors) {
470 ERROR("\"%"TS"\": stream not found", inode_first_full_path(inode));
471 tfprintf(wimlib_error_file,
472 T(" SHA-1 message digest of missing stream:\n "));
473 print_hash(hash, wimlib_error_file);
474 tputc(T('\n'), wimlib_error_file);
476 return WIMLIB_ERR_RESOURCE_NOT_FOUND;
480 * Return the lookup table entry for stream @stream_idx of the inode, where
481 * stream_idx = 0 means the default un-named file stream, and stream_idx >= 1
482 * corresponds to an alternate data stream.
484 * This works for both resolved and un-resolved inodes.
486 struct wim_lookup_table_entry *
487 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
488 const struct wim_lookup_table *table)
490 if (inode->i_resolved)
491 return inode_stream_lte_resolved(inode, stream_idx);
493 return inode_stream_lte_unresolved(inode, stream_idx, table);
497 * Return the lookup table entry for the unnamed data stream of a *resolved*
498 * inode, or NULL if there is none. Also return the 0-based index of the
499 * corresponding stream in *stream_idx_ret.
501 struct wim_lookup_table_entry *
502 inode_unnamed_stream_resolved(const struct wim_inode *inode, u16 *stream_idx_ret)
504 wimlib_assert(inode->i_resolved);
505 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
506 if (inode_stream_name_nbytes(inode, i) == 0 &&
507 !is_zero_hash(inode_stream_hash_resolved(inode, i)))
510 return inode_stream_lte_resolved(inode, i);
518 * Return the lookup table entry for the unnamed data stream of a *resolved*
519 * inode, or NULL if there is none.
521 struct wim_lookup_table_entry *
522 inode_unnamed_lte_resolved(const struct wim_inode *inode)
525 return inode_unnamed_stream_resolved(inode, &stream_idx);
529 * Return the lookup table entry for the unnamed data stream of an *unresolved*
530 * inode, or NULL if there is none.
532 struct wim_lookup_table_entry *
533 inode_unnamed_lte_unresolved(const struct wim_inode *inode,
534 const struct wim_lookup_table *table)
536 wimlib_assert(!inode->i_resolved);
537 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
538 if (inode_stream_name_nbytes(inode, i) == 0 &&
539 !is_zero_hash(inode_stream_hash_unresolved(inode, i)))
541 return inode_stream_lte_unresolved(inode, i, table);
548 * Return the lookup table entry for the unnamed data stream of an inode, or
549 * NULL if there is none.
551 * You'd think this would be easier than it actually is, since the unnamed data
552 * stream should be the one referenced from the inode itself. Alas, if there
553 * are named data streams, Microsoft's "imagex.exe" program will put the unnamed
554 * data stream in one of the alternate data streams instead of inside the WIM
555 * dentry itself. So we need to check the alternate data streams too.
557 * Also, note that a dentry may appear to have more than one unnamed stream, but
558 * if the SHA-1 message digest is all 0's then the corresponding stream does not
559 * really "count" (this is the case for the inode's own file stream when the
560 * file stream that should be there is actually in one of the alternate stream
561 * entries.). This is despite the fact that we may need to extract such a
562 * missing entry as an empty file or empty named data stream.
564 struct wim_lookup_table_entry *
565 inode_unnamed_lte(const struct wim_inode *inode,
566 const struct wim_lookup_table *table)
568 if (inode->i_resolved)
569 return inode_unnamed_lte_resolved(inode);
571 return inode_unnamed_lte_unresolved(inode, table);
575 * Return the SHA-1 message digest of the unnamed data stream of a WIM inode.
577 * If inode does not have an unnamed data stream, this returns a void SHA-1
578 * message digest containing all zero bytes.
581 inode_unnamed_stream_hash(const struct wim_inode *inode)
585 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
586 if (inode_stream_name_nbytes(inode, i) == 0) {
587 hash = inode_stream_hash(inode, i);
588 if (!is_zero_hash(hash))
596 * Translate a single-instance stream entry into the pointer contained in the
597 * inode (or ads entry of an inode) that references it.
599 * This is only possible for "unhashed" streams, which are guaranteed to have
600 * only one reference, and that reference is guaranteed to be in a resolved
601 * inode. (It can't be in an unresolved inode, since that would imply the hash
604 struct wim_lookup_table_entry **
605 retrieve_lte_pointer(struct wim_lookup_table_entry *lte)
607 wimlib_assert(lte->unhashed);
608 struct wim_inode *inode = lte->back_inode;
609 u32 stream_id = lte->back_stream_id;
611 return &inode->i_lte;
613 for (u16 i = 0; i < inode->i_num_ads; i++)
614 if (inode->i_ads_entries[i].stream_id == stream_id)
615 return &inode->i_ads_entries[i].lte;
621 * Read the alternate data stream entries of a WIM dentry.
624 * Pointer to buffer that starts with the first alternate stream entry.
627 * Inode to load the alternate data streams into. @inode->i_num_ads must
628 * have been set to the number of alternate data streams that are expected.
630 * @nbytes_remaining_p:
631 * Number of bytes of data remaining in the buffer pointed to by @p.
632 * On success this will be updated to point just past the ADS entries.
634 * On success, inode->i_ads_entries is set to an array of `struct
635 * wim_ads_entry's of length inode->i_num_ads. On failure, @inode is not
639 * WIMLIB_ERR_SUCCESS (0)
640 * WIMLIB_ERR_INVALID_METADATA_RESOURCE
644 read_ads_entries(const u8 * restrict p, struct wim_inode * restrict inode,
645 size_t *nbytes_remaining_p)
647 size_t nbytes_remaining = *nbytes_remaining_p;
649 struct wim_ads_entry *ads_entries;
652 BUILD_BUG_ON(sizeof(struct wim_ads_entry_on_disk) != WIM_ADS_ENTRY_DISK_SIZE);
654 /* Allocate an array for our in-memory representation of the alternate
655 * data stream entries. */
656 num_ads = inode->i_num_ads;
657 ads_entries = CALLOC(num_ads, sizeof(inode->i_ads_entries[0]));
661 /* Read the entries into our newly allocated buffer. */
662 for (u16 i = 0; i < num_ads; i++) {
664 struct wim_ads_entry *cur_entry;
665 const struct wim_ads_entry_on_disk *disk_entry =
666 (const struct wim_ads_entry_on_disk*)p;
668 cur_entry = &ads_entries[i];
669 ads_entries[i].stream_id = i + 1;
671 /* Do we have at least the size of the fixed-length data we know
673 if (nbytes_remaining < sizeof(struct wim_ads_entry_on_disk))
676 /* Read the length field */
677 length = le64_to_cpu(disk_entry->length);
679 /* Make sure the length field is neither so small it doesn't
680 * include all the fixed-length data nor so large it overflows
681 * the metadata resource buffer. */
682 if (length < sizeof(struct wim_ads_entry_on_disk) ||
683 length > nbytes_remaining)
686 /* Read the rest of the fixed-length data. */
688 cur_entry->reserved = le64_to_cpu(disk_entry->reserved);
689 copy_hash(cur_entry->hash, disk_entry->hash);
690 cur_entry->stream_name_nbytes = le16_to_cpu(disk_entry->stream_name_nbytes);
692 /* If stream_name_nbytes != 0, this is a named stream.
693 * Otherwise this is an unnamed stream, or in some cases (bugs
694 * in Microsoft's software I guess) a meaningless entry
695 * distinguished from the real unnamed stream entry, if any, by
696 * the fact that the real unnamed stream entry has a nonzero
698 if (cur_entry->stream_name_nbytes) {
699 /* The name is encoded in UTF16-LE, which uses 2-byte
700 * coding units, so the length of the name had better be
701 * an even number of bytes... */
702 if (cur_entry->stream_name_nbytes & 1)
705 /* Add the length of the stream name to get the length
706 * we actually need to read. Make sure this isn't more
707 * than the specified length of the entry. */
708 if (sizeof(struct wim_ads_entry_on_disk) +
709 cur_entry->stream_name_nbytes > length)
712 cur_entry->stream_name = utf16le_dupz(disk_entry->stream_name,
713 cur_entry->stream_name_nbytes);
714 if (!cur_entry->stream_name)
717 /* Mark inode as having weird stream entries. */
718 inode->i_canonical_streams = 0;
721 /* It's expected that the size of every ADS entry is a multiple
722 * of 8. However, to be safe, I'm allowing the possibility of
723 * an ADS entry at the very end of the metadata resource ending
724 * un-aligned. So although we still need to increment the input
725 * pointer by @length to reach the next ADS entry, it's possible
726 * that less than @length is actually remaining in the metadata
727 * resource. We should set the remaining bytes to 0 if this
729 length = (length + 7) & ~7;
731 if (nbytes_remaining < length)
732 nbytes_remaining = 0;
734 nbytes_remaining -= length;
736 inode->i_ads_entries = ads_entries;
737 inode->i_next_stream_id = inode->i_num_ads + 1;
738 *nbytes_remaining_p = nbytes_remaining;
742 ret = WIMLIB_ERR_NOMEM;
743 goto out_free_ads_entries;
745 ERROR("An alternate data stream entry is invalid");
746 ret = WIMLIB_ERR_INVALID_METADATA_RESOURCE;
747 out_free_ads_entries:
749 for (u16 i = 0; i < num_ads; i++)
750 destroy_ads_entry(&ads_entries[i]);
757 /* Check a WIM inode for unusual field values. */
759 check_inode(struct wim_inode *inode, const struct wim_security_data *sd)
761 /* Check the security ID. -1 is valid and means "no security
762 * descriptor". Anything else has to be a valid index into the WIM
763 * image's security descriptors table. */
764 if (inode->i_security_id < -1 ||
765 (inode->i_security_id >= 0 &&
766 inode->i_security_id >= sd->num_entries))
768 WARNING("\"%"TS"\" has an invalid security ID (%d)",
769 inode_first_full_path(inode), inode->i_security_id);
770 inode->i_security_id = -1;
773 /* Make sure there is only one unnamed data stream. */
774 unsigned num_unnamed_streams = 0;
775 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
777 hash = inode_stream_hash(inode, i);
778 if (inode_stream_name_nbytes(inode, i) == 0 && !is_zero_hash(hash))
779 num_unnamed_streams++;
781 if (num_unnamed_streams > 1) {
782 WARNING("\"%"TS"\" has multiple (%u) un-named streams",
783 inode_first_full_path(inode), num_unnamed_streams);
784 /* We currently don't treat this as an error and will just end
785 * up using the first unnamed data stream in the inode. */
789 /* Acquire another reference to each single-instance stream referenced by this
790 * inode. This is necessary when creating a hard link to this inode.
792 * The inode must be resolved. */
794 inode_ref_streams(struct wim_inode *inode)
796 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
797 struct wim_lookup_table_entry *lte;
799 lte = inode_stream_lte_resolved(inode, i);
805 /* Drop a reference to each single-instance stream referenced by this inode.
806 * This is necessary when deleting a hard link to this inode. */
808 inode_unref_streams(struct wim_inode *inode,
809 struct wim_lookup_table *lookup_table)
811 for (unsigned i = 0; i <= inode->i_num_ads; i++) {
812 struct wim_lookup_table_entry *lte;
814 lte = inode_stream_lte(inode, i, lookup_table);
816 lte_decrement_refcnt(lte, lookup_table);
820 /* Initialize a hash table for hard link detection. */
822 init_inode_table(struct wim_inode_table *table, size_t capacity)
824 table->array = CALLOC(capacity, sizeof(table->array[0]));
826 return WIMLIB_ERR_NOMEM;
827 table->num_entries = 0;
828 table->capacity = capacity;
829 INIT_LIST_HEAD(&table->extra_inodes);
833 /* Free the memory allocated by init_inode_table(). */
835 destroy_inode_table(struct wim_inode_table *table)
840 static struct wim_inode *
841 inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno)
843 u64 hash = hash_u64(hash_u64(ino) + hash_u64(devno));
844 size_t pos = hash % table->capacity;
845 struct wim_inode *inode;
846 struct hlist_node *cur;
848 /* Search for an existing inode having the same inode number and device
850 hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
851 if (inode->i_ino == ino && inode->i_devno == devno) {
852 /* Found; use the existing inode. */
858 /* Create a new inode and insert it into the table. */
859 inode = new_timeless_inode();
862 inode->i_devno = devno;
863 hlist_add_head(&inode->i_hlist, &table->array[pos]);
864 table->num_entries++;
870 * Allocate a new dentry, with hard link detection.
873 * The inode table being used for the current directory scan operation. It
874 * will contain the mapping from (ino, devno) pairs to inodes.
877 * The name to give the new dentry.
880 * The inode number of the file, read from the filesystem.
883 * The device number of the file, read from the filesystem. Proper setting
884 * of this parameter prevents cross-device hardlinks from being created.
885 * If this is not a problem (perhaps because the current directory scan
886 * operation is guaranteed to never traverse a filesystem boundary), then
887 * this parameter can just be a fixed value such as 0.
890 * If %true, the new dentry will not be hard linked to any existing inode,
891 * regardless of the values of @ino and @devno. If %false, normal hard
892 * link detection will be done.
895 * On success, a pointer to the new dentry will be returned in this
896 * location. If i_nlink of the dentry's inode is greater than 1, then this
897 * function created a hard link to an existing inode rather than creating a
900 * On success, returns 0. On failure, returns WIMLIB_ERR_NOMEM or an error code
901 * resulting from a failed string conversion.
904 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
905 u64 ino, u64 devno, bool noshare,
906 struct wim_dentry **dentry_ret)
908 struct wim_dentry *dentry;
909 struct wim_inode *inode;
913 /* File that cannot be hardlinked--- Return a new inode with its
914 * inode and device numbers left at 0. */
915 ret = new_dentry_with_timeless_inode(name, &dentry);
918 list_add_tail(&dentry->d_inode->i_list, &table->extra_inodes);
920 /* File that can be hardlinked--- search the table for an
921 * existing inode matching the inode number and device;
922 * otherwise create a new inode. */
923 ret = new_dentry(name, &dentry);
926 inode = inode_table_get_inode(table, ino, devno);
929 return WIMLIB_ERR_NOMEM;
931 /* If using an existing inode, we need to gain a reference to
932 * each of its streams. */
933 if (inode->i_nlink > 1)
934 inode_ref_streams(inode);
935 dentry->d_inode = inode;
936 inode_add_dentry(dentry, inode);
938 *dentry_ret = dentry;
945 * Following the allocation of dentries with hard link detection using
946 * inode_table_new_dentry(), this function will assign consecutive inode numbers
947 * to the new set of inodes. It will also append the list of new inodes to the
948 * list @head, which must contain any inodes already existing in the WIM image.
951 inode_table_prepare_inode_list(struct wim_inode_table *table,
952 struct list_head *head)
954 struct wim_inode *inode, *tmp_inode;
955 struct hlist_node *cur, *tmp;
958 /* Re-assign inode numbers in the existing list to avoid duplicates. */
959 list_for_each_entry(inode, head, i_list)
960 inode->i_ino = cur_ino++;
962 /* Assign inode numbers to the new inodes and move them to the image's
964 for (size_t i = 0; i < table->capacity; i++) {
965 hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist)
967 inode->i_ino = cur_ino++;
969 list_add_tail(&inode->i_list, head);
971 INIT_HLIST_HEAD(&table->array[i]);
973 list_for_each_entry_safe(inode, tmp_inode, &table->extra_inodes, i_list)
975 inode->i_ino = cur_ino++;
977 list_add_tail(&inode->i_list, head);
979 INIT_LIST_HEAD(&table->extra_inodes);
980 table->num_entries = 0;