2 * Copyright (c) 2006 Pawel Jakub Dawidek <pjd@FreeBSD.org>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * Copyright (c) 1982, 1986, 1989, 1993
27 * The Regents of the University of California. All rights reserved.
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
32 * 1. Redistributions of source code must retain the above copyright
33 * notice, this list of conditions and the following disclaimer.
34 * 2. Redistributions in binary form must reproduce the above copyright
35 * notice, this list of conditions and the following disclaimer in the
36 * documentation and/or other materials provided with the distribution.
37 * 4. Neither the name of the University nor the names of its contributors
38 * may be used to endorse or promote products derived from this software
39 * without specific prior written permission.
41 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54 #include <sys/cdefs.h>
55 __FBSDID("$FreeBSD$");
57 #include <sys/param.h>
58 #include <sys/disklabel.h>
59 #include <sys/mount.h>
62 #include <ufs/ufs/ufsmount.h>
63 #include <ufs/ufs/dinode.h>
64 #include <ufs/ffs/fs.h>
79 char cgcu_buf[MAXBSIZE];
83 LIST_ENTRY(cgchain) cgc_next;
85 #define cgc_cg cgc_union.cgcu_cg
87 #define MAX_CACHED_CGS 1024
88 static unsigned ncgs = 0;
89 static LIST_HEAD(, cgchain) cglist = LIST_HEAD_INITIALIZER(&cglist);
91 static const char *devnam;
92 static struct uufsd *disk = NULL;
93 static struct fs *fs = NULL;
94 struct ufs2_dinode ufs2_zino;
96 static void putcgs(void);
99 * Write current block of inodes.
102 putino(struct uufsd *disk, ino_t inode)
109 inoblock = disk->d_inoblock;
111 assert(inoblock != NULL);
112 assert(inode >= disk->d_inomin && inode <= disk->d_inomax);
113 ret = bwrite(disk, fsbtodb(fs, ino_to_fsba(fs, inode)), inoblock,
116 return (ret == -1 ? -1 : 0);
120 * Return cylinder group from the cache or load it if it is not in the
122 * Don't cache more than MAX_CACHED_CGS cylinder groups.
124 static struct cgchain *
129 assert(disk != NULL && fs != NULL);
130 LIST_FOREACH(cgc, &cglist, cgc_next) {
131 if (cgc->cgc_cg.cg_cgx == cg) {
132 //printf("%s: Found cg=%d\n", __func__, cg);
137 * Our cache is full? Let's clean it up.
139 if (ncgs >= MAX_CACHED_CGS) {
140 //printf("%s: Flushing CGs.\n", __func__);
143 cgc = malloc(sizeof(*cgc));
146 * Cannot allocate memory?
147 * Let's put all currently loaded and not busy cylinder groups
148 * on disk and try again.
150 //printf("%s: No memory, flushing CGs.\n", __func__);
152 cgc = malloc(sizeof(*cgc));
154 err(1, "malloc(%zu)", sizeof(*cgc));
156 if (cgread1(disk, cg) == -1)
157 err(1, "cgread1(%d)", cg);
158 bcopy(&disk->d_cg, &cgc->cgc_cg, sizeof(cgc->cgc_union));
161 LIST_INSERT_HEAD(&cglist, cgc, cgc_next);
163 //printf("%s: Read cg=%d\n", __func__, cg);
168 * Mark cylinder group as dirty - it will be written back on putcgs().
171 dirtycg(struct cgchain *cgc)
178 * Mark cylinder group as busy - it will not be freed on putcgs().
181 busycg(struct cgchain *cgc)
188 * Unmark the given cylinder group as busy.
191 unbusycg(struct cgchain *cgc)
198 * Write back all dirty cylinder groups.
199 * Free all non-busy cylinder groups.
204 struct cgchain *cgc, *cgc2;
206 assert(disk != NULL && fs != NULL);
207 LIST_FOREACH_SAFE(cgc, &cglist, cgc_next, cgc2) {
210 LIST_REMOVE(cgc, cgc_next);
212 if (cgc->cgc_dirty) {
213 bcopy(&cgc->cgc_cg, &disk->d_cg,
214 sizeof(cgc->cgc_union));
215 if (cgwrite1(disk, cgc->cgc_cg.cg_cgx) == -1)
216 err(1, "cgwrite1(%d)", cgc->cgc_cg.cg_cgx);
217 //printf("%s: Wrote cg=%d\n", __func__,
218 // cgc->cgc_cg.cg_cgx);
226 * Free all non-busy cylinder groups without storing the dirty ones.
233 assert(disk != NULL && fs != NULL);
234 while ((cgc = LIST_FIRST(&cglist)) != NULL) {
237 LIST_REMOVE(cgc, cgc_next);
238 //printf("%s: Canceled cg=%d\n", __func__, cgc->cgc_cg.cg_cgx);
245 * Open the given provider, load statistics.
254 disk = malloc(sizeof(*disk));
256 err(1, "malloc(%zu)", sizeof(*disk));
257 if (ufs_disk_fillout(disk, devnam) == -1) {
258 err(1, "ufs_disk_fillout(%s) failed: %s", devnam,
262 fs->fs_csp = malloc((size_t)fs->fs_cssize);
263 if (fs->fs_csp == NULL)
264 err(1, "malloc(%zu)", (size_t)fs->fs_cssize);
265 bzero(fs->fs_csp, (size_t)fs->fs_cssize);
266 for (i = 0; i < fs->fs_cssize; i += fs->fs_bsize) {
267 if (bread(disk, fsbtodb(fs, fs->fs_csaddr + numfrags(fs, i)),
268 (void *)(((char *)fs->fs_csp) + i),
269 (size_t)(fs->fs_cssize - i < fs->fs_bsize ? fs->fs_cssize - i : fs->fs_bsize)) == -1) {
270 err(1, "bread: %s", disk->d_error);
273 if (fs->fs_contigsumsize > 0) {
274 fs->fs_maxcluster = malloc(fs->fs_ncg * sizeof(int32_t));
275 if (fs->fs_maxcluster == NULL)
276 err(1, "malloc(%zu)", fs->fs_ncg * sizeof(int32_t));
277 for (i = 0; i < fs->fs_ncg; i++)
278 fs->fs_maxcluster[i] = fs->fs_contigsumsize;
283 * Mark file system as clean, write the super-block back, close the disk.
290 if (fs->fs_contigsumsize > 0) {
291 free(fs->fs_maxcluster);
292 fs->fs_maxcluster = NULL;
295 if (sbwrite(disk, 0) == -1)
296 err(1, "sbwrite(%s)", devnam);
297 if (ufs_disk_close(disk) == -1)
298 err(1, "ufs_disk_close(%s)", devnam);
305 * Write the statistics back, call closedisk().
312 assert(disk != NULL && fs != NULL);
313 for (i = 0; i < fs->fs_cssize; i += fs->fs_bsize) {
314 if (bwrite(disk, fsbtodb(fs, fs->fs_csaddr + numfrags(fs, i)),
315 (void *)(((char *)fs->fs_csp) + i),
316 (size_t)(fs->fs_cssize - i < fs->fs_bsize ? fs->fs_cssize - i : fs->fs_bsize)) == -1) {
317 err(1, "bwrite: %s", disk->d_error);
325 * Free memory, close the disk, but don't write anything back.
332 assert(disk != NULL && fs != NULL);
334 if (fs->fs_contigsumsize > 0)
335 free(fs->fs_maxcluster);
336 if (ufs_disk_close(disk) == -1)
337 err(1, "ufs_disk_close(%s)", devnam);
345 isblock(unsigned char *cp, ufs1_daddr_t h)
349 switch ((int)fs->fs_frag) {
351 return (cp[h] == 0xff);
353 mask = 0x0f << ((h & 0x1) << 2);
354 return ((cp[h >> 1] & mask) == mask);
356 mask = 0x03 << ((h & 0x3) << 1);
357 return ((cp[h >> 2] & mask) == mask);
359 mask = 0x01 << (h & 0x7);
360 return ((cp[h >> 3] & mask) == mask);
362 assert(!"isblock: invalid number of fragments");
368 * put a block into the map
371 setblock(unsigned char *cp, ufs1_daddr_t h)
374 switch ((int)fs->fs_frag) {
379 cp[h >> 1] |= (0x0f << ((h & 0x1) << 2));
382 cp[h >> 2] |= (0x03 << ((h & 0x3) << 1));
385 cp[h >> 3] |= (0x01 << (h & 0x7));
388 assert(!"setblock: invalid number of fragments");
393 * check if a block is free
396 isfreeblock(u_char *cp, ufs1_daddr_t h)
399 switch ((int)fs->fs_frag) {
403 return ((cp[h >> 1] & (0x0f << ((h & 0x1) << 2))) == 0);
405 return ((cp[h >> 2] & (0x03 << ((h & 0x3) << 1))) == 0);
407 return ((cp[h >> 3] & (0x01 << (h & 0x7))) == 0);
409 assert(!"isfreeblock: invalid number of fragments");
415 * Update the frsum fields to reflect addition or deletion
419 fragacct(int fragmap, int32_t fraglist[], int cnt)
425 inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1;
427 for (siz = 1; siz < fs->fs_frag; siz++) {
428 if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0)
431 subfield = inside[siz];
432 for (pos = siz; pos <= fs->fs_frag; pos++) {
433 if ((fragmap & field) == subfield) {
434 fraglist[siz] += cnt;
446 clusteracct(struct cg *cgp, ufs1_daddr_t blkno)
450 u_char *freemapp, *mapp;
451 int i, start, end, forw, back, map, bit;
453 if (fs->fs_contigsumsize <= 0)
455 freemapp = cg_clustersfree(cgp);
456 sump = cg_clustersum(cgp);
458 * Clear the actual block.
460 setbit(freemapp, blkno);
462 * Find the size of the cluster going forward.
465 end = start + fs->fs_contigsumsize;
466 if (end >= cgp->cg_nclusterblks)
467 end = cgp->cg_nclusterblks;
468 mapp = &freemapp[start / NBBY];
470 bit = 1 << (start % NBBY);
471 for (i = start; i < end; i++) {
472 if ((map & bit) == 0)
474 if ((i & (NBBY - 1)) != (NBBY - 1)) {
483 * Find the size of the cluster going backward.
486 end = start - fs->fs_contigsumsize;
489 mapp = &freemapp[start / NBBY];
491 bit = 1 << (start % NBBY);
492 for (i = start; i > end; i--) {
493 if ((map & bit) == 0)
495 if ((i & (NBBY - 1)) != 0) {
499 bit = 1 << (NBBY - 1);
504 * Account for old cluster and the possibly new forward and
508 if (i > fs->fs_contigsumsize)
509 i = fs->fs_contigsumsize;
516 * Update cluster summary information.
518 lp = &sump[fs->fs_contigsumsize];
519 for (i = fs->fs_contigsumsize; i > 0; i--)
522 fs->fs_maxcluster[cgp->cg_cgx] = i;
526 blkfree(ufs2_daddr_t bno, long size)
530 ufs1_daddr_t fragno, cgbno;
531 int i, cg, blk, frags, bbase;
538 cgbno = dtogd(fs, bno);
539 blksfree = cg_blksfree(cgp);
540 if (size == fs->fs_bsize) {
541 fragno = fragstoblks(fs, cgbno);
542 if (!isfreeblock(blksfree, fragno))
543 assert(!"blkfree: freeing free block");
544 setblock(blksfree, fragno);
545 clusteracct(cgp, fragno);
546 cgp->cg_cs.cs_nbfree++;
547 fs->fs_cstotal.cs_nbfree++;
548 fs->fs_cs(fs, cg).cs_nbfree++;
550 bbase = cgbno - fragnum(fs, cgbno);
552 * decrement the counts associated with the old frags
554 blk = blkmap(fs, blksfree, bbase);
555 fragacct(blk, cgp->cg_frsum, -1);
557 * deallocate the fragment
559 frags = numfrags(fs, size);
560 for (i = 0; i < frags; i++) {
561 if (isset(blksfree, cgbno + i))
562 assert(!"blkfree: freeing free frag");
563 setbit(blksfree, cgbno + i);
565 cgp->cg_cs.cs_nffree += i;
566 fs->fs_cstotal.cs_nffree += i;
567 fs->fs_cs(fs, cg).cs_nffree += i;
569 * add back in counts associated with the new frags
571 blk = blkmap(fs, blksfree, bbase);
572 fragacct(blk, cgp->cg_frsum, 1);
574 * if a complete block has been reassembled, account for it
576 fragno = fragstoblks(fs, bbase);
577 if (isblock(blksfree, fragno)) {
578 cgp->cg_cs.cs_nffree -= fs->fs_frag;
579 fs->fs_cstotal.cs_nffree -= fs->fs_frag;
580 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
581 clusteracct(cgp, fragno);
582 cgp->cg_cs.cs_nbfree++;
583 fs->fs_cstotal.cs_nbfree++;
584 fs->fs_cs(fs, cg).cs_nbfree++;
590 * Recursively free all indirect blocks.
593 freeindir(ufs2_daddr_t blk, int level)
595 char sblks[MAXBSIZE];
599 if (bread(disk, fsbtodb(fs, blk), (void *)&sblks, (size_t)fs->fs_bsize) == -1)
600 err(1, "bread: %s", disk->d_error);
601 blks = (ufs2_daddr_t *)&sblks;
602 for (i = 0; i < howmany(fs->fs_bsize, sizeof(ufs2_daddr_t)); i++) {
606 blkfree(blks[i], fs->fs_bsize);
608 freeindir(blks[i], level - 1);
610 blkfree(blk, fs->fs_bsize);
613 #define dblksize(fs, dino, lbn) \
614 ((dino)->di_size >= smalllblktosize(fs, (lbn) + 1) \
616 : fragroundup(fs, blkoff(fs, (dino)->di_size)))
619 * Free all blocks associated with the given inode.
622 clear_inode(struct ufs2_dinode *dino)
625 int extblocks, i, level;
630 if (fs->fs_magic == FS_UFS2_MAGIC && dino->di_extsize > 0)
631 extblocks = btodb(fragroundup(fs, dino->di_extsize));
632 /* deallocate external attributes blocks */
634 osize = dino->di_extsize;
635 dino->di_blocks -= extblocks;
636 dino->di_extsize = 0;
637 for (i = 0; i < NXADDR; i++) {
638 if (dino->di_extb[i] == 0)
640 blkfree(dino->di_extb[i], sblksize(fs, osize, i));
643 #define SINGLE 0 /* index of single indirect block */
644 #define DOUBLE 1 /* index of double indirect block */
645 #define TRIPLE 2 /* index of triple indirect block */
646 /* deallocate indirect blocks */
647 for (level = SINGLE; level <= TRIPLE; level++) {
648 if (dino->di_ib[level] == 0)
650 freeindir(dino->di_ib[level], level);
652 /* deallocate direct blocks and fragments */
653 for (i = 0; i < NDADDR; i++) {
657 bsize = dblksize(fs, dino, i);
663 gjournal_check(const char *filesys)
665 struct ufs2_dinode *dino;
669 uint8_t *inosused, *blksfree;
675 /* Are there any unreferenced inodes in this file system? */
676 if (fs->fs_unrefs == 0) {
677 //printf("No unreferenced inodes.\n");
682 for (cg = 0; cg < fs->fs_ncg; cg++) {
683 /* Show progress if requested. */
685 printf("%s: phase j: cyl group %d of %d (%d%%)\n",
686 cdevname, cg, fs->fs_ncg, cg * 100 / fs->fs_ncg);
690 setproctitle("%s pj %d%%", cdevname,
691 cg * 100 / fs->fs_ncg);
696 /* Are there any unreferenced inodes in this cylinder group? */
697 if (cgp->cg_unrefs == 0)
699 //printf("Analizing cylinder group %d (count=%d)\n", cg, cgp->cg_unrefs);
701 * We are going to modify this cylinder group, so we want it to
705 /* We don't want it to be freed in the meantime. */
707 inosused = cg_inosused(cgp);
708 blksfree = cg_blksfree(cgp);
710 * Now go through the list of all inodes in this cylinder group
711 * to find unreferenced ones.
713 for (cino = 0; cino < fs->fs_ipg; cino++) {
714 ino = fs->fs_ipg * cg + cino;
715 /* Unallocated? Skip it. */
716 if (isclr(inosused, cino))
718 if (getino(disk, &p, ino, &mode) == -1)
719 err(1, "getino(cg=%d ino=%d)", cg, ino);
721 /* Not a regular file nor directory? Skip it. */
722 if (!S_ISREG(dino->di_mode) && !S_ISDIR(dino->di_mode))
724 /* Has reference(s)? Skip it. */
725 if (dino->di_nlink > 0)
727 //printf("Clearing inode=%d (size=%jd)\n", ino, (intmax_t)dino->di_size);
728 /* Free inode's blocks. */
731 clrbit(inosused, cino);
732 /* Update position of last used inode. */
733 if (ino < cgp->cg_irotor)
734 cgp->cg_irotor = ino;
735 /* Update statistics. */
736 cgp->cg_cs.cs_nifree++;
737 fs->fs_cs(fs, cg).cs_nifree++;
738 fs->fs_cstotal.cs_nifree++;
741 /* If this is directory, update related statistics. */
742 if (S_ISDIR(dino->di_mode)) {
743 cgp->cg_cs.cs_ndir--;
744 fs->fs_cs(fs, cg).cs_ndir--;
745 fs->fs_cstotal.cs_ndir--;
747 /* Zero-fill the inode. */
749 /* Write the inode back. */
750 if (putino(disk, ino) == -1)
751 err(1, "putino(cg=%d ino=%d)", cg, ino);
752 if (cgp->cg_unrefs == 0) {
753 //printf("No more unreferenced inodes in cg=%d.\n", cg);
758 * We don't need this cylinder group anymore, so feel free to
763 * If there are no more unreferenced inodes, there is no need to
764 * check other cylinder groups.
766 if (fs->fs_unrefs == 0) {
767 //printf("No more unreferenced inodes (cg=%d/%d).\n", cg,
772 /* Write back modified cylinder groups. */
774 /* Write back updated statistics and super-block. */