Infrastructure: Switch testing over to Autotest.

[mLib] / sys / mdup.c

/* -*-c-*-
 *
 * Duplicate multiple files
 *
 * (c) 2008 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include <errno.h>
#include <stdlib.h>

#include <unistd.h>

#include "mdup.h"

/*----- Data structures ---------------------------------------------------*/

typedef struct mdup_fdinfo {

  mdup_fd *f;
  /* Each @fdinfo@ structure refers to one of the caller's @fd@ structures.
   * This is it.
   */

  struct mdup_fdinfo *eqnext, *eqprev;
  /* The caller's request list can contain more than one entry with any given
   * @cur@ descriptor.  We group them together into an equivalence class,
   * which is doubly linked using these fields.
   */

  struct mdup_fdinfo *up;
  /* We require that there be at most one node with any given @want@
   * descriptor (other than @-1@).  There is therefore at most one node whose
   * @want@ is equal to my @cur@.  If such a node exists, @up@ points to it;
   * otherwise @up@ is null.
   */

  struct mdup_fdinfo *down;
  /* Obviously, @down@ links in the opposite direction from @up@.  However,
   * there may be several nodes whose @cur@ equals my @want@; therefore
   * @down@ simply links to one of the nodes in the equivalence class.
   *
   * Unsurprisingly, @down@ is the direction we move during the depth-first
   * traversal phase of the operation.
   */

  struct mdup_fdinfo *dlink;
  /* Nodes with @want == -1@, and nodes where we've broken cycles, are
   * considered `dynamic': their @cur@ has been chosen by @dup@ to be
   * distinct from any existing descriptor, but may collide with a @want@.
   * We check each proposed move against the list of dynamic nodes, and move
   * them out of the way as necessary.  Note that this is really a list of
   * equivalence classes rather than single nodes.
   */

  unsigned state;
  /* The current state of this node.  One of the @ST@ constants described
   * below.
   */
} mdup_fdinfo;

enum {
  ST_READY,
  /* Node has not yet been processed.
   */

  ST_MARK,
  /* Node has been reached by the depth-first traversal, but its descriptor
   * has not yet been moved.  This state is used to detect cycles using the
   * depth-first traversal.
   */

  ST_DONE,
  /* Node has been processed completely.  We have @want == -1@ or
   * @want == cur@.
   */

  ST_BROKEN,
  /* Node has been clobbered in order to break a cycle.  The node's
   * equivalence class has been remapped to a fresh descriptor which (we
   * hope) is not equal to any node's @want@.  All broken nodes are put on
   * the dynamic list: if our hope turns out to be misplaced we can remap the
   * class again.
   */
};

/*----- Main code ---------------------------------------------------------*/

/* --- @DO_EQUIVS@ --- *
 *
 * Perform @body@ once for each @g@ in the equivalence class of @f@.
 */

#define DO_EQUIVS(g, f, body) do {					\
  mdup_fdinfo *f_ = (f), *g_ = f_;					\
  do { mdup_fdinfo *g = g_; g_ = g_->eqnext; body; } while (g_ != f_);	\
} while (0)

/* --- @dump@ --- *
 *
 * Arguments:	@mdup_fdinfo *v@ = pointer to info vector
 *		@size_t n@ = size of vector
 *
 * Returns:	---
 *
 * Use:		Dumps a scary-looking description of the state of @mdup@'s
 *		workings.
 */

#ifdef DEBUG

#include <stdarg.h>
#include <stdio.h>

#define D(x) x

static void dump(mdup_fdinfo *v, size_t n, mdup_fdinfo *dhead,
		 const char *fmt, ...)
{
  int i;
  mdup_fdinfo *f, *g;
  static const char *state[] = { "READY", "MARK", "DONE", "BROKEN" };
  va_list ap;

#define INDEX(p) ((p) ? (int)((p) - (v)) : -1)

  /* --- Dump the items, fairly raw --- */

  va_start(ap, fmt);
  fputs("*** ", stdout);
  vprintf(fmt, ap);
  putchar('\n');
  for (i = 0; i < n; i++) {
    f = &v[i];
    printf("%3d: %-6s %3d -> %3d; "
	   "equivs: %3d, %3d; up: %3d; down: %3d; dyn: %3d\n",
	   i, state[f->state], f->f->cur, f->f->want,
	   INDEX(f->eqprev), INDEX(f->eqnext),
	   INDEX(f->up), INDEX(f->down), INDEX(f->dlink));
  }
  putchar('\n');
  va_end(ap);

#undef INDEX
}

#else

#define D(x)

#endif

/* --- @dfs@ --- *
 *
 * Arguments:	@mdup_fdinfo *f@ = which node to process
 *		@mdup_fdinfo **dhead, ***dtail@ = the dynamic list
 *
 * Returns:	Zero on success, @-1@ on some OS failure.
 *
 * Use:		Recursive depth-first traversal of the descriptor graph.
 *
 *		On exit, the node @f@ will be in state @ST_DONE@ or
 *		@ST_BROKEN@.
 */

static int dfs(mdup_fdinfo *f, mdup_fdinfo **dhead, mdup_fdinfo ***dtail)
{
  mdup_fdinfo *d;
  mdup_fd *ff;
  int can_close_p = 1;
  int fd, ofd;
  int e;

  /* --- Null pointers need no processing --- *
   *
   * Null pointers mark the end of descending chains.
   */

  if (!f)
    return (0);

  /* --- Otherwise our behaviour depends on the node's state --- */

  switch (f->state) {

    /* --- The standard processing, in several phases --- */

    case ST_READY:

      /* --- Mark the class as being in-progress --- */

      DO_EQUIVS(g, f, { g->state = ST_MARK; });

      /* --- Ensure that the our proposed destination is clear --- *
       *
       * The depth-first traversal will leave the node in @ST_DONE@ or
       * @ST_BROKEN@ afterwards; either way, its @cur@ will not be same as
       * our @want@.
       *
       * Note that this can move @%\emph{us}@ to @ST_BROKEN@.  This is not a
       * significant problem.
       */

      DO_EQUIVS(g, f, { if (dfs(g->down, dhead, dtail)) return (-1); });

      /* --- Now the real work can begin --- *
       *
       * For each node in the class, copy the descriptor from @cur@ to
       * @want@.  Before doing this, we must move out of the way any (other)
       * dynamic nodes whose @cur@ matches our @want@.
       *
       * Interestingly, this is the only point in the function where we need
       * nontrivial error handling: if something goes wrong with one of the
       * @dup2@ calls, we must close the descriptors made so far this pass
       * before returning.
       */

      ofd = f->f->cur;
      DO_EQUIVS(g, f, {
	ff = g->f;
	for (d = *dhead; d; d = d->dlink) {
	  if (d != f && d->f->cur == ff->want) {
	    if ((fd = dup(ff->want)) < 0)
	      goto fail;
	    DO_EQUIVS(dd, d, { dd->f->cur = fd; });
	    close(ff->want);
	  }
	}
	if (ff->cur == ff->want)
	  can_close_p = 0;
	else if (dup2(ofd, ff->want) < 0)
	  goto fail;
	goto ok;
      fail:
	e = errno;
	for (g = g->eqprev; g != f->eqprev; g = g->eqprev) {
	  if (g->f->want != g->f->cur)
	    close(g->f->want);
	}
	errno = e;
	return (-1);
      ok:;
      });

      /* --- We're done --- *
       *
       * If the original descriptor isn't wanted by anyone we can (and must)
       * close it.  Nodes can now move to @ST_DONE@.
       */

      if (can_close_p)
	close(ofd);
      DO_EQUIVS(g, f, {
	g->f->cur = g->f->want;
	g->state = ST_DONE;
      });
      break;

    /* --- We have encoutered a cycle --- *
     *
     * The caller wants our descriptor.  We therefore shunt this entire
     * equivalence class to a new descriptor, and link it onto the dynamic
     * list.  Mark it as broken so that we don't try to do anything
     * complicated to it again.
     */

    case ST_MARK:
      ofd = f->f->cur;
      if ((fd = dup(ofd)) < 0)
	return (-1);
      DO_EQUIVS(g, f, {
	g->f->cur = fd;
	g->state = ST_BROKEN;
      });
      f->dlink = **dtail;
      **dtail = f;
      close(ofd);
      break;

    /* --- Nothing to be done here --- *
     *
     * @ST_DONE@ nodes have already been completely processed; @ST_BROKEN@
     * nodes will be fixed up after the main traversal.
     */

    case ST_DONE:
    case ST_BROKEN:
      return (0);

  }
  return (0);
}

/* --- @mdup@ --- *
 *
 * Arguments:	@mdup_fd *v@ = pointer to @mdup_fd@ vector
 *		@size_t n@ = size of vector
 *
 * Returns:	Zero if successful, @-1@ on failure.
 *
 * Use:		Rearranges file descriptors.
 *
 *		The vector @v@ consists of a number of @mdup_fd@ structures.
 *		Each `slot' in the table represents a file.  The slot's @cur@
 *		member names the current file descriptor for this file; the
 *		@want@ member is the file descriptor we want to use for it.
 *		if you want to keep a file alive but don't care which
 *		descriptor it ends up with, set @want = -1@.  Several slots
 *		may specify the same @cur@ descriptor; but they all have to
 *		declare different @want@s (except that several slots may have
 *		@want = -1@.
 *
 *		On successful exit, the function will have rearranged the
 *		file descriptors as requested.  To reflect this, the @cur@
 *		members will all be set to match the (non-@-1@) @want@
 *		members.
 *
 *		If there is a failure, then some rearrangement may have been
 *		performed and some not; the @cur@ members are set to reflect
 *		which file descriptors are to be used.  The old file
 *		descriptors are closed.  (This is different from usual @dup@
 *		behaviour, of course, but essential for reliable error
 *		handling.)  If you want to keep a particular source file
 *		descriptor open as well as make a new copy then specify two
 *		slots with the same @cur@, one with @want = cur@ and one with
 *		the desired output descriptor.
 *
 *		This function works correctly even if the desired remappings
 *		contain cycles.
 */

int mdup(mdup_fd *v, size_t n)
{
  size_t i, j;
  mdup_fdinfo *vv;
  mdup_fdinfo *f, *g, *dhead, **dtail;
  mdup_fd *ff;
  int rc = -1;
  int can_close_p;
  int ofd, fd;

  /* --- Allocate and initialize the table of info nodes --- *
   *
   * Each entry @ff@ in the caller's @v@ array will have a corresponding node
   * @f@ in @vv@ with @f->f = ff@.  Initially each node's links are null, and
   * the node is in the @ST_READY@ state.
   *
   * We also initialize a list given by @dhead@ and @dtail@ containing the
   * entries with `dynamically-assigned' descriptors -- i.e., those whose
   * values we made up using @dup@.  The list lets us detect collisions with
   * explicitly requested descriptors and move the dynamic ones out of the
   * way.
   */

  if ((vv = malloc(sizeof(*vv) * n)) == 0)
    return (-1);

  dhead = 0;
  dtail = &dhead;
  for (i = 0; i < n; i++) {
    f = &vv[i];
    f->f = &v[i];
    f->up = f->down = 0;
    f->eqnext = f->eqprev = 0;
    f->state = ST_READY;
  }

  /* --- Pass one: link the graph together --- *
   *
   * Once this pass is complete, the following properties will hold.
   *
   *   * The nodes which have the same @cur@ are linked together by their
   *	 @eqnext@ and @eqprev@ fields into a doubly-linked circular list
   *	 representing this equivalence class.
   *
   *   * @f->up == g@ if and only if @f->f->cur == g->f->want@.  (Note that
   *	 @want@ fields are unique according to our interface.  We detect
   *	 violations and exit with @errno == EINVAL@.)
   *
   *   * If @f->up == g@ then there exists a @ff@ in the same equivalence
   *	 class (and therefore on @f@'s @eqnext@ list) as @f@ with
   *	 @g->down == ff@.
   */

  for (i = 0; i < n; i++) {
    f = &vv[i];
    if (!f->eqnext)
      f->eqnext = f->eqprev = f;
    for (j = 0; j < n; j++) {
      if (i == j)
	continue;
      g = &vv[j];
      if (f->f->cur == g->f->cur) {
	if (!g->eqnext) {
	  g->eqnext = f->eqnext;
	  g->eqprev = f;
	  f->eqnext->eqprev = g;
	  f->eqnext = g;
	}
      }
      if (g->f->want == -1)
	/* fine */;
      else if (f->f->want == g->f->want) {
	errno = EINVAL;
	goto fail;
      } else if (f->f->cur == g->f->want) {
	f->up = g;
	if (!g->down)
	  g->down = f;
      }
    }
  }

  /* --- Pass two: handle don't-care requests --- *
   *
   * By the end of this pass, we have the following properties.
   *
   *   * Every node will be marked @ST_DONE@.  This is a temporary abuse of
   *	 the @ST_DONE@ state which will be rectified during the next pass.
   *
   *   * Every node with @want == -1@ will have @cur@ set to a freshly
   *	 allocated file descriptor distinct from every previously open file.
   */

  for (i = 0; i < n; i++) {
    f = &vv[i];
    switch (f->state) {
      case ST_DONE:
	break;
      case ST_READY:
	can_close_p = 1;
	DO_EQUIVS(g, f, {
	  ff = g->f;
	  ofd = ff->cur;
	  if (ff->want != -1)
	    can_close_p = 0;
	  else {
	    if ((fd = dup(ofd)) < 0)
	      goto fail;
	    ff->cur = fd;
	  }
	  g->state = ST_DONE;
	});
	if (can_close_p)
	  close(ofd);
	break;
    }
  }

  /* --- Pass three: restore equivalence classes and @down@ links --- *
   *
   * This pass re-establishes the properties from pass one.  Because we've
   * changed some @cur@ members, the equivalence classes will have changed,
   * so we must fix up the @eqnext@ lists and @down@ links.
   *
   * Nodes with @want == -1@ are now finished with (modulo tweaking
   * dynamically allocated descriptors as we process the others), so we leave
   * them in @ST_DONE@; other nodes are restored to @ST_READY@.
   */

  for (i = 0; i < n; i++) {
    f = &vv[i];
    ff = f->f;
    if (ff->want == -1) {
      f->eqnext->eqprev = f->eqprev;
      f->eqprev->eqnext = f->eqnext;
      f->eqnext = f->eqprev = f;
      f->dlink = *dtail;
      *dtail = f;
    } else
      f->state = ST_READY;
  }

  /* --- Pass four: main depth-first traversal --- *
   *
   * See the description of the function @dfs@ above.  After this pass, every
   * node is in state @ST_DONE@ or @ST_BROKEN@.
   */

  for (i = 0; i < n; i++) {
    if (dfs(&vv[i], &dhead, &dtail))
      goto fail;
  }

  /* --- Finished --- */

  rc = 0;
fail:
  free(vv);
  return (rc);
}

/*----- That's all, folks -------------------------------------------------*/