chiark / gitweb /
mdup: New unit for juggling file descriptors.
authorMark Wooding <mdw@distorted.org.uk>
Sun, 4 Jan 2009 13:53:42 +0000 (13:53 +0000)
committerMark Wooding <mdw@distorted.org.uk>
Sun, 4 Jan 2009 16:23:46 +0000 (16:23 +0000)
The mdup function solves the problem of incorrect file descriptor
renumbering in fork/exec.

Makefile.am
mdup-test.c [new file with mode: 0644]
mdup-test.sh [new file with mode: 0755]
mdup.3 [new file with mode: 0644]
mdup.c [new file with mode: 0644]
mdup.h [new file with mode: 0644]

index 7f61828..44ada15 100644 (file)
@@ -403,6 +403,21 @@ pkginclude_HEADERS += lock.h
 libmLib_la_SOURCES     += lock.c
 LIBMANS                        += lock.3
 
+## File descriptor juggling.
+pkginclude_HEADERS     += mdup.h
+libmLib_la_SOURCES     += mdup.c
+LIBMANS                        += mdup.3
+
+check_PROGRAMS         += mdup.t
+mdup_t_SOURCES          = mdup-test.c
+mdup_t_CPPFLAGS                 = $(TEST_CPPFLAGS)
+mdup_t_LDFLAGS          = -static
+
+EXTRA_DIST             += mdup-test.sh
+CLEANFILES             += mdup.[0-9]*.out mdup.[0-9]*.err
+tests:: mdup.t mdup-test.sh
+       $(srcdir)/mdup-test.sh
+
 ## Time arithmetic.
 pkginclude_HEADERS     += tv.h
 libmLib_la_SOURCES     += tv.c
diff --git a/mdup-test.c b/mdup-test.c
new file mode 100644 (file)
index 0000000..d2a198a
--- /dev/null
@@ -0,0 +1,75 @@
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include "mdup.h"
+
+#define MAXFD 256
+
+static void fail(const char *what) { perror(what); exit(1); }
+
+int main(int argc, char *argv[])
+{
+  int i, n;
+  int fd, fd2;
+  struct stat st;
+  int ino[MAXFD];
+  int flag[MAXFD];
+  mdup_fd fds[MAXFD];
+  int win = 1;
+
+  for (i = 0; i < argc - 1; i++) {
+    if (i >= MAXFD) {
+      fprintf(stderr, "too many\n");
+      exit(1);
+    }
+    if (sscanf(argv[i + 1], "%d:%d", &fds[i].cur, &fds[i].want) < 2 ||
+        fds[i].cur >= MAXFD) {
+      fprintf(stderr, "bad syntax\n");
+      exit(1);
+    }
+  }
+  n = argc - 1;
+  for (i = 0; i < MAXFD; i++) flag[i] = -1;
+  for (i = 0; i < n; i++) {
+    fd = fds[i].cur;
+    if (flag[fd] >= 0)
+      ino[i] = ino[flag[fd]];
+    else {
+      flag[fd] = i;
+      if ((fd2 = open(",delete-me",
+                     O_WRONLY | O_CREAT | O_EXCL,
+                     0700)) < 0)
+       fail("creat");
+      unlink(",delete-me");
+      if (fd2 != fd) {
+       if (dup2(fd2, fd) < 0) fail("dup2");
+       close(fd2);
+      }
+      if (fstat(fd, &st)) fail("fstat");
+      ino[i] = st.st_ino;
+    }
+  }
+
+  if (mdup(fds, n)) fail("mdup");
+
+  for (i = 0; i < n; i++) {
+    fd = fds[i].cur;
+    if (fds[i].want != -1 && fds[i].want != fd) {
+      printf("fd %d[%d] != %d\n", fd, i, fds[i].want);
+      win = 0;
+    } else if (fstat(fd, &st)) {
+      printf("fstat %d[%d] failed: %s\n", fd, i, strerror(errno));
+      win = 0;
+    } else if (st.st_ino != ino[i]) {
+      printf("ino %d[%d] wrong\n", fd, i);
+      win = 0;
+    }
+  }
+
+  return (!win);
+}
diff --git a/mdup-test.sh b/mdup-test.sh
new file mode 100755 (executable)
index 0000000..1b34916
--- /dev/null
@@ -0,0 +1,66 @@
+#! /bin/sh
+
+set -e
+: ${test=./mdup.t}
+cases=
+
+###--------------------------------------------------------------------------
+### Set up the test cases.
+###
+### The mdup-test program takes a command-line representation of an mdup_fd
+### array, calls mdup, and checks the result.  In particular, it ensures that
+### the file descriptors returned are the ones asked for, and that the
+### resulting file descriptors actually correspond to the requested files.
+### (It does the latter by comparing inodes before and after.)
+
+## Very simple tests.
+cases="$cases 3:4"
+cases="$cases 4:3"
+
+## Overlapping sources and destinations.
+cases="$cases 4:3,3:5,5:6"
+
+## Repeated sources.
+cases="$cases 3:4,3:3,3:-1"
+cases="$cases 5:8,3:4,3:5,4:6"
+
+## Cycles.
+cases="$cases 5:7,3:4,3:5,4:6,5:3"
+cases="$cases 5:8,3:4,3:5,4:6,5:3"
+
+###--------------------------------------------------------------------------
+### Actually run the tests.
+
+## Initialize counters.
+win=0
+lose=0
+total=0
+
+## Run the tests.
+for case in $cases; do
+  total=$(expr $total + 1)
+  case=$(echo "$case" | sed 'y/,/ /')
+  printf "%d: %-60s  " $total "$case"
+  if $test $case >mdup.$total.out 2>mdup.$total.err; then
+    echo "ok"
+    win=$(expr $win + 1)
+    rm mdup.$total.out mdup.$total.err
+  else
+    echo "FAIL"
+    lose=$(expr $lose + 1)
+  fi
+done
+
+## Announce the outcome.
+if [ $win = $total ]; then
+  echo "All $total tests successful."
+  rc=0
+else
+  echo "FAILED $lose of $total tests."
+  rc=1
+fi
+
+## And exit.
+exit $rc
+
+###----- That's all, folks --------------------------------------------------
diff --git a/mdup.3 b/mdup.3
new file mode 100644 (file)
index 0000000..fc21cd6
--- /dev/null
+++ b/mdup.3
@@ -0,0 +1,186 @@
+.\" -*-nroff-*-
+.de VS
+.sp 1
+.RS
+.nf
+.ft B
+..
+.de VE
+.ft R
+.fi
+.RE
+.sp 1
+..
+.de hP
+.IP
+.ft B
+\h'-\w'\\$1\ 'u'\\$1\ \c
+.ft P
+..
+.ie t .ds o \(bu
+.el .ds o o
+.TH mdup 3 "4 January" "Straylight/Edgeware" "mLib utilities library"
+.SH NAME
+mdup \- renumber file descriptors
+.SH SYNOPSIS
+.B "#include <mLib/mdup.h>"
+
+.BI "int mdup(mdup_fd *" v ", size_t " n ");"
+.SH DESCRIPTION
+The
+.B mdup
+function renumbers file descriptors, using the
+.BR dup (2)
+and
+.BR dup2 (2)
+system calls.  Its arguments are a pointer
+.I v
+to a vector of
+.B mdup_fd
+structures, and the length
+.I n
+of this vector, in elements.  The
+.B mdup_fd
+structure is defined as
+.VS
+typedef struct mdup_fd {
+  int cur;
+  int want;
+} mdup_fd;
+.VE
+Each `slot' (element) in the vector
+.I v
+represents a file.  The slot's
+.B cur
+member names the current file descriptor for this file; the
+.B want
+member is the file descriptor to move it to.  In order to keep a file
+alive when you don't care which descriptor it ends up with, set
+.I want
+= \-1.  Several slots may specify the same
+.B cur
+descriptor; but they all have to declare different
+.BR want s
+(except that several slots may have
+.I want
+= \-1.
+.PP
+On successful exit, the function will have rearranged the file
+descriptors as requested.  To reflect this, the
+.B cur
+members will all be set to match the
+.B want
+members (except where the latter are \-1).
+.PP
+If there is a failure, then some rearrangement may have been performed
+and some not; the
+.B cur
+members are set to reflect which file descriptors are to be used.
+.PP
+The old file descriptors are
+.IR closed .
+This is different from usual
+.BR dup (2)
+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
+.BR cur ,
+one with
+.B want " = " cur
+and one with the desired output descriptor.
+.PP
+The
+.B mdup
+function is capable of arbitrary file descriptor remappings.  In
+particular, it works correctly even if the desired remappings contain
+cycles.
+.SS "Background: the problem that mdup solves"
+The
+.B mdup
+function is intended to be used to adjust file descriptors prior to
+invoking one of the
+.B exec
+system calls.  The standard use of
+.BR dup (2)
+to establish the child process's standard input/output/error files is
+prone to errors in the case where the newly opened file in fact already
+has one of the relevant file descriptors.
+.PP
+Consider the case where we want to run a process with separate pipes
+attached to each of the standard descriptors.  Typical code looks like
+this.
+.VS
+#define P_INIT { \-1, \-1 }
+int p_in[2] = P_INIT, p_out[2] = P_INIT, p_err[2] = P_INIT;
+pid_t kid = -1;
+int i;
+
+if (pipe(p_in) || pipe(p_out) || pipe(p_err)) goto error;
+if ((kid = fork()) < 0) goto error;
+if (!kid) {
+  if (dup2(p_in[0], STDIN_FILENO) < 0 ||
+      dup2(p_out[1], STDOUT_FILENO) < 0 ||
+      dup2(p_err[2], STDERR_FILENO) < 0 ||
+      close(p_in[0]) || close(p_out[0]) || close(p_err[0]) ||
+      close(p_in[1]) || close(p_out[1]) || close(p_err[1]))
+    _exit(127);
+  execvp("/bin/sh", "sh", "-c", "...", (char *)0);
+}
+\&...
+.VE
+Now suppose that, in the parent process, the standard input, output and
+error descriptors are all initially closed.  After the calls to
+.BR pipe (2),
+descriptors 0, 1, and 2 refer to
+.BR p_in[0] ,
+.BR p_in[1] ,
+and
+.B p_out[0]
+respectively.  In the child process, the calls to
+.BR dup2 (2)
+rearrange these.  But then the
+.BR close (2)
+calls will immediately close all three descriptors, before
+.BR exec ing
+the child.
+.PP
+Here's how to rewrite the above function using
+.BR mdup .
+.VS
+#define P_INIT { \-1, \-1 }
+int p_in[2] = P_INIT, p_out[2] = P_INIT, p_err[2] = P_INIT;
+pid_t kid = -1;
+mdup_fd md[3];
+int i;
+
+if (pipe(p_in) || pipe(p_out) || pipe(p_err)) goto error;
+if ((kid = fork()) < 0) goto error;
+if (!kid) {
+  if (close(p_in[1] || close(p_out[0]) || close(p_err[0]))
+    goto _exit(127);
+  md[0].cur = p_in[0];  md[0].want = STDIN_FILENO;
+  md[1].cur = p_out[1]; md[1].want = STDOUT_FILENO;
+  md[2].cur = p_err[1]; md[2].want = STDERR_FILENO;
+  if (mdup(md, 3)) _exit(127);
+  execvp("/bin/sh", "sh", "-c", "...", (char *)0);
+}
+\&...
+.VE
+One can see that, not only is the resulting program more correct, it's
+also simpler.  Note that we close the unwanted ends of the pipes
+.I before
+invoking
+.BR mdup .
+Closing them afterwards risks interfering with the newly assigned
+descriptors which are meant to be passed to the child process.  Note
+also that
+.B mdup
+has taken responsibility for closing the other descriptors for the
+wanted ends of the pipes.
+.SH "SEE ALSO"
+.BR dup (2),
+.BR dup2 (2),
+.BR mLib (3).
+.SH AUTHOR
+Mark Wooding, <mdw@distorted.org.uk>
+
diff --git a/mdup.c b/mdup.c
new file mode 100644 (file)
index 0000000..caf48ab
--- /dev/null
+++ b/mdup.c
@@ -0,0 +1,511 @@
+/* -*-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 -------------------------------------------------*/
diff --git a/mdup.h b/mdup.h
new file mode 100644 (file)
index 0000000..d073ea1
--- /dev/null
+++ b/mdup.h
@@ -0,0 +1,89 @@
+/* -*-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.
+ */
+
+#ifndef MDUP_H
+#define MDUP_H
+
+#ifdef __cplusplus
+  extern "C" {
+#endif
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct mdup_fd {
+  int cur;                             /* Current file descriptor */
+  int want;                            /* File descriptor wanted */
+} mdup_fd;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @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.
+ *
+ * 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.
+ */
+
+extern int mdup(mdup_fd */*v*/, size_t /*n*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+  }
+#endif
+
+#endif