/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-----------------------------------------------------1) INFORMATION -----------------------------------------------------
Project: Dynamic Storage Allocator
Author Names: [Alexander Pretka (B.S. Computer Engineering) & Ayush Chhangani (M.S. Computer Science and Engineering)]
Date: October 20th, 2023
Insitution: Pennsylvania State University
Class: Computer Science (CMPSC) 473 - Operating Systems Design & Construction
Instructor: Ruslan Nikolaev (Assistant Professor)
File Name: mm.c [The only C file to edit for this project]
PROJECT 1 CHECKPOINT 1 TIMELINE (12 Days):
• Start Date: Friday, September 22nd, 2023
• Finish Date: Tuesday, October 3rd, 2023
Friday, 9/22/23 --- Introduce ourselves to each other.
Read the project description.
Took notes on the project description.
Saturday, 9/23/23 --- Cloned the project repository from the provided GitHub link.
Familiarize ourselves with the provided memlib.c functions.
Sunday, 9/24/23 --- Worked on the mm_init function for memory initialization.
Test to see if malloc returns a 16-byte aligned pointer.
Monday, 9/25/23 --- Wrote test cases for mm_init and malloc.
Implemented free functions to release memory blocks.
Implemented null pointers.
Tuesday, 9/26/23 --- Wrote test cases to verify correctness of free function.
Updated mm_checkheap function to check for proper free block management.
Wednesday, 9/27/23 --- Implemented the realloc function to resize allocated memory.
Wrote test cases for the realloc function.
Thursday, 9/28/23 --- Optimized allocator for space efficiency and allocation speed.
Tried using techniques like segregated free lists.
Friday, 9/29/23 --- Conducted preliminary benchmarking tests to assess the allocator's performance.
Test your allocator with a variety of trace files using the provided mdriver.
Saturday, 9/30/23 --- Made use of heap checker to identify and fix any inconsistencies.
Sunday, 10/1/23 --- Tested realloc with shrinking, expanding, and moving memory.
Monday, 10/2/23 --- Updated the README.md file
Tested the program on the W135 machines to ensure compatibility.
Tuesday, 10/3/23 --- Tested the program on the W135 machines to ensure effecient memory utilization.
Wednesday, 10/4/23 --- Debugged and tested the program again on the W135 machines to ensure more effecient memory
utilization.
PROJECT 1 Final Submission TIMELINE (17 Days):
• Start Date: Wednesday, October 4th, 2023
• Finish Date: Friday, October 20th, 2023
Wednesday, 10/4/23 --- Read the project description.
Brainstormed ways on how to use space utilization and throughput in our code.
Debugged our code with the gdb mdriver
Thursday, 10/5/23 --- Familiarize ourselves with the provided min and max target
Friday, 10/6/23 --- Obsrevd the aggregate amount of memory used by the driver
Test to see if malloc returns a 16-byte aligned pointer.
Saturday, 10/7/23 --- Wrote the throughput metric to measures the average number of operations.
Wrote the space utlization metric to measures the average number of operations.
Sunday, 10/8/23 --- Wrote additional test cases to verify correctness of malloc, realloc, and free function.
Monday, 10/9/23 --- Scripted a heap checker, mm_checkheap, that scans the heap and checks it for consistency.
Tuesday, 10/10/23 --- Checked pointers in the free list point to valid free blocks.
Checked if any of the allocated blocks overlap.
Implemented error messages to print out if the checks fails.
Wednesday, 10/11/23 --- Conducted preliminary benchmarking tests to assess the allocator's performance
to make sure the maketest file ran correctly.
Thursday, 10/12/23 --- Made use of heap checker to pass in the line number of the caller.
Friday, 10/13/23 --- Tested the program again on the W135 machines to ensure space ultization and throughput
rate was utilized effeciently.
Debugged as needed
Saturday, 10/14/23 --- Tested the program again on the W135 machines to ensure space ultization and throughput
rate was utilized effeciently.
Debugged as needed
Sunday, 10/15/23 --- Tested the program again on the W135 machines to ensure space ultization and throughput
rate was utilized effeciently.
Debugged as needed
Monday, 10/16/23 --- Updated the README.md file
Tested the program again on the W135 machines to ensure space ultization and throughput
rate was utilized effeciently.
Tuesday, 10/17/23 --- debugged various malloc issues in the code.
Wednesday, 10/18/23 --- Added HeapChecker and fixed certain bugs
Thursday, 10/19/23 ---
Friday, 10/20/23 ---
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* -------------------------------2) Description of Alexander's & Ayush's Solution--------------------------------------
We designed a custom dynamic storage allocator, our own version of malloc, free, and realloc, through implementing
various features and utilizing a systematic approach to ensure reliability and correctness through 7 easy steps:
• STEP 1) We first defined static helper functions and structures to enhance code modularity and maintainability within
the allocator. These functions and structures assisted in managing the internal data structures and operations of the
allocator performing memory management.
• STEP 2) We initialized the initial heap area using the mm_init function. This initialization was critical for
setting up the memory allocation in the code. The mm_init function returned true on successful initialization and
false if any issues arose during the process of testing the code.
• STEP 3) We designed our malloc function to return 16-byte aligned pointers. This alignment ensures that the memory
allocated meeted the certain CMPSC 473 Project 1 alignment requirements, which can be important for future performance
optimizations on different hardware linux architectures.
• STEP 4) We implemented the free function, allowing users of the program to deallocate memory previously allocated
using malloc. This function ensures that the memory can be reused for future allocations.
• STEP 5) We included a realloc function that returns a pointer to an allocated region of at least the specified size.
This function enables users to resize previously allocated memory blocks, and it ensures that the new memory region
meets the requested size requirements which could have been 1 to 16 bytes.
• STEP 6) To maintain the utilization of the allocated heap, we implemented a heap checker. This checker scans the heap
and verifies its consistency. We made it easy to identify issues by incorporating a mechanism to pass the line number
of the caller when invoking mm_checkheap. This way, if any problems were detected, we could quickly pinpoint which part
of the code caused the issue.
• STEP 7) To ensure the correctness of my allocator and verify that it met its specifications, we adopted a systematic
testing approach. We compiled and built the code using 'make' every time I made changes to the code or test cases.
Additionally, we created a suite of test cases and automated them using 'make test.' This allowed us to easily run all
the tests and confirm that my allocator consistently produced the expected results.
OVERVIEW: We created a custom dynamic storage allocator that is a well-designed and thoroughly tested memory management
system. It offers 16-byte aligned memory allocation, seamless resizing of memory blocks, and a robust heap checker f
or maintaining heap consistency, all while adhering to best practices in coding, testing, and development.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* ------------------------------------ Preprocessor Directives --------------------------------------------------*/
#include <assert.h> // If condition is true in program, nothing happens
// If condition is false in program, program terminates
#include <stdio.h> // Provides functions for input and output operations: printf
#include <stdlib.h> // used for memory management: malloc(), calloc(), realloc(), and free()
#include <string.h> // Strings and character arrays
#include <errno.h> // Provides error code definitions and error handling functions.
#include <unistd.h> // Used for file operations: open(), close(), read(), write(), lseek(), fork(), exec()
#include <stdbool.h> // Provides True (1) and False (0) values
#include <stdint.h> // Used for system with different word sizes: int8_t, int16_t, int32_t, and int64_t
#include "mm.h" /* File preprocessor directives to conditionally declare memory allocation functions
based on whether the DRIVER macro is defined or not. */
#include "memlib.h" // File for memory initialization, manipulation, and debugging
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* --------------------------- Redefining Standard Memory Allocation (Helper Functions) -------------------------------*/
#define DEBUG [UNCOMMENT THIS LINE TO ENABLE DEBUGGING !!!!!!!!!]
#ifdef DEBUG
/* When debugging is enabled, the underlying functions get called */
#define dbg_printf(...) printf(__VA_ARGS__)
#define dbg_assert(...) assert(__VA_ARGS__)
#else
/* When debugging is disabled, no code gets generated */
#define dbg_printf(...)
#define dbg_assert(...)
#endif /* DEBUG */
#ifdef DRIVER // DO NOT CHANGE THIS LINE !!!!!!!!
/* 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 /* DRIVER */
#define WSIZE sizeof(void *) /* Word and header/footer size in bytes for the memory block */
#define DSIZE (2 * WSIZE) /* Doubleword size (bytes) */
#define ExtendHeap (1 << 12) /* Increase the heap size by this amount (in bytes) */
static void place(void *ptr, size_t asize);
static void remove_from_free_list(void *ptr);
static char *free_list_start = 0;
static void *find_fit(size_t asize);
static void *extend_heap(size_t words);
static void insert_in_free_list(void *ptr);
static char *heap_listp = 0;
static void *combine(void *ptr);
size_t PACKAAllocationAllocation(size_t size, size_t alloc) { // Helper Function
return size | alloc;
}
uintptr_t GETAddress(void *p) {
return *(uintptr_t *)p;
}
// Helper function to calculate the maximum of two values
size_t MAX(size_t x, size_t y) {
return (x > y) ? x : y;
}
// Helper function to extract the size from a pointer
size_t GET_SIZE(void *ptr) {
return (uintptr_t)ptr & ~(DSIZE - 1);
}
// Helper function to calculate the footer pointer of a block
void *FTRP(void *ptr) {
return (void *)((char *)ptr + GET_SIZE((void *)((char *)ptr - WSIZE)) - DSIZE);
}
// Helper function to calculate the next block's address
void *NEXT_Block_Address(void *ptr) {
return (void *)((char *)ptr + GET_SIZE((void *)((char *)ptr - WSIZE)));
}
// Helper function to calculate the previous block's address
void *PREV_Block_Address(void *ptr) {
return (void *)((char *)ptr - GET_SIZE((void *)((char *)ptr - DSIZE)));
}
// Helper function to extract the next pointer from a block
void *GET_NEXT_PTR(void *ptr) {
return *(char **)((char *)ptr + WSIZE);
}
// Helper function to extract the previous pointer from a block
void *GET_PREV_PTR(void *ptr) {
return *(char **)ptr;
}
// Helper function to set the next pointer of a block
void SET_NEXT_PTR(void *ptr, void *qp) {
*(char **)((char *)ptr + WSIZE) = qp;
}
// Helper function to set the previous pointer of a block
void SET_PREV_PTR(void *ptr, void *qp) {
*(char **)ptr = qp;
}
// Helper function to write a word at the given address
void PUT(void *p, uintptr_t val) {
*(uintptr_t *)p = val;
}
// Helper function to check if a block is allocated
int GET_ALLOC(void *p) {
return (GET_SIZE(p) & 0x1);
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* ----------------------------------------- Memory Alignment Requirements ------------------------------------------*/
/* What is the correct alignment? */
#define ALIGNMENT 16
/* rounds up to the nearest multiple of ALIGNMENT */
static size_t align(size_t x)
{
return ALIGNMENT * ((x+ALIGNMENT-1)/ALIGNMENT);
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/*-----------------------------------------------------------3) MM_INIT----------------------------------------------------
FROM PROJECT 1 DOCUMENT ON CANVAS: m_init: Before calling malloc, realloc, calloc, or free, the application program
calls the mm_init function to perform any necessary initializations, such as allocating the initial heap area. The
return value should be true on success and false if there were any problems in performing the initialization.
Initialize: returns false on error, true on success. initializes the memory management system. This function perform
tasks such as setting up the initial memory pool, data structures, various resources for memory allocation
and deallocation. */
// True = Success
// False = Error
bool mm_init(void) //Ayush
{
if ((heap_listp = mem_sbrk(8*WSIZE)) == NULL) // I created the initial empty heap
return false;
PUT(heap_listp, 0); // Alignment padding
PUT(heap_listp + (1 * WSIZE), PACKAAllocationAllocation(DSIZE, 1)); // The Prologue header
PUT(heap_listp + (2 * WSIZE), PACKAAllocationAllocation(DSIZE, 1)); // The Prologue footer
PUT(heap_listp + (3 * WSIZE), PACKAAllocationAllocation(0, 1)); // The Epilogue header
free_list_start = heap_listp + 2*WSIZE;
if (extend_heap(4) == NULL){
return false;
}
return true;
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/*-----------------------------------------------------------4) MALLOC----------------------------------------------------
FROM PROJECT 1 DOCUMENT ON CANVAS: malloc: The malloc function returns a pointer to an allocated block payload of at
least size bytes. The entire allocated block should lie within the heap region and should not overlap with any other
allocated chunk. If the requested size is 0 or if mem_sbrk is unable to extend the heap, then you should return NULL.
This is similar to how the standard C library (libc) always returns payload pointers that are aligned to 16 bytes, your
malloc implementation should do likewise and always return 16-byte aligned pointers.
malloc (memory allocation) - to dynamically allocate memory on the heap. The heap is a region of the computer's memory where date
can be stored and managed at runtime.)
When I use malloc, I specify the amount of memory you want to allocate, and it returns a pointer to the first byte of the
allocated memory block. This allows us to create data structures of variable size and manage memory more flexible in the
program.*/
// MALLOC always returns 16-byte aligned pointers
// requestedSize = 0 || mem_sbrk = error
// return NULL;
void* mm_malloc(size_t size) // Alex
{
size_t asize; // Adjusting the size of the block
size_t extendsize; // Increasing the heap size
void* ptr; // Pointer to the allocated block
if (size == 0)
return (NULL); // Return NULL for allocation that have no size
if (size <= DSIZE)
asize = DSIZE * (2); // setting the minimum block size
else
asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE); // requesting the block size
if ((ptr = find_fit(asize)) != NULL) // Result in the find fit function
{
place(ptr, asize); // Allocate the block
return (ptr); // Return the block
}
extendsize = MAX(asize, ExtendHeap);
if ((ptr = extend_heap(extendsize / WSIZE)) == NULL) // Extending the heap
return (NULL); // Failed heap extension = NULL
place(ptr, asize); // Allocated the extended block
return (ptr); // Returns the pointer to the allocated block
}
static void place(void *ptr, size_t asize)
{
size_t csize = GET_SIZE((void *)(ptr) - WSIZE); // Calculate the size of the block preceding 'ptr'
if ((csize - asize) >= 4 * WSIZE) // If there's enough space to split the block into two:
{
PUT((void *)(ptr) - WSIZE, PACKAAllocationAllocation(asize, 1)); // Set the header and footer of the allocated block
PUT(FTRP(ptr), PACKAAllocationAllocation(asize, 1));
remove_from_free_list(ptr); // Remove the block from the free list
ptr = NEXT_Block_Address(ptr); // Move 'ptr' to the next block
// Setting the header and footer of the remaining free block
PUT((void *)(ptr) - WSIZE, PACKAAllocationAllocation(csize - asize, 0));
PUT(FTRP(ptr), PACKAAllocationAllocation(csize - asize, 0));
}
else
{
// If there's not enough space to split the block, We are setting the header and footer of the allocated block
PUT((void *)(ptr) - WSIZE, PACKAAllocationAllocation(csize, 1));
PUT(FTRP(ptr), PACKAAllocationAllocation(csize, 1));
remove_from_free_list(ptr); // Remove the block from the free list
}
}
static void remove_from_free_list(void *ptr)
{
if (GET_PREV_PTR(ptr))
{
// If there is a previous block in the free list, update its next pointer
SET_NEXT_PTR(GET_PREV_PTR(ptr), GET_NEXT_PTR(ptr));
}
else
{
// If 'ptr' was the first block in the free list, update the start of the free list
free_list_start = GET_NEXT_PTR(ptr);
}
// Update the previous pointer of the next block (if it exists)
SET_PREV_PTR(GET_NEXT_PTR(ptr), GET_PREV_PTR(ptr));
}
// Function to find a suitable free block for asize:
static void* find_fit(size_t asize)
{
void* ptr; // Pointer used for traversal
static int SizeMallocLAST = 0; // Size of last allocated block
static int CounterRepeat = 0; // Count consecutive repeated block sizes
if (SizeMallocLAST == (int)asize) // extend the heap to prevent excessive repetition.
{
if (CounterRepeat > 30) // If the same size has been allocated more than 30 times in a row,
{
int Sizeextendsize = MAX(asize, (4) * WSIZE);
ptr = extend_heap(Sizeextendsize / 4);
return ptr; // return the pointer
}
else
CounterRepeat++;
}
else
CounterRepeat = 0;
for (ptr = free_list_start; GET_ALLOC(((void*)(ptr) - WSIZE)) == 0; ptr = GET_NEXT_PTR(ptr)) // Loop through the free blocks in the free list
{
if (asize <= (size_t)GET_SIZE(((void*)(ptr) - WSIZE))) // last allocated size and return the pointer to it.
{
SizeMallocLAST = asize;
return ptr;
}
}
return NULL; // Return NULL if no suitable block is found in the free list
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/*-----------------------------------------------------------5) FREE------------------------------------------------------
FROM PROJECT 1 DOCUMENT ON CANVAS: free: The free function frees the block pointed to by ptr. It returns nothing. This
function is only guaranteed to work when the passed pointer (ptr) was returned by an earlier call to malloc, calloc, or
realloc and has not yet been freed. If ptr is NULL, then free should do nothing
free - releasing previously allocated memory so that it can be returned to the system's memory pool for reuse. This is to
prevent memory leaks and utilize avaliable system resources.*/
// Call to malloc || calloc || realloc
// ptr = free block
// return 0;
// ptr = NULL
// free = false
void free(void *ptr) // Ayush implemented this:
{
size_t size; // Declare a variable to store the size of the block
if (ptr == NULL) // Check if 'ptr' is NULL (i.e., if you're trying to free a NULL pointer)
return; // If 'ptr' is NULL, there's nothing to free, so just return.
size = GET_SIZE((void *)(ptr) - WSIZE); // Calculate the size of the block to be freed
PUT((void *)(ptr) - WSIZE, PACKAAllocationAllocation(size, 0)); // Set the header and footer of the block to indicate
PUT(FTRP(ptr), PACKAAllocationAllocation(size, 0)); // it's no longer allocated
return; // Exit the function after freeing the block.
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* -----------------------------------------------------------6) REALLOC---------------------------------------------------
FROM PROJECT 1 DOCUMENT ON CANVAS: realloc: The realloc function returns a pointer to an allocated region of at least
size bytes with the following constraints:
– if ptr is NULL, the call is equivalent to malloc(size);
– if size is equal to zero, the call is equivalent to free(ptr);
– if ptr is not NULL, it must have been returned by an earlier call to malloc, calloc, or realloc.
The call to realloc changes the size of the memory block pointed to by ptr (the old block) to size bytes
and returns the address of the new block. Notice that 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 8 bytes and the new block
is 12 bytes, then the first 8 bytes of the new block are identical to the first 8 bytes of the old block and the
last 4 bytes are uninitialized. Similarly, if the old block is 8 bytes and the new block is 4 bytes, then the
contents of the new block are identical to the first 4 bytes of the old block.
realloc - "reallocation" - used to change the size of previously allocated block of memory. */
// ptr = NULL --> call = malloc(size)
// size = 0 --> call = free(ptr)
// ptr = notNULL --> returned by malloc || calloc || realloc
void* realloc(void* ptr, size_t size) // Alex
{
if ((int)size == 0) { // Check if 'size' is zero; if so, it will call free. Typecasting is needed.
free(ptr);
}
else if (ptr == NULL) { // Check if 'ptr' is NULL; allocate new memory using malloc if it is.
malloc(size);
}
else if ((int)size < 0) { // Check if 'size' is negative; return NULL if it is.
return NULL;
}
else if (size > 0) { // Check if 'size' is positive.
size_t oldsize = GET_SIZE((void*)(ptr) - WSIZE); // Calculate the old size of the memory block
size_t newsize = size + 2 * WSIZE; // 2 words for header and footer
/* If newsize is less than or equal to oldsize, we just return ptr */
if (newsize <= oldsize) {
return ptr;
}
/* If newsize is greater than oldsize */
else {
size_t next_alloc = GET_ALLOC((void*)(NEXT_Block_Address(ptr) - WSIZE));
size_t csize;
/* Check if the next block is free and the combined size is sufficient */
if (!next_alloc && ((csize = oldsize + GET_SIZE((void*)(NEXT_Block_Address(ptr) - WSIZE))) >= newsize)) {
remove_from_free_list(NEXT_Block_Address(ptr)); // Combine the two blocks and return ptr
PUT((void*)(ptr) - WSIZE, PACKAAllocationAllocation(csize, 1));
PUT(FTRP(ptr), PACKAAllocationAllocation(csize, 1));
return ptr;
}
else {
void* new_ptr = malloc(newsize); // Allocate a new memory block and copy the data to it
place(new_ptr, newsize);
memcpy(new_ptr, ptr, newsize);
free(ptr); // Free the old memory block and return the new one
return new_ptr;
}
}
}
return NULL;
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* -----------------------------------------------------------CALLOC---------------------------------------------------
calloc - "contigous allocation" - used to allocate a block of memory for an array of elements and initialize all the elements to 0
This function is not tested by mdriver, and has been implemented for you. */
void* calloc(size_t nmemb, size_t size)
{
// Declare a pointer variable to store the allocated memory block
void* ptr;
// Calculate the total size to allocate by multiplying 'nmemb' and 'size'
size *= nmemb;
// Call the 'malloc' function to allocate memory of the calculated size
ptr = malloc(size);
// Check if the memory allocation was successful (i.e., 'ptr' is not NULL)
if (ptr) {
// If memory allocation succeeded, initialize the allocated block with zeros
memset(ptr, 0, size);
}
// Return the pointer to the allocated (and possibly initialized) memory block
return ptr;
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* ------------------------------------------HELPFUL DEBUGGING SCRIPT #1------------------------------------------------*/
static bool in_heap(const void* p) // Check if a given pointer 'p' is within the allocated heap space.
{
return p <= mem_heap_hi() && // Check if 'p' is less than or equal to the highest address within the heap.
p >= mem_heap_lo(); // Check if 'p' is greater than or equal to the lowest address within the heap.
}
// Professor Note: returns whether the pointer is in the heap. may be useful for debugging.
/* My Note: in_heap function is used to determine whether a given pointer p points to memory within the heap managed by
the memory allocator. It helps ensure that operations like memory allocation and deallocation are performed only on valid
memory within the allocator's managed heap, preventing access or modification of memory outside that region,
which could lead to undefined behavior or memory corruption. */
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
/* ------------------------------------------HELPFUL DEBUGGING SCRIPT #2------------------------------------------------*/
static bool aligned(const void* p) // Check if a given pointer 'p' is aligned according to my alignment requirement.
{
size_t ip = (size_t) p; // Convert the pointer 'p' to an integer representation ('ip').
return align(ip) == ip; /* Call the 'align' function (assumed to exist elsewhere) on 'ip'
and check if the result is equal to the original integer 'ip'. */
}
static void *extend_heap(size_t words) {
char *ptr ;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
//Since minimum block size given to us is 4 words (ie 16 bytes)
if (size < 16){
size = 16;
}
/* call for more memory space */
if ((intptr_t)(ptr = mem_sbrk(size)) == -1){
return NULL;
}
/* Initialize free block header/footer and the epilogue header */
PUT(((void *)(ptr) - WSIZE), PACKAAllocationAllocation(size, 0)); /* free block header */
PUT(FTRP(ptr), PACKAAllocationAllocation(size, 0)); /* free block footer */
PUT(((void *)(ptr) - WSIZE), PACKAAllocationAllocation(0, 1)); /* new epilogue header */
/* combine ptr with next and previous blocks */
return combine(ptr);
}
static void *combine(void *ptr) {
// Check if the previous block is allocated or its size is zero (0):
size_t NEXT_ALLOC = GET_ALLOC(((void *)(ptr) - WSIZE));
size_t PREV_ALLOC = GET_ALLOC(FTRP(PREV_Block_Address(ptr))) || PREV_Block_Address(ptr) == ptr;
size_t size = GET_SIZE(((void *)(ptr) - WSIZE));
/* Next block is only free */
if (PREV_ALLOC && !NEXT_ALLOC) {
size += GET_SIZE(((void *)(NEXT_Block_Address(ptr)) - WSIZE)); // Combine the size of the current and next free blocks
remove_from_free_list(NEXT_Block_Address(ptr)); // Remove the next block from the free list
PUT(((void *)(ptr) - WSIZE), PACKAAllocationAllocation(size, 0)); // Update the header and footer of the current block
PUT(FTRP(ptr), PACKAAllocationAllocation(size, 0));
}
/* Prev block is only free */
else if (!PREV_ALLOC && NEXT_ALLOC) {
// Combine the size of the current and previous free blocks
size += GET_SIZE(((void *)(PREV_Block_Address(ptr)) - WSIZE));
ptr = PREV_Block_Address(ptr); // Move 'ptr' to the previous block
remove_from_free_list(ptr); // Remove the previous block from the free list
PUT(((void *)(PREV_Block_Address(ptr)) - WSIZE), PACKAAllocationAllocation(size, 0)); // Update the header and footer
PUT(FTRP(ptr), PACKAAllocationAllocation(size, 0));
}
/* Both blocks are free */
else if (!PREV_ALLOC && !NEXT_ALLOC) {
// Combine the size of the current, previous, and next free blocks
size += GET_SIZE(((void *)(PREV_Block_Address(ptr)) - WSIZE)) + GET_SIZE(((void *)(NEXT_Block_Address(ptr)) - WSIZE));
remove_from_free_list(PREV_Block_Address(ptr)); // Remove both the previous and next blocks from the free list
remove_from_free_list(NEXT_Block_Address(ptr));
ptr = PREV_Block_Address(ptr); // Move 'ptr' to the previous block
PUT(((void *)(ptr) - WSIZE), PACKAAllocationAllocation(size, 0)); // Update the header and footer of the current block
PUT(FTRP(ptr), PACKAAllocationAllocation(size, 0));
}
/* Lastly, insert 'ptr' into the free list and return 'ptr' */
insert_in_free_list(ptr);
return ptr;
}
static void insert_in_free_list(void *ptr) {
SET_NEXT_PTR(ptr, free_list_start); // Set the next pointer of 'ptr' to the current start of the free list
SET_PREV_PTR(free_list_start, ptr); // Set the previous pointer of the current start of the free list to 'ptr'
SET_PREV_PTR(ptr, NULL); // Set the previous pointer of 'ptr' to NULL
free_list_start = ptr; // Update the start of the free list to 'ptr'
}
// Professor Note: returns whether the pointer is aligned. may be useful for debugging
/* My Note: memory allocators use alignment to ensure that memory blocks are positioned at specific addresses that meet
the application-specific alignment constraints.*/
/* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
/* ------------------------------------------------7) HEAP CHECKER------------------------------------------------------
FROM PROJECT 1 DOCUMENT ON CANVAS: The heap checker will check for invariants which should always be true.
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?
You should implement checks for any invariants you consider prudent. It returns true if your heap is in a valid,
consistent state and false otherwise. You are not limited to the listed suggestions nor are you required to check all
of them. You are encouraged to print out error messages when the check fails. You can use dbg_printf to print
messages in your code in debug mode. To enable debug mode, uncomment the line #define DEBUG. To call the heap checker,
you can use mm_checkheap( LINE ), which will pass in the line number of the caller. This can be used to identify which
line detected a problem.
heap checker - to verify the correctness and integrity of the heap data structure in a program's memory. The "heap"
refers to a region of a program's memory used for dynamic memory allocation, where data is allocated and deallocated
during program execution */
static void checkblock(void *ptr) //Ayush
{
if ((uintptr_t)ptr % DSIZE)
printf("Error: %p is not doubleword aligned\n", ptr);
if (GETAddress(((void *)(ptr) - WSIZE)) != GETAddress(FTRP(ptr)))
printf("Error: header does not match footer\n");
}
bool mm_checkheap(int lineno) //Ayush
{
#ifdef DEBUG
/* Write code to check heap invariants here */
/* IMPLEMENT THIS */
void *ptr;
// Check for consistency of the prologue block
// Check for consistency of the prologue block
if (GET_SIZE(((void *)(heap_listp) - WSIZE)) != DSIZE || !GET_ALLOC(((void *)(heap_listp) - WSIZE))) {
printf("Error at line %d: Bad prologue header\n", lineno);
return false;
}
checkblock(heap_listp);
// Check for the consistency of the epilogue block
for (ptr = heap_listp; GET_SIZE(((void *)(ptr) - WSIZE)) > 0; ptr = NEXT_Block_Address(ptr)) {
// Check each block in the heap
// Add more checks here based on your heap invariants
checkblock(ptr);
}
if (GET_SIZE(((void *)(ptr) - WSIZE)) != 0 || !GET_ALLOC(((void *)(ptr) - WSIZE))) {
printf("Error at line %d: Bad epilogue header\n", lineno);
return false;
}
#endif /* DEBUG */
return true;
}
/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
