lock-free Queue

[FlashBurn]

Ich habe mich an einer lock-free Queue probiert und das ganze auch noch mit Templates und ich muss dazu sagen, ist mein erstes Template, also nicht gleich schlagen

template <typename T>
class atomicPtr {
public:	
	T *ptr;
	uint32t count;

	atomicPtr(T *val)  : ptr(val), count(0) {}
	atomicPtr(T *val, uint32t init) : ptr(val), count(init) {}

	~atomicPtr() {}

	atomicPtr<T>& operator=(const atomicPtr<T> &init) {
		ptr= init.ptr;
		count= init.count;

		return *this;
	}

	bool operator==(const atomicPtr<T> &other) {
		if(ptr == other.ptr && count == other.count)
			return true;
		else
			return false;
	}

	bool operator!=(const atomicPtr<T> &other) {
		return !(*this == other);
	}
};

template <typename T>
class queueItem {
public:
	atomicPtr<queueItem> next;
	T *obj;

	queueItem(T *val) : next(NULL), obj(val) {}

	~queueItem() {}

	queueItem* operator new(uint32t size) {
		return queueAllocItem();
	}

	uint32t operator delete(queueItem *ptr) {
		return queueFreeItem(ptr);
	}
};

template <typename T>
class queue {
	atomicPtr<queueitem<T>> head;
	atomicPtr<queueItem<T>> tail;
	queueItem<T> dummyNode;
public:	
	queue() : head(&dummyNode), tail(&dummyNode) {}

	~queue() {}

	bool enqueue(T *obj) {
		queueItem<T> *item;

		if(unlikely(!obj))
			return false;

		item= new queueItem<T>(obj);

		while(true) {
			atomicPtr<queueItem<T>> t= tail;
			atomicPtr<queueItem<T>> n= t.next;
			//look if t and the tail are still the same
			if(likely(t == tail)) {
				//look if the next pointer is null
				if(likely(n.ptr == NULL)) {
					//try to set the next ptr of the tail
					if(likely(atomicCAS8b(&t.next,&n,&atomicPtr<queueItem<T>>(item,n.count + 1))))
						break;
				} else {
					//try to update the tail
					atomicCAS8b(&tail,&t,&atomicPtr<queueItem<T>>(n.ptr,n.count + 1));
				}
			}
		}
		//try to update the tail
		atomicCAS(&tail,&t,&atomicPtr<queueItem<T>>(item,tail.count + 1));

		return true;
	}

	T* dequeue() {
		atomicPtr<queueItem<T>> h;
		T *res;

		while(true) {
			h= head;
			atomicPtr<queueItem<T>> t= tail;
			atomicPtr<queueItem<T>> n= h.next;
			//look if h and head are still the same
			if(likely(h == head)) {
				//look if head == tail, either queue is empty or we need to update tail
				if(unlikely(head == tail)) {
					//queue is empty
					if(unlikely(n.ptr == NULL))
						return NULL;
					//try to update tail
					atomicCAS8b(&tail,&t,&atomicPtr<queueItem<T>>(n.ptr,tail.count + 1));
				} else {
					//get the object before someone changes it
					res= next.ptr->obj;
					//try to update the head
					if(likely(atomicCAS8b(&head,&h,&atomicPtr<queueItem<T>>(n.ptr,head.count + 1))))
						break;
				}
			}			
		}
		//free the queueItem object
		delete h.ptr;

		return res;
	}
};

Ich weiß nicht ob ihr mein "atomicCAS8b" auch mal sehen wollt (ist GCC inline-Assembler)?

Ich habe diesen Code erstmal einfach geschrieben, habe ihn aber noch nicht getestet. Wollte nur erstmal wissen ob jemandem grobe Fehler (was die Templates betrifft) auffallen und ob das wirklich sicher ist.

[hustbaer]

Ne, das ist nicht sicher, da du - bis auf das "CAS" - keine atomaren Operationen verwendest.

Heisst: du musst auch das Lesen der atomicPtr Instanzen atomar machen, und natürlich mit den nötigen Barriers.

Und was sollen likely() und unlikely() sein? Optimierungs-Annotationen?

BTW: compiliert das überhaupt? Du nimmst da die Adresse einer Rvalue, was nicht erlaubt ist. Hast du überhaupt versucht es zu compilieren?

[FlashBurn]

hustbaer schrieb:

Ne, das ist nicht sicher, da du - bis auf das "CAS" - keine atomaren Operationen verwendest.

Heisst: du musst auch das Lesen der atomicPtr Instanzen atomar machen, und natürlich mit den nötigen Barriers.

Das Lesen muss (und kann auch nicht) atomar sein. Ich Vergleiche ja später nochmal die Werte und gucke ob die immernoch gleich sind, wenn sie es sind dann versuche ich sie in der Queue zu ändern (was ja atmor ist).

Das einzige was ich machen müsste, wäre dem Compiler per "volatile" zu sagen, das die Werte auch von Außen geändert werden können.

hustbaer schrieb:

Und was sollen likely() und unlikely() sein? Optimierungs-Annotationen?

Ja likely/unlikely sind Makros die dem Compiler sagen was wahrscheinlich eintritt.

hustbaer schrieb:

BTW: compiliert das überhaupt? Du nimmst da die Adresse einer Rvalue, was nicht erlaubt ist. Hast du überhaupt versucht es zu compilieren?

Kompiliert habe ich es noch nicht. Mir ging es erstmal nur um den Algorithmus.

Ich dachte das mit dem atomicPtr erzeugen geht, weil der wird ja auf dem Stack erzeugt und die Adresse von dem Objekt müsste ich auch bekommen können, aber wenn es nicht geht. Dann muss ich das nochmal ändern.

template <typename T>
class atomicPtr {
public:   
    T *ptr;
    uint32t count;

    atomicPtr(T *val)  : ptr(val), count(0) {}
    atomicPtr(T *val, uint32t init) : ptr(val), count(init) {}

    ~atomicPtr() {}

    atomicPtr<T>& operator=(const atomicPtr<T> &init) {
        ptr= init.ptr;
        count= init.count;

        return *this;
    }

    bool operator==(const atomicPtr<T> &other) {
        if(ptr == other.ptr && count == other.count)
            return true;
        else
            return false;
    }

    bool operator!=(const atomicPtr<T> &other) {
        return !(*this == other);
    }
};

template <typename T>
class queueItem {
public:
    atomicPtr<queueItem> next;
    T *obj;

    queueItem(T *val) : next(NULL), obj(val) {}

    ~queueItem() {}

    queueItem* operator new(uint32t size) {
        return queueAllocItem();
    }

    uint32t operator delete(queueItem *ptr) {
        return queueFreeItem(ptr);
    }
};

template <typename T>
class queue {
    atomicPtr<queueitem<T>> head;
    atomicPtr<queueItem<T>> tail;
    queueItem<T> dummyNode;
public:   
    queue() : head(&dummyNode), tail(&dummyNode) {}

    ~queue() {}

    bool enqueue(T *obj) {
        queueItem<T> *item;

        if(unlikely(!obj))
            return false;

        item= new queueItem<T>(obj);

        while(true) {
            atomicPtr<queueItem<T>> t= tail;
            atomicPtr<queueItem<T>> n= t.next;
            //look if t and the tail are still the same
            if(likely(t == tail)) {
                //look if the next pointer is null
                if(likely(n.ptr == NULL)) {
                    atomicPtr<queueItem<T>> tmp(item,n.count + 1);
                    //try to set the next ptr of the tail
                    if(likely(atomicCAS8b(&t.next,&n,&tmp)))
                        break;
                } else {
                    atomicPtr<queueItem<T>> tmp(n.ptr,n.count + 1);
                    //try to update the tail
                    atomicCAS8b(&tail,&t,&tmp);
                }
            }
        }

        atomicPtr<queueItem<T>> tmp(item,tail.count + 1);
        //try to update the tail
        atomicCAS(&tail,&t,&tmp);

        return true;
    }

    T* dequeue() {
        atomicPtr<queueItem<T>> h;
        T *res;

        while(true) {
            h= head;
            atomicPtr<queueItem<T>> t= tail;
            atomicPtr<queueItem<T>> n= h.next;
            //look if h and head are still the same
            if(likely(h == head)) {
                //look if head == tail, either queue is empty or we need to update tail
                if(unlikely(head == tail)) {
                    //queue is empty
                    if(unlikely(n.ptr == NULL))
                        return NULL;

                    atomicPtr<queueItem<T>> tmp(n.ptr,tail.count + 1);
                    //try to update tail
                    atomicCAS8b(&tail,&t,&tmp);
                } else {
                    atomicPtr<queueItem<T>> tmp(n.ptr,head.count + 1);
                    //get the object before someone changes it
                    res= next.ptr->obj;
                    //try to update the head
                    if(likely(atomicCAS8b(&head,&h,&tmp)))
                        break;
                }
            }           
        }
        //free the queueItem object
        delete h.ptr;

        return res;
    }
};

[Shade Of Mine]

Auf den ersten Blick sieht es OK aus. Aber bei lock free Algorithmen gibt es viele subtile Probleme.

Hier 2 Seiten fuer naehere Erklaerungen zu der lock free queue:
http://www.boyet.com/articles/LockfreeQueue.html
http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

PS:
bei drdobbs gab es sogar mal eine offiziell vorgestellte lock free queue die falsch war. Das hier ist der korrigierte Artikel: http://www.drdobbs.com/high-performance-computing/210604448

[FlashBurn]

Shade Of Mine schrieb:

Auf den ersten Blick sieht es OK aus. Aber bei lock free Algorithmen gibt es viele subtile Probleme.

Genau deswegen hatte ich den Algo hier gepostet Im Endeffekt ist es auch nur ein "nachprogrammierter" Algo, aber ich bin mir halt nicht sicher ob ich es auch hinbekommen habe.

Shade Of Mine schrieb:

Hier 2 Seiten fuer naehere Erklaerungen zu der lock free queue:
http://www.boyet.com/articles/LockfreeQueue.html
http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

Die kenne ich noch nicht, muss ich mir dann mal angucken. Danke!

Shade Of Mine schrieb:

PS:
bei drdobbs gab es sogar mal eine offiziell vorgestellte lock free queue die falsch war. Das hier ist der korrigierte Artikel: http://www.drdobbs.com/high-performance-computing/210604448

Habe ich auch gelesen.

[hustbaer]

FlashBurn schrieb:

hustbaer schrieb:

Ne, das ist nicht sicher, da du - bis auf das "CAS" - keine atomaren Operationen verwendest.

Heisst: du musst auch das Lesen der atomicPtr Instanzen atomar machen, und natürlich mit den nötigen Barriers.

Das Lesen muss (und kann auch nicht) atomar sein. Ich Vergleiche ja später nochmal die Werte und gucke ob die immernoch gleich sind, wenn sie es sind dann versuche ich sie in der Queue zu ändern (was ja atmor ist).

Doch, es kann atomar sein, und es muss sogar.

Warum es muss: weil du den gelesenen Zeiger dereferenzierst (t.next). Ohne atomare Leseoperation könntest du einen total ungültigen Zeigerwert lesen. Den dann zu dereferenzieren, bzw. auch nur in eine andere Variable zu kopieren, ist UB. Real wird das nicht vorkommen (zumindest auf den meisten CPUs nicht), wenn der Zeiger passend aligned ist (was sowieso voraussetzung für atomare Zugriffe ist). Allerdings verlässt man sich damit auf das Verhalten von bestimmten CPUs. Vom kommenden C++ Standard ist das soweit ich weiss nicht abgedeckt. (Von anderen Standards evtl. schon, also wenn deine Implementierung z.B. nur mit MSVC funktionieren soll, oder nur mit GCC und nur mit bestimmten CPUs, dann könnte es durchaus OK sein.)

Zum "wie" es geht: eine Möglichkeit ist CAS zu verwenden. Also in einer Schleife lesen, und dann mit CAS versuchen den selben Wert drüberzuschreiben, so lange bis CAS Erfolg meldet. Ist natürlich überhaupt nicht effizient. Andere Möglichkeiten sind je nach CPU verschieden. Bei amd64 CPUs reicht es beide Werte mit einem einzigen "mov" in ein Register zu laden (und von dort aus dann z.B. in die lokale Variable zu koieren). Andere CPUs haben u.U. spezielle Befehle dafür. Bzw. mit dem neuen Standard wird es auch ganz einfach über die entsprechenden atomic Funktionen gehen.

Und IMO ist auch eine "acuire" Barrier nötig, wobei ich mir da gerade nicht mehr so 100% sicher bin.

[FlashBurn]

hustbaer schrieb:

Warum es muss: weil du den gelesenen Zeiger dereferenzierst (t.next). Ohne atomare Leseoperation könntest du einen total ungültigen Zeigerwert lesen.

Das einzige was da schief gehen könnte, ist dass ich auf Speicher zugreife der schon freigegeben wurde. Sprich zwischen dem lesen/kopieren von tail und tail.next wurde das letzte Element entfernt und der Speicher wurde vom Betriebssystem freigegeben (ist also nicht mehr gemappt). Das ist aber durchaus ein reales Problem

hustbaer schrieb:

Zum "wie" es geht: eine Möglichkeit ist CAS zu verwenden. Also in einer Schleife lesen, und dann mit CAS versuchen den selben Wert drüberzuschreiben, so lange bis CAS Erfolg meldet. Ist natürlich überhaupt nicht effizient.

Wäre auch meine einzige Idee gewesen, aber ich denke mal bei der Performance die dabei rauskommt, ist man mit Locks wieder besser dran

hustbaer schrieb:

Bei amd64 CPUs reicht es beide Werte mit einem einzigen "mov" in ein Register zu laden (und von dort aus dann z.B. in die lokale Variable zu koieren).

Nein das geht nicht! Denn du kannst nur die 64bit Register nutzen wenn du im 64bit Modus (LongMode) bist, aber da sind die Pointer ja auch 64bit groß und schon hast du wieder das selbe Problem.

hustbaer schrieb:

Bzw. mit dem neuen Standard wird es auch ganz einfach über die entsprechenden atomic Funktionen gehen.

Da würde mich dann mal interessieren wie sie das realisieren wollen. Denn eigentlich ist es nicht möglich (ohne CAS) mehr als die Registerbreite atomor zu lesen/schreiben.

Bzw. ist das atomar auch gar nicht das Problem, sondern das man auf einen Speicherbereich zugreift, der schon längst nicht mehr da sein könnte. Wie man das jetzt aber lösen kann, muss ich nochmal drüber nachdenken.

hustbaer schrieb:

Und IMO ist auch eine "acuire" Barrier nötig, wobei ich mir da gerade nicht mehr so 100% sicher bin.

Wenn du mir verrätst was du mit einer "acquire" Barriere (du meinst bestimmt eine Memory-Barriere) meinst und warum die eventuell nötig ist?

[hustbaer]

FlashBurn schrieb:

hustbaer schrieb:

Warum es muss: weil du den gelesenen Zeiger dereferenzierst (t.next). Ohne atomare Leseoperation könntest du einen total ungültigen Zeigerwert lesen.

Das einzige was da schief gehen könnte, ist dass ich auf Speicher zugreife der schon freigegeben wurde.

Du kannst auch einen Zeiger lesen der aus zwei oder mehreren gültigen Werten zusammengesetzt ist. Angenommen ein Wert war 0x11111111 und ein anderer 0x22222222, dann kannst du z.B. 0x11112222 oder 0x22221111 lesen. Also nicht die Adresse eines Speicherbereichs der schon freigegeben wurde, sondern eine komplett ungültige Adresse.
Daher brauchst du eine atomare Operation zum Lesen.

FlashBurn schrieb:

Sprich zwischen dem lesen/kopieren von tail und tail.next wurde das letzte Element entfernt und der Speicher wurde vom Betriebssystem freigegeben (ist also nicht mehr gemappt). Das ist aber durchaus ein reales Problem

Das ist auch ein Problem, allerdings ein anderes. Kann man z.B. über Hazard-Pointer lösen. Ist allerdings einigermassen aufwendig.

FlashBurn schrieb:

hustbaer schrieb:

Bei amd64 CPUs reicht es beide Werte mit einem einzigen "mov" in ein Register zu laden (und von dort aus dann z.B. in die lokale Variable zu koieren).

Nein das geht nicht! Denn du kannst nur die 64bit Register nutzen wenn du im 64bit Modus (LongMode) bist, aber da sind die Pointer ja auch 64bit groß und schon hast du wieder das selbe Problem.

Hm. Gibt es nicht einen Befehl mit dem man einen 64 Bit Wert in zwei 32 Bit Register laden kann? Denke schon.

FlashBurn schrieb:

Bzw. ist das atomar auch gar nicht das Problem, sondern das man auf einen Speicherbereich zugreift, der schon längst nicht mehr da sein könnte. Wie man das jetzt aber lösen kann, muss ich nochmal drüber nachdenken.

Atomares Lesen ist wie gesagt sehr wohl nötig. Zumindest musst du sicher stellen dass die Zeiger selbst atomar gelesen werden, was auch nicht vom C++ Standard garantiert wird. Und das lässt sich auf jeden Fall machen, da ein Zeiger ja nicht breiter als ein Register ist. Bei amd64/x86 reicht wieder ein einfaches "mov" wenn das Alignment passt.

FlashBurn schrieb:

hustbaer schrieb:

Und IMO ist auch eine "acuire" Barrier nötig, wobei ich mir da gerade nicht mehr so 100% sicher bin.

Wenn du mir verrätst was du mit einer "acquire" Barriere (du meinst bestimmt eine Memory-Barriere) meinst und warum die eventuell nötig ist?

Upps, hab ich das q vergessen
Naja, mit Acquire-Barrier meine ich, du brauchst was, was dir garantiert, dass du keine alten Werte liest (nicht alle CPUs haben synchronisierte Caches wie x86). Sonst könnte es nämlich trotz Hazard-Pointern (oder wie auch immer du sicherstellst dass du keine freigegebenen Nodes liest) passieren, dass du auf freigegebenen Speicher zugreifst, weil du einen Wert liest, der schon lange nicht mehr aktuell ist.

[FlashBurn]

hustbaer schrieb:

Du kannst auch einen Zeiger lesen der aus zwei oder mehreren gültigen Werten zusammengesetzt ist. Angenommen ein Wert war 0x11111111 und ein anderer 0x22222222, dann kannst du z.B. 0x11112222 oder 0x22221111 lesen. Also nicht die Adresse eines Speicherbereichs der schon freigegeben wurde, sondern eine komplett ungültige Adresse.
Daher brauchst du eine atomare Operation zum Lesen.

Sag das doch gleich Du meinst also (auf x86 bezogen) unaligned Lesevorgänge?! Die kommen in meinem Fall nicht vor und sollten auch nicht vorkommen können (ein Alignment an 4 sollte eigentlich immer der Fall sein (Ausnahme, Strings und Byte/DByte-Arrays).

hustbaer schrieb:

Das ist auch ein Problem, allerdings ein anderes. Kann man z.B. über Hazard-Pointer lösen. Ist allerdings einigermassen aufwendig.

Naja, das sehe ich als das eigentliche Problem an und von den Algos die ich so im Internet gefunden habe, scheint auch keiner sich großartig Gedanken darüber zu machen (es wird nur immer geschrieben das man ohne einen GC Probleme mit dem Speicher bekommt, aber die Algos werden selbst für C++ als funktionierend hingestellt).

hustbaer schrieb:

Hm. Gibt es nicht einen Befehl mit dem man einen 64 Bit Wert in zwei 32 Bit Register laden kann? Denke schon.

Also eigentlich kann ich Assembler und außer CAS und SSE Befehle (welche aber auch rausfallen und ich mir nicht sicher bin ob die bei 64bit atomar sind, aufjeden Fall muss dann die Adresse an 8 aligned sein) gibt es keine Befehle für sowas.

[hustbaer]

FlashBurn schrieb:

hustbaer schrieb:

Du kannst auch einen Zeiger lesen der aus zwei oder mehreren gültigen Werten zusammengesetzt ist. Angenommen ein Wert war 0x11111111 und ein anderer 0x22222222, dann kannst du z.B. 0x11112222 oder 0x22221111 lesen. Also nicht die Adresse eines Speicherbereichs der schon freigegeben wurde, sondern eine komplett ungültige Adresse.
Daher brauchst du eine atomare Operation zum Lesen.

Sag das doch gleich Du meinst also (auf x86 bezogen) unaligned Lesevorgänge?! Die kommen in meinem Fall nicht vor und sollten auch nicht vorkommen können (ein Alignment an 4 sollte eigentlich immer der Fall sein (Ausnahme, Strings und Byte/DByte-Arrays).

So ungefähr. Ich meine was was bei x86 eigentlich nicht vorkommen kann, da die Objekte ja sowieso aligned sein müssen, sobald man irgendwo CAS verwenden will. Bei anderen CPUs sind aligned reads aber vielleicht nicht automatisch atomar. Und da an der Stelle mMn. wie bereits gesagt ein Load mit Acquire Semantik nötig ist, kann man gleich eine entsprechende Load_Acquire Funktion definieren und verwenden. Da hier "single width" reicht, ist das auch relativ einfach:

uint32_t Load_Acquire(uint32_t volatile* p)
{
    return *p; // ausreichend bei MSVC mit x86 und amd64. Mit anderen Compilern/CPUs muss man u.u. intrinsics/inline asm verwenden
}

void* Load_Acquire(void* volatile* p)
{
    return reinterpret_cast<void*>(Load_Acquire(reinterpret_cast<uint32_t volatile*>(p)));
}

//atomicPtr<queueItem<T>> t= tail;
atomicPtr<queueItem<T>> t;
t.ptr = Load_Acquire(&tail.ptr);
t.count = Load_Acquire(&tail.count);

FlashBurn schrieb:

hustbaer schrieb:

Das ist auch ein Problem, allerdings ein anderes. Kann man z.B. über Hazard-Pointer lösen. Ist allerdings einigermassen aufwendig.

Naja, das sehe ich als das eigentliche Problem an und von den Algos die ich so im Internet gefunden habe, scheint auch keiner sich großartig Gedanken darüber zu machen (es wird nur immer geschrieben das man ohne einen GC Probleme mit dem Speicher bekommt, aber die Algos werden selbst für C++ als funktionierend hingestellt).

Sind für mich beides "eigentliche" Probleme, bloss das eine ist relativ einfach zu lösen (s.o.)

FlashBurn schrieb:

hustbaer schrieb:

Hm. Gibt es nicht einen Befehl mit dem man einen 64 Bit Wert in zwei 32 Bit Register laden kann? Denke schon.

Also eigentlich kann ich Assembler und außer CAS und SSE Befehle (welche aber auch rausfallen und ich mir nicht sicher bin ob die bei 64bit atomar sind, aufjeden Fall muss dann die Adresse an 8 aligned sein) gibt es keine Befehle für sowas.

Sieht so aus als hättest du Recht (hab ein wenig gegoogelt). SSE oder dergleichen müsste OK sein was "atomar" angeht, allerdings müsste ich mir erstmal die genauen Specs durchlesen was memory ordering etc. angeht -- für manche Befehle gelten ja nicht die strengen ordering Regeln die x86/amd64 sonst grossteils verwendet (z.B. die "string" Befehle movs und dergleichen sind glaube ich ausgenommen). Aber da atomare "double width" Loads ja nicht nötig sind, ist es wohl einfacher und sinnvoller es mit "single with" Loads zu machen.

EDIT

p.S.: für Lesen mit CAS braucht man natürlich gar keine Retry-Schleife, da hab ich Unsinn geschrieben. CAS liefert bei x86 ja die Werte zurück die vor dem eventuellen Tausch im Ziel gestanden haben. Ein einziges CAS(&target, 0, 0) reicht also. Bleibt trotzdem ineffizient, da CAS bekanntermassen viel langsamer ist als ein oder zwei normale Loads.

[FlashBurn]

hustbaer schrieb:

für Lesen mit CAS braucht man natürlich gar keine Retry-Schleife, da hab ich Unsinn geschrieben. CAS liefert bei x86 ja die Werte zurück die vor dem eventuellen Tausch im Ziel gestanden haben. Ein einziges CAS(&target, 0, 0) reicht also. Bleibt trotzdem ineffizient, da CAS bekanntermassen viel langsamer ist als ein oder zwei normale Loads.

Das Problem mit CAS (in dem Zusammenhang mit paralleler Ausführung) ist, das du dir nur sicher sein kannst das der ganze Spaß auch atomar ist, wenn du ein Lock-Präfix davor setzt und nach den Infos die ich gefunden habe, wird grundsätzlich auch ein Lock-Write auf den Memorybus geschickt (auch wenn nichts geändert wird) und damit "zerstörst" du den Cacheinhalt in anderen CPUs. Zumal das Aktualisieren der Caches auch nicht unterschätzt werden sollte.

Hast du (oder jemand) denn eine Idee wie man das Problem, dass man auf nicht mehr vorhandenen Speicher zugreift, umgehen kann ohne das man Hazard-Pointers nutzt?

[hustbaer]

FlashBurn schrieb:

hustbaer schrieb:

für Lesen mit CAS braucht man natürlich gar keine Retry-Schleife, da hab ich Unsinn geschrieben. CAS liefert bei x86 ja die Werte zurück die vor dem eventuellen Tausch im Ziel gestanden haben. Ein einziges CAS(&target, 0, 0) reicht also. Bleibt trotzdem ineffizient, da CAS bekanntermassen viel langsamer ist als ein oder zwei normale Loads.

Das Problem mit CAS (in dem Zusammenhang mit paralleler Ausführung) ist, das du dir nur sicher sein kannst das der ganze Spaß auch atomar ist, wenn du ein Lock-Präfix davor setzt und nach den Infos die ich gefunden habe, wird grundsätzlich auch ein Lock-Write auf den Memorybus geschickt (auch wenn nichts geändert wird) und damit "zerstörst" du den Cacheinhalt in anderen CPUs. Zumal das Aktualisieren der Caches auch nicht unterschätzt werden sollte.

Ja, ich hab ja geschrieben "CAS bekanntermassen viel langsamer"
Hab was von 200~~400 Zyklen in Erinnerung (Mit lock Prefix auf nem Core 2 Quad ohne dass zwei Threads sich um die Cacheline streiten, also idealfall. Und die Zahl ist aus dem Gedächtnis, aber die Grössenordnung müsste hinkommen).

Wobei... wer sagt denn dass der Load-Teil des CAS nicht auch ohne lock Prefix atomar ist? Müsste er IMO sein. Und ohne Lock Prefix sollte das durchaus akzeptabel schnell sein.

EDIT: man müsste natürlich einen Vergleichswert verwenden, der nie vorkommen kann, damit sicher gestellt ist, dass nie geschrieben wird. Und... ist lock bei cmpxchg8b nicht sowieso implizit? Hmmm... /EDIT

Hast du (oder jemand) denn eine Idee wie man das Problem, dass man auf nicht mehr vorhandenen Speicher zugreift, umgehen kann ohne das man Hazard-Pointers nutzt?

Ich nicht (jemand vielleicht schon ).

D.h. der Teil wo man auf nichtmehr vorhandenen Speicher zugreift ist noch einfach: man gibt die Nodes halt nicht frei, sondern steckt sie in eine (per-thread) Free-List. Bloss ist es ja vermutlich genau so ein Problem, wenn sich der Inhalt einer Node (Next-Pointer) einfach so ändert, weil sie (u.U. in einer ganz anderen Liste) wiederverwendet wurde.

[FlashBurn]

hustbaer schrieb:

Wobei... wer sagt denn dass der Load-Teil des CAS nicht auch ohne lock Prefix atomar ist? Müsste er IMO sein. Und ohne Lock Prefix sollte das durchaus akzeptabel schnell sein.

EDIT: man müsste natürlich einen Vergleichswert verwenden, der nie vorkommen kann, damit sicher gestellt ist, dass nie geschrieben wird. Und... ist lock bei cmpxchg8b nicht sowieso implizit? Hmmm... /EDIT

Das mit dem lock, da scheiden sich die Geister Jeder sagt was anderes, aber ich kann es mir so erklären:

XCHG ist immer "gelockt" und wenn du bei CMPXCHG kein LOCK verwendest dann ist nur der XCHG Teil atomar, verwendest du bei CMPXCHG LOCK, dann ist das CMP und der XCHG atomar!

Naja, ich hoffe ja noch das ich entweder eine Erleuchtung habe oder aber noch wirklich funktionierend Code finde.

[FlashBurn]

Den Code muss ich mir nochmal richtig angucken und ändern. Denn beim Entfernen ist noch mind. 1 Fehler drin (ich packe ja in die leere Queue ein Dummy-Element, aber anstand beim Entfernen das erste wirkliche Element zu entfernen entferne ich jedes Mal das Dummy-Element und ändere aber den Head.ptr nicht ).

Auch muss ich das Dummy-Element mit new erzeugen damit ich es überhaupt freigeben kann! Denn das wird ja gemacht damit immer ein Element in der Queue ist und Head/Tail nicht ins leere zeigen.

Das andere Problem bleibt aber, meiner Meinung nach, bestehen.

[FlashBurn]

Also Hazard-Pointers sind eine Lösung um die Probleme mit dem Memory Management (wenn man keinen GC hat) zu lösen.

Am Bsp. der Queue ist ja das Problem, dass man eventuell einen Pointer dereferenziert (also liest) von einem Speicherbereich der schon wieder weg (im Sinne von geunmappt, dem OS zurückgegeben) ist und man eine Exception auslöst. Wenn ein Thread nicht unterbrochen werde kann solange er an der Queue arbeitet, sollte das Problem ja theoretisch nicht auftauchen können (da in dem speziellen Fall der Speicher auch nicht so schnell freigegeben wird, da dafür doch ein wenig Code von nöten ist (ca. 100 - 1000 Opcodes).

Also noch mal kurz, würde die Queue (mit dem Update-Tag wie im ersten Post ersichtlich) funktionieren, wenn man davon ausgeht das der Code nicht unterbrochen wird?

[FlashBurn]

Noch eine Frage zu dem scheinbar "einfachen" lock-free Queue Algo wie er oft benutzt wird.

Mir ist (das glaube ich zumindest) eine Situation eingefallen, wo dieser Algo selbst mit einem Garbage-Collector schief gehen kann.

Das Problem ist immernoch, dass man einen Pointer dereferenziert, der auf Speicher zeigt, der nicht mehr vorhanden ist.
Wäre es, theoretisch, nicht möglich das ich die Adresse eines Queue-Elements in ein CPU Register lade, der Thread wird darauf unterbrochen (vom Scheduler) und ein anderer Thread löscht jetzt genau dieses Element (bzw. entfernt es aus der Liste). Da der Code, der unterbrochen wurde, in einem Thread mit sehr niedriger Priorität lief und dummerweise eine Weile nicht dran kommt, kommt der Garbage-Collector mal wieder zum Laufen, baut seinen Graphen auf (um festzustellen welche Objekte endgültig freigegeben werden können) und gibt das Element frei, weil die Adresse ja in einem CPU Register steht und nicht in einer Speichervariable.

Auch wenn dieser Fall sehr unwahrscheinlich ist, ist er doch möglich und der Code damit, meiner Meinung nach, auch mit einen Garbage-Collector nicht sicher!

[hustbaer]

Der GC inspiziert normalerweise die Register (und Stacks) von laufenden Threads.
Und wenn nicht, dann ist der GC kaputt, nicht der Algorithmus.

[FlashBurn]

hustbaer schrieb:

Der GC inspiziert normalerweise die Register (und Stacks) von laufenden Threads.

Wenn du mir noch verrätst wie er das macht (das mit den Registern)? Denn dazu müsste er an den KernelSpace-Stack ran (was nicht geht, ohne das der GC im KernelSpace läuft) und er müsste noch den genauen Aufbau des Stacks kennen (ohne den er nicht weiß was ein Register ist oder irgendetwas anderes).

[hustbaer]

Bei "managed" Sprachen geht es relativ einfach: bevor ein Thread den "managed" Mode verlässt, sorgt er einfach dafür, dass alle Referenzen auf Objekte die er in Registern hält vom GC gefunden werden können. Dazu reicht es z.B. schon wenn der Thread vor dem Wechsel alle Register auf den Stack pusht.

Und vor dem Wechsel zurück in den "managed" Mode prüft der Thread ob gerade eine Collection läuft, und wenn ja, legt er sich schlafen bis die Collection abgeschlossen ist.
(Threads werden normalerweise nur im "managed" Mode angehalten, Threads die gerade "unmanaged" laufen dürfen gerne weiter laufen)

Wie ein GC für "unmanaged" Sprachen das macht weiss ich nicht. Eine Möglichkeit wäre einfach so lange zu warten, bis alle Threads wieder im Usermode laufen. Wobei das natürlich auch ein Problem ist, denn man hat ja oft genug Threads die sehr sehr lange im Kernelmode auf etwas warten - u.U. so lange bis das Programm beendet wird.

Bzw. ich bin mir nichtmal sicher ob es überhaupt ein Problem ist - werden die Usermode Registerwerte nicht beim Wechsel in den Kernelmode noch am Usermode-Stack abgelegt, und sind damit für den GC lesbar?

Was den Aufbau des Stacks angeht: GCs für "unmanaged" Sprachen sind meist nicht exakt sondern konservativ. D.h. der GC nimmt einfach bei allem was am Stack rumliegt an dass es eine Referenz bzw. ein "innerer Zeiger" ist.

Und bei "managed" Sprachen kann der GC wissen welche Teile des Stacks Referenzen sind und welche nicht - der JITer kann ja die dazu nötigen Daten in diverse Tabellen schreiben.

[FlashBurn]

Das ist so ziemlich das was ich mir gedacht habe. Die Register werden auf dem KernelSpace-Stack gespeichert.

Die GC die ich z.B. für C++ kenne, sind halt konservativ und leaken im Endeffekt Speicher, aber wie es mit dieser Sache aussieht weiß ich gar nicht, müsste ich mal nachgucken, aber ich bezweifle, dass das bedacht wurde.

Heißt Managed-Sprache eigentlich grundsätzlich VM (JIT-Compiler)?