4 * Code to deal with hard links in WIMs. Essentially, the WIM dentries are put
5 * into a hash table indexed by the inode ID field, then for each hard
6 * inode, a linked list is made to connect the dentries.
10 * Copyright (C) 2012 Eric Biggers
12 * This file is part of wimlib, a library for working with WIM files.
14 * wimlib is free software; you can redistribute it and/or modify it under the
15 * terms of the GNU General Public License as published by the Free
16 * Software Foundation; either version 3 of the License, or (at your option)
19 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
20 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
21 * A PARTICULAR PURPOSE. See the GNU General Public License for more
24 * You should have received a copy of the GNU General Public License
25 * along with wimlib; if not, see http://www.gnu.org/licenses/.
28 #include "wimlib_internal.h"
31 #include "lookup_table.h"
36 * / \ ----------- -----------
37 * | dentry<---| struct | | struct |---> dentry
39 * dentry ------------ ------------
43 * ----------- ----------- / \
44 * dentry<---| struct | | struct |---> dentry dentry
45 * / |inode| |inode| \ /
46 * dentry ------------ ------------ dentry
50 * inode_table->array | idx 0 | idx 1 |
54 /* Hash table to find inodes, identified by their inode ID.
57 /* Fields for the hash table */
58 struct hlist_head *array;
63 * Linked list of "extra" inodes. These may be:
65 * - inodes with link count 1, which are all allowed to have 0 for their
66 * inode number, meaning we cannot insert them into the hash table
67 * before calling assign_inode_numbers().
69 * - Groups we create ourselves by splitting a nominal inode due to
70 * inconsistencies in the dentries. These inodes will share a inode
71 * ID with some other inode until assign_inode_numbers() is called.
73 struct hlist_head extra_inodes;
76 /* Returns pointer to a new inode table having the specified capacity */
77 struct inode_table *new_inode_table(size_t capacity)
79 struct inode_table *table;
80 struct hlist_head *array;
82 table = MALLOC(sizeof(struct inode_table));
85 array = CALLOC(capacity, sizeof(array[0]));
90 table->num_entries = 0;
91 table->capacity = capacity;
93 INIT_HLIST_HEAD(&table->extra_inodes);
96 ERROR("Failed to allocate memory for inode table with capacity %zu",
102 * Insert a dentry into the inode table based on its inode
105 * If there is already a dentry in the table having the same inode ID,
106 * and the inode ID is not 0, the dentry is added to the circular
107 * linked list for that inode.
109 * If the inode ID is 0, this indicates a dentry that's in a hard link
110 * inode by itself (has a link count of 1). We can't insert it into the hash
111 * table itself because we don't know what inode numbers are available to
112 * give it (this could be kept track of but would be more difficult). Instead
113 * we keep a linked list of the single dentries, and assign them inode
116 int inode_table_insert(struct dentry *dentry, void *__table)
118 struct inode_table *table = __table;
121 struct inode *d_inode = dentry->inode;
123 if (d_inode->ino == 0) {
125 /* Single inode--- Add to the list of extra inodes (we can't put
126 * it in the table itself because all the singles have a link
128 list_add(&dentry->inode_dentry_list, &d_inode->dentry_list);
129 hlist_add_head(&d_inode->hlist, &table->extra_inodes);
131 /* Hard inode that may contain multiple dentries (the code
132 * will work even if the inode actually contains only 1 dentry
134 struct hlist_node *cur;
136 /* Try adding to existing inode */
137 pos = d_inode->ino % table->capacity;
138 hlist_for_each_entry(inode, cur, &table->array[pos], hlist) {
139 if (inode->ino == d_inode->ino) {
140 list_add(&dentry->inode_dentry_list,
141 &inode->dentry_list);
145 /* Add new inode to the table */
146 list_add(&dentry->inode_dentry_list, &d_inode->dentry_list);
147 hlist_add_head(&d_inode->hlist, &table->array[pos]);
149 /* XXX Make the table grow when too many entries have been
151 table->num_entries++;
156 /* Frees a inode table. */
157 void free_inode_table(struct inode_table *table)
166 assign_inos_to_list(struct hlist_head *head, u64 cur_ino)
169 struct hlist_node *cur;
170 struct dentry *dentry;
171 hlist_for_each_entry(inode, cur, head, hlist) {
176 /* Assign the inode numbers to dentries in a inode table, and return the
177 * next available inode ID. */
178 u64 assign_inode_numbers(struct hlist_head *inode_list)
181 struct hlist_node *cur;
183 struct dentry *dentry;
184 hlist_for_each_entry(inode, cur, inode_list, hlist) {
185 list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list)
186 dentry->link_group_id = cur_ino;
187 inode->ino = cur_ino;
195 print_inode_dentries(const struct inode *inode)
197 struct dentry *dentry;
198 list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list)
199 printf("`%s'\n", dentry->full_path_utf8);
202 static void inconsistent_inode(const struct inode *inode)
204 ERROR("An inconsistent hard link group that we cannot correct has been "
206 ERROR("The dentries are located at the following paths:");
207 print_inode_dentries(inode);
210 static bool ref_dentries_consistent(const struct dentry * restrict ref_dentry_1,
211 const struct dentry * restrict ref_dentry_2)
213 wimlib_assert(ref_dentry_1 != ref_dentry_2);
215 if (ref_dentry_1->inode->num_ads != ref_dentry_2->inode->num_ads)
217 if (ref_dentry_1->inode->security_id != ref_dentry_2->inode->security_id
218 || ref_dentry_1->inode->attributes != ref_dentry_2->inode->attributes)
220 for (unsigned i = 0; i <= ref_dentry_1->inode->num_ads; i++) {
221 const u8 *ref_1_hash, *ref_2_hash;
222 ref_1_hash = inode_stream_hash(ref_dentry_1->inode, i);
223 ref_2_hash = inode_stream_hash(ref_dentry_2->inode, i);
224 if (!hashes_equal(ref_1_hash, ref_2_hash))
226 if (i && !ads_entries_have_same_name(ref_dentry_1->inode->ads_entries[i - 1],
227 ref_dentry_2->inode->ads_entries[i - 1]))
234 static bool dentries_consistent(const struct dentry * restrict ref_dentry,
235 const struct dentry * restrict dentry)
237 wimlib_assert(ref_dentry != dentry);
239 if (ref_dentry->inode->num_ads != dentry->inode->num_ads &&
240 dentry->inode->num_ads != 0)
242 if (ref_dentry->inode->security_id != dentry->inode->security_id
243 || ref_dentry->inode->attributes != dentry->inode->attributes)
245 for (unsigned i = 0; i <= min(ref_dentry->inode->num_ads, dentry->inode->num_ads); i++) {
246 const u8 *ref_hash, *hash;
247 ref_hash = inode_stream_hash(ref_dentry->inode, i);
248 hash = inode_stream_hash(dentry->inode, i);
249 if (!hashes_equal(ref_hash, hash) && !is_zero_hash(hash))
251 if (i && !ads_entries_have_same_name(ref_dentry->inode->ads_entries[i - 1],
252 dentry->inode->ads_entries[i - 1]))
260 print_dentry_list(const struct dentry *first_dentry)
262 const struct dentry *dentry = first_dentry;
264 printf("`%s'\n", dentry->full_path_utf8);
265 } while ((dentry = container_of(dentry->inode_dentry_list.next,
267 inode_dentry_list)) != first_dentry);
272 static size_t inode_link_count(const struct inode *inode)
274 const struct list_head *cur;
276 list_for_each(cur, &inode->dentry_list)
281 static struct dentry *inode_first_dentry(struct inode *inode)
283 return container_of(inode->dentry_list.next, struct dentry,
287 /* Fix up a "true" inode and check for inconsistencies */
288 static int fix_true_inode(struct inode *inode)
290 struct dentry *dentry;
291 struct dentry *ref_dentry = NULL;
295 bool found_short_name = false;
297 list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) {
298 if (!ref_dentry || ref_dentry->inode->num_ads == 0)
300 if (dentry->short_name_len) {
301 if (found_short_name) {
302 ERROR("Multiple short names in hard link "
304 inconsistent_inode(inode);
305 return WIMLIB_ERR_INVALID_DENTRY;
307 found_short_name = true;
310 if (dentry->inode->creation_time > last_ctime)
311 last_ctime = dentry->inode->creation_time;
312 if (dentry->inode->last_write_time > last_mtime)
313 last_mtime = dentry->inode->last_write_time;
314 if (dentry->inode->last_access_time > last_atime)
315 last_atime = dentry->inode->last_access_time;
318 list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) {
319 if (dentry != ref_dentry) {
320 if (!dentries_consistent(ref_dentry, dentry)) {
321 inconsistent_inode(inode);
322 return WIMLIB_ERR_INVALID_DENTRY;
324 /* Free the unneeded `struct inode'. */
325 free_inode(dentry->inode);
326 dentry->inode = ref_dentry->inode;
327 ref_dentry->inode->link_count++;
330 ref_dentry->inode->creation_time = last_ctime;
331 ref_dentry->inode->last_write_time = last_mtime;
332 ref_dentry->inode->last_access_time = last_atime;
333 wimlib_assert(inode_link_count(inode) == inode->link_count);
338 * Fixes up a nominal inode.
340 * By a nominal inode we mean a group of two or more dentries that share
341 * the same hard link group ID.
343 * If dentries in the inode are found to be inconsistent, we may split the inode
344 * into several "true" inodes. @new_inodes points to a linked list of
345 * these split inodes, and if we create any, they will be added to this list.
347 * After splitting up each nominal inode into the "true" inodes we
348 * will canonicalize the link group by getting rid of all the superfluous
349 * `struct inodes'. There will be just one `struct inode' for each hard link
353 fix_nominal_inode(struct inode *inode, struct hlist_head *inode_list)
355 struct dentry *tmp, *dentry, *ref_dentry;
356 struct hlist_node *cur;
358 size_t num_true_inodes;
360 LIST_HEAD(dentries_with_data_streams);
361 LIST_HEAD(dentries_with_no_data_streams);
362 HLIST_HEAD(true_inodes);
364 /* Create a list of dentries in the nominal inode that have at
365 * least one data stream with a non-zero hash, and another list that
366 * contains the dentries that have a zero hash for all data streams. */
367 list_for_each_entry(dentry, &inode->dentry_list, inode_dentry_list) {
368 for (unsigned i = 0; i <= dentry->inode->num_ads; i++) {
370 hash = inode_stream_hash(dentry->inode, i);
371 if (!is_zero_hash(hash)) {
372 list_add(&dentry->tmp_list,
373 &dentries_with_data_streams);
377 list_add(&dentry->tmp_list,
378 &dentries_with_no_data_streams);
383 /* If there are no dentries with data streams, we require the nominal
384 * inode to be a true inode */
385 if (list_empty(&dentries_with_data_streams)) {
388 if (inode->link_count > 1) {
389 DEBUG("Found link group of size %zu without "
390 "any data streams:", inode->link_count);
391 print_inode_dentries(inode);
392 DEBUG("We are going to interpret it as true "
393 "link group, provided that the dentries "
398 hlist_add_head(&inode->hlist, inode_list);
399 return fix_true_inode(inode);
402 /* One or more dentries had data streams specified. We check each of
403 * these dentries for consistency with the others to form a set of true
406 list_for_each_entry(dentry, &dentries_with_data_streams, tmp_list)
408 /* Look for a true inode that is consistent with
409 * this dentry and add this dentry to it. Or, if none
410 * of the true inodes are consistent with this
411 * dentry, make a new one. */
412 hlist_for_each_entry(inode, cur, &true_inodes, hlist) {
413 if (ref_dentries_consistent(inode_first_dentry(inode), dentry)) {
414 list_add(&dentry->inode_dentry_list,
415 &inode->dentry_list);
420 hlist_add_head(&dentry->inode->hlist, &true_inodes);
421 INIT_LIST_HEAD(&dentry->inode->dentry_list);
422 list_add(&dentry->inode_dentry_list, &dentry->inode->dentry_list);
427 wimlib_assert(num_true_inodes != 0);
429 /* If there were dentries with no data streams, we require there to only
430 * be one true inode so that we know which inode to assign the
431 * streamless dentries to. */
432 if (!list_empty(&dentries_with_no_data_streams)) {
433 if (num_true_inodes != 1) {
434 ERROR("Hard inode ambiguity detected!");
435 ERROR("We split up inode 0x%"PRIx64" due to "
436 "inconsistencies,", inode->ino);
437 ERROR("but dentries with no stream information remained. "
438 "We don't know which true hard link");
439 ERROR("inode to assign them to.");
440 return WIMLIB_ERR_INVALID_DENTRY;
442 /* Assign the streamless dentries to the one and only true link
444 ref_dentry = inode_first_dentry(inode);
445 list_for_each_entry(dentry, &dentries_with_no_data_streams, tmp_list)
446 list_add(&dentry->inode_dentry_list, &inode->dentry_list);
448 if (num_true_inodes != 1) {
451 printf("Split nominal inode 0x%"PRIx64" into %zu "
453 inode->ino, num_true_inodes);
454 puts("------------------------------------------------------------------------------");
456 hlist_for_each_entry(inode, cur, &true_inodes, hlist) {
457 printf("[Split inode %zu]\n", i++);
458 print_inode_dentries(inode);
461 puts("------------------------------------------------------------------------------");
466 hlist_for_each_entry(inode, cur, &true_inodes, hlist) {
467 hlist_add_head(&inode->hlist, inode_list);
468 ret = fix_true_inode(inode);
476 * Goes through each inode and shares the inodes among members of a hard
479 * In the process, the dentries in each inode are checked for consistency.
480 * If they contain data features that indicate they cannot really be in the same
481 * inode, this should be an error, but in reality this case needs to
482 * be handled, so we split the dentries into different inodes.
484 int fix_inodes(struct inode_table *table, struct hlist_head *inode_list)
487 struct hlist_node *cur, *tmp;
489 INIT_HLIST_HEAD(inode_list);
490 for (u64 i = 0; i < table->capacity; i++) {
491 hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], hlist) {
492 ret = fix_nominal_inode(inode, inode_list);