gen_bitmap64.c revision 67861e5bf3ae177b14d34846218fcdfdeee805a6 
1/*
2 * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and
3 * block bitmaps.
4 *
5 * Copyright (C) 2007, 2008 Theodore Ts'o.
6 *
7 * %Begin-Header%
8 * This file may be redistributed under the terms of the GNU Public
9 * License.
10 * %End-Header%
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#include <errno.h>
22#if HAVE_SYS_STAT_H
23#include <sys/stat.h>
24#endif
25#if HAVE_SYS_TYPES_H
26#include <sys/types.h>
27#endif
28
29#include "ext2_fs.h"
30#include "ext2fsP.h"
31#include "bmap64.h"
32
33/*
34 * Design of 64-bit bitmaps
35 *
36 * In order maintain ABI compatibility with programs that don't
37 * understand about 64-bit blocks/inodes,
38 * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap()
39 * will create old-style bitmaps unless the application passes the
40 * flag EXT2_FLAG_64BITS to ext2fs_open().  If this flag is
41 * passed, then we know the application has been recompiled, so we can
42 * use the new-style bitmaps.  If it is not passed, we have to return
43 * an error if trying to open a filesystem which needs 64-bit bitmaps.
44 *
45 * The new bitmaps use a new set of structure magic numbers, so that
46 * both the old-style and new-style interfaces can identify which
47 * version of the data structure was used.  Both the old-style and
48 * new-style interfaces will support either type of bitmap, although
49 * of course 64-bit operation will only be possible when both the
50 * new-style interface and the new-style bitmap are used.
51 *
52 * For example, the new bitmap interfaces will check the structure
53 * magic numbers and so will be able to detect old-stype bitmap.  If
54 * they see an old-style bitmap, they will pass it to the gen_bitmap.c
55 * functions for handling.  The same will be true for the old
56 * interfaces as well.
57 *
58 * The new-style interfaces will have several different back-end
59 * implementations, so we can support different encodings that are
60 * appropriate for different applications.  In general the default
61 * should be whatever makes sense, and what the application/library
62 * will use.  However, e2fsck may need specialized implementations for
63 * its own uses.  For example, when doing parent directory pointer
64 * loop detections in pass 3, the bitmap will *always* be sparse, so
65 * e2fsck can request an encoding which is optimized for that.
66 */
67
68static void warn_bitmap(ext2fs_generic_bitmap bitmap,
69			int code, __u64 arg)
70{
71#ifndef OMIT_COM_ERR
72	if (bitmap->description)
73		com_err(0, bitmap->base_error_code+code,
74			"#%llu for %s", arg, bitmap->description);
75	else
76		com_err(0, bitmap->base_error_code + code, "#%llu", arg);
77#endif
78}
79
80
81errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
82				    int type, __u64 start, __u64 end,
83				    __u64 real_end,
84				    const char *descr,
85				    ext2fs_generic_bitmap *ret)
86{
87	ext2fs_generic_bitmap	bitmap;
88	struct ext2_bitmap_ops	*ops;
89	errcode_t retval;
90
91	if (!type)
92		type = EXT2FS_BMAP64_BITARRAY;
93
94	switch (type) {
95	case EXT2FS_BMAP64_BITARRAY:
96		ops = &ext2fs_blkmap64_bitarray;
97		break;
98	default:
99		return EINVAL;
100	}
101
102	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
103				&bitmap);
104	if (retval)
105		return retval;
106
107	/* XXX factor out, repeated in copy_bmap */
108	bitmap->magic = magic;
109	bitmap->fs = fs;
110	bitmap->start = start;
111	bitmap->end = end;
112	bitmap->real_end = real_end;
113	bitmap->bitmap_ops = ops;
114	bitmap->cluster_bits = 0;
115	switch (magic) {
116	case EXT2_ET_MAGIC_INODE_BITMAP64:
117		bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
118		break;
119	case EXT2_ET_MAGIC_BLOCK_BITMAP64:
120		bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
121		bitmap->cluster_bits = fs->cluster_ratio_bits;
122		break;
123	default:
124		bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
125	}
126	if (descr) {
127		retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
128		if (retval) {
129			ext2fs_free_mem(&bitmap);
130			return retval;
131		}
132		strcpy(bitmap->description, descr);
133	} else
134		bitmap->description = 0;
135
136	retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
137	if (retval) {
138		ext2fs_free_mem(&bitmap->description);
139		ext2fs_free_mem(&bitmap);
140		return retval;
141	}
142
143	*ret = bitmap;
144	return 0;
145}
146
147void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
148{
149	if (!bmap)
150		return;
151
152	if (EXT2FS_IS_32_BITMAP(bmap)) {
153		ext2fs_free_generic_bitmap(bmap);
154		return;
155	}
156
157	if (!EXT2FS_IS_64_BITMAP(bmap))
158		return;
159
160	bmap->bitmap_ops->free_bmap(bmap);
161
162	if (bmap->description) {
163		ext2fs_free_mem(&bmap->description);
164		bmap->description = 0;
165	}
166	bmap->magic = 0;
167	ext2fs_free_mem(&bmap);
168}
169
170errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
171				   ext2fs_generic_bitmap *dest)
172{
173	char *descr, *new_descr;
174	ext2fs_generic_bitmap	new_bmap;
175	errcode_t retval;
176
177	if (!src)
178		return EINVAL;
179
180	if (EXT2FS_IS_32_BITMAP(src))
181		return ext2fs_copy_generic_bitmap(src, dest);
182
183	if (!EXT2FS_IS_64_BITMAP(src))
184		return EINVAL;
185
186	/* Allocate a new bitmap struct */
187	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
188				&new_bmap);
189	if (retval)
190		return retval;
191
192	/* Copy all the high-level parts over */
193	new_bmap->magic = src->magic;
194	new_bmap->fs = src->fs;
195	new_bmap->start = src->start;
196	new_bmap->end = src->end;
197	new_bmap->real_end = src->real_end;
198	new_bmap->bitmap_ops = src->bitmap_ops;
199	new_bmap->base_error_code = src->base_error_code;
200	new_bmap->cluster_bits = src->cluster_bits;
201
202	descr = src->description;
203	if (descr) {
204		retval = ext2fs_get_mem(strlen(descr)+1, &new_descr);
205		if (retval) {
206			ext2fs_free_mem(&new_bmap);
207			return retval;
208		}
209		strcpy(new_descr, descr);
210		new_bmap->description = new_descr;
211	}
212
213	retval = src->bitmap_ops->copy_bmap(src, new_bmap);
214	if (retval) {
215		ext2fs_free_mem(&new_bmap->description);
216		ext2fs_free_mem(&new_bmap);
217		return retval;
218	}
219
220	*dest = new_bmap;
221
222	return 0;
223}
224
225errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
226				     __u64 new_end,
227				     __u64 new_real_end)
228{
229	if (!bmap)
230		return EINVAL;
231
232	if (EXT2FS_IS_32_BITMAP(bmap))
233		return ext2fs_resize_generic_bitmap(bmap->magic, new_end,
234						    new_real_end, bmap);
235
236	if (!EXT2FS_IS_64_BITMAP(bmap))
237		return EINVAL;
238
239	return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
240}
241
242errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,
243					errcode_t neq,
244					__u64 end, __u64 *oend)
245{
246	if (!bitmap)
247		return EINVAL;
248
249	if (EXT2FS_IS_32_BITMAP(bitmap)) {
250		ext2_ino_t tmp_oend;
251		int retval;
252
253		retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic,
254							 neq, end, &tmp_oend);
255		if (oend)
256			*oend = tmp_oend;
257		return retval;
258	}
259
260	if (!EXT2FS_IS_64_BITMAP(bitmap))
261		return EINVAL;
262
263	if (end > bitmap->real_end)
264		return neq;
265	if (oend)
266		*oend = bitmap->end;
267	bitmap->end = end;
268	return 0;
269}
270
271__u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap)
272{
273	if (!bitmap)
274		return EINVAL;
275
276	if (EXT2FS_IS_32_BITMAP(bitmap))
277		return ext2fs_get_generic_bitmap_start(bitmap);
278
279	if (!EXT2FS_IS_64_BITMAP(bitmap))
280		return EINVAL;
281
282	return bitmap->start;
283}
284
285__u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap)
286{
287	if (!bitmap)
288		return EINVAL;
289
290	if (EXT2FS_IS_32_BITMAP(bitmap))
291		return ext2fs_get_generic_bitmap_end(bitmap);
292
293	if (!EXT2FS_IS_64_BITMAP(bitmap))
294		return EINVAL;
295
296	return bitmap->end;
297}
298
299void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)
300{
301	if (EXT2FS_IS_32_BITMAP(bitmap))
302		ext2fs_clear_generic_bitmap(bitmap);
303	else
304		bitmap->bitmap_ops->clear_bmap (bitmap);
305}
306
307int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
308			     __u64 arg)
309{
310	if (!bitmap)
311		return 0;
312
313	if (EXT2FS_IS_32_BITMAP(bitmap)) {
314		if (arg & ~0xffffffffULL) {
315			ext2fs_warn_bitmap2(bitmap,
316					    EXT2FS_MARK_ERROR, 0xffffffff);
317			return 0;
318		}
319		return ext2fs_mark_generic_bitmap(bitmap, arg);
320	}
321
322	if (!EXT2FS_IS_64_BITMAP(bitmap))
323		return 0;
324
325	arg >>= bitmap->cluster_bits;
326
327	if ((arg < bitmap->start) || (arg > bitmap->end)) {
328		warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
329		return 0;
330	}
331
332	return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
333}
334
335int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
336			       __u64 arg)
337{
338	if (!bitmap)
339		return 0;
340
341	if (EXT2FS_IS_32_BITMAP(bitmap)) {
342		if (arg & ~0xffffffffULL) {
343			ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR,
344					    0xffffffff);
345			return 0;
346		}
347		return ext2fs_unmark_generic_bitmap(bitmap, arg);
348	}
349
350	if (!EXT2FS_IS_64_BITMAP(bitmap))
351		return 0;
352
353	arg >>= bitmap->cluster_bits;
354
355	if ((arg < bitmap->start) || (arg > bitmap->end)) {
356		warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
357		return 0;
358	}
359
360	return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
361}
362
363int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
364			     __u64 arg)
365{
366	if (!bitmap)
367		return 0;
368
369	if (EXT2FS_IS_32_BITMAP(bitmap)) {
370		if (arg & ~0xffffffffULL) {
371			ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR,
372					    0xffffffff);
373			return 0;
374		}
375		return ext2fs_test_generic_bitmap(bitmap, arg);
376	}
377
378	if (!EXT2FS_IS_64_BITMAP(bitmap))
379		return 0;
380
381	arg >>= bitmap->cluster_bits;
382
383	if ((arg < bitmap->start) || (arg > bitmap->end)) {
384		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
385		return 0;
386	}
387
388	return bitmap->bitmap_ops->test_bmap(bitmap, arg);
389}
390
391errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
392					__u64 start, unsigned int num,
393					void *in)
394{
395	if (!bmap)
396		return EINVAL;
397
398	if (EXT2FS_IS_32_BITMAP(bmap)) {
399		if ((start+num-1) & ~0xffffffffULL) {
400			ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR,
401					    0xffffffff);
402			return EINVAL;
403		}
404		return ext2fs_set_generic_bitmap_range(bmap, bmap->magic,
405						       start, num, in);
406	}
407
408	if (!EXT2FS_IS_64_BITMAP(bmap))
409		return EINVAL;
410
411	return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
412}
413
414errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
415					__u64 start, unsigned int num,
416					void *out)
417{
418	if (!bmap)
419		return EINVAL;
420
421	if (EXT2FS_IS_32_BITMAP(bmap)) {
422		if ((start+num-1) & ~0xffffffffULL) {
423			ext2fs_warn_bitmap2(bmap,
424					    EXT2FS_UNMARK_ERROR, 0xffffffff);
425			return EINVAL;
426		}
427		return ext2fs_get_generic_bitmap_range(bmap, bmap->magic,
428						       start, num, out);
429	}
430
431	if (!EXT2FS_IS_64_BITMAP(bmap))
432		return EINVAL;
433
434	return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
435}
436
437errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
438				      ext2fs_generic_bitmap bm1,
439				      ext2fs_generic_bitmap bm2)
440{
441	blk64_t	i;
442
443	if (!bm1 || !bm2)
444		return EINVAL;
445	if (bm1->magic != bm2->magic)
446		return EINVAL;
447
448	/* Now we know both bitmaps have the same magic */
449	if (EXT2FS_IS_32_BITMAP(bm1))
450		return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2);
451
452	if (!EXT2FS_IS_64_BITMAP(bm1))
453		return EINVAL;
454
455	if ((bm1->start != bm2->start) ||
456	    (bm1->end != bm2->end))
457		return neq;
458
459	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
460		if (ext2fs_test_generic_bmap(bm1, i) !=
461		    ext2fs_test_generic_bmap(bm2, i))
462			return neq;
463
464	return 0;
465}
466
467void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap)
468{
469	__u64	start, num;
470
471	if (EXT2FS_IS_32_BITMAP(bmap)) {
472		ext2fs_set_generic_bitmap_padding(bmap);
473		return;
474	}
475
476	start = bmap->end + 1;
477	num = bmap->real_end - bmap->end;
478	bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
479	/* XXX ought to warn on error */
480}
481
482int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
483				    blk64_t block, unsigned int num)
484{
485	if (!bmap)
486		return EINVAL;
487
488	if (num == 1)
489		return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
490						 bmap, block);
491
492	if (EXT2FS_IS_32_BITMAP(bmap)) {
493		if ((block+num-1) & ~0xffffffffULL) {
494			ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
495					    EXT2FS_UNMARK_ERROR, 0xffffffff);
496			return EINVAL;
497		}
498		return ext2fs_test_block_bitmap_range(
499			(ext2fs_generic_bitmap) bmap, block, num);
500	}
501
502	if (!EXT2FS_IS_64_BITMAP(bmap))
503		return EINVAL;
504
505	return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
506}
507
508void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
509				     blk64_t block, unsigned int num)
510{
511	if (!bmap)
512		return;
513
514	if (EXT2FS_IS_32_BITMAP(bmap)) {
515		if ((block+num-1) & ~0xffffffffULL) {
516			ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
517					    EXT2FS_UNMARK_ERROR, 0xffffffff);
518			return;
519		}
520		ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
521					       block, num);
522	}
523
524	if (!EXT2FS_IS_64_BITMAP(bmap))
525		return;
526
527	if ((block < bmap->start) || (block+num-1 > bmap->end)) {
528		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
529				   bmap->description);
530		return;
531	}
532
533	bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
534}
535
536void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
537				       blk64_t block, unsigned int num)
538{
539	if (!bmap)
540		return;
541
542	if (EXT2FS_IS_32_BITMAP(bmap)) {
543		if ((block+num-1) & ~0xffffffffULL) {
544			ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
545					    EXT2FS_UNMARK_ERROR, 0xffffffff);
546			return;
547		}
548		ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
549						 block, num);
550	}
551
552	if (!EXT2FS_IS_64_BITMAP(bmap))
553		return;
554
555	if ((block < bmap->start) || (block+num-1 > bmap->end)) {
556		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
557				   bmap->description);
558		return;
559	}
560
561	bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
562}
563
564void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
565{
566#ifndef OMIT_COM_ERR
567	if (bitmap && bitmap->description)
568		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
569			"called %s with 64-bit bitmap for %s", func,
570			bitmap->description);
571	else
572		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
573			"called %s with 64-bit bitmap", func);
574#endif
575}
576
577errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
578					   ext2fs_block_bitmap *bitmap)
579{
580	ext2fs_block_bitmap	cmap, bmap;
581	errcode_t		retval;
582	blk64_t			i, b_end, c_end;
583	int			n, ratio;
584
585	bmap = *bitmap;
586
587	if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap))
588		return 0;	/* Nothing to do */
589
590	retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
591					      &cmap);
592	if (retval)
593		return retval;
594
595	i = bmap->start;
596	b_end = bmap->end;
597	bmap->end = bmap->real_end;
598	c_end = cmap->end;
599	cmap->end = cmap->real_end;
600	n = 0;
601	ratio = 1 << fs->cluster_ratio_bits;
602	while (i < bmap->real_end) {
603		if (ext2fs_test_block_bitmap2(bmap, i)) {
604			ext2fs_mark_block_bitmap2(cmap, i);
605			i += ratio - n;
606			n = 0;
607			continue;
608		}
609		i++; n++;
610		if (n >= ratio)
611			n = 0;
612	}
613	bmap->end = b_end;
614	cmap->end = c_end;
615	ext2fs_free_block_bitmap(bmap);
616	*bitmap = cmap;
617	return 0;
618}
619