^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * linux/fs/hfs/brec.c
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (C) 2001
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Brad Boyer (flar@allandria.com)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * (C) 2003 Ardis Technologies <roman@ardistech.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * Handle individual btree records
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include "btree.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) static int hfs_brec_update_parent(struct hfs_find_data *fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) static int hfs_btree_inc_height(struct hfs_btree *tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) /* Get the length and offset of the given record in the given node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) __be16 retval[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) u16 dataoff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) dataoff = node->tree->node_size - (rec + 2) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) hfs_bnode_read(node, retval, dataoff, 4);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) *off = be16_to_cpu(retval[1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) return be16_to_cpu(retval[0]) - *off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) /* Get the length of the key from a keyed record */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) u16 retval, recoff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) if ((node->type == HFS_NODE_INDEX) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) if (node->tree->attributes & HFS_TREE_BIGKEYS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) retval = node->tree->max_key_len + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) retval = node->tree->max_key_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) if (!recoff)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) if (node->tree->attributes & HFS_TREE_BIGKEYS) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) retval = hfs_bnode_read_u16(node, recoff) + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) if (retval > node->tree->max_key_len + 2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) pr_err("keylen %d too large\n", retval);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) retval = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) if (retval > node->tree->max_key_len + 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) pr_err("keylen %d too large\n", retval);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) retval = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) return retval;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int entry_len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) struct hfs_btree *tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) struct hfs_bnode *node, *new_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) int size, key_len, rec;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) int data_off, end_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) int idx_rec_off, data_rec_off, end_rec_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) __be32 cnid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) tree = fd->tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) if (!fd->bnode) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) if (!tree->root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) hfs_btree_inc_height(tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) node = hfs_bnode_find(tree, tree->leaf_head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) if (IS_ERR(node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) return PTR_ERR(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) fd->bnode = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) fd->record = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) new_node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) key_len = (fd->search_key->key_len | 1) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) again:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) /* new record idx and complete record size */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) rec = fd->record + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) size = key_len + entry_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) node = fd->bnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) hfs_bnode_dump(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) /* get last offset */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) end_rec_off = tree->node_size - (node->num_recs + 1) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) end_off = hfs_bnode_read_u16(node, end_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) end_rec_off -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) hfs_dbg(BNODE_MOD, "insert_rec: %d, %d, %d, %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) rec, size, end_off, end_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) if (size > end_rec_off - end_off) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) if (new_node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) panic("not enough room!\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) new_node = hfs_bnode_split(fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) if (IS_ERR(new_node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) return PTR_ERR(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) goto again;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) if (node->type == HFS_NODE_LEAF) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) tree->leaf_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) mark_inode_dirty(tree->inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) node->num_recs++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) /* write new last offset */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) hfs_bnode_write_u16(node, end_rec_off, end_off + size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) data_off = end_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) data_rec_off = end_rec_off + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) idx_rec_off = tree->node_size - (rec + 1) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) if (idx_rec_off == data_rec_off)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) goto skip;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) /* move all following entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) data_off = hfs_bnode_read_u16(node, data_rec_off + 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) hfs_bnode_write_u16(node, data_rec_off, data_off + size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) data_rec_off += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) } while (data_rec_off < idx_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) /* move data away */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) hfs_bnode_move(node, data_off + size, data_off,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) end_off - data_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) skip:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) hfs_bnode_write(node, fd->search_key, data_off, key_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) hfs_bnode_write(node, entry, data_off + key_len, entry_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) hfs_bnode_dump(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) * update parent key if we inserted a key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) * at the start of the node and it is not the new node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) if (!rec && new_node != node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) hfs_bnode_read_key(node, fd->search_key, data_off + size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) hfs_brec_update_parent(fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) if (new_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) hfs_bnode_put(fd->bnode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) if (!new_node->parent) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) hfs_btree_inc_height(tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) new_node->parent = tree->root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) fd->bnode = hfs_bnode_find(tree, new_node->parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) /* create index data entry */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) cnid = cpu_to_be32(new_node->this);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) entry = &cnid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) entry_len = sizeof(cnid);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) /* get index key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) hfs_bnode_read_key(new_node, fd->search_key, 14);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) __hfs_brec_find(fd->bnode, fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) hfs_bnode_put(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) new_node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) if (tree->attributes & HFS_TREE_VARIDXKEYS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) key_len = fd->search_key->key_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) fd->search_key->key_len = tree->max_key_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) key_len = tree->max_key_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) goto again;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) int hfs_brec_remove(struct hfs_find_data *fd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) struct hfs_btree *tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) struct hfs_bnode *node, *parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) int end_off, rec_off, data_off, size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) tree = fd->tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) node = fd->bnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) again:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) rec_off = tree->node_size - (fd->record + 2) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) end_off = tree->node_size - (node->num_recs + 1) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) if (node->type == HFS_NODE_LEAF) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) tree->leaf_count--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) mark_inode_dirty(tree->inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) hfs_bnode_dump(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) hfs_dbg(BNODE_MOD, "remove_rec: %d, %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) fd->record, fd->keylength + fd->entrylength);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) if (!--node->num_recs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) hfs_bnode_unlink(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) if (!node->parent)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) parent = hfs_bnode_find(tree, node->parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) if (IS_ERR(parent))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) return PTR_ERR(parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) node = fd->bnode = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) __hfs_brec_find(node, fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) goto again;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) if (rec_off == end_off)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) goto skip;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) size = fd->keylength + fd->entrylength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) data_off = hfs_bnode_read_u16(node, rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) hfs_bnode_write_u16(node, rec_off + 2, data_off - size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) rec_off -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) } while (rec_off >= end_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) /* fill hole */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) hfs_bnode_move(node, fd->keyoffset, fd->keyoffset + size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) data_off - fd->keyoffset - size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) skip:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) hfs_bnode_dump(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) if (!fd->record)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) hfs_brec_update_parent(fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) struct hfs_btree *tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) struct hfs_bnode *node, *new_node, *next_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) struct hfs_bnode_desc node_desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) int num_recs, new_rec_off, new_off, old_rec_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) int data_start, data_end, size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) tree = fd->tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) node = fd->bnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) new_node = hfs_bmap_alloc(tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) if (IS_ERR(new_node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) return new_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) hfs_bnode_get(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) hfs_dbg(BNODE_MOD, "split_nodes: %d - %d - %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) node->this, new_node->this, node->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) new_node->next = node->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) new_node->prev = node->this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) new_node->parent = node->parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) new_node->type = node->type;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) new_node->height = node->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) if (node->next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) next_node = hfs_bnode_find(tree, node->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) next_node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) if (IS_ERR(next_node)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) hfs_bnode_put(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) return next_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) size = tree->node_size / 2 - node->num_recs * 2 - 14;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) old_rec_off = tree->node_size - 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) num_recs = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) data_start = hfs_bnode_read_u16(node, old_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) if (data_start > size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) old_rec_off -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) if (++num_recs < node->num_recs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) /* panic? */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) hfs_bnode_put(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) if (next_node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) hfs_bnode_put(next_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) return ERR_PTR(-ENOSPC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) if (fd->record + 1 < num_recs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) /* new record is in the lower half,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) * so leave some more space there
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) old_rec_off += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) num_recs--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) data_start = hfs_bnode_read_u16(node, old_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) hfs_bnode_get(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) fd->bnode = new_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) fd->record -= num_recs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) fd->keyoffset -= data_start - 14;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) fd->entryoffset -= data_start - 14;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) new_node->num_recs = node->num_recs - num_recs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) node->num_recs = num_recs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) new_rec_off = tree->node_size - 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) new_off = 14;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) size = data_start - new_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) num_recs = new_node->num_recs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) data_end = data_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) while (num_recs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) hfs_bnode_write_u16(new_node, new_rec_off, new_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) old_rec_off -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) new_rec_off -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) data_end = hfs_bnode_read_u16(node, old_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) new_off = data_end - size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) num_recs--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) hfs_bnode_write_u16(new_node, new_rec_off, new_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) /* update new bnode header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) node_desc.next = cpu_to_be32(new_node->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) node_desc.prev = cpu_to_be32(new_node->prev);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) node_desc.type = new_node->type;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) node_desc.height = new_node->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) node_desc.num_recs = cpu_to_be16(new_node->num_recs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) node_desc.reserved = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) /* update previous bnode header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) node->next = new_node->this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) node_desc.next = cpu_to_be32(node->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) node_desc.num_recs = cpu_to_be16(node->num_recs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) /* update next bnode header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) if (next_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) next_node->prev = new_node->this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) node_desc.prev = cpu_to_be32(next_node->prev);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) hfs_bnode_put(next_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) } else if (node->this == tree->leaf_tail) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) /* if there is no next node, this might be the new tail */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) tree->leaf_tail = new_node->this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) mark_inode_dirty(tree->inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) hfs_bnode_dump(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) hfs_bnode_dump(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) return new_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) static int hfs_brec_update_parent(struct hfs_find_data *fd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) struct hfs_btree *tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) struct hfs_bnode *node, *new_node, *parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) int newkeylen, diff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) int rec, rec_off, end_rec_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) int start_off, end_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) tree = fd->tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) node = fd->bnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) new_node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) if (!node->parent)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) again:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) parent = hfs_bnode_find(tree, node->parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) if (IS_ERR(parent))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) return PTR_ERR(parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) __hfs_brec_find(parent, fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) if (fd->record < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) hfs_bnode_dump(parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) rec = fd->record;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) /* size difference between old and new key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) if (tree->attributes & HFS_TREE_VARIDXKEYS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) newkeylen = (hfs_bnode_read_u8(node, 14) | 1) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) fd->keylength = newkeylen = tree->max_key_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) hfs_dbg(BNODE_MOD, "update_rec: %d, %d, %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) rec, fd->keylength, newkeylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) rec_off = tree->node_size - (rec + 2) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) diff = newkeylen - fd->keylength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) if (!diff)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) goto skip;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) if (diff > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) end_off = hfs_bnode_read_u16(parent, end_rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) if (end_rec_off - end_off < diff) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) printk(KERN_DEBUG "splitting index node...\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) fd->bnode = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) new_node = hfs_bnode_split(fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) if (IS_ERR(new_node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) return PTR_ERR(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) parent = fd->bnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) rec = fd->record;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) rec_off = tree->node_size - (rec + 2) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) end_off = start_off = hfs_bnode_read_u16(parent, rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) hfs_bnode_write_u16(parent, rec_off, start_off + diff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) start_off -= 4; /* move previous cnid too */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) while (rec_off > end_rec_off) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) rec_off -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) end_off = hfs_bnode_read_u16(parent, rec_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) hfs_bnode_write_u16(parent, rec_off, end_off + diff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) hfs_bnode_move(parent, start_off + diff, start_off,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) end_off - start_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) skip:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) if (!(tree->attributes & HFS_TREE_VARIDXKEYS))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) hfs_bnode_write_u8(parent, fd->keyoffset, newkeylen - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) hfs_bnode_dump(parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) node = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) if (new_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) __be32 cnid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) if (!new_node->parent) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) hfs_btree_inc_height(tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) new_node->parent = tree->root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) fd->bnode = hfs_bnode_find(tree, new_node->parent);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) /* create index key and entry */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) hfs_bnode_read_key(new_node, fd->search_key, 14);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) cnid = cpu_to_be32(new_node->this);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) __hfs_brec_find(fd->bnode, fd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) hfs_brec_insert(fd, &cnid, sizeof(cnid));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) hfs_bnode_put(fd->bnode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) hfs_bnode_put(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) if (!rec) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) if (new_node == node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) /* restore search_key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) hfs_bnode_read_key(node, fd->search_key, 14);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) new_node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) if (!rec && node->parent)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) goto again;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) fd->bnode = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) static int hfs_btree_inc_height(struct hfs_btree *tree)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) struct hfs_bnode *node, *new_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) struct hfs_bnode_desc node_desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) int key_size, rec;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) __be32 cnid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) if (tree->root) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) node = hfs_bnode_find(tree, tree->root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) if (IS_ERR(node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) return PTR_ERR(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) new_node = hfs_bmap_alloc(tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) if (IS_ERR(new_node)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) return PTR_ERR(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) tree->root = new_node->this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) if (!tree->depth) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) tree->leaf_head = tree->leaf_tail = new_node->this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) new_node->type = HFS_NODE_LEAF;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) new_node->num_recs = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) new_node->type = HFS_NODE_INDEX;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) new_node->num_recs = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) new_node->parent = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) new_node->next = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) new_node->prev = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) new_node->height = ++tree->depth;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) node_desc.next = cpu_to_be32(new_node->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) node_desc.prev = cpu_to_be32(new_node->prev);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) node_desc.type = new_node->type;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) node_desc.height = new_node->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) node_desc.num_recs = cpu_to_be16(new_node->num_recs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) node_desc.reserved = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) rec = tree->node_size - 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) hfs_bnode_write_u16(new_node, rec, 14);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) if (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) /* insert old root idx into new root */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) node->parent = tree->root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) if (node->type == HFS_NODE_LEAF ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) tree->attributes & HFS_TREE_VARIDXKEYS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) key_size = hfs_bnode_read_u8(node, 14) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) key_size = tree->max_key_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) hfs_bnode_copy(new_node, 14, node, 14, key_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) key_size = tree->max_key_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) hfs_bnode_write_u8(new_node, 14, tree->max_key_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) key_size = (key_size + 1) & -2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) cnid = cpu_to_be32(node->this);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) hfs_bnode_write(new_node, &cnid, 14 + key_size, 4);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) rec -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) hfs_bnode_put(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) hfs_bnode_put(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) mark_inode_dirty(tree->inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags