5 ms·

A lot of embedded devices and safety critical software sometimes don't even use a heap, and instead use pre-allocated chunks of memory whose size is calculated

A lot of embedded devices and safety critical software sometimes don't even use a heap, and instead use pre-allocated chunks of memory whose size is calculated beforehand. It's memory safe, and has much more deterministic execution time. This is also a popular approach in games, especially ones with entity-component-system architectures. I'm excited about Zig for these use cases especially, it can be a much easier approach with much less complexity than using a borrow checker.

brundolf 4y ago
Rust's borrow checker would be much calmer in these scenarios too, wouldn't it? If there are no lifetimes, there are no lifetime errors
- thecatster 4y ago
  Rust is definitely different (and calmer imho) on bare metal. That said (as much of a Rust fanboy I am), I also enjoy Zig.
- the__alchemist 4y ago
  Yep! We've entered a grey areas, where some Rust embedded libs are expanding the definitions of memory safety, and what the borrow checker should evaluate beyond what you might guess. Eg, structs that represent peripherals, that are now checked for ownership; the intent being to prevent race conditions. And Traits being used to enforce pin configuration.
_vvhw 4y ago
This is almost what we do for TigerBeetle, a new distributed database being written in Zig. All memory is statically allocated at startup [1]. Thereafter, there are zero calls to malloc() or free(). We run a single-threaded control plane for a simple concurrency model, and because we use io_uring—multithreaded I/O is less of a necessary evil than it used to be. I find that the design is more memory efficient because of these constraints, for example, our new storage engine can address 100 TiB of storage using only 1 GiB of RAM. Latency is predictable and gloriously smooth, and the system overall is much simpler and fun to program. [1] “Let's Remix Distributed Database Design” https://www.youtube.com/channel/UC3TlyQ3h6lC_jSWust2leGg https://www.youtube.com/channel/UC3TlyQ3h6lC_jSWust2leGg
- infamouscow 4y ago
  > Latency is predictable and gloriously smooth, and the system overall is much simpler and fun to program. This has also been my experience building a database in Zig. It's such a joy.
- catlifeonmars 4y ago
  > for example, our new storage engine can address 100 TiB of storage using only 1 GiB of RAM. I’m a little confused by this statement. I assume by “address” you mean indexing, and the size of an index is related to the number of entries, not the amount of data being indexed. (For example, you could trivially address 100TiB using 1 address width of memory if all 100TiB belongs to the same key).
  - _vvhw 4y ago
    > I’m a little confused by this statement. I assume by “address” you mean indexing, and the size of an index is related to the number of entries, not the amount of data being indexed. Thanks for the question! What's in view here is an LSM-tree database storage engine. In general, these typically store keys between 8 and 32 bytes and values up to a few MiB. In our case, the question is how much memory is required for the LSM-tree to be able to index 100 TiB worth of key/value storage, where: * keys are between 8 and 32 bytes, * values are between 8 and 128 bytes, * keys and values are stored in tables up to 64 MiB, * each table requires between 128 and 256 bytes of metadata to be kept in memory, * auxiliary data structures such as a mutable/immutable table must be kept in memory, and where * all memory required by the engine must be statically allocated. That's alot of small keys and values! Typically, a storage system might require at least an order of magnitude more than 1 GiB of memory to keep track of that many keys using an LSM-tree as index, even using dynamic allocation, which only needs to allocate as needed. Another way to think of this is as a filesystem, since it's a very similar problem. Imagine you stored 100 TiB worth of 4096 byte files in ZFS. How much RAM would that require for ZFS to be able to keep track of everything?
    - catlifeonmars 4y ago
      Thanks for taking the time to reply in detail! The metric makes much more sense when put into context.
snicker7 4y ago
How exactly is pre-allocation safer? If you would ever like to re-use chunks of memory, then wouldn’t you still encounter “use-after-free” bugs?
- verdagon 4y ago
  The approach can reuse old elements for new instances of the same type, so to speak. Since the types are the same, any use-after-free becomes a plain ol' logic error. We use this approach in Rust a lot, with Vecs.
  - olig15 4y ago
    But if you have a structure that contains offsets into another buffer somewhere, or an index, whatever - the wrong value here could be just as bad as a use-after-free. I don’t see how this is any safer. If you use memory after free from a malloc, with any chance you’ll hit a page fault, and your app will crash. If you have a index/pointer to another structure, you could still end up reading past the end of that structure into the unknown.
    - verdagon 4y ago
      That's just a logic error, and not memory unsafety which might risk UB or vulnerabilities. The type system enforces that if we use-after-"free" (remember, we're not free'ing or malloc'ing), we just get a different instance of the same type, which is memory-safe. You do bring up a valid broader concern. Ironically, this is a reason that GC'd systems can sometimes be better for privacy than Ada or Rust which uses a lot more Vec+indexes. An index into a Vec<UserAccount> is riskier than a Java List<UserAccount>; a Java reference can never suddenly point to another user account like an index could. But that aside, we're talking about memory safety, array-centric approaches in Zig and Rust can be appropriate for a lot of use cases.
      - pjmlp 4y ago
        In high integrity computing that is pretty much safety related, if that logic error causes someone to die due to corrupt data, like using the wrong radiation value.
pcwalton 4y ago
Even in this environment, you can still have dangling pointers to freed stack frames. There's no way around having a proper lifetime system, or a GC, if you want memory safety.
- verdagon 4y ago
  Yep, or generational references [0] which also protect against that kind of thing ;) The array-centric approach is indeed more applicable at the high levels of the program. Sometimes I wonder if a language could use an array-centric approach at the high levels, and then an arena-based approach for all temporary memory. Elucent experimented with something like this for Basil once [1] which was fascinating. [0] https://verdagon.dev/blog/generational-references https://verdagon.dev/blog/generational-references [1] https://degaz.io/blog/632020/post.html https://degaz.io/blog/632020/post.html
  - com2kid 4y ago
    > Yep, or generational references [0] which also protect against that kind of thing ;) First off, thank you for posting all your great articles on Vale! Second off, I just read the generational references blog post for the 3rd time and now it makes complete sense, like stupid obvious why did I have problems understanding this before sense. (PS: The link to the benchmarks is dead :( ) I hope some of the novel ideas in Vale make it out to the programming language world at large!
    - verdagon 4y ago
      Thank you! I just fixed the link, thanks for letting me know! And if any of my articles are ever confusing, feel welcome to swing by the discord or file an issue =) I'm pretty excited about all the memory safety advances languages have made in the last few years. Zig is doing some really interesting things (see Andrew's thread above), D's new static analysis for zero-cost memory safety hit the front page yesterday, we're currently prototyping Vale's region borrow checker, and it feels like the space is really exploding. Good time to be alive!
  - 4y ago

brundolf 4y ago

Rust's borrow checker would be much calmer in these scenarios too, wouldn't it? If there are no lifetimes, there are no lifetime errors

thecatster 4y ago
Rust is definitely different (and calmer imho) on bare metal. That said (as much of a Rust fanboy I am), I also enjoy Zig.
the__alchemist 4y ago
Yep! We've entered a grey areas, where some Rust embedded libs are expanding the definitions of memory safety, and what the borrow checker should evaluate beyond what you might guess. Eg, structs that represent peripherals, that are now checked for ownership; the intent being to prevent race conditions. And Traits being used to enforce pin configuration.

_vvhw 4y ago

This is almost what we do for TigerBeetle, a new distributed database being written in Zig. All memory is statically allocated at startup [1]. Thereafter, there are zero calls to malloc() or free(). We run a single-threaded control plane for a simple concurrency model, and because we use io_uring—multithreaded I/O is less of a necessary evil than it used to be. I find that the design is more memory efficient because of these constraints, for example, our new storage engine can address 100 TiB of storage using only 1 GiB of RAM. Latency is predictable and gloriously smooth, and the system overall is much simpler and fun to program. [1] “Let's Remix Distributed Database Design” https://www.youtube.com/channel/UC3TlyQ3h6lC_jSWust2leGg https://www.youtube.com/channel/UC3TlyQ3h6lC_jSWust2leGg

infamouscow 4y ago
> Latency is predictable and gloriously smooth, and the system overall is much simpler and fun to program. This has also been my experience building a database in Zig. It's such a joy.
catlifeonmars 4y ago
> for example, our new storage engine can address 100 TiB of storage using only 1 GiB of RAM. I’m a little confused by this statement. I assume by “address” you mean indexing, and the size of an index is related to the number of entries, not the amount of data being indexed. (For example, you could trivially address 100TiB using 1 address width of memory if all 100TiB belongs to the same key).
- _vvhw 4y ago
  > I’m a little confused by this statement. I assume by “address” you mean indexing, and the size of an index is related to the number of entries, not the amount of data being indexed. Thanks for the question! What's in view here is an LSM-tree database storage engine. In general, these typically store keys between 8 and 32 bytes and values up to a few MiB. In our case, the question is how much memory is required for the LSM-tree to be able to index 100 TiB worth of key/value storage, where: * keys are between 8 and 32 bytes, * values are between 8 and 128 bytes, * keys and values are stored in tables up to 64 MiB, * each table requires between 128 and 256 bytes of metadata to be kept in memory, * auxiliary data structures such as a mutable/immutable table must be kept in memory, and where * all memory required by the engine must be statically allocated. That's alot of small keys and values! Typically, a storage system might require at least an order of magnitude more than 1 GiB of memory to keep track of that many keys using an LSM-tree as index, even using dynamic allocation, which only needs to allocate as needed. Another way to think of this is as a filesystem, since it's a very similar problem. Imagine you stored 100 TiB worth of 4096 byte files in ZFS. How much RAM would that require for ZFS to be able to keep track of everything?
  - catlifeonmars 4y ago
    Thanks for taking the time to reply in detail! The metric makes much more sense when put into context.

snicker7 4y ago

How exactly is pre-allocation safer? If you would ever like to re-use chunks of memory, then wouldn’t you still encounter “use-after-free” bugs?

verdagon 4y ago
The approach can reuse old elements for new instances of the same type, so to speak. Since the types are the same, any use-after-free becomes a plain ol' logic error. We use this approach in Rust a lot, with Vecs.
- olig15 4y ago
  But if you have a structure that contains offsets into another buffer somewhere, or an index, whatever - the wrong value here could be just as bad as a use-after-free. I don’t see how this is any safer. If you use memory after free from a malloc, with any chance you’ll hit a page fault, and your app will crash. If you have a index/pointer to another structure, you could still end up reading past the end of that structure into the unknown.
  - verdagon 4y ago
    That's just a logic error, and not memory unsafety which might risk UB or vulnerabilities. The type system enforces that if we use-after-"free" (remember, we're not free'ing or malloc'ing), we just get a different instance of the same type, which is memory-safe. You do bring up a valid broader concern. Ironically, this is a reason that GC'd systems can sometimes be better for privacy than Ada or Rust which uses a lot more Vec+indexes. An index into a Vec<UserAccount> is riskier than a Java List<UserAccount>; a Java reference can never suddenly point to another user account like an index could. But that aside, we're talking about memory safety, array-centric approaches in Zig and Rust can be appropriate for a lot of use cases.
    - pjmlp 4y ago
      In high integrity computing that is pretty much safety related, if that logic error causes someone to die due to corrupt data, like using the wrong radiation value.

pcwalton 4y ago

Even in this environment, you can still have dangling pointers to freed stack frames. There's no way around having a proper lifetime system, or a GC, if you want memory safety.

verdagon 4y ago
Yep, or generational references [0] which also protect against that kind of thing ;) The array-centric approach is indeed more applicable at the high levels of the program. Sometimes I wonder if a language could use an array-centric approach at the high levels, and then an arena-based approach for all temporary memory. Elucent experimented with something like this for Basil once [1] which was fascinating. [0] https://verdagon.dev/blog/generational-references https://verdagon.dev/blog/generational-references [1] https://degaz.io/blog/632020/post.html https://degaz.io/blog/632020/post.html
- com2kid 4y ago
  > Yep, or generational references [0] which also protect against that kind of thing ;) First off, thank you for posting all your great articles on Vale! Second off, I just read the generational references blog post for the 3rd time and now it makes complete sense, like stupid obvious why did I have problems understanding this before sense. (PS: The link to the benchmarks is dead :( ) I hope some of the novel ideas in Vale make it out to the programming language world at large!
  - verdagon 4y ago
    Thank you! I just fixed the link, thanks for letting me know! And if any of my articles are ever confusing, feel welcome to swing by the discord or file an issue =) I'm pretty excited about all the memory safety advances languages have made in the last few years. Zig is doing some really interesting things (see Andrew's thread above), D's new static analysis for zero-cost memory safety hit the front page yesterday, we're currently prototyping Vale's region borrow checker, and it feels like the space is really exploding. Good time to be alive!
- 4y ago