Double-checked locking pattern

Michał ‘mina86’ Nazarewicz | 29 kwietnia 2008

Jakiś czas temu w pewnych okolicznościach poruszony został wzorzec double-checked locking singleton, który jak powszechnie wiadomo nie jest do końca poprawny. Wynikła z tego krótka dyskusja, której kompilację pozwolę sobie wkleić poniżej (gdyż nie jest ona ogólnie dostępna, a nie lubię, gdy informacje się marnują).

Witam wszystkich,

chciałbym odnieść się do poruszonego przeze mnie problemu poprawności efektywnego wzorca singletonu dla programów wielowątkowych zwanego również double-checked locking pattern1. W tym celu, na początku przywołam trochę teorii.

Standard C++ definiuje pojęcie sequence point, na bazie którego określa zachowanie programu. Konkretnie opisuje stan środowiska wykonującego program w konkretnych punktach sekwencyjnych. Co się dzieje pomiędzy nimi nie jest powiedziane. W szczególności nie jest prawdą, że wyrażenie po prawej stronie operatora przypisania musi być wykonane zanim nastąpi przypisanie. Bardzo prostym przykładem jest kod:

int foo = 0x42;
int bar = 42;
/* 1 */
foo = bar++;
/* 2 */

w którym standard definiuje, iż w pierwszym. punkcie zmienne foo i bar mają wartości odpowiednio 0x42 i 42, a w drugim — 42 i 43, ale nie określa ich wartości przejściowych. Kompilator może powyższy kod zaimplementować najpierw przypisując zmiennej foo wartość zmiennej bar, a potem dopiero inkrementując tą drugą2:

foo = bar;
++bar;

Sugerowałoby to, iż miałem rację twierdząc, iż instrukcja instance = new Foo(); może spowodować uruchomienie konstruktora dopiero po przypisaniu adresu przydzielonej pamięci do zmiennej. Muszę się jednak przyznać, iż standardu C++ nie studiowałem tak dogłębnie jak standardu C i nie wiem, czy przez przypadek operator new nie wprowadza kolejnego punktu sekwencyjnego3. Gdyby tak było, to kod ten należałoby traktować jak:

Foo *new_foo() { return new Foo(); }
/* … */
instance = new_Foo();

w którym problem nie powinien4 już występować, gdyż wszystkie efekty uboczne funkcji muszą zostać wykonane zanim zwróci ona swoją wartość, a więc konstruktor musi być wywołany zanim funkcja zwróci adres przydzielonej pamięci.

Po tych wszystkich przemyśleniach postanowiłem sprawdzić jak to wygląda w praktyce i faktycznie, kompilacja kodu:

struct Foo {
    static Foo *instance() {
        static Foo *inst = 0;
        if (!inst) inst = new Foo(0);
        return inst;
    }

    int get() const { return 0; }

    Foo(int p) : param(p) { }

private:
    int param;
};

int main(void) {
    return Foo::instance()->get();
}

wskazuje, iż wartość do zmiennej inst została przypisana dopiero po wywołaniu konstruktora.

Czas na chwilę refleksji. Przeanalizowany przykład nie potwierdził moich zarzutów, ale wcale nie spowodowało to, iż przestałem uważać, iż mam rację, że wzorzec ten jest błędny. :) Czemu jestem taki pewny siebie? Ponieważ, nawet jeżeli w C++ standard wymaga wywołania konstruktora zanim operator new zwróci wynik, to kto mi zagwarantuje, że identycznie zachowują się wszystkie języki programowania? Z informacji, które swego czasu do mnie dotarły wynika, iż Java oraz C# mają co do tego ździebko odmienne zdanie.

Skoro już się tyle rozpisałem to należy też poświęcić trochę uwagi poruszonemu (przez kogoś z tyłu sali) problemowi, gdy instrukcja przypisania jest nieatomowa. Zostawiam to na sam koniec po części dlatego, że kończy to całą dyskusję, a jeśli chodzi o różne dziwne, założenia, że instrukcja przypisania jest zawsze atomowa odpowiadam bardzo prostym przykładem: 16-bitowy procesor Intel 8086 (do 80286 włącznie), w którym dalekie wskaźniki są 32-bitowe, a procesor potrafi wykonywać atomowe operacje jedynie na 16-bitowych porcjach danych5. Jeżeli ktoś mi zarzuci, iż to jakieś przedpotopowe procesory, to z chęcią podam drugi przykład: zapis do 32-bitowej zmiennej leżącej na granicy linii cache’u6 powoduje w procesorach i386 dwa zapisy przy równoczesnym braku blokowania magistrali7.

Poza tym artykuł na stronie IBM uświadomił mi8, iż w grę wchodzi jeszcze kolejność wykonywania operacji przez procesor, która wcale nie musi być tożsama z kolejnością instrukcji w kodzie maszynowym. Procesor może stwierdzić, iż lepiej będzie najpierw zapisać wskaźnik, a dopiero potem wykonać jakieś przypisanie z konstruktora, nawet jeżeli napotkał na te instrukcje w odwrotnej kolejności. W przypadku maszyn jednoprocesorowych nie stanowi to problemu, ale w przypadku maszyn wieloprocesorowych (wielordzeniowych) już tak.

Przypisy

1 Dla osób nieobecnych na wykładzie, chodzi o:

class Foo {
    Foo *getInstance() {
        static Foo *instance = 0;
        if (!instance) {
            Lock lock(mutex);
            if (!instance)
                instance = new Foo();
            }
        }
        return instance;
    }
};

Twierdzę, iż wzorzec ten jest niepoprawny.

2 Szczerze mówiąc tak właśnie bym się spodziewał, że ta instrukcja zostanie zaimplementowana, gdyż alternatywą wobec tego jest tworzenie niepotrzebnych zmiennych tymczasowych (np. niepotrzebne zużywanie rejestru). Aby sprawdzić swoją intuicję postanowiłem zrobić pewien test:

[mina86@tuptus ~/code]$ cat foo.c
int main(void) {
    int foo = 42;
    int bar = 0x42;
    foo = bar++;
    return foo + bar;
}
[mina86@tuptus ~/code]$ g++ -S -o foo.s foo.c
[mina86@tuptus ~/code]$ cat foo.s
        .file   "foo.c"
        .text
        .align 2
.globl main
        .type   main, @function
main:
.LFB2:
        leal    4(%esp), %ecx
.LCFI0:
        andl    $-16, %esp
        pushl   -4(%ecx)
.LCFI1:
        pushl   %ebp
.LCFI2:
        movl    %esp, %ebp
.LCFI3:
        pushl   %ecx
.LCFI4:
        subl    $16, %esp
.LCFI5:
        movl    $42, -12(%ebp)
        movl    $66, -8(%ebp)
        movl    -8(%ebp), %eax	; ### eax = bar ###
        movl    %eax, -12(%ebp)	; ### foo = eax ###
        incl    -8(%ebp)		; ### ++bar     ###
        movl    -8(%ebp), %eax
        addl    -12(%ebp), %eax
        addl    $16, %esp
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
.LFE2:
        .size   main, .-main
.globl __gxx_personality_v0
        .ident  "GCC: (GNU) 4.1.2"
        .section        .note.GNU-stack,"",@progbits

Wyróżnione przeze mnie linie wskazują, iż kompilator zachowuje się tak jak przewidziałem.

3 Wydaje się, iż w przypadku przeciążania tego operatora sequence point faktycznie jest dodawany, z racji faktu, iż jego użycie jest wówczas zamaskowanym wywołaniem funkcji, a wywołania funkcji dodają sequence point.

4 Nadal jakiś kompilator mógłby próbować to optymalizować, ale wówczas nie byłby to kompilator zgodny ze standardem C++.

5 Takie samo zachowanie występuje rzecz jasna na nowszych generacjach tego procesora działających w trybie real.

6 Chyba wystarczy, żeby nie była wyrównana do jakiejś mniejszej jednostki.

7 Przynajmniej nie znalazłem wzmianki o tym, aby instrukcja mov blokowała magistralę w intelowskim Software Developer’s Manual.

8 Link do artykułu, na który się powoływałem, gdzieś mi niestety zaginął.