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, struct hfs_find_data *fd) 87 { 88 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 89 int res; 90 91 WARN_ON(!mutex_is_locked(&hip->extents_lock)); 92 93 hfsplus_ext_build_key(fd->search_key, inode->i_ino, hip->cached_start, 94 HFSPLUS_IS_RSRC(inode) ? 95 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA); 96 97 res = hfs_brec_find(fd); 98 if (hip->flags & HFSPLUS_FLG_EXT_NEW) { 99 if (res != -ENOENT) 100 return; 101 hfs_brec_insert(fd, hip->cached_extents, 102 sizeof(hfsplus_extent_rec)); 103 hip->flags &= ~(HFSPLUS_FLG_EXT_DIRTY | HFSPLUS_FLG_EXT_NEW); 104 } else { 105 if (res) 106 return; 107 hfs_bnode_write(fd->bnode, hip->cached_extents, 108 fd->entryoffset, fd->entrylength); 109 hip->flags &= ~HFSPLUS_FLG_EXT_DIRTY; 110 } 111 } 112 113 static void hfsplus_ext_write_extent_locked(struct inode *inode) 114 { 115 if (HFSPLUS_I(inode)->flags & HFSPLUS_FLG_EXT_DIRTY) { 116 struct hfs_find_data fd; 117 118 hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd); 119 __hfsplus_ext_write_extent(inode, &fd); 120 hfs_find_exit(&fd); 121 } 122 } 123 124 void hfsplus_ext_write_extent(struct inode *inode) 125 { 126 mutex_lock(&HFSPLUS_I(inode)->extents_lock); 127 hfsplus_ext_write_extent_locked(inode); 128 mutex_unlock(&HFSPLUS_I(inode)->extents_lock); 129 } 130 131 static inline int __hfsplus_ext_read_extent(struct hfs_find_data *fd, 132 struct hfsplus_extent *extent, 133 u32 cnid, u32 block, u8 type) 134 { 135 int res; 136 137 hfsplus_ext_build_key(fd->search_key, cnid, block, type); 138 fd->key->ext.cnid = 0; 139 res = hfs_brec_find(fd); 140 if (res && res != -ENOENT) 141 return res; 142 if (fd->key->ext.cnid != fd->search_key->ext.cnid || 143 fd->key->ext.fork_type != fd->search_key->ext.fork_type) 144 return -ENOENT; 145 if (fd->entrylength != sizeof(hfsplus_extent_rec)) 146 return -EIO; 147 hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfsplus_extent_rec)); 148 return 0; 149 } 150 151 static inline int __hfsplus_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block) 152 { 153 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 154 int res; 155 156 WARN_ON(!mutex_is_locked(&hip->extents_lock)); 157 158 if (hip->flags & HFSPLUS_FLG_EXT_DIRTY) 159 __hfsplus_ext_write_extent(inode, fd); 160 161 res = __hfsplus_ext_read_extent(fd, hip->cached_extents, inode->i_ino, 162 block, HFSPLUS_IS_RSRC(inode) ? 163 HFSPLUS_TYPE_RSRC : 164 HFSPLUS_TYPE_DATA); 165 if (!res) { 166 hip->cached_start = be32_to_cpu(fd->key->ext.start_block); 167 hip->cached_blocks = hfsplus_ext_block_count(hip->cached_extents); 168 } else { 169 hip->cached_start = hip->cached_blocks = 0; 170 hip->flags &= ~(HFSPLUS_FLG_EXT_DIRTY | HFSPLUS_FLG_EXT_NEW); 171 } 172 return res; 173 } 174 175 static int hfsplus_ext_read_extent(struct inode *inode, u32 block) 176 { 177 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 178 struct hfs_find_data fd; 179 int res; 180 181 if (block >= hip->cached_start && 182 block < hip->cached_start + hip->cached_blocks) 183 return 0; 184 185 hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd); 186 res = __hfsplus_ext_cache_extent(&fd, inode, block); 187 hfs_find_exit(&fd); 188 return res; 189 } 190 191 /* Get a block at iblock for inode, possibly allocating if create */ 192 int hfsplus_get_block(struct inode *inode, sector_t iblock, 193 struct buffer_head *bh_result, int create) 194 { 195 struct super_block *sb = inode->i_sb; 196 struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb); 197 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 198 int res = -EIO; 199 u32 ablock, dblock, mask; 200 int shift; 201 202 /* Convert inode block to disk allocation block */ 203 shift = sbi->alloc_blksz_shift - sb->s_blocksize_bits; 204 ablock = iblock >> sbi->fs_shift; 205 206 if (iblock >= hip->fs_blocks) { 207 if (iblock > hip->fs_blocks || !create) 208 return -EIO; 209 if (ablock >= hip->alloc_blocks) { 210 res = hfsplus_file_extend(inode); 211 if (res) 212 return res; 213 } 214 } else 215 create = 0; 216 217 if (ablock < hip->first_blocks) { 218 dblock = hfsplus_ext_find_block(hip->first_extents, ablock); 219 goto done; 220 } 221 222 if (inode->i_ino == HFSPLUS_EXT_CNID) 223 return -EIO; 224 225 mutex_lock(&hip->extents_lock); 226 res = hfsplus_ext_read_extent(inode, ablock); 227 if (!res) { 228 dblock = hfsplus_ext_find_block(hip->cached_extents, 229 ablock - hip->cached_start); 230 } else { 231 mutex_unlock(&hip->extents_lock); 232 return -EIO; 233 } 234 mutex_unlock(&hip->extents_lock); 235 236 done: 237 dprint(DBG_EXTENT, "get_block(%lu): %llu - %u\n", inode->i_ino, (long long)iblock, dblock); 238 mask = (1 << sbi->fs_shift) - 1; 239 map_bh(bh_result, sb, (dblock << sbi->fs_shift) + sbi->blockoffset + (iblock & mask)); 240 if (create) { 241 set_buffer_new(bh_result); 242 hip->phys_size += sb->s_blocksize; 243 hip->fs_blocks++; 244 inode_add_bytes(inode, sb->s_blocksize); 245 mark_inode_dirty(inode); 246 } 247 return 0; 248 } 249 250 static void hfsplus_dump_extent(struct hfsplus_extent *extent) 251 { 252 int i; 253 254 dprint(DBG_EXTENT, " "); 255 for (i = 0; i < 8; i++) 256 dprint(DBG_EXTENT, " %u:%u", be32_to_cpu(extent[i].start_block), 257 be32_to_cpu(extent[i].block_count)); 258 dprint(DBG_EXTENT, "\n"); 259 } 260 261 static int hfsplus_add_extent(struct hfsplus_extent *extent, u32 offset, 262 u32 alloc_block, u32 block_count) 263 { 264 u32 count, start; 265 int i; 266 267 hfsplus_dump_extent(extent); 268 for (i = 0; i < 8; extent++, i++) { 269 count = be32_to_cpu(extent->block_count); 270 if (offset == count) { 271 start = be32_to_cpu(extent->start_block); 272 if (alloc_block != start + count) { 273 if (++i >= 8) 274 return -ENOSPC; 275 extent++; 276 extent->start_block = cpu_to_be32(alloc_block); 277 } else 278 block_count += count; 279 extent->block_count = cpu_to_be32(block_count); 280 return 0; 281 } else if (offset < count) 282 break; 283 offset -= count; 284 } 285 /* panic? */ 286 return -EIO; 287 } 288 289 static int hfsplus_free_extents(struct super_block *sb, 290 struct hfsplus_extent *extent, 291 u32 offset, u32 block_nr) 292 { 293 u32 count, start; 294 int i; 295 296 hfsplus_dump_extent(extent); 297 for (i = 0; i < 8; extent++, i++) { 298 count = be32_to_cpu(extent->block_count); 299 if (offset == count) 300 goto found; 301 else if (offset < count) 302 break; 303 offset -= count; 304 } 305 /* panic? */ 306 return -EIO; 307 found: 308 for (;;) { 309 start = be32_to_cpu(extent->start_block); 310 if (count <= block_nr) { 311 hfsplus_block_free(sb, start, count); 312 extent->block_count = 0; 313 extent->start_block = 0; 314 block_nr -= count; 315 } else { 316 count -= block_nr; 317 hfsplus_block_free(sb, start + count, block_nr); 318 extent->block_count = cpu_to_be32(count); 319 block_nr = 0; 320 } 321 if (!block_nr || !i) 322 return 0; 323 i--; 324 extent--; 325 count = be32_to_cpu(extent->block_count); 326 } 327 } 328 329 int hfsplus_free_fork(struct super_block *sb, u32 cnid, struct hfsplus_fork_raw *fork, int type) 330 { 331 struct hfs_find_data fd; 332 hfsplus_extent_rec ext_entry; 333 u32 total_blocks, blocks, start; 334 int res, i; 335 336 total_blocks = be32_to_cpu(fork->total_blocks); 337 if (!total_blocks) 338 return 0; 339 340 blocks = 0; 341 for (i = 0; i < 8; i++) 342 blocks += be32_to_cpu(fork->extents[i].block_count); 343 344 res = hfsplus_free_extents(sb, fork->extents, blocks, blocks); 345 if (res) 346 return res; 347 if (total_blocks == blocks) 348 return 0; 349 350 hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd); 351 do { 352 res = __hfsplus_ext_read_extent(&fd, ext_entry, cnid, 353 total_blocks, type); 354 if (res) 355 break; 356 start = be32_to_cpu(fd.key->ext.start_block); 357 hfsplus_free_extents(sb, ext_entry, 358 total_blocks - start, 359 total_blocks); 360 hfs_brec_remove(&fd); 361 total_blocks = start; 362 } while (total_blocks > blocks); 363 hfs_find_exit(&fd); 364 365 return res; 366 } 367 368 int hfsplus_file_extend(struct inode *inode) 369 { 370 struct super_block *sb = inode->i_sb; 371 struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb); 372 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 373 u32 start, len, goal; 374 int res; 375 376 if (sbi->alloc_file->i_size * 8 < 377 sbi->total_blocks - sbi->free_blocks + 8) { 378 // extend alloc file 379 printk(KERN_ERR "hfs: extend alloc file! (%Lu,%u,%u)\n", 380 sbi->alloc_file->i_size * 8, 381 sbi->total_blocks, sbi->free_blocks); 382 return -ENOSPC; 383 } 384 385 mutex_lock(&hip->extents_lock); 386 if (hip->alloc_blocks == hip->first_blocks) 387 goal = hfsplus_ext_lastblock(hip->first_extents); 388 else { 389 res = hfsplus_ext_read_extent(inode, hip->alloc_blocks); 390 if (res) 391 goto out; 392 goal = hfsplus_ext_lastblock(hip->cached_extents); 393 } 394 395 len = hip->clump_blocks; 396 start = hfsplus_block_allocate(sb, sbi->total_blocks, goal, &len); 397 if (start >= sbi->total_blocks) { 398 start = hfsplus_block_allocate(sb, goal, 0, &len); 399 if (start >= goal) { 400 res = -ENOSPC; 401 goto out; 402 } 403 } 404 405 dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len); 406 407 if (hip->alloc_blocks <= hip->first_blocks) { 408 if (!hip->first_blocks) { 409 dprint(DBG_EXTENT, "first extents\n"); 410 /* no extents yet */ 411 hip->first_extents[0].start_block = cpu_to_be32(start); 412 hip->first_extents[0].block_count = cpu_to_be32(len); 413 res = 0; 414 } else { 415 /* try to append to extents in inode */ 416 res = hfsplus_add_extent(hip->first_extents, 417 hip->alloc_blocks, 418 start, len); 419 if (res == -ENOSPC) 420 goto insert_extent; 421 } 422 if (!res) { 423 hfsplus_dump_extent(hip->first_extents); 424 hip->first_blocks += len; 425 } 426 } else { 427 res = hfsplus_add_extent(hip->cached_extents, 428 hip->alloc_blocks - hip->cached_start, 429 start, len); 430 if (!res) { 431 hfsplus_dump_extent(hip->cached_extents); 432 hip->flags |= HFSPLUS_FLG_EXT_DIRTY; 433 hip->cached_blocks += len; 434 } else if (res == -ENOSPC) 435 goto insert_extent; 436 } 437 out: 438 mutex_unlock(&hip->extents_lock); 439 if (!res) { 440 hip->alloc_blocks += len; 441 mark_inode_dirty(inode); 442 } 443 return res; 444 445 insert_extent: 446 dprint(DBG_EXTENT, "insert new extent\n"); 447 hfsplus_ext_write_extent_locked(inode); 448 449 memset(hip->cached_extents, 0, sizeof(hfsplus_extent_rec)); 450 hip->cached_extents[0].start_block = cpu_to_be32(start); 451 hip->cached_extents[0].block_count = cpu_to_be32(len); 452 hfsplus_dump_extent(hip->cached_extents); 453 hip->flags |= HFSPLUS_FLG_EXT_DIRTY | HFSPLUS_FLG_EXT_NEW; 454 hip->cached_start = hip->alloc_blocks; 455 hip->cached_blocks = len; 456 457 res = 0; 458 goto out; 459 } 460 461 void hfsplus_file_truncate(struct inode *inode) 462 { 463 struct super_block *sb = inode->i_sb; 464 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 465 struct hfs_find_data fd; 466 u32 alloc_cnt, blk_cnt, start; 467 int res; 468 469 dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", 470 inode->i_ino, (long long)hip->phys_size, inode->i_size); 471 472 if (inode->i_size > hip->phys_size) { 473 struct address_space *mapping = inode->i_mapping; 474 struct page *page; 475 void *fsdata; 476 u32 size = inode->i_size; 477 int res; 478 479 res = pagecache_write_begin(NULL, mapping, size, 0, 480 AOP_FLAG_UNINTERRUPTIBLE, 481 &page, &fsdata); 482 if (res) 483 return; 484 res = pagecache_write_end(NULL, mapping, size, 0, 0, page, fsdata); 485 if (res < 0) 486 return; 487 mark_inode_dirty(inode); 488 return; 489 } else if (inode->i_size == hip->phys_size) 490 return; 491 492 blk_cnt = (inode->i_size + HFSPLUS_SB(sb)->alloc_blksz - 1) >> 493 HFSPLUS_SB(sb)->alloc_blksz_shift; 494 alloc_cnt = hip->alloc_blocks; 495 if (blk_cnt == alloc_cnt) 496 goto out; 497 498 mutex_lock(&hip->extents_lock); 499 hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd); 500 while (1) { 501 if (alloc_cnt == hip->first_blocks) { 502 hfsplus_free_extents(sb, hip->first_extents, 503 alloc_cnt, alloc_cnt - blk_cnt); 504 hfsplus_dump_extent(hip->first_extents); 505 hip->first_blocks = blk_cnt; 506 break; 507 } 508 res = __hfsplus_ext_cache_extent(&fd, inode, alloc_cnt); 509 if (res) 510 break; 511 start = hip->cached_start; 512 hfsplus_free_extents(sb, hip->cached_extents, 513 alloc_cnt - start, alloc_cnt - blk_cnt); 514 hfsplus_dump_extent(hip->cached_extents); 515 if (blk_cnt > start) { 516 hip->flags |= HFSPLUS_FLG_EXT_DIRTY; 517 break; 518 } 519 alloc_cnt = start; 520 hip->cached_start = hip->cached_blocks = 0; 521 hip->flags &= ~(HFSPLUS_FLG_EXT_DIRTY | HFSPLUS_FLG_EXT_NEW); 522 hfs_brec_remove(&fd); 523 } 524 hfs_find_exit(&fd); 525 mutex_unlock(&hip->extents_lock); 526 527 hip->alloc_blocks = blk_cnt; 528 out: 529 hip->phys_size = inode->i_size; 530 hip->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits; 531 inode_set_bytes(inode, hip->fs_blocks << sb->s_blocksize_bits); 532 mark_inode_dirty(inode); 533 } 534