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