This one is tried and true! But not bad as a starter:
fnfib(n:i32)->i32{ if n <=2{ return1; } fire::dbg!("return",fib(n -1)+fib(n -2)) }
What does the call tree of fib(5) look like?
Call tree of `fib(5)`
To make it more efficient, we can use a "memo" to cache the function calls. There are multiple ways to do this, let's try using a static HashMap:
lazy_static::lazy_static!{ staticrefMEMO:Mutex<HashMap<i32,i32>>=Mutex::new(HashMap::new()); } fnfibm(n:i32)->i32{ if n <=2{ return1; } { letmut memo =MEMO.lock().unwrap(); ifletSome(o)= memo.get(&n){ return*o; } // we have to release the lock here } let res =fibm(n -1)+fibm(n -2); letmut memo =MEMO.lock().unwrap(); memo.insert(n, res); res }
Now, what will the call tree look like?
Call tree of `fibm(5)`
Nice! We can see that the fibm(n = 3) (9th node) returned early.
Here is one more comparison for fib(10).
Call tree of `fib(10)`
Call tree of `fibm(10)`
We can see that the memo helped reduce the number of nodes down from 111 to just 19!
Let's get to a slightly more interesting problem. According to Wikipedia, the change-making problem addresses the question of finding the minimum number of coins that add up to a given amount of money.
Example 1:
Given the coins { 1, 2 } (with unlimited number), how many coins do we need to make up to 5?
The answer is 3, with coins 1 + 2 + 2. Now, let's look at the standard recursive implementation:
fnmin_coins(m:i32, coins:&[i32])->Option<usize>{ if m ==0{ returnSome(0); } letmut count:Option<usize>=None; for coin in coins { let next = m - coin; if next <0{ continue; } count =match(count,min_coins(next, coins)){ (Some(a),Some(b))=>Some(a.min(b +1)), (Some(a),None)=>Some(a), (None,Some(b))=>Some(b +1), (None,None)=>None, } } fire::dbg!("return", count) }
The call tree for min_coins(13, &[1, 4, 5]):
Call tree of `min_coins(13, ..)`
With memoization, we'd use a context specific HashMap:
fnmin_coins_m(m:i32, coins:&[i32], memo:&mutHashMap<i32,Option<usize>>)->Option<usize>{ if m ==0{ returnSome(0); } ifletSome(c)= memo.get(&m){ return*c; } letmut count:Option<usize>=None; for coin in coins { let next = m - coin; if next <0{ continue; } count =match(count,min_coins_m(next, coins, memo)){ (Some(a),Some(b))=>Some(a.min(b +1)), (Some(a),None)=>Some(a), (None,Some(b))=>Some(b +1), (None,None)=>None, } } memo.insert(m, count); count }
Now, the call tree is reduced down to just 28 nodes:
This is the most interesting and practical problem. The video uses it to implement a git diff algorithm which is pretty neat.
Here let's go straight into memoizing, because otherwise it would never return even for trivial test cases:
structMemo{ memo:HashMap<(usize,usize),usize>, } fnlcs_impl<T:Copy+Eq>(left:&[T], right:&[T], state:&mutMemo)->usize{ if left.is_empty()|| right.is_empty(){ return0; } fire::dbg!("(i, j)",(left.len()-1, right.len()-1)); ifletSome(n)= state.memo.get(&(left.len()-1, right.len()-1)){ return*n; } let n =if left[left.len()-1]== right[right.len()-1]{ 1+lcs_impl(&left[..left.len()-1],&right[..right.len()-1], state) }else{ let leftn =lcs_impl(&left[..left.len()-1], right, state); let rightn =lcs_impl(left,&right[..right.len()-1], state); leftn.max(rightn) }; state.memo.insert((left.len()-1, right.len()-1), n); n }
The .len() - 1 bits are pretty verbose, but if you look pass them, the code should be pretty understandable. The clever bit here is to use a HashMap with a tuple key instead of a 2D vector to save space!
But it's only half of the story. Because we still need to walk the path again to re-construct the common subsequence:
pubfnlcs<T:Copy+Eq>(left:&[T], right:&[T])->Vec<T>{ letmut state =Memo{ memo:Default::default(), }; let length =lcs_impl(left, right,&mut state); // reconstruct the common subsequence letmut seq =Vec::new(); let(mut i,mut j)=(left.len()-1, right.len()-1); while seq.len()< length { if left[i]== right[j]{ seq.push(left[i]); if seq.len()== length { break; } i -=1; j -=1; }else{ if i >0&& state.memo.get(&(i, j)).unwrap()== state.memo.get(&(i -1, j)).unwrap(){ i -=1; }else{ j -=1; } } } seq.reverse(); seq }
If we look into the memo of the last node, we can see that we only used 13 elements, instead of 8 x 6 = 48 as in the video (or pretty much every other tutorial), and that the call tree only has 35 nodes. So there is some trade-off between top-down vs bottom-up dynamic programming here.
I hope you learnt something today! FireDBG is your best companion in writing, debugging and analyzing algorithms. You don't have to install the Rust toolchain to interact with the call trees, as I have bundled them in the testbench with full source code here. You should be able to just open the dynamic-programming folder, install the VS Code extension and start playing.
In this blog post, we will cover the basic usage of FireDBG VS Code Extension ("the Extension") and FireDBG CLI ("the CLI"). By the end of this tutorial, you will learn:
How to install the Extension and the CLI
How to setup a Rust workspace for FireDBG debugger
How to debug Rust binary, example, unit test and integration test with FireDBG debugger
How to interpret and inspect visualized call tree, variables and timeline in the Extension
How to interpret and inspect breakpoint events of multi-threaded program in the Extension
How to trace any variable / expression of interest with the fire::dbg! trace macro
How to selectively enable / disable tracing of a local package
How to use the CLI to operate FireDBG debugger and then interpret and inspect breakpoint events via SQLite
If you're curious about the background and inner working of FireDBG
The Extension provides seamless integration with FireDBG to enhance debugging experience and developer productivity.
Search and install the FireDBG extension.
To keep the .vsix package small in size, we dont't ship the platform-specific binaries with the Extension.
Instead, we have a dedicated installer script for the FireDBG binaries. We provide prebuilt binaries for the following CPU and OS combination:
Once the the Extension has been installed, you should see a prompt hinting that FireDBG binaries are missing. Click on the "install" button to run the installer.
Note that the root directory of testbench isn't a Cargo workspace. In the next section, please open each sub-folder (e.g. getting-started) in VS Code. For convenience, each example already included a sample run.
Where can I see the list of all debuggable Rust targets, how can I debug it and how to inspect previous runs?
Click on the "Run and Debug" panel on your primary sidebar, you should see two new panels on the bottom
Click on the "Activate FireDBG" to enable FireDBG debugger on this workspace
The FIREDBG panel should display all binaries, examples, integration tests and unit tests in your current Rust workspace. Click on the list item to reveal the Rust source code. To debug it, hover the list item and click on the play icon ▶️ on the list item. A new debugger view will be shown and tail the progress in real time.
All previous debug runs can be found in the FIREDBG RUNS panel, simply click on it to open.
Alternatively, you can list all debuggable Rust targets with the CLI:
$ firedbg list-target Available binaries are: roll_dice
And, list all previous runs with the CLI:
$ firedbg list-run Available `firedbg` runs are: 1) roll_dice-1701678002235.firedbg.ss
How to interpret and inspect visualized call tree, variables, timeline and threads in the Extension?
We can the open the debugger view by clicking the items in the FIREDBG RUNS panel, or with the open command:
firedbg open
Each node represent a function call; the depth of each node indicates the depth of the call stack; each node has a unique frame ID; there are two types of edge:
Function call with return value: -<->-
Function call only: -->--
If the program exited with a panic, the panicking function will be highlighted in red with an exclamation mark.
Click on the function name on the call tree node to reveal the Rust source code.
Function Arguments: the name of the argument is shown as the label. The faded text on the bounding box denote the type name, where hovering on it will reveal the fully-qualified name. The actual value is enclosed in the bounding box.
Function Return Value: the return value will be shown on the far right with the label return.
Timeline: toggle the timline by checking the timeline checkbox on the bottom. There are two kinds of node:
Circle: function call
Square: function return
Thread selector: If the program has more than one thread, a dropdown will be shown on the bottom. You can switch to inspect the execution of other threads. Bring up the timeline to view the execution of all threads in a single view.
Use the control buttons on the timebar to jump to the beginning or the end of program execution. Use JK on your keyboard or stepping buttons <> to step one frame backward or forward. The unit of time on the timebar is frame ID of the selected thread. Clicking on the timebar would jump to the exact function call.
The visualization will be updated as you traverse the call tree. Use WASD keys on your keyboard or your left mouse click to pan; Click the +|- buttons on the bottom right or -= on your keyboard or use your mouse scroll wheel to zoom.
To resize a panel, hover the mouse on the panel gutter then drag to resize. Tip: double clicking the gutter reverts the panel to a pre-defined size.
Cargo workspace is a set of crates sharing the same Cargo.lock and target directory.
FireDBG rely on Cargo to locate source files and targets for debugging.
Now you have a basic understanding on the usage of FireDBG.
Let's create a Cargo workspace and practice debugging with FireDBG!
We found that it's quite hard to inspect what elements are swapped in each partition.
To help debugging, we can add a swap function and rewrite the original code:
fn partition<T: PartialOrd>(arr: &mut [T], low: isize, high: isize) -> isize { let pivot = high as usize; let mut store_index = low - 1; let mut last_index = high; loop { store_index += 1; while arr[store_index as usize] < arr[pivot] { store_index += 1; } last_index -= 1; while last_index >= 0 && arr[last_index as usize] > arr[pivot] { last_index -= 1; } if store_index >= last_index { break; } else { - arr.swap(store_index as usize, last_index as usize); + swap(&mut arr[store_index as usize..=last_index as usize]); } } - arr.swap(store_index as usize, pivot as usize); + swap(&mut arr[store_index as usize..=pivot as usize]); store_index } + fn swap<T: PartialOrd>(arr: &mut [T]) { + arr.swap(0, arr.len() - 1); + }
Tip: you can add #[cfg_attr(not(debug_assertions), inline)] to the swap function to inline it in release build, so that it will not incur any overhead.
Now, we can clearly see what was swapped and how many times swap was called. Upon a closer inspection we will see a pattern, i.e. the first element is always untouched in all partition operations. That's the bug 🐛!
Let's try to debug the same program with a different approach. An non-invasive approach, this time we only trace the swap without modifying the program structure.
FireDBG provide a fire::dbg! macro similar to std::dbg! to capture the variable of interest.
We can trace the swap actions with the help of fire::dbg!. The main advantage compared to std::dbg!, is that the trace data is associated with the stack frame of the calling function.
Undo the previous change and go back to the original implementation.
Cargo.toml
[dependencies] + firedbg-lib = "0.1"
+ use firedbg_lib::fire; fn partition<T: PartialOrd>(arr: &mut [T], low: isize, high: isize) -> isize { let pivot = high as usize; let mut store_index = low - 1; let mut last_index = high; loop { store_index += 1; while arr[store_index as usize] < arr[pivot] { store_index += 1; } last_index -= 1; while last_index >= 0 && arr[last_index as usize] > arr[pivot] { last_index -= 1; } if store_index >= last_index { break; } else { + fire::dbg!("swap", &arr[store_index as usize..=last_index as usize]); arr.swap(store_index as usize, last_index as usize); } } + fire::dbg!("swap", &arr[store_index as usize..=pivot as usize]); arr.swap(store_index as usize, pivot as usize); store_index }
This time the swap is shown in the variables of the partition function.
As expected, we see 3 swaps. This should help us to observe the pattern, locate and fix the bug 🔎!
Similar to unit test, we can debug integration test with FireDBG. Let's add an integration test file:
quicksort/tests/bookshelf.rs
#[test] fntest_quicksort_1(){ letmut books =[ "The Rust Programming Language", "Beginning Rust: From Novice to Professional", "Rust in Action", "Programming Rust: Fast, Safe Systems Development", "Rust Programming Language for Beginners", ]; quicksort::run(&mut books); assert_eq!( books, [ "Beginning Rust: From Novice to Professional", "Programming Rust: Fast, Safe Systems Development", "Rust Programming Language for Beginners", "Rust in Action", "The Rust Programming Language", ] ); }
Alternatively, you can debug integration test with the CLI:
usefiredbg_lib::fire; usestd::iter::repeat_with; usestructopt::StructOpt; #[derive(StructOpt, Debug)] structOpt{ /// Random seed #[structopt(long, default_value = "2525")] seed:u64, /// Number of random numbers to be sorted #[structopt(default_value = "10")] n:usize, } fnmain(){ letOpt{ seed, n }=Opt::from_args(); fire::dbg!(&seed); fire::dbg!(&n); fastrand::seed(seed); let max =if n <=10{100}else{1000}; println!("Sort {n} numbers in ascending order"); letmut numbers:Vec<_>=repeat_with(||fastrand::i32(1..max)).take(n).collect(); println!("Input: {:?}", numbers); quicksort::run(&mut numbers); println!("Sorted: {:?}", numbers); letmut c =0; for n in numbers { assert!(n >= c); c = n; } }
We can add a [[targets]] entry in firedbg.toml to create additional profiles:
A firedbg folder will be created for storing the symbols, debug runs and other supporting files.
You should ignore this folder from your source control, i.e. add firedbg/ to .gitignore.
Let's try and add one more crate to the workspace.
$ cargo new --lib book-store $ cd book-store
Update the Cargo.toml at workspace root, adding our new book-store package.
Cargo.toml
[workspace] members=["quicksort","book-store"]
Below we have a simple function to list the inventory in alphabetical order.
book-store/src/lib.rs
useanyhow::Result; usestd::fs::File; usestd::io::{BufRead,BufReader}; pubfninventory(path:&str)->Result<Vec<String>>{ let file =File::open(path)?; let reader =BufReader::new(file); letmut books =Vec::new(); for line in reader.lines(){ let book = line?.trim().to_owned(); books.push(book); } quicksort::run(&mut books); Ok(books) }
To put it in action we can add a books.txt file to the package root and then write a unit test to invoke the inventory function.
book-store/books.txt
The Rust Programming Language Rust Programming Language for Beginners Programming Rust: Fast, Safe Systems Development Beginning Rust: From Novice to Professional Rust in Action
book-store/src/lib.rs
#[cfg(test)] modtest{ usesuper::*; useanyhow::Result; #[test] fntest_inventory_1()->Result<()>{ let path =concat!(env!("CARGO_MANIFEST_DIR"),"/books.txt"); let books =inventory(path)?; assert_eq!( books, [ "Beginning Rust: From Novice to Professional", "Programming Rust: Fast, Safe Systems Development", "Rust Programming Language for Beginners", "Rust in Action", "The Rust Programming Language", ] ); Ok(()) } }
Umm... we see that function calls to the quicksort crate are missing in the call tree.
By default FireDBG will only trace the functions of the debug target.
If you want to trace other crates in your local workspace, you will need to create a firedbg.toml config file in your workspace root.
When you open a .firedbg.ss file, FireDBG indexer will create a .sqlite file to store the analyzed debug info.
You can also run the indexer manually with the firedbg index sub-command. You can now write SQL queries to your heart's content!
Supported Windows (WSL 2) distributions: Ubuntu 22.04, Ubuntu 20.04↩
Debugging programs is hard. It is extremely mind boggling when something does not work as expected. More often than not 90% of the work is on tracking down where the bug is, and 10% is actually solving it!
But why don't programmers use debuggers more often these days? Instead, we all enjoy adding println all over the place, running the program, adding more prints, rinse and repeat, just to find out that we still haven't printed the key variable and may even need to make guesses about the program state while drowning in the logs.
A running program is like a blackbox to us, and the console is our only window into its internal states. However, at the end of the day, it is still the programmer's responsibility to print the relevant information.
How does a debugger help us debug a program? We identified that it usually comes down to:
Where did the control flow of my program go?
Where do my errors come from?
What are inside my variables?
What happened in what order?
That's why we created FireDBG - a Time Travel Visual Debugger for Rust 🎬
According to Wikipedia, time travel debugging is the process of stepping back in time through source code to understand what is happening during execution of a computer program. Unlike "traditional" debuggers which can only step forward, time travel debuggers allow us to step backward and see the cause and effects.
Time travel debuggers exist1, and they usually work by recording data on the instruction level. But that would result in a gigantic amount of data, so now the question is: how do we make sense of this data and navigate through time effectively?
If you instantly get it, you can skip this section! If not, let's go through it step by step:
"A call tree is all the state transitions of a program's call stack laid out on a 2D plane, organized in form of a tree"
Every time a function call is made, we create a child node; when the function returns, we go back to the parent node. So subsequent function calls become sibling nodes.
At any given node, traversing up to the root node gives us a chain - which is the call stack.
We have two notations, -->-- for function calls; --<->-- for function calls with return values.
We assign a unique frame ID to each node and this is the time sequence used in the timebar.
FireDBG is built around the call tree. You may ask, wouldn't this call tree become very large? Yes, that's why we spent enormous effort into linearizing everything. We developed a streaming file format to process the data in real time, and figured out a layout algorithm that can render infinite trees.
What's so interesting about call trees? Their shapes reveal a lot about the properties of algorithms. To illustrate, here's a side-by-side comparison of quicksort and mergesort, and we can see that quicksort yields a deeper tree than mergesort2. So quicksort is using more stack memory3 than mergesort, which makes sense because mergesort uses some memory on the heap!
Since both are binary trees, they are not tail-call optimizable. And since both algorithms claim to be of O(n log n), statistically only one of the two branches should grow deeper. There are a lot more to observe and I have been drawing this on paper by hand for many years.
This might be a Rust specific problem: Rust don't have exceptions. Instead, Rust uses a Result system coupled with the ergonmic ? operator to effectively signal and handle errors. This has both pros and cons - the good thing is that errors propagate back to the parent along the exact same path the function is being called, which is deterministic and predictable. The bad thing is, when you finally unwrap an error and decide to panic, the context of the error has long been lost.
This echos our second question: where do my errors come from? Consider the following toy program, where we get to roll some dice and each time we could be rolling one, two or three dice. Once in a while, throwing a die can cause an error. This is deliberately randomized, so there is no way to statically analyze where the error might come from - such is life!
FireDBG captures all functions' return values and so is able to locate where the error originated from and how it propagated up! Here is the rendered call tree of this roll_dice program, where FireDBG is able to highlight the error path up until the point of panic, which is conveniently marked by !:
As you have seen in the above screenshots, FireDBG captures all functions' parameters and return values. Capturing parameters is the easy part, because it's a basic feature of any debuggers4. But capturing return values is a little intricate. The current implementation is: we set a breakpoint at every ret instruction and capture the return value at that particular point in time. The next instruction will immediately jump back to the parent function, which may overwrite the value.
Let's talk about ABI. There are different call conventions and Rust is particularly flexible in whether a value is returned via stack or register. In some cases complex data can be packed into one register, because Rust can return complex types like tuples and unions5. We tried super hard, but return value capture is still a hit-or-miss, but some visibility is better than no visibility!
Inspecting the parameters and return value of the partition function
We rely on lldb's awesome SBType API to parse Rust's debug symbols, and capture variables' values in binary forms - not all things are printable, in particular, pointers (references) and containers. We have to reference the memory locations to get their values. This becomes non-trivial if the references form a diamond or worse, cycles6.
For pointers, our brilliant intern7 has a great idea - capture and store the pointees as context for each variable and dereference those pointers on replay. Each memory address will only be serialized once, but can be copied many times on deserialization.
As such, we were able to construct a type system that can represent Rust values, which are serialized as binary data. We can then visualize them beautifully!
For containers, it is more murky. For vectors, we can simply read a blob of memory from the heap, because the items are contiguous. But ... how about hash maps? Luckily, in Rust, the standard library's hashmap is a flat hashmap, which means items are densely packed, although not contiguous. So with some memory fiddling, we are able to capture the contents of hashmaps!
Note that in the screenshot below, the hash key is &str, which means after extracting the hash keys from the hash map, we have to dereference the pointers to retrieve the string content.
Left panel: captured hashmap; middle panel: rendered hashmap; right panel: raw representation of a hashmap
Visualization is a new lens into our code. Above are just a few simple examples, and FireDBG opens the door to domain-specific visualizations that are meaningful to us. Below are a few more examples:
We tried our best to boost the signal-to-noise ratio. Instead of alloc::sync::Arc { core::ptr::non_null::NonNull { alloc::sync::ArcInner { strong: core::sync::atomic::AtomicUsize { .. }, weak: core::sync::atomic::AtomicUsize { .. }, data: pointer::Object { .. } } } }, we try to prettify standard library types like Arc as RefCounted { strong: 1usize, weak: 1usize, value: pointer::Object { .. } }.
FireDBG only traces user code - not standard library, not vendor libraries - only the code inside the specific crate you are currently programming. Which means the call tree will only contain functions you wrote. No implementation details like <I as alloc::vec::in_place_collect::SpecInPlaceCollect<T,I>>::collect_in_place.
Which also means that the overhead of program tracing is confined - even with a very complex program, the subset of user code that we want to trace would only be a fraction of the program binary.
Rust's slogan is "Fearless Concurrency", so how do we debug multi-threaded Rust programs? It's possible to pause and step through a multi-threaded program, but doing so manually would affect the timing and synchronization of other threads.
FireDBG can track multiple threads and keep them running as smoothly as possible, allowing us to observe how multiple threads work together. It's a proof-of-concept, but let's take a look at a small Rust program that spawns multiple worker threads to perform matrix computation:
fninverse(m:&Matrix<D,D>)->Option<Matrix<D,D>>{ fire::dbg!("return",Matrix::inv(m)) } fnrunner(receiver:Receiver<Matrix<D,D>>, sender:Sender<(Matrix<D,D>,Option<Matrix<D,D>>)>){ whileletOk(m)= receiver.recv(){ // send back the input with solution let mm =inverse(&m); sender.send((m, mm)).unwrap(); } } fnmain(){ let(result, collector)=channel(); letmut senders =Vec::new(); for _ in0..THREADS{ // spawn worker threads let(sender, receiver)=channel(); senders.push(sender); let result = result.clone(); std::thread::spawn(move||runner(receiver, result)); } for c in0..ITEMS{ // spmc; fan out let m =Matrix::<D,D>::random(); senders[c %THREADS].send(m).unwrap(); } for _ in0..ITEMS{ // mpsc; consolidate let(m, mm)= collector.recv().unwrap(); println!("Source = {m:?}"); println!("Inverse = {mm:?}"); } }
Top panel: a matrix and its inverse computed by a worker thread; bottom panel: timeline showing events across all threads within a specific time window
What you see today is an MVP of FireDBG. It may be slow and buggy, and notably, async Rust support is still a work-in-progress. But it outlines the vision I have for what a debugger could be and how it can level up our debugging experience. I still have a dozen of visualization ideas: channels, mutexes, arc/rc graph, async timeline, etc.
We aim to bring FireDBG to other programming languages and engineering domains. Our ultimate goal is to improve the debugging experience for all developers!
I am looking for a co-founder. If you are like me, deeply passionate about developer experience and willing to commit to this idea, let's team up and embark on a journey to transform software engineering. You can find my profile on YC Co-Founder Matching9.
Many great software inspired me, but two of them is worth mentioning: Firebug and Flame Graph. Firebug changed web development forever, and is the predecessor to the awesome browser developer tools we enjoy today.
Flame Graph is the classic example of how a simple but powerful idea became ubiquitous, and it really demonstrates the magic of visualization. Good visualization enlightens our brains.
A huge thanks to the CodeLLDB project, which powers FireDBG's lldb driver. In case you're wondering, FireDBG uses both SeaORM and SeaStreamer under the hood. And of course none of this could be possible without the Rust programming language and the awesome Rust community!
firedbg-cli drives everything. It acts as a proxy to cargo, so a cargo run command becomes firedbg run, cargo test becomes firedbg test and so on. firedbg-cli also relies on cargo to list all the executable targets shown in the "Run and Debug" tab of VS Code.
firedbg-parser parses all source files in the workspace and outputs a symbol table per file. These .map files are cached, so they will be reused if the source files are unchanged since the last parse.
firedbg-debugger is the debugging engine of FireDBG. It is configured according to firedbg.toml. The debugger drives the target process via lldb and streams the breakpoint events in real-time. The output file, with the extension .firedbg.ss, follows the binary file format defined in SeaStreamer File.
It sometimes uses rustc on the host for miscellaneous things.
firedbg-indexer is a streaming indexer. It can stream events from the .firedbg.ss file and process them in real-time. It outputs a .sqlite file with the same name, using SeaORM to drive SQLite. The index enables the GUI to quickly look up the call chain and frame info.
The basic idea of FireDBG is to automate the actions done by a user on a debugger CLI/TUI/GUI. For example, a user would usually set some breakpoints at some strategic locations and inspect all local variables every time a breakpoint is hit. FireDBG does the same! But our goal is to make each breakpoint hit as brief as possible, in order to keep the program-under-debug running in real-time. This is important because some resources like sockets and timers are time sensitive.
This mode of operation is called "galloping"1, as it only breaks on user code - library code and system calls are all skipped. In other words, the call tree we construct is not the full process call tree; it's down-sampled. In theory, we can use a VM to execute and record2 the process, then run it through FireDBG to condense the data.
The thesis is: "too much details obfuscate our understanding", and more often than not, we want to see the big picture. FireDBG lays out the call tree on a plane, so our brain can make sense of the two-dimensional space. The UX of the GUI is designed based on modern interactive maps3.
We parse the Rust source files with syn, looking for all functions, methods, and trait implementation blocks. The location and span of these functions are then dumped into .map files. In the future, we're hoping to support constructing a static call graph, so as to allow the debugger to only set breakpoints at functions reachable from main (or the program entry point, whatever it is).
On startup, the symbol tables are read. After loading the target executable into memory, the debugger loads the corresponding symbol tables and set breakpoints at those functions according to the configuration. We also set breakpoints on the panic handler and heap allocators.
The program will then be run. The debugger keeps a logical stack model for each thread. On each function call, a new frame ID will be assigned. The tuple (thread ID, frame ID, function call) uniquely identifies any point in program execution.
When a function is first called, we disassemble it. Then breakpoints are set at all ret instructions, so that whenever the function returns, the breakpoints will be hit, and a function return event is recorded. (We also cache the SBType definition of the function, with which the function return handler can salvage the return value from the registers, but this is an implementation detail). All parameters of the function are captured once the program has gone past the prologue4.
All breakpoint events happening meanwhile will be tagged with the current frame ID in the current thread.
All events will be streamed out in real-time. The format of the stream events is defined in firedbg-protocol.
It is actually possible to debug multiple threads by hand using a conventional GUI debugger, you just need to know this one trick ;)
Multiple threads can be hitting the same breakpoint at the same time, so we need to inspect all the threads each time a breakpoint is hit. We look at the PC address to determine whether this thread was actually paused on a breakpoint, and if so, record the event. All threads are resumed as soon as possible.
Value capture is currently done via lldb's excellent SBValue / SBType API. There are some edge cases, particularly around Rust's "complex enums" aka union types. There are many hacks5 done by firedbg-debugger to capture various Rust standard types, including but not limited to Vec<u8>, &str, &dyn T, Rc/Arc, HashMap.
Return value capture is currently done by looking at the return type and guessing where it will be placed at, registers or stack, and salvage the value. More ideally, we would query the call convention and extract accordingly.
All values are serialized as binary blobs in native endian. There are several motivations: 1) faithfulness 2) avoiding floating point and utf-8 idiosyncrasies6 3) avoiding serialization to strings which is slow 4) smaller file size.
The indexer reconstructs the call stack for each thread from the event stream. It then represents the call trees in SQL by self-references7. It also performs basic analysis like counting hits for each breakpoint.
The indexer deserializes the value blobs and transforms them into pretty-printed strings and JSON. They will then be queried by the GUI for display and visualization.
Parallelism in FireDBG; outer boxes: processes; inner boxes: threads
A lot of effort has been put in making FireDBG to improve responsiveness. The previous diagram shows the pipeline where data is streamed real-time. This diagram gives a different perspective: how the components work in parallel.
The Debugger, Indexer and GUI are separate processes, and each uses multiple threads for stream producer and consumer. Except in node.js the streamer is a subprocess instead of a thread.
The Call Tree Renderer is incremental: nodes are added on canvas as they arrive.
Our vision is to bring FireDBG to all programming languages. Some possible candidates are:
C++: supported by lldb; but it is difficult to distinguish user code from library code
Swift: supported by lldb; but need to support a lot of Apple system stuff
Go: delve seems very API drivable!
node.js: we can use the DevTools Protocol
Python: debugpy seems very promising
Your favourite language: suggestions are welcome!
When designing this architecture, we have been keeping in mind how we'd piece in other languages. Each language would have its own firedbg-xxx-debugger, outputting the same .firedbg.ss stream protocol. Primitives can more or less be shared so we can reuse the same PValue. RValue actually stands for "Rust Value", so you can assume we'd have GoValue for Go, JsValue for Javascript, etc.
We will ship multiple indexer binaries, but they will likely share the same codebase.
The CLI will be each implemented in its own language.
The GUI will all share the same codebase, but of course each language will have its own VS Code extension.
Rust probably has the most complex type system8, hopefully it will not get much more complicated than what we have already implemented.
The async programming model should be similar among languages, so we should be able to visualize them under the same model.
You can pan with click-and-drag (or three finger drag on macOS), scroll to zoom; we also have (x, y) coordinates: x-axis is the depth, y-axis is the breadth in the tree↩
Sometimes the function prologue is wrong and FireDBG currently has some logic to guess the prologue↩
Many; maybe in the next version we will abandon debug symbols altogether↩
They are not interpreted on serialization; only on deserialization which is the job of the indexer↩
If we have a MySQL backend, a single recursive CTE query can reconstruct the call chain of a given frame↩
