BPF过滤器实现

在HURD中 目前 1dbc5f61中 BPF的实现为cBPF 即传统BPF.

在Hurd里, BPF承担的作用会和Hurd的微内核架构的IPC紧密结合.

它决定了一个网络包最终应该被送到哪个Mach receive port.

BPF过滤器

BPF最初是 Berkeley Packet Filter 就是用来过滤网络包的过滤器.

在UNIX中cBPF(classic BPF)的执行位于内核态.

而在Hurd中cBPF是hurd的用户态实现.

BPF使用了一种基于寄存器的虚拟机.

ISA指令集架构

BPF两种ISA:

  • 基本指令编码 64bit.

  • 宽指令编码, 也就是两个64bit 一共128bit.

基本指令编码

也就是64bit的编码

|opcode 8bit|regs 8bit|offset 16bit|imm 32bit|

Linux内核文档明确要求,未使用的字段必须置0

  • opcode: 操作码

操作码的组成如下:

|specific 5bit|class 3bit|


- `specific`: 这些位的意义定义于不同的`instruction class`
- `class`: 指令类别

  • regs: 源和目标寄存器的号码

regs组成如下:

|dst_reg|src_reg| # big-endian
|src_reg|dst_reg| # little-endian, 常见PC都是little-endian x86-64, arm64

- `src_reg`: 源寄存器的号码(0-10), 64bit的imm指令集对这个字段有其他用处
- `dst_reg`: 目标寄存器号码(0-10)

  • offset: 指针运算中使用的有符号偏移量 相当于i16

  • imm: 立即数 是个i32

宽指令编码

宽指令编码由两条基本指令编码组成.

第一条是基本指令编码 第二条除了imm都是0.

也就是说 宽指令编码有两个imm i32.

instruction class

opcode的class占3bit.

class

val

descri

LD

0x0

从内存/特殊来源load

LDX

0x1

从内存加载到寄存器

ST

0x2

imm写入内存

STX

0x3

把寄存器写入内存

ALU

0x4

32bit 算术/逻辑

JMP

0x5

32bit 条件/无条件控制流

JMP32

0x6

32bit 比较跳转

ALU64

0x7

64bit 算术/逻辑
算术与跳转

对于 ALU JMP 系列, opcode分为三个部分：

| code 4bit| src 1bit| class 3bit|

  • code: 操作码

  • src: 0代表使用imm作为源操作数; 1代表使用src_reg作为操作数

code操作码:

code

val

offset

op

descrip

ADD

0x0

0

dst += src

加

SUB

0x1

0

dst -= src

减

MUL

0x2

0

dst *= src

乘

DIV

0x3

0

dst = (src !=0) ? (dst/src) : 0

有符号除

SDIV

0x3

1

dst = (src ==0) ? 0 :((src == -1 && dst == LLONG_MIN) ? LLONG_MIN : (dst s/ src))

无符号除

OR

0x4

0

dst |= src

或

AND

0x5

0

dst &= src

与

LSH

0x6

0

dst <<= (src & mask)

左移

RSH

0x7

0

dst >>= (src & mask)

逻辑右移

NEG

0x8

0

dst = -dst

取负

MOD

0x9

0

dst = (src != 0) ? (dst % src) : dst

无符号取模

SMOD

0x9

1

dst = (src == 0) ? dst : ((src == -1 && dst == LLONG_MIN) ? 0: (dst s% src))

有符号取模

XOR

0xa

0

dst ^= src

异或

MOV

0xb

0

dst = src

复制src到dst

MOVSX

0xb

8/16/32

dst = (s8,s16,s32)src

符号拓展

ARSH

0xc

0

sign extending dst >>= (src & mask)

算术右移

END

0xd

0

字节交换操作

字节交换

边界行为规约:

  • 算术运算允许 下溢 与 溢出.

  • 如果除0 那么dst_reg会被设置为0.

  • ALU64 如果 LLONG_MIN 除以-1, 那么dst_reg置为LLONG_MIN

  • ALU 如果INT_MIN除以-1, 那么dst_reg置为INT_MIN

  • 如果 MOD了0, 那么ALU64的dst_reg不变.

  • 如果 MOD了0, 则ALU的dst_reg的高32位 置为0.

  • 如果 是 LLONG_MIN MOD了 -1 或者 INT_MIN MOD 了 -1, dst_reg都置为0.

字节交换指令END

hurd实现

  • hurd/libbpf/: cBPF的用户态实现

  • gnumach/device/net_io.c: Mach的内核侧实现

  • gnumach/device/net_io.h

  • gnumach/include/device/bpf.h

流程

GNU Mach在受到packet后, 核心流程是:

  1. 网络设备

  2. 执行net_filter()

  3. 选择输入或输出过滤器队列

  4. bpf_do_filter()

  5. 返回需要投递的字节数

  6. 复制到目标 Mach receive port

queue

BPF要用到的双向链表.

hurd/libbpf/queue.h hurd/libbpf/queue.c

双向链表.

struct queue_entry {
	struct queue_entry	*next;		/* next element */
	struct queue_entry	*prev;		/* previous element */
};

typedef struct queue_entry	*queue_t;
typedef	struct queue_entry	queue_head_t;
typedef	struct queue_entry	queue_chain_t;
typedef	struct queue_entry	*queue_entry_t;

if_filter_list_t

每个网络接口维护两类过滤器队列 定义于hurd/libbpf/bpf_impl.h:

  • 输入过滤器: if_rcv_port_list

  • 输出过滤器: if_snd_port_list

typedef struct
{
  queue_head_t if_rcv_port_list;	/* input filter list */
  queue_head_t if_snd_port_list;	/* output filter list */
} if_filter_list_t;

net_rev_port

每个队列的对象是 net_rev_port_t

/*
 * Receive port for net, with packet filter.
 * This data structure by itself represents a packet
 * filter for a single session.
 */
struct net_rcv_port {
	queue_chain_t	input;		/* list of input open_descriptors */
	queue_chain_t	output;		/* list of output open_descriptors */
	mach_port_t	rcv_port;	/* port to send packet to */
	int		rcv_count;	/* number of packets received */
	int		priority;	/* priority for filter */
	filter_t	*filter_end;	/* pointer to end of filter */
	filter_t	filter[NET_MAX_FILTER];
	/* filter operations */
};

其中:

  • rev_port: 匹配成功后 投递到的Mach Port.

  • priority: 过滤器优先级

  • filter[]: 过滤器程序

  • filter_end: 程序结束位置