Skip to content

[intl] Size sortWithSortKeys buffers based on array size #23504

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
iliaal wants to merge 1 commit into
base: master
Choose a base branch
from
+85 −18
Open

[intl] Size sortWithSortKeys buffers based on array size #23504

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 2 additions & 0 deletions NEWS
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,6 +7,8 @@ PHP NEWS
100-continue flow control). (Sjoerd Langkemper)

- Intl:
. Fixed Collator::sortWithSortKeys() allocating fixed 2MiB buffers
regardless of array size. (iliaal)
. Fixed a memory leak when iterating IntlBreakIterator::getPartsIterator()
results. (iliaal)
. Fixed a leak in Locale::getKeywords() when a keyword value cannot be
Expand Down
44 changes: 26 additions & 18 deletions ext/intl/collator/collator_sort.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -44,9 +44,8 @@ ZEND_EXTERN_MODULE_GLOBALS( intl )

static const size_t DEF_SORT_KEYS_BUF_SIZE = 1048576;
static const size_t DEF_SORT_KEYS_BUF_INCREMENT = 1048576;

static const size_t DEF_SORT_KEYS_INDX_BUF_SIZE = 1048576;
static const size_t DEF_SORT_KEYS_INDX_BUF_INCREMENT = 1048576;
static const size_t MIN_SORT_KEYS_BUF_SIZE = 4096;
static const size_t SORT_KEY_LENGTH_ESTIMATE = 32;

static const size_t DEF_UTF16_BUF_SIZE = 1024;

Expand Down Expand Up @@ -427,17 +426,17 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
zval* hashData = nullptr; /* currently processed item of input hash */

char* sortKeyBuf = nullptr; /* buffer to store sort keys */
uint32_t sortKeyBufSize = DEF_SORT_KEYS_BUF_SIZE; /* buffer size */
uint32_t sortKeyBufSize = 0; /* buffer size */
ptrdiff_t sortKeyBufOffset = 0; /* pos in buffer to store sort key */
uint32_t sortKeyLen = 0; /* the length of currently processing key */
uint32_t bufLeft = 0;
uint32_t bufIncrement = 0;

collator_sort_key_index_t* sortKeyIndxBuf = nullptr; /* buffer to store 'indexes' which will be passed to 'qsort' */
uint32_t sortKeyIndxBufSize = DEF_SORT_KEYS_INDX_BUF_SIZE;
uint32_t sortKeyIndxSize = sizeof( collator_sort_key_index_t );

uint32_t sortKeyCount = 0;
uint32_t numElements = 0;
uint32_t j = 0;

UChar* utf16_buf = nullptr; /* tmp buffer to hold current processing string in utf-16 */
Expand Down Expand Up @@ -472,9 +471,20 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
if( !hash || zend_hash_num_elements( hash ) == 0 )
RETURN_TRUE;

numElements = zend_hash_num_elements( hash );

if( numElements > DEF_SORT_KEYS_BUF_SIZE / SORT_KEY_LENGTH_ESTIMATE ) {
sortKeyBufSize = DEF_SORT_KEYS_BUF_SIZE;
} else {
sortKeyBufSize = numElements * SORT_KEY_LENGTH_ESTIMATE;
}
if( sortKeyBufSize < MIN_SORT_KEYS_BUF_SIZE ) {
sortKeyBufSize = MIN_SORT_KEYS_BUF_SIZE;
}

/* Create buffers */
sortKeyBuf = reinterpret_cast<char *>(ecalloc( sortKeyBufSize, sizeof( char ) ));
sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(ecalloc( sortKeyIndxBufSize, sizeof( uint8_t ) ));
sortKeyBuf = reinterpret_cast<char *>(ecalloc( sortKeyBufSize, sizeof( char ) ));
sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(ecalloc( numElements, sortKeyIndxSize ));
utf16_buf = eumalloc( utf16_buf_size );

/* Iterate through input hash and create a sort key for each value. */
Expand Down Expand Up @@ -524,7 +534,15 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
/* check for sortKeyBuf overflow, increasing its size of the buffer if needed */
if( sortKeyLen > bufLeft )
{
bufIncrement = ( sortKeyLen > DEF_SORT_KEYS_BUF_INCREMENT ) ? sortKeyLen : DEF_SORT_KEYS_BUF_INCREMENT;
bufIncrement = sortKeyBufSize;

if( bufIncrement > DEF_SORT_KEYS_BUF_INCREMENT ) {
bufIncrement = DEF_SORT_KEYS_BUF_INCREMENT;
}

if( bufIncrement < sortKeyLen ) {
bufIncrement = sortKeyLen;
}

sortKeyBufSize += bufIncrement;
bufLeft += bufIncrement;
Expand All @@ -534,16 +552,6 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
sortKeyLen = ucol_getSortKey( co->ucoll, utf16_buf, utf16_len, (uint8_t*)sortKeyBuf + sortKeyBufOffset, bufLeft );
}

/* check sortKeyIndxBuf overflow, increasing its size of the buffer if needed */
if( ( sortKeyCount + 1 ) * sortKeyIndxSize > sortKeyIndxBufSize )
{
bufIncrement = ( sortKeyIndxSize > DEF_SORT_KEYS_INDX_BUF_INCREMENT ) ? sortKeyIndxSize : DEF_SORT_KEYS_INDX_BUF_INCREMENT;

sortKeyIndxBufSize += bufIncrement;

sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(erealloc( sortKeyIndxBuf, sortKeyIndxBufSize ));
}

sortKeyIndxBuf[sortKeyCount].key = (char*)sortKeyBufOffset; /* remember just offset, cause address */
/* of 'sortKeyBuf' may be changed due to realloc. */
sortKeyIndxBuf[sortKeyCount].zstr = hashData;
Expand Down
57 changes: 57 additions & 0 deletions ext/intl/tests/collator_sort_with_sort_keys_buffer_size.phpt
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,57 @@
--TEST--
Collator::sortWithSortKeys() buffer allocation scales with array size
--EXTENSIONS--
intl
--FILE--
<?php
$c = new Collator('en_US');
$a = ['bb', 'aa', 'dd', 'cc'];
$c->sort($a);

$before = memory_get_peak_usage();
$b = ['bb', 'aa', 'cc', 'ab', 'ca', 'bc', 'ac', 'ba'];
$c->sortWithSortKeys($b);
$peakDelta = memory_get_peak_usage() - $before;

var_dump($a);
var_dump($b);
var_dump($peakDelta < 100000);

$long = str_repeat('a', 10000);
$d = [$long . 'b', $long . 'a'];
$c->sortWithSortKeys($d);
echo $d[0] === $long . 'a' ? "long-a\n" : "fail-a\n";
echo $d[1] === $long . 'b' ? "long-b\n" : "fail-b\n";
?>
--EXPECT--
array(4) {
[0]=>
string(2) "aa"
[1]=>
string(2) "bb"
[2]=>
string(2) "cc"
[3]=>
string(2) "dd"
}
array(8) {
[0]=>
string(2) "aa"
[1]=>
string(2) "ab"
[2]=>
string(2) "ac"
[3]=>
string(2) "ba"
[4]=>
string(2) "bb"
[5]=>
string(2) "bc"
[6]=>
string(2) "ca"
[7]=>
string(2) "cc"
}
bool(true)
long-a
long-b
Loading