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 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); 17 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) 20 { 21 __be16 retval[2]; 22 u16 dataoff; 23 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; 28 } 29 30 /* Get the length of the key from a keyed record */ 31 u16 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, 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, 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, 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 65 int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int 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, tree->leaf_head); 79 if (IS_ERR(node)) 80 return PTR_ERR(node); 81 fd->bnode = node; 82 fd->record = -1; 83 } 84 new_node = NULL; 85 key_len = (fd->search_key->key_len | 1) + 1; 86 again: 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, 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("not enough room!\n"); 102 new_node = hfs_bnode_split(fd); 103 if (IS_ERR(new_node)) 104 return PTR_ERR(new_node); 105 goto again; 106 } 107 if (node->type == HFS_NODE_LEAF) { 108 tree->leaf_count++; 109 mark_inode_dirty(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), node->num_recs); 114 hfs_bnode_write_u16(node, end_rec_off, 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, data_rec_off + 2); 123 hfs_bnode_write_u16(node, data_rec_off, 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, data_off + size, data_off, 129 end_off - data_off); 130 131 skip: 132 hfs_bnode_write(node, fd->search_key, data_off, key_len); 133 hfs_bnode_write(node, entry, data_off + key_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, fd->search_key, data_off + size); 142 hfs_brec_update_parent(fd); 143 } 144 145 if (new_node) { 146 hfs_bnode_put(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, 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(new_node, fd->search_key, 14); 160 __hfs_brec_find(fd->bnode, fd); 161 162 hfs_bnode_put(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 177 int 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; 186 again: 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(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, node->parent); 202 if (IS_ERR(parent)) 203 return PTR_ERR(parent); 204 hfs_bnode_put(node); 205 node = fd->bnode = parent; 206 207 __hfs_brec_find(node, fd); 208 goto again; 209 } 210 hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), 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, src, size); 217 goto skip; 218 } 219 220 do { 221 data_off = hfs_bnode_read_u16(node, rec_off); 222 hfs_bnode_write_u16(node, rec_off + 2, 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, src, len); 237 238 skip: 239 /* 240 * Remove the obsolete offset to free space. 241 */ 242 hfs_bnode_write_u16(node, end_off, 0); 243 244 hfs_bnode_dump(node); 245 if (!fd->record) 246 hfs_brec_update_parent(fd); 247 return 0; 248 } 249 250 static 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(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, node->next); 274 else 275 next_node = NULL; 276 277 if (IS_ERR(next_node)) { 278 hfs_bnode_put(node); 279 hfs_bnode_put(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, 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(new_node); 296 if (next_node) 297 hfs_bnode_put(next_node); 298 return ERR_PTR(-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, old_rec_off); 308 } else { 309 hfs_bnode_put(node); 310 hfs_bnode_get(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(new_node, new_rec_off, new_off); 326 old_rec_off -= 2; 327 new_rec_off -= 2; 328 data_end = hfs_bnode_read_u16(node, old_rec_off); 329 new_off = data_end - size; 330 num_recs--; 331 } 332 hfs_bnode_write_u16(new_node, new_rec_off, new_off); 333 hfs_bnode_copy(new_node, 14, node, data_start, 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(new_node, &node_desc, 0, sizeof(node_desc)); 343 344 /* update previous bnode header */ 345 node->next = new_node->this; 346 hfs_bnode_read(node, &node_desc, 0, 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, &node_desc, 0, sizeof(node_desc)); 350 351 /* update next bnode header */ 352 if (next_node) { 353 next_node->prev = new_node->this; 354 hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc)); 355 node_desc.prev = cpu_to_be32(next_node->prev); 356 hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc)); 357 hfs_bnode_put(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(tree->inode); 362 } 363 364 hfs_bnode_dump(node); 365 hfs_bnode_dump(new_node); 366 hfs_bnode_put(node); 367 368 return new_node; 369 } 370 371 static 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 385 again: 386 parent = hfs_bnode_find(tree, node->parent); 387 if (IS_ERR(parent)) 388 return PTR_ERR(parent); 389 __hfs_brec_find(parent, fd); 390 if (fd->record < 0) 391 return -ENOENT; 392 hfs_bnode_dump(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, 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(parent, 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(new_node)) 416 return PTR_ERR(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(parent, rec_off); 425 hfs_bnode_write_u16(parent, rec_off, 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(parent, rec_off); 431 hfs_bnode_write_u16(parent, rec_off, end_off + diff); 432 } 433 hfs_bnode_move(parent, start_off + diff, start_off, 434 end_off - start_off); 435 skip: 436 hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen); 437 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) 438 hfs_bnode_write_u8(parent, fd->keyoffset, newkeylen - 1); 439 hfs_bnode_dump(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, new_node->parent); 452 /* create index key and entry */ 453 hfs_bnode_read_key(new_node, fd->search_key, 14); 454 cnid = cpu_to_be32(new_node->this); 455 456 __hfs_brec_find(fd->bnode, fd); 457 hfs_brec_insert(fd, &cnid, sizeof(cnid)); 458 hfs_bnode_put(fd->bnode); 459 hfs_bnode_put(new_node); 460 461 if (!rec) { 462 if (new_node == node) 463 goto out; 464 /* restore search_key */ 465 hfs_bnode_read_key(node, fd->search_key, 14); 466 } 467 new_node = NULL; 468 } 469 470 if (!rec && node->parent) 471 goto again; 472 out: 473 fd->bnode = node; 474 return 0; 475 } 476 477 static 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, tree->root); 487 if (IS_ERR(node)) 488 return PTR_ERR(node); 489 } 490 new_node = hfs_bmap_alloc(tree); 491 if (IS_ERR(new_node)) { 492 hfs_bnode_put(node); 493 return PTR_ERR(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(new_node, &node_desc, 0, sizeof(node_desc)); 517 518 rec = tree->node_size - 2; 519 hfs_bnode_write_u16(new_node, rec, 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, 14) + 1; 527 else 528 key_size = tree->max_key_len + 1; 529 hfs_bnode_copy(new_node, 14, node, 14, key_size); 530 531 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { 532 key_size = tree->max_key_len + 1; 533 hfs_bnode_write_u8(new_node, 14, tree->max_key_len); 534 } 535 key_size = (key_size + 1) & -2; 536 cnid = cpu_to_be32(node->this); 537 hfs_bnode_write(new_node, &cnid, 14 + key_size, 4); 538 539 rec -= 2; 540 hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4); 541 542 hfs_bnode_put(node); 543 } 544 hfs_bnode_put(new_node); 545 mark_inode_dirty(tree->inode); 546 547 return 0; 548 } 549