arm32le: segfault in lookup_static() with musl libc

[nmeum]

Hello, I am a contributor to the Alpine Linux distribution (which uses musl libc). I am currently trying to improve our ChezScheme package. As part of this effort, I am trying to make the package available for more architectures (currently it is only supported on x86/x86_64). I started working on a port for armv6. While working on this, I ran into the following segfault during the build process on armv6:

Program received signal SIGSEGV, Segmentation fault.
0x4002d22c in lookup_static (s=0x4005d584 "(cs)lookup_foreign_entry") at foreign.c:101
101	    if (strcmp(s, (char *)&BVIT(Scar(Scar(p)),0)) == 0)
(gdb) bt
#0  lookup_static (s=0x4005d584 "(cs)lookup_foreign_entry") at foreign.c:101
#1  lookup (s=0x4005d584 "(cs)lookup_foreign_entry") at foreign.c:141
#2  0x4002d39c in Sforeign_symbol (s=0x4005d584 "(cs)lookup_foreign_entry",
    v=0x4002d304 <lookup_foreign_entry>) at foreign.c:170
#3  0x4002d6a0 in S_foreign_init () at foreign.c:323
#4  0x40035fe8 in main_init () at scheme.c:77
#5  Sbuild_heap (
    kernel=kernel@entry=0x3ffff951 "/var/tmp/abuild.XXXXEdCBcm/tmp/src/csv9.5.8/arm32le/bin/arm32le/scheme", custom_init=custom_init@entry=0x0) at scheme.c:1121
#6  0x40008168 in main (argc=1, argv=0x3ffff7b4) at main.c:292

To me, it looks like it segfaults when iterating through the S_G.foreign_static vector in lookup_static for the (cs)lookup_foreign_entry symbol:

ChezScheme/c/foreign.c

Lines 100 to 102 in e47faca

	for (p = Svector_ref(S_G.foreign_static, b); p != Snil; p = Scdr(p))
	if (strcmp(s, (char *)&BVIT(Scar(Scar(p)),0)) == 0)
	return Scdr(Scar(p));

Since lookup_static is called from S_foreign_init here I would have assumed the vector to be only filled with Snil but for some reason Scar(p) ends up creating a pointer which causes a segmentation fault on dereference. Since I am not an expert on the ChezScheme code base I am presently not sure what is causing this and was hoping someone with more advanced knowledge of the ChezScheme code might have an idea what could be causing the segfault (it is likely musl-related since I assume that arm32le is well tested in conjunction with glibc).

The full build log: alpine-edge-chez-scheme-armhf.txt

---

PS: I also had to slightly patch the code to address #527 and #621.

[jltaylor-us]

it is likely musl-related since I assume that arm32le is well tested in conjunction with glibc

That's probably not the best assumption... arm32le is not tested in GitHub automation, and the last work that I know for sure was done on it was for a project that is now defunct. I'm sure it was working and tested at some point, but bit rot may have set in.

Hopefully someone more familiar with that part of Chez will be able to take a look.

[cjfrisz]

Unfortunately, arm32le isn't supported as well as some of the other machine types, so currently it gets updated when someone raises an issue (like this). I haven't used Alpine Linux, and I'm not familiar with musl libc, but I will get out my RasPi4 and try to reproduce your issue.

[nmeum]

I debugged this a bit further and one problem seems to be the implementation of the hash function symhash:

ChezScheme/c/foreign.c

Lines 88 to 94 in e47faca

	static iptr symhash(const char *s) {
	iptr n, h;
	h = n = strlen(s);
	while (n--) h = h * multiplier + *s++;
	return (h & 0x7fffffff) % buckets;
	}

On arm32le, the iptr type is an alias for int (i.e. a 32-bit signed integer). The while loop body can easily cause this integer to overflow. Keep in mind that signed integer overflow is undefined behavior, but on my arm32le system it causes symhash to return a negative value for (cs)lookup_foreign_entry. Since this value is then used to index the S_G.foreign_static vector via Svector_ref this seems to be the cause of the segmentation fault.

I am not entirely sure why the symhash function returns a signed integer type in the first place but if I simply change the type from iptr to uptr then ChezScheme compiles fine on arm32le here.

Breakpoint 1, symhash (s=s@entry=0x4005d584 "(cs)lookup_foreign_entry") at foreign.c:91
91        h = n = strlen(s);
(gdb) n
92        while (n--) h = h * multiplier + *s++;
(gdb) n
93        return (h & 0x7fffffff) % buckets;
(gdb) p h
$1 = -426584701
(gdb) finish
Run till exit from #0  symhash (s=0x4005d59c "", s@entry=0x4005d584 "(cs)lookup_foreign_entry")
    at foreign.c:93
lookup_static (s=0x4005d584 "(cs)lookup_foreign_entry") at foreign.c:100
100       for (p = Svector_ref(S_G.foreign_static, b); p != Snil; p = Scdr(p))
Value returned is $2 = -336
(gdb) p b
-336

[nmeum]

As it turns out, the problem is that GCC optimizes out the h & 0x7fffffff on ARMv6:

0002d09c <symhash>:
   2d09c:       e92d4010        push    {r4, lr}
   2d0a0:       e1a04000        mov     r4, r0
   2d0a4:       ebff6bc8        bl      7fcc <strlen@plt>
   2d0a8:       e0842000        add     r2, r4, r0
   2d0ac:       e1520004        cmp     r2, r4
   2d0b0:       1a000003        bne     2d0c4 <symhash+0x28>
   2d0b4:       e59f1018        ldr     r1, [pc, #24]   ; 2d0d4 <symhash+0x38>
   2d0b8:       eb00aeee        bl      58c78 <__aeabi_idivmod>
   2d0bc:       e1a00001        mov     r0, r1
   2d0c0:       e8bd8010        pop     {r4, pc}
   2d0c4:       e4d41001        ldrb    r1, [r4], #1
   2d0c8:       e0803080        add     r3, r0, r0, lsl #1
   2d0cc:       e0810003        add     r0, r1, r3
   2d0d0:       eafffff5        b       2d0ac <symhash+0x10>
   2d0d4:       000001c9        andeq   r0, r0, r9, asr #3

This also explains the return value of the symhash function in the GDB session from my previous comment (-426584701 % 457 == -336).

My hypothesis is that GCC perform this optimization because char is unsigned on ARMv6 and hence arithmetic operations are only performed on the local variable h with unsigned types. Additionally, since signed integer overflow is undefined behavior GCC assumes it doesn't take place, hence the sign bit should always be 0 and GCC removes the h & 0x7fffffff. This hypothesis seems to be confirmed by the fact that GCC does include the h & 0x7fffffff if *s is explicitly casted to signed char:

--- a/c/foreign.c
+++ b/c/foreign.c
@@ -89,7 +89,7 @@ static iptr symhash(const char *s) {
   iptr n, h;

   h = n = strlen(s);
-  while (n--) h = h * multiplier + *s++;
+  while (n--) h = h * multiplier + (signed char)*s++;
   return (h & 0x7fffffff) % buckets;
 }

This is compiled as follows:

0002d09c <symhash>:
   2d09c:       e92d4010        push    {r4, lr}
   2d0a0:       e1a04000        mov     r4, r0
   2d0a4:       ebff6bc8        bl      7fcc <strlen@plt>
   2d0a8:       e0842000        add     r2, r4, r0
   2d0ac:       e1540002        cmp     r4, r2
   2d0b0:       1a000004        bne     2d0c8 <symhash+0x2c>
   2d0b4:       e59f101c        ldr     r1, [pc, #28]   ; 2d0d8 <symhash+0x3c>
   2d0b8:       e3c00102        bic     r0, r0, #-2147483648    ; 0x80000000
   2d0bc:       eb00aeef        bl      58c80 <__aeabi_idivmod>
   2d0c0:       e1a00001        mov     r0, r1
   2d0c4:       e8bd8010        pop     {r4, pc}
   2d0c8:       e0d410d1        ldrsb   r1, [r4], #1
   2d0cc:       e0803080        add     r3, r0, r0, lsl #1
   2d0d0:       e0810003        add     r0, r1, r3
   2d0d4:       eafffff4        b       2d0ac <symhash+0x10>
   2d0d8:       000001c9        andeq   r0, r0, r9, asr #3

In this disassembly h & 0x7fffffff is performed using the bic instruction. However, I think explicitly casting to signed char is not the proper fix as it still relies on undefined behavior (signed integer overflow) and may break again in future GCC versions. As such, I modified symhash in a way that it operates on unsigned types in #625.

[cjfrisz]

This is a really nice rundown of the issue. Thank you for figuring this out!

I had a couple of false starts installing Alpine Linux on my Pi, but I put some time into it--unfortunately to no avail. It looks like the armhf version doesn't work on the RasPi 4B, which is the only one I have on hand. After installing the aarch64 version, I discovered that musl libc doesn't support multilib in the same way glibc does, so it appears I'm out of luck reproducing your issue and validating your fix for myself.

That said, I will install a more up-to-date glib-based distro on my Pi, and if the changes work, then I'm comfortable going ahead with #625.

[nmeum]

Any updates on this? I personally just reproduced this using qemu-arm. I also think that the changes proposed in #625 make sense for non-ARM platforms as signed integer overflow is always undefined behavior in C.

[cjfrisz]

I resolved the new entries with in the LOG, and once the mats pass, I'll merge #625 today.