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