# [PATCH] fix potential infinite loop given large unsigned integer 14 messages from 2009-08-09 to 2009-08-11. Participants: Ryan Flynn, Junio C Hamano, Erik Faye-Lund, Christian Couder, Johannes Schindelin, Tony Finch, Jeff Epler. Thread: https://gitlist.dev/t/20491 ## Ryan Flynn, 2009-08-09 04:41 Subject: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/a3f15ee60908082141l7b2134cg5ddcef17c45fc888%40mail.gmail.com ``` given n, tried to find i greater than n via i=1, iterate i *= 10. given n sufficiently close to UINT_MAX this will overflow; which can produce i==0, which results in an infinite loop. iteratively dividing n /= 10 does not have this problem, and though division is slower than multiplication this only runs once per `git format-patch --cover-letter` Signed-off-by: pizza --- log-tree.c | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/log-tree.c b/log-tree.c index 6f73c17..53a1bd2 100644 --- a/log-tree.c +++ b/log-tree.c @@ -160,9 +160,9 @@ static void append_signoff(struct strbuf *sb, const char *signoff) static unsigned int digits_in_number(unsigned int number) { - unsigned int i = 10, result = 1; - while (i <= number) { - i *= 10; + unsigned int result = 1; + while (number > 9) { + number /= 10; result++; } return result; -- 1.6.0.4 ``` ## Junio C Hamano, 2009-08-09 06:19 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: <7vy6pta4rd.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7vy6pta4rd.fsf%40alter.siamese.dyndns.org In-Reply-To: ``` Ryan Flynn writes: > given n, tried to find i greater than n via i=1, iterate i *= 10. > given n sufficiently close to UINT_MAX this will overflow; which can > produce i==0, which results in an infinite loop. iteratively dividing > n /= 10 does not have this problem, and though division is slower than > multiplication this only runs once per `git format-patch > --cover-letter` > > Signed-off-by: pizza Pizza? This is somewhat amusing. - digits_in_number() is called only with opt->total that is "int"; - opt->total is the total number of patches. - the return value is used like this: sprintf(buf, "%0*d", digits_in_number(opt->total), opt->nr); and opt->nr runs from 1 to opt->total; the use of "d" would be already wrong anyway even if you computed digits_in_number() correctly. Perhaps we should get rid of this function altogether? ``` ## Junio C Hamano, 2009-08-09 07:38 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: <7v3a81a13z.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v3a81a13z.fsf%40alter.siamese.dyndns.org In-Reply-To: <7vy6pta4rd.fsf@alter.siamese.dyndns.org> ``` Junio C Hamano writes: > Ryan Flynn writes: > >> given n, tried to find i greater than n via i=1, iterate i *= 10. >> given n sufficiently close to UINT_MAX this will overflow; which can >> produce i==0, which results in an infinite loop. iteratively dividing >> n /= 10 does not have this problem, and though division is slower than >> multiplication this only runs once per `git format-patch >> --cover-letter` >> >> Signed-off-by: pizza > > Pizza? > > This is somewhat amusing. > > - digits_in_number() is called only with opt->total that is "int"; > > - opt->total is the total number of patches. > > - the return value is used like this: > > sprintf(buf, "%0*d", digits_in_number(opt->total), opt->nr); > > and opt->nr runs from 1 to opt->total; the use of "d" would be already > wrong anyway even if you computed digits_in_number() correctly. > > Perhaps we should get rid of this function altogether? Or perhaps something stupid like this... builtin-log.c | 6 +++++- log-tree.c | 12 +----------- revision.h | 2 +- 3 files changed, 7 insertions(+), 13 deletions(-) diff --git a/builtin-log.c b/builtin-log.c index 3817bf1..321e8f5 100644 --- a/builtin-log.c +++ b/builtin-log.c @@ -1096,8 +1096,12 @@ int cmd_format_patch(int argc, const char **argv, const char *prefix) total = nr; if (!keep_subject && auto_number && total > 1) numbered = 1; - if (numbered) + if (numbered) { + static char num_buf[64]; rev.total = total + start_number - 1; + sprintf(num_buf, "%d", rev.total); + rev.num_width = strlen(num_buf); + } if (in_reply_to || thread || cover_letter) rev.ref_message_ids = xcalloc(1, sizeof(struct string_list)); if (in_reply_to) { diff --git a/log-tree.c b/log-tree.c index 6f73c17..0d32a6c 100644 --- a/log-tree.c +++ b/log-tree.c @@ -158,16 +158,6 @@ static void append_signoff(struct strbuf *sb, const char *signoff) strbuf_addch(sb, '\n'); } -static unsigned int digits_in_number(unsigned int number) -{ - unsigned int i = 10, result = 1; - while (i <= number) { - i *= 10; - result++; - } - return result; -} - static int has_non_ascii(const char *s) { int ch; @@ -212,7 +202,7 @@ void log_write_email_headers(struct rev_info *opt, struct commit *commit, snprintf(buffer, sizeof(buffer), "Subject: [%s %0*d/%d] ", opt->subject_prefix, - digits_in_number(opt->total), + opt->num_width, opt->nr, opt->total); subject = buffer; } else if (opt->total == 0 && opt->subject_prefix && *opt->subject_prefix) { diff --git a/revision.h b/revision.h index fb74492..21e4d9d 100644 --- a/revision.h +++ b/revision.h @@ -84,7 +84,7 @@ struct rev_info { unsigned int abbrev; enum cmit_fmt commit_format; struct log_info *loginfo; - int nr, total; + int nr, total, num_width; const char *mime_boundary; const char *patch_suffix; int numbered_files; ``` ## Erik Faye-Lund, 2009-08-09 12:25 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: <40aa078e0908090525h7b4d6efeh658e2edcfbe16c7e@mail.gmail.com> URL: https://gitlist.dev/e/40aa078e0908090525h7b4d6efeh658e2edcfbe16c7e%40mail.gmail.com In-Reply-To: <7v3a81a13z.fsf@alter.siamese.dyndns.org> ``` On Sun, Aug 9, 2009 at 9:38 AM, Junio C Hamano wrote: > +               static char num_buf[64]; >                rev.total = total + start_number - 1; > +               sprintf(num_buf, "%d", rev.total); > +               rev.num_width = strlen(num_buf); how about rev.num_width = (int)log10((double)rev.total) + 1; hm? log10() appears to be C99, but can be emulated on earlier C-versions by doing #define log10(x) (log(x) / log(10.0)) -- Erik "kusma" Faye-Lund kusmabite@gmail.com (+47) 986 59 656 ``` ## Ryan Flynn, 2009-08-09 23:16 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/a3f15ee60908091616v3ce41374x873a0cf473d0bd3%40mail.gmail.com In-Reply-To: <7vy6pta4rd.fsf@alter.siamese.dyndns.org> ``` > Perhaps we should get rid of this function altogether? I was thinking of something like that, but figured i'd start small and fix the bug first. ``` ## Ryan Flynn, 2009-08-10 00:23 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/a3f15ee60908091723l3e8a29adw8fbc990f4b0925db%40mail.gmail.com In-Reply-To: <7v3a81a13z.fsf@alter.siamese.dyndns.org> ``` On Sun, Aug 9, 2009 at 3:38 AM, Junio C Hamano wrote: > Junio C Hamano writes: > >> Ryan Flynn writes: >> >>> given n, tried to find i greater than n via i=1, iterate i *= 10. >>> given n sufficiently close to UINT_MAX this will overflow; which can >>> produce i==0, which results in an infinite loop. iteratively dividing >>> n /= 10 does not have this problem, and though division is slower than >>> multiplication this only runs once per `git format-patch >>> --cover-letter` >>> >>> Signed-off-by: pizza >> >> Pizza? >> >> This is somewhat amusing. >> >>  - digits_in_number() is called only with opt->total that is "int"; >> >>  - opt->total is the total number of patches. >> >>  - the return value is used like this: >> >>      sprintf(buf, "%0*d", digits_in_number(opt->total), opt->nr); >> >>    and opt->nr runs from 1 to opt->total; the use of "d" would be already >>    wrong anyway even if you computed digits_in_number() correctly. >> >> Perhaps we should get rid of this function altogether? > > Or perhaps something stupid like this... > >  builtin-log.c |    6 +++++- >  log-tree.c    |   12 +----------- >  revision.h    |    2 +- >  3 files changed, 7 insertions(+), 13 deletions(-) > > diff --git a/builtin-log.c b/builtin-log.c > index 3817bf1..321e8f5 100644 > --- a/builtin-log.c > +++ b/builtin-log.c > @@ -1096,8 +1096,12 @@ int cmd_format_patch(int argc, const char **argv, const char *prefix) >        total = nr; >        if (!keep_subject && auto_number && total > 1) >                numbered = 1; > -       if (numbered) > +       if (numbered) { > +               static char num_buf[64]; >                rev.total = total + start_number - 1; > +               sprintf(num_buf, "%d", rev.total); > +               rev.num_width = strlen(num_buf); > +       } >        if (in_reply_to || thread || cover_letter) >                rev.ref_message_ids = xcalloc(1, sizeof(struct string_list)); >        if (in_reply_to) { > diff --git a/log-tree.c b/log-tree.c > index 6f73c17..0d32a6c 100644 > --- a/log-tree.c > +++ b/log-tree.c > @@ -158,16 +158,6 @@ static void append_signoff(struct strbuf *sb, const char *signoff) >        strbuf_addch(sb, '\n'); >  } > > -static unsigned int digits_in_number(unsigned int number) > -{ > -       unsigned int i = 10, result = 1; > -       while (i <= number) { > -               i *= 10; > -               result++; > -       } > -       return result; > -} > - >  static int has_non_ascii(const char *s) >  { >        int ch; > @@ -212,7 +202,7 @@ void log_write_email_headers(struct rev_info *opt, struct commit *commit, >                snprintf(buffer, sizeof(buffer), >                         "Subject: [%s %0*d/%d] ", >                         opt->subject_prefix, > -                        digits_in_number(opt->total), > +                        opt->num_width, >                         opt->nr, opt->total); >                subject = buffer; >        } else if (opt->total == 0 && opt->subject_prefix && *opt->subject_prefix) { > diff --git a/revision.h b/revision.h > index fb74492..21e4d9d 100644 > --- a/revision.h > +++ b/revision.h > @@ -84,7 +84,7 @@ struct rev_info { >        unsigned int    abbrev; >        enum cmit_fmt   commit_format; >        struct log_info *loginfo; > -       int             nr, total; > +       int             nr, total, num_width; >        const char      *mime_boundary; >        const char      *patch_suffix; >        int             numbered_files; > why carry around a piece of information that is only used in one place and is not expensive to calculate? how about a middle-ground such as: diff --git a/log-tree.c b/log-tree.c index 6f73c17..4888518 100644 --- a/log-tree.c +++ b/log-tree.c @@ -158,14 +158,11 @@ static void append_signoff(struct strbuf *sb, const char *signoff) strbuf_addch(sb, '\n'); } -static unsigned int digits_in_number(unsigned int number) +static int digits_in_number(int number) { - unsigned int i = 10, result = 1; - while (i <= number) { - i *= 10; - result++; - } - return result; + static char num_buf[64]; + sprintf(num_buf, "%u", number); + return (int)strlen(num_buf); } static int has_non_ascii(const char *s) ``` ## Christian Couder, 2009-08-10 05:24 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: <200908100724.53345.chriscool@tuxfamily.org> URL: https://gitlist.dev/e/200908100724.53345.chriscool%40tuxfamily.org In-Reply-To: <40aa078e0908090525h7b4d6efeh658e2edcfbe16c7e@mail.gmail.com> ``` On Sunday 09 August 2009, Erik Faye-Lund wrote: > On Sun, Aug 9, 2009 at 9:38 AM, Junio C Hamano wrote: > > +               static char num_buf[64]; > >                rev.total = total + start_number - 1; > > +               sprintf(num_buf, "%d", rev.total); > > +               rev.num_width = strlen(num_buf); > > how about > rev.num_width = (int)log10((double)rev.total) + 1; > > hm? > > log10() appears to be C99, but can be emulated on earlier C-versions by > doing #define log10(x) (log(x) / log(10.0)) That would mean linking with -lm? Regards, Christian. ``` ## Erik Faye-Lund, 2009-08-10 11:12 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: <40aa078e0908100412l3c2afd1bnda9b10aaf1de383f@mail.gmail.com> URL: https://gitlist.dev/e/40aa078e0908100412l3c2afd1bnda9b10aaf1de383f%40mail.gmail.com In-Reply-To: <200908100724.53345.chriscool@tuxfamily.org> ``` On Mon, Aug 10, 2009 at 7:24 AM, Christian Couder wrote: >> log10() appears to be C99, but can be emulated on earlier C-versions by >> doing #define log10(x) (log(x) / log(10.0)) > > That would mean linking with -lm? I guess so. Are we currently trying to avoid linking to the math-parts of libc? -- Erik "kusma" Faye-Lund kusmabite@gmail.com (+47) 986 59 656 ``` ## Johannes Schindelin, 2009-08-10 12:24 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0908101421340.8324%40intel-tinevez-2-302 In-Reply-To: <40aa078e0908100412l3c2afd1bnda9b10aaf1de383f@mail.gmail.com> ``` Hi, On Mon, 10 Aug 2009, Erik Faye-Lund wrote: > On Mon, Aug 10, 2009 at 7:24 AM, Christian > Couder wrote: > >> log10() appears to be C99, but can be emulated on earlier C-versions by > >> doing #define log10(x) (log(x) / log(10.0)) > > > > That would mean linking with -lm? > > I guess so. Are we currently trying to avoid linking to the math-parts > of libc? Yes. I guess we could fix the overflow thing very easily, though: static unsigned int digits_of_number(unsigned int number) { unsigned int result; for (result = 1; number; number /= 10, result++) ; /* do nothing */ return result; } Ciao, Dscho ``` ## Ryan Flynn, 2009-08-10 16:14 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/a3f15ee60908100914n6d9e11fbk77a90f5619b9a860%40mail.gmail.com In-Reply-To: ``` On Mon, Aug 10, 2009 at 8:24 AM, Johannes Schindelin wrote: > Hi, > > On Mon, 10 Aug 2009, Erik Faye-Lund wrote: > >> On Mon, Aug 10, 2009 at 7:24 AM, Christian >> Couder wrote: >> >> log10() appears to be C99, but can be emulated on earlier C-versions by >> >> doing #define log10(x) (log(x) / log(10.0)) >> > >> > That would mean linking with -lm? >> >> I guess so. Are we currently trying to avoid linking to the math-parts >> of libc? > > Yes. > > I guess we could fix the overflow thing very easily, though: > > static unsigned int digits_of_number(unsigned int number) { >        unsigned int result; >        for (result = 1; number; number /= 10, result++) >                ; /* do nothing */ >        return result; > } > > Ciao, > Dscho > > that is equivalent to the original patch, yes. ``` ## Ryan Flynn, 2009-08-10 16:17 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/a3f15ee60908100917k2a2d6de7ndd5e4ddd1d926cc3%40mail.gmail.com In-Reply-To: ``` On Mon, Aug 10, 2009 at 8:24 AM, Johannes Schindelin wrote: > Hi, > > On Mon, 10 Aug 2009, Erik Faye-Lund wrote: > >> On Mon, Aug 10, 2009 at 7:24 AM, Christian >> Couder wrote: >> >> log10() appears to be C99, but can be emulated on earlier C-versions by >> >> doing #define log10(x) (log(x) / log(10.0)) >> > >> > That would mean linking with -lm? >> >> I guess so. Are we currently trying to avoid linking to the math-parts >> of libc? > > Yes. > > I guess we could fix the overflow thing very easily, though: > > static unsigned int digits_of_number(unsigned int number) { >        unsigned int result; >        for (result = 1; number; number /= 10, result++) >                ; /* do nothing */ >        return result; > } > > Ciao, > Dscho > > whoops, actually yours: digits_of_number(1) -> 2 ``` ## Johannes Schindelin, 2009-08-10 16:53 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0908101850570.8324%40intel-tinevez-2-302 In-Reply-To: ``` Hi, [please cull the quoted text to what you are actually replying to. Thanks] On Mon, 10 Aug 2009, Ryan Flynn wrote: > On Mon, Aug 10, 2009 at 8:24 AM, Johannes > Schindelin wrote: > > > > static unsigned int digits_of_number(unsigned int number) { > >    unsigned int result; > >     for (result = 1; number; number /= 10, result++) > >         ; /* do nothing */ > >     return result; > > } > > whoops, actually yours: digits_of_number(1) -> 2 static unsigned int digits(unsigned int number) { unsigned int result; for (result = 1; (number /= 10); result++) ; /* do nothing */ return result; } I'm sorry, I forgot the "something like this" in my mail. This version is actually tested. It has non-optimal runtime, but then, it does not really matter. Ciao, Dscho ``` ## Tony Finch, 2009-08-10 18:19 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: URL: https://gitlist.dev/e/alpine.LSU.2.00.0908101914470.14039%40hermes-2.csi.cam.ac.uk In-Reply-To: <7v3a81a13z.fsf@alter.siamese.dyndns.org> ``` On Sun, 9 Aug 2009, Junio C Hamano wrote: > + if (numbered) { > + static char num_buf[64]; > rev.total = total + start_number - 1; > + sprintf(num_buf, "%d", rev.total); > + rev.num_width = strlen(num_buf); > + } why not if (numbered) { rev.total = total + start_number - 1; rev.num_width = snprintf(NULL, 0, "%d", rev.total); } ? Tony. -- f.anthony.n.finch http://dotat.at/ GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS. MODERATE OR GOOD. ``` ## Jeff Epler, 2009-08-11 00:55 Subject: Re: [PATCH] fix potential infinite loop given large unsigned integer Message-ID: <20090811005517.GB32235@unpythonic.net> URL: https://gitlist.dev/e/20090811005517.GB32235%40unpythonic.net In-Reply-To: <40aa078e0908090525h7b4d6efeh658e2edcfbe16c7e@mail.gmail.com> ``` On Sun, Aug 09, 2009 at 02:25:40PM +0200, Erik Faye-Lund wrote: > log10() appears to be C99, but can be emulated on earlier C-versions by doing > #define log10(x) (log(x) / log(10.0)) I don't think you'll like the results of this very much. #include #include int main(void) { double n=1; int i, j; for(i=0; i<10; i++, n*=10) { j = (int)(log(n)/log(10)); if(i != j) printf("%d %d\n", i, (int)j); } return 0; } (on my system, 3 of the 10 tested cases give the wrong answer due to rounding) For a tour of some of the difficulties of implementing log10, http://www.cs.berkeley.edu/~wkahan/LOG10HAF.TXT Jeff ```