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 <stdint.h>
14#include <sys/types.h>
15#include <sys/stat.h>
16#include <sys/ioctl.h>
17#include <fcntl.h>
18#include <errno.h>
19
20#include "e2fsck.h"
21#include "problem.h"
22
23#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
24
25static void check_block_bitmaps(e2fsck_t ctx);
26static void check_inode_bitmaps(e2fsck_t ctx);
27static void check_inode_end(e2fsck_t ctx);
28static void check_block_end(e2fsck_t ctx);
29
30void e2fsck_pass5(e2fsck_t ctx)
31{
32#ifdef RESOURCE_TRACK
33	struct resource_track	rtrack;
34#endif
35	struct problem_context	pctx;
36
37#ifdef MTRACE
38	mtrace_print("Pass 5");
39#endif
40
41	init_resource_track(&rtrack, ctx->fs->io);
42	clear_problem_context(&pctx);
43
44	if (!(ctx->options & E2F_OPT_PREEN))
45		fix_problem(ctx, PR_5_PASS_HEADER, &pctx);
46
47	if (ctx->progress)
48		if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2))
49			return;
50
51	e2fsck_read_bitmaps(ctx);
52
53	check_block_bitmaps(ctx);
54	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
55		return;
56	check_inode_bitmaps(ctx);
57	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
58		return;
59	check_inode_end(ctx);
60	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
61		return;
62	check_block_end(ctx);
63	if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
64		return;
65
66	ext2fs_free_inode_bitmap(ctx->inode_used_map);
67	ctx->inode_used_map = 0;
68	ext2fs_free_inode_bitmap(ctx->inode_dir_map);
69	ctx->inode_dir_map = 0;
70	ext2fs_free_block_bitmap(ctx->block_found_map);
71	ctx->block_found_map = 0;
72
73	print_resource_track(ctx, _("Pass 5"), &rtrack, ctx->fs->io);
74}
75
76static void e2fsck_discard_blocks(e2fsck_t ctx, blk64_t start,
77				  blk64_t count)
78{
79	ext2_filsys fs = ctx->fs;
80
81	/*
82	 * If the filesystem has changed it means that there was an corruption
83	 * which should be repaired, but in some cases just one e2fsck run is
84	 * not enough to fix the problem, hence it is not safe to run discard
85	 * in this case.
86	 */
87	if (ext2fs_test_changed(fs))
88		ctx->options &= ~E2F_OPT_DISCARD;
89
90	if ((ctx->options & E2F_OPT_DISCARD) &&
91	    (io_channel_discard(fs->io, start, count)))
92		ctx->options &= ~E2F_OPT_DISCARD;
93}
94
95/*
96 * This will try to discard number 'count' inodes starting at
97 * inode number 'start' within the 'group'. Note that 'start'
98 * is 1-based, it means that we need to adjust it by -1 in this
99 * function to compute right offset in the particular inode table.
100 */
101static void e2fsck_discard_inodes(e2fsck_t ctx, dgrp_t group,
102				  ext2_ino_t start, int count)
103{
104	ext2_filsys fs = ctx->fs;
105	blk64_t blk, num;
106
107	/*
108	 * Sanity check for 'start'
109	 */
110	if ((start < 1) || (start > EXT2_INODES_PER_GROUP(fs->super))) {
111		printf("PROGRAMMING ERROR: Got start %d outside of group %d!"
112		       " Disabling discard\n",
113			start, group);
114		ctx->options &= ~E2F_OPT_DISCARD;
115	}
116
117	/*
118	 * Do not attempt to discard if E2F_OPT_DISCARD is not set. And also
119	 * skip the discard on this group if discard does not zero data.
120	 * The reason is that if the inode table is not zeroed discard would
121	 * no help us since we need to zero it anyway, or if the inode table
122	 * is zeroed then the read after discard would not be deterministic
123	 * anyway and we would not be able to assume that this inode table
124	 * was zeroed anymore so we would have to zero it again, which does
125	 * not really make sense.
126	 */
127	if (!(ctx->options & E2F_OPT_DISCARD) ||
128	    !io_channel_discard_zeroes_data(fs->io))
129		return;
130
131	/*
132	 * Start is inode number within the group which starts
133	 * counting from 1, so we need to adjust it.
134	 */
135	start -= 1;
136
137	/*
138	 * We can discard only blocks containing only unused
139	 * inodes in the table.
140	 */
141	blk = DIV_ROUND_UP(start,
142		EXT2_INODES_PER_BLOCK(fs->super));
143	count -= (blk * EXT2_INODES_PER_BLOCK(fs->super) - start);
144	blk += ext2fs_inode_table_loc(fs, group);
145	num = count / EXT2_INODES_PER_BLOCK(fs->super);
146
147	if (num > 0)
148		e2fsck_discard_blocks(ctx, blk, num);
149}
150
151#define NO_BLK ((blk64_t) -1)
152
153static void print_bitmap_problem(e2fsck_t ctx, problem_t problem,
154			    struct problem_context *pctx)
155{
156	switch (problem) {
157	case PR_5_BLOCK_UNUSED:
158		if (pctx->blk == pctx->blk2)
159			pctx->blk2 = 0;
160		else
161			problem = PR_5_BLOCK_RANGE_UNUSED;
162		break;
163	case PR_5_BLOCK_USED:
164		if (pctx->blk == pctx->blk2)
165			pctx->blk2 = 0;
166		else
167			problem = PR_5_BLOCK_RANGE_USED;
168		break;
169	case PR_5_INODE_UNUSED:
170		if (pctx->ino == pctx->ino2)
171			pctx->ino2 = 0;
172		else
173			problem = PR_5_INODE_RANGE_UNUSED;
174		break;
175	case PR_5_INODE_USED:
176		if (pctx->ino == pctx->ino2)
177			pctx->ino2 = 0;
178		else
179			problem = PR_5_INODE_RANGE_USED;
180		break;
181	}
182	fix_problem(ctx, problem, pctx);
183	pctx->blk = pctx->blk2 = NO_BLK;
184	pctx->ino = pctx->ino2 = 0;
185}
186
187/* Just to be more succint */
188#define B2C(x)	EXT2FS_B2C(fs, (x))
189#define EQ_CLSTR(x, y) (B2C(x) == B2C(y))
190#define LE_CLSTR(x, y) (B2C(x) <= B2C(y))
191#define GE_CLSTR(x, y) (B2C(x) >= B2C(y))
192
193static void check_block_bitmaps(e2fsck_t ctx)
194{
195	ext2_filsys fs = ctx->fs;
196	blk64_t	i;
197	unsigned int	*free_array;
198	dgrp_t		g, group = 0;
199	unsigned int	blocks = 0;
200	blk64_t	free_blocks = 0;
201	blk64_t first_free = ext2fs_blocks_count(fs->super);
202	unsigned int	group_free = 0;
203	int	actual, bitmap;
204	struct problem_context	pctx;
205	problem_t	problem, save_problem;
206	int		fixit, had_problem;
207	errcode_t	retval;
208	int		csum_flag;
209	int		skip_group = 0;
210	int	old_desc_blocks = 0;
211	int	count = 0;
212	int	cmp_block = 0;
213	int	redo_flag = 0;
214	blk64_t	super_blk, old_desc_blk, new_desc_blk;
215	char *actual_buf, *bitmap_buf;
216
217	actual_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize,
218						     "actual bitmap buffer");
219	bitmap_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize,
220						     "bitmap block buffer");
221
222	clear_problem_context(&pctx);
223	free_array = (unsigned int *) e2fsck_allocate_memory(ctx,
224	    fs->group_desc_count * sizeof(unsigned int), "free block count array");
225
226	if ((B2C(fs->super->s_first_data_block) <
227	     ext2fs_get_block_bitmap_start2(ctx->block_found_map)) ||
228	    (B2C(ext2fs_blocks_count(fs->super)-1) >
229	     ext2fs_get_block_bitmap_end2(ctx->block_found_map))) {
230		pctx.num = 1;
231		pctx.blk = B2C(fs->super->s_first_data_block);
232		pctx.blk2 = B2C(ext2fs_blocks_count(fs->super) - 1);
233		pctx.ino = ext2fs_get_block_bitmap_start2(ctx->block_found_map);
234		pctx.ino2 = ext2fs_get_block_bitmap_end2(ctx->block_found_map);
235		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
236
237		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
238		goto errout;
239	}
240
241	if ((B2C(fs->super->s_first_data_block) <
242	     ext2fs_get_block_bitmap_start2(fs->block_map)) ||
243	    (B2C(ext2fs_blocks_count(fs->super)-1) >
244	     ext2fs_get_block_bitmap_end2(fs->block_map))) {
245		pctx.num = 2;
246		pctx.blk = B2C(fs->super->s_first_data_block);
247		pctx.blk2 = B2C(ext2fs_blocks_count(fs->super) - 1);
248		pctx.ino = ext2fs_get_block_bitmap_start2(fs->block_map);
249		pctx.ino2 = ext2fs_get_block_bitmap_end2(fs->block_map);
250		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
251
252		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
253		goto errout;
254	}
255
256	csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
257					       EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
258redo_counts:
259	had_problem = 0;
260	save_problem = 0;
261	pctx.blk = pctx.blk2 = NO_BLK;
262	if (csum_flag &&
263	    (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT)))
264		skip_group++;
265	for (i = B2C(fs->super->s_first_data_block);
266	     i < ext2fs_blocks_count(fs->super);
267	     i += EXT2FS_CLUSTER_RATIO(fs)) {
268		int first_block_in_bg = (B2C(i) -
269					 B2C(fs->super->s_first_data_block)) %
270			fs->super->s_clusters_per_group == 0;
271		int n, nbytes = fs->super->s_clusters_per_group / 8;
272
273		actual = ext2fs_fast_test_block_bitmap2(ctx->block_found_map, i);
274
275		/*
276		 * Try to optimize pass5 by extracting a bitmap block
277		 * as expected from what we have on disk, and then
278		 * comparing the two.  If they are identical, then
279		 * update the free block counts and go on to the next
280		 * block group.  This is much faster than doing the
281		 * individual bit-by-bit comparison.  The one downside
282		 * is that this doesn't work if we are asking e2fsck
283		 * to do a discard operation.
284		 */
285		if (!first_block_in_bg ||
286		    (group == (int)fs->group_desc_count - 1) ||
287		    (ctx->options & E2F_OPT_DISCARD))
288			goto no_optimize;
289
290		retval = ext2fs_get_block_bitmap_range2(ctx->block_found_map,
291				B2C(i), fs->super->s_clusters_per_group,
292				actual_buf);
293		if (retval)
294			goto no_optimize;
295		if (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT))
296			memset(bitmap_buf, 0, nbytes);
297		else {
298			retval = ext2fs_get_block_bitmap_range2(fs->block_map,
299					B2C(i), fs->super->s_clusters_per_group,
300					bitmap_buf);
301			if (retval)
302				goto no_optimize;
303		}
304		if (memcmp(actual_buf, bitmap_buf, nbytes) != 0)
305			goto no_optimize;
306		n = ext2fs_bitcount(actual_buf, nbytes);
307		group_free = fs->super->s_clusters_per_group - n;
308		free_blocks += group_free;
309		i += EXT2FS_C2B(fs, fs->super->s_clusters_per_group - 1);
310		goto next_group;
311	no_optimize:
312
313		if (skip_group) {
314			if (first_block_in_bg) {
315				super_blk = 0;
316				old_desc_blk = 0;
317				new_desc_blk = 0;
318				ext2fs_super_and_bgd_loc2(fs, group, &super_blk,
319					 &old_desc_blk, &new_desc_blk, 0);
320
321				if (fs->super->s_feature_incompat &
322						EXT2_FEATURE_INCOMPAT_META_BG)
323					old_desc_blocks =
324						fs->super->s_first_meta_bg;
325				else
326					old_desc_blocks = fs->desc_blocks +
327					fs->super->s_reserved_gdt_blocks;
328
329				count = 0;
330				cmp_block = fs->super->s_clusters_per_group;
331				if (group == (int)fs->group_desc_count - 1)
332					cmp_block = EXT2FS_NUM_B2C(fs,
333						    ext2fs_group_blocks_count(fs, group));
334			}
335
336			bitmap = 0;
337			if (EQ_CLSTR(i, super_blk) ||
338			    (old_desc_blk && old_desc_blocks &&
339			     GE_CLSTR(i, old_desc_blk) &&
340			     LE_CLSTR(i, old_desc_blk + old_desc_blocks-1)) ||
341			    (new_desc_blk && EQ_CLSTR(i, new_desc_blk)) ||
342			    EQ_CLSTR(i, ext2fs_block_bitmap_loc(fs, group)) ||
343			    EQ_CLSTR(i, ext2fs_inode_bitmap_loc(fs, group)) ||
344			    (GE_CLSTR(i, ext2fs_inode_table_loc(fs, group)) &&
345			     LE_CLSTR(i, (ext2fs_inode_table_loc(fs, group) +
346					  fs->inode_blocks_per_group - 1)))) {
347				bitmap = 1;
348				actual = (actual != 0);
349				count++;
350				cmp_block--;
351			} else if ((EXT2FS_B2C(fs, i) - count -
352				    EXT2FS_B2C(fs, fs->super->s_first_data_block)) %
353				   fs->super->s_clusters_per_group == 0) {
354				/*
355				 * When the compare data blocks in block bitmap
356				 * are 0, count the free block,
357				 * skip the current block group.
358				 */
359				if (ext2fs_test_block_bitmap_range2(
360					    ctx->block_found_map,
361					    EXT2FS_B2C(fs, i),
362					    cmp_block)) {
363					/*
364					 * -1 means to skip the current block
365					 * group.
366					 */
367					blocks = fs->super->s_clusters_per_group - 1;
368					group_free = cmp_block;
369					free_blocks += cmp_block;
370					/*
371					 * The current block group's last block
372					 * is set to i.
373					 */
374					i += EXT2FS_C2B(fs, cmp_block - 1);
375					bitmap = 1;
376					goto do_counts;
377				}
378			}
379		} else if (redo_flag)
380			bitmap = actual;
381		else
382			bitmap = ext2fs_fast_test_block_bitmap2(fs->block_map, i);
383
384		if (!actual == !bitmap)
385			goto do_counts;
386
387		if (!actual && bitmap) {
388			/*
389			 * Block not used, but marked in use in the bitmap.
390			 */
391			problem = PR_5_BLOCK_UNUSED;
392		} else {
393			/*
394			 * Block used, but not marked in use in the bitmap.
395			 */
396			problem = PR_5_BLOCK_USED;
397
398			if (skip_group) {
399				struct problem_context pctx2;
400				pctx2.blk = i;
401				pctx2.group = group;
402				if (fix_problem(ctx, PR_5_BLOCK_UNINIT,&pctx2)){
403					ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT);
404					skip_group = 0;
405				}
406			}
407		}
408		if (pctx.blk == NO_BLK) {
409			pctx.blk = pctx.blk2 = i;
410			save_problem = problem;
411		} else {
412			if ((problem == save_problem) &&
413			    (pctx.blk2 == i - EXT2FS_CLUSTER_RATIO(fs)))
414				pctx.blk2 += EXT2FS_CLUSTER_RATIO(fs);
415			else {
416				print_bitmap_problem(ctx, save_problem, &pctx);
417				pctx.blk = pctx.blk2 = i;
418				save_problem = problem;
419			}
420		}
421		ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
422		had_problem++;
423
424		/*
425		 * If there a problem we should turn off the discard so we
426		 * do not compromise the filesystem.
427		 */
428		ctx->options &= ~E2F_OPT_DISCARD;
429
430	do_counts:
431		if (!bitmap) {
432			group_free++;
433			free_blocks++;
434			if (first_free > i)
435				first_free = i;
436		} else if (i > first_free) {
437			e2fsck_discard_blocks(ctx, first_free,
438					      (i - first_free));
439			first_free = ext2fs_blocks_count(fs->super);
440		}
441		blocks ++;
442		if ((blocks == fs->super->s_clusters_per_group) ||
443		    (EXT2FS_B2C(fs, i) ==
444		     EXT2FS_B2C(fs, ext2fs_blocks_count(fs->super)-1))) {
445			/*
446			 * If the last block of this group is free, then we can
447			 * discard it as well.
448			 */
449			if (!bitmap && i >= first_free)
450				e2fsck_discard_blocks(ctx, first_free,
451						      (i - first_free) + 1);
452		next_group:
453			first_free = ext2fs_blocks_count(fs->super);
454
455			free_array[group] = group_free;
456			group ++;
457			blocks = 0;
458			group_free = 0;
459			skip_group = 0;
460			if (ctx->progress)
461				if ((ctx->progress)(ctx, 5, group,
462						    fs->group_desc_count*2))
463					goto errout;
464			if (csum_flag &&
465			    (i != ext2fs_blocks_count(fs->super)-1) &&
466			    ext2fs_bg_flags_test(fs, group,
467						EXT2_BG_BLOCK_UNINIT))
468				skip_group++;
469		}
470	}
471	if (pctx.blk != NO_BLK)
472		print_bitmap_problem(ctx, save_problem, &pctx);
473	if (had_problem)
474		fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP);
475	else
476		fixit = -1;
477	ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
478
479	if (fixit == 1) {
480		ext2fs_free_block_bitmap(fs->block_map);
481		retval = ext2fs_copy_bitmap(ctx->block_found_map,
482						  &fs->block_map);
483		if (retval) {
484			clear_problem_context(&pctx);
485			fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx);
486			ctx->flags |= E2F_FLAG_ABORT;
487			goto errout;
488		}
489		ext2fs_set_bitmap_padding(fs->block_map);
490		ext2fs_mark_bb_dirty(fs);
491
492		/* Redo the counts */
493		blocks = 0; free_blocks = 0; group_free = 0; group = 0;
494		memset(free_array, 0, fs->group_desc_count * sizeof(int));
495		redo_flag++;
496		goto redo_counts;
497	} else if (fixit == 0)
498		ext2fs_unmark_valid(fs);
499
500	for (g = 0; g < fs->group_desc_count; g++) {
501		if (free_array[g] != ext2fs_bg_free_blocks_count(fs, g)) {
502			pctx.group = g;
503			pctx.blk = ext2fs_bg_free_blocks_count(fs, g);
504			pctx.blk2 = free_array[g];
505
506			if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP,
507					&pctx)) {
508				ext2fs_bg_free_blocks_count_set(fs, g, free_array[g]);
509				ext2fs_mark_super_dirty(fs);
510			} else
511				ext2fs_unmark_valid(fs);
512		}
513	}
514	free_blocks = EXT2FS_C2B(fs, free_blocks);
515	if (free_blocks != ext2fs_free_blocks_count(fs->super)) {
516		pctx.group = 0;
517		pctx.blk = ext2fs_free_blocks_count(fs->super);
518		pctx.blk2 = free_blocks;
519
520		if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) {
521			ext2fs_free_blocks_count_set(fs->super, free_blocks);
522			ext2fs_mark_super_dirty(fs);
523		}
524	}
525errout:
526	ext2fs_free_mem(&free_array);
527	ext2fs_free_mem(&actual_buf);
528	ext2fs_free_mem(&bitmap_buf);
529}
530
531static void check_inode_bitmaps(e2fsck_t ctx)
532{
533	ext2_filsys fs = ctx->fs;
534	ext2_ino_t	i;
535	unsigned int	free_inodes = 0;
536	int		group_free = 0;
537	int		dirs_count = 0;
538	dgrp_t		group = 0;
539	unsigned int	inodes = 0;
540	ext2_ino_t	*free_array;
541	ext2_ino_t	*dir_array;
542	int		actual, bitmap;
543	errcode_t	retval;
544	struct problem_context	pctx;
545	problem_t	problem, save_problem;
546	int		fixit, had_problem;
547	int		csum_flag;
548	int		skip_group = 0;
549	int		redo_flag = 0;
550	ext2_ino_t		first_free = fs->super->s_inodes_per_group + 1;
551
552	clear_problem_context(&pctx);
553	free_array = (ext2_ino_t *) e2fsck_allocate_memory(ctx,
554	    fs->group_desc_count * sizeof(ext2_ino_t), "free inode count array");
555
556	dir_array = (ext2_ino_t *) e2fsck_allocate_memory(ctx,
557	   fs->group_desc_count * sizeof(ext2_ino_t), "directory count array");
558
559	if ((1 < ext2fs_get_inode_bitmap_start2(ctx->inode_used_map)) ||
560	    (fs->super->s_inodes_count >
561	     ext2fs_get_inode_bitmap_end2(ctx->inode_used_map))) {
562		pctx.num = 3;
563		pctx.blk = 1;
564		pctx.blk2 = fs->super->s_inodes_count;
565		pctx.ino = ext2fs_get_inode_bitmap_start2(ctx->inode_used_map);
566		pctx.ino2 = ext2fs_get_inode_bitmap_end2(ctx->inode_used_map);
567		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
568
569		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
570		goto errout;
571	}
572	if ((1 < ext2fs_get_inode_bitmap_start2(fs->inode_map)) ||
573	    (fs->super->s_inodes_count >
574	     ext2fs_get_inode_bitmap_end2(fs->inode_map))) {
575		pctx.num = 4;
576		pctx.blk = 1;
577		pctx.blk2 = fs->super->s_inodes_count;
578		pctx.ino = ext2fs_get_inode_bitmap_start2(fs->inode_map);
579		pctx.ino2 = ext2fs_get_inode_bitmap_end2(fs->inode_map);
580		fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
581
582		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
583		goto errout;
584	}
585
586	csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
587					       EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
588redo_counts:
589	had_problem = 0;
590	save_problem = 0;
591	pctx.ino = pctx.ino2 = 0;
592	if (csum_flag &&
593	    (ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)))
594		skip_group++;
595
596	/* Protect loop from wrap-around if inodes_count is maxed */
597	for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) {
598		bitmap = 0;
599		if (skip_group &&
600		    i % fs->super->s_inodes_per_group == 1) {
601			/*
602			 * Current inode is the first inode
603			 * in the current block group.
604			 */
605			if (ext2fs_test_inode_bitmap_range(
606				    ctx->inode_used_map, i,
607				    fs->super->s_inodes_per_group)) {
608				/*
609				 * When the compared inodes in inodes bitmap
610				 * are 0, count the free inode,
611				 * skip the current block group.
612				 */
613				first_free = 1;
614				inodes = fs->super->s_inodes_per_group - 1;
615				group_free = inodes;
616				free_inodes += inodes;
617				i += inodes;
618				skip_group = 0;
619				goto do_counts;
620			}
621		}
622
623		actual = ext2fs_fast_test_inode_bitmap2(ctx->inode_used_map, i);
624		if (redo_flag)
625			bitmap = actual;
626		else if (!skip_group)
627			bitmap = ext2fs_fast_test_inode_bitmap2(fs->inode_map, i);
628		if (!actual == !bitmap)
629			goto do_counts;
630
631		if (!actual && bitmap) {
632			/*
633			 * Inode wasn't used, but marked in bitmap
634			 */
635			problem = PR_5_INODE_UNUSED;
636		} else /* if (actual && !bitmap) */ {
637			/*
638			 * Inode used, but not in bitmap
639			 */
640			problem = PR_5_INODE_USED;
641
642			/* We should never hit this, because it means that
643			 * inodes were marked in use that weren't noticed
644			 * in pass1 or pass 2. It is easier to fix the problem
645			 * than to kill e2fsck and leave the user stuck. */
646			if (skip_group) {
647				struct problem_context pctx2;
648				pctx2.blk = i;
649				pctx2.group = group;
650				if (fix_problem(ctx, PR_5_INODE_UNINIT,&pctx2)){
651					ext2fs_bg_flags_clear(fs, group, EXT2_BG_INODE_UNINIT);
652					skip_group = 0;
653				}
654			}
655		}
656		if (pctx.ino == 0) {
657			pctx.ino = pctx.ino2 = i;
658			save_problem = problem;
659		} else {
660			if ((problem == save_problem) &&
661			    (pctx.ino2 == i-1))
662				pctx.ino2++;
663			else {
664				print_bitmap_problem(ctx, save_problem, &pctx);
665				pctx.ino = pctx.ino2 = i;
666				save_problem = problem;
667			}
668		}
669		ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
670		had_problem++;
671		/*
672		 * If there a problem we should turn off the discard so we
673		 * do not compromise the filesystem.
674		 */
675		ctx->options &= ~E2F_OPT_DISCARD;
676
677do_counts:
678		inodes++;
679		if (bitmap) {
680			if (ext2fs_test_inode_bitmap2(ctx->inode_dir_map, i))
681				dirs_count++;
682			if (inodes > first_free) {
683				e2fsck_discard_inodes(ctx, group, first_free,
684						      inodes - first_free);
685				first_free = fs->super->s_inodes_per_group + 1;
686			}
687		} else {
688			group_free++;
689			free_inodes++;
690			if (first_free > inodes)
691				first_free = inodes;
692		}
693
694		if ((inodes == fs->super->s_inodes_per_group) ||
695		    (i == fs->super->s_inodes_count)) {
696			/*
697			 * If the last inode is free, we can discard it as well.
698			 */
699			if (!bitmap && inodes >= first_free)
700				e2fsck_discard_inodes(ctx, group, first_free,
701						      inodes - first_free + 1);
702			/*
703			 * If discard zeroes data and the group inode table
704			 * was not zeroed yet, set itable as zeroed
705			 */
706			if ((ctx->options & E2F_OPT_DISCARD) &&
707			    io_channel_discard_zeroes_data(fs->io) &&
708			    !(ext2fs_bg_flags_test(fs, group,
709						   EXT2_BG_INODE_ZEROED))) {
710				ext2fs_bg_flags_set(fs, group,
711						    EXT2_BG_INODE_ZEROED);
712				ext2fs_group_desc_csum_set(fs, group);
713			}
714
715			first_free = fs->super->s_inodes_per_group + 1;
716			free_array[group] = group_free;
717			dir_array[group] = dirs_count;
718			group ++;
719			inodes = 0;
720			skip_group = 0;
721			group_free = 0;
722			dirs_count = 0;
723			if (ctx->progress)
724				if ((ctx->progress)(ctx, 5,
725					    group + fs->group_desc_count,
726					    fs->group_desc_count*2))
727					goto errout;
728			if (csum_flag &&
729			    (i != fs->super->s_inodes_count) &&
730			    (ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)
731			     ))
732				skip_group++;
733		}
734	}
735	if (pctx.ino)
736		print_bitmap_problem(ctx, save_problem, &pctx);
737
738	if (had_problem)
739		fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP);
740	else
741		fixit = -1;
742	ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
743
744	if (fixit == 1) {
745		ext2fs_free_inode_bitmap(fs->inode_map);
746		retval = ext2fs_copy_bitmap(ctx->inode_used_map,
747						  &fs->inode_map);
748		if (retval) {
749			clear_problem_context(&pctx);
750			fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx);
751			ctx->flags |= E2F_FLAG_ABORT;
752			goto errout;
753		}
754		ext2fs_set_bitmap_padding(fs->inode_map);
755		ext2fs_mark_ib_dirty(fs);
756
757		/* redo counts */
758		inodes = 0; free_inodes = 0; group_free = 0;
759		dirs_count = 0; group = 0;
760		memset(free_array, 0, fs->group_desc_count * sizeof(int));
761		memset(dir_array, 0, fs->group_desc_count * sizeof(int));
762		redo_flag++;
763		goto redo_counts;
764	} else if (fixit == 0)
765		ext2fs_unmark_valid(fs);
766
767	for (i = 0; i < fs->group_desc_count; i++) {
768		if (free_array[i] != ext2fs_bg_free_inodes_count(fs, i)) {
769			pctx.group = i;
770			pctx.ino = ext2fs_bg_free_inodes_count(fs, i);
771			pctx.ino2 = free_array[i];
772			if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP,
773					&pctx)) {
774				ext2fs_bg_free_inodes_count_set(fs, i, free_array[i]);
775				ext2fs_mark_super_dirty(fs);
776			} else
777				ext2fs_unmark_valid(fs);
778		}
779		if (dir_array[i] != ext2fs_bg_used_dirs_count(fs, i)) {
780			pctx.group = i;
781			pctx.ino = ext2fs_bg_used_dirs_count(fs, i);
782			pctx.ino2 = dir_array[i];
783
784			if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP,
785					&pctx)) {
786				ext2fs_bg_used_dirs_count_set(fs, i, dir_array[i]);
787				ext2fs_mark_super_dirty(fs);
788			} else
789				ext2fs_unmark_valid(fs);
790		}
791	}
792	if (free_inodes != fs->super->s_free_inodes_count) {
793		pctx.group = -1;
794		pctx.ino = fs->super->s_free_inodes_count;
795		pctx.ino2 = free_inodes;
796
797		if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) {
798			fs->super->s_free_inodes_count = free_inodes;
799			ext2fs_mark_super_dirty(fs);
800		}
801	}
802errout:
803	ext2fs_free_mem(&free_array);
804	ext2fs_free_mem(&dir_array);
805}
806
807static void check_inode_end(e2fsck_t ctx)
808{
809	ext2_filsys fs = ctx->fs;
810	ext2_ino_t	end, save_inodes_count, i;
811	struct problem_context	pctx;
812
813	clear_problem_context(&pctx);
814
815	end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count;
816	pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end,
817						     &save_inodes_count);
818	if (pctx.errcode) {
819		pctx.num = 1;
820		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
821		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
822		return;
823	}
824	if (save_inodes_count == end)
825		return;
826
827	/* protect loop from wrap-around if end is maxed */
828	for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) {
829		if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) {
830			if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) {
831				for (; i <= end; i++)
832					ext2fs_mark_inode_bitmap(fs->inode_map,
833								 i);
834				ext2fs_mark_ib_dirty(fs);
835			} else
836				ext2fs_unmark_valid(fs);
837			break;
838		}
839	}
840
841	pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map,
842						     save_inodes_count, 0);
843	if (pctx.errcode) {
844		pctx.num = 2;
845		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
846		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
847		return;
848	}
849}
850
851static void check_block_end(e2fsck_t ctx)
852{
853	ext2_filsys fs = ctx->fs;
854	blk64_t	end, save_blocks_count, i;
855	struct problem_context	pctx;
856
857	clear_problem_context(&pctx);
858
859	end = ext2fs_get_block_bitmap_start2(fs->block_map) +
860		((blk64_t)EXT2_CLUSTERS_PER_GROUP(fs->super) * fs->group_desc_count) - 1;
861	pctx.errcode = ext2fs_fudge_block_bitmap_end2(fs->block_map, end,
862						     &save_blocks_count);
863	if (pctx.errcode) {
864		pctx.num = 3;
865		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
866		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
867		return;
868	}
869	if (save_blocks_count == end)
870		return;
871
872	/* Protect loop from wrap-around if end is maxed */
873	for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) {
874		if (!ext2fs_test_block_bitmap2(fs->block_map,
875					       EXT2FS_C2B(fs, i))) {
876			if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) {
877				for (; i <= end; i++)
878					ext2fs_mark_block_bitmap2(fs->block_map,
879							EXT2FS_C2B(fs, i));
880				ext2fs_mark_bb_dirty(fs);
881			} else
882				ext2fs_unmark_valid(fs);
883			break;
884		}
885	}
886
887	pctx.errcode = ext2fs_fudge_block_bitmap_end2(fs->block_map,
888						     save_blocks_count, 0);
889	if (pctx.errcode) {
890		pctx.num = 4;
891		fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
892		ctx->flags |= E2F_FLAG_ABORT; /* fatal */
893		return;
894	}
895}
896
897
898
899