Mit ad vissza az Object.GetHashCode()?

Az Object.GetHashCode() metódust tévedések sora öleli körül. Van két állítás, amelyben viszonylag sokan hisznek:

  • Az Object osztály GetHashCode() implementációja a referenciából (mint pointerből) származtatja az értéket.
  • GetHashCode() által visszaadott érték egyértelműen azonosítja a példányt.

Ha az ember nem gondol mélyebben bele, akkor a két állítás elfogadhatónak tűnik. Ami érdekes, hogy ez a rész még a CLR via C# könyvben is rosszul szerepel (2. és 3. kiadás, 147-148. oldal). Mivel 2007-ben ezzel a könyvvel kezdtem el tanulni a .NET-et, és meghatározta a témához való hozzáállásomat, számomra most szimbolikus jelentőséggel bír javítani a tartalmát. A könyv a hash kód egyediséget állítja, ami nem igaz.

Referencia mint hash kód

Ez a megoldás azért tűnik jónak, mivel egy memóriacímen egyszerre csak egy példány lehet jelen. A .NET memóriakezelője azonban rendelkezik egy tulajdonsággal, ami alkalmatlanná teszi a referenciát (mint pointert) arra, hogy hash kódnak használjuk: egy-egy szemétgyűjtés után hajlamos átmozgatni az objektumokat a memóriában, emiatt a referencia (mint pointer) értéke megváltozik. A gyakorlatban ez azt jelentené, hogy egy garbage collection lefutása után esetleg nem találnánk meg az objektumunkat mondjuk egy Dictionary-ben.

GetHashCode() mint egyedi azonosító

Ez hasonló kérdés, mint hogy miért nem lehet minden embernek egyedi születésnapja? Azért, mert 365 (366) nap van egy évben, de több, mint 365 ember él a földön. A GetHashCode() egy 32 bites értéket ad vissza, így elvileg kb 4 milliárd különböző értéket tud ábrázolni. Egy program a futása során viszont több, mint négymilliárd objektumot is létrehozhat. No igen, gyakorlatban persze ez nehezen kivitelezhető, mert nincs annyi memória. De egy 64 bites brutálisan felturbózott rendszer esetén lehetne. És ha nem egyszerre hozzuk létre az objektumokat, hanem ciklusban mindig eldobálva a régiket, akkor akár egy közönséges gépen is lehet. Ilyenkor elviekben ki lehet osztani azokat a kódokat, amihez tartozó objektum már el lett dobva. Ehhez viszont valami komoly adminisztráció kellene, hogy tudni lehessen, milyen kódokat lehet kiosztani újra. Ekkora áldozatot hozni egy hash kódért egyébként is felesleges. A hash értéket használó algoritmusok eleve úgy vannak felépítve (pontosabban úgy kellene legyenek felépítve), hogy felkészüljenek a hash értékek ütközésére. A Dictionary mögött levő algoritmus például ekkor hívja az Equals() függvényt, mint ahogy ebben a cikkben nagyszerűen le van írva.

A valóság

A GetHashCode() nem garantál egyedi értéket. Mit ad vissza akkor? Röviden a válasz, hogy egy pszeudo random számot. Amikor egy példányon a GetHashCode() függvényt hívjuk, és ezt a függvényt a példány nem írta felül (tehát az System.Object implementációja fut), akkor egy véletlenszám generálódik, és azt egy speciális helyen tárolva a CLR a példányhoz rendeli.

A bizonyíték – a hash kód megjóslása

Hogy a fenti kijelentéssel nem csak egy újabb legendát indítok útnak, az alábbiakban fogjuk bizonyítani. A feladat: írni egy programot, ami megjósolja, hogy mi lesz a következő GetHashCode() kérés eredménye. Ehhez pontosan ugyanazt a véletlenszám generátort kell implementálni, amit a CLR használ a hash kód számításához, illetve szinkronba kell hozni a működésüket.

A pszeudo random generátorok feltörése a kriptográfia kedvenc területe, mivel a titkos kulcsok előállítása véletlenszámok felhasználásával történik. Ha egy SSL/TLS kapcsolat felépítésénél tudjuk a kliens véletlenszámgenerátorának a működését és az állapotát, többnyire gond nélkül származtathatjuk a kommunikáció megfejtéséhez szükséges kulcsokat.

Emiatt sok kifinomult módszer ismert véletlenszám generátorok analizálására, amelyekkel a CLR generátora is kiismerhető. Mielőtt valaki elkezdene örülni, hogy mekkora hekkelésben lesz része, gyorsan elárulom, hogy mi egy sokkal primitívebb módszert fogunk alkalmazni: ahelyett, hogy Neo-t játszanánk, egyszerűen megnézzük az SSCLI forráskódjában hogyan működik a generátor, hehehe. Akit így is érdekel, az sscli20\clr\src\vm\threads.cpp 1752 sora körül és a threads.h 942-es sora körül van a lényeg. Az alábbi kód az SSCLI-ből visszafejtett működés alapján készült:

 
public static class HashCodeOracle
{
    // Több független generátor működik a kódban, minden thread
    // sajáttal rendelkezik. Ami közös, hogy mindegyik ebből a számból
    // származtatja az állapotát:
    private const uint coreSeed = 123456789;

    // Nem fogjuk tudni pontosan, hogy adott szál generátora
    // milyen állapotban van, mivel a CLR esetleg már használta,
    // mire a tesztprogramunk kódja megkapja a vezérlést. Emiatt
    // szinkronizálni kell, amit úgy csinálunk, hogy addig próbálkozunk,
    // amíg megkapjuk a keresett értéket. Maximum az alábbi számú próbát
    // tesszük, mielőtt feladjuk.
    private const uint maxSyncTrials = 1000;

    // A CLR egy speciális helyen tárolja az adott objektum hash értékét.
    // Ezen a helyen más értékek is tárolódnak, ami igénybe vesz pár bitet.
    private const int syncFlagCount = 6;

    // Thread lokális változó, mivel minden thread saját
    // állapottal rendelkezik a véletlenszám előállításához
    // A ThreadLocal<T> adott szálon az első hivásnál inicializálja
    // magát az GetInitStateForThread() metódussal
    private static ThreadLocal<uint> state = new ThreadLocal<uint>(
                                                    () => GetInitStateForThread());
    // Kezdő állapot kiszámítása adott szálra
    private static uint GetInitStateForThread()
    {
        // Minden szálnak külön seed értéke van a véletlenszám
        // generálásához, így nem ugyanazokon a "véletlen" értékeken 
        // fut végig az összes szál
        var initState = CalculateThreadSeed();

        // Az initState változó most az első generálandó véletlenszámot
        // tartalmazza, azonban a szálon esetleg már korábban használva volt
        // az Object.GetHashCode(). Emiatt készítünk egy mintát, amihez 
        // szinkronizáljuk a generátorunk állapotát. Valós helyzetben ennél
        // komolyabb szinkronizáció kellene, mivel előfordulhat, hogy a
        // számsorozat egy másik pontjára illeszkedünk:
        var syncObject = new Object();
        var syncValue = syncObject.GetHashCode();

        // Ne legyen végtelenciklus, ha rossz az algoritmus:
        var syncIterations = 0;
        while (++syncIterations < maxSyncTrials)
        {
            // Véletlenszám generátor pörgetése
            initState = IterateState(initState);

            // Meg van az állapot!!
            if ((initState >> syncFlagCount) == syncValue)
            {
                return initState;
            } // if
        } // while

        throw new NotSupportedException("Could not sync on current thread");        
    } // GetInitStateForThread()

    // Az aktuális szál véletlenszám generátorához a szál specifikus
    // seed számolása
    private static uint CalculateThreadSeed()
    {
        // Minden szál ugyanattól a kezdőértéktől származtat
        var threadSeed = coreSeed;

        // A számításban részt vesz a thread id, ez jelenleg egy inkrementálisan
        // kioszotott szám
        var managedThreadId = Thread.CurrentThread.ManagedThreadId;

        // Itt a CLR kódjában van egy race condition, amit mi nem tudunk utánozni. 
        // Emiatt az alább ciklus rossz eredményt adhat. Az eredeti kódban nem a thread id-t 
        // használják, hanem amelyik szál az inicializáló kódra fut, az pörget egyet a seed-en. 
        // Ha létrejött egy szál, de az később számol seed-et, mint a rákövetkező, akkor nem az
        // alábbi ciklus által számolt seed-je lesz a szálnak. Tesztnek most jó lesz ez.
        for (int i = 0; i < managedThreadId; i++)
        {
            threadSeed = threadSeed * 1566083941 + 1;
        } // for i

        return threadSeed;
    } // CalculateThreadSeed()

    // A véletlenszám generátor kódja
    private static uint IterateState(uint currentState)
    {
        var managedThreadId = (uint)Thread.CurrentThread.ManagedThreadId;
        return currentState * (managedThreadId * 4u + 5u) + 1u;
    } // IterateState()

    // Adott szálon a következő hash érték számítása.
    // Egyszerűen kér egy véletlenszámot, és a felső
    // biteket felszabadítja egy shift-tel. Ez azért
    // szülséges, mert ahol egy objektum példányhoz a 
    // hash kód tárolva van, a felső pár biten flag-ek
    // vannak.
    public static int Next()
    {
        int result = 0;

        do
        {
            var currentState = state.Value;
            var newState = IterateState(currentState);
            state.Value = newState;

            result = (int)(newState >> syncFlagCount);
        } 
        while (result == 0);

        return result;
    } // Next()
} // class HashCodeOracle

A hash kód számításában az az érdekes, hogy egy szálfüggő véletlenszám generátort használ. Emiatt a fenti osztály egy thread lokális változót alkalmaz, amiben a thread-re jellemző seed értéket számolja ki, illetve a thread-re jellemző állapotot tartja fent. Az osztályt kipróbálhatjuk a következő kóddal:

static void Main(string[] args)
{
    for (var i = 0; i < 1000; i++)
    {
        Console.WriteLine("jóslat: " + HashCodeOracle.Next());
        var o = new object();
        Console.WriteLine("tény:   " + o.GetHashCode());
    } // for i
} // Main()

Egy részlet az eredményből:

jóslat: 3863873
tény:   3863873
jóslat: 34774863
tény:   34774863
jóslat: 44538317
tény:   44538317
jóslat: 65300541
tény:   65300541
jóslat: 50833958
tény:   50833958
jóslat: 54852443
tény:   54852443

A program tehát szépen követi az eredeti véletlenszámgenerátort.

Mennyire egyedi a hash kód?

Szó volt róla, hogy a GetHashCode() egy 32 bites értéket ad vissza. Valóságban azonban csak 26 bit hordoz értéket, a felső pár bit foglalt, később kiderül miért. Ez azt jelenti, hogy 2^26, azaz kb 67 millió féle értéket kapunk vissza. Ez sok? Úgy tűnhet, hogy a gyakorlatban sokszor minden példánynak lehet saját kódja. Azonban ez csalóka.

Birthday Attack

Ismert egy támadási mód, amelyet gyengébb kriptográfiai hash algoritmusok ellen lehet alkalmazni. Ennek az alapja a birthday paradoxon, amely a következőképpen szól: hány ember kell egy terembe, hogy 50% valószínűsége legyen annak, hogy van két ember ugyanazzal a születésnappal? (a születési évszám nem kell azonos legyen). Bár úgy érezzük, hogy ehhez sok ember kell, a meglepő válasz 23. Szintén meglepő, hogy 99% esélyhez, tehát a majdnem biztoshoz is elég 57 ember.

Visszatérve a mi problémánkra, vajon hány objektum hash kódja kell ahhoz, hogy jó valószínűséggel, montjuk 50%-kal ütközés legyen? A Wikipédán talált cikk képleteit alkalmazva a 26 bites hash kódnál 50% az esélye ütközésnek, ha kb 9600 objektum hash kódját kérjük el. Ha 25000 objektum hash kódját kérjük el, akkor pedig az ütközés valószínűsége 99%. Ez nem egy magas szám, kisebb programok is könnyen elérhetik.

Hash Collision a gyakorlatban

Egy egyszerű programmal könnyű ellenőrizni, hogy stimmelnek-e a nagyságrendek a fenti számításban. Készítsünk egy programot, ami addig generálja a hash kódokat, amíg ütközés nem lesz:

var hashCodes = new HashSet<int>();

int i = 0;
while (hashCodes.Add(HashCodeOracle.Next()))
{
  i++;
} // while

Console.WriteLine(i);  

A fenti kód a hash érték jósló osztályt használja. Addig tölt fel egy halmaz kollekciót a számított hash értékekkel, amíg ütközést nem észlel. Ekkor kiírja a számláló értékét, amely az általam lefuttatott tesztben 5310. Elég gyorsan sikerül tehát ütközést produkálni.

Hol tárolódik a hash érték?

Miután a System.Object.GetHashCode() véletlenszámot generált, ezt össze kell rendelni az objektummal, hogy minden rákövetkező GetHashCode() hívás ugyanazt az értéket adja vissza. Hogy történik az összerendelés? Valami mezőjében az object példánynak? Hát, igen is meg nem is.

SyncBlockIndex avagy a mosogató

Korábbi cikkekben már említettem, hogy amikor egy objektum a heapen létrejön, akkor nem csak a saját mezőinek foglalódik terület. Az a terület, amire a referencia mutat, egy speciális értékkel kezdődik, aminek sok neve van, attól függően, mire használják. Hívhatjuk type handle-nek, metódus táblának, type object pointernek. Ez az érték kell például a virtuális vagy interfész függvények feloldásához, a statikus változók eléréséhez, és még sok mindenhez. Ezután a speciális érték után jönnek a példány mezői, és utána nem jön más. Ezekre a helyekre tehát a hash kód nem fér be. Hol tárolódik akkor?

Aki olvasta a CLR via C# könyvet, az tudja, hogy kell lennie egy SyncBlockIndex nevű értéknek valahol, de hol? Az a furcsa helyzet, hogy ez a referencia által mutatott terület előtt van, azaz a -4-es (-8-as 64 bitnél) offsettől. Hogy könnyebb legyen elképzelni, valahogy igy néz ki az elrendezés:

A vicces ebben a SyncBlockIndex-ben, hogy maga az SSCLI kódjának a kommentje is mosogatónak nevezi, mivel időközben minden szutykos dolgot beleraktak már. Eredetileg az objektumok lockolását szolgálja ki ez a mező. Mik tárolódnak itt ezen kívül? Például, ha az objektum egy string, akkor egy-két információ található a stringről, amit a CLR kihasználhat optimalizáció céljából. Ha egy stringben csak ASCII karakterek vannak, akkor könnyebb konvertálgatni, case insensitive-en hasonlítgatni. Ezt a lehetőséget egy bit jelzi. De a GC is használ itt egy bitet, hogy megjelölje, amikor egy objektumhoz már eljutott. Így tudja a GC elkerülni a köröket az egymásra hivatkozó objektumok esetén.

Mivel legtöbb objektummal nem végeznek szinkronizációt, a fent említett flag-ek által meghagyott területet legtöbb esetben fel lehet használni. Ez 26 szabad bitet jelent, és ez az oka, hogy a hash érték csak 26 bites. Első lépésként nézzük meg, hogy tényleg ide kerül-e a generált hash:

Az ábrán sok minden szerepel. Egy egyszerű programkód látható, ami létrehoz egy System.Object példányt, majd elkéri a hash kódját, és kiírja (1-es pont). Alul a fekete ablakban látszik a hash kód. A 2-es pontnál az Immediate ablakba betöltött sos kiterjesztés látható, aminek a segítségével a CLR adatai között csemegézhetünk. Az ablakban látható !CLRStack -l parancs a vermen levő lokális változókat listázza ki. Az egyik változó az object példány, ennek a címe a memóriában 0x0278b2ec. Az előbb említettük, hogy a SyncBlockIndex a -4 offseten van, emiatt a 0x0278b3e8 címtől vizsgáljuk a memóriát (3-as pont). Itt található a 98 80 bf 0e érték. Ez ugyan elsőre nem hasonlít a hash értékre, azonban figyelembe kell venni, hogy a futtató számítógép processzora Little Endian ábrázolást használ, emiatt meg kell fordítani a byte-ok sorrendjét. Ekkor már csak egy apró különbség van, a hash kód 2-vel kezdődik, a memória dump pedig hexa e-vel. De tudjuk, hogy 6 bit foglalt különböző flag-ek miatt, emiatt ezeket ki kell nullázni (az alsó 4 bitből 2 bit flag), és így megkapjuk a 2-es értéket.

Megbizonyosodtunk róla, hogy a hash kódot a SyncBlockIndex tárolja. Mi van azonban akkor, ha az objektumon lock-ot hajtunk végre? A SyncBlockIndex eredeti feladata az, hogy a lockokáshoz szükséges struktúrát meg lehessen találni. A C# lock kulcsszó mögött egy Monitor osztály van, a Monitor osztály mögött pedig egy Critical Section objektum, amin keresztül a Windows operációs rendszer egyik szinkronizációs szolgáltatása érhető el.

Amikor egy objektumra lock-ot teszünk, akkor a CLR létrehoz egy Critical Section objektumot, amit a lockolt objektummal össze kell rendelni. Az Critical Section objektum (leegyszerűsítve) egy struktúrába kerül, amit SyncBlock-nak hívnak. Ezek a SyncBlock-ok egy tömbbe vannak rendezve. Hogy egy objektumhoz melyik SyncBlock tartozik, azt a már megismert SyncBlockIndex mondja meg.

Ebbe a SyncBlockIndex-be viszont már ott ül a hash kód. Mi történik hát, ha egy objektumra lockot teszünk? A problémát úgy oldották meg, hogy SyncBlock-nak több rekesze van. Itt elfér a Critical Section objektum és a hash kód is. A SyncBlockIndex felső pár bitje flag-eket kódól, itt van leírva, hogy mi a SyncBlockIndex tartalma. Amikor lock-olunk, és a SyncBlockIndex nem indexként használt, akkor a SyncBlockIndex 26 szabad bitje átmásolódik a SyncBlock-ba, mint hash érték. Emellett a SyncBlockIndex flag-jei jelzik, hogy a tartalom most már tényleg SyncBlockIndex. A következő GetHashCode() kérés így tudja, hogy a generált véletlenszámot honnan kell elővenni, közvetlenül a SyncBlockIndex-ből vagy a SyncBlock-ból.

A mechanizmust nyomkövetéssel ellenőrizhetjük:

Az ábra hirtelen ránézésre kuszának tűnhet, de nem olyan bonyolult: A program most egy lock-on belül írja ki a hash kódot (1-es pont). Emiatt a SyncBlockIndex-et nem lehet a hash kód tárolására használni. Hogy erről megbizonyosodjunk, kilistázzuk a vermen levő példányokat (2-es pont). Az Object példányunk a 0x0251b2ec címen van, ezt 4 byte-os eltolással listázzuk ki, a 0x0251b2e8 címtől (3-as pont). Látszik, hogy a SyncBlockIndex értéke 0x08000001 (Little Endian, fordítani kell). A felső részen a flag-ek vannak, alul pedig az index, ami most 1. Az immediate ablakban egy !SyncBlk paranccsal kilistázzuk a SyncBlock-okat (4-es pont), itt látszik, hogy csak egy ilyen van, és ennek az indexe 1. A sor végén az is látszik, hogy ez a mi System.Object példányunkhoz tartozik. Ha kilistázzuk a SyncBlock memóriaterületét (5-ös pont) akkor látszik, hogy ez a terület sok információt tárol. Ezek között megtaláljuk a hash kódot is.

Konklúzió

Az, hogy hogyan működik a GetHashCode() default implementációja, lényegtelen a fejlesztő szempontjából. Néhány félreértés viszont okozhat problémát. Ha a fejlesztő arra épít, hogy minden objektum saját, egyedi hash kóddal fog rendelkezni a default implementáció szerint, akkor a programja hibásan fog működni. Arra sem szabad építeni, hogy ugyanolyan mezőtartalommal a GetHashCode() ugyanazt az értéket adja vissza (value type-ok esetén igen, ott nem az eddig ismertetett mechanizmus működik), hiszen szimpla véletlenszámokról van szó.

  1. #1 by Mező Gábor on 2011. September 12. - 10:56

    Nagyon szeretem a cikkeidet olvasni. Keep it up!

    Bár én a helyedben nem osztogatnám ingyen, hanem összeszedegetném, és kiadnám egy könyvben Inside C# vagy valami hasonló néven.😉

    Üdv,
    chikk

  2. #2 by Tóth Viktor on 2011. September 12. - 20:06

    Köszönöm! A könyvvel kapcsolatban, attól tartok a befolyó pénzből nem sok túrórudit tudnék venni🙂

  1. What does Object.GetHashCode() return? | ProC#tology

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: