matklad

1,168 karmajoined 12 лет назад

https://github.com/matklad

Submissions

Automation That Screams Joy

tigerbeetle.com

9 pointsby matklad3 месяца назад0 comments

comments

позавчераdiscuss

Some thoughts on this here: https://matklad.github.io/2025/12/23/static-allocation-compi...

3 дня назадdiscuss

To add more context around lifetime errors and TigerBeetle's particular style guide:

>Many projects opt to answer these kinds of questions through a style guide. TigerBeetle's TigerStyle is an example in Zig and Google's 31,000 word C++ style guide is another. The challenge with style guides is enforcement.

TigerStyle[1] is a bit more than just a style guide. The key rule for this discussion, uplifted straight from of NASA[2], is *static memory allocation*: all memory is allocated in the startup phase, and there's absolutely zero `alloc`s afterwrads . This plus crash only[3] design means that we never call `free`.

This rule is self-enforcing and compositional, in Zig. There's no global memory allocator, so the code after startup simply hasn't the API to allocate. You can't circumvent this by accident. Of course, if the programmer is byzantine, they can stuff allocator in the global, or just directly `mmap` and `unmap` pages of memory, but, at our scale, we don't have problems with that. This is a similar in kind (not degree) to Rust, where untrusted code generally can circumvent safety guarantees, even without literally spelling `unsafe`.

And, naturally, never `free`ing goes a long way towards solving many memory errors by construction. Empirically, they just haven't been a problem for TigerBeetle. It's hard to untangle contribution of static allocation in particular from everything else we are doing, but it would make sense for it to play a leading role.

(As a footnote, we aren't actually do static allocation to avoid memory errors, we use it as a linter to check that every quantity has a known _logical_ static limit, the main property we care about)

[1]: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI...

[2]: https://spinroot.com/gerard/pdf/P10.pdf

[3]: https://www.usenix.org/legacy/events/hotos03/tech/full_paper...

2 месяца назадdiscuss

To clarify, those are things an LLM considers to be issues, and LLMs can make mistakes.

Some of those are clear false positives, others I need to revisit tomorrow to say one way or another.

5 месяцев назадdiscuss

Ha! I also use `line_number = line_index + 1` convention!

5 месяцев назадdiscuss

Thanks, I haven't considered this! My history is usually naturally project-scoped, but I bet I'll find ~/make.ts useful now that I have it!

6 месяцев назадdiscuss

I assume you ment to write `assert(subexpression != undefined)`?

This is resilient parsing --- we are parsing source code with syntax errors, but still want to produce a best-effort syntax tree. Although expression is required by the grammar, the `expression` function might still return nothing if the user typed some garbage there instead of a valid expression.

However, even if we return nothing due to garbage, there are two possible behaviors:

* We can consume no tokens, making a guess that what looks like "garbage" from the perspective of expression parser is actually a start of next larger syntax construct:

``` function f() { let x = foo(1, let not_garbage = 92; } ```

In this example, it would be smart to _not_ consume `let` when parsing `foo(`'s arglist.

* Alternatively, we can consume some tokens, guessing that the user _meant_ to write an expression there

``` function f() { let x = foo(1, /); } ```

In the above example, it would be smart to skip over `/`.

6 месяцев назадdiscuss

In

    const recv_buffers = try ByteArrayPool.init(gpa, config.connections_max, recv_size);
    const send_buffers = try ByteArrayPool.init(gpa, config.connections_max, send_size);

if the second try throws, than the memory allocation created by the first try is leaked. Possible fixes:

A) clean up individual allocations on failure:

    const recv_buffers = try ByteArrayPool.init(gpa, config.connections_max, recv_size);
    errdefer recv_buffers.deinit(gpa);

    const send_buffers = try ByteArrayPool.init(gpa, config.connections_max, send_size);
    errdefer send_buffers.deinit(gpa);

B) ask the caller to pass in an arena instead of gpa to do bulk cleanup (types & code stays the same, but naming & contract changes):

    const recv_buffers = try ByteArrayPool.init(arena, config.connections_max, recv_size);
    const send_buffers = try ByteArrayPool.init(arena, config.connections_max, send_size);

C) declare OOMs to be fatal errors

    const recv_buffers = ByteArrayPool.init(gpa, config.connections_max, recv_size) catch |err| oom(err);
    const send_buffers = ByteArrayPool.init(gpa, config.connections_max, send_size) catch |err| oom(err);

    fn oom(_: error.OutOfMemory) noreturn { @panic("oom"); }

You might also be interesting in https://matklad.github.io/2025/12/23/static-allocation-compi..., it's essentially a complimentary article to what @MatthiasPortzel says here https://news.ycombinator.com/item?id=46423691

6 месяцев назадdiscuss

>If you look at MITRE's top 25 most dangerous software weaknesses, the top four (in the 2025 list) aren't related to UB in any language (by the way, UAF is #7).

FWIW, I don't find this argument logically sound, in context. This is data aggregated across programming languages, so it could simultaneously be true that, conditioned on using memory unsafe language, you should worry mostly about UB, while, at the same time, UB doesn't matter much in the grand scheme of things, because hardly anyone is using memory-unsafe programming languages.

There were reports from Apple, Google, Microsoft and Mozilla about vulnerabilities in browsers/OS (so, C++ stuff), and I think there UB hovered at between 50% and 80% of all security issues?

And the present discussion does seem overall conditioned on using a manually-memory-managed language :0)

6 месяцев назадdiscuss

They do make a lot of sense in other contexts :-) From the actual rules, only #2 (minimize preprocessor) and #10 (compiler warnings) are C specific. Everything else is more-or-less universally applicable.

6 месяцев назадdiscuss

There's some reshuffling of bugs for sure, but, from my experience, there's also a very noticeable reduction! It seems there's no law of conservation of bugs.

I would say the main effect here is that global allocator often leads to ad-hoc, "shotgun" resource management all other the place, and that's hard to get right in a manually memory managed language. Most Zig code that deals with allocators has resource management bugs (including TigerBeetle's own code at times! Shoutout to https://github.com/radarroark/xit as the only code base I've seen so far where finding such bug wasn't trivial). E.g., in OP, memory is leaked on allocation failures.

But if you manage resources manually, you just can't do that, you are forced to centralize the codepaths that deal with resource acquisition and release, and that drastically reduces the amount of bug prone code. You _could_ apply the same philosophy to allocating code, but static allocation _forces_ you to do that.

The secondary effect is that you tend to just more explicitly think about resources, and more proactively assert application-level invariants. A good example here would be compaction code, which juggles a bunch of blocks, and each block's lifetime is tracked both externally:

* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...

and internally:

* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...

with a bunch of assertions all other the place to triple check that each block is accounted for and is where it is expected to be

https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...

I see a weak connection with proofs here. When you are coding with static resources, you generally have to make informal "proofs" that you actually have the resource you are planning to use, and these proofs are materialized as a web of interlocking asserts, and the web works only when it is correct in whole. With global allocation, you can always materialize fresh resources out of thin air, so nothing forces you to do such web-of-proofs.

To more explicitly set the context here: the fact that this works for TigerBeetle of course doesn't mean that this generalizes, _but_, given that we had a disproportionate amount of bugs in small amount of gpa-using code we have, makes me think that there's something more here than just TB's house style.

6 месяцев назадdiscuss

See https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... for motivation.

- Operational predictability --- latencies stay put, the risk of threshing is reduced (_other_ applications on the box can still misbehave, but you are probably using a dedicated box for a key database)

- Forcing function to avoid use-after-free. Zig doesn't have a borrow checker, so you need something else in its place. Static allocation is a large part of TigerBeetle's something else.

- Forcing function to ensure existence of application-level limits. This is tricky to explain, but static allocation is a _consequence_ of everything else being limited. And having everything limited helps ensure smooth operations when the load approaches deployment limit.

- Code simplification. Surprisingly, static allocation is just easier than dynamic. It has the same "anti-soup-of-pointers" property as Rust's borrow checker.

6 месяцев назадdiscuss

To add more context, TigerStyle is quite a bit more than just static allocation, and it indeed explicitly attributes earlier work:

> NASA's Power of Ten — Rules for Developing Safety Critical Code will change the way you code forever. To expand:

* https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI...

* https://spinroot.com/gerard/pdf/P10.pdf

6 месяцев назадdiscuss

Yes, very good point, thanks!

As a tiny nit, TigerBeetle isn't _file system_ backed database, we intentionally limit ourselves to a single "file", and can work with a raw block device or partition, without file system involvement.

7 месяцев назадdiscuss

It is the other way around --- it is _relatively_ easy to re-use the storage engine, but plug your custom state machine (implemented in Zig). We have two state machines, an accounting one, and a simple echo one here: https://github.com/tigerbeetle/tigerbeetle/blob/main/src/tes....

I am not aware of any "serious" state machine other than accounting one though.

7 месяцев назадdiscuss

It's not that ironic though --- the number of bugs that were squashed fuzzers&asserts but would have dodged the borrow checker is much, much larger.

This is what makes TigerBeetle context somewhat special --- in many scenarios, security provided by memory safety is good enough, and any residual correctness bugs/panics are not a big deal. For us, we need to go extra N miles to catch the rest of the bugs as well, and DST is a much finer net for those fishes (given static allocation & single threaded design).

7 месяцев назадdiscuss

You need to learn both. Both borrow checker (Rust) and comptime (Zig) are huge ideas worth getting your hands dirty with.

If you don't have time to learn both, then learn Zig, as it requires much smaller time investment (though do try to find time for both).

8 месяцев назадdiscuss

Just to avoid potential confusion, the claim is that this is a function that generates a random permutation:

    pub fn shuffle(g: *Gen, T: type, slice: []T) void {
        if (slice.len <= 1) return;

        for (0..slice.len - 1) |i| {
            const j = g.range_inclusive(u64, i, slice.len - 1);
            std.mem.swap(T, &slice[i], &slice[j]);
        }
    }

And this is a function that enumerates all permutations, in order, exactly once:

    pub fn shuffle(g: *Gen, T: type, slice: []T) void {
        if (slice.len <= 1) return;

        for (0..slice.len - 1) |i| {
            const j = g.range_inclusive(u64, i, slice.len - 1);
            std.mem.swap(T, &slice[i], &slice[j]);
        }
    }

Yes, they are exactly the same function. What matters is Gen. If it looks like this

https://github.com/tigerbeetle/tigerbeetle/blob/809fe06a2ffc...

then you get a random permutation. If it rather looks like this

https://github.com/tigerbeetle/tigerbeetle/blob/809fe06a2ffc...

you enumerate all permutations.

8 месяцев назадdiscuss

It is much better than this. You can _directly_ enumerate all the objects, without any probabilities involved. There's nothing about probabilities in the interface of a PRNG, it's just non-determinism!

You could _implement_ non-determinism via probabilistic sampling, but you could also implement the same interface as exhaustive search.

9 месяцев назадdiscuss

I personally learned Zig by reading https://ziglang.org/documentation/master/ and stdlib source code once I joined TigerBeetle. enums.zig and meta.zig are good places to learn, in addition to usual suspects like array_list.zig.

(though, to be fair, my Rust experience was a great help for learning Zig, just as my C++ knowledge was instrumental in grokking Rust)

9 месяцев назадdiscuss

Well said! Having a mental borrow checker running in background certainly helps a lot when coding in Zig. What also helps is that Zig safety checks generally catch lifetime bugs at runtime nicely. E.g., undefined memory is set to `0xAAAA`, which, if interpreted as a pointer, is guaranteed to be invalid, and fail loudly on dereference.