Update to LGPL v2.1.
[kopensolaris-gnu/glibc.git] / 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 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 #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 }