kernelchina - 分享学习的乐趣

Challenges in multicore network system programming (5)

droplet — Mon, 09 Nov 2009 17:01:29 +0800

不同的指令集对不同的应用，性能不同。RISC对l2/l3的处理可能更快，但是CISC对L4以上的处理可能更有优势。但是一般在multicore里面，都是相同结构的core，而没有不同结构的core。如果有多种异构的core组成的multi core system，针对不同的应用，用不同的core，是不是能够提高性能哪？不过，可能性能提高了，成本和复杂度也提高了。
应用可以集成，但是硬件如何集成哪？可以把多个blade，组合成一个系统，把blade看成一个处理单元，有做包分类，有做路由的，有做firewall，有做IDP的，可以根据需求来插不同的blade。有个问题就是throughput如何提高，是pipeline哪，还是look-aside。如果是pipeline，瓶颈就是最慢的那个blade，如果是look-aside，可以按需求把包发到相应的blade去处理。
应用对硬件的要求是不同的，按需配置是最好的选择。

Challenges in multicore network system programming (4)

droplet — Fri, 06 Nov 2009 10:47:41 +0800

到了session这一级，有些协议可以并行处理，比如UDP，同一个session的包是独立的，多个线程可以同时处理这个session的包。这对throughput应该有很大帮助。但是对于tcp的session来说，就不一定了。假设一个tcp session上要做URL filter，它就必须先把这个stream上的包先reassemble了，然后才能处理。这就需要serialized的处理。同一时刻，只能有一个线程在处理这个session，否则状态机就出错了。所以，如何写出一个可以并行处理同一个session的engine，也是一个很大的问题。否则，同一个session的throughput是没法提高的，用multicore，顶多就是对多个session的throughput有帮助。
这里面有个sequence check的问题，同一个session的sequence check能否并行进行？我想应该是可以的，因为同一个窗口的包，它的window size应该是一样的，用window size去检查sequence，即使是out of order的检查，也不会出错。在前面的包没有到达host之前，window size和ack sequence也不会更新，看起来是没什么问题。

Link-local address的作用

帅云霓 — Thu, 05 Nov 2009 22:14:05 +0800

学习IPV6的时候涉及到一个概念，link-local address, 中文叫“链路本地地址”，它的前缀是
FE80::/64
一个link-local address的范例：
FE80::713e:a426:d167:37ab

实际上，这个概念类似于ipv4中，当DHCP分配失败时自动生成的169.254.XXX.XXX这样的地址，凡是源地址或目的地址中含有link-local address的报文，路由器都不应当转发它。这样的报文只能在一个LAN中互通。

Challenges in multicore network system programming (3)

droplet — Thu, 05 Nov 2009 16:38:05 +0800

在multi core里面，最好做到task decouple, data decouple，任务之间没有关系，数据之间没有关系。没有share的数据结构。但是做到这一点，就意味着CPU power不是share的，CPU和memory的利用率没法提高。所以，spinlock还是必须的。但是，如果有很多线程都去抓一个lock，锁的性能就有很高的要求。对不同的应用场景，使用不同的spinlock，这就增加的编程的难度。所以，最好是share一个lock的线程数目少一点，把任务变短，然后用queue连接起来，做成pipe line，这应该是一个比较好的选择。
spinlock最多能够支持多少个线程哪？在将来core的数目增加的情况下，lock还适用吗？值得考虑。

Challenges in multicore network system programming (2)

droplet — Thu, 05 Nov 2009 16:31:18 +0800

一个很重要的问题是，如何做packet reorder？在单CPU的情况下，包发出的顺序和包接收到的顺序是一样的(中间没有drop和queue等）。但是在多CPU的情况下，由于有多个线程去收包和处理，一个stream上的包的顺序，在发出时就有可能和收到时不一样了。引入乱序，对application的性能有影响。所以，最好是在整条路径上没有乱序。能够用硬件做reorder最好了，如果用软件做，怎么做？
首先要在收到包时，能够给包打上序号。所以这个收包的线程不能多线程。否则，包上的序号是无效的。在发包时，要检查这个序号，把包按顺序发出去。如果序号不是in order的，还需要缓存这个包，等待in order了再把包发出去。
一个分配序号的线程，一个消耗序号的线程，消耗序号的线程按序号的顺序发包。如果其中某个序号的包被丢掉，或者queue了，需要通知这个线程把相应的序号释放掉。
乱序是个很严重的问题，在multicast的应用里面，尤其重要。

这里有一个网上找到资料，可以了解一下。
A Hardware Packet Re-Sequencer Unit for Network Processors

Challenges in multicore network system programming (1)

droplet — Tue, 03 Nov 2009 14:06:33 +0800

在Multicore network system里面，首先遇到的一个问题就是每个core的任务如何划分？如果每个core或者thread执行的是一个while-loop，那么它如何去poll网络包？core与core直接如何通信？用中断驱动已经证明是不行的，这也是为什么linux引入NAPI的原因。那么，是不是每个core轮询每个interface哪？还是把interface收到的包，都放到一个queue里面去，然后，core去poll这个queue。这就需要一个线程或者core去把包从interface里面poll出来。如图：

  interface 1 -----+
                   |                      +---Thread
  interface 2 -----+----Thread----Queue---+
                   |                      +---Thread
  interface 3 -----+

如果每个thread有自己的queue，那么谁来保证包能够平均的分配给每个线程？如果这个包在系统里面处理的时间是一样的，那么可以round-robin，如果是不一样的，有没有可能某些线程比较忙，而其他线程比较闲哪？

Design Patterns
for Packet
Processing
Applications on
Multi-core Intel®
Architecture
Processors

知识管理，博客，论坛，邮件列表

droplet — Thu, 29 Oct 2009 18:27:45 +0800

可以看看这个公司的产品
http://www.jivesoftware.com/
集合了一些很好的东西。对于提高工作效率很有帮助。如果能做个中文版，或者适合中国人用的东西，应该很有前途。
其实sourceforge.net里面整合的一些开源软件也不错，但是缺乏一个整体的设计，而且也没有中文版。
Google占领了英文搜索市场，但是并不影响Baidu的成长。中国的市场足以支持一些有规模的公司。这也就是为什么海归能够在中国创业成功了。拿了国外的好点子，来做中国的本地化产品。这条路依然适用。

An ip hash function for better performance

droplet — Thu, 29 Oct 2009 18:20:05 +0800

HASH_SHIFT的定义要根据hash_size的大小来定义，最大是16。ports是source port左移16位然后或destination port。srcip,dstip是network byte order。在做hash时，把source ip做bit reverse，这样的destination的bit order是不一样的。正好把网络部分和主机部分调换，这样可以得到更好的hash distribution.
==========================================================
unsigned int hash_size = 0x10000;
#define HASH_SHIFT 16

static inline unsigned int
reverse(unsigned int x) {
unsigned int h = 0;
int i = 0;

for(h = i = 0; i = 1;
}

return h;
}

int ip_hash(unsigned int srcip, unsigned int dstip,
unsigned int ports, unsigned int hash_mask)
{
unsigned hash;

hash = (reverse(srcip) ^ dstip ^ ports);
hash = ((hash>>HASH_SHIFT) ^ hash);

return (hash & hash_mask);
}

Multi thread/Multi core program performance evaluation

droplet — Tue, 27 Oct 2009 18:10:54 +0800

Multi thread/Multi core program performance如何评估？从静态分析的角度来说，首先应该确定每个execution path上spin lock的个数，可以确定的是，lock的数量越多，性能就越低。在parallel programming 里面，很重要的工作就是decouple 数据之间的相关性。一般来说，如果数据完全无关，那么就不需要锁；反之，则需要锁来保护。
锁的性能暂不考虑，因为那是首先要保证的。
再者，需要考虑cache miss的几率。如果整个execution path能够放在cache里面执行，毫无疑问，这样性能会最好。但是如果execution path太长，cache miss的几率就会很高。如果系统里面的任务种类很多的话，不同任务之间切换，也会导致cache flush，性能也不会高。所以在任务长短，或任务类型之间，需要一个平衡。
把长任务划分成短任务，然后用pipeline链接，每个execution path分配几个线程去执行。这样也可以提高cache hit ratio。总之，cache在multi thread/multi core里面也很重要。
Profile工具对multi thread分析并不一定有很大的帮助，特别是对那些有锁的函数。当然，前期用profile工具来分析应该还是有好处的，毕竟一个函数执行的指令个数，用profile工具可以衡量。
还有其他需要关注的地方吗？

ip hash performance evaluation

droplet — Tue, 27 Oct 2009 14:46:56 +0800

网络里面五元组(proto,saddr,daddr,sport,dport} hash的性能如何评估，test sample如何选？如果选取[0,255],[0,4294967295],[0,65535]的range来测试，好像不太现实，样本空间太大了，普通的机器没法跑。而且hash entry的分配，释放是个动态的过程。用静态的样本，很难估计在某一段时间内的hash performance。
hash performance包括哪些方便，比如给定一个样本，用hash function计算，至少hash value的分布应该是很离散的，而且某个hash link list 不能太长（假设用link list来解决hash冲突的问题）。hash lengt的平均长度是样本空间里面项的总数，除以hash table size
avg hash length = sample size/hash size
如果样本空间在hash空间是平均分布的，它的性能是不是就是最好？这个如何评价哪？hash冲突链的长度是平均长度好哪，还是随机长度好呢？这就还是前面那个问题，hash entry是动态的，用静态的样本是很难测量的。我们只能说，在某个时间范围内，比如说30分钟（假设hash entry的timeout是30分钟），用这个样本测试hash performance，有比较的价值。
怎样才能得到一个好的hash function？至少最后的hash value，考虑到了五元组的每一个bit，这样的结果才能最优，因为如果不是每个bit都考虑到，那么样本变化时，冲突的几率就会很大。这也就是为什么hash value最后要left shift或者right shift来计算最后的结果。
计算ip hash，还需要考虑字节序的问题，网络序和主机序是有区别的，在设计hash function时，需要考虑。