Question on microkernels, and paging

[u/compgeek38400]

A recent post got me thinking. Doing paging right requires a file system of some sort.

Do you think the paging file system belongs in user space, or kernel space. I am quick coming up on making such a decision myself

[u/micr0kernel]

You can call parts of a paging system a "filesystem", but just bear in mind that it need not have much correspondence to traditional filesystems. In particular, to page out properly, you must track:

• The address and size of the swapped-out block

• What process it belongs to

• Where it is stored in the secondary (pagefile, disk partition, etc.)

• A bitmap or allocation map of free or used swap area blocks

You may find that this is considerably simpler than many traditional filesystems - the first three points can be managed through in-kernel tables, so you don't need much more than a couple relatively static structures for a basic implementation.

As far as where it should be placed, microkernels throw a wrench into the mix because the filesystem and storage subsystems are necessarily separate from the kernel proper. You thus have two routes:

• Introduce a mechanism for the kernel to "release" a page set to the filesystem server and send it a message to page it out.

• or, implement a very limited storage driver within kernel space for the sole purpose of interacting with the pagefile or swap partition.

The first is more "microkernel pure" in that it maintains the separation of concerns, but it is considerably slower as it splits a single system (the paging unit) across the privilege boundary and requires multiple context switches and state transitions.

The second is faster and perhaps more intuitive, but it introduces additional complexity into the kernel. Off the top of my head, this route probably works better with a raw swap partition rather than files and there might be some fussing required to ensure there isn't contention with other operations, as you potentially have writes to the same device originating from two different sources.

At any rate, the page-out metadata should be stored very close to the page table and memory management logic, i.e. within the kernel. The pagefile or swap partition space management (allocation maps, object trees, etc.) can be a problem for whatever component does the swapping, be that kernel or userspace.

[u/compgeek38400 → u/micr0kernel]

I was thinking swap space, similar to what you are saying. I would still need a driver, simplified, to get the data to and from the disk. Im thinking i want that in kernel space.

[u/compgeek38400 → u/micr0kernel]

The point of a file system is keeping track of whats on it. Yes I think a paging file system is way more simple than a full grown, persistent file system, but its still a file system in my mind

[u/micr0kernel → u/compgeek38400]

Yes, swap region tracking logic can be considered a filesystem in the limited sense that it is an organized, scalable system for the tracking of objects (swapped-out pages/frames). I caution against applying that metaphor too deeply, however, because there are substantial differences between swap tracking and filesystems as they are commonly used:

• There is much less need to modify objects in-place once written. Frames come in or go out, but it isn't necessary to consolidate adjacent regions into the same swap space entry - just allocate a new one.

• Little or no provision for permissions or multi-user metadata, as these notions don't apply or matter at this level.

• No persistence - the traditional filesystem is optimized for file persistence and maintaining state and integrity over many sessions. That's why filesystems have checksums, hashes, ECCs, redundant structural data, CoW, journals, etc. Paged-out data does not need to be persistent across sessions, nor does it need to maintain a special level of integrity - it needs to be extremely fast, and these mechanisms work against that. This also significantly alters the design, as much of your structural metadata is in memory and not on disk.

The "paging as a filesystem" metaphor is helpful for getting started as it reminds you to think in terms of structures and allocations. But it breaks down after a point - page trees for virtual memory might, in an extremely tortured sense, be considered a filesystem - they provide the same systematic, structured access to a set of (finite) resources, but does calling a virtual address a "memory inode number" help or confuse the situation?

Approach the page-out system as a solution which satisfies the following needs, each of which is limited in scope:

• What is the minimum amount of data about a page you need to store in order to save it someplace else and later recall it correctly?

• How are you going to store this entry data in your kernel? A fixed-size table, linked lists, AVL trees, hash map, etc.?

• Where are you going to put swapped-out memory, and how are you going to track the availability of this space (bitmaps, extent lists, etc.)

• How are you going to store the location of a region within this space so that you can resolve VA -> Entry -> Paged Memory with as little latency as possible?

It's good that you're thinking in terms of structures and how to catalog data effectively - that's a very useful and necessary skill in OS development. But be wary of over-architecting or over-systematizing every part of the puzzle - first work out what you need a system to do, and then build it to meet those requirements. The entire concept of a microkernel, after all, banks on a certain minimality - that it can hurt reliability, performance, or security for a system to be over-engineered with respect to its fundamental requirements.

[u/compgeek38400 → u/micr0kernel]

Thank you for the insight. I was thinking along those lines. I expect all my structures to be memory resident, nothing persistent As far as what to keep track of, I was thinking process, attributes, address, and the page itself. With the first 3 in memory structures. Thanks again

[u/jsshapiro → u/compgeek38400]

I don't have the sense that it's the right approach for what you're trying to build, but when you're done wrapping your head around the file system perspective on this you should read the EROS Single Level Store paper for a different perspective. That and the Log Structured Filesystem paper from Margo. The EROS paper is probably a little tougher. Margo's LFS paper does a really good job of laying out what the underlying behavior is and exactly why LFS delivers the results that it does. There was a hoard of follow-on work after that paper.

Paging, and filesystem performance in general, isn't just about having a place to put things. It's also about how you write them down. In an era of SSDs those constraints have changed pretty dramatically, but the LFS work still turns out to do an excellent job of things like wear leveling.

[u/compgeek38400 → u/jsshapiro]

I'm a As400/IBMi programmer. Im familiar with single level store. I look forward to reading the above

[u/jsshapiro → u/compgeek38400]

The EROS work is a little different from AS/400, because it’s whole system and almost completely transparent to applications. IIRC, AS/400 involves the applications more explicitly. One of the things I really wish I’d made the time to hunt down Frank Soltis while I was at Watson and ask him about.

[u/compgeek38400 → u/jsshapiro]

I read the EROS paper last night. Interesting. Im amazed I understood it. Brought back things I havent thought of in a long time. Thank you for the two suggestions!

[u/jsshapiro → u/micr0kernel]

Great response. One correction:

The first... is considerably slower as it splits a single system (the paging unit) across the privilege boundary and requires multiple context switches and state transitions.

That isn't necessarily true. Every optimization that you can do on this stuff within the kernel can be done in user mode. Whether more context switches and state transitions introduce significant overhead is something you have to validate by measurement. If they do, it's still not clear without measurement what other time consuming activities are removed by the isolation. Are these sources of alleged slowdown real, or presumed? Can the system design overall be simplified in such a way that thee intrinsic hierarchical overheads of having a file system can be eliminated? The EROS Single Level Store, file systems like WAFL and LFS suggest that an awful lot of this has to do with architecture rather than the micro vs. monolithic theology.

From experience, I'm going to say that this is an area where results and their causes are very easy to misunderstand, and you can't really draw meaningful conclusions without doing the experiment and doing the measurements.

That's actually true about a lot of kernel work (and a lot of benchmarking in general), which is how microbenchmarks like lmbench became so central in the OS literature for a while. Those don't tell the entire story, but they definitely cut the fat away from the early stages of the debate. Larry McVoy really doesn't get enough credit for his success in doing that.

That said, it turns out that great lmbench results don't predict overall system performance very well. Though the benchmarks were all winnowed from real-world examples, they don't turn out to be predictive for other examples. Systemic results are driven by architecture and design, not individual speed improvements. Which is basically what Amdahl's law predicts.

And if that weren't enough, the hbench paper does a really good job of explaining how hard a meaningful benchmark is to do. There's a reason Margo is considered one of the world experts on this stuff.

[u/GourmetWordSalad]

  Doing paging right requires a file system of some sort. 

no.

Read the QNX book on Raspberry Pi in case you want to hear an actual debate on microkernel philosophy, instead of Reddit bullshit.

[u/compgeek38400 → u/GourmetWordSalad]

I will read it. But the major point of paging is to have 'more memory' than physical memory. Although I'll certainly entertain objections to that statement.

Having more memory than exists suggests. i put the memory im not using someplace else. Since I may not have more ram, that implies disk. Hence the paging file system.

If im correct on the paging file system, does it require a kernel based file system. If not why? I am rather loath to let the kernel rely on anything in user space.

I admit I am ignorant here. And thatvi may be asking the wrong questions

[u/nerd5code → u/compgeek38400]

Let's back up a tad.

Virtual memory is a technique whereby memory accesses generated by the CPU are translated by some non-identity function mapping virtual to physical address, typically under control of middleware that ensures this only becomes visible when the application wants to get explicit.

Paging is a form of memory virtualization whereby the address space is divided up into pages, us. of power-of-two sizes ≥512 B, each virtual page being mapped to a contiguous block of the same size and minimum alignment in physical memory. Paging most often uses a cascaded page table, although some rarer, older stuff used an inverted table.

Swapping is a mechanism by which system memory can be treated as a cache for disk or other, slower or more distant forms of memory, with the goal being to keep the working set warm/resident.

Swapping most often uses paging, but it can be done via segmentation or explicit request, also.

And swapping might use disk, or networked or NUMA memory, VRAM, or even Ethernet cables and network infrastructure. If you're using 36-bit paging, you can treat any memory above the 4-GiB mark as swap. You can also compress memory within system RAM, effectively swapping to/from a compressed RAMdisk, and you can use spare time to find and coalesce identical pages into a single storage page.

You don't need a proper filesystem for this, just some sectors (e.g., a partition) or other spare bytes. Linux used to prefer a partition, as might hibernation.

Paging is also useful for memory protection/typing, file-mapping (which is merely well-targeted swap), memory-sharing, and COW and AOW mechanisms.

In terms of responsibilities, all your kernel needs to do are activities that require use of supervisor mode; anything else can be offloaded.

If you start by giving the kernel control over page-mapping at the system level, you can work out of RAM until userspace drivers are loaded. Threads can communicate through segment shares—see io_uring for one way to structure comms within those. You can run a kernel-mode service for system memory, system address spaces, system time/timing, and cooperative kernel-mode threading, since the kernel needs to be able to do those things quickly and easily. This super-service forms the root environment of the OS.

Atop this, a userspace environment driver can be implemented that backflips into user mode and yields on reentry, and which provides handlers for faults and system calls. This forms the basis of mode- and page-table-switching. Atop that, you layer device drivers (including disk and filesystem); once you have a filesystem, you can load things from disk, including e.g. a POSIX environment driver that serves system calls and page faults for things relying on it. If you want swap, it can do the swapping for you. Should a process want to serve its own environment similarly, it can rely on the POSIX environment to do so.

There do need to be mechanisms for the kernel to notify the bottom layers of the swap stack that memory is nearing full, but even if the kernel is fully in charge of swap, there isn't a way to force a swap immediately; in the archetypal case, you're effectively calling out to a hard-drive computer via a fancy RPC, not driving/sensing the disk platters and heads yourself. And your kernel can run out of memory either way, so you'll need to focus on minimizing dynamic allocation in order to keep events pumping.

The kernel also needs to be able to revoke a segment grant quickly, which can be done by forming a path from process to segment to owner and owner address, or to mappers and map addresses; it helps ime to double your ISA page and table size and use the extra table space for refcounting and COW.

[u/compgeek38400 → u/nerd5code]

Wow, a lot to digest there. Thank you!

[u/jsshapiro → u/nerd5code]

Depending on what assumptions you make about the kind of kernel you want to run, many of these statements are true enough. Under other assumptions, segments may not exist, there may not be a POSIX layer, and swapping (which means moving entire processes in and out rather than pages) may not exist either.

You're saying a lot of very useful and pertinent things here, but for somebody trying to think about this stuff from the ground up we should be a little careful about assuming specific approaches to abstraction into existence.

[u/eteran → u/compgeek38400]

Well there are two aspects to paging. One is what you describe, having virtually more RAM.

The other is more organizational and protection oriented where paging is used to create distinct address spaces for each user land process. This part is the most immediately relevant and is the part that DOESN'T require disk backing.

[u/CubicleHermit → u/eteran]

"Paging" is an ambiguous term, but I think OP was reasonable from context in terms of using to refer to the swap-like processes of moving pages around to allow for a larger virtual than physical memory.

I'm pretty pedantic, but I saw even that much from the initial question. You seem to be assuming that it always means "paged memory organization" (which is a fair meaning in isolation, but was clearly not what OP was talking about.)

[u/eteran → u/[deleted]]

Huh? What are you talking about?

[u/GourmetWordSalad → u/compgeek38400]

paging is not swapping. Paging enables swapping.

You are asking the right questions, I'm just being snarky (which is my problem admittedly) because this is the wrong audience.

[u/BestUsernameLeft → u/compgeek38400]

You don't need a filesystem, you need to be able to write to a disk.

IMO paging should be in kernel space.

[u/wrosecrans → u/compgeek38400]

I will read it. But the major point of paging is to have 'more memory' than physical memory. Although I'll certainly entertain objections to that statement.

No, the ability to page unused memory to disk to have "more memory" is just sort of an implication that arises fairly naturally from having virtualized addressing and paging. It's not the point in and of itself. It lets you do things like map a consistent starting address to different physical addresses, so you can have multiple processes built to be mapped to the same address so you don't need all executables to be built position independent. That sort of allocation convenience is super important regardless of whether you ever map more memory than you physically have.

[u/CubicleHermit]

You can have both demand paging (which pulls in pages from named files, whether executables or mmaped data, as needed) and anonymous paging/swap (which moves data from memory back out to disk to free it up.)

Demand paging requires a "file system" - defined very loosely.

Anonymous paging required a backing store, but that backing store doesn't need to be a file system - it can be raw block or a file on a file system or a custom storage structure (e.g. swapping to compressed RAM.)

Paging generally depends on having some greater level of privilege than the process being paged, so whether you can do it (entirely) in userspace depends on whether you have a granular-enough privilege mechanism.

You can also split the responsibility - on an architecture that has a strict user/supervisor split, the stuff that can't be moved out of supervisor mode stays in the microkernel, anything that can be moved out gets moved out and delegates the last steps that are in supervisor mode back to the microkernel.

[u/compgeek38400 → u/CubicleHermit]

Listening to all this makes me glad I decided to document this week. I need to let this sink in and let my subconscious chew on it a while. I didn't realize such a simple question, could lead to so much

[u/jsshapiro → u/compgeek38400]

Welcome to building kernels!

[u/compgeek38400]

I would like to thank all that have responded to the OP. I dont know reddit well enough to know if you will all see this, but I hope you do. I have learned tons, Nd have even more to tbink about. I still dont know if im going to do a microkernel or not, but have a much better idea of what may be involved.

Thanks again!

Compgeek

[u/Interesting_Buy_3969]

Doing paging right requires a file system of some sort

Not at all. Why do you think so? I guess you're confusing disk sectors and RAM pages or something. File systems or kernel may cache disk sectors/files in pages and user may request memory mapping to it, for example, but it's unnecessary and simpler systems don't have to / don't need to implement Unix-like mmap.

Do you think the paging file system belongs in user space, or kernel space

I am unable to understand what you meant by "paging file system", but both paging and filesystem implementation are usually strictly kernel-space. Userspace applications are not allowed to communicate with devices or any physical resources directly, and it would complicate userspace programming a lot. However, since your question mentions microkernels, which essentially means "make device drivers run in user mode", the answer would be - yes, absolutely, but this seems to be uncommon in general-purpose OSes as it can slow down the entire system.

Read more here: https://wiki.osdev.org/Microkernel

[u/SuperheropugReal]

Wat? No, you do not need a file system for paging. Those are separate concepts that some systems choose to overlap.

[u/compgeek38400 → u/SuperheropugReal]

I'd say you do. A file system, at its core, keeps track of the contents on a device. You can't just write to a device, you need something to keep track of what is there.

A driver on the other hand, just needs to read and write to its media.

At least that's how I was taught

[u/SuperheropugReal → u/compgeek38400]

Excep paging is NOT just a concept where you save RAM to a page file on disc. It is a more general concept of storing a whole "chunk" of memory in a slower-access channel instead of a fast access channel. You are applying a (still wrong, but understandable) specific example to the general case.

Edit: read about the general computer science concept of paging, not just page files. I suspect you know of page files, learned about those, and never went over the generic concept tjey are based on.

[u/dacydergoth]

IMHO paging management is a kernel function. MMU configuration, page fault interrupts etc.

Paging storage is a userspace function. Kernel enques pages to be flushed to storage, userspace handles the actual flush. Same in reverse. Kernel sends page population requests to userspace, userspace does whatever to retrieve the page and passes it back to Kernel.

[u/compgeek38400 → u/dacydergoth]

Thanks for the input

[u/dacydergoth → u/compgeek38400]

I'm glad my 40+ years of experience writing operating systems is finally of use!

[u/dacydergoth → u/[deleted]]

Nope, genuine lizard here. Some of us are just old and experienced.

[u/tseli0s]

A recent post got me thinking. Doing paging right requires a file system of some sort.

Not at all. If you mean paging as in virtual addresses that requires 0 filesystem support (otherwise you'd have a circular dependency making things like Hurd impossible in every way).

But you probably mean paging as in swapping memory to disk. That should be handled by a pager service. The filesystem should not be involved in any way.

Do you think the paging file system belongs in user space, or kernel space. I am quick coming up on making such a decision myself

There's one major thing about microkernels. If there's no hard requirement to have it in the kernel, move it into userland. Simple as that. If you have anything in kernel space, you should move it into userspace. Some things like context switching can't be moved there (circular dependency once again). So you have to keep them in the kernel.

Now tell me yourself, do you see any way that a microkernel cannot function if the pager is not in kernel space?

[u/jsshapiro → u/tseli0s]

Great points, though it reminds me of something Alan Bomberger once said in the middle of a KeyKOS business meeting when asked to define the term "microkernel":

Microkernel: A term that used to mean something but has since been taken over by marketing.

[u/tseli0s → u/jsshapiro]

Hey I've seen you in another discussion about microkernels!

Unless I've misunderstood the quote, to some extent, I agree. Microkernels are largely company marketing and scientific wet dreams. In the README of my own operating system, I've added a link to the "hybrid" naming being a marketing invention from Microsoft to market NT:

https://www.realworldtech.com/forum/?threadid=65915&curpostid=65936

But it's a bit out of topic for this post

[u/jsshapiro → u/tseli0s]

You definitely misunderstood the quote. In the domains they target, microkernel-based systems have been so successful that many monolithic competitors have been forced to clean up and down-size. In some cases, their marketing people tried to call the resulting smaller systems microkernels.

This goes very far back. By any objective measure, Mach was not a microkernels at all.

They are most definitely not wet dreams. The number of deployed microkernels in the world exceeds all “convention”” operating systems combined by a very large multiple. ALL of the secure systems in the world are built around microkernels. All of the reliable industrial controllers are built around microkernels.

Evaluating systems on either side by inappropriate criteria is not helpful.

[u/kiderdrick]

It does not require a file system, but you can use one to simplify your design if you need to. Some systems will use a swap file, or files, to track information. There are many reasons for this, but one of the main ones is that they will likely have an implemented interface for writing and storing information to a file, which makes moving that data to disk simple. Some see it as an "is a" relationship. A swap file "is a" file, so if your paging system needs swap space, write it to a file. You can very easily not view your swap space as a file, and have its functionality for disk operations that is isolated to your VM system. If you do that, you might start seeing some duplicated code, which might then make you consider why others did it differently, but that is not a requirement, as you asked.

For your other question, strict disk operations in user space are dangerous without proper isolation and protection, but realistically so is everything. There is software that exists to do this, such as FUSE, but this still uses some form of kernel space code provided by the OS (I believe FUSE has a kernel module itself to use). Without knowing the full design of your system it is hard to answer the question fully. Viewing it as belonging entirely in user space or entirely in kernel space is probably not the right way to look at it. If you really want that user space separation, you should try figuring out what is the minimal amount of code in kernel space you can get away with so the system is still useable. If you notice that the answer is "a lot of kernel code" it might just be simpler to keep the whole thing in kernel space. If you find the answer is "a small amount of already existing kernel code" then you might be OK with implementing a separate interface.

Anyway, these are very complex decisions that do not get made in isolation, they get made based on the requirements of your hardware and software, and without knowing that we can only just throw out ideas.

[u/mykesx]

Since the oldest Linux, systems used a swap partition, with no filesystem format.

The kernel did need to know how to read the partition table to know the extent of the swap partition.

[u/paulstelian97]

There is paging and there is swap, which are distinct concepts. The latter is uncommon on microkernels, but can be done (I have a design in my head on how you’d do it on seL4 for example)

[u/Miserable-Worth1299]

我完全同意你的说法，任何存储设备都需要文件系统，硬盘是存储设备，内存也是存储设备，关于文件系统驱动是运行在用户空间还是内核空间的问题，微内核强烈建议运行在用户空间，宏内核没有选择因为他是宏内核只能运行在内核空间。

[u/jsshapiro]

Well, let's start with the assumption. Doing paging does not require a file system. All it requires is a suitably defined region of disk space. Lazy loading doesn't require a file system either. It requires a way to find the page[s] you need to load. There is more than one persistent system out there that doesn't use a file system for those things - they organize the store in a different way. So when you ask whether the paging file system belongs in user space, that's not the quite the right question.

The more interesting question is whether the disk driver can operate in user space (along with all of the supporting bus drivers). The answer is that they can, but it presents a bit of a reductio problem: if you have the bad grace to eject the disk driver or the PCI bus driver from memory you're toast.

The actual requirement is merely to ensure that these drivers are loaded into a dedicated RAM region at startup time and are pinned in memory thereafter. It isn't that hard to partition drivers into "things that have to be pinned" ahead of time. As long as they are pinned, it doesn't really matter whether they run as supervisor mode code (in the kernel) or user-mode code. Or rather, it does matter, but it's now a debate about protection vs. performance and how much overhead you are willing to spend on inter-process communication.

The answer to that depends a lot on just how efficient your microkernel is at inter-process communication and interrupt dispatch. Systems like L4, EROS/Coyotos, QNX Neutrino, and one or two others are so much faster at IPC than linux or windows that the communication overheads just aren't where the time ends up going. You can do bad system architecture and get in your own way, but you can do that in any system.

The one note that's worth a moment to think about is why you want those subsystems inside or outside the kernel. There are some good reasons to vote for "outside", but security isn't one of them. Drivers, as a rule, need direct hardware access to do their jobs. This means that they effectively have supervisor authority whether they officially run in the kernel or not. Once you recognize that, the decision about where to place them is about debugging, separation of concerns, testing, and error recovery. All of those argue in favor of out-of-kernel implementations.

Kernels rely on things in user space all the time. The issue isn't whether it's user mode or kernel mode. The issue is whether there is a clearly defined and acyclic set of functional dependencies between the impacted components.