Нужен совет по реализации malloc и free в C - PullRequest
0 голосов
/ 12 октября 2018

Для школы мне нужно написать программу, использующую мою собственную реализацию malloc и бесплатную.Мне нужно иметь возможность сообщать обо всех фрагментах памяти в моей «куче», независимо от того, выделена она или нет.Я чувствую, что написал хороший код для этого, но, очевидно, нет.Первые несколько раз, когда я запускал его, отчет продолжал сообщать об одном и том же адресе навсегда.При попытке отладки, наступил момент, когда программа даже не позволяла мне начать выделять пространство для использования в качестве «кучи», она просто получала ошибку сегментации и выходила.Любые указатели на то, где я ошибаюсь, или даже на чистку кода, были бы очень полезны.

#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;
}

1 Ответ

0 голосов
/ 12 октября 2018

Первая очевидная ошибка, которую я вижу, связана с арифметикой указателя.SplitBlock пытается разделить 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 на самом деле size * sizof(node_t) байт в блок - что вполне может бытьмимо конца квартала.Вам нужно привести node к char * перед выполнением арифметики с ним, если вы хотите смещения байтов.Однако вы можете столкнуться с проблемами выравнивания ...

...