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