io/ftw.c

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