Line data    Source code

       1             : /* help detect directory cycles efficiently
       2             : 
       3             :    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
       4             : 
       5             :    This program is free software: you can redistribute it and/or modify
       6             :    it under the terms of the GNU General Public License as published by
       7             :    the Free Software Foundation; either version 3 of the License, or
       8             :    (at your option) any later version.
       9             : 
      10             :    This program is distributed in the hope that it will be useful,
      11             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      12             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13             :    GNU General Public License for more details.
      14             : 
      15             :    You should have received a copy of the GNU General Public License
      16             :    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
      17             : 
      18             : /* Written by Jim Meyering */
      19             : 
      20             : #include <config.h>
      21             : 
      22             : #include <sys/types.h>
      23             : #include <sys/stat.h>
      24             : #include <stdio.h>
      25             : #include <assert.h>
      26             : #include <stdlib.h>
      27             : 
      28             : #include <stdbool.h>
      29             : 
      30             : #include "cycle-check.h"
      31             : 
      32             : #define CC_MAGIC 9827862
      33             : 
      34             : /* Return true if I is a power of 2, or is zero.  */
      35             : 
      36             : static inline bool
      37       66331 : is_zero_or_power_of_two (uintmax_t i)
      38             : {
      39       66331 :   return (i & (i - 1)) == 0;
      40             : }
      41             : 
      42             : void
      43         186 : cycle_check_init (struct cycle_check_state *state)
      44             : {
      45         186 :   state->chdir_counter = 0;
      46         186 :   state->magic = CC_MAGIC;
      47         186 : }
      48             : 
      49             : /* In traversing a directory hierarchy, call this function once for each
      50             :    descending chdir call, with SB corresponding to the chdir operand.
      51             :    If SB corresponds to a directory that has already been seen,
      52             :    return true to indicate that there is a directory cycle.
      53             :    Note that this is done `lazily', which means that some of
      54             :    the directories in the cycle may be processed twice before
      55             :    the cycle is detected.  */
      56             : 
      57             : bool
      58       66334 : cycle_check (struct cycle_check_state *state, struct stat const *sb)
      59             : {
      60       66334 :   assert (state->magic == CC_MAGIC);
      61             : 
      62             :   /* If the current directory ever happens to be the same
      63             :      as the one we last recorded for the cycle detection,
      64             :      then it's obviously part of a cycle.  */
      65       66334 :   if (state->chdir_counter && SAME_INODE (*sb, state->dev_ino))
      66           3 :     return true;
      67             : 
      68             :   /* If the number of `descending' chdir calls is a power of two,
      69             :      record the dev/ino of the current directory.  */
      70       66331 :   if (is_zero_or_power_of_two (++(state->chdir_counter)))
      71             :     {
      72             :       /* On all architectures that we know about, if the counter
      73             :          overflows then there is a directory cycle here somewhere,
      74             :          even if we haven't detected it yet.  Typically this happens
      75             :          only after the counter is incremented 2**64 times, so it's a
      76             :          fairly theoretical point.  */
      77         126 :       if (state->chdir_counter == 0)
      78           0 :         return true;
      79             : 
      80         126 :       state->dev_ino.st_dev = sb->st_dev;
      81         126 :       state->dev_ino.st_ino = sb->st_ino;
      82             :     }
      83             : 
      84       66331 :   return false;
      85             : }