[2022] CMPSC473 Operating Systems - Malloc Lab: Writing a Dynamic Storage
CMPSC473, Summer 2022 Malloc Lab: Writing a Dynamic Storage Allocator Assigned
Please read this document carefully!
1 Introduction
In this lab, you will be writing a dynamic storage allocator for C programs, i.e., your own version of the malloc, free, and realloc functions. You are encouraged to explore the design space creatively and implement an allocator that is correct, space efficient, and fast.
The only file you will be modifying is mm.c. Modifications in other files will not be used in the grading. You will be implementing the following functions:
• bool mm init(void)
• void* malloc(size t size)
• void free(void* ptr)
• void* realloc(void* oldptr, size t size) • bool mm checkheap(int lineno)
You are encouraged to define other (static) helper functions, structures, etc. to better structure your code.
2 Programming Rules
· IMPORTANT: You are required to implement a heap checker (see Section 5) that will be graded. The heap checker will help you debug your code.
· IMPORTANT: You are required to write comments for all of your code including the heap checker. Additionally, you need to write a file comment at the top of the file describing your overall malloc design. See Section 7 for grading details.
· You are not allowed to change any of the interfaces in mm.c.
· You are not allowed to invoke any memory-management related library calls or system calls. For example, you are not allowed to use sbrk, brk, or the standard library versions of malloc, calloc, free, or realloc. Instead of sbrk, you should use our provided mem sbrk.
· Your code is expected to work in 64-bit environments, and you should assume that allocation sizes and offsets will require 8 byte (64-bit) representations.
· You are not allowed to use macros as they can be error-prone. The better style is to use static functions and let the compiler inline the simple static functions for you.
· You are limited to 128 bytes of global space for arrays, structs, etc. If you need large amounts of space for storing extra tracking data, you can put it in the heap area.
IMPORTANT: Failure to abide by these requirements may result in a 0 for the assignment.
3 Description of the dynamic memory allocator functions
• mm init: Before calling malloc, realloc, calloc, or free, the application program (i.e., the trace- driven driver program that will evaluate your code) calls your 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.
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. 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.
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.
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.
These semantics match the semantics of the corresponding libc malloc, realloc, and free functions.Run man malloc to view complete documentation.
4 Support Functions
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(int incr): Expands the heap by incr bytes, where incr is a positive non-zero inte- ger. It returns a generic pointer to the first byte of the newly allocated heap area. The semantics are identical to the Unix sbrk function, except that mem sbrk accepts only a non-negative integer argument. You must use our version, mem sbrk, for the tests to work. Do not use sbrk.
· 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 Linux systems).
· void* memset(void* ptr, int value, size t n): Sets the first nbytes of memory pointed to by ptr to value.
void* memcpy(void* dst, const void* src, size t n): Copies nbytes from src to dst.
5 Heap Consistency Checker
Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. They are difficult to program correctly because they involve a lot of untyped pointer manipulation and low-level manipulation of bits and bytes. You will find it very helpful to write a heap checker mm checkheap that scans the heap and checks it for consistency. 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 escapedcoalescing?
- 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.
You are required to implement a heap checker for your code, both for grading and debugging purposes. See Section 7 for details on grading.
