xiaoxiaoling

C++博客 首页 新随笔 联系 聚合 管理
  13 Posts :: 2 Stories :: 9 Comments :: 0 Trackbacks

2017年2月5日 #


dpdk是通过许多不同的纬度来加速包处理的,其中主要包括:

 

hugepage大页内存(进程使用的是虚拟地址,一般页表(4k)能映射的虚拟地址空间有限,使用大页能减少换页次数提高cache命中,通过mmap把大页映射到用户态的虚拟地址空间有用过mmap的都知道这是实现共享内存的手段,所以dpdk还支持多进程共享内存)

 

cache预取 (每次预读当前数据相邻前后的数据),批量操作数据,cache line对齐(通过浪费一点内存将要操作的数据对齐)

 

接管了网卡用户态驱动使用轮询而不是网卡中断

 

将网卡rx tx队列映射到用户态空间实现真正的零拷贝(传统堆栈至少也得一次拷贝,因为队列空间在内核而内核和用户态使用不同的地址空间)(传统堆栈为了支持通用性,例如ipx等其他网络,将包处理过程分了很多层次,层之间的接口标准统一数据结构就需要转换,无形中带来了巨大的成本,如osi七层模型而实用的就是tcp/ip四层模型)

 

线程绑定cpu

 

支持NUMA,不同的core属于不同的node,每个node有自己的mempool减少冲突

 

无锁环形队列(冲突发生时也是一次cas的开销)

 

dpdk通过tools/dpdk-setup.sh的脚本,通过编译、挂载内核模块, 绑定网卡(先把网卡ifconfig down),设置hugepage后就可以使用了。

 

 

在内核模块igb加载时,会注册pci设备驱动

static struct pci_driver igbuio_pci_driver = {

.name = "igb_uio",

.id_table = NULL,

.probe = igbuio_pci_probe,

.remove = igbuio_pci_remove,

};

 

在绑定网卡时,会调用igbuio_pci_probe,使用用户态驱动uio接管网卡(中断处理、mmap映射设备内存到用户空间)

系统启动时,bios会将设备总线地址信息记录在/sys/bus/pci/devices,dpdk程序启动时会去这里扫描pci设备,根据不同类型的NIC有对应的初始化流程。在后面配置队列的时候会把用户态的队列内存地址通过硬件指令交给NIC,从而实现零拷贝。


 

如果NIC收到包,会做标记,轮询的时候通过标记取数据包

while (nb_rx < nb_pkts) {

/*

 * The order of operations here is important as the DD status

 * bit must not be read after any other descriptor fields.

 * rx_ring and rxdp are pointing to volatile data so the order

 * of accesses cannot be reordered by the compiler. If they were

 * not volatile, they could be reordered which could lead to

 * using invalid descriptor fields when read from rxd.

 */

rxdp = &rx_ring[rx_id];

staterr = rxdp->wb.upper.status_error;

if (! (staterr & rte_cpu_to_le_32(E1000_RXD_STAT_DD)))

break;

rxd = *rxdp;

发包的轮询就是轮询发包结束的硬件标志位,硬件发包完成会写回标志位,驱动发现后再释放对应的描述符和缓冲块。

 

KNI

通过创建一个虚拟网卡,将收到的包丢给协议栈

 /* 发送skb到协议栈 */

            /* Call netif interface */

            netif_receive_skb(skb);

 

POWER

在负载小的时候没有必要使用轮询模式,这时可以打开网卡中断 使用eventfd  epoll通知用户层

 

Ring

无锁环形队列的核心就是操作头尾索引,先将头尾索引赋给临时变量,再把尾索引往后跳n个位置,利用cas判断头如果还是在原来的位置就指向尾否则就重复这个过程,然后在操作中间跳过的n个元素就是安全的了,此时头尾索引应该指向同一个位置,如果不同应该是有别的线程也在操作,重复等待即可。(这里有个细节,索引是只加不减的,因为是环形队列索引又是unsigned 32bits,所以每次取数据前把索引模队列长度-1, uint32_t mask;           /**< Mask (size-1) of ring. */即可)

 

Windows下使用vmware虚拟机的时候出现EAL: Error reading from file descriptor,根据网上的说法打了patch还是不行,后来尝试挂载内核模块的时候不加载vfio模块就可以了

 

posted @ 2017-02-05 14:08 clcl 阅读(61) | 评论 (0)编辑 收藏

2017年1月24日 #

Redis是工作中很常用的,这里将比较普遍使用的结构研究了下做个备忘。

 

hash

实现和dnspod的dataset半斤八两,本质上是个二维数组,通过将key哈希作为一维的下表,第二维的数组存相同哈希的元素,查找使用遍历的方式,所以这里redis做了优化,当满足条件的时候(数组数量太大)会进行rehash,动态扩大桶的数量来减少最后一维遍历的次数.

函数名称

作用

复杂度

dictCreate

创建一个新字典

O(1)

dictResize

重新规划字典的大小

O(1)

dictExpand

扩展字典

O(1)

dictRehash

对字典进行N步渐进式Rehash

O(N)

_dictRehashStep

对字典进行1步尝试Rehash

O(N)

dictAdd

添加一个元素

O(1)

dictReplace

替换给定key的value值

O(1)

dictDelete

删除一个元素

O(N)

dictRelease

释放字典

O(1)

dictFind

查找一个元素

O(N)

dictFetchValue

通过key查找value

O(N)

dictGetRandomKey

随机返回字典中一个元素

O(1)

 

字典结构

typedef struct dict {

    // 类型特定函数

    dictType *type;

    // 私有数据

    void *privdata;

    // 哈希表

    dictht ht[2];

    // rehash 索引

    // 当 rehash 不在进行时,值为 -1

    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量

    int iterators; /* number of iterators currently running */

} dict;

这里哈希表有两个,一般都用ht[0],当需要rehash的时候会创建一个比ht[0]大的 2 的 N 次方的ht[1],然后渐进式的将数据dictEntry移过去(除了定时的rehash,在每次操作哈希表时都会_dictRehashStep),完成后将ht[1]替换ht[0]

 

zset

zset本质就是list,只不过每个元素都有若干个指向后继span长的指针,这样简单的设计大大提高了效率,使得可以比拟平衡二叉树,查找、删除、插入等操作都可以在对数期望时间内完成,对比平衡树,跳跃表的实现要简单直观很多。

 

 

/* ZSETs use a specialized version of Skiplists */

/*

 * 跳跃表节点

 */

typedef struct zskiplistNode {

    // 成员对象

    robj *obj;

    // 分值

    double score;

    // 后退指针

    struct zskiplistNode *backward;

    // 层

    struct zskiplistLevel {

        // 前进指针

        struct zskiplistNode *forward;

        // 跨度

        unsigned int span;

    } level[];

} zskiplistNode;

 

/*

 * 跳跃表

 */

typedef struct zskiplist {

    // 表头节点和表尾节点

    struct zskiplistNode *header, *tail;

    // 表中节点的数量

    unsigned long length;

    // 表中层数最大的节点的层数

    int level;

} zskiplist;

 

/*

 * 有序集合

 */

typedef struct zset {

 

    // 字典,键为成员,值为分值

    // 用于支持 O(1) 复杂度的按成员取分值操作

    dict *dict;

    // 跳跃表,按分值排序成员

    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作

    // 以及范围操作

    zskiplist *zsl;

 

} zset;

 

虽然这种方式排序查找很快,但是修改的话就得多做些工作了

 

/* Delete an element with matching score/object from the skiplist.

 *

 * 从跳跃表 zsl 中删除包含给定节点 score 并且带有指定对象 obj 的节点。

 *

 * T_wrost = O(N^2), T_avg = O(N log N)

 */

int zslDelete(zskiplist *zsl, double score, robj *obj)

 

intset

typedef struct intset {  

uint32_t encoding; //所使用类型的长度,4\8\16  

uint32_t length; //元素个数  

int8_t contents[]; //保存元素的数组  

} intset;  

 

intset其实就是数组,有序、无重复地保存多个整数值,查找用的是二分查找 * T = O(log N),添加的话在找到对应的数组中应该存在的位子后使用memmove向后移出空位填补(当然需要先realloc预分配空间),同理删除也是用memmove向前移动

 

set

当使用整数时,使用intset,否则使用哈希表

 

 

其他的关于网络事件处理,epoll,回调,拆包都和正常使用差不多,关于错误处理EINTR(系统调用期间发生中断)和EAGAIN 继续重试而如果是EPOLLHUP或EPOLLERR则让io该读读该写写,有错处理就是了。

 

 

posted @ 2017-01-24 18:13 clcl 阅读(21) | 评论 (0)编辑 收藏

2017年1月23日 #

 

 

dns的递归解析过程还是挺繁琐的,要知道一个域名可能有cname、ns 而请求的cname、ns可能还有cname、ns,如果按照线性的处理每个请求那逻辑就变成毛线团了

dnspod的处理还是挺巧妙的,通过一个公共的数据集dataset将所有域名对应的a、cname、ns等类型的数据作为单独的条目存入,当有需要某个域名的信息时先去dataset找,找不到在加入qlist请求根,有专门的线程不间断的将qlist轮询dataset找(这里只要次数允许,没得到想要的结果就轮询所有qlist到dataset找虽然可以简化逻辑分离的彻底但是会是个性能瓶颈,后面有方案)当根返回以后只是简单的将记录(通常是一个域名的cname、ns或者a)存入dataset(而不是继续流程,因为根据这个返回是cname还是ns或者a处理不同逻辑复杂,而这样处理对于用到相同域名的请求还有优化作用),剩下的工作交给那边不间断轮询的线程

 

Dnspod主要由3个run(若干个线程)组成

 

run_sentinel  监听53端口接收客户端请求,将请求放到队列中

run_fetcher   从队列中取出请求,根据qname取得最后一级cname,查看本地dataset 是否有记录,如果有则返回,没有则将该请求放入qlist中

 

run_quizzer    

1.不间断的遍历qlist,只要状态为PROCESS_QUERYdataset中没有的就向对应的根发送请求。

2.通过epoll等待根返回,解析返回的数据加入 dataset

3.检查记录的ttl,在将记录加入dataset时还会将这些记录以红黑树的形式组织起来,取得ttl最早到期的,将其放入qlist中等待刷新,注意这里不是删除,如果收不到不返回则该记录一直存在

 

关于dataset的实现

dataset是使用哈希表实现的,本质上是个二维数组,将域名哈希成一个值,模上数组的数量作为下标,找到对应的数组接着遍历查找,根据需要可以扩大数组的数量提升性能。

 

我们的优化手段

之前提到dnspod的qlist会不间断轮询,属于主动查询,对性能有不小的影响,这里我们采取的做法是被动(类似回调的方式),我们将请求的域名和类型分类,相同的放在一组,当dataset找不到向根发出请求后我们并不每次主动轮询,而是在等到应答后,触发该域名和类型的请求组,让他们根据自己的逻辑走下一步(一般是先找该域名的最后一级cname,根据这个cname查是否存在他的对应请求类型的记录,一般是a或者ns,如果没有,则找这个cname的ns)

 

以上可以看出dataset很重要,负载也不小,还经常需要并发访问,这里我们每次接收到根的回复后,除了将记录的答案加进dataset,还创建一个临时的dataset,只存该次回复的信息,在后面的流程会优先到这里去找,没有的再找dataset。

posted @ 2017-01-23 15:14 clcl 阅读(13) | 评论 (0)编辑 收藏

2017年1月22日 #

     摘要: 最近在研究DPDK,这是sigcomm 2014的论文,纪录在此备忘Ps:  文中关键词的概念:segment : 对应于tcp的PDU(协议传输单元),这里应该指tcp层的包,如果一个包太大tcp负责将它拆分成多个segment(这个概念对理解后文有帮助)根据unix网络编程卷1 第8页注解2:packet是IP层传递给链路层并且由链路层打包好封装在帧中的数据(不包括帧头)而IP层的包...  阅读全文
posted @ 2017-01-22 18:01 clcl 阅读(50) | 评论 (0)编辑 收藏

2010年4月27日 #

一直想用cegui,但是没机会用,只是抽空看其代码

最近听朋友说0.7 debug下帧数提高100多,挺惊讶的,重新到久违了的官网上下了0.7.1

看了下渲染的实现(GL)

首先,添加了GeometryBuffer玩意,使得每个window保存了属于自己的顶点和纹理信息

然后在RenderingSurface中有GeometryBuffer队列,使得每个拥有AutoRenderingSurface属性的window有属于自己的队列(默认只有FrameWindow才有)

而在drawself中执行的则是先通过looknfeel,把需要渲染的信息丢到每个部件自己的GeometryBuffer里,然后把GeometryBuffer丢到RenderingSurface的队列中(一般为

FrameWindow的GeometryBuffer队列,每个面板就有自己的渲染队列了)

要知道以往都是只有一个队列的,要渲染啥直接往里塞。 。 。
这样一改就不必每个小部件有更改都要全部重新清空渲染了


再往后就是把每个窗口队列里的GeometryBuffer渲染到各自的RenderingSurface表面上,这里要注意的是并不是渲染到屏幕上而是表面上,cegui在这里使用了渲染到纹理,GL

用的是fbo实现的。

注意RenderingSurface只有两个来源,一是通过设置AutoRenderingSurface属性,另一个就是RenderingRoot了,RenderingRoot只有一个,在render中,通过第一个来源的使

用的是fbo的渲染,而第二个来源则直接渲染到屏幕了。

所有的这些执行完后就可以渲染到屏幕了,通过RenderingRoot执行,注意这里的RenderingRoot中的RenderTarget和之前的不一样,这里用的是OpenGLViewportTarget而不是

OpenGLFBOTextureTarget。

posted @ 2010-04-27 20:56 clcl 阅读(888) | 评论 (2)编辑 收藏

2009年10月25日 #

     摘要: 这个看代码里面batch相关的。[Direct3D] 实现批次渲染、硬件 T&L 的渲染器和 D3DPipeline 在是否从 D3DRender 提供顶点缓存区操作给流水线时做了一些权衡,最后决定暂时使用 IDirect3DDevice9::DrawPrimitiveUP 来渲染,因为它更容易书写,而且开销是一次顶点拷贝,流水线也不用操心对缓存的使用。 (DrawPrimitive的...  阅读全文
posted @ 2009-10-25 17:15 clcl 阅读(871) | 评论 (0)编辑 收藏

2008年12月11日 #

1)打开资源文件,把LANGUAGE LANG_ENGLISH, SUBLANG_ENGLISH_US修改为
LANGUAGE LANG_CHINESE, SUBLANG_CHINESE_SIMPLIFIED
2)关闭资源文件
3)打开对话框,输入汉字,并保存
4)右击资源文件属性,选择Resources->General->Culture,设置为:中文(中国) (0x804)
5)编译,测试
posted @ 2008-12-11 17:53 clcl 阅读(279) | 评论 (0)编辑 收藏

2008年11月11日 #

前言  
  看到有些人对位运算还存在问题,于是决定写这篇文章作个简要说明。  
   
  什么是位(bit)?  
   
  很简单,位(bit)就是单个的0或1,位是我们在计算机上所作一切的基础。计算机上的所有数据都是用位来存储的。一个字节(BYTE)由八个位组成,一个字(WORD)是二个字节或十六位,一个双字(DWORD)是二个字(WORDS)或三十二位。如下所示:  
   
      0   1   0   0   0   1   1   1   1   0   0   0   0   1   1   1   0   1   1   1   0   1   0   0   0   1   1   1   1   0   0   0  
  |   |                             |                               |                               |                             |   |  
  |   +-   bit   31             |                               |                               |               bit   0   -+   |  
  |                                 |                               |                               |                                 |  
  +--   BYTE   3   ----   -+----   BYTE   2   ---+----   BYTE   1   ---+---   BYTE   0   -----+  
  |                                                                 |                                                                 |  
  +------------   WORD   1   ------------+-----------   WORD   0   -------------+  
  |                                                                                                                                   |  
  +-----------------------------   DWORD   -----------------------------+  
   
  使用位运算的好处是可以将BYTE,   WORD   或   DWORD   作为小数组或结构使用。通过位运算可以检查位的值或赋值,也可以对整组的位进行运算。  
   
  16进制数及其与位的关系  
  用0或1表示的数值就是二进制数,很难理解。因此用到16进制数。  
   
  16进制数用4个位表示0   -   15的值,4个位组成一个16进制数。也把4位成为半字节(nibble)。一个BYTE有二个nibble,因此可以用二个16进制数表示一个BYTE。如下所示:  
   
  NIBBLE       HEX   VALUE  
  ======       =========  
    0000                 0  
    0001                 1  
    0010                 2  
    0011                 3  
    0100                 4  
    0101                 5  
    0110                 6  
    0111                 7  
    1000                 8  
    1001                 9  
    1010                 A  
    1011                 B  
    1100                 C  
    1101                 D  
    1110                 E  
    1111                 F  
   
  如果用一个字节存放字母"r"(ASCII码114),结果是:  
  0111   0010         二进制  
      7         2           16进制  
   
  可以表达为:'0x72'  
   
  有6种位运算:  
        &       与运算  
        |       或运算  
        ^       异或运算  
        ~       非运算(求补)  
      >>       右移运算  
      <<       左移运算  
   
  与运算(&)  
  双目运算。二个位都置位(等于1)时,结果等于1,其它的结果都等于0。  
        1       &       1       ==       1  
        1       &       0       ==       0  
        0       &       1       ==       0  
        0       &       0       ==       0  
   
  与运算的一个用途是检查指定位是否置位(等于1)。例如一个BYTE里有标识位,要检查第4位是否置位,代码如下:  
   
  BYTE   b   =   50;  
  if   (   b   &   0x10   )  
          cout   <<   "Bit   four   is   set"   <<   endl;  
  else  
          cout   <<   "Bit   four   is   clear"   <<   endl;  
   
  上述代码可表示为:  
   
          00110010     -   b  
      &   00010000     -   &   0x10  
    ----------------------------  
          00010000     -   result  
   
  可以看到第4位是置位了。  
   
  或运算(   |   )  
  双目运算。二个位只要有一个位置位,结果就等于1。二个位都为0时,结果为0。  
        1       |       1       ==       1  
        1       |       0       ==       1  
        0       |       1       ==       1  
        0       |       0       ==       0  
   
  与运算也可以用来检查置位。例如要检查某个值的第3位是否置位:  
   
  BYTE   b   =   50;  
  BYTE   c   =   b   |   0x04;  
  cout   <<   "c   =   "   <<   c   <<   endl;  
   
  可表达为:  
   
          00110010     -   b  
      |   00000100     -   |   0x04  
      ----------  
          00110110     -   result  
   
  异或运算(^)  
  双目运算。二个位不相等时,结果为1,否则为0。  
   
        1       ^       1       ==       0  
        1       ^       0       ==       1  
        0       ^       1       ==       1  
        0       ^       0       ==       0  
   
  异或运算可用于位值翻转。例如将第3位与第4位的值翻转:  
   
  BYTE   b   =   50;  
  cout   <<   "b   =   "   <<   b   <<   endl;  
  b   =   b   ^   0x18;  
  cout   <<   "b   =   "   <<   b   <<   endl;  
  b   =   b   ^   0x18;  
  cout   <<   "b   =   "   <<   b   <<   endl;  
   
  可表达为:  
   
          00110010     -   b  
      ^   00011000     -   ^0x18  
      ----------  
          00101010     -   result  
   
          00101010     -   b  
      ^   00011000     -   ^0x18  
      ----------  
          00110010     -   result  
   
  非运算(~)  
  单目运算。位值取反,置0为1,或置1为0。非运算的用途是将指定位清0,其余位置1。非运算与数值大小无关。例如将第1位和第2位清0,其余位置1:  
   
  BYTE   b   =   ~0x03;  
  cout   <<   "b   =   "   <<   b   <<   endl;  
  WORD   w   =   ~0x03;  
  cout   <<   "w   =   "   <<   w   <<   endl;  
   
  可表达为:  
   
          00000011     -   0x03  
          11111100     -   ~0x03     b  
   
          0000000000000011     -   0x03  
          1111111111111100     -   ~0x03     w  
   
  非运算和与运算结合,可以确保将指定为清0。如将第4位清0:  
   
  BYTE   b   =   50;  
  cout   <<   "b   =   "   <<   b   <<   endl;  
  BYTE   c   =   b   &   ~0x10;  
  cout   <<   "c   =   "   <<   c   <<   endl;  
   
  可表达为:  
   
          00110010     -   b  
      &   11101111     -   ~0x10  
      ----------  
          00100010     -   result  
   
  移位运算(>>   与   <<)  
  将位值向一个方向移动指定的位数。右移   >>   算子从高位向低位移动,左移   <<   算子从低位向高位移动。往往用位移来对齐位的排列(如MAKEWPARAM,   HIWORD,   LOWORD   宏的功能)。  
   
  BYTE   b   =   12;  
  cout   <<   "b   =   "   <<   b   <<   endl;  
  BYTE   c   =   b   <<   2;  
  cout   <<   "c   =   "   <<   c   <<   endl;  
  c   =   b   >>   2;  
  cout   <<   "c   =   "   <<   c   <<   endl;  
   
  可表达为:  
          00001100     -   b  
          00110000     -   b   <<   2  
          00000011     -   b   >>   2  
   
  译注:以上示例都对,但举例用法未必恰当。请阅文末链接的文章,解释得较为清楚。  
   
  位域(Bit   Field)  
  位操作中的一件有意义的事是位域。利用位域可以用BYTE,   WORD或DWORD来创建最小化的数据结构。例如要保存日期数据,并尽可能减少内存占用,就可以声明这样的结构:  
   
  struct   date_struct   {  
          BYTE       day       :   5,       //   1   to   31  
                        month   :   4,       //   1   to   12  
                        year     :   14;     //   0   to   9999  
          }date;  
           
  在结构中,日期数据占用最低5位,月份占用4位,年占用14位。这样整个日期数据只需占用23位,即3个字节。忽略第24位。如果用整数来表达各个域,整个结构要占用12个字节。  
   
  |   0   0   0   0   0   0   0   0   |   0   0   0   0   0   0   0   0   |   0   0   0   0   0   0   0   0   |  
        |                                                           |                   |                     |  
        +-------------   year   --------------+   month+--   day   --+  
   
  现在分别看看在这个结构声明中发生了什么  
   
  首先看一下位域结构使用的数据类型。这里用的是BYTE。1个BYTE有8个位,编译器将分配1个BYTE的内存。如果结构内的数据超过8位,编译器就再分配1个BYTE,直到满足数据要求。如果用WORD或DWORD作结构的数据类型,编译器就分配一个完整的32位内存给结构。  
   
  其次看一下域声明。变量(day,   month,   year)名跟随一个冒号,冒号后是变量占用的位数。位域之间用逗号分隔,用分号结束。  
   
  使用了位域结构,就可以方便地象处理普通结构数据那样处理成员数据。尽管我们无法得到位域的地址,却可以使用结构地址。例如:  
  date.day   =   12;  
  dateptr   =   &date;  
  dateptr->year   =   1852;
posted @ 2008-11-11 22:21 clcl 阅读(120) | 评论 (0)编辑 收藏

CButtonT           CButton           CTrackBarCtrlT         CTrackBarCtrl
CListBoxT          CListBox          CUpDownCtrlT           CUpDownCtrl
CComboBoxT         CComboBox         CProgressBarCtrlT      CProgressBarCtrl
CEditT             CEdit             CHotKeyCtrlT           CHotKeyCtrl
CScrollBarT        CScrollBar        CAnimateCtrlT          CAnimateCtrl
CToolTipCtrlT CToolTipCtrl      CRichEditCtrlT         CRichEditCtrl
CHeaderCtrlT       CHeaderCtrl       CReBarCtrlT            CReBarCtrl
CListViewCtrlT     CListViewCtrl     CMonthCalendarCtrlT    CMonthCalendarCtrl
CTreeViewCtrlT     CTreeViewCtrl     CDateTimePickerCtrlT  CDateTimePickerCtrl
CToolBarCtrlT CToolBarCtrl      CIPAddressCtrlT        CIPAddressCtrl
CStatusBarCtrlT    CStatusBarCtrl    CPagerCtrlT            CPagerCtrl
CTabCtrlT          CTabCtrl
posted @ 2008-11-11 17:02 clcl 阅读(974) | 评论 (0)编辑 收藏

2008年10月14日 #

   char file[MAX_PATH];
   TCHAR Tchartmp[MAX_PATH];

sprintf_s(file, "fileName%d", 134);

   CString strUnicode = file;

   wcscpy(Tchartmp,strUnicode);
posted @ 2008-10-14 15:00 clcl 阅读(703) | 评论 (1)编辑 收藏

仅列出标题  下一页