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
freeblock_subr(struct v7fs_self * fs,void * ctx,v7fs_daddr_t freeblk)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
datablock_subr(struct v7fs_self * fs,void * ctx,v7fs_daddr_t blk,size_t sz __unused)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
inode_subr(struct v7fs_self * fs,void * ctx,struct v7fs_inode * p,v7fs_ino_t ino)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
datablock_vs_freeblock_check(struct v7fs_self * fs)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
datablock_i_j(struct v7fs_self * fs,void * ctx,v7fs_daddr_t blk,size_t sz __unused)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
loopover_j(struct v7fs_self * fs,void * ctx,struct v7fs_inode * p,v7fs_ino_t ino)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
datablock_i(struct v7fs_self * fs,void * ctx,v7fs_daddr_t blk,size_t sz __unused)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
loopover_i(struct v7fs_self * fs,void * ctx,struct v7fs_inode * inode,v7fs_ino_t ino)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
datablock_vs_datablock_check(struct v7fs_self * fs)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
copy_block(struct v7fs_self * fs,v7fs_daddr_t dst,v7fs_daddr_t src)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
replace_block_direct(struct v7fs_self * fs,struct v7fs_inode * p,int dupidx,v7fs_daddr_t newblk)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
prepare_list(struct v7fs_self * fs,v7fs_daddr_t listblk,v7fs_daddr_t * p)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
replace_block_indexed(struct v7fs_self * fs,v7fs_daddr_t listblk,int dupidx,v7fs_daddr_t newblk)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
dupfind_loop1(struct v7fs_self * fs,v7fs_daddr_t listblk,v7fs_daddr_t dupblk,v7fs_daddr_t newblk)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
dupfind_loop2(struct v7fs_self * fs,v7fs_daddr_t listblk,v7fs_daddr_t dupblk,v7fs_daddr_t newblk)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
do_replace(struct v7fs_self * fs,struct v7fs_inode * p,v7fs_daddr_t dupblk,v7fs_daddr_t newblk)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
datablock_dup_remove(struct v7fs_self * fs,v7fs_ino_t i,v7fs_ino_t j,v7fs_daddr_t dupblk)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