1/* $NetBSD$ */ 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$"); 35#endif /* not lint */ 36 37#include <stdio.h> 38#include <stdbool.h> 39 40#include "v7fs.h" 41#include "v7fs_endian.h" 42#include "v7fs_superblock.h" 43#include "v7fs_inode.h" 44#include "v7fs_impl.h" 45#include "v7fs_datablock.h" 46#include "v7fs_file.h" 47#include "fsck_v7fs.h" 48 49static void datablock_dup_remove(struct v7fs_self *, v7fs_ino_t, v7fs_ino_t, 50 v7fs_daddr_t); 51 52struct loop_context { 53 v7fs_ino_t i; 54 v7fs_ino_t j; 55 v7fs_daddr_t blk; 56}; 57 58/* 59 * datablock vs freeblock 60 */ 61static int 62freeblock_subr(struct v7fs_self *fs, void *ctx, v7fs_daddr_t freeblk) 63{ 64 struct loop_context *arg = (struct loop_context *)ctx; 65 66 progress(0); 67 if (arg->blk == freeblk) { 68 pwarn("*** ino%d(%s) data block %d found at freeblock", 69 arg->i, filename(fs, arg->i), freeblk); 70 if (reply("CORRECT?")) { 71 freeblock_dup_remove(fs, freeblk); 72 return V7FS_ITERATOR_ERROR; /* Rescan needed. */ 73 } 74 } 75 76 return 0; 77} 78 79static int 80datablock_subr(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk, 81 size_t sz __unused) 82{ 83 struct loop_context *arg = (struct loop_context *)ctx; 84 int ret; 85 86 arg->blk = blk; 87 if ((ret = v7fs_freeblock_foreach(fs, freeblock_subr, ctx)) == 88 V7FS_ITERATOR_ERROR) 89 return ret; 90 91 return 0; 92} 93 94static int 95inode_subr(struct v7fs_self *fs, void *ctx, struct v7fs_inode *p, 96 v7fs_ino_t ino) 97{ 98 struct loop_context *arg = (struct loop_context *)ctx; 99 int ret; 100 101 arg->i = ino; 102 103 if ((ret = v7fs_datablock_foreach(fs, p, datablock_subr, ctx)) == 104 V7FS_ITERATOR_ERROR) 105 return ret; 106 107 return 0; 108} 109 110int 111datablock_vs_freeblock_check(struct v7fs_self *fs) 112{ 113 struct v7fs_superblock *sb = &fs->superblock; 114 int nfree = sb->total_freeblock; 115 int ndata = sb->volume_size - sb->datablock_start_sector - nfree; 116 int ret; 117 118 progress(&(struct progress_arg){ .label = "data-free", .tick = (ndata / 119 PROGRESS_BAR_GRANULE) * nfree }); 120 121 if ((ret = v7fs_ilist_foreach(fs, inode_subr, &(struct loop_context) 122 { .i = 0, .blk = 0 })) == V7FS_ITERATOR_ERROR) 123 return FSCK_EXIT_UNRESOLVED; 124 125 return 0; 126} 127 128 129/* 130 * datablock vs datablock 131 */ 132static int 133datablock_i_j(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk, size_t sz 134 __unused) 135{ 136 struct loop_context *arg = (struct loop_context *)ctx; 137 138 progress(0); 139 if (blk == arg->blk) { 140 pwarn("*** duplicated block found." 141 "#%d(%s) and #%d(%s) refer block %d", 142 arg->i, filename(fs, arg->i), 143 arg->j, filename(fs, arg->j), blk); 144 if (reply("CORRECT?")) { 145 datablock_dup_remove(fs, arg->i, arg->j, blk); 146 return V7FS_ITERATOR_ERROR; /* Rescan needed. */ 147 } 148 } 149 150 return 0; 151} 152 153static int 154loopover_j(struct v7fs_self *fs, void *ctx, struct v7fs_inode *p, 155 v7fs_ino_t ino) 156{ 157 struct loop_context *arg = (struct loop_context *)ctx; 158 int ret; 159 160 arg->j = ino; 161 162 if (arg->j >= arg->i) 163 return V7FS_ITERATOR_BREAK; 164 165 if ((ret = v7fs_datablock_foreach(fs, p, datablock_i_j, ctx)) == 166 V7FS_ITERATOR_ERROR) 167 return V7FS_ITERATOR_ERROR; 168 169 return 0; 170} 171 172static int 173datablock_i(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk, 174 size_t sz __unused) 175{ 176 struct loop_context *arg = (struct loop_context *)ctx; 177 int ret; 178 179 arg->blk = blk; 180 181 if ((ret = v7fs_ilist_foreach(fs, loopover_j, ctx)) == 182 V7FS_ITERATOR_ERROR) 183 return V7FS_ITERATOR_ERROR; 184 185 return 0; 186} 187 188static int 189loopover_i(struct v7fs_self *fs, void *ctx, struct v7fs_inode *inode, 190 v7fs_ino_t ino) 191{ 192 struct loop_context *arg = (struct loop_context *)ctx; 193 int ret; 194 195 arg->i = ino; 196 197 if ((ret = v7fs_datablock_foreach(fs, inode, datablock_i, ctx)) == 198 V7FS_ITERATOR_ERROR) 199 return V7FS_ITERATOR_ERROR; 200 201 return 0; 202} 203 204 205int 206datablock_vs_datablock_check(struct v7fs_self *fs) 207{ 208 const struct v7fs_superblock *sb = &fs->superblock; 209 int n = sb->volume_size - sb->total_freeblock; 210 int ret; 211 212 progress(&(struct progress_arg){ .label = "data-data", .tick = (n / 2) 213 * ((n - 1) / PROGRESS_BAR_GRANULE) }); 214 215 if ((ret = v7fs_ilist_foreach(fs, loopover_i, &(struct loop_context){ 216 .i = 0, .j = 0 })) == V7FS_ITERATOR_ERROR) 217 return FSCK_EXIT_UNRESOLVED; 218 219 return 0; 220} 221 222/* 223 * Remove duplicated block. 224 */ 225static void 226copy_block(struct v7fs_self *fs, v7fs_daddr_t dst, v7fs_daddr_t src) 227{ 228 void *buf; 229 230 if (!(buf = scratch_read(fs, src))) 231 return; 232 fs->io.write(fs->io.cookie, buf, dst); 233 scratch_free(fs, buf); 234 235 pwarn("copy block %d->%d\n", src, dst); 236} 237 238static void 239replace_block_direct(struct v7fs_self *fs, struct v7fs_inode *p, int dupidx, 240 v7fs_daddr_t newblk) 241{ 242 v7fs_daddr_t oldblk; 243 244 oldblk = p->addr[dupidx]; 245 p->addr[dupidx] = newblk; 246 v7fs_inode_writeback(fs, p); /* endian conversion done by here. */ 247 248 copy_block(fs, newblk, oldblk); 249} 250 251static void 252prepare_list(struct v7fs_self *fs, v7fs_daddr_t listblk, v7fs_daddr_t *p) 253{ 254 size_t i; 255 256 fs->io.read(fs->io.cookie, (void *)p, listblk); 257 for (i = 0; i < V7FS_DADDR_PER_BLOCK; i++) 258 p[i] = V7FS_VAL32(fs, p[i]); 259} 260 261static void 262replace_block_indexed(struct v7fs_self *fs, v7fs_daddr_t listblk, int dupidx, 263 v7fs_daddr_t newblk) 264{ 265 void *buf; 266 v7fs_daddr_t *list; 267 v7fs_daddr_t oldblk; 268 269 if (!(buf = scratch_read(fs, listblk))) 270 return; 271 list = (v7fs_daddr_t *)buf; 272 oldblk = V7FS_VAL32(fs, list[dupidx]); 273 list[dupidx] = V7FS_VAL32(fs, newblk); 274 fs->io.write(fs->io.cookie, buf, listblk); 275 scratch_free(fs, buf); 276 277 copy_block(fs, newblk, oldblk); 278 pwarn("dup block replaced by %d\n", newblk); 279} 280 281static bool 282dupfind_loop1(struct v7fs_self *fs, v7fs_daddr_t listblk, v7fs_daddr_t dupblk, 283 v7fs_daddr_t newblk) 284{ 285 v7fs_daddr_t list[V7FS_DADDR_PER_BLOCK]; 286 size_t i; 287 288 prepare_list(fs, listblk, list); 289 for (i = 0; i < V7FS_DADDR_PER_BLOCK; i++) { 290 if (list[i] == dupblk) { 291 replace_block_indexed(fs, listblk, i, newblk); 292 return true; 293 } 294 } 295 296 return false; 297} 298 299static bool 300dupfind_loop2(struct v7fs_self *fs, v7fs_daddr_t listblk, v7fs_daddr_t dupblk, 301 v7fs_daddr_t newblk) 302{ 303 v7fs_daddr_t list[V7FS_DADDR_PER_BLOCK]; 304 v7fs_daddr_t blk; 305 size_t i; 306 307 prepare_list(fs, listblk, list); 308 for (i = 0; i < V7FS_DADDR_PER_BLOCK; i++) { 309 if ((blk = list[i]) == dupblk) { 310 replace_block_indexed(fs, listblk, i, newblk); 311 return true; 312 } 313 if (dupfind_loop1(fs, blk, dupblk, newblk)) 314 return true; 315 } 316 317 return false; 318} 319 320static void 321do_replace(struct v7fs_self *fs, struct v7fs_inode *p, v7fs_daddr_t dupblk, 322 v7fs_daddr_t newblk) 323{ 324 size_t i; 325 v7fs_daddr_t blk, blk2; 326 v7fs_daddr_t list[V7FS_DADDR_PER_BLOCK]; 327 328 /* Direct */ 329 for (i = 0; i < V7FS_NADDR_DIRECT; i++) { 330 if (p->addr[i] == dupblk) { 331 replace_block_direct(fs, p, i, newblk); 332 return; 333 } 334 } 335 336 /* Index 1 */ 337 if ((blk = p->addr[V7FS_NADDR_INDEX1]) == dupblk) { 338 replace_block_direct(fs, p, V7FS_NADDR_INDEX1, newblk); 339 return; 340 } 341 if (dupfind_loop1(fs, blk, dupblk, newblk)) 342 return; 343 344 /* Index 2 */ 345 if ((blk = p->addr[V7FS_NADDR_INDEX2]) == dupblk) { 346 replace_block_direct(fs, p, V7FS_NADDR_INDEX2, newblk); 347 return; 348 } 349 if (dupfind_loop2(fs, blk, dupblk, newblk)) 350 return; 351 352 /* Index 3 */ 353 if ((blk = p->addr[V7FS_NADDR_INDEX3]) == dupblk) { 354 replace_block_direct(fs, p, V7FS_NADDR_INDEX3, newblk); 355 return; 356 } 357 prepare_list(fs, blk, list); 358 for (i = 0; i < V7FS_DADDR_PER_BLOCK; i++) { 359 if ((blk2 = list[i]) == dupblk) { 360 replace_block_indexed(fs, blk, i, newblk); 361 return; 362 } 363 if (dupfind_loop2(fs, blk2, dupblk, newblk)) 364 return; 365 } 366} 367 368static void 369datablock_dup_remove(struct v7fs_self *fs, v7fs_ino_t i, v7fs_ino_t j, 370 v7fs_daddr_t dupblk) 371{ 372 struct v7fs_inode inode; 373 v7fs_ino_t victim; 374 v7fs_daddr_t newblk; 375 int error; 376 377 pwarn("Is victim %s (%s is preserved)", filename(fs, i), 378 filename(fs, j)); 379 if (reply("?")) { 380 victim = i; 381 } else { 382 pwarn("Is victim %s (%s is preserved)", 383 filename(fs, j), filename(fs, i)); 384 if (reply("?")) { 385 victim = j; 386 } else { 387 pwarn("Don't correct.\n"); 388 return; 389 } 390 } 391 392 if ((error = v7fs_inode_load(fs, &inode, victim))) 393 return; 394 395 /* replace block. */ 396 if ((error = v7fs_datablock_allocate(fs, &newblk))) { 397 pwarn("Can't allocate substitute block."); 398 return; 399 } 400 401 do_replace(fs, &inode, dupblk, newblk); 402} 403 404