Thema: Speicherideen

[Martin Erhardt]

Ich sammele in diesem Post einige Ideen zur Verwaltung von Speicher.
Ich gehe hier von einer Speicherverwaltung mit Bitmap aus, die ich für performant(und vorallem dingen fehlersicher genug halte !!!)

1. Dynamische Arrays/Puffer im Kernel:

   Es ist in Betriebsystemen häufig der Fall das man eine Liste aus Daten(strukturen) erstellen muss(zb. eine Liste aus Thread, Prozess oder User structs).
   Wenn diese mehr als 4kb speicher einnehmen könnte man mit krealloc den folgenden Speicherblock alloziieren, was ist wenn der aber schon belegt ist, dann müsste man mit kmalloc(neuesize) einen neuen Bereich alloziieren und die Daten dort hinkopieren. Dann müsste man aber auch alle Pointer auf den Array ändern,was bei vergessen schnell zu fehlern führen kann.

   Ich habe hier ein mehrstufiges System im Sinn:
   Zunächst wird ein Block für einen Pointer alloziiert. Dieser zeigt auf eine Dynamische liste aus Puffer structs diese bestehen aus:
       1. einer ID mit der man den Buffer identifizieren kann
       2. einem Pointer
       3. der Größe
   Soll ein Buffer vergrössert werden und krealloc geht nicht, alloziert man wie besagt einen neuen Speicherbereich und kopiert die Daten dorthin; man braucht aber nur den Ptr in dem Puffer struct zu ändern weil nur dieser als Pointer benutzt  werden sollte. Wird die dynamische Liste aus Puffer structs größer als 4k ändert man den zuerst erwähnten Pointer.
  Der Vorteil daran ist ,dass man z.b nicht für jeden einzelnen task 4kb alloziieren muss wie im Beispielkernel und dass man über einen Offset oder Index direkt auf einen einzelnes Element zugreifen kann. Außerdem verhindert dass Verfahren recht effektiv Bufferoverflows.

 
2. Kopieren/bewegen großer Datenmengen auf der RAM über DMA und externe Datenträger

   Meine memmove und memcpy funktionen kopieren den Speicher ganz konventionel mit XCHG und einer Schleife.
   Das ist sehr langsam(1 ganze sekunde[!] fur 4kb).
   Natürlich könnte ich das mit AVX achtmal schneller machen, aber das allein ist mir zu spießig  

   Man könnte wenn ein beschreibbarer externer Datenträger verfügbar ist, den SATA Host Controller oder USB Hub dazu nutzen den zu bewegenden Speicherbereich erst in eine Datei in dem Datenträger und dann zurück in das zielgebiet zu kopieren.
   Der clue daran:
   Die CPU(s) selbst werden kein bisschen zusätzlich belastet Der Host controller,der auf das kopieren großer Datenmengen ausgelegt ist macht alles selber über DMA.
   Problem:
   Wenn man auf der CPU einfach fortfährt könnte es zu RaceConditions kommen weil die CPU beispielsweise bereits auf die kopierten Speicherbereich zugreifen will, bevor alles kopiert ist.
   Damit man nicht doch auf der CPU warten muss bis alles fertig ist würde ich einfach den Registersatz des Kernels speichern und den Thread wegschedulen. Ich würde ihn dann so lange weggeschedult lassen bis alles fertig ist und DANN(wenn alles kopiert ist) den Registersatz wieder herstellen.
   
   Mit memset wäre das dann ganz ähnlich.
   Ich habe DMA, PCI,USB und SATA alles noch nicht implementiert, wüsste also gern was ich verändern muss, Ich finde einfach die Idee cool die Speichercontroller so umzufunktionieren.

Es wäre gut zu wissen wie und ob meine Ideen in Linux, FreeBSD oder tyndur umgesetzt sind und ob man noch was verbessern kann

[Martin Erhardt]

Reaktionen sind jetzt ausdrücklich erwünscht 

[Jidder]

1. Dynamische Arrays/Puffer im Kernel:

Ich weiß nicht genau, ob du die Struktur deiner Speicherverwaltung ganz durchdacht hast. Soll das Konzept den Mangel in der Speicherverwaltung im Beispielkernel ausgleichen, dass selbst für die kleinsten Objekte immer 4 kB reserviert werden?

Wenn ja, dann muss ich dazu sagen, dass der Beispielkernel auf Einfachheit ausgelegt ist. Häufig ist die Speicherverwaltung so strukturiert:
- phyische Speicherverwaltung
- virtuelle Speicherverwaltung
- Heap (malloc/free oder spezialisiertere Allokatoren)
Der Beispielkernel implementiert eigentlich nur die physische Speicherverwaltung. Der virtuelle Speicher wird nur in Teil 9 besprochen, und die virtuelle Speicherverwaltung wird dem Leser als Aufgabe überlassen. Ein Heap wird gar nicht implementiert und stattdessen wird die physische Speicherverwaltung der Einfachheit halber dafür verwendet. Wenn eine anständige Speicherverwaltung in deinem Kernel haben willst, musst du die fehlenden Allokatoren implementieren. Hinweise wie die virtuelle Speicherverwaltung aussehen sollte, wird im Tutorial gegeben. Darauf aufbauend solltest du dann einen Allokator (kmalloc/krealloc/kfree) für den Heap implementieren. Erst dieser Allokator sollte für Datenstrukturen verwendet werden, weil nur er frei von dem Konzept der 4-kB-Seiten ist.

Die Speicherverwaltungen bauen aufeinander auf: kmalloc schaut in irgendwelchen Datenstrukturen nach, ob irgendwo x Bytes frei sind. Wenn nicht werden von vmm_alloc genügend neue Pages angefordert und das fordert dann wiederrum von pmm_alloc Speicher an. Aber in den meisten Fällen hat kmalloc noch freien Speicher übrig und kann die Anfrage selbst bearbeiten. Wenn du kmalloc für jede struct einzeln aufrufst, kannst du einfach verkettete Listen statt dynamischer Arrays verwenden. Dann musst du nie was kopieren auch keine Zeiger ändern beim kopieren.

2. Kopieren/bewegen großer Datenmengen auf der RAM über DMA und externe Datenträger

Reaktionen sind jetzt ausdrücklich erwünscht 

Kannste gerne mal versuchen, aber die CPU kopieren zu lassen sollte immer schneller sein, als über einen externen Controller zu gehen. 4 kB/s sind allerdings zu wenig und du solltest auf aktuellen Systemen in die Region von 100 MB/s oder 1 GB/s kommen ohne irgendwelchen AVX-Schnickschnack. Ich denke eher, dass deine memmove/memcpy-Funktionen nicht richtig funktionieren. XCHG ist nämlich eine Instruktion um Werte zu vertauschen. Speicher wird mit MOV kopiert. Oder schreib die Funktionen einfach in C.

[Martin Erhardt]

1. Dynamische Arrays/Puffer im Kernel:

Die Speicherverwaltungen bauen aufeinander auf: kmalloc schaut in irgendwelchen Datenstrukturen nach, ob irgendwo x Bytes frei sind.

Ich verwende kmalloc für meine physische Speicherverwaltung und nicht den Heap.

[Martin Erhardt]

Kannste gerne mal versuchen, aber die CPU kopieren zu lassen sollte immer schneller sein, als über einen externen Controller zu gehen. 4 kB/s sind allerdings zu wenig und du solltest auf aktuellen Systemen in die Region von 100 MB/s oder 1 GB/s kommen ohne irgendwelchen AVX-Schnickschnack. Ich denke eher, dass deine memmove/memcpy-Funktionen nicht richtig funktionieren. Speicher wird mit MOV kopiert. Oder schreib die Funktionen einfach in C.

Neneh Ich hab das auch in C realisiert ist aber trotzdem sau lahm, aber AVX mach ich auf jeden Fall weils durch die breiteren Register so oder so schneller ist. Das man mit mov auf die RAM zugreifen kann wusste der ASM NOOB gar nicht.
Code: https://docs.google.com/file/d/0B-x3QNiQfEeCNU1ibHpIc2hMQWM/edit

Testen kann man mit der Funktion kpmm_test() in src/kernel/mm/pmm.c

Also wieso is des dann so lahm 

[Jidder]

Ich hab es nicht ausprobiert, aber in dieser Zeile in kpmm_test() gibt es einen Buffer-Overflow:

Code: [Auswählen]

memcpy((void*)((uintptr_t) (vlarge_puffer_ptr)+j*PAGE_SIZE),&vlarge_puffer_src, vlarge_puffer_size);
vlarge_puffer_size hat den Wert 81920000, aber vlarge_puffer_src ist nur 4096 Bytes groß und du liest über das Ende hinaus. Wenn du in vlarge_puffer_ptr reinkopierst, schreibst du außerdem über das Ende hinaus wenn j > 0. Vielleicht meintest du PAGE_SIZE statt vlarge_puffer_size. Wenn das Kopieren trotzdem fehlerfrei (das heißt ohne Konsequenzen durch den Buffer Overflow) gelingt, und 1 Sekunde dauert, bist du bei 80 MB/s, was gar nicht mal so langsam ist.

Dein Messverfahren hat allerdings noch das Problem, dass du in der Schleife Ausgabefunktionen hast. Die verfälschen die Messung und du solltest deren Effekt nicht unterschätzen. Je kleiner die memcpys desto größer der Fehler.

[Martin Erhardt]

Genau das wars es hat jetzt nur noch einen SekundenBruchteil gedauert.