Commit a06ec283e125 ("hfs: add logic of correcting a next unused CNID") made hfs_correct_next_unused_CNID() lower the next CNID after the newest file or directory is deleted. It takes the CNID of the last file or directory record in the catalog as the largest CNID in use. However, catalog records are sorted by parent ID and name, not by CNID, so the next CNID can be one that is still in use. As of now, creating a file after deleting the newest one can fail with EEXIST. Commit 6592287869bf ("hfs: fix incorrect inode ID assignment in hfs_new_inode()") exposed this issue. The issue can be reproduced on a freshly formatted HFS volume with: mkdir z touch a b rm b touch c Without this change, the result is: touch: cannot touch 'c': File exists With it, c is created. Keep the largest CNID of the records in and below each catalog node in memory, in leaf nodes and in index nodes, so that the root node gives the largest CNID in use. Adding a record raises it in the nodes above, and removing the record with the largest CNID makes them compute it again. Fixes: a06ec283e125 ("hfs: add logic of correcting a next unused CNID") Cc: stable@vger.kernel.org Suggested-by: Viacheslav Dubeyko Assisted-by: LLM Signed-off-by: Hengyu Liang --- Changes in v2: - Keep the largest CNID in memory in every catalog node, leaf and index, as Viacheslav Dubeyko suggested. v1 walked the leaf nodes. - Rebase on hfs for-next. - v1: https://lore.kernel.org/r/20261015110114.1649059-1-hengyul@cs.unc.edu Tested in KVM with KASAN on 34ee5f8c2198, without and with this patch. All fstests on HFS: 24 failures without the patch, 20 with it, no new failures. Deleting 8000 files: unpatched patched newest first 11 s 0.36 s odd ones, then even ones newest first 3.8 s 0.19 s Creating the files (0.54 s and 0.55 s) and deleting them oldest first (0.37 s and 0.38 s) take about the same time. fs/hfs/brec.c | 172 +++++++++++++++++++++++++++++++++++++++++++++++ fs/hfs/btree.h | 5 ++ fs/hfs/catalog.c | 96 +++----------------------- 3 files changed, 186 insertions(+), 87 deletions(-) diff --git a/fs/hfs/brec.c b/fs/hfs/brec.c index 1ca1ee9f73ef..318bbee43529 100644 --- a/fs/hfs/brec.c +++ b/fs/hfs/brec.c @@ -62,6 +62,174 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) return retval; } +/* Get the CNID of a file or directory record of the catalog tree */ +static u32 hfs_brec_cnid(struct hfs_bnode *node, u32 off) +{ + __be32 cnid; + + switch (hfs_bnode_read_u8(node, off)) { + case HFS_CDR_DIR: + off += offsetof(struct hfs_cat_dir, DirID); + break; + case HFS_CDR_FIL: + off += offsetof(struct hfs_cat_file, FlNum); + break; + default: + return 0; + } + hfs_bnode_read(node, &cnid, off, sizeof(cnid)); + return be32_to_cpu(cnid); +} + +/* Forget max_cnid of all nodes of the tree */ +static void hfs_btree_drop_max_cnid(struct hfs_btree *tree) +{ + struct hfs_bnode *node; + int i; + + spin_lock(&tree->hash_lock); + for (i = 0; i < NODE_HASH_SIZE; i++) { + for (node = tree->node_hash[i]; node; node = node->next_hash) + clear_bit(HFS_BNODE_MAX_CNID, &node->flags); + } + spin_unlock(&tree->hash_lock); +} + +/* + * The record at @off has been added to the catalog leaf @node, or is about + * to be removed from it. Update max_cnid of the node and of its parents: + * a new CNID can only raise it, and after the largest CNID is gone it has + * to be computed again. + */ +static void hfs_brec_update_max_cnid(struct hfs_bnode *node, u32 off, + bool insert) +{ + struct hfs_btree *tree = node->tree; + u32 nidx = node->this; + u32 cnid; + bool done; + + if (tree->cnid != HFS_CAT_CNID || node->type != HFS_NODE_LEAF) + return; + cnid = hfs_brec_cnid(node, off); + if (!cnid) + return; + + for (;;) { + node = hfs_bnode_find(tree, nidx); + if (IS_ERR(node)) + break; + + done = nidx == tree->root; + if (test_bit(HFS_BNODE_MAX_CNID, &node->flags)) { + if (insert && node->max_cnid < cnid) + node->max_cnid = cnid; + else if (!insert && node->max_cnid <= cnid) + clear_bit(HFS_BNODE_MAX_CNID, &node->flags); + else + done = true; /* the parents do not change */ + } + nidx = node->parent; + hfs_bnode_put(node); + + if (done) + return; + if (!nidx) + break; + } + + /* a parent could not be reached */ + hfs_btree_drop_max_cnid(tree); +} + +/* + * Compute max_cnid of a catalog node: the largest CNID of the file and + * directory records of a leaf node, or the largest max_cnid of the children + * of an index node. If a child has no max_cnid yet, return the number of + * that child in @child instead. + */ +static int hfs_brec_calc_max_cnid(struct hfs_bnode *node, u32 *child) +{ + struct hfs_bnode *cnode; + u32 max_cnid = 0; + u16 off, len, keylen; + __be32 data; + int i; + + for (i = 0; i < node->num_recs; i++) { + len = hfs_brec_lenoff(node, i, &off); + keylen = hfs_brec_keylen(node, i); + if (!keylen || keylen + sizeof(data) > len) + return -EIO; + off += keylen; + + if (node->type == HFS_NODE_LEAF) { + max_cnid = max(max_cnid, hfs_brec_cnid(node, off)); + continue; + } + + hfs_bnode_read(node, &data, off, sizeof(data)); + cnode = hfs_bnode_find(node->tree, be32_to_cpu(data)); + if (IS_ERR(cnode)) + return PTR_ERR(cnode); + if (cnode->height != node->height - 1) { + hfs_bnode_put(cnode); + return -EIO; + } + if (!test_bit(HFS_BNODE_MAX_CNID, &cnode->flags)) { + cnode->parent = node->this; + *child = cnode->this; + hfs_bnode_put(cnode); + return 0; + } + max_cnid = max(max_cnid, cnode->max_cnid); + hfs_bnode_put(cnode); + } + + node->max_cnid = max_cnid; + set_bit(HFS_BNODE_MAX_CNID, &node->flags); + return 0; +} + +/* + * hfs_btree_max_cnid() + * + * Find the largest CNID of the file and directory records of the catalog + * tree. It is max_cnid of the root node. max_cnid is not stored on disk, + * so walk down to the nodes that do not have it and compute it from the + * bottom up. + */ +int hfs_btree_max_cnid(struct hfs_btree *tree, u32 *max_cnid) +{ + struct hfs_bnode *node; + u32 nidx = tree->root; + u32 child; + int res = 0; + + *max_cnid = 0; + while (nidx && !res) { + node = hfs_bnode_find(tree, nidx); + if (IS_ERR(node)) + return PTR_ERR(node); + + child = 0; + if (!test_bit(HFS_BNODE_MAX_CNID, &node->flags)) + res = hfs_brec_calc_max_cnid(node, &child); + + if (res || child) { + nidx = child; + } else if (nidx == tree->root) { + *max_cnid = node->max_cnid; + nidx = 0; + } else { + /* a node that was read again has lost its parent */ + nidx = node->parent ? node->parent : tree->root; + } + hfs_bnode_put(node); + } + return res; +} + int hfs_brec_insert(struct hfs_find_data *fd, void *entry, u32 entry_len) { struct hfs_btree *tree; @@ -131,6 +299,7 @@ int hfs_brec_insert(struct hfs_find_data *fd, void *entry, u32 entry_len) skip: hfs_bnode_write(node, fd->search_key, data_off, key_len); hfs_bnode_write(node, entry, data_off + key_len, entry_len); + hfs_brec_update_max_cnid(node, data_off + key_len, true); hfs_bnode_dump(node); /* @@ -183,6 +352,7 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode; + hfs_brec_update_max_cnid(node, fd->entryoffset, false); again: rec_off = tree->node_size - (fd->record + 2) * 2; end_off = tree->node_size - (node->num_recs + 1) * 2; @@ -322,6 +492,8 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) } new_node->num_recs = node->num_recs - num_recs; node->num_recs = num_recs; + /* the records that move to the new node may hold the largest CNID */ + clear_bit(HFS_BNODE_MAX_CNID, &node->flags); new_rec_off = tree->node_size - rec_size; new_off = node_desc_size; diff --git a/fs/hfs/btree.h b/fs/hfs/btree.h index 1f703f2c53d8..21f69cddc683 100644 --- a/fs/hfs/btree.h +++ b/fs/hfs/btree.h @@ -62,6 +62,9 @@ struct hfs_bnode { u8 type; u8 height; + /* catalog tree: largest CNID in the records in and below the node */ + u32 max_cnid; + struct hfs_bnode *next_hash; unsigned long flags; wait_queue_head_t lock_wq; @@ -73,6 +76,7 @@ struct hfs_bnode { #define HFS_BNODE_ERROR 0 #define HFS_BNODE_NEW 1 #define HFS_BNODE_DELETED 2 +#define HFS_BNODE_MAX_CNID 3 /* max_cnid is valid */ struct hfs_find_data { btree_key *key; @@ -140,6 +144,7 @@ extern u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off); extern u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec); extern int hfs_brec_insert(struct hfs_find_data *fd, void *entry, u32 entry_len); extern int hfs_brec_remove(struct hfs_find_data *fd); +extern int hfs_btree_max_cnid(struct hfs_btree *tree, u32 *max_cnid); /* bfind.c */ extern int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd); diff --git a/fs/hfs/catalog.c b/fs/hfs/catalog.c index 490c5e130da3..ead094e44c9a 100644 --- a/fs/hfs/catalog.c +++ b/fs/hfs/catalog.c @@ -271,102 +271,24 @@ void hfs_set_next_unused_CNID(struct super_block *sb, static int hfs_correct_next_unused_CNID(struct super_block *sb, u32 cnid) { - struct hfs_btree *cat_tree; - struct hfs_bnode *node; - s64 leaf_head; - s64 leaf_tail; - s64 node_id; + u32 max_cnid; + int res; hfs_dbg("cnid %u, next_id %lld\n", cnid, atomic64_read(&HFS_SB(sb)->next_id)); - if ((cnid + 1) < atomic64_read(&HFS_SB(sb)->next_id)) { + if ((cnid + 1) != atomic64_read(&HFS_SB(sb)->next_id)) { /* next ID should be unchanged */ return 0; } - cat_tree = HFS_SB(sb)->cat_tree; - leaf_head = cat_tree->leaf_head; - leaf_tail = cat_tree->leaf_tail; - - if (leaf_head > leaf_tail) { - pr_err("node is corrupted: leaf_head %lld, leaf_tail %lld\n", - leaf_head, leaf_tail); - return -ERANGE; - } - - node = hfs_bnode_find(cat_tree, leaf_tail); - if (IS_ERR(node)) { - pr_err("fail to find leaf node: node ID %lld\n", - leaf_tail); - return -ENOENT; - } - - node_id = leaf_tail; - - do { - int i; - - if (node_id != leaf_tail) { - node = hfs_bnode_find(cat_tree, node_id); - if (IS_ERR(node)) - return -ENOENT; - } - - hfs_dbg("node %lld, leaf_tail %lld, leaf_head %lld\n", - node_id, leaf_tail, leaf_head); - - hfs_bnode_dump(node); - - for (i = node->num_recs - 1; i >= 0; i--) { - hfs_cat_rec rec; - u16 off, len, keylen; - int entryoffset; - int entrylength; - u32 found_cnid; - - len = hfs_brec_lenoff(node, i, &off); - keylen = hfs_brec_keylen(node, i); - if (keylen == 0) { - pr_err("fail to get the keylen: " - "node_id %lld, record index %d\n", - node_id, i); - return -EINVAL; - } - - entryoffset = off + keylen; - entrylength = len - keylen; - - if (entrylength > sizeof(rec)) { - pr_err("unexpected record length: " - "entrylength %d\n", - entrylength); - return -EINVAL; - } - - hfs_bnode_read(node, &rec, entryoffset, entrylength); - - if (rec.type == HFS_CDR_DIR) { - found_cnid = be32_to_cpu(rec.dir.DirID); - hfs_dbg("found_cnid %u\n", found_cnid); - hfs_set_next_unused_CNID(sb, cnid, found_cnid); - hfs_bnode_put(node); - return 0; - } else if (rec.type == HFS_CDR_FIL) { - found_cnid = be32_to_cpu(rec.file.FlNum); - hfs_dbg("found_cnid %u\n", found_cnid); - hfs_set_next_unused_CNID(sb, cnid, found_cnid); - hfs_bnode_put(node); - return 0; - } - } - - node_id = node->prev; - hfs_bnode_put(node); - - } while (node_id >= leaf_head); + res = hfs_btree_max_cnid(HFS_SB(sb)->cat_tree, &max_cnid); + if (res) + return res; - return -ENOENT; + hfs_dbg("max_cnid %u\n", max_cnid); + hfs_set_next_unused_CNID(sb, cnid, max_cnid); + return 0; } /* base-commit: 34ee5f8c2198db9585da6c181c50869d2eb43c3a -- 2.53.0