What we have dubbed reachability analysis, and that requires a little bit of explanation,
so we'll get to that.
So, a little bit about me.
My name is Danny Hammewing.
I'm a software engineer at Isolvalent, which is now part of Cisco.
I am a Selium Committer, a Selium is sort of at where the focus of the topic today.
I'm a maintainer of the EBPF Go library.
So, our Selium EBPF, if you're more familiar with that,
and I also maintain the EBPF docs for anyone who has seen that before.
So, I'm standing here on the podium, but I would also like to acknowledge
my colleagues of mine, Timo and Robin.
Timo has co-authored a lot of the work that I'll be presenting here today.
He's a co-maintener of the Selium EBPF project, and Robin, who didn't, I don't think,
directly worked on this, but he did review everything and gave us great feedback and stuff like that,
so I wanted to acknowledge him as well.
So, let's get in.
So, we have been on a sort of journey to modernized Selium.
The Selium is now 10 years old, actually one of the first users of EBPF ever.
So, there's a lot of history there, and there's also a lot of technical that.
So, one of those interesting things is that if you would write any project,
EBPF project today, or most of you, we'll probably compile ahead of time, ship your
programs as an elf, only your target, and then just vomit at it, and use the nice,
little, the nice core facilities to make sure that it works everywhere.
However, 10 years ago, all of that didn't exist, so back then, we decided to just ship
all of clang, and all of our source code, always to target, modified it slightly for whatever we
need it, and then run it, and we don't want to do that anymore, because we don't have to any more,
but we have to technical that, so, there's a few reasons for doing that.
If you don't have to compile, it's faster, compilation is really slow.
If we don't ship clang, we have smaller images, we get a little CBE reports,
unlike parts of our images, which we didn't, we don't use.
They're like standard libraries that we had to import, because we also have clang.
We can just get rid of all of that, where we have lost a look-less security,
right, things, and hopefully, if you don't have a whole compiler in the loop at one time,
there's, it's, hopefully, going to have less bugs. But this has been going since 2003.
I found the issue that democracy had back then, and we're still lurking on this, but we're really
we're getting really quite close now. So, the key in making this happen is low-time configuration.
So, we can't do things at compile time anymore. We need to shift everything that happened at compile
time to happening at low-time. Sillium is really complex, and it has a bunch of settings, options,
a little of optional features. In fact, I counted them. At the moment, we're like,
halfway through this conversion, but we have 94 different settings. They're being Boolean's,
numbers, IP addresses, that sort of thing. That all need to, that all go into the data path
at low-time. All compile time before that, but again, we're migrating from that.
We used to do this with pre-processors macros, so we would conditionally compile
bits of the code that we weren't using, and then a compiler would take care of all of that.
But now, we compile everything in. Now, you need to at low-time disable or enable that.
And the two bits, the two patch series that really made this happen for us are linked here.
So, actually, the verifier can do death code elimination. So, what it does is, if it
you provide it a variable, and it knows that this variable is always certain, like a static,
you have a branch like an if statement, and it says, okay, hey, this branch is always taken or never taken.
It can completely, it realizes one bit as that code, completely removes it. At least, if you're running
as a privileged user, although I suggest patches that are within most and jumps off it,
the other thing that makes this happen is tracking of the read-on in maps. So, if you have a
global variable, like, so you get sort of the code that I have here. So, if you have a global variable,
that gets put in a map, and a bpf map, that's how global variables work in bpf.
If this read-only, so constant, and you freeze it when you load it, the verifier says, hey,
that the content of that map is static, I'll just treat it as a scalar value, as a, as a, as a
number, and then it flows, and then it works. So, you can write code like this, where you say,
I have to make it volatile, because otherwise the compiler gets smart on me, but if you declare it
like this, if a volatile const, I can change this constant value from user space, and I can actually
enable or disable code in my bpf program, that will be completely removed from the jittered output.
I'll show that example. So, this is what we use to do. So, the question now is, okay, cool,
I can, like, control constable bits of my code, but how do I, how do I do this with maps?
One of the core values of Sillium is that if you disable a feature, you don't pay for it,
you don't pay for the CPU, you don't pay for the memory, you don't pay for bpf data path complexity.
So, if I, if I'm close to a complexity limit, for example, which used to be the case more,
nowadays it's less of an issue, but if that's the case, then I can disable a big feature,
and I can enable more smaller features. That's the idea. So, you can use the user chooses what
they want to run, and we just make that happen in a small case. But it also means that if I have
feature A, which uses a map, how do I now make sure in this new world that I do not have to
this map load it and there. So, this is what we had, and then you say, okay, we know the solution,
let's do the naive fix, we create this global variable, the constants, we wrap our usage code,
and then sure we have to provide the map initially, but surely after that map is free,
because the only place that uses it is going, so we know the program that uses a map gets unloaded,
it also removes your map. But unfortunately, unfortunately, unfortunately, that's not the case, actually.
So, don't be scared, this is like bpf, this is simply, but it looks like almost like c. So,
I'm going to help you steer it. The things I want to look at are, have the red line under it.
So, the first thing that happens is we check our Enable flag. So, we load the red only map.
We load some, we load the Boolean from that, it gets checked, and that's like. In this case,
we have it set the true, so the body of the function still exists here. And then a body,
we have the second map, which is the one we wanted to get rid of, if we don't use it. And then in the
output, if we inspect, which maps are associated with which programs, we can see both maps are associated.
Expected, that's normal. So, let's now disable this feature. So, disable my feature.
We still have the red only map. We don't have the map anymore that I want to get rid of,
but it's still associated. What gives? So, it turns out that it is a work of the way that
verifier works at the moment. This is slightly technical. You can download the slides later and
then follow the nice links. Essentially, what happens is in the verifier, in your nother program,
there's a function called Resolve Studio, load IMM64, which is a little bit verbose.
But every time you pause, file the scriptors for maps into the kernel, it converts these into
into the actual pointers to the map, because at the end, kernel needs to work with the actual
map SSDs in the kernel. It doesn't flood scan. It maintains this list of the use maps,
which is what you see when you dump the program listing. And it increments the graph count.
We make sure that this map stays loaded in the kernel while we are still using it.
Then, the majority of all verification happens, like all the complex things to be
relevant hate. And then, at the very end, once we have, like, good on all of the, all of the
all the interesting things, there's this optimization pass, which is the way the death code
elimination that I talked about earlier. It happens in three stages. So, first, it detects
the branching thing, and it like hardwires it to normal jumps. And it puts like no ups in between.
And then, it will actually gradually in steps, like we move the no ups and make it so that
it's completely gone from legit to output. But the interesting part is that we never, if we
remove the last usage of this map, we never released a ref count, we never removed this
from this use maps. So, it means that even if I, after death code elimination, my map is still
associated, that still holds on to the memory, even though it can never use it. So, that is just
the state of things at the moment, and I'm sure that can be improved. So, we have to work around this.
So, the first work around that we thought of was to do a double load. So, we would load our
program once, but instead of loading, like maps that allocate like a megabytes of space,
we would just set the motor to max entries of one. So, we still need to create the maps,
but it's not that bad. We load our program, and then we can read it back and see, hey,
we see that exactly these maps were eliminated, and now we can reload the program with the actual maps
that we're going to use, minus what we determined is unused. And then, for the place,
is where we had the original unused maps. We patch out the file descriptor. So, if the funny thing,
even if you can't just set the file descriptor to zero, that always has to be
like valid, but you can basically tell the load instruction that is not loading a
file descriptor, but just a scalar number. So, that's what we do. We make it a scalar number,
recognizable hex code, so that if we ever see it in an error message, then we know,
okay, this is probably due to some bug in our logic. And then we, and then after this, we load again,
and this works, like actually worked it decently, except for the cases where it doesn't.
So, one problem with this is it takes a really long. We, Selium, has really big
programs. We have 50 tail calls all together. Not all of them are always there, but like,
we have a big programs, big tail calls, it can take like a significant like 200,
200 milliseconds to load big programs. So, that's really undesirable, takes a little CPU, a lot of memory,
et cetera. If you've still created all these maps, and also there is a limit in the kernel,
where you can only use like 64 maps at max. And even, I think Selium currently has 80, 80,
something maps defined. I would have to look it up again. We have a lot of maps. And of course,
we don't all, we don't use them all at the same time, which is why we want this. But if we still have
to like initially load with all of them at the same time, there's a chance we are going to run
over this limit at some point. So, we don't avoid that. If I have to load a map, that might
not be supported on a current kernel, like a arena map, this doesn't work, because I have to initially
load it still, create it, to be able to do it the first time. And the last thing, which we actually
discovered, like later on after we decide to switch off of this work, work around already,
is that if you have a combination of CtL enabled, it actually prevents you entirely from reading
back loaded instructions to get it instructions and even the accelerated instructions. And if that's
the case, this approach just wouldn't work. So, if you're on a very secure system, this just wouldn't
wouldn't have been a wounded if impossible. So, we may, we thought okay, second work around,
slightly like maybe even simpler, or like in principle, it's simpler. You just match whatever you
do in C and go in your user space. So, if you say in C, I only use this map if these features are
enabled, then I match that in my user space. But now you have two places, they need to keep a
sink. If you've ever done this, you know, it's very difficult to maintain. We have a lot of
maintainers, a lot of people that might not know about this. A lot of chances for this to go wrong,
and if we make a mistake, our programs just will not love, will not run, will not do anything.
So, we decided, this is just not what we won't learn term. And thus, we landed on
pitchability analysis. So, the idea of reachability analysis is, what if we knew, reach instructions
were reachable before we were even, we had even loaded them into the kernel. So, this is essentially
recreating a very, very small verse, a bit of the verifiers, specifically for these loads,
I'm configurations. We adopt this reachability analysis, and this is actually applicable,
not only to maps, which is like the menus case I'm presenting, but also for tilt calls with
hard coded slots, and BPF to BPF functions, specifically global BPF to BPF functions, where
if I know, I don't have to, like, if I don't use them, I might be able to just completely avoid
loading them in a kernel in the first time, reduce a lot of time loading programs into the kernel
that I've done never end up using, same from maps to same for global BPF programs.
And it actually addressed most of the concerns we had with other deodorant approaches, so we
don't have to load maps ahead of time, we don't have to do a bunch of things. The only thing is
engineering effort, because now we have to do these interesting things in user space beforehand.
So, how does this work? How does reachability analysis work? So, first, we need to break up our code,
so I took the same or the code of this example program, we need to break this up into basic blocks.
And a basic block is a block of code, so the sequential assertions that are guaranteed to run together.
So, the way you do this is we first go over the code and we identify all of the branching instructions
that we have here, and we say, okay, that's the end of a block. So, we start the one big, big list,
that's the end of a block, and now we identify all of the points where we jump to,
and every time you jump to it, that means that these instructions don't
might not execute always together, so that's the start of a block, and that's our, this is our
block list. So, we get this list of blocks, they execute, and now we can make assertions about these,
and if we visualize this, you get something like this. So, we have this, we have our entry block,
it can jump all the way to exit, it can do these other things, you might have seen this if you are
into reverse engineering, or into compilers, or that sort of thing, and add a little bit of
annotation here. So, when we do this, we maintain some metadata, we say, okay, we have a branching
block, a fallback block, and we have a list of our parent blocks. The bit I left out of this is
BPF functions, because it didn't fit on the slide frankly, but we also maintain a list of if we
ever do a function call to BPF to BPF function, that doesn't, it's not branching, because it will
always return, but we maintain that just so we can always discover, so if a basic block is
reachable, then we also say, okay, that BPF function is not also reachable, and we can recurse through that.
So, that's not here, but it does exist in the actual code. So, we've done all of this, we have our
block list, now what? So, now we need to discover where our load time configuration is, and if you go
look at the instructions, this is whatever, if you have these like volatile comes, then this is what
it looks like. So, you load the pointer to the map, the read-only map, so it's every, all of your
constant values, living the same map in the same array value, so it's on array map with only one
entry, and it's a really long thing, and it actually, they take the L, read-only data section,
it just put it in a map. So, we have this map, we take an offset, so we need to, we need to know the
same map, and in blue, we have the offset, here it's the only variable, but you can imagine that
that if you have a lot of them, then every variable has its own offset, it gets loaded into
this, into this green register, and then that green register is compared, in this example,
it's an equals operation to a, like an IMM value, so it's a value that is encoded in the instruction
itself. And this is essentially the basic, the easy example that we look for. We know that we know
this is a branching instruction, so it must live at the end of a block, so when we go and do this,
we can just loop over all of our blocks, we see as the last block a branching instruction,
and then we backtrace from that, so we go look and see if we can find a case where we find these
instructions, and of course we can't be clobbered, so if we loop and we find that between these two
instructions, our one gets repurposed for something else, and of course we haven't found it, so we're
looking for this very positive pattern of, okay, we need exactly this, but there are some variations.
Now, if once you've done this, you can actually, because we know which variables work on
a lot with, because we already have the map value essentially prepared, we can just predict
the outcome of this branching instruction, so we can say, okay, either this is always branches,
or there's never branches, and then that has implications for our blocks, because if we now know
that we can remove the green or the red arrow, now we suddenly know that, hey, these blocks are
unreachable, or they might be, so we don't need to implement a whole verifier, but we only need to
implement this slight bit of it. And of course, it's not as easy as just looking for these things,
instructions that they are sent to each other. So one of the things that can happen is a verifier,
or a compiler that's smart on you, and they're like, okay, so we're going to first load our
this variable that we're going to compare with, and then we're going to insert a bunch of all the
random instructions, including an other branching instruction, and only then are we going to use it.
So, now we need to deal with this. The way what we've done is we looked at, like, specifically
silly them, and what happened, what occurred, and what we found it in, like, essentially all the
cases that we were able to find, there's usually only one ancestor, like, only one parent of the
basic block where it is happening. So we don't only just backtrack in the local basic block,
but we can also say, okay, if there's only one, exactly one parent, we can just treat it as
a set that was also a basic block, because you can only get into this block if you go via via this
virus, or one. So we implement this, and that can actually follow over multiple, and it's again
a search that this register doesn't need to be covered. Your water, interesting, interesting cases,
so if you have a signed, in this case, I made a signed 16-bit integer, and if the compiler decides
to use a 64-bit comparison instruction, now you need to 64-bit numbers, which are the 16-bit
number, which you always load as a signed. If you were to just put this in here, it wouldn't work.
Register a 64-bit, the CPU things that if you even if I load only 16-bit into it, it'll
still 3-bit, 3-bit as a 64-bit number, so compilers do this clever thing, where they shift the
number up, and then use a signed shift down, so it preserves the sign, and now you basically
cost your 16-bit sign number into a 64-bit sign number. But we have to account for the fact that
this register might change and also how we need to track how the actual map value evolves so
that it matches, so that we accurately can predict if it works, and only we're in CPU instructions
to the ISA-FEC. There's variations of this, where it uses 32-bit numbers instead, because we
go to instructions to do this. So there's a bunch of logic here, same goes for unsigned numbers.
It can be that it's masked off, so you actually need to implement these like mask
operations as well, and even masking and shifting if it was for example a bit
field or something like this. Then the last one, I made a mistake on this slide, bonus points
for anyone who spots it, but what is the late, I think, this is the last interesting case
that I'm going to handle, one of the second one. If you have two 64-bit numbers, and you want
to compare them, the compiler actually does this, so it uses a register register compare and puts
a constant in the second register. The reason for this is that these like this IMAAM value that
was encoded in the comparison instruction is only 32-bit, so if you need to do 64-bit
constants, it does this all the better. So you need to keep track of how this is of
so we needed to keep track of this pattern as well. And then the very last edge case, which
unfortunately we had to do some actual macro stuff in our code, is this. Sometimes the compiler
gets even more clever, and it says, okay, you use this variable like you check for this feature,
flag like 16 times, perhaps we should store this in a stack. But this makes it really difficult to
find this pattern without implementing a whole verifier. So if it does this, where it saves it into
some register, and then it reads it back like 40 basic blocks later, and that's really annoying,
and we just decided to just move handle this case. And the workaround that we found is if you
change the way you write the code slightly, we can trick the compiler. So what we say to the
compiler is in this ASM block, we always want to dereference, so we always get this value, we always
want to dereference it, just always emit this right before the branching instruction. So we essentially
force it to color the branching instruction and the de-referencing instruction. This one,
we put these together, and then I believe, almost guaranteed, it will also put this R1 instruction
next to it. So it isn't perfect, but it improves the reliability of this enormously.
And that sort of brings me to final conclusions. So reachability analysis, this whole concept
seems like a good tool for optimization, because it reduces a lot of, it reduces a lot of time,
I remember using it during loading a bunch of these other things. Although I would really also
like to see the verifier get improved, it would be really cool if the verifier could like,
if we could teach the verifier to just release these maps, if they get that code eliminated.
But even if that, even if that were the case in the future,
we would likely still be a place for this logic, just for the, just for the tail calls and
the BPF, the BPF functions. It should be noted that the system airs on the side of caution,
so we always keep maps unless we can absolutely prove that they are dead.
So the system has false negatives, but doesn't have false positives.
And I wanted to basically put this question to the audience as well. It's like, is this,
this very silly specific use case, like we ran into this, but do other people maybe
see a use for this code, would this be something, or people are interested in? And something I,
I just throw away thought perhaps, like, could we make this work with signing, or does this,
does doing this usual space stuff, like make, make true signing in some way,
where it's difficult or impossible? Interesting things to, well, maybe maybe we'll do a talk about that
whenever, whenever I figure out the answer, the answer to that. Then before I go to the
questions, I realized, I completely forgot to put the link to all of this code in the slide,
which is sort of sad. But I do, I do have it, so if you, it lives in the Selim repository at the moment,
so under package BPF analyzed, you can just look at it, see what this does. I believe you can even,
if you wanted to copy, copy just this code, use it elsewhere, or import it for now, you would need to
import like the whole of Helium, which is a bit excessive, but like you can already play with this today.
And yeah, perhaps if, if we do, if this does end up being useful, we might just split this out
into some separate repository, isn't it? So, and that brings me to two questions. If we
still, I don't know how much time we exactly have left. Maybe one. Maybe one. Okay.
Where are one, one hand going up?
Hi. Very interesting presentation. Thank you. I was wondering if it's possible, instead of doing
this analysis in user space, to somehow probe the verifier to get the information that you need about
the reachability of certain blocks out, so then you just let the verifier do the heaviless
lifting and data entry. It brings that the double loading problem, of course, but maybe you don't
have to implement that's complicated analysis in user space. Yeah. So, what I, so technically,
you can, you can just fix this with, if the verifier were to like release the map rough count,
then you could just load your, you still have to dig maps, you load them, you have like a peak of
memory usage, and then they just get released afterwards, so it's like it's not as nice as this,
but it would be a way to avoid a lot of the user space work. I think that would be a good way
for it to lose for the maps on the map side of it now, right? I'll go make room for the next speaker.
Anyone that has the latest study to work on the verifier regarding the map rough count?
I haven't, I haven't started working on this, but I really look forward to seeing if I can get
if I can get a kernel patch upstream for the right. Thank you, Dylan.