lib/fts-cycle.c

   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 2, or (at your option)
  10    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, write to the Free Software Foundation,
  19    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #include "cycle-check.h"
  26 #include "hash.h"
  27
  28 /* Use each of these to map a device/inode pair to an FTSENT.  */
  29 struct Active_dir
  30 {
  31   dev_t dev;
  32   ino_t ino;
  33   FTSENT *fts_ent;
  34 };
  35
  36 static bool
  37 AD_compare (void const *x, void const *y)
  38 {
  39   struct Active_dir const *ax = x;
  40   struct Active_dir const *ay = y;
  41   return ax->ino == ay->ino
  42       && ax->dev == ay->dev;
  43 }
  44
  45 static size_t
  46 AD_hash (void const *x, size_t table_size)
  47 {
  48   struct Active_dir const *ax = x;
  49   return (uintmax_t) ax->ino % table_size;
  50 }
  51
  52 /* Set up the cycle-detection machinery.  */
  53
  54 static bool
  55 setup_dir (FTS *fts)
  56 {
  57   if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
  58     {
  59       enum { HT_INITIAL_SIZE = 31 };
  60       fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash,
  61                                            AD_compare, free);
  62       if (! fts->fts_cycle.ht)
  63         return false;
  64     }
  65   else
  66     {
  67       fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state);
  68       if (! fts->fts_cycle.state)
  69         return false;
  70       cycle_check_init (fts->fts_cycle.state);
  71     }
  72
  73   return true;
  74 }
  75
  76 /* Enter a directory during a file tree walk.  */
  77
  78 static bool
  79 enter_dir (FTS *fts, FTSENT *ent)
  80 {
  81   if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
  82     {
  83       struct stat const *st = ent->fts_statp;
  84       struct Active_dir *ad = malloc (sizeof *ad);
  85       struct Active_dir *ad_from_table;
  86
  87       if (!ad)
  88         return false;
  89
  90       ad->dev = st->st_dev;
  91       ad->ino = st->st_ino;
  92       ad->fts_ent = ent;
  93
  94       /* See if we've already encountered this directory.
  95          This can happen when following symlinks as well as
  96          with a corrupted directory hierarchy. */
  97       ad_from_table = hash_insert (fts->fts_cycle.ht, ad);
  98
  99       if (ad_from_table != ad)
 100         {
 101           free (ad);
 102           if (!ad_from_table)
 103             return false;
 104
 105           /* There was an entry with matching dev/inode already in the table.
 106              Record the fact that we've found a cycle.  */
 107           ent->fts_cycle = ad_from_table->fts_ent;
 108           ent->fts_info = FTS_DC;
 109         }
 110     }
 111   else
 112     {
 113       if (cycle_check (fts->fts_cycle.state, ent->fts_statp))
 114         {
 115           /* FIXME: setting fts_cycle like this isn't proper.
 116              To do what the documentation requires, we'd have to
 117              go around the cycle again and find the right entry.
 118              But no callers in coreutils use the fts_cycle member. */
 119           ent->fts_cycle = ent;
 120           ent->fts_info = FTS_DC;
 121         }
 122     }
 123
 124   return true;
 125 }
 126
 127 /* Leave a directory during a file tree walk.  */
 128
 129 static void
 130 leave_dir (FTS *fts, FTSENT *ent)
 131 {
 132   struct stat const *st = ent->fts_statp;
 133   if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
 134     {
 135       struct Active_dir obj;
 136       void *found;
 137       obj.dev = st->st_dev;
 138       obj.ino = st->st_ino;
 139       found = hash_delete (fts->fts_cycle.ht, &obj);
 140       if (!found)
 141         abort ();
 142       free (found);
 143     }
 144   else
 145     {
 146       FTSENT *parent = ent->fts_parent;
 147       if (parent != NULL)
 148         CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state,
 149                                       *(parent->fts_statp), *st);
 150     }
 151 }
 152
 153 /* Free any memory used for cycle detection.  */
 154
 155 static void
 156 free_dir (FTS *sp)
 157 {
 158   if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
 159     {
 160       if (sp->fts_cycle.ht)
 161         hash_free (sp->fts_cycle.ht);
 162     }
 163   else
 164     free (sp->fts_cycle.state);
 165 }