Rambles around computer science

Diverting trains of thought, wasting precious time Tue, 25 Aug 2026 Flat vs segmented memory -- it's recursive My recent forays in x86 segmentation (1 2) made me notice a trend in the evolution of x86: the decline of fine-grained memory protection, both across the move to 64-bit and indeed before that in the fast system calling features. These both partially hobbled the sophisticated segmentation system, which had been a hallmark of the architecture since the 286. The explanation is possibly Unix: the dominance of Unix and its preference for flat address spaces, rather than segmented ones, arguably inherited from the PDP-11 or indeed PDP-7, meant that “nobody wanted” a 64-bit version of the segmentation features. Meanwhile, I like to joke among WebAssembly enthusiasts that “segmented memory is coming back”. WebAssembly is rather like a return to the programming model of OS/2 or some other non-Unix OSes, where flatness did not reign so supreme. Such non-flatness is still highly relevant to safety and security of course. I recently revisited some of the ever-enjoyable writings of Poul-Henning Kamp, who framed CHERI as a reaction against flat memory models that he describes as “unsafe at any speed”. Kamp observes that the first thing software does on any flat memory is impose some subdivision structure on it. One way to look at the question is as about to what extent the hardware should know about this subdivision... CHERI says yes, whereas earlier hardware had said no—except, of course, in certain cases, for a bunch of segmentation stuff! Of course segmentation as realised in x86 doesn't have the semantics needed for fine-grained confinement, i.e. confinement within appropriate corners of the non-flat address space. Unprivileged code can reload segment registers and thereby reach any defined segment, modulo a very coarse-grained four-ring privilege model. So, the non-flatness of traditional segments was more for fault isolation than for security: it was secure only up to coarse-grained distinctions like user vs system, and otherwise protected only against incompetence not malice. I think that “yes or no” is the wrong way to look at it, though. It's recursive! When we've imposed some subdivision structure on a flat memory, we like to do so again. Think arenas or memory pools, but also think about fields within structures (within structures). The question is not about flatness or not—the programmer's mental abstraction is never flat—but somehow how we square a fundamentally recursive phenomenon practised by programmers, namely subdivision, with hardware—which is very much non-recursive. Hardware is conceptually finite-state, and its engineering practices tend to prefer fixed structures and bounded depths; maybe an ultra-CISC CPU will provide some iteration in microcode, but that's about the limit. If hardware is non-recursive but software is recursive, how can we square those differences? A naive approach is just to bound the depth: say hardware knows up to N levels of decomposition, probably with N=1, and the rest is on software. But that is not satisfactory; it is “the hardware washing its hands” of what the programmer is doing. It guarantees non-unformity and the loss, at higher N, of any hardware-added value. CHERI does not do this; it keeps the flexibility to deal with recursive decomposition because software still handles the recursive steps: bounds can be arbitrarily narrow (-ish), but are narrowed by software and passed around explicitly. What you can address at any point, therefore, is determined not so much by the state of the hardware but by an emergence of the software: what has flowed within reach of the currently executing code, i.e. the memory you can access the transitive closure of reachable capabilities. (This emergence naturally opens up an obvious auditing difficulty, although one which the right tools could address.) CHERI also buys this flexibility by, ironically, a restriction: addressing is constrained to be over an unbroken chain of capability derivation operations with monotonically decreasing bounds. I've always felt some discomfort about this bargain, because, software being software, some programs will choose to go their own way, e.g. by performing funky non-monotonic address calculations. Our several-decades' legacy of programs expressing their traversal of a somehow-subdivided address space in software, just the way they like it, set up friction with any new, more opinionated hardware. Overcoming this is a mere matter of development effort, but making that effort will only become normalised, a.k.a. its cost “successfully” externalised across the industry, if CHERI (or something similar) “wins”. (That cost would come with great benefits in return of course. But “winning”, in the sense of achieving hardware ubiquity, is a high-stakes game.) With liballocs, I have been “happily” much less concerned with security and therefore largely free not to get into the business of prescribing rules for how addresses may be derived. I've instead been much more concerned with capturing descriptively whatever structure real software may have come up with, as it recursively subdivides the flat address space it starts out with. It has a recursive abstraction at its heart: allocations nest within other allocations, forming a tree. There's also no “level-N cut-off” or hardware/software divide: it's fundamentally software, and it wants to capture the structure all the way down using reflective abstractions that are as uniform as possible despite their many and heterogeneous implementations within the system. This “homogeneous interface, heterogeneous implementation” idea is of course often associated with object-orientation, and rarely with hardware. While liballocs itself is not opinionated about how programs use the recursively subdivided structure that liballocs keeps track of, it could certainly be used to build added-security mechanisms that impose some opinions—although secure against malice if, and only if, the underlying hardware provides useful primitives for securing those mechanisms themselve, within the same address space. Annoyingly, x86-style segmentation would have been a near-sufficient basis, if the OS actually exposed it to userland. For roughly what I'd like, I'm constantly reminded of the amusingly-titled “Lord of the x86 Rings” paper. Incidentally, to finish on another object-oriented note, the classical language-VM approach to subdivision punts in completely the opposite way to hardware: everything is near-maximally subdivided, into tiny objects and an enormous explicit interreferencing (pointer) relation between them. The programmer no doubt has coarser-grained structures in their head, but they stay there: the system doesn't offer to structure storage around them. As a result, these systems also punt on spatial locality—the hardware's heuristic of grouping together bytes or words into larger units, hence the longstanding performance disadvantages of such approaches. [/research] [all entries] permalink contact validate this page