How does Fio use an RB tree for verify - vincentkfu/fio-blog GitHub Wiki

What are the details of how Fio tracks verify metadata in an RB tree? A recent pull request from Yehor Malikov offered improvements in Fio's handling of a red-black (RB) tree for tracking verify workload metadata. Nodes are added to the tree as write operations are issued and then removed as verify IOs are issued. In the course of reviewing the pull request I compiled these notes on how Fio uses this tree. 

Data structures

Fio creates a tree out of struct io_piece nodes:

/*
 * When logging io actions, this matches a single sent io_u
 */
struct io_piece {
        union {
                struct fio_rb_node rb_node;
                struct flist_head list;
        };
        struct flist_head trim_list;
        union {
                int fileno;
                struct fio_file *file;
        };
        unsigned long long offset;
        uint64_t numberio;
        unsigned long len;
        unsigned int flags;
        enum fio_ddir ddir;
        unsigned long delay;
        unsigned int file_action;
};

These nodes contain metadata on write operations that are to be verified. This metadata includes the file, offset, sequence number, length, and flags.

struct thread_data contains a member struct rb_root io_hist_tree that is the root of the RB tree.

struct fio_rb_node
{
        intptr_t rb_parent_color;
#define RB_RED          0
#define RB_BLACK        1
        struct fio_rb_node *rb_right;
        struct fio_rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
        struct fio_rb_node *rb_node;
};

Tree Construction

Let us start discussing how the RB tree is used by first describing the steps carried out during the write phase of a verify workload during which the RB tree is constructed.

Nodes for write operations are added to the RB tree via the log_io_piece() function which is called in do_io() after an IO is composed but before it is issued:

                /*
                 * Always log IO before it's issued, so we know the specific
                 * order of it. The logged unit will track when the IO has
                 * completed.
                 *
                 * Trim command is determined by @io_u loggged in the @io_hist
                 * based on the percentage of the given value to
                 * --trim_percentage=<%>.  Log @io_u for trim command even in
                 * --do_verify=0 case.
                 */
                if (td_write(td) && io_u->ddir == DDIR_WRITE &&
                    (td->o.do_verify || td->trim_verify) &&
                    td->o.verify != VERIFY_NONE &&
                    !td->o.experimental_verify)
                        log_io_piece(td, io_u);

Here is the code for log_io_piece()

void log_io_piece(struct thread_data *td, struct io_u *io_u)
{
        struct fio_rb_node **p, *parent;
        struct io_piece *ipo, *__ipo;

        ipo = calloc(1, sizeof(struct io_piece));
        init_ipo(ipo);
        ipo->file = io_u->file;
        ipo->offset = io_u->offset;
        ipo->len = io_u->buflen;
        ipo->numberio = io_u->numberio;
        ipo->flags = IP_F_IN_FLIGHT;

        io_u->ipo = ipo;

        if (io_u->flags & IO_U_F_ZEROED)
                ipo->flags |= IP_F_ZEROED;
        else if (io_u->flags & IO_U_F_ERRORED)
                ipo->flags |= IP_F_ERRORED;

        if (io_u_should_trim(td, io_u)) {
                flist_add_tail(&ipo->trim_list, &td->trim_list);
                td->trim_entries++;
        }

        /*
         * Sort writes if we don't have a random map in which case we need to
         * check for duplicate blocks and drop the old one, which we rely on
         * the rb insert/lookup for handling. Sort writes if we have offset
         * modifier which can also create duplicate blocks.
         */
        if (!fio_offset_overlap_risk(td)) {
...
                return;
        }

        RB_CLEAR_NODE(&ipo->rb_node);

        /*
         * Sort the entry into the verification list
         */
restart:
        p = &td->io_hist_tree.rb_node;
        parent = NULL;
        while (*p) {
                int overlap = 0;
                parent = *p;

                __ipo = rb_entry(parent, struct io_piece, rb_node);
                if (ipo->file < __ipo->file)
                        p = &(*p)->rb_left;
                else if (ipo->file > __ipo->file)
                        p = &(*p)->rb_right;
                else if (ipo->offset < __ipo->offset) {
                        p = &(*p)->rb_left;
                        overlap = ipo->offset + ipo->len > __ipo->offset;
                }
                else if (ipo->offset > __ipo->offset) {
                        p = &(*p)->rb_right;
                        overlap = __ipo->offset + __ipo->len > ipo->offset;
                }
                else
                        overlap = 1;

                if (overlap) {
                        dprint(FD_IO, "iolog: overlap %llu/%lu, %llu/%lu\n",
                                __ipo->offset, __ipo->len,
                                ipo->offset, ipo->len);
                        td->io_hist_len--;
                        rb_erase(parent, &td->io_hist_tree);
                        remove_trim_entry(td, __ipo);
                        if (!(__ipo->flags & IP_F_IN_FLIGHT))
                                free(__ipo);
                        goto restart;
                }
        }

        rb_link_node(&ipo->rb_node, parent, p);
        rb_insert_color(&ipo->rb_node, &td->io_hist_tree);
        ipo->flags |= IP_F_ONRB;
        td->io_hist_len++;
}

This function creates a node and sets its members (including file, offset, length, and sequence number). It also sets the IO piece's in-flight flag since IOs are added to the tree as they are submitted.

If the write workload uses a random map or is sequential with no possibility of overlapping write operations then the IOs are simply stored in a list and no RB tree is used. On the other hand, when the write phase can potentially contain overwrites, Fio stores nodes in an RB tree to efficiently detect overlaps. In this case Fio first searches through the RB tree to determine if the current IO piece overlaps with any nodes already in the tree. If an overlap is found, the existing node is removed and if it is not currently in flight, its memory is deallocated. Then, the process is repeated until no overlaps are found. Finally, after the tree is cleared of all overlaps, the new IO piece is added to the tree.

This point is where one of the pull request fixes comes in. Fio's original approach leads to a slow memory leak because in-flight nodes that are evicted from the tree never have their memory deallocated. The second patch of the pull request clears the IO piece's on-tree flag when the node is evicted and then during IO completion, checks if the on-tree flag is unset. If so, the IO piece is deallocated.

During the write phase of a verify workload, the RB tree is also modified when IOs are completed. This may happen via unlog_io_piece() which is called from three different sites:

  • io_u.c:io_completed()
  • backend.c:io_queue_event() (two call sites)

io_completed() is called for each IO after it is completed. The portion relevant to the RB tree is here:

        /*
         * Mark IO ok to verify
         */
        if (io_u->ipo) {
                /*
                 * Remove errored entry from the verification list
                 */
                if (io_u->error)
                        unlog_io_piece(td, io_u);
                else {
                        atomic_store_release(&io_u->ipo->flags,
                                        io_u->ipo->flags & ~IP_F_IN_FLIGHT);
                }
        }

If the IO operation has an IO piece defined, tree processing is carried out. If the result of the IO was an error, unlog_io_piece() is called because this errored IO should not be verified. Otherwise, the in-flight flag is cleared since the IO has completed successfully.

io_queue_event() processes the return value of an ioengine's queue() hook. If queue() returns FIO_Q_COMPLETED but zero bytes were transferred to the device, unlog_io_piece() is called. Similarly, if queue() returns FIO_Q_BUSY, unlog_io_piece() is also called.

What does unlog_io_piece() actually do?

void unlog_io_piece(struct thread_data *td, struct io_u *io_u)
{
        struct io_piece *ipo = io_u->ipo;

...
        if (!ipo)
                return;

        if (ipo->flags & IP_F_ONRB)
                rb_erase(&ipo->rb_node, &td->io_hist_tree);
        else if (ipo->flags & IP_F_ONLIST)
                flist_del(&ipo->list);

        free(ipo);
        io_u->ipo = NULL;
        td->io_hist_len--;
}

If the IO operation is associated with an RB tree node, the node is removed from the tree, memory for the node is deallocated, and the tree size is decremented.

Tree consumption

How are nodes consumed from the RB tree? This happens in get_next_verify():

int get_next_verify(struct thread_data *td, struct io_u *io_u)
{
        struct io_piece *ipo = NULL;

        /*
         * this io_u is from a requeue, we already filled the offsets
         */
        if (io_u->file)
                return 0;

        if (!RB_EMPTY_ROOT(&td->io_hist_tree)) {
                struct fio_rb_node *n = rb_first(&td->io_hist_tree);

                ipo = rb_entry(n, struct io_piece, rb_node);

                /*
                 * Ensure that the associated IO has completed
                 */
                if (atomic_load_acquire(&ipo->flags) & IP_F_IN_FLIGHT)
                        goto nothing;

                rb_erase(n, &td->io_hist_tree);
                assert(ipo->flags & IP_F_ONRB);
                ipo->flags &= ~IP_F_ONRB;
        } else if (!flist_empty(&td->io_hist_list)) {
...
        }

        if (ipo) {
                td->io_hist_len--;

                io_u->offset = ipo->offset;
                io_u->verify_offset = ipo->offset;
                io_u->buflen = ipo->len;
                io_u->numberio = ipo->numberio;
                io_u->file = ipo->file;
                io_u_set(td, io_u, IO_U_F_VER_LIST);

                io_u_clear(td, io_u, IO_U_F_TRIMMED | IO_U_F_ZEROED | IO_U_F_ERRORED);

                if (ipo->flags & IP_F_TRIMMED)
                        io_u_set(td, io_u, IO_U_F_TRIMMED);
                else if (ipo->flags & IP_F_ZEROED)
                        io_u_set(td, io_u, IO_U_F_ZEROED);
                else if (ipo->flags & IP_F_ERRORED)
                        io_u_set(td, io_u, IO_U_F_ERRORED);

                if (!fio_file_open(io_u->file)) {
                        int r = td_io_open_file(td, io_u->file);

                        if (r) {
                                dprint(FD_VERIFY, "failed file %s open\n",
                                                io_u->file->file_name);
                                return 1;
                        }
                }

                get_file(ipo->file);
                assert(fio_file_open(io_u->file));
                io_u->ddir = DDIR_READ;
                io_u->xfer_buf = io_u->buf;
                io_u->xfer_buflen = io_u->buflen;

                remove_trim_entry(td, ipo);
                free(ipo);
                dprint(FD_VERIFY, "get_next_verify: ret io_u %p\n", io_u);

                return 0;
        }

nothing:
        dprint(FD_VERIFY, "get_next_verify: empty\n");
        return 1;
}

If the RB tree is not empty, Fio obtains the first node from the tree. If the first node belongs to an in-flight IO, nothing is returned. If the first node has already completed, the node is removed from the tree and the node's on-RB-tree flag is cleared. The relevant members of the IO piece are transferred over to struct io_u and the memory for this IO piece is deallocated.

This is the second site where the pull request offers an improvement. Instead of fruitlessly returning when the first member of the tree is in flight, the pull request traverses the RB tree to find the first completed IO piece. This lessens the possibility of read starvation if the first node in the tree happens to belong to an in-flight IO.

Conclusion

These notes document how Fio uses an RB tree to track metadata for verify workloads. With a clear understanding of how the tree is used I was able to carry out a thorough review of the pull request and ultimately merge it. 

Notes

  • To understand how the RB tree is used I used cscope to find references to the RB tree root
  • One other place where the tree is accessed is backend.c:do_dry_run(). This is the counterpart to do_io() that builds the RB tree for a verify_only=1 Fio run. 
  • GitHub Copilot reviewed the pull request and identified a bug in an error path. When an in-flight IO piece is removed from the RB tree in log_io_piece(), the tree's length is decremented. If the associated IO returns an error, the tree's length is decremented for a second time in unlog_io_piece(). Copilot's analysis seems reasonable although this issue requires a unique set of circumstances to manifest and is difficult to reproduce and test a fix.
⚠️ **GitHub.com Fallback** ⚠️