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 | ||
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 -------------------------------------------------*/ |