绪论

设计缘由

工作后第一个项目是实现一个数据转发服务器，将视频数据通过websocket转发给手机app端。

第一次在需要考虑网络因素，需要设计一个消息缓冲队列，用于存储大量数据。领导建议我利用环形缓冲区替换链式缓冲区减少memmove的次数，提高服务器性能。

为什么要设计环形缓冲区

目的：避免频繁的内存创建取消、分配，移动以提高服务器性能。内存一直只用了一块。

环形缓冲区的实现原理

环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。

图1、图2和图3是一个环形缓冲区的运行示意图。图1是环形缓冲区的初始状态，可以看到读指针和写指针都指向第一个缓冲区处；图2是向环形缓冲区中添加了一个数据后的情况，可以看到写指针已经移动到数据块2的位置，而读指针没有移动；图3是环形缓冲区进行了读取和添加后的状态，可以看到环形缓冲区中已经添加了两个数据，已经读取了一个数据。

判断“空”和“满”

上述的操作并不复杂，不过有一个小小的麻烦：空环和满环的时候，R和W都指向同一个位置！这样就无法判断到底是“空”还是“满”。

大体上有两种方法可以解决该问题。
办法1：始终保持一个元素不用
　　当空环的时候，R和W重叠。当W比R跑得快，追到距离R还有一个元素间隔的时候，就认为环已经满。当环内元素占用的存储空间较大的时候，这种办法显得很土（浪费空间）。
办法2：维护额外变量
　　如果不喜欢上述办法，还可以采用额外的变量来解决。比如可以用一个整数记录当前环中已经保存的元素个数（该整数>=0）。当R和W重叠的时候，通过该变量就可以知道是“空”还是“满”。

环形缓冲区设计分两种模式

模式一

写入读取数据，不考虑读取数据的长度，读取数据的顺序为写入数据的顺序

环形缓冲区测试代码

#include "lwsBuffer.h"
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
int main()
{
    char dataBuf[1024];
    void *temp = NULL;
    int readFd = open("lwsBuffer.cpp", O_RDONLY);
    int writeFd = open("temp.cpp", O_WRONLY | O_CREAT);

    int ret;
    memset(dataBuf, '\0', 1024);
    lwsBuffer Buff;
    while (1)
    {
        /* code */
        memset(dataBuf, '\0', sizeof(dataBuf));
        ret = read(readFd, dataBuf, sizeof(dataBuf));
        if (ret == 0)
        {
            printf("read end..");
            break;
        }
        else if (ret < 0)
            printf("read error ret:%d", ret);
        else
            printf("read  ret:%d\n", ret);
        ret = Buff.write(dataBuf, ret); //将 dataBuf 数据写入到Buff缓冲区
        printf("write ret:%d\n", ret);
    }
    printf("\n\ncurrent Buff total len:%d\n\n", Buff.getTotalLen());
    while (1)
    {
        char tempBuf[1024];
        memset(tempBuf,'\0',sizeof(tempBuf));
        ret = Buff.read(&temp); //从 Buff缓冲区中读取数据
        if (ret == -1)
            break;
        memmove(tempBuf, temp, ret);
        /* code */
        printf("total len:%d\n", Buff.getTotalLen());
        write(writeFd, tempBuf, ret);
    }

    close(readFd);
    close(writeFd);
    return 0;
}

makefile编译文件

test:test.cpp
	g++ -o test test.cpp lwsBuffer.cpp 
.PHONY:clean
clean:
	rm -f test temp.cpp

运行结果

sh-4.3$ make
g++ -o test test.cpp lwsBuffer.cpp 
sh-4.3$ ls
lwsBuffer.cpp  lwsBuffer.h  makefile  test  test.cpp
sh-4.3$ ./test 
read  ret:1024
write ret:1024
read  ret:1024
write ret:1024
read  ret:1024
write ret:1024
read  ret:964
write ret:964
read end..

current Buff total len:4036

total len:3012
total len:1988
total len:964
total len:0
sh-4.3$ ls
lwsBuffer.cpp  lwsBuffer.h  makefile  temp.cpp  test  test.cpp

执行后结果就是读取 lwsBuffer.cpp 里面的数据，储存到环形缓冲区，再从环形缓冲区读取数据写入到 temp.cpp

应用场景和优缺点

大量数据的转发

优点：牺牲少量内存实现最少的数据拷贝memmove

缺点：当转发的数据很大时，没一个对象浪费的内存在转发的数据大小之内

​ 当读取数据缓慢的时候会造成频繁的内存重分配，缓冲区变得越来越大。

lwsBuffer.h

#pragma once

#ifndef _LWS_BUFFER_H_
#define _LWS_BUFFER_H_
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <list>
#define BUFFER_SIZE 1024
class lwsBuffer
{
private:
    /* data */
    void* buffer;               /* 数据 */
    size_t bufMaxSize;          /* 最大的存储数据大小 */
    size_t rightWritePos;
    int readpos,writepos;       /* 读写位置 */

    size_t totalLen;            /* 存储的数据大小 */
    std::list<int> lenList;     /* 数据长度的链表 */
public:
    lwsBuffer(/* args */);
    ~lwsBuffer();
public:
    int write(void *data, int dataLen);
    int read(void** data);
    int getTotalLen();
protected:
    int writeAfter(void* data, int dataLen);
    int writePre(void* data, int dataLen);
    void _remalloc();
};
#endif

lwsBuffer.cpp

#include "lwsBuffer.h"

lwsBuffer::lwsBuffer(/* args */)
{
    this->readpos = 0;
    this->writepos = 0;
    this->rightWritePos = 0;
    this->bufMaxSize = BUFFER_SIZE;
    this->buffer = malloc(this->bufMaxSize);

    this->totalLen = 0;
    this->lenList.clear();
}

lwsBuffer::~lwsBuffer()
{
    if (buffer)
        free(buffer);
}

int lwsBuffer::write(void *data, int dataLen)
{
    int ret = -1;
    if (dataLen <= 0 || data == NULL)
        return ret;

    /* writePos 在 readPos 前 / readPos == writePos push*/
    if (this->writepos >= this->readpos)
    {
        ret = writePre(data, dataLen);
    }
    /* readPos 在 writePos 前  push*/
    else if(this->writepos < this->readpos)
    {
        ret = writeAfter(data, dataLen);
    }
    return ret;
}

int lwsBuffer::writePre(void* data, int dataLen)
{
    int ret = -1;
    /*  写入位置在前  */
    /*  buffer 后面有空间可以写入数据*/
    if ((this->writepos + dataLen) <= this->bufMaxSize) 
    {
        //将数据写入到 buffer 里面去
        memmove((char *)this->buffer + this->writepos, data, dataLen);
        /* 修改 writepos 偏移 */
        this->writepos = this->writepos + dataLen;
        /* 计算数据长度*/
        lenList.push_back(dataLen);
        totalLen += dataLen;
        ret = dataLen;
    }
    else
    {
        /*  buffer 后面没有空间可以写入数据  记录下罪*/
        this->rightWritePos = this->writepos;
        /* 修改 writepos 偏移 */
        this->writepos = 0;
        ret = writeAfter(data, dataLen);
    }
    return ret;
}

int lwsBuffer::writeAfter(void *data, int dataLen)
{
    int ret = -1;
    /*  写入位置在后  */
    /*  writepos 到 readpos 有足够的空间可以写入数据  */
    if ((this->writepos + dataLen) < this->readpos)
    {
        //将数据写入到 buffer 里面去
        memmove((char *)this->buffer + this->writepos, data, dataLen);
        /* 修改 writepos 偏移 */
        this->writepos = this->writepos + dataLen;
        /* 计算数据长度*/
        lenList.push_back(dataLen);
        totalLen += dataLen;
        ret = dataLen;
    }
    else
    {
        this->_remalloc();
        ret = writePre(data, dataLen);
    }
    return ret;
}

void lwsBuffer::_remalloc()
{
    /*  数据满了 */
    void *newBuf = malloc(this->bufMaxSize + BUFFER_SIZE / 2);
    /*      */
    memmove(newBuf, (char*)this->buffer + this->readpos, this->rightWritePos - this->readpos);
    memmove((char*)newBuf + this->rightWritePos - this->readpos, this->buffer, this->writepos);
    free(this->buffer);
    this->buffer = newBuf;

    this->writepos = this->rightWritePos - this->readpos + this->writepos;
    this->readpos = 0;
    this->bufMaxSize = this->bufMaxSize + BUFFER_SIZE / 2;
    // printf("buffMaxSize:%d, totalLen:%d ,list size:%d\n", (int)this->bufMaxSize, (int)this->totalLen, (int)lenList.size());
}

int lwsBuffer::read(void** data)
{
    int ret = -1;
    if (this->totalLen > 0)
    {
        int dataLen = lenList.front();
        if((this->readpos + dataLen) <= this->bufMaxSize)
        {
            (*data) = (char *)this->buffer + this->readpos;
            // printf("\n读取位置: %d ,读取信息 len: %d, data:%s\n", this->readpos, dataLen, (char*)data);
            /* 修改 writepos 偏移 */
            this->readpos += dataLen;
            /* 计算数据长度*/
            this->totalLen -= dataLen;
            lenList.pop_front();
            ret = dataLen;
        }
        else{
            printf("从头开始读取\n");
            this->readpos = 0;
            (*data) = (char *)this->buffer + this->readpos;

            // printf("\n读取位置: %d ,读取信息 len：%d, data:%s\n", this->readpos, dataLen, (char*)data);
            this->readpos += dataLen;
            /* 计算数据长度*/
            this->totalLen -= dataLen;
            lenList.pop_front();
            ret = dataLen;
        }
    }
    return ret;
}

int lwsBuffer::getTotalLen()
{
    return this->totalLen;
}

模式二

写入读取数据，写入指定长度数据，和读取指定长度数据，模仿QBuffer的读写功能

环形缓冲区测试代码

#include "lwsBuffer.h"
#include<stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

int main()
{
    char buf[1024],temp[1024];
    int readFd = open("lwsBuffer.cpp",O_RDONLY);
    int writeFd = open("temp.cpp",O_WRONLY|O_CREAT,0666);
    
    int ret;
    memset(buf, '\0', 1024);
    memset(temp, '\0', 1024);
    lwsBuffer Buff;
    while (1)
    {
        /* code */
        ret = read(readFd, buf, sizeof(buf));
        if (ret == 0)
            break;
        int dataLen = Buff.write(buf,ret);  //将数据保存到环形缓冲区
        memset(buf, '\0', 1024);
        printf("dataLen:%d\n",dataLen);
    }

    while(1)
    {
        memset(temp,'\0',sizeof(temp));
        ret = Buff.read(temp, 1024);    //从环形缓冲区中读取数据
        if (ret == -1)
            break;
        /* code */
        ret = write(writeFd, temp, ret);
        printf("write ret:%d\n", ret);
    }

    close(readFd);
    close(writeFd);
    return 0;
}

makefile编译文件

test:test.cpp
	g++ -o test test.cpp lwsBuffer.cpp 
.PHONY:clean
clean:
	rm -f test temp.cpp

运行结果

sh-4.3$ make
g++ -o test test.cpp lwsBuffer.cpp 
sh-4.3$ ./test 
dataLen:1024
dataLen:1024
dataLen:1024
dataLen:766
write ret:1024
write ret:1024
write ret:1024
write ret:766

应用场景和优缺点

适用于少量数据的频繁读写

优点：多次memmove实现占空间最少的快速读写

缺点：当转发的数据很大且很频繁时，多次memmove会导致性能的减少

lwsBuffer.h

#pragma once

#ifndef _LWS_BUFFER_H_
#define _LWS_BUFFER_H_
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define BUFFER_SIZE 1024
class lwsBuffer
{
private:
    /* data */
    void* buffer;               /*数据*/
    size_t bufMaxSize;          /* 最大的存储数据大小 */
    size_t bufLen;              /* 存储的数据大小 */
    int readpos,writepos;       /* 读写位置 */
public:
    lwsBuffer(/* args */);
    ~lwsBuffer();
public:
    int write(void *data, int dataLen);
    int read(void *data, int dataLen);

protected:
    int writeAfter(void* data, int dataLen);
    int writePre(void* data, int dataLen);
    void _remalloc();
};

#endif

lwsBuffer.cpp

#include "lwsBuffer.h"

lwsBuffer::lwsBuffer(/* args */)
{
    this->readpos = 0;
    this->writepos = 0;
    this->bufLen = 0;
    this->bufMaxSize = BUFFER_SIZE;
    this->buffer = malloc(this->bufMaxSize);
}

lwsBuffer::~lwsBuffer()
{
    if (buffer)
        free(buffer);
}

int lwsBuffer::write(void *data, int dataLen)
{
    int ret = -1;
    /* writePos 在 readPos 前 / readPos == writePos push*/
    if (this->writepos >= this->readpos)
    {
        ret = writePre(data, dataLen);
    }
    /* readPos 在 writePos 前  push*/
    else if(this->writepos < this->readpos)
    {
        ret = writeAfter(data, dataLen);
    }
    return ret;
}

int lwsBuffer::writePre(void* data, int dataLen)
{
    int ret = -1;
    /*  写入位置在前  */
    /*  buffer 后面有空间可以写入数据  预留一个字节不存储数据，用于区分*/
    if ((this->writepos + dataLen) <= this->bufMaxSize)
    {
        //将数据写入到 buffer 里面去
        memmove((char *)this->buffer + this->writepos, data, dataLen);
        // printf("即将 push %d 消息 on:%d :%s\n", dataLen, prod->writepos, (char *)prod->buffer + prod->writepos + LWS_PRE);
        this->writepos = this->writepos + dataLen;
        ret = dataLen;
        bufLen += dataLen;
    }
    else
    {
        /*  buffer 后面没有空间可以写入数据  记录下*/
        int temp = this->bufMaxSize - this->writepos;
        temp = writePre(data, temp);
        this->writepos = 0;
        ret = writeAfter((char*)data + temp, dataLen - temp) + temp;
    }
    return ret;
}

int lwsBuffer::writeAfter(void *data, int dataLen)
{
    int ret = -1;
    /*  写入位置在后  */
    /*  writepos 到 readpos 有足够的空间可以写入数据  */
    if ((this->writepos + dataLen) < this->readpos)
    {
        //将数据写入到 buffer 里面去
        memmove((char *)this->buffer + this->writepos, data, dataLen);
        this->writepos = this->writepos + dataLen;
        ret = dataLen;
        bufLen += dataLen;
    }
    else
    {
        this->_remalloc();
        ret = writePre(data, dataLen);
    }
    return ret;
}

void lwsBuffer::_remalloc()
{
    /*  数据满了 */
    void *newBuf = malloc(this->bufMaxSize + BUFFER_SIZE / 2);
    /*      */
    memmove(newBuf, (char*)this->buffer + this->readpos, this->bufMaxSize - this->readpos);
    memmove((char*)newBuf + this->bufMaxSize - this->readpos, this->buffer, this->writepos);
    free(this->buffer);
    this->buffer = newBuf;

    this->writepos = this->bufMaxSize - this->readpos + this->writepos;
    this->readpos = 0;
    this->bufMaxSize = this->bufMaxSize + BUFFER_SIZE / 2;
    // printf("buffMaxSize:%d, bufLen:%d\n", (int)this->bufMaxSize,(int)this->bufLen);
}

int lwsBuffer::read(void *data, int dataLen)
{
    int ret = -1;
    if (this->bufLen > 0)
    {
        if (dataLen > this->bufLen)
        {
            dataLen = this->bufLen;
        }
        if ((this->readpos + dataLen) <= this->bufMaxSize)
        {
            memmove(data, (char *)this->buffer + this->readpos, dataLen);
            // printf("\n读取位置: %d ,读取信息 len：%d,data:%s\n", this->readpos, dataLen, (char *)data);
            this->readpos += dataLen;
            this->bufLen -= dataLen;
            ret = dataLen;
        }
        else
        {
            int temp = this->bufMaxSize - this->readpos;
            temp = read(data, temp);
            this->readpos = 0;
            
            memmove((char*)data + temp, (char *)this->buffer, dataLen - temp);
            // printf("\n读取位置: %d ,读取信息 len：%d, data:%s\n", this->readpos, dataLen, (char *)data);
            this->readpos = this->readpos + dataLen - temp;
            this->bufLen = this->bufLen - (dataLen - temp);
            ret = dataLen;
        }
    }
    return ret;
}