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