I've said it again and again: To teach is to lie.
I'll simplify things. A lot.
Not that the details aren't interesting, but if I start throwing around PTEs, PFNs, page faults, kernel internals and CPU privileges from the beginning, nobody is going to read this.
Worry slightly, though. I'll throw some stuff your way. End of warning.
I Wanted a C project
I've been learning C for a while and I genuinely like it. I like it a lot. But I don't like the "just build a project!" approach to learning.
Build an app.
A website.
A to-do list.
A game or something that simplifies your life.
Yeah, that's not me. I'm not a programmer. I don't want to build an app and spend months adding features, fixing bugs and maintaining it. That's not me. To me, these kinds of projects are mood-killers.
What I do enjoy is understanding what the machine is actually doing. I want to use C to ask questions about the stuff I really want to understand.
And I've been having some success learning C and Assembly while also playing around with microcontrollers and lower-level concepts: memory, pointers, addresses, system calls, how OSes work, and so on.
A Memorable Idea?
I knew that a process doesn't deal directly with physical RAM addresses. It works with virtual addresses.
The CPU and OS cooperate to translate those virtual addresses into physical addresses. The OS sets up the mappings; the CPU's memory-management hardware uses them.
The details are considerably more interesting, but let's keep this mental picture for now:
Process --> Virtual Address --> Translation --> Physical Address
I also knew that, under certain conditions, the relationship between virtual and physical addresses could change.
The same virtual address could end up referring to a different physical page.
So, could I force those conditions? Can I make one of those addresses change?
Hey, isn't this a project of sorts?
I was hyped. And that's a good sign. If you are ecstatic about doing something that is useful for what you're studying, something you actually want to become good at, that's a good sign.
The Plan
I started by asking myself some questions and starting small:
- Can I get the PID of a process? Of course, easy.
- Can I allocate a page? Probably.
- Can I print the virtual address? Sure.
- Can I figure out which page that address belongs to?
- Can I find the corresponding physical page?
- Do I have enough privileges for anything related to the physical address?
And finally, when I know I can access all of this and print it to stdout:
- Can I make the relationship change while the process is still alive?
Oh, but for context mmap() in ASM was the touchstone that made me trip into this rabbit hole. I even considered building my whole project in ASM, but then briefly considered how much pain I was willing to accept. So C it was!
mmap()
If you haven't used it before, mmap() is a Linux/POSIX interface that lets a program create mappings in its virtual address space.
For my first experiment, I used it to create a mapping for a single 4096-byte page of memory. Remember that 4096 bytes in decimal is 0x1000 in hexadecimal.
This was important because 4096 bytes is also the page size I'm working with here.
A 4096-byte page needs 12 bits to identify any byte within it, because:
4096 = 2¹²
So, the lowest 12 bits of a virtual address tell us the offset within the page.
Everything above those 12 bits gives us the virtual page number.
Once we have the virtual page number, we can find the corresponding entry in pagemap.
There is one 64-bit entry in pagemap for each virtual page. So, to find the entry for our virtual page, we multiply the virtual page number by 8.
A pagemap entry consists of several pieces of information. I care here about the PFN, which tells me which physical page is backing the virtual page.
Then I wrote a value into that memory:
So far, nothing particularly exciting. Just moving along and gathering our LEGO bricks.
But now we had our program, a process, a virtual address, a page, and a value stored at that address.
I made the program request the user to press the Enter key. This way, it was kept alive.
But where is that page actually sitting in physical memory?
Linux provides an interesting interface for this:
/proc/<PID>/pagemap
This is a kernel-provided interface that lets a userspace program inspect information about a process's page mappings.
In particular, a pagemap entry can contain the Page Frame Number (PFN), corresponding to a virtual page.
And, from here, the physical address is fairly straightforward:
Physical Address = PFN x page size + page offset
So, now I had all the bricks that I needed.
I also learned that you needed the appropriate privileges to actually access the pagemap.
Root isn't necessarily equivalent to having every Linux capability. On my system, I needed the privileges associated with CAP_SYS_ADMIN to obtain the PFN information from pagemap.
And that gave me another little rabbit hole: being root and having a particular Linux capability aren't quite the same thing.
Experiment A (first steps) or, as Ilike to call it: To Sudo or Not to Sudo
The Experiments
I called these the experiments. Gathering all the tools I needed was Experiment A. I now wanted to jump into Experiment B, where I'd try to change the physical address.
I knew one cheaty way to do it.
I knew about Copy-On-Write (COW). I'd recently been reading about COW in another context, including some security research involving COW-related behaviour.
So this seemed like a natural place to start.
The basic idea behind COW is pretty simple to understand:
Suppose a process has a page containing some data. Now we create a child process with fork() - see here.
The child gets its own process and its own virtual address space.
But, for the moment, the kernel has no need to immediately make a complete physical copy of every page.
Instead, parent and child can initially refer to the same physical page.
The mappings are made effectively read-only (this is important) and the system keeps track of the fact that the page can be copied if someone tries to modify it.
Experiment B
Why 666? Because Gilfoyle is my spirit animal
Now, my child process did the following:
*(int *)addr = 666;
The CPU detects that the attempted write isn't permitted by the current page-table entry and raises a page fault.
Now, before you start thinking segfault, nope.
A page fault does not automatically mean something has gone wrong.
A page fault is a mechanism, and the kernel can handle it.
In this case, it recognizes that this is a legitimate COW situation, creates a new physical page for the child, copies the contents, changes the child's mapping, and allows the write to continue.
And, voilà! Same virtual address in two processes, different physical addresses.
So, slight cheating, but not entirely.
Also, see the weird thing there? Maybe you don't. Compare it against my running that exact same program a second time. See it now? Both processes are writing to stdout and we cannot predict which one will print which line first.
For a moment, I was baffled by this, but then I remembered what fork() actually does. It's not instructing the child to run after the parent runs. It means:
There are now two concurrent processes capable of running. Run them.
The scheduler decides when each gets CPU time.
So, voilà! an accidental demonstration of concurrency. You're welcome. It wasn't planned.
As for concurrency, that's another rabbit hole. Rabbit holes everywhere you look. Reminds me of math classes and the Real line. My professor used to draw rabbit holes there all the time. Fun, fun, fun.
Experiment C
Single process, same physical page, two different virtual addresses.
I now wanted to remove fork() from the equation.
This required a different approach, and I used a POSIX shared-memory object and mapped it twice into the same process.
Think of the shared-memory object as the thing being mapped. The mapping itself isn't the memory.
I asked Linux to map the same object twice.
So, now Linux could give me two different virtual addresses while both mappings referred to the same physical page.
Note: it is not a given that the two addresses will be adjacent.
I could inspect both virtual pages through /proc/<PID>/pagemap, once more and check that the PFN was the same and, therefore, the same physical page.
The Issue
I had technically answered part of my original question, but I had used fork(). What if I didn't?
Could I get a single process, keep the same virtual address, and somehow make Linux replace the physical page underneath it?
That became the next question.
And this is where the project is currently sitting.
I already received a very interesting suggestion for how to approach it, involving madvise() and memory pressure.
I haven't properly investigated it yet, so I'm not going to pretend I understand it well enough to explain that here.
That's the next rabbit hole, and one you might want to trip into yourself. All quite accidentally, of course.
Yup, I'm a cute little sunrise.
I started this little field trip because I wanted to learn C and understand virtual memory better. And, along the way, I got to touch on:
- mmap()
- pointers and pointer casts
- virtual pages and page offsets
- PFNs
- /proc/<PID>/pagemap
- Linux capabilities
- COW
- page faults
- shared memory
- multiple virtual mappings
- process IDs
- scheduling and concurrent processes
- ...
If anyone reads this and is interested in its innards, here's my Github. Mind the step, not the mess.
The code is deliberately small, and certainly not a production-quality memory inspection tool.
It's an experiment. Or a series of them, actually.
Something you can compile yourself, run, modify, break, and have fun with.
One last thing:
The little snippets of these experiments that I posted on LinkedIn were well received. People have suggested alternative experiments, pointed out things I wasn't considering, asked interesting questions which themselves gave me ideas of stuff to try.
That's been rather nice.
I don't pretend to be an expert in any of these things. Quite the contrary. So I'm humbled and grateful when those that know more than I do chime in and give their input.
I was going to say keep digging, but that's not necessary. Just accidentally trip into any of the rabbit holes that are all around us. And be perpetually amazed as you fall deeper and deeper.
No comments:
Post a Comment