This is a patch to 4.3 release fsck_ffs to reduce the block map
memory usage in almost all cases. It uses a sparse representation
where regions of all zeros or all ones require no memory.
In the worst case (every region contains both ones and zeros)
it increases memory usage by less than 2%. In the best case
it reduces memory usage for the block map by 98% or so.
CPU usage is increased slightly. Since fsck is very disk-bound
I believe this will not be a problem.
This is a VERY preliminary version. It has been tested on the
few large filesystems ( > 30G) I have. I do not assert that
it is acceptable for production in either format or content.
It contains debug code, #if 0, #if 1, and other constructs
which would not be present in a production version.
I would like people to try it and see how badly it fails.
Please send me any failure information and I will attempt to fix the problem.
Thanks very much.
geoff steckel
diff -Pupr /deep/4.3/src/sbin/fsck_ffs/Makefile fsck_ffs/Makefile
--- /deep/4.3/src/sbin/fsck_ffs/Makefile Sun Sep 21 07:36:37 1997
+++ fsck_ffs/Makefile Mon May 19 15:08:41 2008
@@ -3,7 +3,7 @@
PROG= fsck_ffs
MAN= fsck_ffs.8
SRCS= dir.c inode.c main.c pass1.c pass1b.c pass2.c pass3.c pass4.c \
- pass5.c fsutil.c setup.c utilities.c ffs_subr.c ffs_tables.c
+ pass5.c fsutil.c setup.c utilities.c ffs_subr.c ffs_tables.c blockmap.c
.PATH: ${.CURDIR}/../../sys/ufs/ffs ${.CURDIR}/../fsck
CFLAGS+= -I${.CURDIR}/../fsck
diff -Pupr /deep/4.3/src/sbin/fsck_ffs/blockmap.c fsck_ffs/blockmap.c
--- /deep/4.3/src/sbin/fsck_ffs/blockmap.c Wed Dec 31 19:00:00 1969
+++ fsck_ffs/blockmap.c Mon May 19 17:45:51 2008
@@ -0,0 +1,133 @@
+/*
+ * Copyright (c) 2008 Geoff Steckel. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The names of the contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#define DKTYPENAMES
+#include <sys/param.h>
+#include <sys/time.h>
+#include <ufs/ufs/dinode.h>
+#include <ufs/ffs/fs.h>
+#include <sys/stat.h>
+#include <sys/ioctl.h>
+#include <sys/disklabel.h>
+
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+
+#include "fsck.h"
+#include "extern.h"
+#include "fsutil.h"
+
+#define ERR1 "tsetbit couldn't enter a new item in blockmap\n"
+#define ERR2 "tclrbit couldn't find an item in blockmap\n"
+
+void
+blkmapset(struct blockmapchunk **blockmap, daddr64_t blkno)
+{
+ struct blockmapchunk *thischunk;
+ daddr64_t chunkno;
+ unsigned int ofsinchunk;
+
+ if (blkno >= maxfsblock + 7) {
+ printf("blkmapset called with block %lld out of range\n",
blkno);
+ return;
+ }
+ chunkno = blkno / BLKMAPCHUNK;
+ ofsinchunk = blkno % BLKMAPCHUNK;
+ thischunk = blockmap[chunkno];
+ if ( ! thischunk) {
+ thischunk = calloc(1, sizeof *thischunk);
+ if ( ! thischunk) {
+ printf("blkmapset can't alloc for block %lld\n", blkno);
+ return;
+ }
+ blockmap[chunkno] = thischunk;
+ }
+ setbit(thischunk->bmc_bits, ofsinchunk);
+ thischunk->bmc_count++;
+ if (thischunk->bmc_count == BLKMAPCHUNK) {
+ free(thischunk);
+ blockmap[chunkno] = alloneschunk;
+ }
+}
+
+int
+blkmaptest(struct blockmapchunk **blockmap, daddr64_t blkno)
+{
+ struct blockmapchunk *thischunk;
+ daddr64_t chunkno;
+ unsigned int ofsinchunk;
+
+ if (blkno >= maxfsblock + 7) {
+ printf("blkmaptest called with block %lld out of range\n",
blkno);
+ return 0;
+ }
+ chunkno = blkno / BLKMAPCHUNK;
+ ofsinchunk = blkno % BLKMAPCHUNK;
+ thischunk = blockmap[chunkno];
+
+ return thischunk && isset(thischunk->bmc_bits, ofsinchunk);
+}
+
+void
+blkmapclr(struct blockmapchunk **blockmap, daddr64_t blkno)
+{
+ struct blockmapchunk *thischunk;
+ daddr64_t chunkno;
+ unsigned int ofsinchunk;
+
+ if (blkno >= maxfsblock + 7) {
+ printf("blkmapclr called with block %lld out of range\n",
blkno);
+ return;
+ }
+ chunkno = blkno / BLKMAPCHUNK;
+ ofsinchunk = blkno % BLKMAPCHUNK;
+ thischunk = blockmap[chunkno];
+ if ( ! thischunk) {
+ fprintf(stderr, "freeing free block #%lld\n", blkno);
+ return; /* freeing free chunk? */
+ }
+ if (thischunk->bmc_count == BLKMAPCHUNK) { /* full chunk */
+ thischunk = malloc(sizeof *thischunk);
+ if ( ! thischunk) {
+ write(2, ERR1, (sizeof ERR1) - 1);
+ return;
+ }
+ memset(thischunk->bmc_bits, 0xFF, sizeof thischunk->bmc_bits);
+ thischunk->bmc_count = BLKMAPCHUNK;
+ }
+ clrbit(thischunk->bmc_bits, ofsinchunk);
+ thischunk->bmc_count--;
+ if (thischunk->bmc_count == 0) {
+ free(thischunk);
+ blockmap[chunkno] = NULL;
+ }
+}
diff -Pupr /deep/4.3/src/sbin/fsck_ffs/extern.h fsck_ffs/extern.h
--- /deep/4.3/src/sbin/fsck_ffs/extern.h Mon Jul 9 18:47:24 2007
+++ fsck_ffs/extern.h Mon May 19 17:06:05 2008
@@ -74,3 +74,7 @@ void catch(int);
void catchquit(int);
void voidquit(int);
void catchinfo(int);
+struct blockmapchunk;
+void blkmapset(struct blockmapchunk **, daddr64_t);
+void blkmapclr(struct blockmapchunk **, daddr64_t);
+int blkmaptest(struct blockmapchunk **, daddr64_t);
diff -Pupr /deep/4.3/src/sbin/fsck_ffs/fsck.h fsck_ffs/fsck.h
--- /deep/4.3/src/sbin/fsck_ffs/fsck.h Mon May 19 11:41:14 2008
+++ fsck_ffs/fsck.h Mon May 19 17:05:22 2008
@@ -223,7 +223,9 @@ int fswritefd; /* file descriptor for writing
file sy
int rerun; /* rerun fsck. Only used in non-preen mode */
daddr64_t maxfsblock; /* number of blocks in the file system
*/
-char *blockmap; /* ptr to primary blk allocation map */
+struct blockmapchunk;
+struct blockmapchunk **blockmap; /* ptr to primary blk
allocation map */
+struct blockmapchunk *alloneschunk; /* full chunk for compactness */
ino_t maxino; /* number of inodes in file system */
ino_t lastino; /* last inode in use */
char *statemap; /* ptr to inode state table */
@@ -248,9 +250,15 @@ long *cginosused; /* # of allocated
inodes in each
struct ufs1_dinode ufs1_zino;
struct ufs2_dinode ufs2_zino;
-#define setbmap(blkno) tsetbit(&blockmap, blkno)
-#define testbmap(blkno) tisset(&blockmap, blkno)
-#define clrbmap(blkno) tclrbit(&blockmap, blkno)
+#if 1
+#define setbmap(blkno) blkmapset(blockmap, blkno)
+#define testbmap(blkno) blkmaptest(blockmap, blkno)
+#define clrbmap(blkno) blkmapclr(blockmap, blkno)
+#else
+#define setbmap(blkno) setbit(blockmap, blkno)
+#define testbmap(blkno) isset(blockmap, blkno)
+#define clrbmap(blkno) clrbit(blockmap, blkno)
+#endif
#define STOP 0x01
#define SKIP 0x02
@@ -265,3 +273,11 @@ ino_t allocino(ino_t, int);
int (*info_fn)(char *, size_t);
char *info_filesys;
+
+/* sparse array of allocated disk blocks */
+#define BLKMAPCHUNK 1024 /* # bits in a block map chunk */
+
+struct blockmapchunk {
+ char bmc_bits[howmany(BLKMAPCHUNK,NBBY)];
+ int bmc_count; /* when == BLKMAPCHUNK, replace with allones */
+};
diff -Pupr /deep/4.3/src/sbin/fsck_ffs/setup.c fsck_ffs/setup.c
--- /deep/4.3/src/sbin/fsck_ffs/setup.c Mon Jun 18 16:30:53 2007
+++ fsck_ffs/setup.c Mon May 19 14:53:40 2008
@@ -401,11 +401,17 @@ setup(char *dev)
/*
* allocate and initialize the necessary maps
*/
- bmapsize = roundup(howmany(maxfsblock, NBBY), sizeof(int16_t));
- blockmap = calloc((unsigned)bmapsize, sizeof(char));
+ bmapsize = roundup(howmany(maxfsblock, BLKMAPCHUNK), sizeof(int16_t));
+ blockmap = calloc((unsigned)bmapsize, sizeof(struct blockmapchunk *));
if (blockmap == NULL) {
printf("cannot alloc %u bytes for blockmap\n",
- (unsigned)bmapsize);
+ (unsigned)bmapsize * sizeof (struct blockmapchunk *));
+ goto badsblabel;
+ }
+ alloneschunk = malloc(sizeof(struct blockmapchunk));
+ if (alloneschunk == NULL) {
+ printf("cannot alloc %u bytes for full blockmap chunk\n",
+ sizeof (struct blockmapchunk));
goto badsblabel;
}
statemap = calloc((unsigned)(maxino + 1), sizeof(char));
