itree.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475
  1. /*
  2. * linux/fs/sysv/itree.c
  3. *
  4. * Handling of indirect blocks' trees.
  5. * AV, Sep--Dec 2000
  6. */
  7. #include <linux/buffer_head.h>
  8. #include <linux/mount.h>
  9. #include <linux/string.h>
  10. #include "sysv.h"
  11. enum {DIRECT = 10, DEPTH = 4}; /* Have triple indirect */
  12. static inline void dirty_indirect(struct buffer_head *bh, struct inode *inode)
  13. {
  14. mark_buffer_dirty_inode(bh, inode);
  15. if (IS_SYNC(inode))
  16. sync_dirty_buffer(bh);
  17. }
  18. static int block_to_path(struct inode *inode, long block, int offsets[DEPTH])
  19. {
  20. struct super_block *sb = inode->i_sb;
  21. struct sysv_sb_info *sbi = SYSV_SB(sb);
  22. int ptrs_bits = sbi->s_ind_per_block_bits;
  23. unsigned long indirect_blocks = sbi->s_ind_per_block,
  24. double_blocks = sbi->s_ind_per_block_2;
  25. int n = 0;
  26. if (block < 0) {
  27. printk("sysv_block_map: block < 0\n");
  28. } else if (block < DIRECT) {
  29. offsets[n++] = block;
  30. } else if ( (block -= DIRECT) < indirect_blocks) {
  31. offsets[n++] = DIRECT;
  32. offsets[n++] = block;
  33. } else if ((block -= indirect_blocks) < double_blocks) {
  34. offsets[n++] = DIRECT+1;
  35. offsets[n++] = block >> ptrs_bits;
  36. offsets[n++] = block & (indirect_blocks - 1);
  37. } else if (((block -= double_blocks) >> (ptrs_bits * 2)) < indirect_blocks) {
  38. offsets[n++] = DIRECT+2;
  39. offsets[n++] = block >> (ptrs_bits * 2);
  40. offsets[n++] = (block >> ptrs_bits) & (indirect_blocks - 1);
  41. offsets[n++] = block & (indirect_blocks - 1);
  42. } else {
  43. /* nothing */;
  44. }
  45. return n;
  46. }
  47. static inline int block_to_cpu(struct sysv_sb_info *sbi, sysv_zone_t nr)
  48. {
  49. return sbi->s_block_base + fs32_to_cpu(sbi, nr);
  50. }
  51. typedef struct {
  52. sysv_zone_t *p;
  53. sysv_zone_t key;
  54. struct buffer_head *bh;
  55. } Indirect;
  56. static DEFINE_RWLOCK(pointers_lock);
  57. static inline void add_chain(Indirect *p, struct buffer_head *bh, sysv_zone_t *v)
  58. {
  59. p->key = *(p->p = v);
  60. p->bh = bh;
  61. }
  62. static inline int verify_chain(Indirect *from, Indirect *to)
  63. {
  64. while (from <= to && from->key == *from->p)
  65. from++;
  66. return (from > to);
  67. }
  68. static inline sysv_zone_t *block_end(struct buffer_head *bh)
  69. {
  70. return (sysv_zone_t*)((char*)bh->b_data + bh->b_size);
  71. }
  72. /*
  73. * Requires read_lock(&pointers_lock) or write_lock(&pointers_lock)
  74. */
  75. static Indirect *get_branch(struct inode *inode,
  76. int depth,
  77. int offsets[],
  78. Indirect chain[],
  79. int *err)
  80. {
  81. struct super_block *sb = inode->i_sb;
  82. Indirect *p = chain;
  83. struct buffer_head *bh;
  84. *err = 0;
  85. add_chain(chain, NULL, SYSV_I(inode)->i_data + *offsets);
  86. if (!p->key)
  87. goto no_block;
  88. while (--depth) {
  89. int block = block_to_cpu(SYSV_SB(sb), p->key);
  90. bh = sb_bread(sb, block);
  91. if (!bh)
  92. goto failure;
  93. if (!verify_chain(chain, p))
  94. goto changed;
  95. add_chain(++p, bh, (sysv_zone_t*)bh->b_data + *++offsets);
  96. if (!p->key)
  97. goto no_block;
  98. }
  99. return NULL;
  100. changed:
  101. brelse(bh);
  102. *err = -EAGAIN;
  103. goto no_block;
  104. failure:
  105. *err = -EIO;
  106. no_block:
  107. return p;
  108. }
  109. static int alloc_branch(struct inode *inode,
  110. int num,
  111. int *offsets,
  112. Indirect *branch)
  113. {
  114. int blocksize = inode->i_sb->s_blocksize;
  115. int n = 0;
  116. int i;
  117. branch[0].key = sysv_new_block(inode->i_sb);
  118. if (branch[0].key) for (n = 1; n < num; n++) {
  119. struct buffer_head *bh;
  120. int parent;
  121. /* Allocate the next block */
  122. branch[n].key = sysv_new_block(inode->i_sb);
  123. if (!branch[n].key)
  124. break;
  125. /*
  126. * Get buffer_head for parent block, zero it out and set
  127. * the pointer to new one, then send parent to disk.
  128. */
  129. parent = block_to_cpu(SYSV_SB(inode->i_sb), branch[n-1].key);
  130. bh = sb_getblk(inode->i_sb, parent);
  131. lock_buffer(bh);
  132. memset(bh->b_data, 0, blocksize);
  133. branch[n].bh = bh;
  134. branch[n].p = (sysv_zone_t*) bh->b_data + offsets[n];
  135. *branch[n].p = branch[n].key;
  136. set_buffer_uptodate(bh);
  137. unlock_buffer(bh);
  138. dirty_indirect(bh, inode);
  139. }
  140. if (n == num)
  141. return 0;
  142. /* Allocation failed, free what we already allocated */
  143. for (i = 1; i < n; i++)
  144. bforget(branch[i].bh);
  145. for (i = 0; i < n; i++)
  146. sysv_free_block(inode->i_sb, branch[i].key);
  147. return -ENOSPC;
  148. }
  149. static inline int splice_branch(struct inode *inode,
  150. Indirect chain[],
  151. Indirect *where,
  152. int num)
  153. {
  154. int i;
  155. /* Verify that place we are splicing to is still there and vacant */
  156. write_lock(&pointers_lock);
  157. if (!verify_chain(chain, where-1) || *where->p)
  158. goto changed;
  159. *where->p = where->key;
  160. write_unlock(&pointers_lock);
  161. inode->i_ctime = CURRENT_TIME_SEC;
  162. /* had we spliced it onto indirect block? */
  163. if (where->bh)
  164. dirty_indirect(where->bh, inode);
  165. if (IS_SYNC(inode))
  166. sysv_sync_inode(inode);
  167. else
  168. mark_inode_dirty(inode);
  169. return 0;
  170. changed:
  171. write_unlock(&pointers_lock);
  172. for (i = 1; i < num; i++)
  173. bforget(where[i].bh);
  174. for (i = 0; i < num; i++)
  175. sysv_free_block(inode->i_sb, where[i].key);
  176. return -EAGAIN;
  177. }
  178. static int get_block(struct inode *inode, sector_t iblock, struct buffer_head *bh_result, int create)
  179. {
  180. int err = -EIO;
  181. int offsets[DEPTH];
  182. Indirect chain[DEPTH];
  183. struct super_block *sb = inode->i_sb;
  184. Indirect *partial;
  185. int left;
  186. int depth = block_to_path(inode, iblock, offsets);
  187. if (depth == 0)
  188. goto out;
  189. reread:
  190. read_lock(&pointers_lock);
  191. partial = get_branch(inode, depth, offsets, chain, &err);
  192. read_unlock(&pointers_lock);
  193. /* Simplest case - block found, no allocation needed */
  194. if (!partial) {
  195. got_it:
  196. map_bh(bh_result, sb, block_to_cpu(SYSV_SB(sb),
  197. chain[depth-1].key));
  198. /* Clean up and exit */
  199. partial = chain+depth-1; /* the whole chain */
  200. goto cleanup;
  201. }
  202. /* Next simple case - plain lookup or failed read of indirect block */
  203. if (!create || err == -EIO) {
  204. cleanup:
  205. while (partial > chain) {
  206. brelse(partial->bh);
  207. partial--;
  208. }
  209. out:
  210. return err;
  211. }
  212. /*
  213. * Indirect block might be removed by truncate while we were
  214. * reading it. Handling of that case (forget what we've got and
  215. * reread) is taken out of the main path.
  216. */
  217. if (err == -EAGAIN)
  218. goto changed;
  219. left = (chain + depth) - partial;
  220. err = alloc_branch(inode, left, offsets+(partial-chain), partial);
  221. if (err)
  222. goto cleanup;
  223. if (splice_branch(inode, chain, partial, left) < 0)
  224. goto changed;
  225. set_buffer_new(bh_result);
  226. goto got_it;
  227. changed:
  228. while (partial > chain) {
  229. brelse(partial->bh);
  230. partial--;
  231. }
  232. goto reread;
  233. }
  234. static inline int all_zeroes(sysv_zone_t *p, sysv_zone_t *q)
  235. {
  236. while (p < q)
  237. if (*p++)
  238. return 0;
  239. return 1;
  240. }
  241. static Indirect *find_shared(struct inode *inode,
  242. int depth,
  243. int offsets[],
  244. Indirect chain[],
  245. sysv_zone_t *top)
  246. {
  247. Indirect *partial, *p;
  248. int k, err;
  249. *top = 0;
  250. for (k = depth; k > 1 && !offsets[k-1]; k--)
  251. ;
  252. write_lock(&pointers_lock);
  253. partial = get_branch(inode, k, offsets, chain, &err);
  254. if (!partial)
  255. partial = chain + k-1;
  256. /*
  257. * If the branch acquired continuation since we've looked at it -
  258. * fine, it should all survive and (new) top doesn't belong to us.
  259. */
  260. if (!partial->key && *partial->p) {
  261. write_unlock(&pointers_lock);
  262. goto no_top;
  263. }
  264. for (p=partial; p>chain && all_zeroes((sysv_zone_t*)p->bh->b_data,p->p); p--)
  265. ;
  266. /*
  267. * OK, we've found the last block that must survive. The rest of our
  268. * branch should be detached before unlocking. However, if that rest
  269. * of branch is all ours and does not grow immediately from the inode
  270. * it's easier to cheat and just decrement partial->p.
  271. */
  272. if (p == chain + k - 1 && p > chain) {
  273. p->p--;
  274. } else {
  275. *top = *p->p;
  276. *p->p = 0;
  277. }
  278. write_unlock(&pointers_lock);
  279. while (partial > p) {
  280. brelse(partial->bh);
  281. partial--;
  282. }
  283. no_top:
  284. return partial;
  285. }
  286. static inline void free_data(struct inode *inode, sysv_zone_t *p, sysv_zone_t *q)
  287. {
  288. for ( ; p < q ; p++) {
  289. sysv_zone_t nr = *p;
  290. if (nr) {
  291. *p = 0;
  292. sysv_free_block(inode->i_sb, nr);
  293. mark_inode_dirty(inode);
  294. }
  295. }
  296. }
  297. static void free_branches(struct inode *inode, sysv_zone_t *p, sysv_zone_t *q, int depth)
  298. {
  299. struct buffer_head * bh;
  300. struct super_block *sb = inode->i_sb;
  301. if (depth--) {
  302. for ( ; p < q ; p++) {
  303. int block;
  304. sysv_zone_t nr = *p;
  305. if (!nr)
  306. continue;
  307. *p = 0;
  308. block = block_to_cpu(SYSV_SB(sb), nr);
  309. bh = sb_bread(sb, block);
  310. if (!bh)
  311. continue;
  312. free_branches(inode, (sysv_zone_t*)bh->b_data,
  313. block_end(bh), depth);
  314. bforget(bh);
  315. sysv_free_block(sb, nr);
  316. mark_inode_dirty(inode);
  317. }
  318. } else
  319. free_data(inode, p, q);
  320. }
  321. void sysv_truncate (struct inode * inode)
  322. {
  323. sysv_zone_t *i_data = SYSV_I(inode)->i_data;
  324. int offsets[DEPTH];
  325. Indirect chain[DEPTH];
  326. Indirect *partial;
  327. sysv_zone_t nr = 0;
  328. int n;
  329. long iblock;
  330. unsigned blocksize;
  331. if (!(S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
  332. S_ISLNK(inode->i_mode)))
  333. return;
  334. blocksize = inode->i_sb->s_blocksize;
  335. iblock = (inode->i_size + blocksize-1)
  336. >> inode->i_sb->s_blocksize_bits;
  337. block_truncate_page(inode->i_mapping, inode->i_size, get_block);
  338. n = block_to_path(inode, iblock, offsets);
  339. if (n == 0)
  340. return;
  341. if (n == 1) {
  342. free_data(inode, i_data+offsets[0], i_data + DIRECT);
  343. goto do_indirects;
  344. }
  345. partial = find_shared(inode, n, offsets, chain, &nr);
  346. /* Kill the top of shared branch (already detached) */
  347. if (nr) {
  348. if (partial == chain)
  349. mark_inode_dirty(inode);
  350. else
  351. dirty_indirect(partial->bh, inode);
  352. free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
  353. }
  354. /* Clear the ends of indirect blocks on the shared branch */
  355. while (partial > chain) {
  356. free_branches(inode, partial->p + 1, block_end(partial->bh),
  357. (chain+n-1) - partial);
  358. dirty_indirect(partial->bh, inode);
  359. brelse (partial->bh);
  360. partial--;
  361. }
  362. do_indirects:
  363. /* Kill the remaining (whole) subtrees (== subtrees deeper than...) */
  364. while (n < DEPTH) {
  365. nr = i_data[DIRECT + n - 1];
  366. if (nr) {
  367. i_data[DIRECT + n - 1] = 0;
  368. mark_inode_dirty(inode);
  369. free_branches(inode, &nr, &nr+1, n);
  370. }
  371. n++;
  372. }
  373. inode->i_mtime = inode->i_ctime = CURRENT_TIME_SEC;
  374. if (IS_SYNC(inode))
  375. sysv_sync_inode (inode);
  376. else
  377. mark_inode_dirty(inode);
  378. }
  379. static unsigned sysv_nblocks(struct super_block *s, loff_t size)
  380. {
  381. struct sysv_sb_info *sbi = SYSV_SB(s);
  382. int ptrs_bits = sbi->s_ind_per_block_bits;
  383. unsigned blocks, res, direct = DIRECT, i = DEPTH;
  384. blocks = (size + s->s_blocksize - 1) >> s->s_blocksize_bits;
  385. res = blocks;
  386. while (--i && blocks > direct) {
  387. blocks = ((blocks - direct - 1) >> ptrs_bits) + 1;
  388. res += blocks;
  389. direct = 1;
  390. }
  391. return blocks;
  392. }
  393. int sysv_getattr(struct vfsmount *mnt, struct dentry *dentry, struct kstat *stat)
  394. {
  395. struct super_block *s = mnt->mnt_sb;
  396. generic_fillattr(dentry->d_inode, stat);
  397. stat->blocks = (s->s_blocksize / 512) * sysv_nblocks(s, stat->size);
  398. stat->blksize = s->s_blocksize;
  399. return 0;
  400. }
  401. static int sysv_writepage(struct page *page, struct writeback_control *wbc)
  402. {
  403. return block_write_full_page(page,get_block,wbc);
  404. }
  405. static int sysv_readpage(struct file *file, struct page *page)
  406. {
  407. return block_read_full_page(page,get_block);
  408. }
  409. static int sysv_prepare_write(struct file *file, struct page *page, unsigned from, unsigned to)
  410. {
  411. return block_prepare_write(page,from,to,get_block);
  412. }
  413. static sector_t sysv_bmap(struct address_space *mapping, sector_t block)
  414. {
  415. return generic_block_bmap(mapping,block,get_block);
  416. }
  417. const struct address_space_operations sysv_aops = {
  418. .readpage = sysv_readpage,
  419. .writepage = sysv_writepage,
  420. .sync_page = block_sync_page,
  421. .prepare_write = sysv_prepare_write,
  422. .commit_write = generic_commit_write,
  423. .bmap = sysv_bmap
  424. };