Malloc和free

Question

我在寻求帮助加速一些我正在修改的代码。

其余的代码，以及我的“基准”，都可以找到这里。

#ifndef LALLOC_H
#define LALLOC_H

#define PAGESIZE (1048576)

#include <stdbool.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <errno.h>

typedef struct bblk bblock;
typedef bblock* bb;
struct bblk {
    size_t ind;
    bb next;
    size_t occ;
    char mem[PAGESIZE - (sizeof(size_t) + sizeof(bb) + sizeof(size_t))];
} __attribute__((packed));

typedef struct smmblk memblock;
typedef memblock* mb;
struct smmblk {
    mb prev;
    mb next;
    void* end;
    bb bblk;
    bool free;
} __attribute__((packed));

size_t bbhdr = (sizeof(size_t) + sizeof(bb) + sizeof(size_t));

bb first;

/**
 * @author Lev Knoblock
 * @notice Allocates a 'big block' of memory using mmap and inserts 1 'small block' into it
 * @dev Consider moving away from 1 page of memory. Maybe larger blocks would be better.
 * @param
 * @return bblk *
 */
bb bbinit() {
    bb out = mmap(NULL, PAGESIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE, -1, 0);
    if (out == MAP_FAILED) {
        printf("%s", sys_errlist[errno]);
        exit(40);
    }

    /* Big blocks are appended to an append-only linked list.
     * Since initially all memory in the block is free, the
     * occupancy is set to 0 */
    out->next = NULL;
    out->occ = 0;

    mb t = (mb) out->mem;
    /* The internal small block has no predecessors or
     * successors, but spans the full block width */
    t->prev = NULL;
    t->next = NULL;
    t->end = out->mem + (PAGESIZE - (sizeof(size_t) + sizeof(bb) + sizeof(size_t)));
    t->free = true;
    t->bblk = out;
    return out;
}

/**
 * @author Lev Knoblock
 * @notice Allocates a slice of memory by creating an appropriately sized small block in a big block
 * @dev Well its somehow slower than the prototype and I swear I knew what was making that one slow
 * @param 'big block' to allocate from, size of slice
 * @return void* to memory, or NULL if no space was found.
 */
static void* bblkalloc(bb blk, size_t size) {
    mb sb = (mb) blk->mem;
    /* Find the first free small block */
    while (1) {
        if (sb->free) break;
        tryGetNext:;
        if (sb->next == NULL) {
            /* Reached end of big block */
            return NULL;
        }
        sb = sb->next;
    }

    /* Remaining space in small block */
    size_t frsize = sb->end - (((void*)sb) + sizeof(memblock));

    /* If there isn't enough space to fit a new small block
     * find another block that will fit one */
    if (frsize < (size + sizeof(memblock))) {
        goto tryGetNext;
    }

    /* Initialize the new small block by stealing
     * space from the end of the 'current' small block */
    mb nsb = sb->end - (sizeof(memblock) + size);
    nsb->prev = sb;
    nsb->next = sb->next;
    nsb->end = sb->end;
    nsb->free = false;
    nsb->bblk = blk;

    /* Append new small block to list */
    sb->end = nsb;
    if (sb->next != NULL) sb->next->prev = nsb;
    sb->next = nsb;

    sb->bblk = blk;
    blk->occ++;
    /* Return pointer past allocation header */
    return ((void*)nsb) + sizeof(memblock);
}

/**
 * @author Lev Knoblock
 * @notice Allocates a slice of memory from the memory pool
 * @dev Currently has no functionality for reducing number of big blocks.
 * @param size of slice
 * @return void*
 */
void* lalloc(size_t size) {
    void* out;
    bb curr = first;
    unsigned int ind = 0;
    do {
        if (curr == NULL) {
            /* If current big block is null, set it up with its first small block */
            curr = bbinit();
            curr->ind = ind;
            if (ind == 0) first = curr;
        }
        /*
        if (curr->occ) {
            curr = curr->next;
            ind++;
            continue;
        }
         */
        out = bblkalloc(curr, size);
        /* If allocation fails go to the next big block (and allocate it if necessary)
         * otherwise, return the valid pointer */
        if (out != NULL) return out;
        //curr->occ = 1;
        curr = curr->next;
        ind++;
    } while (1);
}

/**
 * @author Lev Knoblock
 * @notice Frees a slice of memory from the memory pool
 * @dev Not really sure how to optimize further.
 * @param void* to slice
 * @return
 */
void lfree(void* a) {
    /* Decrement pointer to get to begining of header */
    mb sb = a - sizeof(memblock);
    sb->free = true;

    if (sb->prev != NULL && sb->prev->free) {
        /* If previous block exists and is free, extend it
         * to wrap over this one and remove pointers to
         * this block header */
        sb->prev->end = sb->end;
        sb->prev->next = sb->next;
        if (sb->next != NULL) sb->next->prev = sb->prev;

        /* Replace block pointer on stack */
        sb = sb->prev;
    }

    if (sb->next != NULL && sb->next->free) {
        /* If next block exists extend current one over
         * it and scrub pointers to it */
        sb->end = sb->next->end;
        sb->next = sb->next->next;
        if (sb->next != NULL) sb->next->prev = sb;
    }

    /* Decrement occupancy */
    sb->bblk->occ--;
}

#endif

Answer 1

变量联动

bb first;

好像在头文件里。这意味着每次您从不同的模块中包含它时，都会用它自己的单独地址重新声明它。这不可能是你想要的。相反，声明它为extern，然后在C文件中定义它一次。

除此之外，为什么要在标题中声明它呢？这是一个不应该向用户公开的实现细节。

此外，看起来绝对所有的东西--包括你的功能体--都在头上。也许您的理论是，内联所有的东西产生的代码比有一个更标准的.c/.h布局更快。如果这个库作为一个. to /..dll包含在另一个项目中，那么有一些非零的可能性是这样的，但是如果这个库包含在源代码中，并且包含了具有整个程序优化功能的任何类型的自重编译器，那么这个机会就会降到零。基本上，我会考虑这种过早的优化，如果有一个分离的.c来更好地隔离您的设计和减少代码重声明是值得的，我会感到惊讶。

嵌套包括

这些：

#include <stdbool.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <errno.h>

需要削减到只需要声明lalloc.h中的符号所必需的内容。errno绝对可以删除；stdbool不能；其他的我也不确定。裁剪后的包含将被移动到.c。

stderr

    printf("%s", sys_errlist[errno]);

很可能会被fprintf编辑成stderr。另外，fprintf也不是必需的；您可以使用puts/fputs。

神秘错误码

    exit(40);

应该得到一个#define。

是的，goto实际上是糟糕的

这是：

while (1) {
    tryGetNext:;
    // ...
}

if (frsize < (size + sizeof(memblock))) {
    goto tryGetNext;
}

只是演示了您的while还没有足够地捕捉到实际正在循环的内容。外部循环应该包含到这个goto的所有东西；现有的while应该变成一个内环，goto应该消失。

一个例子是：

size_t frsize;
do {
    while (!sb->free) {
        if (sb->next == NULL) {
            /* Reached end of big block */
            return NULL;
        }
        sb = sb->next;
    }

    /* Remaining space in small block */
    frsize = sb->end - (((void*)sb) + sizeof(memblock));

    /* If there isn't enough space to fit a new small block
     * find another block that will fit one */
} while (frsize >= size + sizeof(memblock));

这并不是完全等效的，因为在原始版本中，在某些条件下跳过了free检查。我不清楚这是否是个问题。

指针数学

size_t frsize = sb->end - (((void*)sb) + sizeof(memblock));

看起来有点尴尬。你能不能不只是：

size_t frsize = (sb->end - sb - 1)*sizeof(memblock);

我感到惊讶的是，原来的版本--减去非无效和无效指针--甚至被允许。

Forever-loops

你混合风格：

do { } while (1);

while (1) { }

我也不爱。对我来说最清楚的通常是while (true) { }，考虑到您有stdbool，这是可能的。

在第一种情况下，它实际上不应该是一个while循环；

unsigned int ind = 0;
do {
    ind++;
} while (1);

我觉得会更干净

for (unsigned int ind = 0;; ind++)