Wandering Thoughts archives

The kernel memory addressing problem

One of the engineering issues in writing an operating system kernel is how your kernel gets access to physical memory. This requires some explanation, since on the surface you might think that this is easy; after all, the kernel runs with full access to the machine so how could it have problems accessing memory?

The simple answer is that today's kernels almost always run with virtual memory, not just for user processes but for themselves as well. Although they run with full privileges, kernels still have a virtual address space and (kernel) page tables that map the virtual addresses that the kernel uses into real physical addresses (both for RAM and for memory-mapped devices). This may be required by the CPU (once you turn on virtual memory it may always use page tables) and even if it's not, it's almost always more convenient (for example, the kernel code doesn't have to be relocated depending on what physical address it was loaded at). Once the kernel is using virtual addresses, you get the question of how to map physical memory to (or into) the kernel's virtual address space.

I am not going to try to provide a complete inventory of the different techniques that have historically been used, but there are two general extremes. The easiest situation is if your kernel address space is large enough to include all of the physical memory and address space of the machine with room left over. This allows you to simply establish a direct linear mapping for all of physical memory and often it will let you use huge pages (page table entries that map large amounts of contiguous physical memory in a single entry).

(You need extra room because you need some amount of virtual address space for things like the kernel code and data itself, since you want these to be at a constant spot.)

The polar opposite of this is to explicitly map chunks of physical memory into the kernel address space as you need them and then unmap them afterwards. This generally creates a kernel interface that looks something like mmap(), because this is basically what you're doing. The obvious drawback of this approach is that kernel code has to explicitly manage these mappings, especially removing them when it doesn't need them any more (otherwise you 'leak' kernel address space). However, if you don't have enough (kernel) address space you don't really have any choice.

There are a number of things that make an explicit mapping approach less painful:

• when the kernel is getting (and releasing) memory for its own use, you generally need a memory allocator anyways. Such an allocator is a natural central place to establish and release mappings, hiding this entire issue from all of its callers.

• device drivers, which need to map physical memory in order to get access to memory-mapped devices, are generally long-lived; they can often establish the mapping when they're loaded or the device started and then hold it until the device is closed down.

• if what the kernel is really doing is accessing the memory of a process you need to take special steps anyways (to map from the process's virtual address space to physical memory, to insure that the access is legal, and perhaps to page things back in or allocate memory). Managing a kernel mapping for the eventual page of physical RAM is in many ways the least of the work involved.

A common element in all of these cases is that the kernel often wants to do additional bookkeeping and checking while it's setting up these mappings. For example, you might want to prevent two device drivers from claiming that they both own the same chunk of physical memory.

(Some people would even argue that directly mapping all of physical memory by default is an invitation for kernel programmers to write sloppy code that skips these sort of necessary steps and thus bypasses important safety checks. This is probably especially so for device drivers, which stereotypically are often written by people who are not expert kernel programmers.)

PS: I suspect that there have been CPUs with instructions that let you explicitly use physical addresses and bypass virtual address translation. I don't know if any current CPUs work that way; it seems at least a little bit at odds with current CPU design trends.

Unicode code points and abstract characters

In yesterday's entry I mentioned in passing that Unicode code points were both more and less than abstract characters. Since this is the kind of statement that might raise people's eyebrows, I figure that I should explain (and justify) it.

Unicode code points are more than just abstract characters because of the presence of combining characters. Combining characters turn Unicode code points into a system for assembling an abstract character from components; you have the base character and then various accent marks and suchlike added on to it.

(I don't consider Unicode direction marks and other zero-width formatting characters to be on the same level as combining characters. My impression is that you can not use the formatting characters, while combining characters are a fundamental part of how you use Unicode.)

Unicode code points are less than abstract characters because of Han unification. I say this because the practical upshot of Han unification is that a Unicode code point by itself is not enough information to display the right glyph to someone in all circumstances; you also need to know their locale. This makes the real abstract character the combination of the Unicode code point and the locale information.

(Some of this is a matter of people's preferences, but there are apparently at least some cases where people will not recognize pr understand the wrong glyph. See the discussion and the links in my old entry on how Unicode is not simple. The whole issue is complicated and contentious.)

A theory on why defaults for tunable parameters stay unchanged

Despite my grumblings about tunable parameters with stupid old defaults, I've decided that I actually have a reasonable amount of sympathy for kernel engineers and other developers who are in this situation and wind up leaving the defaults untouched. The following is only a theory, because I have never been in this situation, but I think it's a plausible one.

The problem with the defaults for tunable parameters in any long-lived project is that leaving them unchanged takes no work at all while changing them is probably going to require a bunch of your time. In an ideal world you could just set good values as the new defaults, and here we run into the first problem: what are good default values now? Worse, how do you know that these are good default values? Have you measured this or done analytic work to defend your numbers?

In a long-lived project, there's going to be someone who will ask you these questions if you propose new default values. You're proposing a change, so it's up to you to justify it. In fact it's probably up to you to argue people into accepting your new values (or formula) even in the face of people who disagree with it or think that it's possible to come up with better default values or who worry about corner cases that they think you haven't considered.

All of this is a bunch of work and a pain in the rear. As an OS developer (or any sort of developer) there's a lot of other things you could be doing with your time, things that are more obviously productive and less annoying. So, really, who wants to stir up the anthill? Better to leave those old defaults unchanged. Besides, these days everyone changes them anyways (except not really, but don't think about that).

(If you want to you can see this as another example of the perfect being the enemy of the good, or at least the enemy of the 'better than it currently is'.)