lib/fts-cycle.c

   1 /* Detect cycles in file tree walks.
   2
   3    Copyright (C) 2003-2006, 2009-2020 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 <https://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 }