xref: /openbmc/linux/fs/hfsplus/bitmap.c (revision e868d61272caa648214046a096e5a6bfc068dc8c)
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 	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;
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;
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;
81 	}
82 	dprint(DBG_BITMAP, "bitmap full\n");
83 	start = size;
84 	goto out;
85 
86 found:
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;
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;
126 	}
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;
135 	}
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;
147 }
148 
149 int 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 
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;
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);
201 		page = read_mapping_page(mapping, ++pnr, NULL);
202 		pptr = kmap(page);
203 		curr = pptr;
204 		end = pptr + PAGE_CACHE_BITS / 32;
205 	}
206 done:
207 	/* do any partial u32 at end */
208 	if (count) {
209 		mask = 0xffffffffU >> count;
210 		*curr &= cpu_to_be32(mask);
211 	}
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);
218 
219 	return 0;
220 }
221