linux/fs/affs/bitmap.c
<<
>>
Prefs
   1/*
   2 *  linux/fs/affs/bitmap.c
   3 *
   4 *  (c) 1996 Hans-Joachim Widmaier
   5 *
   6 *  bitmap.c contains the code that handles all bitmap related stuff -
   7 *  block allocation, deallocation, calculation of free space.
   8 */
   9
  10#include "affs.h"
  11
  12/* This is, of course, shamelessly stolen from fs/minix */
  13
  14static const int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
  15
  16static u32
  17affs_count_free_bits(u32 blocksize, const void *data)
  18{
  19        const u32 *map;
  20        u32 free;
  21        u32 tmp;
  22
  23        map = data;
  24        free = 0;
  25        for (blocksize /= 4; blocksize > 0; blocksize--) {
  26                tmp = *map++;
  27                while (tmp) {
  28                        free += nibblemap[tmp & 0xf];
  29                        tmp >>= 4;
  30                }
  31        }
  32
  33        return free;
  34}
  35
  36u32
  37affs_count_free_blocks(struct super_block *sb)
  38{
  39        struct affs_bm_info *bm;
  40        u32 free;
  41        int i;
  42
  43        pr_debug("AFFS: count_free_blocks()\n");
  44
  45        if (sb->s_flags & MS_RDONLY)
  46                return 0;
  47
  48        mutex_lock(&AFFS_SB(sb)->s_bmlock);
  49
  50        bm = AFFS_SB(sb)->s_bitmap;
  51        free = 0;
  52        for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
  53                free += bm->bm_free;
  54
  55        mutex_unlock(&AFFS_SB(sb)->s_bmlock);
  56
  57        return free;
  58}
  59
  60void
  61affs_free_block(struct super_block *sb, u32 block)
  62{
  63        struct affs_sb_info *sbi = AFFS_SB(sb);
  64        struct affs_bm_info *bm;
  65        struct buffer_head *bh;
  66        u32 blk, bmap, bit, mask, tmp;
  67        __be32 *data;
  68
  69        pr_debug("AFFS: free_block(%u)\n", block);
  70
  71        if (block > sbi->s_partition_size)
  72                goto err_range;
  73
  74        blk     = block - sbi->s_reserved;
  75        bmap    = blk / sbi->s_bmap_bits;
  76        bit     = blk % sbi->s_bmap_bits;
  77        bm      = &sbi->s_bitmap[bmap];
  78
  79        mutex_lock(&sbi->s_bmlock);
  80
  81        bh = sbi->s_bmap_bh;
  82        if (sbi->s_last_bmap != bmap) {
  83                affs_brelse(bh);
  84                bh = affs_bread(sb, bm->bm_key);
  85                if (!bh)
  86                        goto err_bh_read;
  87                sbi->s_bmap_bh = bh;
  88                sbi->s_last_bmap = bmap;
  89        }
  90
  91        mask = 1 << (bit & 31);
  92        data = (__be32 *)bh->b_data + bit / 32 + 1;
  93
  94        /* mark block free */
  95        tmp = be32_to_cpu(*data);
  96        if (tmp & mask)
  97                goto err_free;
  98        *data = cpu_to_be32(tmp | mask);
  99
 100        /* fix checksum */
 101        tmp = be32_to_cpu(*(__be32 *)bh->b_data);
 102        *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
 103
 104        mark_buffer_dirty(bh);
 105        sb->s_dirt = 1;
 106        bm->bm_free++;
 107
 108        mutex_unlock(&sbi->s_bmlock);
 109        return;
 110
 111err_free:
 112        affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
 113        mutex_unlock(&sbi->s_bmlock);
 114        return;
 115
 116err_bh_read:
 117        affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
 118        sbi->s_bmap_bh = NULL;
 119        sbi->s_last_bmap = ~0;
 120        mutex_unlock(&sbi->s_bmlock);
 121        return;
 122
 123err_range:
 124        affs_error(sb, "affs_free_block","Block %u outside partition", block);
 125        return;
 126}
 127
 128/*
 129 * Allocate a block in the given allocation zone.
 130 * Since we have to byte-swap the bitmap on little-endian
 131 * machines, this is rather expensive. Therefor we will
 132 * preallocate up to 16 blocks from the same word, if
 133 * possible. We are not doing preallocations in the
 134 * header zone, though.
 135 */
 136
 137u32
 138affs_alloc_block(struct inode *inode, u32 goal)
 139{
 140        struct super_block *sb;
 141        struct affs_sb_info *sbi;
 142        struct affs_bm_info *bm;
 143        struct buffer_head *bh;
 144        __be32 *data, *enddata;
 145        u32 blk, bmap, bit, mask, mask2, tmp;
 146        int i;
 147
 148        sb = inode->i_sb;
 149        sbi = AFFS_SB(sb);
 150
 151        pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
 152
 153        if (AFFS_I(inode)->i_pa_cnt) {
 154                pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
 155                AFFS_I(inode)->i_pa_cnt--;
 156                return ++AFFS_I(inode)->i_lastalloc;
 157        }
 158
 159        if (!goal || goal > sbi->s_partition_size) {
 160                if (goal)
 161                        affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
 162                //if (!AFFS_I(inode)->i_last_block)
 163                //      affs_warning(sb, "affs_balloc", "no last alloc block");
 164                goal = sbi->s_reserved;
 165        }
 166
 167        blk = goal - sbi->s_reserved;
 168        bmap = blk / sbi->s_bmap_bits;
 169        bm = &sbi->s_bitmap[bmap];
 170
 171        mutex_lock(&sbi->s_bmlock);
 172
 173        if (bm->bm_free)
 174                goto find_bmap_bit;
 175
 176find_bmap:
 177        /* search for the next bmap buffer with free bits */
 178        i = sbi->s_bmap_count;
 179        do {
 180                if (--i < 0)
 181                        goto err_full;
 182                bmap++;
 183                bm++;
 184                if (bmap < sbi->s_bmap_count)
 185                        continue;
 186                /* restart search at zero */
 187                bmap = 0;
 188                bm = sbi->s_bitmap;
 189        } while (!bm->bm_free);
 190        blk = bmap * sbi->s_bmap_bits;
 191
 192find_bmap_bit:
 193
 194        bh = sbi->s_bmap_bh;
 195        if (sbi->s_last_bmap != bmap) {
 196                affs_brelse(bh);
 197                bh = affs_bread(sb, bm->bm_key);
 198                if (!bh)
 199                        goto err_bh_read;
 200                sbi->s_bmap_bh = bh;
 201                sbi->s_last_bmap = bmap;
 202        }
 203
 204        /* find an unused block in this bitmap block */
 205        bit = blk % sbi->s_bmap_bits;
 206        data = (__be32 *)bh->b_data + bit / 32 + 1;
 207        enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
 208        mask = ~0UL << (bit & 31);
 209        blk &= ~31UL;
 210
 211        tmp = be32_to_cpu(*data);
 212        if (tmp & mask)
 213                goto find_bit;
 214
 215        /* scan the rest of the buffer */
 216        do {
 217                blk += 32;
 218                if (++data >= enddata)
 219                        /* didn't find something, can only happen
 220                         * if scan didn't start at 0, try next bmap
 221                         */
 222                        goto find_bmap;
 223        } while (!*data);
 224        tmp = be32_to_cpu(*data);
 225        mask = ~0;
 226
 227find_bit:
 228        /* finally look for a free bit in the word */
 229        bit = ffs(tmp & mask) - 1;
 230        blk += bit + sbi->s_reserved;
 231        mask2 = mask = 1 << (bit & 31);
 232        AFFS_I(inode)->i_lastalloc = blk;
 233
 234        /* prealloc as much as possible within this word */
 235        while ((mask2 <<= 1)) {
 236                if (!(tmp & mask2))
 237                        break;
 238                AFFS_I(inode)->i_pa_cnt++;
 239                mask |= mask2;
 240        }
 241        bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
 242
 243        *data = cpu_to_be32(tmp & ~mask);
 244
 245        /* fix checksum */
 246        tmp = be32_to_cpu(*(__be32 *)bh->b_data);
 247        *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
 248
 249        mark_buffer_dirty(bh);
 250        sb->s_dirt = 1;
 251
 252        mutex_unlock(&sbi->s_bmlock);
 253
 254        pr_debug("%d\n", blk);
 255        return blk;
 256
 257err_bh_read:
 258        affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
 259        sbi->s_bmap_bh = NULL;
 260        sbi->s_last_bmap = ~0;
 261err_full:
 262        mutex_unlock(&sbi->s_bmlock);
 263        pr_debug("failed\n");
 264        return 0;
 265}
 266
 267int affs_init_bitmap(struct super_block *sb, int *flags)
 268{
 269        struct affs_bm_info *bm;
 270        struct buffer_head *bmap_bh = NULL, *bh = NULL;
 271        __be32 *bmap_blk;
 272        u32 size, blk, end, offset, mask;
 273        int i, res = 0;
 274        struct affs_sb_info *sbi = AFFS_SB(sb);
 275
 276        if (*flags & MS_RDONLY)
 277                return 0;
 278
 279        if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
 280                printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
 281                        sb->s_id);
 282                *flags |= MS_RDONLY;
 283                return 0;
 284        }
 285
 286        sbi->s_last_bmap = ~0;
 287        sbi->s_bmap_bh = NULL;
 288        sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
 289        sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
 290                                 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
 291        size = sbi->s_bmap_count * sizeof(*bm);
 292        bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
 293        if (!sbi->s_bitmap) {
 294                printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
 295                return -ENOMEM;
 296        }
 297
 298        bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
 299        blk = sb->s_blocksize / 4 - 49;
 300        end = blk + 25;
 301
 302        for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
 303                affs_brelse(bh);
 304
 305                bm->bm_key = be32_to_cpu(bmap_blk[blk]);
 306                bh = affs_bread(sb, bm->bm_key);
 307                if (!bh) {
 308                        printk(KERN_ERR "AFFS: Cannot read bitmap\n");
 309                        res = -EIO;
 310                        goto out;
 311                }
 312                if (affs_checksum_block(sb, bh)) {
 313                        printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
 314                               bm->bm_key, sb->s_id);
 315                        *flags |= MS_RDONLY;
 316                        goto out;
 317                }
 318                pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
 319                bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
 320
 321                /* Don't try read the extension if this is the last block,
 322                 * but we also need the right bm pointer below
 323                 */
 324                if (++blk < end || i == 1)
 325                        continue;
 326                if (bmap_bh)
 327                        affs_brelse(bmap_bh);
 328                bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
 329                if (!bmap_bh) {
 330                        printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
 331                        res = -EIO;
 332                        goto out;
 333                }
 334                bmap_blk = (__be32 *)bmap_bh->b_data;
 335                blk = 0;
 336                end = sb->s_blocksize / 4 - 1;
 337        }
 338
 339        offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
 340        mask = ~(0xFFFFFFFFU << (offset & 31));
 341        pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
 342        offset = offset / 32 + 1;
 343
 344        if (mask) {
 345                u32 old, new;
 346
 347                /* Mark unused bits in the last word as allocated */
 348                old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
 349                new = old & mask;
 350                //if (old != new) {
 351                        ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
 352                        /* fix checksum */
 353                        //new -= old;
 354                        //old = be32_to_cpu(*(__be32 *)bh->b_data);
 355                        //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
 356                        //mark_buffer_dirty(bh);
 357                //}
 358                /* correct offset for the bitmap count below */
 359                //offset++;
 360        }
 361        while (++offset < sb->s_blocksize / 4)
 362                ((__be32 *)bh->b_data)[offset] = 0;
 363        ((__be32 *)bh->b_data)[0] = 0;
 364        ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
 365        mark_buffer_dirty(bh);
 366
 367        /* recalculate bitmap count for last block */
 368        bm--;
 369        bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
 370
 371out:
 372        affs_brelse(bh);
 373        affs_brelse(bmap_bh);
 374        return res;
 375}
 376
 377void affs_free_bitmap(struct super_block *sb)
 378{
 379        struct affs_sb_info *sbi = AFFS_SB(sb);
 380
 381        if (!sbi->s_bitmap)
 382                return;
 383
 384        affs_brelse(sbi->s_bmap_bh);
 385        sbi->s_bmap_bh = NULL;
 386        sbi->s_last_bmap = ~0;
 387        kfree(sbi->s_bitmap);
 388        sbi->s_bitmap = NULL;
 389}
 390