malloc.c

#include <errno.h>
#include <limits.h>
#include <string.h>
#include <assert.h>

#include "malloc.h"
#include "memreq.h"

#define pagesize 4096

// dedicate 1 page to the bitmap for pages, which can handle up to 32768 pages
static unsigned int* page_bitmap;

// dedicate 1*pagesize*8*4 = 131072 bytes to the page-address map
//static void** page_addrmap;

// base of our pages
static char* page_base;

// set the ith bit in an array to given value
static void bitmap_set(unsigned int *bitmap, int i, int value) {
    if (value) bitmap[i/32] |= (1 << (i&31));
    else bitmap[i/32] &= ~(1 << (i&31));
}

// get the value of the ith bit in an array
static int bitmap_get(unsigned int *bitmap, int i) {
    return (bitmap[i/32] >> (i&31))&1;
}

#define pageptr(idx) (char*)(page_base + (idx)*pagesize)

static int pages_used;

// get the next free bit
// O(max), which can be at the very worst bounded to 128
static int bitmap_getfree(unsigned int* bitmap, int first, int max){
    int i;
    for (i=first/32;i<max;i++){
        unsigned int map = bitmap[i];
        if (map < (unsigned int)(4294967295U)){
            // there's a free slot
            int j;
            for (j=0;j<32;j++){
                if ((((map >> j)&1) == 0) && i*32+j >= first)
                    return i*32+j;
            }
            
        }
    }
    return -1;
}


void page_init(){
    page_bitmap = (unsigned int*)get_memory(32*pagesize);
    memset(page_bitmap,0,32*pagesize);
    //page_addrmap = (void**)get_memory(pagesize*64*2);
    //memset(page_bitmap,0,pagesize*64*2);
    page_base = ((char*)(page_bitmap))+pagesize*32;
}

char* get_memory_check(unsigned n){
    //static int i = 0;
    char* page = get_memory(n);
    int j = (((char*)page)-page_base)/pagesize;
    //if (i != j)
       //printf("%x %x\n",i,j);
    assert(pages_used==j);
    pages_used+= n/pagesize + (n&4095?-1:0);
    return page;
}

// allocate n pages, the user is responsible for individually freeing each
void* page_alloc(int n){
    // let's initialize if we haven't already
    if (page_bitmap == NULL)
        page_init();
    int idx, i, last;
    char* ptr;
    last = 0;
    // check for n consecutive blocks
    // we hope that get_memory returns consecutive blocks
    while (1){
        last = (idx = bitmap_getfree(page_bitmap, last, pagesize));
        //printf("%x\n",idx);
        //ptr = page_addrmap[last];
        ptr = pageptr(last);
        if (idx == -1)
            return NULL;
        for (i=1;i<n;i++){
            last++;
            
            if (bitmap_get(page_bitmap, last)){
                //printf("bitmap_get\n",idx);
                goto continue1;
            }
            
            if (last >= pages_used)
                break;

            //if (page_addrmap[last] == NULL){
            //    break;
            //} else if ((int)(page_addrmap[last]-((int)ptr)) != pagesize) {
            //    //printf("assumption violated\n");
            //    goto continue1;
            //}
            //ptr = page_addrmap[last];
            ptr = pageptr(last);
        }
        break;
        continue1:
        continue;
    }
    
    //page_addrmap[idx] = (void*)get_memory_check(n*pagesize);
    int alloc = 0;
    for (i=0;i<n;i++){
        bitmap_set(page_bitmap, idx+i, 1);
        // if has already been allocated, just return as is
        // otherwise, allocate it
        //if (page_addrmap[idx+i] == NULL){
        if (idx+i <= pages_used){
            // allocate it
            if (!alloc){
                //page_addrmap[idx+i] = get_memory_check((n-i)*pagesize);
                get_memory_check((n-i)*pagesize);
                alloc = 1;
            }
            //page_addrmap[idx+i] = ((char*)page_addrmap[idx]) + i*pagesize;
        }
    }
    //return page_addrmap[idx];
    return pageptr(idx);
}

int page_free(void* page, int n){
    int idx = (((char*)page)-page_base)/pagesize;
    int i;
    // validate that each page are indeed used
    for (i = idx; i < idx+n; i++){
        if (!bitmap_get(page_bitmap, i))
            return -1;
    }
    // free the pages
    for (i = idx; i < idx+n; i++){
        bitmap_set(page_bitmap, i, 0);
    }
    return 0;
}


// each block of memory is 64 bytes long
// each panel can contain 63 blocks
typedef struct block{
    int n1,n2,n3,n4,n5,n6,n7,n8;
    int m1,m2,m3,m4,m5,m6,m7,m8;
} __attribute__((packed)) block;

// small allocation panels, these are linked "arenas"
// guaranteed exactly 1 page, so we can use page_free here
typedef struct panel{
    unsigned short magic;
    struct panel* prev;
    struct panel* next;
    int n;
    unsigned int bitmap[2];
    block blocks [63];
}* panel; // 2 + 4 + 4 + 4 + 8 = 22

// malloc header, 2 bytes
typedef unsigned short* hdr;

panel root_panel;
panel tail_panel;

// get the next panel+start with n contiguous free blocks
panel panel_getfree(int n, int* pidx){
    panel cur;
    for (cur = root_panel; cur != NULL; cur = cur->next){
        // let's see if our current panel can actually support n blocks
        if (63-cur->n < n)
            continue;
        // use bitmap_getfree
        int idx = bitmap_getfree((unsigned int*)&cur->bitmap, 0, 2);
        int last = idx;
        // check for contiguity
        int i;
        for (i = idx; i < idx+n; i++){
            
            // check for overflow
            if (i >= 63) goto continue2;
            // check not used
            if (bitmap_get((unsigned int*)&cur->bitmap, i)) goto continue2;
            last++;
        }
        *pidx = idx;
        return cur;
        continue2:
        continue;
    }
    return NULL;
}

panel panel_new(){
    panel new_panel = (panel)page_alloc(1);
    new_panel->prev = NULL;
    new_panel->next = NULL;
    new_panel->n = 0;
    new_panel->bitmap[0] = 0;
    new_panel->bitmap[1] = 0;
    new_panel->magic = 0xbabe;
    return new_panel;
}

int panel_prepend(panel prev){
    if (!prev) return -1;
    // clober prev and next
    prev->prev = NULL;
    prev->next = root_panel;
    if (root_panel)
        root_panel->prev = prev;
    else
        tail_panel = prev;
    root_panel = prev;
    return 0;
}

int panel_append(panel next){
    if (!next) return -1;
    // clober prev and next
    next->next = NULL;
    next->prev = tail_panel;
    if (tail_panel)
        tail_panel->next = next;
    else
        root_panel = next;
    tail_panel = next;
    return 0;
}

int panel_remove(panel p){
    if (!p) return -1;
    // 4 cases
    // p is the only element
    // p is in front
    // p is in back
    // p is in between
    if (tail_panel == p && root_panel == p){
        tail_panel = NULL;
        root_panel = NULL;
        return 0;
    } else if (root_panel == p && p->next){
        // set root to p->next and p->next's prev to null
        root_panel = p->next;
        p->next->prev= NULL;
        return 0;
    } else if (tail_panel == p && p->prev){
        // set tail to p->prev and p->prev->next to null
        tail_panel = p->prev;
        p->prev->next = NULL;
        return 0;
    } else if (p->prev && p->next && p->prev->next == p && p->next->prev == p){
        // set p->prev->next to p->next and p->next->prev to p->prev
        panel next = p->next;
        panel prev = p->prev;
        prev->next = next;
        next->prev = prev;
        return 0;
    }
    return -1;
}

void *malloc(size_t size) {
    static int total = 0;
    total += size;
    //printf("malloc(%d): %d %d\n",getpid(),size,total);
    
    // we can store only 4032-8 bytes in 63 blocks contiguously
    // so if we need more, we're going to use big allocation
    
    if (size <= 4024){
        
        // use small allocation
        if (size <= sizeof(block)-sizeof(unsigned short)){
            // only allocate one small block
            // panel panel_getfree(int n, int* pidx)
            int idx;
            panel p = panel_getfree(1, &idx);
            //printf("\tyay %x %d %d\n",p,idx);
            if (p){
                // set the bit in p's map, offset the header
                // and return
                bitmap_set((unsigned int*)&p->bitmap, idx, 1);
                hdr h = (hdr)&p->blocks[idx];

                //h->magic = 0xbabe;
                *h = 1;
                //h->panel_idx = idx;
                return ((char*)h)+sizeof(unsigned short);
            } else {
                // let's create a new panel, set its first bit, and append it
                //printf("new\n");
                panel p = panel_new();
                bitmap_set((unsigned int*)&p->bitmap, 0, 1);
                if (panel_append(p)) return NULL;
                hdr h = (hdr)&p->blocks[0];

                //h->magic = 0xbabe;
                *h = 1;
                //h->panel_idx = 0;
                return ((char*)h)+sizeof(unsigned short);
            }
        } else {
            // we need multiple small blocks
            // let's first find the number of blocks needed
            int leftover = size + sizeof(unsigned short) - sizeof(block);
            int nblocks = leftover/(sizeof(block)) + /*(leftover%(sizeof(block)) == 0 ? 0 : 1) +*/ + 1 + 1;
            //printf("\tsmall blocks: %d %d\n",nblocks, leftover);
            int idx;
            panel p = panel_getfree(nblocks, &idx);
            //printf("yay2 %x\n",p);
            if (p){
                // set the bits in p's map and return
                int i;
                for (i=idx;i<idx+nblocks;i++)
                    bitmap_set((unsigned int*)&p->bitmap, i, 1);
                
                hdr h = (hdr)&p->blocks[idx];

                //h->magic = 0xbabe;
                *h = nblocks;
                //h->panel_idx = idx;
                return ((char*)h)+sizeof(unsigned short);
            } else {
                // let's create a new panel, set its first bits, and append it
                panel p = panel_new();
                int i;
                for (i=0;i<nblocks;i++)
                    bitmap_set((unsigned int*)&p->bitmap, i, 1);
                panel_append(p);
                
                hdr h = (hdr)&p->blocks[0];

                //h->magic = 0xbabe;
                *h = nblocks;
                return ((char*)h)+sizeof(unsigned short);
            }
        }
    } else {
        // large block allocation
        // if size <= pagesize-sizeof(struct hdr), then nblocks = 1
        int nblocks = 1;
        if (size > pagesize-2*sizeof(unsigned short)){
            int leftover =  size + 2*sizeof(unsigned short) - pagesize;
            nblocks += leftover/(pagesize) + (leftover%(pagesize) == 0 ? 0 : 1);
        }
        hdr h = page_alloc(nblocks);
        h[0] = 0xcafe;
        h[1] = nblocks;
        //printf("\tlarge %x\n",h);
        return ((char*)h)+2*sizeof(unsigned short);
    }
}

static size_t highest(size_t in) {
    size_t num_bits = 0;

    while (in != 0) {
        ++num_bits;
        in >>= 1;
    }

    return num_bits;
}

void* calloc(size_t number, size_t size) {
    size_t number_size = 0;

    /* This prevents an integer overflow.  A size_t is a typedef to an integer
     * large enough to index all of memory.  If we cannot fit in a size_t, then
     * we need to fail.
     */
    if (highest(number) + highest(size) > sizeof(size_t) * CHAR_BIT) {
        errno = ENOMEM;
        return NULL;
    }

    number_size = number * size;
    void* ret = malloc(number_size);

    if (ret) {
        memset(ret, 0, number_size);
    }

    return ret;
}

void* realloc(void *ptr, size_t size) {
    size_t old_size = 0; /* XXX Set this to the size of the buffer pointed to by ptr */
    void* ret = malloc(size);

    if (ret) {
        if (ptr) {
            memmove(ret, ptr, old_size < size ? old_size : size);
            free(ptr);
        }

        return ret;
    } else {
        errno = ENOMEM;
        return NULL;
    }
}

#define pagealign(x) (((unsigned int)(x)) & (~(unsigned int)4095))

// must free on the topmost
void free(void* ptr) {
    // The free function causes the space pointed to by ptr to be
    // deallocated, that is, made available for further allocation. 
    // If ptr is a null pointer, no action occurs.
    if (!ptr) return;
    unsigned short* page = (unsigned short*)pagealign(ptr);
    if (*page == 0xbabe){
        // small page
        panel p = (panel)page;
        int offset = (int)((int)ptr - (int)&p->blocks);
        int idx = offset/sizeof(struct block);
        hdr h = (hdr)&p->blocks[idx];
        int n = *h;
        // free the next n consecutive blocks
        int i;
        for (i=idx;i<idx+n;i++){
            assert(bitmap_get((unsigned int*)&p->bitmap, i));
            bitmap_set((unsigned int*)&p->bitmap, i, 0);
        }
        // let's impose an approximate ordering on the relative
        // "freeness" of the panels, bring this one to the front
        panel_remove(p);
        panel_prepend(p);
    } else if (*page == 0xcafe) {
        // large page
        int n = page[1];
        page_free(page, n);
    }
}