C Ringspeicher

[verwirrt (Gast)]

Hallo,

ich weiß dass es zu dem Thema schon unzählige Threads gibt. eigentlich 
ist ein Ringbuffer ja auch eine einfache Sache aber irgendwie habe ich 
gerade ein kleines Problem und komme nicht auf die Lösung.

Ich habe mir dazu auch den Artikel 
https://www.mikrocontroller.net/articles/FIFO#FIFO_als_Bibliothek 
angesehen.
und das erste Codebeispiel entspricht ziemlich genau dem was ich auch 
selber geschrieben habe.

hier die Stelle aus dem Artikel

#define BUFFER_FAIL     0
#define BUFFER_SUCCESS  1

#define BUFFER_SIZE 23

struct Buffer {
  uint8_t data[BUFFER_SIZE];
  uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt
  uint8_t write; // zeigt immer auf leeres Feld
} buffer = {{}, 0, 0};

//
// Stellt 1 Byte in den Ringbuffer
//
// Returns:
//     BUFFER_FAIL       der Ringbuffer ist voll. Es kann kein weiteres Byte gespeichert werden
//     BUFFER_SUCCESS    das Byte wurde gespeichert
//
uint8_t BufferIn(uint8_t byte)
{
  //if (buffer.write >= BUFFER_SIZE)
  //  buffer.write = 0; // erhöht sicherheit

  if ( ( buffer.write + 1 == buffer.read ) ||
       ( buffer.read == 0 && buffer.write + 1 == BUFFER_SIZE ) )
    return BUFFER_FAIL; // voll

  buffer.data[buffer.write] = byte;

  buffer.write++;
  if (buffer.write >= BUFFER_SIZE)
    buffer.write = 0;

  return BUFFER_SUCCESS;
}

//
// Holt 1 Byte aus dem Ringbuffer, sofern mindestens eines abholbereit ist
//
// Returns:
//     BUFFER_FAIL       der Ringbuffer ist leer. Es kann kein Byte geliefert werden.
//     BUFFER_SUCCESS    1 Byte wurde geliefert
//    
uint8_t BufferOut(uint8_t *pByte)
{
  if (buffer.read == buffer.write)
    return BUFFER_FAIL;

  *pByte = buffer.data[buffer.read];

  buffer.read++;
  if (buffer.read >= BUFFER_SIZE)
    buffer.read = 0;

  return BUFFER_SUCCESS;
}

Nun aber zu der Frage, da beim

  - Lesen des Speichers immer auf read==write (dann leer)

  - beim Schreiben auf write+1=read (Vereinfach dargestellt, wegen dem 
Überlauf, dann voll)

abgefragt wird, entsteht immer eine Zelle in die nicht geschrieben 
werden kann.

bsp. read steht auf 5, write auf 4 es soll geschrieben werden, was aber 
nicht ausgeführt wird da write+1 = read ist, somit kann die leere stelle 
4 nicht beschrieben werden.

Wie kann man alle Stellen verwenden?
Bei nur einem Byte des Speichers wäre mir das relativ egal. aber da es 
darum geht, jeweils eine struct mit viel speicher zu verwenden, so ist 
es schon interessant wenn ich einen Speicher von z.B. 3 
"Speicherplätzen" benötige ob ich dann wegen der eigenheit speicher für 
4 zur Verfügung stellen muss.

Vielen Dank

[MaWin (Gast)]

verwirrt schrieb:
> Wie kann man alle Stellen verwenden?

Die Belegung nicht über den Zeigervergleich machen, sondern separat 
mitzählen, wie viele Elemente belegt sind.

[Jim M. (turboj)]

verwirrt schrieb:
> Wie kann man alle Stellen verwenden?

Gar nicht.

Das ist der Preis den man beim Ringpuffer für die Unabhängigkeit des 
Lesers und Schreibers zahlt.

Ansonsten bräuchte man eine Semaphore, Mutex oder eine andere Art von 
Locking.

Übrigens ist Dein Ringpuffer nicht interrupt-fest, wenn im C Compier der 
Optimizer eingeschaltet wird. Die read und write Indizes müssten 
volatile sein (jedenfalls der der im Interrupt verwendet wird).

[Adam P. (adamap)]

Wenn deine Struktur so aussieht:

struct Buffer {

  uint8_t data[BUFFER_SIZE];

  uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt

  uint8_t write; // zeigt immer auf leeres Feld

} buffer = {{}, 0, 0};

und die Bedingung (write == read) als Buffer leer definiert ist,
dann kannst du nicht alle "Speicherstellen" nutzen.
Weil, wenn du nun doch ein weiteres Element speicherst, erhöhst du den 
write und dann wäre er auf read was wieder bedeuten würde, Buffer leer 
...obwohl er komplett voll wäre.

Du könntest natürlich deine Struktur erweitern:

struct Buffer {
  uint8_t data[BUFFER_SIZE];
  uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt
  uint8_t write; // zeigt immer auf leeres Feld
  size_t level; // Anzahl der gespeicherten Daten/Bytes etc.
} buffer = {{}, 0, 0};

Dann würde die Logik nicht an write, read hängen, sondern an "level".

Ob das nun wirklich schöner/besser ist, mh...

[MaWin (Gast)]

Jim M. schrieb:
> Gar nicht.

Unsinn.

> Das ist der Preis den man beim Ringpuffer für die Unabhängigkeit des
> Lesers und Schreibers zahlt.

Die Frage ist, ob man die im konkreten Fall überhaupt braucht.

> Ansonsten bräuchte man eine Semaphore, Mutex oder eine andere Art von
> Locking.

Nur, wenn der Zugriff aus zwei verschiedenen Kontexten stattfinden. z. 
B. Interrupt + Hauptschleife oder von zwei verschiedenen CPUs aus.

[Endwirrer (Gast)]

Bau Buffer_In() doch so um, das write immer auf das letzte beschriebene 
Feld zeigt. Dann muss eigentlich nur buffer.write++; früher ausgefhürt 
werden und alles andere kann so bleiben.

[Falk B. (falk)]

verwirrt schrieb:
> Wie kann man alle Stellen verwenden?

Wie schon mehrfach beantwortet, mit mehr Aufwand. Aber grade der sollte 
in der Bibliothek vermieden werden, Geschwindigkeit war oberste 
Priorität. In der Praxis spielt die eine ungenutzte Speicherzelle keine 
Rolle, wenn man nicht gerade einen FIFO mit 10kB structs anlegt.

[verwirrt (Gast)]

um es nochmal kurz zu erwähnen, das Beispiel stammt nicht von mir, 
sondern hier aus dem wiki :)

Das mit dem Threadsave ist mir bewust, ich weiß aber in diesem Fall 
nicht was schief gehen soll, der read (nicht im Interrupt) würde im 
schlimmsten Fall unterbrochen werden und hätte trotz ausgelesenem Wert 
den readzeiger nicht hochgezählt, was nach dem zurückkehren aus dem 
(write) Interrupt fortgesetzt werden würde. ok, das hieße das bei vollem 
Buffer nicht geschrieben werden könnte. Das gilt natürlich nur unter der 
Vorraussetzung dass das schreiben des Readzeigers (als Teil des 
Incements) Atomar sein muss.

[PittyJ (Gast)]

Ich würde immer einen Zähler mitlaufen lassen.
Denn bei mir kommt es öfter vor, dass ich später auch die Anzahl wissen 
möchte. Dann hat sich das gleich damit erledigt.

[kannAllesBesser! (Gast)]

verwirrt schrieb:
> abgefragt wird, entsteht immer eine Zelle in die nicht geschrieben
> werden kann.

... dann überdenke mal deine write/in Funktion!

Beispiel:

uint8_t writeBuf(irNEC_t *data) {
   if (!((irBuf->r + 1 - irBuf->w) % (uint8_t) IR_BUF_SIZE)) return 0; 
//full
   irBuf->data[irBuf->w++] = *data;
   if (irBuf->w >= IR_BUF_SIZE) irBuf->w = 0;
   return 1;
}

[A. S. (Gast)]

PittyJ schrieb:
> Ich würde immer einen Zähler mitlaufen lassen. Denn bei mir kommt es
> öfter vor, dass ich später auch die Anzahl wissen möchte. Dann hat sich
> das gleich damit erledigt.

Meistens lohnt der Aufwand nicht, zumindest wenn bytebuffer verwendet 
werden:
Speicher spart man nicht, die Anzahl kann auch so schnell berechnet 
werden. Und man hat einen Zähler, der in beiden Tasks beschrieben wird. 
Meist ist nur dafür ein Lock notwendig, alle anderen werden in einem 
Teil nur gelesen.

[Falk B. (falk)]

PittyJ schrieb:
> Ich würde immer einen Zähler mitlaufen lassen.
> Denn bei mir kommt es öfter vor, dass ich später auch die Anzahl wissen
> möchte. Dann hat sich das gleich damit erledigt.

Ist aber in Summe langsamer.

[foobar (Gast)]

[Bezieht sich auf Anwendungen, wo eine Seite in einer ISR läuft]

Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares 
inc/dec, Lock-less funktionieren.  Jeweils eine Seite ändert den Index, 
die andere liest ihn nur[1].

Führt man einen zusätzliches Datum ein (full-flag/counter), kommt man 
üblicherweise um Locks nicht herum - beide Seiten ändern das gleiche 
Feld, mehrere Felder müssen konsistent gehalten werden.

[Falk B. (falk)]

foobar schrieb:
> Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares
> inc/dec, Lock-less funktionieren.  Jeweils eine Seite ändert den Index,
> die andere liest ihn nur[1].

Nö, das geht auch nicht, denn die Indices bzw. Pointer sind nicht 
zwingend atomar! Nur wenn deine CPU atomare Zugriffe auf die beteiligten 
variablen OHNE Zusatzmaßnahmen in Software GARANTIERT, geht es ohne 
Verriegelung (neudeutsch Lock)

[Iwo (Gast)]

Falk B. schrieb:
> Nur wenn deine CPU atomare Zugriffe auf die beteiligten
> variablen OHNE Zusatzmaßnahmen in Software GARANTIERT

Interessant!

Ich ging bisher immer davon aus, dass uint8 immer atomar funktioniert.
Meine eigene Ringbuffer-Implementierung, die ich privat seit Jahren auf 
verschiedensten Systemen nutze, definiert Leser und Schreiber mit 
unsigned int, sodass je nach System eine 8-16-32Bit breite Variable 
angelegt wird, die dann auch auf jedem Targetatomar 
inkrementiert/dekrementiert.

Denkfehler oder Wissenslücke meinerseits?

[MaWin (Gast)]

Iwo schrieb:
> Ich ging bisher immer davon aus, dass uint8 immer atomar funktioniert.

Nur, wenn die Architektur überhaupt uint8_t im RAM zugreifen kann.
Das können nicht alle.
Mache lesen bei einem 8-Bit Schreibzugriff ein ganzes Maschinenwort, 
manipulieren das Byte und schreiben das Wort zurück.

[foobar (Gast)]

> denn die Indices bzw. Pointer sind nicht zwingend atomar!

Das setze ich als gegeben aus - load und store müssen atomar sein.  Die 
Read-modify-write-Instruktionen aber nicht.

[Falk B. (falk)]

Iwo schrieb:
> Interessant!
>
> Ich ging bisher immer davon aus, dass uint8 immer atomar funktioniert.

Mag sein, aber sind deine Pointer uint8_t? Oder deine Indices? Im 
Spezialfall ja, allgemein NEIN!

> Meine eigene Ringbuffer-Implementierung, die ich privat seit Jahren auf
> verschiedensten Systemen nutze,

Was nicht bedeutet, daß deine Implementierung wasserdicht ist. Du kannst 
auch sehr lange viel Glück haben.

> definiert Leser und Schreiber mit
> unsigned int,

Wer ist Leser und Schreiber?

> sodass je nach System eine 8-16-32Bit breite Variable
> angelegt wird, die dann auch auf jedem Targetatomar
> inkrementiert/dekrementiert.

Wer sagt das daß immer atromar ist?

> Denkfehler oder Wissenslücke meinerseits?

Möglichweweise beides. Aber ohne konkreten Code ist das eher schwer 
diskutierbar.

[Falk B. (falk)]

foobar schrieb:
>> denn die Indices bzw. Pointer sind nicht zwingend atomar!
>
> Das setze ich als gegeben aus

Schon mal ein Fehler!

>- load und store müssen atomar sein.

Das ist weniger das Problem, wenn gleich auch das groß genug ist.

>  Die
> Read-modify-write-Instruktionen aber nicht.

Aha. Und wie paßt das dann mit deiner Aussage  zusammen?

"
[Bezieht sich auf Anwendungen, wo eine Seite in einer ISR läuft]

Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares
inc/dec, Lock-less funktionieren.  Jeweils eine Seite ändert den Index,
die andere liest ihn nur[1]."

Au0erdem, was meinst du mit "dieser Art Ringspeicher"?

[kannAllesBesser! (Gast)]

kannAllesBesser! schrieb:
> uint8_t writeBuf(irNEC_t *data) {
>    if (!((irBuf->r + 1 - irBuf->w) % (uint8_t) IR_BUF_SIZE)) return 0;

struct {uint8_t r, w; irNEC_t data[IR_BUF_SIZE];} fifo, *irBuf = &fifo;

verwirrt schrieb:
> abgefragt wird, entsteht immer eine Zelle in die nicht geschrieben
> werden kann.


Zur Prüfung durch die vielen "Experten" hier ...
Es gibt keine ungenutzte Belegung im Circular Buffer und benötigt auch 
keinen extra Zähler.

[A. S. (Gast)]

kannAllesBesser! schrieb:
> Zur Prüfung durch die vielen "Experten" hier ...
> Es gibt keine ungenutzte Belegung im Circular Buffer und benötigt auch
> keinen extra Zähler.

Doch. Wenn Du %BUFSIZE rechnest, hast Du nur BUFSIZE Zahlen. Und damit 
kannst Du nicht BUFFSIZE Elemente PLUS 0 zählen.

Oder Du packst das mal in einen zusammenhängenden Code.

[A. S. (Gast)]

Iwo schrieb:
> sodass je nach System eine 8-16-32Bit breite Variable
> angelegt wird, die dann auch auf jedem Targetatomar
> inkrementiert/dekrementiert.

Abgesehen davon, dass int nicht 8 Bit sein dürfte: Ja, wenn es atomar 
ist, geht das wasserdicht. Wenn Zweifel bestehen (zumal mit %), dann 
halt einen Wrapper (bzw. je einen für Lesen und Schreiben) drum, der auf 
"atomaren" Plattformen zu nix zerfällt. Oder wenn klar ist, wer wen 
unterbricht (Interrupt die Main-Task), dann geht es auch ohne Lock 
sauber.

Also z.B. 2 Funktionen für Lesen und schreiben: Je ein Paar für 
Schreiben im Interrupt und lesen im Main und umgekehrt.

[foobar (Gast)]

>>> denn die Indices bzw. Pointer sind nicht zwingend atomar!
>>
>> Das setze ich als gegeben voraus
>
> Schon mal ein Fehler!
>
>>- load und store müssen atomar sein.
>
> Das ist weniger das Problem, wenn gleich auch das groß genug ist.

Natürlich geht das nicht mit jedem beliebigen Datentyp.  Man wählt den 
Typ der Indizes extra so, dass sie atomar gelesen und geschrieben 
werden.  Fertig.  Evtl ergeben sich dadurch Einschränkungen (z.B. max 
256-Byte-Buffer).  Und jetzt komm bitte nicht mit "aber wenn es keinen 
gibt" ...

>>  Die Read-modify-write-Instruktionen aber nicht.
>
> Aha. Und wie paßt das dann mit deiner Aussage  zusammen?
>
> "Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares
> inc/dec, Lock-less funktionieren. [...]"

Increment/decrement sind read-modify-write Instruktionen: load memory, 
increment, store memory - da darf jeweils beliebig Zeit zwischen 
vergehen, dürfen Interrupts ausgeführt werden, selbst schlafen ist 
erlaubt[2].  Einzig load und store müssen atomar sein - was kein Problem 
ist.

> Außerdem, was meinst du mit "dieser Art Ringspeicher"?

So einen, wie er im Eingang gezeigt wurde[1]: Nur ein Schreib- und ein 
Lese-Index, ein unbenutzes Element im Buffer zur Unterscheidung zwischen 
leer (w==r) und voll (w+1==r), keine zusätzlichen Flags, Zähler, etc.



[1] Eine Sache macht ihn nicht-IRQ-fest: die Modulo-Checks schreiben 
evtl erstmal einen ungültigen Index und korrigieren anschließend - ist 
aber ein Implementationsfehler, kein prinzipieller.

[2] Als Beispiel ein Ausschnitt aus meinen UART-Routinen: schau mal, 
wann txw gelesen, erhöht und geschrieben wird.

static u8 txbuf[16], txw;
static volatile u8 txr;

void uart_putc(u8 c)
{
    u8 w = (txw + 1) % sizeof(txbuf);

    sleep_while (w == txr);     // sleep while txbuf full
    txbuf[txw] = c;
    barrier("write txbuf before changing txw");
    txw = w;
    UCSR0B |= B(UDRIE0);
}

[verwirrt (Gast)]

Jim M. schrieb:
> Übrigens ist Dein Ringpuffer nicht interrupt-fest, wenn im C Compier der
> Optimizer eingeschaltet wird. Die read und write Indizes müssten
> volatile sein (jedenfalls der der im Interrupt verwendet wird).

kurze frage dazu, ja ich habe das in meinem richtigen code schon mit 
volatile, aber ebend nur weil das halt irgendwann mal so gesagt wurde.
Die Frage die sich mir stellt, ist das wirklich nötig?
soweit ich das verstanden habe ist volatile (frei nach mir) die Angabe 
an den Compiler, Achtung diese Variable kann außerhalb deines 
Sichbereichs geändert werde, also nicht wegoptimieren, nicht im speicher 
behalten.
Dieses trift imho dann zu wenn z.B. auf eine Variable mittels extern 
zugegriffen wird.
Aber in dem Beispiel hier ist es ja so, das der Compiler innerhalb einer 
(.c) Datei "sieht" das die Modulglobale (static) Variablen buffer.write 
bzw buffer.read in verschiedenen Funktionen verwendet werden.

Warum also sollte der Compiler hier egal in welcher Optimierungsstufe 
etwas bei dem Zugriff auf die Variable tun?

[MaWin (Gast)]

verwirrt schrieb:
> Dieses trift imho dann zu wenn z.B. auf eine Variable mittels extern
> zugegriffen wird.

Nein, überhaupt nicht.

Es geht bei der Überlegung darum, dass im Maschinenmodell der C-Sprache 
es kein Multithreading und keine Interrupts gibt.
Der Compiler kann also annehmen, dass alle Funktionen nacheinander, in 
welcher Anordnung auch immer, aufgerufen werden. Aber niemals parallel 
laufen können.

Wenn du dann in einer Funktion hintereinander

a += 1
b += 1
a -= 1

machst, dann darf der Compiler die Operationen auf a komplett verwerfen.
Das kann natürlich in der Praxis fatal sein, wenn zwischen den 
a-Operationen etwas anderes laufen darf.

Das ist nur ein Beispiel. Optimierungsmöglichkeiten hat der Compiler 
noch viel mehr.
Deshalb: Wenn eine Variable in einem Interrupt irgendwie angefasst wird 
(auch lesend!), dann volatile.

[verwirrt (Gast)]

ja richtig innerhalb einer Funktion darf der compiler Schritte 
optimieren, weglassen etc. aber beim einstieg in die Funktion darf er 
doch wohl nicht davon ausgehen das die Variable den gleichen Wert hat 
wie vor 3 Wochen als die Funktion das letzte mal durchlaufen wurde.

in dem Fall Ringbuffer wird ja jeweils nur lesend auf die Variablen 
zugegriffen

bsp:

es wird die readfunktion von der writefunktion unterbrochen

read()
{
lese buffer.write in register

INTERRUPT

write()
{
buffer.write++
}

INTERRUPT ende

bewerte buffer.write in register (um 1 niedriger als in der 
buffer.write)
lese ggf Buffer Stelle Aus

buffer.read++
}

ich hoffe es ist ungefähr ersichtlich wie das gemeint ist.
an welcher Stelle würde der Compiler denn hier etwas wegoptimieren 
können?

Es geht nicht darum das ich kein volatile da hin schreiben will, sondern 
dass ich verstehen will an welcher Stelle das passiert.


oder anders gefragt bei dem Beispiel oben

a += 1
b += 1
a -= 1

was würde es für einen Unterschied machen ob es static uint8_t a oder 
volatile static uint8_t a wäre?

[kannAllesBesser! (Gast)]

verwirrt schrieb:
> was würde es für einen Unterschied machen ob es static uint8_t a oder
> volatile static uint8_t a wäre?

static uint8_t a
global scope, könnte nach einmal lesen, die ganze weitere zeit in einem 
register gehalten werden oder auch nur abschnittsweise ohne neu 
einlesen.

volatile static uint8_t a
global scope, muss IMMER neu eingelesen werden, kann also nicht 
"zwischen gespeichert" werden.

[A. S. (Gast)]

verwirrt schrieb:
> ich hoffe es ist ungefähr ersichtlich wie das gemeint ist. an welcher
> Stelle würde der Compiler denn hier etwas wegoptimieren können?

Du hast Recht, dass gewisse Kombinationen kein volatile erfordern. Aber 
genau dann schadet es meist nicht, weil der Zugriff dann meist nur 
einmalig erfolgt.

Die Analyse (nötig/nicht nötig) ist zu selten wirklich umfassend, meist 
fehlerhaft und mit der kleinsten Änderung obsolete.

[Einer K. (Gast)]

verwirrt schrieb:
> aber beim einstieg in die Funktion darf er
> doch wohl nicht davon ausgehen das die Variable den gleichen Wert hat
> wie vor 3 Wochen als die Funktion das letzte mal durchlaufen wurde.

Doch darf er!
Denn schließlich weiß er genau, welche Register verändert wurden, in den 
letzten 3 Wochen.
Zudem macht er ja auch Funktionen inline, von denen man es nie erwarten 
würde.

[A. S. (Gast)]

Arduino Fanboy D. schrieb:
> Doch darf er!
> Denn schließlich weiß er genau, welche Register verändert wurden, in den
> letzten 3 Wochen.
> Zudem macht er ja auch Funktionen inline, von denen man es nie erwarten
> würde.

Das gilt (wenn überhaupt) nur für C++.

In C muss eine "ganz normale" Funktion (void foo(void)) damit rechnen, 
von irgendwoher aufgerufen zu werden. Und kann nicht annehmen, dass 
irgendetwas genauso war wie beim letzten mal.

[Einer K. (Gast)]

A. S. schrieb:
> In C muss eine "ganz normale" Funktion (void foo(void)) damit rechnen,
> von irgendwoher aufgerufen zu werden. Und kann nicht annehmen, dass
> irgendetwas genauso war wie beim letzten mal.
Ein kleiner Test, würde dir das Gegenteil beweisen!
OK, kannst du nicht...

Dann zeige ich es dir:

Eine ganz normale *.c Datei, etwas minimalistisch, ok

void init()
{
  DDRB |= _BV(PB5);
}

int main()
{
  init();
  for(;;);
}

Der Compiler Output, etwas gekürzt:

0000007c <__bad_interrupt>:
  7c:  0c 94 00 00   jmp  0  ; 0x0 <__vectors>

00000080 <main>:

void init()
{
  DDRB |= _BV(PB5);
  80:  25 9a         sbi  0x04, 5  ; 4
}

int main()
{
  init();
  for(;;);
  82:  ff cf         rjmp  .-2        ; 0x82 <main+0x2>

00000084 <_exit>:
  84:  f8 94         cli

00000086 <__stop_program>:
  86:  ff cf         rjmp  .-2        ; 0x86 <__stop_program>

Wie man sieht, hat es die Funktion init() inline gemacht, obwohl du 
sagst, das darf er nicht.

[Andreas M. (amesser)]

Natürlich kann man in einem Ringpuffer alle Elemente benutzen. Der Trick 
ist, die Zähler nicht bis BUFFSIZE sondern bis 2*BUFFSIZE laufen 
zulassen und erst dann umzubrechen.

Die Füllmenge des Puffers ist dann: (write < read)? (write-read + 
2xBUFFSIZE) : (write-read) Für den Index muss man dann rechnen: (read > 
=BUFFSIZE) ? (read - BUFFSIZE) : (read).

Wenn die Elementzahl ne Zweierpotenz ist, dann kann man den Index 
einfach read%BUFFSIZE und den Füllstand (write-read)%(2*BUFFSIZE) 
rechnen.

Die Read/Write Zähler sollten (/müssen) als "volatile" deklariert werden 
außerdem sollten diese der native Datenbreite der CPU entsprechen 
(Kleiner geht außer bei bestimmten Architekturen auch).

[Andreas M. (amesser)]

Arduino Fanboy D. schrieb:
> Wie man sieht, hat es die Funktion init() inline gemacht, obwohl du
> sagst, das darf er nicht.

Zeig doch mal die Compileroptionen. Denn eigentlich darf er das wirklich 
nicht, ich vermute mal es es ist "-funit-at-a-time" oder ähnliches 
gesetzt.

[Einer K. (Gast)]

Andreas M. schrieb:
> Compileroptionen.

Aber gerne doch:

compiler.c.cmd=avr-gcc
compiler.c.flags=-c -g -Os {compiler.warning_flags} -std=gnu11 -ffunction-sections -fdata-sections -MMD -flto -fno-fat-lto-objects
compiler.c.elf.flags={compiler.warning_flags} -Os -g -flto -fuse-linker-plugin -Wl,--gc-sections
compiler.c.elf.cmd=avr-gcc

PS:
Dieses kommt auch zum Einsatz:
(bevor noch Fragen kommen)

compiler.warning_flags.all=-Wall -Wextra

Andreas M. schrieb:
> "-funit-at-a-time"

-funit-at-a-time
This option is left for compatibility reasons. -funit-at-a-time has no 
effect ....

[Andreas M. (amesser)]

Dafür

Arduino Fanboy D. schrieb:
> Andreas M. schrieb:
>> Compileroptionen.

Na dann schau doch mal was "-flto" bewirkt. Und disambliere mal das .o 
file und nicht das ".elf" bzw vergleiche die beiden mal...

Kleiner Tip: Es ist nicht der Compiler der init() wegoptimiert, sondern 
der Linker.

[Einer K. (Gast)]

Andreas M. schrieb:
> Kleiner Tip: Es ist nicht der Compiler der init() wegoptimiert, sondern
> der Linker.
Ich weiß!
bzw, kann schon sein...
Tut aber nichts zur Sache.

Oder möchtest du mir sagen, dass LTO irgendwie verwerflich ist?

PS:
Habe mir mal den Spaß gegönnt und die ganzen LTO Options entfernt

compiler.c.flags=-c -g -Os {compiler.warning_flags} -std=gnu11 -ffunction-sections -fdata-sections -MMD
compiler.c.elf.flags={compiler.warning_flags} -Os -g  -Wl,--gc-sections

Das Ergebnis ist exakt das gleiche.
init() wird  inline eingebunden.

> was "-flto" bewirkt.
Habe geschaut.
Resultat: In diesem Fall wirkungslos.
(so wie ich es auch erwartet habe)

[Andreas M. (amesser)]

Arduino Fanboy D. schrieb:
> Andreas M. schrieb:
>> Kleiner Tip: Es ist nicht der Compiler der init() wegoptimiert, sondern
>> der Linker.
> Ich weiß!
> bzw, kann schon sein...
> Tut aber nichts zur Sache.
>
> Oder möchtest du mir sagen, dass LTO irgendwie verwerflich ist?

Nein, es ging darum das Du behauptest hast:

Arduino Fanboy D. schrieb:
> A. S. schrieb:
>> In C muss eine "ganz normale" Funktion (void foo(void)) damit rechnen,
>> von irgendwoher aufgerufen zu werden. Und kann nicht annehmen, dass
>> irgendetwas genauso war wie beim letzten mal.
> Ein kleiner Test, würde dir das Gegenteil beweisen!

Was falsch ist. Ein C-Compiler, genauso wie ein C++ Compiler oder ein 
Fortran Compiler oder ... MUSS eine nicht statisch oder inline markierte 
Funktion als global verfügbares Symbol in einer Objektdatei ablegen. 
Eben damit dieses Symbol aus einer anderen Objekt Datei heraus gebunden 
werden kann. Und damit darf der Compiler auch keine Annahmen bezüglich 
des Aufrufs der Funktion treffen, da er gar nicht wissen kann wer, wann 
oder ob überhaupt die Funktion aufgerufen werden wird.

Der C-Standard geht sogar noch weiter: Selbst wenn in einer C-Datei zwei 
Funktion mit exakt dem gleichen Code aber unterschiedlichem Namen 
definiert sind, muss der C-Compiler daraus zwei unterschiedliche 
Symboladressen generieren. Er darf im allgemeinen nicht beide Symbole 
auf die gleiche Zieladresse zeigen lassen. ISO C99 Abschnitt 6.5.9.6 
Pointervergleiche gilt auch für Funktionspointer. Es gibt darüber in den 
gcc, clang mailinglisten diverse Diskussionen.

Der Compiler wird es bei Optimierung so lösen, dass er an der 
Symboladresse der zweiten Funkion ein Sprung auf den Einsprungpunkt der 
ersten legt oder ein NOP einfügt. Hier mal als Beispiel: 
https://godbolt.org/z/oMfbq5

LTO ist jedoch etwas völlig anderes. Bei LTO interessiert sich der 
Linker überhaupt nicht für den vom Compiler erzeugten Objektcode, Statt 
dessen nimmt er die ganzen IR Bäume aus den mit LTO Flag kompilierten 
Objektdateien und optimiert diese in ihrer Gesamtheit unter der Annahme 
das es exakt ein extern sichtbares Symbol gibt ( bei AVR die 
Vektortabelle, bei einem "PC" Programm die main() Funktion. Dann kann 
der Linker natürlich eine ganze Menge mehr Annahmen machen, denn er 
kennt das komplette Program. Damit kann der Linker dann den Code viel 
weiter optimieren als es der C-Compiler alleine könnte, denn er "weis" 
nun ganz genau wann und wo welche Funktion wie oft aufgerufen wird oder 
ob diese überhaupt verwendet wird.

Effektiv gesehen ist LTO nichts anders als den gesamten Quellcode in 
eine einzige Datei zu schreiben, alle Deklarationen statisch zu machen 
(Bis auf main oder der Vektortabelle) und diese eine C Datei in den 
Compiler zu Füttern

[Andreas M. (amesser)]

Arduino Fanboy D. schrieb:
> PS:
> Habe mir mal den Spaß gegönnt und die ganzen LTO Options
> entferntcompiler.c.flags=-c -g -Os {compiler.warning_flags} -std=gnu11
> -ffunction-sections -fdata-sections -MMD
> compiler.c.elf.flags={compiler.warning_flags} -Os -g  -Wl,--gc-sections
> Das Ergebnis ist exakt das gleiche.
> init() wird  inline eingebunden.
>
>> was "-flto" bewirkt.
> Habe geschaut.
> Resultat: In diesem Fall wirkungslos.
> (so wie ich es auch erwartet habe)

Klar, der Compiler darf natürlich selbständig inlinen, aber er muss 
init() trotzdem als Objekt anlegen. Das Du das Symbol am Ende nicht 
siehst liegt an "-ffunction-sections -fdata-sections" welches bewirkt, 
dass das zusätzliche, extern sichtbare init in einer eigenen Section 
landet, welche wiederum der Linker entsorgt, da init() nicht weiter 
verwendet wird.

[MaWin (Gast)]

Andreas M. schrieb:
> da er gar nicht wissen kann wer, wann
> oder ob überhaupt die Funktion aufgerufen werden wird.

-fwhole-program

[Oliver S. (oliverso)]

Andreas M. schrieb:
> Dann kann
> der Linker natürlich eine ganze Menge mehr Annahmen machen, denn er
> kennt das komplette Program. Damit kann der Linker dann den Code viel
> weiter optimieren als es der C-Compiler alleine könnte,

Genau genommen ist’s auch bei lto der Compiler, der das alles macht. 
Link-time optimization ist da etwas irreführend.

Oliver

[Andreas M. (amesser)]

Oliver S. schrieb:
> Genau genommen ist’s auch bei lto der Compiler, der das alles macht.
> Link-time optimization ist da etwas irreführend.

Ich denke es heißt so, weil die "große" Optimierung dann während des 
Aufrufs des Linkers passiert, am Ende steht dann ja das ausführbare 
Programm. Das der im Hintergrund dann wieder Teile des Compilers 
aufruft...klar. Wobei man bei clang/llvm Compiler und Linker sowieso 
nicht mehr so ohne weiteres trennen kann, letzlich benutzen beide die 
gleiche Bibliothek im Hintergrund.

[c++standard (Gast)]

Andreas M. schrieb:
> Was falsch ist. Ein C-Compiler, genauso wie ein C++ Compiler oder ein
> Fortran Compiler oder ... MUSS eine nicht statisch oder inline markierte
> Funktion als global verfügbares Symbol in einer Objektdatei ablegen.
> Eben damit dieses Symbol aus einer anderen Objekt Datei heraus gebunden
> werden kann. Und damit darf der Compiler auch keine Annahmen bezüglich
> des Aufrufs der Funktion treffen, da er gar nicht wissen kann wer, wann
> oder ob überhaupt die Funktion aufgerufen werden wird.

interessant... wo finde ich das im C++ Standard?

[W.S. (Gast)]

verwirrt schrieb:
> Wie kann man alle Stellen verwenden?
> Bei nur einem Byte des Speichers wäre mir das relativ egal. aber da es
> darum geht, jeweils eine struct mit viel speicher zu verwenden, so ist
> es schon interessant wenn ich einen Speicher von z.B. 3
> "Speicherplätzen" benötige ob ich dann wegen der eigenheit speicher für
> 4 zur Verfügung stellen muss.

Also, du willst partout mit dem Kopf durch die Wand, ohne mal eine 
Fallunterscheidung in Erwägung zu ziehen.

Selbige würde ich allerdings als Allererstes tun:
a) Wenn du einen klassischen Fall für einen Ringpuffer hast, also viele 
Bytes zum Drucken oder sowas ähnliches, dann schert dich ein unbenutztes 
Byte schlichtweg garnicht.

b) wenn du hingegen nur ganz wenige Elemente hast, diese dafür aber groß 
sind (wie dein Beispiel mit dem Array aus 3 Struct's), dann ist ein 
Ringpuffer einfach nur fehl am Platze.

Dort macht man es sinnvollerweise anders, indem man jedem Struct ein 
Zähl- bzw. Alters-Byte hinzufügt. Die schreibende Instanz (z.B. ISR) 
sucht in dem Array nach einem Eintrag, der als leer markiert ist. Findet 
sie einen, dann sucht sie nach dem größten Altersbyte, versieht den 
neuen Struct mit einem um 1 erhöhten Altersbyte und schreibt dann den 
neuen Struct an die leere Stelle. Findet sie keine leere Stelle, dann 
entweder "FAIL" oder irgend etwas intelligenteres deiner Wahl.

Die lesende Instanz sucht im Array nach dem Eintrag mit dem kleinsten 
Altersbyte, liest es aus, und dann numeriert sie alle anderen Einträge 
neu durch, vom kleinsten beginnend. Dann wird der ausgelesene Eintrag 
als ungültig erklärt, z.B. ne 0 als Altersbyte hinein geschrieben.

Bei diesem Vefahren kann es Lücken im Zählbyte geben, aber die sind 
egal, da es ja nur drauf ankommt, die Reihenfolge zu bewahren. Ebenso 
ist es egal, ob da nun alles atomar erfolgt, weil bei diesem Verfahren 
keine Instanz der anderen dazwischenschreibt.

W.S.

[Einer K. (Gast)]

Andreas M. schrieb:
> Nein, es ging darum das Du behauptest hast:
>
> ....
>
> Was falsch ist. Ein C-Compiler, genauso wie ein C++ Compiler oder ein
> Fortran Compiler oder ... MUSS eine nicht statisch oder inline markierte
> Funktion als global verfügbares Symbol in einer Objektdatei ablegen.
Nun, dabei habe ich doch gar keine Aussagen, zu Objekt Dateien, gemacht.
Interessiert mich auch nicht sonderlich.

Das, was ins Flash gebrannt wird, das macht die Musik.



Bisher waren die Irrtümer ehr auf deiner Seite!
1. darf nicht inline machen - tut es aber
2. -funit-at-a-time - has no effect
3. LTO machts inline - hat in dem Beispiel keine Wirkung

Natürlich muss die Toolchain Wissen darüber haben (ob Compiler oder 
Linker ist mir dabei egal), welche Register in Nutzung sind, und welche 
nicht, denn sonst könnte es ja gar nicht dessen Nutzung optimieren.

Aber wenn es dich glücklich macht:
Ja, du hast in allem recht.
Immer.

So uns jetzt ziehe weiter und suche dir einen anderen den du für blöd 
erklären kannst.
Bei mir hast du es ja jetzt geschafft.
Meinen herzlichen Dank dafür.

[MaWin (Gast)]

Interessant, wie so ein Thread, der mit der ersten Antwort schon 
beantwortet wurde, eskalieren kann.

[Jörg (Gast)]

@ Arduino Fanboy D.
Ich finde es, schade, dass es am Ende immer so ausarten muss. Ohne jetzt 
da die Art der Auseinandersetzung bewerten zu wollen, fand ich die 
Ausführungen von Andreas M. wie Compiler/Linker arbeiten rein inhaltlich 
schon interessant (auch wenn am Ende natürlich gilt "Wichtig is' aufm 
Platz" also was geflasht wird).

[Einer K. (Gast)]

Jörg schrieb:
> Ich finde es, schade, dass es am Ende immer so ausarten muss.
Ich weiß gar nicht, was du willst...
Die mir weit überlegende Fachkompetenz des Andreas M. habe ich neidlos 
anerkannt und mich sogar für den ungerechtfertigten Einlauf bedankt.
Ein mehr an Demut kann ich nicht leisten....
Tiefer komme ich nicht runter.

[Jörg (Gast)]

Es war vielleicht falsch von mir, das mit dem Inhaltlichen auf Andreas 
M. beschränkt zu haben.
Ich habe jedenfalls von Euch beiden was gelernt. Danke dafür (das meine 
ich ohne jegliche Ironie) und ich hoffe, dass solche Diskussionen auch 
in Zukunft noch geführt werden. Und jetzt kann der Thread hoffentlich in 
Frieden ruhen ...

[S. R. (svenska)]

verwirrt schrieb:
> Wie kann man alle Stellen verwenden?

Das Problem ist, dass (read_index == write_index) dann mehrdeutig wird - 
entweder der Puffer ist randvoll oder leer. Diese Mehrdeutigkeit musst 
du vermeiden. Dazu genügt ein Flag, welches angibt, ob der letzte 
Zugriff lesend oder schreibend war. Man kann auch einen Zähler mitlaufen 
lassen.

Der Haken ist, dass Zähler oder Flag von beiden Seiten benutzt werden, 
also ein Lock brauchen.

foobar schrieb:
> Einzig load und store müssen atomar sein - was kein Problem ist.

Erstens: Wenn nur load/store atomar sind, aber das inc/dec nicht, dann 
funktioniert der Puffer nur mit genau einem Producer und genau einem 
Consumer. Das solltest du erwähnen.

Zweitens: Wenn der Compiler das Alignment deiner Variablen nicht 
garantieren kann, sind load/store möglicherweise auf keinem Datentypen 
atomar. Das ist mir mal sehr böse auf die Füße gefallen.

[900ss (900ss)]

Arduino Fanboy D. schrieb:
> den ungerechtfertigten Einlauf

Die Aussagen von Andreas waren alle sachlich, nicht persönlich. Also gab 
es auch keinen Einkauf, für niemanden.
Unsachlich wurde es an anderer Stelle und nicht von Andreas.
Also bitte bleib bei der Sache ;)