1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
21da177e4SLinus Torvalds /* Generic part */
31da177e4SLinus Torvalds
41da177e4SLinus Torvalds typedef struct {
51da177e4SLinus Torvalds block_t *p;
61da177e4SLinus Torvalds block_t key;
71da177e4SLinus Torvalds struct buffer_head *bh;
81da177e4SLinus Torvalds } Indirect;
91da177e4SLinus Torvalds
101da177e4SLinus Torvalds static DEFINE_RWLOCK(pointers_lock);
111da177e4SLinus Torvalds
add_chain(Indirect * p,struct buffer_head * bh,block_t * v)121da177e4SLinus Torvalds static inline void add_chain(Indirect *p, struct buffer_head *bh, block_t *v)
131da177e4SLinus Torvalds {
141da177e4SLinus Torvalds p->key = *(p->p = v);
151da177e4SLinus Torvalds p->bh = bh;
161da177e4SLinus Torvalds }
171da177e4SLinus Torvalds
verify_chain(Indirect * from,Indirect * to)181da177e4SLinus Torvalds static inline int verify_chain(Indirect *from, Indirect *to)
191da177e4SLinus Torvalds {
201da177e4SLinus Torvalds while (from <= to && from->key == *from->p)
211da177e4SLinus Torvalds from++;
221da177e4SLinus Torvalds return (from > to);
231da177e4SLinus Torvalds }
241da177e4SLinus Torvalds
block_end(struct buffer_head * bh)251da177e4SLinus Torvalds static inline block_t *block_end(struct buffer_head *bh)
261da177e4SLinus Torvalds {
27939b00dfSAndries Brouwer return (block_t *)((char*)bh->b_data + bh->b_size);
281da177e4SLinus Torvalds }
291da177e4SLinus Torvalds
get_branch(struct inode * inode,int depth,int * offsets,Indirect chain[DEPTH],int * err)301da177e4SLinus Torvalds static inline Indirect *get_branch(struct inode *inode,
311da177e4SLinus Torvalds int depth,
321da177e4SLinus Torvalds int *offsets,
331da177e4SLinus Torvalds Indirect chain[DEPTH],
341da177e4SLinus Torvalds int *err)
351da177e4SLinus Torvalds {
361da177e4SLinus Torvalds struct super_block *sb = inode->i_sb;
371da177e4SLinus Torvalds Indirect *p = chain;
381da177e4SLinus Torvalds struct buffer_head *bh;
391da177e4SLinus Torvalds
401da177e4SLinus Torvalds *err = 0;
411da177e4SLinus Torvalds /* i_data is not going away, no lock needed */
421da177e4SLinus Torvalds add_chain (chain, NULL, i_data(inode) + *offsets);
431da177e4SLinus Torvalds if (!p->key)
441da177e4SLinus Torvalds goto no_block;
451da177e4SLinus Torvalds while (--depth) {
461da177e4SLinus Torvalds bh = sb_bread(sb, block_to_cpu(p->key));
471da177e4SLinus Torvalds if (!bh)
481da177e4SLinus Torvalds goto failure;
491da177e4SLinus Torvalds read_lock(&pointers_lock);
501da177e4SLinus Torvalds if (!verify_chain(chain, p))
511da177e4SLinus Torvalds goto changed;
521da177e4SLinus Torvalds add_chain(++p, bh, (block_t *)bh->b_data + *++offsets);
531da177e4SLinus Torvalds read_unlock(&pointers_lock);
541da177e4SLinus Torvalds if (!p->key)
551da177e4SLinus Torvalds goto no_block;
561da177e4SLinus Torvalds }
571da177e4SLinus Torvalds return NULL;
581da177e4SLinus Torvalds
591da177e4SLinus Torvalds changed:
601da177e4SLinus Torvalds read_unlock(&pointers_lock);
611da177e4SLinus Torvalds brelse(bh);
621da177e4SLinus Torvalds *err = -EAGAIN;
631da177e4SLinus Torvalds goto no_block;
641da177e4SLinus Torvalds failure:
651da177e4SLinus Torvalds *err = -EIO;
661da177e4SLinus Torvalds no_block:
671da177e4SLinus Torvalds return p;
681da177e4SLinus Torvalds }
691da177e4SLinus Torvalds
alloc_branch(struct inode * inode,int num,int * offsets,Indirect * branch)701da177e4SLinus Torvalds static int alloc_branch(struct inode *inode,
711da177e4SLinus Torvalds int num,
721da177e4SLinus Torvalds int *offsets,
731da177e4SLinus Torvalds Indirect *branch)
741da177e4SLinus Torvalds {
751da177e4SLinus Torvalds int n = 0;
761da177e4SLinus Torvalds int i;
771da177e4SLinus Torvalds int parent = minix_new_block(inode);
78da27e0a0SEric Biggers int err = -ENOSPC;
791da177e4SLinus Torvalds
801da177e4SLinus Torvalds branch[0].key = cpu_to_block(parent);
811da177e4SLinus Torvalds if (parent) for (n = 1; n < num; n++) {
821da177e4SLinus Torvalds struct buffer_head *bh;
831da177e4SLinus Torvalds /* Allocate the next block */
841da177e4SLinus Torvalds int nr = minix_new_block(inode);
851da177e4SLinus Torvalds if (!nr)
861da177e4SLinus Torvalds break;
871da177e4SLinus Torvalds branch[n].key = cpu_to_block(nr);
881da177e4SLinus Torvalds bh = sb_getblk(inode->i_sb, parent);
89da27e0a0SEric Biggers if (!bh) {
90da27e0a0SEric Biggers minix_free_block(inode, nr);
91da27e0a0SEric Biggers err = -ENOMEM;
92da27e0a0SEric Biggers break;
93da27e0a0SEric Biggers }
941da177e4SLinus Torvalds lock_buffer(bh);
95939b00dfSAndries Brouwer memset(bh->b_data, 0, bh->b_size);
961da177e4SLinus Torvalds branch[n].bh = bh;
971da177e4SLinus Torvalds branch[n].p = (block_t*) bh->b_data + offsets[n];
981da177e4SLinus Torvalds *branch[n].p = branch[n].key;
991da177e4SLinus Torvalds set_buffer_uptodate(bh);
1001da177e4SLinus Torvalds unlock_buffer(bh);
1011da177e4SLinus Torvalds mark_buffer_dirty_inode(bh, inode);
1021da177e4SLinus Torvalds parent = nr;
1031da177e4SLinus Torvalds }
1041da177e4SLinus Torvalds if (n == num)
1051da177e4SLinus Torvalds return 0;
1061da177e4SLinus Torvalds
1071da177e4SLinus Torvalds /* Allocation failed, free what we already allocated */
1081da177e4SLinus Torvalds for (i = 1; i < n; i++)
1091da177e4SLinus Torvalds bforget(branch[i].bh);
1101da177e4SLinus Torvalds for (i = 0; i < n; i++)
1111da177e4SLinus Torvalds minix_free_block(inode, block_to_cpu(branch[i].key));
112da27e0a0SEric Biggers return err;
1131da177e4SLinus Torvalds }
1141da177e4SLinus Torvalds
splice_branch(struct inode * inode,Indirect chain[DEPTH],Indirect * where,int num)1151da177e4SLinus Torvalds static inline int splice_branch(struct inode *inode,
1161da177e4SLinus Torvalds Indirect chain[DEPTH],
1171da177e4SLinus Torvalds Indirect *where,
1181da177e4SLinus Torvalds int num)
1191da177e4SLinus Torvalds {
1201da177e4SLinus Torvalds int i;
1211da177e4SLinus Torvalds
1221da177e4SLinus Torvalds write_lock(&pointers_lock);
1231da177e4SLinus Torvalds
1241da177e4SLinus Torvalds /* Verify that place we are splicing to is still there and vacant */
1251da177e4SLinus Torvalds if (!verify_chain(chain, where-1) || *where->p)
1261da177e4SLinus Torvalds goto changed;
1271da177e4SLinus Torvalds
1281da177e4SLinus Torvalds *where->p = where->key;
1291da177e4SLinus Torvalds
1301da177e4SLinus Torvalds write_unlock(&pointers_lock);
1311da177e4SLinus Torvalds
1321da177e4SLinus Torvalds /* We are done with atomic stuff, now do the rest of housekeeping */
1331da177e4SLinus Torvalds
134*f7f43858SJeff Layton inode_set_ctime_current(inode);
1351da177e4SLinus Torvalds
1361da177e4SLinus Torvalds /* had we spliced it onto indirect block? */
1371da177e4SLinus Torvalds if (where->bh)
1381da177e4SLinus Torvalds mark_buffer_dirty_inode(where->bh, inode);
1391da177e4SLinus Torvalds
1401da177e4SLinus Torvalds mark_inode_dirty(inode);
1411da177e4SLinus Torvalds return 0;
1421da177e4SLinus Torvalds
1431da177e4SLinus Torvalds changed:
1441da177e4SLinus Torvalds write_unlock(&pointers_lock);
1451da177e4SLinus Torvalds for (i = 1; i < num; i++)
1461da177e4SLinus Torvalds bforget(where[i].bh);
1471da177e4SLinus Torvalds for (i = 0; i < num; i++)
1481da177e4SLinus Torvalds minix_free_block(inode, block_to_cpu(where[i].key));
1491da177e4SLinus Torvalds return -EAGAIN;
1501da177e4SLinus Torvalds }
1511da177e4SLinus Torvalds
get_block(struct inode * inode,sector_t block,struct buffer_head * bh,int create)1524f2ed694SDenys Vlasenko static int get_block(struct inode * inode, sector_t block,
1531da177e4SLinus Torvalds struct buffer_head *bh, int create)
1541da177e4SLinus Torvalds {
1551da177e4SLinus Torvalds int err = -EIO;
1561da177e4SLinus Torvalds int offsets[DEPTH];
1571da177e4SLinus Torvalds Indirect chain[DEPTH];
1581da177e4SLinus Torvalds Indirect *partial;
1591da177e4SLinus Torvalds int left;
1601da177e4SLinus Torvalds int depth = block_to_path(inode, block, offsets);
1611da177e4SLinus Torvalds
1621da177e4SLinus Torvalds if (depth == 0)
1631da177e4SLinus Torvalds goto out;
1641da177e4SLinus Torvalds
1651da177e4SLinus Torvalds reread:
1661da177e4SLinus Torvalds partial = get_branch(inode, depth, offsets, chain, &err);
1671da177e4SLinus Torvalds
1681da177e4SLinus Torvalds /* Simplest case - block found, no allocation needed */
1691da177e4SLinus Torvalds if (!partial) {
1701da177e4SLinus Torvalds got_it:
1711da177e4SLinus Torvalds map_bh(bh, inode->i_sb, block_to_cpu(chain[depth-1].key));
1721da177e4SLinus Torvalds /* Clean up and exit */
1731da177e4SLinus Torvalds partial = chain+depth-1; /* the whole chain */
1741da177e4SLinus Torvalds goto cleanup;
1751da177e4SLinus Torvalds }
1761da177e4SLinus Torvalds
1771da177e4SLinus Torvalds /* Next simple case - plain lookup or failed read of indirect block */
1781da177e4SLinus Torvalds if (!create || err == -EIO) {
1791da177e4SLinus Torvalds cleanup:
1801da177e4SLinus Torvalds while (partial > chain) {
1811da177e4SLinus Torvalds brelse(partial->bh);
1821da177e4SLinus Torvalds partial--;
1831da177e4SLinus Torvalds }
1841da177e4SLinus Torvalds out:
1851da177e4SLinus Torvalds return err;
1861da177e4SLinus Torvalds }
1871da177e4SLinus Torvalds
1881da177e4SLinus Torvalds /*
1891da177e4SLinus Torvalds * Indirect block might be removed by truncate while we were
1901da177e4SLinus Torvalds * reading it. Handling of that case (forget what we've got and
1911da177e4SLinus Torvalds * reread) is taken out of the main path.
1921da177e4SLinus Torvalds */
1931da177e4SLinus Torvalds if (err == -EAGAIN)
1941da177e4SLinus Torvalds goto changed;
1951da177e4SLinus Torvalds
1961da177e4SLinus Torvalds left = (chain + depth) - partial;
1971da177e4SLinus Torvalds err = alloc_branch(inode, left, offsets+(partial-chain), partial);
1981da177e4SLinus Torvalds if (err)
1991da177e4SLinus Torvalds goto cleanup;
2001da177e4SLinus Torvalds
2011da177e4SLinus Torvalds if (splice_branch(inode, chain, partial, left) < 0)
2021da177e4SLinus Torvalds goto changed;
2031da177e4SLinus Torvalds
2041da177e4SLinus Torvalds set_buffer_new(bh);
2051da177e4SLinus Torvalds goto got_it;
2061da177e4SLinus Torvalds
2071da177e4SLinus Torvalds changed:
2081da177e4SLinus Torvalds while (partial > chain) {
2091da177e4SLinus Torvalds brelse(partial->bh);
2101da177e4SLinus Torvalds partial--;
2111da177e4SLinus Torvalds }
2121da177e4SLinus Torvalds goto reread;
2131da177e4SLinus Torvalds }
2141da177e4SLinus Torvalds
all_zeroes(block_t * p,block_t * q)2151da177e4SLinus Torvalds static inline int all_zeroes(block_t *p, block_t *q)
2161da177e4SLinus Torvalds {
2171da177e4SLinus Torvalds while (p < q)
2181da177e4SLinus Torvalds if (*p++)
2191da177e4SLinus Torvalds return 0;
2201da177e4SLinus Torvalds return 1;
2211da177e4SLinus Torvalds }
2221da177e4SLinus Torvalds
find_shared(struct inode * inode,int depth,int offsets[DEPTH],Indirect chain[DEPTH],block_t * top)2231da177e4SLinus Torvalds static Indirect *find_shared(struct inode *inode,
2241da177e4SLinus Torvalds int depth,
2251da177e4SLinus Torvalds int offsets[DEPTH],
2261da177e4SLinus Torvalds Indirect chain[DEPTH],
2271da177e4SLinus Torvalds block_t *top)
2281da177e4SLinus Torvalds {
2291da177e4SLinus Torvalds Indirect *partial, *p;
2301da177e4SLinus Torvalds int k, err;
2311da177e4SLinus Torvalds
2321da177e4SLinus Torvalds *top = 0;
2331da177e4SLinus Torvalds for (k = depth; k > 1 && !offsets[k-1]; k--)
2341da177e4SLinus Torvalds ;
2351da177e4SLinus Torvalds partial = get_branch(inode, k, offsets, chain, &err);
2361da177e4SLinus Torvalds
2371da177e4SLinus Torvalds write_lock(&pointers_lock);
2381da177e4SLinus Torvalds if (!partial)
2391da177e4SLinus Torvalds partial = chain + k-1;
2401da177e4SLinus Torvalds if (!partial->key && *partial->p) {
2411da177e4SLinus Torvalds write_unlock(&pointers_lock);
2421da177e4SLinus Torvalds goto no_top;
2431da177e4SLinus Torvalds }
2441da177e4SLinus Torvalds for (p=partial;p>chain && all_zeroes((block_t*)p->bh->b_data,p->p);p--)
2451da177e4SLinus Torvalds ;
2461da177e4SLinus Torvalds if (p == chain + k - 1 && p > chain) {
2471da177e4SLinus Torvalds p->p--;
2481da177e4SLinus Torvalds } else {
2491da177e4SLinus Torvalds *top = *p->p;
2501da177e4SLinus Torvalds *p->p = 0;
2511da177e4SLinus Torvalds }
2521da177e4SLinus Torvalds write_unlock(&pointers_lock);
2531da177e4SLinus Torvalds
2541da177e4SLinus Torvalds while(partial > p)
2551da177e4SLinus Torvalds {
2561da177e4SLinus Torvalds brelse(partial->bh);
2571da177e4SLinus Torvalds partial--;
2581da177e4SLinus Torvalds }
2591da177e4SLinus Torvalds no_top:
2601da177e4SLinus Torvalds return partial;
2611da177e4SLinus Torvalds }
2621da177e4SLinus Torvalds
free_data(struct inode * inode,block_t * p,block_t * q)2631da177e4SLinus Torvalds static inline void free_data(struct inode *inode, block_t *p, block_t *q)
2641da177e4SLinus Torvalds {
2651da177e4SLinus Torvalds unsigned long nr;
2661da177e4SLinus Torvalds
2671da177e4SLinus Torvalds for ( ; p < q ; p++) {
2681da177e4SLinus Torvalds nr = block_to_cpu(*p);
2691da177e4SLinus Torvalds if (nr) {
2701da177e4SLinus Torvalds *p = 0;
2711da177e4SLinus Torvalds minix_free_block(inode, nr);
2721da177e4SLinus Torvalds }
2731da177e4SLinus Torvalds }
2741da177e4SLinus Torvalds }
2751da177e4SLinus Torvalds
free_branches(struct inode * inode,block_t * p,block_t * q,int depth)2761da177e4SLinus Torvalds static void free_branches(struct inode *inode, block_t *p, block_t *q, int depth)
2771da177e4SLinus Torvalds {
2781da177e4SLinus Torvalds struct buffer_head * bh;
2791da177e4SLinus Torvalds unsigned long nr;
2801da177e4SLinus Torvalds
2811da177e4SLinus Torvalds if (depth--) {
2821da177e4SLinus Torvalds for ( ; p < q ; p++) {
2831da177e4SLinus Torvalds nr = block_to_cpu(*p);
2841da177e4SLinus Torvalds if (!nr)
2851da177e4SLinus Torvalds continue;
2861da177e4SLinus Torvalds *p = 0;
2871da177e4SLinus Torvalds bh = sb_bread(inode->i_sb, nr);
2881da177e4SLinus Torvalds if (!bh)
2891da177e4SLinus Torvalds continue;
2901da177e4SLinus Torvalds free_branches(inode, (block_t*)bh->b_data,
2911da177e4SLinus Torvalds block_end(bh), depth);
2921da177e4SLinus Torvalds bforget(bh);
2931da177e4SLinus Torvalds minix_free_block(inode, nr);
2941da177e4SLinus Torvalds mark_inode_dirty(inode);
2951da177e4SLinus Torvalds }
2961da177e4SLinus Torvalds } else
2971da177e4SLinus Torvalds free_data(inode, p, q);
2981da177e4SLinus Torvalds }
2991da177e4SLinus Torvalds
truncate(struct inode * inode)3001da177e4SLinus Torvalds static inline void truncate (struct inode * inode)
3011da177e4SLinus Torvalds {
302939b00dfSAndries Brouwer struct super_block *sb = inode->i_sb;
3031da177e4SLinus Torvalds block_t *idata = i_data(inode);
3041da177e4SLinus Torvalds int offsets[DEPTH];
3051da177e4SLinus Torvalds Indirect chain[DEPTH];
3061da177e4SLinus Torvalds Indirect *partial;
3071da177e4SLinus Torvalds block_t nr = 0;
3081da177e4SLinus Torvalds int n;
3091da177e4SLinus Torvalds int first_whole;
3101da177e4SLinus Torvalds long iblock;
3111da177e4SLinus Torvalds
312939b00dfSAndries Brouwer iblock = (inode->i_size + sb->s_blocksize -1) >> sb->s_blocksize_bits;
3131da177e4SLinus Torvalds block_truncate_page(inode->i_mapping, inode->i_size, get_block);
3141da177e4SLinus Torvalds
3151da177e4SLinus Torvalds n = block_to_path(inode, iblock, offsets);
3161da177e4SLinus Torvalds if (!n)
3171da177e4SLinus Torvalds return;
3181da177e4SLinus Torvalds
3191da177e4SLinus Torvalds if (n == 1) {
3201da177e4SLinus Torvalds free_data(inode, idata+offsets[0], idata + DIRECT);
3211da177e4SLinus Torvalds first_whole = 0;
3221da177e4SLinus Torvalds goto do_indirects;
3231da177e4SLinus Torvalds }
3241da177e4SLinus Torvalds
3251da177e4SLinus Torvalds first_whole = offsets[0] + 1 - DIRECT;
3261da177e4SLinus Torvalds partial = find_shared(inode, n, offsets, chain, &nr);
3271da177e4SLinus Torvalds if (nr) {
3281da177e4SLinus Torvalds if (partial == chain)
3291da177e4SLinus Torvalds mark_inode_dirty(inode);
3301da177e4SLinus Torvalds else
3311da177e4SLinus Torvalds mark_buffer_dirty_inode(partial->bh, inode);
3321da177e4SLinus Torvalds free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
3331da177e4SLinus Torvalds }
3341da177e4SLinus Torvalds /* Clear the ends of indirect blocks on the shared branch */
3351da177e4SLinus Torvalds while (partial > chain) {
3361da177e4SLinus Torvalds free_branches(inode, partial->p + 1, block_end(partial->bh),
3371da177e4SLinus Torvalds (chain+n-1) - partial);
3381da177e4SLinus Torvalds mark_buffer_dirty_inode(partial->bh, inode);
3391da177e4SLinus Torvalds brelse (partial->bh);
3401da177e4SLinus Torvalds partial--;
3411da177e4SLinus Torvalds }
3421da177e4SLinus Torvalds do_indirects:
3431da177e4SLinus Torvalds /* Kill the remaining (whole) subtrees */
3441da177e4SLinus Torvalds while (first_whole < DEPTH-1) {
3451da177e4SLinus Torvalds nr = idata[DIRECT+first_whole];
3461da177e4SLinus Torvalds if (nr) {
3471da177e4SLinus Torvalds idata[DIRECT+first_whole] = 0;
3481da177e4SLinus Torvalds mark_inode_dirty(inode);
3491da177e4SLinus Torvalds free_branches(inode, &nr, &nr+1, first_whole+1);
3501da177e4SLinus Torvalds }
3511da177e4SLinus Torvalds first_whole++;
3521da177e4SLinus Torvalds }
353*f7f43858SJeff Layton inode->i_mtime = inode_set_ctime_current(inode);
3541da177e4SLinus Torvalds mark_inode_dirty(inode);
3551da177e4SLinus Torvalds }
3561da177e4SLinus Torvalds
nblocks(loff_t size,struct super_block * sb)357939b00dfSAndries Brouwer static inline unsigned nblocks(loff_t size, struct super_block *sb)
3581da177e4SLinus Torvalds {
359939b00dfSAndries Brouwer int k = sb->s_blocksize_bits - 10;
3601da177e4SLinus Torvalds unsigned blocks, res, direct = DIRECT, i = DEPTH;
361939b00dfSAndries Brouwer blocks = (size + sb->s_blocksize - 1) >> (BLOCK_SIZE_BITS + k);
3621da177e4SLinus Torvalds res = blocks;
3631da177e4SLinus Torvalds while (--i && blocks > direct) {
3641da177e4SLinus Torvalds blocks -= direct;
365939b00dfSAndries Brouwer blocks += sb->s_blocksize/sizeof(block_t) - 1;
366939b00dfSAndries Brouwer blocks /= sb->s_blocksize/sizeof(block_t);
3671da177e4SLinus Torvalds res += blocks;
3681da177e4SLinus Torvalds direct = 1;
3691da177e4SLinus Torvalds }
3701da177e4SLinus Torvalds return res;
3711da177e4SLinus Torvalds }
372