[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
cycle-check integer overflow fix for coreutils
From: |
Paul Eggert |
Subject: |
cycle-check integer overflow fix for coreutils |
Date: |
Tue, 27 Jul 2004 17:35:09 -0700 |
User-agent: |
Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3 (gnu/linux) |
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);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- cycle-check integer overflow fix for coreutils,
Paul Eggert <=