lib/fts-cycle.c

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