almost certainly the new algo, will poke at it.

Fix: https://github.com/ebernhardson/hiphop-php/commit/bde76850eb855a655c4b53659caf6f2e5903d70e

From the backtrace it appears that this happens when attempting to insert a value into the pattern cache when the pattern cache is full, causing an existing item to be evicted. The cache size is pretty small -- is it possible that the item being evicted is still referenced by another request which is being executed at the same time?

even if evicted i think the shared_ptr semantics will ensure nothing funny happens there. I could be improperly using the ConcurrentLRUCache though. Its the same data structure that backs APC but i could have easily gotten something wrong. will look around a bit.

You should be careful assigning the result of dereferencing a ConstAccessor to a non-const shared_ptr. That pointer is shared between threads now, so initTables() could be run more than once. prefix.reserve() doesn't change the size, so you have a race condition window open from the "prefix.size() == 0" check until the first prefix.push_back() call.

Maybe you could move the initTables() call to the constructor, and call it unconditionally, instead of deferring it, that way there would be no race condition. Then make "replacer" a const variable, and make translate() a const function, so that any other inappropriate shared writes will be flagged by the compiler.

I'm not sure how the memcmp() avoids reading past the end of "source". The inequality only seems to prevent it from reading past the end of "pat", and the lastpos check would only prevent overflow if all the patterns were the same size. There is the hash check, but the hash is only 16 bits so presumably collides all the time.

Speaking of hash collisions, I see you are using a 64-bit non-cryptographic hash as the cache key, which seems a bit dangerous. What if the cache holds trusted HTML for one module and untrusted user input for another? There is PHP_SHA1Init() etc., or you could use the whole array as the key and define custom hash and equality functions.

noticed the problem with initTables() when ori first noticed this problem, applied a similar fix[1] in my initial attempt to fix this which ori put into prod last a little over a week ago. I only moved the call and didn't follow up with the rest of your suggestions, I will now.

I'm pretty sure the first part of the conditional, pnr->pat.size() > source.size() - pos, prevents overrunning source as intended. if source.size() is 100 and pos is 96 we will skip the memcmp and go straight to continue for all patterns longer than 4 bytes.

The hashes are small as they are used to index into a table. It's almost always a hash of either a 2 or 3 byte prefix/suffix of the pattern (maximum is set by the shortest pattern length). In the case of the function with memcmp that is indexing into a 10 bit table, so on our larger pattern sets (~15k zh2hant) there is a good bit of collision. The size of the tables is a trade off between quick initialization with small pattern sets and efficient operation with larger ones (and memory usage). It would actually be nice to refactor so that those work on a bounded sliding scale based on the number of patterns but i haven't had the time.

Good point about not using murmur for the hash function. If we upgrade to a cryptographic hash i wonder if it will make the LRU less worthwhile. As is it saves ~75% of runtime on shorter strings with larger pattern sets. Most of that remaining runtime is the hashing time. I'm wonder if the LRU cache is truly worthwhile.

For the best efficiency this LRU isn't our best bet anyways, the hashing itself takes a significant portion of the runtime. The best efficiency would be found by caching the WuManberReplacement by a user definable string. We might be better off creating a custom extension (except, this was supposed to kill a custom extension...) the holds the WuManberReplacement ptr within a php object(or resource? probably object), and fetch/store the cached values directly in APC. If i understand APC correctly in HHVM in takes advantage of COW and just directly stores the variable representations. I'm not sure how exactly to go about that (although i'm sure can figure it out). More so though i'm not sure we really want to change from fss to yet another custom extension.

Ideas/thoughts?

[1] https://github.com/facebook/hhvm/pull/6071

In T109540#1591745, @EBernhardson wrote:

Good point about not using murmur for the hash function. If we upgrade to a cryptographic hash i wonder if it will make the LRU less worthwhile. As is it saves ~75% of runtime on shorter strings with larger pattern sets. Most of that remaining runtime is the hashing time. I'm wonder if the LRU cache is truly worthwhile.

Using a cryptographic hash is a simple but inefficient solution. The efficient way to do it is to use the whole array as the key, and to cache the murmur hash value in the key object, like what I did in LRUCacheKey. That way you only compute the hash once per insert/fetch. Using the same underlying storage for the key and value avoids copying. The additional overhead would then just be an equality check on fetch, consisting of a pair of string comparisons for each array element.

And as I type that, the words "avoids copying" are reverberating in my head...

You are just inserting String objects into the shared cache, without copying. If the string is dynamically constructed, not a string literal, then the underlying StringData will be allocated from the request-local allocator and it will be destroyed at the end of the request. So that is a bug and at least explains Ori's backtrace above.

I think the best solution for this is to copy. In theory you could save a few cycles for string literals and strings fetched from APC by doing something analogous to APCHandle::Create(), but it doesn't seem worth the effort when the replacement strings are just going to be copied into the destination string. You can use std::string or whatever.

For the best efficiency this LRU isn't our best bet anyways, the hashing itself takes a significant portion of the runtime. The best efficiency would be found by caching the WuManberReplacement by a user definable string. We might be better off creating a custom extension (except, this was supposed to kill a custom extension...) the holds the WuManberReplacement ptr within a php object(or resource? probably object), and fetch/store the cached values directly in APC. If i understand APC correctly in HHVM in takes advantage of COW and just directly stores the variable representations. I'm not sure how exactly to go about that (although i'm sure can figure it out). More so though i'm not sure we really want to change from fss to yet another custom extension.

I think this would be justified only if profiling clearly shows that hashing is an important user-visible performance issue.

Looks like tim was on the right track for the crasher. This script consistently segfaults hhvm on the 11th web request after a restart:

<?php
$alphabet = 'ﭐٱﭑٱﭒٻﭓٻﭔٻﭕٻﭖپ ﭗپﭘپﭙپﭚڀﭛڀﭜڀﭝڀ ﭞٺﭟٺﭠٺﭡٺﭢٿﭣٿﭤٿ ﭥٿﭦٹﭧٹﭨٹﭩٹﭪڤﭫڤ ﭬڤﭭڤﭮڦﭯڦﭰڦﭱڦﭲڄ ﭳڄﭴڄﭵڄﭶڃﭷڃﭸڃﭹڃ ﭺچﭻچﭼچﭽچﭾڇﭿڇﮀڇ ﮁڇﮂڍﮃڍﮄڌﮅڌﮆڎﮇڎ ﮈڈﮉڈﮊژﮋژﮌڑﮍڑﮎک ﮏکﮐک';

$map = array();
$alphaLen = strlen( $alphabet );
for( $i = 0; $i < 1001; ++$i ) {
        $len = mt_rand( 3, $alphaLen );
        $key = substr( str_shuffle( $alphabet ), 0, $len );
        $map[$key] = $key;
}
strtr( implode( '', array_keys( $map ) ), $map );
echo ".";

After switching from String to std::string this problem looks to be solved. I have made most of tim's suggested updates here: https://github.com/ebernhardson/hiphop-php/commit/dd8fe894be6f3a784c287ce7af4e39e39863e29c

This is still missing the LRU cache key handing adjustments, i'm pretty sure i follow what you are suggesting now after looking over LRUCacheKey I didn't have time to work that out tonight though.

This has been closed by I don't see any commit to the HHVM repository and just a version of HHVM in production (whitout the corresponding source, so I can't even backport whatever is in there).

@ori did I miss the change open? If not please submit it to git so that I can build a new package.

The relevant patch is still stalled at https://reviews.facebook.net/D44973

No issues reported there, its just taking time to do the back and forth dance once we figured out the last part of the problem.

just to follow up, this was merged to HHVM today.

And segfault in same place in strtr inside ReplacementArray is now with HHVM 3.10.0, see https://github.com/facebook/hhvm/issues/6384.

I am not sure whether this is exactly the same issue or just similar.

I advice against updating to HHVM 3.10.0 (caused us some downtime) until the issue is fixed.

It is the same issue, and jwatzman is pushing out a 3.10.1 soon.