gen_bitmap.c revision f1f115a78f5ea599fc5f8815a741d43fedd5840d 
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
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	retval = ext2fs_get_mem(size, &bitmap->bitmap);
107	if (retval) {
108		ext2fs_free_mem(&bitmap->description);
109		ext2fs_free_mem(&bitmap);
110		return retval;
111	}
112
113	if (init_map)
114		memcpy(bitmap->bitmap, init_map, size);
115	else
116		memset(bitmap->bitmap, 0, size);
117	*ret = bitmap;
118	return 0;
119}
120
121errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
122					 __u32 end,
123					 __u32 real_end,
124					 const char *descr,
125					 ext2fs_generic_bitmap *ret)
126{
127	return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
128					  start, end, real_end, descr, 0, ret);
129}
130
131errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,
132				     ext2fs_generic_bitmap *dest)
133{
134	return (ext2fs_make_generic_bitmap(src->magic, src->fs,
135					   src->start, src->end,
136					   src->real_end,
137					   src->description, src->bitmap,
138					   dest));
139}
140
141void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)
142{
143	if (check_magic(bitmap))
144		return;
145
146	bitmap->magic = 0;
147	if (bitmap->description) {
148		ext2fs_free_mem(&bitmap->description);
149		bitmap->description = 0;
150	}
151	if (bitmap->bitmap) {
152		ext2fs_free_mem(&bitmap->bitmap);
153		bitmap->bitmap = 0;
154	}
155	ext2fs_free_mem(&bitmap);
156}
157
158int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
159					blk_t bitno)
160{
161	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
162		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
163		return 0;
164	}
165	return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
166}
167
168int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
169					 __u32 bitno)
170{
171	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
172		ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
173		return 0;
174	}
175	return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
176}
177
178int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
179					   blk_t bitno)
180{
181	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
182		ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
183		return 0;
184	}
185	return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
186}
187
188__u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
189{
190	return bitmap->start;
191}
192
193__u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
194{
195	return bitmap->end;
196}
197
198void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
199{
200	if (check_magic(bitmap))
201		return;
202
203	memset(bitmap->bitmap, 0,
204	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
205}
206
207errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,
208					  errcode_t magic, errcode_t neq,
209					  ext2_ino_t end, ext2_ino_t *oend)
210{
211	EXT2_CHECK_MAGIC(bitmap, magic);
212
213	if (end > bitmap->real_end)
214		return neq;
215	if (oend)
216		*oend = bitmap->end;
217	bitmap->end = end;
218	return 0;
219}
220
221errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
222				       __u32 new_end, __u32 new_real_end,
223				       ext2fs_generic_bitmap bmap)
224{
225	errcode_t	retval;
226	size_t		size, new_size;
227	__u32		bitno;
228
229	if (!bmap || (bmap->magic != magic))
230		return magic;
231
232	/*
233	 * If we're expanding the bitmap, make sure all of the new
234	 * parts of the bitmap are zero.
235	 */
236	if (new_end > bmap->end) {
237		bitno = bmap->real_end;
238		if (bitno > new_end)
239			bitno = new_end;
240		for (; bitno > bmap->end; bitno--)
241			ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
242	}
243	if (new_real_end == bmap->real_end) {
244		bmap->end = new_end;
245		return 0;
246	}
247
248	size = ((bmap->real_end - bmap->start) / 8) + 1;
249	new_size = ((new_real_end - bmap->start) / 8) + 1;
250
251	if (size != new_size) {
252		retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
253		if (retval)
254			return retval;
255	}
256	if (new_size > size)
257		memset(bmap->bitmap + size, 0, new_size - size);
258
259	bmap->end = new_end;
260	bmap->real_end = new_real_end;
261	return 0;
262}
263
264errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
265					ext2fs_generic_bitmap bm1,
266					ext2fs_generic_bitmap bm2)
267{
268	blk_t	i;
269
270	if (!bm1 || bm1->magic != magic)
271		return magic;
272	if (!bm2 || bm2->magic != magic)
273		return magic;
274
275	if ((bm1->start != bm2->start) ||
276	    (bm1->end != bm2->end) ||
277	    (memcmp(bm1->bitmap, bm2->bitmap,
278		    (size_t) (bm1->end - bm1->start)/8)))
279		return neq;
280
281	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
282		if (ext2fs_fast_test_block_bitmap(bm1, i) !=
283		    ext2fs_fast_test_block_bitmap(bm2, i))
284			return neq;
285
286	return 0;
287}
288
289void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)
290{
291	__u32	i, j;
292
293	/* Protect loop from wrap-around if map->real_end is maxed */
294	for (i=map->end+1, j = i - map->start;
295	     i <= map->real_end && i > map->end;
296	     i++, j++)
297		ext2fs_set_bit(j, map->bitmap);
298}
299
300errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap,
301					  errcode_t magic,
302					  __u32 start, __u32 num,
303					  void *out)
304{
305	if (!bmap || (bmap->magic != magic))
306		return magic;
307
308	if ((start < bmap->start) || (start+num-1 > bmap->real_end))
309		return EXT2_ET_INVALID_ARGUMENT;
310
311	memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3);
312	return 0;
313}
314
315errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
316					  errcode_t magic,
317					  __u32 start, __u32 num,
318					  void *in)
319{
320	if (!bmap || (bmap->magic != magic))
321		return magic;
322
323	if ((start < bmap->start) || (start+num-1 > bmap->real_end))
324		return EXT2_ET_INVALID_ARGUMENT;
325
326	memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3);
327	return 0;
328}
329
330int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
331				   blk_t block, int num)
332{
333	int	i;
334
335	if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) {
336		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
337				   block, bitmap->description);
338		return 0;
339	}
340	for (i=0; i < num; i++) {
341		if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
342			return 0;
343	}
344	return 1;
345}
346
347void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
348				    blk_t block, int num)
349{
350	int	i;
351
352	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
353		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
354				   bitmap->description);
355		return;
356	}
357	for (i=0; i < num; i++)
358		ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
359}
360
361void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
362					       blk_t block, int num)
363{
364	int	i;
365
366	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
367		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
368				   bitmap->description);
369		return;
370	}
371	for (i=0; i < num; i++)
372		ext2fs_fast_clear_bit(block + i - bitmap->start,
373				      bitmap->bitmap);
374}
375