extents.c 15 KB

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