Hacker News Reader

Comment by TheLoneWolfling | Hacker News Reader

Your sentence to missing a word.

Nonetheless, I agree. Eventually one cannot continue putting blame solely on the proximal cause.

It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking. Even something as simple as "any writes inside the stack outside my stack frame and all reads inside the stack and after my stack frame should assert" (on an opt-in until the next return) would do wonders towards preventing some of these sorts of errors, although not all.

View on HN

It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking

It's called the BOUND instruction, and has been there since the 80186/188:

http://en.wikipedia.org/wiki/X86_instruction_listings#Added_...

Ironically, AMD removed it in AMD64 and Intel followed them, but it's still there in 32-bit mode.

Because individual instructions doing the same thing are faster. Though it's especially slow because it's microcoded and is left just for backwards compatibility and not trying to be fast. So modern CPUs are good at reordering, predicting branches, etc., for simple instructions and no extra silicon needs to be wasted to duplicate that. And encoding space is limited as well.

If individual instructions are faster, that means the instruction decoder isn't as good as it should be. BOUND wasn't fast because it didn't get any use, and it didn't get any use because people thought it was slow... but now that the usefulness of this instruction is apparent, it seems to me that they should make the decoder issue the necessary uops and make it at least as fast as the (bigger, more cache-wasting) sequence of simpler instructions.

Instructions like MOVS and STOS used to be slower than the equivalent series of simple instructions, but now they're much faster. Even the more obscure and far less useful BCD arithmetic instructions have been made on-par with a longer series of equivalent instructions[1] so not doing the same for the much more useful BOUND is... unusual. The amount of silicon needed to implement MPX (which includes several new instructions) seems far more than it'd take to make a BOUND decode faster.

[1] https://news.ycombinator.com/item?id=8477585

BOUND didn't get much of an use because it is useful only for bounds checking of the "dump core if outside" kind.

Why? (Honest question).

Because the instruction raises a software exception if the test fails. This is a rather heavy-handed reaction, although I guess it kind of makes sense from the instruction's point of view I guess.

Of course a language runtime based on using this instruction needs to capture the exception and handle it, core-dumping need not be the only option at that point.

Part of the issue is that the interrupt number, 5, is hard-wired. So there really was no need to keep it alive.

Divide-by-zero has always been interrupt 0, and the page fault is at #14, and that hasn't been problematic...

BOUND does raise an exception if it fails but I think that's a good thing - if code is doing array bounds-checking, OOB accesses are very likely to be a bug (and possible security vulnerability) so aborting execution by default is the right thing to do.

I feel like this suggestion is a little misplaced. To use a scheme like this you must ultimately tell the hardware what the bounds are, and that layer is going to be error prone in the same ways as what it replaces.

From this vantage point I can say the abstraction that already exists for this is the page table. The MMU knows what regions are mapped and it will generate a fault for an out of bounds access. But within mapped regions the array bounds are all fiction. As they should be in the eyes of the hardware. That is for higher level layers to worry about.

I feel like the c-haters don't get that some layer of the system must work this way. By all means build your higher level stuff on top. But things like virtual memory and allocators are well understood, frankly when it gets to that level there is little reason for it to give a damn that a[] has an element count of 5. At some point something must chop up larger blocks into smaller ones, and create new bounds from nothing.

This would require using zillions of VM areas for all your language level objects, and aligning them on page boundaries. It's really not going to work.

Have a look at SoftBound and HardBound for some of the current thinking in this area that scales to object level granularity.

I think you misunderstand me. I am advocating the status quo, not for more granular pages.

Anyway from what I have seen some high level languages are actually using the MMU for some things. For example, a null check at every access would be kind of lame, from what I have seen high level language runtimes just let it fault on the zero page and handle it by raising exceptions. (I am 100% sure CLR does this, I believe JVM does too.)

On 32-bit x86, you could use segment registers to get bounds checking with overhead only at setup and not at use, effectively making bounds checks free in hot loops (http://www.blackhat.com/presentations/bh-usa-05/BH_US_05-Chi...). I believe that SpiderMonkey uses this trick. Doesn't work on x86-64 though.

Have you heard of MPX?

http://en.m.wikipedia.org/wiki/Intel_MPX

Yes I have, but MPX is primarily for a different use case.

Also, MPX has performance issues. See [1].

Also, it has false positives (!). Not a good thing.

[1]https://code.google.com/p/address-sanitizer/wiki/IntelMemory...

Hmm... according to that page, the false positives and performance issues seem to largely derive from using the cache structure to store bounds externally. But if you manage the bounds explicitly as part of your data structures, and use BNDMOV/BNDMK rather than BND{ST,LD}X, it should be reasonably fast. What else could Intel do?

Have a read of the linked page again. A large chunk of the performance issues are because in many cases you can't just "use BNDMOV/BNDMK rather than BND{ST,LD}X".

There are a number of data structures where managing bounds explicitly has... issues. Namely, you end up with a lot of overhead. And the entire purpose of hardware support is to prevent the overhead.

Something like, as I said, an opt-in assert when you read past the end of your stack frame, or write before or after your stack frame, doesn't have the overhead. It doesn't prevent a lot of things - about the only thing it prevents is stack smashing - but it's better than nothing and doesn't have the overhead.

That will only work for direct writes to array variables on the stack, or pointers which can be proved to live on the current stack frame, but those are quite rare; e.g. in the vulnerability mentioned in the post, it's sprintf doing the overflowing write into its parent stack frame, but sprintf could be called with any pointer. If, say, you narrow the trapping region to some unused region of the stack frame to try to avoid this, you can get slightly better protection than a stack canary, but not much better. And most overflow vulnerabilities in modern software seem to be on the heap anyway.*

(Which is not to say primitives based on fine-grained tagged memory couldn't do some interesting things; OpenRISC has some form of this, but I haven't looked into it in detail.)

I don't see content on the linked page corresponding to data structures where managing bounds explicitly is difficult, other than the bnd_variable_size bit, which is described as rare.

*corrected to state that I'm only considering overflows, not, e.g., use-after-frees, which aren't related to bounds checks

Reply on news.ycombinator.com