1 /* $NetBSD: datablock.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: datablock.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 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 49 static void datablock_dup_remove(struct v7fs_self *, v7fs_ino_t, v7fs_ino_t, 50 v7fs_daddr_t); 51 52 struct 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 */ 61 static int 62 freeblock_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 79 static int 80 datablock_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 94 static int 95 inode_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 110 int 111 datablock_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 */ 132 static int 133 datablock_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 153 static int 154 loopover_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 172 static int 173 datablock_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 188 static int 189 loopover_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 205 int 206 datablock_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 */ 225 static void 226 copy_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 238 static void 239 replace_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 251 static void 252 prepare_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 261 static void 262 replace_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 281 static bool 282 dupfind_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 299 static bool 300 dupfind_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 320 static void 321 do_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 368 static void 369 datablock_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