A Malloc Tutorial

simple_malloc.c

#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <sys/resource.h>
#include <sys/types.h>


typedef struct s_block* t_block;
struct s_block {
    size_t size;
    t_block prev;
    t_block next;
    int free;
    int padding;
    void *ptr;      /* Magic pointer, point to data */
    char data[1];
};

#define BLOCK_SIZE 40 
t_block first_block = NULL;

/* Find an suitable block using first fit */
t_block find_block(t_block *last, size_t size) {
    t_block b = first_block;
    while (b && !(b->free && b->size >= size)) {
        *last = b;
        b = b->next;
    }
    return b;
}

/* Add a new block at the end of heap */
/* return NULL if things go wrong */
t_block extend_heap(t_block last, size_t s) {
    t_block b;
    b = (t_block)sbrk(0);
    if (sbrk(BLOCK_SIZE + s) == (void*) -1)
        return NULL;
    b->size = s;
    b->next = NULL;
    b->prev = last;
    b->ptr = b->data;
    if (last)
        last->next = b;
    b->free = 0;
    return b;
}

/* Split block according to size. */
/* The b block must be exist.     */
void split_block(t_block b, size_t s) {
    t_block new_block;
    new_block = (t_block)(b->data + s);
    /* insert new_block between b and b->next */
    new_block->next = b->next;
    new_block->prev = b;
    b->next = new_block;
    if (new_block->next)
        new_block->next->prev = new_block;
    /* update meta of new_block */
    new_block->size = b->size - s - BLOCK_SIZE; 
    new_block->ptr = b->data;
    new_block->free = 1;
    /* update meta of b */
    b->size = s;
}

/* Align size */
size_t align8(size_t s) {
    /* s % 8 */
    if ((s & 0x7) == 0)
        return s;
    return ((s >> 3) + 1) << 3;
}


void* malloc(size_t size)
{
    t_block b, last;
    size_t s;
    
    /* align */
    s = align8(size);
    if (first_block) {
        /* find suitable block */
        last = first_block;
        b = find_block(&last, s);
        if (b) {
            /* too big, split */
            if ((b->size - s) >= (BLOCK_SIZE + 8)) {
                split_block(b, s);
            }
            /* */
            b->free = 0;
        }
        else {
            /* no suitable block, create a new one */
            b = extend_heap(last, s);
            if (!b) return NULL;
        }
    }
    else {
        b = extend_heap(NULL, s);
        if (!b) return NULL;
        first_block = b;
    }
    return b->data;
}


void* calloc(size_t n, size_t size) {
    size_t* new_block;
    size_t s8, i;
    new_block = (size_t*)malloc(n * size);
    if (new_block) {
        /* the number os groups */
        s8 = align8(n * size) >> 3;
        for (i = 0; i < s8; i++)
            new_block[i] = 0;
    }
    return new_block;
}

t_block get_block(void *p) {
    char *tmp;
    tmp = (char *)p;
    return (t_block)(p = tmp -= BLOCK_SIZE);
}

int valid_addr(void *p) {
    if (first_block) {
        if (p > first_block && p <sbrk(0)) {
            return (p == (get_block(p))->ptr);
        }
    }
    /* No block */
    return 0;
}

t_block fusion(t_block b) {
    if (b->next && b->next->free) {
        b->size += BLOCK_SIZE + b->next->size;
        b->next = b->next->next;
        if (b->next)
            b->next->prev = b;
    }
    return b;
}

void free(void *p) {
    t_block b;
    if (valid_addr(p)) {
        b = get_block(p);
        b->free = 1;
        /* fusion with previous if possible */
        if (b->prev && b->prev->free)
            b = fusion(b->prev);
        /* then fusion with next */
        if (b->next)
            fusion(b);
        else {
            /* reach the break, free the end of the heap */
            if (b->prev)
                b->prev->prev = NULL;
            else
                /* NO more block */
                first_block = NULL;
            brk(b);
        }
    }
}


int main()
{
    struct rlimit *limit = (struct rlimit *)malloc(sizeof(struct rlimit));
    if (limit) {
        if (getrlimit(RLIMIT_AS, limit) == 0) { /* RLIMIT_AS represents virtual memory information */
            printf("soft limit: %ld, hard limit: %ld\n", limit->rlim_cur, limit->rlim_max);
        }
        else {
            printf("errno = %d\n", errno);
        }
    }

    int* p = (int*)malloc(sizeof(int));
    *p = 1;
    printf("addr of p: %p\n", p);
    printf("value of p: %d\n", *p);
    free(p);
    return 0;
}