gen_bitmap64.c revision ba37bb704f4ab2631a39c32b35d6bb339e17b293 
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	switch (type) {
92	case EXT2FS_BMAP64_BITARRAY:
93		ops = &ext2fs_blkmap64_bitarray;
94		break;
95	default:
96		return EINVAL;
97	}
98
99	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
100				&bitmap);
101	if (retval)
102		return retval;
103
104	/* XXX factor out, repeated in copy_bmap */
105	bitmap->magic = magic;
106	bitmap->fs = fs;
107	bitmap->start = start;
108	bitmap->end = end;
109	bitmap->real_end = real_end;
110	bitmap->bitmap_ops = ops;
111	bitmap->cluster_bits = 0;
112	switch (magic) {
113	case EXT2_ET_MAGIC_INODE_BITMAP64:
114		bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
115		break;
116	case EXT2_ET_MAGIC_BLOCK_BITMAP64:
117		bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
118		bitmap->cluster_bits = fs->cluster_ratio_bits;
119		break;
120	default:
121		bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
122	}
123	if (descr) {
124		retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
125		if (retval) {
126			ext2fs_free_mem(&bitmap);
127			return retval;
128		}
129		strcpy(bitmap->description, descr);
130	} else
131		bitmap->description = 0;
132
133	retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
134	if (retval) {
135		ext2fs_free_mem(&bitmap->description);
136		ext2fs_free_mem(&bitmap);
137		return retval;
138	}
139
140	*ret = bitmap;
141	return 0;
142}
143
144void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
145{
146	if (!bmap)
147		return;
148
149	if (EXT2FS_IS_32_BITMAP(bmap)) {
150		ext2fs_free_generic_bitmap(bmap);
151		return;
152	}
153
154	if (!EXT2FS_IS_64_BITMAP(bmap))
155		return;
156
157	bmap->bitmap_ops->free_bmap(bmap);
158
159	if (bmap->description) {
160		ext2fs_free_mem(&bmap->description);
161		bmap->description = 0;
162	}
163	bmap->magic = 0;
164	ext2fs_free_mem(&bmap);
165}
166
167errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
168				   ext2fs_generic_bitmap *dest)
169{
170	char *descr, *new_descr;
171	ext2fs_generic_bitmap	new_bmap;
172	errcode_t retval;
173
174	if (!src)
175		return EINVAL;
176
177	if (EXT2FS_IS_32_BITMAP(src))
178		return ext2fs_copy_generic_bitmap(src, dest);
179
180	if (!EXT2FS_IS_64_BITMAP(src))
181		return EINVAL;
182
183	/* Allocate a new bitmap struct */
184	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
185				&new_bmap);
186	if (retval)
187		return retval;
188
189	/* Copy all the high-level parts over */
190	new_bmap->magic = src->magic;
191	new_bmap->fs = src->fs;
192	new_bmap->start = src->start;
193	new_bmap->end = src->end;
194	new_bmap->real_end = src->real_end;
195	new_bmap->bitmap_ops = src->bitmap_ops;
196	new_bmap->base_error_code = src->base_error_code;
197	new_bmap->cluster_bits = src->cluster_bits;
198
199	descr = src->description;
200	if (descr) {
201		retval = ext2fs_get_mem(strlen(descr)+1, &new_descr);
202		if (retval) {
203			ext2fs_free_mem(&new_bmap);
204			return retval;
205		}
206		strcpy(new_descr, descr);
207		new_bmap->description = new_descr;
208	}
209
210	retval = src->bitmap_ops->copy_bmap(src, new_bmap);
211	if (retval) {
212		ext2fs_free_mem(&new_bmap->description);
213		ext2fs_free_mem(&new_bmap);
214		return retval;
215	}
216
217	*dest = new_bmap;
218
219	return 0;
220}
221
222errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
223				     __u64 new_end,
224				     __u64 new_real_end)
225{
226	if (!bmap)
227		return EINVAL;
228
229	if (EXT2FS_IS_32_BITMAP(bmap))
230		return ext2fs_resize_generic_bitmap(bmap->magic, new_end,
231						    new_real_end, bmap);
232
233	if (!EXT2FS_IS_64_BITMAP(bmap))
234		return EINVAL;
235
236	return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
237}
238
239errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,
240					errcode_t neq,
241					__u64 end, __u64 *oend)
242{
243	if (!bitmap)
244		return EINVAL;
245
246	if (EXT2FS_IS_32_BITMAP(bitmap)) {
247		ext2_ino_t tmp_oend;
248		int retval;
249
250		retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic,
251							 neq, end, &tmp_oend);
252		if (oend)
253			*oend = tmp_oend;
254		return retval;
255	}
256
257	if (!EXT2FS_IS_64_BITMAP(bitmap))
258		return EINVAL;
259
260	if (end > bitmap->real_end)
261		return neq;
262	if (oend)
263		*oend = bitmap->end;
264	bitmap->end = end;
265	return 0;
266}
267
268__u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap)
269{
270	if (!bitmap)
271		return EINVAL;
272
273	if (EXT2FS_IS_32_BITMAP(bitmap))
274		return ext2fs_get_generic_bitmap_start(bitmap);
275
276	if (!EXT2FS_IS_64_BITMAP(bitmap))
277		return EINVAL;
278
279	return bitmap->start;
280}
281
282__u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap)
283{
284	if (!bitmap)
285		return EINVAL;
286
287	if (EXT2FS_IS_32_BITMAP(bitmap))
288		return ext2fs_get_generic_bitmap_end(bitmap);
289
290	if (!EXT2FS_IS_64_BITMAP(bitmap))
291		return EINVAL;
292
293	return bitmap->end;
294}
295
296void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)
297{
298	if (EXT2FS_IS_32_BITMAP(bitmap))
299		ext2fs_clear_generic_bitmap(bitmap);
300	else
301		bitmap->bitmap_ops->clear_bmap (bitmap);
302}
303
304int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
305			     __u64 arg)
306{
307	if (!bitmap)
308		return 0;
309
310	if (EXT2FS_IS_32_BITMAP(bitmap)) {
311		if (arg & ~0xffffffffULL) {
312			ext2fs_warn_bitmap2(bitmap,
313					    EXT2FS_MARK_ERROR, 0xffffffff);
314			return 0;
315		}
316		return ext2fs_mark_generic_bitmap(bitmap, arg);
317	}
318
319	if (!EXT2FS_IS_64_BITMAP(bitmap))
320		return 0;
321
322	arg >>= bitmap->cluster_bits;
323
324	if ((arg < bitmap->start) || (arg > bitmap->end)) {
325		warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
326		return 0;
327	}
328
329	return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
330}
331
332int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
333			       __u64 arg)
334{
335	if (!bitmap)
336		return 0;
337
338	if (EXT2FS_IS_32_BITMAP(bitmap)) {
339		if (arg & ~0xffffffffULL) {
340			ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR,
341					    0xffffffff);
342			return 0;
343		}
344		return ext2fs_unmark_generic_bitmap(bitmap, arg);
345	}
346
347	if (!EXT2FS_IS_64_BITMAP(bitmap))
348		return 0;
349
350	arg >>= bitmap->cluster_bits;
351
352	if ((arg < bitmap->start) || (arg > bitmap->end)) {
353		warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
354		return 0;
355	}
356
357	return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
358}
359
360int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
361			     __u64 arg)
362{
363	if (!bitmap)
364		return 0;
365
366	if (EXT2FS_IS_32_BITMAP(bitmap)) {
367		if (arg & ~0xffffffffULL) {
368			ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR,
369					    0xffffffff);
370			return 0;
371		}
372		return ext2fs_test_generic_bitmap(bitmap, arg);
373	}
374
375	if (!EXT2FS_IS_64_BITMAP(bitmap))
376		return 0;
377
378	arg >>= bitmap->cluster_bits;
379
380	if ((arg < bitmap->start) || (arg > bitmap->end)) {
381		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
382		return 0;
383	}
384
385	return bitmap->bitmap_ops->test_bmap(bitmap, arg);
386}
387
388errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
389					__u64 start, unsigned int num,
390					void *in)
391{
392	if (!bmap)
393		return EINVAL;
394
395	if (EXT2FS_IS_32_BITMAP(bmap)) {
396		if ((start+num-1) & ~0xffffffffULL) {
397			ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR,
398					    0xffffffff);
399			return EINVAL;
400		}
401		return ext2fs_set_generic_bitmap_range(bmap, bmap->magic,
402						       start, num, in);
403	}
404
405	if (!EXT2FS_IS_64_BITMAP(bmap))
406		return EINVAL;
407
408	return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
409}
410
411errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
412					__u64 start, unsigned int num,
413					void *out)
414{
415	if (!bmap)
416		return EINVAL;
417
418	if (EXT2FS_IS_32_BITMAP(bmap)) {
419		if ((start+num-1) & ~0xffffffffULL) {
420			ext2fs_warn_bitmap2(bmap,
421					    EXT2FS_UNMARK_ERROR, 0xffffffff);
422			return EINVAL;
423		}
424		return ext2fs_get_generic_bitmap_range(bmap, bmap->magic,
425						       start, num, out);
426	}
427
428	if (!EXT2FS_IS_64_BITMAP(bmap))
429		return EINVAL;
430
431	return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
432}
433
434errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
435				      ext2fs_generic_bitmap bm1,
436				      ext2fs_generic_bitmap bm2)
437{
438	blk64_t	i;
439
440	if (!bm1 || !bm2)
441		return EINVAL;
442	if (bm1->magic != bm2->magic)
443		return EINVAL;
444
445	/* Now we know both bitmaps have the same magic */
446	if (EXT2FS_IS_32_BITMAP(bm1))
447		return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2);
448
449	if (!EXT2FS_IS_64_BITMAP(bm1))
450		return EINVAL;
451
452	if ((bm1->start != bm2->start) ||
453	    (bm1->end != bm2->end))
454		return neq;
455
456	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
457		if (ext2fs_test_generic_bmap(bm1, i) !=
458		    ext2fs_test_generic_bmap(bm2, i))
459			return neq;
460
461	return 0;
462}
463
464void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap)
465{
466	__u64	start, num;
467
468	if (EXT2FS_IS_32_BITMAP(bmap)) {
469		ext2fs_set_generic_bitmap_padding(bmap);
470		return;
471	}
472
473	start = bmap->end + 1;
474	num = bmap->real_end - bmap->end;
475	bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
476	/* XXX ought to warn on error */
477}
478
479int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
480				    blk64_t block, unsigned int num)
481{
482	if (!bmap)
483		return EINVAL;
484
485	if (num == 1)
486		return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
487						 bmap, block);
488
489	if (EXT2FS_IS_32_BITMAP(bmap)) {
490		if ((block+num-1) & ~0xffffffffULL) {
491			ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
492					    EXT2FS_UNMARK_ERROR, 0xffffffff);
493			return EINVAL;
494		}
495		return ext2fs_test_block_bitmap_range(
496			(ext2fs_generic_bitmap) bmap, block, num);
497	}
498
499	if (!EXT2FS_IS_64_BITMAP(bmap))
500		return EINVAL;
501
502	return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
503}
504
505void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
506				     blk64_t block, unsigned int num)
507{
508	if (!bmap)
509		return;
510
511	if (EXT2FS_IS_32_BITMAP(bmap)) {
512		if ((block+num-1) & ~0xffffffffULL) {
513			ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
514					    EXT2FS_UNMARK_ERROR, 0xffffffff);
515			return;
516		}
517		ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
518					       block, num);
519	}
520
521	if (!EXT2FS_IS_64_BITMAP(bmap))
522		return;
523
524	if ((block < bmap->start) || (block+num-1 > bmap->end)) {
525		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
526				   bmap->description);
527		return;
528	}
529
530	bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
531}
532
533void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
534				       blk64_t block, unsigned int num)
535{
536	if (!bmap)
537		return;
538
539	if (EXT2FS_IS_32_BITMAP(bmap)) {
540		if ((block+num-1) & ~0xffffffffULL) {
541			ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
542					    EXT2FS_UNMARK_ERROR, 0xffffffff);
543			return;
544		}
545		ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
546						 block, num);
547	}
548
549	if (!EXT2FS_IS_64_BITMAP(bmap))
550		return;
551
552	if ((block < bmap->start) || (block+num-1 > bmap->end)) {
553		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
554				   bmap->description);
555		return;
556	}
557
558	bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
559}
560
561void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
562{
563#ifndef OMIT_COM_ERR
564	if (bitmap && bitmap->description)
565		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
566			"called %s with 64-bit bitmap for %s", func,
567			bitmap->description);
568	else
569		com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
570			"called %s with 64-bit bitmap", func);
571#endif
572}
573
574errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
575					   ext2fs_block_bitmap *bitmap)
576{
577	ext2fs_block_bitmap	cmap, bmap;
578	errcode_t		retval;
579	blk64_t			i, b_end, c_end;
580	int			n, ratio;
581
582	bmap = *bitmap;
583
584	if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap))
585		return 0;	/* Nothing to do */
586
587	retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
588					      &cmap);
589	if (retval)
590		return retval;
591
592	i = bmap->start;
593	b_end = bmap->end;
594	bmap->end = bmap->real_end;
595	c_end = cmap->end;
596	cmap->end = cmap->real_end;
597	n = 0;
598	ratio = 1 << fs->cluster_ratio_bits;
599	while (i < bmap->real_end) {
600		if (ext2fs_test_block_bitmap2(bmap, i)) {
601			ext2fs_mark_block_bitmap2(cmap, i);
602			i += ratio - n;
603			n = 0;
604			continue;
605		}
606		i++; n++;
607		if (n >= ratio)
608			n = 0;
609	}
610	bmap->end = b_end;
611	cmap->end = c_end;
612	ext2fs_free_block_bitmap(bmap);
613	*bitmap = cmap;
614	return 0;
615}
616