Advanced Unit Testing in the Hedron Microkernel
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 287 | |
| Autor | ||
| Lizenz | CC-Namensnennung 2.0 Belgien: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/56912 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
FOSDEM 2022101 / 287
2
4
6
8
12
17
21
23
31
35
37
41
44
45
46
47
50
62
65
66
67
68
71
73
81
84
85
86
90
92
94
100
102
105
111
114
115
116
117
118
121
122
124
127
131
133
135
137
139
140
141
142
145
149
150
156
164
165
167
169
170
171
172
174
176
178
180
183
184
189
190
192
194
198
205
206
207
208
210
218
220
224
225
229
230
232
235
236
238
239
240
242
243
244
245
246
249
250
253
260
262
264
267
273
274
277
282
283
287
00:00
SoftwareentwicklerKerberos <Kryptologie>CodeUmwandlungsenthalpieQuick-SortPhysikalismusRechenschieberAutomatische IndexierungMAPQuellcodeRechter WinkelCASE <Informatik>Kernel <Informatik>MikrokernelMultiplikationsoperatorWeb-SeiteSchnittmengeDatenstrukturVerschlingungSpeicheradresseCodeTranslation <Mathematik>BitAdressraumNetzbetriebssystemKomponententestProgrammierumgebungPufferüberlaufKeller <Informatik>Natürliche ZahlSoftwaretestKontrollstrukturBereichsschätzungSoftwareentwicklerPhysikalisches SystemMereologieProjektive EbeneSoftwareEndliche ModelltheorieComputersicherheitGüte der AnpassungNormalvektorBefehlsprozessorProzess <Informatik>SeitentabelleRückkopplungNotebook-ComputerWhiteboardServerVirtuelle AdressePunktResultanteProgrammiergerätARM <Computerarchitektur>ProgrammfehlerFunktionalMapping <Computergraphik>HalbleiterspeicherWort <Informatik>Schreib-Lese-KopfHypermediaRechenwerkPerspektiveVierzigDatenflussTabelle <Informatik>ZweiMinkowski-MetrikProgrammierungVirtualisierungRahmenproblemHardwareWeb SiteQuaderDiagrammTechnische Zeichnung
06:35
BEEPOffene MengeWeb-SeiteSeitentabelleUmwandlungsenthalpieTabelle <Informatik>ParametersystemHeegaard-ZerlegungImplementierungWeb-SeiteSoftwareentwicklerSchreiben <Datenverarbeitung>SpeicherabzugWellenpaketEinfache GenauigkeitFunktionalLaufzeitfehlerAggregatzustandProdukt <Mathematik>SoftwaretestMAPKomponententestSpeicheradresseNichtlinearer OperatorCASE <Informatik>Prozess <Informatik>SoundverarbeitungHalbleiterspeicherPolygonzugRechenwerkTwitter <Softwareplattform>Ordnung <Mathematik>CodeQuick-SortRechter WinkelPunktHoaxInformationsspeicherungRechenschieberRichtungMessage-PassingMapping <Computergraphik>Translation <Mathematik>Klasse <Mathematik>VerschlingungDatenstrukturRobotikObjekt <Kategorie>BefehlsprozessorArithmetisches MittelEinsIndexberechnungKernel <Informatik>Klassische PhysikEinschwingvorgangValiditätHyperbelverfahrenSpannweite <Stochastik>VersionsverwaltungGenerizitätOverhead <Kommunikationstechnik>
12:58
Web-SeiteStatistikROM <Informatik>Textur-MappingVektorpotenzialMessage-PassingNP-hartes ProblemKerberos <Kryptologie>ImplementierungFehlermeldungNetzbetriebssystemMailing-ListeAbstraktionsebeneKomponententestProdukt <Mathematik>Open SourceLesen <Datenverarbeitung>UmwandlungsenthalpieSoftwaretestThreadHoaxWeb logSpeicheradresseDatenstrukturPhysikalisches SystemQuick-SortStellenringSchreiben <Datenverarbeitung>RechenwerkHalbleiterspeicherHeegaard-ZerlegungWeb-SeiteSpeicherabzugVererbungshierarchieEinschwingvorgangBildschirmmaskeSeitentabelleRechenschieberParametersystemSampler <Musikinstrument>Zeiger <Informatik>NebenbedingungKlasse <Mathematik>DatenparallelitätVollständigkeitNichtlinearer OperatorMatrizenrechnungMapping <Computergraphik>Twitter <Softwareplattform>ValiditätMessage-PassingKategorie <Mathematik>VersionsverwaltungLuenberger-BeobachterSoundverarbeitungCodeKernel <Informatik>AggregatzustandSchlüsselverwaltungBitErwartungswertFunktionalLoopPunktMultiplikationsoperatorVektorpotenzialBefehlsprozessorProzess <Informatik>Rechter WinkelMathematikTabelle <Informatik>URLUmfangMetrisches SystemBitrateMAPNeuroinformatikMatchingFächer <Mathematik>Zusammenhängender GraphDienst <Informatik>Figurierte ZahlGruppenoperationComputeranimation
20:18
Computeranimation
Transkript: Englisch(automatisch erzeugt)
00:12
Hello, I'm Jorn Schäckliner, and I'm going to talk about advanced unit testing in Hadron. So this year I'm not organizing the microkernel dev room, so I know what effort goes into that,
00:27
and I wanted to say thanks to Martin and Sebastian who took the organizing this year. And with these words, let's start. This may be the first time you hear of the Hadron microhypervisor, so let's start with what it is.
00:44
Hadron is a microhypervisor with a capability-based security model that's written in C++. It's developed by Syverus Technology. We focus on simplicity, readability, testability, and our use cases are mostly in the realm of x86 virtualization.
01:05
The source code lives on GitHub, and you can just check it out there. It is a fork of the Nova microhypervisor, which you can also find on GitHub. If you're interested in what we do with it, just check out our company blog, which is linked below.
01:23
But today I'm not going to talk about any of what we actually do with this kernel, but instead I wanted to talk about testing. And to see why, I just want to step back a bit. So for me, a healthy software project is a project that is easy to change by multiple people,
01:44
and when you change it, you need to have the confidence that it doesn't break in weird ways. And there are many ways to achieve this, but one good way is to have unit test coverage. Unit tests are awesome because they can run anywhere, which is very nice in operating system development.
02:06
So if you don't have the weird arm board that your kernel runs on, or you don't have the big server box, your unit tests will still work because they just run on your laptop. Also, the feedback you get from unit tests is almost immediate.
02:21
So headrun specifically builds in a couple of seconds, even complete build. It's only a couple of seconds, and the unit tests also give you immediate feedback. You don't have to wait for minutes or hours until some test system comes back. And then, since unit tests are typically just normal Linux application, it also unlocks lots of good tooling like sanitizer.
02:44
So you can just use the address sanitizer with your unit tests. Unfortunately, kernels are not doing so well in the testing departments. This has some inherent problems, but also some social problems, I would say.
03:02
So the inherent problems are that the programming environment is usually strange, so it's not what you would see on Stack Overflow. You also, due to the nature of kernels, you have to interact with hardware, which sucks from a testing perspective. But really, a large part comes down to a mindset, or you can also call it lack of education.
03:23
So few operating system courses ever talk about how to write operating systems in a way that the code is easily testable. And the end result is that the testing story for lots of low-level projects are extremely poor.
03:41
And the point of this talk is mostly to start spreading some testing ideas for low-level code and maybe also motivate one of you in the audience to share their testing ideas. Our example today will be the page table manipulation code in Headroom.
04:04
So we will come to what this actually does in a second, but page table modification is kind of an important piece of code in the microkernel because microkernel don't have a lot of functionality by design. The ability to create address spaces is a pretty central one that is still left in the microkernel, so this should better work.
04:28
The other thing is page table manipulation code. Bugs in this code are extremely hard to debug, so we will see why in a couple of slides. So having good test coverage for this code is really crucial.
04:44
So when we needed to modify this code, we asked ourselves how to get good test coverage, and we decided to redesign and reimplement the whole thing to get the test coverage we wanted. So before we get to the code itself, so maybe a quick recap for people that are not familiar what this page table thing is about.
05:07
So in an operating system you typically execute code in address spaces, so your process is basically an address space. So the programmer sees the virtual memory on the left, some code pages, some data pages, these pages have a fixed size.
05:23
On x86 it's 4K, 2MB or 1GB. And then there's a set of tables, a data structure, that translates each of these pages to the specific physical memory location,
05:41
sort of physical frame, together with access rights. And the data structure that contains this mapping is called the page table. So this is the most low-level slide I'm going to have. How does this actually work in hardware? So the CPU takes the virtual address, which is the FFFF8C something on the left,
06:05
and if we want to map it to something else, the CPU needs to know where in the page table it actually needs to look. So it will take 9-bit chunks, four 9-bit chunks for the four levels of page tables that we can have, and it will just take the first index, index into the first page table,
06:24
and either it finds a link to the next page table or the translation finishes there. And in the end there are like 12 bits that just get added to the physical address we find in the page table. So for this example we have these four page table indices and an offset.
06:44
If you are interested how this works in detail, I'm glossing over many details, check out the Intel Software Developers Manual. So what are the challenges if you write code that manipulates page tables and you want to test it? So the first one is inherent to pretty much all kernel code.
07:02
The code uses kernel internal APIs, which don't exist if you want to compile the code for Linux. So this prevents us to easily compile the code for Linux. The second one is more specific to page table code, and this is also the main point being addressed in this talk today,
07:24
and that is that the CPU will read the page tables while they are being modified. So that means that the classical way of testing this code, like producing an initial state, doing an operation on the page table, and then checking whether whatever comes out is correct,
07:42
is insufficient because the CPU will also see all the transient states in between. So here we have to spend some effort to make this testable. To drive this home a bit, I have an example here. So this is the only slide that actually contains page tables.
08:04
In this example here, we have one gigabyte page. So it works like this, that the CPU would start reading. It would read the address at the page table base register, find a page table, would look up an entry there. For us, this points to another page table.
08:23
This level would then map one gigabyte entries, and there it is like a super page in there. Just stops at one gigabyte. So in this example, we want to write protect a single four kilobyte in this one gigabyte range. So to do this, our code would need to first split the gigabyte page into smaller pages.
08:47
So the first step is to allocate a new page table. So this is like the next level, which maps even smaller entries to megabyte. And we just use this to recreate the mappings that we had from the gigabyte page before.
09:03
But this is like two megabytes, we still want to see a four kilobyte mapping. So we need to take one of these two megabyte pages and create the next level of page tables for it. So we would have now the fourth level of page tables where we map four kilobyte pages.
09:21
And now we have to link these newly created page tables into the structure. So first, in the two megabyte page table, we link the smaller ones. And then in the gigabyte page table, we can link the two megabyte ones. And now everything is connected. So if the CPU now does a translation, it can reach all the way to the four kilobyte entries.
09:44
And now we are at the point where we can actually change one of those four kilobyte entries to be read-only and we have accomplished what we want. So if you didn't get all the details, don't worry about it. The only point from this slide is that you can see that the order of operations matters.
10:04
So if we would have created the links to subsequent page tables before we prepare them, the CPU could traverse the links and see garbage. And this is something we want to prevent. So the order of these operations has to be correct.
10:26
The idea here is that in the unit test, we want to record all visible side effects, so all page table modifications, while our page table code is running. So this will allow us to check all transient states for validity later.
10:45
But we also want to do it in a way that doesn't introduce any runtime overhead if we use this code in production. And to do this, we reach into the C++ toolkit.
11:02
Specifically, we apply what's called policy-based design. So policy-based design is an idea that was made popular by the book on the top right, Modern C++ Design. This is not a modern book anymore, so this is from the early 2000s, and the C++ style in there is not very modern anymore.
11:26
But it does explain the idea of policy-based design. Policy-based design at the core means that we try to push all the functionality that is not core to the problem we're using into policy classes.
11:44
And these will be handed into our implementation as compile-time parameters. So for us, we want to have different ways of writing to memory. So we want to have a simple implementation that just writes to memory for production use,
12:01
and then we want a more complicated version that allows us to do the flight recorder use case for testing. So we have a policy class called memory. We instantiate this, so we have a policy object in our generic page table class. And whenever the code actually wants to write to a page table, it would use this policy class.
12:26
So here we have a write to physical memory. And as you can see in the top, we also do this with other things. This has the benefit that it also solves our first problem, and that is that we can use this page table code without directly referring to any of the kernel APIs.
12:46
That means we have head-run-specific implementations for the production use case, and we have Linux-specific implementations for unit testing. But the core of the code is exactly the same. For memory, this looks like this.
13:01
So this is the memory policy implementation that we use in the production kernel, where read and writes basically map to atomic reads and writes. So there's no overhead introduced there. And for the unit tests, we have this fake memory, where we keep a list of all writes to memory.
13:24
So here we have the thing called memory list, which is literally a list of pointer plus data pairs. And you see that the write implementation, so the page table code writes to this, it will just add a new entry to this memory list.
13:40
And for reading, reading from a pointer will just iterate through this list until it finds a matching write and then provides the value that was written. And if there's no write that matches, we just provide zero. And with this memory list, we can now recreate the state of memory in all,
14:05
so we can recreate all transient states of memory. So now we come to the one slide that I basically wanted to show. So this is like the core of everything, which is the test, which shows that the super page splitting example,
14:23
so the example where we split the gigabyte pages into smaller pieces, that this works as expected. So we go through this from the top. So first, we have our initial one gigabyte mapping. We also define some valid transient mappings that we want to see.
14:43
So there's like a transient two megabyte mapping and the transient four kilobyte mapping. And then there's page mapping, which is what we actually want to enter into the page table. Then we create the initial state. So we create the page table state with this one gigabyte mapping. And then we take a snapshot of the memory as it is at that point.
15:05
So we are not concerned about everything that happened until this point. So now there's this thing mapped four kilobyte over one gigabyte page, which is what we discussed in the example, which this is exactly what we're going to test.
15:20
So we execute this operation. And then the for loop will take the memory and just sort of rewind it one by one through all previous states. And for all previous memory states, we will look up the mapping at the address that interests us. And we check that it's either the initial one, it's either of the transient ones,
15:44
or it's the one that we want to end up with. And with that, we are very sure that if the CPU does that in the real system, it will also only see these kinds of mappings.
16:01
So how do you take this further? So we haven't implemented all of the things here, but you can. So you can now express tests that were previously pretty hard to express. For example, you can write a test that checks that page tables are actually disconnected from all structures before we hand them to the deallocator.
16:21
We can also write a fake memory implementation that makes atomic compare exchanges fail. So typically, this is hard to test in a unit test because it would require a concurrent thread that writes to specific memory locations at the right time. But with the abstraction we've built here, we can just say that the memory write will happen exactly when we need it.
16:44
And we can test otherwise hard to reach atomic compare exchange failures. We can also check whether page tables are read and written exactly as often as it's needed for specific operations to complete.
17:01
This is also sometimes useful for concurrency properties. So we've only started to tap the potential with this abstraction. One thing that sucks pretty hard with policy classes is that if your policy class doesn't really implement the API
17:22
that is expected by your code, then the error messages will be pretty horrible. C++20 has something that helps us here. It has concepts where you can constrain compile time parameters to adhere to some form of specifications.
17:41
These are C++20 concepts. So here we say that the memory access concept has to have a read and write function that sort of worked like expected. And this sort of feels a bit like traits in Rust and also allow us to get way more readable error messages.
18:05
So let's summarize. So what we did here is we rewrote Hadron's page table code. After we actually decided which properties we want to test, we used policy-based design to allow competing implementations of certain aspects of the code.
18:24
And we used this to unit test otherwise really hard to test properties. The key was to record all observable side effects in our modification of the data structure, and then look at the past to see whether all versions of the past adhere to some property.
18:48
I believe this is a concept that is applicable to both C++ and Rust, so this makes it not C++ specific. But to step one step back, the key message here is we can do a better job at testing our kernel implementations.
19:08
And if you have an interesting story about how you test some aspects of your low-level code, I would be glad if you share it in your next talk at Forstner.
19:23
Some final resources. On the left side is Sybaris technology stuff. So we have a tech blog where you can see what happens in Sybaris technology with our products. We are on GitHub with our open source components, and you will find Sybaris technology on Twitter.
19:40
For me personally, I have a blog where I rant about x86 stuff mostly. You can find my open source stuff on GitHub as well. With a friend, we do the syslog podcast where we talk with the local operating system people about systems topics,
20:01
and then you can also find me on Twitter and Matrix. So if you have any questions, feel free to ping me on either of these channels. And with that, this concludes the talk, and I'm happy to take questions.