Writing an OS in Rust: Introduction to Paging
os.phil-opp.com
os.phil-opp.com
A lot of the OS development, especially esoteric subjects are behind walls of IP control barring Linux kernel. Even then, just reading the source code is different than having access to the knowledge base that enables you to write such a code. I am new to all of this but like you, I am fascinated.
Handmade Hero is unique in that it is: - Real time, watching a dude program a game - He speaks his though process, stumbles, gets up and resolves issues - Community interaction as they progress through the game
All, at the expense of content bloat. I think its popularity has spoken for itself in that Handmade Hero is a totally unique form of education.
Join the Redox community! Development is on gitlab[0] and chat is on Mattermost.
I don’t know what this says about me but I haven’t been this excited about new OS since I first installed OpenBSD 2.5. :)
I think writing an OS from scratch is discouraging and not very accessible because... writing an OS is discouraging and not very accessible. It's a bit as if a painter was saying "It tried looking up guides on how to paint The Wedding Feast at Cana but they all make it look super difficult, I wish I could get an easy step-by-step tutorial". Even if you break it down in small, digestible parts I'd wager that you'll end up with a few hundred episodes before you even get a basic microkernel up and running on a modern system. It's truly a daunting task.
I learned that the hard way: I tried to write a guide on how to emulate a PlayStation from scratch. At first you focus on emulating the instructions in the CPU, that's relatively focused and straightforward. But then once you're done with that you need to explain the various peripherals, and the main bus, and the interrupts, and the cache, and the timers, and the pipelines, and the intricacies of the various CD formats, and the memorycard filesystem, and video modes, and paging, and high impedance, and metastability and everything kind of interacts with everything else so it's difficult to maintain a coherent narrative.
On top of that a PlayStation is a ridiculously simple system compared to a modern desktop computer. The task of writing a very accessible guide on how to write an OS that would take you from zero to a working userland is absolutely tremendous. I think you could probably write a thousand-page book on the virtual memory subsystem alone.
I wouldn't consider Phil's blog a good resource for, e.g., gaining particular insight into how something like the Linux kernel works, but I also don't think Phil intended it for that use.
Have you tried reading any book?
By the way, you mention high impedance and metastabilty. Knowing next to nothing about the PlayStation, are those concepts relevant for emulation there for some reason? For other platforms I think that’s an abstraction layer that even accurate emulators rarely hit (though I might be wrong). Is there something special on the PlayStation?
- Regarding high impedance it might be relevant if you want to explain how the controller and memory card interface works, and why you read full 1s when nothing is connected (high impedance line with a pull-up resistor). More generally the issue will crop up every time you have an interface that might be floating, I think people who have no background in electronic engineering might assume that unconnected wire == 0 on the line.
- Regarding metastability it crops up in the timers. The PSX timers can either run from the CPU clock or from signals coming from the GPU (pixelclock and horizontal blanking). IIRC this is used in some lightgun games to be able to synchronize the signal coming from the gun ("I saw the lightbeam") with the current position of the pixel in the frame currently being sent to the TV set.
The problem with that is that the signals coming from the GPU are not synchronous with the CPU and apparently are not resynchronized. That creates metastability issues when the value from these timers are read from the CPU and you may end up reading bogus values from time to time. The software workaround is to read the register values in a loop until you get twice the same value in row. Now, you probably don't need to emulate that but if you want to be thorough it's probably worth pointing out.
So in summary you're right, you don't really need to know that in order to write a proper PSX emulator but if you really want to get into all the details you'll probably want to brush the subject. At least these are concepts that anybody is sure to encounter eventually is they spend time in bare-metal land...
Of course it's not the smartest choice for that purpose, because there might be chip-to-chip differences. And environmental factors like temperature could affect it as well.
But who knows what people wrote after Bleem PS1 emulator was public?
So have metastability issues (or other HW bugs) ever been used for copy/emulation protection?
I'm not aware of any copy-protection scheme on the console that would target specifically emulators. I guess Bleem was not big enough a threat to warrant specific protections?
Besides I expect that Bleem, in order to run full speed on the underpowered hardware of the time, must have had terrible accuracy and therefore must have employed a wealth of game-specific hacks to get around issues. As such I expect that if they had decided to emulate your game they wouldn't have had too many issues reverse-engineering any trivial metastability-detecting code to implement an ad-hoc hack.
And nice to know that there are indeed metastability issues that crop up very visibly in the PlayStation!
also, being able to develop under qemu is a massive* timesaver. not only can you reboot completely from the terminal, and have access to a gdb stub, but you can also get tracing information directly from the "hardware" itself.
using the virtio drivers gives you a pretty quick onramp to having network and storage support.
you could* write a 1000 page book on vm...but writing a little interface that builds x84-64 page tables really is a couple hundred lines. interrupts another 1-2 hundred. threads another, syscall dispatch, etc.
I'm not suggesting that everyone go off and build their own production grade private OS.. but its a pretty fun exercise, and it gives you a really great perspective on whats going on down there.
A lot of work, yes, but, IMO, fairly accessible if you are willing to skip the steps initializing the hardware (“it’s tedious, but luckily somebody did it for us”), don’t aim for replacing the state of the art, and support limited hardware (certainly no USB-C, for example)
For example, your first usable system doesn’t need paging, memory protection, or even a halfway decent memory allocator. You also need not support zillions of different devices (Linus didn't, either, with his first usable system)
Just start with an OS that runs a fixed max number of processes each in some fixed amount of memory in round-robin fashion. Let’s say you have a gig of RAM. Split it in 1024 1 megabyte blocks, reserve one for your OS, and require programs to be position independent.
Yes, that’s almost equal to a single process running multiple threads (in some sense even worse, as a program wanting over a MB of memory can’t run, even if the other processes take only a small fraction of their megabyte or memory) but that’s what makes it accessible. It also isn’t too dissimilar from what was done historically (it isn’t that many steps away from the original model of Windows CE, for example, and that isn’t even 25 years old).
If you have that and a minimalistic file system, you probably can run quite a bit of Linux userland on it (slowly because of the round-robin scheduler, and crashing often when processes run out of memory), but then it’s just a matter of scratching itches as they come up. Memory protection probably would be one of the first features I would add, as it makes the system way more robust. An editor and a (simple, say a single-pass compiler of a pascal-like language) compiler also would be high up, to make the system self-compiling. VM paging probably would come late in the game now that small systems have at least a gig of RAM.
The trouble is, you get yet another UNIX clone that way.
[1] https://github.com/siraben/zkeme80 [2] https://www.ticalc.org/archives/files/fileinfo/442/44227.htm...
I actually learned C by writing an OS from ages 16 to 18. I don't know if I'd recommend it to everyone, but it is surprisingly accessible if you limit scope. The real hard parts are dealing with complicated hardware. If you care about the basics like keyboard, mouse, display, flat memory, no threads, then its incredibly easy in 16bit C for x86. 32bit C (i386) is also easy, but does require a bit more setup etc.
It is incredibly educational learning how to write your own libc and having to manage toolchains etc. You very quickly learn the exact boundaries of what is computer controlled and what is toolchain controlled, and of course what is controlled by your own code.
And yes, I had a similar experience to you re: emulators. Tried making a simple 8086 computer emulator. CPU instructions are really easy and really the part I enjoyed. Emulating the hardware and all the machine protocols gets very difficult and complicated very quickly. I ended up, after a few months of that, rescoping the project to only be an 8086 CPU emulator, which was one of the few projects of my youth I actually completed.
like these articles too as they are fairly complete where a lot of other tutorials omit a long of things or are just some scattered collection of information which is hard to put into a project.
You can also follow the Rust Embedded Working Group blog if you wish: https://rust-embedded.github.io/blog/
I took a class in it about 2 years ago now, it was really cool. I’m not an embedded developer though, so not sure of your needs here.
Tock appears to be a Rust based embedded OS, so relevant to this discussion.
You want someone to write a Rust RTOS? Or would it suffice for a vendor to release a BSP with Rust support? IMO your current RTOS vendor can (and should!) offer this. Lots of existing RTOS companies will vendor a gcc or clang toolchain for their customers. The fact that C and C++ are well specified independent of their implementation really helps, though. But the baseline rust toolchain already provides a lot of what's needed. They "just" need to offer integration with their C library, designate llvm triple(s), etc.
If your RTOS vendor offers support for C and C++ already, chances are you can write rust for your target already. Unfortunately you'll need to stick to no_std until that BSP shows up though. :)
I had to look that up, seem like what you’re talking about here.
I’d also like to see Rust make it’s way into embedded. C support for things like data serialization or RPC for interfacing to web stuff is limited, people just don’t port it to C. And C++ doesn’t thrill me in terms of its non-deterministic garbage handling and difficult to debug nature. Rust though, seems modern and still safe, but I looked over the crates for embedded it’s prstty slim pickings!
When I see mfgs pushing out their own Rust libs, or a professional IDE with support I can buy that uses the Rust compiler, I’ll give it a try. Until then, it’s clearly hobbiest-only.
My company, Ferrous Systems[2], is also focused on embedded systems development in Rust, and we are already helping companies both with embedded linux and bare-metal/RTOS projects in Rust.
We're also running a conference in Berlin on April 26th-29th called OxidizeConf[3] if you are interested in learning more about what is already going on in the Embedded Rust world :)
[0]: https://github.com/rust-embedded/wg
Frame entry 511 for "Level 2 Page Table" should be 32KiB instead of 24KiB.
Yes. To begin with, on modern processors, paging is tied with the memory protection system. Memory is protected on a per-page basis. Memory mapped files are implemented through paging. There's also backwards compatibility. Virtual memory allows 32-bit applications to have their physical memory located anywhere. Without that, we'd have to ensure that they reside below 4GB. Programs would start up slower as the executable would have to be relocated every time. Additionally, it's hard to imagine a hypervisor that doesn't use virtual memory. Virtual memory allows hypervisors to present a unified address space to their guests; no matter how fragmented physical memory gets.
What if we don't tie paging with memory protection when designing CPUs? What if we don't assume, build, or run 32 bit applications? What if we do actually put a hard physical 4GB (or whatever) limit on processes? What if we don't need hypervisors?
What if we trade off hardware and software complexity we've built decades ago for limitations we had decades ago, and build something simpler from scratch?
Just allocating into such a memory region (essentially custom page swapping) will eventually be possible with data structures that can be constructed with custom allocators, but it still wouldn't be ok to reload those.
I found an old discussion on this topic here: https://news.ycombinator.com/item?id=13890011
Note that the Microsoft C++ compiler implements based pointers, using the __based keyword.
So to do this safely all the types must be whitelisted through a custom trait. Copy is close, but not quite, since references are still Copy.
It is easy to show that the total utility of a piece of data to the rest of the program is reduced by assigning an owner to it. Each potential user of the data, faced with the need to mess with the borrow checker to use it, may choose to mess, or may forego use of the data and write a complicated workaround instead.
To counter the borrow checker, I'm currently designing a programming language featuring a mechanism that grants free access to data structures, with the restriction that copiers must grant the same rights to anyone else:
0. the freedom to use the data for any purpose,
1. the freedom to change the data to suit your needs,
2. the freedom to share the data with your friends and neighbors, and
3. the freedom to share the changes you make.I don't think this is true at all. Reducing copies and allocations in my programs is one of the things which has speeded them up the most.
> If widely useful data is protected by the borrow checker, far fewer people will use it.
Are you also against private struct/class fields? Because they also restrict access to useful data.
For me, the need for Rust is as a language that gives me maximum possible performance, while giving me safety guards that C and C++ do not. This makes Rust much easier to use than those languages for me.
So....C? GNU makes so much sense now!