Bachelor Thesis: Extended Abstract

Almost fourteen months ago, I started working on my bachelor thesis. Although I finished it half a year ago, it’s still part of my work as a student research assistant.

During my initial work, most of the code was written for an internal research kernel. I’m now happy that we were able to port it to an open source kernel called eduOS. This minimal operating system is used for practical demo’s and assignments during the OS course at my university. There’s much more I could write about. So this will probably be another separate blog post.

The motive for this article is an abstract I wrote for the student research competition of the ASPLOS conference which is held this year in Istanbul, Turkey. Unfortunately my submission got rejected. But as a nice side-effect, I’ve now the chance to present my work to an english audience as well:

PDF Version


Self-referencing Page Tables for the x86-Architecture

A simple Paging Implementation for a minimalistic Operating System

Steffen Vogel

Academic advisor: Dr. rer nat. Stefan Lankes
Institute for Automation of Complex Power Systems
E.ON Energy Research Center, RWTH Aachen University
Mathieustr. 10, 52074 Aachen, Germany

This was a submission for ASPLOS Student Research Competition ’15 Istanbul, Turkey1

ABSTRACT

The adoption of 64 bit architectures went along with an extension of the virtual address space (VAS). To cope with this growth, the memory management unit (MMU) had to be extended as well. For paging-based systems like Intel’s x86-architecture this was realized by adding more levels of indirection to the page table walk.

This walk translates virtual pages to physical page frames (PF) by performing look-ups in a radix / prefix tree in which every node represents a page table (Figure 1a). Since the tables are part of the translation process, they must be referenced by physical page frame numbers (PFN, blue line). As the operating system is only eligible to access the VAS, it cannot follow the path of a walk. In order to allow the manipulation of page tables, it must provide:

Page table walk in the x86 64 longmode: Traditional, without self-reference.

Figure 1a): Page table walk in the x86 64 longmode without self-reference.

  • Access to the table entries, by mapping the tables themselves to the VAS.
  • A mapping between physical references to corresponding locations in the VAS.

Additionally, every level of the page table walk increases the complexity of managing these mappings. They also increase the memory consumption by occupying physical page frames. It is possible to avoid both drawbacks by the technique described in the following.

In my bachelor thesis, I presented an approach, which is compatible with both the 32 bit and 64 bit version of Intel’s x86-architecture. This allows for a replacement of two code bases, one for each architecture, by one supporting both. Thus, results in a shorter, easier comprehensible, and maintainable code. As foundation for this implementation our teaching OS called “eduOS” was used2. “eduOS” supports only the 32 bit protected mode whereas the 64 bit longmode is only implemented for an internal research kernel.

Thanks to the sophisticated design of Intel’s x86 MMU, it is possible to avoid most of the complexity and space requirements by using a little trick. Adding a self-reference in the root table (PML4 resp. PGD) automatically enables access to all page tables from the VAS without the need for manual mappings as described above (Figure 1b). The operating system does not need to manually follow the path of a page table walk, as this task is executed by the MMU for accessing individual tables instead of page frames.

Page table walk in the x86 64 longmode: With self-reference.

Figure 1b): Page table walk with self-reference.

An access to the VAS region covered by a self-reference causes the MMU to look up the root table twice (red line). Effectively, this shifts the whole page table walk by one level. Therefore, it stops with the PFN of page tables instead of page frames that are usually translated by the MMU. Here, both the PML4 and PDPT indexes are used to choose an entry out of the PML4 table. Therefore, it must be guaranteed that PML4 entries can be interpreted as PDPT entries, too. This demands for the following requirements:

  • Homogenous coding of paging flags across all paging levels.
  • Equal table sizes across all paging levels.

Fortunately, the x86-architecture complies with this prerequisites as shown in Figure 2. Green colored flags are coded consistently across all paging levels. Only PAT, size and global flags have a slightly different meaning for entries in the PGT. My bachelor thesis shows that these deviations still allow maintaining full control caching and memory protection properties of self-mapped tables. This includes for common system calls like fork() and kill().

Similar flags across all paging levels.

Figure 2: Similar flags across all paging levels.

By repeatedly addressing the self-reference, it is also possible to access tables of the upper levels (PGD to PML4). Table 1 shows the resulting virtual addresses of all page tables when using the last (512th) entry of the PML4 table for the self-reference3. This grants access to all possible page tables, including those which might not yet exist and may be allocated in the future. Hence, the self-reference reserves a fixed fraction of the VAS for the page tables. The size of this region is equal to 256 TiB / 512 = 512 GiB for 64 bit (resp. 4 GiB / 1024 = 4 MiB for 32 bit), which is negligible in comparison to the huge VAS of 248 byte.

Virtual addresses of self-mapped tables.

Table 1: Virtual addresses of self-mapped tables.

For the manipulation of page table entries two approaches
are feasible:

  • Top-down Use known tree traversals, starting at the root node,
    which corresponds to the PML4 respectively PGD.
  • Bottom-up Use the page fault handler to create new tables on-the-fly,
    when they are not yet present.

But there are also other architectures which satisfy the prerequisites described above. One of these is the Alpha4 architecture, which suggests a similar approach in the reference manual. Intel and AMD do not mention the technique in their x86 manuals. In the field of operating systems, support is far more limited. There is only a single reference5 dated to 2010 indicating that Microsoft might use a similar approach for its NT kernel. Linux cannot profit because its paging implementation must support a broad selection of virtual memory architectures of which not all fulfill the requirements mentioned above.

noteblok2Dies ist das neue Logo und Name meines Blogs.

Bisher gab es hier nur wenige persönliche Beiträge. Da ich das auch so beibehalten möchte, habe ich mich entschlossen meinen Namen aus dem Titel zu streichen. Vielleicht findet so auch mal der ein oder andere Gastbeitrag seinen Weg hierher.

DomainsWorld_IPv6_launch_badge_256

Mit dem neuen Namen hat sich auch die Domain geändert. Der Blog ist nun erreichbar unter noteblok.{de,net,org,dn42}. Über meine persönliche Domain gelangt man nun direkt zu ein paar Infos über mich.

Neben den neuen Domains sind nun auch alle Websiten/Blogs über IPv6 erreichbar :-)

dn42dn42

Zudem ist der Blog auf über des dn42 Darknet erreichbar. Das dn42 ist ein dezentrales und dynamisches VPN Netzwerk. Es besteht aus einem Verbund von Freiwilligen Admins, die jeweils Peer-to-Peer Verbindungen über VPNs herstellen. Es baut damit auf dem bestehenden Internet auf. Zudem nutzt das dn42 mit BGP das gleiche Routing Protokoll.

Mit ein paar Freunden betreiben wir (/dev/nulll) das Autonome System AS 76100 und unterhalten Verbindungen (engl. peerings) mit zur Zeit 5 anderen Knoten.

 

Abschluss Bachelorarbeit

Nachdem ich vor knapp acht Monaten mit meiner Bachelorarbeit begonnen habe, freue ich mich nun diese fertigstellen zu können. Dazu lade ich alle Interessenten zu meiner Abschlusspräsentation ein:

am 18. Juni 2014
um 13:00 Uhr
im Raum BSZ-20 des EON Energy Research Center

Update: Nachdem ich am Mittwoch meine Arbeit mit der Bestnote abschließen konnte, möchte ich sie nun hier veröffentlichen:

Jetzt mag sich der Ein oder Andere wundern weshalb mein Vortrag im EON Energy Research Center (EONERC) und nicht im Lehrstuhl für Betriebssysteme (LfBS) stattfindet. Der Lehrstuhl für Betriebssysteme wurde von unserer Fakultät aufgelöst. Die wissenschaftlichen Mitarbeiter setzen Ihre Arbeit nun in anderen Instituten fort.

EON Energy Research Center

Weiterlesen…

tileLED

tileLEDUnd schon wieder habe ich ein kleines Hardwareprojekt, das ich hier vorstellen möchte. Auf eBay bin ich auf diese günstige LED Dot-Matrix Displaymodule gestoßen. Auf einer Größe von 3x3cm besitzen sie 8×8 rote oder grüne LEDs, die per Multiplexverfahren angesteuert werden.

Für diese Module habe ich eine kleine Platine gelayoutet, die nicht größer ist als das Modul selber. Die LEDs werden über einen kleinen ATmega8 Mikrocontroller direkt angesteuert. Auf Konstantstromquellen habe ich hier zugunsten der Platinengröße verzichtet. Auch wenn diese Beschaltung den ATmega etwas überlastet, funktioniert es super.

top_btm

Ursprünglich war geplant aus vielen kleinen Modulen ein interaktives Puzzle oder Dominospiel zu basteln. Dazu besitzen die Module an allen vier Seiten Lötpads für Versorgungsspannung und SPI, über die sie auch mit ISP geflasht werden können.

Aus Zeitgründen und der doch recht fizzeligen SMD Löterei habe ich mich jedoch dann dagegen entschieden. Aktuell setze ich ein paar der Displays in Verbindung mit einem digitalen Temperatursensor1 als einfaches Tischthermometer ein.

Auch hier habe ich einige Platinen zu verschenken bzw. tauschen. Vielleicht hat ja jemand die Muse sich mit der Kaskadierung mehrere Elemente auseinander zu setzen? Von den ursprünglich 40 Modulen sind jetzt noch ca. die Hälfe übrig. Aus ihnen bastele ich gerade größere “Tiles” mit 24×24 und 32×32 Pixeln. Diese werden dann über 9 bzw. 16 74HC696 Schieberegister angesteuert, sodass nur noch ein Mikrocontroller benötigt wird. Unten könnt ihr die ersten Bilder der größeren Tiles sehen.

1 2 3 32  Scrolle nach oben