bitmap.c

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

FreeBSD/Linux Kernel Cross Reference
sys/fs/affs/bitmap.c
