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_DEREFERENCE) &&
  64                                !(walk_flags & WALK_TREE_PHYSICAL) &&
  65                                depth == 0);
  66         int have_dir_stat = 0, flags = walk_flags, err;
  67         struct entry_handle dir;
  68         struct stat st;
  69
  70         /*
  71          * If (walk_flags & WALK_TREE_PHYSICAL), do not traverse symlinks.
  72          * If (walk_flags & WALK_TREE_LOGICAL), traverse all symlinks.
  73          * Otherwise, traverse only top-level symlinks.
  74          */
  75         if (depth == 0)
  76                 flags |= WALK_TREE_TOPLEVEL;
  77
  78         if (lstat(path, &st) != 0)
  79                 return func(path, NULL, flags | WALK_TREE_FAILED, arg);
  80         if (S_ISLNK(st.st_mode)) {
  81                 flags |= WALK_TREE_SYMLINK;
  82                 if ((flags & WALK_TREE_DEREFERENCE) ||
  83                     ((flags & WALK_TREE_TOPLEVEL) &&
  84                      (flags & WALK_TREE_DEREFERENCE_TOPLEVEL))) {
  85                         if (stat(path, &st) != 0)
  86                                 return func(path, NULL,
  87                                             flags | WALK_TREE_FAILED, arg);
  88                         dir.dev = st.st_dev;
  89                         dir.ino = st.st_ino;
  90                         have_dir_stat = 1;
  91                 }
  92         } else if (S_ISDIR(st.st_mode)) {
  93                 dir.dev = st.st_dev;
  94                 dir.ino = st.st_ino;
  95                 have_dir_stat = 1;
  96         }
  97         err = func(path, &st, flags, arg);
  98
  99         /*
 100          * Recurse if WALK_TREE_RECURSIVE and the path is:
 101          *      a dir not from a symlink
 102          *      a link and follow_symlinks
 103          */
 104         if ((flags & WALK_TREE_RECURSIVE) &&
 105            (!(flags & WALK_TREE_SYMLINK) && S_ISDIR(st.st_mode)) ||
 106            ((flags & WALK_TREE_SYMLINK) && follow_symlinks)) {
 107                 struct dirent *entry;
 108
 109                 /*
 110                  * Check if we have already visited this directory to break
 111                  * endless loops.
 112                  *
 113                  * If we haven't stat()ed the file yet, do an opendir() for
 114                  * figuring out whether we have a directory, and check whether
 115                  * the directory has been visited afterwards. This saves a
 116                  * system call for each non-directory found.
 117                  */
 118                 if (have_dir_stat && walk_tree_visited(dir.dev, dir.ino))
 119                         return err;
 120
 121                 if (num_dir_handles == 0 && closed->prev != &head) {
 122 close_another_dir:
 123                         /* Close the topmost directory handle still open. */
 124                         closed = closed->prev;
 125                         closed->pos = telldir(closed->stream);
 126                         closedir(closed->stream);
 127                         closed->stream = NULL;
 128                         num_dir_handles++;
 129                 }
 130
 131                 dir.stream = opendir(path);
 132                 if (!dir.stream) {
 133                         if (errno == ENFILE && closed->prev != &head) {
 134                                 /* Ran out of file descriptors. */
 135                                 num_dir_handles = 0;
 136                                 goto close_another_dir;
 137                         }
 138
 139                         /*
 140                          * PATH may be a symlink to a regular file, or a dead
 141                          * symlink which we didn't follow above.
 142                          */
 143                         if (errno != ENOTDIR && errno != ENOENT)
 144                                 err += func(path, NULL, flags |
 145                                                         WALK_TREE_FAILED, arg);
 146                         return err;
 147                 }
 148
 149                 /* See walk_tree_visited() comment above... */
 150                 if (!have_dir_stat) {
 151                         if (stat(path, &st) != 0)
 152                                 goto skip_dir;
 153                         dir.dev = st.st_dev;
 154                         dir.ino = st.st_ino;
 155                         if (walk_tree_visited(dir.dev, dir.ino))
 156                                 goto skip_dir;
 157                 }
 158
 159                 /* Insert into the list of handles. */
 160                 dir.next = head.next;
 161                 dir.prev = &head;
 162                 dir.prev->next = &dir;
 163                 dir.next->prev = &dir;
 164                 num_dir_handles--;
 165
 166                 while ((entry = readdir(dir.stream)) != NULL) {
 167                         char *path_end;
 168
 169                         if (!strcmp(entry->d_name, ".") ||
 170                             !strcmp(entry->d_name, ".."))
 171                                 continue;
 172                         path_end = strchr(path, 0);
 173                         if ((path_end - path) + strlen(entry->d_name) + 1 >=
 174                             FILENAME_MAX) {
 175                                 errno = ENAMETOOLONG;
 176                                 err += func(path, NULL,
 177                                             flags | WALK_TREE_FAILED, arg);
 178                                 continue;
 179                         }
 180                         *path_end++ = '/';
 181                         strcpy(path_end, entry->d_name);
 182                         err += walk_tree_rec(path, walk_flags, func, arg,
 183                                              depth + 1);
 184                         *--path_end = 0;
 185                         if (!dir.stream) {
 186                                 /* Reopen the directory handle. */
 187                                 dir.stream = opendir(path);
 188                                 if (!dir.stream)
 189                                         return err + func(path, NULL, flags |
 190                                                     WALK_TREE_FAILED, arg);
 191                                 seekdir(dir.stream, dir.pos);
 192
 193                                 closed = closed->next;
 194                                 num_dir_handles--;
 195                         }
 196                 }
 197
 198                 /* Remove from the list of handles. */
 199                 dir.prev->next = dir.next;
 200                 dir.next->prev = dir.prev;
 201                 num_dir_handles++;
 202
 203         skip_dir:
 204                 if (closedir(dir.stream) != 0)
 205                         err += func(path, NULL, flags | WALK_TREE_FAILED, arg);
 206         }
 207         return err;
 208 }
 209
 210 int walk_tree(const char *path, int walk_flags, unsigned int num,
 211               int (*func)(const char *, const struct stat *, int, void *),
 212               void *arg)
 213 {
 214         char path_copy[FILENAME_MAX];
 215
 216         num_dir_handles = num;
 217         if (num_dir_handles < 1) {
 218                 struct rlimit rlimit;
 219
 220                 num_dir_handles = 1;
 221                 if (getrlimit(RLIMIT_NOFILE, &rlimit) == 0 &&
 222                     rlimit.rlim_cur >= 2)
 223                         num_dir_handles = rlimit.rlim_cur / 2;
 224         }
 225         if (strlen(path) >= FILENAME_MAX) {
 226                 errno = ENAMETOOLONG;
 227                 return func(path, NULL, WALK_TREE_FAILED, arg);
 228         }
 229         strcpy(path_copy, path);
 230         return walk_tree_rec(path_copy, walk_flags, func, arg, 0);
 231 }