Welcome everyone, today we are going to talk about walking native stacks in BPF without
frame pointers.
So my name is Roy Shally, I work at Polar Signals as a software engineer, I mostly work
on profilers and eBPF related stuff and before that I have worked in different kernel subsystems
as part of my job.
My name is Javier and I have been working at Polar Signals for a year, mostly working
on native stack and winding, so the work that we are going to introduce today and before
that I was working on web reliability, tooling for developers and performance at Facebook.
Yeah, so before we dive into the topic, I wanted to go through the agenda.
So first we actually want to talk about why there is a need for a dwarf based stack walker
in eBPF because that is like the most asked question, then we will go into the design
of our stack walker and then we will talk about how we went from the prototype to making
it production ready and then a bunch of learnings so far on some future plans.
So as we said, we work on the production profilers which means that generally sampling profilers
collect the stack traces at particular intervals and attaches values to it.
Note that the profilers generally need like the user and application level stacks as well
as kernel stacks and it sort of involves iterating over all the stack frames and then collecting
the written addresses.
Historically, there have been a dedicated register for that called frame pointer in both
x86 and 64, but in recent times because of some of the compiler optimizations, it has
been mostly disabled in most of the runtimes as well as in distros.
Also it becomes really hard when you don't have frame pointers and instead of involving
a couple of memory accesses per frame which is like quite fast, we will need to really
do more work in the stack walkers.
Note that the stack walking is like also a common practice in the debuggers as you all
know.
So what's like the current state of the world?
Well, it's not a problem for the hyperscalers because hyperscalers actually have all the
applications which are already enabling frame pointers in production and this is important
because when the things break and you want to really go through the inspection, it's
really helpful to have all the stack when it's needed.
There's also a recent discussion in the Fedora mailing list, so just feel free to go through
it.
TLDR of that discussion is that it's being, so FPs are going to be enabled.
Since I think Fedora 38, so that's about to be released in late April, Mac or software
always have binaries which has frame pointers enabled.
There's also an amazing work going on by Oracle engineers to have a simple format instead
of Dwarf and we hope that that work also goes through and helps the ecosystem.
So that's like sort of the current status, but what we want is we want that right now
and we want the support for all the distros as well as all the runtimes which is like
scattered here and there, for example, only go runtime, enables FPs like since go 1.7
and in x86 and since 1.12 and 64.
So now some of you might be wondering if not frame pointers, what do we have?
For example, say in Rust where it has been disabled by its own, by default, but even,
but when you have the panic, you still get the all mattress, so how is it happening?
So well, compilers always have this information and we generally need to know the value of
the stack pointer in the previous frame and it can be like from any offset if there is
no frame pointer.
So that way we can always like find the value of the return addresses and continue unwinding
the stack.
This information is generally encoded as part of.ehframe section or.debugframe section
in the Dwarf and there is also another way which is like unwine tables can be also synthesized
from the object file which is something being done by orc format that has been used in kernel
for a while now.
We will talk in detail about.ehframe in a minute, but first of all, let's see if anybody
else is using.ehframe already, of course.
So the profiler we have developed is not the first thing who is going to use.ehframe.
Perf, the popular profiler from Linux kernel, added the Dwarf support in since like when
the perf event opens, this call was added which was like in 3.4 and it can collect the registers
for the profile processors as well as the copy of the stack for every sample.
While this approach has been proven to work, there are a bunch of drawbacks to it.
For example, one of the things which perf does is it actually collects all the stacks
and copies it into the user space.
The second thing is that the implications of one process having another processes data
in the user space can be quite complicated and also be it's like a lot of data especially
for the CPU intensive applications.
So why BPF? Stack walking in BPF for our profilers actually makes a lot of sense to us because
in that case we don't really have to copy the whole stack.
The information, a lot of it still stays in the kernel which provides like higher safety
guarantees especially in the case of like stack walking mechanism.
Once it's been implemented, we can like sort of leverage the perf subsystem to get the
sample CPU cycles and then instructions, altricache misses, etc.
And it can then also help us to develop other tools like allocation tracers, runtime specific
profilers for example for JVM or Ruby, etc.
So some of you who are probably also familiar with BPF may know that there is already BPF
get stack ID so why there is a need for implementing something different.
Well, as it turns out, the problem with that helper is that it also requires frame pointers.
So it also uses frame pointers to walk through the stacks.
And for the historical reasons, fully featured DWARF unwinder is like unlikely to be part
of the Linux kernel.
So before we dive into how we are using EH frame with BPF, let's look at what EH frame
actually has to offer.
So the EH frame section contains one or more call frame informations.
The main goal of the call frame information is to provide answers on like how to restore
every register for the previous frame at any part of our code execution.
Directly storing the table, that sort of contain each program counter and all the registered
and then locations such as like whether they have been pushed to the stack or not, etc.
would generate huge unwind tables.
And for that reason, DWARF is actually quite compact and very space efficient in that sense.
So the unwind tables encoded in the CFI format are in the form of upcodes and those upcodes
needs to be evaluated.
So in the case of stack walking, once it has been evaluated, we generate the table that
contains for each instruction boundary like how to store the value of the register.
There are two main layers to it.
One is that it helps with repetitive patterns that compress well and allows for like more
compact representation of some data.
In some cases, there is like also a specialized opcode that consumes say 1, 2, 4 bytes rather
than just 4 bytes at like all time.
And the second layer, which we call the second layer is the spatial opcode.
That contains like the other set of opcodes, which is like containing the arbitrary expressions.
That needs to be evaluated and that's like a lot of work.
The main difference between these two is that in the first one, we just need like these
two values.
But in the second part of it, we will actually need to evaluate like the arbitrary during
complete expressions.
So for that reason, we would need to have like the full blown VM to be implemented in
the BPF itself, which is not quite practical.
So those who don't know how like generally the BPF applications flow works.
This is how it would look like in a very, yeah, very high level point of view.
So like in the user space, you would have like the driver program written in go.
Like that's that's our stack and we are using likely BPF go over there.
We are doing like creating the maps, attaching the BPF program to a CPU cycle perf event.
It reads parses and evaluates the EH frame section of the process and like all the dynamic
libraries.
And in the BPF program, we have using the PID, we are fetching the table.
And then we have like an unwind algorithm, which processes that work information.
We will go in depth for each component, but let's see how the algorithm looks like.
So basically for this one, it's like a really simple one.
But basically we just read like three important register.
First one is instruction pointer, RIP.
Next one is the stack pointer.
And the third one is, of course, like frame pointer, RBP.
And then when the frame count is less or equal to the maximum stack depth we have defined,
we find the unwind table for the program counter.
We are the instruction pointer to the stack, calculate the previous frame, frame stack
pointer, then update the registers with the calculated values for the previous frame and
then continue with the next frame.
So there's like just a nutshell that's what the algorithm is in the BPF.
But now the important part is how we store that unwind information and what we have done
to make it scalable.
So now Javier will talk about that.
Cool.
So now we have some unwind information that we're going to describe the format later,
but we need to put it somewhere, right?
So one possibility would be to store this unwind info in the memory space of the applications
that we are trying to profile.
And we could do this, for example, using a combination of ptrace, mmap, and mlock.
And we could use ptrace to hijack the process execution and allocate a new memory segment.
And then we will have to lock it because in BPF we need to make sure that the pages that
we are accessing are never going to be swapped out.
But this has a big problem, that is, that will be altering the execution flow of the
program.
And it's something that we never want to do.
One of the reasons for this is because, first, this memory will live in the process, which
means that accounting for it will be odd and developers will find a new memory segment
there that appeared out of the blue.
So in their metrics, there will be something that changes behind their backs, which is not
great.
But also because the lifecycle of managing this memory chunk is very complicated.
For example, what do you do if our application, if our profiler dies before the processes
that we are introspecting?
How do we clean this up?
It involves a lot of, that's a lot of problems and adding solutions to these problems will
require like crazy engineering, which we were not planning to tackle because it will over
complicated project a lot.
The other problem is that sharing memories way harder and accounting for our overhead
is also very hard.
If you think about it, for example, Libc is probably linked in most of the applications
in your machine.
So why having the same information like for every single process, right?
So how do we actually store this information?
We use BPF maps, which are data structures that, as Shali said, they can be written and
read both from kernel and user space.
We use in particular hash maps, which in the case of BPF, they are basically a mapping
of bytes to bytes where you can put arbitrary information.
So this is always locked in memory.
BPF allows you with this flag not to lock memory, but in the type of BPF program we use,
it is mandatory to lock it.
Otherwise, as we said before, these pages could be swapped out and from the type of
BPF programs that we have, page faults are forbidden.
And yeah, in the end, we could reuse these mappings because they are in this kind of
global BPF map that we have control over.
So we can store, for example, Libc in one particular area, and then we'll have to add
metadata for where it is for every single process that has this mapping.
So yeah, this is a logical representation of our information for different executable
segments.
So imagine this is Libc, MySQL, Zlib, SystemD, and then some tank that isn't used.
So this assumes that we have this logical view has a chunk of memory that is contiguous.
But in reality, we cannot allocate any arbitrary chunk of memory in BPF.
We cannot say we want 200 megabytes and it needs to be contiguous.
We cannot do an malloc, right?
So we've been doing some experiments and in the systems that we have tested and the kernels
that we want to support, we can add up to 250,000 wine entries to each value of a
BPF map.
So because we want to be able to fit larger wine tables, we basically use the same solution
that you would use in any other data intensive application, which is partitioning or sharding.
So we are splitting the wine table into different shards and depending on the memory that your
machine has, we'll allocate more or less shards ahead of time.
That will result in a CPU to memory trade-off because when they get full, we'll regenerate
them.
But we'll talk about this later.
So for example, let's see SystemD some wine table and let's suppose that it's a bit bigger
than 250,000 elements so it doesn't fit in a single shard.
So because it doesn't, we have to chunk it up.
So we store the first chunk in the first shard and then there's a little bit that it's stored
in the second shard.
So we have added all these layers of indirection.
We need some bookkeeping to do and this metadata is also stored in BPF maps.
So we have a process that can have many mappings.
Each mapping can have one or more chunks and then each chunk maps to a particular shard
because you might have one and wine entry or up to 250,000 in a shard.
We have some other metadata to exactly tell you where that information leaves.
So yeah, thanks to this way of organizing data, we're able to, as we said before, share
these executable mappings and thanks to that, we skip table generation for most of the executables
in your box.
And thanks to this, we only use 0.9% of the CPU cycles doing the process that Vashali
was talking about before, which is not the most complex process in the universe, but
it consumes some CPU cycles because we need to read some information from your L file,
find the section, then we need to read the section and we need to parse it and interpret
the dwarf information.
So now we need to do way fewer times.
So in your machine, we're only going to do it once per unique executable section.
So what happens if we run out of space?
So basically what we have implemented is basically a bump allocator.
We keep on appending information to the shards and logically you can see it as a big chunk
of memory.
Once it's full, at some point, we'll decide to wipe the whole thing and start again, but
we do it in such a way that we give every single process a fair chance of being profiled.
So yeah, let's take a look at how are we doing this.
So we start with a PID of any process that you find in your machine that at that point
happens to be running on CPU, and the first thing we do is to check if it has unwind information.
If it does, we need to find the mapping with the current instruction pointer that we have
for that frame.
Then we need to find the chunk.
We can find it doing linear search because we have the information of every single, like
minimum and maximum program counter that is covered by that chunk.
Once we get the chunk, we can have the shard information, and once we have the shard information,
we have the unwind information.
But the problem is the unwind information, as we said before, it's basically an array.
On this array, we need to find it there, but it can be up to 250,000 items.
If you have done anything on BPF, you know that you have to basically build whatever
you need yourself, and you don't have, for example, some sort of binary search that is
executed on kernel space for you, so you need to implement it yourself, which is not a big
deal in general.
Implementing binary search is not rocket science, but the problem, most of the times, it's difficult
to get all the off by once, but the problem here is that in kernel space, we have a lot
of limitations we're going to talk about later, and we're going to talk about how we overcame
them, because this produces quite a bit of code that has to be split logically.
Not only the data structures are sharded, but the code is sharded, too.
So anyways, we binary search this with up to seven iterations, but let's say eight, if
you're feeling pessimistic, and then we're going to get the unwind action.
So what is the operation we need to do to the current registers to recover the previous
registers, and add that frame to the stack trace, and continue with the next frame, as
I shall explain before.
If the stack is correct, and we have the luxury to know that, because when we have known one
information, and RBP is zero, that is specified by the X64 API to be the end of the stack,
the bottom of the stack.
So if it is correct, we hash the addresses, add the hash to a map, and bump a counter.
So it is reasonably cheap, and I will show you some data later on this.
And then every couple seconds, I think it's every 10 seconds or so, we collect all this
information from user space, and we generate the actual profiles that we send to some server.
As I said before, BPF has some interesting challenges for us.
I think it's the closest that I've been to coding in the 90s or 80s, because we have
very little stack space.
We have 512 bytes, if I am not mistaken.
So in order to overcome that, we used BPF maps as some sort of heap.
Then there's a problem that I mentioned before about memory locking.
That memory can never be swapped out, and it is in kernel space.
So we want to make sure that we allocate the minimal space you need, and we need to do it
properly, because each single environment has a different C-group configuration, and as
some talks explained yesterday, it's quite tricky to know the actual memory that your
machine has available.
For the program size, there is two main issues.
One of them is that there's a limitation on the number of instructions that you can store
in the kernel, but also the BPF verifier, which is this machinery that makes sure that your
program is safe, and for example, your program is going to finish, you're not the reference
in any null pointers, and that in general, you're not going to crash the kernel, has
a limit on the amount of iterations that it does internally.
This is a problem for us, because doing a full binary search already fills these limits.
So we need to use some techniques like this thing called BPF tail calls that is similar
to Lisp tail calls, and if you're lucky, we are not.
You can use, well, we use bounded loops, but we're going to use this new helper called
BPF loop that basically it's a function that you can call multiple times creating some
sort of loop in BPF, but we cannot use that because we want to support older kernels.
That's a pretty new feature.
So let's switch to something else.
We have written our application in user space in Go, and we are a profiler, so we want to
make sure that the overhead we have on your machine is as little as possible.
But unfortunately, many of the Go APIs aren't designed with performance in mind.
I am new to Go.
I didn't know this was like this, and every single time I profiled our profiler, and I
found these things, I was like, how is this possible?
But it has the dwarf and elf parsing library in the standard library, which is great, but
they are not designed for performance sensitive environments, let's say.
And also, there's two functions that are binary read and binary writes that we use all the
time because we need to deal with bytes back and forth that allocate in the fast path.
But anyways, we profile our profiler all the time.
We have found lots of opportunities that we keep on fixing, but of course, there's more
work to do.
And one of the areas where we try to be pretty comprehensive, it's with testing.
So we have thorough testing for, well, unit testing for most of the core functions to
ensure that we don't regress, but I think that, in my opinion, has helped us the most
is snapshot testing.
If you're not familiar with this technique, it's very simple.
You basically generate some textual representation of your data structures, write them to disk
or somewhere in memory, it doesn't matter, and then you generate them again after you
make some changes to your code, and then you compare them.
So this is how it looks in our case.
We have some Git sub repository called test data, and then we have this textual representation
of the unwind tables.
You don't have to understand it all, but the idea here is that this covers a full function,
which program counter starts in the one over there and ends in the one over there.
And then we have the information for every single program counter, and then it tells
you, for example, what to do here.
The first one says CFA type two that I know is for RBP.
So you need to get the current RBP at eight, and that will give you the previous frame
stack pointer.
But anyways, the interesting thing here is that this is very easy to implement, as you
can see by our very advanced setup in our make file.
We just build our binary.
We dump these tables to disk, and then we ask Git to give us the changes.
And if there's anything that has changed, we fail.
So thanks to this, we have found a lot of bugs, and it has allowed us to iterate with
confidence.
One of the important things in this project has been de-risking it.
It's been quite complex.
When I started working at this, I had no idea about dwarf unwinding.
I had no idea about unwinding without frame pointers at all.
So we had to make sure that all these avenues were properly covered.
We had, for example, the dwarf parser properly implemented, that we had all the interactions
with BPF cover, and that the BPF unwinder worked well as well.
So for this, we always tried to have a plan B at every stage of the project, and we tried
to go in depth as well as in breadth.
But anyways, I have five minutes left apparently.
So we had a lot of automated testing, and one of the things that we did was adding kernel
tests, which is super important, especially for BPF programs, because the BPF sub-system
changes a lot over time.
And there's a lot of features that we want to make sure we don't use, because otherwise
it wouldn't work in other kernels.
So we have a kernel testing system where basically it runs our application in multiple kernels
and reports the state.
And one of the things that I want to talk about is that production, as usual, brings
a lot of interesting challenges.
So by deploying our profiler to production, we found a lot of things that we didn't know
about.
And we were able to find some of these things thanks to using continuous profiling, our
own profiler on our profiler.
As you know, different hardware and different configuration are the biggest sources of performance
differences as well as incidents in production.
So I want to show you two things that we have found recently.
One of them is basically we're using almost 30% CPU time opening files in our production
environments that never showed up on my NVMe.
And the reason is because, turns out, cloud disks are very slow.
So we have fixed this.
Another very interesting thing that we fixed the other day, it's something that happened
when we rolled our profiler to production and then it started crashing.
If you are interested, we will upload the slides, so feel free to check the pull request
because everything is open source.
But basically what happened here was that, for reasons, Go has a signal-based profiler
and we have it enabled for even more reasons.
And this only was enabled in production.
So SIGPROV was interrupting our program execution while we were trying to load the BPF program.
The BPF program takes a little while to load because the verifier has to run a bunch of
algorithms to start to actually ensure that everything is safe and it was getting interrupted
all the time.
The BPF, that is the BPF library we used to load the BPF program, was retrying this up
to five times until it basically said, I tried, this didn't work, sorry, and obviously we
need the BPF program to be loaded to work.
So there's many other considerations in this project, like short-lived processes, which
we haven't optimized for, but we are still pretty decent ads.
If your program runs for one second, we're probably going to catch it, but if this is
something that you care about, feel free to message us.
It will be something that we optimized.
And then, yeah, this is our current format, I probably have one minute left or something
like that.
So you don't have to understand it all, but the point is we represent every single row
with 264-bit words, but since we are making it a bit smaller, and this is basically how
our size compares to dwarf.
We are bigger because dwarf is optimized for disk while we are optimized for disk space
while we are optimized for just raw speeds.
So for example, our whole table for one shard pretty much fits in L2 cache.
I guess, do I have any more time, or probably not, right?
Two minutes, oh, okay, sorry, maybe I sped up too much.
So we need to support parsing every single dwarf CFI opcodes, and the reason for this
is because otherwise we won't be able to progress, but we cannot unwind from every single program
counter, which sucks.
But this is not a problem in practice.
The reason for this is because the most typical way to recover the previous frame stack pointer
is, which is called CFA in dwarf, but doesn't matter, is that you will get given which register
you need to apply some offset to, and that will give you the previous frame stack pointer.
We support that, but the problem is that it could be any arbitrary register, and right
now we only support either RBP or RSP offsets, which happen 99% of the time.
So this is something that we're going to work on soon.
The other problem, as Vishali said before, is that dwarf has a VM that you need to implement,
which has to be Turing-complete, and can implement any expression.
It's not Turing-complete.
The second level, yeah.
The dwarf?
No.
That's why in the infinity project they had to add this new opcode in the draft hat.
Okay.
It's not exactly Turing-complete, it's almost there, yeah.
Okay, well.
But you need to implement a VM that basically has a set of virtual registers.
Yeah.
But the second, well, we're going to talk about those later, because the first level, yeah,
it's the stack machine 100%, but the second level is, I can show you our code, it's messed
up.
It's messed up.
But anyways, but the thing is that we are very lucky here, and you can check more about
this in this PR.
So there's two dwarf expressions that account for 50% of all the expressions that we have
seen in most distributions.
They are the expressions used by, well, the dynamic linker needs some, basically, and they
are the expressions for procedure linkage tables or PLTs.
The other good news, as I said before, is that RBP and RSP offsets rarely occur, and
all the other possibilities that I haven't talked about, they almost never occur.
Like, we've seen them very, very, very few times.
The indexes are useful.
Oh, good question.
So.
We're playing with AR64, because the GCC has 64 backend generates CFA expressions.
That's what I was talking about, yeah, yeah, yeah.
So but right now we only support X64, but I'm also going to talk about this later, sorry.
But anyways.
We don't know.
Oh.
Okay.
Done.
Okay, well.
But we have the minutes buffer for the next one, right?
Five minutes.
Okay.
I have two more slides.
Well, anyways, our BPR program, we tried to make it as fast as possible.
So this was running on my machine with a bunch of applications that have 90 frames or more.
So even the maximum time that it takes is 0.5 milliseconds, which is not terrible on
my CPU, which is from late 2017.
And this is in a big part because we have optimized everything for memory.
So everything's aligned properly.
And we try to fit as many things as possible in the CPU cache.
What about high level languages?
So there's a project that I happen to work on, which is called RB Perf.
So this is something that we're going to be adding in the future, basically for dynamic
languages.
You have the knowledge of the ABI of every interpreter version.
And then the Stackwalker is also implemented in BPF.
But instead of getting the return addresses, because you have no return addresses there
that are meaningful to you, you have to directly extract the function names and other information
of the process heap.
Our project is called PARCA.
So there's a couple of things that we're going to be doing, like mix and why mode, that as
far as we know, no one else does this in profiling, in the baggers for sure, but not in profiling,
which is the idea of that different sections will be on wants using different techniques.
And for example, if you have a JIT that will be used, like Node.js, that has frame pointers.
So you will unwind it with frame pointers.
But once you reach the actual code from your interpreter, which is compiled and has some
white information, we will use Dwarf and white information.
RM64 support is coming late this year.
And this feature is now disabled by default, but it is stable enough that we're going
to be enabling it in a month.
And then we're going to add other runtime such as the JVM or Ruby.
And then just to say that we are open source, user space on the Apache 2, BPF on the GPL.
And yeah, all the links are here.
Thanks, yeah, thank you so much.