Threading.Interlocked methods are not full fences

Everybody is in the wrong lane

When you google Interlocked class, you will find many blogs/articles/other things claiming that methods in the Interlocked class generate full fences. Even the excellent book CLR via C# from Jeffrey Richter claims it on page 803 (Interlocked Constructs).

Now what I am saying is: no, Interlocked operations are not full fences. When everything is coming your way, you’re in the wrong lane, you could answer. But not this time, and I am going to prove it.

What do Interlocked methods actually do?

To see what is the implementation of the Interlocked methods, check the generated assembly code of the following simple program:

class Program
{
    static int source = 10;
    static int destination = 0;

    static void Main(string[] args)
    {
        Debugger.Break();

        Interlocked.Exchange(ref destination, source); 
    }
}

The generated code is:

// Debugger.Break();
00000000  call        65BE7D10 

// Interlocked.Exchange(ref destination, source);
00000005  mov         eax,dword ptr ds:[00293358h] 
0000000a  xchg        eax,dword ptr ds:[0029335Ch] 

00000010  ret 

At the core of the implementation of Interlocked.Exchange() method (which is inlined), there is an x86 XCHG operation. From the manual of the processor we can learn that XCHG does a full fence. It seems that I am the one who drives on the wrong side. But wait a minute! CPU is only one component of the processing flow when we use a high level language like C#. The C# compiler still can reorder operations, and we have the jitter too. If an Interlocked operation is a full fence, it prevents the compiler and the jitter to do reordering across the call of Interlocked.Exchange() method.

The test

It is hard to predict when will the compiler/jitter optimize, but there is a common scenario: variables in the conditional expression of a for loop are often optimized into registers. If we use an Interlocked.Exchange() in the for loop, the program flow crosses the full fence before it reaches the evaluation of the conditional expression (not the first time, but after). According to the rules of full fencing, a read operation cannot cross the fence, so before the second evaluation of the conditional expression, the variables must be read from the memory again. Let’s see:

class Program
{
    static int source = 10;
    static int destination = 0;

    static void Main(string[] args)
    {
       Debugger.Break();

       for (var i = 0; i < source; i++)
       {
            Interlocked.Exchange(ref destination, source);
       } 
    }
}

And the generated code:

// Save stack state
00000000  push        ebp 
00000001  mov         ebp,esp 
00000003  push        esi 

// Debugger.Break
00000004  call        65A27D10 

// for loop, i = 0. So "i" will be in esi
00000009  xor         esi,esi 

// first evaluation of the conditional expression. It works
// a bit different as we expected. Here the jitter knows that
// i = 0, so i < source is false if source <= 0. This is what
// checked below:
// read "source" into edx:
0000000b  mov         edx,dword ptr ds:[001A3358h]     // enregister "source"

// source <= 0? 
00000011  test        edx,edx 

// if it is, goto after the loop
00000013  jle         00000022 

// the implementation of the Interlocked.Exchange().
// at this moment variable "source" is in edx. It is ok to use it
// because this is the first execution of the loop,
// so we have not crossed the fence yet.
00000015  mov         eax,edx 
00000017  xchg        eax,dword ptr ds:[001A335Ch]     // the fence is here

// i++
0000001d  inc         esi 

// this is the second and further evaluation of the conditional
// expression. but wait! the enregistered value in edx is being used, 
// so the read operation at 0x0000000b crossed the fence!!
0000001e  cmp         esi,edx                          // using enregistered value

// execute loop again, if i < enregistered "source"
00000020  jl          00000015 

// back to caller.
00000022  pop         esi 
00000023  pop         ebp 
00000024  ret 

As we can see, the program flow crossed the fence, but the read operation of the source variable was used behind the fence. If Interlocked.Exchange() would be a full fence, the “soure” variable would not be enregistered. We can try this using a real fence, Thread.MemoryBarrier():

class Program
{
    static int source = 10;
    static int destination = 0;

    static void Main(string[] args)
    {
        Debugger.Break();

       for (var i = 0; i < source; i++)
       {
            Interlocked.Exchange(ref destination, source);
            Thread.MemoryBarrier();
       } 
    }
}

And the generated code:

// Save stack state
00000000  push        ebp 
00000001  mov         ebp,esp 

// Debugger.Break
00000003  call        65D37D10 


// for loop, i = 0
00000008  xor         edx,edx 

// This time it is a direct operation on "source". But the logic 
// remained the same, instead of i < source, it check source <= 0
0000000a  cmp         dword ptr ds:[00143358h],0 
00000011  jle         0000002C 

// Interlocked now uses direct read
00000013  mov         eax,dword ptr ds:[00143358h] 
00000018  xchg        eax,dword ptr ds:[0014335Ch] 

// implementation of MemoryBarrier(). It uses a lock prefix when does "nothing"
// with the top of the stack. The lock prefix makes the fence at CPU level. We 
// do not really need it now, because CPU fence was made by xchg just one operation
// before.
0000001e  lock or     dword ptr [esp],0 

// i++
00000023  inc         edx 

// this is the second and further evaluation of the conditional
// expression. Now it re-reads value of "source" variable
00000024  cmp         edx,dword ptr ds:[00143358h] 
0000002a  jl          00000013 

// back to caller.
0000002c  pop         ebp 
0000002d  ret 

Conclusion

We found an example where a method of Interlocked class did not act as fence. The confusion around this class probably comes from the fact, that at machine code level it uses fencing instructions.

  1. #1 by Anonymous on 2011. December 21. - 15:19

    Hmm erdekes. Nem lehet, hogy ez valami jitter bug ? (32/64 biten is ez az eredmeny ?) Joe Duffy is explicit leirja, hogy az Interlocked az full fence compiler es processzor szinten is. Nem ertek asm-hez, de nekem 32bit 2.0FW alatt igy nez ki a kerdeses resz:
    00000029 lea ecx,ds:[00982FE4h]
    0000002f mov edx,dword ptr ds:[00982FE0h]
    00000035 call 7902C5E7 ; ez az Exchange hivas, ha minden igaz (nem tudom hogyan juthatok el a xchg utasitashoz)

  2. #2 by Tóth Viktor on 2011. December 21. - 19:23

    Helló,

    Valószínűleg visual studioból indítottad a kódot, és emiatt a jitter nem inline-olta be az Exchange() hívást. Ekkor visual studiót használva egyébként bele sem tudsz lépni a hívásba, és nem tudod megnézni az implementációt. Én visual studión kívül indítom, és a Debugger.Break() hívás húzza be a debuggert.
    64 biten a példakódból generált kód valóban nem tartja a változót regiszterben, szóval úgy látszódhat, mintha működne az Interlocked osztály fencing-je. Azonban ha megnézünk 64 biten egy üres for ciklust, kiderül a turpisság:

    00000000 sub rsp,28h

    // Debugger.Break();
    00000004 call FFFFFFFFE83F64A0

    // source beolvasása
    00000009 mov r11d,dword ptr [FFEE3678h]

    // source < 0?
    00000010 test r11d,r11d
    00000013 jle 000000000000002C

    // i = 0
    00000015 xor ecx,ecx

    // Ez valószínű azért kell, hogy 16 byte határra igazítsa a ciklus
    // magját
    00000017 nop word ptr [rax+rax+00000000h]

    // i++
    00000020 inc ecx

    // source beolvasása regiszterbe
    00000022 mov eax,dword ptr [FFEE3678h]

    // i < source?
    00000028 cmp ecx,eax
    0000002a jl 0000000000000020

    0000002c add rsp,28h
    00000030 ret

    Tehát az x64-re dolgozó jitter optimalizálás tekintetében láthatólag nyomában sincs az x86-ra fordítónak. Így itt nem tudjuk megnézni, hogy generált-e fencinget az interlocked vagy nem.

    Viszont találni más esetet is x86-ra, ahol egy olvasás elémegy az interlocked-nak. Nézzük a következő kódot:

    for (var i = 0; i < source; i++)
    ;

    Interlocked.Exchange(ref destination, source);

    for (var i = 0; i < source; i++)
    ;

    Igaz, most is a for ciklust használjuk arra, hogy rávegyük a jittert az optimalizálásra (biztos máshogy is lehet), viszont maga a fencing nem a ciklusban van. Mégis, a második for ciklus "source" olvasása igazából az Interlocked.Exchange() előtt történik meg, azaz nem volt fence:

    // Verem, regiszterek mentése
    00000000 push ebp
    00000001 mov ebp,esp
    00000003 push esi

    // Debugger.Break();
    00000004 call 676C7D10

    // Első for ciklus:
    // i = 0
    00000009 xor esi,esi

    // "source" olvasása egy regiszterbe, ez keresztezi majd az
    // Interlocked műveletet
    0000000b mov edx,dword ptr ds:[00253358h]

    // A conditional expression kiértékelése az első lefutáshoz
    // i = source)
    00000011 test edx,edx
    00000013 jle 0000001A

    // i++
    00000015 inc esi

    // Conditional expression a további lefutásoknál
    // i < source? a regiszterből olvas, de ez legális,
    // nem volt fence
    00000016 cmp esi,edx
    00000018 jl 00000015

    // Interlocked.Exchange() be-inline-olva
    0000001a mov eax,edx
    0000001c xchg eax,dword ptr ds:[0025335Ch]

    // Második for ciklus
    // Most az eax lesz a ciklusváltozó,
    // i = 0
    00000022 xor eax,eax

    // WOW!!!! Átléptük a fence-t, mégis, a regiszterből olvas.
    // Ez azt jelenti, hogy bár a C# kódban itt egy olvasást végzünk
    // a source-ra, de ez az olvasás valójában az első for ciklus előtt
    // történt meg, innen nézve túl a fence-en.
    // Egyént meg source <= 0?
    00000024 test edx,edx
    00000026 jle 0000002D

    // i++
    00000028 inc eax

    // i < source
    00000029 cmp eax,edx
    0000002b jl 00000028

    // Vissza a hívóhoz.
    0000002d pop esi
    0000002e pop ebp
    0000002f ret

    Szóval nem egyedi esetről van szó, és nem csak egy ciklus magjában lehet előhozni az anomáliát (annak ellenére, hogy magához az optimalizáláshoz most is a ciklust használtam)

    Persze, Joe Duffy nagy koponya, mint ahogy Jeffrey Richter is. Ugyanakkor ezek az emberek is tévednek, például lásd a GetHashCode-ról szóló cikkemet. Másik oldalról az MSDN (ami szintén nem mindig tökéletes) igazából nem mondja, hogy az Interlocked az memory fence-ként működne. Nem hinném, hogy a jitter hibája lenne. Sajna nincs meg az éles CLR forráskódja nekem, így nem tudom megnézni mi történik ott. Az SSCLI-ben nem láttam optimalizálást, ott meg azért nem tudtam megnézni.

    • #3 by Anonymous on 2011. December 22. - 00:38

      Termeszetesen Release buildet hasznalva es nem VS-bol inditva probaltam a dolgot. A GetHashCode-os cikket olvastam – az is nagyon erdekes volt – de konnyen lehet, hogy mikor Richter irta a konyvenek azt a reszet, meg mashogy mukodott. Meg az MSDN is megemliti, hogy GetHashCode mukodese barmikor megvaltozhat (es valoszinu mar valtozott is a FW szuletese ota). Azert kivancsi lennek, hogy biztos nem a jitter az, ami tul okos ebben a moricka peldaban. Szoval ha egy ThreadPool.QueueUserWorkItem(_=>source++); is szerepelne a Main-ben akkor is ugyanez lenne az eredmeny ? (Kiprobalnam en is, csak nekem nem igy nez ki az asm)

  3. #4 by Tóth Viktor on 2011. December 22. - 09:47

    Bocsánat, akkor pedig valószínű régebbi verziót használsz, és ott nem annyira agresszív még az inline-ing.
    A QueueUserWorkItem()-mel kapcsolatban nem egészen értem a koncepciódat, ha az általad leírt sort a Main() törzsébe írom, akkor az nem fogja használni a “source” változót. Az fog történni, hogy a “_ => source++” alapján készít egy metódust, aminek a törzse lesz a “source++” mint programkód. Ez a metódus a Program osztály egy metódusa lesz. A Main() metódus törzsének a kódja pedig annyival bővül, hogy létrehoz egy delegate-et (WaitCallback típussal), ennek odaadja az előbb említett metódus címét, majd az így összeállított delegate-tel meghívja a QueueUserWorkItem()-et. Tehát bár a programkód szövege a Main()-ben tartalmazni fog egy új hivatkozást a “source” vátozóra, valójában ezt már a c# compiler kiszedi onnan, hiszen ezek csak szintaktikai könnyítések, régebbi C# verziókban eleve le sem írhattuk volna, azt a kódot kellett volna begépelnünk, amit végülis a c# fordító most elvégez nekünk. Mivel nem is használjuk ekkor a “source” változót a Main-ban, nem látom hogyan befolyásolná az optimalizációt.
    A fentiek miatt nem értem, hogy mit szeretnél pontosan, hogy mit próbáljak ki.
    A nagy emberek hibáival és a GetHashCode()-dal kapcsolatban, a könyv 3-as kiadása elvileg a 4-es frameworkhöz van igazítva, és az is tartalmazza a hibát, de az algoritmust az SSCLI-ből szedtem, ami pedig a 2-es framework testvére. A 2-3-4 verzió tehát ezt használja. Szerintem annyi történt, hogy egyszerűen nem nézett utána, hanem elhitte valakinek. Vannak más hibák is abban a könyvben, például ugyanaz, amit a szinkronizáció buktatói cikkben a lock kulcsszóból generált kódnál és is elkövettem, és Kovács Zoltán Attila vette észre. Senki nem tévedhetetlen, és mivel nagyon sok idő/energia mindennek utána nézni, vagy utána gondolni, az ember a jónak tartott forrást elhiszi, és emiatt természetes, hogy előfordulnak biztosnak állított, de téves információk.
    Ha egyéb ötleted van kipróbálásra, szívesen megnézem, de attól a helyzet az álláspontom szerint megmarad: mivel van ellenpélda, az interlocked nem ad full fence-t, legalábbis nem minden esetben.

    • #5 by Anonymous on 2011. December 22. - 11:14

      Koszi a kimerito valaszt, de pont ez a koncepciom lenyege. Azaz legyen hivatkozas mondjuk egy masik szalbol is a source-ra. Lehet nem valtoztat semmit a dolgon, de amig a jitter tudja, hogy csak egy szal van, akar meg agresszivebben is optimalizalhat. Persze ez mind talalgatas.

  4. #6 by Tóth Viktor on 2011. December 22. - 14:41

    Ja értem. Kipróbáltam, amit mondtál, de nem változtat. Egyébként a .NET alatt soha nincs csak egy szál. A ThreadPool eleve beröffent szálakat, ott a timer-nek a dedikált szála, a debugger szál (ami akkor is van, ha nincs attacholt debugger). Igy mindig van esélye, hogy másik szál fut. Másrészt a jitter nem olyan szofisztikált, egyszerűen nincs rá ideje. Gyorsnak kell lennie, mert ha sokat gondolkodik, akkor végül több idő megy el optimalizálásra, mint amennyivel az optimalizált kód gyorsabb lesz. Emiatt annál egyszerűbb dolgokkal sem foglalkozik, mint hogy fut-e másik szál vagy nem. Egy C++ fordító például már 15 éve is kivágta a kódból az üres for ciklusokat, a példakódban meg benne maradt, látod. Szépen eldarálja a ciklusváltozót, aztán nem használja semmire, és nem veszi észre, hogy mindez felesleges. Ilyen kis ügyetlen.
    Harmadrészt, alaposabban elolvasva a Thread.MemoryBarrier doksiját, ott is azt írja, hogy CPU levelen barrier. Az egyik komment rá is kérdez, hogy a silverlight doksijában a compiler-jittert is említik, itt hogy hogy nem szerepel. Szóval még a MemoryBarrier is kérdéses, hogy compiler-jitter szinten hat-e. Majd megpróbálok felhajtani valami microsoftos emberkét, és megkérdezni ezeket tőle, hátha mondanak okosat. De most már csak annak hiszek, aki konkrétan a compiler/jittert írta🙂

    • #7 by Anonymous on 2011. December 22. - 15:07

      Koszi szepen, ez tenyleg nagyon fura akkor.

  5. #8 by flata on 2012. February 21. - 11:10

    System.Threading.SpinLock.Exit(bool useMemoryBarrier)

    Akkor ez most hogy is van? Itt, ha jól látom, Interlocked.Exchange hívással akarja a memory barriert elintézni.

    • #9 by Tóth Viktor on 2012. February 21. - 12:24

      Neki azért kellhet a MemoryBarrier, mert több mag akarhatja a lockot, és ha az egyik elengedi (és ezzel SpinLock belső állapotát módosítja), akkor arról nem árt, ha a többi mag időben értesül. Ha true-ra rakod a useMemoryBarrier értéket, belül egy Interlocked.Exchange-t használ, ami azt eredményezi, hogy a többi mag nézőpontjából is megváltozik a SpinLock állapota. Egyébként pedig csak tekerne a többi mag a cache által tárolt “foglalt” állapot körül, amíg véletlenül valamiért újra nem olvas a cache.
      Hogy miért van értelme mégis az UseMemoryBarrier = false-nak? Ez a hotness/fairness téma, ha barrier nélkül engeded el a lockot, akkor a következő enternél valószínű a te szálad lesz sikeres, mivel a többi még mindig foglaltnak látja a lockot (a cache miatt).

      Szóval kicsit más itt a téma, nem barrierként használja az useMemoryBarrier-t, hanem cache szinkronizációnak. Igazi barrierként valószínűleg csak a volatile változók működnek (erre a CLI specifikáció is kimondja), esetleg még a lock kulcsszót annak veszi a c# compiler, de még nem jártam utána. Kicsit több a melóm mostanában, mint eddig, ezért lassultak be a cikkek.

      • #10 by flata on 2012. February 21. - 13:52

        Tehát, ha “A” szál vár a zárra, mivel “B” szál lefoglalta már, hogy “X” halmaz változóit megváltoztathassa, akkor miután “B” szál elengedi a zárat, “A” szál már le tudja foglalni, de ezután nem feltétlenül fogja “X” halmaz változóit a legfrissebb állapotban látni? Ehhez egy explicit MemoryBarrier hívás szükséges? Furcsálom, nem valami “developer friendly”🙂.

      • #11 by Tóth Viktor on 2012. February 21. - 14:20

        Nem, akkor rosszul magyaráztam. Van “A” és “B” szál, használnak egy közös SpinLock-ot, ami “X” belső változójában tárolja, hogy ő maga szabad-e vagy nem. Kezdetben “A” szál birtokolja a lockot, tehát “X” valami olyasmit ír le, hogy “A szálhoz tartozom”. Amikor “A” elengedi a lockot, akkor frissül “X” állapotváltozó tartalma, hogy most már szabad a SpinLock. Na itt lehet meghatározni, hogy useMemoryBarrier. Ha nem kell barrier, akkor az “X” állapotváltozó tartalma sokkal később szivárog át a “B” szál cache-ébe, emiatt “B” szál még mindig pörögni fog a SpinLock-on, olvasgatva “X”-et, mivel a régi tartalmát látja.
        Ha “A” szál használja useMemoryBarrier-flag-et, akkor a belül használt Interlocked művelet miatt az “X” tartalma az összes mag/processzor számára láthatóvá válik szinte azonnal (hardveres szinkronizációval), és így a “B” szál rá tud ugrani.
        Ha false a useMemoryBarrier, akkor az “A” szálnak a következő lockolásnál több esélye lesz, mivel a “B” szál esetleg még nem látja, hogy szabad a lock. Emiatt ez a működés “hot”, az utoljára dolgozó szál kezelheti a lockolt adatot (ami adat így nagyobb valószínűséggel van a maghoz tartozó cache-ben). Ellenkező esetben a működés “fair”, itt egyenlő esély van a lock elvitelére.

      • #12 by flata on 2012. February 21. - 16:28

        Na akkor ezt én nem írtam érthetően, megpróbálom formálisan

        A, B – szál
        X – védett memória tartalom
        Y – zárt reprezentáló belső változó (amit Te X-nek neveztél)

        A: Exchange Y := 1
        B: …
        A: X[0] = 1
        B: …
        A: X[1] = 2
        B: …
        A: Exchange Y := 0
        B: Exchange Y := 1
        B: p := X[0], q := X[1]

        Ekkor biztosan elmondható, hogy p = 1, q = 2?
        A leírtakból úgy gondolom, hogy *nem*, és ezt nem tartom developer friendlynek, főleg hogy useMemoryBarrier-ként jelenik meg az említett paraméter. Szükség van-e az explicit Thread.MemoryBarrier() hívásra?

  6. #13 by flata on 2012. February 21. - 16:33

    Ha jól tudom, a ECMA szabvánnyal ellentétben a CLR memory modeljében minden írás volatile, így a lock megszerzése után kellene hívni az MB-t.

    • #14 by Tóth Viktor on 2012. February 21. - 18:15

      A példádban, ha UseMemoryBarrier-t használsz, akkor a p és a q a megfelelő értéket fogja tartalmazni. Azért van ez így, mert az intel processzorokon a lock-olt műveleteket (mint például a MemoryBarrier mögött levé lock or) nem léphetik át az írások/olvasások (pontosabban a lock előtt indított írás nem végződhet a lock mögött, és a lock mögött kiadott olvasás nem történhet meg a lock elött). Másikoldalról, az intel konzisztenciát biztosít más processzorról nézve az írások és az olvasások sorrendjére (tehát ha “A” processzor X,Y,X sorrendben írta a memóriát, akkor az másik “B” processzoron is ebben a sorrendben látszik az írás.
      Na most, ha a lockolt írás (mint az Interlocked.Exchange) látszik a másik processzoron is “azonnal”, illetve ehhez az azonnal látszódó íráshoz képest is megtartja az írási sorrendet az intel processzor, akkor ha előbb írod X[0]-t és X[1]-t, majd lock-olt utasítást (mint Interlocked.Exchange) használsz Y írására, akkor az írási sorrend a végrehajtó processzor szemszögéből X[0], X[1], Y, szükségképpen ezt az írási sorrendet látja a B processzor, plusz Y-t már most látja (a lock miatt), tehát X[0]-t és X[1]-et is most látja (ezt meg az írási sorrend miatt kénytelen most látni).
      Remélem nem volt túl zavaros.
      A CLR memória modellt pont az x86 nagylelkűsége miatt kellett szigorítani, mivel ott semmit nem kellett tenni a konzisztencia érdekében, ezt a fejlesztők megszokták, és emiatt egy itaniumon, ami nem ilyen konzisztens, megfeküdnének a programok.

      • #15 by flata on 2012. February 22. - 22:38

        Már kapizsgálgatom, lehet végig kéne még néhányszor olvasni a “A szinkronizáció buktatói” cikket🙂. Köszönöm!

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: