bitmap.c

   1 /* Routines for bitmap allocation */
   2 #include <errno.h>
   3 #include <stdlib.h>
   4 #include <assert.h>
   5 #include "omfs.h"
   6 #include "bits.h"
   7
   8
   9 static int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
  10
  11 unsigned long omfs_count_free(omfs_info_t *info)
  12 {
  13     unsigned int i;
  14     unsigned long sum = 0;
  15     size_t bsize = (swap_be64(info->super->num_blocks) + 7) / 8;
  16
  17     u8 *map = info->bitmap->bmap;
  18
  19     for (i = 0; i < bsize; i++)
  20         sum += nibblemap[map[i] & 0xf] + nibblemap[(map[i] >> 4) & 0xf];
  21
  22     return sum;
  23 }
  24
  25 /*
  26  *  Mark the bitmap block which holds an allocated/cleared bit dirty.
  27  *  Call after every set_bit/clear_bit in the bitmap.  Block is the
  28  *  *data* block number.
  29  */
  30 static void mark_dirty(omfs_info_t *info, u64 block)
  31 {
  32     int blocksize = swap_be32(info->super->blocksize);
  33     u64 bit_blk = (block >> 3) / blocksize;
  34     set_bit(info->bitmap->dirty, bit_blk);
  35 }
  36
  37 /*
  38  * Scan through a bitmap for power-of-two sized region (max 8).  This
  39  * should help to keep down fragmentation as mirrors will generally
  40  * align to 2 blocks and clusters to 8.
  41  */
  42 static int scan(u8* buf, int bsize, int bits)
  43 {
  44     int shift = 1 << bits;
  45     int mask = shift - 1;
  46     int m, i;
  47
  48     for (i=0; i < bsize * 8; i += bits)
  49     {
  50         m = mask << (i & 7);
  51         if (!(buf[ i >> 3 ] & m))
  52         {
  53             buf[ i >> 3 ] |= m;
  54             break;
  55         }
  56     }
  57     return i;
  58 }
  59
  60 int omfs_clear_range(omfs_info_t *info, u64 start, int count)
  61 {
  62     int i;
  63     u8 *bitmap = info->bitmap->bmap;
  64
  65     for (i=0; i < count; i++) {
  66         clear_bit(bitmap, i + start);
  67         mark_dirty(info, i + start);
  68     }
  69
  70     omfs_flush_bitmap(info);
  71     return 0;
  72 }
  73
  74 int omfs_allocate_one_block(omfs_info_t *info, u64 block)
  75 {
  76     int ok = 0;
  77     u8 *bitmap = info->bitmap->bmap;
  78
  79     if (!test_bit(bitmap, block))
  80     {
  81         set_bit(bitmap, block);
  82         mark_dirty(info, block);
  83         omfs_flush_bitmap(info);
  84         ok = 1;
  85     }
  86     return ok;
  87 }
  88
  89 int omfs_allocate_block(omfs_info_t *info, int size, u64 *return_block)
  90 {
  91     size_t bsize;
  92     int ret = 0;
  93     int block, i;
  94
  95     u8 *bitmap = info->bitmap->bmap;
  96
  97     bsize = (swap_be64(info->super->num_blocks) + 7) / 8;
  98
  99     assert(is_power_of_two(size));
 100
 101     block = scan(bitmap, bsize, size);
 102     if (block == bsize * 8) {
 103         ret = -ENOSPC;
 104         goto out;
 105     }
 106     *return_block = block;
 107
 108     for (i=0; i < size; i++)
 109         mark_dirty(info, block + i);
 110
 111     omfs_flush_bitmap(info);
 112 out:
 113     return ret;
 114 }
 115