10 ms·

Using uninitialized memory for fun and profit (2008)

120 points by Smaug123 3y ago

lois1250 3y ago
[flagged]
devbug 3y ago
A similar data-structure that is also very useful uses sparse-dense arrays but encodes a free-list in the unused memory. It's an ideal data structure if your access patterns are sporadic reads/writes bookmarked by frequent complete iterations of the dense array. You can insert and remove (swap 'n' pop) in O(1) and iterate in O(n) without polluting your cache and skipping over empty slots. It's frequently used in Entity-Component Systems (ECS) which introduce safety by associating a counter with each entry in the sparse array (usually called a "generation") and incrementing them on deletion. You can also verify cross-linkage between the sparse and dense arrays like the data structure described in the article, but that comes at the cost of another indirection and fetch from memory.
- mandarax8 3y ago
  This sounds like just what I need for a project, any idea where I could find more info on this or how its called?
  - orlp 3y ago
    In Rust there's my crate slotmap, the above described design matches the DenseSlotMap type. It's also often called a generational arena.
  - devbug 3y ago
    There’s some articles floating around that touch on the idea. Bitsquid comes to mind. [1] To give a slightly more detailed description, you allocate two arrays of the extents. One is the dense array of whatever type, say T, and the other is the sparse array of 32 bit or 64 bit integers. The sparse array stores indices into the dense array for extant objects. However, for extinct objects, the indices instead point to the sparse array itself to encode a free-list. To insert, in O(1), you check the free-list for an unused slot. If there is none, then you grow the sparse array (increment a counter) and use the newly introduced slot. Then you insert (or construct in place) your object at the end of the dense array. Finally, you map that slot in the sparse array to the end of the dense array. To delete, in O(1), you swap the object you wish to delete with the last in the dense array and decrement the counter (swap and pop). Then you add the index in the sparse array to the free-list. You’ll need to know the index assigned to the object you swapped with to do this, which can either be stored on the object itself or by introducing another array the maintains an inverse mapping. To iterate, you can treat the dense array like any other array. This scheme poses some challenges: - You lose pointer stability because you are relocating your objects. You must access them through indices. If you can defer your deletions, say to a frame boundary, you assume your pointers are stable. - Indices, without further work, are not safe. They are just as safe as pointers. Usually you don’t expect more than N objects, so you can use log2(N) bits for the forward and reverse mappings between sparse and dense arrays and then use the leftover bits to identify stale indices. You can, and should, encapsulate this in a type-safe handle system. [2][3] - High churn can cause index invalidation to fail (if you wrap a counter) and performs worse than other data structures. - “Swap and pop” requires T to be trivially copyable, or ideally, trivially relocatable. It’s also worth mentioning that you can reorder the dense array to maintain custom invariants. This is really useful if you have dependencies between objects and want to iterate in order.[4] [1]: http://bitsquid.blogspot.com/2014/08/building-data-oriented-entity-system.html http://bitsquid.blogspot.com/2014/08/building-data-oriented-... [2]: https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html [3]: You usually can use 24 bits for index and 8 bits for a discriminator (counter) in games. Handles (that you pass around) can be wider to exploit register widths and increase safety, since you have 32 bits for further runtime checks. [4]: By doing more work at insertion and deletion, a constant factor on O(1), you can save work on iteration or updates, a constant factor on O(n). A great example of this being a worthwhile optimization is for scene graphs or transform hierarchies. If you partially order by depth in the hierarchy, you can guarantee correct computation without chasing indexes or pointers. If you maintain additional information about boundaries, you can trivially parallelize computation of transforms or reduce redundant work.
- gpderetta 3y ago
  Is this related to std::hive [1] as proposed for next C++ standard? [1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0447r22.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p04...
  - devbug 3y ago
    At a quick glance, this is very close. However, the proposal goes through several contortions to maintain pointer stability. If you preallocate sufficient storage for your worst case (which can be unmapped virtual memory) then it makes implementation a lot simpler. Neat that the committee is looking to introduce it. Too bad we eschew the STL (and even CRT) in games.
saagarjha 3y ago
For those wondering: in C, this is probably OK on your system, but if you don’t fully understand the explanation I give below, then you should get sign-off from an expert before using this code. Here’s how it works: Accessing an uninitialized variable is always undefined, in the following case: * the storage can be declared with the register keyword Because this is an array of uninitialized data, this is not relevant. In that case, the standard specifies that the value produced is indeterminate. An indeterminate value can either be: * a trap representation * an unspecified value unsigned char never has any trap representations. Its value when uninitialized is always unspecified. Other types may have a trap representation, in theory: this is implementation defined. On your system this is almost certainly not true for integer types, but you may have signaling floats. Accessing a value that is a trap representation is undefined behavior. If you don’t have any trap representations, then the value produced is unspecified. An unspecified value is, morally, “some random value from the range of values this thing can take”. Of note, the value produced is not required to be consistent: two “reads” can produce different results. However the act of performing the read and the results it produces (bounded by what I just mentioned) are well defined. Putting it all together, in the case of this algorithm, on a system where integers do not have trap representations, the uninitialized read will produce an unspecified value, which the algorithm does not rely on a consistent result from. So, overall, it’s probably ok. If you are using this code and don’t have a comment that describes exactly what I just said then you need to add one immediately. There are not many cases where it is crucial to juggle the precise definition of well-defined, undefined, implementation-defined, indeterminate, and unspecified. This is one of them.
- lmm 3y ago
  I don't believe it's guaranteed to work correctly on any system, because in this code: is-member(i): return sparse[i] < n && dense[sparse[i]] == i there's no requirement for the two sparse[i] to take the same value (since that expression evaluates to an indeterminate vaule). So the second occurrence of sparse[i] can take a value >=n, or indeed greater than the length of the whole array, at which point reading it is definitely UB.
  - au8er 3y ago
turndown 3y ago
> return sparse[i] < n && dense[sparse[i]] == i This line lives in fear of the optimizer. sparse[i] references uninitialized memory and is thus UB and could be optimized out at a certain level. Also I think I read once that even if we’ll allow that sparse[i] stays in the program, there’s still no guarantee that each access of sparse[i] will read the same value since it’s still UB.
- alexvitkov 3y ago
  If you're running in some theoretical fairy dust C++ spec environment sure, but in reality sparse is just a pointer and the compiler can't know its value, or whether or not it's "initialized". Even if you construct a degenerate case: int* sparse = (int*)malloc(100 * sizeof(int)); int x = sparse[40]; // provably unitialized it still won't "optimize out" the access, since 1. it's insane. nobody would write such an optimization because there's no possible performance gain, and it changes program behavior 2. malloc is just a function, it's not treated in any special way 3. there's no guarentee this malloc is a per-spec malloc, it can be a user-defined function for which this is perfectly valid
  - dwattttt 3y ago
    to address the points in order: 1. a specific optimisation pass won't do this, but the combination of several passes written with other intentions can 2 & 3. the C runtime a compiler links with is known to the compiler/linker, and it _does_ usually treat intrinsics like malloc specially A quick google reveals https://github.com/llvm/llvm-project/issues/52930 https://github.com/llvm/llvm-project/issues/52930, LLVM recognising uninitialised memory as 'undef', and needing to treat it as poisoned (IIRC propogation of undef can cause things like separate uses of the variable to not even unify to a single value) EDIT: duplicated link
  - adwn 3y ago
    Well, you're 100% wrong: https://godbolt.org/z/en31xx9Yx https://godbolt.org/z/en31xx9Yx clang optimizes this function to a single ret, optimizing away not just the memory access, but the call to malloc() as well. I does this (and is allowed to do this) because it recognizes that sparse[40] accesses uninitialized memory, which is UB, and therefore anything goes – including replacing the entire function with a no-op.
dang 3y ago
Related: Using Uninitialized Memory for Fun and Profit (2008) - https://news.ycombinator.com/item?id=8710557 https://news.ycombinator.com/item?id=8710557 - Dec 2014 (17 comments) Using Uninitialized Memory for Fun and Profit - https://news.ycombinator.com/item?id=3565212 https://news.ycombinator.com/item?id=3565212 - Feb 2012 (14 comments) Using Uninitialized Memory for Fun and Profit - https://news.ycombinator.com/item?id=1156628 https://news.ycombinator.com/item?id=1156628 - Feb 2010 (16 comments)
tialaramex 3y ago
This maybe calls for a way to tell the compiler that we don't care what value this object has, but we promise it does already have some concrete value. As written this can't work, but once the compiler understands what's going on it seems fine. In Rust I'd imagine this as a method on MaybeUninit<T> the type which might be a T but maybe not yet. It's possible we can just assume_init() today where T is something like a byte but if it's unclear, a method which expresses our intent to get an unspecified value is better than just saying well, maybe you can assume_init() but we're not sure if that means what you intended.
- iudqnolq 3y ago
  Problem is an uninit value is unstable. The compiler could be using it to store something else, and could change what it's storing at different times. You need a freeze operation to say "I don't care what that this is, but it should have one value". https://www.ralfj.de/blog/2019/07/14/uninit.html https://www.ralfj.de/blog/2019/07/14/uninit.html
  - tialaramex 3y ago
    Right, I have seen that post but I didn't end up remembering the use of "freeze" to name this operation. I'd be fine if it was named freeze, labelled unsafe and specifically called out in Safety as requiring that all bit patterns for T are valid representations of T which I think meets the requirement, but it sounds like this can't be done (easily?) without help from LLVM
- raphlinus 3y ago
  Right, in relatively recent versions of LLVM, there is a "freeze" operation. Making it available to programmers, possibly as a method off MaybeUninit, would potentially be useful. The safety overlaps that of "safe transmute" (and ecosystem crates such as bytemuck that provide that). The Pod trait[1] probably establishes the invariants so that freeze on uninitialized memory is safe. I imagine the details are tricky (my understanding is that "freeze" took a long time to land in LLVM), but that there's no fundamental reason it can't be done. But I also imagine there are a lot higher priorities; the use case in this blog is pretty niche. There's more discussion in this thread: [2] [1]: https://docs.rs/bytemuck/latest/bytemuck/trait.Pod.html https://docs.rs/bytemuck/latest/bytemuck/trait.Pod.html [2]: https://internals.rust-lang.org/t/freeze-maybeuninit-t-maybeuninit-t-for-masked-reads/17188 https://internals.rust-lang.org/t/freeze-maybeuninit-t-maybe...
NikkiA 3y ago
A neat trick that I discovered at university was that VMS' email system used 'sparse' disk blocks for your personal mailbox file, and immediately after forcing a rebuild of your mailbox by compacting it, you'd have dozens of sparse, uninitialised, disk blocks in your file - which you naturally had read access to. Since compacting mail was the most common activity on a time shared university system, the odds were a good number of those uninit'ed blocks would be other people's erased blocks, and thus you could essentially read other people's emails just by sitting and compacting your email, then hex viewing the raw mailbox file.

120 points by Smaug123 3y ago

[flagged]

A similar data-structure that is also very useful uses sparse-dense arrays but encodes a free-list in the unused memory. It's an ideal data structure if your access patterns are sporadic reads/writes bookmarked by frequent complete iterations of the dense array. You can insert and remove (swap 'n' pop) in O(1) and iterate in O(n) without polluting your cache and skipping over empty slots. It's frequently used in Entity-Component Systems (ECS) which introduce safety by associating a counter with each entry in the sparse array (usually called a "generation") and incrementing them on deletion. You can also verify cross-linkage between the sparse and dense arrays like the data structure described in the article, but that comes at the cost of another indirection and fetch from memory.

mandarax8 3y ago
This sounds like just what I need for a project, any idea where I could find more info on this or how its called?
- orlp 3y ago
  In Rust there's my crate slotmap, the above described design matches the DenseSlotMap type. It's also often called a generational arena.
- devbug 3y ago
  There’s some articles floating around that touch on the idea. Bitsquid comes to mind. [1] To give a slightly more detailed description, you allocate two arrays of the extents. One is the dense array of whatever type, say T, and the other is the sparse array of 32 bit or 64 bit integers. The sparse array stores indices into the dense array for extant objects. However, for extinct objects, the indices instead point to the sparse array itself to encode a free-list. To insert, in O(1), you check the free-list for an unused slot. If there is none, then you grow the sparse array (increment a counter) and use the newly introduced slot. Then you insert (or construct in place) your object at the end of the dense array. Finally, you map that slot in the sparse array to the end of the dense array. To delete, in O(1), you swap the object you wish to delete with the last in the dense array and decrement the counter (swap and pop). Then you add the index in the sparse array to the free-list. You’ll need to know the index assigned to the object you swapped with to do this, which can either be stored on the object itself or by introducing another array the maintains an inverse mapping. To iterate, you can treat the dense array like any other array. This scheme poses some challenges: - You lose pointer stability because you are relocating your objects. You must access them through indices. If you can defer your deletions, say to a frame boundary, you assume your pointers are stable. - Indices, without further work, are not safe. They are just as safe as pointers. Usually you don’t expect more than N objects, so you can use log2(N) bits for the forward and reverse mappings between sparse and dense arrays and then use the leftover bits to identify stale indices. You can, and should, encapsulate this in a type-safe handle system. [2][3] - High churn can cause index invalidation to fail (if you wrap a counter) and performs worse than other data structures. - “Swap and pop” requires T to be trivially copyable, or ideally, trivially relocatable. It’s also worth mentioning that you can reorder the dense array to maintain custom invariants. This is really useful if you have dependencies between objects and want to iterate in order.[4] [1]: http://bitsquid.blogspot.com/2014/08/building-data-oriented-entity-system.html http://bitsquid.blogspot.com/2014/08/building-data-oriented-... [2]: https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html [3]: You usually can use 24 bits for index and 8 bits for a discriminator (counter) in games. Handles (that you pass around) can be wider to exploit register widths and increase safety, since you have 32 bits for further runtime checks. [4]: By doing more work at insertion and deletion, a constant factor on O(1), you can save work on iteration or updates, a constant factor on O(n). A great example of this being a worthwhile optimization is for scene graphs or transform hierarchies. If you partially order by depth in the hierarchy, you can guarantee correct computation without chasing indexes or pointers. If you maintain additional information about boundaries, you can trivially parallelize computation of transforms or reduce redundant work.
gpderetta 3y ago
Is this related to std::hive [1] as proposed for next C++ standard? [1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0447r22.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p04...
- devbug 3y ago
  At a quick glance, this is very close. However, the proposal goes through several contortions to maintain pointer stability. If you preallocate sufficient storage for your worst case (which can be unmapped virtual memory) then it makes implementation a lot simpler. Neat that the committee is looking to introduce it. Too bad we eschew the STL (and even CRT) in games.

saagarjha 3y ago

For those wondering: in C, this is probably OK on your system, but if you don’t fully understand the explanation I give below, then you should get sign-off from an expert before using this code. Here’s how it works: Accessing an uninitialized variable is always undefined, in the following case: * the storage can be declared with the register keyword Because this is an array of uninitialized data, this is not relevant. In that case, the standard specifies that the value produced is indeterminate. An indeterminate value can either be: * a trap representation * an unspecified value unsigned char never has any trap representations. Its value when uninitialized is always unspecified. Other types may have a trap representation, in theory: this is implementation defined. On your system this is almost certainly not true for integer types, but you may have signaling floats. Accessing a value that is a trap representation is undefined behavior. If you don’t have any trap representations, then the value produced is unspecified. An unspecified value is, morally, “some random value from the range of values this thing can take”. Of note, the value produced is not required to be consistent: two “reads” can produce different results. However the act of performing the read and the results it produces (bounded by what I just mentioned) are well defined. Putting it all together, in the case of this algorithm, on a system where integers do not have trap representations, the uninitialized read will produce an unspecified value, which the algorithm does not rely on a consistent result from. So, overall, it’s probably ok. If you are using this code and don’t have a comment that describes exactly what I just said then you need to add one immediately. There are not many cases where it is crucial to juggle the precise definition of well-defined, undefined, implementation-defined, indeterminate, and unspecified. This is one of them.

lmm 3y ago
I don't believe it's guaranteed to work correctly on any system, because in this code: is-member(i): return sparse[i] < n && dense[sparse[i]] == i there's no requirement for the two sparse[i] to take the same value (since that expression evaluates to an indeterminate vaule). So the second occurrence of sparse[i] can take a value >=n, or indeed greater than the length of the whole array, at which point reading it is definitely UB.
- au8er 3y ago

turndown 3y ago

> return sparse[i] < n && dense[sparse[i]] == i This line lives in fear of the optimizer. sparse[i] references uninitialized memory and is thus UB and could be optimized out at a certain level. Also I think I read once that even if we’ll allow that sparse[i] stays in the program, there’s still no guarantee that each access of sparse[i] will read the same value since it’s still UB.

alexvitkov 3y ago
If you're running in some theoretical fairy dust C++ spec environment sure, but in reality sparse is just a pointer and the compiler can't know its value, or whether or not it's "initialized". Even if you construct a degenerate case: int* sparse = (int*)malloc(100 * sizeof(int)); int x = sparse[40]; // provably unitialized it still won't "optimize out" the access, since 1. it's insane. nobody would write such an optimization because there's no possible performance gain, and it changes program behavior 2. malloc is just a function, it's not treated in any special way 3. there's no guarentee this malloc is a per-spec malloc, it can be a user-defined function for which this is perfectly valid
- dwattttt 3y ago
  to address the points in order: 1. a specific optimisation pass won't do this, but the combination of several passes written with other intentions can 2 & 3. the C runtime a compiler links with is known to the compiler/linker, and it _does_ usually treat intrinsics like malloc specially A quick google reveals https://github.com/llvm/llvm-project/issues/52930 https://github.com/llvm/llvm-project/issues/52930, LLVM recognising uninitialised memory as 'undef', and needing to treat it as poisoned (IIRC propogation of undef can cause things like separate uses of the variable to not even unify to a single value) EDIT: duplicated link
- adwn 3y ago
  Well, you're 100% wrong: https://godbolt.org/z/en31xx9Yx https://godbolt.org/z/en31xx9Yx clang optimizes this function to a single ret, optimizing away not just the memory access, but the call to malloc() as well. I does this (and is allowed to do this) because it recognizes that sparse[40] accesses uninitialized memory, which is UB, and therefore anything goes – including replacing the entire function with a no-op.

dang 3y ago

Related: Using Uninitialized Memory for Fun and Profit (2008) - https://news.ycombinator.com/item?id=8710557 https://news.ycombinator.com/item?id=8710557 - Dec 2014 (17 comments) Using Uninitialized Memory for Fun and Profit - https://news.ycombinator.com/item?id=3565212 https://news.ycombinator.com/item?id=3565212 - Feb 2012 (14 comments) Using Uninitialized Memory for Fun and Profit - https://news.ycombinator.com/item?id=1156628 https://news.ycombinator.com/item?id=1156628 - Feb 2010 (16 comments)

tialaramex 3y ago

This maybe calls for a way to tell the compiler that we don't care what value this object has, but we promise it does already have some concrete value. As written this can't work, but once the compiler understands what's going on it seems fine. In Rust I'd imagine this as a method on MaybeUninit<T> the type which might be a T but maybe not yet. It's possible we can just assume_init() today where T is something like a byte but if it's unclear, a method which expresses our intent to get an unspecified value is better than just saying well, maybe you can assume_init() but we're not sure if that means what you intended.

iudqnolq 3y ago
Problem is an uninit value is unstable. The compiler could be using it to store something else, and could change what it's storing at different times. You need a freeze operation to say "I don't care what that this is, but it should have one value". https://www.ralfj.de/blog/2019/07/14/uninit.html https://www.ralfj.de/blog/2019/07/14/uninit.html
- tialaramex 3y ago
  Right, I have seen that post but I didn't end up remembering the use of "freeze" to name this operation. I'd be fine if it was named freeze, labelled unsafe and specifically called out in Safety as requiring that all bit patterns for T are valid representations of T which I think meets the requirement, but it sounds like this can't be done (easily?) without help from LLVM
raphlinus 3y ago
Right, in relatively recent versions of LLVM, there is a "freeze" operation. Making it available to programmers, possibly as a method off MaybeUninit, would potentially be useful. The safety overlaps that of "safe transmute" (and ecosystem crates such as bytemuck that provide that). The Pod trait[1] probably establishes the invariants so that freeze on uninitialized memory is safe. I imagine the details are tricky (my understanding is that "freeze" took a long time to land in LLVM), but that there's no fundamental reason it can't be done. But I also imagine there are a lot higher priorities; the use case in this blog is pretty niche. There's more discussion in this thread: [2] [1]: https://docs.rs/bytemuck/latest/bytemuck/trait.Pod.html https://docs.rs/bytemuck/latest/bytemuck/trait.Pod.html [2]: https://internals.rust-lang.org/t/freeze-maybeuninit-t-maybeuninit-t-for-masked-reads/17188 https://internals.rust-lang.org/t/freeze-maybeuninit-t-maybe...

NikkiA 3y ago

A neat trick that I discovered at university was that VMS' email system used 'sparse' disk blocks for your personal mailbox file, and immediately after forcing a rebuild of your mailbox by compacting it, you'd have dozens of sparse, uninitialised, disk blocks in your file - which you naturally had read access to. Since compacting mail was the most common activity on a time shared university system, the odds were a good number of those uninit'ed blocks would be other people's erased blocks, and thus you could essentially read other people's emails just by sitting and compacting your email, then hex viewing the raw mailbox file.