* @file mm.c
* @brief A 64-bit struct-based implicit free list memory allocator
* 15-213: Introduction to Computer Systems
* TODO: insert your documentation here. 🙂
Copyright By PowCoder代写 加微信 powcoder
*************************************************************************
* ADVICE FOR STUDENTS.
* – Step 0: Please read the writeup!
* – Step 1: Write your heap checker.
* – Step 2: Write contracts / debugging assert statements.
* – Good luck, and have fun!
*************************************************************************
* @author Your Name
#include
#include
#include
#include
#include
#include
#include
#include
#include “memlib.h”
#include “mm.h”
/* Do not change the following! */
#ifdef DRIVER
/* create aliases for driver tests */
#define malloc mm_malloc
#define free mm_free
#define realloc mm_realloc
#define calloc mm_calloc
#define memset mem_memset
#define memcpy mem_memcpy
#endif /* def DRIVER */
/* You can change anything from here onward */
*****************************************************************************
* If DEBUG is defined (such as when running mdriver-dbg), these macros *
* are enabled. You can use them to print debugging output and to check *
* contracts only in debug mode. *
* *
* Only debugging macros with names beginning “dbg_” are allowed. *
* You may not define any other macros having arguments. *
*****************************************************************************
#ifdef DEBUG
/* When DEBUG is defined, these form aliases to useful functions */
#define dbg_printf(…) printf(__VA_ARGS__)
#define dbg_requires(expr) assert(expr)
#define dbg_assert(expr) assert(expr)
#define dbg_ensures(expr) assert(expr)
#define dbg_printheap(…) print_heap(__VA_ARGS__)
/* When DEBUG is not defined, no code gets generated for these */
/* The sizeof() hack is used to avoid “unused variable” warnings */
#define dbg_printf(…) (sizeof(__VA_ARGS__), -1)
#define dbg_requires(expr) (sizeof(expr), 1)
#define dbg_assert(expr) (sizeof(expr), 1)
#define dbg_ensures(expr) (sizeof(expr), 1)
#define dbg_printheap(…) ((void)sizeof(__VA_ARGS__))
/* Basic constants */
typedef uint64_t word_t;
/** @brief Word and header size (bytes) */
static const size_t wsize = sizeof(word_t);
/** @brief Double word size (bytes) */
static const size_t dsize = 2 * wsize;
/** @brief Minimum block size (bytes) */
static const size_t min_block_size = 2 * dsize;
* TODO: explain what chunksize is
* (Must be divisible by dsize)
static const size_t chunksize = (1 << 12);
* TODO: explain what alloc_mask is
static const word_t alloc_mask = 0x1;
* TODO: explain what size_mask is
static const word_t size_mask = ~(word_t)0xF;
/** @brief Represents the header and payload of one block in the heap */
typedef struct block {
/** @brief Header contains size + allocation flag */
word_t header;
* @brief A pointer to the block payload.
* TODO: feel free to delete this comment once you've read it carefully.
* We don't know what the size of the payload will be, so we will declare
* it as a zero-length array, which is a GCC compiler extension. This will
* allow us to obtain a pointer to the start of the payload.
* WARNING: A zero-length array must be the last element in a struct, so
* there should not be any struct fields after it. For this lab, we will
* allow you to include a zero-length array in a union, as long as the
* union is the last field in its containing struct. However, this is
* compiler-specific behavior and should be avoided in general.
* WARNING: DO NOT cast this pointer to/from other types! Instead, you
* should use a union to alias this zero-length array with another struct,
* in order to store additional types of data in the payload memory.
char payload[0];
* TODO: delete or replace this comment once you've thought about it.
* Why can't we declare the block footer here as part of the struct?
* Why do we even have footers -- will the code work fine without them?
* which functions actually use the data contained in footers?
} block_t;
/* Global variables */
/** @brief Pointer to first block in the heap */
static block_t *heap_start = NULL;
*****************************************************************************
* The functions below are short wrapper functions to perform *
* bit manipulation, pointer arithmetic, and other helper operations. *
* *
* We've given you the function header comments for the functions below *
* to help you understand how this baseline code works. *
* *
* Note that these function header comments are short since the functions *
* they are describing are short as well; you will need to provide *
* adequate details for the functions that you write yourself! *
*****************************************************************************
* ---------------------------------------------------------------------------
* BEGIN SHORT HELPER FUNCTIONS
* ---------------------------------------------------------------------------
* @brief Returns the maximum of two integers.
* @param[in] x
* @param[in] y
* @return `x` if `x > y`, and `y` otherwise.
static size_t max(size_t x, size_t y) {
return (x > y) ? x : y;
* @brief Rounds `size` up to next multiple of n
* @param[in] size
* @param[in] n
* @return The size after rounding up
static size_t round_up(size_t size, size_t n) {
return n * ((size + (n – 1)) / n);
* @brief Packs the `size` and `alloc` of a block into a word suitable for
* use as a packed value.
* Packed values are used for both headers and footers.
* The allocation status is packed into the lowest bit of the word.
* @param[in] size The size of the block being represented
* @param[in] alloc True if the block is allocated
* @return The packed value
static word_t pack(size_t size, bool alloc) {
word_t word = size;
if (alloc) {
word |= alloc_mask;
return word;
* @brief Extracts the size represented in a packed word.
* This function simply clears the lowest 4 bits of the word, as the heap
* is 16-byte aligned.
* @param[in] word
* @return The size of the block represented by the word
static size_t extract_size(word_t word) {
return (word & size_mask);
* @brief Extracts the size of a block from its header.
* @param[in] block
* @return The size of the block
static size_t get_size(block_t *block) {
return extract_size(block->header);
* @brief Given a payload pointer, returns a pointer to the corresponding
* block.
* @param[in] bp A pointer to a block’s payload
* @return The corresponding block
static block_t *payload_to_header(void *bp) {
return (block_t *)((char *)bp – offsetof(block_t, payload));
* @brief Given a block pointer, returns a pointer to the corresponding
* payload.
* @param[in] block
* @return A pointer to the block’s payload
* @pre The block must be a valid block, not a boundary tag.
static void *header_to_payload(block_t *block) {
dbg_requires(get_size(block) != 0);
return (void *)(block->payload);
* @brief Given a block pointer, returns a pointer to the corresponding
* footer.
* @param[in] block
* @return A pointer to the block’s footer
* @pre The block must be a valid block, not a boundary tag.
static word_t *header_to_footer(block_t *block) {
dbg_requires(get_size(block) != 0 &&
“Called header_to_footer on the epilogue block”);
return (word_t *)(block->payload + get_size(block) – dsize);
* @brief Given a block footer, returns a pointer to the corresponding
* header.
* @param[in] footer A pointer to the block’s footer
* @return A pointer to the start of the block
* @pre The footer must be the footer of a valid block, not a boundary tag.
static block_t *footer_to_header(word_t *footer) {
size_t size = extract_size(*footer);
dbg_assert(size != 0 && “Called footer_to_header on the prologue block”);
return (block_t *)((char *)footer + wsize – size);
* @brief Returns the payload size of a given block.
* The payload size is equal to the entire block size minus the sizes of the
* block’s header and footer.
* @param[in] block
* @return The size of the block’s payload
static size_t get_payload_size(block_t *block) {
size_t asize = get_size(block);
return asize – dsize;
* @brief Returns the allocation status of a given header value.
* This is based on the lowest bit of the header value.
* @param[in] word
* @return The allocation status correpsonding to the word
static bool extract_alloc(word_t word) {
return (bool)(word & alloc_mask);
* @brief Returns the allocation status of a block, based on its header.
* @param[in] block
* @return The allocation status of the block
static bool get_alloc(block_t *block) {
return extract_alloc(block->header);
* @brief Writes an epilogue header at the given address.
* The epilogue header has size 0, and is marked as allocated.
* @param[out] block The location to write the epilogue header
static void write_epilogue(block_t *block) {
dbg_requires(block != NULL);
dbg_requires((char *)block == mem_heap_hi() – 7);
block->header = pack(0, true);
* @brief Writes a block starting at the given address.
* This function writes both a header and footer, where the location of the
* footer is computed in relation to the header.
* TODO: Are there any preconditions or postconditions?
* @param[out] block The location to begin writing the block header
* @param[in] size The size of the new block
* @param[in] alloc The allocation status of the new block
static void write_block(block_t *block, size_t size, bool alloc) {
dbg_requires(block != NULL);
dbg_requires(size > 0);
block->header = pack(size, alloc);
word_t *footerp = header_to_footer(block);
*footerp = pack(size, alloc);
* @brief Finds the next consecutive block on the heap.
* This function accesses the next block in the “implicit list” of the heap
* by adding the size of the block.
* @param[in] block A block in the heap
* @return The next consecutive block on the heap
* @pre The block is not the epilogue
static block_t *find_next(block_t *block) {
dbg_requires(block != NULL);
dbg_requires(get_size(block) != 0 &&
“Called find_next on the last block in the heap”);
return (block_t *)((char *)block + get_size(block));
* @brief Finds the footer of the previous block on the heap.
* @param[in] block A block in the heap
* @return The location of the previous block’s footer
static word_t *find_prev_footer(block_t *block) {
// Compute previous footer position as one word before the header
return &(block->header) – 1;
* @brief Finds the previous consecutive block on the heap.
* This is the previous block in the “implicit list” of the heap.
* If the function is called on the first block in the heap, NULL will be
* returned, since the first block in the heap has no previous block!
* The position of the previous block is found by reading the previous
* block’s footer to determine its size, then calculating the start of the
* previous block based on its size.
* @param[in] block A block in the heap
* @return The previous consecutive block in the heap.
static block_t *find_prev(block_t *block) {
dbg_requires(block != NULL);
word_t *footerp = find_prev_footer(block);
// Return NULL if called on first block in the heap
if (extract_size(*footerp) == 0) {
return NULL;
return footer_to_header(footerp);
* —————————————————————————
* END SHORT HELPER FUNCTIONS
* —————————————————————————
/******** The remaining content below are helper and debug routines ********/
*
*
*
*
* @param[in] block
static block_t *coalesce_block(block_t *block) {
* TODO: delete or replace this comment once you’re done.
* Before you start, it will be helpful to review the “Dynamic Memory
* Allocation: Basic” lecture, and especially the four coalescing
* cases that are described.
* The actual content of the function will probably involve a call to
* find_prev(), and multiple calls to write_block(). For examples of how
* to use write_block(), take a look at split_block().
* Please do not reference code from prior semesters for this, including
* old versions of the 213 website. We also discourage you from looking
* at the malloc code in CS:APP and K&R, which make heavy use of macros
* and which we no longer consider to be good style.
return block;
*
*
*
*
* @param[in] size
static block_t *extend_heap(size_t size) {
// Allocate an even number of words to maintain alignment
size = round_up(size, dsize);
if ((bp = mem_sbrk(size)) == (void *)-1) {
return NULL;
* TODO: delete or replace this comment once you’ve thought about it.
* Think about what bp represents. Why do we write the new block
* starting one word BEFORE bp, but with the same size that we
* originally requested?
// Initialize free block header/footer
block_t *block = payload_to_header(bp);
write_block(block, size, false);
// Create new epilogue header
block_t *block_next = find_next(block);
write_epilogue(block_next);
// Coalesce in case the previous block was free
block = coalesce_block(block);
return block;
*
*
*
*
* @param[in] block
* @param[in] asize
static void split_block(block_t *block, size_t asize) {
dbg_requires(get_alloc(block));
/* TODO: Can you write a precondition about the value of asize? */
size_t block_size = get_size(block);
if ((block_size – asize) >= min_block_size) {
block_t *block_next;
write_block(block, asize, true);
block_next = find_next(block);
write_block(block_next, block_size – asize, false);
dbg_ensures(get_alloc(block));
*
*
*
*
* @param[in] asize
static block_t *find_fit(size_t asize) {
block_t *block;
for (block = heap_start; get_size(block) > 0; block = find_next(block)) {
if (!(get_alloc(block)) && (asize <= get_size(block))) {
return block;
return NULL; // no fit found
*
*
*
*
* @param[in] line
bool mm_checkheap(int line) {
* TODO: Delete this comment!
* You will need to write the heap checker yourself.
* Please keep modularity in mind when you’re writing the heap checker!
* As a filler: one guacamole is equal to 6.02214086 x 10**23 guacas.
* One might even call it… the avocado’s number.
* Internal use only: If you mix guacamole on your bibimbap,
* do you eat it with a pair of chopsticks, or with a spoon?
return true;
*
*
*
*
bool mm_init(void) {
// Create the initial empty heap
word_t *start = (word_t *)(mem_sbrk(2 * wsize));
if (start == (void *)-1) {
return false;
* TODO: delete or replace this comment once you’ve thought about it.
* Think about why we need a heap prologue and epilogue. Why do
* they correspond to a block footer and header respectively?
start[0] = pack(0, true); // Heap prologue (block footer)
start[1] = pack(0, true); // Heap epilogue (block header)
// Heap starts with first “block header”, currently the epilogue
heap_start = (block_t *)&(start[1]);
// Extend the empty heap with a free block of chunksize bytes
if (extend_heap(chunksize) == NULL) {
return false;
return true;
*
*
*
*
* @param[in] size
void *malloc(size_t size) {
dbg_requires(mm_checkheap(__LINE__));
size_t asize; // Adjusted block size
size_t extendsize; // Amount to extend heap if no fit is found
block_t *block;
void *bp = NULL;
// Initialize heap if it isn’t initialized
if (heap_start == NULL) {
mm_init();
// Ignore spurious request
if (size == 0) {
dbg_ensures(mm_checkheap(__LINE__));
return bp;
// Adjust block size to include overhead and to meet alignment requirements
asize = round_up(size + dsize, dsize);
// Search the free list for a fit
block = find_fit(asize);
// If no fit is found, request more memory, and then and place the block
if (block == NULL) {
// Always request at least chunksize
extendsize = max(asize, chunksize);
block = extend_heap(extendsize);
// extend_heap returns an error
if (block == NULL) {
return bp;
// The block should be marked as free
dbg_assert(!get_alloc(block));
// Mark block as allocated
size_t block_size = get_size(block);
write_block(block, block_size, true);
// Try to split the block if too large
split_block(block, asize);
bp = header_to_payload(block);
dbg_ensures(mm_checkheap(__LINE__));
return bp;
*
*
*
*
* @param[in] bp
void free(void *bp) {
dbg_requires(mm_checkheap(__LINE__));
if (bp == NULL) {
block_t *block = payload_to_header(bp);
size_t size = get_size(block);
// The block should be marked as allocated
dbg_assert(get_alloc(block));
// Mark the block as free
write_block(block, size, false);
// Try to coalesce the block with its neighbors
block = coalesce_block(block);
dbg_ensures(mm_checkheap(__LINE__
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com