Virtualisatie van Android Henri De Veene
Promotoren: prof. dr. ir. Bjorn De Sutter, prof. dr. ir. Koen De Bosschere Begeleider: ir. Niels Penneman Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012
Voorwoord Mijn interesse voor het onderwerp van deze masterproef komt voort uit mijn interesse in Linux en in het algemeen openbronsoftware. Gelet op het feit dat smartphones en tablets met Android de laatste jaren alomtegenwoordig geworden zijn en dat virtualisatie aan een opmars bezig is, zowel in de serverwereld als in de wereld van mobiele toestellen, was dit het ideale onderwerp voor mijn masterproef. De masterproef is echter niet van een leien dakje verlopen en ik wil daarom de mensen bedanken die mij het afgelopen jaar gesteund hebben. Eerste en vooral zou ik mijn begeleider Niels Penneman en mijn promotor prof. Bjorn De Sutter willen bedanken voor alle hulp tijdens de maanden dat ik op het Technicum kwam werken en voor alle opbouwende feedback op mijn werk. Uiteraard wil ik hen ook bedanken om mij de kans te geven om mijn masterproef dit jaar nog af te werken, zelfs na het tijdverlies door mijn ongeval. Ik wil natuurlijk ook mijn ouders, broers en zussen bedanken voor het geduld dat ze hebben moeten uitoefenen, niet enkel dit jaar maar gedurende de afgelopen vijf jaar. Het was niet altijd even gemakkelijk maar ze zijn mij altijd blijven steunen en geloven. Een speciale dankjewel gaat naar mijn oudste zus Elise om mijn thesis volledig te controleren op taalfouten! Mijn vriendin Karen wil ik natuurlijk ook bedanken. Het was niet gemakkelijk om mij telkens opnieuw zien te verdwijnen in de examenperiodes. Toch heeft ze me ook altijd gesteund in al mijn werk. Als laatste wil ik nog mijn vrienden van de scouts, The Woods,... bedanken om in de gaten te houden dat ik niet zou veranderen in een computer.
Bedankt allemaal! Henri De Veene
21 juni 2012
i
Toelating tot bruikleen De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.
Henri De Veene
21 juni 2012
ii
Virtualisatie van Android door Henri De Veene Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen Academiejaar 2011-2012 Universiteit Gent Faculteit Ingenieurswetenschappen en Architectuur Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Promotoren: prof. dr. ir. Bjorn De Sutter, prof. dr. ir. Koen De Bosschere Begeleiders: ir. Niels Penneman, dr. Jonas Maebe
Samenvatting In deze masterproef wordt het werk voorgesteld dat uitgevoerd werd om Android te ondersteunen met een ARM hypervisor. De ARM architectuur en de werking van de initi¨ele hypervisor worden eerst besproken om de lezer inzicht te laten krijgen in de huidige problemen. Daarna wordt in meer detail uitgelegd wat de problemen zijn en hoe deze opgelost werden. Ten slotte worden de conclusies gemaakt en de wordt een overzicht gegeven van het werk dat in de toekomst nog moet gebeuren om het werk te voltooien. Trefwoorden: virtualisatie, hypervisor, Android, OMAP, ARM iii
Virtualizing Android Henri De Veene Supervisor(s): prof. Bjorn De Sutter, prof. Koen De Bosschere, Niels Penneman Abstract— This article presents the work that has been done to improve an ARM hypervisor in order to support Android. The work can be subdivided in several areas: adding support for the Thumb2 instructionset, improving the memory management system, improving virtual hardware support and adding unittest functionality. Keywords— Hypervisor, ARM, OMAP, Android, virtualization
I
MPROVEMENTS and progress in the technical field made the development of high-performance mobile devices possible, which incorporate a number of different functionalities. This, however, is achieved by combining several dedicated processing units together which leads to an inefficient device because the different processing units will never be fully in use, all at the same time. With virtualization it is possible to eliminate this inefficiency by letting all the software share a single powerful processing unit. This requires a hypervisor which manages the different software components to run together without the possibility of interference between the different components. In a collaboration between The University of Manchester and Ghent University a hypervisor for the ARM architecture is being developed. The hypervisor does not yet support Android, which is the subject of this Master’s thesis. I. Android Google Android is currently the most popular mobile operating system. It is an opensource operating system and uses the Linux-kernel, which is also opensource software. Because Android is an excellent OS to support with the hypervisor because it is opensource software which can make development easier. The most popular version of Android uses version 2.6.37 of the Linux-kernel. This is important because it has much better support for the OMAP System-on-Chip (SoC) than the Linux version which has been used to develop the hypervisor prior to this Master’s thesis. The OMAP SoC includes the ARM Cortex-A8 processor and is part of the BeagleBoard hardware on which the hypervisor is currently being developed. II. The hypervisor The hypervisor is a type 1 hypervisor which uses the technique full virtualization for its virtual ma-
chines [1]. This means that the virtual hardware behaves the same way as the real hardware and no modifications need to be made to the guestsoftware, as opposed to paravirtualization. To achieve full virtualization, the hypervisor uses dynamic binary translation (DBT). This technique replaces sensitive instructions in guest code with supervisor calls (SVC). A sensitive instruction is an instruction that depends on the configuration of the hardware [2]. Because guestcode is executed in user mode an exception will be thrown when executing an SVC instruction. This exception is catched by the hypervisor which will then emulate the replaced instruction. With DBT, the hypervisor can control the hardware and guarantee the proper execution of a guest OS. The hypervisor uses shadow page tables to share the physical memory between serveral guest operating systems. Each guest maintains its own page tables, but these are not used for address translation. Instead the hypervisor copies the structure of the guest page table to the shadow page table and configures the hardware to use this table for address translation. With shadow page tables, the hypervisor can control which regions of the physical memory are used by which guest OS. III. Shortcomings There are three major areas in which the hypervisor does not yet suffice to support the Android operating system. Firstly: the support for the Thumb-2 lacks support for conditional execution of instructions. This instruction set is used by the just-intime compiler of Android and should thus be fully supported. Secondly: the memory management has some problems preventing Linux 2.6.37 from booting. And thirdly: not all the hardware used by Linux 2.6.37 has been virtualized. IV. Unittesting When testing certain parts of the hypervisor, in particular concerning corner cases, it is not favorable to run an entire operating system. This approach has two problems: it will be slow and execution may not be deterministic. For these reasons, the unittest functionality was added to the hypervisor. Unittests will be small compared to an OS and are used to test only a few features. Unittests
can also be saved, to use in a later stage of the development of the hypervisor to test for regression bugs. V. Thumb-2 support An important improvement that has been made to the hypervisor is the support for conditional execution of instructions in Thumb-2 code. In contrast with ARM instructions, which can (almost) all be executed conditionally by default, Thumb-2 instructions can not because they do not contain a condition code field. However, using the Thumb-2only IT instruction it is possible to make up to four following instructions conditional. These instructions are called the IT block. The initial implementation of the DBT did not take the IT instructions into account, which can cause SVC instructions, inside an IT block, not to be executed. The hypervisor then loses control over the virtual machine. This problem was solved by taking the ITSTATE field into account when replacing sensitive instructions. This field holds all the information needed to execute instructions conditionally in Thumb-2 code. Now, only sensitive instructions that will actually be executed will be replaced by the improved DBT. Another improvement is the improved support for interworking branches, which are used to swich instruction sets in the code. VI. Memory management The memory management of the hypervisor is mainly the focus of development at The University of Manchester. However, to be able to virtualize Android some changes needed to be made to succesfully boot the Linux-kernel. The changes include the implementation of extra cases when the guest OS adds page table entries and the fixing of bugs causing the hypervisor to crash. These changes are not very substantial but the problems underlying these changes were sometimes very hard to detect. Mainly because of the limited debug opportunities. There were more problems discovered with the memory management, but these could be (temporarily) bypassed. These problems are described in the thesis and were reported to the people working on the memory management system. VII. Hardware As mentioned before, the guest OS runs in a virtual machine. This VM consists of virtual copies of the real hardware. The actual virtual hardware was however very limited in the hypervisor. This was due to the hypervisor being developed with an
outdated Linux-kernel with very limited support for the OMAP3530 SoC. In this Master’s thesis extra virtual hardware has been added to the VM. But, it was also necessary to add dummy modules and registers because Linux seems to use hardware that is not described in the OMAP manual. When this happened, the behaviour of the real hardware was mimicked in the hypervisor. Mostly, this means that a load retuns zero and a store is ignored. In one particular case, a load had to return another value because Linux expects this behaviour. VIII. Results It is now possible to boot Linux 2.6.37 to the command line interface with the hypervisor. However, it is not possible to input commands because of a problem with global interrupts. The unittest framework is able to boot tests using the hypervisor. IX. Conclusion The work in this Master’s thesis improved the hypervisor substantially but, considering the timeframe and the work that had to be done, it was not possible to fully support Android. However, this work can serve as a basis for further development towards supporting Android and other mobile operating systems. With the addition of unittesting framework it is now possible to avoid regression bugs by being able to test the hypervisor more systematic and more directed. This can improve the development speed. References [1] J.E. Smith and R. Nair., Virtual machines: versatile platforms for systems and processes. Morgan Kaufmann, 2005. [2] Gerald J. Popek and Robert P. Goldberg. Formal requirements for virtualizable thirdgeneration architectures. Commun. ACM, 17(7):412421, July 1974
Inhoudsopgave Voorwoord
i
Toelating tot bruikleen
ii
Inhoudsopgave
vii
1 Inleiding 1.1 Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Overzicht van de masterproef . . . . . . . . . . . . . . . . . . . . . . . . . 2 Gerelateerd werk 2.1 Virtualisatie . . . . . . . . . . . . . . . . . . . . . 2.1.1 Effici¨ent virtualiseren . . . . . . . . . . . . 2.1.2 Paravirtualisatie en volledige virtualisatie . 2.1.3 Type 1 en type 2 hypervisors . . . . . . . 2.2 ARM architectuur . . . . . . . . . . . . . . . . . 2.2.1 De ARM processoren . . . . . . . . . . . . 2.2.2 Uitvoeringstoestand van de processor . . . 2.2.3 Voorwaardelijke uitvoering . . . . . . . . . 2.2.4 Thumb-2 instructieset . . . . . . . . . . . 2.2.5 Geheugenbeheer . . . . . . . . . . . . . . . 2.2.6 Het ontwikkelplatform . . . . . . . . . . . 2.3 Android . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 De architectuur van Android . . . . . . . . 2.3.2 Verschillende versies van Android . . . . . 2.4 De hypervisor . . . . . . . . . . . . . . . . . . . . 2.4.1 Type 1 met volledige virtualisatie . . . . . 2.4.2 Dynamische binaire vertaling . . . . . . . 2.4.3 Gevirtualiseerd geheugenbeheer . . . . . . 2.4.4 Gevirtualiseerde hardware . . . . . . . . . 2.5 Besluit . . . . . . . . . . . . . . . . . . . . . . . . vi
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
1 2 3 4 5 5 6 7 8 9 9 10 11 12 15 17 19 20 21 21 22 22 24 26 27
3 Unittest functionaliteit 29 3.1 Gastbesturingssysteem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Uitbreidbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Thumb-2 ondersteuning 4.1 Voorwaardelijke uitvoering . . . . . . . . . . 4.1.1 Probleem met initi¨ele DBT algoritme 4.1.2 Aanpassingen DBT algoritme . . . . 4.2 Overige aanpassingen . . . . . . . . . . . . . 4.3 Resultaten . . . . . . . . . . . . . . . . . . . 4.4 Besluit . . . . . . . . . . . . . . . . . . . . .
. . . . . .
5 Gevirtualiseerd geheugenbeheer 5.1 Oplossingsmethoden en debuggen . . . . . . . 5.2 Aanpassingen . . . . . . . . . . . . . . . . . . 5.2.1 Geheugenadres van de gastpaginatabel 5.2.2 Probleem met invalideren . . . . . . . 5.2.3 Overige aanpassingen . . . . . . . . . . 5.3 Besluit . . . . . . . . . . . . . . . . . . . . . . 6 Gevirtualiseerde hardware 6.1 Oplossingsmethoden . . . 6.2 Energiebeheer . . . . . . . 6.3 Beveiligingsmechanisme . 6.4 Onbekende timer . . . . . 6.5 Bijkomende aanpassingen 6.6 Besluit . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
31 31 31 32 35 36 37
. . . . . .
38 38 40 40 42 42 43
. . . . . .
44 44 45 46 47 48 48
7 Besluit
50
8 Toekomstig werk
51
A Conditiecodes
52
B Unittesten
53
Bibliografie
56
vii
Hoofdstuk 1 Inleiding In de afgelopen jaren zijn mobiele toestellen zoals smartphones en tablets steeds populairder geworden. Deze toestellen combineren doorgaans een groot aantal functies zoals GPS, MP3-speler, camera en uiteraard telefoon, welke vroeger allemaal aparte toestellen waren. Door deze combinatie van functionaliteiten zijn de toestellen intern een samensmelting van verschillende soorten hardware en software, gemaakt door verschillende fabrikanten. Aangezien voor elk van deze functies een eigen processor aanwezig is, zorgt dit voor ineffici¨entie verdeling van de werklast over de beschikbare hardware met excessief batterijverbruik als gevolg. Deze ineffici¨entie kan verholpen worden door de verschillende functies de hardware te laten delen. Dit is slechts mogelijk als de beschikbare hardware krachtig genoeg is om al deze verschillende functies tegelijk te ondersteunen. Gelukkig zorgt de populariteit van mobiele toestellen ervoor dat de ontwikkeling niet stil staat en bijgevolg zijn de mobiele processoren de afgelopen jaren dan ook steeds krachtiger geworden en kunnen zich soms al meten met processoren in laptops. Het delen van ´e´en krachtige processor heeft als gevolg dat de verschillende kleinere processoren achterwege gelaten kunnen worden waardoor de hardwarekost van mobiele toestellen verminderd kan worden. Hardware kan echter niet zomaar gedeeld worden. Ten eerste moet de software van de verschillende fabrikanten van elkaar afgeschermd worden opdat vertrouwelijke informatie in de software niet zomaar beschikbaar zou zijn voor andere software. Ten tweede moet de software enkel in staat zijn de hardware aan te sturen die het nodig heeft om zijn functie uit te voeren. Dit zou anders, door bijvoorbeeld defecte of kwaadwillige software, tot ernstige schade kunnen leiden aan het toestel zoals een batterij die ontploft. Wat uiteraard ook ernstige gevolgen kan hebben voor de gebruiker. Door het gebruik van virtualisatie kan de beschikbare hardware veilig gedeeld worden door verschillende toepassingen. Iedere toepassing wordt dan uitgevoerd in een afgeschermde omgeving met gevirtualiseerde hardware. Een dergelijke omgeving wordt een virtuele machine (VM) genoemd. Dit concept wordt afgebeeld in Figuur 1.1. De virtuele 1
Figuur 1.1: Virtuele machines. hardware kan een volledige kopie van de fysieke hardware zijn of enkel delen daarvan, zie respectievelijk links en rechts op de figuur. Sommige types van virtualisatie laten zelf toe dat de gevirtualiseerde hardware volledig verschillend is van de echte hardware. De software die voor de goede werking van deze virtuele machines zorgt noemt een virtuelemachinemonitor (VMM) of hypervisor. Voor mobiele toestellen is op het vlak van hardware een ARM processor het meest populair [22]. Op het vlak van software is Google Android op het moment van schrijven het meest gebruikte mobiele besturingssysteem voor toestellen gebaseerd op een ARM processor [12]. Android gebruikt als basis de Linux-kernel en is, net als de Linux-kernel, als openbronsoftware vrij beschikbaar op het internet. Voor deze masterproef is Android dus een heel geschikt platform om door de hypervisor te ondersteunen.
1.1
Probleemstelling
Op dit moment is er nog geen hypervisor beschikbaar die volledige virtualisatie van de ARM-architectuur aankan en die Android kan virtualiseren. In samenwerking met The University of Manchester is op de Universiteit Gent sinds enkele jaren een dergelijke hypervisor in ontwikkeling. Deze hypervisor heeft echter nog enkele belangrijke beperkingen die het virtualiseren van Android tegenhouden. Om Android te kunnen virtualiseren moeten de eisen van Android grondig onderzocht worden en nagegaan worden waar de hypervisor nog niet aan deze eisen kan voldoen. Aangezien Android gebruik maakt van de Linux-kernel is het belangrijk om te onderzoeken welke versie van de kernel het meest gebruikt wordt. Dit is niet zo eenvoudig omdat Google 2
de kernel niet opgenomen heeft in de broncode van Android en er veel verschillende versies van Android beschikbaar zijn op het internet. De ontwikkeling van de hypervisor gebeurt op een BeagleBoard waarvoor een Android project bestaat [8]. Voor de populairste versie van Android, versie 2.3.7, wordt Linuxkernel versie 2.6.37 gebruikt [20]. Ook andere Android projecten gebruiken voor deze Android versie dezelfde versie van de kernel [3]. Deze kernel heeft heel wat meer hardwareondersteuning voor de ARM architectuur gekregen, in vergelijking met de 2.6.28 kernel die gebruikt werd voor de ontwikkeling van de hypervisor. De hardware die gebruikt wordt door deze kernel, en dus door Android, zal dus gevirtualiseerd moeten worden. Momenteel wordt er door de Linuxgemeenschap gewerkt aan het integreren van de aanpassingen die nodig zijn voor de ondersteuning van Android in recentere versies van de Linux-kernel [24]. Het doel is om meer recente versies te gebruiken in Android-toestellen. Versie 3.3 van de Linux-kernel bevat al een deel van de aanpassingen, en in de huidige ontwikkeling van versie 3.4 zullen nog meer aanpassingen komen [25]. Om dus mee te zijn met de ontwikkeling van Android is het belangrijk om ook recentere versies te ondersteunen. Bovenop de Linux-kernel draait het eigenlijke Android systeem [21]. Een belangrijk onderdeel van Android is de proces-VM waarin alle gebruikersapplicaties draaien. Deze virtuele machine maakt gebruik van de Thumb-2 instructieset van de ARM architectuur. Aangezien de ondersteuning van deze instructieset niet voldoende is, moet hier ook aandacht aan besteed worden.
1.2
Doelstelling
Het doel van deze masterproef was om het mobiele besturingssysteem Android te virtualiseren. Om dit te realiseren was echter heel wat werk nodig in verschillende onderdelen van de hypervisor waarvoor in deze masterproef geen tijd genoeg was. Daarom werd er voor gekozen om enkel de ondersteuning van de volgende eisen van Android te verbeteren. Eerst werd de ondersteuning van de Thumb-2 instructieset verbeterd, aangezien deze door Android zeker gebruikt wordt. Daarna werd de ondersteuning voor de bijhorende Linuxkernel verbeterd. Dit bestaat uit twee delen: de uitbreiding van de virtuele hardware en het aanpassen van het gevirtualiseerd geheugenbeheer. Naast deze doelstellingen was het ook de bedoeling om de hypervisor robuuster te maken. Daarom werd er ondersteuning voor unittesten ingebouwd waarmee delen van de 3
hypervisor herhaaldelijk getest kunnen worden. Met deze unittesten is het mogelijk om problemen te isoleren waardoor ze gemakkelijker opgelost kunnen worden.
1.3
Overzicht van de masterproef
In hoofdstuk 2 van deze masterproef wordt het gerelateerd werk besproken. Hierin wordt eerst algemeen uitgelegd wat virtualisatie inhoudt en hoe dit van toepassing is op deze masterproef. Daarna wordt de staat en werking van de hypervisor waarmee de ontwikkeling is begonnen besproken samen met de problemen die het virtualiseren van Android in de weg staan. Het volgende hoofdstuk bespreekt de unittest functionaliteit die toegevoegd werd aan de hypervisor. Hoofdstuk 4 beschrijft de problemen omtrent de ondersteuning van de Thumb-2 instructieset, en hoe deze werden opgelost. Verder wordt in hoofdstuk 5 de aandacht gevestigd op het gevirtualiseerd geheugenbeheer. Ten slotte wordt in hoofdstuk 6 uitgelegd hoe de ondersteuning van specifieke hardware is verbeterd.
4
Hoofdstuk 2 Gerelateerd werk In dit hoofdstuk zal eerst informatie gegeven worden over virtualisatie: waarom wordt aan virtualisatie gedaan en wat zijn de vereisten van een architectuur om dit effici¨ent te realiseren? Daarna worden de verschillende types virtualisatie toegelicht en de wat gebruikelijke technieken zijn. Hierbij zal ook verantwoord worden waarom er gekozen werd voor een bepaald type virtualisatie. Nadien zal de ARM architectuur in meer detail uitgelegd worden en de invloed hiervan op het ontwerp van de hypervisor. Ook worden kort de gebruikte hardware en de ontwikkelmethoden besproken. Daarna wordt de architectuur van Android behandeld en de verschillende versies die ervan beschikbaar zijn. Als laatste wordt de staat van de hypervisor bij aanvang van deze masterproef besproken. Daarbij wordt aandacht geschonken aan de werking van verschillende onderdelen en de openstaande problemen.
2.1
Virtualisatie
Het virtualiseren van hardware wordt om verschillende redenen toegepast [33]. In de context van mobiele systemen zijn de energie-effici¨entie en het plaatsgebruik van hardware de belangrijkste redenen om voor virtualisatie te kiezen. Door middel van virtualisatie is het immers mogelijk om hardware te delen waardoor er minder hardware nodig is om aan de eisen van eenzelfde aantal softwarecomponenten te voldoen. Dit heeft dan weer een positieve invloed op het energieverbruik. Er zijn echter ook nadelen verbonden aan het delen van hardware. Softwarecomponenten die zich niet gedragen volgens de regels, al dan niet opzettelijk, zijn schadelijker wanneer de hardware gedeeld wordt. Een voorbeeld hiervan is het volledig opeisen van de hardware door ´e´en softwarecomponent waardoor deze niet meer kan gebruikt worden door andere softwarecomponenten. Wanneer softwarecomponenten niet goed van elkaar afgeschermd zijn kan bovendien vertrouwelijke informatie lekken naar alle softwarecomponenten die van dezelfde hardware gebruik maken. Deze nadelen kunnen echter vermeden worden door een goed ontwerp van de virtualisatiesoft5
ware. Om de softwarecomponenten van elkaar te isoleren maakt de virtualisatiesoftware voor iedere softwarecomponent een eigen virtuele machine (VM) aan. In deze masterproef is de softwarecomponent meestal een besturingssysteem, daarom wordt verder in deze masterproef de term (gast)besturingssysteem gebruikt in plaats van softwarecomponent. Een VM is een voorstelling van de hardware zoals het gastbesturingssyteem die zou zien mocht die rechtstreeks op de fysieke hardware draaien. De virtualisatiesofware is verantwoordelijk voor de goede werking van deze VMs en wordt ook een virtuele machinemonitor (VMM) genoemd, of een hypervisor. Er zijn twee grote categorie¨en: systeem-VMs en proces-VMs. Zoals de naam aangeeft kan binnenin een proces-VM ´e´en enkel proces uitvoeren. Voorbeelden van proces-VMs zijn de Java VM en de Dalvik VM gebruikt door Android [29, 21]. Systeem-VMs virtualiseren een volledig hardwareplatform en ondersteunen dus de uitvoering van een volledig besturingssyteem. Voorbeelden van hypervisors die gebruik maken van dit type VMs zijn VirtualBox en Xen Hypervisor [7, 11]. De hypervisor die het onderwerp is van deze masterproef wordt ontwikkeld voor mobiele toestellen en moet ondersteuning bieden voor volledige (mobiele) besturingssystemen. Deze hypervisor hoort dus bij de categorie van systeem-VMs.
2.1.1
Effici¨ ent virtualiseren
Voor het implementeren van een hypervisor is het interessant om te kijken hoe dit best aangepakt wordt. Een paper van Popek en Goldberg beschrijft hypervisors theoretisch. Volgens de paper moet een volwaardige hypervisor voldoen aan drie eigenschappen: controle over de hardware, gelijkheid en effici¨entie [30]. Het is vanzelfsprekend dat de hypervisor de volledige controle over de hardware moet hebben zodat de gastbesturingssystemen niet zomaar de configuraties van de gedeelde hardware, zoals het geheugen en de processor, kunnen lezen of aanpassen. Gelijkheid wijst er op dat besturingssystemen binnenin een VM hetzelfde gedrag vertonen alsof ze rechtstreeks op de fysieke hardware zouden uitvoeren, met uitzondering van een verschil in snelheid. Dit verschil zal door het gebruik van virtualisatie altijd aanwezig zijn aangezien de hypervisor moet ingrijpen om te voldoen aan de vorige eigenschap. Om de laatste eigenschap uit te leggen moet eerst het verschil tussen verschillende types instructies behandeld worden: enerzijds tussen bevoorrechte en onbevoorrechte instructies en anderzijds tussen gevoelige en ongevoelige instructies. 6
Een bevoorrechte instructie zal een exceptie opwerpen wanneer deze uitgevoerd wordt in een onbevoorrechte modus. Onbevoorrechte instructies zijn instructies die hetzelfde gedrag vertonen in alle uitvoeringsmodi. Gevoelige instructies worden opgedeeld in twee types: controle- en gedragsgevoelige instructies. Controlegevoelige instructies zijn instructies die het fysieke geheugen of de uitvoeringsmodus van de processor proberen aanpassen en die de controle-eigenschap kunnen schenden. Gedragsgevoelige instructie zijn instructies waarvan het gedrag afhangt van de plaats in het fysiek geheugen of van de uitvoeringsmodus van de processor. Een instructie die noch controle- of gedragsgevoelig is, wordt een ongevoelige instructie genoemd. Met deze definities kan de laatste eigenschap als volgt uitgelegd worden: effici¨entie vereist dat alle ongevoelige instructies rechtstreeks op de hardware uitgevoerd moeten worden, en dat dus enkel gevoelige instructies ge¨emuleerd worden door de hypervisor. Enkel wanneer alle gevoelige instructies ook bevoorrechte instructies zijn kan een hypervisor, volgens de theorie van Popek en Goldberg, effici¨ent ge¨ımplementeerd worden [30]. Dit is echter niet het geval voor de ARM architectuur waar bijvoorbeeld de CPS instructie, die de processor modus wil veranderen, als NOP wordt behandeld in de onbevoorrechte modus [14]. Dit is dus een gevoelige instructie, maar ze is niet bevoorrecht omdat ze geen exceptie opwerpt. In de praktijk is het echter wel mogelijk om een effici¨ente hypervisor te ontwikkelen door gebruik te maken van technieken zoals dynamische binaire vertaling of met een andere architectuur die hardwareondersteuning voor virtualisatie heeft.
2.1.2
Paravirtualisatie en volledige virtualisatie
De beschikbare technieken voor het realiseren van systeemvirtualisatie kunnen ingedeeld worden in paravirtualisatie en volledige virtualisatie. Bij volledige virtualisatie wordt de fysieke hardware volledig ge¨emuleerd en zal het bovenliggende besturingssysteem er zich niet van bewust zijn dat het te maken heeft met virtualisatie. Een besturingssysteem dat zonder problemen op de fysieke hardware kan uitvoeren zal dus zonder aanpassingen op de hypervisor kunnen uitvoeren. De hypervisor moet in dit geval wel alle gevoelige instructies onderscheppen en emuleren. Volledige virtualisatie zorgt voor een grote virtualisatiekost maar heeft als voordeel dat de besturingssystemen niet aangepast moeten worden. Deze virtualisatiekost kan vermeden worden wanneer er hardwareondersteuning voor virtualisatie is. Deze hardwareondersteuning is momenteel nog niet beschikbaar voor de ARM architectuur. 7
(a) Type 1 of bare-metal: hypervisor draait rechtstreeks op de hardware.
(b) Type 2 of hosted: hypervisor draait bovenop een besturingssysteem.
Figuur 2.1: Type 1 en type 2 hypervisors. Bij paravirtualisatie wordt het gastbesturingssysteem gedeeltelijk aangepast zodat het een interface herkent die aangeboden wordt die de moeilijk virtualiseerbare eigenschappen van de architectuur omzeilt [35]. Op die manier wordt de virtualisatiekost zo veel mogelijk gereduceerd. Dit zorgt echter wel voor grote onderhoudsproblemen. Voor ieder mogelijke combinatie van besturingssysteem en hypervisor moeten deze aanpassingen immers gemaakt worden. Zowel bij een update van het besturingssysteem als bij de hypervisor is het dus mogelijk dat de aanpassingen opnieuw doorgevoerd moeten worden. Voor de hypervisor die gebruikt wordt in deze masterproef werd voor volledige virtualisatie gekozen aangezien er geen aanpassingen aan de gastbesturingssystemen nodig zijn. Er kan dus met verschillende gastbesturingssystemen gewerkt worden.
2.1.3
Type 1 en type 2 hypervisors
Hypervisors kunnen ook ingedeeld worden op basis van de plaats die ze innemen in de hardware/software-stapel. Wanneer de hypervisor rechtstreeks uitvoert op de hardware spreken we van een type 1 of bare-metal hypervisor. Het is ook mogelijk dat de hypervisor een gebruikersprogramma is dat zelf een besturingssysteem nodig heeft om uit te voeren. Deze hypervisors zijn type 2 of hosted hypervisors. In Figuur 2.1 worden deze twee types voorgesteld. Een type 1 hypervisor draait rechtstreeks op de hardware en dus zal het ontwerp ervan op enkele punten gelijkaardig zijn aan dat van een traditioneel besturingssysteem. Zo moeten er drivers voor de hardware zijn en moet de hardware ge¨ınitialiseerd worden. 8
Een type 2 hypervisor steunt voor de aansturing van de hardware op de drivers van het besturingssysteem. Aangezien er geen drivers ontwikkeld en ingebouwd moeten worden voor een type 2 hypervisor kan de ontwikkeling ervan een stuk sneller verlopen en is het gemakkelijker om te debuggen. Een traditioneel besturingssysteem zal echter naast de hypervisor nog andere processen uitvoeren die ook de nodige verwerkingstijd zullen innemen. Alle instructies van een gastbesturingssysteem moeten bovendien nog door een extra laag software. De prestaties van een type 2 hypervisor zullen dus steeds lager zijn dan de prestaties van een type 1 hypervisor [32]. Daarom werd voor de hypervisor van dit werk gekozen voor een type 1 implementatie. Voorbeelden van type 1 en type 2 hypervisors zijn respectievelijk Xen en VirtualBox [7, 11].
2.2
ARM architectuur
De ARM processor is met meer dan 90% marktaandeel de populairste processor voor mobiele toestellen [17, 22]. Daarom werd er gekozen om met de hypervisor de ARM architectuur te virtualiseren en is het dus belangrijk om deze in meer detail te bespreken. In wat volgt zullen de aspecten van de ARM architectuur, die voor deze masterproef interessant zijn, besproken worden. Eerst wordt algemeen informatie gegeven over de verschillende ARM processoren en de verschillende modi waarin een processor kan uitvoeren. Daarna komt de voorwaardelijke uitvoering van instructies aan bod. Daarna wordt uitleg gegeven over de verschillende instructiesets van de architectuur: ARM, Thumb en Thumb-2. Ten slotte zal wordt het geheugenbeheer besproken.
2.2.1
De ARM processoren
ARM processoren zijn beschikbaar in verschillende types: van processoren voor smartcards tot processoren voor krachtige mobiele toestellen zoals smartphones en tablets. De processoren worden ingedeeld in drie profielen: Cortex-A, Cortex-R en Cortex-M [2]. De processoren voor ingebedde systemen maken deel uit van het Cortex-M en Cortex-R profiel. Het Cortex-R profiel bevat de processoren voor real-time toepassingen, waar een goede afweging wordt gemaakt tussen laag energieverbruik en hoge prestaties. Processoren voor microcontrollers, waar er vooral gefocust wordt op laag energieverbruik, komen terecht in het Cortex-M profiel. Het Cortex-A profiel bevat de toepassingsprocessoren die 9
Figuur 2.2: Schema van het PSR.
Figuur 2.3: Schema van het APSR. hoge prestaties leveren en zijn bedoeld voor gebruik in mobiele toestellen zoals smartphones en tablets. Iedere processor implementeert een bepaalde variant van de ARM architectuur. Processoren uit het Cortex-A profiel ondersteunen de ARMv7-A architectuur, die in dit werk gevirtualiseerd wordt. De ARMv7-A architectuur wordt verder in dit werk de ARM architectuur genoemd. Deze architectuur implementeert de ARM en Thumb-2 instructiesets en biedt ondersteuning voor geheugenbeheer met geheugenbescherming en adresvertaling die gebruik maakt van paginatabellen. Deze eigenschappen worden verder in meer detail besproken.
2.2.2
Uitvoeringstoestand van de processor
De uitvoeringstoestand van de processor wordt bijgehouden in het Current Program Status Register (CPSR). Figuur 2.2 toont dit register met aanduiding van de verschillende velden. De grijze bits zijn gereserveerd en geven bij het uitlezen altijd de waarde nul terug. Dit zijn de belangrijkste velden van het CPSR die verder in meer detail behandeld zullen worden: • N, Z, C, V: dit zijn conditiecode vlaggen en worden gewijzigd na het uitvoeren van instructies die de vlaggen willen wijzigen. De verschillende vlaggen zijn: – N: Negatieve conditiecode vlag, – Z: Nul conditiecode vlag, – C: Carry conditiecode vlag, – V: Overflow conditiecode vlag. • IT 7:2, IT 1:0: Deze velden vormen samen het ITSTATE veld dat de uitvoeringstoestand bijhoudt voor een IT instructie. Deze velden zijn enkel zinvol als de 10
processor zich in Thumb-2 modus bevindt. • T: Bepaalt, samen met de J bit, de instructieset modus van de processor. De J bit wordt niet gebruikt in deze masterproef en staat altijd op 0. Als de T bit op 1 staat is de instructieset Thumb-2 anders is deze ARM. • M: Bepaalt de uitvoeringsmodus van de processor. De enige onbevoorrechte modus is de user modus en wordt gecodeerd als 0b10000. Alle andere, geldige, modi zijn wel bevoorrecht. De ARM architectuur beschikt over zeven verschillende uitvoeringsmodi waarin de processor zich kan bevinden. De user modus (USR) is de enige onbevoorrechte modus van de architectuur. De bevoorrechte modi zijn: system (SYS), supervisor (SVC), abort (ABT), undefined (UND), interrupt (IRQ) en fast interrupt (FIQ). Het CPSR kan enkel uitgelezen of aangepast worden in een bevoorrechte modus. Een deel van dit register is ook beschikbaar in de gebruikersmode en wordt het Application Program Status Register (APSR) genoemd. Dit is geen apart register maar een gemaskeerde versie van het CPSR, zie Figuur 2.3. Voor iedere uitvoeringsmodus, met uizondering van de gebruikersmodus, is er een Saved Program Status Register (SPSR), dat hetzelfde formaat heeft als het CPSR en de waarde van het CPSR register bijhoudt wanneer van de gebruikersmodus naar een bevoorrechte modus veranderd wordt. Wanneer er dan terug gewisseld wordt naar de gebruikersmodus wordt het SPSR teruggeschreven naar het CPSR. De hypervisor zal altijd uitvoeren in een van de bevoorrechte modi. Het gastbesturingssysteem zal enkel uitvoeren in de gebruikersmodus. Dit is nodig opdat de hypervisor de controle over de hardware zou kunnen behouden.
2.2.3
Voorwaardelijke uitvoering
Een belangrijk kenmerk van de ARM architectuur is de voorwaardelijke uitvoering van het grootste deel van de instructies. Dit kenmerk wordt ook wel de geprediceerde uitvoering van instructies genoemd. Aangezien bijna alle instructies voorwaardelijk uitgevoerd kunnen worden, zijn er minder voorwaardelijke spronginstructies nodig. Daarom wordt de code een stuk compacter wat voordelig is voor het cachegebruik [26]. Bekijk als voorbeeld de pseudocode uit Figuur 2.4(a). In dit voorbeeld wordt R2 bij R1 opgeteld als R1 nul is, anders wordt R3 opgeteld bij R1. Na compilatie wordt de code 11
if ( R1 == 0) R1 = R1 + R2 ; else R1 = R1 + R3 ; (a) Pseudocode
L1 L2
CMP R1, #0 BNE L1 ADD R1, R1, R2 B L2 ADD R1, R1, R3 ...
(b) Zonder predicaten
CMP R1, #0 ADDEQ R1, R1, R2 ADDNE R1, R1, R3 (c) Met predicaten
Figuur 2.4: Voorwaardelijke uitvoering van ARM code. uit Figuur 2.4(b) genereerd als enkel de spronginstructies geprediceerd zijn. Wanneer alle instructies geprediceerd zijn, wordt de code uit Figuur 2.4(c) gegenereerd. Zonder geprediceerde instructies neemt dit stukje code vijf ARM instructies in, er zijn immers twee spronginstructies nodig om over ´e´en van de twee ADD instructies te springen. Met geprediceerde instructies zijn geen spronginstructies nodig om dezelfde functionaliteit te verkrijgen. In dit voorbeeld zorgt het gebruik van geprediceerde instructies dus voor 40% minder instructies. De eerste vier bits van een geprediceerde ARM instructie bepalen de conditiecode. De conditiecode wordt vergeleken met de conditievlaggen uit het CPSR register, zie Sectie 2.2.2 voor het formaat van dit register. De conditiecode op zich bestaat uit twee delen: de eerste drie bits vormen de basisconditie, de laatste bit geeft aan of deze basisconditie tegengesteld moet worden. Bijvoorbeeld, de conditiecode EQ (equal), gecodeerd als 0b0000, geeft aan dat de Z (zero) vlag op 1 moet staan. De conditiecode NE (not equal) 0b0001 geeft aan dat de vlag op 0 moet staan. EQ is het omgekeerde van NE. Voor sommige instructies zijn de eerste vier bits gelijk aan 0b1111. Deze instructies kunnen niet voorwaardelijk gemaakt worden en zullen dus altijd onvoorwaardelijk uitgevoerd worden [14]. In bijlage A worden de verschillende conditiecodes samen met hun codering en betekenis opgesomd.
2.2.4
Thumb-2 instructieset
De ARM instructieset bestaat uitsluitend uit 32-bit instructies [14]. Ingebedde systemen beschikken echter niet over veel cachegeheugen en moeten energiezuinig zijn: om deze reden werd de 16-bit Thumb instructieset ge¨ıntroduceerd. Thumb code zal in het algemeen kleiner zijn dan ARM code waardoor er minder instructies opgehaald moeten worden en de cache minder energie zal verbruiken [23]. 12
De Thumb instructieset is een deelverzameling van de ARM instructieset en bestaat uitsluitend uit 16-bit instructies. Om de codering van instructies compacter te maken werd de conditiecode weggelaten en kunnen enkel registers R0 tot en met R7 gebruikt worden. Door de halvering van het aantal bits is de expressiviteit van Thumb-instructies wel verminderd. In vergelijking met ARM code zullen hierdoor meer instructies nodig zijn om dezelfde functionaliteit te verkrijgen, maar door de kleinere instructies zal de code gemiddeld 30% compacter zijn [18]. Om optimale gecompileerde code te verkrijgen wordt code, waar de prestatie kritisch is, gecompileerd naar ARM en code, waar compactheid belangrijker is, gecompileerd naar Thumb [18, 23]. Deze menging van Thumb en ARM code kan gebeuren met heel grove granulariteit (per softwaremodule) tot heel fijne granulariteit (binnenin een functie). Om de geschikte menging te bepalen zijn echter extra hulpmiddelen zoals een profiler nodig die werkt op basis van heuristieken [31, 23]. Ook zijn er nog andere nadelen zoals het beperkt aantal instructies en het weglaten van de voorwaardelijke uitvoering. Daarom werd de Thumb-2 instructieset ge¨ıntroduceerd. Thumb-2 bestaat uit zowel 16- als 32-bit instructies die gemakkelijk door elkaar gebruikt kunnen worden zonder de processormodus te veranderen [31]. Dit reduceert ook de extra instructies die nodig zijn om de instructieset te wijzigen. Ook Thumb-2 instructies bevatten geen conditiecode maar kunnen wel voorwaardelijk uitgevoerd worden met behulp van een nieuwe instructie, de IT of If-Then instructie. De IT instructie bepaalt een IT-blok die ´e´en tot vier instructies bevat die voorwaardelijk uitgevoerd zullen worden. De syntax voor deze instructie is als volgt: ITxyz conditiecode. De operand van de IT instructie bepaalt de conditiecode voor de eerste instructie in het IT blok. De conditiecodes van de volgende instructies worden bepaald door de waarde van de condities x, y en z, voor respectievelijk de eerste, tweede en derde instructie. Deze condities zijn optioneel en kunnen ofwel T ofwel E zijn. Wanneer de conditie T is wordt dezelfde conditiecode gebruikt als die van de eerste instructie, als de conditie E is wordt de tegengestelde conditiecode gebruikt. In Figuur 2.5 wordt de Thumb-2 code gegeven voor het voorbeeld van Figuur 2.4(a). Het IT blok bevat twee instructies waarbij de conditiecode EQ is en de conditie voor de ander instructie E is. Het enige verschil tussen de ARM en Thumb-2 code is de IT instructie die de conditiecodes voor de volgende twee instructies bepaalt. Na het uitvoeren van de IT instructie worden de ITSTATE velden van het CPSR register ingesteld. De eerste drie bits van ITSTATE zijn de basisconditie voor het ITblok, de laatste vijf bits bepalen de grootte van het IT-blok en de minst significante bit 13
CMP ITE ADD ADD
R1 , #0 EQ R1 , R1 , R2 R1 , R1 , R3
Figuur 2.5: Voorwaardelijke uitvoering van Thumb-2 code. Tabel 2.1: Opeenvolgende toestanden van ITSTATE. ITSTATE: [7:5] basisconditie basisconditie basisconditie basisconditie 000
[4] [3] [2] [1] [0] b1 b2 b3 b4 1 b1 b2 b3 1 0 b1 b2 1 0 0 b1 1 0 0 0 0 0 0 0 0
Toestand IT-blok met 4 IT-blok met 3 IT-blok met 2 IT-blok met 1 Geen IT-blok
instructies instructies instructies instructie
van de conditiecode voor iedere instructie uit het IT-blok. De grootte van het IT-blok wordt bepaald door de positie van de minst significante 1 bit. Met de ITSTATE heeft de processor dus genoeg informatie om de instructies in het IT-blok voorwaardelijk uit te voeren. Na het uitvoeren van een voorwaardelijke instructie worden de vijf laatste bits verschoven naar links. Als na het uitvoeren van een voorwaardelijke instructie de laatste drie bits van ITSTATE nul zijn, wordt ITSTATE gereset op nul en wordt uit het IT-blok gegaan. In Tabel 2.1 worden de opeenvolgende toestanden gegeven waarbij b1 staat voor de minst significante bit van de conditiecode van de eerst volgende instructie, b2 voor de tweede, enzovoort. De conditiecode voor de eerste instructie is dan de samenvoeging van basisconditie en b1, voor de tweede instructie de samenvoeging van basisconditie en b2, enzovoort. Thumb-2 reduceert de grootte van de code met gemiddeld 20% en behoudt tot 98% van de prestaties in vergelijking met ARM code [31]. Dit is een heel stuk beter dan de resultaten van Thumb. Andere voordelen van de Thumb-2 instructieset tegenover de Thumb instructieset zijn dat de Thumb-2 instructieset bijna alle instructies uit de ARM instructieset bevat en er niet gewisseld moet worden van processormode om 16- en 32-bit instructies door elkaar te gebruiken [14]. Het is mogelijk om tijdens de uitvoering de instructieset te wijzigen door het gebruik van een speciale spronginstructie: de interworking branch. Een interworking branch kan voorkomen bij spronginstructies maar ook bij POP, LDR en LDM instructies, deze laden ´e´en of meerdere registers in van het geheugen waaronder eventueel de programmateller waardoor ook een sprong kan gebeuren. Bij een interworking branch bepalen de laatste 14
twee bits van het doeladres de instructieset. Als deze bits 0b00 zijn wordt gesprongen naar ARM code. Als de minst significante bit 1 is wordt gesprongen naar Thumb-2 code en moet deze bit op 0 gezet worden om een juiste uitlijning te verkrijgen. Als de bits 0b10 zijn, is het sprongadres verkeerd uitgelijnd en is dus ongeldig. Als dit voorkomt zal een exceptie opgeworpen worden. De ondersteuning voor de Thumb-2 instructieset werd ge¨ımplementeerd ter ondersteuning van FreeRTOS. FreeRTOS is een klein real-time besturingssysteem [9]. In tegenstelling tot Linux ondersteunt het zowel de ARM instructieset als de Thumb-2 instructieset en kan dus gebruikt worden om de Thumb-2 ondersteuning te testen.
2.2.5
Geheugenbeheer
Virtueel geheugen is een belangrijk aspect van geavanceerde besturingssystemen omdat dit de mogelijkheid biedt om meerdere processen op transparante wijze gebruik te laten maken van het fysiek geheugen. De geheugenadressen, gebruikt in de software, worden dan logische of virtuele adressen genoemd. De virtuele adressen worden door het gebruikte geheugenbeheersysteem vertaald naar fysieke adressen. Deze vertaling gebeurt in de Memory Management Unit (MMU). Enkel wanneer de MMU aangeschakeld is, worden virtuele geheugenadressen vertaald naar fysieke geheugenadressen. Wanneer de MMU uitgeschakeld is, zijn de virtuele adressen gelijk aan de fysieke adressen. De structuur en werking van het geheugenbeheer van ARM is belangrijk voor de ontwikkeling van de hypervisor omdat dit ook gevirtualiseerd moet worden. Verschillende gastbesturingssystemen mogen immers niet in staat zijn elkaars toegewezen geheugen zomaar te lezen of aan te passen. Het geheugenbeheer van de ARMv7-A architectuur heet Virtual Memory System Achitecture (VMSAv7) en maakt gebruik van een 2-niveau vertalingsschema. Het fysiek geheugen wordt ingedeeld in vier paginagroottes: supersectie, sectie, grote pagina en kleine pagina. Deze hebben respectievelijk een grootte van 16 MB, 1 MB, 64 KB en 4 KB. In de paginatabel kunnen verschillende types verwijzingen voorkomen die wijzen naar een pagina of een paginatabel op het tweede niveau. De paginatabel op het eerste niveau bevat verwijzingen naar secties, supersecties en paginatabellen op het tweede niveau. Op het tweede niveau wordt verwezen naar kleine en grote pagina’s. Op beide niveaus kunnen ook lege plaatsen voorkomen. Het type van een verwijzing wordt bepaald door de laatste twee bits van de verwijzing. Voor een paginatabel op het eerste niveau zijn de mogelijke 15
waarden: 0b01 voor een verwijzing naar een paginatabel op het tweede niveau en 0b10 voor een sectie of supersectie. Het verschil tussen een sectie of supersectie wordt bepaald door een andere bit in de verwijzing. Voor een paginatabel op het eerste niveau zijn de mogelijke waarden: 0b01 voor een grote pagina en 0b1x voor een kleine pagina, waarbij x zowel 1 als 0 kan zijn. Op beide niveaus is een verwijzing waarbij de laatste twee bits 0b00 zijn een lege verwijzing, dit wordt gezien als een ongeldige verwijzing. Alle geldige verwijzingen bevatten het basisadres van de pagina, of paginatabel waar ze naar verwijzen. Naast dit basisadres en de bits die het type bepalen worden nog andere bits bijgehouden die onder andere belangrijk zijn voor de toegangsbeperking. Deze bits kunnen bijvoorbeeld aanduiden dat een sectie in de onbevoorrechte modus enkel gelezen mag worden maar niet mag worden aangepast. In Figuur 2.6 wordt een deel van het fysiek geheugen voorgesteld met een sectie en enkele grote pagina’s. Om de figuur leesbaar te houden werd het fysiek geheugen voorgesteld in blokken van 64 KB, de grootte van een grote pagina. De pijlen wijzen naar het eerste adres van de pagina of paginatabel. Dit is dus het basisadres. Een vertaling van een virtueel adres naar een fysiek adres gebeurt op de volgende manier. In een speciaal register, het Translation Table Base Register (TTBR), wordt de locatie van de paginatabel op het eerste niveau opgeslagen. Een deel van het virtueel adres wordt gebruikt als index in deze tabel. Als op die plaats in de tabel een verwijzing naar een sectie of supersectie zit, wordt het virtueel adres vertaald door het basisadres van de (super)sectie en de paginaindex uit het virtueel adres samen te voegen. Anders wordt de paginatabel op het tweede niveau opgehaald waar naar verwezen wordt. In deze paginatabel wordt opnieuw een deel van het virtueel adres als index gebruikt, deze keer voor de tabel op het tweede niveau. De vertaling van het virtueel adres gebeurt dan via een kleine of grote pagina. In Figuur 2.7 wordt een virtueel adres (VA) vertaald naar een fysiek adres (FA) wanneer dit fysiek adres zich in een kleine pagina bevindt. In de figuur staat N1 voor het eerste niveau en N2 voor het tweede niveau. Bij het vertalen van een virtueel adres kunnen er verschillende fouten optreden. Wanneer een adres verwijst naar een lege plaats zal er een vertaalfout opgeworpen worden. Iedere verwijzing in de paginatabel heeft toegangsbits die worden nagekeken wanneer een virtueel adres gebruikt wordt. Wanneer een bepaalde lees- of schrijfopdracht niet geoorloofd is, zal er een permissiefout opgeworpen worden. Beide fouten worden algemeen een datafout genoemd. Als een datafout optreedt, wordt het virtueel geheugenadres en het 16
Figuur 2.6: Paginatabellen op het eerste en tweede niveau. fouttype bijgehouden. Met deze twee gegevens moet het besturingssysteem de fouten proberen afhandelen.
2.2.6
Het ontwikkelplatform
De huidige ontwikkeling van de hypervisor gebeurt op een BeagleBoard [15]. Dit bord is gemaakt met het oog op de ontwikkeling van openbronsoftware op openbronhardware. Openbronhardware wil zeggen dat alle documentatie over de hardware en het ontwerp ervan vrij beschikbaar is. Voor deze masterproef zijn belangrijkste onderdelen van het BeagleBoard de Texas Instruments (TI) OMAP3530 System-on-Chip (SoC), de JTAG en UART voor het debuggen en communiceren over de seri¨ele poort naar de computer en de SD/MMC geheugenkaartlezer. Een SoC combineert al de nodige hardwarecomponenten voor een bepaald systeem op ´e´en chip. De OMAP is gericht op het gebruik in mobiele ingebedde systemen zoals smartphones [34]. De OMAP kan opgedeeld worden in verschillende subsystemen. Het Microprocessor Unit (MPU) subsysteem bevat de ARM rekenkern met onder andere een ARM Cortex-A8 17
Figuur 2.7: Vertaling van een VA op twee niveaus.
processor, die de eerder vernoemde ARMv7 architectuur gebruikt, en L1 en L2 cachegeheugen. Het geheugen subsyteem omvat alle verschillende geheugentypes: intern ROM en RAM, SDRAM, NAND en andere. Het L3 en L4 interconnectiebus subsysteem verbint verschillende subsystemen, modules, randapparaten en extern en intern geheugen met elkaar. Andere subsystemen zijn het IVA subsysteem voor het verwerken van audio en video, het ISP subsysteem voor het verwerken van camera-afbeeldingen en een display subsysteem voor het aansluiten van schermen. In Figuur 2.8 wordt de OMAP SoC in een diagram voorgesteld. De volgende afkortingen worden gebruikt: SDRAM Controller (SDRC), General-Purpose Memory Controller (GPMC), General-Purpose I/O (GPIO), System Control Module (SCM) en Power, Reset and Clock Manager (PRCM). De OMAP SoC maakt gebruik van memory-mapped I/O. Om te communiceren met het de hardware, bijvoorbeeld het geheugen, de subsystemen of randapparaten, worden geheugentoegangen gebruikt. Er worden 32-bit geheugenadressen gebruikt en dus is de geheugenruimte 232 B = 4 GB groot. Deze ruimte wordt hi¨erarchisch opgedeeld. Eerst wordt een opdeling gemaakt in vier kwartalen Q0 tot Q3 die elk 1 GB groot zijn. Deze kwartalen worden verder opgesplitst per subsysteem of randapparaat. De belangrijke kwartalen zijn Q1, die de geheugenadressen voor de registers van de L3 en L4 bus bevat, en Q2 waar het SDRAM werkgeheugen zich bevindt. Om met het BeagleBoard te kunnen werken wordt, gebruik gemaakt van het Flys18
Figuur 2.8: Diagram van de OMAP3530 SoC. watter debugbord [4]. Dit bord wordt via een USB poort verbonden met de computer en wordt aan het BeagleBoard aangesloten via zowel de JTAG als de UART interface. Via de UART interface kunnen nieuwe versies van de hypervisor in het geheugen geplaatst worden en kan de output van de hypervisor uitgelezen worden. Met behulp van de OpenOCD software wordt via de JTAG interface gecommuniceerd met de debug module van de ARM processor [6]. Met deze software is het is mogelijk om break- en watchpoints in te stellen. Een breakpoint zal de processor stoppen wanneer voor het uitvoeren van een vooraf bepaalde instructie. Een watchpoint stopt de processor wanneer een lees- of schrijfopdracht met een bepaald geheugenadres uitgevoerd moet worden. Vanaf deze punten kan per instructie verdergestapt worden door de code. Met OpenOCD is het ook mogelijk om waarden uit het geheugen te lezen en kunnen instructies gedeassembleerd worden. OpenOCD en de output van de hypervisor zijn de enige mogelijkheden om problemen te debuggen. Dit maakt het soms moeilijk om de oorzaak van problemen te weten te komen, zeker omdat OpenOCD niet stabiel is.
2.3
Android
Het mobiele besturingssysteem Android is vandaag ´e´en van de meest populaire mobiele besturingssystemen voor smartphones die gebruik maken van een ARM processor [12, 13]. 19
Figuur 2.9: De architectuur van Android De broncode van Android is vrij beschikbaar [19]. Het besturingssysteem is gebaseerd op de Linux-kernel, waarvan de broncode ook vrij beschikbaar is [10]. Dit zorgt dat Android een goede keuze is om te ondersteunen met de hypervisor. In wat volgt zal de globale architectuur van Android uitgelegd worden. Daarna volgt een bespreking van de verschillende versies Android en wordt verantwoord waarom een bepaalde versie gebruikt werd om de ontwikkeling van de hypervisor op te baseren.
2.3.1
De architectuur van Android
In Figuur 2.9 is de architectuur van Android compact voorgesteld. De onderste laag van de architectuur is de Linux-kernel. Deze kernel is echter op verschillende plaatsen aangepast om Android te kunnen ondersteunen [16]. De aanpassingen hebben vooral te maken met specifieke drivers voor Android, verbeterd energiebeheer en ondersteuning voor hardwareplatformen die gebruikt worden in smartphones. Boven de Linux-kernel draaien enkele standaard C/C++ bibliotheken die gebruikt worden door verschillende onderdelen van het Android systeem. Bibliotheken voor het weergeven van lettertypes en het afspelen van audio en video zijn hier enkele voorbeelden van. Deze bibliotheken worden beschikbaar gesteld aan ontwikkelaars van applicaties via het applicatieraamwerk. De Android Runtime bestaat uit enkele Java bibliotheken en de Dalvik proces-VM. Deze virtuele machine is een belangrijk onderdeel van het Android besturingssysteem. Applicaties worden ontwikkeld in Java maar worden a priori vertaald naar de Dalvik bytecode. Deze bytecode werd speciaal ontworpen om een zo laag mogelijk geheugenge20
bruik te hebben. De bytecode wordt dan door de Dalvik-VM ge¨ınterpreteerd. Sinds versie 2.2 van Android bevat Dalvik ook een just-in-time (JIT) compiler die ARM en Thumb-2 machinecode genereert [16]. Boven de bibliotheeklaag draaien het applicatieraamwerk en de applicaties. Het raamwerk bevat enkele diensten en systemen om de applicaties te ondersteunen. Voorbeelden hiervan zijn de Activity Manager, waarmee de levenscyclus van applicaties wordt beheerd, en de Content Provider, die applicaties kunnen gebruiken om gedeelde data zoals contactpersonen kunnen raadplegen of om zelf data te delen.
2.3.2
Verschillende versies van Android
De Linux-kernel die Android gebruikt, wordt sinds enkele maanden niet meer opgenomen in de broncode van Android. De ontwikkelaar kan dus zelf kiezen welke kernel gebruikt wordt. Dit betekende voor mij dat ik zelf moest onderzoeken welke kernel het best gebruikt wordt in deze masterproef. De handleiding van Google stelt versie 2.6 voor [21]. Bij nader onderzoek bleek dat voor de populairste versie van Android, dit is versie 2.3.3, vooral kernel 2.6.37 gebruikt wordt [3, 8, 20]. De aanpassingen aan de Linux-kernel werden lange tijd door Google intern onderhouden, maar de meerderheid van deze aanpassingen worden sinds de introductie van de versie 3.3 van de Linux-kernel terug onderhouden door de ontwikkelaars van de Linuxkernel [1, 24]. Er zijn ook plannen om nog meer aanpassingen toe te voegen aan de kernel [25]. Dit wordt gedaan om het gebruik van meer recentere Linux-kernels aan te moedigen voor de ontwikkeling van Android. Dit betekent wel dat de recentere kernels ook ondersteund moeten worden met de hypervisor om met de ontwikkelingen van Android bij te blijven. Voor deze masterproef werd gekozen om te werken met Android 2.3.3 en versie 2.6.37 van de kernel aangezien die momenteel het meest gebruikt worden [20]. De eerste taak in het ondersteunen van Android met de hypervisor is dus het ondersteunen van Linux-kernel versie 2.6.37.
2.4
De hypervisor
Deze sectie behandelt de staat van de hypervisor bij aanvang van deze masterproef. Eerst zal het type van de hypervisor besproken worden en hoe dit gerealiseerd wordt. Daarna 21
zal uitgelegd worden hoe de dynamische binaire vertaling werkt. De volgende sectie geeft een beknopte uitleg over de aanpak van het geheugenbeheer. Ten slotte wordt de virtuele hardware besproken. Het is belangrijk te weten dat er door verschillende mensen aan de hypervisor gewerkt wordt. Aan het gedeelte over het geheugen wordt bijvoorbeeld gewerkt aan The University of Manchester. Dit wordt hier toch vermeld omdat er problemen waren met het geheugenbeheer die mijn werk vertraagd hebben.
2.4.1
Type 1 met volledige virtualisatie
Zoals besproken in Sectie 2.1 is de hypervisor een type 1 hypervisor die volledige virtualisatie realiseert: type 1 om een zo laag mogelijke virtualisatiekost te hebben en volledige virtualisatie om onafhankelijk te zijn van de mogelijke gastbesturingssystemen. Normaal gezien draait een besturingssysteem in een bevoorrechte modus en draait de gebruikerssoftware in een onbevoorrechte modus. Wanneer de gebruikerstoepassingen de hardware nodig hebben, moet dit gebeuren via het besturingssysteem zodat die volledige controle over de hardware heeft. De hypervisor vormt nu een extra laag software tussen de hardware en het gastbesturingssyteem. Aangezien de hypervisor volledige controle moet hebben over de hardware mag enkel de hypervisor in bevoorrechte modi uitvoeren en moet alle bovenliggende software uitgevoerd worden in de gebruikersmodus. Het gastbesturingssysteem zal echter nog altijd de hardware proberen aansturen. Via gevoelige instructies en geheugentoegangen kan de hardware aangesproken worden. In de volgende sectie wordt het systeem besproken dat gebruikt wordt om deze instructies uit de code te halen zodat de hypervisor de controle over de hardware kan behouden en de correcte werking van het gastbesturingssysteem kan garanderen.
2.4.2
Dynamische binaire vertaling
Zoals besproken in Sectie 2.1.1 kunnen gevoelige instructies de configuratie van de hardware aanpassen, of hangt het gedrag af van de configuratie van de hardware. Aangezien de hardware gevirtualiseerd wordt, moeten deze instructies ook gevirtualiseerd worden. Op het eerste zicht lijkt dit gemakkelijk omdat bevoorrechte instructies een exceptie zullen opwerpen, maar de meerderheid van de gevoelige instructies genereren echter geen exceptie omdat ze niet bevoorrecht zijn en dus moet de hypervisor ingrijpen v´oo´r deze 22
instructies worden uitgevoerd. Dit gebeurt met behulp van dynamische binaire vertaling of dynamic binary translation (DBT).
Figuur 2.10: Basisstappen dynamische binaire vertaling. In Figuur 2.10 zijn de basisstappen van het DBT algoritme voorgesteld. Na het opstarten van de hypervisor zal in de eerste stap het eerste instructieblok van het gastbesturingssysteem gescand worden v´o´or het uitvoeren van de eerste gastinstructies. Een instructieblok eindigt met een gevoelige instructie en begint waar het vorige instructieblok be¨eindigd is. Aangezien spronginstructies gevoelig zijn zullen opeenvolgende instructieblokken elkaar niet altijd direct opvolgen in de code. Iedere instructie wordt met een decoder gedecodeerd, welke aangeeft of een instructie al dan niet gevoelig is. Voor ARM instructies is ieder woord (32 bit), een instructie. Dit maakt het gemakkelijk voor de decoder. Thumb-2 instructies kunnen echter uit zowel een of twee halfwoorden bestaan. Gelukkig kan aan de vorm van het eerste halfwoord gezien worden of een tweede halfwoord volgt of niet. Een gevoelige instructie wordt in de tweede stap van het DBT algoritme vervangen door een supervisor call (SVC) instructie. Dit is een bevoorrechte instructie en zal dus een exceptie opwerpen (zie Sectie 2.1.3). Deze exceptie wordt opgevangen door de hypervisor die de originele instructie dan zal emuleren. ARM instructies hebben allemaal dezelfde breedte van 32 bit. Een gevoelige instructie kan dus gemakkelijk vervangen worden door een SVC instructie. In het geval dat de gevoelige instructie een Thumb-2 instructie is, moeten er extra maatregelen getroffen worden omdat instructies namelijk zowel 16- als 32-bit breed kunnen zijn. Gelukkig zijn in Thumb-2 zowel de SVC als de NOP (No Operation) instructie gecodeerd met 16 bits. In het geval dat de te vervangen instructie een 16-bit instructie is, kan deze vervangen 23
worden door een enkele SVC instructie. In het geval dat de instructie 32 bit breed is, wordt de instructie vervangen door een NOP instructie gevolgd door een SVC instructie. In Hoofdstuk 4 zal blijken dat deze volgorde voor problemen zorgt bij het emuleren van de gevoelige instructie. Om te weten welke instructie op de plaats van de SVC instructie stond, wordt in een blokcache de originele instructie bewaard samen met het begin- en eindadres van het instructieblok. Aan de SVC instructie wordt dan de index meegegeven van het instructieblok in de blokcache. In de cache wordt ook een verwijzing bijgehouden naar de emulatiefunctie van de vervangen instructie. Een instructieblok wordt ge¨ıdentificeerd aan de hand van het beginadres. Wanneer een instructieblok een tweede maal uitgevoerd moet worden, kan het scannen overgeslaan worden aangezien de gevoelige instructie al vervangen is en de emulatiefunctie gekend is. Het is echter mogelijk dat de blokcache vol is waardoor een conflict kan optreden bij het toevoegen van een nieuw instructieblok. De gevoelige instructie van het conflicterende instructieblok wordt dan hersteld om plaats te maken voor het nieuwe blok. Nadat de gevoelige instructie vervangen is door een SVC instructie kan het instructieblok van de gast veilig uitgevoerd worden. De fysieke processormodus wordt veranderd naar de gebruikersmodus en de controle wordt overgedragen aan de gast. Na enkele instructies zal de SVC instructie uitgevoerd worden en een exceptie opwerpen aangezien de processor zich nog in de onbevoorrechte modus bevindt. Nu neemt de hypervisor de controle weer over en zal deze de originele instructie emuleren. Via de code van de SVC instructie weet de hypervisor welke instructie ge¨emuleerd moet worden. Na emulatie zal de hypervisor de programmateller van de volgende instructie terugkrijgen van de emulatiefunctie. Deze programmateller wordt gebruikt als startpunt om een nieuw codeblok te scannen en uit te voeren.
2.4.3
Gevirtualiseerd geheugenbeheer
Het geheugenbeheer moet voor ieder gastbesturingssysteem gevirtualiseerd worden opdat verschillende gastbesturingssystemen tegelijk van het fysiek geheugen gebruik kunnen maken zonder dat het mogelijk is om het geheugen van andere gastbesturingssystemen te lezen of aan te passen. Dit is hetzelfde principe van virtueel geheugen voor processen, maar dan op het niveau van volledige besturingssystemen. Om dit te realiseren moet het bestaande geheugensysteem uitgebreid worden met een extra vertaalstap. Virtuele geheugenadressen worden dan eerst vertaald via de paginatabellen van het gastbesturings24
systeem naar gastadressen. Dit is het fysiek adres volgens het gastbesturingssysteem. Dit adres wordt via de paginatabellen van de hypervisor verder vertaald naar een echte fysieke adres. Er bestaan echter systemen die de extra vertaalstap omzeilen door virtuele adressen van het gastbesturingssysteem rechtstreeks te vertalen naar fysieke adressen. Een systeem dat veel gebruikt wordt is, dat van schaduwpaginatabellen (SPT) [27, 33]. Voor ieder gastbesturingssysteem wordt een schaduwtabel aangemaakt die de structuur van de gastpaginatabellen (GPT) kopieert. De SPT wordt dan gebruikt door de MMU om geheugenadressen te vertalen. Het geheugen waar de GPT zich bevindt, wordt in de SPT beschermd tegen schrijven, zodat een aanpassing door de gast resulteert in een permissiefout. Deze permissiefout wordt opgevangen door de hypervisor zodat wijzigingen aan de GPT ook in de SPT kunnen gebeuren. Een optimalisatie van dit systeem is het gebruik van luie updates. Als een gastbesturingssysteem aanpassingen maakt aan de GPT worden deze niet direct gekopieerd naar de SPT. Het is immers mogelijk dat de virtuele adressen niet gebruikt zullen worden. Als het gastbesturingssysteem een virtueeladres effectief gebruikt voor een lees- of schrijfopdracht zal er vertaalfout opgeworpen worden. De hypervisor zal deze vertaalfout opvangen en de nodige aanpassingen maken aan de SPT. Om vlot te kunnen werken met de verschillende paginatabellen houdt de hypervisor enkele geheugenadressen en structuren bij die informatie bevatten over de paginatabellen. Wanneer het gastbesturingssysteem zijn paginatabellen opstelt, zal een geheugenadres naar het virtueel TTBR register geschreven worden. Dit geheugenadres is volgens het gastbesturingssysteem het fysieke geheugenadres van de GPT. Voor een lees- of schrijfopdracht moeten echter virtuele adressen gebruikt worden. Om aanpassingen te kunnen maken aan de paginatabellen zelf zal de gast dus een sectie moeten toevoegen die de paginatabellen zelf bevat. Dit wordt duidelijk gemaakt in Figuur 2.11. De aangeduide sectieverwijzing in de paginatabel wijst naar een sectie van 1 MB in het fysiek geheugen. Deze 1 MB bevat de paginatabel op het eerste niveau die 16 KB groot is. Wanneer de gast deze sectie toevoegt, zal deze sectie terechtkomen in de SPT en weet de hypervisor ook het virtueel geheugenadres van de GPT. Beide geheugenadressen worden bijgehouden door de hypervisor. De hypervisor houdt ook twee gelinkte lijsten bij die informatie over de paginatabellen op het tweede niveau bijhouden. Dit is nodig omdat de geheugenadressen van paginatabellen op het tweede niveau in de paginatabel op het eerste niveau fysieke geheugenadressen zijn en om aanpassingen te maken zijn virtuele geheugenadressen nodig. 25
Figuur 2.11: Een sectieverwijzing naar de paginatabel. Dit systeem is relatief nieuw en bevat nog (onverwachte) fouten en onderdelen die niet ge¨ımplementeerd zijn. Deze problemen doen zich echter niet voor bij het opstarten van Linux versie 2.6.28 waarvoor dit systeem is ontwikkeld. Voor de versies die in deze masterproef gebruikt worden komen deze fouten wel naar boven waar ik dus oplossingen het moeten voor zoeken. Deze oplossingen worden besproken in hoofdstuk 5.
2.4.4
Gevirtualiseerde hardware
Alle hardware waar een gastbesturingssyteem mee werkt moet, gevirtualiseerd worden. Deze gevirtualiseerde hardware maakt deel uit van de virtuele machine die per gastbesturingssysteem de configuratie van de hardware bijhoudt. Wanneer het besturingsysteem dan een lees- of schrijfopdracht wil uitvoeren naar de hardware zal de hypervisor de controle overnemen en de opdracht uitvoeren met de gevirtualiseerde hardware. 26
Wanneer een gastbesturingssysteem aan het uitvoeren is, wordt wel gewerkt met de fysiek registers R1 tot R15 van de processor. Als de controle overgedragen wordt aan de hypervisor door een exceptie worden de waarden van de registers opgeslagen in de VM en kan de hypervisor het nodige werk uitvoeren om de exceptie af te handelen. Voordat de controle terug naar het gastbesturingssyteem gaat, worden de registerwaarden hersteld. De hi¨erarchische structuur van de hardware, zoals uitgelegd in Sectie 2.2.6, wordt ook in de hypervisor gebruikt. Een lees- of schrijfoperatie wordt eerst uitgevoerd op het hoogste niveau, die verantwoordelijk is voor de gehele geheugenruimte van 4 GB. Daarna wordt gekeken tot welk kwartaal het adres behoort. Recursief wordt dan naar de module gezocht die verantwoordelijk is voor het gebruikte geheugenadres. Op die manier moeten enkel die modules ge¨ımplementeerd worden die nodig zijn voor het opstarten van het gebruikte gastbesturingssysteem. Het is belangrijk om te weten dat het fysiek adres gebruikt moet worden om het juiste apparaat te vinden. De hypervisor werd ontwikkeld voor Linux 2.6.28.1 met een minimale configuratie. Zo zijn er weinig drivers gecompileerd, is er geen energiebeheer aanwezig en is er geen ondersteuning voor netwerkverbindingen. Bovendien is de verzameling gebruikerssoftware die gebruikt werd om het succesvol opstarten van de kernel te testen is zeer beperkt. Door deze beperkte configuratie is er nog niet veel hardware gevirtualiseerd. Zoals vermeld in Sectie 2.3 maakt Android gebruik van de Linux-kernel, versie 2.6.37 of hoger. Tussen versie 2.6.28.1 en 2.6.37 is er echter heel wat ondersteuning bijgekomen voor de OMAP SoC familie [28]. Dit komt omdat de verschillende chips een gelijkaardige structuur hebben, wat het ondersteunen van meerdere hardwareplatformen uiteraard ten goede komt. Door deze beter ondersteuning wordt meer hardware van de OMAP SoC gebruikt die dus ook ge¨ımplementeerd moet worden.
2.5
Besluit
Uit de voorgaande secties blijkt dat er voor het ondersteunen van Android in de hypervisor nog heel wat werk nodig is in de verschillende delen van het project. Eerst en vooral is door de grondig verbeterde ondersteuning van de OMAP SoC familie in de Linuxkernel heel wat werk nodig om deze hardware te virtualiseren. Ten tweede is het intieel gevirtualiseerd geheugenbeheer niet voldoende om besturingssystemen anders dan Linux 2.6.28 te ondersteunen. Aangezien het geheugenbeheer een essentieel onderdeel is van besturingssystemen is dit ook een heel belangrijk onderdeel dat aangepakt moet worden. 27
Tot slot is de ondersteuning voor de Thumb-2 instructieset heel belangrijk aangezien de Dalvik JIT compiler van Android hier gebruik van maakt. Naast deze problemen zijn tijdens deze masterproef nog andere problemen voorgekomen die mijn werk vertraagd hebben. Deze problemen worden hier niet vermeld aangezien die opgelost werden door andere mensen die ook aan de hypervisor werken. Door het vele werk dat nog moet gebeuren en het feit dat de nodige aanpassingen voorkomen in bijna alle plaatsen van de hypervisor was het in de tijdspanne van deze masterproef niet mogelijk om Android volledig te ondersteunen in de hypervisor. Er is wel een grote voortuigang geboekt ten opzichte van de initi¨ele hypervisor, wat het verder ontwikkelen van de ondersteuning alleen maar ten goede zal komen. In de volgende hoofdstukken worden de problemen en aanpassingen die er gemaakt zijn in dit werk in detail besproken.
28
Hoofdstuk 3 Unittest functionaliteit In dit hoofdstuk wordt kort de unittest functionalteit besproken. Deze functionaliteit wordt in de volgende hoofdstukken gebruikt om de aangepaste onderdelen te testen. Omdat voor het testen van kleine onderdelen, zoals de werking van ´e´en bepaalde emulatiefunctie, het opstarten van een volledig besturingssysteem te lang duurt of soms onvoorspelbare resultaten geeft, is er nood aan een betere testmethode. Er is dan gekozen om ondersteuning voor unittesten in te bouwen in de hypervisor om op die manier bepaalde onderdelen snel en los van elkaar te kunnen testen. De verschillende unittesten kunnen na verloop van tijd opnieuw uitgevoerd worden om na te gaan of aanpassingen aan ´e´en onderdeel de werking van een ander onderdeel niet geschaad hebben.
3.1
Gastbesturingssysteem
De initi¨ele hypervisor had reeds ondersteuning voor twee verschillende types besturingssystemen: Linux en FreeRTOS. De toevoeging van een derde type besturingssystemen, namelijk het unittest-type, was voldoende om ook unittesten te laten opstarten. Een unittest bestaat uit twee onderdelen: een header die metadata over de test bevat, en de eigenlijke test. De metadata bevat het fysiek laadadres (waar de test in het geheugen geplaatst moet worden), het fysiek beginadres (waar de eerste instructie van de test staat) en de naam van de test. Het laad- en beginadres zijn belangrijk voor de testen in verband met het gevirtualiseerd geheugenbeheersysteem omdat de plaats in het geheugen een belangrijke rol kan spelen voor het testen van randgevallen. Het beginadres wordt ook gebruikt om aan te geven of een test gestart moet worden met de processor in ARM of Thumb-2 modus. Dit gebeurt op dezelfde manier waarop een interworking sprong gebeurt. Dit is een sprong die de uitvoeringsmodus van de processor kan veranderen. De wissel wordt aangegeven door de minst significante bit van het sprongadres. Staat deze bit op 1 dan wordt er gesprongen naar Thumb-2 code, anders 29
wordt er gesprongen naar ARM code. Door in het beginadres van een unittest de minst significante bit op 1 te zetten, zal de test in Thumb-2 modus gestart worden, anders wordt die gestart in ARM modus.
3.2
Uitbreidbaarheid
Een unittest voert allerlei operaties uit en test verschillende onderdelen van de hypervisor. Op het einde van de test worden verschillende voorwaarden nagekeken om te zien of deze onderdelen het gewenste gedrag vertonen. Het uiteindelijk resultaat van een test wordt op het einde van de test via de waarde van een softwarematig breekpunt gecommuniceerd met de hypervisor. Een breakpoint (BKPT) instructie is een gevoelige instructie en heeft dus een bijhorende emulatiefunctie. Na een breekpunt wordt de test onmiddellijk gestopt en wordt het resultaat getoond. Momenteel wordt er een onderscheid gemaakt tussen twee gevallen: succes in het geval dat het breekpunt de waarde nul meekrijgt, alle andere gevallen worden gezien als falen. Dit is gemakkelijk uitbreidbaar. Zo kunnen er meerdere gevallen onderscheiden worden door in de emulatiefunctie van de BKPT instructie extra waarden toe te voegen. Er kan, bijvoorbeeld, ook gekozen worden om de test niet onmiddellijk af te breken bij een succes maar enkel na falen. Er kunnen dan in ´e´en unittest verschillende voorwaarden getest worden. De header heeft ook nog een veld dat voorlopig niet gebruikt wordt. Hier kan extra metadata aan toegevoegd worden om eventueel extra functionaliteit of informatie aan de testen toe te voegen.
30
Hoofdstuk 4 Thumb-2 ondersteuning In hoofdstuk 2 werd reeds vermeld dat de ondersteuning van de Thumb-2 instructieset problemen vertoont in de hypervisor. Dit hoofdstuk haalt deze problemen aan en bespreekt hoe ik ze opgelost heb. Aan het einde van dit hoofdstuk wordt aangetoond hoe deze aanpassingen getest werden met behulp van unittesten.
4.1
Voorwaardelijke uitvoering
Een belangrijk verschil tussen Thumb-2 en ARM is de manier waarop instructies voorwaardelijk gemaakt kunnen worden. Instructies kunnen op zich niet voorwaardelijk gemaakt worden omdat de conditiecode niet meer gecodeerd is in de instructie. Met behulp van de IT instructie kan er wel een conditiecode ingesteld worden voor de volgende ´e´en tot vier instructies.
4.1.1
Probleem met initi¨ ele DBT algoritme
De initi¨ele implementatie van het DBT algoritme houdt geen rekening met de IT instructie. Zoals te zien is in voorbeeld 4.1 kunnen daardoor fouten ontstaan. In dit voorbeeld wordt conditievlag Z (zero) ingesteld door de eerste instructie aangezien 1 6= 0. De volgende instructie is de If-Then instructie en stelt de conditiecode op voor de daarop volgende instructies. Voor de eerste instructie is dit EQ (Equal), voor de tweede is dit de tegengestelde conditiecode NE. Dit wil zeggen dat in dit voorbeeld de MRS instructie niet uitgevoerd moet worden maar de daarop volgende spronginstructie B wel. De MRS instructie slaat de waarde van het APSR register op in een gewoon register. Aangezien de MRS instructie een gevoelige instructie is, wordt de MRS instructie als gevoelig beschouwd en moet ze vervangen worden door een supervisor call. Ook de spronginstructie is een gevoelige instructie en zal uiteindelijk vervangen moeten worden. 31
MOVS ITE MRS B
R0 , #1 EQ R0 , APSR L1
MOVS ITE SVC B
(a) Originele instructies
R0 , #1 EQ #0 x50 L1
(b) Vertaalde instructies
Figuur 4.1: Foute vertaling door de initi¨ele implementatie DBT. Als het initi¨ele DBT algoritme uitgevoerd wordt op deze instructies wordt de eerste gevoelige instructie, MRS, vervangen. Bij de uitvoering van dit instructieblok zal de bijhorende SVC instructie echter nooit uitgevoerd worden aangezien de conditiecode en conditievlaggen niet overeenstemmen op het moment dat de processor zich bij deze instructie bevindt. Als gevolg zal de spronginstructie uitgevoerd worden en is de hypervisor de controle over de gast kwijt.
4.1.2
Aanpassingen DBT algoritme
De oplossing voor dit probleem bestaat uit twee delen. Eerst moet de IT instructie ge¨emuleerd worden om ervoor te zorgen dat een instructieblok correct bepaald kan worden. Ten tweede moet het ITSTATE veld bijgehouden en gecontroleerd worden in de scanner om eventueel gevoelige instructies over te slaan.
Emulatie IT instructie Het eerste deel van de oplossing bestaat er in de IT instructie te emuleren. De IT instructie wordt nu ook herkend als gevoelige instructie en zal dus vervangen worden door een supervisor call. Wanneer deze dan een exceptie opwerpt, zal de IT instructie als volgt ge¨emuleerd worden. Eerst wordt de ITSTATE en de basisconditiecode uit de instructie gehaald. Met deze twee elementen wordt vervolgens per instructie die volgt op de IT instructie ge¨evalueerd of ze al dan niet uitgevoerd zal worden. Per instructie wordt ook het ITSTATE veld bijgewerkt volgens het algoritme uit Sectie 2.2.4 voor de pseudocode van deze functie. Deze berekening stopt wanneer de eerste instructie gevonden wordt die effectief uitgevoerd zal worden of op het einde van het IT blok. Gevoelige instructies die niet worden uitgevoerd, worden op deze manier overgeslaan aangezien ze niet moeten vervangen worden. Daarna worden de ITSTATE velden van het CPSR register ge¨ updated met de nieuwe waarden. Als laatste stap wordt de programmateller teruggegeven van de 32
MOVS ITE MRS B
R0 , #1 EQ R0 , APSR L1
MOVS ITE MRS SVC
(a) Originele instructies
R0 , #1 EQ R0 , APSR #0 x50
(b) Correcte vertaling
Figuur 4.2: Correcte vertaling door de aangepaste implementatie DBT. eerste instructie die effectief uitgevoerd zal worden. Dit kan dus zowel een instructie van binnenin het IT blok zijn of erna. In voorbeeld 4.2 wordt dit toegepast op dezelfde code als in het voorbeeld 4.1 en wordt niet de MRS instructie maar wel de B instructie vervangen. Bij het uitvoeren van de resulterende code zal de MRS instructie overgeslaan worden waarna de SVC instructie wel uitgevoerd zal worden. De hypervisor zal in dit geval de controle over het gastbesturingssysteem dus niet verliezen.
Aanpassingen aan de instructiescanner Er zijn uiteraard meerdere volgordes mogelijk waarin gevoelige en ongevoelige instructies voorkomen in een IT blok en ook de If en Then kunnen in alle mogelijke volgordes voorkomen. De voorgaande aanpassingen veronderstellen dat de eerste instructies die volgen op een IT instructie niet uitgevoerd zullen worden en de instructies die daarop volgen wel. Dit is slechts ´e´en van de vele mogelijke gevallen. In Figuur 4.3 wordt Thumb-2 code getoond die nog altijd een foute vertaling zal opleveren. Let er op dat de basisconditie nu NE is, waardoor de eerste instructie na de IT uitgevoerd zal worden. Door de aanpassingen uit de vorige sectie wordt eerst de IT instructie vervangen. Bij het emuleren van de instructie zal gezien worden dat de MRS instructie uitgevoerd zal worden en zal dus de eerste instructie van een nieuw instructieblok zijn. In de scanner wordt de instructie gedecodeerd als gevoelig en zal ook vervangen worden. Na emulatie wordt de B instructie gebruikt als startpunt voor opnieuw een nieuw instructieblok. Ook deze instructie wordt als gevoelig gedecodeerd in de scanner en zal vervangen worden. Dit is echter incorrect omdat de spronginstructie deel uitmaakt van het IT blok en niet uitgevoerd zal worden. Het is dus nodig om tijdens het scannen van Thumb-2 instructies ook rekening te houden met de uitvoeringstoestand van de IT instructie. 33
MOVS ITE MRS B
R0 , #1 NE R0 , APSR L1
1 2 3
MOVS SVC SVC SVC
R0 , #1 #0 xBE #0 x50 #0 xAD
Figuur 4.3: Instructiesequentie die nog altijd fout vertaald zal worden.
Figuur 4.4: Aangepaste Thumb-2 instructiescanner.
Voordat instructies gescand worden moet het ITSTATE veld dat geldig is aan het begin van een instructieblok uit het CPSR register gehaald worden. Daarna kan de aangepaste instructiescanner uitgevoerd worden. Deze volgt het schema zoals te zien is in Figuur 4.4, dit is een uitvergroting van het “Scan blok”-blok uit Figuur 2.10. Zoals in de initi¨ele scanner wordt er eerst op zoek gegaan naar gevoelige instructies. Na iedere gescande instructie wordt het ITSTATE veld bijgewerkt, maar wordt nu niet teruggeschreven naar het CPSR register omdat de uitvoering begint bij de eerste instructie van het instructieblok waar de initi¨ele ITSTATE geldig is. Wanneer een gevoelige instructie ontdekt wordt, wordt nagegaan als de gescande instructie zich in een IT blok bevindt. Dit kan gemakkelijk door te kijken naar de laatse vier bits van het ITSTATE veld. Als dit niet het geval is, wordt onmiddellijk overgegaan naar de volgende stap en zal de instructie vervangen worden. Als de instructie zich wel in een IT blok bevindt, wordt nagegaan of de instructie effectief uitgevoerd zal worden. Zo ja, dan wordt ze vervangen, zo niet, wordt ze behandeld als een ongevoelige instructie en zal er verder gescand worden. Het is uiteraard mogelijk dat de gevoelige instructie in een later stadium, als de conditievlaggen anders ingesteld zijn, alsnog uitgevoerd zal worden. Daarvoor worden de instructies echter opnieuw gescand en zou dit dus geen probleem mogen opleveren. 34
4.2
Overige aanpassingen
Bij het zoeken naar oplossingen voor de problemen omtrent de voorwaardelijke uitvoering van de Thumb-2 instructieset zijn nog andere problemen opgedoken die een goede ondersteuning van de Thumb-2 instructieset belemmerden. Deze problemen werden niet zichtbaar gemaakt door de unittesten wat het debuggen ervan moeilijk maakte. Ondanks dat de problemen niet zo groot waren, heeft het dus toch wat tijd gekost om ze te vinden en op te lossen waardoor ze hier vermeld worden. In wat volgt is een opsomming van de bijkomende problemen en oplossingen om de ondersteuning van de Thumb-2 instructieset te verbeteren. Aanvankelijk leken de aanpassingen uit Sectie 4.1.2 goed te werken, maar na grondig testen bleek het in bepaalde gevallen toch fout te lopen. Dit was het gevolg van het niet goed opslaan en herstellen van de hardwaretoestand wanneer het gastbesturingssysteem een exceptie veroorzaakte. In de code van voor de contextwissel waren namelijk onvoorspelbare instructies geslopen die de waarde van en naar het CPSR register niet correct kopieerden. Een onvoorspelbare instructie wordt UNPREDICTABLE genoemd in de ARM ARM [14] en heeft zoals de naam zegt een onvoorspelbaar gedrag. Door deze instructies werd onder andere het ITSTATE veld niet gekopieerd en werd de uitvoeringstoestand van de IT instructie niet behouden. Na een contextwissel waren de Thumb-2 instructies die voorwaardelijk waren gemaakt werden door een IT instructie terug onvoorwaardelijk. Door de onvoorspelbare instructies aan te passen was dit probleem opgelost. Zoals vermeld in het vorige hoofdstuk werden 32-bit Thumb-2 instructies vervangen door twee 16-bit instructies: eerst een NOP instructie gevolgd door de SVC instructie. Deze volgorde zorgt echter voor twee problemen: ten eerste worden er voor iedere gevoelige 32-bit instructie twee instructies uitgevoerd. Als deze gevoelige instructie zich in een IT blok bevindt, komt er dus een extra instructie bij in het IT blok. De ITSTATE wordt dan verkeerd aangepast zodat het IT blok te vroeg eindigt, waardoor de laatste instructies niet meer voorwaardelijk zijn. Ten tweede is de programmateller van de ge¨emuleerde instructie niet gelijk aan die van de originele instructie. Dit zorgt onder andere voor problemen met programmateller-afhankelijke 32-bit spronginstructies. De programmateller op het moment van de supervisor call is dan gelijk aan die van de originele spronginstructie. Op zijn beurt zorgde de omwisseling van NOP en SVC dan weer voor problemen met de blokcache. Wanneer er namelijk een conflict optreedt in de cache moeten de SVC instructies terug vervangen worden door de originele instructies om plaats te maken voor een nieuw instructieblok in de cache. Hier moest dus ook rekening gehouden worden met 35
de omwisseling van de NOP en SVC instructie. Aangezien met kleine unittesten weinig tot geen conflicten voorkwamen, was dit probleem heel moeilijk te lokaliseren. In de emulatiefuncties van de verschillende spronginstructies werden ook heel wat fouten weggewerkt. Zo waren er fouten omtrent de berekening van de offset waardoor een grote negatieve offset soms omgezet werd in een positieve offset, of werd de gecodeerde conditiecode niet correct uit de instructie gehaald. Ook dit probleem werd niet zichtbaar door het gebruik van de unittesten aangezien deze te klein waren om een spronginstructie te bevatten met een voldoende grote negatieve offset. Een ander probleem met spronginstructies deed zich voor bij de interworking branches waarbij niet nagekeken werd of een verandering van instructieset moest gebeuren. Het is ook mogelijk dat na het afhandelen een exceptie veranderd moet worden van instructieset, bijvoorbeeld omdat de exceptie optrad in Thumb-2 code en de afhandeling ervan gebeurt in ARM code. Als dit voorkomt, moet de programmateller op de juiste manier uitgelijnd worden, afhankelijk van de instructieset waar naartoe gesprongen wordt, alvoorens de sprong uit te voeren. De instructieset wordt bepaald door de Thumb bit in het CPSR register. Voor beide vormen van interworking branches is er nu ondersteuning gekomen in de hypervisor. Een laatste toevoeging is de ondersteuning voor afhandelfuncties voor excepties geschreven in Thumb-2 code. Standaard worden opgeworpen excepties afgehandeld in ARM instructieset, zelf al wordt deze exceptie opgeworpen vanuit Thumb-2 instructieset. Een bit in het systeemcontroleregister (SCTLR) kan echter ingesteld worden die aangeeft in welke instructieset de afhandelfuncties geschreven zijn. Deze bit wordt nu nagekeken door de hypervisor voor er naar de afhandelfunctie van het gastbesturingssysteem gesprongen wordt om zo de juiste instructieset in te stellen.
4.3
Resultaten
De ondersteuning voor de Thumb-2 instructieset werd getest met behulp van unittests. Een unittest die gebruikt kan worden om de voorwaardelijke uitvoering van Thumb-2 instructies te testen kan gevonden worden in bijlage B. Met deze test kan aangetoond worden dat de voorwaardelijke instructies inderdaad correct gevirtualiseerd worden. De Thumb-2 ondersteuning werd ook getest met behulp van het FreeRTOS besturingssysteem. De output van FreeRTOS, geconfigureerd voor Thumb-2, werd dan vergeleken met de versie geconfigureerd voor ARM wanneer deze opgestart werden met de hypervisor. 36
4.4
Besluit
Door de verbeterde ondersteuning voor de Thumb-2 instructieset is de virtualisatie van de ARM architectuur completer geworden. Met behulp van de unittesten is de ondersteuning getest, maar zoals is besproken geeft dit geen garantie dat er geen problemen meer zijn met de Thumb-2 ondersteuning. Het zorgt wel voor een goede basis voor de ondersteuning van besturingssystemen die van deze instructieset gebruik maken, zoals Android.
37
Hoofdstuk 5 Gevirtualiseerd geheugenbeheer Bij aanvang van deze masterproef was de implementatie van het geheugenbeheer ontoereikend voor de verdere ontwikkeling van de hypervisor. Voorlopig volstond deze implementatie wel om ongecomprimeerde Linux-kernels op te starten. De implementatie werd volledig herzien aan The University of Manchester en tegen februari 2012 waren de fundamentele problemen met het systeem verholpen. De werking van deze implementatie werd behandeld in Sectie 2.4.3. Dit nieuw gevirtualiseerd geheugenbeheer was voorlopig enkel ontwikkeld met Linux 2.6.28 waardoor er delen van het systeem niet ge¨ımplementeerd waren of niet genoeg getest waren. Om het doel van deze masterproef te bereiken was het nodig sommige van deze delen te implementeren of aan te passen om Linux 2.6.37 op te starten. Aangezien de ontwikkeling van het gevirtualiseerd geheugenbeheer voornamelijk de focus is in Manchester gebeurt heb ik niet altijd een volledige oplossing ge¨ımplementeerd. Het werk uit dit hoofdstuk dient wel als basis voor de verdere ontwikkeling van het geheugenbeheer. In de volgende sectie wordt eerst uitleg gegeven over verschillende oplossingsmethoden waarna de problemen die tegengekomen werden met de bijhorende oplossingen worden besproken.
5.1
Oplossingsmethoden en debuggen
Om verschillende redenen is het detecteren van de oorzaak van problemen in verband met het geheugenbeheer niet altijd even evident. Een eerste reden is dat het uitvoeringspad bij het opstarten van Linux niet deterministisch wanneer de onderbrekingen aan staan en dan kan de plaats van een crash afhangen van de hoeveelheid debuginformatie die getoond wordt. Het tonen van debuginformatie zorgt immers voor een vertraging waardoor (tijdsafhankelijke) fouten niet direct zichtbaar worden. Deze vertraging is ook problematisch wanneer een probleem zich pas laat in het op38
startproces manifesteert. Om een goed beeld te krijgen van het probleem moet immers veel debuginformatie getoond worden, maar dit zorgt er wel voor dat het opstarten van Linux enkele minuten kan duren. Als er dan verschillende oplossingen geprobeerd moeten worden, kan dit dus veel tijd in beslag nemen. Een laatse reden is in het geval van een recursieve datafout, dit is een datafout die tijdens het afhandelen opnieuw een datafout opwerpt, wat er voor kan zorgen dat de hypervisor in een oneindige lus van datafouten terechtkomt. Met OpenOCD kan de processor gestopt worden en kan er gekeken worden wat het geheugenadres is die de laatste datafout heeft opgeworpen, maar het is niet onmiddellijk duidelijk wat het geheugenadres van de eerste datafout is. Dit probleem komt bijvoorbeeld voor bij een foute aanpassing aan de schaduwpaginatabellen. In een corrupte paginatabel kan de ´e´en-op-´e´en afbeelding van het geheugen van de hypervisor incorrect zijn of ontbreken. Onder andere de geheugenadressen van de stapels zijn dan niet meer bereikbaar vanuit de hypervisor, wat recursieve datafouten veroorzaakt. Bij het afhandelen van een datafout moet immers op de stapel geschreven worden, wat opnieuw een datafout zal genereren. De corrupte paginatabel kan dan ook niet meer rechtstreeks uitgelezen worden met OpenOCD omdat de geheugenadressen die verwijzen naar deze tabel ook niet meer correct vertaald worden. Daarom werd door mijn begeleider een functie geschreven die opgeroepen kan worden vanuit OpenOCD door eerst de processor te stoppen en rechtstreeks naar het corresponderende fysiek adres van deze functie te springen. Deze functie legt de onderbrekingen af, wijzigt de uitvoeringsmodus naar de SVC modus en schakelt de MMU uit zodat er geen foute vertalingen zouden gebeuren bij het weergeven van de corrupte paginatabel. Om de vertraging, veroorzaakt door het tonen van debuginformatie zo veel mogelijk te vermijden, werd gebruik gemaakt van de instructieblokteller om de informatie pas te tonen wanneer een vooraf bepaalde drempelwaarde overschreden werd. De instructieblokteller is een globale variable die bijhoudt hoeveel instructieblokken gescand werden. Aangezien de teller gedefinieerd wordt als een globale variable kan deze met OpenOCD rechtstreeks uitgelezen worden. Om een geschikte waarde voor de teller te bepalen wordt de hypervisor eerst opgestart zonder dat deze debuginformatie toont. Wanneer er dan een probleem optreedt kan de teller uitgelezen worden. Een geschikte drempelwaarde is de gevonden tellerwaarde verminderd met enkele instructieblokken. Op die manier wordt enkel debuginformatie getoond voor de laatste instructieblokken wat het opstarten van Linux minder zal vertragen. 39
Het probleem van de recursieve datafout kan deels ook opgelost worden door het gebruik van de instructieblokteller. Wanneer een oneindige lus ontdekt wordt, als gevolg van een datafout, wordt de teller uitgelezen. De hypervisor wordt dan aangepast om te stoppen wanneer de eerste datafout optreedt nadat de instructieblokteller een drempelwaarde overschrijdt. De drempelwaarde is de gevonden tellerwaarde opnieuw verminderd met enkele instructieblokken. Door het gebruik van de instructieblokteller wordt de zoektocht naar de oorzaak van een probleem gemakkelijker gemaakt. Het is echter niet evident om een correcte drempelwaarde te vinden. De functies om (corrupte) paginatabellen te tonen zijn ook een handig hulpmiddel, maar aangezien paginatabellen soms heel groot kunnen worden is het moeilijk om de verwijzing te vinden die voor de foute vertaling zorgt. Nadat de oorzaak van een bepaald probleem gevonden is moet er nog een oplossing gevonden worden.
5.2
Aanpassingen
Nu de oplossingsmethoden en de moeilijkheid van debuggen aangehaald zijn worden de verschillende problemen en oplossingen doorgenomen. In de laatste sectie worden zoals in het vorige hoofdstuk enkele kleinere problemen en oplossingen aangehaald.
5.2.1
Geheugenadres van de gastpaginatabel
In Sectie 2.4.3 werd al aangehaald dat de hypervisor per gast twee geheugenadressen bijhoudt die wijzen naar de paginatabel op het eerste niveau van de gast. Het ene adres is het adres dat het gastbesturingssysteem opgeeft wanneer het zijn paginatabellen opstelt. Dit adres bevindt zich in het virtueel TTBR register van de gast. Het ander adres is het virtueel adres van de gastpaginatabel (GPT) die de hypervisor te weten komt wanneer de gast een sectie toevoegt aan de GPT die de GPT zelf bevat. Wanneer dit virtueel adres echter nog niet gekend is en er moeten aanpassingen gemaakt worden aan de paginatabellen maakt de hypervisor zelf een tijdelijke sectieverwijzing aan in de schaduwpaginatabel die de paginatabel van de gast bevat. Deze sectieverwijzing wordt op een dergelijke manier aangemaakt dat een ´e´en-op-´e´en afbeelding bestaat tussen de fysieke en virtuele adressen. Het virtueel geheugenadres is dan gelijk aan het fysiek geheugenadres van de gastpaginatabel. Nadat de nodige aanpassingen doorgevoerd zijn wordt deze sectieverwijzing weer verwijderd. 40
Figuur 5.1: Tijdelijke sectie in de schaduwpaginatabel.
Een voorbeeld wordt weergegeven in Figuur 5.1. De nieuwe sectieverwijzing is aangeduid en is verantwoordelijk voor 1 MB geheugen. In deze sectie bevindt zich de gastpaginatabel (GPT). Aangezien de vertaling van het adres in het TTBR register van de gast het adres zelf is kan de GPT nu gelezen worden.
Het is echter mogelijk dat er al een geldige verwijzing staat op de plaats waar de tijdelijke sectieverwijzing zal komen. Daarom wordt een back-up genomen van deze verwijzing die terug geplaatst zal worden wanneer de sectieverwijzing niet meer nodig is.
Het probleem was dat het toevoegen van de tijdelijke sectieverwijzing gebeurde met een functie die eerst nagaat of het wel mogelijk is om een sectie toe te voegen op die plaats in de paginatabel. Dit is echter niet nodig omdat er een back-up is van de originele verwijzing. Door de sectieverwijzing de originele te laten overschrijven kan dit probleem worden opgelost. 41
5.2.2
Probleem met invalideren
Zoals beschreven in Sectie 2.4.3 houdt de hypervisor een gelinkte lijst bij met informatie over paginatabellen op het tweede niveau. Wanneer het gastbesturingssysteem de MMU aanschakelt moeten structuren in deze lijst ge¨ınvalideerd worden omdat volledig nieuwe afbeeldingen aangemaakt zullen worden. Dit invalideren veroorzaakte echter een crash bij het verder opstarten van Linux omdat, volgens de hypervisor, de informatie over een paginatabel op het tweede niveau niet beschikbaar was. Dit wees op een probleem met het invalideren omdat ofwel de informatie onterecht verwijderd was ofwel de bijhorende verwijzing naar de paginatabel op het tweede niveau niet correct verwijderd was. Een oplossing die geprobeerd werd was om tijdens het invalideren van de informatiestructuren ook de bijhorende verwijzingen te invalideren, en er dus lege verwijzingen van te maken. Dit zorgde dat er te veel verwijzingen werden verwijderd waardoor een oneindige lus van recursieve datafouten optrad. Een andere oplossing die geprobeerd werd, was om enkel de problematische verwijzing te verwijderen uit de paginatabel, maar dit zorgde ook voor een oneindige lus van recursieve datafoutens. Het bleek echter mogelijk om dit invalideren niet te doen. Dit zorgde ervoor dat Linux verder kon opstarten waarbij voorlopig geen problemen meer optraden in verband met het geheugen.
5.2.3
Overige aanpassingen
Het eerste probleem was dat er nog geen ondersteuning was voor het geval dat het gastbesturingssysteem een kleine pagina toevoegt aan zijn paginatabellen. Deze kleine pagina moet ook in de schaduwpaginatabel toegevoegd worden wat niet gebeurde. Een volgend probleem deed zich voor bij het toevoegen van een verwijzing naar een paginatabel op het tweede niveau. Wanneer het geheugen voor deze tabel gealloceerd wordt, wordt het virtueel geheugenadres teruggegeven. In de paginatabel op het eerste niveau moet echter fysiek geheugenadres komen van de paginatabel op het tweede niveau. Als de MMU nog niet is aangeschakeld, is dit gelijk aan het virtueel adres. Is de MMU wel aangeschakeld dan moet het virtueel adres vertaald worden aan de hand van de schaduwtabellen. Het probleem was dat er werd nagegaan of de fysieke MMU aan lag of niet, wat incorrect is aangezien de staat van de fysieke MMU niet overeen komt met de staat van virtuele MMU. Dit werd gecorrigeerd en er wordt nu dus nagegaan of de virtuele MMU aanligt of niet. 42
Een laatste fout die aangepast werd, is de uitlijning van de paginatabellen op het eerste niveau. De ARM architectuur vereist dat een paginatabel op het eerste niveau uigelijnd is op 214−N bytes [14]. De waarde voor N is gespecifieerd in het Translation Table Base Control register (TTBCR) en kan waarden van 0 tot en met 7 aannemen. De standaardwaarde is 0 en wordt gebruikt door de hypervisor. Het is ook de enige waarde die ondersteund wordt. Bij het alloceren van een paginatabel gebeurde dit door de hypervisor echter uitgelijnd op 215 bytes. Dit zorgt niet onmiddellijk voor problemen bij het aanmaken van nieuwe paginatabel aangezien een uitlijning op 215 bytes automatisch ook een uitlijning is op 214 bytes. Het kan wel voor problemen zorgen wanneer nagegaan wordt als een paginatabel van het gastbesturingssysteem correct uitgelijnd is. Dit werd dan ook aangepast zodat correct uitgelijnde paginatabellen niet voor problemen kunnen zorgen.
5.3
Besluit
Door het werk verricht in dit hoofdstuk zijn er enkele problemen in verband met het geheugenbeheer aan het licht gekomen. Een deel van deze problemen zijn opgelost om de werking van de hypervisor te verbeteren. Aangezien het doel van deze masterproef niet was om het gevirtualiseerd geheugenbeheer volledig te implementeren zijn er enkele problemen niet volledig opgelost. Deze problemen zijn nu wel bekend waardoor deze problemen nu opgelost kunnen worden aan The University of Manchester.
43
Hoofdstuk 6 Gevirtualiseerde hardware Linux 2.6.37 ondersteunt, in vergelijking met Linux 2.6.28, meer hardware van de OMAP SoC familie. Omdat deze hardware tijdens het opstarten van Linux ge¨ınitialiseerd wordt, moet deze hardware gevirtualiseerd worden door de hypervisor. In dit hoofdstuk komen de verschillende hardwaredomeinen aan bod waar veranderingen zijn aangebracht om Linux 2.6.37 te laten opstarten. Eerst wordt de gebruikte oplossingsmethode besproken. Daarna wordt uitleg gegeven over de hardware die instaat voor het energiebeheer. De daar op volgende sectie bespreekt enkele modules die verantwoordelijk zijn voor het beveiligingsmechanisme. Daarna wordt een ongeldige module besproken die ge¨ımplementeerd moest worden. Als laatste worden nog enkele kleinere aanpassingen besproken en volgt het besluit.
6.1
Oplossingsmethoden
Omdat het praktisch niet haalbaar is om voor alle hardware onmiddellijk een volledige emulatielaag te implementeren, werd de volgende werkwijze gebruikt. Eerst wordt Linux opgestart met de hypervisor. Deze zal na enkele seconden stoppen omdat een lees- of schrijfopdracht een (fysiek) geheugenadres gebruikt waarvoor de bijhorende hardware nog niet is gevirtualiseerd. Met het fysiek adres wordt dan nagekeken in de handleiding van de OMAP3530 SoC welke hardware voor dit adres verantwoordelijk is [34]. Deze hardware wordt, waar mogelijk, dan gevirtualiseerd in de hypervisor. Deze aanpak werkte goed tot het moment dat Linux geheugenadressen gebruikte die volgens de handleiding ofwel gereserveerd ofwel ongeldig waren [34]. Dit heeft enerzijds te maken met het feit dat tussen de verschillende revisies van de handleiding beschrijvingen van registers en soms volledige modules werden toegevoegd of verwijderd. Aan de andere kant wordt soms te veel ervan uitgegaan dat alle OMAP SoCs dezelfde structuur hebben waardoor er een opportunistische implementatie bestaat in het Linux besturingssysteem. 44
Zonder de hypervisor kan het gebruikte Linux besturingssyteem echter wel opstarten op de OMAP SoC dus was het nodig om een oplossing te zoeken voor deze ongeldige geheugentoegangen. Daarom werd gekeken naar het gedrag van een lees- of schrijfopdracht naar de fysieke hardware met deze geheugenadressen: in de meeste gevallen wordt bij een leesopdracht gewoon de waarde nul teruggegeven en wordt bij een schrijfopdracht de waarde die geschreven moet worden genegeerd door de hardware. Dit werd ook zo ge¨ımplementeerd in de hypervisor. Het was ook regelmatig nodig om de broncode van de Linux-kernel te doorzoeken om te weten waar bepaalde geheugenadressen vandaan kwamen of om af te leiden wat er precies gebeurt met een uitgelezen waarde. Dit was vooral nodig bij het virtualiseren van registers en modules die niet in de handleiding staan. De virtuele hardware kan dan toch het gedrag vertonen dat Linux verwacht. Het doorzoeken van de broncode kan met programma’s zoals grep maar ook met Linux Cross Referencer (LXR) [5]. Dit is een webapplicatie om de broncode te doorzoeken waarbij gemakkelijk kan doorgeklikt worden op namen van functies en variabelen. Om Linux te laten opstarten is het echter niet nodig dat alle virtuele hardware effectief werkt omdat deze bijvoorbeeld enkel ge¨ınitialiseerd of uitgeschakeld wordt. Om geen tijd te verliezen met het implementeren van modules die toch niet gebruikt worden, werd ervoor gekozen om deze modules niet volledig te virtualiseren in de hypervisor. Enkel de registers die effectief gebruikt worden door Linux werden dan gevirtualiseerd.
6.2
Energiebeheer
Veel hardware die gevirtualiseerd werd heeft te maken met het energiebeheer. Omdat de OMAP SoC ontworpen is voor mobiele toestellen is het energiebeheer een belangrijk onderdeel [34]. Het is echter niet meer de taak van een gastbesturingssysteem om aan energiebeheer te doen, maar dit is wel de taak van de hypervisor. Het is immers mogelijk dat een gastbesturingssysteem een bepaald onderdeel niet nodig heeft en het dus uitschakelt, maar een ander besturingssyteem kan dit wel nog nodig hebben. Daarom komt het gedrag van de virtuele hardware niet altijd overeen met die van de fysieke hardware. Dit is bijvoorbeeld het geval wanneer Linux instelt dat een bepaalde module automatisch in een slaapstand terecht mag komen of automatisch moet ontwaken wanneer een andere module ontwaakt. Dit gedrag werd niet ge¨ımplementeerd. Wat volgt is een beschrijving van de verschillende modules en bijhorende registers die toegevoegd werden aan de hypervisor. 45
De belangrijkste module voor het energiebeheer is de Power, Reset and Clock Manager (PRCM). Deze module is verder opgesplitst in twee submodules: de Power and Reset Manager (PRM) en de Clock Manager (CM). De CM staat in voor de verdeling van de verschillende kloksignalen. De PRM staat in voor het energiebeheer, het beheer van de systeemklok en het resetten van de componenten. Aan de CM werden drie verschillende types registers toegevoegd. Het eerste type controleert de klokstatus van de verschillende energiedomeinen. Het tweede type geeft voor de verschillende domeinen aan of ze automatisch mogen slapen. Een leesopdracht zal de resetwaarde van beide types registers teruggeven en een schrijfopdracht zal genegeerd worden. Het derde type schakelt klokken voor verschillende modules of subsystemen aan of uit. Een schrijfopdracht naar een register van het derde type zal controleren welke module of subsysteem uitgeschakeld moet worden en zal de corresponderende bit in een ander register instellen. Dit was nodig aangezien Linux nakijkt of het uitschakelen effectief gebeurt Aan de PRM werden ook verschillende registers toegevoegd die de te maken hebben met het automatisch ontwaken van modules. Voor al deze registers zal een leesopdracht de resetwaarde teruggeven en zal een schrijfopdracht genegeerd worden. De resetwaarde van deze registers zorgt immers dat alle modules aangeschakeld blijven. Er werden ook enkele “ongeldige” registers toegevoegd aan de PRM.
6.3
Beveiligingsmechanisme
De L3 interconnectiebus bevat een mechanisme om toegangen tot bepaalde modules te beperken. Dit gebeurt aan de hand van firewalls die door de software ingesteld moeten worden. Het beveiligingsmechanisme dat gebruikt wordt om een lees- of schrijfopdracht al dan niet toe te laten, wordt in Figuur 6.1 vereenvoudigd voorgesteld [34]. Het berust op verschillende registers en signalen om een opdracht al dan niet toe te laten. Wat naast een beslissing staat, zijn de signalen of registers om de beslissing te kunnen nemen. Alle lees- en schrijfopdrachten naar de registers die de instellingen voor de firewalls bevatten, zijn ge¨ımplementeerd. Het integreren van dit beveilingsmechanisme in de andere modules is echter niet gebeurd omdat hiervoor een volledige herschrijving nodig is van het systeem in de hypervisor dat de lees- en schrijfopdrachten behandelt. Dit is nodig omdat de bijkomende signalen, waaronder de herkomst van de opdracht, niet meegegeven worden in de huidige implementatie. Voorlopig was dit echter niet nodig omdat Linux de 46
Figuur 6.1: Beveiligingsmechanisme L3 bus.
firewalls op een dergelijke manier instelt dat deze alle opdrachten zullen toelaten.
6.4
Onbekende timer
Tijdens het opstarten van Linux worden enkele geheugenadressen gebruikt die volgens de handleiding ongeldig zijn [34]. In de broncode van de Linux-kernel werd gevonden dat deze geheugenadressen deel uitmaken van een reeks timers. De ongeldige geheugenadressen blijken te verwijzen naar een timer die in een oude versie van de handleiding wel beschreven werd. Deze timer werd eerst gevirtualiseerd door bij een leesopdracht de waarde terug te geven en de schrijfopdracht te negeren. Na onderzoek bleek dat Linux echter bij ´e´en bepaald geheugenadres een andere waarde verwacht. Dit adres komt overeen met de het resetregister van andere timers. Door dit te implementeren werd een snelheidswinst geboekt bij het opstarten van Linux omdat de lus, die wacht op het resetten van de timer, niet meer uitgevoerd moet worden. 47
6.5
Bijkomende aanpassingen
Naast het toevoegen van deze modules zijn nog enkele kleinere aanpassingen gemaakt aan andere modules. De eerste aanpassing is aan de UART module. Volgens de TRM moeten de registers benaderd worden per byte en dit was ook zo ge¨ımplementeerd in de hypervisor. Linux benadert de adressen echter ook per woord en halfwoord. Een toegang tot een register per woord of halfwoord resulteert nu niet meer in een crash maar zal enkel een waarschuwing tonen. Naast deze aanpassing werden ook nog enkele registers toegevoegd aan de UART module. Er werd een extra timer toegevoegd: de MPU Watchdog Timer (WDT2). De timerwaarde werd echter niet gebruikt door Linux waardoor deze timer niet volledig ge¨ımplementeerd is. Een gedeelte van het System Control Module (SCM) is ook ge¨ımplementeerd. Dit zijn vooral registers die enkel uitgelezen kunnen worden. Daarnaast heeft deze module een regio van 1 kB geheugen, die gebruikt wordt voor het tijdelijk opslaan van data. Het toevoegen of verwijderen van deze data heeft geen invloed op andere modules zodat de implementatie eenvoudig was. Het implementeren van deze module heeft echter wel wat tijd in beslag genomen omdat bijna 300 registers toegevoegd werden. Tijdens het opstarten test Linux op verschillende manieren op welke hardware er wordt uitgevoerd. Er werd opgemerkt dat het BeagleBoard niet correct herkend werd en dat sommige modules niet de juiste versienummers vertoonden. Deze aanpassingen werden ook gemaakt aan de hypervisor.
6.6
Besluit
Het werk in dit hoofdstuk heeft zich beperkt tot het toevoegen en aanpassen van enkel die virtuele hardware die nodig was om Linux te laten opstarten. Voor veel onderdelen van de hardware was het voorlopig voldoende om bij leesopdrachten de resetwaarde terug te geven en om schrijfopdrachten te negeren of geen actie te ondernemen met de nieuwe waarde van het register. Toch heeft dit werk om verschillende redenen veel tijd in beslag genomen. Voor sommige geheugenadressen leek het immers op het eerst zicht dat er zich een probleem voordeed met het virtueel geheugen omdat dit adres verwees naar een ongeldige plaats. Er moest dan gezocht worden in de broncode van Linux of andere documentatie naar de betekenis en het gewenste gedrag van operaties met deze 48
geheugenadressesn. Een andere reden is dat het aanspreken van de registers niet altijd in een logische volgorde gebeurde, waardoor er na het toevoegen van een register iedere keer gewacht moest worden tot Linux opgestart kon worden om te ontdekken wat het volgend register was dat toegevoegd moest worden. Na het werk uit dit hoofdstuk kon Linux opgestart worden tot aan de commandolijn. Het was echter niet mogelijk om commando’s uit te voeren omdat het invoeren van tekst niet lukte. Dit heeft te maken met een implementatiefout waardoor globaal de onderbrekingen afgezet worden. Er was echter geen tijd meer in deze masterproef om dit proberen te verhelpen.
49
Hoofdstuk 7 Besluit Het oorspronkelijke doel, namlijke het virtualiseren van Android, is niet volledig volbracht in deze masterproef. De oorzaak hiervan is dat er veel implementatie werk nodig is om aan de eisen van Android te voldoen. Het werk werd ook gehinderd door fouten in de hypervisor die niet altijd even gemakkelijk op te lossen waren, mede door de beperkte mogelijkheden om te debuggen. Dit heeft mij echter niet tegengehouden om zo veel mogelijk werk te doen om het virtualiseren van Android mogelijk te maken. De virtualisatie van de ARM architectuur is completer geworden door de ondersteuning voor de Thumb-2 instructieset te verbeteren. Door het werk aan het gevirtualiseerd geheugenbeheer zijn ook enkele fouten uit het systeem gehaald en werden ander fouten ge¨ıdentificeerd die nu opgelost kunnen worden door mensen die verder werken aan dit project. De toevoegingen aan de virtuele hardware zorgen ervoor dat meer recentere versies van Linux ook opgestart kunnen worden met de hypervisor, en deze starten bovendien veel sneller op. Ook komt er met de toevoeging van de unittest functionaliteit een mogelijkheid om de hypervisor meer systematisch en gericht te testen. Zo kan er vermeden worden dat aanpassingen aan het ene onderdeel voor fouten zorgt in een andere onderdeel van de hypervisor.
50
Hoofdstuk 8 Toekomstig werk Om Android effectief te kunnen virtualiseren, moet nog heel wat werk gebeuren. Een belangrijk onderdeel hiervan is de volledige virtualisatie van de hardware die nodig is voor Android. Met volledig virtualiseren wordt bedoeld dat de virtuele hardware hetzelfde gedrag vertoont zoals de fysieke hardware. In deze lijst worden enkele taken aangehaald die zeker nog nodig zijn voor Android gevirtualiseerd kan worden, en in het algemeen voor de vooruitgang van de hypervisor: • De afhandeling van onderbrekingen moet nagekeken worden zodat het invoeren van commando’s in de commandolijn werkt. • Het probleem dat ontstaat na het invalideren van de metadata over paginatabellen moet opgelost worden. • Er moet ondersteuning voor recentere Linux-kernels komen. Deze bevatten sinds versie 3.3 de Android-specifieke stuurprogramma’s en bieden betere ondersteuning voor de OMAP SoC familie. Deze ondersteuning zal vooral te maken hebben met het toevoegen van hardwareondersteuning. • En tot slot moet de unittest functionaliteit uitgebreid worden om regressies in de code tegen te gaan. Deze masterproef heeft de hypervisor op verschillende vlakken verbeterd en kan dus als basis dienen om Android en andere besturingssystemen te ondersteunen met de hypervisor. Het is echter niet altijd te voorzien hoeveel werk er precies zal nodig zijn om bepaalde zaken te realiseren.
51
Bijlage A Conditiecodes De meeste ARM instructies bevatten een conditiecode. Deze is altijd gecodeerd in de eerste vier bits. Thumb-2 instructies bevatten geen conditiecode, met uitzondering van enkele spronginstructies. In Tabel A.1 wordt de codering van de verschillende conditiecodes gegeven. Bits [31 : 28] 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110
Suffix EQ NE CS CC MI PL VS VC HI LS GE LT GT LE (AL)
Betekenis Gelijk Niet gelijk Overdracht Geen overdracht Negatief Positief of nul Overflow Geen overflow Hoger Lager Groter of gelijk aan Kleiner dan Groter dan Kleiner of gelijk aan Onvoorwaardelijk
Tabel A.1: Conditiecodes
52
Conditievlaggen Z == 1 Z == 0 C == 1 C == 0 N == 1 N == 0 V == 1 V == 0 C == 1 ∧ Z == 0 C == 0 ∨ Z == 1 N == V N != V N == V Z == 1 ∨ N != V —
Bijlage B Unittesten Unittest B.1 IT instructie . syntax unified . thumb . section . text . global start start : MOV R1 , #0 xF SUBS R2 , R1 , R1 it : ITTE MRSEQ MOVEQ BNE
EQ R3 , APSR R1 , #0 xABC fail
CMP BNE BEQ
R1 , #0 xABC fail stop
/* EQ */
stop : BKPT #0 x0 fail : BKPT #0 x1
53
Bibliografie [1] Android Mainlining Project. http://elinux.org/Android_Mainlining_Project. [2] ARM Processors. http://arm.com/products/processors/index.php. [3] CyanogenMod: Building the Kernel from source. http://wiki.cyanogenmod.com/ wiki/Building_Kernel_from_source. [4] Flyswatter JTAG debugger. http://www.tincantools.com/product.php? productid=16134&cat=251&page=1. [5] LXR Cross Referencer. http://lxr.linux.no. [6] Open On-Chip Debugger: Free and Open On-Chip Debugging, In-System Programming and Boundary-Scan Testing. http://openocd.sourceforge.net/. [7] Oracle VM VirtualBox. https://www.virtualbox.org/. [8] Rowboat: Android for Texas Instruments Devices (Sitara, Davinci and Integra). https://code.google.com/p/rowboat/. [9] The FreeRTOS Project. http://www.freertos.org/. [10] The Linux Kernel Archives. https://www.kernel.org/. [11] Xen Hypervisor Project: Leading Open Source Hypervisor for Servers. http://xen. org/products/xenhyp.html. [12] Gartner Says Sales of Mobile Devices Grew 5.6 Percent in Third Quarter of 2011; Smartphone Sales Increased 42 Percent. https://www.gartner.com/it/page.jsp? id=1848514, 2011. [13] U.S. Smartphone Market: Who’s the Most Wanted? http://blog.nielsen.com/ nielsenwire/?p=27418, 2011. [14] ARM. ARMv7-AR architecture reference manual, armv7-a and armv7-r edition, 2011. [15] BeagleBoard. BeagleBoard System Reference Manual, revision c4 edition, 2009. [16] Stefan Braehler. Analysis of the Android Architecture. Master’s thesis, KIT, 2010. 54
[17] Jason Fitzpatrick. An interview with Steve Furber. Commun. ACM, 54(5):34–39, May 2011. [18] L. Goudge and S. Segars. Thumb: reducing the cost of 32-bit RISC performance in portable and consumer applications. In Compcon’96.’Technologies for the Information Superhighway’Digest of Papers, pages 176–181. IEEE, 1996. [19] Google Inc. Google Android. https://developer.android.com/index.html, 2012. [20] Google Inc. Platform Versions. https://developer.android.com/resources/ dashboard/platform-versions.html, 2012. [21] Google Inc. What is Android? https://developer.android.com/guide/basics/ what-is-android.html, 2012. [22] Tom Krazit. ARMed for the living room. http://news.cnet.com/ ARMed-for-the-living-room/2100-1006_3-6056729.html, 2006. [23] A. Krishnaswamy and R. Gupta. Profile guided selection of ARM and thumb instructions. ACM SIGPLAN Notices, 37(7):56–64, 2002. [24] Michael Larabel. A Real Effort To Mainline Android Changes In Linux Kernel. http://www.phoronix.com/scan.php?page=news_item&px=MTAzMTY, 2011. [25] Michael Larabel. Linux 3.4 Kernel Will Gain More Android Patches. http://www. phoronix.com/scan.php?page=news_item&px=MTA2ODA, 2012. [26] S.A. Mahlke, R.E. Hank, J.E. McCormick, D.I. August, and W.M.W. Hwu. A comparison of full and partial predicated execution support for ILP processors. In Computer Architecture, 1995. Proceedings. 22nd Annual International Symposium on, pages 138–149. IEEE, 1995. [27] Bartosz Milewski. Virtual Machines: Virtualizing Virtual Memory. https://corensic.wordpress.com/2011/12/05/ virtual-machines-virtualizing-virtual-memory/, 2011. [28] OMAPpedia. Linux OMAP Kernel Project. http://omappedia.org/wiki/Linux_ OMAP_Kernel_Project. [29] Oracle. The JavaTM Virtual Machine Specification, java se 7 edition edition. [30] Gerald J. Popek and Robert P. Goldberg. Formal requirements for virtualizable third generation architectures. Commun. ACM, 17(7):412–421, July 1974. 55
[31] Philippe Robin. Experiment with Linux and ARM Thumb-2 ISA. Technical report, ARM Ltd., 2007. [32] Danielle Ruest and Nelson Ruest. Virtualization hypervisor comparison: Type 1 vs. Type 2 hypervisors. http://searchservervirtualization.techtarget.com/tip/ Virtualization-hypervisor-comparison-Type-1-vs-Type-2-hypervisors, September 2010. [33] J.E. Smith and R. Nair. Virtual machines: versatile platforms for systems and processes. Morgan Kaufmann, 2005. [34] Texas Instruments. OMAP35x Applications Processor: Technical Reference Manual, spruf98w edition, 2012. [35] A. Whitaker, M. Shaw, and S.D. Gribble. Scale and performance in the Denali isolation kernel. ACM SIGOPS Operating Systems Review, 36(SI):195–209, 2002.
56
Lijst van figuren 1.1
Virtuele machines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11
Type 1 en type 2 hypervisors. . . . . . . . . . Schema van het PSR. . . . . . . . . . . . . . . Schema van het APSR. . . . . . . . . . . . . . Voorwaardelijke uitvoering van ARM code. . . Voorwaardelijke uitvoering van Thumb-2 code. Paginatabellen op het eerste en tweede niveau. Vertaling van een VA op twee niveaus. . . . . Diagram van de OMAP3530 SoC. . . . . . . . De architectuur van Android . . . . . . . . . . Basisstappen dynamische binaire vertaling. . . Een sectieverwijzing naar de paginatabel. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
8 10 10 12 14 17 18 19 20 23 26
4.1 4.2 4.3 4.4
Foute vertaling door de initi¨ele implementatie DBT. . . . . Correcte vertaling door de aangepaste implementatie DBT. Instructiesequentie die nog altijd fout vertaald zal worden. Aangepaste Thumb-2 instructiescanner. . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
32 33 34 34
5.1
Tijdelijke sectie in de schaduwpaginatabel. . . . . . . . . . . . . . . . . . . 41
6.1
Beveiligingsmechanisme L3 bus. . . . . . . . . . . . . . . . . . . . . . . . . 47
57
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
2
Lijst van tabellen 2.1
Opeenvolgende toestanden van ITSTATE. . . . . . . . . . . . . . . . . . . 14
A.1 Conditiecodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
58
