fs/gfs2/bits.c

   1 /*
   2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
   3  * Copyright (C) 2004-2005 Red Hat, Inc.  All rights reserved.
   4  *
   5  * This copyrighted material is made available to anyone wishing to use,
   6  * modify, copy, or redistribute it subject to the terms and conditions
   7  * of the GNU General Public License v.2.
   8  */
   9
  10 /*
  11  * These routines are used by the resource group routines (rgrp.c)
  12  * to keep track of block allocation.  Each block is represented by two
  13  * bits.  One bit indicates whether or not the block is used.  (1=used,
  14  * 0=free)  The other bit indicates whether or not the block contains a
  15  * dinode or not.  (1=dinode, 0=not-dinode) So, each byte represents
  16  * GFS2_NBBY (i.e. 4) blocks.
  17  */
  18
  19 #include <linux/sched.h>
  20 #include <linux/slab.h>
  21 #include <linux/spinlock.h>
  22 #include <linux/completion.h>
  23 #include <linux/buffer_head.h>
  24 #include <asm/semaphore.h>
  25
  26 #include "gfs2.h"
  27 #include "bits.h"
  28
  29 static const char valid_change[16] = {
  30                 /* current */
  31         /* n */ 0, 1, 0, 1,
  32         /* e */ 1, 0, 0, 0,
  33         /* w */ 0, 0, 0, 0,
  34                 1, 0, 0, 0
  35 };
  36
  37 /**
  38  * gfs2_setbit - Set a bit in the bitmaps
  39  * @buffer: the buffer that holds the bitmaps
  40  * @buflen: the length (in bytes) of the buffer
  41  * @block: the block to set
  42  * @new_state: the new state of the block
  43  *
  44  */
  45
  46 void gfs2_setbit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  47                  unsigned int buflen, uint32_t block, unsigned char new_state)
  48 {
  49         unsigned char *byte, *end, cur_state;
  50         unsigned int bit;
  51
  52         byte = buffer + (block / GFS2_NBBY);
  53         bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
  54         end = buffer + buflen;
  55
  56         gfs2_assert(rgd->rd_sbd, byte < end);
  57
  58         cur_state = (*byte >> bit) & GFS2_BIT_MASK;
  59
  60         if (valid_change[new_state * 4 + cur_state]) {
  61                 *byte ^= cur_state << bit;
  62                 *byte |= new_state << bit;
  63         } else
  64                 gfs2_consist_rgrpd(rgd);
  65 }
  66
  67 /**
  68  * gfs2_testbit - test a bit in the bitmaps
  69  * @buffer: the buffer that holds the bitmaps
  70  * @buflen: the length (in bytes) of the buffer
  71  * @block: the block to read
  72  *
  73  */
  74
  75 unsigned char gfs2_testbit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  76                            unsigned int buflen, uint32_t block)
  77 {
  78         unsigned char *byte, *end, cur_state;
  79         unsigned int bit;
  80
  81         byte = buffer + (block / GFS2_NBBY);
  82         bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
  83         end = buffer + buflen;
  84
  85         gfs2_assert(rgd->rd_sbd, byte < end);
  86
  87         cur_state = (*byte >> bit) & GFS2_BIT_MASK;
  88
  89         return cur_state;
  90 }
  91
  92 /**
  93  * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
  94  *       a block in a given allocation state.
  95  * @buffer: the buffer that holds the bitmaps
  96  * @buflen: the length (in bytes) of the buffer
  97  * @goal: start search at this block's bit-pair (within @buffer)
  98  * @old_state: GFS2_BLKST_XXX the state of the block we're looking for;
  99  *       bit 0 = alloc(1)/free(0), bit 1 = meta(1)/data(0)
 100  *
 101  * Scope of @goal and returned block number is only within this bitmap buffer,
 102  * not entire rgrp or filesystem.  @buffer will be offset from the actual
 103  * beginning of a bitmap block buffer, skipping any header structures.
 104  *
 105  * Return: the block number (bitmap buffer scope) that was found
 106  */
 107
 108 uint32_t gfs2_bitfit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
 109                      unsigned int buflen, uint32_t goal,
 110                      unsigned char old_state)
 111 {
 112         unsigned char *byte, *end, alloc;
 113         uint32_t blk = goal;
 114         unsigned int bit;
 115
 116         byte = buffer + (goal / GFS2_NBBY);
 117         bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
 118         end = buffer + buflen;
 119         alloc = (old_state & 1) ? 0 : 0x55;
 120
 121         while (byte < end) {
 122                 if ((*byte & 0x55) == alloc) {
 123                         blk += (8 - bit) >> 1;
 124
 125                         bit = 0;
 126                         byte++;
 127
 128                         continue;
 129                 }
 130
 131                 if (((*byte >> bit) & GFS2_BIT_MASK) == old_state)
 132                         return blk;
 133
 134                 bit += GFS2_BIT_SIZE;
 135                 if (bit >= 8) {
 136                         bit = 0;
 137                         byte++;
 138                 }
 139
 140                 blk++;
 141         }
 142
 143         return BFITNOENT;
 144 }
 145
 146 /**
 147  * gfs2_bitcount - count the number of bits in a certain state
 148  * @buffer: the buffer that holds the bitmaps
 149  * @buflen: the length (in bytes) of the buffer
 150  * @state: the state of the block we're looking for
 151  *
 152  * Returns: The number of bits
 153  */
 154
 155 uint32_t gfs2_bitcount(struct gfs2_rgrpd *rgd, unsigned char *buffer,
 156                        unsigned int buflen, unsigned char state)
 157 {
 158         unsigned char *byte = buffer;
 159         unsigned char *end = buffer + buflen;
 160         unsigned char state1 = state << 2;
 161         unsigned char state2 = state << 4;
 162         unsigned char state3 = state << 6;
 163         uint32_t count = 0;
 164
 165         for (; byte < end; byte++) {
 166                 if (((*byte) & 0x03) == state)
 167                         count++;
 168                 if (((*byte) & 0x0C) == state1)
 169                         count++;
 170                 if (((*byte) & 0x30) == state2)
 171                         count++;
 172                 if (((*byte) & 0xC0) == state3)
 173                         count++;
 174         }
 175
 176         return count;
 177 }
 178