1 // SPDX-License-Identifier: GPL-2.0
6 * Brad Boyer (flar@allandria.com)
7 * (C) 2003 Ardis Technologies <roman@ardistech.com>
9 * Handle individual btree records
14 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
);
15 static int hfs_brec_update_parent(struct hfs_find_data
*fd
);
16 static int hfs_btree_inc_height(struct hfs_btree
*tree
);
18 /* Get the length and offset of the given record in the given node */
19 u16
hfs_brec_lenoff(struct hfs_bnode
*node
, u16 rec
, u16
*off
)
24 dataoff
= node
->tree
->node_size
- (rec
+ 2) * 2;
25 hfs_bnode_read(node
, retval
, dataoff
, 4);
26 *off
= be16_to_cpu(retval
[1]);
27 return be16_to_cpu(retval
[0]) - *off
;
30 /* Get the length of the key from a keyed record */
31 u16
hfs_brec_keylen(struct hfs_bnode
*node
, u16 rec
)
35 if (node
->type
!= HFS_NODE_INDEX
&& node
->type
!= HFS_NODE_LEAF
)
38 if ((node
->type
== HFS_NODE_INDEX
) &&
39 !(node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
40 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
)
41 retval
= node
->tree
->max_key_len
+ 2;
43 retval
= node
->tree
->max_key_len
+ 1;
45 recoff
= hfs_bnode_read_u16(node
, node
->tree
->node_size
- (rec
+ 1) * 2);
48 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
) {
49 retval
= hfs_bnode_read_u16(node
, recoff
) + 2;
50 if (retval
> node
->tree
->max_key_len
+ 2) {
51 pr_err("keylen %d too large\n", retval
);
55 retval
= (hfs_bnode_read_u8(node
, recoff
) | 1) + 1;
56 if (retval
> node
->tree
->max_key_len
+ 1) {
57 pr_err("keylen %d too large\n", retval
);
65 int hfs_brec_insert(struct hfs_find_data
*fd
, void *entry
, int entry_len
)
67 struct hfs_btree
*tree
;
68 struct hfs_bnode
*node
, *new_node
;
69 int size
, key_len
, rec
;
70 int data_off
, end_off
;
71 int idx_rec_off
, data_rec_off
, end_rec_off
;
77 hfs_btree_inc_height(tree
);
78 fd
->bnode
= hfs_bnode_find(tree
, tree
->leaf_head
);
79 if (IS_ERR(fd
->bnode
))
80 return PTR_ERR(fd
->bnode
);
84 key_len
= (fd
->search_key
->key_len
| 1) + 1;
86 /* new record idx and complete record size */
88 size
= key_len
+ entry_len
;
93 end_rec_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
94 end_off
= hfs_bnode_read_u16(node
, end_rec_off
);
96 hfs_dbg(BNODE_MOD
, "insert_rec: %d, %d, %d, %d\n",
97 rec
, size
, end_off
, end_rec_off
);
98 if (size
> end_rec_off
- end_off
) {
100 panic("not enough room!\n");
101 new_node
= hfs_bnode_split(fd
);
102 if (IS_ERR(new_node
))
103 return PTR_ERR(new_node
);
106 if (node
->type
== HFS_NODE_LEAF
) {
108 mark_inode_dirty(tree
->inode
);
111 /* write new last offset */
112 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
113 hfs_bnode_write_u16(node
, end_rec_off
, end_off
+ size
);
115 data_rec_off
= end_rec_off
+ 2;
116 idx_rec_off
= tree
->node_size
- (rec
+ 1) * 2;
117 if (idx_rec_off
== data_rec_off
)
119 /* move all following entries */
121 data_off
= hfs_bnode_read_u16(node
, data_rec_off
+ 2);
122 hfs_bnode_write_u16(node
, data_rec_off
, data_off
+ size
);
124 } while (data_rec_off
< idx_rec_off
);
127 hfs_bnode_move(node
, data_off
+ size
, data_off
,
131 hfs_bnode_write(node
, fd
->search_key
, data_off
, key_len
);
132 hfs_bnode_write(node
, entry
, data_off
+ key_len
, entry_len
);
133 hfs_bnode_dump(node
);
136 * update parent key if we inserted a key
137 * at the start of the node and it is not the new node
139 if (!rec
&& new_node
!= node
) {
140 hfs_bnode_read_key(node
, fd
->search_key
, data_off
+ size
);
141 hfs_brec_update_parent(fd
);
145 hfs_bnode_put(fd
->bnode
);
146 if (!new_node
->parent
) {
147 hfs_btree_inc_height(tree
);
148 new_node
->parent
= tree
->root
;
150 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
152 /* create index data entry */
153 cnid
= cpu_to_be32(new_node
->this);
155 entry_len
= sizeof(cnid
);
158 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
159 __hfs_brec_find(fd
->bnode
, fd
);
161 hfs_bnode_put(new_node
);
164 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
165 key_len
= fd
->search_key
->key_len
+ 1;
167 fd
->search_key
->key_len
= tree
->max_key_len
;
168 key_len
= tree
->max_key_len
+ 1;
176 int hfs_brec_remove(struct hfs_find_data
*fd
)
178 struct hfs_btree
*tree
;
179 struct hfs_bnode
*node
, *parent
;
180 int end_off
, rec_off
, data_off
, size
;
185 rec_off
= tree
->node_size
- (fd
->record
+ 2) * 2;
186 end_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
188 if (node
->type
== HFS_NODE_LEAF
) {
190 mark_inode_dirty(tree
->inode
);
192 hfs_bnode_dump(node
);
193 hfs_dbg(BNODE_MOD
, "remove_rec: %d, %d\n",
194 fd
->record
, fd
->keylength
+ fd
->entrylength
);
195 if (!--node
->num_recs
) {
196 hfs_bnode_unlink(node
);
199 parent
= hfs_bnode_find(tree
, node
->parent
);
201 return PTR_ERR(parent
);
203 node
= fd
->bnode
= parent
;
205 __hfs_brec_find(node
, fd
);
208 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
210 if (rec_off
== end_off
)
212 size
= fd
->keylength
+ fd
->entrylength
;
215 data_off
= hfs_bnode_read_u16(node
, rec_off
);
216 hfs_bnode_write_u16(node
, rec_off
+ 2, data_off
- size
);
218 } while (rec_off
>= end_off
);
221 hfs_bnode_move(node
, fd
->keyoffset
, fd
->keyoffset
+ size
,
222 data_off
- fd
->keyoffset
- size
);
224 hfs_bnode_dump(node
);
226 hfs_brec_update_parent(fd
);
230 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
)
232 struct hfs_btree
*tree
;
233 struct hfs_bnode
*node
, *new_node
, *next_node
;
234 struct hfs_bnode_desc node_desc
;
235 int num_recs
, new_rec_off
, new_off
, old_rec_off
;
236 int data_start
, data_end
, size
;
240 new_node
= hfs_bmap_alloc(tree
);
241 if (IS_ERR(new_node
))
244 hfs_dbg(BNODE_MOD
, "split_nodes: %d - %d - %d\n",
245 node
->this, new_node
->this, node
->next
);
246 new_node
->next
= node
->next
;
247 new_node
->prev
= node
->this;
248 new_node
->parent
= node
->parent
;
249 new_node
->type
= node
->type
;
250 new_node
->height
= node
->height
;
253 next_node
= hfs_bnode_find(tree
, node
->next
);
257 if (IS_ERR(next_node
)) {
259 hfs_bnode_put(new_node
);
263 size
= tree
->node_size
/ 2 - node
->num_recs
* 2 - 14;
264 old_rec_off
= tree
->node_size
- 4;
267 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
268 if (data_start
> size
)
271 if (++num_recs
< node
->num_recs
)
275 hfs_bnode_put(new_node
);
277 hfs_bnode_put(next_node
);
278 return ERR_PTR(-ENOSPC
);
281 if (fd
->record
+ 1 < num_recs
) {
282 /* new record is in the lower half,
283 * so leave some more space there
287 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
290 hfs_bnode_get(new_node
);
291 fd
->bnode
= new_node
;
292 fd
->record
-= num_recs
;
293 fd
->keyoffset
-= data_start
- 14;
294 fd
->entryoffset
-= data_start
- 14;
296 new_node
->num_recs
= node
->num_recs
- num_recs
;
297 node
->num_recs
= num_recs
;
299 new_rec_off
= tree
->node_size
- 2;
301 size
= data_start
- new_off
;
302 num_recs
= new_node
->num_recs
;
303 data_end
= data_start
;
305 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
308 data_end
= hfs_bnode_read_u16(node
, old_rec_off
);
309 new_off
= data_end
- size
;
312 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
313 hfs_bnode_copy(new_node
, 14, node
, data_start
, data_end
- data_start
);
315 /* update new bnode header */
316 node_desc
.next
= cpu_to_be32(new_node
->next
);
317 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
318 node_desc
.type
= new_node
->type
;
319 node_desc
.height
= new_node
->height
;
320 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
321 node_desc
.reserved
= 0;
322 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
324 /* update previous bnode header */
325 node
->next
= new_node
->this;
326 hfs_bnode_read(node
, &node_desc
, 0, sizeof(node_desc
));
327 node_desc
.next
= cpu_to_be32(node
->next
);
328 node_desc
.num_recs
= cpu_to_be16(node
->num_recs
);
329 hfs_bnode_write(node
, &node_desc
, 0, sizeof(node_desc
));
331 /* update next bnode header */
333 next_node
->prev
= new_node
->this;
334 hfs_bnode_read(next_node
, &node_desc
, 0, sizeof(node_desc
));
335 node_desc
.prev
= cpu_to_be32(next_node
->prev
);
336 hfs_bnode_write(next_node
, &node_desc
, 0, sizeof(node_desc
));
337 hfs_bnode_put(next_node
);
338 } else if (node
->this == tree
->leaf_tail
) {
339 /* if there is no next node, this might be the new tail */
340 tree
->leaf_tail
= new_node
->this;
341 mark_inode_dirty(tree
->inode
);
344 hfs_bnode_dump(node
);
345 hfs_bnode_dump(new_node
);
351 static int hfs_brec_update_parent(struct hfs_find_data
*fd
)
353 struct hfs_btree
*tree
;
354 struct hfs_bnode
*node
, *new_node
, *parent
;
356 int rec
, rec_off
, end_rec_off
;
357 int start_off
, end_off
;
366 parent
= hfs_bnode_find(tree
, node
->parent
);
368 return PTR_ERR(parent
);
369 __hfs_brec_find(parent
, fd
);
372 hfs_bnode_dump(parent
);
375 /* size difference between old and new key */
376 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
377 newkeylen
= (hfs_bnode_read_u8(node
, 14) | 1) + 1;
379 fd
->keylength
= newkeylen
= tree
->max_key_len
+ 1;
380 hfs_dbg(BNODE_MOD
, "update_rec: %d, %d, %d\n",
381 rec
, fd
->keylength
, newkeylen
);
383 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
384 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
385 diff
= newkeylen
- fd
->keylength
;
389 end_off
= hfs_bnode_read_u16(parent
, end_rec_off
);
390 if (end_rec_off
- end_off
< diff
) {
392 printk(KERN_DEBUG
"splitting index node...\n");
394 new_node
= hfs_bnode_split(fd
);
395 if (IS_ERR(new_node
))
396 return PTR_ERR(new_node
);
399 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
400 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
404 end_off
= start_off
= hfs_bnode_read_u16(parent
, rec_off
);
405 hfs_bnode_write_u16(parent
, rec_off
, start_off
+ diff
);
406 start_off
-= 4; /* move previous cnid too */
408 while (rec_off
> end_rec_off
) {
410 end_off
= hfs_bnode_read_u16(parent
, rec_off
);
411 hfs_bnode_write_u16(parent
, rec_off
, end_off
+ diff
);
413 hfs_bnode_move(parent
, start_off
+ diff
, start_off
,
414 end_off
- start_off
);
416 hfs_bnode_copy(parent
, fd
->keyoffset
, node
, 14, newkeylen
);
417 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
))
418 hfs_bnode_write_u8(parent
, fd
->keyoffset
, newkeylen
- 1);
419 hfs_bnode_dump(parent
);
427 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
428 /* create index key and entry */
429 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
430 cnid
= cpu_to_be32(new_node
->this);
432 __hfs_brec_find(fd
->bnode
, fd
);
433 hfs_brec_insert(fd
, &cnid
, sizeof(cnid
));
434 hfs_bnode_put(fd
->bnode
);
435 hfs_bnode_put(new_node
);
438 if (new_node
== node
)
440 /* restore search_key */
441 hfs_bnode_read_key(node
, fd
->search_key
, 14);
445 if (!rec
&& node
->parent
)
452 static int hfs_btree_inc_height(struct hfs_btree
*tree
)
454 struct hfs_bnode
*node
, *new_node
;
455 struct hfs_bnode_desc node_desc
;
461 node
= hfs_bnode_find(tree
, tree
->root
);
463 return PTR_ERR(node
);
465 new_node
= hfs_bmap_alloc(tree
);
466 if (IS_ERR(new_node
)) {
468 return PTR_ERR(new_node
);
471 tree
->root
= new_node
->this;
473 tree
->leaf_head
= tree
->leaf_tail
= new_node
->this;
474 new_node
->type
= HFS_NODE_LEAF
;
475 new_node
->num_recs
= 0;
477 new_node
->type
= HFS_NODE_INDEX
;
478 new_node
->num_recs
= 1;
480 new_node
->parent
= 0;
483 new_node
->height
= ++tree
->depth
;
485 node_desc
.next
= cpu_to_be32(new_node
->next
);
486 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
487 node_desc
.type
= new_node
->type
;
488 node_desc
.height
= new_node
->height
;
489 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
490 node_desc
.reserved
= 0;
491 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
493 rec
= tree
->node_size
- 2;
494 hfs_bnode_write_u16(new_node
, rec
, 14);
497 /* insert old root idx into new root */
498 node
->parent
= tree
->root
;
499 if (node
->type
== HFS_NODE_LEAF
||
500 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
501 key_size
= hfs_bnode_read_u8(node
, 14) + 1;
503 key_size
= tree
->max_key_len
+ 1;
504 hfs_bnode_copy(new_node
, 14, node
, 14, key_size
);
506 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
507 key_size
= tree
->max_key_len
+ 1;
508 hfs_bnode_write_u8(new_node
, 14, tree
->max_key_len
);
510 key_size
= (key_size
+ 1) & -2;
511 cnid
= cpu_to_be32(node
->this);
512 hfs_bnode_write(new_node
, &cnid
, 14 + key_size
, 4);
515 hfs_bnode_write_u16(new_node
, rec
, 14 + key_size
+ 4);
519 hfs_bnode_put(new_node
);
520 mark_inode_dirty(tree
->inode
);