Line data Source code
1 : /* Detect cycles in file tree walks.
2 :
3 : Copyright (C) 2003, 2004, 2005, 2006 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 <http://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 42327 : AD_compare (void const *x, void const *y)
33 : {
34 42327 : struct Active_dir const *ax = x;
35 42327 : struct Active_dir const *ay = y;
36 42327 : return ax->ino == ay->ino
37 42327 : && ax->dev == ay->dev;
38 : }
39 :
40 : static size_t
41 87933 : AD_hash (void const *x, size_t table_size)
42 : {
43 87933 : struct Active_dir const *ax = x;
44 87933 : return (uintmax_t) ax->ino % table_size;
45 : }
46 :
47 : /* Set up the cycle-detection machinery. */
48 :
49 : static bool
50 176 : setup_dir (FTS *fts)
51 : {
52 176 : if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
53 : {
54 : enum { HT_INITIAL_SIZE = 31 };
55 54 : fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash,
56 : AD_compare, free);
57 54 : if (! fts->fts_cycle.ht)
58 0 : return false;
59 : }
60 : else
61 : {
62 122 : fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state);
63 122 : if (! fts->fts_cycle.state)
64 0 : return false;
65 122 : cycle_check_init (fts->fts_cycle.state);
66 : }
67 :
68 176 : return true;
69 : }
70 :
71 : /* Enter a directory during a file tree walk. */
72 :
73 : static bool
74 106142 : enter_dir (FTS *fts, FTSENT *ent)
75 : {
76 106142 : if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
77 : {
78 39810 : struct stat const *st = ent->fts_statp;
79 39810 : struct Active_dir *ad = malloc (sizeof *ad);
80 : struct Active_dir *ad_from_table;
81 :
82 39810 : if (!ad)
83 0 : return false;
84 :
85 39810 : ad->dev = st->st_dev;
86 39810 : ad->ino = st->st_ino;
87 39810 : 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 39810 : ad_from_table = hash_insert (fts->fts_cycle.ht, ad);
93 :
94 39810 : if (ad_from_table != ad)
95 : {
96 0 : free (ad);
97 0 : if (!ad_from_table)
98 0 : 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 0 : ent->fts_cycle = ad_from_table->fts_ent;
103 0 : ent->fts_info = FTS_DC;
104 : }
105 : }
106 : else
107 : {
108 66332 : 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 3 : ent->fts_cycle = ent;
115 3 : ent->fts_info = FTS_DC;
116 : }
117 : }
118 :
119 106142 : return true;
120 : }
121 :
122 : /* Leave a directory during a file tree walk. */
123 :
124 : static void
125 106139 : leave_dir (FTS *fts, FTSENT *ent)
126 : {
127 106139 : struct stat const *st = ent->fts_statp;
128 106139 : if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
129 : {
130 : struct Active_dir obj;
131 : void *found;
132 39810 : obj.dev = st->st_dev;
133 39810 : obj.ino = st->st_ino;
134 39810 : found = hash_delete (fts->fts_cycle.ht, &obj);
135 39810 : if (!found)
136 0 : abort ();
137 39810 : free (found);
138 : }
139 : else
140 : {
141 66329 : FTSENT *parent = ent->fts_parent;
142 66329 : if (parent != NULL && 0 <= parent->fts_level)
143 66270 : CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state,
144 : *(parent->fts_statp), *st);
145 : }
146 106139 : }
147 :
148 : /* Free any memory used for cycle detection. */
149 :
150 : static void
151 176 : free_dir (FTS *sp)
152 : {
153 176 : if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
154 : {
155 54 : if (sp->fts_cycle.ht)
156 54 : hash_free (sp->fts_cycle.ht);
157 : }
158 : else
159 122 : free (sp->fts_cycle.state);
160 176 : }
|
