4 ms·

The long term solution is to burn down x86 and C and start over with sane hardware, which has bounds checking in hardware.

archgoon 8y ago
I'm curious; what does your memory hardware and cpu instruction set look like in this scenario? What's the interface between the cpu and memory? (rough idea, not asking for a whitepaper here :) )
- someguydave 8y ago
  Consider the scheme 79 chip: http://dspace.mit.edu/handle/1721.1/6334 http://dspace.mit.edu/handle/1721.1/6334
chmod775 8y ago
> bounds checking in hardware. What. That's a horrible idea. Not only would that require your hardware to understand abstractions several layers above what it actually operates on, it would also mean it'd have to check bounds of - for example - an array on every instruction accessing it. That is something compilers can do at more strategic places. Please keep that complexity out of my CPUs, they're buggy enough already. At least with software we can fix issues later, which isn't a given with hardware.
- DblPlusUngood 8y ago
  Turns out the x86 already has some bounds checking support; see chapter 17 in volume 1 of Intel's developer manuals and the BOUND and BND* instructions.
  - hyperman1 8y ago
    In fact they were removed in 64 bit mode. Same for INTO
- marcosdumay 8y ago
  LoadAddressIfSmallerThan makes for a long opcode name, but it doesn't look much more complex than your usual load. The added complexity is negligible. And, of course, the added complexity of doing that in two instructions is also negligible. The entire problem seems to be that arrays are on a more abstract level than C operates. It looks like entirely a language problem.
- pjc50 8y ago
  Having the CPU do the checking within an instruction saves you instruction issue events. ARM have an interesting solution to this, pointer authentication: https://news.ycombinator.com/item?id=14479438 https://news.ycombinator.com/item?id=14479438 > several layers above what it actually operates on The instruction set is something of an abstraction bottleneck - C is tied to machines that look something like a PDP-11, while a lot of the stuff that the machine is doing is invisible at the instruction set layer.
  - makomk 8y ago
    Pointer authentication is not a form of bounds checking. It solely exists to prevent a malicious attacker using a bug to directly overwrite pointers (and in practice, it's mostly limited to return addresses right now). Code which does buggy pointer arithmetic will still create valid pointers to data outside the intended buffer.
sly010 8y ago
> which has bounds checking in hardware. x86 has bounds checking in hardware. it's called a page fault. [edit: formatting]
- erik_seaberg 8y ago
  Segmentation was expensive (loading an 80286 segment register was very slow and the segment table was impractically small) but could express "offsets between 0 and 42 are valid". Paging is much coarser and suffers from false negatives, because x[y] might accidentally walk off the end of x, skip a guard page, and land on a mapped page from another object.
- insertcredit 8y ago
  Not quite true: There would not exist exploitable buffer overflows if that was the case.
sseth 8y ago
I worked (a long time ago) on Burroughs mainframes which did bounds checking of arrays (and in fact even type checking), because the whole machine was build around ALGOL. I am not sure whether the experience from these machines was negative. It may be that when you move beyond one-dimensional arrays, bounds checking becomes more complicated. Perhaps performance suffers too. Languages which do bounds checking often have intelligent compilers which can skip the bounds check in a variety of conditions. So even if the hardware is faster, it may be doing unnecessary checks. See for example : https://www.ardanlabs.com/blog/2018/04/bounds-check-elimination-in-go.html https://www.ardanlabs.com/blog/2018/04/bounds-check-eliminat...
- qznc 8y ago
  I also believe that bounds checking in hardware is not worth it. Memory accesses dominate the runtime such that a few extra instructions for bounds checking is negligible.

archgoon 8y ago

I'm curious; what does your memory hardware and cpu instruction set look like in this scenario? What's the interface between the cpu and memory? (rough idea, not asking for a whitepaper here :) )

someguydave 8y ago
Consider the scheme 79 chip: http://dspace.mit.edu/handle/1721.1/6334 http://dspace.mit.edu/handle/1721.1/6334

chmod775 8y ago

> bounds checking in hardware. What. That's a horrible idea. Not only would that require your hardware to understand abstractions several layers above what it actually operates on, it would also mean it'd have to check bounds of - for example - an array on every instruction accessing it. That is something compilers can do at more strategic places. Please keep that complexity out of my CPUs, they're buggy enough already. At least with software we can fix issues later, which isn't a given with hardware.

DblPlusUngood 8y ago
Turns out the x86 already has some bounds checking support; see chapter 17 in volume 1 of Intel's developer manuals and the BOUND and BND* instructions.
- hyperman1 8y ago
  In fact they were removed in 64 bit mode. Same for INTO
marcosdumay 8y ago
LoadAddressIfSmallerThan makes for a long opcode name, but it doesn't look much more complex than your usual load. The added complexity is negligible. And, of course, the added complexity of doing that in two instructions is also negligible. The entire problem seems to be that arrays are on a more abstract level than C operates. It looks like entirely a language problem.
pjc50 8y ago
Having the CPU do the checking within an instruction saves you instruction issue events. ARM have an interesting solution to this, pointer authentication: https://news.ycombinator.com/item?id=14479438 https://news.ycombinator.com/item?id=14479438 > several layers above what it actually operates on The instruction set is something of an abstraction bottleneck - C is tied to machines that look something like a PDP-11, while a lot of the stuff that the machine is doing is invisible at the instruction set layer.
- makomk 8y ago
  Pointer authentication is not a form of bounds checking. It solely exists to prevent a malicious attacker using a bug to directly overwrite pointers (and in practice, it's mostly limited to return addresses right now). Code which does buggy pointer arithmetic will still create valid pointers to data outside the intended buffer.

sly010 8y ago

> which has bounds checking in hardware. x86 has bounds checking in hardware. it's called a page fault. [edit: formatting]

erik_seaberg 8y ago
Segmentation was expensive (loading an 80286 segment register was very slow and the segment table was impractically small) but could express "offsets between 0 and 42 are valid". Paging is much coarser and suffers from false negatives, because x[y] might accidentally walk off the end of x, skip a guard page, and land on a mapped page from another object.
insertcredit 8y ago
Not quite true: There would not exist exploitable buffer overflows if that was the case.

sseth 8y ago

I worked (a long time ago) on Burroughs mainframes which did bounds checking of arrays (and in fact even type checking), because the whole machine was build around ALGOL. I am not sure whether the experience from these machines was negative. It may be that when you move beyond one-dimensional arrays, bounds checking becomes more complicated. Perhaps performance suffers too. Languages which do bounds checking often have intelligent compilers which can skip the bounds check in a variety of conditions. So even if the hardware is faster, it may be doing unnecessary checks. See for example : https://www.ardanlabs.com/blog/2018/04/bounds-check-elimination-in-go.html https://www.ardanlabs.com/blog/2018/04/bounds-check-eliminat...

qznc 8y ago
I also believe that bounds checking in hardware is not worth it. Memory accesses dominate the runtime such that a few extra instructions for bounds checking is negligible.