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