{"thread":{"id":"25352","subject":"[PATCH v4] do not depend on signed integer overflow","startedAt":"2010-10-05T07:24:10Z","lastAt":"2011-02-10T13:23:25Z","messageCount":5,"participants":["Erik Faye-Lund","Nicolas Pitre","Jonathan Nieder","Sverre Rabbelier","Joshua Juran"],"isPatch":true,"patchVersion":4,"patchTotal":null},"messages":[{"id":"152647","messageId":"1286263450-5372-1-git-send-email-kusmabite@gmail.com","threadId":"25352","inReplyTo":null,"subject":"[PATCH v4] do not depend on signed integer overflow","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2010-10-05T07:24:10Z","receivedAt":"2010-10-05T07:24:10Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"Signed integer overflow is not defined in C, so do not depend on it.\n\nThis fixes a problem with GCC 4.4.0 and -O3 where the optimizer would\nconsider \"consumed_bytes > consumed_bytes + bytes\" as a constant\nexpression, and never execute the die()-call.\n\nSigned-off-by: Erik Faye-Lund <kusmabite@gmail.com>\n---\n builtin/index-pack.c     |    2 +-\n builtin/pack-objects.c   |    2 +-\n builtin/unpack-objects.c |    2 +-\n git-compat-util.h        |   12 ++++++++++++\n 4 files changed, 15 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 2e680d7..e243d9d 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -161,7 +161,7 @@ static void use(int bytes)\n \tinput_offset += bytes;\n \n \t/* make sure off_t is sufficiently large not to wrap */\n-\tif (consumed_bytes > consumed_bytes + bytes)\n+\tif (signed_add_overflows(consumed_bytes, bytes))\n \t\tdie(\"pack too large for current definition of off_t\");\n \tconsumed_bytes += bytes;\n }\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 3756cf3..d5a8db1 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -431,7 +431,7 @@ static int write_one(struct sha1file *f,\n \twritten_list[nr_written++] = &e->idx;\n \n \t/* make sure off_t is sufficiently large not to wrap */\n-\tif (*offset > *offset + size)\n+\tif (signed_add_overflows(*offset, size))\n \t\tdie(\"pack too large for current definition of off_t\");\n \t*offset += size;\n \treturn 1;\ndiff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\nindex 685566e..f63973c 100644\n--- a/builtin/unpack-objects.c\n+++ b/builtin/unpack-objects.c\n@@ -83,7 +83,7 @@ static void use(int bytes)\n \toffset += bytes;\n \n \t/* make sure off_t is sufficiently large not to wrap */\n-\tif (consumed_bytes > consumed_bytes + bytes)\n+\tif (signed_add_overflows(consumed_bytes, bytes))\n \t\tdie(\"pack too large for current definition of off_t\");\n \tconsumed_bytes += bytes;\n }\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 81883e7..2af8d3e 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -28,6 +28,18 @@\n #define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))\n #define bitsizeof(x)  (CHAR_BIT * sizeof(x))\n \n+#define maximum_signed_value_of_type(a) \\\n+    (INTMAX_MAX >> (bitsizeof(intmax_t) - bitsizeof(a)))\n+\n+/*\n+ * Signed integer overflow is undefined in C, so here's a helper macro\n+ * to detect if the sum of two integers will overflow.\n+ *\n+ * Requires: a >= 0, typeof(a) equals typeof(b)\n+ */\n+#define signed_add_overflows(a, b) \\\n+    ((b) > maximum_signed_value_of_type(a) - (a))\n+\n #ifdef __GNUC__\n #define TYPEOF(x) (__typeof__(x))\n #else\n-- \n1.7.3.1.51.ge462f.dirty\n"},{"id":"152674","messageId":"alpine.LFD.2.00.1010050928200.3107@xanadu.home","threadId":"25352","inReplyTo":"1286263450-5372-1-git-send-email-kusmabite@gmail.com","subject":"Re: [PATCH v4] do not depend on signed integer overflow","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-10-05T13:28:55Z","receivedAt":"2010-10-05T13:28:55Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 5 Oct 2010, Erik Faye-Lund wrote:\n\n> Signed integer overflow is not defined in C, so do not depend on it.\n> \n> This fixes a problem with GCC 4.4.0 and -O3 where the optimizer would\n> consider \"consumed_bytes > consumed_bytes + bytes\" as a constant\n> expression, and never execute the die()-call.\n> \n> Signed-off-by: Erik Faye-Lund <kusmabite@gmail.com>\n\nAcked-by: Nicolas Pitre <nico@fluxnic.net>\n\n> ---\n>  builtin/index-pack.c     |    2 +-\n>  builtin/pack-objects.c   |    2 +-\n>  builtin/unpack-objects.c |    2 +-\n>  git-compat-util.h        |   12 ++++++++++++\n>  4 files changed, 15 insertions(+), 3 deletions(-)\n> \n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index 2e680d7..e243d9d 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -161,7 +161,7 @@ static void use(int bytes)\n>  \tinput_offset += bytes;\n>  \n>  \t/* make sure off_t is sufficiently large not to wrap */\n> -\tif (consumed_bytes > consumed_bytes + bytes)\n> +\tif (signed_add_overflows(consumed_bytes, bytes))\n>  \t\tdie(\"pack too large for current definition of off_t\");\n>  \tconsumed_bytes += bytes;\n>  }\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 3756cf3..d5a8db1 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -431,7 +431,7 @@ static int write_one(struct sha1file *f,\n>  \twritten_list[nr_written++] = &e->idx;\n>  \n>  \t/* make sure off_t is sufficiently large not to wrap */\n> -\tif (*offset > *offset + size)\n> +\tif (signed_add_overflows(*offset, size))\n>  \t\tdie(\"pack too large for current definition of off_t\");\n>  \t*offset += size;\n>  \treturn 1;\n> diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\n> index 685566e..f63973c 100644\n> --- a/builtin/unpack-objects.c\n> +++ b/builtin/unpack-objects.c\n> @@ -83,7 +83,7 @@ static void use(int bytes)\n>  \toffset += bytes;\n>  \n>  \t/* make sure off_t is sufficiently large not to wrap */\n> -\tif (consumed_bytes > consumed_bytes + bytes)\n> +\tif (signed_add_overflows(consumed_bytes, bytes))\n>  \t\tdie(\"pack too large for current definition of off_t\");\n>  \tconsumed_bytes += bytes;\n>  }\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 81883e7..2af8d3e 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -28,6 +28,18 @@\n>  #define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))\n>  #define bitsizeof(x)  (CHAR_BIT * sizeof(x))\n>  \n> +#define maximum_signed_value_of_type(a) \\\n> +    (INTMAX_MAX >> (bitsizeof(intmax_t) - bitsizeof(a)))\n> +\n> +/*\n> + * Signed integer overflow is undefined in C, so here's a helper macro\n> + * to detect if the sum of two integers will overflow.\n> + *\n> + * Requires: a >= 0, typeof(a) equals typeof(b)\n> + */\n> +#define signed_add_overflows(a, b) \\\n> +    ((b) > maximum_signed_value_of_type(a) - (a))\n> +\n>  #ifdef __GNUC__\n>  #define TYPEOF(x) (__typeof__(x))\n>  #else\n> -- \n> 1.7.3.1.51.ge462f.dirty\n> \n"},{"id":"160819","messageId":"20110210093536.GB365@elie","threadId":"25352","inReplyTo":"1286263450-5372-1-git-send-email-kusmabite@gmail.com","subject":"[PATCH] compat: helper for detecting unsigned overflow","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-02-10T09:35:51Z","receivedAt":"2011-02-10T09:35:51Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Date: Sun, 10 Oct 2010 21:59:26 -0500\n\nThe idiom (a + b < a) works fine for detecting that an unsigned\ninteger has overflowed, but a more explicit\n\n\tunsigned_add_overflows(a, b)\n\nmight be easier to read.\n\nDefine such a macro, expanding roughly to ((a) < UINT_MAX - (b)).\nBecause the expansion uses each argument only once outside of sizeof()\nexpressions, it is safe to use with arguments that have side effects.\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\nFrom the svn remote helper project.  Sane?\n\n git-compat-util.h |    6 ++++++\n patch-delta.c     |    2 +-\n strbuf.c          |    5 +++--\n wrapper.c         |    2 +-\n 4 files changed, 11 insertions(+), 4 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex d6d269f..9c23622 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -31,6 +31,9 @@\n #define maximum_signed_value_of_type(a) \\\n     (INTMAX_MAX >> (bitsizeof(intmax_t) - bitsizeof(a)))\n \n+#define maximum_unsigned_value_of_type(a) \\\n+    (UINTMAX_MAX >> (bitsizeof(uintmax_t) - bitsizeof(a)))\n+\n /*\n  * Signed integer overflow is undefined in C, so here's a helper macro\n  * to detect if the sum of two integers will overflow.\n@@ -40,6 +43,9 @@\n #define signed_add_overflows(a, b) \\\n     ((b) > maximum_signed_value_of_type(a) - (a))\n \n+#define unsigned_add_overflows(a, b) \\\n+    ((b) > maximum_unsigned_value_of_type(a) - (a))\n+\n #ifdef __GNUC__\n #define TYPEOF(x) (__typeof__(x))\n #else\ndiff --git a/patch-delta.c b/patch-delta.c\nindex d218faa..56e0a5e 100644\n--- a/patch-delta.c\n+++ b/patch-delta.c\n@@ -48,7 +48,7 @@ void *patch_delta(const void *src_buf, unsigned long src_size,\n \t\t\tif (cmd & 0x20) cp_size |= (*data++ << 8);\n \t\t\tif (cmd & 0x40) cp_size |= (*data++ << 16);\n \t\t\tif (cp_size == 0) cp_size = 0x10000;\n-\t\t\tif (cp_off + cp_size < cp_size ||\n+\t\t\tif (unsigned_add_overflows(cp_off, cp_size) ||\n \t\t\t    cp_off + cp_size > src_size ||\n \t\t\t    cp_size > size)\n \t\t\t\tbreak;\ndiff --git a/strbuf.c b/strbuf.c\nindex 9b3c445..07e8883 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -63,7 +63,8 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n \n void strbuf_grow(struct strbuf *sb, size_t extra)\n {\n-\tif (sb->len + extra + 1 <= sb->len)\n+\tif (unsigned_add_overflows(extra, 1) ||\n+\t    unsigned_add_overflows(sb->len, extra + 1))\n \t\tdie(\"you want to use way too much memory\");\n \tif (!sb->alloc)\n \t\tsb->buf = NULL;\n@@ -152,7 +153,7 @@ int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n void strbuf_splice(struct strbuf *sb, size_t pos, size_t len,\n \t\t\t\t   const void *data, size_t dlen)\n {\n-\tif (pos + len < pos)\n+\tif (unsigned_add_overflows(pos, len))\n \t\tdie(\"you want to use way too much memory\");\n \tif (pos > sb->len)\n \t\tdie(\"`pos' is too far after the end of the buffer\");\ndiff --git a/wrapper.c b/wrapper.c\nindex 55b074e..4c147d6 100644\n--- a/wrapper.c\n+++ b/wrapper.c\n@@ -53,7 +53,7 @@ void *xmalloc(size_t size)\n void *xmallocz(size_t size)\n {\n \tvoid *ret;\n-\tif (size + 1 < size)\n+\tif (unsigned_add_overflows(size, 1))\n \t\tdie(\"Data too large to fit into virtual memory space.\");\n \tret = xmalloc(size + 1);\n \t((char*)ret)[size] = 0;\n-- \n1.7.4\n"},{"id":"160820","messageId":"AANLkTinqkSxj0C+GyMVR4a7d=yy_mh+oDuar0moZjZ8_@mail.gmail.com","threadId":"25352","inReplyTo":"20110210093536.GB365@elie","subject":"Re: [PATCH] compat: helper for detecting unsigned overflow","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2011-02-10T12:11:17Z","receivedAt":"2011-02-10T12:11:17Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Thu, Feb 10, 2011 at 10:35, Jonathan Nieder <jrnieder@gmail.com> wrote:\n>        unsigned_add_overflows(a, b)\n\n> Define such a macro, expanding roughly to ((a) < UINT_MAX - (b)).\n> Because the expansion uses each argument only once outside of sizeof()\n> expressions, it is safe to use with arguments that have side effects.\n\n> +#define unsigned_add_overflows(a, b) \\\n> +    ((b) > maximum_unsigned_value_of_type(a) - (a))\n\nI'm confused, you say you won't use it twice, and then you do use it twice?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"160821","messageId":"E84FF9D8-92D7-4CA0-9CF4-77FF33893977@gmail.com","threadId":"25352","inReplyTo":"AANLkTinqkSxj0C+GyMVR4a7d=yy_mh+oDuar0moZjZ8_@mail.gmail.com","subject":"Re: [PATCH] compat: helper for detecting unsigned overflow","fromName":"Joshua Juran","fromEmail":"jjuran@gmail.com","sentAt":"2011-02-10T13:23:25Z","receivedAt":"2011-02-10T13:23:25Z","isPatch":true,"sender":{"key":"jjuran@gmail.com","avatar":null},"body":"On Feb 10, 2011, at 4:11 AM, Sverre Rabbelier wrote:\n\n> On Thu, Feb 10, 2011 at 10:35, Jonathan Nieder <jrnieder@gmail.com>  \n> wrote:\n>>       unsigned_add_overflows(a, b)\n>\n>> Define such a macro, expanding roughly to ((a) < UINT_MAX - (b)).\n>> Because the expansion uses each argument only once outside of  \n>> sizeof()\n>> expressions, it is safe to use with arguments that have side effects.\n>\n>> +#define unsigned_add_overflows(a, b) \\\n>> +    ((b) > maximum_unsigned_value_of_type(a) - (a))\n>\n> I'm confused, you say you won't use it twice, and then you do use it  \n> twice?\n\nThe author is asserting that maximum_unsigned_value_of_type() is a  \nfunction of sizeof a, which would have no runtime effect.\n\nJosh\n"}]}