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