FIFO

Aus der Mikrocontroller.net Artikelsammlung, mit Beiträgen verschiedener Autoren (siehe Versionsgeschichte)
Wechseln zu: Navigation, Suche

Ein FIFO (First-In-First-Out) ist ein Pufferspeicher nach dem "Warteschlangen-Prinzip". Pufferspeicher dienen dazu, Daten aufzufangen, die noch nicht sofort verarbeitet werden können. Ein FIFO funktioniert definitionsgemäß so, dass das erste Element (First In), welches "hinten" in die Warteschlange eingefügt wird, später auch als erstes "vorne" herausgeholt wird (First Out). Das Gegenstück zum FIFO ist LIFO.

Funktion

Ein bekanntes Beispiel für einen FIFO-Speicher ist der des UARTs im PC. Dieser sammelt ankommende Daten solange, bis er fast voll ist (meist 14 Bytes). Dann wird ein Interrupt ausgelöst und der Prozessor kann "auf einen Rutsch" alle Daten auf einmal schnell auslesen. Ganz am Anfang hatten UARTs keinen FIFO und erzeugten für jedes empfangene Byte einen Interrupt, so wie es heute noch die meisten Mikrocontroller machen. Damit ist aber die CPU-Belastung wesentlich höher, was bei höheren Datenraten zu Problemen führen kann. In Senderichtung ist das Problem auch vorhanden, wenn gleich unkritischer. Mit einem FIFO kann die CPU sehr viele Dutzende bis Hunderte Bytes in sehr kurzer Zeit (wenige Dutzend Mikrosekunden) hineinschreiben, welche dann relativ langsam mittels Interrupt Byte für Byte mit dem UART gesendet werden. Die CPU muss nicht warten, bis jedes einzelne Zeichen versendet wurde. Zum Vergleich. Ein AVR mit 16 MHz Takt macht während der Übertragung von 1 Byte bei 115200 Baud (86,8us) 1389 CPU-Takte. Damit kann man sehr viel anstellen! Bei schnelleren CPUs bzw. niedrigeren Baudraten ist das Mißverhältnis noch deutlich größer. Im Idealfall werden die Daten aus dem FIFO mittels DMA an den UART übertragen, dann hat der Prozessor gar nichts mehr damit zu tun.

Die Umsetzung eines FIFOs in Software heißt Ringpuffer und weist auch eine feste Puffergröße auf. Wesentlicher Vorteil gegenüber der verketteten Liste ist die schnellere Ausführungszeit und der geringere Aufwand.

Standard-Ringpuffer

Vorteile:

  • Simpel
  • Leicht verständlich
  • Daten können auch vom Typ struct sein

Nachteile:

  • Schnell aber nicht optimal

Beschreibung

Ringpuffer.png

Circular buffer.png

Die Inhalte des Puffers werden in einem schlichten Array gespeichert und der Zugriff erfolgt über einen Integer-Index. Erreicht ein Index die Obergrenze springt dieser auf Null zurück. Topologisch ist dies äquivalent zu einem Ringschluss, bei dem man ja auch nach dem letzten Element wieder beim ersten angelangt ist. Man denke zb an das Zifferblatt einer Uhr, bei der nach der 59 wieder die 0 kommt. Ein größer-gleich statt nur eines ist-gleich Vergleichs ist sicherer gegenüber Programmfehlern, bei denen der Index verstellt wurde.

write = write + 1;
if (write >= BUFFER_SIZE)
  write = 0;

Haben Lese- und Schreib-Index den gleichen Wert, wird der Puffer als leer angesehen und es kann kein Element aus dem Puffer entnommen werden. Wenn write+1 und read identisch sind wird der Puffer als voll angesehen und es kann kein weiteres Element mehr im Puffer gespeichert werden. Nun fehlt noch der Sonderfall bei dem read gleich Null ist, hier funktioniert der write+1-Vergleich nicht mehr (wegen dem 'Überlauf' am Ende des Arrays, der den Ringschluss bewirkt) und die Abfrage einer zusätzlichen Bedingung ist zur Voll-Abfrage erforderlich.

read == write => leer
write + 1 == read || read == 0 && write+1 == BUFFER_SIZE => voll

Bei gleichzeitigem Zugriff zwischen dem Befüller (zb. einer UART-ISR) und dem Entnahmecode (zb. der Code in der Hauptschleife) muss ausgeschlossen werden, dass der Entnahmecode beim Lesen aus dem Puffer nicht durch den Interrupt unterbrochen werden kann. Denn während diese Funktion läuft, ist zwischenzeitlich der read-Index in einem inkonsistenten Zustand. Erst nach Beendigung der Funktion spiegelt der read-Index wieder die Realität des Füllgrades wieder. Als Abhilfe dienen Atomare Abschnitte, solche können durch keinen Interrupt unterbrochen werden. Die Radialkur deaktiviert alle Interrupts, besser ist die Deaktivierung eines einzelnen Interrupts. Es geht aber meistens auch so, da die FIFO-Funktionen sehr kurz sind und daher auch die Interrupts nur kurz abgeschaltet werden. Im Allgemeinen werden versäumte Interrupts nach erneuter Aktivierung nachgeholt und gehen nicht verloren, so dass bereits anstehende Interrupts nur kurz verzögert werden. Solange die Interruptperiodendauer größer als die Ausführungsgeschwindigkeit der FIFO Funktionen ist, stellt das Abschalten der Interrupts daher auch in der Praxis meist kein allzugroßes Problem dar.

cli()
ret = BufferOut(&var);
sei()

Hilfreich ist die Initialisierung der Indizes (read, write) mit -1, denn damit kann man einen leere Ringpuffer von einem vollen unterscheiden. Initialisiert man nur mit 0, kann man einen leeren nicht von einem vollen mit read=write=0 unterscheiden.

Eine weitere Möglichkeit der Vereinfachung entsteht durch die Einführung einer "Counter" Variable, die den Füllstand des Buffers wiedergibt. Bei Einschreiben wird diese um +1 erhöht, beim Auslesen um 1 erniedrigt. Ist sie 0 ist der Buffer leer. Damit lässt sich die Codeeffizienz steigern, da die obigen Vergleiche kürzer ausfallen und sich auf nur diese eine Variable beschränken. Nachteilig ist allerdings, dass man eine weitere Variable im System hat und natürlich benötigen die entsprechenden Operationen zum Erhöhen bzw. Erniedrigen dieser Variable ja auch Ausführungszeit. Benötigt man im restlichen Code den Füllgrad der FIFO nicht als explizite Zahl, dann lohnt daher eine derartige Counter-Variable meistens nicht.

Code-Beispiel

#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;
}

FIFO als Bibliothek

Hier sollen FIFO-Funktionen bereitgestellt werden, welche folgende Eigenschaften besitzen.

  • Mehrfache FIFOs einfach anlegen und benutzen
  • Leistungsfähiger Zugriff auf FIFO-Daten (Blockzugriff)
  • Interruptfester FIFO-Zugriff

Diese FIFOs sind auf so ziemlich allen Plattformen nutzbar, entwickelt wurde sie jedoch auf einem AVR. Daher ist im FIFO im Moment auch noch eine Begrenzung der FIFO-Größe auf 64kiB vorhanden, welche aber leicht per typedef in fifo.h abgeändert werden kann. Ebenso kann die Größe der FIFO-Elemente eingestellt werden (8, 16, 32 Bit, ebenfalls structs). Alle FIFO-Funktionen sind interruptsicher aufgebaut, d.h. die kritschen Zugiffe auf die FIFO-Kontrolldaten erfolgen atomar. Damit ist der Einsatz im Hauptprogramm und in Interrupts sicher möglich. Bei anderen Plattformen muss ggf. der atomare Zugriff angepasst werden. Der Datenzugriff erfolgt direkt über Pointer, das erhöht die Geschwindigkeit gegenüber Indexoperationen. Die folgenden Funktionen sind im wesentlichen verfügbar:

  • fifo_init(): FIFO initialisieren
  • fifo_write_busy(): wartet bis mindesten 1 Element im FIFO frei ist und schreibt es in den FIFO
  • fifo_write(): schreibt ein Element in den FIFO, ohne Prüfung ob genügend Platz vorhanden ist
  • fifo_read_busy(): wartet bis mindesten 1 Element im FIFO vorhanden ist und liest es aus dem FIFO
  • fifo_read(): liest ein Element es aus dem FIFO, ohne Prüfung ob Daten vorhanden sind
  • fifo_get_level(): liefert die Anzahl der Elemente im FIFO zurück
  • fifo_get_free(): liefert die Anzahl der noch frei verfügbaren Elemente im FIFO zurück

Die Funktionen fifo_write_busy() und fifo_read_busy() warten solange vor dem FIFO-Zugriff, bis Speicher bzw. Daten im FIFO verfügbar sind. Das kann bisweilen lange dauern (blockierende Funktionen). Die Funktionen fifo_write() und fifo_read() greifen ohne weitere Prüfung auf den FIFO zu. Die Prüfung muss vorher erfolgen. Damit ist eine nicht blockierende Arbeitsweise möglich (Multitasking).

Leistungsverbesserung

Die Funktionen zum Lesen und Schreiben einzelner Elemente sind einfach und klar. Aber was ist, wenn man mehrere Elemente aus dem FIFO lesen will? Oder noch viel schlimmer, wenn Bibliotheksfunktionen mehrere Elemente über einen Zeiger lesen wollen? Hier kommen die restlichen Funktionen ins Spiel.

  • fifo_write_bursted(): korrigiert den Schreibzeiger des FIFOs nach einem Blockzugriff
  • fifo_read_bursted(): korrigiert den Lesezeiger des FIFOs nach einem Blockzugriff

D.h. eine Funktion wie z.B. memcpy() liest eine Anzahl X Bytes aus dem FIFO und kopiert sie woanders hin. Danach wird der Lesezeiger um die Anzahl X korrigiert. Damit muss nicht X mal die Funktion fifo_read() aufgerufen werden, was deutlich an CPU-Leistung spart. Ein derartiger Blockzugriff spart auch Zwischenspeicher, wenn z.B. eine Funktion zum Schreiben von Daten auf SD-Karte direkt auf diese zugreifen kann, ohne dass sie weiß, dass diese in einem FIFO stecken!

Doch Vorsicht, so einfach ist es nicht! Denn unser FIFO ist ein Ringpuffer! Am Ende des Datenbereichs muss der Schreib- bzw. Lesezeiger immer wieder auf den Anfang des Datenbereichs zurück springen. Allerdings wissen Funktionen wie memcpy() und andere nichts von einem Ringpuffer! Sie erwarten die Daten immer in linearer Anordnung im Speicher. D.h. man muss vor einem Blocktransfer immer erst prüfen, ob die gewünschte Menge Daten linear an einem Stück im FIFO liegt oder ob zwischendrin ein Überlauf des Schreib- oder Lesezeiger statt findet. In diesem Fall muss man den Blockzugriff auf zwei Zugriffe aufteilen. Dazu dienen die beiden Funktionen

  • fifo_get_read_wrap(): liefert die Anzahl Elemente bis zu Überlauf des Lesezeigers
  • fifo_get_write_wrap(): liefert die Anzahl Elemente bis zu Überlauf des Schreibzeigers

Die Anwendung aller Funktionen ist in einem kurzen Beispielprogramm demonstriert und mit Doxygen dokumentiert (/doxygen/html/index.html). Dabei ist vor allem zu beachten, dass die Funktionen des FIFOs immer mit der Anzahl von Elementen arbeiten, wogegen viele andere Funktionen mit der Anzahl von Bytes arbeiten. Die kleine Bibliothek ist als Archiv verfügbar. Für die Simulation muss man die Optimierung des Compilers ausschalten, um alle Variablen anzeigen zu können.

2n-Ringpuffer - die schnellste Lösung

Vorteile:

  • Durch Bitmaske auf den Feld-Index write kann der nicht "Amoklaufen" und beliebige Inhalte im Speicher überschreiben
  • Sehr einfach, sehr schnell

Nachteile:

  • Nur Größenfaktoren von 2n möglich
  • Nur in speziellen Fällen Pointerreferenz möglich

Beschreibung

Wenn der Index am oberen Ende angekommen ist springt er an den Anfang zurück. Die Definition der Obergrenze wird nicht durch einen Vergleich realisiert, sondern durch Modulo-Arithmetik. Dies kann sehr einfach und schnell durch Maskieren des Index-Werts umgesetzt werden.

Beispiel:

( write + 1 ) & MASK

15 = 0b00001111
15 + 1 = 16 = 0b000010000
16 & MASK = 0b000010000 & 0b000001111 = 0b000000000

Daraus folgt das write nur einen Wert zwischen 0 und 15 einnehmen kann. Das ganze funktioniert nur mit Zahlen der Reihe 2n.

Da der Puffer nur eine endliche Größe aufweist, muss eine voll/leer Indikation verfügbar sein. read == write bedeutet Puffer leer, entsprechend bedeutet write + 1 == read, dass keine weiteren Elemente mehr hinzugefügt werden können, denn sonst würde das Hinzufügen weiterer Daten einen Pufferüberlauf hervorrufen. Für die Behandlung des Pufferüberlaufs gibt es zwei Methoden, nichts tun und Fehler zurück geben oder ältesten Puffer-Inhalt verwerfen (read+1).

read == ((write + 1) & MASK)

Auch hier verhindert die Bitmaske einen möglichen Überlauf. Weiter zu beachten ist, dass ein Byte durch die voll/leer Indikation verloren geht, der Puffer hat hier nur eine größe von 15 statt 16 Byte

Und noch ein kleiner Trick. Bei einer Zahl der Reihe 2^n lässt sich auf einfache Weise immer eine passende Bitmaske erzeugen und man sieht gleichzeitig klar die Anzahl der genutzten Bytes.

# define SIZE 16
# define MASK (SIZE-1)

16     = 0b010000
16 - 1 = 0b001111

Im Normalbetrieb sollte der Puffer nie voll ausgereizt sein und wenn der Puffer bereits überläuft ist es für die Systemstabilität und Fehleranlyse oft schon zu spät, denn von einem nicht mehr funktionierenden Gerät lässt sich nur wenig Information herauskitzeln. Da kann ein Frühwarnsystem mehr bieten, wobei zwei Ausprägungen typisch sind, Höchstwert merken und eine Meldeschwelle einführen.

 freeMemory =  (read - write - 1 ) & MASK);
 if (freeMemory < floodmark)
   floodmark = freeMemory;
 if ( (read - write - 1 ) & MASK) <= FLOODMARK;
   FloodmarkExcess();

Eine entsprechende Auswertung kann z.B. bei einer UART zur Steuerung des Handshakes benutzt werden, bei dem die Gegenstelle aufgefordert wird, das Senden kurzfristig einzustellen, damit man nicht Gefahr läuft, übertragene Zeichen zu verlieren, weil die FIFO voll wird. Dabei ist allerdings auch zu berücksichtigen, dass die Gegenstelle das Senden nicht sofort einstellen kann, da sich beispielsweise bereits Zeichen in der Sendehardware befinden können, die der Sender nicht mehr stoppen kann. Hier heißt es also rechtzeitig zu reagieren und nicht erst, wenn der FIFO propevoll ist. Fällt der Füllgrad einer darartigen UART-FIFO wieder unter eine gewisse Schwelle, dann wird der Gegenstelle signalisiert, dass sie mit dem Senden fortfahren kann.

Code-Beispiel

#define BUFFER_FAIL     0
#define BUFFER_SUCCESS  1
 
#define BUFFER_SIZE 16 // muss 2^n betragen (8, 16, 32, 64 ...)
#define BUFFER_MASK (BUFFER_SIZE-1) // Klammern auf keinen Fall vergessen

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)
{
  uint8_t next = ((buffer.write + 1) & BUFFER_MASK);

  if (buffer.read == next)
    return BUFFER_FAIL; // voll

  buffer.data[buffer.write] = byte;
  // buffer.data[buffer.write & BUFFER_MASK] = byte; // absolut Sicher
  buffer.write = next;

  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 = (buffer.read+1) & BUFFER_MASK;

  return BUFFER_SUCCESS;
}

FIFO mit C-Präprozessor

#ifndef FIFO_H_
#define FIFO_H_

#include <stdint.h>

typedef struct {
        uint8_t _read;
        uint8_t _write;
        uint8_t _buffer[64];
} FIFO64_t;

typedef struct {
        uint8_t _read;
        uint8_t _write;
        uint8_t _buffer[128];
} FIFO128_t;

#define FIFO_init(fifo)         { fifo._read = 0; fifo._write = 0; }

#define FIFO_available(fifo)    ( fifo._read != fifo._write )

#define FIFO_read(fifo, size) (                                         \
        (FIFO_available(fifo)) ?                                        \
        fifo._buffer[fifo._read = (fifo._read + 1) & (size-1)] : 0      \
)

#define FIFO_write(fifo, data, size) {                                                          \
        uint8_t tmphead = ( fifo._write + 1 ) & (size-1);       /* calculate buffer index */    \
        if(tmphead != fifo._read) {                             /* if buffer is not full */     \
                fifo._buffer[tmphead] = data;                   /* store data in buffer */      \
                fifo._write = tmphead;                          /* store new index */           \
        }                                                                                       \
}

#define FIFO64_read(fifo)			FIFO_read(fifo, 64)
#define FIFO64_write(fifo, data)		FIFO_write(fifo, data, 64)

#define FIFO128_read(fifo)			FIFO_read(fifo, 128)
#define FIFO128_write(fifo, data)		FIFO_write(fifo, data, 128)

#endif /*FIFO_H_*/

Hinweis: viele C-Compiler übersetzen automatisch eine Modulo-Division mit einem Divisor einer 2-er Potenz in Form einer entsprechenden Bitmaskierung. Zum einen erspart man sich dadurch das Bestimmen der entsprechenden Maske, zum anderen hat man dann den 'Bonus', dass der Code immer noch korrekt funktioniert (wenn auch langsamer), wenn der Anwender einen Fehler macht und die Array-Länge nicht als 2-er Potenz definiert. Die Operation

	fifo._buffer[fifo._read = (fifo._read + 1) & (size-1)] : 0	\

kann dann durch die in diesem Sinne gleichwertige Operation

	fifo._buffer[fifo._read = (fifo._read + 1) % size] : 0	\

ausgedrückt werden, bzw.

	uint8_t tmphead = ( fifo._write + 1 ) & (size-1);       /* calculate buffer index */	\

durch

	uint8_t tmphead = ( fifo._write + 1 ) % size;           /* calculate buffer index */	\

Generische FIFO mit C-Präprozessor

Mit einigen zusätzlichen Macro-Tricks (und GCC Compiler Extensions) ist es möglich diese FIFO auf beliebige Datentypen und Längen zu erweitern. Die Grundidee ist, dass für jede FIFO ein neuer struct erstellt wird, dessen Bestandteile identisch benannt sind. So können später Macros auf die einzelen Elemente per Bezeichung zugreifen, selbst wenn diese einen beliebigen Typen haben!

Ein einfaches Macro zum deklarieren einer solchen FIFO-Struktur ist:

#define _fifo__name_struct(_id)		fff_ ## _id ## _s

#define _fifo_declare(_type, _id, _depth)	\
struct _fifo__name_struct(_id) {			\
	uint8_t read;							\
	uint8_t write;							\
	uint8_t level;							\
	_type data[_depth];						\
} _id

Zum initialisieren kann folgendes Macro genutzt werden:

#define _fifo_init(_id)						\
struct _fifo__name_struct(_id) _id = {0, 0, 0, {}}

Die benötigte Maske bzw. FIFO Größe müssen nicht in dem Struct gespeichert werden, denn sie können beim Compilieren ermittelt werden:

#define _sizeof_array(_array)	(sizeof(_array)/sizeof(_array[0]))
#define _fifo_mem_depth(_id)	(_sizeof_array(_id.data))
#define _fifo_mem_mask(_id)		(_sizeof_array(_id.data)-1)
#define _fifo_wrap(_id, idx)	((idx) & _fifo_mem_mask(_id))

Die Makros für den Zugriff auf die FIFO sind dem vorherigen Beispiel sehr ähnlich und werden daher nicht weiter erläutert. Mit Macros ist es allerdings ebenfalls möglich, auf die FIFO wie auf einen Array zuzugreifen, wessen Startadresse sich mit dem aktuellen 1. Element ändert:

#define _fifo_peek(_id, idx)	_id.data[_fff_wrap(_id, _id.read+(idx))]

Anders als die typische "read" Funktion wird mit _fifo_peek() kein Element aus der FIFO entfernt. Damit ist es sehr einfach möglich, einen fließenden Mittelwert zu generieren oder komplexere FIR-Filter zu programmieren. Da auf die Daten wie bei einem Array zugegriffen wird, kann das Macro sogar als linker Operand genutzt werden, um bereits genutzten Speicher zu überschreiben/ bearbeiten.

Diese Macros sind zudammen mit den typischen read/write-Macros zu einer kleinen, MIT-lizensierten Lib zusammengefasst und auf https://github.com/nqtronix/fifofast gehostet. Beiliegend ist ebenfalls eine readme.md sowie ein Demo-Projekt für Atmel Studio 7 zum Testen und Debuggen der FIFO. Fragen, Verbesserungsvorschläge oder generelles Feedback können im Thread https://www.mikrocontroller.net/topic/460020 gepostet werden; für Bug-Reports bitte ich darum ein Issue auf github zu erstellen.

Weblinks