io/ftw.c

   1 /* File tree walker functions.
   2    Copyright (C) 1996-2001, 2002, 2003 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #if __GNUC__
  26 # define alloca __builtin_alloca
  27 #else
  28 # if HAVE_ALLOCA_H
  29 #  include <alloca.h>
  30 # else
  31 #  ifdef _AIX
  32  #  pragma alloca
  33 #  else
  34 char *alloca ();
  35 #  endif
  36 # endif
  37 #endif
  38
  39 #if defined _LIBC
  40 # include <dirent.h>
  41 # define NAMLEN(dirent) _D_EXACT_NAMLEN (dirent)
  42 #else
  43 # if HAVE_DIRENT_H
  44 #  include <dirent.h>
  45 #  define NAMLEN(dirent) strlen ((dirent)->d_name)
  46 # else
  47 #  define dirent direct
  48 #  define NAMLEN(dirent) (dirent)->d_namlen
  49 #  if HAVE_SYS_NDIR_H
  50 #   include <sys/ndir.h>
  51 #  endif
  52 #  if HAVE_SYS_DIR_H
  53 #   include <sys/dir.h>
  54 #  endif
  55 #  if HAVE_NDIR_H
  56 #   include <ndir.h>
  57 #  endif
  58 # endif
  59 #endif
  60
  61 #include <errno.h>
  62 #include <ftw.h>
  63 #include <limits.h>
  64 #include <search.h>
  65 #include <stdlib.h>
  66 #include <string.h>
  67 #include <unistd.h>
  68 #if HAVE_SYS_PARAM_H || defined _LIBC
  69 # include <sys/param.h>
  70 #endif
  71 #ifdef _LIBC
  72 # include <include/sys/stat.h>
  73 #else
  74 # include <sys/stat.h>
  75 #endif
  76
  77 #if ! _LIBC && !HAVE_DECL_STPCPY && !defined stpcpy
  78 char *stpcpy ();
  79 #endif
  80
  81 #if ! _LIBC && ! defined HAVE_MEMPCPY && ! defined mempcpy
  82 /* Be CAREFUL that there are no side effects in N.  */
  83 # define mempcpy(D, S, N) ((void *) ((char *) memcpy (D, S, N) + (N)))
  84 #endif
  85
  86 /* #define NDEBUG 1 */
  87 #include <assert.h>
  88
  89 #ifndef _LIBC
  90 # undef __chdir
  91 # define __chdir chdir
  92 # undef __closedir
  93 # define __closedir closedir
  94 # undef __fchdir
  95 # define __fchdir fchdir
  96 # undef __getcwd
  97 # define __getcwd(P, N) xgetcwd ()
  98 extern char *xgetcwd (void);
  99 # undef __mempcpy
 100 # define __mempcpy mempcpy
 101 # undef __opendir
 102 # define __opendir opendir
 103 # undef __readdir64
 104 # define __readdir64 readdir
 105 # undef __stpcpy
 106 # define __stpcpy stpcpy
 107 # undef __tdestroy
 108 # define __tdestroy tdestroy
 109 # undef __tfind
 110 # define __tfind tfind
 111 # undef __tsearch
 112 # define __tsearch tsearch
 113 # undef internal_function
 114 # define internal_function /* empty */
 115 # undef dirent64
 116 # define dirent64 dirent
 117 # undef MAX
 118 # define MAX(a, b) ((a) > (b) ? (a) : (b))
 119 #endif
 120
 121 /* Arrange to make lstat calls go through the wrapper function
 122    on systems with an lstat function that does not dereference symlinks
 123    that are specified with a trailing slash.  */
 124 #if ! _LIBC && ! LSTAT_FOLLOWS_SLASHED_SYMLINK
 125 int rpl_lstat (const char *, struct stat *);
 126 # undef lstat
 127 # define lstat(Name, Stat_buf) rpl_lstat(Name, Stat_buf)
 128 #endif
 129
 130 #ifndef __set_errno
 131 # define __set_errno(Val) errno = (Val)
 132 #endif
 133
 134 /* Support for the LFS API version.  */
 135 #ifndef FTW_NAME
 136 # define FTW_NAME ftw
 137 # define NFTW_NAME nftw
 138 # define INO_T ino_t
 139 # define STAT stat
 140 # ifdef _LIBC
 141 #  define LXSTAT __lxstat
 142 #  define XSTAT __xstat
 143 # else
 144 #  define LXSTAT(V,f,sb) lstat (f,sb)
 145 #  define XSTAT(V,f,sb) stat (f,sb)
 146 # endif
 147 # define FTW_FUNC_T __ftw_func_t
 148 # define NFTW_FUNC_T __nftw_func_t
 149 #endif
 150
 151 /* We define PATH_MAX if the system does not provide a definition.
 152    This does not artificially limit any operation.  PATH_MAX is simply
 153    used as a guesstimate for the expected maximal path length.
 154    Buffers will be enlarged if necessary.  */
 155 #ifndef PATH_MAX
 156 # define PATH_MAX 1024
 157 #endif
 158
 159 struct dir_data
 160 {
 161   DIR *stream;
 162   char *content;
 163 };
 164
 165 struct known_object
 166 {
 167   dev_t dev;
 168   INO_T ino;
 169 };
 170
 171 struct ftw_data
 172 {
 173   /* Array with pointers to open directory streams.  */
 174   struct dir_data **dirstreams;
 175   size_t actdir;
 176   size_t maxdir;
 177
 178   /* Buffer containing name of currently processed object.  */
 179   char *dirbuf;
 180   size_t dirbufsize;
 181
 182   /* Passed as fourth argument to `nftw' callback.  The `base' member
 183      tracks the content of the `dirbuf'.  */
 184   struct FTW ftw;
 185
 186   /* Flags passed to `nftw' function.  0 for `ftw'.  */
 187   int flags;
 188
 189   /* Conversion array for flag values.  It is the identity mapping for
 190      `nftw' calls, otherwise it maps the values to those known by
 191      `ftw'.  */
 192   const int *cvt_arr;
 193
 194   /* Callback function.  We always use the `nftw' form.  */
 195   NFTW_FUNC_T func;
 196
 197   /* Device of starting point.  Needed for FTW_MOUNT.  */
 198   dev_t dev;
 199
 200   /* Data structure for keeping fingerprints of already processed
 201      object.  This is needed when not using FTW_PHYS.  */
 202   void *known_objects;
 203 };
 204
 205
 206 /* Internally we use the FTW_* constants used for `nftw'.  When invoked
 207    as `ftw', map each flag to the subset of values used by `ftw'.  */
 208 static const int nftw_arr[] =
 209 {
 210   FTW_F, FTW_D, FTW_DNR, FTW_NS, FTW_SL, FTW_DP, FTW_SLN
 211 };
 212
 213 static const int ftw_arr[] =
 214 {
 215   FTW_F, FTW_D, FTW_DNR, FTW_NS, FTW_F, FTW_D, FTW_NS
 216 };
 217
 218
 219 /* Forward declarations of local functions.  */
 220 static int ftw_dir (struct ftw_data *data, struct STAT *st) internal_function;
 221
 222
 223 static int
 224 object_compare (const void *p1, const void *p2)
 225 {
 226   /* We don't need a sophisticated and useful comparison.  We are only
 227      interested in equality.  However, we must be careful not to
 228      accidentally compare `holes' in the structure.  */
 229   const struct known_object *kp1 = p1, *kp2 = p2;
 230   int cmp1;
 231   cmp1 = (kp1->ino > kp2->ino) - (kp1->ino < kp2->ino);
 232   if (cmp1 != 0)
 233     return cmp1;
 234   return (kp1->dev > kp2->dev) - (kp1->dev < kp2->dev);
 235 }
 236
 237
 238 static inline int
 239 add_object (struct ftw_data *data, struct STAT *st)
 240 {
 241   struct known_object *newp = malloc (sizeof (struct known_object));
 242   if (newp == NULL)
 243     return -1;
 244   newp->dev = st->st_dev;
 245   newp->ino = st->st_ino;
 246   return __tsearch (newp, &data->known_objects, object_compare) ? 0 : -1;
 247 }
 248
 249
 250 static inline int
 251 find_object (struct ftw_data *data, struct STAT *st)
 252 {
 253   struct known_object obj;
 254   obj.dev = st->st_dev;
 255   obj.ino = st->st_ino;
 256   return __tfind (&obj, &data->known_objects, object_compare) != NULL;
 257 }
 258
 259
 260 static inline int
 261 open_dir_stream (struct ftw_data *data, struct dir_data *dirp)
 262 {
 263   int result = 0;
 264
 265   if (data->dirstreams[data->actdir] != NULL)
 266     {
 267       /* Oh, oh.  We must close this stream.  Get all remaining
 268          entries and store them as a list in the `content' member of
 269          the `struct dir_data' variable.  */
 270       size_t bufsize = 1024;
 271       char *buf = malloc (bufsize);
 272
 273       if (buf == NULL)
 274         result = -1;
 275       else
 276         {
 277           DIR *st = data->dirstreams[data->actdir]->stream;
 278           struct dirent64 *d;
 279           size_t actsize = 0;
 280
 281           while ((d = __readdir64 (st)) != NULL)
 282             {
 283               size_t this_len = NAMLEN (d);
 284               if (actsize + this_len + 2 >= bufsize)
 285                 {
 286                   char *newp;
 287                   bufsize += MAX (1024, 2 * this_len);
 288                   newp = (char *) realloc (buf, bufsize);
 289                   if (newp == NULL)
 290                     {
 291                       /* No more memory.  */
 292                       int save_err = errno;
 293                       free (buf);
 294                       __set_errno (save_err);
 295                       result = -1;
 296                       break;
 297                     }
 298                   buf = newp;
 299                 }
 300
 301               *((char *) __mempcpy (buf + actsize, d->d_name, this_len))
 302                 = '\0';
 303               actsize += this_len + 1;
 304             }
 305
 306           /* Terminate the list with an additional NUL byte.  */
 307           buf[actsize++] = '\0';
 308
 309           /* Shrink the buffer to what we actually need.  */
 310           data->dirstreams[data->actdir]->content = realloc (buf, actsize);
 311           if (data->dirstreams[data->actdir]->content == NULL)
 312             {
 313               int save_err = errno;
 314               free (buf);
 315               __set_errno (save_err);
 316               result = -1;
 317             }
 318           else
 319             {
 320               __closedir (st);
 321               data->dirstreams[data->actdir]->stream = NULL;
 322               data->dirstreams[data->actdir] = NULL;
 323             }
 324         }
 325     }
 326
 327   /* Open the new stream.  */
 328   if (result == 0)
 329     {
 330       const char *name = ((data->flags & FTW_CHDIR)
 331                           ? data->dirbuf + data->ftw.base: data->dirbuf);
 332       assert (data->dirstreams[data->actdir] == NULL);
 333
 334       dirp->stream = __opendir (name);
 335       if (dirp->stream == NULL)
 336         result = -1;
 337       else
 338         {
 339           dirp->content = NULL;
 340           data->dirstreams[data->actdir] = dirp;
 341
 342           if (++data->actdir == data->maxdir)
 343             data->actdir = 0;
 344         }
 345     }
 346
 347   return result;
 348 }
 349
 350
 351 static inline int
 352 process_entry (struct ftw_data *data, struct dir_data *dir, const char *name,
 353                size_t namlen)
 354 {
 355   struct STAT st;
 356   int result = 0;
 357   int flag = 0;
 358   size_t new_buflen;
 359
 360   if (name[0] == '.' && (name[1] == '\0'
 361                          || (name[1] == '.' && name[2] == '\0')))
 362     /* Don't process the "." and ".." entries.  */
 363     return 0;
 364
 365   new_buflen = data->ftw.base + namlen + 2;
 366   if (data->dirbufsize < new_buflen)
 367     {
 368       /* Enlarge the buffer.  */
 369       char *newp;
 370
 371       data->dirbufsize = 2 * new_buflen;
 372       newp = (char *) realloc (data->dirbuf, data->dirbufsize);
 373       if (newp == NULL)
 374         return -1;
 375       data->dirbuf = newp;
 376     }
 377
 378   *((char *) __mempcpy (data->dirbuf + data->ftw.base, name, namlen)) = '\0';
 379
 380   if ((data->flags & FTW_CHDIR) == 0)
 381     name = data->dirbuf;
 382
 383   if (((data->flags & FTW_PHYS)
 384        ? LXSTAT (_STAT_VER, name, &st)
 385        : XSTAT (_STAT_VER, name, &st)) < 0)
 386     {
 387       if (errno != EACCES && errno != ENOENT)
 388         result = -1;
 389       else if (!(data->flags & FTW_PHYS)
 390                && LXSTAT (_STAT_VER, name, &st) == 0
 391                && S_ISLNK (st.st_mode))
 392         flag = FTW_SLN;
 393       else
 394         flag = FTW_NS;
 395     }
 396   else
 397     {
 398       if (S_ISDIR (st.st_mode))
 399         flag = FTW_D;
 400       else if (S_ISLNK (st.st_mode))
 401         flag = FTW_SL;
 402       else
 403         flag = FTW_F;
 404     }
 405
 406   if (result == 0
 407       && (flag == FTW_NS
 408           || !(data->flags & FTW_MOUNT) || st.st_dev == data->dev))
 409     {
 410       if (flag == FTW_D)
 411         {
 412           if ((data->flags & FTW_PHYS)
 413               || (!find_object (data, &st)
 414                   /* Remember the object.  */
 415                   && (result = add_object (data, &st)) == 0))
 416             {
 417               result = ftw_dir (data, &st);
 418
 419               if (result == 0 && (data->flags & FTW_CHDIR))
 420                 {
 421                   /* Change back to the parent directory.  */
 422                   int done = 0;
 423                   if (dir->stream != NULL)
 424                     if (__fchdir (dirfd (dir->stream)) == 0)
 425                       done = 1;
 426
 427                   if (!done)
 428                     {
 429                       if (data->ftw.base == 1)
 430                         {
 431                           if (__chdir ("/") < 0)
 432                             result = -1;
 433                         }
 434                       else
 435                         if (__chdir ("..") < 0)
 436                           result = -1;
 437                     }
 438                 }
 439             }
 440         }
 441       else
 442         result = (*data->func) (data->dirbuf, &st, data->cvt_arr[flag],
 443                                 &data->ftw);
 444     }
 445
 446   return result;
 447 }
 448
 449
 450 static int
 451 internal_function
 452 ftw_dir (struct ftw_data *data, struct STAT *st)
 453 {
 454   struct dir_data dir;
 455   struct dirent64 *d;
 456   int previous_base = data->ftw.base;
 457   int result;
 458   char *startp;
 459
 460   /* Open the stream for this directory.  This might require that
 461      another stream has to be closed.  */
 462   result = open_dir_stream (data, &dir);
 463   if (result != 0)
 464     {
 465       if (errno == EACCES)
 466         /* We cannot read the directory.  Signal this with a special flag.  */
 467         result = (*data->func) (data->dirbuf, st, FTW_DNR, &data->ftw);
 468
 469       return result;
 470     }
 471
 472   /* First, report the directory (if not depth-first).  */
 473   if (!(data->flags & FTW_DEPTH))
 474     {
 475       result = (*data->func) (data->dirbuf, st, FTW_D, &data->ftw);
 476       if (result != 0)
 477         return result;
 478     }
 479
 480   /* If necessary, change to this directory.  */
 481   if (data->flags & FTW_CHDIR)
 482     {
 483       if (__fchdir (dirfd (dir.stream)) < 0)
 484         {
 485           if (errno == ENOSYS)
 486             {
 487               if (__chdir (data->dirbuf) < 0)
 488                 result = -1;
 489             }
 490           else
 491             result = -1;
 492         }
 493
 494       if (result != 0)
 495         {
 496           int save_err = errno;
 497           __closedir (dir.stream);
 498           __set_errno (save_err);
 499
 500           if (data->actdir-- == 0)
 501             data->actdir = data->maxdir - 1;
 502           data->dirstreams[data->actdir] = NULL;
 503
 504           return result;
 505         }
 506     }
 507
 508   /* Next, update the `struct FTW' information.  */
 509   ++data->ftw.level;
 510   startp = strchr (data->dirbuf, '\0');
 511   /* There always must be a directory name.  */
 512   assert (startp != data->dirbuf);
 513   if (startp[-1] != '/')
 514     *startp++ = '/';
 515   data->ftw.base = startp - data->dirbuf;
 516
 517   while (dir.stream != NULL && (d = __readdir64 (dir.stream)) != NULL)
 518     {
 519       result = process_entry (data, &dir, d->d_name, NAMLEN (d));
 520       if (result != 0)
 521         break;
 522     }
 523
 524   if (dir.stream != NULL)
 525     {
 526       /* The stream is still open.  I.e., we did not need more
 527          descriptors.  Simply close the stream now.  */
 528       int save_err = errno;
 529
 530       assert (dir.content == NULL);
 531
 532       __closedir (dir.stream);
 533       __set_errno (save_err);
 534
 535       if (data->actdir-- == 0)
 536         data->actdir = data->maxdir - 1;
 537       data->dirstreams[data->actdir] = NULL;
 538     }
 539   else
 540     {
 541       int save_err;
 542       char *runp = dir.content;
 543
 544       while (result == 0 && *runp != '\0')
 545         {
 546           char *endp = strchr (runp, '\0');
 547
 548           result = process_entry (data, &dir, runp, endp - runp);
 549
 550           runp = endp + 1;
 551         }
 552
 553       save_err = errno;
 554       free (dir.content);
 555       __set_errno (save_err);
 556     }
 557
 558   /* Prepare the return, revert the `struct FTW' information.  */
 559   data->dirbuf[data->ftw.base - 1] = '\0';
 560   --data->ftw.level;
 561   data->ftw.base = previous_base;
 562
 563   /* Finally, if we process depth-first report the directory.  */
 564   if (result == 0 && (data->flags & FTW_DEPTH))
 565     result = (*data->func) (data->dirbuf, st, FTW_DP, &data->ftw);
 566
 567   return result;
 568 }
 569
 570
 571 static int
 572 internal_function
 573 ftw_startup (const char *dir, int is_nftw, void *func, int descriptors,
 574              int flags)
 575 {
 576   struct ftw_data data;
 577   struct STAT st;
 578   int result = 0;
 579   int save_err;
 580   char *cwd = NULL;
 581   char *cp;
 582
 583   /* First make sure the parameters are reasonable.  */
 584   if (dir[0] == '\0')
 585     {
 586       __set_errno (ENOENT);
 587       return -1;
 588     }
 589
 590   data.maxdir = descriptors < 1 ? 1 : descriptors;
 591   data.actdir = 0;
 592   data.dirstreams = (struct dir_data **) alloca (data.maxdir
 593                                                  * sizeof (struct dir_data *));
 594   memset (data.dirstreams, '\0', data.maxdir * sizeof (struct dir_data *));
 595
 596   /* PATH_MAX is always defined when we get here.  */
 597   data.dirbufsize = MAX (2 * strlen (dir), PATH_MAX);
 598   data.dirbuf = (char *) malloc (data.dirbufsize);
 599   if (data.dirbuf == NULL)
 600     return -1;
 601   cp = __stpcpy (data.dirbuf, dir);
 602   /* Strip trailing slashes.  */
 603   while (cp > data.dirbuf + 1 && cp[-1] == '/')
 604     --cp;
 605   *cp = '\0';
 606
 607   data.ftw.level = 0;
 608
 609   /* Find basename.  */
 610   while (cp > data.dirbuf && cp[-1] != '/')
 611     --cp;
 612   data.ftw.base = cp - data.dirbuf;
 613
 614   data.flags = flags;
 615
 616   /* This assignment might seem to be strange but it is what we want.
 617      The trick is that the first three arguments to the `ftw' and
 618      `nftw' callback functions are equal.  Therefore we can call in
 619      every case the callback using the format of the `nftw' version
 620      and get the correct result since the stack layout for a function
 621      call in C allows this.  */
 622   data.func = (NFTW_FUNC_T) func;
 623
 624   /* Since we internally use the complete set of FTW_* values we need
 625      to reduce the value range before calling a `ftw' callback.  */
 626   data.cvt_arr = is_nftw ? nftw_arr : ftw_arr;
 627
 628   /* No object known so far.  */
 629   data.known_objects = NULL;
 630
 631   /* Now go to the directory containing the initial file/directory.  */
 632   if (flags & FTW_CHDIR)
 633     {
 634       /* GNU extension ahead.  */
 635       cwd =  __getcwd (NULL, 0);
 636       if (cwd == NULL)
 637         result = -1;
 638       else if (data.ftw.base > 0)
 639         {
 640           /* Change to the directory the file is in.  In data.dirbuf
 641              we have a writable copy of the file name.  Just NUL
 642              terminate it for now and change the directory.  */
 643           if (data.ftw.base == 1)
 644             /* I.e., the file is in the root directory.  */
 645             result = __chdir ("/");
 646           else
 647             {
 648               char ch = data.dirbuf[data.ftw.base - 1];
 649               data.dirbuf[data.ftw.base - 1] = '\0';
 650               result = __chdir (data.dirbuf);
 651               data.dirbuf[data.ftw.base - 1] = ch;
 652             }
 653         }
 654     }
 655
 656   /* Get stat info for start directory.  */
 657   if (result == 0)
 658     {
 659       const char *name = ((data.flags & FTW_CHDIR)
 660                           ? data.dirbuf + data.ftw.base
 661                           : data.dirbuf);
 662
 663       if (((flags & FTW_PHYS)
 664            ? LXSTAT (_STAT_VER, name, &st)
 665            : XSTAT (_STAT_VER, name, &st)) < 0)
 666         {
 667           if (!(flags & FTW_PHYS)
 668               && errno == ENOENT
 669               && LXSTAT (_STAT_VER, name, &st) == 0
 670               && S_ISLNK (st.st_mode))
 671             result = (*data.func) (data.dirbuf, &st, data.cvt_arr[FTW_SLN],
 672                                    &data.ftw);
 673           else
 674             /* No need to call the callback since we cannot say anything
 675                about the object.  */
 676             result = -1;
 677         }
 678       else
 679         {
 680           if (S_ISDIR (st.st_mode))
 681             {
 682               /* Remember the device of the initial directory in case
 683                  FTW_MOUNT is given.  */
 684               data.dev = st.st_dev;
 685
 686               /* We know this directory now.  */
 687               if (!(flags & FTW_PHYS))
 688                 result = add_object (&data, &st);
 689
 690               if (result == 0)
 691                 result = ftw_dir (&data, &st);
 692             }
 693           else
 694             {
 695               int flag = S_ISLNK (st.st_mode) ? FTW_SL : FTW_F;
 696
 697               result = (*data.func) (data.dirbuf, &st, data.cvt_arr[flag],
 698                                      &data.ftw);
 699             }
 700         }
 701     }
 702
 703   /* Return to the start directory (if necessary).  */
 704   if (cwd != NULL)
 705     {
 706       int save_err = errno;
 707       __chdir (cwd);
 708       free (cwd);
 709       __set_errno (save_err);
 710     }
 711
 712   /* Free all memory.  */
 713   save_err = errno;
 714   __tdestroy (data.known_objects, free);
 715   free (data.dirbuf);
 716   __set_errno (save_err);
 717
 718   return result;
 719 }
 720
 721
 722
 723 /* Entry points.  */
 724
 725 int
 726 FTW_NAME (path, func, descriptors)
 727      const char *path;
 728      FTW_FUNC_T func;
 729      int descriptors;
 730 {
 731   return ftw_startup (path, 0, func, descriptors, 0);
 732 }
 733
 734 int
 735 NFTW_NAME (path, func, descriptors, flags)
 736      const char *path;
 737      NFTW_FUNC_T func;
 738      int descriptors;
 739      int flags;
 740 {
 741   return ftw_startup (path, 1, func, descriptors, flags);
 742 }