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 | ||
3832000d MW |
140 | static void PRINTF_LIKE(4, 5) IGNORABLE |
141 | dump(mdup_fdinfo *v, size_t n, mdup_fdinfo *dhead, const char *fmt, ...) | |
b317b99d MW |
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 -------------------------------------------------*/ |