1/* $NetBSD: freeblock.c,v 1.1 2011/06/27 11:52:58 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.1 2011/06/27 11:52:58 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 48struct freeblock_arg { 49 v7fs_daddr_t i; 50 v7fs_daddr_t j; 51 v7fs_daddr_t blk; 52}; 53 54static int 55freeblock_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 64static int 65freeblock_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 93static int 94freeblock_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 116int 117freeblock_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 */ 132void 133freeblock_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 206int 207v7fs_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 261int 262freeblock_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