libomfs/bitmap.c

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