c - 需要关于在 C 中实现 malloc 和 free 的建议

Question

对于学校，我需要编写一个使用我自己的 malloc 和 free 实现的程序。我需要能够报告“堆”中的所有内存块，无论是否已分配。我觉得我已经编写了很好的代码来做到这一点，但显然不是。我运行它的前几次，报告一直在报告同一个地址。在尝试调试它时，程序甚至不允许我开始分配空间用作我的“堆”，它只会出现段错误并退出。任何关于我出错的地方的指示，甚至清理我的代码，都会非常有帮助。

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


#define WORDSIZE 8
#define ALLOCMAGIC 0xbaddecaf
#define FREEMAGIC 0xdeadbeef

typedef struct __header_t {
    size_t size;
    int magic;
} header_t;

typedef struct __node_t {
    size_t size;
    struct __node_t *next;
} node_t;

node_t *head = NULL;


// Find the free node that occurs just before the given node.
node_t *findLastFree(node_t * node) {

    // Initialize some pointers to traverse the free node linked list;
    node_t *lastFree = head;
    node_t *nextFree = lastFree->next;

    // Traverse linked list until the last node's pointer is pointed to NULL,
    // meaning the end of the list.
    while (nextFree != NULL) {

        // Check if target node is less than the next node, meaning the target node
        // is between last and next.  If so, then return last node.
        if (node < nextFree) {
            return lastFree;
        }

        lastFree = nextFree;
        nextFree = lastFree->next;
    }

    // If we have reached the end of the list and the target node is still greater
    // than the last node, return last node.
    return lastFree;
}


// If the given pointer is allocated, deallocate the space and coalesce the free
// node list.
void myFree(void *ptr) {

    // Initialize some free node pointers and assert that the given pointer is
    // the beginning of allocated space.
    node_t *lastFree;
    node_t *nextFree;
    node_t *newFree;
    header_t *block = ((header_t *) ptr) - 1;
    assert(block->magic == ALLOCMAGIC);

    // Set this block's signal to free space
    block->magic = FREEMAGIC;

    // Typecast the block into a free node and set it's size.
    size_t size = block->size + sizeof(header_t);
    newFree = (node_t *) block;
    newFree->size = size;

    // Check if node is before the first free node.  If so set the new node as
    // the new head.  If not, then handle node as it occurs after head.
    if (newFree < head) {

        nextFree = head;

        // Check if new node ends at the start of head.  If so, merge them
        // into a single free node.  Else point the new node at the previous head.
        // Either way, set new free as the new head.
        if ((newFree + newFree->size) == head) {
            newFree->next = head->next;
            newFree->size = newFree->size + head->size;
        } else {
            newFree->next = head;
        }
        head = newFree;
    } else {

        // Set the free nodes for before and after the new free node.
        lastFree = findLastFree(newFree);
        nextFree = lastFree->next;

        // Check if new node is the last node.  If so, point the previous final
        // node at the new node and point the new node at NULL.
        if (nextFree == NULL) {

            lastFree->next = newFree;
            newFree->next = NULL;
        }

        // Check if end of new node is touching next node.  If so, merge them
        // into a single free node.  Else point new free and next free.
        if ((newFree + newFree->size) == nextFree) {
            newFree->next = nextFree->next;
            newFree->size = newFree->size + nextFree->size;
        } else {
            newFree->next = nextFree;
        }

        // Check if start of new node is touching last free node.  If so, merge
        // them into a single free node.  Else point last's next to new free.
        if ((lastFree + lastFree->size) == newFree) {
            lastFree->next = newFree->next;
            lastFree->size = lastFree->size + newFree->size;
        } else {
            lastFree->next = newFree;
        }
    }
}


// Split the given free node to fit the given size.  Create a new node at the 
// remainder and rearrange the free list to accomodate.
void splitBlock(node_t *node, size_t size) {

    // Create a new pointer at the end of the requested space.
    void *newBlock = node + size;

    // Set the bits of the new space as if it were allocated then freed.
    header_t *hptr = (header_t *) newBlock;
    hptr->size = (node->size - size - sizeof(header_t));
    hptr->magic = FREEMAGIC;

    // Typecast the new space into a node pointer.  Reinsert it into the free
    // node list.
    node_t *newFree = (node_t *) newBlock;
    newFree->size = node->size - size;
    newFree->next = node->next;
    node_t *lastFree = findLastFree(newFree);
    lastFree->next = newFree;
}


// Find a free node that can fit the given size.  Split the node so no space is 
// wasted.  If no node can fit requested size, increase the heap size to accomodate.
void *findFirstFit(size_t size) {

    // Create a node pointer to traverse the free node list.
    node_t *node = head;

    // Traverse the list until the end is reached.
    while(node != NULL) {

        // Check if the node can accomodate the requested size.
        if (node->size >= size) {

            // Split the current node at the requested size and return a pointer
            // to the start of the requested space.
            splitBlock(node, size);
            return (void *) node;
        }
        node = node->next;
    }

    // No free space could fit requested size, so request more space at the end
    // of the heap.
    void *newspace = sbrk(size);
    assert(newspace >= 0);

    return newspace;
}


// Allocate a block of space for the given size and return a pointer to the start
// of the freed space.

void *myMalloc(size_t need) {

    // Round the given size up to the next word size.  Add the size of a header to
    // the amount actually needed to allocate.
    need = (need + WORDSIZE - 1) & ~(WORDSIZE - 1);
    size_t actual = need + sizeof(header_t);

    // Find a free node that can accomodate the given size.  Check it is valid.
    void *firstfit = findFirstFit(actual);
    assert(firstfit >= 0);

    // Create a header for the newly allocated space.
    header_t *hptr = (header_t *) firstfit;
    hptr->magic = ALLOCMAGIC;
    hptr->size = need;

    return (void *) (hptr + 1);
}


// Print a report on the space starting at the given pointer.  Return a pointer to
// the start of the next block of space.
void *reportAndGetNext(void *ptr) {

    void *nextptr;
    header_t *hptr = (header_t *) ptr;

    // Check if the pointer is pointing to allocated space.
    if (hptr->magic == ALLOCMAGIC) {

        // Report the characteristics of the current block.
        printf("%p is ALLOCATED starting at %p and is %zd bytes long.\n", hptr, (hptr + 1), hptr->size);

        // Set the next pointer to be returned.
        nextptr = hptr + hptr->size + sizeof(header_t);
    } else {

        // Cast the pointer as a free node.  Set the next pointer to be returned.
        node_t *free = (node_t *) ptr;
        nextptr = free + free->size;

        // Report the characteristics of the current block.
        printf("%p is FREE for %zd bytes.\n", hptr, free->size);
    }
    return nextptr;
}


// Report on all blocks of space contained within the heap space, starting at the 
// given pointer.
void report(void* startheap) {

    void *ptr = startheap;
    void *end = sbrk(0);
    int count = 50;

    printf("Current Status of Heap:\n");

    while (ptr != NULL && count > 0) {
        ptr = reportAndGetNext(ptr);
        count = count - 1;
    }

    printf("Heap Length: %zd \n", (end - startheap));

}


int main(void) {

    void *start = sbrk(4096);
    assert(start >= 0);
    head = (node_t *) start;
    head->size = 4096;
    head->next = NULL;

    printf("Allocating block 1");
    void *ptr1 = myMalloc(26);
    void *ptr2 = myMalloc(126);
    report(start);
    myFree(ptr1);
    myFree(ptr2);

    return 0;
}

Answer 1

我看到的第一个明显错误是指针算术错误。 SplitBlock 试图从 block 的前面分割 size 字节，但是当您这样做时:

void splitBlock(node_t *node, size_t size) {
    // Create a new pointer at the end of the requested space.
    void *newBlock = node + size;

你的newBlock指针实际上是 block 中的size * sizof(node_t)个字节——这很可能超出了 block 的末尾。如果您想要字节偏移量，则需要在对其进行指针算术之前将 node 转换为 char *。但是，您可能会遇到对齐问题...