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 /* 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               memcpy (buf + actsize, d->d_name, this_len);
 190               actsize += this_len;
 191               buf[actsize++] = '\0';
 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   memcpy (data->dirbuf + data->ftw.base, name, namlen);
 263   data->dirbuf[data->ftw.base + namlen] = '\0';
 264
 265   if (((data->flags & FTW_PHYS)
 266        ? LXSTAT (_STAT_VER, data->dirbuf, &st)
 267        : XSTAT (_STAT_VER, data->dirbuf, &st)) < 0)
 268     {
 269       if (errno != EACCES && errno != ENOENT)
 270         result = -1;
 271       else if (!(data->flags & FTW_PHYS)
 272                && LXSTAT (_STAT_VER, data->dirbuf, &st) == 0
 273                && S_ISLNK (st.st_mode))
 274         flag = FTW_SLN;
 275       else
 276         flag = FTW_NS;
 277     }
 278   else
 279     {
 280       if (S_ISDIR (st.st_mode))
 281         flag = FTW_D;
 282       else if (S_ISLNK (st.st_mode))
 283         flag = FTW_SL;
 284       else
 285         flag = FTW_F;
 286     }
 287
 288   if (result == 0
 289       && (flag == FTW_NS
 290           || !(data->flags & FTW_MOUNT) || st.st_dev == data->dev))
 291     {
 292       if ((data->flags & FTW_PHYS) || flag == FTW_NS
 293           || (!find_object (data, &st)
 294               /* Remember the object.  */
 295               && (result = add_object (data, &st)) == 0))
 296         {
 297           if (flag == FTW_D)
 298             {
 299               result = ftw_dir (data, &st);
 300
 301               if (result == 0 && (data->flags & FTW_CHDIR))
 302                 {
 303                   /* Change back to current directory.  */
 304                   int done = 0;
 305                   if (dir->stream != NULL)
 306                     if (__fchdir (dirfd (dir->stream)) == 0)
 307                       done = 1;
 308
 309                   if (!done)
 310                     {
 311                       if (data->ftw.base == 1)
 312                         {
 313                           if (chdir ("/") < 0)
 314                             result = -1;
 315                         }
 316                       else
 317                         {
 318                           /* Please note that we overwrite a slash.  */
 319                           data->dirbuf[data->ftw.base - 1] = '\0';
 320
 321                           if (chdir (data->dirbuf) < 0)
 322                             result = -1;
 323
 324                           data->dirbuf[data->ftw.base - 1] = '/';
 325                         }
 326                     }
 327                 }
 328             }
 329           else
 330             result = (*data->func) (data->dirbuf, &st, data->cvt_arr[flag],
 331                                     &data->ftw);
 332         }
 333     }
 334
 335   return result;
 336 }
 337
 338
 339 static int
 340 internal_function
 341 ftw_dir (struct ftw_data *data, struct STAT *st)
 342 {
 343   struct dir_data dir;
 344   struct DIRENT *d;
 345   int previous_base = data->ftw.base;
 346   int result;
 347   char *startp;
 348
 349   /* Open the stream for this directory.  This might require that
 350      another stream has to be closed.  */
 351   result = open_dir_stream (data, &dir);
 352   if (result != 0)
 353     {
 354       if (errno == EACCES)
 355         /* We cannot read the directory.  Signal this with a special flag.  */
 356         result = (*data->func) (data->dirbuf, st, FTW_DNR, &data->ftw);
 357
 358       return result;
 359     }
 360
 361   /* First, report the directory (if not depth-first).  */
 362   if (!(data->flags & FTW_DEPTH))
 363     {
 364       result = (*data->func) (data->dirbuf, st, FTW_D, &data->ftw);
 365       if (result != 0)
 366         return result;
 367     }
 368
 369   /* If necessary, change to this directory.  */
 370   if (data->flags & FTW_CHDIR)
 371     {
 372       if (__fchdir (dirfd (dir.stream)) < 0)
 373         {
 374           if (errno == ENOSYS)
 375             {
 376               if (chdir (data->dirbuf) < 0)
 377                 result = -1;
 378             }
 379           else
 380             result = -1;
 381         }
 382
 383       if (result != 0)
 384         {
 385           int save_err = errno;
 386           closedir (dir.stream);
 387           __set_errno (save_err);
 388
 389           if (data->actdir-- == 0)
 390             data->actdir = data->maxdir - 1;
 391           data->dirstreams[data->actdir] = NULL;
 392
 393           return result;
 394         }
 395     }
 396
 397   /* Next, update the `struct FTW' information.  */
 398   ++data->ftw.level;
 399   startp = strchr (data->dirbuf, '\0');
 400   *startp++ = '/';
 401   data->ftw.base = startp - data->dirbuf;
 402
 403   while (dir.stream != NULL && (d = READDIR (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       assert (result == 0);
 431
 432       while (*runp != '\0')
 433         {
 434           char *endp = strchr (runp, '\0');
 435
 436           result = process_entry (data, &dir, runp, endp - runp);
 437           if (result != 0)
 438             break;
 439
 440           runp = endp + 1;
 441         }
 442
 443       save_err = errno;
 444       free (dir.content);
 445       __set_errno (save_err);
 446     }
 447
 448   /* Prepare the return, revert the `struct FTW' information.  */
 449   data->dirbuf[data->ftw.base - 1] = '\0';
 450   --data->ftw.level;
 451   data->ftw.base = previous_base;
 452
 453   /* Finally, if we process depth-first report the directory.  */
 454   if (result == 0 && (data->flags & FTW_DEPTH))
 455     result = (*data->func) (data->dirbuf, st, FTW_DP, &data->ftw);
 456
 457   return result;
 458 }
 459
 460
 461 static int
 462 internal_function
 463 ftw_startup (const char *dir, int is_nftw, void *func, int descriptors,
 464              int flags)
 465 {
 466   struct ftw_data data;
 467   struct STAT st;
 468   int result = 0;
 469   int save_err;
 470   char *cwd = NULL;
 471   char *cp;
 472
 473   /* First make sure the parameters are reasonable.  */
 474   if (dir[0] == '\0')
 475     {
 476       __set_errno (ENOTDIR);
 477       return -1;
 478     }
 479
 480   data.maxdir = descriptors < 1 ? 1 : descriptors;
 481   data.actdir = 0;
 482   data.dirstreams = (struct dir_data **) alloca (data.maxdir
 483                                                  * sizeof (struct dir_data *));
 484   memset (data.dirstreams, '\0', data.maxdir * sizeof (struct dir_data *));
 485
 486 #ifdef PATH_MAX
 487   data.dirbufsize = MAX (2 * strlen (dir), PATH_MAX);
 488 #else
 489   data.dirbufsize = 2 * strlen (dir);
 490 #endif
 491   data.dirbuf = (char *) malloc (data.dirbufsize);
 492   if (data.dirbuf == NULL)
 493     return -1;
 494   cp = __stpcpy (data.dirbuf, dir);
 495   /* Strip trailing slashes.  */
 496   while (cp > data.dirbuf + 1 && cp[-1] == '/')
 497     --cp;
 498   *cp = '\0';
 499
 500   data.ftw.level = 0;
 501
 502   /* Find basename.  */
 503   while (cp > data.dirbuf && cp[-1] != '/')
 504     --cp;
 505   data.ftw.base = cp - data.dirbuf;
 506
 507   data.flags = flags;
 508
 509   /* This assignment might seem to be strange but it is what we want.
 510      The trick is that the first three arguments to the `ftw' and
 511      `nftw' callback functions are equal.  Therefore we can call in
 512      every case the callback using the format of the `nftw' version
 513      and get the correct result since the stack layout for a function
 514      call in C allows this.  */
 515   data.func = (NFTW_FUNC_T) func;
 516
 517   /* Since we internally use the complete set of FTW_* values we need
 518      to reduce the value range before calling a `ftw' callback.  */
 519   data.cvt_arr = is_nftw ? nftw_arr : ftw_arr;
 520
 521   /* No object known so far.  */
 522   data.known_objects = NULL;
 523
 524   /* Now go to the directory containing the initial file/directory.  */
 525   if ((flags & FTW_CHDIR) && data.ftw.base > 0)
 526     {
 527       /* GNU extension ahead.  */
 528       cwd =  getcwd (NULL, 0);
 529       if (cwd == NULL)
 530         result = -1;
 531       else
 532         {
 533           /* Change to the directory the file is in.  In data.dirbuf
 534              we have a writable copy of the file name.  Just NUL
 535              terminate it for now and change the directory.  */
 536           if (data.ftw.base == 1)
 537             /* I.e., the file is in the root directory.  */
 538             result = chdir ("/");
 539           else
 540             {
 541               char ch = data.dirbuf[data.ftw.base - 1];
 542               data.dirbuf[data.ftw.base - 1] = '\0';
 543               result = chdir (data.dirbuf);
 544               data.dirbuf[data.ftw.base - 1] = ch;
 545             }
 546         }
 547     }
 548
 549   /* Get stat info for start directory.  */
 550   if (result == 0)
 551     if (((flags & FTW_PHYS)
 552          ? LXSTAT (_STAT_VER, data.dirbuf, &st)
 553          : XSTAT (_STAT_VER, data.dirbuf, &st)) < 0)
 554       {
 555         if (errno == EACCES)
 556           result = (*data.func) (data.dirbuf, &st, FTW_NS, &data.ftw);
 557         else if (!(flags & FTW_PHYS)
 558                  && errno == ENOENT
 559                  && LXSTAT (_STAT_VER, dir, &st) == 0
 560                  && S_ISLNK (st.st_mode))
 561           result = (*data.func) (data.dirbuf, &st, data.cvt_arr[FTW_SLN],
 562                                  &data.ftw);
 563         else
 564           /* No need to call the callback since we cannot say anything
 565              about the object.  */
 566           result = -1;
 567       }
 568     else
 569       {
 570         if (S_ISDIR (st.st_mode))
 571           {
 572             /* Remember the device of the initial directory in case
 573                FTW_MOUNT is given.  */
 574             data.dev = st.st_dev;
 575
 576             /* We know this directory now.  */
 577             if (!(flags & FTW_PHYS))
 578               result = add_object (&data, &st);
 579
 580             if (result == 0)
 581               result = ftw_dir (&data, &st);
 582           }
 583         else
 584           {
 585             int flag = S_ISLNK (st.st_mode) ? FTW_SL : FTW_F;
 586
 587             result = (*data.func) (data.dirbuf, &st, data.cvt_arr[flag],
 588                                    &data.ftw);
 589           }
 590       }
 591
 592   /* Return to the start directory (if necessary).  */
 593   if (cwd != NULL)
 594     {
 595       int save_err = errno;
 596       chdir (cwd);
 597       free (cwd);
 598       __set_errno (save_err);
 599     }
 600
 601   /* Free all memory.  */
 602   save_err = errno;
 603   __tdestroy (data.known_objects, free);
 604   free (data.dirbuf);
 605   __set_errno (save_err);
 606
 607   return result;
 608 }
 609
 610
 611
 612 /* Entry points.  */
 613
 614 int
 615 FTW_NAME (path, func, descriptors)
 616      const char *path;
 617      FTW_FUNC_T func;
 618      int descriptors;
 619 {
 620   return ftw_startup (path, 0, func, descriptors, 0);
 621 }
 622
 623 int
 624 NFTW_NAME (path, func, descriptors, flags)
 625      const char *path;
 626      NFTW_FUNC_T func;
 627      int descriptors;
 628      int flags;
 629 {
 630   return ftw_startup (path, 1, func, descriptors, flags);
 631 }