funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

PHP compaction hell: Kdo neamortizuje, spláče nad O(n²)

30. 10. 2015

Staré hackerské přísloví praví: "Nehledej, jak budou věci fungovat, ale jak selžou." Degenerativní chování je vždycky zajímavější než popis běžného provozu.

Před nějakou dobou1 jsem aplikací této metodiky našel skulinu v připravovaném PHP 7, která dokáže rozpoutat perfektní bouři, která vyústí v katastrofické chování a možný DOS útok.

Všechno začalo, když jsem pročítal článek popisující novou implementaci hashtabulek (která je v porovnání s tou starou nádherná a v paměťové kompaktnosti předčí i standardní hashmapy z frameworku kolekcí Javy2 ) a narazil jsem na následující odstavec:

As you can see the first five arData elements have been used, but elements at position 2 (key 0) and 3 (key 'xyz') have been replaced with an IS_UNDEF tombstone, because they were unset. These elements will just remain wasted memory for now. However, once nNumUsed reaches nTableSize PHP will try compact the arData array, by dropping any UNDEF entries that have been added along the way. Only if all buckets really contain a value the arData will be reallocated to twice the size.

Hm, řekl jsem si, tohle na první pohled vypadá jako potenciální slabina, kdyby bylo možné spustit kompakci, která trvá čas lineárně úměrný velikosti tabulky, konstatním počtem operací.

Pak jsem dlouho civěl do céčkovských zdrojáků zend enginu, než jsem v té hromadě smetí našel funkci, která se stará o kompakci/zdvojnásobení hashtabulek (zend_hash_do_resize). Potom jsem na téměř nedokumentovaný kód zíral ještě chviličku, než mi došlo, že ona slabina nemůže nastat.

Proto jsem poslal pull request, který byl se slovy "nice catch, thanks, merged" přijat.

Abych to upřesnil: Onen patch nezanesl do PHP enginu chybu, ale jen ho upravil tak, aby fungoval podle představ jeho vývojářů. A shodou náhod jejich vize obsahovala jednu potenciálně závažnou slabinu.

S tímto zlepšovákem je ono chování jasně vidět. Vezměte si následující kus kódu:

$max = 2 ** 20;
$idxs = range(1, $max+1);
shuffle($idxs);
$arr = [];
foreach ($idxs as $idx) {
  $arr[$idx] = 1;
}

for ($i = 1; $i < 200000; $i++) {
  unset($arr[$i]);
  $arr[] = 1;
}

A pak tento fragment:

$max = 2 ** 20;
$idxs = range(1, $max-1); // tady je minus místo plusu
shuffle($idxs);
$arr = [];
foreach ($idxs as $idx) {
  $arr[$idx] = 1;
}

for ($i = 1; $i < 200000; $i++) {
  unset($arr[$i]);
  $arr[] = 1;
}

Oba jsou si až nepříjemně podobné, jen první běží o něco rychleji než ten druhý. A když říkám o něco rychleji, myslím tím o něco rychleji. První kus se na mém stroji vykoná za ±1 milisekundu, druhý bude trvat 96 vteřin. To je rozdíl mezi programem, který běží rychle a který neběží vůbec.

O co jde?

Vysvětlení je až nebezpečně prozaické. PHP7 s sebou přineslo veliké změny v reprezentacích interních struktur: zval je jiný, stejně jako implementace hash tabulek. Už nejde o divokou změť dynamicky alokovaných bucketů a spojových seznamů (první obrázek), ale o dvě kompaktní pole (druhý obrázek). Jedno se stará asociace mezi hashi klíčů a buckety a druhé pole bucketů udržuje pořadí v jakém byly hodnoty vloženy.

Tato změna přinesla spoustu dobrého, ale také jeden problém: Co se má stát, když je některá položka vymazána? Pokud je tabulka implementovaná pomocí spojových seznamů, je to jednoduché: Stačí položku vymazat a přesměrovat pointery. Ale když je pole nově vytesáno do souvislého kusu paměti, není to možné. PHP proto smazané elementy jen jako smazané označuje, ale v tabulce stále zabírají místo.

Když se hash tabulka naplní, implementace se nejdřív podívá, jestli některé sloty nejsou označeny jako smazané (udržuje proto několik čítačů). Pokud některý je, PHP provede kompakci a položky "sklepe". Pokud jsou všechny obsazené, zdvojí velikost hash tabulky (resp. oněch dvou polí) a rehashuje všechny klíče, jak je zvykem ve slušné společnosti.

A právě tady leží jádro pudla. Když druhý ukázkový kód odebere jeden element, označí jeden slot jako smazaný. Když pak vzápětí jeden element přidá, vynutí tak kompaci, protože počet elementů označených jako smazané je větší než nula a počet elementů, kterými byla tabulka naplněna byl zvolen těsně na hranici. Takhle to dělá pořád dokola a vynutí jednu kompaci na každou iteraci smyčky.

(Tady si dovolím malou odbočku, která ve výsledku nikam nepovede: Když jsem na tohle narazil někdy v prosinci, napsal jsem snippet testovacího kódu, který hlásil asi čtyřicetisedminásobné zpomalení. Později se však ukázalo, že vůbec netestoval to, co jsem si myslel, že testoval. PHP7 jako další optimalizaci zavedlo takzvané packed arrays. Jde o hashtabulky, které mají pouze numerické klíče z určitého spojitého intervalu, typicky z 0-N jako reálná pole reálných jazyků. V těch případech se struktura vůbec nechová jako hashtabulka a lookup probíhá přímo podle numerického klíče. Jak se zdá, tak packed arrays slabinou opakované kompakce netrpí. Z tohoto důvodu testovací programu provádí shuffle - rozbije tak packed array na obyčejnou hash tabulku.)

Rozdíl mezi jednou a devadesáti šesti tisíci milisekundami je značný, ale přestavuje jen teoretickou hrozbu, pokud její zlobu nikdo nedokáže zneužít k útoku. Dovedu si představit dva scénáře, kdy tohle může představovat problém: dávkové zpracování a websockety. Můžu mít například eshop, který je hip a moderní a celý napsaný v React.PHP a nákupní košík je v paměti PHP procesu. A protože chci, aby lidé nakupovali, není velikost košíku nijak omezena. To představuje ideální půdu pro útočníka, který může košík naplnit do přesně určené míry a pak opakovaně odebírat a přidávat jednu položku, a rozpoutat tak peklo kompakce.

Druhý případ na sebe přivolá nic netušící vývojář, který si do paměti načte určité nešťastně zvolené množství položek (jsme programátoři a proto zvolíme mocninu dvou, proč ne žejo?) a pak je bude zpracovávat a při této činnosti odebírat zpracované položky a přidávat nové.

Ok to by stačilo. Teď co s tím?

Řešení je jednoduché: amortizovat. Problém spočívá v tom, že lineární množství práce je možné spustit vykonáním konstantního množství kroků. Když zařídím, aby tuto práci spustilo jen lineární množství kroků, problém zcela zmizí.

Ze stejného důvodu se například velikost hash tabulky zdvojuje - lineární práce zdvojení je amortizování přes lineární počet přidání nových položek do tabulky. Jinými slovy musím přidat n položek, než bude třeba alokovat 2n paměti a přesunout oněch n položek. Amortizovaná cena každého vložení je alokace 2 slotů a jedno přesunutí do nové tabulky. I když jednou za čas jedna operace bude velice drahá, její cena se rozloží v úměrném množství levnějších operací.

Do PHP jsem poslal pull request s jednořádkovou opravou, která povolí kompakci jen pokud je smazaných víc jak 1/32 elementů. Tato změna způsobí, že v nejhorším případě musím provést n/32 kroků na to, abych vynutil kompakci, která udělá n kroků, a tedy v patologickém případě je cena jedné operace 32 - a i když to není malá konstanta, jde stále o konstantu. Hodnotu 32 jsem zvolil jako kompromis. Kdyby byla menší operace by měly těsnější garance, ale zároveň by prováděly kompakci méně často, protože by potřebovaly víc smazaných elementů, než by se do ní pustily. Tento patch zatím stále čeká na přijetí. Patch byl konečně začleněn poté, co k němu Martin Major přitáhl pozornost.

Dále k tématu:

Pozn:

  1. Bylo to už před pár měsíci. Tenhle článek jsem napsal už před nějakou dobou, ale dlouho mi ležel ladem na disku.
  2. Pro úplnost se sluší dodat, že v Javě je možné napsat vlastní specializované verze kolekcí, které jsou efektivnější než ty z PHP7, co se týká jak paměti tak rychlosti (viz tento článek a taky tento). Proti Javě hrají hlavně erased generika a nutnost dělat boxing primitivních typů. C# tento problém nemá (CLR specializuje pro hodnotové typy) a říká se o něm, že velké kolekce primitivních typů jsou až 10x rychlejší než jejich generické obdoby z Javy.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články