Root/fs/hfs/bitmap.c

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
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 */
139u32 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    dprint(DBG_BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
162    HFS_SB(sb)->free_ablocks -= *num_bits;
163    hfs_bitmap_dirty(sb);
164out:
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 */
193int 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    dprint(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    }
237out:
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

Archive Download this file



interactive