制作自malloc的，什么是错在这里？ [英] making custom Malloc, what is wrong here?

问题描述

我一直工作在一个小的定制worstfit的malloc使用双链表一段时间，虽然这是小我以为这会工作。有什么明显的不对这个code？

 的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆string.h中GT;
＃包括LT＆;＆unistd.h中GT;＃包括mymal.htypedef结构节点
{
    INT大小;
    INT状态;
    结构节点*接下来的;
    结构节点* previous;
}节点;
节点*终端节点;
节点* rootNode中;无效* worstfit_mall（INT大小）
{
    节点* theNode = SBRK（尺寸+的sizeof（theNode））;
    无效* PTR;
    如果（rootNode中== NULL）
    {
        theNode-＆GT;状态= 1;
        theNode-＆GT;大小=;
        theNode-＆GT; previous = theNode;
        theNode-＆gt;接下来= theNode;
        rootNode中= theNode;
        终端节点= theNode;
        返回theNode;
    }
    节点* worstNode;
    worstNode = worstFit（大小）;
    如果（worstNode！= NULL）
    {
        theNode-＆GT;状态= 1;
        theNode-＆GT;大小=;
        节点* newNode = SBRK（（worstNode-＆GT;大小 -  theNode-＆GT;大小）+的sizeof（theNode））;
        newNode-＆GT;状态= 0;
        newNode-＆GT;大小= worstNode-＆GT;大小 -  theNode-＆GT;大小;
        theNode-＆gt;接下来= newNode;
        theNode-＆GT; previous = worstNode-＆GT; previous;
        newNode-＆gt;接下来= worstNode-＆gt;接下来，
        返回newNode;
    }
    endNode-＆gt;接下来= theNode;
    终端节点= theNode;
    endNode-＆GT;状态= 1;
    endNode-＆GT;大小=;
    PTR = SBRK（尺寸+的sizeof（theNode））;
    返回PTR;
}无效my_free（无效* PTR）
{
    节点*指针;
    指针=（节点*）PTR;
    指针 - ＆GT;状态= 0;
    如果（（指针 - ＆GT;下一步 - ＆GT;状态== 0）及及（指针 - ＆GT; previous-＆GT;状态== 0））
        SBRK（-1 *（指针 - ＆GT;下一步 - ＆GT;大小+指针 - ＆GT;大小））;
    否则，如果（（指针 - ＆GT;下一步 - ＆GT;状态== 1）及及（指针 - ＆GT; previous-＆GT;状态== 0））
        SBRK（-1 *（指针 - ＆GT; previous-＆GT;大小+指针 - ＆GT;大小））;
    否则，如果（（指针 - ＆GT;下一步 - ＆GT;状态== 0）及及（指针 - ＆GT;下一步 - ＆GT;状态== 0））
        SBRK（-1 *（指针 - ＆GT; previous-＆GT;大小+指针 - ＆GT;下一步 - ＆GT;大小+指针 - ＆GT;大小））;
    其他
        SBRK（-1 *指针 - ＆GT;大小）;
}无效* worstFit（INT大小）
{
        节点* theNode = rootNode中;
        节点* worstNode;
        而（theNode！= NULL）
        {
                如果（（worstNode == NULL || theNode-＆GT;大小＆GT; worstNode-＆GT;大小）及及（theNode-＆GT;大小＆GT; =大小）及及（theNode-＆GT;状态== 0 ））
                        worstNode = theNode;
                theNode = theNode-＆gt;接下来，
        }
        返回worstNode;
}
 

解决方案

下面是马上打我的事情：

• worstFit 不初始化 worstNode 到 NULL 和尝试，同时它还是垃圾读它。




• 您创建节点第一个链表，但尾节点的接下来总是指向自身。与此同时 worstFit 需要一个 NULL 警戒值时，它遍历列表中。




• worstfit_mall 不初始化当最初创建终端节点 rootNode中。




• worstfit_mall 返回一个指向分配节点，但如果它的意思是替代为的malloc ，它应该是一个指针，返回的内存调用者被允许写。你不想呼叫者在你的节点数据乱画。

  我期望 worstfit_mall 返回（（字符*）节点）+ sizeof的*节点）（或更简单地说，节点+ 1 ），而不是返回节点直接。 my_free 需要做相应的，反向的调整来获取节点指针。

  无效my_free（无效* PTR）
{
    节点* NODEPTR = PTR;
    nodePtr--;
    ...
}




• 此外，这是我不清楚为什么 worstfit_mall 通过 SBRK 下去，当<$分配内存C $ C> worstNode！= NULL 路径。是不是这条道路的点找到的现有的内存块重用？此外，这条道路叫 SBRK 的两次的




• 最后，在我看来， my_free 无条件地减少分配的内存量，但如果你释放你分配的最后一件事，只会工作与 SBRK 。如果你叫 worstfit_mall 两次，然后叫 my_free 第一个结果？没有路径，其中 my_free 标记内存块为没有再使用中让 worstfit_mall 可重用更高版本。

我不知道是否有其他问题，您的code;我会说，有很可能给出这些类型的根本问题。

I've been working on a little custom worstfit Malloc using a double-linked list for a while, and although this is small I thought this would work. Is there anything obvious that is wrong with this code?

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

#include "mymal.h"

typedef struct Node 
{
    int size;
    int status;
    struct Node *next;
    struct Node *previous;
} Node;


Node *endNode;
Node *rootNode;

void *worstfit_mall(int size)
{
    Node *theNode = sbrk (size + sizeof(theNode));
    void *ptr;
    if (rootNode == NULL)
    {
        theNode->status = 1;
        theNode->size = size;
        theNode->previous = theNode;
        theNode->next = theNode;
        rootNode = theNode;
        endNode = theNode;
        return theNode;
    }
    Node *worstNode;
    worstNode = worstFit(size);
    if (worstNode != NULL)
    {
        theNode->status = 1;
        theNode->size = size;
        Node *newNode = sbrk((worstNode->size - theNode->size) + sizeof(theNode));
        newNode->status = 0;
        newNode->size = worstNode->size - theNode->size;
        theNode->next = newNode;
        theNode->previous = worstNode->previous;
        newNode->next = worstNode->next;
        return newNode;
    }
    endNode->next = theNode;
    endNode = theNode;
    endNode->status = 1;
    endNode->size = size;
    ptr = sbrk(size + sizeof(theNode));
    return ptr;
}

void my_free(void *ptr)
{
    Node *pointer;
    pointer = (Node*)ptr;
    pointer->status = 0;
    if ((pointer->next->status == 0) && (pointer->previous->status == 0))
        sbrk(-1 * (pointer->next->size + pointer->size));
    else if ((pointer->next->status == 1) && (pointer->previous->status == 0))
        sbrk(-1 * (pointer->previous->size + pointer->size));
    else if ((pointer->next->status == 0) && ( pointer->next->status == 0))
        sbrk(-1 * (pointer->previous->size + pointer->next->size + pointer->size));
    else
        sbrk(-1 * pointer->size);
}

void *worstFit(int size)
{
        Node *theNode = rootNode;
        Node *worstNode;
        while (theNode != NULL)
        {
                if ((worstNode == NULL || theNode->size > worstNode->size) && (theNode->size >= size) && (theNode->status == 0))
                        worstNode = theNode;
                theNode = theNode->next;
        }
        return worstNode;
}

解决方案

Here are the things that immediately strike me:

• worstFit does not initialize worstNode to NULL and tries to read it while it's still garbage.

• You create a linked list of Nodes, but the tail Node's next always points to itself. Meanwhile worstFit expects a NULL sentinel value when it iterates over the list.

• worstfit_mall does not initialize endNode when initially creating rootNode.

• worstfit_mall returns a pointer to the allocated Node, but if it's meant to be substitutable for malloc, it should be returning a pointer to memory that the caller is allowed to write to. You don't want the caller to scribble all over your Node data.

  I'd expect worstfit_mall to return ((char*) node) + sizeof *node) (or more simply, node + 1) instead of returning node directly. my_free would need to do a corresponding, inverse adjustment to retrieve the Node pointer.

  void my_free(void *ptr) { Node *nodePtr = ptr; nodePtr--; ... }

• Additionally, it's unclear to me why worstfit_mall allocates memory via sbrk when going down the worstNode != NULL path. Isn't the point of this path to find an existing memory chunk to reuse? Furthermore, this path calls sbrk twice.

• Finally, it appears to me that my_free unconditionally reduces the amount of allocated memory, but that would work only if you're freeing the last thing you allocated with sbrk. What if you called worstfit_mall twice and then called my_free on the first result? There is no path where my_free marks the memory chunk as no-longer-in-use so that worstfit_mall can reuse it later.

I don't know if there are other problems with your code; I would say that there very likely are given these types of fundamental issues.

这篇关于制作自malloc的，什么是错在这里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！