#include <fcntl.h>
#include <errno.h>
#include "dirfd.h"
-#include "cycle-check.h"
-#include "hash.h"
-#include "unistd-safer.h"
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
-#if HAVE_INTTYPES_H
-# include <inttypes.h>
-#endif
-#if HAVE_STDINT_H
-# include <stdint.h>
-#endif
-#if ULONG_MAX < ULLONG_MAX
-# define LONGEST_MODIFIER "ll"
-#else
-# define LONGEST_MODIFIER "l"
-#endif
-#if PRI_MACROS_BROKEN
-# undef PRIuMAX
-#endif
-#ifndef PRIuMAX
-# define PRIuMAX LONGEST_MODIFIER "u"
-#endif
#if defined _LIBC
# include <dirent.h>
static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
internal_function;
+#if _LGPL_PACKAGE
+static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
+static void leave_dir (FTS *fts, FTSENT *ent) {}
+static bool setup_dir (FTS *fts) { return true; }
+static void free_dir (FTS *fts) {}
+static int fd_safer (int fd) { return fd; }
+#else
+# include "fts-cycle.c"
+# include "unistd-safer.h"
+#endif
+
#ifndef MAX
# define MAX(a,b) ((a) > (b) ? (a) : (b))
#endif
#define BNAMES 2 /* fts_children, names only */
#define BREAD 3 /* fts_read */
-#define HT_INITIAL_SIZE 31
-
#if FTS_DEBUG
-bool fts_debug = false;
+# include <inttypes.h>
+# include <stdint.h>
# include <stdio.h>
+bool fts_debug = false;
# define Dprintf(x) do { if (fts_debug) printf x; } while (0)
#else
# define Dprintf(x)
#endif
-#define ENTER_DIR(Fts, Ent, Tag) \
- do { \
- Dprintf ((" %s-entering: %s\n", Tag, (Ent)->fts_path)); \
- enter_dir (sp, p); \
- } while (0)
-
#define LEAVE_DIR(Fts, Ent, Tag) \
- do { \
+ do \
+ { \
Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
- leave_dir (sp, p); \
- } while (0)
-
-/* Use these each of these to map a device/inode pair to an FTSENT. */
-struct Active_dir
-{
- dev_t dev;
- ino_t ino;
- FTSENT *fts_ent;
-};
-
-static bool
-AD_compare (void const *x, void const *y)
-{
- struct Active_dir const *ax = x;
- struct Active_dir const *ay = y;
- return ax->ino == ay->ino
- && ax->dev == ay->dev;
-}
-
-static size_t
-AD_hash (void const *x, size_t table_size)
-{
- struct Active_dir const *ax = x;
- return (uintmax_t) ax->ino % table_size;
-}
-
-static void
-enter_dir (FTS *fts, FTSENT *ent)
-{
- if (fts->active_dir_ht)
- {
- struct stat const *st = ent->fts_statp;
- struct Active_dir *ad = malloc (sizeof (struct Active_dir));
- struct Active_dir *ad_from_table;
-
- if (ad == NULL)
- goto give_up;
-
- ad->dev = st->st_dev;
- ad->ino = st->st_ino;
- ad->fts_ent = ent;
-
- /* See if we've already encountered this directory.
- This can happen when following symlinks as well as
- with a corrupted directory hierarchy. */
- ad_from_table = hash_insert (fts->active_dir_ht, ad);
-
- if (ad_from_table == NULL)
- {
- give_up:
- /* Insertion failed due to lack of memory. Free the hash
- table and turn off this sort of cycle detection. */
- hash_free (fts->active_dir_ht);
- fts->active_dir_ht = NULL;
- return;
- }
-
- if (ad_from_table != ad)
- {
- /* There was an entry with matching dev/inode already in the table.
- Record the fact that we've found a cycle. */
- ent->fts_cycle = ad_from_table->fts_ent;
- ent->fts_info = FTS_DC;
-
- /* ad was not inserted, so free it. */
- free (ad);
- }
- }
- else if (fts->cycle_state)
- {
- if (cycle_check (fts->cycle_state, ent->fts_statp))
- {
- /* FIXME: setting fts_cycle like this isn't proper.
- To do what the documentation requires, we'd have to
- go around the cycle again and find the right entry.
- But no callers in coreutils use the fts_cycle member. */
- ent->fts_cycle = ent;
- ent->fts_info = FTS_DC;
- }
- }
-}
-
-static void
-leave_dir (FTS *fts, FTSENT *ent)
-{
- if (fts->active_dir_ht)
- {
- struct stat const *st = ent->fts_statp;
- struct Active_dir obj;
- void *found;
- obj.dev = st->st_dev;
- obj.ino = st->st_ino;
- found = hash_delete (fts->active_dir_ht, &obj);
- if (!found)
- abort ();
- free (found);
- }
-}
+ leave_dir (Fts, Ent); \
+ } \
+ while (false)
/* Open the directory DIR if possible, and return a file
descriptor. Return -1 and set errno on failure. It doesn't matter
SET(FTS_NOCHDIR);
/*
- * Start out with 1K of path space, and enough, in any case,
- * to hold the user's paths.
+ * Start out with 1K of file name space, and enough, in any case,
+ * to hold the user's file names.
*/
#ifndef MAXPATHLEN
# define MAXPATHLEN 1024
/* Allocate/initialize root(s). */
for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
- /* Don't allow zero-length paths. */
+ /* Don't allow zero-length file names. */
if ((len = strlen(*argv)) == 0) {
__set_errno (ENOENT);
goto mem3;
goto mem3;
sp->fts_cur->fts_link = root;
sp->fts_cur->fts_info = FTS_INIT;
-
- if (ISSET (FTS_TIGHT_CYCLE_CHECK))
- {
- sp->active_dir_ht = hash_initialize (HT_INITIAL_SIZE,
- NULL, AD_hash,
- AD_compare, free);
- if (sp->active_dir_ht == NULL)
- goto mem3;
- sp->cycle_state = malloc (sizeof *sp->cycle_state);
- }
- else
- {
- sp->cycle_state = malloc (sizeof *sp->cycle_state);
- if (sp->cycle_state == NULL)
- goto mem3;
- cycle_check_init (sp->cycle_state);
- sp->active_dir_ht = NULL;
- }
+ if (! setup_dir (sp))
+ goto mem3;
/*
* If using chdir(2), grab a file descriptor pointing to dot to ensure
- * that we can get back here; this could be avoided for some paths,
+ * that we can get back here; this could be avoided for some file names,
* but almost certainly not worth the effort. Slashes, symbolic links,
* and ".." are all fairly nasty problems. Note, if we can't get the
* descriptor we run anyway, just more slowly.
* actually enter the directory until after the preorder visit, set
* the fts_accpath field specially so the chdir gets done to the right
* place and the user can access the first node. From fts_open it's
- * known that the path will fit.
+ * known that the file name will fit.
*/
len = p->fts_pathlen = p->fts_namelen;
memmove(sp->fts_path, p->fts_name, len + 1);
free(p);
}
- /* Free up child linked list, sort array, path buffer. */
+ /* Free up child linked list, sort array, file name buffer. */
if (sp->fts_child)
fts_lfree(sp->fts_child);
if (sp->fts_array)
(void)close(sp->fts_rfd);
}
- /* Free any memory used for cycle detection. */
- if (sp->active_dir_ht)
- hash_free (sp->active_dir_ht);
- if (sp->cycle_state)
- free (sp->cycle_state);
+ free_dir (sp);
/* Free up the stream pointer. */
free(sp);
}
/*
- * Special case of "/" at the end of the path so that slashes aren't
- * appended which would cause paths to be written as "....//foo".
+ * Special case of "/" at the end of the file name so that slashes aren't
+ * appended which would cause file names to be written as "....//foo".
*/
#define NAPPEND(p) \
(p->fts_path[p->fts_pathlen - 1] == '/' \
} else
p->fts_flags |= FTS_SYMFOLLOW;
}
- if (p->fts_info == FTS_D)
- ENTER_DIR (sp, p, "7");
- return (p);
+ goto check_for_dir;
}
/* Directory in pre-order. */
/*
* If reached the top, return to the original directory (or
- * the root of the tree), and load the paths for the next root.
+ * the root of the tree), and load the file names for the next
+ * root.
*/
if (p->fts_level == FTS_ROOTLEVEL) {
if (FCHDIR(sp, sp->fts_rfd)) {
return (NULL);
}
fts_load(sp, p);
- if (p->fts_info == FTS_D)
- ENTER_DIR (sp, p, "8");
- return (sp->fts_cur = p);
+ goto check_for_dir;
}
/*
name: t = sp->fts_path + NAPPEND(p->fts_parent);
*t++ = '/';
memmove(t, p->fts_name, p->fts_namelen + 1);
+check_for_dir:
+ sp->fts_cur = p;
if (p->fts_info == FTS_D)
- ENTER_DIR (sp, p, "9");
- return (sp->fts_cur = p);
+ {
+ Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
+ if (! enter_dir (sp, p))
+ {
+ __set_errno (ENOMEM);
+ return NULL;
+ }
+ }
+ return p;
}
/* Move up to the parent node. */
return (sp->fts_cur = NULL);
}
- /* NUL terminate the pathname. */
+ /* NUL terminate the file name. */
sp->fts_path[p->fts_pathlen] = '\0';
/*
instr = BCHILD;
/*
- * If using chdir on a relative path and called BEFORE fts_read does
- * its chdir to the root of a traversal, we can lose -- we need to
+ * If using chdir on a relative file name and called BEFORE fts_read
+ * does its chdir to the root of a traversal, we can lose -- we need to
* chdir into the subdirectory, and we don't know where the current
* directory is, so we can't get back so that the upcoming chdir by
* fts_read will work.
else
oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
#else
-# define __opendir2(path, flag) opendir(path)
+# define __opendir2(file, flag) opendir(file)
#endif
if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
if (type == BREAD) {
* but set a flag so we don't chdir after the post-order visit.
* We won't be able to stat anything, but we can still return the
* names themselves. Note, that since fts_read won't be able to
- * chdir into the directory, it will have to return different path
+ * chdir into the directory, it will have to return different file
* names than before, i.e. "a/b" instead of "b". Since the node
* has already been visited in pre-order, have to wait until the
* post-order visit to return the error. There is a special case
/*
* Figure out the max file name length that can be stored in the
- * current path -- the inner loop allocates more path as necessary.
+ * current buffer -- the inner loop allocates more space as necessary.
* We really wouldn't have to do the maxlen calculations here, we
- * could do them in fts_read before returning the path, but it's a
+ * could do them in fts_read before returning the name, but it's a
* lot easier here since the length is part of the dirent structure.
*
* If not changing directories set a pointer so that can just append
- * each new name into the path.
+ * each new component into the file name.
*/
len = NAPPEND(cur);
if (ISSET(FTS_NOCHDIR)) {
oldaddr = sp->fts_path;
if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) {
/*
- * No more memory for path or structures. Save
+ * No more memory. Save
* errno, free up the current structure and the
* structures already allocated.
*/
if (new_len < len) {
/*
* In the unlikely even that we would end up
- * with a path longer than SIZE_MAX, free up
+ * with a file name longer than SIZE_MAX, free up
* the current structure and the structures already
* allocated, then error out with ENAMETOOLONG.
*/
closedir(dirp);
/*
- * If realloc() changed the address of the path, adjust the
+ * If realloc() changed the address of the file name, adjust the
* addresses for the rest of the tree and the dir list.
*/
if (doadjust)
fts_padjust(sp, head);
/*
- * If not changing directories, reset the path back to original
+ * If not changing directories, reset the file name back to original
* state.
*/
if (ISSET(FTS_NOCHDIR)) {
/*
* If descended after called from fts_children or after called from
* fts_read and nothing found, get back. At the root level we use
- * the saved fd; if one of fts_open()'s arguments is a relative path
+ * the saved fd; if one of fts_open()'s arguments is a relative name
* to an empty directory, we wind up here with no other way back. If
* can't get back, we're done.
*/
if (S_ISDIR(sbp->st_mode)) {
if (ISDOT(p->fts_name))
return (FTS_DOT);
+
+#if _LGPL_PACKAGE
+ {
+ /*
+ * Cycle detection is done by brute force when the directory
+ * is first encountered. If the tree gets deep enough or the
+ * number of symbolic links to directories is high enough,
+ * something faster might be worthwhile.
+ */
+ FTSENT *t;
+
+ for (t = p->fts_parent;
+ t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
+ if (sbp->st_ino == t->fts_statp->st_ino
+ && sbp->st_dev == t->fts_statp->st_dev)
+ {
+ p->fts_cycle = t;
+ return (FTS_DC);
+ }
+ }
+#endif
+
return (FTS_D);
}
if (S_ISLNK(sbp->st_mode))
}
/*
- * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
- * Most systems will allow creation of paths much longer than MAXPATHLEN, even
- * though the kernel won't resolve them. Add the size (not just what's needed)
- * plus 256 bytes so don't realloc the path 2 bytes at a time.
+ * Allow essentially unlimited file name lengths; find, rm, ls should
+ * all work on any tree. Most systems will allow creation of file
+ * names much longer than MAXPATHLEN, even though the kernel won't
+ * resolve them. Add the size (not just what's needed) plus 256 bytes
+ * so don't realloc the file name 2 bytes at a time.
*/
static bool
internal_function
}
/*
- * When the path is realloc'd, have to fix all of the pointers in structures
- * already returned.
+ * When the file name is realloc'd, have to fix all of the pointers in
+ * structures already returned.
*/
static void
internal_function
}
/*
- * Change to dir specified by fd or path without getting
+ * Change to dir specified by fd or file name without getting
* tricked by someone changing the world out from underneath us.
* Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
*/
static int
internal_function
-fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *path)
+fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
{
int ret, oerrno, newfd;
struct stat sb;
newfd = fd;
if (ISSET(FTS_NOCHDIR))
return (0);
- if (fd < 0 && (newfd = fd_safer (diropen (path))) < 0)
+ if (fd < 0 && (newfd = fd_safer (diropen (dir))) < 0)
return (-1);
if (fstat(newfd, &sb)) {
ret = -1;