gen_bitmap.c revision 50448d3dffc66f86592ee0d4b16e4bbe9d08449e 
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 Public
8 * License.
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
30/*
31 * Used by previously inlined function, so we have to export this and
32 * not change the function signature
33 */
34void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,
35			    int code, unsigned long arg)
36{
37#ifndef OMIT_COM_ERR
38	if (bitmap->description)
39		com_err(0, bitmap->base_error_code+code,
40			"#%lu for %s", arg, bitmap->description);
41	else
42		com_err(0, bitmap->base_error_code + code, "#%lu", arg);
43#endif
44}
45
46static errcode_t check_magic(ext2fs_generic_bitmap bitmap)
47{
48	if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) ||
49			 (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) ||
50			 (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP)))
51		return EXT2_ET_MAGIC_GENERIC_BITMAP;
52	return 0;
53}
54
55errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs,
56				     __u32 start, __u32 end, __u32 real_end,
57				     const char *descr, char *init_map,
58				     ext2fs_generic_bitmap *ret)
59{
60	ext2fs_generic_bitmap	bitmap;
61	errcode_t		retval;
62	size_t			size;
63
64	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
65				&bitmap);
66	if (retval)
67		return retval;
68
69	bitmap->magic = magic;
70	bitmap->fs = fs;
71	bitmap->start = start;
72	bitmap->end = end;
73	bitmap->real_end = real_end;
74	switch (magic) {
75	case EXT2_ET_MAGIC_INODE_BITMAP:
76		bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
77		break;
78	case EXT2_ET_MAGIC_BLOCK_BITMAP:
79		bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
80		break;
81	default:
82		bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
83	}
84	if (descr) {
85		retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
86		if (retval) {
87			ext2fs_free_mem(&bitmap);
88			return retval;
89		}
90		strcpy(bitmap->description, descr);
91	} else
92		bitmap->description = 0;
93
94	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
95	retval = ext2fs_get_mem(size, &bitmap->bitmap);
96	if (retval) {
97		ext2fs_free_mem(&bitmap->description);
98		ext2fs_free_mem(&bitmap);
99		return retval;
100	}
101
102	if (init_map)
103		memcpy(bitmap->bitmap, init_map, size);
104	else
105		memset(bitmap->bitmap, 0, size);
106	*ret = bitmap;
107	return 0;
108}
109
110errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
111					 __u32 end,
112					 __u32 real_end,
113					 const char *descr,
114					 ext2fs_generic_bitmap *ret)
115{
116	return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
117					  start, end, real_end, descr, 0, ret);
118}
119
120errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,
121				     ext2fs_generic_bitmap *dest)
122{
123	return (ext2fs_make_generic_bitmap(src->magic, src->fs,
124					   src->start, src->end,
125					   src->real_end,
126					   src->description, src->bitmap,
127					   dest));
128}
129
130void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)
131{
132	if (check_magic(bitmap))
133		return;
134
135	bitmap->magic = 0;
136	if (bitmap->description) {
137		ext2fs_free_mem(&bitmap->description);
138		bitmap->description = 0;
139	}
140	if (bitmap->bitmap) {
141		ext2fs_free_mem(&bitmap->bitmap);
142		bitmap->bitmap = 0;
143	}
144	ext2fs_free_mem(&bitmap);
145}
146
147int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
148					blk_t bitno)
149{
150	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
151		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
152		return 0;
153	}
154	return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
155}
156
157int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
158					 __u32 bitno)
159{
160	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
161		ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
162		return 0;
163	}
164	return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
165}
166
167int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
168					   blk_t bitno)
169{
170	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
171		ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
172		return 0;
173	}
174	return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
175}
176
177__u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
178{
179	return bitmap->start;
180}
181
182__u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
183{
184	return bitmap->end;
185}
186
187void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
188{
189	if (check_magic(bitmap))
190		return;
191
192	memset(bitmap->bitmap, 0,
193	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
194}
195
196errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,
197					  errcode_t magic, errcode_t neq,
198					  ext2_ino_t end, ext2_ino_t *oend)
199{
200	EXT2_CHECK_MAGIC(bitmap, magic);
201
202	if (end > bitmap->real_end)
203		return neq;
204	if (oend)
205		*oend = bitmap->end;
206	bitmap->end = end;
207	return 0;
208}
209
210errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
211				       __u32 new_end, __u32 new_real_end,
212				       ext2fs_generic_bitmap bmap)
213{
214	errcode_t	retval;
215	size_t		size, new_size;
216	__u32		bitno;
217
218	if (!bmap || (bmap->magic != magic))
219		return magic;
220
221	/*
222	 * If we're expanding the bitmap, make sure all of the new
223	 * parts of the bitmap are zero.
224	 */
225	if (new_end > bmap->end) {
226		bitno = bmap->real_end;
227		if (bitno > new_end)
228			bitno = new_end;
229		for (; bitno > bmap->end; bitno--)
230			ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
231	}
232	if (new_real_end == bmap->real_end) {
233		bmap->end = new_end;
234		return 0;
235	}
236
237	size = ((bmap->real_end - bmap->start) / 8) + 1;
238	new_size = ((new_real_end - bmap->start) / 8) + 1;
239
240	if (size != new_size) {
241		retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
242		if (retval)
243			return retval;
244	}
245	if (new_size > size)
246		memset(bmap->bitmap + size, 0, new_size - size);
247
248	bmap->end = new_end;
249	bmap->real_end = new_real_end;
250	return 0;
251}
252
253errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
254					ext2fs_generic_bitmap bm1,
255					ext2fs_generic_bitmap bm2)
256{
257	blk_t	i;
258
259	if (!bm1 || bm1->magic != magic)
260		return magic;
261	if (!bm2 || bm2->magic != magic)
262		return magic;
263
264	if ((bm1->start != bm2->start) ||
265	    (bm1->end != bm2->end) ||
266	    (memcmp(bm1->bitmap, bm2->bitmap,
267		    (size_t) (bm1->end - bm1->start)/8)))
268		return neq;
269
270	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
271		if (ext2fs_fast_test_block_bitmap(bm1, i) !=
272		    ext2fs_fast_test_block_bitmap(bm2, i))
273			return neq;
274
275	return 0;
276}
277
278void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)
279{
280	__u32	i, j;
281
282	/* Protect loop from wrap-around if map->real_end is maxed */
283	for (i=map->end+1, j = i - map->start;
284	     i <= map->real_end && i > map->end;
285	     i++, j++)
286		ext2fs_set_bit(j, map->bitmap);
287}
288
289int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
290				   blk_t block, int num)
291{
292	int	i;
293
294	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
295		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
296				   block, bitmap->description);
297		return 0;
298	}
299	for (i=0; i < num; i++) {
300		if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
301			return 0;
302	}
303	return 1;
304}
305
306void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
307				    blk_t block, int num)
308{
309	int	i;
310
311	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
312		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
313				   bitmap->description);
314		return;
315	}
316	for (i=0; i < num; i++)
317		ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
318}
319
320void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
321					       blk_t block, int num)
322{
323	int	i;
324
325	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
326		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
327				   bitmap->description);
328		return;
329	}
330	for (i=0; i < num; i++)
331		ext2fs_fast_clear_bit(block + i - bitmap->start,
332				      bitmap->bitmap);
333}
334