Threadsichere, nicht-blockierende Variablen

[Walter T. (nicolas)]

Guten Morgen,

es ist Freitagmorgen und ich habe gerade wieder eine Denkblockade bei 
einem Problem, das wohl im ersten Semesters eines Informatikstudiums 
verordnet sein sollte.

Ich will eine große, nicht-atomar änderbare Variable nicht-blockierend 
von einer langsamen Hauptschleife konsistent in eine schnelle ISR 
bringen.

Mein Ansatz:

/* Globale Variablen */
typedef struct InputBuffer_s
{
    int64_t nonAtomicVariable0;
    int64_t nonAtomicVariable1;
}
InputBuffer_t;

InputBuffer_t InputBuffer[2] = {[0] = {.nonAtomicVariable0 = 0, .nonAtomicVariable1 = 1}};
InputBuffer_t *ValidBuffer = &InputBuffer[0];



/* Funktionsdeklarationen */
void doSomeFastStuffWith(int64_t var);
void doOtherFastStuffWith(int64_t var);
int64_t doALittleBitSimplerCalculation(void);
int64_t doSomeMassiveCalculation(void);



/* Langsame Hauptschleifenfunktion */
void mainloop(void)
{
    InputBuffer_t LocalBuffer;

    LocalBuffer.nonAtomicVariable0 = doSomeMassiveCalculation();
    LocalBuffer.nonAtomicVariable1 = doALittleBitSimplerCalculation();


    /* Puffer-Tausch */
    if( ValidBuffer == &InputBuffer[0] )
    {
        InputBuffer[1] = LocalBuffer;
        ValidBuffer = &InputBuffer[1];
    }
    else if( ValidBuffer == &InputBuffer[1] )
    {
        InputBuffer[0] = LocalBuffer;
        ValidBuffer = &InputBuffer[0];
    }
    else
    {
        assert( false );
    }
}



/* ISR wird pro Hauptschleifendurchlauf viele Male aufgerufen */
void ISR(void)
{
    InputBuffer_t LocalBuffer = *ValidBuffer;

    doSomeFastStuffWith(LocalBuffer.nonAtomicVariable1);
    doOtherFastStuffWith(LocalBuffer.nonAtomicVariable0);
}

Habe ich etwas wichtiges übersehen, oder benötige ich wirklich vier 
Kopien davon, wenn ich nicht-blockierend arbeiten will und die ISR immer 
konsistente Daten benötigt?

[Dunno.. (Gast)]

Wie fängst du denn bei deinem vorgehen ab dass die ist Eintritt in dem 
Moment wo valid Buffer geändert werden soll?

Meiner Meinung nach kann's dir da passieren dass die isr trotzdem noch 
die alten Daten verarbeitet.

[Walter T. (nicolas)]

Dunno.. schrieb:
> Meiner Meinung nach kann's dir da passieren dass die isr trotzdem noch
> die alten Daten verarbeitet.

Alt ist ja nicht schlimm. Hauptsache die Daten sind nicht inkonsistent, 
d.h.

1. alle Daten, die die ISR bekommt passen zueinander und
2. es werden nie neuere Daten durch alte überschrieben.

[Oliver S. (oliverso)]

dosomeFastStuffWith(LocalBuffer);

call by value->noch eine Kopie ;)


Ich verstehe deine Frage so:

doSomeMassiveCalculation und doALittleBitSimplerCalculation erzeugen die 
Daten in der mainloop, unabhängig von einem alten Datensatz (!!!).

dosomeFastStuffWith benutzt die Daten, ändert sie aber nicht.

In dem Fall reicht doch InputBuffer mit zwei Feldern, mit atomarem swap 
von ValidBuffer und WorkBuffer - pointern, ganz ohne Kopie der 
Datensätze.

Oliver

[Thomas W. (goaty)]

Du brauchst auf jeden Fall eine Mutex um den Puffertausch zu locken, 
denke ich.

Oder mal sehen was std::atomic library zu bieten hat.

[Walter T. (nicolas)]

Oliver S. schrieb:
> dosomeFastStuffWith(LocalBuffer);
>
> call by value->noch eine Kopie ;)

Ich habe das Beispiel im Eröffnungsbeitrag mal angepasst, um es weniger 
missverständlich zu machen.

Oliver S. schrieb:
> Ich verstehe deine Frage so:
>
> doSomeMassiveCalculation und doALittleBitSimplerCalculation erzeugen die
> Daten in der mainloop, unabhängig von einem alten Datensatz (!!!).
>
> dosomeFastStuffWith benutzt die Daten, ändert sie aber nicht.

Genau.

Oliver S. schrieb:
> In dem Fall reicht doch InputBuffer mit zwei Feldern, mit atomarem swap
> von ValidBuffer und WorkBuffer - pointern, ganz ohne Kopie der
> Datensätze.

Stimmt. mainloop() kann mir ja den aktiven Puffer nicht überschreiben, 
solange die ISR läuft. Es ist also nur eine Frage der Geschwindigkeit, 
ob es schneller ist, eine Kopie des Structs zu machen oder in einem 
veränderlichen Speicherbereich mit festen Offsets herumzuzeigern.

Gibt es darüber Daumenregeln, oder hilft nur profilen?

So sähe das aus:

/* Langsame Hauptschleifenfunktion */
void mainloop1(void)
{
    static InputBuffer_t *OutBuffer = &InputBuffer[1];

    OutBuffer->nonAtomicVariable0 = doSomeMassiveCalculation();
    OutBuffer->nonAtomicVariable1 = doALittleBitSimplerCalculation();


    /* Puffer-Tausch */
    if( ValidBuffer == &InputBuffer[0] )
    {
        OutBuffer =   &InputBuffer[0];
        ValidBuffer = &InputBuffer[1];
    }
    else if( ValidBuffer == &InputBuffer[1] )
    {
        OutBuffer =   &InputBuffer[1];
        ValidBuffer = &InputBuffer[0];
    }
    else
    {
        assert( false );
    }
}



/* ISR wird pro Hauptschleifendurchlauf viele Male aufgerufen */
void ISR1(void)
{
    InputBuffer_t *Buffer = ValidBuffer;

    doSomeFastStuffWith(Buffer->nonAtomicVariable1);
    doOtherFastStuffWith(Buffer->nonAtomicVariable0);
}

[Thomas W. (goaty)]

Du mußt aber sicher sein daß

  OutBuffer =   &InputBuffer[0];
  ValidBuffer = &InputBuffer[1];

nicht unterbrochen wird, sonst hast du da einen halben Zustand.
Selbst

  ValidBuffer = &InputBuffer[1];

ist ja erstmal unterbrechbar, da du ja nicht weißt aus welchen 
Instructions sich das im Maschinencode zusammensetzt.

[Walter T. (nicolas)]

Thomas W. schrieb:
> Du mußt aber sicher sein daß
>
>   OutBuffer =   &InputBuffer[0];
>   ValidBuffer = &InputBuffer[1];
>
> nicht unterbrochen wird, sonst hast du da einen halben Zustand.

Verstehe ich nicht. mainloop() wird in Outbuffer nichts mehr 
hineinschreiben, bevor nicht Validbuffer geändert wurde.

Thomas W. schrieb:
> welbst
>
>   ValidBuffer = &InputBuffer[1];
>
> ist ja erstmal unterbrechbar, da du ja nicht weißt aus welchen
> Instructions sich das im Maschinencode zusammensetzt.

Stimmt. In meinem Fall ist aber praktischerweise Maschinenwortbreite == 
Zeigerbreite (Cortex M4). Ich gehe also davon aus, dass ValidBuffer nie 
auf etwas Ungültiges zeigt.

[Thomas W. (goaty)]

Ah ok, ich dachte da sind evtl noch mehr Threads die da arbeiten, dann 
wirds schon passen.

[Walter T. (nicolas)]

Thomas W. schrieb:
> Ah ok, ich dachte da sind evtl noch mehr Threads die da arbeiten, dann
> wirds schon passen.

Nanu? Ich hätte gesagt: Für jede Kommunikation zwischen je zwei 
"Threads" brauche ich je eine unabhängige Austauschvariable pro 
Richtung. Wobei letztere unterschiedliche behandelt werden müssen, je 
nachdem wer wen unterbrechen kann.





Walter T. schrieb:
> Es ist also nur eine Frage der Geschwindigkeit,
> ob es schneller ist, eine Kopie des Structs zu machen oder in einem
> veränderlichen Speicherbereich mit festen Offsets herumzuzeigern.
>
> Gibt es darüber Daumenregeln, oder hilft nur profilen?

Gibt es Daumenregeln, ob das Kopieren eines structs oder der Zugriff auf 
jedes Element per Zeiger schneller ist, wenn die Adresse nicht fest und 
das Ziel volatile ist?

(Edit: letzteres habe ich im Eröffnungspost tatsächlich vergessen)

[Heiko L. (zer0)]

Ich will noch anmerken: Das geht alles nicht.
Ohne atomics (oder zumindest Speicherbarrieren) gibt es keine Garantie, 
in welcher Reihenfolge da irgendetwas geschrieben wird. Interrupts kennt 
der Compiler nicht - interessieren also auch nicht.
Also ob der Pointer-Write echt vor dem Datenwrite kommt entscheidet so 
irgendein Optimierungsalgorithmus.

[Walter T. (nicolas)]

Heiko L. schrieb:
> Pointer-Write echt vor dem Datenwrite kommt entscheidet so
> irgendein Optimierungsalgorithmus.

Wie ich schon schrieb: Im Eröffnungsthread das "volatile" vergessen. 
Zwei "volatile"-Schreibzugriffe dürfen nicht vertauscht werden.

volatile InputBuffer_t InputBuffer[2] = {[0] = {.nonAtomicVariable0 = 0, .nonAtomicVariable1 = 1}};
volatile InputBuffer_t *ValidBuffer = &InputBuffer[0];

[Heiko L. (zer0)]

Walter T. schrieb:
> Heiko L. schrieb:
>> Pointer-Write echt vor dem Datenwrite kommt entscheidet so
>> irgendein Optimierungsalgorithmus.
>
> Wie ich schon schrieb: Im Eröffnungsthread das "volatile" vergessen.
> Zwei "volatile"-Schreibzugriffe dürfen nicht vertauscht werden.

Das nicht, aber non-volatile writes können daran vorbei wandern. Das 
müsste schon eine direkt Daten-Dependency verhindern.

Edit: ach so - ich sehe.
In dem Fall fiele mir noch ein, dass man sichergehen müsste, dass der 
Pointer-Write atomar ist.

[Peter D. (peda)]

Wozu vor der Zuweisung erst noch vergleichen?
Das kostet doch ein Lesen, einen Vergleich und einen Sprung zusätzlich.

Wie schon geschrieben wurde, kapsele es atomar und gut is.
Sachen sollte man nicht unnötig verkomplizieren.

[Heiko L. (zer0)]

Sehr interessanter Vortrag übrigens rund um solche Problematiken sogar 
noch mit atomics:
https://www.youtube.com/watch?v=IB57wIf9W1k

These: Der Compiler könnte auch erstmal zwei Schleifendurchläufe 
durchrechnen und dann am Schluss ein paar mehr volatile writes in Folge 
machen oder die Berechnung des lokalen Buffers mit den volatilen writes 
interleaven.

[Walter T. (nicolas)]

Peter D. schrieb:
> Wozu vor der Zuweisung erst noch vergleichen?
> Das kostet doch ein Lesen, einen Vergleich und einen Sprung zusätzlich.
>
> Wie schon geschrieben wurde, kapsele es atomar und gut is.
> Sachen sollte man nicht unnötig verkomplizieren.

Das verstehe ich nicht. Wie würdest Du den Puffer-Tausch realisieren? 
Oder meinst Du beide Puffer hintereinander mit einem Flag?

#define BUFFERDEFAULT {.nonAtomicVariable0 = 0, .nonAtomicVariable1 = 1}
volatile InputBuffer_t InputBuffer2 = BUFFERDEFAULT;
volatile bool bufferValid2 = false;



/* Langsame Hauptschleifenfunktion */
void mainloop2(void)
{
    InputBuffer_t OutBuffer;

    OutBuffer.nonAtomicVariable0 = doSomeMassiveCalculation();
    OutBuffer.nonAtomicVariable1 = doALittleBitSimplerCalculation();

    /* Puffer schreiben */
    bufferValid2 = false;
    InputBuffer2 = OutBuffer;
    bufferValid2 = true;
}



/* ISR wird pro Hauptschleifendurchlauf viele Male aufgerufen */
void ISR2(void)
{
    static InputBuffer_t Buffer = BUFFERDEFAULT;

    if( bufferValid2 )
    {
        InputBuffer_t Buffer = InputBuffer2;
    }

    doSomeFastStuffWith(Buffer.nonAtomicVariable1);
    doOtherFastStuffWith(Buffer.nonAtomicVariable0);
}

Dann käme die ISR ja nur zu neuen Daten, wenn die Hauptschleife langsam 
genug ist, dass die Schreibfunktion nur einen kleinen Anteil hat.

[Peter D. (peda)]

Walter T. schrieb:
> Das verstehe ich nicht. Wie würdest Du den Puffer-Tausch realisieren?
> Oder meinst beide Puffer hintereinander mit einem Flag?

Vergiß es, ich hatte das mit den Pointern übersehen.

[W.S. (Gast)]

Walter T. schrieb:
> Ich will eine große, nicht-atomar änderbare Variable nicht-blockierend
> von einer langsamen Hauptschleife konsistent in eine schnelle ISR
> bringen.

Eine Variable kannst du nicht irgendwo hin bringen. So etwas geht 
grundsätzlich NICHT.

Was du kannst, ist dir ein Agreement ausdenken, mit dessen Hilfe du den 
Zugriff mehrerer unabhängiger Programmteile auf besagte Variable 
geregelt kriegst.

Wie du das im einzelnen tust, ist deine Sache und hängt vom dahinter 
steckenden Problem ab.

Aber im Allgemeinen tut man das so, daß es irgend einen Kenner gibt, der 
atomar änderbar ist und den nur eine einzige "Master"-Instanz schreiben 
darf. Zum Beispiel ein "IsValid" Bit oder bool im Datensatz.

Alle anderen Instanzen dürfen den Kenner nur lesend zur Kenntnis nehmen 
und allenfalls in einem anderen Antwortkenner (der dann ihnen gehört) 
mitteilen, wie sie auf den gelesenen Kenner reagiert haben. Sowas kann 
auch in Form von System-Botschaften erfolgen (ereignisgsteuerte Abläufe)

W.S.

[Walter T. (nicolas)]

W.S. schrieb:
> Eine Variable kannst du nicht irgendwo hin bringen.

Danke für die präzise Klarstellung.

[Wilhelm M. (wimalopaan)]

Dein Problem ist doch das atomare Vertauschen zweier Zeigervariablen, 
und zwar ausschließlich von einem "thread" (main). Der andere (ISR) 
vertausch nicht. Und nur der vertauschende kann unterbrochen werden.

Dann brauchst Du nur ein atomares swap der Zeigervariablen (in main).