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