Cache Strategien für E2PROM in uC

[Christian J. (Gast)]

Moin,

ich versuche grad mehr als Denksport das kleine EE in einem AVR 328 
etwas zu schonen, auch wenn es kein Thema wäre den Stein öfter zu 
tauschen. Ich habe das EE jedenfalls noch nicht kaputt gekriegt. Aber es 
geht mehr um den Denksport und eine "schöne" Lösung. Könnte das hier 
hinhauen? Zumindest dann wenn es sich wiederholende Zugriffe gibt? Zu 
gross darf der Cache nicht sein, sonst wird er langsam, zu kleiner aber 
auch nicht.

typedef struct {
   uint16_t address;
   uint8_t  data;
} eecache_t;

#define EECacheSize  128
static eecache_t eecache[EECacheSize];
static uint8_t eecache_pnt = 0;

/* Schreibt unter Nutzung des Cache ins interne EE */
void EEIntCacheWrite(const uint16_t address, uint8_t zahl)
{
  /*Adresse schon im Cache ? */
  int target = 0;
  bool treffer = false;
  while (!treffer && (target < eecache_pnt))
    if (eecache[target].address == address)
      treffer = true;
    else
      target++;
  }
  
  if (treffer) {
    /* Neuen Wert an gecachter Adresse eintragen */
    eecache[target].address = address;
    eecache[target].data    = zahl;
  } else {
    /* Neuen Wert am Ende hinzufügen */
    eecache[eecache_pnt].address = address;
    eecache[eecache_pnt].data    = zahl;
    
    /* Cache voll? */
    eecache_pnt = (eecache_pnt + 1) % EECacheSize;
    
    if (eecache_pnt == 0) {  /* Bei Überlauf alles einzeln wegschreiben */
      for (int i = 0; i < EECacheSize; i++)
        EEPROM.update(eecache[i].adress, eecache[i].data);
    }
  }
}

/* Liest ein Byte aus dem internen EE bzw. Cache */
byte EEIntCacheRead(uint16_t address)
{
  /*Adresse schon im Cache ? */
  int target = 0;
  while (target < eecache_pnt) {
    if (eecache[target].address == address)
      return (eecache[target].data);
    else
      target++;
  }
  
  /* Wert aus EE lesen und in Cache eintragen */
  eecache[eecache_pnt].address = address;
  uint8_t temp          = EEPROM.read(address);
  eecache[eecache_pnt].data    = temp;

  /* Bei Überlauf alles einzeln wegschreiben */
  eecache_pnt = (eecache_pnt + 1) % EECacheSize;
  if (eecache_pnt == 0) {  
        for (int i = 0; i < EECacheSize; i++)
      EEPROM.update(eecache[i].adress, eecache[i].data);
  }
  return (temp);
}


/* Schreibt den ganzen Cache weg */
EEIntCacheFlush() {
  for (int i = 0; i < EECacheSize; i++)
      EEPROM.update(eecache[i].adress, eecache[i].data);
  eecache_pnt  = 0;
}

[Sebastian E. (sbe_15)]

Moin

Spontane Ideen:
- Den Cache sortiert halten (binary search + insertion sort beim 
lesen/schreiben)
- Beim lesen die Daten nicht in den Cache laden (macht IMO keinen Sinn)
- Größe der Cache-Einträge auf mehrere Bytes erweitern (sollte den 
Suchaufwand reduzieren)

[Christian J. (Gast)]

Sebastian E. schrieb:
> - Beim lesen die Daten nicht in den Cache laden (macht IMO keinen Sinn)

Warum? Das machen Festplatten Caches aber auch. RAM ist viel schneller 
als diese I2C krücke. Alles andere Zustimmung. Sortieren ... gucken..... 
es ist ja alles nur sehr klein, da ist ein Suchlauf fix durch. Binäre 
Bäume wollte ich nicht aufziehen, die allerdings sehr schnell durchsucht 
werden können. Schon 1986 gelernt bei UCSD Pascal auf Apple II :-) Das 
hier ist aber ein AVR328P.

[Sebastian E. (sbe_15)]

Wir reden vom internen EEPROM, oder?
Daher würde ich das normale Lesen für so zügig halten (müsste man wohl 
benchmarken), dass sich das Cachen nicht lohnt.

Dazu könnte ein Lesen einen Flush auslösen, was dann wiederum sehr lange 
dauert (weil der Cache eben grad voll ist).

[Christian J. (Gast)]

Sebastian E. schrieb:
> Daher würde ich das normale Lesen für so zügig halten (müsste man wohl
> benchmarken), dass sich das Cachen nicht lohnt.

Sorry..... mein Denkfehler. Habe beides in meiner Bastelsache, 64kb 
Extern und 1 kb intern. Extern ist schwierig, da die Messwerte seriell 
weggeschrieben werden und keine Wiederolungen passieren. Im Internen 
halte ich nur die Eckdaten, Zeiten, Pointer, Array-Laufvariable, 
Maximalwerte usw.

[x^y (Gast)]

Ich habe einen solchen Cache Layer selbst schon geschrieben. Ich würde 
dir zu einem Page basierten Ansatz raten. Natürlich hängt es davon ab 
wieviel RAM zu spendieren möchtest. Bei deinem Ansatz ist das Verhältnis 
aus Nutzdaten zu Adressen sehr schlecht (2 Byte je 1 Byte Daten). Das 
macht auch das Lookup in der langen Liste vergleichsweise langsam.

Ein Page basierter Ansatz (typisch: gleiche Page Größe wie EEPROM) kann 
die Lese/Schreib Geschwindigkeit deutlich steigern, da i.d.R. weniger 
I2C Transfers statt finden. Gelesen/Geschrieben werden immer ganze 
Pages. Die Adressen sind immer in Bezug zur Page Größe aligned. Als 
Caching Strategie eignet sich z.B. LRU.

Beim Schreiben wird mit diesem Ansatz der Verlust an Geschwindigkeit 
durch den Internal Write Cycle limitiert, da dieser i.d.R. nicht kürzer 
ist ob nur ein Byte oder eine ganze Page geschrieben wird und das 
Schreiben vieler einzelner Bytes aus einer Page sonst zu mehrfachem 
Neubeschreiben führt.

[Christian J. (Gast)]

x^y schrieb:
> Ich habe einen solchen Cache Layer selbst schon geschrieben.

Hast du da vielleicht auch Code zu? Ich habe nicht viel Platz, iszt ja 
nur ein kleiner uC aber vielleicht brauche ich das noch mal für den ARM 
Cortex. Aber der hat auch Backup Ram und das kann man genauso verwenden. 
Bzw auch emuliertes EEPROM was vom Flash abgezwackt wird. Beim ESP8266 
ist das auch genial mit dem internen FS.

[foobar (Gast)]

Ein Bug: in CacheFlush darf die Schleife nur bis eecache_pnt gehen.

Ansonsten:

- Die Laufzeit von CacheWrite ist ziemlich zufällig und kann beim Flush 
seeehr langsam sein - ist das immer erlaubt?
- Mach dir mal Gedanken, was zu welcher Zeit tatsächlich im EEPROM 
landet und ob die Daten dann noch konsistent sind, z.B. nen 16bit-Wert, 
der mit zwei CacheWrite gemacht wird (ein Write landet im EEPROM, einer 
im Cache).  Bei größeren Datenblöcken mit interner Konsistenz wird es 
immer kritischer.
- Du schreibst, auch wenn sich die Daten selbst nicht geändert haben.
- Ab und zu musst du die Daten wegschreiben (cache flush), sonst landen 
sie nie im nicht-flüchtigen Speicher.  Dies ist die minimale 
Schreibrate, die eh nie unterschritten wird.
- Deine Routinen sind zwar universell, verbrauchen dadurch aber auch 
viel RAM.  Hast du wirklich so viele Schreibzugriffe auf wilde Adressen 
dass das nötig ist?
- Was passiert, wenn eine Zelle gekaputt geht?

Überleg dir, ob es nicht sinnvoller ist, die zu speichernden Daten in 
einer Struct zu verwalten (kann auch automatisch per Segment-Attribute 
sein), die zu festgelegten (sicheren) Zeitpunkten weggeschrieben werden, 
wenn möglich mit wear-leveling und evtl CRC.

[x^y (Gast)]

Christian J. schrieb:
> Hast du da vielleicht auch Code zu?

Den darf ich nur leider nicht herausgeben, tut mir leid. Ich kann dir 
nur mit Rat zur Seite stehen.

Was noch etwas ungewöhnlich an deinem Ansatz ist, dass du gar kein 
"Dirty" Flag führst und somit auch Werte zurückschreibst, die gar nicht 
geschrieben werden müssten, weil sie sich nicht geändert haben. Solange 
du z.B. nur liest musst du ja nichts schreiben. Das "Dirty" Flag (für 
eine Page) kann man entweder pauschal (immer) in der Schreiben Funktion 
setzen oder nach memcmp() wenn sich durch das Schreiben etwas ändert.

[Christian J. (Gast)]

x^y schrieb:
> Was noch etwas ungewöhnlich an deinem Ansatz ist, dass du gar kein
> "Dirty" Flag führst

Das macht die eeprom.update Funktion intern, die in der Lib drin ist.

[Christian J. (Gast)]

foobar schrieb:
> Ein Bug: in CacheFlush darf die Schleife nur bis eecache_pnt gehen.
>
> Ansonsten:

Ich lasse mir das mal durch den Kopf gehen. Danke!

Muss trotzdem auf 0 prüfen, da MOD % ja 0 ergeben kann bei Überlauf und 
dann auf jeden Fall geschrieben werden muss.

/* Schreibt den ganzen Cache weg */
void EEIntCacheFlush()
{
  int limit;
  if (eecache_pnt == 0)
    limit = EECacheSize;
  else
    limit = eecache_pnt;

  for (int i = 0; i < limit; i++)
     EEPROM.update(eecache[i].address, eecache[i].data);

  debugln(F("Flushing Cache... "));
  eecache_pnt  = 0;
}

[Christian J. (Gast)]

Müsste jetzt so halbwegs funzen, bzw läuft es schon zum Testen. 
Optimaler geht immer aber erster Wurf jetzt.

1. Lauf
W:Searching Cache... W:Kein Treffer->Haenge an bei 0 W:Cache Pointer: 1
W:Searching Cache... W:Treffer bei 0
W:Searching Cache... W:Kein Treffer->Haenge an bei 1 W:Cache Pointer: 2
W:Searching Cache... W:Kein Treffer->Haenge an bei 2 W:Cache Pointer: 3
W:Searching Cache... W:Treffer bei 2
W:Searching Cache... W:Kein Treffer->Haenge an bei 3 W:Cache Pointer: 4
W:Searching Cache... W:Kein Treffer->Haenge an bei 4 W:Cache Pointer: 5
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Kein Treffer->Haenge an bei 5 W:Cache Pointer: 6
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Kein Treffer->Haenge an bei 6 W:Cache Pointer: 7
W:Searching Cache... W:Treffer bei 6
W:Searching Cache... W:Treffer bei 6
W:Searching Cache... W:Treffer bei 6


2.ter Lauf
W:Searching Cache... W:Treffer bei 0
W:Searching Cache... W:Treffer bei 0
W:Searching Cache... W:Treffer bei 1
W:Searching Cache... W:Treffer bei 2
W:Searching Cache... W:Treffer bei 2
W:Searching Cache... W:Treffer bei 3
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Treffer bei 4
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Treffer bei 5
W:Searching Cache... W:Treffer bei 6
W:Searching Cache... W:Treffer bei 6
W:Searching Cache... W:Treffer bei 6
W:Searching Cache... W:Treffer bei 6

[foobar (Gast)]

> Muss trotzdem auf 0 prüfen, da MOD % ja 0 ergeben kann bei Überlauf
> und dann auf jeden Fall geschrieben werden muss.

Wenn pnt auf 0 ist, hast du gerade geschrieben.  Das Durcheinander kommt 
daher, dass du mMn an der falschen Stelle incrementierst.

Kurz und Knapp™:

static struct { uint16_t addr; uint8_t data; } cache[128];
static int used = 0;

void EEIntCacheFlush()
{
    for (int i = 0; i < used; ++i)
        EEPROM.update(cache[i].addr, cache[i].data);
    used = 0;
}

static int find(uint16_t addr, int read_it)
{
    for (int i = 0; i < used; ++i)
        if (cache[i].addr == addr)
            return i;

    if (used == sizeof(cache)/sizeof(*cache))
        EEIntCacheFlush();

    cache[used].addr = addr;
    cache[used].data = read_it ? EEPROM.read(addr) : 0;
    return used++;
}

uint8_t EEIntCacheRead(uint16_t addr)
{
    return cache[find(addr, 1)].data;
}

void EEIntCacheWrite(uint16_t addr, uint8_t data)
{
    cache[find(addr, 0)].data = data;
}

Sinnvoll finde ich es trotzdem nicht ;-)

[Gerhard O. (gerhard_)]

Wenns interessiert: Alternativ gibt es auch EERAMs und Magneto Resistive 
Speicher mit einige hundert Trillionen Schreibzyklen. Sollen elektrisch 
Buskompatibel sein. Vielleicht erspart diese Möglichkeit unnötig 
komplizierte FW.

Die EERAMS transferieren den RAM Inhalt bei Verlust von Vdd in ein 
Schatten EEPROM. Ein lokal angeschlossener C stellt die Energie dazu 
unabhängig von der Stromversorgung bereit. Diese EERAMS haben 
unbegrenzte Schreibzyklen.

Siehe hier:

https://www.microchip.com/design-centers/memory/serial-eeram

https://www.digikey.ca/catalog/en/partgroup/serial-mram/1501

[Olaf (Gast)]

> Sollen elektrisch Buskompatibel sein.

Aber vor dem Einsatz den Strombedarf in allen Betriebszustaenden 
vergleichen..

> Vielleicht erspart diese Möglichkeit unnötig komplizierte FW.

...sonst koennte es zu einer interessanten Firmware kommen. .-)

Olaf

[Christian J. (Gast)]

foobar schrieb:
> Sinnvoll finde ich es trotzdem nicht ;-)

ich auch nicht :-) Daher spare ich mir das Ganze und tausche einfach den 
2,95 Eur Arduino pro Mini, wenn was kaputt gehen sollte. Trotzdem danke 
dass du dir die Mühe mit dem Code gemacht hast.

[foobar (Gast)]

Och, die Idee, die Lebensdauer des EEPROMs zu verbessern, ist ja nicht 
verkehrt.  Ich denke nur, dass dieser Ansatz nicht der richtige ist :-)

[Christian J. (Gast)]

Gucke mal doooo:

https://codeahoy.com/2017/08/11/caching-strategies-and-how-to-choose-the-right-one/

Ich spendier heute abend mal einen Pro Mini Arduino und lasse den mal 
nudeln, bis die erste Zelle tot vom Baum fällt. Gucken was dabei heraus 
kommt. In die Ecke stellen und laufen lassen.