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

source code of linux/fs/hfs/brec.c