[GFS2] The core of GFS2
[linux-2.6.git] / 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