Introduction to Paging

[utterances-bot]

This is a general purpose comment thread for the “Introduction to Paging” post.

[boomshroom]

Great post as always!

In the diagrams for the multi-level paging, the level 2 table seems to be set to the 24K block, which is its own, but the level 1 table is set at the 32K block. I suspect this was just a typo.

[phil-opp]

Yeah, it was a typo. I fixed it a few minutes ago in f423c06. Thanks for reporting!

[FrankvdStam]

Very clear and thoroughly explained. Keep them coming!

[phil-opp]

@FrankvdStam Thanks a lot! The next post is already in progress.

[iddm]

Amazing. Refreshed my knowledge of memory, read almost the same in low-level-programming book by Igor Zhirkov, but information here is a bit more detailed, love that. Thanks everyone who was involved into writing this.

[phil-opp]

You're welcome, great to hear that!

[ruier]

Nice blog。I should like to thank the author for his time。

[iddm]

@phil-opp Are you working alone on it? I had read a few books about writing oses and their internals, I am a linux systems developer, have some knowledge on cpu and hardware.. Actually, it's difficult to mention all of areas I am interested in, I just wanted to say that I could help you writing something and you could review my efforts. Also, this book is somewhat similar to csbu (computer science from the bottom up) online book. I read it and translated first parts of it to russian. :)

[phil-opp]

@ruier Thanks! :)

@vityafx Yes, I'm working alone on it. Thanks for the offer, I'll keep you in mind if I need help! I didn't know csbu, looks interesting.

[goranmoomin]

Wow, great post! Found these blog series a week ago and following... It’s great! One thing I am curious: When does the blog post about boot loaders come? Thanks for the post :-)

[phil-opp]

@pcr910303 Thanks!

When does the blog post about boot loaders come?

I don't know yet… I want to port most of the assembly code of the bootloader to Rust before I write about it.

[goranmoomin]

@phil-opp I have a question about integration tests... Can there be a way to run integration tests integrated to cargo by putting integration tests in ~/tests/? I thought that a simple program that calls cargo and compiles binary and running in headless qemu mode would suffice, but based on what I tried, it looks like cargo tries to compile the whole crate(thus failing because of duplicate language items...) Do you know an alternative plan(eg. integrating boot image test to cargo test, excluding compiling in cargo test...etc)?

[phil-opp]

I don't know a way to do this since, as you say, the crate is always compiled for the host platform. cfg(test) does deliberately not work with integration tests, so we have no way to exclude the duplicate lang items. Maybe the custom test frameworks RFC will help, but it is still not implemented as far as I know.

[goranmoomin]

Ahh… That’s something cargo can do it better :-( I did fall across to the RFC, looking for that…. Wouldn’t there be any way to integrate `bootimage test` to `cargo test`?

…

2019. 1. 18. 오전 2:11, Philipp Oppermann ***@***.***> 작성: I don't know a way to do this since, as you say, the crate is always compiled for the host platform. cfg(test) does deliberately not work <https://github.com/rust-lang/rust/pull/38823/files> with integration tests, so we have no way to exclude the duplicate lang items. Maybe the custom test frameworks RFC <rust-lang/rust#50297> will help, but it is still not implemented as far as I know. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#519 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AkOxyi-5SLkNE11Zx2mbAaUwhxHVP8Jnks5vEK7MgaJpZM4Z_vDC>.

[phil-opp]

Not that I know.. I would like to integrate it too.

[deleteJ]

I do finish reading your post and a big thanks
feel good when learning

[phil-opp]

@deleteJ Great to hear that!

[hismito]

In Example Translation

Through the entry with index 127 of the level 1 table we finally find out that the page is mapped to frame 12KiB, or 0xc000 in hexadecimal.

The hex value should be 0x3000?

[phil-opp]

@hismito Good catch! Fixed in 0b971c9.

[mitnk]

In the description of "problem of a single page table", article says:

... imagine a program that uses the four virtual pages 0, 1_000_000,
1_000_050, and 1_000_100 ... It only needs 4 physical frames, but the
page table has over a million entries. ...

My confusion here is why the Page Table cannot use a Hash data structure
so that only needed number of entries (in this example, 4) to be saved?

Is it because:

(Pagin translation) is entirely done in hardware ...

So only array-like method can be used? (Hash like method is too complex for Hardwares?)

[phil-opp]

@mitnk Yes, one reason is that the hardware only supports array lookup. Other reasons are the unpredicability of hash map latency (it's only amortized O(1)), its worse lookup performance (array indexing requires less work than hashing + indexing), and the complexity of memory management (how much memory should be allocated for the hash table? how to grow its size without reallocating?).

[anlofw]

@mitnk @phil-opp
As a sidenote, there are (older?) platforms using hashed page tables. One example is the PowerPC 740/750 (for which I'm currently implementing paging). For this platform you decide on a size of the table and there are two hash functions used to point to a group (eight) entries. If the first group is full you use the second hash function. If the second group is full, you have to replace (or ignore) an entry when populating the page table. If an entry is not found in the table during lookup (which is performed in hardware checking all eight entries in the group in parallel), an exception is generated and the OS can insert a page table entry if the access was valid.

[phil-opp]

@anlofw Interesting, I didn't know that!

It's probably also worth mentioning that there are also architectures (e.g. MIPS) that allow/require you to implement page translation in software. You get an exception for any virtual address that is not available in the TLB and then have to perform the translation yourself, using a data structure of your choice.

[anlofw]

@phil-opp True, there are a few PowerPCs using that approach too. I'm working with a few of those as well.

[chrisbroome]

Not really able to test that reading from the code segment works. I think maybe one of my packages has changed since the post was written. Looks like my CS (your value is 8) and SS (your value is 0) aren't ever initialized like they are in your example.

When writing, it causes a page fault like you would expect:

let ptr = 0xdeadbeef as *mut u32;
unsafe { *ptr = 42; }

EXCEPTION: PAGE FAULT
Accessed Address: VirtAddr(0xdeadbeef)
Error Code: CAUSED_BY_WRITE
InterruptStackFrame {
    instruction_pointer: VirtAddr(
        0x8d480000002a00c7,
    ),
    code_segment: 10180386957689365692,
    cpu_flags: 0x1ba00020dec35,
    stack_pointer: VirtAddr(
        0xffb6f80d8d480000,
    ),
    stack_segment: 3380163216087724543,
}

But notice how my CS and SS aren't initialized and my IP VirtAddr is pretty high. I tried reading from just the lower 32 bits (0x2a00c7) but that didn't work either.

Any thoughts? Right now I'm thinking that maybe there a bug in my gdt.rs somewhere.

[chrisbroome]

AHA! I found the issue - and the compiler was telling me what was wrong the whole time!

warning: use of deprecated associated function x86_64::structures::idt::Entry::<for<'r> extern "x86-interrupt" fn(&'r mut x86_64::structures::idt::InterruptStackFrame)>::set_handler_fn: Taking the InterruptStackFrame by reference no longer works on latest Rust nightlies. Please update to x86_64 v0.14.0.

So it looks like the latest run nightlies broke mutable references to the stack frame. No worries. I updated to x86_64 = v0.14.0 and then (as expected) got these errors:

expected struct `InterruptStackFrame`, found `&mut InterruptStackFrame

Well of course, that's the entire reason we had to update to v0.14.0 in the first place. So the solution - as the compiler already told me - was to change the first parameter of each interrupt handler from &mut InterruptStackFrame to InterruptStackFrame. Now I get the right selectors in my PAGE FAULT output!

I was also able to test that reading from the code page worked fine (I got the Read Worked!) message.

And finally, writing to the code page triggered the proper PAGE FAULT exception also:

EXCEPTION: PAGE FAULT
Accessed Address: VirtAddr(0x204ac7)
Error Code: PROTECTION_VIOLATION | CAUSED_BY_WRITE
InterruptStackFrame {
    instruction_pointer: VirtAddr(
        0x204b99,
    ),
    code_segment: 8,
    cpu_flags: 0x202,
    stack_pointer: VirtAddr(
        0x10000201d70,
    ),
    stack_segment: 0,
}

[GrubbyHalo]

It only needs 4 physical frames, but the page table has over a million entries. We can’t omit the empty entries because then the CPU would no longer be able to jump directly to the correct entry in the translation process (e.g., it is no longer guaranteed that the fourth page uses the fourth entry).

The page table in this example 0 - 1_000_150 only has 20_003 entries and not a million ? or am I missing something ? Great tutorial btw.

[wmarais]

This bit is weirdly written, but I think this is in context to a being able to address all the available memory in a 32 bit address space. Basically 2^32 = 4GB, so for a page size of 4kB, you need 4GB/4kB = 1 Million Entries. If you then want a single array that you will not resize etc as the process executes, you need to have 1 Million entries available in the page table. I think the key here is a fixed page table size. Using a multilevel page table, you effectively have resizing in 1k entry chunks.

[Bridiro]

I have a problem that I can't figure out. When I run the OS with the code for accessing the memory outside the kernel, so let ptr = 0xdeadbeaf as *mut u32 it paniks saying: paniked at 'misaligned pointer derederence: address must be a multiple of 0x4 but is 0xdeadbeaf', src/main.rs:18:14.

I even tought I forgot something so I opened all the files but everying was ok. The last thing I did was downloading the entire project for this post and copying all the .rs files and the Cargo.toml in my project, but the result is the same.

Can someone explaing what's happening?

[cubed-guy]

#1215 provides a workaround

[yijun-tang]

I hated that I saw this series of articles so late!!!

[Mrgoblings]

Amazing! Life changing. I tried to do it in assembly 😭