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