Hacker News new | past | comments | ask | show | jobs | submit login
Writing an OS in Rust: Introduction to Paging (phil-opp.com)
597 points by ingve 3 months ago | hide | past | web | favorite | 79 comments

I've followed Phil's site on making an operating system. Ever since having worked on PintOS in college, operating systems and their internals have fascinated me. I've tried learning more about writing operating systems via resources like the OSdev wiki, but much of its material almost seems to discourage working on an OS of any kind unless you're already sure of what you're doing. Phil's articles seems so much more accessible for someone just wanting to dip their toes in the water.

I think it's one of these things that's more approachable if you start by working on specific subsystems of an existing OS. This way you don't have to figure everything out at once. At least that's how I did it.

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 think writing an OS from scratch is discouraging and not very accessible”

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.

For what it's worth, this is exactly how most Operating Systems courses in undergraduate CS work, so it definitely seems like many different smart people have converged on this as the right way to go. At least in my course, we did build a toy OS by the end of the semester, but it was rigorously divided projects for the individual subsystems in isolation: write the pre-emptive scheduler, write the networking layer, write the filesystem, etc. A modern OS is an incredibly complex beast and trying to grasp it all at once is just going to lead to madness.

I fully agree, but I think it's good to have options on how to approach the issue. Generally, I've referred to OSDev when I need more real-world information on how things tend to work in practice and resources like Phil's when writing a toy operating system.

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.

> I need more real-world information on how things tend to work in practice.

Have you tried reading any book?

I think it's one of these things that's more approachable if you start by working on specific subsystems of an existing OS. This way you don't have to figure everything out at once.

The trouble is, you get yet another UNIX clone that way.

> I think writing an OS from scratch is discouraging and not very accessible because... writing an OS is discouraging and not very accessible

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.

i dont disagree with you, but there are alot more basic resources available now then when I learned kernel programming in the early 90s.

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.

That's why it's important to choose simpler systems. I've been having fun writing a Forth-based Z80 operating system for the TI-84+ calculator[1]. There isn't too many moving parts and there are many "toy" systems to learn from such as one that boots up to a smiley face[2]. It's all about choice of architecture.

[1] https://github.com/siraben/zkeme80 [2] https://www.ticalc.org/archives/files/fileinfo/442/44227.htm...

I agree.

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?

It's been a while since I've looked into it so I hope I won't be too far off the mark:

- 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...

Ah, thanks. Now that you mention it, high impedance data lines ("open bus") do play a role in other platforms as well. Even more so, on the C64 for example some undocumented instructions cause conflicting drivers to drive the same lines and produce randomish/unstable outcomes.

And nice to know that there are indeed metastability issues that crop up very visibly in the PlayStation!

It's conceivable that metastability issues could be used as a part of copy protection. Well, protection against emulation more like.

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?

Most (all?) copy-protection schemes on the PSX had to do with the CD subsystem. I think they were mainly attempting to defeat hardware "modchips" used to play non-original copies of games. Obviously those are trivial to bypass in an emulator.

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.

There are copy protection schemes on magnetic disks that mess with the clock bits on the disk to produce an unstable value:


This would make sense....if existing OSes were very good at maintaining non-leaky abstractions. As it stands, one would have to learn tons of stuff unrelated to the task at hand, on top of all the legacy cruft that usually comes with the hardware itself.

To your comment about a PlayStation being ridiculously simple compared to a desktop computer I'd call that close to true in the case of the now 20 year old first generation. The most recent two have basically been custom extensions on top of an operating system (FreeBSD 9). Which is to say they are desktop computers.

I generally assume if there's no numbers appended to the end of PlayStation it's referring to the PlayStation 1. Also, based on the context of what the parent poster was describing, I think it's fairly safe to assume they were in fact referring to the 'first generation' Playstation as you call it.

I agree. Wouldn't it be amazing to have a "Handmade Hero" series but for OS development in Rust? That would be incredible.

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.

>A lot of the OS development, especially esoteric subjects are behind walls of IP control barring Linux kernel.

Join the Redox community! Development is on gitlab[0] and chat is on Mattermost.

0: https://gitlab.redox-os.org/redox-os/

+1! Redox Os (micro kernel Os written in Rust) feels like a gust of fresh air! Godspeed! I am rooting for you!

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. :)

Just found "Handmade Hero" last weekend and now this. Programmer's dream

How does one approach watching Handmade Hero? There's just so much content...

Think it is a problem but every other resource in game development is summarized, organized and bookish.

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.

Is there any video somewhere of the actual game the handmade hero series builds up to? I would want to know the goal before jumping in

The game is still actively in development. It isn't just a clone of some other game, it's a new game and the actual design of the game is another part of the project that's evolving as the engine is built.

To be honest, I think this is the primary weakness of Handmade Hero. Casey is plainly a more talented programmer than designer, and his missteps in the latter domain felt to me more like wasted time than valuable experience. This is why I stopped watching somewhere between episode 200 and 300.

Backtracking, experimenting, and changing your mind is part of the game development process. No game ever ends up being exactly what the designers imagined at the start.

Same here. Especially MenuetOS[1], because it was written in Assembly and originally fit on a floppy disk. That's a level of patience and programming (in Assembly) that I can only admire from afar...

[1] - https://en.wikipedia.org/wiki/MenuetOS

Holy heck, it's still in active development

definitely not an easy journey :D to learn to write x64 OS. After getting paging and interrupts it plunged me into the depths of compilers / assemblers / file formats and linking & loading all to be tackled at the same time :'D would use ELF to prevent 2 of the topics, but where's the fun in that :D

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.

As a side note: I wish Rust would come to embedded development ASAP running a real time OS written in Rust. You can use massive Boost libraries and Qt frameworks on non-embedded systems with C/C++, but in embedded, there is no such luxury. I am new to it but it is painful and I wish to see a day where we have a complete LLVM based ARM compiler toolchain with Rust sitting on top. I think there were some blog posts about running Rust on STM32 but it is still very early.

Hey, I saw that links to the Embedded Working Group[0], TockOS[1], and others have been posted already, and those are great places to start!

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

[1]: https://www.tockos.org/

[2]: https://ferrous-systems.com

[3]: https://oxidizeconf.com

It is still pretty early, but if there's been quite a bit of progress this year. This is probably the closest to what you are looking for that exists at the moment: https://github.com/japaric/cortex-m-rtfm

You can also follow the Rust Embedded Working Group blog if you wish: https://rust-embedded.github.io/blog/

Thank you for sharing, subscribed. As I read through the Rust Embedded Work Group manifesto, it is comforting to see the level of organizational skills, planning and vision of the team involved. Bravo. https://github.com/rust-embedded/wg

Have you looked at TockOS? https://www.tockos.org

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.

Ooh that looks pretty interesting!

Tock appears to be a Rust based embedded OS, so relevant to this discussion.


> I wish Rust would come to embedded development ASAP running a real time OS written in Rust.

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. :)

BSP, board support package.

I had to look that up, seem like what you’re talking about here.

Sorry, yes, that's what I meant. It's a soup-to-nuts working+tested configuration of a board, bootstrap code, examples that exercise board features, etc. IIRC this is common for chip/computer/board/RTOS vendors to provide.

Get used to the idea that embedded is 15 years behind PC. Which is initially frustrating but if you step back is kind of a good thing.

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.

Non deterministic garbage handling doesn't sound right in combination with C++. You have to do it your self. And you can make it deterministic.

C++ has deterministic garbage collection.

C++ does not have garbage collection of any sorts. Objects leave the scope and are destroyed, however the order in which they are destroyed is not defined by the standard.

C++ has a garbage collection interface API since ISO C++11, it is up to the respective implementation to provide an optional implementation.

Not only this is interesting well understandable Rust code for non-Rust developer, but it is also one of the best tutorial how page tables work on modern PC CPUs.

Regardless of the platform, this is a truly excellent introduction to memory segmentation, which in my experience tends to be relevant far outside of the realm of operating system (or even single process application) development. Just the other day I was struggling to explain several concepts illustrated eloquently here to a coworker trying to design a scheduling/persistence system for variably-sized datasets that needs to be stored in hundreds of Redis instances across a compute cluster.


Frame entry 511 for "Level 2 Page Table" should be 32KiB instead of 24KiB.

Phil writes this topic very clearly unlike many others, good stuff

Any idea what tool might have been used to create the diagrams?

They were created with draw.io (https://about.draw.io/).

I'm a few surprised nobody have mentioned UlixOS [1]. I'm reading their book, it is just great on many aspects, although it rushes to explain other things that should be detailed a bit more. The chapter about paging is very explicative too.

[1] http://ulixos.org/

The article seems written much easier to follow than PintOS manual. Could anyone tell me how much writing OS became enjoyable by adopting Rust? Dealing with a excessive amount of unsafe pointers was really a pain in my memory.

With memory growing arguably beyond what most application workloads really require anyways, and possibly hardware such as Intel Optane, do we still need things like VM, paging, and segmentation?

>do we still need things like VM, paging, and segmentation?

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.

I was thinking in terms detached from typical system architecture.

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?

On page tables... Why would they go to 5 levels rather than just increasing the page size and the number of bits in the indexes from 9 to 12 and make each page 32K or 64K?

I assume backwards compatibility. It's a much smaller change to existing operating systems than to create a completely new page table format.

Why not join Redox?

Redox looks awesome, my impression is that this is more about learning by implementing from scratch. I could imagine feeling more comfortable contributing to something like Redox after working with this course.

Off topic: can we please get support for storing arbitrary data structures inside mmapped files (with nonfixed base address)?

That's not possible to do safely for arbitrary data structures because they can contain pointers or references. If you reload to a different address then the pointers, even within the allocated chunk, would be invalid and require fixup. And if you require fixup then you might as well do (de)serialization for your data structures.

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.

Perhaps this problem can be overcome by modifying the concept of a pointer slightly, to make it a "based pointer" (?)

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.

Specialized data structures can be built that contain primitives and other types supporting this kind of thing. But you still can't store arbitrary data because they could contain FFI pointers, handles to native resources, things that need to run destructors etc.

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.

Curious to see a re-write of MINIX in Rust.

Nothing like finally grokking a major part of the CS operating systems curriculum. Wonderful write up

While in college, I did not understand paging well. Thank you for the wonderful post.

I had trouble understanding how paging worked it until it was explained in Rust

I've never programmed in Rust because I still have trouble seeing the point. It seems overly restrictive. A copy of any data has nearly zero marginal cost (and you can pay the cost by doing the work yourself), so in a free machine, it would have nearly zero price. If widely useful data is protected by the borrow checker, far fewer people will use it.

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.

> A copy of any data has nearly zero marginal cost

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.

The person you're replying seems to be making a parody of copyleft, applying Richard Stallmann's four essential freedoms to program data. I don't think it's a serious attack on Rust's borrow checker.

Ah yes, I see it now. Thanks :)

I very much agree with this: https://www.youtube.com/watch?v=_xLgr6Ng4qQ

I'd just like to interject for a moment. What you're referring to as Rust, is in fact, Rust/LLVM, or as I've recently taken to calling it, Rust plus LLVM ...

"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:"

So....C? GNU makes so much sense now!

i.e. Memory will be under GPL license!

Did you just read the Mongo/Amazon article and get inspired?

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact