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