Debian Codegraph @

lib/fts-cycle.c

raw
1 /* Detect cycles in file tree walks.
2
3 Copyright (C) 2003-2006, 2009-2026 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
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
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
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
74 enter_dir (FTS *fts, FTSENT *ent)
75 {
76 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
77 {
78 struct Active_dir *ad = malloc (sizeof *ad);
79 if (!ad)
80 return false;
81
82 struct stat const *st = ent->fts_statp;
83 ad->dev = st->st_dev;
84 ad->ino = st->st_ino;
85 ad->fts_ent = ent;
86
87 /* See if we've already encountered this directory.
88 This can happen when following symlinks as well as
89 with a corrupted directory hierarchy. */
90 struct Active_dir *ad_from_table = hash_insert (fts->fts_cycle.ht, ad);
91
92 if (ad_from_table != ad)
93 {
94 free (ad);
95 if (!ad_from_table)
96 return false;
97
98 /* There was an entry with matching dev/inode already in the table.
99 Record the fact that we've found a cycle. */
100 ent->fts_cycle = ad_from_table->fts_ent;
101 ent->fts_info = FTS_DC;
102 }
103 }
104 else
105 {
106 if (cycle_check (fts->fts_cycle.state, ent->fts_statp))
107 {
108 /* FIXME: setting fts_cycle like this isn't proper.
109 To do what the documentation requires, we'd have to
110 go around the cycle again and find the right entry.
111 But no callers in coreutils use the fts_cycle member. */
112 ent->fts_cycle = ent;
113 ent->fts_info = FTS_DC;
114 }
115 }
116
117 return true;
118 }
119
120 /* Leave a directory during a file tree walk. */
121
122 static void
123 leave_dir (FTS *fts, FTSENT *ent)
124 {
125 struct stat const *st = ent->fts_statp;
126 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
127 {
128 struct Active_dir obj;
129 obj.dev = st->st_dev;
130 obj.ino = st->st_ino;
131 void *found = hash_remove (fts->fts_cycle.ht, &obj);
132 if (!found)
133 abort ();
134 free (found);
135 }
136 else
137 {
138 FTSENT *parent = ent->fts_parent;
139 if (parent != NULL && 0 <= parent->fts_level)
140 CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state,
141 *(parent->fts_statp), *st);
142 }
143 }
144
145 /* Free any memory used for cycle detection. */
146
147 static void
148 free_dir (FTS *sp)
149 {
150 if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
151 {
152 if (sp->fts_cycle.ht)
153 hash_free (sp->fts_cycle.ht);
154 }
155 else
156 free (sp->fts_cycle.state);
157 }