Conditional jump or move depends on uninitialised value(s)

[NathanFreeman]

Description

The following code:

valgrind --track-origins=yes php run-tests.php ext/dom/tests/canonicalization.phpt

Resulted in this output:

==13849== Conditional jump or move depends on uninitialised value(s)
==13849==    at 0x4070622: ???
==13849==    by 0x7358017: ???
==13849==    by 0x7358017: ???
==13849==    by 0x7358784: ???
==13849==    by 0x6ED2B9F: ???
==13849==    by 0x7358017: ???
==13849==  Uninitialised value was created by a stack allocation
==13849==    at 0x86D650: zend_delayed_compile_dim (zend_compile.c:2743)
==13849==

But I expected this output instead:

without warning

PHP Version

PHP 8.0+

Operating System

CentOS Linux release 7.9.2009 (Core)

[cmb69]

I can reproduce with a release build calling valgrind --track-origins=yes php run-tests.php -m ext/dom/tests/canonicalization.phpt (note the additional -m argument to run-tests.php). I cannot reproduce with a debug build, though.

[NathanFreeman]

I can reproduce it with PHP-8.0 branch without debug build.

[nielsdos]

I confirm this happens on 8.1+ with Valgrind.
This is a very cool bug which randomly goes away and appears again depending on what kind of debugging code I add.
Moreover, this bug only triggers on GCC with -O2, not on other optimisation levels and not on Clang.
Root cause: It's an interesting register corruption with a Valgrind replacement function.
TLDR: Proposed patch below.

Here's what I did to come to this conclusion:

To debug this case I used the builtin gdb support of Valgrind (--vgdb-full --vgdb-error=0).

Upon running Valgrind with the default checker I get a bunch of these:

==1756107== Invalid read of size 8
==1756107==  Address 0x70fdfb0 is 0 bytes after a block of size 32 alloc'd

When I add a printf("ret->len: %zu\n", ret->len); to the happy path of zend_interned_string_ht_lookup in zend_new_interned_string_permanent I get a crash at the read of ret->len:

==1757764==  Address 0x70d9a88 is 8 bytes after a block of size 32 alloc'd

So ret is pointing after the string, we can verify this by inspecting both str and ret:

(gdb) p ret
$1 = (zend_string *) 0x70d9a78
(gdb) p str
$2 = (zend_string *) 0x717a150
(gdb) p *ret
$3 = {gc = {refcount = 49, u = {type_info = 0}}, h = 0, len = 0, val = ""}
(gdb) p *str
$4 = {gc = {refcount = 2, u = {type_info = 150}}, h = 9223372036854953430, len = 1, val = "1"}
(gdb) p *(zend_string*)(0x70d9a78-24)
$5 = {gc = {refcount = 1, u = {type_info = 470}}, h = 9223372036854953430, len = 1, val = "1"}

We can see that ret should've been 0x70d9a78-24 instead of 0x70d9a78.
Also interesting to note is that I can trigger the bug with the none checker too if I add that printf!
My guess is zend_interned_string_ht_lookup is likely returning garbage somehow.

In zend_interned_string_ht_lookup, changing if (((p->h == h) && zend_string_equal_content(p->key, str))) { to if (((p->h == h) /*&& zend_string_equal_content(p->key, str)*/)) { magically "fixes" the crash (ofc it's an incorrect change but I'm doing trial and error).
So the problem must be in zend_string_equal_content? Let's see...

static zend_always_inline bool zend_string_equal_content(zend_string *s1, zend_string *s2)
{
	return ZSTR_LEN(s1) == ZSTR_LEN(s2) && zend_string_equal_val(s1, s2);
}

All it does is comparing the length and calling zend_string_equal_val. zend_string_equal_val contains inline assembly on my platform, and the code in zend_string.c does mention something about a Valgrind false positive...

/* Even if we don't build with valgrind support, include the symbol so that valgrind available
 * only at runtime will not result in false positives. */
#ifndef I_REPLACE_SONAME_FNNAME_ZU
# define I_REPLACE_SONAME_FNNAME_ZU(soname, fnname) _vgr00000ZU_ ## soname ## _ ## fnname
#endif

ZEND_API bool ZEND_FASTCALL I_REPLACE_SONAME_FNNAME_ZU(NONE,zend_string_equal_val)(zend_string *s1, zend_string *s2)
{
	return !memcmp(ZSTR_VAL(s1), ZSTR_VAL(s2), ZSTR_LEN(s1));
}

I'll call this the "Valgrind replacement function" and I ignore this for now.
I changed the non-replacement function to a simple for-loop comparing the characters and undoing the earlier change in zend_interned_string_ht_lookup. I also added zend_always_inline to zend_string_equal_val.
The crash is gone, but upon changing zend_always_inline to zend_never_inline the crash reappears.
So somehow calling zend_string_equal_val from zend_interned_string_ht_lookup breaks the code, except when it's inlined???

I decided to place a breakpoint on zend_string_equal_content in zend_interned_string_ht_lookup.
I also used gdb's layout asm command.

Upon hitting the breakpoint I checked s1 and s2, and they pointed to valid strings: s1=0x4052f80, s2=0x407fcb0
s1 is stored in rdi and s2 is stored in rbx.
I proceeded to step through the instructions.
The rbx and rdi register remained the same just before the call to zend_string_equal_content.
Right after the call to zend_string_equal_val I noticed that rbx (s2) is still correctly 0x407fcb0, but rdi (s1) is now 0x4052f98 instead of 0x4052f80 (0x18 bytes higher)!
A couple of instructions later, rdi is the value that's returned from this function!
So is zend_string_equal_content somehow corrupting rdi? (Note: that function's body is still the simple for loop I wrote about earlier).

I decided to try again but now step into zend_string_equal_content as well. zend_string_equal_content looks like this:

<vgr00000ZU_NONE_zend_string_equal_val>		sub $0x8, %rsp
<vgr00000ZU_NONE_zend_string_equal_val+4>	mov 0x10(%rdi), %rdx
<vgr00000ZU_NONE_zend_string_equal_val+8>	add $0x18, %rsi
<vgr00000ZU_NONE_zend_string_equal_val+12>	add $0x18, %rdi
<vgr00000ZU_NONE_zend_string_equal_val+16>	call 0x308740 <memcmp@plt>
<vgr00000ZU_NONE_zend_string_equal_val+21>	test %eax, %eax
<vgr00000ZU_NONE_zend_string_equal_val+23>	sete %al
<vgr00000ZU_NONE_zend_string_equal_val+26>	add $0x8, %rsp
<vgr00000ZU_NONE_zend_string_equal_val+30>	ret

Oh, it's actually the Valgrind replacement function that's called!
The add $0x18, %rdi instruction indeed modifies rdi, but according to the ABI, rdi is a scratch register, therefore it may be overwritten without saving it first.
However, at the call site (this is zend_interned_string_ht_lookup), rdi is assumed to be unmodified. We know this because of the move to rax as we described earlier.
So what I guess is happening here is that the compiler sees that the non-replacement zend_string_equal_val does not use rdi, so that the caller zend_interned_string_ht_lookup assumes rdi is not modified.
It does not know that Valgrind will use the Valgrind replacement function.

Patch:

The first thing I tried was removing the Valgrind replacement function, and that worked. However, the commit that introduced it said that it prevents false positives for Valgrind.
So I propose this PoC patch instead, which solves this bug on my system:

diff --git a/Zend/zend_string.c b/Zend/zend_string.c
index 8e6a16c64a..9900a4aef6 100644
--- a/Zend/zend_string.c
+++ b/Zend/zend_string.c
@@ -374,7 +374,16 @@ ZEND_API void zend_interned_strings_switch_storage(bool request)
 
 ZEND_API bool ZEND_FASTCALL I_REPLACE_SONAME_FNNAME_ZU(NONE,zend_string_equal_val)(zend_string *s1, zend_string *s2)
 {
-       return !memcmp(ZSTR_VAL(s1), ZSTR_VAL(s2), ZSTR_LEN(s1));
+#if defined(__GNUC__) && defined(__x86_64__)
+       asm volatile("pushq %r8");
+#endif
+       bool return_value = !memcmp(ZSTR_VAL(s1), ZSTR_VAL(s2), ZSTR_LEN(s1));
+       /* See issue https://github.com/php/php-src/issues/9068 */
+#if defined(__GNUC__) && defined(__x86_64__)
+       asm volatile("" : "=D" (s1) : "0" (s1));
+       asm volatile("popq %r8");
+#endif
+       return return_value;
 }
 
 #if defined(__GNUC__) && defined(__i386__)

I verified the generated assembly code and it now restores rdi to the initial value.
EDIT: On my laptop I also had to store and restore register r8.
This patch works for me. Could somebody else please test this patch as well? If it works I can maybe create a PR for this. Thanks.
The patch is a bit dirty, so a more proper solution might be to have zend_string_equal_val in a different file than zend_string.c such that the compiler cannot make the assumptions about the registers, but that could then again lead to less optimal codegen...

EDIT 2: The cleaner option I just realized is to use __attribute__((no_caller_saved_registers)) together with the target attribute "general-regs-only" just for that function only. This will automatically store and restore the registers whilst only affecting the replacement function. It's also more robust against breakage introduced by different codegen.

[arnaud-lb]

Nice writeup :)

I'm not able to reproduce the issue. What gcc and valgrind versions do you have?

__attribute__((no_caller_saved_registers)) seems like a good solution indeed

[nielsdos]

Nice writeup :)

Thanks :)

I'm not able to reproduce the issue. What gcc and valgrind versions do you have?

GCC 12.2.0, Valgrind 3.19.0, Linux 6.1.3
Configured using just: ./configure --enable-dom. You can't repro it on debug builds.

__attribute__((no_caller_saved_registers)) seems like a good solution indeed

That would've been the best one. Sadly, it's only available on GCC >= 7.0 or Clang >= 5.0. So AFAIK we can't really use it because it would require raising / setting a minimum compiler version. Furthermore, it's also unsupported on ICC. That's why I opted for the inline-assembly approach in my PR.