2 * inode_table.c - hard link detection
6 * Copyright (C) 2012-2016 Eric Biggers
8 * This file is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU Lesser General Public License as published by the Free
10 * Software Foundation; either version 3 of the License, or (at your option) any
13 * This file is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this file; if not, see http://www.gnu.org/licenses/.
26 #include "wimlib/bitops.h"
27 #include "wimlib/dentry.h"
28 #include "wimlib/error.h"
29 #include "wimlib/inode.h"
30 #include "wimlib/inode_table.h"
31 #include "wimlib/list.h"
32 #include "wimlib/util.h"
34 /* Initialize a hash table for hard link detection. */
36 init_inode_table(struct wim_inode_table *table, size_t capacity)
38 capacity = roundup_pow_of_2(capacity);
39 table->array = CALLOC(capacity, sizeof(table->array[0]));
41 return WIMLIB_ERR_NOMEM;
43 table->capacity = capacity;
44 INIT_HLIST_HEAD(&table->extra_inodes);
48 /* Free the memory allocated by init_inode_table(). */
50 destroy_inode_table(struct wim_inode_table *table)
55 /* Double the capacity of the inode hash table. */
57 enlarge_inode_table(struct wim_inode_table *table)
59 const size_t old_capacity = table->capacity;
60 const size_t new_capacity = old_capacity * 2;
61 struct hlist_head *old_array = table->array;
62 struct hlist_head *new_array;
63 struct wim_inode *inode;
64 struct hlist_node *tmp;
66 new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
69 table->array = new_array;
70 table->capacity = new_capacity;
71 for (size_t i = 0; i < old_capacity; i++) {
72 hlist_for_each_entry_safe(inode, tmp, &old_array[i], i_hlist_node) {
73 hlist_add_head(&inode->i_hlist_node,
74 &new_array[hash_inode(table, inode->i_ino,
82 * Allocate a new dentry, with hard link detection.
85 * The inode table being used for the current directory scan operation. It
86 * will contain the mapping from (ino, devno) pairs to inodes.
89 * The name to give the new dentry.
92 * The inode number of the file, read from the filesystem.
95 * The device number of the file, read from the filesystem. Proper setting
96 * of this parameter prevents cross-device hardlinks from being created.
97 * If this is not a problem (perhaps because the current directory scan
98 * operation is guaranteed to never traverse a filesystem boundary), then
99 * this parameter can just be a fixed value such as 0.
102 * If %true, the new dentry will not be hard linked to any existing inode,
103 * regardless of the values of @ino and @devno. If %false, normal hard
104 * link detection will be done.
107 * On success, a pointer to the new dentry will be returned in this
108 * location. If i_nlink of the dentry's inode is greater than 1, then this
109 * function created a hard link to an existing inode rather than creating a
112 * On success, returns 0. On failure, returns WIMLIB_ERR_NOMEM or an error code
113 * resulting from a failed string conversion.
116 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
117 u64 ino, u64 devno, bool noshare,
118 struct wim_dentry **dentry_ret)
120 struct wim_dentry *dentry;
121 struct wim_inode *inode;
122 struct hlist_head *list;
126 /* No hard link detection */
127 list = &table->extra_inodes;
129 /* Hard link detection */
130 list = &table->array[hash_inode(table, ino, devno)];
131 hlist_for_each_entry(inode, list, i_hlist_node) {
132 if (inode->i_ino != ino || inode->i_devno != devno)
134 if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) {
135 WARNING("Not honoring directory hard link "
137 inode_any_full_path(inode));
140 /* Inode found; use it. */
141 return new_dentry_with_existing_inode(name, inode,
145 /* Inode not found; create it. */
148 ret = new_dentry_with_new_inode(name, false, &dentry);
151 inode = dentry->d_inode;
153 inode->i_devno = devno;
154 hlist_add_head(&inode->i_hlist_node, list);
155 if (list != &table->extra_inodes)
156 if (++table->filled > table->capacity)
157 enlarge_inode_table(table);
158 *dentry_ret = dentry;
163 * Following the allocation of dentries with hard link detection using
164 * inode_table_new_dentry(), this function will assign consecutive inode numbers
165 * to the new set of inodes. It will also append the list of new inodes to the
166 * list @head, which must contain any inodes already existing in the WIM image.
169 inode_table_prepare_inode_list(struct wim_inode_table *table,
170 struct hlist_head *head)
172 struct wim_inode *inode;
173 struct hlist_node *tmp;
176 /* Re-assign inode numbers in the existing list to avoid duplicates. */
177 hlist_for_each_entry(inode, head, i_hlist_node)
178 inode->i_ino = cur_ino++;
180 /* Assign inode numbers to the new inodes and move them to the image's
182 for (size_t i = 0; i < table->capacity; i++) {
183 hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
184 inode->i_ino = cur_ino++;
185 hlist_add_head(&inode->i_hlist_node, head);
188 hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
189 inode->i_ino = cur_ino++;
190 hlist_add_head(&inode->i_hlist_node, head);