itree.c 12 KB

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