1/*
2 * pass5.c --- check block and inode bitmaps against on-disk bitmaps
3 *
4 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 *
11 */
12
13#include "e2fsck.h"
14#include "problem.h"
15
16static void check_block_bitmaps(e2fsck_t ctx);
17static void check_inode_bitmaps(e2fsck_t ctx);
18static void check_inode_end(e2fsck_t ctx);
19static void check_block_end(e2fsck_t ctx);
20
21void e2fsck_pass5(e2fsck_t ctx)
22{
23#ifdef RESOURCE_TRACK
24	struct resource_track	rtrack;
25#endif
26	struct problem_context	pctx;
27
28#ifdef MTRACE
29	mtrace_print("Pass 5");
30#endif
31
32	init_resource_track(&rtrack, ctx->fs->io);
33	clear_problem_context(&pctx);
34
35	if (!(ctx->options & E2F_OPT_PREEN))
36		fix_problem(ctx, PR_5_PASS_HEADER, &pctx);
37
38	if (ctx->progress)
39		if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2))
40			return;
41
42	e2fsck_read_bitmaps(ctx);
43
44	check_block_bitmaps(ctx);
45	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
46		return;
47	check_inode_bitmaps(ctx);
48	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
49		return;
50	check_inode_end(ctx);
51	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
52		return;
53	check_block_end(ctx);
54	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
55		return;
56
57	ext2fs_free_inode_bitmap(ctx->inode_used_map);
58	ctx->inode_used_map = 0;
59	ext2fs_free_inode_bitmap(ctx->inode_dir_map);
60	ctx->inode_dir_map = 0;
61	ext2fs_free_block_bitmap(ctx->block_found_map);
62	ctx->block_found_map = 0;
63
64	print_resource_track(ctx, _("Pass 5"), &rtrack, ctx->fs->io);
65}
66
67#define NO_BLK ((blk_t) -1)
68
69static void print_bitmap_problem(e2fsck_t ctx, int problem,
70			    struct problem_context *pctx)
71{
72	switch (problem) {
73	case PR_5_BLOCK_UNUSED:
74		if (pctx->blk == pctx->blk2)
75			pctx->blk2 = 0;
76		else
77			problem = PR_5_BLOCK_RANGE_UNUSED;
78		break;
79	case PR_5_BLOCK_USED:
80		if (pctx->blk == pctx->blk2)
81			pctx->blk2 = 0;
82		else
83			problem = PR_5_BLOCK_RANGE_USED;
84		break;
85	case PR_5_INODE_UNUSED:
86		if (pctx->ino == pctx->ino2)
87			pctx->ino2 = 0;
88		else
89			problem = PR_5_INODE_RANGE_UNUSED;
90		break;
91	case PR_5_INODE_USED:
92		if (pctx->ino == pctx->ino2)
93			pctx->ino2 = 0;
94		else
95			problem = PR_5_INODE_RANGE_USED;
96		break;
97	}
98	fix_problem(ctx, problem, pctx);
99	pctx->blk = pctx->blk2 = NO_BLK;
100	pctx->ino = pctx->ino2 = 0;
101}
102
103static void check_block_bitmaps(e2fsck_t ctx)
104{
105	ext2_filsys fs = ctx->fs;
106	blk_t	i;
107	int	*free_array;
108	int	group = 0;
109	blk_t	blocks = 0;
110	blk_t	free_blocks = 0;
111	int	group_free = 0;
112	int	actual, bitmap;
113	struct problem_context	pctx;
114	int	problem, save_problem, fixit, had_problem;
115	errcode_t	retval;
116	int		csum_flag;
117	int		skip_group = 0;
118
119	clear_problem_context(&pctx);
120	free_array = (int *) e2fsck_allocate_memory(ctx,
121	    fs->group_desc_count * sizeof(int), "free block count array");
122
123	if ((fs->super->s_first_data_block <
124	     ext2fs_get_block_bitmap_start(ctx->block_found_map)) ||
125	    (fs->super->s_blocks_count-1 >
126	     ext2fs_get_block_bitmap_end(ctx->block_found_map))) {
127		pctx.num = 1;
128		pctx.blk = fs->super->s_first_data_block;
129		pctx.blk2 = fs->super->s_blocks_count -1;
130		pctx.ino = ext2fs_get_block_bitmap_start(ctx->block_found_map);
131		pctx.ino2 = ext2fs_get_block_bitmap_end(ctx->block_found_map);
132		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
133
134		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
135		goto errout;
136	}
137
138	if ((fs->super->s_first_data_block <
139	     ext2fs_get_block_bitmap_start(fs->block_map)) ||
140	    (fs->super->s_blocks_count-1 >
141	     ext2fs_get_block_bitmap_end(fs->block_map))) {
142		pctx.num = 2;
143		pctx.blk = fs->super->s_first_data_block;
144		pctx.blk2 = fs->super->s_blocks_count -1;
145		pctx.ino = ext2fs_get_block_bitmap_start(fs->block_map);
146		pctx.ino2 = ext2fs_get_block_bitmap_end(fs->block_map);
147		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
148
149		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
150		goto errout;
151	}
152
153	csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
154					       EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
155redo_counts:
156	had_problem = 0;
157	save_problem = 0;
158	pctx.blk = pctx.blk2 = NO_BLK;
159	if (csum_flag &&
160	    (fs->group_desc[group].bg_flags & EXT2_BG_BLOCK_UNINIT))
161		skip_group++;
162	for (i = fs->super->s_first_data_block;
163	     i < fs->super->s_blocks_count;
164	     i++) {
165		actual = ext2fs_fast_test_block_bitmap(ctx->block_found_map, i);
166
167		if (skip_group) {
168			blk_t	super_blk, old_desc_blk, new_desc_blk;
169			int	old_desc_blocks;
170
171			ext2fs_super_and_bgd_loc(fs, group, &super_blk,
172					 &old_desc_blk, &new_desc_blk, 0);
173
174			if (fs->super->s_feature_incompat &
175			    EXT2_FEATURE_INCOMPAT_META_BG)
176				old_desc_blocks = fs->super->s_first_meta_bg;
177			else
178				old_desc_blocks = fs->desc_blocks +
179					fs->super->s_reserved_gdt_blocks;
180
181			bitmap = 0;
182			if (i == super_blk)
183				bitmap = 1;
184			if (old_desc_blk && old_desc_blocks &&
185			    (i >= old_desc_blk) &&
186			    (i < old_desc_blk + old_desc_blocks))
187				bitmap = 1;
188			if (new_desc_blk &&
189			    (i == new_desc_blk))
190				bitmap = 1;
191			if (i == fs->group_desc[group].bg_block_bitmap)
192				bitmap = 1;
193			else if (i == fs->group_desc[group].bg_inode_bitmap)
194				bitmap = 1;
195			else if (i >= fs->group_desc[group].bg_inode_table &&
196				 (i < fs->group_desc[group].bg_inode_table
197				  + fs->inode_blocks_per_group))
198				bitmap = 1;
199			actual = (actual != 0);
200		} else
201			bitmap = ext2fs_fast_test_block_bitmap(fs->block_map, i);
202
203		if (actual == bitmap)
204			goto do_counts;
205
206		if (!actual && bitmap) {
207			/*
208			 * Block not used, but marked in use in the bitmap.
209			 */
210			problem = PR_5_BLOCK_UNUSED;
211		} else {
212			/*
213			 * Block used, but not marked in use in the bitmap.
214			 */
215			problem = PR_5_BLOCK_USED;
216
217			if (skip_group) {
218				struct problem_context pctx2;
219				pctx2.blk = i;
220				pctx2.group = group;
221				if (fix_problem(ctx, PR_5_BLOCK_UNINIT,&pctx2)){
222					fs->group_desc[group].bg_flags &=
223						~EXT2_BG_BLOCK_UNINIT;
224					skip_group = 0;
225				}
226			}
227		}
228		if (pctx.blk == NO_BLK) {
229			pctx.blk = pctx.blk2 = i;
230			save_problem = problem;
231		} else {
232			if ((problem == save_problem) &&
233			    (pctx.blk2 == i-1))
234				pctx.blk2++;
235			else {
236				print_bitmap_problem(ctx, save_problem, &pctx);
237				pctx.blk = pctx.blk2 = i;
238				save_problem = problem;
239			}
240		}
241		ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
242		had_problem++;
243
244	do_counts:
245		if (!bitmap && (!skip_group || csum_flag)) {
246			group_free++;
247			free_blocks++;
248		}
249		blocks ++;
250		if ((blocks == fs->super->s_blocks_per_group) ||
251		    (i == fs->super->s_blocks_count-1)) {
252			free_array[group] = group_free;
253			group ++;
254			blocks = 0;
255			group_free = 0;
256			skip_group = 0;
257			if (ctx->progress)
258				if ((ctx->progress)(ctx, 5, group,
259						    fs->group_desc_count*2))
260					goto errout;
261			if (csum_flag &&
262			    (i != fs->super->s_blocks_count-1) &&
263			    (fs->group_desc[group].bg_flags &
264			     EXT2_BG_BLOCK_UNINIT))
265				skip_group++;
266		}
267	}
268	if (pctx.blk != NO_BLK)
269		print_bitmap_problem(ctx, save_problem, &pctx);
270	if (had_problem)
271		fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP);
272	else
273		fixit = -1;
274	ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
275
276	if (fixit == 1) {
277		ext2fs_free_block_bitmap(fs->block_map);
278		retval = ext2fs_copy_bitmap(ctx->block_found_map,
279						  &fs->block_map);
280		if (retval) {
281			clear_problem_context(&pctx);
282			fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx);
283			ctx->flags |= E2F_FLAG_ABORT;
284			goto errout;
285		}
286		ext2fs_set_bitmap_padding(fs->block_map);
287		ext2fs_mark_bb_dirty(fs);
288
289		/* Redo the counts */
290		blocks = 0; free_blocks = 0; group_free = 0; group = 0;
291		memset(free_array, 0, fs->group_desc_count * sizeof(int));
292		goto redo_counts;
293	} else if (fixit == 0)
294		ext2fs_unmark_valid(fs);
295
296	for (i = 0; i < fs->group_desc_count; i++) {
297		if (free_array[i] != fs->group_desc[i].bg_free_blocks_count) {
298			pctx.group = i;
299			pctx.blk = fs->group_desc[i].bg_free_blocks_count;
300			pctx.blk2 = free_array[i];
301
302			if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP,
303					&pctx)) {
304				fs->group_desc[i].bg_free_blocks_count =
305					free_array[i];
306				ext2fs_mark_super_dirty(fs);
307			} else
308				ext2fs_unmark_valid(fs);
309		}
310	}
311	if (free_blocks != fs->super->s_free_blocks_count) {
312		pctx.group = 0;
313		pctx.blk = fs->super->s_free_blocks_count;
314		pctx.blk2 = free_blocks;
315
316		if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) {
317			fs->super->s_free_blocks_count = free_blocks;
318			ext2fs_mark_super_dirty(fs);
319		} else
320			ext2fs_unmark_valid(fs);
321	}
322errout:
323	ext2fs_free_mem(&free_array);
324}
325
326static void check_inode_bitmaps(e2fsck_t ctx)
327{
328	ext2_filsys fs = ctx->fs;
329	ext2_ino_t	i;
330	unsigned int	free_inodes = 0;
331	int		group_free = 0;
332	int		dirs_count = 0;
333	int		group = 0;
334	unsigned int	inodes = 0;
335	int		*free_array;
336	int		*dir_array;
337	int		actual, bitmap;
338	errcode_t	retval;
339	struct problem_context	pctx;
340	int		problem, save_problem, fixit, had_problem;
341	int		csum_flag;
342	int		skip_group = 0;
343
344	clear_problem_context(&pctx);
345	free_array = (int *) e2fsck_allocate_memory(ctx,
346	    fs->group_desc_count * sizeof(int), "free inode count array");
347
348	dir_array = (int *) e2fsck_allocate_memory(ctx,
349	   fs->group_desc_count * sizeof(int), "directory count array");
350
351	if ((1 < ext2fs_get_inode_bitmap_start(ctx->inode_used_map)) ||
352	    (fs->super->s_inodes_count >
353	     ext2fs_get_inode_bitmap_end(ctx->inode_used_map))) {
354		pctx.num = 3;
355		pctx.blk = 1;
356		pctx.blk2 = fs->super->s_inodes_count;
357		pctx.ino = ext2fs_get_inode_bitmap_start(ctx->inode_used_map);
358		pctx.ino2 = ext2fs_get_inode_bitmap_end(ctx->inode_used_map);
359		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
360
361		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
362		goto errout;
363	}
364	if ((1 < ext2fs_get_inode_bitmap_start(fs->inode_map)) ||
365	    (fs->super->s_inodes_count >
366	     ext2fs_get_inode_bitmap_end(fs->inode_map))) {
367		pctx.num = 4;
368		pctx.blk = 1;
369		pctx.blk2 = fs->super->s_inodes_count;
370		pctx.ino = ext2fs_get_inode_bitmap_start(fs->inode_map);
371		pctx.ino2 = ext2fs_get_inode_bitmap_end(fs->inode_map);
372		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
373
374		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
375		goto errout;
376	}
377
378	csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
379					       EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
380redo_counts:
381	had_problem = 0;
382	save_problem = 0;
383	pctx.ino = pctx.ino2 = 0;
384	if (csum_flag &&
385	    (fs->group_desc[group].bg_flags & EXT2_BG_INODE_UNINIT))
386		skip_group++;
387
388	/* Protect loop from wrap-around if inodes_count is maxed */
389	for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) {
390		actual = ext2fs_fast_test_inode_bitmap(ctx->inode_used_map, i);
391		if (skip_group)
392			bitmap = 0;
393		else
394			bitmap = ext2fs_fast_test_inode_bitmap(fs->inode_map, i);
395		if (actual == bitmap)
396			goto do_counts;
397
398		if (!actual && bitmap) {
399			/*
400			 * Inode wasn't used, but marked in bitmap
401			 */
402			problem = PR_5_INODE_UNUSED;
403		} else /* if (actual && !bitmap) */ {
404			/*
405			 * Inode used, but not in bitmap
406			 */
407			problem = PR_5_INODE_USED;
408
409			/* We should never hit this, because it means that
410			 * inodes were marked in use that weren't noticed
411			 * in pass1 or pass 2. It is easier to fix the problem
412			 * than to kill e2fsck and leave the user stuck. */
413			if (skip_group) {
414				struct problem_context pctx2;
415				pctx2.blk = i;
416				pctx2.group = group;
417				if (fix_problem(ctx, PR_5_INODE_UNINIT,&pctx2)){
418					fs->group_desc[group].bg_flags &=
419						~EXT2_BG_INODE_UNINIT;
420					skip_group = 0;
421				}
422			}
423		}
424		if (pctx.ino == 0) {
425			pctx.ino = pctx.ino2 = i;
426			save_problem = problem;
427		} else {
428			if ((problem == save_problem) &&
429			    (pctx.ino2 == i-1))
430				pctx.ino2++;
431			else {
432				print_bitmap_problem(ctx, save_problem, &pctx);
433				pctx.ino = pctx.ino2 = i;
434				save_problem = problem;
435			}
436		}
437		ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
438		had_problem++;
439
440do_counts:
441		if (bitmap) {
442			if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, i))
443				dirs_count++;
444		} else if (!skip_group || csum_flag) {
445			group_free++;
446			free_inodes++;
447		}
448		inodes++;
449		if ((inodes == fs->super->s_inodes_per_group) ||
450		    (i == fs->super->s_inodes_count)) {
451			free_array[group] = group_free;
452			dir_array[group] = dirs_count;
453			group ++;
454			inodes = 0;
455			skip_group = 0;
456			group_free = 0;
457			dirs_count = 0;
458			if (ctx->progress)
459				if ((ctx->progress)(ctx, 5,
460					    group + fs->group_desc_count,
461					    fs->group_desc_count*2))
462					goto errout;
463			if (csum_flag &&
464			    (i != fs->super->s_inodes_count) &&
465			    (fs->group_desc[group].bg_flags &
466			     EXT2_BG_INODE_UNINIT))
467				skip_group++;
468		}
469	}
470	if (pctx.ino)
471		print_bitmap_problem(ctx, save_problem, &pctx);
472
473	if (had_problem)
474		fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP);
475	else
476		fixit = -1;
477	ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
478
479	if (fixit == 1) {
480		ext2fs_free_inode_bitmap(fs->inode_map);
481		retval = ext2fs_copy_bitmap(ctx->inode_used_map,
482						  &fs->inode_map);
483		if (retval) {
484			clear_problem_context(&pctx);
485			fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx);
486			ctx->flags |= E2F_FLAG_ABORT;
487			goto errout;
488		}
489		ext2fs_set_bitmap_padding(fs->inode_map);
490		ext2fs_mark_ib_dirty(fs);
491
492		/* redo counts */
493		inodes = 0; free_inodes = 0; group_free = 0;
494		dirs_count = 0; group = 0;
495		memset(free_array, 0, fs->group_desc_count * sizeof(int));
496		memset(dir_array, 0, fs->group_desc_count * sizeof(int));
497		goto redo_counts;
498	} else if (fixit == 0)
499		ext2fs_unmark_valid(fs);
500
501	for (i = 0; i < fs->group_desc_count; i++) {
502		if (free_array[i] != fs->group_desc[i].bg_free_inodes_count) {
503			pctx.group = i;
504			pctx.ino = fs->group_desc[i].bg_free_inodes_count;
505			pctx.ino2 = free_array[i];
506			if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP,
507					&pctx)) {
508				fs->group_desc[i].bg_free_inodes_count =
509					free_array[i];
510				ext2fs_mark_super_dirty(fs);
511			} else
512				ext2fs_unmark_valid(fs);
513		}
514		if (dir_array[i] != fs->group_desc[i].bg_used_dirs_count) {
515			pctx.group = i;
516			pctx.ino = fs->group_desc[i].bg_used_dirs_count;
517			pctx.ino2 = dir_array[i];
518
519			if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP,
520					&pctx)) {
521				fs->group_desc[i].bg_used_dirs_count =
522					dir_array[i];
523				ext2fs_mark_super_dirty(fs);
524			} else
525				ext2fs_unmark_valid(fs);
526		}
527	}
528	if (free_inodes != fs->super->s_free_inodes_count) {
529		pctx.group = -1;
530		pctx.ino = fs->super->s_free_inodes_count;
531		pctx.ino2 = free_inodes;
532
533		if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) {
534			fs->super->s_free_inodes_count = free_inodes;
535			ext2fs_mark_super_dirty(fs);
536		} else
537			ext2fs_unmark_valid(fs);
538	}
539errout:
540	ext2fs_free_mem(&free_array);
541	ext2fs_free_mem(&dir_array);
542}
543
544static void check_inode_end(e2fsck_t ctx)
545{
546	ext2_filsys fs = ctx->fs;
547	ext2_ino_t	end, save_inodes_count, i;
548	struct problem_context	pctx;
549
550	clear_problem_context(&pctx);
551
552	end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count;
553	pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end,
554						     &save_inodes_count);
555	if (pctx.errcode) {
556		pctx.num = 1;
557		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
558		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
559		return;
560	}
561	if (save_inodes_count == end)
562		return;
563
564	/* protect loop from wrap-around if end is maxed */
565	for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) {
566		if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) {
567			if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) {
568				for (; i <= end; i++)
569					ext2fs_mark_inode_bitmap(fs->inode_map,
570								 i);
571				ext2fs_mark_ib_dirty(fs);
572			} else
573				ext2fs_unmark_valid(fs);
574			break;
575		}
576	}
577
578	pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map,
579						     save_inodes_count, 0);
580	if (pctx.errcode) {
581		pctx.num = 2;
582		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
583		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
584		return;
585	}
586}
587
588static void check_block_end(e2fsck_t ctx)
589{
590	ext2_filsys fs = ctx->fs;
591	blk_t	end, save_blocks_count, i;
592	struct problem_context	pctx;
593
594	clear_problem_context(&pctx);
595
596	end = ext2fs_get_block_bitmap_start(fs->block_map) +
597		(EXT2_BLOCKS_PER_GROUP(fs->super) * fs->group_desc_count) - 1;
598	pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, end,
599						     &save_blocks_count);
600	if (pctx.errcode) {
601		pctx.num = 3;
602		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
603		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
604		return;
605	}
606	if (save_blocks_count == end)
607		return;
608
609	/* Protect loop from wrap-around if end is maxed */
610	for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) {
611		if (!ext2fs_test_block_bitmap(fs->block_map, i)) {
612			if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) {
613				for (; i <= end; i++)
614					ext2fs_mark_block_bitmap(fs->block_map,
615								 i);
616				ext2fs_mark_bb_dirty(fs);
617			} else
618				ext2fs_unmark_valid(fs);
619			break;
620		}
621	}
622
623	pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map,
624						     save_blocks_count, 0);
625	if (pctx.errcode) {
626		pctx.num = 4;
627		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
628		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
629		return;
630	}
631}
632
633
634
635