It's hard to understand what tigerbeetle is about. Can anyone ELI5 it for me?
As far as I can tell, it's some kind of a library/system geared at distributed transactions? But is it a blockchain, a db, a program ? (I did look at the website)
Hey thanks for the feedback! We've got concrete code samples in the README as well [0] that might be more clear?
It's a distributed database for tracking accounts and transfers of amounts of "thing"s between accounts (currency is one example of a "thing"). You might also be interested in our FAQ on why someone would want this [1].
The faq helped, thanks!
So, an example of typical use would be, say, as the internal ledger for a company like (transfer)wise, with lots of money moving around between accounts?
But I understand it's meant to be used internally to an entity, with all nodes in your system trusted, and not as a mean to deal with transactions from one party to another, right?
Yes, exactly. You can think of TigerBeetle as your internal ledger database, where perhaps in the past you might have had to DIY your own ledger with 10 KLOC around SQL.
And to add to what Phil said, you can also use TigerBeetle to track transactions with other parties, since we validate all user data in the transaction—there are only a handful of fields when it comes to double-entry and two-phase transfers between entities running different tech stacks.
The TigerBeetle account/transfer format is meant to be simple to parse, and if you can find user data that would break our state machine, then it's a bug.
First, because I'm a strong believer in defense-in-depth. Secondly because both disk corruption and network packet corruption happen. Alarmingly often, in fact, if you're operating at large scale.
This means that we fully expect the disk to be what we call “near-Byzantine”, i.e. to cause bitrot, or to misdirect or silently ignore read/write I/O, or to simply have faulty hardware or firmware.
Where Jepsen will break most databases with network fault injection, we test TigerBeetle with high levels of storage faults on the read/write path, probably beyond what most systems, or write ahead log designs, or even consensus protocols such as RAFT (cf. “Protocol-Aware Recovery for Consensus-Based Storage” and its analysis of LogCabin), can handle.
For example, most implementations of RAFT and Paxos can fail badly if your disk loses a prepare, because then the stable storage guarantees, that the proofs for these protocols assume, is undermined. Instead, TigerBeetle runs Viewstamped Replication, along with UW-Madison's CTRL protocol (Corruption-Tolerant Replication) and we test our consensus protocol's correctness in the face of unreliable stable storage, using deterministic simulation testing (ala FoundationDB).
Finally, in terms of network fault model, we do end-to-end cryptographic checksumming, because we don't trust TCP checksums with their limited guarantees.
So this is all at the physical storage and network layers.
"Zero deserialization? That sounds rather scary."
At the wire protocol layer, we:
* assume a non-Byzantine fault model (that consensus nodes are not malicious),
* run with runtime bounds-checking (and checked arithmetic!) enabled as a fail-safe, plus
* protocol-level checks to ignore invalid data, and
* we only work with fixed-size structs.
At the application layer, we:
* have a simple data model (account and transfer structs),
* validate all fields for semantic errors so that we don't process bad data,
* for example, here's how we validate transfers between accounts: https://github.com/tigerbeetledb/tigerbeetle/blob/d2bd4a6fc240aefe046251382102b9b4f5384b05/src/state_machine.zig#L867-L952.
No matter the deserialization format you use, you always need to validate user data.
In our experience, zero-deserialization using fixed-size structs the way we do in TigerBeetle, is simpler than variable length formats, which can be more complicated (imagine a JSON codec), if not more scary.
> Where Jepsen will break most databases with network fault injection, we test TigerBeetle with high levels of storage faults on the read/write path, probably beyond what most systems, or write ahead log designs, or even consensus protocols such as RAFT (cf. “Protocol-Aware Recovery for Consensus-Based Storage” and its analysis of LogCabin), can handle.
Oh, nice one. Whenever I speak with people who work on "high reliability" code, they seldom even use fuzz-testing or chaos-testing, which is... well, unsatisfying.
Also, what do you mean by "storage fault"? Is this simulating/injecting silent data corruption or simulating/injecting an error code when writing the data to disk?
> validate all fields for semantic errors so that we don't process bad data,
Ahah, so no deserialization doesn't mean no validation. Gotcha!
> In our experience, zero-deserialization using fixed-size structs the way we do in TigerBeetle, is simpler than variable length formats, which can be more complicated (imagine a JSON codec), if not more scary.
That makes sense, thanks. And yeah, JSON has lots of warts.
Not sure what you mean by variable length. Are you speaking of JSON-style "I have no idea how much data I'll need to read before I can start parsing it" or entropy coding-style "look ma, I'm somehow encoding 17 bits on 3.68 bits"?
> Also, what do you mean by "storage fault"? Is this simulating/injecting silent data corruption or simulating/injecting an error code when writing the data to disk?
Exactly! We focus more on bitrot/misdirection in our simulation testing. We use Antithesis' simulation testing for the latter. We've also tried to design I/O syscall errors away where possible. For example, using O_DSYNC instead of fsync(), so that we can tie errors to I/Os.
> Ahah, so no deserialization doesn't mean no validation. Gotcha!
Well said—they're orthogonal.
> Not sure what you mean by variable length. Are you speaking of JSON-style "I have no idea how much data I'll need to read before I can start parsing it"
Yes, and also where this is internal to the data structure being read, e.g. both variable-length message bodies and variable-length fields.
There's also perhaps an interesting example of how variable-length message bodies can go wrong actually, that we give in the design decisions for our wire protocol, and why we have two checksums, one over the header, and another over the body (instead of one checksum over both!): https://github.com/tigerbeetledb/tigerbeetle/blob/main/docs/...
But Zig is the charm. TigerBeetle wouldn't be what it is without it. Comptime has been a gamechanger for us, and the shared philosophy around explicitness and memory efficiency has made everything easier. It's like working with the grain—the std lib is pleasant. I've learned so much also from the community.
My own personal experience has been that I think Andrew has made some truly stunning number of successively brilliant design decisions. I can't fault any. It's all the little things together—seeing this level of conceptual integrity in a language is such a joy.
Looking at the bugs themselves, I don't think any low level language would've caught those. C/C++ would've crashed as well (hopefully, at least, many of these problems would be UB and the compiler might just ignore the problem or patch out the offending code) and Rust would've panic'd. There are a few cases where Rust wouldn't have allowed the code to panic but the surrounding code would be pretty unreadable in safe Rust (without stacking types like Box+RefCell+Rc and clone()ing a bunch) so it's hard to compare the two.
The advantage of Rust would be a nice and readable stack trace to the crashing method, but a core dump would've included even more information for the person debugging the binary, so I think it ends up quite even.
I don’t know what’s going on in this thread where encountering UB has somehow been morphed into some kind of guaranteed immediate core dump that’s basically better than panicking anyway. Yes, people are talking about segfaults. But it’s memory corruption. Maybe you get a crash at some point, maybe you do not.
A reminder for all that have forgotten: UB is the one that can email your local council and submit a request to bulldoze the house you’re in. It is not a free core dump.
A sementation fault is well-defined behavior. If you look at Jarred's comment nearby he reveals that the pointers in question are special pointers, e.g. 0x0, 0x1, 0x2, etc.
It is 100% well-defined behavior to dereference these pointers. It always segfaults, which as Jarred mentioned is a lot like a panic.
Rust evangelists need to be careful because in their zeal they have started to cause subtle errors in the general knowledge of how computers work in young people's minds. Ironically it's a form of memory corruption.
I can buy that dereferencing null is a special case, but why is 0x2 special? Is 0x20 also special? What about 0x20000? Are the invalid non-null pointer values listed in a reference somewhere? If 0x2 is an invalid pointer, what do I do if my microcontroller has a hardware register at 0x2?
On many platforms, the zero page is set up so access to it will always segfault. This isn't a language guarantee, but it's a guarantee in most modern operating systems (Linux, FreeBSD, Windows). This is set up for pointers all the way up to the end of the first page.
On Windows and Linux this is the first 4KiB so range 0x0000 up to 0x1000, unless large pages are on (then it's even more).
On macOS in x64 this is the entire 4GiB memory space, probably a method to help developers port their 32-bit software to x64. I don't know what the zero page size on ARM is.
If your microcontroller doesn't have this guarantee, you can't make use of this feature.
That's a guarantee on the level of the hardware/OS, but hardware semantics are not the same as language/compiler semantics. Even if according to the source code you're dereferencing a pointer value 0x0 or 0x2, that doesn't mean the compiler-emitted machine code will end up telling the hardware to do the same.
Once you trigger UB, all bets are off and your code could do anything. A segfault just means you spun the roulette wheel, bet it all on red, and got lucky your house wasn't bulldozed.
Zig also uses LLVM under the hood, right? So it's subject to these same semantics. An LLVM pointer value cannot legally contain arbitrary non-null non-pointer integers such as 0x2. That's a dead giveaway of UB. And I doubt the emitted Zig code safety-checks every pointer dereference for a value less than 0x1000 before performing the dereference.
The semantics are actually operating system and even compiler flag dependent. On macOS you can choose the size of your zero page during build. The numbers I've listed are just the defaults.
Zig UB is not C UB. There is an entire language built on top of it. Just because something behaves a certain way in C, doesn't mean the same thing is true in Zig. Zig is no longer a code generator for C, it has switched to a self hosted compiler a while back. In fact, the language is rapidly progressing to the point where LLVM is a mere optional dependency.
I don't know the semantics around LLVM pointers. I don't see why 0x2 would be invalid, there are plenty of platforms programmed in C(++) that have a flat memory model. It would be quite painful to have a microcontroller where you can't send data to the output pin because LLVM decided that 2 is invalid (but 0 isn't). I've never seen LLVM complain about invalid dereferencing, though, it always ends up doing what the compiler tells it to do as far as I can tell.
Zig pointers will definitely cause UB but most Zig code shouldn't need them. Slices are actually bound checked and should probably be preferred in most cases of pointer arithmetic. Simple pointers can't be increased or decremented so you need to manually go through @intToPtr if you want to do real pointer arithmetic, which is quite unusable.
I haven't used Zig much so I don't know how many Zig semantics are copies of C semantics and how many are translated by the Zig frontend. However, "this is a bad/undefined thing in C so it must be a bad/undefined thing in Zig" is simply not true.
I know Zig is not C, that's why I specifically mentioned LLVM. It's fine if Zig has different opinions about UB than LLVM does, but in that case ReleaseSafe builds should not use LLVM, not even optionally. If Zig says some operation is defined, but LLVM says it's undefined, well, LLVM is the one optimizing code so it's LLVM's invariants that matter. Right now it looks like Zig is playing fast and loose with correctness, shoving everything through LLVM but not respecting LLVM's invariants. And hey, if something is observed to segfault under some conditions today on the current version of LLVM, we'll just say segfaults are guaranteed. It's disappointing to see.
A lot of people have the same misunderstanding as you.
LLVM has rules about what is legal and what is not legal. If you follow the rules, you get well-defined behavior. It's the same thing in C. You could compile a safe language to C, and as long as you follow the rules of avoiding UB in C, everything is groovy.
Likewise, this is how Zig and other languages such as Rust use LLVM. They play by the rules, and get rewarded by well-defined behavior.
Is not one of the LLVM rules, pointers must be valid and have a valid provenance in order to be dereferenced? If 0x2 ends up in a pointer that is dereferenced (or 0x0 in a nonnull pointer), has that rule not been broken? And if the rule is broken, does that not trigger undefined behavior?
I invite you to share a snippet from the LLVM language reference[1] that backs up your interpretation.
I will return the courtesy, with regards to my interpretation:
> An integer constant other than zero or a pointer value returned from a function not defined within LLVM may be associated with address ranges allocated through mechanisms other than those provided by LLVM. Such ranges shall not overlap with any ranges of addresses allocated by mechanisms provided by LLVM. [2]
- Any memory access must be done through a pointer value associated with an address range of the memory access, otherwise the behavior is undefined.
- A null pointer in the default address-space is associated with no address.
A null pointer (0x0) is associated with no address, therefore it has no address range. So if you do attempt a memory access (dereference), the behavior is undefined. QED. A naive translation to assembly would indeed segfault on a modern OS, but LLVM's optimizations are free to assume that code path is unreachable and do anything else.
Once the program is in this state, a bug of some kind is unavoidable. I don't take issue with that - what I take issue with is your claim that this behavior is well-defined, because it definitely is not. It would be equally valid for a null dereference to corrupt your program state or wipe your hard disk.
You have already admitted that 0x1, 0x2, etc. are fine. Your remaining argument rests entirely on the incorrect premise that Zig's only option is to lower to LLVM IR using the default address space.
I don't think 0x2 is a valid pointer either. The docs say the pointer value must be "associated with address ranges allocated through mechanisms..." - to me the word "allocated" means it's the result of an allocation, pointing at usable address space. (Sorry, I know this is a purely semantic argument. Debating the meaning of words does not make for very interesting discussion.)
In Rust for example, derefencing a raw pointer is unsafe - because that pointer could have a value of 0x2 - which would result in undefined behavior according to LLVM.
tbh I'm surprised any of this is even up for debate. If you google "is segfault undefined behavior" you'll get 100 results telling you yes, yes it is.
Are you claiming that any program that segfaults exhibits undefined behavior within LLVM semantics, even those that were not compiled by LLVM? Or within some other set of semantics shared by all programs that can segfault?
I'm claiming that if a program is compiled with LLVM, it must follow must LLVM's rules. One of those rules is that a pointer must be valid in order to be dereferenced. If a program attempts to dereference an invalid pointer and segfaults, it has broken those rules* and thus exhibited undefined behavior. While undefined behavior MAY result in a segfault, it's equally valid for the program to continue running with corrupted state and wipe your hard disk in a background thread.
I'm not sure how I can connect the dots any more clearly. Like gggggp said, it's baffling to see the creator of a popular language sweep the nasal demons under the rug and pretend that certain undefined behavior is guaranteed.
Calling such segfaults "safe" or "well-defined" is setting your users up for disappointment and CVEs, because a "well-defined" result is axiomatically impossible in the presence of undefined behavior. It's subtle, and if we were talking about a Java competitor maybe I could forgive the mistake. But if you're writing a low-level language it's important to understand how this stuff works. Ironically, he spread misinformation in the very post where he accused Rust evangelists of the same.
This thread is long dead and continuing the discussion seems futile, so I'll just leave it at that.
Sure, I think I understand. The claim is maybe that it's legal for LLVM to emit code that (before every pointer access to a pointer obtained from outside of LLVM) somehow checks whether the pointer points to a region of memory that was actually allocated outside of LLVM and does different stuff based on the result of that check. In the face of such adversarial codegen on the part of LLVM, if someone wanted to implement this correctly on Linux, they might need to make sure they actually mapped the pages they wanted to use for crashing with PROT_NONE before using any pointers pointing into the crashing region. Is that right?
Do the docs actually define exactly which mechanisms external to LLVM count as allocating address ranges and which do not? It's possible that calling mmap and passing PROT_NONE does not count, for example.
I wouldn't call codegen adversarial. The optimizer isn't out to get you. It emits the best code it can given a certain set of assumptions. It may just seem adversarial at times because the output can behave in unintuitive ways if you break those assumptions.
I don't believe PROT_NONE suffices. The address needs to be accessible, not merely mapped. If reading through a pointer, the address must be readable. If writing through a pointer, the address must be writeable. This is why writing to a string constant is undefined behavior, even though reading would be fine.
Another issue is alignment. If you read from a `*const i32` with unaligned pointer value 0x2, the optimizer is free to assume that code path is unreachable and, you guessed it, bulldoze your house. If you get a segfault from reading an `i32` from address 0x2, you've already hit UB and spun the roulette wheel.
In theory the emitted code could check pointers for alignment and validity (in whatever platform-specific way) before accessing them, and simulate a segfault if not. Such checks would serve as optimization barriers in LLVM, and prevent these instances of UB. Of course Zig's current ReleaseSafe doesn't do this, and I think it would be silly if it did. But that's the only way you could accurately call segfaults "well-defined".
> An LLVM pointer value cannot legally contain arbitrary non-null non-pointer integers such as 0x2.
0x2 is a perfectly valid pointer value, it just happens to never be a good virtual memory address on modern systems where virtual memory is setup by the usual OSs, hence the fact that you can rely on it segfaulting.
> On many platforms, the zero page is set up so access to it will always segfault. This isn't a language guarantee, but it's a guarantee in most modern operating systems (Linux, FreeBSD, Windows). This is set up for pointers all the way up to the end of the first page.
Then I guess it could be a language guarantee if Zig only supports/targets those platforms. However, considering how low-level Zig is, I doubt that that is the case.
> I can buy that dereferencing null is a special case, but why is 0x2 special?
It isn't, in the general case. But JavaScript engines do some dark magic with pointer packing / NaN boxing as a performance optimization (most things in the VM are single words, passing around a single word is usually way cheaper than full unboxing), and I suspect bun in occasionally running into issues where it gets returned something from the JS engine which it thinks is a pointer but actually it's a packed, special value. This is a logic error, that turns into a weird memory issue at the abi boundary, not a memory safety issue.
> If you look at Jarred's comment nearby he reveals that the pointers in question are special pointers, e.g. 0x0, 0x1, 0x2, etc.
Is that guaranteed by the language semantics, or could it possibly change at some point in the future? If it's the latter, then yes, it is very much Undefined Behavior, and not guaranteed to segfault before opening the door for potential exploits.
> It is 100% well-defined behavior to dereference these pointers. It always segfaults
Not on every architecture, not in LLVM (even if well-defined on the underlying architecture), and not in C (even if well-defined in the underlying compiler backend).
TL;DR: Zig injects checks and aborts the program at runtime unless you specify that you wish to ignore the problem. This can be done explicitly within the code or by compiling under a build mode that ignores checks (unless specified manually).
Programs compiled as Debug and ReleaseSafe will terminate at runtime if UB is triggered. Compiling for ReleaseSmall and ReleaseFast will cause traditional C-style UB. If you care about your program doing what it's supposed to do, you use ReleaseSafe. Doing Release[Fast|Small] will do something similar to -O3 in other languages, which will often change behaviour.
Note, however, that you can compile your code under "just allow UB and see what happens" mode but still benefit from checked UB by setting @setRuntimeSafety(true); this will introduce the assertions despite the unsafe build modes you may specify.
It's like introducing a C++ compiler flag* telling the compiler "ignore exceptions and just continue". You know you're in for a bad time the moment you specify it, but it makes your program blazingly fast because it greatly reduces the amount of code to generate/checks to execute.
The main advantage of checked UB is that well-tested code can make use of the unchecked nature of these features for speed without having length check code blocks that need to be wrapped in debug #ifdefs or similar. Assuming you don't run test builds with checks enabled (and why wouldn't you) you'd catch these problems in your build pipeline.
This is different from the normal way of working with C and friends, where UB remains in debug/-O1 builds but just acts a little differently. Some compilers will insert breakpoints, others will ignore the problem like in release mode, nobody knows what will happen and your compiler can't detect this problem for you.
* note that -fno-exceptions exists, but that aborts the program rather than let it continue.
A panic (deterministic, guaranteed, immediate, and worst-case a dos) is an order of magnitude better than memory corruption (non-deterministic, not guaranteed, eventual-if-at-all, and worst-case-rce).
Most of what manifests as a segfault in Bun have been due to assuming a JSValue is a heap allocated value when it is (the JavaScript representation) “null”, “undefined”, “true”, “false” etc. These are invalid pointers, the operating system signals the memory access was invalid, Bun runs the signal handler, prints some metadata, and exits. This is a lot like a panic
