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 #define D(x) x
 137
 138 static void dump(mdup_fdinfo *v, size_t n, mdup_fdinfo *dhead,
 139                  const char *fmt, ...)
 140 {
 141   int i;
 142   mdup_fdinfo *f, *g;
 143   static const char *state[] = { "READY", "MARK", "DONE", "BROKEN" };
 144   va_list ap;
 145
 146 #define INDEX(p) ((p) ? (int)((p) - (v)) : -1)
 147
 148   /* --- Dump the items, fairly raw --- */
 149
 150   va_start(ap, fmt);
 151   fputs("*** ", stdout);
 152   vprintf(fmt, ap);
 153   putchar('\n');
 154   for (i = 0; i < n; i++) {
 155     f = &v[i];
 156     printf("%3d: %-6s %3d -> %3d; "
 157            "equivs: %3d, %3d; up: %3d; down: %3d; dyn: %3d\n",
 158            i, state[f->state], f->f->cur, f->f->want,
 159            INDEX(f->eqprev), INDEX(f->eqnext),
 160            INDEX(f->up), INDEX(f->down), INDEX(f->dlink));
 161   }
 162   putchar('\n');
 163   va_end(ap);
 164
 165 #undef INDEX
 166 }
 167
 168 #else
 169
 170 #define D(x)
 171
 172 #endif
 173
 174 /* --- @dfs@ --- *
 175  *
 176  * Arguments:   @mdup_fdinfo *f@ = which node to process
 177  *              @mdup_fdinfo **dhead, ***dtail@ = the dynamic list
 178  *
 179  * Returns:     Zero on success, @-1@ on some OS failure.
 180  *
 181  * Use:         Recursive depth-first traversal of the descriptor graph.
 182  *
 183  *              On exit, the node @f@ will be in state @ST_DONE@ or
 184  *              @ST_BROKEN@.
 185  */
 186
 187 static int dfs(mdup_fdinfo *f, mdup_fdinfo **dhead, mdup_fdinfo ***dtail)
 188 {
 189   mdup_fdinfo *d;
 190   mdup_fd *ff;
 191   int can_close_p = 1;
 192   int fd, ofd;
 193   int e;
 194
 195   /* --- Null pointers need no processing --- *
 196    *
 197    * Null pointers mark the end of descending chains.
 198    */
 199
 200   if (!f)
 201     return (0);
 202
 203   /* --- Otherwise our behaviour depends on the node's state --- */
 204
 205   switch (f->state) {
 206
 207     /* --- The standard processing, in several phases --- */
 208
 209     case ST_READY:
 210
 211       /* --- Mark the class as being in-progress --- */
 212
 213       DO_EQUIVS(g, f, { g->state = ST_MARK; });
 214
 215       /* --- Ensure that the our proposed destination is clear --- *
 216        *
 217        * The depth-first traversal will leave the node in @ST_DONE@ or
 218        * @ST_BROKEN@ afterwards; either way, its @cur@ will not be same as
 219        * our @want@.
 220        *
 221        * Note that this can move @%\emph{us}@ to @ST_BROKEN@.  This is not a
 222        * significant problem.
 223        */
 224
 225       DO_EQUIVS(g, f, { if (dfs(g->down, dhead, dtail)) return (-1); });
 226
 227       /* --- Now the real work can begin --- *
 228        *
 229        * For each node in the class, copy the descriptor from @cur@ to
 230        * @want@.  Before doing this, we must move out of the way any (other)
 231        * dynamic nodes whose @cur@ matches our @want@.
 232        *
 233        * Interestingly, this is the only point in the function where we need
 234        * nontrivial error handling: if something goes wrong with one of the
 235        * @dup2@ calls, we must close the descriptors made so far this pass
 236        * before returning.
 237        */
 238
 239       ofd = f->f->cur;
 240       DO_EQUIVS(g, f, {
 241         ff = g->f;
 242         for (d = *dhead; d; d = d->dlink) {
 243           if (d != f && d->f->cur == ff->want) {
 244             if ((fd = dup(ff->want)) < 0)
 245               goto fail;
 246             DO_EQUIVS(dd, d, { dd->f->cur = fd; });
 247             close(ff->want);
 248           }
 249         }
 250         if (ff->cur == ff->want)
 251           can_close_p = 0;
 252         else if (dup2(ofd, ff->want) < 0)
 253           goto fail;
 254         goto ok;
 255       fail:
 256         e = errno;
 257         for (g = g->eqprev; g != f->eqprev; g = g->eqprev) {
 258           if (g->f->want != g->f->cur)
 259             close(g->f->want);
 260         }
 261         errno = e;
 262         return (-1);
 263       ok:;
 264       });
 265
 266       /* --- We're done --- *
 267        *
 268        * If the original descriptor isn't wanted by anyone we can (and must)
 269        * close it.  Nodes can now move to @ST_DONE@.
 270        */
 271
 272       if (can_close_p)
 273         close(ofd);
 274       DO_EQUIVS(g, f, {
 275         g->f->cur = g->f->want;
 276         g->state = ST_DONE;
 277       });
 278       break;
 279
 280     /* --- We have encoutered a cycle --- *
 281      *
 282      * The caller wants our descriptor.  We therefore shunt this entire
 283      * equivalence class to a new descriptor, and link it onto the dynamic
 284      * list.  Mark it as broken so that we don't try to do anything
 285      * complicated to it again.
 286      */
 287
 288     case ST_MARK:
 289       ofd = f->f->cur;
 290       if ((fd = dup(ofd)) < 0)
 291         return (-1);
 292       DO_EQUIVS(g, f, {
 293         g->f->cur = fd;
 294         g->state = ST_BROKEN;
 295       });
 296       f->dlink = **dtail;
 297       **dtail = f;
 298       close(ofd);
 299       break;
 300
 301     /* --- Nothing to be done here --- *
 302      *
 303      * @ST_DONE@ nodes have already been completely processed; @ST_BROKEN@
 304      * nodes will be fixed up after the main traversal.
 305      */
 306
 307     case ST_DONE:
 308     case ST_BROKEN:
 309       return (0);
 310
 311   }
 312   return (0);
 313 }
 314
 315 /* --- @mdup@ --- *
 316  *
 317  * Arguments:   @mdup_fd *v@ = pointer to @mdup_fd@ vector
 318  *              @size_t n@ = size of vector
 319  *
 320  * Returns:     Zero if successful, @-1@ on failure.
 321  *
 322  * Use:         Rearranges file descriptors.
 323  *
 324  *              The vector @v@ consists of a number of @mdup_fd@ structures.
 325  *              Each `slot' in the table represents a file.  The slot's @cur@
 326  *              member names the current file descriptor for this file; the
 327  *              @want@ member is the file descriptor we want to use for it.
 328  *              if you want to keep a file alive but don't care which
 329  *              descriptor it ends up with, set @want = -1@.  Several slots
 330  *              may specify the same @cur@ descriptor; but they all have to
 331  *              declare different @want@s (except that several slots may have
 332  *              @want = -1@.
 333  *
 334  *              On successful exit, the function will have rearranged the
 335  *              file descriptors as requested.  To reflect this, the @cur@
 336  *              members will all be set to match the (non-@-1@) @want@
 337  *              members.
 338  *
 339  *              If there is a failure, then some rearrangement may have been
 340  *              performed and some not; the @cur@ members are set to reflect
 341  *              which file descriptors are to be used.  The old file
 342  *              descriptors are closed.  (This is different from usual @dup@
 343  *              behaviour, of course, but essential for reliable error
 344  *              handling.)  If you want to keep a particular source file
 345  *              descriptor open as well as make a new copy then specify two
 346  *              slots with the same @cur@, one with @want = cur@ and one with
 347  *              the desired output descriptor.
 348  *
 349  *              This function works correctly even if the desired remappings
 350  *              contain cycles.
 351  */
 352
 353 int mdup(mdup_fd *v, size_t n)
 354 {
 355   size_t i, j;
 356   mdup_fdinfo *vv;
 357   mdup_fdinfo *f, *g, *dhead, **dtail;
 358   mdup_fd *ff;
 359   int rc = -1;
 360   int can_close_p;
 361   int ofd, fd;
 362
 363   /* --- Allocate and initialize the table of info nodes --- *
 364    *
 365    * Each entry @ff@ in the caller's @v@ array will have a corresponding node
 366    * @f@ in @vv@ with @f->f = ff@.  Initially each node's links are null, and
 367    * the node is in the @ST_READY@ state.
 368    *
 369    * We also initialize a list given by @dhead@ and @dtail@ containing the
 370    * entries with `dynamically-assigned' descriptors -- i.e., those whose
 371    * values we made up using @dup@.  The list lets us detect collisions with
 372    * explicitly requested descriptors and move the dynamic ones out of the
 373    * way.
 374    */
 375
 376   if ((vv = malloc(sizeof(*vv) * n)) == 0)
 377     return (-1);
 378
 379   dhead = 0;
 380   dtail = &dhead;
 381   for (i = 0; i < n; i++) {
 382     f = &vv[i];
 383     f->f = &v[i];
 384     f->up = f->down = 0;
 385     f->eqnext = f->eqprev = 0;
 386     f->state = ST_READY;
 387   }
 388
 389   /* --- Pass one: link the graph together --- *
 390    *
 391    * Once this pass is complete, the following properties will hold.
 392    *
 393    *   * The nodes which have the same @cur@ are linked together by their
 394    *     @eqnext@ and @eqprev@ fields into a doubly-linked circular list
 395    *     representing this equivalence class.
 396    *
 397    *   * @f->up == g@ if and only if @f->f->cur == g->f->want@.  (Note that
 398    *     @want@ fields are unique according to our interface.  We detect
 399    *     violations and exit with @errno == EINVAL@.)
 400    *
 401    *   * If @f->up == g@ then there exists a @ff@ in the same equivalence
 402    *     class (and therefore on @f@'s @eqnext@ list) as @f@ with
 403    *     @g->down == ff@.
 404    */
 405
 406   for (i = 0; i < n; i++) {
 407     f = &vv[i];
 408     if (!f->eqnext)
 409       f->eqnext = f->eqprev = f;
 410     for (j = 0; j < n; j++) {
 411       if (i == j)
 412         continue;
 413       g = &vv[j];
 414       if (f->f->cur == g->f->cur) {
 415         if (!g->eqnext) {
 416           g->eqnext = f->eqnext;
 417           g->eqprev = f;
 418           f->eqnext->eqprev = g;
 419           f->eqnext = g;
 420         }
 421       }
 422       if (g->f->want == -1)
 423         /* fine */;
 424       else if (f->f->want == g->f->want) {
 425         errno = EINVAL;
 426         goto fail;
 427       } else if (f->f->cur == g->f->want) {
 428         f->up = g;
 429         if (!g->down)
 430           g->down = f;
 431       }
 432     }
 433   }
 434
 435   /* --- Pass two: handle don't-care requests --- *
 436    *
 437    * By the end of this pass, we have the following properties.
 438    *
 439    *   * Every node will be marked @ST_DONE@.  This is a temporary abuse of
 440    *     the @ST_DONE@ state which will be rectified during the next pass.
 441    *
 442    *   * Every node with @want == -1@ will have @cur@ set to a freshly
 443    *     allocated file descriptor distinct from every previously open file.
 444    */
 445
 446   for (i = 0; i < n; i++) {
 447     f = &vv[i];
 448     switch (f->state) {
 449       case ST_DONE:
 450         break;
 451       case ST_READY:
 452         can_close_p = 1;
 453         DO_EQUIVS(g, f, {
 454           ff = g->f;
 455           ofd = ff->cur;
 456           if (ff->want != -1)
 457             can_close_p = 0;
 458           else {
 459             if ((fd = dup(ofd)) < 0)
 460               goto fail;
 461             ff->cur = fd;
 462           }
 463           g->state = ST_DONE;
 464         });
 465         if (can_close_p)
 466           close(ofd);
 467         break;
 468     }
 469   }
 470
 471   /* --- Pass three: restore equivalence classes and @down@ links --- *
 472    *
 473    * This pass re-establishes the properties from pass one.  Because we've
 474    * changed some @cur@ members, the equivalence classes will have changed,
 475    * so we must fix up the @eqnext@ lists and @down@ links.
 476    *
 477    * Nodes with @want == -1@ are now finished with (modulo tweaking
 478    * dynamically allocated descriptors as we process the others), so we leave
 479    * them in @ST_DONE@; other nodes are restored to @ST_READY@.
 480    */
 481
 482   for (i = 0; i < n; i++) {
 483     f = &vv[i];
 484     ff = f->f;
 485     if (ff->want == -1) {
 486       f->eqnext->eqprev = f->eqprev;
 487       f->eqprev->eqnext = f->eqnext;
 488       f->eqnext = f->eqprev = f;
 489       f->dlink = *dtail;
 490       *dtail = f;
 491     } else
 492       f->state = ST_READY;
 493   }
 494
 495   /* --- Pass four: main depth-first traversal --- *
 496    *
 497    * See the description of the function @dfs@ above.  After this pass, every
 498    * node is in state @ST_DONE@ or @ST_BROKEN@.
 499    */
 500
 501   for (i = 0; i < n; i++) {
 502     if (dfs(&vv[i], &dhead, &dtail))
 503       goto fail;
 504   }
 505
 506   /* --- Finished --- */
 507
 508   rc = 0;
 509 fail:
 510   free(vv);
 511   return (rc);
 512 }
 513
 514 /*----- That's all, folks -------------------------------------------------*/