1 /* 2 * linux/fs/hfs/extent.c 3 * 4 * Copyright (C) 1995-1997 Paul H. Hargrove 5 * (C) 2003 Ardis Technologies <roman@ardistech.com> 6 * This file may be distributed under the terms of the GNU General Public License. 7 * 8 * This file contains the functions related to the extents B-tree. 9 */ 10 11 #include <linux/pagemap.h> 12 13 #include "hfs_fs.h" 14 #include "btree.h" 15 16 /*================ File-local functions ================*/ 17 18 /* 19 * build_key 20 */ 21 static void hfs_ext_build_key(hfs_btree_key *key, u32 cnid, u16 block, u8 type) 22 { 23 key->key_len = 7; 24 key->ext.FkType = type; 25 key->ext.FNum = cpu_to_be32(cnid); 26 key->ext.FABN = cpu_to_be16(block); 27 } 28 29 /* 30 * hfs_ext_compare() 31 * 32 * Description: 33 * This is the comparison function used for the extents B-tree. In 34 * comparing extent B-tree entries, the file id is the most 35 * significant field (compared as unsigned ints); the fork type is 36 * the second most significant field (compared as unsigned chars); 37 * and the allocation block number field is the least significant 38 * (compared as unsigned ints). 39 * Input Variable(s): 40 * struct hfs_ext_key *key1: pointer to the first key to compare 41 * struct hfs_ext_key *key2: pointer to the second key to compare 42 * Output Variable(s): 43 * NONE 44 * Returns: 45 * int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2 46 * Preconditions: 47 * key1 and key2 point to "valid" (struct hfs_ext_key)s. 48 * Postconditions: 49 * This function has no side-effects */ 50 int hfs_ext_keycmp(const btree_key *key1, const btree_key *key2) 51 { 52 __be32 fnum1, fnum2; 53 __be16 block1, block2; 54 55 fnum1 = key1->ext.FNum; 56 fnum2 = key2->ext.FNum; 57 if (fnum1 != fnum2) 58 return be32_to_cpu(fnum1) < be32_to_cpu(fnum2) ? -1 : 1; 59 if (key1->ext.FkType != key2->ext.FkType) 60 return key1->ext.FkType < key2->ext.FkType ? -1 : 1; 61 62 block1 = key1->ext.FABN; 63 block2 = key2->ext.FABN; 64 if (block1 == block2) 65 return 0; 66 return be16_to_cpu(block1) < be16_to_cpu(block2) ? -1 : 1; 67 } 68 69 /* 70 * hfs_ext_find_block 71 * 72 * Find a block within an extent record 73 */ 74 static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off) 75 { 76 int i; 77 u16 count; 78 79 for (i = 0; i < 3; ext++, i++) { 80 count = be16_to_cpu(ext->count); 81 if (off < count) 82 return be16_to_cpu(ext->block) + off; 83 off -= count; 84 } 85 /* panic? */ 86 return 0; 87 } 88 89 static int hfs_ext_block_count(struct hfs_extent *ext) 90 { 91 int i; 92 u16 count = 0; 93 94 for (i = 0; i < 3; ext++, i++) 95 count += be16_to_cpu(ext->count); 96 return count; 97 } 98 99 static u16 hfs_ext_lastblock(struct hfs_extent *ext) 100 { 101 int i; 102 103 ext += 2; 104 for (i = 0; i < 2; ext--, i++) 105 if (ext->count) 106 break; 107 return be16_to_cpu(ext->block) + be16_to_cpu(ext->count); 108 } 109 110 static int __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd) 111 { 112 int res; 113 114 hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start, 115 HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA); 116 res = hfs_brec_find(fd); 117 if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) { 118 if (res != -ENOENT) 119 return res; 120 /* Fail early and avoid ENOSPC during the btree operation */ 121 res = hfs_bmap_reserve(fd->tree, fd->tree->depth + 1); 122 if (res) 123 return res; 124 hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec)); 125 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW); 126 } else { 127 if (res) 128 return res; 129 hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength); 130 HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY; 131 } 132 return 0; 133 } 134 135 int hfs_ext_write_extent(struct inode *inode) 136 { 137 struct hfs_find_data fd; 138 int res = 0; 139 140 if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) { 141 res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd); 142 if (res) 143 return res; 144 res = __hfs_ext_write_extent(inode, &fd); 145 hfs_find_exit(&fd); 146 } 147 return res; 148 } 149 150 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent, 151 u32 cnid, u32 block, u8 type) 152 { 153 int res; 154 155 hfs_ext_build_key(fd->search_key, cnid, block, type); 156 fd->key->ext.FNum = 0; 157 res = hfs_brec_find(fd); 158 if (res && res != -ENOENT) 159 return res; 160 if (fd->key->ext.FNum != fd->search_key->ext.FNum || 161 fd->key->ext.FkType != fd->search_key->ext.FkType) 162 return -ENOENT; 163 if (fd->entrylength != sizeof(hfs_extent_rec)) 164 return -EIO; 165 hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec)); 166 return 0; 167 } 168 169 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block) 170 { 171 int res; 172 173 if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) { 174 res = __hfs_ext_write_extent(inode, fd); 175 if (res) 176 return res; 177 } 178 179 res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino, 180 block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA); 181 if (!res) { 182 HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN); 183 HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents); 184 } else { 185 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0; 186 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW); 187 } 188 return res; 189 } 190 191 static int hfs_ext_read_extent(struct inode *inode, u16 block) 192 { 193 struct hfs_find_data fd; 194 int res; 195 196 if (block >= HFS_I(inode)->cached_start && 197 block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks) 198 return 0; 199 200 res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd); 201 if (!res) { 202 res = __hfs_ext_cache_extent(&fd, inode, block); 203 hfs_find_exit(&fd); 204 } 205 return res; 206 } 207 208 static void hfs_dump_extent(struct hfs_extent *extent) 209 { 210 int i; 211 212 hfs_dbg(EXTENT, " "); 213 for (i = 0; i < 3; i++) 214 hfs_dbg_cont(EXTENT, " %u:%u", 215 be16_to_cpu(extent[i].block), 216 be16_to_cpu(extent[i].count)); 217 hfs_dbg_cont(EXTENT, "\n"); 218 } 219 220 static int hfs_add_extent(struct hfs_extent *extent, u16 offset, 221 u16 alloc_block, u16 block_count) 222 { 223 u16 count, start; 224 int i; 225 226 hfs_dump_extent(extent); 227 for (i = 0; i < 3; extent++, i++) { 228 count = be16_to_cpu(extent->count); 229 if (offset == count) { 230 start = be16_to_cpu(extent->block); 231 if (alloc_block != start + count) { 232 if (++i >= 3) 233 return -ENOSPC; 234 extent++; 235 extent->block = cpu_to_be16(alloc_block); 236 } else 237 block_count += count; 238 extent->count = cpu_to_be16(block_count); 239 return 0; 240 } else if (offset < count) 241 break; 242 offset -= count; 243 } 244 /* panic? */ 245 return -EIO; 246 } 247 248 static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent, 249 u16 offset, u16 block_nr) 250 { 251 u16 count, start; 252 int i; 253 254 hfs_dump_extent(extent); 255 for (i = 0; i < 3; extent++, i++) { 256 count = be16_to_cpu(extent->count); 257 if (offset == count) 258 goto found; 259 else if (offset < count) 260 break; 261 offset -= count; 262 } 263 /* panic? */ 264 return -EIO; 265 found: 266 for (;;) { 267 start = be16_to_cpu(extent->block); 268 if (count <= block_nr) { 269 hfs_clear_vbm_bits(sb, start, count); 270 extent->block = 0; 271 extent->count = 0; 272 block_nr -= count; 273 } else { 274 count -= block_nr; 275 hfs_clear_vbm_bits(sb, start + count, block_nr); 276 extent->count = cpu_to_be16(count); 277 block_nr = 0; 278 } 279 if (!block_nr || !i) 280 return 0; 281 i--; 282 extent--; 283 count = be16_to_cpu(extent->count); 284 } 285 } 286 287 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type) 288 { 289 struct hfs_find_data fd; 290 u32 total_blocks, blocks, start; 291 u32 cnid = be32_to_cpu(file->FlNum); 292 struct hfs_extent *extent; 293 int res, i; 294 295 if (type == HFS_FK_DATA) { 296 total_blocks = be32_to_cpu(file->PyLen); 297 extent = file->ExtRec; 298 } else { 299 total_blocks = be32_to_cpu(file->RPyLen); 300 extent = file->RExtRec; 301 } 302 total_blocks /= HFS_SB(sb)->alloc_blksz; 303 if (!total_blocks) 304 return 0; 305 306 blocks = 0; 307 for (i = 0; i < 3; i++) 308 blocks += be16_to_cpu(extent[i].count); 309 310 res = hfs_free_extents(sb, extent, blocks, blocks); 311 if (res) 312 return res; 313 if (total_blocks == blocks) 314 return 0; 315 316 res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd); 317 if (res) 318 return res; 319 do { 320 res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type); 321 if (res) 322 break; 323 start = be16_to_cpu(fd.key->ext.FABN); 324 hfs_free_extents(sb, extent, total_blocks - start, total_blocks); 325 hfs_brec_remove(&fd); 326 total_blocks = start; 327 } while (total_blocks > blocks); 328 hfs_find_exit(&fd); 329 330 return res; 331 } 332 333 /* 334 * hfs_get_block 335 */ 336 int hfs_get_block(struct inode *inode, sector_t block, 337 struct buffer_head *bh_result, int create) 338 { 339 struct super_block *sb; 340 u16 dblock, ablock; 341 int res; 342 343 sb = inode->i_sb; 344 /* Convert inode block to disk allocation block */ 345 ablock = (u32)block / HFS_SB(sb)->fs_div; 346 347 if (block >= HFS_I(inode)->fs_blocks) { 348 if (!create) 349 return 0; 350 if (block > HFS_I(inode)->fs_blocks) 351 return -EIO; 352 if (ablock >= HFS_I(inode)->alloc_blocks) { 353 res = hfs_extend_file(inode); 354 if (res) 355 return res; 356 } 357 } else 358 create = 0; 359 360 if (ablock < HFS_I(inode)->first_blocks) { 361 dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock); 362 goto done; 363 } 364 365 mutex_lock(&HFS_I(inode)->extents_lock); 366 res = hfs_ext_read_extent(inode, ablock); 367 if (!res) 368 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents, 369 ablock - HFS_I(inode)->cached_start); 370 else { 371 mutex_unlock(&HFS_I(inode)->extents_lock); 372 return -EIO; 373 } 374 mutex_unlock(&HFS_I(inode)->extents_lock); 375 376 done: 377 map_bh(bh_result, sb, HFS_SB(sb)->fs_start + 378 dblock * HFS_SB(sb)->fs_div + 379 (u32)block % HFS_SB(sb)->fs_div); 380 381 if (create) { 382 set_buffer_new(bh_result); 383 HFS_I(inode)->phys_size += sb->s_blocksize; 384 HFS_I(inode)->fs_blocks++; 385 inode_add_bytes(inode, sb->s_blocksize); 386 mark_inode_dirty(inode); 387 } 388 return 0; 389 } 390 391 int hfs_extend_file(struct inode *inode) 392 { 393 struct super_block *sb = inode->i_sb; 394 u32 start, len, goal; 395 int res; 396 397 mutex_lock(&HFS_I(inode)->extents_lock); 398 if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) 399 goal = hfs_ext_lastblock(HFS_I(inode)->first_extents); 400 else { 401 res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks); 402 if (res) 403 goto out; 404 goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents); 405 } 406 407 len = HFS_I(inode)->clump_blocks; 408 start = hfs_vbm_search_free(sb, goal, &len); 409 if (!len) { 410 res = -ENOSPC; 411 goto out; 412 } 413 414 hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len); 415 if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) { 416 if (!HFS_I(inode)->first_blocks) { 417 hfs_dbg(EXTENT, "first extents\n"); 418 /* no extents yet */ 419 HFS_I(inode)->first_extents[0].block = cpu_to_be16(start); 420 HFS_I(inode)->first_extents[0].count = cpu_to_be16(len); 421 res = 0; 422 } else { 423 /* try to append to extents in inode */ 424 res = hfs_add_extent(HFS_I(inode)->first_extents, 425 HFS_I(inode)->alloc_blocks, 426 start, len); 427 if (res == -ENOSPC) 428 goto insert_extent; 429 } 430 if (!res) { 431 hfs_dump_extent(HFS_I(inode)->first_extents); 432 HFS_I(inode)->first_blocks += len; 433 } 434 } else { 435 res = hfs_add_extent(HFS_I(inode)->cached_extents, 436 HFS_I(inode)->alloc_blocks - 437 HFS_I(inode)->cached_start, 438 start, len); 439 if (!res) { 440 hfs_dump_extent(HFS_I(inode)->cached_extents); 441 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY; 442 HFS_I(inode)->cached_blocks += len; 443 } else if (res == -ENOSPC) 444 goto insert_extent; 445 } 446 out: 447 mutex_unlock(&HFS_I(inode)->extents_lock); 448 if (!res) { 449 HFS_I(inode)->alloc_blocks += len; 450 mark_inode_dirty(inode); 451 if (inode->i_ino < HFS_FIRSTUSER_CNID) 452 set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags); 453 set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags); 454 hfs_mark_mdb_dirty(sb); 455 } 456 return res; 457 458 insert_extent: 459 hfs_dbg(EXTENT, "insert new extent\n"); 460 res = hfs_ext_write_extent(inode); 461 if (res) 462 goto out; 463 464 memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec)); 465 HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start); 466 HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len); 467 hfs_dump_extent(HFS_I(inode)->cached_extents); 468 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW; 469 HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks; 470 HFS_I(inode)->cached_blocks = len; 471 472 res = 0; 473 goto out; 474 } 475 476 void hfs_file_truncate(struct inode *inode) 477 { 478 struct super_block *sb = inode->i_sb; 479 struct hfs_find_data fd; 480 u16 blk_cnt, alloc_cnt, start; 481 u32 size; 482 int res; 483 484 hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n", 485 inode->i_ino, (long long)HFS_I(inode)->phys_size, 486 inode->i_size); 487 if (inode->i_size > HFS_I(inode)->phys_size) { 488 struct address_space *mapping = inode->i_mapping; 489 void *fsdata; 490 struct page *page; 491 492 /* XXX: Can use generic_cont_expand? */ 493 size = inode->i_size - 1; 494 res = hfs_write_begin(NULL, mapping, size + 1, 0, &page, 495 &fsdata); 496 if (!res) { 497 res = generic_write_end(NULL, mapping, size + 1, 0, 0, 498 page, fsdata); 499 } 500 if (res) 501 inode->i_size = HFS_I(inode)->phys_size; 502 return; 503 } else if (inode->i_size == HFS_I(inode)->phys_size) 504 return; 505 size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1; 506 blk_cnt = size / HFS_SB(sb)->alloc_blksz; 507 alloc_cnt = HFS_I(inode)->alloc_blocks; 508 if (blk_cnt == alloc_cnt) 509 goto out; 510 511 mutex_lock(&HFS_I(inode)->extents_lock); 512 res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd); 513 if (res) { 514 mutex_unlock(&HFS_I(inode)->extents_lock); 515 /* XXX: We lack error handling of hfs_file_truncate() */ 516 return; 517 } 518 while (1) { 519 if (alloc_cnt == HFS_I(inode)->first_blocks) { 520 hfs_free_extents(sb, HFS_I(inode)->first_extents, 521 alloc_cnt, alloc_cnt - blk_cnt); 522 hfs_dump_extent(HFS_I(inode)->first_extents); 523 HFS_I(inode)->first_blocks = blk_cnt; 524 break; 525 } 526 res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt); 527 if (res) 528 break; 529 start = HFS_I(inode)->cached_start; 530 hfs_free_extents(sb, HFS_I(inode)->cached_extents, 531 alloc_cnt - start, alloc_cnt - blk_cnt); 532 hfs_dump_extent(HFS_I(inode)->cached_extents); 533 if (blk_cnt > start) { 534 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY; 535 break; 536 } 537 alloc_cnt = start; 538 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0; 539 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW); 540 hfs_brec_remove(&fd); 541 } 542 hfs_find_exit(&fd); 543 mutex_unlock(&HFS_I(inode)->extents_lock); 544 545 HFS_I(inode)->alloc_blocks = blk_cnt; 546 out: 547 HFS_I(inode)->phys_size = inode->i_size; 548 HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits; 549 inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits); 550 mark_inode_dirty(inode); 551 } 552