Merge git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
[wrt350n-kernel.git] / fs / hfsplus / bitmap.c
blobd128a25b74d2e78ae14b5e06473629add09d620b
1 /*
2 * linux/fs/hfsplus/bitmap.c
4 * Copyright (C) 2001
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handling of allocation file
9 */
11 #include <linux/pagemap.h>
13 #include "hfsplus_fs.h"
14 #include "hfsplus_raw.h"
16 #define PAGE_CACHE_BITS (PAGE_CACHE_SIZE * 8)
18 int hfsplus_block_allocate(struct super_block *sb, u32 size, u32 offset, u32 *max)
20 struct page *page;
21 struct address_space *mapping;
22 __be32 *pptr, *curr, *end;
23 u32 mask, start, len, n;
24 __be32 val;
25 int i;
27 len = *max;
28 if (!len)
29 return size;
31 dprint(DBG_BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
32 mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
33 mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
34 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
35 pptr = kmap(page);
36 curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
37 i = offset % 32;
38 offset &= ~(PAGE_CACHE_BITS - 1);
39 if ((size ^ offset) / PAGE_CACHE_BITS)
40 end = pptr + PAGE_CACHE_BITS / 32;
41 else
42 end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
44 /* scan the first partial u32 for zero bits */
45 val = *curr;
46 if (~val) {
47 n = be32_to_cpu(val);
48 mask = (1U << 31) >> i;
49 for (; i < 32; mask >>= 1, i++) {
50 if (!(n & mask))
51 goto found;
54 curr++;
56 /* scan complete u32s for the first zero bit */
57 while (1) {
58 while (curr < end) {
59 val = *curr;
60 if (~val) {
61 n = be32_to_cpu(val);
62 mask = 1 << 31;
63 for (i = 0; i < 32; mask >>= 1, i++) {
64 if (!(n & mask))
65 goto found;
68 curr++;
70 kunmap(page);
71 offset += PAGE_CACHE_BITS;
72 if (offset >= size)
73 break;
74 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
75 NULL);
76 curr = pptr = kmap(page);
77 if ((size ^ offset) / PAGE_CACHE_BITS)
78 end = pptr + PAGE_CACHE_BITS / 32;
79 else
80 end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
82 dprint(DBG_BITMAP, "bitmap full\n");
83 start = size;
84 goto out;
86 found:
87 start = offset + (curr - pptr) * 32 + i;
88 if (start >= size) {
89 dprint(DBG_BITMAP, "bitmap full\n");
90 goto out;
92 /* do any partial u32 at the start */
93 len = min(size - start, len);
94 while (1) {
95 n |= mask;
96 if (++i >= 32)
97 break;
98 mask >>= 1;
99 if (!--len || n & mask)
100 goto done;
102 if (!--len)
103 goto done;
104 *curr++ = cpu_to_be32(n);
105 /* do full u32s */
106 while (1) {
107 while (curr < end) {
108 n = be32_to_cpu(*curr);
109 if (len < 32)
110 goto last;
111 if (n) {
112 len = 32;
113 goto last;
115 *curr++ = cpu_to_be32(0xffffffff);
116 len -= 32;
118 set_page_dirty(page);
119 kunmap(page);
120 offset += PAGE_CACHE_BITS;
121 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
122 NULL);
123 pptr = kmap(page);
124 curr = pptr;
125 end = pptr + PAGE_CACHE_BITS / 32;
127 last:
128 /* do any partial u32 at end */
129 mask = 1U << 31;
130 for (i = 0; i < len; i++) {
131 if (n & mask)
132 break;
133 n |= mask;
134 mask >>= 1;
136 done:
137 *curr = cpu_to_be32(n);
138 set_page_dirty(page);
139 kunmap(page);
140 *max = offset + (curr - pptr) * 32 + i - start;
141 HFSPLUS_SB(sb).free_blocks -= *max;
142 sb->s_dirt = 1;
143 dprint(DBG_BITMAP, "-> %u,%u\n", start, *max);
144 out:
145 mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
146 return start;
149 int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
151 struct page *page;
152 struct address_space *mapping;
153 __be32 *pptr, *curr, *end;
154 u32 mask, len, pnr;
155 int i;
157 /* is there any actual work to be done? */
158 if (!count)
159 return 0;
161 dprint(DBG_BITMAP, "block_free: %u,%u\n", offset, count);
162 /* are all of the bits in range? */
163 if ((offset + count) > HFSPLUS_SB(sb).total_blocks)
164 return -2;
166 mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
167 mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
168 pnr = offset / PAGE_CACHE_BITS;
169 page = read_mapping_page(mapping, pnr, NULL);
170 pptr = kmap(page);
171 curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
172 end = pptr + PAGE_CACHE_BITS / 32;
173 len = count;
175 /* do any partial u32 at the start */
176 i = offset % 32;
177 if (i) {
178 int j = 32 - i;
179 mask = 0xffffffffU << j;
180 if (j > count) {
181 mask |= 0xffffffffU >> (i + count);
182 *curr++ &= cpu_to_be32(mask);
183 goto out;
185 *curr++ &= cpu_to_be32(mask);
186 count -= j;
189 /* do full u32s */
190 while (1) {
191 while (curr < end) {
192 if (count < 32)
193 goto done;
194 *curr++ = 0;
195 count -= 32;
197 if (!count)
198 break;
199 set_page_dirty(page);
200 kunmap(page);
201 page = read_mapping_page(mapping, ++pnr, NULL);
202 pptr = kmap(page);
203 curr = pptr;
204 end = pptr + PAGE_CACHE_BITS / 32;
206 done:
207 /* do any partial u32 at end */
208 if (count) {
209 mask = 0xffffffffU >> count;
210 *curr &= cpu_to_be32(mask);
212 out:
213 set_page_dirty(page);
214 kunmap(page);
215 HFSPLUS_SB(sb).free_blocks += len;
216 sb->s_dirt = 1;
217 mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
219 return 0;