0

So, I'm currently going thorugh the book "Crafting Interpreters", one of the challenges is to allocate a big chunk of memory (only once) in the beginning of the program and manage it. So far i've written this piece of code, but I'm not quite shure that I'm in the right direction.

#include <stdio.h>
#include "stdbool.h"
#include "stdlib.h"

typedef struct node {
    _Bool free;
    struct node* next;
} freeList;

#define IS_VALID(head) ((head)->next == NULL) ? 0 : 1
#define BLOCK_SIZE 8

void initFreeList(freeList* head, size_t size);
void* malloc_(freeList* head, size_t size);
void free_(freeList* head, void* var);

void initFreeList(freeList* head, size_t size)
{
    freeList* ptr = NULL;

    head->next = NULL;
    head->free = true;
    ptr = head;

    for (int i = 0; i < size; i++) {
        freeList* temp = malloc(sizeof(freeList*));
        temp->next = NULL;
        temp->free = true;
        ptr->next = temp;
        ptr = temp;
    }
}

// Removes a node from the freeList and returns a void pointer.
void* malloc_(freeList* head, size_t size)
{
    void* block = NULL;
    freeList* ptr = NULL, *prev = NULL, *temp_ptr = NULL;
    int counter = 0;

    if (!IS_VALID(head))
        return NULL;

    while((size) % BLOCK_SIZE != 0)
        size++;

    for (ptr = head; ptr->next != NULL && ptr->free == true && counter < size;) {
        counter += BLOCK_SIZE;
        prev = ptr;
        ptr = ptr->next;
        ptr->free = false;
    }

    temp_ptr = ptr;
    for (counter = 0; counter < size; counter += BLOCK_SIZE, temp_ptr = temp_ptr->next)
        temp_ptr->free = false;

    prev->next = temp_ptr->next;
    temp_ptr->next = NULL;
    block = ptr;

    return block;
}

void free_(freeList* head, void* var)
{
    _Bool flag = true;

    while(head && flag) {
        if (head->next == NULL) {
            head->next = (freeList *) var;
            head->next->free = true;
            head->next->next = NULL;
            flag = false;
        }
        head = head->next;
    }
}

int main()
{
    freeList* head = malloc(sizeof(freeList));

    initFreeList(head, 10);


    char* str = malloc_(head, 16);
    int *var1 = malloc_(head, 8), *var2 = malloc_(head, 8);

    sprintf(str, "%s", "Hello world !");

    *var1 = 2000000000;
    *var2 = 257;

    free_(head, var1);
    free_(head, str);
    free_(head, var2);

   printf("%s\n%d %d\n", str, *var1, *var2);

    return 0;
}

I'm able to allocate memory for the variables in main, and when freeing the chunks are added back to the free list but some of them get lost, I guess it's because when I assigned memory using the malloc_ im overwriting memory. What will be the right approach for this kind of problem ?

CASIO15
  • 1
  • 2
    Side note: It seems strange to use `_Bool` instead of `bool` after including `stdbool.h`. The whole point of including that file is so that you don't have to write `_Bool` anymore. – Andreas Wenzel Sep 10 '21 at 23:53
  • Side note: [What is the difference between #include and #include "filename"?](https://stackoverflow.com/q/21593/12149471) – Andreas Wenzel Sep 10 '21 at 23:54
  • This has a problem: `freeList* temp = malloc(sizeof(freeList*));` The size is of the pointer; you want `sizeof (freeList)`, like you did in `main`.Better yet, `sizeof *temp`. – Kaz Sep 10 '21 at 23:56
  • Your program does not allocate one large chunk of memory and manage it afterwards; it pre-allocates many small objects and keeps them in a free list before doing anything else. There is no advantage in doing that compared to just allocating those objects when they are needed, and then recycling them through the free list. – Kaz Sep 11 '21 at 00:01
  • Oh, you are right, I thought I changed it… and there is no particular reason why I’m using the unsigned version of bool. – CASIO15 Sep 11 '21 at 00:02
  • `free_` should just push the freed object onto the head of the free list without looping. What you have is that each time `free_` is called, an O(N) search takes place to find the end of the free list. This is going to be slower than if you just called `malloc` and `free` without any recycling scheme. `malloc_` can likewise just yank the item from the front of the list, if available. This is good for caching behavior: the most recently freed items are allocated back into use first. – Kaz Sep 11 '21 at 00:04
  • Hi Kaz, so what will be the correct approach for managing a large chunk of malloc ? Should I use system calls for doing this ? Or there’s a simpler way of doing so ? – CASIO15 Sep 11 '21 at 00:05
  • Your program, if I'm understanding it correctly, is suffering from a fatal flaw. I'm getting the impression from trying to understand `malloc_`, that you believe that this function can satisfy a request for some `size` number of bytes by allocating multiple consecutive free items from the free list. But this is not so; when a request is made to allocate a certain amount of memory, it is expected that the memory is one contiguous block. – Kaz Sep 11 '21 at 00:06
  • An allocator that returns multiple blocks which add up to the requested size is a "rope allocator". That's only useful to a specialized application: like a string module that uses a rope representation of strings, or a network stack supporting scatter-gather I/O. you need a proper API for that; the caller can't just get a `void *` pointer: it has to know how many pieces there are and has to be able to get all their addresses. – Kaz Sep 11 '21 at 00:09
  • You are right the memory is scattered because of the use of pointers, this implementation just came to do the top of my head, and I decided to go with it… but it has more flaws than merits (if it has any merits at all lol). This exercise was an extra mile challenge… maybe I’ll try it at some other time. – CASIO15 Sep 11 '21 at 00:18

0 Answers0