My Type of Language

I have no formal training in type theory – I don’t have much informal training – I’m still lost when I crack open Benjamin Pierce’s Types and Programming Languages book. I do, however, have smart co-maintainers and a lot of experience banging my head against this small DSL called bpftrace.

As you probably know, bpftrace, the language, is an abstraction of BPF C code, which is itself a restricted version of standard C that runs in the Linux kernel. One of the “value adds” of bpftrace is that users don’t need explicit types. bpftrace is statically typed but the types are inferred. So, in the statement $x = 5, $x is resolved to an unsigned 8-bit integer. For the most part, this was a good language design choice as bpftrace’s goals are to be fast, terse, and flexible. However, this choice has had its issues; both externally in terms of causing strange user errors and internally with how the type system was built.

This post is about bpftrace’s type system and how it’s improved over the past 2 years.

Integer Types

bpftrace has your garden-variety integer types:

• uint8 / int8
• uint16 / int16
• uint32 / int32
• uint64 / int64

You get one of these when you use an integer literal or if a function argument is an integer of the same size and signed-ness (based on BTF or DWARF data). Until fairly recently, bpftrace would automatically promote all integer literals to 64 bits. For the statement $x = 5, $x would be an int64. It was also signed, for the same reason — so that users wouldn’t have to think too much about casting or assigning differently sized (or signed) integers to variables and maps. 5, -1, 50000000 could all be assigned to the same variable without error or warning. It all just worked…kinda.

However, if a user tried to assign a uint64 argument or builtin to $x (after 5 was assigned initially) they would get an error. bpftrace didn’t want to automatically cast a uint64 to a int64 or change the type of $x to a uint64 because that might cause confusing/broken behavior at runtime (e.g. large numbers turning into negative numbers).

If the only assignment to $x was 5 then bpftrace should be smart enough (through static analysis) to accept assigning a uint64 value to $x later. Something like this $a = (uint32)1; $a = -1; should also be valid because $a can be promoted to an int64 and it will safely fit both r-values. This is known as the supremum (least upper bound).

bpftrace now does this. A variable or map key/value is only as large as it needs to be based on static analysis. For $x = 5, $x is now a uint8. For $x = 5; $x = -1;, $x is an int16. Users may still encounter cases where they have to explicitly cast but it’s more rare and less surprising.

There is still room for improvement though, take this trivial example:

$a = 1;
$b = $a + 1;

We know the type of $a is a uint8 but what about $b? I think a sensible person might say it should also be a uint8 or the next largest integer uint16. However, $b is promoted to a uint64 because bpftrace doesn’t yet do dataflow analysis. In the example above, such a thing would be trivial but what if $b was being added to (or incremented) inside a loop where we couldn’t statically determine the number of iterations? Making it a uint64 is a bit of a cop-out but also just a tradeoff in terms of how complex we want to make the static analysis.

Magic Builtin Types

bpftrace has a lot of “builtin” features (pid, comm, kptr, etc.) and, for many of these, bpftrace assigns a special builtin type to them so that:

• we know what LLVM IR to generate in our code generation step
• we know how to handle them in userspace when they’re printed

For example, for printf("IP: %s", ntop(1)) we call additional handling functions in userspace when we encounter an inet type, which is what the builtin function ntop(1) returns.

There are also aggregate map functions, e.g. avg(N), which tracks the average of all the values passed to it. Its type is avg_t, which is actually just a struct with a sum field and a count field.

The issue here is that if someone wants to add a new builtin that requires special handling in codegen and userspace, they need a new builtin type and expansion of all the type switch statements to handle it.

We, the maintainers, are contemplating some form of Duck typing, where if the userspace side of bpftrace sees a struct with a sum field and a count field, for example, then it knows it’s from an avg builtin and dispatches the appropriate printing calls.

We’ve had success making some of these builtins more generic so as to remove the custom code requiring a specific type. We've also removed these magic builtin types from the parsing code but there is still more to be done to improve this part of the type system.

Explicit Types

Even though bpftrace’s types are inferred, there are times when users have to explicitly tell bpftrace the type of an expression:

• Accessing fields or passing around opaque pointers, e.g. $runq = ((struct rq*)percpu_kaddr("runqueues", 0)). Here percpu_kaddr returns an address/pointer and the user needs to tell bpftrace its actual type.
• Explicitly declaring types for variables, e.g. let $x: uint16, which tells bpftrace that it can’t upcast or change the type of $x.
• Using type introspection functions (like typeof, offsetof), which require explicit types or expressions.

(Users also once had to include the correct kernel headers for these types to be available but that was fixed last year.)

Explicit typing for variable declarations is a somewhat “hidden” feature because we didn’t want users to have to know about all our magic builtin types, which are more of an implementation detail, and also because bpftrace had limited ability to properly parse a lot of C types (e.g. it could only handle two levels of pointers).

However, we’ve made many improvements to explicit type handling (available in master). We threw out our flex and bison lexer/parser and replaced it with a custom recursive descent parser. This new parser can handle:

• (almost) any level of pointer depth, e.g. let $x: uint64********
• array types for any base type (it was previously restricted to a subset of magic builtin types)
• complex nested types, e.g. struct Foo *[2]
• typedefs, e.g. zstd_out_buffer
• ambiguity with cast expressions that were once misinterpreted as binary operations, e.g. (sometype)*$x, which is now parsed as a cast unless the wrapped identifier is a known builtin like arg0

bpftrace also got smarter about resolving known typedefs. $x = (uint64_t)1 now works as expected and users don’t necessarily even have to know about bpftrace’s representation of a 64-bit unsigned integer (uint64).

This work removes a lot of concern around exposing explicit types to users, which also benefits the new C-interop feature. However, we want to continue promoting and improving bpftrace’s type inference by leaning into BTF and DWARF. For the most part, bpftrace should be able to determine the types of variables and arguments without user intervention.

Internal Type Resolution

When I started working on bpftrace, there was a beast of a class called SemanticAnalyser, which was thousands of lines of code and dealt with type resolution/inference, type checking, and other forms of “semantic analysis”. This class would walk the generated AST from roots to leaves exactly 10 times. I’m guessing 10 was chosen because it was a round number and, surely, bpftrace wouldn’t need any more than 10 AST walks to finish resolving types. The latter was mostly true; we didn’t get many user complaints but back then bpftrace scripts were pretty small and no one was doing something crazy (and contrived) like:

interval:s:1 { @k = @j; @j = @i; @i = @h; @h = @g; @g = @f; @f = @e; @e = @d; @d = @c; @c = @b; @b = @a; }

(note: the above script needed 11 walks)

One of the first things we did was remove this hard-coded 10 walks and build in a mechanism to see if we were making progress on type resolution after each walk (meaning more types were resolved after every subsequent walk) and error if no progress was being made (like in a recursive situation: @a = @b; @b = @a). This was a good temporary fix but one new feature exposed a large gap in the way type resolution worked: comptime.

comptime is similar to constexpr - its following expression is evaluated at compilation time, as opposed to runtime. Let’s look at an example:

$x = 1;

if comptime (sizeof($x) == 4) {
  … do something
} else {
  … do other thing
}

In this example bpftrace should be able to determine the type and size of $x, evaluate the comptime expression and, depending on whether it’s true or false, prune the if or else branch before generating and running BPF code (more detailed walkthrough of comptime).

So why is this a problem for type resolution? Let’s expand this example:

$x = 1;

if comptime (sizeof($x) == 4) {
  $x = (uint64)arg0;
} else {
   $x = (int32)arg1;
}

$x = (int32)2;

Do you notice the contradiction? We can’t prune one of the branches until we know the type of $x but knowing the type depends on what branch we don't prune.

This required a more sophisticated type resolution solution (my new band name). The first thing we did was split up the giant SemanticAnalyser mono class. We separated out function/builtin error checking into a separate class (cleverly named PreTypeCheck) then we extracted out many of the errors that required having type information into a class called TypeChecker. The idea was that the class doing the type resolution should be doing one job; not 10 and not 10 times.

If you want to read about how this whole thing works, there is now a doc in the repo. The final type resolver is based on a lot of iteration and reading about actual type theory (specifically constraint-based solving - even though Viktor claims I'm slightly misusing that term).

So how does bpftrace now solve the contradiction above? The type resolver uses a simple map to keep track of variables/maps that were used in type introspection functions (e.g. sizeof or typeinfo) and “locks” their type prior to visiting branches guarded by comptime expressions. The above code now yields a type error. However, this code is valid:

$x = 1;
$y = 2;

if comptime (sizeof($y) == 4) {
  $x = (uint64)arg0;
} else {
  $x = (int32)arg1;
}

$x = (int32)2;

And that’s because the type of $x is not used in any type introspection functions - it doesn’t need locking.

Another nifty thing to call out is how bpftrace now handles injected casts. Let’s say you had this block of code:

$a = -1;
$b = (uint32)2;

if ($a == $b) {
 ...
}

Here it's comparing a uint32 and an int8. We don't want to change the type of either $a or $b but rather just make them compatible for comparison. Using our friend “least upper bound” again, we can insert casts on both sides of the comparison so that LLVM is happy comparing the two, e.g.

if ((int64)$a == (int64)$b) {
  ...
}

This also happens for ternaries:

$a = -1;
$b = (uint32)2;
$c = true;
$d = $c ? $a : $b;

becomes

$a = -1;
$b = (uint32)2;
$c = true;
$d = $c ? (int64)$a : (int64)$b;

We could easily do this up-casting in the LLVM IR generation layer but it’s less explicit and requires special codegen plumbing. Users can also debug AST transformations, like injected casts, via the debug flag -d ast.

Type Next

bpftrace is in a much better spot today with its types than it was 2 years ago; it has gotten better at inferring types, resolving them, and allowing users to explicitly type them without issue. However, there is still more work to be done and internal tech debt to pay off. This is valuable work if a language like bpftrace wants to be successful, because when users are debugging production issues at 3 AM, the last thing they should be fighting is their tool’s type system.