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 17 #include "hfsplus_fs.h" 18 #include "hfsplus_raw.h" 19 20 /* Copy a specified range of bytes from the raw data of a node */ 21 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len) 22 { 23 struct page **pagep; 24 int l; 25 26 off += node->page_offset; 27 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 28 off &= ~PAGE_CACHE_MASK; 29 30 l = min_t(int, len, PAGE_CACHE_SIZE - off); 31 memcpy(buf, kmap(*pagep) + off, l); 32 kunmap(*pagep); 33 34 while ((len -= l) != 0) { 35 buf += l; 36 l = min_t(int, len, PAGE_CACHE_SIZE); 37 memcpy(buf, kmap(*++pagep), l); 38 kunmap(*pagep); 39 } 40 } 41 42 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) 43 { 44 __be16 data; 45 /* TODO: optimize later... */ 46 hfs_bnode_read(node, &data, off, 2); 47 return be16_to_cpu(data); 48 } 49 50 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) 51 { 52 u8 data; 53 /* TODO: optimize later... */ 54 hfs_bnode_read(node, &data, off, 1); 55 return data; 56 } 57 58 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) 59 { 60 struct hfs_btree *tree; 61 int key_len; 62 63 tree = node->tree; 64 if (node->type == HFS_NODE_LEAF || 65 tree->attributes & HFS_TREE_VARIDXKEYS || 66 node->tree->cnid == HFSPLUS_ATTR_CNID) 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_t(int, len, 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_t(int, len, 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 /* TODO: 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_t(int, len, 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_t(int, len, 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 hfs_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_t(int, len, 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_t(int, len, 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 hfs_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, 217 kmap(*src_page) + src, len); 218 kunmap(*src_page); 219 set_page_dirty(*dst_page); 220 kunmap(*dst_page); 221 } else { 222 void *src_ptr, *dst_ptr; 223 224 do { 225 src_ptr = kmap(*src_page) + src; 226 dst_ptr = kmap(*dst_page) + dst; 227 if (src < dst) { 228 l = src; 229 src = PAGE_CACHE_SIZE; 230 dst -= l; 231 } else { 232 l = dst; 233 src -= l; 234 dst = PAGE_CACHE_SIZE; 235 } 236 l = min(len, l); 237 memmove(dst_ptr - l, src_ptr - l, l); 238 kunmap(*src_page); 239 set_page_dirty(*dst_page); 240 kunmap(*dst_page); 241 if (dst == PAGE_CACHE_SIZE) 242 dst_page--; 243 else 244 src_page--; 245 } while ((len -= l)); 246 } 247 } else { 248 src_page = node->page + (src >> PAGE_CACHE_SHIFT); 249 src &= ~PAGE_CACHE_MASK; 250 dst_page = node->page + (dst >> PAGE_CACHE_SHIFT); 251 dst &= ~PAGE_CACHE_MASK; 252 253 if (src == dst) { 254 l = min_t(int, len, PAGE_CACHE_SIZE - src); 255 memmove(kmap(*dst_page) + src, 256 kmap(*src_page) + src, l); 257 kunmap(*src_page); 258 set_page_dirty(*dst_page); 259 kunmap(*dst_page); 260 261 while ((len -= l) != 0) { 262 l = min_t(int, len, PAGE_CACHE_SIZE); 263 memmove(kmap(*++dst_page), 264 kmap(*++src_page), l); 265 kunmap(*src_page); 266 set_page_dirty(*dst_page); 267 kunmap(*dst_page); 268 } 269 } else { 270 void *src_ptr, *dst_ptr; 271 272 do { 273 src_ptr = kmap(*src_page) + src; 274 dst_ptr = kmap(*dst_page) + dst; 275 if (PAGE_CACHE_SIZE - src < 276 PAGE_CACHE_SIZE - dst) { 277 l = PAGE_CACHE_SIZE - src; 278 src = 0; 279 dst += l; 280 } else { 281 l = PAGE_CACHE_SIZE - dst; 282 src += l; 283 dst = 0; 284 } 285 l = min(len, l); 286 memmove(dst_ptr, src_ptr, l); 287 kunmap(*src_page); 288 set_page_dirty(*dst_page); 289 kunmap(*dst_page); 290 if (!dst) 291 dst_page++; 292 else 293 src_page++; 294 } while ((len -= l)); 295 } 296 } 297 } 298 299 void hfs_bnode_dump(struct hfs_bnode *node) 300 { 301 struct hfs_bnode_desc desc; 302 __be32 cnid; 303 int i, off, key_off; 304 305 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this); 306 hfs_bnode_read(node, &desc, 0, sizeof(desc)); 307 hfs_dbg(BNODE_MOD, "%d, %d, %d, %d, %d\n", 308 be32_to_cpu(desc.next), be32_to_cpu(desc.prev), 309 desc.type, desc.height, be16_to_cpu(desc.num_recs)); 310 311 off = node->tree->node_size - 2; 312 for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) { 313 key_off = hfs_bnode_read_u16(node, off); 314 hfs_dbg(BNODE_MOD, " %d", key_off); 315 if (i && node->type == HFS_NODE_INDEX) { 316 int tmp; 317 318 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || 319 node->tree->cnid == HFSPLUS_ATTR_CNID) 320 tmp = hfs_bnode_read_u16(node, key_off) + 2; 321 else 322 tmp = node->tree->max_key_len + 2; 323 hfs_dbg_cont(BNODE_MOD, " (%d", tmp); 324 hfs_bnode_read(node, &cnid, key_off + tmp, 4); 325 hfs_dbg_cont(BNODE_MOD, ",%d)", be32_to_cpu(cnid)); 326 } else if (i && node->type == HFS_NODE_LEAF) { 327 int tmp; 328 329 tmp = hfs_bnode_read_u16(node, key_off); 330 hfs_dbg_cont(BNODE_MOD, " (%d)", tmp); 331 } 332 } 333 hfs_dbg_cont(BNODE_MOD, "\n"); 334 } 335 336 void hfs_bnode_unlink(struct hfs_bnode *node) 337 { 338 struct hfs_btree *tree; 339 struct hfs_bnode *tmp; 340 __be32 cnid; 341 342 tree = node->tree; 343 if (node->prev) { 344 tmp = hfs_bnode_find(tree, node->prev); 345 if (IS_ERR(tmp)) 346 return; 347 tmp->next = node->next; 348 cnid = cpu_to_be32(tmp->next); 349 hfs_bnode_write(tmp, &cnid, 350 offsetof(struct hfs_bnode_desc, next), 4); 351 hfs_bnode_put(tmp); 352 } else if (node->type == HFS_NODE_LEAF) 353 tree->leaf_head = node->next; 354 355 if (node->next) { 356 tmp = hfs_bnode_find(tree, node->next); 357 if (IS_ERR(tmp)) 358 return; 359 tmp->prev = node->prev; 360 cnid = cpu_to_be32(tmp->prev); 361 hfs_bnode_write(tmp, &cnid, 362 offsetof(struct hfs_bnode_desc, prev), 4); 363 hfs_bnode_put(tmp); 364 } else if (node->type == HFS_NODE_LEAF) 365 tree->leaf_tail = node->prev; 366 367 /* move down? */ 368 if (!node->prev && !node->next) 369 hfs_dbg(BNODE_MOD, "hfs_btree_del_level\n"); 370 if (!node->parent) { 371 tree->root = 0; 372 tree->depth = 0; 373 } 374 set_bit(HFS_BNODE_DELETED, &node->flags); 375 } 376 377 static inline int hfs_bnode_hash(u32 num) 378 { 379 num = (num >> 16) + num; 380 num += num >> 8; 381 return num & (NODE_HASH_SIZE - 1); 382 } 383 384 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) 385 { 386 struct hfs_bnode *node; 387 388 if (cnid >= tree->node_count) { 389 pr_err("request for non-existent node %d in B*Tree\n", 390 cnid); 391 return NULL; 392 } 393 394 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; 395 node; node = node->next_hash) 396 if (node->this == cnid) 397 return node; 398 return NULL; 399 } 400 401 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) 402 { 403 struct super_block *sb; 404 struct hfs_bnode *node, *node2; 405 struct address_space *mapping; 406 struct page *page; 407 int size, block, i, hash; 408 loff_t off; 409 410 if (cnid >= tree->node_count) { 411 pr_err("request for non-existent node %d in B*Tree\n", 412 cnid); 413 return NULL; 414 } 415 416 sb = tree->inode->i_sb; 417 size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * 418 sizeof(struct page *); 419 node = kzalloc(size, GFP_KERNEL); 420 if (!node) 421 return NULL; 422 node->tree = tree; 423 node->this = cnid; 424 set_bit(HFS_BNODE_NEW, &node->flags); 425 atomic_set(&node->refcnt, 1); 426 hfs_dbg(BNODE_REFS, "new_node(%d:%d): 1\n", 427 node->tree->cnid, node->this); 428 init_waitqueue_head(&node->lock_wq); 429 spin_lock(&tree->hash_lock); 430 node2 = hfs_bnode_findhash(tree, cnid); 431 if (!node2) { 432 hash = hfs_bnode_hash(cnid); 433 node->next_hash = tree->node_hash[hash]; 434 tree->node_hash[hash] = node; 435 tree->node_hash_cnt++; 436 } else { 437 spin_unlock(&tree->hash_lock); 438 kfree(node); 439 wait_event(node2->lock_wq, 440 !test_bit(HFS_BNODE_NEW, &node2->flags)); 441 return node2; 442 } 443 spin_unlock(&tree->hash_lock); 444 445 mapping = tree->inode->i_mapping; 446 off = (loff_t)cnid << tree->node_size_shift; 447 block = off >> PAGE_CACHE_SHIFT; 448 node->page_offset = off & ~PAGE_CACHE_MASK; 449 for (i = 0; i < tree->pages_per_bnode; block++, i++) { 450 page = read_mapping_page(mapping, block, NULL); 451 if (IS_ERR(page)) 452 goto fail; 453 if (PageError(page)) { 454 page_cache_release(page); 455 goto fail; 456 } 457 node->page[i] = page; 458 } 459 460 return node; 461 fail: 462 set_bit(HFS_BNODE_ERROR, &node->flags); 463 return node; 464 } 465 466 void hfs_bnode_unhash(struct hfs_bnode *node) 467 { 468 struct hfs_bnode **p; 469 470 hfs_dbg(BNODE_REFS, "remove_node(%d:%d): %d\n", 471 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 472 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; 473 *p && *p != node; p = &(*p)->next_hash) 474 ; 475 BUG_ON(!*p); 476 *p = node->next_hash; 477 node->tree->node_hash_cnt--; 478 } 479 480 /* Load a particular node out of a tree */ 481 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) 482 { 483 struct hfs_bnode *node; 484 struct hfs_bnode_desc *desc; 485 int i, rec_off, off, next_off; 486 int entry_size, key_size; 487 488 spin_lock(&tree->hash_lock); 489 node = hfs_bnode_findhash(tree, num); 490 if (node) { 491 hfs_bnode_get(node); 492 spin_unlock(&tree->hash_lock); 493 wait_event(node->lock_wq, 494 !test_bit(HFS_BNODE_NEW, &node->flags)); 495 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 496 goto node_error; 497 return node; 498 } 499 spin_unlock(&tree->hash_lock); 500 node = __hfs_bnode_create(tree, num); 501 if (!node) 502 return ERR_PTR(-ENOMEM); 503 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 504 goto node_error; 505 if (!test_bit(HFS_BNODE_NEW, &node->flags)) 506 return node; 507 508 desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + 509 node->page_offset); 510 node->prev = be32_to_cpu(desc->prev); 511 node->next = be32_to_cpu(desc->next); 512 node->num_recs = be16_to_cpu(desc->num_recs); 513 node->type = desc->type; 514 node->height = desc->height; 515 kunmap(node->page[0]); 516 517 switch (node->type) { 518 case HFS_NODE_HEADER: 519 case HFS_NODE_MAP: 520 if (node->height != 0) 521 goto node_error; 522 break; 523 case HFS_NODE_LEAF: 524 if (node->height != 1) 525 goto node_error; 526 break; 527 case HFS_NODE_INDEX: 528 if (node->height <= 1 || node->height > tree->depth) 529 goto node_error; 530 break; 531 default: 532 goto node_error; 533 } 534 535 rec_off = tree->node_size - 2; 536 off = hfs_bnode_read_u16(node, rec_off); 537 if (off != sizeof(struct hfs_bnode_desc)) 538 goto node_error; 539 for (i = 1; i <= node->num_recs; off = next_off, i++) { 540 rec_off -= 2; 541 next_off = hfs_bnode_read_u16(node, rec_off); 542 if (next_off <= off || 543 next_off > tree->node_size || 544 next_off & 1) 545 goto node_error; 546 entry_size = next_off - off; 547 if (node->type != HFS_NODE_INDEX && 548 node->type != HFS_NODE_LEAF) 549 continue; 550 key_size = hfs_bnode_read_u16(node, off) + 2; 551 if (key_size >= entry_size || key_size & 1) 552 goto node_error; 553 } 554 clear_bit(HFS_BNODE_NEW, &node->flags); 555 wake_up(&node->lock_wq); 556 return node; 557 558 node_error: 559 set_bit(HFS_BNODE_ERROR, &node->flags); 560 clear_bit(HFS_BNODE_NEW, &node->flags); 561 wake_up(&node->lock_wq); 562 hfs_bnode_put(node); 563 return ERR_PTR(-EIO); 564 } 565 566 void hfs_bnode_free(struct hfs_bnode *node) 567 { 568 int i; 569 570 for (i = 0; i < node->tree->pages_per_bnode; i++) 571 if (node->page[i]) 572 page_cache_release(node->page[i]); 573 kfree(node); 574 } 575 576 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) 577 { 578 struct hfs_bnode *node; 579 struct page **pagep; 580 int i; 581 582 spin_lock(&tree->hash_lock); 583 node = hfs_bnode_findhash(tree, num); 584 spin_unlock(&tree->hash_lock); 585 if (node) { 586 pr_crit("new node %u already hashed?\n", num); 587 WARN_ON(1); 588 return node; 589 } 590 node = __hfs_bnode_create(tree, num); 591 if (!node) 592 return ERR_PTR(-ENOMEM); 593 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { 594 hfs_bnode_put(node); 595 return ERR_PTR(-EIO); 596 } 597 598 pagep = node->page; 599 memset(kmap(*pagep) + node->page_offset, 0, 600 min_t(int, PAGE_CACHE_SIZE, tree->node_size)); 601 set_page_dirty(*pagep); 602 kunmap(*pagep); 603 for (i = 1; i < tree->pages_per_bnode; i++) { 604 memset(kmap(*++pagep), 0, PAGE_CACHE_SIZE); 605 set_page_dirty(*pagep); 606 kunmap(*pagep); 607 } 608 clear_bit(HFS_BNODE_NEW, &node->flags); 609 wake_up(&node->lock_wq); 610 611 return node; 612 } 613 614 void hfs_bnode_get(struct hfs_bnode *node) 615 { 616 if (node) { 617 atomic_inc(&node->refcnt); 618 hfs_dbg(BNODE_REFS, "get_node(%d:%d): %d\n", 619 node->tree->cnid, node->this, 620 atomic_read(&node->refcnt)); 621 } 622 } 623 624 /* Dispose of resources used by a node */ 625 void hfs_bnode_put(struct hfs_bnode *node) 626 { 627 if (node) { 628 struct hfs_btree *tree = node->tree; 629 int i; 630 631 hfs_dbg(BNODE_REFS, "put_node(%d:%d): %d\n", 632 node->tree->cnid, node->this, 633 atomic_read(&node->refcnt)); 634 BUG_ON(!atomic_read(&node->refcnt)); 635 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) 636 return; 637 for (i = 0; i < tree->pages_per_bnode; i++) { 638 if (!node->page[i]) 639 continue; 640 mark_page_accessed(node->page[i]); 641 } 642 643 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { 644 hfs_bnode_unhash(node); 645 spin_unlock(&tree->hash_lock); 646 if (hfs_bnode_need_zeroout(tree)) 647 hfs_bnode_clear(node, 0, tree->node_size); 648 hfs_bmap_free(node); 649 hfs_bnode_free(node); 650 return; 651 } 652 spin_unlock(&tree->hash_lock); 653 } 654 } 655 656 /* 657 * Unused nodes have to be zeroed if this is the catalog tree and 658 * a corresponding flag in the volume header is set. 659 */ 660 bool hfs_bnode_need_zeroout(struct hfs_btree *tree) 661 { 662 struct super_block *sb = tree->inode->i_sb; 663 struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb); 664 const u32 volume_attr = be32_to_cpu(sbi->s_vhdr->attributes); 665 666 return tree->cnid == HFSPLUS_CAT_CNID && 667 volume_attr & HFSPLUS_VOL_UNUSED_NODE_FIX; 668 } 669