/* NULL NULL
* ^ ^
- * dentry | |
- * / \ ----------- -----------
+ * dentry | |
+ * / \ ----------- -----------
* | dentry<---| struct | | struct |---> dentry
- * \ / |inode| |inode|
+ * \ / | inode | | inode |
* dentry ------------ ------------
* ^ ^
* | |
* | | dentry
* ----------- ----------- / \
* dentry<---| struct | | struct |---> dentry dentry
- * / |inode| |inode| \ /
+ * / | inode | | inode | \ /
* dentry ------------ ------------ dentry
* ^ ^
* | |
* -----------------
- * inode_table->array | idx 0 | idx 1 |
+ * inode_table->array | idx 0 | idx 1 |
* -----------------
*/
+/* Hash table to find inodes, identified by their inode ID.
+ * */
+struct inode_table {
+ /* Fields for the hash table */
+ struct hlist_head *array;
+ u64 num_entries;
+ u64 capacity;
+
+ /*
+ * Linked list of "extra" inodes. These may be:
+ *
+ * - inodes with link count 1, which are all allowed to have 0 for their
+ * inode number, meaning we cannot insert them into the hash table
+ * before calling assign_inode_numbers().
+ *
+ * - Groups we create ourselves by splitting a nominal inode due to
+ * inconsistencies in the dentries. These inodes will share a inode
+ * ID with some other inode until assign_inode_numbers() is called.
+ */
+ struct hlist_head extra_inodes;
+};
+
+static inline void destroy_inode_table(struct inode_table *table)
+{
+ FREE(table->array);
+}
-int init_inode_table(struct inode_table *table, size_t capacity)
+static int init_inode_table(struct inode_table *table, size_t capacity)
{
table->array = CALLOC(capacity, sizeof(table->array[0]));
if (!table->array) {
return 0;
}
-
-static size_t inode_link_count(const struct inode *inode)
+static inline size_t inode_link_count(const struct inode *inode)
{
const struct list_head *cur;
size_t size = 0;
return size;
}
-/*
+/*
* Insert a dentry into the inode table based on its inode
* ID.
*
* we keep a linked list of the single dentries, and assign them inode
* numbers later.
*/
-int inode_table_insert(struct dentry *dentry, void *__table)
+static int inode_table_insert(struct dentry *dentry, void *__table)
{
struct inode_table *table = __table;
- struct inode *d_inode = dentry->inode;
+ struct inode *d_inode = dentry->d_inode;
if (d_inode->ino == 0) {
/* Single inode--- Add to the list of extra inodes (we can't put
static void inconsistent_inode(const struct inode *inode)
{
- ERROR("An inconsistent hard link group that we cannot correct has been "
- "detected");
+ ERROR("An inconsistent hard link group that cannot be corrected has "
+ "been detected");
ERROR("The dentries are located at the following paths:");
+#ifdef ENABLE_ERROR_MESSAGES
print_inode_dentries(inode);
+#endif
}
static bool ref_inodes_consistent(const struct inode * restrict ref_inode_1,
ref_2_hash = inode_stream_hash(ref_inode_2, i);
if (!hashes_equal(ref_1_hash, ref_2_hash))
return false;
- if (i && !ads_entries_have_same_name(ref_inode_1->ads_entries[i - 1],
- ref_inode_2->ads_entries[i - 1]))
+ if (i && !ads_entries_have_same_name(&ref_inode_1->ads_entries[i - 1],
+ &ref_inode_2->ads_entries[i - 1]))
return false;
}
hash = inode_stream_hash(inode, i);
if (!hashes_equal(ref_hash, hash) && !is_zero_hash(hash))
return false;
- if (i && !ads_entries_have_same_name(ref_inode->ads_entries[i - 1],
- inode->ads_entries[i - 1]))
+ if (i && !ads_entries_have_same_name(&ref_inode->ads_entries[i - 1],
+ &inode->ads_entries[i - 1]))
return false;
}
return true;
}
/* Fix up a "true" inode and check for inconsistencies */
-static int fix_true_inode(struct inode *inode)
+static int fix_true_inode(struct inode *inode, struct hlist_head *inode_list)
{
struct dentry *dentry;
struct dentry *ref_dentry = NULL;
u64 last_atime = 0;
inode_for_each_dentry(dentry, inode) {
- if (!ref_dentry || dentry->inode->num_ads > ref_dentry->inode->num_ads)
+ if (!ref_dentry || dentry->d_inode->num_ads > ref_dentry->d_inode->num_ads)
ref_dentry = dentry;
- if (dentry->inode->creation_time > last_ctime)
- last_ctime = dentry->inode->creation_time;
- if (dentry->inode->last_write_time > last_mtime)
- last_mtime = dentry->inode->last_write_time;
- if (dentry->inode->last_access_time > last_atime)
- last_atime = dentry->inode->last_access_time;
+ if (dentry->d_inode->creation_time > last_ctime)
+ last_ctime = dentry->d_inode->creation_time;
+ if (dentry->d_inode->last_write_time > last_mtime)
+ last_mtime = dentry->d_inode->last_write_time;
+ if (dentry->d_inode->last_access_time > last_atime)
+ last_atime = dentry->d_inode->last_access_time;
}
- ref_inode = ref_dentry->inode;
+ ref_inode = ref_dentry->d_inode;
ref_inode->link_count = 1;
+ hlist_add_head(&ref_inode->hlist, inode_list);
list_del(&inode->dentry_list);
list_add(&ref_inode->dentry_list, &ref_dentry->inode_dentry_list);
inode_for_each_dentry(dentry, ref_inode) {
if (dentry != ref_dentry) {
- if (!inodes_consistent(ref_inode, dentry->inode)) {
+ if (!inodes_consistent(ref_inode, dentry->d_inode)) {
inconsistent_inode(ref_inode);
return WIMLIB_ERR_INVALID_DENTRY;
}
/* Free the unneeded `struct inode'. */
- free_inode(dentry->inode);
- dentry->inode = ref_inode;
+ dentry->d_inode->hlist.next = NULL;
+ dentry->d_inode->hlist.pprev = NULL;
+ free_inode(dentry->d_inode);
+ dentry->d_inode = ref_inode;
ref_inode->link_count++;
}
}
return 0;
}
-/*
+/*
* Fixes up a nominal inode.
*
* By a nominal inode we mean a group of two or more dentries that share
* inodes'. There will be just one `struct inode' for each hard link group
* remaining.
*/
-static int
-fix_nominal_inode(struct inode *inode, struct hlist_head *inode_list)
+static int fix_nominal_inode(struct inode *inode,
+ struct hlist_head *inode_list)
{
- struct dentry *dentry, *ref_dentry;
+ struct dentry *dentry;
struct hlist_node *cur, *tmp;
int ret;
size_t num_true_inodes;
* least one data stream with a non-zero hash, and another list that
* contains the dentries that have a zero hash for all data streams. */
inode_for_each_dentry(dentry, inode) {
- for (unsigned i = 0; i <= dentry->inode->num_ads; i++) {
+ for (unsigned i = 0; i <= dentry->d_inode->num_ads; i++) {
const u8 *hash;
- hash = inode_stream_hash(dentry->inode, i);
+ hash = inode_stream_hash(dentry->d_inode, i);
if (!is_zero_hash(hash)) {
list_add(&dentry->tmp_list,
&dentries_with_data_streams);
if (list_empty(&dentries_with_data_streams)) {
#ifdef ENABLE_DEBUG
if (inode->link_count > 1) {
- DEBUG("Found link group of size %zu without "
+ DEBUG("Found link group of size %u without "
"any data streams:", inode->link_count);
print_inode_dentries(inode);
DEBUG("We are going to interpret it as true "
"are consistent.");
}
#endif
- hlist_add_head(&inode->hlist, inode_list);
- return fix_true_inode(inode);
+ return fix_true_inode(inode, inode_list);
}
/* One or more dentries had data streams specified. We check each of
* consistent with this dentry, add a new one (if that happens,
* we have split the hard link group). */
hlist_for_each_entry(inode, cur, &true_inodes, hlist) {
- if (ref_inodes_consistent(inode, dentry->inode)) {
+ if (ref_inodes_consistent(inode, dentry->d_inode)) {
inode_add_dentry(dentry, inode);
goto next_dentry_2;
}
}
num_true_inodes++;
- INIT_LIST_HEAD(&dentry->inode->dentry_list);
- inode_add_dentry(dentry, dentry->inode);
- hlist_add_head(&dentry->inode->hlist, &true_inodes);
+ INIT_LIST_HEAD(&dentry->d_inode->dentry_list);
+ inode_add_dentry(dentry, dentry->d_inode);
+ hlist_add_head(&dentry->d_inode->hlist, &true_inodes);
next_dentry_2:
;
}
#endif
hlist_for_each_entry_safe(inode, cur, tmp, &true_inodes, hlist) {
- hlist_add_head(&inode->hlist, inode_list);
- ret = fix_true_inode(inode);
+ ret = fix_true_inode(inode, inode_list);
if (ret != 0)
return ret;
}
* split inodes as well as the inodes that were good before, is returned in the
* list @inode_list.
*/
-int fix_inodes(struct inode_table *table, struct hlist_head *inode_list)
+static int fix_inodes(struct inode_table *table, struct hlist_head *inode_list)
{
struct inode *inode;
struct hlist_node *cur, *tmp;
hlist_add_head(cur, inode_list);
return 0;
}
+
+int dentry_tree_fix_inodes(struct dentry *root, struct hlist_head *inode_list)
+{
+ struct inode_table inode_tab;
+ int ret;
+
+ DEBUG("Inserting dentries into inode table");
+ ret = init_inode_table(&inode_tab, 9001);
+ if (ret != 0)
+ return ret;
+
+ for_dentry_in_tree(root, inode_table_insert, &inode_tab);
+
+ DEBUG("Cleaning up the hard link groups");
+ ret = fix_inodes(&inode_tab, inode_list);
+ destroy_inode_table(&inode_tab);
+ return ret;
+}
git://wimlib.net / wimlib / blobdiff