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