cycle-check integer overflow fix for coreutils

[Paul Eggert]

I installed this fix to handle counter overflow better in cycle-check.
(At least, I hope it's better: perhaps someone who understands the
algorithm deeply can suggest a better fix.  :-)

2004-07-27  Paul Eggert  <address@hidden>

        cycle-check integer overflow fixup.

        * cycle-check.c (is_zero_or_power_of_two): Renamed from
        is_power_of_two, to reflect better what it really does.
        All uses changed.  Arg is now uintmax_t, not unsigned int
        (it should have been unsigned long int -- that was a bug).
        (cycle_check): Check for integer overflow in cycle count,
        and report a cycle if that happens, as it must be a cycle
        by this point.
        * cycle-check.h: Remove now-inaccurate comment about the files
        you need to include first.  You don't need to include any files
        other than the usual config.h.
        Include <inttypes.h> and <stdint.h> if available, for uintmax_t.
        Remove 'struct stat;' not needed since we know sys/stat.h has
        been included by dev-ino.h.
        (struct cycle_check_state): Change chdir_counter to uintmax_t,
        not size_t, since it isn't limited by object sizes.
        Change magic from long unsigned int to int; that's good enough
        for our use.

Index: lib/cycle-check.c
===================================================================
RCS file: /home/eggert/coreutils/cu/lib/cycle-check.c,v
retrieving revision 1.3
diff -p -u -r1.3 cycle-check.c
--- lib/cycle-check.c   6 Jun 2003 19:16:31 -0000       1.3
+++ lib/cycle-check.c   28 Jul 2004 00:21:23 -0000
@@ -1,5 +1,6 @@
 /* help detect directory cycles efficiently
-   Copyright 2003 Free Software Foundation, Inc.
+
+   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -39,8 +40,10 @@
 
 #define CC_MAGIC 9827862
 
+/* Return true if I is a power of 2, or is zero.  */
+
 static inline bool
-is_power_of_two (unsigned int i)
+is_zero_or_power_of_two (uintmax_t i)
 {
   return (i & (i - 1)) == 0;
 }
@@ -73,8 +76,16 @@ cycle_check (struct cycle_check_state *s
 
   /* If the number of `descending' chdir calls is a power of two,
      record the dev/ino of the current directory.  */
-  if (is_power_of_two (++(state->chdir_counter)))
+  if (is_zero_or_power_of_two (++(state->chdir_counter)))
     {
+      /* On all architectures that we know about, if the counter
+        overflows then there is a directory cycle here somewhere,
+        even if we haven't detected it yet.  Typically this happens
+        only after the counter is incremented 2**64 times, so it's a
+        fairly theoretical point.  */
+      if (state->chdir_counter == 0)
+       return true;
+
       state->dev_ino.st_dev = sb->st_dev;
       state->dev_ino.st_ino = sb->st_ino;
     }
Index: lib/cycle-check.h
===================================================================
RCS file: /home/eggert/coreutils/cu/lib/cycle-check.h,v
retrieving revision 1.3
diff -p -u -r1.3 cycle-check.h
--- lib/cycle-check.h   7 Jul 2004 15:07:08 -0000       1.3
+++ lib/cycle-check.h   28 Jul 2004 00:21:51 -0000
@@ -1,29 +1,20 @@
 #ifndef CYCLE_CHECK_H
 # define CYCLE_CHECK_H 1
 
-/* Before including this file, you need something like the following:
-
-       #if HAVE_CONFIG_H
-       # include <config.h>
-       #endif
-
-       #include <sys/types.h>
-       #include <sys/stat.h>
-
-       #include <stdbool.h>
-
-   so that the proper identifiers are all declared.  */
-
+# if HAVE_INTTYPES_H
+#  include <inttypes.h>
+# endif
+# if HAVE_STDINT_H
+#  include <stdint.h>
+# endif
 # include <stdbool.h>
 # include "dev-ino.h"
 
-struct stat;
-
 struct cycle_check_state
 {
   struct dev_ino dev_ino;
-  size_t chdir_counter;
-  long unsigned int magic;
+  uintmax_t chdir_counter;
+  int magic;
 };
 
 void cycle_check_init (struct cycle_check_state *state);