使用无锁环形缓冲(Wait-free ring buffer)提升IO效率

相关文章：

无锁队列

http://aigo.iteye.com/blog/2288131

 

摘自：http://www.oschina.net/code/snippet_54334_12505

代码源于 http://www.ibm.com/developerworks/cn/linux/l-cn-lockfree/ 的实现. 
注意: 构造时参数 buf_size 必须是2的N次方.

 

#ifndef min
#define min(a,b) (((a) < (b)) ? (a) : (b))
#endif

#ifndef max
#define max(a,b) (((a) > (b)) ? (a) : (b))
#endif

// 无锁缓冲队列.
class circular_buffer
{
public:
   circular_buffer(int buf_size)
      : m_buffer_size(buf_size)
      , m_circle_buffer(NULL)
      , m_write_p(0)
      , m_read_p(0)
   {
      m_circle_buffer = new char[m_buffer_size];
   }

   ~circular_buffer()
   {
      if (m_circle_buffer)
         delete[] m_circle_buffer;
      m_circle_buffer = NULL;
   }

   void clear()
   {
      m_write_p = 0;
      m_read_p = 0;
   }

   unsigned int available()
   {
      return m_buffer_size - (m_write_p - m_read_p);
   }

   unsigned int used()
   {
      return m_write_p - m_read_p;
   }

   unsigned int put_data(char* buffer, unsigned int len)
   {
      unsigned int l;
      len = _min(len, m_buffer_size - m_write_p + m_read_p);
      /* first put the data starting from fifo->in to buffer end */
      l = _min(len, m_buffer_size - (m_write_p & (m_buffer_size - 1)));
      memcpy(m_circle_buffer + (m_write_p & (m_buffer_size - 1)), buffer, l);
      /* then put the rest (if any) at the beginning of the buffer */
      memcpy(m_circle_buffer, buffer + l, len - l);
      m_write_p += len;
      return len;
   }

   unsigned int get_data(char* buffer, unsigned int len)
   {
      unsigned int l; 
      len = _min(len, m_write_p - m_read_p); 
      /* first get the data from fifo->out until the end of the buffer */ 
      l = _min(len, m_buffer_size - (m_read_p & (m_buffer_size - 1))); 
      memcpy(buffer, m_circle_buffer + (m_read_p & (m_buffer_size - 1)), l); 
      /* then get the rest (if any) from the beginning of the buffer */ 
      memcpy(buffer + l, m_circle_buffer, len - l); 
      m_read_p += len; 
      return len; 
   }

protected:
   inline unsigned int _max(unsigned int a, unsigned int b)
   {
      return max(a, b);
   }

   inline unsigned int _min(unsigned int a, unsigned int b)
   {
      return min(a, b);
   }

private:
   int m_buffer_size;
   char* m_circle_buffer;
   unsigned int m_write_p;
   unsigned int m_read_p;
};

 

 

摘自：http://blog.csdn.net/xocoder/article/details/7880769

 

最近在重构之前写的网络底层时，从各个方面认真考虑了每一个细节实现。其中，在提交I/O（WSASend/WSARecv）和I/O完成（GetQueuedCompletionStatus）时，难免出现一个缓冲区需要两个线程公用的问题。

 

假设主线程不断发送该消息，这些消息被堆叠在一个缓冲区里，定时使用WSASend提交发送I/O请求，在GetQueuedCompletionStatus返回后，才能按照已发送的字节数去删掉该缓冲区里相应字节数的数据。不明白？好吧我说的简单一些。

WSASend调用后，你传递的参数只是说明：我希望发送这么多数据。但请求提交后，你的要求未必能够被全部满足，也就是说也许你想发送1024字节的东西，但也许GetQueuedCompletionStatus返回，操作完成后，本次只成功发送了1000个字节，也就是说剩余的24字节的数据，你还需要再调用WSASend，直到都发送成功为止。所以在这种情况下，一定要等待GetQueuedCompletionStatus返回，才知道究竟发送成功了多少，也才能从之前的发送缓冲里删掉数据。否则，如果你在提交WSASend时就把数据删掉了，而GetQueuedCompletionStatus返回后却告诉你只发了1000字节，那就杯具了-----那24字节的数据永远地离开了我们。

 

而在这种情况下，我们发送消息，也就是向这个缓冲区后面堆放要发送的数据，是主线程中执行的，而GetQueuedCompletionStatus完成后，从缓冲区内弹出数据，确是IOCP的工作线程做的。当然，最简单的办法就是------加个锁呗。但是，在I/O频繁的情况下，可以想象会出现多少线程争用的情况。于是，就有了本文要说的东西：环形缓冲。

 

环形缓冲的原理并不难理解，只适用于一个线程写，一个线程读的情况。环形缓冲的原理我就不再赘述，可以自行搜索。

 

废话不多说。下面给出我在这次优化中写的一个环形缓冲类，该环形缓冲完美地在IOCP中工作了起来，实实在在地解决了线程争用引发地效率低下。

2012.9.1 0:57 重贴代码
修改了一个可能出现的误置Full标志的BUG，之前的代码中，是先增加写指针，再判断是否等于读指针，等于则置Full标志，但若在该判断之前，读线程将数据读空，此时写线程继续工作，进行该判断时，就会发现写指针 = 读指针（但是是由于读空造成的），于是错误地将状态置为Full。

 

2014.8.4 2:08 重贴代码

重写代码，解决掉xiaolizi提出的可能会引发数据被覆盖的BUG，详细请见回复：（十分感谢您提出这个问题）
XRingBuffer.h 

#pragma once

#include "XBaseDefine.h"

const BYTE XRING_BUFFER_READ_POS_AND_WRITE_POS_SIZE = 2;

class XRingBuffer
{
public:
	XRingBuffer(const DWORD size);
	~XRingBuffer();

	bool pushData(const void* data, const DWORD size);

	bool copyData(void* dest, const DWORD destSize, const DWORD copySize);
	bool popData(void* dest, const DWORD destSize, const DWORD popSize);
	bool popData(const DWORD popSize);
	const DWORD getUsedSize() const;
	const DWORD getFreeSize() const;
private:
	bool copyDataWithAddReadPosOption(void* dest, const DWORD destSize, const DWORD popSize, bool addReadPos);
private:
	char* _buffer;
	const DWORD _size;
	volatile DWORD _write_pos;
	volatile DWORD _read_pos;
};

 XRingBuffer.cpp

#include "XRingBuffer.h"
#include "XDebug.h"

XRingBuffer::XRingBuffer(const DWORD size) : 
_size(size + XRING_BUFFER_READ_POS_AND_WRITE_POS_SIZE),
_write_pos(1),
_read_pos(0),
_buffer(NULL)
{
	_buffer = new char[_size];
}

XRingBuffer::~XRingBuffer()
{
	delete [] _buffer;
}

bool XRingBuffer::pushData(const void* data, const DWORD size)
{
	const DWORD freeSize = getFreeSize();
	if(freeSize < size)
	{
		return false;
	}
	const DWORD readPos =_read_pos;
	const DWORD writePos = _write_pos;
	if(writePos > readPos)
	{
		const DWORD lenFromWritePosToBufferEnd = _size - writePos;
		if(size <= lenFromWritePosToBufferEnd)
		{
			memcpy(_buffer + _write_pos, data, size);
			_write_pos += size;
			if(_write_pos == _size)
			{
				_write_pos = 0;
			}
			else if(_write_pos > _size)
			{
				assert_fail("wirtepos cannot bigger than size");
				return false;
			}
			return true;
		}
		else
		{	// 先拷贝前一部分到缓冲区尾部
			memcpy(_buffer + _write_pos, data, lenFromWritePosToBufferEnd);
			const DWORD secondPartLen = size - lenFromWritePosToBufferEnd;
			// 拷贝后一部分到缓冲区前部
			memcpy(_buffer, ((char*)data) + lenFromWritePosToBufferEnd, secondPartLen);
			_write_pos = secondPartLen;
			return true;
		}
	}
	else if(writePos < readPos)
	{
		memcpy(_buffer + writePos, data, size);
		_write_pos += size;
		return true;
	}
	else
	{
		assert_fail("write pos equal read pos, it's an error");
		return false;
	}
}


bool XRingBuffer::copyData(void* dest, const DWORD destSize, const DWORD copySize)
{
	return copyDataWithAddReadPosOption(dest, destSize, copySize, false);
}

bool XRingBuffer::popData(void* dest, const DWORD destSize, const DWORD popSize)
{
	return copyDataWithAddReadPosOption(dest, destSize, popSize, true);
}

bool XRingBuffer::popData(const DWORD popSize)
{
	return copyDataWithAddReadPosOption(NULL, 0, popSize, true);
}

const DWORD XRingBuffer::getUsedSize() const
{
	const DWORD writePos = _write_pos;
	const DWORD readPos = _read_pos;
	if(writePos > readPos)
	{
		return writePos - readPos - 1;
	}
	else if(writePos < readPos)
	{
		return (_size - readPos - 1) + _write_pos;
	}
	else
	{
		assert_fail("write pos equal read pos, it's an error");
		return 0;
	}
}

const DWORD XRingBuffer::getFreeSize() const
{
	const DWORD usedSize = getUsedSize();
	return _size - (usedSize + XRING_BUFFER_READ_POS_AND_WRITE_POS_SIZE);
}

bool XRingBuffer::copyDataWithAddReadPosOption(void* dest, const DWORD destSize, const DWORD copySize, bool addReadPos)
{
	const DWORD usedSize = getUsedSize();
	if(usedSize < copySize)
	{
		assert_fail("data is not enought to copy");
		return false;
	}
	if(dest != NULL)
	{
		if(destSize < copySize)
		{
			assert_fail("dest buffer size is smaller than copy size");
			return false;
		}	
	}
	const DWORD writePos = _write_pos;
	const DWORD readPos = _read_pos;
	if(writePos > readPos)
	{
		if(dest != NULL)
		{
			memcpy(dest, _buffer + readPos + 1, copySize);
		}
		if(addReadPos)
		{
			_read_pos += copySize;
		}
		return true;
	}
	else if(writePos < readPos)
	{
		const DWORD lenFromReadPosToBufferEnd = _size - readPos - 1;
		if(copySize <= lenFromReadPosToBufferEnd)
		{
			if(dest != NULL)
			{
				memcpy(dest, _buffer + readPos + 1, copySize);
			}
			if(addReadPos)
			{
				_read_pos += copySize;
				assert(_read_pos < _size);
			}
			return true;
		}
		else
		{
			const DWORD secondPartLen = copySize - lenFromReadPosToBufferEnd;
			if(dest != NULL)
			{
				memcpy(dest, _buffer + readPos + 1, lenFromReadPosToBufferEnd);
				memcpy(((char*)dest) + lenFromReadPosToBufferEnd, _buffer, secondPartLen);
			}
			if(addReadPos)
			{
				_read_pos = secondPartLen - 1;
			}
			return true;
		}
	}
	else
	{
		assert_fail("write pos equal read pos, it's an error");
		return false;
	}
}