fs/minix/itree_common.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /* Generic part */
0003
0004 typedef struct {
0005     block_t *p;
0006     block_t key;
0007     struct buffer_head *bh;
0008 } Indirect;
0009
0010 static DEFINE_RWLOCK(pointers_lock);
0011
0012 static inline void add_chain(Indirect *p, struct buffer_head *bh, block_t *v)
0013 {
0014     p->key = *(p->p = v);
0015     p->bh = bh;
0016 }
0017
0018 static inline int verify_chain(Indirect *from, Indirect *to)
0019 {
0020     while (from <= to && from->key == *from->p)
0021         from++;
0022     return (from > to);
0023 }
0024
0025 static inline block_t *block_end(struct buffer_head *bh)
0026 {
0027     return (block_t *)((char*)bh->b_data + bh->b_size);
0028 }
0029
0030 static inline Indirect *get_branch(struct inode *inode,
0031                     int depth,
0032                     int *offsets,
0033                     Indirect chain[DEPTH],
0034                     int *err)
0035 {
0036     struct super_block *sb = inode->i_sb;
0037     Indirect *p = chain;
0038     struct buffer_head *bh;
0039
0040     *err = 0;
0041     /* i_data is not going away, no lock needed */
0042     add_chain (chain, NULL, i_data(inode) + *offsets);
0043     if (!p->key)
0044         goto no_block;
0045     while (--depth) {
0046         bh = sb_bread(sb, block_to_cpu(p->key));
0047         if (!bh)
0048             goto failure;
0049         read_lock(&pointers_lock);
0050         if (!verify_chain(chain, p))
0051             goto changed;
0052         add_chain(++p, bh, (block_t *)bh->b_data + *++offsets);
0053         read_unlock(&pointers_lock);
0054         if (!p->key)
0055             goto no_block;
0056     }
0057     return NULL;
0058
0059 changed:
0060     read_unlock(&pointers_lock);
0061     brelse(bh);
0062     *err = -EAGAIN;
0063     goto no_block;
0064 failure:
0065     *err = -EIO;
0066 no_block:
0067     return p;
0068 }
0069
0070 static int alloc_branch(struct inode *inode,
0071                  int num,
0072                  int *offsets,
0073                  Indirect *branch)
0074 {
0075     int n = 0;
0076     int i;
0077     int parent = minix_new_block(inode);
0078     int err = -ENOSPC;
0079
0080     branch[0].key = cpu_to_block(parent);
0081     if (parent) for (n = 1; n < num; n++) {
0082         struct buffer_head *bh;
0083         /* Allocate the next block */
0084         int nr = minix_new_block(inode);
0085         if (!nr)
0086             break;
0087         branch[n].key = cpu_to_block(nr);
0088         bh = sb_getblk(inode->i_sb, parent);
0089         if (!bh) {
0090             minix_free_block(inode, nr);
0091             err = -ENOMEM;
0092             break;
0093         }
0094         lock_buffer(bh);
0095         memset(bh->b_data, 0, bh->b_size);
0096         branch[n].bh = bh;
0097         branch[n].p = (block_t*) bh->b_data + offsets[n];
0098         *branch[n].p = branch[n].key;
0099         set_buffer_uptodate(bh);
0100         unlock_buffer(bh);
0101         mark_buffer_dirty_inode(bh, inode);
0102         parent = nr;
0103     }
0104     if (n == num)
0105         return 0;
0106
0107     /* Allocation failed, free what we already allocated */
0108     for (i = 1; i < n; i++)
0109         bforget(branch[i].bh);
0110     for (i = 0; i < n; i++)
0111         minix_free_block(inode, block_to_cpu(branch[i].key));
0112     return err;
0113 }
0114
0115 static inline int splice_branch(struct inode *inode,
0116                      Indirect chain[DEPTH],
0117                      Indirect *where,
0118                      int num)
0119 {
0120     int i;
0121
0122     write_lock(&pointers_lock);
0123
0124     /* Verify that place we are splicing to is still there and vacant */
0125     if (!verify_chain(chain, where-1) || *where->p)
0126         goto changed;
0127
0128     *where->p = where->key;
0129
0130     write_unlock(&pointers_lock);
0131
0132     /* We are done with atomic stuff, now do the rest of housekeeping */
0133
0134     inode->i_ctime = current_time(inode);
0135
0136     /* had we spliced it onto indirect block? */
0137     if (where->bh)
0138         mark_buffer_dirty_inode(where->bh, inode);
0139
0140     mark_inode_dirty(inode);
0141     return 0;
0142
0143 changed:
0144     write_unlock(&pointers_lock);
0145     for (i = 1; i < num; i++)
0146         bforget(where[i].bh);
0147     for (i = 0; i < num; i++)
0148         minix_free_block(inode, block_to_cpu(where[i].key));
0149     return -EAGAIN;
0150 }
0151
0152 static int get_block(struct inode * inode, sector_t block,
0153             struct buffer_head *bh, int create)
0154 {
0155     int err = -EIO;
0156     int offsets[DEPTH];
0157     Indirect chain[DEPTH];
0158     Indirect *partial;
0159     int left;
0160     int depth = block_to_path(inode, block, offsets);
0161
0162     if (depth == 0)
0163         goto out;
0164
0165 reread:
0166     partial = get_branch(inode, depth, offsets, chain, &err);
0167
0168     /* Simplest case - block found, no allocation needed */
0169     if (!partial) {
0170 got_it:
0171         map_bh(bh, inode->i_sb, block_to_cpu(chain[depth-1].key));
0172         /* Clean up and exit */
0173         partial = chain+depth-1; /* the whole chain */
0174         goto cleanup;
0175     }
0176
0177     /* Next simple case - plain lookup or failed read of indirect block */
0178     if (!create || err == -EIO) {
0179 cleanup:
0180         while (partial > chain) {
0181             brelse(partial->bh);
0182             partial--;
0183         }
0184 out:
0185         return err;
0186     }
0187
0188     /*
0189      * Indirect block might be removed by truncate while we were
0190      * reading it. Handling of that case (forget what we've got and
0191      * reread) is taken out of the main path.
0192      */
0193     if (err == -EAGAIN)
0194         goto changed;
0195
0196     left = (chain + depth) - partial;
0197     err = alloc_branch(inode, left, offsets+(partial-chain), partial);
0198     if (err)
0199         goto cleanup;
0200
0201     if (splice_branch(inode, chain, partial, left) < 0)
0202         goto changed;
0203
0204     set_buffer_new(bh);
0205     goto got_it;
0206
0207 changed:
0208     while (partial > chain) {
0209         brelse(partial->bh);
0210         partial--;
0211     }
0212     goto reread;
0213 }
0214
0215 static inline int all_zeroes(block_t *p, block_t *q)
0216 {
0217     while (p < q)
0218         if (*p++)
0219             return 0;
0220     return 1;
0221 }
0222
0223 static Indirect *find_shared(struct inode *inode,
0224                 int depth,
0225                 int offsets[DEPTH],
0226                 Indirect chain[DEPTH],
0227                 block_t *top)
0228 {
0229     Indirect *partial, *p;
0230     int k, err;
0231
0232     *top = 0;
0233     for (k = depth; k > 1 && !offsets[k-1]; k--)
0234         ;
0235     partial = get_branch(inode, k, offsets, chain, &err);
0236
0237     write_lock(&pointers_lock);
0238     if (!partial)
0239         partial = chain + k-1;
0240     if (!partial->key && *partial->p) {
0241         write_unlock(&pointers_lock);
0242         goto no_top;
0243     }
0244     for (p=partial;p>chain && all_zeroes((block_t*)p->bh->b_data,p->p);p--)
0245         ;
0246     if (p == chain + k - 1 && p > chain) {
0247         p->p--;
0248     } else {
0249         *top = *p->p;
0250         *p->p = 0;
0251     }
0252     write_unlock(&pointers_lock);
0253
0254     while(partial > p)
0255     {
0256         brelse(partial->bh);
0257         partial--;
0258     }
0259 no_top:
0260     return partial;
0261 }
0262
0263 static inline void free_data(struct inode *inode, block_t *p, block_t *q)
0264 {
0265     unsigned long nr;
0266
0267     for ( ; p < q ; p++) {
0268         nr = block_to_cpu(*p);
0269         if (nr) {
0270             *p = 0;
0271             minix_free_block(inode, nr);
0272         }
0273     }
0274 }
0275
0276 static void free_branches(struct inode *inode, block_t *p, block_t *q, int depth)
0277 {
0278     struct buffer_head * bh;
0279     unsigned long nr;
0280
0281     if (depth--) {
0282         for ( ; p < q ; p++) {
0283             nr = block_to_cpu(*p);
0284             if (!nr)
0285                 continue;
0286             *p = 0;
0287             bh = sb_bread(inode->i_sb, nr);
0288             if (!bh)
0289                 continue;
0290             free_branches(inode, (block_t*)bh->b_data,
0291                       block_end(bh), depth);
0292             bforget(bh);
0293             minix_free_block(inode, nr);
0294             mark_inode_dirty(inode);
0295         }
0296     } else
0297         free_data(inode, p, q);
0298 }
0299
0300 static inline void truncate (struct inode * inode)
0301 {
0302     struct super_block *sb = inode->i_sb;
0303     block_t *idata = i_data(inode);
0304     int offsets[DEPTH];
0305     Indirect chain[DEPTH];
0306     Indirect *partial;
0307     block_t nr = 0;
0308     int n;
0309     int first_whole;
0310     long iblock;
0311
0312     iblock = (inode->i_size + sb->s_blocksize -1) >> sb->s_blocksize_bits;
0313     block_truncate_page(inode->i_mapping, inode->i_size, get_block);
0314
0315     n = block_to_path(inode, iblock, offsets);
0316     if (!n)
0317         return;
0318
0319     if (n == 1) {
0320         free_data(inode, idata+offsets[0], idata + DIRECT);
0321         first_whole = 0;
0322         goto do_indirects;
0323     }
0324
0325     first_whole = offsets[0] + 1 - DIRECT;
0326     partial = find_shared(inode, n, offsets, chain, &nr);
0327     if (nr) {
0328         if (partial == chain)
0329             mark_inode_dirty(inode);
0330         else
0331             mark_buffer_dirty_inode(partial->bh, inode);
0332         free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
0333     }
0334     /* Clear the ends of indirect blocks on the shared branch */
0335     while (partial > chain) {
0336         free_branches(inode, partial->p + 1, block_end(partial->bh),
0337                 (chain+n-1) - partial);
0338         mark_buffer_dirty_inode(partial->bh, inode);
0339         brelse (partial->bh);
0340         partial--;
0341     }
0342 do_indirects:
0343     /* Kill the remaining (whole) subtrees */
0344     while (first_whole < DEPTH-1) {
0345         nr = idata[DIRECT+first_whole];
0346         if (nr) {
0347             idata[DIRECT+first_whole] = 0;
0348             mark_inode_dirty(inode);
0349             free_branches(inode, &nr, &nr+1, first_whole+1);
0350         }
0351         first_whole++;
0352     }
0353     inode->i_mtime = inode->i_ctime = current_time(inode);
0354     mark_inode_dirty(inode);
0355 }
0356
0357 static inline unsigned nblocks(loff_t size, struct super_block *sb)
0358 {
0359     int k = sb->s_blocksize_bits - 10;
0360     unsigned blocks, res, direct = DIRECT, i = DEPTH;
0361     blocks = (size + sb->s_blocksize - 1) >> (BLOCK_SIZE_BITS + k);
0362     res = blocks;
0363     while (--i && blocks > direct) {
0364         blocks -= direct;
0365         blocks += sb->s_blocksize/sizeof(block_t) - 1;
0366         blocks /= sb->s_blocksize/sizeof(block_t);
0367         res += blocks;
0368         direct = 1;
0369     }
0370     return res;
0371 }