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