c - 现在实现平板分配器值得吗？

Question

我正在使用必须读取同时连接的数千个套接字客户端的服务器。客户端请求由具有大约32个字节的所有相同确切大小的消息构成。

我正在阅读有关slab allocator的信息，当我调用read从套接字中获取数据时，我想在我的应用程序中使用此特殊技术(read将数据从内核缓冲区复制到我选择的缓冲区中，我想使用一些动态分配的内存)。

在我阅读本文时，似乎Linux内核已经在使用这种技术。如果将其用于实现malloc or new，鉴于分配已经有效，我仍然值得这样做吗？

我当时在想，通过在没有SLAB算法的情况下在堆栈上使用分配可能会更好，但是我不确定哪种方法是最好的。

Answer 1

如果您是C程序员，那么您当然应该对内存管理有所了解!

但是，除非真正接近机器的极限，否则看起来不可能简单地通过malloc分配每个请求就不会遇到任何问题。但是我相信了解您的替代方案比相信某人的话要好。这里是一些需要考虑的想法。

静态数组

最简单的替代方法是使用单个全局请求槽数组，并跟踪正在使用的请求槽。这意味着静态限制了多少个请求，但是另一方面，这没有开销，也没有碎片的实际问题。只需将限制设置得很高。

这是一个示例实现。如果您不熟悉按位操作，可能会有些困惑，但要点是，我们还有一个额外的数组，每个请求插槽包含一个位(开或关)，用于指定该插槽是否正在使用。您可以改为向结构本身添加“is_used”变量，但这最终会使结构填充多于一个位，这不利于我们将开销降至最低的目标。

头文件非常小(顺便说一下，这是C的真正美丽!):

typedef struct request_s {
  /* your 32 bytes of information */
  unsigned char data[32];
} request_t;

request_t *alloc_request(void);
void free_request(request_t *req);

源文件:

#include the header file

/* note: this example is not written with multithreading in mind */

/* allow a million requests (total 32 MB + 128 KB of memory) */
#define MAX_REQUESTS (1*1024*1024)

static request_t g_requests[MAX_REQUESTS];

/* use one bit per request to store whether it's in use */
/* unsigned int is 32 bits. shifting right by 5 divides by 32 */
static unsigned int g_requests_used[MAX_REQUESTS >> 5];

request_t *alloc_request(void) {
  /* note: this is a very naive method. you really don't want to search
   * from the beginning every time, but i'll leave improving that as an
   * exercise for you. */
  unsigned int word_bits;
  unsigned int word, bit;

  /* look through the bit array one word (i.e., 32 bits) at a time */
  for (word = 0; word < (MAX_REQUESTS >> 5); word++) {
    word_bits = g_requests_used[word];

    /* we can tell right away whether the entire chunk of 32 requests is
     * in use, and avoid the inner loop */
    if (word_bits == 0xFFFFFFFFU)
      continue;

    /* now we know there is a gap somewhere in this chunk, so we loop
     * through the 32 bits to find it */
    for (bit = 0; bit < 32; bit++) {
      if (word_bits & (1U << bit))
        continue; /* bit is set, slot is in use */

      /* found a free slot */
      g_requests_used[word] |= 1U << bit;
      return &g_requests[(word << 5) + bit];
    }
  }

  /* we're all out of requests! */
  return NULL;
}

void free_request(request_t *req) {
  /* make sure the request is actually within the g_requests block of
   * memory */
  if (req >= g_requests && req < g_requests + MAX_REQUESTS) {
    /* find the overall index of this request. pointer arithmetic like this
     * is somewhat peculiar to c/c++, you may want to read up on it. */
    ptrdiff_t index = req - g_requests;

    /* reducing a ptrdiff_t to an unsigned int isn't something you should
     * do without thinking about it first. but in our case, we're fine as
     * long as we don't allow more than 2 billion requests, not that our
     * computer could handle that many anyway */
    unsigned int u_index = (unsigned int)index;

    /* do some arithmetic to figure out which bit of which word we need to
     * turn off */
    unsigned int word = u_index >> 5; /* index / 32 */
    unsigned int bit  = u_index & 31; /* index % 32 */

    g_requests_used[word] &= ~(1U << bit);
  }
}

(是的，是的，您可以编写 index / 32而不是 index >> 5，依此类推，编译器会为您进行优化。但这对我来说并不对劲……)

您可以深入研究，并在优化分配器的空闲插槽搜索方面变得很有创意。一个简单的想法是从最后一个分配的位置开始搜索，并在结束时回绕。

这种方法有很多好处，但有一个很大的缺点:限制。您可能希望将限制设置为高于您希望一次拥有的最大请求数。但是，如果您能够做到这一点，那么您可能并没有违反系统的限制，那么为什么您首先来这里？

内存池(静态数组的链接列表)

如果您不喜欢静态限制，则可以批量分配。保留一个内存“池”的链接列表，每个池包含一定数量的固定请求槽。如上所述，每个单独的池基本上都是静态数组。如果所有现有池都已满，我们将分配一个新池并将其添加到链接列表中。一个池基本上看起来像这样:

#define REQUESTS_PER_POOL 1024

typedef struct request_pool_s request_pool_t;

struct request_pool_s {
  request_t requests[REQUESTS_PER_POOL];

  unsigned int requests_used[REQUESTS_PER_POOL >> 5];

  request_pool_t *prev;
  request_pool_t *next;
};

您将希望能够在流量中断时释放池，否则这与静态限制几乎没有什么不同!不幸的是，在这种情况下，您将要处理碎片问题。您可能会发现自己拥有大量稀疏使用的池，尤其是如果请求有时可能持续很长时间的情况下。直到整个池的最后一个插槽为空，才能释放整个池。您仍然可以节省开销(考虑到单个请求的大小)，但是处理碎片可能会使它从一个小巧，优雅的解决方案变成更多的工作，而不是值得的。

您可以减少每个池的请求数以减少碎片的影响，但是到那时，我们将失去这种方法的优势。

哪一个？

首先，您应该考虑完全替代单个malloc的主要原因是:结构的小尺寸(32字节)，大量的结构以及它们创建和销毁的频率。

静态数组可以大大减少开销，但是在当今这个时代很难证明这一点。除非您的服务器在Arduino上运行。

内存池是解决此类问题的明显方向，但它们可能需要大量工作才能顺利进行。如果这是你的小巷，那我就说吧。

Slab分配器就像复杂的内存池一样，不限于特定的单个结构大小。因为您只有32字节的请求，所以它们对您来说太过分了，尽管也许您可以找到适合您的第三方库。

采取简单的方法，简单地对每个请求进行malloc分配是一个滑坡，最终可能会导致您完全放弃C。 ;)