1 /* 2 * linux/fs/hfsplus/extents.c 3 * 4 * Copyright (C) 2001 5 * Brad Boyer (flar@allandria.com) 6 * (C) 2003 Ardis Technologies <roman@ardistech.com> 7 * 8 * Handling of Extents both in catalog and extents overflow trees 9 */ 10 11 #include <linux/errno.h> 12 #include <linux/fs.h> 13 #include <linux/pagemap.h> 14 15 #include "hfsplus_fs.h" 16 #include "hfsplus_raw.h" 17 18 /* Compare two extents keys, returns 0 on same, pos/neg for difference */ 19 int hfsplus_ext_cmp_key(const hfsplus_btree_key *k1, 20 const hfsplus_btree_key *k2) 21 { 22 __be32 k1id, k2id; 23 __be32 k1s, k2s; 24 25 k1id = k1->ext.cnid; 26 k2id = k2->ext.cnid; 27 if (k1id != k2id) 28 return be32_to_cpu(k1id) < be32_to_cpu(k2id) ? -1 : 1; 29 30 if (k1->ext.fork_type != k2->ext.fork_type) 31 return k1->ext.fork_type < k2->ext.fork_type ? -1 : 1; 32 33 k1s = k1->ext.start_block; 34 k2s = k2->ext.start_block; 35 if (k1s == k2s) 36 return 0; 37 return be32_to_cpu(k1s) < be32_to_cpu(k2s) ? -1 : 1; 38 } 39 40 static void hfsplus_ext_build_key(hfsplus_btree_key *key, u32 cnid, 41 u32 block, u8 type) 42 { 43 key->key_len = cpu_to_be16(HFSPLUS_EXT_KEYLEN - 2); 44 key->ext.cnid = cpu_to_be32(cnid); 45 key->ext.start_block = cpu_to_be32(block); 46 key->ext.fork_type = type; 47 key->ext.pad = 0; 48 } 49 50 static u32 hfsplus_ext_find_block(struct hfsplus_extent *ext, u32 off) 51 { 52 int i; 53 u32 count; 54 55 for (i = 0; i < 8; ext++, i++) { 56 count = be32_to_cpu(ext->block_count); 57 if (off < count) 58 return be32_to_cpu(ext->start_block) + off; 59 off -= count; 60 } 61 /* panic? */ 62 return 0; 63 } 64 65 static int hfsplus_ext_block_count(struct hfsplus_extent *ext) 66 { 67 int i; 68 u32 count = 0; 69 70 for (i = 0; i < 8; ext++, i++) 71 count += be32_to_cpu(ext->block_count); 72 return count; 73 } 74 75 static u32 hfsplus_ext_lastblock(struct hfsplus_extent *ext) 76 { 77 int i; 78 79 ext += 7; 80 for (i = 0; i < 7; ext--, i++) 81 if (ext->block_count) 82 break; 83 return be32_to_cpu(ext->start_block) + be32_to_cpu(ext->block_count); 84 } 85 86 static void __hfsplus_ext_write_extent(struct inode *inode, 87 struct hfs_find_data *fd) 88 { 89 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 90 int res; 91 92 WARN_ON(!mutex_is_locked(&hip->extents_lock)); 93 94 hfsplus_ext_build_key(fd->search_key, inode->i_ino, hip->cached_start, 95 HFSPLUS_IS_RSRC(inode) ? 96 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA); 97 98 res = hfs_brec_find(fd, hfs_find_rec_by_key); 99 if (hip->extent_state & HFSPLUS_EXT_NEW) { 100 if (res != -ENOENT) 101 return; 102 hfs_brec_insert(fd, hip->cached_extents, 103 sizeof(hfsplus_extent_rec)); 104 hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW); 105 } else { 106 if (res) 107 return; 108 hfs_bnode_write(fd->bnode, hip->cached_extents, 109 fd->entryoffset, fd->entrylength); 110 hip->extent_state &= ~HFSPLUS_EXT_DIRTY; 111 } 112 113 /* 114 * We can't just use hfsplus_mark_inode_dirty here, because we 115 * also get called from hfsplus_write_inode, which should not 116 * redirty the inode. Instead the callers have to be careful 117 * to explicily mark the inode dirty, too. 118 */ 119 set_bit(HFSPLUS_I_EXT_DIRTY, &hip->flags); 120 } 121 122 static int hfsplus_ext_write_extent_locked(struct inode *inode) 123 { 124 int res; 125 126 if (HFSPLUS_I(inode)->extent_state & HFSPLUS_EXT_DIRTY) { 127 struct hfs_find_data fd; 128 129 res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd); 130 if (res) 131 return res; 132 __hfsplus_ext_write_extent(inode, &fd); 133 hfs_find_exit(&fd); 134 } 135 return 0; 136 } 137 138 int hfsplus_ext_write_extent(struct inode *inode) 139 { 140 int res; 141 142 mutex_lock(&HFSPLUS_I(inode)->extents_lock); 143 res = hfsplus_ext_write_extent_locked(inode); 144 mutex_unlock(&HFSPLUS_I(inode)->extents_lock); 145 146 return res; 147 } 148 149 static inline int __hfsplus_ext_read_extent(struct hfs_find_data *fd, 150 struct hfsplus_extent *extent, 151 u32 cnid, u32 block, u8 type) 152 { 153 int res; 154 155 hfsplus_ext_build_key(fd->search_key, cnid, block, type); 156 fd->key->ext.cnid = 0; 157 res = hfs_brec_find(fd, hfs_find_rec_by_key); 158 if (res && res != -ENOENT) 159 return res; 160 if (fd->key->ext.cnid != fd->search_key->ext.cnid || 161 fd->key->ext.fork_type != fd->search_key->ext.fork_type) 162 return -ENOENT; 163 if (fd->entrylength != sizeof(hfsplus_extent_rec)) 164 return -EIO; 165 hfs_bnode_read(fd->bnode, extent, fd->entryoffset, 166 sizeof(hfsplus_extent_rec)); 167 return 0; 168 } 169 170 static inline int __hfsplus_ext_cache_extent(struct hfs_find_data *fd, 171 struct inode *inode, u32 block) 172 { 173 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 174 int res; 175 176 WARN_ON(!mutex_is_locked(&hip->extents_lock)); 177 178 if (hip->extent_state & HFSPLUS_EXT_DIRTY) 179 __hfsplus_ext_write_extent(inode, fd); 180 181 res = __hfsplus_ext_read_extent(fd, hip->cached_extents, inode->i_ino, 182 block, HFSPLUS_IS_RSRC(inode) ? 183 HFSPLUS_TYPE_RSRC : 184 HFSPLUS_TYPE_DATA); 185 if (!res) { 186 hip->cached_start = be32_to_cpu(fd->key->ext.start_block); 187 hip->cached_blocks = 188 hfsplus_ext_block_count(hip->cached_extents); 189 } else { 190 hip->cached_start = hip->cached_blocks = 0; 191 hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW); 192 } 193 return res; 194 } 195 196 static int hfsplus_ext_read_extent(struct inode *inode, u32 block) 197 { 198 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 199 struct hfs_find_data fd; 200 int res; 201 202 if (block >= hip->cached_start && 203 block < hip->cached_start + hip->cached_blocks) 204 return 0; 205 206 res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd); 207 if (!res) { 208 res = __hfsplus_ext_cache_extent(&fd, inode, block); 209 hfs_find_exit(&fd); 210 } 211 return res; 212 } 213 214 /* Get a block at iblock for inode, possibly allocating if create */ 215 int hfsplus_get_block(struct inode *inode, sector_t iblock, 216 struct buffer_head *bh_result, int create) 217 { 218 struct super_block *sb = inode->i_sb; 219 struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb); 220 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 221 int res = -EIO; 222 u32 ablock, dblock, mask; 223 sector_t sector; 224 int was_dirty = 0; 225 int shift; 226 227 /* Convert inode block to disk allocation block */ 228 shift = sbi->alloc_blksz_shift - sb->s_blocksize_bits; 229 ablock = iblock >> sbi->fs_shift; 230 231 if (iblock >= hip->fs_blocks) { 232 if (iblock > hip->fs_blocks || !create) 233 return -EIO; 234 if (ablock >= hip->alloc_blocks) { 235 res = hfsplus_file_extend(inode); 236 if (res) 237 return res; 238 } 239 } else 240 create = 0; 241 242 if (ablock < hip->first_blocks) { 243 dblock = hfsplus_ext_find_block(hip->first_extents, ablock); 244 goto done; 245 } 246 247 if (inode->i_ino == HFSPLUS_EXT_CNID) 248 return -EIO; 249 250 mutex_lock(&hip->extents_lock); 251 252 /* 253 * hfsplus_ext_read_extent will write out a cached extent into 254 * the extents btree. In that case we may have to mark the inode 255 * dirty even for a pure read of an extent here. 256 */ 257 was_dirty = (hip->extent_state & HFSPLUS_EXT_DIRTY); 258 res = hfsplus_ext_read_extent(inode, ablock); 259 if (res) { 260 mutex_unlock(&hip->extents_lock); 261 return -EIO; 262 } 263 dblock = hfsplus_ext_find_block(hip->cached_extents, 264 ablock - hip->cached_start); 265 mutex_unlock(&hip->extents_lock); 266 267 done: 268 dprint(DBG_EXTENT, "get_block(%lu): %llu - %u\n", 269 inode->i_ino, (long long)iblock, dblock); 270 271 mask = (1 << sbi->fs_shift) - 1; 272 sector = ((sector_t)dblock << sbi->fs_shift) + 273 sbi->blockoffset + (iblock & mask); 274 map_bh(bh_result, sb, sector); 275 276 if (create) { 277 set_buffer_new(bh_result); 278 hip->phys_size += sb->s_blocksize; 279 hip->fs_blocks++; 280 inode_add_bytes(inode, sb->s_blocksize); 281 } 282 if (create || was_dirty) 283 mark_inode_dirty(inode); 284 return 0; 285 } 286 287 static void hfsplus_dump_extent(struct hfsplus_extent *extent) 288 { 289 int i; 290 291 dprint(DBG_EXTENT, " "); 292 for (i = 0; i < 8; i++) 293 dprint(DBG_EXTENT, " %u:%u", be32_to_cpu(extent[i].start_block), 294 be32_to_cpu(extent[i].block_count)); 295 dprint(DBG_EXTENT, "\n"); 296 } 297 298 static int hfsplus_add_extent(struct hfsplus_extent *extent, u32 offset, 299 u32 alloc_block, u32 block_count) 300 { 301 u32 count, start; 302 int i; 303 304 hfsplus_dump_extent(extent); 305 for (i = 0; i < 8; extent++, i++) { 306 count = be32_to_cpu(extent->block_count); 307 if (offset == count) { 308 start = be32_to_cpu(extent->start_block); 309 if (alloc_block != start + count) { 310 if (++i >= 8) 311 return -ENOSPC; 312 extent++; 313 extent->start_block = cpu_to_be32(alloc_block); 314 } else 315 block_count += count; 316 extent->block_count = cpu_to_be32(block_count); 317 return 0; 318 } else if (offset < count) 319 break; 320 offset -= count; 321 } 322 /* panic? */ 323 return -EIO; 324 } 325 326 static int hfsplus_free_extents(struct super_block *sb, 327 struct hfsplus_extent *extent, 328 u32 offset, u32 block_nr) 329 { 330 u32 count, start; 331 int i; 332 int err = 0; 333 334 hfsplus_dump_extent(extent); 335 for (i = 0; i < 8; extent++, i++) { 336 count = be32_to_cpu(extent->block_count); 337 if (offset == count) 338 goto found; 339 else if (offset < count) 340 break; 341 offset -= count; 342 } 343 /* panic? */ 344 return -EIO; 345 found: 346 for (;;) { 347 start = be32_to_cpu(extent->start_block); 348 if (count <= block_nr) { 349 err = hfsplus_block_free(sb, start, count); 350 if (err) { 351 printk(KERN_ERR "hfs: can't free extent\n"); 352 dprint(DBG_EXTENT, " start: %u count: %u\n", 353 start, count); 354 } 355 extent->block_count = 0; 356 extent->start_block = 0; 357 block_nr -= count; 358 } else { 359 count -= block_nr; 360 err = hfsplus_block_free(sb, start + count, block_nr); 361 if (err) { 362 printk(KERN_ERR "hfs: can't free extent\n"); 363 dprint(DBG_EXTENT, " start: %u count: %u\n", 364 start, count); 365 } 366 extent->block_count = cpu_to_be32(count); 367 block_nr = 0; 368 } 369 if (!block_nr || !i) { 370 /* 371 * Try to free all extents and 372 * return only last error 373 */ 374 return err; 375 } 376 i--; 377 extent--; 378 count = be32_to_cpu(extent->block_count); 379 } 380 } 381 382 int hfsplus_free_fork(struct super_block *sb, u32 cnid, 383 struct hfsplus_fork_raw *fork, int type) 384 { 385 struct hfs_find_data fd; 386 hfsplus_extent_rec ext_entry; 387 u32 total_blocks, blocks, start; 388 int res, i; 389 390 total_blocks = be32_to_cpu(fork->total_blocks); 391 if (!total_blocks) 392 return 0; 393 394 blocks = 0; 395 for (i = 0; i < 8; i++) 396 blocks += be32_to_cpu(fork->extents[i].block_count); 397 398 res = hfsplus_free_extents(sb, fork->extents, blocks, blocks); 399 if (res) 400 return res; 401 if (total_blocks == blocks) 402 return 0; 403 404 res = hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd); 405 if (res) 406 return res; 407 do { 408 res = __hfsplus_ext_read_extent(&fd, ext_entry, cnid, 409 total_blocks, type); 410 if (res) 411 break; 412 start = be32_to_cpu(fd.key->ext.start_block); 413 hfsplus_free_extents(sb, ext_entry, 414 total_blocks - start, 415 total_blocks); 416 hfs_brec_remove(&fd); 417 total_blocks = start; 418 } while (total_blocks > blocks); 419 hfs_find_exit(&fd); 420 421 return res; 422 } 423 424 int hfsplus_file_extend(struct inode *inode) 425 { 426 struct super_block *sb = inode->i_sb; 427 struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb); 428 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 429 u32 start, len, goal; 430 int res; 431 432 if (sbi->alloc_file->i_size * 8 < 433 sbi->total_blocks - sbi->free_blocks + 8) { 434 /* extend alloc file */ 435 printk(KERN_ERR "hfs: extend alloc file! " 436 "(%llu,%u,%u)\n", 437 sbi->alloc_file->i_size * 8, 438 sbi->total_blocks, sbi->free_blocks); 439 return -ENOSPC; 440 } 441 442 mutex_lock(&hip->extents_lock); 443 if (hip->alloc_blocks == hip->first_blocks) 444 goal = hfsplus_ext_lastblock(hip->first_extents); 445 else { 446 res = hfsplus_ext_read_extent(inode, hip->alloc_blocks); 447 if (res) 448 goto out; 449 goal = hfsplus_ext_lastblock(hip->cached_extents); 450 } 451 452 len = hip->clump_blocks; 453 start = hfsplus_block_allocate(sb, sbi->total_blocks, goal, &len); 454 if (start >= sbi->total_blocks) { 455 start = hfsplus_block_allocate(sb, goal, 0, &len); 456 if (start >= goal) { 457 res = -ENOSPC; 458 goto out; 459 } 460 } 461 462 dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len); 463 464 if (hip->alloc_blocks <= hip->first_blocks) { 465 if (!hip->first_blocks) { 466 dprint(DBG_EXTENT, "first extents\n"); 467 /* no extents yet */ 468 hip->first_extents[0].start_block = cpu_to_be32(start); 469 hip->first_extents[0].block_count = cpu_to_be32(len); 470 res = 0; 471 } else { 472 /* try to append to extents in inode */ 473 res = hfsplus_add_extent(hip->first_extents, 474 hip->alloc_blocks, 475 start, len); 476 if (res == -ENOSPC) 477 goto insert_extent; 478 } 479 if (!res) { 480 hfsplus_dump_extent(hip->first_extents); 481 hip->first_blocks += len; 482 } 483 } else { 484 res = hfsplus_add_extent(hip->cached_extents, 485 hip->alloc_blocks - hip->cached_start, 486 start, len); 487 if (!res) { 488 hfsplus_dump_extent(hip->cached_extents); 489 hip->extent_state |= HFSPLUS_EXT_DIRTY; 490 hip->cached_blocks += len; 491 } else if (res == -ENOSPC) 492 goto insert_extent; 493 } 494 out: 495 mutex_unlock(&hip->extents_lock); 496 if (!res) { 497 hip->alloc_blocks += len; 498 hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY); 499 } 500 return res; 501 502 insert_extent: 503 dprint(DBG_EXTENT, "insert new extent\n"); 504 res = hfsplus_ext_write_extent_locked(inode); 505 if (res) 506 goto out; 507 508 memset(hip->cached_extents, 0, sizeof(hfsplus_extent_rec)); 509 hip->cached_extents[0].start_block = cpu_to_be32(start); 510 hip->cached_extents[0].block_count = cpu_to_be32(len); 511 hfsplus_dump_extent(hip->cached_extents); 512 hip->extent_state |= HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW; 513 hip->cached_start = hip->alloc_blocks; 514 hip->cached_blocks = len; 515 516 res = 0; 517 goto out; 518 } 519 520 void hfsplus_file_truncate(struct inode *inode) 521 { 522 struct super_block *sb = inode->i_sb; 523 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 524 struct hfs_find_data fd; 525 u32 alloc_cnt, blk_cnt, start; 526 int res; 527 528 dprint(DBG_INODE, "truncate: %lu, %llu -> %llu\n", 529 inode->i_ino, (long long)hip->phys_size, 530 inode->i_size); 531 532 if (inode->i_size > hip->phys_size) { 533 struct address_space *mapping = inode->i_mapping; 534 struct page *page; 535 void *fsdata; 536 u32 size = inode->i_size; 537 538 res = pagecache_write_begin(NULL, mapping, size, 0, 539 AOP_FLAG_UNINTERRUPTIBLE, 540 &page, &fsdata); 541 if (res) 542 return; 543 res = pagecache_write_end(NULL, mapping, size, 544 0, 0, page, fsdata); 545 if (res < 0) 546 return; 547 mark_inode_dirty(inode); 548 return; 549 } else if (inode->i_size == hip->phys_size) 550 return; 551 552 blk_cnt = (inode->i_size + HFSPLUS_SB(sb)->alloc_blksz - 1) >> 553 HFSPLUS_SB(sb)->alloc_blksz_shift; 554 alloc_cnt = hip->alloc_blocks; 555 if (blk_cnt == alloc_cnt) 556 goto out; 557 558 mutex_lock(&hip->extents_lock); 559 res = hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd); 560 if (res) { 561 mutex_unlock(&hip->extents_lock); 562 /* XXX: We lack error handling of hfsplus_file_truncate() */ 563 return; 564 } 565 while (1) { 566 if (alloc_cnt == hip->first_blocks) { 567 hfsplus_free_extents(sb, hip->first_extents, 568 alloc_cnt, alloc_cnt - blk_cnt); 569 hfsplus_dump_extent(hip->first_extents); 570 hip->first_blocks = blk_cnt; 571 break; 572 } 573 res = __hfsplus_ext_cache_extent(&fd, inode, alloc_cnt); 574 if (res) 575 break; 576 start = hip->cached_start; 577 hfsplus_free_extents(sb, hip->cached_extents, 578 alloc_cnt - start, alloc_cnt - blk_cnt); 579 hfsplus_dump_extent(hip->cached_extents); 580 if (blk_cnt > start) { 581 hip->extent_state |= HFSPLUS_EXT_DIRTY; 582 break; 583 } 584 alloc_cnt = start; 585 hip->cached_start = hip->cached_blocks = 0; 586 hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW); 587 hfs_brec_remove(&fd); 588 } 589 hfs_find_exit(&fd); 590 mutex_unlock(&hip->extents_lock); 591 592 hip->alloc_blocks = blk_cnt; 593 out: 594 hip->phys_size = inode->i_size; 595 hip->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> 596 sb->s_blocksize_bits; 597 inode_set_bytes(inode, hip->fs_blocks << sb->s_blocksize_bits); 598 hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY); 599 } 600