/* 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->d_inode;
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,
}
/* 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;
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);
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;
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
#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;
+}