1 /* Detect cycles in file tree walks.
2 
3    Copyright (C) 2003-2006, 2009-2021 Free Software Foundation, Inc.
4 
5    Written by Jim Meyering.
6 
7    This program is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3 of the License, or
10    (at your option) any later version.
11 
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16 
17    You should have received a copy of the GNU General Public License
18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
19 
20 #include "cycle-check.h"
21 #include "hash.h"
22 
23 /* Use each of these to map a device/inode pair to an FTSENT.  */
24 struct Active_dir
25 {
26   dev_t dev;
27   ino_t ino;
28   FTSENT *fts_ent;
29 };
30 
31 static bool
AD_compare(void const * x,void const * y)32 AD_compare (void const *x, void const *y)
33 {
34   struct Active_dir const *ax = x;
35   struct Active_dir const *ay = y;
36   return ax->ino == ay->ino
37       && ax->dev == ay->dev;
38 }
39 
40 static size_t
AD_hash(void const * x,size_t table_size)41 AD_hash (void const *x, size_t table_size)
42 {
43   struct Active_dir const *ax = x;
44   return (uintmax_t) ax->ino % table_size;
45 }
46 
47 /* Set up the cycle-detection machinery.  */
48 
49 static bool
setup_dir(FTS * fts)50 setup_dir (FTS *fts)
51 {
52   if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
53     {
54       enum { HT_INITIAL_SIZE = 31 };
55       fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash,
56                                            AD_compare, free);
57       if (! fts->fts_cycle.ht)
58         return false;
59     }
60   else
61     {
62       fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state);
63       if (! fts->fts_cycle.state)
64         return false;
65       cycle_check_init (fts->fts_cycle.state);
66     }
67 
68   return true;
69 }
70 
71 /* Enter a directory during a file tree walk.  */
72 
73 static bool
enter_dir(FTS * fts,FTSENT * ent)74 enter_dir (FTS *fts, FTSENT *ent)
75 {
76   if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
77     {
78       struct stat const *st = ent->fts_statp;
79       struct Active_dir *ad = malloc (sizeof *ad);
80       struct Active_dir *ad_from_table;
81 
82       if (!ad)
83         return false;
84 
85       ad->dev = st->st_dev;
86       ad->ino = st->st_ino;
87       ad->fts_ent = ent;
88 
89       /* See if we've already encountered this directory.
90          This can happen when following symlinks as well as
91          with a corrupted directory hierarchy. */
92       ad_from_table = hash_insert (fts->fts_cycle.ht, ad);
93 
94       if (ad_from_table != ad)
95         {
96           free (ad);
97           if (!ad_from_table)
98             return false;
99 
100           /* There was an entry with matching dev/inode already in the table.
101              Record the fact that we've found a cycle.  */
102           ent->fts_cycle = ad_from_table->fts_ent;
103           ent->fts_info = FTS_DC;
104         }
105     }
106   else
107     {
108       if (cycle_check (fts->fts_cycle.state, ent->fts_statp))
109         {
110           /* FIXME: setting fts_cycle like this isn't proper.
111              To do what the documentation requires, we'd have to
112              go around the cycle again and find the right entry.
113              But no callers in coreutils use the fts_cycle member. */
114           ent->fts_cycle = ent;
115           ent->fts_info = FTS_DC;
116         }
117     }
118 
119   return true;
120 }
121 
122 /* Leave a directory during a file tree walk.  */
123 
124 static void
leave_dir(FTS * fts,FTSENT * ent)125 leave_dir (FTS *fts, FTSENT *ent)
126 {
127   struct stat const *st = ent->fts_statp;
128   if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
129     {
130       struct Active_dir obj;
131       void *found;
132       obj.dev = st->st_dev;
133       obj.ino = st->st_ino;
134       found = hash_remove (fts->fts_cycle.ht, &obj);
135       if (!found)
136         abort ();
137       free (found);
138     }
139   else
140     {
141       FTSENT *parent = ent->fts_parent;
142       if (parent != NULL && 0 <= parent->fts_level)
143         CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state,
144                                       *(parent->fts_statp), *st);
145     }
146 }
147 
148 /* Free any memory used for cycle detection.  */
149 
150 static void
free_dir(FTS * sp)151 free_dir (FTS *sp)
152 {
153   if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
154     {
155       if (sp->fts_cycle.ht)
156         hash_free (sp->fts_cycle.ht);
157     }
158   else
159     free (sp->fts_cycle.state);
160 }
161