io/ftw.c

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