shred.c

Linux下文件工具。

  longjmp (env, 1);  /* Trivial, just return an indication that it happened */
}

/* FIXME: find a better way.
   This signal-handling code may well end up being ripped out eventually.
   An example of how fragile it is, on an i586-sco-sysv5uw7.0.1 system, with
   gcc-2.95.3pl1, the "rdtsc" instruction causes a segmentation violation.
   So now, the code catches SIGSEGV.  It'd probably be better to remove all
   of that mess and find a better source of random data.  Patches welcome.  */

static void
isaac_seed_machdep (struct isaac_state *s)
{
  RETSIGTYPE (*old_handler[2]) (int);

  /* This is how one does try/except in C */
  old_handler[0] = signal (SIGILL, sigill_handler);
  old_handler[1] = signal (SIGSEGV, sigill_handler);
  if (setjmp (env))  /* ANSI: Must be entire controlling expression */
    {
      signal (SIGILL, old_handler[0]);
      signal (SIGSEGV, old_handler[1]);
    }
  else
    {
# if __i386__
      word32 t[2];
      __asm__ __volatile__ ("rdtsc" : "=a" (t[0]), "=d" (t[1]));
# endif
# if __alpha__
      unsigned long t;
      __asm__ __volatile__ ("rpcc %0" : "=r" (t));
# endif
# if _ARCH_PPC
      /* Code not used because this instruction is available only on first-
	 generation PPCs and evokes a SIGBUS on some Linux 2.4 kernels.  */
      word32 t;
      __asm__ __volatile__ ("mfspr %0,22" : "=r" (t));
# endif
# if __mips
      /* Code not used because this is not accessible from userland */
      word32 t;
      __asm__ __volatile__ ("mfc0\t%0,$9" : "=r" (t));
# endif
# if __sparc__
      /* This doesn't compile on all platforms yet.  How to fix? */
      unsigned long t;
      __asm__ __volatile__ ("rd	%%tick, %0" : "=r" (t));
# endif
     signal (SIGILL, old_handler[0]);
     signal (SIGSEGV, old_handler[1]);
     isaac_seed_data (s, &t, sizeof t);
  }
}

#else /* !(__i386__ || __alpha__) */

/* Do-nothing stub */
# define isaac_seed_machdep(s) (void) 0

#endif /* !(__i386__ || __alpha__) */


/*
 * Get seed material.  16 bytes (128 bits) is plenty, but if we have
 * /dev/urandom, we get 32 bytes = 256 bits for complete overkill.
 */
static void
isaac_seed (struct isaac_state *s)
{
  isaac_seed_start (s);

  { pid_t t = getpid ();   ISAAC_SEED (s, t); }
  { pid_t t = getppid ();  ISAAC_SEED (s, t); }
  { uid_t t = getuid ();   ISAAC_SEED (s, t); }
  { gid_t t = getgid ();   ISAAC_SEED (s, t); }

  {
#if HAVE_GETHRTIME
    hrtime_t t = gethrtime ();
    ISAAC_SEED (s, t);
#else
# if HAVE_CLOCK_GETTIME		/* POSIX ns-resolution */
    struct timespec t;
    clock_gettime (CLOCK_REALTIME, &t);
# else
#  if HAVE_GETTIMEOFDAY
    struct timeval t;
    gettimeofday (&t, (struct timezone *) 0);
#  else
    time_t t;
    t = time (NULL);
#  endif
# endif
#endif
    ISAAC_SEED (s, t);
  }

  isaac_seed_machdep (s);

  {
    char buf[32];
    int fd = open ("/dev/urandom", O_RDONLY | O_NOCTTY);
    if (fd >= 0)
      {
	read (fd, buf, 32);
	close (fd);
	isaac_seed_data (s, buf, 32);
      }
    else
      {
	fd = open ("/dev/random", O_RDONLY | O_NONBLOCK | O_NOCTTY);
	if (fd >= 0)
	  {
	    /* /dev/random is more precious, so use less */
	    read (fd, buf, 16);
	    close (fd);
	    isaac_seed_data (s, buf, 16);
	  }
      }
  }

  isaac_seed_finish (s);
}

/* Single-word RNG built on top of ISAAC */
struct irand_state
{
  word32 r[ISAAC_WORDS];
  unsigned numleft;
  struct isaac_state *s;
};

static void
irand_init (struct irand_state *r, struct isaac_state *s)
{
  r->numleft = 0;
  r->s = s;
}

/*
 * We take from the end of the block deliberately, so if we need
 * only a small number of values, we choose the final ones which are
 * marginally better mixed than the initial ones.
 */
static word32
irand32 (struct irand_state *r)
{
  if (!r->numleft)
    {
      isaac_refill (r->s, r->r);
      r->numleft = ISAAC_WORDS;
    }
  return r->r[--r->numleft];
}

/*
 * Return a uniformly distributed random number between 0 and n,
 * inclusive.  Thus, the result is modulo n+1.
 *
 * Theory of operation: as x steps through every possible 32-bit number,
 * x % n takes each value at least 2^32 / n times (rounded down), but
 * the values less than 2^32 % n are taken one additional time.  Thus,
 * x % n is not perfectly uniform.  To fix this, the values of x less
 * than 2^32 % n are disallowed, and if the RNG produces one, we ask
 * for a new value.
 */
static word32
irand_mod (struct irand_state *r, word32 n)
{
  word32 x;
  word32 lim;

  if (!++n)
    return irand32 (r);

  lim = -n % n;			/* == (2**32-n) % n == 2**32 % n */
  do
    {
      x = irand32 (r);
    }
  while (x < lim);
  return x % n;
}

/*
 * Fill a buffer with a fixed pattern.
 *
 * The buffer must be at least 3 bytes long, even if
 * size is less.  Larger sizes are filled exactly.
 */
static void
fillpattern (int type, unsigned char *r, size_t size)
{
  size_t i;
  unsigned bits = type & 0xfff;

  bits |= bits << 12;
  ((unsigned char *) r)[0] = (bits >> 4) & 255;
  ((unsigned char *) r)[1] = (bits >> 8) & 255;
  ((unsigned char *) r)[2] = bits & 255;
  for (i = 3; i < size / 2; i *= 2)
    memcpy ((char *) r + i, (char *) r, i);
  if (i < size)
    memcpy ((char *) r + i, (char *) r, size - i);

  /* Invert the first bit of every 512-byte sector. */
  if (type & 0x1000)
    for (i = 0; i < size; i += 512)
      r[i] ^= 0x80;
}

/*
 * Fill a buffer, R (of size SIZE_MAX), with random data.
 * SIZE is rounded UP to a multiple of ISAAC_BYTES.
 */
static void
fillrand (struct isaac_state *s, word32 *r, size_t size_max, size_t size)
{
  size = (size + ISAAC_BYTES - 1) / ISAAC_BYTES;
  assert (size <= size_max);

  while (size--)
    {
      isaac_refill (s, r);
      r += ISAAC_WORDS;
    }
}

/*
 * Generate a 6-character (+ nul) pass name string
 * FIXME: allow translation of "random".
 */
#define PASS_NAME_SIZE 7
static void
passname (unsigned char const *data, char name[PASS_NAME_SIZE])
{
  if (data)
    sprintf (name, "%02x%02x%02x", data[0], data[1], data[2]);
  else
    memcpy (name, "random", PASS_NAME_SIZE);
}

/*
 * Do pass number k of n, writing "size" bytes of the given pattern "type"
 * to the file descriptor fd.   Qname, k and n are passed in only for verbose
 * progress message purposes.  If n == 0, no progress messages are printed.
 *
 * If *sizep == -1, the size is unknown, and it will be filled in as soon
 * as writing fails.
 */
static int
dopass (int fd, char const *qname, off_t *sizep, int type,
	struct isaac_state *s, unsigned long k, unsigned long n)
{
  off_t size = *sizep;
  off_t offset;			/* Current file posiiton */
  time_t thresh IF_LINT (= 0);	/* Time to maybe print next status update */
  time_t now = 0;		/* Current time */
  size_t lim;			/* Amount of data to try writing */
  size_t soff;			/* Offset into buffer for next write */
  ssize_t ssize;		/* Return value from write */
#if ISAAC_WORDS > 1024
  word32 r[ISAAC_WORDS * 3];	/* Multiple of 4K and of pattern size */
#else
  word32 r[1024 * 3];		/* Multiple of 4K and of pattern size */
#endif
  char pass_string[PASS_NAME_SIZE];	/* Name of current pass */

  /* Printable previous offset into the file */
  char previous_offset_buf[LONGEST_HUMAN_READABLE + 1];
  char const *previous_human_offset IF_LINT (= 0);

  if (lseek (fd, (off_t) 0, SEEK_SET) == -1)
    {
      error (0, errno, _("%s: cannot rewind"), qname);
      return -1;
    }

  /* Constant fill patterns need only be set up once. */
  if (type >= 0)
    {
      lim = sizeof r;
      if ((off_t) lim > size && size != -1)
	{
	  lim = (size_t) size;
	}
      fillpattern (type, (unsigned char *) r, lim);
      passname ((unsigned char *) r, pass_string);
    }
  else
    {
      passname (0, pass_string);
    }

  /* Set position if first status update */
  if (n)
    {
      error (0, 0, _("%s: pass %lu/%lu (%s)..."), qname, k, n, pass_string);
      thresh = time (NULL) + VERBOSE_UPDATE;
      previous_human_offset = "";
    }

  offset = 0;
  for (;;)
    {
      /* How much to write this time? */
      lim = sizeof r;
      if ((off_t) lim > size - offset && size != -1)
	{
	  if (size < offset)
	    break;
	  lim = (size_t) (size - offset);
	  if (!lim)
	    break;
	}
      if (type < 0)
	fillrand (s, r, sizeof r, lim);
      /* Loop to retry partial writes. */
      for (soff = 0; soff < lim; soff += ssize)
	{
	  ssize = write (fd, (char *) r + soff, lim - soff);
	  if (ssize <= 0)
	    {
	      if ((ssize == 0 || errno == ENOSPC)
		  && size == -1)
		{
		  /* Ah, we have found the end of the file */
		  *sizep = size = offset + soff;
		  break;
		}
	      else
		{
		  int errnum = errno;
		  char buf[LONGEST_HUMAN_READABLE + 1];
		  error (0, errnum, _("%s: error writing at offset %s"),
			 qname,
			 human_readable ((uintmax_t) (offset + soff),
					 buf, 1, 1));
		  /*
		   * I sometimes use shred on bad media, before throwing it
		   * out.  Thus, I don't want it to give up on bad blocks.
		   * This code assumes 512-byte blocks and tries to skip
		   * over them.  It works because lim is always a multiple
		   * of 512, except at the end.
		   */
		  if (errnum == EIO && soff % 512 == 0 && lim >= soff + 512
		      && size != -1)
		    {
		      if (lseek (fd, (off_t) (offset + soff + 512), SEEK_SET)
			  != -1)
			{
			  soff += 512;
			  continue;
			}
		      error (0, errno, "%s: lseek", qname);
		    }
		  return -1;
		}
	    }
	}

      /* Okay, we have written "soff" bytes. */

      if (offset + soff < offset)
	{
	  error (0, 0, _("%s: file too large"), qname);
	  return -1;
	}

      offset += soff;

      /* Time to print progress? */
      if (n
	  && ((offset == size && *previous_human_offset)
	      || thresh <= (now = time (NULL))))
	{
	  char offset_buf[LONGEST_HUMAN_READABLE + 1];
	  char size_buf[LONGEST_HUMAN_READABLE + 1];
	  char const *human_offset
	    = human_readable ((uintmax_t) offset, offset_buf, 1,
			      OUTPUT_BLOCK_SIZE);

	  if (offset == size
	      || !STREQ (previous_human_offset, human_offset))
	    {
	      if (size == -1)
		error (0, 0, _("%s: pass %lu/%lu (%s)...%s"),
		       qname, k, n, pass_string, human_offset);
	      else
		{
		  int percent = (size == 0
				 ? 100
				 : (offset <= TYPE_MAXIMUM (uintmax_t) / 100
				    ? offset * (uintmax_t) 100 / size
				    : offset / (size / 100)));
		  error (0, 0, _("%s: pass %lu/%lu (%s)...%s/%s %d%%"),
			 qname, k, n, pass_string, human_offset,
			 human_readable ((uintmax_t) size, size_buf, 1,
					 OUTPUT_BLOCK_SIZE),
			 percent);
		}

	      strcpy (previous_offset_buf, human_offset);
	      previous_human_offset = previous_offset_buf;
	      thresh = now + VERBOSE_UPDATE;

	      /*
	       * Force periodic syncs to keep displayed progress accurate
	       * FIXME: Should these be present even if -v is not enabled,
	       * to keep the buffer cache from filling with dirty pages?
	       * It's a common problem with programs that do lots of writes,
	       * like mkfs.
	       */
	      if (fdatasync (fd) < 0 && fsync (fd) < 0)
		{
		  error (0, errno, "%s: fsync", qname);
		  return -1;
		}
	    }
	}
    }

  /* Force what we just wrote to hit the media. */
  if (fdatasync (fd) < 0 && fsync (fd) < 0)
    {
      error (0, errno, "%s: fsync", qname);
      return -1;
    }
  return 0;
}

/*
 * The passes start and end with a random pass, and the passes in between
 * are done in random order.  The idea is to deprive someone trying to
 * reverse the process of knowledge of the overwrite patterns, so they
 * have the additional step of figuring out what was done to the disk
 * before they can try to reverse or cancel it.
 *
 * First, all possible 1-bit patterns.  There are two of them.
 * Then, all possible 2-bit patterns.  There are four, but the two
 * which are also 1-bit patterns can be omitted.
 * Then, all possible 3-bit patterns.  Likewise, 8-2 = 6.
 * Then, all possible 4-bit patterns.  16-4 = 12.
 *
 * The basic passes are:
 * 1-bit: 0x000, 0xFFF
 * 2-bit: 0x555, 0xAAA
 * 3-bit: 0x249, 0x492, 0x924, 0x6DB, 0xB6D, 0xDB6 (+ 1-bit)
 *        100100100100         110110110110
 *           9   2   4            D   B   6
 * 4-bit: 0x111, 0x222, 0x333, 0x444, 0x666, 0x777,
 *        0x888, 0x999, 0xBBB, 0xCCC, 0xDDD, 0xEEE (+ 1-bit, 2-bit)
 * Adding three random passes at the beginning, middle and end
 * produces the default 25-pass structure.
 *
 * The next extension would be to 5-bit and 6-bit patterns.
 * There are 30 uncovered 5-bit patterns and 64-8-2 = 46 uncovered
 * 6-bit patterns, so they would increase the time required
 * significantly.  4-bit patterns are enough for most purposes.
 *
 * The main gotcha is that this would require a trickier encoding,
 * since lcm(2,3,4) = 12 bits is easy to fit into an int, but
 * lcm(2,3,4,5) = 60 bits is not.
 *
 * One extension that is included is to complement the first bit in each
 * 512-byte block, to alter the phase of the encoded data in the more
 * complex encodings.  This doesn't apply to MFM, so the 1-bit patterns
 * are considered part of the 3-bit ones and the 2-bit patterns are
 * considered part of the 4-bit patterns.
 *
 *
 * How does the generalization to variable numbers of passes work?
 *
 * Here's how...
 * Have an ordered list of groups of passes.  Each group is a set.
 * Take as many groups as will fit, plus a random subset of the
 * last partial group, and place them into the passes list.
 * Then shuffle the passes list into random order and use that.
 *
 * One extra detail: if we can't include a large enough fraction of the
 * last group to be interesting, then just substitute random passes.
 *
 * If you want more passes than the entire list of groups can
 * provide, just start repeating from the beginning of the list.
 */
static int const
  patterns[] =
{
  -2,				/* 2 random passes */
  2, 0x000, 0xFFF,		/* 1-bit */
  2, 0x555, 0xAAA,		/* 2-bit */
  -1,				/* 1 random pass */
  6, 0x249, 0x492, 0x6DB, 0x924, 0xB6D, 0xDB6,	/* 3-bit */
  12, 0x111, 0x222, 0x333, 0x444, 0x666, 0x777,
  0x888, 0x999, 0xBBB, 0xCCC, 0xDDD, 0xEEE,	/* 4-bit */
  -1,				/* 1 random pass */
	/* The following patterns have the frst bit per block flipped */
  8, 0x1000, 0x1249, 0x1492, 0x16DB, 0x1924, 0x1B6D, 0x1DB6, 0x1FFF,
  14, 0x1111, 0x1222, 0x1333, 0x1444, 0x1555, 0x1666, 0x1777,
  0x1888, 0x1999, 0x1AAA, 0x1BBB, 0x1CCC, 0x1DDD, 0x1EEE,
  -1,				/* 1 random pass */
  0				/* End */
};

/*
 * Generate a random wiping pass pattern with num passes.
 * This is a two-stage process.  First, the passes to include
 * are chosen, and then they are shuffled into the desired
 * order.
 */
static void
genpattern (int *dest, size_t num, struct isaac_state *s)
{
  struct irand_state r;
  size_t randpasses;
  int const *p;
  int *d;
  size_t n;
  size_t accum, top, swap;
  int k;

  if (!num)
    return;

  irand_init (&r, s);

  /* Stage 1: choose the passes to use */
  p = patterns;
  randpasses = 0;
  d = dest;			/* Destination for generated pass list */
  n = num;			/* Passes remaining to fill */

  for (;;)
    {
      k = *p++;			/* Block descriptor word */
      if (!k)
	{			/* Loop back to the beginning */
	  p = patterns;
	}
      else if (k < 0)
	{			/* -k random passes */
	  k = -k;
	  if ((size_t) k >= n)
	    {
	      randpasses += n;