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