Flame Graph Viewer

Linux Perf creates a binary with the recorded events. I expected to read the binary file to avoid using stackcollapse-perf.pl. Reading of the binary file would allow my program to depend only on Linux Perf, but I didn't understand the file format. Luckily, I found this command in the blog of Brendan Gregg (the author of stockcollapse.pl):

perf report --stdio --no-children -n -g folded,0,caller,count -s comm | \
    awk '/^ / { comm = $3 } /^[0-9]/ { print comm ";" $2, $1 }' > collapsed.perf

After that, I had a look at the format of the output file and found that an event has one number. In order to understand what the number means, I read the code of flamegraph.pl. The logic was more or less clear apart from this piece:

$Tmp{$k}->{delta} += $i == $len_b ? $d : 0;

As far as I'm aware, I am not the only one who is confused by this. I decided to ignore it for now.

Another aspect I couldn't understand is the value for a perf event can have various formats. In the stackcollapse.pl, you can find this regular expression to extract any variant.

($stack, $samples) = $stack =~ (/^(.*)\s+?(\d+(?:\.\d*)?)$/);

So far, I decided to avoid regular expressions and to process just one integer after the last space.

let split = line.split(char::is_whitespace).rev();
let samples = split.next()?;

As I don't have a pre-existing widget for scrolling, I had to create one myself. My initial design of the widget involved making a big canvas and moving a viewport showing only some area of it.

I made a pixmap and a window. The pixmap is the big canvas and the window is the viewport. The pixmap is drawn from a certain offset with a static length. Technically, the drawing is copying the pixels from the pixmap to the window. The problem is Xlib doesn't allow to make pixmaps that are too big. As a result, I needed to move the buttons themselves.

The simple solution to move the buttons is simply changing the coordinates of each button. I implemented the solution quickly: it's a loop over the 1000 buttons. Every iteration of the loop processes the respective button. The processing involves calculation of the new coordinates for the button and calling XMoveWindow. It's stupid, but I wanted to see the numbers to be sure that it is stupid. It consumes 30-35% of CPU. I want less.

The processing, which runs every iteration, should run only when necessary. The obvious criteria of the necessity is visibility of the button. That says that only the visible buttons should be scrolled. Let's solve the problem then. The basic solution, I can do, is unmapping those buttons which are beyond the viewport. To explain, if a button is beyond the boundaries of the viewport, I call XUnmapWindow. If a button is in the viewport, even partially, I call XMapWindow. As a result, XMoveWindow is still called, but it costs nothing for the unmapped windows.

The CPU consumption dropped to 10-15%. It's better, but I still wasn't happy with the numbers, because it's just scrolling.

It's better to avoid recalculating the coordinates of those buttons that are unmapped. To achieve this, I need to maintain the range of visible buttons. The coordinates of the invisible buttons aren't recalculated. Also, I can stop calling XMoveWindow for unmapped windows.

Steps of the algorithm

1. Make a range of the visible buttons.
2. Maintain the range when scrolling happens.
   1. Change the offset.
   2. Move the visible buttons by the offset.
   3. If the button is out of the viewport, exclude it from the range.
   4. Pick the first button from those beyond the viewport, and if the viewport has space for it, move it by the offset and include it in the range.

I failed to implement the algorithm correctly the first time. Buttons didn't appear in the viewport after a couple of scrolls. What happened? My implementation of the algorithm involved having 2 stacks of buttons. One stack is above the viewport and one stack is beyond the viewport. The unexpected thing happened at the initialization of the program. At that moment, the buttons weren't in a stack. The buttons laid in a row next to each other.

When the user scrolled the window, the first "invisible" button was moved by the offset distance, but from its initial position. The idea of the fix was to place the first "invisible" button right after the last "visible" button.

Finally, the CPU load was barely above 0%.

The Perf data in the folded format looks like this

rust-analyzer;<DB as hir_def::db::DefDatabase>::attrs::__shim;salsa::QueryTable<Q>::get;salsa::QueryTable<Q>::try_get;<salsa::derived::DerivedStorage<Q,MP> as salsa::plumbing::QueryStorageOps<Q>>::try_fetch;salsa::derived::slot::Slot<Q,MP>::read;salsa::derived::slot::Slot<Q,MP>::read_upgrade;salsa::derived::slot::PanicGuard<Q,MP>::proceed;salsa::derived::slot::PanicGuard<Q,MP>::overwrite_placeholder;salsa::runtime::Runtime::unblock_queries_blocked_on_self;salsa::runtime::DependencyGraph<K>::remove_edge 1
rust-analyzer;<DB as hir_def::db::DefDatabase>::attrs::__shim;salsa::QueryTable<Q>::get;salsa::QueryTable<Q>::try_get;<salsa::derived::DerivedStorage<Q,MP> as salsa::plumbing::QueryStorageOps<Q>>::try_fetch;salsa::derived::slot::Slot<Q,MP>::read;salsa::derived::slot::Slot<Q,MP>::read_upgrade;salsa::derived::slot::PanicGuard<Q,MP>::proceed;salsa::derived::slot::PanicGuard<Q,MP>::overwrite_placeholder;salsa::runtime::Runtime::unblock_queries_blocked_on_self;salsa::runtime::DependencyGraph<K>::remove_edge;<&smallvec::SmallVec<A> as core::iter::traits::collect::IntoIterator>::into_iter 1

These lines are pretty long, but in the model, I have in my mind, they are like a tree with two leaves.

Every parent has the value of its children plus its own. Also, they have names. A simple parser should do just fine. Let's run it… it took 7 seconds to load. Why? Because I have to draw 38003 buttons instead of 1000.

Well, given that I need to make a lot more buttons, I should stop using windows and instead draw a few rectangles on a canvas. This means that solving the challenges with the window scrolling only served to give me more experience.

Xlib provides the function XFillRectangle to draw a rectangle. The function needs the size and the position of the rectangle.

1. Size.
   1. Height is constant. It's clear from the picture.
   2. Width should be calculated. To be specific, it's a sum the value of a perf event plus the value of the direct children.
2. Position.
   1. Abscissa (x coordinate) is the sum of the width and the abscissa of the neighbouring element on the left. The abscissa of the first rectangle is equal to the abscissa of its parent plus the value of the parent.
   2. Ordinate (y coordinate) is the number of the ascendants of the rectangle multiplied by the height, which is constant.

The main thing I had been scared of was handling the click and hover events (when the pointer is over a button). Both of the events require finding the button by the position of the cursor.

My initial idea was to make a KD tree, which is not a big deal for 2 dimensions. Luckily, I didn't need to implement KD tree at all. Instead of the tree, I made a simple index for the buttons, which effectively is a vector of vectors. The outer vector represents the vector of rows in the graph. An inner vector represents a row with the buttons. To find the position in the outer vector, I simply divide the ordinate by the height. The complexity of the search is just O(1). The rectangles in the inner vector should be sorted by the abscissa, allowing the button to be found using binary search. Binary search has the complexity O(log(n)). Another stroke of luck is that, in addition to the height being constant, the buttons are already sorted in the input data. This means, that building the index doesn't require any sorting.

fn find_rect<'a, 'node>(
    button_table: &'a [Rectangle<'node>],
    position_index: &[impl AsRef<[RectangleIndex]>],
    pos: Position,
) -> Result<&'a Rectangle<'node>, usize> {
    let lvl = &position_index
        .get((pos.1 as u32 / HEIGHT) as usize)
        .ok_or(0usize)?;
    lvl.as_ref()
        .binary_search_by(|((x_left, x_right), _)| {
            if pos.0 > *x_right {
                Ordering::Less
            } else if pos.0 < *x_left {
                Ordering::Greater
            } else {
                Ordering::Equal
            }
        })
        .map(|x| &button_table[lvl.as_ref()[x].1])
}

It is worth mentioning that while the binary search is good on paper, but it might be bad in the computer, because the CPU processes data in cache lines. When you read an array the CPU reads ahead filling the cache line. This means, if you read an array sequentially, the next element might be in the cache. As a result, the CPU won't go to RAM to fetch that next element. On the other hand, the binary search doesn't read an array sequentially. To confirm that binary search is efficient, I did a simple benchmark. Namely, I compared binary search with sequential reading of the index. In my case, the binary search worked at the same speed, so I left the binary search.

I implemented the lookup and was happy that it worked fast enough and, of cause, correctly. The handling of clicks is not as intensive as the handling of mouse moving. As I wanted to highlight the button under the cursor, I needed to handle the intensity.

Surprisingly, the code for the clicks worked fast enough for mouse moving as well. The same lookup in the index worked just fine and doesn't consume CPU.

The idea involves drawing a border around a rectangle when the cursor is over it and remove the border when the cursor is beyond the rectangle. The border can be drawn with XDrawRectangle, but drawing the border was not a trick. The trick was removing it, because the picture should be restored to its state before the border has been drawn.

In order to do it, I created an additional instance of Pixmap for the window displaying the graph. The new pixmap helped to make triple buffering to render the graph. Namely, the buffers are:

1. The window itself. The thing which the user sees.
2. The back buffer. It accumulates the changes and flushes them into the window.
3. The backup buffer. It holds the initial picture of the graph and flushes into the window when a button is no longer highlighted.

graph.restore(&ui_factory);  // Restore the original picture from the backup buffer to the back buffer.
if let Ok(r) = find_rect(
    &button_table,
    &position_index,
    (x_cursor, y_cursor + graph.offset_y),
) {
    graph.draw_rectangle(&ui_factory, r);
    graph.set_to_draw(BufferSide::Back);  // Draw the picture with the highlighted rectangle to the back buffer.
    status_line_upper.set_text(&ui_factory, r.node.name());
}

The last piece is scrolling. All of my previous experiments to make scrolling working were for a bunch of windows, but now, I no longer use windows. Instead of the windows I have just a pixmap. That enabled me to implement my initial idea of scrolling. In particular, I keep track of the offset and copy the pixels from the back buffer into the window using this offset.

It's confusing when you need to write: "here is the text with this background". You create a window, define its position and the color, and you get nothing. Here is the example of the code which brings you to this situation

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // initialization begins
    let mut xlib = ui::new_xlib()?;
    let mut display = ui::Display::try_new(&xlib)?;
    let screen = ui::Screen::try_new(&mut xlib, &mut display)?;
    let mut visual = ui::Visual::try_new(&xlib, &mut display, &screen)?;
    let root_win = ui::Window::new_root(&xlib, &mut display, &screen);
    let background = 0x1d2021;
    let mut main_win = ui::Window::new_main(
        &xlib,
        &mut display,
        &screen,
        &mut visual,
        &root_win,
        (0, 0, 800, 600),
        background,
        "FlameGraph Viewer",
        "FlameGraph Viewer",
        std::env::args(),
    )?;

    let mut pixmap = ui::Pixmap::new(&xlib, &mut display, &main_win);
    let gc = ui::GraphicContext::new(&xlib, &mut display, &main_win);
    let mut ui_factory = ui::Factory::new(xlib, display, screen, visual, root_win, gc);

    let font_data = include_bytes!("../DejaVuSansMono.ttf");
    let font =
        Font::try_from_bytes(font_data as &[u8]).expect("error constructing a Font from bytes");
    // initialization ends

    ui_factory.show_window(&main_win);

    ui_factory.set_foreground(background);
    ui_factory.set_background(0xffffff);
    ui_factory.fill_rectange(&pixmap, (main_win.width(), main_win.height()));
    draw_caption("RustType",
        &mut ui_factory, &font, &pixmap, 0xffffff, background);
    let mut quit = false;
    while !quit {
        let event = ui_factory.wait_event();
        match event {
            ui::Event::Expose(_) => (),
            ui::Event::KeyPress(KEY_Q) => quit = true,
            ui::Event::KeyPress(key) => println!("key code {:x}", key),
            ui::Event::ConfigureNotify { width, height } => {
                main_win.set_width(width as _);
                main_win.set_height(height as _);
                pixmap = ui_factory.resize_pixmap(pixmap, &main_win);
            }
        };
    }

    Ok(())
}

In Xlib, you don't make UI in the declarative way. Instead, you keep track of the events in the window and redraw it as needed. In this case, the solution is to draw the text only when the Expose event occurs.

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // initialization begins
    let mut xlib = ui::new_xlib()?;
    let mut display = ui::Display::try_new(&xlib)?;
    let screen = ui::Screen::try_new(&mut xlib, &mut display)?;
    let mut visual = ui::Visual::try_new(&xlib, &mut display, &screen)?;
    let root_win = ui::Window::new_root(&xlib, &mut display, &screen);
    let background = 0x1d2021;
    let mut main_win = ui::Window::new_main(
        &xlib,
        &mut display,
        &screen,
        &mut visual,
        &root_win,
        (0, 0, 800, 600),
        background,
        "FlameGraph Viewer",
        "FlameGraph Viewer",
        std::env::args(),
    )?;

    let mut pixmap = ui::Pixmap::new(&xlib, &mut display, &main_win);
    let gc = ui::GraphicContext::new(&xlib, &mut display, &main_win);
    let mut ui_factory = ui::Factory::new(xlib, display, screen, visual, root_win, gc);

    let font_data = include_bytes!("../DejaVuSansMono.ttf");
    let font =
        Font::try_from_bytes(font_data as &[u8]).expect("error constructing a Font from bytes");
    // initialization ends
    ui_factory.show_window(&main_win);

    let mut quit = false;
    while !quit {
        let mut is_redraw = false;
        let event = ui_factory.wait_event();
        // we reset the background of the pixmap every event, but the actual drawing happens if the
        // flat is_redraw is raised.
        ui_factory.set_foreground(background);
        ui_factory.set_background(0xffffff);
        ui_factory.fill_rectange(&pixmap, (main_win.width(), main_win.height()));
        match event {
            // here we draw the caption.
            ui::Event::Expose(0) => {
                draw_caption("RustType",
                    &mut ui_factory, &font, &pixmap, 0xffffff, background);
                println!("expose redraw");
                is_redraw = true;
            }
            // the rest of the events aren't changed.
            ui::Event::Expose(_) => (),
            ui::Event::KeyPress(KEY_Q) => quit = true,
            ui::Event::KeyPress(key) => println!("key code {:x}", key),
            ui::Event::ConfigureNotify { width, height } => {
                main_win.set_width(width as _);
                main_win.set_height(height as _);
                pixmap = ui_factory.resize_pixmap(pixmap, &main_win);
            }
        };

        if is_redraw {
            println!("swap buffers");
            ui_factory.swap_buffer(&main_win, &pixmap);
        }
    }

    Ok(())
}

It's annoying at first, but as I approached the implementation of the search feature in the application, I clearly understood the possible states of the application from the code.

1. The search should be invalidated after one of the buttons is clicked.
2. The keys n and N should work only after the search program has successfully finished.
3. If the search program finishes unsuccessfully, it shouldn't affect the current active search.

Rendering text for every rectangle doesn't really work in this case, because the rectangles are short, while the text is long. As a result, the text goes beyond the rectangle and sets on top of the text of neighboring rectangle. It makes such a mess in which you can't read the names of the rectangles. Luckily, when you draw text at this level, you control every pixel. In order to prevent the mess, I needed to trim that text which goes beyond its button. There was one more reason for the trimming - the drawing of names of the perf events took a couple of minutes. The API of rusttype allows me to get the information of every glyph (in our case it means a character). It allows me to get the coordinates of the pixels of every glyph and draw them on the canvas. As I know the coordinates of the pixels I can omit those ones which are beyond the rectangles.

let scale = Scale::uniform(font_size);
let v_metrics = font.v_metrics(scale);
let offset = point(0.0, v_metrics.ascent);
let glyphs: Vec<_> = font.layout(content.as_ref(), scale, offset).collect();
glyphs.iter().for_each(|g| {
    if let Some(bb) = g.pixel_bounding_box() {
        g.draw(|x, y, v| {
            let color = color_blend(foreground, background, v);
            let x = x as i32 + bb.min.x + start_at.0;
            let y = y as i32 + bb.min.y + start_at.1;
            if ((x - start_at.0) as u32) < width_limit {
                canvas.draw_point(color, x, y);
            }
        })
    }
});

Once I've drawn the text, I realized that it doesn't make sense to draw text on a very small button, as the first 2-3 letters are unlikely to convey any meaningful idea about the name of the button's perf event. Just one simple condition solves the problem.

button_table.into_iter().for_each(|rect| {
    rect.draw(ui_factory, scrollable_pixmap);
    if rect.width > 10 {
        draw_caption(
            rect.node.name(),
            &ButtonDrawer {
                ui_factory,
                pixmap: scrollable_pixmap,
            },
            font,
            FONT_SIZE,
            TEXT_COLOR,
            rect.color,
            rect.pos,
            rect.width,
        );
    }
});

One function of Flame Graph Viewer is zooming to a certain frame. If you zoom to a certain frame, you get the traceback to the frame. The traceback consists of all of the parents of the frame. In order to find them, I need to hold a reference to the parent in every frame. So far, Rust doesn't allow the creation of self-referential structures with a regular pointer. If it had allowed, the code would have looked like this:

struct Node<'self> {
    parent: &'self Node
}

In short, it's impossible because the Rust compiler can't determine how long the self reference should live. Details are here.

There are a couple of popular options to deal with it:

1. Rc or his brother Arc. This way you can get a memory leak if you forget to clean references.
2. An unsafe option is raw pointer. Using this method, you have to deal with dangling pointers and null pointers. In other words, there are three cases:
   1. It points to an inaccessible memory block. The address 0x0 for example.
   2. It points the memory block which is freed, but the type of the data matches the type of the pointer.
   3. It points to the block of memory is freed and filled with some data of the type which doesn't match the type of the pointer.
3. Use one of the crates which allows you to create a self-referential structure. Of course, each one has its pros and cons.
4. Maintain a vector of objects and keep the index to the parent.

In my case the tree is immutable. The parent of a node lives as long as the tree. Once a parent is created, all of the pointers from its children are valid. This means I will not come across the problems mentioned in point 3. With this in mind, I decided to use raw pointers.

So the structure of node is

struct Node {
    parent: Option<NonNull<Node>>, // the pointer to the parent
    children: Vec<Node>, // the children nodes
    name: String,
    time: Range<u64>,
}

With absolute confidence, I used this structure. Unfortunately, it failed me when I implemented the handlers for the button clicks. Namely, once a button is clicked, the tree is rebuilt, and I see the subtree. The root of the subtree is the button I've pressed. It wasn't even clear in the beginning that I had issues with the memory. Later I found that clicking the same button gives a different subtree. It's definitely a bug.

I realized that the problem is related to the fact that vectors of children move in the memory if they don't have enough space to extend. An extension is needed when you push items into a vector. In this case, the extension involves a process called reallocation. A new space is allocated for the vector. That new space is large enough for the vector to extend. The vector data is copied to the new space in the memory and the capacity of the vector is increased.

The old space of the vector still holds the old data, but the space is marked as unallocated and can be reused. Eventually, the pointer points to the data at the old space. Dereferencing the pointer leads to these 3 situations:

1. Segmentation fault if the old space remains unallocated.
2. Glitches if the old space is allocated. In my case the old space is reused for the new nodes. I pressed on the parent node, but end up at some unexpected place of the graph.
3. Glitches again if the old space is allocated, but the type of the data is different. The pointer is dereferenced, and the data is cast to the type the pointer expects, rather than data which is actually there. It didn't happen in my case, but it's possible.

In this animation, I show two arrows (-1- and -2-) which point to their parents. Then their parents are moved, and the arrows point to an unallocated space. Then the space is reused for the vector of the children of the new Parent 3. The arrow -1- points to the first child (n1p3) of the Parent 3, which means that the child of the Parent 1 thinks that n1p3 is its parent, which is absurd.

I decided to make vectors with a big capacity to prevent the reallocations. It didn't help. I was surprised, but sure that the problem is related to reallocation. I removed the setting of the capacity and made vectors of boxes. Thus, the parent pointer points not to an element of the vector, but to the chunk of memory allocated for the box. Once a vector is moved, the addresses of the boxes are changed, but not the addresses of the nodes in the boxes.

And eventually the code of the structure looks like this

struct Node {
    parent: Option<NonNull<Node>>, // points to the data on the heap allocated by Box
    children: Vec<Box<Node>>, // the children nodes
    name: String,
    time: Range<u64>,
}

Actually, Rust has a container, named Pin, designed for these kinds of situations. It's designed to prevent references to those objects which move around the stack. The moving implies that when you pass an object as an argument to a function, it has a different address. As a result, the parent of a node in a tree should be on the heap. It was hard for me to understand. I got it only when I found how function calling is generally implemented in assembly.

The detail explanation of Pin I understood came from this video. In short the value in the container must satisfy the trait Unpin.

impl<P> Pin<P>
where
    P: Deref,
    <P as Deref>::Target: Unpin

A better data type would be children: Vec<Pin<Box<Node>>>. I avoided it for now, as I wanted to completely avoid these double references.

I really missed having a proper search in flamegraphs. Sometimes I preferred to inspect perf events in plain text format instead of the flamegraph. It allows me to use the tools like grep, fzf, sed, ogrep to manipulate the text representation of the perf events and look and examine the hot spots in the program from different angles.

In order to implement a search box, you have to address a few aspects apart from text drawing.

1. Selection
2. Deletion
3. Copying
4. Pasting
5. Jumping of the caret

I checked the code of ST in order to understand how much work needs to be done. At that moment, I wished I had used some GUI toolkit. Apart from those things, I had to implement the actual search, and I wanted to have the search be fuzzy. This reminded me that I had embedded Rofi into my ST to search for links in the terminal output.

I didn't want to use Rofi for this project. Rofi is good, but it's not as fast as Dmenu. I did a little test with it and my 38003 records were loaded momentarily. Moreover, the search results updated without any delay after I pressed a button. I needed to embed it into my application. X11 allows to set a window of one application to be a parent for a window of another application. Dmenu exposes the functionality, so you don't need to change the source code for it. In order to embed Dmenu into your application, you have to:

1. Get the ID of the window of your application. You get it when you call XCreateWindow.
2. Invoke Dmenu with the flag -w where you pass the ID.

I added a search box which makes the actual fuzzy search. The default behavior didn't meet my needs. It returned only the picked record. In order to make it usable for me, I added a couple of patches:

1. History. Just to pop up the previous search.
2. Numbers. This will return the number of the results. It allows me to relate the search results to the buttons in the graph.
3. Multiple selection. In case I want to check a couple of buttons with the same name.
4. Case-insensitive. The patch allows setting whether the search is case-sensitive or not. Given the case in a symbol name matters, I've added it.

Also, I implemented a feature in Dmenu to select all the results. So:

1. Press Enter to add the selected entry to the results and close the window.
2. Press Ctrl-Enter to add the current entry to the results.
3. Press Alt-Enter to add all of the filtered entries to the results.