关于大容量快速路径代码中使用的零拷贝内存分配器的设计

reos 发布于 2019-11-10 c 最后更新 2019-11-10 12:10 104 浏览

免责声明:除非您是嵌入式程序员,内核开发人员或高性能系统软件程序员,否则请不要费心阅读这篇长篇文章。它是关于内存分配器的,可能对您没有任何兴趣。 我正在使用特定于操作系统的管道(Windows上的命名管道和UNIX上的UNIX域套接字)构建用于高容量高性能相同机器IPC的库。库接收消息,并将它们注入到处理引擎中,并且该引擎可以在C++或Erlang或Lua之类的相同进程中,或者可能移到中央机器上。 目前的消息来自Web服务器并且是HTTP请求的解析流程的一部分,并且应该与Web服务器一起扩展 - 即,我不能编写低效系统,因为Web服务器工作线程依赖他们可以卸载这些消息的速度。如果一个Web服务器能够处理10k个静态页面请求,那么这个IPC机制不应该大大妨碍它。 数据以类型消息的形式出现,我相信他们将拥有自己的大小统计数据,可以利用它们。如果我没记错的话,Doug lea的分配器会根据大小创建桶的链表,也许这就是我应该去的方式 - 它是一般分配器的标准。 我想要零拷贝语义,所以直到消息完成处理它不应该被复制。另一方面:由于有线格式与内存中对象格式不同,因此可能需要Googles协议缓冲区(目前无法确定)。我将进一步调查 - 我目前的实现使用我自己的IPC格式;也许有人对协议缓冲区的工作方式有一些看法,它是否在内部使用零拷贝? 我想在应用程序的所有区域中使用此分配器。我对网络堆栈软件的研究正在催促我选择基于处理器页面对齐池的分配器;我的应用程序肯定具有相同的访问语义。我会将所有消息复制到页面中,只有在所有元素引用(分配给池)处于非活动状态时才会回收页面。 要稍微形式化并帮助您理解我正在考虑的内容,请考虑以下数据结构:

typedef struct _page
{
   int active_elements;            // page is returned to empty pool at zero
   int free_bytes;                 // used to sort the pages
   void * next_free_contigious;    // pointer to where next allocation may occur
   _page * next_page;              // linked list next page pointer
} page;

struct pageAllocator { page ll_empty; // completely empty pages page ll_active; // sorted by highest_size_available, could be binary tree // continue reading for rationale. };

一些要点是:

  1. 这些消息不会徘徊。所以页面很快就会免费。
  2. 我需要编写防弹代码来释放页面。
  3. 我不知道page-> next_free_contigious是否需要单词排列。
  4. 我认为在压力下分配的页面数量会稳定。
  5. 我应该将页面返回到操作系统还是应该保留它们?一旦确定最大压力,最大压力将仅根据需要分配。
  6. 我应该将消息分配给大小排序列表中的第一个元素(首先是最高的),还是应该找到最匹配的页面。在这种情况下,我将不得不使用某种二叉树。我在这里重新实施道格算法吗?
我希望得到个人处理此类事情的建议,欢迎备用分配器建议。现成的库很棒(它们必须是ANSI-C或c-pre-processor元代码实现)。 APR是一个受欢迎的库,具有基于分层池的策略,但我不处理此低级别的会话,因此我不需要层次结构。 我认为我没有预先优化,因为我确信我需要它。我在Web服务器CPU饱和期间将此系统的当前实现跳转到30%的CPU,我知道这是因为我使用C++编写的新的和大量的复制构建应用程序的天真方式。在我继续之前,我将对我的应用程序进行基准测试(我太忙于重新构建测试环境),但无论结果如何,这里的任何讨论都将是有用的。 ---编辑1 --- 这个实现的灵感来自Markr的一些评论,请在下面查看答案进行讨论。更多的思考导致以下。 好的,我现在正在考虑循环缓冲区(比如1mb ^ x)。由大小相等的元素组成(可能是128字节的一些倍数)。分配逐渐发生直到结束(分配可能发生的allocatex-head(A)标记,以及标记有条件的自由区域(0)的自由标记(F)返回到池中。请考虑以下ASCII插图:
|000000F101110001111A00000000|
0 =自由,1 =被占用。 一些具体的是:
  • 自由标记划分自由连续区域。在图示中,当返回紧接的下一个块时,F将仅向前移动两个。
  • 一旦分配到达终点,或者末尾没有足够的空间来执行连续分配,分配头移动到开头;到目前为止,大部分缓冲区应该是免费的。
  • 一旦消息移动到其目的地,块就会立即返回缓冲区。
  • 在同一台机器上,消息将以短时间(一些阻塞)传递,或者如果它只需要一个无线程函数调用则立即传递。

评论会很好,如果有人知道任何类似的东西,我仍然会更喜欢一些自包含的便携式库。 GLIBC切片分配器看起来不错,但我相信上面的实现更简单,可能更快,缓冲区上的活动区域总是具有良好的局部性。
已邀请:

yeum

赞同来自:

在阅读其他人的评论之后,听起来像使用固定的对象池并分配它们的所有权可能比试图搞乱分配器更好。 大概你有大量的线程,所以任何分配器都需要进行相当多的锁定;大量小的alloc / frees听起来不受欢迎。 如果你认为你有足够的内存来为每个线程保留合理大小的池,你可以为每个线程分配一个固定池,其中包含足够的IPC对象来处理线程一次未完成的所有请求,并按以下方式分配它们来自此池的线程没有任何锁定,标记它们以便在请求完成后重用。 一旦你移开其他进程,问题就会变得完全不同,因为零拷贝不再是一个选项(数据显然需要至少复制一次以到达另一台机器)所以我认为你还有其他问题。

fet

赞同来自:

答:想想你想要达到的目标。

  • 处理邮件时是否需要零拷贝语义?
  • 或者你想要一个花哨的新uberfast内存分配器?
“零拷贝内存分配器”是无意义的! 编写通用内存分配器很困难(很可能默认分配器非常适合您的目的)。如果您需要为您的目的寻找好的分配器,那么请提供更多详细信息。 零复制的东西:它取决于你的应用程序中的许多其他东西,但是例如我假设一段代码从命名管道读取流,另一段代码解析此流,并将其解释为消息。 首先,从IPC管道读取:有一个缓冲区列表:read()从FIFO到buffers[current_write_buffer_idx].data+write_pos最多(buffer_size-write_pos)个字节。向write_pos添加读取字节数,依此类推。如果缓冲区已满,则检查缓冲区列表是否找到未使用的缓冲区(每个缓冲区保留一个使用标记)。如果未找到未使用的,则分配新缓冲区。在旧缓冲区上设置next_buffer_index(稍后用于“解析”)。 你最终得到:
size_t write_pos, read_pos;
struct Buffer {
    void* data;
    bool is_used;
    size_t number_bytes_written;
    size_t next_buffer_index;
};
Buffer *buffers;
size_t number_buffers;
size_t current_write_buffer_idx;
size_t current_read_buffer_idx;
其次,解析流:在buffers[current_read_buffer_index].data+read_pos找到下一个字节。您可以从该缓冲区读取字节,直到buffer.number_bytes_written字节,如果写入的字节数等于buffer_size(固定),则缓冲区已满,您必须继续读取next_buffer_index处的缓冲区... 等等。无论何时写入新缓冲区,都设置为is_used true,只要完成解析缓冲区,就将其设置为false。 “阅读”究竟意味着什么,取决于您的信息编码方式! 这么久......为了(几乎)零复制,你必须提供更多细节。当消息被修改时,它的大小太容易了。但是假设你的消息以类型和/或大小信息为前缀而消息的数据是某种结构,那么你可以执行以下操作:
  • 从流和...中读取类型和/或大小信息。
  • 如果邮件尚未完全收到(read_pos,number_bytes_written,...)则跳过...
  • 如果消息(现在已知大小)适合单个缓冲区,只需将指针放入此缓冲区(struct MsgXYZ*)( buffers[current_read_buffer_idx].data + start_of_message_index )并将其传递给作业中的任何代码
  • 如果消息确实产生了缓冲区,则创建一个临时缓冲区并将消息的各个部分复制在一起,将指针传递给代码..之后释放临时缓冲区(无论如何都是罕见的情况)
好吧,我在这里省略了很多细节;)如果零拷贝真的对你的应用有意义,请三思而后行。 从socket / pipe / ...读取时的零拷贝是不可能的,可能是通过某种mmap的共享内存,但不是管道。

wqui

赞同来自:

也许您正在寻找像GLib Slice Allocator这样的东西? 它专为高速分配和释放类似大小的对象而设计。它还声称在多线程环境中具有出色的性能。 可能给您带来麻烦的API的一个方面是您必须在解除分配和分配期间给出对象的大小。