kfifo的移植
两个月前，我花了两天时间，查找Linux内核里kfifo的相关资料，将其从内核层移植到应用层，并成功应用于多线程CAN总线采集程序（一个线程接收/一个线程输出）。kfifo.c是从Linux 5.3 stable内核代码里复制出来的，路径是lib/kfifo，对应的kfifo.h路径是include/linux/kfifo.h。由于kfifo是内核里的代码，应用层无法直接使用，我做了如下修改：


注释掉无关的或不必要的代码，如对内核头文件的引用，如涉及dma、sgl的代码


重新实现某些功能，如采用SO上的代码取代了roundup_pow_of_two，用GCC内置函数__sync_synchronize取代了smp_wmb，重新定义了ARRAY_SIZE


代码仓库：https://github.com/liigo/kfifo
kfifo的使用
很简单就三点：用 DEFINE_KFIFO 定义缓冲区变量并初始化，用 kfifo_in 向缓冲区内写入数据，用 kfifo_out 从缓冲区取出数据。DEFINE_KFIFO宏参数1是一个变量名（调用者只给一个名称，宏内部负责定义类型和变量），参数2是自定义结构体（也可以是任意其他类型），参数3是缓冲区长度（必须是2的幂，单位是参数2的类型尺寸）。
DEFINE_KFIFO(g_canbuf, buf_item_t, 1024);
kfifo_in(&g_canbuf, &bufitem, 1);
int n = kfifo_out(&g_canbuf, &bufitem, 1);

kfifo代码里大量使用宏，理解起来很费劲，主要因为宏参数的类型不明确。
kfifo的设计和实现
关于Linux内核kfifo的设计和实现的精妙之处，推荐大家阅读如下文章：

博主chen19870707的《眉目传情之匠心独运的kfifo》
博主张小小飞的《Linux kfifo 源码分析》
博主海枫的《巧夺天工的kfifo(修订版）》

需要特别说明的是，以上第三方分析文章所基于的kfifo内核版本都相对陈旧，而本文所采用的代码所属内核版本是当前最新的5.3。

        前段时间有个项目要实现一个基于live555的rtspserver，部分功能要用到环形缓冲区，网上看了一些blog，大部分是实验性质的，不太敢用，原理比较简单，所以就自己写了一个；
        实现环形缓冲区的关键点：
        1. 一个线程读，一个线程写
        2. 读线程维护读指针，写线程维护写指针
        3. 数据一致性
        3.1 写线程写数据时，要先确定读指针；读线程读数据时，要先确定写指针；
        这里写的可能比较拗口，其实就是 写线程写数据时，需要多次用使用读指针，比如说计算ringbuf可用空间，是否达到ringbuf末尾等等；由于读指针是在读线程里实时更新的，所以写线程写数据函数多次使用读指针时，读指针的值会不一样；解决这个问题只需要在 读/写 函数 开始处 定义一个临时变量，保存 读/写 指针的值，后续计算都使用该临时变量就OK了；
        3.2 这里多说几句废话
        ringbuf实现类中可能不仅会开放 ReadData/WriteData接口，还会有类似GetRingbufDataLen的函数，这类函数内部肯定要使用读写指针，这个时候就要注意，如果ReadData/WriteData函数调用这类函数，要保证它们和ReadData/WriteData 使用的读写指针的值是一致的。
说完废话贴代码：

//left 1Byte for guard
int RingBuffer::GetFreeBufferBytes(int iRidx, int iWidx)
{
	if (iRidx == iWidx)
	{
		return m_uBufferSize-1;
	}
	else if (iWidx > iRidx)
	{
		return (iRidx - iWidx + m_uBufferSize - 1);
	}
	else
	{
		return (iRidx - iWidx - 1);
	}
}

//this func can  write to the addr = ridx-1 (at most)
int RingBuffer::Write(const unsigned char* pBuf, unsigned writeLen)
{
	//m_pBuffer may alloc memory failed
	if (!m_pBuffer)
	{
		return -1;
	}

	int iRidx = m_iRIdx;
	int iWidx = m_iWidx;
	if (!pBuf || 0 == writeLen || GetFreeBufferBytes(iRidx, iWidx) < writeLen)
	{
		return -1;
	}

	int len1 = 0;
	if (m_iWidx < iRidx)
	{
		memcpy(&m_pBuffer[m_iWidx], pBuf, writeLen);
		m_iWidx += writeLen;
	}
	else
	{
		len1 = m_uBufferSize - m_iWidx;
		if (writeLen <= len1)
		{
			memcpy(&m_pBuffer[m_iWidx], pBuf, writeLen);
			m_iWidx += writeLen;
		}
		else
		{
			memcpy(&m_pBuffer[m_iWidx], pBuf, len1);
			memcpy(m_pBuffer, pBuf + len1, writeLen - len1);
			m_iWidx = writeLen - len1;
		}
	}

	return writeLen;
}

//
int RingBuffer::Read(unsigned char* pBuf, unsigned readLen)
{
	//m_pBuffer may alloc memory failed
	if (!m_pBuffer)
	{
		return -1;
	}

	if (!pBuf)
	{
		return -1;
	}

	int iWidx = m_iWidx;
	int iRidx = m_iRIdx;
	int bufferDataLen = m_uBufferSize - GetFreeBufferBytes(iRidx, iWidx) - 1;
	if (bufferDataLen <= readLen)
	{
		//can not use readall here, because GetFreeBufferBytes func and readall func may use the different
		//ridx and widx
		return ReadToWidx(pBuf, iWidx);
	}
	else  
	{
		if (m_iRIdx < iWidx)
		{
			memcpy(pBuf, &m_pBuffer[m_iRIdx], readLen);
			m_iRIdx += readLen;
		} 
		else
		{
			int len1 = m_uBufferSize - m_iRIdx;
			if (len1 >= readLen)
			{
				memcpy(pBuf, &m_pBuffer[m_iRIdx], readLen);
				m_iRIdx += readLen;
			}
			else
			{
				memcpy(pBuf, &m_pBuffer[m_iRIdx], len1);
				memcpy(pBuf + len1, m_pBuffer, readLen - len1);
				m_iRIdx = readLen - len1;
			}
		} //end m_iRIdx >= m_iWidx

		return readLen;
	}//end bufferDataLen > readLen
}

// read to widx
int RingBuffer::ReadToWidx(unsigned char* pBuf, int iWidx)
{
	//m_pBuffer may alloc memory failed
	if (!m_pBuffer)
	{
		return -1;
	}
	if (!pBuf || m_iWidx == m_iRIdx)
	{
		return -1;
	}

	int curWidx = m_iWidx;
	if (m_iRIdx < curWidx)
	{
		if (iWidx < m_iRIdx || iWidx > curWidx)
		{
			return -1;
		}
	}
	else
	{
		if (iWidx > curWidx && iWidx < m_iRIdx)
		{
			return -1;
		}
	}

	//must use temp varible here
	//int iWidx = m_iWidx;
	int readLen = 0;
	if (m_iRIdx > iWidx)
	{
		memcpy(pBuf, &m_pBuffer[m_iRIdx], m_uBufferSize - m_iRIdx);
		memcpy(pBuf + m_uBufferSize - m_iRIdx, m_pBuffer, iWidx);
		readLen = m_uBufferSize - m_iRIdx + iWidx;
	}
	else
	{
		memcpy(pBuf, &m_pBuffer[m_iRIdx], iWidx - m_iRIdx);
		readLen = iWidx - m_iRIdx;
	}
	//###can not set m_iRIdx = m_iWidx!!!!!
	m_iRIdx = iWidx;

	return readLen;
}

int RingBuffer::ReadAll(unsigned char* pBuf)
{
	//m_pBuffer may alloc memory failed
	if (!m_pBuffer)
	{
		return -1;
	}
	if (!pBuf || m_iWidx == m_iRIdx)
	{
		return -1;
	}

	return ReadToWidx(pBuf, m_iWidx);
}
 关键函数就这些了，有些地方写的比较繁琐，因为已经测试通过了，当做工具类，暂时就不改了...

 cpp下载地址: http://download.csdn.net/detail/lifexx/9603842  

由以下博客的分析可以知道，内核的kfifo使用了很多技巧以实现其高效性。比如，通过限定写入的数据不能溢出和内存屏障实现在单线程写单线程读的情况下不使用锁。因为锁是使用在共享资源可能存在冲突的情况下。还用设置buffer缓冲区的大小为2的幂次方，以简化求模运算，这样求模运算就演变为 (fifo->in & (fifo->size - 1))。通过使用unsigned int为kfifo的下标，可以不用考虑每次下标超过size时对下表进行取模运算赋值，这里使用到了无符号整数的溢出回零的特性。由于指示读写指针的下标一直在增加，没有进行取模运算，知道其溢出，在这种情况下写满和读完就是不一样的标志，写满是两者指针之差为fifo->size，读完的标志是两者指针相等。后面有一篇博客还介绍了VxWorks下的环形缓冲区的实现机制点击打开链接，从而可以看出linux下的fifo的灵巧性和高效性。

 

通过这篇文章也了解到了一些计算机体系结构的知识：多核计算机，每个核都有一个cache。

 

眉目传情之匠心独运的kfifo

 

Author：Echo Chen（陈斌）

Email：chenb19870707@gmail.com

Blog：Blog.csdn.net/chen19870707

Date：October 8th, 2014

      学不考儒，务掇精华；文不按古，匠心独运。Linux kernal 鬼斧神工，博大精深，让人叹为观止，拍手叫绝。然匠心独运的设计并非扑朔迷离、盘根错节，真正的匠心独运乃辞简理博、化繁为简，在简洁中昭显优雅和智慧，kfifo就是这样一种数据结构，它就是这样简约高效，匠心独运，妙不可言，下面就跟大家一起探讨学习。

 

一、kfifo概述

本文分析的原代码版本
			
2.6.32.63
		
kfifo的头文件
			
include/linux/kfifo.h
		
kfifo的源文件
			
kernel/kfifo.c
		
 

kfifo是一种"First In First Out “数据结构，它采用了前面提到的环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。更重要的是，kfifo采用了并行无锁技术，kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。

   1: struct kfifo {

   2:     unsigned char *buffer;    /* the buffer holding the data */

   3:     unsigned int size;    /* the size of the allocated buffer */

   4:     unsigned int in;    /* data is added at offset (in % size) */

   5:     unsigned int out;    /* data is extracted from off. (out % size) */

   6:     spinlock_t *lock;    /* protects concurrent modifications */

   7: };

buffer
			
用于存放数据的缓存
		
size
			
缓冲区空间的大小，在初化时，将它向上圆整成2的幂
		
in
			
指向buffer中队头
		
out
			
指向buffer中的队尾
		
lock
			
如果使用不能保证任何时间最多只有一个读线程和写线程，必须使用该lock实施同步。
		
 

它的结构如图：



这看起来与普通的环形缓冲区没有什么差别，但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性，处理各种操作，下面我们来详细分析。

 

二、kfifo内存分配和初始化

 

首先，看一个很有趣的函数，判断一个数是否为2的次幂，按照一般的思路，求一个数n是否为2的次幂的方法为看 n % 2 是否等于0， 我们知道“取模运算”的效率并没有 “位运算” 的效率高，有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性，若n为2的次幂，则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111))，&出来的结果肯定是0；如果n不为2的次幂，则各个位肯定有相同的 (如7(0111) 和6(0110))，&出来结果肯定为0。是不是很巧妙？

   1: bool is_power_of_2(unsigned long n)

   2: {

   3:     return (n != 0 && ((n & (n - 1)) == 0));

   4: }

再看下kfifo内存分配和初始化的代码，前面提到kfifo总是对size进行2次幂的圆整，这样的好处不言而喻，可以将kfifo->size取模运算可以转化为与运算，如下：

           kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)

 

“取模运算”的效率并没有 “位运算” 的效率高还记得不，不放过任何一点可以提高效率的地方。

   1: struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)

   2: {

   3:     unsigned char *buffer;

   4:     struct kfifo *ret;

   5:  

   6:     /*

   7:      * round up to the next power of 2, since our 'let the indices

   8:      * wrap' technique works only in this case.

   9:      */

  10:     if (!is_power_of_2(size)) {

  11:         BUG_ON(size > 0x80000000);

  12:         size = roundup_pow_of_two(size);

  13:     }

  14:  

  15:     buffer = kmalloc(size, gfp_mask);

  16:     if (!buffer)

  17:         return ERR_PTR(-ENOMEM);

  18:  

  19:     ret = kfifo_init(buffer, size, gfp_mask, lock);

  20:  

  21:     if (IS_ERR(ret))

  22:         kfree(buffer);

  23:  

  24:     return ret;

  25: }

 

三、kfifo并发无锁奥秘---内存屏障

  

   为什么kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的呢？天底下没有免费的午餐的道理人人都懂，下面我们就来看看kfifo实现并发无锁的奥秘。

我们知道 编译器编译源代码时，会将源代码进行优化，将源代码的指令进行重排序，以适合于CPU的并行执行。然而，内核同步必须避免指令重新排序，优化屏障（Optimization barrier）避免编译器的重排序优化操作，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。

举个例子，如果多核CPU执行以下程序：

   1: a = 1;

   2: b = a + 1;

   3: assert(b == 2);

假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：


			
1 CPU0执行a=1; 

			2 因为a在CPU1-cache中，所以CPU0发送一个read invalidate消息来占有数据 

			3 CPU0将a存入store buffer 

			4 CPU1接收到read invalidate消息，于是它传递cache-line，并从自己的cache中移出该cache-line 

			5 CPU0开始执行b=a+1; 

			6 CPU0接收到了CPU1传递来的cache-line，即“a=0” 

			7 CPU0从cache中读取a的值，即“0” 

			8 CPU0更新cache-line，将store buffer中的数据写入，即“a=1” 

			9 CPU0使用读取到的a的值“0”，执行加1操作，并将结果“1”写入b（b在CPU0-cache中，所以直接进行） 

			10 CPU0执行assert(b == 2); 失败
			
		
软件可通过读写屏障强制内存访问次序。读写屏障像一堵墙，所有在设置读写屏障之前发起的内存访问，必须先于在设置屏障之后发起的内存访问之前完成，确保内存访问按程序的顺序完成。Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统，如果仅用于多处理器系统，就使用smp_xxx函数，在单处理器系统上，它们什么都不要。


			
smp_rmb
			
			
适用于多处理器的读内存屏障。
		

			
smp_wmb
			
			
适用于多处理器的写内存屏障。
		

			
smp_mb
			
			
适用于多处理器的内存屏障。
		
如果对上述代码加上内存屏障,就能保证在CPU0取a时，一定已经设置好了a = 1:

 

   1: void foo(void)

   2: {

   3:  a = 1;

   4:  smp_wmb();

   5:  b = a + 1;

   6: }

这里只是简单介绍了内存屏障的概念，如果想对内存屏障有进一步理解,请参考我的译文《为什么需要内存屏障》。

 

 

四、kfifo的入队__kfifo_put和出队__kfifo_get操作

 

      __kfifo_put是入队操作，它先将数据放入buffer中，然后移动in的位置，其源代码如下：

   1: unsigned int __kfifo_put(struct kfifo *fifo,

   2:             const unsigned char *buffer, unsigned int len)

   3: {

   4:     unsigned int l;

   5:  

   6:     len = min(len, fifo->size - fifo->in + fifo->out);

   7:  

   8:     /*

   9:      * Ensure that we sample the fifo->out index -before- we

  10:      * start putting bytes into the kfifo.

  11:      */

  12:  

  13:     smp_mb();

  14:  

  15:     /* first put the data starting from fifo->in to buffer end */

  16:     l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));

  17:     memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

  18:  

  19:     /* then put the rest (if any) at the beginning of the buffer */

  20:     memcpy(fifo->buffer, buffer + l, len - l);

  21:  

  22:     /*

  23:      * Ensure that we add the bytes to the kfifo -before-

  24:      * we update the fifo->in index.

  25:      */

  26:  

  27:     smp_wmb();

  28:  

  29:     fifo->in += len;

  30:  

  31:     return len;

  32: }

 

6行，环形缓冲区的剩余容量为fifo->size - fifo->in + fifo->out，让写入的长度取len和剩余容量中较小的，避免写越界；

13行，加内存屏障，保证在开始放入数据之前，fifo->out取到正确的值（另一个CPU可能正在改写out值）

16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)，所以fifo->size - (fifo->in & (fifo->size - 1)) 即位 fifo->in 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为需要拷贝l 字节到fifo->buffer + fifo->in的位置上。

17行，拷贝l 字节到fifo->buffer + fifo->in的位置上，如果l = len，则已拷贝完成，第20行len – l 为0，将不执行，如果l = fifo->size - (fifo->in & (fifo->size - 1)) ，则第20行还需要把剩下的 len – l 长度拷贝到buffer的头部。

27行，加写内存屏障，保证in 加之前，memcpy的字节已经全部写入buffer，如果不加内存屏障，可能数据还没写完，另一个CPU就来读数据，读到的缓冲区内的数据不完全，因为读数据是通过 in – out 来判断的。

29行，注意这里 只是用了 fifo->in +=  len而未取模，这就是kfifo的设计精妙之处，这里用到了unsigned int的溢出性质，当in 持续增加到溢出时又会被置为0，这样就节省了每次in向前增加都要取模的性能，锱铢必较，精益求精，让人不得不佩服。

__kfifo_get是出队操作，它从buffer中取出数据，然后移动out的位置，其源代码如下：

   1: unsigned int __kfifo_get(struct kfifo *fifo,

   2:              unsigned char *buffer, unsigned int len)

   3: {

   4:     unsigned int l;

   5:  

   6:     len = min(len, fifo->in - fifo->out);

   7:  

   8:     /*

   9:      * Ensure that we sample the fifo->in index -before- we

  10:      * start removing bytes from the kfifo.

  11:      */

  12:  

  13:     smp_rmb();

  14:  

  15:     /* first get the data from fifo->out until the end of the buffer */

  16:     l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));

  17:     memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

  18:  

  19:     /* then get the rest (if any) from the beginning of the buffer */

  20:     memcpy(buffer + l, fifo->buffer, len - l);

  21:  

  22:     /*

  23:      * Ensure that we remove the bytes from the kfifo -before-

  24:      * we update the fifo->out index.

  25:      */

  26:  

  27:     smp_mb();

  28:  

  29:     fifo->out += len;

  30:  

  31:     return len;

  32: }

 

6行，可去读的长度为fifo->in – fifo->out，让读的长度取len和剩余容量中较小的，避免读越界；

13行，加读内存屏障，保证在开始取数据之前，fifo->in取到正确的值（另一个CPU可能正在改写in值）

16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->out % kfifo->size 可以转化为 kfifo->out & (kfifo->size – 1)，所以fifo->size - (fifo->out & (fifo->size - 1)) 即位 fifo->out 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为从fifo->buffer + fifo->in到末尾所要去读的长度。

17行，从fifo->buffer + fifo->out的位置开始读取l长度，如果l = len，则已读取完成，第20行len – l 为0，将不执行，如果l =fifo->size - (fifo->out & (fifo->size - 1)) ，则第20行还需从buffer头部读取 len – l 长。

27行，加内存屏障，保证在修改out前，已经从buffer中取走了数据，如果不加屏障，可能先执行了增加out的操作，数据还没取完，令一个CPU可能已经往buffer写数据，将数据破坏，因为写数据是通过fifo->size - (fifo->in & (fifo->size - 1))来判断的 。

29行，注意这里 只是用了 fifo->out +=  len 也未取模，同样unsigned int的溢出性质，当out 持续增加到溢出时又会被置为0，如果in先溢出，出现 in  < out 的情况，那么 in – out 为负数（又将溢出），in – out 的值还是为buffer中数据的长度。

 

这里图解一下 in 先溢出的情况，size = 64， 写入前 in = 4294967291， out = 4294967279 ，数据 in – out = 12;



    写入 数据16个字节，则 in + 16 = 4294967307，溢出为 11，此时 in – out = –4294967268，溢出为28，数据长度仍然正确，由此可见，在这种特殊情况下，这种计算仍然正确，是不是让人叹为观止，妙不可言？

 



五、扩展

          kfifo设计精巧，妙不可言，但主要为内核提供服务，内存屏障函数也主要为内核提供服务，并未开放出来，但是我们学习到了这种设计巧妙之处，就可以依葫芦画瓢，写出自己的并发无锁环形缓冲区，这将在下篇文章中给出，至于内存屏障函数的问题，好在gcc 4.2以上的版本都内置提供__sync_synchronize()这类的函数，效果相差不多。《眉目传情之并发无锁环形队列的实现》给出自己的并发无锁的实现，有兴趣的朋友可以参考一下。

 

Reference

1.http://blog.csdn.net/xujianqun/article/details/7800813

2.http://zh.wikipedia.org/wiki/%E7%92%B0%E5%BD%A2%E7%B7%A9%E8%A1%9D%E5%8D%80#.E7.94.A8.E6.B3.95

3.http://blog.csdn.net/linyt/article/details/5764312

 

-

Echo Chen：Blog.csdn.net/chen19870707

-

在多线程环境下为了保证线程安全，往往需要加锁，例如读写锁可以保证读写互斥，读读不互斥。有没有一种数据结构能够实现无锁的线程安全呢？答案就是使用RingBuffer循环队列。在Disruptor项目中就运用到了RingBuffer。

RingBuffer的基本原理如下：



在RingBuffer中设置了两个指针，head和tail。head指向下一次读的位置，tail指向的是下一次写的位置。RingBuffer可用一个数组进行存储，数组内元素的内存地址是连续的，这是对CPU缓存友好的——也就是说，在硬件级别，数组中的元素是会被预加载的，因此在RingBuffer中，CPU无需时不时去主内存加载数组中的下一个元素。通过对head和tail指针的移动，可以实现数据在数组中的环形存取。当head==tail时，说明buffer为空，当head==(tail+1)%bufferSize则说明buffer满了。

在进行读操作的时候，我们只修改head的值，而在写操作的时候我们只修改tail的值。在写操作时，我们在写入内容到buffer之后才修改tail的值；而在进行读操作的时候，我们会读取tail的值并将其赋值给copyTail。赋值操作是原子操作。所以在读到copyTail之后，从head到copyTail之间一定是有数据可以读的，不会出现数据没有写入就进行读操作的情况。同样的，读操作完成之后，才会修改head的数值；而在写操作之前会读取head的值判断是否有空间可以用来写数据。所以，这时候tail到head - 1之间一定是有空间可以写数据的，而不会出现一个位置的数据还没有读出就被写操作覆盖的情况。这样就保证了RingBuffer的线程安全性。

import java.util.Arrays;

public class RingBuffer<T> {

    private final static int DEFAULT_SIZE  = 1024;
    private Object[] buffer;
    private int head = 0;
    private int tail = 0;
    private int bufferSize;

    public RingBuffer(){
        this.bufferSize = DEFAULT_SIZE;
        this.buffer = new Object[bufferSize];
    }

    public RingBuffer(int initSize){
        this.bufferSize = initSize;
        this.buffer = new Object[bufferSize];
    }

    private Boolean empty() {
        return head == tail;
    }

    private Boolean full() {
        return (tail + 1) % bufferSize == head;
    }

    public void clear(){
        Arrays.fill(buffer,null);
        this.head = 0;
        this.tail = 0;
    }

    public Boolean put(String v) {
        if (full()) {
            return false;
        }
        buffer[tail] = v;
        tail = (tail + 1) % bufferSize;
        return true;
    }

    public Object get() {
        if (empty()) {
            return null;
        }
        Object result = buffer[head];
        head = (head + 1) % bufferSize;
        return result;
    }

    public Object[] getAll() {
        if (empty()) {
            return new Object[0];
        }
        int copyTail = tail;
        int cnt = head < copyTail ? copyTail - head : bufferSize - head + copyTail;
        Object[] result = new String[cnt];
        if (head < copyTail) {
            for (int i = head; i < copyTail; i++) {
                result[i - head] = buffer[i];
            }
        } else {
            for (int i = head; i < bufferSize; i++) {
                result[i - head] = buffer[i];
            }
            for (int i = 0; i < copyTail; i++) {
                result[bufferSize - head + i] = buffer[i];
            }
        }
        head = copyTail;
        return result;
    }

}

RingBuffer解决粘包问题：

TCP粘包是指发送方发送的若干包数据到接收方接收时粘成一包，从接收缓冲区看，后一包数据的头紧接着前一包数据的尾。粘包可能由发送方造成，也可能由接收方造成。TCP为提高传输效率，发送方往往要收集到足够多的数据后才发送一包数据，造成多个数据包的粘连。如果接收进程不及时接收数据，已收到的数据就放在系统接收缓冲区，用户进程读取数据时就可能同时读到多个数据包。因为系统传输的数据是带结构的数据，需要做分包处理。

 

为了适应高速复杂网络条件，我们设计实现了粘包处理模块，由接收方通过预处理过程，对接收到的数据包进行预处理，将粘连的包分开。为了方便粘包处理，提高处理效率，在接收环节使用了环形缓冲区来存储接收到的数据。其结构如表1所示。

                                                            表1 环形缓冲结构


			
字段名
			
			

			
类型
			
			

			
含义
			
		

			
CS
			
			

			
CRITICAL_SECTION
			
			

			
保护环形缓冲的临界区
			
		

			
pRingBuf
			
			

			
UINT8*
			
			

			
缓冲区起始位置
			
		

			
pRead
			
			

			
UINT8*
			
			

			
当前未处理数据的起始位置
			
		

			
pWrite
			
			

			
UINT8*
			
			

			
当前未处理数据的结束位置
			
		

			
pLastWrite
			
			

			
UINT8*
			
			

			
当前缓冲区的结束位置
			
		
环形缓冲跟每个TCP套接字绑定。在每个TCP的SOCKET_OBJ创建时，同时创建一个PRINGBUFFER结构并初始化。这时候，pRingBuf指向环形缓冲区的内存首地址，pRead、pWrite指针也指向它。pLastWrite指针在这时候没有实际意义。初始化之后的结构如图1所示。



 

                                  图1 初始化后的环形缓冲区

在每次投递一个TCP的接收操作时，从RINGBUFFER获取内存作接收缓冲区，一般规定一个最大值L1作为可以写入的最大数据量。这时把pWrite的值赋给BUFFER_OBJ的buf字段，把L1赋给bufLen字段。这样每次接收到的数据就从pWrite开始写入缓冲区，最多写入L1字节，如图 2。



                                   图2 分配缓冲后的环形缓冲

如果某次分配过程中，pWrite到缓冲区结束的位置pEnd长度不够最小分配长度L1，为了提高接收效率，直接废弃最后一段内存，标记pLastWrite为pWrite。然后从pRingBuf开始分配内存，如图 3。



                                   图 3 使用到结尾的环形缓冲

特殊情况下，如果处理包速度太慢，或者接收太快，可能导致未处理包占用大部分缓冲区，没有足够的缓冲区分配给新的接收操作，如图4。这时候直接报告错误即可。



                                  图 4 没有足够接收缓冲的环形缓冲

当收到一个长度为L数据包时，需要修改缓冲区的指针。这时候已经写入数据的位置变为（pWrite+L），如图 5。



                                  图 5 收到长度为L的数据的环形缓冲

分析上述环形缓冲的使用过程，收到数据后的情况可以简单归纳为两种：pWrite>pRead，接收但未处理的数据位于pRead到pWrite之间的缓冲区；pWrite<pRead，这时候，数据位于pRead到pLastWrite和pRingbuf到pWrite之间。这两种情况分别对应图6、图 7。

首先分析图6。此时，pRead是一个包的起始位置，如果L1足够一个包头长度，就获取该包的长度信息，记为L。假如L1>L，就说明一个数据包接收完成，根据包类型处理包，然后修改pRead指针，指向下一个包的起始位置（pRead+L）。这时候仍然类似于之前的状态，于是解包继续，直到L1不足一个包的长度，或者不足包头长度。这时退出解包过程，等待后续的数据到来。



                                图 6 有未处理数据的环形缓冲（1）



                              图 7 有未处理数据的环形缓冲（2）

图 8稍微复杂。首先按照上述过程处理L1部分。存在一种情况，经过若干个包处理之后，L1不足一个包，或者不足一个包头。如果这时（L1+L2）足够一个包的长度，就需要继续处理。另外申请一个最大包长度的内存区pTemp，把L1部分和L2的一部分复制到pTemp，然后执行解包过程。

经过上述解包之后，pRead就转向pRingBuf到pWrite之间的某个位置，从而回归情况图 6，继续按照图 6部分执行解包。