libmisc/walk_tree.c

   1 /*
   2   File: walk_tree.c
   3
   4   Copyright (C) 2007 Andreas Gruenbacher <a.gruenbacher@computer.org>
   5
   6   This program is free software; you can redistribute it and/or modify it under
   7   the terms of the GNU Lesser General Public License as published by the
   8   Free Software Foundation; either version 2.1 of the License, or (at
   9   your option) any later version.
  10
  11   This program is distributed in the hope that it will be useful, but WITHOUT
  12   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14   License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public
  17   License along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include <sys/types.h>
  21 #include <sys/stat.h>
  22 #include <unistd.h>
  23 #include <sys/time.h>
  24 #include <sys/resource.h>
  25 #include <dirent.h>
  26 #include <stdio.h>
  27 #include <string.h>
  28 #include <errno.h>
  29
  30 #include "walk_tree.h"
  31
  32 struct entry_handle {
  33         struct entry_handle *prev, *next;
  34         dev_t dev;
  35         ino_t ino;
  36         DIR *stream;
  37         off_t pos;
  38 };
  39
  40 struct entry_handle head = {
  41         .next = &head,
  42         .prev = &head,
  43         /* The other fields are unused. */
  44 };
  45 struct entry_handle *closed = &head;
  46 unsigned int num_dir_handles;
  47
  48 static int walk_tree_visited(dev_t dev, ino_t ino)
  49 {
  50         struct entry_handle *i;
  51
  52         for (i = head.next; i != &head; i = i->next)
  53                 if (i->dev == dev && i->ino == ino)
  54                         return 1;
  55         return 0;
  56 }
  57
  58 static int walk_tree_rec(const char *path, int walk_flags,
  59                          int (*func)(const char *, const struct stat *, int,
  60                                      void *), void *arg, int depth)
  61 {
  62         int follow_symlinks = (walk_flags & WALK_TREE_LOGICAL) ||
  63                               (!(walk_flags & WALK_TREE_PHYSICAL) &&
  64                                depth == 0);
  65         int have_dir_stat = 0, flags = walk_flags, err;
  66         struct entry_handle dir;
  67         struct stat st;
  68
  69         /*
  70          * If (walk_flags & WALK_TREE_PHYSICAL), do not traverse symlinks.
  71          * If (walk_flags & WALK_TREE_LOGICAL), traverse all symlinks.
  72          * Otherwise, traverse only top-level symlinks.
  73          */
  74         if (depth == 0)
  75                 flags |= WALK_TREE_TOPLEVEL;
  76
  77         if (lstat(path, &st) != 0)
  78                 return func(path, NULL, flags | WALK_TREE_FAILED, arg);
  79         if (S_ISLNK(st.st_mode)) {
  80                 flags |= WALK_TREE_SYMLINK;
  81                 if ((flags & WALK_TREE_DEREFERENCE) ||
  82                     ((flags & WALK_TREE_TOPLEVEL) &&
  83                      (flags & WALK_TREE_DEREFERENCE_TOPLEVEL))) {
  84                         if (stat(path, &st) != 0)
  85                                 return func(path, NULL,
  86                                             flags | WALK_TREE_FAILED, arg);
  87                         dir.dev = st.st_dev;
  88                         dir.ino = st.st_ino;
  89                         have_dir_stat = 1;
  90                 }
  91         } else if (S_ISDIR(st.st_mode)) {
  92                 dir.dev = st.st_dev;
  93                 dir.ino = st.st_ino;
  94                 have_dir_stat = 1;
  95         }
  96         err = func(path, &st, flags, arg);
  97
  98         /*
  99          * Recurse if WALK_TREE_RECURSIVE and the path is:
 100          *      a dir not from a symlink
 101          *      a link and follow_symlinks
 102          */
 103         if ((flags & WALK_TREE_RECURSIVE) &&
 104            (!(flags & WALK_TREE_SYMLINK) && S_ISDIR(st.st_mode)) ||
 105            ((flags & WALK_TREE_SYMLINK) && follow_symlinks)) {
 106                 struct dirent *entry;
 107
 108                 /*
 109                  * Check if we have already visited this directory to break
 110                  * endless loops.
 111                  *
 112                  * If we haven't stat()ed the file yet, do an opendir() for
 113                  * figuring out whether we have a directory, and check whether
 114                  * the directory has been visited afterwards. This saves a
 115                  * system call for each non-directory found.
 116                  */
 117                 if (have_dir_stat && walk_tree_visited(dir.dev, dir.ino))
 118                         return err;
 119
 120                 if (num_dir_handles == 0 && closed->prev != &head) {
 121 close_another_dir:
 122                         /* Close the topmost directory handle still open. */
 123                         closed = closed->prev;
 124                         closed->pos = telldir(closed->stream);
 125                         closedir(closed->stream);
 126                         closed->stream = NULL;
 127                         num_dir_handles++;
 128                 }
 129
 130                 dir.stream = opendir(path);
 131                 if (!dir.stream) {
 132                         if (errno == ENFILE && closed->prev != &head) {
 133                                 /* Ran out of file descriptors. */
 134                                 num_dir_handles = 0;
 135                                 goto close_another_dir;
 136                         }
 137
 138                         /*
 139                          * PATH may be a symlink to a regular file, or a dead
 140                          * symlink which we didn't follow above.
 141                          */
 142                         if (errno != ENOTDIR && errno != ENOENT)
 143                                 err += func(path, NULL, flags |
 144                                                         WALK_TREE_FAILED, arg);
 145                         return err;
 146                 }
 147
 148                 /* See walk_tree_visited() comment above... */
 149                 if (!have_dir_stat) {
 150                         if (stat(path, &st) != 0)
 151                                 goto skip_dir;
 152                         dir.dev = st.st_dev;
 153                         dir.ino = st.st_ino;
 154                         if (walk_tree_visited(dir.dev, dir.ino))
 155                                 goto skip_dir;
 156                 }
 157
 158                 /* Insert into the list of handles. */
 159                 dir.next = head.next;
 160                 dir.prev = &head;
 161                 dir.prev->next = &dir;
 162                 dir.next->prev = &dir;
 163                 num_dir_handles--;
 164
 165                 while ((entry = readdir(dir.stream)) != NULL) {
 166                         char *path_end;
 167
 168                         if (!strcmp(entry->d_name, ".") ||
 169                             !strcmp(entry->d_name, ".."))
 170                                 continue;
 171                         path_end = strchr(path, 0);
 172                         if ((path_end - path) + strlen(entry->d_name) + 1 >=
 173                             FILENAME_MAX) {
 174                                 errno = ENAMETOOLONG;
 175                                 err += func(path, NULL,
 176                                             flags | WALK_TREE_FAILED, arg);
 177                                 continue;
 178                         }
 179                         *path_end++ = '/';
 180                         strcpy(path_end, entry->d_name);
 181                         err += walk_tree_rec(path, walk_flags, func, arg,
 182                                              depth + 1);
 183                         *--path_end = 0;
 184                         if (!dir.stream) {
 185                                 /* Reopen the directory handle. */
 186                                 dir.stream = opendir(path);
 187                                 if (!dir.stream)
 188                                         return err + func(path, NULL, flags |
 189                                                     WALK_TREE_FAILED, arg);
 190                                 seekdir(dir.stream, dir.pos);
 191
 192                                 closed = closed->next;
 193                                 num_dir_handles--;
 194                         }
 195                 }
 196
 197                 /* Remove from the list of handles. */
 198                 dir.prev->next = dir.next;
 199                 dir.next->prev = dir.prev;
 200                 num_dir_handles++;
 201
 202         skip_dir:
 203                 if (closedir(dir.stream) != 0)
 204                         err += func(path, NULL, flags | WALK_TREE_FAILED, arg);
 205         }
 206         return err;
 207 }
 208
 209 int walk_tree(const char *path, int walk_flags, unsigned int num,
 210               int (*func)(const char *, const struct stat *, int, void *),
 211               void *arg)
 212 {
 213         char path_copy[FILENAME_MAX];
 214
 215         num_dir_handles = num;
 216         if (num_dir_handles < 1) {
 217                 struct rlimit rlimit;
 218
 219                 num_dir_handles = 1;
 220                 if (getrlimit(RLIMIT_NOFILE, &rlimit) == 0 &&
 221                     rlimit.rlim_cur >= 2)
 222                         num_dir_handles = rlimit.rlim_cur / 2;
 223         }
 224         if (strlen(path) >= FILENAME_MAX) {
 225                 errno = ENAMETOOLONG;
 226                 return func(path, NULL, WALK_TREE_FAILED, arg);
 227         }
 228         strcpy(path_copy, path);
 229         return walk_tree_rec(path_copy, walk_flags, func, arg, 0);
 230 }