1 /* Detect cycles in file tree walks. 2 3 Copyright (C) 2003-2006, 2009-2014 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 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 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 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_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 150 static void 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