xref: /freebsd/sbin/fsck_ffs/pass5.c (revision 1e413cf93298b5b97441a21d9a50fdcd0ee9945e)
1 /*
2  * Copyright (c) 1980, 1986, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 4. Neither the name of the University nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 
30 #if 0
31 #ifndef lint
32 static const char sccsid[] = "@(#)pass5.c	8.9 (Berkeley) 4/28/95";
33 #endif /* not lint */
34 #endif
35 #include <sys/cdefs.h>
36 __FBSDID("$FreeBSD$");
37 
38 #include <sys/param.h>
39 #include <sys/sysctl.h>
40 
41 #include <ufs/ufs/dinode.h>
42 #include <ufs/ffs/fs.h>
43 
44 #include <err.h>
45 #include <inttypes.h>
46 #include <limits.h>
47 #include <string.h>
48 
49 #include "fsck.h"
50 
51 static void check_maps(u_char *, u_char *, int, int, const char *, int *, int, int);
52 
53 void
54 pass5(void)
55 {
56 	int c, i, j, blk, frags, basesize, mapsize;
57 	int inomapsize, blkmapsize;
58 	struct fs *fs = &sblock;
59 	struct cg *cg = &cgrp;
60 	ufs2_daddr_t d, dbase, dmax;
61 	int excessdirs, rewritecg = 0;
62 	struct csum *cs;
63 	struct csum_total cstotal;
64 	struct inodesc idesc[3];
65 	char buf[MAXBSIZE];
66 	struct cg *newcg = (struct cg *)buf;
67 
68 	inoinfo(WINO)->ino_state = USTATE;
69 	memset(newcg, 0, (size_t)fs->fs_cgsize);
70 	newcg->cg_niblk = fs->fs_ipg;
71 	if (cvtlevel >= 3) {
72 		if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) {
73 			if (preen)
74 				pwarn("DELETING CLUSTERING MAPS\n");
75 			if (preen || reply("DELETE CLUSTERING MAPS")) {
76 				fs->fs_contigsumsize = 0;
77 				rewritecg = 1;
78 				sbdirty();
79 			}
80 		}
81 		if (fs->fs_maxcontig > 1) {
82 			const char *doit = 0;
83 
84 			if (fs->fs_contigsumsize < 1) {
85 				doit = "CREAT";
86 			} else if (fs->fs_contigsumsize < fs->fs_maxcontig &&
87 				   fs->fs_contigsumsize < FS_MAXCONTIG) {
88 				doit = "EXPAND";
89 			}
90 			if (doit) {
91 				i = fs->fs_contigsumsize;
92 				fs->fs_contigsumsize =
93 				    MIN(fs->fs_maxcontig, FS_MAXCONTIG);
94 				if (CGSIZE(fs) > (u_int)fs->fs_bsize) {
95 					pwarn("CANNOT %s CLUSTER MAPS\n", doit);
96 					fs->fs_contigsumsize = i;
97 				} else if (preen ||
98 				    reply("CREATE CLUSTER MAPS")) {
99 					if (preen)
100 						pwarn("%sING CLUSTER MAPS\n",
101 						    doit);
102 					fs->fs_cgsize =
103 					    fragroundup(fs, CGSIZE(fs));
104 					rewritecg = 1;
105 					sbdirty();
106 				}
107 			}
108 		}
109 	}
110 	basesize = &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield);
111 	if (sblock.fs_magic == FS_UFS2_MAGIC) {
112 		newcg->cg_iusedoff = basesize;
113 	} else {
114 		/*
115 		 * We reserve the space for the old rotation summary
116 		 * tables for the benefit of old kernels, but do not
117 		 * maintain them in modern kernels. In time, they can
118 		 * go away.
119 		 */
120 		newcg->cg_old_btotoff = basesize;
121 		newcg->cg_old_boff = newcg->cg_old_btotoff +
122 		    fs->fs_old_cpg * sizeof(int32_t);
123 		newcg->cg_iusedoff = newcg->cg_old_boff +
124 		    fs->fs_old_cpg * fs->fs_old_nrpos * sizeof(u_int16_t);
125 		memset(&newcg->cg_space[0], 0, newcg->cg_iusedoff - basesize);
126 	}
127 	inomapsize = howmany(fs->fs_ipg, CHAR_BIT);
128 	newcg->cg_freeoff = newcg->cg_iusedoff + inomapsize;
129 	blkmapsize = howmany(fs->fs_fpg, CHAR_BIT);
130 	newcg->cg_nextfreeoff = newcg->cg_freeoff + blkmapsize;
131 	if (fs->fs_contigsumsize > 0) {
132 		newcg->cg_clustersumoff = newcg->cg_nextfreeoff -
133 		    sizeof(u_int32_t);
134 		newcg->cg_clustersumoff =
135 		    roundup(newcg->cg_clustersumoff, sizeof(u_int32_t));
136 		newcg->cg_clusteroff = newcg->cg_clustersumoff +
137 		    (fs->fs_contigsumsize + 1) * sizeof(u_int32_t);
138 		newcg->cg_nextfreeoff = newcg->cg_clusteroff +
139 		    howmany(fragstoblks(fs, fs->fs_fpg), CHAR_BIT);
140 	}
141 	newcg->cg_magic = CG_MAGIC;
142 	mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff;
143 	memset(&idesc[0], 0, sizeof idesc);
144 	for (i = 0; i < 3; i++)
145 		idesc[i].id_type = ADDR;
146 	memset(&cstotal, 0, sizeof(struct csum_total));
147 	dmax = blknum(fs, fs->fs_size + fs->fs_frag - 1);
148 	for (d = fs->fs_size; d < dmax; d++)
149 		setbmap(d);
150 	for (c = 0; c < fs->fs_ncg; c++) {
151 		if (got_siginfo) {
152 			printf("%s: phase 5: cyl group %d of %d (%d%%)\n",
153 			    cdevname, c, sblock.fs_ncg,
154 			    c * 100 / sblock.fs_ncg);
155 			got_siginfo = 0;
156 		}
157 		if (got_sigalarm) {
158 			setproctitle("%s p5 %d%%", cdevname,
159 			    c * 100 / sblock.fs_ncg);
160 			got_sigalarm = 0;
161 		}
162 		getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize);
163 		if (!cg_chkmagic(cg))
164 			pfatal("CG %d: BAD MAGIC NUMBER\n", c);
165 		newcg->cg_time = cg->cg_time;
166 		newcg->cg_old_time = cg->cg_old_time;
167 		newcg->cg_unrefs = cg->cg_unrefs;
168 		newcg->cg_cgx = c;
169 		dbase = cgbase(fs, c);
170 		dmax = dbase + fs->fs_fpg;
171 		if (dmax > fs->fs_size)
172 			dmax = fs->fs_size;
173 		newcg->cg_ndblk = dmax - dbase;
174 		if (fs->fs_magic == FS_UFS1_MAGIC) {
175 			if (c == fs->fs_ncg - 1)
176 				newcg->cg_old_ncyl = howmany(newcg->cg_ndblk,
177 				    fs->fs_fpg / fs->fs_old_cpg);
178 			else
179 				newcg->cg_old_ncyl = fs->fs_old_cpg;
180 			newcg->cg_old_niblk = fs->fs_ipg;
181 			newcg->cg_niblk = 0;
182 		}
183 		if (fs->fs_contigsumsize > 0)
184 			newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag;
185 		newcg->cg_cs.cs_ndir = 0;
186 		newcg->cg_cs.cs_nffree = 0;
187 		newcg->cg_cs.cs_nbfree = 0;
188 		newcg->cg_cs.cs_nifree = fs->fs_ipg;
189 		if (cg->cg_rotor >= 0 && cg->cg_rotor < newcg->cg_ndblk)
190 			newcg->cg_rotor = cg->cg_rotor;
191 		else
192 			newcg->cg_rotor = 0;
193 		if (cg->cg_frotor >= 0 && cg->cg_frotor < newcg->cg_ndblk)
194 			newcg->cg_frotor = cg->cg_frotor;
195 		else
196 			newcg->cg_frotor = 0;
197 		if (cg->cg_irotor >= 0 && cg->cg_irotor < fs->fs_ipg)
198 			newcg->cg_irotor = cg->cg_irotor;
199 		else
200 			newcg->cg_irotor = 0;
201 		if (fs->fs_magic == FS_UFS1_MAGIC) {
202 			newcg->cg_initediblk = 0;
203 		} else {
204 			if ((unsigned)cg->cg_initediblk > fs->fs_ipg)
205 				newcg->cg_initediblk = fs->fs_ipg;
206 			else
207 				newcg->cg_initediblk = cg->cg_initediblk;
208 		}
209 		memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum);
210 		memset(cg_inosused(newcg), 0, (size_t)(mapsize));
211 		j = fs->fs_ipg * c;
212 		for (i = 0; i < inostathead[c].il_numalloced; j++, i++) {
213 			switch (inoinfo(j)->ino_state) {
214 
215 			case USTATE:
216 				break;
217 
218 			case DSTATE:
219 			case DCLEAR:
220 			case DFOUND:
221 			case DZLINK:
222 				newcg->cg_cs.cs_ndir++;
223 				/* FALLTHROUGH */
224 
225 			case FSTATE:
226 			case FCLEAR:
227 			case FZLINK:
228 				newcg->cg_cs.cs_nifree--;
229 				setbit(cg_inosused(newcg), i);
230 				break;
231 
232 			default:
233 				if (j < (int)ROOTINO)
234 					break;
235 				errx(EEXIT, "BAD STATE %d FOR INODE I=%d",
236 				    inoinfo(j)->ino_state, j);
237 			}
238 		}
239 		if (c == 0)
240 			for (i = 0; i < (int)ROOTINO; i++) {
241 				setbit(cg_inosused(newcg), i);
242 				newcg->cg_cs.cs_nifree--;
243 			}
244 		for (i = 0, d = dbase;
245 		     d < dmax;
246 		     d += fs->fs_frag, i += fs->fs_frag) {
247 			frags = 0;
248 			for (j = 0; j < fs->fs_frag; j++) {
249 				if (testbmap(d + j))
250 					continue;
251 				setbit(cg_blksfree(newcg), i + j);
252 				frags++;
253 			}
254 			if (frags == fs->fs_frag) {
255 				newcg->cg_cs.cs_nbfree++;
256 				if (fs->fs_contigsumsize > 0)
257 					setbit(cg_clustersfree(newcg),
258 					    i / fs->fs_frag);
259 			} else if (frags > 0) {
260 				newcg->cg_cs.cs_nffree += frags;
261 				blk = blkmap(fs, cg_blksfree(newcg), i);
262 				ffs_fragacct(fs, blk, newcg->cg_frsum, 1);
263 			}
264 		}
265 		if (fs->fs_contigsumsize > 0) {
266 			int32_t *sump = cg_clustersum(newcg);
267 			u_char *mapp = cg_clustersfree(newcg);
268 			int map = *mapp++;
269 			int bit = 1;
270 			int run = 0;
271 
272 			for (i = 0; i < newcg->cg_nclusterblks; i++) {
273 				if ((map & bit) != 0) {
274 					run++;
275 				} else if (run != 0) {
276 					if (run > fs->fs_contigsumsize)
277 						run = fs->fs_contigsumsize;
278 					sump[run]++;
279 					run = 0;
280 				}
281 				if ((i & (CHAR_BIT - 1)) != (CHAR_BIT - 1)) {
282 					bit <<= 1;
283 				} else {
284 					map = *mapp++;
285 					bit = 1;
286 				}
287 			}
288 			if (run != 0) {
289 				if (run > fs->fs_contigsumsize)
290 					run = fs->fs_contigsumsize;
291 				sump[run]++;
292 			}
293 		}
294 		cstotal.cs_nffree += newcg->cg_cs.cs_nffree;
295 		cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree;
296 		cstotal.cs_nifree += newcg->cg_cs.cs_nifree;
297 		cstotal.cs_ndir += newcg->cg_cs.cs_ndir;
298 		cs = &fs->fs_cs(fs, c);
299 		if (cursnapshot == 0 &&
300 		    memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 &&
301 		    dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) {
302 			memmove(cs, &newcg->cg_cs, sizeof *cs);
303 			sbdirty();
304 		}
305 		if (rewritecg) {
306 			memmove(cg, newcg, (size_t)fs->fs_cgsize);
307 			cgdirty();
308 			continue;
309 		}
310 		if (cursnapshot == 0 &&
311 		    memcmp(newcg, cg, basesize) != 0 &&
312 		    dofix(&idesc[2], "SUMMARY INFORMATION BAD")) {
313 			memmove(cg, newcg, (size_t)basesize);
314 			cgdirty();
315 		}
316 		if (bkgrdflag != 0 || usedsoftdep || debug) {
317 			excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir;
318 			if (excessdirs < 0) {
319 				pfatal("LOST %d DIRECTORIES\n", -excessdirs);
320 				excessdirs = 0;
321 			}
322 			if (excessdirs > 0)
323 				check_maps(cg_inosused(newcg), cg_inosused(cg),
324 				    inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR",
325 				    freedirs, 0, excessdirs);
326 			check_maps(cg_inosused(newcg), cg_inosused(cg),
327 			    inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE",
328 			    freefiles, excessdirs, fs->fs_ipg);
329 			check_maps(cg_blksfree(cg), cg_blksfree(newcg),
330 			    blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG",
331 			    freeblks, 0, fs->fs_fpg);
332 		}
333 		if (cursnapshot == 0 &&
334 		    memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 &&
335 		    dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) {
336 			memmove(cg_inosused(cg), cg_inosused(newcg),
337 			      (size_t)mapsize);
338 			cgdirty();
339 		}
340 	}
341 	if (cursnapshot == 0 &&
342 	    memcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal) != 0
343 	    && dofix(&idesc[0], "SUMMARY BLK COUNT(S) WRONG IN SUPERBLK")) {
344 		memmove(&fs->fs_cstotal, &cstotal, sizeof cstotal);
345 		fs->fs_ronly = 0;
346 		fs->fs_fmod = 0;
347 		sbdirty();
348 	}
349 
350 	/*
351 	 * When doing background fsck on a snapshot, figure out whether
352 	 * the superblock summary is inaccurate and correct it when
353 	 * necessary.
354 	 */
355 	if (cursnapshot != 0) {
356 		cmd.size = 1;
357 
358 		cmd.value = cstotal.cs_ndir - fs->fs_cstotal.cs_ndir;
359 		if (cmd.value != 0) {
360 			if (debug)
361 				printf("adjndir by %+" PRIi64 "\n", cmd.value);
362 			if (bkgrdsumadj == 0 || sysctl(adjndir, MIBSIZE, 0, 0,
363 			    &cmd, sizeof cmd) == -1)
364 				rwerror("ADJUST NUMBER OF DIRECTORIES", cmd.value);
365 		}
366 
367 		cmd.value = cstotal.cs_nbfree - fs->fs_cstotal.cs_nbfree;
368 		if (cmd.value != 0) {
369 			if (debug)
370 				printf("adjnbfree by %+" PRIi64 "\n", cmd.value);
371 			if (bkgrdsumadj == 0 || sysctl(adjnbfree, MIBSIZE, 0, 0,
372 			    &cmd, sizeof cmd) == -1)
373 				rwerror("ADJUST NUMBER OF FREE BLOCKS", cmd.value);
374 		}
375 
376 		cmd.value = cstotal.cs_nifree - fs->fs_cstotal.cs_nifree;
377 		if (cmd.value != 0) {
378 			if (debug)
379 				printf("adjnifree by %+" PRIi64 "\n", cmd.value);
380 			if (bkgrdsumadj == 0 || sysctl(adjnifree, MIBSIZE, 0, 0,
381 			    &cmd, sizeof cmd) == -1)
382 				rwerror("ADJUST NUMBER OF FREE INODES", cmd.value);
383 		}
384 
385 		cmd.value = cstotal.cs_nffree - fs->fs_cstotal.cs_nffree;
386 		if (cmd.value != 0) {
387 			if (debug)
388 				printf("adjnffree by %+" PRIi64 "\n", cmd.value);
389 			if (bkgrdsumadj == 0 || sysctl(adjnffree, MIBSIZE, 0, 0,
390 			    &cmd, sizeof cmd) == -1)
391 				rwerror("ADJUST NUMBER OF FREE FRAGS", cmd.value);
392 		}
393 
394 		cmd.value = cstotal.cs_numclusters - fs->fs_cstotal.cs_numclusters;
395 		if (cmd.value != 0) {
396 			if (debug)
397 				printf("adjnumclusters by %+" PRIi64 "\n", cmd.value);
398 			if (bkgrdsumadj == 0 || sysctl(adjnumclusters, MIBSIZE, 0, 0,
399 			    &cmd, sizeof cmd) == -1)
400 				rwerror("ADJUST NUMBER OF FREE CLUSTERS", cmd.value);
401 		}
402 	}
403 }
404 
405 static void
406 check_maps(
407 	u_char *map1,	/* map of claimed allocations */
408 	u_char *map2,	/* map of determined allocations */
409 	int mapsize,	/* size of above two maps */
410 	int startvalue,	/* resource value for first element in map */
411 	const char *name,	/* name of resource found in maps */
412 	int *opcode,	/* sysctl opcode to free resource */
413 	int skip,	/* number of entries to skip before starting to free */
414 	int limit)	/* limit on number of entries to free */
415 {
416 #	define BUFSIZE 16
417 	char buf[BUFSIZE];
418 	long i, j, k, l, m, n, size;
419 	int astart, aend, ustart, uend;
420 	void (*msg)(const char *fmt, ...);
421 
422 	if (bkgrdflag)
423 		msg = pfatal;
424 	else
425 		msg = pwarn;
426 	astart = ustart = aend = uend = -1;
427 	for (i = 0; i < mapsize; i++) {
428 		j = *map1++;
429 		k = *map2++;
430 		if (j == k)
431 			continue;
432 		for (m = 0, l = 1; m < CHAR_BIT; m++, l <<= 1) {
433 			if ((j & l) == (k & l))
434 				continue;
435 			n = startvalue + i * CHAR_BIT + m;
436 			if ((j & l) != 0) {
437 				if (astart == -1) {
438 					astart = aend = n;
439 					continue;
440 				}
441 				if (aend + 1 == n) {
442 					aend = n;
443 					continue;
444 				}
445 				if (astart == aend)
446 					(*msg)("ALLOCATED %s %d MARKED FREE\n",
447 					    name, astart);
448 				else
449 					(*msg)("%s %sS %d-%d MARKED FREE\n",
450 					    "ALLOCATED", name, astart, aend);
451 				astart = aend = n;
452 			} else {
453 				if (ustart == -1) {
454 					ustart = uend = n;
455 					continue;
456 				}
457 				if (uend + 1 == n) {
458 					uend = n;
459 					continue;
460 				}
461 				size = uend - ustart + 1;
462 				if (size <= skip) {
463 					skip -= size;
464 					ustart = uend = n;
465 					continue;
466 				}
467 				if (skip > 0) {
468 					ustart += skip;
469 					size -= skip;
470 					skip = 0;
471 				}
472 				if (size > limit)
473 					size = limit;
474 				if (debug && size == 1)
475 					pwarn("%s %s %d MARKED USED\n",
476 					    "UNALLOCATED", name, ustart);
477 				else if (debug)
478 					pwarn("%s %sS %d-%ld MARKED USED\n",
479 					    "UNALLOCATED", name, ustart,
480 					    ustart + size - 1);
481 				if (bkgrdflag != 0) {
482 					cmd.value = ustart;
483 					cmd.size = size;
484 					if (sysctl(opcode, MIBSIZE, 0, 0,
485 					    &cmd, sizeof cmd) == -1) {
486 						snprintf(buf, BUFSIZE,
487 						    "FREE %s", name);
488 						rwerror(buf, cmd.value);
489 					}
490 				}
491 				limit -= size;
492 				if (limit <= 0)
493 					return;
494 				ustart = uend = n;
495 			}
496 		}
497 	}
498 	if (astart != -1) {
499 		if (astart == aend)
500 			(*msg)("ALLOCATED %s %d MARKED FREE\n", name, astart);
501 		else
502 			(*msg)("ALLOCATED %sS %d-%d MARKED FREE\n",
503 			    name, astart, aend);
504 	}
505 	if (ustart != -1) {
506 		size = uend - ustart + 1;
507 		if (size <= skip)
508 			return;
509 		if (skip > 0) {
510 			ustart += skip;
511 			size -= skip;
512 		}
513 		if (size > limit)
514 			size = limit;
515 		if (debug) {
516 			if (size == 1)
517 				pwarn("UNALLOCATED %s %d MARKED USED\n",
518 				    name, ustart);
519 			else
520 				pwarn("UNALLOCATED %sS %d-%ld MARKED USED\n",
521 				    name, ustart, ustart + size - 1);
522 		}
523 		if (bkgrdflag != 0) {
524 			cmd.value = ustart;
525 			cmd.size = size;
526 			if (sysctl(opcode, MIBSIZE, 0, 0, &cmd,
527 			    sizeof cmd) == -1) {
528 				snprintf(buf, BUFSIZE, "FREE %s", name);
529 				rwerror(buf, cmd.value);
530 			}
531 		}
532 	}
533 }
534