GNU Linux-libre 4.9.308-gnu1
[releases.git] / 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_SIZE * 8)
17
18 int hfsplus_block_allocate(struct super_block *sb, u32 size,
19                 u32 offset, u32 *max)
20 {
21         struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
22         struct page *page;
23         struct address_space *mapping;
24         __be32 *pptr, *curr, *end;
25         u32 mask, start, len, n;
26         __be32 val;
27         int i;
28
29         len = *max;
30         if (!len)
31                 return size;
32
33         hfs_dbg(BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
34         mutex_lock(&sbi->alloc_mutex);
35         mapping = sbi->alloc_file->i_mapping;
36         page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
37         if (IS_ERR(page)) {
38                 start = size;
39                 goto out;
40         }
41         pptr = kmap(page);
42         curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
43         i = offset % 32;
44         offset &= ~(PAGE_CACHE_BITS - 1);
45         if ((size ^ offset) / PAGE_CACHE_BITS)
46                 end = pptr + PAGE_CACHE_BITS / 32;
47         else
48                 end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
49
50         /* scan the first partial u32 for zero bits */
51         val = *curr;
52         if (~val) {
53                 n = be32_to_cpu(val);
54                 mask = (1U << 31) >> i;
55                 for (; i < 32; mask >>= 1, i++) {
56                         if (!(n & mask))
57                                 goto found;
58                 }
59         }
60         curr++;
61
62         /* scan complete u32s for the first zero bit */
63         while (1) {
64                 while (curr < end) {
65                         val = *curr;
66                         if (~val) {
67                                 n = be32_to_cpu(val);
68                                 mask = 1 << 31;
69                                 for (i = 0; i < 32; mask >>= 1, i++) {
70                                         if (!(n & mask))
71                                                 goto found;
72                                 }
73                         }
74                         curr++;
75                 }
76                 kunmap(page);
77                 offset += PAGE_CACHE_BITS;
78                 if (offset >= size)
79                         break;
80                 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
81                                          NULL);
82                 if (IS_ERR(page)) {
83                         start = size;
84                         goto out;
85                 }
86                 curr = pptr = kmap(page);
87                 if ((size ^ offset) / PAGE_CACHE_BITS)
88                         end = pptr + PAGE_CACHE_BITS / 32;
89                 else
90                         end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
91         }
92         hfs_dbg(BITMAP, "bitmap full\n");
93         start = size;
94         goto out;
95
96 found:
97         start = offset + (curr - pptr) * 32 + i;
98         if (start >= size) {
99                 hfs_dbg(BITMAP, "bitmap full\n");
100                 goto out;
101         }
102         /* do any partial u32 at the start */
103         len = min(size - start, len);
104         while (1) {
105                 n |= mask;
106                 if (++i >= 32)
107                         break;
108                 mask >>= 1;
109                 if (!--len || n & mask)
110                         goto done;
111         }
112         if (!--len)
113                 goto done;
114         *curr++ = cpu_to_be32(n);
115         /* do full u32s */
116         while (1) {
117                 while (curr < end) {
118                         n = be32_to_cpu(*curr);
119                         if (len < 32)
120                                 goto last;
121                         if (n) {
122                                 len = 32;
123                                 goto last;
124                         }
125                         *curr++ = cpu_to_be32(0xffffffff);
126                         len -= 32;
127                 }
128                 set_page_dirty(page);
129                 kunmap(page);
130                 offset += PAGE_CACHE_BITS;
131                 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
132                                          NULL);
133                 if (IS_ERR(page)) {
134                         start = size;
135                         goto out;
136                 }
137                 pptr = kmap(page);
138                 curr = pptr;
139                 end = pptr + PAGE_CACHE_BITS / 32;
140         }
141 last:
142         /* do any partial u32 at end */
143         mask = 1U << 31;
144         for (i = 0; i < len; i++) {
145                 if (n & mask)
146                         break;
147                 n |= mask;
148                 mask >>= 1;
149         }
150 done:
151         *curr = cpu_to_be32(n);
152         set_page_dirty(page);
153         kunmap(page);
154         *max = offset + (curr - pptr) * 32 + i - start;
155         sbi->free_blocks -= *max;
156         hfsplus_mark_mdb_dirty(sb);
157         hfs_dbg(BITMAP, "-> %u,%u\n", start, *max);
158 out:
159         mutex_unlock(&sbi->alloc_mutex);
160         return start;
161 }
162
163 int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
164 {
165         struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
166         struct page *page;
167         struct address_space *mapping;
168         __be32 *pptr, *curr, *end;
169         u32 mask, len, pnr;
170         int i;
171
172         /* is there any actual work to be done? */
173         if (!count)
174                 return 0;
175
176         hfs_dbg(BITMAP, "block_free: %u,%u\n", offset, count);
177         /* are all of the bits in range? */
178         if ((offset + count) > sbi->total_blocks)
179                 return -ENOENT;
180
181         mutex_lock(&sbi->alloc_mutex);
182         mapping = sbi->alloc_file->i_mapping;
183         pnr = offset / PAGE_CACHE_BITS;
184         page = read_mapping_page(mapping, pnr, NULL);
185         if (IS_ERR(page))
186                 goto kaboom;
187         pptr = kmap(page);
188         curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
189         end = pptr + PAGE_CACHE_BITS / 32;
190         len = count;
191
192         /* do any partial u32 at the start */
193         i = offset % 32;
194         if (i) {
195                 int j = 32 - i;
196                 mask = 0xffffffffU << j;
197                 if (j > count) {
198                         mask |= 0xffffffffU >> (i + count);
199                         *curr++ &= cpu_to_be32(mask);
200                         goto out;
201                 }
202                 *curr++ &= cpu_to_be32(mask);
203                 count -= j;
204         }
205
206         /* do full u32s */
207         while (1) {
208                 while (curr < end) {
209                         if (count < 32)
210                                 goto done;
211                         *curr++ = 0;
212                         count -= 32;
213                 }
214                 if (!count)
215                         break;
216                 set_page_dirty(page);
217                 kunmap(page);
218                 page = read_mapping_page(mapping, ++pnr, NULL);
219                 if (IS_ERR(page))
220                         goto kaboom;
221                 pptr = kmap(page);
222                 curr = pptr;
223                 end = pptr + PAGE_CACHE_BITS / 32;
224         }
225 done:
226         /* do any partial u32 at end */
227         if (count) {
228                 mask = 0xffffffffU >> count;
229                 *curr &= cpu_to_be32(mask);
230         }
231 out:
232         set_page_dirty(page);
233         kunmap(page);
234         sbi->free_blocks += len;
235         hfsplus_mark_mdb_dirty(sb);
236         mutex_unlock(&sbi->alloc_mutex);
237
238         return 0;
239
240 kaboom:
241         pr_crit("unable to mark blocks free: error %ld\n", PTR_ERR(page));
242         mutex_unlock(&sbi->alloc_mutex);
243
244         return -EIO;
245 }