Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linear Address Spaces: Unsafe at any speed (2022)

queue.acm.org

Post reply on HN
Print view View original

101–110 of 183 posts

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

#101

Post by musicale »

Veserv wrote: post #51
josephg wrote: post #47

Earlier quoted context omitted.

Is there anything stopping us from doing this today on modern hardware? Why do we grow the stack down?

x86-64 call instruction decrements the stack pointer to push the return address. x86-64 push instructions decrement the stack pointer. The push instructions are easy to work around because most compilers already just push the entire stack frame at once and then do offset accesses, but the call instruction would be kind of annoying. ARM does not suffer from that problem due to the usage of link registers and generic p…

> [x86] call instruction would be kind of annoying

I wonder what the best way to do it (on current x86) would be. The stupid simple way might be to adjust SP before the call instruction, and that seems to me like something that would be relatively efficient (simple addition instruction, issued very early).

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

#102

Post by musicale »

LukeShu wrote: post #55
ch_123 wrote: post #31

Earlier quoted context omitted.

HP-UX on PA-RISC had an upward-growing stack. In practice, various exploits were developed which adapted to the changed direction of the stack. One source from a few mins of searching: https://phrack.org/issues/58/11

Linux on PA-RISC also has an upward-growing stack (AFAIK, it's the only architecture Linux has ever had an upward-growing stack on; it's certainly the only currently-supported one).

Both this and parent comment about PA-RISC are very interesting.

As noted, stack growing up doesn't prevent all stack overflows, but it makes it less trivially easy to overwrite a return address. Bounded strings also made it less trivially easy to create string buffer overflows.

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

#103

Post by jason_oster »

inkyoto wrote: post #96
LegionMammal978 wrote: post #77

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.

«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…

> «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.

That already exists. Swap memory, mmap, disk paging, and so on.

Virtual memory is mostly fine for what it is, and it has been used in practice for decades. The problem that comes up is latency. Access time is limited by the speed of light [1]. And for that reason, CPU manufacturers continue to increase the capacities of the faster, closer memories (specifically registers and L1 cache).

[1] https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

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

#104

Post by musicale »

dmitrygr wrote: post #86

“Why don’t we do $thing_that_decisively_failed instead of $thing_that_evolved_to_beat_all_other_approaches?” Usually this sort of question comes from a lack of understanding of the history of the failure of the first and the success of the second. The fence principle always applies “don’t tear down a fence till you understand why it was built” Linear address spaces allow for how computers actually operate - layers. O…

IIRC Multics (among other systems) had both segmentation and paging, and a unified memory/storage architecture.

[I had thought that Multics' "ls" command abbreviation stood for "list segments" but the full name of the command seems to have been just "list". Sadly Unix/Linux didn't retain the dual full name (list, copy, move...) + abbreviated name (ls, cp, mv...) for common commands, using abbreviated names exclusively.]

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

#105

Post by Joker_vD »

musicale wrote: post #101
Veserv wrote: post #51

Earlier quoted context omitted.

x86-64 call instruction decrements the stack pointer to push the return address. x86-64 push instructions decrement the stack pointer. The push instructions are easy to work around because most compilers already just push the entire stack frame at once and then do offset accesses, but the call instruction would be kind of annoying. ARM does not suffer from that problem due to the usage of link registers and generic p…

> [x86] call instruction would be kind of annoying I wonder what the best way to do it (on current x86) would be. The stupid simple way might be to adjust SP before the call instruction, and that seems to me like something that would be relatively efficient (simple addition instruction, issued very early).

Some architectures had CALL that was just "STR [SP], IP" without anything else, and it was up to the called procedure to adjust the stack pointer further to allocate for its local variables and the return slot for further calls. The RET instruction would still normally take an immediate (just as e.g. x86/x64's RET does) and additionally adjust the stack pointer by its value (either before or after loading the return address from the tip of the stack).

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

#106

Post by duped »

inkyoto wrote: post #97
duped wrote: post #78

Earlier quoted context omitted.

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…

Ultimately everything is an abstraction. The point I'm making is that linear regions are a useful abstraction for both disk and memory, but that's not enough to unify them. Particularly in that memory cares about the visibility of writes to other processes/threads, whereas disk cares about the durability of those writes. This is an important distinction that programmers need to differentiate between for correctness.

Perhaps a WAL was a bad example. Ultimately you need the ability to atomically reserve a region of a certain capacity and then commit it durably (or roll back). Perhaps there are other abstractions that can do this, but with linear memory and disk regions it's exceedingly easy.

Personally I think file I/O should have an atomic CAS operation on a fixed maximum number of bytes (just like shared memory between threads and processes) but afaik there is no standard way to do that.

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

#107

Post by musicale »

RachelF wrote: post #82
mpweiher wrote: post #45

> 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…

> iAPX 432 Yes, this was a failure, the Itanium of the 1980's I also regard ADA as a failure. I worked with it many years ago. ADA would take 30 minutes to compile a program. Turbo C++ compiled equivalent code in a few seconds.

Machines are thousands of times faster now, yet C++ compilation is still slow somehow (templates? optimization? disinterest in compiler/linker performance? who knows?) Saving grace is having tons of cores and memory for parallel builds. Linking is still slow, though.

Of course Pascal compilers (Turbo Pascal etc.) could be blazingly fast since Pascal was designed to be compiled in a single pass, but presumably linking was faster as well. I wonder how Delphi or current Pascal compilers compare? (Pascal also supports bounded strings and array bounds checks IIRC.)

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

#108

Post by dmitrygr »

Joker_vD wrote: post #12
btdmaster wrote: post #3

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.

In ARMv4/v5 (non-thumb-mode) stack is purely a convention that hardware does not enforce. Nobody forces you to use r13 as the stack pointer or to make the stack descending. You can prototype your approach trivially with small changes to gcc and linux kernel. As this is a standard architectural feature, qemu and the like will support emulating this. And it would run fine on real hardware too. I'd read the paper you publish based on this.

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

#109

Post by tliltocatl »

shrubble wrote: post #99
mpweiher wrote: post #45

> 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, a…

> IBM i Series / AS400

Aren't AS400 closer to JVM than to a AXP432 in it's implementation details? Sans IBM's proprietary lingo, TIMI is just a bytecode virtual machine and was designed as such from the beginning. Then again, on a microcoded CPU it's hard to tell the difference.

> I think the use by Unix of linear made it more popular

More like linear address space was the only logical solution since EDVAC. Then in late 50's Manchester Atlas invented virtual memory to abstract away the magnetic drums. Some smart minds (Robert S. Barton with his B5000 which was a direct influence for JVM but was he the first one?) released what we actually want is segment/object addressing. Multics/GE-600 went with segments (couldn't find any evidence they were directly influenced by B5000 but seems so).

System/360, which was the pre-Unix lingo franca, went with flat address space. Guess IBM folks wanted to go as conservative as possible. They also wanted S/360 to compete in HPC as well so performance was quite important - and segment addressing doesn't give you that. Then VM/370 showed that flat/paged addressing allows you to do things segments can't. And then came PDP-11 (which was more or less about compressing S/360 into a mini, sorry DEC fans), RMS/VMS and Unix.

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

#110

Post by GeorgeTirebiter »

musicale wrote: post #104
dmitrygr wrote: post #86

“Why don’t we do $thing_that_decisively_failed instead of $thing_that_evolved_to_beat_all_other_approaches?” Usually this sort of question comes from a lack of understanding of the history of the failure of the first and the success of the second. The fence principle always applies “don’t tear down a fence till you understand why it was built” Linear address spaces allow for how computers actually operate - layers. O…

IIRC Multics (among other systems) had both segmentation and paging, and a unified memory/storage architecture. [I had thought that Multics' "ls" command abbreviation stood for "list segments" but the full name of the command seems to have been just "list". Sadly Unix/Linux didn't retain the dual full name (list, copy, move...) + abbreviated name (ls, cp, mv...) for common commands, using abbreviated names exclusivel…

Correct. 'Segments' are the Proper Unit to think about a bag of bits doing a computation; pages sitting under segments is how VM systems worked to only load the active parts of segments; that's kind of what defined Demand Paging. We have got to get back to the garden here, we need to start valuing security and safety at least as much as raw speed. https://en.wikipedia.org/wiki/Multics?useskin=vector Tagged memory, Capabilities (highly granular), and, yes, segments. Probably needs a marketing refresh (renaming) so as to not be immediately discarded.
Post reply on HN