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