xref: /openbmc/linux/fs/hfs/bitmap.c (revision c2b3e1f7)
1 /*
2  *  linux/fs/hfs/bitmap.c
3  *
4  * Copyright (C) 1996-1997  Paul H. Hargrove
5  * (C) 2003 Ardis Technologies <roman@ardistech.com>
6  * This file may be distributed under the terms of the GNU General Public License.
7  *
8  * Based on GPLed code Copyright (C) 1995  Michael Dreher
9  *
10  * This file contains the code to modify the volume bitmap:
11  * search/set/clear bits.
12  */
13 
14 #include "hfs_fs.h"
15 
16 /*
17  * hfs_find_zero_bit()
18  *
19  * Description:
20  *  Given a block of memory, its length in bits, and a starting bit number,
21  *  determine the number of the first zero bits (in left-to-right ordering)
22  *  in that range.
23  *
24  *  Returns >= 'size' if no zero bits are found in the range.
25  *
26  *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
27  *  may read beyond the 'size'th bit.
28  */
hfs_find_set_zero_bits(__be32 * bitmap,u32 size,u32 offset,u32 * max)29 static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max)
30 {
31 	__be32 *curr, *end;
32 	u32 mask, start, len, n;
33 	__be32 val;
34 	int i;
35 
36 	len = *max;
37 	if (!len)
38 		return size;
39 
40 	curr = bitmap + (offset / 32);
41 	end = bitmap + ((size + 31) / 32);
42 
43 	/* scan the first partial u32 for zero bits */
44 	val = *curr;
45 	if (~val) {
46 		n = be32_to_cpu(val);
47 		i = offset % 32;
48 		mask = (1U << 31) >> i;
49 		for (; i < 32; mask >>= 1, i++) {
50 			if (!(n & mask))
51 				goto found;
52 		}
53 	}
54 
55 	/* scan complete u32s for the first zero bit */
56 	while (++curr < end) {
57 		val = *curr;
58 		if (~val) {
59 			n = be32_to_cpu(val);
60 			mask = 1 << 31;
61 			for (i = 0; i < 32; mask >>= 1, i++) {
62 				if (!(n & mask))
63 					goto found;
64 			}
65 		}
66 	}
67 	return size;
68 
69 found:
70 	start = (curr - bitmap) * 32 + i;
71 	if (start >= size)
72 		return start;
73 	/* do any partial u32 at the start */
74 	len = min(size - start, len);
75 	while (1) {
76 		n |= mask;
77 		if (++i >= 32)
78 			break;
79 		mask >>= 1;
80 		if (!--len || n & mask)
81 			goto done;
82 	}
83 	if (!--len)
84 		goto done;
85 	*curr++ = cpu_to_be32(n);
86 	/* do full u32s */
87 	while (1) {
88 		n = be32_to_cpu(*curr);
89 		if (len < 32)
90 			break;
91 		if (n) {
92 			len = 32;
93 			break;
94 		}
95 		*curr++ = cpu_to_be32(0xffffffff);
96 		len -= 32;
97 	}
98 	/* do any partial u32 at end */
99 	mask = 1U << 31;
100 	for (i = 0; i < len; i++) {
101 		if (n & mask)
102 			break;
103 		n |= mask;
104 		mask >>= 1;
105 	}
106 done:
107 	*curr = cpu_to_be32(n);
108 	*max = (curr - bitmap) * 32 + i - start;
109 	return start;
110 }
111 
112 /*
113  * hfs_vbm_search_free()
114  *
115  * Description:
116  *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
117  *   the hfs MDB. 'mdb' had better be locked or the returned range
118  *   may be no longer free, when this functions returns!
119  *   XXX Currently the search starts from bit 0, but it should start with
120  *   the bit number stored in 's_alloc_ptr' of the MDB.
121  * Input Variable(s):
122  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
123  *   u16 *num_bits: Pointer to the number of cleared bits
124  *     to search for
125  * Output Variable(s):
126  *   u16 *num_bits: The number of consecutive clear bits of the
127  *     returned range. If the bitmap is fragmented, this will be less than
128  *     requested and it will be zero, when the disk is full.
129  * Returns:
130  *   The number of the first bit of the range of cleared bits which has been
131  *   found. When 'num_bits' is zero, this is invalid!
132  * Preconditions:
133  *   'mdb' points to a "valid" (struct hfs_mdb).
134  *   'num_bits' points to a variable of type (u16), which contains
135  *	the number of cleared bits to find.
136  * Postconditions:
137  *   'num_bits' is set to the length of the found sequence.
138  */
hfs_vbm_search_free(struct super_block * sb,u32 goal,u32 * num_bits)139 u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
140 {
141 	void *bitmap;
142 	u32 pos;
143 
144 	/* make sure we have actual work to perform */
145 	if (!*num_bits)
146 		return 0;
147 
148 	mutex_lock(&HFS_SB(sb)->bitmap_lock);
149 	bitmap = HFS_SB(sb)->bitmap;
150 
151 	pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
152 	if (pos >= HFS_SB(sb)->fs_ablocks) {
153 		if (goal)
154 			pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
155 		if (pos >= HFS_SB(sb)->fs_ablocks) {
156 			*num_bits = pos = 0;
157 			goto out;
158 		}
159 	}
160 
161 	hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
162 	HFS_SB(sb)->free_ablocks -= *num_bits;
163 	hfs_bitmap_dirty(sb);
164 out:
165 	mutex_unlock(&HFS_SB(sb)->bitmap_lock);
166 	return pos;
167 }
168 
169 
170 /*
171  * hfs_clear_vbm_bits()
172  *
173  * Description:
174  *   Clear the requested bits in the volume bitmap of the hfs filesystem
175  * Input Variable(s):
176  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
177  *   u16 start: The offset of the first bit
178  *   u16 count: The number of bits
179  * Output Variable(s):
180  *   None
181  * Returns:
182  *    0: no error
183  *   -1: One of the bits was already clear.  This is a strange
184  *	 error and when it happens, the filesystem must be repaired!
185  *   -2: One or more of the bits are out of range of the bitmap.
186  * Preconditions:
187  *   'mdb' points to a "valid" (struct hfs_mdb).
188  * Postconditions:
189  *   Starting with bit number 'start', 'count' bits in the volume bitmap
190  *   are cleared. The affected bitmap blocks are marked "dirty", the free
191  *   block count of the MDB is updated and the MDB is marked dirty.
192  */
hfs_clear_vbm_bits(struct super_block * sb,u16 start,u16 count)193 int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
194 {
195 	__be32 *curr;
196 	u32 mask;
197 	int i, len;
198 
199 	/* is there any actual work to be done? */
200 	if (!count)
201 		return 0;
202 
203 	hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count);
204 	/* are all of the bits in range? */
205 	if ((start + count) > HFS_SB(sb)->fs_ablocks)
206 		return -2;
207 
208 	mutex_lock(&HFS_SB(sb)->bitmap_lock);
209 	/* bitmap is always on a 32-bit boundary */
210 	curr = HFS_SB(sb)->bitmap + (start / 32);
211 	len = count;
212 
213 	/* do any partial u32 at the start */
214 	i = start % 32;
215 	if (i) {
216 		int j = 32 - i;
217 		mask = 0xffffffffU << j;
218 		if (j > count) {
219 			mask |= 0xffffffffU >> (i + count);
220 			*curr &= cpu_to_be32(mask);
221 			goto out;
222 		}
223 		*curr++ &= cpu_to_be32(mask);
224 		count -= j;
225 	}
226 
227 	/* do full u32s */
228 	while (count >= 32) {
229 		*curr++ = 0;
230 		count -= 32;
231 	}
232 	/* do any partial u32 at end */
233 	if (count) {
234 		mask = 0xffffffffU >> count;
235 		*curr &= cpu_to_be32(mask);
236 	}
237 out:
238 	HFS_SB(sb)->free_ablocks += len;
239 	mutex_unlock(&HFS_SB(sb)->bitmap_lock);
240 	hfs_bitmap_dirty(sb);
241 
242 	return 0;
243 }
244