Shik's blog

By Shik, history, 7 years ago, In English

31662632

It's a minimized code based on my segment tree solution for 877E - Danil and a Part-time Job. I got RE during the contest and cannot figured out why. Can anyone reproduce the bug and paste the generated assembly? I cannot reproduce the crash on my Mac/Linux machine...QQ

  • Vote: I like it
  • +54
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I added some words in this code and it passed...

#include <cstdio>

namespace A{ 
    struct Seg {
        int ask(int id, int l, int r, int q) {
            printf("ask %d, %d, %d, %d\n", id, l, r, q);
            fflush(stdout);
            if (l != r) {
                int m = (l + r) / 2;
                if (q <= m) ask(id * 2, l, m, q);
                else ask(id * 2 + 1, m + 1, r, q);
            }
            return 0;
        }
    } seg;

    void my_main() {
        int q;
        scanf("%d", &q);
        printf("q = %d\n",q);
        seg.ask(1, 1, 3, q / q);
        puts("done");
    }
}

int main() {
    A::my_main();
    return 0;
}
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I have tried to remove the unnamed namespace, and it passed as well...orz

»
7 years ago, # |
Rev. 3   Vote: I like it +23 Vote: I do not like it

Good job reducing the test case.

It probably doesn't happen without unnamed namespace because it marks the functions as internal linkage — not callable externally from other cpp files. That gives optimizer much more freedom. It might be possible to repeat without unnamed namespace by making my_main static and ask static non member function. Custom invocations currently don't work so I can't investigate it further.

I have one idea for getting compiled code from Codeforces. I hope it doesn't make the bug disappear. Unfortunately I can't try it out as custom invocations don't work.

»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

It'd nice if there was a way to setup programming environment in exactly the same way as CF. I've tried compiling with mingw-w64 g++6.2 and it works fine. But maybe CF uses another mingw package or something like that.

Assembly seems to be different with and without anonymous namespace but it's impossible to guess the reason of the crash without proper debugging.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    I assume Codeforces uses its home-made package manager (pbox). I believe the exact binaries run on CF are in one of packages.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it +33 Vote: I do not like it

      Huge thanks! I reproduced it with package "mingw-w64" which contains gcc version 6.2. I will try to investigate further.

»
7 years ago, # |
  Vote: I like it +39 Vote: I do not like it

So I've done a bit of research and here's some conclusions:

  • This bug is reproducible only on 32-bit MinGW (or probably if you target 32-bit with 64-bit compiler) and it affects versions starting from at least 4.9 (I didn't check earlier). It was fixed in MinGW starting 7.1 and 6.4.

  • As far as I can tell for ask function gcc ends up using its own "calling convention" where it passes first three arguments as eax, edx, ecx registers and the fourth one on a stack. But on all of the generated calls it doesn't actually pushes the fourth argument to a stack but writes it directly to memory pointed by esp(stack pointer) register but after each call it for some reason subtracts 4 from esp register which I believe shouldn't happen because we didn't move it in any way before call. So esp register points to incorrect memory during ret instruction and program crashes after finishing the first recursive call.

Here's screenshot showing that difference between 6.4 and 6.2 generated assembly mostly consists in removal of esp subtraction.

The things which are unclear to me:

  • Why it's not reproducible on Linux. It seems to generate the same "calling convention" for ask function but code for calls look totally different from MinGW. I don't know what can cause such discrepancy.

  • Where to find relevant bugfix. Have no idea where to find MinGW changelogs, gcc 6.4 fixes doesn't contain anything similar.

  • gcc inling logic is super crazy. Moving my_main out of anonymous namespace leads to whole recursion being inlined inside it but in current code recursive function is actually called.

Morale: Updating to new minor gcc versions could actually be useful.