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