Assertion failure when adding more than 2**30 elements to an unpacked array

[arnaud-lb]

Description

Found while testing #10149

The following code:

<?php

$start_index = -1; // Force unpacked array
array_fill($start_index, (2**30)+1, 0);

Resulted in this output:

php: /home/ubuntu/php-src/Zend/zend_hash.c:219: zend_hash_real_init_mixed_ex: Assertion `size >= 64 && ((size & 0x3f) == 0)' failed.

But I expected this output instead:

(no output)

gdb:

$ gdb --args sapi/cli/php -d memory_limit=-1 test.php
(gdb) r
Starting program: /home/ubuntu/php-src/sapi/cli/php -d memory_limit=-1 test.php
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
php: /home/ubuntu/php-src/Zend/zend_hash.c:219: zend_hash_real_init_mixed_ex: Assertion `size >= 64 && ((size & 0x3f) == 0)' failed.

Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (no_tid=0, signo=6, threadid=140737339844544) at ./nptl/pthread_kill.c:44
44	./nptl/pthread_kill.c: No such file or directory.
(gdb) bt
#0  __pthread_kill_implementation (no_tid=0, signo=6, threadid=140737339844544) at ./nptl/pthread_kill.c:44
#1  __pthread_kill_internal (signo=6, threadid=140737339844544) at ./nptl/pthread_kill.c:78
#2  __GI___pthread_kill (threadid=140737339844544, signo=signo@entry=6) at ./nptl/pthread_kill.c:89
#3  0x00007ffff72c5476 in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#4  0x00007ffff72ab7f3 in __GI_abort () at ./stdlib/abort.c:79
#5  0x00007ffff72ab71b in __assert_fail_base (fmt=0x7ffff7460150 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", assertion=0x5555565fca80 "size >= 64 && ((size & 0x3f) == 0)", file=0x5555565fc980 "/home/ubuntu/php-src/Zend/zend_hash.c", line=219, function=<optimized out>)
    at ./assert/assert.c:92
#6  0x00007ffff72bce96 in __GI___assert_fail (assertion=0x5555565fca80 "size >= 64 && ((size & 0x3f) == 0)", file=0x5555565fc980 "/home/ubuntu/php-src/Zend/zend_hash.c", line=219, function=0x5555565fd320 <__PRETTY_FUNCTION__.49> "zend_hash_real_init_mixed_ex")
    at ./assert/assert.c:101
#7  0x0000555555ea6f58 in zend_hash_real_init_mixed_ex (ht=0x7ffff3c4b3c0) at /home/ubuntu/php-src/Zend/zend_hash.c:219
#8  0x0000555555ea8101 in zend_hash_real_init_mixed (ht=0x7ffff3c4b3c0) at /home/ubuntu/php-src/Zend/zend_hash.c:335
#9  0x0000555555b13652 in zif_array_fill (execute_data=0x7ffff3c060a0, return_value=0x7fffffffa1b0) at /home/ubuntu/php-src/ext/standard/array.c:2604
#10 0x0000555555f09cec in ZEND_DO_ICALL_SPEC_RETVAL_UNUSED_HANDLER () at /home/ubuntu/php-src/Zend/zend_vm_execute.h:1235
#11 0x0000555556053dda in execute_ex (ex=0x7ffff3c06020) at /home/ubuntu/php-src/Zend/zend_vm_execute.h:55771
#12 0x0000555556066e18 in zend_execute (op_array=0x7ffff3c4f280, return_value=0x0) at /home/ubuntu/php-src/Zend/zend_vm_execute.h:60147
#13 0x0000555555e74a88 in zend_execute_scripts (type=8, retval=0x0, file_count=3) at /home/ubuntu/php-src/Zend/zend.c:1799
#14 0x0000555555d077e9 in php_execute_script (primary_file=0x7fffffffcdc0) at /home/ubuntu/php-src/main/main.c:2541
#15 0x0000555556240c1d in do_cli (argc=4, argv=0x604000000090) at /home/ubuntu/php-src/sapi/cli/php_cli.c:965
#16 0x0000555556242ed7 in main (argc=4, argv=0x604000000090) at /home/ubuntu/php-src/sapi/cli/php_cli.c:1367
(gdb) frame 7
#7  0x0000555555ea6f58 in zend_hash_real_init_mixed_ex (ht=0x7ffff3c4b3c0) at /home/ubuntu/php-src/Zend/zend_hash.c:219
219		HT_HASH_RESET(ht);
(gdb) list
214			data = emalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)));
215		}
216		ht->nTableMask = HT_SIZE_TO_MASK(nSize);
217		HT_SET_DATA_ADDR(ht, data);
218		HT_FLAGS(ht) = HASH_FLAG_STATIC_KEYS;
219		HT_HASH_RESET(ht);
220	}
221	
222	static zend_always_inline void zend_hash_real_init_ex(HashTable *ht, bool packed)
223	{
(gdb) p nSize
$1 = 2147483648
(gdb) p nSize == 0x80000000                // HT_MAX_SIZE
$2 = 1
(gdb) p ht->nTableMask
$3 = 0
(gdb) p ((uint32_t)(-((nSize) + (nSize)))) // HT_SIZE_TO_MASK
$4 = 0

nSize is an uint32_t. HT_MAX_SIZE is 0x80000000 (2**31), so nSize+nSize in HT_SIZE_TO_MASK overflows uint32_t, leading to ht->nTableMask == 0.

PHP Version

PHP 8.1

Operating System

No response

[nielsdos]

I believe we can fix this by decreasing the current value of HT_MAX_SIZE by 1 on 64-bit systems, i.e. 0x7FFFFFFF. It won't be a BC break because it never worked anyway and there will be no changes to internal structures/data types. I can make a PR for this soon if no one works on this yet?

[arnaud-lb]

Agreed. Sorry I was working on it already, I should have assigned myself.

I've chosen to use a HT_MAX_SIZE of 0x40000000, which is half the current value, and the effective maximum number of elements.

I think that the discrepancy between HT_MAX_SIZE and the actual maximum has been introduced when the load factor has been decreased from 1.0 to 0.5 in 34ed8e5.

[nielsdos]

No worries!

I now understand also understand why the size has to be halved for 64-bit.
I just don't get why 32-bit systems need the halving as well. AFAICT HT_HASH_SIZE also uses uint32_t's on 32-bit systems, and HT_MAX_SIZE is already small enough for 32-bit that it can't overflow the uint32_t on doubling?

[arnaud-lb]

On 32bit we can overflow size_t when computing the allocation size for the the hash table. The HT_HASH_SIZE macro has been added in 12abac8. This commit essentially avoids overflow checks in this computation by relying on HT_HASH_SIZE.

The hash table size was computed like this back then:

// packed
ht->nTableSize * sizeof(Bucket)
// non-packed
ht->nTableSize * (sizeof(Bucket) + sizeof(uint32_t))

With sizeof(Bucket)=24 on 32bits, ht->nTableSize can be at most SIZE_MAX/28: 0x09249249, which is twice as much as the value of HT_HASH_SIZE in 12abac8. If we take the max addressable space into account, this would be SSIZE_MAX/28: 0x04924924, nearly the value of HT_HASH_SIZE.

In #10242, halving HT_HASH_SIZE is actually too drastic on 32bit. I will update the PR.

[nielsdos]

Thanks for the clear explanation :)