malloc.c File Reference

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/mman.h>

Include dependency graph for malloc.c:

Go to the source code of this file.

Data Structures
struct	Header
struct	HeapPool

Macros
#define	HEAP_MAGIC   0x8051
#define	HEAP_MIN_POOLSIZE   (64 - sizeof(Header))
#define	HEAP_MAX_POOLSIZE   (128*1024 - sizeof(Header))
#define	HEAP_POOLS   (12)
#define	PGSIZE   4096
#define	HEAP_INCREMENT   (PGSIZE / 64)
#define	ROUNDUP(_x, _n)   (((_x) + (_n) - 1) & ~((_n) - 1))

Typedefs
typedef struct Header	Header
typedef struct HeapPool	HeapPool

Functions
static int	size_to_idx (size_t sz)
static void	grow_small (int idx)
static void *	malloc_small (size_t sz)
static void	free_small (Header *mem)
static void *	malloc_large (size_t sz)
static void	free_large (Header *mem)
void *	calloc (size_t num, size_t sz)
void *	malloc (size_t sz)
void	free (void *mem)

Variables
static HeapPool	pool [HEAP_POOLS]
static HeapPool	largePool = { 0, 0, (Header *)0, 0x4C000000, 0x4C000000 }

---

Data Structure Documentation

Header

struct Header

Definition at line 8 of file malloc.c.

Collaboration diagram for Header:

Data Fields
uint16_t	magic
struct Header *	next
uint32_t	size
uint16_t	status

HeapPool

struct HeapPool

Definition at line 24 of file malloc.c.

Collaboration diagram for HeapPool:

Data Fields
uint64_t	base
uint32_t	blocksFree
uint32_t	blocksInuse
Header *	free
uint64_t	top

Macro Definition Documentation

HEAP_INCREMENT

#define HEAP_INCREMENT   (PGSIZE / 64)

Definition at line 22 of file malloc.c.

HEAP_MAGIC

#define HEAP_MAGIC   0x8051

Definition at line 15 of file malloc.c.

HEAP_MAX_POOLSIZE

#define HEAP_MAX_POOLSIZE   (128*1024 - sizeof(Header))

Definition at line 18 of file malloc.c.

HEAP_MIN_POOLSIZE

#define HEAP_MIN_POOLSIZE   (64 - sizeof(Header))

Definition at line 17 of file malloc.c.

HEAP_POOLS

#define HEAP_POOLS   (12)

Definition at line 19 of file malloc.c.

PGSIZE

#define PGSIZE   4096

Definition at line 21 of file malloc.c.

ROUNDUP

#define ROUNDUP	(		_x,
			_n
	)		(((_x) + (_n) - 1) & ~((_n) - 1))

Definition at line 32 of file malloc.c.

Typedef Documentation

Header

typedef struct Header Header

HeapPool

typedef struct HeapPool HeapPool

Function Documentation

calloc()

void * calloc	(	size_t	num,
		size_t	sz
	)

Definition at line 154 of file malloc.c.

{
    return malloc(num*sz);
}

Here is the call graph for this function:

free()

void free

(

void *

mem

)

Definition at line 169 of file malloc.c.

{
    Header *hdr = (Header *)mem;
    hdr--;
 
    if (mem == NULL)
        return;
 
    assert(hdr->magic == HEAP_MAGIC);
 
    if (hdr->size > HEAP_MAX_POOLSIZE)
        free_large(hdr);
    else
        free_small(hdr);
}

Here is the call graph for this function:

Here is the caller graph for this function:

free_large()

static void free_large ( Header *  mem )

static

Definition at line 148 of file malloc.c.

{
    munmap(mem, mem->size);
}

Here is the call graph for this function:

Here is the caller graph for this function:

free_small()

static void free_small ( Header *  mem )

static

Definition at line 115 of file malloc.c.

{
    int idx = size_to_idx(mem->size);
 
    mem->next = pool[idx].free;
    pool[idx].free = mem;
}

Here is the call graph for this function:

Here is the caller graph for this function:

grow_small()

static void grow_small ( int  idx )

static

Definition at line 67 of file malloc.c.

{
    int i;
    size_t bucketSz = (1 << idx) * 64; // Compute bucket size
    char *addr = (char *)pool[idx].top;
 
    addr = (char *)mmap(addr, bucketSz * HEAP_INCREMENT,
                        PROT_READ|PROT_WRITE, MAP_ANON|MAP_FIXED,
                        -1, 0);
    if (addr == NULL) {
        return;
    }
 
    // Update top pointer
    pool[idx].top += bucketSz * HEAP_INCREMENT;
 
    for (i = 0; i < HEAP_INCREMENT; i++) {
        Header *obj = (Header *)(addr + i * bucketSz);
 
        obj->magic = HEAP_MAGIC;
        obj->status = 0;
        obj->size = bucketSz - sizeof(Header);
        obj->next = pool[idx].free;
        pool[idx].free = obj;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

malloc()

void * malloc

(

size_t

sz

)

Definition at line 160 of file malloc.c.

{
    if (sz > HEAP_MAX_POOLSIZE)
        return malloc_large(sz);
    else
        return malloc_small(sz);
}

Here is the call graph for this function:

Here is the caller graph for this function:

malloc_large()

static void * malloc_large ( size_t  sz )

static

Definition at line 124 of file malloc.c.

{
    uintptr_t ptr = largePool.top;
    uintptr_t realSz = ROUNDUP(sz, 4096);
    Header *addr;
 
    addr = (Header *)mmap((void *)ptr, realSz,
                          PROT_READ|PROT_WRITE, MAP_ANON|MAP_FIXED,
                          -1, 0);
    if (addr == NULL) {
        return NULL;
    }
 
    addr->magic = HEAP_MAGIC;
    addr->status = 0;
    addr->size = realSz;
    addr->next = 0;
 
    largePool.top += realSz;
 
    return (void *)(addr + 1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

malloc_small()

static void * malloc_small ( size_t  sz )

static

Definition at line 95 of file malloc.c.

{
    int idx = size_to_idx(sz);
    Header *hdr;
 
    // Grow pool if freelist is empty
    if (pool[idx].free == 0)
        grow_small(idx);
 
    // Malloc failed
    if (pool[idx].free == 0)
        return NULL;
 
    hdr = pool[idx].free;
    pool[idx].free = hdr->next;
 
    return (void *)(hdr + 1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

size_to_idx()

static int size_to_idx ( size_t  sz )

static

Definition at line 52 of file malloc.c.

{
    int i;
    size_t bucketSz = 64;
 
    for (i = 0; ; i++) {
        if ((bucketSz - sizeof(Header)) >= sz) {
            return i;
        }
 
        bucketSz *= 2;
    }
}

Here is the caller graph for this function:

Variable Documentation

largePool

HeapPool largePool = { 0, 0, (Header *)0, 0x4C000000, 0x4C000000 }

static

Definition at line 49 of file malloc.c.

pool

HeapPool pool[HEAP_POOLS]

static

Initial value:

= {
    { 0, 0, (Header *)0, 0x400000000, 0x400000000 }, 
    { 0, 0, (Header *)0, 0x410000000, 0x410000000 }, 
    { 0, 0, (Header *)0, 0x420000000, 0x420000000 }, 
    { 0, 0, (Header *)0, 0x430000000, 0x430000000 }, 
    { 0, 0, (Header *)0, 0x440000000, 0x440000000 }, 
    { 0, 0, (Header *)0, 0x450000000, 0x450000000 }, 
    { 0, 0, (Header *)0, 0x460000000, 0x460000000 }, 
    { 0, 0, (Header *)0, 0x470000000, 0x470000000 }, 
    { 0, 0, (Header *)0, 0x480000000, 0x480000000 }, 
    { 0, 0, (Header *)0, 0x490000000, 0x490000000 }, 
    { 0, 0, (Header *)0, 0x4A0000000, 0x4A0000000 }, 
    { 0, 0, (Header *)0, 0x4B0000000, 0x4B0000000 }, 
}

Definition at line 34 of file malloc.c.