其实，bpf 子系统里并没有一个叫 bpf_binary_search() 的 helper 函数。
但并不是说，在 eBPF 里就实现不了二分查找了。
小需求
怎么判断一个 IP 地址是否在某几个 CIDR 里？
已知方法有二：
lpm_trie[1] eBPF Talk: 实战经验之 loop
但它们各自有各自的优缺点：
lpm_trie实用性强，适合以 CIDR 为 key 的比较复杂的场景。lpm_trie在性能上并不占优势，它的查找性能不稳定，取决于 CIDR 的 bit 分布情况，不适用于高效地判断一个 IP 是否在某几个 CIDR 里的场景。loop方法的实现简单，性能稳定，对于少量（可能小于等于 8）CIDR 的情况，它能比较高效地判断一个 IP 是否在这几个 CIDR 里。loop方法的缺点也比较明显，随着 CIDR 的数量的增加，它的性能会线性下降。
有没有一种查找性能稳定、且查找性能跟 loop 方法差不多的方法呢？
如果不直接限定在 eBPF 里，那么，答案就是二分查找了。
二分查找
对二分查找算法不是很熟悉，上 ChatGPT：
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if target is present at the middle
if (arr[mid] == target)
return mid;
// If target is greater, ignore the left half
if (arr[mid] < target)
left = mid + 1;
// If target is smaller, ignore the right half
else
right = mid - 1;
}
// Target was not found
return -1;
}
eBPF 里的二分查找
抄，但不能直接抄：
struct delay_cidr {
__u32 start;
__u32 end;
};
typedef struct {
struct delay_cidr cidrs[DELAY_CIDR_CAPACITY];
} delay_cidrs_t;
static const volatile delay_cidrs_t delay_cidrs;
static const volatile __u32 delay_cidrs_len = 0;
static __always_inline bool
__should_delay_sip(__be32 ip)
{
__u32 lo = 0;
__u32 hi = delay_cidrs_len - 1;
__u32 addr = bpf_ntohl(ip);
#pragma clang loop unroll(full)
for (__u32 index = 0; index < 32; index++) {
if (lo > hi) // Checking lo > hi for the end of binary search.
return false;
__u32 mid = (lo + hi) >> 1;
if (mid >= DELAY_CIDR_CAPACITY) // It's required to do bound check for mid.
return false;
struct delay_cidr *cidr = (typeof(cidr))&delay_cidrs.cidrs[mid];
if (addr >= cidr->start && addr <= cidr->end) {
return true;
}
if (addr < cidr->start) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return false;
}
其中需要注意：
将 IP 地址转换为 __u32类型，是为了方便比较。eBPF 里只支持有限次数的循环，所以不能直接套用 while (lo <= hi)。访问 cidrs数组前，需要先对mid进行边界检查。先判断 IP 地址是否在 mid对应的 CIDR 里，再调整lo和hi。
完美，以上代码片段实现了 log2 级别的查找性能。
但是，以上代码片段通不过 verifier，报错 "R3 unbounded memory access, make sure to bounds check any such access"。
eBPF 里的二分查找（bpf_loop）
因为上面的代码片段过不了 verifier，所以，我们需要换一种思路：借助 bpf_loop() helper 函数。
struct delay_ctx {
__u32 lo, hi;
__u32 ip;
bool found;
};
static long loop_delay_cidrs(__u32 index, struct delay_ctx *ctx)
{
if (!ctx) // It's required to check NULL ctx.
return 1;
if (ctx->lo > ctx->hi) // Checking lo > hi for the end of binary search.
return 1;
__u32 mid = (ctx->lo + ctx->hi) >> 1;
if (mid >= DELAY_CIDR_CAPACITY) // It's required to do bound check for mid.
return 1;
struct delay_cidr *cidr = (typeof(cidr))&delay_cidrs.cidrs[mid];
if (ctx->ip >= cidr->start && ctx->ip <= cidr->end) {
ctx->found = true;
return 1;
}
if (ctx->ip < cidr->start) {
ctx->hi = mid - 1;
} else {
ctx->lo = mid + 1;
}
return 0;
}
static __always_inline bool
__should_delay_sip(__be32 ip)
{
struct delay_ctx ctx = {
.lo = 0,
.hi = delay_cidrs_len - 1,
.ip = bpf_ntohl(ip),
.found = false,
};
bpf_loop(32, loop_delay_cidrs, &ctx, 0);
return ctx.found;
}
该代码片段的实现逻辑跟 for 循环的实现逻辑一样，但是，它可以通过 verifier。
不过嘛，bpf_loop() helper 函数要求 5.17 内核。
bpf: Add bpf_loop helper[2] since 5.17 kernel.
小结
没有做性能测试，不过能够在 eBPF 里实现二分查找是一件很有意思的事情，不是吗？
二分查找的实现思路有两个：
通过 for循环实现。通过 bpf_loop()helper 函数实现。
其中，相比 bpf_loop() helper 的实现方式，for 循环实现的方式更具有普适性。
问题：有没有办法解决 for 循环实现方式的 verifier 问题呢？
参考资料
lpm_trie: https://github.com/torvalds/linux/blob/master/kernel/bpf/lpm_trie.c
[2]bpf: Add bpf_loop helper: https://github.com/torvalds/linux/commit/e6f2dd0f80674e9d5960337b3e9c2a242441b326
