Nachrichten

521

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 08. November 2010, 16:58 »

Er ist der VMM, er kümmert sich um die Verwaltung des virtuellen Speichers. Also weiß er, wo da im Adressraum etwas frei ist...

Und wo speichert er diese Infos? Die nächste Frage wäre dann woher er den Speicher bekommt das er diese Infos Speichern kann.
Wie gesagt, alles im Vorraus zu allokieren ist nicht praktikabel.

der VMM kümmert sich um die Umrechnung von physischen Adressen in virtuelle Adressen

Nicht wirklich, das macht die MMU, wie du dann weiterschreibst steuert der VMM die MMU. Die eigentliche Aufgabe des VMM ist es, zu wissen welche Bereiche, in einem Adressraum, noch frei sind.

Also gut nur mal so als Bsp. wie ein Pseudo-Code von einem malloc() aussehen könnte:

Code: [Auswählen]

void *malloc(uint32t size) {
 void *addr= guckeObFreierBlockVorhanden(size + 4); //man kann das in einer Liste machen

 if(!addr) {
  void *newMem= vmmGetVirtMem((size + 3 & ~0xFFF) + 0x1000); //das in der Klammer aligned size+4 auf Page-Größe
  packeNeuenSpeicherBlockInList(newMem);
  addr= guckeObFreierBlockVorhanden(size);
 }

 *((uint32t *)addr)= size; //ich merke mir wie groß der rausgegebene Block ist

 return addr + 4; //und gebe die Addr auf den eigentlichen Speicher an den User weiter
}

Der malloc()-Code hat in dem Sinne erstmal gar nichts mit dem VMM zu tun, sondern er benutzt ihn. Wenn du als User mit 4KB-Pages an Speicher klarkommst, könntest du auch malloc() gar nicht benutzen. malloc() ermöglicht dir einfach das du dich nicht darum kümmern brauchst.

Der SlabAllocator funktioniert ähnlich, auch er holt sich immer ein vielfaches der Page-Größe vom VMM (was anderes bekommst du auch nicht und das ist der Unterschied zu malloc()) und gibt dann einen Pointer auf ein freies Objekt raus, hat auch nichts mit dem VMM zu tun.

Kein Grund, mir Inkompetenz vorzuwerfen.

Sorry, aber nachdem was du geschrieben hast, hast du halt nicht verstanden wie das normalerweise so miteinander funktioniert.

Außerdem bin ich auf Arbeit und habe nebenher noch andere Dinge zu tun. Code analysieren kostet halt Zeit.

Du darfst auf Arbeit nebenbei surfen

Ich meinte damit auch gar nicht das du den Code schnell mal analysieren sollst. Es ging mir darum, das nur weil ich den Code in meinem OS verwende, muss man sich nicht mit OS Programmierung auskennen, um den Code zu verstehen.

Ich kann mir mit der folgenden Aussage jetzt ziemlichen Ärger einhandeln, aber was solls

Ich denke als Programmierer sollte man schon so grundlegende Datenstrukturen wie Bäume (auch ausgeglichene) kennen. Ich weiß nun nicht ob du beruflich programmierst oder nicht (wenn nicht dann schiebe ich das jetzt mal auf noch keine Erfahrung), aber Bäume gibt es schon ziemlich lange
Auch ist es keine Ausrede in welcher Sprache du das mal geschrieben hast, wer programmieren kann, dem ist die Sprache (nicht das Paradigma!) egal.

und die Compilerinterna vom gcc kenne ich auch nicht.

Ich denke mal du spielst auf likely/unlikely an? Ich hab mal "gcc likely" bei google eingegeben und gleich die ersten beiden Ergebnisse waren dahingehend sehr hilfreich

Lässt sich das Mergen nicht durchführen, indem du den Baum mit den Adressen als Suchschlüssel stupide in-order traversierst und, wenn du deine freizugebende Adresse findest, das vorhergehende und das nachfolgende Element vergleichst? (Die drei Elemente fallen beim Traversieren eh raus.) Wenn du bei jeder Freigabe jeweils deinen Block mit dem vorhergehenden und nachfolgendem Block zusammenfügst (sofern möglich), brauchst du nicht den gesamten Baum durchsuchen, sondern nur diese drei Blöcke und die Wege dazwischen und du hast trotzdem die größtmöglichen Blöcke.

Ich bin mir jetzt nicht sicher ob ich dich verstanden habe, aber in einem Baum muss das vorhergehende (der Vater) Element (Node) nicht auch der Vorgänger sein!

Du bringst mich allerdings auf die Idee, das ich gleichzeitig gucken kann, ob ich einen Bereich am Ende oder am Anfang gefunden habe, mit dem ich mergen kann (das mach ich momentan in 2 Baum-Traversierungen). Denn wenn ich eins gefunden haben kann der eventuell andere Bereich nur noch in den Kind-Knoten davon liegen. Damit würde ich mir eine weitere Traversierung sparen.

522

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 08. November 2010, 13:52 »

void *kmalloc(size_t size, int flags) alloziiert Speicher der Größe size, wobei flags angibt, ob es User-/Kernel-/Interrupthandler-Speicher ist.

Ein kmalloc ist nichts anderes als ein malloc! Der einzige Unterschied ist, das er im Kernel benutzt wird.

Der physische Speicherverwalter (ab hier PMM) nimmt physischen Speicher, arbeitet mit physischen Adressen und kann nur PAGESIZE-große (=4k, 2M, 4M, ...) Blöcke verwalten. Diese Blöcke sind also physische Speicherblöcke mit RAM dahinter.

Wo läuft der Code des PMM und wo speichert der PMM seine Daten?

Der virtuelle Speicherverwalter (ab hier VMM) nimmt diese physischen Speicherblöcke, die ihm vom PMM zur Verfügung gestellt wurden und verwaltet die. Er implementiert ein kmalloc(). Er darf kmalloc() niemals aufrufen. Wenn er für sich selbst Speicher braucht, muss er den PMM danach fragen und kann auch nur physische Speicherblöcke für sich selbst verwenden. Diesen Blöcken darf er gerne virtuelle Adressen geben und damit weiterarbeiten.

Woher weiß der VMM welche virtuelle Adresse frei ist? Nach deinem Verständnis ist virtuelle Adresse == physischer Adresse. Dem ist aber fast nie so, dafür gibt es ja Paging und genau deswegen braucht man ja einen PMM und einen VMM.

Der Slab-Allocator sitzt oben auf dem VMM drauf und verwaltet Objekte. Er darf kmalloc() benutzen und mit dem Speicher tun, was immer er möchte.

Warum sollte der SlabAllocator kmalloc() benutzen? Der SlabAllocator holt sich seinen Speicher vom VMM und nur mal so, in Linux steckt hinter dem kmalloc() der SlabAllocator.

Warum? Ein kmalloc() ist eng mit der Speicherverwaltung verbunden, wird also vom VMM bereitgestellt. Du kannst kmalloc() nicht vom VMM trennen, ohne zirkuläre Abhängigkeiten und damit Extra-Codepfade zu bekommen.

Sorry, aber du hast nicht verstanden was ein kmalloc() ist und was es macht. Genauso weißt du eigentlich nicht was ein VMM macht und wie Paging funktioniert.

Tut mir Leid, dass ich derzeit  kein OS auf die Beine stelle. Ich habe dazu weder Zeit noch Lust, dennoch Interesse daran.

Naja, der Code hat erstmal gar nichts mit einem OS zu tun und ich bin daher davon ausgegangen das du theoretisch was vom Programmieren weißt, es aber praktisch noch nicht wirklich gemacht hast.

Der Code verwendet im Endeffekt einfach nur 2 Bäume um seine Daten zu organisieren und dafür muss man sich nicht mal im entferntesten mit einem OS beschäftigt habe.

523

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 08. November 2010, 11:46 »

Jein. Der VMM darf kein kmalloc() benutzen, weil er ein kmalloc() implementieren soll. Du musst aber trotzdem nichts spezielles bauen, denn dein virtueller Speichermanager baut auf dem physischen Speicherverwalter auf und kann diesen auch selbst benutzen. Ich sehe keine besondere Einschränkung, wenn im VMM nur ein getPhysMem() existiert, was nur ganze Pages bereitstellen kann. Mit virtuellen Adressen kannst du im VMM ohnehin nichts anfangen, weil du diese ja erst bereitstellst.

Was macht denn ein kmalloc()? Der weiß wieviel Speicher er noch hat und wenn dieser nicht mehr reicht dann wird der VMM aufgerufen. Also müsste auch ein kmalloc() was vom VMM implementiert (hört sich doof an und weiß auch nicht so richtig was du damit meinst) ist den VMM aufrufen.
Desweiteren kannst du ja so nicht mal eben deinen kmalloc() austauschen und das ist ja auch doof.

Warum sollte der VMM selbst einen VMM nutzen müssen?

Woher soll denn der VMM wissen welche virtuellen Bereiche frei sind und welche nicht, wenn er es nicht irgendwo speichert? Um diese Infos irgendwo zu speichern, brauchst du Speicher (virtuellen und physischen). Um das ganze möglichst flexibel zu machen, sollte man nicht immer schon den ganzen Speicher für den worst-case allokieren (dann würde dein OS sehr sehr viel Speicher brauchen um nur starten zu können und zur Laufzeit wird das pro Prozess immer und immer mehr).
Also muss der VMM die Möglichkeit haben nur Objekte zu allokieren und dafür kann es (und wird es) notwendig sein das du nen freien virtuellen Bereich brauchst und dafür brauchst du wieder den VMM.

Was ist unlikely() ? Das habe ich schon öfter gesehen und kann mir darunter garnichts vorstellen...

Sorry, wenn ich mal so treist frage, aber kannst du englisch?

Likely = Wahrscheinlich
Unlikely = Unwahrscheinlich

Das sind Makros um dem Compiler mehr Infos zum Optimieren zu geben, da ich ja besser als er weiß welche Pfade wahrscheinlicher sind als andere.

Schaue ich mir eventuell nachher an, ist aber Praxis und die kann ich nicht.

Das ist immer schlecht. Ich (persönlich) finde ja das man nur mit Praxis weiter kommt als nur mit Theorie!

524

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 08. November 2010, 11:35 »

Wenn ein Userspace-Prozess einen Syscall aufruft und damit in den Kernel springt, kann der Kernel trotzdem ohne weiteres auf die Userspace-Ressourcen zugreifen? Was, wenn sich die Adressräume überschneiden?

Ja, der Kernel kann dann einfach per Pointer (auch wenn man das so einfach nicht machen sollte) auf UserSpace Sachen zugreifen und es kann nicht zu Überschneidungen kommen, da der User 3GB und der Kernel 1GB (z.B. unter Linux), von den vorhanden 4GB Adressraum, bekommt.

Was muss alles im Kernel-Adressraum liegen, zusätzlich zu Code&Daten, aus denen der Kernel besteht? (Mir fallen da konkret der lineare Grafikspeicher und der PCI-Adressraum ein. Was noch?)

Kommt ganz darauf an von was für einem Kernel wir hier sprechen. Ansonsten reicht alles was man für IPC, VMM, PMM, IRQ und halt Task/Thread-Sachen braucht.
Denn Rest kann man ja im UserSpace machen.

525

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 07. November 2010, 13:07 »

So ich habe mal etwas gecodet und ich bin noch nicht ganz mit meiner mapFree-Funktion zufrieden. Ich finde sie ist in dem Zustand zwar elegant geschrieben, aber der Algo ist nicht die schnellste Möglichkeit ein Segment/Bereich wieder freizugeben.

Optimierungen die mir schon bekannt sind (sparen Allocator- und Baumänderungs-Aufrufe):

• Anstatt jedes Mal die nodeStart aus dem Baum zu entfernen, wird sie drin gelassen und erst entfernt falls man 2mal mergen kann
• nodeSize kann auch einmal "behalten" werden und nur falls es schon eine Node mit der Größe gibt wird sie freigegeben

Erstmal der Code:

Code: [Auswählen]

uint32t mapFree(struct map_t *map, uint32t start, uint32t size) {
struct boundaryTag_t *tag= 0, *merge;
struct avlNode_t *nodeStart, *nodeSize;

if(unlikely(start < map->start || (start + size) > (map->start + map->size)))
goto error0;
//look if we can merge a segment before/after and look if the segment is used
spinAcquire(&map->lock);

nodeStart= map->freeStart;
//we first search for a segment after ours
while(likely(nodeStart)) {
merge= nodeStart->obj;
//is the start or the end in this segment
if(unlikely((start >= merge->start && start < (merge->start + merge->size)) || ((start + size) > merge->start && (start + size) < (merge->start + merge->size))))
goto error1;
//is our end == the start of the node segment
if(unlikely((start + size) == merge->start)) {
//we need to remove the original tag out of the size-tree
nodeSize= avlFind(map->freeSize,merge->size,&mapSizeComparatorVal);
//shouldn´t happen, just to be sure
if(unlikely(!nodeSize))
goto error1;

nodeSize->obj= listRemove((struct list_t *)nodeSize->obj,(struct list_t *)merge)
//look if we need to take the size-node out of the tree and free it
if(!nodeSize->obj) {
map->freeSize= avlDelete(nodeSize);
map->freeNode(nodeSize);
}
//get the start-node out of the tree and free it
map->freeStart= avlDelete(nodeStart);
map->freeNode(nodeStart);
//actualize the new segment, given size and set tag to the just merged tag
merge->start= start;
merge->size+= size;
size= merge->size;
tag= merge;

break;
}
//if our segment comes after the node segment then go right
if(start > merge->start)
nodeStart= nodeStart->right;
else
nodeStart= nodeStart->left;
}
//we found no segment after us for merging, now we search for a segment before us
nodeStart= map->freeStart;

while(likely(nodeStart)) {
merge= nodeStart->obj;
//is start == merge->start + merge->size
if(unlikely(start == (merge->start + merge->size))) {
//we need to remove the node segment out of the size-tree
nodeSize= avlFind(map->freeSize,merge->size,&mapSizeComparatorVal);
//shouldn´t happen, just to be sure
if(unlikely(!nodeSize))
goto error1;

nodeSize->obj= listRemove((struct list_t *)nodeSize->obj,(struct list_t *)merge)
//look if we need to take the size-node out of the tree and free it
if(!nodeSize->obj) {
map->freeSize= avlDelete(nodeSize);
map->freeNode(nodeSize);
}
//get the start-node out of the tree
map->freeStart= avlDelete(nodeStart);
//actualize the tag start, tag size, set nodeStart to our tag and free the merge tag
tag->start= merge->start;
tag->size+= merge->size;
nodeStart->obj= tag;
map->freeTag(merge);

break;
}
//if our segment comes after the node segment then go left
if(start > (merge->start + merge->size))
nodeStart= nodeStart->left;
else
nodeStart= nodeStart->right;
}
//if tag isn´t set, alloc a new one
if(!tag) {
if(unlikely(!(tag= map->allocTag())))
goto error1;

tag->start= start;
tag->size= size;
}
//if nodeStart isn´t set, alloc a new one
if(!nodeStart) {
if(unlikely(!(nodeStart= map->allocNode())))
goto error2

nodeStart->obj= tag;
}
//look for a node with the same size
nodeSize= avlFind(map->freeSize,size,&mapSizeComparatorVal);
//insert the tag into the size-tree
if(!nodeSize) {
if(unlikely(!(nodeSize= map->allocNode())))
goto error3;

nodeSize->obj= listAddFirst((struct list_t *)tag);

map->size= avlInsert(map->size,nodeSize,&mapSizeComparatorNode);
} else {
nodeSize->obj= listAddTail((struct list_t *)nodeSize->obj,(struct list_t *)tag);
}
//now insert the tag into the start-tree
map->freeStart= avlInsert(map->freeStart,nodeStart,&mapStartComparatorNode);
end0:
spinRelease(&map->lock);

return 1;
error3:
map->freeNode(nodeStart);
error2:
map->freeTag(tag);
error1:
spinRelease(&map->lock);
error0:
return 0;
}

Ich hoffe die Funktionsaufrufe sind selbsterklärend, wenn nicht fragen.

Ich hätte jetzt gerne gewusst ob noch jemand ne Optimierung des Algos einfällt. Blöd ist halt das der Baum zweimal durchgegangen werden muss (einmal um nach einem Bereich vor uns und einmal um nach einem Bereich nach uns zu suchen mit dem wir mergen können) und wie schon gesagt, die zuvielen Allocator-Aufrufe.

Es kann auch sein das noch Fehler drin sind, ich habe den Code noch nicht getestet!

526

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 06. November 2010, 19:07 »

Genau das möchte ich auch tun. Nur mit einer kleinen Abwandlung im SlabAllocator für die Heap-Objekte des Kernels, der SlabAllocator holt die doch immer aus einem (oder mehreren) großen Block und wenn dort der Platz fast aufgebraucht ist dann wird ein Flag gesetzt aber die Heap-Anforderung des VMM (z.B. nach einem neuen Baum-Element für die VMM-Verwaltungsstrukturen) trotzdem noch bedient (es ist ja noch ein kleiner Rest übrig). Wenn der VMM dann fertig ist mit seiner Arbeit sollte er als letztes den VMM-Lock abgeben (der VMM ist eine zentrale Ressource die IMHO nur einmal gleichzeitig benutzt werden kann) aber unmittelbar bevor der Lock freigegeben wird wird noch geprüft ob das Heap-SlabAllocator-NearEmpty-Flag gesetzt ist und dann für den SlabAllocator noch mal ein dicker Brocken alloziert, das kann gemacht werden weil der VMM von seiner eigentlichen Arbeit ja nicht mehr in einem kritischen Zustand ist. Mit diesem Trick kann ich den Kernel-Heap voll dynamisch verwalten und auch der VMM kann den Kernel-Heap benutzen um dort seine Verwaltungsstrukturen zu holen und trotzdem kann der Heap aus großen Blöcken vom VMM geholt werden. Der Heap würde also die Verwaltungsstrukturen die ihn beschreiben selber enthalten.

Sowas in der Art habe ich probiert und das hat auch funktioniert, bis ich zuviele CPUs (unter QEMU) hatte. Problem ist ja, das wenn du als VMM den SlabAllocator aufrufst und dein Objekt bekommst, wieder eine andere CPU den SlabAllocator aufrufen kann und da reicht dann so ein Flag nicht mehr aus (ich habe halt auch mit 255 CPUs getestet), weil bei zu vielen CPUs reichen die Objekte in einem Slab nicht mehr aus um alle CPUs bedienen zu können (vorallem nicht wenn du den SlabAllocator in seiner aktuellsten Abwandlung einsetzt).

527

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 06. November 2010, 18:01 »

Warum liegt der Kernel üblicherweise im virtuellem Adressraum eines jeden Prozesses?

Performance! Und bei einer 64bit Architektur musst du den Kernel auch nicht in einen anderen Adressraum packen, da du ja genug hast.

Der Prozess fordert einen ausgerichteten Buffer vom Kernel an und merkt sich dessen Zeiger. Dann füllt er diesen mit Daten, setzt die Register (Funktionsnummer, Zeiger auf Buffer, Buffergröße) und ruft dann einen Syscall auf (z.B. "int 80h"). Kann der Kernel dann mit diesem Zeiger etwas anfangen, also den entsprechenden Bereich in seinen eigenen Adressraum mappen und verarbeiten?

Frage wäre was dir das bringen soll, ob du die Daten nun über den Stack oder über einen solchen Buffer (der mehr Speicher verbraucht als wenn man das alles übern Stack macht) an den Kernel weitergibst sollte fast egal sein.

Bzw. die Idee an sich gefällt mir (pro Thread ein 4KB Buffer für Syscalls, aber das wäre halt eigentlich nen tierischer Overhead, denn wieviel Speicher wird man wohl max pro Syscall brauchen, 128Byte?), aber warum willst du diesen Buffer auch im KernelSpace nochmal mappen? Du kannst doch vom KernelSpace aus schon auf den UserSpace zugreifen.

Es gibt ein Bsp. wo das wahrscheinlich sogar so gemacht wird. Wimre dann hat bei MacOSX der Kernel seinen eigenes PageDir und ist somit nicht in jeden Prozess gemappt, sondern da ist immer nur ein kleiner Stub, der das PageDir in den Kernel wechselt.

528

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 06. November 2010, 17:55 »

Freigeben kann man Ressourcen aber nur dann, wenn man sie besitzt oder liege ich da falsch? Wenn dein Kernel sich die Löcher selbst greift, kann nur er sie wieder freigeben und genau das tut er ja nie...

Ich sags mal so, mein Kernel stellt eine Funktion zur Verfügung womit du als User wieder virtuellen (und damit verbunden physischen) Speicher wieder freigeben kannst.
Da ich nicht Buch führe wer welche Ressource (was die Map allgemein und die virtuellen Bereiche speziell betrifft) hat, kann ich auch nicht nachprüfen ob jemand eine Ressource freigibt, die ihm gar nicht gehört. Im Kernel sollte das nicht passieren, da wäre es ein Bug, aber wenn der User sowas probiert sollte man das schon abfangen können.

Um auf das Bsp. mit dem Freigeben von virtuellem Speicher zurück zu kommen, so könnte der User einfach diesen Syscall aufrufen mit einer Adresse die er gar nicht "besitzt" sondern die ich als OS "besitze" (die aber im UserSpace sind) und genau das will ich verhindern.

Da der VMM selbst die Hoheit über den virtuellen Adressraum hat, muss er seine eigenen Datenstrukturen ja nicht in den gleichen Büchern führen, wie die restlichen Datenstrukturen.

Äh, das ist im Prinzip genau das was ich mache.

Der VMM kümmert sich vollautonom um den virtuellen Speicher und benutzt selbst den PMM für den Zugriff auf den physischen Speicher.

Ist ja fast wieder das selbe wie oben. Auch ich nutze den SlabAllocator nicht (mehr) für den VMM, aber den Allocator den ich mir geschrieben habe, funktioniert genauso wie der SlabAllocator (weil der einfach besser ist).

Das ist nicht einfach, nicht sauber und führt zu Problemen, wenn du Teile davon austauschen möchtest.

Ich behaupte mal dieser Satz ist quatsch. Denn er impleziert ja (so wie ich ihn verstehe) das du alles so allgemein wie möglich halten musst und damit dürftest du den SlabAllocator ja sowieso nie effizient (denn man kann den SlabAllocator auch für malloc/free einsetzen, aber das ist sehr unschön) einsetzen und das wäre ja quatsch.
Irgendwelche Komponenten auszutauschen wird immer irgendwo zu Problemen führen.

529

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 06. November 2010, 15:39 »

Damit bist du doch einmal das Problem der Löcher los (die sind nie frei) und kannst gleichzeitig immer den ersten freien Descriptor (das erste Baumblatt) zurückgeben.

Es geht mir nicht darum das man diese "Löcher" allokieren könnte, sondern das man sie freigeben kann und dann könnten sie allokiert werden!

Ein Programm darf nur Ressourcen in Anspruch nehmen, die es vom System angefordert und zugewiesen bekommen hat - und auch nur diese Ressourcen darf es wieder freigeben. Löcher werden aber niemals zugewiesen, können also auch nicht freigegeben werden. Und die Verwaltung der zugewiesenen Ressourcen obliegt dem Programm selbst, also hat sich der Kernel nicht drum zu kümmern.

Du vertraust einem Programm aber ganz schön. Denn dann würde es auch keine Buffer-Overflows geben, wenn die Programme nur soviele Daten "schicken" wie sie dürfen!
Es geht um das freigeben von Speicher/virtuellem Speicher und da gibt es Sachen im UserSpace die ich gerne davor schützen würde.
Zumal sich mein Kernel wahrscheinlich mehr um den UserSpace kümmert als das normalerweise der Fall ist.

Achso. Dann ist das Problem im Design enthalten und nicht lösbar... zirkuläre Abhängigkeiten sind für mich schlechtes Design. wink Erklärt aber dein Problem.

Dann wäre meine Frage wie du das Problem lösen willst, das der VMM Datenstrukturen dynamisch allokiert und damit er das machen kann muss er ja wieder (irgendwann) auf den VMM zugreifen.
Du brauchst also ne Möglichkeit im VMM Speicher zu allokieren ohne das du den VMM dazu brauchst.

Dafür wäre übrigens der Thread wo ich mein VMM Design vorgestellt habe nicht schlecht.

Klingt kompliziert.

Nicht wirklich, ich hab halt nen bestimmten Bereich (am Ende des KernelSpace) von 8MB (glaub ich, habe jetzt nicht nachgesehen) wo in jedem Prozess andere physikalische Pages gemappt sind und aus diesem Bereich hole ich mir die Datenstrukturen für den VMM (der für den UserSpace zuständig ist).

Theoretische Zwischenfrage: Ist es möglich, in den Adressraum jeden Prozesses nur eine einzelne Page einzublenden, die nur eine IPC-Funktion enthält und auf diese Weise Kernelfunktionen bereitzustellen?

Das musst du genauer erklären!

Meinst du das du den Funktions-Code von einer Kernel-Funktion in den UserSpace mappst und dort dann vom "User" der Code ausgeführt werden kann?
Wenn ja, wird nichts werden, weil du dann ja auch die Datenstrukturen mit in den UserSpace mappen musst und dafür muss genug freier virtueller Speicher vorhanden sein, dann kommt noch hinzu das du den Speicher mit den Datenstrukturen erstmal finden musst und du erlaubst dem User damit nicht nur deine Daten lesen zu können, sondern auch noch zu schreiben und dann kannst du das Konzept des getrennten Kernel- und UserSpace gleich abschaffen.

530

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 06. November 2010, 14:44 »

Mein Ansatz war, dass jeder Prozess mehrere Threads haben kann, die immer durchnummeriert werden, es für jeden Prozess also einen eigenen ID-Raum gibt. Nur der Kernel kennt die systemweite ID des Threads, der Thread selbst nicht. Damit kann es solche leckenden ThreadIDs vom Userspace aus nicht geben.

Willst du wirklich 2 IDs für Threads vergeben, weil sich deine Erklärung so anhört und das wäre doch quatsch.
Ob du nun nen eigenen ID-Raum für Threads hast oder nicht, du brauchst nur eine ID. Denn wenn du sagst das die Prozess und die Thread IDs nur 16bit groß sind (was für 32bit Systeme vollkomen ausreichend sein sollte) dann bildest du eine globale ID aus den beiden zusammen.
Ich plane halt so das ich bestimmt mal irgendwo die Thread ID brauche.

Achso. Vor 2 Posts schriebst du nämlich, du speicherst nur die freien Bereiche. Wenn du nur die belegten Bereiche speicherst, wird das natürlich aufwendiger.

Nee, ich habe geschrieben dass das so bei meiner momentanen Implementierung ist und da wird dieser allgemeine Allocator noch nicht genutzt.

Bei dem vorgeschlagenen allgemeinen Ressourcen Allocator sollen nur die freien Bereiche gespeichert werden.

Mein Gedanke ist, dass der Kernel die Löcher als belegt markiert und sie nie freigegeben werden dürfen. Wenn du ein solches Loch freigibst, ist das ein Bug und sollte gefixt werden, statt das Problem zu verschleiern. Je weniger Code, desto weniger Bugs.

Ich dachte da dann auch an irgendwelche "Löcher" im UserSpace, die das Programm zwar versuchen könnte freizugeben, was aber nicht passieren darf. Dagegen habe ich im moment noch keinen Schutz, aber den bräuchte man und da kannst du dann nicht so eine einfache Lösung nehmen.

Das ist schon klar. Aber die Endlosschleife entsteht doch nur Erzeugen der allerersten Datenstrukturen, weil diese Ressourcen sind und sich somit selbst verwalten. In dem Moment, wo du diese erzeugt hast, ist dein Allokator doch funktionsfähig. Also erzeugst du die statisch (bereits im Code), dann umgehst du die ganzen Schwierigkeiten.

Nope! Das Starten ist nicht das Problem, sondern die Sachen die während der Laufzeit passieren.

Ich allokieren alle Datenstrukturen dynamisch, bei mir ist in dem Sinne nichts statisch und dadurch kann es passieren das der VMM dynamisch ne Datenstruktur allokiert. Das ganze würde dann über den allgemeinen SlabAllocator-Code gemacht werden und dieser stellt fest das er keine Objekte mehr in seinem Cache hat und muss vom VMM neuen Speicher anfordern und dadurch entsteht die endlos Schleife.

Ich weiß net ob du da mit dem VMM vom Linuxkernel durcheinander kommst, denn den finde ich mal richtig scheiße Meiner funktioniert etwas anders.
Ich mappe im KernelSpace nicht 1:1 sondern bei mir passiert alles dynamisch, ich nutze also Paging auch im KernelSpace aus.

Auch habe ich in meinem KernelSpace für jeden Prozess ne Art privaten Bereich reserviert, für genau diese Datenstrukturen und nutze da dann auch nen eigenen Allocator.

Das verstehe ich nicht.

Normalerweise ist doch der KernelSpace für alle Prozesse gleich. Dem ist bei mir nicht so, ich habe nen Bereich der für jeden Prozess anders ist und aus diesem Bereich kommen die Objekte/Datenstrukturen die der VMM für den UserSpace braucht.
Dadurch verbrauche ich weniger virtuellen Speicher und könnte meinen Kernel wahrscheinlich sogar auf 512MB anstatt 1GB virtuellen Speicher beschränken.

Mach doch eine Map je Pagegröße, die du miteinander synchronisierst. Belegst du eine 4MB-Page, so werden 4MB in der 4KB-Map als belegt markiert und belegst du eine 4KB-Page, so wird in der 4MB-Map eine einzelne Page markiert. Für andere Pagegrößen gilt entsprechendes. Kostet ein bisschen RAM, sollte aber dennoch schneller sein, als alles aus einer Map mit der kleinsten Pagegröße rauszupopeln.

Allerdings weiß ich nicht, wie effizient dein jetziger PMM arbeitet. Gehe ich richtig in der Annahme, dass dein VMM sowieso ständig auf den PMM zugreift? Dann lohnt sich es wahrscheinlich trotzdem, den PMM ebenfalls in dieses Schema zu stopfen.

Ich behaupte das mein jetziger PMM schneller (wesentlich schneller) ist als es eine zusammengefrieckelte Map Variante je sein könnte.

Spart man sich zwei verschiedene Allokatoren mit verschiedenen Bugs und von Bugfixes profitieren dann alle Beteiligten.

Das ist auch eine Idee hinter diesem allgemeinen Allocator und trotzdem werde ich meinen PMM extra behandeln (das hat mehrere Gründe).

531

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 05. November 2010, 19:47 »

Sachen wie Thread-IDs sollten übrigens für jede Anwendung in einem eigenen Adressraum stattfinden, denn Threads kommunizieren nie direkt mit anwendungsfremden Threads, sondern immer nur über IPC. Der Kernel sollte solche Interna besser nicht öffentlich machen.

Es gibt aber so Sachen wie die Priorität eines Threads ändern und dafür brauchst du dann die ID und es gibt bestimmt noch andere Sachen. Es wird die Situation das ein Thread seine ID oder die eines anderen Wissen möchte (so fern er es darf) also schon geben.

Und die ProzessID wirst du irgendwann auf jeden Fall mal brauchen.

Wenn du in deinem Baum nur freie IDs speicherst, dann ist jedes Blatt des Baumes doch eine freie ID? Und die erste freie ID ist die, wenn du immer nur links abbiegst. Irre ich da? Wie gesagt, die Wiederverwertung von manchen Ressourcen wird von POSIX vorausgesetzt (wobei ich nicht weiß, inwieweit sich Anwendungen auch darauf verlassen).

Nope. Bei meiner momentanen Implementierung stehen in dem Baum z.B. Thread-Diskriptoren und jeder Thread hat ne ID. Also stehen in dem Baum nur benutzte IDs, wenn ich jetzt ne freie finden möchte (und nicht den einfachsten Fall nehme -> größte ID + 1) muss ich den ganzen Baum durchsuchen (im worst-case, obwohl der average-case auch nicht besser sein wird).

Aber warum brauchst du einen eigenen Allokator, um das für dein VMM nutzen zu können?

Um mir ne endlos-Schleife zu vermeiden. Denn der Map-Code ruft den Slab-Allocator auf, der ruft den VMM auf und der wiederrum den Map-Code und das Spiel geht wieder von vorne los.

Das lässt sich leider nicht so leicht lösen und deswegen nutze ich da nen eigenen Allocator, der nur aus nem bestimmten statischen Bereich die Objekte holt.

Auch habe ich in meinem KernelSpace für jeden Prozess ne Art privaten Bereich reserviert, für genau diese Datenstrukturen und nutze da dann auch nen eigenen Allocator.

Du unterteilst deine Map in Bereiche, indem du die Löcher vom Kernel in Beschlag nimmst. Also der Kernel sucht die Löcher im Ressourcenadressraum und markiert diese als "belegt/unswapbar" für sich selbst. Schon ist das Loch gefüllt.

Dann hast du das Prinzip nicht verstanden. Ich speichere nicht welche Bereiche in Benutzung sind und von wem, sondern nur was noch frei ist und wie groß der "Ur-Bereich" ist.

Deswegen könnte es durch einen Fehler/Bug passieren das man einfach ein solches Loch freigeben könnte. Wenn ich aber in einer Map mehrere Unter-Maps speichern könnte, dann wäre das kein Problem.

Was den PMM betrifft, wird das bei mir nichts werden (es sei denn ich nutze viele Maps, aber das lohnt sich einfach nicht), weil ich auch 4MB Pages unterstütze und mein PMM daher immer darauf achtet das er nur Pages rausgibt, so dass die größtmöglichste Anzahl an 4MB Pages frei ist.

Ansonsten kann man solch einen Allocator für viele Sachen benutzen, was natürlich den Code kleiner und robuster macht.

532

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 05. November 2010, 09:27 »

Du solltest grundsätzlich 64-Bit-Werte oder größer in deinen Strukturen verwenden, um z.B. einen ID-Adressraum oder den virtuellen Adressraum im 64-Bit-Modus abbilden zu können.

Da es im Moment eh nur unter 32bit laufen soll, ist das erstmal nicht nötig und würde unnötig Spiecherplatzverschwenden.

Wenn es mal nach 64bit portiert werden sollte, kann man das ja ganz einfach ändern.

So wie ich das verstehe, steigt der Speicherverbrauch nur mit dem Fragmentierungsgrad der Nutzung aller Ressourcen. Das heißt, am Anfang enthalten beide Bäume genau einen Eintrag (mapSegment:start=map:start, mapSegment:size=mapSegment:size), wird dann ein Teil in Anspruch genommen, so existieren je zwei Einträge ("genutzter Bereich", dahinter "freier Bereich"). Gibst du den Bereich wieder frei, dann hast du nur noch einen Eintrag, wenn du direkt zusammenfügst. Der Speicherverbrauch hält sich somit in Grenzen.

Wenn ich dich jetzt richtig verstanden habe, dann hast du mich nicht richtig verstanden

Ich will nur die Bereiche speichern, die auch frei sind, die genutzten tauchen nirgends auf! Spart Speicher und zum Nachgucken ob ein Bereich der freigegeben werden soll auch wirklich genutzt ist, brauch ich einfach nur die "Liste" der freien Bereiche durchgehen, wo sie dem Start-Wert nach sortiert sind.

Den Maximalspeicherverbrauch erreichst du also, wenn der Ressourcen-Adressraum den Aufbau "genutzt"-"ungenutzt"-"genutzt"-"ungenutzt"-... hat. Das ist allerdings äußerst unwahrscheinlich, da du z.B. IDs immer von vorne zuweist (Descriptoren nach POSIX müssen immer der kleinstmögliche sein) und Adressraum meist im Block alloziiert wird (und auch als Block freigegeben wird).

Ja (Fragmentierung) und Nein (IDs). Ich gehe jetzt mal von Task, Thread und Port IDs aus. Da wäre es schön wenn man erstmal die Liste bis zum größt möglichen Wert durchgeht und dann wieder von vorne (natürlich nur die freien) anfängt.
Das wäre deswegen schön, weil dann die wahrscheinlich sinkt, das du als Programm ne Thread-ID von nem anderen Thread gespeichert hast und mit dem irgendetwas machen willst, aber inzwischen schon ein anderer Thread die ID hat (noch schlimmer ist das bei Ports).

Im Moment ist es bei mir sogar ziemlich einfach diesen worst-Case (genutzt-frei-genutzt-...) herzustellen. Man muss einfach nur zwei Programme haben, die jeweils das andere Programm starten und sich dann selbst beenden, da ich benutzte IDs nicht wiederverwende (weil es zu aufwendig wäre nen ganzen Baum nach einer freien ID zu durchsuchen).
Das gleiche kannst du im Adressraum machen, einfach den ganzen Adressraum allokieren und dann jede zweite "Page" wieder freigeben.

Also werde ich wohl den Baum benutzen, es sei denn ich finde noch ne schönere Datenstruktur.

Ich würde diese Map dann noch dahingehend erweitern, dass man seinen eigenen Allocator (für die mapSegment_t und die node_t Strukturen) mitgeben kann. Damit erreiche ich dann, dass ich diesen Ressourcen-Allocator auch für meinen VMM nutzen kann und kein Henne-Ei-Problem erschaffe. Theoretisch könnte man den Allocator sogar für nen PMM verwenden.

Ich überlege auch, ob es Sinn macht wenn man einer solchen Map noch Bereiche hinzufügen/adden könnte (wenn z.B. bei einem PMM "Löcher" im physikalischen Speicher sind).

533

Lowlevel-Coding / Allgemeiner Ressourcen-Allocator

« am: 04. November 2010, 21:32 »

Ich arbeite gerade an einem allgemeinen Ressourcen-Allocator (inspiriert durch Bonwick und seinen SlabAllocator) und stecke ein wenig fest.

Es geht darum das man viele ja auf Integerwerte und Bereich zurück führen kann (z.B. IDs und virtuelle Speicherbereiche).

Man initialisert eine sogenannte Map mit einem Startwert und einer Größe (z.B. beim UserSpace mit 0 als Startwert und 0xC0000000 als Größe). Desweiteren gibt man noch die Größe einer Einheit an (bei virtuellen Adressen 0x1000 und bei IDs 1).

Eine Map-Datenstruktur könnte also so aussehen:

Code: [Auswählen]

struct map_t {
 uint32t start;
 uint32t size;
 uint32t sizeItem;
};

Probleme habe ich jetzt bei der Organisation der einzelnen bzw. des gesamten Bereichs einer Map. Ich würde pro Bereich folgende Datenstruktur haben:

Code: [Auswählen]

struct mapSegment_t {
 uint32t start;
 uint32t size;
};

Wenn man ein Segment/Bereich aus einer Map haben möchte ist es hilfreich wenn die freien Segmente/Bereiche de größe nach geordnet sind. Damit es im extrem Fall auch schnell geht würde ich nen Baum (AVL/Rot-Schwarz) verwenden.

Wenn man ein Segment/Bereich wieder freigibt und 2 oder 3 Segmente/Bereiche zu einem zusammengefügt werden sollen, wäre es nicht schlecht wenn sie auch nach dem Start-Wert sortiert sind, also noch nen Baum.
Auch macht es eine Sortierung nach dem Start-Wert einfacher beim zurückgeben, eines Segments/Bereichs, zu überprüfen ob das Segement/der Bereich überhaupt benutzt war.

Das ist ja alles gut und schön, aber wenn ich z.b. an IDs denke dann finde ich den Speicherverbrauch ziemlich hoch. Wenn es um virtuelle Adressbereiche geht ist der Speicherverbrauch in Ordnung (meine momentane Variante verbraucht genauso viel).

Hat jemand eine Idee wie man das mit dem Sortieren noch anders lösen könnte, so dass der Speicherverbrauch geringer wird, aber die Geschwindigkeit erhalten bleibt?

534

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 31. October 2010, 19:54 »

@svenska

Interessant der Thread, aber schon etwas älter und leider bestätigt er nur das was ich schon wusste/vermutet habe

Sowas ist natürlich schade, aber uBoot muss doch auch irgendwie etwas auf den Bildschirm bringen und da laufen ja bestimmt keine closed-source Treiber, oder?

535

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 30. October 2010, 16:56 »

Der Verbrauch sollte bei einem Board, das nur zum Spielen da ist und nicht die ganze Zeit läuft, doch egal sein.

Sicher, aber ist ja nicht nur für mich da und es ist eigentlich für irgendwelche mobile Sachen gedacht, aber die Performance sollte doch eigentlich auch für normalen Desktopgebrauch ausreichend sein.
Wie gesagt, sehr interessant das ganze.

Edit::

Zumal ich das Board dann auch dafür nutzen würde, mir Filme auf meinem Monitor anzugucken und meine Alltäglichen Surf-Sachen könnte ich auch darauf machen, also Stromsparen könnte ich/man damit schon, aber damit man den Preis wieder rausholt, müsste das Ding schon so nen PC ersetzen der 24h und ca. 100W zieht. Dann sollte sich das nach nem Jahr rechnen.

536

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 30. October 2010, 15:40 »

Wobei es doch sicher auch ARM-Boards mit PCI-Slots gibt, oder?

Nochmal zum mitschreiben es geht um ein ARM SoC, da ist nichts mit PCI-Slots und das ist auch gar nicht gewollt, wir reden hier von einem Board das max. 2W verbraucht (trifft auf das BeagleBoard zu, aber sollte auch beim PandaBoard so sein und das ist ein DualCore)!

537

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 30. October 2010, 14:05 »

Wie wär's mit ATI und Intel?

Ich meinte im Zusammenhang mit einem ARM SoC. Da dürfte zumindest Intel rausfallen und auch bei AMD wüsste ich nicht das sie so einen ähnlichen Grafikchip im Angebot haben.
Zumal es schon seinen Grund geben wird warum man bei solchen Sachen gerne PowerVR Chips nimmt.

538

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 30. October 2010, 13:36 »

Ich würde auf dem Board sicherlich nicht nur OS-Dev (wenn überhaupt) machen wollen, sondern mit Linux rumbasteln wollen... Der Grafikchip ist ein PowerVR SGX und die zeigten sich bisher sehr unwillig, Linux-Treiber oder Specs zu veröffentlichen. Es gibt einen Binary-Treiber, aber wie lange (und womit) der funktioniert.

Das ist wirklich schade und eigentlich nicht mal richtig nachzu vollziehen. Denn eigentlich sind diese Boards ja für die Community gedacht und bestimmte Hersteller müssen ja an die Specs kommen. Ob die die nicht mal leaken könnten

Gigt es denn überhaupt Grafikchips (3D fähig mit vergleichbarer Performance) wo man die Specs und/oder OpenSource Treiber bekommt?

539

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 29. October 2010, 21:41 »

Interessant wäre vorallem wenn mal erklärt wird (so das ich es auch verstehe ) warum solche "lock-free" Algos schneller sind und besser skalieren.

@off-topic

Schon jemand was vom PandaBoard gehört? Da könnte ich dann wirklich mal schwach werden und vllt wird es dann zu Weihnachten nen günstigerer Laptop und dann noch das Board.

540

Lowlevel-Coding / Re:App-/GUI-Server

« am: 29. October 2010, 12:58 »

Der Treiber, der Textmodus darstellt, ist ein VGA-Treiber, also unportabel. Und der muss aus einem Zeichenstrom die Cursor-/Farb-/CLS-Geschichten extrahieren und den Rest darstellen.

Das ist mir schon klar! Ich meine das ich dann einen Textmode-Treiber für die jeweilige Platform schreiben will/muss und diese Treiber stellen auf allen Platformen das selbe Interface zur Verfügung.
Ich denke einfach das ein Textmode-Treiber einfacher und schneller geschrieben ist als ein komplett grafischer Treiber. Auch das Interface will erstmal designt werden und da ich erstmal nur mit einer Text-Oberfläche plane ist das halt einfacher.