bf: find blocks in inodes

[Brant Cheikes]

Since there seems to be no available utility (AT&T-supplied or PD)
to find the inodes corresponding to a given logical block, I have
written "bf," the block-find utility.  Usage is bf fs blk blk ...,
e.g., "bf /dev/rfp002 14016 2354".  For each block, if bf finds that
it is allocated to a file, it will print the corresponding inode
number.  You may then use ncheck to go from the inode number to the
filename.  A very handy utility when investigating hard disk errors.

Bf has passed lint, compiled with both pcc (on 3.51) and gcc 1.33, and
passed a bunch of test cases.  I think it's pretty clean.  Any
comments, questions, suggestions, (gasp) bug reports, etc., to me
please.

							Brant

-----snip-----snip-----snip-----snip-----snip-----snip-----snip-----snip-----
/*
 * bf.c 1.0
 * Search filesystem for particular blocks, returning corresponding inodes.
 *
 * Brant Cheikes
 * University of Pennsylvania, Department of Computer and Information Science
 * brant at manta.pha.pa.us, brant at linc.cis.upenn.edu, bpa!manta!brant
 *
 * Copyright (C) 1989 Brant A. Cheikes.  All rights reserved.
 *
 * bf is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY.  No author or distributor accepts responsibility to anyone
 * for the consequences of using it or for whether it serves any particular
 * purpose or works at all, unless he says so in writing.
 *
 * Everyone is granted permission to copy, modify and redistribute bf,
 * but only under the conditions described in the GNU General Public License.
 * Among other things, the copyright notice and this notice must be preserved
 * on all copies.
 */

#define KERNEL
#include <stdio.h>
#include <ctype.h>
#include <fcntl.h>
#include <sys/filsys.h>
#include <sys/ino.h>
#include <sys/inode.h>
#include <sys/types.h>
#include <sys/param.h>

/*
 * Macros to manipulate block bitmap.
 * setmapbit(m,b) turns on the bit in bitmap m corresponding to block b.
 * inmap(m,b) evaluates to non-zero if block b's bit is on in map m.
 */
#define setmapbit(m,b) *(m+((int)(b)>>3)) |= (char)(1<<((b)&7))
#define inmap(m,b) (*(m+((b)>>3)) & (char)(1<<((b)&7)))

extern char *calloc();
extern long lseek();

/*
 * Main program.
 */
main(argc,argv)
     int argc;
     char **argv;
{
  int fsdev;			/* file system device */
  int nblk;			/* number of blocks to find */
  struct filsys superblk;	/* the superblock <sys/filsys.h> */
  char *bitmap;			/* bitmap of allocated blocks */
  void getsb();

  /*
   * Verify we were given at least three arguments.
   */
  if (argc < 3) {
    (void) fprintf(stderr,"Usage: %s filesystem numbers\n",*argv);
    exit(1);
  }

  /*
   * Open the filesystem and read the superblock.
   */
  if ((fsdev = open(argv[1],O_RDONLY)) == EOF) {
    char errmsg[100];

    (void) sprintf(errmsg,"cannot open %s",argv[1]);
    (void) perror(errmsg);
    exit(1);
  }
  getsb(fsdev,&superblk);

  /*
   * Initialize the bitmap.
   *
   * The bitmap consists of one bit for each block in the filesystem.
   * Bits in the bitmap are turned on for blocks that are being sought.
   */
  bitmap = calloc((unsigned)((superblk.s_fsize>>3)+1),sizeof(char));
  if (bitmap == (char *)NULL) {
    (void) perror("calloc failed in main");
    exit(1);
  }

  /*
   * Read list of blocks from command line.
   */
  nblk = argc-2; argc -= 2; argv += 2;
  for (; argc-- ; ++argv) {
    long blk;
    extern long atol();

    blk = atol(*argv);
    if (blk == 0) {
      (void) puts("block 0 is superblock!");
      --nblk;
    } else if (blk == 1) {
      (void) puts("block 1 reserved");
      --nblk;
    } else if (blk < superblk.s_isize+3) {
      (void) printf("block %ld in i-list\n",blk);
      --nblk;
    } else if (blk > superblk.s_fsize) {
      (void) printf("block %ld outside fs\n",blk);
      --nblk;
    } else
      /*
       * Turn on the bit in the bitmap corresponding to this block.
       */
      setmapbit(bitmap,blk);
  }

  /*
   * Verify that we still have blocks to look for.
   */
  if (nblk == 0) {
    (void) puts("feh! no blocks");
    exit(0);
  }

  /*
   * Scan the allocated block list.
   */
  return(scan_ilist(fsdev,&superblk,nblk,bitmap));
}

/*
 * Top-level loop of search.
 *
 * We scan thru the i-list, looking at inodes for regular, directory, or
 * fifo files.  For those inodes, we scan the allocated block lists for
 * the blocks we're searching for.
 *
 * Returns non-zero on error.
 */
int
scan_ilist(fp,superb,blks,map)
     int fp, blks;
     struct filsys *superb;
     register char *map;
{
  int inoblk;			/* block in ilist being scanned */
  int inode;			/* current inode */
  int bcnt = 0;			/* count of sought blocks found */
  struct dinode inobuf[INOPB];	/* a block's worth of inodes <sys/ino.h> */

  /*
   * Start at the root inode block (ROOTINO defined in <sys/param.h>).
   * Loop through each block in the ilist.
   */
  for (inoblk = ROOTINO, inode = 1; inoblk < superb->s_isize; ++inoblk) {
    int i;

    /*
     * Read a block.  If an error occurs (like a read failure), just
     * move on to the next block in the ilist.
     */
    if (getblk((long)inoblk,(char *)inobuf,fp))
      continue;

    /*
     * Loop through each inode in this block.
     */
    for (i = 0; i < INOPB; ++i, ++inode) {
      if (inobuf[i].di_mode & IFREG || /* regular file */
	  inobuf[i].di_mode & IFIFO || /* fifo */
	  inobuf[i].di_mode & IFDIR) { /* directory */
	if ((bcnt += scan_inode(fp,inobuf+i,inode,map)) == blks)
	  return(0);
	else if (bcnt > blks) {
	  /*
	   * A rare but possible scenario.  If we find more blocks than
	   * we were looking for, that means that there's at least one
	   * block allocated to more than one file.  So print error
	   * message and quit.
	   */
	  (void) fprintf(stderr,
		    "warning: multiply-allocated block found--run fsck\n");
	  return(1);
	}
      }
    }
  }
  return(0);
}

/*
 * Scan the list of allocated blocks in a particular inode.
 *
 * Input:
 *  fp: pointer to open filesystem
 *  inoptr: pointer to a disk inode
 *  ino: # of inode pointed to by inoptr
 *  map: pointer to block bitmap
 *
 * Returns:
 *  number of blocks found
 */
int
scan_inode(fp,inoptr,ino,map)
     register struct dinode *inoptr;
     int fp, ino;
     register char *map;
{
  int i, bcnt = 0;
  static long daddr[13];
  extern void l3tol();

  /*
   * Convert the di_addr area to an array of block numbers.
   */
  l3tol(daddr,inoptr->di_addr,13);

  /*
   * Scan array.
   */
  for (i = 0; i < 13; ++i) {
    if (daddr[i] && inmap(map,daddr[i])) {
      (void) printf("block %ld inode %d\n",daddr[i],ino);
      ++bcnt;
    }

    /*
     * Scan indirect blocks.
     */
    if (i > 9 && daddr[i])
      bcnt += scan_iblock(fp,daddr[i],i-9,ino,map);
  }
  return(bcnt);
}

/*
 * Recursive scan of indirect blocks.
 * Returns number of sought blocks that were found.
 */
int
scan_iblock(fp,blk,ilevel,ino,map)
     long blk;
     int fp, ilevel, ino;
     register char *map;
{
  if (ilevel < 1 || ilevel > 3) {
    (void) fprintf(stderr,"bad ilevel (%d) in scan_iblock\n",ilevel);
    exit(1);
  } else {
    int i, bcnt = 0;
    long *ib;

    if ((ib = (long *)calloc((unsigned)BSIZE,sizeof(char))) == NULL) {
      perror("calloc failed in scan_iblock");
      exit(1);
    }
    /*
     * Try to read the indirect block.  If that succeeds,
     * check each block that it points to.
     */
    if (getblk(blk,(char *)ib,fp) == 0) {
      for (i = 0; i < BSIZE/sizeof(long); ++i) {
	long iblk = *(ib+i);

	if (iblk) {
	  if (inmap(map,iblk)) {
	    (void) printf("block %ld inode %d\n",iblk,ino);
	    ++bcnt;
	  }
	  if (ilevel > 1)
	    bcnt += scan_iblock(fp,iblk,ilevel-1,ino,map);
	}
      }
    }
    (void) free((char *)ib);
    return(bcnt);
  }
}

/*
 * Read the superblock off the specified (open) device.
 */
void
getsb(fp,superb)
     int fp;
     register struct filsys *superb;
{
  /*
   * SUPERBOFF is offset in bytes of superblock in block 0 of filesystem.
   * It's defined in <sys/param.h>
   */
  if (lseek(fp,(long)SUPERBOFF,0) < 0L) {
    perror("lseek failed in getsb");
    exit(1);
  }
  if (read(fp,(char *)superb,sizeof(struct filsys)) < sizeof(struct filsys)) {
    perror("read error in getsb");
    exit(1);
  }
  if (superb->s_magic != FsMAGIC) {
    (void) fprintf(stderr,"bad magic in superblock\n");
    exit(1);
  }
}

/*
 * getblk(n,bufp,dev)
 *
 * Read logical block #n of device dev into area pointed to by bufp.
 *
 * NB: This uses the (portable) lseek() call rather than diddling the
 * disk controller directly.  As a result it may be slow.
 */
int
getblk(n,bufp,fp)
     long n;
     register char *bufp;
     int fp;
{
  char errmsg[100];

  /*
   * lseek errors are fatal.
   *
   * dbtob(x) defined in <sys/sysmacros.h>
   * disk blocks to bytes
   */
  if (lseek(fp,dbtob(n),0) < 0L) {
    (void) sprintf(errmsg,"lseek to block %ld failed",n);
    (void) perror(errmsg);
    exit(1);
  }
  /*
   * read errors are reported, but do not cause termination.
   *
   * BSIZE is size of a logical block in bytes
   * defined in <sys/param.h>
   */
  if (read(fp,bufp,BSIZE) < BSIZE) {
    (void) sprintf(errmsg,"read error (block %ld)",n);
    (void) perror(errmsg);
    return(1);
  }
  return(0);
}
-----snip-----snip-----snip-----snip-----snip-----snip-----snip-----snip-----
-- 
Brant Cheikes
University of Pennsylvania, Department of Computer and Information Science
brant at manta.pha.pa.us, brant at linc.cis.upenn.edu, bpa!manta!brant