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(len, (int)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(len, (int)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 // 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 // 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 key_len = hfs_bnode_read_u16(node, off) + 2; 67 else 68 key_len = tree->max_key_len + 2; 69 70 hfs_bnode_read(node, key, off, key_len); 71 } 72 73 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) 74 { 75 struct page **pagep; 76 int l; 77 78 off += node->page_offset; 79 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 80 off &= ~PAGE_CACHE_MASK; 81 82 l = min(len, (int)PAGE_CACHE_SIZE - off); 83 memcpy(kmap(*pagep) + off, buf, l); 84 set_page_dirty(*pagep); 85 kunmap(*pagep); 86 87 while ((len -= l) != 0) { 88 buf += l; 89 l = min(len, (int)PAGE_CACHE_SIZE); 90 memcpy(kmap(*++pagep), buf, l); 91 set_page_dirty(*pagep); 92 kunmap(*pagep); 93 } 94 } 95 96 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) 97 { 98 __be16 v = cpu_to_be16(data); 99 // optimize later... 100 hfs_bnode_write(node, &v, off, 2); 101 } 102 103 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) 104 { 105 struct page **pagep; 106 int l; 107 108 off += node->page_offset; 109 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 110 off &= ~PAGE_CACHE_MASK; 111 112 l = min(len, (int)PAGE_CACHE_SIZE - off); 113 memset(kmap(*pagep) + off, 0, l); 114 set_page_dirty(*pagep); 115 kunmap(*pagep); 116 117 while ((len -= l) != 0) { 118 l = min(len, (int)PAGE_CACHE_SIZE); 119 memset(kmap(*++pagep), 0, l); 120 set_page_dirty(*pagep); 121 kunmap(*pagep); 122 } 123 } 124 125 void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst, 126 struct hfs_bnode *src_node, int src, int len) 127 { 128 struct hfs_btree *tree; 129 struct page **src_page, **dst_page; 130 int l; 131 132 dprint(DBG_BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len); 133 if (!len) 134 return; 135 tree = src_node->tree; 136 src += src_node->page_offset; 137 dst += dst_node->page_offset; 138 src_page = src_node->page + (src >> PAGE_CACHE_SHIFT); 139 src &= ~PAGE_CACHE_MASK; 140 dst_page = dst_node->page + (dst >> PAGE_CACHE_SHIFT); 141 dst &= ~PAGE_CACHE_MASK; 142 143 if (src == dst) { 144 l = min(len, (int)PAGE_CACHE_SIZE - src); 145 memcpy(kmap(*dst_page) + src, kmap(*src_page) + src, l); 146 kunmap(*src_page); 147 set_page_dirty(*dst_page); 148 kunmap(*dst_page); 149 150 while ((len -= l) != 0) { 151 l = min(len, (int)PAGE_CACHE_SIZE); 152 memcpy(kmap(*++dst_page), kmap(*++src_page), l); 153 kunmap(*src_page); 154 set_page_dirty(*dst_page); 155 kunmap(*dst_page); 156 } 157 } else { 158 void *src_ptr, *dst_ptr; 159 160 do { 161 src_ptr = kmap(*src_page) + src; 162 dst_ptr = kmap(*dst_page) + dst; 163 if (PAGE_CACHE_SIZE - src < PAGE_CACHE_SIZE - dst) { 164 l = PAGE_CACHE_SIZE - src; 165 src = 0; 166 dst += l; 167 } else { 168 l = PAGE_CACHE_SIZE - dst; 169 src += l; 170 dst = 0; 171 } 172 l = min(len, l); 173 memcpy(dst_ptr, src_ptr, l); 174 kunmap(*src_page); 175 set_page_dirty(*dst_page); 176 kunmap(*dst_page); 177 if (!dst) 178 dst_page++; 179 else 180 src_page++; 181 } while ((len -= l)); 182 } 183 } 184 185 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) 186 { 187 struct page **src_page, **dst_page; 188 int l; 189 190 dprint(DBG_BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len); 191 if (!len) 192 return; 193 src += node->page_offset; 194 dst += node->page_offset; 195 if (dst > src) { 196 src += len - 1; 197 src_page = node->page + (src >> PAGE_CACHE_SHIFT); 198 src = (src & ~PAGE_CACHE_MASK) + 1; 199 dst += len - 1; 200 dst_page = node->page + (dst >> PAGE_CACHE_SHIFT); 201 dst = (dst & ~PAGE_CACHE_MASK) + 1; 202 203 if (src == dst) { 204 while (src < len) { 205 memmove(kmap(*dst_page), kmap(*src_page), src); 206 kunmap(*src_page); 207 set_page_dirty(*dst_page); 208 kunmap(*dst_page); 209 len -= src; 210 src = PAGE_CACHE_SIZE; 211 src_page--; 212 dst_page--; 213 } 214 src -= len; 215 memmove(kmap(*dst_page) + src, kmap(*src_page) + src, len); 216 kunmap(*src_page); 217 set_page_dirty(*dst_page); 218 kunmap(*dst_page); 219 } else { 220 void *src_ptr, *dst_ptr; 221 222 do { 223 src_ptr = kmap(*src_page) + src; 224 dst_ptr = kmap(*dst_page) + dst; 225 if (src < dst) { 226 l = src; 227 src = PAGE_CACHE_SIZE; 228 dst -= l; 229 } else { 230 l = dst; 231 src -= l; 232 dst = PAGE_CACHE_SIZE; 233 } 234 l = min(len, l); 235 memmove(dst_ptr - l, src_ptr - l, l); 236 kunmap(*src_page); 237 set_page_dirty(*dst_page); 238 kunmap(*dst_page); 239 if (dst == PAGE_CACHE_SIZE) 240 dst_page--; 241 else 242 src_page--; 243 } while ((len -= l)); 244 } 245 } else { 246 src_page = node->page + (src >> PAGE_CACHE_SHIFT); 247 src &= ~PAGE_CACHE_MASK; 248 dst_page = node->page + (dst >> PAGE_CACHE_SHIFT); 249 dst &= ~PAGE_CACHE_MASK; 250 251 if (src == dst) { 252 l = min(len, (int)PAGE_CACHE_SIZE - src); 253 memmove(kmap(*dst_page) + src, kmap(*src_page) + src, l); 254 kunmap(*src_page); 255 set_page_dirty(*dst_page); 256 kunmap(*dst_page); 257 258 while ((len -= l) != 0) { 259 l = min(len, (int)PAGE_CACHE_SIZE); 260 memmove(kmap(*++dst_page), kmap(*++src_page), l); 261 kunmap(*src_page); 262 set_page_dirty(*dst_page); 263 kunmap(*dst_page); 264 } 265 } else { 266 void *src_ptr, *dst_ptr; 267 268 do { 269 src_ptr = kmap(*src_page) + src; 270 dst_ptr = kmap(*dst_page) + dst; 271 if (PAGE_CACHE_SIZE - src < PAGE_CACHE_SIZE - dst) { 272 l = PAGE_CACHE_SIZE - src; 273 src = 0; 274 dst += l; 275 } else { 276 l = PAGE_CACHE_SIZE - dst; 277 src += l; 278 dst = 0; 279 } 280 l = min(len, l); 281 memmove(dst_ptr, src_ptr, l); 282 kunmap(*src_page); 283 set_page_dirty(*dst_page); 284 kunmap(*dst_page); 285 if (!dst) 286 dst_page++; 287 else 288 src_page++; 289 } while ((len -= l)); 290 } 291 } 292 } 293 294 void hfs_bnode_dump(struct hfs_bnode *node) 295 { 296 struct hfs_bnode_desc desc; 297 __be32 cnid; 298 int i, off, key_off; 299 300 dprint(DBG_BNODE_MOD, "bnode: %d\n", node->this); 301 hfs_bnode_read(node, &desc, 0, sizeof(desc)); 302 dprint(DBG_BNODE_MOD, "%d, %d, %d, %d, %d\n", 303 be32_to_cpu(desc.next), be32_to_cpu(desc.prev), 304 desc.type, desc.height, be16_to_cpu(desc.num_recs)); 305 306 off = node->tree->node_size - 2; 307 for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) { 308 key_off = hfs_bnode_read_u16(node, off); 309 dprint(DBG_BNODE_MOD, " %d", key_off); 310 if (i && node->type == HFS_NODE_INDEX) { 311 int tmp; 312 313 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) 314 tmp = hfs_bnode_read_u16(node, key_off) + 2; 315 else 316 tmp = node->tree->max_key_len + 2; 317 dprint(DBG_BNODE_MOD, " (%d", tmp); 318 hfs_bnode_read(node, &cnid, key_off + tmp, 4); 319 dprint(DBG_BNODE_MOD, ",%d)", be32_to_cpu(cnid)); 320 } else if (i && node->type == HFS_NODE_LEAF) { 321 int tmp; 322 323 tmp = hfs_bnode_read_u16(node, key_off); 324 dprint(DBG_BNODE_MOD, " (%d)", tmp); 325 } 326 } 327 dprint(DBG_BNODE_MOD, "\n"); 328 } 329 330 void hfs_bnode_unlink(struct hfs_bnode *node) 331 { 332 struct hfs_btree *tree; 333 struct hfs_bnode *tmp; 334 __be32 cnid; 335 336 tree = node->tree; 337 if (node->prev) { 338 tmp = hfs_bnode_find(tree, node->prev); 339 if (IS_ERR(tmp)) 340 return; 341 tmp->next = node->next; 342 cnid = cpu_to_be32(tmp->next); 343 hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 344 hfs_bnode_put(tmp); 345 } else if (node->type == HFS_NODE_LEAF) 346 tree->leaf_head = node->next; 347 348 if (node->next) { 349 tmp = hfs_bnode_find(tree, node->next); 350 if (IS_ERR(tmp)) 351 return; 352 tmp->prev = node->prev; 353 cnid = cpu_to_be32(tmp->prev); 354 hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, prev), 4); 355 hfs_bnode_put(tmp); 356 } else if (node->type == HFS_NODE_LEAF) 357 tree->leaf_tail = node->prev; 358 359 // move down? 360 if (!node->prev && !node->next) { 361 printk(KERN_DEBUG "hfs_btree_del_level\n"); 362 } 363 if (!node->parent) { 364 tree->root = 0; 365 tree->depth = 0; 366 } 367 set_bit(HFS_BNODE_DELETED, &node->flags); 368 } 369 370 static inline int hfs_bnode_hash(u32 num) 371 { 372 num = (num >> 16) + num; 373 num += num >> 8; 374 return num & (NODE_HASH_SIZE - 1); 375 } 376 377 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) 378 { 379 struct hfs_bnode *node; 380 381 if (cnid >= tree->node_count) { 382 printk(KERN_ERR "hfs: request for non-existent node %d in B*Tree\n", cnid); 383 return NULL; 384 } 385 386 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; 387 node; node = node->next_hash) { 388 if (node->this == cnid) { 389 return node; 390 } 391 } 392 return NULL; 393 } 394 395 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) 396 { 397 struct super_block *sb; 398 struct hfs_bnode *node, *node2; 399 struct address_space *mapping; 400 struct page *page; 401 int size, block, i, hash; 402 loff_t off; 403 404 if (cnid >= tree->node_count) { 405 printk(KERN_ERR "hfs: request for non-existent node %d in B*Tree\n", cnid); 406 return NULL; 407 } 408 409 sb = tree->inode->i_sb; 410 size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * 411 sizeof(struct page *); 412 node = kmalloc(size, GFP_KERNEL); 413 if (!node) 414 return NULL; 415 memset(node, 0, size); 416 node->tree = tree; 417 node->this = cnid; 418 set_bit(HFS_BNODE_NEW, &node->flags); 419 atomic_set(&node->refcnt, 1); 420 dprint(DBG_BNODE_REFS, "new_node(%d:%d): 1\n", 421 node->tree->cnid, node->this); 422 init_waitqueue_head(&node->lock_wq); 423 spin_lock(&tree->hash_lock); 424 node2 = hfs_bnode_findhash(tree, cnid); 425 if (!node2) { 426 hash = hfs_bnode_hash(cnid); 427 node->next_hash = tree->node_hash[hash]; 428 tree->node_hash[hash] = node; 429 tree->node_hash_cnt++; 430 } else { 431 spin_unlock(&tree->hash_lock); 432 kfree(node); 433 wait_event(node2->lock_wq, !test_bit(HFS_BNODE_NEW, &node2->flags)); 434 return node2; 435 } 436 spin_unlock(&tree->hash_lock); 437 438 mapping = tree->inode->i_mapping; 439 off = (loff_t)cnid << tree->node_size_shift; 440 block = off >> PAGE_CACHE_SHIFT; 441 node->page_offset = off & ~PAGE_CACHE_MASK; 442 for (i = 0; i < tree->pages_per_bnode; block++, i++) { 443 page = read_cache_page(mapping, block, (filler_t *)mapping->a_ops->readpage, NULL); 444 if (IS_ERR(page)) 445 goto fail; 446 if (PageError(page)) { 447 page_cache_release(page); 448 goto fail; 449 } 450 page_cache_release(page); 451 node->page[i] = page; 452 } 453 454 return node; 455 fail: 456 set_bit(HFS_BNODE_ERROR, &node->flags); 457 return node; 458 } 459 460 void hfs_bnode_unhash(struct hfs_bnode *node) 461 { 462 struct hfs_bnode **p; 463 464 dprint(DBG_BNODE_REFS, "remove_node(%d:%d): %d\n", 465 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 466 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; 467 *p && *p != node; p = &(*p)->next_hash) 468 ; 469 if (!*p) 470 BUG(); 471 *p = node->next_hash; 472 node->tree->node_hash_cnt--; 473 } 474 475 /* Load a particular node out of a tree */ 476 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) 477 { 478 struct hfs_bnode *node; 479 struct hfs_bnode_desc *desc; 480 int i, rec_off, off, next_off; 481 int entry_size, key_size; 482 483 spin_lock(&tree->hash_lock); 484 node = hfs_bnode_findhash(tree, num); 485 if (node) { 486 hfs_bnode_get(node); 487 spin_unlock(&tree->hash_lock); 488 wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags)); 489 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 490 goto node_error; 491 return node; 492 } 493 spin_unlock(&tree->hash_lock); 494 node = __hfs_bnode_create(tree, num); 495 if (!node) 496 return ERR_PTR(-ENOMEM); 497 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 498 goto node_error; 499 if (!test_bit(HFS_BNODE_NEW, &node->flags)) 500 return node; 501 502 desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset); 503 node->prev = be32_to_cpu(desc->prev); 504 node->next = be32_to_cpu(desc->next); 505 node->num_recs = be16_to_cpu(desc->num_recs); 506 node->type = desc->type; 507 node->height = desc->height; 508 kunmap(node->page[0]); 509 510 switch (node->type) { 511 case HFS_NODE_HEADER: 512 case HFS_NODE_MAP: 513 if (node->height != 0) 514 goto node_error; 515 break; 516 case HFS_NODE_LEAF: 517 if (node->height != 1) 518 goto node_error; 519 break; 520 case HFS_NODE_INDEX: 521 if (node->height <= 1 || node->height > tree->depth) 522 goto node_error; 523 break; 524 default: 525 goto node_error; 526 } 527 528 rec_off = tree->node_size - 2; 529 off = hfs_bnode_read_u16(node, rec_off); 530 if (off != sizeof(struct hfs_bnode_desc)) 531 goto node_error; 532 for (i = 1; i <= node->num_recs; off = next_off, i++) { 533 rec_off -= 2; 534 next_off = hfs_bnode_read_u16(node, rec_off); 535 if (next_off <= off || 536 next_off > tree->node_size || 537 next_off & 1) 538 goto node_error; 539 entry_size = next_off - off; 540 if (node->type != HFS_NODE_INDEX && 541 node->type != HFS_NODE_LEAF) 542 continue; 543 key_size = hfs_bnode_read_u16(node, off) + 2; 544 if (key_size >= entry_size || key_size & 1) 545 goto node_error; 546 } 547 clear_bit(HFS_BNODE_NEW, &node->flags); 548 wake_up(&node->lock_wq); 549 return node; 550 551 node_error: 552 set_bit(HFS_BNODE_ERROR, &node->flags); 553 clear_bit(HFS_BNODE_NEW, &node->flags); 554 wake_up(&node->lock_wq); 555 hfs_bnode_put(node); 556 return ERR_PTR(-EIO); 557 } 558 559 void hfs_bnode_free(struct hfs_bnode *node) 560 { 561 //int i; 562 563 //for (i = 0; i < node->tree->pages_per_bnode; i++) 564 // if (node->page[i]) 565 // page_cache_release(node->page[i]); 566 kfree(node); 567 } 568 569 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) 570 { 571 struct hfs_bnode *node; 572 struct page **pagep; 573 int i; 574 575 spin_lock(&tree->hash_lock); 576 node = hfs_bnode_findhash(tree, num); 577 spin_unlock(&tree->hash_lock); 578 if (node) { 579 printk(KERN_CRIT "new node %u already hashed?\n", num); 580 WARN_ON(1); 581 return node; 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