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 2, or (at your option)
    8:    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; see the file COPYING.
   17:    If not, write to the Free Software Foundation,
   18:    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
   19: 
   20: /* Written by Jim Meyering */
   21: 
   22: #include <config.h>
   23: 
   24: #include <sys/types.h>
   25: #include <sys/stat.h>
   26: #include <stdio.h>
   27: #include <assert.h>
   28: #include <stdlib.h>
   29: 
   30: #include <stdbool.h>
   31: 
   32: #include "cycle-check.h"
   33: 
   34: #define CC_MAGIC 9827862
   35: 
   36: /* Return true if I is a power of 2, or is zero.  */
   37: 
   38: static inline bool
   39: is_zero_or_power_of_two (uintmax_t i)
   40: {
   41:   return (i & (i - 1)) == 0;
   42: }
   43: 
   44: void
   45: cycle_check_init (struct cycle_check_state *state)
   46: {
   47:   state->chdir_counter = 0;
   48:   state->magic = CC_MAGIC;
   49: }
   50: 
   51: /* In traversing a directory hierarchy, call this function once for each
   52:    descending chdir call, with SB corresponding to the chdir operand.
   53:    If SB corresponds to a directory that has already been seen,
   54:    return true to indicate that there is a directory cycle.
   55:    Note that this is done `lazily', which means that some of
   56:    the directories in the cycle may be processed twice before
   57:    the cycle is detected.  */
   58: 
   59: bool
   60: cycle_check (struct cycle_check_state *state, struct stat const *sb)
   61: {
   62:   assert (state->magic == CC_MAGIC);
   63: 
   64:   /* If the current directory ever happens to be the same
   65:      as the one we last recorded for the cycle detection,
   66:      then it's obviously part of a cycle.  */
   67:   if (state->chdir_counter && SAME_INODE (*sb, state->dev_ino))
   68:     return true;
   69: 
   70:   /* If the number of `descending' chdir calls is a power of two,
   71:      record the dev/ino of the current directory.  */
   72:   if (is_zero_or_power_of_two (++(state->chdir_counter)))
   73:     {
   74:       /* On all architectures that we know about, if the counter
   75:          overflows then there is a directory cycle here somewhere,
   76:          even if we haven't detected it yet.  Typically this happens
   77:          only after the counter is incremented 2**64 times, so it's a
   78:          fairly theoretical point.  */
   79:       if (state->chdir_counter == 0)
   80:         return true;
   81: 
   82:       state->dev_ino.st_dev = sb->st_dev;
   83:       state->dev_ino.st_ino = sb->st_ino;
   84:     }
   85: 
   86:   return false;
   87: }