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