1/* Detect cycles in file tree walks.
2
3   Copyright (C) 2003-2006, 2009-2010 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.  */
24struct Active_dir
25{
26  dev_t dev;
27  ino_t ino;
28  FTSENT *fts_ent;
29};
30
31static bool
32AD_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
40static size_t
41AD_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
49static bool
50setup_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
73static bool
74enter_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
124static void
125leave_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_delete (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
150static void
151free_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