itree.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509
  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. if (!bh) {
  133. sysv_free_block(inode->i_sb, branch[n].key);
  134. break;
  135. }
  136. lock_buffer(bh);
  137. memset(bh->b_data, 0, blocksize);
  138. branch[n].bh = bh;
  139. branch[n].p = (sysv_zone_t*) bh->b_data + offsets[n];
  140. *branch[n].p = branch[n].key;
  141. set_buffer_uptodate(bh);
  142. unlock_buffer(bh);
  143. dirty_indirect(bh, inode);
  144. }
  145. if (n == num)
  146. return 0;
  147. /* Allocation failed, free what we already allocated */
  148. for (i = 1; i < n; i++)
  149. bforget(branch[i].bh);
  150. for (i = 0; i < n; i++)
  151. sysv_free_block(inode->i_sb, branch[i].key);
  152. return -ENOSPC;
  153. }
  154. static inline int splice_branch(struct inode *inode,
  155. Indirect chain[],
  156. Indirect *where,
  157. int num)
  158. {
  159. int i;
  160. /* Verify that place we are splicing to is still there and vacant */
  161. write_lock(&pointers_lock);
  162. if (!verify_chain(chain, where-1) || *where->p)
  163. goto changed;
  164. *where->p = where->key;
  165. write_unlock(&pointers_lock);
  166. inode->i_ctime = current_time(inode);
  167. /* had we spliced it onto indirect block? */
  168. if (where->bh)
  169. dirty_indirect(where->bh, inode);
  170. if (IS_SYNC(inode))
  171. sysv_sync_inode(inode);
  172. else
  173. mark_inode_dirty(inode);
  174. return 0;
  175. changed:
  176. write_unlock(&pointers_lock);
  177. for (i = 1; i < num; i++)
  178. bforget(where[i].bh);
  179. for (i = 0; i < num; i++)
  180. sysv_free_block(inode->i_sb, where[i].key);
  181. return -EAGAIN;
  182. }
  183. static int get_block(struct inode *inode, sector_t iblock, struct buffer_head *bh_result, int create)
  184. {
  185. int err = -EIO;
  186. int offsets[DEPTH];
  187. Indirect chain[DEPTH];
  188. struct super_block *sb = inode->i_sb;
  189. Indirect *partial;
  190. int left;
  191. int depth = block_to_path(inode, iblock, offsets);
  192. if (depth == 0)
  193. goto out;
  194. reread:
  195. read_lock(&pointers_lock);
  196. partial = get_branch(inode, depth, offsets, chain, &err);
  197. read_unlock(&pointers_lock);
  198. /* Simplest case - block found, no allocation needed */
  199. if (!partial) {
  200. got_it:
  201. map_bh(bh_result, sb, block_to_cpu(SYSV_SB(sb),
  202. chain[depth-1].key));
  203. /* Clean up and exit */
  204. partial = chain+depth-1; /* the whole chain */
  205. goto cleanup;
  206. }
  207. /* Next simple case - plain lookup or failed read of indirect block */
  208. if (!create || err == -EIO) {
  209. cleanup:
  210. while (partial > chain) {
  211. brelse(partial->bh);
  212. partial--;
  213. }
  214. out:
  215. return err;
  216. }
  217. /*
  218. * Indirect block might be removed by truncate while we were
  219. * reading it. Handling of that case (forget what we've got and
  220. * reread) is taken out of the main path.
  221. */
  222. if (err == -EAGAIN)
  223. goto changed;
  224. left = (chain + depth) - partial;
  225. err = alloc_branch(inode, left, offsets+(partial-chain), partial);
  226. if (err)
  227. goto cleanup;
  228. if (splice_branch(inode, chain, partial, left) < 0)
  229. goto changed;
  230. set_buffer_new(bh_result);
  231. goto got_it;
  232. changed:
  233. while (partial > chain) {
  234. brelse(partial->bh);
  235. partial--;
  236. }
  237. goto reread;
  238. }
  239. static inline int all_zeroes(sysv_zone_t *p, sysv_zone_t *q)
  240. {
  241. while (p < q)
  242. if (*p++)
  243. return 0;
  244. return 1;
  245. }
  246. static Indirect *find_shared(struct inode *inode,
  247. int depth,
  248. int offsets[],
  249. Indirect chain[],
  250. sysv_zone_t *top)
  251. {
  252. Indirect *partial, *p;
  253. int k, err;
  254. *top = 0;
  255. for (k = depth; k > 1 && !offsets[k-1]; k--)
  256. ;
  257. write_lock(&pointers_lock);
  258. partial = get_branch(inode, k, offsets, chain, &err);
  259. if (!partial)
  260. partial = chain + k-1;
  261. /*
  262. * If the branch acquired continuation since we've looked at it -
  263. * fine, it should all survive and (new) top doesn't belong to us.
  264. */
  265. if (!partial->key && *partial->p) {
  266. write_unlock(&pointers_lock);
  267. goto no_top;
  268. }
  269. for (p=partial; p>chain && all_zeroes((sysv_zone_t*)p->bh->b_data,p->p); p--)
  270. ;
  271. /*
  272. * OK, we've found the last block that must survive. The rest of our
  273. * branch should be detached before unlocking. However, if that rest
  274. * of branch is all ours and does not grow immediately from the inode
  275. * it's easier to cheat and just decrement partial->p.
  276. */
  277. if (p == chain + k - 1 && p > chain) {
  278. p->p--;
  279. } else {
  280. *top = *p->p;
  281. *p->p = 0;
  282. }
  283. write_unlock(&pointers_lock);
  284. while (partial > p) {
  285. brelse(partial->bh);
  286. partial--;
  287. }
  288. no_top:
  289. return partial;
  290. }
  291. static inline void free_data(struct inode *inode, sysv_zone_t *p, sysv_zone_t *q)
  292. {
  293. for ( ; p < q ; p++) {
  294. sysv_zone_t nr = *p;
  295. if (nr) {
  296. *p = 0;
  297. sysv_free_block(inode->i_sb, nr);
  298. mark_inode_dirty(inode);
  299. }
  300. }
  301. }
  302. static void free_branches(struct inode *inode, sysv_zone_t *p, sysv_zone_t *q, int depth)
  303. {
  304. struct buffer_head * bh;
  305. struct super_block *sb = inode->i_sb;
  306. if (depth--) {
  307. for ( ; p < q ; p++) {
  308. int block;
  309. sysv_zone_t nr = *p;
  310. if (!nr)
  311. continue;
  312. *p = 0;
  313. block = block_to_cpu(SYSV_SB(sb), nr);
  314. bh = sb_bread(sb, block);
  315. if (!bh)
  316. continue;
  317. free_branches(inode, (sysv_zone_t*)bh->b_data,
  318. block_end(bh), depth);
  319. bforget(bh);
  320. sysv_free_block(sb, nr);
  321. mark_inode_dirty(inode);
  322. }
  323. } else
  324. free_data(inode, p, q);
  325. }
  326. void sysv_truncate (struct inode * inode)
  327. {
  328. sysv_zone_t *i_data = SYSV_I(inode)->i_data;
  329. int offsets[DEPTH];
  330. Indirect chain[DEPTH];
  331. Indirect *partial;
  332. sysv_zone_t nr = 0;
  333. int n;
  334. long iblock;
  335. unsigned blocksize;
  336. if (!(S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
  337. S_ISLNK(inode->i_mode)))
  338. return;
  339. blocksize = inode->i_sb->s_blocksize;
  340. iblock = (inode->i_size + blocksize-1)
  341. >> inode->i_sb->s_blocksize_bits;
  342. block_truncate_page(inode->i_mapping, inode->i_size, get_block);
  343. n = block_to_path(inode, iblock, offsets);
  344. if (n == 0)
  345. return;
  346. if (n == 1) {
  347. free_data(inode, i_data+offsets[0], i_data + DIRECT);
  348. goto do_indirects;
  349. }
  350. partial = find_shared(inode, n, offsets, chain, &nr);
  351. /* Kill the top of shared branch (already detached) */
  352. if (nr) {
  353. if (partial == chain)
  354. mark_inode_dirty(inode);
  355. else
  356. dirty_indirect(partial->bh, inode);
  357. free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
  358. }
  359. /* Clear the ends of indirect blocks on the shared branch */
  360. while (partial > chain) {
  361. free_branches(inode, partial->p + 1, block_end(partial->bh),
  362. (chain+n-1) - partial);
  363. dirty_indirect(partial->bh, inode);
  364. brelse (partial->bh);
  365. partial--;
  366. }
  367. do_indirects:
  368. /* Kill the remaining (whole) subtrees (== subtrees deeper than...) */
  369. while (n < DEPTH) {
  370. nr = i_data[DIRECT + n - 1];
  371. if (nr) {
  372. i_data[DIRECT + n - 1] = 0;
  373. mark_inode_dirty(inode);
  374. free_branches(inode, &nr, &nr+1, n);
  375. }
  376. n++;
  377. }
  378. inode->i_mtime = inode->i_ctime = current_time(inode);
  379. if (IS_SYNC(inode))
  380. sysv_sync_inode (inode);
  381. else
  382. mark_inode_dirty(inode);
  383. }
  384. static unsigned sysv_nblocks(struct super_block *s, loff_t size)
  385. {
  386. struct sysv_sb_info *sbi = SYSV_SB(s);
  387. int ptrs_bits = sbi->s_ind_per_block_bits;
  388. unsigned blocks, res, direct = DIRECT, i = DEPTH;
  389. blocks = (size + s->s_blocksize - 1) >> s->s_blocksize_bits;
  390. res = blocks;
  391. while (--i && blocks > direct) {
  392. blocks = ((blocks - direct - 1) >> ptrs_bits) + 1;
  393. res += blocks;
  394. direct = 1;
  395. }
  396. return res;
  397. }
  398. int sysv_getattr(struct user_namespace *mnt_userns, const struct path *path,
  399. struct kstat *stat, u32 request_mask, unsigned int flags)
  400. {
  401. struct super_block *s = path->dentry->d_sb;
  402. generic_fillattr(&init_user_ns, d_inode(path->dentry), stat);
  403. stat->blocks = (s->s_blocksize / 512) * sysv_nblocks(s, stat->size);
  404. stat->blksize = s->s_blocksize;
  405. return 0;
  406. }
  407. static int sysv_writepage(struct page *page, struct writeback_control *wbc)
  408. {
  409. return block_write_full_page(page,get_block,wbc);
  410. }
  411. static int sysv_read_folio(struct file *file, struct folio *folio)
  412. {
  413. return block_read_full_folio(folio, get_block);
  414. }
  415. int sysv_prepare_chunk(struct page *page, loff_t pos, unsigned len)
  416. {
  417. return __block_write_begin(page, pos, len, get_block);
  418. }
  419. static void sysv_write_failed(struct address_space *mapping, loff_t to)
  420. {
  421. struct inode *inode = mapping->host;
  422. if (to > inode->i_size) {
  423. truncate_pagecache(inode, inode->i_size);
  424. sysv_truncate(inode);
  425. }
  426. }
  427. static int sysv_write_begin(struct file *file, struct address_space *mapping,
  428. loff_t pos, unsigned len,
  429. struct page **pagep, void **fsdata)
  430. {
  431. int ret;
  432. ret = block_write_begin(mapping, pos, len, pagep, get_block);
  433. if (unlikely(ret))
  434. sysv_write_failed(mapping, pos + len);
  435. return ret;
  436. }
  437. static sector_t sysv_bmap(struct address_space *mapping, sector_t block)
  438. {
  439. return generic_block_bmap(mapping,block,get_block);
  440. }
  441. const struct address_space_operations sysv_aops = {
  442. .dirty_folio = block_dirty_folio,
  443. .invalidate_folio = block_invalidate_folio,
  444. .read_folio = sysv_read_folio,
  445. .writepage = sysv_writepage,
  446. .write_begin = sysv_write_begin,
  447. .write_end = generic_write_end,
  448. .bmap = sysv_bmap
  449. };