Agent Work: Dynamic Memory Allocator

Claude Sonnet 4.6 · COMP 321: Introduction to Computer Systems

COMP 321: Introduction to Computer Systems

Project 5: Malloc

Overview

In this lab you will be writing a dynamic memory allocator for C programs, i.e., your own version of the malloc, free, and realloc routines. You are encouraged to explore the design space creatively and implement an allocator that is correct, efficient, and fast.

Project Description

Your dynamic memory allocator will consist of the following four functions, which are declared in mm.h and defined in mm.c.

int   mm_init(void);
void *mm_malloc(size_t size);
void  mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

The mm.c file that we have given you implements a simple memory allocator based on an implicit free list, first-fit placement, and boundary-tag coalescing, as described in the CS:APP3e text. Using this as a starting place, modify these functions (and possibly define other private static functions), so that they obey the following semantics:

mm_init: Before calling mm_malloc, mm_realloc, or mm_free, the application program (i.e., the trace-driven driver program that you will use to evaluate your implementation) calls mm_init to perform any necessary initialization, such as allocating the initial heap area. The return value should be -1 if there was a problem in performing the initialization, and 0 otherwise.

The driver will call mm_init before running each trace (and after resetting the brk pointer). Therefore, your mm_init function should be able to reinitialize all state in your allocator each time it is called. In other words, you should not assume that it will only be called once.

mm_malloc: The mm_malloc routine returns a pointer to an allocated block with a payload of at least size bytes that begins at an 8-byte aligned address. The entire allocated block should lie within the heap region and should not overlap with any other allocated chunk.

mm_free: The mm_free routine frees the block pointed to by ptr. It returns nothing. This routine is only guaranteed to work when the passed pointer (ptr) was returned by an earlier call to mm_malloc or mm_realloc and has not yet been freed.

mm_realloc: The mm_realloc routine returns a pointer to an allocated block with a payload of at least size bytes with the following constraints.

- if ptr is NULL, the effect of the call is equivalent to mm_malloc(size); - if size is equal to zero, the effect of the call is equivalent to mm_free(ptr) and the return value is NULL; - if ptr is not NULL, it must have been returned by an earlier call to mm_malloc or mm_realloc. The call to mm_realloc changes the size of the memory block pointed to by ptr (the *old block*) to provide a payload of size bytes and returns the address of the new block. The address of the new block might be the same as the old block, or it might be different, depending on your implementation, the amount of internal fragmentation in the old block, and the size of the realloc request.

The contents of the new block are the same as those of the old ptr block, up to the minimum of the old and new sizes. Everything else is uninitialized. For example, if the old block is 32 bytes and the new block is 48 bytes, then the first 32 bytes of the new block are identical to the first 32 bytes of the old block and the last 16 bytes are uninitialized. Similarly, if the old block is 32 bytes and the new block is 16 bytes, then the contents of the new block are identical to the first 16 bytes of the old block.

These semantics match those of the corresponding libc malloc, realloc, and free routines with one exception: If size is equal to zero, the mm_malloc and mm_realloc routines return NULL. Type man malloc for complete documentation.

*Note: Instead, the C standard specifies that malloc and realloc return a valid pointer, not NULL, when size is equal to zero. However, implementing the standard behavior is slightly more complex than returning NULL, and it doesn't teach you any additional lessons, so we chose not to specify it.*

Heap Consistency Checker

Dynamic memory allocators are notoriously tricky to program correctly and efficiently. They are difficult to program correctly because they involve a lot of untyped pointer manipulation. You will find it very helpful to write a heap checker that scans the heap and checks it for consistency.

Some examples of what a heap checker might check are:

Is every block in the free list marked as free?
Are there any contiguous free blocks that somehow escaped coalescing?
Is every free block actually in the free list?
Do the pointers in the free list point to valid free blocks?
Do any allocated blocks overlap?
Do the pointers in a heap block point to valid heap addresses?

Your heap checker will consist of the function void checkheap(bool verbose) in mm.c. This function should check any invariants or consistency conditions that you consider prudent. It should print out a descriptive error message when it discovers an inconsistency in the heap. You are not limited to the listed suggestions nor are you required to check all of them.

This consistency checker is intended to help you with debugging your memory allocator during development. However, the provided implementation of checkheap is only suited to a memory allocator that is based on an implicit free list. So, as you replace parts of the provided memory allocator, you should update the implementation of checkheap.

When you submit mm.c, make sure to remove any calls to checkheap as they would likely reduce your throughput score!

Support Routines

The memlib.c package simulates the memory system for your dynamic memory allocator. You can invoke the following functions in memlib.c:

void *mem_sbrk(intptr_t incr): Expands the heap by incr bytes, where incr is a positive non-zero integer and returns a generic pointer to the first byte of the newly allocated heap area. If there is an error, it returns (void *)-1. The semantics are identical to the Unix sbrk function, except that mem_sbrk accepts only a positive integer argument.

void *mem_heap_lo(void): Returns a generic pointer to the first byte in the heap.

void *mem_heap_hi(void): Returns a generic pointer to the last byte in the heap.

size_t mem_heapsize(void): Returns the current size of the heap in bytes.

size_t mem_pagesize(void): Returns the system's page size in bytes (4K on x86-64 Linux systems).

Files

Your workspace contains:

mm.c - Main source file (implement your solution here)
mm.h - Header file for mm.c
memlib.c, memlib.h - Memory system simulation
mdriver.c - Test driver program
config.h - Configuration for mdriver
clock.c, clock.h, fcyc.c, fcyc.h, fsecs.c, fsecs.h, ftimer.c, ftimer.h - Timing utilities
Makefile - Build specification
*.rep - Trace files for testing
writeup.md - Skeleton writeup file

The Trace-driven Driver Program

The driver program mdriver.c tests your mm.c package for correctness, space utilization, and throughput. The driver program is controlled by a set of *trace files*. Each trace file contains a sequence of allocate, reallocate, and free directions that instruct the driver to call your mm_malloc, mm_realloc, and mm_free routines in some sequence.

The driver mdriver.c accepts the following command line arguments:

-t <tracedir>: Look for the trace files in directory tracedir instead of the default directory defined in config.h.
-f <tracefile>: Use one particular tracefile for testing instead of the default set of tracefiles.
-h: Print a summary of the command line arguments.
-v: Verbose output. Print a performance breakdown for each tracefile in a compact table.
-V: More verbose output. Prints additional diagnostic information as each trace file is processed. Useful during debugging for determining which trace file is causing your malloc package to fail.

Programming Rules

You should not change the interface to any function declared in mm.h or memlib.h.

You should not invoke any memory-management related library calls or system calls. Therefore, you may not use malloc, calloc, free, realloc, sbrk, brk, or any variants of these calls in your code.

You are not allowed to define any global or static variables that are arrays or structs in your mm.c program. However, this does not mean that you are prohibited from using arrays and structs, only that the memory for holding them must come from your heap. You *are* allowed to declare a small number of scalar global variables such as integers, floats, and pointers in mm.c.

You are permitted to study the trace files and use your observations about them to inform the design of your dynamic memory allocator. Moreover, if you are implementing a segregated free list for keeping track of free blocks, you may use your observations to determine the number of free lists and the size range for each free list. However, your implementations of mm_malloc and mm_realloc are not allowed to explicitly test for any allocation sizes from the trace files, for example, if (size == 456) ..., unless that test is being used to select a free list. Likewise, you are not allowed to test for which trace file is being executed.

Your allocator must always return pointers that are aligned to 8-byte boundaries. The driver will enforce this requirement for you.

Notes

*Use the mdriver -f option.* During initial development, using tiny trace files will simplify debugging and testing. We have included two such trace files (short{1,2}-bal.rep) that you can use for initial debugging.

*Use the mdriver -v and -V options.* The -v option will give you a detailed summary for each trace file. The -V will also indicate when each trace file is read, which will help you isolate errors.

*Use a debugger.* A debugger will help you isolate and identify out of bounds memory references.

*Understand every line of the provided malloc implementation.* The textbook describes how this simple implicit free list allocator works. Don't start working on your own allocator until you understand everything about this simple allocator.

*Do your implementation in stages.* The first 9 traces contain requests to malloc and free. The last 2 traces contain requests for realloc, malloc, and free. We recommend that you start by getting your malloc and free routines working correctly and efficiently on the first 9 traces. Only then should you turn your attention to the realloc implementation. The provided realloc implementation works by simply calling your malloc and free routines. But, to get really good performance, you will need to build a smarter realloc that calls malloc and free less often.

*Don't forget what you've learned before.* There are many ways to write the code to manipulate pointers to insert and remove free blocks from a free list. The most complex and error-prone way would be to use the provided macros to try and manipulate raw memory as pointers. A better way would be to define a struct that contains next and previous pointers and cast block pointers into pointers to that struct. This is a common and important idiom in C.

*Use a profiler.* You may find gprof and/or gcov helpful for optimizing performance.

*Start early!* It is possible to write an efficient malloc package with a few pages of code. However, we can guarantee that it will be some of the most difficult and sophisticated code you have written so far in your career. So start early, and good luck!

Performance Scoring

Your performance score will be based on the following two metrics:

*Space utilization:* The peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via mm_malloc or mm_realloc but not yet freed via mm_free) and the size of the heap used by your allocator. The optimal ratio equals to 1. You should find good policies to minimize fragmentation in order to make this ratio as close as possible to the optimal.

*Throughput:* The average number of operations completed per second.

The driver program summarizes the performance of your allocator by computing a *performance index*, P, which is a weighted sum of the space utilization and throughput:

P = wU + (1 - w) min(1, T/T_target)

where U is your space utilization, T is your throughput, and T_target is the throughput of a reasonable malloc implementation on the default traces. The performance index favors throughput over space utilization, with a default of w = 0.4.

Observing that both memory and CPU cycles are expensive system resources, we adopt this formula to encourage balanced optimization of both memory utilization and throughput. Ideally, the performance index will reach P = w + (1 - w) = 1 or 100%. Since each metric will contribute at most w and 1 - w to the performance index, respectively, you should not go to extremes to optimize either the memory utilization or the throughput only. To receive a good score, you must achieve a balance between utilization and throughput.

The provided implementation already achieves a performance index of around 30/100. Your goal is to build a better memory allocator.

Testing

Use the grade tool to run the automated test suite:

# From the workspace directory
bin/grade .

# Or specify the workspace path
bin/grade ./workspaces/agent_malloc

The grade tool will compile your code and run correctness tests. For performance testing, use the malloc_perf tool:

# Run performance benchmark (after correctness tests pass)
bin/malloc_perf ./workspaces/agent_malloc

This runs the full trace suite and reports your utilization score (out of 40), throughput score (out of 60), and total performance index (out of 100). A performance index of 90 or higher is considered excellent.

--- *COMP 321: Introduction to Computer Systems, Rice University, Spring 2024*

Makefile501 B

makefile

CC      = cc
CFLAGS  = -std=gnu11 -Wall -Wextra -Werror -g -O2
LDLIBS  = -lm

OBJS    = mdriver.o mm.o memlib.o fsecs.o fcyc.o clock.o ftimer.o

mdriver: ${OBJS}
	${CC} ${CFLAGS} -o mdriver ${OBJS} ${LDLIBS}

mdriver.o: mdriver.c fsecs.h fcyc.h clock.h memlib.h config.h mm.h
memlib.o: memlib.c memlib.h
mm.o: mm.c mm.h memlib.h
fsecs.o: fsecs.c fsecs.h config.h
fcyc.o: fcyc.c fcyc.h
ftimer.o: ftimer.c ftimer.h config.h
clock.o: clock.c clock.h

clean:
	${RM} *.o mdriver core.[1-9]*

.PHONY: clean

Makefile501 B

makefile

CC      = cc
CFLAGS  = -std=gnu11 -Wall -Wextra -Werror -g -O2
LDLIBS  = -lm

OBJS    = mdriver.o mm.o memlib.o fsecs.o fcyc.o clock.o ftimer.o

mdriver: ${OBJS}
	${CC} ${CFLAGS} -o mdriver ${OBJS} ${LDLIBS}

mdriver.o: mdriver.c fsecs.h fcyc.h clock.h memlib.h config.h mm.h
memlib.o: memlib.c memlib.h
mm.o: mm.c mm.h memlib.h
fsecs.o: fsecs.c fsecs.h config.h
fcyc.o: fcyc.c fcyc.h
ftimer.o: ftimer.c ftimer.h config.h
clock.o: clock.c clock.h

clean:
	${RM} *.o mdriver core.[1-9]*

.PHONY: clean

mm.c17.0 KB

/*
 * Segregated free list allocator.
 *
 * Uses NUM_CLASSES size classes with explicit doubly-linked free lists.
 * List heads are stored in the heap before the prologue block.
 * Blocks use boundary tags (header + footer) for O(1) coalescing.
 * Free blocks contain pred/succ pointers for explicit list traversal.
 * LIFO insertion, first-fit search within each class then larger classes.
 *
 * Block layout:
 *   Allocated: [header (WSIZE)] [payload] [footer (WSIZE)]
 *   Free:      [header (WSIZE)] [pred ptr (WSIZE)] [succ ptr (WSIZE)] [...] [footer (WSIZE)]
 *
 * Heap layout after mm_init:
 *   [seg_list_0] ... [seg_list_19] [pad] [prologue_hdr] [prologue_ftr] [epilogue_hdr]
 */

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#include "memlib.h"
#include "mm.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
	/* Team name */
	"BSCS Bench",
	/* First member's full name */
	"BSCS Bench Agent",
	/* First member's NetID */
	"bscs1",
	/* Second member's full name (leave blank if none) */
	"",
	/* Second member's NetID (leave blank if none) */
	""
};

/* Basic constants and macros */
#define WSIZE      sizeof(void *)       /* Word and header/footer size (bytes) */
#define DSIZE      (2 * WSIZE)          /* Doubleword size (bytes) */
#define CHUNKSIZE  (1 << 12)            /* Extend heap by this amount (bytes) */

#define MAX(x, y)  ((x) > (y) ? (x) : (y))

/* Pack a size and allocated bit into a word. */
#define PACK(size, alloc)  ((size) | (alloc))

/* Read and write a word at address p. */
#define GET(p)       (*(uintptr_t *)(p))
#define PUT(p, val)  (*(uintptr_t *)(p) = (val))

/* Read the size and allocated fields from address p. */
#define GET_SIZE(p)   (GET(p) & ~(DSIZE - 1))
#define GET_ALLOC(p)  (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer. */
#define HDRP(bp)  ((char *)(bp) - WSIZE)
#define FTRP(bp)  ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks. */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* Segregated free list parameters */
#define NUM_CLASSES  20
/* Minimum block: header + pred_ptr + succ_ptr + footer */
#define MIN_BLOCK    (4 * WSIZE)

/* Access pred/succ pointers stored in a free block's payload. */
#define PRED(bp)     (*(char **)(bp))
#define SUCC(bp)     (*(char **)((char *)(bp) + WSIZE))

/* Access the free list head for class c (stored in heap before prologue). */
#define SEG_HEAD(c)  (*(char **)(seg_free_lists + (c) * WSIZE))

/* Global variables */
static char *seg_free_lists;  /* Pointer to start of seg list head area in heap */
static char *heap_listp;      /* Pointer to prologue block */

/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void *place(void *bp, size_t asize);
static void  insert_free(void *bp, size_t size);
static void  remove_free(void *bp);
static int   get_class(size_t size);

/* Function prototypes for heap consistency checker routines */
static void checkblock(void *bp);
static void printblock(void *bp);

/*
 * get_class - Return the segregated list class index for a block of given size.
 *   Class 0: size <= 32 (minimum block size)
 *   Class k: (2^(k+4)+1) to 2^(k+5), for k < NUM_CLASSES-1
 *   Class NUM_CLASSES-1: all larger sizes
 */
static int
get_class(size_t size)
{
	int c = 0;
	size_t threshold = MIN_BLOCK;  /* 32 bytes */

	while (c < NUM_CLASSES - 1 && threshold < size) {
		threshold <<= 1;
		c++;
	}
	return c;
}

/*
 * insert_free - Insert a free block at the front of its size class list (LIFO).
 */
static void
insert_free(void *bp, size_t size)
{
	int c = get_class(size);
	char *head = SEG_HEAD(c);

	PRED(bp) = NULL;
	SUCC(bp) = head;
	if (head != NULL)
		PRED(head) = bp;
	SEG_HEAD(c) = bp;
}

/*
 * remove_free - Remove a free block from its size class list.
 */
static void
remove_free(void *bp)
{
	int c = get_class(GET_SIZE(HDRP(bp)));
	char *prev = PRED(bp);
	char *next = SUCC(bp);

	if (prev != NULL)
		SUCC(prev) = next;
	else
		SEG_HEAD(c) = next;

	if (next != NULL)
		PRED(next) = prev;
}

/*
 * mm_init - Initialize the memory manager.
 *
 * Heap layout:
 *   [seg_list_0..19 (NUM_CLASSES words)] [pad] [prologue hdr] [prologue ftr] [epilogue hdr]
 */
int
mm_init(void)
{
	char *start, *init;
	int c;

	/* Allocate: NUM_CLASSES list heads + padding + prologue + epilogue */
	if ((start = mem_sbrk((NUM_CLASSES + 4) * WSIZE)) == (void *)-1)
		return -1;

	seg_free_lists = start;

	/* Initialize all free list heads to NULL */
	for (c = 0; c < NUM_CLASSES; c++)
		SEG_HEAD(c) = NULL;

	/* Set up prologue and epilogue after the seg list area */
	init = start + NUM_CLASSES * WSIZE;
	PUT(init, 0);                           /* Alignment padding */
	PUT(init + WSIZE, PACK(DSIZE, 1));      /* Prologue header */
	PUT(init + 2 * WSIZE, PACK(DSIZE, 1)); /* Prologue footer */
	PUT(init + 3 * WSIZE, PACK(0, 1));     /* Epilogue header */
	heap_listp = init + 2 * WSIZE;

	/*
	 * Do NOT pre-extend the heap here. Let the first mm_malloc extend on
	 * demand. This avoids creating a persistent CHUNKSIZE-byte free fragment
	 * when traces have large first allocations (> CHUNKSIZE), which would
	 * otherwise coalesce and leave a large unusable remainder.
	 */
	return 0;
}

/*
 * 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 */
	void *bp;

	if (size == 0)
		return NULL;

	/* Adjust block size to include overhead and alignment reqs. */
	if (size <= DSIZE)
		asize = 2 * DSIZE;
	else
		asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);

	/* Ensure minimum block size (for free list pointers) */
	if (asize < MIN_BLOCK)
		asize = MIN_BLOCK;

	/* Search free lists for a fit */
	if ((bp = find_fit(asize)) != NULL)
		return place(bp, asize);

	/* No fit found. Extend the heap. */
	extendsize = MAX(asize, CHUNKSIZE);
	if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
		return NULL;
	return place(bp, asize);
}

/*
 * mm_free - Free a block pointed to by bp.
 */
void
mm_free(void *bp)
{
	size_t size;

	if (bp == NULL)
		return;

	size = GET_SIZE(HDRP(bp));
	PUT(HDRP(bp), PACK(size, 0));
	PUT(FTRP(bp), PACK(size, 0));
	coalesce(bp);
}

/*
 * mm_realloc - Reallocate a block.
 * Optimized to avoid copying when possible:
 *   Case 1: Current block is big enough — shrink/keep as is.
 *   Case 2: Next block is free and combined size is sufficient — merge in place.
 *   Case 3: At end of heap (next is epilogue) — extend heap in place.
 *   Case 4: Fall back to malloc + memcpy + free.
 */
void *
mm_realloc(void *ptr, size_t size)
{
	size_t oldsize, asize;
	void *newptr;
	void *next;
	size_t next_size;

	if (size == 0) {
		mm_free(ptr);
		return NULL;
	}

	if (ptr == NULL)
		return mm_malloc(size);

	/* Adjust new size */
	if (size <= DSIZE)
		asize = 2 * DSIZE;
	else
		asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
	if (asize < MIN_BLOCK)
		asize = MIN_BLOCK;

	oldsize = GET_SIZE(HDRP(ptr));

	/* Case 1: Current block is already big enough */
	if (asize <= oldsize) {
		if (oldsize - asize >= MIN_BLOCK) {
			/* Split and free the remainder */
			PUT(HDRP(ptr), PACK(asize, 1));
			PUT(FTRP(ptr), PACK(asize, 1));
			next = NEXT_BLKP(ptr);
			PUT(HDRP(next), PACK(oldsize - asize, 0));
			PUT(FTRP(next), PACK(oldsize - asize, 0));
			coalesce(next);
		}
		return ptr;
	}

	next = NEXT_BLKP(ptr);
	next_size = GET_SIZE(HDRP(next));

	/* Case 2: Next block is free and combined is sufficient */
	if (!GET_ALLOC(HDRP(next)) && oldsize + next_size >= asize) {
		remove_free(next);
		size_t combined = oldsize + next_size;
		if (combined - asize >= MIN_BLOCK) {
			PUT(HDRP(ptr), PACK(asize, 1));
			PUT(FTRP(ptr), PACK(asize, 1));
			void *rem = NEXT_BLKP(ptr);
			PUT(HDRP(rem), PACK(combined - asize, 0));
			PUT(FTRP(rem), PACK(combined - asize, 0));
			insert_free(rem, combined - asize);
		} else {
			PUT(HDRP(ptr), PACK(combined, 1));
			PUT(FTRP(ptr), PACK(combined, 1));
		}
		return ptr;
	}

	/*
	 * Case 2.5: Next block is free (but combined isn't enough), and next
	 * is adjacent to the epilogue — absorb next and extend heap in place.
	 */
	if (!GET_ALLOC(HDRP(next)) && GET_SIZE(HDRP(NEXT_BLKP(next))) == 0) {
		size_t combined = oldsize + next_size;
		size_t need = asize - combined;
		size_t extend_amount = MAX(need, CHUNKSIZE);
		extend_amount = DSIZE * ((extend_amount + DSIZE - 1) / DSIZE);

		if (mem_sbrk(extend_amount) == (void *)-1)
			return NULL;

		remove_free(next);
		size_t total = combined + extend_amount;
		size_t rem_size = total - asize;

		if (rem_size >= MIN_BLOCK) {
			PUT(HDRP(ptr), PACK(asize, 1));
			PUT(FTRP(ptr), PACK(asize, 1));
			void *rem = NEXT_BLKP(ptr);
			PUT(HDRP(rem), PACK(rem_size, 0));
			PUT(FTRP(rem), PACK(rem_size, 0));
			PUT(HDRP(NEXT_BLKP(rem)), PACK(0, 1));
			insert_free(rem, rem_size);
		} else {
			PUT(HDRP(ptr), PACK(total, 1));
			PUT(FTRP(ptr), PACK(total, 1));
			PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));
		}
		return ptr;
	}

	/*
	 * Case 3: Next block is epilogue (size 0) — extend heap in place.
	 *
	 * After mem_sbrk(extend_amount):
	 *   Total available = oldsize (old block) + WSIZE (old epilogue reused
	 *   as free block header by convention) + extend_amount (new memory).
	 *   But in terms of block accounting: rem_size = oldsize + extend_amount - asize.
	 */
	if (next_size == 0) {
		size_t need = asize - oldsize;
		size_t extend_amount = MAX(need, CHUNKSIZE);
		/* Align to DSIZE */
		extend_amount = DSIZE * ((extend_amount + DSIZE - 1) / DSIZE);

		if (mem_sbrk(extend_amount) == (void *)-1)
			return NULL;

		size_t rem_size = oldsize + extend_amount - asize;

		if (rem_size >= MIN_BLOCK) {
			PUT(HDRP(ptr), PACK(asize, 1));
			PUT(FTRP(ptr), PACK(asize, 1));
			void *rem = NEXT_BLKP(ptr);
			PUT(HDRP(rem), PACK(rem_size, 0));
			PUT(FTRP(rem), PACK(rem_size, 0));
			PUT(HDRP(NEXT_BLKP(rem)), PACK(0, 1)); /* new epilogue */
			insert_free(rem, rem_size);
		} else {
			size_t total_size = oldsize + extend_amount;
			PUT(HDRP(ptr), PACK(total_size, 1));
			PUT(FTRP(ptr), PACK(total_size, 1));
			PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1)); /* new epilogue */
		}
		return ptr;
	}

	/*
	 * Case 0: Previous block is free and combined size is sufficient —
	 *   merge backward using memmove. Avoids expensive malloc+copy+free
	 *   when the block is sandwiched (allocated neighbor on the right,
	 *   free space on the left).
	 */
	{
		void *prev = PREV_BLKP(ptr);
		if (!GET_ALLOC(FTRP(prev))) {
			size_t prev_size = GET_SIZE(HDRP(prev));
			if (prev_size + oldsize >= asize) {
				remove_free(prev);
				size_t combined = prev_size + oldsize;
				size_t copysize = oldsize - DSIZE;
				/* Move payload to new (lower) location */
				memmove(prev, ptr, copysize);
				size_t rem = combined - asize;
				if (rem >= MIN_BLOCK) {
					PUT(HDRP(prev), PACK(asize, 1));
					PUT(FTRP(prev), PACK(asize, 1));
					void *rem_block = NEXT_BLKP(prev);
					PUT(HDRP(rem_block), PACK(rem, 0));
					PUT(FTRP(rem_block), PACK(rem, 0));
					insert_free(rem_block, rem);
				} else {
					PUT(HDRP(prev), PACK(combined, 1));
					PUT(FTRP(prev), PACK(combined, 1));
				}
				return prev;
			}
		}
	}

	/* Case 4: Must allocate a new block and copy */
	newptr = mm_malloc(size);
	if (newptr == NULL)
		return NULL;

	size_t copysize = oldsize - DSIZE; /* payload size of old block */
	if (size < copysize)
		copysize = size;
	memcpy(newptr, ptr, copysize);
	mm_free(ptr);
	return newptr;
}

/*
 * The following routines are internal helper routines.
 */

/*
 * coalesce - Coalesce adjacent free blocks using boundary tags.
 *   Removes neighbors from free lists, merges, then inserts merged block.
 */
static void *
coalesce(void *bp)
{
	bool prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
	bool next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
	size_t size = GET_SIZE(HDRP(bp));

	if (prev_alloc && next_alloc) {
		/* Case 1: no neighbors to coalesce */
		insert_free(bp, size);
		return bp;
	} else if (prev_alloc && !next_alloc) {
		/* Case 2: coalesce with next */
		void *next = NEXT_BLKP(bp);
		remove_free(next);
		size += GET_SIZE(HDRP(next));
		PUT(HDRP(bp), PACK(size, 0));
		PUT(FTRP(bp), PACK(size, 0));
		insert_free(bp, size);
		return bp;
	} else if (!prev_alloc && next_alloc) {
		/* Case 3: coalesce with prev */
		void *prev = PREV_BLKP(bp);
		remove_free(prev);
		size += GET_SIZE(HDRP(prev));
		PUT(FTRP(bp), PACK(size, 0));
		PUT(HDRP(prev), PACK(size, 0));
		insert_free(prev, size);
		return prev;
	} else {
		/* Case 4: coalesce with both prev and next */
		void *prev = PREV_BLKP(bp);
		void *next = NEXT_BLKP(bp);
		remove_free(prev);
		remove_free(next);
		size += GET_SIZE(HDRP(prev)) + GET_SIZE(HDRP(next));
		PUT(HDRP(prev), PACK(size, 0));
		PUT(FTRP(next), PACK(size, 0));
		insert_free(prev, size);
		return prev;
	}
}

/*
 * extend_heap - Extend the heap with a free block of at least "words" words.
 *   The old epilogue header becomes the new free block's header.
 */
static void *
extend_heap(size_t words)
{
	size_t size;
	void *bp;

	/* Allocate even number of words to maintain DSIZE alignment. */
	size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
	if ((bp = mem_sbrk(size)) == (void *)-1)
		return NULL;

	PUT(HDRP(bp), PACK(size, 0));          /* Free block header */
	PUT(FTRP(bp), PACK(size, 0));          /* Free block footer */
	PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

	return coalesce(bp);
}

/*
 * find_fit - Find a free block of at least asize bytes.
 *   Searches from the smallest size class that could contain a block of
 *   size asize, moving to larger classes if no fit is found.
 *   Uses first-fit within each class.
 */
static void *
find_fit(size_t asize)
{
	int c = get_class(asize);

	for (; c < NUM_CLASSES; c++) {
		char *bp = SEG_HEAD(c);
		while (bp != NULL) {
			if (GET_SIZE(HDRP(bp)) >= asize)
				return bp;
			bp = SUCC(bp);
		}
	}
	return NULL;
}

/*
 * place - Place a block of asize bytes in free block bp.
 *   Split if remainder >= MIN_BLOCK. Returns pointer to the allocated block.
 *
 *   For large allocations (asize >= 96 bytes), place at the END of the free
 *   block so the small remainder stays at the front. This reduces fragmentation
 *   for traces with interleaved small and large allocations.
 */
static void *
place(void *bp, size_t asize)
{
	size_t csize = GET_SIZE(HDRP(bp));

	remove_free(bp);

	if (csize - asize >= MIN_BLOCK) {
		/*
		 * For medium-sized allocations (96–2047 bytes), place at the end
		 * of the free block so the small remainder stays at the front.
		 * This reduces fragmentation for interleaved small/large patterns.
		 * Very large blocks (>= 2048) are excluded because they tend to be
		 * realloc'd in-place and should stay adjacent to the free space.
		 */
		if (asize >= 96 && asize < 2048) {
			/* Place at end: small remainder stays at front */
			size_t rem_size = csize - asize;
			PUT(HDRP(bp), PACK(rem_size, 0));
			PUT(FTRP(bp), PACK(rem_size, 0));
			insert_free(bp, rem_size);
			void *new_bp = NEXT_BLKP(bp);
			PUT(HDRP(new_bp), PACK(asize, 1));
			PUT(FTRP(new_bp), PACK(asize, 1));
			return new_bp;
		} else {
			/* Place at front: remainder goes to end */
			PUT(HDRP(bp), PACK(asize, 1));
			PUT(FTRP(bp), PACK(asize, 1));
			void *next = NEXT_BLKP(bp);
			PUT(HDRP(next), PACK(csize - asize, 0));
			PUT(FTRP(next), PACK(csize - asize, 0));
			insert_free(next, csize - asize);
			return bp;
		}
	} else {
		PUT(HDRP(bp), PACK(csize, 1));
		PUT(FTRP(bp), PACK(csize, 1));
		return bp;
	}
}

/*
 * The remaining routines are heap consistency checker routines.
 */

/*
 * checkblock - Perform a minimal check on block bp.
 */
static void
checkblock(void *bp)
{
	if ((uintptr_t)bp % DSIZE)
		printf("Error: %p is not doubleword aligned\n", bp);
	if (GET(HDRP(bp)) != GET(FTRP(bp)))
		printf("Error: header does not match footer\n");
}

/*
 * checkheap - Perform a minimal check of the heap for consistency.
 *   Verifies prologue, epilogue, and all blocks between them.
 */
void
checkheap(bool verbose)
{
	void *bp;

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

	if (GET_SIZE(HDRP(heap_listp)) != DSIZE || !GET_ALLOC(HDRP(heap_listp)))
		printf("Bad prologue header\n");
	checkblock(heap_listp);

	for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
		if (verbose)
			printblock(bp);
		checkblock(bp);
	}

	if (verbose)
		printblock(bp);
	if (GET_SIZE(HDRP(bp)) != 0 || !GET_ALLOC(HDRP(bp)))
		printf("Bad epilogue header\n");
}

/*
 * printblock - Print a block's header and footer info.
 */
static void
printblock(void *bp)
{
	size_t hsize, fsize;
	bool halloc, falloc;

	hsize = GET_SIZE(HDRP(bp));
	halloc = GET_ALLOC(HDRP(bp));
	fsize = GET_SIZE(FTRP(bp));
	falloc = GET_ALLOC(FTRP(bp));

	if (hsize == 0) {
		printf("%p: end of heap\n", bp);
		return;
	}

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

Section: Design Description

Score: 0/10 points

Assessment:

What was provided: The student did not provide any design description. The submission contains only the placeholder text: "[Replace with an English description of your submission's design.]"

Strengths:

None — no content was provided.

Errors/Gaps:

No description of block structure (header/footer format, minimum block size, alignment)
No description of free list organization (implicit, explicit, or segregated)
No description of allocation policy (first fit, next fit, best fit)
No description of splitting strategy
No description of coalescing strategy
No description of heap extension behavior

Detailed Feedback: The student left the template placeholder text unchanged, providing no information whatsoever about their allocator's design. A complete answer would have described the block structure (header/footer format, minimum block size, alignment requirements), the free list organization (e.g., segregated free lists with size classes), the allocation search strategy, when and how blocks are split, the coalescing approach, and heap extension policy. Without any content, no credit can be awarded.

Rubric Breakdown:

Block Structure: 0/2 - not addressed
Free List Organization: 0/2 - not addressed
Allocation Policy: 0/2 - not addressed
Splitting Strategy: 0/1.5 - not addressed
Coalescing Strategy: 0/1.5 - not addressed
Heap Extension: 0/1 - not addressed

---

Section: checkheap() Description

Score: 0/10 points

Assessment:

What was provided: The student did not provide any description of their heap consistency checker. The submission contains only the placeholder text: "[Replace with an English description of your submission's heap consistency checker.]"

Strengths:

None — no content was provided.

Errors/Gaps:

No description of block-level checks (header/footer consistency, size validation, alignment, bounds)
No description of free list checks (marked as free, valid pointers, consistent linking)
No description of coalescing checks (no consecutive free blocks)
No description of count consistency checks
No description of any additional checks (prologue/epilogue, heap integrity)

Detailed Feedback: The student left the template placeholder text unchanged, providing no information about what their checkheap() function verifies. A complete answer would have described the specific invariants being checked: block-level consistency (header/footer match, size and alignment validation, heap bounds), free list integrity (all listed blocks are free, pointer consistency, correct size class membership), coalescing verification (no adjacent free blocks), and count consistency (free block counts match between heap scan and list traversal). Without any content, no credit can be awarded.

Rubric Breakdown:

Block-Level Checks: 0/3 - not addressed
Free List Checks: 0/3 - not addressed
Coalescing Check: 0/2 - not addressed
Count Consistency: 0/1 - not addressed
Additional Checks: 0/1 - not addressed

---

Overall Summary

Section	Score	Notes
Design Description	0/10	Placeholder text only — no content provided
checkheap() Description	0/10	Placeholder text only — no content provided
Total	0/20

General Comments:

The student submitted the writeup template without modifying any of the placeholder text. None of the required written questions were answered. Both the design description and the checkheap() description sections are completely empty of substantive content. To earn credit, the student would need to describe their allocator's design (block format, free list organization, allocation/splitting/coalescing strategies) and explain what consistency checks their heap checker performs. Even a brief or partial description would have earned partial credit.

Total: 0/20

.mcp.json

diff --git a/.mcp.json b/.mcp.json
deleted file mode 100644
index c8b4d48..0000000
--- a/.mcp.json
+++ /dev/null
@@ -1,11 +0,0 @@
-{
-  "mcpServers": {
-    "bscs-bench": {
-      "command": "/Users/bebe/Code/bscs-bench/bin/bscs-mcp",
-      "args": [
-        "--workspace",
-        "/Users/bebe/Code/bscs-bench/workspaces/comp321_malloc_sonnet"
-      ]
-    }
-  }
-}
\ No newline at end of file

Agent Work: Dynamic Memory Allocator

COMP 321: Introduction to Computer Systems

Project 5: Malloc

Overview

Project Description

Heap Consistency Checker

Support Routines

Files

The Trace-driven Driver Program

Programming Rules

Notes

Performance Scoring

Testing

Section: Design Description

Score: 0/10 points

Assessment:

Rubric Breakdown:

Section: checkheap() Description

Score: 0/10 points

Assessment:

Rubric Breakdown:

Overall Summary

General Comments:

Sub-Model Usage