xref: /openbmc/linux/fs/hfs/bitmap.c (revision 84d517f3)
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   */
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   */
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   */
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