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