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 <stdio.h>
13#include <string.h>
14#if HAVE_UNISTD_H
15#include <unistd.h>
16#endif
17#include <fcntl.h>
18#include <time.h>
19#if HAVE_SYS_STAT_H
20#include <sys/stat.h>
21#endif
22#if HAVE_SYS_TYPES_H
23#include <sys/types.h>
24#endif
25
26#include "ext2_fs.h"
27#include "ext2fsP.h"
28#include "bmap64.h"
29
30/*
31 * Private data for bit array implementation of bitmap ops.
32 * Currently, this is just a pointer to our big flat hunk of memory,
33 * exactly equivalent to the old-skool char * bitmap member.
34 */
35
36struct ext2fs_ba_private_struct {
37	char *bitarray;
38};
39
40typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
41
42static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap)
43{
44	ext2fs_ba_private bp;
45	errcode_t	retval;
46	size_t		size;
47
48	/*
49	 * Since we only have the one pointer, we could just shove our
50	 * private data in the void *private field itself, but then
51	 * we'd have to do a fair bit of rewriting if we ever added a
52	 * field.  I'm agnostic.
53	 */
54	retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
55	if (retval)
56		return retval;
57
58	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
59
60	retval = ext2fs_get_mem(size, &bp->bitarray);
61	if (retval) {
62		ext2fs_free_mem(&bp);
63		bp = 0;
64		return retval;
65	}
66	bitmap->private = (void *) bp;
67	return 0;
68}
69
70static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
71			     ext2fs_generic_bitmap bitmap)
72{
73	ext2fs_ba_private bp;
74	errcode_t	retval;
75	size_t		size;
76
77	retval = ba_alloc_private_data (bitmap);
78	if (retval)
79		return retval;
80
81	bp = (ext2fs_ba_private) bitmap->private;
82	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
83	memset(bp->bitarray, 0, size);
84
85	return 0;
86}
87
88static void ba_free_bmap(ext2fs_generic_bitmap bitmap)
89{
90	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
91
92	if (!bp)
93		return;
94
95	if (bp->bitarray) {
96		ext2fs_free_mem (&bp->bitarray);
97		bp->bitarray = 0;
98	}
99	ext2fs_free_mem (&bp);
100	bp = 0;
101}
102
103static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src,
104			      ext2fs_generic_bitmap dest)
105{
106	ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
107	ext2fs_ba_private dest_bp;
108	errcode_t retval;
109	size_t size;
110
111	retval = ba_alloc_private_data (dest);
112	if (retval)
113		return retval;
114
115	dest_bp = (ext2fs_ba_private) dest->private;
116
117	size = (size_t) (((src->real_end - src->start) / 8) + 1);
118	memcpy (dest_bp->bitarray, src_bp->bitarray, size);
119
120	return 0;
121}
122
123static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap,
124				__u64 new_end, __u64 new_real_end)
125{
126	ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
127	errcode_t	retval;
128	size_t		size, new_size;
129	__u64		bitno;
130
131	/*
132	 * If we're expanding the bitmap, make sure all of the new
133	 * parts of the bitmap are zero.
134	 */
135	if (new_end > bmap->end) {
136		bitno = bmap->real_end;
137		if (bitno > new_end)
138			bitno = new_end;
139		for (; bitno > bmap->end; bitno--)
140			ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
141	}
142	if (new_real_end == bmap->real_end) {
143		bmap->end = new_end;
144		return 0;
145	}
146
147	size = ((bmap->real_end - bmap->start) / 8) + 1;
148	new_size = ((new_real_end - bmap->start) / 8) + 1;
149
150	if (size != new_size) {
151		retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
152		if (retval)
153			return retval;
154	}
155	if (new_size > size)
156		memset(bp->bitarray + size, 0, new_size - size);
157
158	bmap->end = new_end;
159	bmap->real_end = new_real_end;
160	return 0;
161
162}
163
164static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
165{
166	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
167	blk64_t bitno = (blk64_t) arg;
168
169	return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
170}
171
172static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
173{
174	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
175	blk64_t bitno = (blk64_t) arg;
176
177	return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
178}
179
180static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
181{
182	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
183	blk64_t bitno = (blk64_t) arg;
184
185	return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
186}
187
188static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
189				unsigned int num)
190{
191	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
192	blk64_t bitno = (blk64_t) arg;
193	unsigned int i;
194
195	for (i = 0; i < num; i++)
196		ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
197}
198
199static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
200				  unsigned int num)
201{
202	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
203	blk64_t bitno = (blk64_t) arg;
204	unsigned int i;
205
206	for (i = 0; i < num; i++)
207		ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
208}
209
210static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
211				     __u64 start, unsigned int len)
212{
213	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
214	__u64 start_byte, len_byte = len >> 3;
215	unsigned int start_bit, len_bit = len % 8;
216	unsigned int first_bit = 0;
217	unsigned int last_bit  = 0;
218	int mark_count = 0;
219	int mark_bit = 0;
220	int i;
221	const char *ADDR;
222
223	ADDR = bp->bitarray;
224	start -= bitmap->start;
225	start_byte = start >> 3;
226	start_bit = start % 8;
227
228	if (start_bit != 0) {
229		/*
230		 * The compared start block number or start inode number
231		 * is not the first bit in a byte.
232		 */
233		mark_count = 8 - start_bit;
234		if (len < 8 - start_bit) {
235			mark_count = (int)len;
236			mark_bit = len + start_bit - 1;
237		} else
238			mark_bit = 7;
239
240		for (i = mark_count; i > 0; i--, mark_bit--)
241			first_bit |= 1 << mark_bit;
242
243		/*
244		 * Compare blocks or inodes in the first byte.
245		 * If there is any marked bit, this function returns 0.
246		 */
247		if (first_bit & ADDR[start_byte])
248			return 0;
249		else if (len <= 8 - start_bit)
250			return 1;
251
252		start_byte++;
253		len_bit = (len - mark_count) % 8;
254		len_byte = (len - mark_count) >> 3;
255	}
256
257	/*
258	 * The compared start block number or start inode number is
259	 * the first bit in a byte.
260	 */
261	if (len_bit != 0) {
262		/*
263		 * The compared end block number or end inode number is
264		 * not the last bit in a byte.
265		 */
266		for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
267			last_bit |= 1 << mark_bit;
268
269		/*
270		 * Compare blocks or inodes in the last byte.
271		 * If there is any marked bit, this function returns 0.
272		 */
273		if (last_bit & ADDR[start_byte + len_byte])
274			return 0;
275		else if (len_byte == 0)
276			return 1;
277	}
278
279	/* Check whether all bytes are 0 */
280	return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
281}
282
283
284static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap,
285				     __u64 start, size_t num, void *in)
286{
287	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
288
289	memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
290
291	return 0;
292}
293
294static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap,
295				     __u64 start, size_t num, void *out)
296{
297	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
298
299	memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
300
301	return 0;
302}
303
304static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
305{
306	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
307
308	memset(bp->bitarray, 0,
309	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
310}
311
312static void ba_print_stats(ext2fs_generic_bitmap bitmap)
313{
314	fprintf(stderr, "%16llu Bytes used by bitarray\n",
315		((bitmap->real_end - bitmap->start) >> 3) + 1 +
316		sizeof(struct ext2fs_ba_private_struct));
317}
318
319/* Find the first zero bit between start and end, inclusive. */
320static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
321				    __u64 start, __u64 end, __u64 *out)
322{
323	ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
324	unsigned long bitpos = start - bitmap->start;
325	unsigned long count = end - start + 1;
326	int byte_found = 0; /* whether a != 0xff byte has been found */
327	const unsigned char *pos;
328	unsigned long max_loop_count, i;
329
330	if (start < bitmap->start || end > bitmap->end || start > end)
331		return EINVAL;
332
333	if (bitmap->cluster_bits)
334		return EINVAL;
335
336	/* scan bits until we hit a byte boundary */
337	while ((bitpos & 0x7) != 0 && count > 0) {
338		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
339			*out = bitpos + bitmap->start;
340			return 0;
341		}
342		bitpos++;
343		count--;
344	}
345
346	if (!count)
347		return ENOENT;
348
349	pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
350	/* scan bytes until 8-byte (64-bit) aligned */
351	while (count >= 8 && (((unsigned long)pos) & 0x07)) {
352		if (*pos != 0xff) {
353			byte_found = 1;
354			break;
355		}
356		pos++;
357		count -= 8;
358		bitpos += 8;
359	}
360
361	if (!byte_found) {
362		max_loop_count = count >> 6; /* 8-byte blocks */
363		i = max_loop_count;
364		while (i) {
365			if (*((const __u64 *)pos) != ((__u64)-1))
366				break;
367			pos += 8;
368			i--;
369		}
370		count -= 64 * (max_loop_count - i);
371		bitpos += 64 * (max_loop_count - i);
372
373		max_loop_count = count >> 3;
374		i = max_loop_count;
375		while (i) {
376			if (*pos != 0xff) {
377				byte_found = 1;
378				break;
379			}
380			pos++;
381			i--;
382		}
383		count -= 8 * (max_loop_count - i);
384		bitpos += 8 * (max_loop_count - i);
385	}
386
387	/* Here either count < 8 or byte_found == 1. */
388	while (count-- > 0) {
389		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
390			*out = bitpos + bitmap->start;
391			return 0;
392		}
393		bitpos++;
394	}
395
396	return ENOENT;
397}
398
399struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
400	.type = EXT2FS_BMAP64_BITARRAY,
401	.new_bmap = ba_new_bmap,
402	.free_bmap = ba_free_bmap,
403	.copy_bmap = ba_copy_bmap,
404	.resize_bmap = ba_resize_bmap,
405	.mark_bmap = ba_mark_bmap,
406	.unmark_bmap = ba_unmark_bmap,
407	.test_bmap = ba_test_bmap,
408	.test_clear_bmap_extent = ba_test_clear_bmap_extent,
409	.mark_bmap_extent = ba_mark_bmap_extent,
410	.unmark_bmap_extent = ba_unmark_bmap_extent,
411	.set_bmap_range = ba_set_bmap_range,
412	.get_bmap_range = ba_get_bmap_range,
413	.clear_bmap = ba_clear_bmap,
414	.print_stats = ba_print_stats,
415	.find_first_zero = ba_find_first_zero
416};
417