Tests fail with gcc stack protection

[ganesh-k13]

Hi, as discussed previously, I wanted to see if gcc works. But I was getting this error and a few warnings:

mkdir -p ../build/test/../src
gcc -g -Wall -Wextra -pedantic -I../include -fprofile-arcs -ftest-coverage -MMD -c ../src/log.c -o ../build/tes
t/../src/log.o
mkdir -p ../build/test
gcc -g -L../build/src -L../build/test --coverage  ../build/test/test_gc.o ../build/test/../src/log.o -o ../buil
d/test/test_gc
make[1]: Leaving directory '/root/gc/test'
./build/test/test_gc
---=[ GC tests
Heap allocation referenced from stack should be tagged
Tests run: 5
profiling:/root/gc/test/../build/test/test_gc.gcda:Version mismatch - expected A74* got 402*
Makefile:10: recipe for target 'test' failed
make: *** [test] Error 1

I was hoping I can look into this if it is an actual issue and not some local system problem with some dependencies.

[mkirchner]

That would be greatly appreciated. In particular the Heap allocation referenced from stack... is an interesting one. I never tested stack scanning using gcc, but it should work. Regarding the warning about the Version mismatch, that's gcov.

[ganesh-k13]

Here is my initial RCA:
GCC Result:

Breakpoint 1, test_gc_mark_stack () at test_gc.c:196
196         int** five_ptr = gc_malloc(&gc_, 2*sizeof(int*));
(gdb) n
197         gc_mark_stack(&gc_);
(gdb) p *(gc_.allocs->allocs[32])
$1 = {ptr = 0x555555762b90, size = 16, tag = 0 '\000', dtor = 0x0, next = 0x0}
(gdb) n
198         Allocation* a = gc_allocation_map_get(gc_.allocs, five_ptr);
(gdb) p *(gc_.allocs->allocs[32])
$2 = {ptr = 0x555555762b90, size = 16, tag = 0 '\000', dtor = 0x0, next = 0x0}
(gdb) p five_ptr
$3 = (int **) 0x555555762b90

CLANG Result:

Breakpoint 1, test_gc_mark_stack () at test_gc.c:196
196         int** five_ptr = gc_malloc(&gc_, 2*sizeof(int*));
(gdb) p *(gc_.allocs->allocs[16])
Cannot access memory at address 0x0
(gdb) n
197         gc_mark_stack(&gc_);
(gdb) p *(gc_.allocs->allocs[16])
$1 = {ptr = 0x612c10, size = 16, tag = 0 '\000', dtor = 0x0, next = 0x0}
(gdb) n
198         Allocation* a = gc_allocation_map_get(gc_.allocs, five_ptr);
(gdb) p *(gc_.allocs->allocs[16])
$2 = {ptr = 0x612c10, size = 16, tag = 2 '\002', dtor = 0x0, next = 0x0}

Basically gc_mark_stack fails to hit on five_ptrs, I'll see more as to why it is so.

[ganesh-k13]

I narrowed down the problem to this:
in clang:

. // in gc_mark_stack()
.
.
Checking stack location 0x7fffffffe33d with value 0x611c10000000
Checking stack location 0x7fffffffe33e with value 0x611c100000
Checking stack location 0x7fffffffe33f with value 0x611c1000
Checking stack location 0x7fffffffe340 with value 0x611c10 <------------ LOOK HERE
Checking stack location 0x7fffffffe341 with value 0x100000000000611c
Checking stack location 0x7fffffffe342 with value 0x3010000000000061
.
.
.
(gdb) bt
#0  __GI_raise (sig=<optimized out>) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x00000000004030bf in gc_mark_stack (gc=0x7fffffffe350) at ./../src/gc.c:529
#2  0x0000000000407045 in test_gc_mark_stack () at test_gc.c:197
#3  0x0000000000404f69 in test_suite () at test_gc.c:400
#4  0x00000000004041b8 in main () at test_gc.c:412
(gdb) f 2
#2  0x0000000000407045 in test_gc_mark_stack () at test_gc.c:197
197         gc_mark_stack(&gc_);
(gdb) p five_ptr
$1 = (int **) 0x611c10
(gdb) p &five_ptr
$2 = (int ***) 0x7fffffffe340 <------------------------------------------------- SAME VALUE

But in case of gcc:

.
.
.
Checking stack location 0x7fffffffe348 with value 0x40
Checking stack location 0x7fffffffe349 with value 0x9000000000000000
Checking stack location 0x7fffffffe34a with value 0x2b90000000000000
Checking stack location 0x7fffffffe34b with value 0x762b900000000000
// ends here
(gdb) bt
#0  __GI_raise (sig=<optimized out>) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x0000555555557b21 in gc_mark_stack (gc=0x7fffffffe360) at ../src/gc.c:529
#2  0x000055555555923a in test_gc_mark_stack () at test_gc.c:197
#3  0x0000555555559f2a in test_suite () at test_gc.c:400
#4  0x000055555555a17c in main () at test_gc.c:412
(gdb) f 2
#2  0x000055555555923a in test_gc_mark_stack () at test_gc.c:197
197         gc_mark_stack(&gc_);
(gdb) p five_ptr
$1 = (int **) 0x555555762b90
(gdb) p &five_ptr
$2 = (int ***) 0x7fffffffe350 <--------------------- Beyond last value, so it'll never get tagged
(gdb) x 0x7fffffffe350
0x7fffffffe350: 0x55762b90

Any idea how to proceed? Although we create bos then five_ptr and then only pos in fn, five_ptr still goes beyond the two

[EDIT]:
Seems to be a fundamental problem: https://stackoverflow.com/questions/26434289/gcc-stack-memory-allocation

[mkirchner]

This looks like variable reordering for stack protection. Can you give me your platform/os/gc versions?

[mkirchner]

Hey @ganesh-k13, I looked into this. One option seems to be to use __builtin_frame_address(0) to get the bottom-of-stack address. The builtin is available in both, GCC and clang. AFAICT, this works fine in clang but I still see failing tests with GCC where the gc run fails to detect and collect what is expected to be collected. It's super hard for me to debug this since I don't have a GCC setup.
Would you be able to take a stab at this, i.e. using the builtin and see why the tests still fail w/ GCC?

[ganesh-k13]

@mkirchner sure, thanks a lot for the info, I'll look into this one.

[ssrlive]

I think this line is wrong.

gc/src/gc.c

Line 522 in 0fc3a84

gc_mark_alloc(gc, *(void**)p);

because char dummy; is a stack var, is't value is random. if we change the code link below

void gc_mark_stack(GarbageCollector* gc)
{
    LOG_DEBUG("Marking the stack (gc@%p) in increments of %ld", (void*) gc, sizeof(char));
    char dummy[sizeof(void *)] = { 0 };
    void *tos = (void*) dummy;
    void *bos = gc->bos;
    if (tos > bos) {
        void* tmp = tos;
        tos = gc->bos;
        bos = tmp;
    }
    for (char* p = (char*) tos; p < (char*) bos; ++p) {
        // LOG_DEBUG("Checking stack location %p with value %p", (void*) p, *(void**)p);
        gc_mark_alloc(gc, *(void**)p);
    }
}

the express of *(void**)p will get 0, I think it is not your wish.

@mkirchner, is your mean is the following?

    uintptr_t *tos=(uintptr_t*)(&tos);

[ganesh-k13]

Hi @ssrlive, value of the variable is not important, we only need it to get the location. Basic assumption is like this:

1. Create a var called bos, we start tracking from here.
2. Before tagging we create a variable called tos.
3. So all variables created between those two variables in terms of time will reside in a stack address between those two, meaning: p(stack address) and value *(void**)p (value at that location)
4. Thus in the loop, five_ptr will eventually correspond to one of *(void**)p, and will get tagged.

So that code(logically at least) is right as far as I know, @mkirchner thoughts on this?

[ssrlive]

We assume that all variables on the stack are the same size. But in fact they are not always the same size.
Therefore, searching the stack with boundaries of the same size may not necessarily find the value of a variable. The value of the variable may be truncated.

[ganesh-k13]

@ssrlive , you are absolutely right about the value to be incorrect, in fact take a look at my trace in clang comment:

Checking stack location 0x7fffffffe33d with value 0x611c10000000 // Incorrect
Checking stack location 0x7fffffffe33e with value 0x611c100000 // Incorrect
Checking stack location 0x7fffffffe33f with value 0x611c1000 // Incorrect
Checking stack location 0x7fffffffe340 with value 0x611c10 // Finally correct, only this is right

So since we go in steps of char(smallest quantum of increment), we will eventually hit the starting location(note carefully, starting, cause we only want to tag it) of all variables if not directly.

[ssrlive]

so, the searching logic must be changed.

[ssrlive]

so, why the gcc compiler can not run the right result?

[ssrlive]

maybe GCC forbidden read memory across stack frames?

[ganesh-k13]

@ssrlive please read 4th comment, I have explained the reason why gcc is failing but not clang

[mkirchner]

@ssrlive This may help as well.

[ssrlive]

Hi @ganesh-k13 , I'm debug on Win64, it' very strange that the bos address is smaller than stack var ints, it will cause the mark action will failed. how to do it?

[ssrlive]

And when I move uintptr_t *bos=(uintptr_t*)(&bos); to bottom, the code works fine. It's not a good practice.

[ssrlive]

Win64 exe always failed at this line.

gc/test/test_gc.c

Line 238 in be9f1e4

mu_assert(unmarked_alloc->tag == GC_TAG_NONE, "Unreferenced alloc should not be tagged");

because gc_mark_stack can always find out unmarked_alloc and mark it.

[ssrlive]

Failed in Win7 & VS2019 & 32bit.

[ssrlive]

maybe it is a better selection to use void *tos = __builtin_frame_address(1); with gcc.

I haven't found a similar implementation under Windows. Obviously _AddressOfReturnAddress is not the right choice.

[mkirchner]

Failed in Win7 & VS2019 & 32bit.

Given the code in the editor window, if your C compiler does not reshuffle the order of variable declarations, bos will end up at a lower stack address than five and hence the scan won't be able to find it. Have you tried declaring bos as the first variable in the function?

Also, uintptr_t* bos = (uintptr_t*)(&bos) seems self-referential. Is that valid C code and does it do what you expect it to?

[mkirchner]

maybe it is a better selection to use void *tos = __builtin_frame_address(1); with gcc.

Using __builtin_frame_address(n) with n > 0 is not recommended in the the GCC docs:

"Calling this function with a nonzero argument can have unpredictable effects, including crashing the calling program. As a result, calls that are considered unsafe are diagnosed when the -Wframe-address option is in effect. Such calls should only be made in debugging situations."

I haven't found a similar implementation under Windows. Obviously _AddressOfReturnAddress is not the right choice.

Not sure that I can follow why _AddressOfReturnAddress is not a good choice on Windows (we could wrap it into a #ifdef MSVC.... The docs actually look promising. However, keep in mind that you need to switch off frame pointer omission on 32bit architectures.

[ssrlive]

I means, if tos is point to parent stack frame, therefore we needn't mind the var order any more.

[ssrlive]

I have researched it again. I think I have find out the solve under windows. see below image.

We can use the _AddressOfReturnAddress as the bos, and use CONTEXT.Esp as the top of stack.
since GetThreadContext always return a lower CONTEXT.Esp value than ESP.

we can use CONTEXT.Esp as a beginning of searching memory and ending with the value of _AddressOfReturnAddress.

__declspec(noinline)
void func() {
    void* pvAddressOfReturnAddress = _AddressOfReturnAddress();
    uintptr_t *bos=(uintptr_t*)(&bos);

    CONTEXT *ctx = (CONTEXT *)calloc(1, sizeof(*ctx));
    ctx->ContextFlags = CONTEXT_ALL;
    GetThreadContext(GetCurrentThread(), ctx);

    printf_s("RSP %p\n", ctx->Rsp);
    printf_s("RBP %p\n", ctx->Rbp);

    printf_s("%p\n", pvAddressOfReturnAddress);
    printf_s("%p\n", *((void**)pvAddressOfReturnAddress));
    printf_s("%p\n", _ReturnAddress());

    free(ctx);
}

[mkirchner]

Hey @ssrlive , thanks for continuing to look into this! Given that this ticket is about GCC and @ganesh-k13 added GCC support in #22 , I am going to close this and fork off a separate MSVC discussion in #27 . Hope that's ok with you.

Fixed in #22.