Recovering deleted files: saga and code
Mike Morton
mikem at uhccux.uhcc.Hawaii.Edu
Thu Jun 27 17:40:18 AEST 1991
Some weeks back, I posted a plea for help in recovering some text files
which I had stupidly deleted and for which I did not have recent backups.
The response from the net was not overwhelming. One message was "Let
me know how it goes" and another waxed philosophical about how a work
of art is always better the second time you have to do it. Two more
helpful messages arrived a bit late to be of help.
Well, here's what I did, and how it worked. I learned a number of things
about how to do this, but Unix-types probably know all these things, and
may want to skip to my scavenger program, included at the end here.
Background ...
I'm running NeXTstep 2.1 on a NeXTstation. I'm told by a number of people
that the file system is vanilla BSD. I deleted a directory of text files
with the Workspace Manager's "Destroy" command; I think this is the same
as rm'ing them. My best backup was 17 days old (and it had been a very
productive 17 days at that).
When does the disk get updated? ...
There are two problems when one deletes a file. Loosely speaking, (1)
the directory forgets where the file's data are and (2) the file's
data are in unclaimed blocks which may be used when new data are
written to disk. Worse, some opined that disk blocks are allocated
in FILO order, so that the most-recently-freed will be the first
ones allocated.
Everyone agrees that you should do as little as possible after
trashing files, because it will exacerbate problem (2). Some folks
thought that shutting down the machine in an orderly fashion might
cause some allocation. On the advice of a friend at NeXT, I pulled
the plug.
A few people claimed that had I immediately pulled the plug, I might
have been able to prevent the updated directory information from
being written back to disk. Estimates for the meaning of "immediate"
here ranged from a few milliseconds to 15 minutes. Unless other
people use your machine, pulling the plug sounds like a good idea.
Hardware hassles ...
Having shut down the machine, I of course didn't want to boot it;
lots of people thought that would allocate files like crazy. [Don't
you love this advice-by-opinion-polling?]
Opening my NeXTstation was a breeze, as was removing the hard disk.
Plugging it into another NeXT (a cube) turned out to be a huge hassle.
We [at this point my boss was helping, and he was pretty nice about
the whole thing -- thanks, Bob] never got the two hard disks to work
together, and wound up booting the cube from the optical drive, a
device which sounds like a Model 33 Teletype, but which is somewhat
slower.
(I'll skip some grueling details here, but should mention that to
attach my now-naked hard drive to the cube, I couldn't put the back
on the cube. Since the back has the fan, I was obliged to cool the
cube by other means. Despite living in Hawaii, I have no fans, so
I feebly waved a piece of cardboard at the open cube for 2 1/2 hours
when scavenging. Does this make me a "NeXT fan"?)
Free blocks on disk ...
Some include files and pestering some friends at NeXT found that free
chunks of disk come in 8K blocks and 1K fragments. Files are allocated
in blocks whenever possible, and apparently their tail ends get put in
fragments.
The scavenging program ...
My strategy was to write a program which reads every free block on a
disk and saves (NOT on the trashed disk -- further allocation verboten)
those blocks which look "interesting". Here, "interesting" means
consisting largely of ASCII.
I made a mistake here which cost me both time and some data. I assumed
that all the chunks of both sizes would be largely ASCII. I had a
cutoff of 90% ASCII for "interesting", assuming that some characters
(curly quotes, e.g.) weren't standard ASCII.
This is wrong because fragments probably aren't all ASCII -- they tend
to contain the ends of files. A better approach would have been to look
for an ASCII beginning of at least some small number of characters.
It was also slow, because it rescued a lot of data I didn't care about.
I should have looked for something distinctive to C code, such as "/*"
(or in my case, "//", the comment character for Objective-C). [If your
code has 1K consecutive characters without a comment, I'd argue that
it's not worth recovering.]
I also made a low-level mistake, which I noticed only while writing
this up. I assumed that if the eight fragments comprising a block were
all ASCII, I should save them together, and not go on to examine them
individually (the program can save both 8K blocks and 1K fragments).
So after finding an 8K block with lots of ASCII, the program should
save it and not bother checking its fragments. Trouble is, I put in
a return statement after saving a fragment, not a block.
The above bug is fixed in the source below. It's not of interest
per se, but it points out the need for someone (perhaps you, gentle
reader) to write a utility like this and test it under calmer
circumstances.
The X-periment ...
I did try one thing to validate the program before actually using
it on the trashed drive. I created files filled with capital X's,
using up about half the free space on a test drive, then deleted
those files, and scavenged. About half of what I got back was all
X's, which looked right. Trouble is, big files like this exercise
the block recovery, and not fragments.
Road to Recovery ...
As I mentioned, the actual scavenge took 2.5 hours. It recovered
2,000 8K blocks and 3,000 1K fragments. I quickly realized that
a grep for "//" would find what I wanted, but only later noticed
that the scavenger should have done this selection.
I wound up recovering about 40% of my code. Combined with a
somewhat outdated backup, I was able to catch up in 2 days. But
the recovery took a full 4 days. I believe that the total time
was somewhat less than reconstructing all my code from just the
backup would have been. Still, fanning a hot cube at 3 a.m. makes
one wonder about the advisability of this route...
Future Thoughts ...
I don't want to ever think about this topic again, so I'll note some
possible concerns for others to worry about:
* A less selective scavenge might produce so many files that the
receiving file system would be overloaded (one person at NeXT
worried that this would happen to me; it didn't). I did have
to wait forever to delete 5,000 files after I was done grepping.
* Some (all?) Unix file systems lie about the amount of free space.
If you're trying to check your results on the back of an envelope,
remember this.
* It would have been good to store the files I produced in a tree of
directories, instead of just one, for better response (especially
in the NeXT browser).
* One good thing about the program is descriptive file names: it tells
you the level of interesting-ness (ASCII percentage) and which block
or fragment the data came from. This wasn't helpful in my case, but
I bet it could be.
The source ...
Here's the program. Use it as you see fit, but make sure you know what
you're doing, since this is currently a completely special-purpose,
one-night job. No idea how it will work on any other machines, but
I'm placing it in the public domain in hopes that someone will think
about writing a better scavenger.
-- Mike Morton // P.O. Box 11299, Honolulu, HI 96828, (808) 676-6966 HST
Internet: mikem at uhccux.uhcc.hawaii.edu
(this address goes away on 30 June)
(anagrams): Mr. Machine Tool; Ethical Mormon; Chosen Immortal; etc.
/* Recover unallocated blocks from a file system and store them
in a specified directory, which should not be on the same file
system. We attempt to select only blocks with ASCII; others
might save everything, or have another criterion.
No guarantees at all are made for this code.
Mike Morton, 11 June 91
Based very heavily on code from bp at NeXT
*/
/* If you use the same handleBlock() code, this is the threshhold below
which a block is assumed to be garbage. We don't insist on 100% vanilla
ASCII because some text files may contain non-ASCII stuff (ellipsis,
curly quotes, etc).
*/
#define GOODPCT 0.90 /* assume this %, or more, ASCII means worth saving */
#include <stdio.h>
#include <sys/file.h>
#include <sys/param.h>
#include <ufs/fs.h>
#define FRAGSIZE (MAXBSIZE/8) /* size of one sub-block (better name for this?) */
static char *dirName = 0; /* where to store output */
/* save -- Write some data to a new file "filename" inside the directory
specified in the command line args.
*/
static void save (filename, data, length)
char *filename; /* INPUT: name to save under */
unsigned char *data; /* INPUT: stuff to save */
unsigned long length; /* INPUT: length of stuff to save */
{ char pathname [200];
FILE *f;
/* printf (filename); printf ("\n"); return; */
strcpy (pathname, dirName); /* get dir */
strcat (pathname, "/"); /* get dir/ */
strcat (pathname, filename); /* get dir/file */
#if 0 /* useful for writing out only some stuff during testing */
{ static long counter = 0;
if ((counter++ % 200) != 0) return;
printf ("\nsaving: %s", pathname);
}
#endif
f = fopen (pathname, "w+");
if (! f) { printf ("Couldn't open %s\n", pathname); return; }
if (fwrite (data, 1, length, f) != length)
printf ("Write failed!\n", pathname);
fclose (f);
} /* end of save () */
/* handleBlock -- This is called from findFreeData(). We're passed a partly or completely
free block which has been read in, and write out either the block, fragments of it, or
both.
If you're trying to recover some other kind of data (other than ASCII), you want to
change this function to save different stuff when findFreeData() calls it.
*/
static void handleBlock (block, blkNum, freeInfo)
unsigned char *block; /* INPUT: pointer to MAXBSIZE bytes of data */
unsigned long blkNum; /* INPUT: block number on disk */
unsigned char freeInfo; /* INPUT: bit-coded info for eight fragments of block */
/* one-bits mean the frag is free (hence, interesting) */
{ unsigned int fragNum; /* ranges 0..7, for frags of the block */
register unsigned char *subBlock; /* one frag of data */
register unsigned short count;
register unsigned long goodChars; /* count of apparently-ASCII chars in fragment or block */
unsigned char fragBit; /* bit compared against "freeInfo" */
char filename [200];
/* If the 8-frag block is entirely free, write it out if it looks good. We'll do the
8-frag breakup below as well, if it seems good from that p.o.v. */
if (freeInfo == 0xff)
{ subBlock = block; /* set up a working pointer... */
count = MAXBSIZE; /* ...and a loop counter */
goodChars = 0;
/* My hard disk appears to initialize a lot of stuff with many 0x04s, so use 0x05: */
while (count--)
{ if ((*subBlock > 0x05)
&& ((*subBlock & 0x80) == 0)) /* appears to be ASCII? */
goodChars++;
subBlock++;
}
/* If we beat the quota, save this stuff: */
if (goodChars >= (GOODPCT * MAXBSIZE))
{ sprintf (filename, "Block-%03d-%ld", goodChars*100/MAXBSIZE, blkNum);
save (filename, block, MAXBSIZE);
return; /* HACK -- save space and don't fragment blocks we already write out whole */
}
} /* end of handling all-free block */
/* Do the same thing for each fragment. */
for (fragNum = 0; fragNum <= 7; fragNum++)
{ fragBit = (0x80 >> fragNum); /* bits run left-to-right (lower blocks are lefterly) */
if (freeInfo & fragBit) /* interesting fragment? */
{ subBlock = block + (fragNum * FRAGSIZE); /* point to this frag of the block */
count = FRAGSIZE;
goodChars = 0;
while (count--) /* tally the fragment */
{ if ((*subBlock > 0x05)
&& ((*subBlock & 0x80) == 0)) /* appears to be ASCII? */
goodChars++;
subBlock++;
}
/* If we beat the quota, save this stuff: */
if (goodChars >= (GOODPCT * FRAGSIZE))
{ sprintf (filename, "Frag-%03d-%ld-%d", goodChars*100/FRAGSIZE, blkNum, fragNum);
subBlock = block + (fragNum * FRAGSIZE); /* point (again) to this frag of the block */
save (filename, subBlock, FRAGSIZE);
}
} /* end of handling interesting frag */
} /* end of loop through frags */
} /* end of handleBlock () */
/* bread -- Read a block (specified by 1K-block number, not byte address). */
bread (fd, blk, buf, size)
int fd; /* INPUT: file to read from */
daddr_t blk; /* INPUT: block to start at */
char *buf; /* OUTPUT: where to read to */
int size; /* INPUT: how much to read */
{ if (lseek (fd, (long) dbtob (blk), 0) < 0)
{ fprintf(stderr, "bread: lseek error.\n");
perror("lseek");
return 1;
}
if (read (fd, buf, size) != size)
{ fprintf(stderr, "bread: read error.\n");
perror("read");
return 1;
}
return 0;
} /* end of bread () */
/* findFreeData -- Find all the free or partly-free blocks in a file system, and
pass them to "func".
*/
void findFreeData (filesys, func)
char *filesys; /* INPUT: pathname of file system */
void (* func) (); /* INPUT: function to call with blocks */
{ int rawFd; /* file descriptor for raw device */
char slop[MAXBSIZE]; /* big enough to read a whole block */
struct fs *sblock = (struct fs *) slop; /* superblock, overlaid on buffer */
unsigned int cgNum; /* number of a cylinder group */
char cgSlop[MAXBSIZE]; /* big enough to read a whole block */
struct cg* theCg = (struct cg*) cgSlop; /* cylinder group struct, overlaid on buffer */
unsigned char *freeMapPtr; /* pointer into free-block list */
unsigned long blk; /* index into same */
char blockData [MAXBSIZE]; /* data from one block */
unsigned long totBlksRead = 0;
/* Open the device */
if ((rawFd = open(filesys, O_RDONLY, 0)) < 0)
{ perror("open");
fprintf(stderr, "findFreeData: cannot open %s.\n", filesys);
exit(1);
}
sync (); /* get the disk up to date */
/* Read, check, and chat about the superblock. */
if (bread (rawFd, SBLOCK, sblock, SBSIZE))
{ fprintf(stderr, "Error reading superblock.\n"); exit(1); }
if (sblock->fs_magic != FS_MAGIC)
{ fprintf(stderr, "Bad superblock magic number.\n");
exit(1);
}
printf ("Free blocks %ld\n", sblock->fs_cstotal.cs_nbfree);
printf ("Free frags %ld\n", sblock->fs_cstotal.cs_nffree);
/* Loop through all cylinder groups. */
/* @@@ Why must we use -1 in sblock->fs_ncg-1? We get lots of errors without this... */
for (cgNum = 0; cgNum < sblock->fs_ncg-1; cgNum++)
{ printf ("CYLINDER GROUP #%d\n\n", cgNum); fflush (stdout); /* help impatient humans */
if (bread (rawFd, (daddr_t) cgtod (sblock, cgNum), theCg, MAXBSIZE))
{ printf ("Read of cgtod failed.\n"); return; }
if (theCg->cg_magic != CG_MAGIC)
{ printf ("Magic constant in cylinder group info is wrong!\n"); return; }
if (theCg->cg_cgx != cgNum)
{ printf ("Cylinder number in cylinder group info is wrong!\n"); return; }
/* Walk the array of free blocks at the end of the cylinder block. Each byte in
the array is bit-coded -- any '1' bits at all mean some of the block is free.
*/
freeMapPtr = theCg->cg_free;
for (blk = 0; blk < theCg->cg_ndblk; blk++)
{ if (freeMapPtr [blk]) /* nonzero value means partly or entirely free */
{ daddr_t absBlk; /* absolute block number on disk, suitable for bread() */
absBlk = (8*blk) + cgdmin(sblock, cgNum); /* find start of 8K block */
if (bread (rawFd, absBlk, blockData, MAXBSIZE))
printf ("Read failed for block #%ld.\n", absBlk);
else
{ ++totBlksRead;
(* func) (blockData, absBlk, freeMapPtr [blk]); /* pass block & free-info to whomever */
}
} /* end of handling partly/entirely free block */
} /* end of loop through blocks */
} /* end of loop through cylinders */
printf ("\nTotal blocks read: %ld.\n", totBlksRead);
close(rawFd);
} /* end of findFreeData () */
void main(argc, argv)
int argc;
char *argv[];
{ register int argNum = 0; /* argument number */
char *fileSystemName;
argNum = 1;
while (argNum < argc)
{ if (*argv[argNum] == '-')
{ switch (argv[argNum][1])
{ case 's': /* specify file System */
if (++argNum == argc) usage(argv[0]); /* no more args? */
fileSystemName = argv[argNum];
break;
case 'o': /* specify Output directory */
if (++argNum == argc) usage(argv[0]); /* no more args? */
dirName = argv[argNum];
break;
default:
usage(argv[0]);
} /* end of switch on switch */
} /* end of handling "-" token */
else usage(argv[0]);
++argNum;
} /* end of scanning args */
if (fileSystemName == 0) usage(argv[0]); /* insist on a file system name */
if (dirName == 0) usage(argv[0]); /* insist on an output directory */
/* Pass every unallocated block or fragment to handleBlock() */
findFreeData (fileSystemName, handleBlock);
} /* end of main () */
/* Print a usage message and die. */
usage(s)
char *s;
{ printf("usage: %s -s filesystem -o outputdirectory\n", s);
exit(1);
}
More information about the Comp.unix.wizards
mailing list