2 * inode_table.c - hard link detection
6 * Copyright (C) 2012, 2013, 2014 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/dentry.h"
27 #include "wimlib/error.h"
28 #include "wimlib/inode.h"
29 #include "wimlib/inode_table.h"
30 #include "wimlib/list.h"
31 #include "wimlib/util.h"
33 /* Initialize a hash table for hard link detection. */
35 init_inode_table(struct wim_inode_table *table, size_t capacity)
37 table->array = CALLOC(capacity, sizeof(table->array[0]));
39 return WIMLIB_ERR_NOMEM;
40 table->num_entries = 0;
41 table->capacity = capacity;
42 INIT_HLIST_HEAD(&table->extra_inodes);
46 /* Free the memory allocated by init_inode_table(). */
48 destroy_inode_table(struct wim_inode_table *table)
54 * Allocate a new dentry, with hard link detection.
57 * The inode table being used for the current directory scan operation. It
58 * will contain the mapping from (ino, devno) pairs to inodes.
61 * The name to give the new dentry.
64 * The inode number of the file, read from the filesystem.
67 * The device number of the file, read from the filesystem. Proper setting
68 * of this parameter prevents cross-device hardlinks from being created.
69 * If this is not a problem (perhaps because the current directory scan
70 * operation is guaranteed to never traverse a filesystem boundary), then
71 * this parameter can just be a fixed value such as 0.
74 * If %true, the new dentry will not be hard linked to any existing inode,
75 * regardless of the values of @ino and @devno. If %false, normal hard
76 * link detection will be done.
79 * On success, a pointer to the new dentry will be returned in this
80 * location. If i_nlink of the dentry's inode is greater than 1, then this
81 * function created a hard link to an existing inode rather than creating a
84 * On success, returns 0. On failure, returns WIMLIB_ERR_NOMEM or an error code
85 * resulting from a failed string conversion.
88 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
89 u64 ino, u64 devno, bool noshare,
90 struct wim_dentry **dentry_ret)
92 struct wim_dentry *dentry;
93 struct wim_inode *inode;
97 /* File that cannot be hardlinked--- Return a new inode with its
98 * inode and device numbers left at 0. */
99 ret = new_dentry_with_new_inode(name, false, &dentry);
102 hlist_add_head(&dentry->d_inode->i_hlist_node, &table->extra_inodes);
106 /* File that can be hardlinked--- search the table for an
107 * existing inode matching the inode number and device. */
108 pos = hash_u64(hash_u64(ino) + hash_u64(devno)) % table->capacity;
109 hlist_for_each_entry(inode, &table->array[pos], i_hlist_node) {
110 if (inode->i_ino == ino && inode->i_devno == devno) {
111 /* Found; use the existing inode. */
112 return new_dentry_with_existing_inode(name, inode,
117 /* Not found; create a new inode and add it to the table. */
118 ret = new_dentry_with_new_inode(name, false, &dentry);
121 inode = dentry->d_inode;
123 inode->i_devno = devno;
124 hlist_add_head(&inode->i_hlist_node, &table->array[pos]);
125 table->num_entries++;
127 *dentry_ret = dentry;
132 * Following the allocation of dentries with hard link detection using
133 * inode_table_new_dentry(), this function will assign consecutive inode numbers
134 * to the new set of inodes. It will also append the list of new inodes to the
135 * list @head, which must contain any inodes already existing in the WIM image.
138 inode_table_prepare_inode_list(struct wim_inode_table *table,
139 struct hlist_head *head)
141 struct wim_inode *inode;
142 struct hlist_node *tmp;
145 /* Re-assign inode numbers in the existing list to avoid duplicates. */
146 hlist_for_each_entry(inode, head, i_hlist_node)
147 inode->i_ino = cur_ino++;
149 /* Assign inode numbers to the new inodes and move them to the image's
151 for (size_t i = 0; i < table->capacity; i++) {
152 hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
153 inode->i_ino = cur_ino++;
154 hlist_add_head(&inode->i_hlist_node, head);
156 INIT_HLIST_HEAD(&table->array[i]);
158 hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
159 inode->i_ino = cur_ino++;
160 hlist_add_head(&inode->i_hlist_node, head);
162 INIT_HLIST_HEAD(&table->extra_inodes);
163 table->num_entries = 0;