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

Using uninitialized memory for fun and profit (2008)

research.swtch.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Using uninitialized memory for fun and profit (2008)

#11

Post by dooglius »

NobodyNada wrote: post #8
kmeisthax wrote: post #4

Earlier quoted context omitted.

My impression was that there was some kind of optimization in LLVM that relied on being able to assume values were never undef[0], which is why undefined memory access was always illegal in Rust[1]. Putting that aside, a deliberate "read uninitialized memory with bounded UB" primitive like freeze would only work for types where all possible bit patterns are valid. So no freezing chars[2], references, or sum types. An…

> there was some kind of optimization in LLVM that relied on being able to assume values were never undef It's true that LLVM has restrictions on what you can do with undef/poison memory, but LLVM also supports the "freeze" operation that comes up in the Rust discussions (which transforms an undefined value into an arbitrary, well-defined value). It would certainly need to be unsafe to avoid violating invariants like…

Seems like the heap allocator has a bug if it doesn't handle invalidating the free hint before it returns it to the application. This does raise the question of why MADV_FREE works on the basis of writes rather than accesses -- there are PTE bits for both cases right, and it would have been just as easy to have any access cancel the free hint? (I am assuming x86 here.)

Re: Using uninitialized memory for fun and profit (2008)

#12

Post by joseluis »

kmeisthax wrote: post #4
jojomodding wrote: post #2

Interestingly enough, Rust does not allow you to access undefined memory, not even if you do not care about the value stored there. People have been proposing a `freeze` operation that replaces uninitialized memory with garbage but initialized data (i.e. a no-op in assembly). But there is tension about this: Not allowing access to uninitialized memory, ever, means that you get more guarantees about what foreign (safe…

My impression was that there was some kind of optimization in LLVM that relied on being able to assume values were never undef[0], which is why undefined memory access was always illegal in Rust[1]. Putting that aside, a deliberate "read uninitialized memory with bounded UB" primitive like freeze would only work for types where all possible bit patterns are valid. So no freezing chars[2], references, or sum types. An…

Just a nitpick. Rust's char is really a 21 bit unicode scalar value (a code point without surrogates) using a 32-bit representation and indeed there are a lot of invalid char values in a 32-bit space. Utf-8 is a different encoding format for code points using variable width (1-4 bytes per).

Re: Using uninitialized memory for fun and profit (2008)

#13

Post by Sesse__ »

dooglius wrote: post #9
Sesse__ wrote: post #7

An elegant optimization, but how would you intersect two of these efficiently? It sounds like you'd need to iterate over the entire dense vector and do a sparse-vector check for each and every value (O(m) with a very high constant factor). Either that, or sort both sparse vectors (O(n log n)).

Why would iterating over the dense vector be O(m) rather than O(n)?

Sorry, I meant iterating over the sparse vector, not the dense vector (I find the nomenclature in the article somehow inverted).

Re: Using uninitialized memory for fun and profit (2008)

#14

Post by dzaima »

Sesse__ wrote: post #7

An elegant optimization, but how would you intersect two of these efficiently? It sounds like you'd need to iterate over the entire dense vector and do a sparse-vector check for each and every value (O(m) with a very high constant factor). Either that, or sort both sparse vectors (O(n log n)).

Wouldn't it be just a trivial O(n) of a loop of "for (x in dense vector of one set) { if (is x a member of the other set) add to result; }"?

Re: Using uninitialized memory for fun and profit (2008)

#15

Post by dzaima »

dooglius wrote: post #11
NobodyNada wrote: post #8

Earlier quoted context omitted.

> there was some kind of optimization in LLVM that relied on being able to assume values were never undef It's true that LLVM has restrictions on what you can do with undef/poison memory, but LLVM also supports the "freeze" operation that comes up in the Rust discussions (which transforms an undefined value into an arbitrary, well-defined value). It would certainly need to be unsafe to avoid violating invariants like…

Seems like the heap allocator has a bug if it doesn't handle invalidating the free hint before it returns it to the application. This does raise the question of why MADV_FREE works on the basis of writes rather than accesses -- there are PTE bits for both cases right, and it would have been just as easy to have any access cancel the free hint? (I am assuming x86 here.)

That could be classified as a bug if it was decided that the allocator must guarantee that uninitialized memory is readable as a consistent value. Otherwise, making the allocator clear the hint is just unnecessary work.

Clearing the hint on read would probably be more sane, but would mean many more potential situations of unnecessarily losing it (GC doing unnecessary scanning, doing a heap dump, debuggers trying to read it, other sorts of memory scanning)

Re: Using uninitialized memory for fun and profit (2008)

#16

Post by Sesse__ »

dzaima wrote: post #14
Sesse__ wrote: post #7

An elegant optimization, but how would you intersect two of these efficiently? It sounds like you'd need to iterate over the entire dense vector and do a sparse-vector check for each and every value (O(m) with a very high constant factor). Either that, or sort both sparse vectors (O(n log n)).

Wouldn't it be just a trivial O(n) of a loop of "for (x in dense vector of one set) { if (is x a member of the other set) add to result; }"?

True. The constant factor is nasty, though, compared to the 256-bits-per-instruction of normal bit sets.

Re: Using uninitialized memory for fun and profit (2008)

#17

Post by dzaima »

Sesse__ wrote: post #16
dzaima wrote: post #14

Earlier quoted context omitted.

Wouldn't it be just a trivial O(n) of a loop of "for (x in dense vector of one set) { if (is x a member of the other set) add to result; }"?

True. The constant factor is nasty, though, compared to the 256-bits-per-instruction of normal bit sets.

Right; generally the constant factors of this approach are horrible though, can't think of any situation where it'd be worth it on systems with, well, cache (or a TLB for that matter, which is even worse off with the sparse memory usage).

Re: Using uninitialized memory for fun and profit (2008)

#19

Post by dooglius »

Sesse__ wrote: post #13
dooglius wrote: post #9

Earlier quoted context omitted.

Why would iterating over the dense vector be O(m) rather than O(n)?

Sorry, I meant iterating over the sparse vector, not the dense vector (I find the nomenclature in the article somehow inverted).

You could do intersection by iterating over the dense vector though, not sure why you would need to iterate over the sparse one

Re: Using uninitialized memory for fun and profit (2008)

#20

Post by Sesse__ »

dooglius wrote: post #19
Sesse__ wrote: post #13

Earlier quoted context omitted.

Sorry, I meant iterating over the sparse vector, not the dense vector (I find the nomenclature in the article somehow inverted).

You could do intersection by iterating over the dense vector though, not sure why you would need to iterate over the sparse one

Yeah, sure, you can iterate over the dense vector and check in the other side's sparse vector, that's correct.
Post reply on HN