Hacker News new | comments | ask | show | jobs | submit login
Writing an OS in Rust: Catching CPU Exceptions (phil-opp.com)
171 points by phil-opp on May 28, 2016 | hide | past | web | favorite | 41 comments

Haven't been following this blog, but one thing caught my eye while skimming the post:

>The implementations of these methods need to modify the correct bits of the u16 without touching the other bits. For example, we would need the following bit-fiddling to set the stack index:

    self.0 = (self.0 & 0xfff8) | stack_index;
>Or alternatively:

    self.0 = (self.0 & (!0b111)) | stack_index;

    self.0 = ((self.0 >> 3) << 3) | stack_index;
>Well, none of these variants is really readable and it’s very easy to make mistakes somewhere. Therefore I created a BitField type with the following API:

    self.0.set_range(0..3, stack_index);
>I think it is much more readable, since we abstracted away all bit-masking details.

Personally, I disagree. Whilst it is easy to make mistakes when writing bit-fiddling code (there seems to be one in the second example, unless Rust has on of the more weird !-operators in programming languages), or any code for that matter, the meaning of all the bitwise operations is easy to recognise.

Without knowing the API, the transformed line rings no bells. How many APIs do you want to learn?

Ranges are used in a lot of places in Rust (over sequential collections, for example). Bit operations are used to engage with low level system APIs like this or for modular arithmetic, which is not common in Rust. As A Rust user, I absolutely know what a range is, and find the `set_range` function very intuitive. I have to drop into messing around with bitwise AND only rarely, and as someone who only wrote a small amount of C before Rust, it is always an exhausting effort.

And I find the bit manipulations easier to grok (then again, I know several different assembly languages and have been programming in C for years).

As for the bit ranges, it looks backwards to me, since bits are normally numbered high to low. I would find it easier to read if it read:

    self.0.set_range(3..0, stack_index);
I can "see" that much easier.

Well, Rust supports both bitwise manipulations and a range-based interface, so people from various backgrounds can use whichever they find more natural. :-)

Agreed, definitely should go high to low.

Yeah, it depends on personal taste. However, Ranges [1][2] are a core type of Rust and used pretty frequently, so it shouldn't be completely alien to Rust users…

[1]: https://doc.rust-lang.org/book/iterators.html [2]: https://doc.rust-lang.org/nightly/std/ops/struct.Range.html

My feeling is that the clearest way to do this would be:

    self.0.stack_index = stack_index;
using an appropriate packed struct/union type such that this makes sense.

This best represents what you're actually doing, instead of faffing around with bit twiddling to achieve the same result.

Does Rust not allow something like this?

This is indeed a rust failing. There are no untagged unions.

There should be. Obviously, unions with pointers are special. Some code might need to be marked unsafe. I suspect there is a subset of pointer-in-union operations that could be made safe, possibly either changing or using the pointer but not both.

Another thing missing is bifields. I'd love to see this done right, with adjustable packing so that one can use them to write an emulator or file parser.

Bitfields are in a crate, untagged unions are in the RFC process.

Crates and cargo look like trouble:

I'm not going to develop while connected to the internet. This is not allowed by any employer that cares about security.

I prefer to use the package manager that comes with my OS. Every other installer (firefox, nvidia crap, etc.) risks screwing things up.

Given the two things above, I hope you can see how much of a pain it would be to run some non-standard installer. I'd need to ask IT to mirror the rust cargo stuff... and is this even possible? Would I have to dig deep into the rust stuff to change a public key?

With it being a crate, I worry about it going unsupported. I've seen this all too often with firefox extensions. If not that, maybe somebody will come along and change the API.

I couldn't even find the crate. I found one called bitflags that does 1-bit fields. That isn't suitable. I'm looking for something that can handle stuff like an x86-64 descriptor table (GDT, LDT, IDT) entry or a PowerPC opcode. The PowerPC mtspr and bl instructions are interesting examples: mtspr has a 10-bit split bitfield, with a pair of 5-bit halves in the wrong order, and bl has a field that kind of has the low 2 bits stolen by other fields. The x86-64 descriptors have lots of strange-sized split fields and they are tagged unions for which the tag layout is hardware-defined. Another good one is page table entries, from the perspective of: emulator, hypervisor, OS.

With this not being part of the language proper, I have to wonder how well it performs. Has anybody compared the resulting assembly code?

  > I'm not going to develop while connected to the internet.
You don't have to. If you do use crates from crates.io, then you need to be connected the first time, to get everything. Not after that.

   > ... and is this even possible?
Running your own registry with your own universe of crates is very possible. Mirroring the external world inside that one is not that easy.

  > I couldn't even find the crate. ... that isn't suitable.
Well, multi-bit fields are made up of one-bit fields... if you're looking for GDT, LDT, IDT stuff, the crate referenced in the article already has all of that defined for you. If you want to define it yourself, well, I did it with a struct and a method that handles the bit shifting.

  > I have to wonder how well it performs.
Well, Rust is itself implemented in Rust, the standard library is all in Rust, so.

Also, finally, you don't have to use crates.io to use Cargo. You can just specify crates that are on your local filesystem, or a git repository hosted anywhere.

I was just about to post this exact same thing. Now there's an introduction of ranges and another API that is necessary to understand in order to grok this code. Bit twiddling, ANDing, and ORing are specific and absolute.

For example, what happens when I specify a range of 0..100 for a 32 bit int? what if the value is too big for the range? APIs around small operations like this introduce ambiguity that wasn't present before.

>Bit twiddling, ANDing, and ORing are specific and absolute

So what? You could implement addition using bitwise operators, but it makes for much more readable and less error-prone code to abstract it into an addition operator. Code should clearly express intent, and if your intent is to set, say, bits 5 though 9 of some register to some value, the clearest expression of that is something like (given a right-open range convention, which is well-established in this particular language):

    register.set_bits(5..10, value);
If I look at the above statement, I know what the author of the code intended it to do and can rely on (or manually verify once) the correctness of the implementation of "set_bits." If instead I'm reading code like

    register = (register & 0xFC1F) | (value << 5);
I have to work out in my head what the bit fiddling is doing, and from that guess what the author meant the code to do. I can't know whether he or she made a mistake in translating the intent to bitwise operations (say I know from context that value is less than 8; did they really mean to clear bits 8 and 9?), because the intent isn't expressed anywhere.

>For example, what happens when I specify a range of 0..100 for a 32 bit int?

What happens is that you've violated a precondition of the API. Because this is Rust, I would expect the operation to be implemented in such a way as to panic (in debug mode), or just fail to compile, since selecting a bit range like this at run time is extremely uncommon.

>what if the value is too big for the range?

Same thing as if you weren't using the abstraction around the bitwise operators: either you'd clobber higher bits, or the implementation would truncate the value.

Again, though, I would expect a debug-mode panic.

>APIs around small operations like this introduce ambiguity that wasn't present before.

I'm not sure what "ambiguity" you see here. There's the issue of whether the range is right-open or -closed, but again right-open ranges are well-established in Rust.

A range of 0..100 could be a static error. There's nothing fundamentally ambiguous about the technique, eg you can shift by 100 already.

Every other project comes up with its own wrapper for bit wise operations. Its not that big a piece of code to find and understand. Its a matter of taste. The first one is the canonical form (in C) and the only error source is the hex.

! is both bitwise and boolean negation, depending on the type (bool vs some numeric)

>Personally, I disagree. Whilst it is easy to make mistakes while writing bit-fiddling code

Luckily Rust gives you the #[test] directive so the next line after abstracting away the bit-flipping details you can provide it works correctly.

I've been following this series of articles. As a total beginner in the field, I found it to be a quite approachable introduction and learned a lot reading it. Thank you !

Thanks :)

Is it actually 100% necessary to hand-craft assembly for bootstrapping the OS?

I suppose it could be that it's simpler to write it out in assembly, since the C (/etc) code would look basically the same - just a lot of assigning cryptic variables to cryptic pointers?

Or, based on a quick Google search (http://stackoverflow.com/questions/3022046/is-it-possible-to...), is it because you cannot write to these registers from C, thus needing to drop down to assembly?

As others have mentioned, you need assembly operations to access hardware specific control registers. However, most system languages have some kind of inline assembly, which can be used to encapsulate those operations into e.g. a C or Rust function. So you could eliminate a large portion of the bootstrap assembly and rewrite it in Rust.

The problem is that we're in 32-bit mode at the beginning. So we would need two Rust libraries, one for the bootstrap 32-bit code and one for the 64-bit kernel code. We would need to link them together somehow or use GRUB modules. Doing it in assembly was somehow simpler and more fun :)

So let's assume you wanted to create an OS with a minimal amount of assembly: The minimum requirement of all higher level languages is at least a valid stack pointer. On x86, you need to initialize the stack pointer explicitely through a `mov esp, 0x{stack_pointer}`. It might be possible to do it in a naked Rust function [1]. As soon as you have set up a stack, you can directly call into Rust or C code (see [2]).

It's easier on ARM Cortex-M boards, since the stack pointer is loaded from address 0 on reset. So you can boot directly into Rust, without any assembly file (see [3], especially the `common.ld` linker script).

[1]: https://github.com/rust-lang/rfcs/pull/1201

[2]: http://wiki.osdev.org/Bare_Bones

[3]: https://github.com/japaric/cu

It generally doesn't matter how the machine code came to be. It is theoretically possible to write an operating system for (say) x86 in (say) Javascript. The reason people generally pick a "systems" language and drop down to assembly when necessary is due to two broad reasons:

1. As you'd pointed out, the language in question might not let you generate certain instructions. For instance how do you express LGDT in C? You can't. You'd instead write it in assembly (or inline assembly) and expose it to the C world as a function (or in a compiler that supports it, an intrinsic) that it can call.

2. A CPU's understanding of state is defined around the notion of registers and memory. A programming language however exposes a higher level abstraction. For instance, a function call in C is an abstraction that defines both transfer of control (which the CPU knows about) and persistence of local state (saving and restoring registers, stack pointer etc., which the CPU knows nothing about). This is called the ABI and is merely a previously agreed upon convention. Higher level languages (say Java) are able to provide richer abstractions than merely an ABI as their "agreed upon conventions" are defined at a much higher level than in terms of a CPU (registers and memory). Java, for instance even defines a virtual architecture in terms of which facilities offered in the language are defined. User code written in one of these higher level languages depends on these facilities being available to them at any time. This is what makes it unsuitable for writing certain sections of OS code. For instance, the CPU expects the OS to save and restore register state around an interrupt handler. If said handler was written in C (as a function) though, it'd expect its first six arguments in certain registers etc. - conventions, the CPU knows nothing about. You can think of the CPU as exposing its own, simple ABI which can only be implemented by writing certain sections of code in assembly (This is not entirely true though, as one might be able to mimic something like this in certain compilers, especially C compilers, that let the programmer write "naked" function bodies and custom prolog / epilog code). This is also why most parts of the OS, that don't directly interact with the CPU, can and are written in a higher level language. For e.g. The Singularity OS by MSR was written in C# and assembly.

Isn't the LGDT just an address though? You provide a starting address and a length offset that's it. Why can't that be expressed in C? Does it live in a register not visible to the compiler?

You mentioned: "For instance, a function call in C is an abstraction that defines both transfer of control (which the CPU knows about) and persistence of local state (saving and restoring registers, stack pointer etc., which the CPU knows nothing about). "

Doesn't the CPU know about this "persistence of local state"? I mean it pushing and popping that state form the stack right? I'm curious what you mean there.

What's a "naked function" in this context? I think of naked function as one that doesn't have a return statement.


LGDT is an instruction that Loads the Global Descriptor Table [1].

The CPU doesn't know about the persistence of local state in that it doesn't know (in this case), the significance of anything that is being pushed onto / restored from a frame around a call. It knows that a "PUSH R9" writes the value of R9 onto the region in the stack being currently pointed to by the stack pointer (RSP). It however doesn't know that this is being done because, the current frame has a live value in R9, which, per the ABI, the function being called is allowed to trash, as it is considered a volatile, callee saved register. Like I'd said earlier, these are just agreed upon conventions that might even change across compilers.

I'd used the term "naked" the way the VC++ compiler uses it. A "naked" function is one without a prolog or an epilog [2].

[1] https://pdos.csail.mit.edu/6.828/2008/readings/i386/LGDT.htm

[2] https://msdn.microsoft.com/en-us/library/21d5kd3a.aspx

I see, that makes sense. Thanks for the clarification and the links!

No, LGDT is actually an instruction (like MOV or ADD). You'll be hard-pressed to get a C compiler to emit that without using inline assembly.



Yes, on x86 at least. There are special data structures that can only be initialized with special instructions, which you can't generate with normal C because they aren't useful for anything but initializing those special data structures.

I personally would say yes, it is 100% necessary to write assembly for bootstrapping the OS (at least on x86). It's almost entirely due to your third point--x86 has dedicated instructions which only exist to write to certain control registers, and these, somewhere down the stack, need to be written in assembly. C, and pretty much any other multi-architecture programming language, just isn't going to include architecture-specific control register manipulations in its freestanding library.

IMO a bigger issue is that most of these kernel entries have unusual calling conventions. Exception handlers need to preserve all registers, for example. On x86_64, it's more complicated due to GSBASE handling. (Linux had it subtly wrong literally forever. OpenBSD still had it wrong last time I checked, but other hardening measures seem to make it impossible to exploit.

SYSCALL is even worse -- when the handler is invoked, there isn't even a stack.

I'm not familiar with the term GSBASE, could you explain?

I looked it up - segmentation in long mode. I'm curious how both Linux and BSD had/have gotten it "wrong" for so long? That just sounds unusual and likely not an oversight. Can you elaborate?

It's not segmentation. It's effectively just one extra register usable only for address offsets.

Unfortunately, on x86, privilege transitions and exception handling is an incoherent mess, and, worse, privilege changes (via IRET) can fail. Most kernels messed up what happens when IRET fails for obscure reasons, resulting in corrupting the value of GSBASE and therefore allowing a malicious program to change the targets of certain kernel memory accesses.

The result was "BadIRET", which I discovered, fixed on Linux, and reported via CERT (not a good experience) to other vendors. Someone else named it, and a few other people wrote exploits based on it.

This is interesting, but it's not the hard part of exception handling. The next step is doing something to the state of the process that got the exception. If the exception comes from a userspace process, that's OK, because those processes aren't part of the Rust OS. But if the exception comes from kernel code, there's a problem. Rust code has to mess with the internal state of Rust code.

Signals have the same issue in ordinary Rust programs. See [1]. What's the state of the Rust world when you're in a signal handler?

[1] https://github.com/rust-lang/rust/issues/11203

That's a two year old, closed, issue, from when rust had a runtime, probably doesn't apply anymore.

I don't think signal handlers are a big deal because global mutable state in rust is rare; and when it exists it probably is immune to the issues -- global mutable state in rust is required to be thread safe (since rust doesn't know if you are using threads), which should make it signal -safe too.

Not sure what you mean, doesn't Rust have a runtime now?

Everything has a runtime, except perhaps hand-rolled assembly. Rust today has a C-like runtime, which is bare minimum and makes it possible to FFI easily. For the most part you can pretend it doesn't exist; it doesn't affect programs.

In the past, Rust did have a bulkier runtime with a green thread scheduler and libuv; a runtime that "mattered".

It has a runtime comparable to C. Back in those days, it had a much larger one.

Ok, that's what I thought : )

It interesting that they stripped down the runtime from previous(larger) iterations. Are those discussion discussed anywhere that you know about? It seems like that would be an interesting read.

https://github.com/rust-lang/rfcs/blob/master/text/0230-remo... and the PR/issue linked there.

There are also old mailing list discussions on rust-dev somewhere which discuss this IIRC.

Woww thus informative

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