malloc实施

Question

请给我一些反馈，我的malloc实现。我实现这个设计是为了理解这个基本概念。

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

#define HEAP_MEM_SIZE 150
#define MEMORY_AVAILABLE 1 
#define MEMORY_USED 0 

struct chunk_header {
  struct chunk_header *next; // next pointer on free list
  size_t size;               // the size of this chunk
  bool is_available;         // indicates if this chunk is MEMORY_AVAILABLE or MEMORY_USED
};

typedef struct chunk_header chunk_header;
chunk_header *chunk_header_begin;
static char buffer[HEAP_MEM_SIZE];
unsigned int heap_size;

void init() {
    heap_size = HEAP_MEM_SIZE;
    chunk_header_begin = (chunk_header*)&buffer;
    chunk_header_begin->next = NULL;
    chunk_header_begin->size = heap_size;
    chunk_header_begin->is_available = MEMORY_AVAILABLE;
}

void init_next_chunk(chunk_header *curr, unsigned int bytes) {
    heap_size -= bytes;
    curr->next = NULL;
    curr->size = heap_size;
    curr->is_available = MEMORY_AVAILABLE;
}

void *my_malloc(unsigned int nbytes) {
    static bool init_flag = false;

    if(!init_flag) {
        init();
        init_flag = true;
    }

    int alloc_size = nbytes + sizeof(chunk_header); 
    chunk_header *curr = chunk_header_begin;

    while(curr) {
        if(curr->is_available && curr->size >= alloc_size) {
            curr->is_available = MEMORY_USED;
            curr->size = alloc_size;
            curr->next = curr + alloc_size;

            init_next_chunk(curr->next, alloc_size);

            // return memory region
            curr = curr + sizeof(chunk_header);
            return curr;
        }

        curr = curr->next;
    }

    return NULL;
}

void my_free(void *firstbyte) {
    chunk_header *mem = (chunk_header*)firstbyte - sizeof(chunk_header);
    chunk_header *curr = chunk_header_begin;

    while (curr) {
        if (curr == mem) {
            heap_size += curr->size;

            // Mark the block as being available
            curr->is_available = MEMORY_AVAILABLE;
            break;
        }

        curr = curr->next;
    }

    firstbyte = NULL;
}

void print_heap_allocations() {
    chunk_header *curr = chunk_header_begin;

    printf("\n\tSize\tAvailable\tMemory-Ptr");

    while (curr) {
        void *mem_ptr = curr + sizeof(chunk_header);
        printf("\n\t%d\t%d\t\t%x", curr->size, curr->is_available, mem_ptr);
        curr = curr->next;
    }

    printf("\n");
}

int main() {
    char *mem1 = (char*)my_malloc(20); 
    if(mem1 == NULL) {
        goto err;
    }
        memset (mem1,'x',19); 
        mem1[19] = '\0'; 

        print_heap_allocations();

        char *mem2 = (char*)my_malloc(20); 
        if(mem2 == NULL) {
        goto err;
    }
        memset (mem2,'y',19); 
        mem2[19] = '\0'; 

        print_heap_allocations();

        char *mem3 = (char*)my_malloc(20); 
        if(mem3 == NULL) {
            goto err;
        }
        memset (mem3,'z',19); 
        mem3[19] = '\0'; 

        print_heap_allocations();

    my_free(mem2);

    print_heap_allocations();

    char *mem4 = (char*)my_malloc(20);
    if(mem4 == NULL) {
        goto err;
    } 
        memset (mem4,'a',20); 
    mem4[19] = '\0';

        print_heap_allocations();

        printf("should be 19 x sein: %s\n", mem1); 
        printf("should be 19 a sein: %s\n", mem4); 
        printf("should be 19 z sein: %s\n", mem3);

    return 0;

err:
        printf("could not allocate mem\n");
        return 0;
}

Answer 1

你做得很好：

• 一些评论的使用。
• typedef的使用。

您可以改进的东西：

Syntax/Styling:

• Never使用goto。

是的，有一些罕见的情况下，你可能会觉得有必要使用它。这不是他们中的一个。错误:printf(“无法分配mem\n")；返回0；正如您所看到的，您在这里的小代码块中所做的一切就是打印一个不特定的错误消息，然后退出(使用0，这意味着程序在这里是成功的，并且是矛盾的)。您应该完全取消goto's。打印特定的、有用的错误消息，然后用唯一的退出代码返回。if(mem2 == NULL) { fprintf(stderr，“将内存分配给mem2.n”)；返回-2；}

• 当您试图打印字符串时，您的格式指定了int类型，但是参数的类型是size_t (基本上是unsigned long)。您的格式还指定了unsigned int类型，但是参数具有void *类型。printf(“\n\t%d\t%x”，curr->size，curr->is_available，mem_ptr)；只需更改它们的类型，您就可以打印出来，并将mem_ptr转换为unsigned int。printf(“n%zuu\t%d\t%x”，curr->size，curr->is_available，(无符号int) mem_ptr)；
• 您没有在typedef struct中使用标准命名约定。结构chunk_header chunk_header；
  1. 您应该为typedef指定一个特定的名称，与抽象的struct名称不同。
  2. 您应该将类型的名称大写，或者在末尾添加一个_t (尽管这是POSIX中保留的)

• typedef你的structs，当你宣布他们。struct chunk_header { struct chunk_header * next；// next指针关于空闲列表size_t大小；//此块的大小为is_available；//指示此块是MEMORY_AVAILABLE还是MEMORY_USED }；typedef结构size_t chunk_header；typedef表示不再需要在所有地方写入struct，因为您已经使用过它。但是您可以将这两个部分组合在一起，使事情变得更简单: this struct chunk_header { struct chunk_header * next；// next指针关于空闲列表size_t大小；//这个块的大小是is_available；//指示这个块是MEMORY_AVAILABLE还是MEMORY_USED } ChunkHeader；
• 您可以简化NULL检查。如果(mem1 == NULL)由于NULL被定义为(void *)0，我们可以将其视为与0的比较。如果(！mem1)

Parameters/Returns:

• 对于某些函数，例如main()，您不接受任何参数。如果不接受任何参数，请将它们声明为void。int main(void)
• 您仍然应该从一个函数中return，即使它被声明为return void。void my_free(void-1字节){.返回；}

Compilation:

• 我从收到的一些警告中可以看出，您没有启用所有编译器警告，这是您应该做的。

Answer 2

如果没有chunk_header_begin和heap_size作为全局变量，我会发现它更整洁:相反，假设chunk_header_begin位于&buffer[0]，并假定堆大小由几个chunk_header->size值定义。

我担心的是，当您重新分配内存时会发生什么:在我看来，实现是不正确的。

我对curr + sizeof(chunk_header);这样的语句有困难:如果curr是char*类型，那么curr+3就意味着“超过curr的3个字符”；但是当curr是chunk_header *类型时，curr+3就意味着“超过curr的3个块头”，所以curr + sizeof(chunk_header);的意思是“curr之后的sizeof(chunk_header)*sizeof(chunk_header)字符”，这不是您想要的。

海事组织应改进单元测试/断言，以验证：

• 接下来是给定大小的预期位置。
• 所有大小值(加上相应块头的大小)之和与堆的总大小相匹配。

传统的做法是在每个块头的开头和末尾添加一些神奇的数字，例如0x死牛肉：

struct chunk_header {
  int magic_start;           // 0xdeadbeef 
  struct chunk_header *next; // next pointer on free list
  size_t size;               // the size of this chunk
  bool is_available;         // indicates if this chunk is MEMORY_AVAILABLE or MEMORY_USED
  int magic_end;             // 0xdeadbeef
};

• 在创建块头时初始化神奇的数字
• 在使用块头时断言神奇的数字
• 这将有助于检测任何使用错误指针算法的人覆盖的块头。

您还可以将一些神奇的字节值(例如0xa3)写入所有空闲/未使用的内存块中，然后(当您遍历未分配块的列表时)验证/断言，因为没有人重写过这些字节值。

为了避免碎裂，一些堆管理器使用另一种算法：例如，有一个32字节块的列表和另一个256个字节块的列表；如果您请求43个字节，那么您将得到256个字节块中的一个。

我认为您的malloc实现应该更像这样：

void *my_malloc(unsigned int nbytes) {
    static bool init_flag = false;

    if(!init_flag) {
        init();
        init_flag = true;
    }

    int alloc_size = nbytes + sizeof(chunk_header); 
    chunk_header *curr = chunk_header_begin;

    while(curr) {
        if(curr->is_available && curr->size >= alloc_size) {
            // we will use this chunk
            curr->is_available = MEMORY_USED;
            // is it big enough that we can split it into two chunks
            // i.e. use the start of this chunk and create a new free chunk afterwards?
            size_t min_chunk_size = sizeof(chunk_header) + 1; // big enough to allocate 1 byte
            if (cur->size - alloc_size >= min_chunk_size)
            {
                // yes so create a new chunk ...
                // ... new chunk is smaller than this one
                size_t new_size = cur->size - alloc_size;
                // ... new chunk is a few bytes beyond this one
                chunk_header *new_chunk = (chunk_header*)((char*)curr + alloc_size);
                init_next_chunk(new_chunk, new_size);
                // fit the new chunk into the existing chain of chunks
                new_chunk->next = curr->next;
                curr->next = new_chunk;
                // this chunk is smaller because its end is now a different/new chunk
                curr->size = alloc_size;
            }
            else
            {
                // can't split this into two chunk
                // don't adjust curr->next
                // don't adjust curr->size even if it's slightly too big
            }
            // return memory region
            // curr = curr + sizeof(chunk_header); I think this is wrong
            ++curr; // I think this is right
            return curr;
        }

        curr = curr->next;
    }

    return NULL;
}

类似地，当您释放一个块时，您应该看到：

• 它后面还有一块链子
• 下一个块也是免费的

如果是这样的话，那么您应该合并这两个块，以形成一个单一的，更大的免费块。