文档章节

ring buffer

t
 time~
发布于 2015/07/05 17:15
字数 1463
阅读 91
收藏 1

行业解决方案、产品招募中!想赚钱就来传!>>>

1. 有关ring buffer的理解

1)  ring buffer位首尾相接的buffer,即类似生活中的圆形跑道;

2)  空闲空间+数据空间=ring buffer大小

3)  ring buffer的读写,类似生活中在圆形跑道上的追赶游戏,领跑者位write,追赶着为read

4)  如果read跑的太快,追上write,追赶者read要停下来,否则游戏结束。即保证没有数据空间时,不再从ring buffer中读取数据;

5)  如果write跑的太快,反过来套圈要超过read,此时领跑者write也要停下来。即保证没有空闲空间时,不再往ring buffer中写入数据;

6) 所以,read和write之间的距离总是介于开区间(0, buffer大小)

2. linux2.6内核,kfifo的理解

假设buffer的大小为size,读指针为in,写指针为out

1) 在计算机中,整型数据加到最大值后溢出会回卷到0,从头开始)

2)buffer的长度必须是2的n次幂

3) buffer空闲空间和数据空间的大小

1> 空闲空间的大小=size-in+out

2> 空闲空间的大小=in-out

2.2 对数据空间大小计算的理解

本设计总能保证in前out前面的,in跑出unsigned int边界溢出后回卷。

因为buffer的大小是2的n次幂,而unsigned int也是2的n次幂(32位机器上,n=32),一般buffer大小不会超过unsigned int大小,即unsigned int被分成m个整块(m>=1)

第1种情况:

out+数据空间=in

空闲空间=size-数据控件=size-(in-out)=size-in+out

第2种情况:(in跑到unsigned int的边界后,溢出了)

out+数据空间=in,这个等式仍然成立。

所以:空闲空间=size-in+out,亦成立

2.3 写操作分析(读操作类似,不再赘述)


2.3.1 基本情况

设落在ring buffer内写指针为__in,读指针为__out,需要写入的空间大小为len, 其中

1. __in = fifo->in % (fifo->size - 1)  (读写指针都是从0开始算起)

2. __out = fifo->out % (fifo->size - 1)

3. __size = fifo->size

4.  len <= 空闲空间大小

2.3.2 写指针没有回卷

这种情况下,需要写两块buffer,做两次拷贝动作,设需要写入的大小为len,第一块空闲空间大小为left1,第二块为left2,需要第一次拷贝的大小为len1,第二次拷贝的大小为len2,len1 + len2 = len:

1. left1 = _size-__in;

2. len1 = min(len, left1) = min(len, _size-__in);

3. left2 = __out;

4. len2 = len - len1

2.3.3 写指针回卷

这种情况下,需要写一块buffer,做一次拷贝动作:

1. left1 = __out - __in <= __size - __in;

2. 而写入长度len <= 空闲空间大小,所以len <= left1 <= __size - __in,所以len1 = len, len1 = min(len, __size - __in)仍然成立

3. left2 = 0;

4. len2 = 0 = len -len1

2.3.4 两种特殊情况一般化

总结以上两种情形,第一块空闲空间大小为left1,第二块为left2,需要第一次拷贝的大小为len1,第二次拷贝的大小为len2,len1 + len2 = len,则通用情况如下:

1. len <= 空闲空间大小

2. len1 = min(len, _size-__in);

3. len2 = len -len1



  1. unsigned int __kfifo_put(struct kfifo *fifo, 

  2.              unsigned char *buffer, unsigned int len) 

  3. { 

  4.     unsigned int l; 


  5.     len = min(len, fifo->size - fifo->in + fifo->out); 


  6.     /* 前提条件写入大小len不超过空闲空间大小 */ 


  7.     smp_mb(); 


  8.     /* 第一块写入空闲空间,大小为min(len, size-in) */ 

  9.     l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); 

  10.     memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); 


  11.     /* 第二块写入空闲空间,大小为len-min(len, size-in) */ 

  12.     memcpy(fifo->buffer, buffer + l, len - l); 


  13.     /* 

  14.      * Ensure that we add the bytes to the kfifo -before- 

  15.      * we update the fifo->in index. 

  16.      */ 


  17.     smp_wmb(); 


  18.     fifo->in += len; 


  19.     return len; 

  20. }


  21. unsigned int __kfifo_get(struct kfifo *fifo, 

  22.              unsigned char *buffer, unsigned int len) 

  23. { 

  24.     unsigned int l; 


  25.     len = min(len, fifo->in - fifo->out); 


  26.     /* 

  27.      * Ensure that we sample the fifo->in index -before- we 

  28.      * start removing bytes from the kfifo. 

  29.      */ 


  30.     smp_rmb(); 


  31.     /* first get the data from fifo->out until the end of the buffer */ 

  32.     l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); 

  33.     memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); 


  34.     /* then get the rest (if any) from the beginning of the buffer */ 

  35.     memcpy(buffer + l, fifo->buffer, len - l); 


  36.     /* 

  37.      * Ensure that we remove the bytes from the kfifo -before- 

  38.      * we update the fifo->out index. 

  39.      */ 


  40.     smp_mb(); 


  41.     fifo->out += len; 


  42.     return len; 

  43. }


buffer大小是2的K次方:size = (size & (size - 1)

将SIZE 调整到最近的2^k:

思想很简单,就是找出当前数的二级制中最大位为1位的位置,然后用1左移位数即可。

比如数据5,它的二进制形式为101,最高位为1的位置是3,然后左移3位,等于1000,即数字8。也就是数字8是5的接近的2的整数次幂。

思想很简单,最主要的任务就是找到最高位为1的位置。这个有专门的AT&T汇编指令bsrl。这个指令是个32位指令,位置范围是0到31。

如果bsrl %eax 5的范围结果是2,所以我们在用它的时候加1即可。当然0是需要考虑的,我们把它的值赋值成-1,这样函数结果的范围就编程1到32。具体实现如下:

static inline int fls(int x)
{
    int r;


    __asm__("bsrl %1,%0\n\t"
            "jnz 1f\n\t"
            "movl $-1,%0\n"
            "1:" : "=r" (r) : "rm" (x));
    return r+1;
}

当然,如果不用汇编也是可以实现的,我们用C语言来实现它。就是不断左移,直到数值为0,记下它左移的次数,既是它最高位为1的位置。

static inline int fls(int x)
{
int position;
int i;
if(0 != x)
{
for (i = (x >> 1), position = 0; i != 0; ++position)
           i >>= 1;
}
else
{
        position = -1;
}
    return position+1;
}

最后把要得到的数字用1左移那么多次数,即可。考虑到0的特殊性,我们把数字都减1,其他都不会受影响,这样0会取值成-1,然后取到的位置为32,1左移32位后还是为0。

实现代码如下:

static inline unsigned int roundup_pow_of_two(unsigned int x)
{
    return 1UL << fls(x - 1);
}

版权




t
粉丝 1
博文 25
码字总数 10258
作品 0
成都
私信 提问
加载中
请先登录后再评论。
用AGG实现高质量图形输出(一)

AGG是一个开源、高效的跨平台2D图形库。AGG的功能与GDI+的功能非常类似,但提供了比GDI+更灵活的编程接口,其产生的图形的质量也非常高 (自称超过GDI+) 使用前AGG的准备工作 下载AGG库,它的...

Waiting4you
2009/08/24
2.6K
0
ntop 2016 路线图

ntop 2016 路线图 2015年是一个充满活力的年份,我们得以完善工具,为社区提供更好的服务。 2016年计划如下: 100 Gbit 正如在2015年我们已经在PF_RING 中为40 Gbit提供了支持,2016年将为100...

RiboseYim
2016/02/08
793
0
Java I/O 模型的演进

原文同步至 什么是同步?什么是异步?阻塞和非阻塞又有什么区别?本文先从 Unix 的 I/O 模型讲起,介绍了5种常见的 I/O 模型。而后再引出 Java 的 I/O 模型的演进过程,并用实例说明如何选择...

waylau
2016/03/01
4.7K
20
java I/O 模型简述

同步与异步&阻塞与非阻塞 五大I/O模型详解 java I/O模型简述 概述 从同步与异步&阻塞与非阻塞的概念,到具体的I/O模型,再到具体的Java语言实现,都是层层递进,本篇就从Java语言来看I/O模型...

haoran_10
2016/07/14
640
5
innodb 5.7.11 版本 所有变量记录

innodbadaptive_flushing 在线可以调整 数据类型 默认值 合法值 Yes boolean on on/off 是否启用innodb根据负载动态刷出脏页的功能。 一般情况下,5.7.5开始,innodb会在实例脏页比例到达inn...

刘伟
2016/04/03
1.3K
1

没有更多内容

加载失败,请刷新页面

加载更多

2020年西安未来五年哪些编程语言更有发展前景

西安作为一线城市,随着5G标准的落地应用,未来五年产业互联网将逐渐落地到广大的传统行业,以辅助传统行业的结构性升级。产业互联网的核心技术包括大数据、云计算、物联网和人工智能等技术,...

osc_4eht81t7
38分钟前
0
0
三网竞对测试仪在多网室分中的应用(移动网络竞对测试)

三网竞对测试仪在多网室分中的应用 现代城市的高楼大厦,栉次鳞比,一片繁华的背后是室分人的焦虑,随着网络的发展室分系统更注重精细化的室内覆盖及优化,系统指标不仅要关注场强覆盖,而且...

osc_k3vwonkw
40分钟前
0
0
B的时代过去了,新的时代已经来临

BAT中的B的时代基本上已经过去了,看起来是败于移动时代,但本质是传统的文字搜索已经到了顶峰,走下坡路了。百度没有抓住移动互联网,也没有抓住视频时代,这里面,其实也包括谷歌,谷歌比百...

osc_mzickfah
41分钟前
0
0
OSP单区域通信(骨干区域)

第一步设置IP地址 R1 undo terminal monitor [Huawei]user-interface console 0 [Huawei-ui-console0]idle-timeout 0 0 [Huawei]sysname R1 [R1]int g0/0/0 [R1-GigabitEthernet0/0/0]ip add......

osc_m6gaz63w
42分钟前
28
0
5G来电奥秘

5G 电话是怎样传播声音的? The number you are trying to reach is turned off ! 电话是怎样传播声音的? 首先,电话有bai一个听筒和一个话筒,话筒内有du一个磁圈可以将人的声波转化zhi为...

osc_kvlhvh2u
43分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部