Autor Thema: Logisim CPU  (Gelesen 118864 mal)

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #160 am: 24. March 2013, 16:38 »
mmh ok, dann bau ich mal meine CPU zuende :D

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #161 am: 02. April 2013, 14:30 »
Gibt es eigntlich eine art schaltung die bei einem stacküberlauf eine Exception auslöst ?

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #162 am: 02. April 2013, 17:05 »
Hallo,

Exceptions funktionieren alle gleich, egal ob Stack-Overflow, Undefined Opcode oder Division By Zero, d.h. von verschiedenen Teilen der CPU kommen Leitungen zur Interruptverarbeitung.

Um Stack-Overflows erkennen zu können, gibt es zwei Bedingungen:
- Die CPU muss Stackzugriffe von normalen Speicherzugriffen unterscheiden können. (Im einfachsten Fall prüfst du nur bei PUSH und POP.)
- Die CPU muss die Größe (Anfang und Ende) des aktiven Stacks kennen und bei Stackzugriffen mit dem Stackpointer vergleichen.

Bedenke, dass du wahrscheinlich mehrere Stacks in deinem System haben wirst (pro Thread einen, plus Kernelstack) und zwischen diesen auch umschalten können musst. Während du umschaltest, ist der Stack ungültig - da sollte diese Exception nicht auftreten dürfen.

Gruß,
Svenska

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #163 am: 04. April 2013, 12:52 »
Mhh wie wurde sowas in anderen Systemen umgesetzt ?

Jidder

  • Administrator
  • Beiträge: 1 625
    • Profil anzeigen
Gespeichert
« Antwort #164 am: 04. April 2013, 18:34 »
Auf x86 können Stack Overflows eigentlich nur durch das Segment Limit erkannt werden. Aber da man heutzutage in der Regel das Limit so setzt, dass die Segmente den gesamten Adressraum überspannen, werden mit diesem Mechanismus keine Stack Overflows erkannt. Wenn das Betriebssystem Paging nutzt, können Stack Overflows unter bestimmten Bedingungen abgefangen werden, indem Seiten direkt unter dem Stack nicht gemappt werden und so beim Zugriff einen Page Fault auslösen. Dann hast du allerdings immer noch das Risiko, dass der Stack Overflow in einem einzigen Schritt so groß ausfallen könnte, dass er diesen geschützen Bereich einfach überspringt, und dann weiter entfernt vom Stack Schaden anrichtet.

Das Problem ist also immer, dass die CPU wissen muss, wo eigentlich der Stack beginnt und endet. Wenn du das mit Segmenten machst, hast du das Problem, dass das von Hochsprachen wie C eher nicht unterstützt wird oder unperformant ist, und wenn du es mittels Paging machst, hast du immer eine Unsicherheit drin.
Dieser Text wird unter jedem Beitrag angezeigt.

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #165 am: 07. April 2013, 13:01 »
Nun mal ne blöde frage, was darf überhapt alles ein thead ? Darf der nur auf seinen Stack-bereich und der Bereich wo die Befehle liegen zugreifen oder darf er auch daten laden die sich nicht in seinem Stack befinden?

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #166 am: 07. April 2013, 13:50 »
Gegenfrage: Was unterscheidet Threads von Prozessen?

Roadrunner

  • Beiträge: 33
    • Profil anzeigen
Gespeichert
« Antwort #167 am: 07. April 2013, 21:14 »
Ein Prozess kann aus einem oder mehreren Threads bestehen, aber einem Thread ist genau ein Prozess zugeordnet. Jeder Prozess erhält eigenen Speicher etc., während die Threads sich den Speicher und die restlichen Ressourcen, die dem Prozess zustehen, teilen müssen.

Also ist die Frage, was ein Thread darf, wohl eher die Frage, was der Prozess darf. Als Userspace-Prozess vermutlich eher wenig.
Exception 0x1A: Insufficient user-IQ

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #168 am: 08. April 2013, 01:31 »
Und wieder habe ich einen Ironiedetektor überlistet...
Das richtete sich an Tufelix, denn die Antwort auf seine Fragen ergeben sich von selbst, wenn er meine Frage beantwortet. Nun ist es zu spät, daher hier die Auflösung:

Nun mal ne blöde frage, was darf überhapt alles ein thead ?
Ein Thread darf das, was ein Prozess darf. Was genau das ist, entscheidest du als Entwickler von CPU und Betriebssystem. :-)

Darf der nur auf seinen Stack-bereich und der Bereich wo die Befehle liegen zugreifen oder darf er auch daten laden die sich nicht in seinem Stack befinden?
Alle Threads eines Prozesses teilen sich einen Adressraum (das ist der Sinn von Threads). Das heißt, dass jeder Thread grundsätzlich auf alles zugreifen darf, was diesem Prozess zugeordnet ist - konkret also Code, (globale) Daten und alle(!) Stacks des Prozesses. Dazu kommt eventuell noch Thread-Local Storage.

Gruß,
Svenska

Roadrunner

  • Beiträge: 33
    • Profil anzeigen
Gespeichert
« Antwort #169 am: 15. April 2013, 15:04 »
Zitat
Und wieder habe ich einen Ironiedetektor überlistet...
Das hatte ich befürchtet. Allerdings war ihm damit wohl wenig geholfen, weshalb ich die Auflösung gleich mal angehängt habe.

Aber eine andere Frage: Was meinst du mit Thread-Local Storage? Schließlich teilen sich alle Threads meines Wissens nach den gleichen Speicher, oder etwa nicht?
Exception 0x1A: Insufficient user-IQ

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #170 am: 15. April 2013, 16:50 »
Zitat
Und wieder habe ich einen Ironiedetektor überlistet...
Das hatte ich befürchtet. Allerdings war ihm damit wohl wenig geholfen, weshalb ich die Auflösung gleich mal angehängt habe.
Selber denken macht schlau. :P

Was meinst du mit Thread-Local Storage? Schließlich teilen sich alle Threads meines Wissens nach den gleichen Speicher, oder etwa nicht?
Die Suchmaschine des geringsten Misstrauens wirft folgenden Link als erstes Ergebnis zu der Frage aus. TLS ist eigentlich ein Workaround für historisch gewachsene Dinge, die Multithreading behindern, wie z.B. errno.

Oder als Frage an die Spezialisten: Gibt es da noch andere sinnvolle Einsatzzwecke für?

Gruß,
Svenska

XanClic

  • Beiträge: 261
    • Profil anzeigen
    • github
Gespeichert
« Antwort #171 am: 15. April 2013, 19:30 »
Ich persönlich hab da noch die PID, die PPID und die PGID drin, aber na ja…

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #172 am: 15. April 2013, 23:20 »
Die passen auch in die normale Thread-Struktur (neben der TID), müssen nicht über TLS laufen. Ist aber auch eine Möglichkeit. :-)

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #173 am: 21. April 2013, 18:11 »
Nun was wird genau in so nem Thread-Local Storage gespeichert, und wie funktioniert er ? Und was sind Thread-strukturen? Auserdem, wie werden in risc-CPU´s stack-überläufer verhindert ?

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #174 am: 21. April 2013, 22:25 »
Die Thread-Struktur speichert all das, was man zu einem Thread wissen muss. Also z.B. ID, zugeordneter Prozess, Adresse für Thread Local Storage und so weiter.

Im Thread-Local Storage wird die Variable "errno" gespeichert und vielleicht auch noch andere Dinge, die mir nicht einfallen.

Einen Stack-Überlauf kannst du nicht verhindern. Guard Pages versuchen nur, einen Stack-Overflow zu erkennen, nachdem er aufgetreten ist und bevor er Schaden verursacht. Das gelingt naturgemäß nur unzureichend.

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #175 am: 21. April 2013, 22:31 »
Was sind guard Pages ?

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #176 am: 21. April 2013, 23:05 »

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #177 am: 23. April 2013, 19:24 »
ops, hatte ganz vergessen das man es auch googlen kann :-D. Aber naja gibts keine andere möglichkeit ohne große segment-tabellen effektiv overflows zu erkennen? Bzw hat einer ne idee wie sowas ausehen müsste ?

Jidder

  • Administrator
  • Beiträge: 1 625
    • Profil anzeigen
Gespeichert
« Antwort #178 am: 23. April 2013, 19:55 »
Du musst doch im Prinzip nur sicherstellen, dass der Stackpointer SP innerhalb eines bestimmten Intervalls liegt. Dazu baust du zwei Register in deine CPU ein: SP_min und SP_max, und bei jeder Stackoperation bzw. Zugriff über den Stackzeiger prüfst du, ob SP_min <= SP <= SP_max (+- Wortgröße je nach Design). Wenn diese Bedingung falsch ist, dann löst du eine Exception aus und das Programm wird aufgrund eines ungültigen Zugriffs terminiert.

Wenn du zusätzlich einen Framepointer hast (wie z. B. BP bei x86) dann behandelst du den genauso wie SP. Außerdem solltest du dir überlegen, ob du verhindern willst, dass der Wert des Stackpointer/Framepointers in ein anderes Register kopiert wird oder in den Speicher geschrieben wird. Sonst lässt sich der Mechanismus nämlich aushebeln, weil normale indirekte Speicherzugriffe ja nicht der oben genannten Prüfung unterlegen. Das ist natürlich eine massive Einschränkung und macht es z. B. unmöglich C vollständig auf die CPU zu portieren.

Beispiel: Wenn du es wie die meisten anderen CPUs machst, und SP wie ein normales Register behandelst, kann man einfach folgenden C-Code schreiben (trifft natürlich auf äquivalenten Code in beliebigen anderen Sprachen inkl. Assembler zu):

int *px;

void foo() {
    int x;
    px = &x; // Zeiger auf x
    *px = 12; // Setze x auf 12. Gültig, weil x existiert.
}

void bar() {
    foo();
    // Zwei fehlerhafte Stackzugriffe:
    *px = 123; // Fehler: x existiert nicht mehr
    px[456] = 789; // Möglicherweise Stackoverflow
}

Wie kann man also dafür sorgen, dass das korrekt erkannt wird? Eine Möglichkeit wäre jedes Wort im Speicher mit einem speziellen Bit auszustatten, auf das von Programmen normalerweise nicht  zugegriffen werden werden kann. Das heißt wenn du zum Beispiel eine Architektur mit 16-Bit-Worten hast, musst du RAM verwenden, der 17-Bit-Worte unterstützt. 16-Bit von diesem 17-Bit-Wort werden ganz normal vom Programm gelesen/beschrieben. Das eine zusätzliche Bit wird hingegen verwendet, um den Ursprung des Wertes zu kennzeichnen.

Bei jedem schreibenden Speicherzugriff wird dieses Bit gesetzt, wenn der Wert eine gültige Stackadresse ist. Das Bit wird gelöscht, wenn es "normale Daten" (Zahlenwerte oder Zeiger auf was anderes als den Stack) sind. Die CPU-Architektur muss intern auch zu jedem Register ein zusätzliches Bit speichern, das genau besagt, ob es eine Stackadresse ist oder nicht. Wenn du also aus dem Speicher etwas liest, wird das 17. Bit aus dem RAM in das zu dem Register gehörende Bit kopiert. Jede Operation (Indirekter Speicherzugriff, Arithmetik, ...) verhält sich nun unterschiedlich jenachdem, ob in einem Register oder in einem Wort im RAM eine Stackadresse steht. Zum Beispiel muss das Ergebnis einer Addition einer Konstante und einem Register, das als Stackadresse markiert ist, weiterhin eine gültige Stackadresse sein. Oder wenn zum Beispiel zufällig in einem Register ein Wert steht, der einer Stackadresse entspricht, aber das Register nicht als Stackadresse gekennzeichnet ist, musst du eine bei einem indirekten Speicherzugriff über dieses Register eine Exception auslösen.

Wenn man das etwas ausweitet, lässt sich vermutlich der fehlerhafte Zugriff auf die nicht mehr existierende Variable x durch *px = 123; auch erkennen. Man könnte z. B. bei Speicherzugriffen überprüfen, ob die Adresse zwischen SP und SP_max liegt (wenn der Stack nach unten wächst). Aber wenn der alte Speicherplatz von x inzwischen von einer andere Variablen verwendet wird, lässt sich das nicht mehr erkennen (aber das ist ja dann kein Stack Overflow mehr, sondern ein anderer Fehler).

Diesen Mechanismus mit dem speziellen Bit kannst du weiter ausbauen, um z. B. ein Sicherheitskonzept basierend auf Capabilities umzusetzen.

Ich halte das hier beschriebene allerdings nicht für sinnvoll. Stack Overflows muss man nicht so präzise erkennen.
« Letzte Änderung: 23. April 2013, 20:09 von Jidder »
Dieser Text wird unter jedem Beitrag angezeigt.

Tufelix

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #179 am: 23. April 2013, 22:26 »
mmh ok, wieso muss man die stack-überläufe nicht so genau erkennen ?

 

Einloggen