1 /* 2 * linux/fs/hfs/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 "btree.h" 12 13 static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd); 14 static int hfs_brec_update_parent(struct hfs_find_data *fd); 15 static int hfs_btree_inc_height(struct hfs_btree *tree); 16 17 /* Get the length and offset of the given record in the given node */ 18 u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) 19 { 20 __be16 retval[2]; 21 u16 dataoff; 22 23 dataoff = node->tree->node_size - (rec + 2) * 2; 24 hfs_bnode_read(node, retval, dataoff, 4); 25 *off = be16_to_cpu(retval[1]); 26 return be16_to_cpu(retval[0]) - *off; 27 } 28 29 /* Get the length of the key from a keyed record */ 30 u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) 31 { 32 u16 retval, recoff; 33 34 if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF) 35 return 0; 36 37 if ((node->type == HFS_NODE_INDEX) && 38 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { 39 if (node->tree->attributes & HFS_TREE_BIGKEYS) 40 retval = node->tree->max_key_len + 2; 41 else 42 retval = node->tree->max_key_len + 1; 43 } else { 44 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); 45 if (!recoff) 46 return 0; 47 if (node->tree->attributes & HFS_TREE_BIGKEYS) 48 retval = hfs_bnode_read_u16(node, recoff) + 2; 49 else 50 retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1; 51 } 52 return retval; 53 } 54 55 int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int entry_len) 56 { 57 struct hfs_btree *tree; 58 struct hfs_bnode *node, *new_node; 59 int size, key_len, rec; 60 int data_off, end_off; 61 int idx_rec_off, data_rec_off, end_rec_off; 62 __be32 cnid; 63 64 tree = fd->tree; 65 if (!fd->bnode) { 66 if (!tree->root) 67 hfs_btree_inc_height(tree); 68 fd->bnode = hfs_bnode_find(tree, tree->leaf_head); 69 if (IS_ERR(fd->bnode)) 70 return PTR_ERR(fd->bnode); 71 fd->record = -1; 72 } 73 new_node = NULL; 74 key_len = (fd->search_key->key_len | 1) + 1; 75 again: 76 /* new record idx and complete record size */ 77 rec = fd->record + 1; 78 size = key_len + entry_len; 79 80 node = fd->bnode; 81 hfs_bnode_dump(node); 82 /* get last offset */ 83 end_rec_off = tree->node_size - (node->num_recs + 1) * 2; 84 end_off = hfs_bnode_read_u16(node, end_rec_off); 85 end_rec_off -= 2; 86 dprint(DBG_BNODE_MOD, "insert_rec: %d, %d, %d, %d\n", rec, size, end_off, end_rec_off); 87 if (size > end_rec_off - end_off) { 88 if (new_node) 89 panic("not enough room!\n"); 90 new_node = hfs_bnode_split(fd); 91 if (IS_ERR(new_node)) 92 return PTR_ERR(new_node); 93 goto again; 94 } 95 if (node->type == HFS_NODE_LEAF) { 96 tree->leaf_count++; 97 mark_inode_dirty(tree->inode); 98 } 99 node->num_recs++; 100 /* write new last offset */ 101 hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs); 102 hfs_bnode_write_u16(node, end_rec_off, end_off + size); 103 data_off = end_off; 104 data_rec_off = end_rec_off + 2; 105 idx_rec_off = tree->node_size - (rec + 1) * 2; 106 if (idx_rec_off == data_rec_off) 107 goto skip; 108 /* move all following entries */ 109 do { 110 data_off = hfs_bnode_read_u16(node, data_rec_off + 2); 111 hfs_bnode_write_u16(node, data_rec_off, data_off + size); 112 data_rec_off += 2; 113 } while (data_rec_off < idx_rec_off); 114 115 /* move data away */ 116 hfs_bnode_move(node, data_off + size, data_off, 117 end_off - data_off); 118 119 skip: 120 hfs_bnode_write(node, fd->search_key, data_off, key_len); 121 hfs_bnode_write(node, entry, data_off + key_len, entry_len); 122 hfs_bnode_dump(node); 123 124 if (new_node) { 125 /* update parent key if we inserted a key 126 * at the start of the first node 127 */ 128 if (!rec && new_node != node) 129 hfs_brec_update_parent(fd); 130 131 hfs_bnode_put(fd->bnode); 132 if (!new_node->parent) { 133 hfs_btree_inc_height(tree); 134 new_node->parent = tree->root; 135 } 136 fd->bnode = hfs_bnode_find(tree, new_node->parent); 137 138 /* create index data entry */ 139 cnid = cpu_to_be32(new_node->this); 140 entry = &cnid; 141 entry_len = sizeof(cnid); 142 143 /* get index key */ 144 hfs_bnode_read_key(new_node, fd->search_key, 14); 145 __hfs_brec_find(fd->bnode, fd); 146 147 hfs_bnode_put(new_node); 148 new_node = NULL; 149 150 if (tree->attributes & HFS_TREE_VARIDXKEYS) 151 key_len = fd->search_key->key_len + 1; 152 else { 153 fd->search_key->key_len = tree->max_key_len; 154 key_len = tree->max_key_len + 1; 155 } 156 goto again; 157 } 158 159 if (!rec) 160 hfs_brec_update_parent(fd); 161 162 return 0; 163 } 164 165 int hfs_brec_remove(struct hfs_find_data *fd) 166 { 167 struct hfs_btree *tree; 168 struct hfs_bnode *node, *parent; 169 int end_off, rec_off, data_off, size; 170 171 tree = fd->tree; 172 node = fd->bnode; 173 again: 174 rec_off = tree->node_size - (fd->record + 2) * 2; 175 end_off = tree->node_size - (node->num_recs + 1) * 2; 176 177 if (node->type == HFS_NODE_LEAF) { 178 tree->leaf_count--; 179 mark_inode_dirty(tree->inode); 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(node); 185 if (!node->parent) 186 return 0; 187 parent = hfs_bnode_find(tree, node->parent); 188 if (IS_ERR(parent)) 189 return PTR_ERR(parent); 190 hfs_bnode_put(node); 191 node = fd->bnode = parent; 192 193 __hfs_brec_find(node, fd); 194 goto again; 195 } 196 hfs_bnode_write_u16(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(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(node, fd->keyoffset, fd->keyoffset + size, 210 data_off - fd->keyoffset - size); 211 skip: 212 hfs_bnode_dump(node); 213 if (!fd->record) 214 hfs_brec_update_parent(fd); 215 return 0; 216 } 217 218 static struct hfs_bnode *hfs_bnode_split(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(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(node); 252 hfs_bnode_put(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(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(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(new_node, new_rec_off, new_off); 288 hfs_bnode_copy(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(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(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(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(next_node, &node_desc, 0, sizeof(node_desc)); 313 hfs_bnode_put(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 mark_inode_dirty(tree->inode); 318 } 319 320 hfs_bnode_dump(node); 321 hfs_bnode_dump(new_node); 322 hfs_bnode_put(node); 323 324 return new_node; 325 } 326 327 static int hfs_brec_update_parent(struct hfs_find_data *fd) 328 { 329 struct hfs_btree *tree; 330 struct hfs_bnode *node, *new_node, *parent; 331 int newkeylen, diff; 332 int rec, rec_off, end_rec_off; 333 int start_off, end_off; 334 335 tree = fd->tree; 336 node = fd->bnode; 337 new_node = NULL; 338 if (!node->parent) 339 return 0; 340 341 again: 342 parent = hfs_bnode_find(tree, node->parent); 343 if (IS_ERR(parent)) 344 return PTR_ERR(parent); 345 __hfs_brec_find(parent, fd); 346 hfs_bnode_dump(parent); 347 rec = fd->record; 348 349 /* size difference between old and new key */ 350 if (tree->attributes & HFS_TREE_VARIDXKEYS) 351 newkeylen = (hfs_bnode_read_u8(node, 14) | 1) + 1; 352 else 353 fd->keylength = newkeylen = tree->max_key_len + 1; 354 dprint(DBG_BNODE_MOD, "update_rec: %d, %d, %d\n", rec, fd->keylength, newkeylen); 355 356 rec_off = tree->node_size - (rec + 2) * 2; 357 end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; 358 diff = newkeylen - fd->keylength; 359 if (!diff) 360 goto skip; 361 if (diff > 0) { 362 end_off = hfs_bnode_read_u16(parent, end_rec_off); 363 if (end_rec_off - end_off < diff) { 364 365 printk(KERN_DEBUG "hfs: splitting index node...\n"); 366 fd->bnode = parent; 367 new_node = hfs_bnode_split(fd); 368 if (IS_ERR(new_node)) 369 return PTR_ERR(new_node); 370 parent = fd->bnode; 371 rec = fd->record; 372 rec_off = tree->node_size - (rec + 2) * 2; 373 end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; 374 } 375 } 376 377 end_off = start_off = hfs_bnode_read_u16(parent, rec_off); 378 hfs_bnode_write_u16(parent, rec_off, start_off + diff); 379 start_off -= 4; /* move previous cnid too */ 380 381 while (rec_off > end_rec_off) { 382 rec_off -= 2; 383 end_off = hfs_bnode_read_u16(parent, rec_off); 384 hfs_bnode_write_u16(parent, rec_off, end_off + diff); 385 } 386 hfs_bnode_move(parent, start_off + diff, start_off, 387 end_off - start_off); 388 skip: 389 hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen); 390 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) 391 hfs_bnode_write_u8(parent, fd->keyoffset, newkeylen - 1); 392 hfs_bnode_dump(parent); 393 394 hfs_bnode_put(node); 395 node = parent; 396 397 if (new_node) { 398 __be32 cnid; 399 400 fd->bnode = hfs_bnode_find(tree, new_node->parent); 401 /* create index key and entry */ 402 hfs_bnode_read_key(new_node, fd->search_key, 14); 403 cnid = cpu_to_be32(new_node->this); 404 405 __hfs_brec_find(fd->bnode, fd); 406 hfs_brec_insert(fd, &cnid, sizeof(cnid)); 407 hfs_bnode_put(fd->bnode); 408 hfs_bnode_put(new_node); 409 410 if (!rec) { 411 if (new_node == node) 412 goto out; 413 /* restore search_key */ 414 hfs_bnode_read_key(node, fd->search_key, 14); 415 } 416 } 417 418 if (!rec && node->parent) 419 goto again; 420 out: 421 fd->bnode = node; 422 return 0; 423 } 424 425 static int hfs_btree_inc_height(struct hfs_btree *tree) 426 { 427 struct hfs_bnode *node, *new_node; 428 struct hfs_bnode_desc node_desc; 429 int key_size, rec; 430 __be32 cnid; 431 432 node = NULL; 433 if (tree->root) { 434 node = hfs_bnode_find(tree, tree->root); 435 if (IS_ERR(node)) 436 return PTR_ERR(node); 437 } 438 new_node = hfs_bmap_alloc(tree); 439 if (IS_ERR(new_node)) { 440 hfs_bnode_put(node); 441 return PTR_ERR(new_node); 442 } 443 444 tree->root = new_node->this; 445 if (!tree->depth) { 446 tree->leaf_head = tree->leaf_tail = new_node->this; 447 new_node->type = HFS_NODE_LEAF; 448 new_node->num_recs = 0; 449 } else { 450 new_node->type = HFS_NODE_INDEX; 451 new_node->num_recs = 1; 452 } 453 new_node->parent = 0; 454 new_node->next = 0; 455 new_node->prev = 0; 456 new_node->height = ++tree->depth; 457 458 node_desc.next = cpu_to_be32(new_node->next); 459 node_desc.prev = cpu_to_be32(new_node->prev); 460 node_desc.type = new_node->type; 461 node_desc.height = new_node->height; 462 node_desc.num_recs = cpu_to_be16(new_node->num_recs); 463 node_desc.reserved = 0; 464 hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc)); 465 466 rec = tree->node_size - 2; 467 hfs_bnode_write_u16(new_node, rec, 14); 468 469 if (node) { 470 /* insert old root idx into new root */ 471 node->parent = tree->root; 472 if (node->type == HFS_NODE_LEAF || 473 tree->attributes & HFS_TREE_VARIDXKEYS) 474 key_size = hfs_bnode_read_u8(node, 14) + 1; 475 else 476 key_size = tree->max_key_len + 1; 477 hfs_bnode_copy(new_node, 14, node, 14, key_size); 478 479 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { 480 key_size = tree->max_key_len + 1; 481 hfs_bnode_write_u8(new_node, 14, tree->max_key_len); 482 } 483 key_size = (key_size + 1) & -2; 484 cnid = cpu_to_be32(node->this); 485 hfs_bnode_write(new_node, &cnid, 14 + key_size, 4); 486 487 rec -= 2; 488 hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4); 489 490 hfs_bnode_put(node); 491 } 492 hfs_bnode_put(new_node); 493 mark_inode_dirty(tree->inode); 494 495 return 0; 496 } 497