Background Tasks in radare2

July 3, 2018

Recently, I have been working on improving performance in Cutter, the radare2 GUI, especially when working with larger binaries. One major issue was that almost everything that accessed r2, such as updating the list of functions, strings, etc., was running on the main thread, and thus freezing the UI. While this is barely noticeable with smaller binaries, it can lead to a severe impact on usability for larger ones.

The obvious solution for this is to somehow run the work in the background and update the UI when it is done. Unfortunately, r2 was never designed to be multi-threaded. This may intuitively seem like a poor design choice, however there are clear reasons behind it: First, apart from potential speed-up, multi-threading would have almost no practical advantages when accessing r2 from its classic command line interface. And second, ensuring all necessary parts of the code are thread-safe would introduce an enormous additional overhead, possibly even lowering the overall performance.

I talked to pancake about this topic and he explained me the rough concept he had in mind on how to implement background tasks in r2 as some sort of a compromise between pure single-threading and full multi-threading. The idea is that multiple tasks can be running at the same time, but only one can actually do any work. Some sort of scheduling algorithm would then stop and dispatch the tasks repeatedly, making them essentially run in an interleaved fashion. The obvious disadvantage of this method is that there will be absolutely no speedup when running tasks in parallel, however it does allow executing long-running tasks in the background while still being able to execute shorter-running commands without having to wait, which is, after all, the single most important issue that background tasks in r2 are supposed to solve, so I eventually decided to implement this method and it is now ready to use and available since radare2 version 2.6.9.

I will now first explain how to use the new tasks feature in r2 from the command line interface and then go further into the actual implementation details to provide some documentation for other r2 developers.

The & command

Everything task-related is accessible through the & command:

[0x00000000]> &?
|Usage: &[-|<cmd>]Manage tasks (WARNING: Experimental. Use with caution!)
| & <cmd>  run <cmd> in a new background task
| &        list all tasks
| &j       list all tasks (in JSON)
| &= 3     show output of task 3
| &- 1     delete task #1
| &-*      delete all done tasks
| &?       show this help
| && 3     wait until task 3 is finished
| &&       wait until all tasks are finished

In order to run an arbitrary r2 command in a new background task, simply add & before it:

[0x102619fb]> & aaa
[x] Analyze all flags starting with sym. and entry0 (aa)nd entry0 (aa)
[0x102619fb]> # The analysis task is now running...
[x] Analyze function calls (aac)
[x] Analyze len bytes of instructions for references (aar)
[x] Use -AA or aaaa to perform additional experimental analysis.
[x] Constructing a function name for fcn.* and sym.func.* functions (aan)

Task 1 finished
[0x102619fb]> # done!

It is always possible to get a list of all task, including already finished ones, using only & with nothing else:

[0x102619fb]> &
 0       running  -- MAIN TASK --
 1          done  aaa

As you can see, there are two tasks in this example, each having a number which uniquely identifies it. The first one, with id 0, is the main task, which is the one on which everything that is not explicitly run in a background task is executed on. The second one, having id 1, is the one we have manually started above. We can remove it from the list by using &-:

[0x102619fb]> &- 1
[0x102619fb]> &
 0       running  -- MAIN TASK --

It is also possible to retrieve the output generated by the command run in the task using &=:

[0x00005000]> & izz
[0x00005000]>
Task 2 finished
[0x00005000]> &
 0       running  -- MAIN TASK --
 2          done  izz
[0x00005000]> &= 2
Do you want to print 1717 lines? (y/N) y
000 0x00000034 0x00000034   4  10 (LOAD0) utf16le @8\t@
001 0x00000238 0x00000238  27  28 (.interp) ascii /lib64/ld-linux-x86-64.so.2
002 0x00001081 0x00001081  11  12 (.dynstr) ascii libcap.so.2
...
1713 0x0002037b 0x000000df   4   5 (.shstrtab) ascii .bss
1714 0x00020380 0x000000e4   8   9 (.shstrtab) ascii .comment

This sums up the most important commands to work with tasks. It should be noted, however, that not all commands are currently safe to be run in background tasks. See the section below about task-safety for more information on this.

Implementation

Tasks are part of RCore, with most of the relevant code being located in libr/core/task.c. The interface for using tasks currently looks like this:

// r_core.h

typedef void (*RCoreTaskCallback)(void *user, char *out);

typedef enum {
	R_CORE_TASK_STATE_BEFORE_START,
	R_CORE_TASK_STATE_RUNNING,
	R_CORE_TASK_STATE_SLEEPING,
	R_CORE_TASK_STATE_DONE
} RTaskState;

typedef struct r_core_task_t {
	int id;
	RTaskState state;
	void *user;
	RCore *core;
	RThreadCond *dispatch_cond;
	RThreadLock *dispatch_lock;
	RThread *thread;
	char *cmd;
	char *res;
	bool cmd_log;
	RConsContext *cons_context;
	RCoreTaskCallback cb;
} RCoreTask;

R_API RCoreTask *r_core_task_get(RCore *core, int id);
R_API void r_core_task_print(RCore *core, RCoreTask *task, int mode);
R_API void r_core_task_list(RCore *core, int mode);
R_API const char *r_core_task_status(RCoreTask *task);
R_API RCoreTask *r_core_task_new(RCore *core, bool create_cons, const char *cmd, RCoreTaskCallback cb, void *user);
R_API void r_core_task_free(RCoreTask *task);
R_API void r_core_task_enqueue(RCore *core, RCoreTask *task);
R_API int r_core_task_run_sync(RCore *core, RCoreTask *task);
R_API void r_core_task_sync_begin(RCore *core);
R_API void r_core_task_sync_end(RCore *core);
R_API void r_core_task_continue(RCoreTask *t);
R_API void r_core_task_sleep_begin(RCoreTask *task);
R_API void r_core_task_sleep_end(RCoreTask *task);
R_API int r_core_task_del(RCore *core, int id);
R_API void r_core_task_del_all_done(RCore *core);
R_API RCoreTask *r_core_task_self(RCore *core);
R_API void r_core_task_join(RCore *core, RCoreTask *current, RCoreTask *task);

RCore also contains some fields that are relevant for tasks:

// r_core.h

typedef struct r_core_t {
	...
	int task_id_next;
	RList *tasks;
	RList *tasks_queue;
	RCoreTask *current_task;
	RCoreTask *main_task;
	RThreadLock *tasks_lock;
	...
} RCore;

Scheduling and Running

When a task is created using r_core_task_new() and enqueued as a background tasks using r_core_task_enqueue(), a new thread is started for the it. Even though only one task is doing actual work at any point in time, it is still necessary to run each of them on a separate thread in order to be able to switch between tasks while retaining their full callstacks. When the thread is started, the task first checks whether there are any other tasks which are currently running. If that is not the case, it can start executing its command. Otherwise, it enqueues itself in core->tasks_queue and waits for its own dispatch_cond to be signaled.

Long-running processes in r2 often call r_cons_is_breaked() repeatedly to check if they should be interrupted. This function will now automatically call r_core_task_schedule(), which is responsible for scheduling and dispatching tasks. It checks whether core->tasks_queue contains any tasks that are currently waiting to be scheduled, and if that is the case, it pops a single task from the queue and signals that task’s dispatch_cond. Then, it will wait until its own dispatch_cond is signalled again.

The result of this behaviour is that the tasks schedule and dispatch each other automatically in a cyclic manner.

Swapping RCons

Generating text output in r2 is achieved by calling functions from RCons, such as r_cons_print(). These functions operate on a global instance of RCons, in which the output is accumulated and can eventually be printed to stdout or used further internally. In its original form, this behaviour is unsuited for concurrent tasks, because they would alternately write into the same buffer, thus creating a corrupt result.

One way to solve this would be to add an additional parameter to each affected r_cons_* function, containing for example a pointer to some sort of local RCons context. However, because these functions are extremely frequently used throughout the entire codebase, this would require refactoring each of these locations. Even worse, the context pointer would have to be passed through all functions that require it in any function they are calling, which would also require changing their signatures.

Instead, I decided to go another way by leaving the r_cons_* function signatures as they are, but frequently swapping out parts of the global RCons instance with task-local data. This is why all affected fields of RCons have been moved to a new struct called RConsContext:

typedef struct r_cons_context_t {
	RConsGrep grep;
	RStack *cons_stack;
	char *buffer;
	int buffer_len;
	int buffer_sz;

	bool breaked;
	RStack *break_stack;
	RConsEvent event_interrupt;
	void *event_interrupt_data;
} RConsContext;

typedef struct r_cons_t {
	RConsContext *context;
	...
}

The context pointer will be swapped out depending on the current task. This means all code can keep using any r_cons_* functions as ususal, but the output will eventually be redirected correctly.

The Main Task

As already mentioned above, there is always a single task called the main task, on which everything is executed that is not explicitly run in a background task. Having this task is necessary for scheduling between the main work and any background tasks to work. The main task has no thread explicitly attached to it since its work is generally simply run on the main thread. For signalling the beginning and end of work, the functions r_core_task_sync_begin() and r_core_task_sync_end() exist. In the normal radare2 executable, these functions are called once at the beginning and the end of main(), respectively.

Sleeping

Sometimes a task may need to wait for something else to complete while not being able to do anything in this time. The most prominent example for this right now is when r2 waits for user input on the command line. No r_cons_is_breaked() is called during that time, so once the main tasks hits this part, all other tasks would automatically be blocked, even though the main task is not actually accessing anything critical.

To solve this, tasks can enter and leave a sleeping state using r_core_task_sleep_begin() and r_core_task_sleep_end(). When a task is sleeping, it will be ignored in the scheduling process and all other tasks will be able to continue running. r_core_task_sleep_end() enqueues the task to be scheduled again and blocks until it is eventually dispatched.

Task-Safety

While this approach to implement background tasks prevents any issues arising from actual multi-threading, certain kinds of race conditions may still occur. Some commands may, for example, temporarily change some eval vars and reset them before exiting. Running such a command, interleaved with another command that accesses one of these eval vars, will thus result in some undesired behaviour.

In order for a command to be considered task-safe, it must not keep any global state in an altered way that differs from its intended purpose when calling r_cons_is_breaked().

Next Steps

Since the basic implementation of tasks now works fairly reliable, the next step will be to use them in Cutter wherever it makes sense. It will be necessary to carefully go through the code of each command that should be run in the background in Cutter in order to ensure task-safety. A few kinds of processes are already executed in tasks in Cutter 1.5.

One feature that is not yet implemented is the possibility to interrupt background tasks while they are still running. It should, however, be possible to implement that quite easily and I plan to do it soon.

– thestr4ng3r (Florian Märkl)