Google Summer of Code 0x06: Maps

Why to leave eBPF maps in all of this?

Motivation

At this point we can use Lunatik to script 3 solid subsystems: xdp, tc, sched_ext. But the issue is the Lua scripts are not stateful.

Since these scripts run in softirq / hardirq path (per packet or per task) we need a way to maintain state in between the invokations to make Lua do much more. An example use case could be: a runtime-aware scheduler.

Something like:

local stats = map

local function workload(ctx)
    local task = ctx:task()
    local pid = task:pid()
    local runtime = task:runtime()

    local last_runtime = stats:lookup(pid) or runtime
    local delta = runtime - last_runtime

    stats:update(pid, runtime)

    if delta > 5 * MS then
        ctx:dsq(BATCH)
    else
        ctx:dsq(DEFAULT)
    end
end

sched.attach(workload)

The current runtime alone isn’t enough. To know how much a task has run since the previous invocation, we need to remember its previous runtime. Since workload() is invoked repeatedly for different tasks, this state also needs to be associated with the task: here, using its PID as the map key.

The important realization is the state should not be restricted to the local script state but a global state.

Enter eBPF maps

Maps provide a way for eBPF programs to communicate with each other (kernel space) and with user space ¹.

This is perfect, since we are already building a bridge between Lunatik and eBPF. The bridge will be incomplete without a support for Lua scripts to interact with eBPF maps.

Design

The kernel owns the map object and other program use it. Likewise Lua can be a consumer, it need not own the map object itself. So we can design the separation like this:

• The kernel creates / frees / deletes the map.
• Lua can interact with the map, as in update, add, delete some key from the map.

This requires Lunatik to be able to use an existing map object somehow.

Challenges

So, I quickly started looking for the right API to interact with these maps. eBPF maps are created via bpf(BPF_MAP_CREATE, ...) and accessed via bpf_map_lookup_elem, bpf_map_update_elem, and bpf_map_delete_elem helpers. We want to access these via kernel’s internal map API without going through syscall interface.

The following APIs are exposed by kernel to use:

• All userspace calls (through libbpf) go through SYSCALL_DEFINE3()
• bpf_map_get(u32 ufd)
• bpf_map_get_with_uref(u32 ufd)

Map resolution normally happens as follows:

• from userspace we call open(path) to get an fd on the pinned bpffs file.
• now we share this fd to kernel side
• we can call bpf_map_get_with_uref(u32 ufd) from kernel side to resolve the fd to pointer to struct bpf_map

This will need the file descriptor which needs to be created via a process context. But Lunatik does not run in process context.

So we need some other way to recover the map object.

Pinned maps

Fortunately, we can pin eBPF maps to a filesystem path like so:

sudo bpftool map create /sys/fs/bpf/runtime_stats \
    type hash \
    key 4 \
    value 16 \
    entries 4096 \
    name runtime_stats

This will create a hash type eBPF map, having key size 4, value size 16, limited to 4096 entries, named runtime_stats and pinned to the filesystem path /sys/fs/bpf/runtime_stats

Now, we just need a way to recover the map object from the pinned filesystem somehow.

Maps API

We need to bypass the standard way and use other kernel helpers to resolve map pointer directly from bpffs path. We can use kern_path to resolve the dentry without triggering the open handler, then read inode->i_private directly where bpffs stores the pointer to struct bpf_map.

I verified this approach via a kernel module POC ².

#include <linux/bpf.h>
#include <linux/namei.h>
#include <linux/fs.h>

static struct bpf_map *luabpf_map_open(lua_State *L)
{
    const char *path = luaL_checkstring(L, 1);
    struct path kpath;
    struct bpf_map *map;
    int err;

    err = kern_path(path, LOOKUP_FOLLOW, &kpath);
    if (err)
        return luaL_error(L, "kern_path failed: %d", err);

    map = d_inode(kpath.dentry)->i_private;
    path_put(&kpath);

    if (!map || IS_ERR(map))
        return luaL_error(L, "not a valid bpf map path");

    bpf_map_inc(map); // increase reference counter
    return map;
}

• lookup(key) on the map pointer will return the value stored in the map for the provided key.
• update(key, data) on the map pointer will update the map for the provided key with the given data.
• delete(key) on the map pointer will delete the key from the map.
• Once we have the pointer to struct bpf_map, we could call kernel ops helpers defined here to do lookup, update, delete.

The final API after multiple reviews iterations, looks something like this:

local hash = require("bpf").hash
local bpf = require("linux.bpf")

local m = hash("/sys/fs/test_map")

local info = m:info()
print(string.format("info.type = %d", info.type))
print(string.format("info.key_size = %d", info.key_size))
print(string.format("info.value_size = %d", info.value_size))
print(string.format("info.max_entries = %d", info.max_entries))

print(m:lookup("foo"))

m:update("foo", "baz", bpf.ANY)
print(m:lookup("foo"))

m:delete("foo")
print(m:lookup("foo"))

m:close()

Cleanup

close() will decrease the reference counter via bpf_map_put(struct bpf_map *map) so that no further operations may be done on the map pointer.