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