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