io/ftw.c

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