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 */
29static 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
69found:
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	}
106done:
107	*curr = cpu_to_be32(n);
108	*max = (curr - bitmap) * 32 + i - start;
109	return start;
110}
111
112u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
113{
114	void *bitmap;
115	u32 pos;
116
117	/* make sure we have actual work to perform */
118	if (!*num_bits)
119		return 0;
120
121	down(&HFS_SB(sb)->bitmap_lock);
122	bitmap = HFS_SB(sb)->bitmap;
123
124	pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
125	if (pos >= HFS_SB(sb)->fs_ablocks) {
126		if (goal)
127			pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
128		if (pos >= HFS_SB(sb)->fs_ablocks) {
129			*num_bits = pos = 0;
130			goto out;
131		}
132	}
133
134	dprint(DBG_BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
135	HFS_SB(sb)->free_ablocks -= *num_bits;
136	hfs_bitmap_dirty(sb);
137out:
138	up(&HFS_SB(sb)->bitmap_lock);
139	return pos;
140}
141
142
143/*
144 * hfs_clear_vbm_bits()
145 *
146 * Description:
147 *   Clear the requested bits in the volume bitmap of the hfs filesystem
148 * Input Variable(s):
149 *   struct hfs_mdb *mdb: Pointer to the hfs MDB
150 *   u16 start: The offset of the first bit
151 *   u16 count: The number of bits
152 * Output Variable(s):
153 *   None
154 * Returns:
155 *    0: no error
156 *   -1: One of the bits was already clear.  This is a strange
157 *	 error and when it happens, the filesystem must be repaired!
158 *   -2: One or more of the bits are out of range of the bitmap.
159 * Preconditions:
160 *   'mdb' points to a "valid" (struct hfs_mdb).
161 * Postconditions:
162 *   Starting with bit number 'start', 'count' bits in the volume bitmap
163 *   are cleared. The affected bitmap blocks are marked "dirty", the free
164 *   block count of the MDB is updated and the MDB is marked dirty.
165 */
166int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
167{
168	__be32 *curr;
169	u32 mask;
170	int i, len;
171
172	/* is there any actual work to be done? */
173	if (!count)
174		return 0;
175
176	dprint(DBG_BITMAP, "clear_bits: %u,%u\n", start, count);
177	/* are all of the bits in range? */
178	if ((start + count) > HFS_SB(sb)->fs_ablocks)
179		return -2;
180
181	down(&HFS_SB(sb)->bitmap_lock);
182	/* bitmap is always on a 32-bit boundary */
183	curr = HFS_SB(sb)->bitmap + (start / 32);
184	len = count;
185
186	/* do any partial u32 at the start */
187	i = start % 32;
188	if (i) {
189		int j = 32 - i;
190		mask = 0xffffffffU << j;
191		if (j > count) {
192			mask |= 0xffffffffU >> (i + count);
193			*curr &= cpu_to_be32(mask);
194			goto out;
195		}
196		*curr++ &= cpu_to_be32(mask);
197		count -= j;
198	}
199
200	/* do full u32s */
201	while (count >= 32) {
202		*curr++ = 0;
203		count -= 32;
204	}
205	/* do any partial u32 at end */
206	if (count) {
207		mask = 0xffffffffU >> count;
208		*curr &= cpu_to_be32(mask);
209	}
210out:
211	HFS_SB(sb)->free_ablocks += len;
212	up(&HFS_SB(sb)->bitmap_lock);
213	hfs_bitmap_dirty(sb);
214
215	return 0;
216}
217