From 62e6c152ac7d3bcc216b34feb5e7a88df978ee68 Mon Sep 17 00:00:00 2001 From: Kirk McKusick Date: Sat, 1 Jun 1985 03:08:51 -0800 Subject: [PATCH] dynamically allocate the duplicate block table SCCS-vsn: sbin/fsck/fsck.h 3.5 SCCS-vsn: sbin/fsck/main.c 3.4 SCCS-vsn: sbin/fsck/pass1.c 3.6 SCCS-vsn: sbin/fsck/pass1b.c 3.3 SCCS-vsn: sbin/fsck/pass4.c 3.3 SCCS-vsn: sbin/fsck/setup.c 3.5 --- usr/src/sbin/fsck/fsck.h | 16 ++++++++++------ usr/src/sbin/fsck/main.c | 4 ++-- usr/src/sbin/fsck/pass1.c | 28 +++++++++++++++++----------- usr/src/sbin/fsck/pass1b.c | 22 ++++++++++++++-------- usr/src/sbin/fsck/pass4.c | 28 +++++++++++++++++----------- usr/src/sbin/fsck/setup.c | 3 +-- 6 files changed, 61 insertions(+), 40 deletions(-) diff --git a/usr/src/sbin/fsck/fsck.h b/usr/src/sbin/fsck/fsck.h index cdff7ec7aa..6d533421d2 100644 --- a/usr/src/sbin/fsck/fsck.h +++ b/usr/src/sbin/fsck/fsck.h @@ -1,8 +1,7 @@ -/* @(#)fsck.h 3.4 (Berkeley) %G% */ +/* @(#)fsck.h 3.5 (Berkeley) %G% */ #define MAXDUP 10 /* limit on dup blks (per inode) */ #define MAXBAD 10 /* limit on bad blks (per inode) */ -#define DUPTBLSIZE 100 /* num of dup blocks to remember */ #define MAXLNCNT 500 /* num zero link cnts to remember */ typedef int (*SIG_TYP)(); @@ -89,10 +88,15 @@ struct inodesc { #define DATA 1 #define ADDR 2 - -daddr_t duplist[DUPTBLSIZE]; /* dup block table */ -daddr_t *enddup; /* next entry in dup table */ -daddr_t *muldup; /* multiple dups part of table */ +/* + * Linked list of duplicate blocks + */ +struct dups { + struct dups *next; + daddr_t dup; +}; +struct dups *duplist; /* head of dup list */ +struct dups *muldup; /* end of unique duplicate dup block numbers */ ino_t badlncnt[MAXLNCNT]; /* table of inos with zero link cnts */ ino_t *badlnp; /* next entry in table */ diff --git a/usr/src/sbin/fsck/main.c b/usr/src/sbin/fsck/main.c index 510f82bc2b..e978d7bfa9 100644 --- a/usr/src/sbin/fsck/main.c +++ b/usr/src/sbin/fsck/main.c @@ -1,5 +1,5 @@ #ifndef lint -static char version[] = "@(#)main.c 3.3 (Berkeley) %G%"; +static char version[] = "@(#)main.c 3.4 (Berkeley) %G%"; #endif #include @@ -143,7 +143,7 @@ checkfilesys(filesys) /* * 1b: locate first references to duplicates, if any */ - if (enddup != &duplist[0]) { + if (duplist) { if (preen) pfatal("INTERNAL ERROR: dups with -p"); printf("** Phase 1b - Rescan For More DUPS\n"); diff --git a/usr/src/sbin/fsck/pass1.c b/usr/src/sbin/fsck/pass1.c index 2a68b1e4d1..80690fee29 100644 --- a/usr/src/sbin/fsck/pass1.c +++ b/usr/src/sbin/fsck/pass1.c @@ -1,5 +1,5 @@ #ifndef lint -static char version[] = "@(#)pass1.c 3.5 (Berkeley) %G%"; +static char version[] = "@(#)pass1.c 3.6 (Berkeley) %G%"; #endif #include @@ -133,10 +133,11 @@ pass1() pass1check(idesc) register struct inodesc *idesc; { - register daddr_t *dlp; int res = KEEPON; int anyout, nfrags; daddr_t blkno = idesc->id_blkno; + register struct dups *dlp; + struct dups *new; if ((anyout = outrange(blkno, idesc->id_numfrags)) != 0) { blkerr(idesc->id_number, "BAD", blkno); @@ -167,21 +168,26 @@ pass1check(idesc) errexit(""); return (STOP); } - if (enddup >= &duplist[DUPTBLSIZE]) { + new = (struct dups *)malloc(sizeof(struct dups)); + if (new == NULL) { pfatal("DUP TABLE OVERFLOW."); if (reply("CONTINUE") == 0) errexit(""); return (STOP); } - for (dlp = duplist; dlp < muldup; dlp++) - if (*dlp == blkno) { - *enddup++ = blkno; - break; - } - if (dlp >= muldup) { - *enddup++ = *muldup; - *muldup++ = blkno; + new->dup = blkno; + if (muldup == 0) { + duplist = muldup = new; + new->next = 0; + } else { + new->next = muldup->next; + muldup->next = new; } + for (dlp = duplist; dlp != muldup; dlp = dlp->next) + if (dlp->dup == blkno) + break; + if (dlp == muldup && dlp->dup != blkno) + muldup = new; } /* * count the number of blocks found in id_entryno diff --git a/usr/src/sbin/fsck/pass1b.c b/usr/src/sbin/fsck/pass1b.c index 7a6e9cb633..84f7c9b39e 100644 --- a/usr/src/sbin/fsck/pass1b.c +++ b/usr/src/sbin/fsck/pass1b.c @@ -1,5 +1,5 @@ #ifndef lint -static char version[] = "@(#)pass1b.c 3.2 (Berkeley) %G%"; +static char version[] = "@(#)pass1b.c 3.3 (Berkeley) %G%"; #endif #include @@ -8,6 +8,7 @@ static char version[] = "@(#)pass1b.c 3.2 (Berkeley) %G%"; #include "fsck.h" int pass1bcheck(); +static struct dups *duphead; pass1b() { @@ -19,6 +20,7 @@ pass1b() bzero((char *)&idesc, sizeof(struct inodesc)); idesc.id_type = ADDR; idesc.id_func = pass1bcheck; + duphead = duplist; inumber = 0; for (c = 0; c < sblock.fs_ncg; c++) { for (i = 0; i < sblock.fs_ipg; i++, inumber++) { @@ -40,21 +42,25 @@ out1b: pass1bcheck(idesc) register struct inodesc *idesc; { - register daddr_t *dlp; + register struct dups *dlp; int nfrags, res = KEEPON; daddr_t blkno = idesc->id_blkno; for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { if (outrange(blkno, 1)) res = SKIP; - for (dlp = duplist; dlp < muldup; dlp++) - if (*dlp == blkno) { + for (dlp = duphead; dlp; dlp = dlp->next) { + if (dlp->dup == blkno) { blkerr(idesc->id_number, "DUP", blkno); - *dlp = *--muldup; - *muldup = blkno; - if (muldup == duplist) - return (STOP); + dlp->dup = duphead->dup; + duphead->dup = blkno; + duphead = duphead->next; } + if (dlp == muldup) + break; + } + if (muldup == 0 || duphead == muldup->next) + return (STOP); } return (res); } diff --git a/usr/src/sbin/fsck/pass4.c b/usr/src/sbin/fsck/pass4.c index bd485d6e51..ae3c67fae9 100644 --- a/usr/src/sbin/fsck/pass4.c +++ b/usr/src/sbin/fsck/pass4.c @@ -1,5 +1,5 @@ #ifndef lint -static char version[] = "@(#)pass4.c 3.2 (Berkeley) %G%"; +static char version[] = "@(#)pass4.c 3.3 (Berkeley) %G%"; #endif #include @@ -51,21 +51,27 @@ pass4() pass4check(idesc) register struct inodesc *idesc; { - register daddr_t *dlp; + register struct dups *dlp; int nfrags, res = KEEPON; daddr_t blkno = idesc->id_blkno; for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { - if (outrange(blkno, 1)) + if (outrange(blkno, 1)) { res = SKIP; - else if (getbmap(blkno)) { - for (dlp = duplist; dlp < enddup; dlp++) - if (*dlp == blkno) { - *dlp = *--enddup; - return (KEEPON); - } - clrbmap(blkno); - n_blks--; + } else if (getbmap(blkno)) { + for (dlp = duplist; dlp; dlp = dlp->next) { + if (dlp->dup != blkno) + continue; + dlp->dup = duplist->dup; + dlp = duplist; + duplist = duplist->next; + free(dlp); + break; + } + if (dlp == 0) { + clrbmap(blkno); + n_blks--; + } } } return (res); diff --git a/usr/src/sbin/fsck/setup.c b/usr/src/sbin/fsck/setup.c index f5a3bd9ff9..3cbece97b0 100644 --- a/usr/src/sbin/fsck/setup.c +++ b/usr/src/sbin/fsck/setup.c @@ -1,5 +1,5 @@ #ifndef lint -static char version[] = "@(#)setup.c 3.4 (Berkeley) %G%"; +static char version[] = "@(#)setup.c 3.5 (Berkeley) %G%"; #endif #include @@ -54,7 +54,6 @@ setup(dev) if (preen == 0) printf("\n"); dfile.mod = 0; - muldup = enddup = &duplist[0]; badlnp = &badlncnt[0]; lfdir = 0; initbarea(&sblk); -- 2.20.1