• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * gen_bitmap.c --- Generic (32-bit) bitmap routines
3  *
4  * Copyright (C) 2001 Theodore Ts'o.
5  *
6  * %Begin-Header%
7  * This file may be redistributed under the terms of the GNU Library
8  * General Public License, version 2.
9  * %End-Header%
10  */
11 
12 
13 #include "config.h"
14 #include <stdio.h>
15 #include <string.h>
16 #if HAVE_UNISTD_H
17 #include <unistd.h>
18 #endif
19 #include <fcntl.h>
20 #include <time.h>
21 #if HAVE_SYS_STAT_H
22 #include <sys/stat.h>
23 #endif
24 #if HAVE_SYS_TYPES_H
25 #include <sys/types.h>
26 #endif
27 
28 #include "ext2_fs.h"
29 #include "ext2fsP.h"
30 
31 struct ext2fs_struct_generic_bitmap_32 {
32 	errcode_t	magic;
33 	ext2_filsys 	fs;
34 	__u32		start, end;
35 	__u32		real_end;
36 	char	*	description;
37 	char	*	bitmap;
38 	errcode_t	base_error_code;
39 	__u32		reserved[7];
40 };
41 
42 typedef struct ext2fs_struct_generic_bitmap_32 *ext2fs_generic_bitmap_32;
43 
44 #define EXT2FS_IS_32_BITMAP(bmap) \
45 	(((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || \
46 	 ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP) || \
47 	 ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP))
48 
49 #define EXT2FS_IS_64_BITMAP(bmap) \
50 	(((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP64) || \
51 	 ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP64) || \
52 	 ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP64))
53 
54 /*
55  * Used by previously inlined function, so we have to export this and
56  * not change the function signature
57  */
ext2fs_warn_bitmap2(ext2fs_generic_bitmap gen_bitmap,int code,unsigned long arg)58 void ext2fs_warn_bitmap2(ext2fs_generic_bitmap gen_bitmap,
59 			    int code, unsigned long arg)
60 {
61 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
62 
63 #ifndef OMIT_COM_ERR
64 	if (bitmap->description)
65 		com_err(0, bitmap->base_error_code+code,
66 			"#%lu for %s", arg, bitmap->description);
67 	else
68 		com_err(0, bitmap->base_error_code + code, "#%lu", arg);
69 #endif
70 }
71 
check_magic(ext2fs_generic_bitmap bitmap)72 static errcode_t check_magic(ext2fs_generic_bitmap bitmap)
73 {
74 	if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) ||
75 			 (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) ||
76 			 (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP)))
77 		return EXT2_ET_MAGIC_GENERIC_BITMAP;
78 	return 0;
79 }
80 
ext2fs_make_generic_bitmap(errcode_t magic,ext2_filsys fs,__u32 start,__u32 end,__u32 real_end,const char * descr,char * init_map,ext2fs_generic_bitmap * ret)81 errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs,
82 				     __u32 start, __u32 end, __u32 real_end,
83 				     const char *descr, char *init_map,
84 				     ext2fs_generic_bitmap *ret)
85 {
86 	ext2fs_generic_bitmap_32 bitmap;
87 	errcode_t		retval;
88 	size_t			size;
89 
90 	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap_32),
91 				&bitmap);
92 	if (retval)
93 		return retval;
94 
95 	bitmap->magic = magic;
96 	bitmap->fs = fs;
97 	bitmap->start = start;
98 	bitmap->end = end;
99 	bitmap->real_end = real_end;
100 	switch (magic) {
101 	case EXT2_ET_MAGIC_INODE_BITMAP:
102 		bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
103 		break;
104 	case EXT2_ET_MAGIC_BLOCK_BITMAP:
105 		bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
106 		break;
107 	default:
108 		bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
109 	}
110 	if (descr) {
111 		retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
112 		if (retval) {
113 			ext2fs_free_mem(&bitmap);
114 			return retval;
115 		}
116 		strcpy(bitmap->description, descr);
117 	} else
118 		bitmap->description = 0;
119 
120 	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
121 	/* Round up to allow for the BT x86 instruction */
122 	size = (size + 7) & ~3;
123 	retval = ext2fs_get_mem(size, &bitmap->bitmap);
124 	if (retval) {
125 		ext2fs_free_mem(&bitmap->description);
126 		ext2fs_free_mem(&bitmap);
127 		return retval;
128 	}
129 
130 	if (init_map)
131 		memcpy(bitmap->bitmap, init_map, size);
132 	else
133 		memset(bitmap->bitmap, 0, size);
134 	*ret = (ext2fs_generic_bitmap) bitmap;
135 	return 0;
136 }
137 
ext2fs_allocate_generic_bitmap(__u32 start,__u32 end,__u32 real_end,const char * descr,ext2fs_generic_bitmap * ret)138 errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
139 					 __u32 end,
140 					 __u32 real_end,
141 					 const char *descr,
142 					 ext2fs_generic_bitmap *ret)
143 {
144 	return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
145 					  start, end, real_end, descr, 0, ret);
146 }
147 
ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap gen_src,ext2fs_generic_bitmap * dest)148 errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap gen_src,
149 				     ext2fs_generic_bitmap *dest)
150 {
151 	ext2fs_generic_bitmap_32 src = (ext2fs_generic_bitmap_32) gen_src;
152 
153 	return (ext2fs_make_generic_bitmap(src->magic, src->fs,
154 					   src->start, src->end,
155 					   src->real_end,
156 					   src->description, src->bitmap,
157 					   dest));
158 }
159 
ext2fs_free_generic_bitmap(ext2fs_inode_bitmap gen_bitmap)160 void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap gen_bitmap)
161 {
162 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
163 
164 	if (check_magic(gen_bitmap))
165 		return;
166 
167 	bitmap->magic = 0;
168 	if (bitmap->description) {
169 		ext2fs_free_mem(&bitmap->description);
170 		bitmap->description = 0;
171 	}
172 	if (bitmap->bitmap) {
173 		ext2fs_free_mem(&bitmap->bitmap);
174 		bitmap->bitmap = 0;
175 	}
176 	ext2fs_free_mem(&bitmap);
177 }
178 
ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,blk_t bitno)179 int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
180 					blk_t bitno)
181 {
182 	ext2fs_generic_bitmap_32 bitmap32 = (ext2fs_generic_bitmap_32) bitmap;
183 
184 	if (!EXT2FS_IS_32_BITMAP(bitmap)) {
185 		if (EXT2FS_IS_64_BITMAP(bitmap)) {
186 			ext2fs_warn_bitmap32(bitmap, __func__);
187 			return ext2fs_test_generic_bmap(bitmap, bitno);
188 		}
189 #ifndef OMIT_COM_ERR
190 		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
191 			"test_bitmap(%lu)", (unsigned long) bitno);
192 #endif
193 		return 0;
194 	}
195 
196 	if ((bitno < bitmap32->start) || (bitno > bitmap32->end)) {
197 		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
198 		return 0;
199 	}
200 	return ext2fs_test_bit(bitno - bitmap32->start, bitmap32->bitmap);
201 }
202 
ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,__u32 bitno)203 int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
204 					 __u32 bitno)
205 {
206 	ext2fs_generic_bitmap_32 bitmap32 = (ext2fs_generic_bitmap_32) bitmap;
207 
208 	if (!EXT2FS_IS_32_BITMAP(bitmap)) {
209 		if (EXT2FS_IS_64_BITMAP(bitmap)) {
210 			ext2fs_warn_bitmap32(bitmap, __func__);
211 			return ext2fs_mark_generic_bmap(bitmap, bitno);
212 		}
213 #ifndef OMIT_COM_ERR
214 		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
215 			"mark_bitmap(%lu)", (unsigned long) bitno);
216 #endif
217 		return 0;
218 	}
219 
220 	if ((bitno < bitmap32->start) || (bitno > bitmap32->end)) {
221 		ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
222 		return 0;
223 	}
224 	return ext2fs_set_bit(bitno - bitmap32->start, bitmap32->bitmap);
225 }
226 
ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,blk_t bitno)227 int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
228 					   blk_t bitno)
229 {
230 	ext2fs_generic_bitmap_32 bitmap32 = (ext2fs_generic_bitmap_32) bitmap;
231 
232 	if (!EXT2FS_IS_32_BITMAP(bitmap)) {
233 		if (EXT2FS_IS_64_BITMAP(bitmap)) {
234 			ext2fs_warn_bitmap32(bitmap, __func__);
235 			return ext2fs_unmark_generic_bmap(bitmap, bitno);
236 		}
237 #ifndef OMIT_COM_ERR
238 		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
239 			"mark_bitmap(%lu)", (unsigned long) bitno);
240 #endif
241 		return 0;
242 	}
243 
244 	if ((bitno < bitmap32->start) || (bitno > bitmap32->end)) {
245 		ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
246 		return 0;
247 	}
248 	return ext2fs_clear_bit(bitno - bitmap32->start, bitmap32->bitmap);
249 }
250 
ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)251 __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
252 {
253 	ext2fs_generic_bitmap_32 bitmap32 = (ext2fs_generic_bitmap_32) bitmap;
254 
255 	if (!EXT2FS_IS_32_BITMAP(bitmap)) {
256 		if (EXT2FS_IS_64_BITMAP(bitmap)) {
257 			ext2fs_warn_bitmap32(bitmap, __func__);
258 			return ext2fs_get_generic_bmap_start(bitmap);
259 		}
260 #ifndef OMIT_COM_ERR
261 		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
262 			"get_bitmap_start");
263 #endif
264 		return 0;
265 	}
266 
267 	return bitmap32->start;
268 }
269 
ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)270 __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
271 {
272 	ext2fs_generic_bitmap_32 bitmap32 = (ext2fs_generic_bitmap_32) bitmap;
273 
274 	if (!EXT2FS_IS_32_BITMAP(bitmap)) {
275 		if (EXT2FS_IS_64_BITMAP(bitmap)) {
276 			ext2fs_warn_bitmap32(bitmap, __func__);
277 			return ext2fs_get_generic_bmap_end(bitmap);
278 		}
279 #ifndef OMIT_COM_ERR
280 		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
281 			"get_bitmap_end");
282 #endif
283 		return 0;
284 	}
285 	return bitmap32->end;
286 }
287 
ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)288 void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
289 {
290 	ext2fs_generic_bitmap_32 bitmap32 = (ext2fs_generic_bitmap_32) bitmap;
291 
292 	if (!EXT2FS_IS_32_BITMAP(bitmap)) {
293 		if (EXT2FS_IS_64_BITMAP(bitmap)) {
294 			ext2fs_warn_bitmap32(bitmap, __func__);
295 			ext2fs_clear_generic_bmap(bitmap);
296 			return;
297 		}
298 #ifndef OMIT_COM_ERR
299 		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
300 			"clear_generic_bitmap");
301 #endif
302 		return;
303 	}
304 
305 	memset(bitmap32->bitmap, 0,
306 	       (size_t) (((bitmap32->real_end - bitmap32->start) / 8) + 1));
307 }
308 
ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap gen_bitmap,errcode_t magic,errcode_t neq,ext2_ino_t end,ext2_ino_t * oend)309 errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap gen_bitmap,
310 					  errcode_t magic, errcode_t neq,
311 					  ext2_ino_t end, ext2_ino_t *oend)
312 {
313 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
314 
315 	EXT2_CHECK_MAGIC(bitmap, magic);
316 
317 	if (end > bitmap->real_end)
318 		return neq;
319 	if (oend)
320 		*oend = bitmap->end;
321 	bitmap->end = end;
322 	return 0;
323 }
324 
ext2fs_resize_generic_bitmap(errcode_t magic,__u32 new_end,__u32 new_real_end,ext2fs_generic_bitmap gen_bmap)325 errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
326 				       __u32 new_end, __u32 new_real_end,
327 				       ext2fs_generic_bitmap gen_bmap)
328 {
329 	ext2fs_generic_bitmap_32 bmap = (ext2fs_generic_bitmap_32) gen_bmap;
330 	errcode_t	retval;
331 	size_t		size, new_size;
332 	__u32		bitno;
333 
334 	if (!bmap || (bmap->magic != magic))
335 		return magic;
336 
337 	/*
338 	 * If we're expanding the bitmap, make sure all of the new
339 	 * parts of the bitmap are zero.
340 	 */
341 	if (new_end > bmap->end) {
342 		bitno = bmap->real_end;
343 		if (bitno > new_end)
344 			bitno = new_end;
345 		for (; bitno > bmap->end; bitno--)
346 			ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
347 	}
348 	if (new_real_end == bmap->real_end) {
349 		bmap->end = new_end;
350 		return 0;
351 	}
352 
353 	size = ((bmap->real_end - bmap->start) / 8) + 1;
354 	new_size = ((new_real_end - bmap->start) / 8) + 1;
355 
356 	if (size != new_size) {
357 		retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
358 		if (retval)
359 			return retval;
360 	}
361 	if (new_size > size)
362 		memset(bmap->bitmap + size, 0, new_size - size);
363 
364 	bmap->end = new_end;
365 	bmap->real_end = new_real_end;
366 	return 0;
367 }
368 
ext2fs_compare_generic_bitmap(errcode_t magic,errcode_t neq,ext2fs_generic_bitmap gen_bm1,ext2fs_generic_bitmap gen_bm2)369 errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
370 					ext2fs_generic_bitmap gen_bm1,
371 					ext2fs_generic_bitmap gen_bm2)
372 {
373 	ext2fs_generic_bitmap_32 bm1 = (ext2fs_generic_bitmap_32) gen_bm1;
374 	ext2fs_generic_bitmap_32 bm2 = (ext2fs_generic_bitmap_32) gen_bm2;
375 	blk_t	i;
376 
377 	if (!bm1 || bm1->magic != magic)
378 		return magic;
379 	if (!bm2 || bm2->magic != magic)
380 		return magic;
381 
382 	if ((bm1->start != bm2->start) ||
383 	    (bm1->end != bm2->end) ||
384 	    (memcmp(bm1->bitmap, bm2->bitmap,
385 		    (size_t) (bm1->end - bm1->start)/8)))
386 		return neq;
387 
388 	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
389 		if (ext2fs_fast_test_block_bitmap(gen_bm1, i) !=
390 		    ext2fs_fast_test_block_bitmap(gen_bm2, i))
391 			return neq;
392 
393 	return 0;
394 }
395 
ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap gen_map)396 void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap gen_map)
397 {
398 	ext2fs_generic_bitmap_32 map = (ext2fs_generic_bitmap_32) gen_map;
399 	__u32	i, j;
400 
401 	/* Protect loop from wrap-around if map->real_end is maxed */
402 	for (i=map->end+1, j = i - map->start;
403 	     i <= map->real_end && i > map->end;
404 	     i++, j++)
405 		ext2fs_set_bit(j, map->bitmap);
406 }
407 
ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap gen_bmap,errcode_t magic,__u32 start,__u32 num,void * out)408 errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap gen_bmap,
409 					  errcode_t magic,
410 					  __u32 start, __u32 num,
411 					  void *out)
412 {
413 	ext2fs_generic_bitmap_32 bmap = (ext2fs_generic_bitmap_32) gen_bmap;
414 
415 	if (!bmap || (bmap->magic != magic))
416 		return magic;
417 
418 	if ((start < bmap->start) || (start+num-1 > bmap->real_end))
419 		return EXT2_ET_INVALID_ARGUMENT;
420 
421 	memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3);
422 	return 0;
423 }
424 
ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap gen_bmap,errcode_t magic,__u32 start,__u32 num,void * in)425 errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap gen_bmap,
426 					  errcode_t magic,
427 					  __u32 start, __u32 num,
428 					  void *in)
429 {
430 	ext2fs_generic_bitmap_32 bmap = (ext2fs_generic_bitmap_32) gen_bmap;
431 
432 	if (!bmap || (bmap->magic != magic))
433 		return magic;
434 
435 	if ((start < bmap->start) || (start+num-1 > bmap->real_end))
436 		return EXT2_ET_INVALID_ARGUMENT;
437 
438 	memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3);
439 	return 0;
440 }
441 
442 /*
443  * Compare @mem to zero buffer by 256 bytes.
444  * Return 1 if @mem is zeroed memory, otherwise return 0.
445  */
ext2fs_mem_is_zero(const char * mem,size_t len)446 int ext2fs_mem_is_zero(const char *mem, size_t len)
447 {
448 	static const char zero_buf[256];
449 
450 	while (len >= sizeof(zero_buf)) {
451 		if (memcmp(mem, zero_buf, sizeof(zero_buf)))
452 			return 0;
453 		len -= sizeof(zero_buf);
454 		mem += sizeof(zero_buf);
455 	}
456 	/* Deal with leftover bytes. */
457 	if (len)
458 		return !memcmp(mem, zero_buf, len);
459 	return 1;
460 }
461 
462 /*
463  * Return true if all of the bits in a specified range are clear
464  */
ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap gen_bitmap,unsigned int start,unsigned int len)465 static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap gen_bitmap,
466 						  unsigned int start,
467 						  unsigned int len)
468 {
469 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
470 	size_t start_byte, len_byte = len >> 3;
471 	unsigned int start_bit, len_bit = len % 8;
472 	int first_bit = 0;
473 	int last_bit  = 0;
474 	int mark_count = 0;
475 	int mark_bit = 0;
476 	int i;
477 	const char *ADDR = bitmap->bitmap;
478 
479 	start -= bitmap->start;
480 	start_byte = start >> 3;
481 	start_bit = start % 8;
482 
483 	if (start_bit != 0) {
484 		/*
485 		 * The compared start block number or start inode number
486 		 * is not the first bit in a byte.
487 		 */
488 		mark_count = 8 - start_bit;
489 		if (len < 8 - start_bit) {
490 			mark_count = (int)len;
491 			mark_bit = len + start_bit - 1;
492 		} else
493 			mark_bit = 7;
494 
495 		for (i = mark_count; i > 0; i--, mark_bit--)
496 			first_bit |= 1 << mark_bit;
497 
498 		/*
499 		 * Compare blocks or inodes in the first byte.
500 		 * If there is any marked bit, this function returns 0.
501 		 */
502 		if (first_bit & ADDR[start_byte])
503 			return 0;
504 		else if (len <= 8 - start_bit)
505 			return 1;
506 
507 		start_byte++;
508 		len_bit = (len - mark_count) % 8;
509 		len_byte = (len - mark_count) >> 3;
510 	}
511 
512 	/*
513 	 * The compared start block number or start inode number is
514 	 * the first bit in a byte.
515 	 */
516 	if (len_bit != 0) {
517 		/*
518 		 * The compared end block number or end inode number is
519 		 * not the last bit in a byte.
520 		 */
521 		for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
522 			last_bit |= 1 << mark_bit;
523 
524 		/*
525 		 * Compare blocks or inodes in the last byte.
526 		 * If there is any marked bit, this function returns 0.
527 		 */
528 		if (last_bit & ADDR[start_byte + len_byte])
529 			return 0;
530 		else if (len_byte == 0)
531 			return 1;
532 	}
533 
534 	/* Check whether all bytes are 0 */
535 	return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
536 }
537 
ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap gen_bitmap,__u32 start,__u32 end,__u32 * out)538 errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap gen_bitmap,
539 						__u32 start, __u32 end,
540 						__u32 *out)
541 {
542 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
543 	blk_t b;
544 
545 	if (start < bitmap->start || end > bitmap->end || start > end) {
546 		ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR, start);
547 		return EINVAL;
548 	}
549 
550 	while (start <= end) {
551 		b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
552 		if (!b) {
553 			*out = start;
554 			return 0;
555 		}
556 		start++;
557 	}
558 
559 	return ENOENT;
560 }
561 
ext2fs_find_first_set_generic_bitmap(ext2fs_generic_bitmap gen_bitmap,__u32 start,__u32 end,__u32 * out)562 errcode_t ext2fs_find_first_set_generic_bitmap(ext2fs_generic_bitmap gen_bitmap,
563 					       __u32 start, __u32 end,
564 					       __u32 *out)
565 {
566 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
567 	blk_t b;
568 
569 	if (start < bitmap->start || end > bitmap->end || start > end) {
570 		ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR, start);
571 		return EINVAL;
572 	}
573 
574 	while (start <= end) {
575 		b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
576 		if (b) {
577 			*out = start;
578 			return 0;
579 		}
580 		start++;
581 	}
582 
583 	return ENOENT;
584 }
585 
ext2fs_test_block_bitmap_range(ext2fs_block_bitmap gen_bitmap,blk_t block,int num)586 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap gen_bitmap,
587 				   blk_t block, int num)
588 {
589 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
590 
591 	EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP);
592 	if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) {
593 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
594 				   block, bitmap->description);
595 		return 0;
596 	}
597 	return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
598 						      bitmap, block, num);
599 }
600 
ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap gen_bitmap,ext2_ino_t inode,int num)601 int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap gen_bitmap,
602 				   ext2_ino_t inode, int num)
603 {
604 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
605 
606 	EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP);
607 	if ((inode < bitmap->start) || (inode+num-1 > bitmap->real_end)) {
608 		ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
609 				   inode, bitmap->description);
610 		return 0;
611 	}
612 	return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
613 						      bitmap, inode, num);
614 }
615 
ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap gen_bitmap,blk_t block,int num)616 void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap gen_bitmap,
617 				    blk_t block, int num)
618 {
619 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
620 	int	i;
621 
622 	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
623 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
624 				   bitmap->description);
625 		return;
626 	}
627 	for (i=0; i < num; i++)
628 		ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
629 }
630 
ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap gen_bitmap,blk_t block,int num)631 void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap gen_bitmap,
632 				      blk_t block, int num)
633 {
634 	ext2fs_generic_bitmap_32 bitmap = (ext2fs_generic_bitmap_32) gen_bitmap;
635 	int	i;
636 
637 	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
638 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
639 				   bitmap->description);
640 		return;
641 	}
642 	for (i=0; i < num; i++)
643 		ext2fs_fast_clear_bit(block + i - bitmap->start,
644 				      bitmap->bitmap);
645 }
646 
647