Orange Pi5 kernel

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