COMS 4995 Advanced Systems Programming

Index of 2025-1/code/12/malloctopus-part2

Parent directory
Makefile
mm-test.c
mm.c
mm.h

Makefile

CC=gcc
CFLAGS=-g -Wall -I../libmem
LDFLAGS=-L../libmem
LDLIBS=-lmem

mm-test: mm.o mm-test.o

mm.o: mm.h

mm-test.o: mm.h

.PHONY: clean
clean:
	rm -f *.o mm-test

.PHONY: all
all: clean mm-test

mm-test.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <pthread.h>

#include "mm.h"

void inc(uint64_t *val) {
    for (int i = 0; i < 1e7; i++)
        ++*val;
    printf("%lu\n", *val);
}

void* inc_thread(void *v) {
    inc(v);
    return NULL;
}

int main(int argc, char **argv)
{
    mm_init();

    void *unused = mm_malloc(32);
    uint64_t *p = mm_malloc(8);
    uint64_t *q = mm_malloc(8);

    mm_checkheap(1);

    // Single-threaded
    inc(p);
    inc(q);

#if 0
    // Multi-threaded
    pthread_t t1, t2;
    pthread_create(&t1, NULL, &inc_thread, p);
    pthread_create(&t2, NULL, &inc_thread, q);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
#endif

    mm_free(p);
    mm_free(q);
    mm_free(unused);
    mm_deinit();
}

mm.c

/*
 * mm.c - A 64-bit port of CSAPP's 32-bit implicit free list allocator.
 *
 * Simple allocator based on implicit free lists, first-fit placement, and
 * boundary tag coalescing, as described in the CS:APP3e text. Blocks must be
 * aligned to doubleword (16 byte) boundaries. Minimum block size is 32 bytes.
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

#include "mm.h"
#include "mem.h"

#define  WORD_SIZE    8
#define DWORD_SIZE   16
#define  PAGE_SIZE 4096

typedef struct {
    // Note that this diverges from CSAPP's header semantics. Here, the size
    // field stores the full block size in bytes using 60 bits. This is more
    // than sufficient -- Linux uses 48 or 57 bits for virtual addresses. We do
    // not use any part of those 60 bits to store the allocated bit. The three
    // bits after size are reserved for future use and the last bit is the
    // allocated bit.
    uint64_t      size : 60;
    uint64_t    unused :  3;
    uint64_t allocated :  1;

    char payload[];
} header_t;

typedef struct {
    uint64_t      size : 60;
    uint64_t    unused :  3;
    uint64_t allocated :  1;
} footer_t;

static inline header_t *header(void *payload) {
    return (header_t *)((char *)payload - sizeof(header_t));
}

static inline footer_t *footer(void *payload) {
    return (footer_t *)((char *)payload + header(payload)->size
                        - sizeof(header_t) - sizeof(footer_t));
}

static inline void *next_payload(void *payload) {
    return (char *)payload + header(payload)->size;
}

static inline void *prev_payload(void *payload) {
    footer_t *prev_footer = (footer_t *)((char *)header(payload)
                                         - sizeof(footer_t));
    return (char *)payload - prev_footer->size;
}

char *heap_listp = 0;  /* Pointer to prologue's zero-byte payload */

/* Function prototypes for internal helper routines */
static void *extend_heap(size_t words);
static void place(void *payload, size_t asize);
static void *find_fit(size_t asize);
static void *coalesce(void *payload);
static void printblock(void *payload);
static void checkheap(int verbose);
static void checkblock(void *payload);

/*
 * mm_init - Initialize the memory manager
 */
void mm_init(void)
{
    // Sanity checks
    assert(sizeof(header_t) == WORD_SIZE);
    assert(sizeof(footer_t) == WORD_SIZE);

    mem_init();

    // Allocate leading padding, prologue, and epilogue
    char *p;
    if ((p = mem_sbrk(4 * WORD_SIZE)) == (void *)-1) {
        perror("mem_sbrk");
        exit(1);
    }

    // 8-byte leading padding
    memset(p, 0, WORD_SIZE);
    // Initialize prologue
    p += DWORD_SIZE;
    header(p)->size = DWORD_SIZE;
    header(p)->allocated = 1;
    footer(p)->size = DWORD_SIZE;
    footer(p)->allocated = 1;
    // Initialize epilogue
    p += DWORD_SIZE;
    header(p)->size = 0;
    header(p)->allocated = 1;
    // Set heap_listp to the prologue's zero-byte payload
    heap_listp = p - DWORD_SIZE;

    // Extend the empty heap with a free block of PAGE_SIZE bytes
    if (extend_heap(PAGE_SIZE / WORD_SIZE) == NULL) {
        perror("extend_heap");
        exit(1);
    }
}

void mm_deinit(void)
{
    mem_deinit();
}

/*
 * mm_malloc - Allocate a block with at least size bytes of payload
 */
void *mm_malloc(size_t size)
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *payload;

    if (heap_listp == 0) {
        mm_init();
    }
    /* Ignore spurious requests */
    if (size == 0) {
        return NULL;
    }

    if (size <= DWORD_SIZE) {
        // Minimum block size is 32 bytes
        asize = 2 * DWORD_SIZE;
    } else {
        // 1. Add 16 bytes for header and footer
        // 2. Round up to a multiple of 16 bytes for alignment
        asize = DWORD_SIZE *
                ((size + DWORD_SIZE + (DWORD_SIZE - 1)) / DWORD_SIZE);
    }

    /* Search the free list for a fit */
    if ((payload = find_fit(asize)) != NULL) {
        place(payload, asize);
        return payload;
    }

    /* No fit found. Get more memory in PAGE_SIZE chunks and place the block */
    extendsize = ((asize + PAGE_SIZE - 1) / PAGE_SIZE) * PAGE_SIZE;
    if ((payload = extend_heap(extendsize / WORD_SIZE)) == NULL) {
        return NULL;
    }
    place(payload, asize);
    return payload;
}

/*
 * mm_free - Free a block
 */
void mm_free(void *payload)
{
    if (payload == NULL) {
        return;
    }

    header(payload)->allocated = footer(payload)->allocated = 0;
    coalesce(payload);
}

/*
 * coalesce - Boundary tag coalescing. Return ptr to coalesced payload
 */
static void *coalesce(void *payload)
{
    void *prev = prev_payload(payload);
    void *next = next_payload(payload);

    uint64_t prev_alloc = header(prev)->allocated;
    uint64_t next_alloc = header(next)->allocated;

    uint64_t size = header(payload)->size;

    if (!prev_alloc) {
        size += header(prev)->size;

        // Coalesced free block starts at prev now
        payload = prev;
    }

    if (!next_alloc) {
        size += header(next)->size;
    }

    // Set size of coalesced block
    header(payload)->size = size;
    footer(payload)->size = size;

    return payload;
}

/*
 * mm_checkheap - Check the heap for correctness
 */
void mm_checkheap(int verbose)
{
    checkheap(verbose);
}

/*
 * The remaining routines are internal helper routines
 */

/*
 * extend_heap - Extend heap with free block and return its payload pointer
 */
static void *extend_heap(size_t words)
{
    char *p;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WORD_SIZE : words * WORD_SIZE;
    if ((p = mem_sbrk(size)) == (void *)-1) {
        return NULL;
    }

    /* The old epilogue header is now the header for the new free block.
     * Initialize the free block header/footer. */
    header(p)->size = size;
    footer(p)->size = size;
    header(p)->allocated = footer(p)->allocated = 0;

    /* Initalize the new epilogue header */
    header(next_payload(p))->size = 0;
    header(next_payload(p))->allocated = 1;

    /* Coalesce if the previous block was free */
    return coalesce(p);
}

/*
 * place - Place block of asize bytes at start of free block p
 *         and split if remainder would be at least minimum block size
 */
static void place(void *p, size_t asize)
{
    uint64_t csize = header(p)->size;

    if ((csize - asize) >= (2 * DWORD_SIZE)) {
        header(p)->size = asize;
        footer(p)->size = asize;
        header(p)->allocated = footer(p)->allocated = 1;

        // q is a new free block left over after placing p
        void *q = next_payload(p);
        header(q)->size = csize - asize;
        footer(q)->size = csize - asize;
        header(q)->allocated = footer(q)->allocated = 0;
    } else {
        // There was no leftover
        header(p)->allocated = footer(p)->allocated = 1;
    }
}

/*
 * find_fit - Find a fit for a block with asize bytes
 */
static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *p;
    for (p = heap_listp; header(p)->size > 0; p = next_payload(p)) {
        if (!header(p)->allocated && asize <= header(p)->size) {
            return p;
        }
    }
    return NULL;
}

static void printblock(void *p)
{
    uint64_t hsize, halloc, fsize, falloc;

    hsize = header(p)->size;
    halloc = header(p)->allocated;
    fsize = footer(p)->size;
    falloc = footer(p)->allocated;

    if (hsize == 0) {
        printf("%p: EOL\n", p);
        return;
    }

    printf("%p: header: [%lu:%c] footer: [%lu:%c]\n", p,
           hsize, (halloc ? 'a' : 'f'),
           fsize, (falloc ? 'a' : 'f'));
}

static void checkblock(void *p)
{
    if ((uint64_t)p % DWORD_SIZE) {
        printf("Error: %p is not doubleword aligned\n", p);
        exit(1);
    }

    if (header(p)->size != footer(p)->size ||
        header(p)->allocated != footer(p)->allocated) {
        printf("Error: header does not match footer\n");
        exit(1);
    }
}

/*
 * checkheap - Minimal check of the heap for consistency
 */
void checkheap(int verbose)
{
    char *p = heap_listp;

    if (verbose) {
        printf("Heap (%p):\n", heap_listp);
    }

    // Check prologue
    if (header(heap_listp)->size != DWORD_SIZE ||
        header(heap_listp)->allocated == 0) {
        printf("Bad prologue header\n");
        exit(1);
    }
    checkblock(heap_listp);

    // Check all blocks
    for (p = heap_listp; header(p)->size > 0; p = next_payload(p)) {
        if (verbose) {
            printblock(p);
        }
        checkblock(p);
    }

    // Check epilogue
    if (verbose) {
        printblock(p);
    }
    if (header(p)->size != 0 || header(p)->allocated == 0) {
        printf("Bad epilogue header\n");
        exit(1);
    }
}

mm.h

#ifndef __MM_H__
#define __MM_H__
#include <stddef.h>

void mm_init(void);
void mm_deinit(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void mm_checkheap(int verbose);

#endif