Merge branch 'master'
[linux-2.6] / fs / hfsplus / bitmap.c
1 /*
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
18 int 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
87 found:
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         }
128 last:
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         }
137 done:
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);
145 out:
146         up(&HFSPLUS_SB(sb).alloc_file->i_sem);
147         return start;
148 }
149
150 int 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         }
207 done:
208         /* do any partial u32 at end */
209         if (count) {
210                 mask = 0xffffffffU >> count;
211                 *curr &= cpu_to_be32(mask);
212         }
213 out:
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 }