1 /* $NetBSD: freeblock.c,v 1.2 2011/07/17 12:47:38 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.2 2011/07/17 12:47:38 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
48 struct freeblock_arg {
49 v7fs_daddr_t i;
50 v7fs_daddr_t j;
51 v7fs_daddr_t blk;
52 };
53
54 static int
freeblock_subr_cnt(struct v7fs_self * fs __unused,void * ctx,v7fs_daddr_t blk __unused)55 freeblock_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
64 static int
freeblock_subr_j(struct v7fs_self * fs,void * ctx,v7fs_daddr_t blk)65 freeblock_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
93 static int
freeblock_subr_i(struct v7fs_self * fs,void * ctx,v7fs_daddr_t blk)94 freeblock_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
116 int
freeblock_vs_freeblock_check(struct v7fs_self * fs)117 freeblock_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 */
132 void
freeblock_dup_remove(struct v7fs_self * fs,v7fs_daddr_t dupblk)133 freeblock_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
206 int
v7fs_freeblock_foreach(struct v7fs_self * fs,int (* func)(struct v7fs_self *,void *,v7fs_daddr_t),void * ctx)207 v7fs_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
261 int
freeblock_check(struct v7fs_self * fs)262 freeblock_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