Merge from vendor branch BIND:
[dragonfly.git] / contrib / bsdtar / tree.c
1 /*-
2  * Copyright (c) 2003-2004 Tim Kientzle
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer
10  *    in this position and unchanged.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 /*-
28  * This is a new directory-walking system that addresses a number
29  * of problems I've had with fts(3).  In particular, it has no
30  * pathname-length limits (other than the size of 'int'), handles
31  * deep logical traversals, uses considerably less memory, and has
32  * an opaque interface (easier to modify in the future).
33  *
34  * Internally, it keeps a single list of "tree_entry" items that
35  * represent filesystem objects that require further attention.
36  * Non-directories are not kept in memory: they are pulled from
37  * readdir(), returned to the client, then freed as soon as possible.
38  * Any directory entry to be traversed gets pushed onto the stack.
39  *
40  * There is surprisingly little information that needs to be kept for
41  * each item on the stack.  Just the name, depth (represented here as the
42  * string length of the parent directory's pathname), and some markers
43  * indicating how to get back to the parent (via chdir("..") for a
44  * regular dir or via fchdir(2) for a symlink).
45  */
46 #include "bsdtar_platform.h"
47 __FBSDID("$FreeBSD: src/usr.bin/tar/tree.c,v 1.1 2005/04/24 05:53:37 kientzle Exp $");
48
49 #include <sys/stat.h>
50 #include <dirent.h>
51 #include <errno.h>
52 #include <fcntl.h>
53 #include <stdlib.h>
54 #include <string.h>
55 #include <unistd.h>
56
57 #include "tree.h"
58
59 /*
60  * TODO:
61  *    1) Loop checking.
62  *    3) Arbitrary logical traversals by closing/reopening intermediate fds.
63  */
64
65 struct tree_entry {
66         struct tree_entry *next;
67         struct tree_entry *parent;
68         char *name;
69         size_t dirname_length;
70         dev_t dev;
71         ino_t ino;
72         int fd;
73         int flags;
74 };
75
76 /* Definitions for tree_entry.flags bitmap. */
77 #define isDir 1 /* This entry is a regular directory. */
78 #define isDirLink 2 /* This entry is a symbolic link to a directory. */
79 #define needsPreVisit 4 /* This entry needs to be previsited. */
80 #define needsPostVisit 8 /* This entry needs to be postvisited. */
81
82 /*
83  * Local data for this package.
84  */
85 struct tree {
86         struct tree_entry       *stack;
87         struct tree_entry       *current;
88         DIR     *d;
89         int      initialDirFd;
90         int      flags;
91         int      visit_type;
92         int      tree_errno; /* Error code from last failed operation. */
93
94         char    *buff;
95         const char      *basename;
96         size_t   buff_length;
97         size_t   path_length;
98         size_t   dirname_length;
99
100         int      depth;
101         int      openCount;
102         int      maxOpenCount;
103
104         struct stat     lst;
105         struct stat     st;
106 };
107
108 /* Definitions for tree.flags bitmap. */
109 #define needsReturn 8  /* Marks first entry as not having been returned yet. */
110 #define hasStat 16  /* The st entry is set. */
111 #define hasLstat 32 /* The lst entry is set. */
112
113
114 #ifdef HAVE_DIRENT_D_NAMLEN
115 /* BSD extension; avoids need for a strlen() call. */
116 #define D_NAMELEN(dp)   (dp)->d_namlen
117 #else
118 #define D_NAMELEN(dp)   (strlen((dp)->d_name))
119 #endif
120
121 #if 0
122 #include <stdio.h>
123 void
124 tree_dump(struct tree *t, FILE *out)
125 {
126         struct tree_entry *te;
127
128         fprintf(out, "\tdepth: %d\n", t->depth);
129         fprintf(out, "\tbuff: %s\n", t->buff);
130         fprintf(out, "\tpwd: "); fflush(stdout); system("pwd");
131         fprintf(out, "\taccess: %s\n", t->basename);
132         fprintf(out, "\tstack:\n");
133         for(te = t->stack; te != NULL; te = te->next) {
134                 fprintf(out, "\t\tte->name: %s%s%s\n", te->name,
135                     te->flags & needsPreVisit ? "" : " *",
136                     t->current == te ? " (current)" : "");
137         }
138 }
139 #endif
140
141 /*
142  * Add a directory path to the current stack.
143  */
144 static void
145 tree_push(struct tree *t, const char *path)
146 {
147         struct tree_entry *te;
148
149         te = malloc(sizeof(*te));
150         memset(te, 0, sizeof(*te));
151         te->next = t->stack;
152         t->stack = te;
153         te->fd = -1;
154         te->name = strdup(path);
155         te->flags = needsPreVisit | needsPostVisit;
156         te->dirname_length = t->dirname_length;
157 }
158
159 /*
160  * Append a name to the current path.
161  */
162 static void
163 tree_append(struct tree *t, const char *name, size_t name_length)
164 {
165         char *p;
166
167         if (t->buff != NULL)
168                 t->buff[t->dirname_length] = '\0';
169         /* Strip trailing '/' from name, unless entire name is "/". */
170         while (name_length > 1 && name[name_length - 1] == '/')
171                 name_length--;
172
173         /* Resize pathname buffer as needed. */
174         while (name_length + 1 + t->dirname_length >= t->buff_length) {
175                 t->buff_length *= 2;
176                 if (t->buff_length < 1024)
177                         t->buff_length = 1024;
178                 t->buff = realloc(t->buff, t->buff_length);
179         }
180         p = t->buff + t->dirname_length;
181         t->path_length = t->dirname_length + name_length;
182         /* Add a separating '/' if it's needed. */
183         if (t->dirname_length > 0 && p[-1] != '/') {
184                 *p++ = '/';
185                 t->path_length ++;
186         }
187         strncpy(p, name, name_length);
188         p[name_length] = '\0';
189         t->basename = p;
190 }
191
192 /*
193  * Open a directory tree for traversal.
194  */
195 struct tree *
196 tree_open(const char *path)
197 {
198         struct tree *t;
199
200         t = malloc(sizeof(*t));
201         memset(t, 0, sizeof(*t));
202         tree_append(t, path, strlen(path));
203         t->initialDirFd = open(".", O_RDONLY);
204         /*
205          * During most of the traversal, items are set up and then
206          * returned immediately from tree_next().  That doesn't work
207          * for the very first entry, so we set a flag for this special
208          * case.
209          */
210         t->flags = needsReturn;
211         return (t);
212 }
213
214 /*
215  * We've finished a directory; ascend back to the parent.
216  */
217 static void
218 tree_ascend(struct tree *t)
219 {
220         struct tree_entry *te;
221
222         te = t->stack;
223         t->depth--;
224         if (te->flags & isDirLink) {
225                 fchdir(te->fd);
226                 close(te->fd);
227                 t->openCount--;
228         } else {
229                 chdir("..");
230         }
231 }
232
233 /*
234  * Pop the working stack.
235  */
236 static void
237 tree_pop(struct tree *t)
238 {
239         struct tree_entry *te;
240
241         t->buff[t->dirname_length] = '\0';
242         if (t->stack == t->current && t->current != NULL)
243                 t->current = t->current->parent;
244         te = t->stack;
245         t->stack = te->next;
246         t->dirname_length = te->dirname_length;
247         t->basename = t->buff + t->dirname_length;
248         /* Special case: starting dir doesn't skip leading '/'. */
249         if (t->dirname_length > 0)
250                 t->basename++;
251         free(te->name);
252         free(te);
253 }
254
255 /*
256  * Get the next item in the tree traversal.
257  */
258 int
259 tree_next(struct tree *t)
260 {
261         struct dirent *de = NULL;
262
263         /* Handle the startup case by returning the initial entry. */
264         if (t->flags & needsReturn) {
265                 t->flags &= ~needsReturn;
266                 return (t->visit_type = TREE_REGULAR);
267         }
268
269         while (t->stack != NULL) {
270                 /* If there's an open dir, get the next entry from there. */
271                 while (t->d != NULL) {
272                         de = readdir(t->d);
273                         if (de == NULL) {
274                                 closedir(t->d);
275                                 t->d = NULL;
276                         } else if (de->d_name[0] == '.'
277                             && de->d_name[1] == '\0') {
278                                 /* Skip '.' */
279                         } else if (de->d_name[0] == '.'
280                             && de->d_name[1] == '.'
281                             && de->d_name[2] == '\0') {
282                                 /* Skip '..' */
283                         } else {
284                                 /*
285                                  * Append the path to the current path
286                                  * and return it.
287                                  */
288                                 tree_append(t, de->d_name, D_NAMELEN(de));
289                                 t->flags &= ~hasLstat;
290                                 t->flags &= ~hasStat;
291                                 return (t->visit_type = TREE_REGULAR);
292                         }
293                 }
294
295                 /* If the current dir needs to be visited, set it up. */
296                 if (t->stack->flags & needsPreVisit) {
297                         t->current = t->stack;
298                         tree_append(t, t->stack->name, strlen(t->stack->name));
299                         t->stack->flags &= ~needsPreVisit;
300                         /* If it is a link, set up fd for the ascent. */
301                         if (t->stack->flags & isDirLink) {
302                                 t->stack->fd = open(".", O_RDONLY);
303                                 t->openCount++;
304                                 if (t->openCount > t->maxOpenCount)
305                                         t->maxOpenCount = t->openCount;
306                         }
307                         t->dirname_length = t->path_length;
308                         if (chdir(t->stack->name) != 0) {
309                                 /* chdir() failed; return error */
310                                 tree_pop(t);
311                                 t->tree_errno = errno;
312                                 return (t->visit_type = TREE_ERROR);
313                         }
314                         t->d = opendir(".");
315                         if (t->d == NULL) {
316                                 tree_pop(t);
317                                 t->tree_errno = errno;
318                                 return (t->visit_type = TREE_ERROR);
319                         }
320                         t->depth++;
321                         t->flags &= ~hasLstat;
322                         t->flags &= ~hasStat;
323                         t->basename = ".";
324                         return (t->visit_type = TREE_POSTDESCENT);
325                 }
326
327                 /* We've done everything necessary for the top stack entry. */
328                 if (t->stack->flags & needsPostVisit) {
329                         tree_ascend(t);
330                         tree_pop(t);
331                         t->flags &= ~hasLstat;
332                         t->flags &= ~hasStat;
333                         return (t->visit_type = TREE_POSTASCENT);
334                 }
335         }
336         return (t->visit_type = 0);
337 }
338
339 /*
340  * Return error code.
341  */
342 int
343 tree_errno(struct tree *t)
344 {
345         return (t->tree_errno);
346 }
347
348 /*
349  * Called by the client to mark the directory just returned from
350  * tree_next() as needing to be visited.
351  */
352 void
353 tree_descend(struct tree *t)
354 {
355         if (t->visit_type != TREE_REGULAR)
356                 return;
357
358         if (tree_current_is_physical_dir(t)) {
359                 tree_push(t, t->basename);
360                 t->stack->flags |= isDir;
361         } else if (tree_current_is_dir(t)) {
362                 tree_push(t, t->basename);
363                 t->stack->flags |= isDirLink;
364         }
365 }
366
367 /*
368  * Get the stat() data for the entry just returned from tree_next().
369  */
370 const struct stat *
371 tree_current_stat(struct tree *t)
372 {
373         if (!(t->flags & hasStat)) {
374                 if (stat(t->basename, &t->st) != 0)
375                         return NULL;
376                 t->flags |= hasStat;
377         }
378         return (&t->st);
379 }
380
381 /*
382  * Get the lstat() data for the entry just returned from tree_next().
383  */
384 const struct stat *
385 tree_current_lstat(struct tree *t)
386 {
387         if (!(t->flags & hasLstat)) {
388                 if (lstat(t->basename, &t->lst) != 0)
389                         return NULL;
390                 t->flags |= hasLstat;
391         }
392         return (&t->lst);
393 }
394
395 /*
396  * Test whether current entry is a dir or dir link.
397  */
398 int
399 tree_current_is_dir(struct tree *t)
400 {
401         /* If we've already pulled stat(), just use that. */
402         if (t->flags & hasStat)
403                 return (S_ISDIR(tree_current_stat(t)->st_mode));
404
405         /* If we've already pulled lstat(), we may be able to use that. */
406         if (t->flags & hasLstat) {
407                 /* If lstat() says it's a dir, it must be a dir. */
408                 if (S_ISDIR(tree_current_lstat(t)->st_mode))
409                         return 1;
410                 /* If it's not a dir and not a link, we're done. */
411                 if (!S_ISLNK(tree_current_lstat(t)->st_mode))
412                         return 0;
413                 /*
414                  * If the above two tests fail, then it's a link, but
415                  * we don't know whether it's a link to a dir or a
416                  * non-dir.
417                  */
418         }
419
420         /* TODO: Use a more efficient mechanism when available. */
421         return (S_ISDIR(tree_current_stat(t)->st_mode));
422 }
423
424 /*
425  * Test whether current entry is a physical directory.
426  */
427 int
428 tree_current_is_physical_dir(struct tree *t)
429 {
430         /* If we've already pulled lstat(), just use that. */
431         if (t->flags & hasLstat)
432                 return (S_ISDIR(tree_current_lstat(t)->st_mode));
433
434         /* TODO: Use a more efficient mechanism when available. */
435         return (S_ISDIR(tree_current_lstat(t)->st_mode));
436 }
437
438 /*
439  * Test whether current entry is a symbolic link.
440  */
441 int
442 tree_current_is_physical_link(struct tree *t)
443 {
444         /* If we've already pulled lstat(), just use that. */
445         if (t->flags & hasLstat)
446                 return (S_ISLNK(tree_current_lstat(t)->st_mode));
447
448         /* TODO: Use a more efficient mechanism when available. */
449         return (S_ISLNK(tree_current_lstat(t)->st_mode));
450 }
451
452 /*
453  * Return the access path for the entry just returned from tree_next().
454  */
455 const char *
456 tree_current_access_path(struct tree *t)
457 {
458         return (t->basename);
459 }
460
461 /*
462  * Return the full path for the entry just returned from tree_next().
463  */
464 const char *
465 tree_current_path(struct tree *t)
466 {
467         return (t->buff);
468 }
469
470 /*
471  * Return the length of the path for the entry just returned from tree_next().
472  */
473 size_t
474 tree_current_pathlen(struct tree *t)
475 {
476         return (t->path_length);
477 }
478
479 /*
480  * Return the nesting depth of the entry just returned from tree_next().
481  */
482 int
483 tree_current_depth(struct tree *t)
484 {
485         return (t->depth);
486 }
487
488 /*
489  * Terminate the traversal and release any resources.
490  */
491 void
492 tree_close(struct tree *t)
493 {
494         /* Release anything remaining in the stack. */
495         while (t->stack != NULL)
496                 tree_pop(t);
497         if (t->buff)
498                 free(t->buff);
499         /* chdir() back to where we started. */
500         if (t->initialDirFd >= 0) {
501                 fchdir(t->initialDirFd);
502                 close(t->initialDirFd);
503                 t->initialDirFd = -1;
504         }
505         free(t);
506 }