fs/affs/bitmap.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/affs/bitmap.c
0004  *
0005  *  (c) 1996 Hans-Joachim Widmaier
0006  *
0007  *  bitmap.c contains the code that handles all bitmap related stuff -
0008  *  block allocation, deallocation, calculation of free space.
0009  */
0010
0011 #include <linux/slab.h>
0012 #include "affs.h"
0013
0014 u32
0015 affs_count_free_blocks(struct super_block *sb)
0016 {
0017     struct affs_bm_info *bm;
0018     u32 free;
0019     int i;
0020
0021     pr_debug("%s()\n", __func__);
0022
0023     if (sb_rdonly(sb))
0024         return 0;
0025
0026     mutex_lock(&AFFS_SB(sb)->s_bmlock);
0027
0028     bm = AFFS_SB(sb)->s_bitmap;
0029     free = 0;
0030     for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
0031         free += bm->bm_free;
0032
0033     mutex_unlock(&AFFS_SB(sb)->s_bmlock);
0034
0035     return free;
0036 }
0037
0038 void
0039 affs_free_block(struct super_block *sb, u32 block)
0040 {
0041     struct affs_sb_info *sbi = AFFS_SB(sb);
0042     struct affs_bm_info *bm;
0043     struct buffer_head *bh;
0044     u32 blk, bmap, bit, mask, tmp;
0045     __be32 *data;
0046
0047     pr_debug("%s(%u)\n", __func__, block);
0048
0049     if (block > sbi->s_partition_size)
0050         goto err_range;
0051
0052     blk     = block - sbi->s_reserved;
0053     bmap    = blk / sbi->s_bmap_bits;
0054     bit     = blk % sbi->s_bmap_bits;
0055     bm      = &sbi->s_bitmap[bmap];
0056
0057     mutex_lock(&sbi->s_bmlock);
0058
0059     bh = sbi->s_bmap_bh;
0060     if (sbi->s_last_bmap != bmap) {
0061         affs_brelse(bh);
0062         bh = affs_bread(sb, bm->bm_key);
0063         if (!bh)
0064             goto err_bh_read;
0065         sbi->s_bmap_bh = bh;
0066         sbi->s_last_bmap = bmap;
0067     }
0068
0069     mask = 1 << (bit & 31);
0070     data = (__be32 *)bh->b_data + bit / 32 + 1;
0071
0072     /* mark block free */
0073     tmp = be32_to_cpu(*data);
0074     if (tmp & mask)
0075         goto err_free;
0076     *data = cpu_to_be32(tmp | mask);
0077
0078     /* fix checksum */
0079     tmp = be32_to_cpu(*(__be32 *)bh->b_data);
0080     *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
0081
0082     mark_buffer_dirty(bh);
0083     affs_mark_sb_dirty(sb);
0084     bm->bm_free++;
0085
0086     mutex_unlock(&sbi->s_bmlock);
0087     return;
0088
0089 err_free:
0090     affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
0091     mutex_unlock(&sbi->s_bmlock);
0092     return;
0093
0094 err_bh_read:
0095     affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
0096     sbi->s_bmap_bh = NULL;
0097     sbi->s_last_bmap = ~0;
0098     mutex_unlock(&sbi->s_bmlock);
0099     return;
0100
0101 err_range:
0102     affs_error(sb, "affs_free_block","Block %u outside partition", block);
0103 }
0104
0105 /*
0106  * Allocate a block in the given allocation zone.
0107  * Since we have to byte-swap the bitmap on little-endian
0108  * machines, this is rather expensive. Therefore we will
0109  * preallocate up to 16 blocks from the same word, if
0110  * possible. We are not doing preallocations in the
0111  * header zone, though.
0112  */
0113
0114 u32
0115 affs_alloc_block(struct inode *inode, u32 goal)
0116 {
0117     struct super_block *sb;
0118     struct affs_sb_info *sbi;
0119     struct affs_bm_info *bm;
0120     struct buffer_head *bh;
0121     __be32 *data, *enddata;
0122     u32 blk, bmap, bit, mask, mask2, tmp;
0123     int i;
0124
0125     sb = inode->i_sb;
0126     sbi = AFFS_SB(sb);
0127
0128     pr_debug("balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
0129
0130     if (AFFS_I(inode)->i_pa_cnt) {
0131         pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
0132         AFFS_I(inode)->i_pa_cnt--;
0133         return ++AFFS_I(inode)->i_lastalloc;
0134     }
0135
0136     if (!goal || goal > sbi->s_partition_size) {
0137         if (goal)
0138             affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
0139         //if (!AFFS_I(inode)->i_last_block)
0140         //  affs_warning(sb, "affs_balloc", "no last alloc block");
0141         goal = sbi->s_reserved;
0142     }
0143
0144     blk = goal - sbi->s_reserved;
0145     bmap = blk / sbi->s_bmap_bits;
0146     bm = &sbi->s_bitmap[bmap];
0147
0148     mutex_lock(&sbi->s_bmlock);
0149
0150     if (bm->bm_free)
0151         goto find_bmap_bit;
0152
0153 find_bmap:
0154     /* search for the next bmap buffer with free bits */
0155     i = sbi->s_bmap_count;
0156     do {
0157         if (--i < 0)
0158             goto err_full;
0159         bmap++;
0160         bm++;
0161         if (bmap < sbi->s_bmap_count)
0162             continue;
0163         /* restart search at zero */
0164         bmap = 0;
0165         bm = sbi->s_bitmap;
0166     } while (!bm->bm_free);
0167     blk = bmap * sbi->s_bmap_bits;
0168
0169 find_bmap_bit:
0170
0171     bh = sbi->s_bmap_bh;
0172     if (sbi->s_last_bmap != bmap) {
0173         affs_brelse(bh);
0174         bh = affs_bread(sb, bm->bm_key);
0175         if (!bh)
0176             goto err_bh_read;
0177         sbi->s_bmap_bh = bh;
0178         sbi->s_last_bmap = bmap;
0179     }
0180
0181     /* find an unused block in this bitmap block */
0182     bit = blk % sbi->s_bmap_bits;
0183     data = (__be32 *)bh->b_data + bit / 32 + 1;
0184     enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
0185     mask = ~0UL << (bit & 31);
0186     blk &= ~31UL;
0187
0188     tmp = be32_to_cpu(*data);
0189     if (tmp & mask)
0190         goto find_bit;
0191
0192     /* scan the rest of the buffer */
0193     do {
0194         blk += 32;
0195         if (++data >= enddata)
0196             /* didn't find something, can only happen
0197              * if scan didn't start at 0, try next bmap
0198              */
0199             goto find_bmap;
0200     } while (!*data);
0201     tmp = be32_to_cpu(*data);
0202     mask = ~0;
0203
0204 find_bit:
0205     /* finally look for a free bit in the word */
0206     bit = ffs(tmp & mask) - 1;
0207     blk += bit + sbi->s_reserved;
0208     mask2 = mask = 1 << (bit & 31);
0209     AFFS_I(inode)->i_lastalloc = blk;
0210
0211     /* prealloc as much as possible within this word */
0212     while ((mask2 <<= 1)) {
0213         if (!(tmp & mask2))
0214             break;
0215         AFFS_I(inode)->i_pa_cnt++;
0216         mask |= mask2;
0217     }
0218     bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
0219
0220     *data = cpu_to_be32(tmp & ~mask);
0221
0222     /* fix checksum */
0223     tmp = be32_to_cpu(*(__be32 *)bh->b_data);
0224     *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
0225
0226     mark_buffer_dirty(bh);
0227     affs_mark_sb_dirty(sb);
0228
0229     mutex_unlock(&sbi->s_bmlock);
0230
0231     pr_debug("%d\n", blk);
0232     return blk;
0233
0234 err_bh_read:
0235     affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
0236     sbi->s_bmap_bh = NULL;
0237     sbi->s_last_bmap = ~0;
0238 err_full:
0239     mutex_unlock(&sbi->s_bmlock);
0240     pr_debug("failed\n");
0241     return 0;
0242 }
0243
0244 int affs_init_bitmap(struct super_block *sb, int *flags)
0245 {
0246     struct affs_bm_info *bm;
0247     struct buffer_head *bmap_bh = NULL, *bh = NULL;
0248     __be32 *bmap_blk;
0249     u32 size, blk, end, offset, mask;
0250     int i, res = 0;
0251     struct affs_sb_info *sbi = AFFS_SB(sb);
0252
0253     if (*flags & SB_RDONLY)
0254         return 0;
0255
0256     if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
0257         pr_notice("Bitmap invalid - mounting %s read only\n", sb->s_id);
0258         *flags |= SB_RDONLY;
0259         return 0;
0260     }
0261
0262     sbi->s_last_bmap = ~0;
0263     sbi->s_bmap_bh = NULL;
0264     sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
0265     sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
0266                  sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
0267     size = sbi->s_bmap_count * sizeof(*bm);
0268     bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
0269     if (!sbi->s_bitmap) {
0270         pr_err("Bitmap allocation failed\n");
0271         return -ENOMEM;
0272     }
0273
0274     bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
0275     blk = sb->s_blocksize / 4 - 49;
0276     end = blk + 25;
0277
0278     for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
0279         affs_brelse(bh);
0280
0281         bm->bm_key = be32_to_cpu(bmap_blk[blk]);
0282         bh = affs_bread(sb, bm->bm_key);
0283         if (!bh) {
0284             pr_err("Cannot read bitmap\n");
0285             res = -EIO;
0286             goto out;
0287         }
0288         if (affs_checksum_block(sb, bh)) {
0289             pr_warn("Bitmap %u invalid - mounting %s read only.\n",
0290                 bm->bm_key, sb->s_id);
0291             *flags |= SB_RDONLY;
0292             goto out;
0293         }
0294         pr_debug("read bitmap block %d: %d\n", blk, bm->bm_key);
0295         bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
0296
0297         /* Don't try read the extension if this is the last block,
0298          * but we also need the right bm pointer below
0299          */
0300         if (++blk < end || i == 1)
0301             continue;
0302         if (bmap_bh)
0303             affs_brelse(bmap_bh);
0304         bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
0305         if (!bmap_bh) {
0306             pr_err("Cannot read bitmap extension\n");
0307             res = -EIO;
0308             goto out;
0309         }
0310         bmap_blk = (__be32 *)bmap_bh->b_data;
0311         blk = 0;
0312         end = sb->s_blocksize / 4 - 1;
0313     }
0314
0315     offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
0316     mask = ~(0xFFFFFFFFU << (offset & 31));
0317     pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
0318     offset = offset / 32 + 1;
0319
0320     if (mask) {
0321         u32 old, new;
0322
0323         /* Mark unused bits in the last word as allocated */
0324         old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
0325         new = old & mask;
0326         //if (old != new) {
0327             ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
0328             /* fix checksum */
0329             //new -= old;
0330             //old = be32_to_cpu(*(__be32 *)bh->b_data);
0331             //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
0332             //mark_buffer_dirty(bh);
0333         //}
0334         /* correct offset for the bitmap count below */
0335         //offset++;
0336     }
0337     while (++offset < sb->s_blocksize / 4)
0338         ((__be32 *)bh->b_data)[offset] = 0;
0339     ((__be32 *)bh->b_data)[0] = 0;
0340     ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
0341     mark_buffer_dirty(bh);
0342
0343     /* recalculate bitmap count for last block */
0344     bm--;
0345     bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
0346
0347 out:
0348     affs_brelse(bh);
0349     affs_brelse(bmap_bh);
0350     return res;
0351 }
0352
0353 void affs_free_bitmap(struct super_block *sb)
0354 {
0355     struct affs_sb_info *sbi = AFFS_SB(sb);
0356
0357     if (!sbi->s_bitmap)
0358         return;
0359
0360     affs_brelse(sbi->s_bmap_bh);
0361     sbi->s_bmap_bh = NULL;
0362     sbi->s_last_bmap = ~0;
0363     kfree(sbi->s_bitmap);
0364     sbi->s_bitmap = NULL;
0365 }