Live data from Hacker News

Linear Address Spaces: Unsafe at any speed (2022)

queue.acm.org

91–100 of 183 posts

Re: Linear Address Spaces: Unsafe at any speed (2022)

#91

I think you could argue there is already some effort to do type safety at the ISA register level, with e.g. shadow stack or control flow integrity. Isn't that very similar to this, except targeting program state rather than external memory?

I mean, if the stacks grew upwards, that alone would nip 90% of buffer overflow attacks in the bud. Moving the return address from the activation frame into a separate stack would help as well, but I understand that having an activation frame to be a single piece of data (a current continuation's closure, essentially) can be quite convenient.

It’s still fairly easy to attack buffer overflows if the stack grows upward

Re: Linear Address Spaces: Unsafe at any speed (2022)

#92
post #74
post #68

Earlier quoted context omitted.

Those holes can be arbitrarily large, though, especially in weirder environments (e.g., memory-mapped optane and similar). Linear address space implies some degree of contiguity, I think.

Indeed. It can get ever weirder in the embedded world where a ROM, an E(E)PROM or a device may get mapped into an arbitrary slice of physical address space, anywhere within its bounds. It has become less common, though. But devices are still commonly mapped at the top of the physical address space, which is a rather widespread practice.

And it's not uncommon for devices to be mapped multiple times in the address space! The different aliases provide slightly different ways of accessing it.

For example, 0x000-0x0ff providing linear access to memory bank A, 0x100-0x1ff linear access to bank B, but 0x200-0x3ff providing striped access across the two banks, with evenly-addressed words coming from bank A but odd ones from bank B.

Similarly, 0x000-0x0ff accessing memory through a cache, but 0x100-0x1ff accessing the same memory directly. Or 0x000-0x0ff overwriting data, 0x100-0x1ff setting bits (OR with current content), and 0x200-0x2ff clearing bits.

Re: Linear Address Spaces: Unsafe at any speed (2022)

#93

Earlier quoted context omitted.

But that address doesn't have to be visible at the ISA level.

Code has to have addresses for calls and branches. Debuggers need to be able to control it all.

> Code has to have addresses for calls and branches.

Does it mean that at that level an address has to be an offset in a linear address space?

If you have hardware powerful enough to make addresses abstract, couldn't also provide the operations to manipulate them abstractly?

Re: Linear Address Spaces: Unsafe at any speed (2022)

#95

Earlier quoted context omitted.

I don't see how any amount of memory technology can overcome the physical realities of locality. The closer you want the data to be to your processor, the less space you'll have to fit it. So there will always be a hierarchy where a smaller amount of data can have less latency, and there will always be an advantage to cramming as much data as you can at the top of the hierarchy.

while that's true, CPUs already have automatically managed caches. it's not too much of a stretch to imagine a world in which RAM is automatically managed as well and you don't have a distinction between RAM and persistent storage. in a spinning rust world, that never would have been possible, but with modern nvme, it's plausible.

Cpus manage it, but ensuring your data structures are friendly to how they manage caches is one of the keys to fast programs - which some of us care about.

Re: Linear Address Spaces: Unsafe at any speed (2022)

#96
post #65

Earlier quoted context omitted.

> Because the attempts at segmented or object-oriented address spaces failed miserably. > That is false. In the Intel World, we first had the iAPX 432, which was an object-capability design. To say it failed miserably is overselling its success by a good margin. I would further posit that segmented and object-oriented address spaces have failed and will continue to fail for as long as we have a separation into two di…

I don't see how any amount of memory technology can overcome the physical realities of locality. The closer you want the data to be to your processor, the less space you'll have to fit it. So there will always be a hierarchy where a smaller amount of data can have less latency, and there will always be an advantage to cramming as much data as you can at the top of the hierarchy.

«Memory technology» as in «a single tech» that blends RAM and disk into just «memory» and obviates the need for the disk as a distinct concept.

One can conjure up RAM, which has become exabytes large and which does not lose data after a system shutdown. Everything is local in such a unified memory model, is promptly available to and directly addressable by the CPU.

Please do note that multi-level CPU caches still do have their places in this scenario.

In fact, this has been successfully done in the AS/400 (or i Series), which I have mentioned elsewhere in the thread. It works well and is highly performant.

Re: Linear Address Spaces: Unsafe at any speed (2022)

#97
post #78
post #65

Earlier quoted context omitted.

> Because the attempts at segmented or object-oriented address spaces failed miserably. > That is false. In the Intel World, we first had the iAPX 432, which was an object-capability design. To say it failed miserably is overselling its success by a good margin. I would further posit that segmented and object-oriented address spaces have failed and will continue to fail for as long as we have a separation into two di…

I shudder to think about the impact of concurrent data structures fsync'ing on every write because the programmer can't reason about whether the data is in memory where a handful of atomic fences/barriers are enough to reason about the correctness of the operations, or on disk where those operations simply do not exist. Also linear regions make a ton of sense for disk, and not just for performance. WAL-based systems…

Linear regions are mostly a figment of imagination in real life, but they are a convenient abstraction and a concept.

Linear regions are nearly impossible to guarantee, unless the underlying hardware has specific, controller-level provisions.

  1) For RAM, the MCU will obscure the physical address of a memory page, which can come from a completely separate memory bank. It is up to the VMM implementation and heuristics to ensure the contiguous allocation, coalesce unrelated free pages into a new, large allocation or map in a free page from a «distant» location.

  2)  Disks (the spinning rust variety) are not that different.  A freed block can be provided from the start of the disk. However, a sophisticated file system like XFS or ZFS, and others like it, will make an attempt do its best to allocate a contiguous block.

  3) Flash storage (SSDs, NVMe) simply «lies» about the physical blocks and does it for a few reasons (garbage collection and the transparent reallocation of ailing blocks – to name a few). If I understand it correctly, the physical «block» numbers are hidden even from the flash storage controller and firmware themselves.
The only practical way I can think of to ensure the guaranteed contiguous allocation of blocks unfortunately involves a conventional hard drive that has a dedicated partition created just for the WAL. In fact, this is how Oracle installation worked – it required a dedicated raw device to bypass both the VMM and the file system.

When RAM and disk(s) are logically the same concept, WAL can be treated as an object of the «WAL» type with certain properties specific to this object type only to support WAL peculiarities.

Re: Linear Address Spaces: Unsafe at any speed (2022)

#98
post #9

Earlier quoted context omitted.

But we don't have a linear address space, unless you're working with a tiny MCU. For last like 30 years we have virtual address space on every mainstream processor, and we can mix and match pages the way we want, insulate processes from one another, add sentinel pages at the ends of large structures to generate a fault, etc. We just structure process heaps as linear memory, but this is not a hard requirement, even on…

its entirely possible to implement segments on top of paging. what you need to do is add the kernel abstractions for implementing call gates that change segment visibility, and write some infrastructure to manage unions-of-a-bunch-of-little-regions. I haven't implemented this myself, but a friend did on a project we were working on together and as a mechanism it works perfectly well. getting userspace to do the right…

If I understood correctly, you'te talking about using descriptors to map segments; the issue with this approach is two-fold: it is slow (as each descriptor needs to be created for each segment - and sometimes more than one, if you need write-execute permissions), and there is a practical limit on the number of descriptors you can have - 8192 total, including call gates and whatnot. To extend this, you need to use LDTs, that - again - also require a descriptor in the GDT and are limited to 8192 entries. In a modern desktop system, 67 million segments would be both quite slow and at the same time quite limited.

Re: Linear Address Spaces: Unsafe at any speed (2022)

#99

> Why do we even have linear physical and virtual addresses in the first place, when pretty much everything today is object-oriented? Because the attempts at segmented or object-oriented address spaces failed miserably. > Linear virtual addresses were made to be backwards-compatible with tiny computers with linear physical addresses but without virtual memory. That is false. In the Intel World, we first had the iAPX…

For object you have the IBM i Series / AS400 based systems which used an object capabilities model (as far as I understand it). A refinement and simplification of what was pioneered in the less successful System/38.

For linear, you have the Sun SPARC processor coming out in 1986, the same year that 386 shipped in volume. I think the use by Unix of linear made it more popular (the MIPSR2000 came out in January 1986, also).

Re: Linear Address Spaces: Unsafe at any speed (2022)

#100

Earlier quoted context omitted.

The PL/I stack growing up rather than down reduced potential impact of stack overflows in Multics (and PL/I already had better memory safety, with bounded strings, etc.) TFA's author would probably have appreciated the segmented memory architecture as well. There is no reason why the C/C++ stack can't grow up rather than down. On paged hardware, both the stack and heap could (and probably should) grow up. "C's stack…

> There is no reason why the C/C++ stack can't grow up rather than down. Historical accident. Imagine if PDP-7/PDP-11 easily allowed for the following memory layout: FFFF +---------------+ | text | X +---------------+ | rodata | R +---------------+ | data + bss | RW +---------------+ | heap | | || | RW | \/ | +---------------+ | empty space | unmapped +---------------+ | /\ | | || | RW | stack | 0000 +---------------…

[deleted]
Post reply on HN