Interesting bug

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Dave Vandervies

    #1

    Interesting bug

    I just fixed a bug that some of the correctness pedants around here may
    find useful as ammunition.


    The problem was that some code would, very occasionally, die with a
    segmentation violation error. (Not as infrequent as some bugs that
    have been discussed here in the past, but maybe once in an overnight
    run of the program when it was configured to aggressively exercise the
    section that the bug was in.) It was easy enough to trap the error
    (using compiler features that are beyond the scope of this newsgroup)
    and retry, and the retry would always work, but the glitch was still
    Annoying to me and one other correctness pedant I work with.

    Turns out that the offending code looked something like this:

    for(i=0;i<num;i ++)
    if(check(array[i]))
    break;
    if(check(array[i]))
    continue;

    array was a pointer to a malloc'd array of num structs; check() was
    an expression that compared a member of the struct to another value.
    (If the values matched, we didn't need to do anything more in the
    next-outer loop.)

    But if the for loop failed to exit abnormally, the check after it exited
    would attempt to read the value just past the end of the malloc'd space.

    My best guess about what the problem was is that normally this wasn't a
    problem, since the bogus value was Highly Unlikely to match what it was
    being checked against and the program was allowed to read that memory
    (and didn't try to write to it), but occasionally the mallocd space would
    be just at the high end of the process's memory space and attempting to
    read a few bytes past it would access memory that the process didn't own,
    and the OS would trap it.


    This may be useful the next time somebody comes around and tries to
    claim that "It works on my system" or something similar.


    Comments?


    dave

    --
    Dave Vandervies dj3vande@csclub .uwaterloo.ca
    Welcome to comp.lang.c. People here are picky. That's good - it means you can
    (generally) trust the answers you get - or at least, you can trust the answer
    that emerges after a couple of days of bickering. --Richard Heathfield in CLC
  • Joona I Palaste

    #2
    Re: Interesting bug

    Dave Vandervies <dj3vande@csclu b.uwaterloo.ca> scribbled the following:[color=blue]
    > I just fixed a bug that some of the correctness pedants around here may
    > find useful as ammunition.[/color]

    (snip)
    [color=blue]
    > Turns out that the offending code looked something like this:[/color]
    [color=blue]
    > for(i=0;i<num;i ++)
    > if(check(array[i]))
    > break;
    > if(check(array[i]))
    > continue;[/color]

    (snip)
    [color=blue]
    > Comments?[/color]

    As soon as I saw that code (and before I saw your explanation of what it
    did) alarm bells went off my head. "If that for loop exits normally,
    array[i] will be out of bounds." I'm amazed none of your colleagues
    managed to spot it. It's like a flashing red light and a siren saying
    (effectively) "Danger, Will Robinson".

    --
    /-- Joona Palaste (palaste@cc.hel sinki.fi) ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "The question of copying music from the Internet is like a two-barreled sword."
    - Finnish rap artist Ezkimo

    Comment

    • Chris Torek

      #3
      Re: Interesting bug

      [much snippage]
      [color=blue]
      >Dave Vandervies <dj3vande@csclu b.uwaterloo.ca> scribbled the following:[color=green]
      >> for(i=0;i<num;i ++)
      >> if(check(array[i]))
      >> break;
      >> if(check(array[i]))
      >> continue;[/color][/color]

      In article <news:c63v3v$ia q$1@oravannahka .helsinki.fi>
      Joona I Palaste <palaste@cc.hel sinki.fi> writes:[color=blue]
      >As soon as I saw that code (and before I saw your explanation of what it
      >did) alarm bells went off my head. "If that for loop exits normally,
      >array[i] will be out of bounds." I'm amazed none of your colleagues
      >managed to spot it. It's like a flashing red light and a siren saying
      >(effectively ) "Danger, Will Robinson".[/color]

      Errors are often a great deal easier to spot after all the irrelevant
      distractions have been removed. :-)

      It is also easy to read what *should* have been written, rather
      than what was actually written. This is particular true if the
      debugging is being done by the original programmer.
      --
      In-Real-Life: Chris Torek, Wind River Systems
      Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
      email: forget about it http://web.torek.net/torek/index.html
      Reading email is like searching for food in the garbage, thanks to spammers.

      Comment

      • Dave Vandervies

        #4
        Re: Interesting bug

        In article <c63v3v$iaq$1@o ravannahka.hels inki.fi>,
        Joona I Palaste <palaste@cc.hel sinki.fi> wrote:[color=blue]
        >Dave Vandervies <dj3vande@csclu b.uwaterloo.ca> scribbled the following:[color=green]
        >> I just fixed a bug that some of the correctness pedants around here may
        >> find useful as ammunition.[/color]
        >
        >(snip)
        >[color=green]
        >> Turns out that the offending code looked something like this:[/color]
        >[color=green]
        >> for(i=0;i<num;i ++)
        >> if(check(array[i]))
        >> break;
        >> if(check(array[i]))
        >> continue;[/color]
        >
        >(snip)
        >[color=green]
        >> Comments?[/color]
        >
        >As soon as I saw that code (and before I saw your explanation of what it
        >did) alarm bells went off my head. "If that for loop exits normally,
        >array[i] will be out of bounds." I'm amazed none of your colleagues
        >managed to spot it. It's like a flashing red light and a siren saying
        >(effectively ) "Danger, Will Robinson".[/color]

        So was I, once I found it. (It's incredible how much easier these
        problems are to find when you've narrowed them down to a few lines of
        code.) The problem was that we had another 2500 lines of code in that
        module that were doing all sorts of interesting things with pointers,
        so we were looking for problems with losing track of the pointers there,
        not looking for things like this one. (But I figured that neither
        the newsgroup nor my employer would be terribly impressed if I posted
        2500 lines of code in my description of the problem instead of just a
        paraphrase of the snippet where the bug actually was.)

        Once we had the time (because we were looking for something else in that
        part of the code anyways) to add checkpoints every few lines and I saw
        which checkpoints the problem was happening between, it took about five
        minutes to identify and fix the problem.


        dave

        --
        Dave Vandervies dj3vande@csclub .uwaterloo.ca
        [S]ome of us take a little convincing that our bugs are in fact bugs, which
        is why we have such delightfully energetic discussions on occasion.
        --Richard Heathfield in comp.lang.c

        Comment

        • Christopher Benson-Manica

          #5
          Re: Interesting bug

          Chris Torek <nospam@torek.n et> spoke thus:
          [color=blue]
          > Errors are often a great deal easier to spot after all the irrelevant
          > distractions have been removed. :-)[/color]

          The most aggravating are stupid typos - I had a recent bug caused by
          misspelling "error" as "errror" that had to be pointed out to me
          because I could not grasp such a simple mistake ;)

          --
          Christopher Benson-Manica | I *should* know what I'm talking about - if I
          ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

          Comment

          • CBFalconer

            #6
            Re: Interesting bug

            Dave Vandervies wrote:[color=blue]
            >[/color]
            .... snip ...[color=blue]
            >
            > Turns out that the offending code looked something like this:
            >
            > for(i=0;i<num;i ++)
            > if(check(array[i]))
            > break;
            > if(check(array[i]))
            > continue;
            >
            > array was a pointer to a malloc'd array of num structs; check()
            > was an expression that compared a member of the struct to another
            > value. (If the values matched, we didn't need to do anything more
            > in the next-outer loop.)
            >
            > But if the for loop failed to exit abnormally, the check after it
            > exited would attempt to read the value just past the end of the
            > malloc'd space.[/color]

            So why didn't the code read:

            while (somecondition) {
            for (i = 0; i < num; i++)
            if (check(array[i])) break;
            if (i < num) continue;
            /* check(array[i]) must be false for all i < num */
            }

            --
            A: Because it fouls the order in which people normally read text.
            Q: Why is top-posting such a bad thing?
            A: Top-posting.
            Q: What is the most annoying thing on usenet and in e-mail?


            Comment

            • Christian Bau

              #7
              Re: Interesting bug

              In article <c64n5h$eh8$1@c hessie.cirr.com >,
              Christopher Benson-Manica <ataru@nospam.c yberspace.org> wrote:
              [color=blue]
              > Chris Torek <nospam@torek.n et> spoke thus:
              >[color=green]
              > > Errors are often a great deal easier to spot after all the irrelevant
              > > distractions have been removed. :-)[/color]
              >
              > The most aggravating are stupid typos - I had a recent bug caused by
              > misspelling "error" as "errror" that had to be pointed out to me
              > because I could not grasp such a simple mistake ;)[/color]

              I always wonder how many switch statements contain a

              defualt:

              label. And it is legal C as well.

              Comment

              • Christian Bau

                #8
                Re: Interesting bug

                In article <4085C52E.29702 7AA@yahoo.com>,
                CBFalconer <cbfalconer@yah oo.com> wrote:
                [color=blue]
                > Dave Vandervies wrote:[color=green]
                > >[/color]
                > ... snip ...[color=green]
                > >
                > > Turns out that the offending code looked something like this:
                > >
                > > for(i=0;i<num;i ++)
                > > if(check(array[i]))
                > > break;
                > > if(check(array[i]))
                > > continue;
                > >
                > > array was a pointer to a malloc'd array of num structs; check()
                > > was an expression that compared a member of the struct to another
                > > value. (If the values matched, we didn't need to do anything more
                > > in the next-outer loop.)
                > >
                > > But if the for loop failed to exit abnormally, the check after it
                > > exited would attempt to read the value just past the end of the
                > > malloc'd space.[/color]
                >
                > So why didn't the code read:
                >
                > while (somecondition) {
                > for (i = 0; i < num; i++)
                > if (check(array[i])) break;
                > if (i < num) continue;
                > /* check(array[i]) must be false for all i < num */
                > }[/color]

                Sometimes the end condition is not that simple; the posted code seems to
                be several hundred lines of code, condensed down to the actual error.
                But it would be simple to introduce a boolean variable that is set to
                TRUE when you break from the loop, and I would probably do that in cases
                when the logic of the loop itself gets complicated.

                Comment

                • Peter Nilsson

                  #9
                  Re: Interesting bug

                  "Christian Bau" <christian.bau@ cbau.freeserve. co.uk> wrote in message
                  news:christian. bau-468E32.07095521 042004@slb-newsm1.svr.pol. co.uk...[color=blue]
                  > In article <c64n5h$eh8$1@c hessie.cirr.com >,
                  > Christopher Benson-Manica <ataru@nospam.c yberspace.org> wrote:
                  >[color=green]
                  > > Chris Torek <nospam@torek.n et> spoke thus:
                  > >[color=darkred]
                  > > > Errors are often a great deal easier to spot after all the irrelevant
                  > > > distractions have been removed. :-)[/color]
                  > >
                  > > The most aggravating are stupid typos - I had a recent bug caused by
                  > > misspelling "error" as "errror" that had to be pointed out to me
                  > > because I could not grasp such a simple mistake ;)[/color]
                  >
                  > I always wonder how many switch statements contain a
                  >
                  > defualt:
                  >
                  > label. And it is legal C as well.[/color]

                  But at least one compiler can pick it up...

                  % gcc -Wall default.c
                  default.c: In function `main':
                  default.c:8: warning: label `defualt' defined but not used

                  --
                  Peter


                  Comment

                  • Eric Sosman

                    #10
                    Re: Interesting bug

                    Christian Bau wrote:[color=blue]
                    >
                    > In article <4085C52E.29702 7AA@yahoo.com>,
                    > CBFalconer <cbfalconer@yah oo.com> wrote:
                    >[color=green]
                    > > So why didn't the code read:
                    > >
                    > > while (somecondition) {
                    > > for (i = 0; i < num; i++)
                    > > if (check(array[i])) break;
                    > > if (i < num) continue;
                    > > /* check(array[i]) must be false for all i < num */
                    > > }[/color]
                    >
                    > Sometimes the end condition is not that simple; the posted code seems to
                    > be several hundred lines of code, condensed down to the actual error.
                    > But it would be simple to introduce a boolean variable that is set to
                    > TRUE when you break from the loop, and I would probably do that in cases
                    > when the logic of the loop itself gets complicated.[/color]

                    This is an irksome weakness of C (and most other languages
                    I've programmed in): A loop with multiple termination conditions
                    gives no direct evidence of which condition actually caused it
                    to terminate. You find yourself at the statement after the loop
                    with no notion of how you got there, and you usually wind up
                    either re-testing a condition already tested (ick) or testing
                    a state flag that summarizes the earlier test (ick again).

                    Some languages have an "alternate exit" formalism for such
                    situations, but in most that I have encountered it looked an
                    awful lot like an unrestricted goto. Some languages have
                    "exception" mechanisms, but it's usually been a fairly heavy-
                    weight construct, too expensive for routine use ("exceptiona l"
                    shouldn't be "routine").

                    However, C lacks such a facility. It follows that nearly
                    every loop with multiple termination conditions should be
                    followed promptly by a test; if there's no test, there's most
                    likely a bug.

                    --
                    Eric.Sosman@sun .com

                    Comment

                    • CBFalconer

                      #11
                      Re: Interesting bug

                      Eric Sosman wrote:[color=blue]
                      > Christian Bau wrote:[color=green]
                      >> CBFalconer <cbfalconer@yah oo.com> wrote:
                      >>[color=darkred]
                      >>> So why didn't the code read:
                      >>>
                      >>> while (somecondition) {
                      >>> for (i = 0; i < num; i++)
                      >>> if (check(array[i])) break;
                      >>> if (i < num) continue;
                      >>> /* check(array[i]) must be false for all i < num */
                      >>> }[/color]
                      >>
                      >> Sometimes the end condition is not that simple; the posted code
                      >> seems to be several hundred lines of code, condensed down to the
                      >> actual error. But it would be simple to introduce a boolean
                      >> variable that is set to TRUE when you break from the loop, and I
                      >> would probably do that in cases when the logic of the loop
                      >> itself gets complicated.[/color]
                      >
                      > This is an irksome weakness of C (and most other languages
                      > I've programmed in): A loop with multiple termination conditions
                      > gives no direct evidence of which condition actually caused it
                      > to terminate. You find yourself at the statement after the loop
                      > with no notion of how you got there, and you usually wind up
                      > either re-testing a condition already tested (ick) or testing
                      > a state flag that summarizes the earlier test (ick again).
                      >
                      > Some languages have an "alternate exit" formalism for such
                      > situations, but in most that I have encountered it looked an
                      > awful lot like an unrestricted goto. Some languages have
                      > "exception" mechanisms, but it's usually been a fairly heavy-
                      > weight construct, too expensive for routine use ("exceptiona l"
                      > shouldn't be "routine").
                      >
                      > However, C lacks such a facility. It follows that nearly
                      > every loop with multiple termination conditions should be
                      > followed promptly by a test; if there's no test, there's most
                      > likely a bug.[/color]

                      The presence of this multiple termination in itself is a strong
                      hint that a dummy value is needed to simplify the loop condition,
                      followed by a simple test. In the case of the above it might have
                      been, with a suitable expansion of array[]:

                      while (somecondition) {
                      array[num] = suitablevalue; i = 0;
                      while (!check(array[i])) i++;
                      if (i < num) continue;
                      /* check(array[i]) must be false for all i < num */
                      }

                      --
                      A: Because it fouls the order in which people normally read text.
                      Q: Why is top-posting such a bad thing?
                      A: Top-posting.
                      Q: What is the most annoying thing on usenet and in e-mail?


                      Comment

                      • Dan Pop

                        #12
                        Re: Interesting bug

                        In <408681CC.5B706 363@sun.com> Eric Sosman <Eric.Sosman@su n.com> writes:
                        [color=blue]
                        > This is an irksome weakness of C (and most other languages
                        >I've programmed in): A loop with multiple termination conditions
                        >gives no direct evidence of which condition actually caused it
                        >to terminate. You find yourself at the statement after the loop
                        >with no notion of how you got there, and you usually wind up
                        >either re-testing a condition already tested (ick) or testing
                        >a state flag that summarizes the earlier test (ick again).
                        >
                        > Some languages have an "alternate exit" formalism for such
                        >situations, but in most that I have encountered it looked an
                        >awful lot like an unrestricted goto. Some languages have
                        >"exception" mechanisms, but it's usually been a fairly heavy-
                        >weight construct, too expensive for routine use ("exceptiona l"
                        >shouldn't be "routine").
                        >
                        > However, C lacks such a facility.[/color]

                        Nope, it's called goto.
                        [color=blue]
                        >It follows that nearly
                        >every loop with multiple termination conditions should be
                        >followed promptly by a test; if there's no test, there's most
                        >likely a bug.[/color]

                        I have yet to understand this irrational fear of using goto where it is
                        called for (i.e. any place where it helps simplifying the code structure).

                        Dan
                        --
                        Dan Pop
                        DESY Zeuthen, RZ group
                        Email: Dan.Pop@ifh.de

                        Comment

                        • Eric Sosman

                          #13
                          Re: Interesting bug

                          Dan Pop wrote:[color=blue]
                          >
                          > In <408681CC.5B706 363@sun.com> Eric Sosman <Eric.Sosman@su n.com> writes:
                          >[color=green]
                          > > This is an irksome weakness of C (and most other languages
                          > >I've programmed in): A loop with multiple termination conditions
                          > >gives no direct evidence of which condition actually caused it
                          > >to terminate. You find yourself at the statement after the loop
                          > >with no notion of how you got there, and you usually wind up
                          > >either re-testing a condition already tested (ick) or testing
                          > >a state flag that summarizes the earlier test (ick again).
                          > >
                          > > Some languages have an "alternate exit" formalism for such
                          > >situations, but in most that I have encountered it looked an
                          > >awful lot like an unrestricted goto. Some languages have
                          > >"exception" mechanisms, but it's usually been a fairly heavy-
                          > >weight construct, too expensive for routine use ("exceptiona l"
                          > >shouldn't be "routine").
                          > >
                          > > However, C lacks such a facility.[/color]
                          >
                          > Nope, it's called goto.[/color]

                          Perhaps my use of "such a facility" was unclear. I meant
                          it to mean "a facility that solves the problem posed in the
                          first paragraph without the objections mentioned in the second."
                          [color=blue][color=green]
                          > >It follows that nearly
                          > >every loop with multiple termination conditions should be
                          > >followed promptly by a test; if there's no test, there's most
                          > >likely a bug.[/color]
                          >
                          > I have yet to understand this irrational fear of using goto where it is
                          > called for (i.e. any place where it helps simplifying the code structure).[/color]

                          My fear of goto is not irrational, but some consider it
                          unnatural: there is disagreement about whether zero is a
                          natural number. My first programming language was FORTRAN II,
                          which would probably have driven me to another field of endeavor
                          had I suffered from gotophobia.

                          --
                          Eric.Sosman@sun .com

                          Comment

                          • Dan Pop

                            #14
                            Re: Interesting bug

                            In <4086ADB3.AE223 C34@sun.com> Eric Sosman <Eric.Sosman@su n.com> writes:
                            [color=blue]
                            >natural number. My first programming language was FORTRAN II,
                            >which would probably have driven me to another field of endeavor
                            >had I suffered from gotophobia.[/color]

                            Back then, gotophobia had not been yet invented ;-)

                            I started with FORTRAN IV, followed by several assembly languages: having
                            gotos with symbolic destinations (instead of F-IV's 1 to 5 digits) was
                            like being in programmers' heaven... (but I had to do all the assemblying
                            by hand, having no access to any kind of hosted platform...).

                            Dan
                            --
                            Dan Pop
                            DESY Zeuthen, RZ group
                            Email: Dan.Pop@ifh.de

                            Comment

                            • Joona I Palaste

                              #15
                              Re: Interesting bug

                              Dan Pop <Dan.Pop@cern.c h> scribbled the following:[color=blue]
                              > In <4086ADB3.AE223 C34@sun.com> Eric Sosman <Eric.Sosman@su n.com> writes:[color=green]
                              >>natural number. My first programming language was FORTRAN II,
                              >>which would probably have driven me to another field of endeavor
                              >>had I suffered from gotophobia.[/color][/color]
                              [color=blue]
                              > Back then, gotophobia had not been yet invented ;-)[/color]
                              [color=blue]
                              > I started with FORTRAN IV, followed by several assembly languages: having
                              > gotos with symbolic destinations (instead of F-IV's 1 to 5 digits) was
                              > like being in programmers' heaven... (but I had to do all the assemblying
                              > by hand, having no access to any kind of hosted platform...).[/color]

                              Right on the money, Dan. I started programming on C=64 BASIC V2, which
                              is an extremely cut-down version of BASIC by 1980s standards. Back then
                              GOTO with a symbolic label rather than a hard-coded line number as the
                              destination was like science fiction...

                              --
                              /-- Joona Palaste (palaste@cc.hel sinki.fi) ------------- Finland --------\
                              \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
                              "'So called' means: 'There is a long explanation for this, but I have no
                              time to explain it here.'"
                              - JIPsoft

                              Comment

                              Working...