blob: d128a25b74d2e78ae14b5e06473629add09d620b [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);
Jes Sorensen1b1dcc12006-01-09 15:59:24 -080032 mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
Linus Torvalds1da177e2005-04-16 15:20:36 -070033 mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
Pekka Enberg090d2b12006-06-23 02:05:08 -070034 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070035 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;
43
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;
52 }
53 }
54 curr++;
55
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;
66 }
67 }
68 curr++;
69 }
70 kunmap(page);
71 offset += PAGE_CACHE_BITS;
72 if (offset >= size)
73 break;
Pekka Enberg090d2b12006-06-23 02:05:08 -070074 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
75 NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070076 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;
81 }
82 dprint(DBG_BITMAP, "bitmap full\n");
83 start = size;
84 goto out;
85
86found:
87 start = offset + (curr - pptr) * 32 + i;
88 if (start >= size) {
89 dprint(DBG_BITMAP, "bitmap full\n");
90 goto out;
91 }
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;
101 }
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;
114 }
115 *curr++ = cpu_to_be32(0xffffffff);
116 len -= 32;
117 }
118 set_page_dirty(page);
119 kunmap(page);
120 offset += PAGE_CACHE_BITS;
Pekka Enberg090d2b12006-06-23 02:05:08 -0700121 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
122 NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123 pptr = kmap(page);
124 curr = pptr;
125 end = pptr + PAGE_CACHE_BITS / 32;
126 }
127last:
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;
135 }
136done:
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);
144out:
Jes Sorensen1b1dcc12006-01-09 15:59:24 -0800145 mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146 return start;
147}
148
149int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
150{
151 struct page *page;
152 struct address_space *mapping;
153 __be32 *pptr, *curr, *end;
154 u32 mask, len, pnr;
155 int i;
156
157 /* is there any actual work to be done? */
158 if (!count)
159 return 0;
160
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;
165
Jes Sorensen1b1dcc12006-01-09 15:59:24 -0800166 mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167 mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
168 pnr = offset / PAGE_CACHE_BITS;
Pekka Enberg090d2b12006-06-23 02:05:08 -0700169 page = read_mapping_page(mapping, pnr, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700170 pptr = kmap(page);
171 curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
172 end = pptr + PAGE_CACHE_BITS / 32;
173 len = count;
174
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;
184 }
185 *curr++ &= cpu_to_be32(mask);
186 count -= j;
187 }
188
189 /* do full u32s */
190 while (1) {
191 while (curr < end) {
192 if (count < 32)
193 goto done;
194 *curr++ = 0;
195 count -= 32;
196 }
197 if (!count)
198 break;
199 set_page_dirty(page);
200 kunmap(page);
Pekka Enberg090d2b12006-06-23 02:05:08 -0700201 page = read_mapping_page(mapping, ++pnr, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202 pptr = kmap(page);
203 curr = pptr;
204 end = pptr + PAGE_CACHE_BITS / 32;
205 }
206done:
207 /* do any partial u32 at end */
208 if (count) {
209 mask = 0xffffffffU >> count;
210 *curr &= cpu_to_be32(mask);
211 }
212out:
213 set_page_dirty(page);
214 kunmap(page);
215 HFSPLUS_SB(sb).free_blocks += len;
216 sb->s_dirt = 1;
Jes Sorensen1b1dcc12006-01-09 15:59:24 -0800217 mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218
219 return 0;
220}