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: src/sbin/fsck_ffs/gjournal.c,v 1.2.2.1.2.1 2010/02/10 00:26:20 kensmith Exp $");
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. */