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 — k47

Staré hac­ker­ské pří­sloví praví: „Ne­hle­dej, jak budou věci fun­go­vat, ale jak selžou.“ De­ge­ne­ra­tivní cho­vání je vždycky za­jí­ma­vější než popis běž­ného pro­vozu.

Před ně­ja­kou dobou1 jsem apli­kací této me­to­diky našel sku­linu v při­pra­vo­va­ném PHP 7, která dokáže roz­pou­tat per­fektní bouři, která vyústí v ka­ta­stro­fické cho­vání a možný DOS útok.

Všechno začalo, když jsem pro­čí­tal článek po­pi­su­jící novou im­ple­men­taci ha­sh­ta­bu­lek (která je v po­rov­nání s tou starou nád­herná a v pa­mě­ťové kom­pakt­nosti předčí i stan­dardní ha­shmapy z fra­meworku ko­lekcí Javy2) a na­ra­zil jsem na ná­sle­du­jící od­sta­vec:

As you can see the first five arData ele­ments have been used, but ele­ments at po­si­tion 2 (key 0) and 3 (key 'xyz') have been repla­ced with an IS_UNDEF tomb­stone, be­cause they were unset. These ele­ments will just remain wasted memory for now. However, once nNu­mUsed re­a­ches nTable­Size PHP will try com­pact the arData array, by drop­ping any UNDEF en­t­ries that have been added along the way. Only if all buckets really con­tain a value the arData will be re­allo­ca­ted to twice the size.

Hm, řekl jsem si, tohle na první pohled vypadá jako po­ten­ci­ální sla­bina, kdyby bylo možné spus­tit kom­pakci, která trvá čas li­ne­árně úměrný ve­li­kosti ta­bulky, kon­stat­ním počtem ope­rací.

Pak jsem dlouho civěl do céč­kov­ských zdro­jáků zend enginu, než jsem v té hro­madě smetí našel funkci, která se stará o kom­pakci/zdvoj­ná­so­bení ha­sh­ta­bu­lek (zend_hash_do_resize). Potom jsem na téměř ne­do­ku­men­to­vaný kód zíral ještě chvi­ličku, než mi došlo, že ona sla­bina nemůže nastat.

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

Abych to upřes­nil: Onen patch ne­za­nesl do PHP enginu chybu, ale jen ho upra­vil tak, aby fun­go­val podle před­stav jeho vý­vo­jářů. A shodou náhod jejich vize ob­sa­ho­vala jednu po­ten­ci­álně zá­važ­nou sla­binu.

S tímto zlep­šo­vá­kem je ono cho­vání jasně vidět. Vez­měte si ná­sle­du­jí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 frag­ment:

$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ž ne­pří­jemně po­dobné, jen první běží o něco rych­leji než ten druhý. A když říkám o něco rych­leji, myslím tím o něco rych­leji. První kus se na mém stroji vykoná za ±1 mi­li­sekundu, druhý bude trvat 96 vteřin. To je rozdíl mezi pro­gra­mem, který běží rychle a který neběží vůbec.

O co jde?

Vy­svět­lení je až ne­bez­pečně pro­za­ické. PHP7 s sebou při­neslo veliké změny v re­pre­zen­ta­cích in­ter­ních struk­tur: zval je jiný, stejně jako im­ple­men­tace hash ta­bu­lek. Už nejde o di­vo­kou změť dy­na­micky alo­ko­va­ných bucketů a spo­jo­vých se­znamů (první ob­rá­zek), ale o dvě kom­paktní pole (druhý ob­rá­zek). Jedno se stará aso­ci­ace mezi hashi klíčů a buckety a druhé pole bucketů udr­žuje pořadí v jakém byly hod­noty vlo­ženy.

Tato změna při­nesla spoustu dob­rého, ale také jeden pro­blém: Co se má stát, když je ně­která po­ložka vy­ma­zána? Pokud je ta­bulka im­ple­men­to­vaná pomocí spo­jo­vých se­znamů, je to jed­no­du­ché: Stačí po­ložku vy­ma­zat a pře­smě­ro­vat poin­tery. Ale když je pole nově vy­te­sáno do sou­vis­lého kusu paměti, není to možné. PHP proto sma­zané ele­menty jen jako sma­zané ozna­čuje, ale v ta­bulce stále za­bí­rají místo.

Když se hash ta­bulka naplní, im­ple­men­tace se nejdřív podívá, jestli ně­které sloty nejsou ozna­čeny jako sma­zané (udr­žuje proto ně­ko­lik čítačů). Pokud ně­který je, PHP pro­vede kom­pakci a po­ložky „sklepe“. Pokud jsou všechny ob­sa­zené, zdvojí ve­li­kost hash ta­bulky (resp. oněch dvou polí) a re­ha­shuje všechny klíče, jak je zvykem ve slušné spo­leč­nosti.

A právě tady leží jádro pudla. Když druhý ukáz­kový kód ode­bere jeden ele­ment, označí jeden slot jako sma­zaný. Když pak vzá­pětí jeden ele­ment přidá, vynutí tak kom­paci, pro­tože počet ele­mentů ozna­če­ných jako sma­zané je větší než nula a počet ele­mentů, kte­rými byla ta­bulka na­pl­něna byl zvolen těsně na hra­nici. Takhle to dělá pořád dokola a vynutí jednu kom­paci na každou ite­raci smyčky.

(Tady si do­vo­lím malou od­bočku, která ve vý­sledku nikam ne­po­vede: Když jsem na tohle na­ra­zil někdy v pro­sinci, napsal jsem snip­pet tes­to­va­cího kódu, který hlásil asi čty­ři­ce­ti­sed­mi­ná­sobné zpo­ma­lení. Poz­ději se však uká­zalo, že vůbec ne­tes­to­val to, co jsem si myslel, že tes­to­val. PHP7 jako další op­ti­ma­li­zaci za­vedlo tak­zvané packed arrays. Jde o ha­sh­ta­bulky, které mají pouze nu­me­rické klíče z ur­či­tého spo­ji­tého in­ter­valu, ty­picky z 0-N jako reálná pole re­ál­ných jazyků. V těch pří­pa­dech se struk­tura vůbec ne­chová jako ha­sh­ta­bulka a lookup pro­bíhá přímo podle nu­me­ric­kého klíče. Jak se zdá, tak packed arrays sla­bi­nou opa­ko­vané kom­pakce netrpí. Z tohoto důvodu tes­to­vací pro­gramu pro­vádí shuffle – roz­bije tak packed array na oby­čej­nou hash ta­bulku.)

Rozdíl mezi jednou a de­va­de­sáti šesti tisíci mi­li­sekun­dami je značný, ale pře­sta­vuje jen te­o­re­tic­kou hrozbu, pokud její zlobu nikdo ne­do­káže zne­u­žít k útoku. Dovedu si před­sta­vit dva scé­náře, kdy tohle může před­sta­vo­vat pro­blém: dáv­kové zpra­co­vání a web­sockety. Můžu mít na­pří­klad eshop, který je hip a mo­derní a celý na­psaný v React.PHP a ná­kupní košík je v paměti PHP pro­cesu. A pro­tože chci, aby lidé na­ku­po­vali, není ve­li­kost košíku nijak ome­zena. To před­sta­vuje ide­ální půdu pro útoč­níka, který může košík na­pl­nit do přesně určené míry a pak opa­ko­vaně ode­bí­rat a při­dá­vat jednu po­ložku, a roz­pou­tat tak peklo kom­pakce.

Druhý případ na sebe při­volá nic ne­tu­šící vý­vo­jář, který si do paměti načte určité ne­šťastně zvo­lené množ­ství po­lo­žek (jsme pro­gra­má­toři a proto zvo­líme moc­ninu dvou, proč ne žejo?) a pak je bude zpra­co­vá­vat a při této čin­nosti ode­bí­rat zpra­co­vané po­ložky a při­dá­vat nové.

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

Řešení je jed­no­du­ché: amor­ti­zo­vat. Pro­blém spo­čívá v tom, že li­ne­ární množ­ství práce je možné spus­tit vy­ko­ná­ním kon­stant­ního množ­ství kroků. Když za­ří­dím, aby tuto práci spus­tilo jen li­ne­ární množ­ství kroků, pro­blém zcela zmizí.

Ze stej­ného důvodu se na­pří­klad ve­li­kost hash ta­bulky zdvo­juje – li­ne­ární práce zdvo­jení je amor­ti­zo­vání přes li­ne­ární počet při­dání nových po­lo­žek do ta­bulky. Jinými slovy musím přidat n po­lo­žek, než bude třeba alo­ko­vat 2n paměti a pře­su­nout oněch n po­lo­žek. Amor­ti­zo­vaná cena kaž­dého vlo­žení je alo­kace 2 slotů a jedno pře­su­nutí do nové ta­bulky. I když jednou za čas jedna ope­race bude velice drahá, její cena se roz­loží v úměr­ném množ­ství lev­něj­ších ope­rací.

Do PHP jsem poslal pull request s jed­no­řád­ko­vou opra­vou, která povolí kom­pakci jen pokud je sma­za­ných víc jak 1/32 ele­mentů. Tato změna způ­sobí, že v nej­hor­ším pří­padě musím pro­vést n/32 kroků na to, abych vy­nu­til kom­pakci, která udělá n kroků, a tedy v pa­to­lo­gic­kém pří­padě je cena jedné ope­race 32 – a i když to není malá kon­stanta, jde stále o kon­stantu. Hod­notu 32 jsem zvolil jako kom­pro­mis. Kdyby byla menší ope­race by měly těs­nější ga­rance, ale zá­ro­veň by pro­vá­děly kom­pakci méně často, pro­tože by po­tře­bo­valy víc sma­za­ných ele­mentů, než by se do ní pus­tily. Tento patch zatím stále čeká na při­jetí. Patch byl ko­nečně za­čle­něn poté, co k němu Martin Major při­táhl po­zor­nost.


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ě­ja­kou dobou, ale dlouho mi ležel ladem na disku.
  2. Pro úpl­nost se sluší dodat, že v Javě je možné napsat vlastní spe­ci­a­li­zo­vané verze ko­lekcí, které jsou efek­tiv­nější než ty z PHP7, co se týká jak paměti tak rych­losti (viz tento článektaky tento). Proti Javě hrají hlavně erased ge­ne­rika a nut­nost dělat boxing pri­mi­tiv­ních typů. C# tento pro­blém nemá (CLR spe­ci­a­li­zuje pro hod­no­tové typy) a říká se o něm, že velké ko­lekce pri­mi­tiv­ních typů jsou až 10x rych­lejší než jejich ge­ne­rické obdoby z Javy.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články