blkmap64_ba.c revision 9288e3be665bb8d5657d7f710687a50fad859acf 
1/*
2 * blkmap64_ba.c --- Simple bitarray implementation for bitmaps
3 *
4 * Copyright (C) 2008 Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 */
11
12#include "config.h"
13#include <stdio.h>
14#include <string.h>
15#if HAVE_UNISTD_H
16#include <unistd.h>
17#endif
18#include <fcntl.h>
19#include <time.h>
20#if HAVE_SYS_STAT_H
21#include <sys/stat.h>
22#endif
23#if HAVE_SYS_TYPES_H
24#include <sys/types.h>
25#endif
26
27#include "ext2_fs.h"
28#include "ext2fsP.h"
29#include "bmap64.h"
30
31/*
32 * Private data for bit array implementation of bitmap ops.
33 * Currently, this is just a pointer to our big flat hunk of memory,
34 * exactly equivalent to the old-skool char * bitmap member.
35 */
36
37struct ext2fs_ba_private_struct {
38	char *bitarray;
39};
40
41typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
42
43static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap)
44{
45	ext2fs_ba_private bp;
46	errcode_t	retval;
47	size_t		size;
48
49	/*
50	 * Since we only have the one pointer, we could just shove our
51	 * private data in the void *private field itself, but then
52	 * we'd have to do a fair bit of rewriting if we ever added a
53	 * field.  I'm agnostic.
54	 */
55	retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
56	if (retval)
57		return retval;
58
59	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
60
61	retval = ext2fs_get_mem(size, &bp->bitarray);
62	if (retval) {
63		ext2fs_free_mem(&bp);
64		bp = 0;
65		return retval;
66	}
67	bitmap->private = (void *) bp;
68	return 0;
69}
70
71static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
72			     ext2fs_generic_bitmap bitmap)
73{
74	ext2fs_ba_private bp;
75	errcode_t	retval;
76	size_t		size;
77
78	retval = ba_alloc_private_data (bitmap);
79	if (retval)
80		return retval;
81
82	bp = (ext2fs_ba_private) bitmap->private;
83	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
84	memset(bp->bitarray, 0, size);
85
86	return 0;
87}
88
89static void ba_free_bmap(ext2fs_generic_bitmap bitmap)
90{
91	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
92
93	if (!bp)
94		return;
95
96	if (bp->bitarray) {
97		ext2fs_free_mem (&bp->bitarray);
98		bp->bitarray = 0;
99	}
100	ext2fs_free_mem (&bp);
101	bp = 0;
102}
103
104static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src,
105			      ext2fs_generic_bitmap dest)
106{
107	ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
108	ext2fs_ba_private dest_bp;
109	errcode_t retval;
110	size_t size;
111
112	retval = ba_alloc_private_data (dest);
113	if (retval)
114		return retval;
115
116	dest_bp = (ext2fs_ba_private) dest->private;
117
118	size = (size_t) (((src->real_end - src->start) / 8) + 1);
119	memcpy (dest_bp->bitarray, src_bp->bitarray, size);
120
121	return 0;
122}
123
124static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap,
125				__u64 new_end, __u64 new_real_end)
126{
127	ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
128	errcode_t	retval;
129	size_t		size, new_size;
130	__u64		bitno;
131
132	/*
133	 * If we're expanding the bitmap, make sure all of the new
134	 * parts of the bitmap are zero.
135	 */
136	if (new_end > bmap->end) {
137		bitno = bmap->real_end;
138		if (bitno > new_end)
139			bitno = new_end;
140		for (; bitno > bmap->end; bitno--)
141			ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
142	}
143	if (new_real_end == bmap->real_end) {
144		bmap->end = new_end;
145		return 0;
146	}
147
148	size = ((bmap->real_end - bmap->start) / 8) + 1;
149	new_size = ((new_real_end - bmap->start) / 8) + 1;
150
151	if (size != new_size) {
152		retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
153		if (retval)
154			return retval;
155	}
156	if (new_size > size)
157		memset(bp->bitarray + size, 0, new_size - size);
158
159	bmap->end = new_end;
160	bmap->real_end = new_real_end;
161	return 0;
162
163}
164
165static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
166{
167	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
168	blk64_t bitno = (blk64_t) arg;
169
170	return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
171}
172
173static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
174{
175	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
176	blk64_t bitno = (blk64_t) arg;
177
178	return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
179}
180
181static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
182{
183	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
184	blk64_t bitno = (blk64_t) arg;
185
186	return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
187}
188
189static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
190				unsigned int num)
191{
192	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
193	blk64_t bitno = (blk64_t) arg;
194	unsigned int i;
195
196	for (i = 0; i < num; i++)
197		ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
198}
199
200static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
201				  unsigned int num)
202{
203	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
204	blk64_t bitno = (blk64_t) arg;
205	unsigned int i;
206
207	for (i = 0; i < num; i++)
208		ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
209}
210
211static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
212				     __u64 start, unsigned int len)
213{
214	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
215	__u64 start_byte, len_byte = len >> 3;
216	unsigned int start_bit, len_bit = len % 8;
217	unsigned int first_bit = 0;
218	unsigned int last_bit  = 0;
219	int mark_count = 0;
220	int mark_bit = 0;
221	int i;
222	const char *ADDR;
223
224	ADDR = bp->bitarray;
225	start -= bitmap->start;
226	start_byte = start >> 3;
227	start_bit = start % 8;
228
229	if (start_bit != 0) {
230		/*
231		 * The compared start block number or start inode number
232		 * is not the first bit in a byte.
233		 */
234		mark_count = 8 - start_bit;
235		if (len < 8 - start_bit) {
236			mark_count = (int)len;
237			mark_bit = len + start_bit - 1;
238		} else
239			mark_bit = 7;
240
241		for (i = mark_count; i > 0; i--, mark_bit--)
242			first_bit |= 1 << mark_bit;
243
244		/*
245		 * Compare blocks or inodes in the first byte.
246		 * If there is any marked bit, this function returns 0.
247		 */
248		if (first_bit & ADDR[start_byte])
249			return 0;
250		else if (len <= 8 - start_bit)
251			return 1;
252
253		start_byte++;
254		len_bit = (len - mark_count) % 8;
255		len_byte = (len - mark_count) >> 3;
256	}
257
258	/*
259	 * The compared start block number or start inode number is
260	 * the first bit in a byte.
261	 */
262	if (len_bit != 0) {
263		/*
264		 * The compared end block number or end inode number is
265		 * not the last bit in a byte.
266		 */
267		for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
268			last_bit |= 1 << mark_bit;
269
270		/*
271		 * Compare blocks or inodes in the last byte.
272		 * If there is any marked bit, this function returns 0.
273		 */
274		if (last_bit & ADDR[start_byte + len_byte])
275			return 0;
276		else if (len_byte == 0)
277			return 1;
278	}
279
280	/* Check whether all bytes are 0 */
281	return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
282}
283
284
285static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap,
286				     __u64 start, size_t num, void *in)
287{
288	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
289
290	memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
291
292	return 0;
293}
294
295static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap,
296				     __u64 start, size_t num, void *out)
297{
298	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
299
300	memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
301
302	return 0;
303}
304
305static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
306{
307	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
308
309	memset(bp->bitarray, 0,
310	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
311}
312
313static void ba_print_stats(ext2fs_generic_bitmap bitmap)
314{
315	fprintf(stderr, "%16llu Bytes used by bitarray\n",
316		((bitmap->real_end - bitmap->start) >> 3) + 1 +
317		sizeof(struct ext2fs_ba_private_struct));
318}
319
320struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
321	.type = EXT2FS_BMAP64_BITARRAY,
322	.new_bmap = ba_new_bmap,
323	.free_bmap = ba_free_bmap,
324	.copy_bmap = ba_copy_bmap,
325	.resize_bmap = ba_resize_bmap,
326	.mark_bmap = ba_mark_bmap,
327	.unmark_bmap = ba_unmark_bmap,
328	.test_bmap = ba_test_bmap,
329	.test_clear_bmap_extent = ba_test_clear_bmap_extent,
330	.mark_bmap_extent = ba_mark_bmap_extent,
331	.unmark_bmap_extent = ba_unmark_bmap_extent,
332	.set_bmap_range = ba_set_bmap_range,
333	.get_bmap_range = ba_get_bmap_range,
334	.clear_bmap = ba_clear_bmap,
335	.print_stats = ba_print_stats,
336};
337