Themen

1

OS-Design / Task-Scheduler und Speichermanager - konstante Performance

« am: 14. March 2013, 12:16 »

Ich will hier kurz den Task-Scheduler und den Speichermanager aus meinem Kernel vorstellen und Details zur Implementierung verraten.

Der Scheduler

Nachdem ich über längere Zeit nicht mehr am Kernel gearbeitet habe, bin ich nun endlich wieder dazu gekommen. In den letzten Tagen habe ich am Scheduler gearbeitet. Anforderungen an diesen waren: Taskwechsel in konstanter Zeit, Prioritäten, gewichtete Verteilung der Ausführungszeit und die Strukturierung in Unter-Tasks. Ein Programm soll über seine Rechenzeit frei verfügen und an Unterprogramme verteilen können, aber keinesfalls Programme überhalb seiner Position im Baum beeinträchtigen. Damit wird verhindert, dass sich das System "aufhängt" und nicht mehr auf Benutzereingaben reagiert.

Die Tasks sind zu einer Liste verkettet. Wenn ein Task seine Ausführungszeit verbraucht hat, wird der nächste Task aufgerufen. Die Ausführungszeit des Schedulers wird mitgezählt, Abweichungen zur geplanten Zeit werden auf die nächsten Slice angerechnet. Durch Timeout-Interrupts wird garantiert, dass kein Task seine Ausführungszeit um das Vielfache überschreitet. Die Unter-Tasks sind ebenfalls alle in dieser Liste enthalten. Sobald ein Task mit höherer Priorität aktiv wird, wird die Liste an Beginn und Ende des übergeordneten Containers aufgetrennt und ein anderes Stück eingefügt. Die Position im Teilstück wird gespeichert. Die parallelen Pfade liegen alle im Speicher vor, sind jedoch erstmal nicht mit der Liste verkettet. Suspend/Resume, Spawn/Terminate und Änderung der Priorität arbeiten zuerst auf der Baumstruktur und aktualisieren dann die Liste in konstanter Zeit.

Ich habe mir Gedanken gemacht über die Anzahl der Taskwechsel pro Sekunde (Overhead), die maximale Antwortzeit von Tasks mit hoher Priorität, sowie das Intervall, bis ein Task nach seiner Ausführung wieder aufgerufen wird.

Folgende Konfiguration war das Resultat:

2G Takte/sek
800 aktive Prozesse (Äquivalent)
256K Takte/Zeitscheibe
8K Zeitscheiben/sek
100ms Intervall für erneuten Aufruf eines Tasks
0.125 ms/Zeitscheibe
< 1ms maximale Antwortzeit (des aktiven Tasks mit der höchten Priorität)

Die Speicherverwaltung

Vor dem Scheduler habe ich an der Speicherverwaltung gearbeitet. Die Anforderungen an diese waren: malloc, free und realloc in konstanter Zeit und keine Fragmentierung oder Performanceverlust nach sehr langer Uptime.

Der Speicher wird in 4KB-Seiten verwaltet. Bereiche kleiner 4KB werden innerhalb der Seite in einer Bitmap verwaltet, Bereiche größer 4KB werden aus mehreren 4KB-Seiten zusammengesetzt. Welche Seiten aneinander gereiht werden, steht in einer Tabelle. Elemente eines Vektors oder andere Zugriffe mit Offset dürfen die Seitengrenze nicht überlappen. Elementare Datenstrukturen, sowie die Funktionen memset(), memcpy() und memcmp() habe ich entsprechend implementiert. Details zu jeder einzelnen Seite stehen in einer weiteren Tabelle, dort sind die Seiten in diversen Listen verkettet. Seiten mit freien Slots kleiner 4KB, Slots in der Tabelle für große Bereiche oder die nächste freie Seite können in konstanter Zeit gefunden werden.

Ich habe mir auch Methoden für effizientes garbage Collecting überlegt, bin aber zu keinem Ergebnis gekommen. Als einzige Möglichkeit ohne Auswirkungen auf die Performance sehe ich die Implementierung in Hardware.

Gruß

2

Lowlevel-Coding / sysexit

« am: 06. December 2012, 15:56 »

Was ist an diesem Code falsch?

Gestartet mit qemu -kernel und CPUID 0xA29, GDT und TSS geladen.

Code: [Auswählen]

wrmsr 0x174,0x08 ; wrmsr makro

mov edx,xyz
mov ecx,0

sysexit

xyz:
;nachricht ausgeben... stattdessen kommt ein #TS
jmp $
Gruß

3

Offtopic / binäre Division

« am: 30. November 2012, 12:47 »

Zur Evaluierung und Ausarbeitung verschieder Ansätze für parallele Architekturen habe ich letztens ein paar Schaltungen für Addierer und Multiplizierer konstruiert. Kurz: Addierer mit n Chipfläche und in log(n) Zeit, sowie Multiplizierer mit 2n Fläche und 2log(n)+x Zeit für Bitbreite n=128 und kleinem x. Packed integer werden unterstützt.

Einen Multiplizierer mit log(n) Zeit und n^2 Platz habe ich verworfen.

Pro Instruktion sind mehrere Schaltungen parallel vorgesehen. Die Kosten berechne ich näherungsweise mit Taktzyklen * Transistoren(d.h. Chipfläche), würde aber kürzere Taktzyklen bevorzugen (Serialisierung).

Nun bin ich auf der Suche nach Ideen für die Division, welche über die schriftliche Division hinausgehen. In der englischen Wikipedia gibt es dazu den Artikel: Division algorithm, der sich mir jedoch nicht ganz erschließt.

Kennt jemand die Schaltungen in aktuellen Prozessoren von Intel/ARM/GraKas etc?

Ich habe bisher noch keinen guten EDA-Designer gefunden, die freien sind etwas unhandlich, oder es fehlt etwas, bspw Logikbausteine, Timing-Simulation oder Export in ein standardisiertes Format.

SORRY NOCH NICHT FERTIG... bis gleich : )

4

Das Wiki / Sourcecode unvollständig in Android-Browser

« am: 09. October 2012, 12:17 »

Bei den formatierten Code Listings fehlt bei mir der Scrollbalken. Nachdem ich nach einem Update nicht mehr auf den Seiten-Quelltext zugreifen kann, sehe ich keine Möglichkeit das Listing in seiner Vollständigkeit einzusehen. Auf meinem Ubuntu funktioniert alles normal.

5

OS-Design / Kernel malloc/free, kompakt und leichtgewichtig

« am: 17. August 2012, 23:46 »

Diese kompakte und leichtgewichtige Implementierung eines Kernel malloc/free ist aus meinem Treiber-Testkernel und soll der Lowlevel-Community nicht vorenthalten bleiben.

http://pastebin.com/JBcwaTpv

Die Speicherverwaltung weist Speicherblöcke der Größe Seitengröße << n direkt aus dem physischen Speicher zu. Die Seitengröße ist auf 4K festgelegt. In der Standardkonfiguration ist MEMORY_PAGES = 8K, es sind also insgesamt 8K * 4K = 32M für malloc verfügbar. Die Verwaltungsdaten (hier Arrays mit Bitmaps) kommen extra in das data Segment. MEMORY_MEMORY_START_P = 16M bedeutet, dass der Speicherbereich erst ab 16M beginnt und bei MEMORY_MEMORY_END_P = 16M + 32M = 48M endet. Der Bereich darunter (ab 1M) ist also für die text, data und bss Segmente des Kernels

malloc() gibt einen Zeiger auf einen Bereich mit der kleinstmöglichen Speicherklasse zurück. Die Speicherklasse bestimmt die Größe des zugewiesenen Speicherbereichs folgendermaßen: Größe = 1 << Klasse. Die kleinste Klasse ist MEMORY_CLASS_START = 12, da 1 << 12 == MEMORY_PAGE_SIZE == 4K. Die Anzahl unterschiedlicher Speicherklassen wird mit MEMORY_SHIFT_LIMIT = 6 festgelegt. Die größte Klasse (inklusive) ist somit MEMORY_CLASS_END = 12 + 6 = 18.

Wie der Speicher mit MEMORY_SHIFT_LIMIT = 2 und MEMORY_PAGES = 8 aufgeteilt werden würde, zeigt folgendes Beispiel:

0x00000 +---+
        |   | 16x Blöcke der Größe  4K = 64K
        |   |
        |   |
        |   |
0x10000 +---+
        |   |  4x Blöcke der Größe  8K = 32K
        |   |
0x18000 +---+
        |   |  2x Blöcke der Größe 16K = 32K
        |   |
0x20000 +---+

Das Ganze hat dann noch einen Offset von MEMORY_MEMORY_START_P. Die letzte Klasse bekommt dabei einen Slot mehr, da der Platz nun nicht weiter aufgeteilt wird.

Die Referenzen auf printf(), print_str() und halt() müssen in der Umgebung des Kernels aufgelöst werden. Um die Bitmaps zu löschen, muss vor dem ersten malloc() mem_init() ausgeführt werden.

Das Laufzeitverhalten kann verbessert werden, indem freie Slots im Hintergrund gesucht werden. Die Speicherverwaltung weist keine externe Fragmentierung auf und ist weitestgehend robust implementiert, was aber durch Redundanz und/oder Asserts noch gesteigert werden kann.

6

Softwareentwicklung / Wie kann man die Zuverlässigkeit von Software und Computern steigern?

« am: 15. August 2012, 14:13 »

Eine nicht vollständige Sammlung von Überlegungen, die Robustheit und Zuverlässigkeit von Software oder auch Hardware zu steigern:

• um durch häufig wiederkehrende Fehler bei der Speicherverwaltung auftretende Verwundbarkeiten zu vermeiden, sollten Maßnahmen ergriffen werden, etwa die zuverlässige Prüfung von Allokations-Details, die Einhaltung der Speichergrenzen und der Zugriffsrechte, sowie das Erkennen von Überläufen .
• bestimmte Algorithmen und Datenstrukturen sind anfälliger für fehlerhafte oder unstimmige Eingabewerte. Die Auswirkungen eines Fehlers sollten sich möglichst lokal auswirken und nicht die gesamte Struktur betreffen.
• der Code bzw. die Schaltung sollte keinen Zustand speichern und vor jedem Aufruf zurückgesetzt werden.
• je einfacher das Design der Architektur und die Implementierung sind, desto nachvollziehbarer ist das System. Dieses kann dann leichter validiert werden, am Besten unabhängig voneinander von mehreren Entwicklern.
• um alle zu erwartenden Kombinationen und Pfade von Daten und Kontrollfluss validieren und die Auswirkung eines eventuellen Fehlers bestimmen zu können sollte deren Anzahl möglichst gering sein.
• neben der Vermeidung resp. Behandlung von DIV-0 und Integer-Overflows sollte die Ausnahmen-Behandlung als besondere Form des Kontrollflusses beachtet werden.
• als String vorliegende Eingabedaten sollten nicht interpretiert werden, so dass diese keinen Einfluss auf den Kontrollfluss haben.
• zwischen nebenläufigem Code sollten keine Abhangigkeiten existieren.
• separate Einheiten sollten so gut es geht isoliert werden und über definierte Schnittstellen mit der Außenwelt kommunizieren. Die Speicherverwaltung sollte den Speicher unterschiedlicher Prozesse voneinander trennen.
• des Weiteren wäre es möglicherweise sinnvoll, ähnliche Maßnahmen redundant auszulegen und neben der Vermeidung auch eine mögliche Kompromittierung erkennen und signalisieren zu können.

Gruß

7

Softwareentwicklung / qemu: fatal: Trying to execute code outside RAM or ROM

« am: 05. June 2012, 13:55 »

Wenn qemu mit der Meldung "qemu: fatal: Trying to execute code outside RAM or ROM" abstürzt gibt es keine Möglichkeit mehr mit gdb ein backtrace zu bekommen. Um dennoch ein backtrace zu bekommen, habe ich folgendes bash-script geschrieben:

Code: [Auswählen]

#!/bin/bash

gdb="gdb bin/kernel.bin --eval-command=\"set pagination off\" --eval-command=\"set confirm off\" --eval-command=\"target remote localhost:1234\""


echo "" > debug_backtrace_list


echo "# list functions..."
list="$(eval gdb bin/kernel.bin --batch --eval-command=\"set pagination off\" --eval-command=\"info functions\")"


echo "# generate break commands..."
while read line
do
line2=$(echo "$line" | grep -oP '((?<= )|(?<= \*))\w+(?=\()')
if [ "$line2" != "" ]
then
echo -ne "break $line2\ncommands\nbt\ncontinue\nend\n" >> debug_backtrace_list
fi
done <<< "$list"


echo "# run gdb..."
eval "$gdb --command=debug_backtrace_list --eval-command=\"continue\" $@" | tee -a debug_output


echo '# done'

qemu wird im Vorfeld gestartet mit

Code: [Auswählen]

qemu-system-i386 -kernel bin/kernel.bin -s -S
Damit wird bei jedem Aufruf einer Funktion ein backtrace erstellt. Eventuell macht es noch Sinn, bestimmte Funktionsnamen auszulassen, wie bspw. putc.

8

Lowlevel-Coding / qemu ACPI

« am: 02. June 2012, 22:09 »

Ich kann den RSDP weder im EBDA noch im BIOS area finden. Ich habe auch schon die ganzen ersten 16MB nach "RSD PTR " gescannt - kein Ergebnis. Ich starte mit qemu -kernel. Wer weiss bescheid?

9

Softwareentwicklung / GNU ld workarounds

« am: 28. May 2012, 22:54 »

Wer mit GNU ld linkt (und das ist wahrscheinlich bei der Arbeit mit bspw. Linux), trifft möglicherweise auf einen der beiden Bugs, welche mir seit gestern auf den Geist gehen:

1. ld sagt "undefined reference to X", beim Verlinken eines stub sagt es "multiple definition of X".
Workaround: Die Referenz war eigentlich vorhanden, deshalb auch die mehrfache Definition, einfach die object files mit der vermeintlich undefinierten Referenz aus dem Linkvorgang nehmen.

2. ld sagt bei Erzeugung eines binary output files:
"ld: reopening o: No such file or directory

ld: final link failed: No such file or directory"
oder "ld: final link failed: File truncated".
Workaround: ld scheint ein Limit für die Gesamtgröße der Inputfiles zu haben. Entweder die größten object files rausnemen oder ein anderes Format erzeugen.

Mein binutils hat die Version 2.20.1-system.20100303

Falls jemand anderes vor den selben Problemen steht, sollte er diesen Thread mit der Suchfunktion finden können.

10

Lowlevel-Coding / qemu -kernel

« am: 25. May 2012, 01:41 »

Laut Qemu-Doku kann man mit -kernel multiboot images laden. Meine kernel.bin ist eine flat binary mit address fields und wird als GRUB image mit -fda geladen, mit -kernel nicht. /boot/memtest86+.bin hat laut mbchk keinen multiboot header, wird aber trotzdem gestartet. Wer weiss bescheid?

11

Offtopic / GPL Copyleft

« am: 29. April 2012, 16:08 »

Ich würde gerne für alle Peripherie ( (S)ATA, Netzwerk, 3d-beschleuniger) und Bussysteme (PCI, USB, diverse *HCI) die treiber aus dem Linux-Projekt nehmen (/drivers). Um meinen kernel nicht sofort unter GPL zu stellen, möchte ich eine art treiber-proxy dazwischen legen und nur die original linux treiber veröffentlichen, ist das OK ?

Der Proxy steht dabei selbst unter der GPL und wird ordnungsgemäß veröffentlicht. Der kernel kommuniziert über ein Interface mit dem Proxy, so, als ob es ein Dienstprogramm wäre. Für die Architektur fallen mir 3 Wege ein: A: der Proxy importiert den unmodifizierten sourcecode und transformiert ihn, B: der Proxy kompiliert die treiber mit GCC und transformiert den Objektcode, C: der Proxy reproduziert die Linux-Kernel-Umgebung und verlinkt dagegen.

Da auch unter Windows GPL-Programme laufen, der NT-Kernel jedoch nicht unter der GPL veröffentlicht wurde, vermute ich damit keine Probleme. Gibt es hier Lizenz-Spezialisten, bzw. was haltet ihr allgemein von der Idee?

12

Lowlevel-Coding / APIC FIFO size

« am: 27. April 2012, 13:20 »

Weiss jemand das Limit der Warteschlange für Interrupts im Local APIC? Also wenn

• IF gelöscht wird (mit CLI bzw. in einer Interrupt-Gate-ISR),
• daraufhin IRQs oder IPIs auftreten, bevor
• IF wieder gesetzt wird (mit! STI bzw. beim Verlassen der ISR), so dass
• die aufgetretenen Interrupts der Reihe nach abgearbeitet werden?

Die Spezifikationen von Intel geben leider keine Auskunft darüber.

Btw: Weiss jemand ein gutes Tutorial für SMP/APIC bootstrapping? Ich habe dieses hier gefunden: http://www.cheesecake.org/sac/smp.html

13

Das Wiki / Timing-Info

« am: 09. February 2012, 15:26 »

Kann man für aktuelle x86-CPUs eine Liste der Instruktionen incl. Timing-Informationen bzw. Taktzyklen machen bzw. im Artikel über Assembler einen Link zu reinmachen? Btw. Hazards gibt es bei x86 doch keine. ..?

Hatte bezüglich der Taktzyklen zumindest für 486 und Pentium mal eine Online-Referenz, wer den Link kennt bitte melden.

14

Offtopic / HW/CPU/VHDL-Fragen

« am: 16. January 2012, 15:14 »

Kann man auf einen internen Cache im selben Takt von mehreren parallelen Prozessen (VHDL) aus lesend zugreifen? Wie sieht es beim schreibenden Zugriff aus? Um zu entspannen denke ich zwischen dem Programmieren in Java ein wenig über massiv parallele HW-Architekturen nach.

Eine Reihe von Fragen, welche ich notiert habe:
- Sollen ausführbare Instruktionen eine kompakte Form von Schlüssel-Wert-Paaren enthalten?
- Könnten Adressen ausschließlich über Hashtables aufgelöst werden, um sich die Relokalisierung zu sparen?
- Könnten Konstanten ausschließlich im RAM liegen?
- Kann der Code teilweise oder vollständig im Cache gehalten werden?
- Können die Einheiten innerhalb der CPU über einen(mehrere) spezielle Busse mit "Adressleitung" Aufgaben untereinander verteilen?
- Inwiefern kann die Kommunikation hierarchisch organisiert werden, sodass mehrere parallele Tasks ihre Instruktionen auf mehrfach vorhandene Einheiten verteilen und diese die Ergebnisse im Speicher ablegen können?
- Kann jede instruktion ihre eigene Pipeline haben? (Die Takte einer jeweiligen Instruktion sind konstant)
- Wie verhalten sich Pipelines bei einem geänderten Ausführungspfad, anders gefragt: Kann der Code statisch (oder dynamisch) nach dem definitiven oder warscheinlichsten Pfad analysiert werden?

Edit: Das hier soll hauptsächlich ein Thread zu VHDL-Fragen werden. Auf die letzteren Fragen/Ideen erwarte ich natürlich keine definitive Antwort, gerne jedoch Kommentare.

15

Offtopic / ExportStructure..java

« am: 09. January 2012, 16:39 »

Ich brauche eine Rückmeldung zum Code, welcher den Zugriff auf x86-Srukturen konvertiert. Ich hoffe jmd hier kann Java lesen. Das ginge zwar mit C wesentlich einfacher, aber ich bin halt schon sehr weit mit dem Import für Java. Der Code hat ein Indent von 4 Zeichen und wird von Pastebin nicht korrekt dargestellt.

http://pastebin.com/gXMVMhB7

Kann da mal jemand drüber schauen? Sind alle Bits, Offsets, Byte-Orders und Flags korrekt? Der Code besteht aus 6 Klassen:
- InterruptDescriptorTablleRegister
- InterruptDescriptor
- GlobalDescriptorTableRegister (äquivalent zu Local)
- GlobalDescriptor (äquivalent zu Local)
- PageDirektoryEntry (äquivalent zu PageTableEntry)
- TaskSegmentDescriptor, unfertig

Jede Klasse beinhaltet die Methoden read und write, sowie einen Feldselektor "Field", welcher das Feld auswählt. Einige Klassen beinhalten zusätzlich Unterklassen für Flags und komprimierte Werte. Die Methode read gibt entweder einen 32-Bit Integerwert oder ein Objekt einer der Unterklassen zurück. Die Methode write nimmt ein solches Objekt entgegen und schreibt es in "structure".

Der Parameter "int start" ist überflüssig.

Ich beschäfte mich gerade mit dem Bootloader (GRUB). Nach 4 Stunden (und einem Haufen anstrengender Fehlermeldungen) habe ich erfolgreiches Plattenimage für Bochs kreiert.

16

OS-Design / Bootbarer Mikrokernel mit Hypervisor für Semantischen Code

« am: 08. December 2011, 14:12 »

Hallo Lowlevel - Entwickler

Ist mein erster Beitrag hier im Forum, ich hoffe dass ihr mit meinem Anliegen etwas anfangen koennt. Ich suche speziell Kernel-Entwickler, die mein Projekt fuer interessant halten und auch etwas Zeit haben. Ich habe bereits ~30K code in Java, haenge jedoch gerade beim Export von Code mit bootbarem Hypervisor (speicher layout fuer paging etc.). Spaeter will ich die Plattform komplett importieren und eine bootbare Version exportieren. Subsysteme fuer Java etc. und Treiber kommen spaeter. Ich ueberarbeite Code haufig, habe meistens Ueberblick und bin etwas perfektionistisch.

Ich arbeite seit ein paar Monaten an einer neuen Mikroarchitektur. Die neue Architektur implementiere ich vorläufig als Emulator in Java. Ich schreibe gerade ein Export-Modul, welches einen bootbaren Mikrokernel erzeugt. Die Prozess-Strukturen werden in Pages organisiert. (genauer: Jede Variable bekommt einen eigenen Stack, mit dem rekursive Aufrufe von Code-Zweigen und Wiederherstellung von gespeicherten Zuständen möglich werden.) Die Speicherverwaltung und andere Dinge will ich in Hardware gießen.

Eigentliche Motivation für den Aufwand ist ein semantischer Editor, der gegenwärtige Probleme der Software-Entwicklung elegant zu lösen versucht. So wird der Code in einem Baum direkt bei der Eingabe geparst und Symbole doppelt verlinkt. Dies vereinfacht statische Analyse und ermöglicht beispielsweise die massiv parallele Ausführung. Weitere Anforderungen, wie die sichere Ausführung, werden durch "Sandboxes" implementiert. (genauer: in die Hardware verlagert). Grundsatz der Architektur soll eine strikte Trennung von Aufgabenbereichen sein.

Java-Code kann importiert werden. Bei Interesse habe ich noch ein beschreibendes Skript von November 2010 (leider auf Englisch)