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