我自己的小内存管理器

Question

我实现了malloc()及其相关函数free()、calloc()和realloc()的一个简单版本。

• 当调用free()时，我的实现只是将这个内存放在自己的内部空闲列表中。
• 当调用malloc()时，它首先检查内部空闲列表。只有当内存不可用时，它才会调用sbrk()请求另一个块。
• 所有的块大小都是基于2的幂。
• 最佳匹配策略用于从自由列表中分配。

请您回顾一下，并让我知道您的建议/意见？

#include <stdio.h>
#include <unistd.h>
#include <string.h>

// a struct representing a memory block
struct memoryBlock {
    // metadata about memory block
    size_t size;
    struct memoryBlock *next;
};

// function declarations
void* malloc(size_t);
void free(void*);
void* calloc(size_t, size_t);
void* realloc(void*, size_t);
struct memoryBlock* mymemcpy(void*, const void*, size_t);
void fuse_adjacent_freeBlocks();
size_t round_to_next_power_of_two(unsigned int);
struct memoryBlock* get_bestFit_freeBlock(size_t size);
void print_freelist();

struct memoryBlock head = { 0, 0 };

/* This function allocates a block of memory of size bytes. */
void* malloc(size_t size) {

    //If size is zero or less, return NULL
    if (size <= 0) {
        return NULL;
    }

    struct memoryBlock *p = head.next;

    size = round_to_next_power_of_two(size + sizeof(struct memoryBlock));

    // when free-list is empty, No freelist traversal, just sbrk and return the pointer
    if (p == NULL) {

        p = (struct memoryBlock*) sbrk(size);
        p->size = size;

        return ((char*) p) + sizeof(struct memoryBlock);
    }

    // traverse the free-list for a best-fit, if found return it
    p = get_bestFit_freeBlock(size);
    if (p != NULL) {
        return ((char*) p) + sizeof(struct memoryBlock);
    }

    // reached only if best-fit not found, sbrk and return

    p = (struct memoryBlock*) sbrk(size);
    p->size = size;
    return ((char*) p) + sizeof(struct memoryBlock);
}

/* This function frees a block of memory that had previously been allocated. */
void free(void *ptr) {

    // If ptr is NULL, this function does nothing, just RETURNs
    if (ptr == NULL) {
        return;
    }

    struct memoryBlock *to_free = (struct memoryBlock*) (((char*) ptr)
            - sizeof(struct memoryBlock));

    struct memoryBlock *p = head.next;

    // if free-list is empty, insert and return
    if (p == NULL) {
        head.next = to_free;
        to_free->next = NULL;
        return;
    }

    // try to insert at the appropriate location, fuse and return
    for (p = head.next; p->next != NULL; p = p->next) {
        if ((p < to_free) && (to_free < p->next)) {
            to_free->next = p->next;
            p->next = to_free;
            fuse_adjacent_freeBlocks();
            return;
        }
    }

    // last resort - insert at the end of free-list
    p->next = to_free;
    to_free->next = NULL;

    // coalesce
    fuse_adjacent_freeBlocks();
}

/* This function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. */
void* calloc(size_t nmemb, size_t size) {

    //If nmemb or size is 0, then returns NULL
    if ((nmemb == 0) || (size == 0)) {
        return NULL;
    }

    size_t actualSize = nmemb * size;

    void *p = malloc(actualSize);

    // zero the memory location
    char *d = (char*) p;
    for (size_t i = 0; i < size; i++) {
        d[i] = 0;
    }

    return p;
}

/* realloc() changes the size of the memory block pointed to by ptr to size bytes. */
void* realloc(void *ptr, size_t size) {

    size_t actulSize = round_to_next_power_of_two(
            size + sizeof(struct memoryBlock));

    // If ptr is NULL, then the call is equivalent to just calling malloc(size) for all values of size.
    if (ptr == NULL) {
        return (malloc(size));
    }

    //if size is equal to zero, and ptr is not NULL, then
    if ((size == 0) && (ptr != NULL)) {
        free(ptr);
        return NULL;
    }

    struct memoryBlock *p = (struct memoryBlock*) (((char*) ptr)
            - sizeof(struct memoryBlock)); //move the pointer back by sizeof(struct FreeList) to make it overlap properly

    // if the new size is equal to the existing size of the block, then just return the ptr as is
    if (actulSize == p->size) {
        return ptr;
    }

    // if the new size is less than the existing size of the block, split it.
    // can be split only if the resulting block is of size - power of 2, if not then we allocate a new block (after this IF)
    if (actulSize < p->size) {

        size_t size_difference = p->size - actulSize;
        if ((size_difference > sizeof(struct memoryBlock))
                && (size_difference
                        >= round_to_next_power_of_two(size_difference))) {

            p->size = actulSize;

            struct memoryBlock *return_to_freelist =
                    (struct memoryBlock*) (((char*) p) + p->size);
            return_to_freelist->size = size_difference;
            return_to_freelist =
                    (struct memoryBlock*) (((char*) return_to_freelist)
                            + sizeof(struct memoryBlock));
            free(return_to_freelist);

            return ((char*) p) + sizeof(struct memoryBlock);
        }

    }

    // reached when neither of the cases were satisfied , and allocating a new block is the option left
    // Allocate a new block  to accommodate the new size, copy the contents to the new block and free the old block
    struct memoryBlock *reallocedBlock = malloc(size);

    // If malloc returns NULL
    if (reallocedBlock == NULL) {
        return NULL;
    }

    // Copy contents from old location to the new one
    if (actulSize > p->size) {
        mymemcpy(reallocedBlock, (((char*) p) + sizeof(struct memoryBlock)),
                (p->size - sizeof(struct memoryBlock)));

    } else if (actulSize < p->size) {
        mymemcpy(reallocedBlock, (((char*) p) + sizeof(struct memoryBlock)),
                size);
    }

    // Free the old block
    free(ptr);
    return reallocedBlock;

}

struct memoryBlock* mymemcpy(void *dest, const void *src, size_t len) {

    char *d = (char*) dest;
    const char *s = (char*) src;

    for (size_t i = 0; i < len; i++) {
        d[i] = s[i];
    }
    return (struct memoryBlock*) d;
}

/* auxillary function to print the free list, meant for debug purpose only */
void print_freelist() {

    char msg_buf[100];

    sprintf(msg_buf, "\t(%s) ", __func__);
    write(2, msg_buf, strlen(msg_buf));

    struct memoryBlock *p = head.next;

    if (p == NULL) {
        sprintf(msg_buf, "Free list is empty!!\n");
        write(2, msg_buf, strlen(msg_buf));

        return;
    }

    sprintf(msg_buf, "Free-List: ");
    write(2, msg_buf, strlen(msg_buf));

    for (p = head.next; p != NULL; p = p->next) {
        sprintf(msg_buf, "[%lu](%p) --> ", p->size, (void*) p);
        write(2, msg_buf, strlen(msg_buf));

    }
    sprintf(msg_buf, " %p\n", (void*) p);
    write(2, msg_buf, strlen(msg_buf));

}

/* Merges two adjacent free blocks into a single, contiguous free block. */
void fuse_adjacent_freeBlocks() {

    struct memoryBlock *p;

    // merge until no more merges possible, 2 passes are enough
    for (int i = 0; i < 2; i++) {
        for (p = head.next; p != NULL; p = p->next) {

            if (p->next != NULL) {

                if (((((char*) p) + p->size) == (char*) p->next)
                        && (p->size == p->next->size)) { // check contiguity & equality of size

                    p->size = p->size + p->next->size; // update the size
                    p->next = p->next->next; // merge
                }
            }
        }
    }
}

/* Given a size, returns the best-fit block from the free-list */
struct memoryBlock* get_bestFit_freeBlock(size_t size) {

    struct memoryBlock *bestFit_freeBlock = NULL;

    // set the minumum to the size difference with the first free block in the free-list
    size_t minimum = head.next->size - size;

    struct memoryBlock *p = head.next;
    struct memoryBlock *trail_p = &head;

    for (p = head.next; p != NULL; p = p->next) {
        if (p->size >= size) {
            // exact size best-fit
            if (p->size == size) {

                bestFit_freeBlock = p;
                trail_p->next = p->next; // unlink p
                return bestFit_freeBlock; // no further search needed, a kind of optimization.
            } else if ((p->size - size) <= minimum) {
                // check if OK to split
                if (((p->size - size) > sizeof(struct memoryBlock))
                        && ((p->size - size)
                                >= round_to_next_power_of_two(p->size - size))) {
                    minimum = p->size - size;
                    bestFit_freeBlock = p;
                }
            }
        }
        trail_p = p; // trail p, useful while unlinking
    }

    // reached if best-fit found by splitting (i.e not by exact size match)
    if (bestFit_freeBlock != NULL) {
        bestFit_freeBlock->size = bestFit_freeBlock->size - size;

        bestFit_freeBlock = (struct memoryBlock*) (((char*) bestFit_freeBlock)
                + bestFit_freeBlock->size);
        bestFit_freeBlock->size = size;
    }

    return bestFit_freeBlock;
}

// code for below function was taken from https://graphics.stanford.edu/~seander/bithacks.html
size_t round_to_next_power_of_two(unsigned int v) {

    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;

    return v;
}

Answer 1

1. 您应该将声明分为三个部分：
   1. 公共接口。malloc calloc realloc free
   2. 调试接口。print_freelist
   3. 实现的详细信息，不应放在标头之外。(其余部分，考虑静态链接)

2. 避免不必要的铸造。每一个演员都是一个可能的麻烦点。
3. 在允许的地方使用标准库。不用自己造方向盘。
4. 评论为什么，而不是什么。后者已经在代码中表达得更好了。
5. 将合同放在声明的旁边，而不是definition. --特别是您的malloc/realloc --应该提到它们总是失败--0大小的request.和realloc是一个特别麻烦的野兽。(考虑阅读手册或C标准)
6. 有很多地方你冒着沉默的包袱。小心点！并将整块计算打包到自己的功能中。静态size_t roundUpToPowerOfTwo(size_t v) { //见https://graphics.stanford.edu/~seander/bithacks.html v-；v |= v >> 1；v |= v >> 2；v |= v >> 4；v |= v >> 8；v |= v >> 16；返回v+ 1；静态size_t getBlockSize(size_t v) { //拒绝过大的请求，如果(v> (size_t)-1 /2+1- sizeof(struct memoryBlock))返回(size_t)-1；v += sizeof(struct memoryBlock)；返回roundUpToPowerOfTwo(v)；}
7. 您的malloc包含不必要的重复，并且无法检查sbrk是否成功。考虑这一点:void(size_t大小){ //故意失败0大小请求，仅仅因为if (! size )返回NULL；struct memoryBlock *p；size= getBlockSize( size)；//尝试重用旧分配if (head.next & (p =get_bestFit_freeBlock(Size)返回p+ 1；//尝试获得新内存，如果(Intptr_t)size)<0而外(p = sbrk(size)) == (void*)-1)返回NULL；p->size = size；返回p+ 1；}
8. calloc必须检查乘法是否溢出。此外，它还必须检查malloc的故障。void* calloc(size_t nmemb，size_t size) { //拒绝环绕和0-请求size_t actualSize = nmemb * size；if(!size / size != nmemb)返回空；void *p = malloc( actualSize )；if(p) memset(p，0，actualSize)；返回p；}
9. 为什么不在fprintf(stderr, ...)中使用print_freelist呢？
10. 考虑重写您的代码，以便您的块总是自然地对齐，以便更好地拆分和融合。

Answer 2

简化块分裂

根据注释，只有2倍于请求大小的块才能被拆分，因为所有块必须保持2大小的幂。当前，您的块拆分函数搜索所有块，保持minimum大小，尽管最小大小必须始终是size。这确实令人困惑，因为它使您看起来像是在允许任意块大小被分割。我会像这样重写您的get_bestFit_freeBlock()函数：

/* Given a size, returns the best-fit block from the free-list */
struct memoryBlock* get_bestFit_freeBlock(size_t size) {

    struct memoryBlock *doubleSize_freeBlock = NULL;
    struct memoryBlock *p                    = NULL;
    struct memoryBlock *prev                 = &head;

    for (p = head.next; p != NULL; p = p->next) {
        if (p->size == size) {
            // Exact size best-fit.  Unlink and return block.
            prev->next = p->next;
            return p;
        } else if (p->size == 2 * size && doubleSize_freeBlock == NULL) {
            // Found first size * 2 block.
            doubleSize_freeBlock = p;
        }
        prev = p;
    }

    // Reached if no exact size match was found.
    if (doubleSize_freeBlock != NULL) {
        struct memoryBlock *ret = (struct memoryBlock *)
                                    (((char*) doubleSize_freeBlock) + size);

        ret->size                  = size;
        doubleSize_freeBlock->size = size;
        return ret;
    }

    return NULL;
}

也可以对realloc()进行类似的更改。

不需要的size_t到int转换

您的舍入函数如下所示：

size_t round_to_next_power_of_two(unsigned int v);

您应该使用size_t v，因为无论您在哪里调用round_to_next_power_of_two()，都会传递一个size_t作为参数。实际上，如果您在一个具有16位int和32位size_t的目标上，那么当您传递大于32 in的大小时，您将返回0。

冗余码

在malloc()中，您有以下代码：

//当空闲列表为空时，没有自由职业者遍历，只返回sbrk并返回指针if (p == NULL) {p= (struct memoryBlock*) sbrk(size)；p->size = size；返回(char*) p) +size if(Struct MemoryBlock)}；

您可以删除这段代码，因为如果空闲列表为空，get_bestFit_freeBlock()将返回NULL，并且您将对sbrk()执行相同的低几行调用。

在realloc()中，您有以下检查：

//if大小等于零，ptr不为空，则if ((size == 0) & (ptr != NULL)) {

您可以简化为：

// if size is equal to zero
if (size == 0) {

因为您已经检查并处理了上面的空指针情况。

使用memset()

在calloc()中，可以使用以下代码对返回的块进行零设置：

//零内存位置char *d = (char*) p；for (size_t i= 0；i< size；i++) { d我 = 0；}

您应该直接调用memset()，因为memset()被优化为尽可能快。

memset(p, 0, size);

另外，您应该使用memcpy()而不是mymemcpy()。

融合相邻块

在fuse_adjacent_blocks()中，使用两次传球。我认为这还不足以保证工作的完成。假设您的空闲块列表如下所示(其中所有块都相邻)：

1024 -> 512 -> 256 -> 128 -> 64 -> 64 (just added)

在第一遍中，您将合并两个64字节块：

1024 -> 512 -> 256 -> 128 -> 128

在第二次访问中，您将合并两个128个字节块：

1024 -> 512 -> 256 -> 256

还需要3次传递才能将该列表完全合并到一个2048字节块中。我认为，如果您跟踪每个"run“的开始，其中"run”由block -> block/2 -> block/4 -> ...组成，您可以在一次传递中做到这一点。如果" run“以一对相同大小的块结尾，那么您可以将从运行开始到结束的所有块合并(如上面的示例所示)。

小事情

在calloc()中，您不检查nmemb * size是否溢出。另外，您也不需要检查malloc()是否返回NULL。

在malloc()中，您可以执行以下检查：

//If size is zero or less, return NULL
if (size <= 0) {
    return NULL;
}

但真的应该是

//If size is zero, return NULL
if (size == 0) {
    return NULL;
}

因为size_t没有签名。

在realloc()中，变量actulSize应该拼写为actualSize。

在realloc()中，您的代码非常可能分配与以前相同大小的块并复制到它，而不仅仅是返回原始块。此外，您可以分配一个新的一半大小的块，而不是把原来的块切成两半。这是因为检查这些特殊“重用”情况的代码只有在新请求的大小恰好是正确的大小(幂为2)时才成功。在执行这些检查时，应首先将新请求的大小整整为2，以便在可能的情况下重用当前块。

Answer 3

我的两分钱。在realloc()中，只要((char*) p) + sizeof(struct memoryBlock);是冗余的，就用ptr替换它，因为p是从ptr派生的。

struct memoryBlock *p = (struct memoryBlock*) (((char*) ptr)
        - sizeof(struct memoryBlock));

此外，还可以将初始if验证移到size_t actulSize = round_to_next_power_of_two(size + sizeof(struct memoryBlock));之前的顶部