The Infinite Loop Mystery

Today’s puzzle is about some code behaving horribly wrong.

Recently, I was working on some operating system project and hacking on the code to switch between privileged and non-privileged mode. I could switch modes successfully and intercept traps when in non-privileged mode.

Then I wanted to check whether I could handle timer interrupts correctly, so I added this to my non-privileged code, to give the timer interrupt a chance to fire:

    volatile int i;
    for (i=0; i<10000; i++);

Timer interrupts were handled correctly and eventually returned to the non-privileged code – but the delay code turned into an infinite loop!

I changed to loop to count only to 10, and I changed it to count down instead of up, but the result remained the same. I looked at the generated assembly. It looked like this:

    movl    $10, 0xfc(%ebp)	// i = 10
    jmp     1f			// goto 1
2:
    movl    0xfc(%ebp), %eax	// %eax = i
    decl    %eax		// %eax--
    movl    %eax,0xfc(%ebp)	// i = %eax
1:
    movl    0xfc(%ebp), %eax	// %eax = i
    testl   %eax, %eax		// if (%eax > 0)
    jg      2b			// goto 2

It looked fine. On every timer interrupt, I dumped %eax, and it was stuck at 10. I debugged my pusha/popa code to save and restore registers between modes, and it was okay. I debugged my flag handing code, and flags were fine.

Then I replaced my C code with the generated assembly code and added instructions that copied the value of %eax before the “decl” into %ebx, and after the “decl” into %ecx and added a trap instruction right after that to have privileged mode print out the values of the three registers.

    movl    $10, 0xfc(%ebp)	// i = 10
    jmp     1f			// goto 1
2:
    movl    0xfc(%ebp), %eax	// %eax = i
    movl    %eax, %ebx          // value before
    decl    %eax		// %eax--
    movl    %eax, %ecx          // value after
    TRAP
    movl    %eax,0xfc(%ebp)	// i = %eax
1:
    movl    0xfc(%ebp), %eax	// %eax = i
    testl   %eax, %eax		// if (%eax > 0)
    jg      2b			// goto 2

The result was %eax = %ebx = %ecx = 10. This is when I understood what was going on.

Please share your comments below. :-)

18 thoughts on “The Infinite Loop Mystery

  1. Alex

    Hey there,

    at first I stumbled across your C-version of the loop where you’ve written “for (i=0; i<10000; i–)”. This obviously isn’t the behaviour that you wanted. But then I realized that this must have been a typo when you wrote your article because it doesn’t fit your further description and also not the pasted assembler source.
    However, in the end I wasn’t able to figure out your puzzle, but I’m interested in the solution which has something to do with an unwanted side-effect, I suppose. Now, please :), what is it?

    Reply
  2. James

    Hmm..

    Offset in your context-switching routine? I.e, when returning to non-privilegied, the previous content of %eax ends up in %ebx, and %ebx shows up in %ecx ?

    If so, I’d venture to guess that the cause is that some traps push an error-code onto the stack when entering privileged mode..

    Reply
  3. Neal Walfield

    In long mode, the decl reg instruction is not supported as such. The op-code is reused as a REX prefix. From the assembly, it doesn’t look like you are running in long mode as you are using ebp and not rbp as your frame pointer. Perhaps the issue is that you were actually running the code in long mode but your code was compiled for legacy mode?

    Reply
  4. Darkstar

    How exactly are you doing the TRAP? INT3? INTO? Last time I checked there was no “TRAP” instruction on x86 (but I stopped doing stuff like this when 386s were still used so it might be a newer addition)

    If this was on MIPS then I’d suggest speculative execution (delay slot or something) but x86 should behave pretty well with respect to that….

    -Darkstar

    Reply
  5. Ge0rG

    My first guess would have been signed/unsigned integer promotion, however that only should cause problems with the depicted C source (decrease i, test for <10000). The assembly code looks clean in that direction.
    My second guess would be an erroneously set ESP pointer, causing stack corruption. However the C compiler should have taken care of that – so it must be something else again.
    The DEC instruction can be explicitly prefixed with a LOCK, causing the operation to be atomic. However I’m pretty sure that only matters for direct memory decrement, not for register access.

    Still, a race condition in the register access seems to be the only plausible cause, because ECX is 10 right after MOV ECX, EAX after the DEC. If this is not a CPU erratum, my guess is: you actually have to run “LOCK DEC EAX” to make that code work.

    Reply
  6. isobel

    If the code runs in 64-bit mode, and decl %eax has been encoded as 0×48+rd, the operation may not do what it is supposed to do, as in this case it is considered a REX prefix not a DEC.

    Just a wild guess.

    Reply
  7. BastiX

    As already mentioned, the behavior would make sense if you
    forgot to return to compatibility mode upon kernel exit.
    But then again:

    > I debugged my pusha/popa code

    Which doesn’t sound like it’s a 64-bit kernel in the first place.
    That’s kinda confusing. So either something very very wired
    is happening (not related to longmode) or the kernel in question
    is …mh… XNU?

    Reply
  8. Anonymous

    That’s bizarre. Although, here’s our guess: you were sleeping. Yeah, it was just a dream.

    Reply
  9. Tal

    if i is volatile, why on earth did the compiler use @eax as a temporary register???

    Did you define a global i variable somewhere?

    Tal.

    Reply
  10. Anonymous

    So, what’s the answer? Was anyone of us even close?

    @Tal:
    That’s perfectly valid behaviour for volatile variables – we see it all the time in the VC9, for example. The difference from non-volatile vars is in fact what for volatile compiler saves variable’s value in memory after every single modification (and loads it from memory before every usage point).

    Reply
  11. strik

    Hello Ge0rG,

    nice to meet you here. ;)

    > My first guess would have been signed/unsigned integer promotion,
    > however that only should cause problems with the depicted C source
    > (decrease i, test for direction.

    as i already is an int, and in the code, nothing “bigger” or unsigned occurs, nothing can be promoted here. So, this one cannot appear.

    > My second guess would be an erroneously set ESP pointer, causing stack
    > corruption.

    As we both know, you have experience with this in the (RT-)Linux KERNEL, right? ;)

    > The DEC instruction can be explicitly prefixed with a LOCK, causing the
    > operation to be atomic. However I’m pretty sure that only matters for
    > direct memory decrement, not for register access.

    In fact, you cannot use LOCK with non-memory operands. The Intel instruction set reference, p. 3-533 (version from June 2005), clearly states:

    “The LOCK prefix can be prepended only to the following instructions and
    only to those forms of the instructions where the destination operand is a
    memory operand: [...] DEC, INC, [...].”

    Since there is no memory operand, LOCK cannot be used here.

    > Still, a race condition in the register access seems to be the only
    > plausible cause, because ECX is 10 right after MOV ECX, EAX after the
    > DEC. If this is not a CPU erratum, my guess is: you actually have to run
    > “LOCK DEC EAX” to make that code work.

    Nope.

    Without having experience with x64, the REX byte reason seems to me to be the most likely. However, I am not sure how it would interpret the movl %eax, %ecx or the movl %eax,0xfc(%ebp) afterwards, as REX is a kind of prefix only.

    Thus, to be more precise: I do not have any idea. Really. ;)

    Spiro

    Reply
  12. isobel

    If the code runs in 64-bit mode, and decl %eax has been encoded as 0×48+rd, the operation may not do what it is supposed to do, as in this case it is considered a REX prefix not a DEC.

    Just a wild guess.

    And now a wild proof…

    $ cat x.c
    void a(void)
    {
    volatile int i;
    for (i = 10; i; i–);
    }

    $ gcc -march=i386 -c x.c
    $ objdump -d x.o

    x.o: file format elf32-i386

    Disassembly of section .text:

    00000000 :
    0: 55 push %ebp
    1: 89 e5 mov %esp,%ebp
    3: 83 ec 10 sub $0×10,%esp
    6: c7 45 fc 0a 00 00 00 movl $0xa,-0×4(%ebp)
    d: eb 07 jmp 16

    f: 8b 45 fc mov -0×4(%ebp),%eax
    12: 48 dec %eax
    13: 89 45 fc mov %eax,-0×4(%ebp)
    16: 8b 45 fc mov -0×4(%ebp),%eax
    19: 85 c0 test %eax,%eax
    1b: 75 f2 jne f

    1d: c9 leave
    1e: c3 ret

    $ objdump -d -M x86-64 x.o

    x.o: file format elf32-i386

    Disassembly of section .text:

    00000000 :
    0: 55 push %rbp
    1: 89 e5 mov %esp,%ebp
    3: 83 ec 10 sub $0×10,%esp
    6: c7 45 fc 0a 00 00 00 movl $0xa,-0×4(%rbp)
    d: eb 07 jmp 16

    f: 8b 45 fc mov -0×4(%rbp),%eax
    12: 48 89 45 fc mov %rax,-0×4(%rbp)
    16: 8b 45 fc mov -0×4(%rbp),%eax
    19: 85 c0 test %eax,%eax
    1b: 75 f2 jne f

    1d: c9 leaveq
    1e: c3 retq

    For those still not seeing it:

    32-bit
    f: 8b 45 fc mov -0×4(%ebp),%eax
    12: 48 dec %eax
    13: 89 45 fc mov %eax,-0×4(%ebp)

    64-bit
    f: 8b 45 fc mov -0×4(%rbp),%eax
    12: 48 89 45 fc mov %rax,-0×4(%rbp)

    Yes, the DEC dissappears…

    Just a wild hint.

    Reply
  13. fmarmond

    we discussed about it on irc freenode ##asm, and we discarded the x86-64 mode because the given sample only uses 32b registers. So the C code was certainly compiled in 32b mode…
    But discarding it, we didn’t found any other solution (except a bug in the code not shown :) )

    Reply
  14. isobel

    Just to clarify it… As shown in the above example, the issue can happen if for some reason the 32-bit binary code (… 8b 45 fc 48 89 45 fc …) runs in 64-bit mode.
    In that case, the processor will interpret the opcodes in 64-bit mode, and the same binary code then translates to different instructions. One of the side effects is that the DEC “vanishes”.

    Now Michael tell if the context switch code was buggy…

    Reply
  15. fmarmond

    ok, some kind of 32bit code executed in 64b mode (like a wrong return without restoring mode). That makes sense to me.

    Reply
  16. Michael Steil

    You guys are right! I was running 32 bit code in 64 bit mode (incorrect CS), which made the “dec” opcode (0×48) be interpreted as a prefix.

    Tom: “Hm, does the ‘dec’ need some special prefix in 64 bit mode?”
    me: “‘dec’ *is* a prefix in 64 bit mode!”

    The virtual medals go to Neal (idea), isobel (proof) and Erik (creative approach).

    @Erik: Actually, I was convinced once that the accumulator was broken on my 8051 because I loaded one value but my debug code in the next instruction would always return something different. As it turned out, I forgot to stop the program there, and it looped back to the debug code later, giving me the impression the dumped data was from the first time the code had been reached.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>