IR decoding with BPF

In the 4.18 kernel, a new feature was merged to allow infrared (IR) decoding to be done using BPF. Infrared remotes use many different encodings; if a decoder were to be written for each, we would end up with hundreds of decoders in the kernel. So, currently, the kernel only supports the most widely used protocols. Alternatively, the lirc daemon can be run to decode IR. Decoding IR can usually be expressed in a few lines of code, so a more lightweight solution without many kernel-to-userspace context switches would be preferable. This article will explain how IR messages are encoded, the structure of a BPF program, and how a BPF program can maintain state between invocations. It concludes with a look at the steps that are taken to end up with a button event, such as a volume-up key event.

在 Linux 4.18 内核中，引入了一项新特性，使得可以使用 BPF 来进行红外（IR）信号解码。红外遥控器使用了许多不同的编码方式；如果每种编码都要在内核中实现一个解码器，那将会产生数百个解码器。因此，目前内核只支持最常用的几种协议。另一种方法是运行 lirc 守护进程来解码 IR 信号。IR 解码逻辑通常只需几行代码即可实现，因此一种更轻量、无需频繁在内核态和用户态之间切换的方案更为理想。本文将介绍红外消息的编码方式、BPF 程序的结构，以及 BPF 程序如何在多次调用之间保持状态。最后，还将展示生成按键事件（如音量增大键）的步骤。

Infrared remote controls emit IR light using a simple LED. The LED is turned on and off for shorter or longer periods, which is interpreted somewhat akin to morse code. When infrared light has been detected for a period, the result is called a “pulse”. The time between pulses when no infrared light is detected is called a “space”.

红外遥控器通过一个简单的 LED 发射红外光。LED 按一定时间间隔开关，类似于摩尔斯电码。当检测到红外光持续存在一段时间时，这段信号称为“脉冲（pulse）”；而在两个脉冲之间没有红外光的时间段则称为“间隔（space）”。

Whenever a pulse or space is detected by an IR receiver, a BPF program will be executed (if one is attached). This program consists of a single function entry point that takes a pointer to a context. For IR decoders, this context is an unsigned int value. For a packet filter, the context would instead be a packet. In our case, the lower 24 bits of the int value contain the duration of the pulse or space, in microseconds. The top eight bits define the type of the event, which can either be LIRC_MODE2_PULSE, LIRC_MODE2_SPACE, or LIRC_MODE2_TIMEOUT. The return value of the BPF program is ignored.

每当红外接收器检测到脉冲或间隔时，若有 BPF 程序挂载，则会执行该程序。该程序包含一个单一的函数入口点，其参数是一个上下文指针。对于红外解码器而言，该上下文是一个无符号整型值；而对于数据包过滤器而言，上下文则是一个数据包。在我们的场景中，该整型值的低 24 位包含脉冲或间隔的持续时间（以微秒为单位），高 8 位表示事件类型，可能是 LIRC_MODE2_PULSE、LIRC_MODE2_SPACE 或 LIRC_MODE2_TIMEOUT。BPF 程序的返回值会被忽略。

If a space between two pulses gets excessively long, it could delay the decoding of a button press. For example, we might want to know that the IR message has really ended by measuring the space after the last pulse has occurred. Since a space is a time between two pulses, we would have to wait for the next pulse from the next IR message to occur before we would get this value. So, for this reason, there is a timeout. If a space lasts longer than the timeout, it is reported as LIRC_MODE2_TIMEOUT. This is typically set at 125ms.

如果两个脉冲之间的间隔过长，可能会导致按键信号的解码被延迟。例如，我们可能需要通过测量最后一个脉冲后的间隔时间来确定 IR 消息是否真正结束。由于“间隔”定义为两个脉冲之间的时间，因此必须等待下一个脉冲出现才能获得该值。为了解决这一问题，引入了“超时（timeout）”机制：如果间隔持续时间超过超时时间（通常设为 125 毫秒），就会被报告为 LIRC_MODE2_TIMEOUT。

A BPF program can be written in a number of different ways, but the easiest way is to use clang with the target BPF. This allows the BPF program to be written in a sort of restricted C that does not allow the use of C-library functions or loops, for example.

BPF 程序可以通过多种方式编写，但最简单的方法是使用 clang 编译器并指定目标为 BPF。这允许我们用一种受限制的 C 语言来编写程序，例如不允许使用标准 C 库函数或循环语句。

To create an IR decoder in BPF, we start with:

要在 BPF 中创建一个红外解码器，可以从以下代码开始：

static int eq_margin(int duration, int expected, int margin)
{
    return (duration >= (expected - margin)) 
        && (duration <= (expected + margin));
}
 
int bpf_decoder(unsigned int *sample)
{
    int duration = *sample & LIRC_VALUE_MASK;
    bool pulse = (*sample & LIRC_MODE2_MASK) == LIRC_MODE2_PULSE;
 
    if (pulse && eq_margin(duration, 300, 100)) {
        // seen short pulse of about 300 microseconds
    }
}

Typically, IR receivers have a precision of 50µs at most. I would recommend checking for durations of at least 100µs around the value you expect.

一般来说，红外接收器的时间精度最多为 50 微秒。我建议在比较持续时间时，允许期望值上下浮动至少 100 微秒的误差范围。

Now we can parse a single pulse or space, but every IR message consists of several pulses and spaces in quick succession. In a regular C program, we would use a static variable, a global variable, or some heap memory to maintain our state while waiting for the next event. Unfortunately none of those options are available in BPF. Instead, we use BPF maps, which are a generic key-value store where the key is always an unsigned int and the value is a generic blob; we can store whatever we want. This is how we declare a BPF map to hold the IR-decoding state:

现在我们可以解析单个脉冲或间隔，但每个 IR 消息由多个脉冲和间隔快速连续组成。在普通的 C 程序中，我们会使用静态变量、全局变量或堆内存来保存状态，以便等待下一个事件。不幸的是，BPF 中这些选项都不可用。取而代之的是使用 BPF map，它是一种通用的键值存储结构，键总是无符号整型，而值可以是任意数据块；我们可以在其中存储任何需要的状态。下面是定义一个用于存储红外解码状态的 BPF map 的方法：

struct decoder_state {
    unsigned int bits;
    unsigned int count;	
};
 
struct bpf_map_def SEC("maps") decoder_state_map = {
    .type = BPF_MAP_TYPE_ARRAY,
    .key_size = sizeof(unsigned int),
    .value_size = sizeof(struct decoder_state),
    .max_entries = 1,
};

There are a few different types of BPF maps, the main ones being “array” and “hash”. Since we are only looking to store one structure, an array is more than sufficient; we thus specify max_entries as one. The key_size has to be the size of an unsigned int, no other key size is supported. The value_size is the size of our blob of data. We've declared a struct for this purpose, and we use sizeof() to ensure we have the right storage for it.

BPF map 有几种不同的类型，主要包括 “array” 和 “hash”。由于我们只需存储一个结构体，因此使用数组类型就足够了，所以将
max_entries 设为 1。
key_size 必须是无符号整型的大小，不支持其他类型的键；
value_size 则是我们存储的数据块大小。我们使用一个结构体定义了解码状态，并用
sizeof() 来确保分配的空间大小正确。

There are a number functions available to use BPF maps from our BPF code. For example, to get an our entry in decoder_state_map BPF map, we can call:

BPF 提供了一些函数以便在程序中操作 map。例如，要从
decoder_state_map 中取出我们存储的状态，可以这样调用：

int key = 0;
struct decoder_state *s = bpf_map_lookup_elem(&decoder_state_map, &key);

Unfortunately, if we try to use the pointer to the map, we will get an error when we load our BPF program: “R6 invalid mem access 'map_value_or_null'”. This is the kernel's BPF verifier complaining; it checks to ensure that a BPF program does not do anything it should not, like try to access out-of-bounds memory. It also checks for other conditions, like relying on undefined behavior or loops.

不幸的是，如果我们尝试直接使用指向 map 的指针，在加载 BPF 程序时会出现错误：“R6 invalid mem access 'map_value_or_null'”。这是内核的 BPF 验证器发出的警告。它会检查 BPF 程序是否进行了不被允许的操作，比如访问越界内存。此外，它还会检测其他情况，比如依赖未定义行为或使用循环等。

The problem here is that bpf_map_lookup_elem(), the function used to obtain a value from a BPF map, might return NULL if the key is beyond the last element. The elements of an array are pre-allocated, and we are looking for element zero out of a total of one, so this lookup should never fail. However, the BPF verifier is not aware of this so, in order to keep the verifier happy, we have to add:

问题在于，用于从 BPF map 中获取值的函数
bpf_map_lookup_elem()，如果所提供的 key 超出了最后一个元素的范围，就可能返回 NULL。虽然数组类型的 map 元素是预先分配好的，并且我们这里要查找的是仅有的第 0 个元素，所以理论上这个查找永远不会失败，但 BPF 验证器并不知道这一点。为了让验证器通过，我们必须添加以下代码：

if (!s)
    return 0;

The pointer we get from bpf_map_lookup_elem() is a direct pointer to the array, so we do not have to call bpf_map_update_elem() after making changes. The BPF verifier will check that we only use our pointer with the right offsets within our array entry; otherwise our program will not load.


bpf_map_lookup_elem() 返回的指针是直接指向数组元素的，因此我们在修改其内容后无需调用
bpf_map_update_elem()。BPF 验证器会检查我们是否仅在合法的偏移范围内使用该指针；否则，程序将无法加载。

Now that we have memory to store state, we can implement decoding. When we have decoded the IR to a button event, we can submit that event to the input subsystem using the BPF function bpf_rc_keydown(). It takes four arguments, being the BPF context, the protocol, the scancode, and the toggle bit:

现在我们已经有了用于保存状态的内存，就可以实现解码逻辑了。当我们将红外信号解码为按键事件后，可以通过 BPF 函数
bpf_rc_keydown() 向输入子系统提交事件。该函数有四个参数，分别是：BPF 上下文（context）、协议（protocol）、扫描码（scancode）以及切换位（toggle bit）。

The context for BPF is the pointer that was passed to the main BPF function; so we simply pass sample here.
The IR protocol can be used by user space to determine which protocol produced any given scancode; at the moment, nothing uses it.
The scancode is the value that was decoded. IR protocols generally encode some sort of value, and that value does not necessarily represent a key or a button. A particular remote might assign particular values with buttons; so, we need a mapping from scancode to key code. This is done using remote-control keymaps, which usually live in /lib/udev/rc_keymaps/ if the v4l-utils package is installed (or the ir-keytable package on Ubuntu or Debian).
Some IR protocols include a toggle bit. Since the IR message is repeated every 90ms or so, it is impossible to distinguish a key being held from a key released and pressed again (toggled). In the latter case, the toggle bit will change value, so rc-core knows to generate both key-up and key-down events.

BPF 的上下文参数就是传递给主函数的指针，因此我们这里直接传入
sample 即可。
IR 协议参数可供用户空间识别某个扫描码对应的协议类型；目前这个参数尚未被使用。
扫描码（scancode）是解码得到的数值。红外协议通常编码某种数值，而该数值并不一定直接代表具体的按键。不同遥控器可能会将不同数值映射为不同的按钮，因此我们需要一个从扫描码到按键码（key code）的映射。这个映射通常通过遥控器键盘映射表（keymap）实现，若系统安装了 v4l-utils（或在 Ubuntu/Debian 上安装了 ir-keytable 包），这些文件通常位于
/lib/udev/rc_keymaps/ 目录下。
某些红外协议包含一个“切换位”（toggle bit）。由于红外信号大约每 90 毫秒重复一次，因此无法直接区分按键是一直按下还是释放后再次按下的情况。而切换位的变化能帮助 rc-core 判断这是一次新的按键事件，从而生成按下和释放事件。

So those are the four arguments to bpf_rc_keydown(). Now, we can show a complete example of a fictional IR decoder.

以上便是
bpf_rc_keydown() 的四个参数。接下来，我们可以看一个完整的虚构 IR 解码器示例：

#include <linux/lirc.h>
#include <linux/bpf.h>
 
#include "bpf_helpers.h"
 
enum state {
    STATE_INACTIVE,
    STATE_FIRST_PULSE,
    STATE_SECOND_PULSE
};
 
struct decoder_state {
   enum state state;
   unsigned int space;
};
 
struct bpf_map_def SEC("maps") decoder_state_map = {
    .type = BPF_MAP_TYPE_ARRAY,
    .key_size = sizeof(unsigned int),
    .value_size = sizeof(struct decoder_state),
    .max_entries = 1,
};
 
SEC("fictional_ir")
int decode(unsigned int *sample)
{
    int key = 0;
    struct decoder_state *s = bpf_map_lookup_elem(&decoder_state_map, &key);
 
    if (!s)
        return 0;
 
    int duration = LIRC_VALUE(*sample);
 
    switch (s->state) {
    case STATE_INACTIVE:
        if (LIRC_IS_PULSE(*sample) && duration == 500) {
            s->state = STATE_FIRST_PULSE;
        }
        break;
    case STATE_FIRST_PULSE:
        if (LIRC_IS_SPACE(*sample)) {
            s->space = duration;
            s->state = STATE_SECOND_PULSE;
        } else {
            s->state = STATE_INACTIVE;
        }
        break;
    case STATE_SECOND_PULSE:
        if (LIRC_IS_PULSE(*sample) && duration == 500) {
            bpf_rc_keydown(sample, 64, s->space / 100, 0);
        }
        s->state = STATE_INACTIVE;
        break;
    }
 
    return 0;
}
 
char _license[] SEC("license") = "GPL";

Several operations are multiplexed through the bpf() system call for managing BPF programs and BPF maps, and for attaching them to devices. To create a BPF program, the BPF_PROG_LOAD is used. We have to provide a pointer to the BPF instructions, the instruction count, and a program name. If the system call is successful, we will get a file descriptor.

多个与 BPF 相关的操作都通过
bpf() 系统调用实现，包括管理 BPF 程序、BPF map 以及将程序附加到设备上。创建 BPF 程序时使用
BPF_PROG_LOAD 命令，我们需要提供 BPF 指令的指针、指令数量以及程序名。如果系统调用成功，将返回一个文件描述符。

We can create BPF maps with the BPF_MAP_CREATE command, which also returns a file descriptor on success. Once we have the program and maps created, we can attach the program to a LIRC device (e.g. /dev/lirc0) using the BPF_PROG_ATTACH command. We have to provide a file descriptor for the LIRC device and the BPF program file descriptor. Once the file descriptor is attached, we can safely exit our process and the BPF program won't be freed when its file descriptor is closed.

我们可以通过
BPF_MAP_CREATE 命令创建 BPF map，成功后同样会返回文件描述符。当程序和 map 都创建好后，可以使用
BPF_PROG_ATTACH 命令将程序附加到 LIRC 设备（例如
/dev/lirc0）。此时需要提供 LIRC 设备的文件描述符以及 BPF 程序的文件描述符。一旦附加完成，即使进程退出或关闭文件描述符，BPF 程序也不会被释放。

Currently there is a hard-coded limit of 64 BPF programs that may be attached to one LIRC device. Any more, and BPF_PROG_ATTACH will return E2BIG. Every time a new pulse or space occurs, all the BPF programs will be executed. This makes it possible to load multiple BPF decoders, so that different remotes can be used at the same time.

目前，每个 LIRC 设备最多只能附加 64 个 BPF 程序，这是一个硬编码限制。如果超过这个数量，
BPF_PROG_ATTACH 将返回
E2BIG 错误。每当新的脉冲或间隔出现时，所有已附加的 BPF 程序都会被执行。这种机制使得可以同时加载多个 BPF 解码器，从而支持多种不同的遥控器。

As you might expect there are also commands for querying and detaching BPF programs.

正如你所预料的，BPF 系统调用也提供了用于查询和分离程序的命令。

The BPF example above can be compiled it with:

上面的 BPF 示例可以使用以下命令进行编译：

clang --target=bpf -O2 -c foobar.c

You'll need to compile it with kernel headers from 4.18 (or later), and the bpf_helpers.h from the same tree. This produces foobar.o, an ELF object file.

编译时需要使用 Linux 4.18 或更高版本的内核头文件，以及来自同一源码树的
bpf_helpers.h 文件。编译完成后将生成
foobar.o，这是一个 ELF 对象文件。

Using ir-keytable, you can load this BPF program. You'll need the BPF patches, which have not been merged yet at the time of writing. In order to simulate this, the rc-loopback pseudo-receiver can be used, so no IR hardware is needed. Here are the steps to make this work:

可以使用
ir-keytable 工具加载该 BPF 程序。不过需要注意，本文撰写时所需的 BPF 补丁尚未合并。为了进行模拟测试，可以使用
rc-loopback 伪接收器，这样无需真实的红外硬件。操作步骤如下：

modprobe rc-loopback
ir-keytable -p ./foobar.o

In order to test this setup, create a file test with the following contents:

为了测试该设置，创建一个名为
test 的文件，内容如下：

pulse 500
space 1500
pulse 500

Now, run:

接着分别执行以下命令：

ir-keytable -k 15:KEY_VOLUMEUP -t

in one terminal, and:

在一个终端中执行上面的命令，然后在另一个终端中运行：

ir-ctl -s test

You should get this output:

你应当会看到如下输出：

855.168999: lirc protocol(64): scancode = 0xf
855.169009: event type EV_MSC(0x04): scancode = 0x0f
855.169009: event type EV_KEY(0x01): key_down: KEY_VOLUMEUP
855.169009: event type EV_SYN(0x00).

The ir-keytable patches above also include a Python script that converts lircd remote configuration so that it can be used with ir-keytable. This should make it possible to do without the lirc daemon. However, some protocol decoders require very basic loops, which currently the BPF verifier does not allow at all.

上述
ir-keytable 补丁中还包含一个 Python 脚本，可将 lircd 的遥控器配置文件转换为可供
ir-keytable 使用的格式。这样一来，系统就无需再运行
lirc 守护进程。不过需要注意，一些协议解码器需要使用非常基本的循环逻辑，而目前 BPF 验证器完全不允许循环结构。

Even with all lircd remote configurations supported, that would still not cover all possible remote controls. A possible solution can be found in IRP notation, a general form of description for IR protocols; it would be nice to generate BPF from that, and have support for a very broad array of remotes, without having to open-code each one. Lastly, other things than button presses are encoded in IR, for example target temperatures in air conditioning remote controls, or some remote controls include a directional pad. Supporting such devices with BPF decoders will require some further work.

即便未来支持所有 lircd 的遥控配置，也仍无法涵盖所有类型的遥控器。一种潜在的解决方案是采用 IRP 表示法（IR Protocol Notation），这是一种通用的红外协议描述格式。若能基于这种描述自动生成 BPF 程序，就可以广泛支持各种遥控器，而无需为每一种协议手工编写解码器。
最后需要指出的是，红外信号不仅用于传输按键事件，还可能包含例如空调的目标温度或带方向键的控制信号。要让 BPF 解码器支持这类复杂设备，还需要进一步的工作。