chiark - git - mdw - mLib/blob - sys/mdup.c

   1 /* -*-c-*-
   2  *
   3  * Duplicate multiple files
   4  *
   5  * (c) 2008 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of the mLib utilities library.
  11  *
  12  * mLib is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * mLib is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with mLib; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <errno.h>
  31 #include <stdlib.h>
  32
  33 #include <unistd.h>
  34
  35 #include "mdup.h"
  36
  37 /*----- Data structures ---------------------------------------------------*/
  38
  39 typedef struct mdup_fdinfo {
  40
  41   mdup_fd *f;
  42   /* Each @fdinfo@ structure refers to one of the caller's @fd@ structures.
  43    * This is it.
  44    */
  45
  46   struct mdup_fdinfo *eqnext, *eqprev;
  47   /* The caller's request list can contain more than one entry with any given
  48    * @cur@ descriptor.  We group them together into an equivalence class,
  49    * which is doubly linked using these fields.
  50    */
  51
  52   struct mdup_fdinfo *up;
  53   /* We require that there be at most one node with any given @want@
  54    * descriptor (other than @-1@).  There is therefore at most one node whose
  55    * @want@ is equal to my @cur@.  If such a node exists, @up@ points to it;
  56    * otherwise @up@ is null.
  57    */
  58
  59   struct mdup_fdinfo *down;
  60   /* Obviously, @down@ links in the opposite direction from @up@.  However,
  61    * there may be several nodes whose @cur@ equals my @want@; therefore
  62    * @down@ simply links to one of the nodes in the equivalence class.
  63    *
  64    * Unsurprisingly, @down@ is the direction we move during the depth-first
  65    * traversal phase of the operation.
  66    */
  67
  68   struct mdup_fdinfo *dlink;
  69   /* Nodes with @want == -1@, and nodes where we've broken cycles, are
  70    * considered `dynamic': their @cur@ has been chosen by @dup@ to be
  71    * distinct from any existing descriptor, but may collide with a @want@.
  72    * We check each proposed move against the list of dynamic nodes, and move
  73    * them out of the way as necessary.  Note that this is really a list of
  74    * equivalence classes rather than single nodes.
  75    */
  76
  77   unsigned state;
  78   /* The current state of this node.  One of the @ST@ constants described
  79    * below.
  80    */
  81 } mdup_fdinfo;
  82
  83 enum {
  84   ST_READY,
  85   /* Node has not yet been processed.
  86    */
  87
  88   ST_MARK,
  89   /* Node has been reached by the depth-first traversal, but its descriptor
  90    * has not yet been moved.  This state is used to detect cycles using the
  91    * depth-first traversal.
  92    */
  93
  94   ST_DONE,
  95   /* Node has been processed completely.  We have @want == -1@ or
  96    * @want == cur@.
  97    */
  98
  99   ST_BROKEN,
 100   /* Node has been clobbered in order to break a cycle.  The node's
 101    * equivalence class has been remapped to a fresh descriptor which (we
 102    * hope) is not equal to any node's @want@.  All broken nodes are put on
 103    * the dynamic list: if our hope turns out to be misplaced we can remap the
 104    * class again.
 105    */
 106 };
 107
 108 /*----- Main code ---------------------------------------------------------*/
 109
 110 /* --- @DO_EQUIVS@ --- *
 111  *
 112  * Perform @body@ once for each @g@ in the equivalence class of @f@.
 113  */
 114
 115 #define DO_EQUIVS(g, f, body) do {                                      \
 116   mdup_fdinfo *f_ = (f), *g_ = f_;                                      \
 117   do { mdup_fdinfo *g = g_; g_ = g_->eqnext; body; } while (g_ != f_);  \
 118 } while (0)
 119
 120 /* --- @dump@ --- *
 121  *
 122  * Arguments:   @mdup_fdinfo *v@ = pointer to info vector
 123  *              @size_t n@ = size of vector
 124  *
 125  * Returns:     ---
 126  *
 127  * Use:         Dumps a scary-looking description of the state of @mdup@'s
 128  *              workings.
 129  */
 130
 131 #ifdef DEBUG
 132
 133 #include <stdarg.h>
 134 #include <stdio.h>
 135
 136 #include "macros.h"
 137
 138 #define D(x) x
 139
 140 static void PRINTF_LIKE(4, 5) IGNORABLE
 141   dump(mdup_fdinfo *v, size_t n, mdup_fdinfo *dhead, const char *fmt, ...)
 142 {
 143   int i;
 144   mdup_fdinfo *f, *g;
 145   static const char *state[] = { "READY", "MARK", "DONE", "BROKEN" };
 146   va_list ap;
 147
 148 #define INDEX(p) ((p) ? (int)((p) - (v)) : -1)
 149
 150   /* --- Dump the items, fairly raw --- */
 151
 152   va_start(ap, fmt);
 153   fputs("*** ", stdout);
 154   vprintf(fmt, ap);
 155   putchar('\n');
 156   for (i = 0; i < n; i++) {
 157     f = &v[i];
 158     printf("%3d: %-6s %3d -> %3d; "
 159            "equivs: %3d, %3d; up: %3d; down: %3d; dyn: %3d\n",
 160            i, state[f->state], f->f->cur, f->f->want,
 161            INDEX(f->eqprev), INDEX(f->eqnext),
 162            INDEX(f->up), INDEX(f->down), INDEX(f->dlink));
 163   }
 164   putchar('\n');
 165   va_end(ap);
 166
 167 #undef INDEX
 168 }
 169
 170 #else
 171
 172 #define D(x)
 173
 174 #endif
 175
 176 /* --- @dfs@ --- *
 177  *
 178  * Arguments:   @mdup_fdinfo *f@ = which node to process
 179  *              @mdup_fdinfo **dhead, ***dtail@ = the dynamic list
 180  *
 181  * Returns:     Zero on success, @-1@ on some OS failure.
 182  *
 183  * Use:         Recursive depth-first traversal of the descriptor graph.
 184  *
 185  *              On exit, the node @f@ will be in state @ST_DONE@ or
 186  *              @ST_BROKEN@.
 187  */
 188
 189 static int dfs(mdup_fdinfo *f, mdup_fdinfo **dhead, mdup_fdinfo ***dtail)
 190 {
 191   mdup_fdinfo *d;
 192   mdup_fd *ff;
 193   int can_close_p = 1;
 194   int fd, ofd;
 195   int e;
 196
 197   /* --- Null pointers need no processing --- *
 198    *
 199    * Null pointers mark the end of descending chains.
 200    */
 201
 202   if (!f)
 203     return (0);
 204
 205   /* --- Otherwise our behaviour depends on the node's state --- */
 206
 207   switch (f->state) {
 208
 209     /* --- The standard processing, in several phases --- */
 210
 211     case ST_READY:
 212
 213       /* --- Mark the class as being in-progress --- */
 214
 215       DO_EQUIVS(g, f, { g->state = ST_MARK; });
 216
 217       /* --- Ensure that the our proposed destination is clear --- *
 218        *
 219        * The depth-first traversal will leave the node in @ST_DONE@ or
 220        * @ST_BROKEN@ afterwards; either way, its @cur@ will not be same as
 221        * our @want@.
 222        *
 223        * Note that this can move @%\emph{us}@ to @ST_BROKEN@.  This is not a
 224        * significant problem.
 225        */
 226
 227       DO_EQUIVS(g, f, { if (dfs(g->down, dhead, dtail)) return (-1); });
 228
 229       /* --- Now the real work can begin --- *
 230        *
 231        * For each node in the class, copy the descriptor from @cur@ to
 232        * @want@.  Before doing this, we must move out of the way any (other)
 233        * dynamic nodes whose @cur@ matches our @want@.
 234        *
 235        * Interestingly, this is the only point in the function where we need
 236        * nontrivial error handling: if something goes wrong with one of the
 237        * @dup2@ calls, we must close the descriptors made so far this pass
 238        * before returning.
 239        */
 240
 241       ofd = f->f->cur;
 242       DO_EQUIVS(g, f, {
 243         ff = g->f;
 244         for (d = *dhead; d; d = d->dlink) {
 245           if (d != f && d->f->cur == ff->want) {
 246             if ((fd = dup(ff->want)) < 0)
 247               goto fail;
 248             DO_EQUIVS(dd, d, { dd->f->cur = fd; });
 249             close(ff->want);
 250           }
 251         }
 252         if (ff->cur == ff->want)
 253           can_close_p = 0;
 254         else if (dup2(ofd, ff->want) < 0)
 255           goto fail;
 256         goto ok;
 257       fail:
 258         e = errno;
 259         for (g = g->eqprev; g != f->eqprev; g = g->eqprev) {
 260           if (g->f->want != g->f->cur)
 261             close(g->f->want);
 262         }
 263         errno = e;
 264         return (-1);
 265       ok:;
 266       });
 267
 268       /* --- We're done --- *
 269        *
 270        * If the original descriptor isn't wanted by anyone we can (and must)
 271        * close it.  Nodes can now move to @ST_DONE@.
 272        */
 273
 274       if (can_close_p)
 275         close(ofd);
 276       DO_EQUIVS(g, f, {
 277         g->f->cur = g->f->want;
 278         g->state = ST_DONE;
 279       });
 280       break;
 281
 282     /* --- We have encoutered a cycle --- *
 283      *
 284      * The caller wants our descriptor.  We therefore shunt this entire
 285      * equivalence class to a new descriptor, and link it onto the dynamic
 286      * list.  Mark it as broken so that we don't try to do anything
 287      * complicated to it again.
 288      */
 289
 290     case ST_MARK:
 291       ofd = f->f->cur;
 292       if ((fd = dup(ofd)) < 0)
 293         return (-1);
 294       DO_EQUIVS(g, f, {
 295         g->f->cur = fd;
 296         g->state = ST_BROKEN;
 297       });
 298       f->dlink = **dtail;
 299       **dtail = f;
 300       close(ofd);
 301       break;
 302
 303     /* --- Nothing to be done here --- *
 304      *
 305      * @ST_DONE@ nodes have already been completely processed; @ST_BROKEN@
 306      * nodes will be fixed up after the main traversal.
 307      */
 308
 309     case ST_DONE:
 310     case ST_BROKEN:
 311       return (0);
 312
 313   }
 314   return (0);
 315 }
 316
 317 /* --- @mdup@ --- *
 318  *
 319  * Arguments:   @mdup_fd *v@ = pointer to @mdup_fd@ vector
 320  *              @size_t n@ = size of vector
 321  *
 322  * Returns:     Zero if successful, @-1@ on failure.
 323  *
 324  * Use:         Rearranges file descriptors.
 325  *
 326  *              The vector @v@ consists of a number of @mdup_fd@ structures.
 327  *              Each `slot' in the table represents a file.  The slot's @cur@
 328  *              member names the current file descriptor for this file; the
 329  *              @want@ member is the file descriptor we want to use for it.
 330  *              if you want to keep a file alive but don't care which
 331  *              descriptor it ends up with, set @want = -1@.  Several slots
 332  *              may specify the same @cur@ descriptor; but they all have to
 333  *              declare different @want@s (except that several slots may have
 334  *              @want = -1@.
 335  *
 336  *              On successful exit, the function will have rearranged the
 337  *              file descriptors as requested.  To reflect this, the @cur@
 338  *              members will all be set to match the (non-@-1@) @want@
 339  *              members.
 340  *
 341  *              If there is a failure, then some rearrangement may have been
 342  *              performed and some not; the @cur@ members are set to reflect
 343  *              which file descriptors are to be used.  The old file
 344  *              descriptors are closed.  (This is different from usual @dup@
 345  *              behaviour, of course, but essential for reliable error
 346  *              handling.)  If you want to keep a particular source file
 347  *              descriptor open as well as make a new copy then specify two
 348  *              slots with the same @cur@, one with @want = cur@ and one with
 349  *              the desired output descriptor.
 350  *
 351  *              This function works correctly even if the desired remappings
 352  *              contain cycles.
 353  */
 354
 355 int mdup(mdup_fd *v, size_t n)
 356 {
 357   size_t i, j;
 358   mdup_fdinfo *vv;
 359   mdup_fdinfo *f, *g, *dhead, **dtail;
 360   mdup_fd *ff;
 361   int rc = -1;
 362   int can_close_p;
 363   int ofd, fd;
 364
 365   /* --- Allocate and initialize the table of info nodes --- *
 366    *
 367    * Each entry @ff@ in the caller's @v@ array will have a corresponding node
 368    * @f@ in @vv@ with @f->f = ff@.  Initially each node's links are null, and
 369    * the node is in the @ST_READY@ state.
 370    *
 371    * We also initialize a list given by @dhead@ and @dtail@ containing the
 372    * entries with `dynamically-assigned' descriptors -- i.e., those whose
 373    * values we made up using @dup@.  The list lets us detect collisions with
 374    * explicitly requested descriptors and move the dynamic ones out of the
 375    * way.
 376    */
 377
 378   if ((vv = malloc(sizeof(*vv) * n)) == 0)
 379     return (-1);
 380
 381   dhead = 0;
 382   dtail = &dhead;
 383   for (i = 0; i < n; i++) {
 384     f = &vv[i];
 385     f->f = &v[i];
 386     f->up = f->down = 0;
 387     f->eqnext = f->eqprev = 0;
 388     f->state = ST_READY;
 389   }
 390
 391   /* --- Pass one: link the graph together --- *
 392    *
 393    * Once this pass is complete, the following properties will hold.
 394    *
 395    *   * The nodes which have the same @cur@ are linked together by their
 396    *     @eqnext@ and @eqprev@ fields into a doubly-linked circular list
 397    *     representing this equivalence class.
 398    *
 399    *   * @f->up == g@ if and only if @f->f->cur == g->f->want@.  (Note that
 400    *     @want@ fields are unique according to our interface.  We detect
 401    *     violations and exit with @errno == EINVAL@.)
 402    *
 403    *   * If @f->up == g@ then there exists a @ff@ in the same equivalence
 404    *     class (and therefore on @f@'s @eqnext@ list) as @f@ with
 405    *     @g->down == ff@.
 406    */
 407
 408   for (i = 0; i < n; i++) {
 409     f = &vv[i];
 410     if (!f->eqnext)
 411       f->eqnext = f->eqprev = f;
 412     for (j = 0; j < n; j++) {
 413       if (i == j)
 414         continue;
 415       g = &vv[j];
 416       if (f->f->cur == g->f->cur) {
 417         if (!g->eqnext) {
 418           g->eqnext = f->eqnext;
 419           g->eqprev = f;
 420           f->eqnext->eqprev = g;
 421           f->eqnext = g;
 422         }
 423       }
 424       if (g->f->want == -1)
 425         /* fine */;
 426       else if (f->f->want == g->f->want) {
 427         errno = EINVAL;
 428         goto fail;
 429       } else if (f->f->cur == g->f->want) {
 430         f->up = g;
 431         if (!g->down)
 432           g->down = f;
 433       }
 434     }
 435   }
 436
 437   /* --- Pass two: handle don't-care requests --- *
 438    *
 439    * By the end of this pass, we have the following properties.
 440    *
 441    *   * Every node will be marked @ST_DONE@.  This is a temporary abuse of
 442    *     the @ST_DONE@ state which will be rectified during the next pass.
 443    *
 444    *   * Every node with @want == -1@ will have @cur@ set to a freshly
 445    *     allocated file descriptor distinct from every previously open file.
 446    */
 447
 448   for (i = 0; i < n; i++) {
 449     f = &vv[i];
 450     switch (f->state) {
 451       case ST_DONE:
 452         break;
 453       case ST_READY:
 454         can_close_p = 1;
 455         DO_EQUIVS(g, f, {
 456           ff = g->f;
 457           ofd = ff->cur;
 458           if (ff->want != -1)
 459             can_close_p = 0;
 460           else {
 461             if ((fd = dup(ofd)) < 0)
 462               goto fail;
 463             ff->cur = fd;
 464           }
 465           g->state = ST_DONE;
 466         });
 467         if (can_close_p)
 468           close(ofd);
 469         break;
 470     }
 471   }
 472
 473   /* --- Pass three: restore equivalence classes and @down@ links --- *
 474    *
 475    * This pass re-establishes the properties from pass one.  Because we've
 476    * changed some @cur@ members, the equivalence classes will have changed,
 477    * so we must fix up the @eqnext@ lists and @down@ links.
 478    *
 479    * Nodes with @want == -1@ are now finished with (modulo tweaking
 480    * dynamically allocated descriptors as we process the others), so we leave
 481    * them in @ST_DONE@; other nodes are restored to @ST_READY@.
 482    */
 483
 484   for (i = 0; i < n; i++) {
 485     f = &vv[i];
 486     ff = f->f;
 487     if (ff->want == -1) {
 488       f->eqnext->eqprev = f->eqprev;
 489       f->eqprev->eqnext = f->eqnext;
 490       f->eqnext = f->eqprev = f;
 491       f->dlink = *dtail;
 492       *dtail = f;
 493     } else
 494       f->state = ST_READY;
 495   }
 496
 497   /* --- Pass four: main depth-first traversal --- *
 498    *
 499    * See the description of the function @dfs@ above.  After this pass, every
 500    * node is in state @ST_DONE@ or @ST_BROKEN@.
 501    */
 502
 503   for (i = 0; i < n; i++) {
 504     if (dfs(&vv[i], &dhead, &dtail))
 505       goto fail;
 506   }
 507
 508   /* --- Finished --- */
 509
 510   rc = 0;
 511 fail:
 512   free(vv);
 513   return (rc);
 514 }
 515
 516 /*----- That's all, folks -------------------------------------------------*/