Home | History | Annotate | Line # | Download | only in fsck_v7fs 
      1 /*	$NetBSD: freeblock.c,v 1.2 2011/07/17 12:47:38 uch Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2011 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by UCHIYAMA Yasushi.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     29  * POSSIBILITY OF SUCH DAMAGE.
     30  */
     31 
     32 #include <sys/cdefs.h>
     33 #ifndef lint
     34 __RCSID("$NetBSD: freeblock.c,v 1.2 2011/07/17 12:47:38 uch Exp $");
     35 #endif /* not lint */
     36 
     37 #include <stdio.h>
     38 #include <stdbool.h>
     39 #include <string.h>
     40 
     41 #include "v7fs.h"
     42 #include "v7fs_superblock.h"
     43 #include "v7fs_inode.h"
     44 #include "v7fs_impl.h"
     45 #include "v7fs_datablock.h"
     46 #include "fsck_v7fs.h"
     47 
     48 struct freeblock_arg {
     49 	v7fs_daddr_t i;
     50 	v7fs_daddr_t j;
     51 	v7fs_daddr_t blk;
     52 };
     53 
     54 static int
     55 freeblock_subr_cnt(struct v7fs_self *fs __unused, void *ctx,
     56     v7fs_daddr_t blk __unused)
     57 {
     58 	((struct freeblock_arg *)ctx)->blk++;
     59 	progress(0);
     60 
     61 	return 0;
     62 }
     63 
     64 static int
     65 freeblock_subr_j(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk)
     66 {
     67 	struct freeblock_arg *arg = (struct freeblock_arg *)ctx;
     68 
     69 	if (!datablock_number_sanity(fs, blk)) {
     70 		pwarn("invalid block#%d in freeblock", blk);
     71 		/* This problem should be fixed at freeblock_check(). */
     72 		return FSCK_EXIT_CHECK_FAILED;
     73 	}
     74 
     75 	if (arg->j >= arg->i)
     76 		return V7FS_ITERATOR_BREAK;
     77 
     78 	progress(0);
     79 
     80 	if (arg->blk == blk) {
     81 		pwarn("freeblock duplicate %d %d blk=%d", arg->i, arg->j, blk);
     82 		if (reply("CORRECT?")) {
     83 			freeblock_dup_remove(fs, blk);
     84 		}
     85 		return FSCK_EXIT_UNRESOLVED; /* Rescan needed. */
     86 	}
     87 
     88 	arg->j++;
     89 
     90 	return 0;	/*continue */
     91 }
     92 
     93 static int
     94 freeblock_subr_i(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk)
     95 {
     96 	struct freeblock_arg *arg = (struct freeblock_arg *)ctx;
     97 	int ret;
     98 
     99 	if (!datablock_number_sanity(fs, blk)) {
    100 		pwarn("invalid block#%d in freeblock", blk);
    101 		/* This problem should be fixed at freeblock_check(). */
    102 		return FSCK_EXIT_CHECK_FAILED;
    103 	}
    104 
    105 	arg->j = 0;
    106 	arg->blk = blk;
    107 	ret = v7fs_freeblock_foreach(fs, freeblock_subr_j, ctx);
    108 	if (!((ret == 0) || (ret == V7FS_ITERATOR_BREAK)))
    109 		return ret;
    110 
    111 	arg->i++;
    112 
    113 	return 0;
    114 }
    115 
    116 int
    117 freeblock_vs_freeblock_check(struct v7fs_self *fs)
    118 {
    119 	struct v7fs_superblock *sb = &fs->superblock;
    120 	int n = sb->total_freeblock;
    121 
    122 	progress(&(struct progress_arg){ .label = "free-free", .tick = (n / 2)
    123 	    * ((n - 1) / PROGRESS_BAR_GRANULE) });
    124 
    125 	return v7fs_freeblock_foreach(fs, freeblock_subr_i,
    126 	    &(struct freeblock_arg){ .i = 0 });
    127 }
    128 
    129 /*
    130  * Remove duplicated block.
    131  */
    132 void
    133 freeblock_dup_remove(struct v7fs_self *fs, v7fs_daddr_t dupblk)
    134 {
    135 	struct v7fs_superblock *sb = &fs->superblock;
    136 	struct v7fs_freeblock *fb;
    137 	int i, total, n;
    138 	void *buf;
    139 	v7fs_daddr_t blk;
    140 
    141 	n = sb->total_freeblock;
    142 
    143 	/* Superblock cache. */
    144 	total = 0;
    145 	for (i = sb->nfreeblock - 1; (i > 0) && (n >= 0); i--, n--, total++) {
    146 		if (sb->freeblock[i] == dupblk) {      /* Duplicate found. */
    147 			memmove(sb->freeblock + i, sb->freeblock + i + 1,
    148 			    sb->nfreeblock - 1 - i);
    149 			sb->nfreeblock--;
    150 			sb->modified = 1;
    151 			v7fs_superblock_writeback(fs);
    152 			pwarn("remove duplicated freeblock %d"
    153 			    "from superblock", dupblk);
    154 			return;
    155 		}
    156 	}
    157 	if (!n)
    158 		return;
    159 	blk = sb->freeblock[0];
    160 
    161 	do {
    162 		if (!blk)
    163 			break;
    164 		buf = scratch_read(fs, blk);
    165 		fb = (struct v7fs_freeblock *)buf;
    166 		v7fs_freeblock_endian_convert(fs, fb);
    167 
    168 		if (blk == dupblk) {
    169 			/* This is difficult probrem. give up! */
    170 			/* or newly allocate block, and copy it and link. */
    171 			pwarn("duplicated block is freeblock list."
    172 			    "Shortage freeblock %d->%d.",
    173 			    sb->nfreeblock, total);
    174 			sb->nfreeblock = total; /*shotage freeblock list. */
    175 			sb->modified = 1;
    176 			v7fs_superblock_writeback(fs);
    177 			return;
    178 		}
    179 		total++;
    180 
    181 		blk = fb->freeblock[0]; /* next freeblock list */
    182 
    183 		for (i = fb->nfreeblock - 1; (i > 0) && (n >= 0);
    184 		    i--, n--, total++) {
    185 			if (fb->freeblock[i] == dupblk)	{
    186 				pwarn("remove duplicated freeblock"
    187 				    "%d from list %d", dupblk, blk);
    188 				memmove(fb->freeblock + i, fb->freeblock + i +
    189 				    1, fb->nfreeblock - 1 - i);
    190 				/* Writeback superblock. */
    191 				sb->nfreeblock--;
    192 				sb->modified = 1;
    193 				v7fs_superblock_writeback(fs);
    194 				/* Writeback freeblock list block. */
    195 				v7fs_freeblock_endian_convert(fs, fb);
    196 				fs->io.write(fs->io.cookie, buf, blk);
    197 				return;
    198 			}
    199 		}
    200 		scratch_free(fs, buf);
    201 	} while (n);
    202 
    203 	return;
    204 }
    205 
    206 int
    207 v7fs_freeblock_foreach(struct v7fs_self *fs,
    208     int (*func)(struct v7fs_self *, void *, v7fs_daddr_t), void *ctx)
    209 {
    210 	struct v7fs_superblock *sb = &fs->superblock;
    211 	struct v7fs_freeblock *fb;
    212 	int i, n;
    213 	void *buf;
    214 	v7fs_daddr_t blk;
    215 	int ret;
    216 
    217 	n = sb->total_freeblock;
    218 
    219 	/* Superblock cache. */
    220 	for (i = sb->nfreeblock - 1; (i > 0) && (n >= 0); i--, n--) {
    221 		if ((ret = func(fs, ctx, sb->freeblock[i])))
    222 			return ret;
    223 	}
    224 	if (!n)
    225 		return 0;
    226 	blk = sb->freeblock[0];
    227 	if (!datablock_number_sanity(fs, blk)) {
    228 		pwarn("invalid freeblock list block#%d.", blk);
    229 		return 0;
    230 	}
    231 	do {
    232 		if (!blk)
    233 			break;
    234 		if (!(buf = scratch_read(fs, blk)))
    235 			return 0;
    236 		fb = (struct v7fs_freeblock *)buf;
    237 
    238 		if (v7fs_freeblock_endian_convert(fs, fb)) {
    239 			pwarn("***corrupt freeblock list blk#%d", blk);
    240 			return 0;
    241 		}
    242 
    243 		/* freeblock list is used as freeblock. */
    244 		n--;
    245 		if ((ret = func(fs, ctx, blk)))
    246 			return ret;
    247 
    248 		blk = fb->freeblock[0]; /* next freeblock list */
    249 
    250 		for (i = fb->nfreeblock - 1; (i > 0) && (n >= 0); i--, n--)
    251 			if ((ret = func(fs, ctx, fb->freeblock[i]))) {
    252 				scratch_free(fs, buf);
    253 				return ret;
    254 			}
    255 		scratch_free(fs, buf);
    256 	} while (n);
    257 
    258 	return 0;
    259 }
    260 
    261 int
    262 freeblock_check(struct v7fs_self *fs)
    263 {
    264 	struct v7fs_superblock *sb = &fs->superblock;
    265 	struct freeblock_arg freeblock_arg = { .blk = 0 };
    266 	v7fs_daddr_t blk;
    267 	v7fs_daddr_t datablock_size = sb->volume_size -
    268 	    sb->datablock_start_sector;
    269 	int error = 0;
    270 	struct progress_arg progress_arg = { .label = "freeblock", .tick =
    271 	    sb->total_freeblock / PROGRESS_BAR_GRANULE };
    272 
    273 	progress(&progress_arg);
    274 	v7fs_freeblock_foreach(fs, freeblock_subr_cnt, &freeblock_arg);
    275 	progress(&progress_arg);
    276 
    277 	blk = freeblock_arg.blk;
    278 	pwarn("\ndatablock usage: %d/%d (%d)\n",  datablock_size - blk,
    279 	    datablock_size, blk);
    280 
    281 	if (sb->total_freeblock != blk) {
    282 		pwarn("corrupt # of freeblocks. %d(sb) != %d(cnt)",
    283 		    sb->total_freeblock, blk);
    284 		if (reply_trivial("CORRECT?")) {
    285 			sb->total_freeblock = blk;
    286 			sb->modified = 1;
    287 			v7fs_superblock_writeback(fs);
    288 		} else {
    289 			error = FSCK_EXIT_CHECK_FAILED;
    290 		}
    291 	}
    292 
    293 
    294 	return error;
    295 }
    296