【笔记】Linux内核中的循环缓冲区

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

 

附:linux2.6内核,kfifo的实现代码


点击(此处)折叠或打开

  1. unsigned int __kfifo_put(struct kfifo *fifo, 
  2.              unsigned char *buffer, unsigned int len) 
  3.     unsigned int l; 
  4.     len = min(len, fifo->size - fifo->in + fifo->out); 
  5.     /* 前提条件写入大小len不超过空闲空间大小 */ 
  6.     smp_mb(); 
  7.     /* 第一块写入空闲空间,大小为min(len, size-in) */ 
  8.     l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); 
  9.     memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); 
  10.     /* 第二块写入空闲空间,大小为len-min(len, size-in) */ 
  11.     memcpy(fifo->buffer, buffer + l, len - l); 
  12.     /* 
  13.      * Ensure that we add the bytes to the kfifo -before- 
  14.      * we update the fifo->in index. 
  15.      */ 
  16.     smp_wmb(); 
  17.     fifo->in += len; 
  18.     return len; 
  19. }
  20. unsigned int __kfifo_get(struct kfifo *fifo, 
  21.              unsigned char *buffer, unsigned int len) 
  22.     unsigned int l; 
  23.     len = min(len, fifo->in - fifo->out); 
  24.     /* 
  25.      * Ensure that we sample the fifo->in index -before- we 
  26.      * start removing bytes from the kfifo. 
  27.      */ 
  28.     smp_rmb(); 
  29.     /* first get the data from fifo->out until the end of the buffer */ 
  30.     l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); 
  31.     memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); 
  32.     /* then get the rest (if any) from the beginning of the buffer */ 
  33.     memcpy(buffer + l, fifo->buffer, len - l); 
  34.     /* 
  35.      * Ensure that we remove the bytes from the kfifo -before- 
  36.      * we update the fifo->out index. 
  37.      */ 
  38.     smp_mb(); 
  39.     fifo->out += len; 
  40.     return len; 
  41. }

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。