1 /* 2 * linux/fs/hfsplus/bnode.c 3 * 4 * Copyright (C) 2001 5 * Brad Boyer (flar@allandria.com) 6 * (C) 2003 Ardis Technologies <roman@ardistech.com> 7 * 8 * Handle basic btree node operations 9 */ 10 11 #include <linux/string.h> 12 #include <linux/slab.h> 13 #include <linux/pagemap.h> 14 #include <linux/fs.h> 15 #include <linux/swap.h> 16 #include <linux/version.h> 17 18 #include "hfsplus_fs.h" 19 #include "hfsplus_raw.h" 20 21 /* Copy a specified range of bytes from the raw data of a node */ 22 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len) 23 { 24 struct page **pagep; 25 int l; 26 27 off += node->page_offset; 28 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 29 off &= ~PAGE_CACHE_MASK; 30 31 l = min(len, (int)PAGE_CACHE_SIZE - off); 32 memcpy(buf, kmap(*pagep) + off, l); 33 kunmap(*pagep); 34 35 while ((len -= l) != 0) { 36 buf += l; 37 l = min(len, (int)PAGE_CACHE_SIZE); 38 memcpy(buf, kmap(*++pagep), l); 39 kunmap(*pagep); 40 } 41 } 42 43 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) 44 { 45 __be16 data; 46 // optimize later... 47 hfs_bnode_read(node, &data, off, 2); 48 return be16_to_cpu(data); 49 } 50 51 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) 52 { 53 u8 data; 54 // optimize later... 55 hfs_bnode_read(node, &data, off, 1); 56 return data; 57 } 58 59 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) 60 { 61 struct hfs_btree *tree; 62 int key_len; 63 64 tree = node->tree; 65 if (node->type == HFS_NODE_LEAF || 66 tree->attributes & HFS_TREE_VARIDXKEYS) 67 key_len = hfs_bnode_read_u16(node, off) + 2; 68 else 69 key_len = tree->max_key_len + 2; 70 71 hfs_bnode_read(node, key, off, key_len); 72 } 73 74 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) 75 { 76 struct page **pagep; 77 int l; 78 79 off += node->page_offset; 80 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 81 off &= ~PAGE_CACHE_MASK; 82 83 l = min(len, (int)PAGE_CACHE_SIZE - off); 84 memcpy(kmap(*pagep) + off, buf, l); 85 set_page_dirty(*pagep); 86 kunmap(*pagep); 87 88 while ((len -= l) != 0) { 89 buf += l; 90 l = min(len, (int)PAGE_CACHE_SIZE); 91 memcpy(kmap(*++pagep), buf, l); 92 set_page_dirty(*pagep); 93 kunmap(*pagep); 94 } 95 } 96 97 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) 98 { 99 __be16 v = cpu_to_be16(data); 100 // optimize later... 101 hfs_bnode_write(node, &v, off, 2); 102 } 103 104 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) 105 { 106 struct page **pagep; 107 int l; 108 109 off += node->page_offset; 110 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 111 off &= ~PAGE_CACHE_MASK; 112 113 l = min(len, (int)PAGE_CACHE_SIZE - off); 114 memset(kmap(*pagep) + off, 0, l); 115 set_page_dirty(*pagep); 116 kunmap(*pagep); 117 118 while ((len -= l) != 0) { 119 l = min(len, (int)PAGE_CACHE_SIZE); 120 memset(kmap(*++pagep), 0, l); 121 set_page_dirty(*pagep); 122 kunmap(*pagep); 123 } 124 } 125 126 void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst, 127 struct hfs_bnode *src_node, int src, int len) 128 { 129 struct hfs_btree *tree; 130 struct page **src_page, **dst_page; 131 int l; 132 133 dprint(DBG_BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len); 134 if (!len) 135 return; 136 tree = src_node->tree; 137 src += src_node->page_offset; 138 dst += dst_node->page_offset; 139 src_page = src_node->page + (src >> PAGE_CACHE_SHIFT); 140 src &= ~PAGE_CACHE_MASK; 141 dst_page = dst_node->page + (dst >> PAGE_CACHE_SHIFT); 142 dst &= ~PAGE_CACHE_MASK; 143 144 if (src == dst) { 145 l = min(len, (int)PAGE_CACHE_SIZE - src); 146 memcpy(kmap(*dst_page) + src, kmap(*src_page) + src, l); 147 kunmap(*src_page); 148 set_page_dirty(*dst_page); 149 kunmap(*dst_page); 150 151 while ((len -= l) != 0) { 152 l = min(len, (int)PAGE_CACHE_SIZE); 153 memcpy(kmap(*++dst_page), kmap(*++src_page), l); 154 kunmap(*src_page); 155 set_page_dirty(*dst_page); 156 kunmap(*dst_page); 157 } 158 } else { 159 void *src_ptr, *dst_ptr; 160 161 do { 162 src_ptr = kmap(*src_page) + src; 163 dst_ptr = kmap(*dst_page) + dst; 164 if (PAGE_CACHE_SIZE - src < PAGE_CACHE_SIZE - dst) { 165 l = PAGE_CACHE_SIZE - src; 166 src = 0; 167 dst += l; 168 } else { 169 l = PAGE_CACHE_SIZE - dst; 170 src += l; 171 dst = 0; 172 } 173 l = min(len, l); 174 memcpy(dst_ptr, src_ptr, l); 175 kunmap(*src_page); 176 set_page_dirty(*dst_page); 177 kunmap(*dst_page); 178 if (!dst) 179 dst_page++; 180 else 181 src_page++; 182 } while ((len -= l)); 183 } 184 } 185 186 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) 187 { 188 struct page **src_page, **dst_page; 189 int l; 190 191 dprint(DBG_BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len); 192 if (!len) 193 return; 194 src += node->page_offset; 195 dst += node->page_offset; 196 if (dst > src) { 197 src += len - 1; 198 src_page = node->page + (src >> PAGE_CACHE_SHIFT); 199 src = (src & ~PAGE_CACHE_MASK) + 1; 200 dst += len - 1; 201 dst_page = node->page + (dst >> PAGE_CACHE_SHIFT); 202 dst = (dst & ~PAGE_CACHE_MASK) + 1; 203 204 if (src == dst) { 205 while (src < len) { 206 memmove(kmap(*dst_page), kmap(*src_page), src); 207 kunmap(*src_page); 208 set_page_dirty(*dst_page); 209 kunmap(*dst_page); 210 len -= src; 211 src = PAGE_CACHE_SIZE; 212 src_page--; 213 dst_page--; 214 } 215 src -= len; 216 memmove(kmap(*dst_page) + src, kmap(*src_page) + src, len); 217 kunmap(*src_page); 218 set_page_dirty(*dst_page); 219 kunmap(*dst_page); 220 } else { 221 void *src_ptr, *dst_ptr; 222 223 do { 224 src_ptr = kmap(*src_page) + src; 225 dst_ptr = kmap(*dst_page) + dst; 226 if (src < dst) { 227 l = src; 228 src = PAGE_CACHE_SIZE; 229 dst -= l; 230 } else { 231 l = dst; 232 src -= l; 233 dst = PAGE_CACHE_SIZE; 234 } 235 l = min(len, l); 236 memmove(dst_ptr - l, src_ptr - l, l); 237 kunmap(*src_page); 238 set_page_dirty(*dst_page); 239 kunmap(*dst_page); 240 if (dst == PAGE_CACHE_SIZE) 241 dst_page--; 242 else 243 src_page--; 244 } while ((len -= l)); 245 } 246 } else { 247 src_page = node->page + (src >> PAGE_CACHE_SHIFT); 248 src &= ~PAGE_CACHE_MASK; 249 dst_page = node->page + (dst >> PAGE_CACHE_SHIFT); 250 dst &= ~PAGE_CACHE_MASK; 251 252 if (src == dst) { 253 l = min(len, (int)PAGE_CACHE_SIZE - src); 254 memmove(kmap(*dst_page) + src, kmap(*src_page) + src, l); 255 kunmap(*src_page); 256 set_page_dirty(*dst_page); 257 kunmap(*dst_page); 258 259 while ((len -= l) != 0) { 260 l = min(len, (int)PAGE_CACHE_SIZE); 261 memmove(kmap(*++dst_page), kmap(*++src_page), l); 262 kunmap(*src_page); 263 set_page_dirty(*dst_page); 264 kunmap(*dst_page); 265 } 266 } else { 267 void *src_ptr, *dst_ptr; 268 269 do { 270 src_ptr = kmap(*src_page) + src; 271 dst_ptr = kmap(*dst_page) + dst; 272 if (PAGE_CACHE_SIZE - src < PAGE_CACHE_SIZE - dst) { 273 l = PAGE_CACHE_SIZE - src; 274 src = 0; 275 dst += l; 276 } else { 277 l = PAGE_CACHE_SIZE - dst; 278 src += l; 279 dst = 0; 280 } 281 l = min(len, l); 282 memmove(dst_ptr, src_ptr, l); 283 kunmap(*src_page); 284 set_page_dirty(*dst_page); 285 kunmap(*dst_page); 286 if (!dst) 287 dst_page++; 288 else 289 src_page++; 290 } while ((len -= l)); 291 } 292 } 293 } 294 295 void hfs_bnode_dump(struct hfs_bnode *node) 296 { 297 struct hfs_bnode_desc desc; 298 __be32 cnid; 299 int i, off, key_off; 300 301 dprint(DBG_BNODE_MOD, "bnode: %d\n", node->this); 302 hfs_bnode_read(node, &desc, 0, sizeof(desc)); 303 dprint(DBG_BNODE_MOD, "%d, %d, %d, %d, %d\n", 304 be32_to_cpu(desc.next), be32_to_cpu(desc.prev), 305 desc.type, desc.height, be16_to_cpu(desc.num_recs)); 306 307 off = node->tree->node_size - 2; 308 for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) { 309 key_off = hfs_bnode_read_u16(node, off); 310 dprint(DBG_BNODE_MOD, " %d", key_off); 311 if (i && node->type == HFS_NODE_INDEX) { 312 int tmp; 313 314 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) 315 tmp = hfs_bnode_read_u16(node, key_off) + 2; 316 else 317 tmp = node->tree->max_key_len + 2; 318 dprint(DBG_BNODE_MOD, " (%d", tmp); 319 hfs_bnode_read(node, &cnid, key_off + tmp, 4); 320 dprint(DBG_BNODE_MOD, ",%d)", be32_to_cpu(cnid)); 321 } else if (i && node->type == HFS_NODE_LEAF) { 322 int tmp; 323 324 tmp = hfs_bnode_read_u16(node, key_off); 325 dprint(DBG_BNODE_MOD, " (%d)", tmp); 326 } 327 } 328 dprint(DBG_BNODE_MOD, "\n"); 329 } 330 331 void hfs_bnode_unlink(struct hfs_bnode *node) 332 { 333 struct hfs_btree *tree; 334 struct hfs_bnode *tmp; 335 __be32 cnid; 336 337 tree = node->tree; 338 if (node->prev) { 339 tmp = hfs_bnode_find(tree, node->prev); 340 if (IS_ERR(tmp)) 341 return; 342 tmp->next = node->next; 343 cnid = cpu_to_be32(tmp->next); 344 hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 345 hfs_bnode_put(tmp); 346 } else if (node->type == HFS_NODE_LEAF) 347 tree->leaf_head = node->next; 348 349 if (node->next) { 350 tmp = hfs_bnode_find(tree, node->next); 351 if (IS_ERR(tmp)) 352 return; 353 tmp->prev = node->prev; 354 cnid = cpu_to_be32(tmp->prev); 355 hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, prev), 4); 356 hfs_bnode_put(tmp); 357 } else if (node->type == HFS_NODE_LEAF) 358 tree->leaf_tail = node->prev; 359 360 // move down? 361 if (!node->prev && !node->next) { 362 printk("hfs_btree_del_level\n"); 363 } 364 if (!node->parent) { 365 tree->root = 0; 366 tree->depth = 0; 367 } 368 set_bit(HFS_BNODE_DELETED, &node->flags); 369 } 370 371 static inline int hfs_bnode_hash(u32 num) 372 { 373 num = (num >> 16) + num; 374 num += num >> 8; 375 return num & (NODE_HASH_SIZE - 1); 376 } 377 378 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) 379 { 380 struct hfs_bnode *node; 381 382 if (cnid >= tree->node_count) { 383 printk("HFS+-fs: request for non-existent node %d in B*Tree\n", cnid); 384 return NULL; 385 } 386 387 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; 388 node; node = node->next_hash) { 389 if (node->this == cnid) { 390 return node; 391 } 392 } 393 return NULL; 394 } 395 396 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) 397 { 398 struct super_block *sb; 399 struct hfs_bnode *node, *node2; 400 struct address_space *mapping; 401 struct page *page; 402 int size, block, i, hash; 403 loff_t off; 404 405 if (cnid >= tree->node_count) { 406 printk("HFS+-fs: request for non-existent node %d in B*Tree\n", cnid); 407 return NULL; 408 } 409 410 sb = tree->inode->i_sb; 411 size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * 412 sizeof(struct page *); 413 node = kmalloc(size, GFP_KERNEL); 414 if (!node) 415 return NULL; 416 memset(node, 0, size); 417 node->tree = tree; 418 node->this = cnid; 419 set_bit(HFS_BNODE_NEW, &node->flags); 420 atomic_set(&node->refcnt, 1); 421 dprint(DBG_BNODE_REFS, "new_node(%d:%d): 1\n", 422 node->tree->cnid, node->this); 423 init_waitqueue_head(&node->lock_wq); 424 spin_lock(&tree->hash_lock); 425 node2 = hfs_bnode_findhash(tree, cnid); 426 if (!node2) { 427 hash = hfs_bnode_hash(cnid); 428 node->next_hash = tree->node_hash[hash]; 429 tree->node_hash[hash] = node; 430 tree->node_hash_cnt++; 431 } else { 432 spin_unlock(&tree->hash_lock); 433 kfree(node); 434 wait_event(node2->lock_wq, !test_bit(HFS_BNODE_NEW, &node2->flags)); 435 return node2; 436 } 437 spin_unlock(&tree->hash_lock); 438 439 mapping = tree->inode->i_mapping; 440 off = (loff_t)cnid << tree->node_size_shift; 441 block = off >> PAGE_CACHE_SHIFT; 442 node->page_offset = off & ~PAGE_CACHE_MASK; 443 for (i = 0; i < tree->pages_per_bnode; block++, i++) { 444 page = read_cache_page(mapping, block, (filler_t *)mapping->a_ops->readpage, NULL); 445 if (IS_ERR(page)) 446 goto fail; 447 if (PageError(page)) { 448 page_cache_release(page); 449 goto fail; 450 } 451 page_cache_release(page); 452 node->page[i] = page; 453 } 454 455 return node; 456 fail: 457 set_bit(HFS_BNODE_ERROR, &node->flags); 458 return node; 459 } 460 461 void hfs_bnode_unhash(struct hfs_bnode *node) 462 { 463 struct hfs_bnode **p; 464 465 dprint(DBG_BNODE_REFS, "remove_node(%d:%d): %d\n", 466 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 467 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; 468 *p && *p != node; p = &(*p)->next_hash) 469 ; 470 if (!*p) 471 BUG(); 472 *p = node->next_hash; 473 node->tree->node_hash_cnt--; 474 } 475 476 /* Load a particular node out of a tree */ 477 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) 478 { 479 struct hfs_bnode *node; 480 struct hfs_bnode_desc *desc; 481 int i, rec_off, off, next_off; 482 int entry_size, key_size; 483 484 spin_lock(&tree->hash_lock); 485 node = hfs_bnode_findhash(tree, num); 486 if (node) { 487 hfs_bnode_get(node); 488 spin_unlock(&tree->hash_lock); 489 wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags)); 490 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 491 goto node_error; 492 return node; 493 } 494 spin_unlock(&tree->hash_lock); 495 node = __hfs_bnode_create(tree, num); 496 if (!node) 497 return ERR_PTR(-ENOMEM); 498 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 499 goto node_error; 500 if (!test_bit(HFS_BNODE_NEW, &node->flags)) 501 return node; 502 503 desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset); 504 node->prev = be32_to_cpu(desc->prev); 505 node->next = be32_to_cpu(desc->next); 506 node->num_recs = be16_to_cpu(desc->num_recs); 507 node->type = desc->type; 508 node->height = desc->height; 509 kunmap(node->page[0]); 510 511 switch (node->type) { 512 case HFS_NODE_HEADER: 513 case HFS_NODE_MAP: 514 if (node->height != 0) 515 goto node_error; 516 break; 517 case HFS_NODE_LEAF: 518 if (node->height != 1) 519 goto node_error; 520 break; 521 case HFS_NODE_INDEX: 522 if (node->height <= 1 || node->height > tree->depth) 523 goto node_error; 524 break; 525 default: 526 goto node_error; 527 } 528 529 rec_off = tree->node_size - 2; 530 off = hfs_bnode_read_u16(node, rec_off); 531 if (off != sizeof(struct hfs_bnode_desc)) 532 goto node_error; 533 for (i = 1; i <= node->num_recs; off = next_off, i++) { 534 rec_off -= 2; 535 next_off = hfs_bnode_read_u16(node, rec_off); 536 if (next_off <= off || 537 next_off > tree->node_size || 538 next_off & 1) 539 goto node_error; 540 entry_size = next_off - off; 541 if (node->type != HFS_NODE_INDEX && 542 node->type != HFS_NODE_LEAF) 543 continue; 544 key_size = hfs_bnode_read_u16(node, off) + 2; 545 if (key_size >= entry_size || key_size & 1) 546 goto node_error; 547 } 548 clear_bit(HFS_BNODE_NEW, &node->flags); 549 wake_up(&node->lock_wq); 550 return node; 551 552 node_error: 553 set_bit(HFS_BNODE_ERROR, &node->flags); 554 clear_bit(HFS_BNODE_NEW, &node->flags); 555 wake_up(&node->lock_wq); 556 hfs_bnode_put(node); 557 return ERR_PTR(-EIO); 558 } 559 560 void hfs_bnode_free(struct hfs_bnode *node) 561 { 562 //int i; 563 564 //for (i = 0; i < node->tree->pages_per_bnode; i++) 565 // if (node->page[i]) 566 // page_cache_release(node->page[i]); 567 kfree(node); 568 } 569 570 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) 571 { 572 struct hfs_bnode *node; 573 struct page **pagep; 574 int i; 575 576 spin_lock(&tree->hash_lock); 577 node = hfs_bnode_findhash(tree, num); 578 spin_unlock(&tree->hash_lock); 579 if (node) { 580 printk("new node %u already hashed?\n", num); 581 BUG(); 582 } 583 node = __hfs_bnode_create(tree, num); 584 if (!node) 585 return ERR_PTR(-ENOMEM); 586 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { 587 hfs_bnode_put(node); 588 return ERR_PTR(-EIO); 589 } 590 591 pagep = node->page; 592 memset(kmap(*pagep) + node->page_offset, 0, 593 min((int)PAGE_CACHE_SIZE, (int)tree->node_size)); 594 set_page_dirty(*pagep); 595 kunmap(*pagep); 596 for (i = 1; i < tree->pages_per_bnode; i++) { 597 memset(kmap(*++pagep), 0, PAGE_CACHE_SIZE); 598 set_page_dirty(*pagep); 599 kunmap(*pagep); 600 } 601 clear_bit(HFS_BNODE_NEW, &node->flags); 602 wake_up(&node->lock_wq); 603 604 return node; 605 } 606 607 void hfs_bnode_get(struct hfs_bnode *node) 608 { 609 if (node) { 610 atomic_inc(&node->refcnt); 611 dprint(DBG_BNODE_REFS, "get_node(%d:%d): %d\n", 612 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 613 } 614 } 615 616 /* Dispose of resources used by a node */ 617 void hfs_bnode_put(struct hfs_bnode *node) 618 { 619 if (node) { 620 struct hfs_btree *tree = node->tree; 621 int i; 622 623 dprint(DBG_BNODE_REFS, "put_node(%d:%d): %d\n", 624 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 625 if (!atomic_read(&node->refcnt)) 626 BUG(); 627 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) 628 return; 629 for (i = 0; i < tree->pages_per_bnode; i++) { 630 if (!node->page[i]) 631 continue; 632 mark_page_accessed(node->page[i]); 633 } 634 635 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { 636 hfs_bnode_unhash(node); 637 spin_unlock(&tree->hash_lock); 638 hfs_bmap_free(node); 639 hfs_bnode_free(node); 640 return; 641 } 642 spin_unlock(&tree->hash_lock); 643 } 644 } 645 646