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