Line data Source code
1 : #include "clusterautoconfig.h"
2 :
3 : #include <inttypes.h>
4 : #include <stdlib.h>
5 : #include <string.h>
6 : #include <unistd.h>
7 : #include <limits.h>
8 :
9 : #include "libgfs2.h"
10 :
11 : #if BITS_PER_LONG == 32
12 : #define LBITMASK (0x55555555UL)
13 : #define LBITSKIP55 (0x55555555UL)
14 : #define LBITSKIP00 (0x00000000UL)
15 : #else
16 : #define LBITMASK (0x5555555555555555UL)
17 : #define LBITSKIP55 (0x5555555555555555UL)
18 : #define LBITSKIP00 (0x0000000000000000UL)
19 : #endif
20 :
21 : #define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))
22 :
23 : /**
24 : * bit_search
25 : * @ptr: Pointer to bitmap data
26 : * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
27 : * @state: The state we are searching for
28 : *
29 : * We xor the bitmap data with a patter which is the bitwise opposite
30 : * of what we are looking for, this gives rise to a pattern of ones
31 : * wherever there is a match. Since we have two bits per entry, we
32 : * take this pattern, shift it down by one place and then and it with
33 : * the original. All the even bit positions (0,2,4, etc) then represent
34 : * successful matches, so we mask with 0x55555..... to remove the unwanted
35 : * odd bit positions.
36 : *
37 : * This allows searching of a whole u64 at once (32 blocks) with a
38 : * single test (on 64 bit arches).
39 : */
40 :
41 39029205 : static inline uint64_t bit_search(const __le64 *ptr,
42 : unsigned long long mask,
43 : uint8_t state)
44 : {
45 : unsigned long long tmp;
46 : static const unsigned long long search[] = {
47 : [0] = 0xffffffffffffffffULL,
48 : [1] = 0xaaaaaaaaaaaaaaaaULL,
49 : [2] = 0x5555555555555555ULL,
50 : [3] = 0x0000000000000000ULL,
51 : };
52 39029205 : tmp = le64_to_cpu(*ptr) ^ search[state];
53 39029205 : tmp &= (tmp >> 1);
54 39029205 : tmp &= mask;
55 39029205 : return tmp;
56 : }
57 :
58 : /**
59 : * lgfs2_bitfit - Find a free block in the bitmaps
60 : * @buffer: the buffer that holds the bitmaps
61 : * @buflen: the length (in bytes) of the buffer
62 : * @goal: the block to try to allocate
63 : * @old_state: the state of the block we're looking for
64 : *
65 : * Return: the block number that was allocated
66 : */
67 321299 : unsigned long lgfs2_bitfit(const unsigned char *buf, const unsigned int len,
68 : unsigned long goal, unsigned char state)
69 : {
70 321299 : uint32_t spoint = (goal << 1) & ((8 * sizeof(uint64_t)) - 1);
71 321299 : const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
72 321299 : const __le64 *end = (__le64 *) (buf + ALIGN(len, sizeof(uint64_t)));
73 : uint64_t tmp;
74 321299 : uint64_t mask = 0x5555555555555555ULL;
75 : uint32_t bit;
76 :
77 321299 : if (state > 3)
78 0 : return 0;
79 :
80 : /* Mask off bits we don't care about at the start of the search */
81 321299 : mask <<= spoint;
82 321299 : tmp = bit_search(ptr, mask, state);
83 321299 : ptr++;
84 39029205 : while(tmp == 0 && ptr < end) {
85 38707906 : tmp = bit_search(ptr, 0x5555555555555555ULL, state);
86 38707906 : ptr++;
87 : }
88 : /* Mask off any bits which are more than len bytes from the start */
89 321299 : if (ptr == end && (len & (sizeof(uint64_t) - 1)))
90 1800 : tmp &= (((uint64_t)~0) >>
91 1800 : (64 - 8 * (len & (sizeof(uint64_t) - 1))));
92 : /* Didn't find anything, so return */
93 321299 : if (tmp == 0)
94 223826 : return LGFS2_BFITNOENT;
95 97473 : ptr--;
96 97473 : bit = ffsll(tmp);
97 97473 : bit /= 2; /* two bits per entry in the bitmap */
98 97473 : return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
99 : }
100 :
101 : /*
102 : * lgfs2_check_range - check if blkno is within FS limits
103 : * @sdp: super block
104 : * @blkno: block number
105 : *
106 : * Returns: 0 if ok, -1 if out of bounds
107 : */
108 2171329 : int lgfs2_check_range(struct lgfs2_sbd *sdp, uint64_t blkno)
109 : {
110 2171329 : if((blkno > sdp->fssize) || (blkno <= LGFS2_SB_ADDR(sdp)))
111 6 : return -1;
112 2171323 : return 0;
113 : }
114 :
115 : /*
116 : * lgfs2_set_bitmap
117 : * @sdp: super block
118 : * @blkno: block number relative to file system
119 : * @state: one of three possible states
120 : *
121 : * This function sets the value of a bit of the
122 : * file system bitmap.
123 : *
124 : * Returns: 0 on success, -1 on error
125 : */
126 2528809 : int lgfs2_set_bitmap(lgfs2_rgrp_t rgd, uint64_t blkno, int state)
127 : {
128 : int buf;
129 : uint32_t rgrp_block;
130 2528809 : struct lgfs2_bitmap *bits = NULL;
131 : unsigned char *byte, cur_state;
132 : unsigned int bit;
133 :
134 : /* FIXME: should GFS2_BLKST_INVALID be allowed */
135 2528809 : if ((state < GFS2_BLKST_FREE) || (state > GFS2_BLKST_DINODE))
136 0 : return -1;
137 :
138 2528809 : if(!rgd || blkno < rgd->rt_data0)
139 0 : return -1;
140 :
141 2528809 : rgrp_block = (uint32_t)(blkno - rgd->rt_data0);
142 7226861 : for(buf= 0; buf < rgd->rt_length; buf++){
143 7226861 : bits = &(rgd->rt_bits[buf]);
144 7226861 : if(rgrp_block < ((bits->bi_start + bits->bi_len)*GFS2_NBBY))
145 2528809 : break;
146 : }
147 :
148 2528809 : if (bits == NULL)
149 0 : return -1;
150 2528809 : byte = (unsigned char *)(bits->bi_data + bits->bi_offset) +
151 2528809 : (rgrp_block/GFS2_NBBY - bits->bi_start);
152 2528809 : bit = (rgrp_block % GFS2_NBBY) * GFS2_BIT_SIZE;
153 :
154 2528809 : cur_state = (*byte >> bit) & GFS2_BIT_MASK;
155 2528809 : *byte ^= cur_state << bit;
156 2528809 : *byte |= state << bit;
157 :
158 2528809 : bits->bi_modified = 1;
159 2528809 : return 0;
160 : }
161 :
162 : /*
163 : * lgfs2_get_bitmap - get value of FS bitmap
164 : * @sdp: super block
165 : * @blkno: block number relative to file system
166 : *
167 : * This function gets the value of a bit of the
168 : * file system bitmap.
169 : * Possible state values for a block in the bitmap are:
170 : * GFS_BLKST_FREE (0)
171 : * GFS_BLKST_USED (1)
172 : * GFS_BLKST_INVALID (2)
173 : * GFS_BLKST_DINODE (3)
174 : *
175 : * Returns: state on success, -1 on error
176 : */
177 2001257 : int lgfs2_get_bitmap(struct lgfs2_sbd *sdp, uint64_t blkno, struct lgfs2_rgrp_tree *rgd)
178 : {
179 : uint64_t offset;
180 2001257 : uint32_t i = 0;
181 : char *byte;
182 : unsigned int bit;
183 : struct lgfs2_bitmap *bi;
184 :
185 2001257 : if (rgd == NULL) {
186 2 : rgd = lgfs2_blk2rgrpd(sdp, blkno);
187 2 : if(rgd == NULL)
188 0 : return -1;
189 : }
190 :
191 2001257 : offset = blkno - rgd->rt_data0;
192 2001257 : if (offset > UINT_MAX) {
193 0 : errno = EINVAL;
194 0 : return -1;
195 : }
196 2001257 : if (offset >= rgd->rt_data0 + rgd->rt_data) {
197 0 : errno = E2BIG;
198 0 : return -1;
199 : }
200 :
201 2001257 : if (offset >= ((uint64_t)rgd->rt_bits->bi_start + rgd->rt_bits->bi_len) * GFS2_NBBY) {
202 1217892 : offset += (sizeof(struct gfs2_rgrp) - sizeof(struct gfs2_meta_header))
203 : * GFS2_NBBY;
204 1217892 : i = offset / sdp->sd_blocks_per_bitmap;
205 1217892 : offset -= (uint64_t)i * sdp->sd_blocks_per_bitmap;
206 : }
207 :
208 2001257 : bi = &rgd->rt_bits[i];
209 2001257 : if (bi->bi_data == NULL)
210 0 : return GFS2_BLKST_FREE;
211 :
212 2001257 : byte = (bi->bi_data + bi->bi_offset) + (offset/GFS2_NBBY);
213 2001257 : bit = (offset % GFS2_NBBY) * GFS2_BIT_SIZE;
214 :
215 2001257 : return (*byte >> bit) & GFS2_BIT_MASK;
216 : }
|
