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