projects/linux·blob master · refs

563 lines · 14.3 KiB

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