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