如何用二叉树改造cBPF程序提高BPF执行效率

偏执的太偏执、 2023-02-27 10:32 10阅读 0赞

在前一篇文章里，我描述了tcpdump的内置BPF程序处理非常多的匹配项时是何等的不堪：  
[https://blog.csdn.net/dog250/article/details/107367725][https_blog.csdn.net_dog250_article_details_107367725]

文中我列举了实验的过程和结果，最后我给出了建议， ***预处理BPF程序，采用相对高效的匹配方式替换遍历式匹配。*** 然后写了些形而上的吐槽，文章就结束了。

记得在很早以前我在优化iptables规则以及路由查找的时候，就提出过类似的思路，即 ***预处理规则集*** 。但从始至终都没能看到一行代码，看起来相当得有破无立。但这是一个古老的故事。

我不会编程，编的不好，但我也不是一点也不会，我还是稍微会一点编程的，本文给出一些代码，演示一下如何生成二叉树匹配的BPF程序。

依然假设匹配IP地址，我希望用程序生成一个BPF指令序列，该序列采用二叉树匹配的方式来进行源IP地址匹配，Java代码如下：

// GenBPF.java
    public class GenBPF { 
    	static int pos = 0;
    	static int ret1 = 0;
    	public static final int ROUNTD_MARK = 0;
    	public static final int ROUNTD_CALC = 1;
    	public static final int ROUNTD_PRINT = 2;
    
    	/* 内部类，其对象表示一条BPF指令的二叉树节点。 */
    	class BPFInsn { 
    		int pos;
    		int addr;
    
    		BPFInsn left;
    		BPFInsn right;
    		StringBuffer code;
    
    		BPFInsn(int addr) { 
    			this.addr = addr;
    			this.left = null;
    			this.right = null;
    			code = new StringBuffer(128);
    		}
    	}
    
    	public BPFInsn Insert(BPFInsn insn_root, int addr) { 
    		if (insn_root == null) { 
    			return new BPFInsn(addr);
    		}
    		if (addr > insn_root.addr) { 
    			insn_root.right = Insert(insn_root.right, addr);
    		} else { 
    			insn_root.left = Insert(insn_root.left, addr);
    		}
    		return insn_root;
    	}
    
    	public static void traval(BPFInsn insn_root, int type) { 
    		if (insn_root == null) { 
    			return;
    		}
    		if (type == ROUNTD_MARK) { 
    			insn_root.pos = pos;
    			pos += 2;
    		} else if (type == ROUNTD_CALC) { 
    			int right_dist;
    			if (insn_root.right != null) { 
    				right_dist = insn_root.right.pos - insn_root.pos - 1;
    				insn_root.code.append("{OP_JGT, ");
    				insn_root.code.append(right_dist);
    				insn_root.code.append(", 0, ");
    				insn_root.code.append(Integer.toHexString(insn_root.addr));
    				insn_root.code.append("},\n");
    			} else { 
    				insn_root.code.append("{OP_JA, 0, 0, 0},\n"); // NOP
    			}
    			insn_root.code.append("{OP_JEQ, ");
    			insn_root.code.append(ret1);
    			insn_root.code.append(", ");
    			insn_root.code.append(insn_root.left != null?0:ret1 + 1);
    			insn_root.code.append(", ");
    			insn_root.code.append(Integer.toHexString(insn_root.addr));
    			insn_root.code.append("},\n");
    			ret1 -= 2;
    		} else if (type == ROUNTD_PRINT) { 
    			System.out.println(insn_root.code);
    		}
    		traval(insn_root.left, type);
    		traval(insn_root.right, type);
    	}
    
    	public static void main(String argv[]) { 
    		GenBPF instance = new GenBPF();
    
    		/* BPFInsn root = instance.Insert(null, 15); instance.Insert(root, 7); instance.Insert(root, 24); instance.Insert(root, 4); instance.Insert(root, 11); instance.Insert(root, 18); instance.Insert(root, 30); instance.Insert(root, 2); instance.Insert(root, 5); instance.Insert(root, 8); instance.Insert(root, 13); instance.Insert(root, 16); instance.Insert(root, 20); instance.Insert(root, 28); instance.Insert(root, 32); */
    		/* 请注意下面的IP地址插入顺序，我做了简化： * 我以比较平衡的顺序对元素进行了插入，因为我的二叉树自身没有平衡操作， * 我就只能在插入的时候来确保平衡，否则如果顺序插入，就会退化成链表。 * * 事实上，标准的做法是将所有IP地址打乱，随机插入到二叉树中！ */
    		BPFInsn root = instance.Insert(null, 0xc0a83863);
    		instance.Insert(root, 0xc0a83861);
    		instance.Insert(root, 0xc0a83860);
    		instance.Insert(root, 0xc0a83862);
    		instance.Insert(root, 0xc0a83865);
    		instance.Insert(root, 0xc0a83864);
    		instance.Insert(root, 0xc0a83866);
    
    		/* 第一轮中序遍历：完成中序顺序的标记。 */
    		traval(root, ROUNTD_MARK);
    		/* 获取return true和return false的相对偏移。 */
    		ret1 = pos - 2;
    		/* 第二轮中序遍历：计算跳转的相对偏移，设置jt，jf指令。 */
    		traval(root, ROUNTD_CALC);
    		/* 第三轮中序遍历：打印BPF程序指令。 */
    		traval(root, ROUNTD_PRINT);
    	}
    }

代码很简单，只说明一点，由于时间仓促，我的二叉树没有自带平衡功能，所以如果是按照IP地址的升序或降序顺序来插入节点的话，势必会将二叉树退化成链表，这就和tcpdump自带的那玩意儿一模一样了，所以我偷了个懒，把一棵相对平衡的二叉树画在本子上，以这棵已经构建好的二叉树为蓝本来进行插入，从而确保平衡。

注释里也写了，其实只要把IP地址足够随机地均匀打乱，然后插入，那就能确保足够平衡，但随机化操作会增加代码量，第一影响可读性，第二我是能不编程就不编程，实在是编不好，只能省略。

至于AVL树，红黑树这些，我觉得我得吭哧很长时间，最终还不一定能写好，所以作罢。

看看上面的程序的输出吧：

[root@localhost bpf]# javac GenBPF.java
    [root@localhost bpf]# java GenBPF
    { OP_JGT, 7, 0, c0a83863},
    { OP_JEQ, 12, 0, c0a83863},
    
    { OP_JGT, 3, 0, c0a83861},
    { OP_JEQ, 10, 0, c0a83861},
    
    { OP_JA, 0, 0, 0},
    { OP_JEQ, 8, 9, c0a83860},
    
    { OP_JA, 0, 0, 0},
    { OP_JEQ, 6, 7, c0a83862},
    
    { OP_JGT, 3, 0, c0a83865},
    { OP_JEQ, 4, 0, c0a83865},
    
    { OP_JA, 0, 0, 0},
    { OP_JEQ, 2, 3, c0a83864},
    
    { OP_JA, 0, 0, 0},
    { OP_JEQ, 0, 1, c0a83866},

将这段输出重定向到一个.h文件中，然后在C代码中include它即可：

[root@localhost bpf]# java GenBPF >./bsearch_prog.h

C文件里如下写法：

...
    static struct sock_filter bpfcode[] = { 
    	{  OP_LDH, 0, 0, 12 },
    	{  OP_JEQ, 0, 16, ETH_P_IP },
    	{  OP_LDW, 0, 0, 26 },
    #include "bsearch_prog.h"
    	{  OP_RET, 0, 0, 0xffff },
    	{  OP_RET, 0, 0, 0 },
    };
    ...

代码只是一个POC，大致就是这个意思。至于eBPF程序如何做，好在eBPF内置很多高效的MAP，各式各样，HASHMAP，LRU，ARRAY，足够用了，让我们可以 ***面向接口编程*** 了。

--------------------

浙江温州皮鞋湿，下雨进水不会胖。

[https_blog.csdn.net_dog250_article_details_107367725]: https://blog.csdn.net/dog250/article/details/107367725