在C语言中编写自己的malloc函数

Question

我需要你的帮助。我对C语言有一定的了解，并且现在遇到了一个问题。我要使用一些基准测试来测试一些计算机架构方面的内容（分支缺失、缓存缺失）在一款新处理器上。问题是这些基准测试都是用C语言编写的，但我不能包含任何库调用。例如，我不能使用malloc函数，因为我会收到错误提示。

"undefined reference to malloc" 

即使我已经包含了库，但还是需要编写自己的malloc。我不需要它效率超高 - 只需基本功能即可。我考虑要在内存中拥有一个地址，并且每次发生malloc时，都会返回该地址的指针并将计数器按该大小递增。我的程序中发生了两次malloc，所以我甚至不需要大内存。

你能帮我吗？我已经设计了一个Verilog，但在C方面没有太多经验。

我看过之前的答案，但对我来说好像都太复杂了。此外，我无法访问K-R书籍。

干杯！

编辑：也许这可以更好地帮助你： 我没有使用gcc，而是sde-gcc编译器。这会有什么区别吗？也许这就是为什么我得到了对malloc未定义的引用？

编辑2： 我正在测试MIPS架构：

我已经包含了：

#include <stdlib.h>

错误信息如下：

undefined reference to malloc
relocation truncated to fit: R_MIPS_26 against malloc

编译器命令 ID：

test.o: test.c cap.h
sde-gcc -c -o test.s test.c -EB -march=mips64 -mabi=64 -G -O -ggdb -O2 -S
    sde-as -o test.o test.s EB -march=mips64 -mabi=64 -G -O -ggdb
    as_objects:=test.o init.o

编辑3: 好的，我使用了上面的实现，它可以顺利运行。问题是，在嵌入式编程中，你必须定义你使用的所有内容，所以我定义了自己的malloc。sde-gcc无法识别malloc函数。

- ghostrider

---

一个“简单”的malloc实现起来已经够难了。 - UmNyobe

难道修复未定义的引用不比编写没有系统调用的自己的malloc更容易吗？ - Mike

@Mike：你一直在问编译的问题，但是malloc的未定义引用似乎是一个链接错误。这在嵌入式编程中很常见。再加上提问者正在测试低级计算机架构特性而不是编写用户级应用程序，看起来他们可能正在嵌入式环境中工作，其中malloc可能不可用，正如他们所说。因此，你关于编译的问题可能不准确。如果你想继续追究这个问题，你应该首先确定malloc是否实际上在库中可用（而不是头文件）。 - Eric Postpischil

@ghostrider 这还不是相关的部分。你展示的是编译命令，但我们需要看到链接器命令。 - Šimon Tóth

@Let_Me_Be：反对澄清需求是工程学的相反。没有理由不确保问题被正确定义。OP已经陈述：“我不能包含任何库调用”和“我想知道是否可以在没有任何syscall的情况下编写它。”他们已经清楚地表达了他们的愿望。如果您想回答不同的问题，那么您至少应该确认情况。 - Eric Postpischil

Answer 1

这是一种非常简单的方法，可能可以让您克服2个动态内存分配：

static unsigned char our_memory[1024 * 1024]; //reserve 1 MB for malloc
static size_t next_index = 0;

void *malloc(size_t sz)
{
    void *mem;

    if(sizeof our_memory - next_index < sz)
        return NULL;

    mem = &our_memory[next_index];
    next_index += sz;
    return mem;
}

void free(void *mem)
{
   //we cheat, and don't free anything.
}

如果需要的话，您可能需要对返回的内存块进行对齐，例如，您始终返回地址是4、8、16或任何您所需的地址的倍数。请注意保留HTML标签。

- nos

---

-1 因为这个无法运作，因为存在对齐问题。Malloc 必须考虑对齐要求，这就是为什么标准 malloc 总是返回内存对齐到最严格的对齐要求。无论是您的内存缓冲区还是实现都没有做到这一点。 - Šimon Tóth

我认为你的意思是 if (sizeof our_memory - next_index < sz)。（如果我们剩余可分配内存的量 小于 我们所需求的内存，则返回 NULL。） - CB Bailey

@Let_Me_Be 「这是一个非常简单的方法...」 - UmNyobe

如果他只需要两个内存块，这样做就过度了... 只需静态声明内存块即可。 - AnthonyLambert

@ghostrider 根据你编译器的文档，malloc 应该可以正常工作。你可能遇到了一些安装/配置问题。此外，平台对齐非常敏感，所以这段代码肯定不会起作用。 - Šimon Tóth

Answer 2

尝试使用上面给出的线程安全的nos答案，我参考了他的代码并进行了一些修改，如下所示：

static unsigned char our_memory[1024 * 1024]; //reserve 1 MB for malloc
static size_t next_index = 0;

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *malloc(size_t sz)
{
    void *mem;
    pthread_mutex_lock(&lock);
    if(sizeof our_memory - next_index < sz){
        pthread_mutex_unlock(&lock);
        return NULL;
    }

    mem = &our_memory[next_index];
    next_index += sz;
    pthread_mutex_unlock(&lock);
    return mem;
}

void free(void *mem)
{
   //we cheat, and don't free anything.
} 

- ChandanK

Answer 3

你需要链接libc.a或者等效库到你的系统上。如果你不使用标准C库，那么在main函数执行前运行的启动代码将无法得到执行。你的程序将永远无法运行...

你可以分配一个静态数据块并将其用作malloc的替代，例如：

// char* fred = malloc(10000);
// equals

static char [100000] fred;

您可以在启动时调用标准的malloc函数来分配一大块连续内存，并编写自己的malloc类型函数将其划分。在第二种情况下，您应在调用系统的malloc后开始基准测试，以不影响基准测试。

- AnthonyLambert

---

因为你原来的回答与问题完全不相关。 - Šimon Tóth

我对于“我无法使用malloc，因为我得到了错误信息'undefined reference to malloc'”的原始回答是链接到lib.c，不确定那是否无关紧要或者你在不这样做的情况下能否取得进展... - AnthonyLambert

Answer 4

我将分享Malloc和free的完整方法，它适用于每种情况。这是使用数组进行补充的。我们也可以使用链接列表来实现元数据。

有三种场景需要覆盖：

1. 连续内存分配：以连续方式分配内存。 2. 在两个已分配的内存之间分配内存：当内存在两个已分配的内存块之间可用时，我们必须使用该内存块进行分配。 3. 从初始块分配内存时，初始块是空闲的。

详见下图：内存分配算法的分配图 malloc源代码：

#define TRUE        1
#define FALSE       0

#define MAX_ALOCATION_ALLOWED       20
static unsigned char our_memory[1024 * 1024];

static int g_allocted_number = 0;
static int g_heap_base_address = 0;

typedef struct malloc_info
{
    int address;
    int size;
}malloc_info_t;

malloc_info_t   metadata_info[MAX_ALOCATION_ALLOWED] ={0};

void* my_malloc(int size)
{
    int j =0;
    int index = 0 ;
    int initial_gap =0;
    int gap =0;
    int flag = FALSE;
    int initial_flag = FALSE;
    void *address = NULL;
    int heap_index = 0;
    malloc_info_t temp_info = {0};

    if(g_allocted_number >= MAX_ALOCATION_ALLOWED)
    {
        return NULL;
    }

    for(index = 0; index < g_allocted_number; index++)
    {
        if(metadata_info[index+1].address != 0 )
        {
            initial_gap = metadata_info[0].address - g_heap_base_address; /*Checked Initial Block (Case 3)*/
            if(initial_gap >= size)
            {
                initial_flag = TRUE;
                break;
            }
            else
            {
                gap = metadata_info[index+1].address - (metadata_info[index].address + metadata_info[index].size);  /*Check Gap Between two allocated memory (Case 2)*/
                if(gap >= size)
                {
                    flag = TRUE;
                    break;
                }
            }
        }
    }

    if(flag == TRUE)    /*Get Index for allocating memory for case 2*/
    {
        heap_index = ((metadata_info[index].address + metadata_info[index].size) - g_heap_base_address);
    
        for(j = MAX_ALOCATION_ALLOWED -1; j > index+1; j--)
        {
            memcpy(&metadata_info[j], &metadata_info[j-1], sizeof(malloc_info_t));
        }
    }
    else if (initial_flag == TRUE) /*Get Index for allocating memory for case 3*/
    {
        heap_index = 0;
        for(j = MAX_ALOCATION_ALLOWED -1; j > index+1; j--)
        {
            memcpy(&metadata_info[j], &metadata_info[j-1], sizeof(malloc_info_t));
        }
    }
    else /*Get Index for allocating memory for case 1*/
    {
        if(g_allocted_number != 0)
        {
            heap_index = ((metadata_info[index -1].address + metadata_info[index-1].size) - g_heap_base_address);
        }
        else    /* 0 th Location of Metadata for First time allocation*/
            heap_index = 0;
    }

    address = &our_memory[heap_index];
    metadata_info[index].address = g_heap_base_address + heap_index;
    metadata_info[index].size = size;

    g_allocted_number += 1;
    return address;
}

现在免费编写代码。

void my_free(int address)
{
    int i =0;
    int copy_meta_data = FALSE;
    
    for(i = 0; i < g_allocted_number; i++)
    {
        if(address == metadata_info[i].address)
        {
            // memset(&our_memory[metadata_info[i].address], 0, metadata_info[i].size);
            g_allocted_number -= 1;
            copy_meta_data = TRUE;
            printf("g_allocted_number in free = %d %d\n", g_allocted_number, address);
            break;
        }
    }
    
    if(copy_meta_data == TRUE)
    {
        if(i == MAX_ALOCATION_ALLOWED -1)
        {
            metadata_info[i].address = 0;
            metadata_info[i].size = 0;
        }
        else
            memcpy(&metadata_info[i], &metadata_info[i+1], sizeof(malloc_info_t));
    }
}

现在进行测试的代码是：

int main()
{
    int *ptr =NULL;
    int *ptr1 =NULL;
    int *ptr2 =NULL;
    int *ptr3 =NULL;
    int *ptr4 =NULL;
    int *ptr5 =NULL;
    int *ptr6 =NULL;
    
    g_heap_base_address = &our_memory[0];

    ptr = my_malloc(20);
    ptr1 = my_malloc(20);
    ptr2 = my_malloc(20);
    
    my_free(ptr);
    ptr3 = my_malloc(10);
    ptr4 = my_malloc(20);
    ptr5 = my_malloc(20);
    ptr6 = my_malloc(10);
    
    printf("Addresses are: %d, %d, %d, %d, %d, %d, %d\n", ptr, ptr1, ptr2, ptr3, ptr4, ptr5, ptr6);

    return 0;
}

- Prabhanjan Kumar